thread on the new paper: The Serial Scaling Hypothesis joint work...

Two graphs can have the same number of nodes, and thus the same total compute cost, but still very different. One may be wide & shallow, another narrow & deep.
A hard sudoku may cost the same FLOPs as 1000 trivial ones, but the compute graph of the hard-sudoku may be narrow & deep, while the compute graph of the 1000-trivial-sudoku is wide & shallow.
The thesis of the paper is that modern machine learning practice has neglected serial scaling.
deep & narrow: recurrent network rollout, computing Pi to 1 trillion digits, traditional imperative programming. CPUs are made for these.
[What about the other 2 cases? Well, we're only considering the Pareto front. If you have hardware that can do wide & deep, then you wouldn't want to do anything that's wide & shallow or narrow & deep. Similarly, since we have hardware to do wide & shallow and narrow & deep, there is no point in doing narrow & shallow.]
As a toy example, solving a hard sudoku *can* be done in O(1) parallel steps -- if you can afford to buy 9^(9×9) processors.
Each processor simply tries one possible way to fill the blanks, then checks it. If no errors, it then outputs the answer.
For this reason, we demand polynomial width for a parallel algorithm, because the exponential width case is embarrassingly trivial.
[Any problem is embarrassingly trivial if your wallet isn't embarrassed.]
1. Experience has shown that any algorithm that is "practical" to compute in the real world on any computer (single-core or many-core), is computable in polynomial time in theory.
[This really deserves a name! Maybe call it the "Cook–Levin thesis"? In analogy with the "Church–Turing thesis".]
2. Thus, we should concern ourselves purely with problems computable in polynomial number of FLOPs.
3. If we have an algorithm that runs on polynomially many cores for polynomially many steps, then... we could have run it for polynomially many steps on a single core! What's the selling point of that?
4. Thus, to show that parallelism helps, we need to find algorithms that run on polynomially many cores for LESS-THAN-polynomially many steps.
What is the most natural thing that's less than polynomial? Answer: polylogarithmic. For example: log(n)^3 + log(n).
Thus, we end up with the definition of what a parallel algorithm is: An algorithm that has a computational graph that grows polynomially in width and polylogarithmically in depth.
Basically, any problem that is naturally formulated as "one step after another" without opportunities to skip steps. We call these problems "inherently serial".
Some prototypical cases are:
1. Given a cellular automata beginning state, find its state T steps later. If the automata is Turing-complete (such as in Rule 30), then you can't skip steps.
2. Given a list of arithmetic expressions, such that latter ones depend on the results of previous ones, find the result of the last expression. Many math benchmarks (like GSM8K) are in essence this.
3. Given a list of balls and their positions and velocities, find where they'll be after time T. The "world models" probably contain this as a subproblem.
Search "TC0" "Nick's class" or "P-completeness" for more.
"Limits to parallel computation: P-completeness theory" contains about 200 such inherently serial problems.
* Chain of thought.
* Use a recurrent net.
* Use a network whose middle layers can be repeated to process hard problems. People have done this! It's called "log-depth transformer". You can think of it as "Chain of Thought in neuralese".
* Use a wider network.
* Use a state-space model (SSM). It's pretty amusing, but SSM was like Transformer in this regard. Both were designed to be parallelizable recurrent nets, and both suffer from lack of seriality precisely because they are parallelizable.
There seems to be no free lunch: If your architecture is parallelizable, then it cannot solve inherently serial problems -- unless you reintroduce it, by methods like chain of thought.
* Use a diffusion sampler. People seem to find this unintuitive, but it turned out that, because diffusion converges rapidly, even denoising for infinitely many steps does not actually allow you to solve problems that are more serial than what the denoising model can solve in 1 forward pass.
* Title inspired by the @gwern essay "The Scaling Hypothesis".
* The "other paper" was submitted on 04-20 and was stuck "On Hold" for 80 days. Then we sent an email to arXiv mods, and that got the paper through the queue in 2 days. arxiv.org/abs/2507.12469
* The early draft, before we joined the team, was on "computational irreducibility" with cellular automata being the main example. We changed the framing to "serial scaling", because we dislike Stephen Wolfram.
* Some material was early cut out from the paper and moved to the blogpost instead, since they are too speculative. yuxi.ml/essays/posts/p…
* Paper was desk-rejected from NeurIPS position track because they require the title to be an exhortative grammatical sentence. So it would have to sound something like "We should be scaling models serially".

We’ve scaled AI by making everything bigger and more parallel: Our models are parallel. Our scaling is parallel. Our GPUs are parallel.
But what if the real bottleneck isn’t size—but depth?What if the model just didn’t have enough serial steps to get it right? Some problems need depth, not width.
This is the Serial Scaling Hypothesis.
This is not the same as recent studies in scaling test-time compute, which focus on train vs. test and are agnostic to parallel vs. serial.
For example: test-time majority voting increases compute by running models in parallel — but doesn’t help when the task itself is serial.
We argue: what really matters is how the compute is structured. And for many real-world problems, it must be serial.
Read more at: arxiv.org/abs/2507.12549 or 🧵.
(In collaboration with: @layer07_yuxi , Kananart Kuwaranancharoen and @YutongBAI1002 )









