Conformal Prediction for LLMs

"The model is 90% confident" is a claim about a softmax value, not about the world. Conformal prediction offers the other thing: a procedure that, given any black-box scorer and a held-out calibration set, returns prediction sets that contain the truth at least \(1-\alpha\) of the time, with no assumption about the model, the data distribution, or whether the scores were calibrated to begin with (Angelopoulos and Bates, 2021, A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification, arXiv:2107.07511; the framework is due to Vovk, Gammerman and Shafer, Algorithmic Learning in a Random World, Springer, 2005).

Split conformal in four steps

Pick a nonconformity score \(s(x, y)\) that is large when the label \(y\) looks wrong for input \(x\). For a classifier, \(s = 1 - \hat{p}(y \mid x)\) works.

1. Hold out \(n\) labelled calibration examples, disjoint from anything used in training or prompt selection.
2. Compute \(s_i = s(x_i, y_i)\) on all of them.
3. Set \(\hat{q}\) to the \(\lceil (n+1)(1-\alpha) \rceil / n\) empirical quantile of those scores. The small correction over the plain \(1-\alpha\) quantile is what makes the guarantee exact in finite samples.
4. For a new input, return every label whose score falls below the threshold: \(C(x) = \{y : s(x, y) \le \hat{q}\}\).

The theorem is that \(\mathbb{P}(Y_{\text{test}} \in C(X_{\text{test}})) \ge 1 - \alpha\), and it is also bounded above by \(1 - \alpha + 1/(n+1)\), provided calibration and test data are exchangeable. Nothing else is assumed. A badly calibrated model still gets valid coverage; it pays in set size.

Adapting it to generation

Open-ended text has no finite label set, so the construction has to be moved somewhere else.

For multiple choice, the label set is already finite and the standard recipe applies directly, producing sets of options with a coverage guarantee (Kumar et al., 2023, arXiv:2305.18404).

For free-form generation, Conformal Language Modeling calibrates a stopping rule for how many samples to draw into a candidate set, together with a rejection rule that removes low-quality candidates, and proves the returned set contains at least one acceptable answer with high probability while staying small in practice (Quach et al., ICLR 2024, arXiv:2306.10193).

The most useful reframing drops sets entirely. Conformal factuality treats an answer as a set of claims and calibrates how far to back off: when uncertainty is high the system returns a less specific statement rather than a longer list, giving high-probability correctness guarantees while retaining the majority of the original output on FActScore, NaturalQuestions and MATH (Mohri and Hashimoto, 2024, Language Models with Conformal Factuality Guarantees, arXiv:2402.10978).

When it breaks

• The guarantee is marginal, not conditional. Coverage holds on average over the whole distribution. It says nothing about coverage for a particular subgroup, and a system can hit 90% overall while covering 99% of easy queries and 40% of hard ones. Group-conditional variants exist and cost calibration data per group.
• Exchangeability is the entire assumption, and deployment violates it. Traffic drifts, the model gets updated, and users adapt to the system. Coverage degrades silently, because nothing in the procedure detects it. Online adaptive schemes adjust \(\alpha\) from observed error rates and recover long-run coverage without exchangeability (Gibbs and Candès, 2021, arXiv:2106.00170).
• Valid does not mean useful. A set containing every option is 100% covering and worth nothing. Efficiency, meaning average set size, is the real quality metric, and it is entirely driven by how good the underlying score is.
• Calibration data is expensive. Getting a tight quantile needs hundreds of labelled examples at \(\alpha = 0.1\), and more in the tail. Reusing evaluation data that also guided prompt selection breaks exchangeability and invalidates the guarantee.
• Scores from generation are awkward. Sequence log-probability is length-biased, and self-reported confidence is not a score with stable ordering. The choice of nonconformity score is where the engineering effort actually goes.