A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification

Anastasios N. Angelopoulos; Stephen Bates

Source-linked AI summary

A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification

Anastasios N. Angelopoulos, Stephen Bates

arXiv:2107.07511v6Jul 15, 2021cs.LGcs.AImath.STstat.MEstat.ML

TL;DR

High-risk machine learning applications need rigorous uncertainty quantification, but model-based heuristics may not provide coverage. This paper presents conformal prediction as a simple calibration procedure that produces distribution-free prediction sets with validity guarantees across diverse tasks.

Problem
High-risk machine learning applications require uncertainty quantification, while heuristic model uncertainty does not guarantee prediction-set coverage.
Method
The paper calibrates prediction sets from any fitted model using a small calibration dataset and conformal scores.
Results
Conformal prediction provides validity guarantees for prediction sets under arbitrary score functions and unknown data distributions.
Takeaways & Limitations
The framework is simple to implement and extends to outlier detection, image segmentation, time-series prediction, and group-balanced coverage.
Takeaways & Limitations
Prediction-set usefulness depends primarily on the score function, with poorly ranked scores producing large or otherwise useless sets.

Abstract

from arXiv · show

Black-box machine learning models are now routinely used in high-risk settings, like medical diagnostics, which demand uncertainty quantification to avoid consequential model failures. Conformal prediction is a user-friendly paradigm for creating statistically rigorous uncertainty sets/intervals for the predictions of such models. Critically, the sets are valid in a distribution-free sense: they possess explicit, non-asymptotic guarantees even without distributional assumptions or model assumptions. One 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%. It is easy-to-understand, easy-to-use, and general, applying naturally to problems arising in the fields of computer vision, natural language processing, deep reinforcement learning, and so on. This hands-on introduction is aimed to provide the reader a working understanding of conformal prediction and related distribution-free uncertainty quantification techniques with one self-contained document. We lead the reader through practical theory for and examples of conformal prediction and describe its extensions to complex machine learning tasks involving structured outputs, distribution shift, time-series, outliers, models that abstain, and more. Throughout, there are many explanatory illustrations, examples, and code samples in Python. With each code sample comes a Jupyter notebook implementing the method on a real-data example; the notebooks can be accessed and easily run using our codebase.

1 Conformal Prediction

Conformal prediction calibrates a pre-trained model’s uncertainty scores to produce prediction sets with distribution-free marginal coverage. Split conformal prediction applies broadly beyond classification and remains useful only when scores meaningfully rank model error.

1 Conformal Prediction: With i.i.d. calibration and test data, conformal prediction achieves marginal coverage between 1 −α and 1 −α + 1/(n+1).The guarantee holds for user-chosen error rate α and calibration size n, with tie-breaking needed for the upper bound in discrete-output settings.
1 Conformal Prediction: The method calibrates a score function on held-out data, takes its ⌈(n+1)(1−α)⌉/n quantile, and uses that threshold to form prediction sets.For image classification, the score is one minus the model’s softmax probability for the true class, so larger scores indicate worse agreement.
1 Conformal Prediction: Prediction sets adapt to each input, becoming larger when the model is uncertain or the example is intrinsically difficult.Set size therefore provides an indicator of model certainty while retaining the coverage guarantee.
1 Conformal Prediction: Conformal prediction converts any model’s heuristic uncertainty notion into rigorous prediction sets for discrete or continuous outputs, including classification and regression.Its validity holds for any score function and possibly unknown data distribution under the stated calibration framework.
1 Conformal Prediction: The guarantee does not require informative scores, but poor scores can produce useless sets; effective scores should rank examples by model error, yielding smaller sets for easy inputs and larger sets for hard ones.Random-noise scores can produce sets containing a random sample of the label space.

2 Examples of Conformal Procedures

This section presents practical conformal procedures for classification and continuous-output regression, showing how calibration turns heuristic uncertainty into valid prediction sets. The examples span adaptive classification sets, quantile- and uncertainty-based intervals, and Bayes-optimal prediction sets under technical assumptions.

