Approximation Rate of the Transformer Architecture for Sequence Modeling
Authors: Haotian Jiang
Qianxiao Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Approximation theory
Transformer
Sequence Modeling
Primary area: learning_theory

Abstract: The Transformer architecture is widely applied in sequence modeling applications, yet the theoretical understanding of its working principles remains limited. In this work, we investigate the approximation rate for single-layer Transformers with one head. We consider general non-linear relationships and identify a novel notion of complexity measures to establish an explicit Jackson-type approximation rate estimate for the Transformer. This rate reveals the structural properties of the Transformer and suggests the types of sequential relationships it is best suited for approximating. In particular, the results on approximation rates enable us to concretely analyze the differences between the Transformer and classical sequence modeling methods, such as recurrent neural networks.

Approximation Rate of the Transformer Architecture for Sequence Modeling
Haotian Jiang haotian. haotian.jianggenreaeeeee hta.rim....aanaeraarrrat......
Qianxiao Li *f qianxiao@mus edu.
Abstract
The Transformer architecture is widely applied in sequence modeling upplications, yet the theoretical understanding of its working principles remains limited. In this work, we investigate the approximation rate results for the Transformer ar- chitectures general sequence to sequence target relationships. We begin by establishing a representation theorem for the target space and introduce a novel notion of complexity measures to construct approximation spaces. These measures encapsulate both pairwise and pointwise interactions among input tokens. Based on this framework, derive an explicit Jackson-type approximation rate estimate for the Transformer. This rate sheds light on the underlying structural characteristics of the Transformer, thereby delineating the types of sequential relationships they excel in approximating. Notably, our findings on approximation rates facilitate a concrete comparison between the Transformer and traditional sequence modeling approaches, such as recurrent neural networks.
Introduction
The Transformer architecture, as introduced by Vaswani et al. 30 has become immensely popular in the field of sequence modeling. Variants such BERT 8 and GPT (6] have achieved excel- lent performance, becoming the default choices for natural language processing (NIP) problems. Concurrently, Dosovitskiy et al. [11] successfully applied the Transformer to image classification problems by flatteming the image into sequence of patches. Despite its success across various fields of practical application, many theoretical questions remain unanswered. Among these, we focus on two essential questions in this work: firstly, the approximation rate of the Transformer on sequence modeling: secondly, the comparative advantages and disadvantages of the Transformer with recurrent neural networks (RNNs) on different temporal structures.
The concept of Jackson-type approximation rates is derived from the Jackson Theorem for poly- nomials [15]. and is further elaborated the work of DeVore [ for addressing general forward approximation problems. To illustrate this, consider classic polynomial approximation. It involves defining an appropriate approximation space, accompanied by specific complexity measures, precisely the Sobolev space. According to the Jackson theorem, function with small Sobolev norm be efficiently approximated by polynomial. We aim to establish similar approximation rate results for the Transformer. This identifies the type of targets that the Transformer can efficiently learn. We target relationships, extending the linear target
examine general non-linear sequence-to-sequenee form explored in previous studies of the approximation results for linear RNNs and linear temporal convolution networks [24] [6]. We introduce novel notion of complexity, establishing a concrete target space from which approximation rates can be deduced. This enables us identify the types of sequential relationships that Transformer can approximate efficiently. Based on our theoretical analysis, we identify concrete classes of temporal structures where the Transformer outperforms
"CNRS@ CREATE LTD, 1 Create Way, #08-01 CREATE Tower, Singapore 138602 Department of Mathematics, Institute for Functional Intelligent Materials, National University of Singapore
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the RNNs and vice versa. Our main contributions are summarized as follows: 1. We develop Jackson-type approximation rate results for single-layer Transformer networks with one attention head. Our analysis reveals that the approximation capacity is governed by a low-rank structure within the pairwise coupling of the target's is temporal features. Empirical validation confirms that the findings observed under theoretical settings also hold true in practical applications. 2. We conduct a comparative analysis between the Transformer and RNNs, aiming to identify specific types of temporal structures where one model excels or underperforms compared to the other.
2 Related work
We first review the approximation results of Transformer networks. The universal approximation property (UAP) of the Transformer architecture is first proved in Yun et al. (33,, which further extended to Transformers with sparse attention matrices 34 The above universal results are developed for a deep Transformer structure. In contrast, Kajitsuka & Sato 17 applying a similar technique to prove one layer Transformers can achieve UAP by increasing the width. Additionally, Kratsios al. [19], Edelman et al. [12]. Luo al. [25] considers the UAP of the Transformer in various different settings, Giannou et al. B3 considers a special setting regarding expressiveness, demonstrating that Transformers can represent any computer program. Beyond the UAP results, there have been developments in specific approximation rate results. Gurevych et al. [14) demonstrated the rate of the misclassification probability by considering the approximation of hierarchical composition functions, which are composed of sparse functions. This rate takes into account both the level of composition and the smoothness of the component functions. Bai et al. [ and Wang target relationships with certain special structures. Additionally, Takakura & Suzuki 29 developed approximation rates for function space consisting of lennth sequence-to sequence-to-sequeee --suueencee functions, which is characterized by the smoothness of the functions. Our approximation rate result steps further by considering temporal structures, shedding light on how the Transformer model handles temporal relationships. Apart from the approximation results, numerous intrinsic properties of the Transformer have been investigated. Dong et al. [10 and Bhojanapalli et al. [4] considers the rank structure of the attention matrices. Levine al. 20 examine the correlation between the dependency of input variables and the depth of the model. The Transformer is a very flexible architecture, such that a special configuration of parameters can emulate other architectures. For example, Cordonnier et al. 77). Li et al. (21) showed that attention layers under certain assumptions can perform convolution operations. However, not all emulations Transformer. In this context, definitions of complexity measures and the resulting Jackson-tys -tppe approximation rate estimates provide more insight into the inner workings of the architecture. This the focus of the current work.
31 explore
valid explanations of the working principles of the
3 Sequence modeling as an approximation problem
We first motivate the thcoretical settings of Jackson-type approximation rate results by considering classic polynomial approximation. Then, we formulate the Transformer as an instance of such an approximation problem.
Motivation of Jackson-type Approximation Rates Consider two normed vector spaces, X' and ), designated as the input and output spaces, respectively. We define the target space C C y as a set of mappings from X' to y that aim to approximate with simpler functions. The hypothesis space is denoted by H. = U.n H(m),, where ((")) represents sequence of hypothesis spaces. Here, denotes the complexity or the approximation budget of these spaces. Hypothesis space H encompasses the candidate functions used to approximate targets in C. Let be constant, introduce complexity measure, denoted as ((a) C + R.P based on the structure of H. The complexity measure is used to construct an approximation space C(a) = {H E C: C(a) (H) < oo). which is usually dense in C. Then for any H E Cla), the Jackson-type approximation rate is expressed as follows:
inf ()
H All < E(Clo) ((C())(H))) m))
(1)
Here, the error bound E). decreases to zero m approaches infinity, and the rate of decay is usually called the approximation rate. In this context, g(a) (H) quantifies the complexity of target

---

H when approximated using H. A smaller value indicates that the target H can be more efficiently approximated with candidates from H. Consequently, the complexity measure discerns the types of targets that can be efficiently approximated within the given hypothesis space. Notably, different hypothesis spaces typically give rise to different complexity measures and approximation spaces. These variations characterize the approximation capabilities of the hypothesis spaces themselves.
Defining an appropriate approximation space ((a) is essential. Without specific structures, the general target space C does not provide any rate results. Opting for an approximation space with defined structures allows for the derivation of approximation rates. Morcover, the property that ((a) is dense in C. ensures that the restriction to ((a) is not overly limiting, preserving the necessary expressiveness of the space. To illustrate these concepts, we consider polynomial approximation over the interval [0, 1]. In this case we set X' [0. 1] and y = R. The target space C C([O, 1]) is the set of continuous functions defined on [0, 1]. The hypothesis space comprises all polynomials, expressed as follows:
H =
U H(m) mEN
U mEN
H(x)
Σ
a ag RR
According to the Jackson theorem for [15) the Sobolev norm serves as appropriate complexity measure, defined as (ka) (H) = =ax,=1...a |l Let C(a) be the approximation space contain- ing targets with finite complexity measures. Consequently, for H E C(*), we have the following approximate rate:
inf || -1 fEE
<
Ca C(H). m
Here, is a constant depending only on a. This theorem implies that smooth functions with small Sobolev norms can efficiently approximated by polynomials. Developing Jackson-type approximation rates for various sequence modeling hypothesis spaces is crucial for understanding their differences. Jackson-type results for RNNs, CNNs, and encoder-decoder hypothesis spaces have been established in Li et al. (24] Jiang et al. [16]. Li et al. [23], where complexity measures such as decaying memory and sparsity were found to influence the approximation rates. In Section 4. we identify appropriate complexity measures regarding the Transformer and develop corresponding approximation rates. This enables us to discern the essential structures that facilitate efficient approximation using the Transformer. Furthermore, it allows us to understand how and when the Transformer architecture differs from traditional sequence modeling architecture RNNs, which we will discuss in 6
Formulation Sequence Modeling as Approximation Problems In sequence modeling, we seek to learn relationships between two sequences æ and y. Mathematically, we consider an input sequence space
x= a (s) E [o, 1jd, for all s E [r]]-
Here, [T] := 7 and r denotes the maximum length of the input, and we focus on the finite setting, where 7 < Corresponding each input E X' is an output sequence y belonging
y = {y: : y(s) E R, for all s E [r]}-
We use H (H.). to denote the mapping between ær and y. such that v(() He( for each t E [r]. Define )( to denote the space of continuous mappings between the input and output space. We may regard each H₁ [0, 1]dxr - IR as a r-variable function, where each variable is a vector [0, 1]d Next, we define the Transformer hypothesis space.
The Transformer Hypothesis Space. We consider the following Transformer block retaining most of the important components.
H F
Σ
Weh(s))
where h = fo o x and F: m. + R, f: Rd 12 are two feed-forward networks. The parameter matrices have dimension Wo, WK E R.m Xn, Wy E mmm.x. The softmax function denoted as exp(p(t.s))
or, such that ppt( ()ss) = E, exple(t..) We focus on a simplified architecture: single-layer
3

---

Transformer with one head. In this work, layer normalization and residual connections are not taken into account. While this constitutes a simplified setting intended for theoretical analysis, it's worth noting that the phenomena observed under the theoretical settings also hold true in practical applications, as we have demonstrated Section [ The approximation budget of the Transformer depends on several components. We use f((mer to denote the class of feed-forward networks used in the Transformer with budget mpF, which is usually determined by the number of neurons and layers. Let m (n, m,; Ma, mpF) denote the overall approximation budget. We use H(m) to denote the Transformer with complexity m. Then, we define the Transformer hypothesis space by
H Hm), m
H( =
{ f ft satisfies Equation
5 with m }
(6)
4 Approximation results
Following the motivation of approximation problems for sequence modeling as discussed in Section 3 this section discusses the approximation rate results for the Transformer. Firstly, we introduce notion of the permutation equivariance property of the Transformer and discuss the role of position encodings in eliminating it. Next, we define the target space and present the corresponding repre- sentation theorem. We then establish the complexity measures necessary to form the approximation space. Our main result Theorem 4.2 presents the approximation rate results.
Permutation Equivariance and Position Encodings Our objective is to approximate target relationship H where each H belongs to C().)). It is important to note that without specific modifications, the Transformer inherently cannot approximate such targets due its permutation equivariance properties. This property implies that permuting the temporal indices of the input sequence results in a corresponding permutation of the output sequence. More precisely, if p denotes a bijection on [r] representing a permutation of T objects, a sequence of functions H is considered permutation equivariant if for all bijections p and inputs
X, the condition H (x
H (x) op holds. The Transformer Á within the hypothesis space indeed permutation equivariant (refer to Appendix for details). Directly applying the Transformer, therefore, yields permutation equivariant hypotheses, which are inadequate for approximating general sequential relationships that lack this symmetry. In practical applications, incorporating position encodings is widely adopted approach to counteract permutation equivariance (30]. Various methods exist for embedding positional information. The simplest approach is fixed encoding, which involves mapping xr() to a higher-dimensional space and then offsetting each sr() by distinct distances. Formally, with A E TR xd where d' 2 dl and constant or trainable e(t) E Rdd,, position encodings can be expressed as xtt) + A (t) + e(t). For general purposes, it's sufficient for the encoded input space ((FF to satisfy the following condition:
x x (ss) E I()) C CR, where (+) ((1) are disjoint, compact Vi.j E [r]}.
(7)
This ensures that for each input x = (z(1),.... I(T)), all tokens x1) and x(i) are distinct, meaning no two input sequences are temporal permutations of each other. Define the set I = UI, be the range of the inputs. Moving forward, we assume that position encoding has been applied, allowing us to consider (E) as the input space. Consequently, we define the target space to be C = ((x()))))))))) ))), which denotes the space of continuous mappings between (E) and y.
4.1 Jackson-type approximation rate
To derive the Jackson-type approximation rate, it is necessary first define the complexity measures to form an approximation space so that approximation rates can be obtained. We begin with the following representation theorem for the target space.
Representation of the target space C Given that the Transformer inherently captures both pair- wise and pointwise relations among input tokens through attention and feed-forward components, respectively, we are motivated to establish the following representation theorem for the target space C. This theorem demonstrates that every target can be exactly expressed in terms of pairwise and pointwise relations.

