自回归推理的样本复杂性：思想链与端到端

现代 大语言模型 自回归生成文本，一次生成一个标记。为了研究此类系统的可学习性，Joshi 等人。 (COLT 2025) 引入了用于下一个词元生成器的 PAC 学习框架，即原始的底层自回归模型。在此框架中，未知的下一个词元生成器将词元序列映射到下一个词元，并迭代应用于 $T$ 步骤，生成词元链，其最终词元构成模型的输出。学习任务是学习由这个自回归过程引起的输入-输出映射。根据可用的监督，训练示例可能仅揭示最终输出（端到端监督）或整个生成链（思想链监督）。这就提出了两个自然问题：样本复杂性如何取决于生成长度 $T$，以及思想链监督可以在多大程度上减少这种依赖性。在这项工作中，我们通过揭示样本复杂性如何随 $T$ 变化的分类法，对这两个问题给出了近乎完整的答案。对于端到端学习，我们表明景观非常丰富：在温和的条件下，基本上恒定和线性之间的任何增长率 $r(T)$ 都可以随着样本复杂性而出现，并与 Joshi 等人的线性上限相结合，这产生了基本上完整的表征。相反，在思想链监督下，我们表明样本复杂性与 $T$ 无关，这表明访问中间推理步骤可以完全消除对生成长度的依赖。我们的分析引入了新的组合工具，作为推论，我们解决了 Joshi 等人提出的几个悬而未决的问题。关于可学习性对生成长度的依赖以及思想链监督的作用。