Before revision:  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.
After revision:  specifically, when the scoring function is a monotonic function in 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 , 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.