acceptodds
Under review as a conference paper at ICLR 2027

A Probabilistic Account of Associative Memory of a Single Attention Head

Abstract

A single attention head that predicts the next token by attending to an earlier, related position in the sequence can also be seen as a form of associative memory. However, the reason and amount of such association storage are generally unclear. In the proposed work, we investigate a non-asymptotic explanation for a single-head, attention-only transformer. We introduce random spherical representations to construct an explicit query-key matrix and a value-output matrix that jointly bind a designated target position in each stored sequence to a prescribed output token. The proposed system allows arbitrary queries and gives each sequence-position pair its own representation, unlike constructions that fix the query to an end-of-sequence token or assign a single embedding per vocabulary item, thereby allowing a repeated token to carry different associations at different positions. Our analysis of the proposed system isolates three effects, namely, query-key retrieval interference, decoder interference, and the operator-norm normalisation of the value-output map, and controls them using sub-Gaussian and sub-exponential concentration, together with a matrix Bernstein bound. It has been proved that with high probability, the construction simultaneously stores associations whenever the sequence length and vocabulary size are polynomial in head dimension, a quadratic-over-logarithmic lower bound on the associative capacity attributable to attention alone. Our experiments confirm the predicted growth of the normalisation constant's scaling exponent and a sharp memorisation phase transition. Our experiments show capacity follows the ambient head dimension when the query/value maps are learned, and shifts toward a spectral dimension when the attention geometry is fixed and strongly anisotropic.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
memorization, associative memory, attention, capacity scaling laws

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_QZ7fOpenReview ↗
Rating
2
Confidence
3(+1)
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the associative memory capacity of a single attention head. The capacity lower bound is meaningful and is obtained through random sphereical representations and a regular construction which controls the WQKW_{QK} and WOVW_{OV} matrices. The problem is significant, but I favor weak rejection.

Critical strengths
  1. The presentation is nice and easy to read.

  2. The main construction is clear, with resonable treatment of shared parameters and operator norms.

Critical weaknesses
  1. The lower bound construction in this paper applies only to a single-layer attention block and there are already several papers on the associative memory capacity of Transformer architectures. A clearer presentation of the contribution relative to previous theoretical results may be needed to clarify the improvements made in this paper.

  2. The target output tokens are required to be pairwise distinct, implying T≤NT\le N. However, when SS and NN are polynomial in dhd_{h}, I am not quite clear on whether thi setting guarantees pairwise distinctness.

  3. In the experiment shown in Firgure 3, additionally learning the unembedding recovers the exponent 2.00, but the unembedding is randomly sampled and fixed in the theoretical analysis. How should this be understood?

Questions for authors

Plz see weaknesses.

6 comments
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for the valuable suggestions.

W1: The existing literature does not isolate the capacity of attention alone under assumptions that reflect practice, such as bound a full Transformer with FFN (Kim et al. (2023)), Mahdavi et al. (2024) impose a context size restriction n<dn<d and a linear independence condition while targeting label fitting, Nichani et al. (2025) assign one spherical embedding per vocabulary item and pin the retrieval query to a single shared EOS embedding, Kajitsuka & Sato (2025) locate the bottleneck in the feedforward block, and Dana et al. (2024) remove n<dn<d but still use one embedding per vocabulary item and only prove a bound linear in dhd_h, leaving their own empirically observed quadratic scaling unexplained. Our contribution is to close this gap. We give a non-asymptotic, high probability construction for a single attention head in which every stored sequence draws its own query independently, every (sequence, position) pair instead of every vocabulary item receives its own representation, and no restriction is placed on context length relative to dhd_h. Under these strictly more practical assumptions we prove T=Ω(dh2/log⁡dh)T=\Omega(d_{h}^{2}/\log d_{h}) whenever S,N=poly(dh)S,N=\mathrm{poly}(d_h), which is the theoretical account consistent with the quadratic in dhd_h scaling that Dana et al. (2024) observe but leave unexplained. The improvement is a change of the modeling assumptions together with a matching in order capacity law. We have clarified this in the revision making this comparison clear, and we emphasize that our bound is a lower bound on capacity, so it establishes achievability.

