Why does parallel sampling fail on graph connectivity tasks?
This explores why generating many independent short answers and voting (parallel sampling) breaks down specifically on tasks like graph connectivity — where you have to trace a path through linked nodes — and what that reveals about the difference between width and depth in reasoning.
This reads the question as being about a specific failure: when a model spins up many independent samples and votes on the answer, it does badly on graph connectivity (is node A reachable from node B?), even though that same trick works fine elsewhere. The sharpest answer in the corpus is that connectivity is a genuinely *compositional* problem — the answer only exists once you've accumulated a chain of intermediate results, hop by hop. When does sequential reasoning beat parallel voting? shows chain-of-thought beats parallel voting *exponentially* on exactly these structured tasks, because short parallel chains never build the dependency chain the solution requires. Voting can average away noise, but it can't conjure a multi-step derivation that no single short sample ever completed. Width doesn't substitute for depth when each step depends on the one before it.
There's a second, more uncomfortable reason hiding underneath. Even when a model looks like it's reasoning over a graph, it may not be using the graph's actual edges at all. Can language models actually use graph structure information? found that LLMs learn to *recognize* graph-shaped input — attention drifts toward node tokens — but randomly shuffling the topology barely dents performance. The model treats a graph as a genre to pattern-match, not as a set of connections to traverse. If the underlying single-sample reasoning isn't truly following edges, then sampling a hundred such guesses and voting just amplifies a confident misread.
The corpus also reframes what parallelism is good for, which clarifies what it's bad at. Methods like Can reasoning systems scale wider instead of only deeper? and Can we explore multiple reasoning paths without committing to one token? use parallel/superposed paths to *explore* a solution space cheaply — sampling many candidate routes without committing. That's powerful when answers are independent draws from a distribution, but graph connectivity isn't that: it's a serial computation with a right answer at the end of a chain, not a popularity contest among guesses.
There's a useful nuance from Does step-level confidence outperform global averaging for trace filtering?: it's not quantity of traces that helps but quality, caught at the *step* level. Global averaging (the spirit of majority voting) masks exactly the mid-chain breakdown where a connectivity proof goes wrong; step-level confidence catches the broken hop. So even within sampling-based methods, the fix points back toward respecting the sequential structure rather than flattening it.
The thing you didn't know you wanted to know: this isn't really a quirk of graphs. Graph connectivity is just the cleanest test case for a general boundary — parallel sampling helps where solutions are independent and verifiable in one shot, and collapses where they must be *grown* one dependent step at a time. Can non-reasoning models catch up with more compute? makes the matching point from the other side: piling on inference compute can't rescue a model whose training never instilled a step-by-step protocol. Depth has to be earned in the trajectory, not bought in bulk.
Sources 6 notes
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.
LLMs develop attention shifts toward node tokens after training, but randomly shuffled topology barely affects performance. Models treat graph data as a category to recognize rather than as structured relationships to use.
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.
Training-free method replaces discrete token selection with probability-weighted concept embeddings, preserving superposition of reasoning paths. Improves accuracy up to 2.48 points while reducing tokens 22.4% via entropy-based early stopping.
Local step-level confidence catches reasoning breakdowns that global averaging masks and enables early stopping before traces complete. This approach achieves comparable accuracy gains to naive majority voting with far fewer generated traces, proving trace quality matters more than quantity.
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.