Stochastic Autoregressive Learning
作者: Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
分类: cs.LG
发布日期: 2026-08-07
💡 一句话要点
提出随机自回归学习模型以改进LLM输出生成
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 随机自回归学习 PAC学习 大型语言模型 样本效率 生成模型
📋 核心要点
- 现有的确定性自回归学习方法在处理随机性和样本效率方面存在局限，难以适应复杂的生成任务。
- 论文提出了一种新的PAC学习模型，通过固定生成器为每个提示字符串分配伯努利分布，支持多种监督形式以提高学习效率。
- 研究结果显示，随机自回归学习在样本需求上与确定性学习有显著差异，且不同学习任务间的样本需求关系复杂，提供了新的理论界限。
📝 摘要（中文）
本研究受到大型语言模型（LLMs）启发，提出了一种用于二元随机自回归学习的PAC学习模型，扩展了Joshi等人提出的确定性自回归学习框架。模型中，固定生成器为每个提示字符串分配伯努利下一个标记分布。通过对输入提示进行采样并逐步扩展，研究了不同监督形式下所需的样本数量。结果表明，随机自回归学习与确定性理论存在根本差异，并且在不同学习任务之间没有普遍的比较关系。论文还探讨了维度d的逻辑函数在模型中的表现。
🔬 方法详解
问题定义：本研究旨在解决现有确定性自回归学习在处理随机生成任务时的不足，尤其是在样本效率和学习任务间比较的复杂性上。
核心思路：提出了一种基于固定生成器的随机自回归学习模型，通过对输入提示进行逐步采样，探索不同监督形式对学习效果的影响。
技术框架：模型的整体架构包括一个固定的生成器，该生成器为每个提示字符串分配伯努利分布。学习过程中，输入提示被逐步扩展，生成新的标记，并在不同的监督形式下进行学习。
关键创新：本研究的主要创新在于引入了随机自回归学习的框架，揭示了与确定性学习的根本区别，特别是在样本需求和学习任务之间的复杂关系。
关键设计：研究中考虑了三种监督形式：基础一阶样本、链式思维样本和端到端样本，分析了在平方损失下，学习不同任务所需的最小样本数量。
🖼️ 关键图片
📊 实验亮点
实验结果表明，在不同监督形式下，随机自回归学习的样本需求与确定性学习显著不同。具体而言，链式思维学习的样本需求上限被证明是基础学习的平方缩放，而端到端学习的样本需求则与链式思维学习呈对数关系，这些发现为理解学习任务间的复杂关系提供了新的视角。
🎯 应用场景
该研究的随机自回归学习模型可广泛应用于自然语言处理、对话系统和生成模型等领域，提升模型在复杂生成任务中的表现。未来，模型的理论框架和实用性可能推动更多基于随机过程的学习方法的发展。
📄 摘要（原文）
Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. This generalizes the deterministic autoregressive learning framework of Joshi et al., COLT 2025. In our model, one fixed generator assigns a Bernoulli next-token distribution to every prompt string. Starting from an input prompt, a token is sampled and appended to the prompt; the same generator is then applied again to this expanded prompt; this procedure is repeated for $M$ steps. Three forms of supervision are considered: base one-step samples, chain-of-thought (CoT) samples that reveal full random trajectories of length $M$, and end-to-end (e2e) samples that reveal only the final token of length $M$ trajectories. For a generator class, we study the minimum number of samples $m_{base}(\varepsilon),m_{CoT}(\varepsilon), m_{e2e}(\varepsilon)$, resp., required to learn the one-step probabilities in the base model, and the final-token probability in the CoT and e2e models, under squared loss error~$\varepsilon$. We show that stochastic autoregressive learning fundamentally differs from the deterministic theory. At scale $\varepsilon$, there is no universal comparison between the three learning tasks: both $m_{CoT}/m_{base}$ and $m_{e2e}/m_{CoT}$ can be made simultaneously arbitrarily larger than $M/\varepsilon$, the natural analogue for the existing deterministic results. Nevertheless, after altering scales, for every class, CoT learning at scale $\varepsilon$ is upper-bounded by base learning at scale $\varepsilon/M^2$, whereas e2e learning at scale $\varepsilon$ is upper-bounded, up to logarithmic factors, by $(M/\varepsilon) m_{CoT}(Θ(\varepsilon))$. These dependencies and scales are essentially tight. We complement these bounds by studying dimension $d$ logistic functions in our model.