From Reasoning to Super-Intelligence: A Search-Theoretic Perspective

• URL: http://arxiv.org/abs/2507.15865v2
• Date: Sat, 26 Jul 2025 07:05:22 GMT
• Title: From Reasoning to Super-Intelligence: A Search-Theoretic Perspective
• Abstract summary: Chain-of-Thought (CoT) reasoning has emerged as a powerful tool for enhancing the problem-solving capabilities of large language models (LLMs)<n>We identify core obstacles that hinder effective CoT learning, including distribution drift, lack of embedded search, and exponential inference costs.<n>We introduce the Diligent Learner, a new learning paradigm that explicitly models reasoning as a depth-first search guided by a validator.
• Score: 19.772800571577747
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Chain-of-Thought (CoT) reasoning has emerged as a powerful tool for enhancing the problem-solving capabilities of large language models (LLMs). However, the theoretical foundations of learning from CoT data remain underdeveloped, and existing approaches -- such as Supervised Fine-Tuning (SFT), Reinforcement Learning (RL), Tree-of-Thoughts (ToT), and Monte Carlo Tree Search (MCTS) -- often fail on complex reasoning tasks. In this work, we identify core obstacles that hinder effective CoT learning, including distribution drift, lack of embedded search, and exponential inference costs. We introduce the Diligent Learner, a new learning paradigm that explicitly models reasoning as a depth-first search guided by a validator and supports backtracking upon failure. Under two mild and realistic assumptions, we prove that the Diligent Learner can efficiently learn from CoT data while existing methods fail to do so. This framework offers a path toward building scalable and reliable reasoning systems trained on naturally occurring, incomplete data -- paving the way for the development of Large Reasoning Models (LRMs) with robust, interpretable problem-solving abilities.

Related papers

• Learning to Reason with Insight for Informal Theorem Proving [50.054221663394195]
  In this work, we identify a primary bottleneck in informal theorem proving as a lack of insight.<n>We propose a novel framework designed to cultivate this essential reasoning skill and enable LLMs to perform insightful reasoning.<n>Our experiments on challenging mathematical benchmarks demonstrate that this insight-aware generation strategy significantly outperforms baselines.
  arXiv  Detail & Related papers  (2026-04-17T17:36:21Z)
• Learning Structured Reasoning via Tractable Trajectory Control [99.75278337895024]
  Ctrl-R is a framework for learning structured reasoning via tractable trajectory control.<n>We show that Ctrl-R enables effective exploration and internalization of previously unattainable reasoning patterns.
  arXiv  Detail & Related papers  (2026-03-02T09:18:19Z)
• Native Reasoning Models: Training Language Models to Reason on Unverifiable Data [16.065264121785294]
  We introduce NRT (Native Reasoning Training), a novel framework that cultivates complex reasoning.<n>NRT reframes the training problem by treating the reasoning process as a latent variable.<n>NRT achieves state-of-the-art performance among verifier-free methods.
  arXiv  Detail & Related papers  (2026-02-12T04:15:46Z)
• FutureMind: Equipping Small Language Models with Strategic Thinking-Pattern Priors via Adaptive Knowledge Distillation [13.855534865501369]
  Small Language Models (SLMs) are attractive for cost-sensitive and resource-limited settings due to their efficient, low-latency inference.<n>We propose FutureMind, a modular reasoning framework that equips SLMs with strategic thinking-pattern priors.
  arXiv  Detail & Related papers  (2026-02-01T13:26:04Z)
• STaR: Towards Cognitive Table Reasoning via Slow-Thinking Large Language Models [12.745473719032026]
  We present STaR (slow-thinking for table reasoning), a new framework achieving cognitive table reasoning.<n> STaR explicitly modeling step-by-step thinking and uncertainty-aware inference.<n>Experiments on benchmarks demonstrate that STaR achieves superior performance and enhanced reasoning stability.
  arXiv  Detail & Related papers  (2025-11-14T12:34:17Z)
