💬 NLP

HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization

本文介绍了 HeuriGym，这是一个开源的智能体基准测试，用于评估大语言模型迭代生成并优化组合优化问题启发式算法的能力，并通过一种新颖的质量-收益指数（Quality-Yield Index）指标，揭示了当前模型在工具使用和自适应推理方面的显著局限性。

原作者： Hongzheng Chen, Yingheng Wang, Yaohui Cai, Hins Hu, Jiajie Li, Shirley Huang, Chenhui Deng, Rongjian Liang, Shufeng Kong, Haoxing Ren, Samitha Samaranayake, Carla P. Gomes, Zhiru Zhang

发布于 2026-01-29

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Hongzheng Chen, Yingheng Wang, Yaohui Cai, Hins Hu, Jiajie Li, Shirley Huang, Chenhui Deng, Rongjian Liang, Shufeng Kong, Haoxing Ren, Samitha Samaranayake, Carla P. Gomes, Zhiru Zhang

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

想象一下，你拥有一支由极其聪明、博学多才的机器人（大语言模型，简称 LLM）组成的团队。它们擅长写论文、回答常识问题，甚至能编写基础的计算机代码。你想知道它们是否真的能够独立解决困难的现实世界谜题，而不仅仅是背诵教科书上的答案。

这篇论文介绍了一个名为 HeuriGym 的新“健身房”来测试这一点。以下是通过简单的类比对它的工作原理进行的解释：

1. 问题所在：“问答竞赛” vs. “真正的职业”

目前的 AI 测试就像是一场多项选择题测验。

问题在于： 如果你问 AI 一个它在训练数据中见过的数学题，它能拿 A+。但如果你问它一种新类型的问题，它往往会陷入僵局。这就像一个背下了答案解析、却并不理解数学本质的学生。
旧的方法： 一些测试要求 AI 编写能够通过特定检查的代码。但这些测试通常过于简单，或者只有一个“正确答案”。
新的方法 (HeuriGym)： HeuriGym 不仅仅是举办一场考试，它更像是给 AI 一个复杂的建筑工程项目，且没有任何说明书。目标不仅仅是“通过”测试，而是要建造一台高效运转的机器。

2. 挑战：“组合优化”谜题

该论文关注一种特定类型的难题，称为组合优化 (Combinatorial Optimization)。

类比： 想象你是一名物流经理，负责调度 1,000 辆货车。你必须为每辆车规划出完美的路线，以便它们使用最少的燃油并准时到达。
难点： 可能的路线数量比宇宙中的原子还要多。你无法检查所有路径。你必须成为一个“启发式 (heuristic)”天才——这意味着你必须发明一种聪明的捷径或“经验法则”，以便快速找到一个足够好的解法，即使它在数学上不是完美的。

3. 设置：“智能体循环 (Agentic Loop)”

HeuriGym 不仅仅是让 AI 写一次代码并评分。它建立了一个反馈循环，就像带有“重生”机制的视频游戏一样。

提示词 (The Prompt)： AI 接收到一个问题描述（例如：“调度这些电子电路以实现最快运行速度”）。
尝试 (The Attempt)： AI 编写一个程序（一种启发式算法）来解决问题。
现实检查 (The Reality Check)： 系统运行该代码。
- 它崩溃了吗？（语法错误）
- 它违反规则了吗？（约束违规）
- 它运行太慢了吗？（超时）
反馈 (The Feedback)： 系统告诉 AI：“你尝试使用了一个不存在的库，”或者“你的方案违反了时间限制。”
重试 (The Retry)： AI 阅读错误信息，从中学习，并尝试重写代码以修复错误。

这个循环不断重复，允许 AI 通过试错来“学习”如何解决问题，就像人类工程师一样。

4. 评分标准：“质量-产出指数 (QYI)”

如何为一个试图发明新方法来解决谜题的机器人评分呢？作者创建了一个新的分数，称为 QYI。

产出 (Yield)： 机器人是否在没有崩溃的情况下完成了任务？（它是否得到了一个可运行的解？）
质量 (Quality)： 与人类专家相比，这个解法有多好？
得分： 得分为 1.0 意味着机器人的表现与人类专家完全一致。得分为 0 意味着它完全失败。

5. 结果：“现实检验”

作者测试了九种目前最智能的 AI 模型（如 GPT-o4-mini 和 Gemini-2.5-Pro）。

结论： 即便是那些“最聪明”的模型，得分也仅在 0.6 左右。
这意味着： 最优秀的 AI 模型在处理这些任务时，其效能仅为人类专家的 60% 左右。它们通常能写出可以运行的代码，但在编写足够高效或足够具有创造性以击败人类设计方案的代码方面，仍感到吃力。
困境： 这些模型经常陷入死循环、产生幻觉（编造不存在的计算机库），或者无法理解复杂的约束条件。它们擅长遵循指令，但在“跳出框架思考”以发明新策略方面表现不佳。

6. 为什么这很重要

论文指出，我们需要停止用简单的问答来测试 AI，而应该开始用真实的工程挑战来测试它们。

目标： 推动 AI 的发展，使其能够真正进行推理、适应并为科学和工程领域发明新的解决方案，而不仅仅是记忆模式。
总结： 我们已经建立了一个强大的工具（HeuriGym）来衡量这种进步。目前，AI 像是一个很有前途的学徒，但在成为解决复杂现实世界优化问题的“大师级匠人”之前，还有很长的路要走。

简而言之： HeuriGym 是一个 AI 机器人尝试通过制造自己的工具来解决不可能完成的谜题的“健身房”。它们正在进步，但仍然会犯很多错误，并且尚未达到人类专家的水平。

