# On the Expressive Power of Self-Attention Matrices

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 46 references that are in the map.
- First posted on arXiv 7 Jun 2021.

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

- [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)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [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)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Scaling Up Visual and Vision-Language Representation Learning With Noisy Text Supervision](https://mlsanity.com/paper/2102.05918/) (2021)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [ViViT: A Video Vision Transformer](https://mlsanity.com/paper/2103.15691/) (2021)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Energy and Policy Considerations for Deep Learning in NLP](https://mlsanity.com/paper/1906.02243/) (2019)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (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)
- [On the Relationship between Self-Attention and Convolutional Layers](https://mlsanity.com/paper/1911.03584/) (2019)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [ProGen: Language Modeling for Protein Generation](https://mlsanity.com/paper/2004.03497/) (2020)
- [Fast Transformers with Clustered Attention](https://mlsanity.com/paper/2007.04825/) (2020)
- [Low-Rank Bottleneck in Multi-head Attention Models](https://mlsanity.com/paper/2002.07028/) (2020)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Orthogonal Estimation of Wasserstein Distances](https://mlsanity.com/paper/1903.03784/) (2019)
- [On the Ability and Limitations of Transformers to Recognize Formal Languages](https://mlsanity.com/paper/2009.11264/) (2020)
- [Recycling Randomness with Structure for Sublinear time Kernel Expansions](https://mlsanity.com/paper/1605.09049/) (2016)
- [Demystifying Orthogonal Monte Carlo and Beyond](https://mlsanity.com/paper/2005.13590/) (2020)
- [Structured adaptive and random spinners for fast machine learning computations](https://mlsanity.com/paper/1610.06209/) (2016)

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

- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [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)
- [FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inference](https://mlsanity.com/paper/2502.20766/) (2025)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [The Expressive Power of Low-Rank Adaptation](https://mlsanity.com/paper/2310.17513/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought](https://mlsanity.com/paper/2505.12514/) (2025)
- [Found in the Middle: How Language Models Use Long Contexts Better via Plug-and-Play Positional Encoding](https://mlsanity.com/paper/2403.04797/) (2024)
- [JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attention](https://mlsanity.com/paper/2310.00535/) (2023)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [How Smooth Is Attention?](https://mlsanity.com/paper/2312.14820/) (2023)
- [When Do Prompting and Prefix-Tuning Work? A Theory of Capabilities and Limitations](https://mlsanity.com/paper/2310.19698/) (2023)
- [SampleAttention: Near-Lossless Acceleration of Long Context LLM Inference with Adaptive Structured Sparse Attention](https://mlsanity.com/paper/2406.15486/) (2024)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input](https://mlsanity.com/paper/2305.18699/) (2023)
- [Sumformer: Universal Approximation for Efficient Transformers](https://mlsanity.com/paper/2307.02301/) (2023)
- [Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics](https://mlsanity.com/paper/2405.04669/) (2024)
- [Prompting a Pretrained Transformer Can Be a Universal Approximator](https://mlsanity.com/paper/2402.14753/) (2024)
- [In-Context Learning with Transformers: Softmax Attention Adapts to Function Lipschitzness](https://mlsanity.com/paper/2402.11639/) (2024)
- [Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot](https://mlsanity.com/paper/2406.06893/) (2024)
- [Can Vision Transformers Perform Convolution?](https://mlsanity.com/paper/2111.01353/) (2021)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [Sample Complexity and Representation Ability of Test-time Scaling Paradigms](https://mlsanity.com/paper/2506.05295/) (2025)
- [ProxyAttn: Guided Sparse Attention via Representative Heads](https://mlsanity.com/paper/2509.24745/) (2025)
- [Self-attention Presents Low-dimensional Knowledge Graph Embeddings for Link Prediction](https://mlsanity.com/paper/2112.10644/) (2021)

## Abstract (arXiv)

Transformer networks are able to capture patterns in data coming from many domains (text, images, videos, proteins, etc.) with little or no change to architecture components. We perform a theoretical analysis of the core component responsible for signal propagation between elements, i.e. the self-attention matrix. In practice, this matrix typically exhibits two properties: (1) it is sparse, meaning that each token only attends to a small subset of other tokens; and (2) it changes dynamically depending on the input to the module. With these considerations in mind, we ask the following question: Can a fixed self-attention module approximate arbitrary sparse patterns depending on the input? How small is the hidden size d required for such approximation? We make progress in answering this question and show that the self-attention matrix can provably approximate sparse matrices, where sparsity is in terms of a bounded number of nonzero elements in each row and column. While the parameters of self-attention are fixed, various sparse matrices can be approximated by only modifying the inputs. Our proof is based on the random projection technique and uses the seminal Johnson-Lindenstrauss lemma. Our proof is constructive, enabling us to propose an algorithm for finding adaptive inputs and fixed self-attention parameters in order to approximate a given matrix. In particular, we show that, in order to approximate any sparse matrix up to a given precision defined in terms of preserving matrix element ratios, d grows only logarithmically with the sequence length L (i.e. d = O(log L)).