7 规划：ReAct、Plan-Execute、树搜索、反思

第 6 章把「证据从哪里来」讲完了：检索、引用、遗忘。现在 agent 手里有一堆证据，下一步要决定先做什么、后做什么、哪些可以并行、哪些做了就回不去。这就是规划。它不是在提示词里加一句「请先制定计划」，而是在状态空间里用有限预算选择动作序列，并对选择的结果负责。

本章的论点只有一句：规划策略的差别不在「想得久不久」，而在搜索结构与验证器。ReAct 用环境反馈替代全局搜索，Plan-Execute 用一次规划成本换全局一致性，树搜索用展开预算换候选质量，反思用上一轮的证据换下一轮的策略。四者都受同一个预算约束；脱离预算谈「哪种策略更强」没有意义。

先把边界划清。本章不重写强化学习或搜索教科书：MDP、Bellman 方程、A* 的最优性证明都属于《深度学习导论》与算法课的领土，这里只引用它们作为背景。本章关心的是 agent 系统里多出来的那一层：计划如何表示、执行如何偏离、偏离后如何重规划、验证器如何决定搜索是否值得。实验在 experiments/ch07/，纯标准库、确定性、无网络；它不模拟 LLM，而是把三种策略的搜索结构钉死，让预算与失败模式可复现。

读图：三块横向并排的不是「难度阶梯」，而是三种预算分配方式。左侧 ReAct 的箭头回到 Thought，表示每一步都重新决策；中间 Plan-Execute 在 Planner 之后有扇出与 Replan 回路，表示计划成本与重规划成本是两项独立开销；右侧树搜索的节点分叉最多，但只有带 ✓ 的叶子被验证器确认——没有 ✓ 的分支再多也只是候选。把这张图和 7.8 的表对照：ReAct 在 key-door 缺的是跨步的全局边，Plan-Execute 在 one-way-return 输在 Planner 的模型与执行器不一致，ToT 在 long-corridor 输在分叉太多、预算不够。

7.1 规划问题：状态、动作、目标与代价

先看一个足够小的事故。任务是把一个只读副本切成主库，agent 生成的计划是：

1. pg.check_replication(primary)
2. pg.promote(replica-2)
3. pg.update_dsn(app-config, replica-2)
4. app.restart(api)
5. smoke.test(/healthz)

第 1 步成功，第 2 步返回 ENOTOOL：工具注册表里只有 pg.failover，没有 pg.promote。agent 把错误当成瞬时失败，重试两次；随后「重规划」出 pg.promote_primary，仍然不存在。第 4 步的 app.restart 有权限，于是 API 被重启，指向一个从未提升的副本。最终状态比开始更糟：主库没切，服务先抖了一次。

这个事故里没有一步是「模型算错了」。计划在纸上完全合理，问题在于计划引用的动作在当前系统里不存在，而执行器没有在动手前校验整条计划。要讲清这类失败，先要把规划问题写成可检查的对象。

这个定义里最容易被省略的是 $A$ 的「接地」。模型说「提升副本」不是动作；pg.failover(replica-2, force=false) 才是动作。接地之后，参数、前置条件、权限、幂等键才有地方挂。很多计划幻觉的根因不是模型不知道「提升副本」这件事，而是规划器把自然语言动词当成了可执行动作，没有把它映射到注册表里的具体条目。

第二个容易被省略的是 $G$。目标必须可判定：replication_lag < 1s 可判定，系统稳定 不可判定。目标不可判定时，执行器无法知道何时停，规划器也无法验证计划是否覆盖目标；最后只能由模型说「完成了」，这等于把终止条件交给了被验证的对象。

这两个对象经常被混为一谈，后果很具体：用计划当轨迹，会把「打算执行」当成「已经执行」，于是模型说「已重启服务」而日志里没有这次调用；用轨迹当计划，会在下一次运行时重放上一次的具体动作，忽略世界已经变化。表 7.1 把差别压成五行。

这张表说明什么：计划和轨迹不是同一份数据的不同格式，而是两种不同的证据。排障时先看轨迹，判断「实际发生了什么」；再对照计划，判断「原本打算做什么」。只看其中一份，都会把「计划错了」和「执行错了」混为一类。

7.1.1 首次偏离之后，计划不再有保证

计划执行最危险的不是第一步就失败，而是前几步成功、第 $j$ 步悄悄偏离，后面的动作仍然「看起来在执行」。例如计划认为门已经打开，实际门还锁着；move 返回失败，但策略把失败当成「已经通过」，继续执行后续的 inspect。这时轨迹已经与计划分叉，后续动作的前提全部失效。

这个定理的工程含义不是「计划没用」，而是计划必须带检查点。每执行一步，至少比较三样东西：动作是否成功、真实状态是否等于预期状态、关键前置条件是否仍成立。三者任一不成立，就把计划标记为「已偏离」，而不是继续往下走。

7.1.2 代价：规划、执行、重规划、验证

规划不是免费的。它消耗模型 token、搜索节点、工具 dry-run 的时间和人的审批。一个完整的代价模型至少有四项：

$$\mathbb{E}[C] = C_{\text{plan}} + \mathbb{E}[C_{\text{exec}}] + p_{\text{dev}} , C_{\text{replan}} + C_{\text{verify}},$$

其中 $p_{\text{dev}}$ 是执行偏离计划的概率。这个式子解释了一个常见困惑：为什么「计划更优」不等于「总成本更低」。规划器找到一条短 2 步的路径，但为此扩展了 50 个节点、多做了一次 dry-run，总成本可能反而更高。第 7.8 节的 detour 任务就是这种情形：Plan-Execute 的动作数比 ReAct 少 2，但规划扩展把总成本拉回同一条线。

四项成本里，验证最容易被漏算。验证包括：执行前的计划校验（工具是否存在、参数是否合法、前置条件是否成立）、执行中的断言、执行后的测试与人工复核。验证越强，$p_{\text{dev}}$ 越低，但 $C_{\text{verify}}$ 越高；这是一条需要显式选择的曲线，不是「越严格越好」。

这张表说明什么：四项成本必须一起进预算。只压 $C_{\text{plan}}$ 会让计划质量下降、$p_{\text{dev}}$ 上升；只压 $C_{\text{exec}}$ 会让 agent 少做事、把未完成包装成完成；只压 $C_{\text{verify}}$ 会把风险推到生产。预算不是四个独立的数字，而是一组需要联合调整的杠杆。

7.1.3 可行性、可逆性与「能不能试」

规划器面对的另一个现实是：有些动作可以随便试，有些试一次就回不去。可逆性可以写成一个存在性条件：

$$\mathrm{rev}(s,a)=1 \iff \exists \sigma \in A^{*}:\ \mathrm{eff}^{*}(\mathrm{eff}(s,a),\sigma)=s \ \land\ C(\sigma) \le R,$$

其中 $R$ 是可接受的恢复成本上界。这个定义故意把「能恢复」和「恢复得起」分开：发一封邮件在技术上可以再发一封「请忽略上一封」，但恢复成本、信誉损失和时间窗口可能都不可接受，工程上应当按不可逆处理。

可逆性直接决定搜索策略。可逆动作可以用试错换信息：先做，失败再退回来。不可逆动作必须先把验证做在前面：dry-run、权限检查、人工审批、灰度。树搜索在不可逆动作上尤其危险，因为它会展开多条分支，而每条分支都可能产生真实副作用；如果搜索用的是真实执行而不是模拟，展开就是在拿生产环境做实验。

