💬 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. 問題点：「クイズ番組」対「実際の仕事」

現在のAIテストは、多肢選択式のクイズのようなものです。

問題点: もしAIに、学習データの中に既にある数学の問題を出せば、彼らはA+（満点）を取ります。しかし、もし「新しいタイプ」の問題を出されたら、彼らはしばしばフリーズしてしまいます。それは、数学の本質を理解していないのに、解答集を丸暗記した学生のようなものです。
従来の方法: 一部のテストでは、特定のチェックをパスするコードを書かせます。しかし、これらはあまりに単純すぎたり、正解が一つしかなかったりすることが多いのです。
新しい方法 (HeuriGym): HeuriGymは、AIにクイズを出すのではなく、指示書のない複雑な建設プロジェクトを与えるようなものです。目標は単に「テストに合格すること」ではなく、効率的に機能する機械を「作り上げること」です。

2. 挑戦：「組合せ最適化」のパズル

この論文は、**組合せ最適化（Combinatorial Optimization）**と呼ばれる特定の難解な問題に焦点を当てています。

比喩: あなたが物流マネージャーで、1,000台の配送トラックのスケジュールを立てようとしていると想像してください。ガソリンを最小限に抑え、かつ時間通りに到着するように、すべてのトラックの最適なルートを考え出さなければなりません。
難関: 可能なルートの数は、宇宙の原子の数よりも多いのです。すべてをチェックすることは不可能です。あなたは「ヒューリスティック（発見的）」な天才にならなければなりません。つまり、数学的に完璧ではなくても、素早く良い解を見つけ出すための、巧妙なショートカットや「経験則」を編み出す必要があるのです。

3. 設定：「エージェンティック・ループ（Agentic Loop）」

HeuriGymは、単にAIにコードを一度書かせて採点するだけではありません。ビデオゲームの「リスポーン（復活）」のように、フィードバック・ループを設定しています。

プロンプト: AIは問題の説明を受け取ります（例：「これらの電子回路をできるだけ高速に動作するようにスケジューリングせよ」）。
試行: AIは問題を解くためのプログラム（ヒューリスティック）を記述します。
現実の検証: システムはそのコードを実行します。
- クラッシュしたか？（構文エラー）
- ルールに違反したか？（制約違反）
- 実行速度が遅すぎたか？（タイムアウト）
フィードバック: システムはAIに対し、「存在しないライブラリを使用しようとしています」や「あなたの解法は制限時間を超えています」といった情報を伝えます。
再試行: AIはそのエラーを読み取り、そこから学び、間違いを修正するためにコードを書き直します。

このサイクルを繰り返すことで、AIは人間エンジニアが行うように、試行錯誤を通じて問題の解き方を「学習」していくことができます。

4. スコアカード：「品質収益指数（Quality-Yield Index: QYI）」

新しい解法を編み出そうとしているロボットを、どのように採点すればよいでしょうか？著者らは、QYIという新しいスコアを作成しました。

収益（Yield）: ロボットはクラッシュすることなく、実際に仕事を完了できましたか？（動作する解を得られましたか？）
品質（Quality）: その解は、人間の専門家と比較してどの程度優れていましたか？
スコア: スコアが 1.0 であれば、ロボットが人間の専門家と全く同等のパフォーマンスを発揮したことを意味します。スコアが 0 であれば、完全に失敗したことを意味します。

5. 結果：「現実の検証」

著者らは、利用可能な最もスマートなAIモデルのうち9つ（GPT-o4-miniやGemini-2.5-Proなど）をテストしました。

