Best-First Beam Search

Best-First Beam Search Clara Meister⋆ Tim Vieira� Ryan Cotterell∗, ⋆ ⋆ETH Z¨urich �Johns Hopkins University ∗University of Cambridge clara.meister@inf.ethz.ch tim.vieira@gmail.com ryan.cotterell@inf.ethz.ch Abstract Decoding for many NLP tasks requires an ef- fective 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 algo- rithm for this job is beam search—a pruned version of breadth-first search. Quite surpris- ingly, 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 can- not be in the final set of hypotheses early on. We devise effective monotonic approxima- tions to popular nonmonontic scoring functions, including length normalization and mutual information decoding. Lastly, we propose a memory-reducedvariantofbest-firstbeamsearch, which has a similar beneficial search bias in terms of downstream performance, but runs in a fraction of the time. 1 Introduction Beam search is a common heuristic algorithm for decoding structured predictors (e.g., neural ma- chine translation models and transition-based parsers). Because of the widespread adoption of recurrent neural networks and other non-Markov models, traditional dynamic programming solu- tions, such as the Viterbi algorithm (Viterbi, 1967), are prohibitively inefficient; this makes beam search a common component of many state- of-the-art NLP systems. Despite offering no formal guarantee of finding the highest-scoring hypothesis under the model, beam search yields impressive performance on a variety of tasks— unexpectedly providing a beneficial search bias over exact search for many tasks (Stahlberg and Byrne, 2019). Within NLP, most research on beam search has focused on altering the log-probability scoring function to return improved results, for example, higher BLEU scores (Wu et al., 2016; Murray and Chiang, 2018; Shu and Nakayama, 2018; Yang et al., 2018) or a more diverse set of outputs (Vijayakumar et al., 2016). However, little work has been done to speed up beam search itself. Filling this gap, this paper focuses on reform- ulating beam search in order to make it faster. We propose best-first beam search, a priori- tized version of traditional beam search that is up to an order of magnitude faster in practice while still returning the same set of results. We add- itionally discuss an even faster heuristic version of our algorithm that further limits the number of candidate solutions, leading to a smaller memory footprint while still finding good solutions. Concretely, we offer a novel interpretation of beam search as an agenda-based algorithm where traditional beam search is recovered by utilizing a length-based prioritization scheme. We prove that a specific best-first prioritization scheme, as in classic A∗ search (Hart et al., 1968), allows for the elimination of paths that will necessarily fall off the beam; for many scoring functions, including standard log-probability scoring, we can still guarantee the same k …

Content truncated to 500 words