Review

Certified uncertainty bounds

Karimi and Samavi take the size of a conformal prediction set for a single input and derive certified upper and lower bounds on a per-input model uncertainty from it. The proof inserts the marginal coverage guarantee, a statement about the average over inputs, as if it held for the input in hand. The bounds that come out depend on the input only through the set size, and their width is at most \(2/(n+1)\), so the theorem pins the uncertainty of every input with the same set size to the same number. A two-group classifier with valid marginal coverage puts every input outside the certified interval, and it is built on two atoms, where conditional coverage is attainable, so the bounds fail in the easiest case rather than a contrived one. Two papers criticise the set size as an uncertainty measure and neither examines the proof, which is set out below with sources. Demonstration 33 rebuilds the example with sliders.

What is proposed

The paper is Karimi and Samavi, “Quantifying Deep Learning Model Uncertainty in Conformal Prediction,” AAAI Summer Symposium 2023, arXiv:2306.00876. The abstract says the authors “provide certified boundaries for the computed uncertainty” and the conclusion says they “certify upper and lower bounds for the uncertainty quantification.” The object is the conformal prediction set \(C(x)\) of a classifier with \(K\) classes at error level \(\delta\), built from \(n\) calibration points, and the quantity is a per-input “conformal model uncertainty” \(U_C(x) \in [0,1]\).

Theorem 2 of the paper states the following. Let \(m = |C(x)|\) be the size of the set for the input \(x\). If \(m = 0\) then \(U_C(x) = 1\). If \(0 < m \le K\), define the “pure model uncertainty”

$$\hat u_C = \frac{m + \delta - 1}{K},$$

and then

$$L_C \;=\; \hat u_C (1-\delta) + \delta - \frac{1}{n+1} \;\le\; U_C(x) \;\le\; \min(H_C, 1), \qquad H_C \;=\; \hat u_C\,\frac{n+2}{n+1} + \delta\,(1-\hat u_C).$$

The proof defines \(U_C(x)\) through two events for the input \(x\): \(P_1\), that the true label is in the set, and \(P_0\), that it is not. It sets the probability of being uncertain to \(\hat u_C\) when \(P_1\) holds and to one when \(P_0\) holds, so that

$$U_C(x) \;=\; \hat u_C\, \mathbb{P}(P_1) + \mathbb{P}(P_0). \tag{13}$$

It then writes, as equations (14) and (15),

$$1-\delta \;\le\; \mathbb{P}(P_1) \;\le\; 1-\delta+\frac{1}{n+1}, \qquad \delta - \frac{1}{n+1} \;\le\; \mathbb{P}(P_0) \;\le\; \delta,$$

and substitutes these into (13) to get \(L_C\) and \(H_C\). The two inequalities are the coverage guarantee of split conformal prediction, quoted from Romano, Sesia and Candès and from Vovk, Gammerman and Shafer.

What has already been said

Two papers criticise this one. Chau, Zargarbashi, Sale and Caprio (2026) reject the set size as a measure of epistemic uncertainty: “the CPR size at a fixed level \(\alpha\) characterises uncertainty about the predicted region itself, rather than the uncertainty encountered when producing that prediction.” They also note, in passing, the observation that drives the section after next, that the construction is a relabeling of the set size, since the normalisation “preserves the instance-wise ranking induced solely by CPR sizes.” Silva and co-authors (2026) report that the estimates “don’t vary significantly for large retrieval databases.” Neither examines the proof of Theorem 2, and of the paper’s thirty citations only four engage with its content at all.

Theorem 2 was also revised. The arXiv version of January 2024, which is the one the AAAI proceedings carry, redefines \(\hat u_C\) from \(m/K\) to \((m+\delta-1)/K\), drops a case, caps the upper bound at one, and adds a sentence conceding that “this heuristic notion of uncertainty is arbitrarily devised and can be replaced by any other heuristic and reasonable uncertainty quantification.” There is no erratum and no note of the change. Equations 13 to 17, which contain the error, are identical in both versions.

The step that fails

The coverage guarantee is marginal. It says that if a calibration set and a fresh test pair \((X, Y)\) are drawn exchangeably, then

$$1-\delta \;\le\; \mathbb{P}\big(Y \in C(X)\big) \;\le\; 1-\delta+\frac{1}{n+1},$$

where the probability averages over the calibration draw and over the test input. Equation (13) needs \(\mathbb{P}(P_1)\) for the particular input \(x\) whose set has size \(m\). That is the conditional probability \(\mathbb{P}(Y \in C(x) \mid X = x)\), and split conformal prediction constrains it not at all. The paper substitutes the marginal quantity for the conditional one, and everything after that step is arithmetic on the wrong number. Theorem 2 even carries the word: it offers “the following marginal lower bound \(L_C\) and upper bound \(H_C\)” for a quantity the same sentence attaches to a single \(x_{\text{val}}\).

How hard the conditional quantity is to control depends on the input distribution, and the distinction matters for what follows. For a continuously distributed input, Vovk (2012) and Foygel Barber, Candès, Ramdas and Tibshirani (2021) show that conditional coverage forces trivial sets: Barber and co-authors prove the expected interval length is infinite “at almost all points \(x\) aside from the atoms of \(P_X\).” Both results exempt atoms, and Vovk says why the exemption is real. “Of course, the condition that \(x\) be a non-atom is essential: if \(P_X(\{x\}) > 0\), an inductive conformal predictor that ignores all examples with objects different from \(x\) will have \(1-\epsilon\) object conditional validity and can give narrow predictions if the training set is big enough.”

The example below is deliberately built on atoms, where that escape is available. Two groups, each with positive probability, and calibrating within each group would deliver exact coverage for both. So the bounds are not failing because the conditional quantity is out of reach. They fail in the one setting where it is within reach, because substituting an average for a conditional is wrong wherever it is done.

