用自回归思维链实现高效学习，无需显式观察思考过程。
A Theory of Learning with Autoregressive Chain of Thought
- 通过固定生成器多步迭代形成思维链，以最终输出为答案。
- 时间不变性使样本复杂度与思维链长度无关，提升效率。
- 适用于希望理解推理机制的AI研究者，尤其关注可解释性模型。
针对一类序列到下一个词的生成器，本文研究通过重复使用固定且时间不变的生成器进行多步迭代，生成思维链，并将最终输出作为答案的提示-答案映射学习问题。我们分别在思维链可观测和仅使用提示-答案对（思维链隐含）两种情况下形式化了学习问题。分析了基于生成器类一般性质（如VC维）及具体类如线性阈值模型的样本复杂度和计算复杂度。提出一个简单基类，具备普遍表达能力且支持计算上可处理的思维链学习。核心发现是时间不变性使得样本复杂度与思维链长度无关。注意力机制自然出现在构造中。
原文摘要 · Abstract (English)
For a given base class of sequence-to-next-token generators, we consider learning prompt-to-answer mappings obtained by iterating a fixed, time-invariant generator for multiple steps, thus generating a chain-of-thought, and then taking the final token as the answer. We formalize the learning problems both when the chain-of-thought is observed and when training only on prompt-answer pairs, with the chain-of-thought latent. We analyze the sample and computational complexity both in terms of general properties of the base class (e.g. its VC dimension) and for specific base classes such as linear thresholds. We present a simple base class that allows for universal representability and computationally tractable chain-of-thought learning. Central to our development is that time invariance allows for sample complexity that is independent of the length of the chain-of-thought. Attention arises naturally in our construction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。