What makes a problem fundamentally sequential versus parallelizable?
This explores what determines whether a problem must be solved one step at a time (sequentially) versus broken into independent pieces solved at once (in parallel) — and why that distinction is now a central design choice in how AI systems reason.
This explores what makes a problem fundamentally sequential — solvable only by accumulating one result before computing the next — versus parallelizable, where independent attempts can run side by side. The sharpest answer in the corpus comes from complexity theory: some problems require polynomial-depth reasoning, and no parallel architecture, including Transformers, can solve them no matter how much you scale width. Real progress on those problems needs recurrent structure that genuinely increases serial computation depth Can parallel architectures solve inherently sequential problems?. The tell for a sequential problem is whether each step *depends on the accumulated result of the prior one*. Graph connectivity is the canonical example: chain-of-thought reasoning beats parallel voting by an exponential margin there, because the solution literally has to be built up step by step, and short parallel chains can never reach the needed depth When does sequential reasoning beat parallel voting?.
The flip side is just as instructive. When sub-problems are short and independent, parallelism wins decisively — multiple independent reasoning paths with majority voting beat one extended chain by up to 22% under the same token budget, because diverse sampling captures a model's capability more faithfully than stretching a single chain, which mostly inflates variance Why does parallel reasoning outperform single chain thinking?. So there isn't one right answer; there's a trade-off keyed to task structure. Parallel scaling buys you *coverage* (sample the solution space widely), sequential scaling buys you *depth* (accumulate intermediate state) — and the corpus frames this as the recurring decision in test-time compute How should we balance parallel versus sequential compute at test time?. The fundamental property of a problem is which of those two resources it actually demands.
What's surprising is how much engineering goes into *converting* sequential-looking problems into parallel-friendly ones. GRAM samples parallel latent trajectories to get depth-like benefits without paying the serial latency cost Can reasoning systems scale wider instead of only deeper?. Atom of Thoughts decomposes a problem into a DAG and contracts it so each state depends only on the current sub-problem, not the full history — a deliberately *memoryless* reformulation that strips out the sequential baggage while preserving the answer Can reasoning systems forget history without losing coherence?. Recursive subtask trees do something similar, breaking a long chain into a structure that can be pruned and partly parallelized Can recursive subtask trees overcome context window limits?. The lesson: 'sequential' is partly a property of the problem and partly a property of how you've chosen to represent it. Find the right decomposition and a chain becomes a tree.
But decomposition has limits, and that's where the genuinely sequential problems show their teeth. Constraint satisfaction — which requires real backtracking, where each choice constrains the next — defeats even frontier reasoning models, which top out at 20–23% exact match Can reasoning models actually sustain long-chain reflection?. The productive response there isn't more parallel sampling; it's to let the LLM do the parallelizable part (translating messy input into formal structure) and hand the irreducibly sequential numeric search to a deterministic solver Should LLMs handle abstraction only in optimization?. And a caution against reading depth off the surface: longer reasoning traces don't reliably indicate harder, more-sequential problems — trace length tracks how close a problem sits to the training distribution, not its intrinsic computational depth Does longer reasoning actually mean harder problems?. The thing you didn't know you wanted to know: sequentiality is a structural property of the computation a problem requires — provable from complexity theory — not something you can infer from how long a model talks about it.
Sources 10 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.
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.
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.
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.
Atom of Thoughts decomposes problems into DAGs and contracts them iteratively, ensuring each state depends only on the current problem—not prior steps. This memoryless approach eliminates historical baggage that bloats reasoning while maintaining answer equivalence.
The Thread Inference Model demonstrates that reasoning structured as recursive subtask trees with rule-based KV cache pruning sustains accurate reasoning beyond context limits, even when manipulating 90% of the cache. This enables single models to replace multi-agent systems by handling full recursive reasoning internally.
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.
LLMs plateau at constraint satisfaction regardless of scale, but excel at natural-language-to-formal-structure translation. The productive architecture restricts LLMs to reading input and emitting solver code, leaving numeric iteration to deterministic solvers.
Controlled A* maze experiments show trace length correlates with difficulty only in-distribution but decouples entirely out-of-distribution. Trace length primarily reflects recall of training schemas, not adaptive computation.