The Serial Scaling Hypothesis
Authors: Yuxi Liu
Konpat Preechakul
Kananart Kuwaranancharoen
Yutong Bai
Venue: ICLR 2026 Poster (2026)
Keywords: Scaling Law
Computation complexity
Diffusion moodels
Primary area: learning theory
TL;DR: Serial scaling is just as important as parallel scaling in machine learning, though it has been undeservedly neglected.

Abstract: While machine learning has advanced through massive parallelization, we identify a critical blind spot: some problems are fundamentally sequential. These "inherently serial" problems—from mathematical reasoning to physical simulations to sequential decision-making—require sequentially dependent computational steps that cannot be efficiently parallelized. We formalize this distinction in complexity theory, and demonstrate that current parallel-centric architectures face fundamental limitations on such tasks. Then, we show for first time that diffusion models despite their sequential nature are incapable of solving inherently serial problems. We argue that recognizing the serial nature of computation holds profound implications on machine learning, model design, and hardware development.

Published as a conference paper at ICLR 2026
THE SERIAL SCALING HYPOTHESIS
Yuxi Liu'* Konpat Preechakul Kananart Kuwaranancharoen" Yutong Bai
UC Berkeley
IIndependent Researcher
ABSTRACT
While machine learning has advanced through massive parallelization, identify a critical blind spot: some problems are fundamentally sequential. These "inher- ently serial" problems from mathematical reasoning to physical simulations sequential socision-making requirr sequentially dependent computational steps that cannot efficiently parallelized. We formalize this distinction complexity theory, and demonstrate that current parallel-centric architectures face fundamental limitations on such tasks. Then, we show for first time that diffusion models despite their sequential nature incapable of solving inherently serial problems. We argue that recognizing the serial nature of computation holds profound implications machine learning, model design, and hardware development.
INTRODUCTION
The scaling up of machine learning has driven remarkable progress (Achiam al., 2023; Hoffmann et al., 2022; Dosovitskiy et al., 2021; Kaplan et al., 2020; Krizhevsky et al., 2012), much this has come from parallel scaling: hardware shifted from CPUs to massively parallel GPUs, architectures moved from RNNs to highly parallelizable Transformers, and algorithms increasingly exploit parallel compute (Dao, 2024; Chowdhery et al., 2023; Jouppi et al., 2017). But some problems stubbornly Kazemi et al., 2025; Li et al., 2024: Merrill & Sabharwal, 2023b; Marcus, 2018; Chollet, 2019): for class of tasks, only scaling serial computa- tion allowingg models to perform more sequential steps yields further progress. It seems not all scaling created equal.
resist such advances (Aggarwal & Welleck, 2025;
The necessity of deep or sequential models for some problems has remained mostly theoretical (Telgarsky, 2016; Merrill & Sabharwal, 2025; Chen et al., 2024a). Only recently has scaling test- time computation become recognized, independently of train-time computation (Snell et al., 2024; OpenAI, 2024; Wu et al., 2025). Yet this dichotomy still overlooks the role of parallel vs. serial computation, which is central to this paper. The literature on scaling still commonly reports both parameter counts and computation FLOPPs each as a single number, treating width (parallel) and depth (serial computation) interchangeably (Kaplan et al., 2020; Hoffmann et al., 2022; OpenAI, 2024: Snell et al., 2024).
Consider Sudoku-a number-placement puzzle requiring each number 1-9 to appear once per row, column, and subgrid as parable (Figure 1). Easy puzzles be solved by filling in many blanks independently, in parallel. Hard puzzles, however, require long chain of dependent reasoning: each blank depends on the others. No algorithm can shortcut the process.
9
2
2065
4
5
8
7
2
6
3
7
2
8
9 5
8
Solving many easy puzzles may cost the same total com- putation solving single hard one, but only the easy ones can be sped up with more processors. This distinc- betwen problems that are "wide" (parallel) and those that are "deep" (inherently serial)-is fundamental, yet it is underappreciated in machine learning.
Figure I: (Left) Many easy Sudoku puz- zles, where the circled blanks can be filled independently in parallel. (Right) A hard Sudoku with the same total com- pute, but the circled blanks interde- pendent, requiring sequential reasoning.
"qqual contribution.

---

Published as a conference paper at ICLR 2026
The Serial Scaling Hypothesis (SSH)
For many important MI. problems such as reasoning, decision making, and modeling dynamic systems, increasing parallel computation alone is insufficient. Progress requires scaling the amount of serial computation.
The appeal of this hypothesis is that it is both theoretically sound and practically relevant:
Complexity theory proves some problems parallelize efficiently, while others do not (Greenlaw et al., 1995).
Grounded in theory:
Explains past successes: The breakthrough of deep learning came from increasing network depth (LeCun et al., 2015; Prince, 2023), and Shtain-of-Thoueee (CoT) improves performance by adding more serial steps (Kojima et al., 2022; Li et al., 2024; Merrill & Sabharwal, 2024).
Connects practice: The parallel-serial lens connects well to practice. Formal results show bounded serial capacity in Transformers (Merrill & Sabharwal, 2023b) and expanded capacity with CoT (Li al., 2024; Merrill & Sabharwal, 2024), matching empirical gains (Aggarwal Welleck, 2025; Muennighoff et al., 2025). Our new analysis extends this picture to diffusion: despite thousands of iterations, diffusion models with a TC backbone have only constant computation depth, consistent with observed step-count plateaus (Ma et al., 2025; Ravishankar et al., 2024).
Why does this matter for machine learning? As we push toward more challenging aassseavvanced reasoning, physical simulations, planning, and scientific discovery- encounter problems that parallel architectures (like Transformers and diffusion models) cannot efficiently solve. Recognizing this has several implications:
Model: Should revisit architectures that allow for deeper sequential computation?
Hardware: Is it time to invest in faster, lower-latency processors, not just more parallel ones?
Task analysis: Can some inherently serial tasks be reformulated into other tasks with reduced serial structure, while remaining useful in practice?
Contributions. We (i) introduce the Serial Scaling Hypothesis (SSH), (ii) prove that diffusion models, despite many iterative steps, have limited serial capacity, (iii) prove that certain Markov decision problems require serial computation for good decisions, (iv) identify machine learning problems where serial computation is essential, and (v) discuss SSH implications for machine learning.
MACHINE LEARNING FROM THE SERIAL PERSPECTIVE
We first formalize inherently serial problems (Section 2.1), show they are not only theoretically valid but also pervasive in machine learning (Section 2.2). We then examine why predominant MI models struggle with these tasks (Section 2.3). Finally, we discuss broader implications for MI. (Section 2.4).
2.1 COMPLEXITY FRAMEWORK FOR INHERENTLY SERIAL PROBLEMS
We focus our attention on binary decision problems which take in input tokens and output either "yes" or "no" as depicted in Figure 2(A). While seemingly limited, this framework includes all problems with discrete responses, since making a discrete choice out of 2" options is equivalent to answering yes/no questions. Figure 2 (C-E) show how cellular automata, many-body mechanics, and open-ended question answering can be represented in this way.
We adopt the complexity class TC (Threshold Circuits) to formally distinguish between serial and parallel problems, since is the standard theoretical framework that formalizes the serial-parallel divide, and has strong connections neural networks.
Definition 2.1 (Informal, see Appendix D). A problem is in TC¹ if, for inputs of size N, it can be solved by a Boolean eircuit with polynomial width and polytogaii depth, using basic logic gates (AND, OR, NOT) plus majority gates. The class TC is the union of all such TC¹ for i 0.
2

---

Published as a conference paper at ICLR 2026
A)
Yes/No
Yaur
Input:
Problem
Cellular automaton (Rule 30)
X
N
Output:
Y261
Problem has variable size input. and fixed-size output.
X,T))
xy(T)
Input 1: (, Xz(O), X₃(0)
Input seconds
B)
Many-body mechanics
X2(O)
Xa(O)
Xa(O)
Deeper More-stop model (Grow with problem size)
X
X,X3
X,/01
X-(T)
XaT) Xx(T)
Input:
baseball together
The bet costs $1 21.00 more than the ball.
Math question answering
What is the price of the ball?
A Serial problem requires more "depth" that grow with problem size solve.
Output: $0.05
baseball
and
Figure (A) decision problem has variable-size imput and a fixed-size output (e.g.. "yes"/'no") (B) A serial problem requires deeper or more steps as the problem size grows. Examples of serial problems are: (C) Cellular automaton: takes the initial state input and outputs a discrete value of the row N at cell for i E (1...., 2N 1}. (D) Many-body mechanics: takes initial positions and momenta of each particle with time T as inputs and outputs the particle locations at time T' in a limited-precision space. (E) Math QA: takes question input and outputs the answer autoregressively, with each output from a fixed set of possibilities.
Intuitively, problem belongs to TC if and only if it can be solved by a multilayer perceptron (MLP) with polynomial width and polylog depth, where polylog denotes poly N) (Parberry & Schnitger, 1988). A problem belongs TC if and only if it be solved by constant-deptl MLP. We consider TC problems as parallel problems, since there are sublinear-depth MLPs that solve them.
Although the universal approximation theorem (Cybenko, 1989; Hornik et al., 1989) shows that 3-layer MLP with unbounded width approximate any continuous func- tion, a constant-depth MLP with only polynomial width far more limited, capturing only problems TC
All Problems
Outside
Inherently serial
Parallel
TC TC¹
A common phenomenon in computational complexity is that one can make neural network shallower at the cost of exponentially larger width (Valiant, 1983; Hajnal al., 1993; Sherstov, 2007; Williams, 2014; Oliveira & San- thanam, 2015; Eldan & Shamir, 2016; Liang & Srikant, 2016; Cohen et al., 2016; Telgarsky. 2016: Merrill & Sab- harwal, 2025). However, such exponential are intractable in both memory and computation. We consider them as inefficient solutions in this paper. This exponential depth-width trade-off underlines the impor- tance characterizing neural networks depth and width separately, which motivates the Serial Scaling Hypothesis.
TC
networks
Figure 3: The complexity classes nested TC TC² c... TCC P. Each containment widely believed to be strict. Problems in TC are parallel, while those outside are inherently serial.
To formally characterize the problems terms of depth, we have the following definition:
Definition 2.2. problem P is parallel E TC; otherwise, it is inherently serial.
Assumption 2.3. We adopt the widely held belief that TC C that is, some polynomial time problems are inherently serial (Greenlaw et al., 1995, Ch. Ch. 8).

---

