Selection-Safe Conformal Early Exit: Distribution-Free Coverage under Adaptive Depth

1 INTRODUCTION

• L individually valid exits can yield only 1−Lα coverage under an earliest-singleton rule, so fixed-layer validity does not generally survive data-dependent selection.The rule selects using the input and observed sets.Source: §1 · p. 2
• One terminal-score quantile yields nested prefix sets that contain the valid terminal set, so adaptive stopping cannot reduce its coverage.The construction avoids a layerwise union bound.Source: §1 · p. 2
• The guarantee protects true-label coverage of the returned set, not agreement with a full-depth prediction, and weak shallow scores can erase computational gains.The practical question is whether the guarantee remains useful at matched coverage and measured latency.Source: §1 · p. 2
• Unlike related methods targeting stability approximations, supervised loss, or language-model degradation, this work gives an exact split-conformal construction for adaptively selected depth.It uses ordered-path pointwise containment rather than a general stability correction.Source: §1 · p. 2
• The paper also gives an efficiency theorem tied to the tail of early-over-terminal score excess and permits post-calibration policy changes when terminal-set containment is preserved.Its experiments examine scaling with candidate exits and deployment-time policy changes.Source: §1 · p. 2

2 RELATED WORK

• Conformal prediction builds finite-sample marginal sets, while APS, RAPS, and least-ambiguous classifiers target smaller classification sets; full feature-conditional validity is impossible without assumptions.Other approaches protect specified partitions or shift models.Source: §2 · p. 2
• General post-selection methods address collections of predictors, whereas this setting exploits ordered depth and terminal-set containment; related risk-control methods target broader losses.The paper also distinguishes returned-set coverage from agreement or supervised risk as separate estimands.Source: §2 · pp. 2–3
• Conditional and adaptive computation allocate different work across inputs, and early-exit architectures apply this principle in vision and language.Examples include vision and language architectures.Source: §2 · p. 3
• Existing early-exit methods use confidence, distillation, patience, or model agreement; EENN-AVCS and Fast-yet-Safe are the closest uncertainty-aware methods.PAC-Bayesian analysis addresses adaptive-depth generalization rather than post-selection coverage.Source: §2 · p. 3
• Selective classification controls when to return a point prediction, while conformal methods also cover text classification, multiple-choice answering, and open-ended generation.Source: §2 · p. 3
• Cascaded conformal inference reduces candidate-evaluation cost across models, whereas this paper allocates resources across the depth of one model.Coverage may fail if a model changes after calibration, so the backbones, heads, scores, and schedules are frozen beforehand.Source: §2 · p. 3

3.1 SETUP AND THE SELECTION FAILURE

• L individually valid exits can produce coverage 1−Lα under an earliest-singleton rule, while several proposed repairs either accumulate miss events, protect a stronger event, or reuse calibration labels.The setup assumes calibration examples are exchangeable with a new test pair conditional on everything fixed before calibration.Source: §3.1 · p. 3

3.2 ONE CONFORMAL RANK FOR THE PATH

• The method calibrates a terminal score formed from prefix maxima and returns nested sets using one order statistic; any label-free rule returning a superset of the terminal set has marginal coverage at least 1−α.The proof uses exchangeability of terminal calibration and test scores plus pointwise nesting, not independence across exits or a layerwise union bound.Source: §3.2 · pp. 3–4
• The efficiency bound links threshold and set-size inflation to calibration examples with material early-over-terminal score excess and candidate scores near the induced threshold band.The smallest admissible empirical excess threshold is t⋆, defined by mt ≤ n−k.Source: §3.2 · p. 4

3.3 EXTENSIONS BEYOND MARGINAL COVERAGE

• The terminal-score construction also supports training-conditional floors, fixed-group Mondrian calibration under group-prior shift, and a point/set hybrid, but these require assumptions beyond the main marginal guarantee.Source: §3.3 · p. 5

3.4 COMPUTATION AND DEPLOYMENT

• After calibration, cardinality budgets and other label-free stopping logic may change without refitting if the terminal set and its containment relation remain unchanged.Changing scores, transformations, the model, or the exit schedule requires fresh calibration; deployment adds O(K) operations and state per classification exit.Source: §3.4 · p. 5

4.1 MATCHED EVALUATION PROTOCOL

• The matched protocol spans eight encoder task–backbone cells and CIFAR-100 with a 24-exit ViT-L/16; the scaling grid varies retained exits and calibration size.The main benchmarks use matched data roles and frozen logits; the scaling grid uses nested calibration subsamples.Source: §4.1 · p. 5

4.2 CONTROLLED THEOREM CHECKS

• The controlled DKW, Mondrian, calibration-size, and fixed-group shift checks are retained in Appendix D.1 rather than used for the main benchmark claims.Source: §4.2 · p. 6

