# On the Depth between Beam Search and Exhaustive Search for Text Generation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 48 references that are in the map.
- First posted on arXiv 25 Aug 2023.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [A Call for Clarity in Reporting BLEU Scores](https://mlsanity.com/paper/1804.08771/) (2018)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization](https://mlsanity.com/paper/1808.08745/) (2018)
- [Teaching Machines to Read and Comprehend](https://mlsanity.com/paper/1506.03340/) (2015)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [A Neural Attention Model for Abstractive Sentence Summarization](https://mlsanity.com/paper/1509.00685/) (2015)
- [Six Challenges for Neural Machine Translation](https://mlsanity.com/paper/1706.03872/) (2017)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Is ChatGPT A Good Translator? Yes With GPT-4 As The Engine](https://mlsanity.com/paper/2301.08745/) (2023)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [Correcting Length Bias in Neural Machine Translation](https://mlsanity.com/paper/1808.10006/) (2018)
- [If beam search is the answer, what was the question?](https://mlsanity.com/paper/2010.02650/) (2020)
- [On NMT Search Errors and Model Errors: Cat Got Your Tongue?](https://mlsanity.com/paper/1908.10090/) (2019)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling](https://mlsanity.com/paper/1811.10996/) (2018)
- [Revisiting the Uniform Information Density Hypothesis](https://mlsanity.com/paper/2109.11635/) (2021)
- [Machine Translation Decoding beyond Beam Search](https://mlsanity.com/paper/2104.05336/) (2021)
- [Consistency of a Recurrent Language Model With Respect to Incomplete Decoding](https://mlsanity.com/paper/2002.02492/) (2020)
- [Best-First Beam Search](https://mlsanity.com/paper/2007.03909/) (2020)
- [Joey NMT: A Minimalist NMT Toolkit for Novices](https://mlsanity.com/paper/1907.12484/) (2019)
- [Faithfulness-Aware Decoding Strategies for Abstractive Summarization](https://mlsanity.com/paper/2303.03278/) (2023)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [Breaking the Beam Search Curse: A Study of (Re-)Scoring Methods and Stopping Criteria for Neural Machine Translation](https://mlsanity.com/paper/1808.09582/) (2018)
- [Don't Say What You Don't Know: Improving the Consistency of Abstractive Summarization by Constraining Beam Search](https://mlsanity.com/paper/2203.08436/) (2022)
- [Incremental Beam Manipulation for Natural Language Generation](https://mlsanity.com/paper/2102.02574/) (2021)
- [SGNMT -- A Flexible NMT Decoding Platform for Quick Prototyping of New Models and Search Strategies](https://mlsanity.com/paper/1707.06885/) (2017)

## Built on by (most cited first, 2 of 2)

- [The Sound of Healthcare: Improving Medical Transcription ASR Accuracy with Large Language Models](https://mlsanity.com/paper/2402.07658/) (2024)
- [Don't Rank, Combine! Combining Machine Translation Hypotheses Using Quality Estimation](https://mlsanity.com/paper/2401.06688/) (2024)

## Abstract (arXiv)

Beam search and exhaustive search are two extreme ends of text decoding algorithms with respect to the search depth. Beam search is limited in both search width and depth, whereas exhaustive search is a global search that has no such limitations. Surprisingly, beam search is not only computationally cheaper but also performs better than exhaustive search despite its higher search error. Plenty of research has investigated a range of beam widths, from small to large, and reported that a beam width that is neither too large nor too small is desirable. However, in terms of search depth, only the two extreme ends, beam search and exhaustive search are studied intensively. In this paper, we examine a range of search depths between the two extremes to discover the desirable search depth. To this end, we introduce Lookahead Beam Search (LBS), a multi-step lookahead search that optimizes the objective considering a fixed number of future steps. Beam search and exhaustive search are special cases of LBS where the lookahead depth is set to 0 and ∞, respectively. We empirically evaluate the performance of LBS and find that it outperforms beam search overall on machine translation tasks. The result suggests there is room for improvement in beam search by searching deeper. Inspired by the analysis, we propose Lookbehind Heuristic Beam Search, a computationally feasible search algorithm that heuristically simulates LBS with 1-step lookahead. The empirical results show that the proposed method outperforms vanilla beam search on machine translation and text summarization tasks.