Published as a conference paper at ICLR 2026
2.2 REAL-WORLD PROBLEMS ARE LIKELY INHERENTLY SERIAL
A natural objection to theory: "Do such theoretical obstructions to parallelism arise in the real world?" We say: Yes part-cuaalllllll if one works in domains involving the need for physical simulation or reinforcement learning. But even outside these areas, it remains highly likely that one will encounter inherently serial problems. Even apparently simple tasks with polynomial-ting algorithm can be inherently serial (Assumption 2.3).
Drawing from both empirical observations and theoretical arguments presented in the following Section 3, we propose the following tomplexityttheoreii hypothesis:
Hypothesis 2.4
The following problems-cellube automata evolution, many-body mechanics, sequential decision problems, mathematical question answering are inherently serial.
Inherently serial problems (see Definitions 2.1, 2.2) exhibit fundamental computational dependencies: the outcome of intermediate steps directly influences subsequent steps in ways that cannot be shortcut without compromising correctness. To make this intuition rigorous, we prove new theorem (Theorem G.2) on inherent seriality in sequential decision making.
Limitations. (1) These arguments apply to the general (worst-case) complexity of the problems. A problem may be inherently serial in general, but parallel algorithm may cover most specific instances occurring in practice. (2) An inherently serial problem may be solved approximately in parallel to accuracy acceptable for practical use.
2.3
ARE OUR MODELS CAPABLE OF SOLVING INHERENTLY SERIAL PROBLEMS?
Most modern architectures are designed for scaling parallel computation. Transformers and state-space models (SSMs) (Gu et al., 2021; Gu & Dao, 2023), though often called "sequence" models, process all available input parallel. This raises crucial question: "How efficiently do they solve inherently serial problems?"
Solve serial problem?
Method
ParalleI?
FF MLPs
X
FF Transformers
FF SSMs (Mamba)
X
RNNs
X
Repeating layers
Chain-of-Thougl
/
Prior work shows that for fixed fixed-depth, polynomial width, and precisiecii various architectures, including MIPs, Transformers, and linear SSMs, all collapse into constant-depth threshold circuits (TC") (Merrill et al., 2022; Chiang, 2024; Chen et al., 2024b; Merrill et al., 2024). Intuitively, their computational graphs all collapse into constant par- allel steps, never requiring long sequential chains. chitectures themselves. A model, however, is the combination of both architecture and inference procedure. Thus, while transformer architecture lies in TC", Transformer model run with serial inference-such as autoregressive CoT ceturrence-extntie beyond TC and can capture inher- ently serial computations (see Appendix C.I). Table summarizes computational characteristics of common machine learning models.
Diffusion models
X
X
(TC² backbone)
Table 1: Parallelizable models are limited to par- allel problems. Only non-pan con-paalleelzable models may solve inherently serial problems. FF stands for Feedforward.
Importantly, these results characterize the ar-
Diffusion models cannot solve inherently serial problems. A key contribution of the present paper new theorem (Theorem F.2) on the limitations of diffusion modeling. Although the step-by -t--epp sampling of a diffiusion model appear serial, we prove in Section 4 that diffusion model with TC backbone remains in TC even with infinitely many sampling steps. Thus, despite their stepwise structure, diffusion models are incapable of solving inherently serial problems.
By linking the computational limits of modern MI models with the inherently serial structure of many key problems, we arrive at the following conclusion:
While diffusion models are not yet parallelizable, given their TC capabilities, there might exist paral- lelization algorithm for diffusion models.
4

---

Published as a conference paper at ICLR 2026
Key Limitation of Modern Machine Learning Models
MLPs, Transformers, SSMs, and diffusion models with TC backbones are provably inca- pable of solving general instances inherently serial problems such as cellular automata evolution, many-body mechanics, sequential decision-making, and mathematical question answering.
Limitations. (1) Certain instances of serial problems may be trivial or admit parallel solutions;
seriality holds only the general case. (2) For problems beyond (e.g.. NP \ P), exponential computation- not serial dimputtioonnddmiattes. Thus, the Serial Scaling Hypothesis applies most directly to problems of practical real-world difficulty.
2.4 IMPLICATIONS OF THE SERIAL SCALING HYPOTHESIS
For machine learning practitioners. Many important real-world problems-such cellular automata, many-body mechanics, and sequential Dacciion-mmking-aaa are inherently serial. Without sufficient serial computation, solving them with shallow models requires an exponentially large set of weights, which in turn demands exponentially large datasets to train. Neither is affordable in practice. This dismatch-soovvie
inherently serial problems using shallow or parallel models-helps explain why many ML systems generalize poorly beyond their training distributions (Torralba & Efros, 2011; Zhang al., 2017: Recht al., 2019; Liang al., 2023; Mancoridis al., 2025; Zhang et al., 2025).
Evidence from RL fine-tuning (Wang et al., 2025b; Yue et al., 2025; Shao et al., 2025) suggests that LLMS already acquire both shallow heuristics (fast but memorization-like (Nikankin et al., 2025)) and deeper algorithms (slower but more general) during pretraining. However, if the inference-time compute budget is set too low, the model defaults to the shallow routines, producing fast but brittle behavior. Only with sufficient serial computation, the deeper routines can be executed resulting in better generalization.
For task & benchmark designers. Recognizing the inevitable cost to inherent seriality, serial problems may be reformulated into coarser or approximate problems to reduce serial depth to acceptable levels while remain practically useful. For RI. truncated value functions cap the effective depth while retaining theoretical guarantees and practical utility (Park et al., 2025; Sutton & Barto, 2018; De Asis et al., 2019). For reasoning, complexity theory shows that coarse decision problems can be tractable even when exact solutions are not-for example, primality is in P while factoring remains hard (Agrawal et al., 2004).
In addition, benchmarks should have inherently serial problems as a separate category, to distinguish serial and parallel scaling in model performance.
For model designers. Solving these challenging real-worls problems may require recurrent struc- tures that increase serial computation alongside today's 's predominantly parallel designs. However, recurrence and depth often amplify gradient variance (Bengio et al., 1994; Pascanu et al., 2013) and L-Lipschitzness (Bartlett al., 2017; Fazlyab al., 2019), making models harder to train. This motivates improved training techniques and novel architectures such as implicit gradients (Wang et al., 2025a), XLSTM (Beck al., 2024), and test-time training (Sun et al., 2024).
For hardware designers. Massively parallel computing machinery, especially GPU clusters, enabled past progress deep learning. Future progress in machine learning and computing general? also depends on progress in high-clockrate, sequential computing machinery, with reduced data movement overhead (Kang et al., 2021; Kaur et al., 2024). concrete example is wafer-scale hardware (c.g.. Cerebras CS-3), which prioritizes extremely high on-chip memory bandwidth (Wang, 2025).
2.5 RELATED WORKS
Our hypothesis is similar to the "parallelism tradcoff" hypothesis- all parallelizable models, irrespective of design, must necessarily fail to solve inherently serial problems (Merrill Sab- harwal, 2023a;b). Our work builds on classical complexity theory, including the "depth-width
Ammdall's 's law (Amdahl, 1967; Gustafson, 1988) shows that seriality is hard upper bound on speedups achievable by parallelism.
5

---

Published as a conference paper at ICLR 2026
tradeoff" (Vishkin & Wigderson, 1985). the "work" vs. "depth" contrast Blelloch (1996), P- completeness (Greenlaw et al., 1995, Ch. 8), and computational irreducibility (Wolfram, 2002).
While these ideas well-established in complexity theory, work brings them into the machine learning context- exxtending them to real-world tasks such as sequential decision making and question answering, and highlighting the gap between these tasks and the limited serial capabilities of modern machine learning models.
3 SERIAL PROBLEMS
In this section, we highlight representative inherently serial problems: cellular automata (Section 3. 1), physical systems (Section 3.2), and complexity -hheortct hardness results (Section 3.3), as well as practical domains such as sequential decision making (Section 3.4) and reasoning QA (Section 3.5). These cases illustrate serial bottlenecks that readers may encounter in other domains.
Rule 110
Initial
3.1 CELLULAR AUTOMATA
We begin with predicting the outcome of cellular automata (CA) (Sarkar, 2000; Codd, 2014), shown in Figure 2(C), as a simple problem that is inherently serial. CA is grid of cells, each in of finitely many states, updated in discrete steps according to a local rule based on its neighbors. Despite this simplicity, CA can exhibit behaviors ranging from predictable to complex dynamics such as Rule 110 (Figure 4), which hints inherent seriality of this problem.
Cellular automata are inherently serial. Rule 110 has been proven (Woods & Neary, 2009), so computing the state of cell v; at row N requires simulating each step in sequence, without shortcuts (Greenlaw et al., 1995, p. 58). This is not unique Rule 1 110 many CA problems are P-complete (Moore, 1997), i.c., not efficiently parallelizable.
Figure 4: A single run of Rule 110. Given the top row, the CA evolves row-by-row according to the 8 rules.
What does this mean? Even systems governed by just 8 simple rules can forbid shortcuts.
3.2 MANY-BODY MECHANICS
The previous section showed that inherent seriality can arise even in systems governed by a handful of local rules. We now turn more realistic setting: Newtonian many-body dynamics.
Consider N particles evolving in Rd under forces and/or hard collisions. Given initial positions and momenta O, the goal is predict the particle positions some later time = T in finit-- precision representation, which reflects practical scientific computation; with unbounded precision, the prediction problem becomes PSPACE-hare This the instance depicted in Figure 2(D).
Many-body mechanics is inherently serial. Classical mechanics is expressive enough to emulate arbitrary computation. The billiard-ball computer of Fredkin & Toffoli (1982) recreates any Turing machine using nothing but billiard balls elastically reflecting off each other and walls, and Moore (1990) proposes a similar recreation using smooth particle motion a potential field in R3, Since problem of simulating general Turing machines is inherently serial (Greenlaw et al., 1995, p. 58), an algorithm that accurately simulates general physical systems can only be done step by step.
Seriality in video prediction. Because vidcos capture inherently serial dynamics, such collisions, forecasting the next frame from a sequence N frames is similarly inherently serial. This task underlies large-scale models for content creation (DeepMind, 2025; Brooks et al., 2024; Wan et al., 2025) and decision making (Bar et al., 2025; Yang et al., 2024).
The computational difficulty in video prediction does not come from the cost of rendering single next frame. If a model maintains a complete world state (c.g., object positions and momenta), stepping that state forward is as efficient applying local physical law. The problem arises when

---

Published as a conference paper at ICLR 2026
losing track on the state: recomputing it requires replaying the chain of many- body mechanics from the last reliable observation, thus inherently sequential.
In real videos, objects frequently leave the field of view become occluded, as illustrated in Figure 5. Current large-scale video pre- typicall- Transformer-basee and trained with next-frame objectives- are optimized only for immediate reconstruction, As result, they are not encouraged maintain the state of occluded objects. This can lead to an incomplete world state, effectively ren- dering the task inherently serial and no longer solvable a single for- ward pass by the model. This may help explain why state-of offee-of-iee of-the-art video generators often produce physically inconsistent results (Kang et al., 2024; Brooks et al., 2024; Wan et al., 2025).
Input
(=
Input
[= T/2
Out of view
Yew
Output (= T
What does this mean? Tasks involving the modeling of system dy- namics, including physical simulations and video prediction, likely require serial models to be efficiently solved. For video prediction, the model must maintain the full evolving world state.
Figure 5: Predicting the frame at time T. The intermediate frames may not be observable by camera motion/acclusion.
3.3 P-COMPLETE PROBLEMS
The inherently serial problems given previously have this in common: Given a problem statement of size (nn), it immediately obvious how to construct linear computational graph of length (n). such that each node of the graph depends, and only depends, on the previous ones, and each step takes constant time. This matches the intuition of what being "serial" means.
Such problems have been formalized as P-complete problems, of which the most prototypical one the Circuit Value Problem (CVP) (Ladner, 1975): Given Boolean circuit with single output bit, specified as a graph of logic gates and their connections, and an input binary string, what is the output bit? The CVP robust in that many variations remain P-complete (Greenlaw et al., 1995).
The obvious solution is to perform a topological sort (takes ((n) time) on the graph of the logic gates, so that each gate depends only on the output values of the previous gates, then evaluate them serially. The CVP embodies the intuition of what an inherently serial problem should be, which that each step easily depends on the previous steps, but skipping steps is difficult. Since any problem is efficiently reducible to the CVP. it is P-complete.
This gives us an intuitive rule: If the problem appears to have a linear computational graph similar to the CVP, then it is likely inherently serial. Indeed, this intuition guided in proving the theorem in Section 3.4. Furthermore, an extensive list of problems is shown to be P-complete (Greenlaw et al., 1995), thus suggesting that inherently serial problems are common in the wild.
3.4 SEQUENTIAL DECISION PROBLEMS
The goal in sequential decision problems is to obtain an optimal policy x² (s) = arg max, (TT). where J(Tr) the expected return under policy и a Markov Decision Process (MDP) with finite horizon N, and discount factor [0. 1]. Therefore, given a state the policy outputs an optimal action a from a limited possibilities (diserete action) or with finite precision (continuous action). There are two aspects in this: finding policy, and executing policy.
Executing a policy inherently serial. In Appendix G, we construct certain MDPs and prove that in these, any approximutely optimal policy is inherently serial.
Finding policy is inherently serial. Consider policy gradient methods (Sutton et al., 1999; Williams, 1992). including popular variants like PPO (Schulman et al., 2017), widely used in applications such as LLM fine-tuning (Ouyang et al., 2022).
In policy gradient, the parameters of policy model are improved via gradient descent on return estimates, which must be unbiased for convergence to the optimal policy?. Here, we show how an
Convergence to suboptimal policies is still possible with biased return estimates (Mu & Klahjan, 2024; Tian al., 2023).
7

---

Published as a conference paper at ICLR 2026
unbiased return estimation is inherently serial, implying that with parallel estimation the optimal
policy is not guaranteed.
Humanoid
Ant Big Maze
Arm Push Easy
750
030
-500
10
Time at Goal
$20
nodes
302
-1000
-1500
10a
150
230
2000
302
150
200
50 75
100
50
100
The dep
Ene cap (M)
Dre stop
10
10
10t4
Tain FLOP
10th
10th
1017
109
Wilit 256
Wist 120
Widhh 1024
Whdth-332
Width-2045
Withh-4056
Desth (width-2235)
Deoth din- 2561
(a) MCTS in Hex board game: Performance improves with more MTCS expansion nodes across all training regimes. Perfect play only possible with test-time MCTS. Data from Villalobos & Atkinson (2023).
(b) Actor & critic networks' depth vs. width in locomotion & manipulation. 2x deeper network (8 layers, width 256) outperforms a 16x wider network (4 layers, width 4.096) in Humanoid, locomotion task with largest observation action spaces among the three. Data from Kevin et al. (2025).
Figure Empirical serial scaling on (a) Hex board game and (b) locomotion & manipulation.
parallel return estimation possible, one must be able to access state i (and thus reward r2) in fewer than linear function of i steps. This is unlikely in real-world MDPs, since even simple CA transition rules (Section 3.1) or physical interactions (Section 3.2) prevent such shortcuts*. While scaling parallel computation via aggregating multiple trajectories can accelerate convergence by reducing variance (Sutton Barto, 2018, p. 93), accurate return estimation still requires serial computation.
This inherent seriality motivates model-based reinforcement learning, where returns are computed by unrolling an internal model step by step. For instance, Monte Carlo Tree Search (MCTS) which increases serial computation via tree expansion and reduces return-estimation bias-hat achieved superhuman-level performance in diverse board games (Silver et al., 2016; 2017; Schrittwieser et al., 2020). Villalobos & Atkinson (2023) demonstrate consistent improvements in Hex from increasing MCTS expansion nodes (see Figure 6a). Even in model-free RI,, adding serial computation with deeper networks significantly outperform wider (more parallel) ones locomotion tasks Kevin et al. (2025) (see Figure 6b).
What does this mean? Parallel computation cannot substitute for serial computation in RL. Without sufficient serial computation, the optimal policy is not guaranteed.
65.0%
3.5 REASONING QUESTION ANSWERING
60.0%
Instead of going through an MDP as in RI., math question answering exhibits seriality through step-by-step logical reasoning, irrespective of the answer length, before ar-
55.0%
Tokans (per rolout)
50.0%
3600
45.0%
2048
riving at the solution. As shown in Figure 2(E), given question as input tokens, the model autoregressively gen- erates the solution, each step from a limited set of tokens.
40.0%
1024
35.0%
512
512
2K
8K
32K
Math QA is likely inherently serial. Solving grade- school mathematics, GSM8K (Cobbe et al., 2021). which has been used benchmark reasoning capabilities in LLMs, can be formalized as dependency graphs (Ye al., 2024). solution is to traverse the graph in topological order and perform necessary arithmetic operations sequen- tially (Ye et al., 2024). This resembles the Arithmetic Circuit Value Problem (Greenlaw al., 1995, p. 124), a generalization of the standard CVP to arithmetic operations. Like CVP, this problem is P-complete- is, inherently serial. Since
Tokens (total)
Figure 7: Average benchmark scores over math benchmarks for longer rea- soning chains (in different colors) vs. majority voting (as dots along each line). Data from Aggarwal & Welleck (2025).
As usual, there is an exponential tradeoff available. One can randomly generate a trajectory and check its consistency with the MDP and policy in parallel, but the expected number of trajectories needed hefore consistent one found grows exponentially with length n.
8

---

Published as a conference paper at ICLR 2026
seriality arises even in simple math QA, it likely extends to advanced benchmarks such as AIME and Olympiad-benan bench, where finding the correct approach is hard.
In mathematics QA, shown in Figure 7, Aggarwal& & Welleck (2025) demonstrate that sequential scaling with longer reasoning chains consistently outperforms parallel scaling via majority voting controlled for the same token budget. This pattern holds across mathematical datasets of varying difficulty, including AMC, MATH, AIME, and Olympiad- -bench.
Similarly, science QA also appears to exhibit inherent seriality. Muennighoff et al. (2025) report that in GPQA Diamond (Rein et al., 2024), a QA benchmark on PhD-level science, sequential scaling yields consistent accuracy improvements, only limited by the model's context window, and is significantly more efficient than parallel scaling (via majority voting), which plateaus.
What does this mean? Complex question answering similar math QA likely requires constructing answers step by step over a computation graph, and thus inherently serial.
4 DIFFUSION MODEL'S 's COMPUTATION IS NOT SERIAL
The Serial Scaling Hypothesis provide a lens to look at machine learning from serial crrial-prrallel lens. We have examined serial machine learning problems. We now turn to a diffusion mod-
Output
Diffusion model (TC* backbone)
els (Ho et al., 2020; Song et al., 2021; Song & Ermon, 2019), widely used in image/video generation (Brooks et al., 2024) and other vision tasks such as depth estimation (Saxena et al., 2023), and language modeling tasks (Li et al., 2022; Nie et al., 2025; Arriola et al., 2025). While commonly thought as a serial model, we show here for the first time that they are not.
X,
X;
X
Output
Figure 8: The backbone network takes as input sequence of tokens, and a single noisy output token. This is repeated until the output to- ken is fully denoised.
Consider a problem with input Zi...., IN and fixed output JN++1 (as in Figure 2). A diffusion model uses a backbone neural network 0 which takes the inputs and a noisy version of IN+1, denoising over T steps until it becomes the output (see Figure 8). This models the conditional distribution Ptruch N# F1...., IN) or concisely Prrth-
While the number of denoising steps T is scalable-more denoising steps for finer approximation of Pruth in practice, diffusion models converge rapidly (Ma et al., 2025). For instance, image generation plateaus at 300 steps (Nichol & Dhariwal, 2021). depth estimation shows little difference between 5 and 100 steps (Ravishankar et al., 2024), and language modeling yields similar perplexity for 32 vs. 1024 steps (Austin et al., 2021). With distillation, 1-4 steps suffice without much loss (Yin et al., 2024; Liu et al., 2024; Song et al., 2023; Lin et al., 2024; Salimans & Ho, 2022). Such rapid convergence suggests that the effective computation depth of diffusion models is low. would be surprising if the underlying computation were truly serial.
Diffusion models with a TC backbone can only solve problems in TC², Previous work showed that a backward diffusion process converges to Po at the rate TV = (dd/T) (Li Yan, 2024, Thm. 1), where TV is the total variation between Po and the denoising Pe, o. and d is the intrinsic dimension of N1 Building on top of it, we obtained the following theorem, the formal statement and proof of which are in Appendix F:
Theorem 4.1 (Informal). Ifa problem can be solved by a diffusion model with a TC" buckbone with high probability with infinite diffusion steps. then the problem itself is in the parallelizable class TC
What does this mean? Diffusion models only provide a constunt amount of additional serial computation. The above theorem precludes the use of diffusion models as a scalable means of increasing serial computation. Unlike CoT, which genuinely adds serial compute (see Appendix E), diffusion models do not. This may explain the empirical mediocre performance of diffusion language modeling as output length increases (Austin et al., 2021: Lou et al., 2024; Guirajani & Hashimoto, 2023; Sahoo et al., 2024).
Limitation. The theorem doesn't 't apply: (1) If solution space grows in intrinsic dimension. (2) If the backbone is either poorly trained or trained under a different objective. This leaves open the possibility of serial-compurte-scllallee generative models beyond score-based diffusion.

---

Published as a conference paper at ICLR 2026
5 ACKNOWLEDGEMENTS
We thank Alexei Efros, whose critiques of deep learning theory helped ground us and motivated us make this paper friendlier to non-theoreticians. We are grateful William Merrill and Anant Sahai for their invaluable technical feedback and corrections that significantly strengthened our theoretical analysis. We also thank Angjoo Kanazawa, Justin Kerr, Amil Dravid, Yossi Gandelsman, and Yuatyong Chaichana for their thoughtful comments and suggestions that helped improve the clarity and presentation of this work. This work is partially supported by the ONR MURI N00014- AI Berkeley from
21-1-2801. YL was supported by gift to the Center for Sluman-Compitn Coefficient Giving (formerly Open Philanthropy) during the development of this work.
REPRODUCIBILITY
No new data code has been used to support this paper. Some new theorems are introduced in this paper, and their proofs are in the appendix.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
Pranjal Aggarwal and Sean Welleck. LI: Controlling how long reasoning model thinks with reinforcement learning. arXiv [es. CLJ, 6 March 2025. URL http:// wwtpaaaaw........a....../../oo.a abs /2003. 04697.
Manindra Agrawal, Kayal, and Nitin Saxena. PRIMES is P. Annals of Mathematics, 160: 781-793, September 2004. URL http://ddx doi 781.
wow. org/10. 4.0.400077/0 ANNALS 2004. 160.
Gene M Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the April 18-20, 1967, spring joint computer conference, pp. 483-485, 1967.
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 arXhv:2503.09573 2025.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in neural information processing systems, 14:1998-- 2021.
Amir Bar, Gaoyue Zhou, Danny Tran, Trevor Darrell, and Yann LeCun. Navigation world models. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), 2025.
Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalizzd margin bounds for neural networks. In Advances in Neural Information Processing Systems, 26 June 2017.
Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. XLSTM: Extended long short-term memory. arXiv [cs.LG), 7 May 2024. URL /LLL:tpp/aaxx...czz/a///////2// 04517.
Bengio, P Simard, and P Frasconi. Learning long-term dependencies with gradient descent difficult. IEEE Trans. Neural Netw,, 5(2):157-166, 1994. URL http:://px..xoo/ doi. org/ 11 1199/72.279181.
Guy E Blelloch. Programming parallel algorithms. Communications of the ACM, 39(3):85-97, 1996.
10

---

Published as a conference paper at ICLR 2026
Andrej Bogdanov, Luca Trevisan, al. Average-case complexity. Foundations and Trends@) in Theoretical Computer Science, 2(1):1-106, 2006.
Tim Brooks, Bill Peebles, Connor Holmes, Will DePue, Yufei Guo, Li Jing, David Schnurr, Joe Taylor, Troy Luhman, Eric Luhman, et al. Video generation models as world simulators. OpenAl Blog, 1:8, 2024.
Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer. arXiv preprini arX1v:241..02975. 2024a.
Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. The computational limits of state-space models and mamba via the lens of circuit complexity. arXiv preprint arXiv24//2.06/48, 2024b.
David Chiang. Transformers uniform TCO. arXiv preprint arXiv:2409. 2024.
François Chollet. On the measure of intelligence. arXiv [cs.Al], 4 November 2019. URL http:
//arxiv. wwtp://ggggaaaaaeoeee.oo httg///b//19111 /1911. 01547.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchrr Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv [cs.LG], 27 October 2021. URL htttp://arxe org/ abs 2110. 14168.
Edgar F Codd. Cellular automata. Academic press, 2014.
Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: tensor analysis. In Conference learning theory, pp. 698-728. PMLR, 2016.
Stephen A. Cook, A taxonomy of problems with fast parallel algorithms. Information and Control, 64(1-3):2-22, 1985.
G Cyhenko. Approximation by superpositions of a sigmoidal function. Math. Control Signals Sys- tems, 2(4)3303-314 December 1989. URL https : htt////w..tt../////////////// njit leriiii.dduuusssattaa edu/~usmanncourrse/
2s677_fal118/// 1.1.. 441. 7873, .ddf.
Tri Dao. FlashAttention-2:: Faster attention with better parallelism and work partitioning. In International Conference on Learning Representations (ICLR), 2024.
Kristopher De Asis, Alan Chan, Silviu Pitis, Richard Sutton, and Daniel Graves. Fixed-horizon temporal difference methods for stable reinforcement learning. arXiv [cs.LG], 9 September 2019. htLp://////axtt org/ abs 1909. 03906.
Google DeepMind. Genie 3: A new frontier for world models. /eepm//d/d google/ discover hwwp://llo/////oo genie- 3 --new- foww-feoniirr... Cor-worlde modeld/ August 2025. Accessed: 2025-8-5.
Josep Díaz, Maria Serna, Paul Spirakis, and Jacobo Torán. Paradigms for Fast Parallel Approxima- bility. Cambridge University Press, Cambridge, 1st edition, 1997.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations (ICIR), 2021.
Ronen Eldan and Ohad Shamir. The power depth for feedforward neural networks. In Conference learning theory, pp. 907-940. PMLR, 2016.

---

Published as a conference paper at ICLR 2026
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in Neural Information Processing Systems, 11 June 2019.
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:70757-70798, 2023.
Edward Fredkin and Tommaso Toffoli, Conservative logic. Int. Theor Phys. 21(3-4)221--553, April 1982. URL http:////// wttp::........../////.....
Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, New York, 1995. ISBN 0-19-50859144
Albert Gu and Tri Dao. Mamba: Linear-ting sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752 2023.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces, arXiv preprint arXiv:2111.00396, 2021.
Ishaan Gulrajani and Tatsunori B Hashimoto. Likelihood-basee diffusion language models. In Advances in Neural Information Processing Systems, 30 May 2023.
John Gustafson. Reevaluating amdahl's law. Communications of the ACM, 31(5):532-553 1988.
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold circuits of bounded depth. Journal of Computer and System Sciences, 46(2): 129-154, 1993.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, 19 June 2020. URL 2006 11239.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13-30, 1963.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556 2022.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Netw. 2(5):359-366, January 1989. URL https: // //cognit ineggniiiveeeiiii
vewedi um. com/
Norman P Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, Rick Boyle, Pierre-Lue Cantin, Clifford Chao, Chris Clark, Jeremy Coriell, Mike Daley, Matt Dau, Jeffrey Dean, Ben Gelb, Tara Vazir Ghaemmaghami, Rajendra Gottipati, William Gulland, Robert Hagmann, C Richard Ho. Doug Hogberg, John Hu, Robert Hundt, Dan Hurt, Julian Ibarz, Aaron Jaffey, Alek Jaworski, Alexander Kaplan, Harshit Khaitan, Andy Koch, Naveen Kumar, Steve Lacy, James Laudon, James Law, Diemthu Le, Chris Leary, Zhuyuan Liu, Kyle Lucke, Alan I Lundin, Gordon MacKean, Adriana Maggiore, Maire Mahony, Kieran Miller, Rahul Nagarajan, Ravi Narayanaswami, Ray Ni, Kathy Nix, Thomas Norrie, Mark Omernick, Narayana Penukonda, Andy Phelps, Jonathan Ross, Matt Ross, Amir Salek, Emad Samadiani, Chris Severn, Gregory Sizikov, Matthew Snelham, Jed Souter, Dan Steinberg, Andy Swing, Mercedes Tan, Gregory Thorson, Bo Tian, Horia Toma, Erick Tuttle, Vijay Vasudevan, Richard Walter, Walter Wang. Eric Wilcox, and Doe Hyun Yoon. In-datacenter performance analysis of tensor processing unit. In Proceedings of the 44th Annual International Symposium on Computer Architecture, 16 April 2017.
Bingyi Kang, Yang Yue, Rui Lu, Zhijie Lin, Yang Zhao, Kaixin Wang, Gao Huang, and Jiashi Feng. How far is video generation from world model: A physical law perspective. arXiv [cs.CV], 4 November 2024. URL http: / / //tp/a/avvvv/////ee/eee//aa org abs///////44// 2411 02385.
12

---

Published as a conference paper at ICLR 2026
Hongbo Kang, Phillip B Gibbons, Guy E Blelloch, Laxman Dhulipala, Yan Gu, and Charles McGuffey. The processing- in-merrr model. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, volume 1, pp. 295-306, New York, NY, USA, 6 July 2021. ACM. URL http: / /xx doi orgg 0. 1145 341334099999 99944. 34618166
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint wwxXi:20011.883.11 2020.
Rupinder Kaur, Arghavan Asad, and Farah Mohammadi. A comprehensive review of processing- in-memory architectures for deep neural networks. Computers, 13(7):174, 16 July 2024. URL http://dd //tp:://xxx doi. org/10. 3990 http://mmuueess1111111
Mehran Kazemi, Bahare Fatemi, Hritik Bansal, John Palowitch, Chrysovalantis Anastasiou, San- ket Vaibhav Mehta, Lalit K Jain, Virginia Aglietti, Disha Jindal, Peter Chen, Nishanth Dikkala, Gladys Tyen, Xin Liu, Uri Shalit, Silvia Chiappa, Kate Olszewska, Yi Tay, Vinh Q Tran, Quoc V Le, and Orhan Firat. BIG-bench extra hard. arXiv [cs.CL) CLJ. 26 February 2025. URL http::/dss doi. arg/10... 48550/ arxiv. 2502. 19187.
Wang Kevin, Javali Ishaan, Bortkiewicz Michal, Trzciński Tomasz, and Eysenbach Benjamin. 1000 layer networks for self-supervised RL: Scaling depth can enable new goal-reaching capabilities. arXiv [cs. 19 March 2025. URL http::/ http//raxivv... org/ awt/ 14858.
Lefteris M. Kirousis and Paul Spirakis. Probabilistic log-space reductions and problems probabilisti- cally hard for P. In SWAT 88: 1st Scandinavian Workshop Algorithm Theory, Halmstad, Sweden, July 5-8, 1988 Proceedings. Springer Berlin Heidelberg, 1988.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems, 24 May 2022.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
Richard E I Ladner. The circuit value problem is log space complete for p. ACM Sigact News, 7(1): 18-20, 1975.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(75533 444, 28 May 2015. URL http: wwwpdd/.ooooooooooooooooo/oo/ /0..g//1..0000 1el-1108/natrre1// /nn/auuuueee39.
Gen Li and Yuling Yan. O(d/T) convergence theory for diffusion probabilistic models under minimal assumptions. arXiv preprint arXiv:2409. 18959, 2024.
Xiang Li, John Thickstun, Ishaan Gulrajani, Percy S Liang, and Tatsunori B Hashimoto. Diffusion- LM improves controllable text generation. Advances in neural information processing systems, 35: 4328 4343, 2022.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402. 2024.
Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, Benjamin Newman, Binhang Yuan, Bobby Yan, Ce Zhang, Christian Alexander Cosgrove, Christopher D Manning, Christopher Re. Diana Acosta-Navas, Drew Arad Hudson, Eric Zelikman, Esin Durmus, Faisal Ladhak, Frieda Rong, Hongyu Ren, Huaxiu Yao, Jue Wang, Keshav Santhanam, Laurel Orr, Lucia Zheng, Mert Yuksekgonul, Mirac Suzgun, Nathan Kim. Neel Guha, Niladri S Chatterji. Omar Khattab, Peter Henderson, Qian Huang, Ryan Andrew Chi, Sang Michael Xie. Shibani Santurkar, Surya Ganguli, Tatsunori Hashimoto, Thomas Icard, Tianyi Zhang, Vishrav Chaudhary, William Wang, Xuechen Li, Yifan Mai, Yuhui Zhang, and Yuta Koreeda. Holistic evaluation of language models. Transactions on Machine Learning Research, 2023. URL https: / wwwp//veew.e.eee////.//. net/ forum?
Shiyu Liang and R Srikant. Why deep neural networks for function approximation? arXiv [cs.LG), 13 October 2016. URL aawiiv..vvvv. org/ wtw./baa/////eeeeeereoooeeeeeeee 61 0. 041 61.
13

---

Published as a conference paper at ICLR 2026
Shanchuan Lin, Anran Wang, and Xiao Yang. SDXL-lightning Progressive adversarial diffusion dis- tillation, arXiv (cs.CV], 21 February 2024. URL http:://axiiii http:://.www..o.......ooooo abs www.ss//.00 //0/2442..11 13929.
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. arXiv preprint urXiv:2210. 1000:9999. 2022.
Xingchao Liu, Xiwen Zhang, Jianzhu Ma, Jian Peng, and Qiang Liu, InstaFlow: One step is enough for high-quality diffusion- based eex-tt--mmage generation. In The Twelfth International Conference on Learning Representations, 2024. URL http: /twpv/araivvvvaaa//ia/ org/ abs/ 209 06380.
Yuxi Liu. Perfect diffusion -Cd diffusion is turing-complete. arXiv preprint wrXiv:2507.124000 2025.
Aaron Lou, Chenlin Meng. and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In Proceedings of the 41 International Conference on Machine Learning (ICML), 2024.
Nanye Ma, Shangyuan Tong, Haolin Jia, Hexiang Hu, Yu-Chuan Su, Mingda Zhang, Xuan Yang, Yandong Li. Tommi Jaakkola, Xuhui Jia, and Saining Xie. Inference-time scaling for diffusion models beyond scaling denoising steps. arXiv [cs.CV], 16 January 2025. URL http: //ar/iaa..iv org/ abs/ 2501. 09732.
Marina Mancoridis, Bec Weeks, Keyon Vafa, and Sendhil Mullainathan. Potemkin understanding in large language models. arXiv [cs.CL.]. 26 June 2025. URL http::t:://rxii.orrr 21521.
Gary Marcus. Deep learning: A critical appraisal. arXiv [cs.Al], 2 January 2018. URL http: //t.xiv.orr//ee/ee..l//.o. abs/1801..1111111111 00631.
William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint urXiv:2310.09923, 2023a.
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log- ree-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023b.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In International Conference on Learning Representations (ICLR), 2024.
William Merrill and Ashish Sabharwal. A little depth goes a long way: The expressive power of log-depth transformers. arXiv preprint arXiv:2503.03990 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.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. arXiv preprint arXiv:2404. 008899, 2024.
Cristopher Moore.
Unpredictability and undecidability in dynamical systems. Physical Review
Letters, 64(20):2354, 1990.
Cristopher Moore. Majority-vote cellular automata, ising dynamics, and p-completeness. Journal of Statistical Physics, 88:795-805, 1997.
Siqiao Mu and Diego Klabjan. On the second-order convergence of biased policy gradient algorithms. In Proceedings of the s/st International Conference on Machine Learning, 2024.
Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling, arXiv preprint arXiv:2501.1933 2025.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffuusinn probabilistic models.
In International conference machine learning, pp. 8162-8171, PMLR, 2021.
14

---

Published as a conference paper at ICLR 2026
Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji- Rong Wen, and Chongxuan Li. Large language diffusion models. arXiv preprint arXiv:2502.09992, 2025.
Yaniv Nikankin, Anja Reusch, Aaron Mueller, and Yonatan Belinkov. Arithmetic without algorithms: Language models solve math with a bag of heuristics. In International Conference on Learning Representations (ICLR), 2025.
Igor Carboni Oliveira and Rahul Santhanam. Majority incompressible by ACO[p] circuits. In 30th Conference on Computational Complexity (CCC 2015), pp. 124-157. Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik, Germany, 2015.
OpenAl. Learning to reason with LLMs. learning-to- wewp--tttrrrso-ittth----------ee 1lsl-11m////mm sep 2024. Accessed: 2025-4-16.
httts:://ppete com/ index/
Long Ouyang. Jeff Wu, Xu Jiang, Diogo Almeida, Carroll I. Wainwright, Pamela Mishkín, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, 4 March 2022.
Ian Parberry and Georg Schnitger. Parallel computation with threshold functions. J. Comput. Syst. (31)3)33) --02, June 1988. URL htt.::tp//// /xx. doi www./rrg...... 1000...11111011111111111111 6/ 0022-0000 (88) 90030-X.
Seohong Park, Kevin Frans, Deepinder Mann, Benjamin Eysenbach, Aviral Kumar, and Sergey Levine. Horizon reduction makes RL scalable. arXiv [cs.L.G), June 2025. URL http:
wwwpiiiorrg/bba.. abs///b///// / 2506. 04168.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, pp. 1310-1318, 13 February 2013. URL http::tpp//. /www. jm jww...or........................ orrg/ wttpor//pooeedddiooo ngs httpp/apppsss/////pp v28 https//////////aa/////ss paspppasccaaac 3. html.
Simon J D Prince. Understanding Deep Learning. MIT Press, 5 December 2023. URL https: gowgle..gllloooooooo
Rahul Ravishankar, Zeeshan Patel, Jathushan Rajasegaran, and Jitendra Malik. Scaling properties of diffusion models for perceptual tasks. arXiv preprint arXiv:241 1,00034, 2024.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do ImageNet classifiers generalize ImageNet? In Proceedings of the 36th International Conference Machine Learning, 13 February 2019.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. GPQA: A graduate-level google-proof Q&A benchmark. In Proceedings of the Conference on Language Modeling (COLM), 2024.
Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM (JACM), 23(3):555-56) 565, 1976.
Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. In Advances in Neural Information Processing Systems (NeurIPS) 2024, 11 June 2024.
Tim Salimans and Jonathan Ho. Progressive distillation for fast sampling of diffusion models. In International Conference on Learning Representations, February 2022. URL org/abs abs///b///// 220222222222 00512.
Palash Sarkar. A brief history of cellular automata. Acm computing surveys (csur), 32(1)8001107 2000.
Saurabh Saxena, Charles Herrmann, Junhwa Hur, Abhishek Kar, Mohammad Norouzi, Deqing Sun, and David J Fleet. The surprising effectiveness of diffusion models for optical flow and monocular depth estimation. Advances in Neural Information Processing Systems, 36:39443-39469, 2023.
15

---

Published as a conference paper at ICLR 2026
Julian Schrittwisser, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with learned model. Nature, 2020.
URL http: /twx/iivvvv/. org/ abs / 911 08265.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv [cs.LG), pp. 1-12, 20 July 2017. URL http: /ttpp///axxiiooo.o/ abs/1707. 06347.
Maria Serna. Approximating linear programming is log-space complete for P. Information Processing Letters, (7):233 230-223,,2662 1991.
Rulin Shao, Shuyue Stella Li, Rui Xin, Scott Geng, Yiping Wang, Sewoong Oh, Simon Shaolei Du, Nathan Lambert, Sewon Min, Ranjay Krishna, et al. Spurious rewards: Rethinking training signals in rlvr. arXiv preprint arXiv:2506. 10947, 2025.
Alexander Sherstov. Separating ACO from depth-2 majority circuits. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 294-301, 2007.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):4844455 489444494444 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676)3354-3333 359, 2017.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling I1m test-time compute optimally can be more effective than scaling model parameters. arXiv preprint 4rXiv:2408.03314, 2024.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song, Jascha Sohl-Dickstein Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, 2021. URL http:: http::://axxww..../.o... /2011. 13456.
Yang Song. Prafulla Dhariwal, Mark Chen, and llya Sutskever. Consistency models. In Proceedings of the 40th International Conference on Machine Learning (ICML), March 2023.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. Transformers as recognizers of formal languages: A survey expressivity. arXiv preprint arXiv:2311.00208. 2023.
Yu Sun, Xinhao Li, Karan Dalal, Jiarui Xu, Arjun Vikram, Genghan Zhang, Yann Dubois, Xinlei Chen, Xiaolong Wang, Sanmi Koyejo, Tatsunori Hashimoto, and Carlos Guestrin. Learning to (learn at test time): RNNs with expressive hidden states. arXiv [cs.LG), 5 July 2024. URL http:// //tp///aavvvv//aa//////eeeeawwea org/ abs/ 2407 04620.
Richard S Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press, edition, 2018.
Richard S Sutton, David Mcallester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances Neural Information Processing Systems 12, pp. 1057-1063, 1999. URL http: /// /xxxxxx/ doi. wttp/1.1...1..3311....111..1.... 97144.
Matus Telgarsky. Benefits of depth in neural networks. In Conference learning theory, pp. 1517-1539. PMLR, 2016.
Haoxing Tian, Alexander Olshevsky, and Yannis Paschalidis. Convergence of actor- critic with multi-layer neural networks. Neural Inf Process Syst, 36:9279-9321. 2023. URL haaa///e22aaaddlss55222222222222
html.
16

---

Published as a conference paper at ICLR 2026
Antonio Torralba and Alexei A Efros. Unbiased look at dataset bias. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, June 2011.
Leslie G Valiant. Exponential lower bounds for restricted monotone circuits. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp. 110-117, 1983.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Pablo
Villalobos and David Atkinson. ing and inference, 2023.
Trading off compute in train- URL https://epochs artrochh.i/blogg..
trading- coff-comput-iing tiaiiniininngg--ii and--and--ai und-inference, Accessed: 2025-04-05.
Uzi Vishkin and Avi Wigderson. Trade-off' between depth and width in parallel computation. SIAM Journal on Computing, 14(2):303-314, 1985.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019.
Team Wan, Ang Wang, Baole Ai. Bin Wen, Chaojie Mao, Chen- Wei Xie, Di Chen, Feiwu Yu, Haiming Zhao, Jianxiao Yang. et Wan: Open and advanced large-scale video generative models. arXiv preprint arXiv:2503.2033 2025.
Guan Wang, Jin Li, Yuhao Sun, Xing Chen, Changling Liu, Yue Wu, Meng Lu, Sen Song, and Yasin Abbasi Yadkori. Hierarchical reasoning model. arXiv [cs.AI], 22 July 2025a. URL
attp://arxivv www.orgg//b///eee
21734.
James Wang. Cerebras cs-3 vs groq Ipu. https: /ww. cerebras a //bl//llo og/ cerebras-cs-3-ae ------cc------ror------- 1pu, September 2025. Cerebras blog post. Accessed: 2025- 11-30.
Yiping Wang, Qing Yang. Zhiyuan Zeng. Liliang Ren, Liyuan Liu, Baolin Peng, Hao Cheng, Xuchai He. Kuan Wang, Jianfeng Gao, Weizhu Chen, Shuohang Wang, Simon Shaolei Du, and Yelong Shen. Reinforcement learning for reasoning in large language models with one training example. arXiv [cs.LG], 29 April 2025b. URL http: arxiv. www./iivoorroooooooooooooo abs 250.2.25..........
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn., 8(3-4):229-255 256, 1992. URL https: //l:: spri nger com/ Srriccee/1..100//EBP
Ryan Williams. Nonuniform ace circuit lower bounds. Journal of the ACM (JACM), 61(1):1-32,
2014.
Stephen Wolfram. A New Kind of Science. Wolfram Media, Inc., 1st edition, May 2002. ISBN 1579550088. 1st Edition.
Damien Woods and Turlough Neary. The complexity of small universal turing machines: A survey. Theoretical Computer Science, 410(4-5):443 450, 2009.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for LLM problem-solving. In International Conference on Learning Representations, 2025. URL https: /wwp//oppeee.e.eeeeeeeeee net www./orumt 1d=vNckp7JEHn.
Sherry Yang, Jacob C Walker, Jack Parker-Holder, Yilun Du, Jake Bruce, Andre Barreto, Pieter Abbeel, and Dale Schuurmans. Position: Video as the new language for real-world decision making. In International Conference on Machine Learning, pp. 56465-56484, PMLR, 8 July 2024.
vtteess//v///// URL https::///// http://pocceeeeeiee/ee/e mlr prwppreessseeee v/t./22253//// 242g242nnn22n...2n
Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of language models: Part 2.1, grade-school math and the hidden reasoning process. In The Thirteenth International Conference Learning Representations, 2024.
17

---

Published as a conference paper at ICLR 2026
Tianwei Yin, Michaël Gharbi, Taesung Park. Richard Zhang. Eli Shechtman, Fredo Durand, and William T Freeman. Improved distribution matching distillation for fast image synthesis. In Advances in Neural Information Processing Systems (NeurIPS), 23 May 2024.
Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Yang Yue, Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model? arXiv [cs.Al], 18 April 2025. URL http:: /tap::///aavv...///aa/aapeaa org/ abs /2004 13837.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of the 5th International Conference on Learning Representations (ICLR 2017), pp. 1-14, 2017.
Yiming Zhang, Yingfan Ma, Yanmei Gu, Zhengkai Yang, Yihong Zhuang, Feng Wang, Zenan Huang. Yuanyuan Wang, Chao Huang, Bowen Song, Cheng Lin, and Junbo Zhao. ABench-physics: Benchmarking physical reasoning in LLMs via high-difficulty and dynamic physics problems. arXiv [cs.LG], 7 July 2025. URL http: /arxivvvvv htgg/bbs/2501 04766.
18

---

Published as a conference paper at ICLR 2026
A LIMITATIONS
Our conclusions rely on the widely-held but unproven assumption that TC & P (Assumption 2.3). If this assumption disproven, our formalization of the serial/parallel dichotomy would be invalid. Moreover, our theoretical arguments apply only to the general case; although the intuition may extend to practical settings, such generalization is not guaranteed. In particular, the average-case complexity (Bogdanov et al., 2006) of many problems could differ or even allow parallel solutions.
For especially hard problems (c.g., NP \ P and beyond), exponential cost-rather than serial depth-may dominate the primary bottleneck. Thus, our focus is on real-world problems of practical difficulty.
Our theorem on diffusion models applies only when the output dimension remains fixed. If it grows with problem size, the result may not hold- hold-though current empirical evidence in language modeling does not suggest strong serial scaling. The theorem also assumes well- well-trained backbone using score-matching objective, and may not apply to poorly trained models, especially early in training.
Finally, beyond theoretical and cireumstantial evidence, more empirical work is needed quantify the degree of seriality in practice- particularly the benefits of increased serial compute. promising direction is to benchmark real-world tasks under varying ratios of serial and parallel computation.
B A BRIEF HISTORY OF SCALING
The success modern machine learning has been driven by scaling-bigger models, more data, and especially more parallel compute. Hardware has shifted from CPUs to massively parallel GPUs; architectures have moved from RNNs to highly parallelizable Transformers; and al- gorithms increasingly exploit parallelism for efficiency.
Serial
Parallel
Scaling
Depth
Width
Architecture
RNN
Transformer
Algorithm
RL
Imitation leam.
Hardware
CPU
GPU
Table 2: Examples of serial and parallel approaches.
However, this focus on parallel scaling has a blind spot: assumes that parallel and serial computation are in- terchangeable. In reality, for many problems, only increasing serial compute-allowinn models to perform more sequential geps-yiildss further progress. This especially true for tasks with inherent temporal or causal dependencies. As we show in this paper, recognizing the limits of parallel scaling and the necessity serial computation is crucial for the next phase of progress in machine learning.
C POTENTIAL MISCONCEPTIONS
C.I ARCHITECTURE VS. INFERENCE METHODS
One may be confused by the statement that "Transformers are not serial," followed by "Chain of Thought is serial." This appears be contradiction. is not, though it may appear due to our omission of words. The first statement really should be "If you fix Transformer's parameters and give problems of size O(n). but only run for ( forward passes, then you cannot solve inherently serial probeem-families Transformer's 's parameters and give it problems of size ((n), and also run it for ((n) forward passes, then you can solve inherently serial
Similarly, the second statement really should be "If you fix
This is special case of general phenomenon: people confuse architecture and inference methods, meshing them all together like two lumps of clay gently melding under the desert sun. This is unfortunate but understandable because, in practice, architecture and inference couple together co-design".
strongly, and this confusion is also encouraged by things like "architecture-deploo" The fact is that the abstractions leak. How you use a model for inference depends on its architecture. model architecture depends what you expect its inference method to be.
How you design This is good thing, but it may cause people to confuse architecture and inference.
Fundamentally, consider an "architecture" to be class that can have instances. For example, gpt2 is an instance the class CausalTzr former Each class-instance should be imagined "atom of computation". An atom has mass and volume. An atom can be copied and put
19

---

Published as a conference paper at ICLR 2026
into many molecules. What atom cannot do is be divided or changed. Similarly, an instance of the "TTranformeer architecture" is an "atomic" Transformer. This atomic Transformer does have "subatomic structures", such its individual layers. However, since we are not performing complicated model surgeries, such as taking off its head, reading out the tensor from its middle layers, etc., we can ignore all of its subatomic structures and assume it simply atomic, perfectly indivisible, unchangeable, eternal. If give you an atomic Transformer, and you want to do something with it, you must perform exactly one single forward pass, because you cannot stop half-way (since you don't have access to its subatomic structures). This has a fixed seriality. It may be 48 layers or 96 layers, and you can pick bigger and bigger atoms from the same class with no upper bound. But for a given particular instance from the class, the seriality is O(1), and cannot possibly grow like (n)).
Still, even though the atomic Transformer is unchanging, can be used in many molecules, and the molecules can change. It can be used in a Chain of Thought molecule, and this molecule would grow like a polymer, taking on a length of (n) in reaction to a length (n) input.
In short, single architecture may be used on its own in a fixed number of forward passes, or number of forward passes growing linearly with the problem size, or in a tree search, a beam search, etc. Inference methods are separate from model architecture. In this paper, we discuss both architectures and inference methods. We have found that Transformers, SSMs, and diffusion models are all not serial when the inference method is just a single forward pass, but can become serial when the inference method allows for more serial compute, such as Chain of Thought inference.
C.2 SSM IS NOT RNN
We class SSMs as not inherently serial, while RNNs as inherently serial. This is not mistake, and in fact, a very valuable illustration of how an architecture can have an illusion of seriality.
First, in what sense is RNN serial, while Transformer is not serial? Recall the title of the original paper on Transformers: "Attention is all you need" (Vaswani et al., 2017). What did they mean by "all you need"? What was removed? Back in 2017, the standard sequence transduction model was pair of RNNs connected in the middle by the attention mechanism. The encoder RNN processes the input sequence one token at time, then the decoder RNN produces the output sequence, again one token at a time. The key problem is that, while both an RNN and a Transformer must decode tokens one-by-one, an RNN must encode tokens also one-by-one, whereas Transformer can encode tokens all-in-one-go go. The animating spirit of the Transformer architecture was to remove everything that stands in the way of all-in-one-go. but preserve everything that allows RNNs to work so well.
So they removed recurrence and preserved attention. Their title meant "attention is all you need (and recurrence is not)". This is exactly what our paper is arguing against: attention is not all you need, and inherently serial processing is necessary. It can be done in many ways: recurrence in architecture, CoT in inference strategy, or some other method, but it cannot be avoided.
So now we come to SSM. SSM is not RNN because it is not recurrent in an inherently serial way. It was designed with the same spirit as the Transformer and suffers the same issue.
Concretely, consider the problem of ingesting an input sequence: 21, , TT,, and the task is to output the next token 11 For Transformer with 96 layers to accomplish the task, it does so by 96 sequential steps. Each step is very wide but not deep. In contrast, RNN with 96 layers must process Tj first, then I2. and so on. It requires 96n sequential steps that cannot be done in parallel. Suppose attempts do them "in parallel", then there is immediate problem: To run the RNN on I4, one needs the internal states of the RNN just after it has processed Zy, and to do that, it needs to have processed 22, etc. Abstractly, the operation of an RNN looks like:
fo(Ins folxn-1, fo so)))),
where 8g is the initial internal state.
In short, because the internal states of an RNN change nonlinearly and unpredictably, one cannot skip the steps. This allows RNN to solve inherently serial problems without chain of thought, but at the price of taking wall-clock time O(n) to even output its first token.
The animating idea of SSM is precisely to remove the inherent seriality of RNN. The idea is that if the internal states change linearly and predictably, then one can skip the steps. Concretely, the
20

