Universal distribution of the empirical coverage in split conformal prediction

arXiv:2303.02770 · math.ST, cs.LG, stat.ML, stat.TH · Submitted 2024-09-21 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Universal distribution of the empirical coverage in split conformal prediction".

Jane: The paper was written by Paulo C. Marques F from Insper Institute of Education and Research.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everyone. Today we’re digging into a paper that’s got a wonderfully precise title: “Universal distribution of the empirical coverage in split conformal prediction.” Jane, I have to say, just reading that title got me excited because it promises something clean and mathematical.

Jane: It really does, Tom. And the author, Paulo C. Marques F. from Insper in Brazil, has given us a result that’s surprisingly simple to state. Essentially, when you use split conformal prediction to build prediction sets for a batch of future data points, the exact probability distribution of how often those sets actually contain the true value—the empirical coverage—is known. And it depends only on two numbers: the nominal miscoverage level and the calibration sample size.

Tom: So it’s universal in the sense that it doesn’t matter what kind of data you have, what model you’re using, or even if the data is independent or just exchangeable. The distribution is the same.

Jane: Exactly. That’s the beauty of conformal prediction. It’s distribution-free. And the paper proves that the empirical coverage follows something called a Beta-Binomial distribution. For a batch of size m, the number of times the prediction set covers the true value is Beta-Binomial with parameters tied to the calibration size and the nominal level.

Tom: And that’s not just a theoretical curiosity. It gives you a practical handle on how many calibration points you need to trust that your prediction sets are working as advertised. I mean, before this, we had a guarantee on the average coverage, but now we can say something about the whole distribution.

Jane: Right. And the author goes further. He also looks at what happens when the batch size goes to infinity. Then the empirical coverage converges almost surely to a Beta distribution. So you can think of it as the limit of that Beta-Binomial.

Tom: So for anyone building systems that output prediction intervals or sets, this is a way to answer the question: how much calibration data do I need so that my coverage is within a certain tolerance with high probability? That’s a real engineering question.

Jane: And the paper even provides a table with minimum required calibration sizes for different tolerances and confidence levels. It’s a very practical contribution wrapped in elegant theory.

Tom: I love when a paper gives you both the theorem and the table. Let’s keep going, because I want to understand how they actually derive this distribution and why exchangeability is the key assumption.

Jane: Good segue, Tom. Let’s talk about the mechanics next.

Summary: Tom: So, Jane, we’ve established the big picture. Now let’s get into the guts of the paper. The key assumption is exchangeability of the data sequence—training, calibration, and future observations all come from the same underlying process, so their order doesn’t matter probabilistically.

Jane: Right. And the author shows that if the conformity scores—the numbers that measure how well the model fits each point—are exchangeable, then the coverage indicators are also exchangeable. That’s the crucial step. It means the pattern of which future points are covered is symmetric, even though the indicators are dependent.

Tom: And that dependence is important. I think a lot of people might assume that if you have a batch of future points, each one is covered independently. But that’s not true, because they all share the same threshold from the calibration sample.

Jane: Exactly. The same calibration score determines the prediction set for every future point. So if that threshold happens to be high, you’ll cover more points; if it’s low, you’ll cover fewer. That creates correlation across the batch. And the paper handles that correlation exactly.

Tom: So the proof uses induction on the batch size. You start with one future point, and you know the probability it’s covered is just the rank of the threshold among the calibration scores. Then you add another point, and you condition on what happened with the first one.

Jane: And because of exchangeability, the new point’s score is uniformly ranked among all the scores you’ve seen so far—calibration plus previous future points. That gives you a clean recursive formula, and it closes to the Beta-Binomial distribution.

Tom: I appreciate that the proof is combinatorial. It’s about counting ranks, not about densities or asymptotic approximations. Everything is finite-sample and exact.

Jane: And that’s a big deal. The result holds for any batch size, no matter how small. You don’t need the batch to be large for the distribution to be correct.

Tom: Then they take the limit as the batch size grows, and de Finetti’s theorem kicks in. That’s the tool that says an exchangeable sequence can be thought of as conditionally independent given some underlying random parameter.

Jane: Yes. So the almost sure limit of the empirical coverage is a Beta random variable. And that Beta distribution is the same one you’d get from a Bayesian analysis with a uniform prior on the coverage probability. It’s a beautiful connection.

Tom: So the summary is: exact finite-sample distribution for finite batches, and an exact limiting distribution for infinite batches. Both universal, both depending only on the calibration size and the nominal level.

Jane: And both practically useful, as we’ll see when we talk about the calibration size table.

