💬 NLP

PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs

PathWise は、含意グラフ上の状態認識型逐次意思決定タスクとしてプロセスを定式化することにより、組合せ最適化のための自動化されたヒューリスティック設計を強化する新規マルチエージェントフレームワークであり、これにより近視眼的な試行錯誤を戦略的計画と自己進化的推論に置き換えて、より速い収束と優れた汎化を実現する。

原著者： Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

公開日 2026-05-26

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

以下は、PathWise 論文の解説を、創造的なアナロジーを用いた平易な言葉で翻訳したものです。

全体像：ロボットにより優れたルールを発明させる

あなたが巨大で散らかったパズル（100 の都市を訪れる最短経路を見つける必要がある配送ドライバーの「巡回セールスマン問題」のようなもの）を持っていると想像してください。これを解くために、人間は通常、コンピュータに次の都市をどう選ぶかを指示する「ルール」（ヒューリスティック）を書きます。

長らく、コンピュータはこれらのルールを自動的に作成しようと試みてきました。その際、エッセイやコードを書くのと同じ種類の AI である**大規模言語モデル（LLM）**が用いられてきました。しかし、従来の手法は、シェフが鍋に材料をランダムに投げ入れ、味見をして、うまくいくことを願うようなものでした。それらはしばしば過ちを繰り返したり、以前に何が機能したかを忘れたり、同じ悪いアイデアを何度も試して行き詰まったりしました。

PathWiseは、このプロセスを変える新しいシステムです。ランダムな推測の代わりに、それはより良いルールを素早く設計するために、自らの思考プロセスの地図を構築する賢く、自己反省的な建築家のように振る舞います。

核心的な問題：過去の AI の「記憶喪失」

この論文は、これらのルールを設計するための従来の AI 手法には、主に 2 つの欠陥があったと主張しています。

過去を忘れること：それらは、過去の失敗から学んだ教訓を無視し、すべての新しい試みを初めてのことであるかのように扱いました。
盲目であること：それらは、ルールがなぜ機能したのか、あるいは失敗したのかを理解していませんでした。最終的なスコアしか見ていなかったのです。

これにより、「近視眼的（視野が狭い）」な結果が生じ、AI は同じ悪いアイデアを再発見する時間を浪費することになりました。

解決策：PathWise（「世界モデル」アプローチ）

PathWise は、設計プロセスをセーブ機能付きのビデオゲームのように扱うことで、この問題を解決します。それは**含意グラフ（Entailment Graph）**と呼ばれる特別な構造を使用します。

含意グラフをアイデアの系図のように考えてください。

ノード（人物）：各ノードは、AI が作成した特定のルール（ヒューリスティック）です。
エッジ（関係性）：それらを結ぶ線は、あるルールがどのように別のルールから作成されたかを示します。AI は 2 つのアイデアを組み合わせましたか？それとも 1 つを微調整しましたか？
記憶：このグラフは完全な履歴を記憶しています。「ルール B」は「ルール A」のわずかな改良であり、「ルール C」は交通パターンを無視したために失敗したことを知っています。

仕組み：3 人のエージェント・チーム

PathWise は 1 つの AI だけを使うのではなく、映画制作クルーのように連携する 3 つの専門エージェントのチームを使用します。

1. 監督（ポリシーエージェント）

役割：このエージェントは「系図（グラフ）」を見て、次の動きを決めます。
行動：どの過去のルールを親として使うかを選び、次のエージェントにそれらをどう組み合わせるかを指示する「脚本（ディレクティブ）」を書きます。
アナロジー：ストーリーボードを見て、「シーン 3 の照明とシーン 5 のカメラアングルを取り入れつつ、もっと暗くしよう」と監督が言うようなものです。

2. 俳優（世界モデルエージェント）

役割：このエージェントは監督の脚本を受け取り、実際にコード（新しいルール）を書きます。
行動：指示に基づいて、実際のコンピュータプログラムを生成します。
アナロジー：脚本を読み、シーンを演じる俳優です。監督のビジョンを具現化しようとします。

3. 批評家（クリティックエージェント）

役割：これらのエージェントはパフォーマンスを見守り、フィードバックを与えます。
行動：新しいルールを古いルールと比較します。新しいルールが優れていれば、「よくやった、その調子で続けろ」と監督に伝えます。劣っていれば、「その照明は暗すぎた。別のことを試せ」と言います。
アナロジー：これらは映画評論家と監督の助手です。単に「良い」か「悪い」かと言うだけでなく、監督が次の脚本を改善できるよう、なぜそうなのかを説明します。

秘密の武器：「状態認識型」計画

