On the Reasoning Abilities of Masked Diffusion Language Models
Authors: Anej Svete
Ashish Sabharwal
Venue: ICLR 2026 Oral (2026)
Keywords: diffusion language models
formal language theory
boolean circuits
expressivity
transformers
masked diffusion models
chain of thought
looped transformers
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We prove that masked text diffusion models are equivalent to padded looped transformers, can solve all problems that chain-of-thought transformers can, and are more efficient on certain problem classes due to their parallel generation mechanism.

Abstract: Masked diffusion models (MDMs) for text offer a compelling alternative to traditional autoregressive language models. Parallel generation makes them efficient, but their computational capabilities and the limitations inherent in their parallelism remain largely unexplored. To this end, we characterize what types of reasoning problems MDMs can provably solve and how efficiently. We do this by connecting MDMs to the well-understood reasoning frameworks of chain of thought (CoT) and padded looped transformers (PLTs) in the finite-precision log-width setting: We show that MDMs and polynomially-padded PLTs are, in fact, equivalent in this setting, and that MDMs can solve all problems that CoT-augmented transformers can. Moreover, we showcase classes of problems (including regular languages) for which MDMs are inherently more efficient than CoT transformers, where parallel generation allows for substantially faster reasoning.

Published as a conference paper at ICLR 2026
ON THE REASONING ABILITIES OF MASKED DIFFU- SION LANGUAGE MODELS
Anej Svete* ETH Zürich aavete@inf.ethz.ch
Ashish Sabharwal Allen Institute for Al
ashishs@allenai.om org
ABSTRACT
Masked diffusion models (MDMs) for text offer a compelling alternative to tradi- tional autoregressive language models. Parallel generation makes them efficient, but their computational capabilities and the limitations inherent in their parallelism remain largely unexplored. To this end, we characterize what types of reasoning problems MDMs can provably solve and how efficiently. We do this by connecting MDMs to the well-understood reasoning frameworks of chain of thought (CoT) and padded looped transformers (PLTs) in the finite-presd snite-precision log-widhe setting: We show that MDMs and polynomially-padeee PLTs are, in fact, equivalent in this setting, and that MDMs can solve all problems that CoT-aagmented transformers can. Moreover, we showcase classes problems (including regular languages) for which MDMs are inherently more efficient than CoT transformers, where parallel generation allows for substantially faster reasoning.
INTRODUCTION
Many complex problems can be decomposed into smaller, independent sub-probie boob-problms,, making them naturally suited for parallel computation. For example, expression by evaluating its sub-expressions independently and combining the results (see Fig. 3). However, dominant autoregressive language models (LMs) tackle these problems sequentially. Meth- ods like chain of thought (CoT), for instance, generate solutions one step at time, failing to capitalize on the underlying parallel structure. Parallel generation by masked diffusion models (MDMs) offers compelling alternative. Recent advances have positioned MDMs as viable contender to autore- gressive LMS in language modeling, code generation, and even molecule design (Lou al., 2024; Zhang et al., 2025; Sun et al., 2025). However, the fundamental reasoning capabilities of MDMs remain poorly understood, which limits the extent to which we can leverage their potential and apply them to appropriate tasks. This work bridges that gap by providing the first formal characterization of the expressivity of MDMs, clarifying their fundamental computational strengths and weaknesses.
compute the value of mathematical
Sequentiality Bottlencek under log N stops.
Cor 3.7
Added stochesticity
Extra steps
Padded Looped Transformers
3.1
Masked Diffusion Models
Chain of Thought
Farm output space
Extra output space
Figure I: A summary of masked diffuuion model expressivity in relation to padded looped transform- ers and chain of thought. X + y indicates the inclusion of X' in V. Dashed arrows represent strict inclusions. Red arrows denote novel results. Edge labels with blue background indicate constraints on the source node, while labels with orange background indicate constraints on the target node.
Our analysis builds upon the study of LM expressivity- the formal characterization of the problems whose solution the neural architecture of an LM (with appropriate parameters) can express. While
This research was conducted while interning the Allen Institute for AT.

---