Tom: Let’s do that. I’m curious how the author turns this into a design criterion.

Improvements: Tom: So, Jane, the paper doesn’t just stop at theory. It gives you a way to choose your calibration sample size. And that’s the improvement I think practitioners will really appreciate.

Jane: Absolutely. The idea is simple. You pick a nominal miscoverage level, say α equals zero point one, so you want ninety percent coverage. Then you specify a tolerance, like you want the empirical coverage to be within zero point zero one of that ninety percent. And you specify a probability, say ninety-five percent, that you want that guarantee to hold.

Tom: So you’re asking: what’s the smallest calibration sample size such that, with ninety-five percent probability, the empirical coverage of an infinite batch of future points is between eighty-nine percent and ninety-one percent?

Jane: Exactly. And the paper provides a table with those numbers. For α equals zero point one, tolerance zero point zero one, and ninety-five percent probability, you need about one thousand eight hundred six calibration points. That’s a lot more than the naive rule of thumb you sometimes hear, like “use ten percent of your data for calibration.”

Tom: And the table shows how sensitive this is to the tolerance. If you relax the tolerance to zero point zero five, you only need about twenty-nine points for the same ninety-five percent probability. That’s a huge difference.

Jane: It is. And that’s the practical improvement: the paper gives you a principled way to trade off calibration cost against coverage precision. You don’t have to guess anymore.

Tom: I also noticed the paper compares its numbers to earlier work by Angelopoulos and Bates. The sizes here are slightly smaller. The author attributes that to a different formulation, but the key point is that the methodology is now exact.

Jane: Right. And there’s a repository with R code so you can reproduce the table and even run simulations to see the distributions in action. That’s great for anyone who wants to verify the results themselves.

Tom: So the improvement is really about moving from an average guarantee to a distributional guarantee. You’re not just saying “on average, you’ll get ninety percent coverage.” You’re saying “with high probability, your coverage will be close to ninety percent.”

Jane: And that’s a much stronger statement. For applications where coverage matters—like medical diagnosis, credit scoring, or any high-stakes prediction—you want to know that your system is reliable, not just on average, but in the worst case that’s still reasonably likely.

Tom: So the next time someone asks me how much calibration data they need, I can point them to this table and give them a number with a clear probabilistic meaning.

Jane: And that’s a real contribution. It’s not just theory for theory’s sake. It’s theory that changes how you design systems.

Tom: Let’s wrap up with our final thoughts on the whole paper.

Conclusion: Tom: So, Jane, we’ve covered a lot of ground on “Universal distribution of the empirical coverage in split conformal prediction.” Let’s bring it home.

Jane: Yes. The paper gives us the exact distribution of empirical coverage for finite batches, which is Beta-Binomial, and the exact limiting distribution for infinite batches, which is Beta. Both are universal, depending only on the calibration size and the nominal miscoverage level.

Tom: And that universality is what makes it so powerful. You can apply this to any model, any data, any problem, as long as your data is exchangeable. That’s a very mild assumption.

Jane: The practical payoff is the calibration size table. You can now choose your calibration sample size to guarantee, with a specified probability, that your coverage will be within a specified tolerance. That’s a design tool, not just a theoretical result.

Tom: I also appreciate that the author was careful to define regularity—no ties in the conformity scores—and to handle the feasibility condition on the pair of calibration size and nominal level. Those details matter when you’re implementing this.

Jane: And the proofs are clean, using exchangeability and de Finetti’s theorem. It’s a nice example of how classical probability tools can solve modern machine learning problems.

Tom: So, as we say goodbye to this paper, I think the takeaway is that conformal prediction is maturing. We’re moving from “it works on average” to “we know exactly how it behaves.” That’s a big step.

Jane: And for anyone building prediction systems, this is a must-read. The table alone is worth the download.

Tom: Well said, Jane. That’s a wrap on this one. Next up, we’ve got a paper on uncertainty quantification in deep learning, so stay tuned.

Jane: Thanks for listening, everyone. See you on the next episode.

Paulo C. Marques F

Insper Institute of Education and Research

math.ST, cs.LG, stat.ML, stat.TH

Submitted: 2024-09-21

Updated: 2026-08-18

Comments: 6 pages, 1 table

Journal ref: Statistics & Probability Letters, Volume 219, 2025, 110350.

DOI: 10.1016/j.spl.2024.110350

Code: https://github.com/paulocmarquesf/coverage

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 63/100

Key concepts