PathWise の魔法は、現在のスコアだけを見るのではなく、旅全体を見る点にあります。

従来の方法：「これを試したが失敗した。全く違うことを試そう。」
PathWise の方法：「これを試したが失敗した。次の都市までの距離を無視していたからだ。また、あれも試したが、それはうまくいった。2 回目の試みからの距離ロジックと、1 回目の試みからの速度ロジックを組み合わせてみよう。」

この「状態を保持する記憶」を保つことで、PathWise は過ちを繰り返すことを避け、成功の上に築き上げ、より迅速な収束（最良の解決策への到達）を実現します。

結果：より速く、より賢く

この論文は、トラックのルート設定、箱詰め、巡回セールスマン問題など、さまざまな複雑なパズルに対して PathWise をテストしました。

速度：PathWise は、他の手法よりも少ない試行回数でより良い解決策を見つけました。「ゴールライン」に早く到達しました。
品質：それが発明したルールは、人間や他の AI 手法によって作られたものよりも優れていました。
汎用性：それは異なる種類の AI モデル（「バックボーン」）や、さまざまな規模の問題に対してうまく機能しました。

要約のアナロジー

完璧なサンドイッチを発明しようとしていると想像してください。

従来の AI：サンドイッチを作り、食べて、もしまずければ捨てて、何を加えたかの記憶もなく、完全にランダムな新しいものを作ります。
PathWise：レシピジャーナルを維持します。サンドイッチを作るたびに、何をしたかを正確に書き留めます。まずければ、ジャーナルを読み、塩を入れすぎたことに気づき、それを記録します。次に、あなたは「批評家」にジャーナルをレビューさせ、「単に推測するのではなく、火曜日の低塩レシピを使い、月曜日のチーズを加えなさい」と言われます。

PathWise は、その賢いレシピジャーナルシステムであり、AI が複雑な問題に対するより良い解決策を発明するために、自らの歴史から学ぶことを可能にします。

技術概要：PathWise

問題定義

自動ヒューリスティック設計（AHD）は、組合せ最適化問題（COP）に対するヒューリスティックアルゴリズムを自動生成し、手動による専門家設計への依存を軽減することを目的としている。大規模言語モデル（LLM）が最近、進化探索プロセスに統合されることで AHD を可能にしてきたが、既存のフレームワークは重大な限界を有している。集団ベースの手法は、しばしば固定された進化則と静的なプロンプトテンプレートに依存しており、視野の狭いヒューリスティック生成、冗長な評価、および早期収束を引き起こす。モンテカルロ木探索（MCTS）を用いる木ベースの手法は、探索ランドスケープのセマンティックな理解ではなく、性能統計に駆動された階層的構造を課す。決定的なことに、現在の手法は、ヒューリスティックがどのように導出されるか、編集が世代間でどのように伝播するか、あるいはなぜ修正が成功または失敗するかについての状態を保持するセマンティックな表現を欠いている。その結果、LLM 呼び出しの非効率的な利用と、過去の決定を効果的に引き継げないという事態を招いている。

手法

著者は、PathWise（自己進化型 LLM による自動ヒューリスティック設計のための世界モデルを通じた計画）を提案する。これは、ヒューリスティック生成を含意グラフ上の逐次決定プロセスとして定式化する、新規のマルチエージェント推論フレームワークである。このグラフは、探索軌跡のコンパクトで状態を保持するメモリとして機能する。

中核コンポーネント

含意グラフ（ $G = (V, E)$ ）:
- 標準的な進化木や集団とは異なり、含意グラフは導出履歴を符号化する。
- ノード（ $v$ ）: ヒューリスティックコード（ $h$ ）、自然言語による導出根拠（ $\kappa$ ）、アルゴリズム記述（ $d$ ）、性能指標（ $P(h; D)$ ）、および親メタデータ（$PM$）を含むタプルを表す。
- エッジ（ $E$ ）: 親セットを子ノードに接続し、親から子を導出するために使用された特定の根拠を符号化する。
- この構造により、システムはステップを孤立したサンプリング事象として扱うのではなく、導出履歴に基づいて将来の決定を条件付けることができる。
マルチエージェントシステム:
フレームワークは、2 つの時間スケール（外部集団更新と内部含意ステップ）にわたる計画、実行、反省の協調サイクルを通じて動作する。
- ポリシーエージェント（ $\pi_p$ ）: 高レベルのプランナーとして機能する。現在の状態（含意グラフのフロンティア）を観察し、選択された親ノードのタプル（ $S$ ）と自然言語による導出根拠（ $\kappa$ ）で定義されたアクションを提案する。これにより、ポリシーは固定テンプレートに依存するのではなく、動的に新しい演算子タイプを考案できる。
- 世界モデルエージェント（ $\pi_{wm}$ ）: 低レベルの実行者として機能する。選択された親と指示に基づき、ポリシーの高レベルアクションを実行可能なヒューリスティックコード（ロールアウト）に変換する。
- クリティックエージェント:
  - ポリシークリティック（ $\pi_{p\_critic}$ ）: ポリシーアクション（親選択と指示）の結果を分析し、将来の進化戦略を導くためのルーティングされた反省を提供する。
  - 世界モデルクリティック（ $\pi_{wm\_critic}$ ）: 最良および最悪の性能を示すヒューリスティックロールアウトを比較し、コード合成の質に関するフィードバックを提供して、世界モデルがアルゴリズム構造と効率を洗練させるよう導く。