这张表说明什么：搜索的「宽度」不只是算力问题，也是副作用问题。一个宽度为 8 的树搜索，在只读任务上是 8 次探索；在不可逆任务上可能是 8 次事故。规划器必须知道每个动作的可逆性，才能决定哪些分支可以真实展开、哪些只能模拟。

关于规划的五个常见误解，可以压成一张表。

这张表说明什么：五个误解里多数来自同一个混淆——把「计划文本」当成了「执行保证」。计划只是意图，保证来自检查点、验证器与权限边界。

7.1.4 四个建模选择

同一个任务可以建成不同粒度的规划问题。建模选择错了，后面换什么搜索算法都救不回来。四个选择最关键：

这张表说明什么：规划问题的质量在建模阶段就决定了大半。状态太粗，计划会在错误的前提上「可行」；动作太细，搜索会被无关分支淹没；目标不可判定，终止条件就回到模型嘴里；模型与执行器不同源，计划幻觉就是结构性的，不是偶发的。

把 7.1.2 的代价公式代入一个具体算例，可以看出规划什么时候划算。设一次扩展折合 0.2 个动作，规划扩展 120 个节点，计划执行 10 步，验证 6 个动作当量，偏离概率 0.2，一次重规划 30 个动作当量：

$$C_{\text{PE}} = 0.2 \times 120 + 10 + 6 + 0.2 \times 30 = 46.$$

同样任务用 ReAct，执行 15 步，重试概率 0.3，期望成本约 $15 + 0.3 \times 15 = 19.5$。在这个规模上，Plan-Execute 的规划开销收不回来。把任务放大到 50 步：Plan-Execute 约 $24 + 50 + 6 + 6 = 86$，ReAct 约 $50 + 0.3 \times 50 = 65$；如果 ReAct 的重试概率随步数上升到 0.6，期望成本变成 80，两者才接近。规划的价值随任务长度与偏离代价增长，不是天然存在的。

7.2 ReAct：交错推理与行动

ReAct 的结构可以用一句话概括：让模型在每一步先写一句「我准备做什么、为什么」，再调用一个工具，把工具结果放回上下文，然后进入下一步。Thought 是自然语言，Action 是工具调用，Observation 是工具结果；三者交错，形成一条既包含推理又包含证据的轨迹。

Thought: 门在右边，钥匙可能在左边；先看看当前位置有什么。
Action:  look()
Observation: room=hall, exits=[north, east], items=[]
Thought: 东边是锁着的门，先去北边找钥匙。
Action:  move(north)
Observation: room=storage, items=[key]
Thought: 拿到钥匙，回大厅开门。
Action:  take(key)
Observation: inventory=[key]

这段轨迹里，Thought 不是装饰。它把「为什么选这个动作」写进了上下文，让下一步的模型能看到自己的意图，也让人类排障时能区分「动作错了」与「意图错了」。ReAct 的原始论文（Yao et al., 2022）在 HotpotQA、FEVER、ALFWorld、WebShop 上报告了推理与行动交错的收益；核心机制不是「思考」本身，而是观察会改变下一步的推理。

context ← task + tool_schemas
while not done and budget_left:
    thought ← model(context)            # 自然语言，可能错
    action  ← parse(thought)            # 工具名 + 参数
    if action == finish: break
    obs     ← execute(action)           # 真实执行，返回结构化结果
    context ← context + (thought, action, obs)

这段伪代码有三个关键点。第一，model(context) 的输入包含全部历史观察，所以上下文会随步数增长；第 5 章讲的压缩与裁剪在这里必须介入。第二，parse(thought) 可能失败：模型可能写出不存在的工具、参数不是合法 JSON、或者同时给出多个动作；解析失败必须变成一条观察，而不是抛穿循环。第三，execute(action) 是唯一产生副作用的地方；Thought 再长也不改变世界。

ReAct 的优点很直接：

• 反馈快。 不需要先建完整模型，执行一步就能拿到真实观察；环境是唯一的事实来源。
• 实现简单。 一个循环、一个工具注册表、一个解析器，就能跑起来；没有单独的规划器与计划表示。
• 适合部分可观测。 计划器不知道的信息，ReAct 可以通过下一步观察获得；它不需要事先枚举所有分支。
• 轨迹可读。 Thought/Action/Observation 三段式让排障者能沿着因果链读下去。

但它的失效条件同样明确。表 7.2 把最常见的五类列出来，每一类都能在 trace 里找到对应信号。

这张表说明什么：ReAct 的失败很少是「模型不会推理」，多数是「策略没有被赋予全局结构」。换一个更强的模型，能让局部贪心更聪明，但不能凭空产生「先拿钥匙」这个子目标；子目标要么来自计划，要么来自被显式写进策略的规则。

第 7.8 节的 key-door 任务把第一、二类失效钉死了。钥匙在起点反方向，门在目标方向；按到目标的曼哈顿距离贪心，在到达钥匙之前，每一步都倾向于靠近门，不会主动退回去拿钥匙。实际 trace 的前八步是：

python3 experiments/ch07/planners.py --task key-door --strategy react --trace /tmp/ch07-react.jsonl
jq -r '[.step, .action, .observation, .value] | @tsv' /tmp/ch07-react.jsonl | head -n 8

1	E	moved	-6
2	E	moved	-5
3	S	moved	-4
4	S	moved	-3
5	W	moved	-4
6	N	moved	-5
7	W	moved	-6
8	S	moved	-5

价值从 $-6$ 走到 $-3$，看起来在接近目标；然后又开始在 $[-4,-6]$ 之间摆动。直到第 22 步，它才偶然经过钥匙（take），第 36 步才打开门（open），第 40 步停在 (4,5)——离目标 (5,5) 只差一步，预算耗尽。take 与 open 各只发生一次，都不是计划出来的，是逛到的。这不是「模型不够聪明」，而是在它到达钥匙之前，策略的目标函数里根本没有「钥匙」这一项。给它加一条「门锁着且没有钥匙时，先去找钥匙」的规则，它通常就能成功；但这条规则本质上是一个两级计划，ReAct 已经不再是纯反应式策略。

ReAct 适合的任务可以压成三个条件：单步反馈能改变下一步决策、动作可逆或代价低、任务不需要长距离的顺序约束。三个条件有一个不成立，就应该考虑 Plan-Execute 或树搜索。反过来，如果任务的环境模型根本不可信（新 API、动态网页、开放世界），Plan-Execute 的计划很容易幻觉，ReAct 的逐步试探反而更稳。

7.2.1 ReAct、思维链与 Plan-Execute 的边界

三者经常被混为一谈，因为它们的输出都是文本。差别在文本是否被外部观察约束、是否有显式计划、反馈以什么粒度进入下一步。

这张表说明什么：CoT 不是 agent，因为它没有外部观察与动作闭环（第 1 章的三个判据）；ReAct 是 agent，但它的「计划」只存在于策略的隐式偏好里；Plan-Execute 把计划显式化，代价是要维护计划模型；树搜索把「多个计划」显式化，代价是要有能区分候选的验证器。四者不是替代关系，而是同一控制回路里「计划显式程度」与「验证器强度」的不同组合。

7.3 Plan-Execute：计划表示、依赖与重规划

Plan-Execute 把决策分成两段：先由规划器生成一个计划，再由执行器按计划执行；执行偏离时触发重规划。它用一次规划成本换全局一致性，适合步骤可预判、依赖可表达、动作代价高的任务。关键不在「先计划」这个动作，而在计划用什么结构表示。

