Beam search

Uses

A beam search is most often used to maintain tractability in large systems with insufficient amount of memory to store the entire search tree. For example, it has been used in many machine translation systems. (The state of the art now primarily uses neural machine translation based methods, especially large language models) To select the best translation, each part is processed, and many different ways of translating the words appear. The top best translations according to their sentence structures are kept, and the rest are discarded. The translator then evaluates the translations according to a given criterion, choosing the translation which best keeps the goals.

History

The Harpy Speech Recognition System (introduced in a 1976 dissertation) was the first use of what would become known as beam search. While the procedure was originally referred to as the "locus model of search", the term "beam search" was already in use by 1977.

Variants

Beam search has been made complete by combining it with depth-first search, resulting in beam stack search and depth-first beam search, and with limited discrepancy search, resulting in beam search using limited discrepancy backtracking (BULB). The resulting search algorithms are anytime algorithms that find good but likely sub-optimal solutions quickly, like beam search, then backtrack and continue to find improved solutions until convergence to an optimal solution.

In the context of a local search, we call local beam search a specific algorithm that begins selecting ${\displaystyle \beta }$ randomly generated states and then, for each level of the search tree, it always considers ${\displaystyle \beta }$ new states among all the possible successors of the current ones, until it reaches a goal.

Since local beam search often ends up on local maxima, a common solution is to choose the next ${\displaystyle \beta }$ states in a random way, with a probability dependent from the heuristic evaluation of the states. This kind of search is called stochastic beam search.

Other variants are flexible beam search and recovery beam search.