Abstract
Autoregressive models, while powerful, often lack statistical reliability, frequently producing "confident but wrong" outputs. This paper introduces two novel methods that integrate Conformal Prediction (CP) into beam search to provide rigorous coverage guarantees. These methods ensure that the generated set of sequences contains the correct answer with a user-defined probability. We evaluate these approaches on tasks ranging from integer addition to chemical reaction prediction, demonstrating that empirical coverage consistently aligns with theoretical targets.
Introduction
Autoregressive models are the backbone of modern AI, excelling in text generation, code synthesis, and scientific discovery. However, standard decoding algorithms like beam search provide no statistical assurance that the correct answer is among the top candidates. Quantifying uncertainty in these models is difficult due to the combinatorially massive space of possible sequences. Traditional Conformal Prediction—a framework for creating prediction sets with rigorous error control—typically requires an exhaustive search of all possible outputs, which is computationally infeasible for long sequences. This research bridges that gap, bringing rigorous uncertainty quantification to greedy decoding processes.
Methods
The researchers propose two distinct algorithms to provide these guarantees:
- Conformal Beam Subsets: A "post-hoc" approach where a standard beam search is performed first. A calibration dataset is then used to determine a threshold, and only sequences meeting this threshold are retained. While simple, its maximum coverage is inherently limited by the quality of the initial beam search.
- Dynamic Conformal Beam Search: A more sophisticated, adaptive approach. Instead of a fixed beam width, the algorithm calculates a CP threshold at every token step. The beam expands when the model is uncertain and shrinks when it is certain, providing an a-priori coverage guarantee for the entire sequence.
Mathematically, these methods treat sequence generation as a multivariate tolerance region, updating classical statistical concepts for modern deep learning architectures.
Experimental Evaluation
The methods were evaluated on two generative tasks with single ground-truth answers:
- Integer Additions: A T5-base model trained to add 7-digit numbers, representing a high-accuracy, short-sequence scenario.
- Chemical Reaction Product Prediction: A T5-small model trained on the USPTO MIT dataset to predict SMILES strings, representing a challenging, long-sequence scenario.
Results and Discussion
Experiments confirmed that empirical coverage consistently met or exceeded the theoretical guarantee ($1-\alpha$). For instance, in the Additions task with a 95% guarantee, the model achieved approximately 96% coverage.
As shown in the calibration plots, the beam size scales naturally with the difficulty of the task and the desired coverage level. In the dynamic approach, the beam size at any given step serves as a direct, interpretable measure of the model's uncertainty. If the beam size for a 95% coverage target suddenly spikes, it indicates the model has entered a high-uncertainty state.
Dynamic beam search proved more adaptive than the subset method. Even on the difficult chemical prediction task, where standard beam search (size 5) only captured the correct answer 64% of the time, the Dynamic Conformal Beam could be tuned to reach significantly higher coverage levels, albeit with larger beam sizes.
Limitations and Future Work
Despite their strengths, these methods have limitations. The dynamic guarantee depends on the maximum sequence length, which acts as a hyperparameter. Furthermore, for very difficult tasks, the dynamic beam can grow quite large (sometimes exceeding 100 sequences), increasing computational costs. Finally, because these methods are tied to greedy/beam search, they cannot "recover" a correct token if it was never explored. Future work may explore integrating these guarantees with sampling-based methods or reinforcement learning (RLHF) to improve performance in open-ended language modeling.
Summary updated