Masked Diffusion Needs More Steps Than Uniform Diffusion

On September 13, 2026, Sitan Chen (Harvard SEAS) and Liye Wang (Tsinghua University) posted a 90-page preprint establishing the first provable separation in forward-pass complexity between the three dominant paradigms for diffusion-based sequence generation. Their paper, arXiv:2609.20539, shows that for a specific hard family of distributions, uniform and Gaussian diffusion require roughly Õ(√d) forward passes to generate an accurate sample, while masked diffusion requires Ω̃(d) forward passes, a gap of √d regardless of how the sampling algorithm is tuned. All three paradigms had been lumped together as “non-autoregressive” alternatives to standard left-to-right decoding. This result shows they are not equivalent.

Three Paradigms, One Shared Goal

Diffusion language models share a common structure: learn to reverse a corruption process. Autoregressive models are themselves a special case where the corruption process is sequential right-to-left erasure, generating one token per forward pass. Alternative corruption processes can in principle allow generation of a length-d sequence in fewer than d forward passes, but how many fewer, and under what conditions, was not rigorously understood before this work.

Chen and Wang compare three leading paradigms. In masked diffusion, at noise level t each token is masked independently with probability 1 − e^−t; once unmasked during generation, tokens are committed and cannot be revised. In uniform diffusion, each token is reassigned uniformly at random with the same probability, and tokens can be revised at each step. In Gaussian diffusion, clean one-hot token embeddings are corrupted via Brownian motion, producing e^−tX₀ + σₙG where G is standard Gaussian noise; all coordinates are updated every step.

The standard practitioner intuition was that masked diffusion is harder to parallelize because its token commitment is irreversible, while uniform and Gaussian diffusion can progressively revise outputs. Chen and Wang show the commitment mechanism is not the source of the gap. The real source is something more specific, and more useful to know.

Result 1: All Three Scale With the Intrinsic Complexity of the Distribution

Before the separation result, the paper closes a gap in positive results. Prior work (Chen, Cong, and Li; Lavenant and Zanella) had shown that masked diffusion can sample from any distribution q using a number of forward passes scaling with the dual total correlation, DTC(q). The dual total correlation measures how much entropy in the distribution is not explained by local conditional entropies H(Xᵏ | X_−i): informally, the total long-range dependency structure of the data. When DTC(q) is much smaller than the context length d, masked diffusion can generate samples in far fewer than d steps.

No corresponding guarantee existed for uniform or Gaussian diffusion. Theorems 1.1 and 1.2 of the paper fill this gap. For any categorical distribution q, there is an algorithm that uses Õ(DTC(q)/ε) uniform diffusion score oracle queries to produce a sample with KL divergence at most ε from q (Theorem 1.1). The same rate holds for Gaussian diffusion (Theorem 1.2). Both results match what was previously known only for masked diffusion.

The proof technique is a deliberate departure from the masked diffusion case. That earlier work used an exact characterization of the sampling error to tune step sizes directly. For uniform and Gaussian diffusion, no such exact characterization is available. Instead, Chen and Wang prove a reverse data processing inequality: the KL distance between two distributions cannot contract too quickly under small additive noise. This lets them bound the error at each sampling step by the drop in DTC(q) at that step, then telescope those bounds across the entire schedule to obtain a total error scaling linearly in DTC(q). A concurrent independent result by Dmitriev, Huang, and Wei reached a similar DTC-adaptive bound for uniform diffusion via related ideas.

Result 2: The Separation

Theorems 1.1 and 1.2 show all three paradigms are equally capable of adapting to DTC. They leave open whether a distribution exists where the paradigms genuinely differ. Theorems 1.3 and 1.4 answer that: yes, and the gap is a square-root factor in query count.

The hard distribution is a family of random empirical measures: distributions supported on 2^Θ(d) points drawn uniformly at random from the Boolean hypercube, where a constant κ (with 0 < κ < log 2) is unknown to the sampling algorithm. For this family, DTC(q) = Θ(d), which means the DTC-adaptive bound from Result 1 gives only an Õ(d) guarantee for all three paradigms. But for uniform and Gaussian diffusion, Theorem 1.3 shows Õ(√d/ε²) queries are sufficient, a strictly better rate. And Theorem 1.4 shows that for masked diffusion, any algorithm using fewer than Ω̃(d) oracle queries produces samples at total variation distance at least 0.99 from the true distribution, with high probability. This holds for every possible sampling algorithm, not just specific ones.

The separation is a factor of √d in query complexity.

The Critical Window Mechanism

The interesting part is where the separation comes from. The Outlook section of the paper states this directly: “In contrast with prior heuristic reasoning which suggested that masked diffusion is less amenable to parallelism because it cannot revise the tokens it commits to during sampling, we showed that the origin of this separation comes from a different mechanism.”

That mechanism is the width of each process’s critical window: the narrow band of noise levels over which the posterior transitions from uninformative, meaning indistinguishable from the prior, to sharply concentrated on the correct sample. Outside this band the score oracle provides no useful signal about the underlying distribution. Inside it, the distribution can be recovered with one-step decoding. A sampler must spend oracle queries to locate and cross this window before it can generate accurate samples.

What differs between paradigms is how wide this window is:

Masked diffusion: the informative noise range occupies an O(log(d)/d) fraction of the full noise spectrum (Proposition 8.6). Window width decays as 1/d.
Uniform and Gaussian diffusion: the informative range occupies an O(log(√d)/√d) fraction (Propositions 6.4 and 7.4). Window width decays as 1/√d.

