Skip to content

Hierarchical Conformal Classification

Conference: NeurIPS 2026
arXiv: 2508.13288
Code: https://github.com/florisdenhengst/hierarchical-conformal-classification
Area: Optimization
Keywords: Conformal Prediction, Hierarchical Classification, Class Taxonomy, Constrained Optimization, Uncertainty Quantification

TL;DR

Hierarchical Conformal Classification (HCC) incorporates class taxonomies modeled as directed acyclic graphs (DAGs) into conformal prediction, formulating prediction set generation as a constrained optimization problem that prunes the search space via non-overlapping leaf covers to produce compact, user-aligned prediction sets with guaranteed finite-sample coverage.

Background & Motivation

Conformal prediction (CP) provides a distribution-free uncertainty quantification framework that endows arbitrary black-box classification models with rigorous statistical guarantees in finite-sample regimes. Specifically, for any test input, CP outputs a set of candidate labels guaranteed to contain the ground truth with a user-specified probability \(1-\alpha\). Despite this rigorous guarantee, standard conformal classification treats the label space as completely flat and unstructured, implicitly assuming every class label is mutually isolated. Under high model uncertainty, standard CP is prone to outputting large, flat sets of labels (such as enumerating dozens of fine-grained dog breeds), overwhelming practitioners and diminishing downstream decision utility.

In real-world domains—including disease diagnosis in medicine, fraud classification in finance, and object recognition in computer vision—classes are naturally organized into taxonomies structured as directed acyclic graphs (DAGs). When a model exhibits uncertainty among fine-grained sub-categories, presenting an informative ancestor concept (e.g., "hound" instead of a long list of specific terrier and hound breeds) is much more compact and faithful to human cognition. However, incorporating hierarchical priors into conformal prediction presents substantial challenges: existing works either restrict themselves to strict tree structures, sacrifice leaf-level coverage guarantees, bound hierarchical distances only along the most probable ancestor path, or rely on integer programming formulations that fail to scale to large taxonomies.

The core tension stems from the combinatorial explosion of candidate node subsets (\(2^{|\mathcal{V}|}\)) and the trade-off between prediction set compactness and semantic specificity. Core idea: formulate hierarchical prediction set construction as a constrained optimization problem balancing set cardinality and leaf coverage penalty, theoretically restrict the search space to non-overlapping leaf covers (NOL-covers), and employ bottom-up score propagation alongside dynamic LCA pruning to guarantee finite-sample coverage while generating compact, highly interpretable prediction sets.

Method

Overall Architecture

Hierarchical Conformal Classification (HCC) operates over a pre-defined class hierarchy DAG \(\mathcal{T} = (\mathcal{V}, \prec)\), aiming to construct an optimal predictor \(h_{\beta, \mathcal{V}}^*(\mathbf{x}_t, \alpha)\) that outputs a subset of nodes from arbitrary levels of the hierarchy. The pipeline integrates offline calibration on \(\mathcal{D}_c\) and online inference on \(\mathbf{x}_t\) across four coordinated stages: 1. Search Space Pruning: Identify valid non-overlapping leaf covers (NOL-covers) over the DAG, compressing the combinatorial search space from \(2^{|\mathcal{V}|}\) down to a structured, polynomial-size candidate family; 2. Bottom-Up Propagation of Scores and Labels: Aggregate base classifier probabilities from the leaves upward to obtain ancestor node prediction scores, and propagate ground-truth leaf labels to all their ancestors as hierarchical multi-labels; 3. Multi-Label Conformal Calibration: Construct and calibrate a conformal predictor for each candidate NOL-cover using a generalized multi-label conformity score function, computing empirical quantile cutoffs; 4. Dynamic Inference Pruning & Selection: Dynamically filter out redundant candidate predictors during test time using the Lowest Common Ancestor (LCA) of standard leaf predictions, apply multiple-testing correction, and select the optimal prediction set minimizing the weighted cost objective.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Test Input and Base Classifier Leaf Probabilities"] --> B["Bottom-Up Score and Multi-Label Propagation"]
    B --> C["Non-Overlapping Leaf Cover Pruning NOL-covers"]
    C --> D["Generalized Multi-Label Conformal Calibration"]
    D --> E["Dynamic LCA Pruning and Multiple-Testing Correction"]
    E --> F["Cost-Minimizing Hierarchical Prediction Set Output"]

