思维树与 LATS:审慎搜索

思维树与 LATS:审慎搜索

本节摘要:单条思维链没有回溯的余地——第一步错了,后面每一步都在错误的前提下打转。思维树(Tree of Thoughts, Yao 等人, 2023)把推理变成一棵带自评的树:每个节点是一个「思维」,每条边是一次扩展,每个节点都有一个「多 promising」的分数。LATS(Zhou 等人, 2024)更进一步,把 ToT、ReAct、Reflexion 统一进蒙特卡洛树搜索(MCTS)。结果是戏剧性的:24 点游戏从 CoT 的 4% 跃升到 ToT 的 74%;LATS 在 HumanEval 上达到 92.7% 的 pass@1。本节讲透「把推理当搜索」的代价与回报,用标准库手写一个 ToT 的 BFS 搜索和一个玩具 LATS 的 MCTS 循环,并给出 2026 年的判断准则——什么时候值得为搜索付那 100~1000 倍的 token 代价,什么时候单条轨迹就够了。

对应原课程:Phase 14 · Lesson 04 · tree-of-thoughts-lats(原英文 phases/14-agent-engineering/04-tree-of-thoughts-lats/docs/en.md)。

学习目标

阅读完本节,你应当能够:

1. 把推理框架成搜索:节点是「思维」,边是「扩展」,值是「多 promising」。
2. 用标准库实现一个 ToT 风格的 BFS 树搜索,带自评打分。
3. 把它扩展成一个玩具 LATS 的 MCTS 循环:选择 / 扩展 / 模拟 / 回传。
4. 判断什么时候搜索值得那个 token 乘数(24 点、复杂代码),什么时候单条轨迹就够了(简单问答)。

一、问题与直觉

思维链是一条线性漫步。如果第一步错了,后面每一步都在错误的前提下工作。在 24 点游戏(用四个数字配 + − × ÷ 凑出 24)上,GPT-4 的 CoT 只有 4% 的准确率——模型早早挑错了子表达式,再也回不来。

推理真正需要的是:提出多个候选、评估它们、挑出有希望的、在死胡同时回溯。这就是搜索。思维树和 LATS 是两种经典的构造。

思维树(Yao 等人,NeurIPS 2023)

每个节点是一个连贯的中间步骤(「一个思维」)。每个节点可以扩展出 K 个子思维。LLM 用一个打分提示给每个节点自评。搜索在树上展开——BFS、DFS 或束搜索(beam)。

自评是承重部件。论文给了三种变体:sure / likely / impossible 三分类、1..10 数值打分、候选间投票。三种都在 24 点上把 CoT 的 4% 大幅拉开(GPT-4 上到 74%)。

LATS(Zhou 等人,ICML 2024)

LATS 把 ToT、ReAct、Reflexion 统一进 MCTS。LLM 扮演三个角色:

• 策略(Policy):提出候选的下一步行动(ReAct 风格)。
• 价值函数(Value function):给一条部分轨迹打分(ToT 风格自评)。
• 自我反思者(Self-reflector):失败时写一段自然语言反思(Reflexion 风格),用它重新播种未来的 rollout。

环境反馈(观察)混进价值函数,所以搜索是由真实工具结果驱动的,而不只是模型的主观意见。论文发表时的成绩:GPT-4 上 HumanEval pass@1 达 92.7%(当时 SOTA),GPT-3.5 上 WebShop 均分 75.9(逼近基于梯度的微调)。

MCTS,最小版本

每次迭代四个阶段:

1. 选择(Select) —— 用 UCT(树的置信上界)从根走到一个叶。
2. 扩展(Expand) —— 用策略生成 K 个子节点。
3. 模拟(Simulate) —— 从某个子节点用策略 rollout,用价值函数(或环境奖励)给叶打分。
4. 回传(Backpropagate) —— 沿路径向上更新访问计数和价值估计。

UCT 公式:Q(s, a) + c * sqrt(ln N(s) / N(s, a))。第一项是利用(exploitation),第二项是探索(exploration)。c 按任务调。

代价的现实

搜索会爆炸 token。ToT 在 24 点上用的是 CoT 的 100~1000 倍 token。LATS 类似。这不是免费的,把搜索留给:

• 单条轨迹明显不够的任务(24 点、复杂代码)。
• 正确性比墙钟时间更重要的任务。
• 有便宜、可靠价值函数的任务(代码的单测、数学的显式目标)。

如果你的任务只有一个正确答案,却配一个噪声大的评估器,搜索往往让事情更糟——它会找到一个「分数很高」的错误答案。

⚠️ 关键警示:搜索放大的是评估器的偏差。如果价值函数系统性偏好某类错误答案,搜索会以更高置信度找到那个错误答案。上搜索之前,先确认你的评估器比模型的一次性判断更可信。

2026 年的定位

大多数生产 Agent 不跑 LATS。它们跑 ReAct 加工具锚定的验证(第 05 节 CRITIC)。搜索出现在专门的利基里:

• 把测试当作价值函数的编码 Agent(HumanEval 风格)。
• 探索多条查询路径的深度研究 Agent。
• LangGraph 子图里规划繁重的工作流。

AlphaEvolve(原课程第 11 节)是 2025 年的极端:在代码上做进化搜索,用机器可检验的适应度,取得前沿进展(56 年来首次对 4×4 矩阵乘法的改进)。

二、从零实现

