CoT推理为何能泛化？理论首次给出OOD保证

当思维链走出训练分布：一个被忽视的理论缺口

思维链（Chain-of-Thought, CoT）早已是大模型提升复杂推理能力的标配手段，但一个根本问题始终缺少严格答案：模型在训练时只见过单步推理的原子数据，为什么能在测试时完成需要多步串联、且分布完全不同的任务？

最近一篇论文把这个问题形式化为组合式分布外泛化（compositional OOD generalization）。设定很清晰：目标任务的完整推理轨迹和直接输入输出对都不可见，训练只提供分布内（ID）的单步原子数据。论文从理论上解释了CoT泛化的机制，并给出了风险上界，代码已在GitHub开源（CoT-OOD）。

组合式分布外泛化（compositional OOD generalization）指模型在测试时面对的任务由训练时见过的子任务以新的方式组合而成，且整体分布与训练分布不同。与常见的协变量偏移不同，这里的挑战不在于输入外观变化，而在于推理结构需要多步串联。典型例子是训练只见过“加一步”“乘一步”等单步原子操作，测试却要求完成多步混合运算。该设定要求模型具备可组合性：把分布内学到的转移函数复用并拼接，而非记忆完整轨迹。

核心机制：共享单步预测器的反复组合

论文的核心观点是：CoT之所以能泛化，靠的是反复调用同一个共享的单步预测器，把可复用的ID转移拼接起来。换句话说，模型并不需要为每个多步任务单独学习映射，它学的是一个通用的"走一步"能力，然后在推理时把这一步重复T次。

这种"共享"是关键。它意味着容量控制只作用在同一个函数类上，而不是随任务长度线性膨胀。后面的泛化分析全部建立在这个结构性假设之上，也是整篇论文最有洞见的地方：CoT的能力来源不是更大的模型，而是更合理的组合方式。

单步预测器指在给定当前状态（或中间推理结果）时，预测下一步转移的函数。在CoT中，它对应“根据已有推理前缀生成下一个推理步骤”的能力。共享意味着所有多步任务复用同一个函数类，而不是为每个任务长度或类型单独参数化。这种参数共享使假设空间容量不随推理步数T增长，从而让泛化分析可以统一处理不同长度的任务，也是理解后续风险上界与下界的关键前提。

风险上界：系数与步数解耦

理论结果给出了一组明确的界。设T为目标任务的推理步数，n为每个子任务的训练样本数，k为每步输出token数，则OOD任务风险由ID子任务风险之和控制，缩放系数为O(k)量级，且与T无关。

这个结论的含义值得细读：虽然子任务风险求和本身可能随T增长，但组合带来的额外惩罚并不随推理链变长而恶化。也就是说，长链推理并不会因为"链更长"而天然更难泛化，困难来自单步风险而非组合结构。

进一步用Rademacher复杂度分析，估计项的阶为O(√(T/n))，而非线性于T。这正是预测器共享在统一容量控制下带来的收益，没有共享，估计误差会随链长线性放大。

Rademacher复杂度是衡量函数类拟合随机噪声能力的工具，常用于给出泛化误差上界。对于由T步组合而成的假设类，朴素分析会得到随T线性增长的复杂度；但若每步共享同一个容量受控的预测器，组合类的复杂度可被控制为与T呈次线性关系（如√T）。这解释了论文中估计项O(√(T/n))的来源：共享结构避免了容量随链长膨胀，从而使长链推理的样本效率不至于急剧恶化。

自回归设定与下界：泛化不是免费的

针对自回归的下一词预测（Next-Token Prediction），论文给出最终任务风险由最优单步风险乘以同样的O(k)系数，加上一个Õ(k√(T/n))量级的估计项构成。

另一面，论文用奇偶耦合构造证明了：对子任务经验风险最小化器而言，当T≤n时，期望最终任务风险至少是最优类内风险加上Ω(√(T/n))。这说明上界在量级上是紧的，组合泛化存在不可消除的代价，不会因为方法巧妙就归零。

奇偶耦合构造是理论下界证明中常用的一种归约技巧：构造一对仅在某个奇偶性上不同的子任务，使得任何经验风险最小化器都难以区分它们，从而迫使最终组合任务产生不可避免的误差。通过精心设计子任务分布，可以证明组合泛化的误差下界为Ω(√(T/n))。这一构造说明上界在量级上紧，也揭示组合泛化的代价源于子任务间的统计不可区分性，而非算法缺陷。

实验验证：短到长与组合泛化

论文在Atom-Task和GSM8K上验证了理论。结果支持两个判断：CoT确实能实现短到长泛化和组合泛化；而显式的状态跟踪对能否泛化至关重要。这一发现对工程实践有直接价值：想让CoT稳定工作，模型需要在推理过程中维护并更新中间状态，而非只是把步骤串起来。

从更长远的视角看，这篇工作把CoT从"经验技巧"推进到可分析的对象。它提醒我们，组合泛化的可靠性取决于共享结构的容量控制与状态跟踪机制，这两点比单纯堆叠推理步数更值得投入。