第20回　搜索式解码——MCTS、过程奖励与顿悟时刻

路口三岔莫忙走，先探虚实再回身。
一招若肯多试错，万步方能少走岔。

上回我们讲“测试时计算”：同一道题，多给点预算，就能把偶然性压下去。
但看官也看出来了：
上回的“多采样+投票”，更像是“人多力量大”，却不一定“越试越聪明”。

这一回我们要把“慢思考”真正练成武功——
不是盲目多试，而是像办案一样有章法地搜：

该先试哪条路？
试到半路发现不对，怎么回头？
走到哪一步就该判断“这条线索已经烂了”？

这便是：搜索式解码（Search-based Decoding）。
它的代表老武功之一，便是蒙特卡洛树搜索：MCTS。

一、把推理当成搜索：从“写作文”变成“走迷宫”

把大模型回答一个问题，想成一条“轨迹”：

状态：当前题目 + 你已经写出的推理/草稿
动作：下一步写什么（下一句、下一步计算、下一段代码）
终止：给出最终答案或到达长度上限

你就会发现：它就是第13回说的 MDP，只是状态变成了“文本上下文”。

于是“推理”也就变成了“在一棵巨大的树里选路径”：

树根：题目
每个分叉：下一步可能写的不同候选
一条从根到叶的路径：一条完整推理链

搜索式解码做的事就是：
别急着走第一条路，先在树上试探几条，再选最靠谱的那条。

二、MCTS 四步：选、扩、跑、回（像一场带记账的试错）

MCTS 的章法常被说成四步循环：

Selection（选择）：从根出发，按“既要探索、又要利用”的规则往下走
Expansion（扩展）：走到一个还没试全分叉的节点，就开一个新分叉
Simulation / Rollout（模拟）：从新分叉继续“随便走走/按策略走走”，走到终局，得到一个分数
Backpropagation（回传）：把这次分数沿路径往上记账，更新各节点的“前途估计”

看官若问它像什么？
像你做压轴题：

先挑一条思路写几步（选择）
发现关键岔口，补一个分支试试（扩展）
往下推到能判断对错/好坏的地方（模拟）
回头给这条思路打分，下次更倾向走好路（回传）

它与第12回老虎机的精神完全一致：
在选择分支时，用 UCB 一类“探索-利用”公式，既不死磕老路，也不放弃新路。

三、结果奖励 vs 过程奖励：只看终点，还是每一步都算账

搜索式解码要“选最好的路径”，就得有“好坏标准”。
这标准（奖励）常见两类：

1）结果奖励（Outcome / Result）

只在终点打分：

最终答案对不对？
最终代码能不能跑？
最终总结是否符合偏好？

这很像只看期末考试分数。
它的好处是简单；坏处是：
路上哪一步错了，你并不知道。

所以你会看到一种现象：
长推理链里，前面写得像样，后面某一步错了，结果全盘皆输；
而“只看终点”的信号，对前面那些步骤几乎没有指导作用。

2）过程奖励（Process）

对中间步骤也打分：

这一步推导是否合理？
这句代码是否有效？
这段解释是否与前文一致？

这像老师批改草稿：在错误发生的第一处就圈出来。

2024 有工作专门讨论“自动化过程监督”，试图更高效地收集过程级奖励/监督信号，用以提升数学推理等长链任务的可靠性。¹

你此刻先记住一句：
结果奖励像“只看答案”，过程奖励像“按步骤给分”。
后者更贵，却更能教会模型“哪里该回头”。

四、搜索式解码的三件套：生成器、评分器、搜索器

把工程抽象到极致，搜索式解码就是三件套：

生成器（Generator）：给一个状态，能提出若干候选下一步
评分器（Scorer / Verifier / Reward）：能给节点或整条路径打分
搜索器（Searcher）：决定预算怎么花、哪些分支值得继续

在 LLM 场景里：

生成器通常就是语言模型本身（采样 top-k/top-p，生成候选）
评分器可能是：规则检查器、单元测试、验证器模型、过程奖励模型
搜索器可能是：best-of-N、beam search、MCTS、带回溯的自检循环

第19回说“预算要花在刀刃上”，在这里落地成一句话：
把预算集中在‘看起来有希望但又不确定’的分支上。

这正是 MCTS 的长处。

五、极简可跑代码：一个玩具 MCTS（用 UCB 找到更好的计划）

我们做一个最小“计划问题”来摸 MCTS 的手感：

状态是一个整数 x，起点 x=1
目标是到达 target=23
动作只有三个：+1、+2、*2
每走一步算一步，最多走 max_depth 步
终局得分：到达目标得 1，否则按离目标距离给一个较小分（越接近越高）

你可以把它当成“在算式里凑到目标数”。

import math
import random


ACTIONS = ["+1", "+2", "*2"]


def step(x, a):
    if a == "+1":
        return x + 1
    if a == "+2":
        return x + 2
    return x * 2


def terminal_score(x, target):
    if x == target:
        return 1.0
    return 1.0 / (1.0 + abs(target - x))


class Node:
    def __init__(self, x, parent=None, action=None):
        self.x = x
        self.parent = parent
        self.action = action
        self.children = {}
        self.n = 0
        self.w = 0.0

    def q(self):
        return 0.0 if self.n == 0 else self.w / self.n

    def untried_actions(self):
        return [a for a in ACTIONS if a not in self.children]


def ucb(child, parent_visits, c=1.4):
    if child.n == 0:
        return float("inf")
    return child.q() + c * math.sqrt(math.log(parent_visits + 1) / child.n)


