Pith. sign in

REVIEW 3 major objections 5 minor 5 cited by

Understanding Transformer from the Perspective of Associative Memory

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Transformers are associative memories; a delta-rule variant with softmax retrieval provably tracks n states using O(log n)-dimensional keys, exceeding the TC0 expressivity of standard Transformers.

desk verdict A clever DeltaFormer construction and useful SNR heuristics, marred by an expressivity claim that is a non-sequitur. read the letter →

arxiv 2505.19488 v1 pith:OPJ6GYGW submitted 2025-05-26 cs.LG cs.AI

Shu Zhong , Mingyu Xu , Tenglong Ao , Guang Shi This is my paper · ORCID
classification cs.LGcs.AI MSC 68T07
keywords associativememoryTransformerretrievalSNRattentionkerneldeltaruleexpressivitycircuitcomplexityin-contextlearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Viewing the Transformer as an associative memory, this paper develops a quantitative theory of memory capacity and memory update. It introduces a retrieval signal-to-noise ratio (SNR) to show why the exponential kernel of softmax attention far outperforms linear attention, and it interprets feed-forward networks as ReLU-kernel associative memories whose lower precision buys superposition and knowledge density. On the update side, it unifies linear attention, DeltaNet, gated attention, and softmax attention as instances of one recurrent memory update $S_t = A_t S_{t-1} B_t + C_t$ with an associated optimization objective. From this unification it proposes DeltaFormer, a model that adds the delta rule to softmax attention, and proves that a single DeltaFormer layer can track the exchange of n elements using $d = O(\log n)$-dimensional keys, placing its expressivity beyond $TC^0$ and reaching $NC^1$. It further argues that as context length grows to infinity, the softmax-attention memory-update objective carries a $1/t$ factor that drives gradients to zero, so infinite-context in-context learning degrades.

What carries the argument

The load-bearing object is the recurrent associative-memory update $S_t = S_{t-1} + u_t \phi(k_t)^\top$, where the new write vector $u_t$ is obtained by removing from $v_t$ the information already stored under similar keys: $u_t = \alpha_t v_t - \beta_t \sum_{i<t} \kappa_1(k_i, w_t) u_i$, and reads use a second kernel $\kappa_2$. The proof machinery is Theorem 1, the State Exchange theorem: with keys on the unit sphere satisfying near-orthogonality ($d = O(\log n)$) and a rounding function $f$ that is exact on neighborhoods of $\{-1, 0, 1, 2\}$, writing $k_t = k_{t_1} - k_{t_2}$ with $v_t = 0$ swaps the stored values of keys $t_1$ and $t_2$; induction over arbitrarily many steps shows all $n$ states remain traceable. For capacity, the central identity is the inverse-SNR formula $\mathrm{SNR}^{-1} \approx N\, \mathbb{E}[\kappa^2(k_j, k_i)] / \kappa^2(k_i, k_i)$, whose exponential-kernel evaluation gives $N / \exp(2(\tau - 1) d_k / \tau^2)$, implying softmax attention needs only $O(\log^2 N)$ dimensions for reliable recall.

What would settle it

Train a single-layer DeltaFormer end-to-end on the swap-tracking task (n = 5 elements, 16 swaps) from random initialization and token embeddings, with key dimension d = 3-4 and no hand-set orthogonal keys; if the model cannot reach 100% accuracy while a hand-wired construction with orthogonal keys does, then the theorem's assumptions are not satisfied by learned representations. Alternatively, test tracking n = 128 elements with learned keys at d = 7; failure there would show the $O(\log n)$ dimension requirement is not learnable.

Watch

Extended reading notes

Core claim

The paper's central claim is that the Transformer architecture is best understood as a form of associative memory, and that this view yields both explanation and new capability. Attention layers form short-term contextual memories through a kernel-weighted outer-product update, while FFNs form persistent memories through a ReLU-like kernel. The paper proves, in Section 2.2.1 and Appendix E, that an architecture called DeltaFormer, defined by the recurrence $u_t = \alpha_t v_t - \beta_t \sum_{i<t} \kappa_1(k_i, w_t) u_i$ and readout $o_t = \sum_i \kappa_2(k_i, q_t) u_i$, can track the positions of n swapped elements for arbitrarily many exchange steps using keys of dimension $d = O(\log n)$, provided the keys are nearly orthogonal and a rounding-like function maps neighborhoods of $\{-1, 0, 1, 2\}$ to the exact integers. Since a constant-depth standard Transformer is known to lie in $TC^0$ and arbitrary-length swaps are beyond it, the paper concludes DeltaFormer reaches $NC^1$ expressivity. The same framework yields a negative result: for softmax attention the memory-update objective carries a $1/t$ factor, so in the infinite-context limit gradients vanish, memory stops updating, and in-context learning degrades.

