Beam Search, Playable

EP 01

The greedy trap — be the decoder yourself

Here is a tiny language model as a menu: after each word it offers a few next words with real probabilities. Build a 5-word sentence by clicking. A sentence's total probability is the product of its steps — so a tempting first word can lead you downhill. Try to beat the greedy strategy (always take the top bar).

Click a bar to pick the next word. Four picks finish the sentence.

The trap: "cake" (40%) looks better than "moon" (35%) at step one — but everything after "cake" is mediocre, while "moon" opens a 90% highway. Greedy commits before it can know that. Every autoregressive model, GPT included, faces this exact myopia at every single token.

EP 02

Keep B sentences alive — watch beams survive and die

Beam search's fix: at every step, expand all surviving candidates, score each by cumulative log-probability, keep only the top B ("the beam"), kill the rest. Set the beam width, then step through the tree. Gold = alive, grey = pruned. Width 1 is exactly greedy; width 5 keeps every option in this toy world.

Beam width 2

Scores are cumulative log-probs: log(0.4) + log(0.5) + … — higher (closer to 0) is better. Adding logs = multiplying probabilities.

Why log-probs: multiplying many probabilities underflows to zero fast, so real decoders add logs instead. And why only B survivors? The full tree has Vⁿ sentences — for GPT that's 100,000¹⁰⁰. Beam search is a budget: explore a little, not everything.

EP 03

The comeback — beam finds what greedy threw away

Same toy model, head to head. Greedy's line starts higher — it took the locally best word. Then the beam's second-choice path overtakes it and never looks back. Greedy can't recover, because it discarded "moon" at step one and there is no undo.

Good case: when there is one globally best answer — a translation, a transcription, a SQL query — beam search reliably finds better outputs than greedy; that's why Google's neural machine translation shipped with beam search from day one. Bad case: greedy's step-1 "lead" is the illusion; it wins the first token and loses the sentence.

EP 04

Five shades of beige — the blandness collapse

Now ask for a story. This toy storyteller has one high-probability backbone and many quieter alternatives. Run beam search: all B "different" beams converge on near-clones of the safest sentence, differing by a word or two. Then sample 5 stories at temperature 1 and compare the diversity score — computed live from word-by-word agreement.

Beam width 5

Run one of the two decoders. Words that differ from the first output get highlighted.

The split: for translation, all beams agreeing is a feature — there IS one right answer, and consensus means confidence. For stories, chat and brainstorms it's a bug: beam search maximizes probability, and the most probable text is the blandest. This is exactly why ChatGPT samples with temperature instead of beam-searching your conversation.

EP 05

Short, safe and wrong — the length bias

One more honest failure. Every extra token multiplies in a probability ≤ 1, so longer sentences always score lower — and raw beam search happily truncates your translation. Below are four candidate translations of the same sentence, with per-token probabilities. Drag the length-penalty α and watch the winner flip.

Length normalization α α = 0.00 (raw beam)

The fix that shipped: dividing the score by length^α (α ≈ 0.6–1.0) is standard in production translation systems precisely because raw beam search kept answering "he left." to eight-word sentences. Beam search is a great searcher for a flawed objective — pure probability is not the same as quality.