[LG]《Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End》S Hanneke, I Mehalel, S Moran [Purdue University & The Hebrew University & Technion and Google Research] (2026)

在自回归推理领域，如何用尽可能少的样本学会「思考」，是一个悬而未决的难题。过去的方法受困于中间步骤的监督信号缺失——模型只见最终答案，不见推理过程，导致样本复杂度随生成长度T线性攀升，本质原因是缺失的中间状态迫使学习算法用更多数据来「反推」推理路径。

本文的核心洞见是：把「观察完整推理链」重新看作一种将单个复杂样本膨胀为T个基础样本的信息放大机制。由此，基于样本压缩方案的学习算法得以将链式样本折叠回基类空间，使问题得以解开——对有限VC维的基类而言，样本复杂度与生成长度T彻底无关；而在端到端模式下，几乎所有介于常数与线性之间的增长率都可被实现，并且不存在任何维度能统一刻画次线性增长。

这项工作真正留下的遗产是：用严格的PAC学习框架，首次完整划定了「思维链监督」与「端到端监督」在样本效率上的分野。它为后来者打开的新门是：将中间推理步骤的价值从经验直觉提升为可量化的理论保证，为设计高效推理模型提供了理论锚点。但尚未跨过的门槛是：当输出空间无界、或基类本身不可学习时，现有框架失效，如何在更宽松的假设下建立有意义的理论，仍是开放问题。

arxiv.org/abs/2604.12013

机器学习 人工智能 论文 AI创造营