# Parallelism, critical windows, and separations among diffusion language models

arXiv: https://arxiv.org/abs/2609.20539 · HTML: https://mlsanity.com/paper/2609.20539/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 24 of its 59 references that are in the map.
- First posted on arXiv 17 Sep 2026.

## Placed in

- Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/)

## Builds on (most cited first, 24 of 24)

- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Continuous diffusion for categorical data](https://mlsanity.com/paper/2211.15089/) (2022)
- [Flow Map Language Models: One-step Language Modeling via Continuous Denoising](https://mlsanity.com/paper/2602.16813/) (2026)
- [ELF: Embedded Language Flows](https://mlsanity.com/paper/2605.10938/) (2026)
- [Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization](https://mlsanity.com/paper/2402.08095/) (2024)
- [Categorical Flow Maps](https://mlsanity.com/paper/2602.12233/) (2026)
- [The Journey, Not the Destination: How Data Guides Diffusion Models](https://mlsanity.com/paper/2312.06205/) (2023)
- [Scaling Beyond Masked Diffusion Language Models](https://mlsanity.com/paper/2602.15014/) (2026)
- [Probing the Latent Hierarchical Structure of Data via Diffusion Models](https://mlsanity.com/paper/2410.13770/) (2024)
- [Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models](https://mlsanity.com/paper/2506.02318/) (2025)
- [Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees](https://mlsanity.com/paper/2602.15008/) (2026)
- [Error Bounds and Optimal Schedules for Masked Diffusions with Factorized Approximations](https://mlsanity.com/paper/2510.25544/) (2025)
- [DiffusionGemma Technical Report](https://mlsanity.com/paper/2608.00146/) (2026)
- [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026)
- [The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity](https://mlsanity.com/paper/2608.13520/) (2026)
- [Bit-Level Discrete Diffusion with Markov Probabilistic Models: An Improved Framework with Sharp Convergence Bounds under Minimal Assumptions](https://mlsanity.com/paper/2502.07939/) (2025)
- [Provably adaptive sampling with uniform and remasking discrete diffusion models](https://mlsanity.com/paper/2608.23554/) (2026)
- [Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems](https://mlsanity.com/paper/2603.20589/) (2026)
- [Vocabulary-size-independent Convergence of Discrete Diffusion Models: adjoint equations induce the right space](https://mlsanity.com/paper/2605.17232/) (2026)
- [Query Lower Bounds for Diffusion Sampling](https://mlsanity.com/paper/2604.10857/) (2026)
- [The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling](https://mlsanity.com/paper/2608.28949/) (2026)
- [Discrete Flow Matching: Convergence Guarantees Under Minimal Assumptions](https://mlsanity.com/paper/2605.08882/) (2026)
- [A Mathematical Introduction to Diffusion Models](https://mlsanity.com/paper/2607.01693/) (2026)

## Built on by (most cited first, 1 of 1)

- [Lower Bounds for Parallel Diffusion Sampling](https://mlsanity.com/paper/2610.09166/) (2026)

## Abstract (arXiv)

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 widetildeTheta(√d) forward passes are necessary and sufficient to sample using uniform or Gaussian diffusion, yet there exist approximate score oracles for which widetildeOmega(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.