Conformal Prediction Sets Quantify Information Gain: A Theoretical Perspective

Kevin Zhang; Stephen Bates

cs.LGOct 6, 2026

Conformal Prediction Sets Quantify Information Gain: A Theoretical Perspective

Authors: Kevin Zhang, Stephen Bates

Organizations: EECS, MIT, Cambridge MA, USA.

Abstract

Conformal prediction is a popular tool for uncertainty quantification that outputs prediction sets with finite-sample coverage guarantees. While prediction set size is commonly used as a heuristic measure of uncertainty, the information-theoretic basis for this interpretation remains poorly understood. In this work, we provide such a foundation using a decision-theoretic generalization of entropy tailored to set-valued prediction. In particular, we introduce a family of generalized information measures based on the size and coverage of conformal prediction sets. Notably, Shannon mutual information admits an exact integral representation in terms of these measures. We then show that, in standard classification settings, the reduction in conformal set size from additional information (i) is sandwiched between calibration-dependent members of this family and (ii) obeys a data processing inequality, both up to finite-sample calibration and model error terms. Together, our results formally relate conformal prediction to classical information-theoretic quantities and justify using set-size reduction as an information gain metric. Empirically, we validate our theory across 11 classification settings and show that set-size reduction and Shannon mutual information can rank features differently in a greedy feature selection experiment.

Figures & tables

Panel of Figure 1 — Figure 1: We illustrate an example of our setting in ( 1(a) ), where $Z$ is a low-resolution image and $X$ is its residual. The information gain of $X$ beyond $Z$ can be quantified by $\Delta_{\alpha}$ . We develop the information hierarchy in ( 1(b) ), showing that conformal mutual information near the calibrated $\lambda$ approximates $\Delta_{\alpha}$ , while Shannon mutual information aggregates the entire family (Theorem 1 ).

Figure 2: Conformal mutual information accurately reflects feature utility for reducing set size, whereas Shannon mutual information may not. We show information profiles $\lambda\mapsto I_{\lambda}(X_{i};Y\mid Z)$ for two candidate features $X_{1}$ and $X_{2}$ with similar Shannon mutual information (left), along with their differences in $I_{\lambda}$ and $\mathbb{E}[\Delta_{\alpha}]$ using the probability score (right). Nominal miscoverage levels $\alpha\in\{0.01,0.1,\ldots,0.9,0.99\}$ are indicated along the top axis. Despite having nearly identical Shannon mutual information, $X_{1}$ yields a larger conformal set-size reduction at high coverage ( $1-\alpha>0.6$ ) , whereas $X_{2}$ reduces set size more at low coverage levels. Each difference in $\mathbb{E}[\Delta_{\alpha}]$ is positioned at the geometric mean of the two calibrated thresholds.

Figure 3: We show the normalized margin, width, and DPI gap based on $100$ random draws of the calibration and test sets from the fixed evaluation pool. The margin and width panels report the mean $\pm$ standard error , while the DPI gap panel summarizes the distribution using boxplots. Datasets whose evaluation pool is too small for a given calibration size are omitted.

Dataset	Criterion	Prob.		APS		Acc.
Dataset	Criterion	$\mathbb{E}[\|\mathcal{C}\|]$ ( $\downarrow$ )	Cov.	$\mathbb{E}[\|\mathcal{C}\|]$ ( $\downarrow$ )	Cov.	Top-1 ( $\uparrow$ )	Top-5 ( $\uparrow$ )
S3 ( $K=40$ )	$\Delta_{\alpha}$ (Prob.)	$\mathbf{2.239\pm 0.002}$	$0.900\pm 0.000$	$2.629\pm 0.002$	$0.900\pm 0.000$	$0.750\pm 0.001$	$\mathbf{0.952\pm 0.000}$
	$\Delta_{\alpha}$ (APS)	$2.243\pm 0.002$	$0.900\pm 0.000$	$\mathbf{2.611\pm 0.002}$	$0.900\pm 0.000$	$0.752\pm 0.000$	$\mathbf{0.952\pm 0.000}$
	Shannon MI	$2.447\pm 0.005$	$0.900\pm 0.000$	$2.876\pm 0.006$	$0.900\pm 0.000$	$0.767\pm 0.000$	$\mathbf{0.952\pm 0.000}$
	Accuracy	$3.613\pm 0.020$	$0.900\pm 0.000$	$4.487\pm 0.029$	$0.900\pm 0.000$	$\mathbf{0.768\pm 0.001}$	$0.914\pm 0.001$
	Random	$3.046\pm 0.100$	$0.900\pm 0.000$	$3.591\pm 0.116$	$0.900\pm 0.000$	$0.672\pm 0.009$	$0.931\pm 0.004$

Table 1: We evaluate feature selection performance using conformal set-size reduction. Each row represents one selection criterion and values are reported as mean

\pm

