acceptodds
Under review as a conference paper at ICLR 2027

Revision Provably Reduces Sequential Computation in Diffusion Language Models

Abstract

Diffusion language models (DLMs) generate multiple tokens with a single forward pass per decoding round, achieving greater parallelism than autoregressive models (ARMs). Revision promises further reductions in sequential computation by allowing a DLM to overwrite previously generated tokens and thereby reducing the number of decoding rounds. Yet it remains unclear whether this advantage persists as DLMs evolve. To assess the expressive power of DLMs with and without revision, we work in a model where each Transformer's decoding round uses computation. We compare the minimum number of rounds each class needs to sample , where the word is uniform on and is the membership function of a binary regular language . We show that revision yields an asymptotic advantage. A DLM with revision exactly samples this distribution in at most two rounds without chain-of-thought (CoT) positions. However, a DLM without revision has tight round complexity even with a constant number of CoT positions for every , that is, every regular language whose membership cannot be computed by such circuits. Moreover, for every such and every constant , CoT positions do not suffice to sample this distribution in constant rounds without revision. We further show a separation when the goal is to approximately sample a length- word uniformly from some regular language . These results provide a theoretical framework for understanding how revision reduces sequential computation and expands the scope of parallel speedups achievable by DLMs.

Primary area:
learning theory
Keywords:
Theory, Diffusion Language Models, Circuit Complexity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_wbzgOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3(+1)
Soundness
2
Read review
Paper summary

This paper presents a theoretical analysis on how revision affects decoding in DLMs. The paper focuses on a particular type of circuits known as AC0AC^0 circuits and limits the analysis to binary languages and polynomial width transformers. One of the main results proven under these conditions is that an DLM with revision can exactly sample input-output pairs for any binary regular languages in at most two rounds without relying on CoT.

Critical strengths

The main strength of this paper is its theoretical analysis. Although it is done in rather artificial/constrained setup with somewhat unrealistic assumptions about modern day DLMs or natural language, I do understand and appreciate the effort that would have gone into the rigorous mathematical analysis presented in the paper. In particular, the side-by-side comparison of computational complexity of the decoding process between DLM vs. autoregressive LMs is instructive. The effect of CoT vs. revision is also something interesting to know.

Critical weaknesses
  • My main concern is the practical real-world impact of the findings reported in the paper. The modelling assumption are quite artificial and does not adhere to the modern-day DLMs and the natural languages which are used in those DLMs. No one really trains DLMs with binary regular languages and I wonder whether the findings made in this paper would be any practical use to the people using DLMs for real world tasks such as natural language generation.
Questions for authors

Can you comment on the significance of the asymptotic gap you had derived? The complexity for the DLMs with revision is O(log⁡n/log⁡log⁡n)O(\log n / \log \log n). For the typical sequence lengths (n<8kn < 8k tokens for example) this sub-logarithmic growth seems extremely slow. Does this separation has any measurable effect if we use wall-clock time?

4 comments
AuthorsOpenReview ↗

Response to Reviewer wbzg (Part 1)

Thanks! Below we address the concerns point by point.

W1 (modeling assumptions and practical implications) Thank you for your concern. Our modeling setup and assumptions follow standard theoretical frameworks and are well-motivated for isolating the core mechanisms of parallel decoding in DLMs [1,2,3]. Specifically, modeling per-round computation via AC0\mathsf{AC}^0 circuits and connecting it to constant-depth, finite-precision Transformers (Theorem 2.1) is a well-established approach in the Transformer expressivity literature. Moreover, an Ω(log⁡n)\Omega(\log n) round gap still arises on certain distributions even under unrestricted per-round computation (Theorems 5.1 and 5.2). Regarding our language choice, a binary vocabulary is standard and without loss of generality, since any finite vocabulary can be represented in binary with only a constant-factor length increase. Indeed, using formal and regular languages to study language models has precedents [3,4]. Still, we completely agree that a gap remains between our theoretical setup and real-world DLMs and natural language, and bridging this gap is an important direction for future work.

Our work offers two direct practical implications for real-world DLM development.

  1. Regardless of how well the model is trained, per-round conditionally independent draws and irrevocable token commitments in DLMs without revision inevitably block further sequential speedups. As a result, decoding must be cautious because tokens drawn in parallel cannot coordinate within the round or be corrected afterward.

  2. To minimize decoding rounds with revision, our construction (Theorem 3.1) suggests generating latent tokens in intermediate rounds instead of conventionally used ground-truth tokens. These latent tokens act as intermediate drafts to coordinate global dependencies before being overwritten. Recent RL works on DLMs with revision (e.g., [5]) also show the promise of this paradigm.

