The Origins of Conformal Prediction

The Intellectual Lineage

The story of conformal prediction begins long before anyone used that name. It begins with a deceptively simple question that statisticians have been asking since the 1930s: can we make valid inferences without knowing the shape of the data distribution?

In the 1930s, R. A. Fisher introduced the idea of permutation tests. The insight was striking: if the null hypothesis is true and the treatment has no effect, then the assignment of observations to groups is arbitrary. You can shuffle the labels and recompute your test statistic. The fraction of shuffles that produce a result as extreme as the observed one gives you an exact p-value — no Gaussian assumption, no parametric model, no asymptotics. The validity comes purely from the symmetry of exchangeable labels.

This idea propagated through decades of statistics. In the 1940s and 1950s, Wilcoxon, Mann, Whitney, and others developed rank-based nonparametric tests. These methods replaced raw data values with their ranks, throwing away information about magnitude but gaining robustness to distributional assumptions. The Wilcoxon signed-rank test, the Mann-Whitney U test, and others in this family all share the same logical core: if the observations are exchangeable, then the ranks are uniformly distributed, and you can make exact probability statements from ranks alone.

The deep principle running through all of this is exchangeability: if the data points have no preferred ordering — if any permutation of the data is equally likely — then rank-based reasoning gives you exact, distribution-free guarantees. This principle would eventually become the single assumption underlying conformal prediction.

Vovk's Question

Fast forward to the late 1990s. Vladimir Vovk, a mathematician at Royal Holloway, University of London, was working at the intersection of algorithmic randomness and online learning. His research agenda was unusual: he was developing a game-theoretic foundation for probability, in which the laws of probability emerge from the inability to make money via a sequential betting strategy, rather than from measure-theoretic axioms.

Within this framework, Vovk asked a pointed question: can we make prediction-time guarantees — not just testing-time guarantees — without assuming any distributional model for the data? The permutation test tradition answered the testing question (is there a difference between groups?) but not the prediction question (where will the next observation fall?). Vovk wanted the prediction version.

The answer was conformal prediction. The core idea: for each candidate value $y$ of the next observation, temporarily include it in the dataset, compute a measure of how "nonconforming" it is relative to the rest, and check if its nonconformity rank is extreme. The prediction set is the collection of all $y$ values whose rank is not too extreme. Because exchangeability makes every element's rank equally likely, this set has guaranteed coverage.

The Founding Text

Vovk, together with Alex Gammerman and Glenn Shafer, developed the theory systematically over several years. The result was the 2005 book Algorithmic Learning in a Random World — the founding text of conformal prediction. The book is dense, mathematical, and deeply original. It presented conformal prediction not as an isolated technique but as a consequence of a broader program: using algorithmic randomness as the foundation for statistical inference.

The book introduced the "full conformal" method, proved its coverage properties, connected it to Martin-Lof randomness tests, and showed how it could be applied to classification and regression. It was a major intellectual achievement. And it was almost entirely ignored by the mainstream statistics and machine learning communities for the next 15 years.

Why Was It Ignored?

The original full conformal method had a devastating computational problem. To construct a prediction set for a single test point in regression, you had to consider every possible value $y$ in the real line (or a fine discretization of it). For each candidate $y$, you had to add the pair $(x_{\text{test}}, y)$ to the entire dataset, refit the model from scratch, compute nonconformity scores for all data points, and check the rank. For a discretization with 1000 grid points and a model that takes one second to train, predicting a single test point would take over 16 minutes. For a dataset with 10,000 test points, the method was simply not usable.

Beyond the computational issue, the book's intellectual framing — rooted in algorithmic randomness and game-theoretic probability — was far from the mainstream vocabulary of either statistics or machine learning. Most practitioners did not read it, and those who encountered it found the connection to practical problems unclear.

The Split Conformal Breakthrough

The computational barrier was broken by a simple observation, first proposed by Papadopoulos, Proedrou, Vovk, and Gammerman in 2002: split the data. Train the model on one portion, compute nonconformity scores on a separate held-out calibration set, and use the quantile of those scores as the threshold. This avoids refitting the model entirely. The cost drops from $O(|\mathcal{Y}| \times \text{model fit})$ to a single model fit plus sorting a list of numbers.

The price of splitting is that you use less data for training (which may produce a slightly worse model and therefore wider intervals) and less data for calibration (which introduces more variability in the quantile estimate). But the coverage guarantee is exact for any split size, and the quantile variability decreases rapidly with the calibration set size. In practice, calibration sets of a few hundred points are usually sufficient.

The Mainstream Arrives

For over a decade after Papadopoulos et al., split conformal prediction existed in a small research niche. The method appeared in scattered papers and conference workshops but had not penetrated the broader statistics or ML communities. Two papers changed this.

