Why Self Attention is Natural for Sequence-to-Sequence Problems? A Perspective from Symmetries
Authors: Chao Ma
Lexing Ying
Venue: Submitted to ICLR 2023 (2023)
Keywords: Self attention
sequence-to-sequence function
orthogonal equivairance
permutation equivariance

Abstract: In this paper, we show that structures similar to self-attention are natural to learn many sequence-to-sequence problems from the perspective of symmetry. Inspired by language processing applications, we study the orthogonal equivariance of {\it seq2seq functions with knowledge}, which are functions taking two inputs---an input sequence and a ``knowledge''---and outputting another sequence.
The knowledge consists of a set of vectors in the same embedding space as the input sequence, containing the information of the language used to process the input sequence. We show that orthogonal equivariance in the embedding space is natural for seq2seq functions with knowledge, and under such equivariance the function must take the form close to the self-attention. This shows that network structures similar to self-attention are the right structures to represent the target function of many seq2seq problems. The representation can be further refined if a ``finite information principle'' is considered, or a permutation equivariance holds for the elements of the input sequence. 

Under review as a conference paper at ICLR 2023
WHY SELF-ATTENTION IS NATURAL FOR SEQUENCE- TO-SEQUENCE PROBLEMS? A PERSPECTIVE FROM SYMMETRIES
Anonymous authors Paper under double-bling review
ABSTRACT
this paper, we show that structures similar to self-attention are natural to learn many sequence-to-sequence problems from the perspective of symmetry. Inspired by language processing applications, we study the orthogonal equivariance of seq2seq functions with knowledge, which are functions taking two inputs in- and put sequence and a "knowledge" and outputting another sequence. The knowl- edge consists of set of vectors in the same embedding space the input quence, containing the information of the language used to process the input se- quence. We show that orthogonal equivariance in the embedding space is natural for seq2seq functions with knowledge, and under such equivariance the function must take the form close to the self-attention. This shows that network structures similar to self-attention are the right structures to represent the target function of many seq2seq problems. The representation can be further refined if "finite in- formation principle" is considered, or permutation equívariance holds for the elements of the input sequence.
INTRODUCTION
Neural network models using self-attention, such as Transformers Vaswani et al. (2017). have be- come the new benchmark in the fields such as natural language processing and protein folding. Though, the design of self-attention is largely heuristic, and theoretical understanding of its success still lacking. this paper, we provide a perspective for this problem from the symmetries of sequence-to- teseuueee---seeeeeeeeeeee (seq2seq) learning problems. By identifying and studying appropriate sym- metries for seq2seq problems practical interest, we demonstrate that structures like self-attention natural for representing these problems.
Symmetries in the learning problems can inspire the invention of simple and efficient neural net- work structures. This is because symmetries reduce the complexity of the problems, and network with matching symmetries can learn the problems more efficiently. For instance, convolutional neural networks (CNNs) have seen great success ance/equivariance of the problems being one of the main reasons. This not only observed in practice, but also justified theoretically [L et al. (2020b). Many other symmetries have been studied and exploited in the design of neural network models. Examples include permutation equivari- ance Zaheer al. (2017) and rotational invariance Kim et al. (2020); Chidester et al. (2019), with various applications in learning physical problems. See Section 2.1 for more related works.
vision problems, with the translation invari-
In this work, we start from studying the symmetry of seq2seq functions in the embedding space, the space in which each element of the input and output sequences lic. For a language processing prob- lem, for example, words or tokens are usually vectorized by a one-hot embedding using dictionary. In this process, the order of words in the dictionary should not influence the meaning of input and output sentences. Thus, a permutation is applied on the dimensions of the embedding space, the input and output sequences should experience the same permutation, without other changes. This implies a permutation equivariance in the embedding space. In our analysis, we consider equivari- ance under orthogonal group, which is slightly larger than the permutation group. We show that a function f is orthogonal equivariant in the embedding space, then its output can be expressed linear combinations of the elements of the input sequence, with the coefficients only depending

---

Under review as a conference paper at ICLR 2023
on the inner products of these elements. Concretely, let X R denote an input sequence with length n in the embedding space R If f(QX) = =X((X) holds for any orthogonal Q E Raxd then there exists function g such that
f(x) = X=xxXXXX
However, the symmetry on the embedding space is actually more complicated than a simple orthog- onal equivariance. In Section 3.2 we show that the target function for simple seq2seq problem is not orthogonal equivariant, because the target function works a fixed embedding. To accurately catch the symmetry in the embedding space, we propose to study seq2xeq functions with knowl- edge, which are functions with two inputs, s(X, 2), where X E RR is the input sequence and Z E Bd is another imput representing our "knowledge" of the language. The knowledge lies in the same embedding space as X. and is used to extract information from X. With this additional input, the symmetry in the embedding space can formulated as an orthogonal equivariance of fX, Z), i.e. f(QX, QZ) Qf K Z) for any inputs and orthogonal matrix Q. Intuitively under- stood, in a language application, as long as the knowledge is always in the same embedding as the input sequence, the meaning of the output sequence will not change with the embedding. Based on the earlier theoretical result for simple orthogonal equivariant functions, if a seq2seq function with knowledge is orthogonal equivariant, then it must have the form
f(X, Z) Xg1 (x" x, z" X, zzz Z)
If Z is understood as a parameter matrix to be learned, the following subset of this representation,
f(X, 2) 2))X"2),
close to self-attention used practice, with Z being the concatenation of query and key parame- ters. This reveals one possible reason behind the success of self self-attention based models on language problems.
Based on the results from orthogonal equivariance, we further study the permutation equivariance on the elements of the input sequence. Under this symmetry, we show that seq2seq functions with knowledge have a further reduced form which only involves four different nonlinear functions. Fi- nally, discussions are made on the possible forms of g (or g1 and g2) in the formulations mentioned above. Based on the assumption that these functions are described by finite amount of information (although their output sizes need to change with respect to the sequence length n). we reason that quadratic forms with nonlinearity used in usual self-attentions is one of the simplest choice of g- We also discuss practical considerations that add the complexity of the models used in application compared with theoretical forms.
BACKGROUND AND RELATED WORK
2.1 NEURAL NETWORKS AND SYMMETRIES
Implementing symmetries in neural networks can help the models learn certain problems more ef- ficiently. A problems due to their (approximate) translation invariance LeCun et al. (1989). Many types of sym- metries have been explored in the design of neural networks, such as permutation equivariance and invariance Zaheer et al. (2017): /Guttenberg et (2016); Rahme et al. (202T): : Qi al. (201 7a b), ro- tational equivariance and invariance Thomas al. (201 8) Shuaiib al. (2021) Fuchs et (2020); Kim et al. (2020), and more Satorras et al. (2021) bb: Wang et al. (2020b) ; Ling et al. (2016s 6a);; Ravan- bakhsh al. (2017). Some works deal with multiple symmetries. In Villar et al. al. (2021). l). the forms of functions with various symmetries are studied. These networks see many applications in physical problems, where symmetries are intrinsic in the problems to learn. Examples include fluid dynam- ics Waag et al. (2020a); Ling et al. (2016b): Li et al. (2020a); Mattheakis et al. (2019), molecular Anderson et al. (2019 y p Schütt al. (2021) Zhang et al. (2018), quantum mechanics Luo et al. (2021a b); Vieijra al. (2020), etc. Theoretical studies have also been conducted to show the benefit of preserving symmetry during learning Bietti et al. (2021); Elesedy & (202) Li et al.
example is the success of convolutional neural networks (CNNs) on image
LevCrianceLLCCun
(2020b): Mei al. (2021).
2.2 SELF-ATTENTION
self-attention Vaswani et al. (017)): Parikh et al. (2016); Paulus et al.
(2017); ; Lin et al. (2017): S/Shaw
et al. 2018) a type of attention mechanism Bahdanau et al. (2014) Luong et al. (2015) that attends
2

