1 Introduction↩︎

Chain-of-thought (CoT) reasoning represents an LLM’s intermediate reasoning steps as a sequence connecting the input to the final answer, and was originally used to decompose complex tasks into more manageable subtasks [1]. Subsequent methods such as tree of thought, self-consistency, and reflection extended this paradigm by exploring multiple reasoning paths, evaluating alternatives, and iteratively refining conclusions [2]–[4], leading to the emergence of large reasoning models (LRMs) that solve problems through sequential revisions and multiple solution attempts, a process known as “in-context search” [5]–[9]. This paradigm has enabled high accuracy on reasoning problems under single-sample inference, outperforming earlier LLMs that relied on extensive multi-sample aggregation [10], and has been prominently observed in models trained with reinforcement learning with verifiable rewards (RLVR), such as DeepSeek-R1 [11] and Kimi-k1.5 [12], where search-like reasoning within the context window emerges from training. It has since motivated a growing body of work on reinforcement-based reasoning and search behavior [13]–[16].

Despite these successes, it remains unclear when in-context search provides genuine advantages over parallel sampling from a base model, and when it does not. We study this question through the lens of inference-time sampling complexity: how many sequential attempts (or backtracks) are required to achieve high success probability, compared to parallel sampling from the base model. The recent theoretical work of [17] demonstrated exponential sample efficiency using an explicit tree-search procedure that prunes failed branches by removing them from context. In contrast, modern LRMs typically retain the full history of attempts in-context, raising the question of when this unstructured form can match the same guarantees.

In this work, we address this question by theoretically characterizing the search process underlying in-context search. Building on the search-based perspective of [17], we model reasoning as inference over reasoning traces, focusing on the regime relevant to modern LRMs, where the full history of attempts - including failures - remains in the context. Our framework (Section 3) formalizes in-context search as an inference process with three components: (i) a prior over reasoning traces induced by the base model, (ii) a reflection mechanism that localizes errors in attempted solutions, and (iii) posterior updates that reweight candidate continuations based on the accumulated reflection feedback. See illustration in figure 1.

Using this framework, we identify reflection as the key determinant of inference-time sampling complexity. Under local updates, negative feedback helps only when it identifies prefixes whose continuations should be suppressed. If reflections localize errors only at late stages, in-context search offers no asymptotic improvement over independent sampling and can even degrade performance (Propositions 2 and 3). In contrast, when reflections reliably identify early errors, in-context search can achieve exponential gains: problems whose base-model pass rate decays exponentially with reasoning depth can be solved with arbitrarily high probability using only polynomially many sequential attempts (Theorem 4).

We further show that this posterior-update behavior is robust and learnable. Approximate step-wise updates suffice to preserve the inference-time improvement, and standard cross-entropy training on efficient search rollouts yields polynomial sample complexity. We also analyze a stagewise abstraction of RLVR and show that, under noisy but mostly correct reflection feedback, the optimal extension of the policy - corresponding to generating additional reasoning attempts conditioned on past attempts and reflections - implements the same posterior reweighting, providing a mechanism for the emergence of search-like reasoning in practice.

Finally, in Section 6, we test qualitative predictions of the theory. First, we evaluate the reflection assumption on synthetic reasoning traces with injected errors, measuring whether a model can localize the earliest incorrect step. Second, on AIME 2025, we study real LRMs through prefix-conditioned pass rates, an observable proxy for posterior mass on correct solutions. Successful trajectories generally increase in downstream pass rate, unsuccessful trajectories exhibit low and oscillatory behavior, and self-correction segments produce both negative and large positive changes, consistent with inference-like redistribution rather than monotone accumulation of useful computation.

To recap our contributions:

• We characterize when reflection-driven inference reduces sampling complexity from exponential (parallel sampling) to polynomial (sequential attempts), and when it does not.

• We show that the posterior update rule underlying efficient in-context search is both learnable from rollouts with polynomial sample complexity and arises as the optimal policy in a stagewise extension setting, providing a mechanism for its emergence under RLVR-like training.

2 Related Work↩︎

2.0.0.1 LLMs empowered by CoT:

Prior theoretical work on chain-of-thought has focused on expressivity and learnability, in terms of computational hardness of the problems, without consideration of the self-supervised search process performed by models in practice [18]–[23]. More recent work studies CoT from a search perspective, modeling reasoning as traversal over a tree of possible continuations with an explicit search mechanism [17], [24]. In contrast, we focus on the regime relevant to modern LRMs, where failed attempts are retained in context and search proceeds through implicit updates rather than explicit pruning, and characterize the resulting inference-time efficiency of such processes.

2.0.0.2 Using LLMs as priors:

Several works treat LLMs as probabilistic priors for reasoning, performing explicit Bayesian inference or analyzing their probabilistic reasoning capabilities [25]–[27]. Closely related is [28], which performs Markov chain Monte Carlo sampling over LLM-induced distributions. We adopt a similar perspective, viewing reasoning as inference over a base-model prior, but focus on the inference-time sample complexity of such procedures. In contrast to prior work, we characterize when sequential conditioning yields exponential improvements over parallel sampling.

2.0.0.3 In-context search:

Recent empirical work has studied how to induce and improve search behavior in LLMs, focusing on training procedures, exploration strategies, and test-time methods for multi-step reasoning [13]–[15], [29]–[31]. In contrast, these works do not characterize when such search is provably more efficient than parallel sampling. A central component of our analysis is self-reflection, which we model as noisy feedback that localizes errors and drives inference updates; our theory characterizes when such feedback is sufficient to yield efficient inference-time search. This mechanism can be further enhanced through improved self-awareness [31] or integration with external tools [16].

3 In-Context Search as Sequential Inference↩︎

We study when sequential reasoning - where a model generates multiple attempts conditioned on past failures - can outperform independent sampling from a base language model. We model this as an inference process over reasoning traces: (i) the base model defines a prior over possible solutions, (ii) reflection provides information about errors in sampled trajectories, (iii) conditioning on this feedback induces an implicit posterior update.

