Planning and Multi-Step Reasoning

这是什么

CS329A Self-Improving AI Agents 第五讲，片长约 75 分钟（duration_s: 4496）。前一讲是工具与执行反馈；本讲把舞台交给多步规划：模型不但要想，还要 act，还要在多条轨迹里搜。课上三篇：

1. Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models（LATS；课上称 ICML 去年）— 把 ReAct 轨迹接到 Monte Carlo Tree Search（MCTS）；用 LLM-as-a-Judge + self-consistency 给状态打分，用 UCT 选节点。
2. SPRINT（NeurIPS 2025，课上说当时还没在会上讲）— 用 LLM 把长推理轨迹标成 plan / execution 的 DAG，SFT 教模型并行分叉思考，减顺序 token、顺带涨点。
3. SWiRL（课上预告下一周 COLM / Conference on Language Modeling，蒙特利尔）— 离线合成多步「推理 + 工具」轨迹，再用 RL 学何时调工具、何时改推理、何时停；训练环里不跑活工具。

素材：raw/collections/cs329a/05-planning-and-multi-step-reasoning.md。00:00:05 00:23:26 00:50:25

核心要点

• 规划任务拆三步：reason（预算、去哪、约束）→ act（搜网页、读 Reddit / travel blog）→ search（拿观察改计划、换目的地、加行程）。缺搜索就只剩「生成一个计划然后执行」。00:01:02 00:01:17 00:01:40
• 到今天模型仍不擅长「产出多样解、再沿多条路径优化」。LATS 把已有的多步 MCTS 搬进 LLM 推理，并把环境反馈折回后续扩展。00:02:23 00:02:58
• LATS vs Math-Shepherd vs ReAct：Math-Shepherd 用 verifier 给推理轨迹打分再导搜索；LATS 的分来自动作结果、模型对轨迹的 reflection、以及环境观察。相对 ReAct，多了轨迹记忆、reflection、环境交互，以及显式规划。00:05:33 00:06:19
• LATS 六阶段：selection → expansion → evaluation → simulation → backpropagation → reflection。选择用 UCT；评估把 LLM-as-a-Judge 的 0–1 分和 self-consistency（同型动作被采到的频率）加在一起。00:07:57 00:10:11 00:13:59
• 重复动作不会当成无关新边：同一父节点下再见到同一动作，就加 visit count，UCT 会压它。形成的是树，不是全连接图。00:22:49
• 树搜索的代价没在论文里做 cost-benefit；也没处理不可逆动作（付款、下单）。UCT 之外的 bandit 算法没比过——讲者把贡献说成「先搭一个别人能换优化器的平台」。00:19:27 00:21:16
• 前沿推理模型（o1、Gemini Think、Gemini 2.5 Pro）题越难想越长。DeepSeek-R1 训练过程中 AIME 变好，同时平均回复长度也在涨。但长 CoT 里不少子步骤彼此独立，不必串行等完。00:23:59 00:24:38
• SPRINT 用 DeepSeek-R1 出轨迹、GPT-4o 标 plan/execution 并建 DAG，再 SFT。配方：MATH 上生成 6k 条 thinking trajectory，留下并行度高的，SFT DeepSeek-R1 Distill-Qwen-7B。目标本是砍顺序 token，结果准确率也涨：相对 Distill-7B 大约 3.5 个点，顺序 token 比 32B 更省。MATH 上相对可比准确率的方法，顺序 token 大约少 40%。00:36:26 00:37:27 00:44:31
• 在 MATH 上练的并行思维，能转到没训过的 Countdown、GPQA Diamond。难题更吃多轮 plan–execute；早期分叉多、后期收成少数计划往下钻。思考很短时，硬上 plan-and-execute 可能比 RFT（rejection fine-tuning）基线更差。00:38:14 00:40:48 00:45:12
• 工具在训练环里又慢又会挂。SWiRL 的策略是离线合成多步轨迹再 RL。Gemma-2-27B 在 HotPotQA / GSM8K 上造数据（课上说大约 50k 量级）。过程过滤（每步都被 LLM-as-a-Judge 判好）比「只要最终答案对」更利于 RL；SFT 则相反，要过程+结果都对。00:52:13 01:06:28 01:07:10 01:12:47
• 合成数据从 100 → 10,000 时，连训练时没当主任务的 MATH / GSM8K 也涨。GSM8K + SymPy 训完，HotPotQA 从 65 → 71；HotPotQA + 搜索工具则 65 → 73，并能反过来帮 GSM8K + Python。学的是「分步想、何时调工具」，不是某一把具体工具。01:08:19 01:10:11
• Claude Sonnet 4.5 的 system card 里，系统提示鼓励尽量用工具、至少 100 次。讲者读成：真实 agent 要被 nudging 才会够勤快地 act；题也已经超出 8k–10k token 量级。00:46:17

