acceptodds
Under review as a conference paper at ICLR 2027

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. We prove: - 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 forward passes are necessary and sufficient to sample using uniform or Gaussian diffusion, yet there exist approximate score oracles for which 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.

Primary area:
learning theory
Keywords:
diffusion language models, discretization analysis, parallel sampling, query complexity, speciation, critical windows

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_zXq4OpenReview ↗
Rating
4
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper compares the few-step (parallel) sampling ability of three diffusion-LM paradigms, measured as the number of queries to an approximate score oracle. (1) It shows uniform and Gaussian diffusion can sample with Õ(DTC(q)/ε) queries, matching the dual-total-correlation rate previously known only for masked diffusion; the proof uses a reverse data-processing inequality and a telescoping argument. (2) For a random codebook of e^{κd} points on the hypercube, it shows Θ̃(√d) queries are necessary and sufficient for uniform/Gaussian diffusion, while there exists a 1/poly(d)-accurate masked oracle forcing Ω̃(d) queries. The separation is attributed to the masked critical window being narrower (O(log d/d) vs O(√(log d/d)) of the noise range).

Critical strengths

The first provable separation among the three dLLM paradigms, and the mechanism identified (critical-window width rather than “commitment”) is a new and non-obvious explanation. Notably, the masked lower bound rules out all algorithms using the oracle, so remasking/correction schemes do not escape it.

Critical weaknesses

The separation is worst-case over adversarial approximate oracles, not a property of the diffusion processes themselves. With an exact masked oracle on this instance, the critical level could seemingly be located by binary search over m in O(log d) queries. So the result is really about robustness to 1/poly(d) score error, and the oracle is allowed to behave arbitrarily on inconsistent partial assignments, which is exactly where the construction gains its freedom. The abstract/introduction frame this as a separation in “parallelism” without making this clear. Practical relevance is asserted rather than shown. The separating instance (uniform random codebook) is far from language data, and the only experiment (Fig. 3) measures posterior recovery probability, not the step count of any actual sampler, let alone a trained dLLM. Both paradigms also require score error e^{-BΛ} with an unspecified exponent B, so it is unclear whether the regime applies at realistic error levels.

Questions for authors

(Clarification) Does the Ω̃(d) masked lower bound survive with an exact oracle (η = 0)? If not, please state explicitly that the separation is driven by score-error tolerance. (Clarification) How large is the exponent B in Theorem 4.2 and the analogous requirement in Theorem 4.3? Are the required accuracies comparable across the three paradigms given that the error metrics differ (Bregman, L2, KL)? (Clarification) Theorem 3.1/3.2 assume a known upper bound DTC ≥ DTC(q). Does the masked result of Chen et al. (2026) need the same, and how is this bound obtained in practice? (Suggestion) Any evidence, even on a small trained model, that critical-window width predicts the number of steps needed?

2 comments
AuthorsOpenReview ↗

Author Response (1/2)

We thank the reviewer for recognizing the novelty of our separation and its critical-window explanation!

We emphasize that our separation concerns query complexity under approximate score access. This is a standard setting for establishing oracle query lower bounds in diffusion sampling, as demonstrated by recent works such as [1-3]. Such results characterize the robustness of sampling algorithms to imperfect scores, which is particularly relevant because practical diffusion models provide learned score estimates rather than exact scores.

Regarding practical relevance, as already discussed in our Introduction, differences in few-step generation capabilities among masked, uniform, and Gaussian diffusion language models have been extensively reported in empirical studies (see, e.g., [4–6]). These observations motivate our theoretical investigation into how the choice of corruption process affects parallel sampling, and our objective is to identify a clean mathematical mechanism that can explain such differences.

As discussed in our responses to reviewers xzZt and YPJN, our random empirical measure is not intended as a literal model of natural language, but rather as a minimal model of the critical-window phenomenon that already suffices to establish the separation. Such abrupt transitions have been observed extensively in language modeling, even in autoregressive settings like the "pivotal tokens" in [7], and critical windows more broadly in [8]. They have also been studied in diffusion models, including speciation and collapse transitions in [9], hierarchical feature-recovery transitions in [10], and spontaneous symmetry breaking in [11].