AuthorsOpenReview ↗

Response to Reviewer wbzg (Part 2)

Q1 (significance of the asymptotic gap and measurable effect on wall-clock time)

Thank you for this question. For regular languages, our construction with revision uses two rounds, while the O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) bound describes the construction without revision. We observe measurable wall-clock gains already at n=1024n=1024 using trained standard Transformers.

We evaluate parity sampling on NVIDIA RTX 6000 Ada GPUs with full-attention Transformers and no CoT tokens. Both the two-round revision sampler and the five-round no-revision sampler use construction-guided supervision. The table reports full-distribution TV upper bounds at 99% confidence and median end-to-end sampling latency for each complete batch. Further architecture and training details are available in our response to W2 of reviewer Wx2S.

MetricTwo rounds with revisionFive rounds without revision
Parameters471K471K
Full-distribution TV0.004050.00231
Latency, batch 1 (ms)2.4626.184
Latency, batch 8 (ms)18.60346.232
Latency, batch 32 (ms)74.325185.590

Both samplers achieve a TV upper bound below 0.01, and the revision implementation achieves an end-to-end speedup of ≈2.5×\approx 2.5\times at n=1024n=1024, well below 8K. As a complementary control, a two-round no-revision model with a larger capacity (1.8M parameters) still fails to learn the target distribution (≈0.50\approx 0.50 TV), showing that no-revision requires more decoding rounds to mitigate the gap at matched parameter scale.

The measured speedup combines fewer decoding rounds with lower computation at matched parameter count. These results show that revision can yield measurable sampling gains at practical sequence lengths on this controlled parity task.

Extending these gains to natural language generation remains future work. As mentioned in our response to W1, no-revision is bottlenecked by conditionally independent parallel draws. Our regular-language distributions have much simpler token dependencies than natural language, as the nn input tokens are independent and only the final label depends on them. As a result, one might expect that on natural language, the bottleneck of no-revision would be amplified, making the practical round gap more pronounced.

As a complementary illustration of scaling with sequence length, we also conduct a CPU simulation of the two zero-CoT circuit constructions. These timings measure the circuit implementations rather than trained Transformers.

nnWith revision (ms)Without revision (ms)Speedup
8K0.03330.04991.50×
16K0.06760.10181.51×
32K0.13250.20201.52×
64K0.2640.4131.57×
128K0.5320.8751.64×
256K1.0641.7501.64×
512K2.0913.5141.68×
1M4.1958.2621.97×
10710^749.797135.3382.72×
10810^8503.2311474.9742.93×

We sincerely appreciate your valuable and constructive feedback, and look forward to our further discussions!

[1] Jiang, Haozhe, Nika Haghtalab, and Lijie Chen. "Diffusion language models are provably optimal parallel samplers." International Conference on Learning Representations. Vol. 2026. 2026.

[2] Li, Zhiyuan, et al. "Chain of thought empowers transformers to solve inherently serial problems." International Conference on Learning Representations. Vol. 2024. 2024.

[3] Merrill, William, and Ashish Sabharwal. "The parallelism tradeoff: Limitations of log-precision transformers." Transactions of the Association for Computational Linguistics 11 (2023): 531-545.

[4] Hahn, Michael. "Theoretical Limitations of Self-Attention in Neural Sequence Models." Transactions of the Association for Computational Linguistics 8 (2020): 156–171.

[5] Bie, Tiwei, et al. "LLaDA2.1: Speeding up text diffusion via token editing." arXiv preprint arXiv:2602.08676 (2026).

Thank you for this detailed responses which clarified most of my concerns. I have increased the rating. Please consider reflecting these answers also into the paper if accepted.

Thank you for your helpful suggestions, which motivated us to provide further clarifications and conduct additional experiments. We will incorporate these clarifications and experimental results into the revised paper.

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

This paper studies whether allowing diffusion language models to revise previously generated tokens reduces the number of sequential decoding rounds. It formalizes a model with deterministic unmasking policies, conditionally independent token draws, and polynomial-size, constant-depth AC0AC^0 computation per round. The principal target is the joint distribution PairL,n=(X,fL(X))\mathrm{Pair}_{L,n}=(X,f_L(X)), where XX is uniform and LL is a fixed binary regular language. The paper proves that revision permits exact sampling in at most two rounds without additional chain-of-thought positions. Validation is theoretical, through explicit constructions and lower-bound proofs, including a transfer to a specified finite-precision Transformer model.