standard error over 10 random splits of the evaluation pool. Arrows indicate the direction of improvement, and the best-performing method for each metric is bolded. Empirical coverage is reported for reference without bolding.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	$n_{\mathrm{total}}$	$n_{\mathrm{eval}}$	$d_{\mathrm{total}}$	$d_{X}$	$d_{Z}$	$m$	$K$
S1	200,000	200,000	4	2	2	—	10
S2	200,000	200,000	20	10	10	10	50
S3	200,000	200,000	58	50	8	50	40
Wine	4,898	1,224	11	6	5	11	7
HAR	10,299	2,575	561	348	213	51	6
Letter	20,000	5,000	16	9	7	16	26

Appendix

Table 2: Sample sizes, feature dimensions, and number of classes for all datasets. For the synthetic datasets S1–S3, the conditional distributions are known and no training data are required. Here,

n_{\mathrm{eval}}

denotes the number of samples available for calibration and evaluation. For tabular datasets, the input features are partitioned into

X

and

Z

. For image datasets,

X

and

Z

correspond to separate image representations with the indicated channel dimensions. The number of candidate features in the feature selection experiments is denoted by

m

Figure 4: Examples of the original image, base, new, and degraded features for each image dataset. The degraded features apply an additional Gaussian blur with standard deviation $\gamma\sigma$ to $X$ .

Dataset	Params.	Max. epochs	Patience	Learning rate	Weight decay	Dropout
Wine	600	1,000	100	$4\times 10^{-4}$	$1\times 10^{-4}$	$0.3$
HAR	178K	1,000	100	$4\times 10^{-4}$	$1\times 10^{-4}$	$0.1$
Letter	106K	1,000	100	$1\times 10^{-3}$	$1\times 10^{-4}$	$0.2$
Covertype	424K	500	100	$4\times 10^{-4}$	$1\times 10^{-5}$	$0.1$
FMNIST	105K	1,000	100	$1\times 10^{-3}$	$4\times 10^{-5}$	$0.3$
CIFAR-10	414K	500	100	$1\times 10^{-3}$	$1\times 10^{-4}$	$0.1$

Appendix

Table 3: Selected hyperparameters and training configurations for the classification models. The learning rate, weight decay, and dropout rate are selected via grid search. The maximum number of epochs and patience correspond to the full training procedure after hyperparameter selection.

Dataset	$(X,Z)$	$(\tilde{X},Z)$ low noise	$(\tilde{X},Z)$ medium noise	$(\tilde{X},Z)$ high noise	$Z$	Mask-conditioned (all)
S1	56.52	54.86	51.83	46.69	39.33	—
S2	50.83	48.84	44.00	34.21	18.43	—
Wine	55.15	54.98	53.43	52.78	50.33	55.80
HAR	98.29	97.40	96.54	93.86	88.08	98.72
Letter	97.68	95.52	92.00	86.76	86.52	97.36
Covertype	96.24	83.11	74.93	68.85	65.16	94.12

Appendix

Table 4: Top-1 classification accuracy (%) on the held-out evaluation pool for the augmented, degraded, and base feature sets, and for the mask-conditioned model with all candidate features observed. For the synthetic datasets S1 and S2, we report the accuracy of the oracle model.

Figure 5: Empirical marginal coverage of the conformal predictors using $(X,Z)$ over 100 random equal calibration and test splits of the evaluation pool. The dashed line indicates the nominal coverage level $1-\alpha=0.9$ .

Figure 6: We show the normalized margin and violation rate as we jointly vary $n_{\mathrm{cal}}$ and $n_{\mathrm{test}}$ (left and middle) and the normalized width as we vary $n_{\mathrm{cal}}$ while keeping $n_{\mathrm{test}}$ fixed (right). All panels report the mean $\pm$ standard error based on $100$ random draws of the calibration and test sets from the fixed evaluation pool.

Figure 7: We show the normalized margin as we vary $n_{\mathrm{cal}}$ and $n_{\mathrm{test}}$ jointly (left) or independently (middle and right). All panels report the mean $\pm$ standard error based on $100$ random draws of the calibration and test sets from the fixed evaluation pool.

Figure 8: We show the violation rate as we vary $n_{\mathrm{cal}}$ and $n_{\mathrm{test}}$ jointly (left) or independently (middle and right). All panels report the mean $\pm$ standard error based on $100$ random draws of the calibration and test sets from the fixed evaluation pool.

Figure 9: We show the normalized width as we vary $n_{\mathrm{cal}}$ and $n_{\mathrm{test}}$ jointly (left) or independently (middle and right). All panels report the mean $\pm$ standard error based on $100$ random draws of the calibration and test sets from the fixed evaluation pool.

Figure 10: We show the normalized margin, violation rate, and normalized width as we vary the nominal coverage level $1-\alpha\in\{0.8,0.85,0.9,0.95,0.99\}$ , with $n_{\mathrm{cal}}$ and $n_{\mathrm{test}}$ fixed at their largest values for each dataset. All panels report the mean $\pm$ standard error based on $100$ random draws of the calibration and test sets from the fixed evaluation pool.

