- 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 and matrices. The problem is significant, but I favor weak rejection.
Critical strengths
-
The presentation is nice and easy to read.
-
The main construction is clear, with resonable treatment of shared parameters and operator norms.
Critical weaknesses
-
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.
-
The target output tokens are required to be pairwise distinct, implying . However, when and are polynomial in , I am not quite clear on whether thi setting guarantees pairwise distinctness.
-
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
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.
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<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<d but still use one embedding per vocabulary item and only prove a bound linear in dh, 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 dh. Under these strictly more practical assumptions we prove T=Ω(dh2/logdh) whenever S,N=poly(dh), which is the theoretical account consistent with the quadratic in dh 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) 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)≤dh2 and (Tlog(c2TN/δ2)≤dh2) given in Section E, which combine into the common sufficient scaling T=Ω(dh2/log(dhmax{S,N}/δ)). When S,N=poly(dh) and δ is fixed, we have log(dhmax{S,N}/δ)=Θ(logdh), so the capacity reduces to the form T=Ω(dh2/logdh) mentioned between lines 866 and 874. The pairwise distinctness assumption is what makes the unembedding vectors uy1,…,uyT 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 and then held fixed, because this is the regime in which our concentration notion, the spherical sub-Gaussian bound on ⟨uj,uyt⟩, the sub-exponential control of the decoder interference Irt,j, and the Matrix Bernstein bound on WOV′ are valid. The construction then exhibits WQK and WOV 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 WQK and WOV 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 WQK and a scale with orthogonal head basis change for the WOV/unembedding pair. Their leading singular subspaces nevertheless overlap by ≈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.