---

Published as a conference paper at ICLR 2026
operation of SSM is of the form:
o fo(M + 2 + xx
since its internal states change linearly in a data-independent way. This means that to run an SSM on input 44,, one does not need to know the internal state of the SSM after processing Z3. This allows it be just as parallel as Transformer, and thus just as lacking in seriality.
C.3 TRAINING VS. INFERENCE
Throughout most of the paper, the main contrast is the parallel vs. serial computation contrast. We do not mean this to be a contrast between the parallel phase of training vs. the autoregressive phase of inference, which is how modern GPT-like transformers are produced and used.
Concretely, consider initializing a language model with 96 layers. The training algorithm samples chunk of text (32,768 tokens long) from the training corpus. The model then performs single forward inference simultaneously on all tokens, such that only takes 96 steps of time one step per layer. Now, during inference, the model must then generate one token at time, the same 32,768 tokens would take 3,145,728 steps of time, which is a vast expansion.
Yet, this is the main focus of the paper. The paper mostly talks about the theoretical and empirical results concerning learned and frozen models. The paper does talk about training, but only occasionally and informally, by sketching out intuitive analogies with inference, without rigorous theoretical justification.
This is not due an intention mislead. Indeed, we recognize that there is parallel training vs. autoregressive inference contrast, and we have attempted to get some theoretical handle on this contrast. We failed. Because learning theory is extremely difficult, we could neither find theorems proven by people that came before us, nor prove theorems ourselves. Therefore, we stayed within inference. Fortunately, the parallel vs. serial contrast is already sharp even within inference, with both clear theoretical and empirical results, allowing to write the paper.
believe strongly that the future, the parallel vs. serial contrast will also be shown for training, and leave this as work for the near-posterity.
D TC AND TC CLASSES
Definition D.1. Let E N. decision problem L S 13, in the complexity class TC' if there exists family {Cn of Boolean circuits such that:
Each circuit C, decides whether x E for all x E {0, 1)".
Each circuit C, has size polynomial in n, i.e., |Cn. = Onn*) for some constant
Each circuit has depth O(log" n..
The circuit gates of unbounded fan-in AND, OR, NOT, and MAJORITY gates. A majority gate outputs 1 if more than half of its inputs are 1.
The family {C.,) is L-uniform, where L stands for "logspace". This means that there exists deterministic Turing machine that, on input (11...1,7) i), outputs the ith bit of the description
n repeats
of Cn using a working tape of length only Ologn))
In addition, a decision problem L S {0, 1)* the complexity class TC if the union of all classes TC' over E N, that is,
TC = TT!
iEN
In the literature, TC is also called NC. "Nick's Class."
Define the L-uniform many-one reduction relation <!. as follows: Given two languages L, L', that is, two sets of binary strings, we say I. <h T/' if and only if there exists function such that if
21