最弱的结构是列表：[a1, a2, a3, ...]。列表只能表达全序，不能表达并行，也不能表达「a2 和 a3 都依赖 a1，但彼此独立」。执行时任何一步失败，通常只能整条重来。它实现简单，适合线性流程，但在有扇出/扇入的任务上会把可并行的步骤串行化，也会让重规划范围过大。

更强的结构是 DAG：节点是接地动作，边是依赖。一个「修复回归」的计划可以画成下面这样。

                    ┌──────────────┐
                    │  reproduce   │  复现失败
                    └──────┬───────┘
                           ▼
                    ┌──────────────┐
                    │   locate     │  定位根因
                    └───┬──────┬───┘
                        ▼      ▼
                 ┌──────────┐ ┌────────────┐
                 │  patch   │ │  add_test  │  两条支路可并行
                 └────┬─────┘ └─────┬──────┘
                      ▼             ▼
                 ┌───────────────────────┐
                 │      unit_suite       │  扇入：两支都完成才跑
                 └──────────┬────────────┘
                            ▼
                 ┌───────────────────────┐
                 │      full_suite       │  全量回归
                 └──────────┬────────────┘
                            ▼
                 ┌───────────────────────┐
                 │        review         │  人工/独立 critic
                 └───────────────────────┘

读图：从 reproduce 到 review 的最长路径是 reproduce → locate → patch → unit_suite → full_suite → review，它决定最短完成时间；patch 与 add_test 之间没有边，可以并行。重规划时，只有失败节点的后代需要失效：如果 patch 失败，add_test、reproduce、locate 都不必重做；如果 locate 的结论被推翻，整棵下游树都要重来。这张图还标出了一个验证边界：review 之前的所有节点都可以自动执行，review 是一个人工/独立 critic 的汇合点，不能由生成计划的同一个模型自己批准。

DAG 的代价不只是节点代价之和。并行会带来协调成本：两个分支同时写同一个文件会冲突；同时调用同一个限流 API 会互相挤占配额；一个分支失败时，另一个分支可能已经产生了需要回滚的副作用。工程上要给每个节点标「资源域」（文件、数据库、外部 API、预算桶），同一资源域内的写操作默认串行；只有读操作或明确声明无冲突的写操作才允许并行。

计划的结构定了，接下来要定什么时候重规划。重规划太晚，会沿着错误计划产生更多副作用；太早，会把本可局部修复的问题升级为全局重来。表 7.3 给出六类触发条件与对应的处理范围。

这张表说明什么：重规划不是「重新生成整条计划」的同义词。大多数偏离只需要替换一个节点或一段子图；全量重规划的成本高，而且会把已经验证过的前缀丢掉。重规划的范围应该由依赖边决定，而不是由模型的方便程度决定。

重规划的成本可以写成

$$C_{\text{PE}} = C_{\text{plan}} + \sum_{v \in V} c_v + \sum_{r \in R} C_{\text{replan}}(r) + C_{\text{verify}},$$

其中 $R$ 是实际发生的重规划集合。若执行环境稳定、计划准确，$|R|$ 很小，Plan-Execute 的总成本接近「一次规划 + 一次执行」；若环境频繁变化，$|R|$ 增大，规划成本会被重复支付，这时 ReAct 的逐步适应反而更便宜。这个成本式没有统一的阈值，它取决于任务的偏离率、单次规划成本与单次执行成本。

7.3.1 一个计划节点应该带什么

计划节点不是「工具名 + 参数」这么简单。一个能被执行器校验的节点至少带八个字段：

{
  "id": "s3",
  "action": "tests.run",
  "args": {"suite": "unit", "timeout_s": 120},
  "deps": ["s1", "s2"],
  "pre": ["worktree_clean == false", "s1.status == 'ok'", "s2.status == 'ok'"],
  "post": ["junit.xml exists", "exit_code == 0"],
  "cost": {"wall_s": 120, "quota": "ci:1"},
  "reversible": true
}

这八个字段里，pre 与 post 是执行器真正用来判断「能不能开始」「有没有成功」的；deps 决定重规划范围；reversible 决定能不能在失败时自动重试；cost 决定预算扣减。只给 action 与 args 的计划，执行器只能「照着调用」，无法在调用前发现计划已经失效。

计划生成后、执行前，至少要过五道校验：

1. 能力校验。 每个 action 都存在于当前工具注册表；参数符合 schema；没有引用不存在的工具或版本。
2. 前置条件校验。 每个节点的 pre 能在当前状态上求值；不能求值的条件视为不成立。
3. 资源校验。 并行分支不争抢同一资源域；总配额不超过预算。
4. 可逆性校验。 不可逆节点必须有审批或 dry-run；不能与自动重试共存。
5. 目标覆盖校验。 计划的后置条件能推出目标 $G$；不能推出时，计划再漂亮也不完整。

五道校验里，第 1 道最便宜，也最能挡住计划幻觉；第 5 道最难，需要把目标写成可判定的断言。工程上常见的偷懒是只做第 1 道，然后在第 3、4 道翻车：工具都存在，参数都合法，但两个分支同时写同一个文件，或者一个不可逆动作被自动重试了三次。

7.3.2 什么时候 Plan-Execute 优于 ReAct

把两节的失效条件放在一起，可以得到一张选择表。

这张表说明什么：Plan-Execute 的优势来自全局约束与不可逆动作，不是来自「计划」这个词。如果任务没有全局约束、动作都可逆、反馈又很快，先规划一遍只是多花一笔钱；反过来，如果任务有「先备份再迁移」「先拿钥匙再开门」这类硬顺序，ReAct 的局部贪心很容易在门前打转。

一个实用的折中是分层计划：高层用 DAG 表达子目标与依赖，低层每个子目标交给 ReAct 执行。高层保证「先备份后迁移」的顺序，低层保留逐步试探的灵活性。代价是要维护两层之间的契约：低层完成时，必须把「哪些后置条件已经成立」写回高层；低层失败时，高层要决定是重试这个子目标，还是让整个计划失效。第 8 章讲多智能体时，这种分层会变成 supervisor 与 worker 的拓扑。

7.4 树搜索：ToT、MCTS 与价值函数

ReAct 只走一条路，Plan-Execute 只信一份计划。树搜索把「一条路」变成「多棵候选」，把预算花在展开与比较上。它的承诺不是「想得更久就一定更好」，而是如果有办法区分候选的好坏，就可以用更多候选换更高的成功率。这句话有两个前提：价值函数能区分好坏，预算足够覆盖展开。缺一个，树搜索就退化成昂贵的随机采样。

三种常见结构：

• ToT（Tree of Thoughts）。 把部分解当成树节点，每一步生成若干个「想法」，对每个想法打分，保留高分分支继续展开；可以用 BFS（保留一层的前沿）或 DFS（深入一条分支再回溯）。Yao et al. (2023) 把它用于 24 点游戏、创意写作与迷你填字，核心是「生成—评估—搜索」三件事，而不是某一种固定树算法。
• MCTS（蒙特卡洛树搜索）。 在选择、扩展、模拟、回传四步之间循环，用访问次数与平均价值决定下一步展开哪条分支；适合分支多、单次模拟便宜、价值可以逐步估计的场景。
• Beam search。 每一层只保留价值最高的 $k$ 个节点，简单、可预测、易并行；没有回溯，也没有最优性保证。

7.4.1 ToT：展开、评估、回传

ToT 的一次循环可以写成：

frontier ← {initial_state}
for depth in 1..D:
    candidates ← []
    for s in frontier:
        for thought in generate(s, k):        # 展开：生成 k 个候选
            candidates.append(apply(s, thought))
    scored ← [(value(c), c) for c in candidates]  # 评估
    frontier ← select_top(scored, width)          # 选择
    if any is_goal(c): return best_path()

