Wolf et al. prove in-context search yields exponential gains when mistakes localized

A new paper from researchers Yotam Wolf, Noam Wies, and Amnon Shashua provides a theoretical foundation for understanding when iterative self-reflection—also known as in-context search—actually improves LLM reasoning. The authors model the process as approximate inference over reasoning traces, where the base model defines a prior and self-reflection provides feedback for posterior updates. Their core finding: when reflections reliably localize early mistakes, in-context search produces exponential improvements over the base model’s zero-shot performance, requiring only a polynomial number of sequential attempts. Conversely, when this property fails, conditioning on past attempts offers no asymptotic benefit over simple parallel sampling.

The theory also demonstrates that these gains are robust: approximate posterior updates suffice, and cross-entropy training on search rollouts can recover the desired behavior with polynomial sample complexity. Additionally, the authors connect their framework to reinforcement learning with verifiable rewards, showing that the optimal policy extension implements the same posterior reweighting rule. They validate key predictions on real large reasoning models, confirming the qualitative behavior of their theoretical results. This work provides a rigorous lens for understanding when and why reflection-driven reasoning works, offering practical guidance for designing more efficient inference-time search strategies in LLMs.