acceptodds
Under review as a conference paper at ICLR 2027

Rank Envelopes and Finite-Sample Geometry in Split Conformal Prediction

Abstract

Split conformal prediction (SCP) provides finite-sample, distribution-free marginal coverage through discrete calibration ranks. In small-calibration, high-coverage regimes, however, the rank grid may be too coarse to represent the desired coverage level, causing SCP to become conservative or vacuous. We develop rank-indexed quantile envelopes that characterize this finite-sample resolution through order-statistic geometry. The envelopes partition the rank space into forced-in, ambiguous, and forced-out regions and yield explicit finite-sample coverage bounds for prediction rules constrained by this geometry. The resulting construction separates rank decisions that are fixed by finite-sample calibration from those that remain unresolved and can therefore be handled by different efficiency mechanisms. When randomization is acceptable, envelope mixing uses the unresolved region to attain exact marginal target coverage whenever the target lies within the attainable coverage range. When historical, prior, or model-based information about the score distribution is available, reference-guided rules use this information only within the unresolved region while retaining explicit distribution-free coverage control. The same construction extends naturally to exchangeable strata, providing stratum-wise finite-sample guarantees when effective calibration sizes are small because coverage is required separately across classes or subgroups. The framework also clarifies the limits of deterministic improvement under finite rank resolution and recovers standard SCP as the ambiguity region vanishes. Experiments in regression and classification illustrate how randomization, auxiliary information, and stratification can improve informativeness in small-calibration regimes while making their corresponding coverage guarantees explicit.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
conformal prediction, predictive inference, efficiency, validity, uncertainty quantification

Reviews

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

The paper investigates the Split Conformal Prediction method (SCP) under the condition of small calibration sample size and high target coverage, which makes SCP return the entire label space quite frequently. The authors construct Beta-quantile envelopes around each rank of the calibration set, which allows them to classify the ranks as forced-in, ambiguous, or forced-out. Based on that, the authors define two sets: the inner set C⁻ and the outer set C⁺, and any prediction set falling in between these two would have a coverage level between a lower bound LB and an upper bound UB. Using the above, the authors suggest three algorithms: a random mixture of the two sets achieving the target coverage exactly, a projected rule using a reference distribution of the scores to assign ambiguous ranks and a stratified version for subgroups. The authors run experiments on synthetic scores and on three datasets: California Housing, Diabetes and CIFAR-10.

Critical strengths
  • The paper deals with a real problem. For small m and large τ, SCP outputs the entire label space and this commonly occurs in class conditional settings.

  • The concept of forced-in/ambiguous/forced-out is well-clarified so one can easily identify what rank choices are yet to be made at a particular m.

  • The reference rule (Proposition 3.10) ensures that the set remains in [C⁻, C⁺]. That is why the selection of an “unfavorable” reference distribution can not contradict the provided coverage guarantees (LB and UB). This is a reasonable approach to utilizing external data.

Critical weaknesses
  • Missing baselines. The main results compare only against plain SCP. For exact coverage, randomized SCP is the natural baseline but it is not used on the California Housing and Diabetes datasets. Comparisons with the simple max-score rule and with SPI would help evaluate the proposed methods.

  • The description of SPI also needs some correcting. The authors say their method “avoids model misspecification and additional exchangeability assumptions required for synthetic data”, but SPI claims finite-sample coverage without assumptions on the real or synthetic data distributions.

  • Formatting and structure.

    • Table 3 goes outside the column margin.
    • There is no single experiments section describing the baselines, setup and choice of β, which makes the paper’s structure hard to follow.
    • The classification results, the stratified results, related work and limitations are not in the main paper.
    • The Figure 14 sub-captions do not match the plot titles.
  • Comparisons are not at matched coverage.

    • In cases where calibration is small but coverage is high, SCP tends to return the whole label space. The improvement is measured against SCP’s capped size, so it depends on the cap the authors chose: 100 in the heteroskedastic setting and Range(Y) = 321 on the Diabetes dataset.
    • Tables 2 and 3 report gains but not coverage.
    • For CIFAR-10, the text reports Ĉλ coverage for only two settings (0.944 at τ = 0.95 and 0.989 at τ = 0.99, both with m = 10).
Questions for authors
  • Compare your methods with randomized SCP, SPI and the max-score threshold at the same coverage, including on the real datasets? Also, what are the exact CIFAR-10 coverages for every setting, and did you break tied scores at random?

  • When k = m + 1, does C⁻ under your definitions include rank m + 1, making it the full label space? If not, which threshold is used instead?

  • Which β values and cutoff convention produced each table? How was C⁻ computed at m = 10, τ = 0.97, where β_min appears to make it the full label space?

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

