A classifier that may abstain needs a score that ranks inputs by how likely it is to get them wrong. Two very different things make an input risky. It can sit near a class boundary where labels genuinely overlap, or it can sit somewhere the model has barely seen data. Almost every score in use today, such as the maximum softmax probability, mostly measures the first. Large benchmarks show the result: deep selective classifiers stay confident on random noise and novel inputs, and they disproportionately reject minority-class examples (Deep Neural Network Benchmarks for Selective Classification). We propose a different score. Cut the input space into random cells that do not depend on any labels, record how often a fixed base model was wrong on held-out labeled points in each cell, and abstain wherever the upper confidence bound on that local error rate is high. A cell that holds many held-out errors gets a high bound. So does a cell that holds almost no held-out data, because its bound is wide. The score therefore covers both kinds of risk without a separate novelty detector.
The cutting tool is the random projection tree, which recursively splits data along random directions instead of chosen coordinates. Its cells shrink along the low-dimensional surface the data actually lies on, not along the full ambient dimension (Learning the structure of manifolds using random projections; Escaping the Curse of Dimensionality with a Tree-based Regressor). This matters most when the base model's inputs are high-dimensional embeddings, for example a network's penultimate layer. Because the cells are fixed before any held-out label is seen, the count of errors inside a cell is an honest binomial sample, and a textbook confidence bound applies to it.
Core Claim
The method is a post-hoc wrapper for any trained classifier $f$, whether a gradient-boosted tree model or a deep network. It builds an ensemble of $T$ random projection trees on unlabeled training features. Each tree's leaves are populated with a calibration set whose labels $f$ never trained on. For a test input $x$, let $n_t(x)$ be the number of calibration points that share leaf $t$ with $x$, and let $k_t(x)$ be how many of them $f$ misclassified. The abstention score is
$$ u(x) = \frac{1}{T}\sum_{t=1}^{T} \mathrm{UCB}_{\delta}\big(k_t(x), n_t(x)\big), $$
where $\mathrm{UCB}_\delta$ is the one-sided Clopper–Pearson upper bound on a binomial error rate at confidence $1-\delta$. An empty leaf gets the value 1. Averaging over trees smooths the jagged cell boundaries, as in Random Forest Density Estimation and On the Optimality of Probability Estimation by Random Decision Trees.
The global coverage threshold on $u$ is then set on a second held-out split with the Selection with Guaranteed Risk procedure of Selective Classification for Deep Neural Networks. That procedure binary-searches for the threshold whose binomial risk bound meets a user target. The end-to-end guarantee therefore comes from that existing procedure. Our contribution is the ranking score fed into it.
The claim to test has three parts. First, $u$ ranks errors at least as well as the base model's own confidence on in-distribution data. Second, it rejects shifted inputs that confidence scores accept. Third, it reduces minority-class rejection bias. The reason for the third part is that $u$ depends on local error counts, not on how dense each class is.
Relation to Prior Work
The closest prior work treats leaf sample counts in random decision trees as "uncertainty about uncertainty" (Combining Predictions under Uncertainty: The Case of Random Decision Trees). It compares averaging, Laplace smoothing, belief functions and evidence accumulation for combining tree predictions, but it never abstains, never studies risk against coverage, and uses only axis-aligned trees. Its negative findings constrain our design. Laplace smoothing hurt, and evidence accumulation broke down on small leaves. We therefore use an explicit count-aware bound rather than smoothed posteriors, and we average bounds across trees rather than multiplying evidence.
Half-space trees (Fast Anomaly Detection for Streaming Data) and random forest density estimation (Random Forest Density Estimation) use label-free random cells to measure how much data a region holds, for anomaly detection. They have no predictor to protect and no notion of selective risk. We reuse their label-free construction, but our cells count a base model's errors, not raw data mass.
Epistemic Reject Option Prediction argues that rejection should target the gap to the best possible predictor rather than total noise, but it is demonstrated only on a synthetic one-dimensional regression task. Our score is a different operational compromise. It does not separate the two uncertainties. It deliberately merges them into a single local risk bound, and the experiments measure whether that merge helps.
SelectiveNet learns a selection head, but it must be retrained for each target coverage. Our score works at every coverage level and needs no retraining.
Research Program
We will build the wrapper with both kinds of split from the original random projection tree work: hyperplane splits at the median plus random jitter, as in the max variant of Random Projection Trees Revisited, and distance-from-mean splits. Depth is controlled by a minimum expected number of calibration points per leaf, which replaces the fragile depth parameter that Random Forest Density Estimation found its estimator sensitive to.
On the analysis side, we will show that the score is valid cell by cell. Conditional on the partition, calibration points in a cell are exchangeable draws from the base model's error distribution restricted to that cell. We will then relate how fast cells shrink, using the bounds of Random Projection Trees Revisited, to how fast $u$ converges to the true local error rate as a function of intrinsic dimension.
Two extensions are secondary and are pursued only if the main results hold. One stratifies counts by predicted class, to test directly whether this removes rejection bias. The other updates leaf counts in a stream in constant time per point, in the manner of half-space trees, to track drift.
Baselines
The naive reference point is the base model's own confidence. For deep networks this is the maximum softmax probability. For tree ensembles it is the averaged predicted-class probability. In both cases the threshold is set by the same guaranteed-risk procedure on the same split. This is what practitioners actually do. Selective Classification for Deep Neural Networks reports that softmax response with this procedure reaches 1% error at 78% coverage on CIFAR-10. Beating this baseline means a lower area under the risk–coverage curve on in-distribution data, or equal area with clearly lower acceptance of shifted inputs.
The strongest existing method is a deep ensemble scored by softmax response. Deep Neural Network Benchmarks for Selective Classification found it the most consistent winner across its 44 datasets, reporting a relative multiclass error of about 0.117. We will run five members on the same training data with the benchmark's tuning protocol, and we will apply our wrapper on top of both a single model and the ensemble. Matching the ensemble while wrapping a single model would already be useful, given the ensemble's training and inference cost. Improving on the ensemble's acceptance of shifted inputs and its minority-class coverage is the result that would matter most. For tree-based selective classifiers on tabular data we found no reported result on Lacuna, so gradient-boosted trees with probability thresholding serve as that reference.
Three ablations isolate the key ingredients. The first replaces random projection trees with axis-aligned random trees, which tests whether adapting to intrinsic dimension matters. The second replaces the confidence bound with the raw cell error rate, which tests whether count-awareness is what drives rejection of shifted inputs. The third builds the partition from the training labels instead of without them, which tests whether label-free honesty matters. All variants share the same calibration data, the same number of trees and the same tuning budget, with the minimum leaf size chosen on a validation split.
Why not just…?
Why not just pair softmax response with a separate novelty detector such as random forest density estimation or Isolation Forest? This is a genuine threat. On the ODDS outlier suite, random forest density estimation reached a rank-sum of 55 against 72 for Isolation Forest (Random Forest Density Estimation), so strong detectors exist. But two separate scores need a combination rule and two thresholds. A density gate also rejects sparse regions where the model happens to be accurate, which costs coverage. We will run softmax-plus-density gating with its combination weight tuned on validation data. If it matches our score both in distribution and under shift, the proposal reduces to "use density gating," and we will report that outcome.
Why not just estimate local accuracy with k-nearest neighbors in the same feature space? This is the most serious competitor. Nearest-neighbor methods also adapt to intrinsic dimension, and a nearest-neighbor error rate is a close cousin of our score. The differences we expect are three. Fixed cells give exact binomial bounds, whereas data-dependent neighborhoods do not. Query cost is logarithmic in the dataset rather than a full search. And counts can be updated in a stream. Whether any of this improves ranking is an empirical question. We will run k-nearest-neighbor local error, with and without a count-aware bound, at matched neighborhood size. A tie on ranking would leave the method's case resting on cost and validity alone.
Why not just train a model to predict the base model's errors, ConfidNet-style or with a gradient-boosted regressor on correctness? A learned error predictor inherits the same overconfidence on unfamiliar inputs that motivates this work, since it extrapolates beyond its data like any learned model. The benchmark of Deep Neural Network Benchmarks for Selective Classification found auxiliary-network methods no better on shifted inputs. We will train a gradient-boosted correctness predictor on the same calibration labels. The shifted-input acceptance rate is the measurement that separates it from our score.
Proposed Experiments
On tabular data, we use the 24 tabular datasets of the Deep Neural Network Benchmarks for Selective Classification suite, plus UCI Adult, the KDD Cup '98 donation data and credit card fraud for skewed classes, and Covertype. The base models are gradient-boosted trees and the benchmark's neural network. On images, we use CIFAR-10 with fixed network embeddings, with SVHN as the shifted set, and ImageNet embeddings with the graded severity levels of A framework for benchmarking Class-out-of-distribution detection and its application to ImageNet. The image setting is the regime where random projections should matter, because the ambient dimension is high and the intrinsic dimension is presumably low.
The metrics are area under the risk–coverage curve, selective error at 80% coverage, coverage achieved at a guaranteed risk target together with the empirical rate of guarantee violations, the fraction of shifted or noise inputs accepted, and the ratio of minority-class coverage to majority-class coverage.
Three checks are decisive. The first is the shifted-input acceptance rate against softmax response and the deep ensemble. If our score does not lower it substantially, the central claim fails. The second is the comparison with k-nearest-neighbor local error at matched cost. The third is the comparison of random projection trees with axis-aligned trees on high-dimensional embeddings against low-dimensional tabular data. The random-projection advantage should appear in the embeddings and fade on tabular data, as the intrinsic-dimension theory predicts. If it appears equally in both settings or in neither, the geometric explanation is wrong.
References
- Deep Neural Network Benchmarks for Selective Classification
- Learning the structure of manifolds using random projections
- Escaping the Curse of Dimensionality with a Tree-based Regressor
- Random Forest Density Estimation
- On the Optimality of Probability Estimation by Random Decision Trees
- Selective Classification for Deep Neural Networks
- Combining Predictions Under Uncertainty: The Case of Random Decision Trees
- Fast Anomaly Detection for Streaming Data
- Epistemic Reject Option Prediction
- SelectiveNet: A Deep Neural Network with an Integrated Reject Option
- Random Projection Trees Revisited
- A framework for benchmarking Class-out-of-distribution detection and its application to ImageNet