acceptodds
Under review as a conference paper at ICLR 2027

SELECTION-SAFE CONFORMAL EARLY EXIT: DISTRIBUTION-FREE COVERAGE UNDER ADAPTIVE DEPTH

29 views

Abstract

Calibrating a conformal prediction set at each early exit does not preserve coverage after a data-dependent exit is selected. We construct one terminal path score from prefix maxima, calibrate one split-conformal quantile, and return nested prefix sets that all contain the valid terminal set. The resulting guarantee is selection-safe without an α/L correction and holds simultaneously for every post-calibration label-free policy that preserves terminal-set containment. We further bound the efficiency cost of the path maximum by the empirical tail of the early-over-terminal score excess, linking set inflation to the mechanism diagnostic J(x, y). At the smallest admissible excess threshold, the held-out plug-in right- hand side is 0.016–0.086 against measured mean positive terminal-set inflation 0.01–0.08; the cell-wise ratio is 1.07–1.73. Across eight matched encoder task– backbone cells, including an RTE split with ncal = 498 drawn from the training partition, 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 and ncal = 500, first-eligible stopping at budget b = 4 attains coverage 0.902, average set size 2.76, and latency fraction 0.57; a design-chosen restriction reduces the returned set to 2.52 while, necessarily, increasing latency to 0.61. The same terminal calibration supports deployment-time budget changes without refitting. A joint L–n sweep isolates candidate-count scaling. At n = 100, pathwise set size changes from 3.02 to 3.11 as L increases from 4 to 24, whereas Bonferroni becomes exactly degenerate at L ≥ 12 and returns all 100 classes. Against MinSE valid selection, the paired set-size difference at (n, L) = (100, 24) is 0.80 [0.47, 1.13], so the long-path, limited-calibration advantage is assessed from paired replicates rather than overlapping marginal intervals. Independent-depth CIFAR-100 and ImageNet-1k replications preserve the qualitative ordering. Full-vocabulary decoder experiments remain a negative boundary, with average sets containing 7,162–9,620 tokens and nearly all examples reaching full depth. The empirical picture is therefore specific: pathwise calibration is most useful when the number of candidate exits is large relative to calibration size, when deployment budgets change after calibration, and when shallow heads can return actionable sets.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Early-exit networks, adaptive depth, conformal prediction, distribution-free coverage.

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_9sCKOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper claims to propose a new conformal prediction method for early exits in neural networks.

Critical strengths

I don't see any strength in the paper.

Critical weaknesses

The paper is terrible in organization and textual clarity, and it doesn't even have a figure explaining the main contribution. I don't do research on conformal prediction but I reviewed some conformal works earlier and I could understand and make helpful comments for them. However, this paper is nowhere close to being readable, and it looks totally AI-written, to be honest; see the ethical section for that. Some examples I listed here, and there are many more in the paper: 1 - claims without citation in the intro, see line52 2 - acronyms without explicit forms; see abstract, section 4.2 3- notations without definitions, see everywhere!!!! 4 - one line paragraphs, see section 3.4 5- No explanatory figures! 6 - Jumping from one topic to another without coherent transitions; see everywhere, especially related works. The list goes like that but I won't spend more time than the authors writing the paper for this paper.

Questions for authors

I don't have any questions

2 comments

Thank you for the direct feedback. We accept the criticism of the presentation. The submitted version was hard to read, and we have rewritten it. For each example you gave:

Claims without citations in the introduction: citations added. Acronyms not spelled out (abstract, Section 4.2): every acronym is now expanded at first use, including EENN, AVCS, FyS, CALM, PABEE, APS, RAPS and DKW. Undefined notation: every symbol is now defined before it is used. One-line paragraphs (Section 3.4): merged. No explanatory figure: the new Figure 1 shows the whole method. Weak transitions, especially in Related Work: rewritten so that each paragraph leads into the next.

On the ethics flag. We understand why a hard-to-read paper raises this concern, and we want to answer it directly. As our AI Use Statement says, generative AI assisted with manuscript organization, prose revision, and mathematical review. The research itself is ours. The method came out of our own experiments: our first version calibrated a separate set at each layer, a diagnostic showed that these sets were not nested, and the running maximum at the center of the paper was our fix. We also dropped an earlier certificate-based method after the simpler construction beat it in every run. The authors are responsible for every claim, proof and number in the paper. We agree that the submitted text read poorly, and we hope the revised version is clearer.

Unfortunately, you should have written a readable paper before the deadline. Otherwise, everybody can submit an unfinished draft and edit the paper after the rebuttal. The rebuttal is not for rewriting the paper, and even with the current changes, the abstract is not readable and contains unnecessary details. About the ethics flag, I don't claim you fabricated the results or AI came up with the idea etc. but it's very apparent that AI wrote most of the text (not edited, directly written) and your statement sounds misleading to me. I let AC decide about the ethics flag.