This paper introduces rank-indexed intervals obtained from Beta order-statistic quantiles and uses them to define inner and outer rank-threshold prediction sets. Any rule sandwiched between these two sets is called admissible, and Theorem 3.1 bounds its marginal coverage between the fractions of ranks included by the inner and outer thresholds. The paper then proposes three uses of this construction: selecting an inner rule, randomizing between the inner and outer sets to attain an exact target coverage, and using a reference score distribution to make decisions within the ambiguous ranks. Numerical experiments focus on small-calibration, high-coverage settings in which ordinary split conformal prediction is conservative or vacuous.

Critical strengths

The paper addresses an important and practically relevant problem. Improving the informativeness of conformal prediction sets in small-calibration, high-coverage regimes is a worthwhile research direction, particularly when standard split conformal prediction becomes overly conservative or vacuous.

Critical weaknesses

Major comments

  1. Certified validity precludes deterministic efficiency gains over SCP. Since LBmβ(τ)=r−/(m+1)LB_m^\beta(\tau)=r^-/(m+1), the certification condition LBmβ(τ)≥τLB_m^\beta(\tau)\ge\tau implies r−≥⌈(m+1)τ⌉r^-\ge\lceil(m+1)\tau\rceil. Consequently, C^SCP⊆C^−⊆C^\widehat C_{SCP}\subseteq\widehat C^-\subseteq\widehat C for every admissible C^\widehat C. Thus, under the paper's own certification condition, no admissible set can be smaller than SCP, contradicting the claimed deterministic efficiency improvements without sacrificing validity.

  2. The coverage bounds do not rely on the Beta envelopes. The pointwise 1−β1-\beta probability statement in Equation (3) is not used in proving Theorem 3.1. The bounds follow solely from uniform test ranks and deterministic rank cutoffs, and hold for arbitrary cutoffs without Beta envelopes or a confidence parameter. This substantially limits the novelty of the central theoretical result.

  3. Limited novelty of the exact-coverage randomization. Theorem 3.9 achieves exact coverage by randomizing between two rank-threshold sets, following the classical idea of smoothed conformal prediction (Vovk et al., 2005). The paper does not establish a novel validity guarantee or a general efficiency advantage over standard randomized SCP.

  4. Unclear and potentially inconsistent selection of β\beta. Proposition 3.2 specifies the condition on β\beta needed to certify nominal coverage, yet the inner and projected envelopes frequently undercover in the experiments. The authors should clarify how β\beta is selected and reconcile the reported efficiency gains with the stated validity guarantees.

Minor comments

  • Tie handling. Theorem 3.1 assumes exchangeability, but its proof additionally assumes continuity to ensure uniform ranks without ties. Tie handling should be clarified, especially for classification scores.

  • Incomplete coverage reporting. Tables 2 and 3 report only efficiency gains without empirical coverage. Coverage should be reported alongside efficiency, particularly since some proposed methods undercover.

Questions for authors

Please see Weaknesses section.

Reviewer_R2xqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors study split conformal prediction (SCP) when the calibration set is small and the target coverage τ\tau is high. In that regime the required rank k=⌈(m+1)τ⌉k=\lceil (m+1)\tau\rceil can exceed mm, and SCP returns the full space. For each rank rr, the authors take the central 1−β1-\beta interval of Beta$(r, m - r+ 2)$. They use it to sort ranks into three types: forced-in, ambiguous and forced-out. This gives cutoffs r−≤r+r_-\le r_+ and inner and outer sets C^−⊆C^+\hat C^-\subseteq\hat C^+. Any rule between the two sets has coverage in [r−/(m+1),r+/(m+1)][r_-/(m+1), r_+/(m+1)] (Theorem 3.1). Inside this, the paper proposes 3 techniques: randomly mixing the two sets to hit τ\tau exactly (Theorem 3.9), a projection rule that uses a reference score distribution only on ambiguous ranks (Proposition 3.10), and a stratified version. The experiments aim to validate theoretical findings using synthetic scores, real-world datasets (California Housing, Diabetes, CIFAR-10), and an imbalanced two-group simulation. They report size reductions relative to SCP, and compare against Randomized-SCP only in the appendix.

Critical strengths