Critical strengths
  1. The aperiodic hidden-DFA representation is particularly consequential: it explains how sampling a word together with its trajectory can be easier than computing the trajectory of a prescribed word. The resulting sampler uses exactly nn fair bits, which is optimal by entropy and makes the no-extra-workspace revision construction possible.

  2. Theorem 5.2 is an important complement to the circuit-complexity results. For L=0∗1∗L=0^{*}1^*, the no-revision lower bound holds for every fixed TV error below one, with constant workspace, even when policies and predictors have unrestricted computational power. Together with the two-round revision upper bound, this demonstrates a limitation arising from the sampling process itself, under the paper’s deterministic-policy and independent-draw assumptions. It substantially strengthens the conceptual case that revision can matter for parallel generation.

Critical weaknesses

The Transformer realization is valuable, but it concerns polynomial-width, constant-precision families with a specified saturating arithmetic convention. The construction even uses saturation to make all visible attention weights equal to one. The resulting equivalence establishes expressivity within that model; it does not establish comparable latency, parameter efficiency, or learnability for fixed-width trained models.

Furthermore, “computationally unrestricted” in Theorem 5.2 does not remove the deterministic-policy and conditionally independent token-sampling assumptions. Those restrictions are important when interpreting the result as a general statement about decoding algorithms. The paper would benefit from a sharper separation between its proved sampling-model statements and broader implications for practical revision mechanisms.

Questions for authors
  1. How should the applicability of Theorem 5.2 be interpreted for decoding policies with external randomness? For example, under a relaxed model, a randomized policy could select an approximately uniform change point, reveal the preceding positions as zeros, and then reveal the remaining positions as ones; a constant-size phase marker would suffice to distinguish the rounds. This appears to bypass the lower bound by allowing the policy to encode shared randomness in the mask pattern. Please clarify which practical classes of policies the deterministic-policy restriction is intended to capture.

  2. Can the dependence on per-round circuit depth be made explicit when interpreting Theorems 4.6–4.7? What tradeoff follows from the existing proofs when the per-round architecture depth is fixed in advance?

1 comment
AuthorsOpenReview ↗

Response to Reviewer tW8p

Thank you for your careful reading and constructive assessment.

W1 (Transformer realization scope) We agree with this distinction. Latency, parameter efficiency, and learnability for trained models are valuable directions for future work, where theoretical and empirical results can complement each other. Thank you for carefully examining the saturation construction.

We provide empirical results for parity sampling at n=1024n=1024 using standard Transformers. Further experimental details are available in our response to W2 of reviewer Wx2S.

SettingParametersFull-distribution TVBatch-1 latency (ms)
Two rounds with revision471K≤0.00405\le 0.004052.462
Two rounds without revision1,844K≈0.50\approx 0.50—
Five rounds without revision471K≤0.00231\le 0.002316.184

W2 (sampling assumptions in Theorem 5.2) We assume a deterministic unmasking policy and conditionally independent token sampling within each round, following a commonly used decoding setup in empirical DLMs (e.g., the default configurations in LLaDA, Dream, and Fast-dLLM). As you noted, Theorem 5.2 shows that these decoding features create a bottleneck for DLMs without revision, and we will clarify this in the manuscript. Conditional independence within a round still allows dependencies to arise across rounds through previously sampled tokens, including CoT tokens, as discussed in our response to Q1. We will distinguish the proved separation under these assumptions from its potential implications for practical revision mechanisms.

Q1 (external randomness in decoding policies) Thank you for this construction using external randomness. Within our framework (with a deterministic policy), a similar two-round construction can be implemented without revision. In the first round, we sample O(log⁡n)O(\log n) CoT tokens independently so that they are almost uniform on {0,1,…,n}\{0,1,\dots,n\} to mark the change point, and in the second round, the predictor reads the change point encoded in the CoT and returns the symbol at each output position. In summary, shared external randomness inside a randomized policy corresponds to explicit CoT compensation under a deterministic policy. Conversely, our lower-bound proof of Theorem 5.2 shows that to locate the 0-to-10\text{-to-}1 change point among nn positions, the number of decoding rounds DnD_n and the number of CoT tokens knk_n must satisfy O(Dn)+kn=Ω(log⁡n)O(D_n) + k_n = \Omega(\log n) (specifically, 6Dn+kn=Ω(log⁡n)6D_n + k_n = \Omega(\log n) in Appendix C.3). Thus, for any constant number of rounds Dn=O(1)D_n = O(1), a DLM without revision requires kn=Ω(log⁡n)k_n = \Omega(\log n) CoT tokens, showing that Θ(log⁡n)\Theta(\log n) CoT tokens are tight.

