Prediction Intervals and Split Conformal Prediction › Formula

We now build the machinery. The aim is to turn a bare point prediction into a band, and to do it in a way that comes with a guarantee we can state precisely. Three questions have to be answered along the way:

1. What are we trying to cover? Not the regression surface, but the next observation. If the response retains nondegenerate noise, additional fitting data do not remove that noise.
2. How do we measure a miss? We need a number that grows when a candidate observation becomes implausible under the fitted model, a nonconformity score.
3. How do we convert finitely many measured misses into a margin that is valid for the next one? This is where exchangeability enters, and where a seemingly cosmetic $+1$ turns out to carry the entire guarantee.

Notation throughout: fit the predictor and score on $\mathcal D_{\mathrm{train}}$, then use a disjoint calibration set $\mathcal D_{\mathrm{cal}}=\{(X_i,Y_i)\}_{i=1}^n$. A fresh test pair is $(X_{n+1},Y_{n+1})$. Conditional on the fitted score function, require these $n+1$ calibration and test scores to be exchangeable. Independent observations from one distribution, with an independent fitting split, are a sufficient setting. The separate test sample in the example evaluates the completed procedure.

Before building the procedure, distinguish three targets: a population quantity, a future observation, and a class label. The target determines which inclusion statement we need to establish.

A confidence interval targets a population quantity, such as a mean, coefficient or quantile. For example, an interval for $\mu(x)=\mathbb E[Y\mid X=x]$ aims to contain that fixed conditional mean across repeated fitting samples at the specified input. Its width can shrink under regular consistent estimation; shrinking is not an unconditional property of every confidence procedure.

A prediction interval targets a future observation and aims for a specified inclusion probability. It accounts for response variation as well as uncertainty in the fitted predictor. With persistent nondegenerate noise it can remain wide even when mean estimation is precise. For a symmetric noise distribution, a symmetric band around its center uses the $(1-\alpha)$ quantile of the absolute noise as its half-width.

A prediction set is the classification analogue: a random subset $\hat C(x) \subseteq \{1,\dots,K\}$ with $P\big(Y_{n+1} \in \hat C(X_{n+1})\big) \ge 1-\alpha$. Whereas an interval is an ordered range on the real line, a set is an unordered collection of labels, and its natural size measure is cardinality rather than length.

For comparison, consider the correctly specified linear model with $n$ fitting observations and $p$ nonconstant predictors plus an intercept. In this comparison only, $n$ denotes fitting size rather than calibration size. Assume $n>p+1$, a fixed full-rank design, independent Gaussian errors with variance $\sigma^2$, and an independent future error with the same variance. At a fixed new design vector $x_0$, the Gaussian prediction interval is

$$\hat y_0 \pm t_{n-p-1,\,1-\alpha/2}\;\hat\sigma\sqrt{1 + x_0^\top (X^\top X)^{-1} x_0},$$

where:

• $\hat y_0 = x_0^\top \hat\beta$: the fitted value at the new input
• $\hat\sigma^2$: the residual variance estimate (the sum of squared residuals divided by $n-p-1$)
• $X$: the full-rank $n\times(p+1)$ training design matrix, including an intercept column and $p$ nonconstant predictors
• $t_{n-p-1,1-\alpha/2}$: the $1-\alpha/2$ quantile of a $t$ distribution with $n-p-1$ degrees of freedom
• $x_0^\top (X^\top X)^{-1} x_0$: the new-point leverage, with $x_0$ containing the intercept and the same $p$ predictors as the design matrix

The "$1+$" inside the square root reflects the additional noise of the future observation. It is there because the error of prediction decomposes as

$$Y_{n+1} - \hat y_{n+1} \;=\; \underbrace{\big(Y_{n+1} - \mu(x_{n+1})\big)}_{\text{irreducible noise}} \;+\; \underbrace{\big(\mu(x_{n+1}) - \hat y_{n+1}\big)}_{\text{estimation error}} .$$

Under these Gaussian-model assumptions, conditional on the fixed design and new input, the new observation error is independent of the fitting-sample estimation error. Their variances therefore add:

$$\operatorname{Var}(Y_{n+1} - \hat y_{n+1}) = \underbrace{\operatorname{Var}\big(Y_{n+1} - \mu(x_{n+1})\big)}_{\text{noise variance } \sigma^2} + \underbrace{\operatorname{Var}\big(\mu(x_{n+1}) - \hat y_{n+1}\big)}_{\text{estimation variance}} .$$

where:

• $Y_{n+1}$: the future observation whose value is not yet known
• $\hat y_{n+1}$: the fitted model's prediction at the future input $x_{n+1}$
• $\mu(x_{n+1})$: the true conditional mean $\mathbb{E}[Y \mid X = x_{n+1}]$
• $\sigma^2$: the noise variance $\operatorname{Var}(Y_{n+1} - \mu(x_{n+1}))$

Under regular increasing-sample designs with a fixed number of predictors, mean-estimation uncertainty decreases. The mean confidence interval uses only the estimation term, while the prediction interval also contains the future-noise term. For a 95% Gaussian interval, its large-sample noise margin is approximately $1.96\sigma$. This comparison explains the extra $1$ in the displayed square root.

