LATS: Language Agent Tree Search — 推論、行動、計画を一つのフレームワークに統合

Tree of Thoughtsの次に来るものは何かを考えてきました。推論のステップを探索できるのであれば、なぜ行動も探索しないのでしょうか？ それこそがLATS (Language Agent Tree Search) が行っていることであり、私が今これを読んでいる理由です。Andy Zhou、Kai Yan、Michal Shlapentokh-Rothman、Haohan Wang、Yu-Xiong Wangによる論文 (ICML 2024, arXiv:2310.04406) は、推論、行動、計画を単一のエージェントフレームワークに統合したこれまでで最も明快な構成であり、その結果は到底無視できるものではありません。

論文について

LATSが対処する核心的な問題は、これまでのエージェント研究における構造的なギャップです。ReActは推論と行動を交互に行いますが、軌道が誤った方向に向かったときに後戻りして別の道を試すメカニズムがありません。Tree of Thoughtsは推論ステップの分岐を可能にしますが、LM内部の知識に基づいて動作するため、探索の中でツールを呼び出したり外部フィードバックを受け取ったりすることができません。Reflexionは言語による自己修正を追加しますが、線形なリトライループであるため、代替案を探索することなく新しい軌道にコミットしてしまいます。LATSは、これら3つのアイデアを適切なモンテカルロ木探索 (MCTS) のバックボーンと融合させ、LLMエージェントが複数の分岐を探索し、実際の環境からのフィードバックを受け取り、パスが失敗したときにバックトラックすることを可能にします。

技術的な仕組みは、6ステップのMCTSループです：選択（UCT式を介して探索する次のノードを選択）、拡張（LMからn個の候補行動をサンプリング）、評価（ハイブリッド価値関数で各ノードをスコアリング）、シミュレーション（最終状態まで実行）、バックプロパゲーション（祖先ノードの値を更新）、そしてリフレクション（失敗時に、何が悪かったのかを言語的に要約して生成し、コンテキストとして保存）。価値関数は注目に値します：V(s) = λ·LM(s) + (1−λ)·SC(s) です。ここでLM(s)は環境フィードバックを受け取った後の軌道の質に対するLM自身の推定値であり、SC(s)は兄弟ノード間でその行動がサンプリングされる頻度に基づく自己整合性（self-consistency）スコアです。これは訓練された報酬モデルではなく、価値関数は完全にプロンプト駆動型です。

主なアイデア

• HumanEvalにおいて、GPT-4 + LATSは92.7%のpass@1を達成しました。これに対し、GPT-4 + Reflexionは91.0%、GPT-3.5 + ReAct単体では56.9%でした。GPT-3.5 + LATSは83.8%まで跳ね上がります。
• HotPotQAでは、LATS (CoT + ReAct) は0.71の完全一致（exact match）に達し、ReActベースラインの0.32に対し、マルチホップ推論の精度を2倍以上に向上させました。
• WebShop（ウェブナビゲーション + 購入）において、LATSは75.9（成功率38.0%）を記録し、Reflexionの64.2（35.0%）に対し、多くのページにわたる状態管理が必要なタスクで意味のある差をつけました。
• Game of 24（純粋な推論パズル）では、LATSは0.44の成功率に達し、同じGPT-4バックボーンを使用しているにもかかわらず、ToTの0.20を上回りました。
• 驚くべきことに、LATSはソリューションを見つけるためにToTよりも少ないノードを拡張し（HotPotQAのk=50で平均66.65対84.05）、使用トークン数も少なくなっています（173,290対210,215）。理論上はより高コストに見えるにもかかわらずです。

何が有効で、何が課題か

ベンチマークの数値は本物であり、フレームワークは概念的に洗練されています。UCT定式化は、ToTにおける場当たり的なBFS/DFSには欠けている、原則に基づいた探索と活用のトレードオフを提供します。純粋なLMの内省ではなく、外部環境のフィードバックを価値関数に統合したことは正しい方向であり、結果がそれを証明しています。

しかし、論文の中に埋もれている重要な前提があり、著者はそれを認めてはいるものの、十分にストレステストを行っていません：LATSは環境を以前の状態に戻す（リバートする）能力を必要とします。チェックポインティングがなければ、木を分岐させることはできません。一度行動が取られると、後戻りはできないからです。著者は、LMタスクにおいては「過去のテキスト入力をコピー＆ペーストする」ことで管理可能であることが多いと述べていますが、実際の行動環境（データベース、ファイルシステム、副作用のあるAPI）において、これは多くの本番システムが満たすことのできない厳しい要件です。WebShopの結果はベースラインより優れているものの、複雑な環境では自己リフレクションが具体的ではなく一般的になりがちで、エージェントが表面上は異なるが構造的には同一のミスを繰り返して行き詰まる可能性があることを示しています。論文はこの点に言及していますが、解決策は示されていません。

また、MCTS構造と価値関数の設計それぞれの寄与を切り分けるアブレーション（除去試験）も行われていません。同じハイブリッド価値関数を用いたより単純な分岐アプローチでも、ギャップの多くを埋められる可能性は十分にありますが、著者はこれを直接テストしていません。

なぜこれが金融AIにとって重要なのか

Beancountの帳簿は、LATSスタイルのツリー探索にとってほぼ理想的な環境です。その主な理由は、すべての帳簿がGitリポジトリで管理されていることです。多くの現実世界の環境でLATSを実用的でなくしている「状態復元」という厳しい要件は、git checkoutやgit stashによって極めて容易に満たすことができます。書き戻しエージェントは、複数の分岐にわたって仕訳エントリの候補を提案し、それらを貸借対照表の制約（価値関数）に照らして評価し、最もスコアの高いパスのみをコミットすることができます。失敗した分岐には、「勘定科目の分類ミスにより、資産 = 負債 + 純資産の不変条件に違反した」といった言語的なリフレクションが付与されます。

ハイブリッド価値関数の設計も直接応用可能です。帳簿エージェントの場合、LM(s)は提案されたエントリを意味的な適合性（これは正しいカテゴリーに見えるか？）に基づいてスコアリングし、SC(s)はエージェントが過去の類似の取引をどれだけ一貫して分類しているかを追跡します。これは、帳簿自体の履歴に根ざした自然な自己整合性チェックとなります。

ただし、金融の例えにおいて、状態復元の前提には注意が必要です。現実の帳簿には下流への影響が伴うことがよくあります。記帳されたエントリが請求書を発行し、それが支払いワークフローをトリガーする場合などです。そのようなケースでは、LATSの前提は崩れます。Beancountのように、帳簿がGit管理下のプレーンテキストファイルであり、下流のトリガーが発生する前に変更がローカルに留まる場合には、この前提は維持されます。しかし、これは明示しておくべき設計上の制約です。

次に読むべきもの

• 環境モデルのないMCTSベースの計画：「Reasoning with Language Model is Planning with World Model」(Hao et al., 2023, arXiv:2305.14992) — RAP。LATSが直接の基礎とし、かつそれを凌駕した手法です。
• LM価値関数はどの程度汎用化されるか？：「Let's Verify Step by Step」(Lightman et al., 2023, arXiv:2305.20050) — プロンプトベースの価値関数の代替としてのプロセス報酬モデル。
• 不可逆性下での安全なマルチステップ計画：「Decision-Making with Language Models via Successive Prompting」(Creswell et al., 2023) — 状態復元要件を回避する、より単純な計画アプローチ。