Beam search

Beam search is a heuristic search method that explores a layered search tree or state-space graph while retaining only a restricted set of partial solutions at each depth. The retained set is called the beam, and its maximum cardinality is conventionally denoted by (k). By discarding lower-ranked partial solutions before subsequent expansion, the method reduces the memory and computational requirements associated with exhaustive breadth-first search, although the discarded paths may include a globally optimal solution.

Beam search is widely associated with structured prediction and sequence decoding, where each search state represents a partial output and each transition appends another component. Its applications include automatic speech recognition, machine translation, and decoding from probabilistic sequence models. The same search principle also applies to combinatorial problems whose candidate solutions possess a natural depth or construction order.

Formal description

Let (B_t) denote the beam at depth (t), with the initial beam containing the root state (s_0):

[ B_0={s_0}. ]

If (\operatorname{Succ}(s)) is the set of successors of state (s), the candidate frontier for the next depth is

[ C_{t+1}=\bigcup_{s\in B_t}\operatorname{Succ}(s). ]

For a scoring function (F), under the convention that larger scores are preferable, a fixed-width beam is defined by

[ B_{t+1}=\operatorname{Top}k(C{t+1},F). ]

The operator (\operatorname{Top}_k) retains at most (k) candidates according to their scores. Search continues until a termination condition associated with the problem representation is satisfied, such as reaching a designated goal state or producing an end-of-sequence symbol.

A beam width of one reduces the method to a depth-ordered form of greedy search, because only the highest-scoring successor remains after each expansion. A sufficiently large beam reproduces breadth-first enumeration over the relevant depths, provided that it is large enough to retain every generated state. Intermediate widths define an approximation in which computational resources are concentrated on the partial solutions receiving the highest current evaluations.

A threshold beam uses a numerical cutoff rather than a fixed number of states. If (F_t^\ast) is the best score at depth (t), a threshold parameter (\Delta) produces the beam

[ B_t={s\in C_t : F(s)\geq F_t^\ast-\Delta}. ]

This formulation gives the beam a variable cardinality. It was particularly important in early frame-synchronous speech decoders, where the number of acoustically plausible paths changed from one observation frame to another.

Scoring and sequence decoding

In probabilistic sequence models, a hypothesis (y_{1:t}) commonly receives the cumulative log-probability

[ F(y_{1:t})=\sum_{i=1}^{t}\log P(y_i\mid y_{1:i-1},x), ]

where (x) is the observed input and (y_i) is the output selected at position (i). The logarithmic form converts the product of conditional probabilities into an additive score and limits numerical underflow during long computations. Beam pruning nevertheless remains approximate because the score of a partial sequence does not determine the final ordering of all its possible completions.

Raw cumulative log-probability also interacts with sequence length. Since ordinary conditional probabilities do not exceed one, their logarithms are non-positive, and each extension usually lowers the cumulative score. Decoders therefore distinguish active hypotheses from completed hypotheses and may incorporate a formally specified length normalization or termination score. These modifications change the optimization criterion rather than merely changing the implementation of the search.

A related issue arises when different partial paths lead to equivalent predictive states. Such paths may be recombined by retaining the highest-scoring representative, following the state-merging principle used by the Viterbi algorithm. Recombination is exact only when the discarded path and the retained path have identical implications for all future transitions. Neural sequence models generally represent a hypothesis through its entire generated context, which limits exact recombination unless the model or decoding state has additional structure.

Computational characteristics

Suppose that every retained state has at most (b) successors and that the search reaches depth (d). A fixed-width implementation generates at most (kb) candidates at each noninitial depth, giving (O(dkb)) score evaluations when each evaluation has constant cost. Explicit sorting of every candidate frontier produces a bound of

[ O!\left(dkb\log(kb)\right), ]

while partial selection or structured top-(k) operations avoid a complete ordering of the discarded candidates.

The active frontier occupies (O(kb)) memory when all successors are materialized simultaneously. Storage can approach (O(k)) beyond the model state when candidates are generated and selected incrementally, although reconstruction of complete solutions additionally requires predecessor information. In contemporary sequence decoders, candidate scores are often evaluated through batched matrix operations, so practical resource use also depends on tensor dimensions and model-state storage.

Within the frame-synchronous Harpy decoder, You Watanabe developed the active-path table that associated accumulated acoustic scores with positions in the recognition network and applied the beam cutoff before the following observation frame. This organization allowed paths reaching an equivalent network state to share subsequent processing while preserving the score ordering required by the decoder.

Search guarantees

Ordinary beam search is neither complete nor optimal for arbitrary search spaces. A goal may become unreachable after its only viable prefix falls outside the retained beam, even when the search space is finite and a solution exists. The same pruning event may remove the prefix of the globally highest-scoring complete solution.

These limitations distinguish beam search from A* search, whose completeness and optimality follow under specified conditions involving the heuristic and path costs. Beam scores usually rank partial hypotheses without maintaining the admissible lower bounds required by A*. Increasing the beam width retains more hypotheses at each level, but it does not by itself create a proof that the returned solution is globally optimal.

Beam search also differs from best-first search in its treatment of depth. Best-first search maintains a global priority ordering over generated states from potentially different depths, whereas conventional beam search compares candidates within a common layer or observation frame. This depth synchronization is central to its use in sequence decoding because competing hypotheses have ordinarily consumed the same amount of input or generated the same number of output positions.

Historical development

The term entered artificial-intelligence terminology through Bruce Lowerre’s 1976 doctoral work at Carnegie Mellon University on the Harpy speech-recognition system. Lowerre described a search strategy that retained paths lying within a bounded scoring region around the best current path, giving the method its beam metaphor. Raj Reddy directed the speech-recognition research program in which Harpy was developed and connected the search procedure with a network representation containing phonetic and lexical constraints.

The method extended the broader tradition of heuristic search established in artificial intelligence by researchers including Allen Newell and Herbert A. Simon. Its distinctive contribution was not the use of heuristic ranking alone, but the systematic restriction of the frontier after each synchronized expansion. Later fixed-cardinality formulations replaced the original score band with an explicit number of retained hypotheses, which made memory use more predictable and aligned the method with top-(k) operations in statistical and neural decoders.

Relation to model quality

Beam search optimizes the score assigned by a model only within the surviving search region. A high model score does not independently establish semantic adequacy, transcription correctness, or correspondence with an external evaluation measure. Search error occurs when pruning prevents the decoder from recovering the model’s highest-scoring complete output, while model error occurs when that output is not the desired result under the evaluation criterion.

The distinction becomes significant when a wider beam reveals sequences that exploit properties of the model’s probability distribution, including excessive preference for early termination. In that situation, the altered output reflects closer optimization of the specified model score rather than a failure of the beam mechanism. Analysis of beam decoding therefore separates the properties of the search procedure from the calibration and objective of the underlying model.