On Powerful Ways to Generate: Autoregression, Diffusion, and Beyond
Authors: Chenxiao Yang
Cai Zhou
David Wipf
Zhiyuan Li
Venue: ICLR 2026 Poster (2026)
Keywords: diffusion models
autoregressive models
large language models
expressiveness
Primary area: foundation or frontier models, including LLMs

Abstract: Diffusion language models have recently emerged as a competitive alternative to autoregressive language models. Beyond next-token generation, they are more efficient and flexible by enabling parallel and any-order token generation. However, despite empirical successes, their computational power and fundamental limitations remain poorly understood. In this paper, we formally study whether non-autoregressive generation in Masked Diffusion Models (MDM) enables solving problems beyond the reach of Auto-Regressive Models (ARM). Our results show that MDM with sufficiently large context length is computationally universal with decoding steps matching the optimal parallel time complexity in PRAM. However, when controlling for other factors, MDM's flexibility to generate in any-order does not expand what ARM can already solve. To address this, we propose a new form of generation called any-process generation, which extends MDM with capabilities to remask, insert and delete tokens, allowing self-correction, length-variable editing, and adaptive parallelism. Theoretically and empirically, we demonstrate these capabilities enable scalability to significantly harder reasoning problems that are otherwise intractable for ARM and vanilla MDM. Additionally, they prove essential for generation tasks where objects naturally evolve through non-sequential processes, crucial for extending current LLMs beyond natural language to domains such as coding and science.

Published as a conference paper at ICLR 2026
ON POWERFUL WAYS TO GENERATE: AUTOREGRES- SION, DIFFUSION, AND BEYOND
Chenxiao Yang! Cai Zhou David Wipf
Zhiyuan Li!
i Toyota Technological Institute at Chicago Massachusetts Institute of Technology
I School of Computing & Data Science The University of Hong Kong
{ [chenxiac,
ABSTRACT
Diffusion language models have recently emerged as competitive alternative to autoregressive language models. Beyond next-token generation, they are more efficient and flexible by enabling parallel and any-order token generation. How- ever, despite empirical successes, their computational power and fundamental limitations remain poorly understood. In this paper, formally study whether aon-auoorerresvve generation in Masked Diffusion Models (MDM) enables solv- ing problems beyond the reach of Auto-Regressive Models (ARM). Our results show that MDM with sufficiently large context length is computationally universal with decoding steps matching the optimal parallel time complexity in PRAM. How- ever, when controlling for other factors, MDM's flexibility to generate in any-order does not expand what ARM can already solve. To address this, we propose a new form of generation called uny-process generation, which extends MDM with capa- bilities remask, insert and delete tokens, allowing self-correction, length-variabl editing, and adaptive parallelism. Theoretically and empirically, we demonstrate these capabilities enable scalability to significantly harder reasoning problems that are otherwise intractable for ARM and vanilla MDM. Additionally, they prove essential for generation tasks where objects naturally evolve through non-sequential processes, crucial for extending current LLMs beyond natural language to domains such as coding and science.
INTRODUCTION
The underlying generation process of almost everything in nature follows a unidirectional arrow of time. Perhaps most representative of all, spoken language is produced through a sequential process where each word builds upon preceding context in causal temporal order. This generic inductive bias has been encoded into Auto-Regressioe next-token generation. Despite its simplicity, ARM when scaled through training on vast corpora, has produced remarkably powerful models capable of general-purpose task completion and reasoning. like GPT (Radford et al., 2018; 2019; Brown et al., 2020; Achiam et al., 2023).
Models (ARM) (Shannon, 1951), through
Yet reality might be more convoluted. Humans, when tackling challenging tasks, naturally undergo a non-sequential process of searching for solutions, evaluating and refining them, backtracking when needed, and iterating until answers are found. Such complexity is not fully captured by current ARM, While it is debatable if human intelligence fundamentally follows this left-to-right process (LeCun, 2023; Malach, 2023; Bachmann & Nagarajan, 2024; Berglund al., 2023; Nagarajan al., 2025), ARM appears increasingly ill-suited when we venture beyond natural language.
For example, code generation must be subject to global constraints like balanced parentheses and well-typedness. Maintaining validity at each intermediate step makes transitions from one state to another easier, thus naturally involving updates such as inserting functions, adding branches, or changing input types. In biology, many domains remain largely beyond the reach of current LLMs, as molecular structures such as proteins and genes are combinatorial objects that can be modeled as graphs, trees, or strings that satisfy physical constraints. Their generation proceeds most naturally through structure-aware edits, e.g., swapping protein domains, inserting binding motifs into sequence graphs, or recombining DNA/RNA segments (Wang al., 2023).

---

Published as a conference paper at ICLR 2026
Seyal
Sky
quick
Stel
runte oiver
quick beoks Fox
quick brown
[+]
OVBE
[
Euna
Loga
Lie
qu likk
brown Fox Leaps
quick brown Eox
[
0Ve
[
the quick
[M]
Fox
runs (owe
logs
quick broks Iox Leapu DVBE
quick brown Fox
Over Logs
Map
the quick
BEOWn
Sox
ciea
Loga
quick
leeps over
Loga
quick brown Fox Imaps
over logs
Weyt
quick Saoowtt
Lmeps
loge
Auto-Regressive Generation
Any-Order Generation
Any-Process Generation
Figure 1: Comparison between autoregressive generation, any-order generation (standard MDM) and any-process generation (our MDM).
Given the long-standing pursuit of building foundation models powerful enough to handle increasingly complex reasoning tasks and general enough to work across diverse domains beyond natural language, it becomes important and timely to rethink the generation process itself, mechanism separate from architectural specifics, by formally asking:
How do we formally compare various ways to generate, and what opportumities may lie beyond next-token generation?
Recent work suggests that next-token generation is not the only viable path. Masked Diffission Models (MDM) (Hoogeboom et al., 2021; Austin et al., 2021; Lou et al., 2024; Sahoo et al., 2024; Shi et al., 2024) offer compelling alternative procedure that, instead of causally generating tokens one by one. permits any-order generation and produces multiple tokens in parallel, with recent large-scale instantiations (DeepMind, 2025; Labs et al., 2025; Nie et al., 2025; Ye et al., 2025) showing comparable performance with AR-based LLMs. Interestingly, besides faster decoding (up to 10x speedups), MDM's generation process brings empirical improvements on some order-sensitive tasks such as reversed-order poem completion (Nic et al., 2025; Berglund et al., 2023) and Sudoku puzzles (Kim et al., 2025c; Shah et al., 2024). This motivates us to formally study it and compare with ARM.
Perhaps counterintuitively, we find while MDM is indeed more powerful than ARM in terms of parallelism and efficiency for simple tasks, the benefits of seemingly greater flexibility are surprisingly limited. Like ARM (Merrill & Sabharwal, 2024; Feng et al., 2024; Li et al., 2024), MDM also achieves Turing-complltennsss, but does more efficiently with optimal parallel time complexity (Theorem 1), thus enabling exponential speedups for simple parallelizable problems. However, for harder reasoning tasks, MDM faces similar fundamental limitations as ARM: both struggle with problems requiring backtracking and rewriting capabilities, and cannot handle them given realistic space resources (Theorem 2). Moreover, when controlling for other factors including degree of parallelism and architecture, any-order generation itself does not expand what ARM can already handle (Theorem 3), since any computation performed by MDM can reorganized into left-to-right order to align with the underlying arrow of time. Therefore we ask:
What are provably more powerful ways generate?
As an initial step, propose Any-Process Generation, inspired by natural generative mechanisms found across domains. It extends standard MDM beyond its existing unmask capability with three additional operations (see Figure 1): remask (converting decoded tokens back to masks), insert (adding new mask tokens at any position), and delete (removing mask tokens), all learned end-to- end from data without architectural changes. Freed from conventional physics-inspired diffusion frameworks, mny-peossss generation removes unnecessary restrictions on mask ratios, decoding steps, sequence lengths and stopping criteria, enabling structural editing and test-time scaling. With these modifications, we show that MDM brings significant promise with both encouraging theoretical and empirical results as follows.
The capability to rewrite and backtrack breaks the non-erasable limitations of ARM and standard MDM, enabling our model to achieve both optimal parallel time and space complexity (Theorem 4), thus solving many NP-hard problems with polynomial space through test-time scaling, i.e. an exponential improvement from achieved by ARM and standard MDM. Empirically, on Sudoku puzzles (Figure 2(a)), our model achieves 99.28% accuracy using only 100 training instances, outperforming ARM (87.18%) and any-order MDM (89.49%) with 5 parameters trained on 1.8M instances, which is orders of magnitude more.
Scalability to Hard Problems:
2

---

Published as a conference paper at ICLR 2026
21
277
217
1
PID
1
1
5
19
5
MEBUI
XE
Learning Order
Backtracking
(a) Sudoku (NP-Complete Problem). Scaling up inference-time computes to solve significantly harder problems by allowing rewrites and backtracking using the remask operation (3 5.1).
Ruto-Regresssve ( Express
Any-Process MDM (Eas Express
ROO [{OT()I))
(01O))
Insert
Insert & unmask
unmask
(b) Coding (Matched Parentheses/ Dyck-A). Generating any-sized two-sided Dyck-k is impossible for ARM, while our model can easily do so with the insert operation ($ 5.2).
Auto-Regressive
Generalize X)
Any-Process MDM
Generalize
1101 [BOS] 1011 [SEP] 1001 True
[305] 11011.1. 1111....
BOS]
[BOs] 0 0
remask
delete
(c) Parity (Counting 1s). Length generalizing parity and counting problems are enabled by learning simple climination algorithm with the remask and delete operations (g 5.3).
Tic G TIT Nerrs TT a
M
M
TTT
MERUUS
TIT
zic TIT III cla IIL
TT ajj TIT TL L cja ITI
TIT a TIIT c Ill
M
(d) DNA Recombination (Splicing System). An example in science / biology where DNA segments are spliced and pasted using combinations of operations, which is hard for ARM 5.2).
IVEI
EvER
DVLL
Parallel Feature Editing
Parallel Structure Editing
(c) Graph Editing. Editing combinatorial structures where feature/ / structural evolution and parallel computation naturally integrated (g 5.3). Using ARM to simulate is hard ($ 5.4).
Figure 2: Examples of any-process generation for different tasks.
Generality to Sequenqult Objects: The flcxibility to rewrite, insert, and delete tokens enables structure-aware generation processes for objects that inherently resist sequential construction, such as DNA recombination biology (Figure 2(d)) and 2D graph generation (Figure 2(c)). This advantage be formalized through simple task of matched parentheses generation (two-sided Dyck-k language), i.e. one of the most basic constraints in coding. Theorem 5 proves that ARM cannot cover the entire support beyond length threshold, because enforeing the generation into left-to- right order demands global foresight of future tokens that is beyond the computational power of constant-depth Transformers. contrast, AP-MDM can easily do at arbitrary length using insert operations (Figure 2(b)). Empirically, we verify the structural generation capability of AP-MDM on a challenging graph editing task. The results show that our approach maintains perfect accuracy for increasingly larger graphs, while ARM performance degrades significantly as graph size increases.
Learning and (OOD) Generalization: Our approach enables learning simpler algorithms that significantly improve learning and generalization. For parity checking (Figure 2(c)), our model achieves 100% generalization to arbitrary lengths after training on only length-2 sequences, while even the latest GPT models struggle this embarrassingly simple task.
Finally, envisioning a future with access data of the underlying generation processes of objects wish to generate, such code revisions, math proof drafts, molecular formation processes, any-process MDM theoretically and empirically more suitable than ARM (Theorem 6) since MD- is hard to be simulated by ARM due to the complexity introduced by editing operations.
3

---

Published as a conference paper at ICLR 2026
2 PRELIMINARY
Auto-Regressee Model (ARM) Let M be finite-sized vocabulary and -n + > be next- token predictor, which maps a sequence x = (I1, 22, ,T,) E 2 to a token In+1 E M. An autoregressive model (ARM) is defined based concatenating input sequence x and the next token x xxx). i.e. fxx) = (x, (x)). ARM formulates generation as an iterative process by repeatedly applying / to the current sequence. In practice. / is typically parameterized by Transformer (Vaswani et al., 2017) with causal attention and learnable (CoT) (Wei et al., 2022) in
sequeence-to-sequuenee mapping : E E',
parameters 0. The notion of ARM here also aligns with Chain--of-Thuugee many other works and we will use them interchangeably throughout this paper.
Masked Diffusion Model (MDM) Let Σ U {M} be the extended vocabulary where M is an absorbing mask token (Austin et al., 2021). Consider sequences X, = (xx,1, St,.......... Tt.s) E Σ indexed by time [T], where S is the maximum context length, T the number of decoding steps, = {M} is the fully masked sequence and Xr E Σ is the target clean sequence. A masked diffusion model (MDM) (Lou et al., 2024; Sahoo et al., 2024; Shi et al., 2024) also relies on sequence-to teateenceet--sepeee to-squuee- mapping f 5S ES with Xt+1 = [xx). formulating generation as an iterative process by repeatedly applying f to progressively unmask tokens from the all-mask state.
Among many MDM variants, we consider the following standard design choices from recent large language diffusion models (Nie et al., 2025): 1) linear noise schedule with S = P- T' for integer P. where each step reveals exactly P tokens; 2) sesiiddeeeebbseee adaptive decoding (Chang et al., 2022) rather than random token selection; 3) encoder-only Transformer architecture without timestep embedding; 4) conditional generation where input prompt x of length n is prefix of Xo, with calculated within context length S, aligned with reasoning problem setup for ARM. Detailed MDM introduction and encoder-only Transformer definition are in 5 B and F, respectively.
3 A THEORY OF MASKED DIFFUSION
The generation process in MDM is unique in two different ways: it generates multiple tokens in parallel and permits any-order generation. We now investigate whether and how exactly these properties, in their own right, translate into concrete advantages.
3.1 POWER OF PARALLELISM
Prior work (Merrill & Sabharwal, 2024; Feng et al., 2024; Li et al., 2024) has shown that ARM with sufficiently many intermediate steps is Turing-complete and thus can solve any computable problem. Analogous to the role of intermediate steps in ARM, two governing resources determine MDM's power: 1) number of decoding (denoising) steps T'n)), and 2) maximum context length S(n) (equivalently, the maximum number of tokens available to decode).
Definition 1 (MDM). Let MDM (n),, T(n) be the class of decision problems solvable by MDM ($ 2) with maximum context length Snn) and at most T(n) decoding steps, using some constant depth and lng(n) embedding size encoder-only Transformer. Also, let
= U (())))
T(n)
To formally characterize MDM's expressivity in relation T(n) and S(n), we establish connection with the canonical parallel computation model called Parallel Random Access Machine (PRAM) (For- tune & Wyllie, 1978; JáJá, 1992), which is the RAM model extended to multiple processors executing over shared memory. See detailed introduction and a formal definition of the variant we use in & E.
Definition 2 (PRAM). Let P(n) be the number of processors budget, and w()) = O(log n) the word size. Define PRAM[ P(n), T(n)) as the class of decision problems solvable by uniform CREW PRAM (see & E for CREW specification) using at most P(n) processors in al most T(n) parallel time. Theorem 1 (MDM Simulation of PRAM, Informal). For any PRAM program that runs on input x E E in al most ((n) parallel time with P(n) maximum processors, there exists an MDM on input x, padded to S(n) O (P(n)) T(n)), that matches the PRAM output in (T()) decoding steps, i.e. PRAM( T(n) S MDM(O(P(n) T(n)), (T()))) See formal statement in Theorem 8.
This demonstrates that MDM can simulate any PRAM algorithm with optimal parallel time complexity, thereby it is not only Turing-compler as ARM already achieves, but can also solve
Unlike convention in diffusion model where larger denotes earlier inference steps, we use following an intuitive feed-forward ordering during inference, i.c. the facus of this paper.
4

---

Published as a conference paper at ICLR 2026
problems significantly faster with parallelization, something ARM cannot offer. The speedup can be exponential compared to ARM's serial time complexity: for efficiently parallelizable problems in NC (Arora & Barak, 2009),² graph connectivity can be solved in (log n) decoding steps versus ARM's linear complexity, and context-free languages including Dyck-k require only (log" 2 n) steps. These tasks have been demonstrated hard or inefficient for ARM in previous literature (Strobl et al., 2024; Zhu et al., 2025).
Remark While MDMs can achieve optimal decoding steps (and thus wall-clock time) through parallel decoding, encoder-based architectures require re-encoding the entire sequence each step and cannot utilize KV caching. resulting in higher per-step FLOPs compared to decoder- based ARM. In theoretical construction for Theorem 1, we do not find such trade-off unavoidable, suggesting potential to improve per-step FLOPs while maintaining the parallel time advantage for current MDMs.
3.2 (UN)SCALABILITY TO HARD TASKS
While noteworthy, the computational power described above comes with non-negligible cost: solving a problem requires context length S(n) to scale as (T P(n)) (the total parallel work), quantity at least as large the serial time complexity (with P(n) = 1), per Brent's 's Theorem (JáJá, 1992). Particularly, in resource-constraingg
regimes, we have:
Theorem 2. (DM))(()) c PRAM(1, (1))) where logarithmic are hidden in Ó.
In other words, MDM with context length (1)) cannot solve problems requiring more than ((S3(n) serial time. This limitation is also shared by ARM (Yang et al., 2025).
This implies MDM is inherently not scalable to solving hard reasoning or generation tasks: for problems beyond P (e.g.. NP-hard problems), this would require superpolynonial context length (under standard complexity assumptions), practically intractable in terms of both memory and per-step FLOPs. The root cause lies in MDM's irreversible token generation: once decoded, those positions cannot be reused or rewritten. As reflected in the construction of Theorem 1, each memory write must be permanently stored as tokens, forcing space to scale with computation time.
In contrast, human reasoning on hard problems naturally involves continuous revision, exploration of alternative paths, and correction of mistakes before reaching final conclusions. Generation tasks no different: for instance, generating planar graphs (drawable on planes without edge crossings) with minimum splitting numbers is NP-complete and naturally involves iteratively adding nodes, checking planarity constraints, and backtracking when violations occur. Such a process has not been captured by either ARM or MDM.
3.3 (LIMITED) POWER OF ANY-ORDER GENER ATION
Any-order generation seems to offer extra flexibility over auto-regression, but does it truly translate into computational advantages? To attribute gains to any-order generation itself, we control for orthogonal factors differentiating ARM and MDM: 1) the number of tokens generated per step, and 2) the backbone architecture (decoder v.s. encoder). The former has already been shown to confer stronger parallelism to MDM (3 3.1); the latter provides internal parallelization benefits (Ewer et al., 2024) and improved expressiveness through padding with dummy tokens (i.c. M) (Merrill & Sabharwal, 2025).
Therefore, we fix MDM to emit exactly one token per step and ARM use the with mask tokens padding the sequence to the same length (called Masked-ARM), or equivalently:
Definition 3 (Masked- ARM). A Masked-ARM is defined as an MDM (8 2) that is forced to decode in left-to-right order and one token per step.
Perhaps counterintuitively, show that the computational benefits from any-order generation are rather limited: any-order generation itself does not expand what ARM can already solve
Theorem (Left-to- Right v.s. Any-Order, Informal), For any AO-MDM with context length S(x) decoding one token per step, there exists Masked-ARM with length (()) and extra constant
NNC is the complexity class for efficiently parallelizable problems. those that are solvable in polylog(n) time using poly(n) processors; NC C P and it is open whether NC = P (Greenlaw et al., 1995). PRAM is the canonical model for this notion Turing machine for
5

---

