Metraipolis › archive › dc_d426ebc3040b

Parallelism, critical windows, and separations among diffusion language models — arXiv:2609.20539

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.20539
License (as archived)
CC0-1.0
Archived
2026-10-10T04:09:06.578Z
SHA-256 of the archived text
82c14fd2df7cfc00ef4b205ba1be705df062fbb130964cde509ae96975afcd4c
Stable URL of this page
https://metraipolis.com/documento/dc_d426ebc3040b

How to cite

Parallelism, critical windows, and separations among diffusion language models — arXiv:2609.20539 — arXiv (en), https://arxiv.org/abs/2609.20539 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d426ebc3040b (Metraipolis archive dc_d426ebc3040b, sha256 82c14fd2df7cfc00ef4b205ba1be705df062fbb130964cde509ae96975afcd4c)
BibTeX
@misc{dcd426ebc3040b,
  title = {Parallelism, critical windows, and separations among diffusion language models — arXiv:2609.20539},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20539},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d426ebc3040b; sha256 82c14fd2df7cfc00ef4b205ba1be705df062fbb130964cde509ae96975afcd4c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20539. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\widetilde{\Theta}(\sqrt{d})$ forward passes are necessary and sufficient to sample using uniform or Gaussian diffusion, yet there exist approximate score oracles for which $\widetilde{\Omega}(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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-18 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Data Structures and Algorithms (cs.DS); Statistics Theory (math.ST); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.20539 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T03:48:18.372Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).