Diffusion Language Models are Provably Optimal Parallel Samplers
Authors: Haozhe Jiang
Nika Haghtalab
Lijie Chen
Venue: ICLR 2026 Poster (2026)
Keywords: Theory
Diffusion Language Model
Large Language Model
Primary area: learning theory

Abstract: Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive models for faster inference via parallel token generation. We provide a rigorous foundation for this advantage by formalizing a model of parallel sampling and showing that DLMs augmented with polynomial-length chain-of-thought (CoT) can simulate any parallel sampling algorithm using an optimal number of sequential steps. 
Consequently, whenever a target distribution 
can be generated using a small number of sequential steps, a DLM can be used to generate the distribution using the same number of optimal sequential steps.
However, without the ability to modify previously revealed tokens, DLMs with CoT can still incur large intermediate footprints. We prove that enabling remasking (converting unmasked tokens to masks or revision (converting unmasked tokens to other unmasked tokens) together with CoT further allows DLMs to simulate any parallel sampling algorithm with optimal space complexity.
We further justify the advantage of revision by establishing a strict expressivity gap: DLMs with revision or remasking are strictly more powerful than those without.
Our results not only provide a theoretical justification for the promise of DLMs as the most efficient sampler, but also 
advocate for why revisions should be enabled in DLMs.

Published as a conference paper at ICLR 2026
DIFFUSION LANGUAGE MODELS ARE PROVABLY OP- TIMAL PARALLEL SAMPLERS
Haozhe Jiang Nika Haghtalab Lijie Chen University of California, Berkeley (ericjiang, nika, 1ijiechenn (bberel)eeeeeeeee edu
ABSTRACT
Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive models for faster inference via parallel token generation. We pro- vide rigorous foundation for this advantage by formalizing model of paral- lel sampling and showing that DLMs augmented with polynomial-lenge chain- of-thought (CoT) can simulate any parallel sampling algorithm using an optimal number of sequential steps. Consequently, whenever a target distribution can be generated using a small number of sequential steps, a DLM can be used to gener- ate the distribution using the same number of optimal sequential steps. However, without the ability to modify previously revealed tokens, DLMs with CoT can still incur large intermediate footprints. We prove that enabling remasking (converting unmasked tokens masks or revision (converting unmasked tokens to other un- masked tokens) together with CoT further allows DLMs to simulate any parallel sampling algorithm with optimal space complexity. We further justify the advan- tage of revision by establishing a strict expressivity gap: DLMs with revision or remasking are strictly more powerful than those without. Our results not only provide theoretical justification for the promise of DLMs as the most efficient sampler, but also advocate for why revisions should be enabled in DLMs.
INTRODUCTION
Diffusion language models (DLMs, Austin et al. (2021) ;; Nie et al. (2025): Song et al. (2025) have recently emerged as a promising alternative to autoregressive (AR) generation, fueled by their poten- tial to deliver faster generation and more efficient inference. In contrast to AR modelss-hiche de- spite running on massively parallel hardware, must still generate text sequentially, token by token- DLMs decode by iteratively denoising masked sequences, allowing many positions be unmasked in parallel. This fundamental architectural difference offers the promise of significantly reducing generation and inference latency, and has led surge of interest DLMs in a world increasingly attuned to the value of inference-time scaling Song et al. 20255) Khanna et al. (2025)
Yet DLMs remain in their infancy compared the highly optimized AR models, and it is far from clear when, or if. their promised advantages will translate into principled gains. This makes theory especially important for evaluating the genuine potential of DLMs: unlike AR models, whose ca- pabilities under chain-of-thought (CoT; Wei et al. (2022) reasoning are well understood, the basic limits of DLMs, such as how much sequential computation they truly save, and what space and memory such parallelism requires, remain largely unexplored.
In this work, we provide such a theoretical foundation for studying DLMs by formalizing them through the lens of circuit complexity, using circuit depth and width as abstractions for the time and space resources required to compute function in parallel. As we describe in more detail below, our results establish the expressive power of DLMs the most efficient parallel sampler.
Our first result Theorem 3.1 shows that when equipped with sufficiently long CoT, DLMs can sim- ulate any sampling procedure with the minimal number of sequential computational steps. Specif- ically, any distribution that can be realized by a circuit of depth can be generated by a DLM decoding rounds, thereby matching the minimum number of sequential steps required by the target computation. This stands in stark contrast to AR decoding. In particular, while is known that autoregressive models equipped with CoT can simulate any Boolean circuit (Li al. 2024), the

---

Published as a conference paper at ICLR 2026
number of sequential steps in this case (which in the cases of AR models equals the length of the CoT) grows linearly with circuit size, Le., the total number of nodes, rather than with depth.
Beyond the number of steps required to generate sample, also analyze the working memory footprint (Theorem 3.2) of DLMs and show that it depends critically on design choices unique to this family of models most notably inference-ting mechanisms such remasking (Nie al. 2025) and revision [Song et al. (2025). Remasking is an inference-ting mechanism that allows a already unmasked tokens to re-masked (noised) and resampled (denoised). Revision, the other hand, permits unmasked tokens to be changed directly to other tokens. We show that when DLMs are augmented with CoT and either remasking or revision, they can simulate any circuit using memory that scales only linearly with the circuit's s width.
Finally, we demonstrate via the problem of uniformly sampling from strings with zero parity that remasking revision can generate strictly richer distributions. More specifically, DLM with remasking or revision can generate the distribution with constant steps (Theorem 4.3), while is impossible for DLM with neither of them (Theorems that remasking and revision, which arise from the special structure of DLMs, can potentially greatly enhance the capability of the model given constrained inference time. This suggests exploring more remasking strategies and more flexible forward processs in the future.
Our results show clear evidence
1.1 RELATED WORK
Diffusion Language Model. Diffusion models were originally built for generative modeling in the continuous domain (Ho et al., 2020 Sohl-Dickstein et al. 2015), and were later extended to the discrete domain. The seminal work of D3PM (Austin et al. 2021) formalized categorical for- ward kernels and popularized absorbing masks, and is followed by series of works on language modeling (He et al.] [,220233] Lou et al., 2024 Sahoo et al. 2024 Shi et al. 2024). Furthermore, re-
cent works (Song al.] 2025 Nie al.] 2025] Yang al. 2025 Ye et al.. 2025 Xie et al., [025 Khanna et al. 2025) scale DLMs up, and achieve competitive performance to AR models and faster generation.
Decoding order, Remasking and Revision. DLM can perform inference in any order, but it is ob- served that decoding order can greatly affect the performance of DLMs (Kim et al. [0225] Yang et al.)
2023 Xie al. 2025). Remasking Nie et al. (2025); Yang et al. (025) is another inference-time strategy that introduces richer decoding paths to further enhance the performance. More recently, DLMs with revision (Song et al., (2225) are introduced and exhibit remarkable capability. However, the fundamental differences of these strategies are not clear yet.
2 PRELIMINARY
In this section, we specify the notations and conventions used in this paper, and describe the theo- retical framework to analyze the problems.
Notations. Let V be the vocabulary Throughout the paper, we will always consider the binary vocabulary set y = {a,bb) b} by default, but the diffusion language model works for any other discrete vocabulary set. We also consider mask token M. We consider sequences of length on the VU [M}. For sequence I₁ E (VU (M)) E [0, 1] denotes the noise level, i.e., the fraction of the masked tokens in the sequence. For simplicity, we assume
(0, 1/L, 2/ L/L...... (L 1)/L, 1). and therefore t L is an integer. Let [n] = f1...., n for positive integer n. A sequence with no mask is called noiscless. We use z; where i [L] to denote the i-th entry of 2,, and 2 to be the subsequence of x, starting from the i-th entry to the j-th entry, including both ends. Since subscripts used noise levels, of distributions with support on set S by (5))
superscripts for indices of sequences by default. We denote the set
2.1 DIFFUSION LANGUAGE MODEL.
Central to a diffusion language model (DLM) is a predictor p(-12.) E A (V*) that predicts a noiseless sequence from noisy sequence x, (VU (M)) Let ('(22x) be the distribution on
2

---

Published as a conference paper at ICLR 2026
the token at position i. The predictor satisfies that its prediction tokens different positions are conditionally independent given Tt, and it only changes mask tokens. Mathematically, for all to E V E (VU (M))", we have
p(zol2,) II pt (z)) and p' (z/(=") if
These constraints arise from the definition of the forward process, where tokens at different positions are independently masked to M.
At inference time, specify noise level that want the output sequence be and unmask set of positions to match this noise level. Following the convention of Kim et al. (2025) we denote the set of positions to be unmasked by 8 F(x+) S {īlzzz M] that depend on 3t-- A simple unmasking policy F(xe) only requires the knowledge of where the masked tokens are and chooses a uniformly random set S S {ilxx] M to unmask, such that |S| L(t - s). For much of the paper we constrain F to be a deterministic function.
We also consider the general case of DLMs trained to generate an output E > conditioned on an input q E y At inference time, we start from Iy gM the sequence of input padded with masks, and adopt an iterative generation process. In each iteration, we first calculate the positions to decode as S = F(x,), and then decode the corresponding positions using p'(+(x) for i E S. The iteration ends at a predetermined number of steps D a noiseless sequence Zn. We finally extract the output
mi11 The generation process is summarized in Algorithm
Chain of Thought (CoT) is the technique in language models that allows the output o to a prompt q to appear after generating some intermediate tokens. In our framework, this means that L >> m and the form of Zo is goooT In this paper we always assume that L matches the length of cCooToo for simplicity, while in practice L is predetermined and is usually larger than the length of q oo. We also allow for the case when is an empty string, which corresponds to generating an unconditional distribution.
Remasking, Remasking is an inference strategy that is used to improve output quality. It allows unmasked tokens to be remasked during the generation process. We model this via function G(-), which at the end of each iteration, it produces set T = G(xx)) S [L] that represents the positions to be remasked and set to M. By default, we consider G that is a random function. The remasking process is also incorporated in Algorithm
Revision. Recent works such as Song et al. 2025) have proposed forward processes that allows token to change into another token before becoming fully masked. We refer this as DLMs with revision. When DLM with revision are considered, we relax the constraint that an unmasked token must remain fixed. However, we still impose the constraint that token distributions across different positions are independent. Formally, for all zo E VL Te E (V (M))², we have
p( (2)) = I p² (zol=r) but is possible that p' (s/]=²) < 1 for o E V.
Unless otherwise specified, throughout this paper DLM refers to the standard model without masking or revision.
2.2 BOOLEAN CIRCUITS
Boolean cireuit is model to characterize the complexity of carrying out certain parallel computa- tions. A circuit C' is defined as layered directed acyclic graph (DAG). Formally, DAG C' = (V. E) consists of a set of vertices and a set of directed edges É C V x with no directed cycles. The number of vertices |V is called the size of the circuit. Furthermore, there is a function 1 V ø+. which assigns every vertex to a layer satisfying 1(22) = I(vz) + for all (01, 12) E E. That is, no edge skips layer. Each vertex represents an input, logic gate vertices have zero in-degree and out-degree, respectively, and they take Boolean values from (0. 1). Logic gates perform range of operations their inputs, which will specify in the following
output. The input and output
3

