Beam Search › Limitations

Beam search has served the NLP community well, but it carries several important limitations.

The most fundamental is the label bias problem. At each step, beam search scores sequences using a locally normalized probability (the decoder outputs a softmax, which sums to 1 over all next tokens). This means a model can "hide" probability by distributing it among many similar continuations, making it harder for beam search to discover sequences that diverge significantly from common patterns. Maximum Entropy Markov Models (MEMMs) have a well-known variant of this problem, and neural seq2seq models are not fully immune.

A second limitation is that beam search finds the maximum a posteriori (MAP) sequence under the model. For tasks where the model has a sharp, well-peaked distribution (like factual question answering), MAP decoding gives the right answer. But for tasks where many good outputs exist (like open-ended dialogue or creative writing), MAP decoding returns the one sequence the model assigns highest probability to, which tends to be generic and safe rather than interesting and varied. The sampling methods discussed above address this but introduce their own challenges.

A third limitation is computational: beam search is sequential. Each step depends on the previous one because the decoder must consume its own output. This makes it incompatible with the kind of fully parallelized computation that made transformers so efficient during training. Speculative decoding and parallel decoding methods attempt to address this, but they require significant engineering and approximate the beam search guarantee rather than preserving it exactly.

Finally, beam search is sensitive to the model's calibration. If the model systematically assigns incorrect probabilities (overconfident or underconfident), beam search faithfully optimizes those incorrect probabilities. A poorly calibrated model with wider beams may produce confidently wrong outputs. Sampling from a well-calibrated model might outperform beam search from a miscalibrated one.

These limitations are not just academic concerns. The NLP community has moved toward sampling-based decoding for many applications partly because beam search's commitment to maximum probability produces outputs that, while internally coherent, feel stilted and over-optimized. The "degenerate text" problem, where very long beam-search outputs fall into repetition, was a major practical problem in early neural MT systems. Solutions like no-repeat-ngram blocking were developed specifically because the MAP sequence under many models includes repeated n-grams, which are penalized by beam search's length normalization but not eliminated.

Despite these limitations, beam search remains a foundational algorithm. Understanding its mechanics is essential for understanding why models behave the way they do at inference time, and for diagnosing problems when output quality is poor. Every practitioner who works with sequence generation models will encounter beam search in some form, whether tuning the beam width for a translation task, debugging a repetition problem in a summarization model, or choosing between beam search and sampling for a generative application.