Conformal Prediction

Unlike Bayesian methods that assume a prior distribution, conformal prediction makes no assumptions about the underlying data distribution. The coverage guarantee holds for any finite sample size, not just asymptotically. This is critical in high-stakes domains like medical diagnosis or financial risk where distributional assumptions are unverifiable.

• Works with any pre-trained model (black-box compatible)
• Guarantees hold under the minimal assumption of exchangeability
• Valid for classification, regression, and structured prediction tasks

Instead of outputting a single point prediction, conformal prediction produces a prediction set — a collection of plausible labels or an interval — that contains the true value with a user-specified confidence level (e.g., 90%).

• For classification: outputs a set of classes like {cat, dog} rather than forcing a single choice
• For regression: produces a prediction interval [lower_bound, upper_bound]
• The set size adapts to prediction difficulty — harder cases yield larger, more cautious sets

The core mechanism relies on a conformity score — a heuristic that measures how unusual a potential label is relative to a calibration set of held-out examples. Common scores include:

• Classification: 1 minus the softmax probability of the true class
• Regression: Absolute residual normalized by a locally-weighted variance estimate
• Adaptive Prediction Sets (APS): Accumulated sorted softmax probabilities for ranked class inclusion

The nonconformity measure is the engine that determines set size and coverage.

Conformal prediction requires splitting data into three distinct partitions:

• Training set: Used to fit the underlying model
• Calibration set: Held-out data used to compute the empirical distribution of conformity scores — this is where the statistical guarantee is calibrated
• Test set: New instances where prediction sets are generated

The calibration set must be exchangeable with test data for the guarantee to hold. This is the weakest assumption in statistics that still enables rigorous inference.

Two computational paradigms exist for applying the framework:

• Transductive (Full) Conformal Prediction: Retrains the model for every possible label of every test point. Provides exact validity but is computationally prohibitive for large models.
• Inductive (Split) Conformal Prediction: Trains the model once, then uses a held-out calibration set. Computationally efficient and the standard approach in practice, at the cost of slightly wider prediction sets.

Most production deployments use the inductive variant.

Standard conformal prediction guarantees marginal coverage — the correct label is in the set on average across all test points. However, this can mask failures on important subpopulations.

• Marginal coverage: 90% guarantee holds over the entire distribution, but may be 70% for a minority subgroup
• Conditional coverage: Guarantees hold for every specific input or subgroup — much harder to achieve without distributional assumptions
• Mondrian conformal prediction: Achieves coverage conditional on discrete categories by stratifying the calibration set

The primary output of a conformal predictor. Instead of a single point prediction, it produces a set of plausible labels that is mathematically guaranteed to contain the true label with a user-specified probability (e.g., 90%).

• For classification: a subset of classes like {"cat", "dog"}
• For regression: a prediction interval with a lower and upper bound
• The set size adapts to difficulty—easy inputs get a single label, ambiguous inputs get a larger set

The defining property of conformal prediction: a finite-sample, distribution-free guarantee that the true label falls within the prediction set at a rate of at least 1 - α, where α is the user-chosen error rate.

• Marginal coverage: holds on average across all test points
• Conditional coverage: holds for each individual input (harder to achieve)
• Valid under the sole assumption of exchangeability—that the order of data points doesn't matter
• Does not require knowing the data distribution

A heuristic function that measures how unusual or atypical a new example is relative to a calibration dataset. This score is the engine of conformal prediction.

• For classification: often 1 - softmax probability of the true class
• For regression: the absolute residual between the predicted and actual value
• A higher score indicates the example is less conforming to the training pattern
• The choice of score function directly impacts prediction set efficiency

A held-out portion of the training data that is never used for model fitting. Its sole purpose is to compute the empirical distribution of nonconformity scores.

• Must be exchangeable with future test data
• Typically 20-30% of the available labeled data
• The model makes predictions on this set, and nonconformity scores are calculated
• The quantile of these scores determines the threshold for inclusion in prediction sets

The most computationally practical variant of conformal prediction. It avoids retraining the model by splitting the data once into a proper training set and a calibration set.

• Model is trained only on the proper training set
• Nonconformity scores are computed on the calibration set in a single pass
• Computationally cheap: no model retraining required
• Trade-off: slightly reduced statistical efficiency compared to full conformal prediction

The core statistical assumption underpinning the validity of conformal prediction. A sequence of data points is exchangeable if their joint distribution is invariant to permutation.

• Independent and identically distributed (IID) data is exchangeable
• Violations: time-series data with temporal drift, adversarial data ordering
• In non-exchangeable settings, coverage guarantees degrade
• Extensions like adaptive conformal inference relax this assumption for streaming data