Beam search is a heuristic search algorithm that explores a space of possible solutions while retaining only a limited number of promising candidates at each stage. This limit, called the beam width, controls how many partial solutions remain available for further expansion. By discarding other candidates, beam search reduces memory use and computation relative to exhaustive search, but generally sacrifices guarantees of finding a solution or the globally best solution. It is widely used in artificial intelligence, particularly for decoding sequences in machine translation, speech recognition, and other structured prediction tasks.
Basic procedure
In its common level-synchronous form, beam search resembles breadth-first search, except that it retains at most candidates at each depth rather than the entire frontier. The positive integer is the beam width.
A candidate represents a partial solution, such as a path through a graph or a prefix of an output sentence. A scoring function ranks candidates according to their estimated usefulness. Depending on the problem, higher scores may indicate greater probability or reward, while lower scores may indicate lower cost.
A typical iteration proceeds as follows:
- Expand: Generate possible successors of each candidate in the current beam.
- Score: Evaluate the resulting candidates.
- Select: Retain only the best eligible candidates across the combined successor set.
- Terminate or repeat: Record completed solutions and continue expanding unfinished candidates until a stopping condition is satisfied.
Selection is normally global across all successors, not a separate selection of successors for each parent. Several surviving candidates may therefore descend from the same parent.
Let denote the beam at depth , let be the successors of candidate , and let be a score to maximize. The basic update is
These expressions omit application-specific handling of completed solutions, duplicate states, constraints, and ties. Such choices can materially change the algorithm’s behavior.
For graph search, implementations may also detect repeated states or cycles. Without such handling, several candidates can represent redundant paths or revisit the same states.
Beam width and pruning
Beam width is a hyperparameter governing the trade-off between search effort and the number of alternatives retained.
With , the level-synchronous procedure reduces to greedy search: only the highest-scoring successor of the current candidate survives. Larger widths preserve alternatives that may initially appear less promising but lead to better complete solutions.
For example, suppose two first-step choices have probabilities and . If their most probable continuations have conditional probabilities and , respectively, the best complete paths through them have probabilities
Greedy search discards the second choice immediately, whereas a beam of width two can preserve it and discover the better complete path.
The defining limitation is irreversible pruning: ordinary beam search does not return to discarded candidates. A promising solution can therefore be lost because one of its prefixes ranked poorly.
For a finite search tree, a beam wide enough to retain every candidate at every level eliminates beam pruning and reproduces exhaustive level-wise exploration. At practical widths, however, beam search is generally neither complete nor optimal. Moreover, beams produced with different widths need not remain nested across successive steps, so increasing width does not provide a universal guarantee of a better returned score.
Sequence decoding
Beam search is especially prominent in natural language processing. An autoregressive language model assigns a probability to an output sequence , optionally conditioned on an input :
Here, denotes the preceding output symbols. In text systems, these symbols are typically tokens defined by a tokenization scheme.
Decoding commonly seeks a high-probability complete sequence:
where is the set of allowed outputs. Exhaustively enumerating that set is usually impractical because the number of possible sequences grows exponentially with length.
A beam decoder retains several output prefixes. Each prefix is extended with possible next tokens, and the highest-scoring extensions survive. Scores are usually accumulated as log probabilities:
Logarithms preserve the ordering of positive probabilities and avoid the numerical underflow associated with multiplying many small values.
An end-of-sequence token marks completion. Its probability is part of the probability of the complete sequence. Implementations differ in whether finished candidates occupy beam slots or are stored separately while unfinished candidates continue expanding.
Beam search is a decoding procedure, not a model architecture or training method. It can be used with recurrent neural networks, Transformers, and other models, including systems built around an encoder–decoder architecture.
Length effects and adjusted scores
Raw sequence probability creates a preference for shorter outputs in the sense that extending a fixed prefix cannot increase its probability. This mathematical property does not by itself establish the correct output length; useful decoding also depends on the model’s learned termination behavior.
Decoders often modify the ranking objective. One possible length-normalized score is
where is the output length and controls the adjustment. Other formulas use an offset length penalty.
Further adjustments can include rewards for covering the input, penalties for repetition, or combinations of several model scores. These modifications change the objective being optimized: a better adjusted score does not necessarily imply a higher model probability.
Stopping conditions
Finding one completed candidate is generally insufficient reason to stop, because an unfinished candidate may later produce a better completion.
For unnormalized cumulative log probability, an unfinished prefix’s score is an upper bound on the score of any extension: each additional log probability is nonpositive. If the best completed sequence scores at least as highly as every surviving unfinished prefix, no descendant of those prefixes can beat it.
This stopping guarantee applies only to candidates that survived pruning. It does not restore global optimality. Length normalization, future rewards, and other score adjustments may invalidate the simple bound and require different stopping rules.
Computational requirements
Let the maximum search depth be , the beam width be , and the maximum branching factor be . A straightforward implementation generates at most approximately successors per step, giving candidate generation and scoring operations when each operation has constant cost.
The actual time complexity also depends on selecting the best candidates. Sorting all successors costs per step. Partial-selection methods or a bounded priority queue can avoid a full sort.
Memory requirements depend on what is stored:
- The live beam contains at most candidates.
- Materializing all successors can require temporary candidate records.
- Storing complete prefixes directly can require space.
- Parent pointers can share prefix structure, although recovering outputs still requires retaining relevant history.
For neural decoding, candidate bookkeeping is only part of the cost. Each prefix also has model state. In Transformer inference, a key–value cache can substantially increase memory consumption as beam width and sequence length grow.
Candidate computations can often be batched on a graphics processing unit, but batching does not eliminate the additional arithmetic and memory associated with multiple hypotheses.
Related algorithms and variants
Best-first and A* search
General best-first search maintains a frontier ordered by a heuristic evaluation function, potentially containing nodes at different depths. Level-synchronous beam search instead compares candidates at a common expansion step and imposes a hard width limit.
A* search can provide optimality guarantees under appropriate assumptions about costs and heuristics. Ordinary beam pruning can discard the path to an optimal solution, even when its scoring function uses an admissible heuristic.
Dynamic programming and Viterbi decoding
Dynamic programming exploits reusable subproblems or states with equivalent futures. Viterbi decoding, for example, retains the best path to each relevant state in suitable finite-state models.
Beam search instead limits the total number of retained hypotheses. It may discard a state that remains necessary for the globally best result.
The approaches can also be combined: a decoder may merge equivalent states using dynamic programming and then apply beam pruning. For general autoregressive neural models, distinct prefixes usually induce different future predictions and cannot simply be merged into one exact state.
Diversity-oriented and stochastic variants
Ordinary beam search often retains near-duplicate candidates. Diverse beam search modifies selection, for example by dividing candidates into groups and penalizing overlap, to encourage distinct alternatives. Diversity then becomes part of the search objective rather than a consequence of retaining more hypotheses.
Stochastic beam methods introduce randomness into candidate selection. Some are designed around particular sampling distributions, while others are heuristic combinations of search and sampling. A deterministic top- beam should not be interpreted as a set of independent samples from the model.
Constraint-aware and backtracking variants
Constrained beam search tracks requirements such as mandatory phrases, valid syntactic structures, or legal action sequences. Candidates may be partitioned according to constraint progress so that an important but temporarily low-scoring path is not immediately eliminated.
Other variants preserve discarded alternatives for later reconsideration, as in beam-stack search or limited-discrepancy methods. Their guarantees depend on the specific backtracking and pruning rules; they are not properties of ordinary beam search.
History and applications
Beam search became established in early artificial-intelligence and speech-understanding research. The Harpy speech-understanding system of the 1970s is a notable early example of beam-style pruning. In speech systems, “beam” can also refer to a score threshold relative to the current best hypothesis, rather than a fixed number of candidates. Threshold-based and fixed-width pruning are related but distinct.
Later applications included statistical machine translation, parsing, and neural sequence generation. Beam search has also been used in automatic text summarization, image captioning, planning, and program generation.
Its role is to approximate the search over outputs or action sequences. It does not determine the underlying model’s accuracy, and a wider beam cannot compensate for a model that assigns high scores to unsuitable solutions.
Limitations and evaluation
Beam search has several separate sources of failure:
- Search error: Pruning removes the highest-scoring complete solution.
- Scoring error: The scoring function favors an incorrect or unsuitable result.
- Limited diversity: Many beam positions are occupied by almost identical candidates.
- Constraint failure: Necessary requirements are omitted or inadequately represented during search.
- Resource cost: Additional hypotheses increase computation and memory use.
A larger beam may reduce some search errors while exposing deficiencies in the scoring model. For example, it may find an output with higher model probability but worse translation quality. This distinction is particularly important for large language model generation, where the most probable sequence is not necessarily the most informative, varied, or appropriate response.
Evaluation therefore distinguishes the decoder’s objective score from external task quality. Beam width, score adjustments, and stopping rules are commonly selected using a validation set, while final comparisons use a separate test set. Reproducible comparisons also specify how completed candidates, ties, constraints, duplicate states, and maximum output lengths are handled.