Technical Summary: When Can Conformal Risk Control Certify LLM Outputs?

1. Problem Statement

Large Language Models (LLMs) are increasingly deployed for structured generation tasks—such as Named Entity Recognition (NER), JSON extraction, Question Answering (QA), and classification—where outputs must adhere to a specific schema and can be evaluated against ground truth. However, these models lack formal reliability guarantees. Standard uncertainty quantification methods (e.g., token probabilities, entropy thresholds) are often miscalibrated for structured losses, and heuristic abstention policies frequently miss user-specified risk targets by 7.5–12.5%.

The core problem addressed is determining when Conformal Risk Control (CRC) can formally certify that an LLM's structured outputs meet a user-defined risk target $\alpha$ (e.g., "error rate $\le 10\%$"), and when such certification is provably impossible regardless of the method used.

2. Methodology

2.1. Problem Setup

The authors define a selective predictor that emits a prediction $\hat{y}$ if a confidence score $s(x, \hat{y}) \ge \lambda$ and abstains otherwise. The goal is to find a threshold $\lambda^*$ such that the conditional risk satisfies:
$$E[R_{task}(\hat{Y}, Y) \mid s(X) \ge \lambda^*] \le \alpha$$
with probability $\ge 1-\delta$, where $R_{task}$ is a task-specific risk (e.g., $1 - F_1$ for NER, $1 - \text{Exact Match}$ for QA).

2.2. Certification Hierarchy

The paper analyzes a hierarchy of bounds used to select $\lambda^*$:

1. Hoeffding Bound: The standard upper confidence bound (UCB) which ignores variance.
2. Empirical Bernstein Bound: Incorporates sample variance $\hat{\sigma}^2$, providing tighter bounds when variance is low ($\hat{\sigma}^2 < 1/4$).
3. e-CRC (Betting-Based): Uses a testing-by-betting framework (e-values) to construct a wealth process. This adapts fully to the empirical distribution via sequential bets, offering the tightest bound, particularly in data-scarce regimes.

The authors prove a strict ordering of certified thresholds: $\Lambda^*_{Hoeff} \subseteq \Lambda^*_{Bern} \subseteq \Lambda^*_{e-CRC}$.

2.3. Impossibility Result (Feasibility Test)

A central theoretical contribution is a closed-form lower bound on abstention. The authors prove that if the base risk $\mu = E[R]$ of the model on the deployment population exceeds the target $\alpha$, any distribution-free method must abstain on at least a fraction of examples:
$$\text{Abstention} \ge \frac{\mu - \alpha}{1 - \alpha}$$
This serves as a feasibility test: if $\mu > \alpha$, certification is only possible by rejecting a significant portion of inputs.

2.4. Adaptive Conformal Inference (ACI)

To address distribution shift (where the test distribution differs from the calibration set), the paper evaluates ACI. This method updates the threshold online based on observed risk:
$$\lambda_{t+1} = \lambda_t + \gamma(r_t - \alpha)$$
This provides asymptotic control under shift, though it does not offer finite-sample guarantees.

2.5. Score Fusion

The authors propose learning a fused confidence score $\tilde{s}(x)$ via logistic regression on disjoint calibration data, combining multiple signals (e.g., Self-Consistency, Token Margin, Semantic Entropy). They prove that if the fusion function is fixed and independent of the CRC calibration sample, the CRC validity guarantee is preserved.

3. Key Contributions

1. Impossibility Result and Feasibility Characterization: The paper establishes that when base risk $\mu > \alpha$, no distribution-free method can certify outputs without abstaining on $\ge (\mu - \alpha)/(1 - \alpha)$ of examples. This provides a pre-deployment check to determine if a risk target is achievable.
2. Certification Hierarchy: The authors establish and empirically verify the hierarchy $\Lambda^*_{Hoeff} \subseteq \Lambda^*_{Bern} \subseteq \Lambda^*_{e-CRC}$. They show that moving from Hoeffding to Bernstein yields the largest gain (+37% more certified configurations) in low-variance regimes, while e-CRC provides critical value when calibration data is scarce (e.g., 10% certification at 20% data vs. 0% for Hoeffding).
3. Adaptation to Shift: The study validates ACI under cross-dataset transfer, demonstrating a reduction in risk-target violations from 71% (static CRC) to 21%. Residual failures occur precisely where the impossibility bound predicts heavy abstention is required.
4. Empirical Benchmark: A comprehensive evaluation across six open-weight models (3B–72B parameters), eight datasets, four tasks, and six nonconformity scores. The study finds that hard NER/QA/CLS configurations are often uncertifiable at strict $\alpha=0.10$, but relaxing $\alpha$ to 0.30–0.40 unlocks practical certification (47% NER, 40% QA, 60% CLS).

4. Results

• Miscalibration: LLMs exhibit significant miscalibration for structured tasks. While average confidence is high (74–97%), actual risk ranges widely (3% for JSON to 80% for NQ Open QA).
• Feasibility Limits: At $\alpha=0.10$, certification rates for NER/QA/CLS are near-zero because $\mu \gg \alpha$. For example, NQ Open QA has $\mu \approx 0.80$, requiring $\ge 78\%$ abstention to meet a 10% risk target.
• Bound Performance:
  • Hoeffding: Certifies 8.7% of configurations.
  • Bernstein: Certifies 11.9% (+37% gain over Hoeffding).
  • e-CRC: Certifies 12.2%, with the most significant advantage in low-data regimes.
  • All methods maintain near-zero violation rates among certified configurations.
• Model Scaling: Increasing model size reduces base risk $\mu$. For CoNLL NER, $\mu$ drops from 0.42 (3B) to 0.24 (72B), enabling certification at $\alpha=0.25$ for 72B models where 14B models fail.
• Score Fusion: Calibrated fusion improves AUROC in 89% of configurations, with the largest gains in classification and NER tasks where individual scores are weaker.

5. Significance and Claims

The paper claims to provide a deployment-facing characterization rather than just a new conformal primitive. Its primary significance lies in shifting the practitioner's question from "Which bound is tightest?" to "Is certification feasible?"

• Feasibility First: The impossibility bound allows practitioners to compute the minimum required abstention before running any CRC procedure. If the required abstention is unacceptable, the paper suggests scaling the model, relaxing the risk target $\alpha$, or accepting heavy abstention.
• Practical Recipe: The authors propose a three-step deployment framework:
  1. Check Feasibility: Compute $\mu$; if $\mu > \alpha$, calculate the abstention floor.
  2. Select Bound and Score: Use Bernstein or e-CRC (never Hoeffding) and employ score fusion or Self-Consistency.
  3. Mitigate Shift: Deploy ACI if the test distribution may differ from calibration.
• Realistic Expectations: The work clarifies that for difficult tasks (high $\mu$) and strict targets (low $\alpha$), certification is inherently limited by the model's base performance, not the statistical method. Relaxing $\alpha$ to realistic levels (e.g., 0.30–0.40) makes certification practical for many structured tasks.

The paper concludes that while CRC provides formal guarantees, its utility is bounded by the fundamental trade-off between base risk and the target risk, a constraint that no statistical bound can overcome.