06. Tree of Thoughts:从线性循环到搜索式推理

ReAct 和 Plan-Execute 都有个共同假设:任务可以被顺序执行,走错了就回头。但有些任务走到第 3 步才能知道第 1 步选错了,而回头的成本非常高。典型的例子是:

复杂的数学推理——多个候选思路哪个走得通,需要走几步才能判断
谜题、规划类问题——24 点、路径规划、棋类决策
创意任务——生成 5 个方向的草稿再选最好的,比直接改一个草稿效果好

这类问题的共同特征是路径多、单路径验证成本高、选错的沉没成本大。线性循环(ReAct)不擅长这种。

Tree of Thoughts(简称 ToT)就是为这类任务设计的。它把 Agent 的推理过程从"一条路"升级到"一棵树":每一步生成多个候选、评估它们、选最有希望的几条继续扩展、回溯剪枝。

核心思想:生成 + 评估 + 搜索

Princeton 和 Google DeepMind 在 2023 年的论文 "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" 给出了这个框架。核心只有三个动作:

Thought Generator——给定当前状态,生成 K 个可能的下一步候选 State Evaluator——给每个候选打分,判断它"值得继续探索"的程度 Search Algorithm——BFS / DFS / Beam Search,在这棵树上走

用伪代码描述就是:

function ToT(initial_state):
    queue = [initial_state]
    while queue not empty:
        state = queue.pop()
        if is_goal(state):
            return state.path
        candidates = generate_next(state, k=5)
        scored = [(c, evaluate(c)) for c in candidates]
        top_n = select_top(scored, n=3)
        for c, _ in top_n:
            queue.push(c)
    return failed

三个部分都由 LLM 完成。Generator 是"创意";Evaluator 是"鉴赏力";Search 是"策略"——三位一体。

手写一个 24 点 ToT

24 点是 ToT 论文里最经典的例子:给你 4 个 1~9 的数字,用四则运算让结果等于 24。GPT-4 用普通 CoT 成功率只有 4%,用 ToT 能到 74%。这种跃升非常说明问题。

from openai import OpenAI
from dataclasses import dataclass, field

client = OpenAI()

@dataclass
class Node:
    numbers: list[float]      # 剩余的数
    ops: list[str]            # 已执行的操作
    score: float = 0.0
    children: list["Node"] = field(default_factory=list)

def generate_moves(numbers: list[float], k: int = 5) -> list[str]:
    """让 LLM 从当前数字列表中提出 k 个可能的下一步操作"""
    prompt = f"""从这些数字中选两个,用 +, -, *, / 之一合并。
当前数字: {numbers}
给出 {k} 个可能的下一步操作,格式为 "a op b = c",每行一个。
例子: "3 * 4 = 12"
"""
    resp = client.chat.completions.create(
        model="gpt-4o",
        messages=[{"role": "user", "content": prompt}],
    )
    return [l.strip() for l in resp.choices[0].message.content.split("\n") if "=" in l]

def evaluate_state(numbers: list[float]) -> float:
    """让 LLM 评估当前状态"值得继续探索"的程度(0-1)"""
    prompt = f"""剩下这些数字: {numbers},目标是通过四则运算得到 24。
判断:从这个状态出发,还有多大可能凑出 24?
只回答一个数字: 1.0(非常有希望)、0.5(一般)、0.1(希望渺茫)"""
    resp = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": prompt}],
    )
    try:
        return float(resp.choices[0].message.content.strip())
    except:
        return 0.3

def apply_move(numbers: list[float], move: str) -> list[float]:
    """把操作应用到数字列表上"""
    left, rest = move.split("=")
    a, op, b = left.strip().split()
    a, b, c = float(a), float(b), float(rest.strip())
    new_nums = numbers.copy()
    new_nums.remove(a); new_nums.remove(b); new_nums.append(c)
    return new_nums

def tot_search(numbers: list[float], beam_width: int = 3, depth_limit: int = 3):
    frontier = [Node(numbers=numbers, ops=[])]
    for _ in range(depth_limit):
        new_frontier = []
        for node in frontier:
            if len(node.numbers) == 1:
                if abs(node.numbers[0] - 24) < 1e-6:
                    return node.ops
                continue
            moves = generate_moves(node.numbers, k=5)
            for move in moves:
                try:
                    new_nums = apply_move(node.numbers, move)
                    score = evaluate_state(new_nums)
                    child = Node(numbers=new_nums, ops=node.ops + [move], score=score)
                    new_frontier.append(child)
                except: continue
        frontier = sorted(new_frontier, key=lambda n: -n.score)[:beam_width]
    return None

