When does sequential reasoning beat parallel voting?

The prevailing empirical finding is that parallel sampling outperforms sequential extension under fixed token budgets (see Why does parallel reasoning outperform single chain thinking?). The "Let Me Think!" paper identifies a class of problems where this reverses — and the reversal is exponential, not marginal.

The setting: graph connectivity tasks, where the model must determine whether vertices are connected by stepping through several edges. This is a proxy for structured multi-step reasoning — any problem where sub-results must be sequentially composed and the correct solution path has a specific depth structure. For these tasks:

• Sequential CoT achieves high accuracy because the chain preserves intermediate results and builds on them step by step.
• Parallel voting (majority voting across multiple short chains) fails because each short chain lacks enough steps to reach the answer; generating more independent short chains does not compensate.

The exponential gap arises because graph connectivity is computationally sequential at its core — bounded-depth transformers struggle with it exactly because they cannot perform arbitrarily deep sequential computation in a single forward pass. CoT, by externalizing intermediate steps into the context window, effectively increases the depth available.

This is a fundamental qualification of the parallel-wins claim, not a contradiction of it. The reconciliation is task structure:

• Parallel wins when: multiple independent attempts at a problem all have sufficient depth to reach an answer; diversity of paths matters more than depth of any single path.
• Sequential wins when: the problem's solution genuinely requires sequential accumulation of intermediate results that cannot be independently computed in shorter chains.

The practical heuristic: if solving a shorter version of the problem would not give useful information toward the longer version, parallel sampling is ineffective — each short chain is simply an incomplete attempt. Sequential extension is the only way forward.