机制 / 论证

多步任务：reason → act → search

旅行规划是贯穿本讲的例子。Reason：预算是多少、想去哪。Act：已经有想法之后，怎么收集信息——浏览网页、发搜索、读 Reddit 或 travel blog。Search：拿到反馈后怎么改计划——换目的地、加当地活动。解决「规划一次旅行」需要这三类步骤反复交错，而不是一次生成一份行程就结束。00:01:02 00:02:02

LATS 要对付的缺口是：从「LLM 生成一个计划并执行」走到「鼓励多样化、探索多条计划」。模型至今仍不擅长产出多样解、再沿多条路径做多步优化。论文把强化学习里已有的多步 MCTS 接进 LLM 推理；因为模型吃得进反馈，探索环境时拿到的观察可以折回来，改后续计划和搜索。00:02:23 00:03:16

夏威夷行程的示意图：对同一 prompt 采样，模型可能决定「问去过的朋友」或「读相关 subreddit」。框架给每个动作一个分数，按分更新树的后续扩展。动作 1 分更高就展开：分别问朋友 A、朋友 B，再按回复质量打分继续扩。多个动作可以并行执行。MCTS 进来的位置是：既要顺着当前最好状态继续探索，又要在探索 / 利用之间混合。00:03:39 00:05:06

直觉拼三块：Chain-of-Thought 把推理拆成步；动作生成把轨迹铺成树，在树上搜索和规划；ReAct 把动作反馈写进后续搜索。00:07:11

LATS 六阶段：用迷宫把 MCTS 走一遍

课上的工作例子：在迷宫里走到出口。初始观察：光线很暗的房间，左右各一扇门。00:08:20

开左门的观察是「有画的黑暗走廊」。评估建议把两个分数加总：（1）LLM-as-a-Judge，按当前动作和观察问「这个状态有多有希望」，打 0–1；（2）self-consistency：假设不是采 3 次而是采 50 次，按动作类型归类，采得越频分越高。课上的示意：状态 A 大约 75% 的采样落在该动作，self-consistency 更高。价值函数是这两项的加权平均（权重课上没给）。00:09:08 00:10:11 00:13:15

Simulation 从 s_A 贪心往下，例如走楼梯，碰巧看到标明的出口。有了成功或失败的轨迹之后，才进入回传。00:11:22

UCT、回传公式、reflection

选择不用「当前价值最高的节点」，否则会错过此刻分低、后头可能更高的分支。UCT（Upper Confidence bounds applied to Trees）完全借自 MCTS：V(s) 负责利用，再加超参 × 探索项。N_p = 父节点访问次数，N_s = 当前节点访问次数。相对父节点访问少，就鼓励再访；访问已经很多，这一项变小，UCT 相对未探索的兄弟节点更低。00:13:44 00:14:29

学生问这是不是最优。讲者说没有证明这是最优配比，只是被认为更能平衡探索 / 利用。00:16:02

回传（课上写出的更新）：新价值 =（旧价值 ×（访问次数 − 1）+ return）/ 总访问次数。00:15:40

Reflection：轨迹结束后，模型追加对失败或成功原因的思考。课上说这一项对整体质量「显然很有帮助」。00:16:56

LATS 实验、代价、答疑

HotPotQA：每道题至少要检索两篇 Wikipedia，题目本身就是多步。增加采样 / 轨迹条数，表现明显涨；把 reflection 和推理痕迹折回去，末段还有一大截增益。这是「测试时多算力 → 更好的多步解」的一条可操作机制。00:17:14

WebShop：例如找一张已经组装好的小号便携折叠桌，还要颜色、饰面、价格。同样无微调、只在测试时跑，结果很高，课上说甚至接近人类专家。具体数字课上没念。00:18:06

优点：推理、行动、规划收在一起；模块化、相对好接；跨域结果强。缺点：每次回传和扩树都很贵，论文没做成本收益。没处理的假设：动作可能不可逆——模型若真的付款、下单，后果很大，这套方法不一定适配。00:19:27

课堂讨论：

• UCT 只是 bandit 里 upper confidence bound 的一种。有没有试过别的探索算法？没有。讲者认为主贡献是先搭平台，别人可以把别的优化器接进来。00:21:16
• 同一动作在多个节点重复、轨迹里出现 ABAB，树认不认？同一父节点下重复动作就加 count，进入 UCT；假设是树，不是全连接图。00:22:15

