Local Charts for Rejection: Cheap Manifold Residuals as a Selective Prediction Score

A classifier that may abstain, called a selective classifier, predicts only when it trusts itself and hands the rest to a human or a fallback system. In practice, the trust signal is almost always the model's top softmax probability. That signal is hard to beat on ordinary held-out data. It fails badly when inputs come from somewhere the training data never covered, because softmax is normalized over the known classes and can be confidently wrong on anything. The geometric fix is to ask whether a test point's internal representation lies on the low-dimensional surface, or manifold, that the training representations occupy. The obstacle is cost. Manifold methods build neighbor graphs and eigendecompositions that scale quadratically or cubically in the number of training points, and nearest-neighbor scores require a search over the whole training set at every query.

We propose to cover the training features with many small overlapping patches, each approximated by a flat local subspace whose dimension is estimated from the data. A test point is rejected when its softmax confidence is low, when its distance from the nearest patch's subspace is large, or when a weighted sum of the two passes a threshold. This mirrors how domain-decomposition manifold learning splits a large dataset into small charts. The key observation is that rejection needs only the local residuals, never a global stitched embedding. The expensive alignment step that dominates scalable manifold learning can therefore be dropped entirely. Inference reduces to a lookup over patch centers plus one small projection, and the reject threshold is set with an existing finite-sample risk guarantee.

Core Claim

Our central hypothesis is that a selection score built from distance to a local tangent subspace beats softmax-only selection when abstention must cover both hard in-distribution inputs and unfamiliar ones. Each local subspace is a small principal-component fit inside one patch of a partitioned neighbor graph. We combine this residual additively with softmax confidence and set the threshold with a guaranteed-risk calibration. The method should also match or beat a single-Gaussian-per-class (Mahalanobis) residual whenever classes are multimodal or curved in feature space. Its cost at test time should not grow with the training set.

Concretely, let $z \in \mathbb{R}^D$ be a test point's penultimate-layer feature. Let chart $j$ have center $\mu_j$, an orthonormal basis $U_j$ of dimension $d_j$, and a typical in-chart residual scale $\sigma_j$. The normalized residual is

$$\rho(z) = \min_{j \in \mathcal{N}(z)} \frac{\|(I - U_j U_j^\top)(z - \mu_j)\|}{\sigma_j},$$

where $\mathcal{N}(z)$ is the small set of charts whose centers are nearest to $z$. Taking the minimum over overlapping charts is our stand-in for stitching. We reject when

$$\big(1 - \max_k p_k(z)\big) + \lambda\, \rho(z) > \tau,$$

where $p_k(z)$ is the softmax probability of class $k$, $\lambda \ge 0$ weights the geometric term, and $\tau$ is the threshold.

The additive form is not a design choice of ours. Plugin estimators for selective classification with out-of-distribution detection derives the Bayes-optimal rule for joint misclassification and out-of-distribution rejection as confidence error plus a density ratio. It also proves that multiplicative heuristics are suboptimal. Our contribution is the density-ratio surrogate, which is local, geometric and cheap, and the claim that it is a better plug-in than the generic scores (such as gradient norms) that paper uses.

Position Relative to Prior Work

Three groups of papers play different roles here.

The first group motivates the gap. A Geometry-Based View of Mahalanobis OOD Detection shows across 22 backbones that local intrinsic dimensionality and within-class spectral decay govern whether a Mahalanobis detector works. That is direct evidence that local geometry carries signal softmax lacks. The paper studies only out-of-distribution detection, not risk–coverage on in-distribution data. It also fits one global Gaussian per class, which is exactly the special case of our method with one chart per class and full dimension. The Bayes-optimal rule from the plug-in paper tells us how to combine scores but leaves the density term to off-the-shelf estimators.

