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

以扩展推理训练大语言模型（LLM）使能了上下文内搜索：模型迭代生成、批评并修订解答尝试。我们把上下文内搜索建模为推理轨迹上的近似推断——基座模型定义先验、自我反思提供后验更新的反馈——并研究由此产生的推理时采样复杂度：达到高成功概率所需的串行尝试数。我们显示：当反思可靠地定位早期错误时，上下文内搜索可产生相对基座模型的指数改进——仅用多项数量的串行尝试解决零样本通过率指数小的难题；而当该性质失效时，以既往尝试为条件相对并行采样没有渐近收益。我们进一步显示这些增益是鲁棒且可学习的：近似后验更新即足够，且在搜索rollout上的交叉熵训练以多项样本复杂度恢复所需行为。最后，在带可验证奖励的强化学习的分阶段抽象下：最优策略扩展实现同样的后验重加权规则。我们在真实大型推理模型上验证理论的关键定性预测。