A classifier that may abstain ("selective prediction") needs a rule for which inputs to answer and which to hand to a human. Current rules score each test input on its own. The rule might use the model's confidence, the gap between its top two outputs, or how close the input's internal features lie to training examples the model got right. Under distribution shift, test inputs do not move one at a time. A batch of fogged or cartoon-style images drifts together into the same region of feature space. A per-input nearest-neighbor score can then keep calling them "close to correct examples," because many shifted inputs can all lean on the same few training neighbors. We propose instead to decide abstention for a whole incoming batch at once. The decision is posed as an optimal transport problem: a way of matching one cloud of points to another at minimum total distance, here with limited capacity on each target. Each calibration example the model classified correctly can "vouch for" only a bounded amount of test mass. Test points that cannot be matched cheaply under that budget are rejected.
The obstacle is cost. Exact transport between a test batch of size $B$ and an ImageNet-scale calibration pool of size $n$ (50,000 points) is out of reach for standard linear programming. Fast approximations such as entropic smoothing, extragradient solvers, and one-dimensional slicing each blur the geometry in a different way. This project therefore asks two linked questions. Does capacity-limited transport reduce selective risk under shift beyond the best per-point selectors? Which fast solver keeps that benefit at deployment cost?
Core Claim
Our claim is that the capacity constraint is the useful ingredient, not optimal transport as such. Consider a nearest-neighbor selector that lets every calibration point serve unlimited test points. It cannot tell "this test input resembles a correct example" apart from "a thousand test inputs all resemble the same correct example." The second situation is the signature of collective drift.
Concretely, let $z_1,\dots,z_B$ be penultimate-layer features of a test batch, each with mass $1/B$. Let $x_1,\dots,x_n$ be features of calibration points pooled into a "correct" set and a "wrong" set according to whether the model classified them correctly, with weights $v_j$ summing to one. Let $C_{ij}$ be the squared distance between normalized features plus a penalty $\lambda$ when the predicted class of $z_i$ differs from the label of $x_j$. We solve
$$\min_{\gamma \ge 0} \langle \gamma, C\rangle \quad \text{s.t.}\quad \gamma \mathbf{1} \le \tfrac{1}{B}\mathbf{1},\;\; \gamma^\top \mathbf{1} \le \kappa\, v,\;\; \mathbf{1}^\top \gamma \mathbf{1} = m,$$
where $\gamma_{ij}$ is the mass sent from test point $i$ to calibration point $j$, $m \le 1$ is the total mass transported, and $\kappa \ge 1$ caps how much mass each calibration point may absorb relative to its share. A test point's acceptance score is the fraction of its mass that lands on correct-pool calibration points. Mass that is sent to the wrong pool, or that cannot be transported at all, counts against acceptance.
As $\kappa \to \infty$ the problem decouples into a per-point nearest-match rule, close in spirit to the $\Delta$-KNN selector. The single knob $\kappa$ therefore isolates exactly what is new. At finite $\kappa$, the implied acceptance tracks a ratio between the density of correct calibration features and the density of the test batch, which is the batch-level analogue of the Neyman–Pearson likelihood ratio.
Relation to Prior Work
Two papers motivate the gap. Know When to Abstain: Optimal Selective Classification with Likelihood Ratios derives the optimal selector as a likelihood ratio between correct and wrong feature densities. It approximates that ratio per point with $\Delta$-MDS (Mahalanobis distance differences) and $\Delta$-KNN (nearest-neighbor distance differences), reporting roughly a 50% reduction in average selective risk on shifted ImageNet variants. We keep its correct-versus-wrong structure but add a coupling across test points, which no per-point method has. Selective Classification Under Distribution Shifts shows that softmax scores are scale-fragile and that logit margins are more robust across covariate and label shift. We use its margin score as a component and its benchmark suite as our testbed.
The closest optimal-transport work plays a different role. Multidimensional Uncertainty Quantification via Optimal Transport (VecUQ-OT) maps vectors of precomputed scalar uncertainty scores onto a reference distribution with Sinkhorn and ranks test points by Monge–Kantorovich rank, a multivariate analogue of a quantile. It transports between scores and a fixed reference using calibration data alone. Its ranking does not depend on the test batch, so it has no mechanism that reacts to collective drift. We transport test-batch features onto labeled calibration features. Optimal transport-based conformal prediction and Neural Optimal Transport Meets Multivariate Conformal Prediction use transport-based ranks to build multivariate prediction sets for regression and classification. The first reports roughly $O(n^3)$ calibration cost and leaves entropic scaling untested. The second amortizes the transport map with input-convex networks but evaluates only continuous regression. Neither produces a binary abstention rule, and both constrain us by documenting the cost wall. Detecting OOD Samples via Optimal Transport Scoring Function uses Wasserstein distances to class means for out-of-distribution detection. The likelihood-ratio paper argues that pure out-of-distribution scores reject correct boundary samples, which is why our cost function separates correct from wrong calibration mass rather than measuring distance to the data alone.
The solver side supplies methods. Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods gives an $O(N^2/\epsilon)$ first-order solver, against $O(N^2/\epsilon^2)$ for Sinkhorn, where $\epsilon$ is the target accuracy. Sliced Optimal Partial Transport solves partial transport on random one-dimensional projections, with quadratic worst-case cost but near-linear behavior in practice. Partial transport is what allows mass to go unmatched, so it fits abstention directly.
Research Program
We will build the selector in three solver variants. The first is an exact linear-programming reference, usable only for small $B$ and $n$. The second is an entropic partial-transport solver run with both Sinkhorn and extragradient updates, streaming the cost matrix in blocks so that memory stays linear. The third applies sliced partial transport after projecting features to their leading principal components, since random one-dimensional slices of raw 768–1024-dimensional features may destroy neighborhood structure.
To produce a full risk–coverage curve without re-solving for every coverage level, we solve once at a moderate $m$. We then use the resulting row mass, or the test-side dual potential, as a continuous score. We also test a hybrid that adds the logit margin, mirroring $\Delta$-KNN-RLog. In deployment the batch is a sliding window of recent test inputs, so each point is scored alongside its neighbors in time.
The analysis has two parts. First, we characterize when the capacity constraint helps: under collective covariate drift. We also characterize when it should hurt: under pure label shift, where a clean batch dominated by one class will exceed that class's calibration capacity and get wrongly rejected. For the second case we test class-wise capacities set from the batch's predicted-class histogram. Second, we map accuracy against cost. For each solver we trace AURC (area under the risk–coverage curve) against wall-clock time and peak memory as $\epsilon$, slice count, and $B$ vary. The aim is to find where entropic blur erases the capacity effect. We expect large $\epsilon$ to spread every test point's mass uniformly across the calibration set and drive scores toward uninformative values.
We do not claim a finite-sample risk guarantee under shift; no label-free method has one. On in-distribution data, the score at fixed $(\kappa, m, B)$ is a fixed function. Its threshold can therefore be calibrated with the binomial bound of Selective Classification for Deep Neural Networks, and we report whether that bound still holds empirically on shifted sets.
Baselines
The naive reference point is maximum softmax probability, the model's top predicted probability, thresholded on ImageNet validation. On clean CIFAR-10 it reaches "1% error rate while maintaining 78% coverage" (Selective Classification for Deep Neural Networks). It costs nothing, and any method that fails to beat it under shift is not worth deploying.
The strongest single-score competitor is the confidence margin $RL_{conf}$-M from Selective Classification Under Distribution Shifts. That paper reports the best overall performance when all shift types are present, though no absolute AURC value is reported on Lacuna.
The strongest existing method is $\Delta$-KNN-RLog for CLIP and $\Delta$-MDS-RLog for EVA, from Know When to Abstain: Optimal Selective Classification with Likelihood Ratios. The only quantitative statement on Lacuna is the "roughly 50% reduction in average Selective Risk (measured by AURC and NAURC)" over standard distance methods; no reported absolute AURC was found on Lacuna for $\Delta$-KNN-RLog. We will therefore reproduce it ourselves with the same CLIP and EVA backbones, the same calibration features, and the same correct/wrong split. Its $k$ and mixing weight get the same tuning budget, on the same held-out clean split, as our $\kappa$, $\lambda$, $m$, and $\epsilon$.
VecUQ-OT is the closest transport-based selector. On CIFAR-10 versus SVHN it reports ROC-AUC 0.957 for out-of-distribution detection, but no reported selective-risk number was found on Lacuna. We run it on the same score vectors.
The key ablation is our own selector with $\kappa \to \infty$, which removes the capacity constraint and leaves everything else fixed. Beating the baselines means a lower AURC than $\Delta$-KNN-RLog on the aggregate of shifted ImageNet sets, at a per-batch cost below the time of the classifier's own forward pass, with the $\kappa \to \infty$ ablation recovering most of the gap.
Why not just…?
Why not just use $\Delta$-KNN-RLog, which already captures feature-space density? It treats each test point independently, so a crowd of shifted points sharing one correct neighbor all look safe. That is precisely the failure we target. The threat is real: if collective drift rarely makes many test points share neighbors in practice, our method collapses to $\Delta$-KNN at greater cost. The $\kappa$ sweep settles this directly. If AURC is flat in $\kappa$, the idea fails.
Why not just estimate the test-to-calibration density ratio with a domain classifier and reweight $\Delta$-KNN? This is the most serious alternative. A logistic classifier trained to separate the test batch from calibration features yields density-ratio weights cheaply, and capacity-limited transport is arguably a geometric estimator of the same quantity. We include this transductive baseline with identical batches. Our method is justified only if it beats this baseline at small batch sizes, where classifier-based ratios are noisy, or on mixed clean-and-corrupted batches. If the domain-classifier variant matches it everywhere, we will report that and recommend the cheaper method.
Why not just subsample the calibration set so exact transport becomes affordable? Subsampling cuts cost but lowers the resolution of the correct/wrong split, and so the precision of the capacity budget. The paper we build on reports that $\Delta$-KNN stays strong with "only 0.1% of labeled training data", which suggests subsampling could be harmless. We test it as a fourth solver path: exact transport on random calibration subsets of 1k–10k points, placed on the same AURC–versus–time plot.
Proposed Experiments
The testbed uses ImageNet-1K validation features from CLIP and EVA as the calibration pool. Evaluation covers ImageNet-C at all five severities (Benchmarking Neural Network Robustness to Common Corruptions and Perturbations), ImageNet-R (The Many Faces of Robustness: A Critical Analysis of Out-of-Distribution Generalization), ImageNet-A, ObjectNet, and OpenImage-O. CIFAR-10-C provides a smaller setting, and iWildCam and Amazon provide natural shift. These follow the protocols of the two selective-classification-under-shift papers. Metrics are AURC, normalized AURC, and selective risk at 80% coverage, each reported alongside solver wall-clock time and peak memory per batch.
Batches are constructed in three regimes. Pure batches contain a single shift. Mixed batches combine clean and corrupted inputs in proportions from 10% to 90% corrupted. Label-shifted clean batches are dominated by a few classes. Batch sizes range from 64 to 8,192.
Four results decide the question. First, on mixed batches the gain over $\Delta$-KNN-RLog must grow with the corrupted fraction and vanish as $\kappa \to \infty$; this pattern would confirm the mechanism. Second, on label-shifted clean batches, plain capacity transport should lose to $\Delta$-KNN, and class-wise capacities should remove that loss; if they do not, the method is unsafe for deployment. Third, the selector must beat the domain-classifier reweighting baseline at batch sizes of 512 or fewer. Fourth, on the cost–accuracy frontier, at least one fast solver, which we expect to be extragradient or principal-component-sliced partial transport, must keep at least 80% of the exact solver's AURC gain over $\Delta$-KNN-RLog, measured on subsets where the exact solver can still run, while staying below the backbone's forward-pass time. Failing that last check would mean the computational cost of transport, not its statistics, is what keeps it out of selective prediction.
References
- Know When to Abstain: Optimal Selective Classification with Likelihood Ratios
- Selective Classification Under Distribution Shifts
- Multidimensional Uncertainty Quantification via Optimal Transport
- Optimal transport-based conformal prediction
- Neural Optimal Transport Meets Multivariate Conformal Prediction
- Detecting OOD Samples via Optimal Transport Scoring Function
- Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods
- Sliced Optimal Partial Transport
- Selective Classification for Deep Neural Networks
- Benchmarking Neural Network Robustness to Common Corruptions and Perturbations
- The Many Faces of Robustness: A Critical Analysis of Out-of-Distribution Generalization