Beam Search Decoding
What you'll learn: How to generate better sequences by exploring multiple promising candidates at once instead of committing to a single choice at each step.
The Problem with Greedy Decoding
In autoregressive generation (lesson 1030), we decode one token at a time. The simplest approach—greedy decoding—picks the highest-probability word at each step. But here's the catch: the locally best choice at step 3 might lead to a poor overall sequence by step 10. Greedy is myopic.
How Beam Search Works
Beam search keeps track of multiple partial sequences (called "beams") simultaneously. At each decoding step:
- For each beam, generate all possible next tokens
- Score each extended sequence (usually by cumulative log-probability)
- Keep only the top k sequences overall (where k is the "beam width")
- Repeat until all beams end or reach max length
Think of it like exploring multiple conversation paths in parallel. With beam width = 3, you're considering the 3 most promising sentence beginnings, then the 3 most promising continuations of those, and so on.
The Trade-off
- Beam width = 1: Reduces to greedy search (fast but potentially suboptimal)
- Beam width = 5-10: Common sweet spot balancing quality and speed
- Beam width = 100+: Approaches exhaustive search (slow, diminishing returns)
Beam search doesn't guarantee finding the globally optimal sequence (that would require exponential search), but it's a practical middle ground between greedy speed and exhaustive accuracy.
Key Takeaway: Beam search improves sequence generation quality by maintaining multiple candidate hypotheses during decoding, exploring a broader solution space than greedy selection while remaining computationally tractable.