🤖 AI

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

本論文は、コストのかかるLLM推論を階層的なワールドモデルとUCB1ベースの木探索に置き換えることで、多様で複雑なタスクにおいて100%の成功率と決定論的かつゼロコールでのプランニングを実現し、LATSやReActといった既存の手法を大幅に凌駕するプランニングフレームワークであるGATSを導入するものである。

原著者： Maureese Williams, Dymitr Nowicki

公開日 2026-07-13

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

CC BY 4.0

原著者： Maureese Williams, Dymitr Nowicki

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

あなたは、巨大でトリッキーな迷路を解こうとしているところだと想像してください。あなたには、進むべき方向を提案してくれる超スマートな友人（大規模言語モデル、またはLLM）がいます。しかし、ここには一つ問題があります。あなたが友人に助言を求めるたびに、彼らは考えるために長い昼寝をしなければならず、しかも同じ質問をしても、毎回異なる推測をすることがあります。もし迷路に行き止まりがあったり、長い一連の方向転換が必要だったりする場合、ステップごとに友人に助けを求めるのは、コストがかかり混乱を招きます。

これが、研究者のモーリース・ウィリアムズとディミトリー・ノウィキが、新しいシステムであるGATS（Graph-Augmented Tree Search：グラフ拡張型ツリー探索）で解決した問題です。彼らは、この迷路を極めて効率的にナビゲートする方法を見つけ出し、その結果、超スマートな友人をほとんど起こす必要さえなくなりました。

旧来の方法：「一歩ごとに尋ねる」アプローチ

ReActやLATSといった従来の手法は、道が分かれるたびにガイドに立ち止まって「どちらに進めばいいですか？」と尋ねるハイカーのようなものでした。

ReActは、一度だけ尋ねてそのまま進みます。高速ですが、しばしば行き止まりに突き当たります。彼らのテストでは、この手法はトリッキーな迷路のシナリオにおいて**64%**の成功率しか示せませんでした。
LATSはより賢いです。ガイドに尋ね、次に進むべきステップについて再び尋ね、さらに次へと、可能性のツリー（木構造）を構築していきます。しかし、ツリーのすべての枝に対してガイド（LLM）に尋ねるため、ガイドは疲れ果て、コストもかさみます。テストにおいて、LATSは92%の成功率を記録しましたが、タスクごとにガイドに対して37回も呼び出しを行いました。さらに、ガイドは時としてランダムに推測するため、同じ迷路を二度試すと異なる経路になる可能性があります。

新しい方法：GATS（「地図作成者」戦略）

GATSはゲームのルールを変えます。あらゆる曲がり角でガイドに尋ねる代わりに、GATSは階層型ワールドモデルを使用して、独自の内部地図を構築します。この地図には、3つの層の知識があると考えてください。

第1層（正確なルールブック）： システムがすでに完璧に把握しているアクション（例：「このボタンを押せばドアが開く」）については、シンプルで即座に確認できるチェックを行います。思考は不要です。これは「2+2は常に4である」と知っている状態と同じです。
第2層（経験ログ）： アクションが以前に起きたことは知っているものの、完璧なルールを持っていない場合、システムは過去の旅のダイアリー（日記）をチェックします。「前回これをやった時は、10回中9回うまくいった」といった具合です。これは推測ではなく、データから学習されたものです。
第3層（超天才の友人）： システムが全く新しい、未知の事象に遭遇したときにのみ、LLMガイドを起こします。しかし、ここが魔法の部分です。ガイドが回答すると、GATSはその回答を地図に書き込みます。次に同じ状況が発生したとき、GATSはただ地図を見るだけです。二度とその特定の事柄についてガイドに尋ねることはありません。

結果：スピード、確実性、そして成功

研究者たちは、分岐する経路や行き止まりがあるように設計された、トリッキーな100の合成プランニング・タスクを用いてテストを行いました。

GATSは**100%**の成功率を達成しました。
LATSは**92%**でした。
ReActは**64%**でした。

しかし、本当の驚きはここにあります。GATSは、これらのタスクの実際のプランニング中にLLMへの呼び出しをゼロにしました。GATSは、自身の地図とルールを用いてすべての思考を行いました。LLMのランダムな推測に依存しなかったため、GсяTSは実行するたびに全く同じ完璧な計画を生み出しました。分散（バラつき）はゼロでした。

彼らはまた、コーディングのワークフロー、航空券の予約、複雑な迷路のナビゲーションなど、12の困難なカテゴリーにわたる120のタスクを用いた大規模な「ストレス・テスト」も実施しました。

GATSは依然として**100%**の成功率を維持しました。
LATSは**88.9%**に低下しました。
ReActは**23.9%**へと崩れ落ちました。

なぜ機能するのか（秘伝のソース）

論文によれば、GATSが勝利したのは、ランダムな推測ではなく系統的な探索（UCB1と呼ばれるもの）を使用しているからです。直感に従うのではなく、あらゆる手がかりを秩序立ててチェックする探偵を想像してください。

