# Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 12 May 2026.

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

- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [The Learnability of In-Context Learning](https://mlsanity.com/paper/2303.07895/) (2023)
- [What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization](https://mlsanity.com/paper/2305.19420/) (2023)
- [A Latent Space Theory for Emergent Abilities in Large Language Models](https://mlsanity.com/paper/2304.09960/) (2023)
- [Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification](https://mlsanity.com/paper/2502.12465/) (2025)
- [Online Estimation via Offline Estimation: An Information-Theoretic Framework](https://mlsanity.com/paper/2404.10122/) (2024)
- [Explicitly Encoding Structural Symmetry is Key to Length Generalization in Arithmetic Tasks](https://mlsanity.com/paper/2406.01895/) (2024)
- [Research Program: Theory of Learning in Dynamical Systems](https://mlsanity.com/paper/2512.19410/) (2025)

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

- [Stochastic Autoregressive Learning](https://mlsanity.com/paper/2608.07224/) (2026)

## Abstract (arXiv)

We study the fundamental and timely problem of learning long sequences in autoregressive modeling and next-token prediction under model misspecification, measured by the joint Kullback--Leibler (KL) divergence. Our goal is to characterize how the sequence horizon (H) affects both approximation and estimation errors in this joint-distribution, sequence-level regime. By establishing matching upper and lower bounds, we provide, to our knowledge, the first complete characterization of long-horizon error behavior under the natural joint KL objective, with improved rates and optimality justification relative to existing work. On the approximation side, we show that joint KL admits a horizon-free approximation factor, in sharp contrast to Hellinger-based analyses that exhibit an (Omega(H)) dependence for computationally efficient methods; this isolates the choice of divergence as the source of approximation amplification. On the estimation side, we prove a fundamental information-theoretic lower bound of order (Omega(H)) that holds for both decomposable policy classes and fully shared policies, matching the (widetilde O(H)) upper bounds achieved by computationally efficient algorithms. Our analysis clarifies the landscape of recent autoregressive learning results by aligning the log-loss training objective, the sequence-level evaluation metric, and the approximation metric colorblackthrough a sharp joint-KL oracle theory. We further show that these joint-KL guarantees imply policy learning regret bounds at rates matching prior imitation learning literature.