Stochastic Autoregressive Learning

arXiv:2608.07224v1 Announce Type: new Abstract: 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}(arepsilon),m_{CoT}(arepsilon), m_{e2e}(arepsilon), 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~arepsilon. We show that stochastic autoregressive learning fundamentally differs from the deterministic theory. At scale arepsilon, 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/arepsilon, the natural analogue for the existing deterministic results. Nevertheless, after altering scales, for every class, CoT learning at scale arepsilon is upper-bounded by base learning at scale arepsilon/M^2, whereas e2e learning at scale arepsilon is upper-bounded, up to logarithmic factors, by (M/arepsilon) m_{CoT}(Theta(arepsilon)). These dependencies and scales are essentially tight. We complement these bounds by studying dimension d logistic functions in our model.

Source: arXiv cs.LG | 2026-08-10