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

1 Conformal Prediction

• The practical algorithm computes a score for each calibration example, sets q̂ to the ⌈(n+1)(1−α)⌉/n quantile, and includes test outputs meeting the resulting threshold.In classification, the score is 1−f̂(X_i)_{Y_i}, and the prediction set contains labels y with f̂(X_test)_y ≥ 1−q̂.Source: §1 · p. 4, §1.1 · p. 5

Remarks

• Prediction sets adapt to each input, becoming larger for uncertain or intrinsically difficult examples while remaining interpretable as plausible outputs.Their size provides an indicator of model certainty, and the construction extends naturally beyond classification to regression.Source: Remarks · p. 5
• The method adjusts potentially overfit softmax probabilities using fresh held-out data rather than trusting their heuristic uncertainty estimates directly.With approximately 500 unseen calibration points, α=0.1 guarantees that at least 90% of true-class softmax outputs exceed the threshold 1−q̂.Source: Remarks · p. 5

1.1 Instructions for Conformal Prediction

• Conformal prediction uses calibration scores and an empirical quantile to turn any model’s uncertainty heuristic into prediction sets with guaranteed marginal coverage.For i.i.d. calibration and test data, coverage lies between 1 −α and 1 −α + 1/(n+1); split conformal prediction is the primary version discussed. [1–3]Source: §1 · p. 4, §1.1 · pp. 5–6
• For discrete labels, tie-breaking may be needed to attain the stated upper coverage bound, though this randomization is typically ignored in practice.The note attributes this modification to discreteness and cites.Source: §1.1 · p. 5

Choice of score function

• The guarantee holds even for uninformative scores, but score quality determines whether sets are small and useful or large and uninformative.Scores that rank model errors well yield smaller sets for easy inputs; random-noise scores can produce large random subsets that only satisfy marginal coverage.Source: Choice of score function · p. 6

2.1 Classification with Adaptive Prediction Sets

• Adaptive prediction sets (APS), developed to address subgroup undercoverage and overcoverage, greedily include classes by cumulative softmax mass and conformal calibration restores rigorous coverage.The method uses all class softmax outputs, calibrates a quantile, and forms sets with a tie-breaking modification to avoid zero-size sets.Source: §2.1 · pp. 6–7

2.2 Conformalized Quantile Regression

• Conformalized quantile regression converts fitted lower and upper quantiles into valid continuous intervals by expanding or shrinking their separation with a calibrated constant.Quantile regression can be added to any base model through a quantile or pinball loss and often provides good coverage before conformalization.Source: §2.2 · pp. 8–9

2.3.1 The Estimated Standard Deviation

• Conformal prediction calibrates estimated standard deviations into valid intervals of the form ˆf(x)±ˆqˆσ(x), even when the Gaussian modeling assumption is unreliable.The standard deviation is commonly produced from a model trained with a Gaussian likelihood, but the conditional distribution need not actually be Gaussian.Source: §2.3.1 · p. 9

2.3.2 Other 1-D Uncertainty Estimates

• Other one-dimensional uncertainty scalars—including residual estimates, ensembles, dropout, perturbations, generative noise, and adversarial changes—receive the same conformal calibration treatment.The resulting intervals are valid and symmetric about ˆf(x), but uncertainty scalars may not scale properly with α, so quantile regression is generally preferred when available.Source: §2.3.2 · p. 9

2.4 Conformalizing Bayes

• Conformalized Bayesian prediction sets are valid and, under the assumptions in [11], have the smallest average size among conformal procedures achieving 1 −α coverage.The procedure uses posterior predictive density as its conformal score and is Bayes optimal under specified technical assumptions.Source: §2.4 · pp. 10–11

Discussion

• Together, the examples show that conformal prediction is easy to implement and computationally trivial while supporting objectives such as average size, adaptivity, and Bayes risk.The section focuses on one-dimensional Y; richer outputs, multiple error notions, or unequal error costs motivate risk-control methods discussed elsewhere.Source: §2 · p. 6, Discussion · p. 11