Split Conformal Prediction: A method used to build prediction sets by using a separate calibration sample. It is distribution-free, meaning it works regardless of the underlying data distribution or model type.
Empirical Coverage: This refers to the exact probability distribution of how often the prediction sets built using split conformal prediction actually contain the true value for a batch of future data points.
Exchangeability: The key assumption is that training, calibration, and future observations all come from the same underlying process. This means the order of data points does not matter probabilistically for the coverage indicators.
Beta-Binomial Distribution: This is the exact distribution found for finite batches of prediction sets in split conformal prediction. Its parameters are determined solely by the calibration sample size and the nominal miscoverage level.

Terminology

Calibration — 55× in this paper · explained in 7 episodes
Empirical Coverage — 33× in this paper · explained in 2 episodes
Conformal Prediction — 30× in this paper · explained in 5 episodes
Exchangeability — 25× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes
Uncertainty Quantification — 1× in this paper · explained in 8 episodes

Summary

Summary

This paper investigates the exact distribution of the empirical coverage of prediction sets produced by the split conformal prediction algorithm for a finite batch of future observables, as well as the exact distribution of its almost sure limit when the batch size tends to infinity. The paper establishes that both distributions are universal, being determined solely by the nominal miscoverage level and the calibration sample size.

The paper operates within a supervised learning setting where, for each sample unit, there is a d-dimensional vector of predictors Xi ∈ Rd and a response variable Yi ∈ Y. The data sequence is laid out as training sample of size t ≥ 1, followed by calibration sample of size n ≥ 1, and then a sequence of future observables. The data exchangeability assumption allows the training sample to be placed at the beginning of the sequence.

A conformity function is defined as a mapping ρ: Rd × Y × omega → R such that ρ(x, y) is T-measurable for every x ∈ Rd and every y ∈ Y, where T is the σ-field generated by the training sample. The sequence of conformity scores S i i≥1 is defined by S i (ω) = ρ(Xi (ω), Yi (ω), ω). A conformity function is regular with respect to a specific data sequence if there are no ties among the corresponding conformity scores almost surely. Lemma 1 establishes that under the data exchangeability assumption, the sequence of conformity scores S i i≥1 is exchangeable.

For a regular conformity function, with ordered calibration sample conformity scores S (1), S (2),..., S (n), and a specified nominal miscoverage level 0 < α < 1 satisfying ⌈(1 − α)(n + 1)⌉ ≤ n (in which case the pair (n, α) is feasible), the random conformal prediction set D(α) n (x, ω) is defined by D(α) n (x, ω) = y ∈ Y: ρ(x, y, ω) ≤ S (⌈(1−α)(n+1)⌉) (ω).

The first major consequence of Lemma 1 is the classical marginal validity property: 1 − α ≤ P(Yn+i ∈ D(α) n (Xn+i)) < 1 − α + 1/(n+1).

Definition 4 introduces the sequence of coverage indicators Zi i≥1 defined by Zi = 1 if Yn+i ∈ D(α) n (Xn+i), and Zi = 0 otherwise. The empirical coverage of a batch of m ≥ 1 future observables is the random variable Cm(n,α) = (1/m) Pm i=1 Zi. The paper notes that in general, the coverage indicators Zi are dependent random variables, since for all future observables the corresponding conformal prediction sets are defined in terms of the same calibration sample conformity score S (⌈(1−α)(n+1)⌉).

Theorem 1 establishes that under the data exchangeability assumption, for a regular conformity function, the sequence of coverage indicators Zi i≥1 is exchangeable and m × Cm(n,α) is distributed as a Beta-Binomial(⌈(1 − α)(n + 1)⌉, ⌊α(n + 1)⌋) random variable. The distribution of the empirical coverage is given by P(Cm(n,α) = k/m) = (m choose k) × [n! (k + ⌈(1 − α)(n + 1)⌉ − 1)! (m − k + ⌊α(n + 1)⌋ − 1)!] / [(⌈(1 − α)(n + 1)⌉ − 1)! (⌊α(n + 1)⌋ − 1)! (m + n)!], for k = 0, 1,..., m, and every future batch size m ≥ 1.

By symmetry, Definition 4 and the exchangeability of the sequence of coverage indicators established in Theorem 1 yield that E[Cm(n,α)] = E[Z1] = P(Yn+1 ∈ D(α) n (Xn+1)). Consequently, the marginal validity property can be interpreted as partial information about the distribution of the empirical coverage, specifically as an inequality constraint on the expectation of Cm(n,α).

