REVIEW 4 major objections 4 minor 2 cited by
Hierarchical Conformal Classification
T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Optimal hierarchical conformal prediction can be restricted to non-overlapping leaf covers without sacrificing finite-sample coverage.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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}$.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Search-Space Pruning, Proposition 1] 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.
- [Search-Space Pruning, Proposition 2] 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.
- [Theorem 1] 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.
- [Appendix C] 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.
minor comments (4)
- [Results section] 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'.
- [Appendix A, Proposition 1 proof] 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.
- [Theorem 1 statement] 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.
- [Abstract] 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.
Circularity Check
No circularity: the coverage argument is a standard exchangeability argument, and the NOL-cover pruning claims are independent structural arguments rather than fitted inputs or self-citation chains.
full rationale
The derivation chain in HCC does not reduce to its own inputs. The optimization in Eq. (3) is a stated objective over node subsets; alpha is a user-chosen error level and beta is set from the taxonomy via Eq. (6) (median leaf-cover sizes), not from the calibration/test labels or from the coverage guarantee. The calibration procedure follows split conformal prediction, with the conformity score in Eq. (4) presented as an explicit generalization of Sadinle et al.; the coverage proof relies on exchangeability and rank uniformity, the standard CP argument, and does not assume the conclusion it is proving. The restriction to NOL-covers is justified by Propositions 1 and 2 in Appendix A; these are structural claims about feasibility and cost, and even if their proofs contain quantifier or direction errors (a correctness concern, not a circularity), they are not cases where a fitted parameter is renamed as a prediction or where a result is imported from the authors' prior work. The only appearance of the authors' own prior work (den Hengst et al. 2024) is a suggestion for a future, larger user study, and it is not load-bearing for the central claim. The empirical section compares against standard CP, LCA, and structured CP on external benchmarks, so the method's main assertions are not forced by construction.
Assumptions & free parameters
free parameters (2)
- beta =
0.19 (dbp), 0.04 (img), 0.25 (gtz)
- alpha =
1-alpha = .9997, .98, .9
assumptions (4)
- domain assumption The class hierarchy is a DAG with a unique root, and the classifier's labels are exactly the leaves (Definitions 1-2).
- standard math Exchangeability of calibration and test data (split conformal prediction).
- ad hoc to paper Any feasible solution to Eq. (3) must cover all leaves, i.e., Proposition 1.
- ad hoc to paper For large taxonomies, restricting to one NOL-cover per depth level preserves near-optimality (Appendix C, 'limited search').
Cite this review
Pith. "Pith review of Hierarchical Conformal Classification." pith.science (2026). https://pith.science/paper/JKVOGWBO
@misc{pith2026250813288,
author = {Pith},
title = {Pith review of: Hierarchical Conformal Classification},
year = {2026},
howpublished = {\url{https://pith.science/paper/JKVOGWBO}},
note = {Machine review of arXiv:2508.13288}
}
read the original abstract
Conformal prediction (CP) is a powerful framework for quantifying uncertainty in machine learning models, offering reliable predictions with finite-sample coverage guarantees. When applied to classification, CP produces a prediction set of possible labels that is guaranteed to contain the true label with high probability, regardless of the underlying classifier. However, standard CP treats classes as flat and unstructured, ignoring domain knowledge such as semantic relationships or hierarchical structure among class labels. This paper presents hierarchical conformal classification (HCC), an extension of CP that incorporates class hierarchies into both the structure and semantics of prediction sets. We formulate HCC as a constrained optimization problem whose solutions yield prediction sets composed of nodes at different levels of the hierarchy, while maintaining coverage guarantees. To address the combinatorial nature of the problem, we formally show that a much smaller, well-structured subset of candidate solutions suffices to ensure coverage while upholding optimality. An empirical evaluation on three new benchmarks consisting of audio, image, and text data highlights the advantages of our approach, and a user study shows that annotators significantly prefer hierarchical over flat prediction sets.
Figures
Figures from the paper (6 more)
Forward citations
Cited by 2 Pith papers
-
Enhancing Conformal Prediction via Class Similarity
Adding a class-similarity penalty to conformal scores can shrink prediction sets and reduce the number of semantic groups they span.
-
When Is a Conformal Guarantee Fair? Auditing Silent Subgroup Under-Coverage in Alzheimer's Disease Longitudinal Prediction
Marginal conformal bands under-cover high-risk Alzheimer's subgroups even at nominal average coverage, and rarity and tail-heaviness explain and repair the deficit.
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Angelopoulos, A. N.; Bates, S.; Cand \`e s, E. J.; Jordan, M. I.; and Lei, L. 2025. Learn then test: Calibrating predictive algorithms to achieve risk control. The Annals of Applied Statistics, 19(2): 1641--1662
work page 2025
-
[4]
N.; Bates, S.; Fisch, A.; Lei, L.; and Schuster, T
Angelopoulos, A. N.; Bates, S.; Fisch, A.; Lei, L.; and Schuster, T. 2024. Conformal Risk Control. In The Twelfth International Conference on Learning Representations
work page 2024
-
[5]
N.; Bates, S.; Jordan, M.; and Malik, J
Angelopoulos, A. N.; Bates, S.; Jordan, M.; and Malik, J. 2021. Uncertainty Sets for Image Classifiers using Conformal Prediction. In The Ninth International Conference on Learning Representations
work page 2021
-
[6]
Angelopoulos, A. N.; Bates, S.; et al. 2023. Conformal prediction: A gentle introduction. Foundations and Trends in Machine Learning , 16(4): 494--591
work page 2023
-
[7]
Bennett, M. 2013. The financial industry business ontology: Best practice for big data. Journal of Banking Regulation, 14(3): 255--268
work page 2013
-
[8]
Cauchois, M.; Gupta, S.; and Duchi, J. C. 2021. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of machine learning research, 22(81): 1--42
2021
Show all 31 references
-
[9]
den Hengst, F.; Wolter, R.; Altmeyer, P.; and Kaygan, A. 2024. Conformal Intent Classification and Clarification for Fast and Accurate Intent Recognition. In Duh, K.; Gomez, H.; and Bethard, S., eds., Findings of the Association for Computational Linguistics: NAACL 2024, 2412-...
2024
-
[10]
Ding, T.; Angelopoulos, A.; Bates, S.; Jordan, M.; and Tibshirani, R. J. 2023. Class-conditional conformal prediction with many classes. Advances in neural information processing systems, 36: 64555--64576
2023
-
[11]
He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 770--778
2016
-
[12]
Holm, S. 1979. A simple sequentially rejective multiple test procedure. Scandinavian journal of statistics, 65--70
1979
-
[13]
Lambrou, A.; and Papadopoulos, H. 2016. Binary relevance multi-label conformal predictor. In Conformal and Probabilistic Prediction with Applications: 5th International Symposium, COPA 2016, Madrid, Spain, April 20-22, 2016, Proceedings 5, 90--104. Springer
2016
-
[14]
Maltoudoglou, L.; Paisios, A.; Lenc, L.; Mart \' i nek, J.; Kr \' a l, P.; and Papadopoulos, H. 2022. Well-calibrated confidence measures for multi-label text classification with a large number of labels . Pattern Recognition, 122: 108271
2022
-
[15]
N.; Jakob, M.; and Bizer, C
Mendes, P. N.; Jakob, M.; and Bizer, C. 2012. DBpedia: A multilingual cross-domain knowledge base. European Language Resources Association (ELRA)
2012
-
[16]
Miller, G. A. 1995. WordNet: a lexical database for English. Communications of the ACM, 38(11): 39--41
1995
-
[17]
Mortier, T.; H \"u llermeier, E.; Dembczy \'n ski, K.; and Waegeman, W. 2022. Set-valued prediction in hierarchical classification with constrained representation complexity. In Uncertainty in Artificial Intelligence, 1392--1401. PMLR
2022
-
[18]
Mortier, T.; Javanmardi, A.; Sale, Y.; H \"u llermeier, E.; and Waegeman, W. 2025. Conformal Prediction in Hierarchical Classification. arXiv preprint arXiv:2501.19038
2025 arXiv
-
[19]
Paisios, A.; Lenc, L.; Mart\' nek, J.; Kr\'al, P.; and Papadopoulos, H. 2019. A Deep Neural Network Conformal Predictor for Multi-label Text Classification. In Gammerman, A.; Vovk, V.; Luo, Z.; and Smirnov, E., eds., Proceedings of the Eighth Symposium on Conformal and Probabi...
2019
-
[20]
Papadopoulos, H. 2014. A cross-conformal predictor for multi-label classification. In Artificial Intelligence Applications and Innovations: AIAI 2014, 241--250. Springer
2014
-
[21]
Russakovsky, O.; Deng, J.; Su, H.; Krause, J.; Satheesh, S.; Ma, S.; Huang, Z.; Karpathy, A.; Khosla, A.; Bernstein, M.; et al. 2015. Imagenet large scale visual recognition challenge. International journal of computer vision, 115: 211--252
2015
-
[22]
Sadinle, M.; Lei, J.; and Wasserman, L. 2019. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525): 223--234
2019
-
[23]
Sedgwick, P. 2012. Multiple significance tests: the Bonferroni correction. Bmj, 344
2012
-
[24]
Sturm, B. L. 2012. An analysis of the GTZAN music genre dataset. In Proceedings of the second international ACM workshop on Music information retrieval with user-centered and multimodal strategies, 7--12
2012
-
[25]
Tyagi, C.; and Guo, W. 2023. Multi-label classification under uncertainty: a tree-based conformal prediction approach. In Conformal and Probabilistic Prediction with Applications, 488--512. PMLR
2023
-
[26]
Vovk, V.; Gammerman, A.; and Shafer, G. 2005. Algorithmic learning in a random world, volume 29. Springer
2005
-
[27]
Wang, H.; Liu, X.; Lv, B.; Yang, F.; and Hong, Y. 2014. Reliable multi-label learning via conformal predictor and random forest for syndrome differentiation of chronic fatigue in traditional Chinese medicine. PloS one, 9(6): e99565
2014
-
[28]
J.; Skogberg, G.; Jackson, S.; Frid \'e n, M.; Karlsson, J.; Spjuth, O.; and W \"a hlby, C
Wieslander, H.; Harrison, P. J.; Skogberg, G.; Jackson, S.; Frid \'e n, M.; Karlsson, J.; Spjuth, O.; and W \"a hlby, C. 2020. Deep learning with conformal prediction for hierarchical analysis of large-scale whole-slide tissue images. IEEE journal of biomedical and health info...
2020
-
[29]
Zesch, T.; and Gurevych, I. 2007. Analysis of the Wikipedia category graph for NLP applications. In Proceedings of the Second Workshop on TextGraphs: Graph-Based Algorithms for Natural Language Processing, 1--8
2007
-
[30]
Zhang, B.; Li, S.; and Bastani, O. 2025. Conformal Structured Prediction. In The Thirtheenth International Conference on Learning Representations
2025
-
[31]
Zhang, X.; Zhao, J.; and LeCun, Y. 2015. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28
2015
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.