Conformal Prediction under Partial Verification

Zijun Yu; Yu Gu; Vahid Partovi Nia; Masoud Asgharian

stat.MLOct 7, 2026

Conformal Prediction under Partial Verification

Authors: Zijun Yu, Yu Gu, Vahid Partovi Nia, Masoud Asgharian

Organizations: McGill University · Polytechnique de Montréal

Abstract

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,\alpha)$	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<\infty

. 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

\gamma

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

\Omega=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

\alpha=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
Extraction	fallback_mode="no_fallback" , extraction_mode="first_match"
Comparison	float_rounding=6 , numeric_precision=15 , strict=True , allow_set_relation_comp=False
Timeouts	5 s for each parse and for verify
Errors	raise_on_error=True for parsing and verify

Appendix

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(\tau-q)

. Serial is cheaper when

\tau=q

Figure 6: Certificate slack under a common all-candidate query trace, with 2,000 paired splits per setting. The supplied lower bound

L_{x}=m_{x}-\Delta

varies with

\Delta

; the observed-minimum upper bound

U_{x}(M_{x})

is the same across

\Delta

at each point of the common trace. Infinite thresholds contribute the full test pool to mean size.

Figure 7: MATH pool-size controls at

\alpha=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

\alpha=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

\Omega=T-W

; Serial is the mean

T_{s}

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^{\prime}$	Exact	Serial	Layer	Size	SD	P90	Finite (a)	Hit	Saving vs. Serial
TREC / BM25, $\alpha=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, $\alpha=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.

$n^{\prime}$	$\Delta$ queries [95% CI]	$\Delta$ size [95% CI]	Same $q$	Finite pairs (a)
TREC / BM25, $\alpha=0.1$ ; full $n=40$ : Layer 209.00, size 16.824
9	-150.30 [-151.92,-148.65]	16.377 [14.591,18.323]	0.1350	1653/2000
10	-143.47 [-145.09,-141.79]	18.802 [16.956,20.837]	0.1435	1612/2000
20	-97.02 [-98.48,-95.56]	4.119 [3.409,4.960]	0.2615	1931/2000
40	0.00 [0.00,0.00]	0.000 [0.000,0.000]	1.0000	2000/2000
TREC / BM25, $\alpha=0.2$ ; full $n=40$ : Layer 172.75, size 10.431

Appendix

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 .

$\varepsilon$	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,

\alpha=.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.

$\varepsilon$	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.

verification queries
Task / ranking	Fitting	Serial cal.	Layer cal.	Deploy	Saving at $D=1$ / $D=1000$ (%)	New fit $D=1$
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

\alpha=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.

Explore similar work

Optimal Conformal Prediction under Epistemic Uncertainty
May 25, 2025Alireza Javanmardi, Soroush H. Zargarbashi, Santo M. A. R. Thies +3Conformal Prediction Conformal Risk Control
1LMU Munich · 2MCML · 3CISPA +3
Isotonic Conformal Prediction
Jul 18, 2026Daniel Bensimon, Sean Xiang Yu, Eric D. Kolaczyk +1Conformal Prediction Uncertainty Calibration
Department of Mathematics and Statistics, McGill University; Mila · Eli Lilly and Company
Benchmarking non-conformity score functions in conformal prediction
Date pendingSol Erika BomanSet Prediction Conformal Prediction
Department of Medical Epidemiology and Biostatistics, Karolinska Institutet · Department of Molecular Medicine and Surgery, Karolinska Institutet

May 25, 2025, stat.MLJ/K move · Enter open · S save

Optimal Conformal Prediction under Epistemic Uncertainty

Alireza Javanmardi, Soroush H. Zargarbashi, Santo M. A. R. Thies, Willem Waegeman+2

1LMU Munich · 2MCML · 3CISPA+3

Conformal Prediction Conformal Risk Control Epistemic Uncertainty

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Optimal Conformal Prediction under Epistemic Uncertainty

Isotonic Conformal Prediction

Benchmarking non-conformity score functions in conformal prediction