---
kind: concept
slug: beam-search
title: Beam search
summary: >-
  Keeps the W best partial outputs at each step; width 1 is greedy decoding. Gains over greedy depend on the model: width 8 adds 1.9 BLEU for one translation model, and language-model re-ranking helps one grammar-correction model but hurts another. Variants: diverse pools, classifier-weighted scores, learned policies, length normalisation, token masks. Trade-off: more work per step.
tags: [decoding, search, inference, length-normalisation]
papers: ["2603.01786", "1612.01744", "2203.16804", "2203.09509", "2301.07695", "2607.06818", "2212.06094", "2604.23627"]
related: [decoding-strategies, constrained-decoding, neural-machine-translation, text-summarization, toxicity-detection, neural-combinatorial-optimization, controllable-text-generation, nucleus-sampling, monte-carlo-tree-search, sequence-to-sequence-learning, reward-proportional-sampling, semantic-parsing, prompt-engineering]
status: draft
updated_at: 2026-11-06
---

## Overview

Beam search is a decoding rule for models that produce a sequence one step at a
time. Greedy decoding keeps one path and takes the most probable next item at
each step. Beam search keeps the W best partial paths, extends each one with
every candidate next item, and prunes back to W [arxiv:2603.01786 §3.4]. With
W = 1 the rule is greedy decoding [arxiv:2603.01786 §3.4]. The stopping rule
differs between papers; see the variants below.

The shared idea is the bounded set: at every step the search holds at most W
hypotheses, ranked by one score. Work per step grows with W, because each
hypothesis is expanded. The variants below differ in what goes into the
candidate pool, what the score is, and how the search stops. The sibling page
[Decoding strategies](/concepts/decoding-strategies) compares beam search with
sampling rules; this page covers the search itself.

The score is usually a sum of token log-probabilities. Several cards rescale
that sum by a length term [arxiv:2203.16804 eq. 9] [arxiv:2607.06818 eq. 10].

## Variants

### Plain beam for a trained sequence model

A translation model with a beam of 8 scores above its own greedy decoding on
the main text test set: 39.8 to 41.7 BLEU. Each column in that table adds one
component to the previous one, so the beam step is the gap from the greedy
column [arxiv:1612.01744 tab. 2]. On the speech test set, with seven references
and the held-out speaker, the same step moves 37.6 to 40.1 [arxiv:1612.01744
tab. 3]. The second text test set does not move (41.0 to 41.0) [arxiv:1612.01744
tab. 2]. Card: [Listen and Translate](/papers/1612.01744).

### Diverse beams for a candidate pool

[BRIO](/papers/2203.16804) uses a diverse beam search to write 16 summaries for
each training article, then ranks them by ROUGE against the reference
[arxiv:2203.16804 §3]. The paper gives the number of candidates but not the beam
width or the diversity setting [arxiv:2203.16804 app. B]. The released code uses
different settings for its two datasets; see the card's Paper vs code section.
Generating candidates runs over the whole training set before training starts.
The authors call this a non-trivial overhead [arxiv:2203.16804 §5.5].

### Classifier-weighted beam score

[ToxiGen](/papers/2203.09509) pushes generation away from a prompt's label with
a classifier. Each candidate's score is a weighted sum of the language model's
log-probability and the classifier's log-probability for the target class. The
weights are 0.5 and 0.5, the beam size is 10, and outputs are at most 30 tokens
[arxiv:2203.09509 §3.3] [arxiv:2203.09509 eq. 1].

The effect is measurable. On 125 prompts, toxic prompts kept their label in
40.3% of ALICE outputs against 67.7% of top-k outputs. The classifier was
fooled in 26.4% of ALICE statements against 16.8% of top-k statements
[arxiv:2203.09509 §4.3]. The method needs log-probabilities for many candidate
tokens at each step. The GPT-3 API the authors used returned only a subset, so
they kept the top 100 [arxiv:2203.09509 §3.3].

### Beam over a learned goal-seeking policy

[Learning Shortest Paths with Generative Flow Networks](/papers/2603.01786)
trains a backward policy that walks from a state toward the goal. The beam is
scored by summed log backward probabilities, and the search stops when the goal
is reached [arxiv:2603.01786 §3.4]. On 4x4x4 Rubik's cubes the authors report
valid paths for the whole test set at width 2^12. They say the baseline needs
at least 2^18 for the same [arxiv:2603.01786 §4.2] [arxiv:2603.01786 tab. 1].
Table 1 leaves its "x" entries undefined, and reported lengths depend on both
the width and the step budget [arxiv:2603.01786 tab. 1].

### Beam with external language-model re-ranking

