# Beam Search

Beam search is a heuristic search algorithm that explores a graph by expanding the most promising nodes in a limited set, balancing quality and diversity in sequence decoding. It is a modification of best-first search that reduces memory requirements by keeping only a predetermined number of best partial solutions.

Beam search is a heuristic search algorithm used in computer science to explore a graph by expanding the most promising node in a limited set. It is a modification of best-first search that reduces memory requirements by keeping only a predetermined number of best partial solutions as candidates, making it a greedy algorithm. The algorithm is widely applied in sequence decoding tasks, such as machine translation and speech recognition, where it balances output quality with computational tractability.

The core idea of beam search is to maintain a set of the most promising partial solutions, called the beam, and expand only those at each step. This approach contrasts with exhaustive search methods that consider all possible paths, which can be computationally prohibitive for large search spaces. By pruning less promising candidates, beam search achieves efficiency while sacrificing guarantees of completeness and optimality.

## Algorithmic Details

Beam search operates using a breadth-first search strategy to build its search tree. At each level of the tree, it generates all successors of the states at the current level and sorts them in increasing order of heuristic cost. However, it only stores a predetermined number, denoted as β (the beam width), of the best states at each level. Only those states are expanded next, and the rest are discarded.

The beam width β is a critical parameter that controls the trade-off between search quality and resource usage. A larger beam width retains more states, reducing the number of pruned candidates and potentially improving solution quality, but it also increases memory and computational requirements. With an infinite beam width, no states are pruned, and beam search becomes identical to best-first search. Conversely, a beam width of 1 corresponds to a hill-climbing algorithm, which greedily follows only the single best path.

The beam width bounds the memory required to perform the search, making it suitable for large systems with limited memory. However, because a goal state could potentially be pruned, beam search sacrifices completeness - the guarantee that an algorithm will terminate with a solution if one exists. Additionally, beam search is not optimal, meaning there is no guarantee that it will find the best possible solution.

## Historical Development