---

Published as a conference paper at ICLR 2026
and only if f() L', and the function is computable by deterministic Turing machine with logspace working tape.
A decision problem is P-complete if and only if there exists Turing machine that decides it in polynomial time, and any problem decidable in polynomial time can be L-uniformly many-one reduced to it.
E SERIAL CAPABILITIES OF MODERN MACHINE LEARNING METHODS
Empirically, we see a tradeoff in modern machine learning architectures. Some have highly paralleliz- able computation graphs, such MLPs, Transformers, and SSMs, but do not solve inherently serial problems. Others can solve inherently serial problems, but cannot be parallelized, such as RNNs, repeating layers, and COT.
In terms of computational complexity, MI.s have been formalized as a family of Boolean circuits with threshold gates called TC (Parberry & Schnitger, 1988). Consider a family of MLPs with constant (1) depth, (oly(n) neurons per layer, and (1) numerical precision. A problem in TC if and only if it is decidable by one forward pass through an MLP under this setup.
It is widely suspected that TC! is strictly larger than TC Therefore, any -had problem requires computations deepening at rate of at least (log r2). We may consider the problem as being serial in weaker, logarithmic sense. simple example of TC is the word problem of the symmetric group on 5 elements Sy: Given 91. .2.............................. In S5, find II, 9: (Liu et al., 2022). Intuitively, this is because S₁ is not a solvable group, and therefore there is no better way to multiply its elements than via binary tree, which has O (log n) layers. Attempting to perform this with just ((1) layers would effectively require one to memorize the entire S - S,, multiplication table, which scales exponentially as e" log(1 20), an exponential depth-wiid width trade-off.
To solve the word problem of S5 by a Transformer in one forward pass, we present it with input tokens 91, .........rr In, Y. where y is a special token. The Transformer's output at y is read out as the answer. Similarly, we may solve such problem by presenting the same input tokens Model (SSM) or a Recurrent Neural Network (RNN). Since a Transformer with O(1) layers and (oly(n) dimensions can only solve problems in TC (Merrill & Sabharwal, 2023b) in one forward pass, it cannot solve the word problem of S3 that lies outside TC
State Space
On the contrary, for an RNN, we can write the multiplication table of Sg + S3 directly into its weights, so it can solve the problem by unrolling for (n)) recurrence steps with O(1) layers and (1) dimensions. Intuitively, the hidden states of an RNN keep track of the progress of multiplication as it performs the forward passes. However, RNN's s recurrence state dependency renders it non- parallelizable. Several families of SSMs were developed as compromise that still have recurrence on hidden states, like an RNN, while making forward passes parallelizable, like Transformer. The prototypical SSM architecture is Mamba (Gu& & Dao, 2023), though there are many others.
Unfortunately, it has been proven that there is not yet a "free serial-compute lunch," in the sense that the main families of SSMs proposed so far still cannot solve the word problem of S3 under the constraints of (11) layers, poly(n) dimensions per layer, and one forward pass. Despite its apparent recurrence, the hidden state offered by an SSM is weaker in a computational sense than that offered by an RNN (Strobl et al., 2023; Merrill & Sabharwal, 2023a; Merrill et al., 2024). This theoretical fact rhymes with the empirical fact that in practice, MI.Ps, Transformers, and SSMs are all more parallelizable than RNNs.
Only genuinely serial method has been shown to go beyond the TC class. In addition to RNNs, this includes repeating layers and COT. Repeating layers for Olog n) times enables a standard Transformer to solve tasks in the TC class (Merrill & Sabharwal, 2025). With poly(n) CoT, requiring multiple forward passes before producing a final answer, Transformer can be lifted from TC" to P (Feng al., 2023; Li et al., 2024). As discussed in Section 3.5, the power of CoT has been well-attested in practice by the improved performance of reasoning models in complex math and science tasks.
22

