last_modified: 2026-01-11

生成AIによる自動生成記事に関する免責事項: 本記事は、提供された学術論文 Tree of Thoughts: Deliberate Problem Solving with Large Language Models (Yao et al., NeurIPS 2023) の内容に基づき、大規模言語モデルによって作成された解説記事です。正確な内容は参考文献を必ず参照してください。

1. 序論：自己回帰的生成から意図的な探索へ#

GPT-4やPaLMに代表される大規模言語モデル（LLM）は、数学、記号論理、常識推論など多岐にわたるタスクにおいて顕著な能力を示している。しかし、これらのモデルの根本的な動作原理は、依然としてトークン単位の左から右への（left-to-right）自己回帰的な決定プロセスに基づいている 。この単純なメカニズムは、トークン生成における局所的な決定が連鎖的に行われるため、探索、戦略的な先読み（lookahead）、あるいは初期の決定が極めて重要な意味を持つタスクにおいて、しばしば不十分であることが指摘されている 。

Yao et al. (2023) が提案した Tree of Thoughts (ToT) フレームワークは、人間の認知プロセスにおける「熟慮（Deliberation）」の概念をLLMの推論に導入することで、これらの課題を克服することを目的としている 。ToTは、従来の Chain-of-Thought (CoT) プロンプティングを一般化したものであり、推論の中間ステップとなる「思考（Thought）」を探索木（Tree）のノードとして扱うことで、LLMが複数の推論パスを検討し、自己評価を行い、必要に応じてバックトラッキングを行うことを可能にする 。

本稿では、ToTの理論的背景、数理的定式化、およびその実証的有効性について、学術的な観点から包括的な解説を行う。

2. 理論的背景と歴史的文脈#

2.1 認知科学における二重過程理論#

ToTの設計思想は、認知心理学における「二重過程理論（Dual Process Theory）」に強く影響を受けている 。

• システム1（System 1）: 高速、自動的、無意識的な思考モード。従来のLLMによるトークン単位の直感的な生成は、このシステム1に類似している 。
• システム2（System 2）: 低速、意図的、意識的な思考モード。論理的な分析や計画、意思決定に関与する。

ToTは、LLMの持つシステム1的な連想能力を、探索アルゴリズムによるシステム2的な計画プロセスで補完する試みと捉えることができる 。

2.2 古典的AIと問題解決の探索モデル#

1950年代、Newell, Shaw, Simonらは、人間の問題解決プロセスを「問題空間（Problem Space）における探索」として定式化した 。彼らの枠組みでは、問題解決は木構造として表現され、ノードは部分的な解の状態を、枝は状態を変更する演算子を表す 。

ToTはこの古典的なAIの視点を現代のLLMに適用したものである。既存の手法（CoT等）が連続的な言語シーケンスをサンプリングするのに対し、ToTは思考の木を明示的に維持・操作する点で、発見的な探索アルゴリズム（Heuristic Search）の現代的解釈と言える 。

3. 数理的定式化#

ToTフレームワークは、LLMを用いた問題解決を木探索として形式化する。以下に、その構成要素を定義する。

3.1 基本定義#

事前学習済みの言語モデルを $p_\theta$ とし、トークンのシーケンスを $x, y, z$ 等で表す。 基本的な Input-Output (IO) プロンプティングは、入力 $x$ から出力 $y$ への写像 $y \sim p_\theta(y|\text{prompt}_{IO}(x))$ として定式化される 。 Chain-of-Thought (CoT) は、入力 $x$ と出力 $y$ を橋渡しする一連の思考 $z_{1:n}$ を導入し、$y \sim p_\theta(y|x, z_{1:n})$ をサンプリングするプロセスである 。

3.2 Tree of Thoughts (ToT) の構成要素#

ToTは、問題を探索木上の探索として定義する。各ノードは状態 $s = [x, z_{1:i}]$ であり、これは入力 $x$ とこれまでの思考列 $z_{1:i}$ を表す 。ToTの実装には以下の4つの要素が必要となる。

1. 思考の分解 (Thought Decomposition)#

中間プロセスをステップに分解する。思考 $z_i$ は、問題の性質に応じて数語（クロスワード）、数式（24のゲーム）、あるいはパラグラフ（クリエイティブライティング）等の単位を取り得る 。

