Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling

Authors: mingze  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:47:19

Abstract: We conduct a systematic study of the approximation properties of Transformer for sequence modeling with long, sparse and complicated memory. 
We investigate the mechanisms through which different components of Transformer, such as the dot-product self-attention, positional encoding and feed-forward layer, affect its expressive power, and we study their combined effects through establishing explicit approximation rates.
Our study reveals the roles of critical parameters in the Transformer, such as the number of layers and the number of attention heads.
These theoretical insights are validated experimentally and offer natural suggestions for alternative architectures.

Main paper: 
 introduction: 
 In recent years, Transformer networks (Vaswani et al., 2017) have emerged as foundational models, setting new benchmarks across various domains, including natural language processing (NLP), computer vision (CV), and protein folding. Despite their impressive practical achievements, the underlying mechanisms and theoretical foundations of Transformer networks remain largely elusive.Transformer networks encompass various components, posing challenges to their comprehensive understanding. A typical Transformer comprises multiple layers, each consisting of a multi-head self-attention (Attn) sub-layer and a feed-forward network (FFN) sub-layer, integrated with residual blocks. FFN is a two-layer nonlinear network, while Attn includes dot-product (DP) and positional encoding (PE). To get a better understanding of how Transformer works in practice, we need to study several key issues. These include:(i) How do the key hyper-parameters, for example, the number of layers, the number of Attn heads and the with of FFN layers, affect the performance of the Transformer network? (ii) How do the Attn and FFN layers contribute differently to the overall performance? (iii) How does DP attention work, and is the DP structure necessary? (iv) How efficient is PE in modeling long-range correlations?Extensive empirical research on Transformer components has led to the proposal of numerous alternatives to the current structure of Transformer. For example, several relative positional encodings (RPE) (Shaw et al., 2018; Raffel et al., 2020; Su et al., 2024; Press et al., 2022) have been proposed to substitute the original absolute positional encoding (APE), yielding superior performance in challenging tasks like length generalization (Ontanón et al., 2022; Csordás et al., 2021; Anil et al., 2022) . Additionally, the necessity of the computationally expensive DP in Attn layers has been widely questioned, and researchers proposed numerous alternatives of DP that show considerable efficacy in specific tasks (Kitaev et al., 2020; Wang et al., 2020; Choromanski et al., 2020; Tay et al., 2021; Allen-Zhu and Li, 2023) . Nonetheless, these explorations have not yielded a satisfactory theoretical understanding of the mechanisms of these components.In this work, we investigate the expressive power of Transformer and the underlying mechanisms of its components for sequence modeling. Our contributions are summarized as follows:We categorize three types of sequence modeling tasks with varying complexity, which are relevant to a broad spectrum of application areas. Task I: Modeling fixed, long but sparse memories. This is relevant to sparse Boolean functions and the traditional n-gram model in NLP. Task II: Modeling adaptive, long but sparse memories. This is relevant to multi-step reasoning tasks as well as various NLP tasks such as dependency parsing, sentiment analysis, and continuation writing. Task III: Modeling essentially sparse memories. Examples include feature representation in CV and wavelet analysis in classical signal processing.For these sequence modeling tasks, we theoretically investigate the expressive power of Transformer and its variants, establishing explicit approximation rates. Our meticulous analysis provides theoretical insights into the underlying mechanisms of Transformer components. Specifically,• The distinct roles of the number of layers, the number of Attn heads, and the width of FFN layers. Deeper Transformer are capable of handling memories with more intricate interrelationships, such as nested relationships (Thm 4.4). In contrast, for memories lacking such interrelationships, single-layer Transformer with sufficient number of Attn heads and FFN width should suffice (Thm 4.1). This is quite intuitive: If the content of the next token relies on a few previous tokens in an independent way, we can treat each such dependence by a separate attention head. There is no need for many layers. Additionally, increasing the depth can also alleviate the reliance on the number of heads and width (Prop 4.5).• The different roles of Attn layers and FFN layers. Our results consistently suggest that: FFN layers are tasked with approximating nonlinear memory functions and the readout function, while Attn layers are responsible for extracting the tokens from these memory locations.• The functionality and necessity of DP. For the relatively simple Task I, DP is not necessary and can be omitted (Thm 3.1). However, for the more complex Task II, the cooperation between DP and RPE provides the needed interaction between the temporal space and the token space, crucial for the extraction of adaptive memories (Thm 4.1 and 4.4). Additionally, for Task II, while the nonlinearity provided by DP is necessary (Prop 4.2), a computationally efficient alternative to DP exists, as we show in Prop 4.3.• The efficiency of RPE in modeling long-range correlations. Our results consistently suggest that the primary role of RPE is to approximate the memory kernels. Specifically, for Task III, we demonstrate that Transformer with suitable RPE can handle heavy-tailed memories, thus overcoming the Curse of Memory faced by recurrent neural networks (Thm 5.1). Moreover, our findings give theoretical support to the choice of RPE in practice.Finally, we conduct experiments to validate our theoretical insights. 
preliminaries: 
 Basic notations. We use bold-faced letters for vectors or matrices and lowercase letters for scalars, e.g. Sequence modeling. For convenience, we consider input sequences of infinite length (t ∈ Z). It is important to note, however, that our theoretical framework can be adapted to finite-length input sequences by masking distant tokens. Formally, the output sequence Y = (y t ) t∈Z ∈ R c×Z is generated from the input sequence X = (x t ) t∈Z ∈ X ⊂ R d×Z via an unknown mapping H • (•) dependent on the input sequence up to the prediction time, and this can be expressed as:EQUATION)Our objective is to learn the mapping H • (•). Additionally, we define the norm |||H||| := sup t∈Z sup X∈X ∥H t (X)∥. Without loss of generality, we assume ∥x t ∥ 2 ≤ 1 for any X ∈ X and set the output dimension c = 1 for simplicity.Long but sparse memories. To model such sequences, we define three types of memories: fixed, long but sparse memories; adaptive, long but sparse memories; and essentially sparse memories. These memory types are prevalent in sequence modeling tasks across diverse domains such as NLP, CV, signal processing, and sparse function representation. In Section 3, 4, and 5, we will formally define these different types and investigate Transformer's capacity to model them.Transformer network. Transformer (Vaswani et al., 2017 ) is a network architecture designed for processing sequences and generating predictions. Given an input sequence X, Transformer executes the following steps. Initially, each d-dimensional (dim) input token is transformed into a D-dim vector through an embedding mapping such as x (0)t = W E x t + b E , where W E ∈ R D×d , b E ∈ R D .Subsequently, a typical L-layer Transformer with residual block operates according to the formulation:EQUATIONAt the l-th layer, FFN (l) (•) denotes a standard (point-wise) two-layer ReLU networks with m neurons: for a given input x ∈ R D , FFN (l) (x) = m k=1 a (l) k σ b (l)⊤ k x + c (l)k , where σ(•) is the activation function such as ReLU. Additionally, in the final (L-th) FFN layer, the residual block is omitted, commonly referred to as the readout function. Moreover, Attn (l) (•) refers to a multi-head self-attention, as elaborated below.Multi-head self-attention. Our focus lies on standard dot-product Attn, denoted as Attn (l) (•) and consisting of H heads. When applied to an input sequence X, Attn operates as follows: (l,h) .Attn (l) (X) = W (l) O H h=1 W (l,h) V Xsoftmax c W (l,h) Q X, W (l,h) K X + R(3)Here, the parameters W(l,h) Q , W (l,h) K , W (l,h) V , W (l,h) Ocorrespond to the query, key, value, output matrices of the (l, h)-th head, respectively. softmax c represents taking softmax normalization across column. Furthermore, R (l,h) ∈ R Z×Z denotes the relative positional encoding matrix, which satisfies R (l,h) t,s = -∞ for t < s in the next-token prediction paradigm. Consequently, the t-th output of Attn is expressed as:Attn (l) t (X) = W (l) O H h=1 +∞ s=0 W (l,h) V x t-s exp W (l,h) Q x t , W (l,h) K x t-s + R (l,h) t,t-s +∞ j=0 exp W (l,h) Q x t , W (l,h) K x t-j + R (l,h) t,t-j .Logarithmic and Power relative positional encoding. As highlighted in Section A, among various types of RPEs, the RPEs used in T5 and KERPLE(log) demonstrate superior performance over Alibi, significantly outperforming other RPEs and APEs in the length generalization task (Kazemnejad et al., 2023; Chi et al., 2022) . This finding motivates our focus on the T5-type, KERPLE(log), and Alibi-type RPEs throughout this paper. All of these RPE matrices are Toeplitz, with the form of R t,s = r(t -s). Notably, for T5 and KERPLE(log), r(t -s) undergoes an initial linear decrease followed by a logarithmic decrease as the relative distance t -s increases (Please refer to Section G.1 for more details). In contrast, for Alibi, r(t -s) decreases linearly. Inspired by these discussions, we examine the following RPEs with different decay rates:ϕ log (z) = -log z, z ≥ 1 -∞, otherwise ; ϕ lin (z) = -z, z ≥ 0 -∞, otherwise.We will study Transformer with ϕ type RPE (type ∈ {log, lin}). Specifically, the RPE in the (l, h)-th head (3) is as follows: R (l,h) t,s := p (l,h) ϕ type (t -s),where p (l,h) ∈ R + is a trainable parameter.Remark 2.1. For standard Transformer (2) incorporating Attn (3) with RPE (4), the parameters are: the embedding matrix W E ; aEQUATIONk in the FFN layers;W (l,h) Q , W (l,h) K , W (l,h) V, p (l,h) ,W (l) Oin the Attn layers. Notably, the number of parameters is independent of the sequence length, thus enabling the model to handle input sequences of arbitrary length.Remark 2.2. In the subsequent sections, we will analyze Transformer and its variants. For the sake of brevity, some shorthand notations are introduced here. For examples, Transformer (2) using ϕ log /ϕ lin RPE (4) is referred to as "Transformer with log/lin-RPE"; Transformer with W (l,h) Q, W(l,h) K = 0 is called "dot-product-free Transformer".This paper delves into the expressive power of Transformer through the lens of approximation theory, with a specific focus on establishing explicit approximation rates for Transformers in modeling long but sparse memories.Approximation rates v.s. universal approximation. In approximation theory, results are generally categorized into two types: universal approximation (density-type) and approximation rates (Jacksontype) (Jackson, 1930) . Universal approximation investigates whether the hypothesis class is dense in the target class. Although this property is fundamental, it does not offer detailed insights into approximation efficiency. In contrast, approximation rates go deeper, emphasizing the efficiency of the approximation. A typical example within this framework is the approximation theory of two-layer neural networks (2NNs).Barron space of 2NNs. The well-known universal approximation result for 2NNs asserts that 2NNs can approximate any continuous function (Barron, 1992; 1993; 1994) . Nonetheless, this result lacks a characterization of the approximation efficiency, i.e., how many neurons are needed to achieve a certain approximation accuracy? This gap was addressed by the Barron space theory (E et al., 2019; 2021; Ma et al., 2020) . It is established that for any function within Barron space f ∈ B (Appendix G.2), 2NNs with m neurons (denoted by H m ) can approximate them efficiently, at a rate of inf fm∈Hm ∥f -f m ∥ ≤ O(∥f ∥ B / √ m), remarkably independent of the input dimension d, thus avoiding the Curse of Dimensionality (Bellman, 1966; Bach, 2017) .3 Fixed, long but M -sparse memories 3.1 Problem formulation Fixed, long but M -sparse memories. In this section, we investigate a fundamental category of long but sparse memories. Our focus is on scenarios where the positions of the sparse memories remain fixed and are independent of the tokens. The target function is represented by:EQUATIONwhere 1 ≤ T 1 < • • • < T M < +∞ signify the fixed positions of the memories. Despite the memories being fixed (token-independent) and sparse (finite M ), the task can still be complex due to the potentially long-range memories (T 1 , • • • , T M can be large enough).Examples. (I) For Boolean inputs, (5) aligns with sparse Boolean functions, also studied in (Edelman et al., 2022; Bhattamishra et al., 2022) . Notably, Bhattamishra et al. (2022) observed that Transformers outperform LSTMs in learning sparse parities. (II) Selecting the simplest case of T i = i in (5) corresponds to the traditional n-gram model, which consists of short and sparse memories.Target class. We focus on target functions described in (5). The readout function f is considered within the standard Barron space B, i.e., which can be effectively approximated by 2NNs. Moreover, we assume that f is Lipschitz, denoted by f ∈ L. Thus, we can focus more on investigating the memory extraction power of Transformer. Formally, we define the target class for modeling fixed, long but M -sparse memories as: H Fix := H : H t (X) = (5), where 1 ≤ T 1 < • • • < T M < +∞, f ∈ B ∩ L . (6)|||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type),whereE FFN = Õ ∥f ∥ B √ m and E Attn (type) =    O C(n) H n M i=1 e 0.01Ti n+1 , type = lin O C(n) H n M i=1 T 1.01 i n+1, type = log .Theorem 3.1 establishes the approximation rate of one-layer DP-free Transformer for modeling fixed, long but sparse memories. Here, the model complexity is governed by the number of Attn heads H and the width of FFN layers m, while the target complexity arises from the lengths of the memories T 1 , • • • , T M and the complexity of the readout function f . The approximation error comprises two components: the error in the FFN component E FFN and the error in the Attn component E Attn (type).The error E FFN aligns with classical results, showcasing its effectiveness in approximating Barron functions. On the other hand, E Attn (type) hinges on the capacity of the Attn block for modeling long-range memories. Specifically, with increasing memory length, the necessary number of Attn heads grows at a small exponential rate for lin-RPE and at a polynomial rate for log-RPE.The proof of Theorem 3.1 is deferred to Appendix B. We can draw some insights from Theorem 3.1 and its proof.Different roles of the Attn layer and the FFN layer. The Attn and FFN layers fulfill distinct roles in this task. Specifically, the FFN layer efficiently approximates the nonlinear readout function f , while the Attn layer is responsible for extracting the token x t-Ti by approximating the memory kernel I{• = T i }. These components together enable effective modeling of fixed, long, but sparse memories.Non-necessity of DP. Theorem 3.1 suggests that the DP component in Attn is not necessary and can be omitted for modeling fixed, long but sparse memories. This is due to the relative simplicity of modeling fixed memory kernels. In a more complex scenario in Section 4, the role of the dot-product becomes important. In contrast to Edelman et al. (2022) , which utilizes the property of DP to prove that Transformer can model sparse Boolean functions, our result reveals that one-layer Transformer can successfully tackle the same task even without the dot product in the attention layer.Effect of RPE types on expressivity. Our result indicates that the type of the RPE used in the Attn layer subtly influences the Transformer's ability to model long-range memories. As the range of the memory increases, the required head number grows at a slightly exponential rate for lin-RPE and at a polynomial rate for log-RPE. The subtle difference is attributed to the relative simplicity of approximating the memory kernel I{• = T i }. We will explore a more complex task in Section 5, where the impact of different types of RPE becomes even more pronounced.4 K-Adaptive, long but M -sparse memories 
