Revision Provably Reduces Sequential Computation in Diffusion Language Models

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 ${\mathrm{AC}}^0$ computation. We compare the minimum number of rounds each class needs to sample $(X,f_L(X))$, where the word $X$ is uniform on $\{0,1{\}}^n$ and $f_L$ is the membership function of a binary regular language $L$. 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 $\Theta (\log n/\log \log n)$ even with a constant number of CoT positions for every $L\notin {\mathrm{AC}}^0$, that is, every regular language whose membership cannot be computed by such circuits. Moreover, for every such $L$ and every constant $\theta >0$, $O(n^{1-\theta })$ 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-$n$ word uniformly from some regular language $L$. These results provide a theoretical framework for understanding how revision reduces sequential computation and expands the scope of parallel speedups achievable by DLMs.