Decoding for many NLP tasks requires a heuristic algorithm for approximating exact search since the full search space is often intractable if not simply too large to traverse efficiently . The default algorithm for this job is beam search--a pruned version of breadth-first search--which in practice, returns better results than exact inference due to beneficial search bias  . In this work, we show that standard beam search is a computationally inefficient choice for many decoding tasks; specifically, when the scoring function is a monotonic function in sequence length, other search algorithms can be used to reduce the number of calls to the scoring function (e.g., a neural network), which is often the bottleneck computation. We propose best-first beam search, an algorithm that provably returns the same set of results as standard beam search, albeit in the minimum number of scoring function calls to guarantee optimality (modulo beam size). We show that best-first beam search can be used with length normalization and mutual information decoding , among other rescoring functions . Lastly, we propose a memory-reduced variant of best-first beam search , which has a similar  search bias in terms of downstream performance, but runs in a fraction of the time.
Decoding for many NLP tasks requires an effective heuristic algorithm for approximating exact search since 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.
R
a
an effective
R
full search
problem of searching the full output
R
if not simply too large to traverse efficiently
, or impractical in many settings
R
search--a
search -- a
R
search--which in practice,
search. Quite surprisingly, beam search often
A
for NLP tasks
R
standard beam search is a computationally inefficient choice for many decoding tasks; specifically, when
the standard implementation of beam search can be made up to 10x faster in practice. Our method assumes that
R
a monotonic function in
monotonic in the
R
other search algorithms can be used to reduce the number of calls to the scoring function (e.g., a neural network), which is often the bottleneck computation. We propose best-first beam search, an algorithm that provably returns the same set of results as standard beam search, albeit in the minimum number of scoring function calls to guarantee optimality (modulo beam size). We show that best-first beam search can be used with
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
D
, among other rescoring functions
R
best-first beam search
Best-First Beam Search
A
beneficial