Generative Conformal Prediction with Optimized Coverage Allocation

Minxing Zheng; Shixiang Zhu

cs.LGOct 17, 2024

Generative Conformal Prediction with Optimized Coverage Allocation

Authors: Minxing Zheng, Shixiang Zhu

Organizations: University of Southern California · Carnegie Mellon University

Abstract

Conformal prediction provides model-agnostic uncertainty quantification with guaranteed coverage, but conventional methods often yield overly conservative uncertainty sets, particularly in multimodal or heterogeneous settings. This inefficiency arises from two sources: (i) limited expressiveness of the predictive model and (ii) simplistic nonconformity score design. Most existing approaches advance only one of these axes, leaving the other underexplored. We propose generative conformal prediction with Optimized Ranking and Coverage Allocation (ORCA), a three-stage framework that advances both aspects jointly. ORCA leverages generative models to capture the full conditional distribution and introduces a rank-dependent optimization procedure that adaptively allocates coverage for efficiency while maintaining validity. We cast this coverage allocation as an optimization problem, derive an exact mixed-integer linear programming formulation, and show that the solution converges asymptotically to the oracle density-level set. Across synthetic, semi-synthetic, and real datasets, ORCA produces substantially more efficient uncertainty sets than state-of-the-art baselines, demonstrating robust gains in scenarios where conventional conformal prediction methods fail.

Figures & tables

Figure 1: Comparison of conformal prediction methods and their prediction regions. From left to right: standard CP [ 1 ] , Bonferroni-corrected CP [ 9 ] , Covariance Weighted CP [ 10 , 11 ] , PCP [ 12 ] , and ORCA (our method). The background gradient shows the multimodal data distribution. ORCA adjusts circle radii via ranking—larger in dense areas, smaller in sparse ones—yielding more efficient and flexible prediction sets. Green dots denote true responses ( $Y_{i}$ ), black dots are generated samples ( $\hat{Y}_{i,k}$ ), and dashed lines mark prediction boundaries ( $\mathcal{C}_{k}$ ).

Figure 2: Empirical coverage and uncertainty-set efficiency on synthetic datasets. Each panel reports marginal coverage versus prediction-set efficiency on a log scale; smaller efficiency is better. The dashed horizontal line marks the nominal coverage level $0.90$ , and vertical bars show the standard error for marginal coverage. ORCA performs best overall.

Figure 3: MNIST digit generation coverage. Samples from PCP and ORCA uncertainty sets across target digits (rows). ORCA yields more semantically consistent samples with target digit number and a lower off-class rate (OCR) than PCP ( $0.16\pm 0.02$ vs. $0.22\pm 0.03$ ).

Figure 4: Empirical coverage and uncertainty-set efficiency on real datasets. Each panel reports marginal coverage versus prediction-set efficiency on a log scale; smaller efficiency is better. The dashed horizontal line marks the nominal coverage level $0.90$ , and vertical bars show the standard error for marginal coverage. ORCA performs best overall.

Panel of Figure 5 — Figure 5: Comparison of prediction sets across methods with the highest efficiency on the Bike dataset. The colored region indicates the set, and the red marker denotes the target location.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

U^{(\gamma)}=\left\{i\in[n_{1}]:\exists r\in[K]\ \text{s.t.}\ a_{i,r,\ell_{r}^{(\gamma)}}=1\right\}

Appendix

Algorithm 2 ORCA -LP: LP relaxation with prefix rounding

\Delta_{\mathrm{cov}}(r,h)=\left|\left\{i\notin U:a_{i,r,h}=1\right\}\right|

Appendix

Algorithm 3 ORCA -Greedy: jump-based partial cover

Dataset	# Features	Response Dimension	# Samples
Blog Feedback (Blog) [ 45 ]	$280$	$1$	$52{,}397$
Facebook Comment Volume (Fb1) [ 46 ]	$53$	$1$	$40{,}948$
Facebook Comment Volume (Fb2)	$53$	$1$	$81{,}311$
MEPS (Year 19) 2 2 2 https://meps.ahrq.gov/mepsweb/	$139$	$1$	$15{,}785$
MEPS (Year 20)	$139$	$1$	$17{,}541$
MEPS (Year 21)	$139$	$1$	$15{,}656$

Appendix

Table 1: Summary of real-world datasets.

