LLM中扩展搜索空间上的类优化逐步推理

摘要

可验证的奖励训练改进了数学和编码推理，但这些领域仅捕获了逐步决策的一部分。许多现实世界的任务需要在许多有效的替代方案中找到一个高价值的可行计划。我们引入了 OPT*，这是一个可扩展的优化式任务系列，用于沿着复杂性轴训练和评估 LLM 逐步优化式推理：每个任务提供可行性检查器和评估器，而复杂性参数扩展搜索空间，而不需要新的人工标签。这促使我们以两种方式研究这些任务：（i）求解器引导的在线策略优化，它使用求解器作为部分状态的价值预言机，并应用基于排名的奖励塑造来加强更好的后续步骤，以及（ii）当此类求解器不可用时，基于搜索的离线强化学习。理论上，我们将大型搜索空间中的成功与推理机每单位搜索预算提取的信息联系起来。根据经验，我们消除了在 OPT* 上提高搜索效率的因素，并表明 OPT* 上的训练可以改善逐步优化的推理。

LLM中扩展搜索空间上的类优化逐步推理：论文配图 — 图 1：使用旅行推销员风格示例的 OPT⋆\star 概述。 (a) 任务可以由人类、程序或 LLM 辅助生成器实例化。 (b1) 经典优化问题自然地暴露目标和约束，使它们可以自动验证。 (b2) 可以通过改变复杂性参数 α\alpha 来调整难度，例如客户数量或实例结构。增加 α\alpha 会扩大搜索空间，同时可行性和客观评估仍然便宜。 (c) 我们研究两种训练方法：当求解器可用时，求解器引导的下一步监督；当只有可行性检查和最终目标值可用时，基于搜索的发现。 (d) 模型动作可以对应于固定一个或多个结构化决策变量。