Strassen Attention, Split VC Dimension and Compositionality in Transformers
Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez, Tomasz Steifer, Germán Pizarro, Matías Fuentes, Francisco Meza, Cristian B. Calderon, Cristóbal Rojas · 2025
Read Strassen Attention, Split VC Dimension and Compositionality in Transformers by Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez, Tomasz Steifer, Germán Pizarro, Matías Fuentes, Francisco Meza, Cristian B. Calderon, Cristóbal Rojas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19215.txt.
Introduction
Alexander Kozachinskiy and eight co-authors prove that one-layer softmax transformers cannot solve three reasoning tasks, then fix them with a new attention form. Their paper from twenty twenty-five is billed as the first such limit proof at any precision, even unbounded. The tasks probe triples of tokens and two kinds of composition: functions and binary relations. Standard attention fails all three in principle.
Their Strassen attention passes the same tasks in a one-layer build. Its run time stays sub-cubic, which scales better than past higher-order rivals. Bench tests compare it with standard, higher-order, and triangular attention. Strassen wins clearly on the test tasks. The authors frame theory as a compass: know the wall, then design the door.
Catalog record
| CREATOR | Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez, Tomasz Steifer, Germán Pizarro, Matías Fuentes, Francisco Meza, Cristian B. Calderon, Cristóbal Rojas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-19215
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Strassen Attention, Split VC Dimension and Compositionality in Transformers Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez, Tomasz Steifer, Germán Pizarro, Matías Fuentes, Francisco Meza, Cristian B. Calderon, Cristóbal Rojas Abstract 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. 1 Introduction What tasks can Transformers solve? A fundamental question in modern AI is understanding why and under which conditions a given deep network architecture succeeds or fails on a given task. Numerous recent works have shown that tasks requiring compositional reasoning stand out as particularly challenging [ 6 , 24 , 16 , 15 ] . Compositionality refers to the ability of composing blocks of knowledge to generate new content or solve new tasks, and is believed to play a major role in the emergence of systematic generalization in language [ 17 , 4 ] ; making the question for these kind of tasks even more relevant. To address this problem, benchmark datasets such as SCAN [ 14 ] , PCFG [ 11 ] , CLUTRR [ 22 ] or CoGS [ 13 ] have been introduced. Moreover, different empirical methods have been developed to test, quantify and compare compositional capabilities [ 12 ] , as well as to assess the impact of design choices on the performance of Transformers on compositional tasks [ 18 ] . While many of these works provide strong empirical evidence that Transformers may suffer from inherent limitations for compositional tasks [ 8 ] , our current theoretical understanding of the underlying phenomenon remains limited. Here, we take a deeper dive into the problem and aim at contributing to the study of compositionality in Transformers on a more basic mathematical level. As we shall see, this allows us to pin down simple theoretical obstacles that make compositionality hard for the standard Transformer architecture. In turn, we can devise a new attention mechanism, which transcends these basic limitations. Theoretical limitations of Transformers A natural first step to explain why models struggle with some tasks is to study their expressivity — whether a given architecture is in-principle capable of solving the task in question. That is, whether there exists a choice of parameters that results in a model computing the function underlying the task solutions. If the answer is positive, then the chances are that the difficulty lies in efficiently learning the appropriate parameters. If the answer is negative, then a formal proof of this fact can be directly related to the poor performance observed in practice. The first theoretical limitations of this sort were obtained for Transformers using hardmax attention [ 10 ] . Instead of computing attention as a convex combination of all input tokens using softmax , one takes a single token where the attention is maximal. Using this simplification, Hahn showed that hardmax Transformers with O(1) layers cannot compute formal languages such as PARITY, MAJORITY, or Dyck-1. Theoretical limitations against softmax Transformers have recently been obtained by employing a different proof technique, one based on communication complexity [ 19 ] . The idea is to show that a Transformer solving a given task can be used to construct a corresponding communication protocol for a problem whose communication complexity is known. From this, one obtains lower bounds on the size of Transformers capable of solving the task for inputs of a given length. In [ 19 ] , for example, the authors apply this technique to show that any one-layer softmax Transformer that can compute the composition of two functions must have n^{\Omega(1)} embedding dimension, where n is the size of the input. Crucially, for this conclusion to hold, one must assume that the Transformer works with a relatively low number of precision bits, namely sub-linear in n . The technique has subsequently been applied to show lower bounds for other tasks such as string equality [ 3 ] and Match3 [ 20 ] (see Section 3.2.2 for a definition). Overcoming Transformers limitations Equipped with a better theoretical understanding of why Transformers struggle with some tasks, the next question is how they can guide research towards the construction of more expressive machines. A key observation is that the standard attention mechanism can only see interactions between pairs of tokens, whereas compositional tasks require to reason about the interaction of three or more tokens simultaneously [ 2 , 20 ] . Consequently, suitably modified attention mechanisms have been proposed, which would track interactions between more than two tokens. For instance, triangular attention [ 2 ] (see Section 2 for a definition) outperforms standard attention in compositional tasks such as CLUTRR [ 22 ] or CoGS [ 13 ] . Similarly, it has been shown that higher-order tensor attention embedded in a constant size one-layer Transformer can theoretically solve Match3, a task that cannot be solved by the standard attention [ 20 ] . However, both these mechanisms suffer from a significant increase in running-time complexity, e.g., order 3 requires cubic-time, limiting its scalability and potentially affecting its practical relevance. In the case of triangular attention, the mechanism works with an adjacency matrix of a graph (in which case it is square-time in the size of the graph). It is possible to produce an adjacency matrix from the sequence of tokens, as already shown in Bergen et al. [2] , but this increases the complexity to cubic. The higher-order tensor attention, on top of being cubic-time as well, has been only considered in theoretical work and has not been evaluated empirically yet. Our contributions In this work we aim at addressing these fundamental questions from complementary angles. Our main results can be summarized as follows: • We present a new technique for proving theoretical limitations. Since previous results establishing limitations for softmax transformers are based on communication complexity, they only apply to transformers that store numbers with relatively few precision bits. This raises the question – would the use of long arithmetic help to circumvent these limitations? In this paper, we answer this question negatively. In order to establish that, we introduce a