🤖 AI

Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces

本文介绍了 OPT*，这是一个具有扩展搜索空间的、可扩展的优化类任务族，它通过基于求解器引导的在线策略优化和基于搜索的离线强化学习，使大语言模型能够进行逐步的类优化推理训练与评估。

原作者： Nicolás Astorga, Nabeel Seedat, Mihaela van der Schaar

发布于 2026-06-05

📖 1 分钟阅读☕ 轻松阅读

原作者： Nicolás Astorga, Nabeel Seedat, Mihaela van der Schaar

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在教一个非常聪明但有点天真的机器人厨师，如何烹饪一道复杂的、多道菜的盛宴。

问题所在：“足够好”陷阱
目前，这些 AI 厨师（大语言模型）非常擅长遵循只有唯一正确答案的食谱，比如解决数学方程或编写可以编译的代码片段。如果它们得到了最终答案，就会得到一颗金星。

但现实生活并非如此。现实生活更像是为 50 辆卡车规划配送路线、为 20 名员工分配 20 个不同的班次，或者装载一辆搬家卡车。在这些场景中，并不存在唯一的正确答案，而是存在成千上万种“有效”的方法（没有出错，每个人都有工作），但其中只有极少数是“极佳”的方法（最短距离、最高满意度、最少空间浪费）。

论文指出，目前的 AI 在处理这类问题时表现挣扎。它可能会找到一个有效的计划，但往往会陷入一个“足够好”的计划中，并因此错过那个“完美”的计划，因为它不知道如何提前观察或及早剔除糟糕的想法。

解决方案：OPT⋆（无限游乐场）
作者创建了一个新的训练场——OPT⋆。你可以把它想象成一个视频游戏关卡生成器，它可以让游戏变得越来越难，而无需人类设计师来绘制新关卡。

游戏： 他们使用了经典的优化谜题（如旅行商问题，即以最短路径访问城市，或将物品装入背包）。
作弊条（辅助工具）： 游戏内置了两个工具：
1. 规则检查器： 立即告知你某个动作是否非法（例如：“你不能把那个沉重的箱子放在脆弱的箱子上面”）。
2. 计分员： 立即告诉你最终结果有多好（例如：“你的路线节省了 10 分钟”）。
难度调节旋钮： 你可以通过旋转一个旋钮（称为 $\alpha$ ）来增加更多的城市、更多的工人或更多的物品。这会让可能的路径呈指数级爆炸式增长，但规则和评分机制保持简单且自动化。不需要人类来批改作业。

他们是如何教 AI 的：两种方法

论文测试了两种教导 AI 在这些庞大且不断扩张的迷宫中导航的方法：

1. “离线”方法：寻宝游戏
想象一下，AI 被丢进了一个黑暗的洞穴（搜索空间），手里只拿着一把手电筒。它没有地图。

策略： AI 到处乱逛，尝试不同的路径。当它发现一条通往宝藏（高分）的路径时，它会记住这条路径。
诀窍： 论文引入了两个“智能过滤器”来提高寻宝效率：
- 保镖（可行性检查）： 如果 AI 试图穿墙而过（执行非法动作），保镖会立即阻止它。这样它就不会在死胡同里浪费时间。
- 孪生检测器（去重）： 有时 AI 会用英语说“向北走”，用法语说“向上走”，或者用西班牙语说“向上移动”。这些其实都是同一个动作。孪生检测器意识到它们是相同的动作，并只保留一个，从而避免 AI 浪费精力重复思考同一个想法。
结果： AI 学会了忽略死胡同和重复的想法，从而更快地找到宝藏。

2. “在线”方法：拥有预知能力的教练
在这种情景下，AI 有一位能够看到未来的教练（求解器）。

策略： AI 做出一个动作。教练观察这个动作，并立即计算：“如果你采取这一步，从这里开始你最高能达到的分数是 90 分。”
奖励： AI 不必等到游戏结束才获得分数，而是能在每一步都获得即时反馈。如果某一步会导致潜在得分降低，教练会说：“坏的动作！”如果某一步能带来高潜力，教练会说：“好的动作！”
结果： AI 学会了如何进行步步优化的决策，而不是仅仅寄希望于一个好的结局。

他们的发现

