acceptodds
Under review as a conference paper at ICLR 2027

Predictive Memory Complexity: Persistent-State Requirements for Continual Prediction

Abstract

Continual world models accumulate an ever-growing history of experience, while the memory that can be persistently retained remains fundamentally bounded. This mismatch raises a fundamental question: how much information from the past must remain encoded in persistent state to preserve future predictive accuracy? We introduce predictive memory complexity (PMC), the minimum persistent-state capacity required to attain a prescribed prediction risk. (i) Under stationary fully observed Gaussian dynamics, Theorem 1 gives the exact finite-memory law , showing that arbitrary recursive memory reduces to quantization of the current predictive state and yielding . (ii) Removing stationarity, Theorem 2 shows that memory tracks the scale of the predictive state: , producing bounded, logarithmic, and linear growth for stable, critical, and unstable dynamics, respectively. (iii) Under partial observability, Theorem 3 bounds the excess prediction risk between quantization of the Bayesian predictive state and the better of two finite-memory mechanisms—history retention and recursive belief representation—thereby separating inferential from representational memory. (iv) Beyond Gaussianity, Theorem 4 preserves the exact quantization reduction while introducing the entropy-power factor , showing that equal variance need not imply equal finite-memory difficulty. (v) Theorem 5 specializes the theory to an isotropic KV-cache model: with bits per scalar, , and half of the asymptotically available predictive gain occurs at . Measurements from Transformer key representations provide an empirical scale check for the stylized cache regime. The results show that persistent memory is a property of the predictive process rather than merely of the predictor architecture: its required capacity is jointly governed by predictive-state geometry, dynamical expansion, and inferential uncertainty. This provides a principled basis for understanding memory in continual world models, including what predictive information must persist, how accurately it must be represented, and when fixed-capacity memory is fundamentally insufficient.

Primary area:
learning theory
Keywords:
predictive memory complexity, bounded-memory prediction, persistent state, predictive states, rate-distortion theory, sequential prediction, partial observability, KV-cache compression

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_QoiPOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper introduces predictive memory complexity, the minimum persistent state bits needed to achieve a target prediction risk. It relates finite-memory prediction to state quantization and analyzes how memory requirements depend on dynamical stability, partial observability, and non-Gaussian distributions. It further claims a compression threshold for a stylized KV-cache model, supported by numerical illustrations and temporal-correlation measurements from GPT-2 key representations.

Critical strengths
  1. The paper studies a meaningful resource question and clearly distinguishes persistent mutable memory from communication rate and fixed model parameters. The reduction to state quantization provides an interpretable connection between memory capacity and prediction accuracy.

  2. The treatment of partial observability highlights a useful distinction between retaining observations and recursively representing a predictive belief.

Critical weaknesses
  1. The exact KV-cache threshold is not established by the presented proof. Equation (20) gives a distortion lower bound, but Equation (21) treats the corresponding normalized gap as an equality without matching achievability. This supports, at most, a necessary condition for recovering half of the predictive improvement. The abstract and Theorem 5 also give different distortion bounds and threshold formulas. Additionally, Appendix E, Step 2 assumes that coordinate independence makes separate scalar encoding optimal without loss of generality, which is not justified. These issues affect a prominently advertised application result.

  2. The empirical evidence does not directly validate the proposed cache threshold, and the presentation makes the results difficult to assess. The GPT-2 experiment only measures correlations in key representations; it does not vary cache precision or measure the resulting prediction distortion or language-model performance. Evaluation on GPT-2 124M alone also limits the scope of the empirical conclusions. Figures 2 and 3 are particularly small, with legends, axis labels, and annotations that are difficult to read at normal viewing size. Figure 3 compresses several central results into three undersized panels, substantially reducing readability.