系統的 vs ランダム： LATSは、どのパスが良さそうかをLLMの「勘」に頼ります。もしLLMの「勘」が外れれば、計画全体が失敗します。GATSはすべての選択肢を系統的にチェックするため、ガイドの調子が悪いという理由だけで正しいパスを見逃すことがありません。
決定的 vs 確率的： GATSはほとんどのステップで独自の地図を使用するため、結果は常に一定です。LLMに依存しているLATSは、同じタスクを二度実行すると異なる答えを出すことがあります。

これが意味すること（および、意味しないこと）

著者たちは、彼らの成功の限界についても非常に明確に述べています。これらの結果は、ゲームのルール（「アクション仕様」）があらかじめ分かっているシミュレーションおよび合成タスクに基づいています。これらの制御された環境において、GATSはチャンピオンです。

しかし、論文では、GATSが現在あらゆるものに対する魔法の杖であるという考えを明確に否定しています。もしGATSを、ルールも過去のログも学習するものもない、完全に予測不能でオープンエンドな世界に放り込んだとしたら、LLMに頼らざるを得なくなり、速度と効率が低下するでしょう。著者らは、GATSが現実世界で輝くためには、まずより優れた地図（ワールドモデル）を構築する必要があると示唆しています。おそらく、人間が実際にツールをどのように使用しているかのログから学習することによってです。

要約すると、この論文は、ルールを定義できるプランニング・タスクにおいては、あらゆるステップで超スマートなAIに助けを求める必要はないということを示しています。私たちは、複雑な問題を100%の成功率、ゼロのコスト、そしてゼロの混乱でナビゲートすることを可能にする、スマートで自己更新型の地図を構築できるのです。

技術要約: GATS (Layered World Modelsを用いたGraph-Augmented Tree Search)

問題提起

大規模言語モデル（LLM）エージェントは、マルチステップの計画策定やツール利用において潜在能力を示しているが、ReActやLATS (Language Agent Tree Search) といった既存の手法は、以下の2つの決定的な限界に直面している：

計算コスト: 既存の手法は、計画の各ステップや探索ノードにおいて高価なLLM推論に依存しており、高いレイテンシとリソース消費を招いている。
確率性: LLMのサンプリングは分散を導入するため、計画の再現性が失われ、実行ごとにパフォーマンスが不安定になる。

核心となる課題は、LLMの推論能力を維持しつつ、状態予測のための推論時LLM呼び出しを排除し、決定論的で効率的かつスケーラブルなエージェント計画を実現するフレームワークを開発することである。

手法: GATS フレームワーク

著者らは、世界モデル（World Model）とLLMをデカップリング（分離）した計画アーキテクチャである GATS (Graph-Augmented Tree Search) を提案している。GATSは、体系的なUCB1ベースの木探索と、階層型世界モデル (Layered World Model) および永続的な 状態遷移グラフ (State-Transition Graph) を組み合わせたものである。

1. 階層型世界モデル ( $W$ )

