Conformal Prediction, by Hand

Prelude

The promise

Most uncertainty methods give you "a number that looks like uncertainty" without any guarantee that it actually is. Conformal prediction gives a finite-sample, distribution-free, model-free coverage guarantee: the interval contains the true value with probability at least $1 - \alpha$ on exchangeable data. Pick $\alpha = 0.1$, get 90% intervals.

The slogan. Trust your point predictor with whatever loss / training recipe / hyperparameters you already use. Just hold out a calibration set, take a quantile of residuals, and the guarantee is yours. No retraining. No new model.

Step 1

Split conformal regression

The simplest variant. Three sets: training, calibration, test. Train your favourite model $\hat f$ on training. On calibration, compute nonconformity scores $s_i = |y_i - \hat f(x_i)|$. Sort them. Take the $\lceil (1-\alpha)(n+1) \rceil / n$-th largest as $\hat q$. For any new $x$, the interval is $[\hat f(x) - \hat q,\, \hat f(x) + \hat q]$.

Theorem (Vovk, Gammerman, Shafer; 2005): if calibration and test data are exchangeable, this interval has marginal coverage at least $1 - \alpha$. No model assumptions; no distributional assumptions on $y$; nothing but a quantile.

Step 2

See it work

Heteroscedastic 1-D regression: noise grows with $|x|$. We fit a polynomial regressor on the training set, conformalise on a calibration set, and report empirical coverage on a large test set. Slide $\alpha$ and the calibration size and watch the coverage bar track the target.

α (miscoverage) 0.10 calibration size 100 variant target coverage 90.0% empirical coverage —

Black points: data. Solid blue: predictor. Teal band: conformal interval. Red dots: test points outside the band (should be α fraction).

Empirical coverage across resamples (target dashed). Coverage should track 1−α with no model assumptions.

Step 3

CQR — adaptive widths

Split conformal gives a constant-width interval everywhere — wasteful when noise is heteroscedastic. The fix: fit two quantile regressors $\hat q_{\alpha/2}, \hat q_{1-\alpha/2}$ on training; let $s_i = \max\{\hat q_{\alpha/2}(x_i) - y_i,\, y_i - \hat q_{1-\alpha/2}(x_i)\}$ be the calibration score. Take the $(1-\alpha)$ quantile $\hat q$. Interval at $x$ is $[\hat q_{\alpha/2}(x) - \hat q,\, \hat q_{1-\alpha/2}(x) + \hat q]$.

Coverage guarantee unchanged. Width adapts to local noise. Toggle CQR in the demo above to see the band breathe with the data.

Step 4

Time series + non-exchangeable data

The exchangeability assumption is broken in time series: today's distribution depends on yesterday. Two practical fixes:

Adaptive Conformal Inference (ACI; Gibbs & Candès, 2021). Maintain a running $\alpha_t$ that adjusts based on recent miscoverage: $\alpha_{t+1} = \alpha_t + \gamma\,(\alpha - \mathbb{1}\{y_t \notin C_t\})$. The interval width breathes with the drift.
EnbPI / weighted conformal. Replace the uniform empirical CDF over residuals with a weighted one that decays older points. Trades some marginal coverage for adaptivity.

Even outside time series, conformal can lose coverage when covariate-shift hits at deployment. Mondrian / class-conditional conformal partitions the calibration set by feature so the guarantee holds per group.

Step 4 ½

Conformal classification — adaptive prediction sets

For classification, the conformal output isn't an interval — it's a set of class labels. Adaptive Prediction Sets (APS; Romano et al., 2020) sort the softmax probabilities and add classes from highest to lowest until the cumulative probability exceeds a calibrated threshold $\hat q$. Coverage guarantee: the true class is in the set with probability at least $1 - \alpha$.

Easy points get small sets (often just 1 class); ambiguous points get larger sets. Average set size is the natural informativeness measure.

α (miscoverage) 0.10 target cov 90.0% empirical cov — avg set size —

Pool of test points colour-coded by predicted set size. Easy regions: singleton sets (lightest). Ambiguous boundaries: 2- or 3-class sets (darker). Slide α and watch sets shrink/grow.

What APS gets right. Set size adapts to difficulty. A trivially-classified point gets a singleton; an ambiguous point gets all the plausible classes; a wildly-confused point gets the full label set. Marginal coverage is guaranteed at $1-\alpha$ regardless of the underlying classifier's quality.

Step 5

Where conformal is the right tool

