Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models

選定理由

評価点	高SABCD低
整合性	B: LLMによる状態価値評価によって探索と利用のトレードオフを解いている点はビジネスニーズが高い
信頼性	S: Proceedings of Machine Learning Research 2024 採択、著者は元DeepMind
健全性	S: 理論設計（MCTSの導入、LM評価の利用、反省の統合）は整然としており、明確なアルゴリズム構成を持つ。
汎用性	A: langgraphでも実装例があり汎用性は高いが、ハイパーパラメータに対する鋭敏性とランニングコストが課題
発展性	A: 様々な発展があるが、木構造に限定される点や状態が明確に定義できないタスクは適用が難しい点が課題である。

Paper: https://arxiv.org/abs/2310.04406
Code: N/A

エグゼクティブサマリ

LLMの思考を木構造で管理することで、先読みを可能とした。これにLLMはより少ないトライ&エラーで正しい結論に辿り着くことができる。

概要

【社会課題】
現状のLLMは、単一の入力に対して即座に応答する「一問一答型」が中心であり、複雑な意思決定や多段階タスクには対応しづらい。

【技術課題】
複雑な意思決定や多段階タスクには先読み(計画)が必要となる。しかし、従来手法（CoT, ReAct, Reflexion等）は多段推論・行動・反省といった要素をLLMに追加するが、計画はできない。そのため行動選択が短期的目標になりがちで、タスク達成率が低下する。