3 Evaluating Conformal Prediction

• Adaptivity requires small sets for easy inputs and large sets for hard inputs, because minimum average set size alone does not guarantee useful uncertainty estimates.Coverage guarantees do not imply adaptivity, so procedures should be evaluated using metrics that assess how set sizes reflect example difficulty.Source: §3 · p. 12, §3.1 · p. 12

3.1 Evaluating Adaptivity

• Set-size histograms assess precision and difficulty sensitivity, while conditional-coverage metrics test whether large sets actually occur on hard examples.Feature-stratified coverage compares groups or binned continuous features, whereas size-stratified coverage is general and requires no prespecified features.Source: §3.1 · pp. 12–14
• Conditional coverage is stronger than marginal coverage and is generally impossible to guarantee, so evaluation must measure how closely procedures approximate 1 −α across inputs or groups.Marginal coverage can concentrate errors in particular groups, whereas conditional coverage requires at least 90% coverage for every subset in the 90% example.Source: §3.1 · p. 13, Figure 10 · p. 13

3.2 The Effect of the Size of the Calibration Set

• n = 1000 calibration points typically yields coverage between .88 and .92, while explicit formulas compute the calibration size needed for coverage 1 −α ± ϵ with probability 1 −δ.The coverage guarantee holds for any calibration-set size, but larger sets reduce finite-sample fluctuations; Table 1 reports required sizes for selected parameters.Source: §3.2 · p. 14, Table 1 · p. 15

3.3 Checking for Correct Coverage

• Correctness checks repeat calibration and validation splits, expecting empirical coverage histograms and means to center approximately at 1 −α.Finite n, nval, and R create benign fluctuations, and exact theory distinguishes these from deviations indicating implementation problems.Source: §3.3 · p. 15
• Efficient evaluation caches conformal scores before repeatedly recomputing coverage over random data splits, reducing the cost of intensive repeated assessments.The suggested evaluations may require at least 100 runs, and caching can accelerate slow score computations by orders of magnitude.Source: §3 · p. 12, §3.3 · p. 15, Figure 12 · p. 16

4.1 Group-Balanced Conformal Prediction

• Group-balanced conformal prediction calibrates separately within observed groups to guarantee 1 −α coverage for every group under i.i.d. sampling [14].Standard marginal coverage may allow errors to concentrate in one group, whereas group-specific quantiles provide the stated error-control property.Source: §4.1 · pp. 16–17

4.2 Class-Conditional Conformal Prediction

• Class-conditional conformal prediction calibrates separately by class and tests each provisional class with its class-specific threshold, guaranteeing class-balanced coverage under i.i.d. sampling.Unlike group balancing, the correct test-time class is unknown, so the procedure evaluates candidate classes individually.Source: §4.2 · pp. 17–18

4.3 Conformal Risk Control

• Conformal risk control selects prediction-set conservativeness to bound any bounded loss that decreases as sets grow, extending beyond miscoverage to losses such as false negative rate [17].For multilabel classification, setting α = 0.1 guarantees that the resulting set contains 90% of true classes on average.Source: §4.3 · pp. 18–19

4.4 Outlier Detection

• Conformal outlier detection calibrates an unsupervised outlier score on clean data and flags test points above its quantile, controlling false positives under i.i.d. sampling.Its effectiveness depends on choosing a score that distinguishes expected outliers from clean data; the method also admits a hypothesis-testing interpretation.Source: §4.4 · pp. 19–20

4.5 Conformal Prediction Under Covariate Shift

• Under known covariate shift, weighted conformal prediction reweights calibration scores toward the test distribution and provides valid prediction sets when P(Y|X) remains fixed.The approach addresses a restricted but practical shift setting and requires knowledge of the covariate shift.Source: §4.5 · pp. 20–21

4.6 Conformal Prediction Under Distribution Drift

