Strassen Attention, Split VC Dimension and Compositionality in Transformers
Authors: Alexander Kozachinskiy
Felipe Urrutia
Hector Ignacio Jimenez Orellana
Tomasz Steifer
Germán Pizarro
Matías Daniel Fuentes Álvarez
Francisco Meza Vásquez
Cristian Buc Calderon
Cristobal Rojas
Venue: NeurIPS 2025 poster ()
Keywords: Transformers
compositionality
attention mechanisms
lower bounds
Primary area: deep_learning
TL;DR: We give a method of obtaining lower bounds on infinite-precision standard-attention transformers, and propose a more scalable version of higher-order attention

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.

Strassen Attention, Split VC Dimension and Compositionality in Transformers
Alexander Kozachinskiy CENIA
Felipe Urrutia University of Chile & CENIA furrutia@dim, uchile.ct cl
alexander: kozachhisskyyCCnnie...l
Hector Jimenez University of Chile & CENIA hjimenez@dcc. uchile.c. cl
Tomasz Steifer
Institute of Fundamental Technological Research, Polish Academy Sciences tsteifer@ippt. pan.pl
Germán Pizarro CENIA german pww..ro@cearaa..cccll
Matías Fuentes
IMC, Pontifical Catholic University of Chile
mdfuentes4@uc. cl
Francisco Meza
Cristian B. Calderon CENIA cristian www.benia.anc....
IMC, Pontifical Catholic University of Chile fjmezal@uc.
Cristóbal Rojas
Institute for Mathematical and Computational Engincering Pontifical Catholic University of Chile & CENIA luis ro luis.rojas@uc.cr jojasuuc.c1
Abstract
We propose the first method 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 input sequence. The second and third tasks address compositionality- function composition (Peng et al., 2024) and binary relations composition, spectively. We formally prove the inability of one-layer softmax Transformers to solve any of these tasks. To overcome these limitations, attention and prove that, equipped with this mechanism, a one-layer transformer in principle solve all these tasks. Importantly, show that it enjoys sub-cubic running-ting time complexity, making it more scalable than similar previously proposed mechanisms, such higher-order attention (Sanford et al., 2023). To complement our theoretical findings, we experimentally studied Strassen attention and compared it against standard (Vaswani 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.
reasoning:
introduce Strassen
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

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 fails on given task. Numerous recent works have shown that tasks requiring compositional reasoning stand out as particularly challenging [6] [4 [6 [5]. 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 [T7 4 making the question for these kind of tasks even more relevant.
To address this problem, benchmark datasets such SCAN 14,, PCFG M. 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 [8]. 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 deeper dive into the problem and aim at contributing to the study of compositionality in Transformers on 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 new attention mechanism, which transcends these basic limitations.
Related work Our work can be related to two complementary lines of research which we now develop.
Theoretical limitations of Transformers. A natural first step to explain why models struggle with some tasks is to study their expressivity- whhethee 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 model computing the function underlying the task solutions. If the answer is positive, then the chances are that the difficulty lies efficiently learning the appropriate parameters. If the answer is negative, then 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 [0). Instead of computing attention as a convex combination of all input tokens using softmax, one takes single token where the attention is maximal. Using this simplification, Hahn showed that hardmax Transformers with (11) layers cannot compute formal languages such as PARITY, MAJORITY, Dyck-
Theoretical limitations against softmax Transformers have recently been obtained by employing a different proof technique, one based on communication complexity [9]. The idea is to show that a Transformer solving a given task can be used to construct a corresponding communication protocol for 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 given length. In [9), 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 2(1 embedding dimension, where 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 k 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 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 (2 or COGS [3). Similarly, it has been shown that higher-order tensor attention embedded in a constant size one-layer Transformer can thcoretically solve Match3, a task that cannot be solved by the standard attention (20). However,

---

both these mechanisms suffer from a significant increase in running-timm 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 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 comple- mentary 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 new technique for proving limitations, based on the novel notion of Splitring VC dimension.
The splitting VC dimension of a Boolean function f. denoted by Split-VC(f), is a positive integer number intended to capture the complexity of f in certain combinatorial sense. Our main technical contribution is the following:
Main Theorem. Let T be any one-layer standard attention Transformer that do arithmetic operations over real numbers with infinite precision. Denote by d. H and L. respectively, its embedding dimension, number of attention heads and size of the output MLP of T. Suppose T can compute a function f. Then it holds that max(d, H, L} 2 split- VC(f)(()
To put it differently, even idealized transformer T that manipulate numbers with infinitely many bits cannot compute a function I with large Split-VC(f) unless T has a large embedding dimension, large number of attention heads, or large output MLP. Obviously, the same limitations apply to real-life Transformers that can only manipulate numbers using some finite (however large) number of bits.
We obtain new theoretical limitations for tasks requiring complex reasoning. We apply our new method to the task of function composition (Peng et al. [99] and the Match3 (Sanford et al. (20) task, and show that previously known limitations for these tasks are also applicable to transformers that work with arbitrarily large (and even infinite) precision.
We also do this for a new task, that we name binary relation composition task. We introduce it because the function composition task can be solved by a 2-layer transformer, while for the binary relation composition task there is no apparent solution with any constant number of layers. Finally, we introduce another task that we call Quotient Binary Relation Composition (see Section S Our method allows to establish limitations for this task even for mixed transformers that can use both the standard and the triangular attention.
We develop more scalable higher-order mechanism. Previous works (e.g. (20) have shown that higher-order methods can in principle overcome these limitations, but suffer from severe scalability issues. In an attempt to address these difficulties, we present and study Strassen attention, a variation devised to be sensitive to interactions between triplets of tokens without sacrificing too much efficiency. In contrast to previous similar attention mechanisms that required running time n² for inputs of length n. our mechanism enjoys n² space and sub-cubic running time, making it more scalable. At the same time, we show that I-layer constant-size Strassen attention transformers are theoretically capable of solving all aforementioned tasks.
We empirically demonstrate the convergence of Strassen attention. Is Strassen atten- tion capable of converging to these theoretical solutions during learning? We empirically demonstrate that the answer is positive for all 4 tasks. For comparison, we have additionally evaluated all other attention mechanisms on these tasks. Our empirical findings agree with theory and show that Strassen attention: (i) outperforms the accuracy of Standard attention, (ii) achieves superior efficiency in terms of training time and computational resources when compared with other triple-wise interaction attention mechanisms.
3

---

Paper organization In Section 2 we recall the Transformer architecture and introduce our new Strassen attention mechanism. Section presentss our new lower bound method and its application to function composition, Match3, and binary relation composition tasks. In Section 4 we show that Strassen attention can be implemented in sub-cubic time, and formally prove that, principle, capable of solving the three aforementioned task. Section S presents a novel task allowing to separate the capabilities of Strassen attention from those of standard and triangular attentions. Finally, section contains our experimental findings. Due to space constraints, some proofs and experimental details are deferred to the Appendix.
2 Preliminaries
Throughout the paper, we denote [n]] = {1, [1,...,73 n. for N. For Σ, we will denote by Σ" the collection of sequences of elements of Σ of length n, and by Σ" the collection of all finite sequences. We start by briefly recalling the basics of the Transformer architecture and formally defining the attention mechanisms studied in this paper.
The main block of the Transformer layer is the attention function, formally defined length- preserving function a: (Id)* + (I")),, where is the embedding dimension. In this paper, we consider 4 types of attention functions.
Standard attention
233, receives as input a sequence z; RR i 1,..., a and outputs a sequence a, E Rd = 1.... n. computed as follows:
0; azyyy
(1)
j=1
aij Softmax, (g,k/Vá,
(2)
9 = W
kj = w*
Wxxz. xj. Vy = W'
(3)
where W W W E Rxd
Triangular attention (2) is defined for m², with input tokens indexed by pairs (i,j), i,
1..., m. Given an input {zig E Bd) Jij=1, the output is computed as follows:
0ij = Σ
(4)
1=1
0:fj Softmax e (nekez/ Va)
(5)
4i W
Whe kej = Wh aej
(6)
vay Vi Vasrys
where W", Wh V1. V22 E Rdxd
Third-order attention 20 is computed as follows:
0; aije(ty O v.)
(8)
1.t=1
aije Softmax s (qq (kr O kk)/va/))
(9)
qi W
kg W zz, Ue = Vide,
kt W xe.
(10)
22 = Vi
(11)
where W W/ Wh. V1, V/2 gdxd

---

We introduce Strassen attention, computed as follows:
0; =
Oijk((yy @ vx)
(12)
JAk=1
Gijk Softmax, j, ((fag + gshhn + hh..i///
(13)
f Wha, 9j W ha = Whaps
(14)
1j Viay,
2k = V2
(15)
where W W W V1, V/2 E Rdxd, and @ denotes the Hadamard product. See Figure Appendix A for the illustration of these attention mechanisms.
in
Definition 2.1. A one-layer Transformer T with H heads and embedding dimension is given by H attention functions Att Att (IR")" + (Rd)", a matrix Wo Rddx(dH), and an "output MLP" N: Rd R with P parameters, which is formally neural network with ReLU activation. We define the size of T as size(T) = max { H, d, P). The output of T on input T (æ1,..., ) E (IR is the sequence y (3 8n) E (IR) given by
a (b) (Atta (z))
= 1,..... H
(16)
0. = Wo
(17)
(H)
(i
y1 = M(: + ks).
(18)
So far, Transformers are defined as functions transforming sequences of vectors in Rd For the tasks we consider in this paper, we need to apply Transformers on sequences of symbols of an arbitrary finite alphabet Σ. This is done by including into the Transformer a positional encoding p: [n] x E + Rd. For a given p, an input word tr 01 ..... E E is converted into sequence of vectors:
on
I (l. Z. on,
that constitute the input for the Transformer. For our lower bounds, we make no assumptions about the function p. In our upper bounds, however, we present constructions that use reasonable, easily computable positional encodings the form p(i, o.) = a(i) + r(a.), treating positions and symbols independently.
3 Theoretical Limitations of Transformers via Split- VC dimension
We now introduce the notion of splitting dimension for Boolean function f. Lett X' be set and H (0, 1) be collection functions h X' -> {0, 1} which we will refer to as hypothesis class. We say that an hypothesis class H shatters a subset X = {I 2m } C X' if for any Boolean vector éj ..... Cm E (0, 13 there exists h E H with h(x1)) = CI. ((m)) ) = Cm The maximal m for which H shatters some X C X' of cardinality m is called the VC dimension of H (2I].
We now explain how adapt VC dimension use it as complexity measure of single function (instead of class of functions). Take a function f: E + {0, 1} and imagine we split the arguments of into two parts. One part will continue to correspond to the inputs, but the other is to be regarded as set of parumeters, so that now we can see / as a class of functions that has well-defined VC dimension. The complexity of I will be defined the maximal VC dimension that we can obtain in this way, considering all possible splittings into parameters and inputs.
Let us formalize this idea. For of positions A S [I,...,n,,, follows. Its rows (interpreted as inputs) will be indexed by all the words w E A and its columns (interpreted as parameters) by the words w² E D where B = {l...... n} \ A. Thus, M will be | [ mIIA Boolean matrix. The value of M/ (wo w²2 ) is then defined
n). we define Boolean matrix M as
M/(w', w²) f(w w²
5

---

where w' { w² E E" is obtained by merging w' and w" according to the positions indicated by A and B. i..
w w iE
A i 1
(w* "oww)
Definition 3.1. We define the splitting VC dimension of f: Σ" + {0, 13. denoted by split-VC(J] as the maximum over A S {1,... (1...., of the VC dimension of the set of columns of M understood as Boolean functions on the set of rows.
n.
Example. Consider Boolean function f: 10, + {0,1}. defined by f(x 1, 33, 33,
(x) A T2) @ (23 A T4). We claim that Split-VC(f) = To establish split-VC(f) 2 2, we consider A (1,3). The matrix Mí is constructed follows: its rows indexed by Boolean vectors
4123 E {0, 132, its columns by Boolean vectors Z204 E {0, 132, and the intersection of the row Fi and column T2 has (x1, 22, F3, T4) in it. Thus, this matrix looks follows:
T2
00
01
10
11
223
00
0
0
01
0
10
0
0
11
0
0
Columns of this matrix realize all Boolean functions the second and the third row, implying that the VC dimension of the set of columns of this matrix is at least 2. We now observe that there is no A S 21, 3, 4] such that the set of columns of M / has VC dimension least Indeed, this requires A to be of size least 2, because otherwise there are less than rows. But [A] 2 2, there are at most 4 columns, making it impossible to realize 2 = 8 different Boolean functions.
3.1 Main Theorem
In order state main Theorem, first need specify way to see Transformer computing a given boolean function f: Σ" >> {0, 1). We assume that an input word w = 0 o. is given the Transformer using n + tokens. The first n tokens are used to encode the symbols of w, while the (n + 1)-st auxiliary token (initially encoding the empty symbol) is used to encode the output f'ww) of the function being computed. More specifically, the output of the Transformer in the auxiliary token has to be a real number Vn++1. satisfying fww)= sign(yx+1). When a Transformer T fulfills this requirement for a given function f. we will say that the Transformer T computes f in an auxiliary token. We can now state our main result.
Theorem 3.2. Let be a one-layer Standund-attention Transformer and let f: E - (0, 1] be Boolean function. I computes f in an auxiliary token, then size(T) = split-VC(f)2(0),
Remark 3.3. Note that from Theorem 3.2 it follows that for any Transformer T satisfying size(T) n o11) it is impossible to compute in an auxiliary token any function f: Σ" + {0, with split-VC(J) = R(1).
3.2 Applications to three concrete tasks
We now apply Theorem 3.2 to three different tasks.
3.2.1 Function Composition
Introduced in Peng et al. [19], in this task we receive description of two functions g [n|] + [n] and h [n] + [n], and we are asked the value of h(g())) for given [n]. The task is presented to a Transformer in the form of a sequence of 2n + 1 tokens, divided in three parts. The first two parts encode the values of g and h, and the third part encodes x in a single token, where the output has to be computed. More specifically, the output has to be real number y2n+1 satisfying [y26+1 h(g(z))l 0.5. That is, with h(g(z)) being the closest integer to y2n+1.
Theorem 3.4. Let T be any lay-l standand-ateention attention Transformer with size(T) = (1)) Then T cannot solve the function composition task.

---

Proof. We show that any Transformer that solves this task can be converted into Transformer computing in the auxiliary token the following Boolean function:
Ind,: [n]
{0,
qp 1,
Ind (P1, 91 4n
otherwise,
and that this transformation requires adding just ((1) neurons to the output MLP. Indeed, by fixing 1 and setting g(1) - Pl, h(1) - ....... h(n) = On obtain that the token with æ outputs a real number y with ly h(g(1)) = ly qp, < 0.5. now remains to change the output to
ReLU((15 - y) which will be positive exactly when dp. = 1.
The result now follows from Theorem 3.2 and the following:
Lemma 3.5. (elit-VC(Ind,) 2
Proof. We claim that the VC dimension of the set of columns of M Mf Ind, with A {1}, is least n. Rows of this matrix are indexed by p1 E [n]]. and columns by vectors q1 ..... 9n E [n]". We claim that the set of all rows of M is shattered by the columns of M. Take any Boolean vector
b G1 Ch...Go Gn E {0, 1)". We need find 91 .... In [n]" such that Ind, (.,...... ( (n) q for all
[1
Q = 1, 2
i [n]. It is suffices to define q: =
G = O.
3.2.2 The Match3 task
Next, we define the Matchs i,, ml task [20). It is sequeniceto-ssquenee task. The input is presented to the Transformer as a sequence of n tokens, encoding a vector integers (pı...., Pn) E [m I|".
The output is vector (y1.....,.) v.) E I,, required satisfy:
sign(y.) {
7j k E [n] s.t.
ps + Pj + Pk= =0
(mod m)
otherwise
Note that we deliberately exclude the value p; for the input positions. This is avoid inputs that make the task trivial. Indeed, if p; 0 for some i, then the output is trivially since we always have ps + Pt + p; 0.
Theorem 3.6. Let T be any one-layer standard-attention Transformer with size(T) (1), Then T cannot solve the Matcha(n, (n, m] task for m 2n - 2.
3.2.3 Binary Relation Composition
Finally, we define the binary relation composition task. This is sequence-to-sequene task, where on input get two Boolean matrices A, B (0, 13 Vixvv The input is presented Transformer using n tokens, indexed by pairs (i,j) E [vn]², with the ji. token receiving an encoding of Ag and Bıg. In the output, have to compute the matrix of the "composition" of and B:
VR
BOAE (0, 1J
(Bo
V (As A Baz). R=1
More precisely, the output of the (i, (i,j)-th -th token for (i.j) E [vn]² has to be real number Bhy with sign(y;) = (B o A)iz- We refer to A and as "relations" on the set [vn]. with Ai indicating whether the pair (i,r) in the relation A and B, doing for relation B. For example, imagine that A = B encodes a relation for a group of researchers where two researchers and j are related they have paper in co-authorship. Then the composition B A refers the relation of "having common co-author"..
Theorem 3.7. Let T be any one-layer cannaadd-atention Transformer with size(T) = (1))) Then T' cannot solve the binary relation composition task.
7

---

Strassen attention - An efficient mechanism to solve complex tasks
Both the third-order mechanism of Sanford et al. [20] and the Strassen mechanism define attention as the interaction between three tokens (i.e., a triplet). The crucial difference is that Strassen attention computed using pairwise dot-products of vectors in the triplet, while the third-order involves coordinates products of all 3 vectors. This allows us to decompose Strassen attention scores in way matrices. Famously, the
that reduces the whole layer to the product of a constant number x n matrix product admits an ( algorithm for w < 3, with currently best known upper bound on being 2.372 77.
Theorem 4.1. Strassen attention layer can be implemented in O d))time, where is the number of input tokens, d is the embedding dimension, and w is the matrix multiplication exponent, i.e the smallest real number such that the matrix product admits an )(n")) algorithm.
Proof. Writing a, in 15 by definition, we get:
13
Σ 3.k
Ze wht.hetthhhh///e. ② vk)
a;
Σ
Eeligstoghetth 1.k
(19)
Defining matrices X,y, Raxn and & Ruaxxd by:
X15 = eio//aa Y₁,x = e0tha/va, Za.s = eusilva
P3, /a/ Vā Uk.
(XPZ)s
get expression for a; in terms of their matrix products a, (XY2).'
On top of exhibiting faster running-time, we show that, in contrast to standard attention, Strassen attention allows a one-layer Transformer to solve all the tasks described in Section 3.2
Theorem 4.2. The function composition, the binary relation composition, and the Matcha poly(n)) tasks can be solved by one-layer constant-sizz Strassen attention Transformer.
5 Disentangling Strassen from Standard and Triangular attentions
So far, we have evaluated tasks that are challenging for one-layer standard attention Transformers but (in principle) easy for one-layer Strassen attention Transformers. In this section, we extend our analysis triangular attention. As reminder, running the triangular attention mechanism on general sequence of length n, requires the creation of n22 tokens. In this regime, the triangular attention running time becomes n² However, when the input is already structured as a yn X /n matrix, one can run the triangular attention on directly, making the running time (n²/2). One such task example using structured input is the binary relation composition task. In this case, a one-layer triangular attention can perform this task with one attention head, constant embedding dimension and constant-size output MI.P.
We devise variant of the binary relation task that allows disentangle the performance of Strassen attention with that of the triangular and standard attentions, namely the quotient binary relation composition task. The latter takes inputs two Boolean matrices A, B {0, mma and
a "coloring" function col: [m]] + [m], where m = vτ. There are = m input tokens, indexed by pairs from [m]?, with the (ith token receiving Ar,; B,, and (col(i), col())) as inputs. The quotient of the composition B o A by col is a Boolean matrix B A/col E (0, 1 defined by:
f
Aki kn E [m]] s.t. Ast. = Bkgj = 1, col(ki) col(k2), and kn + k2, otherwise.
(B o A/col);;
The task is output, for all (i.j) [m]²,, real number viy such that (B A/col);; sign( To illustrate an instance of this task, imagine that A B encodes the graph of co-authorship between set of rescarchers, and assigns each researcher its university. Then we have (B A/col), 1 if

---

Standard
Strassen
Third-Order
Triangular
Function Composition
Binary Relation Compasition
Quetient Binary
Match3
Relation Compasition
(a)
Accuracy per Epoch
0.8
0.8
0.6
0.6
0.6
500
1000
50
100
200
400
1000
2000
1.0
1.0
(b)
0.8
Accuracy per Minute
0.6
0.6
X1.1
(c) Speed gain (Epochs/Minute)
11.8
40
11.9
22
10
118
13.5
/12
Figure 1: Accuracy as a function of (a) the number of epochs, (b) training time (forward plus backward runtime per epoch), and (c) speed gain (measured as epochs per minute). Performance for each task is presented as the median accuracy over 8 independent runs on data outside the training set. For readability, we truncated the binary relation composition and quotient binary relation composition learning curves to 100 and 2000 epochs, respectively.
and only if researchers and j have co-authors from the same university, with the condition that these co-authors must be different people.
Theorem 5.1. The quotient binary relation composition task is solvable by a one-layer Strassen- attention constant-sin size transformer. At the same time, this task cannot be solved by any one- layer Transformer T with ( coandard-attentio heads, n (l)) triangular-atten attention heads, noll) embedding dimension, and n (o())size output MLP.
Experiments and Results
In this section, we systematically compare the performance of standard, triangular, third-order and Strassen attention in four tasks: (i) Indicator of the 1tt coordinate in the Function Composition (with f 9 ). (ii) Binary Relation Composition (with = B), (iii) Match3 (over position-aware permutations) and (iv) Quotient Binary Relation Composition (with B = AT). To obtain tighter upper bound on the capability of the standard attention, we chose to implement simple special cases of the tasks (see Appendix C for all the details on data generation). To compare these attention mechanisms, we evaluate their performance (accuracy per epoch) and training time (accuracy per minute) on the test sets of these tasks. Furthermore, Appendix D provides a thorough analysis in terms of computational performance, evaluating forward pass times, GPU and memory usage. Code for our experiments can be found at
centtentionnnuuripsee neuries22
Figure T displays our main experimental results. First, both the Strassen and third-order atten- tions are the only two mechanisms that present high accuracy levels across all tasks. Note that Strassen attention displays slight advantages on the Function Composition and Match3 tasks (Figure [b). Second, Strassen attention consistently outperforms third-order attention in training time (to peak performance), across all tasks (Figure [p). Third, the advantages of Strassen attention are further exemplified by displaying speed gains (i.e., number of epochs per minute) that match that of the standard attention in the Function Composition and Quotient Binary Relation Composition tasks, and are always superior to that of the third-order attention (Figure Ic). Fourth, perhaps unsurprisingly, triangular attention outperforms all attention mechanisms in terms of training time the Binary Relation Composition task (Figure second column). Indeed, Strassen and the third-order attentions need learn the triangular structure of the task, knowledge that is already structurally embedded in the triangular attention. Fifth, although the third-order attention presents similar accuracy per epoch trend to that of Strassen attention, its learning dynamics seems to be significantly more unstable, particularly for the Function Composition and Quotient Binary Relation Composition tasks. Sixth, a clear advantage of Strassen attention over the triangular and standard attentions was observed for the Quotient Binary Relation Composition task (Figure Dp. last column). Lastly, it is noteworthy that the

---

triangular attention framework has a smaller applicability scope, and therefore could not be run on the Function Composition and Match3 tasks (without changing the data presentation from sequences to matrices).
Strassen vs. standard attention Parameter-matched comparisons Given that I-layer Strassen and standard attention architectures are not parameter matched, we performed two additional experi- ments to provide a fair comparison between them. both experiments, Quotient Binary Relation Composition and Binary Relation Composition, we pitted 1-layer Strassen attention against 2-layer standard attention, both models with hidden dimension 16. less parameters, 1-layer Strassen attention continues outperforming 2-layer Standard attention (with about 40% more parameters) in both the tasks considered. Furthermore, to demonstrate the value of Strassen attention over standard attention in more practical settings, evaluated this two attention architectures on the COGS dataset, in a parameter-matchit configuration. Table T shows that Strassen attention outperforms standard attention.
that even with
Task
Attention Type
Layers
Hidden dim.
Parameters
Accuracy (%
Binary Relation
Strassen
16
2.5k
100
Composition
Standard
2
16
3.6k
92
Quotient Binary
Strassen
1
16
2.5k
98
Relation Composition
Standard
16
3.6k
82
Strassen
64
99k
72
COGS
Standard
68
99k
65
Table 1: Accuracies for the Binary Relation Composition task, Quotient Binary Relation Composition task and COGS dataset function of attention type, layer number, hidden dimension and parameters number.
Future directions and limitations Our results pave the way for several directions of future research. First, we have introduced new method to obtain limitations for one-layer Transformer, based new concept we have named splitting VC dimension. We expect our method will be applied to obtain lower bounds in other architectures and other tasks involving complex reasoning. Second, given the differences observed in learning stability between the third-order and Strassen attentions, the latter seems to be associated with a smoother loss landscape, an hypothesis that needs to be confirmed and studied. Third, Strassen attention can be adapted to incorporate interactions that involve more than three tokens, possibly capturing more complex patterns in data. Yet, practical learnability of such higher-order interactions needs to be assessed. Finally, and related the previous point, although the main goal of our work was to gain a deeper theoretical understanding of the abilities of the Transformer, conclusions advantages of the Strassen attention using specific benchmarks or even in learning methods such as masked language modeling. At the same time, the possible applications of the Strassen attention not limited to compositionality but could extend to such areas as knowledge graphs, protein structure prediction and others.
limited by using toy tasks. Our next step is to test the theoretical
Acknowledgments Kozachinskiy, Urrutia, Jimenez, Pizarro, Calderon, and Rojas are funded by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID. Kozachinskiy is supported by ANID Fondecyt Iniciación grant 1120066..
10

---

References
[1] Jason Ansel, Edward Yang, Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesensky, Bin Bao, Peter Bell, David Berard, Evgeni Burovski, Geeta Chauhan, Anjali Chourdia, Will Constable, Alban Desmaison, Zachary De Veto,o Elias Ellison, Will Feng, Jiong Gong. Michael Gschwind, Brian Hirsh, Sherlock Huang. Kshiteej Kalambarkar, Laurent Kirsch, Michael Lazos, Mario Lezcano, Yanbo Liang, Jason Liang. Yinghai Lu, CK Luk, Bert Maher. Yunjie Pan. Christian Puhrsch, Matthias Reso, Mark Saroufim, Marcos Yukio Siraichi, Helen Suk, Michael Suo, Phil Tillet, Eikan Wang. Xiaodong Wang, William Wen, Shunting Zhang. Xu Zhao, Keren Zhou, Richard Zou, Ajit Mathews, Gregory Chanan, Peng Wu, and Soumith Chintala. PyTorch 2: Faster Machine Learning Through Dynamic Python Bytecode Transformation and Graph Compilation. In 29th ACM International Conference on Architectural Support for Progromming Languages and Operating Systems, Volume 2 (ASPLOOS 24). ACM, April 2024, doi: 10. 01155/620066533644466 URI htttt:t//pttoorrrreee http://pppooooo.oo.a/o.psse wttp://///aaaat//ttoooo2/22.../.
[2] Leon Bergen, Timothy O' O'Donnell, and Dzmitry Bahdanau. Systematic generalization with edge transform- ers. Advances in Neural Information Processing Systems, 34:1390- 1390--4020 2021.
[3] Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the Representational Capabilities of Transformers and Recurrent Architectures. arxiv preprint arXiv:2406.09347, 2024.
[4] Noam Chomsky. Syntactic structures. Mouton, 1957.
[5] G Daniel, Johnnie Gray, et al. Opt's_ _iisum-a python package for optimizing contraction order for cinsum-lik expressions. Journal of Open Source Software, 3(26):753, 2018.
[6] Ronald Dekker, Fabian Otto, and Christopher Summerficld. Curriculum learning for human com- positional generalization. Proceedings of the National Academy of Sciences, (22255111285 2022.
[7] Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. In 2023 IEEE 64th Anmual Symposium on Foundations of Computer Science (FOCS). pages 2129-2138, IEEE, 2023.
[8] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang (Lorraine) Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger. 7aid Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers on compositionality In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 70293-70332. Curran Associates, Inc., 2023, URL https:
neurips wwwrips.ccppapeeeeeeee http:paprrffleeeppeeeeeeeee http://a/...aaa///////////////// 57cb653c155e00 Conference. .df
[9] Paul W Goldberg and Mark R Jerrum. Bounding the Vapmik-CCerronenkiss dimension of concept classes parameterized by real numbers. Machine Learning, 18:13 18:131-148, 1995.
[10] Michael Hahn. Theoretical limitations self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 3:156-171 2020.
[11] Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
[12] Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang. Mare van Zee, and Olivier Bousquet. Measuring compositional generalization: A comprehensive method on realistic data, In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, hett/forummiddSyeeeea
April 26-30, 2020. OpenReview.net, 2020. https:ttss:///ooo
[13] Najoung Kim and Tal Linzen. COGS: a compositional generalization challenge based on semantic interpretation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (emnlp). pages 9087-9105, 2020.
[14] Brenden Lake and Marco Baroni. Generalization without Systematicity: On the Compositional Skills of Serpeence-to-equenne Recurrent Networks. In Proceedings of the 35th International Conference on Machine Learning, pages 2873-2883 PMLR, July 2018.
mmlr press/veee
0/lake18a 1aaeee1ahhtttt html
[15] Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman. Building machines that learn and think like people. Behavioral and brain sciences, 40:e253, 2017.
[16] Gary Marcus. Deep Learning: A Critical Appraisal. arXiv preprint arXiv: 100110001.00111 2018.
11

---

[17] Gary F Marcus. The algebraic mind: Integrating connectionism and cognitive science. MIT press, 2003.
[18] Santiago Ontanon, Joshua Ainslie, Zachary Fisher, and Vaclav Cvicek. Making Transformers Solve Compositional Tasks. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers). pages 2591-3607. Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653/v 1/2022.acl-1ong.255. URL
2022 acl long 251
[19] Binghui Peng. Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture. arXiv preprint arXiv:2402.08164, 2024.
[20] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational Strengths and Limitations of Transformers. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. BtLttttt://ppper nips cc/ http://c....ceeeeee////////aa/// #499eccb2eee44-ttttrad-----reeee
html
[21] Shai Shalev-Shward and Shai Ben-David. Understanding Machine Learning From Theory Algoritluns. Cambridge University Press, 2014, ISBN 978-1-10-705713-5.
[22] Koustuv Sinha, Shagun Sodhani, Dong, Joelle Pineau, and William Hamilton. CLUTRR: diagnostic benchmark for inductive reasoning from text. arXiv preprint arXiv: 1908.06177, 2019.
[23] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention All you Need, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. pages 5998-6008, 2017. URL /ttp Absaaaat.ttaattttmlm
s.
[24] Aimen Zerroug, Mohit Vaishnav, Julien Colin, Sebastian Musslick, and Thomas Serre. A benchmark for compositional visual reasoning. Advances in neural information processing systems, 35:29776-29788. 2022.
12

---

A Illustration of the attention mechanisms
Standard (Vaawani al, 2017)
Third-Order (Sanford of nl, 200g)
Legand
Trarspose Product
nxd
Soltmax
Alt
axd
nxd
ALL
Wiglted
Ealanand Profuct
axd
[Bleremwwii Profuct)
Softmax
nxn
Elmmentvvtee Dossson
Vi
V2
One-Jayer Transformer
e-lepstlengh lengh dinereiot
axd
Ka add
uxd
Triangular [Bergen et al., 2021)
Strassen (Our mechanism)
Output ML2
a Soltmas
Alt
Diagonal
X@Y@2 add
exd
A
nxd
BXB
Vs
B axd
X
Att
Strusicn Attintion
modes
X@Y@
mi m
Figure 2: Comparison of Transformer attention mechanisms: Standard
23 Third-Order 20 Tri-
angular (2), and Strassen (proposed). The diagram shows operations and the one-layer Transformer architecture, highlighting the flow through each attention and output MLP (without layer normal- ization and dropout in the attention mechanism). Notation: input length n, embedding dimension d, number of nodes m, with m² when refers to the shape of flatten matrices.
B
Missing proofs
B.1
Proof of Theorem
Denote Split-VC(f). Let A (1 [I....,n] be such that the VC dimension of the set of columns of A m. Denote B = [n] A. Assume for contradiction that there exists a one-layer standard- attention Transforner that computes f and whose size (that is, embedding dimension, number of attention heads, and the size of the output MI.P) is m())
Consider any n E AA 2 E B and define w = w @ w² = 01 o, E Σ", For h = 1,..., H, observe that the output of the h-th attention head in the (n + 1)-st token (the auxiliary one, where the output of the function is computed), can be written as:
(w=)) + (1) + 7.) (h) = (ww) + (
ax+1
+ 2(A)²
(20)
where
(h) (w²) Σ eontiker Rd,
B(h)
Σ elatikin RRd
SEA
iEB
(1) Σ elutiks E TR
(w
(1)
elntiki
R
SEA
VEB
(1) contskn--guu until
(()) antskaas
Unti
Note that that A; = WVp(i,, oz).
pop(i, o.) are functions of wt for E A and of w² for i E B,
whereas 41+1, 1 k and Un+1 are fixed.
The output of the function is thus computed by:
(w") (ww)))+ +((1)) ( (wر)+,(1) (V (w
f(w) (M' ,w²) = sign N Ent1 + Wo
(21)
(00 (mn ) (
Xen H4 ( (.
13

---

where In+1 = p(0), Wo E Raxal are fixed, and N is the output MLP of T.
Consider now arbitrary real vectors
a' = (a! ,.... (a)) R
= (B 3( E R == (n())
= (A ..... ( E R
(H) R
and define a function F; (,, - {0, 13 as in 21). but with vectors A, 8, allowed to take arbitrary values:
F(o, F(0,A,3,11) = sign W
Int1 + Wo
(22)
200 (n) x0*) +000000
Let H be class, defined by (2 when a, À are considered as inputs to hypotheses and 8 as parameters:
= (1 TRd + (0. (a A) = F,0,A, A. (3, E "dd
On the one hand, the VC dimension of И is at least m split-VC(g) Indeed, consider H is an infinite matrix, with
indexed by (a, A) E RaH+H columns by (B, R4H+H and the intersection of the (a, X)-row and (3, j containing F(a, X, 3, = h A). The VC dimension of H the VC dimension of the columns of this matrix. Since by (2I) this matrix has M as a sub-matrix, we get the required lower bound.
On the other hand, the VC dimension of Hl can be upper bounded by m²(1), Indeed, the number of parameters of H is dH + H m To compute the value of given hypothesis on a given input, it is enough to do m o1 basic arithmetic operations and comparisons with 0, because the size of A is moI By Theorem 2.3 in (9) the VC dimension is polynomial in these quantities, which gives us m upper bound in our case.
B.2 Proof of Theorem 3.6
We fix the value of P1 to be equal to I, and consider the output of Matcha[n, m] at the first position. If additionally set Pj *
2 for j 2, we obtain pl + Pý + Pk (mod m) if and only if j, k 2 2 and Pj + Pk = -1 (mod m). Hence, Transformer for the Matcha(n, m] task can be converted into Transformer, computing the following function in the auxiliary token:
Sumzle, m]] (mm- 1] {m - -2} + {0.1}
Sumz mp(p) f1 3j, le [6] s.t. p, + -1 (mod m),
otherwise
where n2
The following Lemma establishes what we need order to obtain the desired lower bound from Theorem 3.2
Lemma B.1. For even f, holds that
20)) 2 8/2.
Sumzlt.20 with A {1, (1....,//2) f/2]. is least f/2. The rows of this matrix are indexed by vectors p PI... Pe/2 (22 - 1 (2e- - 2)) and columns by vectors = 45+1 E ([2 - 1] \ (2f - 2)) Note
Proof. We claim that the VC dimension of the set of columns of M MA
that in this case, for a given row p and column q, their merging @ is simply their concatenation.
We now consider f/2 rows, corresponding to vectors:
p' (2, 1, 1, 1....,1) 1),
p² (1, 1,...,77 1),
1/2
14

---

and show that these rows can be shattered by the columns of M Sura (4,20] For any Boolean vector
C1 .2... E {0, 1//2, we have to find a column E ([26 - 1] {2e 2/)*/2 such that:
Sumzle, (g e q) 4
8/2. ......,./... for 1,....
then suffices to choose g such that
2 21 - otherwise.
=
95++ {1
i E [e/2].
Indeed, first note that the value 2 = f. - 2 is not used. Now, if c; = 1, then @ has numbers 24 and 26 1, summing up to 2f Next, if = 0, p, @ g only two numbers can appear, and 2if, whose sum is neither 2/- 1 nor 46 because t/2. This completes the proof.
B.3 Proof of Theorem 3.7
We consider subproblem of this task, where only elements A Aix and Bzi..... Bk be equal to I, where k = vn. Under this restriction, a Transformer solving the binary relation composition computes, in the token position (1, 1), the function Disim {0, 1) {0, 1) (0, 1) given by
m Disjm. (a, b) V (a, A b,), k=1
with and b being written in positions A AIR and B21..... B&I respectively. In our case, m = vn- The results now follows from Thcorem 3.2 and the following lemma. Lemma B.2. (iti-VC((Dsj..))) 2 m
Proof. We show that the VC dimension of the of columns of Misii.. at least for A mm.. Both the rows and the columns of Disj.. are indexed by m-bit vectors. We show that m rows, corresponding to the following vectors; a² (1,0
a² (0, (0.1,...,,000)) 0,0),
a" (0,0, ........0.p
can be shattered by the columns of the matrix. To establish that, for every c E {0, 13mh we have to provide b b1 ... bm E {0, 1]th with
Disim (a', b) Cs. ie [m].
This can be achieved by simply setting b; = c; for i E [m].
B.4 Proof of Theorem
Function composition In the function composition task, get (2n 1)-length sequence of numbers
6(1), ., ((2n 1) [n]] The task output, in the (2n + 1)-st token, the value of h(g(z)) with the 0.5-precision (in fact, we will do this with a much better precision, namely e -(((n)), where g, h: [n] + [m] and . E [n] such that 9(1) o(1), ... (n)) = ((n),((1) = o(n ......,(n)) d(2n), x d(2n + 1).
We the following positional encoding:
d(i)
(
== 1.... 2n +
15

---

We take matrices W Wa, W in 12
15
so that:
(0(1))
i)
j²
=
95 =
n
(o(i))
20(
hg
2km + nt k
We obtain:
fi9j + g + hsfi
a.jik = Softmax,,A y.k
v6
=n² [Q((i] - j) (o(i) (k n))
Softmax,,k
v6
In particular, the maximum 02n+1.j. is for j and such that j 6(2n + 1) z, and + <(j) = n + 6(x) = + g(x), and other values of 020+1.j. are by an {(nn)) -factor smaller. Hence, with precision +e -(="),
obtain 02n+1 Uy @ vy for = x and k: + g(x). Observe that ((k) o(n + g()) = h(g(z)) so it enough for @ U2 to have a coordinate equal to ((k). We achieve this by setting matrices Vi, V/2 in (15) such that the first coordinates of ey and U/ 1 and Φ(k), respectively.
Binary relation composition In this task, the length of input is square number n = m and tokens are indexed by pairs (i.j) E [m]]3. The token, indexed by (i.j), receives on input two bits Aij, B,y from two Boolean matrices A, B E {0, 1mmxm. As an output, the jith) token has to produce real number Yij such that
m
(BoA);
V (Ax Buy) sign(y.))
We employ the following positional encoding:
Aij
Bij
i
2
i.j = 1,...,
j
ja
1
16

---

We then take matrices W W W in 12
15
so that:
1
2i
j
2j
d²
fgg = 2
god n?
2d
hyt n?
k2
B
cd
1/m² 1 1/m3
1/m*
1/m²
(horizontal lines are added for readability). We obtain:
Esgea+taaheethe n [(6 - c)² 1d) ()= + Aod + B&d +
cm dm? + km
m
(23)
The expression in brackets has the "integral part", and also has the term cm Am kmmt which is O(1/mo //m) and is different for different quadruples (c, d, k, E). Hence, there is unique quadruple (c, d, k, E), establishing the maximum of the above expression, and it also maximizes the "integral part" [-(i - c)2 (d 2)2 (E - j)² + Acd + B&E Because of the factor n the value for the other quadruples will be smaller by at least (2(n / = 2(n3/3).
The quantity [-(i - c)² (d - k)² (E j)= + Aed + B&E] is at most 2, being equal to 2 if and only if = i,6 = j. d = ko and And = Baj = In other words, the maximum of the integral part is if and only if (B A)ij 1.
As result, the (i, token will get the value the Hadamard product Vied @ tke with precision e -00()/))) for some quadruple d, k E [m] satisfying:
(c= i, j. and Acd Bie = = (Bo A)
(24)
remains define matrices V1 /2 that this Hadamard product in some coordinates has d, k, E, Acd, BuG, and has 0 where Fij has and j. Then Tij + (vy O uk) will have all quanti- ties involved in the equalities of the left-hand side of (4). and checking them can be done with constant-size MLP.
Match3 On input, we get an array Pi... .I...P Pn. E [m 11a We first describe how check, for a fixed Σ and for every i = 1,..., n, if there exist j, k E [n]] such that p; + Pj + Pk Σ using one Strassen attention head. We get solution for the Matchs m] task with 2 attention heads by applying this construction to Σ m and Σ 2m.
The embedding dimension will be 8. Define qi p: Σ/3. We use the following positional encoding:
q 2
24,
i
1,...,
17

---

We define matrices W W W in
12
15
So that:
2qj
9i
2q
20
0
fi n²
0
9j
n²
93
h4g n2?
0
OR
0
As result, we get:
fagi + h + h,fi
aisk = Softmax,,. j.k
v8
n (-(g: + 9Ι + qz)²² m
Softmax j.k
v8
n (-
+ Pj + Pk 2)²
int1
Softmaxji.
v8
For given i, the maximum of Oizk is attained on a single triple (i,j, k) with the minimal value of [p: + Pj + Pk Σ| across the array, and it will be by an ( -fccoor larger than any other value of aij.k. We added the fraction in+1 to ensure uniqueness of the maximum; the added term is different no
for different pairs (i,j) while not exceeding O11/n).
Since all numbers under consideration are polynomial in n, the output a, will be equal to by C for the maximal pair (j, k) up to ( Σ for this pair (j, k). is enough to define V1, 1/2 so that the 5th and the 6th coordinate
In the output MLP, we have check
P;t PP of 1j and 2n are L, and Pk, 1, respectively. As result, the 2nd, the 5h, and the 6th coordinates of x; + 0; will be -p; Pk. and py, respectively, allowing us to find out if Pj + Pk Σ with constant-size output MI..
B.5 Proof of Theorem 5.1
Upper bound The upper bound is very similar to our construction for the binary relation composi- tion task in Theorem 4.2 Namely, first replace (d k)²² by (col co)( in (23 After this modification, the maximum of 23 will be attained on single quadruple (c, d, k, E), and for this quadruple we will have i, f (dl col(k) and A&a B&j if and only a quadruple, satisfying these equalities, exists. However, due to the definition of our task, we have to add smaller term, enforeing that among quadruples, satisfying this property. those with d + k have a larger value of (23). This can be achieved by adding term of the form (d - k)² /m3 which is always ((1 /m) so that the largest possible difference in this term is smaller than the smallest possible difference of the "integral part" in (3
We also have add term which ensures that the maxima is attained at the unique quadruple. The largest possible difference in this term should be smaller than the smallest possible difference in the previous terms, which is ((1/m²). We can again take the expression cm3 + dm² + km + é but
divided by larger denominator, for instance:
cm3 dm km
m8
(now the maximal possible difference in this term is O(1/m²)). Finally, it remains to multiply all the coefficients by a sufficiently large factor to make the minimal possible difference between the maximum and the other values polynomial in n.
Lower bound We employ the same technique as in Theorem 3.2 However, cannot rely on directly as now we have to deal with the triangular attention.
Assume for contradiction that there exists one-layer Transformer T such that (a) it solves the quotient binary relation composition task; (b) it has n ((1) handarddattention heads, (1) triangular-attention
18

---

heads, (1) embedding dimension, and n re0 output MLP. Without loss of generality, let be even and fix s be such that n 2s Given two binary words p = pi ... Px. = 91 9, E {0. 1) we define an instance (A(p), B(g), col) of the quotient binary relation composition task by setting:
A12+j Pjr
B2+o+i.2 9j:
for j E [s], and letting all the other entries of the matrices A, B to be O. The coloring function is defined by col(1) col(2) and
col j) = col(2 + -
for j E [s]. An example of this construction for # = is given in Figure
6
10
5
A
9
p 1010
1
2
B
q 0111
4
8
3
Figure 3: An example of the construction. Nodes apart from and 2 are split into 2 equal groups 3, 5. and 7, 8, 10. If A.y (resp., B, = 1). we draw an A-labeled (resp., B-labeled) edge from i to j. The A-edges can only go from I to 3,4.5,6, and the word p determines, which of these edges are present. Likewise, the B-edges only go from 7, 8, 9, 10 2, according to whether g has or 0 in the corresponding position. Nodes 3 and 7, 4 and 8, 5 and 9, 6 and 10 have the same color but different pairs have different color. Therefore, the only way we can have ( a A/c)12 = when I has an A-edge to some node the left, and the node of the same color from the right has B-edge to 2. In the example from the figure, this is true for and (which happens because p and q both have 1 in the third position).
We claim that for the instance (A(p), B(g), col), the value of the quotient binary relation composition at the pair (1,2) 2) is defined by the equation:
(B(4) A(p)/ col) = Disj(p, 4),
(25)
where Disj(p, q) 1 if and only if there is a position where both p and q have 1. Indeed.
Disj 9) 1, taking j [s] such that pj qj 1 and then setting hi = 2 + j, hi = 2 +
we obtain that Aιk, = Pj = qj Bb,2 = 1 and col(k, = col(kg) = 2 + which implies 1. On the other hand, if (B(g) A(p)/col)12
(B(q) A(p)/col)12
1, then for some k1 # h col(k:2). Since Aik. = 1, Bb,2 1. we have ki = 2 + + j2 for some j1, j2 [s). Since 2 + col(k)) col(k2)
we have A Bb,2 = 1 and col(k: and
j2, derive Øj and Disi 4) = 1, as required.
that j1 = j2 = j. Hence, we get P3 = Aik, Bxy2
We now put the instance (A(p), Bgg). col) to Transformer T and look its output int the token indexed by 21, By (25) we have:
sign(y12) Disj(p. q)-
We now look how the output y12 computed in Transformer on such input. The key observation that, for any h = 1,..., H, the output of the h-th attention head position (1, 2) can be written similarly to (20p fraction, where some terms depend solely on p and others solely on q:
(b) (h) (p) g(h) + (N) 412
a (()) (N) E cdd
(( (x)))))))))))) (1)) E R
(()) (p) + (g) + (h)
19

---

regardless of whether the h-th attention head uses the standard or the triangular attention. Indeed. for the case of the standard attention, this is by the same computation in the proof of Theorem 3.2 Now, for the case of the triangular attention, the same computation goes through but for pairs of tokens of the form (# F222) instead of individual tokens. remains to notice that for 3, .,.... +
the value of this pair is determined by p. and for & = + 3,.... 2s + 2, the value of this pair is determined by (and for s = 1, 2, the value of this pair fixed).
.
The rest of the proof is identical to the corresponding part in the proof of Theorem 3.2 Similarly to 21 we can now write:
(0)+ (a
Disj(p, g) = sign N 21, + Wo
(26)
(1) (p)+ (g +x) ( tutmy
Then we define hypothesis class H by considering parts of (26) that depend on p inputs and parts that depend on q as parameters. On the one hand, since d, H and the size of N are assumed to n (2)))) the VC dimension of this class is n(( by Theorem 2.3 [9]. On the other hand, its VC dimension is lower bounded by the VC dimension of the set of columns of the matrix (isj q).
which is at least n2/2- as established in the proof of Proposition B.2
C Experimental Setup
C.1 Datasets
We create dedicated datasets to evaluate our models across all four tasks, Each task consists of 5 x 10a examples. Below, we detail the data generation process for each task, with explanations of key components and structures.
C.1.1 Function Composition
The task of function composition involves determining whether a specific condition holds for a given sequence derived from a function f. Each example in the dataset is represented tuple (X, y). where:
X = (1),
f(n 1)) is an input sequence of length + 1. The first token, 1, is a query token indicating the position where the output required.
is sampled uniformly from the range [Nain Nmax], with Nuin 25 and Nmax 30. E {0,1) is a binary label that indicates whether the condition f(f()) = 0 is satisfied.
The dataset generation process ensures that the sequences random but incorporates specific constraints to maintain diversity and balance (approximately 50% positive labels). Algorithm outlines the data generation procedure.
Algorithm Dataset Generation for Function Composition
Input: Nmin, Nmax Output: Dataset
for 1 to 5 x 10t do
Sample n Uniform(ANmin N Nmmx)
Generate random sequence X = ToT In-1 with 2; ~
1, 1 1})
Sample y ~ Uniform( (0, 1})
if and Fx. * 0 then
Set F2g else if 0 and Σnp = 0 then
Ensure f(((0) = 0]
Set Ji ~ Uniform(i E (1.2..... 13 xy #0) (Ensure s(((0) + 0)
end if
Prepend query token: X < (1
Add (X, y) to the dataset
end for
20

---

Explanation of Examples ( In the sequence (,, the label 0 implies that the condition (O) does not hold. Specifically; f(0) = 3, and f(3) 1 + 0. Thus, the condition s((()) = 0 is false. In the sequence (J,, 1,,,,,,,55 5, o,.... the label
indicates that is satisfied. Specifically: f(0) 4, and [4) = Thus, the condition
the condition [()()) f(f(0) =
0 is true.
1
3
4
0
1
5
0
Sequence X
Label y
Table 2: Example sequences for the Function Composition task. The label depends whether
f(f(0)) = 0.
C.1.2 Binary Relation Composition
The task of binary relation composition involves determining whether a transitive relation exists between elements in binary relation matrix. Given two relations A, B E {0, 1]mxm, where m = nn, and pair of elements i.j E {0, 1..... m - 1), the goal is to check whether there exists another element & {0, I, ... m 1} such that both relations Aa and Bęj hold. For simplicity, define Rt E {0, 1 and set A R and B = R. Each example in the dataset is represented as tuple (X, Y), where:
X = flatten(R)) is an input sequence of length m2 of a flatten boolean matrix R {0, 1mmxm representing the binary relation. Each element Rij independently to with a probability P between ( to 1, where P is parameter independent on the input length.
is sampled uniformly from the range [Nmin NNmax. with Nmin 6 and Nmax 8.
Y E {0, 133h is a list of binary labels that at position h: = x m + indicates whether there is composition of relations between element and j is satisfied.
The dataset generation process ensures randomness X while adhering to the constraints for Y. For in the range [Nmin: Nima], the probability P is 32.5% to achieve balanced proportion of positive labels. Algorithm 2 provides the detailed data generation procedure.
Algorithm 2 Dataset Generation for Binary Relation Composition
Input: N min N Nmax; Output: Dataset
for 1 to 5 x 10a do
Sample m ~ Uniform N Nmax)
Generate boolean matrix R E {0, 1mmm where each element Rig with probability P Initialize Y =
{An empty list for labels)
for = 0 to m do
for 0 to
do there exists such that Rss and Rej then
Append to Y
else
Append 0 to Y
end if end for end for
Add (flatten(R), the dataset end for
Consider the binary relation matrix R shown in Table 3 For i 0, 4, there exists & such that Roz and R2 1. Thus, Yoxe+4 = For
Explanation of Examples (Table 3
j 0, R50 1 is the unique candidate, but Roo 0. Thus, Ysx610 0.
21

---

0
2
4
0
2
5
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
1
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
1
0
0
Matrix
R
Table 3: Examples of binary relation matrix and corresponding composition. Here, X flatten
and Y = flatten R R).
C.1.3 Match3
The Match3 task involves determining a target label sequence Y for a given input sequence X. Each example consists of imput sequence X of size n and label sequence of the same size, where for every index i E {0, I, - 13. Y; represents the target value for X;. Each example is represented as tuple (X, Y), where:
X = (In, D1,... 1n is pseudo-random sequence of integers sampled from the range 0, .M 1]. where M 37.
Y (yo, V1..... 3n-1)) is binary sequence, with yi E {0, 10. where each value y; indicates the token x; satisfied the Match3 condition in X.
is sampled uniformly from the range [Niin m where N 30 and N 35.
The dataset generation process aims to balance the distribution of ones in Y across four predefined bins corresponding percentage ranges: [0, 25)%, [25, 50) %, [50, 75)%. and [75, 100]%. Algorithm outlines the data generation procedure.
Algorithm Dataset Generation Algorithm Match3
Input: Niin; Nmax, D (Input the dataset size)
Output: Dataset
Initialize four empty bins (Each bin corresponding to percentage ranges of ones in sequences:
[0, 25,25 [25, 50)%, [50, 75)%, and [75, 100
N₂ + (D/10)/4
for i 1 to 5 x 10 do
Randomly select skewness Uniform( (1, (1, 40) [An initial percentage distribution of ones the sequence)
Sample n ~ Uniform(Ne (min: Mmux)
(1 -.,... Tn-1), where Uniform( 10 M - 1}) ensuring the percentage of tokens that satisfied Match3 condition is at least skewness
Generate pseudo-random sequence X
Compute Y (3o. .l...., 3n-1) based on Match3 condition Calculate the percentage of ones in Y
Add (X, Y) to the corresponding bin size(bin) < N, end for for each bin in bins do
while size(bin) * (D/4) do Randomly sample an example (X, YY) from bin
Apply the same permutation to X and Y Add the permuted pair (X*, y*) to bin end while
end for Add examples from the bins to the dataset
Explanation of Examples (Table Y in Table
Consider the example sequence X and its corresponding label
22

---

The input sequence X = (6, (6,9,9.9) 9, 9, contains ayeudo-randon inte- gers between and M 1 (M 37).
The label sequence Y (1,0,0,0, 1,,00,,,,
has skewed distribution of ones.
For instance, 1 indicates that the element 10 satisfies the property, because 37 34 and æ10 = holds, 25 + 27 310 =
2 x M.
0
1
2
3
5
6
7
8
10
Sequence X
9
9
10
34
9
30
Label Y
0
0
0
1
Table 4: Example sequence for Match3 task with M
= 37.
C.1.4 Quotient Binary Relation Composition
The task of quotient binary relation composition involves determining whether a transitive relation exists between two elements in a binary relation matrix while incorporating an additional constraint based on a coloring function col: [0, m 1] -> [0, 1--11 1]. For simplicity, we define R E {0, 1 ] and set and B A Each example in the dataset represented as a tuple (X, Y), where:
= flatten R) is an input sequence of length n = m² obtained by flattening the boolean matrix R. where each element R,y is independently set with probability P, which is independent of the input length.
col is function that assigns unique color to each element [0, m 1], with colors sampled uniformly from the range (0, m 1].
m. is sampled uniformly from the range [Nmin, Nmax], with Nmin = 6 and Nmax = 8.
E {-100, O, 13"h is a list of binary labels, where the position k = m + indicates whether the quotient binary relation composition between elements and is satisfied if and only i + j. otherwise Y 100.
The dataset generation process ensures randomness R while adhering to the constraints for Y. For in the range [Nmin ]. the probability P is set 43.3% to achieve a balanced proportion of positive labels. Algorithm provides the detailed data generation procedure.
Algorithm 4 Dataset Generation for Quotient Binary Relation Composition
Input: N Nminy Nmax: Output: Dataset
for
to 5 x 10 do
Sample
Uniform(NN N max)
Generate boolean matrix R E (0, (0.1)mmx0m) mmx where each element R.j with probability P
Generate coloring function col: [0.
1]
[0. m by assigning colors uniformly
Initialize Y=
(An empty list for labels)
for each pair (i,j) in [0, m 1] x [0, m 1] do
Append 1 to Y if & and there exist k1, K2 such that:
Rik1 1, Ryka 1, col(k) col(k2), and k f k2
Otherwise, if # j, append 0 to Y, else append -100 to Y
end for
Add (flatten(R)) Y' to the dataset end for
Explanation of Examples (Table 5) Consider the binary relation matrix R shown in Table 5
For 2, j 4, there exist elements kn = and lo = such that Ros = 1, R4s 1, and
col(4) 2 col(5), with k l2. Thus, Y2x741 =
23

---

3
6
2
3
5
0
0
1111
0
1
5
1
0
1
0
0
0
0
1
4
0
0
0
0
1
2
0
0
1
1
0
1
1
0
3
0
0
0
0
0
1
0
0
1
0
0
0
5
0
0
0
2
6
0
0
3
0
0
0
0
1
Matrix R
col
Rd R/col
Table 5: Examples of binary relation matrix and corresponding quotient composition.
C.2 Experimental Protocol
Dataset Splitting. The dataset is split into training and validation set. We randomly select 90% of the data for training, and the remaining 10% is used for validation. The validation set is used to monitor the model's performance as well test set. The validation data is kept within the same distribution as the training set to ensure that the evaluation is conducted in an in-distribution manner.
Evaluation. The evaluation metric for all tasks accuracy. compute the accuracy during training or evaluation, we first calculate the accuracy for each batch individually. This is done by dividing the number of correctly predicted labels by the total number of labels that batch. These per-batcl accuracies are then aggregated across all batches within an epoch. The overall accuracy for the epoch obtained by taking the mean of the per-batch accuracies. Note that this is not equivalent just taking the number of correctly predicted labels divided by the number of all labels in the whole dataset (due to variable lengths of examples). Both approaches converge to the same value as the number of examples grows.
Training Setting. We fix random seeds across all experiments. Each task and model configuration evaluated using 8 different random seeds, and the reported results include the median across these runs. This approach mitigates the effects of random weight initialization and stochastic data sampling during training. Additionally, training parameters such as learning rate, batch size, and training duration equally specified for each task across model, summarized in Table
Implementation Details We implement all models using PyTorch framework II with Opt-Einsum library (5). We employ AdamW optimizer for all training tasks without learning rate scheduler, ensuring consistent optimization strategy across experiments. We use the Binary Entrrpyy loss as the objective function. In order handle padding, we used attention masks, preventing the model from attending to padded positions, and thus ensuring no changes in the model's outputs. For the target sequence, we assign a value of -100 to positions corresponding to padded tokens. This ensures that during loss and accuracy calculations, only tokens with values other than -100 are considered. We achieve this by applying a mask, where predictions and targets are filtered as pred = pred [mask] and target = target [mask]] respectively.
Hardware and Resource Utilization We conduct all experiments on high-performance NVIDIA GPUs. Specifically, we execute NVIDIA A /00 GPUs with 80GB of memory tasks requiring extensive computational resources, such as Match3 and Quotient Binary Relation Composition. For tasks with lower computational demands, such as Function Composition and Binary Relation Composition, We use NVIDIA A40 GPUs with 48GB of memory.
D Further Experiments
We evaluate the computational performance of attention mechanisms exclusively on an NVIDIA RTX A6000 GPU. This analysis focuses on three metrics: (a) forward pass time, (b) GPU utilization. and (c) memory utilization. These metrics provide insights into the computational efficiency and hardware constraints associated with different configurations of hidden dimension and input length. Below, we detail the evaluation methodology and the observed limitations in the Figure

---

Task
Model
d
B
p
T
p
Standard
16
2500
10-3
1000 epochs
0.3
Function
Third-Order
16
2500
10-13
1000 epochs
0.3
Composition
Strassen
16
2500
1 1-10-3
1000 epochs
0.3
Standard
16
2500
1-10-3
200 epochs
0.3
Binary Relation
Triangular
16
2500
1.10
200 epochs
0.3
Composition
Third-Order
16
2500
1-10-3
200 epochs
0.3
Strassen
16
2500
1-10-3
200 epochs
0.3
Standard
128
2500
1-10-3
500 epochs
0.4
Match3
Third-Order
128
2500
1.10
500 epochs
0.4
Strassen
128
2
2500
1.10
500 epochs
0.4
Standard
16
2000
1.10-3
3000 epochs
0.3
Quotient
Triangular
16
2000
1-10-3
3000 epochs
0.3
Binary Relation
Third-Order
16
2000
1-10-3
3000 epochs
0.3
Composition
Strassen
16
2000
1-
3000 epochs
0.3
Standard 68
1010
200 epochs 0.1
COGS
Strassen
64
4
100
10-
200 epochs
0.1
Table 6: Training parameter settings for tasks and models. For models and tasks, we run experiments on 8 different seeds with only attention layer (except for the COGS dataset where we use 3 layers). Here d is embedding dimension, h is the number of heads, B is the batch size, p is the learning rate, T is training duration and p is the dropout outside attention mechanism. We did not use batch normalization for any task.
Sie moceen
Third-Order
Triangular (MtNoodes)
Triangular NWw.ddrroooooooooooeeeeeeeee NodeswNadess
38 ms
83 ms
1448 ms
287 ms
ms
(a)
5.0
(Seconds)
2.5
100
1.00
1.0
1.00
(b) Usage
(8)
(c)
Memory (G8)
20
20 20
20
Input Length (N)
Figure 4: Analysis of computational performance for each attention mechanisms presented in this work: Standard, Strassen, Third-Order and Triangular attention. Metries include (a) forward pass time in seconds, (b) GPU utilization in percentage, and (c) memory reserved in GB RTX A6000. Experiments are conducted across varying input lengths (4 to 16,384) and five hidden dimensions (64, 128, 256, 768, 1024). Each result represents the average of the median over 8 runs on 100 random sequences (100 tensors with batch size 1) passed through the respective attention mechanisms.
NVIDIA
Time We measure the forward pass time the delta time before and after passing 1 d random tensor through the attention mechanism, where n is input length and d hidden dimension. We implement this using time. time () function from Python. As expect, the results indicate that forward pass time increases significantly for higher hidden dimensions and input lengths.
GPU Usage We monitor GPU utilization using pynvml library to query the current CUDA device. Specific configurations of attention mechanisms, such as Strassen attention with large hidden dimensions (e-g., 512 higher) and long input lengths (e.g., 1600 or higher), result 100% GPU usage.
25

---

We record the memory reserved during tensor processing using CUDA memory management functions from PyTorch: torch. cuda. memory_reserved.
Memory Reserved
Our computational performance results show that (Figure 4
The computational constraints of Strassen attention become evident for hidden dimensions of 512 higher and input lengths exceeding 1600.
Those of Third-Order attention appear with even lower hidden dimensions (64 or 128) and input lengths exceeding 1600.
Standard and Triangular (n = Nodes) GPU memory usage does not shows bottleneck even for configurations with hidden dimensions of 2048 and input lengths of 16,384.
Triangular =Nodes) Limitations appear for hidden dimensions of 1024 or higher and input lengths as low as 196, with increasing severity for longer input sequences.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claim is that of a new lower bound method to evaluate the theoretical expressivity of transformers (which clearly describe B. We also describe our proposed Strassen attention and its related empirical results in section and [ respectively. Hence all the claims in the abstract are well accounted for the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are addressed in section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
26

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All theoretical results are backed up with correct proofs in the Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the information needed reproduce the paper is available in the main text, and we provide access to our code and data as a link to a github repo
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
27

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
All the results of the experiments are fully reproducible with our code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/pu
blic/
ssi ssionillccy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/nips..c/ppulllee haabblcc/guiee.../ httpa////ggieee//oeeuubbisbsssss http///ooSuumiisiioooo swi.bbmiiiiiooooiccccc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the training and test details are provide, alongside information with respect to the Sypee-parameters.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
28

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report error bar when relevant, but our paper is a theoretical paper that does not involve any statistical analyses.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгror bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have fully dedicated subsection in the Appendix that discusses the compute resources needed to run the distinct models we present.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/ppe.paooos...ooppp////eea
Answer: [Yes]
Justification: Our work conforms with the NeurlPS Code of Ethics
Guidelines:
29

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper discusses theoretical method to evaluate the expressivity of Transformers, this question therefore does not apply to our work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
See justification to question 10.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
30

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: See justification to question 10.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode com/ /atatasssss has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
See justification to question 10.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
31

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: See justification to question 14.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not1082 involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non ntn-standard components.
Please refer to our L.M policy (https: /ttpr:::////pps//e cc/Confereecces/22255 for what should or should not be described.
32


Reviews:
[{"review_id": "UWXbIFsd1B", "reviewer": "Reviewer_4HHd", "summary": "The paper introduces Strassen Attention, a novel higher-order attention architecture that replaces softmax-attention with a three-way normalized product between exponentiated matrices that can be computed efficiently with Strassen matrix multiplication. The model is presented as an alternative to other “triplet” architectures, like third-order attention and triangle attention, with computational advantages and empirical capabilities. The model is motivated by its ability to solve (theoretically and empirically) tasks like Match3, which are known to be hard for standard transformers. They strengthen this separation by introducing a novel theoretical framework of split-VC dimension for proving the limitations of single-layer transformers with arbitrarily precision to solve these tasks.", "questions": "Can you clarify the relationship to [1]? There appears to be substantial overlap in methodology.\n\nCan Strassen and third-order transformers be compared theoretically? i.e. can one be simulated by the other? \n\nWere there any particularly useful empirical lessons learned from training higher-order models? (e.g. differences in learning rate, optimization behavior, etc) \n\n[1] https://arxiv.org/abs/2412.20195?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strengths\n\nThe Strassen attention architecture is novel, creative, and well-motivated by failures of standard models on synthetic tasks. Figure 2 is particularly helpful for understanding the architecture. The model performs in simple empirical settings. and has strong theoretical motivation.\n\nThe split-VC techniques are new and resolve open theoretical questions about the capabilities of arbitrary precision single-layer transformers. (Previous results relied on either burdensome architectural assumptions or exploited bounded bit-precision.) \n\nThe experimental sweep includes a wide range of well-known synthetic tasks and demonstrates clear trade-offs between architectures.\n\n# Weaknesses\n\nThe computational advantages of Strassen attention are found in the connection to efficient metric multiplication, allowing sub-cubic time performance. However, given the suitability of GPUs and TPUs to multiplying large matrices, can these performance gains be realized with large models on modern hardware? \n\nThe empirical results are somewhat limited by their focus on purely synthetic tasks. Did the authors consider experiments on “intrinsically three-wise” practical tasks, perhaps on graph-based or molecular inference?\n\nThe theoretical results are limited by the single-layer assumption. Is it likely that the split-VC dimension approach can be extended to deeper models?\n\n## Minor points:\n- L276: “runnin-time”\n- L1027:  undefined table reference\n- Figure 2 is very helpful for understanding the architecture. Can it be moved to the paper body?", "was_revised": true, "final_justification": "My positive impression of the paper remains after discussion. My score will stay as is.", "rebuttal": "We thank the reviewer for the positive appraisal of our work and greatly appreciate the time invested in reviewing it. Below, we reply to the weaknesses and questions raised by the reviewer.\n\n\n* _(Weakness 2)* The empirical results are somewhat limited by their focus on purely synthetic tasks. Did the authors consider experiments on “intrinsically three-wise” practical tasks, perhaps on graph-based or molecular inference?_\n\nWe have performed an additional experiment on the COGS, a NLP task that tests compositional abilities. We compared Strassen and Standard attentions under a parameter-matched scenario using the following hyperparameters from [1]: learning rate (5e-4), dropout (0.1), batch size (100), linear warmup scheduler and no early stopping criteria. We have met an accuracy for Standard attention Transformer that was reported by [2] under a similar configuration. All the results are condensed in the following table:\n\nStrassen:  3 (Layers), 64 (hidden dimension), 99k (#Parameters), 72% (Accuracy).\n\nStandard: 3 (Layers), 68 (hidden dimension), 99k (#Parameters), 65% (Accuracy).\n\nThis analysis revealed that Strassen attention exhibited a significantly higher performance in COGS task. We thank the reviewer for suggesting this, and we will include results of this experiment into the revised version of the paper.\n\n[1] Bergen, L, O'Donnell, T., Bahdanau, D.2023 .Systematic Generalization with Edge Transformers.\n\n[2] Csordás, R., Irie, K., Schmidhuber, J. 2022. The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers.\n\n* _(Weakness 3) The theoretical results are limited by the single-layer assumption. Is it likely that the split-VC dimension approach can be extended to deeper models?_\n\nThe main technical challenge for extending theoretical limitations to multi-layer softmax encoders is that this requires breakthrough results in computational complexity theory (see Chen, Peng, and Wu, ``Theoretical limitations of multi-layer Transformer’’, Appendix B).\n\n* _(Question 2) Can Strassen and third-order transformers be compared theoretically? i.e. can one be simulated by the other?_\n\nA Strassen-attention layer can be simulated by a third-order attention layer with constant blow-up in the embedding dimension. We do not know whether this can be done in the other direction, but we find it unlikely, given that a Strassen-attention layer can be implemented faster.\n\n*  _(Question 3)Were there any particularly useful empirical lessons learned from training higher-order models? (e.g. differences in learning rate, optimization behavior, etc)_\n\nIn the training process we have seen that higher-order models can suffer from exploding values  during optimization. We deal with this by applying a shifting operation to the logits. Moreover, in order to improve convergence, we have adopted a Kaiming-He distribution for initialization of attention weights. Additionally, we chose to use a pre-layer normalization strategy, which helped to improve convergence time for all models. For more details, we refer to the repository link in Section 6 of the paper."}, {"review_id": "zm2o0JEACH", "reviewer": "Reviewer_nDED", "summary": "This paper presents a novel theoretical framework for analyzing the limitations of single-layer Transformers and introduces a new attention mechanism called Strassen Attention that is designed to overcome these limitations. The authors first develop the concept of \"Splitting VC dimension\" (spvc) to prove that standard one-layer Transformers, even with infinite precision, cannot solve tasks requiring complex compositional reasoning, such as function composition and Match3. Motivated by this, they propose Strassen Attention, a mechanism that efficiently captures interactions between triplets of tokens, resulting in a sub-cubic time complexity - `O(n^ω)` where `ω < 2.372`. The authors provide theoretical proofs demonstrating that a single layer of Strassen Attention can solve these difficult tasks. They further validate their claims through experiments comparing Strassen Attention to standard, triangular, and third-order attention, showing it achieves superior performance and efficiency on a set of challenging synthetic tasks.", "questions": "1.  **On the Power of Depth:** Your lower bounds are for one-layer models. Could you elaborate on the technical challenges of extending this analysis to multi-layer Transformers? Do you believe that a constant number of standard attention layers could solve the tasks you've outlined, or would it require a depth polynomial in the sequence length `n`? A brief discussion on this could help frame the importance of mechanisms like Strassen Attention versus simply stacking more layers.\n\n2.  **Numerical Stability and Implementation:** The core of Strassen Attention involves sums of large dot products inside an exponential (`softmax`). Your proof of sub-cubic implementation relies on decomposing this into matrix products. Could you comment on the numerical stability of this approach in practice? For example, in the function composition proof, the dot products are scaled by `n^2`. Did you encounter any issues with vanishing or exploding values during training, and if so, how were they managed? This would be valuable for others seeking to implement your method.\n\n3.  **Generalization to Higher-Order Interactions:** Strassen Attention elegantly handles 3-way interactions. The form `f_i g_j + g_j h_k + h_k f_i` seems inspired by the structure of the tasks. Could this principle be generalized to create an efficient 4-way (or k-way) attention mechanism? For example, would a formulation like `(f_i g_j) + (g_j h_k) + (h_k l_m) + (l_m f_i)` also be implementable with fast matrix multiplication, or does the cyclic structure break down?", "limitations": "Yes. The authors have done a good job of acknowledging the limitations of their work in the \"Future directions and limitations\" section. They correctly point out that their analysis is based on one-layer models and synthetic tasks, and they identify testing on real-world benchmarks as a crucial next step. They also observe that the learning dynamics and loss landscape of Strassen Attention need further study. The discussion is transparent and appropriately sets the stage for future research.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n1.  **Original and Important Theoretical Framework:** The introduction of the Splitting VC dimension (`spvc`) is a highly original and powerful method for proving lower bounds. Crucially, it works in the infinite precision regime, which improves previous results that relied on communication complexity and finite precision assumptions. This provides a more fundamental understanding of the architectural bottlenecks of standard attention.\n\n2.  **First Introduction of Strassen Attention:** The proposed Strassen Attention is derived directly from the theoretical limitations identified. The insight to structure the triplet interaction as a sum of pairwise dot-products, which in turn enables a fast implementation via matrix multiplication, is elegant. This makes the mechanism theoretically powerful.\n\n3.  **Comprehensive and Rigorous Evaluation:** The paper excels in its thoroughness. It starts with a new theory, proposes a new architecture, proves its capabilities, and validates everything with carefully designed experiments. The inclusion of the \"Quotient Binary Relation Composition\" task to theoretically disentangle the capabilities of Strassen Attention from other advanced mechanisms (like triangular attention) adds to the overall storyline of the paper.\n\n4.  **Clarity of Presentation:** Despite the high technical density, the paper is exceptionally well-written. The authors effectively use figures, formal definitions, and step-by-step proof sketches to make complex ideas clear and accessible. The motivation and narrative flow logically from problem to solution.\n\n**Weaknesses:**\n\n1.  **Limited Scope of Lower Bounds (One-Layer):** The primary theoretical limitation is that the lower bounds are only formally proven for single-layer Transformers. While the authors' intuition that these limitations likely extend to multi-layer models is plausible, this remains a conjecture. The possibility that depth could compensate for the lack of breadth in a single layer (i.e., multiple layers of pairwise attention simulating a triplet attention) is a key open question not addressed.\n\n2.  **Reliance on Synthetic Tasks:** The evaluation is conducted exclusively on synthetic \"toy\" tasks. While these tasks are perfectly designed to isolate and test the specific compositional abilities under investigation, the performance of Strassen Attention on real-world, noisy, and high-dimensional data (e.g., in NLP or vision) is not demonstrated. This leaves a gap between the demonstrated potential and proven real-world utility.\n\n3.  **Expressivity vs. Learnability:** The upper-bound proofs (showing Strassen Attention can solve the tasks) are constructive, demonstrating expressivity. However, they do not guarantee learnability via gradient-based optimization from a random initialization. While the experiments suggest the models are indeed learnable on these tasks, the properties of the loss landscape for more complex problems remain unexplored.\n\n4. **Cite more related works:** The authors should cite related works that study limitations of compositional tasks, like: \"Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory\" by Nikola Zubić, Federico Soldá, Aurelio Sulser, Davide Scaramuzza.", "was_revised": true, "final_justification": "The authors have addressed all of my questions and comments. I therefore expect them to revise their manuscript accordingly, including citations of related work, and I maintain my recommendation of Accept (5).", "rebuttal": "We thank the reviewer for the positive appraisal of our work and greatly appreciate the time invested in reviewing it. Below, we reply to the weaknesses and questions raised by the reviewer.\n\n\n\n* _(Weakness 2)Reliance on Synthetic Tasks: The evaluation is conducted exclusively on synthetic \"toy\" tasks. While these tasks are perfectly designed to isolate and test the specific compositional abilities under investigation, the performance of Strassen Attention on real-world, noisy, and high-dimensional data (e.g., in NLP or vision) is not demonstrated. This leaves a gap between the demonstrated potential and proven real-world utility._\n\nWe have performed an additional experiment on COGS, a NLP task that tests compositional abilities. We compared Strassen and Standard attentions under a parameter-matched scenario using the following hyperparameters from [1]: learning rate (5e-4), dropout (0.1), batch size (100), linear warmup scheduler and no early stopping criteria. We have met an accuracy for Standard attention Transformer that was reported by [2] under a similar configuration. All the results are condensed in the following table:\n\nStrassen:  3 (Layers), 64 (hidden dimension), 99k (#Parameters), 72% (Accuracy).\n\nStandard: 3 (Layers), 68 (hidden dimension), 99k (#Parameters), 65% (Accuracy).\n\nThis analysis revealed that Strassen attention exhibited a significantly higher performance in COGS task. We thank the reviewer for suggesting this, and we will include results of this experiment into the revised version of the paper.\n\n[1] Bergen, L, O'Donnell, T., Bahdanau, D.2023 .Systematic Generalization with Edge Transformers.\n\n[2] Csordás, R., Irie, K., Schmidhuber, J. 2022. The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers.\n\n\n* _(Question 1) Your lower bounds are for one-layer models. Could you elaborate on the technical challenges of extending this analysis to multi-layer Transformers? Do you believe that a constant number of standard attention layers could solve the tasks you've outlined, or would it require a depth polynomial in the sequence length n? A brief discussion on this could help frame the importance of mechanisms like Strassen Attention versus simply stacking more layers._\n\n The main technical challenge for extending lower bounds to multi-layer softmax encoders is that this requires breakthrough results in computational complexity theory (see Chen, Peng, and Wu, ``Theoretical limitations of multi-layer Transformer’’, Appendix B). The function composition task can be done in 2 constant-size standard-attention layers. For our other 3 tasks we conjecture that they cannot be done with a constant number of layers of n^{o(1)}-size standard attention layers.\n\n* _(Question 2) Numerical Stability and Implementation: The core of Strassen Attention involves sums of large dot products inside an exponential (softmax). Your proof of sub-cubic implementation relies on decomposing this into matrix products. Could you comment on the numerical stability of this approach in practice? For example, in the function composition proof, the dot products are scaled by n^2. Did you encounter any issues with vanishing or exploding values during training, and if so, how were they managed? This would be valuable for others seeking to implement your method._\n\n In the training process we have seen that higher-order models can suffer from exploding values  during optimization, which we avoided by applying a shifting operation to the logits. Also, in order to improve convergence, we have adopted a Kaiming-He distribution for initialization of attention weights. Additionally, we chose to use a pre-layer normalization strategy, which resulted in an improved convergence time for all models. For more details, we refer to the repository link in Section 6 of the paper.\n\n* _(Question 3) Generalization to Higher-Order Interactions: Strassen Attention elegantly handles 3-way interactions. The form f_i g_j + g_j h_k + h_k f_i seems inspired by the structure of the tasks. Could this principle be generalized to create an efficient 4-way (or k-way) attention mechanism? For example, would a formulation like (f_i g_j) + (g_j h_k) + (h_k l_m) + (l_m f_i) also be implementable with fast matrix multiplication, or does the cyclic structure break down?_\n\n Exactly, the formulation you are suggesting boils down to the product of 4 matrices instead of 3. This is still sub-cubic time. We are grateful for your remark, it opens an interesting direction for future work."}, {"review_id": "UMFs97MPJA", "reviewer": "Reviewer_3L74", "summary": "This paper introduces split-VC dimension as a novel theoretical framework for analyzing transformer expressivity and proposes Strassen attention to address compositional reasoning limitations. The primary contribution establishes rigorous lower bounds proving that one-layer standard transformers cannot solve tasks requiring ternary interactions (function composition, Match3, quotient binary relations) even with infinite precision arithmetic. The split-VC framework adapts classical learning theory to modern architectures, while Strassen attention offers a sub-cubic O(n^2.372) solution through triple-wise token interactions. The theoretical analysis connects complexity measures to architectural constraints through well-structured impossibility proofs.", "questions": "1. Can you provide experiments comparing Strassen attention against standard attention with matched parameters (either 5 projection matrices or d'=1.29d)? Include ablations testing V_1=V_2 weight sharing.\n2. Will you evaluate on CLUTRR (n>=128) and COGS to demonstrate practical compositional advantages? What performance improvements justify 67% parameter overhead?\n3. Please provide GPU runtime measurements (A100/H100) for sequences {1k, 4k, 16k} showing actual crossover points where Strassen outperforms standard attention in wall-clock time.\n4. Can you prove lower bounds under realistic assumptions: bounded MLPs (P=O(d^2)) and structured positional encodings (p(i,sigma_i) = q(i) + r(sigma_i) )? How do results change?\n5. Are all three interaction terms (f_i g_j + g_j h_k + h_k f_i)  essential? Provide ablations removing individual terms and testing reduced-rank projections.\n\nScore Improvement Criteria: Addressing questions 1-2 with positive results could raise rating to 4 (borderline accept). Demonstrating real-world utility on CLUTRR/COGS with parameter-matched baselines is essential for acceptance.", "limitations": "The authors acknowledge theoretical contributions but inadequately address practical limitations. Missing discussions include:\n\nScalability beyond synthetic tasks\nNumerical stability of Strassen's algorithm in transformer contexts\nEnergy/memory costs of 67% parameter increase\nApplicability to multi-layer architectures (bounds are single-layer only)\n\nSuggested additions: Our theoretical framework analyzes idealized models with unbounded components, limiting direct applicability to practical transformers. The parameter overhead and unvalidated complexity claims require empirical verification before deployment recommendations.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The split-VC dimension represents a creative adaptation of classical VC theory to transformer analysis, providing rigorous mathematical foundations for expressivity limitations.\n2. Lower bound proofs are technically sound, with elegant reductions (e.g., function composition to Ind_n) demonstrating fundamental limitations of pairwise attention mechanisms.\n3. Strassen attention's sub-cubic complexity for ternary interactions shows theoretical promise, correctly identifying that compositional tasks require higher-order token relationships.\n4. The framework successfully isolates attention as the computational bottleneck, proving limitations hold even with unbounded MLPs and arbitrary positional encodings.\n\nWeaknesses\n\n1. Strassen attention requires 67% more parameters (5 projection matrices vs. 3), fundamentally confounding architectural innovation with capacity scaling. Without parameter-matched comparisons, performance gains remain unattributable.\n2. Exclusive evaluation on synthetic tasks (Match3, quotient relations) provides no evidence of practical utility. The absence of CLUTRR/COGS benchmarks renders compositionality claims speculative.\n3. Unbounded MLPs (P >> d,H) and arbitrary positional encodings create a framework analyzing impossible models. Real transformers with bounded components may exhibit entirely different limitations.\n4. The O(n^2.372) complexity requires validation under hardware constraints. Memory bandwidth limitations (2.67× accesses), numerical stability, and energy efficiency remain unaddressed.\n5. Missing comparisons with modern efficient attention (Performer, BigBird, GQA) and recent compositional reasoning advances (Bhattamishra et al., 2024) undermines positioning within contemporary research.", "was_revised": true, "final_justification": "I have reviewed the author's reply and I decided to increase my score.", "rebuttal": "We thank the reviewer for  insightful comments. Below, we reply to the weaknesses and questions raised by the reviewer.\n\n* _(Weakness 1)Strassen attention requires 67% more parameters (5 projection matrices vs. 3), fundamentally confounding architectural innovation with capacity scaling. Without parameter-matched comparisons, performance gains remain unattributable._\n\nWe thank the reviewer for pointing out this concern. To address it, we have repeated two experiments from the tasks that require less computation time (Quotient Binary  Relation Composition and Binary Relation Composition). We have compared 1-layer Strassen Attention against 2 layers of Standard Attention, both models with hidden dimension 16. The number of trainable parameters are shown in the following table:\n\nStrassen (1 Layer):  2.5k (Binary Relation Composition), 2.5k (Quotient Binary Relation Composition).\n\nStandard (2 Layer): 3.6k (Binary Relation Composition), 3.6k (Quotient Binary Relation Composition) \n\nThe obtained accuracies are presented below:\n\nStrassen (1 layer): 100 % (Binary Relation Composition), 98% (Quotient Binary Relation Composition).\n\nStandard (2 layer): 92 % (Binary Relation Composition), 82% (Quotient Binary Relation Composition).\n\nThis analysis revealed that 1-layer Strassen attention still clearly outperforms a 2-layer Standard attention (and about 40% more parameters than the Strassen) in both of the tasks considered. We will include these results in the revised version of the paper. \n\n* _(Weakness 2)Exclusive evaluation on synthetic tasks (Match3, quotient relations) provides no evidence of practical utility. The absence of CLUTRR/COGS benchmarks renders compositionality claims speculative._\n\nWe performed an additional experiment on COGS to compare Strassen and Standard attentions under a parameter-matched scenario using the following hyperparameters from [1]: learning rate (5e-4), dropout (0.1), batch size (100), linear warmup scheduler and no early stopping criteria. We have met an accuracy for Standard attention Transformer that was reported by [2] under a similar configuration. All the results are condensed in the following table:\n\nStrassen:  3 (Layers), 64 (hidden dimension), 99k (#Parameters), 72% (Accuracy).\n\nStandard: 3 (Layers), 68 (hidden dimension), 99k (#Parameters), 65% (Accuracy)\n\nThis analysis revealed that Strassen attention exhibited a significantly higher performance in the COGS task. We thank the reviewer for suggesting this, and we will include results of this experiment into the revised version of the paper.\n\n[1] Bergen, L, O'Donnell, T., Bahdanau, D.2023. Systematic Generalization with Edge Transformers.\n\n[2] Csordás, R., Irie, K., Schmidhuber, J. 2022. The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers.\n\n* _(Weakness 3) Unbounded MLPs (P >> d,H) and arbitrary positional encodings create a framework analyzing impossible models. Real transformers with bounded components may exhibit entirely different limitations._\n\nThe limitations derived from our lower bounds hold for any kind of MLPs and any kind of positional encoding. This is not a weakness but a strength. In particular they also apply to real transformers. Moreover, our positive results are proved by exhibiting transformers with constant size components, as those used in practice. \n\n\n* _(Question 1) Can you provide experiments comparing Strassen attention against standard attention with matched parameters (either 5 projection matrices or d'=1.29d)? Include ablations testing V_1=V_2 weight sharing._\n\nWe thank the reviewer for pointing this concern. We have addressed the comparison with matched parameters in our answer to weakness 1.  We performed the experiment suggested by the reviewer (V_1 = V_2 weight sharing) for the Quotient Binary Relation Composition task.  The accuracy for this experiment was 88%, which is significantly lower than the 98% accuracy obtained without ablation. \n\n* _(Question 2) Will you evaluate on CLUTRR (n>=128) and COGS to demonstrate practical compositional advantages? What performance improvements justify 67% parameter overhead?_\n\nThis was addressed in weakness 2.\n\n\n* _(Question 3) Please provide GPU runtime measurements (A100/H100) for sequences {1k, 4k, 16k} showing actual crossover points where Strassen outperforms standard attention in wall-clock time._\n\nStrassen attention enjoys sub-cubic complexity time. It is designed to run faster than other higher-order attention mechanisms which also have a strictly greater expressivity when compared to Standard attention. But none of these more expressive attention mechanisms outperform Standard attention in running time, since Standard attention enjoys quadratic time only. Strassen outperforms the Standard attention not in time but in accuracy. \n\n* _(Question 4) Can you prove lower bounds under realistic assumptions: bounded MLPs (P=O(d^2)) and structured positional encodings (p(i,sigma_i) = q(i) + r(sigma_i) )? How do results change?_\n\nYes, our lower bounds hold for any kind of MLPs and any kind of positional encoding, including those suggested by the reviewer.  For example, in Theorem 3.7 we show that no one-layer standard attention transformer with n^{o(1)} size can solve the binary relation composition task. Since the transformer suggested by the reviewer is a standard-attention transformer of n^{o(1)} size, it follows that such transformers cannot solve the binary relation composition task. \n\n* _(Question 5) Are all three interaction terms (f_i g_j + g_j h_k + h_k f_i) essential? Provide ablations removing individual terms and testing reduced-rank projections._\n\nFrom a theoretical point of view, all three interaction terms are essential in our solutions (upper bounds) for the binary relation composition, the match 3, and the quotient binary relation tasks. From an experimental point of view, and following the suggestion of the reviewer, we performed three experiments on the Quotient Binary Relation Composition task, in which we removed the first, the second, and the third interaction term, respectively. In all cases we obtained that accuracy was about 71%, significantly lower than the 98% accuracy obtained without ablation."}, {"review_id": "EPGiixygcw", "reviewer": "Reviewer_tYaL", "summary": "This paper studies theoretical limitations of the transformer architecture, and proposes an alternative to attention mechanism - strassen attention. The main contributions are summarized as follows.\n1. This work introduces a new technique, called splitting-VC dimension, for transformer size lower bound. This paper proves that any single-layer transformer that computes a function $f$ must have one of embedding dimension, number of attention heads, size of MLP greater than the splitting-VC dimension of $f$, even if the transformer has infinite precision.\n2. Furthermore, this paper takes advantage of this new technique to prove lower bounds for reasoning tasks such as function composition, triple-wise correlation, (quotient) binary relation composition. It shows that all three tasks require the model size (max of MLP size, embedding dimension, number of heads) to be at least $n^{\\Omega(1)}$ for single-layer transformers.\n3. This paper proposes a new alternative to attention mechanism, called strassen attention, that requires $O(n^{\\omega})$ time to inference, but overcomes the lower bounds for transformers on the tasks above.\nThe theoretical results for strassen attention are verified by a series of experiments.", "questions": "1. I think it is not hard to see that in terms of representational power, attention < strassen attention < third-order attention? I believe that it is helpful to mention this.\n2. Based on question 1, it is interesting that strassen attention outperforms third-order attention in figure 1. Do the authors have some ideas why this would happen?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. Limitations of the transformer architecture, or attention mechanism, is an interesting and important area of research. In addition, this paper provides a concrete and novel technique for transformer lower bounds (compared to previous work that was often based on communication complexity).\n2. I think the idea of strassen attention is quite interesting. One can view the standard attention matrix as an $n \\times n$ matrix such that each entry corresponds to one pair of key and query $\\langle q_i,k_j\\rangle$, the third-order attention (defined in [1]) matrix as an $n \\times n^2$ matrix such that each entry corresponds to the triple-wise inner product of $q_i,k_{1j},k_{2\\ell}$, and here the strassen attention matrix as $\\langle q_i,k_{1j}\\rangle+\\langle q_i,k_{2\\ell}\\rangle+\\langle k_{1j},k_{2\\ell}\\rangle$. Intuitively, strassen attention is the “middle-ground” of standard attention and third-order attention, where it has strictly stronger representational strength compared to attention but strictly weaker representation strength compared to third-order attention.\n3. Theoretical results are verified by experiments. Based on figure 1, it seems like strassen attention outperforms standard attention with respect to accuracy/time, which alleviates the concern of super-quadratic training/inference time.\n\nWeakness:\n1. The lower bounds proved are only for single-layer transformers, which weakens the lower bound results. I think a lower bound for multi-layer transformers would be very interesting, although I understand it is a generally difficult problem.\n2. Regarding the motivation of splitting-VC dimension (line 174-179), my understanding is that, for tasks like function composition, the input contains both the “real input” and functions and therefore we want to split the input into two parts. Are there more motivations? What is its connection to VC dimension? \n3. I think the presentation of section 2 is not clear enough. It could be a personal taste but I think some more explanation (for example, strengths part 2) could be helpful.\n4. The tasks/functions here are mostly binary functions and therefore can be parameterized by the splitting-VC dimension. What about other tasks that are not binary? For example next token prediction, translation etc?\n5. The experiments are small-scale experiments. It is unclear whether strassen attention based transformers are efficient when the model size gets larger. Are there efficient implementations? The real running time for strassen attention will eventually still based on matrix multiplication on hardware, which takes cubic time still as the $n^{\\omega}$ time algorithm exists only in theory.\n\nOverall I find the most interesting parts of this work to be a new technique for proving binary function lower bounds for transformers, and the empirical results which show that strassen attention based transformers outperform vanilla transformers on a series of reasoning tasks. Due to the limitations stated above, I suggest a borderline accept.\n\n[1] Clayton Sanford, Daniel J. Hsu, and Matus Telgarsky. Representational Strengths and Limitations of Transformers. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36.", "was_revised": true, "final_justification": "I think this work is an interesting theory work with some experiments verifying the results. In particular, I find the new lower bound technique pretty interesting. The main limitation, I believe, is the lack of larger scale experiments and that the theory results fail to generalize to multi-layer transformers, which is a bottleneck for many such analysis. Therefore, I suggest a borderline accept.", "rebuttal": "We thank the reviewer for the positive appraisal of our work and greatly appreciate the time invested in reviewing it. Below, we reply to the weaknesses and questions raised by the reviewer.\n\n* _(Weakness 1) The lower bounds proved are only for single-layer transformers, which weakens the lower bound results. I think a lower bound for multi-layer transformers would be very interesting, although I understand it is a generally difficult problem._\n\nThe main technical challenge for extending lower bounds to multi-layer softmax encoders is that this requires breakthrough results in computational complexity theory (see Chen, Peng, and Wu, ``Theoretical limitations of multi-layer Transformer’’, Appendix B). The function composition task can be done in 2 constant-size standard-attention layers. For our other 3 tasks we conjecture that they cannot be done with a constant number of layers of n^{o(1)}-size standard attention layers.\n\n* _(Weakness 2) Regarding the motivation of splitting-VC dimension (line 174-179), my understanding is that, for tasks like function composition, the input contains both the “real input” and functions and therefore we want to split the input into two parts. Are there more motivations? What is its connection to VC dimension?_\n\nThe main motivation is to avoid communication complexity arguments and considerations of precision. The connection to VC dimension is made precisely by splitting the input of the transformer, which can then be naturally seen as implementing a hypothesis class to which the regular notion of VC dimension applies.  This allows us to invoke results from VC-dimension theory in order to obtain our results. \n \n\n* _(Weakness 4) The tasks/functions here are mostly binary functions and therefore can be parameterized by the splitting-VC dimension. What about other tasks that are not binary? For example next token prediction, translation etc?_\n\nWith our method one can obtain lower bounds for any kind of task as long as there is a reduction to a binary function with high splitting-VC dimension. We do so, for instance, for the function composition which is not a binary task. We envision that a similar thing can be done for tasks like next-token prediction.\n\n* _(Question 1) I think it is not hard to see that in terms of representational power, attention < strassen attention < third-order attention? I believe that it is helpful to mention this._\n\nA Strassen-attention layer can be simulated by a third-order attention layer with constant blow-up in the embedding dimension. We do not know whether this can be done in the other direction, but we find it unlikely, given that a Strassen-attention layer can be implemented faster.\n\n* _(Question 2) Based on question 1, it is interesting that strassen attention outperforms third-order attention in figure 1. Do the authors have some ideas why this would happen?_\n\nThis is an interesting point. We think this is related to a difference in learnability between both architectures. Strassen attention seems to have a nicer loss landscape for certain tasks, but more work is required in order to confirm this hypothesis."}]

Author rebuttal:

Meta-review: The paper makes a solid theoretical contribution (infinite-precision one-layer lower bounds via spVC), introduces a well-motivated attention mechanism with proven capability on targeted tasks, and presents supportive experiments including a new compositional generalization result on COGS with parameter control. However, open questions about multi-layer extensions, practical runtime/scale, and explicit positioning relative to VC-dimension work remain. The camera-ready should (i) clearly distinguish from Kozachinskiy (arXiv:2412.20195), adjusting novelty claims, (ii) expand related work, and (iii) improve clarity/presentation and, if possible, add preliminary runtime/memory measurements.
Decision: Accept (poster)