0Pricing
AI Prompt Engineering · レッスン

Tree-of-Thought探索

思考を分岐させて評価します。

「Tree-of-Thought探索」はCoddyKit上の無料AI Prompt Engineeringレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはAI Prompt Engineering学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 AI Prompt Engineeringコースには全4レッスンが含まれています。

チェーンからツリーへ

Tree-of-Thought（ToT、Yao et al., 2023）は、Chain-of-Thoughtを1本の線形経路から、部分解の探索木へと一般化したものです。各ノードは一貫した中間思考を表し、各分岐では異なる続きを探索します。

これにより、モデルは熟考できるようになります。複数の次のステップを生成して評価し、有望なものを残し、行き止まりからバックトラックできます。最初のアイデアに決め打ちするのではなく、体系的な問題解決を模倣します。

class ThoughtNode:
    def __init__(self, state, parent=None):
        self.state = state      # partial solution / reasoning so far
        self.parent = parent
        self.children = []
        self.value = None       # evaluator score

ToTの4つの構成要素

ToTシステムには、4つの設計上の選択肢があります。思考の分解（1つのステップとは何か）、思考生成器（次のステップをどのように提案するか）、状態評価器（部分解をどのように評価するか）、そして探索アルゴリズム（BFS、DFS、またはbest-first）です。

それぞれは独立したプロンプトまたはポリシーです。ToTを設計するには、タスクに対してこの4つすべてを定義する必要があります。

tot = {
    'decompose': step_definition,   # e.g. one equation, one move
    'generate':  propose_thoughts,  # sampling or proposal prompt
    'evaluate':  score_state,        # value/vote prompt
    'search':    bfs_with_beam,      # BFS | DFS | best-first
}

候補となる思考の生成

生成戦略は2つあります。適度な温度で複数の独立した思考をサンプリングする方法（探索空間が豊かな場合に適しています）と、1つのプロンプトで異なる次のステップの集合を提案する方法（明確に異なる選択肢が必要な場合に適しています）です。

分岐数は小さくしてください（多くの場合3〜5）。候補が多すぎると探索量とコストが爆発的に増加します。

def propose_thoughts(state, k=4):
    prompt = (
        'Given the partial solution below, propose ' + str(k) +
        ' DISTINCT possible next steps.\n' + state
    )
    return parse_list(llm(prompt, temperature=0.7))

状態の評価

状態評価器があることで、ToTは単なるランダムサンプリングではなくなります。状態を1〜10で評価して問題解決への近さを示す価値プロンプトや、複数の状態のうちどれが最も有望かを問う投票プロンプトによって、部分解の有望度を評価します。

候補間で投票するほうが、絶対値で評価するより頑健なことがよくあります。モデルにとっては、相対的な判断のほうが容易だからです。

def score_state(state):
    prompt = (
        'Rate how likely this partial solution leads to a correct '
        'final answer. Reply sure / likely / impossible.\n' + state
    )
    label = llm(prompt, temperature=0).strip().lower()
    return {'sure': 1.0, 'likely': 0.5, 'impossible': 0.0}.get(label, 0.3)

ビームサーチを用いたBFS

幅優先のToTでは、フロンティアにあるすべてのノードを一度に1レベルずつ展開し、その後、評価スコア上位のb個だけを残します（これがビームです）。これにより、複数の経路を並行して探索しながら、探索の爆発を抑えられます。

ビーム幅bは、探索の広さとコストのトレードオフを決めます。構造化されたパズルでは、幅5、深さ3が一般的な出発点です。

def bfs_with_beam(root, depth, branch, beam):
    frontier = [root]
    for _ in range(depth):
        nxt = []
        for node in frontier:
            for t in propose_thoughts(node.state, branch):
                child = ThoughtNode(node.state + '\n' + t, node)
                child.value = score_state(child.state)
                nxt.append(child)
        frontier = sorted(nxt, key=lambda n: -n.value)[:beam]
    return max(frontier, key=lambda n: n.value)

バックトラッキングを用いたDFS

深さ優先のToTでは、最も有望な分岐を深く掘り下げ、評価器が状態を見込みなしと判断したらバックトラックします。これは、制約パズルのように実行不可能な部分状態を明確に定義できる問題に適しています。

不可能な分岐を早期に枝刈りすることが、主な効率化につながります。見込みのない部分木を無駄に展開せずに済むためです。

def dfs(node, depth, branch, prune=0.2):
    if depth == 0 or is_solution(node.state):
        return node
    for t in propose_thoughts(node.state, branch):
        child = ThoughtNode(node.state + '\n' + t, node)
        child.value = score_state(child.state)
        if child.value < prune:
            continue                      # backtrack: prune dead end
        res = dfs(child, depth - 1, branch, prune)
        if res and is_solution(res.state):
            return res
    return None

ToTとSelf-consistencyの比較

Self-consistencyは、独立した完全なチェーンをサンプリングして投票します。一方ToTは、中間評価とバックトラッキングによって探索を積極的に誘導し、有望な部分に計算量を割り当てます。