W2: The polynomial growth condition S,N=poly(dh)S,N=\mathrm{poly}(d_h) is a separate and independent conditioning, imposed only to obtain a clean denominator. the retrieval and decoder analyses result the two constraints Tlog⁡(c1TS/δ1)≤dh2T\log\left(c_1TS/\delta_1\right)\le d_h^{2} and (Tlog⁡(c2TN/δ2)≤dh2)(T\log\left(c_2TN/\delta_2\right)\le d_h^{2}) given in Section E, which combine into the common sufficient scaling T=Ω(dh2/log⁡(dhmax⁡{S,N}/δ))T=\Omega\left(d_h^{2}/\log(d_h\max\{S,N\}/\delta)\right). When S,N=poly(dh)S,N = \mathrm{poly}(d_h) and δ\delta is fixed, we have log⁡(dhmax⁡{S,N}/δ)=Θ(log⁡dh)\log(d_h\max\{S,N\}/\delta)=\Theta(\log d_h), so the capacity reduces to the form T=Ω(dh2/log⁡dh)T=\Omega(d_h^{2}/\log d_h) mentioned between lines 866 and 874. The pairwise distinctness assumption is what makes the unembedding vectors uy1,…,uyTu_{y_1},\dots,u_{y_T} mutually independent in our random construction, which is needed for the matrix Bernstein bound in Appendix C.

W3: In the theoretical analysis the unembedding vectors are sampled i.i.d. uniformly from Sdh−1\mathbb{S}^{d_h-1} and then held fixed, because this is the regime in which our concentration notion, the spherical sub-Gaussian bound on ⟨uj,uyt⟩\langle u_j,u_{y_t}\rangle, the sub-exponential control of the decoder interference Irt,jI_r^{t,j}, and the Matrix Bernstein bound on WOV′W_{OV}' are valid. The construction then exhibits WQKW_{QK} and WOVW_{OV} achieving the bound, so Theorem 2 is a lower bound on capacity. Figure 3 is a separate empirical question, whether gradient descen finds a solution with the same scaling. When only WQKW_{QK} and WOVW_{OV} are learned with the unembedding frozen, the readout caps the growth and we observe a fitted exponent of 1.59, i.e. a linear capacity line. Once the unembedding is also learned, the full law with exponent 2.00 is recovered. The learned solution has a constant roughly an order of magnitude larger than the construction, and the learned matrices are not entrywise close to the explicit ones, their Frobenius cosine is near zero because the construction is identified only up to gauge, i.e. an overall scale for WQKW_{QK} and a scale with orthogonal head basis change for the WOVW_{OV}/unembedding pair. Their leading singular subspaces nevertheless overlap by ≈0.8\approx 0.8, showing that gradient descent recovers the same low dimensional structure. The frozen-unembedding experiment is a demonstration that the readout is the binding constraint in that setting, which explains the quadratic over logarithmic law is attributable to attention alone.

AuthorsOpenReview ↗

Official Comment by Authors

Dear reviewer QZ7f,

As the open discussion period draws to a close in a few days, we want to check back to see whether you have any remaining concerns. We also believe that we have sufficiently responded to your earlier comments on various aspects of this work.

Please let us know if/how we can address any remaining concerns, and we are grateful for any additional feedback and suggestions.

Best,

Authors

Thank you for clarifying. The construction in the paper gives each sequence position pair its own representation, thus I still find it difficult to assess the improvement over prior bounds which use shared token embeddings. The mathematical formulation is not quite clear and I personaly think the theoretical results seem somewhat trivial without significant technical challenges. I therefore maintain my rating.

Reviewer_6ZLkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper closes a gap in the theory on attention head memorization capacity. For a single head, and a sequence-to-label memorization task, the authors show that a head of dimension d can memorize up to ~ d^2/log(d) sequences, an improvement over a previously linear loose bound which did not line up with empirical results on real models.

Critical strengths
  • S1: The paper addresses a gap in the current literature, a concrete problem the capacity literature that was posed previously and needs to be fixed to make the theory hold up to real models. The bound comes with a construction, that can be verified empirically and compared to learned methods.
  • S2: The paper is well-structured and readable. The construction is written so that it can be followed without too much effort.
  • S3: I like the empirical comparison to real models, where the authors demonstrate how the learned model has less capacity and are able to compare it to the spectral biases of the learning. This tests intuition and applicability.
