A selective predictor is a model that may say "I don't know" and hand a case to a human. It is normally judged by two numbers: coverage, the fraction of cases it answers, and selective risk, its error rate on those cases. Existing guarantees control that error rate averaged over the whole population. On heterogeneous data, such as transplant cohorts, census records, or clinical images, that average can hide subpopulations where accepted predictions are much worse than promised. Partitioning methods already show that such pockets exist and that local models fix much of the problem, but they set their confidence cutoffs by eye.
We propose a method that learns a tree of regions from data, fits a local predictor at each node, and then uses a held-out set to certify, for every region at once, that the error rate on accepted cases stays below a target. Each region is reported at the finest level its calibration data can support. The core claim is that this keeps the overall coverage of a single-threshold system while removing hidden failure regions. It needs no demographic or group labels, and its guarantee is region-wise rather than only population-wide.
Core Claim
Write $f_v$ for the predictor at tree node $v$, $s_v(x)$ for its confidence score, $\tau_v$ for an acceptance threshold, and $R_v$ for the set of inputs that fall in node $v$. For a target risk $r^*$ and failure probability $\delta$, the method returns a pruned tree whose leaves partition the input space and which satisfies
$$\mathbb{P}\Big(\forall v \in \text{leaves}: \ \mathbb{E}\big[\ell(f_v(X),Y) \mid X \in R_v,\ s_v(X)\ge \tau_v\big] \le r^*\Big) \ge 1-\delta,$$
where $\ell$ is the task loss.
This is the binomial-inversion guarantee of Selection with Guaranteed Risk from Selective Classification for Deep Neural Networks (that paper certifies one global threshold over a held-out set), lifted to a whole family of regions. The lift is simple and valid. The full candidate tree, with $M$ nodes, is fixed before calibration. Each node is certified at level $\delta/M$, so all node certificates hold at the same time. Because of that, any choice of which nodes become leaves can be made after looking at calibration data without breaking the guarantee.
The cost of this design is explicit. The certified slack at a node shrinks roughly like $\sqrt{\log(M/\delta)/n_v}$, the standard concentration rate for a binomial proportion, where $n_v$ is the number of calibration points in the node. Deep, small regions therefore cannot be certified tightly. Pruning resolves this by letting a subtree keep its children only when the children's combined certified coverage beats the parent's.
Why This Is Not Already Done
The intersection already has several pieces, and each misses one ingredient.
Some work localizes but gives no guarantee. ConfidentMatch, in Personalized Donor-Recipient Matching for Organ Transplantation, splits donor–recipient features into hypercubes, picks a learner per cube, and targets 95% accuracy on as many patients as possible. Its cutoffs are empirical and carry no finite-sample risk bound. The Dynamic Classification Algorithm in Dynamic Classification culls local regression outputs that fall outside their assigned target band, which is a hard heuristic rule. Robust SCOAL in Mining for the most certain predictions from dyadic data ranks predictions by co-cluster coherence, but only works on user–item style matrices and also lacks guarantees. All three supply motivating evidence that local models plus abstention raise coverage. We reuse their architectural idea and replace their cutoffs with certificates.
Other work guarantees fairness but needs labels or a different output. Fair Selective Classification Via Sufficiency proves that a single global threshold magnifies disparities between groups, and repairs this with group-specific sub-models and a calibration regularizer. That repair requires the group attribute to be known. This paper is our main motivation, and it is also our reference for what is achievable when groups are known. Adaptive Conformal Prediction via Mixture-of-Experts Gating Similarity and Conformal Prediction Adaptive to Unknown Subpopulation Shifts handle latent subpopulations by reweighting calibration points by similarity. However, they output prediction sets with coverage guarantees, not a predict-or-defer rule with a risk bound. Act or Defer (STRATCP) builds such a rule for EHR foundation models, but stratifies by class around a frozen global model. When that model is bad on a subpopulation, STRATCP can only defer the whole subpopulation.
Our method differs from all of these in the same way. It learns the regions, it lets the predictor change per region, and it certifies risk inside each reported region rather than only on average.
Research Program
The system has three stages, run on three disjoint data splits.
The first stage grows a candidate tree on the training split. Splits are not chosen to make labels or features more uniform. Instead they are chosen to maximize the gap in selective risk between the two children, measured at the target coverage using cross-fitted residuals of a global model. In other words, the tree looks for places where errors concentrate. The split search follows the joint search over splits and local learners in ToPs: Ensemble Learning with Trees of Predictors, with the splitting objective changed.
Each node's predictor is warm-started from its parent and chosen from a small library of learners, namely logistic regression, gradient-boosted trees, and a small multilayer network. This parent-to-child sharing is our answer to the fragmentation problem the file flags for hypercube methods, where small regions leave too few samples to train on.
The second stage, on the calibration split, computes a certified threshold at every node. The confidence score is a scale-invariant margin, following the finding in Selective Classification Under Distribution Shifts that raw softmax scores fail under shift. Each node is certified at level $\delta/M$.
The third stage prunes bottom-up, keeping whichever level yields higher certified coverage. Abstained cases are reported together with the region they came from, which tells a reviewer where the model is weak.
On the theory side we will state and prove the simultaneous guarantee above. We will also characterize the coverage loss compared with an oracle that knows the true subgroups, as a function of $n_v$ and $M$. This tells practitioners how much calibration data a given tree depth needs.
Baselines
The naive reference point is a single global model, gradient-boosted trees for tabular data and a fine-tuned backbone or frozen embeddings for images and text. It uses softmax response with one SGR threshold, as in Selective Classification for Deep Neural Networks. That paper reports a 1% error rate at 78% coverage on CIFAR-10, which shows how strong the global approach is when the data are homogeneous. It is the natural baseline because it is what practitioners deploy. Beating it means equal or better overall certified coverage at the same $r^*$, together with a clearly lower worst-region and worst-known-group selective risk.
The strongest localized competitor on transplant data is ConfidentMatch. Yoon et al. report that it "can provide predictions of success with 95% confidence for 5,489 patients of a total population of 9,620 patients," which is 410 more than DeepBoost. Matching that coverage is not enough, because ConfidentMatch's 95% is empirical. To beat it, we must match or exceed its covered fraction on the UNOS heart data while our 95% holds as a certified bound. We must also show, on bootstrap resamples, how often ConfidentMatch's empirical cutoff actually breaks its 95% target on the held-out set.
The strongest fairness competitor is the sufficiency regularizer of Jones et al.. On Adult, it cuts the area between group precision curves from 0.220 to 0.021, at a cost in overall accuracy from 0.931 to 0.887. Because it uses group labels and we do not, it serves as an upper reference rather than a target to dominate. Our method sees no sex labels. Success means substantially closing the 0.220 gap, with the gap computed afterwards using the held-out sex attribute, while losing less overall accuracy than the regularizer does.
On EHRSHOT with the CLMBR-T-base backbone, we run STRATCP from Act or Defer at matched false-action budgets. That paper reports nearly 2.5x more patients selected than standard conformal prediction on short length of stay. We ask whether letting local predictors change per region selects more patients than a wrapper around a frozen model.
We also run two more competitors: SelectiveNet from SelectiveNet, and MoE-CP turned into an abstention rule by deferring whenever the prediction set holds more than one label. Every method gets the same three-way split, the same calibration size, and the same hyperparameter search budget, set by wall-clock time.
Three ablations isolate the ingredients. The first keeps the learned tree but uses the global model at every node, which turns off local experts. The second swaps the error-driven splits for K-means clusters on the same features, and also for random splits. The third replaces pruning with a fixed depth.
Why not just…?
Why not just use one global model with one certified threshold? That approach gives a valid marginal guarantee. However, Jones et al. show that on CheXpert, worst-group precision falls as the model becomes more selective. QReg also reports that in subspaces where a non-global model wins, the global choice can be several times, and in extreme cases over 1000x, worse. Our main experiment measures exactly this: certified overall coverage against worst-region risk, side by side.
Why not just cluster with K-means and certify a threshold per cluster? This is a serious option and we treat it as the main ablation. Two pieces of evidence argue against it. The file notes that distance-based clustering in high dimensions is dominated by noise features, as observed in Multi-view predictive partitioning in high dimensions and MoE-CP. In addition, DCA reports that K-means-based localization failed to remove missed detections. Even so, per-cluster certification would inherit most of our guarantee for free. If K-means regions match error-driven regions on worst-known-group risk, we will report that the contribution is the certificate and the pruning rule, not the partitioning.
Why not keep the global model and only make the threshold region-specific? This is the biggest threat. Much of the disparity problem may come from thresholds rather than from the predictor itself. Ablation one settles the question directly. Local experts must earn their place through extra certified coverage at fixed $r^*$, which should show up most where QReg-style local opportunity loss is large. If they do not earn it, the proposal shrinks to the simpler method, which still delivers region-wise certificates without group labels.
Why not use mixture-of-experts gating entropy, or MoE-CP, to decide when to abstain? Gating networks are trained to route inputs, not to predict errors, and MoE-CP's own framing treats gating outputs as subpopulation signatures rather than risk estimates. MoE-CP's sets carry a coverage guarantee, but not a bound on the risk of the cases it accepts. Running it as an abstention rule under identical splits will show whether that difference matters in practice.
Proposed Experiments
The tabular core uses three datasets. The first is the UNOS heart transplant data (56,716 patients, 70 features) for 3-year survival. The second is Adult, with sex hidden from training and used only in evaluation. The third is Concrete Compressive Strength for regression, with squared-error risk.
The representation track uses CelebA, Civil Comments, and CheXpert with frozen embeddings. The demographic or device attribute is withheld from the method and used only for evaluation. The clinical track uses EHRSHOT.
The metrics are four. Certified coverage at $r^* \in \{0.02, 0.05, 0.10\}$ with $\delta = 0.05$. Worst-region and worst-known-group selective risk on the test split. Area between group precision curves. And the empirical violation rate of every method's claimed risk over 200 resampled calibration and test splits.
Two checks decide the outcome. First, on Adult and CheXpert, the method must lower worst-known-group selective risk relative to the global SGR baseline without losing more than a small, pre-registered amount of overall coverage. Second, on UNOS, it must reach coverage comparable to ConfidentMatch's 5,489 of 9,620 with a violation rate at or below $\delta$, where ConfidentMatch's own violation rate is reported for comparison. If the tree collapses to the root on most datasets because calibration data cannot support certified children, that is a clean negative result. It would mean that region-wise certification needs more calibration data than these benchmarks provide, and the $n_v$ analysis will say how much more.
References
- Selective Classification for Deep Neural Networks
- Personalized Donor-Recipient Matching for Organ Transplantation
- Dynamic Classification: Leveraging Self-Supervised Classification to Enhance Prediction Performance
- Mining for the most certain predictions from dyadic data
- Fair Selective Classification Via Sufficiency
- Adaptive Conformal Prediction via Mixture-of-Experts Gating Similarity
- Conformal Prediction Adaptive to Unknown Subpopulation Shifts
- Act or Defer: Error-Controlled Decision Policies for EHR Foundation Models
- ToPs: Ensemble Learning With Trees of Predictors
- Selective Classification Under Distribution Shifts
- SelectiveNet: A Deep Neural Network with an Integrated Reject Option
- Query-Centric Regression for In-DBMS Analytics
- Multi-view predictive partitioning in high dimensions