Chain-of-Thought を木構造に拡張し、各推論ステップで複数の分岐を生成・評価して最適な推論経路を探索する手法。BFS/DFS による体系的な探索で、単一パスの CoT では解けない複雑な問題に対応する。
Tree-of-Thought（ToT）は、Yao et al.（2023）が提案した推論フレームワークで、Chain-of-Thought（CoT）の直線的な推論を木構造の探索に拡張する。各推論ステップを「ノード」として複数の候補を生成し、有望な分岐を評価・選択しながら深さ優先探索（DFS）や幅優先探索（BFS）で最適な解に到達する。
| 手法 | 推論構造 | 探索方法 | 評価 |
|---|---|---|---|
| CoT | 直線（1パス） | なし（Greedy） | なし |
| Self-Consistency | 複数の直線 | 独立サンプリング | 多数決 |
| Tree-of-Thought | 木構造 | BFS / DFS | ステップごとに評価 |
CoT は「1本道」、SC は「複数の独立した道から多数決」、ToT は「分岐を体系的に探索して最善の道を選ぶ」と捉えられる。
ToT の代表的なベンチマークは「24ゲーム」（4つの数字と四則演算で24を作る）である。
問題例: 4, 5, 6, 10 → 24 を作る
ステップ1の候補:
(a) 10 - 4 = 6 → 評価: 有望（6, 5, 6 が残る）
(b) 5 + 4 = 9 → 評価: 有望
(c) 10 × 4 = 40 → 評価: 非有望（40 から 24 に近づきにくい）→ 剪定
ステップ2（分岐 a から）:
(a-1) 6 × 6 = 36 → 評価: 非有望 → 剪定
(a-2) 5 × 6 = 30 → 評価: 有望（30 - 6 = 24！）
最終回答: (10 - 4) = 6, 5 × 6 = 30, 30 - 6 = 24
つまり 5 × (10 - 4) - (10 - 4) = 5 × 6 - 6 = 24
24ゲームでの成功率:
| 手法 | 成功率 |
|---|---|
| Standard Prompting (GPT-4) | 7.3% |
| CoT Prompting (GPT-4) | 4.0% |
| CoT + SC (100パス) | 9.0% |
| ToT + BFS (GPT-4) | 74.0% |
CoT では解けない問題を ToT は 74% の成功率で解いた。特に「試行錯誤」や「バックトラック」が必要な問題で圧倒的な差がつく。
| 探索方法 | メリット | デメリット | 適するタスク |
|---|---|---|---|
| BFS | 最適解を見つけやすい | メモリ消費大 | 24ゲーム、パズル |
| DFS | メモリ効率良い | 最適でない解に陥りやすい | 創作、計画 |
ToT は各ノードで LLM を複数回呼び出すため、API コストが大幅に増加する。
このコストのため、実務では「単純な CoT で十分な問題には CoT を使い、CoT で解けない計画・パズル・最適化問題にのみ ToT を適用する」のが現実的。
A1: いいえ。単純な QA や分類では CoT で十分であり、ToT のオーバーヘッドは無駄になる。ToT が真価を発揮するのは「探索空間が広く、バックトラックが必要な問題」（パズル、ゲーム、計画立案、創作）に限られる。
A2: 各ノードの評価に LLM を使うため、Rate Limit に注意が必要。並列リクエストで高速化できるが、OpenAI API の Rate Limit（RPM/TPM）を超えないよう調整する。また、中間状態のキャッシュを実装するとコスト削減になる。
A3: ToT は推論時にプロンプティングで探索を制御するのに対し、o1/o3 は学習時に強化学習で探索能力をモデルに内在化させている。o1/o3 はユーザーが探索方法を指定する必要がなく、モデルが自律的に最適な推論パスを選択する。