Tree-of-Thought（ツリーオブソート）

Tree-of-Thought とは

Tree-of-Thought（ToT）は、Yao et al.（2023）が提案した推論フレームワークで、Chain-of-Thought（CoT）の直線的な推論を木構造の探索に拡張する。各推論ステップを「ノード」として複数の候補を生成し、有望な分岐を評価・選択しながら深さ優先探索（DFS）や幅優先探索（BFS）で最適な解に到達する。

CoT → SC → ToT の進化

CoT は「1本道」、SC は「複数の独立した道から多数決」、ToT は「分岐を体系的に探索して最善の道を選ぶ」と捉えられる。

ToT のアルゴリズム

1. 分解（Decompose）: 問題を中間ステップに分解する方法を定義
2. 生成（Generate）: 各ステップで複数の候補「思考」を生成
3. 評価（Evaluate）: 各候補の有望さをLLM自体で評価（スコアリング or 投票）
4. 探索（Search）: BFS or DFS で有望な候補を展開、非有望な枝を剪定

24ゲームでの実例

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ゲームでの成功率:

CoT では解けない問題を ToT は 74% の成功率で解いた。特に「試行錯誤」や「バックトラック」が必要な問題で圧倒的な差がつく。

BFS vs DFS の使い分け

コストと実用性

ToT は各ノードで LLM を複数回呼び出すため、API コストが大幅に増加する。

• 24ゲーム (BFS, 幅=5, 深さ=3): 約 50〜100 回の API 呼び出し
• 創作タスク (DFS, 深さ=5): 約 20〜50 回の API 呼び出し

このコストのため、実務では「単純な CoT で十分な問題には CoT を使い、CoT で解けない計画・パズル・最適化問題にのみ ToT を適用する」のが現実的。

関連手法

• Graph-of-Thought（GoT）: 木をさらにグラフに拡張し、異なる分岐の思考を合流させる
• Algorithm-of-Thought（AoT）: アルゴリズム的な探索パターンを LLM に模倣させる
• Beam Search: NLP での古典的な探索手法をプロンプティングに応用

FAQ

Q1: ToT は全てのタスクで CoT より優れるか？

A1: いいえ。単純な QA や分類では CoT で十分であり、ToT のオーバーヘッドは無駄になる。ToT が真価を発揮するのは「探索空間が広く、バックトラックが必要な問題」（パズル、ゲーム、計画立案、創作）に限られる。

Q2: ToT を API で実装する際の注意点は？

A2: 各ノードの評価に LLM を使うため、Rate Limit に注意が必要。並列リクエストで高速化できるが、OpenAI API の Rate Limit（RPM/TPM）を超えないよう調整する。また、中間状態のキャッシュを実装するとコスト削減になる。

Q3: ToT と強化学習ベースの推論（o1/o3）の違いは？

A3: ToT は推論時にプロンプティングで探索を制御するのに対し、o1/o3 は学習時に強化学習で探索能力をモデルに内在化させている。o1/o3 はユーザーが探索方法を指定する必要がなく、モデルが自律的に最適な推論パスを選択する。