SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Models¶

会议: NeurIPS 2025
arXiv: 2506.05745
代码: https://github.com/stanford-futuredata/Sprint
领域: LLM推理
关键词: 推理加速, 并行推理, 规划与执行, Chain-of-Thought, 推理模型

一句话总结¶

通过将长链式推理轨迹重组为交替的规划-并行执行阶段，Sprint 使推理模型在保持准确率的同时，将长推理链的顺序 token 数减少高达 39%（OOD 任务上最高 65%），实现推理过程的动态并行化。

研究背景与动机¶

领域现状：大型推理模型（LRM）如 DeepSeek-R1、OpenAI o1 通过生成长链的 Chain-of-Thought 来解决复杂推理任务，准确率很高但推理延迟极大——一道数学题可能需要生成数千个 token 才能得到答案。
现有痛点：现有加速方案要么缺乏协调（repeated sampling / self-consistency 生成多条独立轨迹但信息不共享）、要么依赖预定义的搜索结构（Tree-of-Thought / Graph-of-Thought 需要人工设置搜索模式）、要么不支持多步依赖推理（Skeleton-of-Thought 假设子任务语义独立，对数学推理这类后步依赖前步计算的任务效果差）。
核心矛盾：推理准确率要求长链顺序思考，但实际上许多推理步骤之间是相互独立的——比如同时尝试两种解法、独立计算一个复杂问题的不同子部分。现有方法没有让模型自己学会发现和利用这些并行机会。
本文要解决什么：如何让推理模型自主识别推理过程中的并行化机会，并在保持准确率的前提下减少顺序 token 生成数？
切入角度：仔细分析 R1 的推理轨迹发现，其中包含反思、任务分解、试错等步骤，很多步骤之间并无依赖关系。如果能把这些独立步骤识别出来并行执行，就能大幅缩短推理的"关键路径"。
核心 idea 一句话：通过数据管线将顺序推理轨迹重组为 DAG 结构的并行阶段，再用 SFT 教会模型在推理时自主进行交替规划和并行执行。

方法详解¶

整体框架¶

Sprint 包含两部分：（1）训练时的数据整理 pipeline，把普通的顺序推理轨迹转化为结构化的规划-并行执行格式；（2）推理时的 planner-executor 架构，模型交替扮演 planner（规划独立子任务）和 executor（并行执行子任务）角色。

输入是用户 query，planner 生成当前阶段的规划（可能包含多个独立子任务 prompt），多个 executor 并行执行各子任务，执行结果合并回累积上下文，planner 再做下一轮规划，如此迭代直到输出最终答案。

关键设计¶

数据整理 Pipeline（训练数据构造）:
做什么：把 DeepSeek-R1 生成的原始顺序推理轨迹转化为可并行的阶段化格式
核心思路：分四步——(a) Step Extraction: 用 GPT-4o 将推理轨迹拆分为离散的推理步骤 \(S = \{S_1, S_2, ..., S_n\}\)，每步进一步分为规划阶段 \(P_i\) 和执行阶段 \(E_i\)；(b) DAG Creation: 用 GPT-4o-mini 判断步骤间的依赖关系，构建有向无环图 \(G=(S,D)\)；(c) Packing: 将同一 DAG 深度的无依赖步骤打包到同一个 stage，特别优化了 plan-only 步骤——如果父节点是 plan-only，子节点可以合并到同一 stage；(d) Filtering: 只保留并行化比率（steps/stages）≥1.5 的轨迹
设计动机：直接从真实推理轨迹中挖掘并行结构，而非人工设计，保证了训练数据的自然性和多样性
Planner-Executor 推理架构:
做什么：推理时让同一个微调后的模型交替扮演 planner 和 executor 两个角色
核心思路：在 stage \(i\)，planner 接收完整累积上下文（query + 之前所有 plan 和 execution 结果），生成 <Plan_i> 标签内的规划文本，其中可能包含多个 <prompt_i.j> 子任务；每个子任务由独立的 executor 并行执行，结果封装在 <execution_i.j> 标签中同步回主上下文
设计动机：planner 每轮都能看到之前所有执行结果，避免了 SoT 等方法因单轮规划导致子任务之间缺乏协调的问题；executor 并行执行则直接减少了顺序 token 数
Packing 优化（stage 分配策略）:
做什么：最优化地将步骤分配到 stage，最大化并行度
核心思路：stage 编号的计算公式为 \(\sigma(S_i) = \max_{S_p \in \text{Parents}(S_i)} (\sigma(S_p) + \mathbb{1}(E_p \neq \emptyset))\)，关键在于如果父节点 \(S_p\) 是 plan-only 步骤（\(E_p = \emptyset\)），子节点不需要等待其执行结果，可以归入同一 stage
设计动机：贪心地压缩 stage 数量，同时短执行（<3行）被合并为 plan-only，减少 executor 调用开销