---

Theorem 4.1 (Representation of the target space), Consider d-dimensional, length input space X(E) with position encoding added. Then, for any H E C(X(E) there exists continuous functions F E C( 1]", R), f [0,, and p C(I I, R) such that for all E [T] we have
H₂(x) = (Eo Eololat,,,()MM)(ff
(8)
where n = 2rd + 1 and a is the softmax function. The proof is presented in Appendix A.2
We refer to P as the temporal coupling component and F and the element-wise components. It's important to note that the functions F, f. and may not be uniquely determined. In Appendix B.I] we explore certain invariant properties associated with Equation 8 Additionally, we provide illustrative examples in Appendix [B.I where the target explicitly conforms to Equation (8) Leveraging this representation theorem, we define the following complexity measures for targets H. E C.
Temporal Coupling Component Now, we discuss the complexity measures associated with the temporal coupling term p(u, v) that is central to understanding the attention mechanism in the Transformer. We employ the proper orthogonal decomposition (POD) [3] to decompose the temporal coupling of p. This approach can be viewed as an extension of matrix singular value decomposition (SVD) to functions of two variables. We have the following decomposition: p(u, v) Σk=1 & (u) (v), where ΦR, th are orthonormal bases for (Z), and the singular values 0g 2 are arranged in descending order. The bases th and t/x are of optimal choices, ensuring that p(u, v) satisfies:
inf lle(u, v) p(u-p(u v),, Σ O (r
analogous to the Eckart- Young theorem for matrices, with the rank defined as the number of terms in the POD decomposition. This implies that the approximation quality of p(u, v) can be measured by the decay rate of its singular values. This motivates our following definition of complexity measure
regarding p. Let > 1/2 be a constant, and {a. be singular values of p under POD. We define the complexity measure of H by
c (H)
inf inf { c: ol0) F.f.p
(o:o! S es "assa,,s''
,,,2211
(10)
where the first infimum is taken over all F, f. such that Equation ( holds. In particular, CL (H) oo it has a representation the form ( with p having fast decaying singular values.
<
Element-wise Component Now, we introduce the complexity measure for approximating the element- -iie components F and f. Let F(mer) be hypothesis space comprising feed-forward neural networks with a budget of mFF, representing parameters such as width or depth. We assume the existence of [ >> 0 such that:
c( (f) mFF 9
inf feFompp)
|-
f
(11)
Here, OpF represents a complexity measure of f corresponding to its approximation by F(mre), It is essential to emphasize that we are assuming the existence of pre-existing approximation rate results for the feed-forward component. For instance, in Barron [2]. F(mor) is considered to be one-layer neural networks with sigmoidal activation, where MFF corresponds the width of the network. By adopting this result, we have 3 = 1/2 and c( (f) is a moment of the Fourier transform of f. For shallow ReLU networks commonly used in Transformers, Klusowski & Barron [18] demonstrate
3 = 1/2 + 1/n, where n is the input dimension of the neural network. We maintain the generality of Equation (TT). This enables us to substitute any other relevant estimates from the mentioned references. This flexibility allows for broader application of the complexity measure in different scenarios and settings. Next, we proceed to define the complexity measure for H = H. This measure considers all the components that need to be approximated using the feed-forward network.
( (H,
inf (())) (F)) + F.J.p
(3) FF (f) + C1P) (p, k))
(12)
5

---

where C -x (CFP (P(()))
CPP (vb)) considers the approximation of the approximation of the POD bases @ and vi for the target function p Notably, this complexity measure dependent on parameter k. which determines the number of bases want to consider in the approximation of p. Finally, we define a complexity measure considering the norm of the target.
Co(H)
inf KF llo (sup llvi + l1obllbe):1
(13)
F.S.p
where Ky is the Lipschitz constant of F and Φs. th are POD bases of p.
Approximation Rates
Combining the complexity measures Equations (10) and (33) and Equa-
tion (12) discussed above, we define the approximation spaces. which consists of targets that have finite complexity measures:
cla.²) = [H EC: :
( (H, < <0, 22 1}.
(14)
One can understand this as an analog of the classical Sobolev spaces for polynomial approximation but adapted to the Transformer hypothesis space. Note that C(a.9) is also dense in general continuous
target space (F) ,)) when sufficiently large (See Appendix A.2) We are now ready to present the main result of this paper.
Theorem 4.2 (Jackson-tyse approximation rates for the Transformer). Consider sequences with fixed length т. Suppose the target H E ((a.3) has reprexentation in the form Equation with F E C((0, 11" .R) and f E C(I, [0, 1J").. ). Let the hidden dimension of the Transformer be n = 2* * mhh + Myy with my 2 n'. Then, we have:
inf AEHim)
/ Σ
T
Hx(x)) - Hx) dx S (C((H)
9 (0)
(H) mA 2a-1
cl (H,,)) (mm))++)
mpFF
where m (n. my. mpF) is the approximation budget, and Co. ciaa cl are complexity measures of H defined in (13) 100 and (12. respectively. The proof presented Appendix
Here, my denotes the hidden dimension of the attention mechanism, essentially the size of the query and key vectors, while mFF represents the complexity measure of the pointwise feed-forward network employed in the Transformer. We first consider how the attention mechanism ((x((), (()) approximates the temporal coupling term p. By setting [Wo]x- = es and [WK]s- = +x we can write á into p(x(t),x(s) = (Wof(x(t))) (x((s(s) = D Óx (=((())((()())) where ς2, thz I R for l [ma] are components of f and are represented by the feed-forward network. This suggests that the approximation of p by ý is a low-rank approximation as discussed in Equation ( When we increase m,, the first term in the error decomposition decreases since there are more basis functions included. However, in scenarios where MFF remains unchanged, the second term in the error bound will increase. It is important to highlight that this error increment pertains only to the error bound, not to the best approximation error, which does not necessarily become worse when increasing the approximation budget. When my increases, there are more basis functions that need to be approximated by the foed-forward components; thus, the error bound converges when both my no and m / 8+1 a synthetic example to illustrate the above discussion.
that considers the POD
co. In Appendix B.2 we provide
The complexity measure C2(-) accounts for the quality of approximation using feed-forward networks. On the other hand, C-(-) is the most interesting part, which concerns the internal structure of the attention mechanism. It tells us that if target can be written in form (8) with p(u, v), then it can be efficiently upproximated with small m, if p(u, v) has fast decaying singular values. This decay condition can be understood as effectively a low-rank condition on (u, v) + p(u, v), analogous to the familiar concept for low-rank approximations of matrices. These observations provide important insights into the structure, bias, and limitations of the Transformer.
5 Numerical Demonstrations
In this section, we present numerical examples to demonstrate our approximation rate results. We begin with synthetic examples, where we can specify the singular value decay patterns, thus validating

---

the Jackson-type approximation rates in Theorem 4.2 Then, we turn to a practical example involving Vision Transformer (ViT) model applied to the CIFARIO dataset, where we do not have direct access to the singular values. We will discuss methods to estimate the singular value decaying pattern.
5.1 Practical Example
We next analyze a practical example, focusing on the Vision Transformer (ViT) model with the CIFARIO dataset. In this scenario, we do have direct access to the temporal coupling term p of the target relationship. However, we demonstrate that as we train a sequence of models with increasing attention dimension my, the singular values of converges, implying the decaying pattern of p. Our first step is to estimate the rank of ý from sampled data. Subsequently, we examine the singular value decay pattern, and the error changes when altering the attention head size m,-
Error
0.3
mh
0.18
Error
Fitted
2.0
0.2
1.5
50
55
64
0.5
0.0
0.0
5
10
k
40
(a) Estimated singular values
(b) Singular values for different
(c) Training Errors
m/
Figure I: (a) is the estimated singular value of the attention matrix over a set of inputs for my = 64. The violin plot shows the distribution of each singular value. (b) plots the estimated singular values for models with different my. (c) plots the training error against my.
Given a trained model, it hard to directly compute the rank of p(u, v). Instead, we examine the attention matrix p(x) TR where [p(z))r, = p(z(t), zs)).. This is essentially a sample from p. By analyzing the rank of these sampled matrices, we can estimate the rank of ý. According to Braun [5), the singular values of the matrix p(x) exhibit the same decay pattern as those of p(u,9) v). Consequently, we can approximate the singular values of p(u, v) by averaging the singular values of p(x)) across various inputs. In Figure ((a). we numerically estimate the singular values of I in the ViT-B_16 model []]. We observe that singular values tend to be more concentrated, suggesting that can effectively estimate the rank of p(u, v) by evaluating it at sampled inputs.
Estimate the Rank
We next estimate the singular value decaying pattern of the temporal coupling term p in the target. In Figure [(b) we analyze the singular values of the Å for ViT models with varying values my. We estimate the singular values by averaging over a set of inputs. We observe that as my increases and reaches a sufficiently large value, the decaying pattern of the singular values starts converge. As an example, Figure models with different my. This convergence suggests that the rank of the attention matrix becomes representative of the actual rank of in the target. Consequently, it suggests the presence of low-rank structure real-world datasets. In Figure [[c) we plot the training error as an estimation of the approximation error. The plot reveals that the error decreases ma increases, following power law decaying pattern (1 0.27), This indicates that the target indeed exhibits a low-rank structure, and the pattern of error decay aligns with our approximation rate presented in Theorem 4.2 This illustrates that while our theorem is formulated based on a simplified scenario, the phenomenon of low rank is also observable in real-world datasets and models.
the estimated singular values for the first head of the last layer for
6 Comparison with RNN
Based on the approximation results in Theorem 4.2 this section presents comparison between the Transformer and RNN. Our comparison centers on how each model is affected by the alterations in the temporal structures of sequential relationships. We primarily investigate two distinct temporal
7

---

structures: temporal ordering and temporal mixing, as they have varying impacts on the performance of each architecture. Our approach involves manipulating the temporal structures within the sequential relationships and evaluating how each architecture is affected by these changes. Proof are presented in Appendix D.2 and Appendix D.3
6.1 Temporal Ordering Structure
We first analyze how the Transformer and RNN handle the change in temporal ordering of the sequential relationship. Empirically, is observed that in certain contexts, the ordering of inputs does not significantly impact the relationships. For instance, in NLP applications, altering the word order sentence often does not drastically change meaning. Similarly, in the ViT model, the arrangement of image patches typically does not substantially affect the outcome. However, in specific applications such as time series analysis, temporal ordering plays crucial role, as the target relationships are governed by the ordering of the sequence. To alter the temporal order of target H, we apply fixed permutation and define the new target as H, (1 p) Hz( This permutes the input but keeps the output unchanged, resulting a change to the temporal ordering.
We start by considering the RNN, which is affected by the change in temporal ordering. As demon- strated in Li et al. [22]. a linear RNN is represented by the form Hx(x) Σ. Uri(t s). When we employ to approximate linear targets represented by (x = E p(s)x(t - s), the complexity measures of the RNN CRNN (H) is determined by both decay speed and magnitude of p(s). We use CRNN to denote the approximation space for the RNN. (See Appendix D.I). We next show that the RNN is affected by the change in temporal ordering.
Proposition 6.1. Let H E CRNN and be a fixed permutation, such that there exists I' with p(t') > V. Suppose H is defined by Hy(æ o p) = Hx) Then H & CRNN-
This proposition shows that the altered target H no longer belongs to the approximation space for RNN. This lies in the fact that RNN can only handle causal targets, where y(t) does not depend on future inputs. However, the permuted target z is no longer causal, making the RNN incapable of learning such relationships. We next show that the Transformer, in contrast, remains unaffected by changes in temporal ordering.
Proposition 6.2. Let H E Cla.3) and p be a fixed permutation. Suppose H defined by Hx( = H.).).. Then H have same complexity measures with H for the complexity measures Co, Ci, C2 defined in Equation (13 and
This proposition shows that the altered target H maintains the same complexity measures as the original target. This observation implies that the Transformer's 's approximation capability is not affected by alterations in temporal ordering. This point is further substantiated by our testing of the Transformer on real-world datasets, as illustrated in Table I We consider the ViT model on the CIFAR10 10 dataset and the base Transformer structure 30 the WMT2014 English-German dataset. To alter the temporal ordering of the target relationship, we fix a permutation of indices denoted as p and apply all inputs while keeping the output unchanged. The experimental results provide evidence that the performance of the Transformer is unaffected by the temporal ordering of the target relationships.
CIFARIO (Ace.)
ENG-DE (BLUE)
Original Altered
0.98
26.85
0.96
25.91
Table 1: Numerical results of the Transformer on original and altered targets. The altered target is constructed by permuting the entire input dataset while keeping the output unchanged.
6.2 Temporal Mixing Structure
In this section, we explore how mixing elements from different time indices can affect the performance of the Transformer and RNN. Temporal mixing refers to the idea of blending information from various time indices, often through operations like convolution, which can alter the temporal structure. To
8

---

illustrate. consider linear relationship represented as (x) = E. P(s)art - s). Now, imagine we apply weighted sum of the input sequence x using a filter & to get an altered input. We denote this operation as ã = * æ, where (0 * ]t] = E 8(s)z(t + 8). This mixes the information in the sequence from different time indices. In this case, we define the altered target as Hx(x) = H2 * x) E. ((s))((t s), where أ 0 * p is the altered kernel (See Appendix D.3 This scenario often arises in signal processing and data amalysis. For example, when dealing with a noisy input signal æ, one capproach is apply moving average filter smooth it out. This filtering process involves mixing information from different time indices, which can significantly affect the behavior of target relationships. In the following sections, we will explore how such temporal mixing affects the temporal structures in sequential relationships. We begin by examining the linear RNN.
Proposition 6.3. Let H E CRAN associated with representation p. such that (p(s)] S e $ for some O. Let 0 be a length I filter such that [|0]], < 1. Suppose H is defined by H,(x)) H, * v)). Then we have both CRNN(H) S y and CRNN H) S 7, where CRNN is the complexity measure of the RNN (See Equation (75)
This proposition shows that under temporal mixing f with certain conditions, the complexity measure of the altered target H does not worsen. As result, the performance of the RNN is unaffected in such cases. However, performance of the Transformer can be impacted by temporal mixing in the target relationship. Consider H E Cla.3) and an altered target (x))) = H. * x)). This alteration can affect the complexity measures for i and أ in H. In Appendix D.3 we present an example where the rank of ý increases compared to p. leading to a performance drop in the Transformer. Numerical results in Table I also indicate that temporal mixing influences the Transformer's 's approximation capability. Preprocessing the input to mitigate this temporal mixing could potentially enhance performance, we leave this as future direction. The following numerical examples demonstrate the above discussions. We conduct numerical experiments to substantiate the discussions above. These experiments focus on a linear target relationship defined as Hx(x)) = Σ, e e=*xtt -t) s). To manipulate the temporal ordering, we apply permute the function e e Additionally, for introducing temporal mixing, the input is convolved with randomly generated filter. Both the RNN and the Transformer are employed to learn these targets. Detailed experimental settings are discussed in the Appendix C The results are presented in Table [ The bold font indicates a performance drop in the architecture under the corresponding modification of temporal structures. It is observed that the performance of the Transformer remains unaffected by changes in the temporal ordering structure; however, is impacted by temporal mixing. In contrast, the RNN exhibits opposite behaviors. This highlights that neither architecture consistently outperforms the other, they each adapt to different types of temporal structures.
Temporal Ordering Trans.
Temporal Mixing Trans.
RNN
RNN
Original
1.02e-7
2.18
1.02e-7 2.18e-5
Altered
3.57e-2
2.51e-5
1.58677
2.39e-4
Table 2: The table presents the MSE values for both RNN and the Transformer under different alterations of temporal structures.
7 Conclusion
In this paper, we have developed Jackson-type approximation rates for the Transformer in simplified setting. An important outcome of our work is the identification of complexity measures and approx- imation space defined in Equation (14). This, in turn, enables us to derive explicit Jackson-type approximation rate results in Theorem 4.2 Our rate results suggest that the Transformer performs well when the temporal coupling of the target exhibits a low-rank pattern. The experiments presented in Section 5 showcase the existence of low-rank patterns in real-world applications. Furthermore, the comparisons with RNNs underscore the specific temporal structures that each model handles efficiently. Future research directions involve extending the analysis to multi-headed attention and deeper Transformers. Additionally, we aim to investigate the potential benefits of removing temporal mixing in the input to enhance the performance of the Transformer.
9

---

Acknowledgement
This research is part of the programme DesCartes and supported by the National Research Founda- tion, Prime Minister's ' Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. QL acknowledges support by the National Research Foundation, Singapore, under the NRF fellowship (project No. NRF-NRFFI M--XFFF13-022-0003
References
[1] Bai, Y., Chen, F,, Wang, H.,, Xiong. C., and Mei. S. Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection, July 2023.
[2] Barron, A. R. Approximation and estimation bounds for artificial neural networks. Machine Learning, 14(1):115-133, January 1994, ISSN 1573-0565, doi: 10. 144100//9000999144
[3] Berkooz, G., Holmes, P., and Lumley, L. The Proper Orthogonal Decomposition in the Analysis of Turbulent Flows. Annual Review of Fluid Mechanics, 25(1):539-5733 1993. doi: 10.1 2tt.:aammrre...2250119......00
[4] Bhojanapalli, S., Yun, C., Rawat, A. S., Reddi, J., and Kumar, Low-Rank Bottleneck in Multi-head Attention Models, February 2020.
[5] Braun, M. Spectral properties of the kernel matrix and their relation to kernel methods in machine learning. 2005.
[6] Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A..
Shyam, P., Sastry, G., Askell, A.. Agarwal. S., Herbert- Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E.. Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language Models are Few-Shot Learners, July 2020.
[7] Cordonnier, J.-B., Loukas, A., and Jaggi, M. On the Relationship between Self-Attention and Convolutional Layers. In 11Xiv:1911.0333 [Cs, Stat], January 2020.
[8] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.
[cs], May 2019.
[9] DeVore, R. A. Nonlinear approximation. Acta Numerica, 7:51-150, January 1998. ISSN 1474-0508, 0962-4929, doi: 10. 1010017/009229999000331
[10] Dong, Y., Cordonnier, J.-B., and Loukas, A. Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth. arXiv:2 003.03404 [cs], March 2021.
[11] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani,
M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An Image is Worth
16x16 Words: Transformers for Image Recognition Scale. In International Conference Learning Representations, September 2020.
[12] Edelman, B. L., Goel, S., Kakade, S., and Zhang, C. Inductive Biases and Variable Creation in Self-Attention Mechanisms, June 2022.
[13] Giannou. A.. Rajput, S., Sohn, J.-Y., Lee, K., Lee, J. D., and Papailiopoulos, D. Looped
Transformers as Programmable Computers. In Proceedings of the 40th International Conference on Machine Learning, pp. 11398-1 1442. PMLR, July 2023.
[14] Gurevych, I., Kohler, M., and Sahin, G. G. On the rate of convergence of classifier based Transformer encoder, November 2021.
[15] Jackson, D. The Theory of Approximation. American Mathematical Soc., December 1930. ISBN 978-0-8218-3892-1.
[16] Jiang, H., Li, Z.., and Li, Q. Approximation Theory of Convolutional Architectures for Time Series Modelling. In Proceedings of the 38th International Conference on Machine Learning, pp. 4961-4970. PMLR, July 2021.
10

---

[17] Kajitsuka, T. and Sato, I. Are Transformers with One Layer Self- Aeff-Attention Using Low-Rank Weight Matrices Universal Approximators?. July 2023.
[18]
Klusowski, J. M. and Barron, A. Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with $ 'ell'1 $ and S 'ell'O S Controls, May 2018.
[19] Kratsios, A., Zamanlooy, B., Liu, T., and Dokmanić, Universal Approximation Under Constraints is Possible with Transformers, February 2022.
[20] Levine, Y., Wies, N., Sharir, O., Bata, H., and Shashua. A. Limits to Depth Efficiencies of Self-Attention. In Advances Neural Information Processing Systems, volume 33, pp. 22640-22651. Curran Associates, Inc., 2020.
[21] Li, S., Chen, X., He, D., and Hsieh, C.J. Can Vision Transformers Perform Convolution? October 2021.
[22] Li, Z., Han, J., E, W., and Li, Q. On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis. In International Conference on Learning Represen- tations, September 2020.
[23] Li, Z., Jiang, H., and Li, Q. On the approximation properties of recurrent encoder-decoder architectures. In International Conference on Learning Representations, September 2021.
[24] Z., Han, J., E, W., and Li, Q. Approximation and Optimization Theory for Linear Continuous- Time Recurrent Neural Networks. Journal of Machine Learning Research, 23(42):1-83 2022. ISSN 1533-7928.
[25] Luo, S.. Li, S., Zheng, S., Liu, T.-Y., Wang. L., and He, D. Your Transformer May Not be as Powerful as You Expect, October 2022.
[26] Ostrand, P. A. Dimension of metric spaces and Hilbert's problem 13. Bulletin of the American Mathematical Society, (144):619-622, July 1965. ISSN 0002-9904, 1936-881X XX.
[27] Sanford, C., Hsu, D., and Telgarsky, M. Representational Strengths and Limitations of Trans- formers, June 2023.
[28] Shen, Z., Yang. H., and Zhang, S. Optimal Approximation Rate of ReLU Networks in terms of Width and Depth. Journal de Muthématiques Pures el Appliquées, 157:101-135, January 2022. ISSN 00217824. doi: 10.1016/j matp:r .009.
[29] Takakura, S. and Suzuki, T. Approximation and Estimation Ability of Transformers for Sequence-to-Sequenee Functions with Infinite Dimensional Input, May 2023.
[30] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.., Gomez, A. N., Kaiser, E.,, and Polosukhin, I. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[31] Wang, M. and E, W. Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling, July 2024.
[32] Wu, H., Xu, J., Wang, J., and Long, M. Autoformer: Decomposition Transformers with Auto-Correlation for Long-Teme Series Forecasting, January 2022.
[33] Yun, C.. Bhojanapalli, S.. Rawat, S., Reddi, J., and Kumar, S. Are Transformers universal approximators of sequence-tor -o-suueeee--e functions? In 1rXiv:1912.10077 (Cs, Stat], February 2020.
[34] Yun, C., Chang, Y.-W,, Bhojanapalli,, S., Rawat, A. S., Reddi, S. J., and Kumar, S. $O(n)$ Con- nections are Expressive Enough: Universal Approximability of Sparse Transformers, December 2020.
[35] Zeng, A., Chen, M., Zhang, L., and Xu, Q. Are Transformers Effective for Time Series Forecasting?, August 2022.
[36] Zhou, H., Zhang, S., Peng, J., Zhang, S., Li, J., Xiong, H., and Zhang, W. Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting, March 2021.

---

A Proof of Theorems
A.1 Permutation Equivariance of the Hypothesis Space H
Let p: [7] + [r] be permutation. Let's consider an H E H with permuted inputs:
p) - Σ (xtpttroooo))"xxx00x -wr((co((s)))
(15)
Since the permutation of index does not affect the sum, we have
F ((woofrtttt) (wwla) Wvf((((s)
(16)
(a)))
(17)
This shows that the Transformer hypothesis 7/ is permutation equivariant.
A.2 Density of the Target Space C
In this section, show that the target space defined in Equation (8) is dense in the general continuous target space C(x(E), ()). This ensures that the space defined is general enough to approximate arbitrary continuous targets.
To begin with, first introduce the following representation theorem for multivariate functions.
Theorem A.1 (Kolmogorov Representation Theorem). (26) Let I1, ........ Ir be compact d dimen- sional metric spaces. Then there are continuous functions D4s I. + [0, 1] and continuous function 9g [0, 7] + R, such that any continuous function f 11I; II: I be represented
Σ On Σ E
[1 xT)
(18)
This theorem states that any 7 variable functions can be decomposed into superpositions of one variable function.
Now, we discuss how the pointwise functions on a sequence can apply different mappings on different time indices.
Proposition A.2. Suppose we have T variables in disjoint domains, where I1 E II, I, and
Ii...., I, are all disjoint. We consider the following vector-valued function
f(I1.....,;)= (f
(19)
where Is II + for E [T]. We can indeed define a pointwise function g UI, + to represent f. Since all I, are disjoint, can define piecewise function g, where g(x,,) fe(r.) holds for all 8 E [7].
This proposition demonstrates that for sequence input æ with appropriate positional encodings, where æi) and z(j) belong to disjoint sets, pointwise function can represent distinct mappings for these elements. We are now ready to present the following theorem.
Theorem A.3. Consider d-dimensional, length input space (() with position encoding added. Then, for any H C((((F)))) y)), there exists continuous functions C((0. 1]" 1)"RR). R.), E C(I 1)") and E C(I x I, R.) such that for all E [r] we have
(x(x)) = Σ (oove00),((0)))))aaat)
(20)
where 2rd + 1 and a is the softmax function.
12

