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

• URL: http://arxiv.org/abs/2505.21825v1
• Date: Tue, 27 May 2025 23:23:34 GMT
• Title: Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones
• Abstract summary: We show the existence of reasoning settings where sequential scaling offers an exponential advantage over parallel scaling.<n>We validate our theoretical findings with comprehensive experiments across a range of language models.
• Score: 19.390296419822562
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Inference-time computation has emerged as a promising scaling axis for improving large language model reasoning. However, despite yielding impressive performance, the optimal allocation of inference-time computation remains poorly understood. A central question is whether to prioritize sequential scaling (e.g., longer chains of thought) or parallel scaling (e.g., majority voting across multiple short chains of thought). In this work, we seek to illuminate the landscape of test-time scaling by demonstrating the existence of reasoning settings where sequential scaling offers an exponential advantage over parallel scaling. These settings are based on graph connectivity problems in challenging distributions of graphs. We validate our theoretical findings with comprehensive experiments across a range of language models, including models trained from scratch for graph connectivity with different chain of thought strategies as well as large reasoning models.

Related papers

• LCoT-GV: Graph Attention Networks for Verifying Long Reasoning Chains in Large Language Models [1.546945230112218]
  We propose a graph-based framework that represents Long Chain-of-Thought Graph Verifier (LCoT-GV) as reasoning graphs.<n>A Graph Attention Network is then trained to predict chain-of-thought correctness from the reasoning graph.
  arXiv  Detail & Related papers  (2026-08-31T12:21:22Z)
• Can Large Language Models "Hyper-Thread"? [2.7787094635105185]
  Large language models generate tokens sequentially, but can they execute multiple tasks concurrently while forming each token?<n>We propose the Model Hyper-Threading Hypothesis and evaluate its predictions using multiple coordinated tasks that share state within the same problem.<n>We design three conditions (Baseline, Serial Functional Scheduling, and Concurrent Functional Loading) and evaluate their benefits and costs using accuracy, output-token distributions, and attention metrics.
  arXiv  Detail & Related papers  (2026-08-23T11:53:03Z)
• Latent Chain-of-Thought as Planning: Decoupling Reasoning from Verbalization [9.193078163792427]
  Chain-of-Thought (CoT) empowers Large Language Models (LLMs) to tackle complex problems.<n>Recent latent reasoning approaches attempt to optimize efficiency by performing reasoning within continuous hidden states.<n>We introduce PLaT, a framework that reformulates latent reasoning as planning by fundamentally decouple reasoning from verbalization.
  arXiv  Detail & Related papers  (2026-01-29T07:38:18Z)
• ChainV: Atomic Visual Hints Make Multimodal Reasoning Shorter and Better [59.29940512530982]
  We propose ChainV, a framework that dynamically integrates visual hints into the reasoning process.<n>Our method significantly improves reasoning accuracy and efficiency, especially on math-intensive benchmarks.
  arXiv  Detail & Related papers  (2025-11-21T10:11:17Z)
• ParaThinker: Native Parallel Thinking as a New Paradigm to Scale LLM Test-time Compute [32.915370020808105]
  ParaThinker is an end-to-end framework that trains an LLM to generate multiple, diverse reasoning paths in parallel.<n>It effectively sidesteps the Tunnel Vision issue and unlocks the model's latent reasoning potential.<n>On challenging reasoning benchmarks, ParaThinker achieves substantial accuracy improvements over sequential LLMs.
  arXiv  Detail & Related papers  (2025-08-30T03:09:07Z)
• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• Do Larger Language Models Imply Better Reasoning? A Pretraining Scaling Law for Reasoning [89.17086632436363]
  We introduce a synthetic multihop reasoning environment designed to replicate the structure and distribution of real-world large-scale knowledge graphs.<n>Our reasoning task involves completing missing edges in the graph, which requires advanced multi-hop reasoning and mimics real-world reasoning scenarios.<n>To predict the optimal model size for a specific knowledge graph, we find an empirical scaling that linearly maps the knowledge graph search entropy to the optimal model size.
  arXiv  Detail & Related papers  (2025-04-04T17:57:22Z)
• Landscape of Thoughts: Visualizing the Reasoning Process of Large Language Models [42.407188124841234]
  Landscape of thoughts is a tool to inspect the reasoning paths of chain-of-thought on any multi-choice dataset.<n>It distinguishes between strong and weak models, correct and incorrect answers, as well as different reasoning tasks.<n>It also uncovers undesirable reasoning patterns, such as low consistency and high uncertainty.
  arXiv  Detail & Related papers  (2025-03-28T06:09:51Z)
• Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning [113.49074603075032]
  Recent studies have shown that making a model spend more time thinking through longer Chain of Thoughts (CoTs) enables it to gain significant improvements in complex reasoning tasks.<n>We explore whether scaling with longer CoTs can indeed impair the reasoning performance of Large Language Models (LLMs) in certain domains.
  arXiv  Detail & Related papers  (2025-02-25T10:48:05Z)
• How Do Large Language Monkeys Get Their Power (Laws)? [20.245443422985154]
  We identify an apparent puzzle: a simple mathematical calculation predicts that on each problem, the failure rate should fall exponentially with the number of attempts.<n>We then answer this question by demonstrating per-problem exponential scaling can be made consistent with aggregate scaling.<n>Our work contributes to a better understanding of how neural language model performance improves with scaling inference compute.
  arXiv  Detail & Related papers  (2025-02-24T19:01:47Z)
• Revisiting the Test-Time Scaling of o1-like Models: Do they Truly Possess Test-Time Scaling Capabilities? [61.85289698610747]
  We study whether o1-like large language models (LLMs) truly possess test-time scaling capabilities.<n>We find that longer CoTs of these o1-like models do not consistently enhance accuracy.<n>We propose Shortest Majority Vote, a method that combines parallel scaling strategies with CoT length characteristics.
  arXiv  Detail & Related papers  (2025-02-17T07:21:11Z)
• A Dynamical Model of Neural Scaling Laws [79.59705237659547]
  We analyze a random feature model trained with gradient descent as a solvable model of network training and generalization. Our theory shows how the gap between training and test loss can gradually build up over time due to repeated reuse of data.
  arXiv  Detail & Related papers  (2024-02-02T01:41:38Z)
• Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models [74.40196814292426]
  We propose Graph-of-Thought (GoT) reasoning, which models human thought processes not only as a chain but also as a graph. GoT captures the non-sequential nature of human thinking and allows for a more realistic modeling of thought processes. We evaluate GoT's performance on a text-only reasoning task and a multimodal reasoning task.
  arXiv  Detail & Related papers  (2023-05-26T02:15:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.