4.3 MATCHED SELECTION RESULTS

• 0.901 versus 0.814 macro selected coverage for pathwise versus naive layerwise selection across eight task–backbone cells; pathwise average set size and latency fraction are 1.41 and 0.71.MinSE valid selection reaches macro coverage 0.903, latency 0.70, and average set size 1.40.Source: §4.3 · p. 6

4.4 NUMERICAL SCALE OF THE EFFICIENCY BOUND

• The efficiency-bound comparison reports the paired positive cardinality inflation from the path maximum, with cell-wise RHS/observed ratios of 1.07–1.73.The held-out quantity is 0.016–0.086 across encoder cells, compared with observed test means 0.01–; the supplied result passage truncates the latter range.Source: §4.4 · p. 6, §4.3 · p. 6

4.5 POLICY-UNIFORM FRONTIER AND SPARSE SCHEDULES

• At budget b = 4 on CIFAR-100, first-eligible stopping attains coverage 0.902, average set size 2.76, and latency fraction 0.57.The design-chosen restriction returns smaller sets, 2.52 on average, at coverage 0.901 and latency 0.61; one calibration supports all five budgets and both pathwise policies.Source: §4.5 · p. 7

4.6 SCALING IN CANDIDATE EXITS AND CALIBRATION SIZE

• At n = 100, pathwise average set size increases only 0.09 from L = 4 to 24, while Bonferroni returns all 100 classes at L = 12 and 24.At (n, L) = (100, 24), MinSE minus pathwise set size is 0.80 with paired 95% interval [0.47, 1.13].Source: §4.6 · pp. 7–8, Figure 3 · p. 8
• At n = 100, coverage SD is 0.028 and the worst draw is 0.841; at n = 1500, SD falls to 0.006 and the worst draw rises to 0.888.Marginal validity remains exact, but small calibration sets produce greater variation across calibration draws.Source: §4.6 · p. 9

4.7 UNCERTAINTY AND PAIRED COMPARISONS

• Method comparisons pair results at the data-role level that varies, while RTE keeps its calibration/test partition fixed and resamples head-training seeds and test examples.Source: §4.7 · p. 9

• Every admissible returned set contains the calibrated terminal set, making adaptive-depth selection valid through one terminal conformal rank.The coverage guarantee is marginal under exchangeability and frozen scores.Source: §5 · p. 9
• The practical advantage is clearest when many exits share limited calibration data or deployment budgets change; on short encoder paths, performance remains close to MinSE valid selection.Source: §5 · p. 9
• Coverage does not ensure useful sets when shallow heads are weak; full-vocabulary decoder sets remain operationally inert and protect next-token rather than sequence correctness.Empirical slope estimates do not certify the population constants, and Mondrian protection requires stable within-group score laws and adequate calibration counts.Source: §5 · p. 9

• Appendix B specifies execution and fallback behavior; Appendices C and K provide coverage arguments and the path-maximum efficiency proof.Source: REPRODUCIBILITY STATEMENT · p. 9
• Appendix Q fixes data roles, paired resampling, familywise correction, latency scope, and method-specific targets.Appendices L–N give exact values behind the per-cell, policy-frontier, and L–n figures.Source: REPRODUCIBILITY STATEMENT · p. 9
• The timing record includes device, precision, batch size, input size, warm-up, synchronization, and repetition count; 2025–2026 bibliography entries were cross-checked.Source: REPRODUCIBILITY STATEMENT · p. 9

AI USE STATEMENT

• Generative AI assisted with manuscript organization, prose revision, and mathematical review; the authors retain responsibility for independently verifying claims and results.Source: AI USE STATEMENT · p. 10

A ADAPTIVE SELECTION CAN MULTIPLY MISCOVERAGE

• Each fixed exit in the construction has coverage 1 −α, yet an earliest-singleton rule can have coverage 1 −Lα using only X and set sizes.Source: A ADAPTIVE SELECTION CAN MULTIPLY… · p. 14

B SELECTION-SAFE ALGORITHM

• The algorithm calibrates a quantile of terminal prefix-maximum scores, forms nested prefix sets, and returns the first set meeting the cardinality rule or a fallback set.Any label-free rule is valid when the returned set contains the terminal set.Source: B SELECTION-SAFE ALGORITHM · p. 14

C.1 PROOF OF THEOREM 1

• The proof uses exchangeability of terminal scores for split-conformal coverage, then pointwise containment of the terminal set in every prefix set.The claimed bound does not require independence across exits.Source: §C.1 · p. 14

C.2 TRAINING-CONDITIONAL COVERAGE

• The one-sided DKW inequality supplies the stated distribution-free training-conditional floor.Source: §C.2 · p. 15
• With continuous terminal scores, the terminal set’s conditional coverage follows Beta(k, n + 1 −k) for k ≤n; the +∞ convention gives coverage one when k = n + 1.Source: §D.1 · p. 15

