Bagging 算法实现与 CoT 长度无关的最优样本复杂度学习
Optimal Autoregressive Chain-of-Thought Learning via Bagging
一篇理论论文,教你怎么用 bagging 从 CoT 数据学出生成器,样本复杂度不随推理步数变长而膨胀。做推理模型训练、数据蒸馏的同学值得看看证明思路,工程上集成加蒸馏的组合也能直接借鉴。
arXiv 论文(编号 2611.21597)研究如何从思维链(CoT)示范中学习自回归下一词元生成器 f:Σ*→Σ。作者提出一种基于 bagging 的简单算法:对训练数据做 bootstrap 采样,训练多个 CoT 一致的生成器,再以多数投票方式输出结果。
理论结果方面,对二元词元集,该算法达到最优样本复杂度 O((d_VC+log(1/δ))/ε),且与 CoT 长度 T 无关,其中 d_VC 是假设类的 VC 维。对有限词元集 Σ,VC 维被多分类情形的 Graph 维 d_G 取代,样本复杂度在最优值之上的附加因子仅为 log|Σ|。投票集成中生成器数量为 O(log(T/δ)),论文还证明可额外消耗 n·log(nT) 条无标注提示词,将集成蒸馏回单个生成器。
这项工作的意义在于首次在 CoT 示范学习场景下给出了与推理步数 T 解耦的最优样本复杂度保证,直接回应了此前长 CoT 数据需求随 T 增长的担忧,对从事推理模型训练与蒸馏的研究者有直接参考价值。
Optimal Autoregressive Chain-of-Thought Learning via Bagging
We study how to learn an autoregressive next-token generator $f\colonΣ^\star\toΣ$ from a class $\mathcal{F}$, given chain-of-thought (CoT) demonstrations of length $T$ generated by $f$. We present a simple algorithm based on bagging, which outputs a majority vote of generators that are trained to be CoT-consistent on bootstrap samples of the training data. For binary token sets, it achieves the optimal sample complexity of $O((d_{\mathrm{VC}}+\log(1/δ))/ε)$, independent of the CoT length $T$, where $d_{\mathrm{VC}}$ is the VC dimension of $\mathcal{F}$. For finite token sets $Σ$, the VC dimension is replaced by a multiclass analogue, the Graph dimension $d_{\mathrm{G}}$, and the sample complexity is optimal up to a $\log|Σ|$ factor. The number of generators in the majority-vote ensemble is $O(\log(T/δ))$, and we show that the ensemble can be distilled into a single generator in $\mathcal{F}$ at the expense of $n\log(nT)$ unlabeled prompts.
本条情报归属 AITOP「论文」核心追踪栏目。在跨区域产业观察坐标中,该动态直接关联「AI 开发者工具链、Coding Agent 与工程化实践」研究主线,反映出当前技术演进与商业落地的最新风向。涉及核心实体与技术议题包括:chain-of-thought、样本复杂度、bagging、推理模型,读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。
信源核验说明:本文原始线索采编自「arXiv cs.LG」(@Awni Altabaa, John Lafferty, Omar Montasser),经 AITOP 多维评分管线结构化提炼。