Published as a conference paper at ICLR 2026
layers, that can produce the same generation process for any given input by explicitly specifying both where to write (position) and what to write (token). See formal statement in Theorem 9.
Simulating any-order generation with autoregressive models is not hard because the attention mecha- nism is good at fetching information from any position, and re-organizing it internally in the correct order to perform the same computation. While Masked-ARM need not replicate MDM's exact final sequence, additional post-processing step align their outputs without affecting the theoretical conclusion. There are also some empirical evidence showing the effectiveness of ARM simulating any-order (Xue et al., 2025).
But not all intricacies inherent in natural generation processes can be easily sequentialized. Coding for example (as well as many natural scientific processes alike), involves anywhere editing where new valid state depends upon previous valid states that may not be contained in the final sequence. And even when described in left-to-right temporal order, reproducing the state requires more than simple re-organization, which attention is already provably good at. Hence such a complex process is not captured by ARM or MDM as currently instantiated.
Remark We note that MDM's 's observed advantages in practice may lie in discovering an optimal order (Kim et al.. 2025c) from data, where left-to-right ordering need not exactly correspond the optimal temporal generation order, though computationally equivalent (Theorem 3).
4 ANY-PROCESS GENERATION
We now introduce Any-Process Generation, more powerful generation paradigm that extends the any-order masked diffusion from ş (referred to as AO-MDM hereafter) by removing various restrictions to capture natural processes not present in existing generation strategies.
General Formulation Let fo - x Σ C be a function, by default parameterized by the same Transformer architecture, which input X E Σn returns the triple (Xx. Yk. c&) with ya Eiael and cı E Cixe1, where X may contain one more M tokens (a masked sequence) while is mask-free; yı and C₁ have the same length as the input. Core to the design of this generation process is parameter-free frre (and optionally non non-deterministic) transition function g : Σ* x Σ' x C* + Σ', which takes (xx. Yk, C&) as input to produce the next sequence Xk+1 E Σ" that can differ in length from Xg- The inclusion of input x itself in the output of fo (xx) ensures that g has access which positions are masks initially. Overall, generation is formulated as the iterative application of fo and until some stopping criterion met:
x++1 = (fo(x))) and hence x, = (g (x)) go So foogo So ogo (x
(1)
Notably, unlike vanilla MDM, this framework imposes restrictions mask ratios at any given time step, therefore each decoding step can unmask an arbitrary number of tokens, and Xy can be the input prompt directly with no initial mask, as in ARM. This framework also does not limit the maximum number of decoding steps T, the stopping criterion is flexible and need not be a fully unmasked sequence, as in ARM. We dub this class of models as Any-Process MDM (AP-MDM) and will detail a specific instantiation. It is not difficult to see AO-MDM is special case of AP-MDM.
4.1 AN INSTANTIATION WITH UNMASK, REMASK, INSERT, AND DELETE OPERATIONS
Define C = {0, 13... For each position i and time step t. the per-position control is 3-bit vector C. (1), c2. (3) E reserved for different purposes that will be detailed below. Correspondingly, we write c: = (c.,I,..., x. E Clx.1.
Capability: Rewrite via Remask We use the first bit of the per-position control c,,[1] {0.1) to control remasking (and whether to unmask) and define Vy E Σ:
M y
if F = 1
remask (v)
if xr,, = M and c,,
otherwise
In other words, when [1] 1, position is mask after decoding regardless of its previous state; otherwise, standard unmasking follows as usual. This operation enables self-correction and rest-time scaling, allowing models to scale computation exponentially in S(n) before state repetition occurs.

---

Published as a conference paper at ICLR 2026
Additionally, since the remasking signal can be learned from data, models adaptively determine both decoding order and parallelization degree at each step.
Capability: Length-Variable
Variable Edit via Insert Delete We the second and third bits of the per-position control Cr, to govern insertion and deletion, respectively. Define Vy E Σ {e}:
inserta, (v) (y) M)
c2, =1 delete (v) {{
if ,1,4 M and c,,
otherwise
otherwise
where denotes the empty string. In other words, insert adds mask token after position i when Ce.a [2] = 1. and delete removes position when it was originally a mask token (zz,; = M) and cr. = 1. These operations enable dynamic sequence length adjustment based on problem complexity, with the insert operation allowing sequence length to grow exponentially as each mask loken can spawn additional masks. Furthermore, the delete operation provides computational efficiency by freeing space during stages that require less extensive computation, reducing overall FL.OPs waste. This mechanism can work orthogonally with cemi-autoregrrssoon (Arriola et al., 2025) that expands space at the end of the sequence.
Composition To summarize, each decoding step applies the three operations coordinate-wis and concatenates the resulting segments:
So (xx) = Yr, g(x,, Yr, Ct) (81,1, 81,2, (1, -(,12()) Xe+1
(4)
where $t,i inserte,, o deletez.,. o remask (Bt.1); Vi E [xx]]]
An algorithmic description of any-process generation with these operations is given in Algorithm 1, 8 C.4. And the stopping criterion can be flexibly defined, c.g. one can use generation of an EOS token (as in ARM) or convergence capabilities requires no changes to the Transformer structure, only three additional logit dimensions needed for producing control signals, i.e. three extra linear heads (details in Š C.I).
repeated sequence (loop occurs). Architecturally. implementing these
Pre-Training / Tiin-TTnnng// Data Availability All three operations can be trained end-to-end from text corpora using self-supervised objectives, preserving MDM's scalability to large-scale training (details in & C.2). The minimal architectural changes also enable direct fine-tuning from existing large diffusion models, possibly using supervised data where the underlying generation process is explicitly constructed (details in & C.3). This training flexibility separates our approach from alternatives like looped Transformers (Dehghani et al., 2018; Giannou et al., 2023), which are expressive but notoriously difficult to train due to lack of intermediate supervision.
Design Considerations The proposed three operations all revolve around the mask token M, leveraging existing MDM's strong unmasking capability while only adding modular extensions that are easier to pretrain or fine-tune than learning harder operations such as inversion of uniform noise (Sahoo et al., 2025). Moreover, while the definitions of and c, in (4) suffice for achieving theoretical benefits detailed later, they are not necessary conditions; other designs are possible.
Positional Encoding When insertion or deletion operations modify sequence length, update the positional encodings according to the new token positions. This position re-encoding mechanism is essential for AP-MDM's expressivity advantages ($ 5) as we will show, allowing the model to represent more complex processes where position shifts carry meaningful structural information.
We note that the ideas of remasking and editing have been individually explored in some prior/concur- rent works (Wang et al., 2025; Peng et al., 2025; von Rütte et al., 2025; Havasi et al., 2025; Wu et al., 2025). However, there has not been systematic study of guidance principles for yielding provable computational benefits and their practical implications. See discussions 5 A.
5 THE POWER OF ANY-PROCESS GENERATION
We now show how any-process generation circumvents various difficulties that current ARM and MDM encounter when handling tasks across different domains and complexities.
5.1
UNIVERSALLY EFFICIENT COMPUTATION
Benefit I: Scalability to significantly harder problems through rewriting and backtracking.
7

---

Published as a conference paper at ICLR 2026
Method
# Samples
# Param
Accuracy
0.020
Remaskk (Train)
Unmaask (Train)
ARM (w/o ordering)
1.8M
42M
9.73%
0.015
Remaskk (Val)
Unmaskk (Val)
ARM (with ordering)
1.8M
42M
87.18%
Loss
CD-MDM (vanilla)
18M
6M
6.88%
0.010
AO-MDM pobbbbliny
18M
6M
18.51%
0.005
AO-MDM
1.8M
6M
89.49%
AP-MDM
100
1.2M
99.28%
0.000
50000
100000
Steps
(a) Comparison of accuracy on Sudoku.
(b) Convergence of losses.
Figure 3: Experimental results on Sudoku puzzles. Results of ARM and AO-MDM are taken from
Kim et al. (2025c). Losses are defined in C.2.
As discussed in 3 3.2, inherently hard problems (e.g. many NP-hard tasks) typically do not admit sequential processes but require iterative "search-verify-reviss loops, which hold across various domains: from theorem proving, solving code challenges synthesis of complex structures in nature. The pathological way current generation paradigms gms let discardable tokens accumulate indefinitely creates scaling barriers, where space explodes and each step incurs ever-increasing computational cost (Theorem 2). We now demonstrate how AP-MDM resolves this:
Theorem 4 (AP-MDM Simulation of PRAM, Informal). For any PRAM program that runs at most TT) parallel time, P(n) processors and ('n) memory usage, there exists an AP-MDM that matches PRAM output on any given input with (m)) context length and (T())) decoding steps. See formal statement in Theorem 10.
By comparison, standard MDM requires space scaling with the total work O(P(n) T(n)) (Theo- rem 1), whereas AP-MDM requires only the actual space needed, achieving both optimal parallel time and space complexity (Theorem 4). This implies AP-MDM not only retains the efficiency of parallelization, but also dramatically expands the range of solvable problems. In particular, given polynomial context length, AP-MDM can solve problems in PSPACE rather than just P. which is an exponential improvement that makes many NP-hard problems solvable with test-time scaling.
Experiment: Sudoku Puzzles We conduct experiments on Sudoku puzzles, i.e. an NP NP-complete problem when generalized to n² x n² grids, requiring both the capability of any-order generation, and the capability to rewrite. As illustrated in Figure 2(a), AP-MDM can use the remask (and standard unmask) operations to choose the easiest position to fill first, and also erase failed branches and try alternative assignments, effectively scaling compute to solve harder instances.
We follow the experimental setup from (Kim et al., 2025c) but with a key difference: while the original work used 1.8M training puzzles, we use only 100 (moderately hard) instances for training AP-MDM. Despite this significantly reduced dataset, our approach achieves near-perfect accuracy (99. (9%, on most Sudoku puzzles, outperforming both AO-MDM and ARM that use substantially more samples and larger model sizes, as shown in Figure 3. Any-process generation is more sample- efficient because if the model is allowed to conduct more computes and more steps to solve the same problem, each step would become easier to learn. Orthogonally, we find from the training dynamics in Figure 3 that the model quickly learns to identify and fill the easiest positions (unmasking loss drops rapidly), while learning the order (which position to fill next) proves more challenging.
5.2 STRUCTURAL GENERATION: EXAMPLES IN CODING AND SCIENCE
Benefit 2:
Generating (or reasoning over) complex structured objects that evolve non non-sequentially. common across domains beyond natural language (e.g. coding, science).
When the evolving object involves some complex structures (e.g. trees, graphs, strings with con- straints) that do not inherently build up linearly, forcing the generation into sequential procedure can introduce unnecessary computational difficulties. Such scenarios are especially common across domains beyond natural language (e.g. coding, biology), which current LLMs struggle with.
Coding Programs generally require satisfying global constraints like syntax and semantics at every intermediate state during development, since building each state upon the previous valid one is casier than jumping directly to the final solution. To illustrate this, consider the basic task of generating matched parentheses (the Dyck-k language with À types of parentheses), illustrated
Example 1:
8

---

Published as a conference paper at ICLR 2026
in Figure 2(b). Natural generation involves inserting parentheses anywhere without breaking balance constraints, while left-to-right generation requires global foresight and constant validity checking during generation, provably impossible for Transformers at scale. Particularly, we consider a variant called the two-sided Dyck-k k (Definition in & L):
Theorem 5 (Generating Two-Sided Dyck-k, Informal). For any k 2 2, there exists a stochastic AP-MDM whose generation distribution has support exactly equal the two-sided Dyck-k language, ie., a string has positive generation probability if and only if it is in the language. Conversely, for any fixed ARM, there exists a length threshold beyond which the ARM cannot guarantee positive probability for all strings in two-sided Dyck-k. See formal statement in Theorem 12.
This result holds because generating Dyck language for arbitrary length is as hard as recognizing it, i.e., deciding if the current sequence has matched parentheses, which Transformer restricted in TC expressivity cannot do. Intuitively, both ARM and vanilla MDM require global foresight capabilities that are computationally hard for constant-depth Transformers: ARM must foresee the matching closing brackets when generating opening ones (requiring global planning of the nested structure), while vanilla MDM must predetermine the number of tokens between each matched pair at initialization and commit to fixed positions that cannot be modified later. In contrast, AP-MDM fundamentally circumvents these difficulties through insertion operations, allowing the model to iteratively build the structure through local decisions that are simple to represent.
Example 2: Science Biology Consider linear splicing (Head, 1987; Päun, 1996), which is DNA recombination abstracted (and perhaps simplifie)i as cutting two strings and cross- pooss-patting their halves, as illustrated in Figure 2(d). Iterating such rules from finite seed set generates splicing language, and any regular language with a marker added to the left side can be generated by such a system (Head, 1998; Kari & Kopecki, 2012), while regular language has been proven impossible for constant-depth Transformers (Liu et al., 2022: Li et al., 2024).
To empirically verify AP-MDM's advantage on tasks concerning non-sequential objects, we consider a graph generation task which involves structural editing.
Experiment: Graph Generation Given a directed graph and a prompt specifying source and target nodes s and f, the model is required to generate a modified graph that disconnects s and t by removing the minimum number of edges. This is equivalent to finding the min-cut. Efficient algorithms for generation typically involve iterative editing: 1) Use BFS to find a path from to i; 2) Augment this path and modify the graph structure; 3) Repeat until s and are disconnected, then remove the min-cut edges. Any-process generation is naturally suited for such graph editing tasks, leveraging inser//delete/remask operations for adaptive structural and feature modifications and MDM's s parallel capabilities, as illustrated in Figure 2(e). As shown in Figure 4, our model achieves almost perfect accuracy for increasingly larger graphs. Meanwhile, when we train ARM to simulate the same process, it fails to perform well as graph size increases.
5.3 LEARNING AND OOD GENERALIZATION
Enabling the of simpler algorithms solve problems, thereby improving sample efficiency and (out-of-distribuutin) generalization.
Benefit 3:
Experiment: Parity Given a binary sequence E {0. 1}" parity involves determining if there are an even or odd number of 1s. This task is conceptually trivial but embarrassingly difficult for LLMSs. Intuitively, the difficulty arises because ARM is forced to attend the entire input and learn position-invariant target function, which hard on training sequences with finite-length. With any- process generation, the model circumvents this difficulty by learning simple climination algorithm: examine the first two tokens, delete all Os if the pair contains any 0 or delete the pair if both are 1s, then repeat until all are processed (Figure 2(c)). The answer is true if any Is remain. This mimics how humans solve the problem, a simple
approach only possible with deletion.
As shown in Figure 4, our model achieves 100% accuracy on any length after training on only 2 length sequences with a tiny model (~2000 parameters), while ARM with orders of magnitude more parameters and samples fails generalize beyond training lengths.

---

Published as a conference paper at ICLR 2026
Graph Size (# Nodes)
ARM Acc.
AP-MDM Acc.
100
90.32%
100%
90
AR (n=22
43.04%
100%
AR (m-10)
Accuracy
80
6
0.30%
100%
AR (n-50)
7
N/A
100%
70
AR (m-100)
8
N/A
99.99%
Ours (n=2)
9
N/A
99.97%
50
10
N/A
99.92%
110
50
100
150
200
Sequence Length
(a) Graph generation via editing.
(b) Length generalization on parity.
Figure 4: Graph generation and parity task results.
5.4 HARDNESS OF BEING SIMULATED
Benefit 4: If in the future we have access to data of underlying generation processes (e.g. revision history of code, articles, math proof drafts, molecular formation processes), any-process MDM is more suitable than ARM for practical training.
Besides scalability to harder tasks ($ 5.1) and universality across domains (6 5.2), crucial question remains: suppose given access to datasets containing revision histories the objects we wish to generate, would AP-MDM be the most appropriate model for such data and sarge-scale training? To answer this, we consider ARM as a competitor as it is Turing-complete, and equally expressive as AO-MDM (Theorem 3) when controlled for orthogonal factors.
We next show ARM is inherently unsuitable for training on editing datasets in two ways. Firstly, unlike any-order generation (Theorem 3), AP-MDM's editing operations are hard to be simulated by ARM by explicitly specifying editing operations applied at each decoding step; particularly
Theorem (Hardness of Simulating AP-MDM, Informal). There exists a constant-deptle AP-MDM, such that no constant-depth ARM can simulate the generation process of that AP-MDM using sequence of triplets, i.e., what operation to use (unmask, remask, insert, delete), where apply the operation (position) and what to write for the unmask operation (token), on any input under some complexity hardness assumptions 8 M. See formal statement in Theorem 13.
The key difficulty of simulating AP-MDM lies in the additional complexity brought by the insertion and deletion operations that trigger position shifts: ARM must internally reconstruct the entire editing trajectory determine what token currently occupies each position (formalized via the PRESERVE problem in & M), which is computationally hard for constant-depth Transformers.
Empirically, show that representing our generation process using triplets described above for ARM simulation indeed becomes increasingly difficult to train as sequence length grows, as demonstrated in the graph generation task in $ 5.2.
Secondly, if we disregard the resource constraints from & 5.1 and $ 5.2, simulation becomes possible through additional intermediate steps, but this could require highly contrived trajectories that defeat the purpose of practical training, e.g. periodically summarize the current state, or using more than constant tokens represent each application of an operation.
6 CONCLUSION
This paper provides formal analysis of generation processes and shows, provably and empirically, that moving beyond standard autoregression and current masked diffusion yields more powerful models. These results suggest concrete design principles for frontier LLMs, pointing to training and decoding schemes that scale to increasingly hard tasks and generalize across domains such as code and the sciences. See further contextualization with respect related work in A.
USAGE OF LARGE LANGUAGE MODELS
In this work, use LLMs for literature retrieval and discovery, writing assistance and polishing, and code writing and debugging support. We carefully monitor potential issues such as plagiarism or factual inaccuracies to ensure academic integrity.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
Eric Allender, Tanmoy Chakraborty, David A Mix Barrington, Samir Datta, and Sambuddha Roy.
Grid graph reachability problems. In 21st Annual IEEE Conference on Computational Complexity (CCC'06), pp. 15-27. IEEE, 2006.
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
Marianne Arriola, Aaron Gokaslan, Justin T Chiu, Zhihan Yang, Zhixuan Qi, Jiaqi Han, Sub- ham Sekhar Sahoo, and Volodymyr Kuleshov. Block diffusion: Interpolating between autoregres- sive and diffusion language models. arXiv preprint vrXiv:2503.09573. 2025.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete spate-spaces. In Advances in Neural Information Processing Systems, volume 34, pp.
2021.
Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. arXiv preprint arXiv:2403.06663, 2024.
Lukas Berglund, Meg Tong. Max Kaufmann, Mikita Balesni, Asa Cooper Stickland, Tomasz Korbak, and Owain Evans. The reversal curse: Lims trained on" is b" fail to learn" b is a". arXiv preprint arXiv:2309. 12288, 2023.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neurul information processing systems, 33:1877-1901, 2020.
Huiwen Chang. Han Zhang, Lu Jiang, Ce Liu, and William T. Freeman. Maskgit: Masked generative image transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11335-11345, 1335, 2022.
Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. International conference on machine learning, pp. 933-941, PMLR, 2017.
DeepMind. Gemini diffusion, 2025. gemini-diffusionn
URL https::/deeppindd.eee htt.://pwii.nd.ooooooo/ooo//ooee google
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Eukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018.
Ethan Ewer, Daewon Chae, Thomas Zeng, Jinkyu Kim, and Kangwook Lee. Entp: Encoder-only next token prediction. arXiv preprint arXiv:2410.01600, 2024.
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024.
Steven Fortune and James Wyllie. Parallelism in random access machines. In Proceedings of the tenth annual ACM symposium on Theory of computing, pp. 114-118, 1978.
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-predict: Parallel decoding of conditional masked language models. arXiv preprint 1nXiv:1904.09322 2019.
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. In International Conference on Machine Learning, pp. 11398-111 1138-11142. PMLR, 2023.
Raymond Greenlaw, H James Hoover, and Walter L Ruzzo. Limits to parallel computation: P- completeness theory. Oxford university press, 1995.
11

---

Published as a conference paper at ICLR 2026
Nate Gruver, Samuel Stanton, Nathan Frey, Tim GJ Rudner, Isidro Hotzel, Julien Lafrance- Cafrance-Vanasse, Arvind Rajpal, Kyunghyun Cho, and Andrew G Wilson. Protein design with guided discrete diffusion. Advances in neural information processing systems, 16:112499-2511 2023.
Jiatao Gu, Qi Liu, and Kyunghyun Cho. Insertion-based decoding with automatically inferred generation order. Transactions of the Association for Computational Linguistics, 7:661-676, 2019a.
Jiatao Gu, Changhan Wang, and Junbo Zhao. Levenshtein transformer. Advances in neural informa- fion processing systems, 32, 2019b.
Marton Havasi, Brian Karrer, Itai Gat, and Ricky TQ Chen. Edit flows: Flow matching with edit operations. arXiv preprint arXiv:2506. 2025.
Thomas Head. Splicing languages generated with one sided context. Computing With Bio-molecules: Theory and Experiments, pp. 269-2822 1998.
Tom Head. Formal language theory and dna: an analysis of the generative capacity of specific recombinant behaviors. Bulletin of mathematical biology, 49(6):737-75,, 1987.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in neural information 12465, 2021.
processing systems,
Joseph Jálá. Parallel algorithms. 1992.
Lila Kari and Steffen Kopecki. In International Workshop on DNA-Based Computers, pp. 98-109. Springer, 2012.
Deciding whether a regular language is generated by splicing system.
Jaeyeon Kim, Lee Cheuk-Kit, Carles Domingo-Enrich, Yilun Du, Sham Kakade, Timothy Ngotiaoco, Sitan Chen, and Michael Albergo. Any-order flexible length masked diffusion. arXiv preprini arXiv:2509.01025, 2025a.
Jaeyeon Kim, Seunggeun Kim, Taekyun Lee, David Z Pan, Hyeji Kim, Sham Kakade, and Sitan Chen. Fine-tuning masked diffusion for provable self-correction. arXiv preprint arXiv:2510.01384, 2025b.
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, 2025c.
Inception Labs, Samar Khanna, Siddhant Kharbanda, Shufan Li, Harshit Varma, Eric Wang, Sawyer Birnbaum, Ziyang Luo, Yanis Miraoui, Akash Palrecha, et al. Mercury: Ultra-fast language models based diffusion. arXiv preprint arXiv:2506. 17299 2025.
Yann LeCun. Do large language models need sensory grounding for meaning and understanding, In Workshop on Philosophy of Deep Learning, NYU Center for Mind, Brain, and Consciousness and the Columbia Center for Science and Society, 2023.
Seul Lee, Karsten Kreis, Srimukh Prasad Veccham, Meng Liu, Danny Reidenbach, Yuxing Peng. Sace Paliwal, Weili Nie, and Arash Vahdat. Genmol: A drug discovery generalist with discrete diffusion. arXiv preprint 20XX:25511006552 2025.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint 12885 2024.
Bingbin Liu, Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210. 10749, 2022.
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In International Conference on Machine Learning, 2024. URL https: ///rx//vvvvi wwtp:/oggga/b/eee 1634.
12

---

Published as a conference paper at ICLR 2026
Sidi Lu, Tao Meng, and Nanyun Peng. Insnet: An efficient, flexible, and performant insertion based text generation model. Advances in Neural Information Processing Systems, 35:7011-7023, 2022.
Eran Malach. Auto-regressive next-token predictors are universal learners. arXiv preprint arXiv:2309.066 06979, 2023.
Eric Malmi, Sebastian Krause, Sascha Rothe, Daniil Mirylenka, and Aliaksei Severyn. Encode, tag, realize: High-precision text editing, arXiv preprint arXiv: (0div::909.0//8800 187, 2019.
William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. International Conference on Learning Representations, 2024.
William Merrill and Ashish Sabharwal. Exact expressive power of transformers with padding. arXiv preprint 2555:2505.18444 2025.
William Merrill, Ashish Sabharwal, and Noah Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843-856, 2022.
Vaishnavh Nagarajan, Chen Henry Wu, Charles Ding, and Aditi Raghunathan. Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction. arXiv preprint arXiv:2504. 15266, 2025.
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, 2025.
Gheorghe Päun. On the splicing operation. Discrete Applied Mathematics, 70(1):57-79, 1996.
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, 2025.
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. Improving language understanding by generative pre-training. 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
David Hill Robinson. Parallel algorithms for group word problems. University of California, San Diego, 1993.
Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Mariano Marroquin, Justin Chiu, Alexander M Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024. URL https: http::///pppeeeeeeeeeem wtt.://wwwwe//oouuueeeeee wow.moionmmmmuuaaaaa d=LAAuAA4AAAA...
Subham Sekhar Sahoo, Justin Deschenaux, Aaron Gokaslan, Guanghan Wang, Justin Chiu, and Volodymyr Kuleshov. The diffusion duality. In International Conference on Machine Learning, 2025. URL https: arxiv. .ivivviv org/ abs 22506.10822
Kulin Shah, Nishanth Dikkala, Xin Wang, and Rina Panigrahy. Causal language modeling can elicit search and reasoning capabilities on logic puzzles. Advances in Neural Information Processing Systems, 37:56674-5670.. 2024.
Claude E Shannon. Prediction and entropy of printed english. Bell system technical journal, 30(1): 50-64, 1951.
Jiaxin Shi, Kehang Han, Zhe Wang, Arnad Doucet, and Michalis K. Titsias. Simplified and generalized masked diffusion for discrete data. In Advances in Neural Information Processing Systems, volume 37, 2024.
Jascha Sohl-Dickstein. Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. International conference on machine learning. pp. 2256-2265. pmlr, 2015.
13

---

Published as a conference paper at ICLR 2026
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint 10KV::20111.33566, 2020.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. Insertion transformer: Flexible sequence generation via insertion operations. In International Conference on Machine Learning, pp. 5976-5995. PMLR, 2019.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543-561, 2024.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffiusion solvers for combinatorial optimization. Advances in neural information processing systems, 36:3706-3777 37316,371,2220 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
Dimitri von Rütte, Janis Fluri, Yuhui Ding, Antonio Orvieto, Bernhard Schölkopf, and Thomas Hofmann. Generalized interpolating discrete diffusion. arXiv preprint arXiv:2503.04482. 2025.
Dimitri Rütte, Janis Fluri, Yuhui Ding, Antonio Orvieto, Bernhard Schölkopf, and Thomas Hofmann. Generalized interpolating discrete diffusion, 2025.
Guanghan Wang, Yair Schiff, Subham Sekhar Sahoo, and Volodymyr Kuleshov. Remasking discrete diffusion models with inference-time scaling. arXiv preprint arXiv:2503.00307, 2025.
Hanchen Wang, Tianfan Fu, Yuanqi Du, Wenhao Gao, Kexin Huang, Ziming Liu, Payal Chandak, Shengchao Liu, Peter Van Katwyk, Andreea Deac, et al. Scientific discovery in the age of artificial intelligence. Nature, 620(7972):47--0, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. offin-off-houghh prompting elicits reasoning in large language models. Advances in neural information processing systems, 25:24824-24837, 2022.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Conference on Machine Learning. pp. 11080-11090. PMLR, 2021.
Sean Welleck, Kianté Bramtley, Hal Daumé lii, and Kyunghyun Cho. Non non-monotonic sequential text generation. In International Conference on Machine Learning, pp. 672666626.. PMLR, 2019.
Zirui Wu, Lin Zheng, Zhihui Xie, Jiacheng Ye, Jiahui Gao, Yansong Feng, Zhenguo Li, Victoria W., Guorui Zhou, and Lingpeng Kong. Dreamon: Diffusion language models for code infilling beyond fixed-size canvas, 2025. URL https:/ /hwunlp github. htthbbi.///oogg///2/0 2005 eremonn/. Blog post.
Shuchen Xue, Tianyu Xie, Tianyang Hu, Zijin Feng. Jiacheng Sun, Kenji Kawaguchi, Zhenguo Li, and Zhi-Ming Ma. Any-order gpt as masked diffusion model: Decoupling formulation and architecture. arXiv preprint arXiv:2506. 19935, 2025.
Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. arXiv preprint arXiv:2404.04533 043933, 2024.
Chenxiao Yang, Nathan Srebro, David McAllester, and Zhiyuan Li. Pencil: Long thoughts with short memory, arXiv preprint 2XXx:22503.14337 2025.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. Advances in neural information processing systems, 32, 2019.
14

---

Published as a conference paper at ICLR 2026
Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and Lingpeng Kong. Dream 7b: Diffusion large language models. arXiv preprint 15887 2025.
Hanlin Zhu, Shibo Hao, Zhiting Hu, Jiantao Jiao, Stuart Russell, and Yuandong Tian. Reasoning by superposition: A theoretical perspective on chain of continuous thought. arXiv preprint 2rXiv:2505.12514 2025.
15

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
Preliminary
3 A Theory of Masked Diffusion
3.1 Power of Parallelism
3.2 (Un)Scalabilityy to Hard Tasks
3.3 (Limited) Power of Any-Order Generation
4
Any-Process Generation
4.1
An Instantiation with unmask, remask, insert, and delete Operations
The Power of Any-Process Generation
5.1
Universally Efficient Computation
5.2
Structural Generation: Examples in Coding and Science
5.3
Learning and OOD Generalization
5.4
Hardness of Being Simulated
10
6
Conclusion
10
A Related Work
18
Background: Masked Diffusion Model
18
C Methodological Details
19
C.I Model Architecture
19
C.2 Self-Supervised Training
19
C,3 Supervised Training
20
C.4 Inference-Time Algorithm
22
Implementation Details
22
Parallel Random Access Machine
22
E.1 Definition and Execution Process of Word-RAM
23
E,2 Extension CREW PRAM
25
F Encoder Transformer Architecture
27
G Key Tool: Encoder Full-Access Sequence Processing (E-FASP)
28
G.I Definition of E -FFSP
29
G.2 Equivalence with Encoder Transformer
30
G.3 Two Variants of E-FASP
30
16

---

Published as a conference paper at ICLR 2026
G.4 Original Supported Operators
31
G.5 Additional Operators and Justifications
32
H Proof of Theorem 1
33
I Proof of Theorem 2
37
J Proof of Theorem 3
38
K Proof of Theorem 4
39
L Proof of Theorem 5
44
M Proof of Theorem
45
Experiment: Sudoku Puzzle
47
Experiment: Graph Generation
52
Experiment: Parity
53
17

---

Published as a conference paper at ICLR 2026
A RELATED WORK
Masked diffusion models (Hoogeboom et al., 2021; Austin et al., 2021; Lou et al., 2024; Sahoo et al., 2024; Shi et al., 2024) extend continuous diffusion models (Sohl-Dickstein al., 2015; Ho et al., 2020; Song et al., 2020) to discrete data. Early work applied these models to specialized domains such as graph generation (Vignac et al., 2022; Sun & Yang, 2023), protein design (Gruver al., 2023), and drug discovery (Lee et al., 2025), where non-sequential generation provides natural advantages. The field has evolved with recent commercial-scale language models like Gemini Diffusion (DeepMind. 2025) and Mercury (Labs et al., 2025), which demonstrate competitive performance on language generation, reasoning, and coding tasks. This suggests that MDMs can serve as viable alternatives to the autoregressive models that currently dominate LLMs. Against this background, this paper investigates the fundamental computational differences between generation paradigms and explores whether more powerful generation methods exist.
Several works have explored extensions to standard MDM through mechanisms that enable rewriting and editing (von Rütte et al., 2025; Wang al., 2025; Peng et al., 2025; Havasi et al., 2025; Wu et al., 2025; Kim et al., 2025a), which relate to our any-process generation framework. Wang et al. (2025) introduces random remasking during inference, though this capability is not learned from data. Lou et al. (2024); von Rütte et al. (2025); Sahoo et al. (2025) propose adding uniform noise in the forward process rather than using masks, with models learning revert them in the backward process, but this approach generally underperforms since modifying tokens directly appears more difficult than unmasking. Peng al. (2025) introduces path planning to control generation, though the planner is not trained end-to-end with the base model. Concurrent with ours: Havasi et al. (2025) introduces edit operations to flow matching frameworks but faces similar limitations as uniform noise approaches; Kim et al. (2025a) and Kim et al. (2025b) introduce to insert tokens at any position and remask tokens, while Wu et al. (2025) proposes expansion and delete, but these capabilities per se are insufficient for handling hard reasoning tasks as discussed in $ 3.
Before MDM, there are also some earlier explorations of non-autoregressive generation processes. Insertion-based models such as the Insertion Transformer (Stern et al., 2019), InDIGO (Gu et al., 2019a), non- non-monotonic sequential text generation (Welleck et al., 201 9), the Levenshtein Trans- former (Gu et al., 2019b), and InsNet (Lu et al., 2022) generate text by repeatedly inserting (and sometimes deleting) tokens at arbitrary positions, while XLNet (Yang et al., 2019) generalizes autore- gressive pretraining random permutations of the factorization order. LaserTagger (Malmi et al., 2019) and Mask-Predict (Ghazvininejad et al., 2019) formulate generation as iteratively predicting edit tags or filling masks in parallel. These methods demonstrate that alternative generation orders and local edits can bring empirical benefits on specific tasks, but most of them are defined based on particular architectures and decoding heuristics. contrast, this work provides unified formalization that subsumes insertion, deletion, and (re (re)masking operations as special cases, and the first systematic analysis of their computational power with comparison to ARM and MDM.
B BACKGROUND: MASKED DIFFUSION MODEL
We introduce the preliminaries of diffusion language models or masked diffusion models (MDM), following the notation established in $ 2. Let Σ = Σ U (M) be the extended vocabulary where M the mask special token. Consider sequences x, = (are, T4,2, ,t.5) E ES indexed by time the number of decoding steps, Xg (M) 5 is
t E [T), where S is the maximum context length, the fully masked sequence and XT E Σ is the target clean sequence.
Forward Noising Process The forward noising process constructs training data by generating noisy versions x, from clean sequences xy. Unlike the discrete inference steps in $ 2, training uses continuous time ł E [o, T] with larger t denoting later denoising steps. MDM employs the absorbing mask kernel (Austin et al., 2021) where the signal ratio a, t/TT represents the marginal probability that a token remains unmasked. Since a, increases monotonically with t (i.e., a, < ar for < t), later timesteps preserve more original tokens, consistent with our convention where L is fully masked and t = T is clean. At each position i, tokens either stay unchanged or become M, and once masked, they "absorb" into this state. The marginal distribution is:
q IT,)) Cat arerr. + (1 (1aar)enn ax)em)
(5)
18

---

Published as a conference paper at ICLR 2026
where e, denotes the one-hot vector for token Σ. To obtain noised sequence x2 from xy, compute the masking probability - a and mask each position independently with this probability.
Training Objective The reverse process aims recover Xy from Xo. MDM parameterizes po(xT x2 t) to predict the clean data directly (but as mentioned in $ 2, many recent large-scale MDMs omit explicit timestep embeddings). For the absorbing mask kernel, the true posterior g(xs Xe, Xy) for 8 < & has an analytical form. For each position i:
Cat Ox.,)): (1-a, Jou (a; Jerr.
if Ft.i + M
g( a Te,s FT,3)
(6)
Cat (za,i
if Fe. M
a-a,
This means that, if position i is masked at time it remains unchanged time if position i is masked at time t, it transitions probabilistically between the original token and mask. The training objective is derived from the variational lower bound. For the absorbing mask kernel, simplifies to:
(Cr (0 x.r ((x
1
Σ i:
log Po (o xx,
(7)
Mi m1,i MY
The loss computed only on masked positions and averaged over the number of masked tokens, making this equivalent to conditional masked language modeling with proper normalization. Here, t sampled uniformly from the continuous interval T] during training, XT sampled from the data distribution, and X, is obtained by applying the forward noising process.
C METHODOLOGICAL DETAILS
C.I MODEL ARCHITECTURE
As described in 4, AP-MDM extends standard MDM with three additional capabilities: remask (rewrite via remasking), insert (insert masks), and delete (remove redundant masks). In principle, these capabilities be implemented using shared encoder-only Transformer backbone with three additional linear heads, adding minimal computational overhead.
Architecture Following Equation (4), AP-MDM uses four prediction heads on top of shared encoder-only Transformer backbone. Given the hidden representation h, E I for position i, the heads output logits and probabilities:
(Vt, x₂) = softmax Wi + by),
Wo E F (unmask)
(8)
[ = a (W (,,,,.. + bR),
W E Bdx1
(remask)
(9)
, [2] (W/ hh, br), W, mdd
(insert)
(10)
[3] = a (W ph:;; +b),, Wp E Rxx1
(delete)
(11)
where the unmask head outputs a probability distribution (J predicting tokens at masked positions, while the three control signal heads output binary probabilities
x,) over the vocabulary for
for the corresponding operations. During inference, tokens are obtained via ft. = arg max po (- xx)
and control signals are obtained by thresholding.
C.2 SELF-SUPERVISED TRAINING
In principle, one can design specialized loss functions corresponding to each operation, alongside the standard unmasking loss from MDM, by constructing self-supervised signals from the inherent structure of text data through augmentation strategies.
Unmasking Loss The unmasking loss would follow standard MDM training described in Appendix B. For each training sample Xy, one can sample ~ (0, and apply the forward masking process with signal ratio a; t/TT to create x,:
IT.
with probability 0z
Ft,i =
(12)
M
with probability -
19

---

Published as a conference paper at ICLR 2026
The model would learn to predict original tokens masked positions with time weighting:
XT
m4 log (TT,
(-
Xx)
Cummask =
Et,xr x+
(13)
Σ,
m
where my = 1 position i valid (according to attention mask), otherwise.
Remasking Loss The remasking loss could train the model to identify incorrect tokens that should be remasked. For each sample Xy, one can sample ~ (0, 7) and create a corrupted sequence X using batch-internal shuffling (which effectively samples from the empirical token distribution rather than biased uniform distribution):
TT₁
with probability Oz
Te.i
(14)
shuffled token
with probability 1- Cte
The remasking labels Cr.a [1] | Er,il and the loss uses binary cross-entropy:
Cremusk
Br Bi,,y,
m; B
(15)
Σ, m
where m; indicates valid positions and BCE denotes binary cross-entropy with logits.
Insert Loss The insert loss could teach the model identify positions where additional content is needed. For each sample Xy, one can sample deletion probability 8 ~ 2/(0, 1) and generate deletion indicators for each position i. One would create the deflated sequence by removing tokens at randomly selected positions. The insert labels would be c = for positions ý that remain in x where the next position was deleted, otherwise:
Lissert
E,,xr,
E, m3 Σ my BBC)(BCEEtt,,, Ct,, [2])
(16)
where my indicates valid positions in the deflated sequence.
Delete Loss The delete loss could train the model distinguish between necessary and redundant mask tokens. One can use two-step masking process: first apply standard MDM masking with ar = t/T to create Xbases then sample insertion probability 7 (00 1) to insert additional M tokens at randomly selected positions. The delete labels would distinguish mask origins:
{1
if ut,; M and inserted in step 2
c
(17)
otherwise
The loss uses binary cross-entropy:
Laelete Ex
mn- BBCCo(loogit, D.A. ct,+
(18)
Σx m.
where my indicates valid positions in the contracted sequence.
Combined Training Objective In principle, an AP-MDM training objective could balance all four capabilities:
LAP-MDM = Cunmask + Xp + A,Cinsert + Cd
(19)
where X,, Aoo Ad are hyperparameters controlling the relative importance of each operation with default value 1.
C.3 SUPERVISED TRAINING
In addition to the euf-suueeeeiee training approach described in & C.2, AP-MDM can also be trained with explicit supervision when cnte-trranition data is available. This applies to scenarios where have access to the underlying generation process. can also be combined with the self-supervised approach in C.2 for hybrid training, e.g. self-supervised in pretraining and supervised in finetuning.
20

---

Published as a conference paper at ICLR 2026
Algorithm Any-Process Generation with unmask, remask, insert, and delete Operations
Require: Trained model fa. input prompt x
Ensure: Generated sequence Xínal
1: x
Initialize with input prompt
2: t ++0
3: while stopping criterion not met do
4: (x, C+) < [x()))
D Model forward pass
5:
Z₁
<-
Initialize temporary sequence
6:
for 1 X do
7:
if cr = and _t,
M then
delete operation >> Skip this position
8:
continue
9:
end if
10:
Determine token value: Remask >> Unmask > Keep
oa [1] then
remask operation
12:
Append M to
13:
else Øt, = then
b unmask operation
14:
Append yr to
15:
else
> Keep unchanged
16:
Append 2τ, to end
17:
18:
19:
ca (2 = 1 then
D. insert operation
Append M to z
21: end if
end for
23:
X(+1 f
24: 1 1+1+1
25:
end while
26:
return X
Data Format Each training sample consists of state-transition tuple (xx, ,c') where:
X Sh: current state (potentially containing M tokens)
y" Ixal; target tokens for each position
c² = (ci..... (xx)) where of E = {0, 1) ground-truth control signals
Training Objective Given the state-transition data, the model learns predict both the target tokens and control signals. The training objective consists of four components:
For positions where Tbe M and yf * M. predict the target token:
uumask
1
Σ
log Po xxx)
(20)
Ki Ø3,4
M. ot + MJ
For all valid positions, predict the control signals:
xx
m; BCE cf
(21)
Σ,
1
sup Insert
m; BCE (2(2))
(22)
Σ,
xk
1
delete
E,
m: BCE p. (3))
(23)
1=1
21

---

Published as a conference paper at ICLR 2026
where m, indicates valid positions and BCE denotes binary cross-entropy with logits.
Combined Objective:
CRuP AP-MDM
Suup unmaskk
+
Xy Feeaskk
+
X insert
Xa delete
(24)
C.4 INFERENCE- TIME ALGORITHM
As described in 3 4, AP-MDM generation follows an iterative process formulated as X g(fo (xx)). We provide the complete inference-time sampling algorithm that implements the transition function g following Equation (4).
The algorithm implements the transition function y(x,, Ct) as defined in Equation (4). Thresholds T,, T. Ta control when operations are applied (default value 0.5 for all). The algorithm supports variable-length generation through dynamic insertion and deletion, and terminates when a stopping criterion met (e.g., sequence convergence, generation of special tokens, or reaching maximum iteration limit).
D IMPLEMENTATION DETAILS
We provide implementation details for the experiments described in the main paper. All models are built on encoder-only Transformer architecture as described in & F, with task-specific configurations detailed below.
Model Architecture All models are based on encoder-only Transformer architecture with rotary positional embeddings (RoPE). For AP-MDM, we add three binary classification heads (remask, insert, delete) on top of the standard unmask head. We use no timestep embedding and set time conditioning to zero during supervised training. For Sudoku, we use 6 layers, 4 attention heads, hidden dimension d 256, feed-forward dimension 4d 1024, maximum sequence length 400, vocabulary size 31. For Parity, we use layer, attention head, hidden dimension d' = 4, feed- -orward dimension 4d 16, maximum sequence length 3, vocabulary size with approximately 200 total parameters. For Graph, we use layers, 4 attention heads, hidden dimension d = 256, feed-forward dimension 4d 1024, maximum sequence length set accommodate graphs of varying sizes, vocabulary size 55; the same configuration is used for the ARM baseline.
Training Data Generation For supervised training as described in $ C.3, training data consists of state-transition tuples (Xk.y", ","" generated by simulating the natural solving or generation algorithms for each task. Starting from ground-truth target solutions, we execute task-specific algorithms and record the intermediate computation states each step. For each state, we capture the current sequence X (with unknown or unfilled positions represented as M), the target values y to be revealed, and the control decisions indicating which operations (unmask, remask, insert, delete) should be applied. Concrete examples of data generation for Sudoku, Parity, and Graph tasks are provided in & N, $ P, and & O, respectively.
Training Details
We train all models using AdamW optimizer with learning rate 10-4. (31,32)
(0.9, 0.999), weight decay 0.01, and batch size 256. Learning rate follows a constant schedule with 250 warmup steps. We mixed precision training (bfloat16) with gradient clipping 1.0. Loss weights are set to A = A A = 1.0 by default. Models are trained for up to IM steps or until convergence. For Graph generation,
use 100K graph instances for training both AP-MDM and the ARM baseline. For Parity, we use only 4 training samples for AP-MDM, while the ARM baseline is trained with up to 10K instances.
E PARALLEL RANDOM ACCESS MACHINE
The Random Access Machine (RAM) (Arora & Barak, 2009) serves as the foundational theoretical model for sequential computation, featuring single processor that access any memory location in unit time regardless of address heitress--ennee "random access". along with a finite set of registers and basic arithmetic/logical operations. This contrasts with models like Turing machines where memory
22

---

Published as a conference paper at ICLR 2026
access is sequential. The RAM's key strength lies in its realistic abstraction of modern computers: it captures the essential computational primitives (arithmetic, memory access, conditional branching) while abstracting away hardware details, making it ideal for algorithm analysis.
The Parallel Random Access Machine (PRAM) (Fortune & Wyllie, 1978; JáJá, 1992) extends this familiar RAM model parallel computation by allowing P(n) processors to operate synchronously on shared memory with (log r:)-bit word size. Each processor in PRAM maintains its own program counter and unique identifier, enabling conditional branching and coordinated computation. The model operates in discrete synchronous time steps where all active processors execute simultaneously, inheriting RAM's unit-cost random access property while adding the complexity of concurrent memory operations.
PRAM Variants PRAM has several variants, which differ in their memory access discipline, forming hierarchy with precise complexity relationships. Let EREW, CREW, CRCW-Common. CRCW-Arbitred and CRCW- denote the classes of problems solvable in polynomial parallel time with polynomially many processors under each model, listed in order of increasing expressivity:
EREW (Exclusive Read, Exclusive Write): No concurrent access to any memory cell. Most restrictive but captures essential parallelism.
CREW (Concurrent Read, Exclusive Write): Multiple processors may read the same cell simulta- neously. Enables broadcast in (1) time vs. O n) in EREW.
CRCW-Common: Concurrent writes allowed only if all writers agree on the value. Boolean OR computable in (1) time.
CRCW-Arbitrary: Any concurrent writer may succeed; the choice is made arbitrarily (often modeled random selection).
CRCW-Priority: Concurrent writes resolved by processor priority with various schemes (e.g.. minimum/maxiimm index, sum of conflicting values).
Crucially, any algorithm in stronger model can be simulated in weaker model with at most Oloogn) parallel time overhead (JáJá, 1992). This polylogarithmic separation appears in basic primitives, broadcast requires O(log n) rounds in EREW but ((1) in CREW. yet the models remain polynomially equivalent for most papllexityytheoeettte purposes. We adopt the CREW model throughout this paper, where different processors are not allowed to write the same memory cell simultaneously.
PRAM, as idealized abstraction of shared-memory multiprocessor systems, enables precise analysis of parallel algorithms and gives rise to parallel complexity classes such as NC (Arora & Barak, 2009) (problems solvable in polylogarithmic parallel time using polynomially many processors). For example, PRAM can simulate algorithms on trees, linear arrays, meshes, and hypercubes without loss of parallel time, while reverse simulation costs at most (log 2 P(n)) overhead; Boolean circuits of depth D can be simulated on CREW in O(D) time, making PRAM a natural model for measuring parallel time complexity in theory.
Below, we provide a more formal definition that will be used in proofs.
E. DEFINITION AND EXECUTION PROCESS OF WORD-RAM
We formalize the standard Word-RAM that matches single-processor PRAM (i.e., P(n) = 1). Throughout, let the input length be n and fix the word size w(n) O(logn).
Word Size, Universe, and Addresses. Let the word universe be U = I..., arithmetic modulo 2 (two's-complel s-complement semantics). The address space is A 1 S(n) 11 for some S(n) < 911) Memory is mapping M A + U, zero-initialized.
2"d -1} with
1}
"The (log n) bit word size choice ensures that pointer arithmetic, indexing, and basic integer operations on polynomially bounded values are unit-time, matching the standard RAM assumptions and avoiding artificial speedups due unrealistically wide words.
23

---

Published as a conference paper at ICLR 2026
Let a(n) [log2 [nn]] denote the address width. We adopt the transdichotomous condition:
((n) max[[log; S(n)1. [log2 P(n)1} and
w(n) (logn).
(25)
This ensures every address and processor ID fits in one word, enabling well-typed register-indirect addressing and processor identification.
Instruction Set and Semanties. The machine operates with register names Reg {0, 1..... (for constant k), register file R E W immediate constants Imm C E (a fixed finite set independent of n and w), and label identifiers Lab for jump targets." We assume constant-size register file with |Reg] 2 2 in the proof (any constant 2 suffices to constant factors). Programs define partial label table addr: Lab (O..... f mapping each declared label its instruction index (injective).
The instruction alphabet Instr consists of the following parameterized forms (r, E Reg. E Imm, Lab):
Instr LOAD r; [s], STORE [s]. v, LOADI r, c}
U ADD r, SUB r, AND r, XOR r; SHL T; SHR r, 8
U BRZ r, L, JMP L, HALT }.
Unbracketed registers r, a denote their word values R,, R2 U. The bracketed form [s] denotes register-indirect addressing: LOAD [s] reads M[R.] into R,, and STORE [s), writes R to M MR... Bracketed operands are only allowed in LOAD/STORE; nested or arithmetic addressing (e.g.. [[s]]. (r+c) is not part of this ISA. If Rt & A, execution traps. Immediates are loaded as mod 2
The semanties of the instructions are as follows. We write a - for one execution step. Unless jump changes it, set pc pe + 1 where pc .., {} U {HALT} is the program counter. Let tb and A denote bitwise XOR and AND; let < and >> denote logical shifts; all arithmetic is modulo 2".
LOAD [s]: + Rg; Rr + M(a).
STORE [s], r: Rgi M t Ry.
LOADI r, C: R2 +- e modd n
ADD r; / SUB r; R2 (R, + R.) mod 2
AND s/ XOR r, 8: R, t- R2 A Rs R, t- Rr + R.
SHL r, SHR r, h t- R2 mod w; SHL: R2 (Rr RR h) mod 2"; SHR: R + R
(logical right shift, zero fill).
BRZ r, L: If R2 0 then pc addr(L.) else (no change to pe beyond +1).
JMP L: pc + aL)r(L..
pc HALT and execution stops.
Intuitively, LOAD and STORE handle memory access through register-indirect addressing, LOADI loads immediate constants, ADD/SUB perform modular arithmetic, AND/XOR enable bitwise opera- tions, SHL/SHR provide bit shifts. BRZ (branch zero) enables conditional branching, JMP provides unconditional jumps, and HALT terminates execution.
Programs and Configurations. A program is a pair P (Jo...., J,, addr) with I, E Instr and a partial label table addr Lab (0....,f) {} mapping each declared label to its instruction index (injective). The program is well formed if whenever some I; equals JMP L or BRZ r. L, then dom dom(addr), Code immutable during execution and independent of (and thus the RAM model considered here is uniform). A configuration is a (pc. R. M) where pc (O...., E} U [HALT) the program counter, R E U is the register file, and M A
memory. Input occupies
M 1]; output is read from designated location upon termination.
Initialization. Given an input instance of length n, initialization proceeds as follows:
'A label human-readable name for program location (instruction index) serving jump/branch target.
24

---

Published as a conference paper at ICLR 2026
1. Build the label table addr from the loaded code and check well-fommedness (every label operand the code must appear exactly once as a declared label).
Zero-initialize memory M and write the input into designated block (e.g., M - 1I) using the agreed-upon encoding.
3. Set all registers to zero: R2 + 0 for i E (o....,k]. Set the program counter to the first instruction: pc t 0.
The choice w 2 [log2 [Tn)] ensures that register-indirect addressing is well-typed: a bracketed operand [s] uses RG as an address in A.
Execution Cycle. While pe # HALT and trap occurs, the machine advances in discrete steps. Each successful step costs one time unit. Let 4pe denote the instruction at index pc. Each step follows the felch-decode--xeeuuee-Cooo
cycle:
Fetch: Read the current instruction + Ipe. pf & (o...., C}. the run is invalid and we define this as a trap.
2. Decode and read operands: Parse the opcode and operands of / without changing the machine state. Unbracketed registers r, s denote their current word values Ry, Rs E (used as data). A bracketed operand [s] denotes the candidate address + R2. An immediate Imm is interpreted as с mod 2 label L resolves to addr(L) (guaranteed by well-formedness). No writes occur in this phase.
3. Execute: Apply the instruction semantics of to compute finite write-ser W (register and/or memory locations with their new values) and the next program counter pe For memory- referencing instructions, a bracketed operand [s] is valid only if R. E A: otherwise trap occurs. By default pC = pc + 1, except for jumpsbraacchss/alling which set it to addr(L) (L) (or HALT).
4. Commit (writeback): Atomically apply the writes in W to (R, M) and then set pc <- pCnext Atomicity means all effects of the step become visible only the end of the step.
Cost and continuation: If no trap occurred, charge one unit of time for this step and proceed to the next; otherwise the run aborts (abnormal termination), and only successfully committed steps are counted.
Termination and Complexity. Execution halts when pc HALT. The algorithm's 's output is read from the designated output location(s) in memory (or registers) as specified by the program. Under the assumptions above and for well-formed programs with legal memory accesses, the step relation is deterministic and yields a unique next state at each iteration. The time complexity of an algorithm is the number of executed instructions before halting. A trap aborts the run immediately (abnormal termination); only successfully committed steps are counted in time.
The RAM model defined here is polynomially equivalent bit-complexity RAM (log n) factor separates their running times) and to richer word-RAMs that add WUL/DIV/POPONT// (whose presence typically improves only by constant or log log n factors).
E.2 EXTENSION TO CREW PRAM
We extend the Word-RAM defined above parallel machine with processor-budget function P N + N (typically P(n) < (1)). All word-size/address- widhh assumptions, the instruction alphabet Instr, the immediate-set restriction, and the single-processor instruction semantics are exactly in the WoRd-RAM subsection.
Processors and Shared State. Processors are indexed by E (0. P(n) - -1). Each processor has its own program counter and register file; memory is shared:
Σ = ((pop..... PPr(()))))
(R² (R"...,,PPCC) R,..),R())--1) M).
where pc; E {O..... .,, E} U (HALT} and R = ...)..,))))) E U++1 All processors run the same program P (To,..., Te, addr).
25

---

Published as a conference paper at ICLR 2026
Algorithm 2 Single-Proceess Execution (Word-RAM semantics with PID init)
Note. In PRAM, STORE generates pending write committed at the end of the round under the CREW rule. In the single-processor case, the store can applied immediately.
Require: Program p = (Jg...., ........,, Te. addr), shared memory M : AA U, word size w, processor id pid, processor budget P(n) (optional)
1: Init: pc < 0: ] <- for all j; R[0] t pid: optional: R(1] +- P(n) mod 2
2: while pe o HALT do
3:
+ Ipc
D fetch
4:
PCnext + pc +
default fall-through decode
5:
if is LOAD [s] then
6:
<- R[s)
7:
if a É A then
8:
trap
9:
end if
10:
R[[r] +- MMaa
P execute
11:
else if / is STORE [s],r then
12:
<- R[s]
if a é A then
14:
trap
end if
16:
M [a] < R[r] >> in PRAM semantics, this is a write event to be committed this round
else if / is LOADI r, then
18:
R/r] + mod 2
else [ ADD r, then
20:
I[[r] +- (I[[r] + R((s) mod 2
21:
else if is SUB r, then
22:
R[r] + (R(r] R[s]) mod 2"
23:
else if is AND r, then
24:
R/r] 4- R[()] A R[s]
bitwise AND
25:
else T XOR r, then
26:
R(r] < R[r] ( R[s]
bitwise XOR
27:
else if is SHL r then
28:
4 R[(s] mod
29:
R[r] + (R[r] < h) mod n
else if I is SHR r, then
31:
x R[(s] mod
32:
R[r] 4- [2
logical right shift, zero-fill
33:
else if [ is BRZ L then
34:
R[r] then
35:
PCreat + addr(L)
36:
end
37:
else if is JMP L then PCnext & addr(L) L)) else if is HALT then
38:
39:
40:
PCnext + HALT
else
42:
trap end if
> unknown opcode or malformed operands
44:
pc < pCnext
commit PC; regs/memory updated in each branch above
45:
end while
Initialization (with Processor IDs). At /. = 0:
1. Build addr and check well-formedness (as in Word-RAM); zero-initialize M and write the input block.
2. For each {O,..., P(n) 1}. pc, and clear registers; then write processor-local identifiers: Ré and, if P(n) < 2w(n), optionally R P(n) mod 2#(n), All other R2 <- 0.
26

---

Published as a conference paper at ICLR 2026
These two words provided that processors can branch, partition work, and self-disable if unused.
Concurrent-Aceess Policy (CREW). Multiple processors may read the same address in the same round; writes must exclusive: if two or more writes target the same address in a round, the run traps (abnormal termination).
Round Semanties (Referencing the Word-RAM Step). Each active processor executes exactly one instruction using the single-processee Word-RAM step semantics; the only new aspects (i) simultaneous execution by many processors and (ii) end-of-round memory commit subject to the CREW policy. Execution proceeds in synchronous rounds
1.1.2... with state Σ, ((p))) (R")), M. In round f, each active processor with pcp E {o.....f) executes instruction ppct on its local snapshot (pc pel, R R and shared memory M After all processors compute their local effects, the round commits: register writebacks R + Ri (independently)) then memory writes to M under CREW constraints, finally program counter updates pe." po
Termination and Cost Measures. The parallel run terminates when ped = HALT for all é (or traps an invalid access/conflict). One round costs one unit of parallel time. The work is the total number of executed instructions (()) = E. K pet E [O,..., }. and the span is Too (n) (the critical-path length). For P(n) processors the Brent bound holds (JáJá, 1992):
(n)
(n))
+ Too (n).
P(n)
A singlc-processor run (P(n)= 1) coincides with the Word-RAM model.
Remarks (on P(n), Processor IDs, and Unused Processors). (1) Uniformity: the code P and the immediate set Imm are independent of n. only the hardware parameters w(n), S(n), and P(n) scale with input size. (2) Processor IDs: the values and P(n) are provided via initialization registers (R)
and optionally Ri) for branching and work partitioning; programs may copy/overwrite them. (3) Unused processors: if algorithm needs only m(n) S P(n) processors, each processor executes short self-filter based on (e.g., if i 2 m(n) then HALT), or computes its assigned block; processors with empty assignment halt in (()) rounds, which does not affect the asymptotic parallel time.
The algorithm for a single-processor PRAM shown Algorithm 2.
F ENCODER TRANSFORMER ARCHITECTURE
This section presents encoder-only Transformers, which form the backbone of MDM. We will first establish the sequence-wist extension operation, then define the core components, including bidirectional self-attention, multi-head mechanisms, and wee-ffoward layers, before assembling the complete architecture.
We consider encoder-only Transformer with H heads, L layers, hidden size d, and feed-forward width w. We will use the following notations: Function). For set B, let H(B) denote the set of all functions va such that for every sequence x = (#1...., In. E E* and every index E [n], the value (x, i) B is defined. We write this succinctly
Definition 4 Dosiition-Indxxe
Seq-to-Embeddun
(E*
(26)
and call this desition-indexee reg-to-embedding function. We also define Usen+ H(Rd) as the union of all such classes across real spaces of all output dimensions.
Definition (Canonical Extension Seq-to-Seq Function). Given a position-indexed seq-to- embedding function v E H(B), its canonical extension is defined as:
T: E² + B" where [+()) (xx i) EiE [[]]])
(27)
For elementwise functions g Rd + dd we define (R')' (R by [g(h..)) ghh)). which is special case where (h)m.,)) = gh; (ignoring cross pross-postiion context). When the arity is clear, we reuse the bar notation for both position-indexee and elementwise extensions.
27

---

Published as a conference paper at ICLR 2026
We now define the individual components of encoder Transformers:
Bidirectional Self-Attention. The key difference from decoder Transformers bidirectional attention, where each position can attend to all positions in the sequence. Let d,, be the head dimension. For Wo, WK, , Wy E id and Wo Rddxd, we define single-head attention on sequence embeddings him (Rd)a for any n E N
= Wohl: hg Wi Wich U/ = Wyh
(28)
(Aa(())))) = Wo Σ
(29)
5=1
with os, softmax ky (1)) 0 = (We, WK. Wv, Wo). Position i attends to all j E [n]
without causal restrictions. We use standard 1/ dh scaling.
Multi-Head Attention.
With OMHA -0(1) (0())....0)))
combine heads via summation:
MHA0 (h1m)); =
Σ g (him))
(30)
for any i E [n]. Note that this differs from practical implementations which concatenate heads with dimension d/Ht each, but maintains equivalent theoretical expressivity.
Feed-Forward and Projection. Let = drr. For Wi E Bxxd and W2 E Rdxw;
Fh) W2 (W
(31)
For output projection, PROJ, Idd + R 2- with PROJo = and RR E|xd We apply these via sequence-wise extension: FF and PROJ.
For AP-MDM as described in 4, besides the above heads for unmask, it would require three additional binary classification heads on top of the final layer: PROJR : Rd + IR for remask,
PROJ, E + IR for insert, and PROJ Rd R for delete operations, each followed by sigmoid activation. Therefore, PROJ, is a mapping from Rd to R
Embeddings. Define token embedding TE: Σ - IR and positional embedding PE N+ - Rd (which can be flexibly chosen and will be specified when used). Combined as TE + PE. We write TE, PE for their sequence- wise extensions when clear from context.
Residual Connections. The identity function Ida Rd + Rd is defined by Ida(x) T. A residual connection defined as f Ida, where Id, is the identity function.
Next, we assemble these components into the encoder transformer architecture:
Definition 6 (Encoder Transformer layer). An encoder layer is defined as:
EnH.FF (FFFF + Ida) (MHA6жии + Idda) (Rd) + (I2-)*
(32)
Definition (Encoder Transformer). With parameters 0 (OTE.OPE. (P the encoder transformer is:
EncØ PROJopROS
Fne (e /
(TEOTe -Poppp)
(33)
The model applies embeddings, then encoder layers, then position-wise projection to vocabulary logits. Output length equals input length
G KEY TOOL: ENCODER FULL-ACCESS SEQUENCE PROCESSING (E-FASP)
In this section, we develop Full-Access Sequence Processing for encoders (E- FASP), a programming language whose programs describe the construction process of seq-to-embedding functions that equivalent to those computed by encoder-only Transformers. This extends the FASP framework originally developed for decoder-only Transformers in Yang et al. (2025). Similar connections have also been established in Weiss et al. (2021); Yang & Chiang (2024).
E-FASP is the key technical tool that will be used prove Theorem 1, Theorem 3 and Theorem 4.
28

---

Published as a conference paper at ICLR 2026
G.1 DEFINITION OF E-FASP
Notations. Recall that in $ F, we defined the position position-indesn indexed seq-to-embeedee embedding function space H(B) as the set of all functions &o that map a sequence and a position index to an element in B:
+ (E", [D) -
(34)
That is, for every sequence x x= (T1,--.. In) ) E Σ- and every index E [n], we have (x, i) E B. We also define H UaeN+ (T())) as the union of all such classes across real spaces of all output dimensions. For any position-indexed function 1 E H(B), its canonical extension vi Σ 3* is
defined by (x)]; (x i) for E [|x]]. This allows convert position-indexed functions to sequence-to-sequeeee functions when needed.
Also recall that PE N+ - Rd positional embedding, and additionally define TACT class of activation functions. We formally define E-FAPP as follows:
Definition (Encoder-FASP)). An E-FASP program is sequence of position-indexed seq-to- embedding functions .'...... thr constructed inductively. At each stept [T), the program maintains set of defineable ienttioninndxed seq-to-emet tegg-t-emmbdiingg functions Pe. and defines a new function by applying operators to functions in P.. We define the defineable functions at step E [T]
P. a (TE, {th (1sist-1)
(35)
where TE(x, - and PE(x, PE(1) are the loken and positional embedding functions respectively, viewed as Pnsition-indexee seq-to- seeg-lo--mbeddingg functions. th, at step L has to be defined by applying one of the following four primitive operators alreudy-defined fanctiins from P,:
1. Concatenation: For th v/ E Pe with vb E H(TR))) and v E H((R))), define
W, (vxx,, (Vlx E Rdi
(36)
where || denotes vector concatenation.
Linear Projection: For E Pe with vo H(R) and matrix W gd'xd, define
(W ( i) W (xx Rdd 3. Nonlinear Activation." For 1h P. with 3a E (( and TACT, define ( (x, i) o ( i))
(37)
(38)
4. Encoder Average-Hard Attention: For q, ((Rd. and v H(R") where q, k, Pt, define ahalq, k, (xx [Ai
Σ v(x,j)
(39)
jEn,
where A; arg ja(xx( (g(x, i), k(x, j)) and ties averaged uniformly. This attention can be seen as special case of standard softmax attention with temperature approaching 0 (Merrill et al., 2022).
Finally, when we want to use E-FASP to define a function mapping from sequence of tokens E* and a position index to a single token in E, can define 1b E HR and relurn arg max v(xx (the token corresponding to the largest logit at the position i).
We denote the set of all position-indexed seq-to-embedding functions defineable by E-FASP with position embedding PF and activation functions TACT E-FASP (PF; TACT), where PE can be either Bi PE or SEQ. The expressivity of E-FASP depends on the specific positional embedding and activation functions used.
Wee allow multi-variable activation functions like Gated ReLU (ReGLU), v. + x/g]+
'We could assume arbitrary order to break ties, but omit this for simplicity. In our examples always ensure the argmax is unique.
29

---

Published as a conference paper at ICLR 2026
G.2 EQUIVALENCE WITH ENCODER TRANSFORMER
We now establish the equivalence between E- E-FASP and encoder-only Transformers, and define the specific instantiation considered in the proof of this paper.
Definition 9 (Encoder Transformer Function Class), Let HeseTF(PE:TACT] be the class of seq-to- embedding functions that can be expressed by encoder-only Transformers of finite depth, where the positional embedding uses PE (either BiPE SEQ), feed-forward layers use activation func- tions from TACT, attention layers use average-hard attention as defined in Equation (39), and all intermediate computations use finite precision arttmeeicc.
It is straightforward to see that both variants are equivalent to their corresponding Transformer function classes:
Lemma 7 (Equivalence of E-FASP and Encoder Transformers). For any positional embedding PE E {BiPE, SEQ} and activation finncttioonuuncioonn class TACT, the following equivalence holds:
E E-FASPPPE; TACT] HLEnCTFPP::TACr)
(40)
Sketch. Sketch. Forward direction: Each E FASP primitive operator (concatenation, linear projec- tion, nonlinear activation, encoder attention) directly corresponds to operations in encoder Trans- formers. Concatenation involves merging multiple smaller Transformers into larger Transformer that produces the same output. Reverse direction: Any encoder Transformer can be expressed as an E-FASP program by decomposing each layer into primitive operations.
The detailed proof, including the treatment of closed operators and inductive construction, is invariant decoder encoder Transformers, and thus identical to Yang et al. (2025); we omit the details. L.
Intuitively, this equivalence holds because E-FASP programs capture the computational structure of encoder Transformers. Each step in an E-FASP program corresponds to defining a new seq-to- embedding function by applying primitive operators to previously defined functions, which mirrors how smaller Transformers are constructed into deeper and wider Transformer that produces the same output. The Transformer corresponding to the program is of depth (11) (given constant I') and embedding size (maxx[drp ), by construction in the proof of Lemma 7.
G.3 TWO VARIANTS OF E-FASP
Throughout this paper, we consider two variants of E-FASP based on different positional embeddings, both using the same activation functions.
Variant 1: Binary Positional Encoding We define E-FASP with binary positional embedding BiPE: N+ + {0, 1] [log, S(n));
BiPE(() binary representation of using [log2 S(n)] bits
(41)
This representation uses [log2 S(n)] bits to represent all possible positions within the maximum context length S(n), and aligns with the address representation in PRAM (g E) for efficient bitwise arithmetic operations.
Variant 2: Integer Positional Encoding We also define E-FASP with integer positional embed- ding SEQ N+ N+:
SEQ(1) =
(42)
This is the identity mapping over N+ that directly uses the position index as a scalar feature, as considered in the original decoder-only FASP framework (Yang et al., 2025).
Activation Functions Both variants use the same class of activation functions TACT = {ReGLU), where Gated ReLU (ReGLU) (Dauphin et al., 2017) is defined as ReGLU y) [y]
x max(y, 0) for E R. With Gated ReLU as the primitive activation, we can express ReLU and multiplication operations through the following identities:
ReLU(x) ReGLU(x, 1), x x ReGLU(x, ReGLU(Z,-1)
(43)
30

---

Published as a conference paper at ICLR 2026
Therefore, having ReGLU allows us express both ReLU and multiplication (reverse is also true), making both variants equivalent:
E-FASP BiPE; ReGLU] E FAFPPP BiPE: H++ x]
(44)
E- E-FASP (SE:: ReGLU] = EEFFAPP SEO; [SE;: H++ x]
(45)
where [+ and x are the ReLU and multiplication respectively.
G.4 ORIGINAL SUPPORTED OPERATORS
With the four primitive operators in R-FASP and the activation functions defined above, the follow- ing operators can be included in both variants E E-FASP BiPE; [+]+ x] and E E-FASP(SEQ) []+, x], adapted from the decoder version of FASP:
Arithmetic Operators
add(v/1, v/2) = 1 + 1/2 Element- addition
mi min 1/2) 1/1 1/2 Element-wise subtraction
mult (1 1/2) 1/ x g/2 Element-wise multiplication
max(111, 22 wlement-wise maximum
min(1/1, 42): Element-wise minimum
Boolean Operators For 11, 1/2 HL(0, 1)):
and(V/1, t/2) min(w/. v2): Logical AND
or(V1, 122 - - Logical OR
not (vb) = - vb Logical NOT
xor(vi, Logical XOR
Comparison Operators For vi, 1/2 E H(Z):
leq(V), 1/2) = [V/ ei + 1|+ [//2 1 ]+ Less than or equal
geq(t'1 v/2) leq(1/2 1/1 ): Greater than equal
eq(V1, 42) = leq(th, (h) A leq(V2, v))): Equality
1t(11, 4/2) leq(th, the 1): Less than
gt(V1, 122) = (t w1)) Greater than
Sequence Aggregation Operators
seq.max()):: Returns the maximum value across all positions in the sequence
seq.min(v):: Returns the minimum value across all positions in the sequence
seq_and(v)) seg.min(v):: Logical AND across all positions
seq.or(w) seq_max (V)): Logical OR across all positions
seq (ommm)): Sum of values across all positions (requires log positional embedding)
seq avg (v) E (b(1gg): Average across positions
Positional Operators
is.first(i) 1li 1]: Indicator for first position inv.seq = 1 1/n: Inverse of sequence length
is pos k(i) ji A::: Indicator for position k
31

---

Published as a conference paper at ICLR 2026
Control Flow Operators
if then el se( thmee (Paase) or i i (1/endd, Vinee 1Ptakee:: If-then-else conditional selection
Attention Variants
aha (q, k, v): Standard average- attention (encoder bidirectional)
rha(q, kt e): Righimost-hard attention (breaks ties by selecting rightmost position)
rightmost.exacttaateee k v): Rightmost exact match (returns default no exact match)
G.5
ADDITIONAL OPERATORS AND JUSTIFICATIONS
Next give the semantics of some additional operators used in the PRAM simulation programs and justify their closure the E-FASP framework.
BITWISE ARITHMETIC OPERATORS
These operators are defined the encoder-E FASP framework using activations {[+]+, x (equiv- alently ReGLU) and independent of the specific positional embedding choice. All inputs and outputs are position-ing indlxxdd req-to-embedding functions H({0, 1)")) where (x(x, i) E {0, 1]
encodes m-bit integer with LSB coordinate All arithmetic is modulo 2
Bitwise Addition.
Given 1/1, the E H(((0, 1 1)m"., write at position (x, t):
di (x, =: (a1, (a1...., am) (x, i) b (b1, ..... bm) 13
(46)
Bitwise addition defined as adding two m-bit integers modulo 2mm This can be constructed using the primitive operators (and other operators that are already defined) in Definition 8, which follows an approach similar to standard carry-lookahent and is a constant-depth, polylogarithmic-iith construction:
Define for k E [m] the local propagate/generate bits:
Pk ag @ by
az by ba 9k = ag by
ag
(47)
Let S. = 0 and S, = E Pe for j E [m] (computed by single linear layer). For S < m,
define the interval-all-ones gate:
Qj eqo ((S;-1 -S;) 1(i-1)
(48)
where eq (u) = 2 (iu - (k- 2)1 - 2/u k]+ + [uu - (k: + })++) equals at u = l and 0 at all other integers.
The carry into bit i is:
0,
i=
C, (1 11 ego (E
(49)
i2 2
The sum bits are
3 C. P: + C. - -2,,C.. We define:
bit_addm (vi, 2 i) s (s1 (s...... sm) [0,
(50)
Bitwise Subtraction. For 4/ E H( (0. 1) )m), define:
bit mi nusm (1h1, th2) bi add (wh, m2/2)
(51)
where - is bitwise NOT (elementwise 1 .) and "411" adds the constant vector e = (1,0...., via the same bit add,..
32

---

Published as a conference paper at ICLR 2026
Logical Shifts. Let v E 71{0, r)m and H(f0. At position (x, i), write (xx,t)
(01,..., 4m) and define the shift amount:
int(r)
Σ
2"
2"
Tr (0....,,)) m
(52)
r=1
For l: E [m], we define:
min(m,k-1)
[shift (eftm(6.7)4
Σ
equ(t) ak-s
(53)
win(m,m--))
siiht (bb (
Σ
eq.(t) ax+s
(54)
where out-of-range indices are treated as O, and (-) is the integer-equality gate realized by three ReLUs.
Complexity Analysis. All operators act locally at each position on H((0. 1) without cross- position communication, and are composed from E-FAS? primitives. Throughout m O(log n.).
The witness enumeration method for bitwise addition requires: (i) one linear layer for (p, 9) and prefix sums (Sy); (ii) one nonlinear layer for witnesses Qj,; (each uses 3 ReLUs) and products 9j gjQ5 (iii) linear aggregation and threshold for carries C;; (iv) local polynomial for 8; = Pt @ C.- This achieves constant depth (3-4 layers) and width O(m²) = O((lgg (polylogarithmic in n). Bitwise subtraction uses two's complement and reuses the same addition circuit with identical complexity bounds. Logical shifts compute the shift amount t and all candidate shifts in parallel, then use equality gates for selection, also achieving constant depth and (m²)) width.
All constructions use only 3-F FASP primitives (linear projections, ReLU/ReGLU activations, mul- tiplication). By the equivalence established in & G, these are realizable by constant-depth encoder Transformers.
Instruction Access Operations. This operator enables instruction fetching from memory by address lookup, which is essential for PRAM simulation.
get instruction i) == bin Bin(WRNSTR ite(is addr(x, +), bin(TT(xx.))) (x,, E {0, 1)"
(55)
where WINSTR _ _ is a learned linear transformation (MLP layPlayer) that maps address bits to instruction bits. This operator first extracts the address bits from address positions (even positions i 1) by converting their token embeddings to binary representations, then applies the instruction lookup transformation WINSTR to produce the corresponding instruction encoding. The PRAM instruction (LOAD, STORE, ADD, SUB, etc., defined in & B) is hardcoded into the parameters of W WINSTR during training, enabling the model to perform instruction fetching through learned Mnddess-to-innstreete mappings.
H PROOF OF THEOREM
Theorem 8 (MDM Simulation of PRAM, Formal). For any PRAM program P (Ta. ..., Te, addr) (with finite number of instructions f, and is uniform for all processors and input size n), that on input Xval U with corresponding address Xaddr E A that runs in T(n) parallel time using at most P(n) processors and outputs PRAMp (Xoddr Xval) E U per procedure described in & E, there exists a bijection $ U UUA- and a special token [SEP] E E, and MDM with constant depth and log(n) embedding size encoder-only Transformer, on input X = ((Z2i, Z2s41) [SEP]) E 22n+1 where Z2: @ Xaddtrs) and 22i+1 1 ((xmat)) padded to ((P(n) x T(n)) context length, outputs (PPRMM (xnddr, Xuat)) with ( decoding steps.
The proof demonstrates that AO-MDM can simulate any PRAM algorithm. The construction is based on E-FASP, the programming language we developed, whose definable programs are equivalent to
33

---

Published as a conference paper at ICLR 2026
encoder-only Transformer function class (see G). We prove Theorem 1 by: (1) defining the setup and imput format for PRAM simulation; (2) constructing an E-FASP program that simulates PRAM exccution in Algorithm 2.
the E-FASP [SQ;; H++ variant with integer positional encoding rather than the binary variant. This choice is crucial because MDM's context length can be exponentially large (e.g., for NP-hard problems), while PRAM's actual memory usage remains polynomial. Using log bits to represent positions would be insufficient when the context length n itself grows exponentially with the problem size, even though PRAM addresses can still be represented in log (()) bits. To avoid confusion between MDM's context length and PRAM's memory space, we use (MDM(N) to denote the maximum context length and reserve (m)) for PRAM's memory space.
Choice of Architecture / E-FASP Variant For this simulation,
Input Format The input that encodes the PRAM's initial memory state is sequence E 22n+2 of discrete tokens from the vocabulary E.
Let (log n) be the word width and recall from & that the address width [log2 S(n)] S (addresses fit within words). The sequence has length 2n + 2 = + 2n + where:
21 E Σ
(processor count token)
(56)
P21 E Σ
(address token) for ,....,
(57)
T24+1 E Σ
(data token) for i = ......7 n
(58)
22n+2 [SEP]
(separator token)
(59)
Through token embedding TE: E + Rd and subsequent linear projections, these discrete tokens mapped to their semantic bit representations:
TE(z1) - P(n) {0, 1)"
(60)
TE(x2) + addr; {0, 1]"h (address bits)
(61)
TE(2241) val, {0, 1 (data bits)
(62)
for = 1,..,, The [SEP] token serves separator with special meaning in the computation
trace, as detailed in the next subsection. Following the standard MDM notation from $ 2, the actual
input the MDM the padded sequence Xo (No,1, Fo. Smnss)))))) E E (amm(n) where EU (M]:
Jojj Tj for j = 1,... 2n + 2 To.j M for j 2n 3, ...... (MDM
(63)
(64)
We aim to show that there exists an encoder-only Transformer that, given the initial memory state of PRAM input, can output the exact same result as the PRAM algorithm after TMDM(n)) (()()) decoding steps. The Transformer will have constant depth and context length (SMDM(()) where (MDM(1) represents the MDM's context budget.
next provide an overview of the construction:
First, we state the representation of processor state and computation log tokens. We represent each processor's state and one round of computation using a fixed number of tokens: program counter (1 token), register file (5 tokens), and computation log (2 tokens), for a total of tokens per processor.
Processor State and Computation Log Representation:
Program Counter (PC): A single word encoding the current instruction address.
Register File: We maintain exactly 5 registers, each storing word. This provides sufficient computational capacity while keeping the representation tractable.
Computation Log: This log is populated only when executing STORE [s], instructions, recording the target address and stored value. For all other instructions, the log remains empty (represented by special tokens).
34

---

Published as a conference paper at ICLR 2026
The computation trace for one parallel round can be represented as:
[SEP] (PC1, Ri.1.............. R1,5, Addr1, Val1) (PC2, R2,1. R2,5, Addr2, Val2)
(65)
where [SEP] serves as a separator token to distinguish different computation rounds and there are total of P(n) independent processors. Each processor {l...., P(n)) contributes 8-tuple (PC,, R4,1, R4,2, R4,3, Ri,4, Ri,5, Addr, Val;) representing its program counter, five register values, and memory write operation (address and value). The trace thus contains exactly P(n) such 8-tules per parallel round.
Processor Assignment and Role Identification. The algorithm begins by determining whether the current position contains mask token (i.e. is (s_mask). If the position is mask token (Branch 1), the algorithm continues by computing the distance to the nearest preceding [SEP] token. If the position is not mask token (Branch 2), it indicates this position has already been unmasked (computation has already finished), and the algorithm returns the input token (or an all-zero vector) which will not be unmasked per definition of MDM B 2).
To identify the processor ID, we find the rightmost [SEP] token to the left of the current position (i.e. rightmost_scop sccpppsssssspppssss and compute the distance between them (i.e. distance.to -tspppp....p...... If this distance > 8 x P(n) (Branch 1.1), the position does not participate in the current computation round as it is not token that should be "unmmsseed" in this round, in this case, the algorithm returns a special embedding (an all-zero vector), which results in uniform distribution during prediction and smallest confidence, ensuring that the MDM will not select this position for unmasking; if the distance = 8 x P(n) + (Branch 1.2), this position return the embedding of [SEP], 1, preparing for the next computation round; otherwise if the distance participates in the computation of the current round.
P(n) + 1 (Branch 1.3), the position
For those positions participating in the current computation round. The corresponding processor ID (i.e. processor id) is obtained by right-shifting distancce to sep by 3 bits with zero- pero-padding on the left (since each processor corresponds to exactly tokens). The rightmost 3 bits represent the position within that processor (i.e. tiner_processorjide
Initialization of Processor State. We need to initialize the initial state of all processors at the beginning. This is determined by the current number of [SEP] tokens in the sequence. Specif- ically, when the current position is a mask token and there is exactly one [SEP] token (i.e. peg_suu(isssepp)
1) (Branch 3), we consider this the initialization state. All program counters are set to O, all registers are set to O, and all memory locations are set to 0.
Fetch Instruction and Execution (Main Loop). According to the processor and inner processor position, the algorithm fetches the instruction from the instruction memory (i.e. get. innttructiin), which hard-coded into the parameters of the model, and execute (using execute). Different instructions yields different exccution semanties, and subsequently different 8 token state. Finally, according to the inner processor id, the algorithm chooses what to return. The algorithm terminates when the PC of all processors are HALT.
We now formally construct an E-FASP program that simulates PRAM execution (the single- processor algorithm detailed in E). The semantics meanings and justifications of operators used in the program are summarized in & G. The only two global operators are seq sum and rightmoot__exe wttpooatteeeettttteeeeeeeee implementable by attention, otherwise all local operators imple- mentable by solylog-widthh constant-depth MLPs.
The context length of MDM used by this construction is (M) (n) P(n)), the decoding steps is TMDM( = (T)rr())), where (n))(n) is the parallel time complexity and P(n) the processor count. For the constructed Transformer, embedding size is log(n) and depth is constant.
Initialization
is_sep (TE embed ( [[SP]])
1s_mask = (TE == embed [MASX]))
init (seq_sun (is_sep) == 1)
Get the current and 1ast [SKP] position
35

---

Published as a conference paper at ICLR 2026
cur sep rightmost exact (1, is sep, dist_to_sep PE- cur_sep
pn sighttosst_xxee_matthll (1, is_first, TE) spanned_pn pn <<
participating in computation if (not is_mask) or (dist_to_sep spanned _nne return 0 if dist_to_sep = spanned_ on 1: return (ubed([SEE])
Skip positions
if is in_ini:: return
Iniiiaalzatiin
pid (dist_to_sep 1) >> 3
inner_id - (dist_to_sep - [:3]
if is init and inner id 1: return pid
if init and inner_id != 1: return
Read previcus round state
prev_scp rightmost_cxact m (is_sep and (PE cur_sep)) ) PE)
prev_pic_base prev_sep (pid <<
pos_PC prev_pid_base 0
PC rightmostteeact_naeeee (pos PE, TE)
pos R1 paseyppid_base
R1 righttmest__eect_mmtttee.. (pos R1, PE, TE)
pos_K2 - pree__ii__aaee
R2 tightnosss_sscct_mathh (pos_R2, PE, TE)
pos_k3 prev_pid_basee
R3 riigtmostt_exatt_attaa
R3, PE,
pos R4 prev_pid_base
R4 rightmostt_exatt_metee (pos_R4 PE, TE}
pos_R5 prcc_pid__basc_ 5
R5 rightmoost_xxeet_mtchh (pos_RS, PE, TE)
PC HALT_CODR. return
Fetch and execute instruction
Decode type, r, op_s, op_ label addr get_ int.innstuttio
# Source/ snaurcedeesinattion register
Rs (R1 if ep_s == 1 else
if op_s
else
R3 if op_s 3 clse
R4 if op_s = 4 else
R5 if ep_s == 5 else 0)
Rr
(R1 if op_r 1 else
B2 if op_r = 2 else
R3 if op_r = 3 else
R4 if op_r
4 else
if op_r
5 else 0)
Default effect
PC next
vR_aal Rr
writes_reg False
ADDR_out = # Slot 6: only STORE everwrites address (a <= w, use word
directly)
VAL_out
Slot 7: only STORE everwrites value
Address read it I I_pee == embed [LOAD])
ADDR KEYS (TE if is addr else 0)
36

---

Published as a conference paper at ICLR 2026
ADDR POSVAL (PE if is addr else
last last_addr_pos _oad = righttmstt_cxact_mteelllee (Rs, ADDR_KEYS, ADDR ADDV_POSVAL)
load_val = riggittstt_occcctcccccceceeeeeee
load + 1, PE, TE)
WR_val = load_val val
Per-instruction semantics
elif I_type = embed embed( : ADDR_out, Vut_out out Rs, Rr
elif I_type = embed (ILOAD( WR_val op_e
elif I_type embed ([SJk[[ WR_val (Rr RS)
embed( WR_val
R5)
elif _type
elif __tppe embed [AND]]] WR_val (Rr & RS)
elif I_type -- embed [XOR]]: WR_val (Rr Rs]
elff I type = embed ([SHL]) WR val = (Rr << Rs)
elff 1_type embed (ISHR) WR
Rs)
elff __type
embed [BR2]) and Rr 0: PC next Label_addr
olif I_typc = embed [JMP] ]) ): PC_next label_addr
elif I_typc = embed : PC_next BALT_CODE
Register writeback: only for (LOAD, LOADI, ADD, SUB, AND, XCR, SHL, SHR
writes_reg reg (T [ytppe -- embed [[LOAD])) or (I_type -- embed ( [[OAD]])] or
typtee == emped ([)DD])) (I [I_type == embed ( S []] or
type embed (IANDI)) (I type embed [XCR
type emped (ISHL))) or (I type embed ( [SRR
R1_next (WR_val if (writes_reg and op_r =- 1) else R1)
R2_next (WR_val if
(writes_reg and op_r == 2) else R2)
R3 next (WR_val if
(writes_reg and op_r 3) else R3)
R4 next (WR_val (writes_reg and op_r r 4) else R4)
R5 R5_next (WR_val if (writes_reg and ap_r = 5) else R5)
Return
of slots according to inner
if inner 0: return PC_next
elif inner_id 1: return R1_next
elif inner_id -- 2: return R2_next
elif inner_id 3: return R3_next
elif inner_id
return R4_next
elif inner
return R5 next
elif inner id = 6: return ADDR_cut
else: return VAL out
I PROOF OF THEOREM 2
The result stems from MDM's total amount of computation being bounded by S(n) in both total steps (T(m) < ((n) and per-step capacity (polynomial embedding size), preventing from solving problems requiring greater computational resources.
Fix an encoder-only MDM with context length (n) and T(n) decoding steps. Throughout we assume constant depth/heads and log-precision arithmetic with hidden width d = O(log(S(n)) + T(x))) (binary positional code), as in our setup. Particularly, at each decoding step the model re-encodes length-S(n)) sequence. A single forward pass is dominated by self-attention: for each position i we form a query in I&d and take dot products with all S(n) keys, then take the value-weighted sum.
Counting FLOPs, attention head costs
@(S(n)- S(n) d) (()(()² (5()) + T(n))),
(66)
and the multi head/multi-layer constants only change the leading constant. The position-wise MLP adds (SS(n) poly(d)) = (m)(m) polylog(S(n)) + T(n))) FLOPs and is lower order when (()) d. Thus one decoding step costs
Ō(S(n)²)
FLOPs.
(67)
37

---

Published as a conference paper at ICLR 2026
where Ö(-) suppresses polylog factors in S(n) + T(n). Over T(n) steps the total compute is ((S(m)²T(() In particular, when each step reveals least one token (or a constant number), we have T(n) I S(n), yielding the unified cubic bound (S)))))) Hence any problem that needs af ()()))) serial time cannot be solved by MDM in the (S(n),T(m) regime stated.
J PROOF OF THEOREM 3
Recall Definition 3, we defined Masked-ARN. as an autoregressive model with encoder-only Trans- former architecture that pads the input sequence with mask tokens the maximum context length, which is also equivalent to MDM with a fixed order (left-to-right) generation and generating one token time. Consider an AO-MDM with input format (21,,..,, Fn.) followed by special separator token [SEP] at position n + 1.
AO-MDM Intermediate State: At any intermediate generation step, the AO-MDM state can be represented (=1,-.. ................................ 2s(n)) E 5S(m) where Σ Eu (M). The sequence structure is:
2j = zjj for j E [n] (fixed input portion)
(68)
2n+1 [SEP] (separator)
(69)
2j E EU (M) for j E (n+ 2,..., S(n) (generation region)
(70)
Let D (d1, d2, .2..... da) denote the sequence of positions that have been decoded (unmasked) by the AO-MDM in chronological order, where d: E {n + 2, ,, S(n)} and 2d, * M for all E [k]. The ordering reflects the temporal sequence in which the AO-MDM performed the unmasking operations. Definition 10 (PositionnContent Tokens and Address Encoding). Let E be the base vocabulary. We reserve a subset Epos C for position tokens and define a bijection encode ; S(n)) + Epos with inverse dec-pos: Epos (.....,((11.. For each decoded position d,. define
addra, == encode(d:) E Eopos CE.,
tokd, == 2d, E E.
Thus both address tokens and content tokens are drawn from the original vocabulary Σ. We also reserve subset Eop S for operator tokens used later for AP-MDM edits (5 4).
Masked-ARM Simulation: For each decoded token at position d, E DD the Masked-ARM represents using 2-tuple:
(addra, toka,) (encode(d:). (d4), =a.)
(71)
where encode(d;) is a token representation of the positional index di, and zd; is the actual decoded token. The target Masked-ARM sequence to be constructed is:
YARM (81, ,001-...,.. Fn, [SEP], addra, tokd............................ addrd, tokdy M M....,M M
(72)
remaining positions
where the sequence D (d1, ........dd. d2) preserves the chronological order AO-MDM's decoding operations. The Masked-ARBl sequence has total length 25(n) AO-MDM token requires two tokens (address and content) in the Masked-ARMa representation.
O(S(n)), since each
Induction: To prove We prove by induction that for any AO-MDM, there exists a corresponding Masked-ARM that can simulate the AO-MDM's generation process step by step for arbitrary input sequences.
Theorem 9 (AO-MDM Simulation by Masked-ARMI, For any AO-MDM, there exists a correspond- ing Masked-ARM such that: for any input sequence x (x1..... ..n) and any intermediate state of the AO-MDM with decoded sequence DD = (d1, d2,....da the Masked-ARM, starting from the cor-
responding intermediate state YAM, can generate the next address-token pair (addI tokder) such that:
incode(d++1) addraai (address matches AO-MDM's next decode position)
(73)
2de toká (token matches AO-MDM's 's next decode content)
(74)
where dx+1 is the position that AD- will decode next, and Ede the token that AO-MDM will generate that position.
38

---

Published as a conference paper at ICLR 2026
Proof. To prove this result, decompose the architecture of the AO-MDM into two parts: the input transformation part (which can be represented as an operator ndm_embed) that transforms the token and position into embedding, and the output generation part (which can be represented as operator mdm decode) that transforms the embedding into logits, that is:
A0-MDM(x) = mdm decode(mdm embed(T', (x)
(75)
where TE and PE are seq-to-seq functions defined in Definition 5.
This decomposition is invariant to the choice of token and position embedding functions and AO- MDM's parameter configuration. Simulating AO-MDM's generation process boils down to the following two steps:
Step I: Replicating ndm_embed. We construct initial layers of the Masked-ARM that, given the Mas state YARM- produce intermediate embeddings identical mdm_ent mdm_embed(s) where is the corresponding AO-MDM state. This transformation converts the address-token pair representation back into the embedding format that the AO-MDM expects, enabling the subsequent layers to perform identical computations. We write the E-FASP programs (which corresponds to the encoder Transformer construction) for the construction:
Get logits identical to AD-MDM
mdm logits mdn decode (embed MDM)
tok_scores score (mdn_logits)
A0-MDM candidate set: positions [SEP], still [MASK], and within valid range
cand mask = (PE > sep_ pos) and (TE_MD) == embed (MASK])) ) and (PE <= sn)
cand_score (tok_ scores if cand_mask else
max_score = max score)
is_best cask and (cok_scores == max max_score)
Select A0-MIM'S next decode position and corresponding logits
next next_pos pos tetttmss_exact_mattee (1, is_best, Рк]
logits_neat next = rightmost exact matchahcaatt (next__eeep__eeee pos, PE, mdm logits)
Emit Masked-ARM <addr, tok order
gen_slot = rightmost_oxact__aat
(PE > sep_pos) and (PE <= sn) and (TE == enbed ([MASK])),
PE)
smit_addr (((gen_slot sep_pos) [:1]) 0)
if PE== gen_slot:
result _next_pos if emit addr else Logits next)
else:
result 0
return result
This completes the proof.
We remark the proof relies on two assumptions: 1) the function 5(x) = S(x is deterministic and computable by encoder Transformer (this is implemented by the sn function in the E-FASP program for Step 1); 2) the confidence score is also deterministic and computable by encoder Transformer (this is implemented by the score operator in the E-FASP program for Step 2).
K PROOF OF THEOREM 4
Theorem 10 (AP-MDM Simulation of PRAM, Formal), Let P (lo...., ......,,,, Ie, addr) be a uniform PRAM program with a finite instruction set of size l, identical across processors and input size
39

---

Published as a conference paper at ICLR 2026
On an initial memory state specified by address-value pairs (Xaddr, Xval) with Xval U and Xaddr E AA, suppose P runs in parallel time [(n) using at most P(n) processors and at most S(n) shared-memory words of ('oog n) bits, and outputs PRAMp (Xaddrs
E U (see à E). Then there exists a bijection Φ UUA E and an AP-MDM which, on imput
= (Zu, 21,.... 2n) E EE"!, 20 - ((P(n)) 2; = x( I,....n,
padded to context length (S)) (addresses provided implicitly by positional encodings), produces 6(PRAMpl Xadde; Xval) in (n)) decoding steps.
We first show that AP-MDM can simulate weaker model called Rewrite- MDDM, which is sufficient for the result. Then we construct an E-FASP program that simulates PRAM execution in a space- efficient manner.
Rewrite-MDM follows the same framework as AP-MDM but with simplified control signals. For any token Σ, define:
if [+] = D1, if =f
remask
(3)
(76)
where cI,{1]= (0. 1} is binary rewrite signal. In other words, when [t,i[1] 1, the model rewrites
position with new content y; when Ct, 0, preserves the original content 2t,, unchanged.
We next show how each transition z; - Z in Rewrite-MDD can be simulated by exactly three steps of AP-MDM as defined in 8
Lemma 11 (AP-MDM Simulation of Rewrite-MDM). For any Rewrite- MDM transition z, + Z(+1 on sequence of length n, there exists sequence of three AP-MDM steps that produces the identical result.
Proof. Given a Rewrite-MDM transition where we want to selectively rewrite positions sequence (1t,1, .r,2:...5 n).m) according to rewrite signal = (rr,1, T Tt,n), simulate this
using the following three AP-MDM steps: 2, ( (2) n 2t+1-
Step (Insert): Starting from Zı, apply insert operation at every position E [n]] to create an expanded sequence of length 2n:
(1) (g fo)(z:)
(77)
where of [1] [1] = 0 (no remask), c(2112 [2] = (insert), ( = (no delete) for all E [n]. This yields (1) = -2,,1, M, 21,2, ,t....,2,,... M).
Step 2 (Unmask and Remask): Apply AP-MDM's (g fo) operation on (?) with control signals:
= (g (u)
(78)
where the control signals set follows:
For even positions 2i (newly inserted masks): (2) [1] = (unmask), 2 0 (no insert), (2)
C2 [3] 0 (no delete)
For odd positions 2: - (original tokens): 1 [1] = Tt, (remask), | = 0 (no insert),
[3] = 0 (no delete)
which yield (2) (M, 2141,1, M, 2++1,2, M, 2++1,))
Step 3 (Delete): Apply AP-MDM's (g fo) operation again to delete all mask tokens at original positions:
(3) = (g (2)
(79)
where for all positions in (2):
40

---

Published as a conference paper at ICLR 2026
For odd positions 2; (3) MJ (delete if mask)
(22 -2:-1 [1] (no remask), (2i-1 [2] -0 (no insert), (3)
(3)
-2:-1 [3]
[ (12:-1
(2)
(3) C2i [1] = 0 (no remask), C2 [2] = 0 (no insert), C2: [3] = 0 (no delete)
(8)
For even positions 2r:
This removes all mask tokens at odd positions and recovers the original length n. By construction,
(3) Z,+1, completing the simulation.
State Tracking Mechanism To enable the AP-MDM to autonomously determine which of the three simulation steps to execute, we augment sequences with special boundary tokens [BOS] and [EOS]. The model identifies the current phase by examining the boundary token configuration:
Step (Insert): Normal state with [BOS] at the beginning and [EOS] at the end
Step (Unmask and Remask): [EOS] is followed by M token, indicating expanded state
Step (Delete): [BOS] is preceded by M token, signaling cleanup phase
During Step 2, the model leverages the first bit of positional encodings (e.g. BiPE introduced in G) to distinguish between original positions (odd indices) and newly inserted positions (even indices), enabling correctly apply remasking operations original positions based the rewrite signal r, while unmasking new positions to write content from w,-
We omit the Transformer-basee construction for the procedure described above for brevity, which can be done by simple E-FASP program.
We use the Rewrite-MDD. variant established above simulate PRAM algorithms with optimal space complexity. Here we use the E-FASP B Bi; []++ x] variant with binary positional encoding (5 G). The input that encodes the PRAM's initial memory state sequence x (Z1...., In+1) E gn+1 of discrete tokens from the vocabulary 2:
21 E Σ
(processor count token)
(80)
F++1 E Σ
(data token) for i ,,
(81)
Through token embedding TE : Σ - R", these discrete tokens are mapped to their semantic bit representations:
TE( P(n) E [0, TE(*+1) + val, E {0, 13 (data bits)
(82)
(83)
for i = 1,...,n. The actual input to the AP-MDM is the padded sequence Xy (No,1, 20,2, (0.8(()) E ())) where Σ EU (M]:
=
Øo.j = Ij for j = n, +1
(84)
Fo.j M for j
,...., S(n)
(85)
The crucial advantage of AP-MDM is that it can dynamically rewrite the content at any position using the remask operation, allowing the simulation to use space optimally as (SS(n) rather than the ((P(n) x T(r)) required by standard MDM.
We next provide an overview of the construction:
The key difference between how Rewrite-MDD and AO-MDM simulate PRAM is that Rewrite-MDM can directly rewrite the memory at any position and each computation does not necessarily have be kept in the context forever. This enables us to get rid of the address token. Now representation of processor can be simplified to:
(PC1, R1,1, R1,2; R1,3) (PC2, R2,1, R2,2, R2,3)
(86)
where we only use 3 registers (this is sufficient for the proof but be extended to any 2 2).
Additionally, we do not append processor representations to the end of input x as in AO-MDM, but instead will initialize them at the end of the entire sequence. The remaining part of the sequence is used as a shared memory where token embeddings are data and positional encodings are addresses, aligning more closely with PRAM.
41

---

Published as a conference paper at ICLR 2026
Initialization. When the last position is mask token, initialize the processor state and compu- tation log at the end of the sequence. Roles each token are calculated similarly as the construction in AO-MDM (except it is static throughout the generation process).
The exccution of the program similar to the construction in AO-MDM, except now the address inherently associated with the positional encoding. The termination is also slightly different: the returned embedding has to contain an additional bit to indicate the rewrite operation. Also, the termination condition is longer when all masked unmasked but flexibly defined one: in our case, when all processors are HALT.
Using the operators defined above, execution. The program implements the single-processer algorithm detailed in 3 E.
construct E-FASP program that simulates PRAM
Roles Layout
is_mask (TE embed ( [MASK]))
pn
last_p eightmost_exact_mmg (1, is_first, TE) I number of processors P (n)
(1, is_last, PE) $ last position index
proc_b last_p - (pn << 2) + 1 processor region start
proc (PE proc_b) and (PE proc_b (pn 2)) # in processor region
in_ (PE >= 2) and (PE proc_b) in memory region
Initialization
is last, is_mask)
past_is_mask and in_proc:
inner = (PE prop_b) [:2] $ slet index 0..3 # initialize processor region to 0, and R=1 (require rewrite)
if inner == 0: return
1) # PC
elif inner
return ((PE proc_ b) >> 2, 1) # R1
elif inner 2: return (0, 1) R2
else: return (0, 1) R3
rewrite for other positions in initialization step if last_is mask and not in_proc:
return (TE, 0)
=essee=== Processor zone update (enly if pnoproc)
if inoproc:
pia (PE proc_ >>
slot (PE proc_b) [:2] # 0:Pc 1:R1 2:R2 3:R3
read previous round processer state (fixed slot)
pc_pos proc_b (pid 2)
pos proc
(pid 2) +
r2_pos = proc_ + (pid << 2) + 2
r3_pos = proc_b (pid << 2) +
Ligttmss__ccatt_aacchhho.... (pc_pos,,, PE, TE)
Lightmoss_.xsttmtthhhtt.. (ri_pess PE, TE)
R2 rightmostt_xxett_matae (r2_pcs,, PE, TE)
R3 - rightmost_exact_maate (r3_pcs, PE, TE)
processor already HALTed, do not update (R=0 for this slot)
CODE: return (0, 0)
fetch and decode instruction I_type, op_r, op_s, op_c, label_ades get_instruction (PC)
(R1 if op_s else R2 op_s else R3 if op_s else
0)
Rr = (R1 is op_ == 1 else R2 if op_r == 2 else R3 if op_r == 3 else
0)
default
PCn, WR, WR_en PC 1, Rr, 0
instruction semantics
1_type embed ( [(OAD)]
42

---

Published as a conference paper at ICLR 2026
mem get: address=PE, value=TE (only match in menory region)
hitp rightmost__xact_maacc (Rs, (PE if mem else 0), (PE if
in_mee else 0))
WR = sightmost_cxact_maeee (hitt PE, (TE if mem else 0))
_R_en
elif I_type embed ((STORE)) WR_en
elif I_type = embed(
WR, en = op_
elif I_type = embed([ADD)): : WR, eR_en (Rr Rs), 1
elif I_type
embed(1S7BB)> WR, WR
(Rr Re),
elif 1_type
embed [mbed([AND]]] wR, wR_en (Rr R8)
elif I_type
embed [XXO]]: wR, wR_en (Rr R8),
elif I_type -- ([SHL]) WR, wR_en (Rr << R8)),
elif I_type = embed
WR, WR ee (Rr >> 3s)), 1
elif I_type embed [BRZ]) and (Rr 0): PCn label_adds
elif I_type embed [JMP] PCn label addr
olif I_typc = embod [HALT]) PCn HALT_CODE
unified writeback
Rln (WR if (RR_en and ep_r
else R1)
R2n (WR if (WR_en and op_r 2) else R2)
R3n (WR if (WR_en and op_r -- 3) else R3)
return next state for this sict and require rewrite
slet 0: return (PCn, 1)
elif slot -- 1: return (Rin, 1)
elif slet -- 2: return (R2n, 1)
else: return (R3n, 1)
Memory zone update (also for non MASK)
if in_mem,
for all PC slots, construct STORE stream (address, value) for this step
is_pe_gleh ((PE proc_b) (:2]) 0) and (PE proc_b) and (PB proc_b + (pn << 2)
PCi (TE if is_pe_glob else 0) It, ré, rs, cimm, 1. get get_ inwrinsstuuttioniio (PCC)))
pid (PE proc_ b) >> 2) # only meaningful for PC slot
rl = rightmost_exxeeee exact match (proc_b b + (pid << 2) + 1, PE, TE]
r2 = rightmost_exxnn eea____aacc_cacchhheeaaaaaeaaace (prec_b b + (pid << 2) + 2, PE, TE]
r3_i rightmost_exact
(prec_b + {pid_i << + 3, PE, TE)
Rs_1 (rl_i if rs clse r2_i Is
else r3_1 if rs
clse
0)
Rr_i (rl_i if rd = 1 else r2_i if rd == 2 else r3_i if rd == 3 else 0)
STORE KEYS (Rs i (is_pe_gleb and (It embed (STCRE) )) else
# store address
STORE VALS (Rr i it pis_pc_gleb and (It = embed |TCCRE] )) else 0)
$ store val vue
hit rightmost_exett_matee (PE, STORE_KEYS, 1, 0) val =ightmost_exatt_mett match (PE, STORE KEYS, STORE VALS, TE)
all halt: do rewrite; otherwise, if hit, rewrite this address even not MASK originally) if hit == 1: return (val, 1)
clsc: return (TE, 0)
return (TE, 0)
43

---

Published as a conference paper at ICLR 2026
L PROOF OF THEOREM 5
Definition (Two-Sided Dyck-k)), Let En = {ai _k
+1
+11. Define u = v if v is obtained from
by deleting a factor a,0;" 0; a, for some i E f1..... ... Write u = iff there exist m 2 0 and words Wo..... Wm with wy + w/+1 for all j. Then
TDycky == {w Σg -==-e) c)
(87)
where is the emply word.
For the Two-Sided Dyck-k language, we define the vocabulary as:
== =a aj a+1 a2 ......t +1 .4x " U [ [[BOS), [EOS]]
(88)
and the extended vocabulary E = E U (M, M2), where [a ;i=1 are the 2k bracket tokens, [BCS] and [FOS] ] are boundary tokens, and M1. M2 are two types of mask tokens used to handle an inherent
limitation of vanilla masked diffusion when extended to the non-deterministic case (i.e. given two
mask tokens, the model can not randomly generate AA and BB without also having probability to
generate AB and BA). Thus Σ 2k 2 and |Σ| 2k 4
Following (Merrill et al., 2022):
Definition 12 (Hardmax). For any x E R", define the cerprremperrture softmax (Hardmax) as
i E arg maxj Tjj
softmaxo(#) (2:) A lim softmax,, (x), where [softmaxo(=:)] +
arg max, 2,
0,
otherwise.
Definition 13 (Stochastic AP-MDM), A stochastic AP-MDM is defined AP-MDM with encoder- only Transformer backbone as in F, where instead of greedy decoding, we use sampling from Hardmax distributions. Formally, let Encę E" (R be the encoder Transformer (before the final projection layer) as defined in Definition 7. For each position i in the impul sequence,
let h; [Ency (x)]; Rd be the hidden state. Define logits E(v x, -(h,, TE(e)) and the probability distribution over vocabulary E as:
po(u x, i) = |softmaxx([( x, x,1))l
(89)
where softmax, is the Hardmax function from Definition 12. The stochastic AP-MDM samples tokens according to v; ~ Categorical(pa( x))).. For the insert operation to support two types of mask tokens (M₂ and M2), we use two separate classification heads PROJi, and PROJi, whose outputs are thresholded for inserting M2 or M2, with priority: M2 takes precedence over M. We disable remask and delete operations for this construction.
Theorem 12 (Generating Two-Sided Dyck-k, Formal). For any 2 there exists stochastic AP-MDM as in Definition 13 with constant-depth Transformer backbone such that the support of the induced distribution of AP-MDM over strings w exactly equal TDyck that is,
1. (Coverage) For every w E TDyckg, Pro [w] > O.
2. (Support exactness) For every w & TDyck,, Pro = 0.
Conversely, under the common hardness assumption that TC # NC², for any constant-depy ARM with polylogarithmic embedding dimension, there exists E I such that the support of the distribution generated ARM cannot be exactly equal to TDyck
Proof. For the claim about ARM, we will prove by contradiction. First we note that every w E Di- there exists a w' E TDyck, such that w a prefix of w'. (The existence of such w' is straightforward. for example, one can construct it by taking w' ww-1, where the inverse is performed by viewing w as an element the corresponding free group) Now we suppose ARM can indeed generate a distribution whose support is exactly equal to TDyck This implies that the ARM must be able to determine at each generation step whether the current sequence can be terminated. Specifically, the model must assess whether the currently generated sequence satisfies the complete bracket matching condition. If the sequence is properly matched, the probability of outputting [EOS) must be non zero enable termination. Therefore, the difficulty of generating matched brackets reduces the problem
44

---

Published as a conference paper at ICLR 2026
of recognizing whether given sequence forms valid matched brackets. For the two-sided Dyck-k language, this recognition problem is DLOGTIME--nifon uniform -Cr-hard (Robinson, 1993), which exceeds the computational capacity of constant-depth Transformers which is in TC", under the hardness assumption that TC" NC Thus conclude ARM cannot generate distribution over Si whose support is exactly equal to TDycky.
For the stochastic AP-MDM, construct the following algorithm to generate all strings in the two-sided Dyck-k language through the following algorithmic procedure, illustrated in Figure 2(b);
Step (Probabilistic Mask Insertion): If the current sequence contains no mask tokens, then for any sequence position j not containing an -nd-of-sequence token, the model inserts M1 with constant probability p E (0, 1) using the insert operation from 8 The insertion probability for M2 set to zero at this stage.
Step 2 (Uniform Token Selection): At positions containing M1, the model performs two operations: (i) it samples uniformly from the bracket token set { } to determine the content, and (ii) it inserts M2 with probability Due to the priority- based insertion mechanism defined in Definition 13, M2 overrides M,, making the original insertion probability irrelevant for subsequent processing.
Step 3 (Context-Aware Bracket Matching): When processing M2 tokens, the model identifies the nearest. bracket token a=t to the left of the current position and generates the corresponding matching bracket according to the two-sided Dyck-k reduction rules.
The termination mechanism operates as follows: In Step 2, when the sequence contains M1 tokens but no M2 tokens, the model inserts M2 at the final position with fixed prohability. Subsequently, in Step 3, when processing this final M2 token, the model generates [FCS] (given the binary positional encoding we considered in & E, the model is able to identify if the token should be decoded as [ROS] or matching bracket), signaling the end of the generation process.
Termination Condition:
The above algorithm admits an E- E-FASP program implementation (see 5 G) with the following treatment of stochastic operations:
For uniform sampling over the 2k bracket tokens, we exploit the fixed vocabulary size by assigning each bracket token a; to distinct dimensions in the d-dimensional embedding space. Specifically, when the E-FASP program needs to output uniform distribution over subset $ S ( Jim1+ it returns a hidden state h E Rd where (h, TE())) e for all S (for some constant e) and (h, TE(e")) < e for v' & S. The hardmax from Definition 13, ensures that the probability mass concentrates uniformly over S, achieving the desired uniform sampling behavior.
is easy to see that this generation procedure can produce any string in the two-sided Dyck-k language, and since any token that would violate Dyck constraints always has strictly smaller logit and hence probability 0 under Hardmax, the support of the distribution is exactly TDyck,-
We note the introduction of two mask tokens is for the model distinguish between different steps. but this is not necessary if we allow some random seeds in input which mitigates the limitation of MDM when extending to the non-deteriinistic case.
M PROOF OF THEOREM 6
Edit Triplet Encoding, Eop Epos x Σ, where
We encode each elementary edit as a triplet of tokens (op, pos, val) e
Dpp = (UNMASK, INSERT, DELETE, REMASK)
(90)
The position token set Epos reuses the earlier address/position encoding in Definition 10: position i E [S(n) is encoded as pos = encode (i) with inverse decoding dec dec.pos(pos) =.
The semantics of the triplet follows the instantiation of AP-MDM considered in 5
Definition 14 (Editing Sequence). Given an input sequence x E Σr, an editing sequence is a finite sequence of triplets
T(x)= = (lop), posj, val,)) m(x) op, E Eops pos, E Expos: val, E Σ.
(91)
45

---

Published as a conference paper at ICLR 2026
Its application to x is defined recursively by x( and
x x(i)
Apply(((p))) pos,, valj), x0i-1), j= j=1,...,m(xx m(x).
(92)
We write
Spply-Triplets((( x) == x (m((x))
(93)
An editing sequence is valid iff every intermediate application is well-defined under the triplet semantics (e.g. UNMASK applies only to masks).
Theorem 13 (Hardness of Simulating AP-MDM, Formal), There exists an AP-MDM F with constant-depth encoder-only Transformer backbone such that no ARM Masked-ARM G (Defini- tion 3) with a constant-depth decoder-only Transformer backbone can, on every input x. produce an editing sequence Tx(x) (Definition 14) that realizes F's generation process; i.e., under the assumption that constant-depth Transformers do not include TC²
6 Apply Triplets (To()) x) + (oplyyTripooss((((3)) x),
or (x) invalid.
The ARM in the above result can be replaced by the Masked-ARM with encoder architecture used in Theorem without affecting the result.
Proof. Fix L E N. Let E 2 be the base string, let T'' be valid editing sequence (Definition 14), and q Epss be a query position token with index i dec.pos(4). Encode the input as
x (u, [SEP], flatten(T), [SEP], [SEP]) E IL+3+3m(()
(94)
Here
flatten(T) = (op1, pos,, vali,.... op pos,, valm).
(95)
The task is to output the queried symbol after applying the editing history:
y
Trinlltstiill u)], E E.
(96)
That is, the instance provides (i) base string u, (ii) an editing history T as sequence of triplets, and (iii) query position token The model must simulate T on u and return the symbol at the queried position in the resulting string. For AP-MDM, the simulation is intuitive and can be proven by simple E-PASP program which we skip in this proof.
For ARM, due the construction of the problem, the simulation process is exactly copying the editing sequence part in the input, therefore solving the problem is equivalent to directly answer the query, which we show the equivalence to TC -hard task:
Definition 15 (PRESERVES (Allender et al., 2006)). Let A be an ordered list (1-indexed). The update alphabet is
u = (insert(i), delete(i) | E).
(97)
For an initial list An and an update sequence E u", let A, be the list after applying the first t updates of s. For indices i, define
PRESERVES(Ao)) s,i, i.j) >
the item at position i Ag still exists after and is at position j in Ajal
(98)
The decision problem PRESERVES asks, given (Ao, 8, 8,1,)), whether PRESERVES( Ag. 8, 8,1,j) holds.
Conjecture 14. The PRESERVES problem is NC! -hard under DLOGTIME-unifrm reductions.
We reduce PRESERVES to our Sddting-Query task in one step. Given (Ag. 8, i, with |ool L, let u E LL list the items of Ag (unique token id per item); expand each insert (p, 8) as the triplet block ((INSERT, encode(p), M), (UNMASK, encode(y'), u)) and each delete(p) as ((REMASK, encode(p). ,), (DELETE, encode(p), where p' is the position of the newly inserted mask under our convention and is ignored; let T be the concatenation over and set encode(j). Then with
y TooplyTTripetts u)],
(99)
46

---

Published as a conference paper at ICLR 2026
we have
PRESERVES( s, i,), + y=
(100)
Thus any model that solves Editing- Query on all inputs also decides PRESERVES. By Conjecture 14, PRESERVES is -hrdhard, which places it beyond the computational capacity of constant-depth Transformers that are contained in TC". Under this conjecture, no constant-depth ARM or Masked- ARM can solve our Editing-Quee task on all inputs. This completes the proof.
N EXPERIMENT: SUDOKU PUZZLE
We provide detailed description of training data generation for the Sudoku puzzle experiment. The data generation process simulates a backtracking- solving algorithm and records the intermediate states supervised training trajectories for AP-MDM.
State Representation The 9 x 9 Sudoku grid is represented as a sequence of 324 tokens, where each cell is encoded using 3 consecutive tokens: (value, color, marker). The vocabulary consists of 32 tokens including: EMPTY (unfilled cell), MASK (unknown position to be predicted), digits 1-9 (filled values), WHITE (default color indicating no branch), 15 branch COLOR tokens (tracking different branching paths), NORMAL (standard state), SKULL (failed branch point), BRANCH (active branch starting position), and SEPARATOR (structural delimiter between cells). The value token can be EMPTY (for unfilled cells), a digit 1-9 (for filled cells), or MASK (for positions being predicted). The color token tracks which branching decision path the cell belongs to, using WHITE for non-branched cells and one of 15 COLOR tokens for cells within branches. The marker token indicates the cell's computational status: NORMAL for standard cells, SKULL for positions that caused backtracking, and BRANCH for branch starting points.
The solving algorithm consists of several atomic operations, each translated into state-transition tuples for AP-MDM training:
The two most fundamental operations in Sudoku solving are deterministic assignment and branch creation, both implemented through combinations of remask and unmask operations. For Assign, when deterministically filling a cell with value v, we generate a 2-step transition: first, the three tokens at the target position are remasked, converting them (M, M. M); second, these masks are unmasked to the target values (v, c, NORMAL) where is the appropriate color token determined by the current branch context. For Branch, when creating branch at position (r, e) with candidate value v and branch identifier b, we similarly generate 2-step transition: first, remask the cell tokens to (M, M. M); second, unmask to (v. COLOR, BRANCH) to mark this cell as branch starting point with the corresponding branch color.
Assign and Branch:
Concrete examples visualizing these two operations are shown in Figure
When the solver detects a contradiction (a cell with no valid candidates), before backtracking, we mark this contradicting position through a 2-step transition: first remask the cell to (M, M, M), then unmask to (EMPTY, COLOR, SKULL) to visually indicate the contradiction location. When backtracking from a failed branch, multiple cells need to be cleared through 2-step transition that handles both ordinary cells and the branch starting point differently: in the first step, ordinary cells are remasked in all three token positions while the branch starting point only has its marker token remasked; in the second step, ordinary cells unmasked to (EMPTY, WHITE, NORMAL) while the branch starting point undergoes simultaneous remask and unmask operations with the first two positions remasked to (M, M) and the third position unmasked to store the failed value. After backtracking, when filling the failed position with new value, we generate 2-step transition to convert from the SKULL state: the first step unmasks the value and color while remasking the marker to (M, M, Vou) + (Vnew, c, M), and the second step unmasks the marker either NORMAL or BRANCH depending on whether this creates new branch. Concrete examples visualizing these operations are shown in Figure 5.
Contradiction Marking, Backtrack, and Recovery:
Training Data Statisties Following this generation process, each Sudoku puzzle produces 1421.3 state-trann transition tuples (i.e. from x, to X(41) on average depending the puzzle difficulty and the number of backtracking steps required. For our experiments, we generated training data from 100 hard Sudoku puzzles, each yielding 25,022.6 training state-transition tuples on average.
47

---

Published as a conference paper at ICLR 2026
Input Sequence (X²)
(19766))
3 LECTT
MUS
(eaa)))
lecial
0 JOMER 5J
JOSK
DNITT
[
LMO
INITEE
JUPE
SPAM
1917))
DOUR
METT
[CC
SOYTA
Remask (c)
DIDI
Next Sequence (Gt-1)
(ear))
MIDS
GUPLI XI
SWD
IQUR
[0
[MCTE]]
SWETC
POPPL
D ITS
IOC
DNITE
[
L
DPETT
[6686.)
MITE
[
Te OIL
HN PAL
(a)
Input Sequence (x²)
[ecTe]
IOUOL
[MOTC]
TEETC
N
ICC
DOWNLL
1 [[0ee]]]
(MITES
DOWNL
DNCT
DE POPALT
DETTTT
DORK
SPERT
JUPP
2111
Remask (c)
( E PI B) & G E
E ( R PI R
PIPEP)
Next Sequence (Ker1)
7 (OGPLB)
MUTC
DOWBLT
(H0NAA)
[
HOOM
DOMPL
(NOWAA
[WOTE
DOWNL
[WETTES
(b)
Figure 5: Demonstration of value assignment.
48

---

Published as a conference paper at ICLR 2026
Input Sequence (x²)
1 (METE)
(MUTEE)
IOUL 4
(116E933) 51 19900
[
Lectul
[HER]
INOTET
(669943
TWOTET
DOWNL
THETCT
SOWMET
(WITC))
(MU
Remask (c)
Next Sequence (Xe+1)
[eCTT]]
MET
METT
(MITET)
[
BSAEE
MCC
HIG
DOWKK
EMG T
LECTEL
(a)
Input Sequence (x²)
[eCTT]]
21
MEET
MCNI
[MITET
SOOLL
(SAAS) 11 (0U0LL)) 51
[
IMO
(WITT) (HRPAA)
[WOTEC
TECTEC
Remask (c)
FIR F R R E A O PIR F)
FIF F R FI R S P R
FIFI FI
PI FI
Next Sequence (X++1)
V 20
J.S. (eICTT)
gre
(ICIIT) [1698]] (MITET)
TEAMO-3
PMM
3 JINER
[MM]
[MIR]
MAN
PAM
PANC
L LeNTTN
DOWBE
MIN
UNITT
SOVMLT
Mabe
MMac
JACTET
DOWBLL L
DOWML)
[ecTe]
(b)
Figure 5: Demonstration of backtracking and recovery from failure operations (Part 1). (Continued on next page)
49

---

Published as a conference paper at ICLR 2026
Input Sequence (x²)
3 [63
[
3 LECTTE
1 (METE)
P
11 JINER
[MM]
TOWNL
10500 3)
LNITE
DOWEL
IMA
HNFTT
|0UR
LECTT
Remask (c)
Next Sequence (Ker1)
IRORGE
MCNI
(66T9)
1 [E
1+ (MITT]]
[SS
GOUR
JOUOR 21
IQUAL
PELM
ICC
SHITE:
PEPAL
METTE
[
NES
(c)
Input Sequence (x²)
IQUOL
[MCTC]
HCC
(MPMAT
1 [[
(MITES
D
DOWNL
DNI
DE PEPALT
DETTT
DORK
SPERT
2111
Remask (c)
R 6 ( E PI B) & 9 E
( R PI R
Next Sequence (Ker1)
1000
MUTC
(HONAL)
(ECTE)
TI TO
STN
[0
(M0TE]
(HUTES)
[MCTL]
HOP |
MCC
(
[WOTE
DOWNL
DMITES
[WETTE
(d)
Figure 5: (Continued) Part 2.
50

---

Published as a conference paper at ICLR 2026
Input Sequence (X.)
(19964))
3
MUS
tecial
[
DEITS
DNIT
[
LMO
JUPE
SPAM
1917))
DOUR
METT
ICC
SONMA
Remask (c)
DOUTE'
DIDI
Next Sequence (Gt-1)
(ear))
MIDS
GUPLI XI
SWD
DONMLI
IQUR
TEAARAT
PIL
[MCTET
1 [[WTe]]]
(MITE)
LECTLL
PEPAL
DEETE
DORK
DEIFS
ICRM
(66141
Fe
GOUL
[MCIL
HACTL
(
Input Sequence (x²)
UNITT
IOUOL
MNTTR
DUT
(H00M))
[MCTEL
[ [VINAA
JOWKL
DNPTT
INCTLT
DORN
JOUOE 45)
[
1 [[
DNTTT
[LONN
[1386L]
[PPITT
Remask (c)
R 6 ( E & PI B) & G E
( R PIGIPER
FIBID E PIPEPI
Next Sequence (Ke+1)
7 (OGOLE
MUTC
D
(H0NAA)
(eCTE))
TI TOS
[E
NC
SOORL
[MCTR]
I 2TC1
11 PWETE)
(f)
Figure 5: (Continued) Part 3.
51

---

Published as a conference paper at ICLR 2026
O EXPERIMENT: GRAPH GENERATION
We consider a graph editing task that requires computing the minimum edge set to disconnect two specified nodes. Formally, given directed graph G (V, E) with unit unit-capacity edges and two designated nodes s, t E V (source and target), the task is to generate a modified graph G' = (V, E') where F' F. such that there exists no path from to t in G', and FE \ E'| (the number of removed edges) is minimized. This is equivalent to computing the minimum s-t cut, which by the max-flow min-cut theorem equals the maximum flow from s to t. The generation process involves iteratively finding augmenting paths, modifying the graph structure by reversing edge directions, and tracking intermediate states until no more augmenting paths exist. The final output is the graph with min-cut edges removed, effectively disconnecting s and t.
We provide detailed description of training data generation for this graph editing task based on the Edmonds-Kaat algorithm. The data generation process simulates the BFS-based augmenting path search and records the intermediate algorithmic states as supervised training trajectories for AP-MDM.
State Representation A directed graph with n nodes and edges is represented as token sequence with three main components: prompt (source and target nodes), graph data (edge list with features), and node data (node list with features). Each edge is encoded with its endpoints (u, v) and two feature slots tracking the edge's directional availability: slotl represents forward direction availability (initially FB for (initially MASK indicating unavailable). Each node is encoded with its ID and two features: level (BFS layer, initially INF for unvisited or LVLO for source) and parent (parent node in BFS tree, initially NIL) The vocabulary includes structural tokens (PROMPT, SRC, TGT, GRAPH, NODES, parentheses), edge feature tokens (FB, MASK), node feature tokens (LVLO-LVL9, INF, NIL, PAR), node IDs (0-299), and termination tokens (EOA, EOS).
and slot2 represents reverse direction availability
Atomic Operations
The Edmonds-Kary Karp algorithm is decomposed into atomic operations, each translated into state-transition tuples for AP-MDM training. The algorithm consists of four phases:
Before the algorithm begins, edge and node feature slots must be initialized through a 3-step process following a expansion- teennntteennumne unmask paradigm. First, MASK tokens are inserted after each edge's 's second node and after each node's ID (insert operation). Second, another MASK is inserted while simultaneously unmasking the first MASK to FB for edges and to the appropriate level for nodes (insert- unmask operations). Third, the second MASK is unmasked to MASK for edges and to NIL for nodes (unmask operation). See Figure 6.
Feature Expansion:
-hen-unmaskk
Breadth-Fing Search: The breadth-first search proceeds by discovering nodes layer by layer. When a new node is discovered through an edge, we generate a 2-step transition: first, remask the node's level and parent features to MASK (remask operation); second, unmask these MASKs to the new level and parent ID (unmask operation). This continues until either the target node is reached (proceed to augmentation) no new nodes can be discovered (algorithm terminates). See Figure 7.
Path Augmentation: When an augmenting path from source to target is found, we generate a 2-step transition flip edges along the path and reset node features. First, for each edge on the path, swap its s and slot2 values (reversing the direction), and simultaneously remask all node features to MASK (remask operation). Second, unmask all node MASKs back to their initial values: INF for non-source nodes and LVLO for the source node, with all parents set to NIL (unmask operation). After augmentation, the algorithm returns to BFS phase to search for the next augmenting path. See Figure 8.
When no more augmenting paths exist, the final BFS identifies two disjoint sets S and T where S contains the source and T contains the target. The min-cut edges are those directed from nodes in S to nodes in T' in the original graph, and these edges must be removed to disconnect source and target. This is accomplished through 3-step process. First, remask all tokens representing the min-cut edges to MASK (remask operation). Second, delete these edges while simultaneously expanding a MASK token after EOA (delete insert operations). Third, unmask the expanded MASK to EOS (unmask operation), marking algorithm completion. See Figure 9.
Termination and Structural Editing:
52

---

Published as a conference paper at ICLR 2026
AP-MDM
ARM
# Nodes
# Edges
Avg. Seq. Length
Max Seq. Length
Avg. Seq. Length
Max Seq. Length
4
12
56
65
932
932
5
17
81
88
1,375
1,403
23
129
2,083
2,140
7
29
148
170
2,687
2,874
8
36
189
217
3,529
3,865
9
43
236
252
5,586
6,597
10
50
270
305
4,915
5,392
Table 1: Sequence length statistics for graphs of different sizes. AP-MDM sequences contain state- transition tuples, while ARM sequences enumerate all operations explicitly.
ARM Baseline For comparison with AP-MDM, we train an autoregressive baseline that learns to generate the complete solving trajectory as single sequence. The ARM baseline takes the initial graph state as input and must generate the full sequence of operations needed to solve the task. To enable this, we convert the AP-MDM training data into an ARM-compatible format by representing each operation type (REMASK, UNMASK, INSERT, DELETE), and e is the value (or NONE for operations without values). The sequence format is: [initial state Xy) STEP [operations, STEP (operations,) STEP ANSWER [final state Xinal], where each STEP separates consecutive state transitions and ANSWER marks the beginning of the final output. For ARM training, objective with teacher forcing, where the model learns to autoregressively generate the entire operation sequence given the initial state.
triplet (p, v) where p is the position index (POSEO-POSE399)
is the operation
the standard next-token prediction
As shown in Table 1, the sequence length grows with graph size for both AP-MDM and ARM, but ARM requires significantly longer sequences due to the explicit operation enumeration.
EXPERIMENT: PARITY
The parity task requires determining whether binary sequence contains an even or odd number of 1s. Formally, given an input sequence x = (æ1, Z2.... ... E {0, 1)", the task is to compute ① Z. (XOR of all bits), outputting for even parity and for odd parity.
Algorithm and Data Generation For AP-MDM training, we implement elimination algorithm that mimics how humans naturally solve parity: repeatedly remove pairs of identical elements until only the result remains. The vocabulary consists of 5 tokens: BOS (sequence start), EOS (sequence end), MASK, digit O, and digit The elimination process follows these rules: when encountering Os in the sequence, convert them MASK; when encountering pair of 1s, convert both to MASK; then delete the MASK tokens. This process repeats until only BOS remains (for even parity) or BOS followed by single I remains (for odd parity). Each climination step generates tuple: converting tokens to MASK is a remask operation, and removing MASKs is a delete operation.
tratsttonnntionn
The training data consists only instances that cover all possible elimination patterns. Each sample is single-step state transition demonstrating one atomic operation. The test set contains 1,000 randomly generated binary sequences with varying lengths. The test sequences have approximately equal distribution of even and odd parities.
Data
ARM Baseline For the ARM baseline, we train autoregressive models with chain-of-thought reasoning where the model generates intermediate cumulative XOR values at each position before outputting the final result. The sequence structure is: BOS [x] 22 ... 2n EOP [$1 $2 Sn result] EOS, where = ; Ij represents the cumulative XOR up to position i, and result is True (for odd parity) or False (for even parity). Only the content after EOP is used for computing the training loss. We train ARM models with up 10K training instances at various fixed lengths (e.g., length 10, 50, 100) and evaluate their ability to generalize to longer unseen lengths.
53

---

Published as a conference paper at ICLR 2026
Input Sequence (x)
Remask (c()))
Insert. (cII)
Delete (c2))
Sequence (Xt+1)
wapr Bi Iae map 0000
0000
[S00]
0000
0000
0080
0000
8
00.00
0003
0398
PBS
(a)
Input Sequence (x))
waiey (er vor (BOM
Remask (c(0))
BOTTEROOOD
Insert. (d1)
P
BODER 8000 110 Bille
Delete (ct2)
Next Sequence (Xt+1) IOOM
waer si R 1o
0090 10
[C
(b)
Input Sequence (x)
3
8
MVX
4/3 10
(NS4]
Remask (c(0))
000SER 5000000
Insert (c(1)
BOULER 00000000000000000000000000000000
8. 8. 01
Delete (c(2))
R R 3 a 1000000 01100000000000000000000000000000
00000000000000000000000000000000
Next Sequence (x+
PPCCI
Mysl
2
(POA]
1
1TAI
(c)
Figure 6: Feature Expansion phase in graph generation, showing the initialization process for edge and node feature slots using insert and unmask operations.
54

---

Published as a conference paper at ICLR 2026
Input Sequence (e))
Tracc
000000
0.
8
[MA
10
Remask (c(O))
R 0000000
E E PIDI P S PI
3 (1010)8
Insert. (c(1))
8 ( 0
Delete (c22))
S B 0..0. (1000000000000000000000000 00000000000000000000000001010000
Sequence (xt+
Wave FXX
0
2
MBXCS
[HA]]
(a)
Input Sequence Bid
Remask (c(0))
Insert (c11)
BOEEE (0000000
Delete (c2)
10000000000000000000000000001000 01g.
Next Sequence (x.,))
PM
x
[MAK]
PHIZI
1.
(b)
Figure 7: Parallelized BFS phase in graph generation, showing layer-by-layer node discovery with parallel processing using remask and unmask operations.
55

---

Published as a conference paper at ICLR 2026
Input Sequence (e))
00 1
0.99
[MAX]
Remask (c(O))
R 0000000 01100000101100000100000000000000
3 (1010)8
Insert. (c(1))
8 ( 00000000000000000000000000000000
(
Delete (c22))
Sequence (xt+
Warr FXX
IHOAT
INDO
(a)
Input Sequence
IROM
MIAT
Remask (c(0))
Insert (c11)
BOEEE (000000
Delete (c2)
Next Sequence (x+-1)
PM
e 000xx
MIXT
9.2
[MOK]
PWIZI
10
(b)
Figure 8: Path Augmentation phase in graph generation, showing edge reversal and node feature reset after finding augmenting path using remask and unmask operations.
56

---

Published as a conference paper at ICLR 2026
Input Sequence (x)
1N00
1
TMO
Remask (c(0))
Insert (c11)
50668 8000000)
Delete (c(2))
0 000000 S1 (181)) (J
( C1010)
Next Sequence (X+-1)
0111
INCO
(a)
Input Sequence
(ROR
ITDK
IMDI
EMAM
PW/I
TUXT
HELET
PKA
TAUL
INGET
[NAL]
ICL
SWAI
Remask (c(0))
00032800000000000000000000000000
BFFFEE 10000000000000000000000000000000
Insert (cl1)
0
Delete (c(2))
Sequence 1
Ii TOT BROH
0000
00000:0
(MAN
00:0
1011
MUAI (MA
(b)
Input Sequence (x:)
BRORI 0
IMAA
IMOC
IMDC
0 1
[S
Remask (c(0))
000EE 00000000000000000000000000000000
Insert (cl1)
01 (8 FEEEER
Delete (ct2)
FUETER ( 8 01000100000000000000000000000000 01000000000000001000000000000000
Next Sequence (x++1)
PM
[MO
0
(MAR]
[NILT
(4LL]
(c)
Figure 9: Termination and Structural Editing phase, showing the deletion of min-cut edges and algorithm completion using remask and delete operations.
57


Reviews:
[{"review_id": "8aw15H9ddb", "reviewer": "Reviewer_zY1v", "summary": "This paper studies alternative generation paradigm that breaks the AR hegemony. It argues \"natural\" process that include editing and complete rewriting the intermediate states offer concrete benefits over AR and Mask-dLM. It first formalizes Mask-dLM's power and limits, then proposes Any-Process dLM supporting masking, unmasking, insertion and deletion. AP-dLM is a natural ability-superset model to existing alternatives and strictly expands solvable problems under practical resource bounds. Primitive empirical results on Sudoku, parity and graph editing confirms the proposed method as a proof-of-concept.", "questions": "1) I don't think that when insertion operations and deletion operations are included, their conceptual \"addresses\" can be trivially provided by any existing position encoding without having to trigger the complete re-encoding of context. This caused my confusion when trying to understand THM 10. Can the authors provide more details on this?", "limitations": "", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "1) The clarity of the process-level framing and the proposed AP-dLM is good.\n2) The demonstrated time-optimal PRAM simulation for Mask-dLM and time-space-optimal one for AP-dLM is mind-freshing. \n3) The experiments are compellingly testifying the core claimed benefits at a small scale.", "weaknesses": "1) Please pardon me if I'm being too harsh on this - it claims to have solved everything but really nothing in practice - one of the major issues in language modeling is always about scaling. There's little, if any, discussion on how the proposed method could even scale-up to a medium level. If we break down language generation into a few rather heterogeneous mini-procedures, the two most important steps are:\n\n - Context Encoding, meaning that how the context information is collected and compressed;\n - Action Prediction, meaning how the representation vectors are then transformed into further actions that alters the context.\n\nThe real question in NLG ever since the N-gram era really has been that, given a sequence of N tokens that can be sufficiently long, how to balance between being practically efficient in encoding context and predict the next growth of context that holds the **monotonicity** of context to some extent, such that we can somewhat efficiently reuse the previous computation when the context is altered by the generation step. I don't think the community is unaware of the unnaturalness of AR all along, most scaled-up practices uses it only because we can easily train very large and thus generally capable AR models at ease.\n\n2) Continuing the previous discussion, talking about data efficiency alone without carefully check how efficient can the proposed model utilize the data can be less meaningful. External validity beyond toy settings remains to be shown.\n\n3) A lot of existing efforts in building non-Mask/insertion-based dLMs that are moderately scaled up, such as Insertion Transformer, InDIGO, Non-Monotonic Sequential Text Generation, XLNet, Levenshtein Transformer and InsNet are missing, showing the potential insufficient literature review by the authors.", "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": "A7NUrN1ref", "reviewer": "Reviewer_Fhff", "summary": "This paper proposes a new framework for generative modeling, in which the model is allowed to perform extra operations such as remasking and insertion (rather than solely unmasking/next-token prediction). This more flexible generation process allows computational circuits of higher complexity to be representable, which the authors compare rigorously against masked diffusion models and autoregressive models. Furthermore, the authors demonstrate experimentally on simple tasks that their method appears much more robust  and seems to learn more efficient representations/solutions.", "questions": "1. The authors are looking through a perspective of expressivity/capacity, which is fine and often the right starting point. I am, however, interested if the authors found any qualitative differences in training dynamics/hyperparameter choices/... between their method and ARM or MDM? Anecdotally, does it feel similar training them? I ask because sometimes when a model is, for example, way more robust to learning rate, it's indicative of what kinds of extra structure its baking into its solution.\n\n2. It would be nice to see experiments at larger scale. This is always the case though, isn't it :)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. I think it is a good idea to investigate various generation strategies and their complexities/capacities in a way that is fairly model-agnostic. The authors do exactly this; by adopting a complexity-theoretic language they are able to show separations in a way that does not depend on parameterization. The reason for improvement is clear, and they present it clearly.\n\n2. The experimental results are convincing. The authors' proposed modification to the generation process sounds reasonable and makes intuitive sense, but without definitive empirical proof it doesn't mean as much. In this case, I feel that the authors are able to demonstrate (despite the small scale) that their method is learning qualitatively better solutions (as evidenced by e.g. length generalization in Figure 4b). Of course, while it would be nice to see how things fare at scale, this is the first step. My philosophy is that if a change in the model only slightly increases metrics on synthetic tasks instead of showing clear separations, it isn't as interesting to scale it up. The experiments in this paper certainly indicate that something new is here, but the question of how it does at large remains open.", "weaknesses": "I think it is hard to decipher from the theorem statements (and also from the proofs, at least for me) exactly *which* types of problems are hard for unidirectional sequential models but easy for your type of model. Sudoku makes natural sense, and it was no surprise to see the proposed method do so well on that task. However, it feels like there is a big gap between the complexity-theoretic statements and what is demonstrated empirically. \n\nIn my life I have found it hard to convince people to run large-scale experiments to test modeling changes on the general basis of expressivity and larger capacity; for me it is always much more successful to have a crystal clear problem instance (such as modeling code with parenthesis, ...) where it is clear to demonstrate (both theoretically and empirically) that other methods fail and your method is the fix. Having an example/mascot problem like this gives you a kind of language to explore other problems in, and it helps tie together the different perspectives for your reader.\n\nReading this paper, I felt it difficult to really track the expressivity improvement between the theory and the experiments. The extra flexibility is clear to see intuitively, but the whole point of the theory + empirics is to qualify and quantify exactly what the gains of your method are. Sorry for the long rant, but my main point is that it would be more convincing and gratifying to read if the connections between the theoretical improvements and the experimental results could be explored at a finer scale.", "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": "txtnvkNxpP", "reviewer": "Reviewer_qEHt", "summary": "The paper introduces any-process masked diffusion (AP-MDM), a rewriteable-canvas variant of masked diffusion that augments the usual unmask head with insert, delete, remask, and stop decisions. It first argues, by construction and by complexity intuition, that autoregressive (AR) decoders and standard masked diffusion (MDM) share the same fundamental hardness on combinatorial and structured tasks: with a write-once canvas, you either pay exponential space (beams, branch caching) or exponential time (restarts). AP-MDM changes the computational regime: by allowing in-place edits and dynamic length, it turns generation into an anytime control process that can backtrack without storing branches. The formal upshot is polynomial working memory (space) with time that scales to instance hardness; you still do not beat worst-case exponential time, but you avoid the classic space blow-up of AR/MDM search.\n\nOn the learning side, AP-MDM keeps the strong denoising core of MDM but trains the edit heads via self-supervised surrogates (no ELBO over variable length) to remask, insert, delete, and halt. This decomposes hard global mapping into local repair decisions, which the paper shows is data-efficient in practice. At inference, a simple edit policy iterates these heads; compute is anytime and grows with problem difficulty. Empirically (Sudoku, Dyck/bracket languages, and related structure-heavy settings), AP-MDM achieves higher accuracy at much lower memory than AR or vanilla MDM under realistic budgets, illustrating the claimed time–space tradeoff: it “spends steps” instead of “storing branches.”", "questions": "1.\tA key implication is that the edit trajectory now matters, not just the final text. What should count as an optimal trajectory, and how should we obtain it: human or naturally logged edits for training, or algorithmic schemes such as minimum edit distance, maximum expected information gain per step?\n2.\tIf edit trajectories become first-class data, would you formulate any-process training with an ELBO? Do you see likelihood-based evaluation and probabilistic queries over edits becoming standard practice?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. Big-picture is spot on: AR and standard MDM appear different yet share the write-once-canvas weakness; the paper names it clearly and proposes a simple, natural fix drawn from code and biology, a rewriteable, variable-length canvas.\n2. Claims are precisely scoped; the contribution addresses space, not time. Framing the shift as N to NSPACE is apt; the constructions make the point transparent, and the proofs align with the reported experiments. More baselines/ablations (see weaknesses) would be welcome, but they are not necessary for credibility.\n3. The writing shows taste and control. The title and opening pose the question cleanly; the narrative moves from diagnosis to design to consequences with clarity; examples make the mechanism feel inevitable. I came away having learned a lot.\n4. The design is consequential. It introduces a generation scheme in which test-time compute scales via edits and dynamic length, with implications for training targets, halting criteria, and even what counts as a step in generative modeling.\n5. It lands at the right moment. Recent advances supplied the prerequisites: variable-length backbones that keep state coherent under edits (FlexMDM, DAEDAL), stable credit assignment and scheduling for where and when to edit (P2, ReMDM, R3), and practical stopping. This paper assembles those pieces into a coherent, learnable edit process.", "weaknesses": "1. No ELBO for edits + scheduling and halting schemes are opaque/potentially suboptimal: Learning relies on surrogate labels and augmentation design. The induced trajectories may not reflect human or task-native edit patterns, so calibration and likelihood reporting are unavailable. (see Questions below)\n2. Curious to see compute-normalized baselines (within space budget). With (possibly suboptimal) scheduling learned from augmentation and no cache of failures, how strong is AP-MDM beyond the space advantage? \n2. Would be interesting to ablate rewrite-only with sufficiently large generation length. This would clarify which ops carry the gains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)