CS Paper Radar

Generative sequence modeling for infinite memory processes via predictive states

Michael Wieck-Sosa, Cosma Rohilla Shalizi

cs.LG stat.MLstat.ME ·submitted 2026-09-29 20:42 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.69
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

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

cs.IT stat.MLcs.LG ·2026-09-28 ·Masoud Kavian, Abdellatif Zaidi, Milad Sefidgaran
similarity 0.66
Abstract · 49 Pages, 6 Figures

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.

0.31

Empirical concentration for chains with infinite memory

cs.LG stat.ML ·2026-10-23 ·Pierre Alquier, Paul Doukhan
similarity 0.64
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

Mitigating Representation Gaps in Amortized Bayesian Inference with Auxiliary Supervision

cs.LG stat.MLstat.COstat.ME ·2026-09-30 ·Hans Olischläger, Svenja Jedhoff, Šimon Kucharský, Aayush Mishra, Stefan T. Radev +1 more
similarity 0.61
Abstract

Casting Bayesian inference as a neural network optimization problem targeting an amortized posterior is attractive, as it extends to otherwise intractable statistical models and offers near instantaneous inference for new datasets after prepaying the training cost. Although theory guarantees faithfulness under ideal convergence, practical amortized inference still requires iterating over architectures and optimization choices and ultimately ``satisficing'' under finite simulation, compute, and time budgets. Even the best-performing solution may thus retain avoidable representation gaps that typically require problem-specific fixes. Here, we propose a generic alternative which improves training dynamics with auxiliary guidance losses applied to internal representations. Specifically, we show how such guidance leads to faster convergence when training data is abundant and to better performance when it is scarce. We formalize representation gaps as getting stuck in a local optimum at the information bottleneck between the parts of the network tasked with feature learning and those tasked with conditional distribution learning, and offer a generic diagnostic to separate summary failures from inference failures. Finally, we demonstrate that auxiliary supervision improves convergence speed and accuracy on a range of challenging real-world inference problems.

0.27

Next-token functional estimation

cs.IT stat.MLcs.LGmath.PR+1 ·2026-09-17 ·Milind Nakul, Vidya Muthukumar, Ashwin Pananjady
theory similarity 0.60
Abstract

Suppose we observe the first $n$ points of a sequence of random variables having length $n+1$, and wish to estimate a functional of the unobserved final point and the empirical measure of the $n$ observed training points. Such next-token functionals include the probability that the next token is novel (also known as the surprise probability), the tail probability of the minimum distance between the next token and training points, and the test error of a classifier trained on the observed points. All of these quantities are classically estimated by the leave-one-out method, which is inconsistent under temporal dependence. We propose a leave-a-window-out estimator, which deletes a window of length $τ$ after each index before forming the empirical measure and reduces to leave-one-out at $τ= 1$. Under natural assumptions, we show that the error of our estimator decays at a parametric rate for any stationary $β$-mixing process that also admits a Marton coupling. Our results thus cover several natural functionals on a large class of stochastic processes. We complement these upper bounds with a sharp minimax lower bound for estimating the surprise probability on mixing Markov chains. Simulations on Markov chains, moving-average processes, and autoregressive processes show that our estimator succeeds in many scenarios where leave-one-out and add-constant baselines fail.

0.23

Particle GFlowNets: Rethinking Generative Marginalization Models

cs.LG ·2026-09-10 ·Tiago da Silva, Diego Mesquita, Salem Lahlou
published similarity 0.60
Abstract · Accepted at UAI 2026

Generative Marginalization Models (MaMs) have been recently introduced as efficient neural sampling models for any-order autoregressive modelling of discrete distributions. By learning both the marginal and conditional probabilities of a persistent-block Gibbs sampler, MaMs enable fast posterior evaluation with a single neural network forward pass. While prior work has considered MaMs to be distinct from Generative Flow Networks (GFlowNets), a well-established paradigm for inference in discrete stochastic models, we show that they are equivalent. Then, we also extend MaMs' sampling strategy to non-autoregressive generative processes. In particular, we describe an automatic criterion for full-state rejuvenation of the Gibbs sampler, derived from the Gelman-Rubin statistic, which plays a key role in speeding up learning convergence. Our experiments show that our method, called Particle GFlowNets, markedly accelerates training in large combinatorial spaces.

0.29

From Complex Histories to Simple Predictors: Predictive Dimension in Dynamic Graph Learning

cs.LG cs.AI ·2026-10-20 ·Hantong Feng, Duxin Chen, Wenwu Yu
similarity 0.60
Abstract

Existing continuous-time graph learning methods rely heavily on complex neural architectures to encode ever-expanding interaction histories. However, the future conditional distribution induced by complex histories can often be characterized by a low-dimensional predictive state manifold, implying that only a few predictive degrees of freedom are essential for future interactions. We therefore argue that continuous-time graph learning should identify low-dimensional states sufficient for future prediction rather than reconstruct the full history. To make this perspective measurable, we define and independently estimate the intrinsic predictive dimension, which quantifies the effective predictive degrees of freedom required by a given task. Specifically, we remove the history-independent marginal from the history-conditioned future distribution, decompose the resulting predictive residual operator, and estimate the minimum effective rank needed to preserve the predictive power of the full history. Experiments across datasets show that model performance saturation is largely determined by the intrinsic predictive dimension. Based on this finding, we propose PreDyG, a lightweight model whose capacity is matched to the intrinsic predictive dimension. PreDyG achieves superior predictive performance with only 0.07\% of the parameters of a representative complex baseline.

0.17

Efficient Deep Gaussian Process Surrogates via Mini-Batch Latent MAP Estimation

cs.LG stat.ML ·2026-10-27 ·Chun-Yi Chang, Chih-Li Sung
similarity 0.60
Abstract · 35 pages including references, 11 pages appendix, 5 figures

Deep Gaussian processes (DGPs) are flexible surrogate models for computer experiments with nonstationary response surfaces, but inference over their latent representations remains computationally challenging. Existing methods typically rely on variational inference or Markov chain Monte Carlo (MCMC), which impose variational-family assumptions or require costly posterior sampling. We propose the latent maximum-a-posteriori deep Gaussian process (LaMP-DGP), which uses gradient-based optimization to obtain MAP estimates of the latent representations and enables efficient probabilistic prediction through linked-GP calculations. To scale LaMP-DGP to large datasets, we develop a mini-batch optimization algorithm and, under a polynomial mini-batch bias-decay condition, establish a stationarity bound for latent-state optimization that motivates a growing batch-size schedule. Across numerical experiments and real-data analyses, LaMP-DGP provides consistently competitive predictive performance relative to doubly stochastic variational inference, stochastic gradient Hamiltonian Monte Carlo, and fully Bayesian Vecchia DGP inference. Computationally, LaMP-DGP is substantially faster than the Vecchia MCMC approach while remaining broadly competitive with the stochastic-gradient alternatives. These results position LaMP-DGP as a competitive and computationally efficient alternative for DGP inference. An R package, "LaMPDGP", is available for implementing the proposed method.

0.15