“分支”瓶颈： 随着游戏变得越来越难（更多城市/物品），路径的数量增长得如此之快，以至于普通的搜索就像是在一个银河系规模的草堆里寻找一根针。论文从数学上证明，要取得成功，AI 必须变得更擅长过滤掉坏路径，而不仅仅是更努力地尝试。
过滤器奏效了： “保镖”和“孪生检测器”（离线方法）显著提高了搜索效率。AI 比不使用它们时能更快地找到高质量的解决方案。
教练法效果最好（但成本高）： 使用教练（求解器）的“在线”方法培养出了最聪明的 AI，但它需要一台强大的计算机来充当教练。而“离线”方法在没有超级计算机可用时是一个很好的备选方案。
泛化能力： 当他们在这些优化谜题上训练 AI 时，它在其他空间任务（如旋转形状或覆盖网格）上也变得更出色了，甚至提高了其数学推理能力。这表明 AI 学到的是一种通用的“如何规划”的技能，而不仅仅是解决某一个特定谜题的技巧。

简而言之
这篇论文介绍了一种通过使用可以自动变得无限难的游戏来训练 AI 进行复杂规划的方法。通过教导 AI 快速识别非法动作并避免重复相同的想法，我们可以帮助它在庞大且复杂的难题中找到最优解，即使没有人类老师在旁边监督。

技术摘要：LLM 在扩张搜索空间中的逐步优化式推理

1. 问题陈述

尽管大语言模型（LLMs）通过可验证的奖励训练在数学和代码推理方面取得了成功，但在受约束的逐步决策任务中仍然表现脆弱。在这些场景中，一个局部合理的步骤可能会导致后续问题变得不可行，或迫使生成质量低下的完成结果。与存在单一正确答案的标准答案正确性设置不同，许多现实世界的任务（如资源分配、调度、路由）涉及许多可行解，其目标是在约束条件下构建一个高价值的解。

当前的扩展方法面临两个障碍：

生成能够可靠地要求非平凡推理的多元化任务非常困难。
获取中间步骤的监督成本昂贵，因为这需要识别哪些部分动作会导致最优结果。

本文解决了训练 LLM 在扩张的搜索空间中进行优化式推理的挑战，其中难度通过复杂度参数 $\alpha$ 进行控制，且无需新的人工标注。

2. 方法论：OPT⋆ 框架

作者引入了 OPT⋆（基于优化的可扩展任务自动验证推理），这是一个旨在训练和评估逐步推理的系列任务。

2.1 任务定义

一个 OPT⋆ 任务实例 $t$ 是一个由以下定义的约束决策过程：

可扩展生成： 实例由受复杂度参数 $\alpha$ 控制的程序 $Build_\alpha(\cdot)$ 生成（例如，TSP 中的城市数量、背包问题中的物品数量）。增加 $\alpha$ 会扩大搜索空间 $M(t)$ ，但不会增加标注成本。
廉价验证： 每个任务都提供两个低成本的例程：
- 可行性检查器 ($chkt$)： 验证部分动作（例如，确保未超过负载限制）。
- 结果评估器 ($evalt$)： 对完整的终端解进行评分（例如，总旅行长度）。
自动可验证性： 即使寻找最优解很难， $chkt $和$ evalt$ 也是可以在多项式时间内计算的。

2.2 训练机制

论文提出了两种基于求解器可用性的互补训练方法：

A. 求解器引导的在线策略优化 (Online RL)

当存在快速求解器可以计算从部分状态出发的最佳完成值时：

机制： 求解器充当价值预言机（Value Oracle）。对于给定的状态，采样候选的下一步，并使用在固定求解器预算下的最佳可达终端值对每一步进行评分。
奖励塑造： 使用基于排名的奖励（例如 GRPO, GSPO, PPO）更新策略，其中导致更高价值完成结果的动作会获得更高的排名。
目标： 强化那些导向更好最终结果的步骤，有效地将求解器启发式算法蒸馏到策略中。

B. 基于搜索的离线 RL (Offline RL)

当求解器不可用或对部分状态而言过于昂贵时：

机制： 模型生成候选轨迹。搜索算法（如 MCTS、束搜索/Beam Search）探索空间，利用 $chkt $剪枝无效路径，并使用$ evalt$ 为终端节点评分。
关键搜索组件：
1. 可行性剪枝： 丢弃满足 $chkt(s, a) = 0$ 的子节点。
2. 重复合并： 将映射到相同结构化动作的不同文本输出进行分组，以避免浪费搜索预算。
训练： 模型在搜索过程发现的最佳轨迹上进行微调（SFT），从而有效地学习模仿高价值的推理痕迹。

