Problem. A language model gives, for any prefix, a probability for each next token. The probability of a sequence is the product of its token probabilities, so its log-probability is the sum. Find a sequence of length L with the highest log-probability, or as close as possible within a compute budget.
P(first) a 0.5 b 0.4 c 0.1
P(next | a) a 0.35 b 0.35 c 0.3
P(next | b) a 0.05 b 0.9 c 0.05
greedy: a, then a → 0.5 × 0.35 = 0.175
best: b, then b → 0.4 × 0.9 = 0.36
Greedy takes the best first token and gets stuck behind it. Exhaustive search finds the best, but there are V^L sequences: 50,000 tokens and 20 steps is 10⁹⁴. Beam search sits in between, and its core step is the top-B selection from lessons 9.3 and 9.9.
Why it matters. Beam search is the standard decoder for translation, speech recognition, summarisation with encoder-decoder models, and structured generation where the single most likely output matters more than diversity. Chat models usually sample (lesson 9.9) instead, and knowing why is part of the interview answer.