One-sentence Summary

Researchers at Toyota Technological Institute at Chicago and Georgia Institute of Technology argue that MAP decoding degeneracy in language models stems from training data contamination rather than model inadequacy, propose length-conditioned MAP search to recover fluent modal sequences, and demonstrate via classifier-based approximate search that reasonable outputs can be elicited from LLaMA-7B without finetuning.

Key Contributions

• A theoretical account of degenerate MAP outputs shows that mixing even a tiny amount of low-entropy noise with a text distribution can make the global mode degenerate even when the model is error-free. It also clarifies that MAP search and sampling respond differently to noise.

• Attribute-conditional MAP decoding is proposed to search for the mode of the conditional distribution given an explicit attribute such as output length. Exact length-conditional search on machine translation and language models shows that these modes are more fluent and topical than unconditional modes.

• Exact modal sequences are presented from several autoregressive models, including variants of LLaMA-7B, showing that degenerate modes can persist even at that scale. Classifier-based approximate conditional search on LLaMA-7B elicits reasonable outputs without instruction finetuning.

Introduction

In neural language generation, especially machine translation and story generation, decoding directly controls final text quality. Sampling dominates because approximate MAP decoding often yields degenerate outputs like empty or repetitive text; prior work mostly blamed model bias or treated modes as statistically unimportant. The authors argue that low-entropy distractors in training data can produce such bad modes even in perfectly trained models, so the issue is not purely a model weakness. They propose attribute-conditional search, using attributes such as length or classifier-based quality to locate a cleaner conditional mode. The authors’ contributions include a theoretical explanation of degenerate modes, a caching heuristic enabling exact search on 7B models, evidence that length-conditional modes are often high quality in MT and story generation, and an approximate classifier-guided beam search method that finds outputs with higher likelihood and quality than ordinary beam search.

Method

The authors leverage a decoding-side framework to address the bad mode problem in MAP-like generation. Their key observation is that sampling methods reduce output degeneracy by suppressing low-probability tails and lowering entropy, but mode-seeking search lacks a comparable safeguard because the global mode can be degenerate even when the model has not failed to fit the data. The proposed solution is attribute-conditional search. Instead of searching for the global mode of the output distribution, the method searches for the mode of a conditional distribution:

Here, $x$x denotes the input context, $y$y denotes a candidate output, and $A(y)=a$A(y)=a specifies an attribute constraint such as output length. This formulation converts mode decoding into a constrained search problem. For example, when the dominant degenerate mode is a short or truncated sequence, the attribute can be set to $A(y)=|y|$A(y)=∣y∣, causing the search to return the highest-scoring sequence of a chosen length.

The exact search component operates by exploring autoregressive output sequences with depth-first search and aggressive pruning. This makes it possible to recover exact unconditional or length-conditional modes in models that would otherwise have exponentially large search spaces. The authors extend this exact search procedure to large autoregressive language models by introducing a caching strategy that reduces memory pressure during beam-like traversal over partial prefixes. This exact-search stage functions as a diagnostic and verification module: it confirms that short outputs can be the exact modes of some models, and that imposing simple length conditions can recover high-quality sequences in some settings.

Because exact conditional search becomes computationally prohibitive at realistic output lengths, the authors implement an approximate version of attribute-conditional decoding through conditional beam search. Standard beam search builds a sequence incrementally by maintaining partial hypotheses $x_{1:t}$x1:t​ and ranking them by their cumulative model log-likelihood:

To search for the conditional mode, the score must be adapted to the target attribute:

Directly computing this expression is intractable because the model does not provide the token-level conditional probability of each next token given the global attribute. The authors therefore apply Bayes' rule and use the fact that many terms telescope across timesteps. After dropping constants that do not affect ranking, the desired score can be expressed as an ordinary beam score plus an attribute score:

In practice, the second term is estimated with a learned prefix classifier. This classifier is trained to predict whether a partial prefix is likely to expand into a full output satisfying the desired attribute. The approximate conditional score becomes:

This yields a modular decoding pipeline. First, a language model generates partial hypotheses and computes their standard token-level log-probabilities. Second, a prefix classifier evaluates the top candidate prefixes for the target attribute. Third, the two scores are summed to form a conditional beam score. Fourth, the beam is pruned and extended using this adjusted score. The pipeline is nearly identical to ordinary beam search, except that the classifier output is added during ranking. This design avoids accumulating classifier uncertainty across every timestep, because the classifier is applied as a sequence-level prefix score rather than as a token-level modifier that is summed throughout generation.

