Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones¶

会议: NeurIPS 2025
arXiv: 2505.21825
代码: github.com/seyedparsa/let-me-think
领域: LLM推理
关键词: 推理时缩放, 顺序缩放 vs 并行缩放, 链式思维, 复杂度理论, 图连通性

一句话总结¶

本文从理论和实验两方面证明：存在推理任务（图连通性问题），其中一条长 CoT（顺序缩放）的能力等价于指数多条短 CoT（并行缩放）——即将 CoT 长度减少一点点，就需要指数级增加并行采样数才能达到同等准确率。

研究背景与动机¶

领域现状：推理时计算有两个主要缩放轴——顺序缩放（更长的 CoT）和并行缩放（多条短 CoT + 投票/Best-of-N）。o1、R1 等模型依赖长 CoT，但长 CoT 的计算成本随序列长度二次增长。

现有痛点：目前对两种缩放方式的权衡缺乏理论理解。有人认为多条短 CoT + 多数投票比一条长 CoT 更高效；也有人认为长 CoT 在困难问题上不可替代。没有清晰的理论框架来回答这个问题。

核心矛盾：直觉上，顺序推理（如 DFS 搜索图）需要按步骤积累信息，而并行采样每条都从头开始，无法共享中间计算。但这个直觉缺乏形式化。

本文目标 是否存在推理任务，使得顺序缩放相比并行缩放具有指数级优势？

切入角度：以图连通性问题为研究对象——判断给定图中源节点连接到 \(t_1\) 还是 \(t_2\)。这是多步推理的代理任务，且已知与 Transformer 的表达能力极限密切相关（\(\mathsf{TC}^0\) vs \(\mathsf{L}\)）。

核心 idea：在图连通性任务上，有界深度 Transformer 用 \(O(1)\) 长度 CoT 并行采样多项式次仍只能随机猜，但用一条多项式长度 CoT 就能完美求解——存在指数级的顺序 vs 并行差距。

方法详解¶

整体框架¶

论文分三层递进：(1) 基于 Transformer 表达能力的理论分离（Theorem 1）；(2) 基于 Vertex Query Model（VQM）抽象的更精细分离（Theorem 2 & 3）；(3) 在从头训练的小 Transformer 和前沿大模型上的实验验证。

关键设计¶

基于 \(\mathsf{TC}^0\) 的理论分离（Theorem 1）:
- 功能：证明顺序缩放可以解决图连通性但并行缩放不行
- 核心思路：(a) 多项式长度 CoT 可以模拟 BFS，因此一条 CoT 足以解题（Merrill & Sabharwal 2024b 的推论）；(b) \(O(1)\) 长度 CoT 的 Transformer 等价于 \(\mathsf{TC}^0\) 电路，而 \(\mathsf{TC}^0 \not\supseteq \mathsf{L}\)（标准复杂度假设），因此无法解决连通性问题。关键洞察：对多条独立短 CoT 取多数投票仍是 \(\mathsf{TC}^0\) 电路（因为 MAJORITY 门是 \(\mathsf{TC}^0\) 的一部分），所以并行缩放也无法打破这个限制
- 设计动机：给出最强形式的不可能性结果——即使并行采样多项式次也不行
Vertex Query Model 精细分析（Theorem 2 & 3）:
- 功能：在更精细的计算模型中量化顺序与并行的差距
- 核心思路：VQM 模型中算法只能通过"邻居查询"访问图，每步查询一个顶点的邻居。对于两路径图（Theorem 2）：\(O(L)\) 次查询就够，但 \(<L/2\) 次查询的成功率恰好 1/2。对于桥图（Theorem 3）：即使查询次数超过最短路径长度（\((1-\delta) \cdot \frac{3}{2}ld\) 次），成功概率仍只有 \(1/2 + \exp(-\Omega(d))\)——需要 \(\exp(\Omega(d))\) 次独立运行（并行缩放）才能达到 2/3 成功率
- 设计动机：桥图迫使模型在每个交叉点猜短路径方向，只有 1/2 概率猜对，\(d\) 个交叉点的累积概率指数衰减
RL 中长 CoT 的涌现（Section 5）:
- 功能：用 STaR（Self-Taught Reasoner）训练模型，观察 CoT 长度的自发增长
- 核心思路：在桥图上用短 CoT（Path 策略）训练模型，然后用 RL 迭代（验证正确 CoT → 自训练），发现模型的正确 CoT 逐渐变长，出现了回溯等训练数据中不存在的行为
- 设计动机：呼应 DeepSeek-R1 中观察到的 RL 训练时 CoT 长度增长现象，说明图连通性是研究长 CoT 涌现的有效代理任务