• For distribution drift, weighted quantiles that discount less representative older samples retain marginal coverage, with exactness when shift magnitude is known and no coverage loss without shift [26].In practice, drift distances are unknown, so rolling windows or smooth decay are used; weighting also reduces effective sample size.Source: §4.6 · p. 22
• Under distribution drift, weighted conformal prediction’s coverage variance scales as 1/n_eff and can explode when n_eff is small.The effective sample size n_eff can be large if too many weights w_i are small.Source: §4.6 · p. 22
• Further theory of weighted conformal prediction under distribution drift is available in [26].Source: §4.6 · p. 22

5 Worked Examples

• The worked examples provide Jupyter notebooks so the demonstrated techniques can be conveniently replicated and extended.The notebooks accompany the examples across the practical applications in this section.Source: §5 · p. 23

5.1 Multilabel Classification

• In multilabel classification, conformal risk control thresholds pretrained class probabilities to guarantee that the average fraction of missed ground-truth classes is below α.The example applies false-negative-rate loss to MS COCO image labels.Source: §5.1 · p. 23, Figure 13 · p. 23

5.2 Tumor Segmentation

• In tumor segmentation, conformal risk control thresholds pixelwise tumor probabilities to guarantee that the average fraction of missed tumor pixels is below α.The worked example provides results and code on a gut-polyp dataset.Source: §5.2 · pp. 23–24, Figure 14 · p. 23

5.3 Weather Prediction with Time-Series Distribution Shift

• Weighted conformal prediction achieves desired temperature-interval coverage in steady state and recovers quickly after a distribution change, outperforming an unweighted baseline.The fixed-window procedure lacks a formal coverage bound because adjacent-data total variation cannot be measured, and its window was chosen heuristically.Source: Figure 15 · p. 24, §5.3 · p. 25

5.4 Toxic Online Comment Identification via Outlier Detection

• At type-1 error level α = 10%, conformal outlier detection correctly flags 70% of toxic comments while guaranteeing that at most an α fraction of future nontoxic text is flagged.The procedure thresholds calibration toxicity scores using the ⌈(n + 1)(1 −α)⌉-smallest score.Source: §5.4 · p. 25

5.5 Selective Classification

• Selective classification uses strategic abstention to achieve higher accuracy than the base image-classification model, with the deployed threshold satisfying the target guarantee with high probability.Because selective accuracy is non-monotone in the confidence threshold, Learn then Test scans conservative upper bounds on selective misclassification risk.Source: §5.5 · p. 26

6 Full conformal prediction

• Full conformal prediction avoids a separate calibration split by training on all n + 1 data points, trading split conformal’s computational efficiency for statistical efficiency.It is also presented as historically important, useful when statistical efficiency is paramount, and interpretable as a hypothesis-testing procedure.Source: §6.1 · p. 27, §6 · p. 27

6.1 Full Conformal Prediction

• For each candidate y, full conformal prediction refits a permutation-invariant model on the augmented data, scores every observation, and retains values sufficiently consistent with the observed sample.This directly loops over the possible label space and forms the prediction set for the unknown response.Source: §6.1 · p. 27
• The resulting set retains the full conformal coverage guarantee under i.i.d. sampling and, more generally, exchangeability, assuming a symmetric fitting algorithm [1].The guarantee relies on exchangeability of the candidate score sequence, with the stated upper bound also applying for continuous score functions.Source: §6.1 · p. 27
• Full conformal prediction is generally computationally costly: with |Y| = K, evaluating the prediction set requires (n + 1) · K model fits.For continuous label spaces, the method typically discretizes the space, although some score functions permit exact computation.Source: §6.1 · p. 27

6.2 Cross-Conformal Prediction, CV+, and Jackknife+

• Cross-conformal prediction and CV+/Jackknife+ use fewer fits while using all data for fitting and calibration, occupying intermediate points between split and full conformal prediction.These methods trade computational and statistical efficiency differently and have corresponding statistical guarantees described in their cited works [41, 42].Source: §6.2 · p. 28

7 Historical Notes on Conformal Prediction

• The history focuses on distribution-free methods that are model-agnostic, data-distribution-agnostic, and valid in finite samples, rather than asymptotic traditions such as permutation tests, quantile regression, rank tests, or bootstrap methods.Source: §7 · p. 28