三个函数决定了 ToT 的质量：

1. generate(s,k) 决定候选多样性。温度太低，$k$ 个候选几乎一样，展开是浪费；温度太高，候选大多不可行，评估器被噪声淹没。工程上常用的做法是「先广后深」：前几层多生成，接近叶子时少生成。
2. value(c) 决定搜索方向。它可以是 LLM 打分、程序化启发式、测试通过率、独立 critic 的投票；来源不同，偏差不同（见 7.4.4）。
3. select_top 决定预算分配。BFS 保留每层最好的 $k$ 个，适合深度不大、需要比较多个中间状态的任务；DFS 深入一条分支，适合有明确回溯点、单条路径很长的任务。

「回传」在 ToT 的 BFS 版本里通常表现为「把子节点的最好价值汇总到父节点」，用于决定父节点是否还值得继续展开；在 MCTS 里则是显式的反向传播。两者的区别很重要：ToT 的回传是启发式的，没有访问次数的严格统计；MCTS 的回传会更新每个节点的 $N$ 与 $Q$，让下一次选择有据可依。

一个具体的例子是修一个失败的测试。根节点是「当前工作区」，展开出三个候选：改实现、改测试、加兼容层。每个候选再展开出两个具体补丁。评估器跑单元测试，得到通过/失败与覆盖率。BFS 保留通过率最高的两个补丁继续展开；DFS 则先深入「改实现」这一支，如果测试全绿就返回，不再看另外两支。这里的关键不是树，而是评估器能在中间状态给出信号：如果只有最终测试能打分，中间节点全是 0，树搜索就退化成枚举。

7.4.2 MCTS 与 UCB

MCTS 把「探索哪条分支」变成一个多臂老虎机问题。每个节点 $s$ 的每个动作 $a$ 都维护两个统计量：$N(s,a)$ 是被选中的次数，$Q(s,a)$ 是这些次选择得到的平均价值。选择阶段用 UCB 决定下一步（UCB1 见 Auer et al., 2002；UCT 见 Kocsis & Szepesvári, 2006）：

$$\mathrm{UCB}(s,a) = Q(s,a) + c\sqrt{\frac{\ln N(s)}{N(s,a)}}, \qquad N(s)=\sum_{a'} N(s,a').$$

三项的含义：

• $Q(s,a)$ 是利用项：过去这个动作的平均回报越高，越容易被再次选中。
• $\sqrt{\ln N(s)/N(s,a)}$ 是探索项：$N(s,a)$ 越小，这一项越大；父节点被访问得越多，$\ln N(s)$ 越大，未试过的动作越有吸引力。
• $c$ 是探索系数：$c$ 大，搜索更愿意尝试访问少的分支；$c$ 小，搜索更快收敛到当前看起来最好的分支。

$c$ 不是「越大越好」的魔法常数。它和价值的尺度绑定：如果 $Q \in [0,1]$，经典 bandit 设置常用 $c=\sqrt{2}\approx 1.41$；如果 $Q$ 是 $[-100,100]$ 的分数，同一个 $c$ 几乎不起作用，探索项被价值差淹没。换价值函数时，必须重新标定 $c$，否则搜索要么完全不探索，要么把预算浪费在明显差的分支上。

MCTS 的四步是：

1. 选择（selection）。 从根开始，按 UCB 一路选到叶子；遇到未展开的动作就停下。
2. 扩展（expansion）。 为选中的节点增加一个或多个子节点。
3. 模拟（simulation / rollout）。 从新节点出发，用一个便宜的策略走到终点或深度上限，得到一个价值估计。
4. 回传（backpropagation）。 把这次价值沿路径累加，更新每个节点的 $N$ 与 $Q$。

在 LLM agent 里，第 3 步通常不是随机模拟，而是「让模型快速给一个估计」或「跑一个便宜的启发式」；这省掉了昂贵的真实 rollout，但也把价值函数的偏差带进了搜索。MCTS 的统计保证建立在模拟的无偏性上；如果模拟本身有系统性偏差，访问次数再多也只会更自信地收敛到错误答案。

7.4.3 一次 UCB 计算

公式只有三项，但 $c$ 的作用要算一遍才直观。设节点 $s$ 被访问 $N(s)=10$ 次，三个动作的统计如下；取 $c=1.4$ 与 $c=0.2$ 各算一次。

$c=1.4$ 时选 C：它的 $Q$ 最低，但只被访问过一次，探索项把它推到第一。$c=0.2$ 时选 B：探索的权重不足以抵消 C 的价值差距，搜索转向当前平均回报最高的动作。$c=0$ 时也选 B，搜索完全利用。三个结果没有对错，取决于你更怕「错过一个没试过的好分支」还是「把预算浪费在差分支上」。

这张表还说明 $c$ 与价值尺度必须绑定。若 $Q$ 被归一化到 $[0,1]$，$c=1.4$ 的探索项与价值同量级；若 $Q$ 是 $[0,100]$ 的评分，同一个 $c$ 的探索项几乎可以忽略，搜索会立刻退化成贪心。换价值函数时，先看 $Q$ 的取值范围，再定 $c$；不要把一个任务的 $c$ 直接搬到另一个任务。

7.4.4 价值函数从哪里来

树搜索的质量上限由价值函数决定。表 7.4 比较五种常见来源。

这张表说明什么：没有一种价值函数同时便宜、准确、覆盖广。树搜索的工程问题不是「选最好的价值函数」，而是「按阶段组合」：前几层用便宜启发式剪枝，中间用 LLM/critic 排序，叶子用测试或人工验证。组合的代价要计入预算，不能默认验证免费。

价值函数还有三个容易被忽略的偏差：

• 位置偏差。 LLM 打分对候选在提示中的顺序敏感；同一组候选换一个顺序，排名可能变化。评估时要随机化顺序或做配对比较。
• 长度偏差。 更长的候选看起来更「完整」，却可能包含更多未经证实的断言。用测试或引用核验对冲。
• 同源偏差。 生成候选的模型与打分的模型是同一个，盲点高度相关；它会给自己的错误打高分。至少换一个提示、换一个模型，或引入执行器信号。

7.4.5 Beam search 与一个不可能定理

Beam search 是最简单的树搜索：每一层展开所有候选，按价值排序，只保留前 $k$ 个，继续下一层。它的成本近似为

$$N_{\text{expand}} \approx k \cdot b \cdot d,$$

其中 $b$ 是平均分支因子，$d$ 是深度。$k$ 越大，保留的候选越多，成本线性上升；但 $k$ 大不等于质量高，因为被保留的候选可能高度相关，也可能在早期就被错误的价值函数带偏。

深度也是预算变量。MCTS 的成本近似为「模拟次数 × 深度」，ToT 的成本近似为「每层候选数 × 深度」；每多一层，成本线性累加，而收益通常递减。工程上要给深度设上限，并用「连续几层最好价值不再提升」作为早停条件，而不是让搜索一直展开到预算耗尽。

这个定理不是说 beam 没用，而是说它的保证是经验性的：在特定任务分布上，价值函数的前 $k$ 名恰好包含正确分支，beam 就有效；换一个分布，同样的宽度可能刚好剪掉唯一正确的分支。工程上要用「留一候选」「随机重启」「多宽度并行」来对冲，代价是更多扩展。

7.5 反思：Reflexion、自我批评与经验回写

反思（reflection）是 agent 在失败后把轨迹变成「下次怎么做」的过程。它看起来像让模型「再想一遍」，但真正有用的反思不是重读一遍失败，而是从外部证据中提取一条可检验的修正，并把它写回下一次尝试的条件里。

