Beam search, and why chat models dropped it

The objective#

Beam search approximates

$$ \hat{y} = \arg\max_{y} \ \log P(y \mid x) = \arg\max_{y} \sum_{t=1}^{|y|} \log P(y_t \mid y_{<t}, x) $$

Exact search is intractable — $|V|^{T}$ sequences — so the beam keeps the top $k$ prefixes by partial score at each step. It offers no optimality guarantee: a prefix that ranks $k+1$ at step $t$ is discarded permanently, however good its continuations would have been.

Length normalisation#

Since $\log P \le 0$ per token, raw scores decrease monotonically with length and the search is biased toward short outputs. Two standard corrections.

Simple normalisation, and what transformers implements:

$$ s(y) = \frac{\log P(y \mid x)}{|y|^{\alpha}} $$

The GNMT form (Wu et al., 2016, arxiv.org/abs/1609.08144):

$$ s(y) = \frac{\log P(y \mid x)}{\mathrm{lp}(y)}, \qquad \mathrm{lp}(y) = \frac{(5 + |y|)^{\alpha}}{(5 + 1)^{\alpha}} $$

with $\alpha \approx 0.6$ to $0.7$ in their experiments. The additive constant softens the correction on very short outputs.

The beam search curse#

Koehn and Knowles, Six Challenges for Neural Machine Translation, 2017 (arxiv.org/abs/1706.03872) report BLEU peaking at small beam widths. It degrades as the beam grows. Better search, worse output.

Stahlberg and Byrne, On NMT Search Errors and Model Errors: Cat Got Your Tongue?, EMNLP 2019 (arxiv.org/abs/1908.10090) resolved this with exact search over a Transformer base model on the WMT15 English-German test set. For more than half the sentences, the model's global best score belongs to the empty translation.

Read that again. The mode of the model's distribution is often the empty string. Beam search produces usable output partly because it fails to find the optimum, and small beams fail in a direction that happens to be helpful. Any argument of the form "our decoder finds higher-probability sequences, therefore it is better" is refuted by this result.

Degeneration in open-ended generation#

Holtzman et al., ICLR 2020 (arxiv.org/abs/1904.09751) show the same phenomenon outside translation. Beam-search continuations have per-token probabilities far higher and far less variable than human text, and they repeat.

The framing that stuck: human language is not maximum-probability language. Speakers distribute information roughly evenly rather than always choosing the most predictable word, which is the same observation that motivates typical sampling.

Minimum Bayes risk decoding#

If the mode is a bad estimate, target expected utility instead:

$$ \hat{y} = \arg\max_{y \in \mathcal{Y}} \ \mathbb{E}{y' \sim P(\cdot \mid x)} \big[ u(y, y') \big] \approx \arg\max{y \in \mathcal{Y}} \ \frac{1}{N} \sum_{n=1}^{N} u(y, y^{(n)}) $$

Sample $N$ candidates, score every candidate against every other with a utility $u$ (BLEU, COMET, a learned metric), and return the most "central" one. Eikema and Aziz, Is MAP Decoding All You Need?, 2020 (arxiv.org/abs/2005.10283) show that MBR avoids the pathologies of mode-seeking search. With a strong neural utility it now leads most machine-translation quality tables.

Cost is $O(N^2)$ utility evaluations. The idea reappears in LLM work under other names: self-consistency for chain-of-thought is MBR with exact-match utility over sampled reasoning paths.

Diverse variants#

• Diverse beam search (Vijayakumar et al., 2016, arxiv.org/abs/1610.02424) partitions beams into groups. Each group penalises tokens already chosen by earlier groups, giving genuinely different candidates rather than $k$ near-duplicates. num_beam_groups and diversity_penalty in transformers.
• Constrained beam search forces or forbids specified sequences, used for terminology constraints in translation. Related to but weaker than grammar-constrained decoding.
• Contrastive search (Su et al., 2022, arxiv.org/abs/2202.06417) picks among top-$k$ candidates by trading model confidence against similarity to already-generated hidden states. penalty_alpha in transformers. A deterministic decoder that avoids degeneration without sampling — genuinely useful and under-used.

Why LLM serving stacks deprioritised it#

Four reasons, in descending order of importance.

1. Open-ended generation does not want the mode, per Holtzman and Stahlberg.
2. Streaming is incompatible with a search that can retract a prefix.
3. $k$ concurrent KV caches per request, against a scheduler already memory-bound.
4. RLHF and instruction tuning sharpen the distribution considerably, which shrinks the gap between greedy and beam and removes most of the remaining benefit.

vLLM implements beam search outside the main sampling path (LLM.beam_search) precisely because it does not fit the continuous-batching model. Its presence is for translation-style workloads, not chat.

Papers#

• Wu et al., Google's Neural Machine Translation System, 2016 — arxiv.org/abs/1609.08144
• Vijayakumar et al., Diverse Beam Search, 2016 — arxiv.org/abs/1610.02424
• Koehn and Knowles, Six Challenges for Neural Machine Translation, 2017 — arxiv.org/abs/1706.03872
• Stahlberg and Byrne, On NMT Search Errors and Model Errors, EMNLP 2019 — arxiv.org/abs/1908.10090
• Eikema and Aziz, Is MAP Decoding All You Need?, 2020 — arxiv.org/abs/2005.10283
• Su et al., A Contrastive Framework for Neural Text Generation, 2022 — arxiv.org/abs/2202.06417

What to learn next#

• Constrained decoding and grammars — forcing a shape on the output without searching for it.
• Speculative decoding — running several candidate tokens at once, for speed rather than quality.
• Temperature and sampling — what chat models use instead.