训练策略¶

从 MATH 训练集上 R1 生成的 6000 条轨迹中，经过答案正确性过滤和并行化比率过滤，得到约 1700 条训练样本
对 DeepSeek-R1-Distill-Qwen-7B 做全量 SFT（LoRA 效果不好，模型无法遵循格式），5 epochs，学习率 \(1 \times 10^{-5}\)
使用 ZeRO Stage 3 + 4-bit 量化在 8×A100 上训练

实验关键数据¶

主实验¶

数据集	方法	准确率	顺序Token数	总Token数
MATH-500	R1-Distill-7B	89.1%	-	-
MATH-500	RFT	91.0%	2880	2880
MATH-500	SoT-reasoning	90.8%	3836	11538
MATH-500	Self-consistency	80.5%	590	11645
MATH-500	Sprint	92.5%	2440	3622
Countdown	RFT	84.9%	4917	-
Countdown	Sprint	85.9%	2284	-
GPQA-Diamond	RFT	50.5%	7103	-
GPQA-Diamond	Sprint	51.0%	6336	-

效率分析（按推理长度分段）¶

RFT 顺序Token范围	Sprint 顺序Token减少比例
<2000 tokens	+5%（轻微开销）
4000-6000 tokens	~20% 减少
>8000 tokens	39% 减少
Countdown 长轨迹	65% 减少
GPQA 长轨迹	45% 减少

关键发现¶

Sprint 在 MATH-500 上准确率 92.5% 超过 RFT 的 91.0%，可能是因为并行执行中独立的子任务不会相互干扰，减少了错误传播
问题越难（需要的 token 越多），Sprint 的并行化收益越大——在 >8000 token 的问题上减少 39%
简单问题上有约 5% 的开销（plan/execution 标签和额外 prompt 格式的代价），但整体仍有 15% 的平均顺序 token 减少
Sprint 在完全 OOD 的 Countdown 任务上减少 53.5% 顺序 token，说明模型学到了通用的并行化推理能力而非任务特定的模式
SoT-reasoning 虽然也尝试并行，但总 token 数是 Sprint 的 3 倍（11538 vs 3622），因为单轮规划导致子任务间冗余计算

亮点与洞察¶

数据整理 pipeline 设计精巧：不是人工定义并行结构，而是从真实推理轨迹中用 LLM 自动提取依赖图——这意味着训练数据保留了原始推理的自然分布，只是重新组织了执行顺序
只需 1700 条 SFT 数据：极少量的结构化数据就能解锁模型的并行推理能力，说明推理模型本身就具备并行推理的潜力，只需要被"提醒"怎么做
准确率不降反升：Sprint 92.5% vs RFT 91.0%，并行执行带来了类似 ensemble 的效果——独立的子执行不会互相污染
交替规划的设计：每轮规划都能看到上一轮所有执行结果，形成"规划-执行-同步-再规划"的闭环，避免了 SoT 那样一次性规划导致的子任务不协调问题

局限性 / 可改进方向¶

未验证实际 wall-clock 加速：论文只报告了顺序 token 数减少，但实际推理加速需要专门的 KV-cache 优化和 GPU 并行执行框架，作者承认受限于计算资源未能实现
训练数据构造依赖 GPT-4o：step extraction 和 DAG creation 都需要调用封闭模型，成本和可复现性有一定限制
LoRA 微调失败：只有全量 SFT 才能让模型遵循格式，限制了大模型上的应用
并行度有上限：受限于 SFT 数据中观察到的并行模式，RL 训练（用延迟作为奖励信号）可能发现更激进的并行策略
未扩展到工具调用场景：推理 + 工具调用的场景中，工具调用的延迟远大于 token 生成，并行化收益可能更大

评分¶

新颖性: ⭐⭐⭐⭐ 交替规划-并行执行的框架设计新颖，数据整理 pipeline 的 DAG 方法有创意，但并行推理这个方向同期有 PASTA、APR 等相似工作
实验充分度: ⭐⭐⭐⭐ 三个基准（含 2 个 OOD）+ 多种 baseline + 按难度分析效率，但缺少实际 wall-clock 时间和更大模型的验证
写作质量: ⭐⭐⭐⭐⭐ 论文结构清晰，图表设计精美，示例充分展示了方法的工作方式
价值: ⭐⭐⭐⭐ 为推理模型加速提供了一个优雅的思路，1700 条数据就能解锁能力很有实践价值，但实际部署还需硬件端配合