Course contentsShow
← Machine Learning and Deep Learning
Lesson 1031 of 3,53823. Recurrent Neural NetworksFree lesson

Beam Search Decoding

Exploring multiple candidate sequences simultaneously to find high-probability outputs beyond greedy selection.

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:

  1. For each beam, generate all possible next tokens
  2. Score each extended sequence (usually by cumulative log-probability)
  3. Keep only the top k sequences overall (where k is the "beam width")
  4. 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.