Beam search

Keep the B highest-scoring partial sequences at every decoding step instead of only the best one. Cost O(T·B·V); needs length normalisation, because raw log-probability favours short outputs, and wider beams are not always better.

12 min read1075 wordscore1 viewsupdated 2026-10-12

Definition

Beam search is an approximate search for the most probable output Y^=arg⁡max⁡Ylog⁡P(Y∣X)\hat Y=\arg\max_Y \log P(Y\mid X) of an autoregressive model. At each step it extends each of the BB hypotheses it is keeping (the beam) by every vocabulary token, scores the B⋅VB\cdot V candidates by cumulative log-probability, and keeps the best BB. Hypotheses that emit </s> are set aside as finished. B=1B=1 is greedy decoding; B=∞B=\infty would be exact search.

An encoder–decoder (see Sequence-to-sequence (Seq2Seq)) defines P(Y∣X)=∏tP(yt∣y<t,X)P(Y\mid X)=\prod_t P(y_t\mid y_{<t},X), but finding the best YY exactly means searching VTV^T sequences, and an RNN or Transformer state does not factor in a way dynamic programming can exploit. Greedy decoding commits to the locally best token and can never undo it: a token with probability 0.45 that leads only to weak continuations beats one with probability 0.40 that leads to a strong one. Beam search keeps a few alternatives alive long enough for that difference to show.

The method comes from speech recognition: Lowerre's Harpy system (CMU, 1976) pruned its search to a beam of near-best paths. It became the standard decoder for neural MT with Sutskever, Vinyals and Le (2014), who noted that a beam of 2 already gave most of the benefit, and Bahdanau et al. (2015). The GenAI article Greedy & beam search covers it from the LLM side; CTC models use a variant, prefix beam search, that merges paths collapsing to the same labelling (see Connectionist Temporal Classification).

The algorithm and its score

Ht=top-B⁡(Y, w) : Y∈Ht−1, w∈V[ s(Y)+log⁡P(w∣Y,X) ],s(Y)=∑t=1∣Y∣log⁡P(yt∣y<t,X)\mathcal H_t=\operatorname*{top\text{-}B}_{(Y,\,w)\,:\,Y\in\mathcal H_{t-1},\,w\in\mathcal V}\Big[\,s(Y)+\log P(w\mid Y,X)\,\Big],\qquad s(Y)=\sum_{t=1}^{|Y|}\log P(y_t\mid y_{<t},X)
Ht\mathcal H_t
the beam after step tt: the BB best alive prefixes; H0={⟨s⟩}\mathcal H_0=\{\langle s\rangle\}
s(Y)s(Y)
cumulative log-probability. It only decreases as YY grows, which is what biases search toward short outputs
BB
beam width; candidates per step ≤B⋅V\le B\cdot V
V\mathcal V
the vocabulary, size VV, including </s>

One step, as implemented in fairseq / Hugging Face style decoders

  1. 1Run the model once on all BB alive prefixes (one batched forward step) to get log⁡P(⋅∣Y)\log P(\cdot\mid Y), shape B×VB\times V.
  2. 2Add each row to its prefix score and flatten to B⋅VB\cdot V candidates; take the top 2B2B (so that at least BB do not end in </s>).
  3. 3Walk down the ranking: a candidate ending in </s> that ranks inside the top BB becomes a finished hypothesis; the first BB others become the new beam.
  4. 4Stop when BB hypotheses have finished (Hugging Face early_stopping=True) or at a maximum length, then return the finished hypothesis with the best normalised score.

Cost: TT steps of BB model evaluations each, plus a top-kk over B⋅VB\cdot V scores, i.e. O(T⋅B⋅V)O(T\cdot B\cdot V) for scoring on top of BB times the model cost of greedy decoding. Memory grows by the same factor BB, because every hypothesis carries its own RNN state or Transformer key/value cache, which must be reordered by parent index after every step.

Length normalisation