---

Proof. Based on the representation for continuous function Theorem
we can decompose H into A.1
11((x)) - Σ 94
(21)
where (1) I. + 10, 1] and 94 [0, + R are continuous functions. We next construct F, / and p to make H satisfy this form. Firstly, since I, are disjoint we can define proper piecewise function
o such that ((0(x((t))))(x((())
which simplifies Equation 8 to
H((x)= = F (f(((t) + Σ (((O)))
1
(22)
Next, based on Proposition A.2 we let the pointwise function f I + [0, 1]" to apply different mappings for each (s)), such that
r(s) + (Z.).. ... 22 (z,),
(23)
where by E [0, 1] are different constants. We then have that
f(x(t)) f(((s)) = -(Vo.((z))) + Σ (x.)......... (2nd Σ
22 (x2),
Σ b
(24)
Here, by performs shifting to make the range of Equation 24 disjoint for different L. Again, based on Proposition A.2 we can define F to have individual mappings for different t. We first define Fi [0, 1]"h
0, to
Fi : u(t) +
(u)(t) (x.) U2rd+1 (t) (erd, un(()
Σ b,
(25)
where denotes the i-th dimension of u. Next, define F2 [0, + IR to be
: u()
94 (1)(
(26)
q=u
Finally, let F(u) = P2 Fi ((T + 1)u). Substitute into Equation (2)) we get that
2rd
He(x) = =1=0>o gg
Σ Vooco(zs))
(27)
9=0
This theorem shows that the target space C is, in fact, representation of the general continuous target space (()((E), y?) In particular, since I is compact metric space, the complexity measures of each component g (.) and y used in the construction of have finite complexity measures Co. C and C2. This implies that the approximation space ((a.8) is also dense.
A.3 Proof of Jackson-type approximation rate Theorem
Now, we present the proof of the Jackson-type approximation rates.
Lemma A.4. The following inequality will be used prove the theorem.
ab ab} s |a| 66
b]+ |6] la a]
(28)
< ||| 6 b
|6|
la
al + laa al bb b
(29)
13

---

Since there are various components in the model, we will consider each of them separately. Firstly let's consider the approximation of F.
Proof. Proof of Theorem 4.2
Let
hx(x)) = Σ ol(()())
(30)
and
he(x)) = Σ (((l)(t).a(3))f(((((()
(31)
we have
F(h) - P()) = F(h) F(h) F(h) F(()
(32)
$ KF h - il + [(h) - F(h)
(33)
Let's consider F()) - F(h) first. Since I is compact domain and is continuous, its range
(T) is compact set. For all E h(T) we have F(h(æ)) F(h(ar)) s F|F FllE~(((ZI)) This implies that
Σ F(h,(z)) F(h,(2)) de S
r 1fddd do F (T-FleM(AEE)
Σ
(34)
= ||]a|||1-0 |F- (M(EE)))
F
(35)
where [Z] denotes the volume of I. Recall that h,(2)) - ((((=((),
may
assume the parameters of is bounded such that f(x(s)) C [0. 1]. By the property Softmax we have f(Z)) C [0, 1]. thus,
$ T|
F F
ST F fl. 10010,11)
(36)
Next, let's consider the first term of
32
h h
(( (p(a,, -tt 2.),(=,,)))){=))
(37)
Σ (1100(((0)))))) - - (o((r,) .
(38)
Since Softmax is Lipschitz continuous and bounded by 1, we have that
Mlle ø + -
(39)
The second term an approximation with neural networks
/ [E(ra ((x)) ((as))) f(xx) dx x2 1211--81 f
(40)
Now we remain to derive a bound for Ip Ô). Let be m. term truncation of POD expansion of then
1p- - " أ i
(41)
< 1p p + 1 2
(42)
14

---

The first term is the error estimates using POD, which says that
f Il( ((1r, xx)l dæ = 12 -ll2
(43)
(44)
The second term is again approximation with neural works, which have
Σ
dedis < l lobs Val + Iaal Oz - di + Ibs - 0o lws rbel
(45)
Thus, combining all the inequalities above, we have that
ΣΣ (x(x)) - He((x) dx
(46)
//sup
Σ
o. +
sup
[dil
V/ - di
+ sup
lobs
(0: 8z
+
0x - 2211
1//1100
2b2
1=
1=1
(47)
+
F
F
+
(48)
By substituting the complexity measure of H to R.H.S., we have that
((a)(H)
(
ch (H)
S
2a-1 +
(m))
8
(49)
mp
mfr
This completes the proof.
B Extra discussions
B.1 Numerical Examples of the Target Form Equation (8)
In this section, we provide numerical examples that follow the target form Equation (
H,(x) =
olota(()
This form, in fact, is not unique representation: in other words, for H H may not have Fi = F2, fi = f2 and # = p2- However, we have the following propositions that characterize the invariant properties of the target form.
Proposition B.1. Suppose H and H2 are in the form of Equation then the following properties hold.
1. If H (m) H2(æ) holds for all then F S1 F2 f2.
2. Suppose a is hard-max functoux For non constant H1, H2 Č, (f H2(2) holds for all æ, then arg max (x(1), x())) arg mrg x s())) if the argmax is unique
s(x)
x(s)
and Fi F2 are injections.
3. Suppose is softmax function. For constant H1 H2 if (x)) H2(w)) holds for
all x and Pt, P2 are unbounded, then arg max Pi (x(1), xs))] = arg (a
z(s)
2(s)
if the argmax is unique and F1 f1, F2 f2 injections.
15

---

Proof. By considering constant input sequence = (a.....,z) x) we get Fi fi(x) F3 o f2 for all
Suppose arg max ( = en and arg (ax(p2(<(()))))))) implies Fi pz (c1) F2 (c() By the injection assumption, have e c22 which implies the argmax are equal.
C2 then Hi (a) = 2
When the normalization softmax, since p unbounded, we consider sequence of inputs (x(*) such that the p(z(1) (t), 20 (s)) goes to infinity, which became the same as the previous hard-max case.
L
Although these properties need satisfy certain conditions to be theoretically correct, we empirically found they generally hold true in real applications.
Next, we demonstrate these concepts through numerical examples by utilizing the Transformer model to learn different targets. We consider the following simplified version of single layer Transformer
Hx(x) F (Wvf(æ) o((Wof(=) Wxf(x))).
(50)
Here, Rdxx is the input, F. are nonlinear mappings applied column-wise, and is the softmax function applied column-wise to the matrix.
Nearest point to set In this example, we consider two sets of points U C Rd and V C R as inputs. For each point uy E U, we aim to determine the nearest point from set V. More specifically, we define input sequence X' 22dx7 in the form xxt) (ug U&) Rad where u, and o are two d-dimensional points belonging to point set U and V. respectively. The output defined as
v(() = arg min (u(() - v|- vEV
(51)
This can be rewritten as
v(t) Σ σH |lu(t) (s)))ss)
(52)
(53)
where OH RT + RR is the hard-max function. Note this equation conforms with the form in Equation with Fo begin identity and p(u, v) = -/u ul. For the numerical example, we consider U. V R and each have points, and train Transformer model to learn this target and examine the learned model.
2
3
4 5
1.0
F+f
0.6
0.2
0.00
0.25
0.50
0.75
1.00
(a) Attention matrix
(b) Graph recovered the model
Scatter plot of f
Figure 2: For Figures (a) and (b) examine particular instance of the input Figure (a) plots the attention matrix A, while Figure (b) illustrates the learned relationships, with green points and red points representing points from set U and V. respectively. Figure (c) is the scatter plot of F Pof(a) f(r) for randomly generated inputs x.
In Figure 2(a) we plot the attention matrix A particular instance of the input ac. For Figure 2(b) visualize the point set U, V based on their coordinates and establish connections according
16

---

to the values in A. Specifically, two points u, and U are connected based on the value of Asg. This visualization reveals exactly that each green point in set U is linked the nearest point in V. demonstrating the model's ability to recover the target relationship accurately. Furthermore, for the larget form Equation (52). F o in this case is an identity function. As shown in Figure 2(c) F
also found to learn an identity function. This observation is in accordance with Proposition despite the theoretical assumptions that may not fully apply.
Weighted average by weight In this scenario, we are given sequences of point masses as inputs, Our objective is to compute the center of gravity for each sequence. These point masses are in IR space, each with a mass m E R.
Consider a sequence containing 7 points. We extend this to a sequence of r + points by adding an extra point zpedd & X at the beginning of the sequence, serving as a prediction token. Consequently, the input sequence is represented as:
x
(1 peed+
21
x
(54)
m
The corresponding output sequence is formulated as:
y (| |z1l..... [z,)),
(55)
where Tpred is mapped to T. and the other points remain unchanged. The center of gravity E is defined by the equation:
denotes the Fuclidean norm.
my
T
Es.
(56)
We may consider several sequence segments of point masses, denoted 2n En which may vary in length. These sequences are concatenated to form an input sequence æ. Correspondingly, the output y concatenates y to yn.
As an example, consider the following input-output pair:
x = (Ipreds
.22
JC3
Eprod
J4 ma
It5 ms
)
(57)
m1
m2
mig
Σ A=l MaTa
y
|21 (222), (Iaa),
a
mg
(58)
=1 my
s' =4 mgg
In this example, the output sequence includes the norm of the computed centers of gravity for each concatenated segment of the input sequence æ. where each segment is separated by the prediction
token Fpred This can be formulated as target form Equation ( such that
Σ
my z(s)
xxt) Fpred
Σ
v(t)
AE
JEE
(59)
Σ 11 s(s)
otherwise
where I, denotes the index of the sequence segment corresponding to Fpred The weighted output here depends on the prediction token, such that it only takes the weighted average within the corresponding sequence. For numerical illustration, consider input of length 10, containing sequence segments of length at least 2. We apply the single-layer Transformer model to learn this target.
In Figure 3 we analyze an input æ comprising two sequence segment, æ; and Ø2, with lengths of 3 and 5, respectively. In this scenario, s0 and (5) are prediction tokens. The attention matrix behaves as expected: the outputs y(0) and y(5) are influenced predominantly by the points within their respective sequences, and the values are approximately the normalized weight. Furthermore, since the remaining outputs are the same the inputs, the attention matrix values for these elements are confined to the diagonal, which means that the output at that point is only determined by itself.
Furthermore, in Figure 3(c) we observe that f f can successfully recover F f in the target which is norm of the I2 vector.
17

---

1.0
0.4
0.8
0.2
0.6
0.0
0.2
-0.2
0.0
-0.4
-0.4
-0.2
0.0
0.2
0.4
(a) Attention matrix
(b) Graph recovered by the model
(c) Contour plot of F
Figure 3: Figure (a) plots the attention matrix A, while Figure (b) the illustration of the learned relationship. In this instance, there are two sequences, æ1 and 222 each connected to their respective predictions. The color of the connecting lines represents the corresponding values in A. Figure (c) presents the contour plot of F f(x), generated for set of random inputs
Weighted average by selection The previous calculated the weighted average by specifying the weight of each point. Now, we consider another way to calculate a weighted average where we specify subset of points are going to take the average. Suppose we have length sequence of Id vectors v E Rdxr, We also have sequence of vectors s E [r]**r consisting of sequences of indices. We stack and s to form the input sequence æ E ((d+k)xT This extends the qSA task proposed in Sanford al. (27]
The output yt) defined as
(t))
Σ sEa(()
(60)
This can be written in the target form Equation (8) such that F o f is identity. Depending on the frequency appears the index vector s(t), we have that
((x(1)xx(s)) {0, 1 2
(61)
1 k
As an example, we have the following input-output pairs.
(01, 12, Us),
1
3
(62)
y = 3
2v1 + 02 01 + U2 + Ug. 313
In our numerical experiments, we set 8, d = 2, and k = 3. This configuration implies that both the input and output sequences have length 8, and the output y(t) is computed as the average of three inputs, indices designated by st)). For this particular setting have p {0, 2 3 1}. Again, we use a single-layer transformer model to learn this target.
In Figure 4 we examine particular input, where
=
I
6 7
(63)
In Figure 4(a) we observe that the attention matrix accurately reconstructs P. as demonstrated in Figure illustrates the graph representation of this input-output correlation based on the matrix In this graph, an output and an input j are connected by the value of Aij. The figure highlights the model's capability to recover the relationship: Output y (1), v(3). y(6) each rely on singular input value, output (0), y2) are calculated the average of two values, and output (4),, v(5), (7) each represent average over three values.
Equation 61
18

---

2
1.0
Fxf
Output
0.8
2/8
0.6
1/3
0.4
0.2
0.0
0.00
0.25
0.50
0.75
1.00
(a) Attention matrix
(b) Graph recovered by the model
(c) Contour plot of F
Figure Figure (a) plots the attention matrix A, while Figure (b) illustrates the learned relationship. The points in different colors refer to the input and output, respectively. They are connected based on the value of A. Figure (c) presents the seatter plot of F f())), generated for set of random inputs
In summary, these examples demonstrate tasks that follow the form presented in Equation ( Moreover, the numerical experiments validates Proposition B.1 where F o f is always the same, and the attention matrix recovers the desired weights.
B.2 Synthetic Examples
Error
Error
1.5
2.0
1.5
1.0
0.5
2
4
8
10
mh
8 10 mn
k
-0.30
k: S
(b) k k S
(a) 03
0
k >>
k 2r
We consider two class of with different singular value decay rate as indicated above. Here, r denotes the rank of the target. For each (a) and (b), consider three targets with p having different ranks, where r = 2, 6, oc. The figure plots the training error against my. Each colored line corresponds to target with rank indicated in the legend. The grey dotted line plots m, (2a-1)
Figure 5:
The Jackson-type approximation rate in Theorem 4.2 has the following prediction. For sequence relationships admitting a representation Equation 8) rank finite, then perfect approximation is possible as long as m, 2 r with mEF large enough. If co, then the approximation error is determined by decay of aTk- Concretely, if a k- then the error decays like m, (2a-1) constant, provided mFF is sufficiently large. We numerically verify the prediction by constructing set of targets using Equation (8). In this specific example, we both F and f as the identity function. The temporal coupling term p(u, u, v) is formulated using an orthonormal bases where Φ., v% e
(V2 sin 2iTr: i 2 1}. accompanied by singular values with various decaying patterns. Subsequently. we trained the Transformer defined in Equation (5) to learn these targets. Figure the training error against m,, where (a) and (b) correspond to targets with different singular value decay patterns. also consider different rank r of the targets as plotted using lines with different colors. The error decay rates of (a) and (b) are different, which follows the decay rate determined by that of the singular values. Furthermore, for fixed my, the error increases with the target's rank. The experiment results consistent with estimates in Theorem
19

---

C Experiment settings
In this section, we summarize the settings for the numerical experiments.
Experiments in Appendix B.2 These experiments consider the synthetic targets with simpli-
fied Transformer models defined in Equation (5). The target relationship is constructed using
Equation
H,(x) = F
Σ 2 (lle0))
(64)
We consider scalar inputs where d = 1 and F(x) = f(x) = are identity functions. p(u, u) is constructed using the POD decomposition:
p(u, v) Σ 0,0,(u)),(v).
(65)
1}. By doing this, we can specify os We consider orthonormal bases di, the E (V2sin 2iςr i which are then exactly the singular values. The input sequence of length 16 is generated using a uniform distribution on [0. 1]. We use Transformers as defined in Equation (5) to learn these targets. The feed-forware part is constructed using a dense network with width of 128 and depth of 3 to ensure it has enough expressiveness. Moreover, we have n dg 32 and my, which range from 1 to 16, to construct model with different ranks. We use Py default initialization and use normal training procedures with Adam Optimizer. We train enough epochs to ensure the loss does not decrease so that we can use the training error to estimate the approximation error.
Experiments in Section 5.1 In this example, tested the VIT model on the CIFARIO dataset. We consider the baseline model ViT B 16 [[]. This model configuration utilizes 12 heads, and each head of dimension 64. In Figure (a) we plot the singular values distribution of the attention matrix (before Softmax normalization) from the first attention head. We then vary the size of each attention head from to 64 while keeping other configurations unchanged. We follow the training procedure
as described in 11 to train the modified models.
Experiments in Section
Comparison of the Transformer and RNNs
We consider the following linear target relationship:
H2(x) = Σ p(s)x(t-ss) -
(66)
1=
with kernel p(s) exp(-s) The input sequence of length 32 is generated using uniform
distribution on [0, 1]. For the RNN, we utilize a one-layer vanilla RNN architecture with 128 hidden units, employing linear activation function. For the Transformer, we use the simplified structure as presented in Equation (8) with position encoding added. For parameter settings, we have n d, = m, 32. The feed-forward part is constructed using a dense network with a width 128 and depth 3.
To change the temporal ordering, we permute the input while keeping the output unchanged, this leads to a change in the temporal ordering of the target relationship. For all the input sequences, we exchange the first 10 values with the last 10 values, resulting in change in the underlying temporal structure. For the temporal mixing operation, we use a randomly generated length 5 filter and the operation * described in Section 6.2
In Table 2 it is also interesting to note that for this target, the RNN performs better than the Transformer. This is potentially because temporal ordering is inherently important in this target, and the Transformer is not good at capturing such relationships. Some variants of the Transformer, such as Informer (36) and Autoformer [32], have been proposed specifically to address temporal relationships, particularly in sequence forecasting tasks. However, empirical results presented in Zeng et al. (35) indicate that these variants still cannot effectively capture temporal relationships.
As comparison, we consider a different type of linear relationship where the temporal ordering is unimportant. We randomly generate the filter such that p(s) ~ Uj.11. This does not have temporal
20

---

ordering since if we permute p. the distribution of it does not change. The results are shown in Table We can observe that it hard for RNN learn this target. But the Transformer can learn this target, and a permutation of the input does not affect its performance.
RNN
Trans.
Original
5,58
5.43e-
Permuted
5,24
5.36e-4
Table 3: The table presents the MSE values both RNN and the Transformer datasets without temporal ordering.
Real-world datasets for the Transformer In Table we test the performance of the Transformer on permuted dataset considering real-world examples. For the ViT experiment, we use the ViT B16 model. For the WMT2014 English-German dataset, we use the original Transformer model as proposed in 300 For both experiments, when testing on the permuted dataset, we initialize the model with parameters that are trained on the original dataset. To generate
permuted dataset, we permutation such that the first 10 elements are shifted to the end of the sequence. This operation is applied to all the input sequences. Note that the permutation of the ViT dataset before the addition of position encoding and after the convolution embedding.
D Detailed Dissuasion of Section
In this section, we provide additional discussions related to Section 6 We first review the approxima- tion results for the RNN, the we provide proofs for the propositions presented in Section 6
D.1 Introduce the approximation results for the RNN
We here review the results approximation results of RNN presented Li et al. Here, we consider input and output space defined by
X' fo xs)) E [0, 114, N20)
(67)
and
y ly : v(5) E R N2o) There are infinite sequences with time indices starting from zero We consider the following dynamics for the linear RNN:
(68)
htt) Wh(t 1) Un(t)
(69)
(t) = c h(t).
(70)
where h RR" with h(0)= is the hidden state of the RNN. W E gax" U E Rdx= and c e 1x are parameters. The approximation budget of the model is n, which is the size of its hidden state. We can explicitly solve this dynamic where we get
(x) = Σ e (w-Ux(t-s))
(71)
Here, we assume the eigenvalue W has a negative real part to ensure is stable when s increases.
For the target, we consider linear relationship represented by
H.(x) Σ p(s)x((- -);
(72)
==0
where [|p(s)]] S oo is unique representation of H. Thus, the approximation capability of the RNN is characterized by the properties of
21

---

Note that ((s) = W must also have a similar decay pattern to achieve a good approximation. We have precisely defined the following complexity measures for the RNN.
C in the RNN exhibits an exponential decaying pattern. Thus, the target
(I 1+ inf O: lim eà |p(t)] 0).
(73)
This measures the decaying speed of the RNN, we assume p exhibits an exponential decay, with decaying speed measured by Cj. The next complexity considers the norm of p:
C2 H)) supfe [p(t) : 0}.
(74)
Combined together, we define the complexity measure for RNN as
CRNN Ci(H) C2(H)
(75)
This considers the magnitude of C2 is small if p does not have a large value far from the origin. We define the RNN approximation space to be targets that have finite complexity measures
CRNN {H satisfies Equation (22 CRNN < co).
(76)
The approximation rate of the RNN follows d- CRNN
D.2
Discussion of Section 6.1
Proof of Proposition 6.1 We now present the proof for Proposition 6.1
Proof. Let N20 N2o be permutation on the time indices. We consider altered target
( He(x)
(77)
We then have
ox E (s))x(((1-)) - s))
(78)
Let's consider the most simple case where p only permute two time indices such that p(t1) = f/2 and t2 > 11. We consider the output t
H4, (x) Σ p(s)a(t1 -s)
(79)
==0
Σ p(s)a(11 + =())(())
(80)
However, for He, (x) have
(z)p))
Σ ((s) - s))
(81)
==0
Σ (())a(t -) +))
(82)
Note the in this case the output & depends on future value input (t22), this means that H is no longer causal. Consequently, A cannot written the form of Equation (72). thus not belong to the RNN approximation space.
22

---

Proof of Proposition 6.2 We next consider the Proposition 6.2
Proof. For fixed permutation p P:T + 7, we consider H. p) Hx))). Suppose the altered target has the following form:
Hi(w o p) = Σ (obbc6660))
(83)
we next show that F. and ý has same complexity measures as F, f and p. Firstly, we note that can remove the permutation index because the ordering of a summation does not affect the result.
H. o = Σ Eo(((x(0)))))000)0)
(84)
We now consider the POD expansion of where
x((p(tt). Σ (x((((()((t)) (x(s)))
(85)
Recall that our input space is defined as Equation disjoint sets. Thus, for pointwise function
77 Where I, E I. such that Z, and Z, are closed write it into the following piecewise form
d(x) = (x) I
(86)
Let (x)) o, (o((0) for x E I. This is essentially the permutation of the disjoint pieces of Φ; Thus we have
(.((((())) = 0. (x(t)).
(87)
Consequently, we have p(z(p(t)), xs)) = p(=(t),z(s)) Finally let F= Hz(x o p) = (x)) Since and f remain unchanged, we only need to consider the complexity measure for We note that the rank of the POD is unaffected. We remain with OpF(#)). The function J; is permutation of pieces of the piecewise function Φ;, We next discuss the kind of approximation schemes that (rr(o:) is unchanged under this operation.
F and f= f we achieved
Since the set I is disconnect, apply Tietze extension theorem extend de its convex hull, denoted as 4 such that (x)) = (x) for x E I and sup (x)))) = (x))).
We first consider the polynomial approximation have (r.( max,=1...a || We next show that (r.( (rr( Since I is closed and ő continuous, we apply Tietze extension theorem to extend Φ; a denoted as L, such that &. (z) (x) for x E and supf supf & (x)]). This implies that (rr( = CFr((.) Thus, in the case of polynomial approximation, the complexity measures remain unchanged.
introduced in Section 3 In this case,
Next, we consider the approximation using the ReLu network. We assume O; be Hölder continuous such that
[f(x) - s(w) S C| y1
(88)
The Tietze extension theorem states we can extend to Φ; with the same and az.
As shown in Shen et al. (28). the approximation capability of a ReLU network on Hölder function depends on C' and a. Where functions with small C, can be approximated more effectively, Since &e is permutation of disconnected pieces of d;, its Hölder constant remains unchanged. Thus, its $ has same Hölder constant as D,, which implies the complexity measure is the same.
In the above proof, we considered two different approximation schemes where the complexity measures of H remain unchanged.
23

---

D.3 Discussion for Section 6.2
Proof of Proposition 6.3 We first discuss Proposition 6.3 filter with ||@|| S 1. The altered target is defined by
Consider filter 0 which is a length /
He(x)) = H₂(0 * x) =
Σ
pls](0 * x)[t - s}.
(89)
==0
Rearrange the summation, and get
Hx(x)
Σ p(s) x)(t
(90)
1-1
Σ p(s) Σ
015||a(1 - -8 8))
(91)
s'=0
0|s|)p(s)z(t - s++
(92)
0[s'|p|s s/x=(t-
(93)
0'==
Σ (0 * p)(s|a(t - s]
(94)
Σ p(s)x((1 - 8).
(95)
0=
Thus, we have the altered kernel denoted as - 0 * p.
Proof. Firstly, for [p(s) s exp(- }), by the definition of C₁ and C2 we have C1 (H) I 3 and C2(H) 1.
By assumption we have P exhibits exponential decay such that [p(s) S e 88 for some 8. We then have
[p(s) 1 * p)
Σ 1005) 8')1 S 85 ||0|| e -Ba
(96)
which shows that p[t] is also bounded by e Bs This implies that C1 ( S 3 and C2 S 1.
Transformer Affected by Temporal Mixing Finally, we present an example where a temporal mixing in the input will affect the target's rank. For simplicity we consider the case where d = 1 and 7 2, and æ1, x2 e [0, 1]. Note that here, we do not assume Iı and 22 belong to disjoint intervals for simplicity. For target in the form of Equation (8), we consider a temporal coupling term defined as
p( 22) = 1 + sin (2
(97)
In this case, p(u, v) is of rank 2 with both singular values equal to 1. Consider a new input (21, 22 + 21) with temporal mixing. We then have
p(x1,22 22 + =1)= = = / sin((a)))) (2 1.265, 0.5 and d3 = 0.4. The
(98)
We numerically estimate the singular values of ğ to get rank of ð increases, and there are also extra bases included. Here, we only consider the rank p from the same representation, while we do not exclude the possibility that there exist other representations that may have another rank pattern. Indeed, analyzing the temporal mixing in the Transformer is non- trivial; we only provided an example where the rank increases. Conversely, a suitable deconvolution process can also decrease the complexity measure of the target. We leave as a future direction for analysis.
24

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction accurately reflect the paper's 's contributions and
scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We made simplification and assumptions for theoretical analysis. However, we performed empirical experiments to demonstrate the implication the theoretical results also holds true in general settings.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "LLimitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Justification: All the theoretical settings and assumptions are presented. Complete proofs of theorems presented in the appendices. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We conducted numerical experiments to demonstrate our theoretical results, settings presented in the appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
26

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
We conducted numerical experiments, with settings clearly presented in the
paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
oolicy)lyycyyoooll for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccppbbll/ conooi///gddds//oeeeubbbiii
hat////ooSSueiisseeeeeee weabbbimssiiee SttSSubbissoooooiiiioo.. onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Detailed experiment settings are presented in the appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification:
Our numeric demonstrations does not require error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not contain computational extensive experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The Code of Ethics is followed.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our results are theoretical, and there is no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper have no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papprswiiiiiie thcode com datastts has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "xxxgj5n85m", "reviewer": "Reviewer_YNqb", "summary": "The study explores the theoretical aspects of Transformer architectures in sequence modeling, particularly focusing on approximation rates for sequence-to-sequence relationships. A representation theorem is established, introducing novel complexity measures that analyze interactions among input tokens, culminating in a Jackson-type approximation rate estimate for Transformers.", "questions": "Q1. In the context of POD, it is my understanding that having rho with fast decaying singular values allows for the complexity measure of H to be constant. However, this paper employs a specific construction to derive equation (22) for sigma(rho) as mentioned in line 492.\nCould we still say that rho has fast decaying singular values in this case? Please provide a specific explanation.\n\nQ2. It's unclear how to construct the F1 function that realizes equation (25). Could you explain in detail?\n\nQ3. I cannot  understand the flow from equation (22) to (25). \nEequation (24) (f(x_t)+sum_s f(x_s)) is constructed using equation (22), which is realized by using a specific attention, and then f(x_t) is removed in equation (25). \nWhy not just construct an attention, average pooling, that constitutes sum_s f(x_s) in Eq. (22)?\n\nQ4. Theorem A.3 states that n=tau * (2 * tau * d+1)+1.\nHowever, looking at equation (23), it appears that the output of f is only (2 * tau * d+1)-dimensional.\nWhere does n=tau * (2 * tau * d+1)+1 need to be?\n\nQ.5 Considering the theoretical framework presented here which inherits limitations from the Kolmogorov representation theorem, could you specify what limitations might arise in the class of functions approximated by the model?\nIt is worth noting that identifying these limitations does not detract from the contributions of this paper.", "limitations": "The paper deviates from the standard Transformer architecture by requiring a neural network layer before the attention mechanism to implement the Kolmogorov Representation Theorem, potentially inheriting the theorem's limitations.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This study enhances the understanding of Transformer's approximation rate and gives concrete comparisons with traditional models like recurrent neural networks.", "weaknesses": "The paper deviates from the standard Transformer architecture by requiring a neural network layer before the attention mechanism to implement the Kolmogorov Representation Theorem, potentially inheriting the theorem's limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The paper deviates from the standard Transformer architecture by requiring a neural network layer before the attention mechanism to implement the Kolmogorov Representation Theorem, potentially inheriting the theorem's limitations.\n\n   - For our proposed architecture (5), the term $\\hat h = \\hat f \\circ x$ is fed into the attention component, where $\\hat f$ is a feed-forward network. This assumption is not particularly restrictive. Our architecture (5) can be viewed as a specific \"slice\" of the standard Transformer architecture. The standard Transformer follows a pattern of \"Atten->FFN->Atten->FFN->...\". Our formulation can be seen as focusing on the \"FFN->Atten->FFN\" part within this structure.\n\n\n2.  In the context of POD, it is my understanding that having rho with fast decaying singular values allows for the complexity measure of H to be constant. However, this paper employs a specific construction to derive equation (22) for sigma(rho) as mentioned in line 492. Could we still say that rho has fast decaying singular values in this case? Please provide a specific explanation.\n\n   - Line 492 pertains to the proof of Theorem 4.1, demonstrating the equivalence of Equation (8) with the continuous function space $\\mathcal C=C(\\mathcal X^{(E)}, \\mathcal Y)$. The proof is constructive, involving a specific construction of $\\rho$ at Line 492. It is essential to emphasize that this construction is designed specifically for the proof of Theorem 4.1. When assuming a target in the form of Equation (8), we do not assume $\\rho$ to have any specific form.\n  \n   - For Theorem 4.2, we do not assume $\\rho$ is fixed like the construction presented in Line 492. In Theorem 4.2, the target $H$ adopts the structure of Equation (8), where $\\rho \\in C(\\mathcal I \\times \\mathcal I, \\mathbb R)$ is a general continuous function that have finite complexity $C_1^{\\alpha}$. Since $\\rho$ is not restricted to a specific form, different target $H$ may correspond to varying patterns of singular value decay and thus different complexity measures.\n\n    \n\n3. It's unclear how to construct the F1 function that realizes equation (25). Could you explain in detail?\n\n   Firstly, for clarity, Equation (24) should be defined as $u(t) = f(x(t)) + \\sum_{s=1}^\\tau f(x(s))$. Next, it is observed that each $u(t)$ resides within disjoint cubes since $b_t$ are assumed to be distinct. Consequently, $F_1$ can be defined separately on each disjoint cube. For each $t$, the expression $F_1(u(t))$ is governed by Equation (25). Moreover, $u(t)$ is $n$-dimensional, where $u_i(t)$ denotes its $i$-th component.\n\n\n4. I cannot understand the flow from equation (22) to (25). Eequation (24) (f(x_t)+sum_s f(x_s)) is constructed using equation (22), which is realized by using a specific attention, and then f(x_t) is removed in equation (25). Why not just construct an attention, average pooling, that constitutes sum_s f(x_s) in Eq. (22)?\n   \n   - To clarify, Equation (24) should be defined as $u(t) = f(x(t)) + \\sum_{s=1}^\\tau f(x(s))$. Equation (25) does not remove $f(x_t)$;  \n   rather, it is an intermediate definition of $F$ in Line 500. \n   - The proof aims to align the functions $F$, $f$, and $\\rho$ in Equation (8) with Equation (18). Specifically, $\\rho$ is defined at Line 492, and $f$ is given by Equation (23). The function $F$ is constructed as $F(u) = F_2 \\circ F_1((\\tau+1)u)$, where its definition is decomposed into two distinct functions for clarity. By substituting these expressions for $f$ and $F$ into Equation (22), the proof achieves an exact correspondence with Equation (18).\n\n  \n\n5. Theorem A.3 states that n=tau * (2 * tau * d+1)+1. However, looking at equation (23), it appears that the output of f is only (2 * tau * d+1)-dimensional. Where does n=tau * (2 * tau * d+1)+1 need to be?\n   - Thanks for pointing out. This is indeed a typo, the correct formula should be $n=(2 * \\tau * d+1)$.\n\n\n6.  Considering the theoretical framework presented here which inherits limitations from the Kolmogorov representation theorem, could you specify what limitations might arise in the class of functions approximated by the model? It is worth noting that identifying these limitations does not detract from the contributions of this paper.\n  \n   - A techniqual limitation of the function space arises because a given $H$ may correspond to different sets of $F$, $f$, and $\\rho$, implying non-uniqueness of the form (8). This aspect is reflected in the definitions of complexity measures in (10), (12), and (13), where we take the infimum over all possible $F$, $f$, and $\\rho$. \n\n   - In Section 6, we also discuss limitations arising from target form (8). Proposition 6.2 states that permutation of input sequences does not alter the complexity measures, suggesting that temporal ordering is insignificant within this function space. This implies that Transformers excel in handling sequential relationships with minimal temporal dependencies, as detailed in Section 6.1. However, the complexity of the function space can be significantly influenced by temporal mixing. As discussed in Section 6.2, this indicates that the performance of Transformers can be adversely affected by straightforward temporal mixing manipulations. To summary, these intrinsic structural limitations also implies approximation limitations of the Transformers.", "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": "", "extra_scores": {}}, {"review_id": "aXjYPY3Ffs", "reviewer": "Reviewer_GFZQ", "summary": "This paper introduces a novel concept of complexity measures to construct approximation spaces for single-layer Transformers with one attention head, providing Jackson-type approximation rate results for target spaces that possess a representation theorem.", "questions": "- How can the results be generalized to analyze multi-layer multi-head Transformers? Will such generalization provide new insights or understanding?\n\n- Although the discussion on the parameters' dependence on rank is provided, the factor $\\tau^2$ in the RHS of the inequality in Theorem 4.2 appears suboptimal for approximating long sequences.\n\n- It seems that much of the relevant literature on the approximation power of Transformers has been omitted. For example, [1][2][3].\n\n[1] Giannou et al (2023). Looped Transformers as Programmable Computers.\n\n[2] Bai et al (2023). Transformers as statisticians: Provable in-context learning with in-context algorithm selection.\n\n[3] Wang \\& E (2024). Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling.", "limitations": "See Weaknesses.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The results in this paper are presented within a general framework using rigorous and elegant mathematical tools, offering a solid theoretical foundation for researchers interested in approximation.\n\n- Their hypothesis of singular value decay pattern regarding the target space can be validated through the experiments detailed in Section 5. Furthermore, the hypothesis underscores the crucial role of pairwise coupling and low-rank structure.", "weaknesses": "The results presented are limited to 2-layer single-head Transformers, which restricts their applicability and insights into more common models such as multi-layer multi-head Transformers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. How can the results be generalized to analyze multi-layer multi-head Transformers? Will such generalization provide new insights or understanding?\n\n    - Firstly, our rate still applies to multi-layer and multi-head Transformers, serving as an upper bound. This is because our single-layer, single-head architecture represents the simplest form of multi-layer, multi-head Transformers. However, increasing the number of layers and heads can potentially yield more refined bounds. Theoretical analysis of the relationship with depth and the number of heads requires consideration of a more intricate approximation space, which includes defining suitable target form with complexity measures that account for depth and the multi-head structure.\n\n    - While our theoretical results are based on simplified architectures, empirical verification in Section 5 and Section 6 confirms that these insights (be specific) hold for multi-layer architectures as well. In Section 5, we demonstrated the existence of low-rank structures in multi-layer Transformer architectures. Section 6 discuss both the strengths and limitations of Transformers compared to RNNs. We verified our statements regarding general multi-layer and multi-head structures.\n   \n2. Although the discussion on the parameters' dependence on rank is provided, the factor $\\tau^2$ in the RHS of the inequality in Theorem 4.2 appears suboptimal for approximating long sequences.\n\n    - The quadratic scaling of Transformers in sequence length is a well-known issue. The factor of $\\tau^2$ arises because the size of attention matrix scales as $O(\\tau^2)$ with the sequence length,leading to quadratic scaling in computation time. This scaling also affects approximations, as described by Equation (43), where the approximation of the attention matrix involves both temporal directions $t$ and $s$, resulting in approximation errors that scale with $\\tau^2$. \n\n3. It seems that much of the relevant literature on the approximation power of Transformers has been omitted. For example, [1][2][3].\n\n   - [1] considers a special setting regarding expressiveness, demonstrating that Transformers can represent any computer program. [2] and [3] explore target relationships with certain special structures. Thank you for highlighting these references. We will include them in the related work section.\n\n[1] Giannou et al (2023). Looped Transformers as Programmable Computers.\n\n[2] Bai et al (2023). Transformers as statisticians: Provable in-context learning with in-context algorithm selection.\n\n[3] Wang & E (2024). Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling.", "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": "", "extra_scores": {}}, {"review_id": "0eHgWCvjaH", "reviewer": "Reviewer_fL7j", "summary": "This study investigates a Jackson-type approximation rate for single-layer Transformers with one head, and compares their ability with RNNs, another nonlinear sequence-to-sequence map.", "questions": "- Can the author provide a similar bound in a constructive manner without using the Kolmogorov theorem?\n- Given a dataset, how to estimate $\\alpha$ and $\\beta$?", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The literature overview is concise\n- The Jackson-type approximation rate for the Transformer is derived for the first time", "weaknesses": "The main theorem (Theorem 4.2) sounds trivial because the bound is a combination of the definitions of complexities $C^\\alpha$ (Sobolev smoothness) and $C^\\beta$ (Barron bound). The universality of Eq.8 (Theorem A.3) may sound non-trivial, but it is obtained by rewriting the Kolmogorov representation of continuous function (from Theorem A.1), which is much a stronger (but only existential) result.\n\nIt could be non-trivial if the authors could provide a similar bound in a constructive manner without using the magic argument of Kolmogorov.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The main theorem (Theorem 4.2) sounds trivial because the bound is a combination of the definitions of complexities $C^\\alpha$ (Sobolev smoothness) and $C^\\beta$ (Barron bound).\n\n    - Firstly, we need to clarify that $ C^\\alpha $ is not a Sobolev smoothness term. It is defined as the POD rank of the temporal coupling term $ \\rho $ (Line 181 - Line 195). To the best of our knowledge, our approximation rate results (Theorem 4.2) have no similar results previously.\n    \n    - Theorem 4.2 should not be dismissed as trivial. For Theorem 4.2, our analysis sheds light on the distinct roles of the feed-forward and attention components. The feed-forward component aims to approximate both the pointwise functions $F$ and $f$, as well as the POD bases of the temporal coupling component $\\rho$. We substantiated the validity of our findings numerically in Section 5, demonstrating the existence of low-rank structures in Transformer approximations.\n\n    - Additionally, Theorem 4.2 provides insights into the differences between Transformers and traditional sequence modeling architectures like RNNs, discussed in Section 6. The complexity measures defined Section 4 are unaffected by permutation but is influenced by temporal mixing. This contrast implies the fundamental distinction of Transformers and RNNs in handling temporal relationships. In Section 6.1 we show that the RNN is proficient in handling temporal relationships with strong temporal ordering structure. While for relationship with minimal temporal ordering, the Transformers works better. Section 6.2 explores how temporal mixing can impact Transformer performance, whereas RNNs remain unaffected.\n  \n    - Defining appropriate complexity measures and approximation spaces is crucial in approximation theory, offering insights into hypothesis spaces. A well-chosen approximation space can illuminate the capabilities of the hypothesis space. Referring to recent studies [1] and [2], which consider targets of the form $H_t(x) = \\sum \\rho(s)x(t-s)$, various complexity measures are defined for $\\rho$ considering the architectures. In RNNs [1], these measures account for the smoothness and decay rate of $\\rho$, whereas in CNNs [2], they focus on the sparsity of $\\rho$. Different architectures reveal distinct approximation capabilities: RNNs excel with smooth and fast-decaying targets, while CNNs are effective with sparse targets. Our results also provides insights of the Transformer architectures, which are discussed in Section 5 and Section 6.\n\n    \n[1] Li, Zhong, et al. \"Approximation and optimization theory for linear continuous-time recurrent neural networks.\" Journal of Machine Learning Research 23.42 (2022): 1-85.\n\n[2] Jiang, Haotian, Zhong Li, and Qianxiao Li. \"Approximation theory of convolutional architectures for time series modelling.\" International Conference on Machine Learning. PMLR, 2021.\n\n\n\n2. Given a dataset, how to estimate $\\alpha$ and $\\beta$ ?\n\n    - Estimating $\\alpha$ and $\\beta$ directly from a dataset based on their definitions can be challenging. However, empirical estimation is feasible by training models of varying sizes on the dataset. In Section 5.1, we discuss how to estimate $\\alpha$ in detail. The main idea is train models with varying $m_h$ and fit the error curve with $\\frac{1}{m_h^\\alpha} + c$ for an estimation of $\\alpha$. It is important to highlight that insights derived from approximation results hold greater significance than exact values of approximation bounds. Specifically, in Section 6, we discuss the strengths and limitations of Transformers compared to RNNs, leveraging these approximation insights for discussion.\n\n\n3. Can the author provide a similar bound in a constructive manner without using the Kolmogorov theorem?\n\n    - The approximation bound in Theorem 4.2 is independent of the Kolmogorov theorem. The Kolmogorov theorem is only used in Theorem 4.1 to establish that form (8) is general enough to represent any continuous target. The approximation bound in Theorem 4.2 considers targets of the form (8) where $F$, $f$, and $\\rho$ are assumed to be general continuous function with finite complexity measures and not restricted by the Kolmogorov representation. Consequently, the results in Theorem 4.2 are not depend on the Kolmogorov theorem.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper received favorable reviews. Reviewers acknowledge the novelty of the Jackson-type approximation rate for the Transformer and agree on the merits of this paper being presented at NeurIPS.
Decision: Accept (poster)