本文对上下文搜索进行了理论分析，将其建模为基于推理轨迹的近似推断，其中基础模型定义先验分布，自我反思提供用于后验更新的反馈。作者研究了由此产生的推理阶段采样复杂度，定义为实现高成功概率所需的连续尝试次数。

  • 当反思能够可靠地定位早期错误时，上下文搜索相比基础模型可实现指数级改进，仅用多项式次数的连续尝试即可解决零样本（zero-shot）通过率呈指数级小的问题。
  • 如果该性质不成立，基于历史尝试的条件化在渐近意义上并不优于并行采样。
  • 这些增益具有鲁棒性且可学习：近似后验更新已足够，通过对搜索 rollout 进行交叉熵训练即可以多项式样本复杂度恢复所需行为。
  • 在带有可验证奖励的强化学习（reinforcement learning）的分步抽象下，最优策略扩展实现了相同的后验重加权规则。

作者在实际的大型推理模型上验证了该理论的关键定性预测。