Load-bearing premise

The expressivity result assumes the model can realize a near-orthogonal key set with $d = O(\log n)$ and a rounding-like function that exactly maps neighborhoods of $\{-1, 0, 1, 2\}$ to the correct integers, and that learned projection matrices can produce the constructed keys $k_t = k_{t_1} - k_{t_2}$ and zero values; if gradient descent cannot discover this construction, the claimed separation from $TC^0$ does not hold in practice.

Editorial extensions

If this is right

  • A single-layer DeltaFormer can provably track $n$ elements with $d = O(\log n)$-dimensional keys, a capability beyond the $TC^0$ class of constant-depth Transformers; if the proof's constructions are realizable by learning, this gives a concrete architecture with expressivity reaching $NC^1$.
  • The inverse-SNR analysis predicts that softmax attention maintains reliable retrieval when key dimension scales as $O(\log^2 N)$, whereas linear attention needs $O(N)$; this quantitatively explains why linear-attention models struggle at long-context precise retrieval and where to set head counts and dimensionality.
  • Interpreting FFNs as ReLU-kernel associative memories explains polysemanticity as deliberate superposition, predicts that higher-precision kernels such as SoLU trade knowledge density for monosemanticity, and licenses transferring design elements like multihead, sparsity, and gating between attention and FFN.
  • In the infinite-context limit, the softmax-attention update objective carries a factor $1/t$, so memory updates stall and in-context learning degrades; the paper argues that multi-head structure, gating, memory decay, and cross-layer fluctuations can mitigate the convergence to a fixed memory.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension: if DeltaFormer's advantage depends on learned keys realizing the near-orthogonal construction, then on tasks with structured, non-orthogonal embeddings (such as natural-language tokens) the advantage should shrink; experiments varying key dimension and orthogonality would reveal the practical scope of the $TC^0$ separation.
  • The SNR framework suggests a direct design experiment: sweep the temperature $\tau$ of the attention kernel and the slope of FFN activations while measuring both a retrieval-precision metric and a knowledge-density metric; the framework predicts a monotone tradeoff curve.
  • The memory-convergence argument for single-head DeltaNet (memory converging to $S^* = W_v W_k^{-1}$) implies a concrete failure mode: a single-head linear recurrent model should show degrading in-context learning on longer sequences, while multi-head models should not; this is testable in a controlled synthetic ICL benchmark.
  • The matrix-inverse view $u = (I + A)^{-1}v$ suggests DeltaFormer naturally computes graph reachability; extending the paper's 32-node DAG experiments to larger graphs and measuring length extrapolation would test whether the expressivity advantage persists at scale.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes that Transformer components—self-attention and FFNs—can be understood as associative memories, and it develops this view along two axes: memory capacity and memory update. For capacity, it introduces an inverse SNR metric under i.i.d. Gaussian keys/values and uses a kernel perspective to argue that the softmax/exponential kernel offers much higher retrieval precision than linear or ReLU kernels. For update, it presents a general recurrent form S_t = A_t S_{t-1} B_t + C_t and constructs matching optimization objectives, then interprets linear attention, DeltaNet, gated attention, and softmax attention as special cases. This leads to a new model, DeltaFormer, which combines softmax-style kernels with a delta-rule update. The paper claims that DeltaFormer can track the exchange of n elements and therefore 'surpasses TC0 and theoretically reaches NC1.' It also argues that infinite-context in-context learning may degrade because the memory update objective shrinks as t grows. Experiments include a GPT-2 head-count study, swap-tracking tasks, a DAG reachability task, and stress tests with hand-set orthogonal keys.

Significance. The paper is thought-provoking and clearly written in many places. Its strongest assets are the concrete DeltaFormer proposal (Eqs. 41–42), the reproducible toy experiments and code in Appendix E.4, and the generally honest labeling of exploratory claims. The SNR analysis in Section 2.1 offers a useful heuristic for kernel design and makes falsifiable predictions about dimension scaling, temperature, and multi-head trade-offs. If the expressivity claim were established, the result would be significant for the theory of recurrent memory architectures, since it would show a concrete architecture combining softmax retrieval with delta-rule writes can track states with O(log n)-dimensional keys. However, as it stands, the paper's central separation claim is not supported, and several idealizations are unvalidated; the contribution is best viewed as a position paper with preliminary evidence rather than a formal proof of new complexity-theoretic results.