Reflexion（Shinn et al., 2023）给出四个部件：Actor 执行任务，Evaluator 给出成功/失败信号，Self-Reflection 把失败轨迹转成一段自然语言教训，episodic memory 保存教训；下一次尝试把这段教训放进上下文。它的关键不是「反思」这个词，而是 Evaluator：在 HumanEval 里是单元测试，在 ALFWorld 里是环境成功信号，在 HotpotQA 里是答案匹配或外部评估。没有评估信号，反思就失去了锚点。

Self-Refine（Madaan et al., 2023）是同一轮内的迭代：模型生成初稿，模型自己给反馈，模型根据反馈修改，重复若干轮。它不需要跨回合记忆，也不需要外部环境；优点是便宜、通用，缺点是反馈与生成同源，遇到模型自己看不见的错误时，迭代会把错误改得更精致，而不是改对。

这张表说明什么：两者都叫「反思」，但证据结构完全不同。Reflexion 的收益来自「外部信号 + 跨尝试记忆」；Self-Refine 的收益来自「低成本迭代 + 软约束」。把 Self-Refine 用在需要事实正确性的任务上，等于让同一个模型给自己判卷。

7.5.1 一条反思应该带什么

一条能安全回写的反思，至少包含六个字段：

这个定义把「反思」与「复盘」区分开。复盘可以没有结论，反思必须产出一个可执行的修正；但这个修正仍然只是假设，必须经过下一次尝试或独立验证才能升级为规则。把假设直接写成全局规则，是反思退化最常见的起点。

7.5.2 反思退化的三个条件

反思不是单调改进的。下面三个条件同时出现时，反思很可能让下一次更差：

1. 同一模型、没有新证据。 生成者与批评者共享同一套盲点；模型会把自己的错误解释成「环境问题」或「测试问题」。它写得越具体，越有说服力，也越容易把错误固化成规则。
2. 批评与生成同源。 同一个上下文、同一个提示模板、同一个模型，批评只是生成的镜像。要打破同源，至少换一个提示、换一个模型、或者引入执行器信号（测试、类型检查、外部检索）。
3. 把一次噪声写成全局规则。 一次超时被写成「这个 API 总是超时，应该跳过」；一次权限失败被写成「遇到 EPERM 就重试」。规则的范围远大于证据的范围，下一次在不相关的任务上触发。

还有一个不那么明显但很常见的退化：反思文本挤掉了任务约束。反思通常写在上下文的前部或尾部，模型为了让反思「被看见」，会把任务约束挤到中间；第 5 章讲过中间位置的可利用性最差。结果是反思被记住了，原始目标被忘了。

判断一条反思是否值得写回，可以用一句工程规则：没有外部证据的反思，不进入长期记忆；有外部证据但范围过宽的反思，只进入当前任务的临时上下文。这条规则牺牲了一部分「举一反三」的能力，换来的是记忆不被噪声污染。等同一类证据出现多次，再由人或独立评估器把它升级为规则，而不是让模型在一次失败后自己宣布「我学会了」。

7.6 验证器：测试、形式检查、critic 与投票

7.4 节说「价值函数能区分好坏，树搜索才划算」。这句话里的「区分」不是免费的：它需要一个验证器。验证器可以是单元测试、类型检查、形式化不变量、独立的 critic、多个样本的投票，也可以是真实环境的执行结果。它们的强度、成本与偏差完全不同，混用会让搜索的收益被假阳性吃掉。

先看一个反例。某代码 agent 为同一个 bug 生成了 20 个候选补丁，用一个 LLM critic 打分，取最高分的补丁提交。critic 给每个补丁都写了「看起来合理」的评语，最高分补丁把一个边界条件从 x < 0 改成了 x <= 0，测试没覆盖这个边界，CI 全绿。三天后，负数输入触发了一次线上事故。这里的问题不是搜索不够，而是验证器把「看起来合理」当成了「正确」；候选越多，找到「看起来最合理但实际错误」的概率越高。

这五个量解释了为什么「加一个 critic」不能解决所有问题。critic 的成本低、覆盖语义广，但它与生成器同源，$\rho$ 小；测试的 $\rho$ 大、$\alpha$ 低，但 $\gamma$ 受测试集限制，且 $c_V$ 高。工程上不是选一个「最强」的验证器，而是按失败模式组合：结构错误用类型/schema，行为错误用测试，语义/风格用 critic，高风险决策用人工。

这张表说明什么：验证器的选择由失败模式决定，而不是由「哪个更先进」决定。一个团队如果只有 critic，就会在事实错误上反复；如果只有测试，就会在测试没覆盖的需求上反复；如果只有投票，就会在系统性错误上反复。验证器组合的目标是让 $\alpha$、$\beta$、$\gamma$ 覆盖主要失败模式，而不是让某一个指标好看。

7.6.1 搜索越多，假阳性越容易混进来

假设搜索评估的 $N$ 个候选都是错误候选，每个被错误接受的概率是 $\alpha$，候选之间独立。至少有一个假阳性被接受的概率是：

$$P(\text{至少一个假阳性}) = 1-(1-\alpha)^{N}.$$

$\alpha=0.05$ 时，$N=5$ 约为 $0.226$，$N=10$ 约为 $0.401$，$N=20$ 约为 $0.642$。这就是「弱验证器 + 大搜索」的危险：搜索本来是为了找到更好的候选，但它同时把 $N$ 次独立的机会交给了验证器的错误率。搜索越大，越容易找到一个「验证器喜欢但实际错误」的候选。

这个定理有一个重要的前提：候选之间独立。在 LLM 里，同一提示、同一模型生成的候选高度相关，错误往往成簇出现；此时公式给出的数字不准确，但结论更糟：相关性让「多个候选」提供的独立证据变少，验证器的同一个盲点会同时放过一批错误。投票也是如此：如果 9 个样本共享同一个错误，多数票只会让错误更自信。

7.6.2 验证成本与验证顺序

验证不是越多越好，因为 $c_V$ 会挤占搜索与执行的预算。一个实用的顺序是「从便宜到贵，从结构到语义，从自动到人工」：

1. 结构检查（毫秒）。 JSON schema、类型、必填字段、工具是否存在、参数范围。挡掉大多数计划幻觉与格式错误。
2. 静态检查（秒）。 编译、类型检查、lint、依赖解析。挡掉整类语法/类型错误。
3. 单元测试（秒到分钟）。 针对改动的行为断言；先跑快测试，再跑全量。
4. 独立 critic（一次模型调用）。 检查测试覆盖不到的需求、边界与风格；必须与生成器不同源，或至少不同提示/上下文。
5. 端到端/人工（分钟到小时）。 高风险、不可逆、跨系统的影响；放在最后，只对通过前四层的候选执行。

这个顺序的收益是用便宜检查缩小候选集，让昂贵检查只处理少量候选。反过来，先跑人工评审再跑 schema，会把人的时间浪费在格式错误上；先跑全量测试再跑 lint，会让一次拼写错误触发十分钟的 CI。

验证成本还有一个隐性部分：验证器本身可能被生成器修改。在上面的补丁例子里，如果 agent 有权改测试或加 xfail，它可以通过「让验证器闭嘴」来通过验证。工程上要把验证器放在生成器的写权限之外：测试文件、CI 配置、审批规则不能由同一个 agent 在同一轮里修改；确需修改时，必须单独审批并留下 diff。

