将结构化推理视为搜索

语言模型仍然是一个词元接一个词元地生成。搜索会在模型外加一层控制器，决定下一次调用模型做什么、保留哪个局部结果，以及何时停止。一条链只保留一条后续路径。束会在同一深度保留多条路径。树可以回头尝试其他分支，图还可以复用或合并先前的工作。模型在每一种结构中仍然逐词元生成，搜索过程只是在这些生成操作之间分配模型调用。

本章只讨论推断时控制。一次请求期间，提议模型的权重可以保持不变，但这并不表示整套系统无需训练。局部状态评分器、价值模型或结果模型可能经过单独训练。把这条边界讲清楚，才能避免把提示驱动的树搜索和经过训练的 AlphaZero 式系统视为同一种方法。

搜索问题需要明确接口

把中间文本叫作「思考」，还不足以定义一个搜索问题。控制器需要一套针对任务的接口：

状态是用来预测有效延续和结果的任务信息。搜索节点则是记账结构，还可以保存父节点指针、入边动作、深度、路径成本、分数和访问次数。不同节点可能表示同一个状态。控制器尝试合并重复工作时，这一区别尤其重要。

设 $x$ 为请求，$s_0$ 为初始状态，$a$ 为一个思考单元大小的动作，$T(s,a)$ 为后继状态。提议分布 $\pi_\theta(a\mid s)$ 根据模型参数 $\theta$ 给出状态 $s$ 下可能采取的动作，并不决定扩展哪个搜索节点。这个选择由前沿策略作出。

设 $\mathcal{T}_B(x)$ 为预算 $B$ 耗尽前实际接受评估的终止状态集合。理想目标可以写成

$$s^\star \in \arg\max_{s\in\mathcal{T}_B(x)} q(s),$$

其中 $q(s)$ 是终止状态 $s$ 未知的任务质量，$s^\star$ 是按这种质量衡量时，已评估状态中的最佳者。写出这个目标，并不会让理想目标变得可执行。部署中的控制器只能使用任务实际提供的证据。若存在可观测的终止状态检查器 $G(s)\in\{0,1\}$，并可选地定义效用 $U(s)$，控制器就可以选择

$$\widehat s \in \arg\max_{s\in\mathcal{T}_B(x):G(s)=1} U(s).$$

这里，$G(s)=1$ 表示 $s$ 满足检查器编码的验收条件，$U(s)$ 对通过验收的状态排序，$\widehat s$ 是最终返回的状态。没有精确检查器时，最终选择器可以采用习得估计或提示估计，也可以使用投票或人工审查。这些都只是质量的较弱观测，并不能取代 $q$。答案投票是候选集合的属性，也不是施加于单个终止状态的验证器。

分支会迅速耗尽预算

如果每个非终止状态都产生 $b$ 个子节点，搜索一直到最大深度 $D$，完整树的节点数为

$$N_{\text{full}} = \sum_{d=0}^{D} b^d = \begin{cases} D+1, & b=1,\\ \dfrac{b^{D+1}-1}{b-1}, & b\ne 1. \end{cases}$$

这里，$b$ 是过滤提议后的有效分支因子，$D$ 是最大深度，$d$ 是深度编号，$N_{\text{full}}$ 统计根节点和所有生成节点。当 $b=4$、$D=8$ 时，总数是 87,381 个节点。这里的 $b$ 不是模型词表的大小，而是扩展函数在每个节点实际接纳的思考单元或动作数量。上式统计的是全部生成节点。

束宽限制的是保留状态数，不一定限制提议数，以下记作 $w$。假设每个保留状态恰好产生 $b$ 个互不相同的子节点，而且没有状态提前终止，那么在 $D\ge 1$ 时，生成节点数至多为

$$N_{\text{beam}} \le 1+b+(D-1)wb.$$

第一次扩展产生 $b$ 个节点，之后每一层最多扩展束宽 $w$ 个状态。这个线性上界使束搜索具备实用性，但它并不能保证有效路径仍留在束中。较小的 $w$ 通过不可逆剪枝控制工作量。

只数词元也会漏掉一部分成本。更完整的总工作量可以写成

$$W_B = \sum_{(s,a)\in E_B} c_{\text{gen}}(s,a) + \sum_{s\in Q_B} c_{\text{score}}(s) + \sum_{s\in C_B} c_{\text{check}}(s).$$