Overview: Together, the examples provide practical roadmaps for designing score functions targeting average size, adaptivity, and Bayes risk, while remaining easy to implement and computationally trivial.The section focuses on one-dimensional Y and treats smaller nonconformity scores as indicating greater model confidence.
Classification: Adaptive prediction sets address subgroup miscoverage by ordering classes by softmax score and conformally including them until a calibrated threshold is reached.Unlike the earlier smallest-average-size method, APS avoids undercoverage of hard subgroups and overcoverage of easy ones, while conformal calibration supplies rigorous uncertainty.
Continuous regression: Conformalized quantile regression produces valid continuous prediction intervals by expanding or shrinking fitted lower and upper quantiles using a calibration-derived constant.The intervals achieve approximately 90% target coverage and can be added to models by replacing standard losses with quantile loss.
Continuous regression: Conformal prediction can also rigorously calibrate heuristic scalar uncertainty estimates, including predicted standard deviations or modeled residual magnitudes.This is useful because parametric uncertainty estimates may be unreliable when the conditional outcome distribution violates assumptions such as Gaussianity.
Bayesian prediction: Bayesian conformal prediction incorporates prior information while producing valid sets that, under assumptions in [11], have the smallest average size among conformal procedures with 1 −α coverage.The result is stated in terms of Bayes risk and requires the technical assumptions specified in [11].

3 Evaluating Conformal Prediction

This section evaluates conformal prediction along two axes: adaptivity to input difficulty and correctness of its coverage guarantees. It also examines calibration-set size, recommending about 1,000 points for typical deployments.

Evaluating adaptivity: Conformal procedures should produce smaller sets for easy inputs and larger sets for hard inputs, so evaluations must measure adaptivity beyond marginal coverage.Average set size alone is insufficient because the smallest sets may not reflect uncertainty faithfully.
Set size: Set-size histograms assess precision through average size and adaptation through the spread of sizes, but dynamic range alone does not establish difficulty-sensitive adaptation.Large sets must specifically occur for hard examples, motivating conditional-coverage metrics.
Conditional coverage: Conditional coverage requires approximately 1 −α coverage for every input value, but unlike marginal coverage it is generally impossible to guarantee and must be empirically approximated.Unequal errors across groups can satisfy marginal coverage while violating conditional coverage.
Conditional-coverage metrics: Feature-stratified and size-stratified coverage compare observed subgroup coverage with 1 −α, using feature bins or prediction-set-size bins to identify violations.Size-stratified coverage is more general because users need not specify important discrete features in advance.
Calibration-set size: Figure 11 shows that 1,000 calibration points typically yield coverage between .88 and .92, supporting a guideline of about 1,000 points for most purposes.Calibration-set size also contributes to finite-sample variability and coverage checks.

4 Extensions of Conformal Prediction

This section extends conformal prediction beyond standard supervised prediction to group- and class-balanced coverage, alternative risk guarantees, outlier detection, and covariate shift. These methods provide practical statistical guarantees under their respective conditions, including i.i.d. sampling or known covariate shift.

4.1 Group-balanced coverage: Group-balanced conformal prediction calibrates separately within observed groups and guarantees the desired error-control property for every group under i.i.d. sampling.The relevant group can be a categorical feature or a post-processed discretization of an input, and the test group selects its calibration threshold.
4.2 Class-balanced coverage: Class-balanced conformal prediction calibrates within each possible class and includes a candidate class using its class-specific threshold, guaranteeing class-wise error control under i.i.d. sampling.Because the true test class is unknown, the procedure evaluates provisional response classes rather than directly selecting an observed test-group threshold; Vovk established this guarantee in.
4.3 Conformal risk control: Conformal risk control extends guarantees beyond miscoverage to any bounded loss that decreases as prediction sets become more conservative, including false negative rate.For multilabel classification, setting α = 0.1 guarantees that the calibrated prediction set contains 90% of the true classes on average.
4.3 Conformal risk control: In multilabel classification, increasing the threshold parameter λ produces more conservative sets, while calibration controls the average fraction of omitted true classes.The method post-processes model scores into sets of classes exceeding the threshold and calibrates λ to satisfy the chosen risk guarantee.
4.4 Outlier detection: Conformal prediction also calibrates unsupervised outlier scores from clean data to provide statistical error-control guarantees for detecting test points from a different distribution.The procedure begins with a heuristic outlier score, where larger values indicate greater outlier likelihood, and then conformalizes that score.
4.5 Covariate shift: Weighted conformal prediction addresses covariate shift from P to Ptest, but the presented guarantee applies to the restricted case of known shift.When distribution shift is absent, the coverage loss is zero regardless of the chosen weights; under varying shift, weights trade off coverage effects through weighted calibration errors, as observed previously in [27].

