Beam Search › Summary

Beam search sits between the extremes of greedy decoding (single path, no backtracking) and exhaustive search (all paths, computationally infeasible). By maintaining a beam of $k$ candidate hypotheses and pruning at each step, it explores the probability space efficiently and usually finds significantly better sequences than greedy decoding.

The key ideas to take away are:

• Greedy decoding fails because locally optimal choices lead to globally suboptimal sequences. Irrevocable step-wise decisions close off globally better paths.
• Beam search maintains $k$ hypotheses, expands each by the full vocabulary, and keeps the top $k$ at every step, trading compute for a more thorough search.
• Beam width trades quality for compute; values of 4-6 work well for translation, larger values show diminishing returns and can even hurt quality due to the beam search curse.
• Length normalization corrects the score bias against longer sequences using the penalty $\text{lp}(y) = (5 + |y|)^\alpha / 6^\alpha$, with $\alpha = 0.6$ being a common default.
• Diverse beam search partitions the beam into groups with inter-group diversity penalties to produce varied outputs, useful when multiple distinct hypotheses are needed.
• Nucleus sampling is the preferred alternative for creative generation, adapting the sampling pool to the local probability distribution and producing more natural, varied text.
• Large language models often use sampling rather than beam search for open-ended generation, but beam search remains the standard for constrained tasks like translation and structured generation.
• Engineering details such as KV cache management, batched inference, and n-best reranking matter significantly in production deployment and often determine whether beam search is practical at a given scale.

In the next chapter, we will explore the Attention Intuition that allows seq2seq models to align source and target sequences more effectively, moving away from the fixed-size context vector bottleneck that constrains the encoder-decoder models we have studied so far.