Transformer八子初创：AI横扫NP难题竞赛，Top 2%选手竟是智能体
【导读】编程智能体确实厉害！Transformer作者Llion Jones初创公司，专门收集了NP难题并测试了AI智能体，结果竟在上千人竞赛中排第 21！这意味着，它已经比绝大多数人写得好了。
物流路径选择、人员排班、工厂调度、电网平衡、旅行路线……
这些贴近现实的优化任务，看似日常，实则难度极高。
难点在于：一旦问题规模扩大，传统算法几乎无法计算出最优解。
通常只能依赖启发式或近似算法来接近答案。
这正是NP难(Non-deterministic Polynomial-time hard）题的典型特征。
面对如此复杂的问题，AI能否胜任？编程智能体表现如何？
为探索这一问题，Sakana AI与AtCoder展开合作，共同构建了ALE-Bench（ALgorithm Engineering Benchmark）。
联合创始人Llion Jones是Transformer八子之一
不同于传统的编程基准测试，ALE-Bench聚焦于需要长推理和创造性思维的高难度的NP难题。
由于NP-困难性质，这类问题本身没有明确的最优解，因此分数可以不断提升。
研究人员认为，它有潜力成为新一代推理与编程能力的重要评估标准。
为了应对这类问题，这次研究特别设计了端到端的智能体ALE-Agent。
它以Gemini 2.5 Pro为基础，采用两大核心策略：
（1）通过Prompt提供常用算法与技术的领域知识；
（2）推理阶段生成不同多样解法进行性能增强。
在现实环境中，ALE-Agent已经展现出强大能力。
图1：ALE-Bench概览。（左）ALE-Bench整合历届AtCoder启发式竞赛题目，如路径规划、任务调度等无已知最优解的复杂优化问题，并依据评分对提交程序进行排名。（右）ALE-Bench支持从基础大语言模型（LLM）到具备结构化引导能力的智能体（scaffolded agent）进行全面评估：智能体接收任务后提交代码，可选择性调用测试运行与可视化工具，像人类选手一样迭代优化解决方案
以下图2为例，任务描述如下：
编写一个程序，输入为二维网格上的大量取送请求（pickup-delivery pairs），任务是从中选择指定数量的请求，并规划一条从仓库出发、最终回到仓库的路径。
路径必须满足如下约束：对于每一个被选择的请求，必须先访问其取件点，再访问其对应的送达点。
程序的目标是使这条路径的总长度尽可能短。
评分以路径总长度为依据，路线越短，得分越高。
（每组输入的CPU时间限制为2秒）
图2：来自ALE-Bench的示例问题（ahc006）
5月，编程竞赛平台AtCoder举办了一场启发式竞赛（AtCoder Heuristic Competition，AHC）,吸引了全球顶尖开发者参与.
智能体与1,000名人类选手同场竞技，进行实时比拼。
最终，ALE-Agent表现出色，排名第21，跻身前2%。
AtCoder启发式竞赛第47届（AHC047）的排行榜中，名为「fishylene」的第21名选手，实为Sakana AI提交的智能体ALE-Agent。
这一成果标志着AI在解决现实世界中的优化问题方面取得了突破。
论文链接：https://arxiv.org/abs/2506.09050
数据集：https://huggingface.co/datasets/SakanaAI/ALE-Bench
代码：https://github.com/SakanaAI/ALE-Bench
NP难题，编程智能体新基准
ALE-Bench基于AtCoder启发式竞赛（AHC）构建而成。
为什么AHC值得关注？
因为AHC是AtCoder举办的知名编程比赛之一：
- 目前规模最大的得分型算法竞赛之一：该赛事每年约举行10～18场，截至2025年5月1日，已累计举办了49场正式比赛。
- 参赛者多: 每场比赛平均吸引约1,000名参赛者，过去两年共有超过6,000名用户参与过比赛。
- 题目贴近实际：目类型多种多样，涵盖路径规划、任务调度、多智能体控制等多个领域。
- 支持长期赛和可视化工具等特色。
每次比赛开始时，主办方都会发布一道全新设计的题目。
图2所示即为一道典型路径规划题目。这些任务大多对计算资源要求较高，每个测试用例的运行时间限制通常为2到10秒。
AHC提供两种比赛形式：短期赛（持续约4小时）和长期赛（为期1～2周）。
两者在题目设计和挑战难度上存在显著差异。
短期赛的问题有时可以通过模拟退火（simulated annealing）、束搜索（beam search）等标准算法来求解；
而长期赛更看重深度分析与反复试验，解法往往靠「磨」出来。
图3展示了比赛过程中选手得分逐步提升的过程。
图3：AHC中的长期赛中，得分上升
在为期两周的AHC014竞赛中，图3展示了每个时间点上特定排名的得分显示出持续的进步。
图3中线条颜色，标记了不同的颜色层级，例如，性能perf=2800（第6名）和性能perf=1200（第379名）。
但无论是哪种形式，想要获得高分都要针对问题本身，进行推理与反复调优。
随着比赛推进，选手可以不断提交优化后的解法，从而逐步提升得分。
图4：评级和平均表现分布。截至2025年5月1日，至少参与过5次的用户的累积评级和平均表现分布（背景颜色表示不同的评级层级）
编程新基准：没有最佳答案
为了构建ALE-Bench，在HuggingFace上，研究团队发布了包含40道AHC题目的数据集，这些题目均来自截至2025年4月底前举办的正式比赛。
数据集：https://huggingface.co/datasets/SakanaAI/ALE-Bench/tree/main
这个数据集被称为完整版（full version），还额外提供了一个精简版（lite version），其中精选了10道具有代表性的题目，方便快速评估和测试。
每道题目的数据包包含四大部分：
- Problem：题目的完整描述，采用Markdown格式，并附带所有相关图示；
- Scorer：用Rust编写的评分程序，用于评估选手提交代码在给定测试用例上的表现；
- Visualizer：基于网页的可视化工具和Rust程序，用于动态展示代码的执行过程，图2中的图像即为其示例；
- Leaderboard：用于计算和展示模型或选手得分排名的参考数据。
ALE-Agent，算法工程设计智能体
在算法工程中，智能体还有多大的发展潜力？
为了初步探讨ALE-Bench所打开的研究空间，这次探索了算法工程领域的特定用途智能体。
该领域具有一些独特特性。
对许多问题类型而言，已有成熟的高层策略，而选择正确的整体方案至关重要。
然而，即使整体思路正确，具体的实现细节、超参数设置和微调优化仍可能显著影响最终结果。
基于这一点，在ALE-Agent原型中，研究团队提出并实现了两种技术：
方法一：结合领域知识的提示策略。
将算法工程中常见技术的专家知识直接嵌入提示词中，例如模拟退火（simulatedannealing）和束搜索（beam search）。提示内容涵盖搜索空间和评估函数的设计、邻域生成方式，以及常用的加速技巧。
方法二：注重多样性的解空间搜索。
研究者采用基于最优优先搜索（best-first search）的方法，利用大语言模型（LLM）生成并优化解的候选项。
为避免过早丢弃有潜力的解路径，在算法中加入类似束搜索的扩展策略，使每个节点能一次性生成多个子节点。
这种宽度扩展有助于保留高潜力假设，并在实际操作中，通过并行生成候选方案有效减少API延迟，尤其在使用大型推理模型时优势明显。
具体见附录B。
研究团队让ALE-Agent参加了两次实时竞赛（AHC046和AHC047），与超过1000名人类参赛者遵守相同规则竞争。
结果如下：
AHC046：排名第154（前16%）。
AHC047：排名第21（前2%），表现尤为出色。
ALE-Bench上的评估结果
研究团队在ALE-Bench上对更广泛的组合优化问题进行了评估。
除了ALE-Agent，还测试了其他最先进的AI模型，这些模型在4小时内通过自我优化持续改进解决方案（见上图）。
使用标准优化方法的AI模型，表现大致相当于人类参赛者的前50%，而ALE-Agent的表现达到了前6.8%，显示出显著的性能提升。
完整实验设置和结果请参阅论文。
分析与洞察
在识别复杂优化问题的算法改进方面，ALE-Agent训练得很有竞争力。
更进一步，研究者还观察了它在算法改进中的表现。
观察迭代优化过程时，研究人员发现它经常应用领域知识来提升得分。
例如，它会加速搜索算法和微调超参数，就像该领域的顶尖人类专家一样。
在AHC047实时竞赛中，ALE-Agent取得了前2%的成绩。
以下是一些迭代创新的例子：加速分数计算和改进邻域搜索。
ALE-Agent使用泊松分布近似来加速分数计算，这是提升AHC047得分的关键策略（代码见此处，第254-276行）。
ALE-Agent为模拟退火算法设计了更高效的邻域搜索策略，通过引入更多样化的移动方式，扩展了解决方案空间的探索，最终将其排名从第82提升至第21（初始代码见此处，第304-342行；最终代码见此处，第492-771行）。
ALE-Agent为何能在AHC047中名列前茅？
其中关键原因是人类与AI解决问题方式的差异。
在4小时的比赛中，人类最多可能优化代码十几次，而当前AI能进行大约100次修订。
此外，ALE-Agent能生成数百甚至数千个潜在解决方案。
这种高速、并行的生成能力，让AI在短时限比赛中展现出独特优势。
图5：迭代优化过程中公开分数与代码文件大小的变化趋势。该图表展示了四小时周期内，生成代码文件大小与对应公开评估分数的同步演变过程。图中右侧的点位表示更晚的时间节点
研究者还发现，当前AI非常擅长使用模拟退火，这是AHC中常用的算法（例如，ALE-Agent在AHC039的最佳解决方案，如果参加实际比赛将排名第5）。
未来工作
尽管取得了成功，ALE-Agent仍有一些局限性：
- 调试困难：ALE-Agent有时无法修复代码中的错误。
- 时间超限：它无法正确分析自身代码的复杂度，导致多次超出时间限制。
- 优化误区：它有时执着于改进对得分贡献不大的代码部分。
虽然ALE-Agent在4小时比赛和适合模拟退火的问题上表现良好，但在为期两周的比赛或需要不同类型算法的问题上表现不佳。
它在基于实验分析设计算法（需要通过观察程序行为进行试错）时也显得吃力。
未来改进方向包括：
更可靠的优化：通过融入人类专家使用的更多技术和工具，以及增强反馈机制以支持详细的执行结果分析。
智能体技术升级：例如结合自我改进的方法，使智能体能够不断提升自身能力。
最终目标是打造一个算法工程能力媲美甚至超越顶尖人类算法工程师的AI。
参考资料：
https://sakana.ai/ale-bench/
https://x.com/hardmaru/status/1934767617895747862
本文来自微信公众号“新智元”，编辑：KingHZ ，36氪经授权发布。
