# If beam search is the answer, what was the question?

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

## Key facts

- Cited by 116 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2020.

## Built on by (most cited first, 30 of 116)

- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Offline Reinforcement Learning as One Big Sequence Modeling Problem](https://mlsanity.com/paper/2106.02039/) (2021)
- [Offline RL for Natural Language Generation with Implicit Language Q Learning](https://mlsanity.com/paper/2206.11871/) (2022)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Locally Typical Sampling](https://mlsanity.com/paper/2202.00666/) (2022)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [Lift Yourself Up: Retrieval-augmented Text Generation with Self Memory](https://mlsanity.com/paper/2305.02437/) (2023)
- [Sparks: Inspiration for Science Writing using Language Models](https://mlsanity.com/paper/2110.07640/) (2021)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [Revisiting the Uniform Information Density Hypothesis](https://mlsanity.com/paper/2109.11635/) (2021)
- [Grounded Decoding: Guiding Text Generation with Grounded Models for Embodied Agents](https://mlsanity.com/paper/2303.00855/) (2023)
- [Sampling-Based Approximations to Minimum Bayes Risk Decoding for Neural Machine Translation](https://mlsanity.com/paper/2108.04718/) (2021)
- [Uncertainty in Natural Language Generation: From Theory to Applications](https://mlsanity.com/paper/2307.15703/) (2023)
- [A Plug-and-Play Method for Controlled Text Generation](https://mlsanity.com/paper/2109.09707/) (2021)
- [Machine Translation Decoding beyond Beam Search](https://mlsanity.com/paper/2104.05336/) (2021)
- [The Curious Case of Hallucinatory (Un)answerability: Finding Truths in the Hidden States of Over-Confident Large Language Models](https://mlsanity.com/paper/2310.11877/) (2023)
- [LENS: A Learnable Evaluation Metric for Text Simplification](https://mlsanity.com/paper/2212.09739/) (2022)
- [Lower Perplexity is Not Always Human-Like](https://mlsanity.com/paper/2106.01229/) (2021)
- [Quality-Aware Decoding for Neural Machine Translation](https://mlsanity.com/paper/2205.00978/) (2022)
- [Large Language Models Hallucination: A Comprehensive Survey](https://mlsanity.com/paper/2510.06265/) (2025)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [GPT-who: An Information Density-based Machine-Generated Text Detector](https://mlsanity.com/paper/2310.06202/) (2023)
- [DoCoGen: Domain Counterfactual Generation for Low Resource Domain Adaptation](https://mlsanity.com/paper/2202.12350/) (2022)
- [Closing the Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/2310.01693/) (2023)
- [Faithfulness-Aware Decoding Strategies for Abstractive Summarization](https://mlsanity.com/paper/2303.03278/) (2023)
- [A Well-Composed Text is Half Done! Composition Sampling for Diverse Conditional Generation](https://mlsanity.com/paper/2203.15108/) (2022)
- [Why don't people use character-level machine translation?](https://mlsanity.com/paper/2110.08191/) (2021)
- [Detecting Subtle Differences between Human and Model Languages Using Spectrum of Relative Likelihood](https://mlsanity.com/paper/2406.19874/) (2024)
- [Determinantal Beam Search](https://mlsanity.com/paper/2106.07400/) (2021)
- [On the probability-quality paradox in language generation](https://mlsanity.com/paper/2203.17217/) (2022)

## Abstract (arXiv)

Quite surprisingly, exact maximum a posteriori (MAP) decoding of neural language generators frequently leads to low-quality results. Rather, most state-of-the-art results on language generation tasks are attained using beam search despite its overwhelmingly high search error rate. This implies that the MAP objective alone does not express the properties we desire in text, which merits the question: if beam search is the answer, what was the question? We frame beam search as the exact solution to a different decoding objective in order to gain insights into why high probability under a model alone may not indicate adequacy. We find that beam search enforces uniform information density in text, a property motivated by cognitive science. We suggest a set of decoding objectives that explicitly enforce this property and find that exact decoding with these objectives alleviates the problems encountered when decoding poorly calibrated language generation models. Additionally, we analyze the text produced using various decoding strategies and see that, in our neural machine translation experiments, the extent to which this property is adhered to strongly correlates with BLEU.