acceptodds
Under review as a conference paper at ICLR 2027

When Does Momentum Help Online Associative Memory? A Random-Query Risk Analysis

Abstract

We study online associative memories through their retrieval error on queries that arrive at random times while key–value pairs stream in. The delta rule corrects along the arriving key, while heavy-ball momentum also carries decayed corrections from earlier keys. We ask when this accumulated correction lowers the expected retrieval error, and find that the answer depends first on when the memory updates. When momentum evolves continuously between key changes, we derive leading-order risks in closed form for two nearly collinear keys under Markov access and an exponential query time. From the weak direction, a fixed momentum rule beats every continuous-time delta rule with gain below one. An over-relaxed reflect–project schedule beats that momentum rule for every nonzero initial error, although momentum with large overtakes it from the weak direction. With each family tuned at a fixed key separation, continuous-time momentum beats the best constant gain found only for nearly identical keys (cosine above at every tested ) under reconstruction. For keys, a compatibility matrix that pairs the access modes with the keys' weak directions decides the comparison at small separation. Exact risks on frozen CIFAR-100 and Omniglot features reproduce these effects, and there the tuned delta rule selects a gain above one under reconstruction and below one under the associative query. With one update per token, the comparison reverses: tuned momentum attains lower mean risk than the tuned constant-gain delta rule in every tested synthetic and frozen-feature condition, by up to in normalized reconstruction risk.

Primary area:
learning theory
Keywords:
online associative memory, momentum, delta rule, online learning, heavy-ball momentum, fast weights

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_ryZzOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies different fast-weight update rules. Specifically, it studies the effect of adding momentum to the delta-rule update, as proposed by several recent works. The authors provide a theoretical derivation that models the updates as continuous-time flows. The theory shows that in the 2-key case, sub-unit-gain delta rules cannot reduce the risk below some bound. However, other update rules with larger effective step sizes, such as momentum, can go below this bound. For k>2 keys the best update rule depends on the data itself. Finally, the authors test their theory on a synthetic setup that includes frozen image features.

Critical strengths

The studied problem is valuable, as architecture research provides core contributions to LLM design.

Critical weaknesses
  1. The experiments do not represent a real scenario - the values are hand-crafted as one-hot vectors, the keys are features from a frozen image classifier, and they arrive according to a synthetic schedule. In real-world scenarios keys and values are both projections of the same token v = Wv @ x, k = Wk @ x and their order obeys the natural distribution of the data. To connect the theory to a real setting the authors should perform their experiments on real data taken from trained fast-weight models.

  2. The theory does not cover per-token update rules, which are the rules used in practice, and specifically, the ones used by the models the authors use to motivate their work (Titans, Deltanet). This makes it even harder to connect the theory to actual settings.

Questions for authors

See weaknesses

3 comments

Q1

We thank the reviewer for suggesting experiments on real data from trained fast-weight models. We have added experiments using keys and values extracted from five trained model checkpoints run on real text (WikiText-103). Following our analysis of the strong and weak directions in Section 3, we constructed 359 key–value sets, each containing two key–value pairs generated by one of the five selected checkpoints: OpenRaiser (AdamW and AdamP), Gated DeltaNet (340M and 1.3B), and Qwen3.5-0.8B.

We set different initial memory errors and examined how well the three update rules (P, RP, and H) corrected them. Besides an empty initial memory (W0=0W_0 = 0), we first placed all error energy in the weak direction and then tested initial errors with 1%, 5%, or 10% of their energy in the strong direction and the remainder in the weak direction. We applied P, RP, and H to each initial memory and compared their retrieval risks. The results are shown in the table below (each cell reports P / RP / H; lower is better).

CheckpointW0=0W_0 = 0Weak only1% strong5% strong10% strong
OpenRaiser AdamW0.6489 / 0.6384 / 0.72730.9079 / 0.8932 / 0.88960.8990 / 0.8845 / 0.88410.8634 / 0.8495 / 0.86180.8190 / 0.8057 / 0.8339
OpenRaiser AdamP0.7693 / 0.7568 / 0.80290.9076 / 0.8928 / 0.88930.8987 / 0.8841 / 0.88370.8631 / 0.8491 / 0.86150.8187 / 0.8054 / 0.8337
Gated DeltaNet 340M0.4969 / 0.4888 / 0.63300.9082 / 0.8935 / 0.88990.8993 / 0.8847 / 0.88430.8637 / 0.8497 / 0.86200.8193 / 0.8060 / 0.8341
Gated DeltaNet 1.3B0.7388 / 0.7270 / 0.78440.9093 / 0.8948 / 0.89110.9004 / 0.8860 / 0.88550.8648 / 0.8509 / 0.86310.8202 / 0.8071 / 0.8351
Qwen3.5-0.8B0.4356 / 0.4288 / 0.58980.9137 / 0.8995 / 0.89570.9047 / 0.8907 / 0.89000.8689 / 0.8554 / 0.86710.8241 / 0.8113 / 0.8385
RankingRP < P < HH < RP < PH < RP < PRP < H < PRP < P < H