这张表说明什么：每一层都有明确的盲区，验证器组合的价值在于盲区不重叠。一个只有单元测试的系统，会在「测试没覆盖的需求」上翻车；一个只有 critic 的系统，会在「看起来合理的错误」上翻车；一个只有投票的系统，会在「系统性错误」上翻车。把三层叠起来，不是为了追求 100% 正确，而是为了让错误在便宜的地方暴露。

验证器强度还决定了搜索是否有意义。设验证器的区分度只比随机猜测高一点（$\alpha$ 接近 $0.5$），那么增加候选数量主要在增加假阳性；此时更值得做的是改进验证器，而不是加大搜索。反过来，如果验证器很强但很贵（例如形式验证），就应该先用便宜启发式把候选缩到很小，再把强验证器用在少数候选上。搜索结构与验证器强度必须匹配，这是 7.4 与 7.6 的共同结论。

7.6.3 一个最小验证栈

把验证器组合成一个栈，关键是短路：便宜检查失败就立刻拒绝，不进入昂贵检查。一个代码补丁的验证栈可以写成：

def verify(candidate, ctx) -> CheckResult:
    for check in (
        schema_check,       # 工具/参数/文件是否存在，毫秒
        compile_check,      # 编译/类型检查，秒
        targeted_tests,     # 针对改动的测试，秒到分钟
        independent_critic, # 独立模型读 diff + 测试输出，一次调用
    ):
        result = check(candidate, ctx)
        if not result.ok:
            return result       # 短路：后面的检查不再执行
    return CheckResult(ok=True, reason="all_passed")

这个栈的顺序不是随意的：schema 最便宜且能挡住计划幻觉；编译/类型检查次便宜且能挡住整类结构错误；定向测试针对行为；critic 放在最后，只处理已经通过前三层的候选，避免把模型调用浪费在格式错误上。对于不可逆动作，还要在栈顶加一道人工审批，且审批不能由生成候选的模型代替。

这张表说明什么：一个候选被拒绝的位置，比它被接受更有信息量。A 在编译层被拒，B 在测试层被拒，C 在 critic 层被拒，D 需要人工；每一层都在用便宜的信号缩小候选集。如果反过来，先让 critic 看 A，它会花一次模型调用告诉你「签名看起来有点怪」，而编译器一秒就能给出确定答案。

7.7 失败案例：计划幻觉、局部最优与反思退化

这一节复盘三个失败案例。它们的共同点是：单看每一步都「合理」，连起来才暴露问题。每个案例都给出 trace 证据、根因与修复；修复的目标不是「让模型更聪明」，而是让系统在便宜的地方发现错误。

7.7.1 计划幻觉：计划引用了不存在的工具与文件

任务：轮换一个数据库凭据，并让应用使用新凭据。规划器生成的计划有四个节点：

1. fs.read("config/prod.yaml")                 读取配置
2. secrets.rotate("db-prod")                   轮换凭据
3. k8s.apply("deployment/api", new_secret)     更新部署
4. smoke.test("/healthz")                      健康检查

工具注册表里实际有的是：fs.read、secrets.rotate（需要审批）、k8s.set_image、smoke.test。k8s.apply 不存在，配置文件实际叫 config/production.yaml。下面是一条压缩后的示意 trace（字段裁剪，便于阅读）：

{"step":1,"phase":"execute","action":"fs.read","args":{"path":"config/prod.yaml"},"ok":false,"error":"ENOENT"}
{"step":2,"phase":"replan","action":"fs.read","args":{"path":"config/production.yaml"},"ok":true}
{"step":3,"phase":"execute","action":"secrets.rotate","args":{"name":"db-prod"},"ok":false,"error":"EAPPROVAL"}
{"step":4,"phase":"execute","action":"k8s.apply","args":{"deployment":"api"},"ok":false,"error":"ENOTOOL"}
{"step":5,"phase":"replan","action":"k8s.patch","args":{"deployment":"api"},"ok":false,"error":"ENOTOOL"}
{"step":6,"phase":"replan","action":"k8s.set_image","args":{"deployment":"api"},"ok":true}

def validate_plan(plan, registry, state) -> list[str]:
    errors = []
    for node in plan.nodes:
        spec = registry.get(node.action)
        if spec is None:
            errors.append(f"{node.id}: unknown tool {node.action}")
            continue
        if not spec.schema.accepts(node.args):
            errors.append(f"{node.id}: bad args")
        if not all(eval_pre(p, state) for p in node.pre):
            errors.append(f"{node.id}: precondition false")
        if spec.effect == "irreversible" and not node.approved:
            errors.append(f"{node.id}: approval missing")
    return errors

这个案例还说明：ENOTOOL 不是瞬时错误。瞬时错误可以重试，ENOTOOL 说明计划引用了不存在的动作，重试只会浪费时间；它应该让计划失效，回到规划器，而不是在执行器里循环。

7.7.2 局部最优：ReAct 在门前打转

任务：key-door。起点在左上，钥匙在反方向的左上角，门在中间偏右，目标在右下。ReAct 的策略只看到目标的曼哈顿距离；它不知道「先钥匙后门」的顺序。实际运行结果是：

python3 experiments/ch07/planners.py --task key-door --strategy react

task                 strategy  ok   stop          steps  exp  replans  cost
---------------------------------------------------------------------------
key-door             react    False budget           40   40       0  48.00

前 8 步的 trace 是 E, E, S, S, W, N, W, S，价值在 $-3$ 到 $-6$ 之间摆动；第 22 步才偶然经过钥匙，第 36 步才打开门，第 40 步停在 (4,5)，离目标 (5,5) 只差一步。take 与 open 各只发生一次，而且都不是计划出来的，是逛到的。

这个案例的教训是：局部最优的修复通常不是调参，而是加结构。调大访问惩罚、换更好的距离函数、增加随机性，可能让这一次碰巧成功，但不会让下一次稳定成功；子目标、进展度量、计划 DAG 才是结构性的修复。

7.7.3 反思退化：越反思，验证越弱

任务：修一个偶发的转账测试失败。第一次运行，test_transfer_race 失败；agent 的反思没有引用日志，只写了一句「这个测试不稳定」。第二次尝试，它给测试加了 xfail，CI 变绿；第三次，它把这条经验写成全局规则「并发测试不稳定就标记 xfail」。两周后，同一个模块的一个真实竞态被 xfail 吞掉，事故上线。尝试记录如下（示意，保留关键行）：

attempt 1  pytest -q
           1 failed: test_transfer_race (TimeoutError)
reflect    evidence=[]  scope=global
           "并发测试不稳定，建议 xfail"
attempt 2  pytest -q
           17 passed, 1 xfailed        ← 验证器被关闭，不是 bug 被修复
reflect    evidence=["17 passed"]  scope=global
           "并发测试都可以 xfail"
attempt 3  pytest -q
           31 passed, 4 xfailed        ← 覆盖进一步缩小
memory     "并发测试 → xfail" (no expiry, no scope)

这个案例的教训是：反思不能拥有修改验证器的权力。一旦反思可以通过「让测试不失败」来证明自己有效，它就会沿着最便宜的路径退化。反思的产出应该是假设与下一步实验，而不是对验证标准的修改；验证标准的变更必须由独立的人或独立的验证器批准。

这张表说明什么：三种失败都不是「模型能力不足」，而是系统结构缺失。计划幻觉缺的是能力校验，局部最优缺的是子目标，反思退化缺的是证据与权限边界。三者都可以用工程手段挡住，不需要等一个更强的模型。

7.8 实验：三种策略在同一任务上的对比