---

Published as a conference paper at ICLR 2026
Algorithm 1 DLM Inference
Input: prompt q V", p(-]az),, length L, rounds D, masking F, optional remasking g.
Output: Output E pm
< gM--n
for; j = to
do
S 4 F(x).
x¹ ~ p¹ (-1z) for each i S.
T - ((z).
// If remasking is enabled remasking is enabled
x t M for each i E T.
end for x²
~ p¹ (-1z) for each remaining masked position.
return x m-1
paragraphs. As a result, we can calculate the output from the input using logic gates following the graph.
The input to the a circuit is (x, Rt) E 10, 10, and consists of two parts: E {0, 1)" repre- sents the actual input, and R E 10 are the random bits, sampled from U Uniform (f0, })"), the uniform distribution over {0, 13"" We denote the output of the circuit as C'(x, R). The depth d and width we of the circuit are respectively defined as
d = max ((v), w max (ule E v.1(v) = =]]- VEV
rE[d]
That is, depth the total number of layers, and width is the largest number of vertices a layer. Depth represents the minimum number of sequential steps carry out the computation represented by C. and width represents the minimum number of memory bits needed to carry out the computa- tion. Finally, we say that C' simulates a random function f : {0, 13" 10, if
Pr (/(x) v = PrR-ur [C(x, R) = vb) for x E (0, 10" E 10,
In this paper, we use Latin letters x, y to represent token sequences, and Greek letters X. d to repre- sent boolean sequences. We use Boolean circuit to model the computational complexity generate distributions. All distributions in this paper are assumed to be generated by some circuit. Further- more, we also model the diffusion language model, including the predictor, F and G, circuits. Since the circuit model is standard model of modern computers, it is natural to use circuits to model the distributions that be sampled by computers, as well the computation in DLMs. Be- sides, it has been standard to study the expressive power of neural networks using circuit models (Li
al. 2024 Merrill & Sabharwal 2023
Complexity Classes. A problem is a random map L 10, -> {0.1) A set of cireuits {C*) mEE simulates problem L if
Pr [C()
bb Pr
R-udll (x.xl(x. R) = for x E (0,1)", (0.1)"'
Here 7d represents the number of random bits in C
A basic set of gates for circuits is {AND, OR, NOT, ID). Gates AND, OR has 2 in-degrees, while NOT, ID has 1 in-degree. All of them have out-degree. Gates AND, OR, NOT realize the logic computations suggested by their names, and ID outputs the input without change. A problem L N, if there exists set of circuit {C.) such that it computes L, and
in N where any C₂ has (ppoly(n)) (n)) gates and O ((log n)))) depth. Now we generalize the complexity classes to more powerful classes. we allow AND, OR to have unbounded in-degrees rather than 2 in- degrees, the corresponding complexity class is called *C* If we further allow MAJORITY gates with unbounded in-degrees, which outputs if and only if there more I's than 0's in its input, the corresponding complexity class is called T MAJORITY could be thought of as allowing the circuit to count, as assessing which digit is majority essential requires the circuit to count their numbers of appearance. known that for all é E N, NC¹ C AC' C TC' C NC (Volleer 1999).
4

---

Published as a conference paper at ICLR 2026
{a, to be binary. In order Circuit Model for DLM. Recall that restrict the vocabulary V to encode the vocabulary as well as the masked token M, we will use a fixed 2-bit encoding
a + 00,
01, M 10,
with the unused encoding 11 being invalid and never produced. For a sequence x E (V {M)) let its encoding be E {0, 13 where the pair (X26-1, X2:) encodes r'. When convenient we refer to the numerical token value of and as 0 and rather than their encoded values 00 and 01.
A predictor p(-|2zz) of a DLM is a set of L circuits whose inputs are from the encoding space. For each position E [4] we have eircuit C {0, 1,22 x {0, 1)" + {00, 01, 10), which takes as input the shared encoded sequence X and uses r' random bits R ~ U to simulate pr(-(2x)) Analogous to the definition of DLMs before, the random bits for different i are independent that p( (xn) = II p² (z)) Furthermore, each circuit C2 can only unmask a masked token, i.c., 1:2 * 10 then the output pair at é equals the input pair.
Xr
Masking and remasking are done analogously. In particular, function F is represented by deter- ministic boolean circuit f: {0, 1122 - {0. 10.1 where f(xx)* represents whether the i-th position should be unmasked. Similarly, function is represented by possibly randomized circuit function {0, _ x 1) + {0, 134, where r ~ U" and g(x,, represents whether the i-th position should be unmasked.
DLMS ARE EFFICIENT SAMPLERS
In this section, we prove that DLMs can simulate circuits with the minimum possible parallel com- putation steps and memory needed. As mentioned in /Section 2.2] the depth and width of circuit provide a natural formalization of the minimum sequential steps and memory needed to sample from distribution. In this section, denote DLM as M and use (g) to represent the output from the DLM given input y generated using the DLM following Algorithm ]
3.1 DLM WITH CHAIN OF THOUGHT
The following theorem formalizes the statement that DLMs can generate any distribution with the minimum possible sequential steps.
Theorem 3.1. Let C' be circuit with depth d, m output bits, input bits, random input bits R ~ U and vertices. There is a DLM M with CoT and length = N, such that for every input q. M (g) generates the same distribution C(g, R). Furthermore, the number of decoding steps of M is d, and the corresponding predictor p and unmask position policy F are both represented by constant- depth circuits.
Before presenting the proof, we first define function that is very useful for our construction.
Definition 1. Boolean function ShiftR 10. + 110,1" is defined as follows. For any X (0.1)*
xx <i<isn
ShiftR(x)' = (1 if
Simulating this function is in NC In other words, this circuit can be realized in O(1) with (р))y(nn) AND, OR with in-degree and NOT gates. The 1 can be realized by 17 -7 for any boolean variable 77, and the others come directly from the input.
Proof of Theorem 3./ Let us start by introducing some notations.
Notations. Without loss of generality, we can assume that all input vertices are in the first layer, all output vertices are in the last layer, and there is random bit in the first layer. We define the following variables:
Larger vocahularies are handled by standard reduction that encodes tokens by binary codewords and expand the sequence length accordingly.
5

---

Published as a conference paper at ICLR 2026
v' ..... V be the list of vertices in the circuit; they sorted in way that the layer
number increases the sequence,
ul, ,...., N be the corresponding variables that are output from the vertices;
11 N be the layer number of each vertex;
8 s',..... d be the index of the first vertex in every layer (and 8 0, 0, = L + for
simplicity):
w/ .. "d be the width of each layer in i.e. w = s for all i I,...,d.
In this proof, we use the subscript of x to index the iteration that is being carried out instead of the noise level for convenience. For example, the initial sequence for the model is ø1 = <M- and becomes T2 after the first iteration. The generation process. Now let describe the generation process that we wish to realize. Our construction carries out the computation of circuits layer i during iteration i, appends the output to the end of existing outputs, and carries out the computation for layer i + based on it. Mathematically, we realize the following intermediate sequences:
n M
j < s
if 2 si+1
As result, the generation process stops at sequence Zd ut.... u and x/ f.-m++:1 1: equals o. Below we will describe how to construct the DLM M (specifically, the functions F and the predictor p) that realizes this generation process.
Construction of F. To implement the process above, function JF needs to identify the current iteration index from and produce S = { g!. -1] 1} accordingly. Since x 2 denotes
whether xr mask according the token encoding, it follows that the sequence {x;" 2+
denotes whether each layer in the circuit is decoded in 24. Let 2==1 E 10, d be the concatenation of this sequence, we have that (x.-- and ShiftR (x?*-1y denote whether layer j in the circuit decoded in z; and Ti+1, respectively. Hence (ShiftR (x,²-1) A -xx²=1)² denotes whether layer j should be decoded at iteration i from r;. In other words, it equals only when i Putting everything together, we set
f(a)' (ShiftR (x²+-1) -
1x²--1)"
which is realized by constant-depth circuit using OR with in-degree and NOT.
Construction of p(-[z)). To implement the process above, our p(-(z;) only needs to replicate the computation from the i-th layer the (i + 1)-th layer. Notice that the construction of p(-1xz) is identical for all iterations. The layer of the circuit to simulate is controlled by F, which extracts the information of from the mask patterns in ot described in the last paragraph. Denote the circuit that computes the outputs from the i-th layer the (i + 1)-th layer by C, Yr2 x {0, 1]r"
(0, 13 Here y ,+1 represents the number of random bits in layer + 1. Then the output for p(-1z) is: for forst +1+1 s 1-+221
2j X 0, Xit1 2j C.
R.) R2 Un!!!
Output bits for other j are specified because other positions unmasked and are hence relevant.
Finally, we need to confirm that the outputs of p(-(x,) at diffferent positions are independent. Note that in C,, the random bits R& is only used for generating the random bits in the (i + 1)-th layer. As result, every bit of becomes random bit in the (i + 1) layer, and is not involved in the calculation of any other output bit. Hence, the constructed p(+[2;) indeed realizes an entry-wise independent output distribution.
Too simplify notation, here assume that the circuit takes in tokens from V. which is mapped to the hinary representation before being passed the actual circuit

---

Published as a conference paper at ICLR 2026
In the construction, have to record intermediate calculation results (sequence u) each ap- plication of p can only simulate a constant-depth circuit. Meanwhile, we cannot erase previous intermediate results without remasking or revision, despite only needing them once. As result, though the time complexity is amenable, the construction incurs a large memory footprint.
This result demonstrates that DLMs can in principle generate distributions faster than their autore- gressive counterparts and hold great potential for fast parallel generation. However, in practice, being able to sample in ((d) rounds instead of ((N) does not directly imply that we could reduce computation or wall-clock latency compared to autoregressive models in real-world practice. As a concrete example, we compare the computation cost and wall-clock lateney in one decoding step between an autoregressive Transformer with KV caching and a DLM implemented by a Transformer of the same size. In every attention layer, an autoregressive model only needs to compute the atten- tion output for one position, whereas a DL.M needs to compute the attention output for all positions. Hence, a DLM needs (L) times more FLOPs than an autoregressive model. The computation of the L tokens is parallelizable for the DLM, so if the hardware supports enough degree of parallelism, they have the same wall-clock latency. However, if the hardware does not support enough parallel computing, the wall-clock latency for the DLM can be slower.
3.2 DLM WITH CHAIN OF THOUGHT AND REMASKING OR REVISION
With remasking or revision, we have the power to erase intermediate results that are no longer needed. In this part, we show that with remasking or revision, we can sample from any distribution not only with the minimum possible sequential steps, but also with the minimum amount of memory. The proofs of the following two theorems are deferred to the Appendix as the proof strategy is similar to that of Theorem 3.1
Theorem 3.2. Let C be a circuit with depth d, width w. m output bits, n input bits, and random input bits R ~ U". There exists a DLM M with CoT and remasking with length L = + [log (d + 1)1, such that the distribution of M (q) the same as C(q, R). Furthermore, the number of decoding steps is d + 1, and p. F, 9 are all represented by circuits with Ollog d) depth.
The [log(d + 1)] term in the length L comes from the fact that we can no longer infer the iteration step from the mask pattern, and need extra spaces to record the current iteration step. The proof is simpler for DLMs with revision, as we can directly rewrite xe by 24+1, instead of using two chunks of memory in an alternating way. The theorem statement is follows:
Theorem 3.3. Let C be a circuit with depth d, width w, m oulput bits, imput bits, and random input bits R R~ U", There exists a DLM M with CoT and revision with length = w [log(d+ such that the distribution of (4) is the same as C(g, R). Furthermore, the number of decoding steps is + 1, and p. F are both represented by circuits with O(log) d) depth.
DLMS ARE MORE EXPRESSIVE WITH REMASKING OR REVISION
In the last section, we show how DLMs with appropriate sizes can efficiently simulate the genera- tion process of Boolean circuits, and how enabling remasking or revision can significantly reduce the sequence length L needed. It is natural to ask: for a DLM with fixed L, does remasking or revision enable to generate new distributions with constant generation steps? This section gives an affirmative answer to this question by showing a separation on generating a specific distribution introduced in the next paragraph.
For the purpose of showing separation, we only need to consider the simpler case when the DLM takes no input (q 2). and is sampling from unconditional distribution. Let @ be addition modulo 2. That is, 21 @ 22 = for E (0, 1} iff z + 22 = b (mod 2). It is well-known that @ can be represented by AND and OR
x = (V))) ( ~xx v) for any x, 1b E (0.1)
We define the parity function as follows.

---

Published as a conference paper at ICLR 2026
Definition 2. Boolean function PARITY {0, {0,1} is defined as follows. For any X {0,1)"
PARITY(X)
Xi-
1=1
is well known that PARITY is not in AC (Furst et al.
1984
Håstad
1986).
We show the separa-
tion result using the following distribution.
Definition 3. Distribution t is defined as the uniform distribution over all n-bit strings with even parity (i.e. {(21...., 2n, PARITY) 0}).
In this section, we assume that DLMs consist of AC circuits. Note that constant-precision constant- depth Transformers with poly-sized embedding size can be simulated by AC circuits Li al. (2024), and most current DLM implementations are based on Transformers Nie et al. (2025 ; Yang al. (2025). Besides, Transformers with hard attention mechanism, where each attention block can only attend to the position with the largest score, can be simulated by AC circuits as well Hao et al. (2022). Hence, we believe that our results reflect the true expressiveness current architectures. In particular, for the task of sampling from D the sampling algorithm described above is very simple and can be easily simulated by Transformers.
4.1 UPPER BOUND
In this part, we show that DLMs with revision can sample strings from D in two steps. Theorem 4.1. DLMs with revision and = n can generate D in two steps, such that the predictor and function F are both represented by NC circuits.
Proof. Like the proof of Theorem 3.1 we first describe the generation process that wish to realize, and then show the circuit construction. We also keep the notation that represents the sequence after the i-th generation step.
Our goal is to generate (z),.... (2!,...,2") ~ De Let (u'...., v") E 10, nd be defined as y is easy verify that (yt...., ..... y"-,, Un-1, and y" 0. Furthermore, z y² and
+ =" 2 = yy By' for = ,. by definition, so we can easily recover z from y. Hence we may gen- The procedure above can be implemented by DLMs with revision easily: In the first step, we generate (y) .y...."- and y" 0. In the second step, we calculate 11 y² and 2¹ y @ --1 for i 2, ... n. Below, we describe the circuit construction in detail.
erate t with the following process: To M I1 y, 22
Un-1,
Function F always outputs all-one vector of length n. Formally f(x) = 1 for all x E (0, 1) 1)22.
Now let us describe the circuit for p(-(æ;). We need to first identify whether we are in i = 0 or i by looking whether the first token masked (x)), and then carry out the corresponding computations. Hence, for every E {0, 1}.
(xt A RR) (-x A x²) (xt A Ri) (-x
if =
2j-1 Xi+1 X++1
2j
Xi
+ x 2
if if <j<jn R Un-1
(xt v (-xt
X
2
Xi 2)-
if
The above shows p(- (or) can be implemented easily by a constant-depth circuit (the constant-depth circuit above maps X to X++1 for E {0. 1)). Also, note that every position of x depends on at most one random input bit, so the outputs for different positions are independent conditioned on X This completes the proof.
A similar result holds for DLMs with remasking, stated below.
Theorem 4.2. DLMs with remasking and = n can sample D in O(1) steps, such that the corresponding circuits are AC Here, we also allow the unmask position predictor to depend on the step number in the generation process.
8

---

Published as a conference paper at ICLR 2026
Proof. In the following, we describe the sampling algorithm while also explaining how to implement it using AC" predictor p and an unmask position predictor F. Since here our predictor and F can also depend on the step number in the generation process, at each step we can simply use a new p and F.
Suppose for simplicity that n is even. We will proceed two stages, each consisting of O(1) steps. First, we partition the n-bit input into n/2 2- 2-bit blocks consecutively. In the first stage, at each even position 21, we will sample a bit x' such that the parity of the positions at 2i - and 2i should be x'. Note that all these z' should follow the distribution D2/2- Next in the second stage, we will sample each 2-bit block (i.e., (2i 1, 26) for i = 1,...,n1/22... n/22) uniformly at random such that its parity is x². This gives us the desired distribution D
Stage 1. Sampling the parity of n pairs. For this stage, we will proceed in two steps. In the first step, at all odd positions, we generate y² ,.....,." .y/2 formly random and y" yn/2 = O. Then, in the second step, at all even positions, we compute + gr=1 for E .2.....n/2] and xt y'. After these two steps, we have generated (w', ,2,0² x² ....."" y2/2 ). The first two steps can be implemented using AC" predictor p and
such that (y',..., 1 (y'2-....3///-111 is uni-
x' = y
F easily.
Now, following the proof of Theorem 4.1
(a',...., x222) follows the distribution D n/2
meaning
that they are uniformly random conditioning on having even parity.
Stage 2. Sampling all the n/2 pairs given their parities. Next, we remask all odd positions (all the y" s)s Recall that we interpret x² as the parity of the i-th 2-bit block. The goal from now on is to sample the i-th 2-bit block (2i - 1, 2:) uniformly at random such that its parity is x', which gives us the desired distribution D
Concretely, for each block of the form MO, we will replace it with a new string from {00, 11) with equal probability. For each block of the form M1, we will replace it with a new string from {01, 10] with equal probability. We will do it in two sub-stages, each with several steps.
Stage 2.a. Dealing with blocks of the form MO. In the first sub-stage, for all blocks of the form MO, we sample the first bit randomly. Then, for every block of the form 10, we first remask the to get 1M, and then change the last M to to get 11. In this way, each MO block is replaced by 00 or 11 with equal probability as desired.
Stage 2.b. Dealing with blocks of the form MI. In the second sub-stage, for all blocks of the form M1, we sample the first bit randomly. Then, for every block of the form 11, we first remask the second 1 to get 1M, and then change the last M to 0 to get 10. In this way, each M1 block is replaced by 01 or 10 with equal probability as desired.
is not hard to see that the two sub-stages can be implemented using an AC predictor p and F easily if the predictor and unmask position predictor can also depend on the step number in the generation process. This completes the proof.
4.2 LOWER BOUND
In this part, we show that DLMs without remasking or revision cannot generate D in O(1) steps even if we allow the predictor p and F be AC" circuits. In this way, we establish strong separation between DLMS with and without revision/remasking.
This result should come across as intuitive, given that PARITY is not in AC as mentioned before. During DLM generation, one can only modify mask tokens. When there is only one mask token left, the DLM has to calculate the parity of all other bits, which is not possible. However, formalizing this intuition precisely is challenging because DLM can decode multiple tokens simultaneously in each iteration. As a result, we need an average-case lower bound for parity against AC" as introduced below.
Theorem 4.3 Hästad 2014)). Let d be a constant, and C: (0. 1) - f0,1) be an AC circuit of depth d and size S. There exists a constant ca that only depends on such that
Pr [C(x) = PARITY(X)) < 1/2 + 2 n/oo/lo S) XNU
9

---

Published as a conference paper at ICLR 2026
In plain text, this theorem says that any AC circuit cannot calculate PARITY better than random guessing by too much. Furthermore, this theorem can be directly extended to probabilistic AC circuits as follows.
Corollary 4.4. Let be a constant. Let C: {0,1]a x 10, + {0.1) 1 be a probabilistic AC circuit of depth d and size S. There exists constant ca that only depends d such that
[C(x, R) PARITY(X) < 2 Sy
Pr U--URRRUU
Now are ready to present the lower bound for DLM generations.
Theorem 4.5. DLMs (without remasking or revision) with L cannot sample D in O(1) steps when the predictor p(-(z) and FF are both in AC
Proof. Assume for the sake of contradiction that for any integer n, there exists a DLM that samples D in & steps such that the predictor p and are both in AC
We first set up some notations. Let & = (11) be an arbitrary constant. We define the size of the DLM to be the maximum eircuit size of the predictor p (for all i) and FF. Since both the predictor p
and F are in AC", the size of DLM is upper bounded by n for some constant 1, as long as
is sufficiently large.
Reduction to an Auxiliary Claim. Under the assumption above, we can prove the following claim, which is instrumental for proving our theorem:
For every i {0, 10,,,, there exists O (n")- DLM with L n, that samples D in l steps, where ni 2 n²
J.
Before proving the claim, we first show how this claim helps us finish the proof. This statement implies that size DLM can sample D n² in 0 step, a clear contradiction since one cannot sample any token in 0 steps. The proof of the claim is deferred to the Appendix due to space limit.
Remark. The proof of this theorem includes procedure that converts a constant-round generation of an AC DLM to an AC circuit. One might ask the following question: Why cannot we use the same procedure to obtain an AC circuit from the construction in the proofs of Theorems 4.1 and 4.2 that samples D in single step? Does not this show that DLM without revision/remasking could sample D in a single step? Indeed, one could obtain such AC circuit, but such AC circuit is not a valid DLM. A valid DLM predictor p satisfies p(x((r; = I pd (af (.), so it is impossible to sample distribution with correlation within single step.
Our theoretical analysis advocates that designing a forward process that includes revision and col- lecting training data that contains revision/remasking is very important design component for DLMs and holds greater potential than DLMs without revision or remasking.
CONCLUSION
In this paper, we establish a theoretical foundation for diffusion language models (DLMs) as parallel samplers, showing that with CoT they achieve the optimal number of sequential steps, in contrast to autoregressive models whose cost grows with circuit size. Furthermore, with remasking or revision, it can simultaneously achieve optimal space requirement. Additionally, we prove that remasking and revision not only reduce the memory requirement to scale with circuit width but also strictly expand expressivity, enabling constant-ster step sampling of distributions such parity that standard DLMs cannot realize. These results position DLMs as the most efficient parallel samplers, and highlight remasking and revision essential mechanisms for unlocking their full potential.
10

---

Published as a conference paper at ICLR 2026
6 REPRODUCIBILITY STATEMENT
We state the assumptions in the main text and include proofs for our theoretical results in the Ap- pendix.
REFERENCES
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusiin models in discrete state-spaces. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp. 17981-17993. Curran Associates, Inc., files/paper/20211
2021. URL https::/pproeeeeingg..ooo www.rneeii.... htt.:///ww........oo....ooo.peea File/ 0ll.4988850544710cc6612227111119
Brent and Kung. A regular layout for parallel adders. IEEE Transactions on Computers, C-31(3):
260-264, 1982. doi: 10. 11100TT..182..665999999
Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierar- chy. Mathmattiaal Systems Theory, 17(1):13-27, 1984.
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguisticy, 10:800-810 810, 2022. doi: 10. 162/tacl a. 00490. URL https:://claatthhtt ogy. arg/2022, tac -1..67
J Hästad. Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing. STOC '86, pp. 6-20, New York, NY, USA, 1986. Association for Computing Machinery. ISBN 089791 1938. doi: 10. 10.1145/12130111132 URL
12132
Johan Håstad. On the correlation of parity and small-depth circuits. SIAM J. Comput,, 13(5):1699- 1708, 2014. doi: 10. 10.1137/120897432 URL
org. 10. 001777118994333
Zhengfu He, Tianxiang Sun, Qiong Tang, Kuanning Wang, Xuan-Jing Huang, and Xipeng Qiu. Diffusionbert: Improving generative masked language models with diffusion models. In Pro- ceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 4521 15334, 2023.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 6840- Curran Associates, Inc., neuri iss wtt.ppss.ppcpppeeeeeeeeeee ccppaper Files/paper/2022 4baper. .pdf
2020. URL
file/ Tttee/cccccccc35B44fffff1111.00.
Samar Khanna, Siddhant Kharbanda, Shufan Li, Harshit Varma, Eric Wang, Sawyer Birbaum, Ziyang Luo, Yanis Miraoui, Akash Pairecha, Stefano Ermon, et al. Mercury: Ultra-fast language models based on diffusion. arXiv preprint 17X19. 2025.
Jaeyeon Kim, Kulin Shah, Vasilis Kontonis, Sham Kakade, and Sitan Chen. Train for the worst, plan for the best: Understanding token ordering in masked diffusions. arXiv preprint 0627022502.00668.. 2025.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems, In The Twelfih International Conference on Learning Represen- tations, 2024. URL httttttts////enrree
net forum ?id= 3E 3EWTEy
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In Proceedings of the 41st International Conference on Machine Learning, pp. 32819 12-4482,48, 2024.
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log- precision trans- formers. Transactions of the Association for Computational Linguistics, 1:551-545, 2023. doi: 10.1 162/tal 00562. ARI.http:: //acl antho ogy. org/003., tacl -

---

Published as a conference paper at ICLR 2026
Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji-Rong Wen, and Chongxuan Li. Large language diffusion models. arXiv preprint arXhv:2502.09992, 2025.
Subham Sekhar Sahoo, Mariane Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marro- quin, Justin T Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and ef- fective masked diffusion language models. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan. U. Paquet, J. Tomczak, and C. Zhang (eds.), Advances in Neural In- formation Processing Systems, volume 37, pp- 130136-131184, Curran Associates, Inc., 2024. URL httpps://proceeedddtstss ngs neurips cc wwtpppppp/afesssseeeeeeeeeesssee (lteffe/////ap//2222 F111//800113c1113244481118388883 -awpeeeeeeeaaaPeea-eeaeeeeeeeee- www.-ennneeeeeccceeeeeeee pdf
Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis Titsias. Simplified and general- ized masked diffusion for discrete data. Advances in neural information processing systems, 37: 103131-103167, 2024.
Jascha Sohl-Dickstein Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Francis Bach and David Blei (eds.). Pro- ceedings of the 32nd International Conference on Machine Learning. volume 37 of Proceedings of Machine Learning Research, pp. 2256 2265, Lille, France, 07-09 Jul 2015. PMLR. URL mlr.press v37
htmll
Yuxuan Song, Zheng Zhang. Cheng Luo, Pengyang Gao, Fan Xia, Hao Luo, Zheng Li, Yuchang Yang, Hongli Yu, Xingwei Qu, et al. Seed diffusion: A large-scale diffusion language model with high-speed inference. arXiv preprint arXiv:2508.02 02..0///999 193, 2025.
H. Vollmer. Introduction Circuit Complexity: Uniform Approach. Texts in Theoretical Com- puter Science. An EATCS Series. Springer Berlin Heidelberg, 1999. ISBN 9783540643104 104. URL
https://books google wttp:eeeeeccmmmeeee
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Chi, Quoc Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24833 2022.
Zhihui Xie, Jiacheng Ye, Lin Zheng. Jiahui Gao, Jingwei Dong, Zirui Wu, Xueliang Zhao, Shansan Gong, Xin Jiang, Zhenguo Li, and Lingpeng Kong. Dream-coder 7b: An open diffusion language model for code, 2025. URL httpst::: /ttppv.////xvvv../. http:///wwii...or/////////00/
Ling Yang, Ye Tian, Bowen Li, Xinchen Zhang, Ke Shen, Yunhai Tong, and Mengdi Wang. Mmada: Multimodal large diffusion language models. arXiv preprint arXiv:2505. 15809, 2025.
Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and Lingpeng Kong, Dream 7b: Diffusion large language models. arXiv preprint arXiv:2508. 15487 2025.
12

---

Published as a conference paper at ICLR 2026
A MISSING PROOFS FROM SECTION 3
Theorem 3.2. Let C be a circuit with depth d, width w, m output bits, n input bits, and random input bits R ~ U". There exists DLM M with CoT and remasking with length L = 2w + 2 [log(d 1)], such that the distribution of Mg) is the same as C(q, R). Furthermore, the number of decoding steps is d + 1, and p. F, F,G 9 are all represented by circuits with Oloog d) depth.
Some useful functions. Again, we first introduce some functions that useful for the construction, and then show that they can be realized in constant depth.
Function bin N - {a, b) [og[d+1)] form.
1)1
is function that turns a natural number into its binary
Boolean function ADD Va + f0, 1)" is defined as the function that outputs the binary number represented by the input plus one. When input is b", the output is 0%.
2d is defined as Boolean function IDENTIFY, : b]d {0, 1} where integer outputting and only if the input is bin(i).
Note that ADD is in NC², following from a well-known result in circuit complexity (Brent & Kung 1982]. This means that the AND logic with inputs can be realized by AND with 2 in-degrees in Olog d) depth. The same holds for IDENTIFY which follows from its alternative definition:
IDENTIFY,
A (x' A bin(i))) v (-x² A -bin j=1
Note that Ollog d) is still constant with regard n, so using these two circuits do not violate our restriction on constant-depth circuits.
Proof of Theorem 3.2) In this proof, we use the same notations as those of Theorem 3.1 the proof strategy is similar. Again, we assume that all input vertices are in the first layer, all output vertices in the last layer, and there is no random bit in the first layer. Furthermore, we assume that is even without loss of generality.
Before describing the generation process, we first partition x; into two blocks, each with length w + d", Here d' = [log(d + 1)T. With d' bits, we can record a layer index. Each block is used to record the output from a layer, together with the binary encoding of the layer index. These two blocks are used in an alternating way to store the output from the current layer and that of the next layer. Similar to the construction in Theorem 3.I iteration.
we simulate the calculation of one layer in each
The generation process. Now we formally describe the generation process that we wish to realize. As before, we use the subscript of æ to denote the iteration index. In the beginning, we have To = MM--". For 0 < i S d, we set
Jy "= 1s"" Mw-w' bin(i)M"*e*
when is odd,
J; =w+d" bin (i)M"-"" u +1
when i is even,
In every iteration, we calculate the output of the next layer based on the output of the current layer and write it in the masked block. After that, we remask the block, recording the current layer output to reserve space for the next iteration output. In the end, the DLM outputs o r -.m++1:7.
useful construction of multiplexers. Before delving into the construction detail, let us introduce structure that appears many times: we need to construct a circuit that selects which circuit to use based on current layer index i, i.c. a multiplexer. Formally, we have circuits D Di...., Da with single outputs, and we want to construct circuit D such that outputs D(x, bin(i)) = (z).. This can be realized with an (log d) overhead circuit depth and O (poly (d)) gates because we may construct
D(x, bin(
V IDENTIFY (1) A D,(x).
k=1
13

---

Published as a conference paper at ICLR 2026
Here the OR logic with d imputs can be realized by OR with 2 in-degrees in O d) depth and IDENTIFY has (llgg d) depth. In this proof, bin(t) is either w gotloodd" or x w +1w+2dd" whichever not masked. Formally, for = =
bin(i) (x* x (xx(uttdt))) v (xxx=x2(xx5))
As result, in the rest of the proof, when we need multiplexer, we only need to construct D; separately.
Construction of F, 9 and p(- We first construct F. When i need the set of unmask positions Sp = {w 1, w + d²) For 0 < < d, we need the set of unmask positions
S: {w + d" + l...... + 2d" L w i+ + 1, 1]
when i is odd,
S w
w
d')
when is even.
Formally, let (x) = { E S.). then we could use the multiplexer constructed above to realize the desired J. Such multiplexer usage is similar for the construction of & and p.
Constructing G is similar to constructing F. When i = 0, T = E. For 0 < i < d,
T (1...., w + d²} T = (w d" + +1,....,
if i is odd,
if is even.
Finally, we construct p. Like the proof of Theorem 3.1] we only need to construct the output po- sitions inside S. Again, (t + 1)-th layer bit outputs. When i 0, we have
C; denote the circuit from the i-th layer token outputs to the
x w+bwu+d = bin(1).
For <i d and is odd we have
Ce le R.)
if wit1 +1 L
2j-1 2j X++1 0, Xi+1
R4 Uwtt
ADD (1 (
5-w if wf + dr +15 w 2d
This simulates the circuit computation from the i-th layer to the (i + 1)-th layer, and increments the iteration index. Similarly, for 0 < xisi d and is even we have
C. 2 L 1- -IIL Rá
if < S '41
Rs Uw
X 0, x
ADD (2)((2tttt (2fttdtlotdtdd))
if + 1 S S w + d"
B MISSING PROOFS FROM SECTION
4
Notation for the Claim Proof. Let us now show how to prove the claim by induction. The case when i = 0 follows directly from our assumption. Now, assume that the claim holds for i, and we prove it for i + 1. Here we use similar notations the proof of Theorem 3.1 Let S = F(M")) be the set of positions to be unmasked in the first iteration, and x² ff, b)lsi be the sequence of sampled tokens in the first iteration. Since the marginal distribution of D on S is U111,, and
DLM without revision or remasking cannot change unmasked tokens, we must have x: USS1) Furthermore, let n4 1S1 be the number of masked tokens in Z2. Since t D must have m
High-Level idea of the Claim Proof. Before going into the details, here we introduce the high-level idea. The central argument is to show that m 2 yn, for sufficiently large n,, To prove this, we will show that construct A circuit that approximates PARITY (x) for x {0,1) Sil and
14

---

Published as a conference paper at ICLR 2026
the approximation becomes more accurate as is smaller. The circuit lower bound in Theorem 4.4 would then give us lower bound on m as AC circuit cannot approximate PARITY very well. Besides, we can construct a DLM that samples D. in l - 1 steps using a DLM that samples D in - steps. Combined with 2 nn, finish the induction step.
Key Construction the Claim Proof. The construction of circuit C' that approximates PARITY (x) for x E {0, 1} | ( is as follows:
Set the positions from set SJ in 22 by x using the correspondence 0 + a, 1 + b. Set other positions of 22 to be M.
Simulate the DLM starting from for ---i-- steps and obtain output tokens on [ms] ( In]], The DLM outputs sequence It-i. Circuit C Output 0 if x; are all and output random bit otherwise.
This circuit is in AC because every iteration we apply an AC circuit on I and é = 0(1) Be- sides, outputting whether the outputs are all a can be realized by an AND gate with unbounded fan-ins. Since parity of the output sequence (ARITY())-+) PARITY
0 definition of D we know As a result, the constructed circuit calculates parity slightly better than random guess on average by precisely predicting the parity in the case when ( is all as we must have PARITY (I:5)) 0. =6-
PARITY (i(-))
[m:]/s
Now calculate the probability that C computes parity correctly over input x USS. It is easy to verify that the distribution of gl conditioned on y with parity zero is D -= Hence
the probability of u2-1 [n:]/51 being all a 2-m. Therefore the probability that C outputs the parity
correctly is
1 + 2 (m+1).
2 1+
2
Note that C has constant depth and size ng. applying Theorem 4.4 we know that must have
1 eq + (m++) < (lowng)d
ca(R4 m)
cd-1 (log(n; m))
Finally, since the DLM samples perfectly from D when setting Wi be all-zero, it samples Der over the positions in [n.] S1. In this way, obtain a DLM that samples from D
For sufficiently large n,, have v M
steps, completing the induction.
"Since the induction ends in steps, sufficiently large n, can always realized by sufficiently large
15


Reviews:
[{"review_id": "gnUpRLzbCY", "reviewer": "Reviewer_vuFd", "summary": "This paper provides a theoretical analysis of Diffusion Language Models (DLMs) by leveraging the framework of  Boolean circuit complexity. DLMs have become very popular recently as they allow faster inference than Autoregressive (AR) models via parallel decoding. The manuscript represents parallel computation using circuit depth (time) and circuit width (space). They analyze DLMs with some (unusual) Chain-of-Thought (CoT), acting as a kind of scratchpad, and two increasingly popular inference-time mechanisms: remasking and updating (modifying already unmasked tokens).\n\nThe paper establishes the following results:\nTheorem 3.1 shows that DLMs using sufficient CoT can simulate any depth-$d$ circuit in exactly $d$ rounds. This achieves the theoretical minimum for parallel computation, contrary to AR models which require steps proportional to circuit size.\nTheorem 3.2 shows that by remasking and updating with CoT, DLMs can achieve optimal time ($O(d)$ steps) and optimal space (memory proportional to circuit width $w$).\nIn Section 4, the paper shows that standard DLMs with components restricted to the $AC^0$ complexity class cannot sample the uniform parity distribution in constant time, whereas DLMs with updating/revision or remasking can.", "questions": "I think it is accepted that transformers are more powerful than $AC^0$. What happens to Theorem 4.5 in this case? If the separation does not hold anymore, what does this imply about the necessity of updating/revision for expressivity in practice?\n\nIs there any evidence, whether theoretical or empirical, that standard diffusion training objectives encourage the model to discover the clever time/space-optimal strategies  outlined in  Theorems 3.1 and 3.2? If it is not the case, can you think of any objective that would explicitly force he model to utilize revision/remasking effectively for few-round decoding?\n\nHow robust is the $O(d)$ round complexity to the optimality of the scheduler $\\mathcal{F}$? Do existing suboptimal (unmask random tokens) or adaptive schedules (i.e. greedy decoding) significantly increase the required rounds?\n\nBeyond parity, can you think of other types of distributions exhibit hardness for standard DLMs but become tractable with updating/revision?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality: The paper is original as it is (to the best of my knowledge) the first paper that analyzes the parallel sampling capabilities of DLMs through circuit complexity ideas, so it is an original combination of ideas from theoretical CS and generative modeling. \n\nQuality. The main results are rigorous and the proofs are constructive. I am not an expert on this type of results but could follow (most of) them. Theorem 3.1 provides an equivalence between circuit depth and decoding rounds. The construction in Theorem 3.2 appears non-trivial, it achieves near-optimal space complexity using remasking/updating. The expressivity separation of Section 4 provides a concrete example demonstrating the limitations of standard DLMs.\n\nClarity. The paper is quite difficult to read but it is also because it brings two literatures together. It provides a  formalization of the DLM inference process (Algorithm 1) which defines quite clearly the roles of the predictor, the scheduler, CoT, remasking, and updating/revision. The mapping between these components and Boolean circuits is clarified in Section 2.2 and is key to the understanding of the theoretical analysis.\n\nSignificance. This provides positive results justifying the advantage of DLMs over AR models, as sequential steps scale with circuit size rather than depth. It also shows that heuristic techniques proposed to improve DLMs (updating/remasking) are indeed mechanisms necessary to achieve optimal space efficiency and expressivity.", "weaknesses": "My main concerns are how these theoretical results relate to practical DLM training and inference; i.e. the presented results are interesting but I am not convinced they are telling us much in particular about existing DLMs and whether there is a path to exploit these results to obtain better DLMs.\n\nExpressivity and Learnability. The main results (Thms 3.1, 3.2) are existence proofs. While they show that an optimal predictor $p$ and scheduler $\\mathcal{F}$  exist for specific circuit classes, they fall short of addressing whether these can be learned by standard architectures using standard ELBO objective. It would be beneficial to explain (empirically or theoretically) whether standard training technique can be learned via standard stochastic gradient techniques or whether these techniques tend to find less parallelizable solutions. \n\nComputational Cost. Optimality is defined as minimizing the number of sequential rounds. This does not really take into account the actual computational cost or wall-clock latency of using predictor $p$ and scheduler $\\mathcal{F}$ in each round. It would be useful to clarify that the results do not appear to guarantee lower overall FLOPs compared to AR models (correct me if i am wrong), only lower latency for an idealized parallel hardware. \n\nComplexity of the unmasking schedule. The optimality results appear to rely on an unput-dependent, and dynamic unmasking schedule $\\mathcal{F}$ that precisely identifies which tokens (circuit nodes) to compute next. This is much more complex that what is typically used in practice. It would be beneficial to discuss the schedule$\\mathcal{F}$ . How robust are the results if you were to modify the $\\mathcal{F}$, would one be far off the optimal? how would we learn it practically?\n\n$AC^0$ Constraints. The  results of Section 4 appear to rely heavily on the assumption that the predictor and scheduler are constrained to $AC^0$. However, $AC^0$ is a weak complexity class. How would these results translate to practical scenarios where one  has access to much more powerful predictors, e.g., Transformers. It would be useful to clarify the implications of the  $AC^0$ constraint. Would the  architectural separation outlined in section 4 still hold for much more powerful predictors? \n\nCoT. I find the reliance on CoT quite disturbing... In particular because the CoT considered in the theoretical arguments appears to differs very significantly from practical CoT, i.e. a chain of reasoning steps. I think this requires very substantial clarification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "otXgqvwZ9y", "reviewer": "Reviewer_qnmR", "summary": "In this paper, the authors derive some theoretical results on Diffusion Language Models.\nIn particular, they  show that random functions realized by a circuit with depth $d$ can be described by a Diffusion Language Model with $d$ decoding steps (when augmented with CoT). \nInterestingly they show that the length of the sequence to be generated with a (masked) diffusion model to generate a circuit of size $N$ is $N$ while in the case of a forward process with non-masked perturbation or in the case where remasking is used at inference time they can generate the circuit with a sequence length of the width of the circuit.\nFinally, the authors show that if we restrict the building block circuits for the Diffusion Language Model to be in a certain complexity class then  there is exists an example for which Diffusion Language Models with forward perturbation or remasking can achieve the reconstruction of the examplar circuit in $O(1)$ steps and such a bound is not attainable without the ability to remask tokens.", "questions": "* The authors state that \"More recently, DLMs with revision (Song et al., 2025) are introduced and exhibit remarkable capability.\" \nIt is not really clear to me, how the \"revision\" technique differs from a uniform discrete diffusion. In that case, that would mean that we leave the masking world and that strategies such as remasking are not needed. I am wondering if the current framework also allows the authors to understand this scenario?\n\n* Related to this question, I am wondering if the strategy of the authors could be used to understand the benefits of current continuous augmentation strategies such as CCDD [1] .\n\n* What would be the step to extend the results beyond binary vocabulary? What are the blockers?\n\n* Typo line 176 (notation for the input)\n\n\n[1] Zhou et al., (2025) -- Coevolutionary Continuous Discrete Diffusion: Make Your Diffusion Language Model a Latent Reasoner", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "For me the importance of the results is two fold:\n\n* First, they show the impact of remasking (or using a non-masking forward process) by showing that not only Diffusion Language Models can simulate any circuit but also by showing that the sequence length necessary to generate such circuits is limited by the width of the circuit in the case of Diffusion Language Model.\n\n* Second they highlight an example showing the superiority of Diffusion Language Models with remasking (or using a non-masking forward process) by showing that such Diffusion Language Models can achieve the reconstruction of an examplar circuit in $O(1)$ steps and such a bound is not attainable without the ability to remask tokens.", "weaknesses": "I do not have a lot of complains about the paper. \nI will highlight that I am not an expert on circuits so I did find some parts of the paper hard to follow. \n\n\n* I would suggest to clarify the writing especially Section 4. Indeed, in this Section while I understood the results and their consequences I was unable to follow the logical structure. (Again it might be acceptable for experts in circuits but I could not follow).\n\n* Importance of the results: I am not fully convinced that being able to generate circuit is indicative of performance of Diffusion Language Models. In particular, are there real-word scenarios which are well described by the circuit framework the authors describe (sudoku, puzzle?). It is unclear to me that in the case of _text_ this analysis remains relevant. I would appreciate a discussion about this potential limitation. \n\n* All the results rely on CoT, it would be more impactful to understand what would happen without CoT assumptions. \n\n* All the proofs and the main points of the paper rely on the fact that we can perform parallel sampling operations within the framework of Diffusion Language Model. One big omission in my opinion is that speculative decoding/sampling are powerful methods for AR models which unlock parallel sampling for AR models. I think those models and the consequences of the analysis presented in the current paper and its extension to spec decoding is key to understand what are the key ingredients of the proof and what is truly specific to DLM", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p6WHKAmnEY", "reviewer": "Reviewer_kw6r", "summary": "This paper studies diffusion language models (DLMs) which recently appeared as an alternative to autoregressive models for their efficiency at inference time (possibility to generate tokens in parallel). It provides theoretical results on the benefits of DLMs for parallel sampling from the perspetive of implementing boolean circuits. This allow to quantify the efficiency of DLMs in terms of circuits classes, depth and bits to implement them. The main results show that for any circuit of depth $d$, there exists a DLM with chain-of-thought (CoT) that can implement it with $d$ decoding steps. This comes with additional large intermediate footprints. Further allowing DLMs to use remasking and revision extends the efficiency and expressivity of DLMs since they become strictly more expressive than DLMs without revision or remasking.", "questions": "- Thm 3.1 is one of the main results and it is an existence result but does not ensure that a given DLM can achieve this low number of decoding steps. As such, its benefits for practial DLMs is unclear. Could the authors elaborate on that point?\n- Why not considering prompts in Section 4? Since it echoes results of Section 3, it would be interesting to have similar settings. Could the authors elaborate on that?\n- Obtaining meaningful theoretical results often require simplifying assumptions. In line 131, the authors assume that the length with CoT is $L$ while in practice $L$ is larger than q|CoT|o. How would the results change if considering a bigger sequence length $L$?\n- Remasking is assumed to be modeled by a random function $G$ ni line 138. What is it in practice? If different than random, how does it impact the theoretical results?\n\n*Typos*\n- line 176: \"the\" should be removed\n- line 176: $(x, R)$ should be $(\\chi, R)$\n- line 200: $\\mathbb{Z}^+$ is simply the set of integers $\\mathbb{N}$.\n- line 202: \"unmasked\" --> \"unmask\"", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and enough context is given for the reader on the notions used in the paper\n- The subject is interesting since diffusion LMs are more and more used so a better theoretical understanding is of importance\n- The circuit formulation is elegant and the proofs seem sound although I did not check all of the details in appendix\n- The theoretical claims are of great interest and the methodology of comparing DLMs with and without remasking and revision is well conducted\n- The proofs techniques could be of independent interests to study complex models such as neural networks and language models.", "weaknesses": "I list below what I believe are weaknesses but I would be happy to be corrected if I misunderstood some parts.\n- The connection to distribution sampling should be made more explicit\n- The succession of theoretical results without much discussion on their insights for diffusion LMs hinders the contributions\n- Thm 3.1 is one of the main result but only an existence results. As such, it does not ensure that any DLM can simulate any distribution sampling efficiencly nor does it provide guarantees on the existing DLM that can. As such, I find the presentation of this results in abstract (\"We prove that enabling remasking (converting\nunmasked tokens to masks or revision (converting unmasked tokens to other unmasked tokens) together with CoT further allows DLMs to simulate any parallel sampling algorithm with optimal space complexity\") and the rest of the paper misleading. Could the authors elaborate on that (see questions)?\n- Those two weaknessess explained above make unclear the benefits of the current work. While showing the benefits of remasking and revision is interesting, the connection to distribution sampling is unclear and the connection to practical benefits observed in practice is unclear. I believe the paper would be improved with more discussion on that.\n\nOverall, my main issue with the current work is the connection to distribution sampling that is not clear enough and as such, the benefits of the results to explain the current (and potential future) success of DLMs in terms of efficiency and expressivity is unclear beyond the boolean circuit framework. I believe that better connecting that to distribution sampling and practical use of DLMs (still with theoretical results) would improve the current work. This is why I currently lean towards rejecting the paper but a convincing connection would make me lean towards accepting it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vBywAIYAYg", "reviewer": "Reviewer_9o2i", "summary": "The paper provides a theoretical justification on why Diffusion language models (DLMs) can simulate any parallel sampling algorithm using an optimal number of sequential steps. It makes use of the theory of complexity theory and boolean circuits. First, it proves that DLM with CoT can generate any distribution (on binary data) with the minimum possible sequential steps. Second, it shows that DLMs empowered with the remasking and revision abilities, can sample from any distribution with the minimum amount of memory. Finally, the authors characterize more precisely the simulation abilities of DLMs with/without remasking or/and revision, showing  that DLMs with remasking or revision are more expressive.\n\nOverall, the paper is theoretical and contains no experiments.", "questions": "Please see the \"Weaknesses\" section.\n\n1. Can you provide a more clear connection on the relevance of boolean circuits and your theory angle to a broader understanding of DLMs?\n\n2. Can you explain the complexity classes for boolean circuits and why they are introduced the way they are introduced ? Adding some references would be helpful.\n\n3. How does the proposed theory relate to trained DLMs (which can have some approximation errors?)\n\n4. How does your notion of CoT related to a broadly understood notion of CoT?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides a theory of diffusion language models (DLMs) in the context of binary data and boolean circuits, precisely characterising DLMs expressivity and their ability to simulate parallel sampling algorithm with optimality characteristics. To the best of my knowledge, this is the first paper which builds up a theory for DLMs using such an angle.\n\nThe paper contains the key results and all the proofs.", "weaknesses": "1. The authors could steer the readers better at the beginning of the paper on how and why the boolean circuits theory is relevant for understanding DLMs. While the authors provide a presentation & background on boolean circuits, what is missing is the step on how such theory could generalize our understanding of DLMs on arbitrary vocabularies.\n\n2. In boolean circuits presentation, the authors introduce class TC with MAJORITY operation, but such operation is never used (nor this class). It seems to be coming out of nowhere, especially for readers who are not familiar with boolean circuits. I think authors could do a better job to guide the reader on why such complexity classes are introduced in the way they are introduced. Moreover, the authors say \"By definition, it is known that for all i \\in N, ...\", but no reference to such a statement is provided.\n\n3. While I understand that the theory the authors propose is about understanding the expressivity and optimality of \"ideal DLMs\", such theory does not tell us much about what abilities we would have once we train the DLMs. I think the authors should at least include a discussion about that in their paper.\n\n4. The authors introduce CoT as essentially some intermediate sample steps which DLMs could perform, but CoT is more than that -- it is highly structured prompt of very specific type. The theory proposed in the paper does not make this distinction. I think therefore term CoT might not be correct as it is related to a broader literature. Could authors please explain how CoT they describe connects to CoT which is generally used in the LLM litterature?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)