We also wish to clarify the reviewer's concern about the required score accuracy. For our masked lower bound, Theorem 4.3 applies to any prescribed η∈(0,1/10)\eta\in(0,1/10), and the lower bound remains Ω(d/log⁡d)\Omega(d/\log d) in dd for any inverse-polynomial accuracy η=d−Θ(1)\eta=d^{-\Theta(1)}. In reality the score error should be even higher, which makes our lower bound even stronger. The uniform and Gaussian upper bounds also require only inverse-polynomial score accuracy, expressed as e−BΛ=(εδ/(Cd))Be^{-B\Lambda}=(\varepsilon\delta/(Cd))^B for any sufficiently large constant BB. Such polynomial accuracy assumptions are ubiquitous in theoretical analyses of approximate scores.

Finally, we emphasize that our general DTC-adaptive upper bounds in Theorems 3.1 and 3.2 are another significant contribution of the paper, independent of the separation result. These results work for any approximate score with a bounded amount of error, and thus trivially also hold for exact score. Furthermore, these bounds make no structural assumptions about the underlying data distribution.


References

[1] Xun and Price, Query Lower Bounds for Diffusion Sampling, NeurIPS 2026.

[2] Kou and Wang, Lower Bounds for Parallel Diffusion Sampling, 2026.

[3] Chen et al., Optimal Inference Schedules for Masked Diffusion Models, COLT 2026.

[4] Sahoo et al., The Diffusion Duality, ICML 2025.

[5] Lee et al., Flow Map Language Models: One-step Language Modeling via Continuous Denoising, 2026.

[6] Hu et al., ELF: Embedded Language Flows, 2026.

[7] Abdin et al., Phi-4 Technical Report, 2024.

[8] Li et al., Blink of an eye: a simple theory for feature localization in generative models, ICML 2025.

[9] Biroli et al., Dynamical Regimes of Diffusion Models, Nature Communications 2024.

[10] Sclocchi et al., A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data, PNAS 2025.

[11] Raya and Ambrogioni, Spontaneous Symmetry Breaking in Generative Diffusion Models, NeurIPS 2023.

AuthorsOpenReview ↗

Author Response (2/2)

Regarding the reviewer's specific questions:

  1. Exact score access: As explicitly stated in Theorem 1.4 and formalized in Theorem 4.3, there exists an approximate masked score oracle family satisfying the prescribed accuracy guarantee under which the lower bound holds. The oracle's freedom on inconsistent partial assignments is not the sole source of hardness; on consistent assignments, sufficiently small conditional biases can also be suppressed within the permitted score error. Exact oracle access is therefore a different information model.

  2. Accuracy exponent and comparison across paradigms: The exponent BB can be made explicit, though we made no attempt to optimize it in our proofs. For example, specializing to the interval κ∈[0.20,0.21]\kappa\in[0.20,0.21], we first fix K=12K=12, then choose A=32A=32, and apply Lemmas F.8 and G.9 with L=3L=3 and concentration exponent 1515. This yields CU=3586C_{\sf U}=3586 and CG=13112C_{\sf G}=13112, respectively. Consequently, it suffices to take BU≥3600B_{\sf U}\ge3600 and BG≥6563B_{\sf G}\ge6563 for the estimates in window detection, under the auxiliary conditions of this calculation. These numerical values are very conservative and not intended to reflect the accuracy requirements in practice. Theorem 4.3 imposes no analogous fixed exponent requirement: the masked lower bound holds for any η∈(0,1/10)\eta\in(0,1/10) and remains Ω~(d)\widetilde\Omega(d) for any fixed inverse-polynomial score accuracy. The uniform, Gaussian, and masked oracle errors are measured using Bregman divergence, scaled L2L^2 error, and averaged conditional KL, respectively, since these choices are closely aligned with the training losses used in practice. In fact, we could use the same error measure across all three paradigms by formulating the errors in terms of posterior marginals, and still obtain the separation. More importantly, for any admissible choice of BB in Theorem 4.2 and its Gaussian counterpart, we can choose η=d−b\eta=d^{-b} in Theorem 4.3 with a sufficiently larger constant bb, so that the masked oracle is required to be substantially more accurate, while the masked lower bound — and hence the separation — still holds.

  3. DTC upper bound: Chen et al. (2026) likewise assume a supplied upper bound on DTC. Such a bound can often be obtained from structural information about the data distribution. For example, a mixture of at most 2n2^n product distributions satisfies DTC(q)≤nlog⁡2\mathrm{DTC}(q)\le n\log 2, which can be much smaller than the trivial bound dlog⁡Sd\log S. Moreover, our rate is "adaptive" in the sense that even if we use a schedule based on an incorrect DTC estimate, the discretization error in our algorithms still scales as O~(DTC(q)/T)\widetilde O(\mathrm{DTC}(q)/T), where TT is the number of steps used by that schedule. Thus, a valid upper bound is needed to guarantee a prescribed accuracy, but not to run the algorithm or obtain a DTC-dependent error bound.

  4. Experiments on trained models: We thank the reviewer for the nice suggestion to run an experiment on a small trained model, which we will pursue in empirical follow-up work to this submission. As a theory submission, this paper’s objective was to identify a minimal mathematical model to explain the observed gap in parallelism between masked diffusions and other paradigms. This observation has been widely reported in the empirical literature on diffusion language models.

