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

Source: Dev.to

選定理由

評価点

整合性

B: LLM による状態価値評価で探索と利用のトレードオフを解く点はビジネスニーズが高い。

信頼性

S: Proceedings of Machine Learning Research 2024 採択。著者は元 DeepMind。

健全性

S: 理論設計（MCTS の導入、LM 評価の利用、反省の統合）は整然としており、明確なアルゴリズム構成を持つ。

汎用性

A: langgraph でも実装例があり汎用性は高いが、ハイパーパラメータへの鋭敏性とランニングコストが課題。

発展性

A: 様々な発展が期待できるが、木構造に限定される点や状態が明確に定義できないタスクへの適用は難しい。

論文情報

Paper: Language Agent Tree Search (LATS)
LLM の思考を木構造で管理し、先読みを可能にすることで、少ないトライ＆エラーで正しい結論に辿り着く。

提案手法

モンテカルロ木探索（MCTS）を用いて複数の行動候補を探索し、LLM が価値評価・反省を行うことで、長期的かつ一貫した意思決定を実現する。

• 特徴
  • 推論、行動、計画、反省、記憶というすべての構成要素を統合（LATS が初）。
  • MCTS とベルマンバックアップの概念を LLM の推論時探索に適用。

効果と課題

• 効果

  • LLM の近似的環境予測に依存するためバイアスが重なりやすく、初期値鋭敏性が生じやすい。
  • しかし、LLM は長期的構造や意味的整合性を捉える能力があるため、厳密な環境モデルがなくても有用なヒューリスティックとして機能する。

• 図 2 の解釈

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

アルゴリズム全体像

比較表

探索手続き

UCB に基づくノード選択

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

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

$$ N(S_{t+1}) \leftarrow N(S_t) + 1 $$

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

ノード展開とサンプリング

選ばれたノード $s_t$ から $n$ 個の子ノードを、パラメータ $\theta$ を持つモデル $p_\theta$ からサンプリングして生成する。

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

Evaluation（評価）

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

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

• $\mathrm{LM}(s)$: LLM による価値予測
• $\mathrm{SC}(s)$: Self‑Consistency（自己一貫性）

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

Backpropagation（木構造の統計量更新）

シミュレーションで得られた将来価値の推定結果 $\hat{R}(h_t)$ を探索木をさかのぼって各ノードに反映する。

$$ 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 $$

Reflection（反省）

Reflection は、これまでの思考や行動を振り返り、誤りや改善点を LLM に指摘させて探索方針を修正する段階である。

• 一般性: 明示的な環境モデルや報酬設計を必要とせず、LLM の生成・評価能力をそのまま探索と価値推定に利用できる。
• 探索効率: 実環境との相互作用を最小限に抑えつつ、木探索と価値バックアップで有望な思考経路に計算資源を集中できる。
• 柔軟性: 状態やツリー構造を設計すれば、様々な環境に適用可能。

実験

Programming データセットでの結果

表 4・5 が示すように、LATS は両データセットで最先端（SOTA）性能を達成した。