# Best-First Beam Search

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

## Key facts

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

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

- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [Mutual Information Alleviates Hallucinations in Abstractive Summarization](https://mlsanity.com/paper/2210.13210/) (2022)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Machine Translation Decoding beyond Beam Search](https://mlsanity.com/paper/2104.05336/) (2021)
- [DeAL: Decoding-time Alignment for Large Language Models](https://mlsanity.com/paper/2402.06147/) (2024)
- [Defending Against Backdoor Attacks in Natural Language Generation](https://mlsanity.com/paper/2106.01810/) (2021)
- [Faithfulness-Aware Decoding Strategies for Abstractive Summarization](https://mlsanity.com/paper/2303.03278/) (2023)
- [Why do Nearest Neighbor Language Models Work?](https://mlsanity.com/paper/2301.02828/) (2023)
- [CTC Alignments Improve Autoregressive Translation](https://mlsanity.com/paper/2210.05200/) (2022)
- [Searchable Hidden Intermediates for End-to-End Models of Decomposable Sequence Tasks](https://mlsanity.com/paper/2105.00573/) (2021)
- [Constructing Tree-based Index for Efficient and Effective Dense Retrieval](https://mlsanity.com/paper/2304.11943/) (2023)
- [Conditional Poisson Stochastic Beam Search](https://mlsanity.com/paper/2109.11034/) (2021)
- [FLAP: Flow-Adhering Planning with Constrained Decoding in LLMs](https://mlsanity.com/paper/2403.05766/) (2024)
- [A Call for Clarity in Beam Search: How It Works and When It Stops](https://mlsanity.com/paper/2204.05424/) (2022)
- [SentBS: Sentence-level Beam Search for Controllable Summarization](https://mlsanity.com/paper/2210.14502/) (2022)
- [CT-AGRG: Automated Abnormality-Guided Report Generation from 3D Chest CT Volumes](https://mlsanity.com/paper/2408.11965/) (2024)
- [Massive-scale Decoding for Text Generation using Lattices](https://mlsanity.com/paper/2112.07660/) (2021)
- [Mitigating Image Captioning Hallucinations in Vision-Language Models](https://mlsanity.com/paper/2505.03420/) (2025)
- [Best-k Search Algorithm for Neural Text Generation](https://mlsanity.com/paper/2211.11924/) (2022)
- [A Method to Automate the Discharge Summary Hospital Course for Neurology Patients](https://mlsanity.com/paper/2305.06416/) (2023)
- [Accented Speech Recognition With Accent-specific Codebooks](https://mlsanity.com/paper/2310.15970/) (2023)
- [Parameter Efficient Audio Captioning With Faithful Guidance Using Audio-text Shared Latent Representation](https://mlsanity.com/paper/2309.03340/) (2023)
- [Twist Decoding: Diverse Generators Guide Each Other](https://mlsanity.com/paper/2205.09273/) (2022)
- [Uncertainty-Guided Likelihood Tree Search](https://mlsanity.com/paper/2407.03951/) (2024)
- [WavefrontDiffusion: Dynamic Decoding Schedule for Improved Reasoning](https://mlsanity.com/paper/2511.19473/) (2025)
- [Searching for Search Errors in Neural Morphological Inflection](https://mlsanity.com/paper/2102.08424/) (2021)
- [On the Depth between Beam Search and Exhaustive Search for Text Generation](https://mlsanity.com/paper/2308.13696/) (2023)
- [A Framework for Real-time Safeguarding the Text Generation of Large Language Model](https://mlsanity.com/paper/2404.19048/) (2024)

## Abstract (arXiv)

Decoding for many NLP tasks requires an effective heuristic algorithm for approximating exact search since the problem of searching the full output space is often intractable, or impractical in many settings. The default algorithm for this job is beam search -- a pruned version of breadth-first search. Quite surprisingly, beam search often returns better results than exact inference due to beneficial search bias for NLP tasks. In this work, we show that the standard implementation of beam search can be made up to 10x faster in practice. Our method assumes that the scoring function is monotonic in the sequence length, which allows us to safely prune hypotheses that cannot be in the final set of hypotheses early on. We devise effective monotonic approximations to popular nonmonontic scoring functions, including length normalization and mutual information decoding. Lastly, we propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance, but runs in a fraction of the time.