In 2018, Lei, G'Sell, Rinaldo, Tibshirani, and Wasserman published "Distribution-Free Predictive Inference for Regression" in the Journal of the American Statistical Association. This paper reintroduced split conformal prediction in the language of modern statistics, proved clean finite-sample results, compared conformal methods to classical prediction intervals, and connected the framework to the broader program of distribution-free inference. It was rigorous, clearly written, and published in the most prestigious statistics journal. For many statisticians, this was the first time they encountered conformal prediction.

In 2021, Angelopoulos and Bates published "A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification." This tutorial, aimed squarely at machine learning practitioners, explained conformal prediction with code, examples, and an emphasis on practical implementation. It arrived at exactly the right moment: the ML community was increasingly aware that uncertainty quantification mattered — for safety-critical applications, for large language models, for scientific discovery — and conformal prediction offered a solution that was model-agnostic, assumption-light, and easy to implement. The paper went viral by academic standards.

The result was an explosion of interest. Between 2021 and the present, conformal prediction has been applied to medical imaging, drug discovery, autonomous driving, weather forecasting, natural language processing, and many other domains. The number of papers on conformal prediction has grown roughly tenfold in five years.

From Fisher's permutation tests to the modern adoption explosion — a 90-year intellectual arc.

Why the History Matters

Understanding this lineage clarifies several things about conformal prediction that might otherwise seem mysterious. Why is exchangeability the only assumption? Because the method descends from permutation tests, which rely on exchangeability and nothing else. Why is the coverage guarantee exact in finite samples? Because it is a rank argument, and ranks are exactly uniform under exchangeability — no asymptotics needed. Why does conformal prediction work with any model? Because the model only enters through the nonconformity score, and the rank argument holds for any score function. These are not isolated design choices; they are inherited from the 90-year tradition of nonparametric, exchangeability-based inference.

The Full Conformal Method

The original conformal prediction method, as presented by Vovk, Gammerman, and Shafer, works as follows. You have a training set $Z_1 = (X_1, Y_1), \ldots, Z_n = (X_n, Y_n)$ and a new test point $X_{n+1}$. You want to construct a prediction set $\hat{C}(X_{n+1})$ for $Y_{n+1}$.

For each candidate label $y$, form the augmented dataset:

Fit a model $\hat{f}_y$ on this augmented dataset (note: the model depends on $y$). Compute nonconformity scores for every point in the augmented dataset:

Compute the conformal p-value for the candidate $y$:

