Build Prediction Sets with Conformal Prediction

A classifier usually returns one label even when several labels are plausible. That is convenient for software interfaces, but it can hide uncertainty exactly where mistakes are expensive. A document router might be unsure between billing and account, yet an argmax still emits one of them.

Conformal prediction offers another interface: return a set of labels sized according to the evidence. Easy inputs can produce one label. Ambiguous inputs can produce several. Under specific assumptions, the procedure also gives a finite-sample coverage guarantee.

This article develops the idea from a small classifier example, shows how calibration creates the threshold, and explains the assumptions and trade-offs that matter in deployed AI systems.

Start with a set instead of one answer

Suppose a classifier assigns these probabilities to a support request:

billing     0.62
account     0.31
technical   0.07

A normal top-one decision returns:

billing

That output discards the fact that account still has substantial model support. A prediction-set interface can instead return:

{billing, account}

For a clearer request, the same system might return only:

{billing}

The goal is not to include every remotely possible label. A useful prediction set balances two properties:

• coverage: the true label should appear in the set at the requested long-run rate;
• efficiency: sets should stay small enough to be useful.

A set containing every label has excellent coverage but no discriminating value. Conformal prediction provides a disciplined way to choose a threshold rather than inventing one from intuition.

Calibration data turns scores into a threshold

The simplest split-conformal workflow uses three pieces:

training data    -> fit the classifier
calibration data -> choose a conformal threshold
test inputs      -> build prediction sets

The calibration examples must not be the same examples used to fit the model. Their role is to measure how model scores behave on fresh labeled cases drawn under the same conditions expected at evaluation time.

For classification, define a nonconformity score. Larger values mean that a candidate label looks less compatible with the input. A simple choice for a probabilistic classifier is:

s(x, y) = 1 - p(y | x)

If the model gives the true label probability 0.82, its nonconformity score is:

1 - 0.82 = 0.18

If the true label receives probability 0.25, the score is:

1 - 0.25 = 0.75

For every calibration example (x_i, y_i), compute the score of its true label. These scores form an empirical reference distribution.

Compute the finite-sample quantile carefully

Assume there are n calibration scores and the target miscoverage rate is alpha. A standard split-conformal threshold uses the order statistic at rank:

k = ceil((n + 1) * (1 - alpha))

Sort the calibration scores from smallest to largest and take the value at rank k, using one-based indexing. If k > n, no finite calibration order statistic can supply that target through this basic rule; using an infinite threshold, and therefore including every label, is the conservative fallback.

Consider nine calibration scores:

0.08, 0.11, 0.14, 0.18, 0.22, 0.27, 0.31, 0.39, 0.52

For target coverage 90%:

n = 9
alpha = 0.10
k = ceil((9 + 1) * 0.90)
  = 9

The threshold is therefore:

q = 0.52

The (n + 1) correction matters. Taking an ordinary empirical 90th percentile without the conformal finite-sample adjustment can produce a different threshold and lose the intended guarantee.

Small calibration sets also make coverage levels coarse. With only a few examples, the available order statistics limit how precisely a desired rate can be represented. More calibration data usually gives finer threshold resolution and a more stable estimate of score behavior.

Build a prediction set for a new input

For a new input x, score every candidate label and include labels whose nonconformity score does not exceed the threshold:

C(x) = {y : s(x, y) <= q}

With s(x, y) = 1 - p(y | x) and q = 0.52, inclusion is equivalent to:

p(y | x) >= 0.48

Suppose a new request has:

billing     0.55
account     0.40
technical   0.05

Its nonconformity scores are:

billing     0.45
account     0.60
technical   0.95

Only billing is included because only 0.45 <= 0.52.

For a different threshold, score function, or probability profile, the set can contain multiple labels. The important point is that the cutoff comes from held-out calibration scores rather than from treating a raw model probability as intrinsically calibrated confidence.

This simple score is useful for teaching, but it is not the only conformal classification score. Other score constructions can produce more efficient sets, especially in multiclass tasks where probability mass is spread across many labels.

The guarantee is about marginal coverage

The central split-conformal statement is easy to overstate.

Under exchangeability of the calibration examples and the future example, the procedure is designed so that the prediction set contains the future true label with probability at least 1 - alpha for the standard finite-sample construction. The upper side of the coverage bound depends on score ties and whether randomization is used.

For a target of 90%, this is a marginal coverage claim. It does not say that every subgroup, every label, every difficulty level, or every individual prediction receives 90% coverage.

Imagine two traffic segments:

common requests: 95% coverage
rare requests:   60% coverage

Their aggregate could still meet a 90% target if rare requests form a small enough share. The overall guarantee does not prevent that disparity.

This distinction has direct engineering consequences. If coverage for a particular language, customer tier, medical cohort, device type, or rare class matters, measure that slice explicitly. Some conformal variants target stronger or group-conditional properties, but those require additional structure and should not be inferred from ordinary marginal coverage.

Exchangeability is the key assumption

Conformal guarantees do not come from the classifier being correct or its probabilities being calibrated. They come from the rank behavior of nonconformity scores under an exchangeability assumption.

Informally, calibration and future examples must be comparable enough that their ordering can be treated symmetrically. Independent and identically distributed sampling is a common sufficient setting, though exchangeability is the more direct condition.

This assumption can fail in familiar production situations:

calibration: last year's support traffic
production:  new product launch traffic