major comments (3)
  1. [Section 2.2.1, 'Model Expressivity' paragraph after Eq. (43)] The statement that DeltaFormer 'surpasses TC0 and theoretically reaches NC1' does not follow from Theorem 1. Theorem 1 in Appendix E is an upper bound: it constructs a DeltaFormer recurrence that can track n elements under specific assumptions. It contains no lower bound showing that the tracking problem is outside TC0. Since separating TC0 from NC1 is an open problem in circuit complexity, and tracking n elements (iterated permutation composition, e.g., S5) is NC1-complete under AC0 reductions, the claimed separation would imply a major open result. This claim must be removed or supported by a matching lower-bound argument.
  2. [Appendix E, Assumptions 1–2 and E.2; Section 3.2 stress test] The construction in Theorem 1 requires d = O(log n) near-orthogonal keys, a rounding-like function f that is constant on neighborhoods of {-1, 0, 1, 2}, and hand-set assignments k_t = k_{t1} - k_{t2} and v_t = 0. The experiments in Figure 5 fix orthogonal keys and train only the readout, so they do not verify that learned projections W_k and W_v can realize these assignments. The expressivity conclusion is therefore conditional on an unverified representational assumption. Please either prove realizability by the model's learned projections or state the claim as conditional.
  3. [Section 2.1.1, Eq. (13), and Appendix A] The inverse-SNR formulas are derived under i.i.d. Gaussian keys and values and by omitting the softmax denominator (Eq. 3 states 'we ignore the normalization term'). These assumptions are not validated for trained transformers, where keys are learned and the normalization term affects retrieval. Consequently, the abstract's claim that the analysis 'mathematically reveals why Softmax Attention is so effective' overstates what is proven. I recommend framing this as an analysis under idealized assumptions and adding empirical validation of the predicted scaling behavior.
minor comments (5)
  1. [Page 3, footnote 1] The paper describes itself as 'a blog-style sharing' rather than a formal research paper, yet it makes formal theorem claims. Please reconcile this framing with the journal format and ensure all technical claims receive the same rigor as a standard submission.
  2. [Section 2.2.1 and Theorem 1] The symbol k_t is used both for the current key at time t and for the constructed difference k_{t1} - k_{t2} in the proof. Using different notation (e.g., p_t for the difference key) would improve readability.
  3. [Appendix A, SoLU derivation] The final expression SNR^{-1}_SoLU ≈ 5N/(d_k exp(2√d_k)) drops the constant exp(2) that appears when substituting τ = √d_k into exp(-2(τ - 1)); state explicitly that O(1) constants are omitted.
  4. [Section 3.2, Figure 4 caption] The caption says '⌊·⌋ means round to two decimal,' but the code in Appendix E.4 uses x.round(), which rounds to the nearest integer. Please align the description with the implementation.
  5. [Table 2] The sentence 'Both any element of λ and η ∈ (0, 1)' is ungrammatical; it should be 'Each element of λ and η lies in (0, 1).'

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: SNR and update-unification derivations are self-contained; the TC0/NC1 separation is a logical gap, not a circular reduction.

full rationale

I walked the paper's derivation chain and found no step where a prediction or first-principles result is equivalent to its inputs by construction. The SNR formulas (Eqs. 7, 13, 15, 17) are derived from explicit Gaussian moment-generating-function calculations and do not presuppose the conclusions they are used to explain. The update-objective unification in Table 2 is explicitly a construction: Appendix B.1 states that the aim is to construct L_t such that S_t = S_{t-1} − ∂L/∂S, and the table entries are obtained by substituting (A_t, B_t, C_t) into that constructed potential. This is a transparent post-hoc description, not a fitted parameter renamed as a prediction, so it does not qualify as a circular step under the rules of this review. Theorem 1 is an upper-bound construction with stated assumptions (near-orthogonal keys and a rounding-like f); it does not smuggle in its conclusion. The claim that DeltaFormer 'surpasses TC0 and theoretically reaches NC1' is invalid as an inference because it would require a lower bound showing the tracking task is outside TC0, which the paper does not provide and which would settle the open TC0-versus-NC1 question; however, invalidity is a correctness risk, not circularity. The infinite-context ICL argument follows algebraically from the 1/t factor in the softmax normalization and the constructed objective, so it is a model-derived consequence rather than a renamed input. The only self-citation I found, [46], is used as empirical support for dimension scaling and is not load-bearing: the SNR derivation stands independently of it. The paper's own footnote that it is a 'blog-style sharing' lowers the strength of the claims but does not change the circularity analysis. Score 2 reflects the minor non-load-bearing self-citation and the purely definitional nature of the Table 2 objectives, with no central circularity.

Assumptions & free parameters 2 free parameters · 6 assumptions · 2 invented entities

The accounting shows that the paper's central claims rest on strong distributional assumptions (Gaussian i.i.d. keys, omitted softmax normalization, fixed key distribution for the law of large numbers), a standard packing bound, and an ad hoc rounding function introduced to make the expressivity proof work. The DeltaFormer model and the rounding construct are the two new entities, and neither has independent evidence outside the paper's own toy experiments.

free parameters (2)
  • Temperature tau for exp and SoLU kernels = tau = sqrt(d_k), chosen by hand for scaling
    The temperature is introduced in Section 2.1.1 and Appendix A; the SNR formulas and the O(log^2 N) capacity conclusion depend on the choice tau = sqrt(d_k) to keep dot products O(1).
  • GQA interpolation weights a_1..a_4 for approximating the rounding function f = Not numerically fixed; constrained to satisfy sum a_j exp(jx) = x for x in {-1, 0, 1, 2}
    Appendix E.2 states that with wt^j = j kt, one can set a_1..a_4 so that the combination interpolates the four points exactly; these coefficients are fitted by construction to make the expressivity argument work.
assumptions (6)
  • domain assumption Keys and values are i.i.d. standard Gaussian in the SNR analysis (Appendix A).
    This assumption underlies Eqs. 7, 13, 15, and 17 and all capacity conclusions; real learned keys in Transformers are neither i.i.d. nor Gaussian.
  • domain assumption The softmax normalization term is omitted in the kernel SNR derivation.
    Footnote 4 in Section 2.1.1 states the normalization is omitted because it does not affect the inverse SNR, but in real softmax attention the denominator changes the effective kernel and the claim is not proven.
  • domain assumption Law of large numbers: sum_{j=1}^t exp(qt^T kj) is approximately t c(qt) for large t, with keys drawn i.i.d. from a fixed distribution.
    Used in Appendix B.2 to derive the 1/t scaling for softmax attention and the gradient-vanishing conclusion for infinite context; fails if keys are sequence-dependent or nonstationary during in-context learning.
  • standard math Near-orthogonal packing: there exist n unit vectors in R^d with pairwise inner products bounded by epsilon < 1/8 whenever d = O(log n).
    Assumption 1 of Theorem 1 (Appendix E) requires such keys; the paper cites Zhao's probabilistic method, which provides the packing bound.
  • ad hoc to paper A rounding-like function f exists that maps neighborhoods of {-1, 0, 1, 2} to the exact integers and is realizable by the model.
    Assumption 2 of Theorem 1 introduces this f to make the state-exchange proof work; the paper later proposes approximating it with four exponential kernels with fitted weights, but does not prove the learned model converges to such an f.
  • domain assumption The square matrices Wk are typically full rank and hence invertible.
    Appendix F uses this to simplify S* = Wv Wk^{-1} in the single-head DeltaNet analysis; low-rank or non-invertible projections change the conclusion.
invented entities (2)
  • DeltaFormer model with retrieval vector wt and independent write/read kernels kappa1 and kappa2
    purpose: Combines softmax-attention retrieval precision with delta-rule memory updates; claimed to exceed TC0 expressivity.
    The model is new to this paper; evidence is limited to toy experiments inside the paper (Sections 3.2-3.3) and no external benchmark or independent implementation exists.
  • Rounding-like kernel function f (or its GQA approximation with coefficients a_j)
    purpose: Enables the state-tracking theorem by mapping neighborhood similarities to exact values in {-1, 0, 1, 2}.
    f is an idealized construct introduced for Theorem 1; the paper suggests a GQA combination of exponentials to approximate it, but provides no demonstration that trained transformers learn this function.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Understanding Transformer from the Perspective of Associative Memory." pith.science (2026). https://pith.science/paper/OPJ6GYGW

@misc{pith2026250519488,
  author       = {Pith},
  title        = {Pith review of: Understanding Transformer from the Perspective of Associative Memory},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OPJ6GYGW}},
  note         = {Machine review of arXiv:2505.19488}
}
read the original abstract

In this paper, we share our reflections and insights on understanding Transformer architectures through the lens of associative memory--a classic psychological concept inspired by human cognition. We start with the basics of associative memory (think simple linear attention) and then dive into two dimensions: Memory Capacity: How much can a Transformer really remember, and how well? We introduce retrieval SNR to measure this and use a kernel perspective to mathematically reveal why Softmax Attention is so effective. We also show how FFNs can be seen as a type of associative memory, leading to insights on their design and potential improvements. Memory Update: How do these memories learn and evolve? We present a unified framework for understanding how different Transformer variants (like DeltaNet and Softmax Attention) update their "knowledge base". This leads us to tackle two provocative questions: 1. Are Transformers fundamentally limited in what they can express, and can we break these barriers? 2. If a Transformer had infinite context, would it become infinitely intelligent? We want to demystify Transformer architecture, offering a clearer understanding of existing designs. This exploration aims to provide fresh insights and spark new avenues for Transformer innovation.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Scaling Latent Reasoning via Looped Language Models

    cs.CL 2025-10 unverdicted novelty 7.0 of 10

    Looped language models with latent iterative computation and entropy-regularized depth allocation achieve performance matching up to 12B standard LLMs through superior knowledge manipulation.

  2. Raven: High-Recall Sequence Modeling with Sparse Memory Routing

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Raven is a linear-time sequence model whose sparse, input-dependent routing writes tokens into dedicated memory slots, preserving long-context recall and extrapolating 16x beyond training length.

  3. Stateful Token Reduction for Long-Video Hybrid VLMs

    cs.CV 2026-02 conditional novelty 6.0 of 10

    For hybrid Mamba–Transformer video models, keeping 25% of visual tokens with a query-based progressive schedule gives 3.8–4.2x prefilling speedups with near-baseline accuracy; the paper attributes this to stateful com...

  4. Neural Attention Search Linear: Towards Adaptive Token-Level Hybrid Attention Models

    cs.CL 2026-02 conditional novelty 6.0 of 10

    NAtS-L learns per-chunk routing between Gated DeltaNet and softmax attention, improving long-context retrieval and length extrapolation over fixed hybrids.

  5. Distributed Dynamic Associative Memory via Online Convex Optimization

    cs.LG 2025-11 conditional novelty 5.0 of 10

    Tree-based distributed online gradient descent gives sublinear static regret and path-length-dependent dynamic regret for heterogeneous multi-agent associative memory with communication delays.

Reference graph

Works this paper leans on

58 extracted references · 24 canonical work pages · cited by 5 Pith papers

  1. [1]

    Gqa: Training generalized multi-query transformer models from multi-head checkpoints.arXiv preprint arXiv:2305.13245, 2023

    Joshua Ainslie, James Lee-Thorp, Michiel De Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sang- hai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints.arXiv preprint arXiv:2305.13245, 2023

    arXiv 2023

  2. [2]

    Titans: Learning to memorize at test time.arXiv preprint arXiv:2501.00663, 2024

    Ali Behrouz, Peilin Zhong, and Vahab Mirrokni. Titans: Learning to memorize at test time.arXiv preprint arXiv:2501.00663, 2024

    arXiv 2024

  3. [3]

    It’s all connected: A journey through test-time memorization, attentional bias, retention, and online optimization, 2025

    Ali Behrouz, Meisam Razaviyayn, Peilin Zhong, and Vahab Mirrokni. It’s all connected: A journey through test-time memorization, attentional bias, retention, and online optimization, 2025. URLhttps://arxiv.org/ abs/2504.13173

    arXiv 2025

  4. [4]

    Language models are few-shot learners

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020

    1901

  5. [5]

    Flashattention-2: Faster attention with better parallelism and work partitioning

    Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691, 2023

    arXiv 2023

  6. [6]

    Flashattention: Fast and memory-efficient exact attention with io-awareness

    Tri Dao, Daniel Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. InAdvances in Neural Information Processing Systems, volume 35, pages 12556–12570, 2022

    work page 2022

  7. [7]

    An image is worth 16x16 words: Transformers for image recognition at scale.arXiv preprint arXiv:2010.11929, 2020

    Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale.arXiv preprint arXiv:2010.11929, 2020

    arXiv 2010

  8. [8]

    Softmax linear units.Transformer Circuits Thread, 2022

    Nelson Elhage, Tristan Hume, Catherine Olsson, Neel Nanda, Tom Henighan, Scott Johnston, Sheer ElShowk, Nicholas Joseph, Nova DasSarma, Ben Mann, Danny Hernandez, Amanda Askell, Kamal Ndousse, Andy Jones, Dawn Drain, Anna Chen, Yuntao Bai, Deep Ganguli, Liane Lovitt, Zac Hatfield-Dodds, Jackson Kernion, Tom Conerly, Shauna Kravec, Stanislav Fort, Saurav K...

    work page 2022

Show all 58 references
  1. [9]

    Toy models of superposition.Transformer Circuits Thread, 2022

    Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield- Dodds, Robert Lasenby, Dawn Drain, Carol Chen, Roger Grosse, Sam McCandlish, Jared Kaplan, Dario Amodei, Martin Wattenberg, and Christopher Olah. Toy models of superpos...

    2022

  2. [10]

    Chain and causal attention for efficient entity tracking

    Erwan Fagnou, Paul Caillon, Blaise Delattre, and Alexandre Allauzen. Chain and causal attention for efficient entity tracking. InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 13174–13188, 2024

    2024

  3. [11]

    Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity.Journal of Machine Learning Research, 23(120):1–39, 2022

    William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity.Journal of Machine Learning Research, 23(120):1–39, 2022

    2022

  4. [12]

    What can transformers learn in-context? a case study of simple function classes.Advancesin Neural Information Processing Systems, 35:30583–30598, 2022

    Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes.Advancesin Neural Information Processing Systems, 35:30583–30598, 2022

    2022

  5. [13]

    Unlocking state-tracking in linear rnns through negative eigenvalues.arXiv preprint arXiv:2411.12537, 2024

    Riccardo Grazzi, Julien Siems, Arber Zela, Jörg KH Franke, Frank Hutter, and Massimiliano Pontil. Unlocking state-tracking in linear rnns through negative eigenvalues.arXiv preprint arXiv:2411.12537, 2024

    2024 arXiv

  6. [14]

    Superposition, memorization, and double descent.Transformer Circuits Thread, 6:24, 2023

    Tom Henighan, Shan Carter, Tristan Hume, Nelson Elhage, Robert Lasenby, Stanislav Fort, Nicholas Schiefer, and Christopher Olah. Superposition, memorization, and double descent.Transformer Circuits Thread, 6:24, 2023

    2023

  7. [15]

    Psychology press, 2014

    Geoffrey E Hinton and James A Anderson.Parallel models of associative memory: updated edition. Psychology press, 2014

    2014

  8. [16]

    Highly accurate protein structure prediction with alphafold

    John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žídek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. nature, 596(7873):583–589, 2021

    2021

  9. [17]

    Transformers are rnns: Fast autoregressive transformers with linear attention

    Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. InInternational conference on machine learning, pages 5156–

  10. [18]

    The impact of positional encoding on length generalization in transformers.Advancesin Neural Information Processing Systems, 36:24892–24928, 2023

    Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers.Advancesin Neural Information Processing Systems, 36:24892–24928, 2023

    2023

  11. [19]

    Correlation matrix memories.IEEE transactions on computers, 100(4):353–359, 1972

    Teuvo Kohonen. Correlation matrix memories.IEEE transactions on computers, 100(4):353–359, 1972

    1972

  12. [20]

    Minimax-01: Scaling foundation models with lightning attention.arXiv preprint arXiv:2501.08313, 2025

    Aonian Li, Bangwei Gong, Bo Yang, Boji Shan, Chang Liu, Cheng Zhu, Chunhao Zhang, Congchao Guo, Da Chen, Dong Li, et al. Minimax-01: Scaling foundation models with lightning attention.arXiv preprint arXiv:2501.08313, 2025

    2025 arXiv

  13. [21]

    Forgetting transformer: Softmax attention with a forget gate.arXiv preprint arXiv:2503.02130, 2025

    Zhixuan Lin, Evgenii Nikishin, Xu Owen He, and Aaron Courville. Forgetting transformer: Softmax attention with a forget gate.arXiv preprint arXiv:2503.02130, 2025

    2025 arXiv

  14. [22]

    Moba: Mixture of block attention for long-context llms.arXiv preprint arXiv:2502.13189, 2025

    Enzhe Lu, Zhejun Jiang, Jingyuan Liu, Yulun Du, Tao Jiang, Chao Hong, Shaowei Liu, Weiran He, Enming Yuan, Yuzhi Wang, et al. Moba: Mixture of block attention for long-context llms.arXiv preprint arXiv:2502.13189, 2025

    2025 arXiv

  15. [23]

    The parallelism tradeoff: Limitations of log-precision transformers

    William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531–545, 2023

    2023

  16. [24]

    The illusion of state in state-space models

    William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. InInternational Conference on Machine Learning, pages 35492–35506. PMLR, 2024

    2024

  17. [25]

    In-context learning and induction heads

    Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209.11895, 2022

    2022 arXiv

  18. [26]

    Rwkv-7" goose" with expressive dynamic state evolution.arXiv preprint arXiv:2503.14456, 2025

    Bo Peng, Ruichong Zhang, Daniel Goldstein, Eric Alcaide, Haowen Hou, Janna Lu, William Merrill, Guangyu Song, Kaifeng Tan, Saiteja Utpala, et al. Rwkv-7" goose" with expressive dynamic state evolution.arXiv preprint arXiv:2503.14456, 2025

    2025 arXiv

  19. [27]

    Yarn: Efficient context window extension of large language models.arXiv preprint arXiv:2309.00071, 2023

    Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. Yarn: Efficient context window extension of large language models.arXiv preprint arXiv:2309.00071, 2023

    2023 arXiv

  20. [28]

    Mechanistic design and scaling of hybrid architectures

    Michael Poli, Armin W Thomas, Eric Nguyen, Pragaash Ponnusamy, Björn Deiseroth, Kristian Kersting, Taiji Suzuki, Brian Hie, Stefano Ermon, Christopher Re, et al. Mechanistic design and scaling of hybrid architectures. In International Conference on Machine Learning, pages 4090...

    2024

  21. [29]

    Learning transferable visual models from natural language supervision

    Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pa...

    2021

  22. [30]

    Robust speech recognition via large-scale weak supervision

    Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. InInternational conference on machine learning, pages 28492–28518. PMLR, 2023

    2023

  23. [31]

    Hopfield networks is all you need.arXiv preprint arXiv:2008.02217, 2020

    Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Thomas Adler, Lukas Gruber, Markus Holzleitner, Milena Pavlović, Geir Kjetil Sandve, et al. Hopfield networks is all you need.arXiv preprint arXiv:2008.02217, 2020

    2008 arXiv

  24. [32]

    Understanding transformer reasoning capabilities via graph algorithms.Advancesin Neural Information Processing Systems, 37:78320–78370, 2024

    Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms.Advancesin Neural Information Processing Systems, 37:78320–78370, 2024

    2024

  25. [33]

    Linear transformers are secretly fast weight programmers

    Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers are secretly fast weight programmers. In International conference on machine learning, pages 9355–9366. PMLR, 2021

    2021

  26. [34]

    Flashattention-3: Fast and accurate attention with asynchrony and low-precision.arXiv preprint arXiv:2407.08608, 2024

    Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision.arXiv preprint arXiv:2407.08608, 2024

    2024 arXiv

  27. [35]

    Glu variants improve transformer, 2020

    Noam Shazeer. Glu variants improve transformer, 2020. URLhttps://arxiv.org/abs/2002.05202

    2020 arXiv

  28. [36]

    Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.arXiv preprintarXiv:1701.06538, 2017

    Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.arXiv preprintarXiv:1701.06538, 2017. 24

    2017 arXiv

  29. [37]

    Normformer: Improved transformer pretraining with extra normaliza- tion, 2021

    Sam Shleifer, Jason Weston, and Myle Ott. Normformer: Improved transformer pretraining with extra normaliza- tion, 2021. URL https://arxiv.org/abs/2110.09456

    2021 arXiv

  30. [38]

    Deltaproduct: Improving state-tracking in linear rnns via householder products.arXiv preprint arXiv:2502.10297, 2025

    JulienSiems, TimurCarstensen, ArberZela, FrankHutter, MassimilianoPontil, andRiccardoGrazzi. Deltaproduct: Improving state-tracking in linear rnns via householder products.arXiv preprint arXiv:2502.10297, 2025

    2025

  31. [39]

    Roformer: Enhanced transformer with rotary position embedding.Neurocomputing, 568:127063, 2024

    Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding.Neurocomputing, 568:127063, 2024

    2024

  32. [40]

    Retentive network: A successor to transformer for large language models.arXiv preprint arXiv:2307.08621, 2023

    Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models.arXiv preprint arXiv:2307.08621, 2023

    2023 arXiv

  33. [41]

    Associative learning and the hippocampus

    Wendy A Suzuki. Associative learning and the hippocampus. 2005

    2005

  34. [42]

    Attention is all you need.Advances in Neural Information Processing Systems, 2017

    A Vaswani. Attention is all you need.Advances in Neural Information Processing Systems, 2017

    2017

  35. [43]

    Attention is all you need.Advances in neural information processing systems, 30, 2017

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need.Advances in neural information processing systems, 30, 2017

    2017

  36. [44]

    Length generalization of causal transformers without position encoding.arXiv preprint arXiv:2404.12224, 2024

    Jie Wang, Tao Ji, Yuanbin Wu, Hang Yan, Tao Gui, Qi Zhang, Xuanjing Huang, and Xiaoling Wang. Length generalization of causal transformers without position encoding.arXiv preprint arXiv:2404.12224, 2024

    2024 arXiv

  37. [45]

    Test-time regression: a unifying framework for designing sequence models with associative memory.arXiv preprint arXiv:2501.12352, 2025

    Ke Alexander Wang, Jiaxin Shi, and Emily B Fox. Test-time regression: a unifying framework for designing sequence models with associative memory.arXiv preprint arXiv:2501.12352, 2025

    2025 arXiv

  38. [46]

    Kv shifting attention enhances language modeling

    Mingyu Xu, Wei Cheng, Bingning Wang, and Weipeng Chen. Kv shifting attention enhances language modeling. arXiv preprint arXiv:2411.19574, 2024

    2024 arXiv

  39. [47]

    Gated linear attention transformers with hardware-efficient training.arXiv preprint arXiv:2312.06635, 2023

    Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. Gated linear attention transformers with hardware-efficient training.arXiv preprint arXiv:2312.06635, 2023

    2023 arXiv

  40. [48]

    Parallelizing linear transformers with the delta rule over sequence length.arXiv preprint arXiv:2406.06484, 2024

    Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing linear transformers with the delta rule over sequence length.arXiv preprint arXiv:2406.06484, 2024

    2024 arXiv

  41. [49]

    Root mean square layer normalization.Advancesin Neural Information Processing Systems, 32, 2019

    Biao Zhang and Rico Sennrich. Root mean square layer normalization.Advancesin Neural Information Processing Systems, 32, 2019

    2019

  42. [50]

    Probabilistic methods in combinatorics.Draft available at https://yufeizhao

    Yufei Zhao. Probabilistic methods in combinatorics.Draft available at https://yufeizhao. com/pm, 2022. 25 Appendix A Derivation of the Inverse SNR Formula Since the linear form of Associative Memory is a special case of Eq. 9, we first derive Eq. 10, and then specialize the de...

    2022

  43. [51]

    "" n is the pr evi ou s v , v is a ct ua lly new v

    Conditional on the probe key ki, the inner product Xj = k⊤ j ki ∼ N 0, ∥ki∥2 2 . The Gaussian mo- ment–generating function therefore givesE[exp( 2Xj τ )] = exp( 2∥ki∥2 2 τ 2 ), and thus SNR−1 exp = N exp 2 τ 2 − 2 τ ∥ki∥2 2 = N exp 2(1−τ ) τ 2 ∥ki∥2 2 . Replacing the squared n...

  44. [52]

    If i = l1, then we have f ((ki − kj)⊤kl) = f (U (1, 3ϵ)) = 1 f (k⊤ i kl) − f (k⊤ j kl) = f (U (1, ϵ)) − f (U (0, 2ϵ)) = 1

  45. [53]

    If i = l2, then we have f ((ki − kj)⊤kl) = f (U (−1, 3ϵ)) = −1 f (k⊤ i kl) − f (k⊤ j kl) = f (U (−1, ϵ)) − f (U (0, 2ϵ)) = −1

  46. [54]

    If j = l1, then similarly f ((ki − kj)⊤kl) = f (U (−1, 3ϵ)) = −1 f (k⊤ i kl) − f (k⊤ j kl) = f (U (0, 2ϵ)) − f (U (1, ϵ)) = −1

  47. [55]

    If j = l2, then similarly f ((ki − kj)⊤kl) = f (U (1, 3ϵ)) = 1 f (k⊤ i kl) − f (k⊤ j kl) = f (U (0, 2ϵ)) − f (U (−1, ϵ)) = 1. 37 iii. If two pairs are equal simultaneously:

  48. [56]

    If i = l1, j= l2, we have f ((ki − kj)⊤kl) = f (U (2, 2ϵ)) = 2 f (k⊤ i kl) − f (k⊤ j kl) = f (U (1, ϵ)) − f (U (−1, ϵ)) = 2

  49. [57]

    Combining all the above cases, we have completed the proof

    If i = l2, j= l1, this contradicts the ordering conditionj < i, l2 < l1 and thus cannot occur. Combining all the above cases, we have completed the proof. E.1.2 Formally Prove Theorem 1 We use mathematical induction to prove Theorem 1. When t = n + 1: kt = kt1 − kt2 , (101) ut...

  50. [58]

    b h s d , b h t d - > b h s t

    This implies that for Assumption 1 to hold, it is required that d = O(log n). Regarding the choice off (·) in Assumption 2, intuitively, we can use the rounding functionround(·), i.e., setting the input to the nearest integer. Under appropriate rounding precision, this functio...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.