---

Published as a conference paper at ICLR 2026
Such uniformity restriction is necessary for technical reasons. Specifically, is necessary because one may hide a large amount of computation into small circuit that requires a long time to find. The final circuit produced might run in time (log n), but if the time required to find such circuit requires time 20(m), then this would not be parallel-in in the sense used throughout this paper.
F DIFFUSION IS IN TC
In this section, we consider the non-uniform TC class, in contrast to the usual uniform classes. Note that uniform TC' C non-uniform TC'. We prove that many diffusion models are restricted within that class, We need to assume non-uniformity because, at a certain point in the proof of the main theorem, we merely prove that something exists, without showing that it also efficiently computable. We will highlight this in the proof.
F.1 PROBLEM SETTINGS
An abstract language is simply set of sentences made of letters. Formally:
An alphabet a finite nonempty set. Each element the alphabet may called a letter token.
A sentence in alphabet E is finite sequence of elements of Σ.
A language an alphabet Σ a set of sentences the alphahet Σ.
An abstract language is more than a natural language. A sentence in a natural language is a sequence of tokens. An image, divided into patches and tokenized, becomes sentence in an abstract language. A video, divided into frames and patches and tokenized, becomes sentence in an abstract language.
We define the deterministic prefix language modeling problem: given a sequence of tokens Ii...., In. compute the next token Zn+11 This is a deterministic formalization of next-token prediction, the dominant paradigm in language modeling since the GPT-2 of 2019. This can also be cast into a decision problem: given input of size n. I1, ,,, In, decide whether In+1 is the correct continuation.
Most language model benchmarks can be cast into this form, at least when without chain of thought. For example, consider a problem from the GSMSK benchmark "Tina buys three 12-packs of soda for party How many sodas are left over when the party is over?" has only one correct continuation, "I "11".
The definition has some issues. Some problems may have more than one correct answer. Some answers may occupy more than one token. We may allow chain thought. Language modeling is restricted to prefix modeling. A touted benefit of diffusion language modeling is that, unlike GPT models, it can generate any number of tokens where sequence conditional on other parts of the sequence.
Define nondeterministic masked sequence modeling problem as follows. Consider a sequence of tokens Ø1, ...... Fr,, of which are masked. The task is to compute sequence of tokens that can acceptably fill in the masks.
For example, game of 24 may be cast into nondeterministic masked modeling problem² follows: "1, 3, 9, 9, [M][][[[[[]]]]]]]]] = 24". This has more than one acceptable answer, such as "9 99-
As another example, solving a problem with chain of thought is unmasking an entire block of masked tokens, where any unmasking acceptable as long as the tokens between "Final answer: [END]" are correct.
Given a problem instance, we can train model such that, conditional on the problem instance, would sample one point from possibly many points that form a solution manifold, from which the answer can be recovered by discretizing.
Brackets would different lengths for the masked sequence. We avoid them by reverse Polish notation.
23

