# CoVeR: Conformal Calibration for Versatile and Reliable Autoregressive Next-Token Prediction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 31 references that are in the map.
- First posted on arXiv 5 Sep 2025.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [Large Language Models Can Self-Improve](https://mlsanity.com/paper/2210.11610/) (2022)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [Conformal Language Modeling](https://mlsanity.com/paper/2306.10193/) (2023)
- [Calibrating Sequence likelihood Improves Conditional Language Generation](https://mlsanity.com/paper/2210.00045/) (2022)
- [Class-Conditional Conformal Prediction with Many Classes](https://mlsanity.com/paper/2306.09335/) (2023)
- [A Survey of Reasoning with Foundation Models](https://mlsanity.com/paper/2312.11562/) (2023)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [Large Language Models Pass the Turing Test](https://mlsanity.com/paper/2503.23674/) (2025)
- [Conformal Nucleus Sampling](https://mlsanity.com/paper/2305.02633/) (2023)
- [Say What You Mean! Large Language Models Speak Too Positively about Negative Commonsense Knowledge](https://mlsanity.com/paper/2305.05976/) (2023)
- [RICA: Evaluating Robust Inference Capabilities Based on Commonsense Axioms](https://mlsanity.com/paper/2005.00782/) (2020)
- [Deductive Beam Search: Decoding Deducible Rationale for Chain-of-Thought Reasoning](https://mlsanity.com/paper/2401.17686/) (2024)
- [Probabilistic Conformal Prediction with Approximate Conditional Validity](https://mlsanity.com/paper/2407.01794/) (2024)
- [Relating Neural Text Degeneration to Exposure Bias](https://mlsanity.com/paper/2109.08705/) (2021)
- [Conformal Autoregressive Generation: Beam Search with Coverage Guarantees](https://mlsanity.com/paper/2309.03797/) (2023)
- [Improved Beam Search for Hallucination Mitigation in Abstractive Summarization](https://mlsanity.com/paper/2212.02712/) (2022)
- [Efficient Beam Search for Large Language Models Using Trie-Based Decoding](https://mlsanity.com/paper/2502.00085/) (2025)
- [UnCommonSense: Informative Negative Knowledge about Everyday Concepts](https://mlsanity.com/paper/2208.09292/) (2022)
- [Less Likely Brainstorming: Using Language Models to Generate Alternative Hypotheses](https://mlsanity.com/paper/2305.19339/) (2023)
- [Language-Informed Beam Search Decoding for Multilingual Machine Translation](https://mlsanity.com/paper/2408.05738/) (2024)

## Abstract (arXiv)

Autoregressive pre-trained models combined with decoding methods have achieved impressive performance on complex reasoning tasks. While mainstream decoding strategies such as beam search can generate plausible candidate sets, they often lack provable coverage guarantees, and struggle to effectively balance search efficiency with the need for versatile trajectories, particularly those involving long-tail sequences that are essential in certain real-world applications. To address these limitations, we propose textscCoVeR, a novel model-free decoding strategy wihtin the conformal prediction framework that simultaneously maintains a compact search space and ensures high coverage probability over desirable trajectories. Theoretically, we establish a PAC-style generalization bound, guaranteeing that textscCoVeR asymptotically achieves a coverage rate of at least 1 - α for any target level α ∈ (0,1).