def select(node):
    while node.children and not node.untried_actions():
        node = max(node.children.values(), key=lambda ch: ucb(ch, node.n))
    return node


def expand(node):
    ua = node.untried_actions()
    if not ua:
        return node
    a = random.choice(ua)
    nx = step(node.x, a)
    child = Node(nx, parent=node, action=a)
    node.children[a] = child
    return child


def rollout(x, target, depth_left):
    for _ in range(depth_left):
        if x == target:
            break
        x = step(x, random.choice(ACTIONS))
    return terminal_score(x, target)


def backprop(node, value):
    while node is not None:
        node.n += 1
        node.w += value
        node = node.parent


def mcts_plan(start, target, max_depth=8, iters=3000, seed=0):
    random.seed(seed)
    root = Node(start)
    for _ in range(iters):
        node = select(root)
        node = expand(node)
        depth_used = 0
        cur = node
        while cur.parent is not None:
            depth_used += 1
            cur = cur.parent
        value = rollout(node.x, target, max(0, max_depth - depth_used))
        backprop(node, value)

    plan = []
    node = root
    for _ in range(max_depth):
        if not node.children:
            break
        node = max(node.children.values(), key=lambda ch: ch.n)
        plan.append(node.action)
        if node.x == target:
            break
    return plan, node.x, root


if __name__ == "__main__":
    plan, x_end, _ = mcts_plan(start=1, target=23, max_depth=8, iters=5000, seed=0)
    x = 1
    for a in plan:
        x = step(x, a)
    print("plan:", plan)
    print("end:", x, "score:", round(terminal_score(x, 23), 3))

你跑几次会看到：
它会逐渐偏向那些“更接近目标”的分支，而不是乱走。

这段代码虽然玩具，却把 MCTS 的精髓展示出来了：

不靠把所有路走完，而是用“试探+记账”
试出哪条路更有前途，就把预算往那条路倾斜

把它套回 LLM，就是“在推理树里多试几条链，用验证器/奖励给分，再把预算集中到靠谱链上”。

六、过程奖励 + 树搜索：为什么它更像“真的会推理”

只用结果奖励（只看终点），树搜索也能做：
生成很多条完整推理链，最后用终点评分挑最好。

但过程奖励一加入，味道就变了：
你不必等到走到终点才知道对不对，
中途就能发现“第一处错误”，当场剪枝、当场回头。

2024 的自动化过程监督工作提出用 MCTS 风格的方法更高效地定位推理链中的首个错误，并平衡正负过程样本，降低过程监督数据的收集成本。¹
同年也有工作讨论用“过程奖励引导的树搜索”来做 LLM 自训练，体现的正是同一条主线：
用过程信号，把搜索从‘瞎跑’变成‘有剪枝的办案’。²

七、顿悟时刻：搜索与自检，如何催生长思维链

导读里提到“顿悟时刻”：
模型会突然学会回头检查步骤，再继续往下推。
这并不是玄学，更像是两件事叠加后的自然结果：

奖励/验证器让“自检”有了回报：回头查错能提高通过率
搜索给了“回头”的机会：不只走一条路，允许回溯与重选

当你把“回头”写进训练与推理流程里，它就可能从偶然行为变成稳定习惯。
这也是为什么 2024–2026 的推理系统常常长得像一个“小型工作流”：

生成草稿
验证/自检
发现问题就回溯
重新生成或局部修补

第21回开始，我们会把这种“会办事的推理”进一步升级为智能体工作流：
检索、工具调用、验证执行，都会变成搜索空间的一部分。

八、小结：第20回把“慢思考”落地成搜索武功

本回你要带走五句话：

搜索式解码：在推理树里试多条路，再选最靠谱的
MCTS 四步循环：选、扩、跑、回，用 UCB 平衡探索与利用
结果奖励看终点，过程奖励看步骤；后者更能定位第一处错误
生成器+评分器+搜索器是三件套，预算要花在“不确定但有希望”的分支上
搜索与自检叠加，会把“回头检查”从偶然变成习惯，催生长思维链

下一回（第21回）我们将从“会推理”跨到“会办事”：
把搜索、记忆、规划、行动拼成一套智能体架构。

欲知后事如何，且听下回分解。

幻觉核查

自动化过程监督条目核对：arXiv:2406.06592 可核验标题、摘要中对“过程监督”与“MCTS 收集过程信号”的描述。¹
过程奖励引导树搜索自训练条目核对：arXiv:2406.03816 可核验标题与“process reward guided tree search”的定位。²
本回对 MCTS 的四步描述为经典通行表述；本章不展开其理论收敛证明。

逻辑审计

与第19回衔接：第19回讲“预算能换能力”，本回讲“预算要怎么花”才能像推理而非投票。
与第11–16回一致：UCB 的探索-利用精神来自老虎机，本回把它搬到“推理树分支选择”。
为第21回铺路：本回把推理看成“搜索+验证”，下回把外部工具与检索纳入搜索空间，形成智能体工作流。
难度控制：用“迷宫/办案/批改草稿”类比过程奖励与树搜索，不引入复杂证明与符号密度。

引用与溯源

Luo, L., et al. Improve Mathematical Reasoning in Language Models by Automated Process Supervision arXiv:2406.06592 (v2: 2024-12-11) https://arxiv.org/abs/2406.06592 ↩ ↩² ↩³
Zhang, D., et al. Rest-MCTS*: LLM Self-Training via Process Reward Guided Tree Search arXiv:2406.03816 (2024-06) https://arxiv.org/abs/2406.03816 ↩ ↩²

第20回 搜索式解码——MCTS、过程奖励与顿悟时刻