D.1 CONDITIONAL, GROUP, AND HYBRID GUARANTEES

• Only one terminal score is calibrated, so the training-conditional bound has no log L term.Source: §D.1 · p. 15

C.3 MONDRIAN COVERAGE UNDER GROUP-PRIOR SHIFT

• Fixed-group terminal quantiles provide group-conditional coverage, and marginal coverage survives changes in group proportions when within-group terminal-score laws remain unchanged.Source: §D.1 · p. 15

C.4 HYBRID ERROR BUDGET

• The point/set hybrid has error at most αpt + αset, with calibration failure probabilities combining by the same sum.Source: §D.1 · p. 16

D.1 CONDITIONAL, GROUP, AND HYBRID GUARANTEES

• After the terminal quantile is fixed, budget, slack, randomization, and load-dependent stopping choices may change without recalibration if returned sets remain supersets of CL.Source: §D.1 · p. 16

D.2 CONTROLLED THEOREM CHECKS

• Per-group calibration raises hard-group coverage from 0.6887 to 0.9149 and shifted marginal coverage from 0.8112 to 0.9129 under the theorem-aligned group-prior shift.Source: §D.2 · p. 16

D.3 DECISION RULES AND UNCERTAINTY

• Coverage is reported separately from efficiency, and latency–set-size comparisons include only methods that meet their native controlled target.Source: §D.3 · p. 16

D.4 BOUNDARY TESTS

• Mondrian calibration improves hardest-group coverage from 0.894 to 0.911 on MNLI, 0.811 to 0.895 on BoolQ, and 0.669 to 0.805 on the SST-2 difficulty split.For the SST-2 hard group, ncal = 72 and coverage is 66/82 = 0.805; the passage cautions that the training-conditional floor concerns calibration draws, not a deterministic bound on one finite test proportion.Source: §D.4 · p. 17
• Full-vocabulary decoder sets contain 7,162–9,620 tokens, with early-exit rates at most 0.52%, and make no sequence-level correctness claim.Source: §D.4 · p. 17
• Increasing the hybrid point branch from 0.02 to 0.08 raises commit rate from 0.180 to 0.470 and lowers latency from 0.690 to 0.640, while joint point error rises from 0.0074 to 0.0371.Source: §D.4 · p. 17

D.5 MECHANISM AND SCORE/SCHEDULE DIAGNOSTICS

• SST-2’s terminal maxima concentrate early but have a thin excess tail and small last-layer inflation; RTE’s poor acceleration is driven primarily by late informativeness rather than path-max inflation.Source: §D.5 · p. 17
• The sparse schedule has average set size 1.39 and latency fraction 0.66 while maintaining coverage 0.892–0.929; APS and RAPS produce larger sets and latency above 0.82.Source: §D.5 · p. 17

E FULL EFFICIENCY-BOUND EVALUATION

• The held-out RHS is 0.016–0.086 versus measured mean positive inflation of 0.01–0.08; the ratio of macro averages is 1.14.Across cells, the ratio is 1.07–1.73; the passage concludes the finite-sample quantile perturbation is conservative but not an order-of-magnitude explanation after including the independently estimated local score-mass term.Source: Table 3 · p. 18, E FULL EFFICIENCY-BOUND EVALUATION · p. 18
• The empirical secant slope is evaluated on the independent design role as a held-out scale diagnostic for the theorem’s Lipschitz term, not as a replacement for its population constants.Source: E FULL EFFICIENCY-BOUND EVALUATION · p. 18

E.1 BOUNDARY REGIMES

• The boundary tests delimit where selection-safe guarantees remain informative but do not by themselves produce useful acceleration.Source: §E.1 · p. 19

F.2 SCOPE AND LIMITATIONS

• The guarantee is marginal under exchangeability and frozen path scores, not feature-conditional or robust to arbitrary distribution shift; the dense L–n grid isolates candidate count, not architectural-depth effects.The grid reuses one frozen ViT-L/16 path, and the vision replications do not amount to a population-level architecture study.Source: §F.2 · p. 19
• Mondrian calibration’s hard-group coverage claims require stable within-group score laws and adequate calibration counts, as illustrated by the reported SST-2 denominators of 72 calibration and 82 test examples.The text also cautions that decoder results certify next-token set coverage, not sequence-level correctness.Source: §F.2 · p. 19

F.4 NON-BINARY BENCHMARK: CIFAR-100

• On CIFAR-100 at (n,L)=(500,24), the 24-exit ViT-L/16 at b=4 achieves coverage 0.902, average set size 2.76, and latency fraction 0.57, with smaller sets than Bonferroni (4.05), EENN-AVCS (3.54), and MinSE (3.18).Source: §F.4 · p. 20