Every token adds a negative log⁡P\log P, so with raw scores a finished short hypothesis usually beats a longer one, and the shortest finished hypothesis of all is </s> at step 1. The fix is to compare finished hypotheses by a length-normalised score. Wu et al. (2016, GNMT) first divided by ∣Y∣α|Y|^\alpha, found α∈[0.6,0.7]\alpha\in[0.6,0.7] best on a development set, then settled on the penalty below plus a coverage term:

score(Y,X)=log⁡P(Y∣X)lp(Y)+cp(X;Y),lp(Y)=(5+∣Y∣)α(5+1)α,cp(X;Y)=β∑i=1∣X∣log⁡(min⁡(∑j=1∣Y∣pi,j, 1))\mathrm{score}(Y,X)=\frac{\log P(Y\mid X)}{lp(Y)}+cp(X;Y),\qquad lp(Y)=\frac{(5+|Y|)^{\alpha}}{(5+1)^{\alpha}},\qquad cp(X;Y)=\beta\sum_{i=1}^{|X|}\log\Big(\min\Big(\sum_{j=1}^{|Y|}p_{i,j},\,1\Big)\Big)
α\alpha
strength of the length penalty; α=0\alpha=0 gives raw log-probability, larger α\alpha favours longer outputs
55
a constant that softens the penalty for very short outputs; lp=1lp=1 at ∣Y∣=1|Y|=1
pi,jp_{i,j}
attention weight of target word jj on source word ii; cpcp penalises source words that received little total attention
β\beta
coverage strength; α=β=0\alpha=\beta=0 falls back to plain beam search by probability

On WMT'14 En→Fr (GNMT Table 2, a maximum-likelihood model without RL refinement) plain beam search scored 30.3 BLEU on the development set and α=0.2,β=0.2\alpha=0.2,\beta=0.2 gave 31.4, with a wide range of values close to the best. In Hugging Face generate, length_penalty is the exponent α\alpha of a plain ∣Y∣α|Y|^\alpha divisor (default 1.0); positive values favour longer outputs.

At a glance

Finds
an approximate arg⁡max⁡YP(Y∣X)\arg\max_Y P(Y\mid X); greedy is B=1B=1
Cost
O(T⋅B⋅V)O(T\cdot B\cdot V) scoring; B×B\times the model compute and KV/state memory of greedy
Typical B
4–12 in MT and summarisation (GNMT kept 8–12 and found 2–4 only slightly worse)
Score
log⁡P(Y∣X)/lp(Y)\log P(Y\mid X)/lp(Y) with ∣Y∣α|Y|^\alpha or GNMT's ((5+∣Y∣)/6)α((5+|Y|)/6)^\alpha
Stops
after BB finished hypotheses or at a maximum length
Known failure
wider beams return shorter, worse outputs (the beam search curse)
Not for
open-ended chat and story generation, where sampling (top-k, top-p) gives less repetitive text
beam width B = 2 · |V| = 10 · step 5/5 · candidates scored 22 · stopped: B finishedt = 1t = 2t = 3t = 4t = 5t = 6<s></s>−2.30cat−3.00a−0.80the−0.92big−1.91dog−1.91cat−1.27cat−1.88</s>−2.66ran−2.88sat−1.87sat−2.48</s>−2.99</s>−2.38down−2.79down−3.39</s>−3.39</s>−2.79finished hypothesis|Y|log Plpscore▸ the cat sat </s>4−2.381.000−2.3816 the cat sat down </s>5−2.791.000−2.7871beam result: the cat sat </s> (p = 0.0924)exhaustive best (37 sequences): </s> (p = 0.1000) · search error■ kept ■ </s> ■ pruned
score:
fig.Beam search on a toy bigram language model over 10 tokens. Each column is a step; blue boxes are the kept beam, green ones finished at that step, grey dashed ones the best pruned candidates, each with its cumulative log-probability. With raw scores, greedy (B = 1) returns 'a cat sat </s>' (p = 0.0505); B = 2 scores 22 candidates and returns 'the cat sat </s>' (p = 0.0924); from B = 3 the beam lets the empty output '</s>' (p = 0.1000) finish at step 1, and it wins: it is also the exact maximum over all 37 sequences. Switch to the GNMT score: any α between 0.083 and 1.49 makes 'the cat sat </s>' the exact best, and every B ≥ 2 finds it. With ÷|Y|^α at α = 1 the exact best is 'the cat sat down </s>'; B = 2 finds it, but B = 3 stops after three hypotheses finish at step 4 and misses it (search error).

