On the Depth between Beam Search and Exhaustive Search for Text
  Generation
Yuu Jinnai Tetsuro Morimura Ukyo Honda
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.