A classifier that is unsure whether a photo shows a husky or a malamute should not have to stay silent. It can say "dog" and still be right. Recent work makes this precise. In hierarchical selective classification, a model with a reject option backs off to a coarser node of a class tree when it is uncertain, instead of abstaining outright. The result is a guaranteed bound on how often the emitted node fails to contain the true class. Every such method takes the tree as given: WordNet for ImageNet, the biological taxonomy for iNaturalist. A curated taxonomy, however, records what things are. It does not record what a model confuses. A model that mixes up a tabby cat with a lynx-patterned rug gets nothing from WordNet. The nearest node covering both classes is close to the root, so retreating to it says almost nothing.
This note proposes learning the retreat tree from data, directly for the purpose of selective prediction. Given a trained classifier and held-out data, we build a tree over its classes. Merges are chosen to maximize how specific the answers can be at a fixed, statistically guaranteed error rate. We then calibrate the backing-off rule on a separate data split, so the guarantee survives the fact that the tree was estimated. The claim we test is concrete. At the same guaranteed risk, a discovered tree yields more specific answers than the curated taxonomy, and the gap is largest where the taxonomy and the model's errors disagree. The method also works for label sets that have no taxonomy at all.
Core Claim and Positioning
The closest work is Hierarchical Selective Classification, which supplies most of our machinery. Its climbing rule starts at the most likely leaf. It then walks up the ancestor path until it reaches a node whose summed descendant probability exceeds a threshold $\theta$. The threshold is calibrated with a split-conformal-style procedure, which yields a high-probability bound on hierarchical risk: the chance that the emitted node is not an ancestor of the true label. That paper reports a 14.94% hierarchical gain over flat selective classification on ImageNet-1k across 1,115 models, and gains often above 40% for CLIP-trained models. Its tree is fixed and curated. We keep the climbing rule and the calibration, and replace the tree.
Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity is the second constraint on our design. It outputs prediction sets built from at most $r$ internal nodes of a given tree, chosen by dynamic programming. It shows that on PlantCLEF 2015, allowing $r=3$ shrinks set size from about 123 to about 44 at the same nominal coverage. That gap tells us how much efficiency the single-node restriction costs on a fixed tree. Our bet is different: much of that cost comes from the tree being the wrong shape for the model, not from the single-node restriction itself.
On the discovery side, three lines of work learn hierarchies without a curated tree. Hierarchically Clustered Representation Learning fits a tree-structured mixture inside a variational autoencoder, with grow, prune and merge moves. Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry embeds items in hyperbolic space, where distance from the origin encodes generality. Fine-grained Classes and How to Find Them, known as FALCON, recovers latent subclasses under known coarse labels. All three judge a hierarchy by how well it reconstructs structure, measured by likelihood, mean rank or adjusted Rand index. None judges it by what it buys a downstream abstaining classifier, and none offers any risk control. We use them as alternative tree sources, not as the method.
The Method
Let $f$ be a fixed classifier over $K$ leaf classes, with softmax output $p(y\mid x)$. A tree $T$ assigns each internal node $v$ a leaf set $L(v)$. We measure the specificity of emitting $v$ with a quantity that depends only on the leaf set, so that different trees are scored on the same scale:
$$c(v) = 1 - \frac{\log \pi(L(v))}{\log \pi_{\min}},$$
Here $\pi(L(v))$ is the training-prior mass of the classes under $v$, and $\pi_{\min}$ is the mass of the rarest class. A leaf scores near 1 and the root scores 0. The same numerator gives the information-gain coverage used in Hierarchical Selective Classification, up to normalization. For a target risk $\alpha$, let $\theta_T(\alpha)$ be the climbing threshold that achieves hierarchical risk $\alpha$ on fitting data. The tree objective is then the mean specificity at that operating point, averaged over a grid of target risks $\mathcal{A}$:
$$J(T) = \frac{1}{|\mathcal{A}|}\sum_{\alpha \in \mathcal{A}} \mathbb{E}_x\big[c(v_T(x;\theta_T(\alpha)))\big],$$
In this expression, $v_T(x;\theta)$ is the node the climbing rule emits for input $x$.
We maximize $J$ by greedy agglomeration. Starting from singleton leaves, each candidate merge is scored by its actual change in $J$. Merges can join two nodes, or absorb a node into an existing sibling group, so the tree need not be binary. To keep cost manageable at $K=1000$, candidates are restricted to the top-$k$ most confused neighbors of each current node. The objective is cheap to evaluate because it needs only cached softmax vectors, not retraining.
This criterion differs from confusion-based clustering in two ways that matter. First, it charges for lost specificity: merging two large, heavily populated nodes makes many easy inputs coarser for little reduction in risk. Second, it scores the merge at the thresholds the climbing rule will actually use, rather than by raw pairwise confusion.
Learned nodes are not named, which is a real cost when a curated taxonomy exists. We therefore also run a constrained variant that allows a merge only if the resulting leaf set lies within a WordNet subtree of bounded depth. This variant gives a dial between efficiency and nameability, and we report where along that dial the gains come from.
Guarantee Under an Estimated Tree
The guarantee in Hierarchical Selective Classification treats the tree as fixed. If the tree is fit on the same data used to calibrate $\theta$, exchangeability breaks and the bound can fail. We split held-out data three ways: tree fitting, threshold calibration, and test. Conditional on the fitting split, the tree is fixed. The existing calibration argument then applies unchanged to the event "true label $\in L(v)$", which is well defined for any tree.
This is simple, and we claim no new theory. We do measure two things. One is how badly the guarantee is violated when the fitting and calibration splits are shared. The other is how specificity degrades as the fitting split shrinks, which is the practical price of discovery.
Research Program
The work has three parts. The first is a diagnostic study. Using cached outputs from a range of pretrained ImageNet-1k classifiers, including CLIP zero-shot models, we measure how often the climbing rule under WordNet retreats past semantically distant ancestors. We then ask whether such over-retreats concentrate on class pairs that are visually confusable but far apart in WordNet. This study motivates or falsifies the whole proposal. If WordNet already matches model confusions, learned trees should give little.
The second part builds the selection-aware tree learner, its WordNet-constrained variant, and the three-way-split calibration.
The third part tests transfer. We check whether a tree learned for one model works for another, and whether a tree learned on clean data still holds under distribution shift, where the model's confusions change.
Baselines
The naive reference is flat selective classification with softmax-response confidence and risk-controlled thresholds, as in Selective Classification for Deep Neural Networks. That paper reports 2% top-5 error at about 60% coverage on ImageNet with VGG-16. In our metric, a flat selector emits either a leaf ($c=1$) or the root ($c=0$). It shares the same models and calibration split, so any learned tree must clear it first.
The strongest existing method is climbing over the curated taxonomy, from Hierarchical Selective Classification. It runs on WordNet for ImageNet-1k, the 7-level taxonomy for iNat21, and the 20 superclasses for CIFAR-100. Its reported reference is the 14.94% hierarchical gain over flat selection on ImageNet-1k. For iNat21 we found no reported result on Lacuna for a specific number, so we recompute this baseline ourselves. It uses identical models, softmax outputs and calibration data, and we report results with each method's own threshold calibrated on the same split. Beating it means higher mean specificity $J$ at equal or lower test hierarchical risk across $\alpha \in \{1\%, 2\%, 5\%, 10\%\}$, consistently across models, with non-overlapping bootstrap intervals over calibration resamples.
The key ablation uses the identical agglomeration procedure and the identical candidate restriction. The only change is that merges are scored by symmetric confusion instead of by $\Delta J$. This isolates whether the selection-aware criterion matters. We also include trees from feature-space discovery as tree sources under the same climbing and calibration: agglomerative clustering of class-mean features, a Lorentz embedding of the class confusion graph following Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry, and HCRL where it scales.
Finally, we compare against set-valued conformal prediction: CRSVP and CRSVP-r from Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity on PlantCLEF 2015, Caltech-256 and DBpedia, where its reported set sizes are about 123 for CRSVP and about 44 for CRSVP-3 on PlantCLEF. We run it on both the curated and the learned trees. This shows whether a better tree recovers part of what extra representation complexity buys.
Why not just…?
Why not just cluster the confusion matrix and run the climbing rule on the result? This is the most serious threat, and it is a baseline here, not a strawman. Greedy confusion merging captures most of the intuition, and it may come close to our criterion. Our reason to expect a gap is that confusion ignores the specificity cost of merging populous nodes and ignores the operating thresholds. Both of these enter $J$ directly. The criterion ablation settles the question. If confusion clustering matches the $\Delta J$ criterion within error bars, we will report that the useful contribution is the empirical finding: discovered trees, built by the simplest method, beat curated ones at guaranteed risk. We would not claim a better tree learner.
Why not just abstain flatly? Hierarchical Selective Classification already shows that retreat beats flat rejection, with a 14.94% gain on ImageNet-1k. Our proposal concerns which tree to retreat along, so the flat selector serves only as the floor.
Why not just use the curated taxonomy, which has the advantage of named nodes? When interpretability is the binding requirement, one should. We report the WordNet-constrained variant and the leaf-set Jaccard overlap between each learned node and its best-matching WordNet node, so a practitioner can see how much specificity naming costs. Where no taxonomy exists, which covers many deployed label sets, this alternative is unavailable.
Why not just emit unconstrained conformal label sets? Arbitrary sets are often smaller but lack coherent structure. Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity argues this point and keeps tree structure for that reason. Our learned trees keep the single-node output format while trying to close the efficiency gap. The CRSVP comparison measures how much of that gap is closed.
Proposed Experiments
The decisive check is on ImageNet-1k and iNat21. We plot hierarchical risk against specificity for the curated tree, the confusion-clustered tree, and the selection-aware tree, under the same models and splits. The proposal succeeds if the selection-aware tree dominates the curated one at every target $\alpha$. It should also beat or match confusion clustering, and its improvements should concentrate on the WordNet-distant confusable pairs identified in the diagnostic study.
On CIFAR-100, whose 20 superclasses are coarse and only partly visual, we expect the largest gains over the curated tree. This is a useful falsification point: a small gap there would undercut the thesis.
The guarantee check compares empirical test risk under shared and separated fitting and calibration splits, for fitting-split sizes from 5% to 50% of the held-out data.
The shift check learns trees on clean ImageNet and evaluates on ImageNet-C. It asks whether the risk guarantee holds under shift and whether learned trees lose their advantage. We expect the guarantee to fail under shift for every tree, curated ones included, consistent with the miscalibration under shift documented by Calibrated Selective Classification. The comparison we care about is whether learned trees fail more than curated ones.
The transfer check applies a tree learned for one architecture to another. If tree quality is mostly model-specific, the practical recipe becomes: refit the tree for each model on a small split, which cached softmax outputs make cheap.
References
- Hierarchical Selective Classification
- Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity
- Hierarchically Clustered Representation Learning
- Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry
- Fine-grained Classes and How to Find Them
- Selective Classification for Deep Neural Networks
- Calibrated Selective Classification