# When Can Conformal Risk Control Certify LLM Outputs? Bounds, Impossibility, and Adaptation for Structured Generation

arXiv: https://arxiv.org/abs/2606.29054 · HTML: https://mlsanity.com/paper/2606.29054/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 56 references that are in the map.
- First posted on arXiv 27 Jun 2026.

## Builds on (most cited first, 30 of 41)

- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [SelectiveNet: A Deep Neural Network with an Integrated Reject Option](https://mlsanity.com/paper/1901.09192/) (2019)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Conformal Language Modeling](https://mlsanity.com/paper/2306.10193/) (2023)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [Few-NERD: A Few-Shot Named Entity Recognition Dataset](https://mlsanity.com/paper/2105.07464/) (2021)
- [Language Models with Conformal Factuality Guarantees](https://mlsanity.com/paper/2402.10978/) (2024)
- [Trust or Escalate: LLM Judges with Provable Guarantees for Human Agreement](https://mlsanity.com/paper/2407.18370/) (2024)
- [Safe Testing](https://mlsanity.com/paper/1906.07801/) (2019)
- [Large language model validity via enhanced conformal prediction methods](https://mlsanity.com/paper/2406.09714/) (2024)
- [Optimal strategies for reject option classifiers](https://mlsanity.com/paper/2101.12523/) (2021)
- [Mitigating LLM Hallucinations via Conformal Abstention](https://mlsanity.com/paper/2405.01563/) (2024)
- [Conformal Alignment: Knowing When to Trust Foundation Models with Guarantees](https://mlsanity.com/paper/2405.10301/) (2024)
- [Conformal Prediction for Natural Language Processing: A Survey](https://mlsanity.com/paper/2405.01976/) (2024)

## Built on by (most cited first, 4 of 4)

- [Non-Degenerate Risk Certification for Automated Security Decisions: A Decision-Contract Theory with ATT&CK-Aligned Triage as a Worked Instance](https://mlsanity.com/paper/2608.12444/) (2026)
- [The Exceedance Design Effect: Effective Sample Size for Thresholds under Clustering](https://mlsanity.com/paper/2608.21262/) (2026)
- [Uncertainty Quantification for LLM Agents: A Taxonomy, an Evaluation Protocol, and an Empirical Study](https://mlsanity.com/paper/2609.07395/) (2026)
- [Certified Against Which Oracle? Execution Labels Set the Reported Risk of Conformal Abstention for Text-to-SQL](https://mlsanity.com/paper/2609.25938/) (2026)

## Abstract (arXiv)

Large language models (LLMs) deployed for structured generation (NER, JSON extraction, QA, and classification) lack formal reliability guarantees, and standard heuristic abstention policies violate user-specified risk targets on 7.5--12.5% of settings, with no per-deployment guarantee. We characterize when conformal risk control (CRC) can certify structured LLM outputs and when it provably cannot. First, we prove a sharpened, attained feasibility frontier: when base risk μ exceeds target α, any distribution-free method must abstain on at least (μ-α)/(M-α) of inputs, yielding a closed-form feasibility test that decides whether CRC can work before running it. Second, we establish a proven certification phase diagram across Hoeffding, empirical Bernstein, and a betting-based e-CRC bound, verified over 716 configurations (six open-weight models 3B--72B, eight datasets, six scores): at strict targets (α <= 0.20) the certified sets are nested (51/72/80 certified; Hoeffding-to-Bernstein the largest upgrade, +41%; e-CRC best under calibration scarcity), while at relaxed targets the Hoeffding-Bernstein ordering reverses at a closed-form frontier. Third, we show a negative shift result with a constructive counterpart: under cross-dataset shift the target is violated on 14 of 16 transfers by static CRC and every tested adaptive-conformal-inference (ACI) step size, yet a full-feedback anytime-valid monitor certifies 0 of 16 while remaining non-vacuous. Relaxing the target to α = 0.40 unlocks practical certification (28% NER, 13% QA, 19% CLS). The framework gives a three-step deployment recipe: check feasibility, select the bound and score, then re-check under shift.