Reviewer_Qgk4OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Early-exit networks attach prediction heads to intermediate representations and stop whenever the prediction is sufficiently reliable. To quantify model certainty at each layer, existing works rely on classical stopping rules, e.g., confidence and entropy, but none provide theoretical guarantees about their correctness. Conformal prediction provides theoretical coverage guarantees that the true label belongs to a prediction set with probability at least 1−α1-\alpha. This paper investigates how to use conformal prediction for early-exit networks. It first considers the naive solution of applying conformal prediction at each layer and shows that it is not optimal. It then proposes Pathwise CP, which calibrates a single quantile using the terminal score of the last layer and uses it to construct nested prediction sets at all layers.

Critical strengths
  1. The paper addresses an interesting problem, and conformal prediction provides a principled solution for deciding at which layer to stop, compared to using classic stopping rules like entropy.
Critical weaknesses
  1. The current version reads more like a draft than a paper ready for review, and it does not meet ICLR standards. The paper addresses an interesting problem, and conformal prediction is a principled solution for deciding at which layer to stop. However, the writing is really poor, and I personally had significant difficulties understanding what the authors are trying to say. For example, the abstract is too verbose and could be made more concise and to the point.
  2. Theorem 2 assumes that the per-layer CDF of the score rℓ(X,y)r_\ell(X,y) is MyM_y-Lipschitz, which I consider too strong. The authors empirically estimate these constants across datasets in Table 3, but provide no upper confidence bounds for them.
  3. I don't see any practical benefits of the proposed method and it seems limited in some settings. In particular, the decoder experiments produce very large prediction sets (7162-9620 tokens on average), and nearly all examples reach full depth.
Questions for authors
  1. What is an "increasing map TℓT_\ell"? Is it simply a nonconformity score (e.g., APS, RAPS, etc.)? If so, I don't see the need to introduce new terms that just makes the presentation more complicated.
  2. I don't understand how the models are trained. Do you attach a classification head to each selected layer to predict the class from that layer's representation, then compute the cross-entropy loss at each exit and optimize the backbone and all heads jointly (e.g., by averaging the per-layer classification losses), or are the heads and backbone trained separately?
2 comments

Thank you for the detailed review. We agree with you on the writing (please see the general comment). Your point on the Lipschitz assumption improved Theorem 2, and your point on practical benefit made us find an error in how we reported MinSE.

W2. The Lipschitz assumption. We agree. It was strong and hard to check, and point estimates of MyM_y without confidence bounds do not certify anything. The revised Theorem 2 drops the assumption. The expected extra set size is now bounded by βt\beta_t, the expected number of labels whose last-layer score lies in a small band above the threshold, with no smoothness condition. βt\beta_t does not depend on labels, so it can be bounded from held-out inputs with the empirical Bernstein inequality of Maurer and Pontil (2009). At δ=0.05\delta = 0.05, the certified bounds are 0.051–0.190 across the eight encoder cells, and each is above the observed inflation of 0.01–0.08 (Table 23). We keep the Lipschitz form only as an interpretation, and Section 5 says explicitly that the estimated slopes are not a certificate.

W3. Practical benefit. This comment made us recheck the latency accounting, and we found an error (see the correction in the general comment). With end-to-end latency, our rule matches MinSE in coverage (0.901 vs 0.903) and set size (1.41 vs 1.40) at 0.71 of full latency, against 0.98 for MinSE. The paired difference is −0.274 [−0.292, −0.256] (Table 12). On CIFAR-100 with 24 exits, the gap is larger: 0.57 against 0.994. The sets also differ when many exits share little calibration data. At (n,L)=(100,24)(n, L) = (100, 24), MinSE's sets are larger by 0.80 labels [0.47, 1.13].

On the decoders, you are right that 7,162–9,620 tokens with almost no early exits is not a practical result. We report it on purpose, as the boundary of what exact true-token coverage can deliver over a full vocabulary. Corollary 1 offers a practical alternative for decoding: calibrating for agreement with the full model brings the sets down to 173–418 tokens and the exit/full ratio to 0.874–0.958 (Table 25).

Q1. What is the increasing map TℓT_\ell? It is not a new nonconformity score, and we agree that the name added confusion. APS and RAPS define the score itself. TℓT_\ell is an optional monotone map applied to an existing score, so that scores from different exits are on a similar scale before we take their maximum. In every headline result, TℓT_\ell is the identity, so the score is just −log⁡pℓ(y∣x)-\log p_\ell(y \mid x). Section 3.1 (lines 160–163) now says this directly. Appendix Q defines the two learned options, an affine map and a quantile map, both fitted only on the design split. Table 14 compares them with APS and RAPS. None of them beats the identity on set size.

