# Conformal Autoregressive Generation: Beam Search with Coverage Guarantees

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 45 references that are in the map.
- First posted on arXiv 7 Sep 2023.

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [How Can We Know When Language Models Know? On the Calibration of Language Models for Question Answering](https://mlsanity.com/paper/2012.00955/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Calibration of Pre-trained Transformers](https://mlsanity.com/paper/2003.07892/) (2020)
- [Confident Adaptive Language Modeling](https://mlsanity.com/paper/2207.07061/) (2022)
- [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models](https://mlsanity.com/paper/2305.19187/) (2023)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Molecular Transformer - A Model for Uncertainty-Calibrated Chemical Reaction Prediction](https://mlsanity.com/paper/1811.02633/) (2018)
- [Unsupervised Quality Estimation for Neural Machine Translation](https://mlsanity.com/paper/2005.10608/) (2020)
- [Reducing conversational agents' overconfidence through linguistic calibration](https://mlsanity.com/paper/2012.14983/) (2020)
- [Conformal Language Modeling](https://mlsanity.com/paper/2306.10193/) (2023)
- [Uncertainty Quantification with Pre-trained Language Models: A Large-Scale Empirical Analysis](https://mlsanity.com/paper/2210.04714/) (2022)
- [Predicting Organic Reaction Outcomes with Weisfeiler-Lehman Network](https://mlsanity.com/paper/1709.04555/) (2017)
- [Few-shot Conformal Prediction with Auxiliary Tasks](https://mlsanity.com/paper/2102.08898/) (2021)
- [Regression Transformer: Concurrent sequence regression and generation for molecular language modeling](https://mlsanity.com/paper/2202.01338/) (2022)
- [Uncertainty Estimation for Language Reward Models](https://mlsanity.com/paper/2203.07472/) (2022)
- [Conformal Nucleus Sampling](https://mlsanity.com/paper/2305.02633/) (2023)
- [Conformal prediction for text infilling and part-of-speech prediction](https://mlsanity.com/paper/2111.02592/) (2021)

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

- [Benchmarking LLMs via Uncertainty Quantification](https://mlsanity.com/paper/2401.12794/) (2024)
- [Multicalibration for Confidence Scoring in LLMs](https://mlsanity.com/paper/2404.04689/) (2024)
- [Do Not Design, Learn: A Trainable Scoring Function for Uncertainty Estimation in Generative LLMs](https://mlsanity.com/paper/2406.11278/) (2024)
- [Non-Exchangeable Conformal Language Generation with Nearest Neighbors](https://mlsanity.com/paper/2402.00707/) (2024)
- [Forking Uncertainties: Reliable Prediction and Model Predictive Control with Sequence Models via Conformal Risk Control](https://mlsanity.com/paper/2310.10299/) (2023)
- [Trustworthy Classification through Rank-Based Conformal Prediction Sets](https://mlsanity.com/paper/2407.04407/) (2024)
- [Prune 'n Predict: Optimizing LLM Decision-making with Conformal Prediction](https://mlsanity.com/paper/2501.00555/) (2024)
- [Knowing When to Abstain: Medical LLMs Under Clinical Uncertainty](https://mlsanity.com/paper/2601.12471/) (2026)
- [Certifying Counterfactual Bias in LLMs](https://mlsanity.com/paper/2405.18780/) (2024)
- [Statistical Methods in Generative AI](https://mlsanity.com/paper/2509.07054/) (2025)
- [Conditional Shift-Robust Conformal Prediction for Graph Neural Network](https://mlsanity.com/paper/2405.11968/) (2024)
- [Conformalized Large Language Models under Configuration Shift](https://mlsanity.com/paper/2608.01460/) (2026)
- [CoVeR: Conformal Calibration for Versatile and Reliable Autoregressive Next-Token Prediction](https://mlsanity.com/paper/2509.04733/) (2025)
- [PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Search](https://mlsanity.com/paper/2604.14345/) (2026)
- [Conformal Cascade: Distribution-Free Accuracy Guarantees for Multi-Tier LLM Inference](https://mlsanity.com/paper/2607.25018/) (2026)
- [The Exceedance Design Effect: Effective Sample Size for Thresholds under Clustering](https://mlsanity.com/paper/2608.21262/) (2026)

## Abstract (arXiv)

We introduce two new extensions to the beam search algorithm based on conformal predictions (CP) to produce sets of sequences with theoretical coverage guarantees. The first method is very simple and proposes dynamically-sized subsets of beam search results but, unlike typical CP procedures, has an upper bound on the achievable guarantee depending on a post-hoc calibration measure. Our second algorithm introduces the conformal set prediction procedure as part of the decoding process, producing a variable beam width which adapts to the current uncertainty. While more complex, this procedure can achieve coverage guarantees selected a priori. We provide marginal coverage bounds for each method, and evaluate them empirically on a selection of tasks drawing from natural language processing and chemistry.