Reviewer_YPJNOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proves theoretical results on how many forward passes masked, uniform and Gaussian diffusion models need to sample, i.e. how far parallel sampling can be pushed. It shows that uniform and Gaussian diffusion match the known masked-diffusion bounds. Furthermore, on random codebooks, they need fewer passes than masked diffusion. The authors attribute this gap to masked diffusion's narrower critical window, not to token commitment.

Critical strengths
  • The paper is very dense in theory, but the authors make a clear effort to derive, explain and contextualize it (informal theorems, intuition figures and proof sketches), which I especially appreciate.

  • The paper also challenges the common intuition that masked diffusion parallelizes worse because it commits to tokens and instead relates it to narrower critical windows.

Critical weaknesses
  • The findings in the paper are all theoretical. While the authors state this clearly in many parts of the paper, it would be interesting to reason about how the theoretical findings would apply to real data. As far as I understood, the data assumed for the separation result are random samples from the Boolean hypercube without any structure. How does having structure in the data (e.g. textual data) impact this?
Questions for authors

See weaknesses.

3 comments

We thank the reviewer for the encouraging feedback and thoughtful question!

As discussed in our response to xzZt, the key phenomenon our construction aims to capture is the existence of sharp critical windows. Such behavior is ubiquitous across generative modeling paradigms, including autoregressive and diffusion-based language modeling (see [1]), as well as Gaussian diffusion on real image data. For instance, Figure 4 of [2] illustrates a sharp transition in memorization, while [3] identifies distinct speciation and collapse transitions, [4] studies sharp transitions in hierarchical feature recovery, and [5] investigates spontaneous symmetry breaking in generative dynamics. Moreover, sharp phase transitions also arise in highly structured statistical models, including sparse tensor PCA (see [6]) and low-rank matrix recovery (see [7]).

The critical-window phenomenon also has a natural interpretation in terms of error correcting codes: as more coordinates are revealed, the posterior can rapidly transition from being spread across many codewords to concentrating on a particular one. Random codes are the easiest object to instantiate to get error correction properties, but highly algebraic structure is present in real error correcting codes. Thus, the phenomenon is not inherently tied to whether the data has a structure.

More generally, real data often exhibits substantial geometric or combinatorial structure, such as low intrinsic dimension, sparsity, low rank, or sequential constraints. In ongoing work, we have extended our masked lower-bound construction to random empirical measures drawn from arbitrary discrete background distributions ν\nu, with the codebook size hidden from the sampling algorithm. Writing d∗=H∞(ν)d_* = H_\infty(\nu) for the intrinsic entropy dimension, we establish a query lower bound of Ω(d∗/(1+log⁡(S/η)))\Omega(d_*/(1+\log(S/\eta))) under approximate masked score access, where SS is the alphabet size and η\eta is the permitted score error. For constant alphabet size and inverse-polynomial accuracy in d∗d_*, this gives a lower bound Ω~(d∗)\widetilde\Omega(d_*). Examples include:

  • Sparse rank-one tensors: Ω~(slog⁡(en/s))\widetilde\Omega(s\log(en/s)) for tensors generated by ss-sparse vectors in nn dimensions.

  • Low-rank matrices: Ω~(r(m+n−r))\widetilde\Omega(r(m+n-r)) for rank-rr matrices over F2\mathbb F_2 of size m×nm\times n.

  • Constrained sequences: Ω~(1+log⁡(D−1s))\widetilde\Omega(1+\log\binom{D-1}{s}) for binary sequences of length DD with exactly ss change points.

These examples illustrate that the masked sampling obstruction can persist under substantial nonlinear or combinatorial structure, with complexity governed by intrinsic entropy rather than ambient dimension.

References

[1] Li et al., Blink of an eye: a simple theory for feature localization in generative models, ICML 2025.

[2] Song et al., Selective Underfitting in Diffusion Models, 2025.