The second group constrains the design. Towards Better Selective Classification shows that learned selection heads lose to plain softmax response at test time, so we deliberately add no learned rejection head. Selective Classification for Deep Neural Networks shows that softmax matches multi-pass dropout on ImageNet, which rules out sampling-based uncertainty as the competitor worth chasing. Confidence-aware Contrastive Learning for Selective Classification reshapes features with a Euclidean contrastive loss to shrink intra-class variance. It is complementary: we change the score, not the training, and we test on top of its features.

The third group supplies the method. A Domain Decomposition Method for Fast Manifold Learning partitions the neighbor graph into overlapping subdomains, fits local charts, and then glues them. That reduces Swiss Roll runtime from 6.23 s to 0.11–0.53 s. We reuse the partitioning and local fitting and discard the gluing, because no global coordinates are needed for rejection. The paper's requirement of at least $d+1$ general-position points in each overlap becomes our minimum chart size. Chart dimension $d_j$ is set with the maximum-likelihood estimator of Maximum Likelihood Estimation of Intrinsic Dimension, as implemented in Scikit-dimension: a Python package for intrinsic dimension estimation. The threshold $\tau$ is calibrated with the binomial-bound binary search of the guaranteed-risk method, so the user still gets a statement that test risk is at most $r^*$ with probability $1-\delta$ on in-distribution data.

Conformal prediction in manifold learning is the nearest geometric-uncertainty work. It addresses regression, uses Jacobian-based scores, and reports no benchmark evaluation. We address classification with abstention and run full benchmarks.

Research Program

The build is post hoc on a frozen classifier.

Charts are built offline from training features. If $D$ is large, we first apply a Johnson–Lindenstrauss random projection, following Random Projections for Non-linear Dimensionality Reduction. We then build an approximate neighbor graph on a subsample and partition it with METIS into $J$ overlapping parts. Each part gets a local intrinsic-dimension estimate, a truncated principal-component basis, and a residual scale. Construction cost is roughly $J$ small eigenproblems instead of one large one. At inference we find the few nearest chart centers and compute projections, which costs $O(J D + |\mathcal{N}| D d)$ per query, independent of the training set size $N$.

The analysis component asks three questions. When does locality matter? We sweep $J$ from the number of classes, which recovers Mahalanobis-like behavior, to thousands. Does the estimated $d_j$ matter? We compare it against $d_j = 0$, which reduces the score to plain distance to a patch center. How should $\lambda$ be chosen without outlier data? Following the out-of-distribution-free proxy idea of the Mahalanobis geometry paper, we test an in-distribution-only rule that selects $\lambda$ where in-distribution risk–coverage begins to degrade. We report both the cost-specified $\lambda$, as in the plug-in formulation, and this proxy.

We also examine subgroup effects. Both the plug-in paper and Towards Better Selective Classification warn that reducing coverage hurts underrepresented groups. A geometric score may either worsen this, by rejecting rare-but-valid regions, or improve it.

Baselines

The naive reference point is predicting everything at full coverage. Next is plain softmax-response thresholding calibrated with the guaranteed-risk procedure. That is the zero-cost default any practitioner would use. On ImageNet it reaches 2% top-5 error at about 60% coverage, and on CIFAR-10 1% error at 78% coverage, as reported in Selective Classification for Deep Neural Networks.

The strongest in-distribution competitor is SAT+EM+SR from Towards Better Selective Classification. This is self-adaptive training with entropy minimization, scored by softmax. The paper reports up to 80% relative improvement on ImageNetSubset, though the file gives no absolute value we can quote. We apply our score on top of SAT+EM features and on top of CCL-SC features, whose reported CIFAR-100 full-coverage error is about 26.5%. Beating these baselines means lower area under the risk–coverage curve at equal or better coverage. On pure in-distribution data, we would also count parity as acceptable, as long as the method wins elsewhere.