其中，$E_B$ 是预算 $B$ 内生成状态与动作扩展的集合，$Q_B$ 是接受评分的状态集合，$C_B$ 是接受检查的终止状态集合，三个 $c$ 项表示各自的实测成本。生成成本取决于前缀长度、输出长度、缓存复用和批处理。用提示实现的评估器可能需要另一次解码；可执行检查器每次调用或许很便宜，开发起来却可能很贵。有空余容量时，并行调用可以缩短墙钟时间，但并不会减少 $W_B$。

不同前沿策略舍弃的东西不同

「树搜索」指的是一种数据结构，不是一种特定算法。前沿规则决定系统会探索什么，又可能失去什么。

广度优先和深度优先搜索不需要习得价值。束搜索和最佳优先搜索需要。蒙特卡洛树搜索（MCTS）会反复执行选择、扩展、叶节点评估或模拟，以及结果回传。UCT 常用的一种选择形式为 (Kocsis and Szepesvári 2006)

$$a_{\text{UCT}} = \arg\max_{a\in\mathcal{A}(s)} \left[ Q(s,a) + c\sqrt{\frac{\log N(s)}{1+N(s,a)}} \right].$$

这里，$\mathcal{A}(s)$ 是状态 $s$ 当前可选的动作集合，$Q(s,a)$ 是动作 $a$ 回传后的平均回报，$N(s)$ 是状态 $s$ 的访问次数，$N(s,a)$ 是该动作的访问次数，$c>0$ 控制探索奖励。实现还必须强制尝试或以其他方式处理尚未访问的动作。AlphaZero 式 PUCT 会加入提议策略的先验，不是换了名字的最佳优先搜索。

经典保证依赖一些语言模型控制器经常违背的假设。广度优先搜索的完备性要求分支有限，而且解位于有限深度。最优图搜索要求转移正确、目标测试正确，并满足相应的成本或启发式条件。动作来自采样、预算有限、分数由模型习得或束会剪枝时，这些保证都会消失。算法名称本身无法恢复这些保证。

被剪掉的分支无法挽回

下面这个可运行示例故意使用具有误导性的局部状态启发式。fast 分支在两个可见状态上的分数都更高，最后却失败。patient 分支起初分数较低，但能到达唯一经过验证的解。

GRAPH = {
    "start": [("fast", 0.90), ("patient", 0.70)],
    "fast": [("dead_end", 0.95)],
    "patient": [("bridge", 0.60)],
    "bridge": [("solution", 1.00)],
}
VERIFIED = {"dead_end": False, "solution": True}

def beam_search(width):
    frontier = [("start", ["start"], 0.0)]
    while frontier:
        candidates = []
        for state, path, _ in frontier:
            if VERIFIED.get(state, False):
                return path
            for child, heuristic in GRAPH.get(state, []):
                candidates.append((child, path + [child], heuristic))
        frontier = sorted(
            candidates,
            key=lambda item: item[2],
            reverse=True,
        )[:width]
    return None

for width in (1, 2):
    path = beam_search(width)
    result = "no verified solution" if path is None else " -> ".join(path)
    print(f"width={width}: {result}")

输出为 width=1: no verified solution 和 width=2: start -> patient -> bridge -> solution。束宽为一时，搜索选择 fast，一旦剪掉，就无法回到那个备选分支。束宽为二时，两条分支会保留到终止状态检查器足以区分它们为止。更宽的束可以提高候选覆盖率，也会增加工作量。只有当扩展函数提出了有用分支，而且局部状态评估器没有过早将其删除时，增加宽度才会有帮助。

这里的「图」有两种含义

状态空间图和思维工作流解决的是不同问题。

在图搜索中，不同路径到达同一个任务状态的情况称为转置。控制器可以用已到达状态表，避免重复扩展这个状态。但前提是存在规范状态键，而且这个键保留了所有会影响后续动作与结果的信息。同一段文本可能对应不同的隐藏状态，因为工具版本、文件、数据库内容、权限或先前的副作用可能不同。反过来，两段措辞不同的轨迹也可能表示同一个符号状态。因此，仅按表面文本合并并不安全。带环的状态空间还需要循环检测、关闭集或明确的重新开放规则。

思维图（Graph of Thoughts, GoT）所说的「图」更接近广义数据流。顶点表示思考单元，边可以表示生成、聚合、精炼或反馈 (Besta et al. 2024)。后续操作可以同时使用两个先前结果，但并不声称它们是等价状态。论文中的系统使用人工设计的操作图，以及针对任务的提示、解析器和评分器。在为这些变换挑选的四项任务上，包括排序基准、集合求交、关键词计数和文档合并，定制的 GoT 调度优于论文所报告的适配基线。这些结果支持在相应任务中以程序化方式组合中间结果，但不能证明它能自动做语义合并，也不能证明它是通用图搜索算法。