This illustrates how CoT tokens can provide the shared randomness needed to guide a deterministic unmasking policy without relying on external randomness in the policy itself, which is one motivation for our modeling choice.

Q2 (dependence on per-round circuit depth) Greater per-round circuit depth can reduce the required CoT budget. Specifically, for a fixed regular language L∉AC0L \notin \mathsf{AC}^0 and O(1)O(1) decoding rounds:

  • (Theorem 4.6) If a no-revision DLM uses per-round circuits of depth dd, then the exponent ii in the CoT lower bound Ω(n/(log⁡n)i)\Omega(n / (\log n)^i) satisfies i=O(d)i = O(d).

  • (Theorem 4.7) Conversely, a CoT budget of O(n/(log⁡n)i)O(n / (\log n)^i) can be achieved using per-round circuits of depth d=O(i)d = O(i).

Thus, the polylogarithmic CoT-saving exponent ii and the per-round circuit depth dd have a linear relationship, and we will include the explicit derivation in the revision.

Thanks for your thoughtful and valuable feedback. We look forward to our further discussions!

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

The paper studies the theoretical round complexity of diffusion language models with and without revision. Building on the Boolean circuit complexity established by previous works, the paper further extends the analysis from sampling the toy uniform parity to sampling general languages. They show that DLMs with revision can exactly sample any binary language distribution in two rounds, while DLMs without revision require non-constant rounds. The paper further establishes near-linear lower bounds on the additional token budget required to recover constant-round sampling when revision is disabled.

Critical strengths
  1. The paper provides a comprehensive theoretical characterization of round complexity for sampling binary regular languages with DLM. In particular, the matching upper and lower bounds strengthen the existing separation result of [1].
  2. The construction using a hidden aperiodic DFA appears to be a nontrivial technical ingredient that generalizes the parity-specific construction to a broader family of distributions.

[1] Jiang et al. (2026). "Diffusion Language Models are Provably Optimal Parallel Samplers." ICLR 2026.

Critical weaknesses
  1. My main concern is the degree of conceptual novelty relative to the preceding work. [1] already been established that allowing revision/remasking creates a huge difference in the parallel sampling capability of DLMs, as well as recognizing the reuse of output and CoT positions as buffers to store temporary computations. The paper considerably strengthens and generalizes the results, but its central motivation and interpretation remain largely the same. I would appreciate a clear explanation of the genuinely new technical and conceptual contributions.
  2. Moreover, the current work shares the same major limitation as the previous work [1]. Both only established the existence of a DLM instance that's both faithful to the target distribution and minimal in sequential computation, but this barely informs how to achieve such efficiency in practice. While the results offer a useful insight into DLM inference that remasking should be allowed, they do not address how training and inference algorithms can discover and recover the efficient sampling strategies. More importantly, it remains unclear how the theoretical parallelism advantages carry over if the model is trained imperfectly, where approximation errors may substantially affect the achievable speedup.
  3. The paper refers to additional token positions as CoT, but these positions function as auxiliary computational storage rather than meaningful reasoning trajectories. In fact, any additional writable token positions could serve the same purpose, regardless of whether they represent CoT. I therefore find the terminology somewhat misleading, as the analysis does not model the probabilistic or semantic properties of CoT in practical language models.

[1] Jiang et al. (2026). "Diffusion Language Models are Provably Optimal Parallel Samplers." ICLR 2026.

Questions for authors

See weaknesses.

6 comments
AuthorsOpenReview ↗

Response to Reviewer Wx2S (Part 1)

Thank you for your constructive feedback. We address the concerns point by point.

W1 (conceptual novelty) Thank you for the comment. Below we clarify our core technical challenges and method motivations in (1) and (2), and highlight the new conceptual interpretations our results bring beyond [1] in (3).

(1) With revision. Why the parity construction in [1] does not directly generalize, and how we overcome this obstacle.

