Tree-of-Thought（エージェンティックプランニング）（ツリーオブソート）
LLMの推論プロセスを木構造として展開し、複数の思考パスを並列に探索する手法。各ノードが中間的な思考状態を表し、幅優先探索（BFS）や深さ優先探索（DFS）で最適な推論経路を発見する。Yao et al.（2023）が提案。
Tree-of-Thoughtとは
Tree-of-Thought（ToT）は、Yao et al.が2023年に発表した論文「Tree of Thoughts: Deliberate Problem Solving with Large Language Models」で提案されたLLMの推論フレームワークである。従来のChain-of-Thought（CoT）が単一の思考チェーンを線形的に展開するのに対し、ToTは複数の思考パスを木構造として並列に展開し、探索アルゴリズムにより最適な推論経路を発見する。
ToTの核心的なアイデアは、LLMの推論を「探索問題」として再定式化したことにある。各中間思考状態をノードとして表現し、ノード間の遷移（次の思考の生成）をエッジとして、古典的な探索アルゴリズム（BFS、DFS）やヒューリスティック探索を適用する。これにより、LLMは「行き詰まり」を検出して別のパスを試すバックトラッキングが可能になる。
CoTからToTへの進化
Chain-of-Thought（CoT）の限界を理解することが、ToTの価値を把握するための出発点となる。
| 特性 | Chain-of-Thought | Self-Consistency | Tree-of-Thought |
|---|---|---|---|
| 思考パス数 | 1本（線形） | 複数本（独立） | 複数本（木構造） |
| バックトラッキング | 不可 | 不可 | 可能 |
| 中間評価 | なし | 最終回答の多数決 | 各ノードで評価 |
| 探索戦略 | なし | サンプリング | BFS/DFS/A* |
| 計算コスト | 低 | 中 | 高 |
| 適するタスク | 単純な推論 | 回答のばらつきが大きい問題 | 戦略的探索が必要な問題 |
CoTは1本の思考チェーンを生成するため、途中で誤った推論をしても修正できない。Self-Consistency（Wang et al., 2022）は複数の独立したCoTチェーンを生成して多数決をとるが、各チェーンは互いに情報を共有しない。ToTは木構造により、有望なパスを深掘りしつつ、行き詰まったらバックトラッキングする柔軟な探索が可能である。
ToTの動作アルゴリズム
ToTのアルゴリズムは以下の4つのコンポーネントで構成される。
1. 思考の生成（Thought Generation）
各ノードから次の思考候補を複数生成する。生成方法には以下の2つがある。
| 生成方法 | 概要 | 適するケース |
|---|---|---|
| サンプリング（Sample） | 独立にk個の思考を生成 | 思考空間が広い場合 |
| 提案（Propose） | 1回のプロンプトでk個の候補を一括生成 | 思考空間が限定的な場合 |
2. 状態評価（State Evaluation）
各思考状態の「有望さ」を評価する。評価方法には以下がある。
| 評価方法 | 概要 | メリット | デメリット |
|---|---|---|---|
| 値評価（Value） | 各状態にスコア（1-10等）を付与 | 定量的な比較が可能 | スコアの信頼性にばらつき |
| 投票評価（Vote） | 複数の状態を比較して最も有望なものを選択 | 相対評価で安定 | 候補数が多いと非効率 |
3. 探索アルゴリズム
木構造の探索には、タスクの性質に応じて異なるアルゴリズムを使用する。
| アルゴリズム | 動作 | 適するタスク | メモリ使用量 |
|---|---|---|---|
| BFS（幅優先探索） | 各深さレベルで有望なノードを選択 | 解の深さが浅い問題 | 高（全ノード保持） |
| DFS（深さ優先探索） | 有望なパスを深く探索、行き詰まりでバックトラック | 解の深さが深い問題 | 低 |
| A*探索 | ヒューリスティックを用いた最適探索 | コスト最小化が重要な問題 | 中 |
| MCTS | モンテカルロ木探索 | 不確実性が高い問題 | 中 |
4. 終了条件
探索の終了条件として、（1）十分にスコアの高い解が見つかった、（2）最大探索ステップ数に到達した、（3）すべての探索パスが枝刈りされた、のいずれかを使用する。
ToTの代表的なベンチマーク結果
Yao et al.の論文では、以下のタスクでToTの有効性が実証された。
| タスク | CoT成功率 | ToT成功率 | 向上幅 | タスクの特性 |
|---|---|---|---|---|
| Game of 24 | 7.3% | 74.0% | +66.7pt | 数値組み合わせ探索 |
| Creative Writing | 6.93（人間評価） | 7.56 | +0.63 | 計画的な文章構成 |
| Mini Crosswords | 15.6%（文字正解率） | 60.0% | +44.4pt | 制約充足問題 |
特にGame of 24（4つの数字と四則演算で24を作る）では、CoTの7.3%に対しToTが74.0%と劇的な改善を示した。これは、バックトラッキングによる試行錯誤がこの種の探索問題に極めて有効であることを示している。
エージェンティックプランニングへの応用
ToTはエージェンティックプランニングにおいて、計画の探索と最適化に応用される。具体的には以下の場面で活用される。
- 計画の候補生成: 1つのタスクに対して複数の計画候補を木構造で展開し、最も有望な計画を選択する
- エラーリカバリ: 計画の実行中にエラーが発生した場合、バックトラッキングして別の計画パスを試す
- 最適化: 複数の実行パスのコスト（時間、API呼び出し数、トークン数）を比較して最適なパスを選択する
LATS（Language Agent Tree Search）はToTをエージェント文脈に拡張した手法で、モンテカルロ木探索（MCTS）を用いてエージェントの行動計画を最適化する。LATSでは、各ノードがエージェントの状態（観察履歴＋行動履歴）を表し、UCB1（Upper Confidence Bound）スコアで探索と活用のバランスを取る。
実装上の考慮事項
ToTを実装する際の主要な考慮事項は以下の通りである。
| 考慮事項 | 詳細 | 推奨設定 |
|---|---|---|
| 分岐数（k） | 各ノードから生成する子ノード数 | 3-5（タスク依存） |
| 探索深さ | 木の最大深さ | タスクのステップ数に合わせる |
| 枝刈り閾値 | スコアが低いノードを切る基準 | 上位50-70%を残す |
| 評価方法 | 値評価 vs 投票評価 | 定量的判断は値、比較判断は投票 |
| 計算予算 | 最大LLM呼び出し回数 | 100-500回（コスト許容範囲で） |
計算コストはToTの最大の課題であり、分岐数k=5、深さd=4の場合、最大5^4=625ノードの評価が必要になる。枝刈りにより実際の計算量は大幅に削減されるが、それでもCoTの数十倍のトークンを消費する。
よくある質問（FAQ）
Q1: ToTはどのようなタスクに最も効果的か？
A1: ToTは、（1）明確な正解がある、（2）中間状態の評価が可能、（3）バックトラッキングにより改善の余地がある、という3条件を満たすタスクに最も効果的である。数学パズル、コード生成、制約充足問題、戦略ゲームなどが該当する。逆に、自由度の高い創作タスクや、中間状態の評価が困難なタスクではCoTとの差が小さくなる。
Q2: ToTのコスト問題を軽減する方法は？
A2: 主要な軽減策として、（1）積極的な枝刈り（低スコアノードの早期打ち切り）、（2）分岐数の制限（k=2-3に抑える）、（3）深さの制限、（4）小型モデルでの評価＋大型モデルでの生成の2段階方式、（5）キャッシュの活用（同一思考パターンの再利用）がある。また、ToT-BFS（幅優先）よりToT-DFS（深さ優先）の方がメモリ効率がよい場合が多い。
Q3: ToTとMCTS（モンテカルロ木探索）の違いは？
A3: ToTはLLMの推論に探索アルゴリズムを適用した一般的なフレームワークであり、MCTSはその探索アルゴリズムの1つである。ToTはBFS、DFS、A*など任意の探索アルゴリズムを使用できる。LATSはToTの枠組みにMCTSを組み合わせたもので、UCB1スコアによる探索と活用のバランスが特徴である。MCTSはシミュレーション（ロールアウト）を行うため計算コストが高いが、不確実性が高い環境での意思決定に強い。