• Stabilizing Reinforcement Learning for Honesty Alignment in Language Models on Deductive Reasoning [27.42733470720954]
  We propose a reinforcement learning method that injects ground truth trajectories into rollouts, preventing early training collapse.<n>Our results demonstrate that this method stabilizes learning and significantly improves the overall reasoning performance.
  arXiv  Detail & Related papers  (2025-11-12T11:34:19Z)
• VAR: Visual Attention Reasoning via Structured Search and Backtracking [49.427842994857635]
  We introduce Visual Attention Reasoning, a framework that recasts grounded reasoning as a structured search.<n> VAR decomposes the reasoning process into two key stages: traceable evidence grounding and search-based chain-of-thought.<n>We show that our 7B model, VAR-7B, sets a new state-of-the-art on a comprehensive suite of hallucination and safety benchmarks.
  arXiv  Detail & Related papers  (2025-10-21T13:18:44Z)
• HINT: Helping Ineffective Rollouts Navigate Towards Effectiveness [49.72591739116668]
  Reinforcement Learning (RL) has become a key driver for enhancing the long chain-of-thought (CoT) reasoning capabilities of Large Language Models (LLMs)<n>However, prevalent methods like GRPO often fail when task difficulty exceeds the model's capacity, leading to reward sparsity and inefficient training.<n>We propose HINT: Helping Ineffective rollouts Navigate Towards effectiveness, an adaptive hinting framework.
  arXiv  Detail & Related papers  (2025-10-10T13:42:03Z)
• Deep Hidden Cognition Facilitates Reliable Chain-of-Thought Reasoning [33.30315111732609]
  Chain of Thought (CoT) reasoning has demonstrated remarkable deep reasoning capabilities.<n>However, its reliability is often undermined by the accumulation of errors in intermediate steps.<n>This paper introduces an approach to calibrate the CoT reasoning accuracy by leveraging the model's intrinsic veracity encoding.
  arXiv  Detail & Related papers  (2025-07-14T07:41:35Z)
• CTRLS: Chain-of-Thought Reasoning via Latent State-Transition [57.51370433303236]
  Chain-of-thought (CoT) reasoning enables large language models to break down complex problems into interpretable intermediate steps.<n>We introduce groundingS, a framework that formulates CoT reasoning as a Markov decision process (MDP) with latent state transitions.<n>We show improvements in reasoning accuracy, diversity, and exploration efficiency across benchmark reasoning tasks.
  arXiv  Detail & Related papers  (2025-07-10T21:32:18Z)
• Interleaved Reasoning for Large Language Models via Reinforcement Learning [22.403928213802036]
  Long chain-of-thought (CoT) enhances large language models' (LLM) reasoning capabilities.<n>We propose a novel training paradigm that uses reinforcement learning (RL) to guide reasoning LLMs to interleave thinking and answering for multi-hop questions.
  arXiv  Detail & Related papers  (2025-05-26T07:58:17Z)
• ToTRL: Unlock LLM Tree-of-Thoughts Reasoning Potential through Puzzles Solving [4.987786842464663]
  Tree-of-thoughts (ToT) offers a conceptually more advanced approach by modeling reasoning as an exploration within a tree structure.<n>ToTRL is designed to guide LLMs in developing the parallel ToT strategy based on the sequential CoT strategy.<n>Our ToTQwen3-8B model, trained with ToTRL, achieves significant improvement in performance and reasoning efficiency on complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-05-19T05:18:58Z)
• The Curse of CoT: On the Limitations of Chain-of-Thought in In-Context Learning [56.574829311863446]
  Chain-of-Thought (CoT) prompting has been widely recognized for its ability to enhance reasoning capabilities in large language models (LLMs)<n>We demonstrate that CoT and its reasoning variants consistently underperform direct answering across varying model scales and benchmark complexities.<n>Our analysis uncovers a fundamental hybrid mechanism of explicit-implicit reasoning driving CoT's performance in pattern-based ICL.
  arXiv  Detail & Related papers  (2025-04-07T13:51:06Z)
• Why Reasoning Matters? A Survey of Advancements in Multimodal Reasoning (v1) [66.51642638034822]
  Reasoning is central to human intelligence, enabling structured problem-solving across diverse tasks.<n>Recent advances in large language models (LLMs) have greatly enhanced their reasoning abilities in arithmetic, commonsense, and symbolic domains.<n>This paper offers a concise yet insightful overview of reasoning techniques in both textual and multimodal LLMs.
  arXiv  Detail & Related papers  (2025-04-04T04:04:56Z)
• Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models [54.04678363287392]
  Large Language Models (LLMs) have demonstrated remarkable capabilities in complex tasks.<n>Recent advancements in OpenAI o1 and DeepSeek-R1 have further improved performance in System-2 reasoning domains.
  arXiv  Detail & Related papers  (2025-03-20T17:59:38Z)
• Marco-o1 v2: Towards Widening The Distillation Bottleneck for Reasoning Models [39.22557129190619]
  Distillation--post-training on LRMs-generated data--is a straightforward yet effective method to enhance the reasoning abilities of smaller models.<n>To alleviate this bottleneck, we propose constructing tree-based CoT data from scratch via Monte Carlo Tree Search.<n>We then exploit a set of CoT-aware approaches, including Thoughts Length Balance, Fine-grained DPO, and Joint Post-training Objective, to enhance SFT and RL on the constructed data.
  arXiv  Detail & Related papers  (2025-03-03T12:17:36Z)
• Causality can systematically address the monsters under the bench(marks) [64.36592889550431]
  Benchmarks are plagued by various biases, artifacts, or leakage.<n>Models may behave unreliably due to poorly explored failure modes.<n> causality offers an ideal framework to systematically address these challenges.
  arXiv  Detail & Related papers  (2025-02-07T17:01:37Z)
• Demystifying Long Chain-of-Thought Reasoning in LLMs [46.352406501403465]
  Long chains-of-thought (CoTs) enable strategies like backtracking and error correction.<n>Reinforcement learning (RL) has emerged as a crucial method for developing these capabilities.<n>We identify the key factors that enable models to generate long CoT trajectories.
  arXiv  Detail & Related papers  (2025-02-05T17:13:32Z)
• RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasoner [2.5903660653548366]
  Self-taught reasoner (STaR) uses reinforcement learning to automatically generate reasoning steps.<n> STaR and its variants have demonstrated empirical success, but a theoretical foundation explaining these improvements is lacking.<n>This work provides a theoretical framework for understanding the effectiveness of reinforcement learning on CoT reasoning and STaR.
  arXiv  Detail & Related papers  (2024-10-31T13:17:53Z)
• GIVE: Structured Reasoning of Large Language Models with Knowledge Graph Inspired Veracity Extrapolation [108.2008975785364]
  Graph Inspired Veracity Extrapolation (GIVE) is a novel reasoning method that merges parametric and non-parametric memories to improve accurate reasoning with minimal external input.<n>GIVE guides the LLM agent to select the most pertinent expert data (observe), engage in query-specific divergent thinking (reflect), and then synthesize this information to produce the final output (speak)
  arXiv  Detail & Related papers  (2024-10-11T03:05:06Z)
• Coding for Intelligence from the Perspective of Category [66.14012258680992]
  Coding targets compressing and reconstructing data, and intelligence. Recent trends demonstrate the potential homogeneity of these two fields. We propose a novel problem of Coding for Intelligence from the category theory view.
  arXiv  Detail & Related papers  (2024-07-01T07:05:44Z)
• Igniting Language Intelligence: The Hitchhiker's Guide From Chain-of-Thought Reasoning to Language Agents [80.5213198675411]
  Large language models (LLMs) have dramatically enhanced the field of language intelligence. LLMs leverage the intriguing chain-of-thought (CoT) reasoning techniques, obliging them to formulate intermediate steps en route to deriving an answer. Recent research endeavors have extended CoT reasoning methodologies to nurture the development of autonomous language agents.
  arXiv  Detail & Related papers  (2023-11-20T14:30:55Z)

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.