Q2. How are the models trained? As in your first description. Each encoder backbone gets a linear head on the [CLS] state at each exit. The backbone and all heads are trained jointly, with the per-exit cross-entropy losses averaged with equal weights. After training, the backbone, heads and scores are frozen before design, calibration and testing. For ViT-L/16, the backbone stays frozen and only the 24 linear heads are trained. Appendix Q gives the full settings.

I would like to thank the authors for their response. I am sorry, but I will have to maintain my score and my assessment of the paper. I agree with Reviewer 9sCK and think the authors should reconsider the paper's presentation and clarity. Whether I agree or not with the use of AI for research or writing the manuscript, I think the authors should at least put a bit of effort into making sure the ideas are clear and easy to follow for humans. Additionally, my concerns and questions have led to a substantial portion of the authors' claims and results being changed, which would require another full round of review.

Reviewer_1ckbOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

Consider a model consisting of L layers. In contrast to the original structure, where we get the classification output from the last layer, here we can place the classification layer after each of these layers and return a classification result.

The question is: what is the earliest point at which we can get a conformal prediction set out of it while maintaining the guarantee and maintaining a low set size? The constraint is over the validity of the coverage, and the optimization is over both set size and the number of steps that we should continue from the model during inference.

The way the authors approach this problem is by maximizing the conformity scores with the later layers. This means that, by increasing the number of layers, the set size gets smaller, and only applying one conformal prediction on the ultimate layer gives a valid guarantee for that layer. By the nested property of the sets over layers, the same guarantee applies to the output of each early exits.

Critical strengths

The problem is genuinely interesting, specifically when it comes to next-token prediction, not the classification. However, the model proposed in this paper cannot achieve a good conformal result, meaning that such an efficiency result is not achievable with the current state. In general, it's very important for efficiency and also for classification. The design choice, however simple, is genius to reduce the required calibration steps only to one on the ultimate layer. That theory follows quite intuitively. I should also mention that I could not follow Theorem 2 because it was not clearly motivated and the terminologies were not clearly introduced. I would really appreciate a more reader-friendly version of the theorem.

I think the empirical study is also extensive enough. I also appreciate the fact that the authors reported the negative results on next-token prediction as well.

Critical weaknesses

My main concern about this paper is presentation. In the introduction, the problem is not well motivated and well introduced. In the subsequent sections, things like the data stored for the transformation, the purpose of the non-decreasing transformation, and some other blocks are also not clearly mentioned or justified.
For a normal reader who's not familiar with the topic, I guess it's close to impossible to understand the paper on the first read. For a reader who's familiar, still, it's hard to follow. For example, I could not understand Theorem 2, what it says, and how it connects to other blocks of the paper.
Also, there are other writing and format issues, for example:
- The missing title of the conference at the beginning of the paper in the header.
- Paragraph breaks at lines 233 to 238.
- The y-axis ticks of the third figure were not organized. It could be presented in a much better way just by reducing the font size of the ticks. In general, I found the writing of the paper quite far from other conference papers that I read in these venues. It was closer to a technical report that does not motivate the reader to understand the underlying problem and why this is helpful.

I also thought that the theory, while solid, is not easy to read and not clearly introduced. The outcome of the theorems could be written more clearly. The motivation behind each of them could also be written in a more clear way. I don't find this written in a format that is aligned with the conference.

While the idea behind the paper is borderline more towards accept, the presentation is reducing the quality and also affects my score.

Questions for authors
  1. Can the guarantee be written as a conformal statement about the similarity of the output layer and the intermediate exit layers? I assume that could also be a solution to the issue with the autoregressive decoding.

  2. I'm not sure if the nesting property is needed for each pair of consecutive layers, since you're always using the last layer's result to apply conformal prediction over. I think the only sufficient requirement is that all other layers have a score higher than the last layer, not anything other than that.

Given that, maybe you can have a more clear signal of where, early in the prediction layers, we could apply the early exit. Specifically, there could be some intermediate layers that distort the presentation while the other ones retrieve them, and this sequentially increasing score would affect the final result.

  1. Please restate Theorem 2 in a more clear way. What are each of the components? What is each sentence trying to accomplish in terms of set size? Intuitively, how can I interpret it?

  2. You can also compare your method with an oracle prediction set result: not applying the nesting transformation, but computing the minimum set that can attain 90% coverage given the true label for each layer and stopping at the earliest possible layer. Then compare your result with optimal oracle results. We can understand how much the method is losing.

1 comment

Thank you for the careful review and for engaging with the theory. You were right about the presentation, and your four questions led directly to new material in the paper.

Presentation. Please see the general comment. On the specific points: the paragraph breaks around the old lines 233–238 are fixed, and the y-axis tick labels of Figure 3 are readable.

