Tree of Thoughts（ツリーオブソーツ）

Tree of Thoughts（ToT）とは

Tree of Thoughts（ToT）は、Princeton大学のYao et al. 2023が提案したLLMの推論フレームワークだ。従来のChain-of-Thought（CoT）プロンプティングが推論を一本道の列として扱うのに対し、ToTは推論を木構造として捉え、複数の思考経路を並列探索する。

CoTとの違い

Standard Promptingは直接回答を生成し、探索も自己評価もない。Chain-of-Thoughtは線形思考で貪欲に選択し、自己評価は行わない。Tree of Thoughtsは木構造思考でBFS/DFS探索を行い、LLMによる自己評価を組み込む。MCTSベースの手法はさらに確率的UCT探索とPRM評価を加えた高度なものだ。

ToTの動作原理

フェーズ1: Thought Generation（思考生成）

問題を複数のステップに分解し、各ステップで複数の候補「Thought」を生成する。Game of 24（4つの数で24を作る）の例では、入力として [4, 9, 10, 13] が与えられたとき、LLMは複数の最初のステップ候補を生成する。各候補が木の枝となり、それぞれ独立した推論経路を形成する。

フェーズ2: State Evaluation（状態評価）

LLM自身（または外部評価器）が各Thoughtの「見込み」を評価する。評価プロンプトとして「以下の中間ステップは最終目標に到達できる可能性がありますか？（確実/おそらく可能/不可能）」と問いかけ、各候補をスコアリングする。

フェーズ3: Search（探索）

評価スコアに基づき、BFS（幅優先）またはDFS（深さ優先）で探索を進める。BFSは各深さで上位K件のThoughtを保持し多様な探索に有効だ。DFSは一つの経路を深く探索しリソース効率が良い。

実験結果（元論文）

Game of 24タスクでの成功率比較において、IO Prompting は7.3%、CoT は4.0%だったのに対し、Tree of Thoughts（BFS）は74%を達成した。Mini-crossword（5x5クロスワード）では、CoTの16.0%に対しToT（DFS）が40.0%を達成している。

実装の概略

ToTの実装は次の3つの関数で構成される。Thought生成関数はプロンプトから複数の次ステップ候補を生成する。評価関数はLLMに各Thoughtの見込みを評価させる。探索関数はBFSまたはDFSで木を探索し、最良経路を返す。これらを深さ分ループさせることで推論木の探索が実現する。

派生・拡張

Graph of Thoughts（GoT、ETH Zurich 2023）は木構造をグラフ構造に拡張し、複数経路のマージを可能にした。Algorithm of Thoughts（AoT）はアルゴリズム的思考のパターンを埋め込む手法だ。ToT+MCTSは探索をMCTSで強化した組み合わせ手法であり、現在の推論モデルに取り込まれている。

適用領域

数学パズル・プログラム合成・戦略ゲーム・多段階プランニングに特に有効だ。単一ステップの回答が期待されるQ&Aでは効果が限定される。検証器（verifier）が利用できるタスク、すなわち答えが正しいかどうかを自動確認できる領域で最も威力を発揮する。

計算コストの考慮

ToTはCoTと比較してLLM呼び出し回数が大幅に増加する。BFS深さ3・分岐数3の場合、最大13回のLLM呼び出しが必要だ（1+3+9）。APIコスト管理のためにpruning（枝刈り）の積極的活用と評価閾値の設定が実用上重要だ。

まとめ

Tree of ThoughtsはLLMに「立ち止まって考え直す」能力を与える。Test-Time Computeフレームワークの中でもシンプルさと効果のバランスが良く、2023年以降の推論強化手法の基礎理論となっている。現在の推論モデル（o1/DeepSeek R1等）の内部手法はToTとMCTSの融合として理解できる。