原课程 code/main.py 实现了:一个在「挑算术运算」风格任务上的小型 ToT BFS;一个在同一任务上的玩具 LATS MCTS 循环(选择/扩展/模拟/回传,带 UCT 选择);一个把符号分数与自评分数组合起来的价值函数。

核心骨架如下,用伪代码展示。

Step 1:ToT 的 BFS 搜索

def tot_bfs(root_state, expand, score, k=3, max_depth=4):
    frontier = [root_state]
    for depth in range(max_depth):
        if not frontier:
            break
        candidates = []
        for state in frontier:
            for child in expand(state, k):         # 每节点扩 K 个子思维
                candidates.append((child, score(child)))
        frontier = top_k(candidates, k)            # 只留分数最高的 K 个
        if any(is_goal(s) for s, _ in frontier):
            return best(frontier)
    return best(frontier)
​

Step 2:价值函数(符号分数 + 自评)

def value_function(state):
    symbolic = symbolic_score(state)      # 比如:离目标的距离
    self_eval = llm.score(state)          # 比如:sure/likely/impossible
    return 0.5 * symbolic + 0.5 * self_eval
​

Step 3:LATS 的 MCTS 循环

def lats_mcts(root, policy, value_fn, iterations=50, c=1.4):
    for _ in range(iterations):
        leaf = select(root, c)            # UCT 走到叶
        children = expand(leaf, policy)   # 策略生成子节点
        for child in children:
            reward = simulate(child, policy, value_fn)   # rollout + 打分
            backprop(child, reward)       # 沿路径更新 N 与 Q
    return best_child(root)
​

select 用 UCT 公式平衡利用与探索;backprop 把叶的奖励沿路径向上推,更新每个祖先的访问计数和价值估计。

运行 python3 code/main.py 会展示 ToT 用 BFS 每节点扩三个候选,对比 LATS 用 MCTS 收敛到最佳 rollout,并打印两者的 token 计数。

💡 设计要点:ToT 与 LATS 的差别不在「是不是树」,而在「怎么走树」。ToT 是穷举式 BFS(每层留 top-k),LATS 是采样式 MCTS(按 UCT 优先访问高潜力节点)。token 紧张时,束搜索 ToT 往往性价比更高;价值函数可靠时,LATS 能在更深树上找到更优解。

三、框架对比

对大多数生产场景,搜索不该是默认。它应该是任务复杂度门后的可选路径——只有当单条 ReAct 轨迹被证明不够、且你有可靠价值函数时才打开。

四、可复用产物

本节产出一份可复用技能(原课程 outputs/skill-search-policy.md):

• skill-search-policy.md:给定任务形状、预算、评估器保真度,在「线性 ReAct、ToT、LATS、进化搜索」之间做选择。它包含一份决策清单:任务是否有唯一正确答案?评估器是否比模型一次性判断更可信?墙钟时间有多紧?token 预算多大?据此输出推荐的搜索策略与参数(如 UCT 的 c、束宽 k)。

Python 代码(code/main.py)是独立可运行的玩具,ToT BFS 与 LATS MCTS 的骨架、UCT 选择、价值函数组合都是厂商无关的;把脚本式策略与价值函数换成真实 LLM 调用即可投入生产。

五、练习

1. (Easy) 用 UCT c=0.1 和 c=2.0 分别跑玩具 LATS。轨迹里发生了什么变化?
2. (Easy) 把价值函数换成一个更噪的打分器(加随机抖动)。MCTS 还能找到最佳叶吗?它能容忍的最低信噪比是多少?
3. (Medium) 实现束搜索 ToT(每层留 top-k)并与 BFS 对比。在 token 紧张时哪个更好?
4. (Hard) 读 LATS 论文第 5.1 节。复现 HumanEval 的轨迹计数:达到报告的 pass@1 需要多少次 rollout?
5. (Hard) 读 LATS 论文关于「LATS 在哪些情况下帮助较小」的讨论。写一段决策规则,把任务形状映射到搜索策略。

本节要点回顾

1. 思维链是线性漫步,没有回溯:第一步错了,后面全在错前提下打转;24 点上 GPT-4 CoT 只有 4%。
2. 思维树把推理变成带自评的树:节点是思维,边是扩展,每节点自评打分;24 点上到 74%。
3. LATS 用 MCTS 统一 ToT + ReAct + Reflexion:LLM 同时当策略、价值函数、自我反思者;HumanEval pass@1 达 92.7%。
4. MCTS 四阶段:选择(UCT)、扩展、模拟(rollout + 价值)、回传(更新计数与 Q)。
5. UCT 平衡利用与探索:Q(s,a) + c * sqrt(ln N(s) / N(s,a)),c 按任务调。
6. 搜索爆炸 token:ToT/LATS 是 CoT 的 100~1000 倍,不是免费的。
7. 上搜索的三个前提:单条轨迹明显不够、正确性重于墙钟时间、有便宜可靠的价值函数。
8. 评估器噪声大时搜索更糟:它会高置信地找到「分数很高」的错误答案。
9. 2026 年大多数生产 Agent 不跑 LATS:跑 ReAct + 工具锚定验证(CRITIC);搜索只在利基(编码、深度研究、规划繁重子图)。
10. AlphaEvolve 是极端:进化搜索 + 机器可检验适应度,取得前沿进展。

下一节,我们将进入「自我精炼与 CRITIC」——用一个模型扮演生成/反馈/精炼三个角色,再用外部工具硬化反馈步骤,定义 2026 年迭代改进的默认范式。