自适应生成排名验证：具有昂贵验证的推理时间搜索

许多推理时语言模型管道将廉价的奖励信号与昂贵的验证器相结合，例如数学推理中的精确答案检查或代码生成中的隐藏测试执行。我们使用学习理论镜头将这种设置形式化为生成主动搜索：一个成本敏感的第一正搜索问题，其中策略自适应地从未知分布中对候选者进行采样，观察便宜的分数，并为验证者标签付费，直到找到正例。对于固定提示，生成器和奖励模型会引入两个未知对象：奖励分数的分布和分数条件的成功函数。当这些数量已知时，我们使用动态规划方法来描述分布感知最优策略。在得分分布和成功函数均未知的现实和实际环境中，我们提出了 ADAP，这是一种 shellwise 自适应生成排名验证算法，可逐步增加采样响应和顶级验证的数量。在单调性假设下，即较高的奖励分数通过验证的可能性并不低，我们表明 ADAP 在分布感知最优值的恒定因子内实现了预期成本。我们用基于中心星号的学习理论下限来补充这一结果，表明对分数-标签关系的结构假设是必要的。数学推理和竞争性编程的实验验证了相对于固定非自适应策略和难度自适应基线的预测优势。