A grammatical-error-correction model for Romanian decodes with a beam of 8 and
then re-ranks the final beams with a 5-gram language model [arxiv:2604.23627
§4.1]. The effect depends on the model. For the model fine-tuned after
synthetic pretraining, F0.5 falls from 53.76 without re-ranking to 49.52 with
it, and to 49.83 with the normalised language-model term [arxiv:2604.23627 tab.
5]. For the model trained on synthetic data alone, the same step raises F0.5
from 16.62 to 17.32 [arxiv:2604.23627 tab. 5]. The authors cite the small
language-model corpus and a fixed weight that was not tuned [arxiv:2604.23627
§5]. Card: [Neural Grammatical Error Correction for Romanian](/papers/2604.23627).

### Beam as a decoder under token masks

[LMQL](/papers/2212.06094) is a query language whose constraints, such as a word
limit or a stop phrase, become a token mask at each decoding step
[arxiv:2212.06094 §5.2]. It offers `beam(n)` next to `argmax` and `sample`. The
paper describes `beam(n)` as a scripted beam search, in which beams are kept
over holes and the control flow they drive, so beams may take different
branches [arxiv:2212.06094 §4]. The reported cost results use `argmax` and
`sample`, not beam [arxiv:2212.06094 §6.1] [§6.2] [§6.3]. Against chunk-wise
`generate()` with manual parsing, billable tokens fall 27 to 31% on the
chain-of-thought tasks and 76 to 85% on the ReAct and arithmetic tasks
[arxiv:2212.06094 tab. 3] [tab. 5]. In the released code the name `beam` maps
to a plain token-level beam of width 4. The card did not run either path, so
which one matches the paper's scripted search is not settled
[Prompting Is Programming card](/papers/2212.06094).

### Length normalisation

[BRIO](/papers/2203.16804) divides the summed log-probability by the output
length raised to a power alpha. Alpha is 2.0 for CNN/DailyMail and 0.6 for
XSum, set equal to the beam's length penalty [arxiv:2203.16804 eq. 9]
[arxiv:2203.16804 app. B].

The [ad headline paper](/papers/2607.06818) instead scales each word's
log-likelihood by a factor that depends on the word's position. Alpha is not
stated, and the paper does not explain the constant in the formula
[arxiv:2607.06818 eq. 10] [arxiv:2607.06818 §3.4]. Its ablation removes beam
normalisation and post-processing together. ROUGE-L falls from 6.33 to 5.37
[arxiv:2607.06818 tab. 1], so the effect of normalisation alone is not isolated.

The grammar-correction paper also names length-normalised beam search, but
gives no formula [arxiv:2604.23627 §4.1]. Its released code applies a
GNMT-style penalty with weight 0.6 while beams are kept during search. Per the
card's Paper vs code section, when no language model is used the final output
is still the raw highest log-probability beam, so the penalty changes which
beams survive but not which one is returned [Neural GEC card](/papers/2604.23627).

### Beam-derived confidence

[EHRSQL](/papers/2301.07695) decodes with 5 beams and a length penalty of 1.0
[arxiv:2301.07695 app. G]. Its refusal rule uses the largest per-token entropy
over the decoding steps, and refuses above a threshold [arxiv:2301.07695 §4.3].
The card's Pitfalls section records, from the released code, that the entropy
is read from one beam row per example. The answer may then come from another
beam. Longer outputs also have more steps in which the maximum can be high.
The card did not check these points against beam-search internals
[EHRSQL card](/papers/2301.07695).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Trained generator, want a cheap gain over greedy | Plain beam, width 4 to 8 | Width 8 gave +1.9 BLEU on one text test set and no change on another [arxiv:1612.01744 tab. 2]. Width 4 is the default in BRIO's generation [arxiv:2203.16804 tab. 5] |
| Quality may fall as width grows | Sweep the width on your own model | BART's ROUGE-1 fell from 44.29 at width 4 to 42.79 at width 100, while BRIO-Mul rose from 47.78 to 48.23 [arxiv:2203.16804 tab. 5] |
| Need many diverse outputs to rank or train on | Diverse beam groups, and accept the offline cost | 16 candidates per article [arxiv:2203.16804 §3]; the authors call the candidate step a non-trivial overhead [arxiv:2203.16804 §5.5] |
| Output must move toward or away from an external classifier | Weighted score, and check label agreement | Toxic-prompt label agreement fell to 40.3% [arxiv:2203.09509 §4.3]; needs many log-probabilities per step [arxiv:2203.09509 §3.3] |
| Goal-reaching search in a space too large to store | Beam over a learned policy, tuning width and budget together | Valid solutions at width 2^12 on 4x4x4 cubes [arxiv:2603.01786 §4.2] |
| Output lengths vary and the score favours some lengths | Length normalisation, with alpha tuned on dev | Alpha 2.0 and 0.6 across datasets [arxiv:2203.16804 app. B]; alpha not stated [arxiv:2607.06818 eq. 10] |
| A confidence score from the decoding run gates the answer | Take the score from the beam that produced the output | Card pitfall on EHRSQL's entropy source [arxiv:2301.07695 §4.3] |
| Output must follow token-level rules (word limit, stop phrase, fixed options) | Constraint-masked decoding, as LMQL runs it; use argmax or sample as reported, and test beam yourself | Masks cut billable tokens by 76 to 85% on two tasks against chunk-wise generation [arxiv:2212.06094 tab. 5]; no beam run is reported [arxiv:2212.06094 §6] |
| External language model will re-rank the final beams | Tune the LM weight on your own dev set, per model | F0.5 fell with re-ranking for one model and rose for another [arxiv:2604.23627 tab. 5] |