If new request types change the score distribution, the old conformal threshold may no longer deliver the intended coverage.

Other risks include geographic shifts, sensor replacements, policy changes, class-prior changes, upstream retrieval changes, and model updates. A threshold calibrated for one model version should not be assumed valid after replacing that model.

Treat the model, score function, preprocessing, and calibration set as one versioned unit. If any component changes in a way that can alter scores, recalibration is the safe default.

Set size is an operational signal, not a guarantee of correctness

Prediction-set size often reacts to ambiguity. A clear case may produce one label while a difficult case produces three. That makes set size useful for routing decisions.

For example:

size 1 -> automatic route
size 2 -> apply a secondary rule
size 3+ -> request human review

This can be a practical interface, but set size should not be interpreted as a universal uncertainty scale. A singleton set can still be wrong. A large set can arise from a conservative threshold, weak model separation, distribution shift, or a score function that is inefficient for the task.

Track both coverage and set-size statistics. Useful summaries include mean set size, the fraction of singleton sets, the fraction of empty sets when the construction permits them, and set size by important data slice.

Better base models can make sets smaller

Conformal prediction wraps a base model; it does not repair poor representations or missing information.

Suppose two classifiers both receive a conformal wrapper targeting the same marginal coverage. One sharply separates correct labels from alternatives. The other spreads probability broadly across classes. The first can often achieve the target with smaller sets because its score distribution distinguishes correct candidates more effectively.

This gives a useful separation of responsibilities:

base model quality -> how informative the scores are
conformal calibration -> how the threshold maps scores to coverage

Improving the base model can improve set efficiency while the conformal procedure controls the coverage target under its assumptions.

Do not compare conformal methods only by coverage if each is tuned to the same target. Compare set size and task-specific utility at that coverage level.

Avoid tuning on the calibration split

The calibration set has a narrow job: convert a fixed scoring procedure into a threshold. Repeatedly using it to choose model architecture, hyperparameters, score definitions, or business rules leaks selection decisions into the data intended for calibration.

A cleaner workflow is:

training split   -> fit parameters
validation split -> choose model and score design
calibration split -> compute final threshold
test split       -> estimate final behavior

Not every project needs four physical files, but the statistical roles should remain distinct. If data is scarce, resampling or cross-conformal approaches can use data more efficiently, at the cost of additional procedural complexity.

Also avoid reporting calibration-set coverage as evidence of deployed performance. The final evaluation should use untouched examples that represent the expected operating distribution.

Handle ties and implementation details deliberately

A conformal implementation needs an explicit rule for ties at the threshold. Using <= q rather than < q can affect finite-sample behavior when many scores are identical.

Discrete model outputs can create many ties. Quantized probabilities, rounded scores, and classifiers with repeated confidence values make this more likely. Randomized conformal procedures can handle ties more tightly in some settings, but deterministic conservative inclusion is often easier to operate when slightly larger sets are acceptable.

Numerical details matter too. If scores are computed from logits or probabilities, keep the same preprocessing and numerical path during calibration and serving. A calibration job using one normalization rule and production code using another is no longer applying the same score function.

Store enough metadata to reproduce the threshold:

model version
score definition
calibration dataset version
alpha
threshold
label vocabulary
preprocessing version

That record makes coverage regressions much easier to investigate.

Choose the coverage target from the decision cost

A target such as 90%, 95%, or 99% is not automatically appropriate. Higher target coverage usually requires more permissive prediction sets, which tends to increase set size.

The right trade-off depends on what happens after the set is produced. Missing the correct label in an automated medical triage workflow has a different cost from returning an extra category in an internal content-tagging tool.

Evaluate several target levels on held-out data:

target coverage | observed coverage | mean set size | downstream cost

Then choose a point that matches the application. If a downstream operator cannot act on sets containing ten labels, a nominally strong coverage target may create an unusable system.

A simpler top-one classifier can also be preferable when mistakes are cheap, users already tolerate corrections, and set-valued outputs add interface complexity without changing decisions.

Monitor coverage after deployment

Coverage can only be measured once true labels arrive. If production labels are delayed, establish a process for joining predictions with later outcomes and computing rolling metrics.

Monitor at least:

• empirical marginal coverage;
• set-size distribution;
• coverage for critical labels or slices;
• score distribution relative to the calibration distribution;
• the rate of inputs that trigger fallback handling.

A coverage drop is evidence that the deployed conditions no longer match the assumptions or that some pipeline component changed. Recalibration can fix threshold drift when the model remains suitable, but it cannot compensate for every form of severe distribution shift.

Keep operational monitoring separate from the formal guarantee. A dashboard does not create validity; it tells you whether observed behavior remains consistent with the conditions under which the method was calibrated.

Use conformal prediction as an interface contract

Conformal prediction is most useful when the application can act on a set rather than demanding one answer at any cost. The base model supplies relative evidence, the calibration set converts that evidence into a threshold, and the resulting prediction set exposes uncertainty in a form downstream software can use.

Start with a fixed classifier and a simple nonconformity score. Reserve fresh calibration data, compute the finite-sample threshold, and measure both coverage and set size on untouched test data. Then test the slices and distribution shifts that matter to the product.

The practical contract is precise: target coverage applies under the method’s assumptions, while set efficiency depends heavily on the base model and score design. Keeping those two ideas separate makes conformal prediction much easier to use responsibly.