ToTは、計画や探索が必要な問題、または初期の誤りが致命的になる問題（Game of 24、クロスワード、計画）で力を発揮します。多様なチェーンを低コストで生成でき、回答が離散的なタスクでは、self-consistencyのほうが単純で十分なことがよくあります。

# Rule of thumb
# - reachable by diverse single passes  -> self-consistency
# - needs lookahead / pruning / backtrack -> tree-of-thought
# ToT cost ~ branch * depth * beam * (gen + eval) LLM calls

コストの爆発と予算

ToTには高いコストがかかります。各ノードで生成と評価の呼び出しが発生するためです。総コストはおおよそ、分岐数 × 深さ × ビーム幅に、評価器の呼び出し分を加えたものに比例します。厳格な予算がなければ、コストは膨れ上がります。

LLMの総呼び出し回数に上限を設け、best-first探索を使って価値の高いフロンティアに予算を使い、予算を使い切った場合は最良の部分解にフォールバックしてください。

import heapq

def best_first(root, max_calls):
    heap = [(-root.value, root)]
    best, calls = root, 0
    while heap and calls < max_calls:
        _, node = heapq.heappop(heap)
        for t in propose_thoughts(node.state, 3):
            calls += 1
            child = ThoughtNode(node.state + '\n' + t, node)
            child.value = score_state(child.state); calls += 1
            if child.value > best.value:
                best = child
            heapq.heappush(heap, (-child.value, child))
    return best

評価器の信頼性

ToTの品質は評価器の品質次第です。キャリブレーションされていない評価器は、正しい分岐を枝刈りしたり、行き止まりを追い続けたりします。各状態を複数回評価して投票する、良い状態と悪い状態のfew-shot例を用意する、外部の検証器（単体テスト、ソルバー、チェッカー）を使うなどの方法で改善してください。

客観的なチェック（方程式が成立するか、コードが通るか）が存在する場合は、LLMの判断よりもそちらを優先してください。

def robust_eval(state, votes=3):
    scores = [score_state(state) for _ in range(votes)]
    return sum(scores) / votes        # average to reduce judge noise
# Even better: replace with a deterministic verifier when available

実用性

ToTが効果を発揮するのは、限定的ではあるものの価値の高い問題群です。多段階の計画、組合せパズル、そして全体を解くよりも1ステップを検証するほうが安価なタスクが該当します。日常的なプロンプトのほとんどでは、ToTは過剰です。

強力な組み込み探索機能を持つ推論特化モデルでは、明示的なToTの枠組みを追加しても、コストが増えるだけで大きな効果が得られないことがあります。導入前にベンチマークしてください。

def choose_strategy(task):
    if task.requires_search and task.step_verifiable:
        return 'tree-of-thought'
    if task.discrete_answer:
        return 'self-consistency'
    return 'single chain-of-thought'

最小構成のToTソルバー

エンドツーエンドでは、ステップを定義し、小さな思考の分岐を提案し、それぞれを評価し（投票または検証器を使用）、呼び出し予算の範囲内でBFS-beamまたはDFS-backtrackによって探索し、最良の終端状態を返します。

ノード数と評価スコアを計測し、タスクごとに分岐数、深さ、ビーム幅を実測に基づいて調整できるようにしてください。

def solve(problem, branch=4, depth=3, beam=5, budget=200):
    root = ThoughtNode(problem)
    root.value = score_state(root.state)
    node = bfs_with_beam(root, depth, branch, beam)
    return extract_solution(node.state)

クイックチェック

適切な熟考戦略を選んでみましょう。

まとめ

重要なポイント：

  • ToTは、思考の生成、状態の評価、探索アルゴリズムを備えた探索木へとCoTを一般化したものです。
  • ビームを用いたBFS、またはバックトラッキングを用いたDFSを使い、爆発を抑えるため分岐数は小さく保ちます。
  • 状態評価器が核心です。投票や外部の検証器で堅牢性を高めてください。
  • コストは分岐数 × 深さ × ビーム幅に比例するため、best-first探索などを使って呼び出し予算を設定してください。
  • ToTは、計画や組合せに関する、ステップを検証できる問題に限定して使ってください。日常的なプロンプトには過剰です。

よくある質問

「Tree-of-Thought探索」レッスンは無料ですか？

はい。「Tree-of-Thought探索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、AI Prompt Engineeringコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 AI Prompt Engineeringコースには全4レッスンが含まれています。

「Tree-of-Thought探索」で何を学びますか？

思考を分岐させて評価します。 ブラウザで直接実行するハンズオンコードでAI Prompt Engineeringを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

AI Prompt Engineeringを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのAI Prompt Engineeringは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「Tree-of-Thought探索」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このAI Prompt Engineeringレッスンでコードを書いて実行できますか？

はい。すべてのAI Prompt Engineeringレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. Chain-of-Thoughtプロンプティング
  2. Self-Consistencyサンプリング
  3. Tree-of-Thought探索
  4. 推論プロンプトが役立つ場面
← AI Prompt Engineeringに戻る