TL;DR
Discrete diffusion language models offer a highly parallel alternative to traditional autoregressive text generation, but they lack structured decoding methods to ensure output variety. This paper introduces D5P4, a beam-style decoding algorithm that uses a partitioned Determinantal Point Process (DPP) to jointly select a diverse, high-quality set of complete intermediate sequences. D5P4 operates entirely using internal model signals, eliminating the need for expensive external verifiers while significantly reducing peak memory and decoding latency.
What Problem Does This Paper Address?
Autoregressive language models generate text token-by-token from left to right, allowing mature search algorithms like beam search to maintain high-quality generation paths. In contrast, discrete diffusion language models (MDLMs) refine entire sequences in parallel through iterative denoising. Because their intermediate states are complete sequences rather than partial prefixes, standard left-to-right beam search cannot be applied.
Furthermore, naive parallel decoding in diffusion models often suffers from two major flaws: lineage collapse (where parallel paths quickly degenerate into near-duplicates of a single ancestry) and mode collapse (where strong decoding guidance, like Classifier-Free Guidance, erodes sample variety). Existing decoding procedures lack a principled way to balance individual sequence quality with the collective diversity of the generated batch.
Methods
The authors propose D5P4 (Partition Determinantal Point Process for Diversity in Parallel Discrete Diffusion Decoding). At each denoising step, the algorithm branches out by generating $w$ descendants for each of the $k$ retained beams. To choose the best $k$ candidates for the next step, D5P4 introduces a three-part selection strategy:
- Transversal Partitioning: Candidates are strictly partitioned into groups based on their parent beam. The algorithm is constrained to select exactly one candidate per group, mechanically preventing early lineage collapse.
- DPP Kernel Construction: It builds a model-internal Determinantal Point Process (DPP) kernel. Individual quality scores are derived from token logits (using normalized negative entropy), while pairwise similarity is computed using the cosine similarity of the model's internal hidden representations right before the unembedding layer.
- Greedy MAP Inference: Instead of sampling randomly from the DPP, it uses a fast, GPU-parallelized greedy Maximum A Posteriori (MAP) solver to deterministically select the most representative, high-quality, and mutually dissimilar set of sequences.
Datasets
The method was evaluated across several generation and reasoning tasks using standard benchmarks:
- Open-Ended Generation: Evaluated using FineWeb samples as the target reference distribution.
- Question Answering: TruthfulQA (mimicking human misconceptions), ARC-Challenge (knowledge-intensive science questions), and CommonSenseQA (everyday commonsense reasoning).
- Mathematical Reasoning: GSM8K (grade-school math word problems).
Key Insights and Ideas
- Batch-Level Optimization Over Independent Selection: Selecting candidates based solely on independent sequence scores inherently limits diversity. Treating decoding as a collective set-selection problem via DPPs allows the model to trade off a fraction of individual quality for a massive gain in global batch diversity.
- Self-Contained Signals are Sufficient: You do not need an expensive external model (like a separate LLM verifier) to score quality and diversity. Internal token logits (entropy) and hidden states serve as excellent proxies for external perplexity and semantic similarity.
- Decoupling Guidance from Mode Collapse: Strong Classifier-Free Guidance (CFG) typically erodes sample variety. D5P4 successfully decouples guidance-induced alignment from mode collapse, preserving high diversity even under heavy guidance regimes.
Key Results
- Superior Quality-Diversity Pareto Fronts: In open-ended generation, D5P4 achieves a more favorable trade-off between perplexity (quality) and cosine similarity (diversity), delaying the onset of quality collapse under high diversity pressure compared to alternative methods like Diverse Beam Search (DivBS) or categorical sampling (CAT).
- Higher Solution Coverage: On GSM8K, D5P4 significantly boosts
pass@4coverage (reaching up to 72.2% in the stochastic regime), outperforming all model-internal baselines. On TruthfulQA and ARC-Challenge, it achieves highermax F1scores, proving it explores the solution space more effectively. - CFG Mitigation: D5P4 maintains much higher diversity (lower self-cosine similarity) across various CFG scales compared to Greedy Beam Search and Best-of-N methods, effectively flattening the diversity degradation curve.
- Computational and Memory Efficiency: Surprisingly, adding structured selection improves end-to-end hardware efficiency. By shifting the $n$ sampling operations into $w$ independent samples from $k$ sources, D5P4 reduces categorical sampling time by nearly 10x and cuts peak GPU memory usage by 40% in large-batch settings.
Limitations and Future Work
- Proxy Reliability: The method relies heavily on internal model proxies (logits and hidden states). If these internal representations are poorly calibrated or suffer from representation collapse, the selection quality will degrade.
- Future Directions: The authors suggest exploring task-aware kernels to better align diversity metrics with specific task demands (e.g., functional diversity in code generation). Additionally, extending this partition-DPP framework to non-text domains, such as image or multimodal discrete diffusion models, remains an open and promising direction.
Summary updated