SPRINT：长思考里有可并行的独立块

动机不来自搜索树，而来自推理模型的行为：o1、Gemini Think、Gemini 2.5 Pro 以及当时几乎所有前沿模型，难题会想得更久，更长的思考对应更高准确率。DeepSeek-R1 训练过程中解 AIME 变好，平均回复长度同步上升。00:23:59

但长推理里有三类可拆的东西：备选解法、可并行的子任务、对前一步的核对。推理图里一部分计算互不依赖，不必等模型把它们一个 token 一个 token 串完。SPRINT 在后训练 / 微调里给推理模型配一个 planner（给出一组计划）和一组可并行的 executor；plan 与 execution 可以多层交错，用来加速。00:25:01 00:25:57 00:26:45

用模型给模型造「并行思维」数据

行为要用微调数据教。做法是让 LLM 自己参加数据生产：

1. DeepSeek-R1 针对问题生成推理轨迹和最终回答。
2. GPT-4o 把轨迹标成步骤 1…k，并标每步里哪一段是 plan、哪一段是 execution；有的 plan 对应多段 execution。
3. 再用模型判断步骤依赖，建成 DAG。课上例子：步骤 4 和 2 互不依赖，都依赖步骤 1。
4. Packing：步骤 1 先做，步骤 2 和 3 完全并行，以此类推。
5. 得到带并行 plan / execution 的数据集后，SFT 大推理模型（课上用 Distill-Qwen-7B），让它按标签输出「plan i + 一组可并行 execution」。00:27:30 00:29:09 00:30:49

推理时模型吐出这些 tag 之后，系统可以真的并行执行、把结果 sync 回 context，再进入 plan i+1。执行可以是工具，例如 Python 计算器。00:31:20 00:33:21

顺序基线是：query → plan1 → exec1 → plan2 → exec2 → …。微调后：先并发生成 plan 1 和 2，再同时执行。训练数据把互相独立的 plan 并排放，后面接对应 execution；推理时 execution 才真正并行。模型仍是 next-token；并行靠 tag 把分支打开，不是改网络结构。00:32:24 00:35:48 00:49:06

学生问：执行完发现错了，怎么记得该回到 plan 3 而不是 plan 2？答：每个时刻都在教「能并行就并行」，包括修订已有计划；模型看得到全部 context，仍可回退。独立的 plan 2 不必等 plan 1 执行完再生成。00:33:57

SPRINT 的数字、泛化、答疑

配方再写一遍：MATH 上 6k 条 thinking trajectory，留下并行度更高的，SFT DeepSeek-R1 Distill-Qwen-7B。立项时只想最大化并行、减少顺序生成；结果结构化思考也抬了准确率。相对 R1 Distill-7B 大约 3.5 个点，同时顺序 token 比 32B 更省。模型会探索更多、更并行地想。00:36:26 00:37:11

域外：并行思维只在 MATH 上训，Countdown 和 GPQA Diamond 的并行机会和准确率都更好，这两个集没有拿来训练。讲者同意一种解释：并行思考本身在帮模型；省顺序 token 是副作用。00:38:14

并行分支各自看起来对、合在一起错怎么办？无论串行还是并行，最后都要压进同一段 context，模型应在最终答案前化解矛盾。两种做法都会受矛盾思考之苦。课上看到的 plan 更像「同一道题的不同步骤」，不是「同一道题的不同解法」。00:39:20

另外两条观察：更难的题需要更多轮迭代的 plan–execute（比较直觉）；不那么直觉的是——前段并行 / 探索更多，后段计划变少，往单一 plan–execute 里深挖。00:40:48

负载均衡：无法保证独立子计划耗时相近，仍可能有 straggler。但墙钟被最长那一步卡住，而不是「步骤 4 + 步骤 2」串起来。补救：execution 太简单就并进 plan，拼成更大的可并行块。有没有按组做负载分析，讲者说不确定。00:41:44

树宽（能挖多少并行）是任务相关的。MATH 的顺序 token 比例低于 GPQA Diamond，说明有的任务天生更可并行。课上没有给出平均 / 最大宽度。MATH 上相对准确率相当甚至更低的方法，顺序 token 大约少 40%。思考 token 很少时，机会不够，plan-and-execute 相对 RFT 基线可能更差；难题、需要更长思考时，方法才发光。需要更多思考的题，顺序 token 节省更大。00:43:07 00:45:12

