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，并在机器翻译和文本摘要任务上展示了其超越束搜索的效果。

关于文本生成中的束搜索与穷举搜索之间的深度

On the Depth between Beam Search and Exhaustive Search for Text  Generation

This paper is concerned with a class of algorithms that perform exhaustive
search on propositional knowledge bases. We show that each of these algorithms
defines and generates a propositional language. Specifically, we show that the
trace of a search can be interpreted as a combinational circuit, and a search
algorithm then defines a propositional language consisting of circuits that are
generated across all possible executions of the algorithm. In particular, we
show that several versions of exhaustive DPLL search correspond to such
well-known languages as FBDD, OBDD, and a precisely-defined subset of d-DNNF.
By thus mapping search algorithms to propositional languages, we provide a
uniform and practical framework in which successful search techniques can be
harnessed for compilation of knowledge into various languages of interest, and
a new methodology whereby the power and limitations of search algorithms can be
understood by looking up the tractability and succinctness of the corresponding
propositional languages.

本文提出了一种搜索算法与命题语言相结合的框架，有效地将知识归纳整理而成各种有用语言，通过对称式、迭代式等搜索方法的分析得出，能够相应的引出哥德尔公式、区间逻辑、一阶逻辑等语言。

搜索的语言

The Language of Search

A quantum computer has a clear advantage over a classical computer for
exhaustive search. The quantum mechanical algorithm for exhaustive search was
originally derived by using subtle properties of a particular quantum
mechanical operation called the Walsh-Hadamard (W-H) transform. This paper
shows that this algorithm can be implemented by replacing the W-H transform by
almost any quantum mechanical operation. This leads to several new applications
where it improves the number of steps by a square-root. It also broadens the
scope for implementation since it demonstrates quantum mechanical algorithms
that can readily adapt to available technology.

该研究论文阐述了实现量子计算机通过对有限种量子机械操作的创新运用，从而拓宽了现有技术的适用范围，进一步提高了量子计算机对穷举搜索的计算速度。