Beam search

Beam search generates text by keeping the k most promising partial sentences alive at each step, extending all of them, and keeping the best k again.

It is how a careful chess player thinks. Not "play the best-looking move instantly" — that is greedy-decoding — but "hold my three most promising lines in mind, look one move deeper on each, discard whichever now looks worst." A move that seemed strong can reveal a trap two steps later; keeping alternatives alive lets you back out.

Concretely, with a beam width of 3: keep the 3 highest-probability partial outputs, extend each with its plausible next tokens, score all the extensions by total sequence probability, keep the best 3 overall. Repeat to the end and return the best finished sequence.

beam 1: "The cat sat on"      ─┐
beam 2: "The cat rested on"    ├─ extend all → re-rank → keep best 3
beam 3: "A cat perched on"    ─┘

Beam search hunts for the most probable overall sequence, which suits tasks with a right answer: machine translation and speech recognition made it famous, and it still rules there. For open-ended chat it fell out of favour — maximising probability yields safe, repetitive, oddly dull text, so chat systems sample with temperature and top-p instead. Cost scales with beam width: width 5 means roughly five models' worth of decoding work.

Where to go next#

• Full lesson: How LLMs work
• Related terms: greedy-decoding, temperature, top-p, perplexity