For computational efficiency, the prefix classifier is applied only to a limited set of high-ranked candidate tokens at each decoding step, rather than to the full vocabulary. This keeps the approximate search affordable while still allowing the decoder to favor partial sequences that are more likely to satisfy the target attribute. The result is an attribute-guided beam search that targets conditional modes, making it suitable for realistic translation lengths and for mitigating output degeneracies that cannot be handled by exact unconditional mode search alone.

Experiment

Across machine translation, story completion, and instruction-following models, exact mode searches show that unconditional highest-scoring outputs are frequently empty or otherwise degenerate, especially for longer and more open-ended inputs, while non-empty modes are generally fluent. Case studies and approximate conditional search on length indicate that constraining search to plausible output lengths removes many degeneracies and produces grammatical, high-quality sequences. Additional conditioning on learned quality attributes also improves LLaMA instruction-following outputs, suggesting that degenerate modes reflect search artifacts rather than poor model representations.

The table compares the model's global mode with outputs produced under explicit length constraints. The unconstrained mode is empty, while length-constrained outputs form valid translations that become more informative as the target length increases. Shorter constrained outputs are brief, whereas longer ones add contextual detail and appear more complete. Length conditioning removes the empty global mode in this translation example. Longer length-constrained translations include more detail than shorter constrained modes. The constrained outputs appear grammatical once enough length is available.

The modal outputs conditioned on longer target lengths receive better BLEU and BLEURT scores than outputs conditioned on shorter lengths or the global mode. BLEU rises as the length constraint increases, while BLEURT is unchanged between the global and shortest condition and then improves steadily with longer lengths. This supports the observation that length-conditioned translations become more fluent and higher quality when the target length is sufficient. Longer length constraints correspond to higher translation scores. The shortest and global modal outputs score poorly, especially on BLEU.

Classifier guided beam search generally finds higher likelihood translations than directly constrained search across most length targets and beam sizes, and it also tends to receive better estimated fluency under Llama2-7B. Constrained search is competitive on perplexity, but its search winrate is notably lower, especially for smaller beams and longer targets. Larger beams reduce the gap between the methods, yet classifier guided search remains higher likelihood and higher quality under BLEURT. Classifier guided search consistently outperforms constrained search on search winrate across the reported length ratios. Conditional outputs are more likely to be grammatical, while ordinary constrained beam search can fail to produce valid outputs. Llama2-7B perplexity is similar or better for conditional outputs, suggesting comparable or improved fluency. Increasing beam size brings the two methods closer, but conditional search still gives better likelihood and BLEURT scores.

Prefix classifier guidance changes Chinese to English decoding by producing translations that are more complete and grammatical than ordinary beam search outputs. The examples show that unguided beam search can truncate or emit fragments, while guided decoding often returns fuller sentences closer to the reference translation. Guided decoding yields fuller translations than beam search fragments. Unguided beam search can favor outputs that are incomplete or less fluent.

Conditioned beam search is preferred over ordinary beam search by human raters, GPT-4, and the reward model on the evaluated instruction-following subset. The advantage remains when empty outputs are excluded, suggesting that conditioning improves more than just the blank-response case. Qualitatively, conditioned outputs are also more often grammatical, while ordinary beam search is more likely to produce degenerate or low-quality failures. Human raters, GPT-4, and the reward model each favor conditioned outputs over ordinary beam search outputs on average. Even when ordinary beam search produces a non-empty output, conditioned generation still achieves a higher-reward result more often than beam search. Conditioned outputs are qualitatively more likely to be grammatical than ordinary beam search outputs.

Experiments compare unconstrained, length-constrained, and classifier-guided decoding on translation and instruction-following tasks. They show that length conditioning eliminates empty global modes and yields more complete, grammatical, and higher-quality outputs, with scores improving as target length increases. Classifier-guided and conditioned beam search also outperform ordinary search by producing more valid, fluent outputs and receiving stronger automatic, human, and model-based judgments, especially when unconstrained search is prone to truncation or degenerate failures.