世界モデルは、現在の状態 ( $s$ ) とアクション ( $a$ ) が与えられたとき、次の状態 ( $s'$ ) と確信度 ( $p$ ) を予測する。これは、汎用性と計算コストが増加する順に、以下の3つのレイヤーを順次クエリする：

L1 (記号的/Symbolic): 既知のSTRIPS形式の仕様を持つアクションに対する、前提条件と効果の正確なマッチング。このレイヤーは、最小限の計算コストで決定論的な予測 ( $p=1.0$ ) を提供する（記号的なルックアップ）。
L2 (学習された統計/Learned Statistics): 実行ログから導出された統計的予測。実行中に観察されたが形式的な仕様を持たないアクションに対して、最も頻度の高い効果を、確信度 $p = \min(\text{count}(a)/10, 1.0)$ とともに返す。
L3 (生成型/LLM/Generative): 真に新規または曖昧なアクションに対するLLMベースの予測。極めて重要な点として、L3からの予測はキャッシュされ、同じ遷移に対する繰り返しの推論呼び出しを回避する。

システムはL1およびL2を優先してカバレッジを最大化し、L3の呼び出しは必要最小限に留める。これにより、LLMのコストを「ステップごとの推論要件」から「一度限りのブートストラップ・コスト」へと変え、コストを「償却（amortize）」させている。

2. 永続的な状態遷移グラフ

従来の木探索が各ノードを独立して展開するのに対し、GATSは、ノードが標準的な状態キー $k(s)$ を表す明示的なグラフ $G = (V, E)$ を保持する。

状態の統合 (State Merging): 異なるアクションシーケンスが同じ状態に到達した場合、それらは単一のノードに統合される。これにより、パスを超えて遷移予測、訪問回数、および価値推定を再利用することが可能になる。
永続性 (Persistence): グラフは計画ステップを超えて保持される。アクションが実行された後、計画は探索を最初からやり直すのではなく、対応するグラフノードから再開される。これにより、エピソード全体にわたって価値推定と探索統計が償却される。
デッドエンド検出 (Dead-End Detection): ゴールへの経路が存在しないノードはデッドエンドとしてマークされ、プランナーがその領域へ導くアクションに対して低い値を割り当てることを可能にする。

3. UCB1ベースの探索

GATSは、グラフのエッジに対してUCB1（Upper Confidence Bound）選択戦略を採用している。

アクション選択: 各状態において、アルゴリズムは $Q(s, a) + c\sqrt{\frac{2 \ln N(s)}{N(s, a)}}$ を最大化するアクション $a$ を選択する。これにより、高価値なパスにコミットする前に、適用可能なすべてのアクションを体系的に探索することが保証される。
価値推定: 状態の価値は、BFS（幅優先探索）ベースのヒューリスティックを用いた、ゴールへの最短予測距離 ( $d_G$ ) から導出される： $StateValue(s) = \frac{\alpha}{d_G(s, G) + 1}$ 。
確信度の統合: バックアップ値には世界モデルの確信度が組み込まれる： $v = p \cdot StateValue(s') - \lambda(1-p)$ 。これにより、不確実な予測に対してペナルティを与える。

主な貢献

階層型世界モデル・アーキテクチャ: 効率的な状態予測を可能にし、LLMへの依存を最小限に抑える、記号的、学習的、および生成的なコンポーネントの斬新な統合。
グラフメモリを備えた体系的なUCB1探索: 探索のエビデンスを再利用し、決定論的な結果を保証するために、永続的なグラフを活用することで、ランダムなLLM誘導探索を凌駕する計画アルゴリズム。
包括的な評価: コーディング、ウェブナビゲーション、および長期ホライゾン（long-horizon）シナリオをカバーする100の合成計画タスクと12カテゴリのストレス・テスト（120タスク）による広範な検証。
計画中のLLM呼び出しゼロ: GATSが、計画フェーズ中にゼロのLLM呼び出しで100%の成功率を達成できることを実証した。これは、タスクごとに数十回の呼び出しを必要とするベースラインとは対照的である。

実験結果

合成計画タスク (100タスク)

成功率: GATSは予算 $b=10$ において**100%**の成功を収め、LATS (92%) や ReAct (64%) を上回った。
効率性: GATSは計画中のタスクあたりのLLM呼び出しが0回であったのに対し、LATSは約37回を必要とした。
決定論: GATSはランダムシード間で**分散0%**の計画を生成したが、LATSとReActはLLMの確率性により1〜5%の分散を示した。
最適性: GATSはオラクル（Oracle）と一致する1.00の最適性比を達成した。

ストレス・テスト (12カテゴリ、120タスク)

ストレス・テストには、コーディング・ワークフロー、ウェブナビゲーション、深いホライゾン、および不可逆的な意思決定（デッドエンド）などの困難なシナリオが含まれた。

全体的なパフォーマンス: GATSはすべてのカテゴリで**100%**の成功率を維持した。
比較パフォーマンス: LATSは全体で**88.9%に低下し、特にコーディング (63.3%)、ウェブナビゲーション (63.3%)、およびディープホライゾン (63.3%) のタスクで苦戦した。ReActは23.9%**という壊滅的な失敗を示した。
具体的な改善: GATSは、LATSと比較して、コーディング、ウェブナビゲーション、およびディープホライゾン・タスクにおいて最大の改善（+36.7%）を示した。

アブレーション研究

探索予算 (Search Budget): パフォーマンスは予算 $b=10$ で飽和し、それ以上増やしても収穫逓減が見られた。
世界モデルのレイヤー: L1またはL3を個別に削除しても、L2が十分なカバレッジを提供できる合成タスクにおいては成功率に影響を与えず、システムの緩やかな劣化（graceful degradation）が検証された。オープンドメインの投影においては、L3（LLM）が新規アクションの約10%を処理することが期待される。

意義と主張

本論文は、体系的な探索と学習された世界モデルの組み合わせが、LLM誘導型の探索を大幅に上回ることができると主張している。GATSの主な意義は、以下の点にある：

推論時のLLMコストの排除: 予測をキャッシュし、記号的・学習的レイヤーに依存することで、GATSは繰り返されるLLM呼び出しの計算上のボトルネックを取り除く。
再現性の確保: 階層型世界モデルとUCB1探索の決定論的な性質により、LLMサンプリングに固有の確率的な分散を排除する。
複雑な計画への対応: 本フレームワークは、純粋なLLMベースの手法（ReAct）やLLM重視の木探索（LATS）が失敗または低迷する、分岐するパス、デッドエンド、および長期的な依存関係を伴うシナリオを正常にナビゲートできる。

著者らは、GATSを、アクションのセマンティクスを形式化できる領域（例：API、構造化されたツール利用）において最適化されたソリューションとして位置づけており、より効率的で信頼性の高い自律エージェントへの道筋を提示している。未知のアクション効果を持つオープンエンドな領域では、L3レイヤーへの依存度が高まり、効率性の優位性は減少するものの、完全に消失することはないと認めている。