Beam search and exhaustive search are two extreme ends of text decoding
algorithms with respect to the search depth. Beam search is limited in both
search width and depth, whereas exhaustive search is a global search that has
no such limitations. Surprisingly, beam search is not only computationally
cheaper but also performs better than exhaustive search despite its higher
search error. Plenty of research has investigated a range of beam widths, from
small to large, and reported that a beam width that is neither too large nor
too small is desirable. However, in terms of search depth, only the two extreme
ends, beam search and exhaustive search are studied intensively. In this paper,
we examine a range of search depths between the two extremes to discover the
desirable search depth. To this end, we introduce Lookahead Beam Search (LBS),
a multi-step lookahead search that optimizes the objective considering a fixed
number of future steps. Beam search and exhaustive search are special cases of
LBS where the lookahead depth is set to $0$ and $\infty$, respectively. We
empirically evaluate the performance of LBS and find that it outperforms beam
search overall on machine translation tasks. The result suggests there is room
for improvement in beam search by searching deeper. Inspired by the analysis,
we propose Lookbehind Heuristic Beam Search, a computationally feasible search
algorithm that heuristically simulates LBS with 1-step lookahead. The empirical
results show that the proposed method outperforms vanilla beam search on
machine translation and text summarization tasks.

本文研究了文本解码算法中搜索深度的两个极端，束搜索和穷举搜索，并介绍了 Lookahead Beam Search (LBS) 作为二者的优化方法。实验证明，LBS 在机器翻译任务中表现优于束搜索，启示我们可以通过更深入的搜索提高束搜索的性能。受此分析启发，我们提出了一种计算可行的搜索算法，Lookbehind Heuristic Beam Search，并在机器翻译和文本摘要任务上展示了其超越束搜索的效果。