Conformal Prediction and Uncertainty

A latency model predicts that the next request will finish in 40 milliseconds. Should a caller rely on a 50-millisecond deadline? A prediction interval such as [32, 48] adds information the point prediction lacks, but even that range isn't a promise about this particular request.

Statistical Learning and Generalization established why untouched evidence matters. Traditional confidence intervals often assume normally distributed errors or asymptotic large-sample limits. When production traffic experiences heavy tails or bursty queues, those parametric assumptions break down. Split conformal prediction circumvents this issue by using a separate calibration split to wrap any frozen model's point predictions with statistically rigorous prediction intervals or prediction sets $C(X)$.^{[1]Reference 1A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantificationhttps://arxiv.org/abs/2107.07511}

Under an exchangeability condition on the data, split conformal prediction guarantees that future outcomes fall inside the prediction set with at least a chosen probability:

$$\Pr\!\left(Y_{n+1} \in C(X_{n+1})\right) \geq 1 - \alpha$$

Here $\alpha \in (0, 1)$ represents the allowed miscoverage rate (for example, $\alpha = 0.20$ for an 80% coverage target). This guarantee holds for any sample size $n$, without requiring Gaussian errors, linear relationships, or parametric families.

All latency values below are synthetic teaching data. We start with predictions already made by a frozen model; this lesson calibrates their uncertainty rather than fitting another predictor.

Freeze the model before measuring its errors

Before calculating a radius, decide which rows are allowed to influence it. Three slices play different roles:

Choose features, preprocessing, model settings, and the score rule before using calibration outcomes. Any model selection needs its own validation data within the training workflow. Once calibration starts, freeze that whole prediction procedure, not just its final layer.

For a 40-millisecond prediction, an observed 44 milliseconds gives an error of 4; an observed 53 gives an error of 13. A simple regression nonconformity score records that miss as the absolute residual $s_i = |y_i - \widehat{y}_i|$. Larger scores mean the point prediction missed by more.

The finite-sample guarantee relies on exchangeable calibration and future examples, conditional on the fitted procedure: their joint distribution is unchanged by permuting their positions. Formally, for $n$ calibration points and one future test point:

$$P(Z_1, \dots, Z_n, Z_{n+1}) = P(Z_{\pi(1)}, \dots, Z_{\pi(n)}, Z_{\pi(n+1)})$$

for every permutation $\pi \in S_{n+1}$, where $Z_i = (X_i, Y_i)$. Independent draws from the same distribution satisfy this condition. A queueing time series, diurnal traffic swings, or an altered prompt distribution may not. Shuffling an already shifted log doesn't restore exchangeability.^{[2]Reference 2Conformal Prediction Beyond Exchangeabilityhttps://arxiv.org/abs/2202.13415}

A model was repeatedly tuned using the same nine examples later labeled as its calibration split. Why can't their residuals support the ordinary split-conformal guarantee?

Answer

Those outcomes influenced the model before calibration, so their residuals are no longer held-out measurements of a frozen predictor. Their apparent errors can be optimistically small, and the ordinary exchangeability argument for fresh request outcomes no longer follows.

Let nine errors choose the radius

Our nine held-out requests produce these sorted absolute errors, measured in milliseconds. Which position should set the radius for the next request?

$$[2, 3, 3, 4, 5, 6, 7, 8, 12]$$

For 80% target coverage, allow a miscoverage rate of $\alpha = 0.20$. With nine calibration errors plus one future error, there are ten possible rank positions. Covering the first eight positions gives 8/10 = 80%. The correction counts the future request as well as the calibration requests.

