# When to Finish? Optimal Beam Search for Neural Text Generation (modulo beam size)

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2018.

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

- [Advances and Challenges in Conversational Recommender Systems: A Survey](https://mlsanity.com/paper/2101.09459/) (2021)
- [FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering](https://mlsanity.com/paper/2405.13873/) (2024)
- [A New Approach to Overgenerating and Scoring Abstractive Summaries](https://mlsanity.com/paper/2104.01726/) (2021)
- [A Call for Clarity in Beam Search: How It Works and When It Stops](https://mlsanity.com/paper/2204.05424/) (2022)
- [Massive-scale Decoding for Text Generation using Lattices](https://mlsanity.com/paper/2112.07660/) (2021)
- [TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code Generation](https://mlsanity.com/paper/2511.22277/) (2025)
- [Towards a Path Dependent Account of Category Fluency](https://mlsanity.com/paper/2405.06714/) (2024)
- [Discovering Hidden Algebraic Structures via Transformers with Rank-Aware Beam GRPO](https://mlsanity.com/paper/2508.15766/) (2025)
- [Designing RNAs with Language Models](https://mlsanity.com/paper/2602.12470/) (2026)
- [TreeRanker: Fast and Model-agnostic Ranking System for Code Suggestions in IDEs](https://mlsanity.com/paper/2508.02455/) (2025)

## Abstract (arXiv)

In neural text generation such as neural machine translation, summarization, and image captioning, beam search is widely used to improve the output text quality. However, in the neural generation setting, hypotheses can finish in different steps, which makes it difficult to decide when to end beam search to ensure optimality. We propose a provably optimal beam search algorithm that will always return the optimal-score complete hypothesis (modulo beam size), and finish as soon as the optimality is established (finishing no later than the baseline). To counter neural generation's tendency for shorter hypotheses, we also introduce a bounded length reward mechanism which allows a modified version of our beam search algorithm to remain optimal. Experiments on neural machine translation demonstrate that our principled beam search algorithm leads to improvement in BLEU score over previously proposed alternatives.