Worked example: the figure's search with B = 2

The toy model starts with P(a)=0.45P(a)=0.45, P(the)=0.40P(\text{the})=0.40, P(⟨/s⟩)=0.10P(\langle/s\rangle)=0.10, P(cat)=0.05P(\text{cat})=0.05. After "a" the next word is nearly uniform (cat 0.34, dog 0.33, big 0.33); after "the" it is confident (cat 0.70). Greedy takes "a" and ends with p=0.45⋅0.34⋅0.55⋅0.6=0.0505p=0.45\cdot0.34\cdot0.55\cdot0.6=0.0505.

stepcandidateskept beam (log P)finishedbest pruned
14a −0.799-0.799, the −0.916-0.916–</s> −2.303-2.303 (rank 3)
26the cat −1.273-1.273, a cat −1.877-1.877–a big / a dog −1.907-1.907
36the cat sat −1.871-1.871, a cat sat −2.475-2.475–the cat </s> −2.659-2.659
44the cat sat down −2.787-2.787, a cat sat down −3.391-3.391the cat sat </s> −2.382-2.382a cat sat </s> −2.986-2.986 (rank 3)
52–the cat sat down </s> −2.787-2.787stop: 2 finished
Beam B = 2, raw log-probability (every number from the figure's lib, run in Node)

Scoring the two finished hypotheses

  1. 1Raw: −2.382>−2.787-2.382>-2.787, so B = 2 returns "the cat sat </s>" (p=0.0924p=0.0924), already better than greedy's 0.0505.
  2. 2÷∣Y∣α\div|Y|^\alpha with α=1\alpha=1: −2.382/4=−0.595-2.382/4=-0.595 versus −2.787/5=−0.557-2.787/5=-0.557, so the longer "the cat sat down </s>" wins.
  3. 3GNMT with α=1\alpha=1: lp(4)=9/6=1.5lp(4)=9/6=1.5 and lp(5)=10/6=1.667lp(5)=10/6=1.667, giving −1.588-1.588 and −1.672-1.672; "the cat sat </s>" wins again. The two normalisations disagree.
  4. 4Exact search (raw) finds "</s>" with log⁡0.1=−2.303\log 0.1=-2.303: the empty output is the model's single most probable sequence. Under GNMT it loses to "the cat sat </s>" as soon as 1.5α>2.382/2.3031.5^\alpha>2.382/2.303, i.e. α>0.083\alpha>0.083.

The beam search curse

If search were the only problem, a wider beam would always help. In practice it does not. Koehn and Knowles (2017, Figure 10) decoded Edinburgh's WMT 2016 systems with beams from 1 to 1000: in almost all of 8 language pairs BLEU peaks at a moderate width (from 4 for Czech–English to around 30 for English–Romanian) and then falls, mainly because wider beams find shorter translations. Length normalisation moves the optimum to 30–50 and softens the drop, but does not remove it. Stahlberg and Byrne (2019) ran exact search on a Transformer and found that for more than 50% of sentences the model's global best output is the empty translation.

python
1import torch
2
3@torch.no_grad()
4def beam_search(step_fn, bos, eos, B=4, max_len=50, alpha=0.6):
5 """step_fn(seqs: LongTensor (b, t)) -> log-probs (b, V) of the next token."""
6 seqs = torch.tensor([[bos]])
7 scores = torch.zeros(1) # cumulative log P of each alive hypothesis
8 finished = [] # (normalised score, token list)
9 lp = lambda n: ((5 + n) / 6) ** alpha # GNMT length penalty
10 for t in range(1, max_len + 1):
11 logp = step_fn(seqs) # (b, V)
12 V = logp.size(-1)
13 cand = (scores[:, None] + logp).flatten() # (b*V,)
14 top, idx = cand.topk(min(2 * B, cand.numel()))
15 new_seqs, new_scores = [], []
16 for rank, (s, j) in enumerate(zip(top.tolist(), idx.tolist())):
17 b, k = divmod(j, V)
18 if k == eos:
19 if rank < B: # only EOS inside the top B counts
20 finished.append((s / lp(t), seqs[b].tolist()[1:] + [eos]))
21 else:
22 new_seqs.append(torch.cat([seqs[b], torch.tensor([k])]))
23 new_scores.append(s)
24 if len(new_seqs) == B:
25 break
26 if len(finished) >= B or not new_seqs: # early stopping: B finished
27 break
28 seqs, scores = torch.stack(new_seqs), torch.tensor(new_scores)
29 # a real decoder would also reorder its hidden state / KV cache by parent index here
30 if not finished: # hit max_len: fall back to alive hypotheses
31 finished = [(s / lp(len(q) - 1), q.tolist()[1:]) for s, q in zip(scores.tolist(), seqs)]
32 return max(finished)
33
34# Hugging Face: the same search, batched, with KV-cache reordering built in
35from transformers import AutoTokenizer, AutoModelForSeq2SeqLM
36name = "Helsinki-NLP/opus-mt-en-de"
37tok, model = AutoTokenizer.from_pretrained(name), AutoModelForSeq2SeqLM.from_pretrained(name)
38batch = tok(["The cat sat on the mat."], return_tensors="pt")
39out = model.generate(**batch, num_beams=5, length_penalty=1.0, early_stopping=True,
40 max_new_tokens=40, num_return_sequences=3,
41 output_scores=True, return_dict_in_generate=True)
42print(tok.batch_decode(out.sequences, skip_special_tokens=True))
43print(out.sequences_scores) # sum of log-probs / length**length_penalty, best first
Beam search from scratch (single input, GNMT length penalty), then the same with Hugging Face generate

Use when

  • +Finds higher-probability outputs than greedy for a small constant factor of compute
  • +Simple, deterministic, and easy to batch; standard in MT, ASR and summarisation
  • +Returns an n-best list for reranking or minimum-Bayes-risk decoding
  • +Score is easy to extend: length, coverage, LM fusion, constraints

Avoid when

  • −B×B\times compute and KV/state memory; strictly sequential over time
  • −Not exact: can miss the best output, and better search can give worse outputs (beam search curse)
  • −Raw log-probability favours short or empty outputs; needs a tuned length penalty
  • −Low diversity: the n-best list often differs only in a word or two

Check yourself

A model's vocabulary has 32 000 tokens. With beam width 5 and 40 output steps, roughly how many candidate continuations does beam search score in total?

Check yourself

Increasing the beam width from 5 to 100 on an NMT system lowers BLEU and the outputs get shorter. What is the most likely explanation?

Remember

  • ✓Keep the BB best prefixes by cumulative log⁡P\log P; expand by all VV tokens; move </s> hypotheses to a finished list. B=1B=1 is greedy.
  • ✓Cost O(T⋅B⋅V)O(T\cdot B\cdot V) scoring and B×B\times the model and cache memory of greedy decoding.
  • ✓Compare finished hypotheses with log⁡P/lp(Y)\log P/lp(Y): ∣Y∣α|Y|^\alpha or GNMT's ((5+∣Y∣)/6)α((5+|Y|)/6)^\alpha; α\alpha and BB are tuned together.
  • ✓Wider is not always better: maximum-likelihood models often prefer short or empty outputs, so better search can mean worse output.
  • ✓In practice: model.generate(num_beams=4..8, length_penalty=..., early_stopping=True); use sampling for open-ended text.
← back to Deep Learning roadmap