Origins

• Conformal prediction grew from Kolmogorov and Vovk’s work on finite Bernoulli sequences, with randomness deficiency, tolerance intervals [63–66], and exchangeability inspiring nonconformity scores and predictive regions.The rough notion of collectives became exchangeability, while randomness deficiency became nonconformity.Source: Origins · pp. 29–30

Enter Conformal Prediction

• The framework now called conformal prediction was developed by Vovk, Gammerman, Saunders, and Vapnik in 1996–1999, first using e-values [74] and then p-values [5, 75], followed by split-conformal predictors, Venn Predictors, COPA, cross-conformal and Venn-Abers predictors [78], and conformal predictive distributions.Source: Enter Conformal Prediction · p. 30

Current Trends

• Recent work adapts conformal methods to practical desiderata, distribution shift, dependent data, counterfactuals, survival analysis, privacy, and multivalid coverage, while conformal predictive distributions and calibration methods broaden uncertainty quantification.Examples include adaptive conformal prediction, weighted conformal prediction for slowly changing time series, and procedures for outlier detection, change-point detection, covariate-shift testing, and streaming-risk monitoring.Source: Current Trends · p. 31
• Applications now span large-scale deep learning, computationally efficient and few-shot prediction, election forecasting, clinical studies [124] [125], criminal-justice risk forecasts [125] [127], robotic planning [128] [129], and open-source tooling such as MAPIE.The field is growing rapidly because machine-learning deployment has exposed the limits of point predictions; the authors encourage readers to contribute to practical and technical advances.Source: Current Trends · pp. 31–32

A Distribution-Free Control of General Risks

• Distribution-free risk control calibrates a parameter λ for predictions T_λ so user-defined risks are controlled with high probability.The guarantee applies to arbitrary risks and multiple risks without retraining the pretrained model.Source: A Distribution-Free Control of General… · p. 39
• The framework covers risks beyond coverage, including recall, intersection-over-union, and coverage in instance segmentation.These risks can be automatically controlled using distribution-free statistics.Source: A Distribution-Free Control of General… · p. 39
• Learn then Test supports multi-label classification by thresholding class probabilities to control false-discovery rate.The selected threshold λ determines which classes enter the predicted label set.Source: A Distribution-Free Control of General… · pp. 39–40
• It also jointly controls OOD-detection false alarms and prediction-set miscoverage among inputs identified as in-distribution.The two coordinates of λ separately govern OOD thresholding and prediction-set size.Source: A Distribution-Free Control of General… · p. 40

A.1 Instructions for Learn then Test

• The LTT calibration procedure associates a null hypothesis H_λ with every candidate parameter and seeks parameters where the risk-control condition holds.Its formal development introduces the risk-control property before describing the calibration algorithm.Source: §A.1 · p. 40, §A.1.1 · p. 43

A.1.1 Crash Course on Generating p-values

• For each λ, calibration data produce a p-value whose low value provides evidence against the null hypothesis that risk is uncontrolled.Testing at level δ rejects when p_λ < δ; for example, δ = 5% implies an expected error rate of at most 5%.Source: §A.1.1 · p. 43
• The p-values used by LTT are distribution-free valid, with Hoeffding-based choices for risks bounded in [0, 1].Tighter alternatives, including the Hoeffding-Bentkus p-value, can provide greater power while preserving validity.Source: §A.1.1 · pp. 43–44

Setup

• A pre-trained model can be post-processed into predictors that control a chosen risk regardless of model quality or data distribution.The framework assumes i.i.d. data and constructs predictors from a pre-trained model without requiring a good initial fit.Source: Formal notation for error control · p. 40

Parameterized predictors

• The predictor T_λ maps features to outputs such as responses or prediction sets, with λ selected from a discrete parameter set Λ.If needed, a naturally non-discrete parameter space is finely discretized, such as Λ = {0, 0.001, ..., 1}.Source: Formal notation for error control · p. 40

Risk definition