The results on trained models are consistent with Propositions 3.2 and 3.4 in Section 3: when the initial error lies in the weak direction, the ranking is H < RP < P. In our experiments, as the proportion of error in the strong direction increases, the ranking changes to RP < H < P and then to RP < P < H. We have added these results to Section 5 (page 9), with details in Appendix A.6 (Table 20).

Q2

We believe this is potentially an overlooked point: the per-token setting is already covered in our experiments. The results are reported in Table 1 (page 8) and Appendix A.4.2 (Tables 15–16) of both the initial submission and the revision. The comparison covers three per-token update rules: the delta rule (P, projection), the reflect–project rule (RP), and momentum (H). We also agree with the reviewer’s suggestion that extending the experiments to trained fast-weight models would help validate our theory in practice. Thus, our additional experiments aim to answer two questions: When tokens in real text arrive one by one, which update rule has lower retrieval error? Does the result depend on the gain used for each update?

In our new experiments, we used keys and values extracted from the same five trained checkpoints as in our response to Question 1. For each checkpoint, we recorded the keys and values generated on 100 WikiText documents. We replayed these sequences using the three per-token update rules and measured the memory retrieval error. We compared the fixed learning rate (θ = 1) with a learning rate (θ < 1) based on the mean gate value of the trained model. The results are shown in the table below.

Checkpointθ = 1Rankingθ < 1Ranking
OpenRaiser AdamW0.2653 / 0.5433 / 0.3570P < H < RP0.3735 / 0.3269 / 0.3347RP < H < P
OpenRaiser AdamP0.3357 / 0.6555 / 0.4544P < H < RP0.4758 / 0.4258 / 0.4362RP < H < P
Gated DeltaNet 340M0.4179 / 0.7118 / 0.5411P < H < RP0.4215 / 0.3976 / 0.4034RP < H < P
Gated DeltaNet 1.3B0.4802 / 0.8436 / 0.5812P < H < RP0.4460 / 0.4370 / 0.4369H ≈ RP < P†
Qwen3.5-0.8B0.0987 / 0.1808 / 0.1179P < H < RP0.1050 / 0.0974 / 0.0993RP < H < P
Each cell reports P / RP / H; lower is better. θ is the learning rate defined in Section 2.1.
† For Gated DeltaNet 1.3B, H and RP perform similarly.

With θ = 1, the ranking is P < H < RP for all five checkpoints. With θ < 1, the ranking changes to RP < H < P for four of the five checkpoints: RP attains the lowest risk, followed by H and then P. This is consistent with Theorem 3.6, which shows that RP can attain lower retrieval risk than H. We have added these results to Section 5 (paragraph “Trained checkpoints”, page 9), with further details in Appendix A.7 (Table 21).

Reviewer_ryZzOpenReview ↗

Response to rebuttal

I thank the authors for their rebuttal.

Adding keys and values sampled from trained fast-weight models' geometry narrows the theory-experiment gap. However, manually setting the energy ratio does not reflect real-world statistics. Why not report results weighted by a histogram of the energy ratio measured from the actual memory states of the trained models? Also, token order should not follow a synthetic access process but should be taken directly from the natural text.

Regarding Q2, my concern was that the theory, not the experiments, does not cover per-token updates. This remains unresolved.

Overall, the new version improves over the previous one, yet my main concerns remain, which I believe are too substantial to be addressed within this revision. I will keep my score.

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

The paper concerns classical matrix-based associative memory, which has been extensively studied for more than 30 years. The underlying memory model, delta-rule learning, and related adaptive update mechanisms are well-established topics in the neural network and adaptive filtering literature. Unfortunately, many of the early foundational works in this area are not adequately discussed or cited. The novelty lies mainly in the random-query risk formulation. Therefore, it is unclear whether the paper provides substantially new results or mainly examines well-known mechanisms in a modern machine learning context. Many related results already exist in the literature, including forgetting update rules, momentum-based updates, and other memory update mechanisms. The paper compares different update mechanisms under a common framework, although these mechanisms are well established in matrix-based associative memory. This comparison helps clarify the conditions under which each method performs better.

Critical strengths

The paper compares different update mechanisms under a common framework, although these mechanisms are well established in matrix-based associative memory. This comparison helps clarify the conditions under which each method performs better.

Critical weaknesses

The underlying model is a classical matrix-based associative memory without feedback. Such memory structures and update rules have been extensively studied for several decades in the associative memory and adaptive filtering literature. However, the paper does not sufficiently discuss this prior work.

Many related mechanisms, such as forgetting update rules, momentum updates, normalized updates, and adaptive learning schemes, already exist in the literature. As a result, the novelty of the proposed analysis is clearly limited. Although the motivation comes from modern memory architectures, the main analysis is conducted using a highly simplified memory model, namely, a matrix-based associative memory. It is unclear how well the theoretical conclusions extend to recurrent associative memories.

The paper mainly studies retrieval behavior under specific assumptions and settings. It assumes that the query key is noiseless during recall and does not study recall using noisy or partially observed keys. In practice, the inputs may be noisy or contain outliers. Robustness to such inputs is an important property of associative memory.

Questions for authors

Why does the paper not consider recurrent associative memory and analyze its attraction basins? Such an analysis would help evaluate its error-correction ability during recall.

Classical work by Robert J. Marks and others studied the recall of real-valued signals from partial inputs using alternating projections onto convex sets (POCS). Such methods are closely related to autoassociative pattern completion. What happens if recurrence is included in the recall process?

The memory matrix is only one component of the overall system. The paper does not clearly explain the structure of the complete system. A diagram of the complete system should be included.

3 comments

Q1

We thank the reviewer for this suggestion. We found this idea insightful, and we have extended our experiments to study recurrent recall and attraction for all three update rules. We concluded that this analysis does help evaluate the error-correction ability of each rule during recall. The experimental details are given below.

Recurrent recall. We encoded 192 Omniglot images as representations and divided them into 48 groups of four. For each group, we constructed three memory matrices using the update rules defined in Section 2: projection (P), reflect–project (RP), and momentum (H). We considered two types of queries: Q₁, obtained by masking half of the features, and Q₂, obtained by additionally perturbing one randomly selected observed feature. For each query, we compared single-step retrieval with 64 steps of recurrent retrieval. When each image had been presented at least 200 times during the memory updates, recurrent retrieval improved accuracy for both query types, as shown in the table below. Single and Recurrent denote single-step and recurrent retrieval accuracy, respectively. Correct denotes the proportion of all queries that changed from incorrect to correct, and Incorrect denotes the proportion that changed from correct to incorrect. Numerical failures are counted as incorrect.

RuleQuerySingle ↑Recurrent ↑Correct ↑Incorrect ↓
PQ₁0.39240.50170.23870.1293
PQ₂0.38890.46440.20660.1311
RPQ₁0.35590.46350.23960.1319
RPQ₂0.34640.41670.19530.1250
HQ₁0.30470.46270.27780.1198
HQ₂0.30730.37330.20050.1345

Notably, recurrent retrieval corrected some errors but also changed some correct predictions to incorrect ones. With missing features alone (Q₁), momentum (H) had the largest increase in accuracy from recurrent retrieval in this experiment, at 0.158. When features were additionally perturbed (Q₂), its increase dropped to 0.066, below the increases for projection (P) and reflect–project (RP). These results extend the comparison in Section 5 to recurrent recall. Further details are provided in Appendix A.8 (Table 22).

Attraction analysis. Masking half of the features as in Q₁, we classified each query according to whether the recurrent state met a finite-step convergence criterion (C) and whether it successfully reconstructed the missing features (S). Reconstruction was considered successful when the relative error on the missing features was at most 0.1. In the table, TT means converged and successful, TF converged but unsuccessful, FT not converged but successful, and FF neither converged nor successful.

RuleTTTFFTFF
P0.87370.00040.12500.0009
RP0.85070.00820.13800.0030
H0.65580.08810.13980.1163

P and RP successfully reconstructed the missing features and met the convergence criterion for 0.8737 and 0.8507 of the queries, respectively, compared with 0.6558 for H. H also had a larger proportion of queries that met the convergence criterion but failed to reconstruct the target features: 0.0881, compared with 0.0004 for P and 0.0082 for RP. Under this experimental setting, P and RP therefore showed more reliable feature recovery than H. Further results are reported in Appendix A.8 (Table 23).