Key Designs

1. Constrained Optimization Formulation: Balancing Compactness and Specificity To address the lack of semantic structure in flat prediction sets, HCC formalizes prediction set selection as a constrained optimization problem. For a candidate set \(\mathcal{N} \subseteq \mathcal{V}\), let \(\text{leaf-cov}_\mathcal{T}(\mathcal{N})\) denote the set of all leaf classes covered by \(\mathcal{N}\). The objective minimizes both set cardinality and the total number of implied leaves: $\(h_{\beta, \mathcal{V}}^*(\mathbf{x}_t, \alpha) = \arg\min_{\mathcal{N} \subseteq \mathcal{V}} |\mathcal{N}| + \beta \left|\bigcup_{v \in \mathcal{N}} \text{leaf-cov}_\mathcal{T}(\{v\})\right| \quad \text{subject to} \quad \mathbb{P}\left(y_t \in \text{leaf-cov}_\mathcal{T}(\mathcal{N})\right) \ge 1-\alpha\)$ The first term \(|\mathcal{N}|\) penalizes set size to encourage brevity and human readability. The second term penalizes the total covered leaf count, preventing the predictor from trivializing the task by always choosing high-level, overly abstract root categories. Hyperparameter \(\beta \in \mathbb{R}_+\) controls the trade-off: larger \(\beta\) encourages fine-grained leaf predictions, whereas smaller \(\beta\) allows the inclusion of higher-level parent nodes under elevated uncertainty. The default benchmark sets \(\beta\) adaptively as the inverse of the median number of leaves covered by non-leaf nodes: \(\beta := (\text{median}[\{|\text{leaf-cov}_\mathcal{T}(\{v\})| : v \notin \text{leaves}(\mathcal{T})\}])^{-1}\).

2. Candidate Space Pruning: Non-Overlapping Leaf Covers (NOL-cover) Directly searching over all \(2^{|\mathcal{V}|}\) possible subsets is computationally intractable. HCC establishes that search can be restricted without loss of optimality to non-overlapping leaf covers (NOL-covers). A subset \(\mathcal{S} \subseteq \mathcal{V}\) is defined as a valid NOL-cover if it satisfies two structural properties: - Leaf Coverage: \(\text{leaf-cov}_\mathcal{T}(\mathcal{S}) = \mathcal{Y}\) (every leaf in the taxonomy is covered by at least one node in \(\mathcal{S}\)); - Ancestral Independence: \(\forall u, v \in \mathcal{S}, u \ne v \implies \neg(u \prec\prec v) \land \neg(v \prec\prec u)\) (no two nodes in \(\mathcal{S}\) share an ancestor-descendant relationship).

The theoretical foundations guarantee this reduction: Proposition 1 proves that any feasible solution must cover all leaves, otherwise the empirical coverage constraint cannot be satisfied for all distributions; Proposition 2 proves that any solution containing ancestor-descendant pairs can be strictly improved or matched in cost by eliminating the descendant nodes. In a perfect binary tree of depth \(d\), this insight reduces the candidate space from \(2^{2^d}\) down to \(\sim 2^{d-1}\), turning combinatorial enumeration into an efficient recursive tree traversal.

3. Bottom-Up Propagation and Generalized Conformal Scoring To calibrate internal abstract nodes, HCC aggregates leaf-level classifier outputs \(\hat{f}(\mathbf{x})\) upward: for any node \(v \in \mathcal{V}\), its propagated prediction score is the sum of its descendant leaf probabilities: \(\hat{g}(\mathbf{x})_v := \sum_{w \in \text{leaf-cov}_\mathcal{T}(\{v\})} \hat{f}(\mathbf{x})_w\). The hierarchical ground truth \(\mathcal{Y}'_i\) includes all ancestors of the true leaf \(y_i\). Because a DAG allows multiple inheritance (a leaf node can belong to multiple parents within the same NOL-cover), calibration reduces to a multi-label setting. Standard single-label conformal non-conformity scores do not apply. HCC proposes a generalized score function: $\(s(\mathbf{x}_i, \mathbf{y}_i, \mathcal{S}) = \hat{g}(\mathbf{x}_i)_{v'_i}, \quad \text{where} \quad v'_i := \arg\max_{j: \mathbf{y}_{i,j}=1} \hat{g}(\mathbf{x}_i)_j\)$ By evaluating the highest score among all valid ground-truth labels in the candidate NOL-cover, Theorem 1 proves that constructing prediction sets \(C(\mathbf{x}_t) := \{v \in \mathcal{V} \mid s(\mathbf{x}_t, \mathbf{y}_t, \mathcal{S}) \le \hat{q}\}\) with empirical quantile \(\hat{q} = \lceil(n_c+1)(1-\alpha)\rceil / n_c\) mathematically guarantees finite-sample coverage: \(\mathbb{P}[y_t \in \text{leaf-cov}_\mathcal{T}(C(\mathbf{x}_t))] \ge 1-\alpha\).

