Stochastic Autoregressive Learning

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.