损失函数 / 训练策略¶

小 Transformer（4层 Mistral，128 维隐层）在 50 万 CoT 样本上训练 200 epochs。RL 使用 STaR：每轮采样 50 万条，保留正确的自我训练 20 epochs。

实验关键数据¶

主实验¶

桥图 Bridge(5) 任务：不同 CoT 策略的证据准确率

CoT 策略	CoT 长度	证据准确率	说明
Shortest-Path	~35 tokens	0.0%	太短，无法探索
Path (DFS树路径)	~50 tokens	11.16%	略好但仍不足
DFS (完整搜索)	~90 tokens	~100%	完美解决

DeepSeek-R1-Distill-Qwen-32B 在桥图上的顺序 vs 并行缩放

CoT 长度 (tokens)	并行数 = 1	并行数 = 64	说明
512	~50%	~50%	太短，并行无用
1024	~55%	~60%	开始有效
2048	~75%	~90%	顺序牵引并行
4096	~95%	~99%	顺序足够

消融实验¶

配置	Bridge(3) 证据准确率	说明
Path 模型 (RL前)	21.16%	短 CoT 限制
Path 模型 (RL 4轮后)	92.02%	CoT 自发变长+回溯涌现
DFS 模型	~100%	训练数据含长 CoT

关键发现¶

存在指数级差距：在桥图上，将 CoT 长度从完整 DFS 长度缩减到 Shortest-Path 长度，需要指数级增加并行采样数（从 1 增加到 \(\sim 3^d \cdot 4^{d-1}\)）才能达到同等准确率
并行缩放只有在顺序缩放达到非平凡精度后才有用：在大模型实验中，当 CoT 长度不够时，增加并行数从 1 到 64 几乎没有提升；只有 CoT 长度足够后，并行缩放才开始生效
RL 导致 CoT 长度自发增长：STaR 训练后，模型的正确 CoT 平均长度从 ~15 增长到 ~30，出现了训练数据中没有的回溯行为
在固定总 token 预算下，顺序缩放始终优于并行缩放
趋势在 AIME2024 数学竞赛上也成立：s1-32B 在 AIME 上同样表现出顺序缩放不可替代的特征

亮点与洞察¶

首次证明顺序 vs 并行缩放的指数级分离：这是理论上的重要里程碑。利用 \(\mathsf{TC}^0\) 的表达能力限制来证明并行化多数投票仍是 \(\mathsf{TC}^0\)是真正的核心洞察——这意味着投票机制本身无法突破深度限制
桥图设计精巧：通过在每个交叉点放置短路/长路/死胡同三条路径，迫使模型必须进行真正的序列搜索而非并行猜测。这个构造本身就是一个有用的 benchmark
RL 涌现长 CoT 的解释非常启发人：图连通性任务为 DeepSeek-R1 中观察到的 RL 训练时 CoT 长度增长现象提供了一个简洁的理论解释框架

局限与展望¶

理论结果依赖复杂度假设 \(\mathsf{TC}^0 \not\supseteq \mathsf{L}\)，虽然被广泛相信但未被证明
VQM 作为 Transformer CoT 的抽象仅有启发式支持，缺乏直接理论证明
图连通性是特定的结构化任务，其结论向自然语言推理的迁移程度需要更多研究
实验只在图任务和 AIME 上验证，更广泛的 benchmark 覆盖会更有说服力

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次给出顺序 vs 并行缩放的指数级分离证明，桥图构造巧妙
实验充分度: ⭐⭐⭐⭐ 从头训练小模型 + 前沿大模型验证 + RL涌现实验 + AIME 迁移
写作质量: ⭐⭐⭐⭐⭐ 理论清晰、直觉解释到位、证明结构优雅
价值: ⭐⭐⭐⭐⭐ 对"长思考 vs 多次短思考"这一核心问题给出了理论基础，影响深远