# Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in Language-conditioned policies and VLAs, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 19 of its 85 references that are in the map.
- First posted on arXiv 18 Feb 2025.

## Placed in

- Offline RL and imitation learning from data / [Language-conditioned policies and VLAs](https://mlsanity.com/offlinerl/language-conditioned-policies-and-vlas/)

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

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Diffusion Policy: Visuomotor Policy Learning via Action Diffusion](https://mlsanity.com/paper/2303.04137/) (2023)
- [Learning Fine-Grained Bimanual Manipulation with Low-Cost Hardware](https://mlsanity.com/paper/2304.13705/) (2023)
- [ChauffeurNet: Learning to Drive by Imitating the Best and Synthesizing the Worst](https://mlsanity.com/paper/1812.03079/) (2018)
- [Unifying distillation and privileged information](https://mlsanity.com/paper/1511.03643/) (2015)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Robot Parkour Learning](https://mlsanity.com/paper/2309.05665/) (2023)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Feedback in Imitation Learning: The Three Regimes of Covariate Shift](https://mlsanity.com/paper/2102.02872/) (2021)
- [DextrAH-G: Pixels-to-Action Dexterous Arm-Hand Grasping with Geometric Fabrics](https://mlsanity.com/paper/2407.02274/) (2024)
- [Foundations of Reinforcement Learning and Interactive Decision Making](https://mlsanity.com/paper/2312.16730/) (2023)
- [Lecture Notes: Selected topics on robust statistical learning theory](https://mlsanity.com/paper/1908.10761/) (2019)
- [Online Estimation via Offline Estimation: An Information-Theoretic Framework](https://mlsanity.com/paper/2404.10122/) (2024)
- [Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally](https://mlsanity.com/paper/2102.12948/) (2021)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)

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

- [Dream-VL & Dream-VLA: Open Vision-Language and Vision-Language-Action Models with Diffusion Language Model Backbone](https://mlsanity.com/paper/2512.22615/) (2025)
- [On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference](https://mlsanity.com/paper/2512.04558/) (2025)
- [Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPs](https://mlsanity.com/paper/2505.19946/) (2025)
- [In Good GRACEs: Principled Teacher Selection for Knowledge Distillation](https://mlsanity.com/paper/2511.02833/) (2025)
- [SAMPO:Scale-wise Autoregression with Motion PrOmpt for generative world models](https://mlsanity.com/paper/2509.15536/) (2025)
- [EMA Without the Lag: Bias-Corrected Iterate Averaging Schemes](https://mlsanity.com/paper/2508.00180/) (2025)
- [To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2510.03207/) (2025)
- [When Does Online Imitation Learning Help in LLM Post-Training? The Role of (Non-)Realizability Beyond Horizon](https://mlsanity.com/paper/2606.30445/) (2026)
- [Alternatives To Next Token Prediction In Text Generation -- A Survey](https://mlsanity.com/paper/2509.24435/) (2025)
- [Your Self-Play Algorithm is Secretly an Adversarial Imitator: Understanding LLM Self-Play through the Lens of Imitation Learning](https://mlsanity.com/paper/2602.01357/) (2026)
- [Multi-agent imitation learning with function approximation: Linear Markov games and beyond](https://mlsanity.com/paper/2602.22810/) (2026)
- [Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds](https://mlsanity.com/paper/2605.12316/) (2026)
- [Fast Rates for Inverse Reinforcement Learning](https://mlsanity.com/paper/2605.14599/) (2026)

## Abstract (arXiv)

Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling, but, in practice, suffers from error amplification, where errors in the model compound and generation quality degrades as sequence length H increases. From a theoretical perspective, this phenomenon should not appear in well-specified settings, and, indeed, a growing body of empirical work hypothesizes that misspecification, where the learner is not sufficiently expressive to represent the target distribution, may be the root cause. Under misspecification -- where the goal is to learn as well as the best-in-class model up to a multiplicative approximation factor C≥ 1 -- we confirm that C indeed grows with H for next-token prediction, lending theoretical support to this empirical hypothesis. We then ask whether this mode of error amplification is avoidable algorithmically, computationally, or information-theoretically, and uncover inherent computational-statistical tradeoffs. We show: (1) Information-theoretically, one can avoid error amplification and achieve C=O(1). (2) Next-token prediction can be made robust so as to achieve C=tilde O(H), representing moderate error amplification, but this is an inherent barrier: any next-token prediction-style objective must suffer C=Omega(H). (3) For the natural testbed of autoregressive linear models, no computationally efficient algorithm can achieve sub-polynomial approximation factor C=e^(log H)1-Omega(1); however, at least for binary token spaces, one can smoothly trade compute for statistical power and improve on C=Omega(H) in sub-exponential time. Our results have consequences in the more general setting of imitation learning, where the widely-used behavior cloning algorithm generalizes next-token prediction.