Transformer八子初創：AI橫掃NP難題競賽，Top 2%選手竟是智能體！
物流路徑選擇、人員排班、工廠調度、電網平衡、旅行路線……
這些貼近現實的優化任務，看似日常，實則難度極高。
難點在于：一旦問題規模擴大，傳統算法幾乎無法計算出最優解。
通常只能依賴啟發式或近似算法來接近答案。
這正是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。