Deployed predictor add-on. Wrap any existing model with split-conformal: 200 calibration points, one quantile, ship a 90% interval. Five lines of code; no retraining.
Forecasting. Conformal-on-PatchTST gives interval forecasts at any horizon with a coverage guarantee — a much stronger claim than "we used a Bayesian neural network".
Regression with calibrated uncertainty. Heart-rate / respiration / blood-glucose estimates with calibrated intervals make safety claims realistic.
LLM hallucination control. Conformal language modelling (Quach et al., 2024) gives sets of candidate completions with marginal coverage — turning a free-form generator into a calibrated set predictor.
Multi-class classification with abstention. APS / RAPS variants produce conformal sets (subsets of class labels). When the set is large, the model is abstaining; route to a human.

Final takeaway. Conformal prediction is the cheapest way to add a guaranteed coverage band to any deployed model. It doesn't replace probabilistic methods (Bayesian, NPs, GPs), but it's the right safety net to wrap around them — and it costs almost nothing to add.

Step 6

The marginal-coverage theorem, with the fine print

Split conformal's guarantee is precise: for any nonconformity score $s$, exchangeable calibration set, and miscoverage $\alpha$,

Three subtleties to understand:

"Marginal" not "conditional". The guarantee is over the joint distribution of $(X, Y)$, not conditional on $X$. So you get 90% coverage averaged over inputs, but you don't get 90% coverage on every subgroup. A 90% interval can systematically miss on hard inputs and over-cover on easy ones.
The randomness is in the calibration set. Given a fixed calibration set, the coverage on test data is a fixed number — possibly above or below $1 - \alpha$. The theorem says averaged over draws of the calibration set, coverage hits the target.
Exchangeability is the only assumption. Calibration and test data must come from the same distribution (in fact, slightly weaker — they must be exchangeable as a single set). No assumption on the model, no Gaussian noise, no smoothness.

When does this fail in practice?

Distribution shift. Exchangeability is broken; coverage can drop arbitrarily. Use weighted conformal (Tibshirani et al., 2019) if you know the covariate-shift weights.
Adversarial inputs. Same problem from a different angle — the adversary has chosen the input to be unlike calibration. Conformal gives no defence.
Temporal drift. If your calibration set is from yesterday and your test set is from today, online conformal (ACI; Gibbs & Candès, 2021) maintains coverage by adapting the threshold over time.

Step 7

The conformal recipe, step by step

Split. Hold out a calibration set of size $n$. Typical $n = 500–2000$. Larger $n$ → tighter intervals; the relationship is $\sqrt{1/n}$.
Score. Define a nonconformity score $s(x, y)$. For regression: $|y - \hat\mu(x)|$ (vanilla); $|y - \hat\mu(x)| / \hat\sigma(x)$ (normalised); $\max(\hat q_\alpha(x) - y, y - \hat q_{1-\alpha}(x))$ (CQR). For classification: $1 - \hat p_y(x)$ (vanilla); cumulative-rank score (APS / RAPS).
Calibrate. Compute $\hat q$ = the $\lceil (n+1)(1-\alpha) \rceil / n$ quantile of $\{s(x_i, y_i)\}_{i=1}^n$.
Predict. $\hat C(x_{\text{new}}) = \{y : s(x_{\text{new}}, y) \le \hat q\}$.
Evaluate. On a held-out test set, check (a) empirical coverage ≈ $1 - \alpha$, (b) average set size or interval width (informativeness), (c) conditional coverage on important subgroups.

The score is the design knob. Marginal coverage is automatic for any score. Tight intervals require a score that scales with prediction difficulty — that's why CQR (for regression) and APS (for classification) outperform the vanilla absolute-residual / one-minus-softmax scores.

Step 8

Reading list

Vovk, Gammerman, Shafer (2005) — Algorithmic Learning in a Random World. The original book on conformal prediction.
Lei, Sell, Rinaldo, Tibshirani, Wasserman (2018) — Distribution-Free Predictive Inference for Regression. The split-conformal regression paper.
Romano, Patterson, Candès (2019) — Conformalized Quantile Regression.
Romano, Sesia, Candès (2020) — Classification with Valid and Adaptive Coverage (APS).
Angelopoulos, Bates (2021) — A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification. The most readable modern intro.
Tibshirani et al. (2019) — Conformal Prediction Under Covariate Shift.
Gibbs & Candès (2021) — Adaptive Conformal Inference. Online conformal for non-stationary data.