What is beam search, and how does it differ from greedy decoding?

What you need to know

Where greedy goes wrong — a worked example

A bank bot is continuing "Your refund". The model's probabilities:

Step 1:  " is" 0.5    " will" 0.4Step 2 after " is":    " pending" 0.4   " late" 0.1Step 2 after " will":  " be" 0.9        " not" 0.05

Greedy takes " is" (0.5), then " pending" (0.4). Sequence probability: 0.5 × 0.4 = 0.20.

Beam search, k = 2, keeps both " is" and " will" after step 1. After step 2 the candidates are:

"is pending"  0.5 x 0.4  = 0.20"is late"     0.5 x 0.1  = 0.05"will be"     0.4 x 0.9  = 0.36   <- best"will not"    0.4 x 0.05 = 0.02

Beam search keeps "will be" (0.36) and "is pending" (0.20). The best full sequence started with the second-best first token, which greedy threw away.

How beam search works

1. Start — one beam: the prompt.
2. Expand — for each beam, score the top next tokens.
3. Prune — keep the k sequences with the highest total log-probability.
4. Finish — stop beams that emit an end token; return the best finished one, usually after length normalisation.

Sequence probability always drops as more tokens are multiplied in, so beam search favours short outputs. Length normalisation divides the log-probability by length (or a power of it) to fix this.

Why chat models do not use beam search

• Blandness — the highest-probability text is often generic ("I'm sorry for the inconvenience. Please contact support.").
• Repetition — maximising likelihood can loop on a phrase.
• Cost — k beams means about k times the compute and KV cache.
• Streaming — the best beam can change late, so you cannot show tokens as they come.

So chat, writing and reasoning models sample instead. Beam search remains common in machine translation and speech recognition, where there is roughly one correct output.

A real-life example

A bank sends account notices in English and Hindi. The translation service uses a dedicated encoder–decoder translation model with beam size 4. Greedy decoding occasionally produced an awkward word order that locked the rest of the sentence into a poor phrasing; beam 4 fixed most of these at about 4 times the decoding compute, which is acceptable for a batch job run overnight.

The same bank's chat assistant uses sampling with a low temperature instead. When the team tried beam search there, answers became stiff and repeated the same apology in most replies, and they could no longer stream the reply word by word.

Follow-up questions to expect

• "What beam size is typical?" — 4 to 10. Larger beams often do not help and can even make outputs shorter and worse.
• "Does a reasoning model use beam search?" — No; it samples a chain of thinking tokens. Some systems sample several full answers and pick the best, which is a search over complete outputs rather than beam search.
• "What is speculative decoding?" — A speed-up: a small draft model proposes several tokens and the large model checks them in one pass. It gives the same output distribution as the large model alone, just faster.