Beam Search — Step-by-Step Visualization

Algorithm Pattern

Width-Limited Tree Search

Key Idea

Beam search keeps the top-k (beam width) partial sequences at each step, avoiding exponential cost while outperforming greedy decoding.

Step-by-Step Approach

1. Start with beam = [(<start>, score=1.0)].
2. Expand each beam by scoring all vocab words as the next token.
3. Keep only the top-k sequences by cumulative score.
4. Repeat until all beams reach <end> or max length.
5. Longer sequences get lower scores — apply length normalization.

Common Gotchas

• Greedy search = beam width 1 — fast but suboptimal.
• Beam search can repeat phrases; n-gram blocking is a common fix.
• Top-p sampling is now preferred over beam search for open-ended generation.