2. 思考生成器 (Thought Generator) $G(p_\theta, s, k)$#

現在の状態 $s$ から、次の思考の候補 $k$ 個を生成する。以下の2つの戦略が提案されている 。

• Sample: CoTプロンプトからi.i.d.に $k$ 個の思考をサンプリングする。思考空間が多様な場合（例：クリエイティブライティング）に有効である 。 $z_{i+1}^{(j)} \sim p_\theta^{CoT}(z_{i+1}|s) \quad (j=1 \dots k)$
• Propose: 「提案プロンプト（Propose Prompt）」を用いて、文脈を維持しつつ次の一手を順次提案させる。思考空間が制約されている場合（例：数式生成）に有効である 。 $[z^{(1)}, \dots, z^{(k)}] \sim p_\theta^{\text{propose}}(z_{i+1}^{(1 \dots k)}|s)$

3. 状態評価器 (State Evaluator) $V(p_\theta, S)$#

状態の集合 $S$（フロンティア）に対し、問題解決に向けた進捗を評価する。これは探索アルゴリズムにおけるヒューリスティック関数として機能する 。

• Value (独立評価): 各状態 $s$ に対してスカラー値や分類（sure/likely/impossible等）を付与する 。これは先読みシミュレーションや常識推論に基づく。 $V(p_\theta, S)(s) \sim p_\theta^{\text{value}}(v|s)$
• Vote (投票): 複数の状態 $S$ を比較し、最も有望な状態 $s^*$ を投票により選出する 。絶対的な評価が困難な場合（例：文章の整合性）に適している。 $s^* \sim p_\theta^{\text{vote}}(s^*|S)$

4. 探索アルゴリズム (Search Algorithm)#

ToTフレームワークでは、木構造に応じて任意の探索アルゴリズムを適用可能である 。

• 幅優先探索 (BFS): 各ステップで有望な上位 $b$ 個の状態を維持する 。
• 深さ優先探索 (DFS): 最も有望な状態を深さ方向に探索し、評価値が閾値 $v_{th}$ を下回った場合に枝刈り（Pruning）を行い、バックトラッキングする 。

4. 実験的評価と成果#

Yao et al. は、GPT-4を用いた実験において、標準的なCoTでは解決が困難な3つのタスク（Game of 24, Creative Writing, Mini Crosswords）を用いてToTの有効性を検証した 。

4.1 Game of 24（数理的推論）#

4つの数字を四則演算を用いて24にする数学パズルである。

• 設定: 難易度の高い901-1000番のゲームを使用。思考は3つの中間式に分解される。探索にはBFS（幅 $b=5$）を使用 。
• 結果: GPT-4を用いたCoTの成功率はわずか 4.0% であったのに対し、ToT ($b=5$) は 74% の成功率を達成した 。
• 分析: エラー分析によると、CoTの約60%は最初のステップですでに失敗していた。これは左から右への生成における初期決定の不可逆性を示唆しており、ToTによる広範な探索と先読みの重要性が裏付けられた 。

4.2 Creative Writing（長文生成と計画）#

ランダムな4つの文を入力とし、それらを各段落の末尾に含む整合性のある4段落の文章を作成するタスク 。

• 設定: 思考ステップは「執筆計画」と「文章生成」に分解される。生成された計画に対して投票（Vote）を行い、最良の計画に基づいて文章を生成する 。
• 結果: GPT-4による自動評価および人間によるブラインド評価の双方において、ToTはCoTよりも整合性の高い文章を生成した。特に人間による評価では、41対21でToTが支持された 。

4.3 Mini Crosswords（探索とバックトラッキング）#

$5 \times 5$ のクロスワードパズルを解くタスク。単語レベルの制約だけでなく、文字レベルの整合性が求められる 。

• 設定: 思考は単語を埋める操作。DFSを使用し、埋められないマスが生じた場合（impossibleと評価された場合）に枝刈りを行う 。
• 結果: CoTの単語レベル成功率が16%未満であったのに対し、ToTは 60% を達成した 。
• アブレーション: 枝刈り（Pruning）やバックトラッキングを無効化すると性能が著しく低下することが確認され、探索アルゴリズムにおけるこれらの機構の必要性が示された 。

