Abstract
Training large language models (LLMs) for extended reasoning has enabled in-context search, wherein models iteratively generate, critique, and revise solution attempts. We model in-context search as approximate inference over reasoning traces, where the base model defines a prior and self-reflection provides feedback for posterior updates. We investigate the inference-time sampling complexity—the number of sequential attempts required 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. Conversely, when this property fails, conditioning on past attempts offers no asymptotic benefit over parallel sampling.
Additionally, we demonstrate 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 illustrate 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.
Blogger's Review: This paper provides a profound analysis of the role of in-context search in reflection-driven reasoning, offering a theoretical framework and empirical validation. The crucial impact of self-reflection on enhancing model accuracy and efficiency in complex reasoning tasks is particularly noteworthy for researchers in the field.