CoT 推理的分布外泛化机制研究：风险上界与实验验证
Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs
一篇解释 CoT 为什么能泛化到没见过的长推理任务的理论论文，还配了 GSM8K 实验和开源代码，做模型研究的可以看看推导。
一篇 arXiv 论文将 Chain-of-Thought（CoT）视为组合式分布外（OOD）泛化问题：训练只提供分布内原子步骤数据，目标任务的推理步数为 T。论文证明 OOD 任务风险由分布内子任务风险之和乘以与 T 无关的 O(k) 系数控制，Rademacher 复杂度分析显示估计项为 O(√(T/n)) 而非随 T 线性增长。在 GSM8K 和 Atom-Task 上的实验支持该理论：CoT 能实现短到长和组合泛化，显式状态跟踪是关键。代码已在 GitHub 开源。
Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs
Chain-of-Thought (CoT) reasoning substantially improves Large Language Models (LLMs), yet its out-of-distribution (OOD) generalization mechanism remains theoretically underexplored. We study CoT as compositional OOD generalization: the target task lacks complete reasoning trajectories or direct input-output pairs, while training provides only in-distribution (ID) atomic step data. We show that CoT generalizes by repeatedly applying a shared single-step predictor to compose reusable ID transitions. Theoretically, let $T$ denote the number of reasoning steps in the target task, $n$ the number of training samples per sub-task, and $k$ the number of output tokens per step; then the OOD task risk is controlled by the sum of the ID sub-task risks, scaled by a coefficient of order $\mathcal{O}(k)$ that is independent of $T$, although the summed risk itself may still grow with $T$. A Rademacher-complexity analysis further shows that the estimation term is of order $\mathcal{O}(\sqrt{T/n})$, rather than linear in $T$, due to predictor sharing under a uniform capacity control on the shared class. For autoregressive Next-Token Prediction, the final-task risk is bounded by the best-in-class step-level risk scaled by the same coefficient of order $\mathcal{O}(k)$, plus an estimation term of order $\widetilde{\mathcal{O}}\big(k\sqrt{T/n}\big)$. A parity-coupled construction further shows that, for the sub-task empirical risk minimizer, the expected final-task risk is at least the best in-class risk plus $Ω(\sqrt{T/n})$ when $T\le n$. Experiments on Atom-Task and GSM8K support the theory: CoT enables short-to-long and compositional generalization, while explicit state tracking is crucial. Our code is available at https://github.com/maxliang114514/CoT-OOD.
