One of the more striking capabilities to emerge from recent large reasoning models (LRMs) is what researchers call in-context search: the ability of a model to iteratively generate a solution attempt, critique it, and revise it, all within a single forward pass over an extended context window. Models like DeepSeek-R1 and Kimi-k1.5 exhibit this behaviour after training with reinforcement learning on verifiable rewards (RLVR), and it has become a central feature of high-performance reasoning systems. Yet a basic question has remained unanswered: when does this sequential, reflection-driven process actually outperform simply sampling many independent answers in parallel and taking the best one?
This paper, arXiv:2607.06720, provides the first rigorous theoretical answer to that question. The result is both clarifying and sobering: in-context search is powerful, but only under a specific and non-trivial condition on the quality of the model's self-reflection.
Key Contributions
The paper makes four distinct contributions that together form a coherent theoretical account of in-context search:
- A formal framework modelling in-context search as approximate Bayesian inference over reasoning traces, where the base model defines a prior and self-reflection drives posterior updates.
- A characterisation of when sequential attempts yield exponential gains over parallel sampling, and when they do not, expressed in terms of inference-time sampling complexity.
- A learnability result showing that the required posterior update behaviour can be recovered by standard cross-entropy training on search rollouts with polynomial sample complexity.
- A connection to RLVR showing that the optimal policy extension under a stagewise correctness reward implements the same posterior reweighting rule, providing a mechanistic account of how search-like reasoning emerges from training.
Methodology and Theoretical Framework
The authors represent reasoning traces as root-to-leaf paths in a tree, where each node is a prefix of the reasoning sequence and edges correspond to valid next-step extensions under the base model. This is a notational device rather than an architectural claim; the model itself simply conditions on prefixes. The branching factor W and depth n parameterise the search space.
Reflection is modelled as a noisy signal that, with probability greater than one half, identifies the first incorrect step in a failed trajectory. The key insight is that this locality property matters enormously. When reflections reliably identify early errors, the posterior mass on correct solutions concentrates rapidly. When they do not, conditioning on past failures provides no asymptotic benefit over drawing independent samples.
The central theoretical result (Theorem 4.3) is sharp: if reflections localise errors at early steps, problems whose base-model pass rate decays exponentially with reasoning depth can be solved with high probability using only polynomially many sequential attempts. The complementary negative results (Propositions 4.1 and 4.2) show that late-stage or uninformative reflections yield no improvement, and can even degrade performance by biasing the model away from correct continuations.
The learnability analysis is also notable. The authors show that approximate posterior updates, rather than exact Bayesian updates, suffice to preserve the inference-time gains. This is practically significant because exact posterior computation is intractable in real models. The polynomial sample complexity bound for learning from rollouts connects the theory to practical training pipelines.
Empirical Validation
The empirical component is explicitly framed as qualitative validation rather than a comprehensive benchmark study, which is an honest and appropriate scope for a theory paper. The authors test two predictions on real data.
First, they evaluate whether LRMs can localise the earliest incorrect step in synthetic reasoning traces with injected errors. This directly tests the core assumption underlying the positive theoretical results.
Second, they analyse prefix-conditioned pass rates along chain-of-thought trajectories on AIME 2025 problems, using DeepSeek-R1-Distill-Qwen-2.5-1.5B. The results are consistent with the theoretical picture: successful trajectories generally show increasing pass rates through intermediate gains rather than a single jump, unsuccessful trajectories remain low and non-monotonic, and self-correction events produce a distribution of log pass-rate changes with a long positive tail and some negative values. The authors interpret this as evidence of probability mass redistribution across competing continuations rather than simple monotone accumulation.
This is a reasonable interpretation, though it is worth noting that prefix-conditioned pass rate is an indirect proxy for posterior mass. The connection is principled within the framework but involves assumptions about how well the model's generation probabilities track the theoretical posterior.
Limitations and Open Questions
The authors are candid about the limitations. The theoretical bounds are worst-case in n and W, which are difficult to estimate for real reasoning traces. The RLVR analysis studies a stagewise policy extension consistent with RLVR dynamics rather than a specific algorithm, so the connection to actual training procedures like GRPO or PPO is indirect.
Several open questions follow naturally from this work. The theory assumes a latent correct reasoning trace exists and is reachable under the base model; relaxing this to settings with multiple valid solution paths or no guaranteed correct path would be a meaningful extension. The noisy reflection model assumes conditional independence across attempts, which may not hold when a model's failures are systematically correlated. And the gap between the theoretical reflection model and what real LRMs actually compute during self-critique remains largely uncharacterised.
There is also a practical question the paper does not fully address: how should one design training procedures to specifically encourage the early-error-localisation property that the theory identifies as the key driver of efficiency? The learnability result shows it can be learned, but not how to target it explicitly during training.
For researchers working on inference-time scaling, RLVR training, or the theoretical foundations of chain-of-thought reasoning, this paper provides a principled vocabulary for asking sharper questions about when extended reasoning is worth the compute. The answer, it turns out, depends less on the number of attempts and more on whether the model knows where it went wrong.