Matchability-Aware Conformal Prediction for Open-Ended Language Model Generation

Ilia AziziarXiv 2026 · arXiv

TL;DR

CAELUM is a framework for building semantically calibrated prediction sets for Large Language Models (LLMs) by separating aleatoric uncertainty (ambiguity) from epistemic uncertainty (knowledge gaps). It introduces "matchability"—the probability that a model can even generate the correct answer—as a fundamental theoretical ceiling for reliability and uses a pre-generation classifier to significantly improve coverage guarantees in open-ended tasks.

What Problem Does This Paper Address?

While LLMs are increasingly used in critical settings, they often struggle to communicate how certain they are about an answer. Conformal Prediction (CP) is a popular statistical framework that provides "guaranteed" reliability: if you ask for 90% coverage, it gives you a prediction set that contains the true answer 90% of the time.

However, applying CP to open-ended text generation faces two major hurdles:

  1. Infinite Response Space: Unlike simple classification, the space of possible text responses is vast, and "correctness" is semantic rather than an exact string match.
  2. The Knowledge Gap: Standard CP assumes the true answer is always reachable. For LLMs, the correct answer might not even be in the model's sampled support (i.e., the model simply doesn't know it). If the model cannot generate the right answer, no amount of statistical thresholding can include it in a prediction set.

The authors identify matchability—the fraction of items where the reference answer actually appears in any sampled cluster—as the "hard ceiling" for LLM reliability.

Methods

The authors propose CAELUM (Calibrated Aleatoric-Epistemic Language Uncertainty Modeling), which follows a five-step pipeline:

  1. Clarification Ensembles: For a given query, the model generates $n$ "clarification" prompts. This helps capture aleatoric uncertainty (e.g., "What is the capital of South Africa?" is ambiguous because it has three valid capitals).
  2. Sampling & Semantic Clustering: The model samples $m$ responses for each clarification. These are grouped into semantic clusters (e.g., "Pretoria" and "The city of Pretoria" are the same cluster).
  3. Uncertainty Decomposition: Using kernel-based von Neumann entropy, CAELUM splits total uncertainty into two components:
  4. Aleatoric ($U_{ale}$): Disagreement between different clarifications.
  5. Epistemic ($U_{epi}$): Disagreement within a single clarification (a sign the model is guessing).
  6. Weighted Conformal Prediction: They use a novel weighting function $w_\lambda(x) = 1 + U_{ale}(x) + \lambda U_{epi}(x)$ to scale the conformal threshold. This allows the system to expand prediction sets more aggressively when the model shows signs of a knowledge gap.
  7. Matchability Stratification: They train a lightweight binary classifier to predict if a question is "matchable" based only on the question's features (like embeddings and length) before generation.
Figure 1: Method overview. Each top-panel column shows the same five steps. Disagreement between clarifications raises Uale, and disagreement within a clarification raises Uepi. The weight w sets the effective threshold η = min{ˆτw, 1} for selecting clusters in Equation (7). The third column’s reference answer is absent from sampled support, so expanding the set cannot include it. The lower panel shows the matchability bound. Main experiments use n = 5 and kernel entropy.

Datasets

The study evaluates 30 combinations of LLMs (ranging from 4B to 32B parameters, including Qwen3, Ministral, and Gemma) across six benchmarks:

  • Factual: TriviaQA, OpenNQ, SimpleQA, and PopQA.
  • Ambiguity: AmbigQA and AmbigInst (tasks specifically designed with multiple valid interpretations).

Key Insights and Ideas

  • The Matchability Ceiling: You cannot statistically guarantee 90% coverage if your model only generates the correct answer 60% of the time. This paper formalizes this "support limitation" as a theoretical bound on conformal prediction.
  • Pre-generation Triage: Remarkably, a simple classifier can often predict if an LLM is likely to fail before it even starts generating, just by looking at the question. This allows for safer routing—for example, sending "unmatchable" questions to a human or a retrieval system.
  • Epistemic vs. Aleatoric: Disagreement within a single clarification is a much stronger signal for a "knowledge gap" (hallucination) than disagreement across different clarifications, which usually signals legitimate ambiguity.
  • Universal Hardness: Matchability is somewhat universal. A classifier trained on one model's failures can predict another model's failures with high accuracy (mean transfer AUC of 0.78), suggesting that some questions are inherently difficult for current LLM architectures.

