acceptodds
Under review as a conference paper at ICLR 2027

Prediction Is Not a Sufficient Memory State

Abstract

A memory that reproduces every current prediction may still have forgotten how to learn from the next observation. We characterize this distinction for exact cumulative learning and attention. For smooth convex residual losses with unrestricted real features and labels, a continuous recurrent state of fixed dimension exists exactly when the loss is polynomial. With ordinary, unweighted observations, degree requires precisely coordinates; even among histories with one fixed current predictor, exactly coordinates can remain necessary for continuation. Nonpolynomial losses have unbounded requirements on such equal-prediction histories. Bounded scalar logistic examples retain this obstruction after fixing any finite derivative jet. For ridge regression, the hidden evidence is the design matrix: the exact state costs , versus for the predictor. On a well-conditioned zero-prediction family, optimal -bit compression has average one-update error of order , , even with arbitrary randomized codes. Kernel attention gives a second exact closure classification. The results identify what future updates reveal, rather than proposing a new regression algorithm or asserting trained-model gains.

Primary area:
learning theory
Keywords:
test-time learning, learning theory, memory complexity, sufficient statistics, recurrent state, attention, streaming learning

Reviews

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

This paper studies whether keeping a model's current predictions is enough for future learning and shows that two models can make the same predictions but react differently to new data. The authors explore this question through theoretical analyses of several models, mainly supported by mathematical proofs and some numerical checks.

Critical strengths
  1. The paper studies a possibly interesting theoretical problem: whether preserving current predictions is sufficient for future learning. Given the importance of memory in machine learning, this work could be of interest to a broad range of readers.

  2. The authors provide several theoretical results covering different learning settings, including ridge regression, logistic regression, and attention mechanisms. These results could provide useful insights into the memory requirements of learning systems.

Critical weaknesses
  1. Poor writing and unclear research motivation.

My main concern is that the paper is very difficult to follow. Even after carefully reading the Introduction, I still find it hard to understand the background of this research and why this problem is important. The paper is written in a very theoretical and abstract way, with many mathematical concepts introduced without sufficient intuitive explanations. This makes it difficult for readers to understand the main contributions and judge the value of this work. I think the authors should substantially improve the presentation, especially the Introduction, by providing clearer motivation, more intuitive examples, and a better explanation of the research problem.

  1. Unclear novelty and practical significance.

Although the paper provides several theoretical results, it is not clear to me what the main new insight is compared with existing work on sufficient statistics, online learning, and memory representations. The paper also covers many different settings, including regression, logistic regression, and attention, but their connections and practical implications are not sufficiently explained. Moreover, the work is almost entirely theoretical, without empirical evaluation on practical learning tasks. While I understand that experiments are not always necessary for theoretical papers, some simple experiments or concrete examples would help readers better understand the significance of the theoretical findings.

Questions for authors
  1. Could the authors explain more clearly what problem this paper is trying to address and why it matters? I found it difficult to understand the main motivation, even after carefully reading the Introduction.

  2. What is the main technical novelty of this work compared with previous studies on sufficient statistics, online learning, and memory representations? What are the key new insights that distinguish this paper from existing work?

  3. Could the authors explain how these theoretical findings relate to practical learning systems? For example, are there any concrete cases where the limitations identified in this paper actually affect model performance?

1 comment

Thank you for requesting clearer motivation, precise novelty claims and concrete examples. The revision adds an explicit reference task, a definitions section and an executed synthetic comparison. We address your three questions directly.

  1. What problem does the paper address, and why does it matter?

We ask what a compressed history must retain to reproduce the predictor obtained by fitting the entire accumulated history, including after another observation arrives. The crucial issue is that zero error on every current prediction does not certify that the retained state can reproduce the next update.

The introduction demonstrates this with scalar ridge regression: Fh(w)=12w2+12∑(x,y)∈h(xw−y)2.F_h(w)=\frac12w^2+\frac12\sum_{(x,y)\in h}(xw-y)^2. Consider one zero-label observation with feature 1 or 2. The current predictors agree, but after the same observation (1,1), wA=wB=0,wA+=13,wB+=16.w_A=w_B=0,\qquad w_A^+=\frac13,\qquad w_B^+=\frac16. The second history supplies stronger evidence supporting zero, so the new observation should move its predictor less. That evidence is absent from the current prediction function.

Section 2 defines the common setting and distinguishes reproducing the cumulative minimizer from statistics sufficient for online regret guarantees (Foster et al., 2018). The question is which information must survive compression to support the intended future learning computation.

  1. What is technically new?

Section 4.2 explicitly acknowledges classical sufficiency, including Koopman, Hipp and Mattner. Our contribution is the operational characterization and its sharp consequences:

  • Information forced by allowed updates. Theorem 2 proves that equality of optimizer responses to every possible ordinary single additional observation is equivalent to equality of the entire accumulated gradient function. Under the stated unrestricted observation domain, it establishes exact state dimensions using unit-weight histories, continuous encoders and unrestricted decoders. Theorem 3 quantifies what remains necessary after fixing the current predictor. These are necessity statements for every admissible representation.

  • A bounded obstruction to finite derivative summaries. Theorems 4–5 construct scalar logistic histories with bounded features, the same current predictor and the same prescribed finite list of objective derivatives, while their possible continuation responses still distinguish them. A fixed amount of local curvature information therefore does not generally determine exact cumulative logistic updates.

  • A finite-precision tradeoff. Theorem 6 gives matching average-error bounds as a function of stored bits on a conditioned ridge family whose current predictors all agree. Compression precedes the unknown future update and query; the lower bound permits arbitrary randomized encoders and unrestricted decoders.

Ridge exposes the missing evidence; general residual learning identifies it; bounded logistic learning tests whether local derivatives suffice; attention gives the parallel distinction between normalized predictions and the numerator and mass needed for continuation. Table 1 summarizes these connections.

  1. Does the distinction cause a concrete prediction error?

Yes. Figure 1 and Section 8 report a comparison over 41 ridge histories with the same zero current predictor and the same diagonal evidence, but different off-diagonal evidence. After one shared observation, full recursive least squares matches the full-history batch solution numerically. The tested diagonal-evidence and raw delta recurrences return zero at the diagnostic query. At the two endpoint histories,

f_{\mathrm{diagonal}}=f_{\mathrm{delta}}=0,\qquad \mathrm{MSE}_{\mathrm{endpoints}}=4/49.$$ A test comparing only current predictions would score all these states perfectly. The common continuation exposes the lost information and its effect on prediction. The experiment evaluates the specified recurrences. Learned channels, auxiliary states or replay may preserve additional evidence and must enter the memory accounting. The approximation question is also addressed. The logistic theorem concerns exact continuation, while Propositions 9–10 bound future error from approximation of the gradient function or attention numerator and mass. This gives a constructive criterion: approximate the evidence needed by the intended future computation, and assess the state after shared updates as well as before them.
Reviewer_MSKzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper theoretically studies what a recurrent memory must keep so that a learner can update while reproducing its current predictions. The main claim of the paper is that a memory can match every current prediction yet still miss evidence that future updates need, such as the matrix Ch=λI+∑ixixi⊤C_h=\lambda I+\sum_i x_ix_i^\top in ridge regression or the normalization mass in attention. The paper derives the minimal exact state for ridge regression, smooth convex residual losses, and kernel attention, and shows that a fixed-size exact state exists only for polynomial losses; for bounded logistic regression, it proves that no fixed-size continuous state computes the update exactly. It also gives a finite-bit version for ridge.

Critical strengths
  1. I checked the proofs of Thm 1 (including the Eq. 4 example), Thms 2–5, and Lemmas 14–17, and Thm 6. I did not find any noticeable errors.
  2. Thms 3–5 show that adding curvature (a Hessian) cannot give exact continuation beyond polynomial losses, which relates to recent curvature-aware recurrences.
Critical weaknesses
  1. Thms 2–3 are the optimization analogues of the Pitman–Koopman–Darmois theorem. Koopman [1] showed that, for analytic densities and continuous statistics, fixed-dimensional sufficiency forces an exponential form, using the same invariance-of-dimension argument as Lemma 11. For location families, Koopman showed the exponent must be a polynomial in x−θ1x-\theta_1 (his Thm IV), which parallels the polynomial dichotomy of Thm 3. Hipp [2] gives natural regularity conditions (locally Lipschitz statistics) for such results. With exp⁡(−ρ(x⊤w−y))\exp(-\rho(x^\top w-y)) as the likelihood, "equal accumulated gradient functions" is exactly sufficient for ww. I am not sure which part should be considered new.
  2. For attention, [3] proves that exact or (1±η)(1\pm\eta)-approximate attention needs Ω(nd)\Omega(nd) bits when d≥Clog⁡nd\ge C\log n. The qualitative conclusion of Sec. 7 is therefore already known, and [3] is not cited.
  3. The evaluation protocol in Sec. 8 is proposed but never run (maybe should at least add a small synthetic DeltaNet/TTT/MesaNet). The writing is very dense, with many defensive negations. About 12 pages of appendices (H–M) develop a "Complete Attention" construction that is barely connected to the main claims.

References:

[1] B. O. Koopman. On distributions admitting a sufficient statistic. Transactions of the American Mathematical Society, 39(3):399–409, 1936. DOI: 10.1090/S0002-9947-1936-1501854-3.

[2] C. Hipp. Sufficient statistics and exponential families. The Annals of Statistics, 2(6):1283–1292, 1974. DOI: 10.1214/aos/1176342879.

[3] T. Haris and K. Onak. Compression barriers in autoregressive transformers. In Proceedings of the Conference on Learning Theory (COLT), PMLR 291:2757–2785, 2025.

Questions for authors

See weakness.

2 comments

Thank you for checking the proofs and for identifying these connections. The revision makes the classical antecedents explicit and states the additional claims more precisely.

  1. What goes beyond classical sufficiency?

We agree with the sufficiency correspondence: equal accumulated gradients imply that the losses differ by a parameter-independent constant, giving the usual equivalence for a corresponding likelihood. Section 4.2 now cites Koopman (1936) and Hipp (1974), alongside Anselone–Korevaar and Mattner for the function-space antecedents.

Theorem 2 starts from an optimizer-only requirement and proves that it forces preservation of the entire accumulated gradient function. Equation (7) supplies the decisive construction: one ordinary observation, with the same residual loss and unit weight, makes any chosen parameter the next optimum. Equality of responses to all allowed observations therefore forces equality of the old gradients everywhere.

The proof also constructs an open family of distinguishable gradient functions using unweighted histories at one fixed length. Function dimension is consequently both attainable and necessary for arbitrary continuous encoders with unrestricted decoders. These identification and reachability steps establish why the learner's required outputs force it to retain sufficient evidence.

Theorem 3 resolves this question within histories having exactly the same current predictor. Under its unrestricted feature and label domain, the dimensions for a degree-D loss are

m_{\mathrm{fixed\ predictor}}=\binom{d+D}{D}-1-d.$$ For nonpolynomial losses the second requirement is also unbounded. Section 4.3 realizes these families through a unit-weight balancing construction. The second count concerns prefix summaries at the fixed predictor; a global recurrence may require the full state. Polynomial rigidity and the dimension argument are classic. **The contribution is the characterization of memory forced by allowed learning responses, including the exact evidence requirement after fixing the current predictor.** 2. Bounded data and finite precision Theorems 4–5 construct bounded scalar logistic histories with identical current predictors and identical objective derivatives through any prescribed finite order, while leaving arbitrarily large families distinguishable by their functions of possible one-observation responses. Those continuations can use arbitrarily small positive features. This is an exact obstruction already in one feature dimension. The revision also explains how curvature supports local approximation. Theorem 6 gives a matching finite-bit law on a conditioned ridge family with identical current predictions: $$R_B \asymp \frac{r^2}{d}\cdot 2^{-2B/s_d}, \qquad s_d=\frac{d(d+1)}{2}.$$ Here r is the family's radius parameter. The code precedes the unknown update and query. The lower bound permits arbitrary randomized codes and unrestricted decoders, including decoders that reconstruct no matrix. The exponent is classical; the additional result is the response-to-matrix metric comparison and the matching prediction-error law for this continuation task. The upper bound is an offline quantizer. 3. Attention and Haris–Onak Haris–Onak (2025) is now cited in Section 7 and credited for the qualitative compression barrier. Proposition 7 identifies the precise evidence required by one-token continuation: both numerator and normalization mass. Their standard additive representation is credited to Katharopoulos et al. Theorem 8 gives the kernel-rank classification for weighted histories and, for unweighted exponential attention with distinct keys and an open query domain, $$m=N(d+p),\qquad m_{\mathrm{zero\ values}}=Nd.$$ These are exact continuous-coordinate counts. Haris–Onak gives finite-bit bounds covering approximation; the revision distinguishes the models and assumptions. 4. Executed test and presentation Figure 1 and Section 8 now report a test over 41 ridge histories. All current predictors and diagonal evidence agree. After a shared observation, full RLS matches batch ridge numerically, while diagonal evidence and the specified raw delta recurrence return zero at the diagnostic query. The endpoint reference predictions and resulting endpoint error are $$f_{\mathrm{reference}}=\pm2/7,\qquad \mathrm{MSE}_{\mathrm{endpoints}}=4/49.$$ Section 2 supplies the definitions, and the results have explanatory introductions. Section 8 connects Complete Attention to the main question through Proposition 28: identical normalized fusion actions conceal precision needed by a future observation. The construction remains in Appendices H–M; all main memory proofs are self-contained in A–G.

Thank you for the response and the revision. However, my main concern has not been resolved: there is still no experiment in a realistic setting. The new test in Fig. 1 is a two-dimensional ridge toy example, and no modern setting (e.g., a trained DeltaNet, TTT or MesaNet layer) is evaluated. I will keep my score of 2.

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

This paper presents theoretical results to understand the learning processes of a memory in ridge regression and attention. The authors tackle many different results ranging from ridge regression, polynomial closure for equal-prediction memory and finite-bit memory.

Critical strengths

None

Critical weaknesses

This paper is impossible to read for anybody who did not write the paper. There is no section used to describe the setting of interest nor the main components of the results. There are no definitions for memory, histories, attention or clock. Some mathematical definitions are given, but there is no explanation as to what they describe. For example, in equation 5, what are F, R and ρ\rho ? We know that R is fixed, C∞C^{\infty} and λ\lambda-strongly convex, but not what is its use and what it represents. The results are barely discussed and never introduced. When introduced, the lack of definitions mentioned earlier gives the reader no tools to understand them. The paper either doesn't follow a story or simply doesn't take the time to explain what is this story as each page is a different section with seemingly no link between each other. There is also a lot of blank space, amounting to almost a whole blank page throughout the paper. This is a serious formatting problem. Section 9 is mostly composed of a list of keywords stringed into nonsensical sentences.

Thus, I recommend rejection.

Questions for authors

Here are some missing definitions that would help the reader understand the paper :

  1. What is a memory in your setting?
  2. What is an history ?
  3. What is a readout?
  4. Any assumptions on the decoder in section 2? And where does it appear in the results?
  5. What is an exact recurrent learner ?
  6. What is "equal-prediction" ?
  7. What is a "zero-label history" ?
  8. What is DeltaNet and please cite the source.

