🤖 AI

Forge: Quality-Aware Reinforcement Learning for NP-Hard Optimization in LLMs

本文介绍了 OPT-BENCH，这是一个综合框架，利用质量感知的可验证奖励强化学习（RLVR）在 NP 难优化问题上训练大语言模型，相较于现有模型和二元奖励方法，该框架在解决多样化推理任务时显著提升了求解质量与泛化能力。

原作者： Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Yang Li, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen

发布于 2026-05-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Xiaozhe Li, Xinyu Fang, Shengyuan Ding, Yang Li, Linyang Li, Haodong Duan, Qingwen Liu, Kai Chen

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

想象你有一个非常聪明的机器人助手（大型语言模型，或称 LLM），它擅长回答诸如“这道数学题解对了吗？”或“这个单词拼写正确吗？”之类的问题。长期以来，我们训练这些机器人的方式是：如果答案正确就说“做得好！”，如果错误就说“再试一次”。这就像批改一份只有唯一正确答案的选择题试卷。

但如果任务不仅仅是得到“正确”的答案，而是要得到“最佳”的答案呢？

这正是论文 FORGE 所解决的问题。这就像要求机器人不仅要找到一条去杂货店的路，还要找到尽可能“最短、最快”的那条路，即使存在数百万条其他有效但耗时更长的路线。

以下是他们实现方法的简要分解：

1. 问题：“足够好”与“最佳”

想象你在收拾行李箱。

旧方法（二元奖励）： 你让机器人收拾。如果所有物品都装进了袋子，你就说“成功！”；如果溢出来了，你就说“失败”。机器人学会的只是把物品“塞进”袋子里，哪怕行李箱还有一半是空的，或者把重物压在易碎物品上面。
FORGE 方法（质量感知奖励）： 你告诉机器人：“成功固然好，但如果你能在同样的空间里装进“更多”东西，或者摆放得更轻，你就会获得更大的奖励。”机器人学会不断尝试改进打包方式，直到达到完美。

该论文认为，当前的人工智能模型非常擅长找到“有效”的解决方案（例如一条可行的路线），但极不擅长找到“最优”的解决方案（绝对最佳的路线）。这对于物流、调度和网络设计等现实世界问题至关重要，这些问题被称为 NP 难问题（即极难完美解决的数学问题）。

2. 解决方案："Forge"工厂

作者们建立了一个名为 FORGE-ENGINE 的工厂，用于训练这些机器人成为更优秀的优化器。这就像是为 AI 的大脑建了一个健身房，只不过它举的不是哑铃，而是在解决复杂的谜题。

该工厂有三台主要机器：

生成器： 这台机器生成数百万个练习谜题。它可以制造简单的谜题（如 5 块拼图）、中等难度的，甚至是困难的（如 1000 块拼图）。
验证器： 这是一位严格的裁判。它检查机器人的解决方案是否真正遵循了规则（例如：“你是否恰好访问了每个城市一次？”）。
启发式求解器（秘密武器）： 这是最重要的部分。它是一个超快速的传统计算机程序，能够“几乎”完美地解决谜题。它充当“黄金标准”或教练。
- 类比： 想象机器人是一个正在考试的学生。验证器检查答案是否书写正确。启发式求解器则是手握答案的教师。如果机器人得了 80 分，教师不会只说“错了”。教师会说：“你得了 80 分。试着拿到 90 分。”这给机器人提供了一个连续分数，而不是简单的“通过/不通过”。

3. 训练方法：“攀登高山”

你不能立刻把机器人扔进 1000 块拼图的难题中；它会感到困惑并放弃。因此，该论文采用了课程学习策略：

简单阶段： 机器人解决小型、简单的谜题以学习规则。
中等阶段： 谜题变得更大。机器人学会提前规划。
困难阶段： 机器人挑战巨大且复杂的谜题。
重放技巧： 作者们注意到，如果只向前推进（简单→困难），机器人会忘记如何做简单的任务。因此，他们让机器人定期重玩简单和中等难度的关卡。这使其在掌握高难度内容的同时，保持技能熟练。

4. 结果：更聪明的头脑

他们在 10 种不同类型的困难谜题（如规划送货卡车的最佳路径或安排无冲突的会议）上测试了他们的新机器人（名为 FORGE）。

得分： 机器人不仅找到了“一个”解决方案，而是找到了“出色”的解决方案。它以巨大优势击败了著名的 GPT-4o 模型。当 GPT-4o 约 62% 的时间能找到有效解决方案时，FORGE 达到 93%。更重要的是，FORGE 的解决方案更接近“完美”答案。
额外效应： 这是最酷的部分。当他们在这些高难度优化谜题上训练机器人时，它不仅在谜题上变得更擅长，在其他所有方面也变得更擅长。
- 它在数学上变得更擅长。
- 它在逻辑上变得更擅长。
- 它在遵循指令上变得更擅长。
- 类比： 这就像训练一名棋手成为特级大师。在这个过程中，他们不仅棋艺精进，在策略、耐心和日常生活的规划方面也变得更擅长。该论文表明，学习“优化”（寻找最佳解决方案）教会了 AI 一种深入思考并完善其答案的通用技能，这有助于它完成各种任务。

总结

这篇论文介绍了 FORGE，一种训练 AI 的新方法。他们不再仅仅教导 AI 获得“正确”的答案，而是通过对其解决方案的质量给予持续评分，教导它寻找可能的最佳答案。这将 AI 转变为一位优化大师，它不仅比当前顶级模型更擅长解决高难度数学谜题，而且在通用推理、逻辑和遵循指令方面也变得更加聪明。