探索プロセス:
- 外部ループ: 根ノードの集団を維持する。
- 内部ループ: 現在の集団を根とする含意グラフを段階的に構築する。各ステップで、システムは複数のアクションとロールアウトをサンプリングし、結果として得られる最良のノードを選択してグラフを更新する。
- 多様性メカニズム: 低多様性の出力を防ぐため、PathWise はプロンプトレベルの多様性（探求的なフレーズでプロンプトを攪乱する）と状態シャッフル（位置バイアスを緩和するためにノード順序をランダム化する）を採用する。

主要な貢献

ハイブリッドグラフ・集団定式化: 著者は、導出根拠と性能履歴を符号化する含意グラフを導入し、ポリシーと世界モデルの相互作用のための共有状態として機能させる定式化を提案する。
協調型マルチエージェントフレームワーク: ポリシーエージェントが進化戦略を制御し、世界モデルがコード生成を実行し、クリティックエージェントがルーティングされた反省を提供するシステム。これにより、LLM パラメータの更新なしに、自己進化し状態を認識するヒューリスティック生成が可能となる。
プロンプトレベルの多様性: 親選択とヒューリスティックロールアウトの多様性を確保するためのメカニズムにより、含意グラフ上でのより広範な探索を可能にする。
実証的検証: 多様な COP において、PathWise がより少ない評価で強力なヒューリスティックを発見し、より速く収束し、より大きな問題サイズに対して効果的にスケーリングすることを示す広範な実験。

実験結果

PathWise は、巡回セールスマン問題（TSP）、ナップサック問題（KP）、容量制約付き車両経路問題（CVRP）、多重ナップサック問題（MKP）、オリエンティアリング問題（OP）、およびビンパッキング問題（BPP）を含む複数の NP 困難な COP 上で評価された。このフレームワークは、ステップバイステップ構築、蟻群最適化（ACO）、およびガイド付き局所探索（GLS）の 3 つの探索パラダイムでテストされた。

性能: PathWise は、最先端の LLM ベースの AHD ベースライン（FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD）および手動設計されたヒューリスティックを常に上回った。ドメイン内およびドメイン外のテストセットの両方で、最適性ギャップが低く抑えられた。
効率性: PathWise は、より良いヒューリスティックへより速く収束した。いくつかの実験において、PathWise は 500 回のみで優れた性能を達成したのに対し、ベースラインは 1000 回まで許容されていた。
スケーラビリティ: この手法は、より大きな問題サイズ（例： $N=200$ の TSP、 $N=500$ の KP）および異なる LLM バックボーン（GPT-4o-mini、GPT-5-nano、さまざまな推論レベル）に対して強力な一般化を示した。
アブレーション研究: クリティックエージェントまたは多様性メカニズムを除去すると性能が著しく低下し、状態を認識するフィードバックと探索の必要性が確認された。

意義と主張

本論文は、PathWise が「試行錯誤的な進化」から「推論を通じた状態認識型計画」への転換を表すと主張している。ヒューリスティックの発見を含意グラフ上の逐次決定プロセスとして扱うことで、システムは過去の決定を引き継ぎ、世代間で導出情報を再利用または回避することができる。

著者は、PathWise が LLM パラメータを更新しないという意味でトレーニングフリーであることを強調している。代わりに、自然言語による反省を通じて強化された LLM の事前学習済み知識を活用する。その意義は、探索プロセスの構造化されたメモリを提供することで既存の AHD 手法の視野の狭さを克服し、冗長な評価を削減するとともに、複雑な組合せ問題に対する高品質なヒューリスティックのより効果的な発見を可能にする点にある。この研究は、導出履歴に対する構造化された推論が、LLM ベースの自動アルゴリズム設計をスケーリングするための重要な要素であることを示唆している。