---
title: "Best-First Beam Search — paper by Meister et al. (2020)"
description: "The authors build monotonic approximations of length normalization and mutual-information decoding… 6 references, cited by 28 papers here."
authors: ["Clara Meister", "Tim Vieira", "Ryan Cotterell"]
year: 2020
venue: "Transactions of the Association for Computational Linguistics"
source: "https://aclanthology.org/2020.tacl-1.51/"
doi: "10.1162/tacl_a_00346"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/meister-2020-best-first-beam-search/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/meister-2020-best-first-beam-search/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2020](https://md.research.elamur.ai/free/en/papers/2020/page/7/) / Best-First Beam Search

# Best-First Beam Search

**Authors:** [Clara Meister](https://md.research.elamur.ai/free/en/authors/clara-meister/), [Tim Vieira](https://md.research.elamur.ai/free/en/authors/tim-vieira/) and [Ryan Cotterell](https://md.research.elamur.ai/free/en/authors/ryan-cotterell/) · **Year:** 2020 · **Venue:** [Transactions of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/tacl/) ([Transactions of the Association for Computational Linguistics (TACL) 2020](https://md.research.elamur.ai/free/en/venues/tacl/2020/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2020.tacl-1.51/) · [PDF](https://aclanthology.org/2020.tacl-1.51.pdf) · [DOI 10.1162/tacl\_a\_00346](https://doi.org/10.1162/tacl_a_00346) · [OpenAlex](https://openalex.org/W3041559793)

**Citations:** 0 citations (OpenAlex, 2026-10-14) · [28](https://md.research.elamur.ai/free/en/papers/meister-2020-best-first-beam-search/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Beam search is the standard approximate decoder for neural sequence models such as NMT systems, yet earlier work mostly changed its scoring function rather than its speed. Meister, Vieira and Cotterell recast decoding as a generic agenda-based procedure with configurable choice points: a priority comparator, a stopping rule, a per-length beam limit and a heuristic. Under this view, ordinary beam search is the special case that orders hypotheses by length. Ordering them by score instead gives best-first beam search. When the scoring function never increases as a sequence grows, as with standard log-probability, this method returns exactly the hypotheses that classic beam search would. It can also halt as soon as it pops its first finished hypothesis, skipping work on paths that could never stay in the beam. The authors build monotonic approximations of length normalization and mutual-information decoding, and they add a variant that caps queue memory. Experiments cover machine translation and abstractive summarization. The approach makes a ubiquitous decoder cheaper without changing its outputs.

## Key points
- Best-first beam search saves about 30% over standard beam search at typical beam widths, and roughly 10x at a beam of 500. Abstractive summarization shows similar trends.
- One meta-algorithm recovers greedy search, beam search, best-first (Dijkstra) search and A* by changing a few settings. Exactness relies on the scoring function being monotonic in sequence length.
- Evaluation used IWSLT'14 De-En, MTTT Fr-En and WMT'17 De-En, measured with BLEU, search error and the number of calls to the scoring function.
- The memory-reduced version limits the queue to k·γ entries. On IWSLT'14 with beam 10 it decodes more than 3x faster with no BLEU loss, and search error stays low at γ = 5.
- Heuristic variants for length normalization and mutual information produce many search errors relative to beam search. Their BLEU nevertheless stays comparable to or slightly above the baseline.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Johns Hopkins University](https://md.research.elamur.ai/free/en/universities/johns-hopkins-university/) — University, Baltimore, United States · 247 works · 106,235 citations
- [University of Cambridge](https://md.research.elamur.ai/free/en/universities/university-of-cambridge/) — University, Cambridge, United Kingdom · 256 works · 123,373 citations
- [ETH Zurich](https://md.research.elamur.ai/free/en/universities/eth-zurich/) — University, Zurich, Switzerland · 84 works · 9,181 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works

## Cite

Cite as: Clara Meister, Tim Vieira and Ryan Cotterell. 2020. Best-First Beam Search. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@article{meister2020best,
  title = {{Best-First Beam Search}},
  author = {Clara Meister, Tim Vieira and Ryan Cotterell},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2020},
  doi = {10.1162/tacl\_a\_00346},
  url = {https://doi.org/10.1162/tacl_a_00346}
}
```

- [← previous A Multitask Learning Approach for Diacritic Restoration](https://md.research.elamur.ai/free/en/papers/alqahtani-2020-multitask-learning-approach-diacritic-restoration/)
- [next → HypoNLI: Exploring the Artificial Patterns of Hypothesis-only Bias in Natural Language Inference](https://md.research.elamur.ai/free/en/papers/liu-2020-hyponli-exploring-artificial-patterns-hypothesis/)
- [↑ back to papers of 2020](https://md.research.elamur.ai/free/en/papers/2020/page/7/)

## References

6 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. M. D. Atkinson, J. R. Sack, N. Santoro, and T. Strothotte, 1986. Min-max heaps and generalized priority queues. Communications of ACM: 29(10). DOI: https://doi.org/10.1145/6617.6621 [↗](https://doi.org/10.1145/6617.6621)
2. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. [Neural machine translation by jointly learning to align and translate](https://md.research.elamur.ai/free/en/papers/bahdanau-2014-neural-machine-translation-jointly-learning/). In Proceedings of the International Conference on Learning Representations.
3. Ondřej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Shujian Huang, Matthias Huck, Philipp Koehn, Qun Liu, Varvara Logacheva, Christof Monz, Matteo Negri, Matt Post, Raphael Rubino, Lucia Specia, and Marco Turchi. 2017. [Findings of the 2017 conference on machine transla…](https://md.research.elamur.ai/free/en/papers/bojar-2017-findings-2017-conference-machine-translation/)
4. Mauro Cettolo, Christian Girardi, and Marcello Federico. 2012. Wit 3 : Web inventory of transcribed and translated talks. In Proceedings of the Conference of the European Association for Machine Translation. [find](https://scholar.google.com/scholar?q=Mauro+Cettolo%2C+Christian+Girardi%2C+and+Marcello+Federico%2E+2012%2E+Wit+3+%3A+Web+inventory+of+transcribed+and+translated+talks%2E+In+Proceedings+of+the+Conference+of+the+European+Association+for+Machine+Trans)
5. Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1(1). DOI: https://doi.org/10.1007/BF01386390 [↗](https://doi.org/10.1007/BF01386390)
6. Kevin Duh. 2018. The multitarget TED talks task. [http://www.cs.jhu.edu/∼kevinduh/a/multitarget-tedtalks/](http://www.cs.jhu.edu/∼kevinduh/a/multitarget-tedtalks/) \#\# Conclusion [↗](http://www.cs.jhu.edu/∼kevinduh/a/multitarget-tedtalks/)

*Updated 30 October 2026*