The Serial Scaling Hypothesis

TL;DR

Position paper arguing that machine learning has scaled almost entirely along the parallel axis (width, GPUs, Transformers) and that this is structurally insufficient for problems whose computational steps are mutually dependent — “inherently serial” problems like hard Sudoku, cellular automata, many-body physics, sequential decision-making, and long-form math reasoning. The authors formalize the parallel/serial split via the TC complexity hierarchy (problems outside TC are inherently serial) and show that Transformers, SSMs/Mamba, and — most surprisingly — fixed-depth diffusion models all sit inside TC⁰, so none can solve inherently serial problems regardless of how many tokens, parameters, or denoising steps they get. Only RNNs, layer-repeating / looped architectures, and autoregressive chain-of-thought escape that bound. The practical prescription: depth and CoT length must be scaled as first-class compute axes, not collapsed into “FLOPs”, and hardware roadmaps should treat low-latency serial processing as a separate target from raw parallel throughput.

Key claims

The Serial Scaling Hypothesis: for problems involving complex reasoning, planning, or evolution of interacting systems, increasing parallel computation alone is insufficient — progress requires scaling serial computation (sequential dependent steps) [§1, §2.4].
Formal split: a problem is parallel if it lies in TC (solvable by polynomial-width, polylog-depth threshold circuits / MLPs), otherwise inherently serial [Def. 2.1, Def. 2.2].
Standard feedforward networks, fixed-precision Transformers, and linear state-space models of polynomial size and constant depth are all simulable by uniform TC⁰ threshold circuits — i.e. they cannot solve any inherently serial problem regardless of width [Theorem 2.4].
Diffusion models with a fixed-depth backbone also lie in TC⁰ and cannot solve inherently serial problems even with infinite diffusion steps — the first formal proof of this result [§2.3, §5; Table 2].
Truly serial models (RNNs, repeating/looped layers, autoregressive Chain-of-Thought) fall outside TC and can capture dependencies that unfold across input tokens [§2.3, Table 2].
A Transformer instance is “atomic” — its capability class is determined by architecture × inference method: one forward pass = parallel (TC⁰), autoregressive CoT with O(n) forward passes = serial; the confusion between architecture and inference method is a recurring failure mode in the literature [§3.1].
SSMs/Mamba look recurrent but are not inherently serial: their state updates are linear and data-independent, so they parallelize the same way Transformers do, sharing the TC⁰ bound [§3.2].
Reducing serial depth on inherently serial problems costs exponentially more parallel width — a recurring depth–width trade-off in complexity theory, illustrated by cellular automata where evolving k rows in one parallel step needs 2^(2k+1) lookup rules [§4.1].
Rule 110 cellular automata are Turing-complete, so predicting cell states is inherently serial; many-body Newtonian mechanics is similarly Turing-complete via billiard-ball computers (Fredkin & Toffoli) [§4.1, §4.2].
A rule of thumb for ODEs: slow-changing trajectories tend to be parallelizable (e.g. Parareal with an accurate coarse solver); fast-changing trajectories are inherently serial [§4.2].
Practical generalization hypothesis: models learn many algorithms during training (memorization → fast heuristics → general solutions); when inference-time serial compute is insufficient they default to the fastest routines, which fail to generalize beyond the training distribution. RL fine-tuning is conjectured to elicit the longer, more general routines [§2.4].
Hardware implication: serial computation cannot be substituted by more parallel — future progress depends on low-latency sequential processing; the position paper explicitly calls for revival of CPU-style / memory-integrated designs alongside GPUs [§2.4].

Method

The paper is theoretical / position rather than empirical. The argument has three layers. (1) Use the TC complexity hierarchy as the formal divider between problems an MLP-like network can solve in polylog depth (TC) and those that cannot (everything outside TC, declared “inherently serial”). Reduce a problem to a decision problem (yes/no over input tokens) so the circuit-complexity machinery applies generally — Section 2 shows how cellular automata, many-body mechanics, and open-ended QA all fit. (2) Place common ML architectures inside or outside TC⁰: constant-depth MLPs, Transformers, and linear SSMs all admit a uniform threshold-circuit simulation (Theorem 2.4, building on Merrill / Sanford / Chiang etc.); diffusion models with a fixed-depth backbone are newly placed in TC⁰ in Section 5, where the iterative denoising is shown to collapse under the parallel-circuit simulation; RNNs, layer-repeating networks, and Chain-of-Thought inference are explicitly placed outside TC. (3) Cross-check with empirical evidence on tasks where the literature has already reported failures of parallel models — hard Sudoku, math reasoning, planning, video prediction — and interpret those failures through the lens of the formal bound. A short “potential misconceptions” Section 3 untangles architecture-vs-inference (Transformer + CoT ≠ Transformer alone), SSM-is-not-RNN, and training-vs-inference (the paper’s claims are inference-time; the authors acknowledge they could not get a theoretical handle on the training-time parallel/serial split and leave it open).

Results

Architecture taxonomy (Table 2): MLPs ✓ parallel ✗ serial; Transformers ✓ parallel ✗ serial; SSMs/Mamba ✓ parallel ✗ serial; RNNs ✗ parallel ✓ serial; repeating layers ✗ parallel ✓ serial; Chain-of-Thought ✗ parallel ✓ serial; diffusion models with fixed-depth backbone ✗ parallel ✗ serial — the only entry in the table that is in neither class, since they are not yet parallelizable but cannot solve serial problems either [Table 2].
New formal result: diffusion models with a fixed-depth backbone are simulable by uniform TC⁰ circuits regardless of the number of denoising steps [§5; called out as “first proven here” in §2.3].
The Rule 110 CA argument and the billiard-ball Turing simulation give two independent existence proofs that real-world-relevant problems sit outside TC, blocking any clean “all problems are eventually parallel” position [§4.1, §4.2].
No empirical experiments — the paper is a position / formal-results paper. Three arXiv revisions through Feb 2026; co-author Konpat Preechakul promoted v3 on X (Oct 2025) with a thread emphasizing the diffusion result.

Why it’s interesting

This paper provides the theoretical scaffolding under which the wiki’s Looped Transformers cluster is currently working — looped Transformers, HRM-Text, Hyperloop, and Generative Recursive Reasoning are all attempts to add serial depth back to architectures that the Serial Scaling Hypothesis says cannot solve inherently serial problems otherwise. The framing flips the standard reading of Less is More: Recursive Reasoning with Tiny Networks and HRM-Text: Efficient Pretraining Beyond Scaling from “small recurrent nets compete with big Transformers” into “the only way the small recurrent nets can be competing is that the big Transformers were never in the right complexity class to begin with.” The diffusion result is the surprising one and the reason this tweet circulated: it cuts directly against the Test-time scaling of diffusions with flow maps / flow-map literature in Inference-Time Scaling which argues you can buy more capability from diffusion by spending more denoising steps — Liu et al. say a fixed-depth backbone diffusion model with infinite steps is still in TC⁰. It also reframes the The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity result (reasoning models collapse past a complexity threshold) as the expected outcome rather than a surprise: complexity tells you when CoT runs out of serial budget. The paper’s “atomic Transformer” architecture-vs-inference distinction also sharpens how the Reasoning RL cluster should report compute — total FLOPs collapses width and depth into one number; the hypothesis says they’re not interchangeable.