5 Worked Examples

The worked examples apply conformal methods to multilabel classification, tumor segmentation, time-series temperature prediction, outlier detection, and selective classification. They show how distribution-free guarantees adapt to structured outputs, temporal dependence, toxicity screening, and strategic abstention.

Reproducible examples: Each worked example is accompanied by Jupyter notebook code designed to make the results reproducible and extensible.The examples include results on MS COCO, a gut-polyp dataset, Yandex Weather Prediction, and the Jigsaw Multilingual Toxic Comment Classification dataset.
Multilabel classification and tumor segmentation: Conformal risk control thresholds pretrained models to control false negative rates in multilabel image classification and tumor segmentation.For multilabel classification, the loss is the fraction of true labels missed; for tumor segmentation, it is the average fraction of tumor pixels missed, under exchangeable calibration data.
Time-series temperature estimation: Weighted conformal prediction uses a fixed K-sized window to form temperature prediction sets under serially dependent, non-exchangeable weather data.The example uses the Yandex Weather Prediction dataset, an ensemble of 10 pretrained CatBoost models, and averaged predictions and variances.
Selective classification: Selective classification uses Learn then Test to choose a confidence threshold that guarantees high selective accuracy while allowing the model to abstain.Because accuracy need not be monotone in the confidence cutoff, the method scans thresholds using conservative upper bounds on selective misclassification risk.

6 Full conformal prediction

Full conformal prediction avoids a separate calibration split by retraining on every candidate label, preserving the usual coverage guarantee under exchangeability but requiring substantially more computation. Its prediction set contains labels whose hypothetical augmented datasets remain consistent with the observed data, equivalently via a permutation-test acceptance rule.

6 Full conformal prediction: Full conformal prediction trains on all observed data rather than using a separate calibration dataset, improving statistical efficiency at the cost of repeated model fitting.This contrasts with split conformal prediction, which fits once but sacrifices efficiency through data splitting.
6 Full conformal prediction: For each candidate label y, full conformal prediction refits the model on the augmented data, computes conformity scores, and retains labels sufficiently consistent with the observed examples.The procedure loops over all y ∈ Y and forms a confidence set for the unknown response.
6 Full conformal prediction: Under i.i.d. sampling and a symmetric algorithm, the resulting set has the same validity guarantee as conformal prediction generally, with the result extending to exchangeable data.The proof relies on exchangeability of the relevant scores; the upper bound also holds for continuous score functions.
6 Full conformal prediction: If the label space has size K, computing full conformal prediction requires (n + 1) · K model fits, creating a substantial computational burden.For continuous labels, the space is typically discretized, although some score functions permit exact computation.
6 Full conformal prediction: The prediction set is equivalently the collection of candidate labels accepted by a level α permutation test for exchangeability, meaning hypothetical labels consistent with the observed data are retained.The test rejects when the candidate score is large; non-rejected values are exactly those in the conformal set.

7 Historical Notes on Conformal Prediction

Conformal prediction emerged from distribution-free methods that are model-agnostic, distribution-agnostic, and finite-sample valid, with roots in algorithmic randomness and later development into a modern predictive framework. Its history includes foundational milestones, broader popularization, and limits on conditional guarantees.

