Definition
Beam search is an approximate search for the most probable output of an autoregressive model. At each step it extends each of the hypotheses it is keeping (the beam) by every vocabulary token, scores the candidates by cumulative log-probability, and keeps the best . Hypotheses that emit </s> are set aside as finished. is greedy decoding; would be exact search.
An encoder–decoder (see Sequence-to-sequence (Seq2Seq)) defines , but finding the best exactly means searching 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
- the beam after step : the best alive prefixes;
- cumulative log-probability. It only decreases as grows, which is what biases search toward short outputs
- beam width; candidates per step
- the vocabulary, size , including </s>
One step, as implemented in fairseq / Hugging Face style decoders
- 1Run the model once on all alive prefixes (one batched forward step) to get , shape .
- 2Add each row to its prefix score and flatten to candidates; take the top (so that at least do not end in </s>).
- 3Walk down the ranking: a candidate ending in </s> that ranks inside the top becomes a finished hypothesis; the first others become the new beam.
- 4Stop when hypotheses have finished (Hugging Face
early_stopping=True) or at a maximum length, then return the finished hypothesis with the best normalised score.
Cost: steps of model evaluations each, plus a top- over scores, i.e. for scoring on top of times the model cost of greedy decoding. Memory grows by the same factor , 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 , 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 , found best on a development set, then settled on the penalty below plus a coverage term:
- strength of the length penalty; gives raw log-probability, larger favours longer outputs
- a constant that softens the penalty for very short outputs; at
- attention weight of target word on source word ; penalises source words that received little total attention
- coverage strength; 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 gave 31.4, with a wide range of values close to the best. In Hugging Face generate, length_penalty is the exponent of a plain divisor (default 1.0); positive values favour longer outputs.
At a glance
- Finds
- an approximate ; greedy is
- Cost
- scoring; 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
- with or GNMT's
- Stops
- after 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
Worked example: the figure's search with B = 2
The toy model starts with , , , . 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 .
| step | candidates | kept beam (log P) | finished | best pruned |
|---|---|---|---|---|
| 1 | 4 | a , the | – | </s> (rank 3) |
| 2 | 6 | the cat , a cat | – | a big / a dog |
| 3 | 6 | the cat sat , a cat sat | – | the cat </s> |
| 4 | 4 | the cat sat down , a cat sat down | the cat sat </s> | a cat sat </s> (rank 3) |
| 5 | 2 | – | the cat sat down </s> | stop: 2 finished |
Scoring the two finished hypotheses
- 1Raw: , so B = 2 returns "the cat sat </s>" (), already better than greedy's 0.0505.
- 2 with : versus , so the longer "the cat sat down </s>" wins.
- 3GNMT with : and , giving and ; "the cat sat </s>" wins again. The two normalisations disagree.
- 4Exact search (raw) finds "</s>" with : the empty output is the model's single most probable sequence. Under GNMT it loses to "the cat sat </s>" as soon as , i.e. .
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.
1import torch23@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 hypothesis8 finished = [] # (normalised score, token list)9 lp = lambda n: ((5 + n) / 6) ** alpha # GNMT length penalty10 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 counts20 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 break26 if len(finished) >= B or not new_seqs: # early stopping: B finished27 break28 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 here30 if not finished: # hit max_len: fall back to alive hypotheses31 finished = [(s / lp(len(q) - 1), q.tolist()[1:]) for s, q in zip(scores.tolist(), seqs)]32 return max(finished)3334# Hugging Face: the same search, batched, with KV-cache reordering built in35from transformers import AutoTokenizer, AutoModelForSeq2SeqLM36name = "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 firstUse 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
- − 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 best prefixes by cumulative ; expand by all tokens; move </s> hypotheses to a finished list. is greedy.
- ✓Cost scoring and the model and cache memory of greedy decoding.
- ✓Compare finished hypotheses with : or GNMT's ; and 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.