problem formulation: 
 In this section, we delve into a more complex modeling scenario closely aligned with typical language processing tasks.K-Adaptive, long but M -sparse memories. This section investigates the scenario where the positions of the sparse memories are "adaptive", meaning they depend on the input tokens. The target function is formulated as:EQUATIONwhere the positions of the memory tokens t 1 , • • • , t M follow a nested relationship:t 1 = g 1 (x t ); t 2 = g 2 (x t , x t-t1 ); • • • ; t K+1 = g K+1 (x t , x t-t1 , • • • , x t-t K ); • • • ; t M = g M (x t , x t-t1 , • • • , x t-t K ).Here, M denotes the number of memory tokens, and K measures the nesting complexity in the memory structure. We assume that memory functions g i generate positive integers for the input tokens, and there exist maximum values T i such that g i ≤ T i . In this adaptive framework, each position of the memory token depends on multiple input tokens and is nested within other memory structures, leading to potential influence of later memory tokens by the earlier ones.To facilitate understanding, we first consider a warm-up case, i.e., K = 0 in (8). In this case, the positions of memories only depend on the current token, without interaction with each other. It can be represented as:EQUATIONt i = g(x i ), i ∈ [M ].Target class. The target classes for modeling adaptive, long but sparse memories in both warm-up and general cases are as follows:EQUATION)EQUATIONExamples. Adaptive memories are commonly encountered in practical scenarios. (I) Adaptive sparse Boolean functions, e.g.,y t = x t • x t-g(xt) • x t-g(x t-g(x t ) ), where X ∈ {±1} Z , g(x) = 1 for x = 1 and g(x) = 2 for x = -1. This fits within our framework (8) with K = M = 2. (II) Multi-step reasoning, e.g., modeling the K-adaptive, long, but K-sparse memories contains a complicated K-step reasoning task, which require the sequential search following the rule((• • • ((x t → x t-t1 ) → x t-t2 • • • ) → x t-t K-1 ) → x t-t K . (III)In NLP tasks like dependency parsing, part-of-speech tagging, sentiment analysis, or continuation writing, the positions of relevant prefix tokens usually depend on the context itself, and can vary depending the content. Additionally, the nested structure is a fundamental characteristic of natural language (Hawkins, 2021) .Transformer hypothesis class. Some previous works Yun et al. (2019) ; Kim et al. (2022) treated the softmax with normalization as an approximation of hardmax, suggesting the potential importance of the normalization. In contrast, in this section, we remove the normalization in the denominator of softmax and investigate its ability for sequence modeling. Additionally, to address the discreteness of time and memory values, we consider Transformer with specific precision, as detailed in Appendix C. The precision technique is widely used in LLM training (Kalamkar et al., 2019) , such as BFloat16.Formally, the hypothesis class is defined as follows, encompassing all normalization-free L-layer Transformer, configured with H Attn heads and FFN width m and using type-RPE and specific precision. such that: if the width satisfies m ≥ Ω M i=1 ∥g i ∥ 2 B , type = lin Ω M i=1 ∥log g i ∥ 2 B T 2 i , type = log, then the following approximation rate holds:|||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type),whereE FFN = Õ ∥f ∥ B √ m and E Attn (type) =    O C(n) H n M i=1 e 0.01Ti n+1 , type = lin O C(n) H n M i=1 T 1.01 i n+1, type = log .In Theorem 4.1, we present the approximation rate of two-layer Transformer for the warm-up case: modeling 1-adaptive, long but M -sparse memories. This theorem reveals that the approximation error comprises two distinct components: the error in the FFN component E FFN and the error in the Attn component E Attn (type). A critical difference from 3.1 is the presence of the condition related to the width m of FFN layers. This term arises from using the FFN layer to approximate the memory function g i . Owing to the discreteness of memory g i and the implementation of rounding operations, the approximation within rounding accuracy all achieves zero error after rounding, while it can not get correct rounding beyond this accuracy. In contrast, the error E FFN is caused by using FFN to approximate the readout function f , the same as E FFN in Theorem 3.1.The proof of Theorem 4.1 can be found in Appendix C.1. Theorem 4.1 and its proof offer several critical insights into the underlying mechanism of Transformer.Distinct roles of Attn layers and FFN layers. Our proof elucidates that the FFN layers are tasked with approximating the readout function f and memory functions g i , while the Attn layers are responsible for the extraction of the adaptive memories. It is essential to clarify the difference between "approximating memory functions" and "memory extraction". The former refers to utilizing some function to estimate the memory function g i , whereas the latter pertains to extracting the token x t-gi(xt) from the memory location.Cooperation between DP and RPE. In the 2-nd Attn layer, the extraction of the memory functions is achieved through an interplay between DP and RPE. Specifically, this is done through a nice interaction between the temporal space (provided by RPE) and the token space (provided by DP).Please refer to Appendix C.1 for more details.Rethinking DP in Attn. Our proof highlights that the core mechanism of Attn is to provide a nice interaction between the temporal space and the token space through the cooperation of DP and RPE. This leads us to the following question: Is DP in Attn necessary and replaceable? The following two propositions provide some hints.Proposition 4.2 (DP vs. DP-free (informal)). There exists a target H ∈ H Adap (1,1) (10) such that:(A) For any ϵ > 0, there exists a 1-layer Attn Attn DP such that H -Attn DP ≤ ϵ. Proposition 4.3 demonstrates the existence of a structurally simpler yet effective alternative to traditional DP for modeling (10). This alternative is proposed based on our insights into the role of Attn in facilitating the interaction between the temporal space and the token space. Specifically, we propose a more direct structure to achieve this interaction. More details are deferred to Appendix C.3.(B)Theorem 4.4 (Approximation rate, general case). For any target H ∈ H Adap (K,M ) , rate n ∈ N + , and H, m ∈ N + , there exists an L-layer (L = K + 1 + I{M ≥ K + 1}) Transformer TF ∈ T F type (L,H,m) (12) and a constant C(n) such that: if the width satisfies if the width satis-fies m ≥ Ω max i∈[K] ∨ M i=K+1 ∥g i ∥ 2 B , type = lin, Ω max i∈[K] ∨ M i=K+1 ∥log g i ∥ 2 B T 2 i , type = log, then the following approximation rate holds:|||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type), whereE FFN = Õ ∥f ∥ B √ m ,E Attn (type)=    O C(n) H n K l=1 e 0.02(n+1)T l + M l=K+1 e 0.01T l 2n+2 ,type = lin O C(n) H n K l=1 T 2.02(n+1) l + M l=K+1 T 1.01 l 2n+2 ,type = log .In Theorem 4.4, we establish the approximation rate of deep Transformer for modeling K-adaptive, long but M -sparse memories. Similar to that in Theorem 4.1, the approximation error divides into two distinct terms. A key difference from Theorem 4.1 is the impact of the nested relationships among the memory functions on the required number of layers, Attn heads, and the width of FFN layers. The nested structure within the initial K memories mandates sequential processing in the first K layers one by one. If M ≥ K + 1, then in the K + 1-th layer, the remaining M -K non-nested memory functions t K+1 , • • • , t M are concurrently processed. The proof of Theorem 4.4 is deferred to Appendix D.1.Distinct roles of the number of layers L, the number of Attn heads H, and the width of FFN layers m. Theorem 4.4 and its proof highlight the distinct roles of three key hyper-parameters of Transformer: L, H, and m. Deeper Transformer are capable of handling the memories with more intricate nested relationships, requiring a K + 1 layer network for a nesting complexity of K. In contrast, the number of heads and width needed is dictated by the individual complexity of memory functions themselves (∥g i ∥ B ,∥log g i ∥ B , T i for memory g i ), necessitating that each layer's Attn heads and FFN width are sufficient to capture the memory functions extracted in that layer. This understanding is quite intuitive: If the content of the next token relies on a few previous tokens in an independent way, we can treat each such dependence with a separate attention head. There is no need for many layers.Mitigating required head and width with depth. Recalling Theorem 4.1, the memories lacking nested relationships can be efficiently approximated by 2-layer Transformer with a sufficient number of heads and width. The subsequent proposition further explores how increasing the depth of Transformer can influence its efficiency for modeling memories without nested relationships. C(n) such that: if the width satisfies m ≥ Ω max i∈[K] ∥g i ∥ 2 B , type = lin, Ω max i∈[K] ∥log g i ∥ 2 B T 2 i , type = log, then the following approximation rate holds:|||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type),whereE FFN = Õ ∥f ∥ B √ m and E Attn (type) =    O C(n) H n K l=1 e 0.02(n+1)T l , type = lin O C(n) H n K l=1 T 2.02(n+1) l , type = log .Upon comparing Proposition 4.5 with Theorem 4.1, a notable distinction becomes evident between 2-layer and M + 1-layer Transformer in terms of the requirement of the number of Attn heads and the width of FFN layers. Specifically, for 2-layer Transformer, the required width is proportionally linked to the sum of all the memory functions' complexity (∥g i ∥ B , ∥log g i ∥ B , T i for memory function g i ).In contrast, for M + 1-layer Transformer, the required width correlates with the maximum complexity of the memory functions, much lower than that for 2-layer Transformer. Similarly, the required number of heads for M + 1-layer Transformer is much fewer than that for 2-layer Transformer. Please refer to Appendix D.2 for a detailed comparison. The observation suggests that increased depth can significantly reduce the demands on the number of heads and the width. The underlying reason is that deep networks can distribute the memories across different layers for processing, with each layer focusing on approximating only a single memory function.5 Essentially M -sparse memories 
