CS Paper Radar

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

Masoud Kavian, Abdellatif Zaidi, Milad Sefidgaran

cs.IT stat.MLcs.LG ·submitted 2026-09-28 09:30 UTC · v1

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.

Comment
49 Pages, 6 Figures

Closest papers

Nearest neighbours by meaning across the whole index.

On the Generalization Gap of Streaming Federated Learning with Markovian Data

cs.LG cs.ITstat.ML ·2026-10-28 ·Masoud Kavian, Milad Sefidgaran, Youssef Attia El Hili, Malik Tiomoko, Abdellatif Zaidi
similarity 0.75
Abstract · 78 Pages, 5 Figures

Streaming federated learning (SFL) allows clients to train a shared model from continuously arriving data without retaining large local datasets. Such streams often exhibit temporal dependence, yet its effect on generalization remains poorly understood. In this paper we study the expected generalization gap of the aggregated model when client data follow Markov processes, using information-theoretic and rate-distortion techniques. Our framework accommodates heterogeneous Markovian dynamics across clients and distinguishes temporal dependence from information acquired during local learning. We establish bounds under cross-entropy loss, specializing them to Linear Next-Token Prediction (LNTP) and Self-Attention Next-Token Prediction (SANTP). These results quantify the effects of client count, communication rounds, sample size, data dimension, mixing time, and context length. In particular, they reveal a communication--generalization tradeoff: although frequent aggregation may help optimization, it can weaken generalization guarantees. They also suggest a potential advantage of distributed over centralized streaming learning under a fixed total data budget. Temporal dependence enters through the square root of the mixing time. By analyzing the history-state process, we obtain refined bounds with improved context-length dependence under suitable mixing conditions. Experiments on GPT-style language-model pretraining with TinyStories and real-world time-series forecasting illustrate how collaboration and communication frequency influence generalization under temporal dependence

0.08

Memory Prediction Excess: A Probabilistic Quantity for Predictive Gain and Memory Length in Stochastic Processes

cs.IT stat.MLcs.LGmath.PR ·2026-09-28 ·Jiahao Jiang
theory similarity 0.68
Abstract

A central question in the prediction of stochastic processes is the extent to which past information can improve the probability of correctly predicting the next state. We introduce the Memory Prediction Excess (MPE) to address this question quantitatively. The MPE measures the average improvement in prediction accuracy obtained by using the entire observed history relative to using only the static marginal distribution, in discrete-time finite-state processes. It is defined as the difference between the expected optimal conditional prediction accuracy and the optimal static prediction accuracy. Its basic properties are examined: the MPE is always non-negative; it admits an upper bound depending on the static accuracy, attained if and only if the future is almost surely a deterministic function of the past; and degenerate cases in which the MPE vanishes are characterized. A normalized version, taking values in the unit interval, is introduced as a dimensionless measure of predictive efficiency. A lower bound is derived by comparing predictions based on histories of different lengths, showing that the expected optimal prediction accuracy is monotone with respect to the history length. The framework is extended to finite-length histories, where the finite-history MPE (FH-MPE) measures the predictive gain attainable when only the most recent observations are retained. This leads to the notion of a minimal memory length required to achieve the same predictive performance as the full history. For finite-order Markov chains, this minimal memory length is shown to be bounded by the Markov order. The MPE and its variants are formulated in terms of conditional probabilities and prediction accuracies, offering a probabilistic perspective on the predictive utility of memory that is complementary to classical information-theoretic approaches.

0.27

Generative sequence modeling for infinite memory processes via predictive states

cs.LG stat.MLstat.ME ·2026-09-29 ·Michael Wieck-Sosa, Cosma Rohilla Shalizi
similarity 0.66
Abstract

We consider estimating the one-step-ahead conditional distribution of a multivariate stochastic process. Many existing approaches rely on assumptions such as finite-range memory, sparsity, or additivity, which can be poorly suited to processes with long-range nonlinear interactions. However, without such structural assumptions, nonparametric estimation is challenging due to the curse of dimensionality. To address this challenge, we introduce a new estimator based on learning representations of the \emph{predictive states} of a stochastic process. We show that the statistical complexity of the estimation problem is determined by the dimension of this predictive state representation. Furthermore, we show that a $p$-dimensional predictive state space can be represented in a $2p+1$-dimensional feature space. Our results imply that faster convergence rates are achievable when the predictive state space is lower-dimensional, i.e., when the past history can be compressed into a lower-dimensional statistic that is sufficient for predicting the future. We establish theoretical convergence rate guarantees for an instantiation of our method based on deep neural network estimators. We implement our method in PyTorch and evaluate its performance on processes with infinite-range memory.

0.42

Recursive memory for prediction and generation

cs.IT stat.AP ·2026-11-10 ·Pengbin Feng, Chunlei Meng
theory similarity 0.65
Abstract

Recurrent and state-space language models compress the past into a state of fixed size. The state must answer questions about the future now, and it must remain useful as new tokens arrive, including tokens the model samples itself. We show that the second requirement can cost far more memory than the first. For a known hidden Markov source with positive transition probabilities, a state of $O(\log(1/\varepsilon))$ bits answers every question about the future to accuracy $\varepsilon$, however far ahead it looks, because the Bayesian filter forgets its rounding errors. Generating the future is different. When a model feeds each sampled token back into its state, the small errors in its next-token distributions add up, and $T$ tokens can require a state of order $\log(T/\varepsilon)$ bits. The lower bound comes from the KL chain rule: at every step, a model with $K$ states pays for approximating the true next-token distribution by one of only $K$ distributions. The argument applies to any source, including a language model continuing a prompt, and a small-ball estimate makes it tight for two-state sources. The extra $\log T$ disappears if the model keeps private randomness, or if error is budgeted per token, as in perplexity. Statistics of the recent past show the same gap between describing and maintaining. The number of ones among the last $n$ bits takes $\log n$ bits to write down. But if each bit is a noisy copy of the one $n$ steps earlier, tracking that count to a mean-square error $E^2$ well below its variance costs order $n/(1+E^2)+\log n$ bits. Information about each bit must be kept until the bit leaves the window, and a queue holding the counts of recent blocks keeps just enough of it.

0.17

Speed limits for information acquisition in stochastic learning dynamics

cs.LG cond-mat.stat-mechstat.ML ·2026-09-08 ·Shuta Kobayashi, Andreas Dechant
theoryhot direction similarity 0.65
Abstract · 15 pages, 4 figures

Neural networks acquire internal representations through learning. In this work, we formulate stochastic gradient descent (SGD) as a Markovian stochastic process and derive a Fisher-information flow speed limit that bounds the rate at which trainable parameters can acquire information about data-generating parameters. The resulting inequality decomposes the upper bound on the information flow into drift and noise contributions, thereby quantifying the roles of deterministic learning forces and SGD-induced fluctuations from an information-theoretic perspective. We verify the bound in analytically tractable basis-function linear regression, where the information budget predicted by the bound reproduces the ordering and characteristic time scales with which different data-generating parameters are encoded in the learned parameters. These results establish Fisher-information speed limits as a quantitative framework for understanding which properties of the data-generating process are acquired, in what order, and how rapidly they can be encoded in the trainable parameters.

0.33

Empirical concentration for chains with infinite memory

cs.LG stat.ML ·2026-10-23 ·Pierre Alquier, Paul Doukhan
similarity 0.65
Abstract

Concentration inequalities for time series usually involve unknown quantities measuring dependence. This prevents their direct use as confidence bounds, or as criteria for learning algorithms. Recent works proved empirical concentration inequalities for stationary Markov chains, where the unknown quantities are estimated. We extend this approach beyond the Markov case, by considering stationary chains with infinite memory. We first establish a bounded-differences inequality on bounded Polish metric spaces under a summable Wasserstein contraction condition. We then estimate its dependence coefficients from a single trajectory, using either transition counts when the state space is finite, or derivatives of kernel conditional-density estimates for a continuous state space. We give general error bounds and illustrate their dependence on the memory tail. Finally, a fixed multiplicative safety factor turns these estimators into empirical concentration bounds. While some regularity assumptions are required to make the bounds empirical, our procedure remains fully adaptive in the sense that it does not require the knowledge of the constants involved in these assumptions. The empirical confidence bounds derived from our results are asymptotically as tight as the theoretical ones.

0.14

Does Compression Imply Generalization? A Minimum Description Length Perspective

cs.LG ·2026-10-15 ·Lincen Yang, Jiayang Shi, Nan Pu, Daniël M. Pelt, Matthijs van Leeuwen +2 more
top venue similarity 0.63
Abstract · Published at NeurIPS 2026

A central question in modern learning theory is what notion of compression, if any, explains why over-parameterized neural networks generalize. Existing answers measure complexity at different levels, ranging from weights to representations; however, estimating the associated quantities either requires held-out data in principle or relies on the challenging (ultra) high-dimensional mutual information estimation. To overcome these challenges, we approach the question through the minimum description length (MDL) principle, and specifically, we propose the prequential regret as a complementary signal that is computable from the training trajectory alone. We establish that, in the (nearly) interpolating regime, the expected prequential regret upper-bounds the description length of the trained parameter under the algorithm-induced distribution, and that this description length translates into a high-probability generalization bound in the PAC-MDL setting. Along the way, we show that the encoder-complexity correction recently added to the algorithm-level information bottleneck (IB) is upper-bounded by an MDL parameter description length, \new{bringing together} the two views of compression from MDL and IB. Empirically, the prequential regret tracks the generalization error on CIFAR-10 and CIFAR-100, with Pearson correlations exceeding 0.9.

0.41

On the Information Bottleneck for Ergodic Finite-State Markov Chains: Stationary Approximation and Asymptotic Optimality

cs.IT ·2026-10-19 ·Wael Tabbara, Jihad Fahs, Mohamad Assaad
similarity 0.63
Abstract

In this paper, we investigate the information bottleneck problem for sources that follow discrete-time ergodic finite-state Markov chains. We propose treating observations generated by the time-varying Markov chain as if they were drawn from its unique stationary distribution, and we use the solution to the information bottleneck problem for the stationary process to compress samples from the time-varying process. The resulting error is upper bounded by several information gap terms. We establish sufficient conditions under which these gaps converge to zero and analyze the convergence rates of the different information gap terms. The proofs are based on intricate analysis using convergence of subsequences along with the derivation of properties of the optimization sets associated with the information bottleneck problem. In addition to the inequalities and convergence results we establish, our analysis offers insights into how simple properties of ergodic Markov chains give rise to results concerning the information bottleneck problem for such chains.

0.31