Q1. A guarantee about similarity to the output layer. Yes, this works, and we think it is a good suggestion. Calibrate the same path score on unlabeled inputs and use the last layer's prediction y^L(X)\hat{y}_L(X) in place of the true label. The pairs (Xi,y^L(Xi))(X_i, \hat{y}_L(X_i)) stay exchangeable because the target is a fixed function of the input, so Theorem 1 gives Pr⁡{y^L(X)∈returned set}≥1−α\Pr\{\hat{y}_L(X) \in \text{returned set}\} \ge 1 - \alpha for any stopping rule that keeps the terminal set. The rule "output the first singleton, otherwise fall back to the last layer" therefore disagrees with the full model with probability at most α\alpha. This is Corollary 1 (Section 3.3). As you expected, it helps a lot with decoding. On the three decoders, average sets go from 7,162–9,620 tokens down to 173–418, and the exit/full ratio drops to 0.874–0.958 (Table 25). The catch is that it protects fidelity to the full model, not correctness, so if the last layer is wrong, the early exit is wrong too.

Q2. Is nesting needed? You are right that what matters is the score at the stopping exit not exceeding the calibrated last-layer score. Nesting is not a separate requirement. The subtle part is that when we stop at exit ℓ\ell, we have not yet seen layers ℓ+1,…,L\ell+1, \dots, L. So the rule cannot check "every other layer scores above the last layer" at stopping time. It needs a score that is safe for whatever the later layers turn out to be. Proposition 1 shows that among all such scores computed from the layers already run, the running maximum is the smallest. It gives the smallest valid set at every exit, and nesting comes for free. You are also right that a few intermediate layers can distort the path. Theorem 2 makes this visible: such layers show up as a large mtm_t, and the fix is to drop them from the exit schedule on the design split.

Q3. Theorem 2 in plain words. It measures what the running maximum costs in set size, in two steps. (i) The threshold only goes up because of calibration examples where some earlier layer scored the true label worse than the last layer did. If mtm_t of them are worse by more than tt, the threshold rises by at most wt=t+B(k+mt)−B(k)w_t = t + B_{(k+m_t)} - B_{(k)}. (ii) A label can only enter the set because of this rise if its last-layer score lies in the band (B(k),B(k)+wt](B_{(k)}, B_{(k)} + w_t]. So the expected number of extra labels is at most the expected number of labels in that band. Intuitively, the cost is small when early layers rarely disagree strongly with the last layer about the true label. In our encoder cells, the measured extra set size is 0.01–0.08 labels (Section 4.4).

Q4. Oracle comparison. We added it as Table 24. The oracle sees the test labels and picks, from the same per-layer sets, the earliest exits that still reach 90% coverage. It reaches mean set size 2.18 at selected depth 0.30, against 2.80 and 0.55 for our rule. The oracle cannot be deployed, but the gap shows how much room is left within the same candidate sets, which we think is the comparison you had in mind.

Comments on the paper

1 comment

We thank the reviewers for their time. All three of you found the paper hard to read, and we agree. The submitted text was too dense, many terms were used before they were defined, and there was no picture of the method. We have uploaded a revised PDF. The main changes are listed below.

Presentation. The new Figure 1 (page 2) shows the full method in one picture: per-exit scores, the running maximum, one calibrated quantile, and the nested sets. Every acronym and symbol is now defined where it first appears. We merged the one-line paragraphs and rewrote the introduction and related work so that each paragraph leads into the next. To make room for it, the old Figure 1 (per-cell coverage) has moved to the appendix as Figure 4. The old Figures 2 and 3 keep their numbers.

Theorem 2. It no longer needs a Lipschitz assumption. The extra set size caused by the running maximum is now bounded by the expected number of labels whose last-layer score falls in a small band just above the threshold. This number can be bounded from unlabeled held-out data (Section 3.2 and Table 23). We also added a plain-language reading of the theorem right after its statement (lines 247–259).

New results. Proposition 1 shows that nesting is a consequence, not an extra requirement. Corollary 1 gives a label-free guarantee of agreement with the last layer, and Table 24 compares our rule with a label-aware oracle. All three came from Reviewer 1ckb's questions.

A correction. While answering Reviewer Qgk4 on practical benefit, we found a mistake in how we reported MinSE's latency. The submitted paper counted MinSE's cost only up to the exit it selects (0.70 of full latency on the encoders and 0.65 on CIFAR-100). But MinSE has to see the set size at every exit before it can choose one, so in practice it runs the whole network. With end-to-end latency, MinSE is at 0.984 on the encoders, against 0.710 for our rule. On CIFAR-100 at (n,L)=(500,24)(n, L) = (500, 24), it is at 0.994, against 0.57. Coverage and set sizes do not change. We corrected Tables 1, 12 and 19–21, Figure 2 and Appendix H, and we now report MinSE's selected depth separately.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.