Questions for authors
  1. How is the equality in Equation (21) obtained from the lower bound in Equation (20)? For the scalar case with d=L=1d=L=1 and B=1B=1, optimal Gaussian quantization gives a normalized remaining prediction gap of 1−2/π≈0.36341-2/\pi\approx0.3634, whereas Equation (21) predicts 0.250.25. Can the authors reconcile this discrepancy and provide matching achievability?

  2. Which KV-cache threshold is intended? The abstract gives Ronset=12log⁡2(1/(1−ρ2))R_{\mathrm{onset}}=\frac{1}{2}\log_2(1/(1-\rho^2)), while Theorem 5 gives Ronset=0.5R_{\mathrm{onset}}=0.5, independent of ρ\rho. Do these formulas correspond to different assumptions or operational models?

  3. Does Theorem 5 apply to arbitrary joint encoders under a total memory budget, or only to coordinatewise encoders? What justifies the claim in Appendix E, Step 2 that separate encoding is optimal without loss of generality? Please also clarify whether the threshold is an exact finite-state result or an asymptotic approximation.

Overall, the inconsistencies between the formulas in the abstract, main text, and appendix made the paper difficult to follow and the validity of the claimed threshold difficult to assess. If the authors can reconcile these discrepancies, address the proof gaps, and clearly revise the corresponding claims, I would be willing to reconsider my assessment and potentially raise my score.

Reviewer_q6NYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the question "what capacity is needed for a predictive state to achieve a given target risk," inspired by SSMs and KV cache compression for continual world modeling. Classic coding results don't fully capture this notion of recursively persistent state, motivating an investigation into capacity bounds from simple to more fully realistic scenarios. The authors start from a one-dimensional fully observed Gauss-Markov source Xt+1=aXt+ηtX_{t+1} = a X_t + \eta_t, which reduces to simple state quantization since history isn't needed. A non-Gaussian generalization is also presented. A binary hidden Markov model is then introduced to study the effect of partial observability. A bound is derived that describes both history retention and belief representation as two mechanisms that make up the frontier in different regimes. Lastly, a stylized KV-cache result is presented.

Critical strengths
  1. One thing I find impressive about this work is that I think the authors identify a very interesting problem that appears to have been overlooked in the literature: what capacity is needed for a predictive state to achieve a given target prediction risk? As the authors explain, this is directly relevant to modern SSMs and transformers and to the particular application of continual world modeling.

  2. The writing and presentation is very clear and easy to follow. The main theorems are thematically coherent and offer a useful narrative structure that organizes the paper well.

  3. The tradeoff between the history retention and belief representation mechanisms in the binary HMM (Theorem 3) is interesting in that it suggests (but does not entirely prove, as the authors point out) there may be phase transition in the optimal strategy.

Critical weaknesses
  1. Several of the theorems are relatively minor results. For example, I think the vt→∞v_t \rightarrow \infty results of Theorem 2 are better described as a minor discussion item after the statement of Theorem 1. Similarly, Theorem 4 is a relatively minor modification of Theorem 1. Lastly, the stylized KV-cache model enforces the memory budget to be distributed across both representation dimension and sequence length, while the dynamical structure factorizes across dimension with full observability. The claim at the end of the introduction is inflated relative to the actual result: "... how these limits translation into an explicit memory threshold in a modern sequence-modeling setting." Of all the theorems, I think Theorem 3 is the strongest and most interesting. I would encourage the authors to explore the partial observability direction more deeply, perhaps using a observability model for the KV-cache setting. Another interesting direction that would be very naturally fit the paper objectives would be to explore specific classes of attention and their state capacity requirements, in the style of Mamba-2 ideas [1] or tying the filtering state more deeply to classic SSM and GP-regression ideas [2].

[1] Dao & Gu. Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality (2024) . ICML. [2] Hartikainen and Särkkä (2010). Kalman Filtering and Smoothing Solutions to Temporal Gaussian Process Regression Models. IEEE International Workshop on Machine Learning for Signal Processing.

Questions for authors

See the suggestions in weakness 1.

Reviewer_HcTxOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces predictive memory complexity: the minimum number of persistent bits needed to achieve a target prediction error. It studies this quantity for several simple stochastic processes. When the current state is fully observed, the problem reduces to quantizing that state. When the state is hidden, the paper compares storing recent observations with maintaining a quantized Bayesian belief. It also presents a application to KV-cache compression, supported by measurements of GPT-2 key correlations.

Critical strengths
  • The paper rigorously investigates finite-memory prediction for several simple stochastic processes, with explicit bounds on the memory required to achieve a target prediction error.
  • The partially observed setting provides an interesting comparison between storing recent observations and recursively maintaining a quantized predictive belief.
Critical weaknesses
  • For a machine learning audience, the paper is really hard to read as presented. The abstract includes multiple bounds and formulas without explaining what the symbols in these equations mean. Although it is not strictly necessary to explain everything in the abstract, a clear and readable presentation of the results that follow should be prioritized.
  • A large part of Sections 3 and 4 seems disconnected from machine learning applications as a whole and considers relatively simple Markovian processes whose relevance to machine learning is unclear. These sections, which contain many theorems, should be well motivated by corresponding machine learning settings or real problems encountered, instead of relying on readers to draw the connections themselves.
  • Much of the theory considers simple Markov processes with known dynamics and a fully observed current state. Since the current state already contains all the information needed for prediction, Theorem 1 reduces the problem to quantization. The nonstationary extension then follows from changes in the state variance. These results appear elementary relative to the paper’s broad framing around continual world models, and their contribution beyond existing quantization results is unclear.
  • The connection to machine learning, particularly KV-cache compression, is poorly established. The dynamics and predictive representations are assumed to be given. Measuring GPT-2 key correlations does not show that the theory predicts the effects of actual cache compression.
  • The experimental evaluation is weak when assessed as a machine learning paper, since only one experiment is presented and the theoretical results do not adequately capture a real machine learning setting. This might be viewed less harshly if the theory were practically useful or well motivated, but that is clearly not the case here in my opinion. The presentation leaves the theoretical and empirical parts largely disconnected, without clear practical implications.
Questions for authors
  • Can the authors better motivate the Markov processes studied in Sections 3 and 4 through concrete machine learning problems? What practical insights do these results provide for designing or training continual world models?

  • What is the main technical contribution beyond existing quantization results, beyond when the dynamics are known and the current state is fully observed?

  • Can the authors evaluate whether the theoretical bounds predict the effects of actual KV-cache compression on token prediction loss or downstream performance, rather than only measuring GPT-2 key correlations?

Reviewer_wjLdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper provides useful information-theoretic bounds on the amount of storage a predictor needs to achieve a given fixed prespecified loss. The authors provide bounds across a wide variety of random systems, ranging from fully-visible Gaussian to hidden Markov systems. The contributions are primarily theoretical, with only a short connection to the KV-cache in modern transformers.

Critical strengths

The authors take great care to provide information across different formulations of the memory problem, and indeed find substantively different results for each case. The simultaneous use of memory both as a store for recent information in fully-visible Gaussian systems and as Bayesian evidence within itself in hidden systems is particularly interesting, and provides a strong understanding of memory for different sequential prediction tasks.

Critical weaknesses

Although the authors do give results for multiple scenarios, the extent to which these results extend to practical machine learning pipelines remains unclear. In particular, the main \textit{practical} result in the form of transformer KV-caches relies on the assumption that the KV-cache of xTx_T is just a scalar multiple of xT−1x_{T-1} plus noise. In addition, the authors run just one experiment to understand the extent to which these assumptions are fulfilled in practice. In addition, the paper is extremely dense and would benefit from additional summaries and recaps of finished proofs.

Questions for authors
  • In the conclusion, you write that "world-model memory should be designed around what predictive information must persist, how accurately it must be represented, and how this requirement changes as the environment evolves." In that vein, could you provide specific examples for when these theorems could be used to improve continual learning/memory model architectures or training regiments?

  • Could the authors provide more empirical results bridging the gap between the assumptions of KV cache compression and real-world pretrained models? An experiment logging prediction error as a function of memory size would help characterize the validity of the assumptions with regards to practical relevance. In a more general theoretical sense, which of the regimes you discuss in this paper would you say KV-cache compression would fall into?

  • I may be misunderstanding the theorem, but I am unsure how you move from equation 20 to 21. In particular, equation 21 seems to assume that equation 20 is an equality when in fact it is an inequality. If treated as an inequality, equation 21 would only show that \textit{at most half} of the remaining improvement is recovered, not that exactly half is.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.