In general, with calibration size $n$, select the following residual quantile. Its order statistic, the value at a numbered position in the sorted sample, has rank:^{[1]Reference 1A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantificationhttps://arxiv.org/abs/2107.07511}

$$k = \left\lceil(n+1)(1-\alpha)\right\rceil = \lceil10 \times 0.8\rceil = 8$$

The ceiling brackets mean round upward. For example, an 85% target would require $\lceil10 \times 0.85\rceil = 9$, not eight. At our 80% target, rank eight selects an 8 ms error. Call this selected radius $q$. A new prediction of 40 milliseconds therefore gets:

$$[\widehat y - q, \widehat y + q] = [40 - 8, 40 + 8] = [32, 48]$$

The next cell constructs the absolute errors from frozen predictions and outcomes. Its helper selects an observed order statistic directly, avoiding interpolation between two residuals. Python index rank - 1 converts the one-based rank to a zero-based list position.

The helper returns inf when the requested rank exceeds the available scores. That's deliberate, not a numerical failure. At 90% coverage the ninth error gives radius 12; at 95% the required rank is ten. The standard rule then uses $q=+\infty$, giving the entire real line rather than inventing a tenth error.^{[1]Reference 1A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantificationhttps://arxiv.org/abs/2107.07511}

Check the boundary in code. Raising the target can only preserve or widen the interval:

Don't clip rank ten to nine: a largest-of-nine threshold supports a 90% lower bound in the no-ties case, not 95%. With 19 calibration errors, 95% first becomes possible with a finite observed threshold: $\lceil20 \times 0.95\rceil = 19$. That's a mathematical minimum, not a recommendation for a stable calibration sample. Known bounds on the outcome could support other finite sets; the unavailable threshold here is specific to this residual-quantile construction.

Why does the example choose the eighth residual instead of simply multiplying nine by 0.8 and rounding down?

Answer

The finite-sample conformal rank is ceil((n+1)(1-alpha)). For nine calibration rows and 80% coverage, that is ceil(10 times 0.8), which selects the eighth order statistic.

Why the extra rank gives coverage

Temporarily imagine ten distinct scores, one from the future request and nine from calibration. Exchangeability makes the future request equally likely to occupy any of the ten sorted positions. Its score is no larger than the eighth calibration score exactly when it lands in positions one through eight.

You can inspect every possible test position without a random simulation. The following scores are a separate rank-only example, not additional latency measurements. Each pass holds out one score and calibrates on the remaining nine:

Our latency fixture has tied errors at 3 ms. Ties don't invalidate the lower coverage bound when the set includes the boundary (score <= q); they can make coverage conservative. Don't discard tied rows or promise exact 80% coverage. When scores are almost surely distinct (continuous nonconformity scores), conformal prediction also provides a tight upper bound on coverage:

$$1 - \alpha \leq \Pr\!\left(Y_{\mathrm{new}} \in C(X_{\mathrm{new}})\right) \leq 1 - \alpha + \frac{1}{n+1}$$

The upper bound demonstrates that split conformal prediction isn't overly conservative. With $n = 9$ and $1 - \alpha = 0.80$, coverage is sandwiched between 80% and $80\% + 1/10 = 90\%$. The rank argument doesn't require the predictor to be correct; a poor predictor will usually pay through less useful intervals.^{[3]Reference 3Distribution-Free Predictive Inference for Regressionhttps://www.stat.cmu.edu/~ryantibs/papers/conformal.pdf}

Watch coverage appear in new requests

The interval [32, 48] covers an actual 44-millisecond outcome and misses 53 milliseconds. That single request tells us what the rule does, not whether the rule is reliable. Coverage is measured across a stream of new comparable examples.

Keep the 80% radius 8 fixed and inspect four new synthetic request outcomes. Each request has its own interval centered at its prediction. Before running the cell, predict which outcome falls outside.

A four-row observed coverage of 75% doesn't contradict an 80% marginal coverage guarantee. Four requests are a noisy sample, so the observed fraction can move around the target.

Two sources of variation exist: this calibration sample selected one particular radius, and the four test outcomes are another small sample. Even a very long test run with that fixed radius needn't achieve the nominal coverage. Standard split conformal isn't a guarantee conditional on one realized calibration set.^{[1]Reference 1A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantificationhttps://arxiv.org/abs/2107.07511}

Classification nonconformity scores and adaptive prediction sets

Conformal prediction isn't limited to regression intervals. In multiclass classification, the output $C(X) \subseteq \mathcal{Y}$ is a set of candidate classes guaranteed to contain the true label with probability at least $1 - \alpha$.

Different nonconformity scores produce different set behaviors:

1. Naive softmax score: Let $\widehat{f}(x)_y$ denote the model's estimated probability for class $y$. The score is $s(x, y) = 1 - \widehat{f}(x)_y$. After computing threshold $\widehat{q}$ on calibration data, the prediction set includes all classes whose predicted probability is at least $1 - \widehat{q}$:

$$C(X) = \left\{y \in \mathcal{Y} : \widehat{f}(X)_y \geq 1 - \widehat{q}\right\}$$

When a query is ambiguous and the model distributes probability thinly across many classes (for example, four classes near 0.25), no single class may exceed $1 - \widehat{q}$. That produces an empty prediction set $C(X) = \emptyset$.

1. Adaptive Prediction Sets (APS): To avoid empty sets and adapt set sizes to instance difficulty, sort the predicted class probabilities in descending order $\pi_{(1)}(x) \geq \pi_{(2)}(x) \geq \dots \geq \pi_{(K)}(x)$. Accumulate probabilities until reaching the true class label $y$:^{[1]Reference 1A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantificationhttps://arxiv.org/abs/2107.07511}

$$s(x, y) = \sum_{j=1}^{k} \pi_{(j)}(x) \quad \text{where } \pi_{(k)}(x) = y$$

At test time, the prediction set accumulates sorted classes until their cumulative probability mass reaches or exceeds the calibrated threshold $\widehat{q}$:

$$C(X) = \left\{\pi_{(1)}(x), \dots, \pi_{(m)}(x)\right\} \quad \text{where } m = \min\left\{j : \sum_{i=1}^j \pi_{(i)}(x) \geq \widehat{q}\right\}$$

On easy examples with high confidence (say, top class probability 0.98), $C(X)$ contains a single label. On difficult, ambiguous queries, $C(X)$ automatically expands to contain multiple classes, preserving marginal coverage while signaling uncertainty through set size.

Why does Adaptive Prediction Sets (APS) prefer accumulating sorted probabilities over thresholding individual softmax outputs?

Answer

Thresholding individual softmax probabilities can produce empty sets on difficult, ambiguous inputs where probability mass is dispersed. APS accumulates sorted probabilities until reaching the calibrated threshold, ensuring non-empty prediction sets whose size dynamically reflects input ambiguity.

Find the traffic the average hides

The four-row result measures overall empirical coverage. Breaking that count down by request type asks a different question: who receives the misses?

That guarantee isn't conditional coverage for every subgroup or individual feature value. Consider a constructed evaluation report with 750 short and 250 long requests. Short requests have 96% coverage; long requests have only 54%. The weighted average still exceeds 80%:

$$\frac{750(0.96) + 250(0.54)}{1000} = 0.855$$

These are hypothetical counts, not results from the four-request test above. They expose what an aggregate metric can hide. If the mix shifted to half short and half long while those subgroup rates stayed the same, overall coverage would fall to 0.5 * 0.96 + 0.5 * 0.54 = 75%. The old population guarantee wouldn't transfer automatically to that new mix.^{[2]Reference 2Conformal Prediction Beyond Exchangeabilityhttps://arxiv.org/abs/2202.13415}

An 80% conformal target passes across all traffic, but long requests are covered only 54% of the time. Does the population-wide guarantee refute the long-request measurement?

Answer

No. Standard split conformal guarantees marginal coverage across the exchangeable population, not equal conditional coverage for every prompt-length subgroup. A common well-covered group can keep the aggregate above target while a smaller long-request group remains unsafe.

Different failures call for different repairs:

Constant width isn't the only option. Suppose a second trained model predicts error scales of 3 ms for a short request and 6 ms for a long one. If calibration of normalized errors yields a threshold of 2, their interval radii become 2 * 3 = 6 ms and 2 * 6 = 12 ms. That threshold needs its own calibration; it isn't the 8 ms threshold from the raw-error example.

In symbols, learn a positive error scale $a(x)$ using training data, then calibrate scores $|y - \widehat f(x)| / a(x)$. The interval becomes $\widehat f(x) \pm q\,a(x)$. Both models must be frozen before calibration; this changes how width adapts, not the marginal guarantee into exact conditional coverage.^{[3]Reference 3Distribution-Free Predictive Inference for Regressionhttps://www.stat.cmu.edu/~ryantibs/papers/conformal.pdf}

Conformal risk control for language model triage routing

Modern language model systems often require bounds on general losses rather than simple interval coverage. In conformal risk control, the objective expands from set containment to bounding the expected value of any bounded loss function $\ell(C(X), Y) \in [0, 1]$:^{[1]Reference 1A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantificationhttps://arxiv.org/abs/2107.07511}

$$\mathbb{E}\left[\ell\left(C_\lambda(X), Y\right)\right] \leq \alpha$$

Here $\lambda$ represents a tunable parameter (such as an uncertainty cutoff or threshold). In production language model pipelines, two triage workflows build on this mechanism:

1. Hallucination filtering and human escalation: An evaluator or verifier scores each generated answer with an uncertainty metric $u(x)$ (such as token entropy, consistency variance across sampled rollouts, or an external critic score). By calibrating threshold $\lambda$, the pipeline routes requests with $u(x) > \lambda$ to human review or a fallback search pipeline, guaranteeing that accepted answers maintain an error rate below $\alpha$.
2. Selective intent routing: For tool-calling or API agents, classification prediction sets determine autonomy. If the prediction set contains exactly one intent ($|C(X)| = 1$), the system executes the tool call automatically. If $|C(X)| > 1$, the query triggers a clarification prompt or routes to human support.

How does conformal triage routing turn set size into an operational decision for an autonomous agent?

Answer

When the calibrated prediction set contains a single candidate action, the agent executes autonomously. When uncertainty expands the set to multiple candidates or an empty set, the agent halts and routes the request to human review or asks the user for clarification.

Check the decision, not just the percentage

A coverage number without interval width is incomplete. An interval spanning the entire outcome space never misses, but it can't guide a 50-millisecond deadline.

Return to the deadline question. [32, 48] sits below 50 ms, but the 80% marginal guarantee doesn't mean this request has an 80% conditional chance of meeting its deadline. Selecting only requests with upper endpoints below 50 also creates a subgroup; ordinary marginal validity alone doesn't certify that selected group's failure rate.

For monitoring, retain the model and calibration versions, each interval, actual outcome, request group, and width. Inspect counts as well as percentages. A scorecard with two long requests can't establish a reliable long-request rate, and no finite log proves that future traffic will stay exchangeable.

Try these changes to the cells before checking the expected result: