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

arXiv: https://arxiv.org/abs/2507.15865 · HTML: https://mlsanity.com/paper/2507.15865/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 22 references that are in the map.
- First posted on arXiv 13 Jul 2025.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 19 of 19)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Chain of Thoughtlessness? An Analysis of CoT in Planning](https://mlsanity.com/paper/2405.04776/) (2024)
- [A Sober Look at Progress in Language Model Reasoning: Pitfalls and Paths to Reproducibility](https://mlsanity.com/paper/2504.07086/) (2025)
- [Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Tasks](https://mlsanity.com/paper/2305.14201/) (2023)
- [Learning Montezuma's Revenge from a Single Demonstration](https://mlsanity.com/paper/1812.03381/) (2018)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Training Large Language Models for Reasoning through Reverse Curriculum Reinforcement Learning](https://mlsanity.com/paper/2402.05808/) (2024)
- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)
- [A Theory of Learning with Autoregressive Chain of Thought](https://mlsanity.com/paper/2503.07932/) (2025)
- [RL for Reasoning by Adaptively Revealing Rationales](https://mlsanity.com/paper/2506.18110/) (2025)
- [ASTRO: Teaching Language Models to Reason by Reflecting and Backtracking In-Context](https://mlsanity.com/paper/2507.00417/) (2025)
- [When Hardness of Approximation Meets Hardness of Learning](https://mlsanity.com/paper/2008.08059/) (2020)
- [Artificial Expert Intelligence through PAC-reasoning](https://mlsanity.com/paper/2412.02441/) (2024)

## Built on by (most cited first, 9 of 9)

- [DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs](https://mlsanity.com/paper/2510.19842/) (2025)
- [Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End](https://mlsanity.com/paper/2604.12013/) (2026)
- [Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently](https://mlsanity.com/paper/2606.22938/) (2026)
- [When Is Compositional Reasoning Learnable from Verifiable Rewards?](https://mlsanity.com/paper/2602.07992/) (2026)
- [When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning](https://mlsanity.com/paper/2607.06720/) (2026)
- [Search, Fail, Recover: A Training Framework for Correction-Aware Reasoning](https://mlsanity.com/paper/2607.07492/) (2026)
- [Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods](https://mlsanity.com/paper/2510.16609/) (2025)
- [STATe-of-Thoughts: Structured Action Templates for Tree-of-Thoughts](https://mlsanity.com/paper/2602.14265/) (2026)
- [Tool Use Reduces Depth-Induced Collapse in OOD Reasoning](https://mlsanity.com/paper/2602.21061/) (2026)

## Abstract (arXiv)

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.