# 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.

Source: https://www.mlfoundry.in/learn/beam-search  
Section: Deep Learning › Recurrent Neural Networks and Sequence Models  
Level: core · 12 min read · updated 2026-10-12

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

An encoder–decoder (see **Sequence-to-sequence (Seq2Seq)**) defines $P(Y\mid X)=\prod_t P(y_t\mid y_{<t},X)$, but finding the best $Y$ exactly means searching $V^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

$$
\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)
$$

- $\mathcal H_t$: the beam after step $t$: the $B$ best alive prefixes; $\mathcal H_0=\{\langle s\rangle\}$
- $s(Y)$: cumulative log-probability. It only decreases as $Y$ grows, which is what biases search toward short outputs
- $B$: beam width; candidates per step $\le B\cdot V$
- $\mathcal V$: the vocabulary, size $V$, including </s>

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

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

Cost: $T$ steps of $B$ model evaluations each, plus a top-$k$ over $B\cdot V$ scores, i.e. $O(T\cdot B\cdot V)$ for scoring on top of $B$ times the model cost of greedy decoding. Memory grows by the same factor $B$, 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$, 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|^\alpha$, found $\alpha\in[0.6,0.7]$ best on a development set, then settled on the penalty below plus a coverage term:

$$
\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; $\alpha=0$ gives raw log-probability, larger $\alpha$ favours longer outputs
- $5$: a constant that softens the penalty for very short outputs; $lp=1$ at $|Y|=1$
- $p_{i,j}$: attention weight of target word $j$ on source word $i$; $cp$ penalises source words that received little total attention
- $\beta$: coverage strength; $\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 $\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|^\alpha$ divisor (default 1.0); positive values favour longer outputs.

**At a glance**

- **Finds:** an approximate $\arg\max_Y P(Y\mid X)$; greedy is $B=1$
- **Cost:** $O(T\cdot B\cdot V)$ scoring; $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\mid X)/lp(Y)$ with $|Y|^\alpha$ or GNMT's $((5+|Y|)/6)^\alpha$
- **Stops:** after $B$ 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

