Research map / Learning theory and algorithms / Prediction and decision losses
Conformal Autoregressive Generation: Beam Search with Coverage Guarantees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes two conformal extensions of beam search (post-hoc conformal subsets of beam results, and dynamic per-step conformal beams) that give marginal coverage guarantees for generated sequence sets, evaluated on T5 integer addition and chemical reaction product prediction.
Problem
Autoregressive sequence models lack coverage guarantees for the sets of sequences produced by beam search, since exhaustive conformal prediction over the combinatorial sequence space is intractable.
Approach
Combines split conformal prediction with beam search: (1) calibrates a threshold on beam-search results within the in-beam subgroup and pairs it with a Clopper-Pearson bound on beam coverage; (2) calibrates per-step thresholds via iterative tolerance-region pruning and uses them to set a dynamic beam size at each decoding step, giving a guarantee of (1-alpha)^L.
Key results
- On additions with dynamic conformal beams at per-step 0.99 (sequence guarantee 0.95), observed mean coverage is 0.9607 and the mean beam size is 10.4.
- On reactions at per-step 0.990 (sequence guarantee 0.605), observed coverage is 0.693 with mean beam size 4.13.
- Conformal beam subsets achieve global coverage of about 0.91 at 1-alpha=0.95 for additions (beam size 10) with a bound of 0.910, while the beam itself covers 0.979.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Raise the per-step confidence level from 0.950 to 0.990 | Dynamic conformal beam · Additions | coverage: 0.8231(6) -> 0.9607(3) | Helped |
| Raise the per-step confidence level from 0.950 to 0.990 | Dynamic conformal beam · Additions | mean beam size: 1.756(3) -> 10.4(4) | Hurt |
| Raise the per-step confidence level from 0.990 to 0.995 | Dynamic conformal beam · Reactions | coverage: 0.693(1) -> 0.806(1) | Helped |
| Raise the per-step confidence level from 0.990 to 0.995 | Dynamic conformal beam · Reactions | mean beam size: 4.13(1) -> 47.(5) | Hurt |
Surprising findings
- For the reaction task at per-token level 0.995, a significant fraction of beams exceed 100 sequences, making the dynamic procedure computationally costly.
Limitations
- Dynamic procedure's per-step guarantee degrades exponentially with the number of decoding steps, requiring stringent per-step levels for long sequences.
- Dynamic beam sizes have no upper bound and can become very large for weak models or long sequences.
- Both methods rely on greedy/beam search for high-scoring sequences, which suits predictive tasks but not open-ended language modelling.
Experimental setup
Datasets: synthetic integer addition dataset (130k pairs) USPTO-MIT chemical reactions (479,035 reactions)
Benchmarks: integer addition (synthetic) USPTO-MIT reaction product prediction
Metrics: coverage guarantee bound beam size mean absolute error vs oracle set size beam size to oracle ratio
Baselines: fixed 5-sequence beam search fixed 10-sequence beam search
Builds on: split conformal prediction group-conditional conformal prediction Clopper-Pearson confidence interval multivariate tolerance regions
Closest papers by meaning
- Dynamic-Width Speculative Beam Decoding for LLM Inference (AAAI 2025 · similarity 0.86)
- Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering (ICLR 2025 · similarity 0.86)
- Online conformal prediction with decaying step sizes (ICML 2024 · similarity 0.86)
- Generative Conformal Prediction with Optimized Coverage Allocation (NeurIPS 2026 · similarity 0.86)
- MARS: Enabling Autoregressive Models Multi-Token Generation (NeurIPS 2026 · similarity 0.86)
- Conformal Language Modeling (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.