The search space is motivated by the work of [17], where reasoning is represented at the level of semantic steps rather than tokens, and treats prefixes of reasoning traces as the states of the process. While their work represents this space as a tree and performs explicit search by pruning failed branches, we focus on the regime relevant to modern LRMs, where failed attempts are retained in context and influence future generation, inducing inference through conditioning.

3.1 Base Model as a Prior Over Reasoning Traces↩︎

We model the base language model as an autoregressive distribution \(P_\theta(\cdot \mid x)\) over reasoning traces. A reasoning trace is a sequence \[y = (y_1, \dots, y_n),\] corresponding to a single solution attempt, where each \(y_i\) denotes a reasoning step, and \[P_\theta(y \mid x) = \prod_{i=1}^n P_\theta(y_i \mid x,y_{<i}).\]

We treat prefixes of reasoning traces as the states of the inference process. For a trace \(y\), let \[h_i = y_{1:i}\] denote the prefix up to step \(i\), with \(h_0\) the empty prefix. Generation corresponds to iteratively extending a prefix \(h_i\) by sampling the next step \(y_{i+1} \sim P_\theta(\cdot \mid x,h_i)\).

For notational convenience, these prefixes can be organized into a rooted tree \(T_x = (V,E)\), where each node \(v \in V\) is a prefix and an edge \((v,v')\) exists if \(v'\) extends \(v\) by one step with nonzero probability under \(P_\theta(\cdot \mid x)\). A complete reasoning trace corresponds to a root-to-leaf path. We assume depth at most \(n\) and branching factor at most \(W\).

To ensure that correct solutions are reachable under the base model - so that inference is non-trivial - we impose a local support condition.

This is a one-step support condition: the model assigns non-negligible probability to a correct next transition. We note this assumption is mild as the dependence on \(\gamma\) will be logarithmic, and can be well below any standard sampling scheme. Under this view, the base model defines a prior over reasoning traces, and independent sampling corresponds to drawing trajectories from \(P_\theta(\cdot \mid x)\), consistent with the importance of the base model for search success [32].

The performance of this baseline is given by the pass rate \(\Pr_{y \sim P_\theta(\cdot \mid x)}[y \in \mathcal{Y}_{\mathrm{correct}}(x)]\), which in the worst case decays exponentially with the depth \(n\). In particular, if at each step the probability of selecting a correct continuation is at most \(p<1\), then the full trajectory is at most \(p^n=O(\exp(-n))\).

3.2 Reflection as a Source of Information↩︎

For an iterative sampling procedure to beat the efficiency of sampling from the prior, an inference process must be performed over failed attempts. But simply ruling out an incorrect reasoning trace does not narrow the search space significantly. In contrast, ruling out a prefix prunes all of its continuations and narrows the search space significantly. In our framework such information is obtained through self-reflection, where the model observes the full context and the latest failed attempt, and estimates the source of the failure. We model the process in rounds \(t=1,2,...\) of sequential attempts, with \(\mathcal{C}_t\) denoting the in-context history.

Informally, this assumption requires that once the model encounters the same failure mode multiple times, it can identify the earliest incorrect step with non-negligible probability. The reflection performs a diagnostic task - identifying where a reasoning trace becomes incorrect - rather than constructing a correct solution from an exponentially large set of candidates. The probability of identifying the earliest incorrect step \(p_r\) need not be large, and we require only that this signal becomes reliable after repeated exposure to the same failure mode, captured by the threshold \(m_r\).

In our framework, the model’s new attempts can restart from previously visited states, as in practice. Accordingly, reflection can be applied to the full reasoning trace, including both reused prefixes and newly generated steps. This is important: if reflection were restricted to only the newly generated suffix, the model could repeatedly restart from an already invalid prefix and enter a reasoning loop. Appendix 18 provides empirical evidence for the necessity of this assumption.

3.3 Posterior Updates via Conditioning↩︎

Reflection provides information about which reasoning steps are unlikely to lead to correct solutions. For this information to be useful, it must influence future reasoning attempts. In our framework, this is modeled as a progressive in-context downweighting of transitions identified as incorrect.

Each reflection reduces a transition’s relative likelihood by a factor \(e^{-\eta}\), so repeated feedback leads to exponential suppression of incorrect prefixes. In practice, this update is implemented implicitly via conditioning on the in-context history \(\mathcal{C}_t\). In Section 5, we show that approximate updates suffice.

3.3.0.1 Sequential inference.

We model in-context search as a sequential procedure over rounds \(t = 1, 2, \dots\). At each round, a trace \(\omega_t\) is sampled from the context-conditioned distribution given the context \(\mathcal{C}_{t-1}\). If incorrect, the reflection signal identifies a transition \((h_{t},a_{t})=(y_{<r_t},y_{r_t})\) indexed by \(r_t\); both the trace and the identified transition are appended to the context. The process terminates if a correct trajectory is sampled.

This induces a posterior-like update: transitions identified as incorrect are progressively downweighted, concentrating probability on viable reasoning paths.

3.3.0.2 Reachability.

At each round, the model selects a prefix from which to continue generation, either starting from the empty prefix or resuming from a prefix present in the context. In all cases, generation is conditioned on the full context.

The contextual reachability assumption rules out pathological behaviors in which the model repeatedly resumes from prefixes already identified as incorrect. Without this restriction, the model could cycle indefinitely. Appendix 18 provides empirical evidence for the necessity of this assumption.

4 When Does In-Context Search Help?↩︎

4.1 Failure Modes↩︎

We begin by characterizing regimes in which in-context search does not provide an advantage over independent sampling. These results highlight the necessity of informative reflection and clarify the role of early error localization.

4.1.0.1 Late Error Localization

A central requirement for efficient in-context search is the ability to identify errors early in a reasoning trajectory. Intuitively, the benefit of reflection arises from eliminating large portions of the search space. If reflection only identifies mistakes at late stages, then only a small portion of it is narrowed down. This intuition is formalized in the following result.

Late reflection fails to eliminate incorrect prefixes at early stages and therefore the space of possible continuations remains large. The formal proof is given in Appendix 14.

4.1.0.2 Misleading Positive Feedback

One might also consider reinforcing steps believed to be correct via positive feedback. However, such feedback is inherently unreliable, as correctness cannot be verified without solving the underlying task. This leads to the following negative result.

Positive feedback amplifies selected prefixes rather than eliminating regions of the search space; when noisy, it increases the likelihood of extending incorrect reasoning paths and reduces the probability of sampling a correct solution. This highlights a fundamental asymmetry: eliminating incorrect reasoning is substantially more robust than reinforcing correct reasoning. Proof in Appendix 15.

4.2 Success Conditions↩︎

We characterize when in-context search outperforms independent sampling. When reflection reliably identifies the earliest incorrect step, sequential conditioning transforms an exponentially hard sampling problem into a polynomial one. The key mechanism is that identifying an incorrect prefix eliminates all of its continuations, pruning large regions of the search space rather than ruling out individual trajectories. For simplicity, we state the single-solution case; general case in Appendix 11.

The theorem shows that when early error localization is available, the number of required attempts scales polynomially in \(n\) and \(W\), in contrast to the exponential scaling of independent sampling. This establishes that sequential conditioning can yield an exponential improvement in sampling efficiency.

4.2.0.1 Extensions and robustness.

The result extends to more general settings, with corresponding degradations in sample complexity:

• Multiple correct paths. With \(k\) correct solutions, \(T = \tilde{O}(k)\) (Appendix 11).

• Bounded delayed reflection. If errors are identified within depth \(\Delta_r\) of the earliest mistake, \(T = \tilde{O}(\exp(\Delta_r))\) (Appendix 17) - capturing a transition to inefficiency with late feedback.

• False positives. If each correct transition is incorrectly flagged at most \(d\) times, \(T = \tilde{O}(d)\) (Appendix 16). Thus \(O(poly(n))\) false positives retains polynomial efficiency.

4.2.0.2 Corollary (Exponential vs.polynomial gap).

In reasoning problems, the base model’s pass rate can decay exponentially with depth - if each step is correct with probability at most \(p<1\), then the probability of a correct trajectory is at most \(p^n = O(\exp(-n))\). Under Theorem 4, however, in-context search succeeds with high probability after only \(O(n)\) sequential attempts (up to logarithmic factors), yielding an exponential separation between parallel sampling and sequential inference.

5 Learning and Emergence↩︎

Here we study the learning perspective on in-context search. We first show that the inference-time guarantee of Theorem 4 is stable under standard token-level training: if a model accurately imitates the transcript distribution of an efficient search policy, it inherits its pass-rate guarantee with only polynomial dependence on the rollout length. We then give a complementary stagewise analysis, serving as a stylized proxy for RLVR, showing that under noisy reflection feedback, the posterior update rule of Definition 2 arises as the optimal policy extension.

5.1 Robustness to Approximate Posterior Updates↩︎

The efficiency guarantees of Theorem 4 rely on a specific posterior update rule. We show that the exact implementation is unnecessary: a step-wise approximation, learnable from supervised log loss on next-step prediction suffices to recover the guarantee.

The required step-level loss scales as \(O(1/T_{\epsilon/2})\). In particular, for fixed reflection parameters, Theorem 4 gives \(T_{\epsilon/2}=\widetilde{O}(n W )\), so standard generalization bounds imply polynomial sample complexity, \(\widetilde{O}(n^2W^2/(\delta^2\epsilon^4))\), up to logarithmic factors. Thus, standard autoregressive training on search rollouts suffices to recover the efficiency of in-context search.

5.2 Connection to Reinforcement Learning with Verifiable Rewards↩︎

We provide a principled justification for the posterior reweighting rule in Section 3 via an idealized stagewise policy extension setting. This is not a model of the full RLVR training dynamics; rather, it abstracts one empirical feature of RLVR-trained reasoning models: CoT length tends to increase over training [11]. We interpret this as incremental policy extension, where later training stages learn to append additional reasoning attempts conditioned on earlier attempts and feedback. We ask what update rule is optimal if each extension is chosen to maximize correctness likelihood.

5.2.0.1 Stagewise policy extension.

Starting from a base policy that generates a single trajectory, we iteratively extend it by adding additional sampling stages. At stage \(t\), the policy generates a trajectory conditioned on previous attempts and reflections. Given a fixed \(t\)-stage policy, we characterize the optimal \((t+1)\)-stage extension for maximizing correctness likelihood.

5.2.0.2 Noisy reflection model.

We assume a latent correct reasoning trace \(y^\star\) and a sequence of noisy reflections on sampled trajectories. Each reflection identifies a reasoning step along a trajectory and indicates whether it is the first incorrect step (with probability \(p_r> \tfrac12\)) or the last correct step (with probability \(1-p_r\)). Reflections are conditionally independent given \(y^\star\), and affect only the likelihood of candidate next steps. These signals provide local evidence about trajectory correctness and induce a posterior \(P_t(y) = \Pr(y^\star = y \mid \mathcal{C}_t)\). Formal definitions given in Appendix 12.

Theorem 7 shows that the exponential reweighting rule of Section 3 arises as the optimal strategy for extending a multi-stage reasoning policy under noisy feedback. This provides a lens on RLVR: while we do not model the full training dynamics, the result suggests that policies optimized stage-wise under noisy feedback may favor update rules that approximate this form of posterior reweighting.

6 Empirical Evidence↩︎

We provide empirical evidence supporting the qualitative predictions of our theory. Our goal is not a comprehensive empirical evaluation, but to test whether the key mechanisms identified by the theory are reflected in practice. We test two key components: (i) reflection as an error localization mechanism, and (ii) observable consequences of in-context search in large reasoning models. In appendix 17.1 we test our results on synthetic traces with a controlled implementation of the theoretical update and reflection assumptions.

6.1 Reflection as an Error Localization Mechanism↩︎

Our theory assumes that reflection can identify incorrect reasoning steps, particularly localizing early mistakes with non-negligible probability. We evaluate this on structured reasoning traces (arithmetic chains and equation solving) with a single injected error, asking the model to identify the earliest incorrect step. Qwen-3-4B-Instruct was used.

We measure the reflection delay - the gap between the earliest incorrect step and the step identified by the model. Figure 2 shows non-trivial mass at zero delay, together with a sparse tail of delayed reflections. This supports the early localization assumption, while the tail aligns with the robustness analysis.

6.2 Evidence in Large Reasoning Models↩︎

Theorem 4 suggests that, as reasoning unfolds, probability mass should concentrate on correct solutions. To probe this, we estimate prefix-conditioned pass rates - using them as a proxy for posterior mass - along CoT prefixes. We present results for DeepSeek-R1-Distill-Qwen-2.5-1.5B; complementary results for DeepSeek-R1-Distill-Qwen-2.5-7B are provided in Appendix 20.

Figure 3 (a) shows this quantity for successful trajectories. Pass rates typically increase toward 1 through intermediate gains rather than a single jump, though the evolution is heterogeneous and not strictly monotone. This indicates progressive accumulation of probability mass on correct solutions. Figure 3 (b) shows unsuccessful trajectories. Here, pass rates remain low and highly non-monotonic, suggesting that the dynamics are not simply accumulating progress, but involve redistribution across competing continuations. In appendix 19, we perform this experiment in a setting more similar to our framework - explicit rounds of trace generation and reflections, yielding qualitatively similar results.

To isolate the effect of self-correction, we segment successful trajectories at correction points and measure log changes in pass rate between segments. Figure 3 (c) shows that most updates are small, with both negative values and a long positive tail: some corrections reduce success probability, while a few induce large gains. This supports a view of self-correction as not simply accumulating progress, but as sparse yet sometimes substantial reallocation of probability mass.

7 Discussion↩︎

In this work, we studied in-context search in LRMs as feedback-driven inference over a base model prior. We show that its effectiveness is governed by the quality of reflection: when reflections reliably localize early mistakes, sequential updates can transform an exponentially small pass rate into high success probability using only polynomially many attempts; when reflections are uninformative, conditioning provides no asymptotic improvement over parallel sampling and may even degrade performance. We further show that the required update behavior is robust and learnable from supervised rollouts, and that sequential extension under a final correctness reward - mirroring RLVR - the optimal policy extension implements the same update rule, helping explain the emergence of search-like reasoning in practice. We further discuss the limitations of this framework in Appendix 9.

8 Acknowledgements↩︎

This research was supported by the ERC (European Research Council) and the ISF (Israel Science Foundation).

9 Limitations↩︎

9.0.0.1 Assumptions:

Our analysis relies on several assumptions that may not hold fully in practice.

• First, we assume \(\gamma\)-local support (assumption 1), ensuring that correct continuations have nonzero probability under the base model. While mild, due to the logarithmic dependence of the results, this condition may fail for difficult problems or poorly calibrated models, in which case no amount of inference can recover correct solutions. Even so, this assumption’s limitations has empirical evidence in works such as [32], where the RLVR sharpens reasoning traces already existent in the base model, indicating the importance of the base model having sufficient support for correct traces.

• Second, the adaptive reflection signal (definition 1) requires that the model can identify early incorrect steps with non-negligible probability after repeated exposure. In practice, reflection may be more delayed or reinforcing a promising direction instead of pointing to an incorrect one. In this work we show these two can harm search, but in practice the model can compensate for this with a smarter update of its distribution over traces.

• Third, a central component of our analysis is the local in-context reweighting update (definition 2), which multiplicatively downweights invalid prefixes. The purpose of this is so that the model is responsive to the reflection signal. This rule is idealized and may not be implemented exactly by learned models. We show that approximate step-wise updates suffice to preserve the efficiency guarantees. Additionally, the locality can be relaxed further - for the main results of theorem 4, there need not be restrictions on the redistribution of probability mass on steps that succeed the first incorrect step. Even so, the extent to which real models approximate this behavior depends on training dynamics and model capacity.

• Fourth, we assume contextual reachability (assumption 2), ruling out repeated resumption from previously invalidated prefixes. As shown in Appendix 18, current large reasoning models can exhibit reasoning loops in which invalid prefixes are revisited, leading to inefficient search. The results show that this is a major failure mode, responsible for many of the unsuccessful CoTs. Our theoretical results for search efficiency therefore characterize an idealized regime in which such behavior is avoided, as when search fails it is often for this reason.

• Reflection parameters: We treat the reflection parameters \(p_r\) and \(m_r\) as fixed quantities. This dependence may be substantially more favorable than solving the full problem - identifying an incorrect transition in a chain of length \(n\) is a much simpler task than searching over an exponentially large space of solutions - but characterizing it empirically and theoretically remains an important direction for future work. We note that if \(p_r\) and \(m_r\) scale polynomially with \(n\), then the efficiency of in-context search is maintained. If they do not, this is an outcome consistent with the failure mode of proposition 2, of not identifying the earliest incorrect error quickly enough, which leads to no asymptotic improvement over parallel sampling from the base model.

9.0.0.2 Theoretical results:

Our theoretical results focus on worst-case bounds in terms of reasoning length \(n\) and branching factor \(W\). These quantities may be difficult to estimate in practice, and actual performance may depend on additional factors. Furthermore, the results related to RLVR as a stage-wise policy extension (Theorem 5.2), does not explicitly study an RLVR algorithm, but an effective process consistent with the training dynamics of RLVR, where a model gradually increases the length of the search process under a correctness maximization reward [11].

9.0.0.3 Empirical results:

Our empirical evaluation primarily provides qualitative validation of the theoretical predictions rather than a comprehensive empirical study.

Overall, our results should be interpreted as identifying conditions under which in-context search is efficient, rather than guaranteeing such behavior in all practical settings.

10 Tree Representation for Analysis↩︎

10.0.0.1 Tree representation for analysis.

For the purpose of analysis, we represent the prefix structure of reasoning traces as a rooted tree. Each node corresponds to a prefix \(h = y_{1:i}\), and edges correspond to valid next-step extensions under the base model. A complete trajectory corresponds to a root-to-leaf path.

This representation is purely a notational device: the model itself operates by conditioning on prefixes, as described in Section 3. We use this representation throughout the proofs to reason about how local updates affect sets of continuations.

Each reflection event identifies a transition, which in the tree representation can equivalently be represented by the child node reached by that transition: if the reflection signal returns a transition corresponding to index \(r_t\) in a trajectory \((y_1,\dots,y_n)\), this corresponds to identifying the node \(v = y_{1:r_t}\), or equivalently the transition from its parent to \(v\), as incorrect.

For clarity, we make the correspondence explicit: \[\begin{align} \text{prefix } h &\leftrightarrow \text{node } v, \\ \text{next reasoning step } a &\leftrightarrow \text{child of } v, \\\text{transition } (h,a) &\leftrightarrow \text{edge } (v,v'), \\ \text{reasoning trace } (y_1,\dots,y_n) &\leftrightarrow \text{root-to-leaf path}, \\ \text{earliest incorrect prefix } y_{1:k} &\leftrightarrow \text{earliest incorrect node } v_k, \\ \text{reflection outputs transition indexed by } r_t &\leftrightarrow \text{identified node location on the path}, v_{r_t}\\ Z_t = \mathbf{1}\{r_t = k\} &\leftrightarrow Z_t = \mathbf{1}\{v_{r_t} = v_k\}. \end{align}\]

11 Proof of Theorem 4↩︎

11.0.0.1 Multiple correct solutions.

In the main theorem we presented for a single correct reasoning trace, \(k=1\), here we present for the general case:

As can be seen, the scaling with correct reasoning traces is: \(T=\tilde{O}(k)\).

proof:

We analyze the process using the tree representation of prefixes introduced in Section 10. In this representation, prefixes correspond to nodes, and possible next steps correspond to edges. We will refer to prefixes and their extensions interchangeably as nodes and their children.

For clarity, we make the correspondence explicit: \[\begin{align} \text{prefix } h &\leftrightarrow \text{node } v, \\ \text{next reasoning step } a &\leftrightarrow \text{child of } v, \\\text{transition } (h,a) &\leftrightarrow \text{edge } (v,v'), \\ \text{reasoning trace } (y_1,\dots,y_n) &\leftrightarrow \text{root-to-leaf path}, \\ \text{earliest incorrect prefix } y_{1:k} &\leftrightarrow \text{earliest incorrect node } v_k, \\ \text{reflection outputs transition indexed by } r_t &\leftrightarrow \text{identified node location on the path}, v_{r_t}\\ Z_t = \mathbf{1}\{r_t = k\} &\leftrightarrow Z_t = \mathbf{1}\{v_{r_t} = v_k\}. \end{align}\]

Under this correspondence, downweighting a prefix suppresses all continuations passing through the associated node, allowing us to reason about the effect of updates via elimination of subtrees. We begin the proof with the following lemma:

We next show that a node with a sufficiently low likelihood will not be sampled in a given number of turns with high probability:

We now apply to show that after a given number of rounds with first incorrect nodes returned by the reflection, all first incorrect nodes become suppressed and thus only correct solutions are sampled with high probability.

We now complete the proof of the theorem by accounting for all the rounds where the reflection did not return the first incorrect node.

Proof of technical lemma:

12 Full assumptions for noisy reflection model and proof of Theorem 7↩︎

We formalize the assumptions used in Theorem 7.

1. (Latent correct trajectory and prior) There is a set of candidate trajectories \(\mathcal{Y}\). A latent variable \(y^\star\in\mathcal{Y}\) denotes the correct trajectory. The initial policy \(\pi_0\) induces a prior distribution over trajectories, \[P_0(y)=\Pr(y^\star=y).\] Under the autoregressive factorization, \[P_0(y)=\prod_i P_0(y_i\mid y_{<i}),\] where \(P_0(\cdot\mid h)\) is parameterized by base logits \(\ell_0(\cdot\mid h)\).

2. (Sequential sampling and reflection history) At stage \(s=1,\dots,t\), the current policy samples a trajectory \[y^{(s)}\sim \pi^{(s)}(\cdot\mid \mathcal{C}_{s-1}).\] If the sampled trajectory is incorrect, the reflection oracle marks a transition \[(h_s,a_s)=\bigl(y^{(s)}_{<r_s},y^{(s)}_{r_s}\bigr).\] The reflection history is \[\mathcal{C}_s=\{(h_j,a_j)\}_{j=1}^s.\]

3. (Noisy reflection) The marked transition is truly invalid with probability \(p_r>\tfrac12\). Equivalently, if \(A_s\) is the event that \(a_s\) is the correct next step after \(h_s\), then \[\Pr(r_s\mid A_s)=1-p_r, \qquad \Pr(r_s\mid A_s^c)=p_r.\] That is, the reflection is more likely to mark \(a_s\) when \(a_s\) is invalid than when \(a_s\) is valid.

4. (Prefix locality) A reflection on transition \((h_s,a_s)\) affects only the posterior next-step distribution after prefix \(h_s\). For every prefix \(h\neq h_s\), \[P_s(\cdot\mid h)=P_{s-1}(\cdot\mid h).\]

5. (No distinction among unmarked alternatives) At the marked prefix \(h_s\), the reflection gives no information distinguishing between alternatives \(a\neq a_s\). Thus, for any \(a,a'\neq a_s\), \[\frac{P_s(a\mid h_s)}{P_s(a'\mid h_s)} = \frac{P_{s-1}(a\mid h_s)}{P_{s-1}(a'\mid h_s)}.\]

6. (Conditional independence) Reflection errors are conditionally independent across stages given the latent correct trajectory and sampled trajectories.

7. (Posterior) The history \(\mathcal{C}_s\) induces posterior next-step distributions \[P_s(a\mid h) = \Pr(y^\star \text{ takes next step } a \text{ after prefix } h \mid \mathcal{C}_s).\] These local posteriors induce an autoregressive posterior over trajectories, \[P_s(y\mid \mathcal{C}_s) = \prod_i P_s(y_i\mid y_{<i},\mathcal{C}_s).\]

13 Proof of Proposition 6↩︎

Fix \[T := T(\epsilon/2,n,W),\] and let \(P^*_{(T)}(\cdot\mid x)\) and \(P_{h,(T)}(\cdot\mid x)\) denote the distributions over full search transcripts up to round \(T\) induced by \(P^*\) and \(P_h\), respectively.

By the chain rule for KL divergence, \[\begin{align} \mathbb{E}_{x\sim D}\!\left[ D_{\mathrm{KL}}\!\left(P^*_{(T)}(\cdot\mid x)\,\|\,P_{h,(T)}(\cdot\mid x)\right) \right] &= \mathbb{E}_{x\sim D,\; y\sim P^*_{(T)}(\cdot\mid x)} \left[ \sum_{i=1}^{|y|} \log \frac{P^*(y_i\mid x,y_{<i})}{P_h(y_i\mid x,y_{<i})} \right] \\ &\le \mathbb{E}_{x\sim D,\; y\sim P^*_{(T)}(\cdot\mid x)} \left[ \sum_{i=1}^{|y|} \log \frac{1}{P_h(y_i\mid x,y_{<i})} \right]. \end{align}\] The inequality holds because the entropy term of \(P^*\) is nonnegative.

Since every transcript has length at most \(T\), \[\begin{align} \mathbb{E}_{x\sim D}\!\left[ D_{\mathrm{KL}}\!\left(P^*_{(T)}(\cdot\mid x)\,\|\,P_{h,(T)}(\cdot\mid x)\right) \right] &\le T\cdot \mathbb{E}_{x\sim D,\; y\sim P^*_{(T)}(\cdot\mid x)} \left[ \frac{1}{|y|}\sum_{i=1}^{|y|} \log\frac{1}{P_h(y_i\mid x,y_{<i})} \right] \\ &\le \frac{\delta\epsilon^2}{4}. \end{align}\]

Now apply Markov’s inequality to the nonnegative random variable \[D_{\mathrm{KL}}\!\left(P^*_{(T)}(\cdot\mid x)\,\|\,P_{h,(T)}(\cdot\mid x)\right),\] where \(x\sim D\). We obtain \[\Pr_{x\sim D}\!\left[ D_{\mathrm{KL}}\!\left(P^*_{(T)}(\cdot\mid x)\,\|\,P_{h,(T)}(\cdot\mid x)\right) > \frac{\epsilon^2}{4} \right] \le \delta.\] Therefore, with probability at least \(1-\delta\) over \(x\sim D\), \[D_{\mathrm{KL}}\!\left(P^*_{(T)}(\cdot\mid x)\,\|\,P_{h,(T)}(\cdot\mid x)\right) \le \frac{\epsilon^2}{4}.\]

By Pinsker’s inequality, on this event, \[TV\!\left(P^*_{(T)}(\cdot\mid x),P_{h,(T)}(\cdot\mid x)\right) \le \sqrt{\frac{1}{2}D_{\mathrm{KL}}\!\left(P^*_{(T)}(\cdot\mid x)\,\|\,P_{h,(T)}(\cdot\mid x)\right)} \le \frac{\epsilon}{2\sqrt{2}} \le \frac{\epsilon}{2}.\]

Let \(A_x\) denote the event that a correct solution is generated by round \(T\) on problem \(x\). By Theorem 4 with failure parameter \(\epsilon/2\), \[P^*_{(T)}(A_x\mid x)\ge 1-\frac{\epsilon}{2}.\] Moreover, for any event \(A\) and distributions \(P,Q\), \[Q(A)\ge P(A)-TV(P,Q).\] Applying this with \(A=A_x\), \(P=P^*_{(T)}(\cdot\mid x)\), and \(Q=P_{h,(T)}(\cdot\mid x)\) yields \[P_{h,(T)}(A_x\mid x) \ge P^*_{(T)}(A_x\mid x) - TV\!\left(P^*_{(T)}(\cdot\mid x),P_{h,(T)}(\cdot\mid x)\right) \ge 1-\frac{\epsilon}{2}-\frac{\epsilon}{2} = 1-\epsilon.\]

Hence, with probability at least \(1-\delta\) over \(x\sim D\), the pass rate of \(P_h\) by round \(T(\epsilon/2,n,W)\) is at least \(1-\epsilon\). 0◻

14 Proof of Proposition 2↩︎

15 Proof of Proposition 3↩︎

16 False Positives in Reflection↩︎

We extend the reflection model to allow bounded false positives, where correct prefixes may be incorrectly identified for a bounded number of times.

Under this modified reflection signal, in-context search remains efficient, with a degradation that scales with the false-positive budget:

As can be seen, a dependence of \(\tilde{O}(d)\) is added, coupled to the depth \(n\), width \(W\), and number of correct solutions \(k\). Letting \(d\) scale polynomially with \(n\) retains the polynomial efficiency.

proof:

We analyze the process using the tree representation of prefixes introduced in Section 10, as was done in the proof of the main theorem (Appendix 11). In this representation, prefixes correspond to nodes, and possible next steps correspond to edges. We will refer to prefixes and their extensions interchangeably as nodes and their children.

The key ingredient is a robust version of the suppression argument that accounts for possible penalties on correct nodes:

With this modification in place, the remainder of the proof follows the proof of Theorem 4, with adjusted constants.

17 Delayed Reflections↩︎

We now weaken the reflection model by allowing the reflection to identify errors only up to a bounded delay, while ensuring that reflection signals eventually propagate upward.

For the analysis of this extension, we work with the tree representation of prefixes introduced in Appendix 10, as was done in the proof of the main theorem (Appendix 11). This representation makes it possible to reason about how reflection feedback propagates across multiple levels of continuation. In this view, nodes correspond to prefixes, edges to transitions and subtrees correspond to sets of continuations.

To control the behavior of delayed reflections within incorrect subtrees, we assume that all local transitions have non-negligible prior probability:

Under these assumptions, in-context search remains efficient, with a degradation that depends on the delay parameter:

Notably, the dependence on the delay parameter \(\Delta_r\) is exponential through the factor \(B_{\Delta_r}\), reflecting the need to eliminate an entire subtree of depth \(\Delta_r\) before error signals propagate upward. This yields a smooth transition from the efficient regime of early error localization to the exponentially inefficient regime where reflections occur only at late stages.

proof:

We analyze the process using the tree representation of prefixes introduced in Section 10. In this representation, prefixes correspond to nodes, and possible next steps correspond to edges. We will refer to prefixes and their extensions interchangeably as nodes and their children.

We begin by showing that incorrect nodes within the delayed reflection region can be eliminated from the reflection signal after a sufficient number of reflections.

We next use a recursive argument to exhaust the nodes that can be returned by the reflection to the earliest incorrect steps:

Now we can use the above lemma to reduce to the original reflection definition 1:

We now complete the proof of Theorem 10. Fix a deterministic horizon \(\overline{T}\), and define \[B_{\Delta_r}:=\sum_{j=0}^{\Delta_r}W^j.\] Let \[M := knW B_{\Delta_r}\] be an upper bound on the number of delayed-region edges attached to possible first incorrect edges, and define \[L := \frac{1}{\eta} \log\frac{\overline{T}\,knW B_{\Delta_r}}{\epsilon\gamma} .\]

On the no-return event for suppressed delayed-region edges, which holds with probability at least \(1-\epsilon\), Lemma 8 shows that each possible earliest incorrect edge requires at most \[2B_{\Delta_r}L\] useful delayed reflections before useful reflections through that edge return the earliest incorrect node itself. Once useful reflections return the earliest incorrect node, the original node-suppression argument applies: after at most an additional \(L\) returns of that earliest incorrect node, the corresponding first incorrect edge is suppressed. Since \(B_{\Delta_r}\ge 1\), each possible first incorrect edge therefore absorbs at most \[3B_{\Delta_r}L\] useful delayed reflections before being suppressed.

There are at most \(knW\) possible first incorrect edges. Hence, on the no-return event, after at most \[N := 3knW B_{\Delta_r}L\] useful delayed reflections, all possible first incorrect edges are suppressed. Consequently, any future incorrect trajectory within the horizon would have to traverse a suppressed first incorrect edge, which does not occur on the no-return event. Therefore, after \(N\) useful delayed reflections, either a correct solution has already been sampled or no further incorrect trajectory is sampled during the first \(\overline{T}\) rounds.

It remains to show that \(N\) useful delayed reflections occur quickly. For an incorrect round \(t\), let \(v_k\) be the earliest incorrect node of the sampled trajectory, and define \[Z_t := \mathbf{1} \left\{ r_t\in \{v_k,\dots,v_{\min(k+\Delta_r,n)}\} \right\}.\] By the bounded useful-delay reflection assumption, on every eligible incorrect round, \[\mathbb{E}[Z_t\mid \mathcal{C}_{t-1}]\ge p_r.\]

As before, there are at most \(knWm_r\) ineligible incorrect rounds: each possible earliest incorrect node can appear fewer than \(m_r\) times before it becomes eligible, and there are at most \(knW\) possible earliest incorrect nodes.

Applying the same Azuma–Hoeffding argument as in the proof of Theorem 4, with this new definition of \(Z_t\), we obtain that after \[R \ge \frac{2}{p_r} \left( N+\frac{4}{p_r}\log\frac{1}{\delta} \right)\] eligible incorrect rounds, at least \(N\) useful delayed reflections have occurred with probability at least \(1-\delta\).

Therefore it suffices to take \[T \ge knWm_r + \frac{2}{p_r} \left( N+\frac{4}{p_r}\log\frac{1}{\delta} \right).\] Substituting \[N = 3knW B_{\Delta_r} \frac{1}{\eta} \log\frac{\overline{T}\,knW B_{\Delta_r}}{\epsilon\gamma}\] gives \[T = \widetilde{O}\!\left( knWm_r + \frac{knW B_{\Delta_r}}{p_r\eta} \log\frac{\overline{T}\,knW B_{\Delta_r}}{\epsilon\gamma} + \frac{1}{p_r^2}\log\frac{1}{\delta} \right).\]

Combining the concentration event with the no-return event and taking \(\epsilon=\delta/2\) gives success probability at least \(1-\delta\). Finally, the same self-consistency argument used in the proof of Theorem 4 removes the dependence on \(\overline{T}\), since \(\overline{T}\) appears only logarithmically. Thus, with probability at least \(1-\delta\), a correct solution is sampled after at most \[T = \widetilde{O}\!\left( knWm_r + \frac{knW B_{\Delta_r}}{p_r\eta}\log\frac{1}{\gamma} + \frac{1}{p_r^2}\log\frac{1}{\delta} \right)\] rounds.

0◻

17.1 Synthetic problems↩︎

We validate the qualitative predictions of our theory in a fully controlled synthetic setting, where the search space, reflection signal, and posterior updates are explicitly implemented. We generate random search trees of fixed width \(W\) and varying depth \(n\), with edge weights inducing a prior distribution over paths; a single correct solution is chosen by sampling a path from this prior. We implement the posterior update rule of Definition 2 directly and control the reflection signal to test different feedback regimes.

17.1.0.1 Efficiency of posterior updates:

The corollary from Theorem4 predicts that independent sampling from the prior requires exponentially many samples to find the correct path as depth increases, whereas sequential sampling with posterior updates requires only polynomially many attempts. Figure 4 (a) confirms this separation: parallel sampling exhibits linear growth in the log domain (exponential complexity), while sequential sampling with posterior updates grows sublinearly.

17.1.0.2 Failure with late reflections:

Proposition 2 predicts that this advantage disappears if reflection fails to identify early mistakes. Figure 2(b) shows that when reflections are delayed to depths \(\geq n/2\), in-context search again exhibits exponential complexity, isolating early error localization as the key mechanism enabling efficiency.

18 Reasoning Loops as a Failure Mode↩︎

Assumption 2 prevents the model from repeatedly restarting from prefixes that have already been identified as incorrect.

While this assumption is not strictly necessary for the success of in-context search, removing it permits pathological behaviors in which the model cycles between previously invalidated prefixes without making progress. We refer to such behaviors as reasoning loops. These loops do not necessarily prevent success in all cases, but they can significantly degrade efficiency by repeatedly revisiting the same incorrect regions of the search space. Hence we do not expect them to be part of the efficient search regime.

To assess how often this occurs in practice, we analyze failed reasoning trajectories on the AIME 2025 benchmark. For each model, we sample chains-of-thought (CoTs) that do not reach a correct solution and measure the fraction that exhibit a reasoning loop, defined as repeated resumption from a previously invalidated prefix.

We observe that a substantial fraction of failed trajectories exhibit looping behavior, both with greedy decoding and nucleus sampling.

This supports the relevance of the reachability assumption as a mechanism for ruling out inefficient dynamics. We also observe that larger models exhibit fewer loops, suggesting improved implicit avoidance of previously invalidated prefixes.

Thus, Assumption 2 should be viewed not as a claim that real models never loop, but as an idealized condition isolating the regime where search is efficient.

19 Sequential Reflection Rounds↩︎

We complement the prefix-conditioned pass-rate analysis with an explicit sequential reflection setting. In each round, the model is prompted to produce a final answer, after which generation is resumed with a self-reflection trigger. Pass rate is then estimated after each revised solution attempt.

To induce self-reflection, we append the beginning-of-CoT token followed by the explicit reflection phrase “<think>Wait”. To terminate the reflection segment and elicit a new answer, we append “Summing up, final answer</think>”. Pass rates are estimated from 20 sampled completions conditioned on the resulting prefix. Each answer-generation phase is allocated a 1k-token budget, while reflection phases use either a 100-token or 1k-token budget. This setup is not intended to isolate a pure reflection oracle, since the reflection segment may also perform additional reasoning; rather, it probes whether an explicit self-reflection trigger can substantially change the distribution over final answers.

Figure 5 shows that sequential reflection can sometimes induce large pass-rate increases, from below \(0.05\) (no successes among 20 evaluation samples) to near \(1.0\) within a few rounds. At the same time, reflections can also reduce pass rate or leave it unchanged, indicating that the process is not monotonic improvement but redistribution of probability mass across competing continuations. Similar to the prefix-conditioned trajectory analysis in the main text, the resulting dynamics are sparse and highly heterogeneous.

20 Evidence in Large Reasoning Models - Results in Complementary Model↩︎

In 6.2, we provided results for prefix-conditioned pass rates on DeepSeek-R1-Distill-Qwen-2.5-1.5B. We now provide complementary results for DeepSeek-R1-Distill-Qwen-2.5-7B. Figure 6 shows qualitatively similar results to the \(1.5B\) variant, with a larger tail of reflections leading to an increase in pass rate.

21 Experimental details↩︎

21.0.0.1 Reflection on arithmetic traces:

We start with a random number, then sample chains via a random choice between the actions \(+,-,*,/\), with another random number. A single incorrect calculation is made along the chain, after which correct calculations propagate the error. The model is instructed to find the earliest error.

21.0.0.2 Reflection on equation solutions:

We start with an uncompressed linear equation written as a sum of \(n\) first degree polynomials. Each step merges two of the polynomials into one, reducing to \(n-1\) first degree polynomials. Such that after \(n\) steps, the equation reduced. A single incorrect calculation is made along the chain, after which correct calculations propagate the error. The model is instructed to find the earliest error.

21.0.0.3 Evaluating pass rate along a CoT:

We sample full CoTs to AIME 2025 questions from a model (DeepSeek-R1-Distilled-1.5B/7B). The sampling configuration is set to 16k new tokens, using nucleus sampling with default parameters of the model. We then truncate the CoT at evenly spaced positions of \(1k\) tokens (rounding up at ends of sentence) along the chain and evaluate the pass rate at those positions - by instructing the model to provide a final answer, followed by the model’s end of CoT token \(</ think>\), with a budget of up to \(1024\) tokens and same configurations, using \(100\) generations for the pass rate evaluation. Additionally, for the same evaluation at self-reflection points, we truncate at phrases that imply explicit self-reflection ("Wait").

21.0.0.4 Evaluation of change in log likelihood of pass rate:

In figure 3 (c), we show a histogram of change in pass rate log ratio between consecutive self-reflections. As the pass rate is evaluated with \(100\) final answer completions, pass rates below \(0.01\) are not captured. We thus use a truncated version - \(\log\frac{p_t+0.01}{p_{t-1}+0.01}\).

21.0.0.5 Synthetic trees:

We sampled trees of width \(3\) and depth \(n\). Posterior updates used \(\eta=0.5\).

21.0.0.6 Compute:

All experiments were performed with up to \(4\) \(L4\) gpus.

References↩︎