I will stop at section 2 as there are many other missing definitions.

1 comment

Thank you for identifying the missing definitions and the difficulty in following the argument. We have rebuilt the exposition around one question: what must a memory retain to reproduce a reference learner after another observation arrives? The revised introduction motivates the question, Section 2 defines the common setting, and subsequent sections explain the purpose of each result.

The opening example is the following. Consider scalar ridge regression with objective Fh(w)=12w2+12∑(x,y)∈h(xw−y)2.F_h(w)=\frac12w^2+\frac12\sum_{(x,y)\in h}(xw-y)^2. Take one zero-label observation with feature 1 or 2. Both predictors are zero. Appending the same observation (1,1) gives wA=wB=0,wA+=13,wB+=16.w_A=w_B=0,\qquad w_A^+=\frac13,\qquad w_B^+=\frac16. The evidence supporting zero differs even though every current prediction agrees. The theorems quantify the evidence necessary to reproduce future learning.

Questions:

  1. Memory: the stored encoding of the observed prefix, including all history-dependent parameters, auxiliary arrays, caches and replay data. Fixed history-independent parameters are free. The clock is the known history length, also allowed outside the counted state; the lower bounds compare histories of the same length (§2).

  2. History: the ordered sequence of observations received so far. Regression observations contain a feature and label; attention observations contain a key and value. A continuation appends observations (§2).

  3. Readout: the reference output at a query, without adding an observation. For scalar regression, fh(q)=q⊤wh.f_h(q)=q^\top w_h. Section 2 explicitly distinguishes reading from updating.

  4. Decoder: it may be nonlinear and computationally unrestricted. Only the complete history-to-state encoder must be continuous at each fixed length; decoder continuity is not assumed. Its role in the proofs is precise: identical stored states must produce identical required answers. The continuation-identification argument determines which histories must have distinct states, allowing the dimension lower bound. Section 6 separately treats finite-bit encodings without encoder continuity.

  5. Exact recurrent learner: its encoder, updater and decoder satisfy EN+1(hz)=UN(EN(h),z),DN(EN(h),q)=fh(q)E_{N+1}(hz)=U_N(E_N(h),z),\qquad D_N(E_N(h),q)=f_h(q) for every allowed history, observation and query. Section 2 distinguishes this from the weaker requirement of answering every possible single-observation continuation. Lower bounds for that weaker task also apply to recurrence.

  6. Equal-prediction: two same-length histories give the same current output at every allowed query. This means agreement on the entire current prediction function (§2).

  7. Zero-label history: every observed label is zero. In ridge regression the current predictor is then zero, although the feature second-moment matrix can still vary (§3, immediately after Eq. 1).

  8. DeltaNet: a fast-weight memory updated by the delta rule. Section 3 now gives the update and cites Schlag, Irie and Schmidhuber (2021), Linear Transformers Are Secretly Fast Weight Programmers, and Yang et al. (2024), Parallelizing Linear Transformers with the Delta Rule over Sequence Length. The example specifies the raw recurrence being analyzed; additional learned channels or auxiliary states enter the memory accounting.

Section 4 now explains Eq. (5): Fh(w)=R(w)+∑iρ(xi⊤w−yi).F_h(w)=R(w)+\sum_i\rho(x_i^\top w-y_i). This is the accumulated objective: the first term is a fixed regularization cost, and each summand penalizes a prediction residual. The stated convexity assumptions guarantee a unique reference minimizer. Section 7 similarly defines attention, its weighted-value numerator and its normalization mass.

The revised progression: ridge exposes the missing evidence; general residual learning characterizes it; bounded logistic regression, finite precision and attention examine its consequences. Figure 1 and Section 8 now report an executed synthetic continuation test. We have also reworked pagination and spacing and replaced Section 9 with a connected conclusion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.