The first use of what would become known as beam search was in the Harpy Speech Recognition System, introduced in a 1976 dissertation. The procedure was originally referred to as the "locus model of search," but the term "beam search" was already in use by 1977. Harpy was developed at [Carnegie Mellon University](https://www.wikiprompt.org/wiki/carnegie-mellon-university) and represented a significant advancement in speech recognition technology, demonstrating the practical utility of heuristic search in real-world applications.

The development of beam search was part of a broader trend in the 1970s toward efficient search algorithms for artificial intelligence systems. Researchers recognized that exhaustive search methods were often impractical for complex problems, leading to the development of heuristic approaches that could find good solutions quickly. The Harpy system's success helped establish beam search as a fundamental technique in the field.

## Applications in Machine Translation

Beam search has been most prominently used in machine translation systems, where it helps select the best translation among many possible candidates. In traditional statistical machine translation, each part of a sentence is processed, and many different ways of translating the words are generated. Beam search keeps the top best translations according to their sentence structures and discards the rest, then evaluates the remaining translations according to a given criterion to choose the one that best meets the goals.

In modern neural machine translation, which primarily uses [large language models](https://www.wikiprompt.org/wiki/large-language-model) and [transformer](https://www.wikiprompt.org/wiki/transformer) architectures, beam search remains a key decoding strategy. During generation, the model produces a probability distribution over possible next tokens at each step. Beam search maintains multiple partial sequences, expanding the most promising ones based on their cumulative probabilities. This approach produces higher-quality translations than greedy decoding, which selects only the single most likely token at each step.

The application of beam search in machine translation has been extensively studied, with researchers exploring various modifications to improve performance. For example, length normalization is often applied to avoid biasing toward shorter sequences, and diverse beam search techniques have been developed to encourage variety among the candidate sequences.

## Variants and Extensions

Several variants of beam search have been developed to address its limitations, particularly its lack of completeness and optimality. One approach combines beam search with depth-first search, resulting in beam stack search and depth-first beam search. These 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.

Another variant, beam search using limited discrepancy backtracking (BULB), combines beam search with limited discrepancy search. This approach also produces anytime algorithms that can improve solutions over time. In the context of local search, local beam search is a specific algorithm that begins by selecting β randomly generated states and then, for each level of the search tree, considers β new states among all possible successors of the current ones until reaching a goal.

Since local beam search often ends up on local maxima, a common solution is to choose the next β states in a random way, with a probability dependent on the heuristic evaluation of the states. This kind of search is called stochastic beam search. Other variants include flexible beam search and recovery beam search, which adjust the beam width dynamically or allow for recovery from poor pruning decisions.

## Role in Modern AI Systems

Beam search plays a crucial role in modern [artificial intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence) systems, particularly in [generative AI](https://www.wikiprompt.org/wiki/generative-ai) applications. In [deep learning](https://www.wikiprompt.org/wiki/deep-learning) models, especially those based on the transformer architecture, beam search is used during inference to generate sequences such as text, code, or speech. Companies like [OpenAI](https://www.wikiprompt.org/wiki/openai), [Anthropic](https://www.wikiprompt.org/wiki/anthropic), and [Google DeepMind](https://www.wikiprompt.org/wiki/google-deepmind) employ beam search in their language models to produce coherent and contextually appropriate outputs.

The technique is also used in other sequence generation tasks, such as image captioning, speech recognition, and protein structure prediction. In these applications, beam search helps balance the quality of the generated output with the computational resources required. The beam width can be tuned based on the specific requirements of the task, with larger widths providing better quality at the cost of increased computation.

## Theoretical Properties

Beam search's theoretical properties have been analyzed in the context of heuristic search. As a greedy algorithm, it makes locally optimal choices at each step, which can lead to sub-optimal global solutions. The algorithm's performance depends heavily on the quality of the heuristic function used to evaluate states. A well-designed heuristic can guide the search toward good solutions, while a poor heuristic may cause the algorithm to miss optimal paths.

The trade-off between beam width and solution quality is a central consideration in practical applications. Research has shown that increasing the beam width generally improves solution quality, but with diminishing returns. In some cases, a beam width that is too large can lead to over-generation and increased computational costs without significant quality improvements. Conversely, a beam width that is too small may result in poor solutions due to excessive pruning.

## Computational Considerations

The computational complexity of beam search is primarily determined by the beam width and the branching factor of the search space. At each level, the algorithm generates successors for all states in the beam, which requires β × b operations, where b is the branching factor. The sorting of these successors adds an additional factor of log(β × b) per level. The total complexity is therefore O(β × b × L × log(β × b)), where L is the maximum depth of the search.

Memory usage is bounded by the beam width, as only β states are stored at each level. This makes beam search particularly attractive for applications with limited memory, such as embedded systems or real-time processing. The algorithm's ability to balance memory usage and solution quality has contributed to its enduring popularity in both academic research and industrial applications.

## Comparison with Other Search Methods

Beam search is often compared with other search algorithms, such as greedy search, best-first search, and [machine learning](https://www.wikiprompt.org/wiki/machine-learning)-based decoding methods. Greedy search, which corresponds to beam search with a beam width of 1, is computationally efficient but often produces lower-quality results. Best-first search, which considers all partial solutions, can find optimal solutions but requires memory proportional to the entire search space.

In the context of neural sequence generation, beam search is sometimes contrasted with sampling-based methods, which randomly select tokens based on their probability distributions. Sampling can produce more diverse outputs but may sacrifice coherence, while beam search tends to produce more deterministic and higher-quality results. Recent research has explored hybrid approaches that combine beam search with sampling to achieve a balance between quality and diversity.

## Future Directions

As of the early 2020s, beam search continues to be an active area of research, particularly in the context of large language models. Researchers are exploring adaptive beam width strategies that adjust based on the confidence of the model's predictions, as well as methods for incorporating external constraints into the beam search process. The development of more efficient hardware, such as specialized AI accelerators from companies like [NVIDIA](https://www.wikiprompt.org/wiki/nvidia) and [AMD](https://www.wikiprompt.org/wiki/amd), has enabled larger beam widths and more complex search strategies in real-time applications.

The integration of beam search with other AI techniques, such as reinforcement learning and [neural networks](https://www.wikiprompt.org/wiki/neural-network), is also an area of ongoing investigation. These efforts aim to improve the efficiency and effectiveness of sequence generation in a wide range of applications, from natural language processing to scientific discovery.

---
Source: https://www.wikiprompt.org/wiki/beam-search
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-07T21:29:19.332901+00:00