# Strassen Attention, Split VC Dimension and Compositionality in Transformers

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 27 references that are in the map.
- First posted on arXiv 31 Jan 2025.

## Builds on (most cited first, 15 of 15)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Deep Learning: A Critical Appraisal](https://mlsanity.com/paper/1801.00631/) (2018)
- [CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text](https://mlsanity.com/paper/1908.06177/) (2019)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Making Transformers Solve Compositional Tasks](https://mlsanity.com/paper/2108.04378/) (2021)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [A Benchmark for Compositional Visual Reasoning](https://mlsanity.com/paper/2206.05379/) (2022)
- [Systematic Generalization with Edge Transformers](https://mlsanity.com/paper/2112.00578/) (2021)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [Faster Matrix Multiplication via Asymmetric Hashing](https://mlsanity.com/paper/2210.10173/) (2022)

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

- [Language models can learn implicit multi-hop reasoning, but only if they have lots of training data](https://mlsanity.com/paper/2505.17923/) (2025)
- [Fast and Simplex: 2-Simplicial Attention in Triton](https://mlsanity.com/paper/2507.02754/) (2025)
- [Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)](https://mlsanity.com/paper/2503.22076/) (2025)
- [How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers](https://mlsanity.com/paper/2604.17935/) (2026)
- [Indexing: the Beginning and the End](https://mlsanity.com/paper/2607.22361/) (2026)
- [Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers](https://mlsanity.com/paper/2602.02707/) (2026)
- [Interleaved Head Attention](https://mlsanity.com/paper/2602.21371/) (2026)
- [Positional versus Symbolic Attention Heads: Learning Dynamics, RoPE Geometry, and Length Generalization](https://mlsanity.com/paper/2605.31558/) (2026)
- [Beyond Pairwise Attention: Higher-Order Modular Attention for Efficient Sequence Learning](https://mlsanity.com/paper/2603.11133/) (2026)
- [On the Computational Hardness of Transformers](https://mlsanity.com/paper/2603.11332/) (2026)
- [The Illusion of Replacement: Rethinking Specialized Machine Learning Models in the Foundation Model Era](https://mlsanity.com/paper/2608.28980/) (2026)
- [VC Dimension and Expressivity of Real-Valued Transformers](https://mlsanity.com/paper/2609.31999/) (2026)

## Abstract (arXiv)

We propose the first method to show theoretical limitations for one-layer softmax transformers with arbitrarily many precision bits (even infinite). We establish those limitations for three tasks that require advanced reasoning. The first task, Match 3 (Sanford et al., 2023), requires looking at all possible token triplets in an input sequence. The second and third tasks address compositionality-based reasoning: function composition (Peng et al., 2024) and binary relations composition, respectively. We formally prove the inability of one-layer softmax Transformers to solve any of these tasks. To overcome these limitations, we introduce Strassen attention and prove that, equipped with this mechanism, a one-layer transformer can in principle solve all these tasks. Importantly, we show that it enjoys sub-cubic running-time complexity, making it more scalable than similar previously proposed mechanisms, such as higher-order attention (Sanford et al., 2023). To complement our theoretical findings, we experimentally studied Strassen attention and compared it against standard (Vaswani et al, 2017), higher-order attention (Sanford et al., 2023), and triangular attention (Bergen et al. 2021). Our results help to disentangle all these attention mechanisms, highlighting their strengths and limitations. In particular, Strassen attention outperforms standard attention significantly on all the tasks. Altogether, understanding the theoretical limitations can guide research towards scalable attention mechanisms that improve the reasoning abilities of Transformers.