---

Published as a conference paper at ICLR 2026
We need to make the discretization step simple possible, to avoid secretly performing part of the wrolleg-solving in the discretization step. Consequently, we will only consider cases where the masking pattem is fixed, and the discretization is performed using fixed amount of compute.
As a concrete illustration, suppose that we use a diffusion video model to evaluate an arithmetic expression. The input is sequence of frames presenting the arithmetic expression to be evaluated, and the masked tokens are the frames illustrating an animated process that draws out the answer. The solution might be written in many variable ways, creating the solution manifold. The discretization step can be done by taking the pixel-wise nearest neighbor of the last frame's s digits.
Our overall framework for sequence modeling is:
true answer discretization solution manifold stochastic sampling
We will show that if the dimension of the solution manifold does not grow quickly, and the stochastic sampling is sufficiently parallelizable and accurate, then we can derandomize it to obtain paralleliz- able deterministic algorithm for obtaining the true answer, thus showing that the original problem is parallelizable, not serial.
F.2 DIFFUSION MODELING
There are several equivalent formulations of diffusion modeling. use the score-matching for- mulation. In this formulation, given a probability density Po to be modeled, and noise schedule T1, 2.... OT, we define the forward diffusion process by adding an increasing amount of Gaussian noise to Po:
2o po. ze/20 ~N (Vi-of20.0,))
Let Pt be the probability density of o4, Any (true) score function time is ft, x) V =o (z)). To score-match is to find an (approximate) score function fo. such that xt, R (²) In the sense that the average score modeling error low:
Encp -
Escore 1=
Given a score approximator So and a noise schedule ar, the Score-Matching with Langevin Dynamics (SMLD) (Song & Ermon, 2019) sampler performs backward diffusion accordingly, sampling sequence of êт, d1........ ft. Let PSMLD. be the probability density of &, The theoretical basis for diffusion modeling is that, the limit of continuous noise schedule infinitely many steps, each adding an infinitesimal amount of noise and the limit of perfect score function, PSMLD.0 would converge to exactly equal to Pu-
Generally, the difference between PSMLD.U oo and Po can be understood as consisting of two parts: discretization error, caused by taking finitely many small steps, instead of infinitely many infinitesimal steps; score-matching error part, caused by fo * f
Intuitively, the discretization error converges to zero as - Do, while the mateenn error grows with fecore and T. In the next section, we quote theorem from the literature that makes this intuition precise.
F.3 THE FUNDAMENTAL THEOREM (L1 YAN, 2024, THM. 2)
Intuitively, point is easier to model than line, which is easier than plane, and This be made precise by the intrinsic dimension of the support probability distribution to be modeled.
The support of probability distribution Po is supp(pa). It is the smallest set that satisfies Pr (x E supp(po))
Definition.
Let T denote the number of SMLD denoising steps. It is positive integer.
24

---

