MAP's not dead yet: Uncovering true language model modes by conditioning away degeneracy

Davis Yoshida, Kartik Goyal, Kevin GimpelACL 2024 · DOI

Introduction: The "Bad Mode Problem"

In Natural Language Generation (NLG), Maximum A Posteriori (MAP) decoding—the process of finding the single most probable sequence—is often avoided. Standard beam search, which approximates MAP, frequently yields "degenerate" outputs: empty strings, repetitive loops, or nonsensical fragments. Consequently, the field has largely pivoted to stochastic sampling methods like Top-p or Top-k.

This paper challenges the assumption that MAP is fundamentally broken. The authors argue that these degenerate outputs are not a failure of the model's training or capacity, but rather a byproduct of "low-entropy distractors" within the data distribution.

The Low-Entropy Distractor Theory

The core hypothesis is that valid human language is high-entropy; there are countless ways to express an idea, spreading probability mass thin. Conversely, noise in training data (e.g., empty lines, formatting errors) is low-entropy. Even if such noise represents only 1% of the training set, the "empty string" might have a probability of 0.01, while any specific, high-quality sentence might only have a probability of 0.0001. In a global MAP search, the "empty" noise wins simply because it has no competition within its own category.

Global mode vs. length-constrained modes

As shown in the example above, the global mode is often just an end-of-sentence token. However, by conditioning the search on a specific attribute—like a target length—we can bypass these distractors to find the high-quality, high-likelihood sequences the model has actually learned.

To uncover these hidden modes, the authors propose Attribute-Conditional Search. Instead of solving for the global maximum $\text{argmax}_y P(y)$, they search for the most likely sequence given a constraint $A(y) = a$: $$\text{argmax}_y P(y | A(y) = a)$$

The researchers implemented two primary techniques:

  1. Exact Search via DFS: They developed a Depth-First Search algorithm with aggressive pruning and a novel Key-Value (KV) cache heuristic. This allowed for mathematically exact MAP searches on models as large as LLaMA-7B, a task previously thought to be computationally prohibitive.
  2. Approximate Conditional Search: For efficiency, they utilized classifier-guided beam search. "Prefix classifiers" were trained to predict if a partial sequence would eventually satisfy a desired attribute (like length or a high reward score), steering the search toward valid, high-quality regions of the probability space.

Key Results

The study found that degeneracy is pervasive: the global mode for the base LLaMA-7B model is an empty string for 70.7% of prompts. However, when the search is conditioned on length, the quality of the output improves dramatically.

Translation quality (BLEU/BLEURT) improves significantly as conditioning length increases

Quantitative evaluations in machine translation (WMT’17 Zh-En) demonstrate that while the global mode yields nearly zero BLEU, conditioning on increasing lengths ($L$) recovers fluent text that achieves competitive scores. Furthermore, the authors successfully elicited instruction-following behavior from the base LLaMA-7B model—which was never fine-tuned for instructions—simply by using a reward-model-based classifier to guide the search.

Conclusion

The "bad mode problem" is likely a data-distribution artifact rather than a fundamental flaw in language modeling. By moving away from global MAP search toward attribute-conditioned decoding, we can recover the high-quality knowledge buried beneath low-entropy noise. This suggests that instead of abandoning deterministic decoding for sampling, we should focus on more sophisticated ways to "condition away" degeneracy.

Summary updated

BibTeX
@inproceedings{yoshida2024map,
  author = {Davis Yoshida and Kartik Goyal and Kevin Gimpel},
  title = {{MAP's not dead yet: Uncovering true language model modes by conditioning away degeneracy}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.acl-long.855},
}
Figure