Information-Theoretic Analysis of Next-Token Prediction under Markovian Data
Abstract
We develop an information-theoretic framework for generalization in next-token prediction under temporally dependent data. We consider independent trajectories generated by finite-memory Markov processes and distinguish algorithmic dependence, quantified by mutual information, from temporal dependence, characterized by mixing. For cross-entropy loss, we derive an expected generalization bound using the Donsker--Varadhan variational representation and a McDiarmid-type concentration inequality for Markov chains. A refinement captures the joint effect of context length and temporal mixing through the mixing properties of the history-state process. We then extend the bound through a rate--distortion formulation, replacing mutual information with the minimum information rate required to represent the learned model within a prescribed distortion in the generalization gap, yielding informative guarantees for deterministic algorithms over continuous hypothesis spaces. For margin-based prediction, we derive explicit bounds for linear and self-attention next-token predictors via noisy low-dimensional compression, revealing the roles of context length, model complexity, sample size, margin, and temporal mixing. Experiments on TinyStories and ETTh2 show that longer contexts can reduce both training and test losses, but typically reduce training loss more, enlarging the generalization gap. A complementary ETTh2 analysis identifies an effective predictive-memory scale near 24 hours, with no statistically supported improvement beyond this scale, offering a plausible explanation for test-performance saturation at larger contexts.
Related
- When can Optimally Trained Transformers Achieve Near-Lossless Token Prediction for non-Markovian Data?
- Next-token functional estimation
- From Semantic to Token Communication: The Next Paradigm for Large-Model-Driven 6G Intelligent Connectivity
- Measuring Learned Equivariance: An Information Theoretic Approach
- A Sample-Based Approach for Hierarchical Information-Theoretic Compression of Probabilistic Occupancy Grids
BibTeX
@misc{kavian2026informationtheoretic,
title = {{Information-Theoretic Analysis of Next-Token Prediction under Markovian Data}},
author = {Masoud Kavian and Abdellatif Zaidi and Milad Sefidgaran},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34731},
eprint = {2609.34731},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34731},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Information-Theoretic Analysis of Next-Token Prediction under Markovian Data
AU - Masoud Kavian
AU - Abdellatif Zaidi
AU - Milad Sefidgaran
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34731
UR - https://arxiv.org/abs/2609.34731
AB - We develop an information-theoretic framework for generalization in next-token prediction under temporally dependent data. We consider independent trajectories generated by finite-memory Markov processes and distinguish algorithmic dependence, quantified by mutual information, from temporal dependence, characterized by mixing. For cross-entropy loss, we derive an expected generalization bound using the Donsker--Varadhan variational representation and a McDiarmid-type concentration inequality for Markov chains. A refinement captures the joint effect of context length and temporal mixing through the mixing properties of the history-state process. We then extend the bound through a rate--distortion formulation, replacing mutual information with the minimum information rate required to represent the learned model within a prescribed distortion in the generalization gap, yielding informative guarantees for deterministic algorithms over continuous hypothesis spaces. For margin-based prediction, we derive explicit bounds for linear and self-attention next-token predictors via noisy low-dimensional compression, revealing the roles of context length, model complexity, sample size, margin, and temporal mixing. Experiments on TinyStories and ETTh2 show that longer contexts can reduce both training and test losses, but typically reduce training loss more, enlarging the generalization gap. A complementary ETTh2 analysis identifies an effective predictive-memory scale near 24 hours, with no statistically supported improvement beyond this scale, offering a plausible explanation for test-performance saturation at larger contexts.
ER -