[1] uses the well-known AC0\mathsf{AC}^0 sampler for parity (see Viola, The Complexity of Distributions, Section 1), which first samples prefix parity states independently and then recovers the input bits by taking adjacent differences modulo 22. However, this construction does not directly extend to MODm\mathrm{MOD}_m for m>2m>2. For example, for MOD4\mathrm{MOD}_4, if we sample states yiy_i independently and uniformly from {0,1,2,3}\{0,1,2,3\}, then yi−yi−1y_i-y_{i-1} modulo 44 can be 22 or 33, rather than a binary input. This obstacle motivates us to ask whether AC0\mathsf{AC}^0 sampling is possible for general regular languages.

To overcome this obstacle, we introduce a hidden aperiodic DFA construction. Although the original DFA may have a non-aperiodic transition monoid, block relabeling and state splitting reveal a hidden aperiodic structure whose runs can be computed in AC0\mathsf{AC}^0. The construction preserves the distribution under uniform random inputs, without having to preserve the recognition computation on each given input. It also provides a new view of the classical parity sampler through transitions of a hidden DFA. For parity, the block size is 11 and no state splitting is needed. Given the current hidden state hh and a random bit uu, we set the next hidden state to uu and relabel the input bit as h⊕uh\oplus u.

Current hidden state hhRandom bit uuNext hidden stateRelabeled input h⊕uh\oplus u
00000000
00111111
11000011
11111100

Each hidden transition resets the state to the current random bit, making the hidden DFA aperiodic. Our general construction extends this perspective beyond parity and establishes that sampling is strictly easier than recognition for every regular language outside AC0\mathsf{AC}^0.

Finally, the circuit construction uses only nn fair bits. A DLM can therefore sample these bits in its output positions in the first round and overwrite them with the target output in the second round, requiring no CoT positions.

(2) Without revision. How we strengthen the lower bound in [1] and obtain a matching upper bound.

We exploit the ability to trace the decoding process without revision. Given a candidate output and CoT transcript, the deterministic policy and irrevocable token commitments determine a unique candidate trace, which we can check round by round. This yields a recognition circuit of depth proportional to the number of decoding rounds, allowing us to derive the stronger lower bound from recognition hardness. Together with our revision construction, this explains the separation through the gap between sampling and recognition complexity.

For the matching upper bound, we adapt the classical Θ(log⁡n)\Theta(\log n)-ary tree construction for parity computation, as described by Krause and Wegener, Circuit Complexity, to convey intermediate states through mask patterns. However, directly storing the summary of the whole subtree does not work. Instead, we store the subtree summary excluding the root node's local word, as shown in Figure 1 in the manuscript. For example, in the chain construction accompanying our response to W3, we cannot use Si=⨁j<2ixjS_i=\bigoplus_{j<2i}x_j, since this would require the policy to incorporate a newly sampled fair bit before its value becomes visible. This one-step latency is essential. Surprisingly, the resulting construction conveys intermediate computational traces entirely through the mask pattern of output positions, without CoT, while achieving O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) rounds. This also complements our response to W3.

AuthorsOpenReview ↗

Response to Reviewer Wx2S (Part 2)

(3) New conceptual interpretations beyond [1].

