Parallelism, critical windows, and separations among diffusion language models
Abstract
A popular selling point of diffusion large language models (dLLMs) is their capacity for parallelism: the ability to generate sequences of text far more efficiently than autoregressive models, which require one forward pass per token. Yet among the many competing paradigms for dLLMs, from masked to uniform to Gaussian diffusion, principled understanding of how these different proposals compare in parallelism remains limited. In this work, we initiate a fine-grained comparison of the capacity for parallelism among these three leading approaches and prove the following: - Uniform and Gaussian diffusion can sample in a number of forward passes which scales with the dual total correlation of the underlying distribution, a measure of intrinsic complexity which can be much smaller than the context length. Previously, it was only known how to achieve this using masked diffusion. - For a certain family of random empirical measures, we show that Θ̃(√d) forward passes are necessary and sufficient to sample using uniform or Gaussian diffusion, yet there exist approximate score oracles for which Ω̃(d) forward passes are needed for masked diffusion. This establishes the first provable separation in parallelism between the three prevailing dLLM paradigms. Contrary to popular intuition that masked diffusions are harder to parallelize because they must commit to token values, the latter separation instead comes from the fact that the critical windows in masked diffusion sampling are asymptotically narrower than those in uniform and Gaussian diffusion sampling.
Related
- Why we should condition denoising diffusion generative models on windows of past observations
- Strong solutions of SDEs with critical discontinuities in diffusion coefficients
- Absence of gelation and regularity for coagulation-fragmentation-diffusion equations with critical coagulation rate in low dimension
- Linear maps of C*-algebras preserving norm parallelism
- Continuous Diffusion Scales Competitively with Discrete Diffusion for Language
BibTeX
@misc{chen2026parallelism,
title = {{Parallelism, critical windows, and separations among diffusion language models}},
author = {Sitan Chen and Liye Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20539},
eprint = {2609.20539},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20539},
}
RIS
TY - UNPB
TI - Parallelism, critical windows, and separations among diffusion language models
AU - Sitan Chen
AU - Liye Wang
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.20539
UR - https://arxiv.org/abs/2609.20539
AB - A popular selling point of diffusion large language models (dLLMs) is their capacity for parallelism: the ability to generate sequences of text far more efficiently than autoregressive models, which require one forward pass per token. Yet among the many competing paradigms for dLLMs, from masked to uniform to Gaussian diffusion, principled understanding of how these different proposals compare in parallelism remains limited. In this work, we initiate a fine-grained comparison of the capacity for parallelism among these three leading approaches and prove the following: - Uniform and Gaussian diffusion can sample in a number of forward passes which scales with the dual total correlation of the underlying distribution, a measure of intrinsic complexity which can be much smaller than the context length. Previously, it was only known how to achieve this using masked diffusion. - For a certain family of random empirical measures, we show that Θ̃(√d) forward passes are necessary and sufficient to sample using uniform or Gaussian diffusion, yet there exist approximate score oracles for which Ω̃(d) forward passes are needed for masked diffusion. This establishes the first provable separation in parallelism between the three prevailing dLLM paradigms. Contrary to popular intuition that masked diffusions are harder to parallelize because they must commit to token values, the latter separation instead comes from the fact that the critical windows in masked diffusion sampling are asymptotically narrower than those in uniform and Gaussian diffusion sampling.
ER -