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.
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.
Methods: Attribute-Conditional Search
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:
- 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.
- 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.
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