This is the fraction of scores (including the test point's own score) that are at least as large as the test point's score. The prediction set is:

That is, include all candidate labels $y$ whose nonconformity rank is not in the most extreme $\alpha$ fraction. By the rank uniformity argument (Part 2), the true label $Y_{n+1}$ has a uniformly distributed rank among the $n+1$ scores, so $P(Y_{n+1} \in \hat{C}(X_{n+1})) \geq 1 - \alpha$.

The Computational Problem

The elegance of the theory masks a brutal computational reality. For regression problems, the candidate label $y$ ranges over the entire real line. Even after discretizing to a grid of $G$ values, you must refit the model $G$ times. The total cost is $O(G \times T_{\text{fit}})$, where $T_{\text{fit}}$ is the cost of fitting the model once. For a random forest with $T_{\text{fit}} = 10$ seconds and a grid of $G = 1000$ points, computing the prediction set for a single test point takes nearly 3 hours.

For classification with $K$ classes, the situation is better: you only need to try $K$ candidate labels. But even there, refitting a neural network $K$ times per test point is impractical for modern models.

Full conformal requires refitting for every candidate label. Split conformal fits once and calibrates on held-out data.

Transductive vs. Inductive

The distinction between full and split conformal maps onto a deeper distinction in learning theory: transductive vs. inductive inference.

Transductive learning uses all available data — including the test point's features — jointly. The full conformal method is transductive: it considers the augmented dataset $\{Z_1, \ldots, Z_n, (X_{n+1}, y)\}$ as a whole, and the model is fitted on this augmented set. The advantage is that no data is wasted. The disadvantage is the computational cost of revisiting all data for each test prediction.

Inductive learning builds a model from training data once, then applies it to test data without revisiting the training process. Split conformal prediction is inductive: the model is trained on $D_1$, the calibration scores are computed on $D_2$, and test predictions use only the pre-computed model and quantile. The advantage is efficiency. The disadvantage is the data split: some data goes to training and some to calibration, and neither portion sees the full dataset.

The Split: What Do You Lose?

Splitting costs you in two ways, but neither is as severe as it might first appear.

Loss 1: Training data. The model $\hat{f}$ is trained on $n_1 < n$ points instead of $n$. With less training data, the model may be slightly worse, producing larger residuals and therefore wider intervals. But the coverage guarantee is exact for any split. Even if you train on 10 points and calibrate on 990, the guarantee holds. The split affects efficiency (interval width), not validity (coverage).

Loss 2: Quantile estimation. The conformal quantile $\hat{q}$ is estimated from $n_2$ calibration scores. The variability of this estimator decreases as $O(1/\sqrt{n_2})$. With $n_2 = 500$, the quantile is already quite stable; with $n_2 = 100$, there is noticeable variability but the coverage guarantee still holds exactly. The variability affects the width of the interval (it may fluctuate from one random split to another), not the validity of the coverage.

In practice, a 50-50 or 70-30 split (training-calibration) works well for most problems. The Lei et al. (2018) paper showed that the efficiency loss from splitting is modest compared to the enormous computational savings.

The Mondrian Approach

One of the most prescient ideas in the 2005 book was the Mondrian conformal predictor, named after the painter Piet Mondrian. The idea: partition the data into groups (or "categories"), and run conformal prediction separately within each group. If you partition the calibration set into $K$ groups and compute a separate quantile within each group, you get group-conditional coverage:

This is stronger than marginal coverage. It guarantees that coverage holds not just on average, but within each group. The cost is that each group has fewer calibration points, so the quantile estimates are noisier and the intervals may be wider.

The Mondrian approach was an early form of what we now call adaptive or conditional conformal prediction. The idea of making intervals adapt to local difficulty — the problem we tackled in posts 3 and 8 using other methods — was already present in the original framework. Modern methods like conformalized quantile regression (CQR) and locally-weighted conformal prediction can be viewed as continuous generalizations of the Mondrian partition idea.

The Mondrian approach bridges vanilla conformal (constant width) and modern adaptive methods (smooth adaptation). It was proposed in 2005, more than a decade before adaptive conformal methods became popular.

A Formal Summary

The following table summarizes the key properties of the three approaches.

Probability Without Measure Theory

The standard foundation for probability is Kolmogorov's measure-theoretic framework (1933): a probability space $(\Omega, \mathcal{F}, P)$ where $P$ is a countably additive measure. Events have probabilities, random variables have distributions, and theorems like the law of large numbers and the central limit theorem follow from the axioms.

Vovk and Shafer proposed an alternative foundation: game-theoretic probability. In their framework, there is no underlying probability measure. Instead, probability emerges from a sequential game between two players: Skeptic (who bets) and Reality (who chooses outcomes). A probabilistic statement is "true" if Skeptic cannot become infinitely rich by betting against it. If a law of large numbers holds, it is because any betting strategy that bets against the sample mean converging to the true mean will go bankrupt. The measure-theoretic probability is recovered as a special case, but the game-theoretic framework is more general: it applies even when no probability measure exists.

This is not merely a philosophical curiosity. The game-theoretic framework leads naturally to online guarantees — guarantees that hold sequentially, one observation at a time, without any probabilistic assumptions about how the data are generated. Conformal prediction is a direct product of this way of thinking.

The Connection to Algorithmic Randomness

Vovk's route to conformal prediction passed through algorithmic randomness, a branch of computability theory that defines what it means for an individual sequence to be "random." The key definition, due to Martin-Lof (1966), is:

A sequence $z_1, z_2, \ldots$ is Martin-Lof random (with respect to a computable probability measure $P$) if no effective statistical test can distinguish it from a typical sequence drawn from $P$.

An effective statistical test is, roughly, a computable function that assigns a "nonrandomness score" to each initial segment of the sequence. If the test score grows without bound, the sequence fails the test and is declared non-random. The key theorem: a sequence is Martin-Lof random if and only if no computable martingale (a betting strategy with expected value zero) can make the bettor infinitely rich by betting on the sequence.

The connection to conformal prediction is this: the conformal p-value $p(y)$ for a candidate label $y$ is essentially a randomness test. It checks whether the augmented sequence $z_1, \ldots, z_n, (x_{n+1}, y)$ "looks random" — i.e., whether the test point's nonconformity score has a rank that is consistent with exchangeability. If the p-value is very small (the test point's score has an extreme rank), the candidate $y$ fails the randomness test and is excluded from the prediction set. The prediction set is the collection of all $y$ values that pass the test.

This perspective explains why conformal prediction requires so few assumptions. A randomness test does not need to know the distribution; it only needs to check whether the observed data are consistent with the hypothesis that the data are exchangeable. The test is purely structural — it examines ranks, not magnitudes — and structural tests are inherently distribution-free.

Online Conformal Prediction

The game-theoretic framework naturally extends conformal prediction to the online (sequential) setting. In the online setting, data arrive one at a time: at each round $t$, Nature reveals $X_t$, the forecaster produces a prediction set $\hat{C}_t(X_t)$, and then Nature reveals $Y_t$. The forecaster wants cumulative coverage: the fraction of rounds where $Y_t \in \hat{C}_t(X_t)$ should converge to $1 - \alpha$.