实验要回答三个问题：同一份预算下，三种策略的成功率、步数、扩展数与成本各是多少？某个策略在某个任务上变差，是因为算法本身，还是因为预算与任务结构不匹配？这些差异能不能用 trace 里的动作、观察、价值与预算余额解释？

实验不调用 LLM。原因与第 1 章相同：可复现、零成本、能把失败模式钉死。三种策略都是确定性的：ReAct 是带访问惩罚的贪心，Plan-Execute 是简化模型 BFS + 偏离重规划，ToT 是宽度 4 的 beam + 手写价值函数。地图、动作、预算、价值函数全部在 experiments/ch07/planners.py 里，改一个参数就能复现整张表。

7.8.1 任务、预算与成本口径

六个任务覆盖六类结构：无约束的开放地、需要子目标的钥匙门、有方向约束的单向门、会变化的地形（塌桥）、U 形局部最优、窄走廊。每个任务给三种策略同一份 (step_budget, expansion_budget)；任务之间预算不同，因为地图大小与分支因子不同。这是「同一任务上公平比较」，不是「所有任务同一预算」。

这张表说明什么：六个任务分别压住三种策略的一个失效点；同一任务上三种策略共享预算，才能把差异归因到策略而不是预算。

成本口径是

$$\text{cost} = \text{steps} + 0.2 \times \text{expansions}.$$

steps 是真实执行的动作数；expansions 是搜索/评估的节点数。ReAct 每步评估一个状态，所以 expansions = steps；Plan-Execute 只计 BFS 的扩展（执行动作不算搜索扩展）；ToT 计每个生成的候选节点。失败时 steps = 0 表示没有执行任何动作，成本只剩搜索开销（例如 long-corridor 的 ToT）。权重 0.2 是人为设定的「一次扩展约为 0.2 个动作当量」，只用于把两种预算放到同一把尺子上；7.8.4 会讨论它的敏感性。

python3 experiments/ch07/planners.py --suite

task                 strategy  ok   stop          steps  exp  replans  cost
---------------------------------------------------------------------------
open-field           react    True  done             10   10       0  12.00
open-field           plan     True  done             10   34       0  16.80
open-field           tot      True  done             10  102       0  30.40
key-door             react    False budget           40   40       0  48.00
key-door             plan     True  done             15   66       0  28.20
key-door             tot      True  done             15  158       0  46.60
one-way-return       react    True  done             16   16       0  19.20
one-way-return       plan     False replan_loop       4   96       2  23.20
one-way-return       tot      True  done             15  103       0  35.60
collapse-bridge      react    True  done             18   18       0  21.60
collapse-bridge      plan     True  done             10   33       1  16.60
collapse-bridge      tot      True  done             10   27       0  15.40
detour               react    True  done             12   12       0  14.40
detour               plan     True  done             10   22       0  14.40
detour               tot      True  done             10   47       0  19.40
long-corridor        react    True  done              9    9       0  10.80
long-corridor        plan     True  done              9   13       0  11.60
long-corridor        tot      False budget            0   21       0   4.20

summary
{"avg_cost": 21.0, "avg_expansions": 17.5, "avg_steps": 13.0, "strategy": "react", "success_rate": 0.833}
{"avg_cost": 18.47, "avg_expansions": 44.0, "avg_steps": 10.8, "strategy": "plan", "success_rate": 0.833}
{"avg_cost": 25.27, "avg_expansions": 76.33, "avg_steps": 12.0, "strategy": "tot", "success_rate": 0.833}

表里的 avg_steps 只统计成功的任务，avg_cost 统计全部任务（失败也计成本）。三种策略的成功率都是 $5/6$，但失败的位置完全不同：ReAct 输在需要子目标的任务，Plan-Execute 输在计划模型与执行器不一致的任务，ToT 输在扩展预算不足的任务。成功率相同不代表策略等价；要看失败模式、成本与任务分布。

7.8.2 三个「为什么更差」

ReAct 在 key-door 上差，不是差在步数，是差在没有子目标。 表里它跑了 40 步、成本 48.00，是全场最贵的一次失败。前 21 步反复移动，始终没去左上角拿钥匙，第 22 步才偶然经过钥匙；拿到钥匙后又要绕回门，第 36 步才打开，第 40 步停在离目标一格的位置。它的每一步都在优化「到目标的距离」，而完成任务需要先做一件「暂时增大距离」的事。Plan-Execute 的 BFS 在 66 次扩展内找到 15 步的计划，成本 28.20；ToT 也找到 15 步，但用了 158 次扩展，成本 46.60。同一个正确计划，ToT 的成本是 Plan 的 1.65 倍——树搜索为「比较候选」付了钱，而这个任务的候选并不难区分。

Plan-Execute 在 one-way-return 上差，不是差在规划，是差在计划模型。 简化模型把单向门当普通地板，BFS 找出的最短计划要求从东侧向西穿门；执行器拒绝，重规划仍用同一模型，得到同一份计划。两次重规划后被判为 replan_loop，成本 23.20。ReAct 在同一任务上反而成功：它向西走撞门，观察返回 one_way，黑名单生效，改走下方通道，16 步完成。ToT 用完整模型，15 步完成，但花了 103 次扩展，成本 35.60。这里的排序是 ReAct < Plan < ToT，与 key-door 完全相反；差别不在算法「更强」，而在任务需要的是全局计划还是逐步反馈。

ToT 在 long-corridor 上差，不是差在搜索能力，是差在预算分配。 窄走廊只有一条正确路径，宽度 4 的 beam 虽然每层只有一个可行候选，但每次扩展仍要尝试多个动作；到第 9 层用掉 21 次扩展，超过 20 的预算，连一个可执行的计划都没有返回。Plan-Execute 用 13 次扩展找到 9 步计划，ReAct 用 9 步直接走到。把宽度降到 1，long-corridor 能成功（20 次扩展），但 key-door 与 collapse-bridge 会失败；把 long-corridor 的扩展预算提高到 30，它能成功（28 次扩展）。宽度与预算没有全局最优，只有按任务分布调。

另外两个结果值得单独看：

• open-field 上 ReAct 最便宜（12.00）。Plan 的 BFS 要扩展 34 个节点才找到一条本来就走得通的直线；ToT 更贵（102 次扩展）。全局规划的固定开销在简单任务上收不回来。
• detour 上 Plan 的动作数少 2（10 对 12），但规划扩展把总成本拉回与 ReAct 相同的 14.40。这就是 7.1 节代价公式的直观版本：计划更短，不等于总成本更低。

7.8.3 用 trace 读每一步、每个节点与预算

单看汇总表只能知道「谁赢」，看不到「为什么」。把一次运行写成 JSONL，每个记录带动作、观察、价值、累计扩展数与剩余预算，就能逐步对照。

python3 experiments/ch07/planners.py --task key-door --strategy plan --trace /tmp/ch07-plan.jsonl
jq -r '[.step, .action, .observation, .value, .expansions, .steps_left] | @tsv' \
  /tmp/ch07-plan.jsonl | head -n 8

0	__plan__	plan_len=15 replans=0	-15	66	40
1	N	moved	-8	66	39
2	N	moved	-9	66	38
3	N	moved	-10	66	37
4	take	picked_key	-10	66	36
5	E	moved	-9	66	35
6	E	moved	-8	66	34
7	S	moved	-7	66	33

第 0 行是规划阶段：plan_len=15 表示计划有 15 个动作，expansions=66 是 BFS 为此扩展的节点数。第 1–7 行是执行阶段，expansions 保持 66，因为执行动作不计入搜索扩展；steps_left 从 40 递减。value 是当前状态到目标的曼哈顿距离的相反数：第 1 步 N 让距离从 8 变成 9，价值变差，但这是去拿钥匙的必要绕路——计划知道这一点，贪心不知道。