print(tot_search([3, 4, 7, 8]))

这是一个 Beam Search 实现:每一层保留 top-3 最有希望的节点。对 24 点这种深度不大但分支多的问题,效果显著。完整的 ToT 库还可以做 DFS、BFS 或更复杂的 MCTS,核心差别在"往哪里走"的策略,Evaluator 和 Generator 的实现是一样的。

三种搜索策略的取舍

BFS(广度优先)——每一层都完全展开,保证找到最浅路径。适合:分支少但最优解浅,例如 3~5 步内能解决的问题。缺点:分支多时状态爆炸。

DFS(深度优先)+ 剪枝——一条路走到黑,碰壁就回溯。适合:深路径、大部分分支都是死路。LLM 的评估器负责及时剪枝,避免死路走太深。

Beam Search——每层保留 top-K 最有希望的节点,其他丢弃。是实践中最常用的。计算量可控,对中等复杂度问题效果很好。上面的代码用的就是这种。

MCTS(蒙特卡洛树搜索)——每个节点记录"访问次数"和"成功率",用 UCB 公式平衡探索和利用。需要能做 rollout(从当前节点模拟到终局拿反馈),所以更适合有明确胜负/奖励信号的场景,比如游戏、可验证的编程题。

选哪个的经验:能验证状态好坏、分支不爆炸,用 Beam Search;验证成本高、搜索空间大,用 MCTS;问题结构清晰、有明显最优终止,用 BFS/DFS。

ToT 的真实代价

ToT 非常贵。同样一个任务:

ReAct:10 步 × 1 次调用/步 = 10 次 LLM 调用
Plan-Execute:1 次 plan + 10 次 execute = 11 次
ToT(Beam=3, 深度=4):每层 3 节点 × 每节点 5 生成 + 15 评估 = 每层 30 次 × 4 层 = 120 次

ToT 的成本通常是 ReAct 的 10~20 倍。这意味着它只值得用在那些"一次 ReAct 跑不对,反复 retry 也跑不对"的硬骨头任务上。

Anthropic 和 OpenAI 的实际做法是:只在检测到普通方法失败后才启用 ToT。第一次尝试 ReAct,失败或低置信,切到 Plan-Execute,再失败才上 ToT。这种分层 fallback 把平均成本压回 ReAct 的水平,只有难题才付 ToT 的价。

LATS:ToT + Reflection 的合体

2023 年底有个叫 Language Agent Tree Search (LATS) 的扩展,把 ToT 和 Reflection 结合起来。每个节点不只是生成和评估,还要反思:如果这条路走不通,写一段反思留在节点上,往下扩展的节点会看到这段反思,避免重蹈覆辙。

这个组合在 HumanEval 和 WebShop 这些 benchmark 上的成功率比纯 ToT 又提升 5~10%。代价是每个节点多一次反思调用,成本再涨。

推理模型让 ToT 有点尴尬

到了 2026 年,ToT 的位置有点尴尬——o1、o3、Claude extended thinking 这类推理模型内部已经在做类似 ToT 的事。它们在 reasoning tokens 里展开多条思路、自我评估、剪枝,只是不对外暴露。

所以对于"需要深度搜索的难题",2026 年的主流做法变成了:

第一选择:用推理模型 + 长 reasoning budget。把搜索交给模型内部,代码外部保持 ReAct 结构
第二选择:显式 ToT,只在模型内部搜索不够、或需要可控剪枝策略的场景使用
第三选择:推理模型 + 外层 ToT——模型内部做短链搜索,外层用 Beam Search 组织候选

显式 ToT 的价值现在主要在三个地方:需要并行探索多个方向(例如同时生成 10 个广告文案);需要人类可见的搜索过程(研究、教学);需要特定领域的评估器(非 LLM 的打分函数,比如单元测试、数值校验)。

小结

ToT 不是一个你每天都要用的模式。它是工具箱里"对付难题的那把大锤"。理解它的价值不只是"多一个 pattern",而是理解一个更大的原则:当一条路径不够时,并行探索多条;当探索成本高时,评估和剪枝要狠。这个原则适用于所有需要应对不确定性的 Agent 设计。

下一篇开始讲 Agent 最难的部分——记忆系统。前面几篇所有的循环、规划、反思,都在一次任务内部。一旦任务跨越多次对话、多个 session,Agent 需要的就不只是"这一次想清楚",而是"记得上一次"。那是完全不一样的问题。