【提案】
LLMに多段推論（reasoning）、行動（acting）、計画（planning）を統合的に実行させる枠組みLATS(Language Agent Tree Search）を提案した。LATSはモンテカルロ木探索（MCTS）を用いて複数の行動候補を探索し、LLMが価値評価・反省することでより長期的で一貫した意思決定を実現する。

又、表1に示すように推論、行動、計画、反省、記憶というすべての構成を含んだアプローチはLATSが初である。

【効果】
ファインチューニングなどの勾配学習を行わずに、LLMが自律的に多段推論を重ね計画し、環境と対話的に行動できるようにした。実験では、プログラミングで従来手法を上回り、pass@1で92.7 %を達成。Webナビゲーションで既存の強化学習ベース手法を超え、成功率 75.9 %を記録。マルチホップ推論でも正答率が約 +8 Pt向上。

Language Agent Tree Search (LATS)

LATSは、強化学習で用いられるMCTSやベルマンバックアップの考え方を、LLMの推論時探索に適用したアルゴリズムである。LATSの Evaluation と Simulation において実施されるブートストラップは任意のステップ数先まで予測するが、LLMによる近似的な環境予測に依存するため(選択・モデル・ブートストラップ)バイアスが重なりやすく、初期値鋭敏性を生じやすい。一方で、LLMは長期的構造や意味的整合性を捉える能力を持つため、厳密な環境モデルがなくても有用なヒューリスティックとして機能する。

図２はベルマン方程式におけるバックアップ線図をbelief空間上で近似評価したものと解釈でき、ノードが状態（履歴）で、エッジが行動選択を表す。

アルゴリズムの全体像を以下に示す。

最後に強化学習アルゴリズムと比較すると以下のようになる。

観点	LATS	モンテカルロ法（MC）	TD法（TD(0)）	SARSA
分類	推論時探索	強化学習（価値推定）	強化学習（価値推定）	強化学習（制御）
主目的	推論・行動の最適化	価値関数の学習	価値関数の学習	方策と価値の同時学習
状態・行動空間	自然言語（thought/action）	離散/連続	離散/連続	離散/連続
探索構造	木構造（MCTS）	なし	なし	なし
ロールアウト	LLMによるロールアウト	実エピソード	実遷移	実遷移
評価の基準	LM評価＋自己一貫性	実報酬	実報酬＋推定価値	実報酬＋推定価値
ブートストラップ	あり	なし	あり	あり
更新対象	探索木の統計量	価値関数パラメータ	価値関数パラメータ	行動価値関数 (Q)
学習（重み更新）	しない	する	する	する
方策との関係	探索で暗黙的に決定	固定 or 任意	固定 or 任意	On-policy
失敗の活用	Reflection（自然言語）	サンプル平均	TD誤差	TD誤差（行動依存）

Selection（選択）

全ノードから次に展開すべきノードをUCB（Upper Confidence Bound）に基づく評価で選択する。状態価値関数 $V(s_t)$ と探索回数 $N(s_{t+1})$ のバランスを取って、最も有望なノードを選ぶ行動 $a_t$ を行う。

$$a_t = \arg\max_{a_t} \left[ V(S_t) + c \sqrt{ \frac{\log N(S_t)}{N(S_{t+1})} } \right]$$

$$N(S_{t+1}) = N(S_{t}) + 1$$

その後、記憶に従い観測 $o_{t}$ を得る。これは過去の経験を再学習に使う Experience Replay とは異なり、探索木に保存された観測をそのまま再利用して同じ探索経路を辿るための仕組みである。

Expansion（展開）

選ばれたノード $s_{t}$ から、 $n$ 個の子ノードを $\theta$ のパラメータを持つモデルからサンプリングして生成する。その後、実環境から観測 $o_{t}$ を得る。

$$a_t^{(i)} \sim p_{\theta}(S_t), \quad S_{t+1} = \text{Env}(S_t, a_t)$$

Evaluation（評価）

新しく展開されたノードの状態価値(スカラー量)をLLMによって評価する。

$$V(s) = \lambda \cdot \mathrm{LM}(s) + (1-\lambda)\cdot \mathrm{SC}(s)$$

ここで SC(s) は Self-Consistency を指す。 従来の ToT[Yao2023] が「思考の妥当性」のみを評価していたのに対し、LATSは外部環境からの観測を得た後に評価を行う。これにより、コードの実行エラーやウェブ検索の結果に基づいた、より正確な価値判断が可能になる。

Simulation (予測)

Expansion によって実環境から得られた観測までは事実であり、それ以降の将来については環境観測をせず、言語モデル自身に推論を行わせて「この状態を起点に進んだ場合、最終的にどれくらい良い結果になりそうか」を推定する。この推定値は、実際に得られた報酬ではなく近似的な評価であり、後続の Backpropagation で探索木全体の意思決定を導くために用いられる。

$$\hat{R}(h_t) \approx \sum_{k=0}^{K} \gamma^k \hat{r}_{t+k}$$

Backpropagation (木構造の統計量の更新)

Backpropagation は、Simulation で得られた将来価値の推定結果を、探索木をさかのぼって各ノードに反映する段階である。これにより、どの思考や行動が有望だったかという情報が蓄積され、次の探索ではより良い分岐が選ばれやすくなる。

$$V(h_t) \leftarrow \frac{N(h_t)\,V(h_t) + \hat{R}(h_t)}{N(h_t) + 1}$$

$$N(h_t) \leftarrow N(h_t) + 1$$

Reflextion

Reflection は、これまでの思考や行動を振り返り、誤りや改善点を言語モデル自身に指摘させて、探索の方針を修正する段階である。
単なる価値更新にとどまらず、推論の質そのものを改善することで、同じ失敗を繰り返さない探索を可能にする。

効果まとめ

• 一般性: 明示的な環境モデルや報酬設計を必要とせず、言語モデルの生成・評価能力をそのまま探索と価値推定に利用できるため、推論タスクから対話型タスクまで幅広く適用できる。

• 探索効率: 実環境との相互作用を最小限に抑えつつ、木探索と価値バックアップによって有望な思考経路に計算資源を集中できる。

• 柔軟性: 状態やツリー構造を設計することで様々な環境に適用することができる。

実験

Programming データセットでの実験

表４，５が示すようにLATSは両方のデータセットでSOTAである。