論文解説: Tree of Thoughts — LLMによる探索的問題解決フレームワーク

論文概要（Abstract）

Tree of Thoughts（ToT）は、LLMの推論を木構造探索として定式化する推論フレームワークです。Yao et al.（2023, Princeton/DeepMind）は、Chain-of-Thought（CoT）の線形的な推論をBFS/DFSによる木探索に拡張し、複数の思考パスの並行展開・評価・バックトラックを可能にしました。Game of 24（数字パズル）でCoTの4%に対して74%の成功率を達成し、NeurIPS 2023に採択されています。

この記事は Zenn記事: 2026年版プロンプトテクニック大全：8手法の使い分けとコンテキスト設計の深掘りです。

情報源

arXiv ID: 2305.10601
URL: https://arxiv.org/abs/2305.10601
著者: Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths et al.
発表年: 2023（NeurIPS 2023採択）
分野: cs.CL, cs.AI, cs.LG

背景と動機（Background & Motivation）

CoTやSelf-Consistencyは推論性能を向上させましたが、本質的な制約があります。CoTは左から右への逐次的なトークン生成プロセスであり、一度生成を開始すると「この方向は間違いだ」と気づいてもバックトラックできません。Self-Consistencyは複数の独立した推論パスをサンプリングしますが、各パス間で情報の共有や協調はありません。

人間の問題解決を考えると、特に複雑な問題では「まず候補を複数列挙し、有望なものを深掘りし、行き詰まったら別の候補に戻る」という探索的なアプローチを取ります。これは認知科学で「Dual Process Theory」（System 1の直感的思考とSystem 2の熟慮的思考）として知られる枠組みと対応します。

Yao et al.は、この人間の熟慮的問題解決プロセスをLLMに適用するために、古典的なAI探索アルゴリズム（BFS/DFS）とLLMの推論能力を組み合わせるTree of Thoughtsフレームワークを提案しました。

主要な貢献（Key Contributions）

貢献1: LLMの推論を「思考」を単位とした木構造探索として定式化。各思考ノードの生成・評価・探索を分離したモジュラーなフレームワークを設計
貢献2: Game of 24でCoTの4%に対して74%、Creative Writingで人間評価のCoherence指標で7.56（CoT: 6.19）を達成
貢献3: BFS（幅優先探索）とDFS（深さ優先探索）の使い分け指針を示し、タスク特性に応じた探索戦略の選択方法を提案

技術的詳細（Technical Details）

ToTの形式的定義

ToTは以下の4つのコンポーネントから構成されます。

1. 思考の分解（Thought Decomposition）

問題を中間思考ステップ $z_1, z_2, \ldots, z_T$ の系列に分解します。各 $z_t$ は問題の部分解を表す自然言語テキストです。

\[\text{Problem} \rightarrow z_1 \rightarrow z_2 \rightarrow \cdots \rightarrow z_T \rightarrow \text{Solution}\]

CoTでは $T=1$（全推論を一度に生成）ですが、ToTでは $T > 1$ とし、各ステップで複数の候補を生成します。

2. 思考の生成（Thought Generator）

各ステップ $t$ で、現在の状態 $s = [x, z_1, \ldots, z_{t-1}]$ から $k$ 個の候補思考を生成します。

\[z_t^{(1)}, z_t^{(2)}, \ldots, z_t^{(k)} \sim G(s, k)\]

ここで $G$ は生成関数で、以下の2つの戦略があります。

Sample: 温度 $T > 0$ でi.i.d.にサンプリング。多様性が必要なタスク向け
Propose: 1回のプロンプトで $k$ 個の候補を一度に提案させる。候補間の多様性を制御可能

3. 状態評価（State Evaluator）

各候補思考の有望性を評価する関数 $V(s)$ を定義します。

\[V(s) = V([x, z_1, \ldots, z_t])\]

評価戦略は2つあります。

Value: LLMに状態を1-10のスケールで評価させる。「この部分解から正解に到達できる確率は？」
Vote: 複数の候補を比較させ、最も有望なものに投票。「これらの候補の中で最も正解に近いのは？」

4. 探索アルゴリズム（Search Algorithm）

生成された候補と評価値を使って、解空間を探索します。

BFS（幅優先探索）: 各深さレベルで上位 $b$ 個の状態を保持

\[S_t = \text{top-}b\{s' : s' = [s, z_t^{(j)}], s \in S_{t-1}, j = 1, \ldots, k\}\]

ここで $b$ はビーム幅（beam width）です。

DFS（深さ優先探索）: 有望な枝を優先的に深く探索し、行き詰まったらバックトラック

\[\text{if } V(s) < v_{\text{threshold}}: \text{backtrack}\]

Game of 24の具体例

Game of 24は「4つの数字を四則演算で組み合わせて24を作る」パズルです。

入力: 4, 9, 10, 13

ToTの探索過程:

ステップ1: 最初の演算を選択（k=5候補生成）
  候補A: 13 - 9 = 4  → 残り {4, 4, 10}
  候補B: 10 - 4 = 6  → 残り {6, 9, 13}
  候補C: 13 - 4 = 9  → 残り {9, 9, 10}
  候補D: 4 + 9 = 13  → 残り {10, 13, 13}
  候補E: 9 + 10 = 19 → 残り {4, 13, 19}

ステップ1評価: 候補Bが最有望（6 × 4 = 24の可能性）

ステップ2: 候補Bから続行（k=5候補生成）
  候補B1: 6 × 13 = 78 → 残り {9, 78} → 評価: 低（24を作りにくい）
  候補B2: 13 - 6 = 7  → 残り {7, 9}  → 評価: 低
  候補B3: 13 - 9 = 4  → 残り {4, 6}  → 評価: 高（4 × 6 = 24!）

ステップ3: 候補B3から続行
  4 × 6 = 24 ✅

解: (10 - 4) = 6, (13 - 9) = 4, 4 × 6 = 24

アルゴリズム実装

  
from dataclasses import dataclass
from openai import OpenAI

@dataclass
class ThoughtNode:
    """ToTの思考ノード"""
    state: str
    value: float
    children: list["ThoughtNode"]
    depth: int

def tree_of_thoughts_bfs(
    problem: str,
    max_depth: int = 3,
    beam_width: int = 5,
    n_candidates: int = 5,
    model: str = "gpt-4"
) -> str:
    """Tree of Thoughts (BFS版) の実装

    Args:
        problem: 解きたい問題文
        max_depth: 探索の最大深さ
        beam_width: 各深さレベルで保持する状態数
        n_candidates: 各ステップでの候補生成数
        model: 使用するモデルID

    Returns:
        最良の解
    """
    client = OpenAI()

    # 初期状態
    current_states = [problem]

    for depth in range(max_depth):
        all_candidates = []

        for state in current_states:
            # 思考の生成（Propose戦略）
            candidates = generate_thoughts(
                client, model, state, n_candidates
            )

            # 各候補を評価
            for candidate in candidates:
                new_state = f"{state}\n→ {candidate}"
                value = evaluate_state(client, model, new_state, problem)
                all_candidates.append((new_state, value))

        # 上位beam_width個を選択
        all_candidates.sort(key=lambda x: x[1], reverse=True)
        current_states = [s for s, v in all_candidates[:beam_width]]

    # 最良の状態から最終回答を抽出
    return extract_solution(client, model, current_states[0], problem)


def generate_thoughts(
    client: OpenAI,
    model: str,
    state: str,
    n: int
) -> list[str]:
    """現在の状態からn個の候補思考を生成

    Args:
        client: OpenAIクライアント
        model: モデルID
        state: 現在の状態テキスト
        n: 生成する候補数

    Returns:
        候補思考のリスト
    """
    response = client.chat.completions.create(
        model=model,
        messages=[{
            "role": "user",
            "content": (
                f"現在の状態:\n{state}\n\n"
                f"次のステップとして{n}個の異なるアプローチを提案してください。"
                f"各アプローチを番号付きで簡潔に記述してください。"
            )
        }],
        temperature=0.7
    )
    text = response.choices[0].message.content
    return parse_candidates(text, n)


def evaluate_state(
    client: OpenAI,
    model: str,
    state: str,
    original_problem: str
) -> float:
    """状態の有望性を0-1のスコアで評価

    Args:
        client: OpenAIクライアント
        model: モデルID
        state: 評価対象の状態テキスト
        original_problem: 元の問題文

    Returns:
        0-1の有望性スコア
    """
    response = client.chat.completions.create(
        model=model,
        messages=[{
            "role": "user",
            "content": (
                f"問題: {original_problem}\n"
                f"現在の進捗:\n{state}\n\n"
                f"この進捗から正解に到達できる確率を"
                f"0.0〜1.0で評価してください。数値のみ回答。"
            )
        }],
        temperature=0
    )
    try:
        return float(response.choices[0].message.content.strip())
    except ValueError:
        return 0.5

BFS vs DFSの選択指針

特性	BFS	DFS
適したタスク	候補の評価が信頼できる場合	深い探索が必要な場合
メモリ使用量	$O(b \times d)$	$O(d)$
API呼び出し	多い（広く探索）	少ない（深く探索）
バックトラック	暗黙的（低スコアを枝刈り）	明示的（閾値未満で戻る）
例	Game of 24	Creative Writing

ここで $b$ はビーム幅、$d$ は最大深さです。

実装のポイント（Implementation）

タスク依存の設計要素

ToTを新しいタスクに適用する際、以下の3要素を設計する必要があります。

思考の粒度: Game of 24では「1つの演算」、Creative Writingでは「1段落」が1思考。粒度が細かすぎると探索コストが増大し、粗すぎると探索の意味がなくなる
評価プロンプト: タスクに応じた評価基準の設計。Game of 24では「24を作れるか」、Creative Writingでは「文章の一貫性」
探索パラメータ: ビーム幅 $b$（広さ）と最大深さ $d$（深さ）のバランス。API呼び出し回数は $O(b \times k \times d)$ に比例

