Beam search decoding: Visual walkthrough — AI-ML deep dive

This page rebuilds Beam search decoding from absolute zero, as a sequence of pictures. We never assume you know what "log", "score", or "beam" mean — every symbol is earned before it appears. If you have seen 3.5.12-Sequence-to-sequence-models and 3.5.13-Attention-mechanism the setting will feel familiar, but you do not need them to follow along.

Step 1 — What is the machine even choosing between?

WHAT. Imagine a machine that must write a sentence one word at a time. Before it writes anything, it looks at every word it could write next and gives each one a probability — a number between $0$ and $1$ saying "how likely I think this word is here". All those numbers add to $1$ .

WHY. We need a shared language for "the machine's opinion". That language is probability: bigger number = machine likes it more. Everything else on this page is built on top of these numbers, so we picture them first.

PICTURE. Below, the machine's opinion after seeing the input "Hello" is drawn as bars. The tallest bar (red) is the word the machine likes most right now.

Step 2 — Why picking the biggest bar every time is a trap

WHAT. The obvious plan: at every step, write the single tallest-bar word. This is called greedy decoding. We now show why it can lose.

WHY. A word that looks great right now can force us onto a bad path later. Greedy can't see the future, so it commits too early — like grabbing a chess piece and losing the game two moves later.

PICTURE. Two paths through a tiny tree. The greedy path (following the biggest bar at step 1) ends with a lower total than a path that took a smaller bar at step 1.

The number written on each branch is that word's probability. Multiplying the numbers along a path gives the sentence's total probability:

P (path) = first word P (y_{1}) \times given the first second word, P (y_{2} ∣ y_{1}) \times \dots

$y_{1}, y_{2}, \dots$ :: the words chosen, in order.
$y_{2} ∣ y_{1}$ :: read " $y_{2}$ given $y_{1}$ " — the second word's probability depends on the first.
$\times$ :: we multiply because we want the chance that all the words happen together.

Step 3 — Turn multiplication into addition (why we take logs)

WHAT. Multiplying many small probabilities (like $0.6 \times 0.65 \times 0.9 \times 0.8$ ) gives tinier and tinier numbers. On a computer these can shrink below what the hardware can store — they hit $0$ and we lose information. We fix this by taking the logarithm of every probability.

WHY THIS TOOL. The logarithm answers exactly one question: "what power do I raise $10$ to, to get this number?" Its magic property is $lo g (a \times b) = lo g a + lo g b$ — it turns products into sums. Sums of moderate numbers never underflow, so this is the right and only tool for the job. And because $lo g$ always grows as its input grows (it is monotonic), whichever path has the biggest product also has the biggest sum-of-logs. We lose nothing by switching.

PICTURE. The left curve is $lo g$ : notice it is negative for inputs below $1$ (all probabilities are below $1$ ), and it climbs steadily. On the right, the same tree from Step 2 relabeled with $lo g$ of each probability — now we add along a path instead of multiplying.

score (y) = t = 1 \sum T lo g P (y_{t} ∣ y_{< t})

$\sum_{t = 1}^{T}$ :: "add up, for each step $t$ from $1$ to $T$ ".
$T$ :: how many words the machine actually generated (we do not count <START>).
$y_{< t}$ :: shorthand for "all the words before position $t$ ".
The whole sum is a negative number; closer to $0$ is better.

Step 4 — Keep the best $k$ , not just the best 1 (the beam)

WHAT. Instead of keeping the single best partial sentence, we keep the top $k$ of them. This surviving set is called the beam, and $k$ is the beam width.

WHY. Step 2 showed a good sentence can start with a second-place first word. If we keep the top $k = 2$ first words instead of just the top $1$ , that good sentence survives long enough to prove itself later. $k$ is a dial: $k = 1$ is greedy again; huge $k$ explores everything but costs more.

PICTURE. Same first-word bars as Step 1, but now the top $k = 2$ bars are circled in red — both survive into the next step. The third is discarded.

Step 5 — One expansion round: $k \times V$ candidates, keep $k$

WHAT. Now the engine. Each of the $k$ surviving sentences tries every vocabulary word as its next word. If the beam has $k$ sentences and the vocabulary has $V$ words, we produce $k \times V$ new candidate sentences. We score them all and keep only the top $k$ . Repeat.

WHY. This is the pruning that makes beam search affordable. A full search would examine $V^{T}$ complete sentences (astronomically many). By throwing away all but $k$ after every step, we do only about $k \cdot T \cdot V$ work — the search tree stays a fixed width $k$ instead of exploding.

PICTURE. Two red beam nodes each fan out to all $V$ words (thin black branches). Of the $k \times V = 2 \times 3 = 6$ tips, the top $k = 2$ (red) are kept; the rest (grey, dashed) are pruned.

Step 6 — The length trap and how to fix it