Figure 6: Comparison of prediction set ( $\alpha=0.1$ ) generated by different methods on $1$ -dimensional synthetic data: S-shape, Circles, Spirals, and Unbalanced clusters (from top to bottom row). Blues lines: the predictive intervals of each method; Black dots: test points that are covered by the predictive sets; Reds dots: test points not covered. We plot the figure with $100$ , $500$ , $400$ , and $500$ random samples for each data, respectively.

Figure 7: Ratio of PCP prediction set length over ORCA prediction set length under different $K=3,5,10,15,20$ and number of calibration data for S-shape data. The blue curve represents the mean, and the shaded area indicates the standard error of the ratio. We observe that the ratio remains consistently above 1, demonstrating that ORCA achieves better efficiency.

Dataset	Metric	CQR	CHR	DCP	DistSplit	CDSplit	CRD	R2CCP	PCP	ORCA
Circles	Cover	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$
	Cond_Cover	$0.85\pm 0.04$	$0.84\pm 0.05$	$0.86\pm 0.03$	$0.86\pm 0.03$	$0.87\pm 0.03$	$0.80\pm 0.03$	$0.86\pm 0.01$	$0.85\pm 0.03$	$0.86\pm 0.03$
	Eff	$1.70\pm 0.01$	$1.49\pm 0.06$	$1.64\pm 0.04$	$1.64\pm 0.05$	$0.72\pm 0.04$	$1.61\pm 0.01$	$2.77\pm 0.04$	$0.68\pm 0.31$	$\mathbf{0.63\pm 0.24}$
Moon	Cover	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.92\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.02$
	Cond_Cover	$0.85\pm 0.05$	$0.87\pm 0.08$	$0.87\pm 0.06$	$0.85\pm 0.06$	$0.87\pm 0.05$	$0.78\pm 0.03$	$0.86\pm 0.02$	$0.85\pm 0.03$	$0.85\pm 0.04$
	Eff	$0.69\pm 0.05$	$0.69\pm 0.08$	$0.77\pm 0.06$	$0.75\pm 0.06$	$0.42\pm 0.03$	$0.33\pm 0.03$	$1.84\pm 0.11$	$0.35\pm 0.04$	$\mathbf{0.29\pm 0.04}$

Appendix

Table 2: Summary of synthetic data results.

Dataset	Metric	CQR	CHR	DCP-CQR	DistSplit	CDSplit	CRD	R2CCP	PCP	ORCA
Fb1	Cover	$0.90\pm 0.00$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.00$	$0.92\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.01$	$0.90\pm 0.02$
	Cond_Cover	$0.87\pm 0.02$	$0.86\pm 0.05$	$0.88\pm 0.00$	$0.89\pm 0.03$	$0.87\pm 0.07$	$0.83\pm 0.03$	$0.76\pm 0.04$	$0.82\pm 0.03$	$0.80\pm 0.05$
	Eff	$14.78\pm 2.31$	$11.23\pm 1.34$	$13.73\pm 1.55$	$15.88\pm 2.07$	$35.09\pm 2.69$	$54.07\pm 40.50$	$12.97\pm 0.82$	$7.79\pm 0.28$	$\mathbf{3.70\pm 1.75}$
Fb2	Cover	$0.90\pm 0.01$	$0.89\pm 0.01$	$0.90\pm 0.02$	$0.90\pm 0.01$	$0.93\pm 0.01$	$0.90\pm 0.02$	$0.90\pm 0.02$	$0.90\pm 0.01$	$0.90\pm 0.01$
	Cond_Cover	$0.88\pm 0.02$	$0.84\pm 0.04$	$0.89\pm 0.05$	$0.89\pm 0.01$	$0.87\pm 0.08$	$0.84\pm 0.03$	$0.73\pm 0.05$	$0.82\pm 0.03$	$0.80\pm 0.04$
	Eff	$18.31\pm 1.57$	$10.12\pm 1.04$	$10.54\pm 1.12$	$14.48\pm 1.43$	$44.41\pm 1.61$	$56.26\pm 2.64$	$13.39\pm 1.65$	$9.35\pm 0.21$	$\mathbf{5.68\pm 1.62}$

Appendix

Table 3: Summary of real data results.

#leaf	Cov.	CondCov.	Eff ( ORCA )	$\frac{\mathrm{Eff(\texttt{ORCA})}}{\mathrm{Eff(PCP)}}$	$\frac{\mathrm{Eff(\texttt{ORCA})}}{\mathrm{Eff(CHR)}}$
1	0.90	0.86	3.99	1.00	1.14
20	0.89	0.84	0.11	0.84	0.03
50	0.90	0.85	0.21	0.87	0.06
100	0.90	0.87	0.52	0.85	0.16
200	0.90	0.85	0.77	1.03	0.22