Published as a conference paper at ICLR 2026
Masked Diffusion Models
Chain of Thought
log N sepp, N oupput Tom.
Constantty -man steps
Ing steps (Nl ounpur
(oly(M) paspu
Coa, 3.1
Reg
NC
AC
AC
Figure 2: A summary of masked diffusion model expressivity in relation classical complexity classes. X' - y indicates the inclusion of X' in V, and X' <-> y indicates equality. Dashed arrows represent strict inclusions. Red arrows denote novel results. Reg refers to all regular lan- guages. Edge labels with blue background indicate constraints on the source node, while labels with orange background indicate constraints on the target node (in case ++, on MDMs).
Tree Structure
5
25
5
25
Three unmasking Steps
5
m
Eleven chain thought steps:
Figure 3: Two strategies for solving a mathematical expression. (a) Parallel: Parallel computation of intermediate values (three steps). (b) Sequential: Step-by-step generation (eleven steps).
this field comprehensively describes autoregressive LMs, its findings do not directly apply to MDMs due to their fundamentally different, non-sequential processing of text, leaving the theoretical studies of these two paradigms largely disconnected. Prior theoretical work MDMs has focused on the limitations of their factorized backward process and its convergence properties. This research has shown that while MDMs can approximate n-gram LMs with constantly many denoising steps, the number of steps must grow linearly with the string length even for simple LMs such as probabilistic regular languages (Feng al., 2025; Li & Cai, 2025).! However, the asymptotic nature of these findings, together with the strict assumptions on the theoretical model, makes difficult to draw concrete conclusions about the practical reasoning capabilities of MDMs, leaving a critical gap: A theoretical framework for MDMs that is both (1) formally rigorous enough to provide a comprehensive picture of how MDMs can use the combination of parallelism and iterative refinement for formal reasoning, and (2) faithful to how they are implemented in practice. Our work introduces such framework, providing a tight characterization of their reasoning capabilities.
Concretely, we connect MDMs implemented as finite- pratte-prciiion transformers with logarithmically- growing model width to known reasoning paradigms of CoT (Wei et al., 2022), looping (Dehghani et al., 2019), and pause tokens (I (Lanham et al., 2023). For example, we formalize:
Takeaway 1 (Thms. 3.3 and 3.4). MDMs can perform CoT reasoning with some overhead and the MDM denoising process can (inefficiently) simulated by CoT by generating one symbol at a time.
We also show how MDMs can solve complex problems by solving easier sub- trob-probeess in parallel, which makes them inherently more efficient than CoT on parallelizable problems.
Takeaway 2 (Cor. 3.7). MDMs are provably more efficient at parallelizable problems than CoT.
We refer to the fact that CoT cannot take advantage of this parallelism as the sequentiality bottleneck of COT. Takeaway highlights the potential efficiency gains of parallel CoT that generates multiple symbols at once. Our analysis, in fact, identifies a tighter and more natural connection between MDMs and this variant, which we refer as PCoT. The parallelism of MDMs also facilitates close
We provide detailed overview of related work in App. A.
2

---

Published as a conference paper at ICLR 2026
connection with looped and padded transformers, where looping naturally maps denoising steps and padding tokens to the generated tokens of an MDM. We find that the class of problems solvable by MDMs is, in fact, precisely equivalent to that solvable by padded looped transformers. Takeaway 3 (Thm. 3.1). MDMs are equivalent to PLTs.
These connections allow us to leverage known characterizations of CoT and PLTs together with classical complexity theory results to understand the fundamental capabilities and limits of MDMs (Li et al., 2024; Saunshi et al., 2025; London & Kanade, 2025; Svete et al., 2025). For example, with N representing the length of the input string and with AC for d N being the standard class of Boolean circuits with AND, OR, and NOT gates and depth (log" N), we obtain:
Takeaway 4 (Thm. 3.2). MDMs with log N denoising steps can recognize regular languages.
Takeaway 5 (Cors. 3.3 and 3.4). For d E N, MDMs with (log" N) denoising steps and poly(N) output space are equivalent to AC As - LC, this yields NC, the class of all parallelizable problems. With constantly many denoising steps (d = 0), MDMs are equivalent the limited class AC i.e., they are no more powerful than standard transformers and, e.g,, cannot recognize all regular languages.
We summarize these takeaways and their relationships in Figs. I and Our proofs emphasize the affordances and difficulties in solving reasoning problems with MDMs. We find, for example, that the discrete nature of the generated text, which serves as a communication channel between individual denoising steps, limits the amount of information that can be passed between steps. This necessitates extra output space to store the intermediate computations and is analogous to the discrepancy between fixed-preet reddppreisioon and leg-precision transformers (Li et al., 2024), and the difference between the classes AC and TC, the class of circuits with threshold gates. We find that positional encodings that carry information computable by transformers themselves are crucial in locating this information. We also observe that, while unmasked attention makes MDM attention patterns flexible, it complicates left-to-right processing, which is often natural in human language find that exact implementation of causal masking requires quadratically more output space.
2
PRELIMINARIES
This section introduces the preliminaries and notation used throughout the paper. We reserve the main text for the high-level intuitions and defer technical details to App. B.
2.1
TRANSFORMERS
We analyze maakedd transformers for string generation and classification. We present the full model App. B.4 and focus here on the most relevant aspects.
Transformer families. We study finite precision transformers where the value of each parameter and activation is represented with a fixed number of bits. We allow the model width, i.e., the size of the contextual representations, to grow logarithmically with the input length N. This is standard assumption in the literature on transformer expressivity (Li et al., 2024) since it is necessary and sufficient for the model to uniquely identify input positions, and aligns with modern implementations of quantized but wide transformers. The growing width results in a separate transformer TN for each N, yielding a family (Tw) New of transformers. We enforce L-uniformity in the family by requiring an associated Turing machine that constructs Ty in Olog N) space (cf. App. B.4).
(Parallel) CoT transformers. CoT reasoning enables sequential processing by solving problems in multiple steps (Wei et al., 2022). It is an integral part of today's ' popular "reasoning" models and substantially increases transformers' expressivity (Li et al., 2024; Merrill & Sabharwal, 2024). We define our idealization of CoT transformers in App. B. B.4, including parallel CoT transformers. which predict p' e N symbols in parallel at each time step, enabling some parallelism if the task allows it."
We denote the classes of CoT and parallel CoT transformers by CoT and PCoT, respectively.
Padded looped transformers (PLTs). Looped transformers repeatedly apply fixed block of transformer layers to the input (Dehghani et al., 2019). This dynamically increases the depth of the
Thhis is different from speculative decoding (I (Leviathan et al., 2023), which generates multiple symbols one time with smaller LM and then evaluates their probability in single pass of larger L.M.
3

---

Published as a conference paper at ICLR 2026
model, enabling more complex reasoning, and does not increase the model size, the same blocks are reused, thus reducing the memory footprint and computational cost (Bae et al., 2025). Such reasoning steps include both sequential and parallel processing, resulting in both efficiency well as depth of the reasoning process. Padded transformers additionally pad the input with blank symbols, which can be used to perform additional computations in parallel. This additional padding space is analogous to increasing the circuit width in circuit complexity. We additionally provide PLTs with external noise applied the residual stream at each step, which enables stochastic computations (cf. App. B.6). We denote the class of padded looped transformers by PLT.
Transformer LMs. An alphabet is a finite, non-empty set of symbols. Its Kleene closure is E Un-o Ln, the set of all strings. A language model is a distribution over Σ Most LMs are autoregressive they define next-symbol distributions p w)) over Σ def Σ u (EOS) for ur E Σ*, where EOS & Σ is the end-of-string symbol. A transformer-based LM computes p.( (u) by linearly transforming the contextual representation of the final symbol to the logits of a distribution over Σ. Moreover, contextual representations can be used for infilling- ppredicing symbols at masked positions. Infilling probabilities (- w) at masked positions in w Enn" are distributions over >. where m $ Σ is the mask symbol and Σn def E 2 {m).
Transformers and formal languages. Plenty of work describes transformer capabilities and lim- itations with formal languages (Strobl et al., 2024). These studies typically frame transformers as language recognizers, i.e., classifiers that decide whether a string w E Σ* belongs to some formal language L = Σ* (Butoi et al., 2025). String membership is usually deterministic and can be formal- ized by determinizing the LM defined by a transformer: The next-symbol and infilling probabilities are used to decode the most probable symbol or decision. 3 The final prediction of I (w E L} E {1, 0) can be made (1) in a single pass by classifying based on the contextual representation of a particular symbol in the string. analogous to classifying based on the CLS symbol in BERT (Devlin 2019), or (2) after "reasoning", ", i.e., solving the problem in multiple time steps. In this case, the transformer's prediction only made after sequence of intermediate predictions that augment its computation and help the final decision. This is analogous to using CoT reasoning for string recognition and can be thought of simulating Turing machine with each step of the CoT process.
al.,
Particularly fruitful has been the study of transformers as Boolean circuits. In particular, our idealization of transformers falls under AC circuits (Li et al., 2024)-Boolean circuits of constant depth, polynomial size, and with AND. OR, and NOT gates of unbounded fan-in- and captures the entire class if padding allowed (London & Kanade, 2025). Other idealizations of transformers can compute functions outside of AC (Li et al., 2024; Merrill & Sabharwal, 2025a) but remain in TC², the class of threshold circuits which add threshold gates (which determine whether the number of inputs exceeds some threshold) to AC circuits. Apps. B.2 and B.4 provide more details circuit classes and their relation to transformers.
2.2 MASKED DIFFUSION LANGUAGE MODELS
Discrete diffusion LMs define a distribution over Σ" by progressively denoising noisy strings sampled from some fixed distribution. Formally, they define forward (noising) process and reverse (denoising) process. The forward process defines a Markov chain over strings that iteratively corrupts them. Common examples include replacing symbols uniformly at random (uni- form diffusion) masking them with the mask symbol (masked diffusion models, MDMs). The latter is the focus of this work. In this setting, the forward process starts from an initial string (0) e Σx of some pre-determined length P and, at each of the (discrete) steps, in- dependently masks symbols with probability determined by masking schedule a ax() E [0, I]:
N 11 (w) (o))
1 11-a(f). if Fwy =
(1 w
aa()) otherwise
The masking schedule is set such that (x(0) = (no masking at the start) and a(1) = (fully masked at the end, meaning that the noise distribution is the Dirac delta on the fully masked string).
SSom work also considers transformers as LMs directly (Svete & Cotterell, 2024; Nowak al., 2024; Borenstein et al., 2024; Svete al., 2024) and shows the (probabilistic) gains afforded by CoT reasoning.
4

---

Published as a conference paper at ICLR 2026
Starting from the fully masked input, the reverse process 2OJT inverts the forward process dro by (1) uniformly selecting some positions to unmask, and (2) sampling the chosen unmasked symbols. After T denoising steps, 9ojr produces a string (0) sampled from the LM defined by the diffusion process. It is this reverse process that is learned from data. Its analytical form is generally intractable, so one usually models parameterized approximation of a single denoising step 4--1 (we((t()))))) I) w()), typically implemented as a transformer, that factorizes across positions:
@ (
w (1))
I -- (e- ()
Eq. (1) enables parallel generation but ignores inter-symbol dependencies at each denoising step.
Much of the existing work on MDM expressivity analyzes the convergence of q- to 20/7 (Li & Cai, 2025; Chen & Ying. 2024; Feng et al., 2025). Studying convergence properties usually requires assuming uniform unmasking and a good approximation of the ground-truth model (e.g.. Li & Cai, 2025; Chen & Ying, 2024; Feng et al., 2025; Liu, 2025).
Assumption 2.1 (Uniform unmasking). The uniform unmasking assumption states that 1e- 1/e generates strings (tt-1) from (()) by uniformly selecting positions to unmask.
Assumption 2.2 (Perfect approximation). Let 9t-1/t be the backward processes of an MDM and p transformer-based LM. The perfect approximation assumption states that q-1je(wn (t-1) p² (wx w)) for all w(() En. * (t-1) E Σ, and n E (1,....//w(!))
w(())=
In words, Assumption 2.2 states that the transformer perfectly models all conditional distributions of the diffusion process.* 4 While this seems necessary, the following observation, proved in App. E, shows that Assumptions 2.1 and 2.2 severely limit the class of functions that the model can compute.
Theorem 2.1. If Assumptions 2.1 and 2.2 hold for an LM p. p cannot compute non-AC functions. 5,6
By assuming that the MDM is unable choose which positions to unmask, the model has no choice in which sub-problems to solve first, which ignores the possibility of problem decomposition and requires the model to be equally good at solving any sub-problem-iinluddn predicting the final answer based on the input directly (with no reasoning steps). This implies that the problem is solvable in single prediction step of transformer. However, the expressivity of single transformer pass is limited-Thm. 2.1 uses the fact that fixed-depth transformers lie in AC (Li et al., 2024). However, not all conditional probabilities have to be known to able to solve algorithms in few steps. Intuitively, by choosing to solve simple subproblems with non-random unmasking, an MDM can avoid the difficult parts. For example, given the current arithmetic expression, one only has to predict the next set of simplifications whiiii are simple functions of the current expression. This motivates to loosen Assumptions 2.1 and 2.2, which we do in our idealization of an MDM.
2.2.1 1 OUR IDEALIZATION OF MASKED DIFFUSION MODELS
We aim to understand the expressivity of the reverse process. To this end, we introduce an idealization that captures its key aspects- ippects-iteratie iiterative unmasking and infilling-ani provides a principled lens for understanding the expressivity of practical MDMs and comparing them to well-knnwn paradigms such CoT. Here, we describe the high-level ideas; see App. B.7 for the full formal model.
We formalize the reverse process with two components: A planner that decides which positions to unmask at each step and a predictor that samples the symbols at the unmasked positions. This loosens Assumption 2.1 and generalizes standard MDMs in which the planner is implicitly defined by choosing the positions unmask uniformly random. It also mirrors popular MDM implementations that gen- erate text by selecting a subset of masked positions-for for example, based on model confidence or ac- cording to learned policy- and predicting the symbols conditioned on the current partially unmasked string (Ghazvininejad et al., 2019; Peng et al., 2025; Zheng et al., 2024; Liu et al., 2025a; Kim et al.,
*Or approximates them well, requiring the error to be smaller than some > 0.
'That is, can only implement LMs whose next-symbol logits can he computed by AC circuits (Liu, 2025). 'An analogous version of the theorem applies transformers TC".
5

---

Published as a conference paper at ICLR 2026
2025; Ben- Den-Hamu et al., 2025).? Discarding Assumption 2.1 also sidesteps limitations of the position- wise independence in Eq. (1), a restriction that prevents MDMs with uniform unmasking matching simple distributions exactly (Feng et al., 2025; Wu et al., 2025). In reasoning problems with a deterministic sequential structure, the ability to decide what to unmask enables problem decompo- sition into sequence of deterministic steps that can be solved in parallel. To connect our analysis to practical implementations, we assume that the planner and predictor are implemented as transformers.
We allow the planner choose resample already unmasked positions. This overcomes another key limitation-the inability to revert decisions and correct earlier mistakes-a challenge that is the focus of much recent research (von Rütte al.. 2025; Song et al., 2025, inter alia). 9 While existing work focuses on reformulating the diffusion process to allow for resampling and refining the resulting training objectives, our idealized MDMs can be seen as complementary approach that foregoes the complications of training and focuses on the expressivity of the generation process itself analyzes what theoretically possible in a very targeted way when resampling is allowed.
We denote the class of our idealized MDMs by MDM. For more detailed discussion, including the theoretical connection of our idealization to existing MDM variants, see App.
3 THEORETICAL RESULTS
This section describes two complementary characterizations of MDM expressivity: One based on their connection PLTs and the other based on their ability to perform sequential CoT reasoning.
Notation. Let T T(N) and P = P(N) be functions of N. In the following, CoT[T] refers to languages recognized by families { NeN of CoT transformers with at most T steps. For MDM,
C (pCoT, MDM, PLT), C[T, P] refers to languages recognized by families in C with at most T generation, denoising, or looping steps, respectively, and P total output or padding symbols. Ö(N) refers to big-O notation that ignores logarithmic factors, and poly(N) to polynomial functions in N.
3.1 MDMs ARE EQUIVALENT TO PADDED LOOPED TRANSFORMERS
Intuitively, PLTs closely resemble MDMs: Both iteratively refine information in parallel- by unmasking and predicting discrete symbols, and PLTs by updating the residual stream." 11 Thm. 3.1 formalizes this, assuming PLTs are supplied with external sampling noise (cf. $2, $B.6) like MDMs.
Theorem 3.1 (PLTs and MDMs).
P] C PLT(T, P]
(2a)
and
PLT[T, P1 c MDN[T, (N + P)D]. (2b)
The simulation of PI.T by an MDM incurs a factor increase in the required padding (cf. Eq. (2b)),
where D is the model width of the PLT. In our setting where D = O(log N), this implies that the classes of pinite-precision MDMs and PLTs coincide up to a logarithmic factor in the padding length:
Corollary 3.1. For any K > 1,
MDM(T. O(N*)) = PLT[T, O(N*)]
(3)
The close connection between MDMs and PLTs allows us to leverage existing results about PLT expressivity understand MDMs. Saunshi al. (2025, Thm. 5.1), for example, show that log-depth unpadded transformers can recognize regular languages. Combined with Cor. 3.1, this implies:
TThm. C.I App. C.I shows that the planner and predictor can be fused into a single model that unmasks symbols based on their confidence. This means that our results apply to this popular model of unmasking.
*This is related the importance of the mutual information and correlations between symbols to MDM performance (Li & Cai, 2025; Wu et al., 2025) and string-level correctness (Feng et al., 2025).
"While our results focus on MDMs that can resample generated symbols, they also apply to non-resampling simulate the former if given additional output space.
MDMs-Thh. C.2 in App. C.2 shows that the latter
10 proofs of statements in this section are deferred to App. E.
1l PL.Ts thus also resemble latent diffusion LMs that diffuse in the representation space. We do not explore this connection here due the superior performance and popularity of MDMs (Zhang et al., 2025) in practice.

---

Published as a conference paper at ICLR 2026
Corollary 3.2. Regular languages are in MDM[log N, Nog Nog.
In fact, we obtain tighter bound with more specialized construction."
Theorem 3.2. Regular languages are in MDM[log N, Nj.
London & Kanade (2025) show that polynomially padded smite-precision PLTs with constantly many steps are equivalent to L-uniform AC the class of AC circuits that can be constructed by a logspace Turing machine (cf. App. B.2). We leverage this result together with Thm. 3.1 characterize the expressivity of MDMs with constantly many denoising steps.
Corollary 3.3 (MDMs with constantly many denoising steps).
(on PLT(O(1), p
L-uniform AC
Allowing for a constant number of decoding steps therefore does not increase the expressivity of MDMs beyond the limited class AC This further corroborates the empirical observation that the number of denoising steps must scale with the input complexity and complements existing results on MDM expressivity as a function of the number of denoising steps (Li & Cai, 2025; Feng et al., 2025).
We can, however, increase expressivity with more denoising steps. Svete et al. (2025) show that finite-precision PLTs with Oloog" d N) steps and polynomial padding are equivalent to L-uniform ACe, similar the case of log-precision PLTs and L-uniform TC (Merrill Sabharwal, 2025a). Thus:
Corollary 3.4 (MDMs with polylogarithmically many denoising steps).
MIog N). poly(]] Ploo N).poly(NV] L-uniform AC
(5)
In particular, since NC S AC for d E (where NC denotes AC circuits with bounded fan-in) (Vollmer, 1999), we get that with polylogarithmic looping and polynomial padding, MDMs converge to NC, the class of all parallelizable problems. Cor. 3.4 also implies that regular languages are in MDM[log N, poly(N)} Thm. 3.2 provides more efficient construction with linear output space. Moreover, Cor. 3.4 implies that L-uniform NC C MDM[log poly(N))
3.2 MDMs AND COT CAN (INEFFICIENTLY) SIMULATE EACH OTHER
While the close connection between MDMs and PLTs provides a useful lens to analyze MDMs in terms of known complexity classes, the lack of practical PLT implementations makes it difficult to draw intuitive conclusions. We therefore complement $3.1 by connecting MDMs and the more popular CoT paradigm, and consider how MDM can behave "autoregressively" like COT. The intuition is simple: An MDM can simulate CoT by unmasking one symbol at a time, effectively mimicking the sequential generation. More precisely, connect MDMs to pCoT since the latter's ability to generate multiple symbols at once naturally maps to MDMs' parallel generation. In particular:
Theorem 3.3 (MDMs can simulate pCoT transformers).
PCoT[T, P] MDM[T, P + (N + P)2]
The simulation incurs a quadratic blow-up in the padding length. This is not due to an inherent feature of the diffusion process but rather the challenge of simulating masked attention with unmasked one (cf. Lem. D.14). 13 In particular, the MDM transformer is causally masked, the blow-up disappears. Moreover, if the unmasked transformer can simulate masking more efficiently (with, for example, more expressive scoring functions), the blow-up can be alleviated. 14 While Lem. D.14 14 could possibly be improved, it is interesting to note that the seemingly more general, unmasked nature of MDMs
1his is possible because the PLT of Saunshi et al. (2025) only stores discrete values in its residual stream. To the best of our knowledge, Lem. D.14 is the first result showing how simulate masked attention with unmasked attention and might of interest in its own right.
"This is, for example, used by Saunshi et al. (2025, Thm 5.4) to show that unmasked PLTs can simulate CoT with no blow-up in the padding using masking function-an additional step in the computation of attention scores that allows for zeroing out of irrelevant keys-and and with iinarly-increasing width.
7

---

Published as a conference paper at ICLR 2026
might negatively impact their ability to align with human-oriente sequential processing captured by causal masking, which could provide a useful inductive bias for the masked models. 15
The other direction of Thm. 3.3 shows that pCoT transformers simulate MDMs.
Theorem 3.4 (pCoT transformers can simulate MDMs).
MDM[T, S pCoT[T, LT(P + N)],
where L is the number of layers in the transformer implementing the MDM.
Again, the factor L comes from the need to simulate unmasked attention in MDMs with causally masked transformers implementing pCoT (ef. Lem. D.13). However, here, the blow-up is only linear. The additional factor of T comes from the PCoT having write out every padding token after each denoising step, as the MDM can unmask tokens in an arbitrary order.
The results above can be summarized by the following sequence of inclusions.
Corollary 3.5. We have the following set of inclusions:
CoT[T]
PCoT[T, 7]
(8a, Prop. B.1)
MDM[T, (N T)
(8b, Thm. 3.3)
= I. + T (N+ ()?)
(8c, Thm. 3.4)
S Co + T (N + +T)
(8d, Prop. B.1)
S Co + + 1)²}.
(8e)
In particular, when T 3 N, we have CoT[T] S MDM[T. O(T3) s (CoT[T,O(TT)]
Cor. 3.5 lower- and upper- bounds MDM expressivity based on the expressivity of CoT transformers. For example, MDM with polynomially many denoising steps remain within the class P, the problems solvable in polynomial time by non-random-access multitape Turing machine. This follows from the equivalence of CoT transformers with polynomially many steps to P (Li et al., 2024).
Corollary 3.6 (MDMs with polynomially many denoising steps). For any > 1, we have that
MDM(T, N* = CoT[O(TN*]]
meaning that MDMs with polynomially many denoising steps remain in P:
(MMppll(N)),ooy(Y))) CoT(poly(N)) P.
(10)
3.2.1 A SEPARATION BETWEEN MDMs AND COT TRANSFORMERS
Merrill Sabharwal (2024); et al. (2024) show that CoT transformers with logarithmically many decoding steps remain in TC Combining this with Thm. 3.2, the widely accepted assumption that TC # NC², and known NC NC completeensss of specific regular languages, we obtain the following separation in expressivity under small (logarithmic) number of decoding steps. We term the inability of CoT to leverage parallelism the sequentiality bottleneck of CoT.
Corollary 3.7 (A strict separation in efficient reasoning abilities of MDMs and CoT transformers).
CoT[log N] ş MDM[log N, N].
(11)
Concretely, MDM[log N, NJ CoTilog Nj, for example, contains all NC'-complete regular languages.
4 DISCUSSION
Strengths and weaknesses of MDMs. $3 provides insights into the suitability of using MDMs for different classes of problems. On the one hand, Cor. 3.7 reveals the sequentiality bottleneck of CoT
15 "Interestingly, some existing work finds that MDMs that decode based to decode autoregressively (Gong et al., 2025). In this sense, the unmasked nature of MDMs could be seen as hurdle that the model has to overcome to eventually rely on more autoregressive generation. This further motivates the development of hybrid models that combine autoregressive generation of entire blocks with non-autoregresssve infilling within the blocks (Nic al., 2025; Arriola al., 2025; Song al., 2025, inter alia).
most confident symbols tend
8

---

Published as a conference paper at ICLR 2026
and expressivity gap between CoT transformers and MDMs with logarithmically many model evaluations: While CoT transformers remain in TC MDMs can solve NC¹ complete problems. This formalizes the intuition that MDMs more suitable for seghly-parllellizblle problems and has implications for the practical applications of these two paradigms with a limited number of model evaluations. For example, the common state-tracking benchmark used evaluate the reasoning abilities (Liu et al., 2023; Merrill et al., 2024) can be solved with MDMs with logarithmically many steps, while CoT transformers require linearly many steps. On the other hand, the equivalence of MDMs with polylogarithmically many denoising steps to the class NC (cf. Cor. 3.4) reveals problems where efficiency gains from parallelism are limited. For example, assuming the widely-believen hypothesis that NC of P. none of the following (P-complete) problems benefit from MDM parallelism:
Circuit value problem: Given a circuit, its inputs, and a gate, calculate the gate's 's value.
Linear programming: Maximize linear function subject to linear inequality constraints.
Context free grammar (CFG) membership: Given CFG G and a string w, is w L(g)?
Horn-satisfiability (P version of SAT): Is there satisfying assignment to a set of Horn clauses?
In other words, these problems, in general, require a "CoT-style" step-by-step sequential solution.
Due to the overhead introduced by unmasked attention of MDMs (such as the inability to maintain KV-cache), such problems are more efficiently solved by standard autoregressive CoT transformers.
Equivalence to padded looped transformers. Cor. 3.1 reveals a tight connection between MDMs and PLTs. While this suggests these two frameworks are largely interchangeable, important dis- tinctions exist. On the one hand, unlike MDMs, standard PLTSs perform sequential computations deterministically. This makes MDMs more suitable for ambiguous generation tasks, where decisions early in the generation make subsequent decisions easier. PL.Ts would, in that case, have to keep track of all possible generations in the residual stream until the final- coal-ddcoding-steee MDMs are easier to train and steer-since their intermediate computation steps are based on partially masked imputs, the model explicitly learns solve complex tasks from random sub-tasks, which benefits their reasoning abilities (Kim et al., 2025). PLTs, in contrast, only receive training signal from the final decision and have to construct the sub-steps of the computation on their own. This could lead to suboptimal utilization of the sequential computation or even to failure to use it at all. Similarly, the human- undrrsaadddet sub-tasks that MDMs have to solve make their training more interpretable and casier control. On the other hand, the more information-rict intermediate states of PLTs make them more efficient at storing and processing information, and the lack of sampling steps makes them more efficient at inference time.
Moreover,
Generalizations. By focusing on transformer- MDMs, we can draw from the rich theory developed on the expressivity of transformers. However, MDMs do not have to be implemented by a transformer-ther could, for example, be implemented by state-space model. Nevertheless, the parallelizable nature of MDMs suggests that any reasonable real-world implementation will include parallelizable components-for example, a model implementable by constant-depth circuit, such as a TC circuit. 16 The close connection between transformers (with logarithmically -rowwing precision and padding) and the class TC (Merrill & Sabharwal, 2023; Li et al., 2024) suggests that the results of $3 will largely carry over to such implementations. We conjecture that, regardless of whether MDMs are implemented by unite-precision transformers (AC" circuits) or more expressive TC circuit, MDM[log" N, poly(NV) would remain in AC (cf. Cor. 3.3) or a similar class like TC.. Moreover, we state the sequentiality bottleneck only for log N decoding steps, since the expressivity of CoT N] is known to be limited. However, we believe that a similar separation exists for polylogarihmmially many decoding steps: While the expressivity of CoT[log* N] has not been formalized yet, it likely does not capture all of ACd, unlike MDM[log" N, polyy(N)) (cf. Cor. 3.3).
Discrepancies. We strive to compare different paradigms fairly by analyzing a specific implemen- tation of MDMs-one based on a specific idealization of transformers. Some inherent differences between the frameworks, however, remain. One is the dichotomy between using causal masking for CoT and unmasked transformers for MDMs and PLTs. We focus on unmasked models to analyze the more natural and popular implementations rather than artificially constraining MDMs and PLTs to causal masking.
16 A similar modeling assumption is made by Liu (2025); Liu et al. (2025b) for latent diffusion LMs.

---

Published as a conference paper at ICLR 2026
Positional encodings. Another impactful decision is the nature of positional encodings (PEs). While we assume relatively simple PEs standard in theoretical literature (in particular, logspace-conputtblee cf. App. B.4), allow them to come from outside source not part of the transformer- they may thus carry information not computable by the model. This highlights a crucial feature: The computational capabillit in the L-uniform transformer family is deliberately split between the PEs and the transformer's s computation mechanism. Fixed-precision transformers are limited to a subset of AC and cannot compute division, modulo, or binary representations (Li et al., 2024). The PEs provide this missing information: Binary encodings of position/length and results of division/modulo operations (see App. D.1). The transformer mechanism can then perform AC operations (addition, thresholding, multiplication by powers of two) on this pre-computed data. Thus, in Thm. 3.2, the transformer is looking up pre-computed (but still simple, log-space) information from the PEs rather than computing it. When chaining decoding steps, modulo and division information is needed for correct indexing-matee power beyond fixed- models. We emphasize that offloading computation to PEs is standard in the expressivity literature (Li et al., 2024; Saunshi et al., 2025; London & Kanade, 2025), often encoding entire circuits to be simulated. In contrast, PEs are simpler: Functions of input position and length, not circuit-specific.
L-uniform PEs a prerequisite for "looping" to increase computational
Relaxing assumptions. Our constructions rely on a planner that perfectly unmasks the input string and an unmasker that models the conditional distributions perfectly. These are idealizations of confidence-basee planners and learned unmaskers. How trained planner can learn to approximate this ideal behavior is an important question-one of learnability rather than pure expressivity, As is standard in expressivity analysis of language models, expressivity is necessary first step before one can analyze how a model can learn to represent such functions. While learnability of formal are aware of any existing results that would characterize
languages is an active area of research, the learnability of functions required for planning (e.g.. modulo and division) apart from the issue of the sensitivity of modular counting (Hahn & Rofin, 2024), which suggests that learning planning behaviour used in our constructions is difficult for transformers.
Empirical validation. The main purpose of this work is largely theoretical. It provides framework for understanding the expressivity of MDMs in relation to other popular paradigms and provides new insights into the tasks that MDMs are well-suited for. In fact, this analysis is motivated by existing empirical results that show MDMs outperforming autoregressive models on tasks that allow for parallel reasoning (Kim et al., 2025; Ye et al., 2025). The lack of literature on training MDMs on formal languages, however, makes difficult to draw concrete empirical implications of the presented results. Thus, we see designing targeted experiments and benchmarks that empirically explore the theoretical benefits of MDMs as an important direction for future work.
CONCLUSION
We describe the expressivity of masked diffusion LMs (MDMs) by connecting them to padded looped transformers (PLTs) and nection between PLTss and MDMs, which leads the equivalence of MDM with polylogarihhmically many denoising steps to the class NC of parallelizable problems. with concrete implications around what problems can benefit from the parallelism afforded by MDMs. We also show that MDMs can (somewhat inefficiently) simulate CoT transformers. We describe the sequentiality bottleneck and the strict expressivity gap between MDMs and CoT transformers with logarithmically many model evaluations. This shows MDMs to be more suitable for sighly-prallellizabee problems, while CoT transformers are more suitable for inherently sequential ones. Overall, our results provide insights into the strengths and weaknesses of MDMs and their suitability for different classes of problems.
(CoT) transformers. This reveals a close con-
ETHICS STATEMENT
This work is theoretical and aims to describe the capabilities of masked diffusion models to better understand their strengths and limitations. We do not foresee any direct negative societal impacts.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
All our results are theoretical and thus reproducible from the provided proof's in Apps. D and E.
THE USE OF LARGE LANGUAGE MODELS
We used Al-based tools (Gemini and GitHub Copilot) for brainstorming and writing assistance. We used the tools in compliance with the ICLR 2026 policies.
ACKNOWLEDGMENTS
Anej Svete is supported by the ETH Al Center doctoral fellowship.
REFERENCES
Afra Amini, Ryan Cotterell, John Hewitt, Luca Malagutti, Clara Meister, and Tiago Pimentel. Generating text from language models. In ACL, 2023. URL https://aallatthooogs org/2023
acl-tutorials../
Marianne Arriola, Aaron Gokaslan, Justin T. Chiu, Zhihan Yang, Zhixuan Qi, Jiaqi Han, Sub- ham Sekhar Sahoo, and Volodymyr Kuleshov. Block Diffussin:: Interpolating between autoregres- sive and diffusion language models. arXiv, 2025. URL https://arxx: http://rrivv..rgb/b///////// 2503. 09573.
Sangmin Bae, Yujin Kim, Reza Bayat, Sungnyun Kim, Jiyoun Ha, Tal Schuster, Adam Fisch, Hrayr Harutyunyan, Ziwei Ji, Aaron Courville, and Se- Young Yun. Mixture-of- dynamic recursive depths for adaptive token-level computation. arXiv, 2025. URL https: wfarxiv.org//ee farg/abs/250 10524.
Learning
Heli Ben-Hamu, Itai Gat, Daniel Severo, Niklas Nolte, and Brian Karrer. Accelerated sampling from masked diffusion models via entropy bounded unmasking. arXiv, 2025. URL https: //arxiv. orgg 2a05/2555.00 24857.
Nina L. Corvelo Benz, Stratis Tsirtsis, Eleni Straitouri, Ivi Chatzi, Ander Artola Velasco, Suhas Thejaswi, and Manuel Gomez Rodriguez. Evaluation of large language models via coupled token generation. In /CLR 2025 Workshop on Building Trust in Language Models and Applications, 2025. URL https::p///// /tpp/reveeereeeeeeeeeeeeeeeeeeee nett//Forrumm1dFFBFFAI
Nadav Borenstein, Anej Svete, Robin Chan, Josef Valvoda, Franz Nowak, Isabelle Augenstein, Eleanor Chodroff, and Ryan Cotterell. What languages are easy to language-model? perspective from learning probabilistic regular languages. In ACL, 2024. URL https: htttp:://allanthology org/ 2024. acl-lon. 807/.
Alexandra Butoi, Ghazal Khalighinejad, Anej Svete, Josef Valvoda, Ryan Cotterell, and Brian DuSell. Training neural networks recognizers of formal languages. In ICLR, 2025. URL
Robin S. M. Chan, Reda Boumasmoud, Anej Svete, Yuxin Ren, Qipeng Guo, Zhijing Jin, Shauli Ravfogel, Mrinmaya Sachan, Bernhard Schölkopf, Mennatallah El-Assady, and Ryan Cotterell. On affine homotopy between language encoders. In NeurlPS, 2025.
Ivi Chatzi. Nina L. Corvelo Benz, Eleni Straitouri. Stratis Tsirtsis, and Manuel Gomez Rodriguez. Counterfactual token generation large language models. In Causality and Large Models Workshop @ NeurIPS 2024, 2024. URL
Hongrui Chen and Lexing Ying. Convergence analysis of discrete diffusion model: Exact implemen- tation through uniformization. arXiv, 2024. URL https: wwtpaawwwww.../////////00000 08095.
David Chiang and Peter Cholak. Overcoming theoretical limitation of self-attention. In ACL. 2022.
URL http::://accaattohooi htwpt/hooolggooor//22222222 acl-long
Ryan Cotterell, Anej Svete, Clara Meister, Tianyu Liu, and Li Du. Formal aspects of language modeling. arXiv, 2024. URL httpt:p:://arilw.ogg/b////////// 04329.
11

---

Published as a conference paper at ICLR 2026
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal 03819.
transformers. arXiv, 2019. URL
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In NAACL, 2019. URL https:
//aclanthology.orggg wwt.aa...rg//111//////
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di Hc, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. In NeurlPS, 2023. URL https: //openreview. net for.mmid-ggtrAgaa...
Guhao Feng, Yihan Geng, Jian Guan, Wei Wu, Liwei Wang, and Di He. Theoretical benefit and limitation of diffusion language model. arXiv, 2025. URL https///arxxx.orrg/ab//2222 09622.
Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial- hierarchy, Mathermatical systems theory, 17(1):13-27, Dec 1984. ISSN 1433-0490. doi: 10.1007/BF01744431. URL htw.h:tpp:////e /rrg///////oo./////./.. 1007/BF0174443)
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-predict: Parallel
decoding of conditional masked language models. In EMNLP-IJCNLP, 2019. URL https:
//aclanthology org/D19-1633
Shansan Gong, Ruixiang Zhang, Huangjie Zheng, Jiatao Gu, Navdeep Jaitly, Lingpeng Kong, and Yizhe Zhang. DiffuCoder: Understanding and improving masked diffusion models for code generation. arXiv, 2025. URL /tttss///arivv.ooo wwwg/bs///aaa 20639.
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? In Lun- Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 14973-15008, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024. acl-long 800. URL https://aclaantholooy/ .og.logoo.oooooooooooooo 2024. ac1-oong.111 800/.
Zhengfu He, Tianxiang Sun, Qiong Tang, Kuanning Wang. Xuanjing Huang, and Xipeng Qiu. DiffusionBERT: Improving generative masked language models with diffusion models. In ACL, 2023. URL https: /aclanhl/cll org/2023. 2222222..222 acl-long. 248/
Selim Jerad, Anej Svete, Jiaoda I.,, and Ryan Cotterell. Unique hard attention: A tale of two sides. arXiv, 2025. URL hhttps://ark:: wwtprrwwwwww..w///////.eea arg/ 14615.
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, 2025. URL httpps///arxtt http:://aaxiv.or//bb///50000 06768.
Tamera Lanham, Anna Chen, Ansh Radhakrishnan, Benoit Steiner, Carson Denison, Danny Her- nandez, Dustin Li, Esin Durmus, Evan Hubinger, Jackson Kernion, Kamilè Lukošiūte, Karina Nguyen, Newton Cheng, Nicholas Joseph, Nicholas Schiefer, Oliver Rausch, Robin Larson, Sam McCandlish, Sandipan Kundu, Saurav Kadavath, Shannon Yang. Thomas Henighan, Timothy Maxwell, Timothy Telleen-Lawton, Tristan Hume, Zac -atfield-Dodds, Jared Kaplan, Jan Brauner, Samuel R. Bowman, and Ethan Perez. Measuring faithfulness in chain-of-thought reasoning. arXiv, 2023. URL /uttts::/arttt wwwrxxvvvvog//eee org arg//bs/222 2307. 13702.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In ICML, 2023.
Gen Li and Changxiao Cai. A convergence theory for diffusion language models: An information- 21400.
theoretic perspective. arXiv, 2025. URL
Jiaoda Li and Ryan Cotterell. Characterizing the expressivity of transformer language models. arXiv, 2025. URL pittps://arxiin http://wwwwwo./////e/eee////// 23623.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. ICLR, 2024. URL https: http:///wppeee/ee////e///// fett 3EWTEy9MTM.
12

---

Published as a conference paper at ICLR 2026
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transform- ers learn shortcuts to automata. In ICLR, 2023. URL https://openreeiieeeee wwwppperreeeeeeeeefeeeeeee wwt.eiiwwwwneeeffmmiiiee. De4FYajFueZ.
Sulin Liu, Juno Nam, Andrew Campbell, Hannes Stärk, Yilun Xu, Tommi Jaakkola, and Rafael Goanez-oombrrllee Think while you generate: Discrete diffusion with planned denoising. arXiv, 2025a. URL https:: pttps://arxsee www.v...o//aaas. wbwp/////////.././////// 226.0/6422.....4
Yuxi Liu. Perfect diffuusion is TC
Bad diffusion is Turing-complete. arXiv, 2025. URL https:
Yuxi Liu, Konpat Preechakul, Kananart Kuwaramancchrroen, and Yutong Bai. The serial scaling hypothesis. arXiv, 2025b. URL https://aaxi...or//aa/////////// 111225077.12444 15549.
Charles London and Varun Kanade. Pause tokens strictly increase the expressivity of constant-depth transformers. arXiv, 2025. URL htt.:tp///rrrvv.or//////////5 21024.
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In ICML, 2024. URL https::/aaxxiv.orgg///e
16834.
William Merrill and Ashish Sabharwal. The parallelism tradeoff:: Limitations of log- erg-prcciiion transformers. TACL, 11:531-5455 2023, URL
tacl-1 1.31-11311 31/.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In ICLR, 2024. URL https::/oppeneww/// nett/forummiddcijiGiPPssh
William Merrill and Ashish Sabharwal. Exact expressive power of transformers with padding, arXiv, 2025a. URL https://arxiv..rr/aa////225 189488.
William Merrill and Ashish Sabharwal. A little depth goes a long way: The expressive power of log-depth transformers. arXiv, 2025b. URL https::/arxiv.org/abbss.s// 25t.//361.3...1....
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. In ICML, 2024.
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, 2025, URL https: //aaxivv.rrg/abs/2eee/ 09992.
Franz Nowak, Anej Svete, Alexandra Butoi, and Ryan Cotterell. On the representational capacity of neural language models with mfain-of-thoughl reasoning. In ACL, 2024. URL https:// aclanthology.orge org/ wtt.g////...e.e w acl-long. 676/.
Michael Oberst and David Sontag. Counterfactual off-po evaluation with Gumbel-max structural causal models. In /CML, 2019. URL https://proceedings mlr presss/v9/oobrsst13 ottp:/eeeennnnnnpp..eeees///e/er html.
Fred Zhangzhi Peng. Zachary Bezemek, Sawan Patel, Jarrid Rector-Brooks, Sherwood Yao, Avishek Joey Bose, Alexander Tong, and Pranam Chatterjee. Path planning for masked diffusion model sampling. arXiv, 2025. URL
03540.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. JMLR, 22(75):
1-35, 2021. URL http:
2t0.://22220002.h.mm html.
Alec Radford, Jeff Wu. Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl, 2019. URL https: //cdn. openai. Sultittakk_eernerss.ou pdf.
Shauli Ravfogel, Anej Svete, Vésteinn Snæebjarnaroon. and Ryan Cotterell. Gumbel counterfactual generation from language models. In ICLR, 2025. URL https: htwprrreiiiieeeef//uuumiiie TUCOZT2zIQ.
Nikunj Saunshi. Nishanth Dikkala. Zhiyuan Li, Sanjiv Kumar, and Sashank J. Reddi. Reasoning with latent thoughts: On the power of looped transformers. arXiv, 2025. URL abs/2502. 17416.
13

---

Published as a conference paper at ICLR 2026
Yuxuan Song, Zheng Zhang, Cheng Luo, Pengyang Gao, Fan Xia, Hao Luo, Zheng Li, Yuehang Yang. Hongli Yu, Xingwei Qu, Yuwei Fu, Jing Su, Ge Zhang, Wenhao Huang, Mingxuan Wang. Lin Yan, Xiaoying Jia, Jingjing Liu, Wei- Ying Ma, Ya-Qin Zhang, Yonghui Wu, and Hao Zhou. Seed Diffusion: A large-scale diffusion language model with high-speed inference. arXiv, 2025. URL https://arxiv www. ht//ab///2055 02193.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? a survey. TACL, 12:543-561, 2024. URL https://aclanttholooog org/2024. tacl-1.30/.
Weigao Sun, Jiaxi Hu, Yucheng Zhou, Jusen Du, Disen Lan, Kexin Wang, Tong Zhu, Xiaoye Qu, Yu Zhang, Xiaoyu Mo, Daizong Liu, Yuxuan Liang, Wenliang Chen, Guoqi Li, and Yu Cheng. Speed always wins: A survey on efficient architectures for large language models. arXiv, August 2025. URL htttts://araat htttp:://arxivoorg/ab////33 org/abs/2508 09834.
Anej Svete and Ryan Cotterell, Transformers can represent n-gram language models. In NAACL, 2024. URL httpss:/aaclaattoooley..o/////// -
naacl-long 381/.
Anej Svete, Nadav Borenstein, Mike Zhou, Isabelle Augenstein, and Ryan Cotterell. Can transformers learn n- n-gram language models? In EMNLP, 2024. URL aaclatooccl org/2024. emnlp-main. 550/.
Anej Svete, Will Merrill, and Ashish Sabharwal. The exact expressive power fixed-precision looped padded transformers, 2025. URL http:: //aeesseee gi github..r. ho/files/ffflllltttt pdf..
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser. and Illia Polosukhin. Attention is all you need. In NeurlPS, 2017. URL /tttps:/ppocceddi:n 3f5ee243547dee9) fidd53c1 c4a845aa
cc/pppper_fllespppprr//e2
Heribert Vollmer. Introduction to Circuit Complexity: Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Seinger-Verlagg Berlin, Heidelberg, 1999. ISBN 978-3-
540-64310-4, doi: 10. (007/978-3-662-039777
Dimitri von Rütte, Janis Fluri, Yuhui Ding, Antonio Orvieto, Bernhard Schölkopf, and Thomas Hof- mann. Generalized interpolating discrete diffusion. In ICML, 2025. URL / / net./formm
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V. Le, and Denny Zhou. Chain-of-thoughh prompting elicits reasoning in large language models. In NeurIPS, 2022.
Chengyue Wu, Hao Zhang, Shuchen Xue, Zhijian Liu, Shizhe Diao, Ligeng Zhu, Ping Luo, Song Han, and Enze Xic. Fast-dllm: Training-fri faiinng-ffree acceleration of diffusion Ilm by enabling kv cache and parallel decoding. arXiv, 2025. URL
22618.
Kevin Xu and Issei Sato. To CoT or to loop? formal comparison between offin--f--thughh and looped transformers. arXiv, 2025. URL httph: https://aarxiv.orgaab//3333 19245.
Andy Yang, David Chiang, and Dana Angluin. Masked hard-attention transformers recognize exactly the star-free languages. In NeurIPS, 2024. URL huR..httpps///pperreeeeeeeeettto FBMsBdH0yz.
Jiacheng Yc, Jiahui Gao, Shansan Gong, Lin Zheng. Xin Jiang, Zhenguo Li, and Lingpeng Kong. Beyond autoregression: Discrete diffusion for complex reasoning and planning. arXiv preprint arXiv:2410. 14157, 2025. URL https: wwwperiwvv.ooogrbr.ee org/abs/2410. 14157.
Lingzhe Zhang. Liancheng Fang, Chiming Duan, Minghua Hc, Leyi Pan, Pei Xiao, Shiyu Huang, Yunpeng Zhai, Xuming Hu, Philip S. Yu, and Aiwei Liu. A survey on parallel text generation: From parallel decoding diffusion language models. arXiv, 2025. URL https://arxxv .rg/ abs/2508.0B3 08712.
Lin Zheng, Jianbo Yuan, Lei Yu, and Lingpeng Kong. A reparameterizzed discrete diffusion model for text generation. arXiv, 2024. URL httpp://aaxiv..rrg/////2200000 05737.
org/abs/23022
14

---

Published as a conference paper at ICLR 2026
A RELATED WORK ON THE EXPRESSIVITY OF MDMS
Existing theoretical work on MDMs focuses on the limitations of the factorized backward process and its convergence properties, which can be linked to formal language generation and recognition.
Feng et al. (2025) analyze the implications of the factorized backward process on the expressivity of MDMs. They find that MDMs can approximate n-gram LM distributions arbitrarily well with constantly many sampling steps and linearly many sampling steps suffice to approximately sample from any regular language. They also provide a linear lower bound on the number of sampling steps required to capture the support of general regular languages- factorization, which is incompatible with the sequential generation of regular languages. Crucially, this differs from our recognition setting in which the string to be processed is given and only its membership decision has to be generated.
consequence of the assumed
This line of work is tightened by Li & Cai (2025), who build on work by Chen & Ying (2024) and analyze the approximation error (measured by the KL divergence) of the distribution generated by MDMs with respect to the number of sampling steps and the mutual information (dependence) between the symbols in different positions. Intuitively, the larger the mutual information is, the larger the number of sampling steps has be capture the same distribution (equivalently, the fewer symbols per step can be generated). They show that the KL divergence between the generated and the ground-truth distributions decays linearly with the number of sampling steps (with scaling that depends on the mutual information between the symbols in the strings), and show this decay to be optimal in general. This generalizes the results on n-gram distributions and regular languages by Feng et al. (2025).
Liu (2025); Liu et al. (2025b) take a different perspective and analyze the expressivity of latent diffusion LMs. They show that, under an analogous assumption to our Assumptions 2.1 and 2.2, latent diffusion LMs converge to the data distribution constantly many steps, which means that the computational depth of such models is limited. They show that breaking this assumption makes latent diffusion LMs Turing complete, analogous to our results in $3.2.
While these results provide useful insights into the limitations and affordances of MDMs, their asymptotic and approximate nature makes it difficult to draw concrete conclusions about the (rea- soning) capabilities of MDMs in the sense of the work transformers' expressivity. Our work complements these results by providing a more fine-grat tne-grrined analysis of MDM capabilities based on their connection to PLTs and CoT transformers, which allows us leverage the existing theory developed on transformer expressivity and apply it directly to MDMs.
B PRELIMINARIES
B.1 NOTATION
Let Σ be an alphabet. A language L is a subset of Σ*_ A language recognizer a function
R: Σ {0, 1}. where 0 and 1 are designated reject and accept symbols. R's language is C(R) del {w E Σ R(w)- = 13. Two recognizers Ri and R2 are equivalent and only if C(R,) = ((R2).
We denote the concatenation of two strings wi, the interleaving of the vectors x, y E R as x 3 E R where
Σ as w2 or simply wi W2. We define
Ded + nos
if dl is odd, otherwise d.
x.
yd
(12)
ya
We use [w] {0, 13 EE to denote the one-hot encoding of symbol w E E. We use (n(n) to denote the binary encoding of natural number using p binary bits and (n) to denote the signed binary encoding (n) 1p. where 1p is the D-dimensional vector of all ones. We will leave out when it clear from the context.
For De E N. we define softmax: : RD_ - TR. as softmax(#),, exp(xa)/ Ed exp(x.) for x e RDD max(x, 03. We denote with P(x') the set of all
and d E [D]. We also use the shorthand [x], del
probability distributions over set X.
15

---

Published as a conference paper at ICLR 2026
B.2 CIRCUIT COMPLEXITY
Computational circuits are model of parallel computation. They have been widely used in the study of the expressivity of neural networks. Circuits process binary input strings through a series of logical operations to produce binary outputs,"? Formally, boolean circuit is directed acyelic graph where source nodes represent the N-bit input, and a single sink node represents the output. Non-source vertices are called gates and are labeled with logical operations (c.g.. AND, OR, NOT). The size of circuit is the number of gates, and its depth the longest path from any input to the output.
A circuit computes function C: {0, 1/W N - {0, 1} for some N N. where 0 and 1 designated reject and accept symbols. The value ((w) for input string w E {0. 1] is computed by evaluating the gates in topological order starting from the input bits. We say that the circuit C accepts string w if ((w) = 1.
Circuit families process input strings of variable length. A circuit family is sequence of circuits del [Cn]NeN where ON processes inputs of length N. A circuit family is said to recognize a language if for any given imput string, the corresponding circuit outputs 1 if and only if the string is in the language.
A circuit complexity class is set of circuit families that satisfy certain constraints size, depth, and the types of gates used. This paper focuses on two common classes:
ACa: Circuits with NOT, AND, and OR gates that have unbounded fan-in and depth Ologg" N). TCd: The extension of AC that adds threshold gates, which output 1 if the sum of their inputs exceeds a given threshold. is known that AC _ TC and AC S TCd For example, PARITY, the language of binary strings with an even number of 1s, is in TC but not in AC (Furst et al., 1984).
NC:: This class consists of circuits that can be computed in parallel with a logarithmic depth. a polynomial number of gates, and constant fan-in. It is known that TC C NC!.
Without additional constraints, circuit families can recogmize undecidable languages by having arbitrary, "hard-coded"" solutions for each input length. To avoid this and ensure the model of computation is realistic, we can impose uniformity condition. circuit family uniform if there exists Turing machine that, given an input of 1 can generate a description of the circuit Cn. In particular, a circuit class L-uniform a Turing machine using Olog N) space can construct its description from the input 1 This ensures the circuits for different input lengths are related by systematic procedure.
B.3 FINITE-PRECISION FIXED-POINT ARITHMETIC
We assume that the operations performed by our computational models rely finite- iinei-precision fixed-point arithmetic. This model is based on ones used by Li et al. (2024); Saunshi et al. (2025); London & Kanade (2025).
Definition B.1 (Fixed-Poine Representation). Let p N be the number of bits devoted each of the integer and fractional parts. We use F, to denote the set
F.
[x+
2
x (-1,1), 10. -
(13)
We define Br del max F, rounded to By. Note, however, that By does nor behave like infinity- it does not "consume" all subsequent operations. For example, Bp x # By for some non-negative x F, is a valid number.
2 All values exceeding Bp are considered of range and are
To handle the results of arithmetic operations that may not be exactly representable in the fixed-point format, we define a standard for rounding.
Definition B.2 (Rounding). For any x E R and any closed subset F of containing O, we define rounding round IF) as the closest number to in F. In case of tie, the value with the smaller absolute value is chosen.
By representing symbols from any alphahet with binary encodings, circuits (or circuit functions) can be used process strings over any finite alphabet. We focus on binary strings for simplicity.
16

---

Published as a conference paper at ICLR 2026
We denote the rounding operation as [.p def round(,, Fp). This operation applied vectors and matrices element wise. All binary operations are defined by first performing the ideal mathematical operation and then rounding the result the nearest representable value in Fp. Division by zero is considered an eтror condition resulting in an incorrect output. We also note that Br/2 = 2 P.
For operations involving more than two numbers, rounding applied iteratively. Definition B.3 (Summation with Iterative Rounding). For p, N E N and x E RN we define summation with iterative rounding to p fractional bits the function SUMp: UNeN(PP) Fp.
where for any N N+ and (Fp)
SUMp(x)
def
.... [x] + r2lp D3
IN
(14)
This iterative rounding process is not associative and the order of operations can affect the final result. Based on this, we can also define more complex operations such as the fixed-point inner product (x. y)p def SUM,( O y). where denotes the element-win product of two vectors, and fixed-point matrix product for matrices A and B, where (A Xp B) <(Ac.) B,j)p
B.4 TRANSFORMERS
We consider both unmasked (Devlin al., 2019) and causally masked transformers (Radford et al., 2019). Concretely, we work with fixed-point transformers whose underlying arithmetic operations replaced with their fixed-point counterparts. A transformer T consists of four parts:
(1) a symbol embedding e: - FD of the form e(w) def V[w] for w E E, where V F |>x and [w] F!d is the one-hot encoding of w,
(2) positional encoding p: N x N- - F?,
(3) I. layers -(1), _(),,..., T(4), each of which consists of two sub-layers: A multi-head self-
attention layer and position-wise fully-connected feed-forward network and
(4) an output layer o of the form ohh) def softmax(EM, (Eh) for E FD, where E e F/
Each layer has its parameters and is indexed by the layer feedforward layers. We use D to denote the width of transformer. A transformer with layers
and the depth for attention and
T ..... (()) computes (1) e FD for 1 E (1....,L) L} and each position n [N] in the input string w = W1 ... Wy Σ* as follows:
(0) de e(wn) + p(n, E F. for n [N]
(15a)
( (1
(T)
NN
(1)
E NXD
(15b)
(1) or H WW!
K0 de HWW
K: DA HOW
e NNDD
(15c)
Q:
Q oe softmax (M( (M(QQKKT)) ((T)) + H NND
(15d)
H(++) de @O )(G()))RXX)) END
(15e)
Here, M: ENNN (F (F (- NxN is the masking function. 18.19 We say that the (th layer 7 (I)
computes the function (!); xD FNXD defined by the function =()); H (1-1) H (1) for
1 [I)...,I.). We also denote with T the function T: Σ* FNxD defined as T: un (L)
We use the following definition of the multi-layer perceptron.
Definition B.4 (Multi-layer perceptron). A multi-layer perceptron (MLP) is function f: EDD - ED that can be expressed as composition of affine transformations and the ReLU activation functtionn
f(x) = ReLU(W,(ReLUTC)
-b,)) + bz),
(16)
where W1 E W2 E D' b F" b2 FD' for D,
Similar to Li et al. (2024); Saunshi al. (2025), define masking with function rather than additive matrix since subtracting Bg from an arbitrary number IF does not necessarily result in Bp.
19 Examples of masking functions include the identity function (unmasked attention) and the identity function on the trianglar portion of the matrix that replaces the lower-triangular part with Bg (causally masked attention).
17

---

Published as a conference paper at ICLR 2026
B.4.1 SCALING TRANSFORMER SIZE WITH INPUT LENGTH
The exact expressivity of transformer model depends on seemingly unimportant details (Jerad et al., 2025). One such example is the interplay between the scaling of the numerical precision p of the values stored in the representations h and the scaling of the width D. To be able to uniquely identify the N positions in the input string, the "volume" of the embedding space, i.e. the number of possible distinct representations h, must be at least N. This implies that the product p D must scale least logarithmically with N: P(N) ((N) = Dilog N). Existing work focuses on two modeling choices:
(1) log-precision transformers where p(N) O(log N) with either constant width ((N)
(1) or polynomial width D(N) = ((poly(NV) (Merrill & Sabharwal, 2023; 2024; Li et al., 2024; London & Kanade, 2025; Merrill & Sabharwal, 2025b;a); and
(2) constant-precision logarithmie-width transformers where p = (11) and D(N) = Ollog N) (Li et al., 2024; Saunshi et al., 2025; London & Kanade, 2025).
Despite having the same volume of the representation space, the two models differ in their expressivity, For example, constant-precision transformers are constrained to use the volume in "distributed" manner across model dimensions without the ability to summarize the information into individual values or store pointers to arbitrary positions in string length. Such summarization required in certain steps of the transformer architecture- example, when computing the attention scores. This limits the expressivity of constant-precision transformers compared to log bog-precision transformers: While log-precisien transformers can compute certain TC functions, constant-precision transformers with polynomial width fall within AC (Li et al., 2024; London & Kanade, 2025). Similar separation results extend to popular variants of transformers: (a) Transformers with chain-of-though reasoning (ef. App. B.5) with logarithmic precision can simulate TC circuits of size corresponding to the number of reasoning steps while constant-precision transformers with polynomial width are constrained to AC circuits (Li et al., 2024; Merrill & Sabharwal, 2024). (b) Transformers with additional padding space (blank thinking tokens; cf. App. B.6) with logarithmic precision can express exactly TC functions while constant-precistt transformers with polynomial width are equivalent to AC circuits (Merrill & Sabharwal, 2025a; London & Kanade, 2025). However, the trend of coarse quantization while increasing the model size makes fixed- seed-precision logarithmic-wide width transformers particularly appealing, which is why we focus on finite precision transformers with logarithmic width.
of these require precision growing with
Analogously to circuit families, each string length N is processed by separate transformer model. To process all of Σ*, we therefore define a transformer family {Tx) } as a sequence of transformers where each TN processes strings of length N. Further, we again impose uniformity condition the family, which will relate the transformers for different input lengths.
Definition B.5 (Uniform transformer families; variant of London & Kanade, 2025, Def. 3.6). Let X be a computational complexity class. transformer family {Tx} X-uniform if there exist Turing machines Mi and M2 whose resource usage is construined by the complexity class X such that:
(1) M1 takes input N and outputs description of Tx, and (2) M2 takes input ([,(Bm) and outputs p(n, N).
Def. B.5 allows for size-dependent transformers while keeping them closely related (as the same Turing machines must construct them for all N). It also facilitates natural connections with uniform circuit classes (cf. App. B.2) (London& & Kanade, 2025). All our results concern L-uniform transformer families, in which case, the Turing machines in Def. B.5 operate in logarithmic space.
B.4.2 TRANSFORMER LANGUAGE MODELS AND SYMBOL PREDICTORS
Transformers can implement (non-) juttoorrorreeesivvee LMs and deterministic symbol predictors. A transformer LM computes the probability distribution over the N + 1sd symbol given the length-N string w as
pC w
ur)
o(h
for क E Σ.
(17)
To define infilling probabilities, let w E Σn be a possibly (partially) masked string of length and let [N] such that w,,, We then define the probability distribution over the symbol at the masked position n as
p'(w| un) der (()
for w E.
(18)
18

---

Published as a conference paper at ICLR 2026
Note that the next-symbol probabilities are computed based the contextual representation of the previous symbol while the infilling probabilities are defined based on the contextual representation at the masked position. That is, for autoregressive next-symbol prediction, the transformer uses the hidden state at the last (previous) position, whereas for infilling, it uses the hidden state at the position to be filled.
To define a deterministic transformer- bbasod symbol predictor, we define a decoding step.
Definition B.6 (Decoding step), For any N E N, let H RNxD, The decoding step Dec: NxD
Σ is defined
Dec H) n argmax of H nn:
(19)
WEY:
where the output function o is applied to H row-wise. This can be used either to deterministically infill the masked positions in the string or deterministicallly predict the next symbol based on the final representation. For next-symbol prediction, we also define the shorthand NS: Σ* - as
NS(w))
Dec(T(w))
(20)
B.4.3 LANGUAGE ENCODERS AND MODEL EQUIVALENCE
We are interested in the expressivity of neural networks as language recognizers and LMs, which at a high level, describes their behavior on input strings. This behavior either the prediction of language membership the computation of string probabilities is completely determined by the contextual representations of the input strings produced by the neural network. We abstract the computation of string representations using language encoder-a length-preserving function Enc: Σ* - P)* for some D E N (Chan et al., 2025; Cotterell et al., 2024). We regard the output Enc(w) of language encoder for a string w as a |w| D matrix, where each row corresponds the contextual representation of the symbol at the corresponding position. In the context of transformers, the language encoder is the function Enc(w) del (L) for w Σ*
eitherr
All aspects of the model's behavior that we might be interested in can be described in terms of the contextual representations- the (logits of the) next-symbol or infilling probabilities are determined by a linear transformation of the contextual representations, and the membership test is determined by a linear classifier based on the contextual representations of the final symbol in the string. Studying the expressivity of model thus reduces to determining what types of contextual representations can be produced by the model. If we can show that two language encoders Enc,, Enc2: Σ* P)* compute the same contextual representations for all input strings, we say that Enc, and Enc2 are equivalent. Moreover, we say that two sets of models are equivalent if each model in one set is equivalent to at least one model in the other set.
Model equivalence and variable-length outputs. Sometimes, we will compare the expressivity of models that produce outputs of different lengths, for example when comparing the expressivity of padded and non-padded models, or comparing CoT-augmented transformers with non-augmented ones. This makes direct comparison of contextual representations more difficult. Whenever this is the case, we will explicitly state how the outputs of different lengths are aligned. For example, when comparing a model that produces outputs of length N with a model that produces outputs of length KN for some constant K E N. we may assume that the first (K - N positions of the longer output are used for intermediate computations and only the last N positions are used to produce the final output. Thus, we will only compare the last N positions of the longer output with the N-length output of the shorter model and base model equivalence on that.
B.4.4 SAMPLING FROM (TRANSFORMER LANGUAGE MODEL
The next-symbol and infilling probabilities from App. B.4.2 can be used to sample from the LM by sampling from (- w) or p- wn), respectively." 20 There are many possible ways to implement the sampling. In this paper, we assume that it is performed using the Gumbel-max trick (Oberst & Sontag, 2019), which both provides a convenient and fast implementation as well as interpretable traces of the sampling procedure (Chatzi et al., 2024; Ravfogel et al., 2025; Benz et al., 2025).
2n practice, the raw prohabilities are often processed with temperature scaling or sampling adaptors (Amini al., 2023). The framework described here can easily he adapted those settings.
19

---

Published as a conference paper at ICLR 2026
Definition B.7 (Gumbel-max sampling). Let I def Eh h RD and E R|EExD be the logits of probability distribution over Σ. The Gumbel-max sampling is defined as
w argmax(Pu' 9w'))
(21)
w'EE
where 9u² are i.i.d. samples from the Gumbel distribution with the cumulative distribution function F(x:) exp(- exp(-x) for x E IR.
is well known that Eq. (21) results in samples from softmax(()) (). The Gumbel-max sampling can be used to either sample the next symbol WX+1 from the next-symbol distribution p(: w) or to sample the masked symbol wn, from the infilling distribution p- w).
We rely the Gumbel-max sampling because it conveniently decouples sampling from the model's representations. In particular, provided that model is able to implement the argmax operation and is able to receive the Gumbel noise input, it can sample from the model's distribution without any additional operations. This will provide a convenient way to precisely link different modeling frameworks in unified manner.
B.5 CIAIUIOP REASONING
At high level, chain-of oftt--ghhthhhttttt (CoT) transformers process a string by generating intermediate reasoning steps. These steps can be seen as generated string itself or as an intermediate thinking process that is used to generate the final output.
Definition B.8 (CoT Generation). A causally masked transformer implementing the next-symbol distribution p: Σ* ( generates strings y1 yr, given w E Σ* as
y/ (- y1 ......90 vt-1)
(22)
where yr EOS and yt EOS for t T.
While some existing work analyzes the distributions induced by CoT transformers (Nowak et al., 2024; Xu & Sato, 2025), much of the existing literature (Pérez et al., 2021; Feng et al., 2023; Merrill Sabharwal, 2024; Li et al., 2024; Saunshi et al., 2025) focuses on modeling string acceptance by CoT transformers by determinizing
Definition B.9 (CoT Acceptance). A cuusally masked transformer implementing the next-symbol Eoi generates the sequence of reasoning steps
predictor NS: Σ
Yt
def NS(W o 31 ... V1-1)
(23)
for Σx, E [T], and pre-determined T E N. NS accepts string u in T steps if yr 1 and rejects if yr
To facilitate more convenient connection to MDMs, introduce parallel thain-of-thouue process that can be seen as generalization of CoT transformers, one that generates multiple symbols once.
Definition B.10 (Parallel chain of thought (pCoT)). Let S: = Eno be causally masked transformer symbol predictor and T, P' N. parallel chain-of-thought transformer NS E* Σn processes string w from Σ. for E [T] as follows:
{L ~ S(w (1) o... o (1-1) m N-
for n E [P].
(24)
p
Whenever T and P are clear from the context, write NS (w) del (0) (T)
PCoT transformer generates strings in Σ" by running the PCoT process on the empty string e and outputting (e).
Definition B.11 (Acceptance by a PCoT Transformer). We say that a pCoT transformer accepts string w if there exist T,, P' such that it holds for ((1) ...o ((T) ( that t rejects ( (T)
NS
0.
20

---

Published as a conference paper at ICLR 2026
We denote the class of languages recognizable by a pCoT transformers that generate P' symbols at time for steps as PCoT[T, PJ. where P def P'T's is the total number of generated symbols.
The following relationships between CoT and pCoT transformers are clear. Proposition B.1 (CoT and pCoT). We have PCoT[T; T] CoT[T) and PCoT[T, PJ CoT[P].
B.6 PADDED LOOPED TRANSFORMERS
Looped (or universal) transformers use a fixed block of transformer layers that is applied repeatedly to the input string (Dehghani et al., 2019). This increases the depth of the model, enabling more complex reasoning by applying layers multiple times, and does not increase the model size, as the same block is reused for each iteration, thus reducing the memory footprint and computational cost (Bae et al., 2025). We define looped transformers as follows.
Definition B.12 (Looped transformer (PLT)). Let L, e N and let & 1 & l2 & L. Given a depth-L transformer, looped transformer (PLT) computes symbol contextual representations H by
(I.) Computing the initial hidden states H)) for the input string w....W and computing H as with the first 4 layers of the transformer
(2.) Applying the transformer layers 1 1,...,12 T times to the hidden states H to obtain H (12++((a-bi)
(3.) Applying the transformer layers 12 + 1,.... L to the hidden states HLLT((a--1) to obtain the final representations H that are passed to the output layer.
The representations H can then be used in the same way as described in App. B.4.2.
The dynamic computational depth of PLTs endows them with the ability to perform more complex reasoning tasks by iteratively refining their hidden states over multiple timesteps. Importantly, these reasoning steps include both sequential and parallel processing of the input symbols, allowing for both parallel efficiency and depth the reasoning process.
Padded transformers additionally pad the input string with padding (pause) symbols.
Definition B.13 (Padded Transformer). Given P N, a padded transformer T transformer computes the contextual representations H of a string w E E by processing the padded input w D...D
P
(possibly by looping, cf. Def. B. 12), where a & E is designated padding symbol.
Instead being restricted to the contextual representations of the input symbols, a padded transformer determine string membership symbol probabilities based the contextual representations of the P additional padded symbols as well. This additional space can be used to perform more operations and is analogous increasing the circuit width in circuit complexity.
Padding and looping together increase the expressivity of transformers.
Remark 1 (Expressivity of padded looped transformers). The following characterizations of padded looped transformers are known:
(1) Regular languages PLT[log N, 0] (Saunshi al., 2025, Thm. 5.1),
(2) CTT(T] = PLT(T,,) 0]. where the width of the PLT scales linearly with T (Saunshi et al., 2025, Thm. 5.4).
(3) PLT[log N. poly(NN] AC (London & Kanade, 2025, Thm. 4.1),
(4) PLT[log N. poly([)) = TC where, in contrast to our model, the precision scales logarithmically with string length N (London & Kanade (2025, Thm. 4.5), Merrill & Sabharwal (2025a, Thm. 1)).
(5) PLT[log" N. N.po = TC where the precision p scales logarithmically with string length N (Merrill & Sabharwal, 2025a, Thm. 3).
21

---

Published as a conference paper at ICLR 2026
Stochastic padded looped transformers. The looping mechanism naturally accommodates the unmasking steps of MDMs. However, unlike PLT transformers, the MDM unmasking steps can be stochastic-the predictor samples the unmasked symbol from the infilling probability distribution defined by the transformer. To offer more suitable analogue to MDMs, we introduce stochastic PLTTs, which receive Gumbel-distributed noise as additional input to each loop, mimicking the sampling process of MDMs.
Definition B.14 (Stochastic padded looped transformer). A stochastic padded looped transformer is a padded looped transformer in which H (1++((2=41)) augmented by a matrix of Gumbel-distributed noise variables at each time step t E [T'].
The fact that the MLPs transformer layer can implement the argmax operation used for Gumbel sampling (cf. Lem. D.11) allows PLTs to implement the planner and predictor of an MDM as we detail later (cf. Thm. E.1).
Including stochasticity in PLTs is required for natural connection to stochastic models such as MDMs and CoT transformers. While this departs from the standard definitions of PLTTs, it is a natural extension that allows us to capture the stochastic nature of MDMs while retaining the looping structure. Since the Gumbel noise assumed to come from an external source in the sampling procedure of MDMs and CoT transformers, we believe adding it as input to PLTs is natural.
B.7 OUR IDEALIZATION OF MASKED DIFFUSION MODELS
In the following. E dd u {m] where m ş Σ is the mask symbol and En1 def Σ {0, 13, where 0 and 1 are the reject and accept symbols.
Definition B.15 (Planner). A planner is a length-preserving function U: En P((O, 1)). We distinguish two cases:
Case 1: An unrestricted planner is a planner that can choose to resample any symbol.
Case 2: A mask dominated planner is one where, if Wn # m, then (U( = 1, i.e, U never tries to resample already unmasked symbols.
A deterministic planner is
function U: - (0.1)*
Definition B.16 (Symbol Predictor). symbol predictor a Songth-preservingg function S: >i
P(Eo)) 8² A deterministic symbol predictor is a gength-preserving function S: Σn - Eoi Definition B.17 (Masked Diffusion Model). Given a planner U and a symbol predictor S, we call M (U,S) masked diffusion model (MDM).
An MDM with a mask dominated planner corresponds closely to standard MDMs, where at each step, a subset of masked positions is selected for unmasking and then filled in. For example, setting the planner to implement uniformly random unmasking recovers the true reverse process of an MDM. We, however, additionally allow for unrestricted planners, which can also choose to resample already unmasked positions and we take this to be our default setting-wheneee whenever we refer to an MDM, we mean one with an unrestricted planner. While this departs from standard MDM formulations, allows us to sidestep the limitations of the inability of the MDM to "change" its decisions and thus to correct earlier mistakes. This has recently been identified as a key limitation of MDMs and the focus of much recent work improving MDMs (von Rütte et al., 2025; Song et al., 2025, inter alia).
MDMs generate strings by iteratively unmasking and filling symbols over a series of discrete denoising steps. We call this the unmasking process.
Definition B.18 (Unmasking process). Let M be an MDM and T, P e N. Given a string w E Σ+ M generates the string M ((w)
der (T) follows for t E [T]:
y
(25a)
(1) U(w (w (1
(25b)
(1-1)
if if (1) =0 otherwise
(()
(8) yn
for e
(25c)
yn S(w (t1)))
22

---

Published as a conference paper at ICLR 2026
By running the MDM on the empty string and outputting (z) (constraining the generated symbols to Σ S: Σ.1), an MDM generates strings in Σ* and thus defines an LM.
We can also the MDM to define membership test for languages by using the unmasking process to emit reasoning (intermediate) computations and looking at the final symbol of the generated string.
Definition B.19 (Acceptance by an MDM). We say that the diffusion model M with a deterministic U and S accepts a string w E E* if there exist T, P E N such that it holds for yy _M that (T) 1. M. rejects if yp 0.
(T)
Up
Transformer MDMs. We focus on MDMs where both the planner and predictor are implemented by transformers.
Definition B.20 (Transformer planner and predictor). A transformer planner is planner Σn" P((0, 13) where the logits over {0, 1} are computed by a transformer.
A transformer predictor is predicior S: En² Eo1 * where the logits over Eo1 at each position are computed by a transformer.
C A DISCUSSION OF THE THEORETICAL MODEL
Our formalization of MDMs, centered around the planner and predictor, is motivated by the need to analyze their expressivity. While this definition intentionally departs from the exact analytical reverse process, it remains well-grounded in both empirical practice and theoretical considerations. In the following, we justify our modeling choices and clarify their connections practical implementations.
C.I THE PLANNER AS PRINCIPLED DEPARTURE FROM UNIFORM UNMASKING
At an intuitive level, our formalism distills the essential structure of practical MDMs: A process that iteratively unmasks and fills in symbols. In our idealization, this process is governed by model that chooses which symbols to unmask and when. This is motivated by practical considerations- although the analytical reverse process of the MDM forward masking process would unmask symbols uniformly at random, this is not how practical MDMs operate, since they empirically benefit from strategic, context-aware unmasking (Ghazvininejad al., 2019; Peng al., 2025; Zheng et al., 2024; Liu et al., 2025a; Kim et al., 2025; Ben-Hamu et al., 2025). Forcing a trained MDM to follow uniform unmasking schedule thus suboptimal prevents the model from decoding an order that makes tasks easier to solve (Kim et al., 2025) and can lead to uncontrolled error propagation (Ghazvininejad et al., 2019). The dedicated planner captures many empirically successful planned unmasking strategies that consistently outperform random unmasking such as:
Confidence-based unmasking that unmask based on the model's prediction confidence.
Diffieulty-based scheduling that masks informative symbols longer so they are generated last with maximum context (He et al., 2023).
Structured schedules such as blockwise- auttrrereeattooeeesssvve unmasking (Nie et al., 2025).
Learned planners that use a separate trained model guide unmasking decisions (Peng et al., 2025).
Confidence thresholding that unmasks symbols whose confidence lies above a theory- suggested threshold (Wu et al., 2025).
Theoretically, uniform unmasking is only optimal if the symbol predictor is perfect and unfactorized, which not the case in practice (Peng al., 2025). Furthermore, under a factorized backward process, uniform unmasking is computationally inefficient even with perfect predictor. It requires at least a linear number of denoising steps in the string length to capture dependencies in even simple formal languages, and the KL divergence to the true data distribution converges slowly (Feng et al., 2025; Li & Cai, 2025). This lower bound negates any potential speed benefit over autoregressive models. A planner is therefore necessary component for efficient, accurate generation, as it provides an educated choice of which symbols to unmask and generate in parallel, mitigating the weakness of the independence assumption. Frameworks such that by Zheng al. (2024) and augmented MDM
23

---

Published as a conference paper at ICLR 2026
evidence lower bounds that incorporate explicit planner terms (Peng al., 2025; Liu et al., 2025a) demonstrate that a planner can be a principled, optimizable component of the generative process.
To fürther justify choice of modeling the planner separate component, show that any MDM that can be implemented as a combination of a planner and a predictor can in fact be implemented by single transformer that unmasks symbols based on their confidence- top-k decoding. This means that all our results apply to the popular model unmasking symbols based on their confidence (Ghazvininejad et al., 2019; Peng et al., 2025; Zheng et al., 2024; Liu et al., 2025a; Kim al., 2025; Ben-Hamu et al., 2025).
Definition C.1 (top-k k unmasking). Let T be a transformer and k E N. The top-k unmasking process T is defined by the planner of the form
Uly)n = {
isn top--k(((()))
for n E [M],
(26)
otherwise
where Lim" with N = |y| and (op-k(T(y)) selects the k positions in [N] with the largest maximal logits in T Tyy). The predictor is defined as
S(y) = pt(w (w y) for n E [N].
(27)
where (+( y) is the infilling probability distribution of the n²hh token defined by T.
Theorem C.1 (Combining the planner and predictor). Let M = (U,S) be a masked diffusion model with planner U and symbol predictor S. Then, there exists transformer TT such that it holds for any y Em" with N = yyl and n E [N] that
n. E (etoo-k(T(()) = U(y)n -1
(28a)
p'(w y =Sy)),
(28b)
where (+( y) denotes the infilling probubility distribution of the nh token defined by T.
Proof. The construction of T combines the planner U and predictor S into single model that predicts the next symbol based on the planner's decision and the predictor's distribution. In particular, T runs U and S in parallel. The planner's s output decision U Ugy),, of 0 can be made based on implementing the argmax function with an MLP (cf. Lem. D.1 if the planner is deterministic or by inserting the noise from the Gumbel-max sampling (ef. Def. B.7) if the planner is probabilistic. T can then use this information to down-weight the logits of that are chosen not to be unmasked by the predictor by subtracting Bp from the logits of the symbols that are not chosen by the planner. This ensures that only the symbols that are chosen by the planner can be predicted by the predictor. The predictor S can in parallel compute its residual stream and the accompanying logits before combining them with the planner's decisions. The subtraction of the Bp from the logits of the symbols that are not chosen by the planner ensures that top-k will only select the symbols that are chosen by the planner and the simulation of the predictor ensures that the infilling distributions match.
C.2 EDITING AND NON-EDITING MDMS.
The choice to allow the MDM to resample already unmasked symbols also departs from the analytical reverse process of MDMs, which only unmask masked symbols. This is, however, a principled choice that allows the MDM to correct earlier mistakes and is supported by empirical evidence that resampling already unmasked symbols can improve generation quality (von Rütte et al., 2025). In practice, this choice enables more concise connections to PLTs and pCoT transformers. Moreover, all results in this work can easily be adapted to MDMs with mask dominated planners that do not resample already unmasked symbols. This is justified by the following theorem that shows that any MDM with an unrestricted planner can be simulated by MDM with mask dominated planner by increasing the output space by a factor of to account for the inability to resample. In the following, refer to MDMs with mask dominated planners simple MDMs (sMDMs).
Theorem C.2 (sMDMs can simulate MDMs).
[D P] s aMDM TP..
(29)
24

---

Published as a conference paper at ICLR 2026
Proof. At high level, the sMDM's planner selects the decoding space by selecting the next P positions to unmask, and the predictor (1) reads the string generated so far, (2) simulates a step of the MDM transformer the string, and (3) writes the updated values into portion of the padding space.
More precisely, can implement the sMDM transformer follows:
(1) The sMDM transformer uses TP masked symbols to store the generated symbols at each of the T unmasking steps of the MDM transformer.
(2) The planner is implemented the transformer from Lem. D.9 that acts independently of the input string and uses positional encodings to select the next P positions to unmask.
(3) The predictor is implemented as transformer that predicts the values of the P masked symbols based on the current input string. reads the values from the padding space by attending to the last P unmasked positions in the padding space analogous to the dump- decode-read mechanism from Lem. E.1. The only difference is that the predictor has to attend to the last unmasked block of decoded values. This can be done with two additional transformer layers by (a) ignoring masked symbols and (b) ignoring positions with identical positional encodings their right.
D THEORETICAL GADGETS
This section contains various theoretical gadgets that are used in the proofs of the main results. Not all of these are novel; some are modified restatements from their original sources.
In the following. N e always refers the length of the original input string. the string is additionally padded, the number of padding symbols is denoted by P, meaning that the entire input the transformer of length N P.
D.1 POSITIONAL ENCODINGS
Uniquely identifying positions in a string requires the "volume" of the representation space to grow with the string length. the case of snite-precision logarithmic-width transformers, this is achieved with positional encodings that encode the binary representation of the position in the string. The following lemma follows from the definition of fixed-point arithmetic, and the rounding and thresholding applied therein.
Lemma D.1. Let E F for some p N such that > log 2(p + 1). Then, it holds that
exp(x) 13, exp(-2) = 0.
(30a) (30b)
Lemmata D.2 and D.3 readily follow from Lem. D.1. Lemma D.2 (Li et al. (2024, Lemmata E.1 and E.2)). For Bg from App. B.3, it holds that
exp( B7) Br, exp(-B7) = 0.
(31a)
(31b)
Lemma D.3 (Li et al. (2024, Lem. E.3)). For N, N. n [N], define the vectors on 2 N]
and kn 2log N] as follows:
On del B3 (B+ 1 mi)
(32a)
k, del B+(n') 7 (-1 M))
(32b)
Then, it holds that
0
if n n'
q k. kn
(33)
Br
otherwise.
25

---

Published as a conference paper at ICLR 2026
Thus,
[1
ifn= = rl
exp(a,.k.) knn)
(34)
otherwise.
The following slight generalization of Lem. D.3 is also easy to show.
Lemma D.4. For N e N. n e [N], define the vectors 9n E TR N1 and kn R2 as follows:
qn Be/m- (n) 1 flo N1)
(35a)
kw
det B (n') (- flg v7).
(35b)
Then, it holds that
0 in n' otherwise
T kw
(36)
where x & -2Bm/m.
Our constructions heavily rely on specific positional encodings. We assume that this positional information comes from outside source and is not computed by the transformer model directly. We note that this is in contrast to some existing work with causally masked transformers where the positional encodings are inferred by the model itself (Yang et al., 2024; Li & Cotterell, 2025; Jerad et al., 2025). This matters for multiple reasons. First, including positional information from an external source allows us decouple the computation of positional information from the computations performed by the transformer model. Furthermore, it facilitates providing the model with structured information that it would not able to compute on its own. While this could be abused to give the model unrealistic computational power, we assume that the positional information is easily computable and thus realistic.
In that vein, it is interesting to consider what the minimal amount of positional information is that the model has to be provided with for it to be able to construct the useful positional encodings. This is described by the following lemma. At a high level, it says that our positional encodings require the binary encodings of the relevant numbers, along with any modular and division operations performed on them. Addition, thresholding, and multiplication by power of two, in contrast, be performed by the MLPs in the transformer model.
Lemma D.5 (Arithmetic operations performed by MLPs). Let m, n E N. Then, given the binary encodings of the numbers, ((m),((n) there exist MLPs that can compute the following operations:
(a) computing the signed binary encoding B (m)).
(b) computing the sum B(m) + B(n) and the difference B(m) B(n),
(c) computing B m2) for ke N.
(d) computing the indicator function 11 {m 3 0).
(e) computing the indicator function 1 {m = 0}, and
( computing the positive-part function [m]
Proof.
(a) The transformation B+(m) def 28(m) 1 m| is an affine function that can be implemented by the affine part of the MLP followed by the identity function, which can be implemented by an MLP as well.
(b) It is easy to implement AND and NOT gates by an MLP. This suffices to implement any AC (and thus addition and subtraction) circuit.
(c) The transformation B(m) - B(2 m) can be performed by shifting the binary representation of B(m) the left by l positions, which can be implemented by linear transformation.
26

---

Published as a conference paper at ICLR 2026
(d) The indicator function 1 {m > 0} can be computed by checking the sign bit of the signed binary representation 8 [m), which can be implemented by an MLP.
(e) The indicator function {m 0} can be computed by checking if all bits of the binary representation ((m) are zero, which also be implemented by MLP.
( Computing [m]+ can be done by first computing {m 0} with (d) and then conditionally outputting m or O based on the result, which can be implemented by an MLP similar to Lem. D.12.
Simplification of positional encodings. Lem. D.5 leads conclude that the relatively compli- cated positional encodings used in the following proofs can be thought of as simple transformations of the "basic" information captured by
(n2)..
((N),
. B(n mod m) for some relevant m e N, and B(/m)) for some relevant m N.
This makes the positional encodings in our constructions streamlined and easily computable. While somewhat ntn-standard, we note that positional encodings based on both the symbol position n and string length N are common in theoretical literature (Chiang & Cholak, 2022).
Despite being simple to compute, these positional encodings are powerful enough to allow the transformer to uniquely identify positions in the string and to perform useful computations based on them. In a sense, the inclusion of this information is also necessary, as the operations such as division and modular thus cannot be performed by finieeprrecision transformers (Li et al., 2024). We note, however, that more expressive transformers such those with logarithmic precision could possibly implement the required functions to compute the information in B(n). B mod m.) and B(n/m)) from n and N directly since, unlike fxee-precision transformers, they are not constrained AC operations (Li et al., 2024).21 21 The simplicity and uniformity of these encodings lies in contrast to more complex (non-uniform) positional encodings that directly scrialize the circuits be simulated when analyzing expressivity lower bounds (Li et al., 2024: Saunshi et al., 2025; London & Kanade, 2025).
the computation of the binary encodings-lie outside of AC and
D.2 USEFUL ATTENTION PATTERNS
The following lemmata describe how transformer layer can either ignore or exclusively focus on specific positions in the input string.
Lemma D.6 (ggnoring Marked Positions with Transformer). Let N,D [N], and let H E XDD be a matrix representing the residual stream such that
[e] Hn.: < < E N.
(37)
Here, the notation [o] E Hn.: means that the vector Hn: contains the one-hot encoding of the symbol at position n. Further, let G HINTY (N where HINJN, denotes the projection of the matrix H onto the rows not in N. Finally, let T be transformer layer. Then, there exists a logarithmic-w'i
transformer layer T' such that holds for G' det T(G) R NNNN))xD
and H' def ('H) NxD that
G' = =HHNNA,.
(38)
Informally, Lem. D.6 states that transformer layer can ignore positions containing one-hot encodings of specific "marker" symbols, such as additional symbols not in the original alphabet. Here, ignoring means that the content of the positions with the marker symbols does not affect the output of the transformer layer at other positions.
We also note that the modular information in our encodings resembles the periodic nature of original sinusoidal positional encodings used by the transformer architecture (Vaswani et al., 2017). Moreover, the modular nature of such positional encodings has been analyzed by theoretical work before and is known to increase the expressivity of certain idcalizations of transformers (I.i Cotterell, 2025; Jerad al., 2025).
27

---

Published as a conference paper at ICLR 2026
Proof. Notice that, since H and G match all positions not in NN, ignoring the positions in .V' (marked by о) by T' will ensure that the outputs the two layers T and T' are identical on the positions not in .N. We now construct transformer layer that ignores the contributions of rows marked by [o]. To do so, we modify each attention head of T such that the head computes its attention scores with queries and keys of the form
In def
(-
By [n]
On
(39a)
B3 [=]
knn
Kyy
(39b)
[[w>]]
where On and k are the original head's query and key vectors of T at position n and n', respectively, and [ww]] is the one-hot encoding of the symbol at position n'. We can then compute the dot product of the two vectors as
In kn By 1 {w. = u) - B5 {wn, = u]
(40)
k Thus, if the symbol at position n' is c, the attention score is ke and the head behaves as did in T. If the symbol at position n' is u, the last two components of the vectors yn and kn ensure that the exponentiated value of the attention score becomes 0, thus not contributing to the attention weights. T' can thus simulate T on the rest of the positions.
Lemma D.7 (Focusing on Marked Positions with a Transformer). Let N, N, [N],
[N]. N def (r) = [N]. and let H R be matrix representing the residual stream
such that
B(R(n)) Hn: for all E [N]
(41)
Here, the notation B(R(n)) E Hn,; means that the vector Hn; contains the signed binary encoding (ef. $2) of R(n). Further, let del HN.: E R MDD,, where HN. denotes the projection of the matrix H onto the rows in N. Finally, let be transformer layer. Then, there exists logarithmic-widle transformer layer T' such that it holds for G' del T(G)) E RW and H' del (H) E N that
G'=H''.-
(42)
Informally, Lem. D.7 states that a transformer layer can focus on positions containing signed binary encodings of number computed as a function of the position while ignoring the rest of the positions.
Proof. The idea of the construction of r' is similar that of Lem. D.6, but instead of ignoring the positions in N, we want the transformer layer to focus on them while ignoring the rest of the positions. This can be done by including B(R(n)) in the positional encodings of the attention heads and then using the key and query vectors of the form
qn
d',
Br (B
Dog N7) Dog Ni)
(43a)
Be/22 (B)
kw B B= (- Aoog 1oggN)) .n) (=((m))) (- flog m1)
(43b)
where qn and k, are the original head's query and key vectors of T at position n and n', respectively, and Bg is the maximal representable number in the sxed-point arithmetic (which might depend on the string length N). We can then compute the dot product of the two vectors as
g n W n = q kw + Bb/2 (B* (r)
Dog N1) T(B (R(n')) (- flog N1)
(44a)
Be/2 (B+ (r) Nog v7) (B* (R(n'))( (1 p-1 v7))
d
28

---

Published as a conference paper at ICLR 2026
Note that Eq. (44a) uses fixed- exed-point arithmetic. We compute the inner product in Eq. (44a) by analyzing individual cases:
1. Case 1: R(n') o r.
All intermediate computations of Eq. (44a) are thresholded at min ( Bg, q, k KT,k,, + Br/2)) - In partieular, by Lem. D.4, the value after adding the first term G is at most min( Br, k + Br/2) 2 & BB Bp O. After adding the second term G, the value is at most BB. resulting in a exponentiated attention score, required.
2. Case 2: R(n') = r. We analyze three sub-cases based on the value q, kny.
1. Sub-case 2a: q, k. log 2(p 1). All intermediate computations in Eq. (44a) are bounded by log 2(p + 1) + Br/2 in absolute value, so they fall within the range of Fp-- Moreover, addition of R2r/2 can be exactly represented in Fp. This makes addition in Eq. (44a) associative and commutative. By Lem. D.3, the terms G' in Eq. (44a) are 0, meaning that the final attention score equals q, k....
2. Sub-case 2b: q, kn > log 2(p 1). In this case, the intermediate computations of Eq. (44a) are either exact or thresholded Bz. In both cases, the exponent of the resulting attention score is BF by Lem. D.I. preserving the attention score.
Sub-case 2c: q, kn & log 2(p + 1). In this case, all intermediate computations are representable in F, analogously to the case 2a. The attention score is therefore preserved.
Taken together, this means that the attention scores between positions and n' of T' are identical to those of T on the positions N,, while the attention scores on the rest of the positions are O. This completes the proof.
Lemma D.8 (Detecting a symbol occurrence). Let w E E and w E E. Then, there exists a single- layer unmasked fixed-pree precision logarithmic-widtt transformer T such that, on input w. an entry of its final residual stream contains the entry (w E w)
Proof sketch. Note that T cannot use the commonly exact uniform attention over all symbols to detect 1 {w w) due fixed precision. Nevertheless, rounded uniform attention suffices. By attending to all symbols in the string with weight I, the denominator of the attention scores is at most Bp. Using one-hot encodings of symbols wn, the attention values U,,, it is easy contextual representation at the final position will have a positive value at the entry corresponding to if and only if w E w, since e/B, > for any e > 1. This condition can be checked by the MLP applied after the attention aggregation operation.
that the final
Lemma D.9. Let w E Σ* be string of length N and PT the number of padding symbols where P.T =Poly(NN. There exists a fixed-rrecision and logarithmic-width transformer U: En" (0,1) that, given ur and the current partially masked string ((8), selects the next P positions to unmask by outputting for the next P positions to unmask and 0 for all other positions.
Proof. The idea of the construction for U (l) output 0 for any position that does not contain the padding symbol u, and (2) output 1 for the first P positions that contain the padding symbol Step (1) can implemented by checking whether the symbol at the current position is a and outputting otherwise. Step (2) can be implemented by attending to position P positions back and outputting the symbol at that position * a and 0 otherwise. These steps can be performed by two attention heads in single transformer layer using the positional encodings
B B+(mm) (B=(n - P)) ))))
PE(n, .) der
E {0, 1) O N)
(45)
29

---

Published as a conference paper at ICLR 2026
Lemma D.10 (Converting binary representation into positional encoding). Let N E N and [N]. Then, there exists an unmasked fixed exed-precision logarthmic-width padded looped transformer T such that, input & B(n), after [log N| iterations, the residual stream position [log N + 1 contains the value B(n)
Proof sketch. The transformer T has to convert the binary representation B(n) of n spread across [log N| positions in the input string into single (log - binary vector in the residual stream. This done as follows:
1. In the first layer, each symbol e {0. 1] checks if it is immediately preceded by the & symbol, which denotes the beginning of the pointer the string. it is, Wn stores e and di u, in designated parts of its residual stream. Here, e1 is the first unit vector of IR [log N1.
2. In the subsequent layers e f2..... [log N1,, each symbol why checks if the entry et-1 has already been written to the designated space of the previous symbol's residual stream. If it def
has, Why copies and shifts et-1 into ej, and stores e; and di d + w.er er in designated parts of its residual stream.
After flog M] layers, the residual stream position flog N| + 1 thus contains B(n).
D.3 NEURAL NETWORK CONSTRUCTIONS
Lemma D.11 (Saunshi et al. (2025, Lem. B.6)), For every D E N and precision E N, there exists ReL.Uacctivated MLP f: RDD {0, 1)2 such that for any FD. if there is e [D]. such that Fd maxje(D]:(4) Zj, then (xx Ca. the dth unit vector.
Proof. The proof is based on the construction of 3-layer ReLU network that computes the argmax of a vector a FDD The first layer computes the differences between each pair of elements in æ. The second layer computes the maximum of these differences. The third layer then checks if the maximum difference is greater than zero, indicating that there is unique maximum element in æ.
More concretely, define
def 2D ReLU 2 Σ ReLUUZr Ial Id
(46)
3Fd
which can be computed by 3-layer ReLU network. We have that Jd if and only if ad > maxj Tj, or, equivalently, if and only if I max od Iy 2 2 Indeed if x4 maxj 2j > 2 we have that
ga = 28. ReLU p Σ
ReLU(r, - ma) 1.
(47)
jzd
In contrast, for d' # d, we have that xx Ed < P. and thus
g8 = 2
2 Σ
ReLU(Iz xar) -xa)) < 28 ReLUR2 RReUU 2x)) = 0. (48)
1td
Lemma D.12. Let 10. and ea 10,1)" be the th unit vector Then, there exists
Reativvcte MLP f: (0, D+D
(0. 13 such that
f(x, ea) = x. ea = Fd-
(49)
Proof. We have that
Fy 1 (ReLUU( -1-ea))
(50)
where 1 is the all-ones vector of length D. This can be implemented by ReI U-attivvee MI.P.
30

---

Published as a conference paper at ICLR 2026
D.4 MASKED AND UNMASKED TRANSFORMERS
Lemma D.13 (Unmasked to causally masked; Merrill & Sabharwal (2025a, Lem. 1)). Let T be unmasked fixed- precciiin logarithmic-wide transformer with layers. Then, there exists a fixed- precision logarithmic-wice causally maskeed transformer T' with L layers such that for any input string w & E* of length padded with L(N -1) padding symbols, the representations H H (L-1)N-LN
computed by T on wo equal the final representations H computed by T.
Proof. We adapt the proof of Merrill & Sabharwal (2025a, Lem. 1) our setting. The idea is for T' to unroll the computation of (L) into sequence of "blocks" of padding, each of width N. Each block will attend to the previous represenpnnnn the values in the preceding layer-and will thus be able to see all symbols despite causal masking. To do so, T' uses additional positional encodings of the form
B (Im) (B 1) (1))
PE(n, N) def
E {0, 1} 2fo M1
(51)
Here, L, - |//2|+ + represents the layer that each padding position belongs to. To construct T', we then modify each original head from T with Lem. D.7 to ensure that the attention is focused on the correct padding positions, where the attention head computes the same function as the one in T.
logarithmic- Lemma D.14 (Causally masked to unmasked). Let be an L-layer logaritlmic-widdh unmasked width causally-masked transformer. Then, there exists transformer T' with 21, + layers such that for any input string u Σ.* of length N padded with (N-1)N:22 computed by T' on w equal the final
(N - I padding symbols, the representations HML
representations (L) computed by T
Proof. The idea is for T' to unroll the computation of (L) into a sequence of "blocks" of padding, each of width N. Each block will compute the representation of one of the symbols in the string. To do so, T' uses additional positional encodings of the form
B (bn) B (+((r)
PE(n, N) der
(n N)
E f00, 1) Ollog N)
(52)
1 (bn 3 rn
1 (bn = rnl
Here, by def [ + represents the block that position n falls into and ru def (n mod N) + 1 represents the position within that layer.
T' then processes a string w e * of length N padded with 22 padding symbols follows.
(1) T' uses an additional "copy" layer to copy the input symbols from the first N positions to the residual stream for access later layers. In particular, each position n [ is assigned the value of the input symbol at position Tn. This can be done by the symbol at position n
attending the symbol position r. in the input string, i.e., H.!" (1)
H if bn Tas
which can be ensured by attending only to positions with non-zero entry (b,, 3 (rr,)) in the positional encoding. The latter condition ensures that the 5th block contains only symbols Was wg attending to the entire block is then equivalent to Wh attending to the
(1) (1) (1) computed
string with causal attention. Concretely, the attention scores n.," qn
20hhi simulation is somewhat inefficient in that only subset of the N positions used each of the N blocks (specifically, n positions in the th block). While this could he made more efficient with a more sophisticated construction, the asymptotic complexity would remain quadratic in N.
By additional, that these positional encodings are appended the ones used by T.
31

---

Published as a conference paper at ICLR 2026
with query and key vectors
(r+)))) 1log.1) -1
q def Br
(53a)
( (-11110 1n s N)
( def
(53b)
(2) Once the symbols have been copied to the appropriate positions, T' can simulate one layer of T by augmenting its heads with Lem. D.7 ensure that the computations at position n are restricted to the block b, which, as described above, contains information about Wssh,," This ensures that the attention scores are non-zero only for (i) positions n in the same block bn as n', and (ii) positions that should be unmasked in the current block.
(3) After simulating the layer from T in step (2), the contextual representation in the b, block contain the information about w ws, computed based on the symbols Wgb. In particular, the representations of the symbols Web, in the b, block contain information not obtained by causal masking since they attend to all the symbols Wgb, in the b,, block. To amend that, an additional transformer layer discards the information about symbols wes, in the bn th block by overwriting the representation of Wa in the h, th block with the representation of wn in the nh block for n' bn- This is done by attending to the positions n' in which the block index bn matches the position Tn's i.c., with the query and key vectors
B L (bw.) (B
4n
BF
-1
1og N1
(54a)
B (Pm)) (- (-1 flon [lon m1) 1 (bn rn)
k
(54b)
which ensures that n uniquely attends to the symbols was. the b, th block.
E PROOFS
This section contains the proofs of novel theoretical results. Many constructions in the proofs rely on the theoretical gadgets introduced in App. D.
Theorem 2.1. If Assumptions 2 and 2.2 hold for an LM p. p cannot compute non-AC" functions. 25,26
Proof. This a consequence of the established result that fixed-depth transformers can only compute AC functions (Li et al., 2024; Saunshi al., 2025; London & Kanade, 2025, inter alia). Note that this is similar to the proof in Liu (2025); Liu et al. (2025b) but is simpler due to the focus on discrete predictions directly rather than the continuous modeling of the diffusion process in the latent space.
E. PROOFS OF RESULTS IN $3.1
Theorem E.1 (PLTs can simulate MDMs).
MDM[T, PJ PLT[T,
(55)
Proof. We can simulate an MDM transformer with a PLT transformer by "composing" the planner and predictor into single transformer model. This model
Thh augmented attention mechanism additionally downweights positions with 1 (b,, T rw) 1, which be done by subtracting B: from the attention score. 25That is, can only implement LMs whose next-symbol logits can he computed by AC circuits (Liu, 2025). An analogous version of the theorem applies transformers TC".
32

---

Published as a conference paper at ICLR 2026
(1) computes the planner's contextual representations while passing the input symbol in the residual stream,
(2) computes the planner's decision at each position by simulating the argmax of the planner's output logits in Lem. D.11,
computes the predictor's contextual representations based on the planner's decision, and
(4) predicts the next symbol at each position by simulating the argmax of the predictor's output logits as in Lem. D.11.
Lemma E.1. Let T be fixed-precision and polynomial-width transformer and H 1) the residual stream of ' after layers on some (possibly padded) input string w E Σ* Then, there exist fixed-preciste
and polynomial-wite witth transformer layers Toump and Tread with such that Toump H) {0, 1) Ollog NyxD and
Tread (Dec (Tuun ( .N: H
(56)
for some output matrix E E R2xD
Proof. The idea of the construction of the layers Touno and Tread is to store the contents of the residual stream in the padding space and then read it out the next iteration. To do that, we allocate N D symbols of additional (masked) padding space in the decoded string. Each of the length-/) blocks corresponds position in the input string and each symbol in the block to dimension in the hidden representation. The layers thus have to be augmented with positional encodings that will allow for the identification of the position in the residual stream and the dimension in the hidden representation. This will suffice for Tdunp to write out the contents of the residual stream into the padding space and for the reading layer Tread to read it out again.
More precisely, Taunp and Tread use the following positional encodings:
B (n) B (bb))
PE(n, der
E {0, 13 Olog
Oloog
(57)
[dm]
1 (n & N
to the input of Touro- In particular, for a masked padding symbol at position n, bn del [n N1,/D and d, de [n .N,, mod D correspond to the position in the residual stream and the dimension in the hidden representation that the position will store, respectively. Taup can then be implemented as follows:
(1) Using B (bb,) as the query at masked position n and (=n')) as the key at position n' < N, Tounp individually identify the corresponding position B (b,,) in the residual stream.
(2) Feeding (g.) 1) together with [d,]] as the value at the masked position into the MLP, Touro can write the value of the dimension d, of the residual stream at position 8 (b,,) into the padding space by Lem. D.12.
is then easy to construct the output matrix E as part of the decoding step Dec such that Dec(Taimp (H) decodes the contents of the residual stream. Tread can then be implemented as follows:
(1) Include transformer layer that ignores the attention mechanism and reads the input string and the decoded residual stream values, passes them through the residual connection, and encodes the values into the embedding space with the position-wise MLP. In particular, combining the information in [d,] with the information in the input symbols, the MLP convert the one-hot encoding of the dimension d, into the vector ha, ed,, where ha. corresponds to the value of the appropriate dimension the residual stream at the appropriate position.
33

---

Published as a conference paper at ICLR 2026
(2) Using (n) the query at the input string position & N and ([[n''NNN//)) as the key, Tread can identify all the padding positions that contain the values of the individual dimensions of the residual stream at position n. The positional encodings ensure that the attention scores satisfy (ef. Lem. D.2)
0
if =n=
On kin'
(-Bp otherwise.
(58)
Exponentiating and normalizing the attention scores, the attention mechanism will then only attend to the positions n' that correspond to the position in the residual stream. More concretely, the attention mechanism computes
exp( In kin!)
1
(59)
En (.,
End" exp(q,,,,") min D, Bp)
Bg
for all ní that correspond to the position n in the residual stream and 8n.n' 0 otherwise. Summing over the values at these positions (which project the constructed vectors ha, ed.,) Tread can then reconstruct the value of the residual stream position (normalized by min D, Bz)).
(3) Use the position MLP convert the normalized value of the residual stream at position n into the vector hdd Cd., This can be done by a ReLUvactivaeed MLP that maps (-o0,) 0] to 0 and By o0) to position-wise
Theorem F.2 (MDMs can simulate PLTTs).
PLT MDM[T, (N + P)D].
(60)
Proof. The proof uses Lem. E.1 to simulate single iteration of the PLT transformer loop with single denoising step in the MDM transformer. In particular, by adding (N + P)D padding space, the MDM has enough room to store the residual stream values, allowing it to decode the values the next iteration. At high level, the MDM's planner deterministically selects the entire padding space to unmask or resample, and the predictor (1) reads the input string or the currently stored residual stream values, (2) simulates a single pass of the PLT transformer on the input string and the current residual stream values and thus computes the updated value of the residual stream, and (3) uses Lem. E.1 to write the updated values into the padding space.
More precisely, we can implement the MDM transformer as follows:
(1) The MDM transformer uses (N P)D masked symbols store the residual stream values.
(2) The planner deterministically outputs for positions NN and 0 for positions N.
(3) The predictor predicts the values of the (N + P) D symbols based on the current input string and the residual stream values. It reads the values from the residual stream by making the first positions attend to the (N + P) D padding positions analogous to the dump-decodee-rad mechanism from Lem. E.1.
By treating input symbols Σ separately to the decoded values of the residual stream (which enables the MDM transformer to simulate both the initial as well as the looping blocks of the PLT transformer). the MDM transformer can thus simulate the PLT transformer with TPD padding symbols.
Theorem 3.2. Regular languages are in MDM[log N, N].
Proof. The proof adapts the construction from the proof of Saunshi et al. (2025, Thm. 5.1) to the MDM setting. The key difference lies in adapting the positional encodings allow for the padded tokens to attend to appropriate positions in the residual stream. In particular, the first [N/2] positions of the padding space will attend to the N input symbols while the remaining positions in the padding
34

---

Published as a conference paper at ICLR 2026
space will attend to the other padding positions of the residual stream in later unmasking steps. Concretely, defining ñ def [n N4 the positional encodings take the form
B
B (
B ([2n N14)
B ([2n - N - 11+)
PE(n,, N) #
E {0, 1) (logg)
(61)
B ([2n - N)+)
B (22 - N- - 1++)
{n N
(ñ N/2)
This information gives padding tokens enough information either attend the input symbols (1 (ñ 3 N/2} 1) or to the residual stream values, enabling the simulation of the algorithm from Saunshi al. (2025, Thm. 5.1).
E.2 PROOFS OF RESULTS IN $3.2
Theorem 3.3 (MDMs can simulate pCoT transformers).
pCoT|T, PJ MDM[T, (N + P)
(6)
Proof. P The idea of the simulation is straightforward: The planner first determines the next P' symmoll to unmask. Then, the predictor determines the symbols at those positions by simulating the behavior of the pCoT transformer. This is trivial the MDM is causally masked like the pCoT transformer. However, if the MDM is not causally masked, the planner must take additional steps to ensure that the prediction equivalent to the pCoT transformer.
Concretely, the MDM simulates the pCoT transformer the input string of length N as follows:
1. We first note that the pCoT transformer predicts the next P' symbols at every timestep t based on the input string (t-+()
-::: rather than WgN+(t- This is because,
(T-()P
by Lem. D.6, the PCoT transformer can ignore all symbols containing the padding symbol and thus produce equivalent predictions at every step L. This will help us make use of the same padding space every step of the simulation.
2. We assume that the final output of the MDM will be stored in the first P positions of the padding space. It will be filled in T generation steps, where at each step / [T]. block of P' symbols will be predicted. In particular, by Lem. D.9, the planner can select the next P' positions unmask at time by including the values B ([[n N) //rl) and 8 (II- 1) in the positional encodings.
3. The predictor then uses an initial layer copy the input string (t,N((1-1)P)) ويي into (T-O)
the residual stream of the first N + P positions of the padding space.
4. The predictor then uses the (N + P)² padding positions to predict the next P' symbols predicted by the PCoT transformer. These are written to the positions chosen to be unmasked by the planner.
Theorem 3.4 (pCoT transformers can simulate MDMs).
MDM(T, P] PCoT(T, LT(P + N)),
(7)
where I is the number of layers the transformer implementing the MDM.
35

---

Published as a conference paper at ICLR 2026
Proof. For simplicity, we assume that the input to the pCoT transformer is padded by P symbols. Intuitively, the pCoT transformer simulates an L-layer MDM transformer on the input string w of length N by simulating each MDM generation step with additional padding account for causal masking. Whereas the MDM transformer "overwrites" its previous input and bases its predictions at time step the current version of the unmasked input, the pCoT transformer bases its predictions of the P symbols on the entire string of (t -): P symbols generated so far. For correct simulation, the pCoT transformer therefore has ignore all the symbols not generated at the previous time step, which will be ensured by appropriate positional encodings. The pCoT transformer can then predict the next N + symbols based on the current input string and the previously predicted symbols, simulating the behavior of the MDM transformer on that input. However, to predict N + P symbols, the pCoT transformer uses P def L(N + P) padding space at each step account for the unmasked nature of the MDM transformer (cf. Lem. D.14).
More concretely, the simulation happens as follows.
(I) The pCoT transformer uses additional positional encodings with the information about 1/1], [in-N] [n-Nii/r]], [n NJ+ mod P' - and [n NN. mod P. These positional encodings allow the pCoT transformer to identify (1) the previous block of P' predicted symbols, (2) the last P symbols within that block (which is where the actual predictions of the previous step will be stored), and (3) the current position in the block with Lem. D.7.
(2) The PCoT transformer first uses an initial layer to copy the output of the previous generation step (captured in the previous N + P positions) into the next N P positions of the padding space (this is where we use the assumption that the input to the pCoT transformer is padded if that is not the case, more complicated construction could specifically handle the initial step of the generation where only the initial input string would be copied).
(3) The PCoT transformer can then predict the next P symbols by simulating the behavior of the composed MDM planner and predictor as Thm. E.I.
36


Reviews:
[{"review_id": "2O4UPCJTlo", "reviewer": "Reviewer_nitu", "summary": "This paper provides a formal analysis of the reasoning and computational capabilities of MDM. Under a finite-precision, logarithmic-width transformer setting, the authors prove that MDMs are theoretically equivalent to PLTs and can simulate CoT reasoning. They further show that MDMs are provably more efficient only for parallelizable problems (e.g., regular languages), where parallel denoising enables faster reasoning, while for inherently sequential tasks (e.g., P-complete problems) MDMs offer no efficiency gain and may even be less practical due to architectural overhead.", "questions": "1. The paper makes strong assumptions about positional encodings, requiring them to include arithmetic information such as division and modulo. Do widely used schemes like RoPE [1] satisfy these assumptions?\n\n2. The authors argue that for P-complete problems, MDMs cannot benefit from parallelism and that the absence of KV-cache makes autoregressive models preferable. Would this conclusion still hold if we consider recent MDM variants that incorporate KV-cache [2]?\n\n[1] Su et al. RoFormer: Enhanced Transformer with Rotary Position Embedding.\n\n[2] Wu et al. Fast-dLLM: Training-free Acceleration of Diffusion LLM by Enabling KV Cache and Parallel Decoding.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper offers a novel and rigorous theoretical framework for analyzing the reasoning capability of masked diffusion models, a topic that has been largely unexplored.\n\n2. It provides clear conceptual connections between MDMs, chain-of-thought transformers, and padded looped transformers, helping to unify different reasoning paradigms under one formulation.\n\n3. The analysis yields meaningful theoretical insights into when MDMs can achieve efficiency gains through parallelism, offering guidance for future research on diffusion-based reasoning models.", "weaknesses": "1. The theoretical framework relies on strong assumptions about positional encodings, which are constructed to include arithmetic information (e.g., division and modulo) that real transformers cannot compute, potentially overstating MDMs’ practical capability.\n\n2. The analysis is purely theoretical, without even minimal empirical validation or illustrative experiments to verify whether the predicted efficiency gains appear in practice.", "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": "SEX99UDl9U", "reviewer": "Reviewer_vzeH", "summary": "This paper provides a formal theoretical analysis of the reasoning capabilities of Masked Diffusion Models (MDMs) for language generation. It establishes equivalence between MDMs and Padded Looped Transformers (PLTs) under finite-precision, log-width settings, and compares their expressivity to Chain-of-Thought (CoT) transformers. The authors show that MDMs can simulate CoT reasoning (with some overhead), and are provably more efficient on parallelizable problems. They also identify a \"sequentiality bottleneck\" in CoT transformers, which MDMs can overcome due to their parallel nature. The paper concludes that MDMs are better suited for parallelizable reasoning tasks, while CoT is more efficient for inherently sequential ones.", "questions": "1. Do you plan to validate your theoretical findings empirically? For example, can you design controlled experiments to show that MDMs outperform CoT on parallelizable tasks like expression evaluation or state tracking?\n2. How do your assumptions affect the realism of the model? What are the implications of relaxing assumptions like perfect approximation or uniform unmasking? How would your results change under noisy or learned planners?\n3. Can your framework be extended to other reasoning paradigms? For instance, could similar analyses be applied to latent diffusion models, state-space models, or hybrid autoregressive-diffusion architectures?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides formal proofs and complexity-theoretic characterizations of MDMs, grounding their reasoning capabilities in well-understood models like PLTs and CoT transformers.\n2. It introduces the idea of a \"sequentiality bottleneck\" in CoT and shows how MDMs can leverage parallelism, offering a clear separation in expressive efficiency for certain problem classes (e.g., regular languages, NC1).\n3. The idealized MDM model is motivated by practical implementations, and the authors show how their theoretical framework aligns with real-world MDM behaviors, such as confidence-based unmasking and resampling.", "weaknesses": "1. The paper is purely theoretical and lacks experimental validation of the claims. While theoretical depth is valuable, even synthetic experiments could help illustrate the practical implications of the findings.\n2. The assumptions may be too strong. The analysis relies on idealized assumptions (e.g., finite-precision, log-width transformers, perfect planners/predictors), which may not reflect real-world limitations of MDMs or PLTs.\n3. The reasoning tasks considered (e.g., regular languages, circuit complexity classes) are formal and abstract. It’s unclear how the results translate to more complex, open-domain reasoning tasks commonly faced by LLMs.", "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": "uj8KmJVGph", "reviewer": "Reviewer_ytmY", "summary": "This paper explores the reasoning capabilities of MDMs from the standard complexity theory perspective. The main message of this paper is that MDMs excel on highly parallelizable or ambiguous-generation tasks, achieving strong results with few denoising steps and easy steering via subtask learning. The authors also provide rigorous theoretical statements to support this claim.", "questions": "- How does the theory result affect under without remasking strategy?\n- Are there (at least some prior work's) empirical results that can support the author's claim?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper works on a topic that previous work didn't explore at all: theoretically exploring the MDM's reasoning ability. Although the community believes that MDM can achieve better performance than a causal model in tasks that require non-causal thinking, formalizing that intuition would've been needed for the community. Last but not least, the paper is clearly well-written, even people who aren't familiar with complexity theory can easily follow.", "weaknesses": "This paper doesn't provide any empirical results, which is not actually in the scope, though. Moreover, although the introduction is clearly well-written, Figure 1 gives too much information and is even a bit hard to follow. Also (as far as I understand), this paper's theoretical analysis is based on a remasking scheme (where we remask the unmasked tokens again), which people don't really use in their large-scale Masked Diffusions. Although the authors provide two MDM references that use this scheme, my thought is that the remasking strategy is actually not the mainstream sampling approach, at least by far.", "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": "hvQ8vQKbxf", "reviewer": "Reviewer_rJ1T", "summary": "This paper analyzes the computational capability of MDMs, which is composed of a planner and a predictor, both implemented by transformers. One core finding is the equivalence between MDMs and PLTs under the discussed setting. Based on this equivalence, this paper characterizes the computational capability of MDMs and provides a comparison between MDMs and CoT Transformers.", "questions": "1. Positional encodings. How much of the computational capability attributed to MDMs (e.g., in Theorem 3.2) is actually due to the pre-computed information in the PEs rather than the Transformer’s computation mechanism? This should be more clearly discussed.\n2. Idealized planner. How could practical planners approximate the performance of the idealized planners? A more detailed explanation or empirical investigation of this gap would strengthen the paper's real-world implications.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and provides a detailed discussion of the problem setting, related work, and its theoretical assumptions.\n2. The target question, the computational capability of MDMs, is practically relevant and important.\n3. The proposed \"planner-predictor\" formulation for MDMs is reasonable.\n4. The approach of linking MDMs to the PLTs is natural and allows the use of well-studied conclusions about PLTs.", "weaknesses": "1. Positional encodings. The main theoretical results appear to rely on very strong assumptions about the positional encodings. As discussed in Appendix D.1, the PEs are constructed to carry complex algorithmic information (e.g., the results of division and modulo operations). This assumption seems to offload a large part of the required computation from the Transformer's computation mechanism onto the input representation.\n2. Idealized planner.  In the proofs, the planner is a Transformer designed to perfectly execute a specific algorithm. It is unclear if the practical confidence-based unmasking planner could replicate this perfect capacity.\n3. Empirical study. While the work is theoretical, the results would be strengthened by even simple empirical studies to see the practical performance of the predicted capabilities (e.g., the efficiency of MDMs on parallelizable tasks versus CoT).", "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 (Oral)