Distribution-free conformal prediction targets methods that are model-agnostic, data-distribution-agnostic, and valid in finite samples.
Early influences included Kolmogorov and Vovk’s work on algorithmic randomness, with nonconformity scores arising from the idea of local randomness deficiency.Atypical points have large randomness deficiency, paralleling large nonconformity scores.
Lei, Wasserman, and colleagues helped popularize conformal prediction in the United States through distribution-free predictive inference for regression [80].Their work also developed efficient approximations in special cases such as kernel density estimation and kernel regression.
For arbitrary continuous distributions, distribution-free conditional coverage is impossible, while vanishing-width intervals require effective test-covariate support below the squared sample size [88].
The field remains young, practical, approachable, and open to significant technical contributions in distribution-free uncertainty quantification.The authors encourage readers to implement these methods and pursue further research.

A Distribution-Free Control of General Risks · A.1 Instructions for Learn then Test

The framework controls arbitrary user-defined risks, including multiple risks, by calibrating parameters of a pretrained model without retraining. Learn then Test uses distribution-free p-values to identify parameter values whose risks are controlled with high probability.

A Distribution-Free Control of General Risks: Learn then Test calibrates parameters of a pretrained model to control arbitrary risks, including multiple risks, without retraining.The method forms predictions T_λ(x) from the model and a tunable parameter λ, then selects a calibrated λ̂.
A Distribution-Free Control of General Risks: The risk-control goal is to choose λ̂ so a user-defined risk tolerance α is satisfied with high probability over the calibration data.This guarantee is high-probability rather than an expectation guarantee.
A Distribution-Free Control of General Risks: Examples include multi-label classification, where thresholding predicted class probabilities controls the false-discovery-rate risk.The threshold parameter λ determines which classes enter the predicted label set.
A Distribution-Free Control of General Risks: Another application jointly controls out-of-distribution detection and 90% prediction-set coverage using a two-coordinate parameter.One model scores how out-of-distribution an input is, while another supplies class probabilities.
A.1 Instructions for Learn then Test: The Learn then Test procedure associates a null hypothesis H_λ with every parameter and seeks parameters where the null of uncontrolled risk can be rejected.The formal development introduces risk-control notation and then gives a calibration algorithm.
A.1.1 Crash Course on Generating p-values: Calibration summarizes evidence for risk control at each λ with a p-value p_λ, rejecting H_λ when the p-value is below the testing level δ.A p-value below 5% supports rejection with an expected error rate no greater than 5%.
A.1.1 Crash Course on Generating p-values: LTT requires distribution-free-valid p-values; Hoeffding’s inequality provides a simple choice for risks bounded in [0, 1], while tighter alternatives such as Hoeffding-Bentkus are also available [18].The examples include bounded risks such as coverage, IOU, and FDR, and any valid p-value can be used.

Formal notation for error control

The framework starts with i.i.d. feature-response data and a pre-trained model, then constructs predictors indexed by a discrete parameter to control a user-chosen risk. Risk-controlling prediction guarantees that a calibration-data-selected parameter satisfies the target risk with probability at least 1 − δ.

Given i.i.d. data and a pre-trained model, the framework constructs predictors that control risk regardless of model-fit quality or the data distribution.
A parameterized map T_λ transforms features into predictions or prediction sets, with λ selected from a discrete, possibly discretized, parameter set Λ.
Risk is defined from a loss averaged over a fresh test point, including miscoverage as a familiar special case, and becomes the deterministic scalar R(λ) for fixed λ.
An algorithm may choose a random parameter λ̂ from calibration data; T_λ̂ is (α, δ)-risk-controlling when R(λ̂) meets the target with probability at least 1 − δ.

The Learn then Test procedure

The Learn then Test procedure searches over candidate set functions, estimates their risks on calibration data, and returns those whose risks are statistically controlled. It does so by testing risk-based null hypotheses with concentration-based p-values and combining them through familywise-error-rate control, yielding an (α, δ)-RCP for any selected returned function.

