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 & tables
Figure 1: Hierarchical prediction example from ImageNet, with standard CP output in red and HCC in blue, both covering ground truth Black Widow . HCC yields a more compact, semantically meaningful set and was unanimously preferred.
Figure 2: HCC training: (a) for an input DAG with nodes V , (b) a set {S⊂V} of subsets that each cover all leaf nodes (the leaf covers ) is derived. (c) Classifier scores f^(xi) and labels yi in a calibration set Dc are propagated up the hierarchy, and (d) used to calibrate a set of conformal predictors, one for each leaf cover.
Figure 3: HCC inference: (a) the prediction scores for a test input xt , and for a desired error level α , (b) classifier scores are propagated, and (c) used to infer prediction sets with the predictors h obtained during training. Finally, (d) the prediction set that minimizes the cost in ( 1 ) is selected.
Figure 4: Taxonomy for a running example.
β
1−α
method
coverage ↑
costs ↓
PS size ↓
covered leaves ↓
dbp
.19
.9997
Standard CP
.9998
± .02
3.18
± 2.62
2.67
± 2.20
2.67
± 2.20
LCA
.9998
± .02
2.20
± 1.13
1.00
± .00
6.32
± 5.94
CSP
.9938
± .08
1.20
± .15
1.01
± .09
1.02
± .50
HCC (ours)
.9999
± .01
2.01
± .94
1.23
± .45
4.12
± 4.47
w/o dynamic pruning
.9999
± .01
2.15
± 1.03
1.34
± .62
4.30
± 4.61
w/o correction
.9997
± .02
1.88
± .85
1.22
± .43
3.44
± 3.69
Table 1: Test set results (mean ± SD). Bold indicates meeting coverage guarantee for ‘coverage’ column, and, for other columns, the best out of all methods meeting the coverage guarantee.
Figure 5: Efficiency expressed in the set sizes and number of covered leaves for varying β . Dotted vertical lines indicate β values in Table 1 .
dbp
img
gtz
n
70,000
50,000
1,000
# labels
14
1000
10
modality
text
image
audio
classifier
BERT
ResNet-152
XGBoost
accuracy
.99
.79
.63
# nodes
25
1860
15
Table 2: Overview of data sets.
Figure 6: Additional results for various desired coverage ratios α .HCC maintains coverage and significantly reduces the nominal prediction set size at higher 1−α , at a slight increase of # covered leaves. Results for dbp overlap. Error bars indicate SD.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: Example output and user preferences for random samples from img with unanimous user preferences.
Figure 8: Number of nodes per level: dbp (left) and wordnet-subset (center), gtz (right). "yes" denotes the number of leaves, and "no" the number of internal nodes per level.
Figure 9: dbp taxonomy. Leaves are denoted in green and intermediate nodes in blue.
Figure 10: gtz taxonomy.
β
1−α
method
coverage ↑
costs ↓
PS size ↓
covered leaves ↓
dbp
.19
.9997
Standard CP
.9998
± .02
3.18
± 2.62
2.67
± 2.20
2.67
± 2.20
LCA
.9998
± .02
2.2
± 1.13
1
± .00
6.32
± 5.94
CSP M=4
.9938
± .08
1.2
± .15
1.01
± .09
1.02
± .50
CSP M=8
.9938
± .08
1.2
± .15
1.01
± .09
1.02
± .50
HCC (ours)
.9999
± .01
2.01
± .94
1.23
± .45
4.12
± 4.47
img
.04
.98
Standard CP
.9807
± .14
11.49
± 20.49
11.04
± 19.70
11.04
± 19.70
Appendix
Table 3: Additional test set results for CSP.
dbp
img
gtz
Search space construction (NOL-covers)
0.28
0.54
0.02
Score propagation
0.23
15.88
<0.01
Calibration
9.00
19.36
0.03
Cache lookup (key and load)
5.83
8.11
0.03
Prediction set selection
8.53
49.95
0.01
HCC total, cached inference
23.87
93.84
0.09
Appendix
Table 4: Runtime in seconds of HCC per stage, with inference served from the disk cache, for the main results in Table 1 . Totals exclude data loading. For reference, we list the HCC total without cache, i.e. including per-instance inference over all candidate covers, and the total runtimes of Standard CP and CSP ( M=8 ). All runs are single-process on the hardware described in Appendix H .
Metric
Preference
HCC
Standard CP
No Preference
dbp
Annotation distribution (#)
523
401
74
Annotation distribution (%)
52.4
40.2
7.4
Majority distribution (#)
126
90
12
Majority distribution (%)
50.4
36.0
4.8
img
Annotation distribution (#)
577
239
180
Appendix
Table 5: Annotation and majority distribution across the preferences HCC (ours), Standard CP and No Preference .
Conformal prediction provides distribution-free coverage guarantees, but in many-class classification it may still under-cover specific classes or subpopulations, preventing safe deployment in high-stakes applications. We propose Cluster Frequency Conformal Prediction (CFCP), a plug-in framework that adapts conformal prediction to local structure in a learned representation space. CFCP clusters learned embeddings, estimates cluster-level label-frequency distributions from calibration data, and for each test point constructs a sample-specific probability vector by softly mixing nearby cluster distributions regularized with global-prior and reliability-aware shrinkage. This vector is then conformalized using standard set constructors. In the disjoint-split regime, CFCP inherits standard finite-sample marginal validity. Under additional assumptions, CFCP further admits a local-validity interpretation. Since representation clusters aggregate locally similar samples, their empirical class frequencies provide a stable estimate of local label ambiguity. Across image and text benchmarks, CFCP achieves the best class coverage in 15/16 dataset/score-family comparisons and a competitive prediction set size efficiency, with several settings substantially more efficient. Overall, our results show that cluster-frequency information provides an effective localized signal for improving classwise reliability in many-class conformal prediction.
Tomer Lavi, Bracha Shapira, Nadav Rappoport
Institute of Applied AI Research (AAIR) Faculty of Computer and Information Science Ben-Gurion University of the Negev, Beer-Sheva 84105, ISRAEL · Institute for Interdisciplinary Computational Science (ICS) Faculty of Computer and Information Science Ben-Gurion University of the Negev, Beer-Sheva 84105, ISRAEL
The merit of Conformal Prediction (CP), as a distribution-free framework for uncertainty quantification, depends on generating prediction sets that are efficient, reflected in small average set sizes, while adaptive, meaning they signal uncertainty by varying in size according to input difficulty. A central limitation for deep conformal classifiers is that the nonconformity scores are derived from softmax outputs, which can be unreliable indicators of how certain the model truly is about a given input, sometimes leading to overconfident misclassifications or undue hesitation. In this work, we argue that this unreliability can be inherited by the prediction sets generated by CP, limiting their capacity for adaptiveness. We propose a new approach that leverages information from the pre-softmax logit space, using the Helmholtz Free Energy as a measure of model uncertainty and sample difficulty. By reweighting nonconformity scores with a monotonic transformation of the energy score of each sample, we improve their sensitivity to input difficulty. Our experiments with four state-of-the-art score functions on multiple datasets and deep architectures show that this energy-based enhancement improves the adaptiveness of the prediction sets, leading to a notable increase in both efficiency and adaptiveness compared to baseline nonconformity scores, without introducing any post-hoc complexity.
Navid Akhavan Attar, Hesam Asadollahzadeh, Ling Luo +1
School of Computing and Information Systems, Faculty of Engineering and IT The University of Melbourne, Victoria, Australia
An open question in Imprecise Probabilistic Machine Learning is how to empirically derive a credal region (i.e., a closed and convex family of probabilities on the output space) from the available data, without any prior knowledge or assumption. In classification problems, credal regions are a tool that is able to provide provable guarantees under realistic assumptions by characterizing the uncertainty about the distribution of the labels. Building on previous work, we show that credal regions can be directly constructed using conformal methods. This allows us to provide a novel extension of classical conformal prediction to problems with ambiguous ground truth, that is, when the exact labels for given inputs are not exactly known. The resulting construction enjoys desirable practical and theoretical properties: (i) conformal coverage guarantees, (ii) smaller prediction sets (compared to classical conformal prediction regions) and (iii) disentanglement of uncertainty sources (epistemic, aleatoric). We empirically verify our findings on both synthetic and real datasets.
Michele Caprio, David Stutz, Shuo Li +1
Department of Computer Science University of Manchester · DeepMind · Department of Computer and Information Science University of Pennsylvania +1