5. 議論と考察#

5.1 一般性とモジュール性#

ToTの数理的な利点は、その一般性にある。IO、CoT、CoT-SCといった既存の手法は、ToTにおける木の深さや幅、評価方法を限定した特殊ケースとして再定義できる 。また、ToTは思考の生成、評価、探索の各モジュールが独立しているため、問題の性質やリソースに応じて柔軟に構成を変更可能である 。

5.2 コストと効率のトレードオフ#

ToTは高い性能を発揮する一方で、計算コスト（トークン数）は増大する。例えばGame of 24において、ToTはCoTの約100倍のトークンを消費する場合がある 。しかし、CoT-SC（best of 100）と比較した場合、ToTは同等のコストでより高い成功率（49% vs 74%）を達成しており、探索の効率性は高いと言える 。

5.3 限界と展望#

ToTは、GPT-4がすでに高い性能を持つタスク（例：GSM8K）においては、必ずしも大幅な改善をもたらさない可能性がある 。ToTが真価を発揮するのは、初期の決定が致命的となるような「探索」や「計画」を要する複雑な問題領域である。将来的には、$A^*$探索やモンテカルロ木探索（MCTS）のようなより高度な探索アルゴリズムの導入や、思考生成・評価のためのモデルのファインチューニングが期待される 。

6. 結論#

Tree of Thoughts (ToT) フレームワークは、大規模言語モデルの能力を、単純な連想的生成（システム1）から、意図的な探索と計画（システム2）へと拡張する重要なアプローチである。ToTは、問題解決プロセスを「思考の木」上の探索として定式化し、LLM自身による自己評価をヒューリスティックとして活用することで、数理的推論、創作的執筆、および制約充足問題において、従来手法を凌駕する成果を上げた。この成果は、LLMと古典的AI探索手法の融合が、次世代のAI推論システムの鍵となることを示唆している。

参考文献#

• Brown, T., et al. (2020). Language models are few-shot learners. NeurIPS.
• Daw, N. D., et al. (2005). Uncertainty-based competition between prefrontal and dorsolateral striatal systems for behavioral control. Nature Neuroscience.
• Yao, S., et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601.
• Jung, J., et al. (2022). Maieutic prompting: Logically consistent reasoning with recursive explanations.
• Kahneman, D. (2011). Thinking, fast and slow. Macmillan.
• Kahneman, D., et al. (2002). Representativeness revisited: Attribute substitution in intuitive judgment.
• Kim, G., et al. (2023). Language models can solve computer tasks.
• Liu, B., et al. (2023). LLM+P: Empowering large language models with optimal planning proficiency.
• Newell, A., et al. (1959). Report on a general problem solving program.
• Newell, A., & Simon, H. A. (1972). Human problem solving. Prentice-Hall.
• OpenAI. (2023). GPT-4 technical report.
• Radford, A., et al. (2019). Language models are unsupervised multitask learners.
• Silver, D., et al. (2017). Mastering the game of Go without human knowledge. Nature.
• Wang, X., et al. (2022). Self-consistency improves chain of thought reasoning in language models.
• Wei, J., et al. (2022). Chain of thought prompting elicits reasoning in large language models.
• Newell, A., et al. (1959). Report on a general problem solving program.
• Newell, A., et al. (1972). Human problem solving.
• Yao, S., et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models.
• Brown, T., et al. (2020). Language models are few-shot learners.
• Wei, J., et al. (2022). Chain of thought prompting elicits reasoning in large language models.
• Wei, J., et al. (2022). Chain of thought prompting elicits reasoning in large language models.
• Newell, A., & Simon, H. A. (1972). Human problem solving.
• Hart, P. E., et al. (1968). A formal basis for the heuristic determination of minimum cost paths.
• Touvron, H., et al. (2023). Llama: Open and efficient foundation language models.

補遺：探索アルゴリズムの数理的実装詳細#

本セクションでは、Tree of Thoughts (ToT) における探索アルゴリズム（BFSおよびDFS）の具体的な実装ロジックを、擬似コードと数理的な操作に基づいて詳細に解説する。

A. 幅優先探索 (BFS) のアルゴリズム構成#

Game of 24やCreative Writingのように、思考のステップ数（木の深さ）が $T$ と限定されており、かつ初期段階での質の高い選抜が重要となるタスクにおいて、BFSは有効である。

アルゴリズム定義: ToT-BFS#

• 入力: 問題入力 $x$、言語モデル $p_\theta$、生成器 $G$、評価器 $V$、ステップ制限 $T$、幅制限 $b$。
• 初期化: 状態集合 $S_0 = \{x\}$。

各ステップ $t = 1 \dots T$ において以下の処理を実行する 。

1. 候補生成 (Expansion): 現在の状態集合 $S_{t-1}$ 内の各状態 $s$ に対し、生成器 $G$ を用いて次段階の思考候補 $z_t$ を生成し、候補集合 $S'_t$ を作成する。 $S'_t = \{ [s, z_t] \mid s \in S_{t-1}, z_t \in G(p_\theta, s, k) \}$

2. 評価 (Evaluation): 候補集合 $S'_t$ に対し、評価器 $V$ を用いて評価値の集合 $V_t$ を計算する。 $V_t(s') = V(p_\theta, S'_t)(s') \quad \text{for all } s' \in S'_t$

3. 選択 (Selection/Pruning): 評価値に基づき、上位 $b$ 個の最も有望な状態を選択して次ステップの状態集合 $S_t$ とする。 $S_t = \arg\max_{S \subset S'_t, |S|=b} \sum_{s \in S} V_t(s)$

このプロセスにより、探索空間が指数関数的に爆発することを防ぎつつ、多様な有望解を並行して維持することが可能となる。

B. 深さ優先探索 (DFS) のアルゴリズム構成#

Mini Crosswordsのように、探索空間が深く、かつ正解に辿り着くためのパスが限られている場合、あるいは不可能な状態を早期に検知してリソースを節約する必要がある場合にDFSは適している。

アルゴリズム定義: ToT-DFS#

• 入力: 現在の状態 $s$、現在のステップ $t$、閾値 $v_{th}$（その他のパラメータはBFSと同様）。

再帰関数 DFS(s, t) として定義される 。

1. 終了条件: $t > T$（ステップ制限到達）ならば、解を出力して終了。

2. 候補生成とソート: 現在の状態 $s$ から候補 $S'$ を生成し、評価器 $V$ の値に基づいて降順にソートする。 $S' \leftarrow \text{Sort}(G(p_\theta, s, k)) \text{ by } V$

3. 再帰的探索と枝刈り (Pruning): ソートされた各候補 $s' \in S'$ について、以下を実行する。

   • 枝刈り判定: 評価値 $V(s')$ が閾値 $v_{th}$ 以下であれば、その枝（subtree）は探索せずスキップする（Pruning）。 $\text{if } V(p_\theta, \{s'\})(s') \le v_{th} \text{ then continue}$
   • 再帰呼び出し: 閾値を超えている場合、次ステップへ進む。 $\text{DFS}(s', t+1)$

このバックトラッキング機能により、ToTは行き詰まり（dead-end）から脱出し、別の可能性を模索する能力を獲得する。これはCoTのような一直線の生成では不可能な挙動である。

補遺：大規模言語モデルの推論能力に関する数理的考察#

本セクションでは、Tree of Thoughts (ToT) がなぜChain-of-Thought (CoT) よりも優れた推論能力を発揮するのか、そのメカニズムを確率論および探索理論の観点から数理的に考察する。

1. 同時確率分布の分解と探索空間#

言語モデルによる問題解決は、入力 $x$ が与えられた下で、解となるトークン列 $y$ の条件付き確率 $P(y|x)$ を最大化する問題とみなせる。

CoTの確率的解釈#

CoTは、解 $y$ を導くための中間思考 $z = (z_1, \dots, z_n)$ を導入し、以下の結合確率を最大化しようとする試みである。 $P(y, z|x) = P(z_1|x) P(z_2|x, z_1) \dots P(y|x, z_{1:n})$ しかし、CoTにおけるサンプリング（Greedy または Beam Search）は、局所的な確率 $P(z_{i}|x, z_{1:i-1})$ に依存して決定を行う。一度低い確率の（誤った）思考 $z_i$ が選択されると、以降の確率はその誤った条件付き確率に支配され、回復が困難となる。これを「誤差の蓄積（Error Cascading）」と呼ぶ。

ToTによる大域的最適化#

ToTは、この問題を「探索木上の経路最適化」として再定式化する。目的は、評価関数 $V(s)$ によって近似される「正解への到達確度」を最大化する経路 $s_T = [x, z_1, \dots, z_T]$ を見つけることである。

$\max_{z_1, \dots, z_T} V(x, z_1, \dots, z_T)$

ここで評価関数 $V$ は、現在の部分的な状態 $s$ から将来的に正解に到達できる確率（Lookahead probability）を、LLM自身の知識を用いて推定していると解釈できる。 $V(s) \approx P(\text{reachable to solution} | s)$

2. ヒューリスティック探索としてのLLM#

ToTの核心は、LLM（$p_\theta$）を単なる生成器（Generator）としてだけでなく、評価器（Evaluator）としても利用する点にある。これは古典的な$A^*$探索における評価関数 $f(n) = g(n) + h(n)$ の概念に対応する。

• 生成器 $G$: 探索木の分岐係数（Branching Factor）を制御し、探索空間を展開する役割。
• 評価器 $V$: ヒューリスティック関数 $h(n)$ の役割。ゴールまでの推定距離や、状態の有望さを提供する。

論文中の実験結果（Game of 24での成功率向上）は、LLMが自身の生成した思考に対して、「この思考は正解に繋がらなさそうだ（Impossible）」というメタ認知的な判断（評価）を行う能力を持っており、それを探索のガイダンスとして利用することで、探索効率が劇的に向上することを示している。

3. 計算複雑性とスケーラビリティ#

ToTの計算コストは、木のノード数に比例する。

• BFSの場合、深さ $T$、ビーム幅 $b$、分岐数 $k$ に対し、評価回数は $O(T \cdot b \cdot k)$ となる。
• CoT（Best of $N$）の場合、コストは $O(N)$ である。

実験結果（Table 7 ）は、ToTが高い計算コスト（トークン数）を要することを示しているが、同時にCoT-SCでサンプル数を増やしても到達できない正解率の壁を突破している。これは、単純なサンプリング数の増加（量による解決）では解決できない問題に対し、構造化された探索（質による解決）が必要であることを数理的に裏付けている。

補遺：高校数学と線形代数で解き明かすTree of Thoughtsの数理#

本セクションでは、Tree of Thoughts (ToT) がなぜChain-of-Thought (CoT) よりも優れた推論能力を発揮するのか、そのメカニズムを高校数学（確率・集合）と線形代数（ベクトル）の言葉を用いて、行間を補いつつ数理的に解説します。ToTの本質は、言語モデルの生成プロセスを「確率的な一本道」から「評価関数に基づく最適化問題」へと昇華させる点にあります。

1. 推論プロセスを「状態空間の探索」として定義する#

まず、大規模言語モデル（LLM）による問題解決を、ベクトル空間上の移動として捉え直します。

• 状態（State）: 現在の思考や途中経過を表すベクトル $s$。
• 初期状態: 入力プロンプト $s_0$。
• 遷移（Transition）: LLMがある思考から次の思考を生み出す関数 $G$。 $s_{t+1} = G(s_t)$

CoTとToTの決定的な違い#

• Chain-of-Thought (CoT): 初期状態 $s_0$ から、確率的に $s_1, s_2, \dots$ と一本の道（軌跡）を描くプロセスです。 $s_0 \to s_1 \to s_2 \to \dots \to s_{final}$ 数学的には、各ステップで最も確率が高い（あるいはサンプリングされた）1つのベクトルを選び続ける「貪欲法（Greedy Approach）」に近い挙動をとります。一度「悪い方向」へ進むと、後戻りできません。

• Tree of Thoughts (ToT): ある状態 $s_t$ から、可能性のある複数の未来 $s_{t+1}^{(1)}, s_{t+1}^{(2)}, \dots, s_{t+1}^{(k)}$ を生成し、それを集合として管理します。 $S_{t+1} = \{ s_{t+1}^{(1)}, s_{t+1}^{(2)}, \dots, s_{t+1}^{(k)} \}$ これは一点の移動ではなく、「可能性の領域（領域候補）」を広げながら進むプロセスと言えます。

2. 目的関数（Objective Function）の明確化#

ToTが「思考」できる理由は、進むべき方向を定める羅針盤、すなわち評価関数（Value Function） $V(s)$ を導入した点にあります。

LLM単体は「次に続きそうな単語」を予測する確率 $P(token|context)$ しか持ちませんが、ToTではこれを**「問題が解決する見込み」**という目的関数に変換します。

具体例：Game of 24（数式パズル）の場合#

4つの数字 $\{x, y, z, w\}$ を使って24を作る場合、目的関数 $V(s)$ は以下のように定義される「見込みの関数」です。

論文中の実験では、LLMに「この残り数字で24を作れそうですか？」と問いかけ、その回答を数値化しています。

• sure (確実) $\to 1.0$
• likely (ありそう) $\to 0.5$
• impossible (不可能) $\to 0.0$

ToTは、この $V(s)$ を最大化するような経路 $s_0, s_1, \dots, s_n$ を探索する最適化問題を解いていることになります。

3. 「枝刈り（Pruning）」という名の集合演算#

ToTの探索アルゴリズム（BFS/DFS）は、数学的には**「有望な部分集合のフィルタリング」**です。

幅優先探索（BFS）において、ビーム幅 $b$ で探索する場合、次のような集合演算を行っています。

1. 展開（Expand）: 現在の有望な状態集合 $S_t$ に含まれる全ての要素から、次の候補を生成し、巨大な候補集合 $C_{t+1}$ を作る。 $C_{t+1} = \bigcup_{s \in S_t} \{ \text{LLMが生成した } s \text{ の次の思考候補} \}$
2. 評価と選抜（Evaluate & Select）: 候補集合 $C_{t+1}$ の中から、評価関数 $V(s)$ の値が大きい上位 $b$ 個を選び出し、新しい状態集合 $S_{t+1}$ とする。 $S_{t+1} = \underset{S \subset C_{t+1}, |S|=b}{\operatorname{arg\,max}} \sum_{s \in S} V(s)$

この操作により、**「見込みのないルート（$V(s)$ が低いベクトル）」は集合から削除（枝刈り）**されます。これが、CoTでは不可能な「間違いに気づいて引き返す（あるいはその道を捨てる）」という知的な振る舞いの数理的実体です。

4. LLMプロンプティングへの応用：ToT効果を得るためのレシピ#

複雑なPythonコードを書かずとも、チャット形式のプロンプトでToTに近い効果（思考の拡散と収束）を得るためのテクニックを紹介します。

手順A: 候補の生成（Generate）#

一度に答えを出させるのではなく、複数のアプローチを出させます。

プロンプト例: 「〇〇という課題に対して、考えられる解決アプローチを3つ、互いに異なる視点から提案してください。（案1, 案2, 案3）」

手順B: 自己評価（Evaluate）#

生成された案を、LLM自身に客観的に評価させます。これが $V(s)$ の計算に相当します。

プロンプト例: 「提案された3つの案それぞれについて、実現可能性とリスクの観点から評価し、10点満点でスコアをつけてください。また、その理由を論理的に述べてください。」

手順C: 選抜と実行（Select & Run）#

評価に基づき、最も有望なルートを選択して詳細化させます。

プロンプト例: 「最もスコアが高く、現実的な案を選択してください。その案に基づいて、具体的な解決策をステップバイステップで記述してください。」

手順D: バックトラッキングの模倣（擬似DFS）#

もし結果が思わしくない場合、意図的に手前に戻ります。

プロンプト例: 「この解決策では△△という問題が生じました。手順Bの評価に戻り、2番目に有望だった案（案X）について、同様に詳細化してみてください。」

結論#

ToTは、魔法のような手法ではなく、**「複数の選択肢を持つ（ベクトル集合）」「先読みして評価する（目的関数）」「ダメな案は捨てる（フィルタリング）」**という、人間が意識的に行っている思考プロセスをアルゴリズムとして定式化したものです。この構造を意識してプロンプトを設計することで、LLMの推論精度を大幅に高めることが可能になります。