Empirical Analysis of Beam Search Performance Degradation in Neural Sequence Models

Eldan Cohen, J. Christopher BeckICML 2019 · OpenReview

Introduction

Beam search is the standard inference algorithm for decoding neural sequence models in tasks like machine translation, abstractive summarization, and image captioning. Because exhaustive search is computationally impossible, beam search maintains a fixed number of the most promising partial sequences—the "beam width"—at each step.

Intuitively, a larger beam width explores a broader search space and should yield better, higher-probability sequences. However, researchers have repeatedly observed a frustrating paradox: increasing the beam width beyond a small number (e.g., > 5) causes the quality of the output to drop significantly according to human-aligned metrics like BLEU or ROUGE. Previous work has attempted to explain this degradation through length bias, models lazily copying source text, or overfitting. This paper provides a unified, empirical explanation for why this degradation happens across multiple domains and proposes a general algorithmic fix.

The Root Cause: Search Discrepancies

To understand the degradation, the authors borrow the concept of search discrepancies from combinatorial heuristic search. A discrepancy occurs when the search algorithm chooses a token that is not the most probable one at that specific time step (i.e., it deviates from the greedy choice). The difference in log-probability between the most likely token and the chosen token is defined as the discrepancy gap.

Example of search discrepancies in a decoding tree. Bracketed numbers indicate the discrepancy gap from the greedy choice.

By analyzing the decoding process, the authors identified a clear pattern: "Early Mistake, Late Compensation." As beam width increases, the search algorithm increasingly favors sequences that contain massive discrepancies early in the generation process. Because these early tokens are highly unlikely according to the model, they must be followed by tokens with extremely high conditional probabilities to eventually win the beam search.

Distribution of discrepancies across sequence positions for different beam widths. Larger beams drastically increase early discrepancies.

While these high-discrepancy sequences achieve a higher overall mathematical probability under the model's scoring, they are objectively worse translations or captions. This discrepancy framework elegantly explains previous isolated findings. For example, when a model regurgitates exact training-set captions or copies source text, it often starts with a low-probability first token (a large discrepancy) but follows it with highly predictable, high-probability subsequent tokens. The authors suggest this phenomenon is a symptom of underlying model flaws, such as exposure bias or label bias, where models become overly confident if forced down a specific, familiar trajectory.

To test if these discrepancies are the primary cause of performance degradation, the authors introduce two heuristic constraints to standard beam search:

  1. Discrepancy Gap Constraint: The search is restricted to only consider candidate tokens whose discrepancy gap is smaller than or equal to a tuned threshold $\mathcal{M}$.
  2. Beam Candidate Rank Constraint: The search only considers the top $\mathcal{N}$ one-token extensions from each active beam, rather than evaluating a massive pool of lower-ranked extensions.

Experimental Results

The authors evaluated their hypothesis across three distinct sequence synthesis tasks: Machine Translation (WMT’14 En-De, En-Fr; WMT'17 En-Zh), Abstractive Summarization (Gigaword), and Image Captioning (MSCOCO).

The baseline degradation was confirmed to be severe. In the WMT'14 En-De baseline, a beam width of 5 yielded a BLEU score of 26.11. Pushing the beam width to 250 caused the BLEU score to plummet to 21.38. Crucially, when comparing sequences improved by wider beams versus those degraded by them, the increase in early discrepancies was almost entirely associated with the degraded solutions.

Applying the proposed constraints completely eliminated the performance drop across all domains:

  • Machine Translation: On WMT'14 En-De, using a gap threshold of $\mathcal{M}=1.5$ kept the BLEU score stable at 26.29 even at a massive beam width of 250.
  • Image Captioning: In MSCOCO, the baseline BLEU dropped from 31.96 (B=5) to 29.79 (B=250). With the gap constraint, it remained high at 32.35 (B=250).

Limitations and Future Work

While highly effective, the proposed constraints require tuning a threshold ($\mathcal{M}$ or $\mathcal{N}$) on a held-out validation set, which adds slight overhead to the deployment pipeline. Additionally, the empirical analysis focuses heavily on RNN and CNN-based sequence-to-sequence models trained with word-level likelihood.

Future work should investigate how alternative training schemes—such as sequence-level loss functions designed to mitigate exposure bias—behave under large beam widths. It remains to be seen whether such training methods naturally suppress these large search discrepancies without the need for inference-time constraints, and how these findings fully translate to modern Transformer architectures.

Summary updated

Abstract

Beam search is the most popular inference algorithm for decoding neural sequence models. Unlike greedy search, beam search allows for non-greedy local decisions that can potentially lead to a seque...
BibTeX
@inproceedings{cohen2019empirical,
  author = {Eldan Cohen and J. Christopher Beck},
  title = {{Empirical Analysis of Beam Search Performance Degradation in Neural Sequence Models}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=Sy-Y-3W_bB},
}
Figure