When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning

上下文搜索何时有效？反射驱动推理的采样复杂度理论

Abstract: Training large language models (LLMs) with extended reasoning has enabled in-context search, in which models iteratively generate, critique, and revise solution attempts. We provide a theoretical analysis of in-context search by modeling it as approximate inference over reasoning traces, where the base model defines a prior and self-reflection provides feedback for posterior updates, and study the resulting inference-time sampling complexity - the number of sequential attempts needed to achieve high success probability.

摘要： 训练具有扩展推理能力的大型语言模型（LLM）实现了上下文搜索，即模型可以迭代地生成、批判并修正解决方案。我们通过将上下文搜索建模为推理轨迹上的近似推断，对其进行了理论分析。在该模型中，基础模型定义了先验分布，而自我反射则为后验更新提供了反馈。我们研究了由此产生的推理时采样复杂度——即实现高成功概率所需的顺序尝试次数。

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, whereas when this property fails, conditioning on past attempts offers no asymptotic benefit over parallel sampling.

我们证明，当反射能够可靠地定位早期错误时，上下文搜索可以比基础模型产生指数级的性能提升，仅需多项式数量的顺序尝试即可解决零样本通过率极低的问题；而当该特性失效时，基于过往尝试的条件化在渐近意义上并不比并行采样具有优势。

We further show 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 show 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.

我们进一步证明，这些增益是稳健且可学习的：近似后验更新已足够，且通过对搜索过程进行交叉熵训练，可以以多项式采样复杂度恢复所需的行为。最后，我们证明在具有可验证奖励的强化学习分阶段抽象下，最优策略扩展实现了相同的后验重加权规则。我们在真实的大型推理模型上验证了该理论的关键定性预测。