D5P4: Partition Determinantal Point Process for Diversity in Parallel Discrete Diffusion Decoding

Jonathan Lys, Vincent Gripon, Bastien Pasdeloup, Axel Marmoret, Lukas Mauch, Fabien Cardinaux, Ghouthi Boukli Hacene · 2026

Read D5P4: Partition Determinantal Point Process for Diversity in Parallel Discrete Diffusion Decoding by Jonathan Lys, Vincent Gripon, Bastien Pasdeloup, Axel Marmoret, Lukas Mauch, Fabien Cardinaux, Ghouthi Boukli Hacene (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19146.txt.

Introduction

Lys and co-authors improve how discrete diffusion models pick their next draft when they write text. Standard beam search does not fit these models, since each step holds full draft texts, not word prefixes. Their method, D5P4, picks a batch of drafts with a point process that scores both quality and spread. No outside checker is needed. On open writing, questions, and math tasks, it widens the range of good drafts. Quality stays at or above the base methods.

Catalog record

CREATORJonathan Lys, Vincent Gripon, Bastien Pasdeloup, Axel Marmoret, Lukas Mauch, Fabien Cardinaux, Ghouthi Boukli Hacene
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45386
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.19146

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

D5P4: Partition Determinantal Point Process for Diversity in Parallel Discrete Diffusion Decoding Jonathan Lys, Vincent Gripon, Bastien Pasdeloup, Axel Marmoret, Lukas Mauch, Fabien Cardinaux, Ghouthi Boukli Hacene Abstract Discrete diffusion models are promising alternatives to autoregressive approaches for text generation, yet their decoding methods remain under-studied. Standard decoding methods for autoregressive models, such as beam search, do not directly apply to iterative denoising, and existing diffusion decoding techniques provide limited control over in-batch diversity. To bridge this gap, we introduce a generalized beam-search framework for discrete diffusion that generates candidates in parallel and supports modular beam-selection objectives. As a diversity-focused instantiation, we propose D5P4 , which formulates the selection step as MAP inference over a Determinantal Point Process. Leveraging a scalable greedy solver, D5P4 maintains multi-GPU compatibility and enables an explicit trade-off between model probability and target diversity with near-zero compute overhead. Experiments on free-form generation and question answering demonstrate that D5P4 improves diversity over strong baselines while maintaining competitive generation quality. 1 1 1 https://github.com/jonathanlys01/d5p4 1 Introduction Discrete diffusion models have recently emerged as a competitive alternative to autoregressive language models (ARMs), achieving strong performance on a range of generative tasks ( Sahoo et al. 2024 ; Nie et al. 2025 ; Ye et al. 2025 ) . By refining sequences in parallel through iterative denoising, they depart from left-to-right decoding but introduce new structural inference challenges. In practice, discrete diffusion models rely on simple sampling procedures, whereas ARMs benefit from mature decoding algorithms such as beam search to obtain high-quality outputs ( Lowerre 1976 ) . An analogous decoding paradigm for diffusion models remains largely unexplored, as the non-monotonic and parallel nature of diffusion trajectories prevents the application of ARM-specific algorithms. Beyond this algorithmic gap, recent evidence highlights growing limitations in output diversity. In ARMs, Yue et al. 2025 shows that reinforcement learning and supervised fine-tuning substantially improve top-1 performance while saturating output coverage (pass@ k ), indicating reduced diversity. Similarly, in conditioned diffusion models, strong guidance sharpens fidelity at the expense of diversity ( Sadat et al. 2024 ) . Together, these observations motivate decoding algorithms that explicitly reason about in-batch diversity rather than relying on independent sequence scores. To address these challenges, we introduce Partition Determinantal Point Processes for Diversity in Parallel Discrete Diffusion Decoding (D5P4), a novel decoding algorithm tailored for the iterative and parallel nature of discrete diffusion. Rather than scoring candidates independently, D5P4 performs set-level selection, modeling interactions among hypotheses to balance generation quality and diversity. At each diffusion step, D5P4 formulates candidate selection as sampling from a Determinantal Point Process (DPP), a probabilistic model that favors high-quality candidates while repelling similar ones ( Kulesza et al. 2012 ) . To complement the diversity induced by the DPP objective, we introduce a structural partition constraint on candidate selection that prevents lineage collapse, a phenomenon in which hypotheses degenerate toward a single ancestry, as identified in diverse beam search ( Vijayakumar et al. 2016 ) . The resulting selection procedure leverages an efficient greedy MAP solver for the partition DPP. It operates on representations already computed by the diffusion model, therefore incurring negligible overhead and remaining scalable. We evaluate D5P4 on challenging discrete generation tasks, including open-ended text generation and question answering. Experimental results show consistent improvements in diversity over strong decoding baselines, including beam search and prior diversity-promoting methods, while maintaining competitive or superior quality. 2 Related Work 2.1 Discrete diffusion language models Discrete diffusion models originate from early formulations of diffusion processes over discrete variables ( Sohl-Dickstein et al. 2015 ) , later extended to categorical state spaces via multinomial diffusion and argmax-based flows ( Hoogeboom et al. 2021 ) . D3PM ( Austin et al. 2021 ) formalized discrete diffusion as a structured Markov process over vocabulary elements, yielding a unified ELBO-based training objective and accommodating diverse corruption mechanisms, including uniform, Gaussian, and absorbing-state transitions. Absorbing-state diffusion underlies masked diffusion language models (MDLMs), which leverage advances in continuous diffusion ( Ho et al. 2020 ; Rombach et al. 2022 ) and transformer-based architectures ( Peebles & Xie 2023 ) to narrow the performance gap with autoregressive models. Sahoo et al. 2024 introduce a simplified and stable training recipe, while subsequent work shows that large-scale MDLMs can approach autoregressive performance under suitable scaling and fine-tuning regimes ( von Rütte et al. 2025 ; Nie et al. 2024 ; Ye et al. 2025 ) . More recently, models such as LLaDA ( Nie et al. 2025 ) demonstrate competitive instruction-following and in-context learning behavior. A defining characteristic of MDLMs is parallel decoding, where tokens are refined jointly rather than generated left-to-right. While this decouples decoding depth from sequence length, naive parallel refinement often degrades generation quality, as token updates fail to explicitly model inter-token dependencies. As a result, prior work typically frames parallel decoding as a speed–quality trade-off. Several approaches accelerate inference through speculative execution or diffusion-specific key–value caching ( Wu et al. 2025 ; Israel et al. 2025 ; Ma et al. 2025 ; Wang et al. 2025 ) , but largely focus on throughput, not joint quality or diversity across parallel hypotheses. 2.2 Sampling and selection for text generation In autoregressive models, decoding can be interpreted as approximate search over full sequences. Beam search ( Lowerre 1976 ) maintains multiple partial hypotheses, but shared prefixes often lead to rapid collapse into a single ancestral path. Nucleus sampling ( Holtzman et al. 2020 ) promotes diversity via stochastic truncation, yet lacks explicit coordination or comparison across hypotheses. Other methods introduce diversity at selection time, including Diverse Beam Search ( Vijayakumar et al. 2016 ) , stochastic beam search with Gumbel-Top- k sampling ( Kool et al. 2019 ) , and reranking approaches such as Maximal Marginal Relevance ( Carbonell & Goldstein 1998 ) , which explicitly penalize similarity among outputs. Recent work on test-time compute scaling reinforces a “generate many, then select” paradigm, showing that performance can improve substantially by selecting from large candidate pools ( Beeching et al. 2024 ) . For example, Kang et al. 2025 propose self-certainty as a lightweight selection criterion that does not rely on external verifiers. In the context of discrete diffusion, Dang et al. 2025a introduce Particle Gibbs sampling for diffusion language models, enabling reward-guided inference via MCMC/SMC-style resampling over full denoising trajectories. However, this approach does not model interactions between candidate solutions and is therefore not directly comparable to our method. While an adaptation to incorporate such interactions may be possible, the resulting procedure would incur substantial additional test-time cost, scaling with the number of particles, diffusion steps, sampling iterations, and repeated reward evaluations. As a consequence, any direct quantitative comparison would conflate fundamentally different compute regimes and optimization objectives. 2.3 Diversity-aware decoding Recent analyses of reinforcement learning and supervised fine-tuning (SFT) in ARMs ( Dang et al. 2025b ; Yue et al. 2025 ) observe a consistent reduction in output diversity, particularly in reasoning-focused settings. Li et al. 2025 study this phenomenon in the context of SFT and propose a mitigation strategy at training time that improves coverage and benefits test-time scaling. These findings suggest that gains in alignment and fidelity are not necessarily accompanied by broader coverage, further motivating explicit diversity-aware decoding

Read the complete text