The simulation in Figure 4 of the paper, run at κ = 0.2, shows this directly. Plotting the probability that the posterior at a given noise level recovers the planted distribution against the information per coordinate, the masked diffusion transition is visibly sharper and narrower than the uniform and Gaussian transitions, and its width shrinks faster as d increases.

The algorithmic consequence follows from this geometry. To locate the window for uniform or Gaussian diffusion, Õ(√d) queries suffice; the window is wide enough to hit with a coarse search. For masked diffusion, the window occupies only an O(log(d)/d) fraction of the spectrum, and finding it requires Ω̃(d) queries. Once the window is found for uniform and Gaussian diffusion, above it the score is well-approximated by the score of the uniform distribution, and below it one-step decoding recovers the correct sample. Masked diffusion cannot exploit this two-regime structure as efficiently because the transition is too narrow to navigate cheaply.

The authors note this is the first connection between critical window width and discretization error in diffusion sampling. Prior work studied critical windows, also called speciation transitions, as a descriptive phenomenon in trained models. This paper uses them constructively, as the engine of an upper-bound proof.

Limitations and Open Questions

Chen and Wang are clear that this is not a verdict against masked diffusion. The paper “should not be interpreted reductively as advocating for one paradigm over another.” Three specific limitations bound the scope of the result.

First, the separation is proved over a specific constructed family of distributions. Whether a similar separation exists over natural language distributions is not addressed and remains open. The Boolean hypercube random empirical measure is a clean theoretical object; text corpora are not.

Second, masked diffusion has practical advantages that this analysis does not touch. The paper names any-order generation capability specifically, noting it is “poorly understood in theory but incredibly relevant in practice.” A system that needs to generate tokens in non-left-to-right order may still favor masked diffusion regardless of what this result says about forward-pass count.

Third, the Gaussian diffusion results use only basic one-hot embedding into Euclidean space. Richer encoding maps are unexplored and may shift the picture for Gaussian diffusion in practice.

The paper also includes an explicit AI usage disclosure. The telescoping argument at the core of the DTC-adaptive rates in Theorems 1.1 and 1.2 was suggested by a frontier AI model. AI also proposed a simpler test statistic for locating the critical window than the one the authors had initially developed, and made the observation that one-step decoding suffices below the critical window, simplifying a previously complicated sub-argument. A coding agent implemented the numerical simulation in Figure 4 from scratch. The authors describe verifying these contributions and incorporating them, with remaining proof structure human-written.

What This Means for Engineering Teams

If this theoretical separation survives contact with empirical work, the practical consequence is that the choice of diffusion process becomes a first-order serving decision when building large language models on diffusion architectures. Two models that both escape autoregression may require asymptotically different compute at inference time for the same target distribution, by a factor that grows as √d with sequence length.

For teams currently building or evaluating diffusion LLMs, several concrete things follow from this framework. Forward-pass count at inference is not determined by sequence length alone; it is jointly determined by sequence length and the distributional complexity of the target domain. On distributions with DTC much smaller than d, all three paradigms achieve similar step counts and the practical difference may be negligible. On high-complexity distributions where DTC is close to d, masked diffusion may require substantially more steps to achieve the same output quality as uniform or Gaussian variants.

The immediate practical recommendation is to track whether this theoretical separation appears in empirical benchmarks on the target domain. Papers such as Adaptive Parallel Decoding (arXiv:2506.00413), which benchmarks forward-pass efficiency across diffusion LLMs on real tasks, are the right place to check whether the theoretical gap manifests at deployment-relevant scale and domain.

Teams working on AI system design who are choosing between diffusion architectures should also treat the dual total correlation as a diagnostic tool. Computing or estimating DTC(q) for the target data distribution gives a meaningful signal about which paradigm will require fewer steps at inference. This analysis reframes the design question: instead of asking which diffusion model performs best on a general benchmark, ask which corruption process the distributional structure of the target domain makes most efficient. Teams building domain-specific language models have concentrated distributions by definition, and the answer may differ sharply from the general case.

Key Takeaways

Sitan Chen (Harvard SEAS) and Liye Wang (Tsinghua University) published arXiv:2609.20539 on September 13, 2026, establishing the first provable parallelism separation among the three main diffusion language model families.
All three paradigms, masked, uniform, and Gaussian diffusion, can adapt query count to the dual total correlation (DTC) of the target distribution, scaling sublinearly in context length when DTC is small (Theorems 1.1 and 1.2).
For a specific hard family of distributions with DTC = Θ(d), uniform and Gaussian diffusion require Õ(√d) forward passes. Masked diffusion requires Ω̃(d) forward passes. This is a factor of √d separation (Theorems 1.3 and 1.4).
The source of the gap is not the token-commitment mechanism. It is the width of the critical window: masked diffusion’s informative noise range is O(log(d)/d) wide; uniform and Gaussian diffusion’s is O(log(d)/√d) wide, a factor of √d wider.
A wider critical window is easier for the sampler to locate with fewer queries. Masked diffusion’s narrower window forces more queries even under an optimal sampling algorithm.
The result is theoretical and uses a constructed hard distribution. Whether the separation appears on natural language distributions is an open question the authors explicitly leave unresolved.
Masked diffusion retains practical advantages, including any-order generation capability, that this analysis does not address and does not diminish.

Work With Origins AI

Origins AI builds production AI systems for engineering teams. If you are choosing a diffusion architecture for a domain-specific language model and need to reason about inference-time compute across paradigms, talk to our team.