2.3 理论基础

论文建立了一个信息论界限（定理 A.3），将在大规模搜索空间中的成功与单位搜索预算中提取的信息量联系起来。随着复杂度 $\alpha$ 的增加，有效最优解的数量也会增加。为了保持固定的成功概率，推理器必须要么增加搜索预算，要么在每一步中提取更多信息。有效分支因子 ( $b_{eff}$ ) 被引入作为衡量搜索效率的指标；较低的 $b_{eff}$ 表示搜索预算在高质量终端状态上分配了更多的权重。

3. 核心贡献

概念层面 (OPT⋆)： 形式化了一个用于优化式推理的可扩展、自动可验证的任务族。该框架通过使用复杂度参数来扩展搜索空间，同时保持验证成本不变，从而实现了推理难度与标注成本的解耦。
算法层面：
- 开发了即插即用的搜索组件（可行性检查和重复合并），显著提高了离线设置下的搜索效率。
- 引入了 $\nu$ PO (求解器引导的策略优化)，这是一种利用求解器为在线 RL 提供步级奖励的方法，从而实现对部分状态的训练。
实证层面：
- 证明了在 OPT⋆ 上训练可以提高逐步推理在优化任务中的表现。
- 证据表明，课程学习（从易于 $\alpha_1$ 到难于 $\alpha_4$ 的训练）比仅在困难任务上训练具有更好的泛化能力。
- 展示了优化训练可以迁移到空间推理能力（如旋转、反射、覆盖）并提高数学基准测试（AMC, AIME）的表现。

4. 实验结果

作者在包括角色分配（Role Assignment）、MaxSAT、单机调度（Single-machine Scheduling）、TSP、2D 装箱（2D Packing）和二次指派问题（QAP）在内的任务上评估了该框架。

搜索效率 (Offline RL)：
- 启用可行性剪枝和重复合并显著降低了有效分支因子 ( $b_{eff}$ )。例如，在 QAP 中，使用这些组件的 $\nu$ MCTS 实现了 $b_{eff} \approx 24$ ，而未使用 LLM 提议的求解器参考基准则为 $b_{eff} \approx 728$ 。
- 这些组件是搜索效率的主要驱动力，使 QAP 的 pass@16 从 ~13% 提升到了 ~85%。
模型改进：
- 在 OPT⋆ 任务（角色分配、MaxSAT）上训练的模型相比基础模型有实质性提升。例如，Qwen2.5-3B 在角色分配任务上的 pass@1 从 32.5% 提升至 44.5% (Level 1)，从 17.8% 提升至 31.1% (Level 4)。
- 求解器引导的在线 RL 始终优于领域迁移基准（例如，在数学或代码任务上的训练无法很好地迁移到优化任务）。
泛化能力：
- 在优化任务上的训练提高了模型在分布外 (OOD) 空间问答任务（如旋转、对称、重叠）以及标准数学基准（AMC'23, AIME'24/25）上的表现。
- 课程效应： 混合课程训练 ( $\alpha_1 \to \alpha_4$ ) 的表现优于“仅易”和“仅难”训练策略，尤其是在更难的等级和 OOD 任务上。

5. 重要性与主张

本文声称 OPT⋆ 提供了一个原则性的测试平台，用于研究受约束下的逐步推理，填补了可验证奖励训练（对数学/代码有效）与现实世界优化任务之间的空白。

科学价值： 它提供了一个受控环境来研究扩张的搜索空间如何影响推理能力，并通过信息论分析支持了这一点，即随着复杂度的增长，成功需要从每个预算单位中提取更多信息。
实用价值： 所提出的方法（即插即用的搜索组件和求解器引导的 RL）为在复杂的流程（调度、路由）中训练模型提供了可扩展的方式，即使在无法重复调用精确求解器或求解器过慢的情况下也是如此。
研究范围： 作者指出，虽然求解器可以验证或解决特定实例，但目标是将可复用的启发式算法蒸馏到通用模型中。这项工作侧重于受传统问题启发的合成优化任务，并承认未来的工作可以通过使用 LLM 先验来扩展任务生成，以创建更加多样化且复杂的场景。

总之，本文证明了通过利用自动可验证的优化任务以及互补的离线/在线 RL 策略，LLM 可以更有效地学习导航扩张的搜索空间，从而提高其优化性能以及底层的空间和逻辑推理能力。