Representational Strengths and Limitations of Transformers
Authors: Clayton Sanford
Daniel Hsu
Matus Telgarsky
Venue: NeurIPS 2023 poster (2023)
Keywords: self-attention
approximation theory
communication complexity
TL;DR: We give function approximation tasks that demonstrate the advantages of transformers over RNNs and FNNs, the impact of the self-attention embedding dimension on expressivity, and the limitations of any bounded-size layer of self-attention.

Abstract: Attention layers, as commonly used in transformers, form the backbone of modern deep learning, yet there is no mathematical description of their benefits and deficiencies as compared with other architectures. In this work we establish both positive and negative results on the representation power of attention layers, with a focus on intrinsic complexity parameters such as width, depth, and embedding dimension. On the positive side, we present a sparse averaging task, where recurrent networks and feedforward networks all have complexity scaling polynomially in the input size, whereas transformers scale merely logarithmically in the input size; furthermore, we use the same construction to show the necessity and role of a large embedding dimension in a transformer. On the negative side, we present a triple detection task, where attention layers in turn have complexity scaling linearly in the input size; as this scenario seems rare in practice, we also present natural variants that can be efficiently solved by attention layers. The proof techniques emphasize the value of communication complexity in the analysis of transformers and related models, and the role of sparse averaging as a prototypical attention task, which even finds use in the analysis of triple detection.