problem formulation: 
 In language tasks, each token possesses clear semantic meaning. As a result, the structure of the memory is sparse in the original space. This aligns well with our modeling assumptions discussed in Section 3 and 4. However, in other machine learning tasks, we may encounter situations where the input tokens lack distinct semantic meaning. This might happen in image processing or classical signal processing. In these situations, the memory structure could potentially be dense in the original space. Nonetheless, the memory structure might exhibit sparsity in some transformed domain. We call such memory structure "essentially sparse". In this section, we study the situation in which the memory structure in long-ranged but essentially sparse. For simplicity, we consider the situation in which the positions of the memory kernels are fixed. The analysis can be easily extended to the situation with an adaptive memory structure.Fixed, essentially M -sparse memory. Consider the following situation:EQUATIONwhereρ 1 (•), • • • , ρ M (•) ∈ ℓ 1 (N)serve as memory kernels, and (X * ρ k )(t) = +∞ s=0 x t-s ρ k (s) denotes the convolution of the inputs with kernel ρ k .Target class and Transformer hypothesis class. The target class for modeling essentially sparse memories is defined as:EQUATION)For the hypothesis class, we consider one-layer dot-product-free Transformer with Attn head number H and FFN width m, as defined in (7).Examples. Essentially sparse memories are prevalent in real-world scenarios:(I) Image Tasks. In CV, a fundamental objective is identifying and representing meaningful "features", such as ears, nose, etc. These features can often be modeled using convolution kernels, leading to a task in the form y = f (X * ρ eye , X * ρ nose , X * ρ ear ). This is an extension of the task we discussed above, in which the kernel functions {ρ j } are data-dependent ("adaptive" in the terminology used in the previous section).(II) Signal processing. In signal processing, it is commonly the case that the signals are highly sparse under Wavelet or Fourier transforms. For instance, let ψ(•) be a wavelet function and define ψ a,b (t) := ψ( t-b a )/ |a|. Then we have y = f (X * ψ a1,b1 , • • • , X * ψ a M ,b M ) where (a 1 , b 1 ), • • • , (a M , b M ) might be data-dependent.(III) Mathematical calculation. Consider algebraic operations where memory exhibits sparsity under specific linear transformations. For example, y t = 10x t + x t-4 /( 100 s=0 w s x t-10-s ) -+∞ s=0 v s x t-100-s can be represented in our framework as y = f (X * ρ 1 , • • • , X * ρ 4 ), where each ρ i represents a specific linear transformation.Theorem 5.1 (Approximation rates). (A) Consider H Ess (14) with exponentially decayed memory kernels, i.e., there exists β > 0 such that whereρ 1 (t), • • • , ρ M (t) = O(e -βtE FFN = Õ ∥f ∥ B √ m , E Attn = O C(n)M n+1 H n .Theorem 5.1 illustrates that one-layer DP-free Transformer with lin-RPE is effective in modeling essentially sparse memories with exponentially decayed kernels, and one-layer DP-free Transformer with log-RPE can efficiently model the memories with polynomially decayed kernels. A key difference between Theorem 5.1 and Theorem 3.1 lies in the memory kernels they address. In Theorem 5.1, the Attn layer should approximate general memory kernels ρ i (•), instead of approximating indicator kernels I{• = T i } in Theorem 3.1. The proof of Theorem 5.1 can be found in Appendix E.Overcoming the Curse of Memory (CoM). For recurrent neural networks (RNN), it was discovered (Li et al., 2021; 2022) that both approximation and optimization become exceedingly difficult when the target has long-term memory. This phenomenon is referred as the "curse of memory", or "CoM". It was shown in (Li et al., 2021; 2022) that RNN requires an exponentially large number of neurons to approximate targets with heavy-tailed memory kernels, such as the ones that exhibit polynomial decay. In contrast, Theorem 5.1 reveals that Transformer with log-RPE efficiently handles polynomial decaying memory kernels, requiring only a polynomial number of neurons for effective approximation. This finding theoretically elucidates the superior performance of T5's RPE and KERPLE(log) in length generalization task in practice (Section G.1). 
experimental validation: 
 As summarized in Section 1, our theoretical analysis reveals novel insights into the expressive power and mechanisms of Transformer. To validate these insights, we conduct experiments ranging from simple toy models to more complex language model pre-training. Due to space constraints, detailed experimental validation and practical implications of our insights are presented in Appendix H. 
conclusion and future work: 
 In this work, we investigate theoretically the expressive power and the mechanisms of Transformer for modeling long but sparse memories. Our analysis establishes explicit approximation rates and offers much-needed insights into the functionalities of the various components of Transformer. However, we still have a long way to go for a full theoretical understanding of Transformer. For instance, although we have investigated the mechanisms of Transformer in terms of expressive power, the evolution of the mechanisms during the training process remains elusive. Recent studies revealed that Transformer exhibits multi-phase learning dynamics (Boix-Adsera et al., 2023) and undergoes phase transitions (Olsson et al., 2022) during training, akin to the phenomenon of learning with increasing complexity in classical neural networks (Kalimeris et al., 2019; Xu et al., 2019; Rahaman et al., 2019; Abbe et al., 2023a; Wang and Ma, 2023) . These and other issues will be studied in future work. Giannou et al. (2023) showed that looped Transformer can implement practical computer programs. Jiang and Li (2023) provided explicit approximation rates for Transformer in sequences modeling with inherent graph structures. Liu et al. (2022) found that Transformer can execute finite-state automata. Ma and Ying (2022) asserted the natural suitability of Attn for achieving permutation equivariance. Besides these affirmative results, several studies characterized the expressivity limitation of Transformers, particularly in modeling formal languages or simulating circuits (Hahn, 2020; Weiss et al., 2021; Bhattamishra et al., 2020; Merrill and Sabharwal, 2023b; Merrill et al., 2022) . Additionally Feng et al. (2023) ; Merrill and Sabharwal (2023a) examined the expressivity of Transformer using Chain of Thought prompting (Wei et al., 2022b) . Moreover, some studies showed that the in-context learning ability of Transformer is attainable by simulating gradient-based iterations across various layers (Garg et al., 2022; Akyürek et al., 2022; von Oswald et al., 2023; Von Oswald et al., 2023; Mahankali et al., 2023; Bai et al., 2023; Shen et al., 2023) . Besides, experimental studies also provide insights into the mechanisms of Transformer through induction head (Elhage et al., 2021; Olsson et al., 2022) , information flow (Wang et al., 2023) , anchor functions (Zhang et al., 2024) , etc.Positional encoding. One core component of Transformer is the PE, which facilitates the representation of input sequence order. Theoretically, Transformer without PE lacks UAP and is restricted to representing permutation-invariant functions. PE was first introduced in Vaswani et al. (2017) . It has limitations in encoding unseen positions. To overcome this difficulty, Shaw et al. (2018) (Raffel et al., 2020) , Rotary RPE (Su et al., 2024) (utilized in PaLM (Chowdhery et al., 2023) and LlaMA (Touvron et al., 2023) ), Alibi RPE (Press et al., 2022) (employed in BLOOM (Workshop et al., 2022) ), and KERPLE (Chi et al., 2022) . A prevailing belief is that RPEs can outperform APEs in the "length generalization task" (Ontanón et al., 2022; Csordás et al., 2021) -the ability to generalize from smaller training contexts to larger ones, a critical challenge for Large Language Models (Anil et al., 2022; Abbe et al., 2023b) . However, Press et al. (2022) revealed that the commonly used Rotary RPE may exhibit suboptimal performance in this task. The recent work (Kazemnejad et al., 2023; Chi et al., 2022) conducted systematic experiments comparing the length generalization capabilities of Transformers with various RPEs and APEs, suggesting that the RPEs used in T5 and KERPLE(log) demonstrate superior performance over other types.Rethinking dot-product. Another critical component of Transformer is the DP structure. Due to its quadratic cost as a function of the sequence length, the necessity of DP has always been questioned. Numerous variants of DP have been proposed, demonstrating competitive performance across diverse tasks. Representative examples include Longformer (Beltagy et al., 2020) , Big Bird (Zaheer et al., 2020) , Reformer (Kitaev et al., 2020) , Linformer (Wang et al., 2020) , Performer (Choromanski et al., 2020) , Synthesizer (Tay et al., 2021) , etc. In particular, a recent study (Allen-Zhu and Li, 2023) compared standard and DP-free Transformers in modeling "context-free grammar". Their findings suggested that the presence of DP has a marginal impact on performance. These evidences motivate us to rethink the necessity of DP in Transformer.Sparsity (Donoho, 2006; Candès and Wakin, 2008) has gained considerable attention in sequence modeling. In classical signal processing, there is a prevailing notion that valuable signals are extremely sparse. For example, when representing an image, one often finds that only a few wavelet coefficients hold significant values in wavelet space (Meyer, 1992) . In NLP, the starting point off the traditional n-gram model (Shannon, 1948) is that the next token only relies on a few previous tokens. Such models, however, overlook long-range information, often resulting in suboptimal performance. For NLP tasks such as dependency parsing (Nivre and Scholz, 2004) , sentiment analysis (Nasukawa and Yi, 2003) , part-of-speech tagging (Francis and Kucera, 1979) , and continuation writing (Brown et al., 2020; OpenAI, 2023) , it is indeed often the case that only a limited subset of preceding information is crucial for accurate prediction. However, these relevant information can be quite distant. For instance, the resolution of a mystery novel may hinge on elements introduced at the outset. Moreover, for Transformer networks, extensive research into the visualization and interpretability has revealed that (i) the learned activation maps of FFN layers are extremely sparse (Li et al., 2023) ; (ii) the learned self-attention matrices exhibit notable sparsity, yet it does not closely resemble a diagonal configuration (Elhage et al., 2021) . These observations suggest that the prediction of the next token is influenced by a small number of previous tokens which might be far away. Therefore, being able to represent sparse but long-range dependence is important for sequence modeling. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: In Section H.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We have confirmed that the research is conducted with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]Justification: [NA] 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: In this subsection, we give the detailed proofs of fixed, long but sparse memory:y t = f (x t , x t-T1 , • • • , x t-T M ),where 1 ≤ T 1 < • • • < T M < +∞ signify the fixed positions of the memories. Theorem B.1 (Restatement of Theorem 3.1). For any target H ∈ H Fix (6), rate n ∈ N + , and H, m ∈ N + , there exists a 1-layer Transformer TF ∈ T F DPF,type (1,H,m) (7) and a constant C(n) such that|||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type),whereE FFN = Õ ∥f ∥ B √ m and E Attn (type) =        O C(n) H n M i=1 e 0.01Ti n+1 , type = lin O C(n) H n M i=1 T 1.01 i n+1 , type = log . Proof of Theorem B.1.First, we choose the embedding dimension D = (M + 1)d, and select the simple embeddingW E = (I d×d , 0) ⊤ ∈ R D×d , b E = 0 ∈ R D .Then for any input sequence X = (x t ) t∈Z , the token after embedding satisfies:x E t = W E x t + b E = (x ⊤ t , 0 ⊤ ) ⊤ ∈ R D .For one-layer Dot-product-free Transformer TF ∈ T F DPF,type(1,H,m)with ϕ type , the output token TF t (X) of t-th input token x t satisfies:x (1/2) t = x (0) t + W (1) O H h=1 Attn (1,h) t (X (0) ), x (1) t = FFN (1) (x (1/2) t ) where Attn (1,h) t (X) = W (1,h) V +∞ s=0 x t-s exp p (1,h) ϕ type (s) +∞ j=0 exp p (1,h) ϕ type (j). This proof can be summarized as the following process:• • • x E t • • • Step I. Attn layer ↓ • • • x (1/2) t ≈ (x ⊤ t , x ⊤ t-T1 , • • • , x ⊤ t-T M ) ⊤ • • • Step II. FFN layer ↓ • • • x (1) t ≈ f (x t , x t-T1 , • • • , x t-T M ) • • •Now we give the formal proof.Step I. Extract the memory locations by (Dot-product-free) Attn layer.We consider to use H k attention heads (fromk-1 i=1 H i + 1-th head to k i=1 H i -th head) to extract it, and it satisfies to M k=1 H k = H.For simplicity, we denote the following projection matrices:P (k) := (0 d×kd I d×d 0) ∈ R d×D , 1 ≤ k ≤ M. P (k) ⊥ := I kd×kd 0 d×d 0 0 0 d×d I (M -k)d×(M -k)d ∈ R M d×D , 1 ≤ k ≤ M. Now we consider the extraction of k-th memory x t-T k (1 ≤ k ≤ M ).• Case type = lin.By Lemma F.1, for any rate n ∈ N + , there exists an constant C(n) and a functionϕ exp k (t) = k-1 i=1 Hi+1≤h≤ k i=1 Hi α h e -β h t such that β h > 0 and ∥I{• = T k } -ϕ exp k (•)∥ ℓ1(N) = +∞ s=0 |I{s = T k } -ϕ exp k (s)| ≤ C(n) e 0.01(n+1)T k H n k .Therefore, for these attention heads (k-1 i=1 H i + 1 ≤ h ≤ k i=1 H i ), we can choose p (1,h) = β h , W (1,h) V = α h   +∞ j=0 exp(-β h j)   δ d×d (k+1,1) ,where δ (k+1,1) ∈ R D×D means that: it equals to I d×d for the (k + 1, 1)-th d × d blocks, and 0 d×d for the other d × d blocks.Then it holds that:k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h s 0 kd x t-s 0 ∈ R D .This implies:P (k) k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h s x t-s , P (k) ⊥ k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = 0,moreover, the following estimate holds:P (k) k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) -x t-T k 2 = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h s x t-s -x t-T k 2 = +∞ s=0   k i=1 Hi h= k-1 i=1 Hi+1 α h e -β h s -I{s = T k }   x t-s 2 ≤ +∞ s=0 k i=1 Hi h= k-1 i=1 Hi+1 α h e -β h s -I{s = T k } = ∥ϕ exp k (•) -I{• = T k }∥ ℓ1(N) ≤ C(n) e 0.01(n+1)T k H n k .• Case type = log.By Lemma F.4, for any rate n ∈ N + , there exists an constant C(n) and a functionϕ poly k (t) = k-1 i=1 Hi+1≤h≤ k i=1 Hi α h t -β h , such that β h > 1 and I{• = T k } -ϕ poly k (•) ℓ1(N+) = +∞ s=1 I{s = T k } -ϕ poly k (s) ≤ C(n) T 1.01(n+1) k H n k .Therefore, for these attention heads ( 1) , where δ (k+1,1) ∈ R D×D means that: it equals to I d×d for the (k + 1, 1)-th d × d blocks, and 0 d×d for the other d × d blocks.k-1 i=1 H i + 1 ≤ h ≤ k i=1 H i ), we can choose p (1,h) = β h , W (1,h) V = α h   +∞ j=1 j -β h   δ (k+1,Then it holds that:P (k) k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=1 s -β h x t-s , P (k) ⊥ k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = 0,moreover, the following estimate holds:k i=1 Hi h= k-1 i=1 Hi+1 P (k) Attn (1,h) t (X (0) ) -x t-T k 2 = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=1 s -β h x t-s -x t-T k 2 = +∞ s=1   k i=1 Hi h= k-1 i=1 Hi+1 α h s -β h -I{s = T k }   x t-s 2 ≤ +∞ s=1 k i=1 Hi h= k-1 i=1 Hi+1 α h s -β h -I{s = T k } = ϕ poly k (•) -I{• = T k } ℓ1(N+) ≤ O C(n) T 1.01(n+1) k H n k .Then we combine the results for all k ∈ [M ] for these two cases. By choose W O = I D , we have:x (1/2) t -     x t x t-t1 . . . x t-t M     2 =     x t 0 d . . . 0 d     + M h=1 Attn (1,h) t (X) -     x t x t-t1 . . . x t-t M     2 = M h=1 Attn (1,h) t (X) -     0 d x t-t1 . . . x t-t M     2 = M k=1   k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X) - 0 kd x t-T k 0 d   2 ≤ M k=1 k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X) - 0 kd x t-T k 0 d 2 = M k=1 k i=1 Hi h= k-1 i=1 Hi+1 P (k) Attn (1,h) t (X) -x t-T k 2 ≤E Attn (type) :=    C(n) M k=1 e 0.01(n+1)T k H n k , type = lin C(n) M k=1 T 1.01(n+1) k H n k , type = log .Consequently, one detail is to assign the head number {H k } M k=1 such that the error's sum E Attn (type) is as small as possible. Our way is solving the minimization problem:min H1,••• ,H M : E Attn (type) s.t. M k=1 H k = H,which suggests that we should choose the head number:H k = e 0.01T k M j=1 e 0.01Tj H, k ∈ [M ], type = lin; H k = T 1.01 k M j=1 T 1.01 j H, k ∈ [M ], type = log .Thus, we obtain the bound in Step I:E Attn (type) ≤            C(n) H n M k=1 e 0.01T k n+1 , type = lin C(n) H n M k=1 T 1.01 k n+1 , type = log . Furthermore, by choosing E Attn (type) ≤ 1, it holds that x (1/2) t ∞ ≤ x (1/2) t -     x t x t-t1 . . . x t-t M     ∞ +     x t x t-t1 . . . x t-t M     ∞ ≤ E Attn (type) + 1 ≤ 2.Step II. Approximate the readout function by FFN layer.In this step, we aim to approximate the function f using two-layer network. By Lemma G.6, there exists a two layer neural network with m neurons defined onR D FFN (1) (y) = m k=1 a k σ(b ⊤ k y + c k )such thatE FFN := FFN (1) -f L ∞ ([-2,2] D ) ≤ Õ ∥f ∥ B √ m .The final bound.For any t and X ∈ X , it holds thatH t (X) -x (1) t = f (x t , x t-t1 , • • • x t-t M ) -FFN (1) x (1/2) t = f (x t , x t-t1 , • • • x t-t M ) -f x (1/2) t + f x (1/2) t -FFN (1) x (1/2) t ≤ f (x t , x t-t1 , • • • x t-t M ) -f x (1/2) t + f x (1/2) t -FFN (1) x (1/2) t ≤ ∥f ∥ Lip x ⊤ t , x ⊤ t-t1 , • • • x ⊤ t-t M -x (1/2) t 2 + f -FFN (1) L ∞ ([-2,2] D ) ≤ ∥f ∥ Lip • E Attn (type) + E FFN ,whereE FFN = Õ ∥f ∥ B √ m ; E Attn (type) =            O C(n) H n M k=1 e 0.01T k n+1 , type = lin O C(n) H n M k=1 T 1.01 k n+1 , type = log .Due to the arbitrariness of t and X, the proof is completed.In this section, we give the detailed proofs of the approximation theory of Transformer for modeling the warm-up case of adaptive, long but sparse memory:y t = f (x t , x t-t1 , • • • , x t-t M ),where the adaptive memory satisfies to:t k = g k (x t ), k ∈ [M ].Moreover, g k (•) generate positive integers for the input tokens, and there exist maximum values T k such that 1 ≤ g k (x t ) ≤ T k holds for any x t and k ∈ [M ].To tackle the discrete values of the time and the memory values g k (x t ), a modified version of standard FFN, termed "FFN with precision", us cibsudered. This approach ensures that the output of FFN undergoes a simple rounding operation. Notably, the precision technique is widely used in LLM training (Kalamkar et al., 2019) , such as BFloat16. Specifically, for Transformer using RPE with type, we use the following FFN with precision:EQUATIONwhere [•] signifies rounding to the nearest integer, i.e., [x] = arg minn∈Z |n -x| (x ∈ R).It is important to note that the rounding obtained by using the operator log[exp(z)], used in (15), is quite fine, which is much finer than the vanilla rounding obtained by [z]. To elaborate, the following proposition is presented: Proposition C.1. For any z ≥ 1, the following holds: (i) | log[exp(z)] -z| ≤ 1 2 min{e z , [e z ]} ; (ii) |[z] -z| ≤ 1 2 . C.≥    Ω M i=1 ∥g i ∥ 2 B , type = lin Ω M i=1 ∥log g i ∥ 2 B T 2 i , type = log, then the following approximation rate holds:|||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type),whereE FFN = Õ ∥f ∥ B √ m and E Attn (type) =        O C(n) H n M i=1 e 0.01Ti n+1 , type = lin O C(n) H n M i=1 T 1.01 i n+1 , type = log . Proof of Theorem C.2.First, we choose the embedding dimension D = (M + 1)(d + 1), and select a simple embeddingW E = (I d×d , 0) ⊤ ∈ R D×d , b E = 0 ∈ R D .Then for any input sequence X = (x t ) t∈Z , the token after embedding satisfies:x (0) t = W E x t + b E = (x ⊤ t , 0 ⊤ ) ⊤ ∈ R D .To tackle the discrete values of g m (x t ), we utilize FFN, FFN with precision (15). It ensures that the output of FFN undergoes a simple rounding operation.Thus, for two-layer normalization-free Transformer TF ∈ T F NF,type (2,H,m) with ϕ type , the output token x(2) t of t-th input token satisfies:x (1/2) t = x (0) t + W (1) O H h=1 Attn (1,h) t (X (0) ), x (1) t = x (1/2) t + FFN (1) (x (1/2) t ), x (3/2) t = x (1) t + W (2) O H h=1 Attn (2,h) t (X (1) ), x (2) t = FFN (2) (x (3/2) t ),whereAttn (l,h) t (X) = W (l,h) V +∞ s=0 x t-s exp W (l,h) Q x t , W (l,h) K x t-s + p (l,h) ϕ type (s) .This proof can be summarized as the following process:• Case type = lin. x (0) t Step I. 1-st Attn ↓ x (1/2) t = x (0) t Step II. 1-st FFN ↓ x (1) t = (x ⊤ t , 0 ⊤ , g 1 (x t ), • • • , g M (x t ), 1) ⊤ Step III. 2-st Attn ↓ x (3/2) t ≈ (x ⊤ t , x ⊤ t-g1(xt) , • • • , x ⊤ t-g M (xt) , g 1 (x t ), • • • , g M (x t ), 1) ⊤ Step IV. 2-st FFN ↓ x (2) t ≈ f (x t , x t-g1(xt) , • • • , x t-g M (xt) ) • Case type = log. x (0) t Step I. 1-st Attn ↓ x (1/2) t = x (0) t Step II. 1-st FFN ↓ x (1) t = (x ⊤ t , 0 ⊤ , log g 1 (x t ), • • • , log g M (x t ), log 2) ⊤ Step III. 2-st Attn ↓ x (3/2) t ≈ (x ⊤ t , x ⊤ t-g1(xt) , • • • , x ⊤ t-g M (xt) , log g 1 (x t ), • • • , log g M (x t ), log 2) ⊤ Step IV. 2-st FFN ↓ x (2) t ≈ f (x t , x t-g1(xt) , • • • , x t-g M (xt) )Now we give the formal proof.Step I. Identity map.For the first Attn layer, we only need to do the identity map by taking W(1) 0 = 0. Then x (1/2) t = x (0) t .Step II. Approximate the adaptive memory function by the first FFN layer.• Case type = lin. Our main idea is that using the first FFN layer to express(x ⊤ t , 0 ⊤ , g 1 (x t ), • • • , g M (x t ), 1) ⊤ exactly. First, we consider to approximate the r-th memory function g r (x) by standard FFN.For any r ∈ [M ], by Lemma G.6, there exists a two-layer neural network with m r neuronsf 2NN (1,r) (x) = mr k=1 a (1,r) k σ b (1,r) k ⊤ x + c (1,r) k defined on R d such that g r -f 2NN (1,r) L ∞ ([-1,1] D ) ≤ Õ ∥g r ∥ B √ m r .Therefore, if we chooseÕ ∥g r ∥ B √ m r < 1 2 ,the following holds:g r (x t ) -f 2NN (1,r) (x t ) ≤ g r -f 2NN (1,r) L ∞ ([-1,1] d ) < 1 2 , Noticing g r (x t ) ∈ N + , we have f 2NN (1,r) (x t ) = g r (x t ), which implies: f 2NN (1,r) (x t ) = f 2NN (1,r) (x t ) = g r (x t ).Consequently, in order to construct the form (0⊤ , g 1 (x t ), • • • , g M (x t ), 1) ⊤ ∈ R D , we need to arrange the parameters a (1,r) k , b(1,r) k, and c(1,r) k (k ∈ [m r ], r ∈ [M ]) appropriately. Denote b(1,r) k = (b (1,r) k ⊤ , 0 ⊤ ) ⊤ ∈ R D for k ∈ [m r ], r ∈ [M ].Consider the following two-layer neural network with 1 + M r=1 m r neurons defined on R D :FFN (1) (x) = M r=1 1+ r-1 j=0 mj ≤k≤ r j=0 mj e D-M +r-1 a (1,r) k σ b(1,r) k ⊤ x + c (1,r) k + e D • 1 • σ(0 + 1).It is easy to verify that for any x(1/2) t, it holds thatFFN (1) (x (1/2) t ) = FFN (1) (x (0) t ) = M r=1 1+ r-1 j=0 mj ≤k≤ r j=0 mj e D-M +r-1 a (1,r) k σ b(1,r) k ⊤ x (0) t + c (1,r) k + e D • 1 • σ(0 + 1) = M r=1 1+ r-1 j=0 mj ≤k≤ r j=0 mj e D-M +r-1 a (1,r) k σ b (1,r) k ⊤ x t + c (1,r) k + e D • 1 • σ(0 + 1) = M r=1 e D-M +r-1 f 2NN r (x t ) + e D =(0 ⊤ d , f 2NN (1,1) (x t ), • • • , f 2NN (1,M ) (x t ), 1) ⊤ ∈ R D .Moreover, it satisfies thatFFN (1) (x (1/2) t ) = FFN (1) (x (1/2) t ) =(0 ⊤ d , f 2NN (1,1) (x t ) , • • • , f 2NN (1,M ) (x t ) , 1) ⊤ =(0 ⊤ d , g 1 (x t ), • • • , g M (x t ), 1) ⊤ ∈ R D .Thus, we have achieved our goal in this step:x(1)t = x (1/2) t + FFN (1) (x (1/2) t ) = (x ⊤ t , 0 ⊤ , g 1 (x t ), • • • , g M (x t ), 1) ⊤ .• Case type = log. Our main idea is that using the first FFN layer to express(x ⊤ t , 0 ⊤ , log g 1 (x t ), • • • , log g M (x t ), log 2) ⊤ exactly. First, we consider to approximate the r-th memory function log g r (x) by standard FFN.For any r ∈ [M ], by Lemma G.6, there exists a two-layer neural network with m r neuronsf 2NN (1,r) (x) = mr k=1 a (1,r) k σ b (1,r) k ⊤ x + c (1,r) k defined on R d such that log g r -f 2NN (1,r) L ∞ ([-1,1] D ) ≤ Õ ∥log g r ∥ B √ m r .Therefore, if we chooseÕ ∥log g r ∥ B √ m r < 1 4T r ,the following holds:log g r (x t ) -f 2NN (1,r) (x t ) ≤ g r -f 2NN (1,r) L ∞ ([-1,1] d ) < 1 4T r , which ensures exp f 2NN (1,r) (x t ) -g r (x t ) = exp f 2NN (1,r) (x t ) -exp (log (g r (x t ))) ≤ exp max f 2NN (1,r) (x t ), log (g r (x t )) f 2NN (1,r) (x t ) -log (g r (x t )) ≤ exp log g r (x t ) + 1 4 1 4T r ≤e 1/4 • T r • 1 4T r < 1 2 . Noticing g r (x t ) ∈ N + , we have exp f 2NN (1,r) (x t ) = g r (x t ), which implies: f 2NN (1,r) (x t ) = log exp f 2NN (1,r) = log g r (x t ).Consequently, in order to construct the form (0 ⊤ , log g 1 (x t ), • • • , log g M (x t ), log 2) ⊤ , we need to arrange the parameters a(1,r) k , b (1,r) k, and c(1,r) k (k ∈ [m r ], r ∈ [M ]) appropriately. Denote b(1,r) k = (b (1,r) k ⊤ , 0 ⊤ ) ⊤ ∈ R D for k ∈ [m r ], r ∈ [M ].Consider the following two-layer neural network with 1 + M r=1 m r neurons defined on R D :FFN (1) (x) = M r=1 1+ r-1 j=0 mj ≤k≤ r j=0 mj e D-M +r-1 a (1,r) k σ b(1,r) k ⊤ x + c (1,r) k + e D • 1 • σ(0 + log 2).It is easy to verify that for any x(1/2) t, it holds thatFFN (1) (x (1/2) t ) = FFN (1) (x (0) t ) = M r=1 1+ r-1 j=0 mj ≤k≤ r j=0 mj e D-M +r-1 a (1,r) k σ b(1,r) k ⊤ x (0) t + c (1,r) k + e D • 1 • σ(0 + log 2) = M r=1 1+ r-1 j=0 mj ≤k≤ r j=0 mj e D-M +r-1 a (1,r) k σ b (1,r) k ⊤ x t + c (1,r) k + e D • 1 • σ(0 + log 2) = M r=1 e D-M +r-1 f 2NN r (x t ) + e D log 2 =(0 ⊤ d , f 2NN (1,1) (x t ), • • • , f 2NN (1,M ) (x t ), log 2) ⊤ ∈ R D .Moreover, it satisfies thatFFN (1) (x (1/2) t ) = log exp FFN (1) (x (1/2) t ) =(0 ⊤ d , log exp f 2NN (1,1) (x t ) , • • • , log exp f 2NN (1,M ) (x t ) , log 2, 0 ⊤ ) ⊤ =(0 ⊤ d , log g 1 (x t ), • • • , log g M (x t ), log 2) ⊤ .Thus, we have achieved our goal in this step:x(1)t = x (1/2) t + FFN (1) (x (1/2) t ) = (x ⊤ t , 0 ⊤ , log g 1 (x t ), • • • , log g M (x t ), log 2) ⊤ .As established in the proof above, the width m must satisfy:m ≥ 1 + M r=1 m r =    Ω M r=1 ∥g r ∥ 2 B , type = lin Ω M r=1 ∥log g r ∥ 2 B T 2 r , type = log .Step III. Extract the adaptive memories by the second Attn layer.We consider to use H k attention heads (fromk-1 i=1 H i + 1-th head to k i=1 H i -th head)to extract it, and it satisfies toM k=1 H k = H.For simplicity, we denote the following projection matrices in R D×D :P (k) := (0 d×kd I d×d 0) ∈ R d×D , 1 ≤ k ≤ M ; P (k) ⊥ := I kd×kd 0 d×d 0 0 0 d×d I (D-(k+1)d)×(D-(k+1)d) ∈ R (D-d)×D , 1 ≤ k ≤ M ; Q (M ) := I (M +1)d×(M +1)d 0 ∈ R (M +1)d×D . Now we consider the extraction of k-th adaptive memory x t-g k (xt) (1 ≤ k ≤ M ).• Case type = lin.By Lemma F.2, for any rate n ∈ N + , there exists a constant C(n) and a functionϕ exp k (t; B) = k-1 i=1 Hi+1≤h≤ k i=1 Hi α h exp(-β h (t -B)) = k-1 i=1 Hi+1≤h≤ k i=1 Hi α h exp β h B -β h t such that β h > 0 and sup 1≤B≤T k ∥I{• = B} -ϕ exp k (•; B)∥ ℓ1(N) ≤ C(n)e 0.01(n+1)T k H n k .Moreover, Noticing that 1 ≤ g k (x t ) ≤ T k holds for any X = (x t ) t∈Z ∈ X , the following holds:sup X ∥I{• = g k (x t )} -ϕ exp k (•; g k (x t ))∥ ℓ1(N) ≤ sup 1≤B≤T k ∥I{• = B} -ϕ exp k (•; B)∥ ℓ1(N) ≤ C(n)e 0.01(n+1)T k H n k .Therefore, for these attention heads (k-1 i=1 H i + 1 ≤ h ≤ k i=1 H i ),we can choose:EQUATIONO = I D×D , W (2,h) V = α h δ (d×d) (k+1,1) ∈ R D×D , W (2,h) Q = β h δ (1×1) (D-M +k-1,1) ∈ R D×D , W (2,h) K = β h δ (1×1) (D,1) ∈ R D×D ,where δ (r×r) (p1,p2) means that: it equals to I r×r for the (p 1 , p 2 )-th r × r blocks, and 0 r×r for the other r × r blocks.Then it is easy to verify:W (2,h) Q x (1) t , W (2,h) K x (1) t-s + p (2,h) ϕ lin (s) = -β h s -g k (x t ) , which implies: k i=1 Hi h= k-1 i=1 Hi+1 Attn (2,h) t (X (1) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h (s-g k (xt)) 0 kd x t-s 0 ∈ R D ,Then it holds that:P (k) k i=1 Hi h= k-1 i=1 Hi+1 Attn (2,h) t (X (0) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h (s-g k (xt)) x t-s , P (k) ⊥ k i=1 Hi h= k-1 i=1 Hi+1 Attn (2,h) t (X (0) ) = 0,moreover, the following estimate holds:k i=1 Hi h= k-1 i=1 Hi+1 P (k) Attn (2,h) t (X) -x t-g k (xt) 2 = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h (s-g k (xt)) x t-s -x t-g k (xt) 2 = +∞ s=0   k i=1 Hi h= k-1 i=1 Hi+1 α h e -β h (s-g k (xt)) -I{s = g k (x t )}   x t-s 2 ≤ +∞ s=0 k i=1 Hi h= k-1 i=1 Hi+1 α h e -β h (s-g k (xt)) -I{s = g k (x t )} = ∥ϕ exp k (•; g k (x t )) -I{• = g k (x t )}∥ ℓ1(N) ≤ C(n)e 0.01(n+1)T k H n k .• Case type = log.By Lemma F.5, for any rate n ∈ N + , there exists a constant C(n) and a functionϕ poly k (t; B) = k-1 i=1 Hi+1≤h≤ k i=1 Hi α h (t/B) -β h = k-1 i=1 Hi+1≤h≤ k i=1 Hi α h exp β h log B -β h log t such that β h > 1 and sup 1≤B≤T k I{• = B} -ϕ poly k (•; B) ℓ1(N+) ≤ C(n)T 1.01(n+1) k H n k .Moreover, Noticing that 1 ≤ g k (x t ) ≤ T k holds for any X = (x t ) t∈Z ∈ X , the following holds:sup X I{• = g k (x t )} -ϕ poly k (•; g k (x t )) ℓ1(N+) ≤ sup 1≤B≤T k I{• = B} -ϕ poly k (•; B) ℓ1(N+) ≤ C(n)T 1.01(n+1) k H n k .Therefore, for these attention heads (EQUATIONO = I D×D , W (2,h) V = α h δ (d×d) (k+1,1) ∈ R D×D , W (2,h) Q = β h δ (1×1) (D-M +k-1,1) ∈ R D×D , W (2,h) K = √ β h log 2 δ (1×1) (D,1) ∈ R D×D ,where δ(r×r) (p1,p2) means that: it equals to I r×r for the (p 1 , p 2 )-th r × r blocks, and 0 r×r for the other r × r blocks.Then it is easy to verify:W (2,h) Q x (1) t , W (2,h) K x (1) t-s + p (2,h) ϕ log (s) = -β h log s/g k (x t ) , which implies: k i=1 Hi h= k-1 i=1 Hi+1 Attn (2,h) t (X (1) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 (s/g k (x t )) -β h 0 kd x t-s 0 ∈ R D ,Then it holds that:P (k) k i=1 Hi h= k-1 i=1 Hi+1 Attn (2,h) t (X (0) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 (s/g k (x t )) -β h x t-s , P (k) ⊥ k i=1 Hi h= k-1 i=1 Hi+1 Attn (2,h) t (X (0) ) = 0,moreover, the following estimate holds:k i=1 Hi h= k-1 i=1 Hi+1 P (k) Attn (2,h) t (X) -x t-g k (xt) 2 = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 (s/g k (x t )) -β h x t-s -x t-g k (xt) 2 = +∞ s=0   k i=1 Hi h= k-1 i=1 Hi+1 α h (s/g k (x t )) -β h -I{s = g k (x t )}   x t-s 2 ≤ +∞ s=0 k i=1 Hi h= k-1 i=1 Hi+1 α h (s/g k (x t )) -β h -I{s = g k (x t )} = ϕ poly k (•; g k (x t )) -I{• = g k (x t )} ℓ1(N+) ≤ C(n)T 1.01(n+1) k H n k .Then we combine the estimate for all k ∈ [M ] for these two cases. It holds thatQ (M ) x (3/2) t -     x t x t-g1(xt). . .x t-g M (xt)     2 = x t 0 M d + M h=1 Q (M ) Attn (2,h) t (X (1) ) -     x t x t-g1(xt). . .x t-g M (xt)     2 = M h=1 Q (M ) Attn (2,h) t (X) -     0 d x t-g1(xt). . .x t-g M (xt)     2 = M k=1   k i=1 Hi h= k-1 i=1 Hi+1 Q (M ) Attn (2,h) t (X) - 0 kd x t-g k (xt) 0   2 ≤ M k=1 k i=1 Hi h= k-1 i=1 Hi+1 Q (M ) Attn (2,h) t (X) - 0 kd x t-g k (xt) 0 = M k=1 k i=1 Hi h= k-1 i=1 Hi+1 P (k) Attn (2,h) t (X) -x t-g k (xt) 2 ≤E Attn (type) :=    C(n)e 0.01(n+1)T k H n k , type = lin C(n)T 1.01(n+1) k H n k , type = log .Similar to the proof of Theorem B.1, we choose the head number:H k = e 0.01T k M j=1 e 0.01Tj H, k ∈ [M ], type = lin; H k = T 1.01 k M j=1 T 1.01 j H, k ∈ [M ], type = log .Thus, we obtain the final bound in Step III:E Soft Attn (type) ≤            C(n) H n M k=1 e 0.01T k n+1 , type = lin C(n) H n M k=1 T 1.01 k n+1, type = log .Furthermore, by choosing E Attn (type) ≤ 1, it holds thatQ (M ) x (3/2) t ∞ ≤ Q (M ) x (3/2) t -     x t x t-g1(xt). . .x t-g M (xt)     ∞ +     x t x t-g1(xt). . .x t-g M (xt)     ∞ ≤E Attn (type) + 1 ≤ 2.Step IV. Approximate the nonlinear function by 2-nd FFN layer.In this step, we aim to approximate the function f using two-layer network. By Lemma G.6, there exists a two-layer neural network with m neuronsf 2NN (2) (x) = m k=1 a (2) k σ b (2) k ⊤ x + c (2) k defined on R (M +1)d such that f -f 2NN (2) L ∞ ([-2,2] (M +1)d ) ≤ Õ ∥f ∥ B √ m . Denote b(2) k = (b (2) k ⊤ , 0 ⊤ ) ⊤ ∈ R D for k ∈ [m].And we consider the following two-layer neural network with m neurons defined on R D :FFN (2) (x) := m k=1 a (2) k σ b(2) k ⊤ x + c (2) k .It is easy to verify:FFN (2) x (3/2) t = f 2NN (2) Q (M ) x (3/2) t .Moreover,(2)FFN := f -FFN (2) L ∞ ([-2,2] (M +1)d ) ≤ Õ ∥f ∥ B √ m .The final bound.For any t and ∥X∥ ∈ X , it holds thatH t (X) -x (2) t = f x t , x t-g1(xt) , • • • x t-g M (xt) -FFN (2) x (3/2) t = f (x t , x t-t1 , • • • x t-t M ) -f 2NN (2) Q (M ) x (3/2) t = f x t , x t-g1(xt) , • • • x t-g M (xt) -f Q (M ) x (3/2) t + f Q (M ) x (3/2) t -f 2NN(2)Q (M ) x (3/2) t ≤ f (x t , x t-t1 , • • • x t-t M ) -f Q (M ) x (3/2) t + f Q (M ) x (3/2) t -f 2NN (2) Q (M ) x (3/2) t ≤ ∥f ∥ Lip x ⊤ t , x ⊤ t-t1 , • • • x ⊤ t-t M ⊤ -Q (M ) x (3/2) t 2 + f -f 2NN (2) L ∞ ([-2,2] (M +1)D ) ≤ ∥f ∥ Lip • E Attn + E FFN ,whereE FFN = Õ ∥f ∥ B √ m ; E Attn (type) =            O C(n) H n M k=1 e 0.01T k n+1 , type = lin O C(n) H n M k=1 T 1.01 k n+1 , type = log .Moreover, recalling our proof in Step II, we further need the hard condition:m ≥    Ω M r=1 ∥g r ∥ 2 B , type = lin Ω M r=1 ∥log g r ∥ 2 B T 2 r , type = log .Due to the arbitrariness of t and X, the proof is completed.Remark C.3. The core step in this proof is Step III, where the extraction of the memory functions is achieved through a a nice interaction between the temporal space (provided by RPE) and the token space (provided by DP). Specifically, the memory functions g i (x t ) (in token space) are mapped into the temporal space s, resulting in the form of x s-gi(xt) for DP Attn with lin-RPE or log(s/g i (x t )) for DP Attn with log-RPE. , a uniform lower bound holds:H -Attn DPF ≥ 2 3 .Proof of Proposition C.4.Consider the following target function H ∈ H Adap 1,1 . Let the input sequence X ∈ X = {-1, 0, 1} Z , and we consider the targety t = H t (X) := x t-g(xt) ,where the adaptive memory isg(x) =    0, x = -1 1, x = 0 2, x = 1 .Part (A). The Efficiency of Attn with DP.First, we choose the embedding dimension D = 2, and select simple embeddingW E = b E = (1, 0) ⊤ ∈ R 2×1 .Then for any input sequence X = (x t ) t∈Z , the token after embedding satisfies:x (0) t = W E x t + b E = (x t , 1) ⊤ .We consider one-layer normalization-free Self-attention with ϕ exp , which has the form:Attn DP t (X) = W O H h=1 W (1,h) V +∞ s=0 x (0) t-s exp W (l,h) Q x (0) t , W (1,h) K x (0) t-s + p (1,h) s .By Lemma F.2 (for n = 1), there exists a constant C > 0 and a functionϕ exp (t; B) = H h=1 α h exp(-β h (t -B)) = H h=1 α h exp β h B -β h t such that β h > 0 and sup 0≤B≤2 ∥I{• = B} -ϕ exp (•; B)∥ ℓ1(N) ≤ Ce 0.01•2•2 H = O 1 H .Moreover, Noticing that 0 ≤ g(x t ) ≤ 2 holds for any X = (x t ) t∈Z ∈ X , the following holds:sup X ∥I{• = g(x t )} -ϕ exp (•; g(x t ))∥ ℓ1(N) ≤ sup 0≤B≤2 ∥I{• = B} -ϕ exp (•; B)∥ ℓ1(N) ≤ O 1 H .Therefore, for attention heads (1 ≤ h ≤ H), we can choose:EQUATIONO = (1, 0) ⊤ ∈ R 2×1 , W (1,h) V = α h δ (1×1) (1,1) ∈ R 2×2 , W (1,h) Q = β h (1, 1) ⊤ ∈ R 2×1 , W (1,h) K = β h (0, 1) ⊤ ∈ R 2×1 ,where δ (r×r) (p1,p2) means that: it equals to I r×r for the (p 1 , p 2 )-th r × r blocks, and 0 r×r for the other r × r blocks.Then it is easy to verify:W (1,h) Q x (0) t , W (1,h) K x (0) t-s + p (2,h) s = -p (1,h) s -(x t + 1) = -p (1,h) s -g(x t ) .Thus, the following estimate holds:Attn DP t (X) -x t-g(xt) 2 = H h=1 α h +∞ s=0 e -β h (s-g(xt)) x t-s -x t-g(xt) 2 = +∞ s=0 H h=1 α h e -β h (s-g(xt)) -I{s = g(x t )} x t-s 2 ≤ +∞ s=0 H h=1 α h e -β h (s-g k (xt)) -I{s = g(x t )} = ∥ϕ exp (•; g(x t )) -I{• = g(x t )}∥ ℓ1(N) ≤ O 1 H .Due to the arbitrariness of t and X, the proof is completed: for any ϵ > 0, we only need to use H = Ω(1/ϵ) heads to approximate it.Part (B). The Hardness Result of Attn without DP.We consider one-layer Dot-product-free Self-attention with ϕ exp or ϕ log . For any input X, the corresponding output can be written as:Attn DPF t (X) = +∞ s=0 ρ s (W E x t-s + b E ).For simplicity, we denote:x (0) t = W E x t + b E ,then we have the following estimate:|||H -Attn DPF ||| = sup t sup X |H DPF t (X) -Attn t (X)| ≥ sup X |H 0 (X) -Attn DPF 0 (X)| = sup (••• ,x-2,x-1,x0) x -g(x0) - +∞ s=0 ρ s x (0) -s fixing x-s = 0 for s ≥ 3 ≥ sup (x-2,x-1,x0) x -g(x0) - 2 s=0 ρ s x (0) -s x0∈{-1,0,1} = max max (x-2,x-1) -1 -ρ 0 (-W E + b E ) + ρ 1 x (0) -1 + ρ 2 x (0) -2 , max (x-2,x-1) x -g(0) -ρ 0 b E + ρ 1 x (0) -1 + ρ 2 x (0) -2 , max (x-2,x-1) x -g(1) -ρ 0 (W E + b E ) + ρ 1 x (0) -1 + ρ 2 x (0) -2 = max (x-2,x-1) max x -1 -ρ 0 b E + ρ 1 x (0) -1 + ρ 2 x (0) -2 , -1 -ρ 0 (-W E + b E ) + ρ 1 x (0) -1 + ρ 2 x (0) -2 , x -2 -ρ 0 (W E + b E ) + ρ 1 x (0) -1 + ρ 2 x (0) -2 max{a,b,c}≥ 1 3 (a+b+c) ≥ 1 3 max (x-2,x-1) x -1 -ρ 0 b E + ρ 1 x (0) -1 + ρ 2 x (0) -2 + -1 -ρ 0 (-W E + b E ) + ρ 1 x (0) -1 + ρ 2 x (0) -2 + x -2 -ρ 0 (W E + b E ) + ρ 1 x (0) -1 + ρ 2 x (0) -2 |a|+|b|≥|a+b| ≥ 1 3 max (x-2,x-1) x -1 -ρ 0 b E + ρ 1 x (0) -1 + ρ 2 x (0) -2 + -1 + x -2 -2 ρ 0 b E + ρ 1 x (0) -1 + ρ 2 x (0) -2 ≥ 1 3 max (x-2,x-1) x -1 -ρ 0 b E + ρ 1 x (0) -1 + ρ 2 x (0) -2 + -1 + x -2 2 -ρ 0 b E + ρ 1 x (0) -1 + ρ 2 x (0) -2 |a|+|b|≥|a-b| ≥ 1 3 max (x-2,x-1) x -1 + 1 2 - x -2 2 = 2 3 .In this subsection, we propose a structurally simpler yet effective alternative to traditional Dot-product in Self-attention. This alternative is proposed based on our insights into the role of Attn in facilitating interaction between the temporal-space and the token-space. Specifically, we propose a more direct structure to achieve the interaction ϕ type (s) -ϕ type w ⊤ x t . Definition C.5 (TMX Transformer). We define the TMX ("t minus x") Transformer as follows. In standard Transformer (2), we modify the termW (l,h) Q x t , W (l,h) K x t-s + p (l,h) ϕ type (s)in Multi-head Dot-product Self-attention to the new formulation:p (l,h) ϕ type (s) -ϕ type w (l,h) ⊤ x t ,where the parameters w (l,h) ∈ R D×1 .Notice that in TMX Transformer, the revised term requires only O(D) parameters, much less than O(D 2 ) in standard Dot-product Transformer.Consequently, we define the following TMX Transformer hypothesis class.T F (l,h) Q x t , W (l,h) K x t-s + p (l,h) ϕ type (s)in standard Transformer with p (l,h) ϕ type (s) -ϕ type w (l,h) ⊤ x t . Therefore, the proof is highly similar to that of Theorem C.2. We only need to prove that TMX Attn can also achieve Step I andStep III in the proof of Theorem C.2.Step I.Step I is trivial due to the same use of the residual block.Step III. Extract the adaptive memories by the second Attn layer.We still consider to use H k attention heads (fromk-1 i=1 H i + 1-th head to k i=1 H i -th head) to extract it, and it satisfies to M k=1 H k = H. Now we consider the extraction of k-th adaptive memory x t-g k (xt) (1 ≤ k ≤ M ).• Case type = lin.For the proof of standard Transformer (the proof of Theorem C.2), for the attention heads( k-1 i=1 H i +1 ≤ h ≤ k i=1 H i ), we can construct specific p (2,h) , W (2,h) Q , W (2,h) K , W (2,h) V such that W (2,h) Q x (1) t , W (2,h) K x (1) t-s + p (2,h) ϕ lin (s) = -β h s -g k (x t ) .In this proof, we only need to prove that we can also construct specific w (l,h) , W (2,h) V such that p (2,h) ϕ lin (s) -ϕ lin w (2,h) ⊤ x (1) t = -β h s -g k (x t ) .Recalling the proof of Theorem C.2,x (1) t = (x ⊤ t , 0 ⊤ , g 1 (x t ), • • • , g M (x t ), 1) ⊤ ∈ R D .Therefore, we can choosep (2,h) = β h , w (2,h) = δ (1×1) (D-M +k-1,1) ∈ R D , W (2,h) V = α h δ (d×d) (k+1,1) ∈ R D×D .where δ (r×r) (p1,p2) means that: it equals to I r×r for the (p 1 , p 2 )-th r × r blocks, and 0 r×r for the other r × r blocks.The the following holds:p (2,h) ϕ lin (s) -ϕ lin w (2,h) ⊤ x (1) t = -p (2,h) s -w (2,h) ⊤ x (1) t = -β h s -g k (x t ) .• Case type = log.For the proof of standard Transformer (the proof of Theorem C.2), for the attention heads( k-1 i=1 H i +1 ≤ h ≤ k i=1 H i ), we can construct specific p (2,h) , W (2,h) Q , W (2,h) K , W (2,h) V such that W (2,h) Q x (1) t , W (2,h) K x (1) t-s + p (2,h) ϕ log (s) = -β h log s/g k (x t ) .In this proof, we only need to prove that we can also construct specific w (l,h) , W (2,h) V such that p (2,h) ϕ log (s) -ϕ log w (2,h) ⊤ x (1) t = -β h log s/g k (x t ) .Recalling the proof of Theorem C.2,x (1) t = (x ⊤ t , 0 ⊤ , log g 1 (x t ), • • • , log g M (x t ), log 2) ⊤ .Therefore, we can choosep (2,h) = β h , w (2,h) = δ (1×1) (D-M +k-1,1) ∈ R D , W (2,h) V = α h δ (d×d) (k+1,1) ∈ R D×D .where δ (r×r) (p1,p2) means that: it equals to I r×r for the (p 1 , p 2 )-th r × r blocks, and 0 r×r for the other r × r blocks.The the following holds:p (2,h) ϕ log (s) -ϕ log w (2,h) ⊤ x (1) t = -p (2,h) log s/ w (2,h) ⊤ x (1) t = -β h log s/g k (x t ) .The rest of the proof is exactly the same as the proof of Theorem C.2, and we do not repeat it.In this subsection, we give the detailed proofs for the general case of K-adaptive, long but M -sparse memory:y t = f (x t , x t-t1 , • • • , x t-t M ),where the adaptive memories satisfy:t 1 = g 1 (x t ); t 2 = g 2 (x t , x t-t1 ); • • • t K+1 = g K+1 (x t , x t-t1 , • • • , x t-t K ); • • • t K+2 = g K+2 (x t , x t-t1 , • • • , x t-t K ); • • • t M = g K+1 (x t , x t-t1 , • • • , x t-t K ), where 1 ≤ t k ≤ T k holds for any k ∈ [M ].Theorem D.1 (Restatement of Theorem 4.4). For any target H ∈ H Adap (K,M ) , rate n ∈ N + , and H, m ∈ N + , there exists an L-layer(L = K + 1 + I{M ≥ K + 1}) Transformer TF ∈ T F NF,type (L,H,m) (12) and a constant C(n) such that: if the width satisfies m ≥        Ω max i∈[K] ∨ M i=K+1 ∥g i ∥ 2 B , type = lin, Ω max i∈[K] ∨ M i=K+1 ∥log g i ∥ 2 B T 2 i , type = log, then the following approximation rate holds:|||H -TF||| ≤ E FFN + E Attn (type),where Then for any input sequence X = (x t ) t∈Z , the token after embedding satisfies:EQUATIONx (0) t = W E x t + b E = (x ⊤ t , 0 ⊤ ) ⊤ ∈ R D .Thus, for L-layer(L = K + 1 + I{M ≥ K + 1}) normalization-free Transformer TF ∈ T F NF,type (L,H,m)with ϕ type , the output token x (K+1) t of t-th input token satisfies:x (l-1/2) t = x (l) t + W (l) O H h=1 Attn (l,h) t (X (l-1) ), 1 ≤ l ≤ L + 1 x (l) t = x (l-1/2) t + FFN (l) (x (l-1/2) t ), 1 ≤ l ≤ L x (L+1) t = FFN (L+1) (x (L+1/2) t ),whereAttn (l,h) t (X) = W (l,h) V +∞ s=0 x t-s exp W (l,h) Q x t , W (l,h) K x t-s + p (l,h) ϕ type (s) .Since the proof of this theorem is similar to the proof of Theorem C.2, we mainly discuss the differences.The proof can be summarized as the following process:• Case type = lin.-Regime M ≥ K + 1.x (0) tStep 1. 1-st Attn ↓x(1/2) t = x (0) tStep 2. 1-st FFN ↓x(1)t = x (1/2) t + (0 ⊤ , t 1 , 0 ⊤ M -1 , 1) ⊤ Step 3. 2-st Attn ↓ x (3/2) t ≈ x (1) t + (0 ⊤ d , x ⊤ t-t1 , 0 ⊤ ) ⊤ Step 4. 2-st FFN ↓ x (2) t = x (3/2) t + (0 ⊤ , t 2 , 0 ⊤ M -1 ) ⊤ Step 5. 3-st Attn ↓ x (5/2) t ≈ x (2) t + (0 ⊤ 2d , x ⊤ t-t2 , 0 ⊤ ) ⊤ • • • Step 2K + 1. K + 1-st Attn ↓ x (K+1/2) t ≈ x (K) t + (0 ⊤ Kd , x ⊤ t-t K , 0 ⊤ ) ⊤ Step 2K + 2. K + 1-st FFN ↓ x (K+1) t = x (K+1/2) t + (0 ⊤ , t K+1 , • • • , t M , 0) ⊤ Step 2K + 3. K + 2-st Attn ↓ x (K+3/2) t ≈ x (K+1) t + (0 ⊤ (K+1)d , x ⊤ t-t K+1 , • • • , x ⊤ t-t M , 0) ⊤ Step 2K + 4. K + 2-st FFN ↓ x (K+2) t ≈ f (x t , x t-t1 , • • • , x t-t M ) -Regime M = K. x (0) t Step 1. 1-st Attn ↓ x (1/2) t = x (0) t Step 2. 1-st FFN ↓ x (1) t = x (1/2) t + (0 ⊤ , t 1 , 0 ⊤ M -1 , 1) ⊤ Step 3. 2-st Attn ↓ x (3/2) t ≈ x (1) t + (0 ⊤ d , x ⊤ t-t1 , 0 ⊤ ) ⊤ Step 4. 2-st FFN ↓ x (2) t = x (3/2) t + (0 ⊤ , t 2 , 0 ⊤ M -1 ) ⊤ Step 5. 3-st Attn ↓ x (5/2) t ≈ x (2) t + (0 ⊤ 2d , x ⊤ t-t2 , 0 ⊤ ) ⊤ • • • Step 2K + 1. K + 1-st Attn ↓ x (K+1/2) t ≈ x (K) t + (0 ⊤ Kd , x ⊤ t-t K , 0 ⊤ ) ⊤ Step 2K + 2. K + 1-st FFN ↓ x (K+1) t ≈ f (x t , x t-t1 , • • • , x t-t M ) • Case type = log. -Regime M ≥ K + 1. x (0) t Step 1. 1-st Attn ↓ x (1/2) t = x (0) t Step 2. 1-st FFN ↓ x (1) t = x (1/2) t + (0 ⊤ , log t 1 , 0 ⊤ M -1 , log 2) ⊤ Step 3. 2-st Attn ↓ x (3/2) t ≈ x (1) t + (0 ⊤ d , x ⊤ t-t1 , 0 ⊤ ) ⊤ Step 4. 2-st FFN ↓ x (2) t = x (3/2) t + (0 ⊤ , log t 2 , 0 ⊤ M -1 ) ⊤ Step 5. 3-st Attn ↓ x (5/2) t ≈ x (2) t + (0 ⊤ 2d , x ⊤ t-t2 , 0 ⊤ ) ⊤ • • • Step 2K + 1. K + 1-st Attn ↓ x (K+1/2) t ≈ x (K) t + (0 ⊤ Kd , x ⊤ t-log t K , 0 ⊤ ) ⊤ Step 2K + 2. K + 1-st FFN ↓ x (K+1) t = x (K+1/2) t + (0 ⊤ , log t K+1 , • • • , log t M , 0) ⊤ Step 2K + 3. K + 2-st Attn ↓ x (K+3/2) t ≈ x (K+1) t + (0 ⊤ (K+1)d , x ⊤ t-t K+1 , • • • , x ⊤ t-t M , 0) ⊤ Step 2K + 4. K + 2-st FFN ↓ x (K+2) t ≈ f (x t , x t-t1 , • • • , x t-t M ) -Regime M = K. x (0) t Step 1. 1-st Attn ↓ x (1/2) t = x (0) t Step 2. 1-st FFN ↓ x (1) t = x (1/2) t + (0 ⊤ , log t 1 , 0 ⊤ M -1 , log 2) ⊤ Step 3. 2-st Attn ↓ x (3/2) t ≈ x (1) t + (0 ⊤ d , x ⊤ t-t1 , 0 ⊤ ) ⊤ Step 4. 2-st FFN ↓ x (2) t = x (3/2) t + (0 ⊤ , log t 2 , 0 ⊤ M -1 ) ⊤ Step 5. 3-st Attn ↓ x (5/2) t ≈ x (2) t + (0 ⊤ 2d , x ⊤ t-t2 , 0 ⊤ ) ⊤ • • • Step 2K + 1. K + 1-st Attn ↓ x (K+1/2) t ≈ x (K) t + (0 ⊤ Kd , x ⊤ t-t K , 0 ⊤ ) ⊤ Step 2K + 2. K + 1-st FFN ↓ x (K+1) t ≈ f (x t , x t-t1 , • • • , x t-t M )For simplicity, we denote the following projection matrices:P (k) := (0 d×kd I d×d 0) ∈ R d×D , 1 ≤ k ≤ M ; P (k) ⊥ := I kd×kd 0 d×d 0 0 0 d×d I (D-(k+1)d)×(D-(k+1)d) ∈ R (D-d)×D , 1 ≤ k ≤ M ; Q (k) := I (k+1)d×(k+1)d 0 ∈ R (k+1)d×D , 1 ≤ k ≤ M ; Q (k) ⊥ := 0 I (D-(k+1)d)×(D-(k+1)d) ∈ R (D-(k+1)d)×D , 1 ≤ k ≤ M ; R := 0 (M -K)d×(K+1)d I (M -K)d×(M -K)d 0 ∈ R (M -K)d×D ; R ⊥ := I (K+1)d×(K+1)d 0 0 0 0 I (M +1)×(M +1) ∈ R (D-(M -K)d)×D .Step 1 is trivial due to the use of the residual block.Step 2. In the same way as Step II in the proof of Theorem C.2, we obtain the conclusion in this step: If the width of FFN satisfiesm ≥    Ω ∥g 1 ∥ 2 B , type = lin Ω ∥log g 1 ∥ 2 B T 2 1 , type = log, then the following holds:x(1)t = x (1/2) t + (0 ⊤ , t 1 , 0 ⊤ M , 1) ⊤ .Thus, (E1) holds for l = 2.Step 3 ∼ Step 2K + 1.• Case type = lin.-FFN layers.We use l-th (2 ≤ l ≤ K) FFN layer to express l-th memory t l exactly. By Lemma G.6, there exists a two-layer neural network with m neurons defined on R ldf 2NN (l) (x) = m k=1 a (l) k σ(b (l) k ⊤ x + c (l) k ) such that g l -f 2NN (l) L ∞ ([-2,2] ld ) ≤ Õ ∥g l ∥ B √ m .For l-th FFN layer, we only need to arrange the parameters aEQUATIONk , and c(l) k (k ∈ [m], 2 ≤ l ≤ M ). Denote b(l) k = (b (l) k ⊤ , 0 ⊤ ) ⊤ ∈ R D for k ∈ [m], 2 ≤ l ≤ K -1.Consider the following two-layer neural network with m neurons defined on R D :FFN (l) (x) = m k=1 e D-M +l-1 a (l) k σ b(l) k ⊤ x + c (l) k .It is easy to verifyFFN (l) (x) = 0 ⊤ , f 2NN (l) Q (l) x , 0 ⊤ D-M +l-1 ⊤ ∈ R D , ∀x ∈ R D .Notice that if the width m satisfiesÕ ∥g l ∥ B √ m < 1 4 ,and the input x(l-1/2) t satisfies ∥g l ∥ Lip • (x ⊤ t , • • • , x ⊤ t-t l-1 ) ⊤ -Q (l-1) x (l-1/2) t 2 ≤ 1 4the following holds:g l (x t , • • • , x t-t l-1 ) -f 2NN (l) Q (l) x (l-1/2) t ≤ g l (x t , • • • , x t-t l-1 ) -g l (Q (l-1) x (l-1/2) t ) + g l (Q (l-1) x (l-1/2) t ) -f 2NN (l) (Q (l-1) x (l-1/2) t ) ≤ ∥g l ∥ Lip (x ⊤ t , • • • , x ⊤ t-t l-1 ) ⊤ -Q (l-1) x (l-1/2) t 2 + g l -f 2NN (l) L ∞ < 1 4 + 1 4 = 1 2 , Noticing t l = g l (x t , • • • , x t-t l-1 ) ∈ N + , we have f 2NN (l) (Q (l-1) x (l-1/2) t ) = t l .Thus, it holds that:FFN (l) (x (l-1/2) t ) = (0 ⊤ , t l , 0 ⊤ D-M +l-1 ) ⊤ . -Attn layers.By Lemma F.2, for any rate n ∈ N + , there exists a constant C(n) and K functionsϕ exp l (t; B) = h=1 α l,h exp(-β l,h (t -B)) = H h=1 α l,h exp β l,h B -β l,h t , 1 ≤ l ≤ K such that β l,h > 0 and sup 1≤B≤T l ∥I{• = B} -ϕ exp l (•; B)∥ ℓ1(N) ≤ C(n)e 0.01(n+1)T l H n , 1 ≤ l ≤ K.Moreover, Noticing that 1 ≤ g l (•) ≤ T l holds for any X = (x t ) t∈Z ∈ X and 2 ≤ l ≤ K, the following holds:sup X ∥I{• = t l } -ϕ exp l (•; t l )∥ ℓ1(N) ≤ sup 1≤B≤T l ∥I{• = B} -ϕ exp l (•; B)∥ ℓ1(N) ≤ C(n)e 0.01(n+1)T l H n .Therefore, for the attention heads h (h ∈ [H]) in each layer l (1 ≤ l ≤ K), we can choose:p (l+1,h) = β l,h , W (l+1) O = I, W (l+1,h) V = α l,h δ (d×d) (l+1,1) ∈ R D×D , W (l+1,h) Q = β l,h δ (1×1) (D-M +l,1) ∈ R D×(D/H) , W (l+1,h) K = β l,h δ (1×1) (D,1) ∈ R D×(D/H) ,where δ (r×r) (p1,p2) means that: it equals to I r×r for the (p 1 , p 2 )-th r × r blocks, and 0 r×r for the other r × r blocks.• Case type = log.-FFN layers.We use l-th (2 ≤ l ≤ K) FFN layer to express l-th memory t l exactly. By Lemma G.6, there exists a two-layer neural network with m neurons defined on R ldf 2NN (l) (x) = m k=1 a (l) k σ(b (l) k ⊤ x + c (l) k ) such that log g l -f 2NN (l) L ∞ ≤ Õ ∥log g l ∥ B √ m .For l-th FFN layer, we only need to arrange the parameters aEQUATIONk , and c(l) k (k ∈ [m], 2 ≤ l ≤ M ). Denote b(l) k = (b (l) k ⊤ , 0 ⊤ ) ⊤ ∈ R D for k ∈ [m], 2 ≤ l ≤ K -1.We consider the following l-th layer 2NN with m neurons defined on R D :FFN (l) (x) = m k=1 e D-M +l-1 a (r) k σ b(r) k ⊤ x + c (r) k .It is easy to verifyFFN (l) (x) = 0 ⊤ , f 2NN (l) Q (l) x , 0 ⊤ D-M +l-1 ⊤ ∈ R D , ∀x ∈ R D .Notice that if the width m satisfiesÕ ∥log g l ∥ B √ m < 1 8T l ,and the input x(l-1/2) t satisfies ∥log g l ∥ Lip • (x ⊤ t , • • • , x ⊤ t-t l-1 ) ⊤ -Q (l) x (l-1/2) t 2 ≤ 1 8T l ,the following holds:log g l (x t , • • • , x t-t l-1 ) -f 2NN (l) (Q (l) x (l-1/2) t ) ≤ log g l (x t , • • • , x t-t l-1 ) -log g l (Q (l) x (l-1/2) t ) + g l (Q (l) x (l-1/2) t ) -f 2NN (l) (Q (l) x (l-1/2) t ) ≤ ∥log g l ∥ Lip (x ⊤ t , • • • , x ⊤ t-t l-1 ) ⊤ -Q (l) x (l-1/2) t 2 + log g l -f 2NN (l) L ∞ < 1 8T l + 1 8T l = 1 4T l , which ensures exp f 2NN (l) (Q (l) x (l-1/2) t ) -g l (x t , • • • , x t-t l-1 ) = exp f 2NN (l) (Q (l) x (l-1/2) t ) -exp log g l (x t , • • • , x t-t l-1 ) ≤ exp max f 2NN (l) (Q (l) x (l-1/2) t ), log g l (x t , • • • , x t-t l-1 ) • f 2NN (l) (Q (l) x (l-1/2) t ) -log g l (x t , • • • , x t-t l-1 ) ≤ exp log g l (x t , • • • , x t-t l-1 ) + 1 8 1 4T r ≤e 1/8 • T r • 1 4T r < 1 2 . Noticing t l = g l (x t , • • • , x t-t l-1 ) ∈ N + , we have f 2NN (l) (Q l x (l-1/2) t ) = log exp FFN (l) (x t , • • • , x t-t l-1 ) = log t l .Thus, it holds that:FFN (l) (x (l-1/2) t ) = (0 ⊤ , log t l , 0 ⊤ D-M +l-1 ) ⊤ . -Attn layers.By Lemma F.5, for any rate n ∈ N + , there exists a constant C(n) and K functionsϕ poly l (t; B) = h=1 α l,h (t/B) -β l,h = H h=1 α l,h exp -β l,h log(t/B) , 1 ≤ l ≤ K such that β l,h > 0 and sup 1≤B≤T l I{• = B} -ϕ poly l (•; B) ℓ1(N+) ≤ C(n)T 1.01(n+1) l H n , 1 ≤ l ≤ K.Moreover, Noticing that 1 ≤ g l (•) ≤ T l holds for any X = (x t ) t∈Z ∈ X and 1 ≤ l ≤ K, the following holds:sup X I{• = t l } -ϕ poly l (•; t l ) ℓ1(N+) ≤ sup 1≤B≤T l I{• = B} -ϕ poly l (•; B) ℓ1(N+) ≤ C(n)T 1.01(n+1) l H n .Therefore, for the attention heads h (h ∈ [H]) in each layer l (1 ≤ l ≤ K), we can choose: H) , where δ (r×r) (p1,p2) means that: it equals to I r×r for the (p 1 , p 2 )-th r × r blocks, and 0 r×r for the other r × r blocks.p (l+1,h) = β l,h , W (l+1) O = I, W (l+1,h) V = α l,h δ (d×d) (l+1,1) ∈ R D×D , W (l+1,h) Q = β l,h δ (1×1) (D-M +l,1) ∈ R D×(D/H) , W (l+1,h) K = β l,h δ (1×1) (D,1) ∈ R D×(D/Step III in the proof of Theorem C.2, it is easy to prove the following estimates by induction.m ≥        Ω max l∈[K] ∥g l ∥ 2 B = Ω ∥g K ∥ 2 B , type = lin Ω max l∈[K] ∥log g l ∥ 2 B T 2 l = Ω ∥log g K ∥ 2 B T 2 K , type = log, and the head number satisfies       C(n) H n K-1 l=1 e 0.02(n+1)T l ≤ 1 4 max l∈[K-1] ∥g l ∥ Lip , type = lin C(n) H n K-1 l=1 T 2.02(n+1) l ≤ 1 4 max l∈[K-1] ∥log g l ∥ Lip, type = log , then the following estimates hold:• (E1) for any 2 ≤ l ≤ K, x (l) t = x (l-1/2) t + (0 ⊤ , t l , 0 ⊤ M -l+1 ) ⊤ ; • (E2) for any 1 ≤ l ≤ K, P (l) ⊥ x (l+1/2) t = P (l) ⊥ x (l) t ;• (E3) for any 1 ≤ l ≤ K,P (l) x (l+1/2) t -x (l) t + (0 ⊤ ld , x ⊤ t-t l , 0 ⊤ ) ⊤ 2 ≤ C(n)e 0.01(n+1)T l H n , type = lin C(n)T 1.01(n+1) l H n , type = log ; Q (l) x (l+1/2) t -x (0) t 2 ≤    C(n) H nl j=1 e 0.02(n+1)T l , type = linC(n) H n l j=1 T 2.02(n+1) j , type = log .The Remained Steps.• Regime M ≥ K + 1.Step 2K + 2 and 2K + 3.Step 3 ∼ Step 2K -1 in this proof and Step II, Step III in the proof of Theorem C.2, it is easy to verify the following estimate.If the width satisifesm ≥    Ω M l=K+1 ∥g l ∥ 2 B , type = lin Ω M l=K+1 ∥log g l ∥ 2 B T 2 l , type = log, and the head number satisfies       C(n) H n K l=1 e 0.02(n+1)T l ≤ 1 4 max l∈[K] ∥g l ∥ Lip , type = lin C(n) H n K l=1 T 2.02(n+1) l ≤ 1 4 max l∈[K] ∥log g l ∥ Lip, type = log , then the following estimates hold:x (K+1) t = x (K+1/2) t + (0 ⊤ , t K+1 , • • • , t M , 0) ⊤ ; R ⊥ x (K+3/2) t = R ⊥ x (K+1) t ; R x (K+3/2) t -x (K+1) t + (0 ⊤ (K+1)D , x ⊤ t-t K+1 , • • • , x ⊤ t-t M , 0 ⊤ ) ⊤ 2 ≤          C(n) M l=K+1 e 0.01T l H n n+1 n+1 , type = lin C(n) M l=K+1 T 1.01 l H n n+1 n+1 , type = log , Q (M ) x (K+3/2) t -x (0) t 2 ≤        C(n) H n K l=1 e 0.02(n+1)T l + M l=K+1 e 0.01T l 2n+2, type = linC(n) H n K l=1 T 2.02(n+1) l + M l=K+1 T 1.01 l 2n+2, type = log .Step 2K + 4 and the final bound.In the same way as Step IV in the proof of Theorem C.2, there exists FFN, such that the following estimate holds for any t and X:H t (X) -x (K+2) t ≤ ∥f ∥ Lip • Q (M ) x (K+3/2) t -x (0) t 2 + E FFN = ∥f ∥ Lip • E Attn (type) + E FFN ,whereE FFN = O ∥f ∥ B √ m , E Attn (type) = Q (M ) x (K+3/2) t -x (0) t 2 =        C(n) H n K l=1 e 0.02(n+1)T l + M l=K+1 e 0.01T l 2n+2 , type = lin C(n) H n K l=1 T 2.02(n+1) l + M l=K+1 T 1.01 l 2n+2, type = log .Recalling our analysis, we need the head number satisfies       C(n) H n K l=1 e 0.02(n+1)T l ≤ 1 4 max l∈[K] ∥g l ∥ Lip , type = lin C(n) H n K l=1 T 2.02(n+1) l ≤ 1 4 max l∈[K] ∥log g l ∥ Lip , type = log . Due to    C(n) H n K l=1 e 0.02(n+1)T l ≤ E Attn (type), type = lin C(n) H n K l=1 T 2.02(n+1) l ≤ E Attn (type), type = log ,when we is large enough, this condition holds naturally and do not affect the approximation rate.Moreover, we need the following condition on the width:m ≥        Ω max l∈[K] ∨ M l=K+1 ∥g l ∥ 2 B , type = lin Ω max l∈[K] ∨ M l=K+1 ∥log g l ∥ 2 B T 2 l , type = log , • Regime M = K.Step 2K + 2 and the final bound.In the same way as Step IV in the proof of Theorem C.2, there exists FFN, such that the following estimate holds for any t and X:H t (X) -x (K+1) t ≤ ∥f ∥ Lip • Q (M ) x (K+1/2) t -x (0) t 2 + E FFN = ∥f ∥ Lip • E Attn (type) + E FFN ,whereE FFN = O ∥f ∥ B √ m , E Attn (type) = Q M x (K+1/2) t -x (0) t 2 =    C(n) H n K l=1 e 0.02(n+1)T l , type = lin C(n) H n K l=1 T 2.02(n+1) l , type = log .Recalling our analysis, we need the head number satisfies       C(n) H n K-1 l=1 e 0.02(n+1)T l ≤ 1 4 max l∈[K-1] ∥g l ∥ Lip , type = lin C(n) H n K-1 l=1 T 2.02(n+1) l ≤ 1 4 max l∈[K-1] ∥log g l ∥ Lip , type = log . Due to    C(n) H n K-1 l=1 e 0.02(n+1)T l ≤ E Attn (type), type = lin C(n) H n K-1 l=1 T 2.02(n+1) l ≤ E Attn (type), type = log, when H is large enough, this condition holds naturally and do not affect the approximation rate.Moreover, we need the following condition on the width:m ≥        Ω max l∈[K] ∥g l ∥ 2 B , type = lin Ω max l∈[K] ∥log g l ∥ 2 B T 2 l , type = log ,Combining these two regimes, we complete our proof.Proof of Proposition 4.5. This proposition is a direct corollary of Theorem 4.4. It can be seen as a special case of M = K in Theorem 4.4.Therefore, under the same conditions, there exists a K + 1-layer Transformer TF ∈ T F NF,type (K+1,H,m) (12) and a constant C(n) such that: if the width satisfiesm ≥      Ω max i∈[K] ∥g i ∥ 2 B , type = lin, Ω max i∈[K] ∥log g i ∥ 2 B T 2 i , type = log, then the following approximation rate holds:|||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type),whereE FFN = Õ ∥f ∥ B √ m and E Attn (type) =        O C(n) H n K l=1 e 0.02(n+1)T l , type = lin O C(n) H n K l=1 T 2.02(n+1) l , type = log .Comparison between Proposition 4.5 and Theorem 4.1.We compare 2-layer Transformer and M + 1-layer Transformer regarding the requirement of the number of heads and width.• The required width of FFN layers.-For 2-layer Transformer, the required width of FFN layers m(2)need is proportionally linked to the sum of all the memory functions' complexity:m (2) need =        Ω i∈[K] ∥g i ∥ 2 B , type = lin, Ω i∈[K] ∥log g i ∥ 2 B T 2 i , type = log.-For M + 1-layer Transformer, the required width of FFN layers m (M +1) need correlates with the maximum complexity of the memory functions:m (M +1) need =      Ω max i∈[K] ∥g i ∥ 2 B , type = lin, Ω max i∈[K] ∥log g i ∥ 2 B T 2 i , type = log .It is easy to see that:m (M +1) need m (2) need = max{a 1 , • • • , a M } M k=1 a k , max{a 1 , • • • , a M } ≤ M k=1 a k• The required number of Attn heads. To achieve the same E Attn (type) = ϵ, for 2-layer Transformer, the required number of Attn heads H(2) need satisfies:ϵ =        O C(n) H (2) need n K l=1 e 0.02(n+1)T l , type = lin O C(n) H (2) need n K l=1 T 2.02(n+1) l, type = log .for M + 1-layer Transformer, the required number of Attn heads H (M +1) need satisfies:ϵ =        O C(n) H (M +1) need n M i=1 e 0.01Ti n+1 , type = lin O C(n) H (M +1) need n M i=1 T 1.01 i n+1 , type = log .It is easy to see that:H (M +1) need H (2) need 2n = b 2 1 + • • • + b 2 M (b 1 + • • • b M ) 2 , b 2 1 + • • • + b 2 M ≤ (b 1 + • • • b M ) 2 .This finding suggests that increased depth can significantly reduce the demands on the number of heads and the width. The underlying reason is that deep networks can distribute memories across different layers for processing, with each layer focusing on approximating only a single memory function.E Proof of Section 5E.1 Proof of Theorem 5.1In this subsection, we give the detailed proofs of the warm-up case of (fixed) essentially sparse memories as follows:y t = f ((X * ρ 1 ) (t), • • • , (X * ρ M ) (t)) ,whereρ 1 (•), • • • , ρ M (•) ∈ ℓ 1 (N)serve as memory kernels, and (X * ρ k )(t) = +∞ s=0 x t-s ρ k (s) denotes the convolution of the inputs with kernel ρ k . Theorem E.1 (Restatement of Theorem 5.1). (A) Consider H Ess (14) with exponentially decayed memory kernels, i.e., there exists β > 0 such thatρ 1 (t), • • • , ρ M (t) = O(e -βt). Then for any target H ∈ H Ess , rate n ∈ [⌊99β⌋], and H, m ∈ N + , there exists a 1-layer DP-free Transformer TF ∈ T F DPF,exp (1,H,m) (7) and a constantC(n) such that |||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type);(B) Consider H Ess (14) with polynomially decayed memory kernels, i.e., there existsβ > 1 such that ρ 1 (t), • • • , ρ M (t) = O(t -β ). Then for any target H ∈ H Ess , rate n ∈ [⌊0.99β⌋ -1],and H, m ∈ N + , there exists a 1-layer DP-free Transformer TF ∈ T F DPF,poly (1,H,m) (7) and a constantC(n) such that |||H -TF||| ≤ E FFN + ∥f ∥ Lip E Attn (type);whereE FFN = Õ ∥f ∥ B √ m and E Attn (type) = O C(n)M n+1 H n .Proof of Theorem E.1. The proof of this theorem is highly similar to the proof of Theorem B.1. The only difference is that the Attn layer needs to be used to approximate general memory kernel ρ k (•) instead of simple I{• = T k }. But for the completeness of the proof in this section, we still provide the detailed proof. First, we choose the embedding dimension D = M d, and select the simple embeddingW E = (I d×d , 0) ⊤ ∈ R D×d , b E = 0 ∈ R D .For any input sequence X = (x t ) t∈Z , the token after embedding satisfies:x E t = W E x t + b E = (x ⊤ t , 0 ⊤ ) ⊤ ∈ R D .Then for one-layer Dot-product-free Transformer TF ∈ T F DPF,type (1,H,m) without residual blocks, the output token TF t (X) of t-th input token x t satisfies:x (1/2) t = W (1) O H h=1 Attn (1,h) t (X (0) ), x (1) t = FFN (1) (x (1/2) t ) where Attn (1,h) t (X) = W (1,h) V +∞ s=0 x t-s exp p (1,h) ϕ type (s) +∞ j=0 exp p (1,h) ϕ type (j). This proof can be summarized as the following process:• • • x E t • • • Step I. Attn layer ↓ • • • x (1/2) t ≈ ((X * ρ 1 )(t), • • • , (X * ρ M )(t)) ⊤ • • • Step II. FFN layer ↓ • • • x (1) t ≈ f ((X * ρ 1 )(t), • • • , (X * ρ M )(t)) • • •Now we give the formal proof.Step I. Extract the memory locations by (Dot-product-free) Attn layer.We consider to use H k attention heads (fromk-1 i=1 H i + 1-th head to k i=1 H i -th head) to extract it, and it satisfies to M k=1 H k = H. P (k) := 0 d×(k-1)d I d×d 0 ∈ R d×D , 1 ≤ k ≤ M. P (k) ⊥ := I (k-1)d×(k-1)d 0 d×d 0 0 0 d×d I (M -k-1)d×(M -k-1)d ∈ R (M -1)d×D , 1 ≤ k ≤ M. Now we consider the extraction of k-th memory (X * ρ k )(t) (1 ≤ k ≤ M ).• Case (A). Approximating exponentially decayed memories by type = lin.Because there exists β > 0 such that ρ k (t) = O(e -βt ), by Lemma F.3, for any n ∈ [⌊99β⌋] and m ∈ N + , there exists an absolute constant C(n) only depending on n and a functionϕ exp k (t) = k-1 i=1 Hi+1≤h≤ k i=1 Hi α h e -β h t such that β h > 0 and ∥ρ k (•) -ϕ exp k (•)∥ ℓ1(N) = +∞ s=0 |ρ k (s) -ϕ exp k (s)| ≤ C(n) m n .Therefore, for these attention heads (k-1 i=1 H i + 1 ≤ h ≤ k i=1 H i ), we can choose p (1,h) = β h , W (1,h) V = α h   +∞ j=0 exp(-β h j)   δ d×d (k,1) ,where δ (k,1) ∈ R D×D means that: it equals to I d×d for the (k, 1)-th d × d blocks, and 0 d×d for the other d × d blocks.Then it holds that:k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h s 0 (k-1)d x t-s 0 ∈ R D ,This implies:P (k) k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h s x t-s , P (k) ⊥ k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = 0,moreover, the following estimate holds:k i=1 Hi h= k-1 i=1 Hi+1 P (k) Attn (1,h) t (X (0) ) -(X * ρ k )(t) 2 = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=0 e -β h s x t-s - +∞ s=0 x t-s ρ k (s) 2 = +∞ s=0   k i=1 Hi h= k-1 i=1 Hi+1 α h e -β h s -I{s = T k }   x t-s 2 ≤ +∞ s=0 k i=1 Hi h= k-1 i=1 Hi+1 α h e -β h s -ρ k (s) = ∥ϕ exp k (•) -ρ k (•)∥ ℓ1(N) ≤ C(n) H n k .• Case (B). Approximating polynomially decayed memories by type = log.Because there exists β > 0 such that ρ k (t) = O(t -β ), by Lemma F.6, for any n ∈ [⌊0.99β⌋ -1] and m ∈ N + , there exists an absolute constant C(n) only depending on n and a functionϕ poly k (t) = k-1 i=1 Hi+1≤h≤ k i=1 Hi α h t -β h such that β h > 1 and ρ k (•) -ϕ poly k (•) ℓ1(N+) = +∞ s=1 ρ k (s) -ϕ poly k (s) ≤ C(n) m n .Therefore, for these attention heads ( 1) , where δ (k,1) ∈ R D×D means that: it equals to I d×d for the (k, 1)-th d × d blocks, and 0 d×d for the other d × d blocks.k-1 i=1 H i + 1 ≤ h ≤ k i=1 H i ), we can choose p (1,h) = β h , W (1,h) V = α h   +∞ j=1 j -β h   δ (k,Then it holds that:EQUATION, This implies:P (k) k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=1 s -β h x t-s , P (k) ⊥ k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X (0) ) = 0, k i=1 Hi h= k-1 i=1 Hi+1 P (k) Attn (1,h) t (X (0) ) -(X * ρ k )(t) 2 = k i=1 Hi h= k-1 i=1 Hi+1 α h +∞ s=1 s -β h x t-s - +∞ s=0 x t-s ρ k (s) 2 = +∞ s=1   k i=1 Hi h= k-1 i=1 Hi+1 α h s -β h -ρ k (s)   x t-s 2 ≤ +∞ s=1 k i=1 Hi h= k-1 i=1 Hi+1 α h s -β h -ρ k (s) = ϕ poly H k (•) -ρ k (•) ℓ1(N+) ≤ C(n) H n k .Then we combine the estimate for all k ∈ [M ] for these two cases. By choose W O = I D , we have:x (1/2) t -    (X * ρ 1 )(t) . . . (X * ρ M )(t)    2 = M k=1   k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X) - 0 (k-1)d (X * ρ k )(t) 0 d   2 ≤ M k=1 k i=1 Hi h= k-1 i=1 Hi+1 Attn (1,h) t (X) - 0 (k-1)d (X * ρ k )(t) 0 d 2 = M k=1 k i=1 Hi h= k-1 i=1 Hi+1 P (k) Attn (1,h) t (X (0) ) -(X * ρ k )(t) 2 ≤E Attn := M k=1 C(n) H n k, for both Case (A) and Case (B).Consequently, one detail is to assign the head number {H k } M k=1 such that the error's sum E Attn (type) is as small as possible. Here, we simply choose the same H k :H k = H M , k ∈ [M ].Thus, we obtain the bound in Step I:E Attn = M k=1 C(n) H n k = C(n)M n+1 H n .Furthermore, by choosing E Attn ≤ 1, it holds thatx (1/2) t ∞ ≤ x (1/2) t -    (X * ρ 1 )(t) . . . (X * ρ M )(t)    ∞ +    (X * ρ 1 )(t) . . . (X * ρ M )(t)    ∞ ≤ E Attn + 1 ≤ 2.Step II. Approximate the readout function by FFN layer.In this step, we aim to approximate the function f using two-layer network. By Lemma G.6, there exists a two-layer neural network with m neurons defined onR D FFN (1) (y) = m k=1 a k σ(b ⊤ k y + c k )such thatE FFN := FFN (1) -f L ∞ ([-2,2] D ) ≤ Õ ∥f ∥ B √ m .The final bound.For any t and X ∈ X , it holds thatH t (X) -x (1) t = f ((X * ρ 1 )(t), • • • , (X * ρ M )(t)) -FFN (1) x (1/2) t = f ((X * ρ 1 )(t), • • • , (X * ρ M )(t)) -f x (1/2) t + f x (1/2) t -FFN (1) x (1/2) t ≤ f ((X * ρ 1 )(t), • • • , (X * ρ M )(t)) -f x (1/2) t + f x (1/2) t -FFN (1) x (1/2) t ≤ ∥f ∥ Lip ((X * ρ 1 )(t) ⊤ , • • • , (X * ρ M )(t) ⊤ ) ⊤ -x (1/2) t 2 + f -FFN (1) L ∞ ([-2,2] D ) ≤ ∥f ∥ Lip • E Attn + E FFN ,whereE FFN = ∥f ∥ B √ m ; E Attn = C(n)M n+1H n , for both Case (A) and Case (B).Due to the arbitrariness of t and X, the proof is completed.F Key Lemmas about Approximation Proof of Lemma F.1. Let α, γ > 0 be constants, and they will take specific values at the end of the proof.First, recall the standard bump function on [-1, 1]:Ψ(x) := exp -1 1-x 2 ,x ∈ (-1, 1) 0, otherwise , and we can define the following constants for T ≥ 1:µ T = e -αT , σ T = e -αT -e -α(T +1) .Then we consider the following bump functionΨ T ∈ C ∞ ([0, 1]): Ψ T (x) = V T Ψ x-µ T σ T , x ∈ (µ T -σ T , µ T + σ T ) 0, otherwise, where V T is a scaling constant such that Ψ T (e -αT ) = e γT .First, we consider the approximation of Ψ T on [0, 1].Notice that Ψ T ∈ C ∞ ([0, 1]), and Ψ Ψ (k) (x) ≤ M (n).Notice that for any k ∈ N and x ∈ [0, 1],Ψ (k) T (x) = V T σ k T Ψ (k) x -µ T σ T .Therefore, the following upper bound holds:M T (n) = max 0≤k≤n V T σ k T M (n) = V T σ n T M (n) = e γT • e e -αT -e -α(T +1) n M (n) = M (n)e (1 -1/e) n e (γ+nα)T := C(n, α)e (γ+nα)T . By Lemma G.5, for any m ∈ N + , there exists a polynomialQ m (x) = m-1 k=0 α k x k such that sup x∈[0,1] |Ψ T (x) -Q m (x)| ≤ M T (n) m n ≤ C(n, α)e (γ+nα)T m n .Now we use the transform x = e -αt on the function Ψ and consider Φ T (t) := e -γt Ψ T (e -αt ), t ∈ [0, +∞).It is easy to verify that Φ T satisfies thatΦ T (t) N = I(t = T ).Moreover, we consider the functionP m (t) := e -γt Q m (e -αt ), t ∈ [0, +∞).Then by choosing α = γ = 0.01, the following error estimate holds:∥P m (•) -I(• = T )∥ ℓ1(N) = +∞ t=0 |P m (t) -Φ T (t)| = +∞ t=0 e -γt |Q m (e -αt ) -Ψ T (e -αt )| ≤ +∞ t=0 e -γt M T (n) m n ≤ C(n, α)e (γ+nα)T m n +∞ t=0 e -γt ≤ C(n)e 0.01(n+1)T m n 1 1 -e -γ = C(n)e 0.01(n+1)T m n .Finally, notice thatP m (t) = e -γt Q m (e -αt ) = m-1 k=0α k e -(0.01+0.01k) , so we can select ϕ exp m (t) := P m (t). Proof of Lemma F.2.The key point of the proof is to note that the adaptability of B can be eliminated by the translation operator t -B.First, recall our proof of Lemma F.1. For the same Ψ T (•), for any n, m ∈ N + , there exists an absolute constant C(n) only depending on n and a polynomialQ m (x) = m-1 k=0 α k x k such that sup x∈[0,1] |Ψ T (x) -Q m (x)| ≤ C(n)e 0.01(n+1)T m n .Moreover, using the transform x = e -0.01(t-B+T ) (t ≥ 0) on the function Ψ and consider Φ T (t; B) := e -0.01(t-B+T ) Ψ T e -0.01(t-B+T ) , t ∈ [0, +∞).It is easy to verify that Φ T (•; •) satisfies thatΦ T (t; B) N = I(t = B).And we consider the function P m (t; B) := e -0.01(t-B+T ) Q m e -0.01(t-B+T ) , t ∈ [0, +∞).Then, for any 1 ≤ B ≤ T , the following error estimate holds: α k e -β k t such that∥P m (•; B) -I(• = B)∥ ℓ1(N) =∥ρ(•) -ϕ exp m (•)∥ ℓ1(N) ≤ C(n) m n ,whereβ k > 0 holds for any k ∈ [m].Proof of Lemma F.3.There exists C > 0 such that |ρ(t)| ≤ Ce -βt .Let α, γ > 0 be constants, and they will take specific values at the end of the proof.First, recall the standard bump function on [-1, 1]: Ψ(x) := exp -1 1-x 2 , x ∈ (-1, 1) 0, otherwise , and we can define the following constants for T ≥ 1:µ T = e -αT , σ T = 1 2 e -αT -e -α(T +1) ,and we consider the following bump functionΨ T ∈ C ∞ ([0, 1]): Ψ T (x) = V T Ψ x-µ T σ T , x ∈ (µ T -σ T , µ T + σ T ) 0, otherwise, where V T is a scaling constant such that Ψ T (e -αT ) = e γT ρ(T ).Consequently, we consider the sum of bump functions on [0, 1]:φ(x) := +∞ T =1 Ψ T (x).It is easy to verify that (µ T1 -σ T1 , µ T1 + σ T1 ) ∩ (µ T2 -σ T2 , µ T2 + σ T2 ) = ∅ for any T 1 ̸ = T 2 andEQUATIONFirst, we study the property of φ(•).We denote the absolute constants M k = sup x |φ (k) (x)|. Notice that for any k ∈ N,Ψ (k) T (x) = V T σ k T Ψ (k) x -µ T σ T .Therefore, it holds thatsup x∈(µ T -σ T ,µ T +σ T ) |φ (k) (x)| = sup x∈(µ T -σ T ,µ T +σ T ) |Ψ (k) T (x)| ≤ V T σ k T M k = e γT ρ(T ) e -αT -e -α(T +1) k M k e ≤ CM k e (1 -e -α ) k e (γ+kα-β)T .Therefore, if β ≥ γ + kα, then the following uniform bounds holds:sup x∈(0,1] |φ (k) (x)| = sup T ≥1 sup x∈(µ T -σ T ,µ T +σ T ) |φ (k) (x)| ≤ sup T ≥1 CM k e (1 -e -α ) k e (γ+kα-β)T ≤ CM k e (1 -e -α ) k := C(k, α).Consequently, we consider the smoothness of Φ at x = 0.Recalling the previous results, for any x ∈ (0, 1], we have|φ (k) (x)| x ≤ C(k, α) e (γ+kα-β)T µ T -σ T = 2C(k, α) 1 -e -α e (γ+(k+1)α-β)T , x ∈ (µ T -σ T , µ T + σ T ); |φ (k) (x)| x = 0, otherwiseThus, by induction, it is easy to verify that for any i < β-γ α (i ∈ N), φ (i) (0) = 0.Therefore, for any n < β-γ α (n ∈ N), φ (k) (0) = 0 holds for any 0 ≤ k ≤ n. Moreover, there exists absolute constant C(n, α) such that:max 0≤k≤n sup x∈[0,1] |φ (k) (x)| ≤ C(n, α).By Lemma G.5, for any m ∈ N + , there exists a polynomialQ m (x) = m-1 k=0 α k x k such that sup x∈[0,1] |φ(x) -Q m (x)| ≤ C(n, α) m n .Now we use the transform x = e -αt (t ≥ 0) on the function φ and considerΦ(t) := 1 e γt φ 1 e αt , t ∈ [0, +∞).It is easy to verify that Φ satisfies thatΦ(t) N = ρ(t) N .Moreover, we consider the functionP m (t) := 1 e γt Q m 1 e αt , t ∈ [0, +∞).Then for any n < β-γ α (n ∈ N), the following error estimate holds:∥P m (•) -ρ(•)∥ ℓ1(N) = +∞ t=0 |P m (t) -Φ(t)| = +∞ t=0 e -γt Q m e -αt -Ψ T e -αt ≤ C(n, α) m n +∞ t=0 e -γt .By choosing α = 5 • 10 -3 and γ = 10 -2 β, it holds that 99β < β-γ 2α = β-γ α . Thus, we obtain our result: for any n ∈ [⌊99β⌋] (β ≥ 1/99), the following error estimate holds: ∥P m (•) -ρ(•)∥ ℓ1(N) ≤ C(n) m n +∞ t=0 e -γt = C(n) m n 1 1 -e -10 -2 β = C(n) m n .I(• = T ) -ϕ poly m (•) ℓ1(N+) ≤ C(n)T 1.01(n+1) m n ,whereβ k > 1 holds for any k ∈ [m].Proof of Lemma F.4. Let α, γ > 0 be constants, and they will take specific values at the end of the proof First, recall the standard bump function on [-1, 1]: Ψ(x) := exp -1 1-x 2 , x ∈ (-1, 1) 0, otherwise , and we can define the following constants for T ≥ 1:µ T = 1 T α , σ T = 1 T α - 1 (T + 1) α .Then we consider the following bump functionΨ T ∈ C ∞ ([0, 1]): Ψ T (x) = V T Ψ x-µ T σ T , x ∈ (µ T -σ T , µ T + σ T ) 0, otherwise, where V T is a scaling constant such that Ψ T ( 1 T α ) = T 1+γ . First, we consider the approximation of Ψ T on [0, 1].Notice that Ψ T ∈ C ∞ ([0, 1]), and Ψ Ψ (k) (x) ≤ M (n).Notice that for any k ∈ N and x ∈ [0, 1],Ψ (k) T (x) = V T σ k T Ψ (k) x -µ T σ T .Therefore, the following upper bound holds: 1+α) .M T (n) = max 0≤k≤n V T σ k T M (n) = V T σ n T M (n) = T 1+γ e (1/T α -1/(T + 1) α ) n M (n) ≤ T 1+γ (T + 1) n(1+α) M (n)e α n ≤ 2 n M (n)e α n T 1+γ+n(1+α) := C(n, α)T 1+γ+n(By Lemma G.5, for any m ∈ N + , there exists a polynomialQ m (x) = m-1 k=0 α k x k such that sup x∈[0,1] |Ψ T (x) -Q m (x)| ≤ M T (n) m n ≤ C(n, α)T 1+γ+n(1+α) m n .Now we use the transform x = 1 t α (t ≥ 1) on the function Ψ and considerΦ T (t) := 1 t 1+γ Ψ T 1 t α , t ∈ [1, +∞).It is easy to verify that Φ T satisfies thatΦ T (t) N+ = I(t = T ).Moreover, we consider the functionP m (t) := 1 t 1+γ Q m 1 t α , t ∈ [1, +∞).Then by choosing α = γ = 0.01, the following error estimate holds:∥P m (•) -I(• = T )∥ ℓ1(N+) = +∞ t=1 |P m (t) -Φ T (t)| = +∞ t=1 1 t 1+γ Q m 1 t α -Ψ T 1 t α ≤ +∞ t=1 1 t 1+γ M T (n) m n ≤ C(n, α)T 1+γ+n(1+α) m n +∞ t=1 1 t 1+γ = C(n)T 1.01(n+1) m n +∞ t=1 1 t 1+0.01 = C(n)T 1.01(n+1) m n .Finally, notice that P m (•)satisfies to P m (t) = 1 t 1+γ Q m 1 t α = m-1 k=0 α k t -(1.01+0.01k) , so we can select ϕ poly m (t) := P m (t). Proof of Lemma F.5.The key point of the proof is to note that the adaptability of B can be eliminated by the rescaling operator t/B.First, recall our proof of Lemma F.4. For the same Ψ T (•), for any n, m ∈ N + , there exists an absolute constant C(n) only depending on n and a polynomialQ m (x) = m-1 k=0 α k x k such that sup x∈[0,1] |Ψ T (x) -Q m (x)| ≤ C(n)T 1.01(n+1) m n .We use the transform x = 1 t 0.01 (t ≥ 1) on the function Ψ and considerΦ T (t; B) := B tT 1.01 Ψ T B tT 0.01 , t ∈ [1, +∞).It is easy to verify that Φ T (•; •) satisfies thatΦ T (t; B) N+ = I(t = B).And we consider the functionP m (t; B) := B tT 1.01 Q m B tT 0.01 , t ∈ [1, +∞).Then, for any 1 ≤ B ≤ T , the following error estimate holds:∥P m (•; B) -I(• = B)∥ ℓ1(N+) = +∞ t=1 |P m (t; B) -Φ T (t; B)| = +∞ t=1 B tT 1.01 Q m B tT 0.01 -Ψ T B tT 0.01 ≤ +∞ t=1 1 t 1.01 sup x∈[0,1] |Q m (x) -Ψ T (x)| ≤ C(n)T 1.01(n+1) m n +∞ t=1 1 t 1.01 = C(n)T 1.01(n+1) m n .Due to the arbitrariness of B, the proof is completed. (t) = m k=1 α k t -β k such that ρ(•) -ϕ poly m (•) ℓ1(N+) ≤ C(n) m n ,whereβ k > 1 holds for any k ∈ [m].Proof of Lemma F.6.There exists C > 0 such that |ρ(t)| ≤ C/t β .Let α, γ > 0 be constants, and they will take specific values at the end of the proof First, recall the standard bump function on [-1, 1]: Ψ(x) := exp -1 1-x 2 , x ∈ (-1, 1) 0, otherwise , and we can define the following constants for T ≥ 1:µ T = 1 T α , σ T = 1 2 1 T α - 1 (T + 1) α ,and we consider the following bump function Ψ T ∈ C ∞ ([0, 1]):Ψ T (x) = V T Ψ x-µ T σ T , x ∈ (µ T -σ T , µ T + σ T ) 0, otherwise, where V T is a scaling constant such that Ψ T ( 1 T α ) = T 1+γ ρ(T ). Consequently, we consider the sum of bump functions on [0, 1]:EQUATIONFirst, we study the property of φ(•).We denote the absolute constantsEQUATIONT (x) = V T σ k T Ψ (k) x -µ T σ T .Therefore, it holds thatsup x∈(µ T -σ T ,µ T +σ T ) |φ (k) (x)| = sup x∈(µ T -σ T ,µ T +σ T ) |Ψ (k) T (x)| ≤ V T σ k T M k = T 1+γ ρ(T ) 1 T α - 1 (T +1) α k 2 k M k e ≤ (T + 1) k(1+α) T 1+γ-β C2 k M k e α k ≤ 2 k(2+α) CM k e α k T 1+γ+k(1+α)-β . Therefore, if k ≤ β-(1+γ)1+α , the following uniform bounds hold:sup x∈(0,1] |φ (k) (x)| = sup T ≥1 sup x∈(µ T -σ T ,µ T +σ T ) |φ (k) (x)| ≤ sup T ≥1 2 k(2+α) CM k e α k T 1+γ+k(1+α)-β ≤ 2 k(2+α) CM k e α k := C(k, α).Consequently, we consider the smoothness of Φ at x = 0.Recalling the previous results, for any x ∈ (0, 1], we have|φ (k) (x)| x ≤ C(k, α) T 1+γ+k(1+α)-β µ T -σ T ≤ C(k, α)2 2+α α T 1+γ+(k+1)(1+α)-β , x ∈ (µ T -σ T , µ T + σ T ); |φ (k) (x)| x = 0, otherwiseThus, by induction, it is easy to verify that for any i <β-(1+γ) 1+α (i ∈ N), φ (i) (0) = 0.Therefore, for any n < β-(1+γ) 1+α(n ∈ N + ), φ (k) (0) = 0 holds for any 0 ≤ k ≤ n. Moreover, the following uniform bound holds:max 0≤k≤n sup x∈[0,1] |φ (k) (x)| ≤ C(n, α).By Lemma G.5, for any m ∈ N + , there exists a polynomial Qm (x) = m-1 k=0 α k x k such that sup x∈[0,1] |φ(x) -Q m (x)| ≤ C(n, α) m n .Now we use the transform x = 1 t α (t ≥ 1) on the function φ and considerΦ(t) := 1 t 1+γ φ 1 t α , t ∈ [1, +∞).It is easy to verify that Φ satisfies thatΦ(t) N+ = ρ(t) N+ .Moreover, we consider the functionP m (t) := 1 t 1+γ Q m 1 t α , t ∈ [1, +∞).Then for any n < β-(1+γ) 1+α (n ∈ N), the following error estimate holds:∥P m (•) -ρ(•)∥ ℓ1(N+) = +∞ t=1 |P m (t) -Φ(t)| = +∞ t=1 1 t 1+γ Q m 1 t α -Ψ T 1 t α ≤ C(n, α) m n +∞ t=1 1 t 1+γ .By choosing α = 10 -2 and γ = 10 -4 β, we have 0.99β -1 = β-γ 1+α -1 = β-(1+γ+α) 1+α < β-(1+γ)1+α . Thus, we obtain our result: for any n ∈ [⌊0.99β⌋ -1] (β ≥ 2/0.99), the following error estimate holds: (Ma et al. (2020) ). For any f ∈ B and m ∈ N, there exists a two-layer ReLU neural∥P m (•) -ρ(•)∥ ℓ1(N+) ≤ C(n) m n +∞ t=1 1 t 1+γ ≤ C(n) m n +∞ t=1 1 t 1+10 -4 = C(n) m n . G.3 Useful approximation lemmas Lemma G.5 (Jackson (1930)). Let f ∈ C n ([0, 1]) with f (0) = f ′ (0) = • • • = f (n) (0) = 0. Then for any m ∈ N + , there exists a polynomial Q m (x) = m-1 k=0 α k x k such that ∥f -Q m ∥ L ∞ ([0,1]) ≤ M (n) m n , where M (n) = max k≤n f (k) L ∞ ([0,1]) . Lemma G.6network f m (x) = m k=1 a k σ(b ⊤ k x + c k ) with m neurons such that ∥f -f m ∥ L ∞ ([0,1] d ) ≤ Õ ∥f ∥ B √ m .As detailed in Section 1, our theoretical analysis reveals the following novel insights into the expressive power and mechanisms of Transformer:Insight (1). The distinct roles of the number of layers, the number of Attn heads, and the width of FFN layers. (1a) Deeper Transformers can handle tasks with memories with more intricate interrelationships, such as nested relationships (Type II). (1b) In contrast, for tasks with memories lacking such interrelationships (Type I), a single-layer Transformer with sufficient Attn heads and FFN width should suffice.Insight (2). The different roles of Attn layers and FFN layers. (2a) FFN layers are tasked with approximating nonlinear memory functions and the readout function, (2b) while Attn layers are responsible for extracting the tokens from the memory locations.Insight (3). The functionality and necessity of Dot-product (DP). (3a) For the relatively simple Task I, DP is not necessary and can be omitted. (3b) However, for the more complex Task II, DP provides necessary nonlinearity: the cooperation between DP and RPE provides the needed interaction between the temporal space and the token space.Insight (4). To validation of our theoretical insights (1a)∼(4b), we conduct 8 experiments, from simple toy models to more complex LLM pre-training. The experiments are conducted on 1 A100.Objective. As indicated in Section 4, numerous NLP tasks exhibit complex interrelationships among tokens and belong to our Task II. This experiment aims to verify our Insight (1a): for such tasks, increasing the number of layers L is more efficient than increasing the number of Attn heads H.Setup. Specifically, we pretrain decoder-only Transformers (Vaswani et al., 2017) with different L and H on the OpenWebText dataset (Gokaslan and Cohen, 2019) for 10,000 iterations (approximately 1B tokens) on 1 A100, using cross-entropy loss and AdamW with the same hyperparameters. To ensure comparability, we meticulously balance the total number of parameters across both experimental setups.Results and conclusion. The final validation losses are shown in Table 2 . By comparing these two subtables, the benefits brought by increasing L are much greater than the benefits brought by increasing H (0.802 > 0.136), thereby corroborating our Insight (1a). Training proceeds for 10,000 iterations (1M samples) using squared loss and AdamW with the same hyperparameters.Results and conclusion. The final validation losses are shown in Table 4 . The tables indicate that, for learning a sparse Boolean function with a "complex" readout function and "simple" memories, increasing m can significantly improve the performance (0.49 → 0.002), almost completing this task perfectly. Conversely, increasing H fails to yield substantial improvement. This empirical evidence supports our Insight (2a). Objective. Contrasting with Experiment (2a), this experiment aims to verify our Insight (2b): for learning a sparse Boolean function with a "simple" readout function and "complex" memories, increasing the number of Attn headers H can substantially improve the performance while increasing FFN width m will offer almost no benefit.Setup. Specifically, we train single-layer DP-free Transformers with different H and m to learn a sparse Boolean function with a "simple" linear readout function (g * ) and relatively "complex" memories (x 48 , x 56 , x 99 ): f * (x) := g * (x 48 , x 56 , x 99 ) := x 48 + x 56 + x 99 for any input sequencex = (x 1 , • • • , x 1000 ) ∈ {±1} 1000 .Training processes for 10,000 iterations (1M samples), using squared loss and AdamW with the same hyperparameters.Results and conclusion. The final validation losses are presented in Table 5 . The tables indicate that, for learning a sparse Boolean function with a "simple" readout function and "complex" memories, increasing m can significantly improve the performance (1.16 → 10 -6 ), closely achieving task perfection. In contrast, increasing m brings almost no benefits. This empirical evidence supports our Insight 2(b).Objective. As mentioned in Section 3, learning sparse Boolean functions has no interactions among the memories and belongs to our Task I. This experiment aims to verify our insight (3a): for such Results and conclusion. The final validation losses are shown in Table 6 . The findings illustrate that a DP-free Transformer equipped with a sufficient H (32) and m (256) is adept at accurately representing the given sparse Boolean function. Additionally, the Incorporation of the DP structure into the layers contributes marginally to performance enhancement. This substantiates our Insight (3a). Objective. As indicated in Section 4, numerous NLP tasks exhibit complex interrelationships among tokens and belong to our Task II. This experiment aims to verify our Insight (3b): for such tasks, the utilization of DP structure in Attn layers is necessary.Setup. Specifically, we pre-train Transformers with DP or without DP on the OpenWebText dataset for 10,000 iterations (approximately 1B tokens) on 1 A100, using cross-entropy loss and AdamW with the same hyperparameters.Results and conclusion. The final validation losses are presented in Table 7 . As shown in the table, for NLP pre-training tasks, Transformer incorporating DP structure is more efficient than Transformer without DP (5.796 < 5.830, 5.374 < 5.486, 4.994 < 5.274) , thereby supporting our Insight 3(b). Objective. This experiment aims to verify our Insight (4a): for learning Task III with heavy-tailed memories, Transformers with log-type RPE are efficient, whereas those with lin-type RPE fail.Setup. Specifically, we train single-layer, FFN-free, DP-free Transformers with log-type RPE or lintype RPE and varying numbers of Attn heads H. The target function involves a heavy-tailed memory kernel ρ(t) = t -0.5 : f * (x) := 1000 s=1 x s ρ(1000 -s) for any input sequence x = (x 1 , • • • , x 1000 ) ∈ {±1} 1000 . Training processes for 10,000 iterations (1M samples) using squared loss and AdamW with the same hyperparameters.Results and conclusion. The final validation losses are shown in Table 8 . As shown in the table, to learn heavy-tailed memories, even single-head Transformer with log-type RRE can complete it perfectly (< 10 -5 ). Conversely, Transformers employing lin-type RRE exhibit limited improvement even with up to 64 heads (0.19). This empirical evidence supports our Insight (4a). Objective. In contrast to Experiment (4a), this experiment aims to verify that for learning our Task III with light-tailed memories, Transformers with lin-type RPE are efficient, whereas those with log-type RPE fail.Setup. Specifically, we train single-layer, FFN-free, DP-free Transformers with log-type RPE or lintype RPE and varying numbers of Attn heads H. The target function involves a heavy-tailed memory kernel ρ(t) = e -5t : f * (x) := 1000 s=1 x s ρ(1000 -s) for any input sequence x = (x 1 , • • • , x 1000 ) ∈ {±1} 1000 . Training processes for 10,000 iterations (1M samples) using squared loss and AdamW with the same hyperparameters.Results and conclusion. The final validation losses are shown in Table 9 . As shown in the table, to learn light-tailed memories, even single-head Transformer with lin-type RRE can complete it perfectly (< 10 -7 ). Conversely, Transformers employing log-type RRE exhibit limited improvement even with up to 64 heads (5.3 × 10 -4 ). This empirical evidence supports our Insight (4b).Table 9 : Results of the experiment supporting Insight (4b).H = 1 H = 4 H = 16 H = 64 type=log 9.1e-4 3.7e-3 2.6e-3 5.3e-4 type=lin <1e-7 <1e-7 <1e-7 <1e-7Our theoretical insights and empirical evidence can directly lead to the following 8 practical implications, such as the strategic selection of Transformer hyperparameters for specific tasks.• Implication (1a). (supported by Insight (1a) and Experiment (1a)) For sequence modeling tasks with complex interrelations between memories, such as many NLP applications, enhancing the number of layers L is more beneficial than increasing the number of Attn heads H and FFN width m.• Implication (1b). (supported by Insight (1b) and Experiment (1b)) For simple sequence modeling tasks with almost no memory intercorrelation, such as the learning of sparse Boolean function, improving performance necessitates only sufficient H and m in a single-layer Transformer, without a need to increase L.• Implication (2a). (supported by Insight (2a) and Experiment (2a)) For sequence modeling tasks with complex readout or memory functions, increasing m can significantly improve performance.• Implication (2b). (supported by Insight (2b) and Experiment (2b)) For sequence modeling tasks with multiple memories, increasing H can markedly improve performance.• Implication (3a). (supported by Insight (3a) and Experiment (3a)) For simple sequence modeling tasks with almost no memory correlations, such as learning sparse Boolean functions, omitting the DP structure in Attn layers can still perform well.• Implication (3b). (supported by Insight (3b) and Experiment (3b))For sequence modeling tasks with complex correlations between memories, such as many NLP tasks, preserving the DP structure in attention layers is crucial for achieving high performance due to its indispensable nonlinearity. • Implication (4a). (supported by Insight (4a) and Experiment (4a))For sequence modeling tasks with heavy-tailed memories, the employment of log-type RPE (such as T5's RPE and KERPLE (log)) is recommended over lin-type RPE (such as Alibi). • Implication (4b). (supported by Insight (4b) and Experiment (4b))For sequence modeling tasks with light-tailed memories, the employment of lin-type RPE (such as Alibi) is recommended over log-type RPE (such as T5's RPE and KERPLE (log)).• It 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 a 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 


Decision: This paper is a detailed analysis of the memory mechanisms of transformers. Its analysis relies on the notion of M-sparse memories, which are specific targets of the models, and then approximation properties are studied.

I agree with the reviewers that, despite being simplified, this analysis leads to some interesting insights. The paper is mostly well written: I'd recommend to strengthen its theoretical motivation in the final version of this work.

Reviews: review: paper_summary: paper_summary: The paper provides a thorough analysis of the expressive power of Transformers. It does so by investigating the relative importance of different architectural components, such as the mixing layer (dot product attention), the feed-forwad block and positional embeddings. More specifically, the paper studies three different tasks, characterised by different levels of complexity, sharing some key properties with relevant realistic applications such as n-gram models, sparse Boolean functions (Task I), Adaptive sparse Boolean functions, parsing, part-of-speech tagging (Task II), feature extraction in image and signal processing (Task III). On each of such tasks, the paper studies the approximation rates of transformer models defined in terms of their number of layers $L$ and heads $H$, the width of the feed-forward module $m$ and the type of relative positional embedding utilised (i.e. either Alibi or T5 style). Through its theoretical analysis the paper shows that the necessary model's complexity needs to adapt to the complexity of the task. Moreover by investigating the role of different components, the paper shows that dot-product attention is necessary for more complex tasks (Task II) while its dot-product free variant provably fails. Nevertheless, the authors show that the task can still be solved with a more parameter efficient alternative. In addition, the role of the feed-forward blocks is mainly to approximate readout functions and memory functions, aligning with classical results on approximating Barron functions. The theoretical results are corroborated with empirical results.
strength_weakness: strength_weakness: * Some concepts could be better introduced: for example, it was not clear to the reviewer what the authors meant by "memories" in the introduction of the paper. While this gets clearer later, it would be helpful to clarify it earlier.
* Layer normalization, an important component of modern transformers, does not seem to be included in the analysis. What effect do you expect it to have on your results?
* The role of the embedding dimension $D$ is not considered in the reported rates. What is the effect of varying $D$ on the approximation rates of the model?
questions: questions: See weaknesses section.
limitations: limitations: The limitations of the paper are discussed in section 7
paper_summary: paper_summary: The paper investigates the approximation capabilities of transformers with relative positional encodings and derives approximation rates for three types of sequence modeling tasks. Each task corresponds to a particular choice of target function class. Namely, a first class of mappings are fixed, long but sparse memories (equation (5)), and the authors focus on dot-product free transformers. A second class are adaptive, long but sparse memories (equation (8)), and the authors consider deep transformers with specific precision and no SoftMax. The last class of mappings are essentially sparse memories and consist of convolving the input sequence with different kernels where, again, the considered Transformers are dot-product free.
Each approximation rate is commented on the role of the feedforward and self-attention components, the role of dot-product attention (that is, the fact that the attention maps depend on the input sequence through pairwise interactions), and the effect of relative position encoding (whether it is of linear or logarithmic type).
strength_weakness: strength_weakness: - Unless I missed something, the "true" attention mechanism (line 104) is never used in the paper to derive approximation rates. In sections 3 and 5 the attention is DPF, while in section 4 there is no softmax and quantization is used. I don't think this is a major problem, but it should be emphasised (perhaps by extending remark 2.2) that you never consider the transformer with all the bells and whistles. 

- I understand that the dimension of the embeddings grows with $Md$. This is not mentioned in the main text, nor commented on in the supplement. How does this compare with previous work? 

- Also, you mention that the number of heads needed grows at least polynomially with the $T_i$'s. I understand that this is due to the particular choice of RPE. Would other types of PE give a better dependency in the $T_i$'s ?  How does the current dependency compare with previous works? 

- Paragraph l. 274 to l. 277 is unclear. When do you use this alternative in the rest of the paper? 

- Typo in l. 281

- l. 282, I don't understand the notation for the lower bound on $m$.
questions: questions: - Please see some questions in the Weaknesses part. 

- What do you mean by rate $n$ in all the theorems ? Is there an optimal choice for $n$ ? 

- What is the main reason why you did not consider the SoftMax in section 4 ? 

- How does $C(n)$ behaves with $n$ ? 

- Could you approximate the model with specific precision with another Transformer which does not rely on specific precision ?  

- Overall, the spirit of the approximation in the paper is always to form augmented tokens $(x_{t}, x_{t-t_1}, \dots x_{t-t_M})$ using attention and to apply the MLP on top of it. Do you think this is the "optimal" way ? And if so, what are the reasons behind it ?
limitations: limitations: Yes, the authors adequately addressed the limitations of their work.
paper_summary: paper_summary: This paper conducts a systematic study on the expressive power and mechanisms of Transformers for sequence modeling. It explores various properties of Transformers, including the number of layers, attention heads, width, and the use of dot production. The theoretical results are supported by experimental evidence.
strength_weakness: strength_weakness: The key weakness of this paper lies in its unclear presentation of motivation, innovation, and contributions. The detailed reasons are as follows:

1) The motivation of this paper appears weak. The authors state their motivation as "to gain a better understanding of how Transformers work in practice." However, there are already numerous studies exploring the expressive power of Transformers, covering most of the topics in this paper. It is unclear why the authors believe the current understanding of Transformers is insufficient and why the community needs this paper.

2) The technical contributions of this work are not clearly presented. It is difficult to discern which conclusions are derived from known techniques and which are based on new techniques proposed by the authors. Additionally, the nature of these new techniques is not clearly explained.

3) The paper's analysis is based on dividing tasks into three categories: modeling fixed, long but sparse memories; modeling adaptive, long but sparse memories; and modeling essentially sparse memories. However, the necessity of this categorization and the relationships between these tasks are unclear. The authors claim these categories are prevalent, but the supporting evidence is weak.
questions: questions: 1) This paper includes numerous proofs, making it challenging to verify their correctness. Could the authors provide a proof sketch for Theorem 4.4?

2) The tightness of the bound is also uncertain. Could the authors provide a numerical result demonstrating the bound in a toy case?
limitations: limitations: N/A

Comments: comment: We thank the reviewer for the positive feedback of our response. We appreciate your support very much!
Dear authors,

I have read the rebuttal. Thank you for your work and the answers to my concerns. I am satisfied with the authors' reply and will keep my score.

Best,
Reviewer xF1Y
Thanks again for your valuable time and effort in reviewing our work!

We are wondering if our responses address your questions or concerns.

We are happy to try to address any other comments in the time remaining.
We would like to reiterate our gratitude for your valuable recommendation and positive feedback. Thank you for raising the score!
We are delighted that our responses have addressed your questions. Thank you very much for your support!
I appreciate the authors' detailed response and confirm that they have addressed all the concerns raised. I also find the newly added experiments to be both interesting and insightful. Based on this, I have decided to increase my score to 6.
Dear authors, 

I have read the rebuttal. Thank you for responding to my questions. I have noted that the authors will incorporate the conclusions of the discussions with the reviewers in a revised version, and I have decided to maintain my score. 

Best,

Reviewer iDXk