Beam Search Decoding
What you'll learn: How beam search keeps multiple candidate sequences alive during text generation to find better outputs than greedy decoding.
The Core Problem
When you learned Greedy Decoding (lesson 1191), you saw that picking the single most probable token at each step can lead to suboptimal sequences. Once you commit to a token, there's no going back—even if a slightly less probable token would have led to a much better overall sequence.
How Beam Search Works
Beam search maintains multiple hypothesis sequences simultaneously, called "beams." Instead of keeping just one sequence, you track the top k most promising candidates at each generation step.
The process:
- Start with the beginning token(s)
- Generate all possible next tokens for each beam
- Score each expanded sequence by its cumulative probability (product of all token probabilities so far, or sum of log probabilities)
- Keep only the top
ksequences with highest cumulative scores - Repeat until all beams produce end tokens or reach max length
- Select the sequence with the highest cumulative probability
A Simple Analogy
Imagine exploring multiple hiking trails simultaneously. Greedy decoding commits to the path that looks best at the first fork. Beam search sends scouts down the 3 most promising paths at each fork, eventually choosing the scout who reached the best destination—even if their first step wasn't the absolute best.
Key parameter: Beam width k (typically 3-10). Larger k = more computation but potentially better sequences.
Key Takeaway: Beam search balances quality and efficiency by maintaining multiple hypothesis sequences and selecting the path with the highest cumulative probability, avoiding the myopic decisions of greedy decoding.