Published as a conference paper at ICLR 2026
Definition. Given a base space Ω2 and two probability densities p. 9 it, their total variation is (v 9) = J. (p(x) ((z))dz
Definition. Let be an arbitrary subset IR. Let > 0. The discrete intrinsic dimension is
de dx() = log (X)
log
where N, (X) is the minimal number of radius-e balls necessary to entirely cover X. As 0, if the discrete intrinsic dimension converges, then what converges to the intrinsic dimension.
What does it mean?
Consider 2-dimensional square X in R. As we repeatedly halve the value of c, each halving would require times as many radius-e balls to cover the same square. Thus, d(X) log
This
log 172
true no matter if = or n = 300, and no matter what side length the square has. Thus, the intrinsic dimension recaptures our intuition. However, it is well-defined for more than smooth manifolds. It is well-defined for more general sets, such as fractals. The expression for intrinsic dimension is deeply related to metric entropy, and has applications in statistics and information theory. (Wainwright, 2019, Chap. 5)
However, the intrinsic dimension is not accessible in practice. For example, consider line segment X 100 has (X) + 1 as decreases. However, when c gets small enough, suddenly d, (X) starts converging to 2 instead. What happened? It turns the line segment is really line segment. At high enough zooming level, it is actually a cylindrical tube. However, when got even smaller, suddenly de (X) starts converging to again. turns out the cylindrical tube is actually tightly-wound helix curve.
What accessible in practice the discrete intrinsic dimension de (X). Intuitively, it intrinsic dimension X if we are not allowed to look more closely than Another way to intuit it is by taking X and constructing The intrinsic dimension of the "dehydrated skeleton" of X is approximately (X(X..
dimensionna e-skeleton X, of it. Any point in is within distance of X..
Theorem F.1. There exists constants CM; Ce, > O, such that the following is true. Fix any positive integer T > O. Fix = T Let po be the target distribution. If the target distribution has first order moment that is bounded by a polynomial in T:
Eror-po [1]= < TCM.
and we have a score network fø(x, E) such that it achieves average score modeling error 2,om then there exists SMLD sampler schedule that takes T steps, such that the result of SMLD sampling has distribution PSMLD,0. and
TV (po, PSMLD.) Sc (d((supp(po)) (c (log T)3 + Escore v log
T
The two terms correspond to eтror caused by taking discrete steps, and error caused by drifting away from score matching eиror.
F,4 MAIN THEOREM
We formalize a model of non-uniform TC diffusion modeling.
Given a task, we define what it means to solve it by nondeterministic masked sequence modeling. Each task instance is specified by sequence of n tokens, written Ti,..., Tn. Of these, A, tokens are fixed inputs to the model to specify the problem, and n kn tokens are masked, which the model would denoise. The denoised tokens are discretized to final answer.
To avoid surreptitiously hinting the diffusion model the answer, the masked tokens are always in the same place, which, WLOG, assume comes at the end. Similarly, require that for each n, kn fixed. Finally, we require the discretization step to require constant compute, to avoid secretly off offloading problem-solving computation from the diffusion model to the discretization algorithm.
25

---

Published as a conference paper at ICLR 2026
Given task, TC" family of score-networks fa,n for such task is sequence of networks f0,1, fo.,...., such that:
Each Sa, takes as input n + elements F and produces an output fo the +2. +2....,,... ,n ...,............................ TR.)).
The family fe. has (1) depth, poly(n) width, and ((1) precision.
The holds for any family of score-networks for which a single forward pass is in TC This includes, for example, Transformers and state-space models (Merrill & Sabharwal, 2023b; Merrill et al., 2024).
Comment.
For notational convenience, will thenceforth assume that in our task, there is true solution per problem. If there are multiple true solutions per problem. then our proof shows that the task of "finding at least one true solution for the original task" is TC
Since diffusion model may solve problem only with high probability, instead of solving it deterministically, we make the following definition:
A task is solved with constant probability bound if there exists some d > 0, such that for each input token sequence Ti..... Zns Iet Zeorret be the correct discrete solution, then
P( ,I....,, In) > p(a' [i....., mn) + 6, Va' 7
Teorrect
(2)
As noted before, there are places where diffusion model can incur error in its solution. The first place is due to using discrete time-steps during the backward diffusion process. The second place due to score score-matchin matching error compared to the true forward diffusion process from the solution manifold.
We are ready to state the theorem. We apologize for the amount of complicated epsilon-delta formality in the statement, but it is what it takes to make it rigorous.
Theorem F.2. Given a task, and a TC family of score- netwons f0.0- fe. solving the task, by SMLD with Jo,a(TK, 2k, 42.............................. ... In II,..., J.,,).
Uk,
the n-th solution manifold of the task be Xx. Assume:
1. There exists a constant integer T > O, a constant real number Cscore > O, a small constant real number >> and a sequence of probability distributions po,a on Xn such that
2. Letting C, Ce, Cas be the constants used the statement of Theorem F.I, e T- and Escore be the average score modeling error of using fe. to score-match the forward diffusion process on Po,n-
3. For all n 1,2,3..... we have
Exo-Pa.n [||x0||a| S T
Cycore,n S Cycore:
(e() T
(log T)3 Escom v log
< 2
6.
Then the task is in the non-uniform TC class.
More generally, the family of score-networks is a TC family, and assume:
1. There exists non-negative integer k. a sequence Ti, Te.... such that T, O(logn) a sequence 8, such that 1/6, (n)y(n), such that
2. Letting c, Ce. CM be the constants used in the statement of Theorem F.l, Cn. T and Eoor,, be the average score modeling error of using fo.n to score-match the forward diffusion process on po.as
26

---

Published as a conference paper at ICLR 2026
3. For all 1,2,3..... have
po [1 [=]= S T.
den (Xn)
1
(log Tn)² (n)² + Excoren vl log In
2 on.
Tn
then the task is the non-uniform TC* class.
Proof. The proof of the case for TC is essentially the same the case for TC with more cumber- some notations. Thus, we only prove the case for TC explicitly.
Using the big list of assumptions, we can apply Theorem F.1 directly, and conclude that, if we use SMLD with fa,n as the score network, for 7 steps, we would sample from a distribution PSMLD,0.r that satisfies
(po PSMLD,0.a) 1/2
In particular, this means that after discretization, we obtain the correct solution with probability at least 1/2 + 5. This then implies that the task is solved with constant probability bound. Now derandomize this family, obtaining TC" family of Boolean circuits that solves the problem deterministically. The details the derandomization method appear in (Hajnal et al., 1993, Prp. 4.2). It goes follows:
for each length n, we replicate the network k(n) times. Each network must take one seed. For each choice of k((n) seeds $1...., Sk(n)= we have particular deterministic model:
h mf $1), f(z s2). f(, sk(n))).
randomly sampled, then let the probability that f(x 8) is wrong be upper-bounded by a constant 1/2. By Hoeffding's inequality (Hoeffding, 1963), the probability that the majority vote correct - e (p22(())(p11///)
Sample k(n) random seeds, and fix them. This provides deterministic model. Now, we try this deterministic model on every single possible input of length n. There are only #vocab" of them. we set k(n) 2 logí log(#vocah)
2(p-1/2) then by the union bound, the probability that the majority vote is correct on all inputs of length is nonzero. Thus, there exists specific choice of random seeds ($1. Sk(n)) that makes the compound model correct on all inputs of length n.
This construction is nonuniform precisely in the part where have only shown the choice of seeds exists. To actually find these seeds may take exponential time.
F.5 INTERPRETATION
At the high level, to satisfy the assumptions, one needs to have a good enough approximate score with error Cooor. Then, choose T (or T,) such that
( de (Xn) T
T)3 Scooe, log T
< 1
For constant (X,,, we have the following interpretations:
Perfect diffusion model is non-uniform TC Consider the case if we have a perfect score function Éscore = 0, we have (xx))
T (log T < 1/2 We can select = (X,() = O(1). hence,
the task belongs to the non-uniform TC class. This is the same finding as Liu (2025).
In complexity theory, this choice of seeds "advice string".
27

---

Published as a conference paper at ICLR 2026
Good diffusion model is still non-uniform TCº. Consider if the score function is not perfect. Here, the the accumulated error grows slowly with T, ie., Eecoe Vlog As increases, the term (X.)
T (log T decreases quickly, while the term Goore Vlog T increases only slowly and eventually dominates, setting a floor on the total error. the error is not too large, we can still find a constant T to obtain constant error bound.
Similar interpretations can be obtained for non-uniform TC d.,, (Xn) ())ogn)))
There are two scenarios that the theorem's 's assumptions are violated and the conclusion of the theorem does not apply.
Sccore is too large. In this case the inequality fails and our theorem no longer applies. This corresponds to a diffusion model that is not doing good job at its intended task of score matching. We expect this to occur when the diffusion model is poorly trained or minder-prrameterizer or when the network is not being used as a score-matee matching diffusion model at all. If it is not used for score matching, SMLD can in principle implement arbitrary Turing computations via highly non-score-ve motooennaiiinggggg network.
The intrinsic dimension of the solution space d,(X,, grows faster than polylog(n). In this case, the convergence rate of the diffusion model will be slow enough that the task may go beyond non-uniform TC* if de, (X,,) O(log nt)*). However, it doesn't 't immediately imply that the task is in P TC, nor the diffusion model can solve an inherently serial problem. It only means that diffusion models solve problem with polynomial number of intrinsic dimensions with polynomial steps.
G INHERENTLY SERIAL PROBLEMS IN RL
Throughout this section, by parallel algorithm, mean specifically L-uniform TC Boolean circuit family-an as usual throughout this paper.
In this section, we begin with a problem from computational complexity theory that proven be impossible to parallelize (assuming, as always, that TC & P). then convert it into a deterministic decision problem. We then prove theorem, showing that any parallel decision rule for this problem has arbitrarily bad worst-case performance. As special cases, this includes maximizing parallel value functions, maximizing parallel Q-functions, parallel policies, and parallel learning rules that produce parallel policies.
G.1 1 DEFNITIONS
Boolean circuit C is alternating when it consists solely AND and OR gates such that every AND gate connects to only OR gates and every OR gate connects to only AND gates.
Altemating circuits are monotonic in the following sense. Consider an alternating circuit that takes inputs, and let x, E {00, 1]"h be two possible inputs it. If S x' (i.e., x' is obtained by flipping some zeros of x to ones), then C(x) < C(x'). More generally, for any gate output C₁ of C, we have (ar)) S Cx(x"; intuitively, this be visualized "hot" wires carrying True-signals monotonically "upwards" through the circuit.
The depth of gate is the length of the longest directed path from any circuit input to that gate. chain of the form OR + AND OR- .... therefore has gate depths 1, 2, 3, in order.
For an alternating circuit C on input x, the depth-of-1 (DO1) of this circuit configuration
(C, == max/depth/ (g)
outputs 1 on z).
The problem of computing the DO1 of any circuit configuration is the DO1 problem. Assuming that TC # P. as usual in the paper, then the DO1 problem cannot be solved by a parallel algorithm. In fact, much more can be said. Not only would it be non-parallelizable, any approximation of it is also non-parallelizable.
Fix constants 0 <<< b. Given (C,z), the problem of computing number d(C. satisfying
d(C, [e (C, b (C)
28

---

Published as a conference paper at ICLR 2026
Because solution for (e, b] yields one for (e/b, 1], it suffices consider the special case b 1, which we call the c-approximate DO1 problem.
G.2 NON-PARALLELIIZBBIITT RESULTS
We quote the following result from Kirousis and Spirakis (Kirousis & Spirakis, 1988).
Theorem G.1. For every (0, 1), the e-approximate DOI problem is P-complete. Consequently, if TC A P, no parallel algorithu can solve the e-approximate DO1.
To import the theorem from computational complexity theory into RL theory, we need construct specific decision environment in which an agent must perform actions to maximize rewards.
The idea of the following construction is that an approximately optimal agent can be exploited as problem-solving resource for other ends. Specifically, we will construct some environments in which the first action of the agent a forced choice between two circuits. In the language psychologists, we construct two-alternative forced choice experiments. The agent's 's choice can then be interpreted as an agent's judgment as to which circuit has deeper depth-of-1.
Given circuit configuration (C, we construct, in parallel, many other circuit configura- tions (CM, (C2, 1), (Cz, 1),..... (Cap 1), such that di (C₁, 1) = 1, (C 1) = 2, di (C', 1) = 3...., (C(C)) (c)))) = |C|. Then, we perform in parallel all forced choices for these pairs: (C, x) vs 1), (C, (C2, 1), ..., (C, (Ciap,), 1). At some point, the agent's forced binary choice should switch from preferring (C', 1) to preferring (C,x) x). This can be taken as a judgment that (C(C,z) æ) se k. If the agent is approximately optimal, then di (C, x)) se is correct, in the sense that we can guarantee & E [cdi(C, x), bdy (C, x)] for some constants 0 < c < b that do not depend on either C or
This is the essential idea of the construction and the subsequent proof. The rest are tedious details designed to close loopholes.
We define the DO1 environment as follows. Given a circuit configuration x)) define a corre- sponding deterministic decision problem as follows.
= 0, the agent observes two circuit configurations: the original (C, and a length-k: alternating chain of the form OR - AND - -OR- ...., whose input is 1.
2. The agent selects one gate from of the circuits; the unchosen is then removed. This is the two-alternative forced choice.
3. Subsequently, the agent may select at most one additional gate per time-step, for H max(k: (CT} steps, designed so that the agent has enough time to choose every desired gate.
4. The episode ends at = H. every chosen gate outputs 1, then the reward at this step is I'H = the maximal depth among all the chosen gates. Otherwise, TH 0. The reward at all other steps is zero.
This means that each DO1 environment have the following states:
No gates are selected.
Some gates of C' are selected.
Some gates of the alternating chain are selected.
Theorem G.2 (optimal decision in the DO1 environment inherently serial), Assume TC +
(a) No parallel algorithm can compute an approximate optimal value function V such that 30 < e < b with Vss E (s), (s)) every state in every DO1 environment.
(b) For any parallel algorithum producing a value function V and any e E (0, 1), there exists DO1 environment where the greedy policy TV (s) arg max, V(s') achieves terminal reward In < er", where r" is optimal. Here, s' denotes the next state if. at state s, the agent performs action
29

---

(l) Published as a conference paper at ICLR 2026
(c) Statement (b) extends to any parallel algorithm that, given state in DOI environment, outputs an action.
Proof.
(a) We argue by contradiction. Assume there exists a parallel algorithm that, for some constant < < 1, outputs a value function V satisfying
V(s) E (s), [*(s] for every state in every DO1 environment.
Since any factor b > 1 can be removed by division, set b 1 without loss of generality. Special case. We need to check first the special case where di (C, x)) = 0. This done as follows. First, perform a topological sort of C, which is parallelizable (in TC², in fact (Cook, 1985)). This then allows us find all the gates that in the first layer. Next, for each gate in the first layer, we test in parallel whether that gate outputs 1. Let their outputs be y1,... Vmm If OR(y,, Mm) O, then di (C, 0, because alternating eircuits monotonic. Otherwise, (C, 2 1.
Having thus handled the special case, we assume that di dC, 2 1 for the rest of the proof.
Two-alternative forced choice experiments in parallel. Given an input (C, with n == [CI gates and 1 equal di di x),, choose m E N such that 2 < S 2 For each index E {O..... m construct, in parallel, a DO1 environment Eg whose second circuit an alternating chain of length 2 with the only input being Within each Eg evaluate (again in parallel)
(E) v(sg"). where 5g is the state after initially selecting gate g E C; (E) V(s ((siii))) where Sehin is the state after selecting the input gate of the chain.
The whole procedure requires
(n + +))mmmm + 1)= (IC) + 1) loga [c]]
parallel evaluations.
Identifying the switchover index. For & = m the chain depth 2n is at least as long as what depth-of-1 that C' can create, hence, if the value function is any good, it should satisfy
(mm) V(s chain 2 V($ for all g. As decreases the chain shortens; eventually picking C should be better than picking the chain. This intuition allows us to define the following decision procedure.
Let A be the smallest such that
V (( max ((s!.)).
Output d' : 2m as the estimate for dj.
There are two special cases to handle. If the agent rejects the chain even for & = 0, then output [C|. the agent always picks the chain, then output d' = 1.
Quality of the estimate. Suppose the switchover occurs, such that the agent picks the chain for Ex, but switches to picking the circuit for Eg-1. Consider detail what happens for Eg.
Choose 9 attaining the maximum in the definition of k and set
(k)
by construction, V(s) 2 (s')., and by the assumed guarantce V. ((s) [ed1, di), V(s') (ed', d').
30

---

Published as a conference paper at ICLR 2026
Hence d1 2 ed'.
Similarly, the argument in the case for E shows ed & 2d', so altogether
dp led', d']
A similar argument applies for the two special cases where no switchover occurs.
Therefore the procedure is an approximation algorithm for DO1 that operates in parallel, contradicting Theorem G.I.
A special case of (c).
(c) Assume for contradiction that there exists a parallel decision algorithm that is within an of optimality. That is, when the decision algorithm is applied in any DO1 environment, it always achieves reward at least cr" Then, for any particular DO1 environment, its first action must be approximate solution larger depth-of-1. Now, the same construction of (a) yields parallel algorithm solving e' e'aapproximate DO1, again contradicting Theorem G.I.
whether (C, z) the chain possesses
Comment. By prepending beneath the circuit C a length-|Ci alternating chain of gates, and making some minor adjustments to the proof, we can show that any parallel decision algorithm achieves linear regret in the worst case, meaning that r' r- = OHH)
Although our analysis uses the DO1 problem in particular, there are some other P-complete problems, such as linear programming, that are P-complete to approximate. See for instance (Sahni & Gonzalez, 1976; Serna, 1991; Díaz al., 1997; Greenlaw et al., 1995) for some examples. This leads to conjecture that inherent seriality may be a fairly common phenomenon in RL, not particular to the DO1 setup.
The barrier in Theorem G.2 can be bypassed in several ways:
In the unlikely case that TC = is proven, would have great consequences for com- plexity theory in general, analogous to the case where P NP is proven. This rejects the fundamental assumption in the theorem.
By employing a serial learning algorithm that runs in polynomial (not polylog) time, one may discover the right policy, which then be compressed down into policy that runs faster than serial. This bypasses the "L-uniform" part the obstacle.
By allowing the learned policy or value function to be non-parallel, the "TC circuit family" part of the obstacle is bypassed. This is true for certain RL algorithms, especially model- based methods that simulate the environment dynamics before making a decision.
For some RL applications, one may be able tolerate arbitrarily poor worst-case perfor- mance, long they occur rarely.
Part (b) of the theorem may explain the observation in Kevin et al. (2025). In that work, they trained both policy networks and value function networks by actor-critic methods, and noted that using deeper networks both policy and value function improved performance. Part (b) of the theorem suggests that, when the network for approximating the value function contains less serial compute than the environment demands, then the corresponding exact V-maximizing policy would suffer arbitrarily bad worst-case performance. Though the theorem does not exactly apply when the policy inexact, it suggests that the same phenomenon happens for an actual policy network trained to merely approximate the V- V-maximizing policy.
31


Reviews:
[{"review_id": "EKbPgrBl3m", "reviewer": "Reviewer_wmHT", "summary": "The paper reveals that modern machine learning overlooks problems that are fundamentally sequential and cannot be parallelized. It formalizes this distinction in complexity theory, showing that parallel architectures face theoretical limitations on such tasks. The study further shows that diffusion models also fail on inherently serial problems.", "questions": "In reasoning QA tasks, could more ablation about CoT or not be provided? The claims here try to specialize the type of QA as inherently serial, but it's hard to say that the reasoning and knowledge are decoupled and the models are actually reasoning without ablation.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The writing is concise and sharp and the study focuses on a precise and underexplored question: the boundary between parallel and inherently serial computation.\n- Examples from reasoning, physics, and decision-making vividly illustrate what “inherently serial” means. Theoretical formalization combined with diffusion model evidence creates a rigorous and convincing argument.", "weaknesses": "- The proposed hypothesis trys to introduce computational complexity of serial dependency into model performance evaluation. However, the many-body example of serial problem is a prediction task on chaotic systems, where, even if we have ground truth labels and prior knowledge to train a model, the generalization performance is doubtfully discussed by a general hypothesis and experimental supports. This stems from the nature of the problem itself. It seems not good to use a many-body case here.\n- Further numerical experiments with claim-relate analyses can validate the relevant conclusions and explore future research directions, such as how to verify the proposed hypotheses. This will make the factual existence clearer to the audience.", "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": "AaYEYETUSq", "reviewer": "Reviewer_LMw7", "summary": "The paper argues that some problems are inherently serial and cannot be efficiently parallelized, identifying a conceptual blind spot in current scaling approaches in machine learning. The authors formalize this distinction through computational complexity theory and apply it to modern ML architectures, contending that the diffusion models cannot effectively handle inherently serial tasks. They support this argument by linking theoretical limits on parallelism with empirical patterns observed in reasoning, simulation, and decision-making tasks.", "questions": "1) Can you extend your theory to diffusion models that are trained with auto-regressive objectives or structurally autoregressive generation structures, such as block diffusion? This is a very important point to address for the serial scaling hypothesis to have practical implications for diffusion models in architectural design. \n2) Comment on the translation of the work to papers like https://github.com/DreamLM/Dream-Coder\n3) What concrete architectural or hardware implications follow from your theory?\n\nI enjoyed the paper as a whole, but I can't recommend accepting unless weakness (4) and question (1) are addressed. This is my main issue with the work.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1) Raises a meaningful point: not all tasks yield to parallel scaling.\n2) Connects established computational theory to machine-learning practice.\n3) The theoretical framing is clear and potentially useful.\n4) Adds to the discussion on the limits of diffusion and transformer architectures.\n5) Writing and diagrams were very clear.", "weaknesses": "1) Novelty is limited; the serial/parallel distinction is long-established in complexity theory.\n2) Lacks new experiments or empirical demonstrations.\n3) The implications for model or hardware design remain abstract.\n4) The critique of diffusion models is not representative of how text diffusion models are commonly trained today.", "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": "Ra2YjnWJqo", "reviewer": "Reviewer_U8Ci", "summary": "This paper examines the limitations of parallel scaling in modern machine learning algorithms, with a particular focus on diffusion models. The authors advocate the necessity of serial computation to overcome these limits, through the titular 'serial scaling hypothesis'. Through various examples they argue that many ML tasks require moving out of the $\\textsf{TC}^0$ complexity class. The paper concludes with a theorem arguing that diffusion models with $\\textsf{TC}^0$ backbones remain within $\\textsf{TC}^0$, even with infinite sampling steps.", "questions": "Small typo around line 474: 'which', not 'whiche'.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is a little outside my main area of expertise. I suspect I was assigned to review this due to my experience with diffusion models, so I will focus most of my comments around that area. I have made an effort to understand other parts but it is very possible that there are aspects of the paper that I did not absorb. Overall, I noticed the following strengths:\n\n1. The paper is well written and the authors make a compelling case in favor of serial compute capabilities in the next epoch of ML models.\n\n2. They clearly state the limitations and assumptions behind their statements, and clarify several misconceptions that arise when talking about serial vs. parallel compute in ML. In particular they address how an architecture that is parallel, when paired with an appropriate inference procedure, can capture inherently serial computations (Sec. 2.3). I found this very helpful when trying to understand their theorem on diffusion models. I had in mind a video diffusion model which is rigged to predict the $N+1$-th frame given the first $N$ frames. Such a model can, in principle, be configured in a sliding window manner to auto regressively continue the video. If the video shows a many-body physics problem (an example from the paper) then the whole setup solves a serial problem. If I understood correctly, theorem 4.1 in the paper applies to only one of these steps, where a single frame is predicted. The latter is independent of $N$.", "weaknesses": "1. The proof of theorem 4.1 assumes that scores are known perfectly, which is never the case in a practical diffusion model. While the authors acknowledge this limitation in the comment at the end of App. F.2, and around line 485, they leave the practical case for future work. But this does undercut their contribution somewhat, since it is highlighted as the 'main theorem' in the paper, and since the limitations of approximate scores are central to all realistic diffusion models. Is there an opportunity here to add some experiments to bolster the claim that a generalized version of the main theorem applies if $f_\\theta$ is good enough? At the very least, when speaking about the main theorem in the main text, it could be stated that it applies in an idealized limit.\n\n2. The proof also relies on non-uniform circuit complexity, which is strictly stronger than the usual uniform classes most ML models implicitly correspond to. The former allows for a magic constant to be stored in each circuit. Since these advice strings need not be efficiently derivable or implementable in practice, it is not clear to what extent this result constrains the computational behavior of real diffusion models. A brief discussion clarifying the practical implications of this non-uniformity assumption would strengthen the claims.\n\n3. The paper initially suggests diffusion is sequential, then proves that its step-structure provides no serial scaling. I think this is conflating serial in auxiliary diffusion time (the iterative denoising schedule) with serial in data-dependent logical dependencies (the kind of seriality complexity theory cares about). Although the authors eventually clarify that they are talking about the latter, it felt like they were conflating the two to setup the premise.\n\nOverall, the conceptual contribution of the paper feels timely, and with some clarification around Theorem 4.1, I think the paper could be strengthened further.", "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)