Hierarchical Conformal Classification
Floris den Hengst, Inès Blin, Majid Mohammadi, Syed Ihtesham Hussain Shah, Taraneh Younesian · 2025
Read Hierarchical Conformal Classification by Floris den Hengst, Inès Blin, Majid Mohammadi, Syed Ihtesham Hussain Shah, Taraneh Younesian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13288.txt.
Introduction
Floris den Hengst and co-authors published a 2025 paper on making machine learning predictions that come with honest uncertainty. A method called conformal prediction gives, instead of one label, a set of labels that is very likely to contain the right one. The standard version treats all labels as flat and unrelated. In many fields, though, labels sit in a tree: a sound is a dog, an animal, a living thing.
The authors extend the method to use that tree. Their prediction sets can mix levels of the tree, naming a broad group when the model is unsure and a fine label when it is sure. They prove the sets still keep the promised coverage. They also show that only a small pool of candidate sets needs checking. Tests on audio, image, and text data favored the new sets. Human raters in a user study preferred them over flat sets.
Catalog record
| CREATOR | Floris den Hengst, Inès Blin, Majid Mohammadi, Syed Ihtesham Hussain Shah, Taraneh Younesian |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-13288
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hierarchical Conformal Classification Floris den Hengst, Inès Blin, Majid Mohammadi, Syed Ihtesham Hussain Shah, Taraneh Younesian 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. Introduction Conformal prediction (CP) is a powerful tool for estimating and representing the uncertainty of predictive models, which is crucial in high-stakes application domains ( Vovk, Gammerman, and Shafer 2005 ; Angelopoulos, Bates et al. 2023 ) . CP provides statistical guarantees for any model that outputs prediction scores in a finite-sample regime. For a given input, it produces a set of predictions that contain the ground truth at a user-specified confidence level. This property of CP is known as its coverage guarantee. Motivated by the adoption and success of CP, approaches have been proposed that display additional desiderata on top of its key coverage property. Examples include approaches that provide a coverage guarantee conditional to the input ( Angelopoulos et al. 2021 ) , those that incorporate different misclassification costs for different classes using a risk control framework ( Angelopoulos et al. 2024 ) , and methods that produce structured prediction sets ( Wieslander et al. 2020 ; Zhang, Li, and Bastani 2025 ) . However, relatively little attention has been paid to incorporating prior domain knowledge into the process of generating prediction sets with coverage guarantees. For classification, the semantics of a particular domain are often captured in a taxonomy or hierarchical organization among class labels. The directed acyclic graph (DAG) is the dominant modeling paradigm for doing so. Examples include the organization of diseases in diagnosis ( Zesch and Gurevych 2007 ) , fraud types in fraud detection ( Bennett 2013 ) , and article types in text classification ( Zesch and Gurevych 2007 ) . Another well-known example is ImageNet ( Russakovsky et al. 2015 ) , where class labels are derived from the WordNet lexical database ( Miller 1995 ) . Figure 1 exemplifies how class hierarchies are crucial to creating prediction sets that are more compact, better aligned with how end users understand the domain, and thereby more useful. Figure 1: Input with standard CP output (left), hierarchy subset with compact hierarchy-informed output (right). While recent studies have incorporated hierarchies in labels into the prediction sets ( Angelopoulos et al. 2024 ; Zhang, Li, and Bastani 2025 ) , they fail to balance between the compactness of the prediction sets and their specificity. We propose Hierarchical Conformal Classification (HCC) , an extension of conformal prediction that incorporates class hierarchies into the structure of prediction sets. Rather than treating labels as flat and unstructured, HCC leverages a given class taxonomy modeled as a DAG to construct sets containing nodes from different levels of the taxonomy—including both fine-grained leaf classes and more general ancestor nodes. HCC formulates the construction of such sets as a constrained optimization problem: among all subsets of the hierarchy that guarantee the required coverage, it selects one that minimizes the size of the prediction set while maximizing its specificity. Our solution is inspired by the learn-then-test approach by Angelopoulos et al. 2025 , and combines learning with search. Our search step is efficient and scalable because it is conducted over a carefully constructed subspace of candidate solutions. We show that, despite the combinatorial nature of search over the whole hierarchy, it suffices to search within this much smaller, well-structured subset of candidates. Crucially, HCC preserves the finite-sample coverage guarantees of standard CP by ensuring that the true label is always included in the leaf-level coverage of the returned set. By allowing for the replacement of many similar leaf classes with a single general parent, HCC provides more compact and usable predictions that are better aligned with how users understand the label space. The contributions of this paper can be summarized as: • We formalize Hierarchical Conformal Classification (HCC) as an extension of conformal prediction that accounts for the hierarchy among class labels, formalizing the prediction set construction as a constrained optimization problem with labels in a DAG. • We design efficient calibration and inference algorithms for HCC, including a search-based procedure that exploits the structure of the hierarchy to solve the optimization problem with guaranteed coverage. • We present and release 1 1 1 https://github.com/florisdenhengst/hierarchical-conformal-classification three use cases and benchmarks that span multiple data modalities - audio, image, and text - where class hierarchies are available, and we demonstrate the effectiveness of HCC through both quantitative evaluation and a user study. HCC thereby bridges structured prediction and uncertainty quantification, with broad applicability across domains, offering a foundation for more reliable and user-aligned classification systems. Related Work A handful of works have recently explored prediction sets in hierarchical label spaces, but HCC differs fundamentally in both goal and methodology. Prior methods, such as Mortier et al. 2022 ; Mortier et al. 2025 , aim to capture regions of high probability mass and are limited to trees, rather than our more general focus on coverage guarantees for DAGs. Angelopoulos et al. 2024 focuses on bounding the hierarchical distance rather than achieving leaf coverage, and their approach restricts the inference strictly to ancestor nodes of the most likely label. In contrast, our approach can flexibly include both internal and leaf nodes based on a user-specified trade-off between prediction set size and specificity. Zhang, Li, and Bastani 2025 adopt a learn-then-test framework to achieve a similar goal to ours, and provides coverage guarantees, but their method requires a user-specified limit on the nominal prediction set size and relies on an integer programming formulation that may not scale well with the taxonomy size. In contrast, our approach allows for explicit balancing of compactness with specificity and introduces a structured and substantially reduced search during calibration, which is further pruned of spurious solutions during inference in a scalable way. Wieslander et al. 2020 combine deep learning with conformal prediction for the classification of subregions of tissues. They assess region-specific drug response by employing hierarchical identification of tissue regions and measuring confidence in subregion detection. However, this approach is specific to this problem domain and does not use an existing class hierarchy. Background Notation. We use calligraphic letters (e.g. \mathcal{X},\mathcal{F} ) to denote sets, capital letters (e.g., X,Y )