价值引导押注于局部证据

对于轨迹展开策略 $\rho$，理想状态价值为

$$v^\rho(s)=\mathbb{E}[R(s_T)\mid s,\rho],$$

其中，$s$ 是当前状态，$s_T$ 是按 $\rho$ 继续执行后到达的终止状态，$R(s_T)$ 是终止回报，期望则对提议或环境结果中的随机性取平均。提示所得的置信分数、局部过程分数和剩余路径成本估计，并不会自动估计同一个量，其尺度也可能随深度漂移。

设控制器观测到

$$\widehat v(s)=v^*(s)+\varepsilon(s),$$

其中，$v^*(s)$ 是按控制器目标衡量的真实延续价值，$\widehat v(s)$ 是观测分数，$\varepsilon(s)$ 是评估器误差。搜索会选择最高的观测分数，因此也会选中异常偏大的正误差。控制器比较的状态越多，或越激进地优化同一个评分器，这种选择偏差就越重要 (Gao et al. 2023)。在普通轨迹上校准的评分器，面对更深搜索产生的前缀时也可能落入分布外。错误剪枝则是相反的问题：某个状态的价值被低估，在延迟收益显现之前就遭到删除。

提示驱动的自我评估可以说明这种依赖关系。自我评估引导的随机束搜索使用同一个语言模型，但分别采用生成提示和评估提示，再把步骤置信度与模型似然结合起来 (Xie et al. 2023)。它改善了论文报告的算术任务结果，但在常识任务上，预算匹配后的结果并非始终更好。这项研究表明局部评分可以引导束搜索，不是模型能准确核查自身工作的证据。

已发表的系统不能混为一谈

一些有影响力的系统都采用生成器与评估器循环，但控制器和训练假设并不相同。

Tree of Thoughts 不能证明树搜索在任意任务上都优于重复采样。它在 24 点上的结果很突出，但这项任务会给出紧凑的中间等式，可以在完成前判断。GoT 同样选择了适合聚合与精炼的任务。TS-LLM 展示了经过训练的评论器能提供什么，但这些评论器越过了本章开头划定的训练边界。

AlphaEvolve 提供了一个相关但范围更广的例子。它对程序作评估器引导的演化搜索，并不是在自然语言思考上运行束搜索或 MCTS。其白皮书报告了一个对 $4\times4$ 复矩阵做乘法的秩 48 程序，以及一项 Borg 调度启发式。Google 报告后者平均释放了相当于全机群 0.7% 的算力 (Novikov et al. 2025)。自动化评估使这些搜索可以真正执行，但这些结果不能证明语言树搜索普遍更优。

如何运行搜索控制器

生产实现不能只有一个算法名称，还需要以下约束：

1. 定义状态结构、合法动作结构、规范化规则、终止测试和最终输出约定。拒绝让无法解析的状态进入前沿。
2. 在将要使用评估器的控制器所生成的状态上校准。只用直接回答组成的留出集，无法衡量评估器面对深层、经过选择的前缀时会如何表现。
3. 在预算匹配的评估中比较直接生成、重复采样、Best-of-$n$ 和结构化搜索。对齐生成词元总量、评分器调用、检查器调用、模型版本和可用并发容量，并单独报告延迟。
4. 为节点数、深度、生成词元、工具调用、费用、内存和墙钟截止时间设置硬上限。只有任务约定允许时，才在验证成功后提前停止。
5. 明确定义空前沿、解析失败、评估器超时、没有终止状态通过验收，以及检查器相互冲突时的回退策略。服务可以返回直接回答、弃答或升级处理，但不能让选择隐含在实现里。

使用工具的搜索还需要一条边界：推测性分支不应提交不可逆的外部副作用。检查应在沙箱或事务中运行；只读探索要与经过批准的写入分开；幂等调用则要去重。

每次请求的遥测应记录提示与模型版本、控制器与评估器版本、扩展次数、生成词元数、各深度的前沿大小、去重率、评估器分数、检查器结果、所选路径、停止原因、回退路径、总工作量和延迟。离线分析应分别衡量候选覆盖率、所选答案准确率、错误剪枝、选择遗憾、每个通过验收答案的成本，以及尾部延迟。

搜索是一层算力分配机制。提议模型给出可能的动作，控制器决定工作投向哪里，评估器改变哪些分支能够存活，检查器则决定什么证据足以停止搜索。下一章会改变状态表示本身，把一部分工作从自然语言轨迹移到程序、求解器和证明检查器中。

延伸阅读