This article provides a theoretical analysis of in-context search, modeling it as approximate inference over reasoning traces where the base model defines a prior and self-reflection provides feedback for posterior updates. The authors study the resulting inference-time sampling complexity, defined as the number of sequential attempts needed to achieve high success probability.
- When reflections reliably localize early mistakes, in-context search yields exponential improvements over the base model, solving problems with exponentially small zero-shot pass rates using only a polynomial number of sequential attempts.
- If this property fails, conditioning on past attempts offers no asymptotic benefit over parallel sampling.
- 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.
- Under a stagewise abstraction of reinforcement learning with verifiable rewards, the optimal policy extension implements the same posterior reweighting rule.
The authors validate key qualitative predictions of the theory on real large reasoning models.