Because \(\mathbb{P}(P_1)\) has been replaced by a constant, the bounds no longer depend on \(x\) at all except through \(m\). Their width is

$$H_C - L_C \;=\; \frac{\hat u_C + 1}{n+1} \;\le\; \frac{2}{n+1},$$

so with a thousand calibration points the certified interval is a point to three decimals. What the theorem says, read literally, is that every input whose set has \(m\) elements has uncertainty

$$U_C(x) \;\approx\; \delta + \frac{(m+\delta-1)(1-\delta)}{K}.$$

For \(K = 10\) and \(\delta = 0.1\) this is \(0.109\) for a singleton set and \(0.919\) for the full set. The number is a relabeling of the set size. The paper’s Figure 1 plots the bounds against \(m\) and \(\delta\), and its curves are consistent with this formula.

A two-group example

Setup. Ten classes with equal frequency, \(\delta = 0.1\), and a calibration set of \(n = 1000\) points. Inputs come from two groups. Group A is three quarters of the population and easy: the classifier puts probability \(0.9\) on the true class and \(0.1/9\) on each other class. Group B is one quarter and hard: the classifier puts probability \(0.65\) on one class and \(0.35/9\) on each other, and its favoured class is the true class with probability \(0.65\). The conformal score is one minus the probability of the true class, the score implied by the paper’s equation (3).

Calculation. The calibration scores take three values. Group A inputs score \(0.1\), which is 75% of the calibration set. Group B inputs whose favoured class is correct score \(0.35\), which is \(0.25 \times 0.65 \approx 16\%\). Group B inputs whose favoured class is wrong score \(1 - 0.35/9 \approx 0.961\), the remaining 9%. The threshold is the \(\lceil 1001 \times 0.9 \rceil = 901\)st smallest score, which lands in the second block, so \(\hat q = 0.35\). The set is every class with probability at least \(1 - \hat q = 0.65\). For a group A input that is the true class alone, since \(0.9 \ge 0.65\) and \(0.1/9 < 0.65\). For a group B input it is the favoured class alone. Every set is a singleton, \(m = 1\) for every input.

Marginal coverage is \(0.75 \times 1 + 0.25 \times 0.65 = 0.9125\), above \(1 - \delta\), so the guarantee holds and the construction is a legitimate conformal predictor. Conditional coverage is \(1\) in group A and \(0.65\) in group B.

The theorem. With \(m = 1\), \(\hat u_C = (1 + 0.1 - 1)/10 = 0.01\), and

$$L_C = 0.01 \times 0.9 + 0.1 - \tfrac{1}{1001} = 0.1080, \qquad H_C = 0.01 \times \tfrac{1002}{1001} + 0.1 \times 0.99 = 0.1090.$$

The certified interval for every input is \([0.1080, 0.1090]\). Now evaluate the paper’s own definition (13) with each group’s actual probability of covering the truth. For a group A input, \(\mathbb{P}(P_1) = 1\) and \(U_C = 0.01 \times 1 + 0 = 0.010\). For a group B input, \(\mathbb{P}(P_1) = 0.65\) and \(U_C = 0.01 \times 0.65 + 0.35 = 0.3565\). Neither is inside the interval. The certified bounds miss on every input, and they miss in both directions.

A simulation with these parameters gives \(\hat q = 0.350\), marginal coverage \(0.912\), all 200,000 test sets of size one, conditional coverage \(1.000\) in group A and \(0.647\) in group B, and the two values of \(U_C\) at \(0.010\) and \(0.360\). The script is data/reviews/karimi_check.py.

The example also answers the paper’s stated purpose, which is to let conformal uncertainty “be compared by other uncertainty quantification methods such as Bayesian” ones. A group A input is misclassified never and a group B input 35% of the time. Any Bayesian or ensemble method that saw the probability vectors would separate them. The certified number cannot, because it was built from \(m\) and \(m\) is one for both.

What the set size does carry

The size of a conformal set is a legitimate heuristic. On average over inputs, larger sets go with inputs the score finds harder, and the paper’s reading of \(m\) as an ordinal signal is the standard one. The claim under review is stronger: that the coverage guarantee turns the signal into a certified interval for each input. It does not. The guarantee is one scalar, the average coverage, and it is spent entirely on the average. Nothing is left over for a bound at a point. The same observation, that a functional of the sets alone cannot recover per-input or per-class facts the sets do not contain, is the no-go theorem in our review of conformal correlation, and it applies here with \(g(C) = |C|\).

If a per-group statement is wanted, Mondrian or group-conditional conformal prediction gives one, at the price of naming the groups in advance and calibrating within them. That is a guarantee for the group average, and still not for the input.

The paper is Karimi and Samavi, Quantifying Deep Learning Model Uncertainty in Conformal Prediction, AAAI 2023 Summer Symposium Series, arXiv:2306.00876v2. Equation numbers are the paper’s. The conditional coverage impossibility results are Vovk, Conditional validity of inductive conformal predictors (ACML 2012, arXiv:1209.2673), Lei and Wasserman, Distribution-free prediction bands for non-parametric regression (JRSS-B 2014), and Foygel Barber, Candès, Ramdas and Tibshirani, The limits of distribution-free conditional predictive inference (Information and Inference 2021, arXiv:1903.04684), whose Proposition 1 and Theorem 2 both exclude the atoms of \(P_X\). The prior criticism is Chau, Zargarbashi, Sale and Caprio, Quantifying Epistemic Predictive Uncertainty in Conformal Prediction (arXiv:2602.01667), and Silva, Bernardino and co-authors, Conformal Aerial Geo-Localization Through Visual Place Recognition (ICUAS 2026). Version differences are between arXiv:2306.00876v1 and v2.