コスト見積もり

ToTのAPI呼び出し回数は以下の式で推定できます。

\[C = \sum_{t=1}^{d} |S_t| \times (k + 1)\]

ここで $

S_t

$ は深さ $t$ での状態数（BFSでは $\min(b,

S_{t-1}

\times k)$）、$k$ は候補数、$+1$ は評価呼び出しです。

Game of 24の場合（$b=5, k=5, d=3$）: $C = 5 \times 6 \times 3 = 90$ 回のAPI呼び出し。CoTの1回と比較して約90倍のコストです。

よくあるバグ

評価プロンプトの不整合: 評価プロンプトがタスクの成功基準と一致しない場合、探索が間違った方向に進む
探索の発散: ビーム幅が大きすぎると探索が広がりすぎてコストが爆発。段階的に増やすのが安全
パース失敗: 候補生成や評価のLLM出力を構造化データにパースする処理が脆弱だと、探索全体が破綻

実験結果（Results）

Game of 24

手法	成功率
標準プロンプト	7.3%
CoT	4.0%
CoT + Self-Consistency (100サンプル)	9.0%
ToT (BFS, b=5)	74.0%

CoTの4%から74%への劇的な改善は、このタスクが「バックトラック」を必要とすることを示しています。線形的な推論では最初の演算選択の失敗から回復できませんが、ToTでは複数の演算を並行評価し、最も有望な枝を選択できます。

Creative Writing

手法	Coherence (1-10)
標準プロンプト	6.19
CoT	6.93
ToT (DFS)	7.56

Creative Writingではコヒーレンス（文章の一貫性）が改善。段落ごとの計画とバックトラックにより、物語全体の構造が改善されました。

実運用への応用（Practical Applications）

ToTは以下の場面で特に有効です。ただし、コストが高いため適用範囲は限定的です。

戦略・計画立案: 事業戦略の選択肢を複数展開し、各シナリオの結末を評価して最良の戦略を選択。コンサルティングの「仮説駆動アプローチ」と類似した使い方が可能です。

コード生成: 複雑なアルゴリズムの実装で、複数のアプローチ（動的計画法、貪欲法、分割統治法）を並行生成し、テスト通過率で評価。SWE-bench等のコード生成ベンチマークでの適用が研究されています。

適用すべきでないケース: 単純な分類・翻訳・要約タスク。これらはCoTやFew-shotで十分であり、ToTのコスト（90倍以上のAPI呼び出し）は正当化できません。

まとめと今後の展望

Tree of Thoughtsは、LLMの推論を古典的なAI探索と融合させた画期的なフレームワークです。CoTの線形的制約を克服し、バックトラックや並列探索を可能にすることで、特に組合せ最適化や計画立案タスクで劇的な性能向上を実現しました。

実務での適用はコスト面の制約がありますが、「正解が1つに定まらない複雑な意思決定タスク」では投資対効果が高いです。今後は、探索コストの削減（効率的な枝刈り、キャッシュ活用）や、学習による探索戦略の最適化が研究の方向性として期待されます。

参考文献

arXiv: https://arxiv.org/abs/2305.10601
Code: https://github.com/princeton-nlp/tree-of-thought-llm
Related Zenn article: https://zenn.dev/0h_n0/articles/8d05ea9be7e0f3

📄 論文解説: Tree of Thoughts — LLMによる探索的問題解決フレームワーク

論文概要（Abstract）

情報源

背景と動機（Background & Motivation）

主要な貢献（Key Contributions）

技術的詳細（Technical Details）

ToTの形式的定義

Game of 24の具体例

アルゴリズム実装

BFS vs DFSの選択指針

実装のポイント（Implementation）

タスク依存の設計要素

コスト見積もり

よくあるバグ

実験結果（Results）

Game of 24

Creative Writing

実運用への応用（Practical Applications）

関連研究（Related Work）

まとめと今後の展望

参考文献

📄 論文解説: Tree of Thoughts — LLMによる探索的問題解決フレームワーク

論文概要（Abstract）

情報源

背景と動機（Background & Motivation）

主要な貢献（Key Contributions）

技術的詳細（Technical Details）

ToTの形式的定義

Game of 24の具体例

アルゴリズム実装

BFS vs DFSの選択指針

実装のポイント（Implementation）

タスク依存の設計要素

コスト見積もり

よくあるバグ

実験結果（Results）

Game of 24

Creative Writing

実運用への応用（Practical Applications）

関連研究（Related Work）

まとめと今後の展望

参考文献

関連記事

📄 論文解説: Large Language Models are Zero-Shot Reasoners

📄 論文解説: Chain-of-Thought Prompting Elicits Reasoning in Large Language Models

📄 論文解説: Self-Consistency Improves Chain of Thought Reasoning in Language Models