• Risk is defined as a functional of T_λ, typically the expected loss on an independent test point, with miscoverage as a key example.For deterministic λ, the resulting risk R(T_λ) is a deterministic scalar abbreviated as R(λ).Source: Formal notation for error control · p. 40

Risk control

• An algorithm using calibration data produces a random parameter λ̂, and T_λ̂ is risk-controlling when its risk meets the target with probability at least 1 − δ.The failure probability reflects selecting an unfavorable calibration set and is at most δ.Source: Formal notation for error control · p. 41

Procedure

• Learn then Test searches candidate functions {Tλ}λ∈Λ using calibration data and returns a subset bΛ⊆Λ whose selected candidates control risk below the user-specified threshold α.The procedure estimates each candidate’s risk and retains λ values certified to control risk.Source: The Learn then Test procedure · p. 42
• The procedure tests Hλ: R(λ)>α for each candidate, computes concentration-inequality p-values, and combines them with a familywise-error-rate-controlling procedure such as Bonferroni.Rejecting Hλ identifies a candidate whose risk is controlled with high probability.Source: The Learn then Test procedure · p. 42

Guarantee

• Theorem A.1 guarantees that the returned bΛ satisfies the procedure’s stated statistical guarantee, so any selected λ̂∈bΛ yields an (α, δ)-RCP.This guarantee follows from the combined p-value computation and multiple-testing steps.Source: The Learn then Test procedure · p. 42

A.1.2 Crash Course on Familywise-Error Rate Algorithms

• Testing millions of hypotheses makes at least one false rejection increasingly likely, motivating explicit familywise-error-rate control.FWER is the probability of making at least one false rejection.Source: §A.1.2 · p. 44
• Naively thresholding independent uniform p-values at δ yields FWER 1 − (1 − δ)^|Λ|, which approaches 1 when all hypotheses are null.This demonstrates that multiplicity can make unadjusted testing unreliable.Source: §A.1.2 · p. 44
• FWER-controlling algorithms select the largest hypothesis set with FWER ≤ δ; Bonferroni achieves this by testing each hypothesis at δ/|Λ| via a union bound.The section notes that improvements over Bonferroni are possible.Source: §A.1.2 · p. 44
• Fixed-sequence testing orders hypotheses before calibration, tests them sequentially at level δ, and stops after the first acceptance.The order can reflect prior beliefs, such as sorting larger risk-controlling λ values first.Source: §A.1.2 · p. 44
• Despite testing encountered hypotheses at level δ, fixed-sequence testing still controls FWER and works well for monotone or near-monotone risks such as false-discovery rate.The procedure is illustrated with δ = 0.05.Source: §A.1.2 · p. 45, Figure 21 · p. 45
• Sequential graphical testing extends fixed-sequence ideas to non-monotone functions, enabling powerful procedures designed for particular problems or automatically discovered from data.The topic receives detailed treatment in [18], which the section omits for simplicity.Source: §A.1.2 · p. 45
• After users specify Λ, T_λ, and R, the LTT pipeline automatically produces bΛ, and three worked examples demonstrate how to choose these components in practice.The pipeline is described in PyTorch code in Figure 20.Source: §A.1.2 · p. 45

B Examples of Distribution-Free Risk Control

• The examples in this section apply distribution-free risk control to practical machine-learning problems as pragmatic prototypes for real-world use.Their goal is to provide an arsenal of workable distribution-free risk-control methods.Source: B Examples of Distribution-Free Risk… · p. 45

Setup

• Multi-label classification represents each label as a set of classes, with a pretrained model estimating the probability that each class belongs in that set.The prediction set includes the estimated most likely classes for an input such as an image.Source: §B.1 · p. 46

FDR control

• LTT selects a threshold λ from a discretized grid to satisfy a probabilistic bound on the false-discovery rate.The threshold is chosen from Λ = {0, 0.001, ..., 1}.Source: §B.1 · p. 46
• The false-discovery rate is the expected false-discovery proportion, measuring how often prediction sets contain mostly classes from the true label set.With α = 0.1 and δ = 0.1, the procedure targets the stated FDR guarantee, with probability taken over the calibration-set randomness.Source: §B.1 · p. 46