The Learn then Test procedure: Learn then Test searches a collection of candidate functions using calibration data and returns a subset of parameter values guaranteed to control the specified risk.The goal is to find a set function with risk below the user-specified threshold α.
The Learn then Test procedure: For each candidate λ, the procedure tests H_λ: R(λ) > α, where rejecting the null selects a risk-controlled parameter.
The Learn then Test procedure: It computes p-values from concentration inequalities and combines them with multiple-testing procedures that control the familywise error rate.Bonferroni correction is given as an example, while stronger p-values and FWER-controlling procedures are discussed separately.
The Learn then Test procedure: The returned subset satisfies the procedure’s statistical guarantee, so selecting any λ̂ from it makes T_λ̂ an (α, δ)-RCP.LTT decomposes risk control into p-value computation and multiple-testing combination.

A.1.2 Crash Course on Familywise-Error Rate Algorithms · B Examples of Distribution-Free Risk Control

Testing many hypotheses independently can make false rejection nearly certain, motivating familywise-error-rate procedures that combine p-values while preserving guarantees. The following examples translate distribution-free risk control into practical machine-learning workflows.

A.1.2 Crash Course on Familywise-Error Rate Algorithms: When millions of hypotheses are tested, the probability of at least one false rejection increases, creating the familywise-error-rate problem.FWER is the probability of making at least one false rejection.
A.1.2 Crash Course on Familywise-Error Rate Algorithms: Under independent uniform null p-values, naive thresholding at δ yields FWER 1 − (1 − δ)^|Λ|, which approaches 1.This demonstrates why testing each hypothesis directly at level δ fails to control multiplicity.
A.1.2 Crash Course on Familywise-Error Rate Algorithms: FWER-controlling algorithms seek the largest selected hypothesis set with FWER ≤ δ; Bonferroni achieves this by testing each hypothesis at δ/|Λ|.The guarantee follows from a union bound, though improvements over Bonferroni exist.
A.1.2 Crash Course on Familywise-Error Rate Algorithms: Fixed-sequence testing orders hypotheses before calibration, tests them sequentially at level δ, and stops at the first acceptance.For monotone or near-monotone risks, including false-discovery rate, this can retain FWER control while improving power.
A.1.2 Crash Course on Familywise-Error Rate Algorithms: Sequential graphical testing extends fixed-sequence ideas to non-monotone functions and can produce powerful, flexible procedures tailored to particular problems.Procedures may be designed for high power or discovered automatically from data; detailed treatment is deferred to [18].
A.1.2 Crash Course on Familywise-Error Rate Algorithms: The LTT pipeline automatically produces the selected hypothesis set once users specify Λ, Tλ, and R.The paper presents the pipeline in PyTorch and then uses worked examples to show how to choose these components in practice.
B Examples of Distribution-Free Risk Control: The practical examples provide distribution-free risk-control prototypes for real machine-learning problems.Their goal is to equip readers with pragmatic methods that can be applied to practical settings.

B.1 Multi-label Classification with FDR Control

This section applies multi-label classification to set-valued predictions, using estimated class probabilities and LTT to select a threshold with a probabilistic false-discovery-rate guarantee. FDR measures the expected false-discovery proportion, while the procedure uses fixed-sequence testing and a stronger HB p-value in practice.

Setup: Multi-label classification predicts a set of classes Ytest from features Xtest using a pre-trained model’s estimated class probabilities.The prediction task includes examples such as identifying classes contained in an image.
Threshold selection: LTT identifies threshold values λ that satisfy a precise probabilistic guarantee on the false-discovery rate.The candidate thresholds are selected from the discretized grid Λ = {0, 0.001, ..., 1}.
FDR control: FDR is the expected false-discovery proportion, so low FDR means the prediction set contains mostly elements from the true label set.With α = 0.1 and δ = 0.1, the procedure targets the stated probabilistic control guarantee.
Implementation: The practical implementation uses fixed-sequence testing because FDR is nearly monotone and employs the stronger HB p-value rather than the simple Hoeffding p-value.The procedure is implemented in PyTorch and applied to the MS-COCO image dataset.