We believe these additional experiments improve the rigor and significance of our work, and we thank the reviewer again for this constructive suggestion. We would be glad to discuss these ideas further with the reviewer if we have the chance.

Q2

We thank the reviewer for reminding us of the work of Marks et al. on recovering signals from partial inputs. We have added these references and discussed their connection to our recurrent recall in Appendix F (page 72) and Appendix A.8. Following this suggestion, we also tested recurrent recall, as described in our response to Question 1.

As shown in the experiment above, when each image had been presented at least 200 times during the memory updates, recurrent retrieval improved accuracy for all three rules. At each step, we kept the observed features fixed, completed the missing features using the memory output and the stored image representations, and then read the memory again.

We find that the improvement from recurrent retrieval decreases for all three update rules when an observed feature is additionally perturbed (Q₂), compared with the query with missing features alone (Q₁). The ranking of the rules by improvement also changes: momentum (H) has the largest gain on Q₁, whereas projection (P) has the largest gain on Q₂. This is consistent with our finding in Section 5 (paragraph “Query type”, page 8) that changing the retrieval query can also change the ranking of the update rules by retrieval risk.

Q3

We thank the reviewer for this suggestion. We have added Figure 1 (page 2) to the paper to illustrate the overall system, including memory updates, retrieval, and risk analysis for the three update rules. It also shows the four factors (query type, key geometry, access order, and elapsed time) that can reverse the retrieval risk ranking of the three update rules (P, RP, and H).

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

This paper compares the retrieval risks of delta-rule and momentum updates for online associative memory at a random query time. The authors compare P and RP with the momentum algorithm under a theoretical model and point out that the ranking is affected by the query, key geometry, access process, elapsed time, and update protocol.

Critical strengths

The role of momentum in online associative memory is an interesting question. The paper provides explicit risk bounds with detailed mathematical analysis.

Critical weaknesses
  1. The paper presents many conditional comparisons but does not sufficiently synthesize them into clear takeaway messages. Section 3 studies a specialized two-key model, and its strict risk ordering follows directly from the inequality between the leading-order coefficients in Eq. (10). Although deriving these coefficients is a theoretical contribution, the paper does not sufficiently explain what determines the ordering at a higher level. Section 4 extends the analysis to the K-key setting, but does not sufficiently translate the mathematical conditions on MM into interpretable conditions in practical settings. In particular, the abstract and introduction emphasize that the update protocol is critical (momentum evolves as a flow between key changes while the delta rule updates at key changes). However, the main theoretical analysis does not provide a corresponding framework for comparing the update protocols. The authors should identify the main insights and reorganize the paper around them.

  2. Key update rules are used in the introduction before they are clearly explained. In particular, P, RP, and H(1,30)H(1,30) appear without clear specifications. Moreover, the motivation for choosing H(1,30)H(1,30) as a central comparator is also unclear. This makes the comparisons and claims in the introduction confusing.

Questions for authors

See weakness

2 comments

Q1

We thank the reviewer for recognizing the theoretical contribution and for the constructive suggestions. We agree that the explanation can be improved, and we have strengthened it: the paper is now organized around three takeaways (Section 1, page 3), with a new overview figure (Figure 1) showing the theoretical framework.

Three takeaways from our study of update rules in online associative memory:

  • Corollary 3.3 shows that momentum (H) attains lower retrieval risk than every delta rule with learning rate θ ∈ [0, 1], and Theorem 3.6 proves that with θ > 1, reflect–project (RP) can attain lower retrieval risk than momentum.
  • Proposition 4.2 gives a comparison criterion through the compatibility matrix M, and Section 5 shows that the query type, key geometry, access order, and elapsed time can each reverse the risk ranking of the update rules (projection P, RP, and H).
  • Table 1 shows that momentum attains lower retrieval risk when the memory updates at every token. However, when the same key arrives repeatedly and the memory keeps updating on it, the delta rule attains lower retrieval risk.

What determines the ordering? We discuss this in Section 3, in the paragraph after Theorem 3.6 (page 6), which draws on Theorem 3.1, Corollary 3.3, and Proposition 3.4. In summary, the ordering depends on two things:

  • The learning rate of the update rule. A delta rule with learning rate in (0, 1) can only approach the performance of projection (P). Momentum (H) acts like a learning rate above 1 and can outperform P. Reflect–project (RP), which uses a learning rate of 2 at reflections, can attain the lowest retrieval risk under condition (10) of Theorem 3.6.
  • The timing of the query. The benefit of RP is delayed, because it completes one correction over two key changes. Therefore, RP attains lower retrieval risk than P only when key changes are frequent relative to queries.

How to interpret the condition on M? When a memory stores many similar keys, the better update rule depends on the key geometry and the key access order (Section 4, page 7). If the stream alternates rapidly among keys that differ in their weak directions, RP can attain lower retrieval risk. If it stays within one group of keys before moving to another, momentum (H) can attain lower retrieval risk along the direction that separates the groups. The matrix M captures this relationship, and Figure 3c illustrates it on Omniglot keys.

How we compare update rules. We have added Figure 1 to provide an overview of our comparison framework. We evaluate each rule using the same retrieval-risk objective, defined in Eq. (5) of Section 2.2. We use this objective to compare updates at key changes in Sections 3–4, and per-step and per-token updates in Section 5 (Table 1) and Appendix A.4.

Q2

We thank the reviewer for pointing this out. We have revised the introduction so that each update rule is defined before it is used, and we now explain the choice of H(1, 30) where it is introduced.

Definitions of P, RP, and H. In the revised introduction (page 2), the three rules are now specified before any comparison, together with the overview in Figure 1:

  • Projection (P) applies the delta rule with learning rate θ = 1 at every key change, removing the error along the active key.
  • Reflect–project (RP) alternates θ = 2 (reflection) and θ = 1 (projection) at successive key changes. It carries no momentum and isolates the effect of a learning rate above 1.
  • Momentum (H) is the continuous-time heavy-ball counterpart of the discrete momentum update in Eq. (1), and it evolves between key changes (Definition 2.3).

They are formally defined in Section 2: the discrete delta and momentum updates in Section 2.1, the momentum rule H(α, β) in Definition 2.3, and RP in Construction 2.1.

Why H(1, 30). We introduce H(1, 30) right after Theorem 3.6 (page 5), together with the reason for choosing it. With (α, β) = (1, 30), H satisfies condition (10) of Theorem 3.6 on ρ ∈ [2, 5], so it attains lower retrieval risk than every continuous-time delta rule with learning rate θ < 1. This range includes the switching rate ρ = 4 used in most experiments in Section 5. H(1, 30) is therefore a strong momentum comparator: it already beats every continuous-time delta rule with θ < 1, which makes the comparison with RP meaningful. H(1, 30) is used only in the fixed-comparator experiments. In Table 1 and Appendices A.3 and A.4, the hyperparameters of momentum are tuned on validation data instead.

We believe these changes make the comparisons and claims in the introduction easier to follow, and we thank the reviewer again for this thoughtful suggestion.

Comments on the paper

1 comment

We appreciate all reviewers’ time on our paper. Thanks for recognizing that our paper (1) studies an interesting question, (2) clarifies the theoretical conditions of update mechanisms, and (3) is valuable for LLM design. Following the reviewers’ suggestions, we have added more experiments and revised the paper. We summarize the main improvements as follows:

  1. Provided an overview figure to clearly illustrate our theoretical framework and key findings (sczH, rjLS);
  2. Added more analysis of recurrent memory recall and its attraction basins (rjLS);
  3. Extended the experiments to practical settings with five trained fast-weight models (ryZz).

We have uploaded the revised paper, in which all changes made in response to the reviewers’ suggestions are highlighted in green. The locations of the main revisions are listed below.

  1. Overview figure of the framework (Figure 1, page 2).
  2. Introduction reorganized around three takeaways, with P, RP, and H defined before use (pages 2–3).
  3. Explanation of what determines the ordering, and of the choice of H(1, 30) (Section 3, pages 5–6).
  4. Interpretation of the criterion on M (Section 4, page 7).
  5. Experiments on five trained fast-weight models (Section 5, page 9; Appendices A.6–A.7).
  6. Recurrent recall and attraction analysis (Appendix A.8).
  7. Classical work on alternating projections and partial recall (Appendix F, page 72).

If you feel that our responses have addressed your concerns, we would be grateful if you would consider updating your rating. Please feel free to leave further comments at any time. Even if we are unable to reply after the discussion deadline, we will read every comment carefully and use it to further advance our research.

Thank you again for your time and for helping us improve this paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.