Can sequential computation through depth solve problems that parallel width cannot?
This explores whether stacking computation in sequence — reasoning step-by-step, layer-by-layer, or through recurrence — can crack problems that simply running more independent attempts in parallel never will.
This explores whether sequential depth (chained, recurrent, step-after-step computation) buys you something that parallel width (many independent attempts run side by side) fundamentally cannot. The corpus answer is: yes, for a specific and provable class of problems — and the boundary between the two is one of the sharper dividing lines in the whole collection. The strongest version of the claim is a complexity-theory result: some problems are *inherently sequential*, requiring polynomial-depth reasoning that no parallel architecture — Transformers included — can solve even with infinite scaling Can parallel architectures solve inherently sequential problems?. Progress on those requires recurrent structure that genuinely increases serial computation depth.
The reason shows up concretely in reasoning behavior. On compositional tasks like graph connectivity — where the answer requires accumulating intermediate results in order — sequential chain-of-thought achieves an *exponential* accuracy advantage over parallel voting, because short parallel chains simply cannot reach the answer no matter how many you sample When does sequential reasoning beat parallel voting?. This is the cleanest statement of the trade-off the corpus keeps returning to: parallel methods improve coverage and width; sequential methods enable depth; the right choice depends on whether the task is a bundle of short independent problems or a single long compositional chain How should we balance parallel versus sequential compute at test time?.
Here's the twist that makes this interesting rather than obvious: parallel width often *wins*, and within the same budget. When tasks don't demand serial accumulation, sampling many independent reasoning paths and majority-voting beats extending one chain by up to 22% — because a single long chain inflates variance without improving correctness Why does parallel reasoning outperform single chain thinking?. Some systems even try to get depth's benefits with width's latency by sampling parallel latent trajectories instead of paying the serial cost Can reasoning systems scale wider instead of only deeper?. So the honest answer isn't 'depth beats width' — it's that they solve different shapes of problem, and you lose badly by using one where the other belongs.
The depth-as-architecture story runs parallel to depth-as-reasoning. At tiny scale, deep-and-thin models beat balanced ones because composing abstract concepts through *layers* matters more than spreading parameters across width Does depth matter more than width for tiny language models?. And the most striking corpus result: a hierarchical recurrent model with only 27M parameters solves Sudoku and mazes near-perfectly — tasks where chain-of-thought fails completely — by achieving effective computational depth that escapes the fixed-depth complexity ceiling of standard transformers Can recurrent hierarchies achieve reasoning that transformers cannot?. Recurrence, in other words, manufactures the serial depth the architecture otherwise lacks.
What you didn't know you wanted to know: more sequential depth doesn't automatically deliver the competence it promises. Frontier reasoning models that *look* fluent at long reflective chains hit a 20–23% ceiling on constraint-satisfaction problems requiring genuine backtracking Can reasoning models actually sustain long-chain reflection?. And the gap between reasoning and non-reasoning models persists at any inference budget — because depth only pays off when training has installed a protocol that makes the extra serial tokens productive Can non-reasoning models catch up with more compute?. Depth is necessary for the inherently-sequential class, but it isn't sufficient on its own — you also need a model trained to spend it well.
Sources 9 notes
Complexity theory proves that problems requiring polynomial-depth reasoning cannot be solved by parallel architectures like Transformers, even with infinite scaling. Progress requires recurrent structures that increase serial computation depth.
On structured tasks requiring sequential multi-step reasoning like graph connectivity, chain-of-thought achieves exponentially higher accuracy than parallel voting. The difference emerges because solutions genuinely require accumulating intermediate results sequentially, which short parallel chains cannot achieve.
Parallel methods improve coverage; sequential methods enable depth. The optimal choice depends on task structure: parallel wins for independent short problems, sequential for compositional chains requiring intermediate accumulation.
Multiple independent reasoning paths with majority voting achieve up to 22% higher accuracy than extending a single chain under the same token budget. Parallel diversity samples reasoning capability more faithfully than sequential extension, which inflates variance without improving correctness.
GRAM shows that stochastic latent transitions enabling parallel trajectory sampling sidestep the serial latency cost of depth-only scaling. Width matches token-level parallelism benefits: independent paths sample the solution space without variance inflation.
MobileLLM shows deep-and-thin architectures yield 2.7–4.3% accuracy gains over balanced designs at 125M–350M scale by composing abstract concepts through layers rather than spreading parameters across width.
The Hierarchical Reasoning Model couples slow abstract planning with fast detailed computation across two timescales, achieving near-perfect performance on Sudoku and mazes where chain-of-thought methods fail completely. With only 27M parameters and 1,000 samples, HRM escapes the AC0/TC0 complexity ceiling that constrains fixed-depth transformers.
DeepSeek-R1 and o1-preview achieve only 20-23.6% exact match on 850 constraint satisfaction problems requiring genuine backtracking. This ceiling reveals that reflective reasoning fluency does not translate to actual problem-solving competence on unfamiliar instance structures.
Reasoning models persistently outperform non-reasoning models regardless of inference budget because training instills a reasoning protocol that makes additional tokens productive. The gap is fundamentally about deployment mechanisms and training structure, not raw capability.