📄 Best-First Beam Search

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.