Research map / Large language models / Reasoning and chain of thought

Let Me Think! A Long Chain of Thought Can Be Worth Exponentially Many Short Ones

NeurIPS 2025 · Large language models › Reasoning and chain of thought · approach: Long CoT dynamics and efficiency · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows on graph connectivity tasks that a single long chain of thought can be exponentially more efficient than majority/best-of-n over many short chains, with theory (TC0 expressivity, vertex query model) plus experiments on small trained transformers, STaR RL, and LLMs (Qwen3-32B, DeepSeek-R1-Distill-Qwen-32B, s1-32B).

Problem

Whether inference-time compute is better allocated to sequential scaling (longer chains of thought) or parallel scaling (majority vote or best-of-n over many short chains), which remains poorly understood.

Approach

Identify graph connectivity distributions (two-path and bridge graphs) where sequential scaling yields exponential advantage over parallel scaling, supported by a TC0 expressivity separation, a vertex query model analysis, and experiments with trained transformers and open reasoning LLMs.

Key results

• Shortest-Path and Path models trained from scratch reach 0.0% and 11.16% evidence accuracy on Bridge(5), while the DFS-trained model achieves perfect evidence and decision accuracy.
• STaR fine-tuning raises the Path model's evidence accuracy on Bridge(3) from 21.16% to 92.02% after 4 iterations.
• For LLMs on the bridge graph, sequential scaling of CoT length is essentially required for non-trivial accuracy, and parallel scaling helps only after sequential scaling yields nontrivial performance.

Measured effects reported in the paper

Surprising findings

• Short-CoT models' accuracy matches the exponentially small probability of a random DFS trace following the shortest path, implying parallel sampling needs exponentially many runs.
• Once sequential scale is large enough, parallel scaling becomes more cost-effective again due to diminishing returns, so the optimal mix is problem-dependent.

Limitations

• Results are shown for a specific synthetic graph connectivity task; generality to real-world reasoning is not established beyond a single AIME2024 experiment.
• The Vertex Query Model abstraction is motivated heuristically and lacks direct theoretical backing for transformers.
• Theoretical transformer separation relies on the complexity assumption TC0 not containing L.

Experimental setup

Datasets: synthetic Bridge graph connectivity tasks AIME2024

Benchmarks: Bridge graph connectivity (s,t1,t2) two-path graph connectivity AIME2024

Metrics: decision accuracy evidence accuracy majority vote accuracy best-of-n accuracy

Baselines: Shortest-Path CoT Path CoT DFS CoT majority vote best-of-n

Builds on: Self-Taught Reasoner (STaR) budget forcing globality barrier TC0 expressivity of transformers

Closest papers by meaning

• A Formal Comparison Between Chain of Thought and Latent Thought (ICML 2026 · similarity 0.91)
• Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation (ICML 2025 · similarity 0.91)
• Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning (NeurIPS 2025 · similarity 0.90)
• OptScale: Probabilistic Optimality for Inference-time Scaling (AAAI 2026 · similarity 0.90)
• Reasoning with Latent Thoughts: On the Power of Looped Transformers (ICLR 2025 · similarity 0.90)
• Continuous Chain of Thought Enables Parallel Exploration and Reasoning (ICLR 2026 · similarity 0.90)