# Stochastic Autoregressive Learning

arXiv: https://arxiv.org/abs/2608.07224 · HTML: https://mlsanity.com/paper/2608.07224/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 54 references that are in the map.
- First posted on arXiv 7 Aug 2026.

## Builds on (most cited first, 10 of 10)

- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End](https://mlsanity.com/paper/2604.12013/) (2026)
- [Learning to Think from Multiple Thinkers](https://mlsanity.com/paper/2604.24737/) (2026)
- [A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning](https://mlsanity.com/paper/2605.06819/) (2026)
- [The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought](https://mlsanity.com/paper/2607.07423/) (2026)
- [Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds](https://mlsanity.com/paper/2605.12316/) (2026)

## Built on by (most cited first, 1 of 1)

- [The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought](https://mlsanity.com/paper/2610.17283/) (2026)

## Abstract (arXiv)

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 mbase(varepsilon),mCoT(varepsilon), me2e(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 mCoT/mbase and me2e/mCoT 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/M2, whereas e2e learning at scale varepsilon is upper-bounded, up to logarithmic factors, by (M/varepsilon) mCoT(Theta(varepsilon)). These dependencies and scales are essentially tight. We complement these bounds by studying dimension d logistic functions in our model.