A classifier that is allowed to say "I don't know" should abstain for two different reasons. The first is that the input sits where two known classes genuinely overlap. The second is that the input sits somewhere the training data never reached. Today's abstention scores, such as the top softmax probability or the gap between the top two logits, collapse both reasons into one number. Worse, they can be confidently wrong on shifted inputs that land far from any training example yet still fall well inside one class's decision region.
Density-based clustering, the family of methods like DBSCAN that defines a cluster as a connected region of densely packed points and labels everything else as noise, already has a vocabulary for this distinction. It separates core points that sit inside dense regions, border points that are reachable from them, and noise points that are reachable from nothing. We propose to build that vocabulary into the training set's feature space and add one supervised twist: a test input is trusted only if it can be reached, through a chain of dense training points, from a dense region whose labels agree with the classifier's prediction. The result is a post-hoc rejection rule that needs no retraining. It splits rejections into "overlap", "void", and "wrong neighborhood". We will test whether the chain-of-dense-points ingredient adds anything over simply counting nearby labels.
Core Claim
Selective prediction trains or calibrates a pair: a predictor $f$ and a gate $g$ that decides whether to answer. It is evaluated by the risk–coverage curve, which plots error on accepted inputs against the fraction accepted, and summarized by its area (AURC). The claim is that, under distribution shift, a gate built on label-consistent density reachability in a frozen network's penultimate features gives lower selective risk than margin or softmax scores at matched coverage. It also does better than gates that measure only local density. The reason is that the gate can reject a confident prediction whose feature vector has drifted into a void, or into a dense region belonging to a different class, while keeping in-distribution points that sit near a boundary.
Concretely, we run the decoupled-radius variant from Robustness Guarantees for Density Clustering on training features. That paper separates a small radius $\epsilon$ used to decide which points are dense (core) from a larger radius $\tilde\epsilon$ used to link core points into components, and it proves this buffer stops clusters from being bridged or fragmented by a contamination fraction of points. Each component $C$ gets a majority label $y_C$ and a purity $\pi_C$, the fraction of its core points carrying $y_C$. At test time, $x$ attaches to the component of its nearest core point if that point lies within $\tilde\epsilon$, and is otherwise unreachable. The selection score is lexicographic:
$$s(x) = \begin{cases} 2 + \pi_C\, \sigma(M(x)) & \text{if } x \text{ attaches to } C \text{ with } y_C = f(x),\\ 1 + \sigma(M(x)) & \text{if } x \text{ attaches to } C \text{ with } y_C \neq f(x),\\ \sigma(M(x)) & \text{if } x \text{ is unreachable,} \end{cases}$$
Here $M(x)$ is the top-two logit gap and $\sigma$ is a monotone squashing to $(0,1)$. Within a tier, inputs are ranked by margin, so the score inherits the scale invariance argued for in Selective Classification Under Distribution Shifts. Thresholds on $s$ are then set with the binomial-tail procedure of Selective Classification for Deep Neural Networks, which gives a risk guarantee on i.i.d. data.
Position Relative to Prior Work
Three papers motivate the gap. Selective Classification Under Distribution Shifts defines generalized selective classification over in-distribution errors, label-shift errors and covariate-shift errors. It shows that margin scores reject points near decision boundaries and work best overall. It also reports that off-the-shelf out-of-distribution (OOD) density scores "do not translate well" to this setting. That negative result constrains our design: density alone must not drive the gate, which is why margin stays the within-tier ranking. That paper treats all points at a given margin alike, whatever lies around them; we do not.
Towards Better Selective Classification shows that softmax response on a model trained with self-adaptive training plus entropy minimization (SAT+EM+SR) beats learned selection heads. It concedes that entropy minimization can produce confident errors under shift. That concession is exactly the failure our void and wrong-neighborhood tiers target.
SelectiveNet trains a dedicated selection head. It observes qualitatively that rejected points clump together in latent space, but it decides abstention with a sigmoid rather than by measuring that geometry.
One paper supplies the closest mechanism and is the work we must most clearly differ from. Leveraging Data to Say No (MA-PaPSP) retrieves a fixed number $K$ of nearest neighbors from an external memory and averages them into a proxy embedding. It never asks whether those neighbors lie in one connected dense region or straddle two, and it uses no core/noise distinction.
Robustness Guarantees for Density Clustering supplies the clustering method and its stability argument, but it is purely unsupervised. Self-Adaptive Incremental PCA-Based DBSCAN uses DBSCAN noise as an anomaly flag on motor sounds, reaching an area under the ROC curve of 0.84. It has no predictor, no coverage trade-off and no risk bound. Our contribution is the supervised, label-consistency coupling that neither line has.
Research Program
We freeze trained backbones and extract L2-normalized penultimate features. We optionally reduce them with PCA to a moderate dimension, because the clustering survey A Comprehensive Survey of Clustering Algorithms documents distance concentration in high dimension. Following the adaptive-density literature (Adaptive Density Level Set Clustering), $\epsilon$ is set from a quantile of the $k$-th nearest-neighbor distance, and $\tilde\epsilon$ is a multiple of $\epsilon$. Both are tuned on a held-out in-distribution validation split by AURC, never on shifted data. Neighbor search uses approximate nearest neighbors, so building the graph over ImageNet's training set stays an offline cost. Test-time cost is one nearest-core lookup.
Beyond accuracy, we analyze three things. First, how the three tiers line up with the three error types defined in Selective Classification Under Distribution Shifts. Second, whether entropy-minimized SAT features form purer, better-separated components than plain cross-entropy features; this would explain why SAT+EM helps and when it breaks. Third, how sensitive results are to $(\epsilon, \tilde\epsilon)$, the known weakness of the clustering side.
Baselines
The naive reference is softmax response on a standard cross-entropy model. On CIFAR-10, Selective Classification for Deep Neural Networks reports 1% error at 78% coverage with its guaranteed thresholding. On ImageNet top-5 with VGG-16, it reports 2% error at roughly 60% coverage. We reproduce these numbers as a sanity check before comparing.
The strongest in-distribution competitor is SAT+EM+SR from Towards Better Selective Classification. It reports up to 80% relative error reduction on ImageNetSubset and consistent wins on StanfordCars and Food101; no absolute AURC value appears in our file. The strongest competitor under shift is the confidence-margin and geometric-margin pair from Selective Classification Under Distribution Shifts, reported best overall on ImageNet with the EVA model when all shift types are present. No reported result was found on Lacuna for its exact AURC scalars, so we will rerun it.
Fairness is enforced by sharing everything. Every score is applied to the same frozen SAT+EM backbone, so our gate is post-hoc on the strongest predictor rather than on a weaker one. Every method gets the same validation split and the same grid budget for its hyperparameters. Every threshold is selected by the same procedure. We also include a parametric OOD gate (Mahalanobis or energy, thresholded alone and combined with margin) and SelectiveNet run at its own target coverages.
Two ablations isolate the key ingredient. The first, local-only, replaces reachability with $k$-nearest-neighbor label agreement times $k$-nearest-neighbor density, which is the MA-PaPSP-style fixed ball. The second, unlabeled reachability, keeps the components but drops the label-consistency test.
Beating the field means two things. Our score must have lower AURC than both margin scores and SAT+EM+SR on the shifted benchmarks, averaged over seeds. It must also lose no more than a seed-noise margin in-distribution, where CIFAR-10 is noted as saturated.
Why not just…?
Why not just use softmax response or SAT+EM? In distribution it may be nearly unbeatable, and we expect ties on CIFAR-10. But Towards Better Selective Classification itself flags overconfidence under shift. Selective Classification Under Distribution Shifts finds margin scores beat softmax in the low-risk regime and shows softmax is sensitive to logit scale. Our comparison on ImageNet-C and OpenImage-O, using the same backbone, settles whether the void tier catches the confident shifted errors that softmax accepts.
Why not just use the logit margin? This is the strongest competitor, and our score reduces to it inside each tier. Any gain must therefore come from the tier structure. The tier-versus-error-type analysis shows directly whether rejected-by-tier points are disproportionately covariate-shift errors that margin had accepted.
Why not just combine margin with $k$-nearest-neighbor density and neighbor-label agreement? This is the real threat. It is cheaper and could plausibly match us whenever class manifolds in feature space are compact. The local-only ablation is the decisive test. To probe the mechanism, we also run synthetic moons and circles embedded in feature-like dimensions, where a fixed-$K$ ball provably spans two components. If local-only matches us on the real shift benchmarks, we will report that connectivity is unnecessary in learned features. The remaining contribution would then be only the three-way decomposition.
Why not just threshold an OOD density score? Selective Classification Under Distribution Shifts already reports that OOD scores transfer poorly to selective classification, because they ignore whether accepted predictions are correct. Our design keeps density as a coarse tier and margin as the ranking. The Mahalanobis-plus-margin baseline tests whether a single centroid per class suffices, which the clustering survey suggests fails on curved manifolds.
Why not just use MC-dropout? It costs many forward passes. On ImageNet it lost to softmax response in Selective Classification for Deep Neural Networks, and SelectiveNet beat it by up to 26.8% relative risk at 75% CIFAR-10 coverage in SelectiveNet. We include it only on CIFAR for completeness.
Proposed Experiments
In-distribution runs use CIFAR-100, StanfordCars and ImageNet. Synthetic covariate shift uses CIFAR-10-C and ImageNet-C across all severities. Label shift uses OpenImage-O against an ImageNet backbone. Natural shift uses iWildCam, with its unseen test locations, and Amazon Reviews, the latter with a text encoder to check that the method is not vision-specific. Metrics are AURC, selective risk at fixed coverages, and violation rates of the guaranteed risk bound on i.i.d. and shifted test sets.
Four checks are decisive. First, on combined-shift ImageNet, our score must beat the confidence margin in AURC, and the local-only ablation must fall measurably short of us; otherwise the connectivity claim fails. Second, on iWildCam's new locations, the fraction of covariate-shift errors that the void and wrong-neighborhood tiers reject should exceed what margin rejects at equal coverage. Third, multiplying logits by a constant must leave our risk–coverage curve unchanged. Fourth, AURC should vary smoothly across a factor-of-two sweep in $\epsilon$ and $\tilde\epsilon$. If it does not, the method inherits DBSCAN's parameter fragility, and that limitation is the finding we report.
References
- Robustness Guarantees for Density Clustering
- Selective Classification Under Distribution Shifts
- Selective Classification for Deep Neural Networks
- Towards Better Selective Classification
- SelectiveNet: A Deep Neural Network with an Integrated Reject Option
- Leveraging Data to Say No: Memory Augmented Plug-and-Play Selective Prediction
- Self-Adaptive Incremental PCA-Based DBSCAN of Acoustic Features for Anomalous Sound Detection
- A Comprehensive Survey of Clustering Algorithms
- Adaptive Density Level Set Clustering