推理时并不是把步骤 1…k 一次铺成多层；模型仍按「同时可并行的那一组 plan」顺序往前走：先吐 plan 1 和 2，各 plan 一结束就开执行，结果回写，再吐下一组。00:47:00

讲完 SPRINT 时点了后续：这期做的是 SFT；RL / GRPO 可能从同一类数据里再挖泛化。工具重叠执行、把墙钟加速做实，也还是实现层的活。00:49:47

SWiRL：离线合成多步，训练时不跑工具

真实任务要多步推理加工具：搜索引擎上的多跳问答、数学、软件工程项目、旅行规划、数据分析。人会连续用多种工具想好几步。单步已经复杂；步数一加，错误会复合。还要教会模型用对工具（计算器、Python executor）。训练过程中现场调工具很麻烦：工具会失败、会慢，训练本身已经又慢又脆。00:50:48 00:51:35

回看 RLHF / AI feedback / execution feedback：很多是按单步优化的——模型随便生成，最终答案对不对给奖励，再往回传。SWiRL 想管的是步骤过程本身。00:52:31

设计目标：复杂多步题；知道何时调工具；生成调工具的正确 query；跨步保持准确；从错误里恢复；知道何时停止新步骤 / 新工具、改出最终答案。同时训练时避开活工具（慢、失败、有 bug），并希望迁到新工具和新推理任务。00:53:24

合成数据、逐步打分、训练时假执行

数据：让模型一次只走一步。每步告诉它：可以推理 / CoT、可以调工具、也可以给出最终答案。第一步：原 prompt +「你有这些工具」。模型给出「推理 + 工具调用」后，把环境返回拼回去，再问下一步——原 prompt、上一动作、环境结果都在。不同问题的步数可以是 1、3、5……。00:54:34 00:56:19

标签：LLM-as-a-Judge 看先验 context 和当前动作（推理 + 工具调用），估计这条轨迹 / 该步有多好。整段可以离线、对很多问题并行做。过滤有几档：

• 过程过滤：每一步都被 judge 判好才留。
• 结果过滤：只要最终答案对，不管逐步标签。
• 过程 + 结果都过；或随机。00:56:40 00:57:33

RL 时的例子：谁更年长，Glenn（课上没记清姓）还是 Ross Lynch？动作 1：先搜第一个人的年龄，judge 给这步奖励；环境结果已在训练数据里，再提示下一步。动作 2：搜第二个人。最后模型用 answer 标签交最终答案，再拿一步奖励。00:58:47

关键设计：训练时不调工具。轨迹里的动作和工具返回是预先采好的。RL 时把 prompt 和前 k 步（含环境返回）给模型，让它出下一步，不执行这个新动作，只按该动作收奖励。工具调用全部发生在标注阶段。Judge 没有另训，只是 prompting。Judge 打的是「这条工具 query 好不好」，不是工具返回好不好——「去搜这个人的年龄」在看到搜索结果之前就可以判断是不是合理问题。这是逐步的 process reward；历史工具返回已经在离线 context 里。01:00:11 01:01:29 01:02:07

目标：步骤 S1…SK，每步是推理 + 工具调用。优化的是「在已收集的状态 / 动作条件下，单步动作的期望奖励」，从动作 1 到动作 K 都做。01:03:09

推理时改回真工具。课上计算器例子：用尽量少的词回答；若计算器有用，把数学 query 放进指定标签；信息够了就打 answer 标签。逐步：模型调计算器 → 真正执行 → 把输出连同历史再喂回去，直到它选择停。01:04:18

过程过滤为什么比「答案全对」更有用

实验：Gemma-2-27B 造多步合成数据；题来自 HotPotQA 和 GSM8K；大约 50k 量级，再按过程 / 结果 / 两者 / 随机过滤。01:06:28

反直觉结果：只做过程过滤（逐步被 LLM-as-a-Judge 多数判好，不按最终答案对错筛）比「只留最终答案对的轨迹」或「过程+结果都对」更帮 RL。解释：若只喂模型已经能做对结局的轨迹，测试时那些它本来就不会的题，仍然缺新的思考方式；过程对、结局不一定对的轨迹，反而在教它用另一种方式想。01:06:55

泛化（讲者说是最有意思的图，SPRINT 也出现过同类现象）：

• 在 GSM8K 上教模型用 SymPy（课上称为计算器），再测 HotPotQA：基座 65 → 71。
• 若直接用 HotPotQA、工具改成搜索： 65 → 73。
• 反过来也成立：HotPotQA + 搜索上训，GSM8K + Python 也好。

