Abstract
Transformer architectures have demonstrated remarkable performance across a wide array of domains, yet the theoretical underpinnings of their self-attention mechanism remain partially understood. A central question concerns the "expressive flexibility" of self-attention matrices, particularly when the query dimension ($d$) is significantly smaller than the sequence length ($n$). This paper investigates the capacity of self-attention to represent sparse patterns. We prove that while verifying the representability of a specific pattern is NP-hard for $d > 1$, self-attention can efficiently approximate any $k$-sparse pattern with a query dimension that scales only logarithmically with $n$. Our findings provide a theoretical justification for the empirical success of Transformers with relatively small query dimensions.
Introduction
The self-attention mechanism is the core component of the Transformer architecture, enabling models to capture complex dependencies within sequences. In practical applications, the query and key dimension $d$ is typically much smaller than the sequence length $n$ (e.g., $d=64$ for $n=512$ in BERT). This disparity raises a fundamental theoretical question: how much expressive power is sacrificed by maintaining a small $d$? Can such low-dimensional projections still capture the intricate, sparse interaction patterns observed in real-world data? This work bridges the gap between the empirical "unreasonable effectiveness" of Transformers and our theoretical understanding of their representational limits.
Empirical Motivation
To ground the theoretical analysis, we examine the attention patterns produced by pre-trained models such as DistilBERT. Visualizations of these matrices reveal that attention is rarely dense; instead, it typically concentrates on a few key tokens, forming sparse structures like diagonals or localized clusters. These observations suggest that the ability to represent sparse patterns is a critical requirement for the self-attention mechanism.
Methodology
The study employs a combination of computational complexity theory and high-dimensional geometry to analyze the representational capacity of self-attention:
- NP-Hardness Analysis: By defining "weak approximation"—where the model correctly identifies the relative importance of elements—the authors show that determining if a pattern is representable is NP-hard for any $d > 1$, utilizing the theory of dot product graphs.
- Constructive Approximation: Focusing on $k$-sparse matrices, the authors provide a constructive proof for their approximation using the Johnson-Lindenstrauss (JL) lemma.
- Random Projections: The research demonstrates that random projections, specifically using Stiefel matrices for improved concentration, can map high-dimensional patterns into a lower-dimensional space while preserving the essential structure of attention weights.
Key Insights
A primary discovery is the Logarithmic Law: a query dimension $d = O(k^2 \log n)$ is sufficient to approximate $k$-sparse patterns. This explains why Transformers remain powerful even with small query dimensions relative to sequence length. Furthermore, the self-attention module possesses inherent flexibility; even with fixed internal weights ($W_Q, W_K$), the mechanism can approximate a vast variety of sparse patterns by varying the input $X$. This highlights that the architecture's strength lies in the mechanism itself rather than just the learned parameters.
Results and Discussion
Theoretical bounds indicate that for a $k$-sparse matrix, the required $d$ scales as $O(k^2 \log n)$. Empirical simulations using synthetic sparse matrices (unions of random permutation matrices) verify this scaling, showing that the actual $d$ required often grows even slower than the theoretical upper bound while strictly following the predicted logarithmic curve. The proof is constructive, yielding a randomized polynomial-time algorithm to identify inputs $X$ that generate a target sparse pattern.
Limitations and Future Work
While this work clarifies the expressive power of a single self-attention head, several avenues for future research remain. The interactions within multi-head attention and the compounding effects of depth in multi-layer stacks are not yet fully characterized. Additionally, while "weak approximation" suffices for many tasks, "strong approximation" (matching exact values) may impose stricter constraints. Finally, the analysis primarily addresses sparse patterns; the representation of dense, global dependencies warrants further investigation.
Conclusion
This paper provides a theoretical foundation for the flexibility of self-attention. By proving that sparse patterns can be efficiently represented with a query dimension scaling logarithmically with sequence length, we offer a mathematical explanation for the efficiency and versatility of the Transformer architecture across diverse domains.
Summary updated