The Serial Scaling Hypothesis¶
会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=ObXB7KJn0B
项目页: serial-scaling-hypothesis.github.io
代码: 无（理论/立场论文，仅含新定理与证明）
领域: 学习理论 / 计算复杂度
关键词: 串行计算, 并行计算, 复杂度理论, 扩散模型, 强化学习, Scaling
一句话总结¶
这是一篇立场+理论论文：作者用计算复杂度（TC 电路类）把机器学习问题切成"能高效并行的"与"本质串行的"两类，论证推理、决策、物理模拟等关键任务属于后者，并首次证明扩散模型即便采样上千步、其计算深度仍是常数，从而无法解决本质串行问题——因此只堆并行算力（更宽的网络、更多 GPU）注定到顶，进步必须靠扩展串行计算。
研究背景与动机¶
领域现状：过去十年机器学习的进步几乎全靠"并行 scaling"——硬件从 CPU 转向大规模并行的 GPU，架构从 RNN 转向高度可并行的 Transformer，算法越来越多地榨取并行算力。主流的 scaling law 文献也习惯把参数量、FLOPs 各报成一个单一数字，把网络"宽度"（并行）和"深度"（串行计算）当成可互换的东西混在一起谈。
现有痛点：可有一类问题就是顽固地不吃这一套——数学推理、物理模拟、序贯决策，无论怎么加并行算力都卡在原地，只有让模型多走"串行步数"（更深、更多迭代、更长的思维链）才有进展。但这种"某些问题需要深/序贯模型"的认知一直停留在零散的理论结果里，没有被系统地搬进机器学习的语境，也没有人把"并行 vs 串行"这条轴单独拎出来当成第一性的区分。
核心矛盾：宽度和深度并不等价。复杂度理论里有个经典现象：你可以用指数级变宽来换取网络变浅，但指数级宽度在内存和计算上都不可行。也就是说，对某些问题，浅而宽的并行模型要解它就得用指数大的权重、从而需要指数大的数据集来训——实践中根本负担不起。把宽度和深度当成可互换的单一 FLOPs 数字，正好掩盖了这个根本鸿沟。
本文目标：把"哪些问题能高效并行、哪些本质串行"这件事在复杂度理论里讲严格，并据此回答两个子问题——(1) 机器学习里真正重要的问题有多少落在"本质串行"那一侧？(2) 当今主流的并行架构（Transformer、SSM、扩散模型）到底能不能解这些问题？
切入角度：作者借用阈值电路复杂度类 TC（Threshold Circuits）作为标尺。一个问题属于 TC 当且仅当它能被多项式宽度、polylog 深度的电路（或等价的 MLP）解出——这类问题视为"并行问题"；落在 TC 之外的就是"本质串行"。这个角度有希望，是因为 TC 与神经网络有天然对应：固定深度、多项式宽度、有限精度的 MLP / Transformer / 线性 SSM 全都坍缩进 TC⁰（常数深度）。
核心 idea：提出串行 scaling 假设（Serial Scaling Hypothesis, SSH）——对于推理、决策、动态系统建模这类重要 ML 问题，只增加并行计算是不够的，进步必须扩展串行计算的量。
方法详解¶
这是一篇理论/立场论文，没有"训练某个新模型"，所谓"方法"是一套复杂度论证框架：先用 TC 类把串行/并行的边界定义清楚，再逐类证明（或论证）关键 ML 问题落在串行一侧，最后给出本文最硬的新定理——扩散模型的串行能力受限。
整体框架¶
整篇论文要解决的核心命题是："为什么只堆并行算力会到顶，进步必须靠串行计算？"它的论证分三段递进。
第一段是搭标尺：把问题统一抽象成"输入 N 个 token、输出 yes/no"的二元判定问题（任何离散响应都能拆成若干个 yes/no），然后用电路复杂度类 \(TC\) 把问题分成两堆。\(TC^i\) 指能用多项式宽度、\(O(\text{poly}(\log N))\) 深度的布尔电路（AND/OR/NOT + 多数门）解出的问题；它们层层嵌套 \(TC^0 \subseteq TC^1 \subseteq \cdots \subseteq TC \subseteq P\)，且每个包含关系普遍相信是严格的。定义上，问题 \(P\in TC\) 即为"并行问题"，否则为"本质串行问题"；本文采纳 \(TC \subsetneq P\) 这个广为接受的假设，即存在多项式时间可解、却本质串行的问题。
第二段是指认现实：论证机器学习里真正重要的一大批问题都落在 \(TC\) 之外（本质串行），包括元胞自动机演化、多体力学/视频预测、序贯决策（RL）、数学推理 QA。它们的共性是有一条长度随问题规模线性增长的"计算图"，每一步只依赖前一步、却没法跳步——这正是 P-complete 问题（如电路求值问题 CVP）的本质。
第三段是揭穿模型：固定深度的 MLP、Transformer、SSM 作为架构都坍缩进 \(TC^0\)，只有配上串行的推理过程（自回归 CoT、循环、重复层）才能突破 \(TC^0\)。而本文最硬的一击是证明扩散模型即使无限采样步、其计算仍停在 \(TC^0\)——它看着串行，其实只提供常数量的额外串行计算。三段合起来推出结论：用浅/并行模型去解本质串行问题，要么解不了，要么需要指数级的权重和数据。
关键设计¶
1. TC 复杂度标尺：把"串行 vs 并行"定义成 TC 内外
论文要解决的第一个痛点是——大家一直把"宽度"和"深度"混作单一的 FLOPs 数字，于是"某些问题需要更深的模型"始终是一句模糊的经验之谈，没法证明也没法证伪。作者的办法是引入阈值电路类 \(TC\) 作为严格标尺：一个判定问题属于 \(TC^i\)，当且仅当它能被多项式宽度、\(O(\text{poly}(\log N))\) 深度的电路解出；并行性就等价于"存在亚线性深度的电路/MLP 能解它"。据此给出干净的二分——\(P \in TC\) 叫并行问题，\(P \notin TC\) 叫本质串行问题（Def. 2.2），并采纳 \(TC \subsetneq P\)（Assumption 2.3）这个复杂度理论里公认的信念。
这个标尺之所以有效，关键在它跟神经网络深度有一一对应：一个问题属于 \(TC\) 当且仅当它能被多项式宽度、polylog 深度的 MLP 解出，属于 \(TC^0\) 当且仅当能被常数深度 MLP 解出。于是"网络该多深"这种工程问题被翻译成了"问题落在 \(TC\) 的哪一层"这种可证命题，也让后面"指数级变宽换变浅不可行"的论证（深度-宽度权衡）有了严格落点——你能把网络压浅，代价是指数级变宽，而指数宽度在内存和算力上都不可行，所以深度必须被单独刻画。
2. 本质串行问题的目录：用 P-complete 把现实任务对号入座
光有定义还不够，得回答"现实里到底有没有这种问题"。作者给出一份本质串行问题的清单，并用统一的判据把它们串起来：如果一个规模 \(O(n)\) 的问题能立刻写出一条长度 \(O(n)\) 的线性计算图、每个节点只依赖前面的节点、每步常数时间，那它很可能本质串行——这正是 P-complete 问题（原型是电路求值问题 CVP）的直觉。清单里：元胞自动机（Rule 110 图灵完备、且许多 CA 问题 P-complete，算第 \(N\) 行某格的状态必须逐步模拟）；多体力学（Fredkin-Toffoli 的"台球计算机"能用弹性碰撞模拟任意图灵机，故有限精度下预测 \(t=T\) 的粒子位置本质串行，视频预测同理）；序贯决策与数学 QA（GSM8K 可形式化成依赖图、按拓扑序逐步算术，对应 P-complete 的算术电路求值）。
这一设计的价值在于把抽象的复杂度结论翻译成了从业者认得的任务，并附上一条可操作的"嗅探规则"：看到任务有一条像 CVP 那样的线性依赖图，就该警觉它本质串行。作者也诚实地圈出两条边界——这些是最坏情况复杂度，实践中遇到的具体实例可能恰好可并行或可近似并行解；而且这套论证只对 \(P\) 内的问题最贴切，对 \(NP \setminus P\) 那种问题，主导难度的是指数计算而非串行计算。
3. 扩散模型的串行能力上限：TC⁰ 骨干无限步仍是 TC⁰
这是全文最关键、也最反直觉的新定理。扩散模型一步步去噪、看着特别"串行"，很多人默认它能提供可扩展的串行计算。但作者证明：如果一个问题能被采用 \(TC^0\) 骨干的扩散模型在无限去噪步下高概率解出，那这个问题本身就在并行类 \(TC^0\) 里（Theorem 4.1，正式版在附录 F）。证明搭在已有结论之上——反向扩散过程以 \(TV = O(d/T)\) 的速率收敛到目标分布 \(p_0\)（\(TV\) 是总变差、\(d\) 是 \(x_{N+1}\) 的本征维度、\(T\) 是步数），由于骨干网络每步都是常数深度、且收敛只需多项式步即可把误差压到任意小，整个采样过程能被折叠回常数深度电路。
它点破的痛点是："迭代多 ≠ 串行深度大"。扩散模型只贡献常数量的额外串行计算，跟真正逐步累积串行算力的 CoT 有本质区别。这恰好解释了一堆经验现象：图像生成约 300 步就饱和、深度估计 5 步和 100 步差别不大、语言建模 32 步和 1024 步困惑度相近、蒸馏到 1–4 步几乎不掉点——既然有效计算深度本就很低，快速收敛就不奇怪了，也解释了扩散语言模型在输出变长时表现平庸。作者标注了定理的失效条件：解空间本征维度随规模增长、或骨干训练不充分/换了训练目标时不适用，这给"超越 score-based 扩散的、可扩展串行计算的生成模型"留了口子。
4. SSH 的四方启示：把理论结论落到模型/任务/硬件决策
最后一个设计是把上面的理论推论翻译成可执行建议，避免论文停在"有趣但没用"。对从业者：本质串行问题用浅/并行模型解需要指数级权重与数据，这解释了为何很多系统泛化差；RL 微调的证据表明 LLM 预训练里同时学到了浅启发式（快但像记忆）和深层算法（慢但更通用），推理算力预算给太小时模型会退回浅路径、产生又快又脆的行为，只有给足串行计算才能跑深层算法。对任务/benchmark 设计者：可以把串行问题改写成更粗/近似的版本来削减串行深度（如 RL 里用截断价值函数封顶有效深度、仍保留理论保证），并建议 benchmark 把本质串行问题单列一类。对模型设计者：可能需要循环结构来增加串行计算，但循环和深度会放大梯度方差与 Lipschitz 常数、更难训，这推动隐式梯度、xLSTM、test-time training 等新方向。对硬件设计者：未来进步不只靠更并行，还要靠高主频、低延迟、低数据搬运开销的串行计算硬件（如 Cerebras CS-3 这类晶圆级、超高片上带宽的设计）。
实验关键数据¶
本文不训练新模型，没有自建实验；"证据"来自对已有工作图表的复用与新定理。下面整理它引用的三组关键经验证据，用来佐证 SSH。
主要经验证据¶
| 领域 | 对比 | 关键发现 | 数据来源 |
|---|---|---|---|
| 数学推理 QA | 串行 scaling（更长思维链）vs 并行 scaling（majority voting） | 同 token 预算下，更长推理链一致优于多数投票，且在 AMC/MATH/AIME/Olympiad 各难度都成立 | Aggarwal & Welleck, 2025 |
| 科学 QA | 串行 vs 并行 | GPQA Diamond 上串行 scaling 持续提升准确率（仅受上下文窗口限制），并行投票则很快饱和 | Muennighoff et al., 2025 |
| 棋类（Hex） | 增加 MCTS 扩展节点数 | 所有训练规模下性能随 MCTS 扩展节点单调上升，完美对弈只有靠 test-time MCTS 才达到 | Villalobos & Atkinson, 2023 |
深度 vs 宽度对照¶
| 任务 | 配置 | 结果 | 说明 |
|---|---|---|---|
| Humanoid（运动控制） | 深 8 层 / 宽 256 vs 浅 4 层 / 宽 4096 | 2× 更深的网络胜过 16× 更宽的网络 | 观测与动作空间最大的任务上，串行深度比并行宽度更值钱 |
| Ant Big Maze / Arm Push | 不同宽度 + 深 8 / 深 32 | 加深网络在 locomotion/manipulation 上一致优于单纯加宽 | 即便是 model-free RL，串行计算也不可被并行替代 |
关键发现¶
- 三个独立领域（数学、科学、棋类、RL 控制）给出方向一致的证据：固定预算下，把算力花在"串行"（更长链、更多 MCTS 扩展、更深网络）比花在"并行"（投票、更宽网络）更有效——这正是 SSH 的经验落点。
- 扩散步数的"早饱和"现象被理论解释：图像 300 步饱和、深度估计 5 vs 100 步无差、语言建模 32 vs 1024 步困惑度相近，统一归因为扩散有效计算深度是常数。
- 并行算力无法替代串行算力：在 RL 里，并行聚合多条轨迹只能降方差/加速收敛，无偏的回报估计仍需串行计算，否则最优策略没有保证。
亮点与洞察¶
- 把"宽度 vs 深度"从工程口味之争抬升成可证命题：用 \(TC\) 内/外这一刀，给"某些问题非深不可"提供了严格判据，并配了一条从业者能用的嗅探规则（看到 CVP 式线性依赖图就警觉串行）。这套话术可迁移到任何"该加宽还是加深"的架构决策里。
- 扩散模型那条定理最让人"啊哈"：所有人都觉得逐步去噪 = 串行，作者却证明 \(TC^0\) 骨干无限步仍是 \(TC^0\)，并用一堆"早饱和"经验现象反向印证——这是把"迭代次数"和"串行深度"彻底解耦的漂亮一击。
- CoT 与扩散的对照极具启发：同样是"多步"，CoT 真正累积串行算力（突破 \(TC^0\)），扩散只加常数深度。这提示我们评估任何"测试时 scaling"方法时，要先问它加的是真串行深度还是只是常数迭代。
- 给生成模型留了门：定理失效条件（解空间本征维度随规模增长、或换训练目标）明确指向"可扩展串行计算的生成模型"这一开放方向，对想做下一代 world model / 视频生成的人是直接的设计线索。
局限与展望¶
- 最坏情况复杂度的固有局限（作者承认）：所有"本质串行"结论都是 worst-case，现实遇到的具体实例可能恰好可并行、或可近似并行解到够用的精度——SSH 给的是"原则上的天花板"，不是"每个实例都难"。
- 适用范围限定在 P 内（作者承认）：对 \(NP \setminus P\) 这类问题，主导难度的是指数计算而非串行计算，SSH 最贴切的是"现实难度"的多项式时间问题。
- 扩散定理依赖较强前提：\(TC^0\) 骨干、固定本征维度、训练充分且用 score matching 目标——一旦解空间维度随规模增长或换了目标，定理就不适用，所以"扩散无法串行"不能无脑外推到所有迭代式生成模型。
- 缺少作者自己的受控实验：全部经验证据都是转引他人图表，跨任务/跨设置直接比较时要小心（不同 benchmark 难度、不同算力预算口径不完全可比）；若能有一套统一控制 token/算力预算、横扫"串行 vs 并行"的自建实验会更有说服力。
- 改进思路：把"嗅探规则"做成可自动化的工具（给定任务自动估计其串行深度下界），并探索循环/隐式深度架构在训练稳定性上的具体解法，让"该加串行"从诊断走向可落地的模型设计。
相关工作与启发¶
- vs Merrill & Sabharwal 的"parallelism tradeoff"假设：他们论证所有可并行模型必然解不了本质串行问题；本文与之同源但更进一步，把结论从架构层扩展到真实任务（序贯决策、QA），并补上扩散模型这块此前没人碰过的拼图。
- vs 经典复杂度理论（深度-宽度权衡、work vs depth、P-completeness、计算不可约性）：这些思想在复杂度圈早已成熟，本文的贡献不在于发明新理论，而在于把它们搬进机器学习语境——指认出 ML 里哪些热门任务正好踩中这些坚硬的串行边界。
- vs Chain-of-Thought 的理论分析（Li et al.; Merrill & Sabharwal; Feng et al.）：已有工作证明 CoT 扩展了 Transformer 的串行能力；本文把同一把尺子用到扩散模型上，得出相反结论（扩散不加真串行），形成"CoT 加 / 扩散不加"的鲜明对照。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次把扩散模型纳入 TC⁰ 框架并证明其串行能力受限，"串行 scaling 假设"是一个干净有力的统一视角。
- 实验充分度: ⭐⭐⭐ 立场+理论论文，无自建实验，证据全靠转引他人图表，跨设置比较需谨慎。
- 写作质量: ⭐⭐⭐⭐⭐ 把硬核复杂度理论讲得对非理论读者友好，元胞自动机/数独的类比和"这意味着什么"小节都很到位。
- 价值: ⭐⭐⭐⭐⭐ 对模型、任务、硬件三方都给出可执行启示，可能影响下一代架构与算力投资的方向判断。