Conformal prediction provides prediction sets with finite-sample guarantees, but the label verification required for calibration can be expensive. We develop a partial verification method that returns exactly the same prediction sets as complete verification. We characterize calibration certificates, the verified information sufficient to determine the conformal threshold, and design a procedure that coordinates verification across calibration examples. For finite thresholds at high coverage, its verification cost is less than twice the minimum certificate cost when candidates are checked in order. Across retrieval, mathematical solutions, and configuration evaluation, it reduces verification cost by 15-82% compared with verifying calibration examples one at a time, while producing identical prediction sets.
Figures & tables
Figure 1: Fewer verifications, the same prediction set. Both panels show the same five ranked calibration pools. Here calibration selects the smallest return depth containing an acceptable candidate in at least four pools. Both approaches certify returning the first two candidates on a new input; partial verification leaves the first pool’s search unfinished. Ellipses omit candidates after an observed acceptable one.
Task / ranking
(n,α)
Splits
Finite
Size
Hit
Exact
Serial
Layer
Saving vs. Serial
TREC / BM25
(40,0.2)
10k
100.00%
10.48
0.8158
265.21
260.69
173.51
33.44% [33.25,33.63]
MATH 1B / PRM
(300,0.2)
10k
100.00%
31.41
0.8072
10,960.73
10,924.63
2,877.86
73.66% [73.58,73.73]
MATH 3B / PRM
(300,0.2)
10k
100.00%
17.05
0.8053
8,420.40
8,385.05
1,522.91
81.84% [81.79,81.89]
TabRepo / random
(100,0.1)
10k
100.00%
1.30
0.9522
124.78
118.68
100.87
15.00% [14.78,15.25]
TabRepo / consensus
(100,0.1)
10k
100.00%
1.00
0.9791
243.88
225.91
92.79
58.93% [58.35,59.49]
TREC / BM25
(40,0.1)
2k
100.00%
16.82
0.8985
263.70
261.99
209.00
20.23% [19.85,20.60]
Table 1: Calibration queries and prediction outcomes under exact threshold recovery. Within each row, Exact, Serial, and Layer recover identical thresholds and prediction sets. The upper block reports the main settings; the lower block raises target coverage for TREC and MATH to 90%. Exact, Serial, and Layer report mean query counts; Size is mean prediction-set size; Finite is the fraction of splits with q<∞ . Hit is the fraction whose returned set contains an acceptable candidate for the held-out example; examples without an acceptable candidate count as misses. All means include infinite-threshold splits, which return the full available pool. Savings are computed from mean costs, with 95% paired split-bootstrap intervals.
Figure 2: Query savings and overhead relative to minimum prefix evidence. Left: decomposition of complete-verification cost into the minimum prefix certificate, excess layered work, final-layer negative queries, terminal-layer saving, and saved search tails. Right: mean per-split cost ratio T/W , with horizontal bars showing the 10th–90th percentiles. The labels γ give the worst-case bounds from Theorem 3. Results use the 10,000 splits of each main setting in Table 1.
Figure 3: Synthetic test of the predicted verification overhead. We vary threshold depth and the number of boundary ties while holding above-threshold search cost fixed. For each constructed instance, we run Layer over the same 200 visitation permutations and compare mean overhead Ω=T−W and cost ratio T/W with their analytical predictions from Proposition 2 . Relative overhead peaks at intermediate tie counts. Intervals are 95% paired-permutation bootstrap intervals.
Figure 4: Effect of calibration sample size on verification cost and prediction-set size for MATH at α=0.2 . Points use 2,000 paired splits. Labels give Layer sample sizes; stars mark full size. Error bars are pointwise 95% split-bootstrap intervals for the means; lines connect evaluated sizes.
Appendix figures & tables17 assets
Supplementary material from the paper’s appendix.
Appendix
Step
Setting
Reference
Strip whitespace and outer math delimiters, wrap in … , parse with LatexExtractionConfig
Completion
LatexExtractionConfig(boxed_match_priority=0) , then ExprExtractionConfig
Table 2: math-verify 0.9.0 settings for MATH acceptance.
Figure 5: Constructed saved tails at fixed quantile q , with 200 example orders per setting. The completed-layer saving is exactly 9(τ−q) . Serial is cheaper when τ=q .
Figure 6: Certificate slack under a common all-candidate query trace, with 2,000 paired splits per setting. The supplied lower bound Lx=mx−Δ varies with Δ ; the observed-minimum upper bound Ux(Mx) is the same across Δ at each point of the common trace. Infinite thresholds contribute the full test pool to mean size.
Figure 7: MATH pool-size controls at α=0.2 . Each pool contains the first K completions, selected before ranking. Mean costs include splits with infinite thresholds. The two PRM rows at K=256 use 10,000 splits and the other rows 2,000.
Figure 8: MATH 3B with five generation seeds on the same 500 problems, at K=256 and α=0.2 . Each seed gives a separate candidate pool. Error bars are 95% split-bootstrap intervals. PRM seed 0 uses the 10,000 splits of the main comparison and the other rows 2,000.
q=2
q=16
q=64
e
W
Overhead
Serial
W
Overhead
Serial
W
Overhead
Serial
1
100.00
4.55
180.10
240.00
4.55
320.10
720.00
4.55
800.10
2
100.00
7.04
180.91
240.00
21.05
333.51
720.00
69.05
856.71
5
100.00
11.43
183.90
240.00
67.42
378.36
720.00
259.43
1045.08
10
100.00
17.28
188.90
240.00
143.28
453.36
720.00
575.28
1360.08
30
120.00
17.73
208.90
540.00
143.72
753.36
1980.00
575.73
2620.08
Appendix
Table 3: Boundary-tie costs in queries, using 200 common visitation permutations for every cell and fixed above-quantile tail mass 72. Overhead is the mean Ω=T−W ; Serial is the mean Ts with the same bracket.
q
e
Theory
Empirical
95% interval
2
1
8.250
7.384
[6.339, 8.352]
2
2
6.000
6.184
[5.250, 7.160]
2
5
2.679
2.999
[2.461, 3.534]
2
10
1.240
1.338
[0.930, 1.746]
2
30
0.351
0.371
[0.226, 0.564]
2
90
0.106
0.118
[0.065, 0.182]
Appendix
Table 4: Conditional scheduling variance of T (queries squared) on each fixed synthetic table. Empirical variance uses 200 archived visitation permutations and the unbiased sample formula. Intervals are 95% percentile intervals from 2,000 permutation bootstrap resamples, using the same resampled permutation IDs in all 18 conditions. They describe scheduling Monte Carlo uncertainty conditional on each fixed table.
n′
Exact
Serial
Layer
Size
SD
P90
Finite (a)
Hit
Saving vs. Serial
TREC / BM25, α=0.1
9
58.72
54.67
58.70
33.200
43.04
90
0.8265
0.8895
-7.37%
10
65.55
60.30
65.52
35.626
44.56
103
0.8060
0.9025
-8.67%
20
130.91
128.68
111.98
20.943
18.10
30
0.9655
0.9030
12.98%
40
263.70
261.99
209.00
16.824
3.78
19
1.0000
0.8985
20.23%
TREC / BM25, α=0.2
Appendix
Table 5: All 58 policy-by-size comparisons on 2,000 common splits per cell. Exact, Serial and Layer have identical thresholds and sets at each size. Costs and size are unconditional means; SD and P90 describe the size distribution. Finite and Hit are rates. Complete intervals and spending quantiles are in the supplied CSV.
Table 6: Small-sample Layer minus full-sample Layer, with pointwise 95% paired split-bootstrap intervals. Negative cost differences favor the smaller sample. Positive size differences mean that it returns larger sets. Same- q includes jointly infinite thresholds.
Figure 9: Policy-by-size comparisons for TREC and MATH 1B at both risk levels, with 2,000 matched splits per cell. At each size, Exact, Serial, and Layer return the same predictor. Labels give Layer sample sizes, stars mark the full size, and error bars are pointwise 95% split-bootstrap intervals for mean cost and size.
Figure 10: Policy-by-size comparisons for MATH 3B and TabRepo, continuing Figure 9 .
ε
Finite (a)
Size
Hit
Exact
Serial
Layer
Query saving
Time saving
0.05
0.0000
1,517.19
0.4790
42,157.0
7,596.4
41,267.1
-443.25 [-445.54,-440.97]%
-451.46 [-475.73,-427.99]%
0.10
0.0000
1,517.19
0.6550
27,615.7
7,678.2
27,171.5
-253.88 [-256.10,-251.74]%
-255.22 [-268.98,-242.27]%
0.15
0.0010
1,516.35
0.7575
20,038.5
7,716.0
19,838.2
-157.10 [-159.17,-155.10]%
-152.93 [-161.15,-145.21]%
0.20
0.0090
1,504.90
0.8225
14,222.9
7,622.9
14,142.1
-85.52 [-87.40,-83.74]%
-80.90 [-86.00,-76.39]%
0.30
0.9240
224.51
0.9205
4,814.2
4,690.3
1,245.5
73.44 [71.56,75.32]%
65.61 [63.25,67.84]%
0.40
1.0000
1.00
0.9760
1,526.7
1,425.6
51.3
96.40 [96.28,96.52]%
65.07 [63.94,66.05]%
Appendix
Table 7: Direct absolute-loss TabRepo acquisition: 117 ROC-AUC tasks, 54 fitting and 54 calibration tasks, α=.1 , 2,000 paired splits per tolerance. All three policies return identical sets. Costs include infinite thresholds. Query/time savings are relative to Serial, with pointwise 95% paired intervals; time sums source-recorded three-fold training durations.
ε
Exact sec.
Serial sec.
Layer sec.
Deploy queries
Deploy sec.
New-fit query saving
New-fit time saving
0.05
23,492,660
4,255,867
23,469,581
791.13
410,173
-37.27%
-44.71%
0.10
14,577,321
4,099,711
14,563,061
528.66
248,828
-21.62%
-24.53%
0.15
13,135,252
5,190,180
13,127,535
374.29
225,476
-13.46%
-18.15%
0.20
10,434,048
5,745,924
10,394,344
269.89
184,409
-7.26%
-10.51%
0.30
4,003,765
3,895,277
1,339,580
7.97
7,080
3.98%
6.05%
0.40
204,596
192,364
67,185
1.00
1,248
1.65%
0.33%
Appendix
Table 8: Absolute-target cost ledger. All time entries are cumulative source-recorded seconds. New-fit savings add consensus fitting and one deployment to both policies. Query and time savings use their respective units.
Task / ranking
Fitting
Serial cal.
Layer cal.
Deploy
Saving at D=1 / D=1000 (%)
New fit D=1
verification queries
TREC / BM25
—
260.69
173.51
4.23
32.91% / 1.94%
—
MATH 1B / PRM
—
10,924.63
2,877.86
9.26
73.59% / 39.86%
—
MATH 3B / PRM
—
8,385.05
1,522.91
4.96
81.79% / 51.42%
—
TabRepo / random
—
118.68
100.87
1.06
14.87% / 1.51%
—
TabRepo / consensus
151,059.50
225.91
92.79
1.00
58.67% / 10.86%
0.088%
Appendix
Table 9: Measured cost ledger for the main settings. Query counts and cumulative source-recorded fitting seconds form separate ledger rows. Supplied-ranking savings include calibration and D deployments; the last column additionally includes fitting a new TabRepo consensus ranking.
Figure 11: Acquisition trajectories under budget caps, with 2,000 paired splits at the risk levels in the panel titles. Top: mean returned size, with pointwise 95% split-bootstrap bands. Bottom: probability of a finite threshold, literal hit rate, and score coverage.
Figure 12: Top: mean calibration cost of Exact, Serial, and Layer on the main settings, with 10,000 paired splits per setting. Bottom: cost–size curves on 2,000 splits, where Exact uses smaller calibration samples chosen before their verdicts are seen. Each sample size defines its own reference predictor. Error bars and bands are 95% split-bootstrap intervals.
Figure 13: Simultaneous tolerance frontiers at α=0.1 . ECDF supremum, shared normalizer, pointwise, and Bonferroni use 10,000 splits, and finite-top uses the first 2,000 of them. All constructions in a setting read the same query history. Bottom: probability of selecting a tolerance at deployment depth 10 for TREC and 30 for TabRepo. Shaded regions are pointwise 95% intervals. Finite-top removes finite-score saturation.
Conformal prediction (CP) is a widely used frequentist framework to quantify uncertainty by constructing prediction sets with user-specified marginal coverage guarantees. In practice, CP is typically applied on top of probabilistic classifiers, which are able to express aleatoric but not epistemic uncertainty. In this paper, we consider the question of how to optimally employ CP on top of a more expressive formalism, namely credal sets, which can express both aleatoric and epistemic uncertainty. More specifically, we propose probabilistic Bernoulli prediction sets (BPS) and derive a variant that achieves conditional coverage for valid credal sets while remaining minimal in expected size. We then address the more realistic scenario in which the validity of the credal sets is not guaranteed. Assuming access to calibration data with ground-truth distributions over labels, we apply conformal risk control to BPS and derive a PAC-style guarantee: with high probability over the data, the achieved conditional coverage is at least the desired level. We validate our theoretical findings empirically over various datasets.
Alireza Javanmardi, Soroush H. Zargarbashi, Santo M. A. R. Thies +3
A point prediction that is well calibrated on average can still be systematically biased conditional on its own value, undermining its use in downstream decision-making. We consider two objectives for reliable uncertainty quantification: self-calibration, requiring a point prediction to be unbiased conditional on its own value, and prediction-conditional validity, requiring a prediction interval to attain nominal coverage conditional on the prediction. Self-Calibrating Conformal Prediction (SC-CP) attains both objectives exactly in finite samples, but requires refitting its calibrator for every candidate outcome, which is computationally prohibitive for continuous outcomes. We propose Isotonic Conformal Prediction (ICP), a framework that decouples calibration from prediction-set construction by fitting a single isotonic recalibration map and constructing prediction intervals within strata of similar recalibrated predictions. Within this framework we develop two procedures. Split Isotonic Conformal Prediction (SICP) attains prediction-conditional validity in finite samples and self-calibration asymptotically, at the computational cost of split conformal prediction. Transductive Isotonic Conformal Prediction (TICP) attains both objectives exactly in finite samples through a per-test-point inner loop that avoids refitting the isotonic calibrator. On synthetic heteroscedastic regression problems and a real-world healthcare-utilization dataset, both procedures match the coverage of SC-CP at substantially lower computational cost.
Daniel Bensimon, Sean Xiang Yu, Eric D. Kolaczyk +1
Department of Mathematics and Statistics, McGill University; Mila · Eli Lilly and Company
Conformal prediction is a useful and versatile alternative to model calibration in machine learning classification. It replaces single-class prediction with prediction sets, guaranteeing that the a priori probability of the prediction sets containing the true class is larger than or equal to a pre-specified rate. The size and usefulness of the prediction sets relies heavily on the choice of the non-conformity score function. The scientific literature contains many examples of non-conformity score functions but there is an absence of studies examining their properties and effectiveness. In this paper, we give an overview of properties of non-conformity score functions. We give examples of non-conformity score functions in the existing literature and introduce original modifications. We introduce an original method of evaluating the prediction set sizes of conformal predictors and use it to provide a comparison between non-conformity score functions. We also examine efficacy of different non-conformity score functions for class-conditional conformal prediction in a setting with imbalanced classes.
Sol Erika Boman
Department of Medical Epidemiology and Biostatistics, Karolinska Institutet · Department of Molecular Medicine and Surgery, Karolinska Institutet