These results provide a new in-depth understanding of how revision reduces sequential computation in DLMs. Going beyond [1], our findings yield three main insights: (1) We connect the round complexity of revision to the sampling complexity of the language (implementing its sampling circuit via a DLM with revision in Theorem 3.1), and connect the complexity of no-revision to its recognition complexity (proving that the round complexity without revision is at least the minimum depth of the language's recognition circuit in Theorem 4.3). This reveals that the gap between revision and no-revision is essentially the gap between a language's sampling complexity and recognition complexity. (2) From this connection, we deduce that the separation for PARITY in [1] is not a special case, but a universal phenomenon across all regular languages outside AC0\mathsf{AC}^0. (3) We further consider the setting with unrestricted per-round computation and discover that an Ω(log⁡n)\Omega(\log n) round gap still persists on Word0∗1∗\mathrm{Word}_{0^*1^*} (Theorem 5.2). This shows that the bottleneck arises from conditionally independent parallel draws with irrevocable token commitments, rather than merely AC0\mathsf{AC}^0 compute limits as in [1].

W2 (practical implications)

Thanks. Studying ideal DLMs is valuable because it shows that no matter how much training and inference improve, revision still offers room to further reduce sequential computation. As for achieving minimal sequential computation in practice, our revision construction informs that intermediate decoding rounds should generate latent tokens instead of the conventionally used ground-truth tokens at those positions, because it works by first writing the output positions with auxiliary random bits and then overwriting them with the final target tokens in the next round. Recent RL works on DLMs with revision (e.g., [2]) also show the promise of this paradigm. Still, how to train models to find the most efficient latent trajectories remains an open problem.

To connect our theoretical results with practice, we study parity sampling at n=1024n=1024 using standard Transformers on NVIDIA RTX 6000 Ada GPUs. We compare three settings: two rounds with revision, two rounds without revision, and five rounds without revision.

All three settings use the same design: two Transformer blocks with GELU feed-forward layers, full bidirectional attention, no CoT tokens, learned positional embeddings initialized sinusoidally, and three seeds each.

Two rounds with revisionTwo rounds without revisionFive rounds without revision
Hidden width / heads84 / 12256 / 484 / 12
FFN width / activation966 / GELU1024 / GELU966 / GELU
Parameters471,1581,843,714471,328
Full-distribution TV≤0.00405\le 0.00405≈0.50\approx 0.50≤0.00231\le 0.00231

The two rounds with revision and five rounds without revision models are matched in parameter count (471,158 vs. 471,328), so this comparison isolates the decoding scheme and round complexity rather than model capacity.

The two-round revision implementation achieves the following end-to-end sampling speedups over the five-round no-revision implementation. We report median latency for each complete batch.

MetricTwo rounds with revisionFive rounds without revisionRatio (without / with revision)
Latency, batch 1 (ms)2.4626.1842.51×
Latency, batch 8 (ms)18.60346.2322.49×
Latency, batch 32 (ms)74.325185.5902.50×
Estimated matrix-multiplication GFLOPs per sample2.977.442.50×

For two rounds with revision, we use the construction's local XOR map as supervision. Writing xi(t)x_i^{(t)} for position ii after round tt, the targets are

x_i^{(2)}=x_{i-1}^{(1)}\oplus x_i^{(1)}\quad (2\le i\le n),\qquad x_{n+1}^{(2)}=x_n^{(1)}.$$ For two rounds without revision, the first $n$ bits remain unchanged, and the second-round target is $$x_{n+1}^{(2)}=\bigoplus_{i=1}^{n}x_i^{(1)}.$$ For five rounds without revision, we use the mask-pattern tree construction in Theorem 4.4 to provide intermediate supervision for the unmasking policy and predictor. **Together, the successful two-round revision and five-round no-revision samplers demonstrate that our construction-guided training procedures can recover efficient sampling strategies for parity in standard Transformers**.
AuthorsOpenReview ↗

Response to Reviewer Wx2S (Part 3)

When the two-round revision and no-revision models are configured at matched parameter counts, the two-round no-revision model still fails to train successfully. We therefore attempted to scale up the no-revision model (as shown in the table above), but it still could not be successfully trained. These experiments provide empirical support for the expressivity gap. Furthermore, the no-revision model needs more decoding rounds to mitigate this gap at matched parameter count. In the mask-pattern tree construction, a bit's output can depend on up to 222 positions, whereas the revision construction needs only two. Thus, decoding without revision involves more rounds and a higher computational cost.

Regarding error tolerance, these results show that the sampling advantage can persist with nonzero approximation error in trained models. Section 5 shows that the round separation persists when allowing approximation error in Word0∗1∗\mathrm{Word}_{0^*1^*}. However, a systematic study of how training errors affect sampling quality and speedup remains an important direction for future work.

W3 (CoT terminology) Thank you for pointing out this ambiguity. Following prior work (e.g., [1,3]), we used "CoT" to denote general writable positions, and we will clarify this terminology in the revision. While our lower bounds (Theorems 4.3, 4.6, and 5.2) hold even under this relaxed formulation, we agree that modeling semantic reasoning trajectories in CoT is a promising future direction. Interestingly, our Theorem 4.4 shows that even with no CoT positions, a DLM can still form implicit reasoning trajectories purely through the mask pattern, suggesting that reasoning in DLMs extends beyond explicit CoT tokens (we share a concrete walkthrough in the follow-up comment below in case it is of interest).

We sincerely appreciate your valuable and constructive feedback, and look forward to our further discussions!

[1] Jiang, Haozhe, Nika Haghtalab, and Lijie Chen. "Diffusion language models are provably optimal parallel samplers." International Conference on Learning Representations. Vol. 2026. 2026.

[2] Bie, Tiwei, et al. "Llada2. 1: Speeding up text diffusion via token editing." arXiv preprint arXiv:2602.08676 (2026).

[3] Li, Zhiyuan, et al. "Chain of thought empowers transformers to solve inherently serial problems." International Conference on Learning Representations. Vol. 2024. 2024.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.