Appendix

Table 4: Sensitivity to conditional model quality (QRF). Varying #leaf controls the quality of

\hat{p}(y\mid x)

. We report marginal coverage (Cov.), conditional coverage (CondCov.), ORCA efficiency (Eff.), and efficiency ratios relative to PCP/CHR (smaller is better).

	Number of neighbors $m$
Method	1	4	7	10	13	16	19
ORCA -MILP	-0.022	-0.199	0.264	0.318	0.316	0.289	0.279
ORCA -LP	-0.727	-1.131	0.159	0.229	0.269	0.293	0.275

Appendix

Table 5: Sensitivity to

m

-NN ranking. ORCA efficiency improvement over PCP as a function of the

m

-NN parameter; moderate

m

stabilizes ranking and yields consistent gains.

	time (s) / Eff.
Method	$K{=}10$	$15$	$20$	$25$
PCP	0.00/0.75	0.00/0.48	0.00/0.37	0.00/0.34
ORCA -MILP	11.95/0.67	16.97/0.35	23.15/0.32	40.96/0.31
ORCA -LP	1.50/0.67	2.88/0.37	5.22/0.34	8.94/0.36
ORCA -Greedy	0.02/0.66	0.03/0.35	0.06/0.32	0.09/0.32
ORCA -Naive	174.12/0.69	442.16/0.37	548.92/0.35	665.89/0.33

Appendix

Table 6: Runtime and efficiency vs.

K

Metric	PCP Cover	PCP OCR	ORCA Cover	ORCA OCR
Pixel-space $\ell_{2}$	0.899	0.374	0.900	0.338
Latent-space $\ell_{2}$	0.909	0.178	0.908	0.123
Latent cosine distance	0.906	0.090	0.897	0.054
Learned latent metric	0.901	0.062	0.905	0.019

Appendix

Table 7: Metric ablation on MNIST-VAE. We compare PCP and ORCA under different output-space metrics. Coverage is reported together with the off-class rate (OCR), where smaller OCR indicates fewer semantically incorrect images included in the prediction set.

Explore similar work

Online Conformal Prediction: Enforcing monotonicity via Online Optimization
May 12, 2026Eduardo Ochoa Rivera, Ambuj TewariConformal Prediction Uncertainty Calibration
University of Michigan · Ann Arbor, USA
Sample-Efficient Generative Conformal Prediction
Oct 8, 2026Minxing Zheng, Shixiang ZhuConformal Prediction Adaptive Sampling
Carnegie Mellon University
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

May 12, 2026J/K move · Enter open · S save

Online Conformal Prediction: Enforcing monotonicity via Online Optimization

Eduardo Ochoa Rivera, Ambuj Tewari

University of Michigan · Ann Arbor, USA

Conformal Prediction Uncertainty Calibration

Open paper AskPDF arXiv

Conformal prediction provides a principled framework for uncertainty quantification with finite-sample coverage guarantees. While recent work has extended conformal prediction to online and sequential settings, existing methods typically focus on a single coverage level and do not ensure consistency across multiple confidence levels. In many real-world applications, such as weather forecasting, macroeconomic prediction, and risk management, different users operate under heterogeneous risk tolerances and require calibrated uncertainty estimates across a range of coverage levels. In such settings, it is desirable to produce prediction sets corresponding to different coverage levels that are nested and valid simultaneously. In this paper, we propose two novel online conformal prediction methods that output nested prediction sets across a range of coverage levels, enabling simultaneous uncertainty quantification across the entire risk spectrum. Beyond interpretability, jointly estimating multiple coverage levels is known to improve statistical efficiency in classical quantile regression by enforcing non-crossing constraints and sharing information across quantiles. Our approaches leverage an online optimization perspective with small regret that translates to quantile estimation error control while enforcing nestedness of prediction sets. Empirical results on synthetic and real-world datasets, including applications in forecasting tasks with heterogeneous risk requirements, demonstrate that our method achieves stable coverage across all levels, strictly nested prediction sets, and improved efficiency compared to existing online conformal baselines.

Abstract

Explore similar work

Online Conformal Prediction: Enforcing monotonicity via Online Optimization

Sample-Efficient Generative Conformal Prediction

Optimal Conformal Prediction under Epistemic Uncertainty