Best-First Beam Search

By Clara Meister, Ryan Cotterell, Tim Vieira. 2020

89 citations recorded by the source corpus.

Abstract Decoding for many NLP tasks requires an effective heuristic algorithm for approximating exact search because 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.

Subfields: Prompting & Reasoning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Prompting & Reasoning

Citations in the corpus

OPT: Open Pre-trained Transformer Language Models (2022, methodology): “Future work may wish to incorporate more modern strategies for reducing repetition and improving diversity, such as unlikelihood training (Welleck et al., 2020) or best-first decoding (Meister et al., 2020).”
NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics (2021, methodology): “For many such problems, A* search has been used effectively (Och et al., 2001; Haghighi et al., 2007; Hopkins and Langmead, 2009; Meister et al., 2020).”
PlaTe: Visually-Grounded Planning With Transformers in Procedural Tasks (2021, background): “(4) The discrepancy gap is the difference in log-probability between the most likely token and the chosen token [27], [28].”
Decomposition Enhances Reasoning via Self-Evaluation Guided Decoding (2023, unknown): “Deterministic decoding methods such as greedy decoding and beam search (Jurafsky and Martin, 2009; Graves, 2012) often produce high-quality results but lack diversity (Stahlberg and Byrne, 2019; Meister et al., 2020).”
If Beam Search Is the Answer, What Was the Question? (2020, background): “10https://github.com/pytorch/fairseq/ tree/master/examples/translation cally increasing, which is the case for hypotheses under the scoring scheme used by neural probabilistic text generators (see Meister et al. (2020) for more detailed discussion).”