On the Expressive Power of Self-Attention Matrices

Transformer models, introduced by Vaswani et al., have become dominant in NLP, vision, and biology due to their ability to model long-range dependencies via self-attention. Early works proved their universal approximation capabilities when stacking multiple layers, but the expressive power of single-layer self-attention with fixed weights remained less understood. Empirical studies observed that self-attention matrices are often sparse and input-dependent, hinting at an inherent ability to encode complex patterns efficiently. Recent theoretical efforts focused on large hidden dimensions or multi-head structures, leaving a gap in understanding the minimal conditions under fixed parameters. This paper situates itself in this context, aiming to quantify the input-driven expressive capacity of single-layer self-attention, especially for sparse patterns, which are prevalent in real data.

Despite the widespread use of Transformers, there is limited theoretical understanding of how fixed-parameter self-attention can approximate diverse sparse matrices. Practitioners observe input-dependent sparsity patterns, but the minimal hidden size d needed for such approximation remains unknown. The core challenge is to determine whether, with fixed WQ and WK, the model can adaptively encode arbitrary sparse structures solely through input modifications, and how d scales with sequence length L. Addressing this problem is crucial for designing efficient models that balance expressiveness and computational cost, especially for long sequences where high-dimensional representations are costly.

The key innovation is applying random projection techniques, specifically the Johnson-Lindenstrauss lemma, to analyze the approximation capacity of fixed self-attention weights. The authors show that by constructing appropriate inputs, the self-attention matrix can approximate any sparse matrix with element ratio preservation, with the embedding dimension d only growing as O(log L). This approach departs from prior multi-layer or multi-head analyses, focusing on the fundamental single-layer capacity. The constructive proof provides an explicit algorithm for input and parameter selection, bridging theoretical guarantees with practical implementation. This insight fundamentally shifts understanding of self-attention's expressive limits, highlighting its adaptability even with fixed weights.

• �� Define the self-attention module, including unnormalized USAM and normalized SAM matrices, with parameters WQ, WK. • Characterize sparse matrices A with bounded non-zero elements per row/column and γ-variation bounds. • Construct matrix B using log-transform of A’s non-zero elements, approximating A via exponential mappings. • Perform singular value decomposition of B into UΣV>, then compress D=UΣ and V using random orthogonal projections Y, forming X(1), X(2). • Set WQ, WK to ensure XWQWKX> approximates B, leveraging the properties of the projections. • Use Johnson-Lindenstrauss lemma to guarantee element ratio preservation with high probability, controlling approximation error. • Develop an iterative sampling algorithm to find Y, then compute X, WQ, WK, ensuring the self-attention matrix approximates A within bounds. • Extend analysis to causal self-attention matrices, maintaining the logarithmic dependence on L.

The experiments generate sparse matrices A with controlled non-zero counts and variation bounds, then vary sequence length L from 512 to 3072. For each L, they compute the minimal d satisfying the approximation bounds, repeating multiple trials for statistical robustness. Results show empirical d scales with log L, consistent with theory, and is often significantly smaller than the upper bound. Additional tests vary the sample size Q for the random projections, confirming stability of d. Visualizations of attention maps verify the sparsity pattern alignment between A and the approximated matrix M, demonstrating the practical effectiveness of the approach across different parameter regimes.

The empirical results strongly support the theoretical claim that d = O(log L) suffices for accurate approximation of sparse matrices. The minimal d observed in practice is often well below the theoretical upper bound, confirming the tightness of the analysis. The experiments also validate the robustness of the method across different sparsity levels and variation bounds, with consistent preservation of element ratios. Extending to causal matrices, similar logarithmic scaling was observed, indicating broad applicability. These findings establish a solid foundation for efficient, input-dependent approximation in fixed-parameter self-attention models.

This theoretical insight enables the design of more efficient Transformers capable of handling long sequences with low-dimensional embeddings. Practical applications include NLP tasks like long document modeling, video sequence analysis, and protein structure prediction, where input sparsity is prevalent. The ability to approximate complex patterns with fixed weights reduces training and inference costs, making models more scalable. Industry-wise, this can lead to resource-efficient deployment in edge devices and real-time systems, broadening the scope of Transformer-based solutions.

The analysis assumes matrices are sparse and satisfy specific bounded variation conditions, which may not hold universally. The probabilistic nature of the proof means worst-case scenarios could require multiple sampling attempts, increasing computational overhead. Although the theoretical dimension d is small, actual implementation for very large L may still be computationally intensive. Future work should explore relaxing assumptions, improving algorithm efficiency, and validating on real datasets with diverse sparsity patterns.