WHAT. Every extra word adds another negative number to the score (Step 3: all log-probs are $< 0$ ). So a longer sentence automatically scores lower — even when it's the better translation. Beam search would then always prefer curt, half-finished sentences.

WHY A DIVISION. We're comparing sentences of different lengths unfairly. To make it fair we divide the total score by the length, turning a total into an average per word. But dividing by the full length $T$ over-rewards very short sentences (an incomplete "I." can have a great average). So we soften it with an exponent $α$ between $0$ and $1$ .

score_{norm} (y) = \frac{1}{T ^{α}} t = 1 \sum T lo g P (y_{t} ∣ y_{< t})

$T$ :: number of generated tokens (= len(seq) − 1, excluding <START>).
$α$ :: the softening dial. $α = 1$ = full average; $α = 0$ = no fix (raw sum); $α \approx 0.6 - 0.7$ in practice.
$T^{α}$ :: raising $T$ to a power below $1$ gives a divisor that grows slower than $T$ — a gentle, not brutal, length correction.

PICTURE. Raw scores (black) get more negative as sentences lengthen — a downward slope that punishes length. After dividing by $T^{α}$ (red), the slope flattens: sentences of different lengths become comparable.

Step 7 — The full worked example, drawn

WHAT. Vocabulary {Bonjour, Salut, <END>}, beam width $k = 2$ , $α = 1$ . We translate "Hello". Follow the whole tree.

Step 0 — start. Beam is just [<START>] with score $0$ .

Step 1 — expand <START>:

candidate	log-prob	running score
`Bonjour`	$lo g 0.6 = - 0.51$	$- 0.51$
`Salut`	$lo g 0.35 = - 1.05$	$- 1.05$
`<END>`	$lo g 0.05 = - 3.00$	$- 3.00$

Keep top $k = 2$ : Bonjour ( $- 0.51$ ), Salut ( $- 1.05$ ).

Step 2 — expand both survivors, then finish and normalize:

completed sentence	raw score	$T$	normalized $= raw / T$
`Bonjour <END>`	$- 0.51 + lo g 0.9 = - 0.62$	$2$	$- 0.31$
`Salut <END>`	$- 1.05 + lo g 0.85 = - 1.21$	$2$	$- 0.605$

Winner: Bonjour <END> at normalized score $- 0.31$ (closer to $0$ = better).

PICTURE. The complete decoding tree: red is the winning path, grey-dashed are pruned branches, each edge labelled with its log-prob.

Step 8 — Edge and degenerate cases

WHAT & WHY. A correct picture must cover the corners, not just the happy path.

$k = 1$ . The beam holds one sentence; keeping "top 1" is just picking the biggest bar. Beam search collapses into greedy decoding. (Sanity check: our machinery must reproduce greedy here — it does.)
$k \geq V^{T}$ . Nothing ever gets pruned; we score every possible sentence. This is exhaustive search — guaranteed optimal but astronomically expensive, hence never used.
A sentence hits <END> early. It is finished: we stop expanding it but keep it in the pool, competing on its normalized score. It does not block the others from growing longer.
$α = 0$ . $T^{0} = 1$ , so we divide by $1$ — i.e. no length fix; the raw-sum length trap of Step 6 returns in full.
All log-probs equal. Every path scores the same total; the beam becomes an arbitrary tie — a reminder that beam search is only as good as the model's probabilities.

The one-picture summary

Read it left to right: probabilities → logs (sums) → keep top $k$ → expand → length-normalize → pick the winner. That six-link chain is beam search.

Recall Feynman retelling — say it back in plain words

A machine builds a sentence one word at a time, and for each spot it hands us a bunch of "how much I like this word" numbers between 0 and 1. Multiplying those numbers along a whole sentence tells us how good the sentence is, but the numbers get so tiny the computer chokes — so we take logarithms, which magically turn the multiplying into adding while keeping the same winner. Now, if we just always grabbed the single best word we'd be short-sighted, so instead we keep the $k$ best half-sentences alive. Each round, every survivor tries all vocabulary words, we score the whole crowd, and keep the top $k$ again — that pruning is what keeps the work small. One catch: longer sentences pile up more negative numbers and look worse unfairly, so we divide the score by (length) $^{α}$ to compare fairly. When a sentence says <END> it's done and waits with its final score. At the end the survivor closest to zero wins. And we stay humble: because we threw away everything but $k$ at each step, we might have discarded the true best sentence — beam search is a smart guess, not a guarantee.

Recall Quick self-test

Why take the log before summing scores? ::: To turn a product of tiny probabilities (which underflows) into a sum, without changing which sentence wins (log is monotonic). What does beam width $k = 1$ reduce to? ::: Plain greedy decoding. Why divide by $T^{α}$ ? ::: To stop longer sentences being unfairly penalized by their extra negative log-prob terms, while $α < 1$ avoids over-rewarding very short ones. In the worked example, which French word wins and with what normalized score? ::: Bonjour, at $- 0.31$ .