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.
Test-time scaling improves language model reasoning by spending additional compute at inference. However, both classes of existing methods often fail to continue improving over long timescales. Parallel methods repeatedly sample independent answers from the model, scaling poorly on problems the model is unlikely to solve in a single attempt. In contrast, sequential methods build on previous answers to access new ideas, yet so far have not been shown to reach answers beyond those found by parallel scaling. First, we show that sequential scaling often stops improving because it becomes prematurely trapped in an attractor: a set of answers that prevents exploration of different answers once entered. Across 27 combinations of scaling methods, models, and benchmarks, we find that 53.8% of sequential scaling trajectories enter an attractor within four iterations. Second, we show that a simple model-mixing intervention helps escape attractors. This reduces the attractor hit rate by 21.2 percentage points on average, expands solution coverage beyond a compute-matched parallel baseline, and improves accuracy of recursive self-aggregation by at least 2.2 percentage points. Our results motivate refocusing long-horizon test-time scaling from parallel methods to sequential methods that improve previous answers.
Large language models generate tokens sequentially, but can they execute multiple tasks concurrently while forming each token? Broader attention allocation may provide a mechanism for such task concurrency. Existing approaches to scaling inference primarily rely on longer generations, more samples, or additional verification stages, while attention dispersion is often treated as a signal of interference or error. Task concurrency within serial generation therefore remains underexplored. We propose the Model Hyper-Threading Hypothesis and evaluate its predictions using multiple coordinated tasks that share state within the same problem. We design three conditions (Baseline, Serial Functional Scheduling, and Concurrent Functional Loading) and evaluate their benefits and costs using accuracy, output-token distributions, and attention metrics. On an AIME 2025 development set, Concurrent Functional Loading achieves the highest accuracy. Relative to Serial Functional Scheduling, its typical output length is similar and it is shorter on most problems, while exhibiting greater attention dispersion and higher task-relevant coverage, albeit with a heavier output-length tail. Within-step concurrency and its causal mechanism still require direct tests. Our results show that more dispersed attention can coexist with higher accuracy, providing preliminary behavioral and correlational evidence for the hyper-threading hypothesis. These findings motivate a shift in perspective on inference scaling from "generating more tokens" toward "having each generation step carry more tasks," pointing to a new avenue for improving reasoning performance.
Large Reasoning Models (LRMs) have shown remarkable performance on challenging questions, such as math and coding. However, to obtain a high quality solution, one may need to sample more than once. In principal, there are two sampling strategies that can be composed to form more complex processes: sequential sampling and parallel sampling. In this paper, we first compare these two approaches with rigor, and observe, aligned with previous works, that parallel sampling seems to outperform sequential sampling even though the latter should have more representation power. To understand the underline reasons, we make three hypothesis on the reason behind this behavior: (i) parallel sampling outperforms due to the aggregator operator; (ii) sequential sampling is harmed by needing to use longer contexts; (iii) sequential sampling leads to less exploration due to conditioning on previous answers. The empirical evidence on various model families and sizes (Qwen3, DeepSeek-R1 distilled models, Gemini 2.5) and question domains (math and coding) suggests that the aggregation and context length do not seem to be the main culprit behind the performance gap. In contrast, the lack of exploration seems to play a considerably larger role, and we argue that this is one main cause for the performance gap.
Xiangming Gu, Soham De, Larisa Markeeva +2
Google DeepMind · National University of Singapore