结论偏向：不只是学会某一把工具，而是学会分步思考、以及何时 invoke 工具。01:08:19

另一张「最重要」的图：全程用 HotPotQA + 搜索来训，合成数据从 100 条拉到 10,000 条，推理时在完全不同的 MATH / GSM8K 上继续涨。在更容易造数据的环境里教多步和工具，行为可以迁到全新工具和域；把这条放大，讲者认为可能是很强的方法。01:09:43

为何变好：看逐步的平均 process reward。RL 之后，过程正确性在分布内（HotPotQA）和分布外（GSM8K）都升了——每一步想得更对。01:10:53

同一套流程也可以改成 SFT。多步 RL 明显优于 SFT。SFT 作为模仿学习，需要过程和结果都过滤后的正确轨迹；只做过程过滤会伤 SFT。RL 则在已有前缀上让模型重新采样下一步、按新动作给奖励，从而跳出模仿。01:12:15

Precision / recall、以及和前沿模型的对照，课上翻了片子但超时，字幕里没有可用数字。01:11:52 01:13:34

收束：SWiRL 跨数据集、跨工具泛化；迁到不相近的任务；RL 更吃过程过滤数据；合成数据变多，域内域外都有增益；微调后过程正确性上升，这在分布内外都成立。01:13:51

可操作

• 短任务、分叉少：先 ReAct。需要备选计划、回溯、用观察改路线时，再上树搜索（LATS 这一类），不要默认每条请求都扩 MCTS。
• 树搜索把测试时算力换成更好的多步解（HotPotQA 上加轨迹就涨），但扩树和回传很贵，先预算 visit / 扩展上限。动作会真下单、付款时，不要直接套「执行再打分」——论文没处理不可逆。
• 重复动作用 visit count 压，而不是当新边。UCT 只是探索项的一种；换 bandit 公式是开放接口，不是已比过的结论。
• 长推理先问：哪些子步骤其实独立。能标 DAG 就标；SFT 带 plan/execution 标签，让模型在推理时自己吐可并行块。思考本来就短的题，不要硬上并行框架，可能比 RFT 更差。
• 训练环尽量不要绑活工具。离线采好多步轨迹（逐步 prompt：可想、可调工具、可停），用 LLM-as-a-Judge 给过程分，再 RL。Judge 打的是 query 质量，不是工具返回。
• 过滤策略随算法：RL 优先过程过滤；SFT 要过程+结果都对。合成数据从百级拉到万级，域外任务仍可能涨。
• 系统提示里 nudging 工具次数（Sonnet 4.5 的「至少 100 次」）说明：只给工具不够，还要明确鼓励 act。
• SPRINT 这期停在 SFT；若要再挖泛化，课上点名 RL / GRPO，以及把并行执行的墙钟做实。

术语

不确定 / 待验证

• 并行子计划如何保证耗时相近：课上没有干净答案。可以合并过小的 execution，仍可能有 straggler；有没有分组负载分析，讲者说不确定。00:41:44 00:43:07
• SPRINT 的树宽（平均 / 最大）课上没有数字；只说任务相关，MATH 比 GPQA Diamond 更可并行。00:43:31
• LATS 的 HotPotQA / WebShop 具体分数、相对哪些基线、离人类专家多近，字幕里没有数字。WebShop「接近人类专家」是课上口头判断。
• LATS 价值函数里 LLM-as-a-Judge 与 self-consistency 的权重、UCT 超参，课上没给。
• SWiRL 真正做 RL 的策略模型是不是就是造数据的 Gemma-2-27B，字幕只明确了 Gemma-2-27B 用来造多步数据。[需要验证]
• 「大约 50k」是问题数还是轨迹数，课上说的是 sourced from a number of problems，粒度不清。
• SWiRL 相对前沿模型、precision / recall 的片子课上翻过但超时，没有可用数字。01:11:52
• SPRINT 的 3.5 个点、MATH 顺序 token −40%，是哪张表、哪个 split，课上口头给出，未与论文核对。
• 论文正式年份：LATS 只说「ICML 去年」；SWiRL 只说「下周 COLM」。不要在本页写成已核对的 venue/year。

相关

• CS329A Self-Improving AI Agents
• Test-time compute
• Tool use and execution feedback
• Process reward models
• Train-time RL for reasoning
• Generation-verification gap
• Test-Time Compute Scaling
• Robust Verification
• Learning from Feedback with Tools/Code
• Train-Time Scaling / Scaling RL