The weakness of this construction is the assumption stack: Gaussian errors, constant variance, a correctly specified linear model, and independent observations. Split conformal keeps the same target, the observation, but replaces every one of those assumptions with exchangeability alone.

The engine of conformal prediction is the nonconformity score. The idea is to condense each candidate pair $(x, y)$ and the fitted model $\hat f$ into a single number, $s(x,y)$, that grows as the pair becomes less plausible under the model. A score is doing its job when it is small for observations the model explains well and large for observations it explains poorly.

For regression with a scalar response the standard choice is the absolute residual

$$s_i = \big|\,y_i - \hat f(x_i)\,\big|,$$

where:

• $s_i$: the nonconformity score for calibration point $i$, measuring how far the model's prediction misses the observed response
• $y_i$: the observed response for calibration point $i$
• $\hat f(x_i)$: the fitted model's prediction for calibration point $i$

For classification with fitted class probabilities $\hat p(y \mid x)$ the standard choice is

$$s_i = 1 - \hat p\big(y_i \mid x_i\big),$$

where:

• $s_i$: the nonconformity score for calibration point $i$, equal to one minus the probability of the observed label
• $\hat p(y_i \mid x_i)$: the fitted probability the model assigns to the observed label $y_i$ at input $x_i$
• $y_i$: the observed class label of calibration point $i$

This score is small when the model assigns high probability to the observed label and large when it assigns low probability. Many other scores are possible; we will meet several. Choose and freeze the score function without using the calibration or test outcomes for fitting or selection. At prediction time, evaluate it for candidate labels or responses; the unknown true future response is not supplied to the procedure.

Given the scores $s_1,\dots,s_n$, sort them and write the order statistics as

$$s_{(1)} \le s_{(2)} \le \dots \le s_{(n)} .$$

The conformal quantile at miscoverage level $\alpha$ is the order statistic at index

$$k = \left\lceil (n+1)(1-\alpha) \right\rceil ,$$

For $k\le n$, set $\hat q=s_{(k)}$. If $k=n+1$, set $\hat q=+\infty$ and return the full response space. Clipping $k$ to $n$ would lose the requested guarantee at small calibration sizes.

where:

• $n$: the calibration set size
• $\alpha$: the miscoverage level, so $1-\alpha$ is the nominal coverage
• $k$: the ceiling index $\lceil (n+1)(1-\alpha)\rceil$, which can equal $n+1$; that case uses an infinite threshold
• $s_{(k)}$: the $k$-th smallest calibration score
• $\hat q$: the conformal score threshold; for absolute-residual regression it is the interval half-width

This implementation selects an order statistic without interpolation. Other quantile conventions need to be checked against the stated finite-sample cutoff; an ordinary interpolating call is not generally equivalent.

The $\lceil \cdot \rceil$ symbol denotes the ceiling function: the smallest integer greater than or equal to its argument. For $n = 100$ and $\alpha = 0.10$ we get $(n+1)(1-\alpha) = 101 \times 0.90 = 90.9$, so $k = \lceil 90.9 \rceil = 91$ and $\hat q = s_{(91)}$.

To see the role of $n+1$, first assume the $n+1$ exchangeable scores are almost surely distinct. The test score then has a uniform rank in $\{1,\ldots,n+1\}$. For $k\le n$, it falls below the $k$th calibration score exactly when that rank is at most $k$. Thus

$$P\big(s_{n+1} \le s_{(k)}\big) = \frac{k}{n+1},$$

where:

• $s_{n+1}$: the nonconformity score of the future test point, an exchangeable draw from the same pool as the calibration scores
• $s_{(k)}$: the $k$-th smallest calibration score, used as the conformal quantile $\hat q$
• $k$: the ceiling index $\lceil (n+1)(1-\alpha)\rceil$, computed from the calibration size $n$ and miscoverage level $\alpha$

The equality holds because $s_{n+1} \le s_{(k)}$ happens exactly when the rank of $s_{n+1}$ is one of the $k$ smallest.

The rank calculation behind the guarantee can be inspected directly. With $n=10$ and $\alpha=0.10$, we have $(n+1)(1-\alpha)=11\times0.90=9.9$, so $k=\lceil9.9\rceil=10$. Under distinct exchangeable scores, the test score has eleven equally likely ranks, and ranks one through ten fall at or below the calibrated cutoff $s_{(10)}$; only the largest rank falls outside it. The cell below prepares the rank probabilities for the figure: it computes the ceiling index without clipping, builds uniform rank probabilities, and flags the ranks covered by the cutoff. This is an exact rank illustration, with no sampled data.

This bound arises because $k \le n$ requires $\lceil (n+1)(1-\alpha)\rceil \le n$, equivalently $(n+1)(1-\alpha) \le n$ since $n$ is an integer. Solving:

$$\begin{aligned} (n+1)(1-\alpha) &\le n \\ n+1 - \alpha n - \alpha &\le n \\ 1 - \alpha &\le \alpha n \\ n &\ge \frac{1-\alpha}{\alpha} = \frac{1}{\alpha} - 1 . \end{aligned}$$