Critical weaknesses
  • W1: The model proposed for sequences seems artificial, as every sequence is a sample of S random iid vectors. A sequence-to-label memorization in a high-dimensional setting is therefore basically a point to label association. To me it is unclear, why this result should tell us something about the typical challenges one would intuitively associate with memorization of sequences: Many tokens that can be repeated in different sequences but in different orders - this is not the case in the proposed model.
Questions for authors
  • Q1: I am mostly concerned about the selection of the model, and its limitations as a sequence model (see W1), as this connection is the main assumption of this work. Could you clarify why you chose it, and why it is a reasonable model of sequence data and compares well to the setups in the mentioned related work? If the model is not relevant, the contribution of this work is perhaps smaller than it seems on first sight.
  • Q2: Can you clarify how you identify the phase transition on Fig. 1 (right)? What is the threshold/constant that it approaches?
  • Q3: The figure placements and sizes should be improved. It is unclear what the title tags belong to (Exp: 5...)

Typos/Small improvements:

  • It would have helped to obtain a concrete example for the setup. I appreciate the related work appendix table a lot, it would have been even nicer with such examples.
  • L.51/83 notation not defined
3 comments
AuthorsOpenReview ↗

Official Comment by Authors (Part I)

Thanks for your valuable feedback and suggestions. We address each of your questions in detail below.

W1 & Q1: We respectfully but firmly differ that the model reduces to point to label association in a way that strips it of relevance. We would like to make the modeling choices explicit as in our construction each stored sequence t is a collection xsts=1S{x_s^t}_{s=1}^{S} of position specific representations drawn i.i.d. from Unif$(S^{d_h - 1})$, and the target is the representation at a designated position jtj_t i.e. xjtx_j^t, which is then decoded to a label yty_t via the unembedding uytu_{y_t}. The index pair (t,s) identifies the vector, so a repeated token identity at different positions or in different sequences is not required to share a vector. This is different from the one embedding per vocabulary item assumption Nichani et al. (2025) and Dana et al. (2024). We agree that we do not model repeated tokens with shared embeddings. We model repeated positions with independent representations, which is the more realistic regime for associative recall. The reason we isolate a single head and a single designated retrieval position is that this is the minimal setting in which the capacity question is well posed and in which the three error sources i.e. query–key retrieval interference, decoder interference, and the operator norm normalization of WOVW_{OV} can be separated and bounded. Multi-position and multi-head extensions are natural and we intend to explore that as future work. We would also point the reviewer to the empirical section, where we learn WQK,WOVW_{QK},W_{OV} and the unembedding on this construction by gradient descent and recover the same Θ(dh2/log⁡dh)\Theta(d_h^2/\log d_h) law with fitted exponent 2.00 (R2R^2=0.998), and where we show the learned matrices are not entrywise close to the construction i.e. Frobenius cosine near zero but share the same leading singular subspaces. This gauge invariance result is evidence that the construction is not a fragile artifact of the i.i.d. spherical assumption but captures a structure that gradient descent independently finds. Also, the comparison to related work in Table 1 makes the modeling delta explicit, relative to Mahdavi et al. (2024) we remove the n<dn<d restriction. Relative to Nichani et al. (2025) and Dana et al. (2024), we use one representation per (sequence, position) and an independently drawn query per stored sequence, and relative to Kajitsuka & Sato (2025) we isolate attention from the feedforward block.

Q2: The right of Fig. 1 is for each head dimension dh∈{16,24,32,48,64,96,128,192,256}d_h \in \{16,24,32,48,64,96,128,192,256\}, measures the end to end memorization accuracy (the fraction of the TT associations for which both αjtt≥1−ϵ1\alpha_{j_t}^t \ge 1-\epsilon_1 and yt=arg⁡max⁡j⟨uj,zt⟩y_t = \arg\max_j \langle u_j, z^t\rangle hold), and then plot accuracy\text{accuracy} against the rescaled load T/dh2T/d_h^2. The curves collapsing onto a single trajectory is the empirical signature of the Θ(dh2/log⁡dh)\Theta(d_h^2/\log d_h) law, and the phase transition is the knee of that common trajectory, i.e. the rescaled load at which accuracy departs from one. Also, our concentration analysis gives failure probability 1−acc≈a,dhexp⁡(−b,dh2/T)1-\text{acc} \approx a, d_{h} \exp(-b, d_h^2/T) for absolute constants a,b>0a,b>0 in Appendix E. So on the rescaled axis the curves are, up to the slowly varying prefactor a,dha,d_h, graphs of 1−e−1/x1-e^{-1/x} with x=T/dh2x=T/d_h^2, and the knee of the collapse lies at T/dh2≈c/log⁡dhT/d_h^2 \approx c/\log d_h with c≈1.94c \approx 1.94, and the fitted exponent of the capacity line is 2.00 (R2=0.998R^2 = 0.998). The log⁡dh\log d_h denominator is why the knee is not at a single fixed horizontal position across dhd_h, which is the residual spread at the left of the plot. On the vertical axis, the quantity the curve approaches as T/dh2T/d_h^2 grows is 1−acc1-\text{acc} to 1 (equivalently accuracy →0\to 0). The curves approach as T/dh2→0T/d_h^2 \to 0 is accuracy →1\to 1, i.e. 1−acc→01-\text{acc}\to 0. The phase transition itself is the knee separating these two regimes, and it is identified as the rescaled load at which the collapse departs from the plateau at accuracy one, again a horizontal axis location, in the region T/dh2≈0.03–0.05T/d_h^2 \approx 0.03\text{–}0.05 for the dimensions shown. Plotting log⁡(1−acc)=log⁡(a dh)−b dh2/T\log(1-\text{acc}) = \log(a\,d_h) - b\,d_h^2/T versus TT at fixed dhd_h shows the transition sharpening and shifting right as dhd_h grows lower dimensions saturate to 1−acc→11-\text{acc}\to 1 at smaller TT, higher dimensions retain accuracy longer, which is the dhd_h dependent prefactor and the log⁡dh\log d_h denominator predicted by the bound C(dh,S,N,δfail)≥c dh2/log⁡(dhmax⁡(S,N)/δ)\mathcal{C}(d_h,S,N,\delta_{\text{fail}}) \ge c\, d_h^2/\log(d_h \max(S,N)/\delta) at line 891. We have included the details in the revision to explain the collapse.

AuthorsOpenReview ↗

Official Comment by Authors (Part II)

Q3: We have fixed the figures sizes with its placement in the revision. The Exp: 5 refers to experiment 5, which is for effective dimension correction under synthetic anisotropy

Regarding the typos and improvements, we have included examples for our setups in Table 1 in the revision. Also, we have defined the notations at L51/83 accordingly now included in the revision, where dhd_h is the head dimension of a single head attention only Transformer, which is given in Section 4.

AuthorsOpenReview ↗

Official Comment by Authors

Dear reviewer 6ZLk,

As the open discussion period approaches its end, we would like to follow up on our responses to your earlier comments and check whether any questions or concerns remain.

We would be happy to clarify any points further and sincerely appreciate your time and valuable feedback.

Best,

Authors

Reviewer_7qQiOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the softmax attention as associative memory, and analyze the capacity of such memory system both theoretically and empirically. Specifically, the study construct the query-key matrix WQKW_{QK} and value-output matrix WVOW_{VO} from the samples xstx_{s}^t, where the query-key matrix selects a designated position in the sequence (matching xStx_{S}^t and xjttx_{j_t}^t), while the value-output matrix maps the selected position to the desired output. When all the samples from each sequence are drawn ramdomly from a sphere, along with the two constraint ensuring correct retrieval (sufficient retrieval score gap and correctness), the authors proved that T=O(dh2/log⁡dh)T = \mathcal O(d_h^2 / \log d_h). Although all the premises make this softmax attention model different from the one used in learned LLMs, it provides insights on why the softmax attention architecture itself have a larger memory capacity compared to vanilla Hopfield network.

Critical strengths
  1. Research question is clear and focus, and the conclusion is insightful. To me, understanding the behaviour of a single attention head in one layer is easier and more tacklable compared to a full Transformer, and the author(s) places the attention mechanisms under the scope of associative memory so that the advancement of softmax attention can be compare directly to vanilla Hopfield networks and its variants (which is believed to be similar to a linear attention with Wq=Wk=Wv=IW_q = W_k = W_v = I).
  2. This study also includes proper experiments that well supports the theoretical results. The memory capacity scaling, operator norms agrees with the theory.
Critical weaknesses
  1. The assumptions used in the paper limits the interpretation of attention mechanisms. All of the input and the target are all uniformly sampled from the sphere, and contains zero semantic meanings, and it is completely different from the scenario where LLMs are deployed. It would be great if the author(s) adds a new experiments where the two K-V V-O matrices are learned, and all patterns xstx_{s}^t's are some meaningful and inter-connected objects (e.g., text/image embedding, something that is more realistic). The results of this paper is focused, insightful, and clear to me (as said in the strength), but it would be better if it can be more connected to the real-world scenario.
  2. The conclusion is that T=Ω(dh2/log⁡dn)T = \Omega(d_h^2 / \log d_n), when N=poly⁡(dh)N = \operatorname{poly}(d_h). But the distinction target makes T≤NT \le N, so when N=dN = d, we have T=Ω(d)T = \Omega(d) which contradicts with Ω(dh2/log⁡dh)\Omega(d_h^2 / \log d_h). Why every sequence must have a distinct target output token? Is this necessary, is the theory still valid when NN is small / independent of dhd_h?
  3. [Minor] It would be good if the author(s) can add highlight and hyperlink to citations / reference to image/table/section/appendix. And there is a very small glitch in Table 1 (after Appendix F.1, line 959), where max⁡{N,N2/3S8/3/n4/3}\max\{ N, N^{2/3} S^{8/3} / n^{4/3} \} overlaps with the table cell to the right.
Questions for authors

See the weakness part.

4 comments
AuthorsOpenReview ↗

Official Comment by Authors (Part I)

Thanks for your the constructive and valuable suggestions. We address your concerns below in detail.

W1: We agree that the i.i.d. uniform sphere model is a null model, and we have included experiments in which the query-key and value-output matrices are learned by gradient descent on meaningful, interconnected patterns with real targets. The new experiments confirm that the same capacity law holds on real text and image data when the head is learned, and they explain when and why it fails for the fixed closed form construction.

Initially, we prove that the lower bound is invariant under any invertible linear mixing of the patterns, so isotropy is without loss of generality within the non-degenerate class. If xst=A,ξstx_s^t = A,\xi_s^t and un=B,ηnu_n = B,\eta_n with A,BA,B invertible, and W~QK,W~OV′\widetilde W_{QK}, \widetilde W'_{OV} are our construction on (ξ,η)(\xi,\eta), then setting WQK=A−⊤W~QKA−1W_{QK} = A^{-\top}\widetilde W_{QK}A^{-1} and WOV′=B−⊤W~OV′A−1W'_{OV} = B^{-\top}\widetilde W'_{OV}A^{-1} gives (xSt)⊤WQKxℓt=(ξSt)⊤W~QKξℓt,⟨uj,WOV′x⟩=⟨ηj,W~OV′ξ⟩,(x_S^t)^{\top}W_{QK}x_\ell^t = (\xi_S^t)^{\top}\widetilde W_{QK}\xi_\ell^t, \qquad \langle u_j, W'_{OV}x\rangle = \langle \eta_j, \widetilde W'_{OV}\xi\rangle, so all attention weights and logits coincide with those of the spherical construction, and Theorem 2 delivers the same T=Ω(dh2/log⁡(dhmax⁡{S,N}))T = \Omega(d_h^2/\log(d_h\max\{S,N\})) associations. This is now Proposition 3 in the revision. Elliptical and Gaussian patterns with any non-degenerate covariance therefore admit a head with the full quadratic over logarithmic capacity. The price of anisotropy moves from capacity into the conditioning of the weights.

Also, for the unwhitened closed form construction we quantify how anisotropy degrades capacity. For xst∼N(0,Σx)x_s^t \sim \mathcal N(0,\Sigma_x) and un∼N(0,Σu)u_n \sim \mathcal N(0,\Sigma_u) with tr⁡Σx=tr⁡Σu=1\operatorname{tr}\Sigma_x = \operatorname{tr}\Sigma_u = 1, and participation ratios dx=(tr⁡Σx)2/tr⁡(Σx2)d_x = (\operatorname{tr}\Sigma_x)^2/\operatorname{tr}(\Sigma_x^2), du=(tr⁡Σu)2/tr⁡(Σu2)d_u = (\operatorname{tr}\Sigma_u)^2/\operatorname{tr}(\Sigma_u^2), repeating the Bernstein and decoder arguments with 1/dh1/d_h replaced by 1/dx1/d_x and 1/du1/d_u gives \tau_1 \lesssim \frac{\sqrt{T\ell_1}}{d_x} + \sqrt{\frac{\ell_1}{d_x}}, \qquad \tau_2 \lesssim \sqrt{\frac{T\ell_2}{d_x d_u}} + \sqrt{\frac{\ell_2}{d_u}}, \qquad \text{hence} \qquad T = \Omega\left(\frac{\min\{d_x^2\, d_x d_u}}{\log(\max\{d_x, d_u\}\max\{S,N\}/\delta)}\right) for the fixed Hebbian head in Proposition 4. This is in which a fixed geometry bottlenecks capacity at the spectral dimension, while an adaptive head recovers the ambient dhd_h by the invariance above.

We implemented the suggested experiment. We trained a three layer, width 192 word-level causal Transformer on Tiny Shakespeare with held out perplexity 167.8 versus 471.0 for unigram and 274.6 for interpolated bigram, so the hidden states come from a working language model. The patterns xstx_s^t are its last layer residual stream states at real text positions, contextual, correlated across positions and sequences, and strongly anisotropic, where participation ratio 21.4 of 192. The unembeddings are the model's own tied word embeddings with participation ratio 33.1 of 192, so every target is a real word with its real semantic geometry. We study induction recall (the retrieve then copy behaviour of induction heads, Olsson et al., 2022), with jtj_t the position after the previous occurrence of the query word and yty_t the word found there, using 45,657 natural induction windows and up to 4,399 distinct target words, as well as arbitrary association on the same contextual states. For images we embed MNIST digits with a CNN and build a key to value image memory over S=8S=8 real images with CNN-embedded value targets; the geometry is extremely interconnected, with participation ratio 6.9 of 128. Representations are centred, PCA projected to dhd_h so that dhd_h is a bottleneck, and ℓ2\ell_2-normalised, with W^QK,W^OV\widehat W_{QK}, \widehat W_{OV} trained by full batch Adam with the real unembeddings frozen.

T⋆T^\star at dh=d_h=812162432slopeR2R^2 of T⋆log⁡dhT^\star\log d_h vs dh2d_h^2vs. isotropic
isotropic patterns (control)42841442644321.670.99951.00
text, induction recall461001563526721.910.99341.25
text, arbitrary association42801242243521.520.99920.90
images, key-to-value memory3868961762241.300.9760.71

With learned maps, capacity on real, interconnected patterns follows the same law as on random spherical patterns i.e., on both text tasks T⋆log⁡dhT^\star\log d_h is linear in dh2d_h^2 with R2≥0.993R^2 \ge 0.993, and the isotropic control has local log-log slope 1.67, resembling what Θ(dh2/log⁡dh)\Theta(d_h^2/\log d_h) predicts on this range (since 2−1/ln⁡dh≈1.642 - 1/\ln d_h \approx 1.64–1.711.71 for dh∈[8,32]d_h \in [8,32]). The induction task exceeds the isotropic capacity because language structure is aligned with the association.

AuthorsOpenReview ↗

Official Comment by Authors (Part II)

W1 (Continued): Even on MNIST, where all codes live in an effectively seven dimensional class clustered space, the learned head keeps growing with ambient dhd_h well beyond deff≈7d_{\mathrm{eff}} \approx 7, retaining about 71% of isotropic capacity, approximately fifty times what the closed form construction stores on the same images. The construction itself behaves as Proposition 4 predicts. Its capacity plateaus at dh=64d_h = 64 at 12, 8 and 4 associations for the three tasks against 128 on isotropic patterns, because the participation ratio of the projected geometry saturates at about 21 for text and 7 for images. This isolates the source of the random versus real gap. It is the unwhitened geometry, which a fixed Hebbian head cannot correct and a learned head largely can.

We also verified that learned heads discover the retrieve then copy mechanism our construction uses. At half capacity, the attention argmax lands on the induction position 0.09, 0.14, 0.22, 0.55 and 0.70 of the time at dh=8,…,32d_h = 8,\dots,32 against 1/S=0.06251/S = 0.0625 by chance, i.e. eleven times chance at dh=32d_h = 32, while on arbitrary associations it stays at chance because every position already identifies its sequence. We note that with N=TN=T and a learned unembedding the readout alone can memorize by setting uyt∝ztu_{y_t} \propto z^t, so those panels reflect the optimisation budget instead of head. All learned head results thus keep the unembedding frozen, and we have updated these with the results in the revision.

W2: Thanks for this observation, and we clarify that there is no contradiction. The two statements hold in different regimes and our theorem is conditional on the vocabulary constraint, which we explain and analyse in the small NN regime.

The constraint T≤NT \le N is an artefact of our proof technique. We require the target unembeddings uy1,…,uyTu_{y_1},\dots,u_{y_T} to be mutually independent so that the decoder interference terms are independent and centred, which is what permits the matrix Bernstein and scalar Bernstein arguments. Pairwise distinct targets is the simplest sufficient condition for this independence. The true capacity of the head does not require it, the decoder margin in Proposition 3 is a statement about the TT stored associations, and repeated targets simply mean that some rows of WOV′W'_{OV} are reused, which cannot hurt retrieval of the associations themselves. It only changes the decoding bookkeeping. We are clear that the result is a lower bound on the capacity of the head class, and the distinct target condition is a sufficient condition under which our construction and its proof go through. If we do not consider the target unembeddings to be mutually independent i.e. some sequences have the same target unembedding then the decoder interference given by τ2\tau_2 in proposition 3 would also contain a Tl2dh\sqrt{\frac{Tl_2}{d_h}} term given by the Subgaussian Hoeffding inequality, in the regime where there are higher number of repeated target unembeddings the interference due to them will dominate and result in a capacity of Ω(min⁡(N,dhlog⁡(dhmax⁡{S,N}/δ)))\Omega(\min(N,\frac{d_h}{\log(d_h \max\{S,N\}/\delta)})), which explains the cause of reduction in memorization capacity due to skewed targets, we have included detailed proof in the revision.

On the scaling, the theorem is given as T≤min⁡(N,Cdh2/log⁡(dhmax⁡(S,N)/δ))T \le \min(N, C d_h^2/\log(d_h\max(S,N)/\delta)), and the conclusion T=Ω(dh2/log⁡dh)T = \Omega(d_h^2/\log d_h) is drawn only in the regime N=poly(dh)N = \mathrm{poly}(d_h), S=poly(dh)S = \mathrm{poly}(d_h), with fixed failure probability, where log⁡(dhmax⁡(S,N)/δ)=Θ(log⁡dh)\log(d_h \max(S,N)/\delta) = \Theta(\log d_h). In that regime the vocabulary constraint T≤NT \le N is not binding because NN is polynomial in dhd_h while dh2/log⁡dhd_h^2/\log d_h is eventually smaller than any polynomial. The two bounds are consistent. When N=DN = D is a fixed constant independent of dhd_h, the binding constraint is T≤DT \le D, so the achievable statement degenerates to T=Ω(1)T = \Omega(1) with the constant depending on DD and δ\delta, which is trivially true and is not the regime the theorem addresses. There is no contradiction, Ω(dh2/log⁡dh)\Omega(d_h^2/\log d_h) is a statement about how capacity grows with head dimension when the vocabulary grows at least polynomially, and our work never claims it holds at fixed NN.

The theory remains valid, and indeed informative, for small NN once one reads the bound in its full form. The retrieval constraint Tlog⁡(c1TS/δ1)≤c dh2T\log(c_1 TS/\delta_1) \le c\, d_h^2 and the decoder constraint Tlog⁡(c2TN/δ2)≤c dh2T\log(c_2 TN/\delta_2) \le c\, d_h^2 are both retained, and the achievable capacity is T=Ω(min⁡(N,dh2log⁡(dhmax⁡{S,N}/δ)))T = \Omega(\min(N, \frac{d_h^{2}}{\log(d_h \max\{S,N\}/\delta))}), so for N=DN = D fixed the construction stores all DD associations whenever Dlog⁡(dhmax⁡(S,D)/δ)≲dh2D \log(d_h \max(S,D)/\delta) \lesssim d_h^2, i.e. as soon as the head dimension is large enough relative to the (logarithm of the) vocabulary, which is the correct and expected behaviour. A small vocabulary is not a bottleneck for a wide head.

AuthorsOpenReview ↗

Official Comment by Authors (Part III)

W2 (Continued): Conversely, for NN polynomial in dhd_h the min is attained by the second term and we recover the quadratic over logarithmic law. We have made this regime dependence in the revision, restated the theorem with the min⁡{N,⋅}\min\{N,\cdot\} form as the primary statement, and added a remark that the distinct target assumption can be relaxed to any target set whose unembeddings are in general position, with the same proof up to constants. The pairwise distinct case is the cleanest sufficient condition and the one under which the numerical protocols (which use N=TN=T distinct targets) are run. We hope this fully resolves your concerns.

W3: Thanks for your suggestions. We have updated the table with appropriate references with highlights in each row with explanations in the revision. Also, we have fixed the formatting issue, which is updated in the revision.

AuthorsOpenReview ↗

Official Comment by Authors

Dear reviewer 7qQi,

As the open discussion period draws to a close, we would like to kindly check whether you have any remaining concerns regarding our responses to your earlier comments.

We would be happy to provide further clarification if helpful, and we sincerely appreciate your time and constructive feedback.

Best,

Authors

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

In this paper, under the setting of randomly generated training data, they assume that the token representation at each position is independently and uniformly sampled from a high-dimensional unit sphere. For a given set of T training sequences, each sequence initiates a query from the last position; the target is pre-specified, differs from the query position, and is allowed to vary across sequences. This paper investigates the memory capacity required for the projectile attention mechanism to correctly complete all associative memory tasks via QK retrieval and OV decoding.

The paper constructs WQKW_{QK} and WOVW_{OV} based on the training data and performs a theoretical analysis, providing a constructive lower bound on memory capacity that is approximately quadratic, and experimentally validates the theoretical results.

Critical strengths
  1. The formulation in this paper is very clear and easy to understand. It integrates the computational processes of the QK retrieval and OV decoding stages in single-head attention, taking into account the impact of the weighted output from the QK stage on decoding. Compared to an “OV-Only” analysis, this approach more closely approximates the complete attention computation process.
  2. This paper provides relatively detailed experimental validation of its theoretical modeling and conclusions.
Critical weaknesses

1.The assumption that all token representations are random and sampled from the unit sphere may not hold true in general. In fact, this assumption differs significantly from real-world attention mechanisms or Transformers.

Questions for authors

1.Is “∥Ae∥2≤∥WOV∥op∥e∥2\lVert Ae \rVert_2 \leq \lVert W_OV\rVert_{op}\lVert e \rVert_2” in Appendix C.5 a typographical error?

2.Page 9 of this article states: “The capacity scale experiments are exact and hence bounded by the intrinsic cost of the object. At capacity the number of associations is T∗=Θ(dh2/log⁡dh)T^* = \Theta(d^2_h / \log d_h)” Where does the conclusion regarding “T∗=Θ(dh2/log⁡dh)T^* = \Theta(d^2_h / \log d_h)” come from? Is it based on mathematical derivation or experimentation?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Official Comment by Authors

Dear reviewer nAsE,

As the discussion period draws to a close, we would like to kindly check if you have any remaining questions or concerns regarding our responses.

We appreciate your thoughtful feedback and would be happy to provide further clarification if needed. Thank you again for your time and consideration.

Best,

Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.