acceptodds
Under review as a conference paper at ICLR 2027

Test-time Memory From The Online Learning Perspective: Associative Prediction Game and Regret Optimality

Abstract

Test-time training (TTT) layers and Delta-style memories learn key-value (KV) associations as a sequence arrives. We study which update rules learn these association well and when the resulting memory can answer queries that differ from its update keys. We measure learning through regret, which is the extra prediction loss relative to a fixed comparison map. For exact recursive least squares (RLS), we connect prediction regret and retrieval error through the same regularized key covariance. Specifically, ordinary RLS has logarithmic regret when key norms and prediction residuals remain uniformly bounded. A classical Vovk–Azoury–Warmuth (VAW) readout achieves the optimal worst-case rate in the stated bounded prediction game without the residual condition. A separate construction shows that constant-step Delta can incur much larger regret. Our retrieval guarantees identify additional conditions on query coverage and how values and noise are generated. Furthermore, we analyze approximate updates and memories that forget old observations. Extensive experiments on WikiText streams show that RLS performs better in the evaluated stable settings, while resetting and discounting old information helps against controlled drifts. Meanwhile, a LongBench-v2 setting shows that selected Delta reconstructs native attention slightly better, while RLS performs better when attention is restricted to the stored context. These findings distinguish guarantees for learning KV associations from performance on query-time reconstruction.

Primary area:
learning theory
Keywords:
Test-time training, associative memory, online learning, regret minimization, recursive least squares, DeltaNet, fast-weight memory

Reviews

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

This paper studies the online learning and retrieval properties of TTT layers and Delta-style memories. It establishes regret and retrieval guarantees for RLS-based methods, identifies limitations of constant-step Delta updates, and experimentally evaluates their performance under stable and drifting settings.

Critical strengths

Connecting TTT with online learning is a natural and promising direction. I find the formulation of TTT from an online learning perspective is interesting and potentially valuable for developing a deeper theoretical understanding of TTT mechanisms.

Critical weaknesses

However, I have several concerns regarding the paper's formulation and contributions:

  1. The paper lacks sufficient background and a clear problem formulation. I suggest introducing the problem setup and existing update rules (e.g., Delta-rule memories) early in the paper.

  2. Theorems 1–3 appear incremental, with relatively straightforward proofs. It remains unclear whether the TTT setting introduces new theoretical challenges or requires techniques beyond standard online learning analysis.

  3. The experiments focus primarily on RLS and Delta-style updates, leaving the evaluation rather narrow. I encourage comparisons with a broader range of fast-weight methods [1, 2]. Additionally, some appendix experiments, such as FD-sketched RLS, seem peripheral to the paper's main contributions and add limited empirical value.

[1] Schlag, I., Irie, K., and Schmidhuber, J. Linear Transformers Are Secretly Fast Weight Programmers. ICML 2021.

[2] Feng, G., Luo, S., Hua, K., et al. In-Place Test-Time Training. ICLR 2026

Questions for authors

See Weaknesses.

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

This paper studies online associative memory through online linear regression view. It analyzes the regret properties of delta-rule updates (SGD), RLS, and VAW prediction, and establishes connections between binding regret, query retrieval error, and covariance structure. The analysis is extended to approximate updates and non-stationary associations. Experiments examine fixed-feature wikitext streams, synthetic drifting associations, and attention reconstruction using frozen pretrained Transformer features.

Critical strengths

The paper provides a systematic analysis of distinct aspects of associative memory, especially the distinction between online binding prediction, query-time retrieval, and adaptation to changing associations. The theoretical assumptions are generally explicit, and the authors provide detailed derivations and diagnostic experiments. The discussion also acknowledges important limitations rather than claiming that RLS universally outperforms Delta-based updates.

Critical weaknesses
  1. Limited theoretical novelty relative to established online learning and associative memory research.

The central theoretical results largely build on established online regression theory. Logarithmic regret bounds for online ridge regression and the VAW predictor are classical results [1, 2]. Covariance-dependent prediction error bounds follow established statistical estimation techniques [3]. The paper provides specialized results for constant step Delta, query retrieval, approximation, and forgetting. However, these appear largely to extend existing principles within a restricted linear regression setting. It remains unclear what fundamentally new theoretical insight or prediction emerges beyond the established framework, particularly for practical neural memory architectures.

  1. Insufficient experimental scope to support theoretical contribution.

The experiments primarily examine simplified regression settings rather than learned neural memory systems. The wikitext experiments use fixed random key-value representations and a squared-error objective directly aligned with the RLS formulation. The synthetic drift experiments use controlled linear target changes, including oracle reset boundaries. These are useful diagnostics but provide limited independent evidence of the theory's relevance to realistic memory dynamics.

The pretrained model experiment uses frozen features from a single Transformer checkpoint, with attention-output reconstruction rather than downstream task performance as its primary metric. Its results are also target-dependent, with Delta slightly outperforming RLS on native-attention reconstruction. This limited experimental setting is not enough to establish whether the proposed theoretical quantities predict retrieval behavior across varying sequence lengths, conditioning regimes, or learned feature representations. Consequently, the experiments provide limited evidence that the theoretical analysis explains practical neural memory performance beyond conventional regression behavior.

[1] Vovk, 2001. Competitive On-line Statistics.

[2] Azoury & Warmuth, 2001. Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions.

[3] Abbasi-Yadkori et al., 2011. Improved Algorithms for Linear Stochastic Bandits.

Questions for authors
  1. Could the authors clarify which theoretical conclusions are genuinely new relative to classical online regression and existing test-time regression frameworks? In particular, what nontrivial insight or prediction follows from the proposed analysis that cannot be obtained through a direct application of established results?

  2. Could the authors provide more direct experimental validation of the theoretical predictions?

  • Please vary sequence length, effective key-covariance rank and conditioning, and the alignment between update keys and retrieval queries. Measure empirical regret, cumulative query leverage, and retrieval error against their theoretical bounds, including the predicted dependence on sequence length and effective rank. This would clarify whether the bounds actually explains observed memory behavior rather than just holding worst-case guarantees.
  • Please evaluate delta-based and RLS/preconditioned memory updates within at least one end-to-end trained recurrent or TTT-style sequence model, under matched training and computational budgets. Measure downstream associative recall and long-context retrieval, alongside memory cost and runtime. This would establish whether the theoretical distinctions translate into meaningful improvements in practical neural sequence modeling, beyond fixed-feature regression and attention reconstruction.
Reviewer_iMNCOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies linear associative memory updates from an online learning perspective. It compares the prediction regret of Delta and RLS-based methods and analyzes RLS retrieval error under query coverage conditions. It also considers approximate updates and changing targets. Experiments compare memory updates on fixed-feature KV streams and in attention reconstruction using frozen-model features.

Critical strengths

The distinction between binding prediction and query retrieval is relevant. The paper covers a broad range of theoretical aspects of associative memory.

Critical weaknesses
  1. The paper reads more like a collection of results than a paper with a clear central contribution. It gives a minimax result and a separation between constant-step Delta and VAW, but does not clearly explain which parts of the arguments are new. Several other results follow directly from standard arguments, such as Eq. (14) from the noiseless ridge error identity, Eq. (18) from an excess-loss decomposition, and Eq. (19) from a scalar example with a single change point. I also find it hard to see what new insight comes from putting the prediction, retrieval, approximation, and forgetting analyses together.

  2. The experimental results need more explanation. Experiment 2 shows that forgetting can help or hurt, but the claimed match between the forgetting structure and the drift is not precisely characterized. It is therefore difficult to tell when a particular forgetting rule should help. In Section 7.2, the ranking of RLS and Delta reverses between native and context-restricted attention reconstruction. The paper explains the difference in available information, but does not explain why this changes the ranking. The retrieval bounds also do not directly apply to softmax reconstruction, so it remains unclear how this experiment supports the retrieval analysis.

Questions for authors

See weakness

Comments on the paper

1 comment
AuthorsOpenReview ↗

Discussion deadline approaching

With the discussion deadline approaching today, we thank Reviewer fFsA for your response and kindly invite reviewers iMNC and FFAw to share your feedback on our rebuttal. We would like to know if any concern remains, or if any of you would consider updating your assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.