Diversified Decoding in Autoregressive Sequence Generation

40 concepts34 papers1 proposal

When generating text or sequences using autoregressive language models, standard beam search is the default strategy for finding high-probability outputs. It tracks a fixed number of hypotheses (the beam width) and expands them token by token. However, standard beam search suffers from a notorious flaw: beam collapse. Because conditional language models concentrate massive probability mass around a few highly favored semantic paths, the top candidates in a beam often end up nearly identical, differing only by a minor suffix, a punctuation mark, or a synonym. As Gimpel et al. observed, this lack of variety severely limits the utility of the generated set for downstream tasks like discriminative reranking, system combination, or human post-editing.

To solve this, a prominent line of research focuses on diversified decoding. The core intuition is simple: instead of optimizing purely for the model's raw probability, the decoding process is augmented with a dissimilarity penalty that actively pushes candidate sequences away from one another.

The Mechanics of Similarity Penalties

To understand why diversified decoding works, consider how standard beam search scores a candidate token $x_t$ at time step $t$:

$$\text{Score}(x_t) = \text{Score}(x_{<t}) + \log P(x_t \mid x_{<t})$$

In similarity-penalized decoding, this objective is modified by subtracting a penalty term proportional to how much the candidate overlaps with already selected sequences in the beam:

$$\text{Score}(x_t) = \text{Score}(x_{<t}) + \log P(x_t \mid x_{<t}) - \lambda \cdot \text{Similarity}(x_t, \mathcal{B})$$

where $\mathcal{B}$ is the set of alternative hypotheses and $\lambda$ scales the strength of the penalty.

The nature of this similarity function determines how the search space is explored. Ippolito et al. demonstrate that reducing the score of new hypotheses based on token overlap effectively prevents the search from converging on identical sequences. Depending on the application, this penalty can take several forms:

  • String Distance: Fiorini et al. and Lu utilize normalized Levenshtein distance in query auto-completion systems to suppress near-identical variations of the same phrase.
  • Set Overlap: Bing et al. incorporate Jaccard distance constraints to ensure that generated distractors for multiple-choice questions provide distinct options rather than minor lexical tweaks.
  • Token-Level Group Penalties: Vijayakumar formalized this via Diverse Beam Search (DBS). DBS divides the beam budget into parallel groups. Group 1 proceeds via standard beam search. Group 2 is evaluated next, but its token scores are penalized using a Hamming distance metric if they match the tokens chosen by Group 1 at that exact position. This inference-only method forces different groups to explore entirely separate branches of the probability space without requiring model retraining.

Structural and Semantic Diversity

Diversity is not merely about changing individual words; it can also be enforced at structural and semantic levels. For instance, in creative text generation, Wang et al. calculate a diversity score based on differences between part-of-speech templates, penalizing syntactic similarity to maintain distinct grammatical paths during generation.

Alternatively, the penalty can be tied to the model's internal representations. Chen et al. introduce a divergence-based penalty that measures the difference between the current attention distribution and previous steps. By penalizing the model for looking at the same source content twice, this mechanism forces the decoder to traverse unexplored parts of a long document.

Another elegant formulation adapts information retrieval principles to sequence generation. Song et al. introduce MMR-BS, which integrates the Maximal Marginal Relevance algorithm directly into beam search. At each step, the algorithm selects candidates that maximize a weighted combination of relevance to the prompt and dissimilarity to previously selected sequences in the beam, preventing the generation from collapsing into generic, low-information responses.

Stochastic and Pool-Based Alternatives

While deterministic penalties modify the search space explicitly, another way to achieve diversity is through principled probabilistic sampling. Kool et al. developed Stochastic Beam Search, which integrates the Gumbel-Top-$k$ trick into the beam search framework. By adding perturbed log-probabilities to guide the expansion of partial sequences, this method allows for the efficient sampling of diverse sequences without replacement, guaranteeing that all items in the final beam are unique while maintaining rigorous statistical properties.

Finally, instead of enforcing diversity step-by-step during the token generation phase, one can optimize the final set holistically. Jinnai proposes extending Minimum Bayes Risk (MBR) decoding to optimize for both quality and variety. By applying a greedy selection with a diversity penalty over a pre-generated candidate pool, this approach provides a highly tunable trade-off between quality and variety that avoids the early plateaus often encountered by step-wise diverse beam search.

Key Foundational Work

Distraction-Based Neural Networks for Modeling Document (2016) — contributed 1 concept elements to this direction.
A Systematic Exploration of Diversity in Machine Translation (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_diverse_beam_search_c61c3a4e,
  title = {diverse beam search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diverse-beam-search/rdr_c61c3a4ec8544d78bb5856effd09e672},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_diverse_beam_search_c61c3a4e_v1,
  title = {diverse beam search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diverse-beam-search/rdr_c61c3a4ec8544d78bb5856effd09e672/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake