mlsanityData to 7 Oct 2026

On the Optimal Memorization Capacity of Transformers

arXiv 2409.17677 ↗First posted 26 Sep 2024cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

Recent research in the field of machine learning has increasingly focused on the memorization capacity of Transformers, but how efficient they are is not yet well understood. We demonstrate that Transformers can memorize labels with tildeO(√N) parameters in a next-token prediction setting for N input sequences of length n, which is proved to be optimal up to logarithmic factors. This indicates that Transformers can efficiently perform memorization with little influence from the input length n owing to the benefit of parameter sharing. We also analyze the memorization capacity in the sequence-to-sequence setting, and find that tildeO(√nN) parameters are not only sufficient, but also necessary at least for Transformers with hardmax. These results suggest that while self-attention mechanisms can efficiently identify input sequences, the feed-forward network becomes a bottleneck when associating a label to each token.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 33 of its 46 references that are in the map. First posted on arXiv 26 Sep 2024.

Builds on

33 of 46 references.

References · 33

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  4. 2022Scalable Diffusion Models with Transformerscited by 5,931
  5. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,854
  6. 2017A Broad-Coverage Challenge Corpus for Sentence Understanding through Inferencecited by 2,665
  7. 2019Optuna: A Next-generation Hyperparameter Optimization Frameworkcited by 2,455
  8. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  9. 2017Deep Setscited by 1,394
  10. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  11. 2023Vision Transformers Need Registerscited by 844
  12. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
21 more
  1. 2021MetaFormer Is Actually What You Need for Visioncited by 523
  2. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  3. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  4. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  5. 2023Representational Strengths and Limitations of Transformerscited by 132
  6. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 82
  7. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  8. 2021Universal Approximation of Functions on Setscited by 62
  9. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 46
  10. 2024Mamba-R: Vision Mamba ALSO Needs Registerscited by 41
  11. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  12. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 39
  13. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  14. 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
  15. 2023Approximation Rate of the Transformer Architecture for Sequence Modelingcited by 28
  16. 2023Sequence Length Independent Norm-Based Generalization Bounds for Transformerscited by 28
  17. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 21
  18. 2024What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Taskscited by 19
  19. 2021On the rate of convergence of a classifier based on a Transformer encodercited by 16
  20. 2024Next-token prediction capacity: general upper bounds and a lower bound for transformerscited by 11
  21. 2023Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at Irregularly Spaced Datacited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 8; 2026: 1.

10 papers.

  1. 2025How much do language models memorize?cited by 53
  2. 2024Understanding Factual Recall in Transformers via Associative Memoriescited by 45
  3. 2025Unveiling the Basin-Like Loss Landscape in Large Language Modelscited by 13
  4. 2025Strong Memory, Weak Control: An Empirical Study of Executive Functioning in LLMscited by 6
  5. 2025Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspectivecited by 5
  6. 2025Approximation Bounds for Transformer Networks with Application to Regressioncited by 4
  7. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  8. 2025Memory Limitations of Prompt Tuning in Transformerscited by 4
  9. 2025Analyzing the Power of Chain of Thought through Memorization Capabilitiescited by 1
  10. 2026Approximation Error Upper and Lower Bounds for H"older Class with Transformerscited by 0