- 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 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 . For the typical sequence lengths ( 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
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 bound describes the construction without revision. We observe measurable wall-clock gains already at 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.
| Metric | Two rounds with revision | Five rounds without revision |
|---|---|---|
| Parameters | 471K | 471K |
| Full-distribution TV | 0.00405 | 0.00231 |
| Latency, batch 1 (ms) | 2.462 | 6.184 |
| Latency, batch 8 (ms) | 18.603 | 46.232 |
| Latency, batch 32 (ms) | 74.325 | 185.590 |
Both samplers achieve a TV upper bound below 0.01, and the revision implementation achieves an end-to-end speedup of at , 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 ( 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 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.
| With revision (ms) | Without revision (ms) | Speedup | |
|---|---|---|---|
| 8K | 0.0333 | 0.0499 | 1.50× |
| 16K | 0.0676 | 0.1018 | 1.51× |
| 32K | 0.1325 | 0.2020 | 1.52× |
| 64K | 0.264 | 0.413 | 1.57× |
| 128K | 0.532 | 0.875 | 1.64× |
| 256K | 1.064 | 1.750 | 1.64× |
| 512K | 2.091 | 3.514 | 1.68× |
| 1M | 4.195 | 8.262 | 1.97× |
| 49.797 | 135.338 | 2.72× | |
| 503.231 | 1474.974 | 2.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
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.
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 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 Ω(logn) 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.
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.
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.