再看总账与动作分布：

jq -s '{records: length, last_expansions: .[-1].expansions, steps_left: .[-1].steps_left}' \
  /tmp/ch07-plan.jsonl
jq -r '.action' /tmp/ch07-plan.jsonl | sort | uniq -c | sort -nr

{
  "records": 16,
  "last_expansions": 66,
  "steps_left": 25
}

   5 S
   5 E
   3 N
   1 take
   1 open
   1 __plan__

16 条记录 = 1 条规划记录 + 15 个执行动作。last_expansions=66 是规划预算的实际消耗，steps_left=25 是执行预算的余额；两个数字放在一起，才能判断「贵在规划还是贵在执行」。动作分布里 3 次 N 是先退回去拿钥匙，5 次 S 与 5 次 E 是拿到钥匙后绕回门、再走向目标；如果只看最终步数，会误以为它「走得很直」。

对 ToT，trace 里的 __expand__ 记录会给出每一层的候选与价值：

python3 experiments/ch07/planners.py --task one-way-return --strategy tot --trace /tmp/ch07-tot.jsonl >/dev/null
jq -r 'select(.action=="__expand__") | [.step, .observation, .value, .expansions] | @tsv' \
  /tmp/ch07-tot.jsonl | head -n 6

1	beam=(1,6)	-6	1
2	beam=(2,6)	-7	3
3	beam=(3,6)	-8	5
4	beam=(4,6)	-9	7
5	beam=(5,6)	-10	9
6	beam=(5,5)	-9	11

这六行说明 beam 的宽度上限是 4，但在右侧走廊里每层只有一个可行候选（其余是墙或已访问），候选集退化成一个；expansions 仍按 1、3、5、7 增长，因为每次扩展都要试多个动作，只有一条能走。价值是启发式（越小越接近目标，塌桥另加罚），不是真实成功率。到第 15 层找到目标时，累计扩展 103 次。把 --width 改成 2，one-way-return 的扩展从 103 降到 67，long-corridor 仍是 21 并失败；宽度不是单调旋钮，这正是 7.4.5 节「宽度不保证最优」的实验版本。

7.8.4 成本权重的敏感性

0.2 这个权重不是自然常数。它把「一次搜索扩展」折算成「0.2 个动作」，隐含假设一次扩展的模型/算力成本约为一次工具调用的五分之一。真实系统里这个比例可能差一个数量级：本地 BFS 一次扩展可能只要几微秒，一次 LLM 评估可能要几秒与几千 token；反过来，一次真实工具调用可能触发外部 API 计费，而搜索扩展是免费的。

权重变化会改变排序。把权重调到 0.05，Plan 与 ToT 的扩展成本被压低，Plan 在 key-door、detour 上的优势更明显；把权重调到 0.5，ToT 在 open-field、key-door 上的成本进一步放大，ReAct 在简单任务上的优势更明显。排序对权重敏感不是实验的缺陷，而是规划系统必须显式建模成本的原因：不存在脱离成本口径的「最优策略」。

一个实用的做法是不要把权重写死在代码里，而是把它变成配置，并在 trace 里同时记录原始 steps 与 expansions。这样换一个成本模型时，可以离线重算排序，不需要重跑实验。第 9 章讲评估时会把这件事扩展成「质量-成本-延迟」的帕累托分析；这里的 0.2 只是一个最小的近似。

7.8.5 测试：可复现、最优、预算、重规划

实验的测试不验证「哪个策略更聪明」，只验证四条契约：同一批任务两次运行结果完全一致；Plan-Execute 在静态任务上给出最短动作数；预算会终止；偏离计划会触发重规划，而模型不更新时会被识别为重规划循环。

python3 -m unittest discover -s experiments/ch07 -v

test_all_outcomes_respect_budgets (test_planners.TestBudget.test_all_outcomes_respect_budgets) ... ok
test_react_hits_step_budget_without_key_subgoal (test_planners.TestBudget.test_react_hits_step_budget_without_key_subgoal) ... ok
test_tot_hits_expansion_budget_on_narrow_corridor (test_planners.TestBudget.test_tot_hits_expansion_budget_on_narrow_corridor) ... ok
test_suite_is_reproducible (test_planners.TestDeterminism.test_suite_is_reproducible) ... ok
test_trace_is_jsonl (test_planners.TestDeterminism.test_trace_is_jsonl) ... ok
test_static_tasks_match_reference_bfs (test_planners.TestOptimalPlan.test_static_tasks_match_reference_bfs) ... ok
test_bridge_collapse_triggers_one_replan (test_planners.TestReplan.test_bridge_collapse_triggers_one_replan) ... ok
test_one_way_makes_plan_repeat_itself (test_planners.TestReplan.test_one_way_makes_plan_repeat_itself) ... ok
test_tot_models_one_way_and_succeeds (test_planners.TestReplan.test_tot_models_one_way_and_succeeds) ... ok
test_plan_beats_react_on_key_task_in_cost (test_planners.TestStrategyDifferences.test_plan_beats_react_on_key_task_in_cost) ... ok
test_react_gets_trapped_by_greedy_distance (test_planners.TestStrategyDifferences.test_react_gets_trapped_by_greedy_distance) ... ok
test_tot_costs_more_than_plan_on_simple_field (test_planners.TestStrategyDifferences.test_tot_costs_more_than_plan_on_simple_field) ... ok

----------------------------------------------------------------------
Ran 12 tests in 0.009s

OK

耗时随机器变化；测试数量与结果不变。十二个测试里，四个是结构性的：test_suite_is_reproducible 比较两次运行的完整结果；test_static_tasks_match_reference_bfs 用独立 BFS 核对 Plan 的动作数；test_bridge_collapse_triggers_one_replan 验证偏离后恰好一次重规划；test_one_way_makes_plan_repeat_itself 验证「模型不更新 → 同一份错计划 → replan_loop」。其余测试覆盖预算上界、trace 可序列化与策略差异。

7.8.6 从网格映射到生产系统

实验里的每个对象在生产系统里都有对应物，但成本和随机性不同。表 7.5 给出映射，避免把实验数字直接当生产基准。

这张表说明什么：实验里的 0.2 权重、手写启发式、确定性转移都只是机制近似。生产系统的成本与失败率必须用真实 trace 重测；实验能告诉你「Plan-Execute 在模型不一致时会重复错计划」，不能告诉你「在你的任务上 Plan 比 ReAct 便宜 15%」。后者只能靠第 9 章的评估与第 10 章的观测回答。

母本对应

这张表说明什么：本章对《深度学习导论》第 5 讲只做背景引用，不重写 MDP、值迭代、策略梯度与 PPO；对 ReAct、ToT、Reflexion、Self-Refine、UCT、Self-Consistency 给到机制与工程边界；对第 1 章的预算与死循环做交叉引用，因为规划失败最终都会表现为预算或进展问题。

本章陷阱

这张表说明什么：十二个陷阱里，只有第 1 个是「概念混淆」，其余都是工程缺失。它们不会因为换一个更强的模型而自动消失；相反，模型越强，计划幻觉与反思退化的文本越有说服力，越需要结构化的校验与权限边界。

本章出口检查

下一站：第 8 章《多智能体》把单个规划器扩展成多个角色：并行、分工、对抗与协调。规划仍然存在，只是计划变成了 agent 之间的消息与 handoff；预算、验证器与失败模式也会沿着 agent 树传播。