4. Dynamic Inference Pruning via Lowest Common Ancestors (LCA) Evaluating \(m\) candidate conformal predictors in parallel at inference time requires adjusting the target error rate \(\alpha\) to prevent coverage loss from multiple hypothesis testing. A conservative Bonferroni correction \(\alpha' = \alpha / m\) can produce excessively wide prediction sets if \(m\) is large. HCC introduces dynamic instance-level search pruning: the model computes the prediction set of standard leaf CP and determines its Lowest Common Ancestor (LCA) in the taxonomy DAG. Any candidate NOL-cover containing ancestors above this LCA is guaranteed to produce broader, less specific predictions than the LCA itself, yielding strictly worse objective costs. By dynamically pruning all such candidate solutions during inference, the active candidate count \(m_t\) is dramatically reduced, substantially mitigating the conservatism of the Bonferroni correction.

A Worked Example

Consider the restaurant menu classification problem presented in the paper (7 leaves: Caesar salad, Greek salad, cheese sandwich, ham sandwich, tuna sandwich, omelette, pancakes; internal nodes include salad, sandwich, breakfast, lunch; root node is dish): - Standard Flat CP: For an ambiguous sandwich photo where the base model hesitates between subtle sandwich ingredients, standard CP outputs {cheese sandwich, ham sandwich, tuna sandwich, omelette} to achieve \(99\%\) coverage guarantee. The set has cardinality 4 and lacks focus. - HCC Execution: 1. Leaf probabilities are propagated upward; internal node "sandwich" accumulates scores from cheese, ham, and tuna sandwiches (e.g., \(0.45 + 0.30 + 0.15 = 0.90\)). 2. The candidate NOL-cover containing {sandwich, omelette, pancakes, salad} is evaluated alongside the all-leaf baseline. 3. The node "sandwich" easily passes the calibrated threshold with its high aggregated score (\(0.90\)). 4. Minimizing the cost objective selects the set {sandwich, omelette}. 5. The prediction set size drops from 4 to 2, cleanly summarizing fine-grained model uncertainty using a concise parent category while maintaining exact mathematical coverage of the ground truth.

Loss & Training

Hierarchical Conformal Classification is a post-processing calibration framework that requires no parameter fine-tuning or retraining of the underlying deep neural network: - Offline Phase: For each valid NOL-cover \(\mathcal{S}\) extracted via recursive topological traversal (Algorithm 1), compute conformity scores \(\{s(\mathbf{x}_i, \mathbf{y}_i, \mathcal{S})\}_{i=1}^{n_c}\) over calibration set \(\mathcal{D}_c\), deriving the calibrated quantile threshold \(\hat{q}_\mathcal{S}\). - Online Phase: Given test sample \(\mathbf{x}_t\), apply dynamic LCA pruning to extract active subset \(\mathcal{H}_t\), set corrected significance level \(\alpha' = \alpha / |\mathcal{H}_t|\), generate candidate sets \(C_\mathcal{S}(\mathbf{x}_t)\), and return the candidate set with minimal cost according to Equation (3).

Key Experimental Results

Main Results

HCC was evaluated across three distinct benchmarks spanning text (DBpedia14, 14 classes/25 nodes/depth 6/BERT), image (ImageNet1K, 1000 classes/1860 nodes/depth 17 WordNet/ResNet-152), and audio (GTZAN, 10 classes/15 nodes/depth 3/XGBoost) with an 80/20 calibration/test split. The main evaluation compares Standard CP, LCA baseline, and HCC.

Dataset Target Guarantee \(1-\alpha\) Penalty \(\beta\) Method Empirical Coverage (Coverage ↑) Objective Cost (Costs ↓) Prediction Set Size (PS size ↓) Covered Leaf Count (# covered leaves ↓)
DBpedia14 (dbp) 0.9997 0.19 Standard CP 0.9998 ± 0.02 3.18 ± 2.62 2.67 ± 2.20 2.67 ± 2.20
LCA 0.9999 ± 0.01 2.20 ± 1.13 1.00 ± 0.00 6.32 ± 5.94
HCC (Ours) 0.9999 ± 0.01 2.07 ± 1.00 1.25 ± 0.55 4.30 ± 4.65
ImageNet1K (img) 0.9800 0.04 Standard CP 0.9807 ± 0.14 11.49 ± 20.49 11.04 ± 19.70 11.04 ± 19.70
LCA 0.9951 ± 0.07 14.79 ± 15.63 1.00 ± 0.00 344.70 ± 390.64
HCC (Ours) 0.9846 ± 0.12 8.09 ± 11.01 4.41 ± 6.54 92.12 ± 245.12
GTZAN (gtz) 0.9000 0.25 Standard CP 0.9613 ± 0.19 2.73 ± 0.97 1.19 ± 0.39 6.17 ± 4.14
LCA 0.9812 ± 0.14 2.86 ± 1.01 1.00 ± 0.00 7.45 ± 4.02
HCC (Ours) 0.9637 ± 0.19 2.76 ± 0.98 1.11 ± 0.32 6.57 ± 4.24

Note: Bold indicates meeting target coverage and achieving best performance among valid methods. Numbers reported as mean ± SD.

Ablation Study & User Study

To assess the impact of dynamic pruning, Bonferroni correction, and conformity scoring, ablations were conducted on ImageNet1K. HCC was also compared with Structured Conformal Prediction (SCP; Zhang et al., 2025) using GLPK-MI solver on ImageNet1K with \(\alpha=0.10\). A double-blind user study with 4 annotators was conducted on 500 test instances for DBpedia14 and ImageNet1K.

Ablation Study and Benchmark Comparison Table:

Dataset Variant / Method Coverage (Coverage ↑) Total Cost (Costs ↓) Prediction Set Size (PS size ↓) Covered Leaves (# covered leaves ↓) Mechanism Assessment
img (\(\alpha=0.02\)) HCC (Full) 0.9846 ± 0.12 8.09 ± 11.01 4.41 ± 6.54 92.12 ± 245.12 Full pipeline balancing size & specificity
w/o dynamic pruning 0.9791 ± 0.14 15.90 ± 13.40 2.46 ± 1.94 336.04 ± 327.04 Severe leaf coverage inflation without LCA
w/o correction 0.9630 ± 0.19 4.51 ± 4.76 2.02 ± 1.59 62.17 ± 107.35 Violates 98% coverage guarantee
w/o conformity 0.9497 ± 0.22 2.90 ± 3.43 2.57 ± 3.22 8.38 ± 25.92 Replaces score with Recall loss; fails coverage
img (\(\alpha=0.10\)) Standard CP 0.8982 1.82 1.75 1.75 Flat baseline with no hierarchy
LCA 0.9494 5.58 1.00 114.59 Excessive over-abstraction
SCP (\(M=4\)) 0.9262 2.78 1.64 21.27 Integer programming formulation
SCP (\(M=8\)) 0.9188 2.50 2.13 10.54 Fixed set size constraint limits flexibility
HCC (Ours) 0.9036 1.63 1.49 3.57 Outperforms SCP across all metrics

User Study Preferences Table (4 Annotators, 500 Random Samples):

Dataset Metric Dimension Preference: HCC Preference: Standard CP No Preference Binomial Test \(p\)-value
DBpedia14 (dbp) Annotation count (# / %) 523 (52.4%) 401 (40.2%) 74 (7.4%) \(p = 3.4 \times 10^{-5}\) (~57% preference)
Majority count (# / %) 126 (50.4%) 90 (36.0%) 12 (4.8%) Fleiss' \(\kappa = 0.47\) (moderate agreement)
ImageNet1K (img) Annotation count (# / %) 577 (57.9%) 239 (24.0%) 180 (18.1%) \(p = 2.4 \times 10^{-33}\) (~71% preference)
Majority count (# / %) 126 (50.4%) 35 (14.0%) 46 (18.4%) Fleiss' \(\kappa = 0.53\) (moderate agreement)

Key Findings

  • Coverage Guarantees Require Explicit Multiple-Testing Control: Omitting the Bonferroni correction causes empirical coverage on ImageNet to plummet from 98.46% down to 96.30%, violating the theoretical \(1-\alpha=0.98\) requirement. Similarly, substituting the multi-label score with a Conformal Risk Control recall loss fails coverage (94.97%), confirming the necessity of Theorem 1.
  • Dynamic Pruning Prevents Trivial Over-Abstraction: Disabling dynamic LCA pruning leads to a doubling of objective costs (8.09 to 15.90) and explodes covered leaves from 92.12 to 336.04, demonstrating that dynamic pruning keeps predictions semantically informative rather than collapsing into meaningless high-level roots like "entity".
  • Significant Human Preference for Hierarchical Predictions: The user study demonstrates a statistically significant human preference for HCC over flat CP (57% for DBpedia, 71% for ImageNet; \(p < 10^{-32}\)). Annotators strongly preferred concise category summaries (e.g., {lizard}) over large enumerations of fine-grained leaf categories (e.g., {agama, alligator lizard, green lizard, whiptail}).

Highlights & Insights

  • Bridging Taxonomy Knowledge and Uncertainty Quantification: Rather than treating uncertainty solely as the size of flat label lists, HCC embeds semantic hierarchies into the uncertainty metric itself, allowing smooth trade-offs between prediction set cardinality and specificity.
  • Theoretically Rigorous Combinatorial Pruning via NOL-covers: By proving the necessity of leaf coverage and sufficiency of ancestral independence, the method circumvents the \(2^{|\mathcal{V}|}\) search explosion, offering scalable calibration without commercial solvers.
  • Model-Agnostic Post-Hoc Framework: HCC requires zero architectural modifications or retraining; it interfaces directly with output probability vectors and predefined DAG taxonomies across vision, NLP, and audio domains.

Limitations & Future Work

  • Conservatism of Bonferroni Correction: Bonferroni correction can be overly conservative as the hierarchy size scales up. Incorporating sequential testing procedures (e.g., Holm's step-down procedure) or tree-structured graphical hypothesis testing could sharpen thresholds.
  • Degeneration into Generic Roots Under Extreme Uncertainty: In instances with severe input ambiguity or multi-object confusion, HCC occasionally outputs uninformative high-level parents (e.g., "object" or "artifact"). Constraining maximum hierarchical abstraction depth is a promising avenue.
  • Dependence on Clean Hierarchical Taxonomies: The approach assumes a clean, cycle-free DAG. Extending HCC to noisy, partially observed, or dynamically learned ontologies remains an open challenge.
  • vs. Standard Conformal Prediction (Angelopoulos et al., 2021): Standard CP ignores class topology, outputting large, unstructured sets of leaves under ambiguity; HCC outputs compact internal nodes while guaranteeing statistical coverage.
  • vs. Hierarchical Risk Control (Angelopoulos et al., 2024; Mortier et al., 2025): Prior methods restrict predictions to tree structures or ancestor chains along the single top-1 prediction; HCC operates on general DAGs and flexibly includes internal and leaf nodes across multiple branches.
  • vs. Structured Conformal Prediction (SCP; Zhang et al., 2025): SCP formulates structured prediction as an integer program that scales poorly and requires a hard ceiling on set size; HCC uses NOL-cover pruning and dynamic LCA filtering to achieve superior computational efficiency and Pareto-optimal trade-offs.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ (First rigorous formulation of hierarchical conformal prediction on general DAGs with NOL-cover search pruning)
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ (Comprehensive cross-modal evaluation on text, image, and audio benchmarks, rigorous ablations, and large-scale user study)
  • Writing Quality: ⭐⭐⭐⭐⭐ (Clear mathematical exposition, elegant theoretical proofs, and well-structured empirical analysis)
  • Value: ⭐⭐⭐⭐⭐ (Provides an actionable, highly practical uncertainty quantification methodology for safety-critical classification tasks)