## Implementation sketch

The sketch below is written from the search rule in the cards. It is not any one
paper's code. The cards do not say how finished hypotheses are handled; this
sketch keeps them aside. Each step uses the length-normalised score of the BRIO
card [arxiv:2203.16804 eq. 9].

```pseudocode
# Length-normalised beam search over a next-token scorer  [arxiv:2603.01786 §3.4]
# Input:  start prefix, expand(prefix) -> [(token, logprob)], width W,
#         max_len T, alpha
# Output: best completed sequence

def beam_search(start, expand, width, max_len, alpha, eos):
    # Each beam entry: (tokens, summed log-probability)  [arxiv:2603.01786 §3.4]
    beams = [(start, 0.0)]
    finished = []
    for _ in range(max_len):
        # Extend every beam with every candidate next token
        # [arxiv:2603.01786 §3.4]
        candidates = [
            (seq + [tok], total + lp)
            for seq, total in beams
            for tok, lp in expand(seq)
        ]
        # Drop duplicate prefixes before pruning  [arxiv:2603.01786 app. D]
        candidates = unique_by_tokens(candidates)
        # Set aside completed sequences  [arxiv:2603.01786 §3.4]
        finished += [c for c in candidates if c[0][-1] == eos]
        beams = [c for c in candidates if c[0][-1] != eos]
        # Keep the W best by length-normalised score  [arxiv:2203.16804 eq. 9]
        beams = top(beams, width, key=lambda b: norm_score(b, alpha))
        if not beams:
            break
    return max(finished, key=lambda b: norm_score(b, alpha))

def norm_score(beam, alpha):
    # Summed log-probability divided by length to the power alpha  [eq. 9]
    tokens, total = beam
    return total / len(tokens) ** alpha
```

For a classifier-weighted variant, replace the score with a weighted sum of the
language model term and the classifier term [arxiv:2203.09509 eq. 1]. For a
diverse pool, the candidate step uses a diverse beam search rather than the
plain one above [arxiv:2203.16804 §3]; the cards do not spell out its rule.
For an external language-model re-ranker, add a weighted language-model score
to each final hypothesis before the sort [arxiv:2604.23627 §4.1]. For token
masks, the paper's masked decoding loop applies the mask to one hole at a time
[arxiv:2212.06094 alg. 2]. The cards do not show how that mask combines with
beam pruning, so check it before relying on it.

## Contradictions

None known between cards on the same setting. The effect of width differs by
model. In the BRIO table the baseline summariser loses ROUGE-1 as width grows,
while its own trained model gains [arxiv:2203.16804 tab. 5]. The translation card
reports one width only, so it cannot show a trend [arxiv:1612.01744 tab. 2].
Language-model re-ranking shows the same pattern: it lowers F0.5 for the
fine-tuned model and raises it for the synthetic-only model [arxiv:2604.23627
tab. 5].

Paper and code differ for LMQL. The paper's `beam(n)` is a scripted search
over holes [arxiv:2212.06094 §4]. The released code's `beam` is a token-level
search [Prompting Is Programming card](/papers/2212.06094), so a result from
one should not be assumed for the other.

## Papers

- [Learning Shortest Paths with Generative Flow Networks](/papers/2603.01786): beam over a learned backward policy, with a width sweep on Rubik's cubes and swap puzzles.
- [Listen and Translate](/papers/1612.01744): beam of 8 against greedy decoding, for text and speech translation.
- [BRIO: Bringing Order to Abstractive Summarization](/papers/2203.16804): diverse beams for candidate pools, a width sweep, and length normalisation.
- [ToxiGen](/papers/2203.09509): ALICE, a classifier-weighted beam score.
- [EHRSQL](/papers/2301.07695): a beam of 5 and an entropy-based refusal rule.
- [Ad Headline Generation using Self-Critical Masked Language Model](/papers/2607.06818): position-dependent length normalisation in beam ranking.
- [Prompting Is Programming: A Query Language for Large Language Models](/papers/2212.06094): LMQL, with a `beam(n)` decoder and token masks from output constraints.
- [Neural Grammatical Error Correction for Romanian](/papers/2604.23627): beam of 8 with optional language-model re-ranking and a length penalty in the code.