[3] Biroli et al., Dynamical Regimes of Diffusion Models, Nature Communications 2024.

[4] Sclocchi et al., A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data, PNAS 2025.

[5] Raya and Ambrogioni, Spontaneous Symmetry Breaking in Generative Diffusion Models, NeurIPS 2023.

[6] Niles-Weed and Zadik, The All-or-Nothing Phenomenon in Sparse Tensor PCA, NeurIPS 2020.

[7] Donoho et al., The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising, PNAS 2013.

We kindly ask the reviewer to review our rebuttal. If it addresses your concerns, we would greatly appreciate your acknowledgement and the potential reconsideration of the score. We also welcome any remaining questions or concerns and would be happy to address them during the discussion period.

Thanks for answering to my review. I still believe that having empirical results would be an strong addition to the paper, but as other reviewers agree, the paper has merit and should be accepted.

Reviewer_xzZtOpenReview ↗
Rating
4
Confidence
3(+1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper poses a question about the theoretical limits of parallelism for diffusion language model inference. It identifies the concept of a critical window as a possibly determinative factor for theoretically achievable parallelism, and argues that the masked diffusion may be inherently less amenable to parallel sampling because it can exhibit shorter critical windows than Gaussian or uniform-state diffusion.

Critical strengths

This paper is well-written! The best in my batch this cycle by far. I thank the authors for taking the time to make their work presentable.

The extensions of general upper bounds on query complexity from masked diffusion to uniform state and Gaussian diffusion (Theorem 1.1, Theorem 1.2) are a valuable contribution to the literature. They also seem to introduce interesting new proof techniques to this analysis (I did not carefully evaluate the proofs).

The random empirical measure construction and ensuing analysis of critical windows is thought-provoking. I will need to think more about whether critical windows are the right way to think about lower bounds on inference time when modeling the empirical distribution of text.

Critical weaknesses

Like most ML theory papers this paper is descriptive, not prescriptive. It's unclear exactly how to operationalize these ideas into improved diffusion language modeling techniques. As a practitioner that this paper made me think differently about diffusion parallelism, which is enough to make me recommend acceptance.

Questions for authors

To what extent do the random empirical measures construction reflect the empirical distribution of language? It could help to share some thoughts and intuitions about the degree to which these constructions are representative of the data distributions we care about. To be clear, I think the separation results are interesting regardless of whether the distributions are natural.

2 comments

We thank the reviewer for the positive assessment and thoughtful question!

Our random empirical measure is not intended to be a literal model of natural language, but rather the simplest setting in which we can rigorously capture the phenomenon of a sharp critical window. There is empirical evidence for analogous phenomena in language modeling, including the "pivotal tokens" identified in [1], the critical windows studied in [2] with empirical LLM observations, and the "forking tokens" in [3] observed across various language generation tasks. Such sharp transitions are ubiquitous in generative diffusion models. For example, [4] identify distinct speciation and collapse transitions in diffusion dynamics, [5] study sharp transitions in hierarchical feature recovery, and [6] demonstrate spontaneous symmetry breaking in generative diffusion models. The key phenomenon we seek to model is that, as generation proceeds, the posterior can rapidly transition from being spread across many possibilities to concentrating on a particular feature or outcome.

Importantly, a single sharp transition suffices to establish our separation, and random empirical measures provide a particularly tractable setting in which to analyze it. For realistic long-context language distributions, we expect a richer hierarchy of features, potentially giving rise to multiple critical windows at different scales. Such distributions may therefore be better modeled by a multiscale version of our construction. Moreover, in ongoing unpublished work, we have extended our analysis to more general random empirical measures drawn from arbitrary background distributions on the sphere satisfying a suitable dimension-free concentration inequality for convex Lipschitz functions, further illustrating the generality of the critical-window phenomenon.


References

[1] Abdin et al., Phi-4 Technical Report, 2024.

[2] Li et al., Blink of an eye: a simple theory for feature localization in generative models, ICML 2025.

[3] Bigelow et al., Forking Paths in Neural Text Generation, ICLR 2025.

[4] Biroli et al., Dynamical Regimes of Diffusion Models, Nature Communications 2024.

[5] Sclocchi et al., A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data, PNAS 2025.

[6] Raya and Ambrogioni, Spontaneous Symmetry Breaking in Generative Diffusion Models, NeurIPS 2023.

Reviewer_xzZtOpenReview ↗

Thanks

I reiterate my position that this is a good paper and should be accepted. I have edited my main review to increase my confidence score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.