In the batch setting (split conformal), we have a fixed calibration set and the coverage guarantee is over the randomness of the test point. In the online setting, there is no fixed calibration set — the "calibration set" is the entire history of past observations. The full conformal method adapts naturally: at each round, the augmented dataset includes all past observations plus the new test point with each candidate label. The prediction set for $Y_t$ is the set of labels with conformal p-values above $\alpha$.

The online coverage guarantee takes the following form. Define the error process:

Under exchangeability, $\mathbb{E}[\text{Err}_t \mid \text{past}] \leq \alpha$ at each round. The cumulative error rate satisfies:

with high probability. The cumulative coverage converges to $1 - \alpha$ at rate $O(\sqrt{\log T / T})$. This is not merely an asymptotic statement; the finite-time bound holds with explicit constants.

The Supermartingale Argument

Vovk's original coverage proof used a betting argument rooted in game-theoretic probability. The structure is as follows.

Suppose, for contradiction, that the conformal prediction sets systematically fail to cover — that is, the error rate exceeds $\alpha$ by some positive margin. Then Skeptic can adopt the following betting strategy: at each round, bet that the true label will fall outside the prediction set. If the prediction set has coverage $1 - \alpha$, this bet has expected payoff zero (it is a fair bet). If coverage is less than $1 - \alpha$, the bet has positive expected payoff, and Skeptic's wealth grows.

Formally, define Skeptic's wealth process $\mathcal{K}_t$ as:

where $\lambda > 0$ is a betting fraction. Under exchangeability, this is a nonnegative supermartingale with $\mathbb{E}[\mathcal{K}_t] \leq \mathcal{K}_0 = 1$. By Ville's inequality (the supermartingale analogue of Markov's inequality):

If the error rate persistently exceeds $\alpha$, the wealth $\mathcal{K}_t$ grows exponentially (because $\mathbb{E}[\text{Err}_s - \alpha] > 0$ at each round). But the supermartingale bound says the wealth cannot grow unboundedly with positive probability. Contradiction. Therefore, the cumulative error rate must converge to at most $\alpha$.

This argument has several notable features. It is constructive: it specifies a concrete betting strategy. It is anytime-valid: the bound holds simultaneously for all time horizons $T$, not just a single fixed $T$. And it is non-asymptotic: the bound is finite-sample, with explicit constants that depend on $\lambda$ and $\delta$.

The supermartingale proof by contradiction: if coverage fails, Skeptic can make unbounded wealth, which contradicts the supermartingale property.

Adaptive Conformal Inference

The game-theoretic perspective also opens the door to adaptive online conformal prediction. In the standard setting, exchangeability assumes the data distribution is stationary. But in many real-world applications — financial time series, sensor data, clinical monitoring — the distribution changes over time.

Gibbs and Candes (2021) proposed Adaptive Conformal Inference (ACI), which maintains the betting-style guarantee even under distribution shift. The idea: instead of using a fixed significance level $\alpha$, update $\alpha_t$ at each round based on whether coverage was achieved:

where $\gamma > 0$ is a learning rate. If the prediction set covered at round $t$ ($\text{Err}_t = 0$), the significance level increases slightly, making the next prediction set smaller. If coverage failed ($\text{Err}_t = 1$), the significance level decreases, making the next prediction set larger. This feedback loop tracks the changing error rate and adapts the prediction set size accordingly.

The coverage guarantee of ACI is:

The first term decreases with $T$ (more data helps), and the second is the price of adaptation (larger $\gamma$ tracks distribution shifts faster but introduces more variability). Choosing $\gamma = T^{-1/2}$ balances these terms and gives convergence at rate $O(T^{-1/2})$.

Remarkably, this guarantee holds without any assumption on how the distribution changes. The data need not be exchangeable, need not be stationary, and need not follow any parametric model. The guarantee is purely about the cumulative error rate of the adaptive procedure. This is as close to "assumption-free" as sequential prediction gets.

The Big Picture

The history of conformal prediction is a story about the slow convergence of several intellectual traditions. Permutation tests provided the symmetry argument. Algorithmic randomness provided the framework for defining "consistency with randomness" without a probability model. Game-theoretic probability provided the betting language and supermartingale machinery for online guarantees. And the practical innovations — split conformal, Mondrian conformal, adaptive conformal inference — made these ideas computationally and statistically useful.

What makes conformal prediction special is not any single technical trick. It is the depth of the foundation: a guarantee that holds because exchangeability forces ranks to be uniform, and ranks being uniform is a consequence so basic that it requires almost nothing of the data-generating process. The method is not robust despite its simplicity; it is robust because of its simplicity. When your guarantee depends on almost nothing, almost nothing can break it.