A model that generates text or another sequence makes a series of local decisions. At each step, it assigns scores or probabilities to possible next tokens. The simplest decoder chooses the most likely token, appends it, and repeats.

That strategy is called greedy decoding. It is cheap and easy to understand, but an early choice that looks best by itself can lead to a worse complete sequence. Once greedy decoding commits to that choice, it cannot reconsider it.

Beam search reduces this problem by keeping several promising partial sequences alive at the same time. It does not guarantee the globally best sequence, and it is not appropriate for every generative task. But it provides a useful mental model for understanding the trade-off between search quality and inference cost.

This article explains how beam search works, how sequence scores are calculated, why length matters, and when a wider search is useful or wasteful.

The problem with choosing one token at a time

Suppose a model must generate a two-token sequence. At the first step it predicts:

A: 0.55
B: 0.45

Greedy decoding chooses A because 0.55 is larger than 0.45.

Now suppose the next-token probabilities are:

after A:
X: 0.50
Y: 0.50

after B:
X: 0.90
Y: 0.10

The probability of a complete sequence is the product of its conditional token probabilities. The strongest continuation through A is:

P(A, X) = 0.55 * 0.50 = 0.275

But the strongest continuation through B is:

P(B, X) = 0.45 * 0.90 = 0.405

Greedy decoding never discovers B X because it discarded B after the first step.

The lesson is not that the second-most-likely token is usually better. The lesson is that the score of a partial sequence does not completely determine the score of its future continuations. Search can therefore matter when the goal is to find a high-scoring complete sequence.

Beam search keeps several hypotheses alive

A beam is the set of partial sequences retained after each generation step. Its maximum size is the beam width, often written as k.

With beam width 2, the previous example starts by keeping both candidates:

A    score 0.55
B    score 0.45

At the next step, each candidate is expanded:

A X    0.55 * 0.50 = 0.275
A Y    0.55 * 0.50 = 0.275
B X    0.45 * 0.90 = 0.405
B Y    0.45 * 0.10 = 0.045

The decoder then keeps only the two highest-scoring candidates:

B X    0.405
A X    0.275

Generation continues in this expand-score-prune cycle until a stopping condition is reached.

A simplified algorithm is:

beam = [empty sequence]

repeat:
    expand every unfinished sequence with possible next tokens
    score the expanded sequences
    keep the top k candidates
    stop when the search termination rule is satisfied

return the preferred finished candidate

Real implementations avoid literally expanding every vocabulary token when more efficient top-candidate operations are available, but the conceptual process is the same.

Use log probabilities for sequence scores

Multiplying many probabilities produces increasingly small numbers. In software, it is more convenient and numerically stable to add log probabilities instead.

For tokens y1 ... yT conditioned on input x, a model factorizes the sequence probability as:

P(y1 ... yT | x)
= P(y1 | x)
  * P(y2 | y1, x)
  * ...
  * P(yT | y1 ... yT-1, x)

Taking logarithms turns the product into a sum:

log P(y1 ... yT | x)
= sum over t of log P(yt | y1 ... yt-1, x)

Because logarithm is strictly increasing, comparing unmodified sequence probabilities and comparing their log probabilities gives the same ordering.

For the earlier B X example:

log P(B, X) = log(0.45) + log(0.90)

The exact numeric value is less important than the rule: every generated token contributes its conditional log probability to the candidate’s cumulative score.

Why raw scores tend to prefer shorter sequences

Token probabilities are at most 1, so their log probabilities are at most 0. Adding another token therefore cannot increase an unnormalized log-probability score. This creates an important length effect.

Consider two completed candidates:

candidate 1: log score = -2.0, length = 4
candidate 2: log score = -2.4, length = 8

Using raw log probability alone, candidate 1 wins because -2.0 is greater than -2.4. That comparison may be appropriate if the model’s sequence probability is exactly the objective you want. In many generation tasks, however, raw scoring can favor outputs that terminate too early.

A decoder can compensate with a length normalization or length penalty. One simple teaching example is average log probability:

normalized score = log probability / sequence length

For the candidates above:

candidate 1: -2.0 / 4 = -0.50
candidate 2: -2.4 / 8 = -0.30

Under this scoring rule, candidate 2 ranks higher.

This example illustrates the principle, not a universal production formula. Beam-search implementations use different length-penalty definitions and parameters. A length penalty changes the search objective, so its meaning must be checked in the specific framework or model implementation being used.

Finished and unfinished candidates need careful handling

Sequence models commonly emit a special end-of-sequence token. Once a hypothesis produces that token, the candidate is complete and should not be expanded as though normal generation were continuing.

This creates two groups during search:

  • unfinished candidates that can still receive tokens;
  • finished candidates that are eligible to become the final output.

Stopping as soon as the first candidate finishes can be wrong because another unfinished candidate may later achieve a better final score under the decoder’s scoring rule. Waiting until every beam finishes can also waste computation.

