Conformal Prediction: Coverage and Efficiency

A conformal classifier can reach 90% marginal coverage by returning nearly every possible class. The guarantee holds and the output decides nothing. Evaluation therefore separates two things. Validity is whether the true outcome is covered often enough. Efficiency is whether the sets or intervals are narrow enough to act on.

The distance between the two is measurable, and it has been measured. On ImageNet-Val with a ResNeXt-101 base classifier at a 90% target, two conformal procedures both recorded an empirical coverage of 0.900 — the same figure to three decimals. The average prediction set held 19.7 labels under APS and 2.00 under RAPS. One guarantee, two procedures, and a tenfold difference in what a person is actually handed.

The promise itself is stated carefully. Conformal sets are valid “in a distribution-free sense: they possess explicit, non-asymptotic guarantees even without distributional assumptions or model assumptions”, and you can “use conformal prediction with any pre-trained model, such as a neural network, to produce sets that are guaranteed to contain the ground truth with a user-specified probability, such as 90%”. That is Angelopoulos and Bates, writing in 2021. Distribution-free is a claim about the data distribution. It is not a claim that the procedure has no assumptions at all.

The method wraps a fitted predictor with a calibration procedure. Stage three is the one that carries a number. The quantile comes from a finite calibration set, so the coverage you get from that particular set is itself a random quantity. Its distribution is Beta(n + 1 − l, l), with l = floor((n + 1) × alpha) — a result credited to Vovk in 2012. A single fixed calibration set does not deliver exactly 1 − alpha. It delivers a draw.

Calibration size is therefore a design decision with a computable answer rather than a matter of taste. At alpha = 0.1 the guideline is about a thousand points. Angelopoulos and Bates put it this way: “Inspecting Figure 11, we see that choosing n = 1000 calibration points leads to coverage that is typically between .88 and .92, hence our rough guideline of choosing about 1000 calibration points.” Tighter promises are priced separately. At delta = 0.1 and alpha = 0.1, a coverage slack of 0.05 needs n = 102. A slack of 0.01 needs n = 2,491.

The matching design rule comes with a second bill, because it costs a level adjustment as well as data. The calibration size n must exceed N := (−ln delta) / (2 × epsilon^2). The predictor must then be run at the reduced level epsilon − sqrt((−ln delta) / (2n)) to be (epsilon, delta)-valid. That is Vovk again, in 2012. More data buys the promise. The promise itself is quietly shaved to pay for it.

Guarantees differ in strength and in what they assume, and the standard one is two-sided. With n calibration points at level alpha, split conformal satisfies 1 − alpha ≤ P(Ytest in C(Xtest)) ≤ 1 − alpha + 1/(n + 1). It cannot fall short of the target. It cannot overshoot it by more than one calibration point's worth.

The load-bearing word sits in the middle of the definition. “In words, the probability that the prediction set contains the correct label is almost exactly 1 − α; we call this property marginal coverage, since the probability is marginal (averaged) over the randomness in the calibration and test points”, write Angelopoulos and Bates, immediately after their equation (1). Marginal means averaged. It is not a promise about the case in front of you.

Four researchers stated the same guarantee independently in JMLR in 2024, as P[Yi in C_{1−alpha}(Xi)] ≥ 1 − alpha − eta with eta = (1 − alpha)/(n_cal + 1). They add at once that “the results above are strongly reliant on the data exchangeability.”

The third column is not merely harder to reach than the first. It is unavailable. A 2021 paper on the limits of distribution-free conditional predictive inference says so in its abstract: “On the other hand, exact conditional inference guarantees are known to be impossible without imposing assumptions on the underlying distribution.”

Insisting anyway has a price, and a second 2012 result of Vovk's names it. A set predictor with exact object-conditional validity must return regression intervals of infinite Lebesgue measure at almost every non-atomic test point. In classification it must include each individual label with probability at least 1 − epsilon. An interval of infinite length always covers the truth. That is the point. Exact conditional validity is purchased by handing back a set that says nothing. Group coverage on named slices sits between the two, and it is the claim you can actually audit.

Marginal coverage is an average, and averages have insides. A 2019 paper on equalized coverage ran split conformal on the MEPS health-expenditure data at alpha = 0.1, averaged over 40 random 80/20 train-test splits. Then it printed the coverage group by group. “On the other hand, the marginal CP method under-covers in the white group and over-covers in the non-white group”, its authors write. The one number that looks correct is the one the method was built to hit.

Narrowness has different meanings across outputs, and each has its own unit. On the classification axis it is countable: 19.7 labels against 2.00 at the same 0.900 empirical coverage. On the regression axis it is a length: 2.907 against 2.764 and 3.182 in the MEPS intervals. Neither figure is the guarantee. Both decide whether the guarantee is worth having.

Report nominal and empirical coverage, confidence intervals, set-size distributions, conditional slices, calibration-set size, the nonconformity definition, and failure under plausible shift. Conformalization does not fix a bad base model, label errors, or a harmful decision policy. What it changes is the form and interpretation of uncertainty, and that still has to be integrated into the workflow.

Efficiency is measurable, and the gap has now been measured twice by two groups. The first measurement was an ICLR 2021 spotlight, and its abstract put it this way: “In experiments on both Imagenet and Imagenet-V2 with ResNet-152 and other classifiers, our scheme outperforms existing approaches, achieving coverage with sets that are often factors of 5 to 10 smaller than a stand-alone Platt scaling baseline.” The paper's own table puts figures under the phrase. On ImageNet-Val at a 90% target, empirical coverage was 0.900 for both APS and RAPS. The average set held 19.7 labels against 2.00 for ResNeXt-101, and 89.1 against 5.32 for Inception. Those are medians of means over 100 trials, each using a 20K conformal-calibration split and a 20K evaluation split.

A second group reproduced the gap independently, in AAAI in 2023. Mean set sizes on ImageNet at 1 − alpha = 0.900, over five runs: 20.57 (SD 1.10) for APS against 2.36 (SD 0.069) for RAPS on ResNeXt-101, and 90.28 (SD 4.16) against 5.96 (SD 0.373) on Inception. Both procedures were valid, in both labs, to three decimal places. Only one produced sets a person could act on.