Beam search

Beam search is a heuristic search algorithm that limits memory consumption by keeping only the best β candidate nodes at each depth level of the search tree. It is a disciplined approximation of best-first search: rather than maintaining the entire frontier, beam search aggressively prunes it, sacrificing completeness and optimality for tractability in exponentially large spaces. The beam width β is the central design parameter — a narrow beam runs fast but risks missing good solutions; a wide beam approaches the behavior of full best-first search at the cost of memory and time.

Beam search is the dominant search strategy in natural language processing and speech recognition, where the search space is the exponentially large set of possible word sequences and the heuristic is typically a language model score. The algorithm has also been applied to protein structure prediction and combinatorial optimization, wherever the full search tree is intractable but a good approximate solution is acceptable. Beam search is not a failed attempt at optimality; it is a recognition that in many real systems, the best feasible solution is better than the optimal infeasible one.