The validity layer is correct, and its differetnce from the efficiency layer is clearly demonstrated. Here, Theorem 3.1 and Proposition 3.8 state exactly which rank decisions are fixed, and give a distribution-free coverage interval for any choice in the band. Proposition 3.10 shows that a misspecified reference cannot break this interval. This is the part I would trust as is, and it is a sensible template for bringing auxiliary information into problems with small calibration.

Another thing is that the problem studied is non-trivial and real. The starvation regime appears whenever coverage is needed per group or per class. The experiments target exactly that setting and include Randomized-SCP (which is the right baseline, as far as I am concerned).

Critical weaknesses

First, nothing in the paper shows that envelope mixing beats ordinary Randomized-SCP, and where it appears to, the numbers are inconsistent with Eq. (11). Let δ=(m+1)τ−m\delta=(m+1)\tau-m. In the main tables, the reported C^λ\hat C_\lambda gain equals (1−δ)(1-\delta) times the C^−\hat C^- gain, which is exactly what adjacent-rank randomization gives. For example, Table 1 at m=10m=10, τ=0.97\tau=0.97 gives 0.33×62.46=20.60.33\times62.46=20.6, against 20.3720.37 reported. When τ>m/(m+1)\tau>m/(m+1), Theorem 3.9 forces r+=m+1r_+=m+1, so λ≥δ\lambda\ge\delta and the expected size is at least δ\delta times the full size. Several appendix values fall below this floor. Fig 10(d) (m=18m=18, τ=0.96\tau=0.96) has a floor of 24 but shows roughly 10, and Fig 14 (target 0.95, m=15m=15) has a floor of 2.0 but shows roughly 1.2. The exact numbers in F.1.1 (m=18m=18, τ=0.95\tau=0.95) are the clearest case: if the band is adjacent, C^λ\hat C_\lambda is Randomized-SCP and should give the reported 13.41; if it is wider, the expected length is at least 52.5. The reported 10.15 fits neither, and its coverage, 0.9484, is below target and equal to that of the calibration maximum, 18/1918/19. Wider mixing also shouldn’t be expected to help. If expected size is convex in the rank cutoff, Jensen’s inequality makes adjacent mixing optimal at fixed coverage. For Exp(1) scores with m=20m=20 and τ=0.8\tau=0.8, the envelope rule gives expected length 4.58, against 3.43 for adjacent ranks. Since exact marginal coverage is already available through standard adjacent-rank randomization, the paper has to show a clear efficiency advantage over Randomized-SCP. The reported results do not establish one, and several are inconsistent with the proposed mixing formula.

Second, the deterministic "certified" gains come from lower coverage. If Proposition 3.2 certifies τ\tau, then r−≥kr_-\ge k and C^SCP⊆C^−⊆C^proj\hat C_{SCP}\subseteq\hat C^-\subseteq\hat C_{proj}, so neither set can be smaller than SCP. Appendix F.1 says βmin\beta_\mathrm{min} is used when feasible; then it is feasible at m=10m=10 (βmin≈0.21\beta_\mathrm{min} \approx 0.21 at τ=0.99\tau=0.99), and it would make C^−\hat C^- the full space. Yet Table 4 reports a 62%62\% gain at coverage 0.913≈10/110.913 \approx 10/11. The reported coverage is consistent with using the maximum calibration score, which would be equivalent to SCP at coverage m/(m+1)m/(m+1). The actual cutoff is needed to establish whether this was the implemented rule. The real-data results show the same pattern: for California at m=10m=10, τ=0.99\tau =0.99, C^−\hat C^- reaches 0.9100.910 and C^proj\hat C_{proj} reaches 0.9450.945. However, the paper state that the gains come without sacrificing validity. Moreover, the shorter stratified C^−\hat C^- in Table 5 needs the same explanation.

Questions for authors

For the highlighted Appendix F.1.1 configurations (m=18m=18, τ=0.95\tau=0.95 and m=23m=23, τ=0.96\tau=0.96), what were β\beta, r−r_-, r+r_+ and λ\lambda, and how often was the full interval returned? If the band was wider than two ranks, how is a mean length of 10.15 compatible with λ≥(1+δ)/2\lambda\ge(1+\delta)/2?

How was β\beta chosen in Tables 1, 4, 6 and 7, given that βmin\beta_\mathrm{min} is feasible at m=10m = 10?

Can the mixing rule be compared directly with Randomized-SCP at the same nominal coverage, and can coverage-size curves be reported for the projected rule and Randomized-SCP? Any parameter tuning used to match coverage should be separated from the final evaluation.

What size is assigned to vacuous sets when the half-normal scores are unbounded?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.