Practical implementations therefore use a termination rule that considers finished candidates and whether unfinished candidates can still compete with them. The exact rule depends on the scoring method and library. Treat early stopping behavior as an implementation choice rather than an inherent guarantee of beam search.

Beam width controls a quality-cost trade-off

Beam width 1 reduces beam search to greedy search: only one partial sequence survives each step.

Increasing the width lets the decoder preserve more alternatives. That can recover a sequence that would otherwise be pruned early. It also increases work because more hypotheses must be expanded, scored, and tracked.

The relationship is not “larger beam equals better output.” A wider beam searches the model’s scoring objective more thoroughly, but that objective may not perfectly match human judgments or task quality. If the model assigns high probability to bland, repetitive, or otherwise undesirable sequences, better search can simply find those high-probability sequences more effectively.

A wider beam also consumes more memory for per-hypothesis state. In autoregressive transformer inference, implementations may need to maintain or reorganize attention key-value cache state for multiple beam hypotheses. The exact memory and latency behavior depends on the inference engine, batching strategy, model architecture, and hardware.

Choose beam width empirically against the metric that matters for the application rather than assuming a standard value is optimal.

Beam search is not the same as sampling

Beam search and sampling solve different problems.

Beam search is primarily a search procedure. It tries to retain high-scoring candidate sequences according to the model and any decoding adjustments.

Sampling is a stochastic generation procedure. It draws tokens from a probability distribution, often after transformations such as temperature or top-p filtering. Repeated runs can intentionally produce different outputs.

This distinction matters for product behavior. For a constrained generation task where a single high-probability sequence is desirable, deterministic or nearly deterministic search can be useful. For open-ended writing, dialogue, or ideation, repeatedly choosing only high-probability paths may produce less varied results than sampling.

Neither approach fixes incorrect model beliefs. Decoding controls how outputs are selected from model predictions; it does not make the underlying predictions factual or aligned with the user’s intent.

Treating beam search as a guarantee of the global optimum

Beam search is approximate. At every step it discards candidates outside the top k. A discarded candidate could have led to the highest-scoring complete sequence later.

An exhaustive search would avoid that pruning, but sequence spaces grow exponentially with length and are generally impractical for realistic vocabularies and generation lengths.

Comparing scores without checking normalization

Raw cumulative log probabilities, average log probabilities, and framework-specific length penalties can rank the same candidates differently. When debugging surprising outputs, inspect the actual score definition before changing the beam width.

Tuning only on model score

A decoder can improve the score assigned by the model without improving the application’s real objective. Evaluate generated outputs with task-relevant measurements and representative examples. For tasks with multiple acceptable answers, a reference-based metric alone may also miss important aspects of quality.

Using a large beam when greedy decoding is already sufficient

If greedy decoding already meets quality requirements, a wider beam adds complexity and inference cost without necessarily creating user-visible value. Search effort should earn its cost.

Expecting search to repair hallucinations

Beam search explores outputs under the model’s probability distribution. It does not verify facts, retrieve missing knowledge, or detect unsupported claims. If factual grounding is the problem, improve the relevant data, retrieval, verification, prompting, or model behavior rather than relying on beam width.

When beam search is a good fit

Beam search is most attractive when the task has a relatively narrow set of desirable outputs and sequence-level probability is a useful signal. Historically, variants of beam search have been widely used for structured sequence-generation problems such as translation and speech recognition, often with task-specific scoring adjustments.

It is worth testing when:

  • greedy decoding makes locally attractive choices that hurt complete outputs;
  • deterministic output is useful;
  • the application can afford multiple active hypotheses;
  • task evaluation shows that additional search improves the result that users care about.

A simpler decoder is preferable when greedy output is already adequate, latency or memory is tightly constrained, or diversity is a primary requirement. Sampling is often a more natural starting point when varied, open-ended generations are desired.

Evaluate the decoder as part of the system

Decoding parameters are part of model deployment, not cosmetic settings. Changing beam width, length penalties, stopping rules, or token constraints can change application behavior even when model weights stay fixed.

A practical evaluation should therefore keep a representative input set and compare configurations on dimensions such as:

task quality
output length
failure cases
latency
memory use
stability across representative inputs

Do not tune a beam configuration on a few memorable examples. A setting that fixes one case can shift behavior elsewhere. The right configuration is the smallest amount of search that produces a worthwhile improvement under the application’s actual constraints.

Conclusion

Greedy decoding follows one path. Beam search keeps several paths alive so an early local choice does not immediately determine the entire output.

The central mechanism is simple: expand partial sequences, accumulate token log probabilities, prune to a fixed beam width, and continue until suitable finished candidates are available. The practical difficulty lies in the surrounding choices—beam width, length scoring, stopping rules, and evaluation criteria.

Use beam search when exploring several high-scoring hypotheses improves a sequence task enough to justify the extra inference work. When it does not, a simpler decoder is usually the better engineering choice.

Artificial Intelligence Machine Learning Sequence Generation Inference