B.2 Simultaneous Guarantees on OOD Detection and Coverage

This example simultaneously controls OOD false-flag risk and conditional prediction-set miscoverage. It uses an OOD score, class-probability model, and multi-dimensional LTT calibration to either abstain or output a prediction set.

B.2 Simultaneous Guarantees on OOD Detection and Coverage: The task combines flagging OOD inputs without too many false flags with producing high-probability prediction sets for inputs deemed in-distribution.These are the two stated classification goals.
B.2 Simultaneous Guarantees on OOD Detection and Coverage: The construction uses an OOD score and class-probability model: inputs exceeding λ1 yield ∅, while other inputs receive APS-like prediction sets filtered by λ2.The class-probability model could provide neural-network softmax outputs.
B.2 Simultaneous Guarantees on OOD Detection and Coverage: The two risks are false-flag probability and conditional miscoverage, with α1 controlling false flags and α2 controlling miscoverage among retained in-distribution points.For α = (0.05, 0.1), the stated guarantees are at most 5% false flags and 10% miscoverage under the described conditions.
B.2 Simultaneous Guarantees on OOD Detection and Coverage: LTT combines p-values for the multiple-risk null using sequential graphical testing rather than Bonferroni correction, while the construction discretizes [0, 1] × [0, 1] into N^2 boxes with N ≈1000.The empirical conditional risk differs from a standard empirical risk because calibration points can have empty prediction sets; see Section 4 of [18].
B.2 Simultaneous Guarantees on OOD Detection and Coverage: Every element of bΛ controls both OOD false-flag risk and conditional prediction-set coverage simultaneously.The procedure is implemented in PyTorch in Figure 24.

C Concentration Properties of the Empirical Coverage

Empirical coverage fluctuates because calibration and validation sets, and the number of trials, are finite. Its distribution is analytically characterized through beta-binomial variables, while practitioner-facing behavior can be studied by simulation and diagnostic plots.

Finite calibration size n and validation size nval create coverage fluctuations, with small validation sets producing high-variance estimates.These effects explain why empirical-coverage histograms can be wider than the limiting beta distribution.
Empirical coverage per trial follows a beta-binomial distribution, because its conditional binomial mean is beta distributed.The distribution is denoted BetaBinom(nval, n + 1 − l, l).
As nval grows, empirical-coverage histograms converge toward the analytical distribution; small validation sets inflate variance.Figure 25 visualizes this dependence for large R and varying nval.
Averaging over R independent beta-binomial trials has no closed-form distribution, but it can be simulated for realistic n, nval, and R.Figure 26 visualizes the resulting average empirical-coverage distribution.
Practitioners can debug conformal implementations by comparing empirically simulated coverage with the observed real-data coverage and Figure 26.Substantial mismatch suggests an implementation problem.

D Theorem and Proof: Coverage Property of Conformal Prediction

This section proves split-conformal prediction’s finite-sample coverage guarantee and explains that exchangeability suffices for validity. It also states an upper bound under continuous conformal-score distributions, with ties handled by vanishing random noise.

Proof of the lower bound: The lower-bound proof is the standard split-conformal validity argument, originally appearing in, and is reproduced for completeness.The presentation assumes distinct scores almost surely; a general treatment of ties is cited to.
Coverage guarantee: Theorem D.1 establishes the conformal calibration coverage guarantee for i.i.d. calibration and test data, extending formally to exchangeable observations.The resulting prediction sets are defined from the calibrated score threshold.
Proof of the lower bound: Exchangeability makes the test score equally likely to occupy any rank among the calibration scores, yielding the desired lower-bound coverage.The proof handles the infinite-threshold case trivially and otherwise reduces coverage to a rank event.
Upper bound: The continuity condition avoids ties; in practice, adding a vanishing amount of random noise to the score can enforce it.This makes the upper-bound assumption operationally unimportant.
Upper bound: Theorem D.2 states an upper coverage bound when the conformal scores have a continuous joint distribution.The corresponding proof is deferred to Theorem 2.2 of.