Putting the pieces together, split conformal regression is a four-step procedure, sometimes called inductive conformal prediction (Papadopoulos et al., 2002). Notice how cleanly the steps separate the modelling from the calibration. The model is fit and frozen first, and only then does the conformal machinery measure its mistakes.

1. Fit the point predictor $\hat f$ on $\mathcal{D}_{\text{train}}$. Nothing about this step is special; use whatever model you like and whatever model selection procedure you like, as long as it never touches $\mathcal{D}_{\text{cal}}$.
2. Compute calibration scores $s_i = |y_i - \hat f(x_i)|$ for $i = 1,\dots,n$.
3. Compute $k=\lceil(n+1)(1-\alpha)\rceil$. Set $\hat q=s_{(k)}$ if $k\le n$ and $\hat q=+\infty$ otherwise.
4. For a new input $x$, return $\hat C(x) = \big[\hat f(x) - \hat q,\; \hat f(x) + \hat q\big]$ when $\hat q$ is finite, and return the full response space when $\hat q = +\infty$.

The interval is the point prediction plus or minus a constant margin. When $\hat q$ is finite its width is exactly $2\hat q$ everywhere, independent of $x$; when $\hat q = +\infty$ the set is the full response space. Here $\hat q$ is the conformal quantile computed from calibration scores, and there is no guarantee that averaging a realized test batch reproduces the nominal coverage. That is both its simplicity and its main weakness, and we will return to the consequence shortly.

Step 4 is worth reading backwards, because that is how the guarantee is usually proved. The event $Y_{n+1} \in \hat C(X_{n+1})$ is the same as $|Y_{n+1} - \hat f(X_{n+1})| \le \hat q$, which is the same as $s_{n+1} \le \hat q$. Everything reduces to the rank argument in the previous subsection. The proof does not require a particular predictor family or parametric response law. Its sampling argument uses exchangeability of the held-out scores.

For classification, the same four steps apply with a different score, and step 4 becomes a set construction:

$$\hat C(x) = \big\{\, y \in \{1,\dots,K\} \;:\; 1 - \hat p(y \mid x) \le \hat q \,\big\} = \big\{\, y \;:\; \hat p(y \mid x) \ge 1 - \hat q \,\big\}.$$

where:

• $y$: a candidate class label in $\{1,\dots,K\}$
• $\hat p(y \mid x)$: the fitted probability the model assigns to label $y$ at input $x$
• $\hat q$: the conformal quantile from the calibration scores, so $1-\hat q$ is the probability threshold

For the score $1-\hat p(y\mid x)$, classification keeps labels whose fitted probability is at or above $1-\hat q$. The calibration step chooses the threshold automatically, in such a way that the fraction of calibration points whose nonconformity score $1-\hat p(y_i\mid x_i)$ exceeds $\hat q$ is at most $\alpha$. This uses held-out outcomes to calibrate set inclusion. It is different from Probability Calibration, which evaluates or adjusts probability reliability. Accurate class probabilities are useful, but are not required for this marginal set-coverage proof.

The threshold applies to each candidate label, so set size varies with the probability vector and the calibrated cutoff. Several labels may pass, or none may pass. The marginal guarantee controls overall inclusion under its sampling assumptions. For a proper nonempty subset of the class space, set size alone does not determine its conditional inclusion probability. Set size alone also does not establish an out-of-distribution interpretation.

Several properties follow from the construction and are worth naming. Treat them as a checklist of what the formula does and does not give us.

• Coverage is finite-sample. Under the score-exchangeability condition, $P(Y_{n+1}\in\hat C(X_{n+1}))\ge1-\alpha$ holds for every $n\ge1$ and $0<\alpha<1$, using the infinite-threshold branch when necessary. No asymptotic approximation is used.
• The guarantee is distribution-free over score distributions satisfying exchangeability. The predictor and score construction must be fixed before calibration; no correctly specified parametric response model is required.
• Monotonicity in $\alpha$. With the same calibration scores, decreasing $\alpha$ cannot decrease $k$ or $\hat q$. The sets are nested, although the discrete index can stay unchanged over a range of levels.
• Invariance to monotone rescaling of scores. Replacing $s$ by any strictly increasing transform $g(s)$ yields the same prediction sets, since the ranking is unchanged. The transform must be well-defined and the same for every calibration and candidate score. The small-calibration branch still returns the full response space; it does not require evaluating $g(+\infty)$. Dividing by an input-dependent scale is a different score construction and can change the resulting sets.
• Width depends on the score distribution. With a fixed score and independent calibration samples growing in size, the empirical cutoff converges to its population score quantile at continuity and identifiability points. When the fitted score also changes, additional consistency assumptions are needed. Improving a predictor under one loss does not universally shrink every conformal cutoff.
• Ties can make deterministic inclusion conservative: $P(s_{n+1}\le\hat q)$ may exceed $k/(n+1)$. This removes the distinct-score upper slack bound; it does not by itself prove that an interval can be narrowed while keeping the same guarantee.