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

arXiv:2607.06720v1 公告类型：新 摘要：使用扩展推理训练大型语言模型 (LLM) 已启用上下文搜索，其中模型迭代地生成、批评和修改解决方案尝试。我们通过将上下文搜索建模为推理轨迹上的近似推理来提供上下文搜索的理论分析，其中基本模型定义先验，自我反思为后验更新提供反馈，并研究由此产生的推理时间采样复杂性——实现高成功概率所需的连续尝试的次数。我们表明，当反射可靠地定位早期错误时，上下文搜索可以在基本模型上产生指数级改进，仅使用多项式数量的顺序尝试来解决指数小零样本通过率的问题，而当此属性失败时，对过去尝试的条件与并行采样相比没有渐近优势。我们进一步表明，这些增益是稳健且可学习的：近似后验更新就足够了，搜索推出的交叉熵训练可以以多项式样本复杂度恢复所需的行为。最后，我们表明，在具有可验证奖励的强化学习的阶段性抽象下，最优策略扩展实现了相同的后验重新加权规则。我们在真实的大型推理模型上验证了该理论的关键定性预测。