[Paper] Provable Long-Range Benefits of Next-Token Prediction

Source: arXiv - 2512.07818v1

Overview

Modern language models are trained to predict the next token, yet they surprisingly generate coherent, long‑form text. This paper proves that next‑token prediction is inherently capable of capturing long‑range structure when used with standard recurrent neural networks (RNNs). In other words, a well‑trained RNN can produce sequences that are statistically indistinguishable from real documents, even when an adversary is allowed to look at any fixed window of k consecutive tokens.

Key Contributions

• Theoretical guarantee of long‑range fidelity: Shows that an RNN trained on next‑token loss approximates the true data distribution so well that no bounded‑size algorithm can tell apart k‑token windows from the model versus the original corpus.
• Polynomial‑size model bound: Provides explicit polynomial bounds (in k but independent of total document length) on the number of hidden units and parameters needed to achieve the indistinguishability property.
• Complexity‑theoretic perspective: Frames the success of next‑token training as a provable property rather than an empirical mystery, linking language modeling to concepts from computational learning theory.
• General applicability: The results hold for any RNN architecture that can represent the required functions (e.g., vanilla RNNs, LSTMs, GRUs) without exotic modifications.

Methodology

1. Formal problem setup – The authors define a training distribution over documents and a next‑token loss objective for an RNN.
2. Indistinguishability criterion – They introduce a game: an algorithm with limited description length (i.e., bounded computational resources) receives a length‑k token window and must decide whether it came from a real document or from the model conditioned on the same prefix.
3. Proof strategy –
   • Expressivity argument: Show that an RNN of polynomial size can encode the exact conditional probabilities of the training distribution for any prefix.
   • Optimization guarantee: Prove that minimizing the next‑token loss drives the RNN’s conditional distribution arbitrarily close to the true one.
   • Complexity bound: Use information‑theoretic tools to bound the description length needed for any distinguisher, demonstrating that for the chosen model size the distinguisher’s success probability is negligible.
4. Parameter scaling analysis – Derive explicit polynomial relationships between k (the window size) and the required hidden dimension/weight magnitude.

The proof is deliberately kept at a high level, avoiding deep tensor calculus, so developers can follow the intuition: if the model can predict the next word well enough, it must have learned the underlying statistical dependencies, no matter how far apart they are.

Results & Findings

• k‑token indistinguishability: For any fixed k, a polynomial‑size RNN trained on next‑token loss yields a model where the distribution over any k consecutive tokens (conditioned on the same prefix) is statistically indistinguishable from the true data distribution.
• Model size scaling: The required hidden dimension grows roughly as O(k³) (exact exponent depends on the architecture), which is modest compared to the billions of parameters used in today’s transformer‑based LMs.
• Independence from document length: The guarantee holds for arbitrarily long documents; the bound does not deteriorate as the sequence grows.

In plain terms, the paper shows that good next‑token prediction automatically gives you good long‑range coherence, and it quantifies how big the network needs to be to achieve a given level of coherence.

Practical Implications

• Confidence in next‑token training: Developers can trust that optimizing for next‑token loss is not a shortcut; it fundamentally captures long‑range dependencies, justifying the continued use of this objective in large‑scale LMs.
• Model sizing heuristics: The polynomial bound offers a rule‑of‑thumb for estimating the hidden size needed to guarantee coherence over a desired window (e.g., to ensure 100‑token consistency, a hidden dimension on the order of a few thousand may suffice).
• Efficient architecture choices: Since the theory applies to simple RNNs, it suggests that, for certain applications (e.g., on‑device language modeling), a well‑tuned RNN could replace a heavyweight transformer without sacrificing long‑range quality.
• Benchmark design: The indistinguishability framework can inspire new evaluation metrics that test k-token realism rather than relying solely on perplexity or human judgment.

Limitations & Future Work

• Assumption of exact optimization: The proofs require the RNN to achieve (near) global minima of the next‑token loss, which is not guaranteed in practice with stochastic training.
• Restricted to RNNs: While the authors argue the results extend to other recurrent architectures, they do not cover attention‑based models (e.g., Transformers) that dominate current deployments.
• Bound tightness: The polynomial bounds are likely loose; empirical studies are needed to determine the smallest practical model size for a given k.
• Real‑world data complexity: The theoretical training distribution is assumed to be stationary and well‑behaved; natural language exhibits heavy‑tail phenomena and evolving vocabularies that may affect the guarantees.

Future research directions include extending the analysis to transformer architectures, relaxing the optimization assumptions, and empirically validating the theoretical size‑vs‑coherence trade‑off on large corpora.

Authors

• Xinyuan Cao
• Santosh S. Vempala

Paper Information

• arXiv ID: 2512.07818v1
• Categories: cs.LG, cs.AI, stat.ML
• Published: December 8, 2025
• PDF: Download PDF