判定: 最も「賢い」モデルでさえ、スコアは0.6程度しかありませんでした。
これが意味すること: 最良のAIモデルであっても、これらのタスクにおいて人間の専門家の60%程度の有効性しか持っていません。彼らはコードを実行させることはできますが、人間が設計した解決策を打ち負かすほど「効率的」または「創造的」なコードを書くことには苦戦しています。
苦戦の理由: モデルはしばしばループに陥ったり、ハルシネーション（幻覚）を起こして架空のコンピュータライブラリを捏造したり、あるいは複雑な制約条件を理解できなかったりします。彼らは指示に従うことは得意ですが、新しい戦略を編み出すために「既成概念にとらわれない思考（think outside the box）」を行うことは苦手なのです。

6. なぜこれが重要なのか

論文は、AIのテストを単純なクイズから、現実のエンジニアリング上の課題へと移行させる必要があると主張しています。

目標: AI開発を、単にパターンを暗記するだけでなく、科学やエンジニアリングのために真に推論し、適応し、新しい解決策を発明できるモデルへと押し上げることです。
結論: 私たちは、この進歩を測定するための強力なツール（HeuriGym）を作り上げました。現在、AIは有望な「見習い」ではありますが、複雑な現実世界の最適化問題において、まだ「熟練した職人」には到達していません。

要約すると: HeuriGymは、AIロボットが不可能なパズルを解くための「道具」を自ら作り上げるためのジムです。彼らは向上していますが、依然として多くの間違いを犯しており、人間の専門家のレベルにはまだ達していません。

技術要約：HeuriGym：組合せ最適化におけるLLMが作成するヒューリスティックのためのエージェンティック・ベンチマーク

問題提起

現在の大規模言語モデル（LLM）の評価手法は、その問題解決能力を評価する上で二重の危機に直面している。第一に、正解に基づく客観的ベンチマーク（例：AIME、HumanEval）は、データ汚染や性能の飽和に対して脆弱な閉じた問いに依存しており、解が唯一ではなく事前定義されていない実世界のシナリオを反映できていない。第二に、判定者の好みに基づく主観的評価（例：Chatbot Arena）は、分散が高く、実質的な推論の質よりも表面的な要因を優先してしまうことが多い。

LLMが単なるパターン認識を超え、複雑で反復的なエンジニアリング・ワークフローにおいて、真の問題解決における独創性を示せるかどうかを評価するための決定的なギャップが存在する。具体的には、既存のベンチマークは、膨大な解空間を探索し、厳格な制約を遵守し、実行時のフィードバックに基づいて戦略を適応させる必要がある、組合せ最適化（CO）問題のための新しいヒューリスティックを設計する能力を評価することに苦慮している。

手法

著者らは、組合せ最適化問題のためのヒューリスティック・アルゴリズムを生成、実行、および反復的に洗練させる能力を評価するために設計された、エージェンティック・フレームワークであるHeuriGymを導入する。

フレームワークの概要

HeuriGymは、以下の3つのステージからなるインタラクティブなエージェンティック・ループを通じて動作する。

問題記述： LLMは、自然言語による背景、目的関数と制約の数学的形式化、および特定の入出力ファイル形式を含む構造化されたプロンプトを受け取る。部分的な実装やスケフォールド（足場）を提供する従来のワークとは異なり、Heuriもは関数インターフェースのみを提供し、LLMにデータ構造とアルゴリズムを一から設計させる。
実行と検証： 生成されたコードは、サンドボックス環境内でコンパイルまたは解釈される。ドメイン固有の検証器（Verifier）が、制約充足（例：依存関係の保持）をチェックし、評価器（Evaluator）が最適化目的に基づいてコストを算出する。
反復的な洗練： 少数のデモンストレーション・セットからの実行ログ、検証結果、およびパフォーマンス指標がプロンプトに追加される。このフィードバック・ループにより、LLMはエラーのデバッグ、制約違反の修正、および複数のイテレーションにわたるヒューリスティック戦略の洗練を行うことができる。

ベンチマークの構築

本ベンチマークは、コンピュータシステム、ロジスティクス、計算生物学（例：オペレータ・スケジューリング、テクノロジー・マッピング、航空会社の乗務員ペアリング、タンパク質配列設計）にまたがる9つの組合せ最適化問題で構成されている。

