Beam Search Decoding

A model that generates a sequence one step at a time — words in a translation, moves in a forecast path — has to choose an output at every step, and each choice narrows what can come after it. Always taking the single highest-probability next step, called greedy decoding, is fast but shortsighted: a slightly lower-probability first step might open the door to a much better overall sequence, while the greedy choice locks you into a mediocre one. The question decoding has to answer is how much of that future to look at before committing.

The analogy: exploring a maze with a flashlight

Greedy decoding is like walking through a maze and, at every junction, taking whichever corridor looks brightest right now, never glancing ahead. You might confidently walk into a dead end that a slightly darker corridor would have avoided. Trying every possible full path guarantees the best route but is far too slow. Beam search is the middle ground: at every junction, keep a small fixed number of your most promising partial paths alive, explore one step further from each, and prune back to that same number of best candidates. You never see the whole maze, but you also never commit to one path before comparing it against a handful of live alternatives.

The mechanics: keeping a beam of candidates

Beam search keeps a beam width $k$ of partial sequences at every step. At each step, for every one of the $k$ current partial sequences, the model scores every possible next token, producing many candidate continuations; only the $k$ candidates with the highest total sequence probability survive to the next step. Sequence probability is the product of per-step probabilities, which is normally handled as a sum of log-probabilities for numerical stability:

$$\log P(y_1, \dots, y_T) = \sum_{t=1}^{T} \log P(y_t \mid y_1, \dots, y_{t-1})$$

In words: the log-probability of a full generated sequence is just the sum of the log-probabilities of each step, given everything generated so far — summing logs instead of multiplying raw probabilities avoids numbers shrinking to zero over long sequences. Greedy decoding is the special case $k=1$; exhaustive search is the (usually infeasible) case where $k$ equals every possible sequence.

Worked example 1: beam width 2 on a 3-step toy sequence

Suppose at step 1 the model assigns $P(A) = 0.6$, $P(B) = 0.4$. Greedy picks A and never looks back. Beam search with $k=2$ keeps both alive. At step 2, continuing from A gives best next-step probability $0.3$ (running product $0.6 \times 0.3 = 0.18$), while continuing from B gives $0.9$ (running product $0.4 \times 0.9 = 0.36$). The B-branch, which greedy discarded at step 1, is now ahead. Beam search evaluates step 3 from both and reports whichever has the highest final product — possibly descending from B, something a greedy decoder could never discover.

Worked example 2: why beam width has diminishing, then negative, returns

Say translating a sentence, $k=1$ scores 0.62 on a quality metric, $k=5$ scores 0.71, $k=20$ scores 0.715, and $k=100$ scores 0.70. Quality improves sharply from 1 to 5, barely from 5 to 20, then drops at 100 — a very wide beam starts favoring sequences that are short or generic, simply because raw summed log-probability (always negative) penalizes length, an unrelated side effect of the scoring, not better content. Practical systems fix this with a length-normalization term, and beam widths of 4–10 usually capture most of the benefit.

Beam search's summed log-probability score behaves like this curve: it grows with more (correct) steps but the rate of improvement from adding more search width flattens out — most of the gain comes from the first few candidates you keep alive.

What this means in practice

Beam search is the standard decoding strategy wherever a sequence model must commit to a full discrete output — machine translation, text generation, and any forecasting setup that generates a path token-by-token (e.g. discretized price-move sequences). It is more expensive than greedy decoding by roughly a factor of the beam width, so it trades compute for output quality, and that tradeoff interacts with Bahdanau and Luong Attention, since better per-step attention makes even a narrow beam more reliable.

Practice

1. Walk through beam search with $k=1$ and confirm it reduces exactly to greedy decoding.
2. If two branches have running log-probabilities $-1.2$ and $-1.5$ after step 2, which one survives if $k=1$?
3. Explain in one sentence why summed log-probability without length normalization biases beam search toward shorter outputs.