技术摘要：FORGE-ENGINE

问题陈述

尽管大语言模型（LLM）通过可验证奖励的强化学习（RLVR）在推理基准测试（数学、编程、逻辑）中取得了显著成功，但现有的评估范式存在一个关键局限：它们仅关注正确性（可行性），而非最优性。在许多现实场景中，如物流或资源分配，仅仅“有效”的解决方案是不够的；目标是找到最大化或最小化目标函数的解决方案。当前的基准测试通常依赖二元奖励（通过/失败），无法提供引导模型走向最优解所需的密集、连续反馈。此外，现有的 NP-hard 基准测试缺乏生成真实最优值的机制，阻碍了细粒度奖励的计算，导致训练退化为低效的二元反馈循环。

方法论：FORGE-ENGINE

作者提出了FORGE-ENGINE，这是一个旨在利用质量感知 RLVR在 NP-hard 优化问题上训练和评估大语言模型的综合框架。该框架包含三个核心组件：

1. 数据构建流程

该框架采用可扩展的四阶段流程，生成涵盖五个类别（图聚类、资源调度、图划分、子集选择、路径规划）中 10 个不同 NP-hard 任务的训练数据。

可控生成器：采用“按设计构建”的方法，生成具有分级难度（简单、中等、困难）的无限实例，以保证可行解的存在。
基于规则的验证器：自动验证约束满足情况并计算目标值，确保绝对正确性，无需人工标注。
启发式求解器：这是一项关键创新，任务特定的启发式算法（例如，针对旅行商问题 TSP 的多起点最近邻算法结合 2-opt）为每个实例计算近优基线。这些基线作为奖励计算的真实依据。
课程校准：对难度级别进行经验校准，以实现目标成功率（例如：简单：70-90%，困难：10-40%），以促进渐进式学习。

2. FORGE-BENCH

这是一个严格的评估基准，包含 1,000 个高复杂度实例（每个任务 100 个），设计为在训练期间不可见。与 prior works 不同，它使用两个互补指标评估模型：

成功率（SR）：模型生成满足所有约束的有效解的实例百分比。
质量比率（QR）：衡量解相对于启发式基线质量的连续指标（例如，对于最小化问题， $QR = \text{启发式} / \text{模型}$ ）。这区分了仅仅可行和近优的解。

3. 质量感知 RLVR 框架

该训练策略用源自启发式基线的细粒度连续奖励取代了稀疏的二元信号。

奖励函数：分层奖励系统在三个维度上评估输出：
1. 格式奖励（ $R_{format}$ ）：确保结构化推理（例如，<thought> 标签）。
2. 可行性奖励（ $R_{feasibility}$ ）：对违反约束进行惩罚（例如 -1.5），并对有效解传递最优性得分。
3. 最优性奖励（ $R_{optimal}$ ）：基于模型目标值与启发式基线比率的连续分数，为优化提供密集反馈。
多阶段课程回放：为缓解“冷启动”问题和灾难性遗忘，训练采用循环策略（简单 $\to$ 中等 $\to$ 困难），多次迭代难度级别，在逐步攻克复杂优化的同时巩固基础技能。

关键结果

实验在Qwen2.5-7B-Instruct-1M上进行，训练数据为 15,000 个示例（三个阶段共 15K）。

域内性能：生成的模型FORGE在 FORGE-BENCH 上实现了93.1% 的成功率和46.6% 的质量比率。这显著优于 GPT-4o（62.1% SR，36.2% QR），并大幅超过基座模型的性能（29.6% SR，14.6% QR）。
域外（OOD）泛化：在 FORGE-ENGINE 上的训练迁移到了多样化的推理任务，带来了以下提升：
- 指令遵循：+6.1%
- 知识推理：+4.1%
- 数学：+2.2%
- 逻辑：+1.2%
消融研究：
- 奖励设计：与二元奖励相比，质量感知奖励将解的质量提高了 28.8%，防止了奖励黑客行为并引导模型走向真正的最优性。
- 课程策略：多阶段课程回放优于线性单次通过策略，打破了性能瓶颈并防止停滞。
- 任务多样性与数量：研究发现，在 10 个多样化任务上进行训练比在较少任务上使用更多数据进行训练能带来更好的泛化效果，表明接触多样化的问题结构是推理能力的关键驱动力。
- RLVR 与 SFT：虽然对最优解进行监督微调（SFT）提升了域内性能，但它导致了灾难性的域外退化（-12.0 分）。相比之下，RLVR 培养了稳健且可迁移的约束满足策略。

意义与主张

论文声称，FORGE-ENGINE是首个通过集成启发式求解器提供细粒度最优性奖励，从而成功将 RLVR 应用于 NP-hard 优化问题的综合框架。

作者断言，这项工作弥合了大语言模型推理中可行性与最优性之间的鸿沟。通过超越二元正确性，该框架使模型能够参与迭代优化搜索。至关重要的是，论文提供了实证证据，表明优化训练培养了一种可迁移的“优化思维”——即生成候选解并自我优化的能力——这增强了超越特定优化任务的更广泛推理能力。研究结果表明，对于扩展 RLVR 而言，任务多样性和质量感知奖励比单纯的数据量更为关键。

这项工作被视为将大语言模型与基于优化的推理相结合的基石，为未来复杂推理研究提供了可扩展的基础设施和基准。