Representational Strengths and Limitations of Transformers
Clayton Sanford, Daniel Hsu Department of Computer Science
Matus Telgarsky Courant Institute New York University New York, NY 10012 matus. tetuurstlggasskynnyy
Columbia University
New York, NY 10027
(clayton,djhsuueee wwt.:ri...oubbb.eee......o
Abstract
Attention layers, as commonly used in transformers, form the backbone of mod- ern deep learning, yet there is no mathematical description of their benefits and deficiencies compared with other architectures. In this work we establish both positive and negative results on the representation power of attention layers, with a focus on intrinsic complexity parameters such as width, depth, and embedding dimension. On the positive side, present sparse averaging task, where recur- rent networks and feedforward networks all have complexity scaling polynomially in the input size, whereas transformers scale merely logarithmically in the input size; furthermore, we use the same construction to show the necessity and role of a large embedding dimension in transformer. On the negative side, present triple detection task, where attention layers in turn have complexity scaling linearly in the input size; this scenario seems in practice, variants that can be efficiently solved by attention layers. The proof techniques emphasize the value of communication complexity in the analysis of transformers and related models, and the role of sparse averaging as a prototypical attention task, which even finds use in the analysis of triple detection.
also present natural
Introduction
In recent years, transformer networks (Vaswani et al. 2017 have been established as a fundamen- tal neural architecture powering state-of-the-art results in many applications, including language modeling OpenAl 2023). computer vision Dosovviskiy et al. 2021], and protein folding [Jumper] al. 2021]. The key building block of transformer models is the self-attention unit, primitive that represents interactions among imput elements as inner- omer-products between www-dimensional embeddings of these elements.
The success of transformer models linked to their ability to scale their training and generaliza- tion performance to larger datasets and sequence lengths. Their representational capacity, however, underlies this scaling power, and is tied to the inductive biases of their learning algorithms. Empir- ically, transformer models trained with gradient-based learning algorithms exhibit biases towards certain algorithmic primitives [Edelman et al.) 2022 Liu et al. 2022 and learn representations that may encode Comain-specifee information in attenntoo units Clark et al. 2019 Hewitt and Manning 2019 Rogers et al., 22200] Chen et al. 22022. These examples indicate that transformer architectures only provide computational benehit,, but also have representational capabilities that are particularly well-matched to practical tasks.
In this paper, investigate these inductive biases by identifying "natural" computational tasks for which transformers are well-suited, especially compared to other neural network architectures, as well tasks that highlight the limitations transformers. The tasks-sparse averaging, pair-matching,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and triples-matchinn matching represent primitive operations that aggregate structural information encoded in embeddings. We use these tasks to elucidate the relationship between the embedding dimension of a self-attention unit and its expressivity, and to showcase the fundamental representational limitations of self-attention layers.
In our model, the primary computational bottleneck faced by transformer in computing "sequence- io-sequence" function f: X + y is the constrained processing of pairs of input elements {zi, 2ÿ} E (2): we allow transformers unbounded computational power when processing the individ- ual elements 24 X. This motivated by modern scaling regimes where the context length N has rapidly increased, the self-attention embedding dimension m remains much smaller than N. and the parameterization of multi-layer perceptrons (MLPs) that operate on individual elements is much larger than m. Indeed, the largest GPT-3 model [Brown et al.] 2020) features context length N = 2048, an embedding dimension m 128, and MLPs with a 12288 2288-dimensional parameterization; the context length of GPT-4 is as large as N = 32000. As such, we are interested in the capabilities of transformers with N=o(1) total "size", as opposed to _V The nature of the bottleneck in our model makes the tools of communication complexity indispensable for formalizing computational limits.
1.1 Our contributions
Sparse averaging separations among atomic self-attention units. The q-sparse averaging task qSA aims to capture the essential approximation-theoreae the ith input T; is pair (yi, 2;), where 2; E Id' is the data part of r;, simply a vector in Rd whereas and y; (Ivl) is the indexing part, which specifies q locations in the input sequence; the ith output element in qSA is obtained by averaging the g data parts 2j given by j E yi. meaning
properties of self-attention units. In gSA,
gSA ((v1, 21),.... (UN, 2N))
=
Σ 9
1
2j
1
Σ 2j
q JEYN
JE
(See also Definition As summarized in the following informal theorem, our analysis of qSA in Sec- and Appendix illustrates the ability of the self-attention primitive to associate arbitrary subsets of input elements (as opposed to just "local" subsets, as specified by some sequential/oppoloiica structure), measures the expressive power accrued by increasing the embedding dimension of self-attention unit, and indicates the representational limitations of "traditional" neural architectures on basic computational tasks.
The task aSA for E 2, satisfies the following properties (see Definition for a formal definition and approximation metric).
Informal Theorem 1.
1. There exists unit of self-attention f with an m-dimensional embedding that approximates gSA if and only if m Zo 9'Theoreess Band
2. Any fully-connected neural network whose output approximates qSA requires its first hidden layer to have width at least ((Nd) (Theorem TO).
3. Any recurrent neural network whose iterates approximate qSA requires hidden state of at least ((N) bits (Theorem TT..
We consider the qSA implementation in Item I efffccien since the dimension of the model parameters grows with poly(g, d, log N). whereas the latter two are inefficient since their parameter (or state) dimension grows (NV). The proof's of the positive results employ embeddings for each index j and each subset yi that have large inner products and only if j E Yi. The negative results involve communication complexity reductions and geometric arguments. These arguments naturally introduce a dependence on bits of precision, which we suppress above within the notation "Z"; we results are arguably more relevant to modern networks, which uses as few as 4 or even 2 bits of numerical precision.
note that these bounded-precisee
Contrast between pairwise and triple-wise matching with self-attention layers. We frame stan- dard transformer architectures as being able to efficiently represent functions that are decomposable
Note, however, that attention units are permutation equivariant, so the order of elements in the input "sequence" X E N is irrelevant. In practice, positional encodings used when the sequence order is relevant.

---

into sparse pairwise interactions between inputs. To do so, we introduce two sequential tasks and prove a collection of constructions and hardness results that characterize the abilities of transformers to solve these tasks.
Given input sequence X = (21....., [N) E [M] (for some = poly(N)), we formalize the problems of similar pair detection (Match2) and similar triple detection (Match3) as
Match2(X)xe(n = {3j s.t. 2, + 2j = 0 (mod M)) Match3(X) (X)ee) = (3 24 + Ti + 22 = (mod M)}
(1)
(2)
For both tasks, note that the output is an N-dimensional vector whose ith element if and only the sequence X" includes pair or triple containing z;. In this sense, the problems differ from 2SUM and 3SUM, which are not
to-eneeee---s tasks.
We believe these two tasks are intrinsically "pairwise" and "triple-wise", respectively; moreover, since we also believe self-attention performs fundamentally "pairwise" operation, we will use Match2 and Match3 to show a sharp gap in the representation power of self-attention.
Informal Theorem 2.
1. single unit of standard self-attention with input and output MLPs and an O(d)-dimensional embedding can compute Match2 (Theorem 6)
2. A single layer of standard multi-headed self-attention cannot compute Match3 unless its number of heads H or embedding dimension m grows polynomially in N (Theorem 7
3. standard transformer model can efficiently compute a modified version of Match3 that makes assumptions about embedding structure or locality (Theorems (
4. Under generalized notion of Whirddorder tensor self self-attention" introduced in Appendix C.3 Match3 efficiently computable with single unit of third-order attention (Theorem) T8).
While the above result demonstrates the limitations of multi-headed self-attention and illustrates the importance of learning embeddings with contextual clues, we believe that stronger result exists. Specifically, we conjecture that even multi-layer transformers are unable to efficiently compute Match3 without hints or augmentation.
Informal Conjecture 1. Every multi-layer transformer that computes Match3 must have width, depth, embedding dimension, or bit complexity at least NR(1)
In Appendices C.5 and C.6 we give a heuristic information theoretic argument to support this
conjecture, prove matching upper-bound, and finally prove analogous results for rraph-augmented transformers with respect to the problem of cycle detection in directed and undirected graphs
1.2 Related work
Several computational and learning- -aaming-theoortice aspects of transformers, distinct from but related the specific aims of the present paper, have been mathematically studied previous works.
Universality and carilg-compleetnness. To demonstrate the power of transformers, universal approximation results for transformers Yunn et al. 2020 Wei et al. 2022)-analogous to results for feedforward networks (Fornik et al. 1989 establish the capability for sufficiently large networks to accurately approximate general classes of functions. Note, however, that the precise minimal dependence of the required size (c.g., number of attention units, depth of the network) as a function of the input size N does not directly follow from such results, and it is complicated by the interlcaving of other neural network elements between attention layers. (Approximate) transformers demonstrates their power in different manner, and such results have been established, first assuming infinite precision weights [Pérez al. 2019) and later also with finite- cntte-precisoo [Wei] et al. 2022). Such results are more closely aligned with our aims, because Turing machines represent a uniform model of computation on inputs of arbitrary size. Wei et al. (002) showed that Turing machines that run for 7 steps can be approximated by "encoder-decoder" transformers of depth log(T) and size polynomial in log(T) and the number of states of the Turing machine (but the decoder
curing-completennsss of
runs for I steps).
3

---

Formal language recognition. The ubiquity of transformers in natural language understanding has motivated the theoretical study of their ability to recognize formal languages. On the positive side, Bhattamishra et al. (2020) constructed transformers that recognize counter languages, and Yao et al. [202T] showed that transformers of bounded size and depth can recognize Dyek languages that have bounded stack depth. Liu et al. (2022) showed that the computations of finite-state automata on sequences of length can be performed by transformers of depth log(NV and size polynomial in the number of states. On the negative side, Hahn [2020) showed limitations of modeling distributions over formal languages (including Dyck) with fixed-size transformers (though this result does not imply quantitative lower bounds on the size of the transformer). Hahn 20200] well as Hao et al. 2002]. also establish the inability of "hard attention" " Transformers to recognize various formal languages and circuit classes by leveraging depth reduction techniques from circuit complexity [Furst et al. 1984..
Learnability. The sample complexity of learning with low-weight transformers can be obtained using techniques from statistical learning theory and, in turn, establish learnability of certain boolean concept classes (e.g.. sparse parity) [Edelman et al. 2022 Bhattamishra et al. 2022] using transformer- based hypothesis classes. Our qSA function is inspired by these classes, and we establish concrete size lower bounds for approximation (and hence also learnability) by transformers. We note that our constructions use bounded-size weights, and hence, in principle, the aforementioned sample complexity results can be combined with our results to analyze empirical risk minimization for learning transformers. Prior work of Likhoshesttov et al.] [202T] also shows how sparse attention patterns can be achieved by self-attention units (via random projection arguments); however, when specialized to gSA, their construction is suboptimal in terms of the sparsity level q.
Related models. Graph neural networks (GNNs), like transformers, process very large inputs (graphs) using neural networks that act only on small collections of the input parts (vertex neighbor- hoods). Many classes of GNNs are universal approximators for classes of invariant and equivariant functions (Maron al. 2019 Keriven and Peyré. 2019]. At the same time, they are restricted by the distinguishing power of certain graph isomorphism tests (Xu et al. 2018 Morris et al.) 2019 Chen 2019), and lower bounds have been established on the network size to approximate such tests [Aamand et al. [022]] Loukas (2019) established a connection between GNNs and the LOCAL [Angluin| 1980] and CONGEST (Peleg 2000] models for distributed computation, and hence notably
directly translates lower bounds for CONGEST notaablyyyyb cycle detection problems- into size lower bounds for GNNs. Our lower bounds for cycle detection using transformers also leverage a connection to the CONGEST model. However, transformers do not have the same limitations as GNNs, since the computational substrate of a transformer does not depend on the input graph in the way it is with GNNs. Thus, we cannot directly import lower bounds for CONGEST to obtain lower bounds for transformers.
Transformers are also related to other families of invariant and equivariant networks. Our focus on Match2 and Match3 (and related problems) was inspired by the separation results of Zweig and Bruna [0022 between models for processing sets: Deep Sets [Qi et al. 2017 Zaheer et al. 2017]. which are "singleton symmetric", and the more expressive Relational Pooling networks |Santoro et al. 2017]. which are only "pairwise symmetric".
1.3 Conclusion and future work
Our primary contributions are to present a multi-faceted story about transformer approximation: firstly, qSA separates transformer models approximation-thoortieee moreover the attention embedding dimension both necessary and sufficient for qSA scale directly with q. meaning qSA also functions to characterize representation power amongst different transformers. Secondly, while single units of self-attention can solve the Match2 task, even wide layers of self- attention with high- nigh-dimensional embeddings cannot solve Match3, and we believe that deeper models cannot as well. This question of deeper models is stated as a formal conjecture and addressed heuristically in Appendix [.6 using both information- and communicaiion-thooree proof techniques, both of which we feel are significant steps towards a complete proof.
from RNNs and MLPs, and
While our investigation is purely penooximmationtthooettie we also include in Appendix D prelimi- nary empirical study, showing that attention can learn gSA with vastly fewer samples than recurrent

---

networks and MLPs; we feel this further emphasizes the fundamental value of qSA, and constitutes an exciting direction for future work.
Beyond the explicit open question in Informal Conjecture 1 we anticipate that future research could connect the separation results proved in this work to formal linguistic theory and empirical work attention matrix interpretation. This work examines Match2 and Match3 because we believe that the former could represent key primitive for language processing tasks such as co-referencing, while the latter represents a natural extension of the former that likely is not necessary for language modeling. Rather, it may be possible that language modeling performs triple-wis, wwiee- modeling for tasks such the identification of subject, verb, and object components by relying on pairwise matching constructions and "clues" learned within an embedding, such as those encoded in toy problems Match3Bigram and Match3Loca That is, transformers serve useful foundational model for language modeling because of their abilities to integrate contextual clues and pairwise communication, and while they are not extensible to "purely triple-wise problems," most practical sequential problems have some efficient decomposition to pairwise structures that can be easily exploited by these architectures. Future work by linguists, theoretical computer scientists, and empirical NLP practitioners could assess how foundational our primitives are and study whether there are any practical triple-wise problems that transformer models fail to solve.
2 Preliminaries
Let Bd = fa Rd ||||| 1} denote the unit ball in R and let [n] = (1,,2.... n denote the first positive integers. The expression (P) equals if predicate P is true and 0 otherwise. The row-wise softmax operator applied to matrix A E IRNxM returns
exp(A,,))
softmax(AAis,
Eyz= ())()
2.1 Attention units and transformer architectures
We first introduce the concept of self-attention, which is used the building block of all transformer architectures included in this paper.
Definition 1. For input dimension d, output dimension d', embedding dimension m, precision p. and matrices Q, K E Bdxm and V E Igdxd" (encoded using p-bit fixed-poin numbers), a self-attention unit a function fQ,K. Nxd + N.d' with
fQ.K.v (X) softmax XXQ'xxxXXX
Let Ad,,d'' = (JQ.xv Q, V. denote all such self-attention units.
Self-attention units can be computed in parallel to create multi-headed attention.
Definition For head-count H and self-attention units fH Ad,m.d' 22 multi-headed attention layer is function Li.....f Nxd + R with Ly.... (X) = = fn (X). Let All Adm,d' p contain all such fi....f.
Transformer models are composed of two components: element-win wise multi-layer perceptrons. Due to universal approximation results, we model multi-layer perceptrons arbitrary functions mapping fixed- preccipeciiion vectors to themselves.
attention layers (as above) and
Definition 3. A multi-layer perceptron (MLP) layer is represented by some & Rd + Rd whose real-valued inputs and outputs can be represented using p-bit fixed- precision numbers. We apply á to each element (i.e., row) of an input X E xd abusing notation to let ((X) = (d(x)),...... ((#N)) E Nxd' Let &a,d', denote all such MLPs.
We concatenate the notation of each class of functions to denote function composition. For example, for output dimension d', we use A'a.m.'' == Am.m. d.m.p and A All.m, Pdmm. represent single-headed and multi-heade attention units with input MLP respectively. (The capabilities and limitations of these models are studied in Section 3) For depth D, we let
Thl p 4m.d' (pm.d'p(AAle (A m.. D-1 Hr
A.m.m.p
5

---

represent full transformer model comprising D layers of H- H-headed self-attention with interspersed MLPs.
While two key features of transformer architectures- residual connection and the positional embedding- are conspicuously missing from this formalism, the two be implemented easily under the framework. We can include a positional embedding by encoding the index as coordinate of the input, i.e. I2,1 i. Then, the subsequent MLP transformation ((X) can incorporate suitably into the embedding. A residual connection can be included additively as input to a multi-layer perceptron layer (as is standard) by implementing an "approximate identity" attention head f with Q, K and V Im set to ensure that fXX = x
We periodically consider transformers implemented with real-valued arithmetic with infinite bit complexity; in those cases, we omit the bit complexity p from the notation.
Finally, we assume for the proof of Theorem 3 that the model is permitted to append single <END> token at the end of sequence. That is, we say that a model f E T..mmd'.. represents target h : RN xx Nxd if f(X)) ((X) when X' (Z1...., IN, x²) for constant-valued E gd.
3 Sparse averaging with attention units
We present the sparse averaging task to highlight the ability of transformer architectures to simulate wide range of meaningful interactions between input elements. This task demonstrates how the embedding dimension a self-attention unit modulates the expressive capabilities the architecture, while showcasing the inabilities of fully-connected and recurrent neural networks capture similar interactions (see Appendix[A] (A).
Definition 4. For sparsity problem dimension d', and input dimension d = d' + + + 1. consider an input X (z1,...,ZN) E R N with 2; = (2;; (6;) for E Bd" and yı E ((N)) Let the
q-sparse average be
(SA(X)= =
Zy..
iE[N]
For accuracy >> 0, function f: Nxd + N c-approximates qSA if for all X,
max EE[N]
- (SA(x))l S..
Figure Ia visualizes the sparse averaging task as a bipartite graph between subsets y; and elements 2; with corresponding averages. Theorems jointty show that the minimum embedding dimension m of single self-attention units A' A',m,d' p that ((2) -approxiiie qSA scales linearly with q. We believe that the sparse averaging problem is thus canonical problem establishing the representational capabilities and inductive biases of self-attention units.
3.1 Self-attention can approximate gSA when m Z
Our principle positive result shows that the sparse averaging task gSA can be approximately solved using fixed-precision arithmetic self-attention units with embedding dimension m growing with q log N.
Theorem 2 (Fixed-precision). For any N, any m 2 Q(d + gogg N), any e (0,1), and p 2(log(? log N)), there exists some f E Ala x that e-approximates gSA.
While the full proof appears in Appendix B.I we briefly sketch the argument here. Because the output of self-attention unit is a convex combination of rows of the value matrix <(X)V Nxd", natural way to approximate 9SA with a unit of self- att-ntttenton is to let each value be the corresponding
with iid Gaussian columns fixed every index Then, the diagonals X XQKTX X are larger than all other entries and its softmax is approximately Tx- We may encode element subset of [.V as vector in [N] constrained have distinct components.
AA simple construction involves letting XQ

---

9SA(X)
1
2
3
N
KT (x4)
KJ ('p(x,)
2
(TT((z)
3
11
2/2
3/
144
VN
Q'
94
KT (xx3)
21
23
K²
K ('
2
Softmax (oftmax(((X)00" <XXV
(a) Bipartite graph re- lating ys and in (SA(X).
(b) Attention and value matrices used for the self- attention construction of 4SA(X) in Theorem
(c) Key and query embeddings that produce the self-attention matrix in (b).
Figure I: A visualization of the qSA function outputs given sequence of inputs (24; 1) ie[N] as bipartite graph between subsets y, and vectors 2; (a), and of the attention matrix (b) and underlying embeddings (c) that produce the self-attention construction in Theorem
(a) T 0.
(b) -
(c) T = 40000.
E 20 for a fixed example after T epochs of training self-attention unit to solve gSA for q = 3. Each row i corresponds subset yi, and each cell E yi is outlined in red. See Appendix for experimental details.
Figure 2: Attention matrix softmax(di) (omaax(((X((FF))) (XTXXQTTOO ((X)) (X))(XX(XX)))) X
vector in the average (i.e. VTo(a:) = 2;) and choose the key and query functions in order to ensure that the attention matrix satisfies
if Vi. otherwise.
softmax(
~
To do so, let each key KT (")(x;) represent fixed vertex convex polytope, which depends only on index and constructed from random binary vectors. We select each query Q (Td(x;) ensure that ((x))TQ"" Φ(æ,) is a fixed large value if j and a slightly smaller value otherwise. We obtain the precise query, key, and value embeddings by employing tools from dual certificate analysis from the theory of compressed sensing.
We visualize this construction in Figure Tb and Ic q 3 and d' which presents the associated attention and value matrices necessary for the construction. and plots a polytope of keys (red dots) with each face corresponding each subset y (green dots). The construction empirically relevant; Figure 2 shows that unit of self-attention trained on data generated by the qSA task recovers similar attention matrix the one stipulated our construction and visualized in Figure Ib]
The logarithmic dependence of the embedding dimension m on the sequence length N can be eliminated by considering self-attention units with valued arithmetic with infinite bit complexity.
Theorem 3 Lnfinite-precision For fixed N, 2 2idd +9) and O, there exists some A'amm that e-approximates gSA.

---

/1
Alice:
Vs
(xx((x)
V9
mp bits
2 24
Bob:
b
f(X,, = qSA(Xss
#
DaSI(a, b)
Figure 3:
The my-bbit communication protocol used to reduce the hardness of computing gSA with single unit of self-attention the hardness of solving the DISJ communication problem for the proof of Theorem for
The proof of Theorem employs similar polytope-based construction in Appendix B.2 relying on a cyclic polytope rather than one drawn from discrete boolean vectors. Theorem 16 proves the near-optimality of that bound by employing a geometric argument to show that variant of qSA can only be approximated by a restricted family of self-attention units with a sufficiently high-dimensional embedding.
3.2 Self-attention cannot approximate qSA when m S
We show that the construction used to prove Theorem iis nearly optimal.
Theorem 4. For any sufficiently large q, any N 2 2q + 1, and any 2 1, there exists a universal constant e such that if mp S og, then no f E T..m. exists that
2g approxximstee gSA.
(By choosing p = (g log N)), Theorem 2 is shown to be optimal up logarithmic factors of and doubly-logarithmic factors N.)
The proof of Theorem employs standard communication complexity argument based on reduction from the following sel disjointness problem the two-party communication model, in which each party possesses subset of an element domain (encoded as n-bit strings), and they wish to jointly determine whether their subsets are disjoint. We note that communication complexity commonly-use used technique for proving lower bounds the representational power of circuits and feedforward neural networks [see, c.g., Karchmer and Wigderson 1988 Ben-David et al. 2002
Martens et al. 2013 Vardi et al. 2021]
Fact 5 (Set disjointness communication lower bound Yao 1979]). Suppose Alice and Bob given imputs o, b E {0, 1),h respectively, with the goal of jointly computing DISJ(a, (a, b) = max; a;b; by alternately sending single bit message to the other party over a sequence of communication rounds. Any deterministic protocol for computing DISJ b) requires at least rounds of communication.
Our proof designs a communication protocol that Alice and Bob use to jointly compute DISJJ b) when (mp)) rounds of communication, under the assumption that such an f exists that closely approximates gSA.
Alice encodes her input a in single subset by letting y2 = {ii
i:ie [q]].
Bob uses his input b to assign 22;-1 to 2b; and 221 = -1 for all i E [q]-
All other input components are constant values known by both parties.
Alice sends her mi-bit query embedding Q' (((2(+1) bit-by-bit to Bob, who approximately computes qSA by determining the outcome of f. The crux the reduction shows that gSA(X) and only if a,,; for all E [g], which allows Bob to determine DISJ(a, b).
visualize the protocol Figure 3 and give the proof in Appendix B.3
The proofs of Theorems
21 and 23 employ similar communication complexity reductions to DISJJ

---

Standard transformer models can only efficiently represent intrinsically pairwise functions
In this section, we argue that the standard transformer architecture is unable to efficiently represent functions that do not decompose into small number of pairwise-symmetric functions. We do this by contrasting the tin)approximabili of intrinsically pairwise and triple-wise functions, respectively Match2 and Match3 (defined in I and (2). and their variants.
4.1
Efficient computation of Match2 with standard self-attention
We first show that Match2 can efficiently approximated by a single standard (pairwise) self- attention unit.
Theorem For any input size N, input range M =NO(),, and sxeed-precssion bit complexity Olog M), there exists a transformer architecture f E T with single self-attention unit with embedding dimension m = such that for all X [M] [(x) = Match2(X).
The proof, given in Appendix C.1 uses both a "blank token" and a trigonometric positional embedding, which ensures that
( + +3),k)
cos
M
for some sufficiently large constant c. This embedding ensures that cell of the attention matrix (oltmax((((X))) ((((X(((KKX(())))) (X)))ss, is extremely close to zero, unless v; = -ry (mod M).
4.2 Hardness of computing Match3 with multi-headed self-attention layer
Although Match2 can efficiently represented using a single unit of standard self-attention, repre- senting Match3 using entire layer of multi- headed attention units is impossible unless either the number of heads H, the embedding dimension m, or the precision grows as N2(1),
Theorem There is universal constant > O such that for sufficiently large N, and any M 2 N1 if mphl < cN/ log log N, then there is no f E 1mm.1.p satisfying f(X) Match3(X) for all X [M]]..
We give the proof in Appendix C.2 Like that of Theorem 4 the proof relies on reduction from set disjointness two-party communication. The proof of the lower bound applies a domain-restricted variant of Match3, which actually makes the problem substantially simpler to solve. In Remark [ show how this variant of Match3 introduces depth separation between the representational powers of single-layer and two-layer transformer models.
As mentioned in the introduction, we also conjecture that multiple layers of multi-heade attention subject to the same impossibility (Conjecture 19 The impossibility is specific to standard (pairwise) attention; in Appendix C.4 show that Match3 can be efficiently computed with single unit of shird-order self-attention.
4.3
More efficient constructions for simplified Match3 computations
While the previous sections suggests that no efficient construction exists to compute Match3 with stan- dard transformer models. practical examples of triple detection abound. For example, transformer- based language model will likely succeed in linking a subject/verb/objeet triple because all three tokens likely inhabit the same local region and because the model could agglomerate the triple by first identifying pair and then adding the third. Here, we introduce two variants on the Match3 problem that have additional structure to serve as hints. The first variant specifies triple sums comprising the input element and a neighboring pair elsewhere in the sequence: for each i E [N].
Match3Bigram/ (X); = 1 { s.t. + 2. + Ij+1 = 0 (mod M)).
The second focuses on localized sums, where are all components of a triple must be within a fixed range of constant width K & N: for each [N],
11 (aji.j2 s.t. I; + Fi 3i 0 (mod M), li ji1, --2 S K). We show that the two can be efficiently represented using compact standard transformer models.
Match3Local

---

Theorem 8. For any N, M -M=N4 NOO, and p = Ollo M) there exists transformer architecture E T with embedding dimension m and depth such that for all X E [M] xd f(X) Match3BigramiXX
Informally, the first layer of the construction uses sinusoidal positional encoding to compute each bigram sum 2j + 2:j+1 in the jth element of the sequence. The second layer applies the Match2 construction provided by Theorem to determine whether there exists j for each such that I; + + 2J+1 = 0 (mod M).
Theorem 9. For any d, N, M = p= Oflog M), and K & N, there exists a transformer
architecture f E 1m with embedding dimension m O(K log N) and bitccomplexity p Ollog(K (K log N)) such that for all X E [M] f(X) = Match3Local(X))
Proof. We implement the localized construction by using Theorem to construct a specific sparse simultaneous average of the inputs with q := 2K + 1 and d' := 2K 1. To do so, we use the input MLP to convert z; the embedding (24: y43 i). for zero-padded input
2j J;6q E R22+1
for i i (mod 2K + 1) and subset
2K )
[N]]
y/ {i- - K, i K
K+
This construction ensures that the ith element of self-attention output computes (a rotation of) (zi-K, K,, 14iK-11..... T++k). An output MLP can then verify whether any matching triples involving Ty exist among those vectors.
Acknowledgments and Disclosure of Funding
We are grateful for many discussions with and feedback from Navid Ardeshir, Peter Bartlett, Alberto Bietti, Yuval Efron, Christos Papadimitriou, Shivam Nadimpalli, Rocco Servedio, Yusu Wang, and Cyril Zhang. This work was supported in part by NSF grants CCF-1740833 and IIS-1563785, JP Morgan Faculty Award, and an NSF Graduate Research Fellowship.
References
Anders Aamand, Justin Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, and Tal Wagner. Exponentially improving the complexity of simulating the Weisfeiler-Lehman test with graph neural networks. In Advances in Neural Information Processing Systems 35, 2022.
Dana Angluin. Local and global properties in networks of processors. In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, 1980.
Shai Bav-David, Nadav Eiron, and Hans Ulrich Simon. Limitations of learning via embeddings in euclidean half spaces. Journal of Machine Learning Research, 3(Nov):441 4414-461,111 2002.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020.
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse boolean functions. arXiv preprint arXiv:2211.13311 2022.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. arXiv preprint 14115 2020.
10

---

Emmanuel J Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information theory, 51(12):4203-4115 2005.
Nuo Chen, Qiushi Sun, Renyu Zhu, Xiang Li, Xuesong Lu, and Ming Gao. Cat-probing: A metric-based approach interpret how pre-trained models for programming language atlend code 2022.
structure. arXiv preprini arXiv:2210.0em
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing Systems 32, 2019.
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning. What does bert look at? an analysis of bert's attention. arXiv preprini 19Xxiv 0, 2019.
Amit Daniely. Depth separation for neural networks. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 690 69606696..60 PMLR, 07-10 Jul 2017. URL https://ppooeeddnnss mlr press/v65, vo5ss//v55aae http///anneelylaa..a html
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2021.
Benjamin L. Edelman, Surbhi Goel, Sham M. Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, 2022.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 907-940, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. mlr. hl..ppees/vv9// e eldan16..... html
Merrick Furst, James B Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy, Mathematical systems theory, 17(1):13 2111--222111 1984.
David Gale. Neighborly and eyclic polytopes. In Proc. Sympos. Pure Math, volume 7, pages 225-232, 1963.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 8:156 171, 2020. doi: 10.1162/tacl_ (a112///ccl(((a((_aaa (1)0000))) URLhttps midoi.org//i. 10. 1tt_:/22/aa1___0000000 00306
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Trans. Assoc. Comput. Linguistics, 10:800- 810, 2022. UtL//ttss://traasaad
John Hewitt and Christopher D Manning. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019.
Kurt Homiik Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks
universal approximators. Neural Netw., 2(5):359-366, July 1989.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583 589, 2021.
Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 1988.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems 32, 2019.

---

Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller. On the expressive power of self-attention matrices. arXiv preprint arXiv:2106.03760 037644 2021.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. CoRR, abs/2210.10749, 2022. doi: 10. (0448500/xXx..2220.0002
Andreas Loukas. What graph neural networks cannot learn: depth vs width. arXiv preprint WxXiv:/907.03199 2019.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference on Machine Learning, 2019.
James Martens, Arkadev Chattopadhya, Toni Pitassi, and Richard Zemel. On the representational efficiency of restricted boltzmann machines. In Advances Neural Information Processing Systems 26, 2013.
Shahar Mendelson, Alain Pajor, and Nicole Tomczak-Jaegerman Reconstruction and subgaussian operators in asymptotic geometric analysis. Geometric and Functional Analysis, 17(4):1248-122 1282, 2007.
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric I Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, 2019.
OpenAl. Gpt-4 technical report, 2023.
David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000.
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. arXiv preprint arXiv: 199910112299 2019.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Anna Rogers, Olga Kovaleva, and Anna Rumshisky. A primer in bertology: What we know about how bert works. Transactions of the Association for Computational Linguistics, 8:842 866, Dec 2020. ISSN 2307-387X. doi: 10. 162/tacccccccc a 00349. URL httt:://ds dx. doi org/ 10. 1162/ tacl a 00349
Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. simple neural network module for relational reasoning. In Advances in Neural Information Processing Systems 30, 2017.
Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972.
Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 4111):247-261, 1972.
Matus Telgarsky. Benefits of depth in neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1517-1539, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. /tRL/ttttts://rrceeding http://ppeeeaapiaaappepeee/e////
mlr
html
Vladimir Naumovich Vapnik and Aleksei Yakovlevich Chervonenkis. The uniform convergence of frequencies of the appearance of events to their probabilities. Doklady Akademii Nauk, 181(4): 781-783, 1968.
Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir. Size and depth separation in approximating benign functions with neural networks. In Conference on Learning Theory, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz. Kaiser, and Illia Polosukhin. Attention all you need. In Advances in Neural Information Processing Systems 30, 2017.
12

---

Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: case study on approximating turing machines with transformers. Advances Neural Information Processing Systems, 35:1 35:12071-12083, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rx.v:1810.00026, 2018.
Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the Eleventh Annual ACM Symposium Theory of Computing, 1979.
Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, 2021.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are trans- formers universal approximators of sequence-to-Se to-suuunce functions? In International Conference Learning Representations, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in Neural Information Processing Systems 30, 2017.
Günter M Ziegler. Lectures on polytopes. Graduate Texts in Mathematics, 152, 2006.
Aaron Zweig and Joan Bruna. Exponential separations in symmetric neural networks. CoRR, Abss/206.01266,, 2022. doi: 10.48550/arXx..2200.11222
13

---

A
neural networks and recurrent neural networks cannot efficiently approximate qSA
A.1 Only wide fully-connected neural networks can approximate qSA
In this section, we show that any fully-connected neural network that approximates qSA R.Nd - Re must have width
(NN) We consider networks of the form f'(x:) = g(Wx) for some weight matrix W E Rm (the first layer weights) and arbitrary function g: 1 + RNd (computed by subsequent layers of neural network).
N Theorem 10. Suppose S 2' Any connecco neural network f defined as above that 2q approximates qSA satisfies m 2 rank(W)) 2 Nd.
Proof. For simplicity, arrange the input as
(1; N;V1 UN; 21; (1;..;3NN)
and W- = [W; Vi:....... Vv] with 2 zn Bd, W E RmxxNdddd), and Vi,..., Vv E gmxd'. Nd' - 1, then so too is rank([Vgi....... VNl) I No' 1. and [Vg....; VN] has If rank(W) < 2 nontrivial null space containing nonzero vector u (ugi .......iu ;uN) (N Let
2
{ max (J.....N) ||ulll2 (Ugi ... uN),
=(0ū;.... (ū;...; 0; Egi ......i Ex), and z' (Ō;:..; Egi...; -NN) Then,
1. =j E Bd for all E [N];
2. Vyzj V for all j E [M]: and
3. Ilzz- - = |l2 = 2 for some j E [q....,N.. N}.
Therefore, for any y1,..., yn E (2 respective x = (1;...; Ni #1; :1; and = (l;...; Ni W/: :.: 2'N) satisfy (xx) f(x'). Consider y with yj (I,..., 1,5) for each j E [q...,,N, Then,
f Es and qSA(x'), -
(SA(T),
q
a
Hence, [[gSA(x);- - qSA(2') 112 2 3.2 Because f(x) =(x'),
1 ="
max (11((z) gSA((>) 112 gSA((')) 112) 2
so f can approximate qSA to accuracy no better than
A.2 Only high-memory recurrent neural networks can approximate 9SA
In this section, we show that any memory- algorithm that approximates qSA Nxd Nxd' must use a large "hidden state" (memory) as it processes the input elements. This lower bound applies various recurrent neural network (RNN) architectures.
memory-bounded algorithm with an m-bit memory processes input E Nxd sequentially as follows. There is an initial memory state ho E {0, 1 For i = 1, 2.,...,,N N, the algorithm computes the i-th output f(X): E ddd and the updated memory state h; function of the input 2; E Rd and previous memory state h5-1:
(f(X), h4) = ge h4-1);
'We regard inputs as Nddddimensional vectors rather than N x matrices.
14

---

where 9: IR [0,1) - DR" x (0,1) is permitted to be an arbitrary function, and f: RNxa -
RNxe is the function computed by the algorithm.
Our lower bound applies algorithms that only need solve the subclass of "causal" instances of qSA in which the input X ((z,, Vi, i)) E IR Xxd is promised to satisfy yi = 0 for all i i N/2 + 1, and S (I,...,,,,)........ N/2 + 1} for all > N/2+1.
Theorem 11. For any E (0, 1), any -oundeed algorithm that e-approximates qSA (for q = 1 and d' on the subclass of "causal" instances must have memory m 2 (N 1)/2.
Proof. Consider m-bit memory- bounded algorithm computing function f: R Rxd R that e-approximates qSA (for = and d' = 1). We construct, from this algorithm, a communication protocol for DISJ (with N 2n 1) that uses bits of communication.
Let a, E {0, 1)" be the input for DISJ provided to Alice and Bob, respectively. The protocol is as follows.
1. Alice constructs inputs (zi, 0, for i = I,...,7 n + 1, where for each i = 1,..., ...
+1 if 0,
if a;
and
2x+1 =1.
Bob constructs inputs 2n+1+1 = (0, Un+1+i: + + for i = 1,.... n, where
{n +
if b; = 0,
Un+1+t=
{{i}
if = 1.
Observe that, for this input X = (x1, -22++1, we have
+1 0,,; = 0, if Raa = 1.
gSA(X)n++++
2. Alice simulates the memory-bounde algorithm on the first sends Bob the m-bit memory state hn+1- This requires m bits of communication.
inputs Fnt1, and
3. Starting with h1+ Bob continues the simulation of the memory nomory-bounded algorithm on these additional inputs 22.2.-.. 11
4. If any output f(X) ((4)++4+ for = 1...., satisfies
f(X)+144 < 0,
then Bob outputs (not disjoint); otherwise Bob outputs 0 (disjoint).
The approximation guarantee of f implies that sign(f ( 1...., n, so Bob outputs 1 if and only if a and are not disjoint. Because this protocol for DISJ uses m bits of communication, by Fact 5 it must be that m 2 n (N 1)/2.
1++++) (XA(X) for all i
We note that the proof of Theorem || can be simplified by reducing from the INDEX problem, which has I-way communication lower bound of n bits. This suffices for "single pass" algorothms, such as standard RNNs. However, the advantage of the above argument (and reducing from DISJ) is that easily extends to algorithms that make multiple passes over the input. Such algorithms are able to capture bidirectional recurrent neural net and related models. A straightforward modification of the protocol in the proof of Theorem 11 shows that ((N) memory is required for any algorithm that makes O(1) passes over the input (and computes the outputs in final pass).
15

---

B Supplementary results for Section
B.1 Proof of Theorem 2
Theorem 2 fixed-precision) For any N, any m 2 Oi(d + log N), any E (0, 1), and = a(log(? N)), there exists some A'.mmd's y that e-approximates qSA.
Proof. Before explaining how they produced by the imput MLP, we introduce the corresponding key, value, and query inputs. The values will simply be ((XVV ..,....,N)) For some m' m-d, let ((X) = ( uN) E R N be embedded key vectors, where U1....y UN E (#1/Vm) m' are the columns of a m' N matrix satisfying the (g. 1/4)-restricted isometry and orthogonality property (Definition 5 as guaranteed to exist by Lemma 12 and the assumption on
2
m'. Let == [2log(4N/e)]. By Lemma 13 for each y E (N there exists wy I with
||w,l12 z 2 satisfying
1 (ur, wyyl S 2 (ug, wg) for all i' E y.
for all i' $ y.
Given the bounded precision of the model, we are not free to represent the vectors wy exactly. Under p- bit precision for p sufficiently large, we there exists a vector of p-bit floating point numbers Wy E Imm for every wy with ||w;,]ly
2 satisfying ||w,- Wyll2 S T As immediate consequence, Ku,, Wy) (uy, wyy) S + for all i' and y (by Cauchy- SchwarySchwarz). The remainder of the proof demonstrates that the necessary properties of the argument hold even with this approximation.
We now describe how to structure the neural network. We define an MLP Φ Rd + Rm as ((x;) = Φ(2;; () (zg oityy uz), which works simply by using a look-up table on the values of and Wy: from keys i and y; respectively. Then, we define Q, K, V as sparse moolean-valued matrices that simply copy their respective elements from (XX).
We analyze the output of the softmax. If i' E yi, then
expla (14, Wpy)
Emen. expla (u; ww' - Ev'gy. expla (Ui, Wpn))
expla - 4
e
exp
g
gexpla + ( + exp(( + qea + Nea/2
1
Nea/2)
(1 5) 2
+t) (1 (1-
> ( 1 - 2)
q
qea
q
An analogous argument shows that
sofl)na(6(()QK 3. < 1
{1 )
Likewise, if & yes then
exp( 2 + 3 q exx((a 4 S exp (-r + c
softmax(((x))0) ((X)"),
2 2N
We thus conclude that that we meet the desired degree of approximation for such m:
IS(X), g =
Σ x
Peys
Σ
+
<
+ (N - g)
E
S
2g
2N
16

---

B.1.1
Restricted isometry and orthogonality property
The proof relies on the restricted isometry and orthogonality property from the compressed sensing literature. For v E RN, let supp(u) = {i E [N] is + 0}.
Definition 5, We say matrix U E I satisfies the (g. -e-stricct isometry and orthogonality property if
|1 [(1 ((1-6)]1 8)11012 (1 +1++0) + and KU,, Un') S 8||0||2||'111
for all vectors v, o' E R with supp(p)) S q: suup((')) S 2g, and supp(u) supp(w') =
The first result shows the existence of a sign-valued matrix U that satisfies the desired distance- preserving property.
Lemma 12 (Consequence of Theorem 2.3 of Mendelson al. 2007 and Lemma 1.2 of Candes and
Tao 2005)). ). There an absolute constant C > such that the following holds. Fix 5 E (0. 10.1/2) and q E N. Let U denote random N matrix of independent Rademacher random variables scaled by 1/mm If m 2 C(q log /8², then with positive probability, U satisfies the (q. 6) restrricted isometry and orthogonality property.
Sparse subsets of the columns of such a can then be linearly separated from all other columns.
Lemma 13 (Consequence of Lemma 2.2 in Candes and Tao (005)), D. Fix (0, 1/2) and q N. Let matrix U = [w1:-.. uN] E RmxN satisfy the (q,0) --restricced isometry and orthogonality property. For every vector v {0, N with supp(r) S 9. there exists w E Rm satisfying
||w||2 S /T/(1 26), (wi, w)
if
(u,, w))l 5 6/(1 -26)
if = O.
B.2 Proof of Theorem 3
Theorem 3 (Infinite-rrecision). For fixed N, m 2 (Q)) and >> 0, there exists some f E A'd that c-approximates gSA.
The proof relies on the properties of neighborly polytopes, which we define.
Definition (Ziegler 2006)). A polytope P is q-neighborly if every subset of o' S q vertices forms a (n' - 1)-ffce.
We give g-neighborly polytope below that we use for the construction. For vectors ..,...; UN vx) E Ogt;; [0, 11 Σ, a; 1) denote their convex hull. Fact 14 (Theorem of Gale 1963)). For E R. let ((t) = (f...., ...,,t'' E Rm''. Then. all distinct ty E IR, the cyclic polytope Conv(O(t)),..... )) is m² meinihhhorrl.
Rm let Conv(u,....,
The proof of Theorem is immediate from the aforementioned fact and the following lemma.
Lemma 15. Suppose there exists u1,..., uN E Trmm such that Conv (ui......... uN) q-neighborly. Then, for any > 0, there exists some f E A'am, with fixed key vectors of o(X) (u.,..., ux) that e-approximates gSA.
Proof. The construction employs similar look-up table MLP to the one used in the proof of Theorem We let the key and value embeddings be
oi ((X) ((u1, 1),..., (uN, 1)) E R xx('m1)) and di (X)V = (zI,...,EN) E I Nxd.
To set the query vectors, observe that for any face F of a polytope P. there exists hyperplane Hr such that F c Hp and P lies entirely on one side of HF. Thus, for every y E (INI), there exists w/, E Trmm and by E IR such that
[=
if E y. < otherwise.
I u4 + by
17

---

For > 0, let (( = anly = a(w' by).
We construct the MLP to satisfy ((x;) = (zy: wyy u4; 1) E IRm for m = 2m' + 2 and set parameter weights accordingly. Following the softmax analysis of Theorem 3 sufficiently large choice of ensures that [ [If(X); gSA(X))ll2 S.
B.3 Proof of Theorem 4
Theorem 4, For any sufficiently large 4, any N 2q + 1, and any d' 2 there exists universal constant e such that if mp S cq, then no f E Td.m.d' exists that
24 a-approximates qSA.
Proof. We first embed every instance of DISJ with q into instance of qSA and prove that they correspond. We assume the existence of the transformer f T dd.m.d'.p that 2q qSA and implies the existence of an (mmp)-bit communication protocol that computes DISJ. An application of Fact concludes the proof.
J. -aappoxximates
Consider an instance of DISJ with a {0, 139 and E {0, 1) known by Alice and Bob respectively. (2i +
We design an instance X = (2: ()(e(]] of qSA. For each j E [24]. let U2++1 i [4]]. Additionally, let
C1
if j is odd and b(z21)/ otherwise.
2
-
All other inputs are set arbitrarily. Then,
(SA(X) 22 22
K E [2gl EE V2g+1, j is odd, and a(j-1)/2 = 11/
1 [ E [2q] j 1 and (j is even or d(j11/22 0)} e1
Hi [g] a&b, = H Hi [q] a,b; = 03 e1.
Hence, (SA(X)2044 e, if and only if DISJ (a, b) 0.
It remains to show that this implies the existence of efficient communication protocol that computes
DISJ(a, b). By the existence of f. there exist Q, K, V Fd T and v 1 - Rd such that
Σ
N i= exp [22 1 K)))) ((ra)
(X))2+1 10
N E exp (Q( K
The protocol as follows:
1. From a, Alice determines y2g+1 and then computes ((124+1) R", which she sends Bob. This transmission uses O(mp) bits.
2. Bob determines 21...., B2g from b. Using those and the information from Alice, he computes (2)+ He returns 1 if and only if f(X)2 -1+
The protocol computes DISJ(a, b) because f is 24 approximmaiion of 9SA Because any such protocol requires sharing 2(g) bits of information, conclude that mp eq for some
B.4 Optimality Theorem under restricted architectures
While the near-optimality of the bounded- bounded-precision self attention construction in Theorem assured by the communication complexity argument Theorem 4 it is not immediately apparent whether Theorem 3 similarly optimal among infinite-precision self-attention models. Theorem ( proves that this indeed the case for restricted family of architectures that resembles cress-attention rather than self- self-attention.
18

---

Theorem 16. For input Fı... 2i.....2. EN satisfying 2; = (20)): suppose o(x,)'Q - w(y i), ( =(i), and ((x,)'V 2. Then, for any 9 < N and m I q(1 log q) for some universal C, there do exist w R [N] - Rn and [N] + R such that the resulting self-attention unit by approxximate qSA.
The architectural assumptions of this statement are strong. For each element 2; (2zj Mis i), its value embedding must reproduce its target 2;; its key embedding depends exclusively on the index i; and its query embedding only on the indices yi and i. Indeed this attention unit more closely resembles cross-attention rather than self-attention, in which the problem formulated as two sequences ((=1,
N)) and (yi; 1)...).... (yN; N) that are passed to the key and value inputs and the query inputs respectively. We leave open the problem of generalizing this result to include infinite-precision gross-attention or self-attention architectures, but we note that the constructions in Theorems 3 can be implemented under such architectural assumptions.
The proof relies on geometric argument about how the convex hull of fixed key embeddings U (u(1)..... u(N)) lacks neighborliness and hence cannot separate every size-q subsets of values embeddings 2,, ,,,...;2. ZN from the other values.
Proof. It suffices to show that for any fixed key embedding U, there exists y and setting of . zN such that
(softma((((X)U)))
2x'
29
where wXX) = (w(y1, ( w(UN, N)) E RNxm and U (u(1), ... u(N)) E RNxm
By Fact 17 for some y1 E (! there
and T R satisfying w(y1, 1) 2 if
and only if i' E y1- Hence, for any fixed w, there exists i E y1 and i2 [N] y1 such that w(V, u;; > w(yn, 1)'u,, ui, Given the value embeddings 2,, = E1, 2i, 62 and eg for all
i 8,), we have
1 (softmax (softmax(wx (x))())Z)
Σ 25
2
(iltmax(w(X)U"))
-) + (softmax(w((X)U)))
- 2) 2
max
(ootmax((((X)UT))
1
4g
Fact 17. mm < q log Cq), then the columns of any U (UI...., uN) Nxm' can be par- titioned into sets U1 and U2 with [U1] = q that are not linearly separable. Hence, Conv(u UN) is not n-neighborly.
Proof. By the Sauer-Shelal Lemma [Sauer 1972, Shelah 1972, Vapnik and Chervonenkis 1968 and the fact that the VC dimension of m² dimensional linear thresholds is m' + 1, the maximum number of partitions of the columns of U that can be linearly separated at most
m
M S C'NN'++ SC''N''t&CC' <
No N
)
(Cq)a S
for sufficiently large choice of C' given universal constant C'. If the fact were to be false, then at least (N) ( such partitions must exist, which contradicts the above bound.
19

---

C Supplementary results for Section
C.1 Proof of Theorem
Theorem 6. For any input size N, input range M = NNO)), and fixed-precision bit complexity p Ollog M), there exists transformer architecture E T with single self-attention unit with embedding dimension m = 3 such that for all X [M] f()) = Match2(X),
Proof. As discussed in Section 2.1 allow single blank token to be appended the end of the sequence X and assume the existence of positional encoding. That is, we consider input X' = (21...., NN, x') with 2i,0 = i and x' = Ô to be the input to the target attention model. We define input MLP Φ : + R and parameterizations Q, K, V R33x3 such that
Q'((x,)= = c =(cos
2
2TT
sin
M
M
2
2TT
(';( cos
sin
0
M
M
V'o(;;) I, QTx(2') 0. K' K')(r') es. and V VT)(=")
Ô. By elementary trigonometric
identities, the following is true about the corresponding inner products:
[T, + xz))
= ccos
M
(QT ((²²) od.
As a result, (Q" ((xx)))TKolla I c(1 Mr). (Here, the (log M -bit fxxedprrecsion arithmetic is suffi- cient to numerically distinguish the two cases.) For each E [N] let
= cd and only if a; + Iÿ = @mod M). Otherwise,
3: == Ki E [N] + 2j = 0 (mod M)H represent the total number of matches the input belongs to. If we take M² 1og(6N), then
0,
if if + x3 * 0 (mod M) and i, E [N];
6N
if I = 0 (mod M) and i,j [N]; ifi [N].j N +1
3,
GN
3,41
6N
We conclude that for any i E [N].
< 5
Aj s.l. 4; + = (mod M) if if s.t. x4 + = (mod M),
(softmax(6(X)Q2) (()))((((X))))())))))
where S is partial ordering with S o' if e; S of for all i. Since the latter case holds only when
3 2 1. the final step of the proof is design an output MLP & such that (2)) = if > and
(2) = 0 if 2 < e which can be crafted using two ReLU gates.
C.2 Proof of Theorem
Theorem 7. There is universal constant >> O such that for sufficiently large N, and any M > N + if mpH cN/ log log N, then there is no J E 7.m.1.p satisfying S(X) = Match3(X) for all
X [M
Proof. The proof relies on reduction to Fact 5 that embeds inputs to the set-disjointness problem of cardinality _ into subset of instances passed to Match3. For the sake of simplicity, assume in the construction that N is odd; if were not, we could replace it with N - 1 and set the final element such that it never belongs
triple.
We consider the following family of inputs to Match3:
(0)
if i = 1, if E {2, {....., N+11
24
{1,i}
} if ( N43 N).
(3)
{1, (M
(=1)
20

---

Note that Match3(X), = if and only if there exists i E {2..... N+11 such that = i and "it N-1 (M i). Given imput (a, b) {0, 1)"h [0,1]" DISJ, fet 2141 if and only = 0, and let + N41 if and only if b; O. Then, Match3(X) (X)1 iff DISJ b) = 1.
Suppose f(X) = ( for all X E [M] for some f E TT.m, We show that f simulates an (mmpH)- )-bit communication protocol for testing DISJ. By definition of the standard self-attention unit with multi-layer perceptrons, note that f(X)1 + fx(o(X))) for Φ R R 3b R + {0,1}. and
(xX) = EiS ΣN (xp(Q((T)))))
for Qh, Kn, Vn Rmmxm.
we assume that this construction exists and known explicitly by both Alice and Bob, we design communication protocol for Alice and Bob to solve DISJJ by sharing O(mpH) bits with one another. Let Alice possess E {0, 1 and Bob b E {0, 1 with N-1
1. Alice and Bob compute (I2,.... I xx1 and (x (y. 1 .N) from and b respectively,
2. Alice computes an (pp log log NN --b approximation of the logarithm of the first half of the softmax normalization term for each attention head and sends the result Bob. That is, she sends Bob
Inaa log
Σ cxp(Qu(o(ar))
for each h E [M]. This requires transmitting O(pl log log N) bits.
3. Bob finishes the computation of normalization terms
Ln log exp(LLn.) +
exp(@n(o(at))'
for each h and sends the result back to Alice (up to Opp log N of precision). This again requires transmitting OppH log log N) bits.
4. Alice computes the partial convex combination of the first attention matrix
value vectors stipulated by the N+1
2
Sh.a
1=1
E R
exp(Ln)
for each h and sends the partial combinations to Bob. OmmpH log log N) bits (using the same precision as above).
This requires transmitting
5. Bob finishes the computation of the convex combinations
ΣN N+a ((t(:
(x( Sh.a
I....
cxp(L,.) Bob concludes the protocol by computing and outputting f(X),. using his knowledge of each Sú. (X) and of vb.
By the equivalences previously established, Bob returns if and only if DISJ b) = Because the protocol requires Ompll log log .) bits of communication, we can only avoid contradicting Fact mpHl Z Q/n/ / log log N) = ((N/ log log N).
Remark
The domain restrictions to Match3 stipulated in Equation B make the Match3 problem substantially easier to solve than the full-domain case. Indeed, under the domain restrictions,
Match3(X),
max
Match2(X),
iE
N+1
21

---

which is computable by a two-layer single-headed transformer network with constant embedding dimension. The first layer computes each MXtch2(X); with the construction in the proof of Theorem and the second computes the maximum of the previous outputs by using those outputs as key vectors.
While Informal Conjecture 7 suggests that two layers are insufficient to compute the full-domain version of Match3, this restricted variant introduces concise depth separation (see Eldan and Shamir 2016], Telgarsky (016)), Daniely (2017)) between one- and two-layer transformer models.
C.3 Higher-order tensor attention
We introduce novel category of higher-order tensor-based transformer models in order show that problems like Match3 that are hard to compute with standard transformer models can be made solvable. An s-order transformer is designed efficiently compute dense s-wise interactions among input elements in an analogous manner to how standard transformers compute pairwise interactions. (We think of a standard transformer as recond-order, Before defining the new type of attention, we introduce notation to express the needed tensor products.
For vectors ua E R. and 22 TR,2, let v² v2 E RNN,N denote their Kronecker product by (v' ( v²) 11) = 11 "2" The column-wise Kronecker product of matrices A E RRN, Xm and A
E R
N2 Xm is
A * 1
[A]
A * [A]]--. ... 1 = [A] & A7 ... A A E N.NAm.
The following generalizes the definition of self-attention.
Definition 7. For order $ 2 2, input dimension d, output dimension d', embedding dimension m, bit complexity p. and matrices Q, K' KK...., K*=1 E Raxm and V ..... V E Baxd' (encoded with
Vi....,
p-bit fxee-point numbers), s-order self-atlention unit is funetion fQ.K. RNxx N with
(x) = softmax XQ (XK*) (XK* (XV*) *...* **..**************......> (XV*
ERmxNN-L
CRNA-ixa!
A The input to the row-wise softmax is an N N matrix. Let d.m.d p denote the set containing all such attention units.
Note that A Ad. .p- Because s-order self-attention units have the same domain and codomain as standard self-attention, multiple units can be analogous combined to construct multi- headed attention units and full transformer models. We define A .p and T.D H,
d,m,a', .p accordingly.
The purpose of the s-order transformer model as a theoretical construct is to posit how strictly generalizing the architecture in order to permit higher order outer products transfers the expressive powers of standard transformer architectures to more sophisticated interactions among elements of the input sequence X. The model is not defined to be immediately practical, due to its steep computational cost of evaluation.
However, the trade-offs involved in using such architectures resemble those already made by using transformer models instead of fully-connected networks. Transformers are already computationally wasteful relative to the number of the parameters, and these models likely succeed only because extremely efficient factorized parameterization exist. Likewise, third-order transformers could indeed be practical if even more factorization proves useful, since the computational costs may prove mild the embedding dimension m. number of heads H, and depth D necessary to succeed on task exceed the sequence length N for standard second-order transformers.
C.4 Efficient representation of Match3 with third-order self-attention
Theorem 18 (Match3 construction with third-order self-attention), For any sequence length N, input range M = NOO), and fixed-precision bit complexity = Ollog M). there exists a third-order transformer architecture f E Ti with a single self-attention unit with embedding dimension 5 such that for all X E |M]. f(X)= Match3(X).
22

---

Proof of Theorem 18 The proof is almost identical to that of Theorem 6 except that we instead use different key and query transforms to express different trigonometric function:
2
2
2
2
QΦ(x+)=
cos
COS
sin
sin
1
M
M
M
M
2
Z
2
2
K² ((a())))
cos
sin
COS
sin
.
M
M
M
M
2
2
2
2
(x+))) =
cos
sin
sin
cos
.M
M
M
M
Together, these ensure that the resulting tensor products reduce trigonometric expression that is maximized when zi + zij + Jt = 0 (mod M). That is,
2 (m; + 2zi + x422
(6(X)Q((((X))) (6(X) )4 = coos
()
M
We similarly let V (z;; = ((;)); = and V' = v² ő. The remaining choice of c
and the output MLP, and the analysis of the softmax proceeds identically to the previous proof. D
C.5 Heuristic argument for Informal Conjecture 1
Conjecture 19 (Formal version of Informal Conjecture D. For sufficiently large N and any 2 1,
for all M 2 N + and mpHD D S N20), there is no f T satisfying f(X) = Match3(X) for all X E [M]N.
We believe that the conjecture holds due to a heuristic information-theoreee argument. Define the distribution D over inputs X R that will be used to show that the model cannot compute Match3 for M = N with high probability. We draw X from D as follows:
(E,) With probability 1,2 draw each x; iid from ([M).
(E2) With probability 1. draw n1 f2, Js iid from Unif( (())). For all i a js. draw each x; iid from Un) Let Xja- -Xi Xjz (mod M).
Note that under event E,, a three matching elements exist with probability at most y and
Pr Match3(X) = Ō Eg
N
Under event Ez, a triple of matching elements always planted, so Match3(X) + Ô. would suffice to prove that- suntttuulsss transformer is sufficiently large- it is impossible to determine whether Match3(X) with probability at least 0.9.
Under D. any subset of (x....., xN3 consists of iid integers drawn uniformly from [M], unless all of xa; Xj, appear in the subset. Consider a transformer architecture with p-bit precision, m- dimensional embeddings, H heads per layer, and D layers. We argue informally that single-element output of a self-attention unit can take into account information about mp more inputs xI.... Xy than that had in the previous layer. By induction, after D layers of H-headed self-attention with interleaved MIPs, each element is a function of at most mpH D) inputs. Until an element exists that function of least two of the three of X,, X32 Xaa we assume that the elements "known" by each output are chosen independently of the indices J2. js. (Given two elements of the triple, the third element can be identified with a single self-attention unit.) Hence, we argue that suffices to show that the probability any two elements of the triple f1, J1, ja occurring within any of the N sets of mpHD D inputs vanishingly small for sufficiently large transformer parameters. The probability of single collection having any of two of the three inputs is at most
3 m
(empHD 2
<3
N
Thus, the probability that any collection has all three inputs is no more than 3)3p If m O(VNN, then the randomly chosen triple will not jointly appear the outcome of single
23

---

element of a self-attention unit with probability at least 0.9, and the transformer will be unexpected to successfully distinguish between the two cases.
Should the conjecture hold, it would represented a tight lower bound on the size of the smallest standard transformer architecture necessary compute Match3.
Theorem 20 (Tightness of Conjecture 19]. For any sequence length N. if the imput range satisfies
M NO(1) and the transformer size parameters satisfy p Z log(M), H 1, 2 4, and
mD 2 CN2 for some universal constant C, then there exists a transformer architecture f E T
such that f(x) Match3(X).
Proof. We construct an architecture that collects a group of candidate pairs in each layer of single- headed self-attention and verifies whether there exists a triple incorporating each pair that satisfies the summation property. Then, all candidate triples are disposed of, and the subsequent layer collects new family of candidates.
To do so, we first attention. We let P ((xT) represent collection of all pairs of indices and partition it into D subsets Pl...., PD. each containing é distinct pairs. (Since |P| N(N+1) any D satisfying the theorem's 's preconditions is sufficiently large for this to be a proper partition.) Our construction ensures that there exist 2; Iz + Jz = O (mod M) for (j1.J2) verify its existence and mark z; as belonging the match. Throughout the network, we maintain that the first two dimensions of any embedding of the ith element correspond to z; E [M] and bit indicating whether a match has been found yet containing Zic.
- 12 represent the total number of pairs shared in each layer of
Pk. then the kth layer of self attention will
Consider the first layer of self-attention, and let P1 = ((h11.1)..... (e)). We set the input MLP $1 : 12 + _k" and respective matrices Q² K [R such that
fei ifieP
Q' cei and K (()((x))
{o
otherwise,
for sufficiently large c. We additionally let
i i Pı (2/ + 1): (zy 0; 2102-11
(2l + 1). (z;; 0: 0)
V (xx))
in = j.-
(2l + 1) (xz; 0; 22
By making use of residual connection, we ensure that the ith outcome of the self-attention is (ax, 0, T......, Fi,y ). We encode an MLP to compute
(z,, 0,, Ty...... Tr, 25) 22,, 1 {3x [6] s.t. Ia + x4, + IJ. = (mod M) ; :).
We repeat this construction D times, with the only modifications being the replacement of P1 and the fact that the second dimension of the embedding remains 1 after being set to that value. After D layers, the final MLP outputs the value of the second dimension, which will be I if and only if the respective x; belongs to a three-way match.
C.6 Sharper separations for embedded subgraph detection problems
In pursuit of proving separations analogous to the one between Theorem 18 and Conjecture 19 we draw techniques for proving lower bounds for graph problems in the CONGEST model of distributed computation with restricted bandwidth [Peleg 2000
"tt a high level, the CONGEST model features N players that communicate in synchronous rounds over network (an undirected graph with [N] as its vertices) to solve computational problem [Peleg] [2000]. In each round, each player can send message each of its neighbors. The computation that each player does with the messages received from its neighbors unrestricted; the primary resources considered CONGEST is the number of rounds of communication and the message sizes. Although CONGEST is often studied for solving computational problems on input graphs with vertices [N]. the input graph need not be the same as the communication network.
24

---

The problems we consider take, as imput, the adjaceney matrix X E {0, 10,1 of an N-vertex graph G (V.E) with V = [MV, so 2i,j 1 {(i,]) E E}. We may regard each row of X as high- dimensional (d = N) embedding of the i-th vertex containing information about which (outgoing) edges are incident to the i-th vertex. We consider the following problems:
DirectedCycle3(X) - (1 (3/1, E [N] s.t. Li,51 n1 EEN) Cycle5(X) = (1 with dom (X x=
E [N] 8.1. Fiih Jo is Fast = KENN
The former treats X as a directed graph (where X need not be symmetric) and asks whether each input belongs to a directed 3-cycle. The latter insists that X be an undirected graph by enforcing symmetry and determines membership in (undirected) 5-cycles.
However, solving these problems with any transformer model of constant order trivially requires having the product of the precision p. embedding dimension m, heads per layer H, and depth D grow polynomially with .N, since each attention unit is limited considering at most pm bits of information from each input. Such lower bound is not interesting for dense graphs, where every vertex may have (2) incident edges; the bottleneck is not due to any feature of standard attention units (and would persist with higher-order attention).
To circumvent this issue, we consider an augmented self-attention unit, which permits each element of the self-attention tensor to depend on both its respective inner product and on the presence of edges among corresponding inputs.
Definition 8. For order 2 2, input dimension d, output dimension d', embedding dimension bit complexity p, matrices Q, K -K...... ...... K R and V1 V!,..., ,..., V Raxdd (encoded with p-bit fixed-point numbers), and cell-wise attention tensor function {0, 1)=(=-1) x R R. s-order graph self-atiention unit is function fQ.K.v RRd Nxd with
(X. = soflmax(xxXX XQ((XX)) * *...* (XK* (XK*-)))))((XX))) (())( ..... (XV-*((XVVX))))
For attention tensor A E RN we abuse notation by writing xxX, A) as short-hand for the particular cell-wise application of a fixed function, incorporating information about all relevant edges:
r6( X, A)i = 1i( Fig 5 ii, A Aiy.......
T.D. denote all such attention units and all such transformers respectively. Let d'm.d'.p and T d.
Os
Now, we provide four results that exhibit separations between orders of graph self-attention. Theorem 21 (Hardness of representing Cycle5 with standard graph transformer). For sufficiently large N, any f E T satisfying f(X) = Cycle5 X) for all X E (0, NNNN with X XT requires mpHD D = /(N/ DoN//lo" N).
Theorem 22 (Efficient construction of Cycle5 with fffth-orderge graph transformer). For sequence length N and botcommpyyyty p Ollog N), there exists a fourth- order graph transformer architecture f T 1.151 with a single graph self-attention unit such that all X E [0,1) with X = XT, N.I.1.p
f(X)= = (X).
Theorem 23 (Hardness of representing DirectedCycle3 with standard graph transformer). For sufficiently large N, any f E / satisfying f(X) = DirectedCycle3(() for all X e
(0, 10,1J8 NNN requires mpHD (NN log N).
Theorem 24 (Efficient construction of DirectedCycle3 with fourth-order graph transformer). For sequence length N and bit-complexity p = Olog N), there exists a third-order graph transformer architecture f E N.1.1.p
1 with a single graph self-attention unit such that for all X E (001)Nxx NxN f(X) = DirectedCyylee((X)
The proofs of Theorems 22 and 24 are immediate from the construction. Because each cell of the self-attention tensor has explicit access the the existence of all relevant edges, can be configured to ensure that cell's value is large if and only if the requisite edges for the desired structure all exist. Taking sofumax with blank element (like in Theorem 6) ensures that the outcome of the
25

---

Pap
82
Pyp
P22
Pst
Figure 4: The CONGEST graph G.V visualized for N = 6 with root nodes { {ui he(N] in blue, leaf nodes (ijeee in green, and the nodes V1 of the binary tree B3 shaded red and edges E₁ colored red.
self-attention unit for a given element distinguishes between whether or not it belongs to S-cycle or a directed 3-cycle. The output MLP ensure that the proper output is returned.
We prove Theorems 21 and 23 introducing a particular CONGEST communication graph that can be d,m,d',p (and hence, also any model in T ,t) in OmmH D log N) rounds of communication. Then, we show for each problem that we can encode each instance of the disjointness communication problem as an instance of Cycle5 (or DyrectedCycle3) and derive contradiction from the communication graph.
used to simulate any model in T,
C.6.1 A CONGEST communication graph that generalizes standard graph transformer computation
The key principle of analysis is that the predominant limitation of transformer model is in its communication bandwidth and not its computational abilities. We model transformers as having element-wise multi-layer perceptron units with unbounded computational ability (but bounded precision inputs and outputs) and self-attention units, which compute linear combinations of inputs in carefully regimented way that limits the ability individual elements share information with one another. Here, we introduce a specific CONGEST graph for each sequence length N and show that every transformer has communication protocol that simulates its computation in this graph.
For fixed N, we design an undirected CONGEST graph G (VN EN) with O(N2) nodes, each having degree at most 3. (Note that this graph is not the same the graph provided input X to a transformer; this graph is consistent across all transformers taking input of sequence size N.) Let ui,..., uN be nodes in V corresponding each input. For every pair i, [N), let va.i be a node as well. For each E [N], let B, (V, Ex) be a balanced binary trees having root us and leaves 14 1.l....... UU U1 UN, Hence, each B, has O(N) vertices of degree 3 and is of depth Oloog N). Let V Vi U U.... VN and EN En U... U EN. Noting that E E1,.... EN are disjoint and that Vi..., Vy are disjoint, except for leaves U..j, we ascertain that G contains O(N2) vertices of degree at most and has diameter O(log N). We visualize the graph G with highlighted tree B, in Figure 4
For any transformer f E T.ama.' and any X E Nx with p-bit fixed-precision numbers, there exists a CONGEST communication protocol on the graph G that shares bits of information between adjacent vertices per round satisfying the following characteristics:
Lemma 25.
26

---

Before any communication begins, each node is provided with a; and each node vi.j is provided with Fijj and Zj
After T O + logNoo N)) rounds of communication, each node u, outputs f(X);-
Proof. It suffices to give a protocol that computes the outcome of a single-headed unit of graph self-attention with parameters Q, K, V IRmx and k 1]2 I R and transmits its ith output back to in O(m log N) rounds of p-bit communication. The remainder of the argument involves computing the outcomes of all clement-wise MLPs within respective vertices #1..... uN (since we assume each node to have unbounded computational power in the CONGEST model) and to repeat variants of the protocol HD times for every individual sellf-attention unit. Because the protocol is designed for a particular transformer architecture f, we can assume that every node in the CONGEST graph has knows every parameter of f.
We give the protocol in stages. We assume inductively that every input to f. 91,..., UN E ER", is known by its respective vertex "
1. Every vertex U, computes QTy: E Ih" and propagates it to every vertex Ui,1,-..: Ui,N- This can be done in Omm + log N) rounds by transferring one p-bit fxed-precistee number per round from element of the binary tree B; each of its children per round. Because the respective edges Et...., EN are disjoint, this operation can be carried out in parallel.
2. Each u, computes KJg Ye. Vu E R and propages them to U1,6...., UN in O(m - log rounds.
3. Each Us., using their knowledge s. and zy.s computes anj == exp(x(E2,,, QKKT This takes zero rounds.
4. Each computes Σラ= oij by propagating each oig in Vag up B, to us iteratively summing terms passed up. This takes Ollog N) rounds.
5. Similarly, computes Σ/ o1, VTy in O(m log rounds. Then, it computes
Σラ on V V
Σ/ ozj
which is the target output of the self-attention unit.
Because all steps are achievable in parallel with O(m + log N) rounds, the claim follows.
C.6.2 Reduction from set disjointness
Before proving Theorems 21 and 23 by embedding an instance of transformer model into an instance of each subgraph identification problem, we first introduce a partition of the vertices // of the CONGEST graph into those possessed by Alice and Bob for use in a two-party communication protocol. We call those two sets V.N and V.N.
Note that the previous section made no assumptions about the organization of edges in the binary tree. We thus add an additional condition: that each binary tree B; can be oriented to respect the left-to-right ordering 14 U1.s..... Ug UN, Let u, E V.N if and only if S Y/2 and Vi, V.N N. We label are remaining nodes in B, by labeling a parent node up as a and only if min(i.j) S 2- function of its child nodes wy and w, using the following rules:
(a) If we, V.N. then let up E V.N
(b) If ffg wy VgN. then let wp V.N.
(c) Otherwise, let wp V.N if and only if root un E V.N.
This partition, which we visualize in Figure 5 bounds the number of bits Alice and Bob can exchange by simulating protocol on CONGEST graph G.N.
27

---

11
62
O
Pap
PyP
P56P55
P22
Figure 5: The CONGEST graph G. with vertices partitioned into sets V.N (violet) and Vg" (orange) for The six edges cut by the partition are colored red.
Lemma 26. Suppose Alice and Bob simulate an R-round p-bit protocol on CONGEST communication graph GN where Alice has access to all vertices V.N and Bob V,N. No other communication is permitted besides sharing bits as permitted by the CONGEST protocol between neighboring vertices. Then, Alice and Bob exchange at most O(pRN log N) bits.
Proof. It suffices show that the partition V.N VeN induces ensures that each can send no more than Op log N) bits per round.
of size most O log N); this
Per the rules defined above, an edge in (wps wy) and (Wp, w,,) is cut if and only if they described by case (c). Within each tree B; under the orientation described above, an inductive argument shows that in every layer, all elements in V.N are to the left of all elements in V,N. Thus, there exists at most one parent of that layer that belongs to case (c), and thus, no more than one cut edge per layer.
Because each tree has O(log N) layers and because there are N trees, the partition cuts at most O(N log N) edges.
remains to embed an instance of DISJ in V. VEN for each problem such that its output corresponds identically with that of DISJ.
Proof of Theorem 27 Assume for the sake of simplicity that N is divisible by 5. Let a, b E {0, 1}" for N² be an input to DISJ, and let Alice and Bob possess and respectively. We index those vectors as a = (a1,1, 01,2, ANy5,NN5 1155./55-1- 4N/5,N/6) and = (bI,1...., bN/5.N7/8 for ease of analysis. We design imput matrix X E {0, NxN as follows:
If E (0, N1 and j E ( 2N then Fi.j = Dj. = a: Bi.j-N/5- N/5-
If e
( 1N and j E (2 4N then Ti,j = Fj.i = 85 N/55
If E
4N and j E (4N NJ. then æijj = Fg,i = =b; =bj-NN/5,
If e
IN N and j E (0, 5
Ni then æijj = =j = -8.444155
Otherwise, Fzg 0.
28

---

This ensures that X has a 5-cycle if and only there exist i,j E (0, N: such that at,y = 1 In addition, note that under the protocol in Lemma [25 Alice's 's and Bob's inputs a and b known exclusively by nodes belonging to V.V and V/"" respectively.
Consider any transformer architecture f E TGNN N.m.Ip that computes Cycle5. By Lemma 25 there
exists a protocol on the CONGEST graph G:N that computes Cycle5 after ( (mm+ monn-llog N)) rounds of communication of p-bits each. If Alice and Bob simulate this protocol, and output if and only if at least one of their outputs indicates the existence a Cycle5, then they successfully decide DISJ. By Lemma 26] this communication algorithm solves DISJ after exchanging O(mpH DN log" N) bits of communication. However, Fact implies that no communication algorithm can do so without exchanging (2()) = (2(N2) bits, which concludes the proof.
Proof of Theorem 23 The proof is identical to its predecessor, but uses different embedding of an instance a, {0, 13" to DISJ. Let N2 Then:
i E (0, ] and j E ( ] then Fig 04.j-N12
If E
( 3N and j ($ M1, then 24, = -b- DJj33//4i-N0 N/2-
If E 3N N] and j E (0, N1. then 21,5 = di.+3N/44
Otherwise, Fi = 0.
This construction ensures that directed 3-cycle exists if and only if a corresponding pair of elements in and are both 1.
D Experiment details
This section describes the experimental setup behind Figure 2 and provides further experiments suggesting an implicit bias of transformers for gSA, in particular when compared with MLPs and RNNs.
Experimental setup. Experiments used synthetic data, generated for qSA with n 1000 training and testing examples, a sequence length N = 20, 3, with the individual inputs described in more detail as follows.
The positional encoding of element i is random vector sampled uniformly from the sphere in d with dg == [1 In [,) quantity which agrees with the theory but was not tuned.
A sequence element then consists of the data portion z E Rdd where di = 4, also sampled from the unit sphere, then the positional encoding of this sequence element, and then g further positional encodings identifying elements to average to produce the output; this differs from (and is more tractable than) the presentation in Section 3 where the positional encoding is provided as an integer and the MLP layer input to our attention layers is expected to choose a sufficient positional encoding.
As such, the total dimension of a sequence element d1 + (g + 1)do 32. The architectures are detailed as follows.
The attention is identical to the description in the paper body, with the additional detail of the width and embedding dimension m being fixed to 100.
Figure also contains MLP, which first flattens the input, then has single hidden ReLU layer of width 256, before a final linear layer and an output reshaping to match the desired output sequence shapes.
Figure also contains an LSTM, which is a standard pytorch LSTM with 2 layers and hidden state size 800, which 200 times larger than the target output dimension
WWe consider 5-cycles rather than 4-cycles hecause spurious 4-cycle could exist among edges { i (0, 1 j E ( , 13.
29

---

Itraiing)
10
Figure 6: Test and train error curves of fitting various architectures to gSA, where the horizontal axis denotes thousands of training iterations, and the vertical axis denotes the regression objective; see Section D for further details.
Experiments fit the regression loss using Adam and minibatch size of 32, with default precision. and take a few minutes to run on an NVIDIA TITAN XP, and would be much faster on standard modern hardware.
Further discussion of Figure 2 and Figure In Figure 2 and Figure 7 we plot (post-softmax) alignment matrices after T (0, 1000, 40000) iterations of Adam. The alignment matrices in Figure 2 are taken from the training example whose loss is the median loss across all examples. Figure is similar, but additionally shows the examples of minimal and maximal loss.
Figure 6 plots training and testing error curves for the same attention architecture in Figure 2 but with further MLP and LSTM architectures described above. but also an MLP trained on flattened (vectorized) error bars reflect separate training runs from random initialization. few variations of these architectures were attempted, however curves did not qualitatively change, and particular, only the attention layer achieves good generalization across all attempts.
Further discussion of Figure 6
30

---

(a) Min loss, T
(b) Min loss, T 1000.
(c) Min loss, T 40000.
(d) Median loss, T
Median loss, T 1000.
(f) Median loss, T' 40000.
BB
(g) Max loss, 0.
(h) Max loss, 1000.
(i) Max loss, T 40000.
Figure 7: Alignment plots as in Figure 2 but using examples with minimum, median, and maximum loss, whereas Figure 2 only uses the example with median loss.
31


Reviews:
[{"review_id": "5tpZuUYrdN", "reviewer": "Reviewer_bmhz", "summary": "The authors study the representational power of transformers. They quantify how the transformers are superior to other neural network architectures, as well as the limitation of the transformer architecture. They focus on the $q$-sparse averaging (qSA) task which amounts to  averaging $d$-dimensional input vectors over subsets of size $q$ over a set of size $N$. They show by an explicit construction a unit of self-attention with $m \\geq q$ dimensional embedding can approximate qSA. Using tools from communication complexity between two parties, they show fully connected networks require $\\Omega(Nd)$ hidden layers, and recurrent neural networks require $\\Omega(N)$ bits of information. They further show that standard transformers can approximate functions that intrinsically depends on input pairs, while failing to approximate functions that depends on triplets instead. Finally, they propose a variant of transformers that can approximate the triplet-functions. ", "questions": "- Given a fixed constant precision $p$ what is the bottleneck in creating the transformers that can approximate q-SA? What if $z_i$s are themselves restricted to some $O(p)$ precision?\n\n- Is the use of communication complexity in the approximability of Transformers (and broader Neural networks) novel in this work?", "limitations": "It is hard to foresee any potential negative societal impact of this theoretical work. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The authors leverage the communication complexity to show that the self attention layers add more representational capacity as compared to fully connected and recurrent neural networks. \n\n- They use Match2 and Match3 problems to show rigorously that 2nd-order functions represent the threshold of efficient approximability for transformers.\n\n- The variants of Match3 problems hint at transformers leveraging some local structures present in the data to go beyond pair matching. This reconciles the Match3 impossibility result with the much presumably higher order successes of transformer models. \n\n- They additionally show higher order transformers can solve the higher order function approximations. \n\n\n\n", "weaknesses": "- The fixed precision (Theorem 2) result still uses precision that needs to grow with the data size and approximation parameters. Although it is a good first step, it leaves open the approximability with constant precision (which is used in most practical cases). \n\n- The ``third-order tensor self-attention\" is an important claim in the paper, but it is fully omitted in the main paper. It will be good to at least introduce the basic ideas in the main paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The fixed precision (Theorem 2) result still uses precision that needs to grow with the data size and approximation parameters. Although it is a good first step, it leaves open the approximability with constant precision (which is used in most practical cases).\n\nWe agree that constant precision is an interesting case to consider, and we thank the reviewer for raising this as a potential area of improvement.\n\nWhen reassessing our positive result in Theorem 3, we realized that the bit precision analysis can be improved to $p = \\Omega(\\log(q\\log(N) \\epsilon))$, which should partially address the reviewer's question by reducing the dependence on $N$ to doubly-logarithmic. In brief, the sharpening proceeds by augmenting the proof with the following analysis:\n- Under $p = \\Theta(\\log (q\\log(N) / \\epsilon))$-bit precision, each query vector $w_y$ can be quantized with a $p$-bit floating point vector that that approximates it to accuracy $\\text{poly}(\\epsilon / (q \\alpha))$.\n- Hence, we can ensure that the computed inner products satisfy $\\langle u_{i'}, w_y \\rangle \\in [1 - \\text{poly}(\\epsilon / (q \\alpha)), 1+ \\text{poly}(\\epsilon / (q \\alpha))]$ if $i' \\in y$ and $\\langle u_{i'}, w_y \\rangle \\in [\\frac12 - \\text{poly}(\\epsilon / (q \\alpha)), \\frac12 + \\text{poly}(\\epsilon / (q \\alpha))]$.\n- Propagating this change forward, we can ensure that $\\text{softmax}(\\phi(X) QK^T \\phi(X)^T)\\_{i, i'} \\in [\\frac{(1 - \\epsilon/2)}q, \\frac{(1 + \\epsilon/2)}q]$ if $i' \\in y_i$ and $\\text{softmax}(\\phi(X) QK^T \\phi(X)^T)\\_{i, i'} \\leq \\frac{\\epsilon}{2N}$ otherwise. While $\\log N$ bits are needed to accurately represent the latter quantity, a lower bit-complexity would simply round the term to zero, which does not hinder the ability of $f(X)$ to approximate $\\text{qSA}(X)$.\n\nThe same quality of approximation is thus recovered without requiring $O(\\log N)$-bit precision.\n\nHowever, we would also like to note that we think it's reasonable to consider a $p = \\Theta(\\log N)$ scaling for bit-precision. Trained self-attention matrices frequently compute non-sparse averages over all inputs (see Figure 13 in the supplement of Jumper et al, 2021), where the softmax outputs approximately $\\frac1N$ for each input token. Since transformer implementations use floating-point arithmetic, one can assume that the precision of the floating point is be large enough to ensure that $\\frac1N$ is not rounded to zero.\nOn a similar note, we do not expect our bounds to work with less than $O(\\log q)$-bit precision, since the aim is to approximate a function that computes an average over $q$ elements.\n\nJumper J, Evans R, Pritzel A, Green T, Figurnov M, Ronneberger O, Tunyasuvunakool K, Bates R, Žídek A, Potapenko A, Bridgland A. Highly accurate protein structure prediction with AlphaFold. Nature. 2021.\n\n\n> Given a fixed constant precision what is the bottleneck in creating the transformers that can approximate q-SA? What if z_is are themselves restricted to some precision?\n\nSee above.\n\n> The \"third-order tensor self-attention\" is an important claim in the paper, but it is fully omitted in the main paper. It will be good to at least introduce the basic ideas in the main paper.\n\nThank you for the suggestion; we'll do just that. (The additional content page in the camera-ready should more than suffice.)\n\n> Is the use of communication complexity in the approximability of Transformers (and broader Neural networks) novel in this work?\n\nWe have not seen communication complexity used in the context of Transformers before, but it has been used to prove lower bounds for neural networks (and circuits/formulas) before. We'll make sure to cite these and other works in the camera-ready version.\n\nKarchmer M, Wigderson A. Monotone circuits for connectivity require super-logarithmic depth. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 1988.\n\nMartens J, Chattopadhya A, Pitassi T, Zemel R. On the representational efficiency of restricted Boltzmann machines. Advances in Neural Information Processing Systems, 2013.\n\nVardi G, Reichman D, Pitassi T, Shamir O. Size and depth separation in approximating benign functions with neural networks. In Conference on Learning Theory, 2021."}, {"review_id": "AnGKihI4cV", "reviewer": "Reviewer_iCyX", "summary": "This paper mainly investigates the inductive biases of attention-based models. They propose three computational tasks that show the limitations of Transformers, namely, sparse averaging, pair matching, and triples-matching. Specifically, they analyze the representational power of embedding dimensions and show that the sparse averaging task scales more favorably in the input size as opposed to the other two tasks. Various proofs are provided to support the investigations and conclusions.", "questions": "* It seems somewhat obvious that the representational capacity of performant Transformeres is related to the embedding space and operations for comparison performed on thus. Have the authors experimented with different contexts aside from the embedding space?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* Interesting and relevant topic on interpreting the Transformer computations and learning progress. \n* Good connections with relevant prior works in setting the backgrounds for inspiring the tasks and their practical implications proposed", "weaknesses": "* Initially the notation is a bit confusing, especially in section 1.1 that details the contributions. Variables $y$ and $z$ should be more clearly defined and explained when mentioning results of the theoretical analysis.\n* The intro can maybe be reworked to slowly work in the details and notation of the method instead of initially presenting the mechanisms that the different tasks enable ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Initially the notation is a bit confusing, especially in section 1.1 that details the contributions. Variables and should be more clearly defined and explained when mentioning results of the theoretical analysis.\n\nUpon a closer reading, we see that we use a large amount of condensed English and notation, which hinders a first reading. We will gladly refine and expand this section, using some of the extra space granted with the extra camera ready page. Would the reviewer like to point out any specific frustrations in Section 1.1?\n\nMore broadly, we think that adding a few paragraphs the beginning of the section to clarify the paper's contributions before introducing the task formulations would help remedy the issues identified by this reviewer and SrVL.\n \n1. Brief description of the transformer architecture\n    - Simple mathematical formulation of a self-attention unit (without MLPs to keep it simple)\n    - Overview of how transformers are assembled by composing these units in parallel and in series\n    - Introduction of all relevant architectural resources and their corresponding variables: number of heads, depth, embedding dimension, bit-precision\n2. Overview of our main findings (without getting into details of the problem)\n    - Goal of the paper is to identify tasks that cleanly separate the abilities of different neural architectures with a focus on transformers: what self-attention can do that other models cannot, how embedding dimension modulates approximation power, fundamental limitations of self-attention can do\n    - The methodology of the paper is to introduce such tasks and prove upper and lower bounds the resources necessary for neural architectures to solve those tasks\n\n> The intro can maybe be reworked to slowly work in the details and notation of the method instead of initially presenting the mechanisms that the different tasks enable\n\n> It seems somewhat obvious that the representational capacity of performant Transformeres is related to the embedding space and operations for comparison performed on thus. Have the authors experimented with different contexts aside from the embedding space?\n\nWe agree that it is intuitive that results such as ours should be true, but they have not been proved for transformers before our work. Our investigation also reveals fundamental benchmark problems (e.g., qSA, Match2) that we expect to be useful in future studies of transformers and related architectures.\n\nWe abstracted away many aspects of transformers and embeddings, and this certainly poses interesting questions for future work. (Our particular choices are in part motivated by the practical scaling trends discussed at the top of Page 2 of our paper.) We would very much appreciate suggestions for other aspects of embeddings that might be amenable to mathematical analysis."}, {"review_id": "rYEAOAIIDU", "reviewer": "Reviewer_jpuU", "summary": "This paper focuses on the representational capabilities of attention layers in transformer models and showcases both the strengths and limitations. On one hand, the paper proves that attention layers excel at the presented sparse averaging task compared to RNNs and FNNs. On the negative side, they have complexity scaling linearly in the input size for the triple detection task. The paper theoretically showcases the strengths and limitations of the expressivity of attention layers, especially the role of embedding dimension of the attention layer.", "questions": "My questions and suggestions are listed above.", "limitations": "This is a theory paper and the authors provided open directions for future work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "To my knowledge, the presented theoretical results are novel in the study of transformers and their representational capabilities. However, this work is out of my expertise and I cannot go into depth about the significance of the work. I do appreciate the authors in providing some empirical evidence about the theoretical findings of the work.", "weaknesses": "As said previously, this is not within my area of expertise. I am however interested in how relevant/connected are the proposed tasks (e.g. sparse averaging and triple detection) to empirical studies such as language or visual data modeling. I think the work would be improved if more insights could be provided as to how the theoretical results can be connected to real-world practices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> As said previously, this is not within my area of expertise. I am however interested in how relevant/connected are the proposed tasks (e.g. sparse averaging and triple detection) to empirical studies such as language or visual data modeling. I think the work would be improved if more insights could be provided as to how the theoretical results can be connected to real-world practices.\n\nWe agree that it would be very interesting to connect the tasks to real-world problems and practices. However, it is also independently interesting to establish fundamental capabilities and limitations of transformers on mathematically precise settings. See the response to reviewer SrVL for an explanation of our intuition for selecting these tasks. \n\nIn short, the sparse averaging task was inspired by analyses of the sparsity patterns of attention matrix softmax outputs. We study Match2 because we see a connection between Match2 is a useful primitive for language tasks like coreference resolution and because tree-like grammars can be reconstructed by applying Match2 multiple times; in contrast, Match3 is an analogous primitive that transformers apparently fail to represent without contextual clue (e.g. Match3Assist or Match3Local).  Standard literature on coreferences may be found [at this page hosted by the stanford NLP group](https://nlp.stanford.edu/projects/coref.shtml); we will revise our work with this discussion and appropriate citations."}, {"review_id": "XRlu9cvL77", "reviewer": "Reviewer_SrVL", "summary": "The paper presents the representational strength and some limitations of the transformer architecture.\n1. Strength: separation between a unit of self-attention and a one-hidden layer neural or a recurrent neural network.\nThe authors present a task where the complexity of the latter networks scale with N (number of tokens) and the self-attention does not.\n2. Limitation: the task Match2 can be computed with a self-attention unit that scales with the input dimension d, yet, a modification of the task, Match3, cannot be computed with a single transformer layer. Match3 can be computed with a standard and modified transformer model. The first makes assumptions over the input the second model modifies the self-attention module.\n\n", "questions": "I would be happy to change my mind about the paper since the paper is written technically very well. Better than most theoretical papers I encounter! \n\nCan the authors at least give some intuitive explanations why they think the tasks presented in the paper are relevant to NLP or any other ML task? Maybe a small experimental study on a small transformer network and show that the functions qSA, Match2, and Match3 somewhat resemble the functions the transformer networks actually compute?\n\nMore so, through the years, I haven't encountered a single theory paper about the representational power of neural networks that actually sheds any light on understanding neural networks better in the practical sense of explaining their performance (other than the original universal approximation paper). For example, one can study the VC dimension of different architectures, but this does not bring us any step closer to understanding neural networks in practice. \n\nIn its current form, I think the paper is suited to a pure theoretical venue such as a math journal or a theoretical CS conference. To make it more suitable for an ML venue, a reasonable amount of effort is required to motivate theoretical setup and questions. In that case, it's likely that the scope of the paper would not fit a conference paper but in a journal.\n", "limitations": "The authors adequately addressed the limitations of their work.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is very well written. I could easily understand and follow all the definitions and the Theorems presented in the paper's main text. ", "weaknesses": "The weakness of this paper lies in its relevance to the understanding of transformer networks.\n\nThe paper presents problems qSA, Match2, and Match3, whose relevance to understanding neural networks in practice is unclear. This is even stated in the paper: \"Future work by linguists, theoretical computer scientists, and empirical NLP practitioners could assess how foundational our primitives are and study whether there are any practical triple-wise problems that transformer models fail to solve.\"\n\nI think that when studying theoretical aspects of neural networks, it is the responsibility of the authors to motivate their theoretical results and why their assumptions or framework are relevant. Otherwise, such theoretical content belongs in a mathematical venue.\n\nMinor comment:\nWhen reading Section 1.1 for the first time, I could not follow the authors' intentions/message. Only after carefully reading the rest of the text and definitions could I understand it. As written now, I think it does not convey information properly for someone just interested in having a quick general idea of the results.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Minor comment: When reading Section 1.1 for the first time, I could not follow the authors' intentions/message. Only after carefully reading the rest of the text and definitions could I understand it. As written now, I think it does not convey information properly for someone just interested in having a quick general idea of the results.\n\nWe appreciate this comment, and upon revisiting the section, we recommend a few paragraphs the beginning of the section to clarify our contributions before introducing specific details and notation about tasks. Please see our response to reviewer iCyX for our planned revision of Section 1.1 in the camera-ready version.\n\n> Can the authors at least give some intuitive explanations why they think the tasks presented in the paper are relevant to NLP or any other ML task? Maybe a small experimental study on a small transformer network and show that the functions qSA, Match2, and Match3 somewhat resemble the functions the transformer networks actually compute?\n\nOur intuition was primarily shaped by reading papers that analyzed the self-attention matrices on NLP tasks, such as the following:\n\nClark K, Khandelwal U, Levy O, Manning C. What Does BERT Look At? An Analysis of BERT's Attention. In ACL 2019.\n\nRogers A, Kovaleva O, Rumshisky A. A Primer in BERTology: What We Know About How BERT Works. In ACL 2020.\n\nChen N, Sun Q, Zhu R, Li X, Lu X, Gao M. CAT-probing: A Metric-based Approach to Interpret How Pre-trained Models for Programming Language Attend Code Structure. In EMNLP 2022.\n\nThe qSA task was motivated by the fact that most self-attention matrices appear to be either wide-scale averages over a large fraction of tokens (where most inputs average over the same collection of other inputs and the identity of the token has little bearing on which elements it is associated with), or sparse matrices where different inputs map to different averages of outputs. These often correspond to intuitive linguistic relationships, such as those linking antecedents and coreferences. We were interested in the limitations of this sparse collection of individual linkages, and we crystallized sparse averaging as a way to make this problem concrete.\n\nAs noted by Rogers et al, grammatical structures and syntax are directly encoded in self-attention matrices, which can in turn be decomposed into sentence diagrams or trees over multiple layers. We see Match2 as a fundamental unit of that phenomenon, since trees are easily decomposed into combinations of pairwise matches. We also see a more direct motivation for Match2 in co-reference resolution. On the other hand, we see Match3 as an operation that does appear in standard NLP tasks, and that when it does, it's analogous to Match3Assist or Match3Local. Rather, we considered Match3 to represent a family of sequential learning problems that we expect to be much more difficult to solve than real-world language problems.\n\n> I think that when studying theoretical aspects of neural networks, it is the responsibility of the authors to motivate their theoretical results and why their assumptions or framework are relevant. Otherwise, such theoretical content belongs in a mathematical venue.\n\nWe agree with the general standard---applicable to all papers and not just \"theoretical papers\"---of providing motivation and justifying assumptions and frameworks, and our paper does meet this standard. The motivation to study transformers is given throughout the introduction of the paper, along with specific justification for our analysis framework and scaling regimes. Understanding fundamental capabilities and limitations of transformers is of interest to researchers studying these models, and the types of separation results we proved have a long history of being presented at machine learning venues, including NeurIPS, over the past few decades.\n\nWe don't agree that \"theoretical papers\" are subject to a different standard for NeurIPS compared to other types of papers, as the [NeurIPS Call for Papers](https://neurips.cc/Conferences/2023/CallForPapers) explicitly welcomes learning theory papers without stipulating any such qualifications.\n\n\n> More so, through the years, I haven't encountered a single theory paper about the representational power of neural networks that actually sheds any light on understanding neural networks better in the practical sense of explaining their performance (other than the original universal approximation paper). For example, one can study the VC dimension of different architectures, but this does not bring us any step closer to understanding neural networks in practice. \n\nWhile it is true that theory has failed to provide an end-to-end story for deep learning (e.g., why gradient descent applied to transformers can lead to good question-answering abilities), it has provided many useful *suggestions* and *mental models* for reasoning.  For example, capacity theory (such as generalization bounds) motivate the use of regularization and weight decay, which are still used in modern architectures.  The classical theory of universal approximation, while lacking effective bounds and guidance for architecture selection, do sanity check the enormous representational power of deep networks.  In our case, while our theorems are purely representational, in appendix D we verify empirically that qSA is a problem efficiently learned empirically by transformers, but not by other architectures (as evidence by their poor *test* error); tying this back, while perhaps the reviewer feels our work does not have explicit empirical suggestions, it motivates a problem which does capture some empirical benefits of transformers over their predecessors."}, {"review_id": "aQG46gDz5q", "reviewer": "Reviewer_CgC3", "summary": "This paper investigates the representation power of attention layers in transformer networks and compares them with other neural network architectures. The authors establish both positive and negative results on the benefits and limitations of attention layers, focusing on intrinsic complexity parameters such as width, depth, and embedding dimension. The positive results include the demonstration of a sparse averaging task where transformers scale logarithmically in the input size, compared to polynomial scaling in recurrent networks and feedforward networks. They also show the necessity and role of a large embedding dimension in transformers. On the negative side, they present a triple detection task where attention layers have linear complexity in the input size. However, they also provide variants of the task that can be efficiently solved by attention layers. The paper's contributions include the formalization of computational limits using communication complexity, the establishment of the representational capabilities and limitations of self-attention units, and the demonstration of the impossibility of computing Match3 using standard multi-headed attention layers in an efficient manner.", "questions": "Please see above comments.", "limitations": "Not applicable.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n- This paper brings some original contributions to the understanding of attention layers in transformer networks. It provides a mathematical analysis of the representation power of attention layers and compares them to other neural network architectures. The paper introduces some interesting tasks, such as sparse averaging, pair matching, and triple matching, to evaluate the capabilities and limitations of attention layers. This approach introduces fresh perspectives on the benefits and deficiencies of attention layers and offers valuable insights into their role in deep learning.\n\n- The paper demonstrates a high level of quality in terms of its analysis and proofs. It presents rigorous mathematical formulations and provides formal definitions for the tasks and architectures under study. The proposed theorems and conjectures are well-supported and backed by detailed proofs, showcasing the authors' expertise in the subject matter. The use of communication complexity techniques adds depth and reliability to the analysis. The paper also includes supplementary proofs and explanations in the appendices, further enhancing the quality and comprehensiveness of the work.\n\n- The paper addresses an important gap in the literature by providing a mathematical analysis of the benefits and limitations of attention layers in transformers. The findings have implications for the design and optimization of deep learning models, especially in natural language processing and other sequential tasks. The identification of tasks that highlight the strengths and weaknesses of attention layers can guide future research in developing more efficient and effective architectures. The paper also raises intriguing conjectures, such as the impossibility of efficiently computing Match3, which can inspire further investigations and spark valuable discussions in the research community.", "weaknesses": "\n- While the paper provides rigorous mathematical analysis and proofs, it lacks empirical evaluation of the proposed tasks and architectures. Including experiments using real-world datasets could provide practical validation of the theoretical findings and further strengthen the paper's conclusions. Empirical evaluation could also provide insights into the computational efficiency and generalization performance of attention layers compared to other architectures.\n\n- Providing concrete examples of how the theoretical findings can be applied to practical deep learning problems, such as natural language processing or computer vision tasks, would enhance the paper's relevance and impact.\n\n- While the paper is generally well-written, the mathematical formulations and proofs can be complex and challenging to follow for readers without a strong background in the subject area. Simplifying and clarifying the presentation of the mathematical concepts and providing more intuitive explanations or examples could improve the accessibility of the paper for a wider audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> While the paper provides rigorous mathematical analysis and proofs, it lacks empirical evaluation of the proposed tasks and architectures. Including experiments using real-world datasets could provide practical validation of the theoretical findings and further strengthen the paper's conclusions. Empirical evaluation could also provide insights into the computational efficiency and generalization performance of attention layers compared to other architectures.\n\nEmpirical evaluations on real-world datasets cannot establish fundamental limits or asymptotic separations between different Transformer architectures. While we agree that that computational and statistical properties of transformers can be rigorously studied with empirical methods, these are not the focus of this work, which focuses on approximation capabilities and fundamental limitations.\n\nWe do include brief experiments in Appendix D, which, while not comprehensive, suggest that transformers have a favorable inductive bias for learning qSA from randomly drawn samples, in contrast to other standard neural architectures like MLPs and LSTMs, which both overfit the training dataset with disastrous generalization. We chose not to emphasize these experiments due to our theoretical focus and the space limitations, but the extra space allocated to the camera-ready version would allow us to present this in the main body.\n\n> Providing concrete examples of how the theoretical findings can be applied to practical deep learning problems, such as natural language processing or computer vision tasks, would enhance the paper's relevance and impact.\n\nThe theory of transformers is not yet at this stage; we are still laying the foundations. (This is similar to early theoretical work on MLPs from Kolmogorov and Arnold from 1957, which characterized a broad class of multivariate functions as a superposition of continuous univariate functions and forms a foundation for future work on the universal approximation of 2-layer MLPs. Recent generalization work about MLPs with more practical implications follows several years of approximation-theoretic work on foundational issues.)\n\n> While the paper is generally well-written, the mathematical formulations and proofs can be complex and challenging to follow for readers without a strong background in the subject area. Simplifying and clarifying the presentation of the mathematical concepts and providing more intuitive explanations or examples could improve the accessibility of the paper for a wider audience.\n\nWe are happy to address clarity issues in the presentation. Can you give any specific pointers?"}]

Author rebuttal:
We thank the reviewers for their detailed and thoughtful feedback on our submission. We are grateful that the reviewers largely appreciated the strength and value of our fundamental theoretical contributions while identifying areas of improvement. We agree that some aspects of the presentation of the paper can be improved, and our replies to specific comments detail our plan to do so. If any questions are unanswered or our responses are unclear, we would appreciate the chance to engage further with our reviewers. 

Briefly, the key points of our response are the following:

1. **Precision analysis:** Reviewer bhmz asked about whether our results can be adapted to constant bit precision. We appreciate the constructive feedback, and while considering it, realized that our analysis of the bit precision of our positive sparse-averaging result can be significantly sharpened (from logarithmic to doubly logarithmic dependence on sequence length). We explain in detail in our response below why we believe this bit precision bound to be nearly optimal.

2. **Clarity and notational issues:** Reviewers iCyX and SrVL both noted a difficulty in understanding the framing of our contributions in the introductory Section 1.1, in particular due to the mathematical notation. We appreciate the reviewers calling attention to this issue, and we will add a few paragraphs (outlined in the response to iCyX) to clarify our contributions without dense notation.

3. **Omission of third-order tensor self-attention:** We acknowledge the oversight that third-order tensor attention was insufficiently discussed in the main paper body raised by reviewer bhmz. We regret the omission, and we intend to remedy it with the additional page permitted for the camera-ready version.

4. **Relevance to practical tasks:** Reviewers jpuU, SrVL, and CgC3 requested clarification on our motivation for choosing the qSA, Match2, and Match3 problems and the relevance of our work to empirical training of transformers. While our goal was to define tasks that clearly delineate the capabilities of different architectures, we agree that additional context would help readers understand our contributions. We outline our intuitions about why these tasks are relevant in the response to SrVL, and we call attention to our brief empirical results in Appendix D.

Once again, we are grateful for the time and effort put into reviewing this submission, and we firmly believe that these comments will strengthen the clarity and motivation of our manuscript.

Meta-review: This paper aims to study the representational power of the attention layer -- a key component of the transformer architecture. The authors present a task, namely q-sparse averaging, which a single-layer transformer can approximate with the embedding dimension scaling logarithmically in the sequence length $N$. In contrast, fully connected networks or RNNs require network size to scale polynomially in $N$. The authors also discuss a pair detection task Match2 which the attention layer can efficiently approximate. The authors then highlight the limitation of the attention layer by considering a triple detection task Match3 which requires the attention layer to scale its parameters (number of heads or embedding dimension) polynomially in N. Interestingly, the author also identified structured versions of Match3 which attention layer can efficiently approximate.

Overall, the reviewers agree that this paper makes novel contributions that are technically sound. The paper leverages tools from communication complexity to study the fundamental limits of transformers which will inspire other follow-up works.

One of the key concerns that multiple reviewers raised during the review process was that it was not clear how the tasks considered in this paper are connected with the practice. In their response, the authors pointed out many empirical studies in NLP that served as a motivation for the task considered in this work. Although there is no one-to-one connection with the tasks encountered in practice, the tasks studied in this submission do capture some aspects of the real-life tasks. This paper makes a good first step towards rigorously understanding the representational limits of transformers which many researchers will find interesting. I am sure that this paper will lead to follow-up works that will explore a rigorous analysis of the tasks that are more closely aligned to those encountered in practice.

One of the reviewers had asked to improve the bit precision requirement for Theorem 2. The authors did provide a sketch to improve their analysis and improve the precision requirement from logarithmic to doubly logarithmic.

The reviewers made multiple suggestions to improve the presentation of the paper which the authors have promised to incorporate in the revised version. In particular, 

1) Please improve the presentation in Section 1.1.
2) Please include citations to the references that came up during the discussion with the Reviewer SrVL and provide a discussion on how different tasks considered in this work are (partially) inspired by either the observations in practical Transformer models or sub-tasks encountered in various real-life NLP settings.
3) Please highlight both higher-order attention and your experiments on the synthetic qSA task in the main body of the paper.
Decision: Accept (poster)