> Figure: 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.45$, $P(\text{the})=0.40$, $P(\langle/s\rangle)=0.10$, $P(\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\cdot0.34\cdot0.55\cdot0.6=0.0505$.

Beam B = 2, raw log-probability (every number from the figure's lib, run in Node)

| step | candidates | kept beam (log P) | finished | best pruned |
| --- | --- | --- | --- | --- |
| 1 | 4 | a $-0.799$, the $-0.916$ | – | </s> $-2.303$ (rank 3) |
| 2 | 6 | the cat $-1.273$, a cat $-1.877$ | – | a big / a dog $-1.907$ |
| 3 | 6 | the cat sat $-1.871$, a cat sat $-2.475$ | – | the cat </s> $-2.659$ |
| 4 | 4 | the cat sat down $-2.787$, a cat sat down $-3.391$ | the cat sat </s> $-2.382$ | a cat sat </s> $-2.986$ (rank 3) |
| 5 | 2 | – | the cat sat down </s> $-2.787$ | stop: 2 finished |

**Scoring the two finished hypotheses**

1. Raw: $-2.382>-2.787$, so B = 2 returns "the cat sat </s>" ($p=0.0924$), already better than greedy's 0.0505.
2. $\div|Y|^\alpha$ with $\alpha=1$: $-2.382/4=-0.595$ versus $-2.787/5=-0.557$, so the longer "the cat sat down </s>" wins.
3. GNMT with $\alpha=1$: $lp(4)=9/6=1.5$ and $lp(5)=10/6=1.667$, giving $-1.588$ and $-1.672$; "the cat sat </s>" wins again. The two normalisations disagree.
4. Exact search (raw) finds "</s>" with $\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^\alpha>2.382/2.303$, i.e. $\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.

> **Search errors that help:** The toy reproduces both effects. Raw-score B = 2 commits a search error (it misses "</s>") and that error is what makes its output useful; B = 3 searches better and returns nothing. The model, not the search, is wrong: maximum-likelihood training spreads probability over many long outputs, each individually less likely than a degenerate short one. Beam search with a moderate width and length normalisation works because it is a biased approximation, and Meister, Cotterell and Vieira (2020) argue that this bias toward evenly spread surprisal is part of what we actually want.

```python
import torch

@torch.no_grad()
def beam_search(step_fn, bos, eos, B=4, max_len=50, alpha=0.6):
    """step_fn(seqs: LongTensor (b, t)) -> log-probs (b, V) of the next token."""
    seqs = torch.tensor([[bos]])
    scores = torch.zeros(1)                       # cumulative log P of each alive hypothesis
    finished = []                                 # (normalised score, token list)
    lp = lambda n: ((5 + n) / 6) ** alpha         # GNMT length penalty
    for t in range(1, max_len + 1):
        logp = step_fn(seqs)                      # (b, V)
        V = logp.size(-1)
        cand = (scores[:, None] + logp).flatten() # (b*V,)
        top, idx = cand.topk(min(2 * B, cand.numel()))
        new_seqs, new_scores = [], []
        for rank, (s, j) in enumerate(zip(top.tolist(), idx.tolist())):
            b, k = divmod(j, V)
            if k == eos:
                if rank < B:                      # only EOS inside the top B counts
                    finished.append((s / lp(t), seqs[b].tolist()[1:] + [eos]))
            else:
                new_seqs.append(torch.cat([seqs[b], torch.tensor([k])]))
                new_scores.append(s)
            if len(new_seqs) == B:
                break
        if len(finished) >= B or not new_seqs:   # early stopping: B finished
            break
        seqs, scores = torch.stack(new_seqs), torch.tensor(new_scores)
        # a real decoder would also reorder its hidden state / KV cache by parent index here
    if not finished:                              # hit max_len: fall back to alive hypotheses
        finished = [(s / lp(len(q) - 1), q.tolist()[1:]) for s, q in zip(scores.tolist(), seqs)]
    return max(finished)

# Hugging Face: the same search, batched, with KV-cache reordering built in
from transformers import AutoTokenizer, AutoModelForSeq2SeqLM
name = "Helsinki-NLP/opus-mt-en-de"
tok, model = AutoTokenizer.from_pretrained(name), AutoModelForSeq2SeqLM.from_pretrained(name)
batch = tok(["The cat sat on the mat."], return_tensors="pt")
out = model.generate(**batch, num_beams=5, length_penalty=1.0, early_stopping=True,
                     max_new_tokens=40, num_return_sequences=3,
                     output_scores=True, return_dict_in_generate=True)
print(tok.batch_decode(out.sequences, skip_special_tokens=True))
print(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

> **Early stopping interacts with normalisation:** "Stop when $B$ hypotheses have finished" is only safe if no alive hypothesis could still overtake them. With a length bonus a longer alive hypothesis can: in the figure, $\div|Y|$ with B = 3 stops at step 4 and returns a score of $-0.595$, while the alive "the cat sat down" would have finished at $-0.557$. Hugging Face's `early_stopping=False` uses a heuristic bound and `"never"` keeps going until no alive beam can improve. Always tune `num_beams` and `length_penalty` together on a development set.

> **Common add-ons:** `no_repeat_ngram_size` bans repeated $n$-grams (useful in summarisation), diverse beam search splits the beam into groups with a diversity penalty, constrained beam search forces given phrases, and shallow fusion adds $\lambda\log P_{\text{LM}}$ from an external language model. All of them change the score inside the same loop. For open-ended generation prefer sampling; beams make text repetitive and generic.

**Strengths**

- 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

**Limitations**

- $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

**Question:** 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?

- A. 40 × 5 = 200
- B. 40 × 5 × 32 000 = 6.4 million
- C. 32 000⁴⁰
- D. 5 × 32 000 = 160 000

**Answer:** B. 40 × 5 × 32 000 = 6.4 million — Each step expands every one of the $B=5$ hypotheses by all $V$ tokens, giving $B\cdot V=160\,000$ scores per step, over $T=40$ steps: $O(T\cdot B\cdot V)=6.4$ million. The model itself runs only $T\cdot B=200$ times (as 40 batched steps).

**Question:** 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?

- A. A bug: a wider beam can only find lower-probability outputs
- B. The model assigns high probability to short outputs, and the wider beam finds them; the search is better, the model is wrong
- C. Length normalisation always hurts at large beam widths
- D. Wider beams use a different softmax temperature

**Answer:** B. The model assigns high probability to short outputs, and the wider beam finds them; the search is better, the model is wrong — A wider beam finds outputs with higher model score, and under raw log-probability short ones have high scores. Koehn and Knowles (2017) traced the drop to shorter translations; Stahlberg and Byrne (2019) showed the exact best is often empty. Length normalisation helps but does not fully fix it.

**Key points**

- Keep the $B$ best prefixes by cumulative $\log P$; expand by all $V$ tokens; move </s> hypotheses to a finished list. $B=1$ is greedy.
- Cost $O(T\cdot B\cdot V)$ scoring and $B\times$ the model and cache memory of greedy decoding.
- Compare finished hypotheses with $\log P/lp(Y)$: $|Y|^\alpha$ or GNMT's $((5+|Y|)/6)^\alpha$; $\alpha$ and $B$ 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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
