Information-Theoretic Analysis of Next-Token Prediction under Markovian Data

arXiv:2609.34731 · stat.ML, cs.IT, cs.LG, math.IT · Submitted 2026-09-28 · Read on arXiv

stat.ML, cs.IT, cs.LG, math.IT

Submitted: 2026-09-28

Updated: 2026-09-28

Terminology

• Generalization — 86× in this paper · explained in 13 episodes
• Transformer — 20× in this paper · explained in 2 episodes
• Generalization Bounds — 12× in this paper · explained in 2 episodes
• Embeddings — 5× in this paper · explained in 2 episodes
• Spectral Gap — 3× in this paper · explained in 5 episodes
• Tokenization — 3× in this paper · explained in 2 episodes
• Sample Complexity — 2× in this paper · explained in 15 episodes
• Scaling Laws — 2× in this paper · explained in 4 episodes
• Self-Attention Next Token Prediction — 2× in this paper
• Accuracy — 1× in this paper · explained in 1 episode
• Adam — 1× in this paper · explained in 2 episodes
• Ambient Dimension — 1× in this paper · explained in 1 episode
• Attention Mechanism — 1× in this paper · explained in 3 episodes
• Federated Learning — 1× in this paper · explained in 15 episodes
• Fine-Tuning — 1× in this paper · explained in 5 episodes
• IEEE International Symposium on Information Theory — 1× in this paper
• Information Gain — 1× in this paper · explained in 2 episodes
• Information-Theoretic Framework — 1× in this paper · explained in 2 episodes
• Loss Function — 1× in this paper · explained in 2 episodes
• Non-IID Data — 1× in this paper · explained in 2 episodes
• Pairwise Comparisons — 1× in this paper · explained in 2 episodes
• Redundancy — 1× in this paper · explained in 2 episodes
• Representation Learning — 1× in this paper · explained in 2 episodes
• Sparsity — 1× in this paper · explained in 4 episodes
• Time Series Forecasting — 1× in this paper · explained in 3 episodes
• Transformer Architecture — 1× in this paper · explained in 2 episodes
• Verification — 1× in this paper · explained in 2 episodes

Sources

• On the Expressive Power of Self-Attention Matrices
• Next-token prediction capacity: general upper bounds and a lower bound for transformers
• Towards Understanding the Universality of Transformers for Next-Token Prediction
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• General mixing time bounds for finite Markov chains via the absolute spectral gap
• Auto-Regressive Next-Token Predictors are Universal Learners
• TinyStories: How Small Can Language Models Be and Still Speak Coherent English?

Related papers

• Behavior of prediction performance metrics with rare events
• Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
• A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
• One Permutation Is All You Need: Fast, Deterministic Feature Importance and Model Stress-Testing
• Online Conformal Prediction for Non-Exchangeable Panel Data
• Deep Time-Series Forecasting in 10 Years: A Survey