技术摘要：HeuriGym：针对 LLM 启发式算法在组合优化领域表现的智能体基准测试

问题陈述

当前的语言大模型（LLM）评估方法在评估其问题解决能力方面面临双重危机。首先，基于真值的客观基准测试（如 AIME、HumanEval）依赖于闭口式问题，容易受到数据污染和性能饱和的影响，无法反映解不唯一或预定义的真实世界场景。其次，基于评判者偏好的主观评估（如 Chatbot Arena）引入了高方差，且往往优先考虑表层因素而非实质性的推理质量。

目前存在一个关键差距，即如何评估 LLM 是否能够超越模式识别，在复杂的迭代工程工作流中展现出真正的解决问题能力。具体而言，现有的基准测试难以评估设计新型组合优化（CO）启发式算法的能力，这类算法需要导航广阔的解空间、遵循严格的约束条件，并根据运行时的反馈调整策略。

方法论

作者引入了 HeuriGym，这是一个智能体框架，旨在评估 LLM 生成、执行及迭代优化组合优化问题启发式算法的能力。

框架概述

HeuriGym 通过一个包含三个阶段的交互式智能体循环运行：

问题描述： LLM 接收一个结构化提示词，其中包含自然语言背景、目标与约束的数学形式化定义，以及特定的输入/输出文件格式。不同于以往提供部分实现或脚手架的工作，HeuriGym 仅提供函数接口，要求 LLM 从零开始设计数据结构和算法。
执行与验证： 生成的代码在沙盒环境中进行编译或解释。领域特定验证器检查约束满足情况（例如依赖性保持），而评估器则根据优化目标计算成本。
迭代优化： 来自小型演示集的执行日志、验证结果和性能指标会被附加到提示词中。这种反馈循环允许 LLM 在多次迭代中进行调试错误、纠正约束违规并优化其启发式策略。

基准测试构建

该基准测试包含 九个组合优化问题，涵盖计算机系统、物流和计算生物学领域（例如算子调度、技术映射、航空公司机组配对、蛋白质序列设计）。

选择标准： 所选问题的文献曝光度较低（引用次数最多的论文也少于 1,000 次），以最大限度降低记忆风险。这些问题具有定义明确的自然语言规范、庞大的解空间和可扩展的数据实例。
数据集： 每个问题都包含一个小型演示集（约 5 个实例）用于少样本提示和迭代优化，以及一个较大的评估集（数十个实例）用于最终测试。

评估指标

为了解决标准指标（如 PASS@k）的局限性，作者提出了：

SOLVEs@i： 追踪在 $i$ 次迭代内解决受限问题的概率，衡量通过三个阶段的成功率：执行（阶段 I）、解生成（阶段 II）和验证（阶段 III）。
质量-产量指数 (QYI)： 一个由质量（解与专家基准的接近程度）和产量（通过验证的实例比例）的调和平均值定义的统一指标。
- $Quality = \frac{1}{\hat{N}} \sum \min(1, \frac{c^*_n}{c_n})$ ，其中 $c_n$ 是 LLM 成本， $c^*_n$ 是专家成本。
- $Yield = \frac{\hat{N}}{N}$ ，其中 $\hat{N}$ 是通过验证的解的数量。
- $QYI = \frac{(1 + \beta^2) \cdot Quality \cdot Yield}{(\beta^2 \cdot Quality) + Yield}$ （其中 $\beta=1$ ）。

关键结果

作者在 HeuriGym 基准测试上评估了九种最先进的模型（包括 GPT-o4-mini-high、Gemini-2.5-Pro、DeepSeek-R1 和 LLaMA 变体）。

性能差距： 即便是顶尖模型也难以达到专家级水平。表现最好的模型 Gemini-2.5-Pro 取得的 QYI 分数约为 0.62，表明其解平均而言仅达到专家级启发式算法有效性的 60%。其他模型得分显著较低（例如 LLaMA-3.3 和 LLaMA-4-Maverick 低于 0.30）。
迭代改进： 增加迭代次数会显著提高性能。例如，GPT-o4-mini-high 的成功率（SOLVEIII）从第 1 次迭代的 53.2% 上升到第 10 次迭代的 74.8%，凸显了迭代优化的重要性。
失败模式： 分析揭示了常见的失败类型，包括幻觉 API、错误的算法逻辑、误解约束以及超时。
进化框架： 标准的进化搜索框架（如 ReEvo、HSEvo）表现较差，甚至低于基准模型，通常无法有效地整合执行反馈，并在迭代过程中破坏上下文。

重要性与贡献

该论文声称有三个主要贡献：

一个开源基准测试套件： 一个包含九个具有现实意义、高影响力的组合优化问题的集合，用于评估多步推理和算法设计能力，超越了单纯的模式记忆。
一个端到端的智能体框架： 一个支持解生成、自动化验证和迭代优化的系统，作为高级提示技术和进化策略的试验场。
实证洞察： 一项全面的研究，揭示了当前的 LLM 尽管具备推理能力，但在应用于复杂的现实科学与工程问题时，在工具使用、规划和自适应推理方面仍面临持续的局限性。

作者将 HeuriGym 定位为引导 LLM 发展的重要一步，使其向更有效的、更真实的解决问题方向迈进，特别是在那些最优解仅对小规模实例可行且启发式发现至关重要的领域。该基准测试旨在暴露当前模型能力与实际工程工作流需求之间的差距，鼓励开发能够进行真正的启发式发明而非仅仅是模式匹配的模型。