Key Results

  • Improved Reliability: In the "predicted-matchable" stratum, mean coverage reached 0.74, compared to 0.65 overall, significantly closing the gap toward the 0.90 target.
  • Hallucination Detection: The epistemic uncertainty signal ($U_{epi}$) outperformed standard total entropy for ranking support failures (hallucinations) by an average AUROC improvement of +0.014.
  • Efficiency: CAELUM achieved these coverage gains while maintaining or reducing the average size of the prediction sets compared to vanilla conformal methods.
Table 1: Main results with a target nominal 90% coverage rate (deterministic APS). Test matchability ˆπtest, the fraction of references matched to sampled clusters, and other test results are evaluated on the same held-out questions. Bold and underline designate the smallest and second-smallest displayed set sizes among methods with the highest test coverage in that row, including ties, and † marks sizes below that coverage. Equal/SE refers to numerically identical results from Equal-weight and SE-CP methods. SC proxy is a simple self-consistency heuristic. The fitted λ⋆(deterministic seed SD) does not by itself identify an uncertainty regime. Full comparison results are reported in Table 5.

Limitations and Future Work

  • Computational Cost: Generating 50 responses per query (5 clarifications × 10 samples) is expensive and slow for real-time applications.
  • Heuristic Matching: The "ground truth" for whether a model's answer matches a reference relies on heuristic tiers (substrings, ROUGE scores, embeddings), which can still produce false positives or negatives.
  • Persistent Gaps: Even with CAELUM, some datasets (like PopQA) remain well below nominal coverage targets, indicating deep knowledge gaps that statistical calibration alone cannot fix.
  • Future Directions: The authors suggest extending this work to long-form generation, multi-turn dialogues, and multimodal settings where uncertainty might be spread across different media (e.g., text vs. images).

Summary updated

Abstract

Large language models (LLMs) often do not produce calibrated uncertainty estimates for their answers. We propose CAELUM, a framework that builds semantic prediction sets while separating aleatoric from epistemic uncertainty. CAELUM samples answers using an ensemble of clarification prompts, clusters them by semantic equivalence, and estimates the aleatoric and epistemic components via kernel-based von Neumann entropy before calibrating nonconformity scores with split conformal prediction. We use a weight $w_λ(x)=1+U_{\mathrm{ale}}(x)+λ\,U_{\mathrm{epi}}(x)$ to control for the contribution of the epistemic uncertainty of each instance and fit a coefficient $λ^\star$ to minimize prediction set size. When the objective is nonflat and selection is stable across splits, $λ^\star$ could be a diagnostic, where large values may indicate epistemic dominance (retrieve, abstain) and $λ^\star\to 0$ aleatoric dominance (clarify). For individual queries, a log ratio $R(x)$ compares the weighted epistemic component with the aleatoric component. Theoretically, we demonstrate that the coverage is capped by matchability, the fraction of items whose reference answer appears in any sampled cluster. Empirically, this matchability can be predicted from the original question features using a lightweight classifier. We use those predictions to define a stratum and derive a conformal coverage bound within it. Across 30 LLM and dataset combinations (4-32B), mean coverage is 0.74 in the learned stratum versus 0.65 overall, averaged over the 78 evaluations using the learned classifier. Project page: https://unco3892.github.io/caelum/
BibTeX
@misc{azizi2026matchability,
  author = {Ilia Azizi},
  title = {{Matchability-Aware Conformal Prediction for Open-Ended Language Model Generation}},
  year = {2026},
  eprint = {2611.10738},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.10738},
}
Figure