If beam search is the answer, what was the question?

Clara Meister, Tim Vieira, Ryan Cotterell

Abstract

Quite surprisingly, exact maximum a posteriori (MAP) decoding of neural language generators frequently leads to low-quality results. Rather, most state-of-the-art results on language generation tasks are attained using beam search despite its overwhelmingly high search error rate. This implies that the MAP objective alone does not express the properties we desire in text, which merits the question: if beam search is the answer, what was the question? We frame beam search as the exact solution to a different decoding objective in order to gain insights into why high probability under a model alone may not indicate adequacy. We find that beam search enforces uniform information density in text, a property motivated by cognitive science. We suggest a set of decoding objectives that explicitly enforce this property and find that exact decoding with these objectives alleviates the problems encountered when decoding poorly calibrated language generation models. Additionally, we analyze the text produced using various decoding strategies and see that, in our neural machine translation experiments, the extent to which this property is adhered to strongly correlates with BLEU.

The Paradox of the Beam Search Curse

In Neural Machine Translation (NMT), researchers face a baffling paradox known as the "Beam Search Curse." Theoretically, the goal of decoding is to find the most probable sentence according to the model—a process known as Maximum A Posteriori (MAP) decoding. However, when exact search algorithms are used to find this global maximum, the output is often nonsensical, frequently favoring empty strings or repetitive, short phrases.

Curiously, beam search—a greedy heuristic that explores only a fraction of the search space—consistently produces high-quality text. For years, this was viewed as a necessary evil: a flawed search algorithm that somehow worked. This research flips the script, asking: If beam search is the "answer" to generating good text, what is the actual objective function it is solving?

The authors approach this by framing beam search as an exact solution to a regularized decoding objective:

$$y^* = \text{argmax} (\log p(y|x) - \lambda \cdot R(y))$$

where $R(y)$ is a regularizer penalizing specific text properties. They mathematically demonstrate that beam search and greedy search are limiting cases of regularizers that penalize "local sub-optimality." Essentially, beam search forces the model to make choices that are consistently "good enough" at every step, preventing it from sacrificing local quality for a theoretical global maximum that the model is poorly calibrated to identify.

Uniform Information Density (UID)

Drawing from cognitive science, the paper introduces the Uniform Information Density (UID) hypothesis as the missing link. UID suggests that human communication is most efficient when "surprisal" (the negative log-probability of a word) is distributed evenly across a sentence. The authors propose several UID-based regularizers to explicitly enforce this property during decoding:

  • Variance: Penalizes high variance in surprisal across the sequence.
  • Local Consistency: Penalizes large differences in surprisal between adjacent words.
  • Max Surprisal: Penalizes the single most surprising word.
  • Squared Surprisal: Penalizes the sum of squared surprisals.

Empirical Evidence and Results

The theories were tested on standard benchmarks like IWSLT’14 (German-to-English) and WMT’14 (English-to-French). The results provide strong empirical support for the UID hypothesis.

Performance of UID-regularized decoding on IWSLT'14 (De-En). The inset highlights the near-perfect correlation ($R^2=0.99$) between BLEU and surprisal standard deviation.

Key Findings:

  1. Exact Search Success: By adding UID regularizers, the authors could use exact search (e.g., Dijkstra’s algorithm) and achieve BLEU scores comparable to or better than standard beam search. For instance, on WMT'14 En-Fr, a "Squared Regularizer" achieved a BLEU of 36.92, surpassing the 36.42 of unregularized beam search.
  2. Mitigating the Large Beam Drop: Standard beam search performance typically plummets as the beam size $k$ increases (e.g., to 500). UID-regularized decoding remains robust, maintaining high quality even at large beam sizes where standard methods fail.
  3. The UID-Quality Correlation: As shown in the figure above, there is a striking $R^2 = 0.99$ correlation between the standard deviation of surprisals and BLEU scores. High-quality, human-like text consistently exhibits a "flat" information profile.

Conclusion

This work reveals that beam search's success isn't an accident; it's due to an implicit inductive bias toward Uniform Information Density. By explicitly incorporating UID as a decoding objective, we can move beyond heuristics and develop more robust, theoretically grounded methods for neural language generation. While computationally more intensive than simple beam search, these regularized objectives offer a path to fixing the "Beam Search Curse" in poorly calibrated models.

Summary updated

Abstract

Quite surprisingly, exact maximum a posteriori (MAP) decoding of neural language generators frequently leads to low-quality results. Rather, most state-of-the-art results on language generation tasks are attained using beam search despite its overwhelmingly high search error rate. This implies that the MAP objective alone does not express the properties we desire in text, which merits the question: if beam search is the answer, what was the question? We frame beam search as the exact solution to a different decoding objective in order to gain insights into why high probability under a model alone may not indicate adequacy. We find that beam search enforces uniform information density in text, a property motivated by cognitive science. We suggest a set of decoding objectives that explicitly enforce this property and find that exact decoding with these objectives alleviates the problems encountered when decoding poorly calibrated language generation models. Additionally, we analyze the text produced using various decoding strategies and see that, in our neural machine translation experiments, the extent to which this property is adhered to strongly correlates with BLEU.
BibTeX
@inproceedings{meister2020if,
  author = {Clara Meister and Tim Vieira and Ryan Cotterell},
  title = {{If beam search is the answer, what was the question?}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=R8ODzCcjHlE},
}
Figure