Figure 11: We show the normalized DPI gap across calibration sample sizes and degradation levels, using boxplots to summarize 100 random draws of the calibration and test sets. Each column corresponds to a degradation level, and the marker for each dataset is indicated above the corresponding boxplots. For visual clarity, we magnify the $y$ -axis by $2\times$ and $4\times$ for $n_{\mathrm{cal}}=100$ and $n_{\mathrm{cal}}=1{,}000$ , respectively. Datasets whose evaluation pool is too small for a given calibration size are omitted.

Dataset	Criterion	Prob.		APS		Acc.
Dataset	Criterion	$\mathbb{E}[\|\mathcal{C}\|]$ ( $\downarrow$ )	Cov.	$\mathbb{E}[\|\mathcal{C}\|]$ ( $\downarrow$ )	Cov.	Top-1 ( $\uparrow$ )	Top-5 ( $\uparrow$ )
S2	$\Delta_{\alpha}$ (Prob.)	$11.464\pm 0.032$	$0.900\pm 0.001$	$11.952\pm 0.029$	$0.900\pm 0.001$	$0.366\pm 0.001$	$\mathbf{0.722\pm 0.000}$
	$\Delta_{\alpha}$ (APS)	$11.459\pm 0.033$	$0.900\pm 0.001$	$11.950\pm 0.029$	$0.900\pm 0.001$	$0.366\pm 0.001$	$\mathbf{0.722\pm 0.001}$
	$I_{\lambda}$ (Prob.)	$\mathbf{11.456\pm 0.032}$	$0.900\pm 0.001$	$\mathbf{11.948\pm 0.028}$	$0.900\pm 0.001$	$0.366\pm 0.001$	$\mathbf{0.722\pm 0.001}$
	Shannon MI	$11.473\pm 0.031$	$0.900\pm 0.001$	$11.959\pm 0.027$	$0.900\pm 0.001$	$\mathbf{0.367\pm 0.001}$	$\mathbf{0.722\pm 0.001}$
	Accuracy	$11.503\pm 0.029$	$0.900\pm 0.001$	$11.986\pm 0.026$	$0.900\pm 0.001$	$\mathbf{0.367\pm 0.001}$	$\mathbf{0.722\pm 0.001}$

Appendix

Table 5: We evaluate feature selection performance using conformal set-size reduction. Each row represents one selection criterion and values are reported as mean

\pm

Figure 12: We show the expected set size using the probability score and APS score against the fraction of candidate features selected. Each curve is the mean over 10 random splits of the evaluation pool. We show only the first half of the selection trajectory, after which the curves largely coincide. On S3 and CIFAR-100, the gap between $\Delta_{\alpha}$ and Shannon MI is concentrated in the early steps, which becomes diluted when averaging over the full trajectory.

	Prob.		APS
$k$	Mask-cond.	Subset-specific	Mask-cond.	Subset-specific
1	$3.75\pm 0.36$	$2.49\pm 0.32$	$3.59\pm 0.40$	$2.33\pm 0.35$
2	$5.81\pm 0.46$	$4.06\pm 0.35$	$5.24\pm 0.54$	$3.87\pm 0.46$
4	$3.71\pm 0.33$	$0.42\pm 0.24$	$2.98\pm 0.67$	$1.32\pm 0.31$
8	$3.00\pm 0.46$	$0.58\pm 0.32$	$3.56\pm 0.64$	$0.91\pm 0.28$
Avg.	$4.07\pm 0.27$	$1.89\pm 0.14$	$3.84\pm 0.41$	$2.11\pm 0.14$

Appendix

Table 6: Difference in expected set size between Shannon MI and

\Delta_{\alpha}

on CIFAR-100 when each feature ordering is evaluated with the mask-conditioned model or with subset-specific models. Positive values indicate that

\Delta_{\alpha}

yields smaller sets. Values are reported as mean

\pm

standard error over 10 random splits of the evaluation pool.

Explore similar work

May 25, 2025stat.ML

Optimal Conformal Prediction under Epistemic Uncertainty

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

1LMU Munich · 2MCML · 3CISPA +3

Online Conformal Prediction Predictive Uncertainty Conformal Risk Control Uncertainty Integrity

Ask PDF

Date pendingcs.LG

Benchmarking non-conformity score functions in conformal prediction

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

Nonconformity Scores Online Conformal Prediction Clinical Prediction

Ask PDF

May 12, 2026stat.ML

Online Conformal Prediction: Enforcing monotonicity via Online Optimization

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 \emph{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.

Eduardo Ochoa Rivera, Ambuj Tewari

University of Michigan · Ann Arbor, USA

Online Conformal Prediction Multi-Quantile Regression Uncertainty Quantification Monotonicity

Ask PDF