On the Sample Complexity of Next-Token Prediction

Oğuz Kaan Yüksel, Nicolas FlammarionAISTATS 2025 · OpenReview

Abstract

Next-token prediction with cross-entropy loss is the standard objective for sequence and language modeling. Despite its ubiquity, theoretical analysis regarding how these models generalize has remained sparse. This work provides a rigorous analysis of empirical risk minimization (ERM) for sequential inputs generated by order-$k$ Markov chains. By assuming bounded and Lipschitz logit functions, the study demonstrates that in-sample prediction error decays optimally with the number of tokens. Crucially, the research shows that generalization error depends on the statistical complexity (metric entropy) of the hypothesis class rather than the exponentially large state space of the Markov chain. This explains how modern architectures, such as Transformers, escape the "curse of dimensionality" that hindered classical $k$-gram models.

Introduction

Large Language Models (LLMs) like GPT-4 exhibit remarkable capabilities, yet they are trained on a seemingly simple objective: predicting the next token in a sequence. A significant gap has persisted in our theoretical understanding of this process: How much data is actually required for these models to generalize to unseen text?

In classical linguistics, $k$-gram models were the standard. These models function by counting the frequency of a word following a specific sequence of $k$ previous words. However, the number of possible sequences grows exponentially with $k$. For a vocabulary of 50,000 words and a context of 10 tokens, there are $50,000^{10}$ possible sequences—a number far exceeding the atoms in the observable universe. This "curse of dimensionality" suggested that learning long-range dependencies was statistically impossible. Modern LLMs, however, do not simply count sequences; they use neural networks to approximate underlying probability distributions. This paper quantifies the "sample complexity"—the relationship between training tokens and prediction error—to explain why this modern approach succeeds where $k$-grams failed.

Theoretical Framework

The authors analyze Empirical Risk Minimization (ERM) using cross-entropy loss for sequences generated by order-$k$ Markov chains. The analysis relies on several key technical components:

  • Hypothesis Classes: Rather than exploring all possible transitions, the search is restricted to specific function classes (logits), such as linear predictors or self-attention layers.
  • Metric Entropy: This tool from statistical learning theory measures the complexity of the model architecture by counting the number of "distinctly different" models within a specific class.
  • Mixing Times: The study incorporates the "mixing time" of the data-generating process—a measure of how quickly a sequence explores its possible states and "forgets" its starting point.
  • Coupling Arguments: To address cases where language might "mix" slowly (e.g., a long text remaining on a niche topic), the authors introduce a novel coupling assumption. This assumes that if a single token in a context is changed, the likely continuations of the two versions will eventually converge rather than diverge infinitely.

Key Insights and Results

Escaping the Curse of Dimensionality

The primary finding is that the generalization error of these models depends on the metric entropy of the model class, not the size of the state space. This is a critical distinction: if a model architecture (like a Transformer) has a compact way of representing language, it requires significantly less data to learn than a model attempting to memorize every possible $k$-gram.

Optimal Decay Rates

The paper proves that for a wide range of models, the prediction error decays at a rate of approximately $1/(\text{Total Tokens})$. This matches the optimal rate for much simpler, non-sequential data (i.i.d. settings), suggesting that the sequential nature of language does not inherently degrade the efficiency of the learning process.

In-Sample vs. Out-of-Sample Performance

The authors show that "in-sample" error (error on contexts the model has already encountered) is highly stable and independent of the data's mixing properties. It decays optimally at a rate of $1/NT$ (where $N$ is the number of sequences and $T$ is their length). While out-of-sample error typically incurs a penalty based on mixing times, the authors' coupling assumption allows for generalization rates that are independent of global mixing times, providing a more realistic framework for natural language.

Complexity of Self-Attention

The study specifically calculates the metric entropy for a single-layer self-attention model. The results show that this complexity is independent of the context length $k$. This explains a fundamental property of modern AI: we can increase the context window of LLMs without requiring an exponentially larger training set to maintain performance.

Limitations and Future Work

While providing a robust foundation, the authors identify several avenues for future research:

  • Weight Constraints: The proofs currently assume bounded and Lipschitz functions, whereas real-world Transformer weights may grow large enough to challenge these assumptions.
  • Deep Architectures: The detailed analysis focuses on single-layer or simplified cases; extending these proofs to deep, multi-layer architectures remains a priority.
  • Empirical Verification: The "coupling assumption" is a powerful theoretical bridge, but its prevalence in real-world natural language data requires further empirical validation.

Conclusion

This work provides a theoretical justification for the empirical success of next-token prediction. By shifting the focus from the size of the state space to the complexity of the model architecture, the authors demonstrate why neural models can generalize across vast linguistic contexts using finite data. This research moves us closer to a complete statistical theory of how Large Language Models learn.

Summary updated

Abstract

Next-token prediction with cross-entropy loss is the objective of choice in sequence and language modeling. Despite its widespread use, there is a lack of theoretical analysis regarding the generalization of models trained using this objective. In this work, we provide an analysis of empirical risk minimization for sequential inputs generated by order-$k$ Markov chains. Assuming bounded and Lipschitz logit functions, our results show that in-sample prediction error decays optimally with the number of tokens, whereas out-of-sample error incurs an additional term related to the mixing properties of the Markov chain. These rates depend on the statistical complexity of the hypothesis class and can lead to generalization errors that do not scale exponentially with the order of the Markov chain---unlike classical $k$-gram estimators. Finally, we discuss the possibility of achieving generalization rates independent of mixing.
BibTeX
@inproceedings{yuksel2025sample,
  author = {Oğuz Kaan Yüksel and Nicolas Flammarion},
  title = {{On the Sample Complexity of Next-Token Prediction}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=eJkNMwzZzy},
}

Loading related content...

Figure