選定基準： メモライゼーション（記憶）のリスクを最小限に抑えるため、文献での露出が限定的な問題（最も引用されている論文でも1,000件未満）を選定した。これらは、明確に定義された自然言語仕様、広大な解空間、およびスケーラブルなデータ・インスタンスを備えている。
データセット： 各問題には、数ショット・プロンプティングおよび反復的洗練のための小さなデモンストレーション・セット（約5インスタンス）と、最終テストのための大きな評価セット（数十のインスタンス）が含まれる。

評価指標

標準的な指標であるPASS@kの限界に対処するため、著者らは以下を提案する：

SOLVEs@i： 制約付きの問題を $i$ 回のイテレーション内で解決する確率を追跡し、3つのステージ（実行（ステージI）、解の生成（ステージII）、検証（ステージIII））を通過する成功を測定する。
品質収益指数（Quality-Yield Index: QYI）： 品質（Quality）（解がエキスパートのベースラインにどれだけ近いか）と収益（Yield）（検証を通過したインスタンスの割合）の調和平均として定義される統一指標。
- $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$ ）

主な結果

著者らは、9つの最先端モデル（GPT-o4-mini-high、Gemini-2.5-Pro、DeepSeek-R1、およびLLaMAのバリアントを含む）をHeuriGymベンチマークで評価した。

パフォーマンス・ギャップ： トップクラスのモデルであっても、エキスパートレベルの性能を達成することに苦戦している。最も優れた性能を示したモデルであるGemini-2.5-Proは、約0.62のQYIスコアを達成したが、これはその解が平均してエキスパートが作成したヒューリスティックの60%程度の効果しかないことを示している。他のモデルは著しく低いスコアとなった（例：LLaMA-3.3およびLLaMA-4-Maverickは0.30未満）。
反復による改善： イテレーション数を増やすことで、パフォーマンスは大幅に向上する。例えば、GPT-o4-mini-highの成功率（SOLVEIII）は、イテレーション1での53.2%からイテレーション10では74.8%へと上昇しており、反復的な洗練の重要性を強調している。
失敗モード： 分析により、存在しないAPIの呼び出し（ハルシネーション）、誤ったアルゴリズム論理、制約の誤解、タイムアウトなどの一般的な失敗タイプが明らかになった。
進化型フレームワーク： 標準的な進化型探索フレームワーク（例：ReEvo、HSEvo）は、ベースラインモデルと比較して性能が悪く、実行フィードバックを効果的に組み込むことができず、イテレーション間でコンテキストが断絶することが多かった。

重要性と貢献

本論文は、主に3つの貢献を主張している：

オープンソースのベンチマーク・スイート： 多段階の推論およびアルゴリズム設計能力を評価する、9つの現実的で影響力の高い組合せ最適化問題のコレクションであり、記憶されたパターンを超えた評価を可能にする。
エンドツーエンドのエージェンティック・フレームワーク： 解の生成、自動検証、および反復的洗練をサポートするシステムであり、高度なプロンプティング技術や進化戦略のテストベッドとして機能する。
経験的な洞察： 現在のLLMは、その推論能力にもかかわらず、複雑で現実的な科学・工学問題に適用される際、ツール利用、プランニング、および適応的推論において持続的な限界に直面していることを明らかにする包括的な研究。

著者らは、HeuriGymを、最適解が小規模なインスタンスに対してのみ実行可能であり、ヒューリスティックの発見が不可欠な領域において、より効果的で現実的な問題解決へとLLMの開発を導くための必要なステップとして位置づけている。このベンチマークは、現在のモデルの能力と、実用的なエンジニアリング・ワークフローの要求との間のギャップを露呈させ、単なるパターンマッチングではなく、真のヒューリスティックの発明が可能なモデルの開発を促すことを目的としている。