Implementation

• The implementation uses fixed-sequence testing for the nearly monotone FDR risk and recommends the stronger HB p-value over the simple Hoeffding p-value.The procedure is implemented in PyTorch and evaluated on the MS-COCO image dataset.Source: §B.1 · p. 46, Figure 23 · p. 46

• The method uses an OOD score and class-probability model, returning an empty set when the OOD score exceeds λ1 and otherwise constructing an APS-like prediction set.The parameter λ has two coordinates, with λ2 governing prediction-set formation; the grid discretizes [0, 1] × [0, 1] into N^2 boxes, typically with N ≈1000.Source: §B.2 · p. 47
• The procedure controls two risks simultaneously: false-flag probability and conditional miscoverage among inputs deemed in-distribution.With α = (0.05, 0.1), it guarantees at most 5% false flags and 90% conditional coverage.Source: §B.2 · p. 47
• LTT tests a composite null for each λ, combining intermediate p-values to identify parameters that satisfy both risk constraints.The development uses HB-based p-values and can combine them with sequential graphical testing or a Bonferroni region; see [18].Source: §B.2 · p. 48
• Each element of the returned parameter region controls both OOD-detection and prediction-set coverage risks simultaneously.The procedure is implemented in PyTorch in Figure 24.Source: §B.2 · p. 48, Figure 24 · p. 48
• Conditional coverage is computed only over calibration examples with nonempty prediction sets, so its empirical risk differs from a standard empirical risk [18].Not all calibration points are deemed in-distribution and receive prediction sets.Source: §B.2 · p. 48

Per-trial coverage distribution

• Each trial’s empirical coverage C_j follows a BetaBinom(nval, n + 1 − l, l) distribution because its conditional binomial mean is beta distributed.This analytic distribution exactly characterizes the expected coverage histogram.Source: C Concentration Properties of the… · p. 49

Validation-set effects

• As nval grows, the empirical-coverage histogram converges to the beta distribution, whereas small validation sets inflate its variance.With sufficiently many trials R, the histogram converges to the analytical PMF determined by α, n, and nval.Source: Figure 25 · p. 49, C Concentration Properties of the… · p. 49

Experiment-level averaging

• The average coverage C over R experiments has no closed-form distribution because it averages independent beta-binomial variables, but its distribution is readily simulated.Finite R introduces an additional source of fluctuation, and Figure 26 visualizes realistic choices of R, nval, and n.Source: C Concentration Properties of the… · p. 49, Figure 26 · p. 50

Implementation debugging

• Practitioners should compare empirically computed coverage with simulations from Figure 26; substantial disagreement may indicate a conformal-implementation error.The linked notebook supports simulations for arbitrary n, R, and nval.Source: C Concentration Properties of the… · p. 50

Coverage guarantee

• Theorem D.1 guarantees the stated conformal prediction coverage for i.i.d. calibration and test observations, with prediction sets defined using the calibrated score threshold.The result is the formal version of the introduction’s coverage property.Source: D Theorem and Proof: Coverage Property… · p. 50
• The same coverage guarantee holds under exchangeability, a weaker condition than i.i.d. sampling.The theorem is presented as a standard split-conformal validity proof first appearing in.Source: D Theorem and Proof: Coverage Property… · p. 50

Lower-bound proof

• Exchangeability makes the test score equally likely to fall at any rank among the calibration scores, yielding the desired lower-bound coverage.The proof assumes distinct scores to avoid ties; a general-case proof is referenced in.Source: D Theorem and Proof: Coverage Property… · pp. 50–51

Upper bound

• Theorem D.2 supplies a finite-sample upper bound on coverage when the conformal scores have a continuous joint distribution.The continuity condition avoids ties, while vanishing random noise can enforce it in practice; the proof is deferred to Theorem 2.2 of.Source: D Theorem and Proof: Coverage Property… · p. 51