Beam search is a decoding method that keeps several candidate sequences, called beams, alive at once and expands them step by step, finally selecting the sequence with the best overall score. Unlike greedy decoding, which commits to the best token at each step, beam search explores a few promising paths before deciding. It is a strong choice for translation and summarisation, and a weak one for open-ended writing.
Key takeaways
- Beam width (k) controls how many candidate sequences are kept.
- It approximates finding the highest-probability full sequence.
- A length penalty is needed, or short outputs win unfairly.
- It produces fluent but often bland, repetitive text in open-ended tasks.
- Cost and memory scale roughly with beam width.
Beam search explained in simple terms
Planning a route, greedy decoding takes the best-looking turn at each junction. Beam search keeps the three most promising routes on the map, extends each one at every junction, discards the worst and continues. At the end, it compares the surviving routes and chooses the best complete journey.
How it works
- Start with the prompt and generate the top k tokens as k beams.
- For each beam, compute probabilities for the next token.
- Score every beam-and-token combination by cumulative log probability.
- Keep the best k overall; discard the rest.
- Repeat until beams finish or reach the length limit.
- Apply a length penalty and return the highest-scoring sequence.
A worked example with beam width 2
Prompt: “The meeting was”.
| Step | Beams kept | Cumulative score |
|---|---|---|
| 1 | “postponed” (0.40), “cancelled” (0.35) | log 0.40, log 0.35 |
| 2 | “postponed to” (0.40 × 0.60), “cancelled due” (0.35 × 0.70) | 0.24, 0.245 |
Notice that “cancelled due” overtakes “postponed to” at step 2, even though “postponed” was more likely at step 1. Greedy decoding could never recover this, because it discarded “cancelled” immediately.
Why a length penalty is needed
Each extra token multiplies in another probability below 1, so longer sequences always score lower. Without correction, beam search favours very short outputs. Implementations divide the score by the length raised to a tunable power, often around 0.6 to 1.0.
Where beam search works well
| Task | Suitability | Reason |
|---|---|---|
| Machine translation | Strong | One correct meaning, measurable quality |
| Summarisation | Good | Faithfulness matters more than variety |
| Speech recognition | Strong | A single correct transcript exists |
| Code completion | Sometimes | Precision matters |
| Chat and creative writing | Poor | Produces generic, repetitive text |
The beam search curse
Research on open-ended generation found that increasing beam width can make text worse, not better: it converges on high-probability but dull, repetitive phrasing, because real human text is not the most probable text. This finding helped motivate sampling methods such as top-p for creative tasks.
Limitations
- Slower and more memory-hungry than greedy decoding.
- Needs tuning of beam width and length penalty.
- Produces low-diversity output.
- Rarely used in modern chat APIs, which favour sampling.