# When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 24 of its 32 references that are in the map.
- First posted on arXiv 7 Jul 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [Demystifying Long Chain-of-Thought Reasoning in LLMs](https://mlsanity.com/paper/2502.03373/) (2025)
- [Code Generation with AlphaCodium: From Prompt Engineering to Flow Engineering](https://mlsanity.com/paper/2401.08500/) (2024)
- [Reasoning with Sampling: Your Base Model is Smarter Than You Think](https://mlsanity.com/paper/2510.14901/) (2025)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [Information Gain-based Policy Optimization: A Simple and Effective Approach for Multi-Turn Search Agents](https://mlsanity.com/paper/2510.14967/) (2025)
- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)
- [Bayesian Teaching Enables Probabilistic Reasoning in Large Language Models](https://mlsanity.com/paper/2503.17523/) (2025)
- [Demystifying Reinforcement Learning in Agentic Reasoning](https://mlsanity.com/paper/2510.11701/) (2025)
- [On Provable Length and Compositional Generalization](https://mlsanity.com/paper/2402.04875/) (2024)
- [Attention as a Compass: Efficient Exploration for Process-Supervised RL in Reasoning Models](https://mlsanity.com/paper/2509.26628/) (2025)
- [Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning](https://mlsanity.com/paper/2505.20561/) (2025)
- [From Reasoning to Super-Intelligence: A Search-Theoretic Perspective](https://mlsanity.com/paper/2507.15865/) (2025)
- [Reasoning Under Uncertainty: Exploring Probabilistic Reasoning Capabilities of LLMs](https://mlsanity.com/paper/2509.10739/) (2025)
- [Verifying Meta-Awareness via Predictive Rewards in Reasoning Models](https://mlsanity.com/paper/2510.03259/) (2025)
- [Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling](https://mlsanity.com/paper/2505.22290/) (2025)

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

- [It's the Problem, Not the Path: Budget and Difficulty Confounds in LLM Reasoning Trajectories](https://mlsanity.com/paper/2609.03436/) (2026)

## Abstract (arXiv)

Training large language models (LLMs) with extended reasoning has enabled in-context search, in which models iteratively generate, critique, and revise solution attempts. We provide a theoretical analysis of in-context search by modeling it as approximate inference over reasoning traces, where the base model defines a prior and self-reflection provides feedback for posterior updates, and study the resulting inference-time sampling complexity - the number of sequential attempts needed to achieve high success probability. We show that when reflections reliably localize early mistakes, in-context search can yield exponential improvements over the base model, solving problems with exponentially small zero-shot pass rates using only a polynomial number of sequential attempts, whereas when this property fails, conditioning on past attempts offers no asymptotic benefit over parallel sampling. We further show that these gains are robust and learnable: approximate posterior updates suffice, and cross-entropy training on search rollouts recovers the required behavior with polynomial sample complexity. Finally, we show that under a stagewise abstraction of reinforcement learning with verifiable rewards, the optimal policy extension implements the same posterior reweighting rule. We validate key qualitative predictions of the theory on real large reasoning models.