揭示自回归思维链学习的最优样本复杂度，关键突破是不依赖推理长度。
The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
- 提出奇偶维数控制自回归生成的样本复杂度
- 样本量仅与局部词汇表维度和置信度相关，与推理步数无关
- 对大模型推理分析有理论指导意义，适合算法研究者
在可实现PAC设定下，我们证明了完整自回归思维链精确追踪学习的样本复杂度上界为局部下一个词分类的标准多类率，该率由Daniely-Shalev-Shwartz维数（DSdim）决定。在精确追踪损失下，任一错误动作将导致整个推理路径失效；然而，对于任意停止规则halt和逐点halt-停止的局部类H，其样本复杂度n_{PAC}^{ε,δ}(Roll_{halt}(H))=O((DSdim(H)+log(1/δ))/ε)，且不依赖滚动长度。该对数项的依赖是理论上最优的，因为一步停止即退化为普通多类学习。论文引入奇偶维数（parity dimension），一种基于偶伪立方的、对滚动稳定的DS维数改进版本，通过有限限制上的低坐标覆盖定理控制一包含密度，且不会随自回归滚动增加。我们还证明这一改进必要：传统DS维数会因滚动而上升。
原文摘要 · Abstract (English)
We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule $\mathtt{halt}$ and every pointwise $\mathtt{halt}$-halting local class $\mathrm{H}$, $n_{\mathrm{PAC}}^{\varepsilon,δ}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/δ))/\varepsilon)$, with no dependence on rollout length. The dependence on $\operatorname{DSdim}(\mathrm{H})$ is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of $\mathrm{H}$. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。