# Memorization Capacity of Multi-Head Attention in Transformers

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 48 references that are in the map.
- First posted on arXiv 3 Jun 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [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)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Transformer Feed-Forward Layers Are Key-Value Memories](https://mlsanity.com/paper/2012.14913/) (2020)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [Scaling Vision Transformers to 22 Billion Parameters](https://mlsanity.com/paper/2302.05442/) (2023)
- [Hopfield Networks is All You Need](https://mlsanity.com/paper/2008.02217/) (2020)
- [Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth](https://mlsanity.com/paper/2103.03404/) (2021)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Vision Transformers provably learn spatial structure](https://mlsanity.com/paper/2210.09221/) (2022)
- [Low-Rank Bottleneck in Multi-head Attention Models](https://mlsanity.com/paper/2002.07028/) (2020)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [Your Transformer May Not be as Powerful as You Expect](https://mlsanity.com/paper/2205.13401/) (2022)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformers](https://mlsanity.com/paper/2205.08078/) (2022)
- [Network size and weights size for memorization with two-layers neural networks](https://mlsanity.com/paper/2006.02855/) (2020)
- [An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks](https://mlsanity.com/paper/2106.07724/) (2021)

## Built on by (most cited first, 30 of 40)

- [Challenges and Applications of Large Language Models](https://mlsanity.com/paper/2307.10169/) (2023)
- [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)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)](https://mlsanity.com/paper/2407.01079/) (2024)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [Taming Knowledge Conflicts in Language Models](https://mlsanity.com/paper/2503.10996/) (2025)
- [Undesirable Memorization in Large Language Models: A Survey](https://mlsanity.com/paper/2410.02650/) (2024)
- [Prompting a Pretrained Transformer Can Be a Universal Approximator](https://mlsanity.com/paper/2402.14753/) (2024)
- [Mixture of Parrots: Experts improve memorization more than reasoning](https://mlsanity.com/paper/2410.19034/) (2024)
- [What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Tasks](https://mlsanity.com/paper/2404.01601/) (2024)
- [Superiority of Multi-Head Attention in In-Context Linear Regression](https://mlsanity.com/paper/2401.17426/) (2024)
- [Do LLMs dream of elephants (when told not to)? Latent concept association and associative memory in transformers](https://mlsanity.com/paper/2406.18400/) (2024)
- [How Transformers Utilize Multi-Head Attention in In-Context Learning? A Case Study on Sparse Linear Regression](https://mlsanity.com/paper/2408.04532/) (2024)
- [Next-token prediction capacity: general upper bounds and a lower bound for transformers](https://mlsanity.com/paper/2405.13718/) (2024)
- [On the Optimal Memorization Capacity of Transformers](https://mlsanity.com/paper/2409.17677/) (2024)
- [Understanding Addition and Subtraction in Transformers](https://mlsanity.com/paper/2402.02619/) (2024)
- [On the Benefits of Rank in Attention Layers](https://mlsanity.com/paper/2407.16153/) (2024)
- [Global Convergence in Training Large-Scale Transformers](https://mlsanity.com/paper/2410.23610/) (2024)
- [MeMo: Towards Language Models with Associative Memory Mechanisms](https://mlsanity.com/paper/2502.12851/) (2025)
- [Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective](https://mlsanity.com/paper/2504.13558/) (2025)
- [Memory Limitations of Prompt Tuning in Transformers](https://mlsanity.com/paper/2509.00421/) (2025)
- [The Effect of Attention Head Count on Transformer Approximation](https://mlsanity.com/paper/2510.06662/) (2025)
- [State space models can express n-gram languages](https://mlsanity.com/paper/2306.17184/) (2023)
- [When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective](https://mlsanity.com/paper/2503.11272/) (2025)
- [Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regression](https://mlsanity.com/paper/2508.07571/) (2025)
- [Memorization in Attention-only Transformers](https://mlsanity.com/paper/2411.10115/) (2024)
- [Exact Sequence Interpolation with Transformers](https://mlsanity.com/paper/2502.02270/) (2025)

## Abstract (arXiv)

Transformers have become the go-to architecture for language and vision tasks, yet their theoretical properties, especially memorization capacity, remain elusive. This paper investigates the memorization abilities of multi-head attention mechanisms, examining how many example sequences they can memorize, as a function of the number of heads and sequence length. Motivated by experimental findings on vision transformers, we introduce novel assumptions about the linear independence of input data, distinct from the commonly used general-position assumption. Under these assumptions, we demonstrate that an attention layer with H heads, dimension d, and context size n < d, featuring Theta(Hd2) parameters, can memorize Omega(Hn) examples. Our analysis sheds light on how different attention heads handle various example sequences, aided by the softmax operator's saturation property. We validate our findings through experiments on synthetic data.