G EXTENDED DISCUSSION

• At (n, L) = (100, 24), the paired MinSE-minus-pathwise set-size difference is 0.80 [0.47, 1.13], and Bonferroni is exactly degenerate in five displayed grid cells.The frozen-path scaling grid is nearly flat for pathwise set size as L grows; separately trained vision paths and a second vision dataset show the same ordering.Source: G EXTENDED DISCUSSION · p. 20, N LAYER-COUNT AND CALIBRATION-SIZE GRID · p. 24
• At (n, L) = (500, 24) and budget b = 4, first-eligible stopping reaches latency 0.57 with average set size 2.76; a design-chosen restriction yields 2.52 at latency 0.61 and coverage 0.901.The same terminal calibration supports later changes to set or latency budgets, and first-eligible is pointwise latency-minimal for a fixed cardinality budget.Source: §F.1 · p. 19, G EXTENDED DISCUSSION · p. 20, §F.4 · p. 20
• Theorem 2 links path-maximum set inflation to the calibration tail of early-over-terminal score excess and the local mass of last-layer scores near the conformal threshold.In measured encoder cells, the held-out plug-in bound is 0.016–0.086 against observed positive inflation of 0.01–0.08.Source: G EXTENDED DISCUSSION · p. 20, K PROOF OF THE PATH-MAXIMUM EFFICIENCY… · p. 23

H LARGE-L BASELINE ADAPTATIONS

• The large-L comparison uses one prespecified adaptation per external method, so its scaling curve describes those specific implementations rather than every valid-selection rule.EENN-AVCS retains its native construction, while MinSE rebuilds its candidate family and selector as L changes.Source: H LARGE-L BASELINE ADAPTATIONS · p. 21

I.3 PAIRED ENCODER, PATH-COST, AND MECHANISM DIAGNOSTICS

• The path-maximum diagnostic reports measured returned-set cardinality, the pre-fallback empty-terminal rate, and the paired positive-part statistic required by Theorem 2.Across six binary rows, returned-prefix and path-terminal means differ by at most 0.0022–0.0040, supporting direct measurement rather than reconstructed means.Source: §I.3 · pp. 21–22

O INDEPENDENT-DEPTH AND DATASET REPLICATION

• The independent-path and ImageNet-1k replication preserves the qualitative ordering, though it does not isolate architectural-depth effects.The 12- and 24-exit models were trained separately; ViT-B/16 and ViT-L/16 also differ in capacity.Source: O INDEPENDENT-DEPTH AND DATASET… · p. 24

P.1 DECODER BOUNDARY

• Decoder coverage remains near 0.90, but full-vocabulary sets are too large for actionable early exit and execution remains essentially full-depth.The authors do not use decoder wall-clock latency to support the efficiency claim.Source: §P.1 · p. 24

Data roles

• When tuning is required, the encoder study separates training, design, conformal calibration, and test roles, with no final-test labels used for selection or tuning.Identity scores with a prespecified schedule may omit the design split.Source: Q EXPERIMENTAL PROTOCOL · pp. 24–25

Paired evaluation

• Training-seed variability is kept distinct from calibration-split variability, with methods sharing available role splits within each seed.SST-2, MNLI, and BoolQ use 20 paired role splits per seed; RTE uses one fixed role assignment.Source: Q EXPERIMENTAL PROTOCOL · p. 25

Inference

• Aggregate selection comparisons use a hierarchical paired bootstrap, while eight per-cell selection-gap statistics receive a familywise maximum-statistic correction.The bootstrap resamples training seeds first, then paired role splits or RTE test examples, as applicable.Source: Q EXPERIMENTAL PROTOCOL · p. 25

Efficiency diagnostic

• Theorem 2’s numerical diagnostic estimates the local slope on design data and reports observed cardinality inflation on test data.The calibration role determines t⋆ from final calibration excesses; Table 10 reports directly measured returned-set cardinality and paired positive inflation.Source: Q EXPERIMENTAL PROTOCOL · p. 25, Table 10 · p. 25

Resource measurement

• Resource outcomes use normalized FLOPs and measured latency, with timing that includes exit-head, set, cardinality-check, synchronization, and fallback costs.Offline design and calibration costs are reported separately from online savings.Source: Q EXPERIMENTAL PROTOCOL · p. 25, Table 16 · p. 27

Evaluation reports

• The tables specify paired comparisons, score and schedule ablations, controlled PAC verification, scaling, replication, and full-vocabulary decoder-set evaluations.The MinSE-minus-pathwise set-size difference is paired on a shared calibration subsample and test set; Bonferroni entries marked 100/1.00 are exact degeneracies.Source: Table 12 · p. 26, Table 14 · p. 26, Table 15 · p. 26