{"id":"3b291f81-0b87-464c-8ff9-c0fd3687247a","arxiv_id":"2508.13288","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper proposes Hierarchical Conformal Classification, a conformal prediction method that builds prediction sets from nodes of a label DAG with a finite-sample coverage guarantee, using a pruned search over non-overlapping leaf covers.","lead":"Conformal prediction returns label sets with guaranteed coverage, but treats labels as flat. This paper adds a class hierarchy so the set can contain general categories as well as specific labels, and tests the idea on text, image, and audio data.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1 is false for a fixed alpha: excluding a leaf with prior below alpha preserves coverage, so restricting Eq. (3) to NOL-covers can discard the true optimum.","rationale":"The reader's weakest assumption matches the main load-bearing concern: Proposition 1 is the step that reduces a 2^{|V|} search to NOL-covers, and the paper explicitly relies on it to claim that the smaller search space preserves optimality. The counterexample above is not contrived to a pathological edge case; it uses a rare leaf whose prior is below α, which is exactly the regime a fixed-α formulation must handle. Proposition 2 is also not independent of this flaw: its pruning step may reduce both |N| and the leaf-cover size, but it does not prove that the reduced set still satisfies the coverage constraint when the original set did not cover every leaf. Appendix B compounds the issue with an incorrect recurrence for perfect binary trees: the paper's recurrence gives C(3)=16, whereas the correct recursion f(d)=1+f(d-1)^2 gives f(3)=26, so the claimed search-space growth rate is inaccurate. The empirical results and released benchmarks may still be useful as a heuristic, and the user-study limitations do not need to be invoked to reach a verdict. But the paper's central theoretical claims of guaranteed optimality and a correct hierarchical coverage theorem are not established by the presented arguments, so the rejection is warranted.","tokens_in":15758,"tokens_out":7756,"duration_ms":82914,"concrete_test":"Run an exhaustive enumeration of all subsets of the 5-node DAG described above (root, AB, A, B, C) with the stated priors, α=0.02, and β=0.1, evaluating each subset's coverage P(yt∈leaf-cov(S)) and objective |S|+β|leaf-cov(S)|. If the minimizer is {AB}, which is not a NOL-cover, Proposition 1 and the optimality-preserving pruning claim fail. The same check can then be repeated with β swept over a grid to see the size of the objective gap.","verdict_should_be":"REJECT","load_bearing_attack":"Proposition 1 (necessity of leaf coverage) asserts that any feasible solution to Eq. (3) must satisfy leaf-cov(S)=Y. The proof establishes only that a set omitting a leaf y* violates the constraint for α in [0,P(y=y*)). Equation (3) fixes a single user-chosen α; if P(y=y*)<α, omitting y* does not violate the coverage constraint. Thus the proof has a quantifier shift. Concretely, take a DAG with root, internal node AB (parent of leaves A,B), and leaf C, with P(A)=0.97, P(B)=0.02, P(C)=0.01, α=0.02, β=0.1. The set {AB} covers A and B, has coverage 0.99≥0.98, and cost |N|+β|leaf-cov| = 1+2β = 1.2. NOL-covers are {root} (cost 1+3β=1.3), {AB,C} (cost 2+3β=2.3), and {A,B,C} (cost 3+3β). So the unique minimizer is not a NOL-cover, and restricting the search to NOL-covers does not preserve optimality for the stated fixed-α problem. Additionally, Theorem 1 is not self-consistent: C(xt) is defined using the unknown test label y_t, and the proof's equivalence s_t≤qhat ⇔ v'_t∈C(xt) has the threshold direction reversed relative to the definition in Eq. (2). These are internal correctness issues, not disagreements with the field.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Hierarchical Conformal Classification (HCC), an extension of conformal prediction for classification with a label hierarchy modeled as a DAG. HCC frames the construction of prediction sets—subsets of hierarchy nodes—as the constrained optimization problem in Equation (3), which minimizes the number of nodes plus a specificity penalty on covered leaves, subject to a leaf-coverage probability guarantee. To make search tractable, the authors restrict attention to non-overlapping leaf covers (NOL-covers), claiming that Propositions 1 and 2 show this restriction preserves optimality, and that Theorem 1 gives a finite-sample coverage guarantee for the proposed conformity score in Equation (4). The paper also presents three new benchmarks (text, image, audio) with taxonomies, experiments comparing HCC to standard conformal prediction and an LCA baseline, ablations, and a user study indicating a preference for HCC's outputs.","tokens_in":16016,"tokens_out":5335,"duration_ms":55220,"significance":"If the theoretical claims were valid, HCC would be a practically relevant contribution: it provides a principled way to produce semantically coherent, compact prediction sets in hierarchical label spaces while maintaining the finite-sample guarantees of conformal prediction. The paper also contributes new benchmark datasets with taxonomies and makes code available, which are useful assets. However, the central theoretical foundation is unsound: the claimed optimality of the NOL-cover restriction is not established, and the stated coverage theorem is internally inconsistent. The empirical results are suggestive but cannot, by themselves, compensate for the failure of the main theoretical claims.","major_comments":[{"comment":"Proposition 1 is false for the fixed-alpha optimization problem in Equation (3). The proof shows that omitting a leaf y* violates the coverage constraint for every alpha in [0, P(y=y*)), but Equation (3) fixes a single user-chosen alpha. If P(y=y*) < alpha, a set omitting y* can still satisfy the constraint. For example, let a DAG have a root, an internal node AB with leaves A and B, and a leaf C, with P(A)=0.97, P(B)=0.02, P(C)=0.01, alpha=0.02, beta=0.1. The set {AB} has coverage 0.99 >= 0.98 and cost 1+2*0.1=1.2, while the NOL-covers {root}, {AB,C}, and {A,B,C} have costs 1.3, 2.3, and 3.3, respectively. Thus the unique minimizer of Equation (3) is not a NOL-cover, and the claimed restriction can discard the true optimum.","section":"Search-Space Pruning, Proposition 1"},{"comment":"The proof of Proposition 2 is invalid. It constructs a set S from a feasible solution N* by removing ancestor or descendant nodes and then claims S is feasible because its leaf-cover cardinality is no larger than that of N*. Feasibility in Equation (3) is a probability constraint, P(yt in leaf-cov(S)) >= 1-alpha, not a cardinality condition. Removing a node that is the only cover for some high-probability leaves can reduce the covered probability below the constraint. The proof never shows that the removed nodes are redundant in terms of probability mass, so the conclusion that an optimal solution can always be found among NOL-covers is unsupported.","section":"Search-Space Pruning, Proposition 2"},{"comment":"Theorem 1 is not self-consistent. The prediction set is defined as C(xt) := {v in V | s(xt, yt, S) <= qhat}, but the conformity score s in Equation (4) depends on the unobserved test label yt through the indicator vector Y'_t, so C(xt) is not computable at inference time. Furthermore, the proof asserts the equivalence st <= qhat <=> ghat(xt)_v'_t >= 1 - qhat, which is incompatible with the stated definition of C(xt) (which uses <= qhat) and also conflicts with the threshold direction in Equation (2). These are internal mathematical errors, not alternative conventions, so the claimed hierarchical coverage guarantee is not established.","section":"Theorem 1"},{"comment":"The 'limited search' fallback described in Appendix C restricts the search to one NOL-cover per depth level for large taxonomies, with no statement of optimality or even a bounded approximation ratio. Since the main text claims that the NOL-cover restriction 'upholds optimality,' this further heuristic introduces an additional gap between the stated optimization problem and the actual algorithm that the paper does not discuss or analyze.","section":"Appendix C"}],"minor_comments":[{"comment":"There is an inconsistency in table numbering: the main text repeatedly refers to 'Table 3' for the test results, but the table appears as 'Table 2' in the manuscript; Figure 5 also references 'Table 3'.","section":"Results section"},{"comment":"The proof states that P(y=y*) > 0 'must hold unless y* is excluded from Y altogether,' which is not justified; a leaf in the taxonomy can have zero probability under the data distribution.","section":"Appendix A, Proposition 1 proof"},{"comment":"The theorem says C(xt) ranges over all v in V, while the conformity score s is defined for nodes in the given NOL-cover S; the statement should clarify that the prediction set is a subset of S.","section":"Theorem 1 statement"},{"comment":"The abstract claims the reduced candidate set 'suffices to ensure coverage while upholding optimality,' which is not supported by the current theory given the errors in Propositions 1 and 2; the claim should be qualified or revised.","section":"Abstract"}],"recommendation":"reject","confidential_remarks":"The paper presents an appealing framework and useful benchmarks, but the theoretical core is seriously flawed. Propositions 1 and 2 are the basis for the main algorithmic reduction, and both are false or unproven as stated; Theorem 1 does not provide a valid coverage guarantee. These are not local presentation issues but fundamental correctness problems that would require reworking the formulation or substantially weakening the claims. In my view, the manuscript cannot be accepted in its current form, and even a major revision would need to replace the theoretical foundation rather than patch a few equations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — worth a look, but keep your guard up. The paper delivers a genuinely nice package: a DAG-aware conformal framework, a sensible multi-label conformity score, released benchmarks across text/image/audio, and a user study (however flawed) suggesting people like hierarchical sets. The empirical coverage numbers are fine, and the idea of trading nominal set size against leaf coverage is a useful one for practical deployment. Credit where due: the benchmark release and the algorithmic pipeline are real contributions.\n\nThe soft spot is central. The entire search-space reduction rests on Proposition 1, which claims any feasible set must cover all leaves. The proof establishes only that a set omitting a leaf y* fails the coverage constraint for alpha < P(y = y*). But Equation (3) fixes a single user-chosen alpha. If the omitted leaf has prior probability below alpha, the set is still feasible. The stress-test example is concrete: {AB} in a small DAG beats every NOL-cover for alpha=0.02, beta=0.1. So restricting to NOL-covers can discard the true optimum, and the paper's headline guarantee of optimality is not proven. Theorem 1 has independent issues: the definition of C(x_t) uses the unknown test label y_t, and the proof's threshold direction is reversed relative to Equation (2). These are internal inconsistencies, not just missing details. Appendix B's recurrence for NOL-cover counts also looks wrong for perfect binary trees — C(d) should be the number of antichain leaf covers, which grows much faster than ~2^{d-1}.\n\nThe ablations partly compensate: the method still achieves coverage and often lowers cost in practice, so there is a working heuristic here. But the paper claims a guarantee it does not establish. Missing comparison with Mortier et al. (2025) in the main table weakens the empirical claims further, and the user study's annotators being the authors is a red flag, though not decisive.\n\nBottom line: this deserves a serious referee — the topic is timely, the benchmarks are reusable, and the flaws are concrete enough to be fixable. But in its current form it should not be accepted. I would send it back for a major revision with the theory either corrected or honestly downgraded to a heuristic claim.\n\nFor your reading group: maybe. The healthy skepticism about conformal-theory claims is a good lesson.","headline":"A useful practical setup and benchmarks, but the central optimality claim does not hold as stated: Proposition 1's proof quantifies over all alpha while the objective fixes one, so the NOL-cover pruning is unsupported.","tokens_in":16625,"tokens_out":1132,"would_cite":false,"duration_ms":14026,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Optimal hierarchical conformal prediction can be restricted to non-overlapping leaf covers without sacrificing finite-sample coverage.","keywords":["conformal prediction","hierarchical classification","prediction sets","coverage guarantee","class taxonomy","directed acyclic graph","uncertainty quantification"],"falsifier":"In a two-leaf hierarchy where one leaf has prior probability $0.01$, set $\\alpha=0.05$ and a base classifier that always ranks the likely leaf first; if the feasible singleton set with the likely leaf has lower cost than every NOL-cover, then the claimed reduction does not solve the optimization as stated.","tokens_in":15468,"feed_emoji":"🌳","tokens_out":12342,"duration_ms":112600,"temperature":0.7,"pith_summary":"Standard conformal prediction returns a flat list of class labels. HCC instead builds prediction sets from nodes at any level of a known class hierarchy, so a set can say \"cat\" rather than enumerate fine-grained breeds, while still guaranteeing that the true label is covered with probability at least $1-\\alpha$. The paper shows that the combinatorial search over hierarchy subsets can be restricted to non-overlapping leaf covers without losing optimality or coverage, and proves a finite-sample hierarchical coverage guarantee for the resulting predictors. On three released benchmarks spanning text, image, and audio, the resulting sets are more compact, and annotators prefer them over flat conformal sets in a user study. The contribution is that domain structure is not extra weight on top of conformal prediction but the mechanism that makes its prediction sets understandable.","feed_headline":"Hierarchical prediction sets stay small without losing coverage","feed_subtitle":"Searching only non-overlapping leaf covers keeps conformal guarantees while returning human-readable categories.","key_machinery":"The central object is the non-overlapping leaf cover (NOL-cover): a subset of the hierarchy's nodes that covers every leaf through descendants and contains no two nodes on the same root-to-leaf path. Two structural lemmas carry the argument: any feasible prediction set must cover all leaves, and any optimal set can be made ancestor-independent without increasing the objective, so the search over all $2^{|V|}$ subsets collapses to the NOL-covers. The accompanying machinery is score propagation—each internal node's score is the sum of its descendant leaves' scores, and the multi-label conformity score for a cover is the largest propagated score among the cover's ground-truth nodes—followed by the usual split-conformal quantile threshold $\\lceil(n_c+1)(1-\\alpha)\\rceil/n_c$. In a perfect binary tree this reduces the search from $2^{2^d}$ candidate subsets to roughly $2^{d-1}$.","core_discovery":"The paper's central claim is that the constrained optimization defining hierarchical conformal classification—minimize $|N|+\\beta\\,|\\bigcup_{v\\in N}\\mathrm{leaf-cov}_T(\\{v\\})|$ subject to $\\Pr(y_t\\in\\mathrm{leaf-cov}_T(N))\\ge 1-\\alpha$—can be solved by searching only over non-overlapping leaf covers: subsets of hierarchy nodes whose descendant leaves cover all leaves and that contain no ancestor–descendant pair. HCC calibrates one split-conformal predictor for each NOL-cover after propagating leaf scores upward as sums and marking all ancestors of the true leaf as ground truth. For DAGs, where one instance can have several true nodes inside a cover, the conformity score is the largest propagated score among the cover's ground-truth nodes, reducing to the usual single-label score when the cover is the flat leaf set. The paper proves that this construction satisfies $\\Pr(y_t\\in\\mathrm{leaf-cov}_T(C(x_t)))\\ge 1-\\alpha$ for every $\\alpha\\in[0,1)$, and that feasible optimal solutions to the optimization need only be sought among NOL-covers.","pith_inferences":["If the fixed-alpha reading of the optimization is taken literally, allowing NOL-covers to omit leaves with prior mass below $\\alpha$ could produce lower-cost feasible sets; this is a direct testable relaxation of the paper's pruning step.","Because Bonferroni correction is conservative, ordering NOL-covers by expected cost and applying sequential multiple-testing corrections should shrink prediction sets further without touching the coverage proof.","The same propagated-score conformity mechanism applies to hierarchical multi-label prediction and to retrieval tasks where ground truth is a set of ancestors, not just to single-label classification.","The user-study preference suggests $\\beta$ should be learned per user or per task; the paper's median-descendant-count heuristic is a reasonable default but not necessarily the one annotators would choose."],"forward_implications":["Prediction sets can mix specific leaf labels with broader category labels, so a single set can be compact where the classifier is confident and abstract where it is not.","The coverage guarantee extends to DAG taxonomies with multiple inheritance, because the max-over-true-nodes conformity score handles several simultaneously true nodes per instance.","The $\\beta$ parameter gives continuous control: raising it trades nominal set size against the number of covered leaves, letting users choose how abstract predictions may be.","Calibration cost is bounded by the number of NOL-covers rather than all $2^{|V|}$ subsets, and those covers are computed once per taxonomy.","Dynamic pruning and Bonferroni correction during inference preserve finite-sample coverage while limiting the multiple-comparison penalty."],"supporting_citations":[{"why":"Supplies the split-conformal quantile calibration and exchangeability argument that Theorem 1 relies on.","marker":"Vovk, Gammerman, and Shafer 2005"},{"why":"Provides the least-ambiguous set-valued classifier score that the hierarchical conformity score in Equation (4) generalizes.","marker":"Sadinle, Lei, and Wasserman 2019"},{"why":"Supplies the learn-then-test calibration-and-search framing that HCC adopts for constrained search over prediction sets.","marker":"Angelopoulos et al. 2025"},{"why":"Defines conformal risk control, the multi-label baseline used to ablate the hierarchical conformity score.","marker":"Angelopoulos et al. 2024"},{"why":"Gives conformal structured prediction, the closest prior coverage-guaranteed method compared in the supplementary experiments.","marker":"Zhang, Li, and Bastani 2025"}],"fun_headline_variants":["Hierarchical conformal prediction shrinks sets without losing coverage","Non-overlapping leaf covers make conformal sets human-readable","Hierarchy-aware conformal sets: smaller, preferred, still guarantee coverage","Proof: NOL covers alone solve hierarchical conformal optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The pruning step assumes that any set missing a leaf is infeasible for the coverage constraint, because one can always pick an error level smaller than that leaf's probability, even though the optimization is actually run at one fixed error level where such rare leaves could be safely omitted.","fun_headline_variants_meta":{"raw":{"variants":["Hierarchical conformal prediction shrinks sets without losing coverage","Non-overlapping leaf covers make conformal sets human-readable","Hierarchy-aware conformal sets: smaller, preferred, still guarantee coverage","Proof: NOL covers alone solve hierarchical conformal optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000809,"raw_usage":{"total_tokens":3552,"prompt_tokens":952,"completion_tokens":2600,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":2530}},"tokens_in":568,"tokens_out":2600,"duration_ms":21212,"temperature":1.0,"reasoning_tokens":2530,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:16:18.266414+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"In a two-leaf hierarchy where one leaf has prior probability $0.01$, set $\\alpha=0.05$ and a base classifier that always ranks the likely leaf first; if the feasible singleton set with the likely leaf has lower cost than every NOL-cover, then the claimed reduction does not solve the optimization as stated.","supporting_citations":[{"cited_title":"N.; Bates, S.; Cand \\`e s, E","cited_arxiv_id":null,"evidence_quote":"Supplies the learn-then-test calibration-and-search framing that HCC adopts for constrained search over prediction sets."},{"cited_title":"N.; Bates, S.; Fisch, A.; Lei, L.; and Schuster, T","cited_arxiv_id":null,"evidence_quote":"Defines conformal risk control, the multi-label baseline used to ablate the hierarchical conformity score."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives conformal structured prediction, the closest prior coverage-guaranteed method compared in the supplementary experiments."}],"review_version":2}