- 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
Author Response (2/2)
Regarding the reviewer's specific questions:
-
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.
-
Accuracy exponent and comparison across paradigms: The exponent can be made explicit, though we made no attempt to optimize it in our proofs. For example, specializing to the interval , we first fix , then choose , and apply Lemmas F.8 and G.9 with and concentration exponent . This yields and , respectively. Consequently, it suffices to take and 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 and remains for any fixed inverse-polynomial score accuracy. The uniform, Gaussian, and masked oracle errors are measured using Bregman divergence, scaled 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 in Theorem 4.2 and its Gaussian counterpart, we can choose in Theorem 4.3 with a sufficiently larger constant , so that the masked oracle is required to be substantially more accurate, while the masked lower bound — and hence the separation — still holds.
-
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 product distributions satisfies , which can be much smaller than the trivial bound . 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 , where 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.
-
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.
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), and the lower bound remains Ω(d/logd) in d for any inverse-polynomial accuracy η=d−Θ(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))B for any sufficiently large constant B. 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.