---

Under review as a conference paper at ICLR 2023
different elements in same imput sequence. It is the building block of series of large language models (e.g. Devlin et al. (2018); Brown et al. (2020); Raffel et al. (2020)) ) and is under extensive research. See Bommasani et al. (2021) Niu et al. (2021) for reviews.
As a preparation for later studics, we briefly summarize the structure (multihead) self-attention. A self-attention is seq2seq operator which takes sequence of vectors the input, and another sequence of vectors (of the same size) as the output. Let X E Rdxx be the input sequence with length n. A self-attention computes the output using three parameter matrices: the query parameters We E R2 xd the key parameters WK E RR xd and the value parameters Wv E R Given the input X, "query" and "key" is computed for every column of X by multiplying with WQ and WK. i.c we compute Q(X) W E gd x and (XX) WK X R Then, an attention matrix is obtained by computing the inner product of all pairs of queries and keys:
A(X) Q(X)"X(X)=== = X W E RO*"
Next, weight matrix is computed by applying softmax over rows of A, and the output of the attention is obtained by linear combination of the "values", WvX, using rows in the weight matrix as coefficients, In practice, A(X) usually scaled by factor of 1/ /d, and residual connection is added, thus we have
Attn(X) = x WXXS, (Va, ( (xxWWWxxx) T
(1)
where S,(-) computes the softmax of an input matrix over rows.
Remark 1. In this paper we use X E TRdxn to denote sequences with length n. in the space TR. Each column of X an element of the sequence. many works the same sequence represented by an x d matrix. The two representations intrinsically equivalent.
The self-attention mechanism described above consists of one "head", in the sense that we have one query, key and value for each element of X. Similar to the way that we add more neurons a layer of a fully connected neural network, we can add more heads to self-attention, which gives multihead attention. For a multihead attention with m heads, we have m different query, key, and
value matrices, denoted by w ((O, and Wi w(( and w-( are still dN x d matrices, while V are d2 d matrices. Besides, in order to still use the residual connection, an output parameter matrix (=(+) E idxdd added for each head to transform the value vectors IRda into vectors in Rd With these parameters, each head is similar to single-heat head self-attention:
1 x ( (w( (
head, w XS,
and the output of the multihead attention is
Attn (X)= X +
Σ
w w head,
i=1
=X+
Σ
( w
(0) XS,
(v x (w!l)) Tw
Remark 2. In practical model like Transformer. a fuully-connecee layer is sometines added after multihead attentions. The fully- layer applied to each element of the output sequence.
3 ORTHOGONAL EQUIVARIANCE IN THE EMBEDDING SPACE
In this section, we focus on the orthogonal equivariance in the embedding space. We show that functions with such equivariance enjoy a representation which takes a similar but more general form self-attention. We start from theoretical characterization for simple seq2seq functions with orthogonal equivariance (Proposition [].. Then, we introduce and study a class functions called seq2seq function with knowledge, whose form is inspired by typical seq2seq learning problems.
3

---

Under review as a conference paper at ICLR 2023
3.1 SIMPLE ORTHOGONAL EQUIVARIANT FUNCTIONS
We first consider orthogonal equivariant functions given by the following definition:
Definition 1. Let X = - Raxn be the space of all sequences in R Let f X - X be a sequence sequence function. f is called orthogonal equivariant in the embedding space if for any X E X and orthogonal matrix Q E IRdxd, there is J(QX) = Q](X).
For orthogonal equivariant functions, the following proposition shows that any column the output must be linear combination of the the columns of X, with the coefficients depending only on the inner products between X's columns.
Let f : Then, there exists function g taking X X as input and producing matrix with appropriate shape as output, such that for all X X, we have
Proposition 1.
X +
X be orthogonal equivariant in the embedding space given by Defini-
tion I
XXxX")
Proposition shows that orthogonal equivariant seq2seq functions always represent linear combi- nation of the elements of their input sequence X, with the coefficients being orthogonal invariant. We give the proof Appendix [ A similar result has appeared in Villar et al. (202T) and played an important role for physics applications.
3.2 ORTHOGONAL EQUIVARIANCE WITH "KNOWLEDGE"
Proposition treats seq2seq functions that are strictly orthogonal equivariant in the embedding space. For many practical language problems or other seq2seq learning problems, the embedding indeed has some flexibility over orthogonal transformations- information is encoded only in the relative positions between vectors in the embedding space, and an orthogonal transformation of those vectors does not change the "meaning" of the sequence, hence the "answer" of the transformed input sequence should be the transformed original answer.
However, this intuitive symmetry does not mean that the target function is orthogonal equivariant. As an example, consider a seq2seq function f that takes an arithmetic expression as the input and outputs the result of the expression, e-g 1""2+1")) "3" f(22- 1") "1". The tokens used in the input and output sequences include single digit numbers 0- and arithmetic operators. These tokens can be cast into vectors by an one-hot embedding. To be simple, suppose we only use operators "4" and "_", Then, the embedding space has 12 dimensions. One possible embedding is
+ E1
"0" + es. "1" es. ... "9" + e12+
where e, is the i-th unit vector in the standard orthonormal basis of 1 Under this embedding, f("2 + 1") =3" be written
f((es, 31, e,)) [eg]-
Now, let Q12 R 12x be linear transformation that swaps the first and second entries of any vector in 12 Then, Q12 is orthogonal. If is orthogonal equivariant, we will have
f(les, C2, ea)) = f(Q(es, e1, ea)) = [Qes] = [cs]-
This means ((22-1") = "3", which is obviously not what we expect.
To summarize, the target function is not orthogonal equivariant because it works in fixed em- bedding and cannot deal with sequences from different embeddings. The intuitive symmetry we discussed earlier can be understood as the symmetry in equivalent class of target functions. Let be a seq2seq function in a certain embedding, if an orthogonal transformation Q is applied to this embedding, then there exists another function fo that satisfies
fo(Qx)= (X)
fo does the same thing as ff in different embedding. Collecting fo for all orthogonal transfor- mations Q, the set {fo} } is an equivalence class of f in all embeddings (obtained by orthogonal transformation)..
4

---

Under review as a conference paper at ICLR 2023
The discussion above points out that the target function is aware of the embedding it works in. Intuitively, this is because the function contains some knowledge used to process the input sequence, and the knowledge depends on the embedding. Motivated by this point of view, propose to study functions which take the "knowledge" as an explicit input. Like the input sequence, the knowledge also consists of vectors in the embedding space, showing its embedding dependence. The knowledge is used to extract information from the input sequence. Concretely, we consider functions f: X' [d X taking two inputs, X E X and Rd with X being the original input sequence, and Z being the knowledge. With this additional knowledge input, the function f can be orthogonal equivariant- changing the embedding transforms X and simultaneously, and the true "meaning" of what f does is not changed. In other words, the equívalent class (Se) is parameterized by the knowledge input such that [(,
From now on, we study orthogonal equivariant functions with knowledge, whose definition is given below:
Definition 2. Let f X Baxk X be seq2xeq function with knowledge. For any Z & B is called orthogonal equivariant with knowledge 7 if for any X E X and orthogonal matrix Q E gdxd there is f(Qx, QZ) = Qf (x(x,))
As corollary of Proposition I we have the following proposition characterizing the formulation of functions satisfying Definition? 2
Proposition 2. Let Z Rd*k and f X Bdxk - X be function that is orthogonal equiv- ariant with knowledge Z. Then, there exist two functions 91 and 92 independent of Z, taking X 7T X, ZT Z inputs, and producing matrices with appropriate shapes outputs, such that for all X E X, we have
f(X,2) Xx Zgz (X Xx
(2)
Proof. Let X = [x, Z| (n- Viewed as function of X, f satisfies f(Qx) = Qf for any orthogonal matrix Q E Rddd Hence, by Proposition there exists a function g depending on X X, such that
-(x) x x
By the definition of X, can be written as a function of X X, 2 and 2² i.c. g(X²X) = g(x"x, xT, ZT ZTZ Z). Noticing that X has n + columns, 9 must have n + rows. Letting
91 XT g22(X"' X, 2' ]
9(xT x, 2T x, ZT
with 91 taking the first n rows and g2 taking the next & rows, we have
f(x,2) = X (x 2T x, nJ + Zge (x" x, 2T 2).
In practice the knowledge in a function f(X, Z) studied above can be treated as a parameter ma- trix learned during the training process. We note that the self-attention in equation [ takes a similar form. In the self-attention, the product of X with the attention matrix has the form Xg(2 (z "z' X), with Z [ W and g being the composition of quadratic function and softmax operation:
g(Y) = S. ( Y
[ 0 1 11)r)
dd
Indeed, similar our understanding of Z, the query and key parameters in the self-attention are usu- ally understood as knowledge of the language used to extract information from the input sequence. These parameters naturally embedding dependent. Certainly, the self-attention used in practice contains more components than merely a x9(2"X) form. For example, as shown in equation a linear transformation in the embedding space is applied by Wv, and residual connection is added. in Section 5 we discuss some practical considerations that may cause additional complication of the model in practice.
Coming back to the formulation 2 is understood as a parameter matrix, it is fixed after training. Then, among the three inputs of gi and f2, 7T Z is constant, and X X is an identity matrix under
5

---

Under review as a conference paper at ICLR 2023
one-hot embedding. Hence, Z"X is the most informative input. Moreover, since Z is a constant matrix, the linear combination of its columns, Zog(X"XX Z" X. 2" Z)Z) becomes less important than the linear combination of X's columns, Xgi (X X, Z" X, Z Z). Extracting the most meaningful parts in the formulation 2 we obtain a simpler form f(X, 7) = Xgi x). This coincides with what appears in the self- attenttnnn
3.3 FINITE INFORMATION AND THE REPRESENTATION OF COEIFICIENTS
In formulation 2 the simplified formulation f(X, Xg1 (2"X) the coefficient functions 91, 92 can be quite arbitrary. They can have very complicated dependence with their inputs. For example, for function f(X, Z) Xg( X) whose output has the same length the input, when X E IRdx,, we have gZ" X) E R In the most general case, can have a different formulation In - _Txx for each n. Because n can be arbitrarily large, the description of y requires infinite amount of information. However, if these functions can be described and implemented by machine learning models, they must contain only a finite amount of information. In other words, the functions cannot get infinitely complicated when the sizes of their inputs become large. In this section, based on this finite information principle, we discuss possible forms of the g's.
For the convenience of the discussion, we focus on the form f(X, Z) = Xg(Z"X) and assume that the output of has the same length as its input. Hence, for any input X E Rdxn, we have g(Z"X) E Rax". In this case, we put our discussion on under the following more specific statement of the finite information principle:
Assumption 1. (Finite information principle) g is represented by parameterized model with finite number of parameters not depending on
This assumption concerns only one aspect of the broader idea of "finite information". But is the only aspect that can quantify easily.
Now, we consider parameterized representations for g- Given Assumption T one of the sim- plest parameterizations is the composition of nonlinear function and quadratic forms, such as a (x* ZAZ" X) for some matrix A E _ To see this, denote Y = 2 X E R*** and consider g represented by composition of an elementwise nonlinear function and a sum of matrix products involving Y, i.e.
N
K2 II J=1
g(Y) =
Σ
.o W
(3)
where ÿ is either Y or YT, and N can be infinity. In the formulation above, W.j parameters. By the finite information principle, the dimensions of Wij in equation should not depend on n. Then, it easy show that we always have K; 2 in equation because terms with K; = 0 or 1 cannot have shape n X n without n-dependent parameter matrices. Hence, there is no constant or linear terms in the sum of matrix products, and thus the simplest terms are quadratic terms. In its simplest form, without higher order terms, we have g(Y) = oo for some W R in which case the output always has the shape n X n for any n. Note that the self-attention matrix used in practice is very close to this form. If Z is the concatenation of the query and key matrices, i.e.
0 I
Z = [WT. WX), then by taking
=
0
0
we have
x zAAT x"
The only difference is that the softmax operation is not elementwise.
A PERSPECTIVE FROM KERNELS
Another perspective create g with finite amount of information is from the kernels. Viewing the input Y E & as n vectors in R2, g maps the n vectors into an n x n matrix, characterizing the relations between these vectors. This naturally be achieved by kernel function K(.,)) R x R + IR. Denote = ,y,..., ynl. then we can let g(Y') = (K' (y;, )x)) When K is an inner product kernel K(x, y) = oxx" y), which is widely used traditional machine learning models such as the support vector machine, g takes a similar quadratic form (with an elementwise

---

Under review as a conference paper at ICLR 2023
nonlinearity) in the discussion above, i.c. g(Y) o(TT)). Besides, there more kernels to choose. For instance, a radio basis function (RBF) kernel [(x, y) = f([x y can produce y defined by ())(Y) f( yy These representations of coefficients may see benefits in some special applications. Actually, self-attention using kernels has already been studied in previous
works such as Rymarczyk et al. [2021) Chen et al. (021)
PERMUTATION EQUIVARIANCE FOR SEQUENCE ELEMENTS
in this section, we consider another symmetry- the permutation equivariance for the elements of the sequence. With this permutation equivariance, the form 2 can be further restricted. In seq2seq problem such as a language problem, though, the order of the input is usually important. Hence, permutation equivariance
the order of the sequence should not be expected. However, in practice some parts of the problems or models may have permutation equivariance. For example, when self- attention based models are used learn seq2seq problems. position encoding is usually added to the input sequence before fed into the model Vaswani et al. (2017). In this case, the order information included in the input sequence and the function implemented by the model can be permutation equivariant.
For any sequence E Rdd"" we call the length of X, denoted by ((X). We consider the following definition of permutation equivariance:
Definition 3. Let f X x Raxk + X be seq2seq function
senntseqfunction with knowledge. Assume 1(f(X, Z)) = I(X) always holds. For any 7 E Baakk
called elementwise permutation equivariant with knowledge Z for any permutation matrix P E (=((()x((X) we have f(XP, Z) = f(x, Z)
Based on the discussions in previous sections, we focus on functions with the form f(X, 2) Xg(Z"X) X). Given the additional permutation equivariance in Definition 3 we have the following proposition that further narrows down the form of the functions. The proof of the proposition given in Appendix B
Proposition 3. Let f be function with form f(X, Z) = Xg(Z"X), Assume is elementwise permutation equivariant with knowledge Z. Then, for any specific n, there exist functions PL, P2. 1/, 1h2, such that for any X E BRdxa with full column rank, we have
gu (= x) = pi 7,
Σ
(1 2))
k= I, Aeff
11, x) p2 (x(x xj; Z,
( Xi, Xj, 2))
k= K
jor = 1,2, n and # i. Here, gij are the (i, -th component function of g, i.e. = (axn)
Remark 3. For self-attention layer used in practice, Z = =Wo, Wx], in which case we have
T.
ER W
Using the form in Proposotion this g can be obtained by taking
>WWTWKK
v2(x: 2, = "w"WWWWe (x 2.
x x +
and taking
(x: y, ub,,,,,0, 2))
PRACTICAL CONSIDERATIONS
In previous sections, we revealed the natural forms seq2seq functions that satisfy specific sym- metries that reasonable for many practical problems. Therefore, the structures identified can
7

---

Under review as a conference paper at ICLR 2023
be taken into consideration when designing neural network models to learn these problems, as ap- proaches to improve the efficiency of learning. The self-attention, although designed without uti- lizing these connections between symmetries and structures, has structures that coincides with the forms we identified. This may partially explain the success self-attention hased models.
Usually, the models used in practice have be more complicated than that given by the theory, to address practical issues that are not caught in the simplified setting of the theory. For CNNs, for example, convolution layers are stacked extract features hierarchically, and normalization layers are added to help training. In the following, we discuss several considerations when the theories built in the previous sections are used in practical applications.
THE EVOLUTION OF EMBEDDINGS
In our analysis for orthogonal equivariant functions, we assume the output and the input of the func- tions are in the same embedding. In practice this might not be true. For example, for translation problem the input and the output sequences are two different languages, and hence they may not share embedding. In this case, need to implement mechanism to change the embedding of the output sequence. The simplest way is to apply an elementwise linear transformation to the output, i.e. for function f with form f(X, Z) = Xg(ZZ X), we can build new function f by multiplying a matrix on the left of the output of f:
f(x, Z, W) = WXg x).
(4)
more flexible way is to apply a general elementwise nonlinear transformation to the output, which be achieved for example by a two-layer neural network, as used in many self-attention based models:
2, = Vo(UXg(Z*x))
(5)
where U, V are parameter matrices, and a is an elementwise nonlinear activation function.
HIGHER CAPACITY
In the application of neural networks, higher capacity of the model is desired in many cases. Giving the model more flexibility compared to the theoretical formulation can help improve the performance of the model, as long as the flexibility does not impair the training efficiency. Based on the structures in equation or more flexibility can added the model by considering a "multihead" version of such functions. For example, multihead version for 4 with m heads can be
(x, 2,
Σ (x,
(6)
where .,...., Zm and W W are different matrices, and Z [Z,.... Zm W [W...., Wm]. and 91...., Im are different functions. This structure is similar to the multihead self-attention.
COMPOSITIONS AND HIERARCHICAL FEATURE EXTRACTION
A very successful way to increase the capacity of a model and improve the performance of learning is stack several modules compositionally to form deep model. A deep model with many layers can extract the information from its input hierarchically. This is the intuitive reason behind the success of deep neural networks. For sequence sequence applications, we can also stack structures like into a deep model. For example, model with T. layers can be
(0) = X;
Σ w (110 (000))000(((0)1)00)00000))) (((2 D
= -1,,,)=-k(0)
where Z and W include all 2:") and D parameters, respectively. This structure looks similar to the successful large language models used in practice. One difference that a residual link is added each layer of those models to help the training. Another difference is that elementwise fully connected layers are added after some self-attentions, which can be understood as stacking structures in equation 5
8

---

Under review as a conference paper at ICLR 2023
6 SUMMARY
In this paper, we study the representations of sequence-to-sequenee functions with certain symme- tries, and show that such functions have forms similar to the self-attention. Hence, self-attention seems to be the natural structure to learn many seq2seq problems. Moreover, except the inner prod- uct based attention mechanism widely used nowadays, our study reveals more possibilities that may be picked in the design of attention mechanisms, such as higher-order matrix products or the RBF kernels. These forms arise from the discussion on the finite information principle. As limitation, discussion the forms of in Section 3.3 started from simple general form 3 More gen- cral discussions and more precise characterizations of the finite information principle is left as an important future work.
REFERENCES
Brandon Anderson, Truong Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. Advances in neural information processing systems, 32, 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473, 2014.
Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning with geometric stability, arXiv preprint arXiv:2106.000 07144, 2021.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportu- nities and risks of foundation models. arXiv preprint arXiv:2108.0722 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot leamers. Advances in neural information processing systems, 33:1877-1901, 2020. 2020.
Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian kernel and nyström method. ArXiv, abs/21 11.0003, 2021.
Benjamin Chidester, Tianming Zhou, Minh Do, and Jian Ma. Rotation equivariant and invariant
neural networks for microscopy image analysis. Bioinformatics, 35(14)ii500-553) -537,, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04880, 2018.
Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models. In International Conference Machine Learning, pp. 2959-299999999 2969. PMLR, 2021.
Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se (3)-transformers: 3d roto- translation equivariant attention networks. Advances in Neural Information Processing Systems, 33:1970-1981, 2020.
Nicholas Guttenberg, Nathaniel Virgo, Olaf Witkowski, Hidetoshi Aoki, and Ryota Kanai. Permuration--qquivrrian neural networks applied to dynamics prediction. arXiv preprint arXiv:1612.04530.. 2016.
Jinpyo Kim, Wooekun Jung, Hyungmo Kim, and Jaejin Lee. Cyenn: A rotation invariant enn using polar mapping and cylindrical convolution layers. arXiv preprint arXiv:2007.10588 2020.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard Howard, Wayne Hub- bard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Newral computation, 144)5511-551, 1989.
Yunfei Li, Juntao Chang, Chen Kong, and Ziao Wang. Flow field reconstruction and prediction of the supersonic cascade channel based on a symmetry neural network under complex and variable conditions. AIP Advances, 10(6):065116 16, 2020a.

---

Under review as a conference paper at ICLR 2023
Zhiyuan Li, Yi Zhang, and Sanjeev Arora. Why convolutional nets more sample-efficient than fully-connected nets? arXiv preprint arXiv:2010.08515, 2020b.
Zhouhan Lin, Minwei Feng, Cicero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. A structured self-attentive sentence embedding. arXiv preprint arXiv: 2017.
Julia Ling, Reese Jones, and Jeremy Templeton. Machine learning strategies for systems with in- variance properties. Journal of Computational Physics, 318:22-35, 2016a.
Julia Ling, Andrew Kurzawski, and Jeremy Templeton. Reynolds averaged turbulence modelling using deep neural networks with embedded invariance. Journal of Fluid Mechanics, 807:155- 166, 2016b.
Di Luo, Giuseppe Carlco, Bryan K Clark, and James Stokes. Gauge equivariant neural networks for quantum lattice gauge theories. Physical review letters, 127(27):276402, 2021a.
Di Luo. Zhuo Chen, Kaiwen Hu, Zhizhen Zhao, Vera Mikyoung Hur, and Bryan K Clark. Gauge invariant autoregressive neural networks for quantum lattice models. arXiv preprint arXiv:2101.07243, 2021b.
Minh-Thang Luong, Hieu Pham, and Christopher D Manning. Effective approaches to attention- based neural machine translation. arXiv preprint arXiv:1508.0400 04025, 2015.
Marios Mattheakis, Pavlos Protopapas, David Sondak, Marco Di Giovanni, and Efthimios Kaxiras. Physical symmetries embedded in neural networks. arXiv preprint arXiv: (rXiv:/90400892) 2019.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. Conference on Learning Theory, pp. 3351-3418. PMLR, 2021.
Zhaoyang Niu, Guoqiang Zhong, and Hui Yu. A review on the attention mechanism of deep learning. Neurocomputing, 452:48-66 62, 2021.
Ankur Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit. decomposable attention model for natural language inference. arXiv preprint arXiv:1606.01990 2016.
Romain Paulus, Caiming Xiong, and Richard Socher. A deep reinforced model for abstractive summarization. arXiv preprint arXiv:1705.. 1705.04304, 2017.
Claudio Procesi. Lie groups: an approach through invariants and representations. Springer Science & Business Media, 2006.
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 computer vision and pattern recognition, pp. 652-662266666 660, 2017a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++:: Deep hierarchical fea- ture learning on point sets in a metric space. Advances in neural information processing systems, 30, 2017b.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res., 21 140):1667, 2020.
Jad Rahme, Samy Jelassi, Joan Bruna, and S Matthew Weinberg. A permutation-equuivrraat neural network architecture for auction design. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 5664-5672, 2021.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poezos. Equivariance through parameter- sharing. In International conference machine learning, pp. 2892-2901. PMIR, 2017.
Dawid Rymarczyk, Adriana Borowa, Jacek Tabor, and Bartosz Zieliński. Kernel self-attention for weakly- supervised image classification using deep multiple instance learning. 2021 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 1720-1729, 2021.
10

---

Under review as a conference paper at ICLR 2023
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural net- works. In International conference on machine learning, pp. 9323 9332. PMLR, 2021.
Kristof Schütt,, Oliver Unke, and Michael Gastegger. Equivariant message passing for the prediction of tensorial properties and molecular spectra. In International Conference on Machine Learning. pp. 9377-9388. PMLR, 2021.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. arXiv preprint
2018.
Muhammed Shuaibi, Adeesh Kolluru, Abhishek Das, Aditya Grover, Anuroop Sriram, Zachary Ulissi, and C Lawrence Zitmick. Rotation invariant graph neural networks using spin convolutions. arXiv preprini MXiv:22006009555. 2021.
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and translation-equivarine neural networks for 3d point clouds. arXiv preprint 100.v:/802.08222 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention you need. Advances in neural informa- fion processing systems, 30, 2017.
Tom Vieijra, Corneel Casert, Jannes Nys, Wesley De Neve, Jutho Haegeman, Jan Ryckebusch, and Frank Verstraete. Restricted boltzmann machines for quantum states with non-abelian or anyonic symmetries. Physical review letters, 124(9)097201,, 2020.
Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are universal: Equivariant machine learning, structured like classical physics. Advances in Neural Information Processing Systems, 34:28848-28888 2021.
Rui Wang, Karthik Kashinath, Mustafa Mustafa, Adrian Albert, and Rose Yu. Towards physics- informed deep learning for turbulent flow prediction. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1457-1466, 2020a.
Rui Wang, Robin Walters, and Rose Yu. Incorporating symmetry into deep dynamics models for improved generalization. arXiv preprint urXi::2002.03061 2020b.
Hermann Weyl. The classical groups: their invariants and representations. Number 1. Princeton university press, 1946.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Linfeng Zhang, Jiequn Han, Han Wang, Roberto Car, and EJPRL Weinan. Deep potential molecular dynamics: a scalable model with the accuracy of quantum mechanics. Physical review letters, 120(14) 2018
A PROOF OF PROPOSITION
Proof. Consider X [x1, X2,..., Xn) d X. We first show that the columns of s(X) lie in the span of X1,..., Xn. Without loss of generality, we assume f(X) has only one column, i.e. f(X) Rdd Let V span(X),...,x,,) X,,)- Then, there exist V and V+, such that f(X)= + u. Let Qu be the Householder transformation
2 | uu.
I-=--
Then, Qu is an orthogonal matrix. By its definition, we have Quu -,, and Qu w for any I. u, which implies Quo and Qux; = x; for all 1,2, .,.,... Since f is orthogonal equivariant, we have
= Qu)(X) Qu + u)
11

---

Under review as a conference paper at ICLR 2023
On the other hand, since Qu X, must have
[(QuX) = (XX)
Therefore, we have u 0, and f(X) VEV.
Next, we show that the coefficient of the linear combinations can be taken as orthogonal invariant functions. By the analysis above, there exists a function 9 of input X, such that
f(x) = XX()).
The size of g's output depends on X and f(X). Because f is orthogonal equivariant, for any orthogonal matrix Q E gaxd we have
QXg(QX) = f(Qx) = =
which means Xg(QX) = Xx(X). Obviously, we can choose g to satisfy g(QX) - g(X) for any orthogonal Q.
Finally, we invoke the first fundamental theorem of invariant theory for the orthogonal group Weyl 1946;;
Procesi 2006), which states that g only depends on X via X X. This completes the
proof.
B PROOF OF PROPOSITION 3
Proof. With an abuse notations, we use gXX, Z) to denote the output of g given inputs and Z, despite that g only depends on z"x. Since X has full column rank, we have Xt = I. Hence, g(X, Z) X f(X, 2). By Definition
3 for any permutation matrix P E gaxx, we have
9(XP,Z) Z) p = p PI
p 9X,
Therefore, applying any permutation X leads to the same permutation the rows and column of g(X, Z). Recall that the (i, entry of is given by the function gij. Denote the output of gi given input X and Z by g&j (Xi,..., Xn, Z). We then study the forms of gi using equation
First, consider a permutation Pie that swaps x and x, By equation 7 we have g(X Pi Z)11 = g(X, 2) which means
gii (XI, Xs, ... ,,,, Z) = 9 (x.,
Xn, Z).
Hence, all 9n can be generated by 911 with a swap permutation of its inputs. For 911, we apply permutation that is identity
the output of 9n1 does not change although the order of inputs is changed. This means 911 permutation invariant with the inputs X2...., X,- By Theorem Zaheer et al. (2017), viewed as a function of X2, ... Xa, 911 has the form p(En (xx)) for some functions P and w. Considering the inputs x₁ and Z, the functions p and v above depend on X1 and Z. Therefore, there exist functions P1 and th, such that
9n1 (X( Z) pI Z. Σ
1 (x4:x1 X1, 2))
By the relation between 911 and gii. we have
Iu gu Z) = (1 Z.
Σ (Xcs X,, Z)).
for any i 1......, n.
Next, we consider Piy with * j. Without loss of generality, assume < j. Let P1ç,2 be permutation that swaps X1 with x;, and X2 with xj. By the permutation equivariance, we have
gij (x1, X2, X., Xj.
Xn, Z) = (x,, Xj. .X,
X2, Xny Z),
which means any Piy with + j can be generated by 912- Focusing on J12, similar to the arguments for g11, it is easy show that ø12 permutation invariant with inputs X3, Xn. Therefore, there exist functions and viz such that
(12 Z) = p2(x1, X2, Z.
Ub x X1, X2, Z)).
3
12

---

Under review as a conference paper at ICLR 2023
Hence,
2x, p2(Xi, Xj, Z, Σ
(x X,, 2))
kti.
13


Reviews:
[{"review_id": "e0OMH4NKpYi", "reviewer": "Reviewer_KVpw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces and studies a class of functions called seq2seq function with knowledge, whose form is inspired by typical seq2seq learning problems . This new class of functions explains why  network structures similar to self-attention are the right structures to represent the target function of many seq2seq problems. The paper introduce several concrete illustration to verify the hypothesis proposed in this paper. ", "summary_of_the_review": "The idea present in the paper, i,e., the success of self-attention based language model, is because self-attention is close to “seq2seq function with knowledge”,  a function class that is guaranteed to be orthogonal equivariant is interesting and novel to me. \n\nHowever, I am concerned that there is no empirical evidence supporting the hypothesis proposed in the paper. I think, w.r.t. the content present in this paper, empirical evidence might be a valid justification supporting the hypothesis in the paper. ", "strength_and_weaknesses": "Strength:\nThe paper reveals that one possible reason behind the success of self-attention based language model, is because self-attention is close to “seq2seq function with knowledge”,  a function class that is guaranteed to be orthogonal equivariant. The paper shows that functions with such equivariance enjoy a representation which takes a similar but more general form as self-attention. This idea is fresh and novel to me. I enjoy the clear illustration of the math examples supporting the authors main idea much.  \n\nWeakness:\nHowever, I guess the main weakness of the paper is the lack of empirical study. The paper seems does not provide any empirical evidence supporting the hypothesis present in the paper. Take for example, is the seq2seq function with knowledge with equivariance performs better than the conventional self-attention? Is it possible to verify the superiority of the class of function with equivariance empirically? I sincerely appreciate it if authors may kindly comment on the missing empirical study during rebuttal. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "AVQZT4D2aEJ", "reviewer": "Reviewer_AZo2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the representations of seq2seq functions with certain symmetries, and show that such functions have forms similar to the self-attention. ", "summary_of_the_review": "This is a nice theoretical paper but lack of empirical study.", "strength_and_weaknesses": "The paper introduces an interesting idea that orthogonal equivariance in the embedding space is natural for seq2seq functions with knowledge, and under such quivariance the function must take the form close to the self-attention. It also gives a thorough derivation on the findings. I like this part.\n\nHowever, my main concern is that the paper is lack of empirical studies on the findings. For example, their theoretical study shows that there could be other design of self-attention, such as high-order matrix products or RBF kernels. It would be interesting to see some experimental results on these.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3QJucZCn5p", "reviewer": "Reviewer_KdaA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper showed that structures similar to self-attention are natural to learn many sequence-to-sequence problems from the perspective of symmetry. It studied the representations of sequence-to-sequence functions with certain symmetries, and showed that such functions have forms similar to the self-attention. Hence, self-attention seems to be the natural structure to learn many seq2seq problems. \n", "summary_of_the_review": "The paper showed that structures similar to self-attention are natural to learn many sequence-to-sequence problems from the perspective of symmetry. The main limitaitons lie in 1) theoretical justification; 2) experimental validations.", "strength_and_weaknesses": "Strength:\n\n+ Study the representations of sequence-to-sequence functions with certain symmetries, and show that such functions have forms similar to the self-attention. Hence, self-attention seems to be the natural structure to learn many seq2seq problems. \n\n+ Moreover, except the inner product based attention mechanism widely used nowadays, the paper revealed more possibilities that may be picked in the design of attention mechanisms, such as higher-order matrix products or the RBF kernels.\n\nWeaknesses:\n\n- The paper only provided pure theoretical analysis. Its real-world relevance should be justified through different Seq2Seq problems.\n\n- Many of the analysis and derivations seem to be not very straightfoward and loss connection to some extent. The paper provides the analysis of symmetry from orthogonal and permuation while there are lots of other possibility of symmetry.\n\n- The paper did not provide an in-depth discussions on the limitations.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject