# On the Optimal Memorization Capacity of Transformers

arXiv: https://arxiv.org/abs/2409.17677 · HTML: https://mlsanity.com/paper/2409.17677/

## Key facts

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

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Scalable Diffusion Models with Transformers](https://mlsanity.com/paper/2212.09748/) (2022)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Vision Transformers Need Registers](https://mlsanity.com/paper/2309.16588/) (2023)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [MetaFormer Is Actually What You Need for Vision](https://mlsanity.com/paper/2111.11418/) (2021)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [Mamba-R: Vision Mamba ALSO Needs Registers](https://mlsanity.com/paper/2405.14858/) (2024)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input](https://mlsanity.com/paper/2305.18699/) (2023)
- [Sequence Length Independent Norm-Based Generalization Bounds for Transformers](https://mlsanity.com/paper/2310.13088/) (2023)
- [Approximation Rate of the Transformer Architecture for Sequence Modeling](https://mlsanity.com/paper/2305.18475/) (2023)
- [Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot](https://mlsanity.com/paper/2406.06893/) (2024)
- [What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Tasks](https://mlsanity.com/paper/2404.01601/) (2024)

## Built on by (most cited first, 10 of 10)

- [How much do language models memorize?](https://mlsanity.com/paper/2505.24832/) (2025)
- [Understanding Factual Recall in Transformers via Associative Memories](https://mlsanity.com/paper/2412.06538/) (2024)
- [Unveiling the Basin-Like Loss Landscape in Large Language Models](https://mlsanity.com/paper/2505.17646/) (2025)
- [Strong Memory, Weak Control: An Empirical Study of Executive Functioning in LLMs](https://mlsanity.com/paper/2504.02789/) (2025)
- [Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective](https://mlsanity.com/paper/2504.13558/) (2025)
- [Approximation Bounds for Transformer Networks with Application to Regression](https://mlsanity.com/paper/2504.12175/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Memory Limitations of Prompt Tuning in Transformers](https://mlsanity.com/paper/2509.00421/) (2025)
- [Analyzing the Power of Chain of Thought through Memorization Capabilities](https://mlsanity.com/paper/2511.01190/) (2025)
- [Approximation Error Upper and Lower Bounds for H"older Class with Transformers](https://mlsanity.com/paper/2605.07463/) (2026)

## 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.