Theorem 2 establishes that under the data exchangeability assumption, for a regular conformity function, the empirical coverage Cm(n,α) converges almost surely, when the future batch size tends to infinity, to a random variable C(n,α) ∞ with distribution Beta(⌈(1 − α)(n + 1)⌉, ⌊α(n + 1)⌋). This result is proved as a direct consequence of Theorem 1 and de Finetti’s representation theorem.

The paper then provides a practical criterion for determining the minimum required calibration sample size. Given a nominal miscoverage level α, an ǫ > 0, and a tolerance probability 0 < τ < 1, the minimum required calibration size is given by n0 = min n ≥ (1 − α)/α: P(C(n,α) ∞ − (1 − α) < ǫ) ≥ τ. Table 1 gives the values of the minimum required calibration sample size n0 for different values of α, ǫ, and τ. The paper notes that the calibration sample sizes presented in a previous work [8] are slightly larger than the corresponding values in Table 1.

The proofs are provided in the Appendix. The proof of Lemma 1 uses the Doob-Dynkin lemma to show that the conformity scores can be expressed as a measurable function of the training sample and the corresponding data pair, and then uses the data exchangeability assumption to establish exchangeability of the conformity scores. The proof of Theorem 1 uses induction on the batch size m, establishing that the joint distribution of the coverage indicators has a specific form, and then uses exchangeability to derive the Beta-Binomial distribution. The proof of Theorem 2 uses de Finetti’s representation theorem to express the joint distribution of the coverage indicators as an integral with respect to a unique distribution µ, and then identifies µ as the Beta distribution.

Improvements for AI systems

Based on the paper, I can improve AI systems in the following specific ways:

1. Calibration-Aware Prediction Intervals

Improvement: Integrate the exact Beta-Binomial distribution of empirical coverage (Theorem 1) into AI model deployment pipelines.
What the improved system can do: When an AI model (e.g., regression or classification) generates prediction sets for a batch of future observations, it can now compute the exact probability that the actual coverage will deviate from the nominal level (e.g., 95%). This allows the system to report not just 95% prediction interval but also with 90% probability, the empirical coverage of this batch will be between 93% and 97%.

2. Minimum Calibration Sample Size Optimizer

Improvement: Implement an automatic calibration size selector using Table 1's criterion (Section 4).
What the improved system can do: Before deployment, the AI system can automatically determine the minimum number of calibration samples needed to guarantee that the empirical coverage of an infinite batch of future predictions will be within a specified tolerance (e.g., ±1%) with a specified confidence (e.g., 95%). For instance, if you need 95% nominal coverage with ±1% tolerance at 95% confidence, the system will automatically require at least 1,806 calibration samples (from Table 1), preventing under-powered or over-provisioned calibration.

3. Batch-Size-Aware Coverage Guarantees

Improvement: Use Theorem 1's finite-batch distribution to adjust prediction set thresholds dynamically based on the batch size m.
What the improved system can do: For a given batch of m future predictions, the system can compute the exact probability that the empirical coverage will fall below a critical threshold. If this probability is too high, the system can automatically widen the prediction sets (by increasing the quantile threshold) to meet a stricter batch-level coverage guarantee, rather than relying only on marginal per-observation validity.

4. Uncertainty Quantification for Model Retraining

Improvement: Apply Theorem 2's almost-sure limit distribution to monitor model drift or data shift.
What the improved system can do: After deploying an AI model, the system can continuously monitor the empirical coverage of prediction sets on new data. Since the asymptotic distribution of coverage is known (Beta with parameters determined by calibration size and nominal level), the system can use statistical hypothesis testing to detect when the observed coverage deviates significantly from the expected Beta distribution, triggering an alert for model retraining or data quality issues—even before individual prediction errors become apparent.

5. Risk-Aware Decision Making

Improvement: Incorporate the exact coverage distribution into downstream decision rules.
What the improved system can do: In high-stakes applications (e.g., medical diagnosis, financial forecasting), the AI system can now quantify the risk of under-coverage for a batch of decisions. For example, if a batch of 100 patients is given prediction sets, the system can compute the probability that fewer than 90 patients are correctly covered, and then decide whether to escalate to human review or adjust the confidence level accordingly—all based on exact finite-sample mathematics rather than asymptotic approximations.

Abstract

When split conformal prediction operates in batch mode with exchangeable data, we determine the exact distribution of the empirical coverage of prediction sets produced for a finite batch of future observables, as well as the exact distribution of its almost sure limit when the batch size goes to infinity. Both distributions are universal, being determined solely by the nominal miscoverage level and the calibration sample size, thereby establishing a criterion for choosing the minimum required calibration sample size in applications.