Beam search

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 2603.01786 §3.4. With W = 1 the rule is greedy decoding 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 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 2203.16804 eq. 9 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 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.

Diverse beams for a candidate pool

BRIO uses a diverse beam search to write 16 summaries for each training article, then ranks them by ROUGE against the reference 2203.16804 §3. The paper gives the number of candidates but not the beam width or the diversity setting 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 2203.16804 §5.5.

Classifier-weighted beam score

ToxiGen 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 2203.09509 §3.3 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 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 2203.09509 §3.3.

Beam over a learned goal-seeking policy

Learning Shortest Paths with Generative Flow Networks 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 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 2603.01786 §4.2 2603.01786 tab. 1. Table 1 leaves its "x" entries undefined, and reported lengths depend on both the width and the step budget 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 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.

Beam as a decoder under token masks

LMQL is a query language whose constraints, such as a word limit or a stop phrase, become a token mask at each decoding step 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 2212.06094 §4. The reported cost results use argmax and sample, not beam 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 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.

Length normalisation

BRIO 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 2203.16804 eq. 9 2203.16804 app. B.

The ad headline paper 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 2607.06818 eq. 10 2607.06818 §3.4. Its ablation removes beam normalisation and post-processing together. ROUGE-L falls from 6.33 to 5.37 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 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.

Beam-derived confidence

EHRSQL decodes with 5 beams and a length penalty of 1.0 2301.07695 app. G. Its refusal rule uses the largest per-token entropy over the decoding steps, and refuses above a threshold 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.

When to use which

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 2203.16804 eq. 9.

# 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 2203.09509 eq. 1. For a diverse pool, the candidate step uses a diverse beam search rather than the plain one above 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 2604.23627 §4.1. For token masks, the paper's masked decoding loop applies the mask to one hole at a time 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 2203.16804 tab. 5. The translation card reports one width only, so it cannot show a trend 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 2212.06094 §4. The released code's beam is a token-level search Prompting Is Programming card, so a result from one should not be assumed for the other.

Papers

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