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.
Figures & tables
Figure 1: (Left) Many easy Sudoku puzzles, where the circled blanks can be filled independently in parallel. (Right) A hard Sudoku with the same total compute, but the circled blanks are interdependent, requiring sequential reasoning.
Figure 2: . (A) A decision problem has a variable-size input 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 as input and outputs a discrete value of the row N at cell i for i∈{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 a question as input and outputs the answer autoregressively, with each output from a fixed set of possibilities.
Figure 3: The complexity classes are nested as TC0⊆TC1⊆⋯⊆TC⊆P . Each containment is widely believed to be strict. Problems in TC are parallel, while those outside are inherently serial.
Method
Parallel?
Solve serial problem?
FF MLPs
✓
✗
FF Transformers
✓
✗
FF SSMs (Mamba)
✓
✗
RNNs
✗
✓
Repeating layers
✗
✓
Chain-of-Thought
✗
✓
Table 1: Parallelizable models are limited to parallel problems. Only non-parallelizable models may solve inherently serial problems. FF stands for Feedforward.
Figure 4: A single run of Rule 110. Given the top row, the CA evolves row-by-row according to the 8 rules.
Figure 5: Predicting the frame at time T . The intermediate frames may not be observable by camera motion/occlusion.
Figure 6: Empirical serial scaling on (a) Hex board game and (b) locomotion & manipulation.
Figure 7: Average benchmark scores over 4 math benchmarks for longer reasoning chains (in different colors) vs. majority voting (as dots along each line). Data from Aggarwal and Welleck (2025) .
Figure 8: The backbone network takes as input a sequence of tokens, and a single noisy output token. This is repeated until the output token is fully denoised.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Serial
Parallel
Scaling
Depth
Width
Architecture
RNN
Transformer
Algorithm
RL
Imitation learn.
Hardware
CPU
GPU
Appendix
Table 2: Examples of serial and parallel approaches.