The strongest joint-rejection competitor is the black-box plug-in estimator of Plugin estimators for selective classification with out-of-distribution detection. On CIFAR-100 as in-distribution and OpenImages as out-of-distribution, it reports an area under the risk–coverage curve of 0.222, against 0.316 for SIRC and 0.342 for softmax. We run it with its own scores and also with a radially scaled Mahalanobis distance from A Geometry-Based View of Mahalanobis OOD Detection. Its $\beta$ is tuned by that paper's in-distribution-only proxy, which reports a mean regret of 1.27 percentage points against the oracle on near-OOD benchmarks. Beating this baseline means a lower curve area than 0.222 on the same split with the same backbone, plus consistent gains on near-OOD sets such as NINCO and SSB-Hard.

We also include an exact k-nearest-neighbor distance plugged into the same additive rule, computed on randomly projected features with the same backbone. All methods share frozen backbones, the same calibration split, the same guaranteed-risk calibration, and an equal hyperparameter search budget of 20 configurations. Wall-clock latency and memory are reported alongside accuracy.

Two ablations isolate the key ingredient. The first sets $d_j = 0$, which tests whether tangent geometry adds anything beyond patch-center distance. The second sets $J$ equal to the number of classes, which tests whether locality adds anything beyond a class-conditional Gaussian.

Why not just…?

Why not just threshold softmax confidence after good training? On clean in-distribution test sets this is a genuine threat, and we expect little or no gain there. The evidence that it falls short is specific to unfamiliar inputs. The plug-in paper proves softmax can fail arbitrarily in the joint setting and measures 0.342 against 0.222. Our in-distribution experiments are there to show we do not lose ground. The joint benchmarks are where the claim lives.

Why not just use a class-conditional Mahalanobis distance in the plug-in rule? This is the most serious alternative, and our method contains it as the $J = \text{classes}$ case. If the chart-count sweep shows no gain from more charts, then locality is not worth its cost, and the honest conclusion is that the radially scaled Mahalanobis plug-in suffices. We expect gains on fine-grained and multimodal classes, such as StanfordCars, Food101 and ImageNet near-OOD, where a single Gaussian per class is a poor fit. The sweep settles the question directly.

Why not just use nearest-neighbor distance over the training set? Nearest-neighbor distance is likely competitive in accuracy, since local intrinsic dimension estimators are themselves built from neighbor-distance ratios. Its weakness is cost: per-query search and stored features grow with $N$, even after random projection. We will show whether charts keep most of its accuracy at a fixed, small fraction of its latency and memory as $N$ grows from CIFAR scale to full ImageNet. If charts are less accurate at every budget, the proposal fails on this point.

Why not just use dropout sampling or ensembles? These multiply inference cost by the number of passes. The file's evidence already shows softmax matching dropout on ImageNet (Selective Classification for Deep Neural Networks) and SelectiveNet beating it by 26.8% relative risk on CIFAR-10 (SelectiveNet: A Deep Neural Network with an Integrated Reject Option). We include dropout once, for reference.

Proposed Experiments

The in-distribution experiments use CIFAR-10, CIFAR-100, ImageNetSubset, StanfordCars and Food101. We report risk–coverage curves, the area under them, and guaranteed-risk coverage at fixed targets $r^*$.

The joint experiments use CIFAR-100 against OpenImages-O, SVHN, Textures, Places365 and LSUN, and ImageNet against NINCO, SSB-Hard, iNaturalist and OpenImages-O. Backbones include the BiT ResNet-101 used by the plug-in paper. We report the area under the risk–coverage curve under the joint penalty, matching the plug-in protocol. For the subgroup analysis we measure CelebA per-group error and coverage at matched overall coverage.

The decisive checks are threefold. First, on CIFAR-100 against OpenImages, the chart score in the additive rule must beat 0.222 with the same backbone. Second, the chart-count sweep must show a monotone or peaked gain over $J = \text{classes}$ on near-OOD sets, and the $d_j = 0$ ablation must lose to the full method. Third, latency per query must stay flat as the training set grows while nearest-neighbor latency rises, with accuracy within a small margin of nearest-neighbor accuracy. If the first two checks fail, the geometric story is wrong. If only the third fails, the method is a curiosity rather than a scalable tool.