Beam Search & Structured Decoding

Why It Matters for Modern Models

Beam search is the usual decoder for tasks with one intended output, such as machine translation; the sequence-to-sequence translation model of Sutskever et al. (2014) and Google's GNMT system (Wu et al., 2016) both used it.
It makes the trade-off between search and cost explicit: greedy decoding keeps one hypothesis and can miss a better sequence whose first token looked worse, while a beam of B hypotheses costs about B times as much computation per step.
Searching harder for the most probable sequence does not always give better text. In translation, quality eventually fell as the beam grew wider, mainly because the outputs became shorter (Koehn & Knowles, 2017); in open-ended generation, maximizing likelihood gives bland and repetitive text (Holtzman et al., 2020).

Questions to Think About

Why can a wider beam give worse translations, and how is that connected to models that assign high probability to short or even empty outputs (Koehn & Knowles, 2017; Stahlberg & Byrne, 2019)?
How does length normalization change which finished sequence wins, and what does the exponent α trade off?

Core Math

Key Equation

\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i \mid y_{<i}, x)

Beam search looks for the most probable output sequence $y$ for an input $x$ while keeping only the $B$ best partial sequences (the beam) at each step. A partial sequence is scored by its log-probability:

\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i \mid y_{<i}, x)

At step $t$ , every sequence in the beam is extended by every token in the vocabulary, and the $B$ highest-scoring extensions are kept. With $B = 1$ this is greedy decoding; as $B$ grows it approaches an exact search for the most probable sequence.

Each extra token adds a negative log-probability, so the raw score favours short outputs. Length normalization divides by a power of the length $T$ when comparing finished sequences:

\text{score}_{\text{norm}}(y_{1:T}) = \frac{1}{T^\alpha} \sum_{i=1}^{T} \log p(y_i \mid y_{<i}, x), \quad 0 \le \alpha \le 1

Google's GNMT system used a smoothed version, dividing by $\big((5 + T)/6\big)^\alpha$ (Wu et al., 2016). Diverse beam search splits the beam into groups and penalizes a group for choosing tokens that earlier groups chose, so that the returned sequences differ from one another (Vijayakumar et al., 2018).