# Provable Long-Range Benefits of Next-Token Prediction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 55 references that are in the map.
- First posted on arXiv 8 Dec 2025.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks](https://mlsanity.com/paper/1506.03099/) (2015)
- [Sequence Level Training with Recurrent Neural Networks](https://mlsanity.com/paper/1511.06732/) (2015)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Unifying Human and Statistical Evaluation for Natural Language Generation](https://mlsanity.com/paper/1904.02792/) (2019)
- [Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generation](https://mlsanity.com/paper/2204.01171/) (2022)
- [Is ChatGPT a Highly Fluent Grammatical Error Correction System? A Comprehensive Evaluation](https://mlsanity.com/paper/2304.01746/) (2023)
- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [Analysis of classifiers' robustness to adversarial perturbations](https://mlsanity.com/paper/1502.02590/) (2015)
- [Limitations of Language Models in Arithmetic and Symbolic Induction](https://mlsanity.com/paper/2208.05051/) (2022)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [FELM: Benchmarking Factuality Evaluation of Large Language Models](https://mlsanity.com/paper/2310.00741/) (2023)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Large Language Models Meet Symbolic Provers for Logical Reasoning Evaluation](https://mlsanity.com/paper/2502.06563/) (2025)
- [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023)
- [Language models are better than humans at next-token prediction](https://mlsanity.com/paper/2212.11281/) (2022)
- [Prediction with a Short Memory](https://mlsanity.com/paper/1612.02526/) (2016)
- [Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms](https://mlsanity.com/paper/2209.00735/) (2022)

## Abstract (arXiv)

Why do modern language models, trained to do well on next-word prediction, appear to generate coherent documents and capture long-range structure? Here we show that next-token prediction is provably powerful for learning longer-range structure, even with common neural network architectures. Specifically, we prove that optimizing next-token prediction over a Recurrent Neural Network (RNN) yields a model that closely approximates the training distribution: for held-out documents sampled from the training distribution, no algorithm of bounded description length limited to examining the next k tokens, for any k, can distinguish between k consecutive tokens of such documents and k tokens generated by the learned language model following the same prefix. We provide polynomial bounds (in k, independent of the document length) on the model size needed to achieve such k-token indistinguishability, offering a complexity-theoretic explanation for the long-range coherence observed in practice.