Selection-Safe Conformal Early Exit: Distribution-Free Coverage under Adaptive Depth
Abstract
Calibrating a conformal prediction set at each early exit does not preserve coverage once a data-dependent exit is selected. We construct one terminal path score from prefix maxima, calibrate a single split-conformal quantile, and return nested prefix sets that all contain the valid terminal set. The guarantee is selection-safe without an alpha/L correction and holds simultaneously for every post-calibration label-free stopping policy that preserves terminal-set containment. We also bound the efficiency cost of the path maximum by the empirical tail of the early-over-terminal score excess. Across eight encoder task-backbone cells, pathwise selection attains macro coverage 0.901 versus 0.814 for naive layerwise selection, with average set size 1.41 and latency fraction 0.71. On CIFAR-100 with a 24-exit ViT-L/16 (n_cal=500), first-eligible stopping at budget b=4 attains coverage 0.902, set size 2.76, and latency fraction 0.57, and the same calibration supports deployment-time budget changes without refitting. In a joint exit-count/calibration-size sweep at n=100, pathwise set size moves only from 3.02 to 3.11 as exits increase from 4 to 24, while Bonferroni degenerates to the full label space for 12 or more exits. Paired comparison against MinSE valid selection at (n,L)=(100,24) gives a set-size difference of 0.80 [0.47, 1.13]. Full-vocabulary decoder experiments remain a negative boundary, with sets of 7,162-9,620 tokens. Pathwise calibration is most useful when candidate exits are many relative to calibration size, when budgets change after calibration, and when shallow heads return actionable sets.
Related
- Sequential Confidence Sets for Coverage-Constrained Conformal Model Selection
- Adaptive Conformal Inference Under Delayed Feedback: Coverage Guarantees and a Delay-to-Memory Diagnostic
- Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing
- Conformal Prediction and Conditional Coverage for Tabular Foundation Models
- Conformal Coverage of Time Series: Validity and Inference
BibTeX
@misc{habib2026selectionsafe,
title = {{Selection-Safe Conformal Early Exit: Distribution-Free Coverage under Adaptive Depth}},
author = {Adria Binte Habib and Ibne Farabi Shihab},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20773},
eprint = {2610.20773},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20773},
}
RIS
TY - UNPB
TI - Selection-Safe Conformal Early Exit: Distribution-Free Coverage under Adaptive Depth
AU - Adria Binte Habib
AU - Ibne Farabi Shihab
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20773
UR - https://arxiv.org/abs/2610.20773
AB - Calibrating a conformal prediction set at each early exit does not preserve coverage once a data-dependent exit is selected. We construct one terminal path score from prefix maxima, calibrate a single split-conformal quantile, and return nested prefix sets that all contain the valid terminal set. The guarantee is selection-safe without an alpha/L correction and holds simultaneously for every post-calibration label-free stopping policy that preserves terminal-set containment. We also bound the efficiency cost of the path maximum by the empirical tail of the early-over-terminal score excess. Across eight encoder task-backbone cells, pathwise selection attains macro coverage 0.901 versus 0.814 for naive layerwise selection, with average set size 1.41 and latency fraction 0.71. On CIFAR-100 with a 24-exit ViT-L/16 (n_cal=500), first-eligible stopping at budget b=4 attains coverage 0.902, set size 2.76, and latency fraction 0.57, and the same calibration supports deployment-time budget changes without refitting. In a joint exit-count/calibration-size sweep at n=100, pathwise set size moves only from 3.02 to 3.11 as exits increase from 4 to 24, while Bonferroni degenerates to the full label space for 12 or more exits. Paired comparison against MinSE valid selection at (n,L)=(100,24) gives a set-size difference of 0.80 [0.47, 1.13]. Full-vocabulary decoder experiments remain a negative boundary, with sets of 7,162-9,620 tokens. Pathwise calibration is most useful when candidate exits are many relative to calibration size, when budgets change after calibration, and when shallow heads return actionable sets.
ER -