Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling
Authors: Mingze Wang
Weinan E
Venue: NeurIPS 2024 poster (2024)
Keywords: Transformer
expressive power
theoretical insights
Primary area: learning_theory
TL;DR: We theoretically investigate the expressive power and the mechanisms of Transformer for modeling long but sparse memories.

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.

Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling
Mingze Wang
School of Mathematical Sciences, Peking University, Beijing, China mingzewangōstu, pky.sttuupppuuu..... edu.cn cn
Weinan E
Center for Machine Learning Research and School of Mathematical Sciences, Peking University, Beijing, China Al for Science Institute, Beijing, China weinan@math, pku. edu. en
Abstract
We conduct 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 the dot-product self-attention, positional encoding and feed-forward layer, affect its expressive power, and study their combined effects through establishing explicit approximation rates. Our study reveals the roles of critical parameters in the Transformer, such the number of layers and the number of attention heads. These theoretical insights are validated experimentally and offer natural suggestions for alternative architectures.
Introduction
In recent years, Transformer networks (Vaswani 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 their comprehensive understanding. A typical Transformer comprises multiple layers, each consisting multi-head self-attention (Attn) sub-layer and 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 better understanding of how Transformer works practice, we need study several key issues. These include:
(i) How do the key hyper-parameters, for example, the number of layers, the number of Atin heads and the with of FFN luyers, affect the performance of the Transformer network?
(ii) How do the Atnn and FFN layers contribute differently to the overall performance?
(ii) How does DP attention work, and the DP structure necessary?
(iv) How efficient is PE in modeling long-rand range correlations?
Extensive empirical research on Transformer components has led the proposal of numerous alternatives to the current structure of Transformer. For example, several relative positional encodings (RPE) (Shaw al., 2018: Raffel et al., 2020; Su al., 2024; Press et al., 2022) have been proposed
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to substitute the original absolute positional encoding (APE), yielding superior performance in challenging tasks like length generalization (Ontanón 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 summarizee 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 Trans- former 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 interrelationshiiss, 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 few previous tokens in an independent way, we can treat each such dependence by 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 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. x = (z),.... "ah.....,,.. xx))² E IRd and W = (Wij) (14j)m E Rmxxn The standard Euclidean inner product between two vectors denoted by (- and the Ip norm of vector is represented by I|-IIp-
We employ standard big-O notations O, θ to hide absolute positive constants and use Ö, Ô to further hide logarithmic constants. For any positive integer n, let [n] = (1,... nn. Denote by I(F) the indicator function for an event E. Denote by V b max(a, 6} for real number a, b.

---

2.1 Sequence modeling with long but sparse memories
Sequence modeling. For convenience, we consider input sequences of infinite length E 2). 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 (gt)tez F is
generated from the input sequence X (æz) X' Rdxž via an unknown mapping H.(.) dependent on the input sequence up to the prediction time, and this can be expressed as:
y: = ( = f f 2t -1-1, 21-2, t E Z.
(1)
Our objective is to learn the mapping (-).) Additionally, we define the norm || || = suprez x || (X)I,. Without loss of generality, assume || S for any X E X
and set the output dimension e = 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. Section 4, and 5, we will formally define these different types and investigate Transformer's ' capacity to model them.
2.2 Transformer architecture
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 æ; W Wgæ, + bg, where WE E IR Dxd bg E RR,. Subsequently, typical L-layer Transformer with residual block operates according the formulation:
( = xx (1-1) + Attn 2 (X (x))))),
LE [L];
x = x (1-)) FFN (X ())),,
IE [4].
At the 1-th layer, FFN denotes a standard (point-wise) two-layer ReLU networks with m neurons: for given input E RDD, FFN("( = Σ ag (b (l) (1) where a(-) 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 ())) refers to a multi-head self-attention, elaborated below.
Multi-head self-attention. Our focus lies on standard dot-product Attn, denoted as Attn (.) and consisting of // heads. When applied an input sequence X, Attn operates as follows:
Attn Attnn(X (X) !! Σ
w (LA) ssottmax, ((W!i) (1.)) x, w )) -RaN).
(3)
(LAb (.A.)) (,()))) ((())) correspond to the query, key, value, output matrices of the (I, h) head, respectively. softmax, represents taking softmax normalization across column. Furthermore, R(.A) E 2 denotes the relative positional encoding matrix, which satisfies R!(,A) -oo for t. < in the next-token prediction paradigm. Consequently, the t-th output of Attn expressed as:
Here, the parameters ((..))
Q
Wy
(L.h) xi exp ((Weli) (1,)) æe, ((l. xe-s) )) + R
H
Attn (1) (x)
Σ exp ((wl De, w(ll) (e.)) + Ry
h=1==0
Logarithmic and Power relative positional encoding, As highlighted in Section A, among various types of RPEs, the RPEs used T5 and KERPLE((Og) demonstrate superior performance over Alibi, significantly outperforming other RPEs and APES in the length generalization task (Kazemnejad al., 2023; Chi al., 2022). This finding motivates our focus on the T5-type, KERPLE((og), and Alibi-type RPEs throughout this paper. All of these RPE matrices are Toeplitz, with the form of

---

RI.s r(t s). Notably, for T5 and KERPLE r(t s) undergoes an initial linear decrease followed by a logarithmic decrease as the relative distance s increases (Please refer to Section G.1 for more details). In contrast, for Alibi, r(t - x) decreases linearly. Inspired by these discussions, we examine the following RPEs with different decay rates:
log 2, 00,
221
0 otherwise
Olog (z)
(2n = -00,
otherwise
-00
We will study Transformer with Otypa RPE (type E {log, lin]), Specifically, the RPE in the (4, h)-th head (3) is as follows:
(L.)) R2, == plt.)) Dcypa - -s),
where p(l.) E R.+ is trainable parameter.
Remark 2.1. For standard Transformer (2) incorporating Attn (3) with RPE (4), the parameters are:
(1) in the FFN layers; Wr(.)) wilk)) willii) p(lh) w the embedding matrix Wg: ag b/²) :%:"% C
Q K
in 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 introduced here. For examples, Transformer (2) using Glog Migi/
RPE (4) is referred to as "Transformer with log/lin-RPE" Transformer with (1.h), w (L,A)) 0 is called "dot clot-product-free Transformer".
2.3 Expressive power via approximation theory
This paper delves into the expressive power of Transformer through the lens of approximation theory, with 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 (Jackson- type) (Jackson, 1930). Universal approximation investigates whether the hypothesis class is dense in the target class. Although this property is fundamental, does not offer detailed insights into approximation efficiency. In contrast, approximation rates go deeper, emphasizing the efficiency of the approximation. typical example within this framework 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 characterization of the approximation efficiency, i.e., how many neurons are needed achieve a certain approximation accuracy? This gap was addressed by the Barron space theory (E et al., established that for any function within Barron space E B (Appendix G.2), 2NNs with neurons (denoted by Hm) can approximate them efficiently, at a rate of inf inff,,,HH E.. | fmll S O(I /m), remarkably independent of the input dimension d, thus avoiding the Curse of Dimensionality (Bellman, 1966; Bach, 2017).
2019; 2021; Ma et al., 2020).
3 Fixed, long but M M-sparse memories
3.1 Problem formulation
Fixed, long but M M-sparse memories. In this section, we investigate fundamental category of long but sparse memories. Our focus on scenarios where the positions of the sparse memories remain fixed and are independent of the tokens. The target function is represented by:
f(z, Ti-T; Tt-TTs)
where < Ti .... <M +oo signify the fixed positions of the memories. Despite the memories being fixed (okken-ndeependett) and sparse (finite M), the task can still be complex due to potentially long-range memories "T,,...,TT can be large enough).

---

Examples. (I) For Boolean inputs, (5) aligns with sparse Boolean functions, also studied in (Edelman
al., 2022; Bhattamishra al., 2022). Notably, Bhattamishra al. (2022) observed that Transformers outperform LSTMs in learning sparse parities. (II) Selecting the simplest case of T; 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 E C. 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 -spaase memories as:
H = (H: ( = (5), where < < +oc, JEC,JE
TM
(6)
Transformer hypothesis class. As mentioned in Section 1, one of our main aims is to study the necessity and roles of different components in Transformer, such as DP and RPE. This section focuses on the "simplest" one-layer Transformer and investigates whether it can effectively model this task. Formally, our hypothesis class includes all one-layer DP-free Transformers, configured with Attn heads and FFN width me
TFDPE ptpee = (TF: TF is L-layer, H[-hed, m-width (I.H,m)
(7)
dot-product Transformer with type-RPE).
3.2 Theoretical results and insights
Theorem 3.1 (Approximation rate). For any target H E H. (6), rate E N., and H, E N+, there exists 1-layer Transformer TF E TF F. (7) and constant (nn) such that
H TF S EPEN + I1 Eatca (tyoe)
0 C(n)
Σ
M
0.017;
2+1
type = lin
where EPPN-
[Lflle v/m
and Extra (type)
Hm
i==
1+1
Cin)
Ei=1 T:1.01
M
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 Tr...., Tas and the complexity of the readout function f. The approximation error comprises two components: the error in the FFN component EFEN and the error in the Attn component E (type). The error EFPN aligns with classical results, showcasing its effectiveness approximating Barron functions. On the other hand, Auu (type) hinges 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 deferred to Appendix B. We can draw some insights from Theorem 3.1 and its proof.
Different roles of the Attn layer and the FEN 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 æ;-T; by approximating the memory kernel T(-= : T.). These components together enable effective modeling of fixed, long, but sparse memories.
Non- 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 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, can successfully tackle the same task even without the dot product in the attention layer.
result reveals that one-layer Transformer
Effeet 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 slightly exponential rate for lin-RPE
5

---

and at polynomial rate for log-RPE. The subtle difference is attributed to the relative simplicity of approximating the memory kernel If- T.}. We will explore more complex task in Section where the impact of different types of RPE becomes even more pronounced.
4
K A-Adaptive, long but M -sparse memories
4.1
Problem formulation
In this section, we delve into a more complex modeling scenario closely aligned with typical language processing tasks.
K 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:
Y/ f(z "
(8)
where the positions of the memory tokens " tu follow a nested relationship:
4 91 (zx)): la 92 -t .;......... ;l++1 9K+1 (Ix, 2t-1, 2e Er f = gM (2,, 0t- xt-t
Here, M denotes the number of memory tokens, and K measures the nesting complexity in the memory structure. We assume that memory functions Ii generate positive integers for the input tokens, and there exist maximum values T; such that gi S T. 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.c., 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:
yt f Ft- Bt-tm)
where 4 g(a;;), i [M].
Target class. The target classes for modeling adaptive, long but sparse memories in both warm-up and general cases are as follows:
(1.M) : HH: H2(X) = (9), where E B,, S 9. S T. E [M]; BBCc)
(10)
Hddda MK
H (X) (8), where 9i E B,1 $ 9: S T, E [M] Bn
(11)
Examples. Adaptive memories are commonly encountered in practical scenarios. (I) Adaptive sparse Boolean faneeaanfnncooon functions, e.g- B/ = Ft Tt-g(xz) T(-o((t-a(ze)) where X E 2+ g(x) = for x = and g(x) for x = 1. This fits within our framework (8) with K = M = 2. (II) Multi-step reasoning, e.g., modeling the K -aadaptive, long, but K-sparse memories contains complicated K-step reasoning task, which require the sequential search following the rule ((-.. ((x, + zz-t,) H zz-tk-1) + Iz-tx- (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 vary depending the content. Additionally, the nested structure is a fundamental characteristic of natural language (Hawkins, 2021).
Tt-tz" ..-) +
Transformer hypothesis class. Some previous works Yun al. (2019); Kim et al. (2022) treated the softmax with normalization as an approximation 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, consider Transformer with specific precision, detailed in Appendix C. The precision technique is widely used LLM training (Kalamkar et al., 2019), such as BF1oat16. Formally, the hypothesis class is defined as follows, encompassing all normalization-fre T--layer Transformer, configured with H Attn heads and FFN width m and using type-RPF: and specific precision.
hardmax, suggesting the potential importance of
TFyype (L. = (TF: :TF is an L-layer, H-head, m-width
(12)
Transformer with type-RPE and specific precision).

---

4.2 Theoretical results and insights: The warm-up case
Theorem 4.1 (Approximation rate, warm-up case). For any target H Hallar (8), rate N++ and H, m E N4, there exists two-layer Transformer TF
T (2.H.m) (12) and constant C(n)
|99:
type lin then the following
such that: if the width satisfies approximation rate holds:
[|oo 9: T.
type log
H TF S EFFN + IIf ExSTa (type).
1 C(n)
M
0.017;
n+1
type lin
where EPFN
Ô
[Lflle /mn
and ExttH (type)
==1
0
C(n)
M 2i=1 T:..01
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 the FFN component EFEN and the error in the Attn component Auu (type). A critical difference from 1.1 is the presence of the condition related the width m of FFN layers. This term arises from using the FFN layer approximate the memory function Owing to the discreteness of memory 9i and the implementation of rounding operations, the approximation within rounding accuracy all achieves zero error after rounding, while can not get correct rounding beyond this accuracy. In contrast, the error EPFN is caused by using FFN to approximate the readout function f. the same as EYrN in Theorem 3.1.
The proof of Theorem 4.1 can be found in Appendix C.I. 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 ʃ and memory functions Jt. 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 gs, whereas the latter pertains to extracting the token (m,) 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 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 E (1,1)
(10) such that:
(A) For any 0, there exists 1-layer Attn Attn DP such that H At-n
DP Se
(B) For any 1-layer DP-free Attn Attn DPF uniform lower bound holds:
H - -tttn DPP
>
Proposition 4.2 reveal significant distinction in the expressiveness of two network types for modeling adaptive, long, but sparse memories. Specifically, 1-layer Attn with DP can effectively model this task, while 1-layer DP-free Attn provably fails. This finding underscores the essential role of DP in providing the necessary nonlinearity for Attn to model adaptive memories. The formal version of Proposition 4.2 and its proof can be found in Appendix C.2.
Proposition 4.3 (Substitute for DP (informal)). There exists substitute structure for DP, requiring only O(D) parameters (compared to ODD) in standard DP) that can effectively model H e Hodaa (10). Specifically, if we substitute DP with this structure, 1-layer Transformer can achieve the same approximation rate stated in Section 4.1.
7

---

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 Appendix C.3.
4.3 Theoretical results and insights: The general case
Theorem 4.4 (Approximation rate, general case). For any target H E HAR Myy rate E N+, and H.m m E N+, there exists an L-layer (L = K + 1 1 2 K + 13} Transformer TF E TF (.)) (12) and a constant ((n) such that: if the width satisfies if the width satis-
[S [ V> -M
[ggil(s)
.type lin, then the following approximation
fies m 2 ( max
M
1 K+
[1ogg: $ T?) type = log'
K+
rate holds:
TF I EFEN + 111 Eatth (type), where
0
C(n)
K
c0.02(n+ 11TI
EE- K - 00.01T 2n+2 )2n
type- lin
EFFN= [ vm EAtta (type)
H"
0
C(a)
Ti Ti 2.02 41 + -/.011
type= log
H"
In Theorem 4.4, we establish the approximation rate of deep Transformer for modeling K 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 the impact of the nested relationships among the memory functions layers. The nested structure within the initial memories mandates sequential processing in the first K layers one by one. If M 2 K + 1, then in the K + 1-th layer, the remaining M K non-nested memory functions tK+1, .. fM are concurrently processed. The proof of Theorem 4.4 is deferred to Appendix D.I.
the required number of layers, Attn heads, and the width of FFN
Distinct roles of the number of layers I,, 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 pyperr-arameters of Transformer: I, H, and m. Deeper Transformer are capable of handling the memories with more intricate nested relationships, requiring K + 1 layer network for nesting complexity of K. contrast, the number of heads and width needed is dictated by the individual complexity of memory functions themselves (Igg:]]s- llloollloo 9: gillg. T; for memory 9t), 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 few previous tokens in an independent way, we can treat each such dependence with a separate attention head. There 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.
Proposition 4.5 (Deep network, warm-up case). For any target E H H(.
(8), rate N4, and
H.m m N4, there exists M 1-layer Transformer TF T (M+ (12) and constant
|19:1 1 max |log 9: T
(2 max
type lin, then the type log'
C(n) such that: if the width satisfies m 2 following approximation rate holds:
H
TF S EPEN + IIf Exua (type)
o C(n)
c0.02(n-1)T) 1=1
type = lin
where EPPN- Ô [1/ /m
and Extra (type)
Ha
C(n)
K
2.0
type log
Ha
Upon comparing Proposition 4.5 with Theorem 4.1, a notable distinction becomes evident between 2-layer and M 1-layer Transformer 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
8

---

to the sum of all the memory functions' complexity (lgg |llog9:llæ T, for memory function g:). 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 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
5.1 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 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 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 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 adaptive memory structure.
Fixed, essentially M-sparse memory. Consider the following situation:
Y: f ((X p1) (t). ,X pas) (t)),
(13)
where .......... denotes the convolution of the inputs with kernel Pk:
(.M(-) E (N) serve as memory kernels, and (x (t) = Er a (s)
Target class and Transformer hypothesis class. memories is defined as:
The target class for modeling essentially sparse
HE = ( H. = (13), where P1, PM f
(14)
For the hypothesis class, we consider one-layer dot-product-free Transformer with Attn head number H and FFN width m, defined in (7).
Examples. Essentially sparse memories are prevalent real-world scenarios:
(I) Image Tasks. In CV, a fundamental objective is identifying and representing meaningful "features", such ears, nose, etc. These features can often be modeled using convolution kernels, leading to task in the form = (X + Peye, X Prose, X Pear). This is an extension of the task we discussed above, in which the kernel functions {p,} } 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 vi(-) be a wavelet function and define (t,((t) = ((=hh// / Then we have f (X * Waydiss X * &aa where (a1, by). (aM, bas) might be data-dependent.
(III) Mathematical calculation. Consider algebraic operations where memory exhibits sparsity under specific linear transformations. For example, Yt = 10z; + xt-4/ w.2+-10-s)
Ete = UgZtt-100 100- can be represented in our framework as y = f (X ",, X p4), where each P. represents specific linear transformation.
5.2 Theoretical results and insights
Theorem 5.1 (Approximation rates).
(A) Consider EEss (14) with exponentially decayed memory kernels, i.e., there exists 3 > 0 such that

---

Pi(t). ,Pa = (.). Then for any target H E Hess, rate n E [[99]]]] and H. m N+, there exists 1-layer DP-free Transformer TF E &FF (m. (7) and a constant C(n) such that Jim
H TF - EPEN + IIlflllpp Exttai
(B) Consider Eos (14) with potynomially decayed memory kernels, i.e., there exists B such that Pi Pı(t)..... ,PM (PM(t) (t) = Ot--8). Then for any target H E H. rate n. E [[0.99.]] - 1}. and
H. m E N+, there exists 1-layer DP-free Transformer TF E TFF log (7) and constant (()) (1,
such that
H - TF S EPEN + Il EAttn;
where EPPN
Ô
[iflle mm
EAttn
O
C(n)M=+1 H
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 differ- ence between Theorem 5.1 and Theorem 3.1 lies the memory kernels they address. In Theorem 5.1, the Attn layer should approximate general memory kernels (-(.). instead of approximating indicator kernels I 7:} in Theorem 3.1. The proof of Theorem 5.1 can found in Appendix
Overcoming the Curse of Memory (CoM). For recurrent neural networks (RNN), it was discov- ered (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".. 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 polynomial number of neurons for effective approximation. This finding theoretically elucidates the superior performance of T5's RPE and KERPLE((og) in length generalization task in practice (Section G.I).
6 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- pre-traing vre-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 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 Transformer. However, we still have a long way to go for 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 al., 2022) during training, akin to the phenomenon of learning with increasing complexity 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.
Acknowledgments
This work is supported in part by the National Key Basic Research Program of China (No. 2015CB856000) We thank Prof. Qianxiao Li, Prof. Lei Wu, Dr. Zhong Li, and Dr. Hongkang Yang for helpful discussions and anonymous reviewers for their valuable suggestions.
10

---

References
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference Learning Theory, pages 2552-2623, PMLR, 2023a. 10
Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. Generalization on the unseen, logic reasoning and degree curriculum. International Conference on Machine Learning. 2023b. 17
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algo- rithm in-context learning? investigations with linear models. arXiv preprint arXiv:2211.15661 2022. 17
Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 1, context-free grammar. arXiv preprint arXiv:2305.13672 2023. 2, 17
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546-38555 2022. 2, 17
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, ((1):622-681, 2017. 4, 64
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. arXiv preprint arXiv:2306.044 04637, 2023. 17
Andrew Barron. Neural net approximation. In Proc. 7th Yale Workshop on Adaptive and Learning Systems, volume I, pages 69-72, 1992. 4, 64
Andrew R. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):930-944 1993. 4, 64
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine
Learning, 14(1):115-133, 1994. 4, 64
Richard Bellman. Dynamic programming. Science, 153(3731):34 37, 1966. 4, 64
Iz Beltagy, Matthew Peters, and Arman Cohan. Longformer: The long-document transformer.
arXiv preprint Xiv:2000400555555 2020. 17
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020. 17
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse boolean functions. arXiv preprint arXiv:2211.12311 2022.
Enric Boix-Adsera, Etai Littwin, Emmanuel Abbe, Samy Bengio, and Joshua Susskind. Transformers learn through gradual rank increase. arXiv preprint vrXiiv2306.07044 2023. 10
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020. 17
Emmanuel J Candès and Michael Wakin. An introduction to compressive sampling. IEEE signal
processing magazine, 25(2):21-30. 2008. 17
Ta-Chung Chi, Ting-Han Fan, Peter Ramadge, and Alexander Rudnicky. Kerple: Kerneiized relative positional embedding for length extrapolation. Advances in Neural Information Processing Systems, 35:8386-8399 2022. 3, 17
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009.14744 2020. 2, 17

---

Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023. 17
Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, 2021. 2, 17
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. International Conference on Learning Representations, 2019. 16
David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289-1306 2006. 17
Weinan E, Chao Ma, and Lei Wu. A priori estimates of the population risk for two-layer neural networks. Communications in Mathematical Sciences, 1765):1407-1425, 2419, 4, 64
Weinan E, Chao Ma, and Lei Wu. The barron space and the flow-induced function spaces for neural network models. Constructive Approximation, pages 1-38, 2021. 4, 64
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, pages 5793-5831. PMLR, 2022. 5, 16
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuits Threud, 2021. https:/traansfomee--iiriuus wttp:///eeeeeriiiiiiusup///////e wtwppp///222///aaoooo///ioee html.
Guhao Feng. Yuntian Gu, Bohang Zhang, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. arXiv preprint 230.. 2023. 17
W Nelson Francis and Henry Kucera. Brown corpus manual. Letlers to the Editor, 5(2)77 1979. 17
Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-360 -05598 2022. 17
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. International Conference on Machine Learning, 2023. 16
Aaron Gokaslan and Vanya Cohen. Openwebtext corpus. http://Skylion0007 wtw.::ionnnooiiigg...b.o. wit.hg.tttbbbi.. io/ OpenWebTextCCrpus, 2019, 66
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020. 17
Jeff Hawkins. A thousand brains: A new theory of intelligence. Basic Books, 2021. 6
Dunham Jackson. The theory of approximation, volume 11. American Mathematical Soc., 1930. 65
Haotian Jiang and Qianxiao Li. Approximation theory of transformer networks for sequence modeling. arXiv preprint arXiv:2305. I 18475, 2023. 17
Dhiraj Kalamkar, Dheevatsa Mudigere, Naveen Mellempudi, Dipankar Das, Kunal Banerjee, Sasikanth Avancha, Dharma Teja Vooturi, Nataraj Jammalamadaka, Jianyu Huang, Hector Yuen, et al. A study of 6 for deep learning training. arXiv preprint arXiv: 2019. 6, 23
12

---

Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in neural information processing systems, 32, 2019. 10
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 2023. 3, 17
Junghwan Kim, Michelle Kim, and Barzan Mozafari. Provable memorization capacity of transformers.
In The Eleventh International Conference on Learning Representations, 2022. 6
Nikita Kitaev, łukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv
preprint arXiv:2001 04455,, 2020. 2, 17
Zhong Li, Jiequn Han, Qianxiao Li, and Weinan E. On the curse of memory in recurrent neural
networks: Approximation and optimization analysis. International Conference Learning Representations, 2021. 10
Zhong Li, Jicqun Han, Weinan E, and Qianxiao Li. Approximation and optimization theory for linear continuous-time recurrent neural networks. Journal of Machine Learning Research, 23(42):1-85 2022. 10
Zonglin Li, Chong You, Srinadh Bhojanapalli, Daliang Li, Ankit Singh Rawat, Sashank Reddi, Ke Ye, Felix Chern, Felix Yu, Ruiqi Guo, et al. The lazy neuron phenomenon: On emergence of activation sparsity in transformers. In Conference on Parsimony and Learning (Recent Spotlight Track), 2023. 17
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang, Transformers learn shortcuts to automata. arXiv preprint 0rXIv:2210.10749, 2022. 17
Chao Ma and Lexing Ying. Why self-attention is natural for ssquence-to-sequene problems? a perspective from symmetries. arXiv preprint arXiv:2210.06744 2022. 17
Chao Ma, Stephan Wojtowytsch, Lei Wu, and Weinan E. Towards mathematical understanding of neural network-basse based machine learning: what we know and what we don't. arXiv preprint 200:20009.07133. 2020. 4, 64, 65
Arvind Mahankali, Tatsunori B Hashimoto, and Tengyu Ma. One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. arXiv preprint arXiv:2307.03576, 2023. 17
William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923 2023a. 17
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-preci transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023b. 17
William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843-856, 2022.
17
Yves Meyer. Wavelets and Operators: Volume 1. Cambridge university press, 1992. 17
Tetsuya Nasukawa and Jeonghee Yi. Sentiment analysis: Capturing favorability using natural language processing. In Proceedings of the 2nd international conference on Knowledge capture,
pages 70-77, 2003. 17
Joakim Nivre and Mario Scholz. Deterministic dependency parsing of english text. In COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics, pages 64-70. 2004. 17
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et In-context learning and induction heads. arXiv preprint ar X11:2200.11999.... 2022. 10, 17
13

---

Santiago Ontanón, Joshua Ainslie, Vaclav Cvicek, and Zachary Fisher. Making transformers solve compositional tasks. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics, 2022. 2, 17
OpenAl. Gpt-4 technical report. https://ccn..peeeeeee pttp 2023, 17
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing complete. The Journal of Machine Learning Research,
3499, 2021. 16
Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. International Conference on Learning Representations, 2022. 1, 17
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21 21(1):5485-555 2020. 1, 17, 64
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, pages 5301-5310. PMLR, 2019. 10
Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-477 1948. 17
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics, 2018. 1, 17
Lingfeng Shen, Aayush Mishra, and Daniel Khashabi. Do pretrained transformers really learn in-context by gradient descent? arXiv preprint arXiv:2310.085400 2023. 17
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568: 127063, 2024. 17
Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. Synthesizer: Re- thinking self-attention for transformer models. In International Conference on Machine Learning. pages 10183-10192. PMLR, 2021. 2, 17
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 2023. 17
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017. 1, 3, 17, 66
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pages 35151-35177 35174. PMLR, 2023. 17
Johannes Oswald, Eyvind Niklasson, Maximilian Schlegel, Seijin Kobayashi, Nicolas Zucchet, Nino Scherrer, Nolan Miller, Mark Sandler, Max Vladymyrov, Razvan Pascanu, et al. Uncovering mesa-optimization algorithms in transformers. arXiv preprint 230.00230000 2023. 17
Lean Wang, Lei Li, Damai Dai, Deli Chen, Hao Zhou, Fandong Meng. Jie Zhou, and Xu Sun. Label words are anchors: An information flow perspective for understanding in-context learning. Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing (EMNLP), 2023. 17
Mingze Wang and Chao Ma. Understanding multi-phase optimization dynamics and rich nonlinear behaviors of relu networks. Advances Neural Information Processing Systems, 2023. 10
Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04700 2020. 2, 17
14

---

Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: case study on approximating turing machines with transformers. Advances Neural Information Processing Systems, 35:1 35:12071-,,083, 2022a. 16
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-though prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-24825 2022b. 17
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Conference
on Machine Learning, pages 10900-10900, PMLR, 2021. 17
BigScience Workshop, Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilié, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, al. Bloom: 176b-pan parameter open access multilingual language model. arXiv preprint arXiv:2211.05100 2022. 17
Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. Communications in Compulational Physics, 2019. 10
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequuene functions? arXiv preprint /oXiv: 2019. 6, 16
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang. Yang, al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33:1 13:17787177297, 2020. 17
Zhongwang Zhang, Zhiwei Wang. Junjie Yao, Zhangchen Zhou, Xiaolong Li, Zhi-Qin John Xu, et al. Anchor function: a type of benchmark functions for studying language models. arXiv preprint arXiv22401.08339, 2024. 17
15

---

Appendix
Detailed Related Works
16
Proof of Section 3
18
B.1 Proof of Theorem 3.1
18
C Proof of Section 4.2
23
C.1 Proof of Theorem 4.1
23
C.2 Proof of Proposition 4.2
33
C.3 Proof of Proposition 4.3
35
Proof of Section 4.3
38
D.I Proof of Theorem 4.4
38
D.2 Proof of Proposition 4.5
48
E Proof of Section 5
50
E.1 Proof of Theorem 5.1
50
F Key Lemmas about Approximation
55
F11 Approximation by the sum of exponential :e..............................
55
F.2 Approximation by the sum of polynomial decay
59
Some Background and Proof Preparation
64
G.1
T5's relative positional encoding
64
G.2 Barron space theory
64
G.3 Useful approximation lemmas
65
H Experiments
66
H.1 Restatement of our theoretical insights
66
H.2 Experimental Validation
66
H.3 Practical Implications
69
A Detailed Related Works
Theoretical results of Transformer. We first review the expressive power results of Transformer. Yum et al. (2019) first proved the universal approximation property (UAP) of Transformer, highlighting crucial role of PE in breaking permutation invariance. Edelman et al. (2022) demonstrated that Transformer can approximate fixed sparse functions. Dehghani et al. (2019); Pérez et al. (2021); Wei al. (2022a) explored the Turing-completeness of infinite- prectteepriiiion and finite-precision Transformer. Giannou al. (2023) showed that looped Transformer implement practical computer programs.
16

---

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 lim- itation 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 mudient-bbssed iterations across various layers (Garg et al., 2022: Akyürek et al., 2022: von Oswald et al., 2023; Von Oswald et al., 2023; Mahankali al., 2023; Bai 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 representa- tion of input sequence order. Theoretically, Transformer without PE lacks UAP and is restricted to representing permutation-invel invariint functions. PE was first introduced in Vaswani et al. (2017). has limitations in encoding unseen positions. To overcome this difficulty, Shaw et al. (2018) introduced RPE. Subsequent studies proposed various different RPE types. Notable examples include T5's s RPE (Raffel et al., 2020), Rotary RPE (Su et al., 2024) (utilized in PaLM (Chowdhery 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 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 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 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 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 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 crucial for accurate prediction. However, these relevant information can be quite distant. For instance, the resolution of 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 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 range dependence is important for sequence modeling.
17

---

B Proof of Section 3
B.1 Proof of Theorem 3.1
In this subsection, we give the detailed proof' of fixed, long but sparse memory:
yt fzt, Ft-T,,"" Fs
where 1 S Ti TM too signify the fixed positions of the memories.
Theorem B.1 (Restatement of Theorem 3.1). For any target H E 7 (6), rate n E N+, and H, m N+, there exists L-layer Transformer TF TFDPP that
(I.H.m) (7) and constant C(n) such
H TF S EPEN + IIf Extia (type).
where EPFN
Ö
[L v/n
and
O
C(n) H
E i==1
0..1T)) )
type = lin
Eauta (type)
0
C(n) H
ΣM M
T.I.01) n+1
type log
Proof of Theorem B.I.
First, we choose the embedding dimension (M + 1)d, and select the simple embedding WE (Laxd: 0)T pxd bg 0 R.
Then for any input sequence X (æt)eez. the token after embedding satisfies:
WFE. + bE = ( TT E R..
For one-layer Dot-product-fres Transformer TF E T.D.E. type with Peypes the output token (1.H.m)
TF, of t-th input token 8, satisfies:
(1/2)
Et + (
Σ
Attn (1.b) (x
h=1
x FFN (x)) (x) (1/2))
where
+00
It exp (p( (eype
Attn (1,b) (X)
(:(lhb)
j= exp (j))
too
This proof can be summarized as the following process:
E
Step Attn layer
(1/2)
xo T
T "2ITT))
x
Step II. FFN layer
(1) æe RJ f(x,, Ce " Te-))))
Now we give the formal proof.
Step I. Extract the memory locations by (fot-producttfree) Attn layer.
We consider use Hy attention heads (from Σ H, 1-th head to Σ Hi head) extract it, and it satisfies to Ed H₂ = H.
For simplicity, denote the following projection matrices:
18

---

p(k)
(Odxk
Laxd
0) E Rdx
Isks M.
p(k) =
Ikdxkd
Odxd
0
E ERAaaD, 1 M.
Odxd
((M-R)xx(M
Now consider the extraction of k-th memory T:-Tr (1 S k S M).
Case type lin.
By Lemma F.I, for any rate n E N., there exists an constant (nn) and a function
EMP
Σ
are - Br.
E. H.tIS H.
such that B, > 0 and
0.01(n+1yy) 1)T
||[ TT) ox ()1l, Σ
[11ss Th} -xx xx (s) C(n)
H
Therefore, for these attention heads E H4 H
x HD) choose
(1.))) BB: (1.1)
Σ (xp(-3nnj)
gaxd (k+1,1))
Ohh
where g(++1,1) DDD means that: equals to Laxd for the (A + 1, 1)-th d x blocks, and Oaxd for the other d x d blocks. Then it holds that:
1 H:
+o0
Okd
Attn (1,b)
(1.( (x(1))
Bng
RRD.
Oh
Ft-s
h= b H,+1
h= Sk-1
H,+1
This implies:
Di H
S H,
+
p(A)
Attn; (1,1) (x())-
3x m
h= Ei Hi+1
h=
b=
H,+1
s=0
((k)
Σ
Attn (1.b) (x)))) = =0
1= H,+1
moreover, the following estimate holds:
A He
(())
Σ
Attn (1,b) (x
Fc-Th
h=>
H.+1
+o0
9n
c
Iz-
H,+1
s=0
19

---

Σ
+00
ane Bas -1fs Ti} 21-2
Eisl H,+1
+00
C H4
O4e Ohe-0h0 Pa. --ss= T
>= H,+1
c0.01(++1)77
10 (1) II(-
Tllll SC(n)
H
Case type log.
By Lemma F.4, for any rate N4, there exists an constant C(n) and a function
&k
poly (1) =
Σ
agt
Etel
H.+IShE H;
such that Bn > 1 and
+00
TH (00(++11)
H
T = Tk} oh
pooly
Σ
ITs T oaoly (s) s C(n)
Therefore, for these attention heads
(
k-1 Ei=1
Hi + 1 < h
i=1
HD,,
choose
to0
p(a = Brs W = ah
Σ jm
8(k+1.11,
where g E R DxD means that: it equals to Laxd for the (k + 1, 1,1h d x d blocks, and Oaxd for the other blocks.
Then it holds that:
+00
p(k)
Attn, (1,b) (x)) =
Qh
Tt-8
h= A H.+1
h= -=
H,+1
I H.
[(k)
Attn: (1,1) (x O,
hm S
H.+1
moreover, the following estimate holds:
Σ H: Σ
p(t)
Attn, (1.)) (tt (x())
h E H,+1
Σ H:
Bn E1-8 2z-Tz
O'h
N=> He+1
s=1
H:
04 8n Ifss = Tx
Sk-1 H.+1
20

---

+00
Σ
ans Bh - 11s Tk}
==1
h= Σル H,+1
(0 (c(m) T.. T1101(n=1)
poly (+)
Ti (la...)) 5o
0k
H
Then we combine the results for all & [M] for these two cases. By choose Wo = Ip. we have:
(1/2)
Lt-t1
MM
C1
Od
0g
(L.)) (L (X)
0t-
Attn; (L.))
Attn;
h=1
0
20 tM
2 1M
Σ
H
Okd xc-Te
Attn, (1,60 (X)
Et=l H++1
0a
H₁
Okd
Attn: (1.h) ( (X)
-
0g
Hi+1
M
Ei Hi
pik) Attn, (1.) (X)
(X) - Iz-Tz
Ei=l H++1
C(n) EM
0.01
type lin
H
SEAuc (tyne)
C(
M
T.l
HE
type
log
Consequently, one detail is to assign the head number (H₂) ) M such that the errrr' sum Eatta (type) is as small as possible. Our way is solving the minimization problem:
min HM
E EAttn(type)
s.t. Σ H4
H,
1=
which suggests that we should choose the head number:
0.017
Hg
H, k [M], type lin:
2j=1 j= 00.11T
T1.01
H, k [M],
type log.
ΣS T 01
Thus, obtain the bound in Step I:
M
a+1
C(n)
Σ
0.01T:
type lin
Exttn (oanntype) <
n+1
C(n)
Σ
1.01
type = log
3
k=1
21

---

Furthermore, by choosing Eattn(tpp)) - 1, it holds that
St
(1/2)
Ft-ti
Tt-t1
Estm(type) +15
3tt fx
Step II. Approximate the readout function by FFN layer.
In this step, aim to approximate the function using two-layer network. By Lemma G.6, there exists a two layer neural network with m neurons defined on R
FFN (g)
Σ km
such that
Iflle
EENN = FFN())
((-22)2))))
mm
The final bound.
For any and X E X. it holds that
H,(X) - 2t
(cx,, 02-011' ... -. - FFN(()) (x) (2.1122)
(2 Ti-110 ... x1--11))= 1 - 22
(1/2)) + (z)1/2) FFNO)) 2
(2(/21)
(I D1-1,, x1-(w)) - f ( (1/2))
+ (x(1122) - FFNN
2 (1/2)
|| /| (oT a2-11 (1- (1/2)
+ +15-- | (.-2(_))))))))))))))))))))))))))
$ | | Esum(type) + EYFN,
where
||
EFEN = δ
Vm
0
C(n)
Σ 1= 0.017% n+1
M
type lin
Stun(type)
C(n)
M -=
T
01
n+1
type log
H
Due to the arbitrariness of and X, the proof is completed.
22

---

C Proof of Section 4.2
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:
yt = (at,, Be-t11"" Be-
where the adaptive memory satisfies to:
f = (xx),
[M].
Moreover, (+(-)) generate positive integers for the input tokens, and there exist maximum values Tk such that 1 S 9x (x,) I T3 holds for any and k E [M].
To tackle the discrete values of the time and the memory values gl (ax)). modified version of standard FFN, termed "FFN with precision", us cibsudered. This approach ensures that the output of FFN undergoes 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 the following FFN with precision:
(FN == [FFN(*)),
type = lin;
(15)
FFN (x) == log (exp (FFN(
type = log,
where []] signifies rounding the nearest integer, i.c., [x] arg min I x (x R).
It is important to note that the rounding obtained by using the operator log[exp(2]], used in (15), is quite fine, which much finer than the vanilla rounding obtained by [æ]. To elaborate, the following proposition is presented:
Proposition C.1. For any 2 2 1, the following holds:
1
(i) [og[cxp(=)] 2|
2 minffr |e (i) [2] 215 2
C.1 Proof of Theorem 4.1
Theorem C.2 (Restatement of Theorem 4.1). For any target H E ArAdap (8), rate n E N4, and bype
H, m E N., there exists a two-layer Transformer TF E F.F. FF... (12) and constant ((n) such that: if the width satisfies
(2.H.m)
Σ M 11 11:3)
type = lin
m
M Di= |log gi 11.s T?).
type log
then the following approximation rate holds:
H TFIl S EFFN + II Extra (type),
[L Vm
where EYPN
and
0
C(n)
E
M c0.01T:) )
type lin
H"
Exu (type)
C(n)
EM M
T:1.01 mt1)
type log
H"
Proof of Theorem C.2. First, we choose the embedding dimension D (M 1)(d 1), and select simple embedding WE (Iaxa; 0) E Dxd bg 0 E ___
Then for any input sequence (xx)eez. the token after embedding satisfies:
00) W g., + bg = (x., 0 )T ERP.
23

---

To tackle the discrete values of Im 9m (Zt), we utilize FFN, FFN with precision (15). It ensures that the output of FFN undergoes a simple rounding operation.
Thus, for two-layer normalization-Fie Transformer TF' E TF zt of f-th imput token satisfies:
NFyeype with Otyper the output token (2.H.m)
1/2)
2t +
(0)
(1) W
Attn (1,b)
(x
(1) (1/2)
(1/2)
2 Zt
FFN
(x)
(3/2)
Zt + W
(1)
Attn (2.b) (x
(2) FFN 2) (a. (3/2))
at
where
Attn (1,h) (X) (X)
w((
(wwlin)
22, W (1,)) 20-s) + D
@espe (s)
Tt-s exp
s=0
This proof can be summarized as the following process:
Case type lin.
(0)
Zi
Step I. 1-st Attn +
(1/2)
(0)
xz
Zt
Step
II. 1-st FFN +
(x) T. o ,x.(),,, ... 19)(())))
Step
III. 2-st Attn
+
zt
(3/2)
= (x, T T
2 (x:))
2 ( (2.) 91 (0( 1)
Step 2-st FFN +
2 R f(x D1 (m.))((m.))
Case type log.
(0)
x
Step I. 1-st Attn 1
(1/2)
(0)
at
xi
Step
II. 1-st FFN $
(x. T 0
loog 91 (ar,,. Io gM (ax)), log 2)
Step
III. 2-st Attn
(3/2)
2 (m.. T TT.TT (o.)) TT. (e--aa(a.)) log
log g1 (xx), log gM (xx),, log 2)
Step IV. 2-st FFN
s f(a,, (a))) (t))))
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 0. Then x (1/2) xx
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 (z) 0 99 (z.),... Ia (xx). 1) exactly.
First, we consider to approximate the r-th memory function Ir (x) by standard FFN. For any E [M], by Lemma G.6, there exists two-layer neural network with my neurons
(a)
4k (1,r)
(b (1.r) T + Ck
(1.r)
k=1
defined on I such that
1
9. ((.r))
5ō
1:00 ({-,11p)
m,
Therefore, if we choose
l1 1ss mm,
< 2
the following holds:
(r(())) - (1,r) (2xz)
12NN
S |0r- -fth
F2NN f(.)))
1
(x1111))))
2
Noticing (ax,) E N+, we have ((1,)) (ax)) gr (x:e), which implies:
2NNN (1.r) (xt) = ((i.t) (ari) = (x)))
Consequently, in order to construct the form (0 g1 (xx)), ... 1) E R², we need
to arrange the parameters dj. by (1.r). and c
(1,r)
(1.r) (k: E [m,].r r E [M]) appropriately.
Denote ((1.r) (b T )T E RDD for k E [m=],r E [M]. Consider the following
two-layer neural network with M
my neurons defined on R.D:
FFN (x) Σ
Σ
eD-M+r-10 ( (1,r) Tx + ((rr))
(1,r)
E my M, my
+ep 1 1-0(0+1)
is easy verify that for any x it holds that
(1/2)
FFN(1) ( (1/2)) (F [ (0)
Σ
ep- CD-M+r-14 (1.r) (b(.r) T x
+ o (111)) + + 1..00++
1+ Ei- mysks my
Σ
en-M (1ir) (1()))) x + cx (1)) + ten 1..
1 SKS
eD CD-M+r-1f 2NN (I1) teD
2NN =( S (2))
S (Z 1)T E R
2NN
Moreover, it satisfies that
FFN (a) (x (1/2))
(FN (a (2) (122))
25

---

=(0 ((.))) (z1) ,.... (I.M)) (ax) 11)T
=(0] 91 (.:)), "1 ga (xt). 1)_ E RR.
Thus, we have achieved our goal in this step:
z; 11)
= xi (1/2)
+ FFN (xx (a.(1/2) = (a) " TT,TT 91 (21). ... IMM (x:),,.)
Case type = log. Our main idea is that using the first FFN layer to express (x) 0 log (ot)), .. log gM (o)), 2) exactly.
First, we consider to approximate the r-th memory function log g- (x) by standard FFN. For any [M], by Lemma G.6, there exists two-layer neural network with m, neurons
mer
(x) = Σ ak a (b())) Tx + ck (r
(1r))
defined on IRd such that
|log gr ll /mr
logg. 12
(1.1))))))))
Therefore, if we choose
|loo [llogorlls gr l1s mr
4T,
the following holds:
log gr (xx)) 12NN (2x)) S --- 12NN
1
(-11))
4T,""
which ensures
exp 2NN ((.,))( (ar+) - (r(()))) = -s-(at))= =|exp (12N)) exp (log (gr (2x:)))
max { ((IT)) (2re, (er (2t1)) ((NN)(2 - log (xx)))
$ exp
(1ogg.(zz)) + 4 4T,
1
Sexp
1
1
</2/1 T, 4T, <
2
Noticing (x,) E N4, we have [exp (1PAN gr (2:e), which implies:
(1.))
(xx)
log
exp
(2NN)) log (xx))
Consequently, in order to construct the form (0 g1 (wt), ... log ga: log 2)T, we need to arrange the parameters dj b
(L.r). (1.r)
(1,r) and CR (k E [m,], r E [M]) appropriately,
Denote T( [(.rr)
(b (L.)
TTTT E RDP for E [mr],r E [M]. Consider the following
two-layer neural network with 1 + M
m, neurons defined on R:D:
FFN
( = Σ
Σ
CD-M+r-10 (1.r) (B(l.) T + c (lir))
14 m,sks E5 m,
+ 1 1-0(0- + log 2).
26

---

It is easy verify that for any i.
(1/2)) it holds that
FFN
D (1/2))
FFN )
M
Σ
eD M (1,7) (b% xt + % ) + ep - 1. 100 + log
j my mysks j my
Σ
eD-M+r-14E (1.)) (B0.)) T Et + oz ) + tDD 1. 1.0000000000000 + log 2)
2320 S my
C 2NN (x:) + ep log
=(0 2NN (xt),
- (Zx), E RR.
2NN
Moreover, it satisfies that
FFN
(xe (2r(1/2)) log exp (a (2(1/2)))
= log exp (ax)) ... log exp 12NN (x:))) 2, )T
=(0 log (zt). log gMs (ox), 2)
Thus, we have achieved our goal in this step:
11 2 (1/2)
FFN (1)
(a) (122)))) (I] _ log 91 (xx), ... llg 9M (2t), log 2)
As established in the proof above, the width m must satisfy:
② Σ - |1 Il2))
type lin
m
52 E
|loo 9r 11 1,2)
type log
Step I11. Extract the adaptive memories by the second Attn layer.
We consider to use Hg attention heads (from Σ H, + 1-th head to Σ H,-th head) to extract
it, and it satisfies to Σm= H₁ H.
M
For simplicity, we denote the following projection matrices in DxD:
P(N) = (Oaxkd
Laxd
0) E RdxD
1
p(() :
Jodx 0
Oaxd
O LID-CADDAXD-
E (D-d))
1 1 <
Oaxd
(M) (I(M+I)aX(MHI) E (M++))d
Now consider the extraction of k-tth adaptive memory : - llkk M)
Case type = lin.
By Lemma F.2, for any rate E N4. there exists constant C(n) and function
o (tt(t;
Σ
OA expp(pBBx(t -B)
Et!
H.+ISh+
Σ
a4 exp Bn Byi)
Hi+IShEE
H
27

---

such that Br > 0 and
Ciz)eboluutim
|||| = B} 0x (; (:))l
sup SBB
H
Moreover, Noticing that S 9h (x,, S Tj. holds for any X (It)EE E X, the following holds:
sup
||I| gxx()))) Ox (: (x:; (19)
x
|| = B} 2x exp (;Bllee S C
sup ISBST
H
Therefore, for these attention heads (E H4 + +1s Ei=1 H,), we can choose:
212.b) 3h: W IXDD W - (k-1,1) E ERDx
w (2h V B (D- M+8-11) DxD w Bh E R DxD
where (p1.22) means that: it equals to Fxr for the (2,,P))-h x r blocks, and 0,xr for the other r blocks.
Then it is easy verify:
(2,b) ot w (2,4) (22 ( + +p (2,)) (un(s) -3h -3x(s gu (zxi). W
which implies:
Sk H;
H4
+
Okd x(-s
Attn, (2,8)
(x
Bn (a(s-9((0)) (w,))
E R
Oh
Etat He+1
h= Ei 11+1
8=0
Then it holds that:
E1 Hi
5 H;
p(k)
Attn; (2.1) (x(1))
(x Bt-5:
Oh
AE Het1
h= >
H,+1
D H:
p(k)
Σ
Attn (2.1) X (0)= = 0.
1=
Met1
moreover, the following estimate holds:
Σ Hi
p()) Attn (2,N) (X) (X)) 2z (m()))
|=>>
H,+1
H:
92 x1 (m))
H,+1
#=0
28

---

Σ H:
ahe (x()- - -1(s gk (2x)) 2(-s
Eis H,+1
toc
Σ レim Hi
are ahe-Du(e-ou(ee)) I(s = gh (2+1)
1= -= H,+1
(: (2:x) -II (x) S C(n)e2a(1-177
1 1
H
Case type log.
By Lemma F.5, for any rate n E N4, there exists constant C(n) and function
poly 0k
Σ
(h(t/B) 8r
Etsl
Hittsh
H:
Σ
an exp Bn B 3n log
M 1+tsshE Ha
such that Br > 1 and
C(n)r
[[[- = B} -0h -booy (:
sup LBBTT
(144)
H
Moreover, Noticing that 1 S gh (xxx)) S To holds for any X = (xt)eez E X, the following holds:
sup x
[1f- gx (xx))
BRoly (=:x(Z))) (e,com)
C(n)T &
||||- [B] B} -hooly (:: B)
< sup 18BST
(2
H
Therefore, for these attention heads (E H. + < h Σ Hz), we choose:
(22 BBh,
w IDDD,
W az on gldxd)
RDD
(k-1,1)
vBn ((xx))
w V3 D- D-M
RRD w
log (D,1) E RR DxD
where (m.)))) means that: it equals to I,r for the (pi,P2 -h x blocks, and 0,x for the other blocks.
Then it is easy to verify:
W (2 (1)
oi W a/-s) ) + +p (2M (1n()))))) -Balog (s/gn(ae))
which implies:
D Hi
Σ H.
+00
Oka
Attn. (2,h) (x
Σ
Ctp
(z1))(z)))-
-hh
Fi-s
E RR
1= H,+1
N=Σ!= H.+1
==0
29

---

Then it holds that:
Eis
Σ H:
too
p(k)
Attn; (2.)) (x(1)) =
Ohh Σ (z)))(z)))
-b.
9b 21-80
h= Ek- H.+1
Ik-1
Hct1
==
Σ H.
k)
Attn (2.b) (X (x))))
h= 8,+1
moreover, the following estimate holds:
E1 H
p(k) Attni (2 (x
4= E H,+1
E H,
(s/gx(0))) Bn P::0== 2e-ga
ah
H,+1
8=0
Eisl Hi
an(s/gn(z:)) - Ifs (x<():)))
H.+1
+0c
Dim
(n(s//n(22;))- 115 = gh (x+)}
s=0
h= Eist
H,+1
C(n)T
oooly (z:)(())) 11- =g((z)))
(1(14)
H
Then combine the estimate for all k [M] for these two cases. It holds that
2t P (or))
(e (3/2)
34 and (20.)
2
St Iz- (mr)
Zt OMd
Q
(M) Attn (2,4)
(x(1)
h=1
2 gxe (mte)
1.
Oa Ft- 91 (mL)
M
(M) Attn, (2 (2.6) (X)
Attn
F and (mn))
2
H:
Okd
(M) Attn (2.h) (X)
(X)
- gu (wx))
0
Hi+1
H;
Rud
((M) Attn (2,b) (2,))())
(M)
(X)
Ø3 gu (wx)
H;+1
30

---

M
H.
pk Attn, (2.h)) (x)
(X)
2t- (mt))))
Eis
H,+1
type lin
EEttia (type)
type log
Similar to the proof of Theorem B.1, we choose the head number:
0.017
Hτ
k E [M], type lin; H,
Σ j= c0.01Ty
Th.01
H₂
H,
le [M], type log.
E T3.01
Thus, we obtain the final bound in Step III:
M
a+1
C(n) 11
Σ
e
0.01T,
type
lin
@Soft Atin
(type) v
a+1
C(n)
Σ
11.01
type log
1"
Furthermore, by choosing Eseta (type) < 1, it holds that
Tt
(3/2) | 2x (3/22)
Q (M) (3/2)
(m))
F Zz-
S
2
+
nas (xx))
Fe (00.)
EE (tyne) +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 two-layer neural network with m neurons
m
x
Σ
(2) ak
b
2
C
(2)
defined on (M)+ such that
|Ifl
2NN
(=(1-22(0)))))))
Vm
Denote ((2) = (b(2)
TTTT E R for k E [m]. And we consider the following two-layer neural
network with neurons defined on D
m
FFN (x) :=
4
σ
b
x + c
It is casy to verify:
31

---

FFN (e.0/2)
= 12N
(Q/N)
Moreover,
[Ifll m
e(2)
5 FFN
5
L L (222222))))
The final bound.
For any t and |X|| E X, it holds that
H.(X) - m! (20 = (at, (o)))( ... -F-- FFN (3/2)
f (2i, F2-11 xe-(xs) - (20 2NN (Q (Q(M) (3(222))
f (o (m)())))) ... .. (1 - (Q (M) 2z (3/2)
+ [ (/ (Q())) 20 (3/2)) - NN Q (M)) 20, (3/2)
f Te-11 x(- - f (q (1)
x1 (3/2) ){
+ f (Q (x( 211011)
< |f / (x) "T. x (Tmm) T Q(1) (3/2)
+ f 12NN
[=(1-222((1-100))
S Ill Extia + EFFN,
where
EEEN ② B
vm
C(n) H
Ek c0.11T n+1 )utt))
type lin
Etttn (type)
Σ T T1 n+1 (utt)
C(n)
type log
Moreover, recalling our proof in Step II, we further need the hard condition:
② EM
type = lin
m >
á llo Or T?
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 achieved through a nice interaction between the temporal space (provided by RPE) and the token space (provided by DP). Specifically, the memory functions go (x)))) (in token space) are mapped into the temporal space 8, resulting in the form of r.-9.( for DP Attn with lin-RPE (og(s/g((x.) for DP Attn with log- RPE.
32

---

C.2 Proof of Proposition 4.2
For Proposition 16, we denote the following one-layer Attn hypothesis class:
ATTN 2ype (1,H)
(Atn TF is a 1-layer, H-head (normalization-free)) Attn with type- RPE]:
ATTA ATT.ADPF..7E type (1.H)
TF Attn is a 1-layer, H H-head DP-free Attn with type-RPE).
(16)
Proposition C.4 (The formal version of Proposition 4.2), Consider 1-kayer Alin. Then, there exists target H (1,)) (10) such that:
(A) (Attn with DP) For any > O, there exists L-layer Attn Attn DP
E EATT (type (1,11
such that
Attn DP
(B) (Attn without DP) For any 1-layer DP-free Atm Attn DPF bound holds:
E EATT
=ype uniform lower
(1.H)
Attn AtAt
H
DPF
Proof of Proposition C.4. Consider the following target function H1,1 Let the input sequence X X (-1,0,1), and we consider the target
V1 = H = Tt g(xs)
where the adaptive memory is
0, I
g(x) =
1,
2,
Part (A). The Efficiency Attn with DP.
First, choose the embedding dimension D = 2, and select simple embedding We bg
(1,0) e R2x1, Then for any input sequence X = (2t)tez, the token after embedding satisfies:
(0) It
WET,
gr, + bg (zx,
We consider one-layer normalization-fret Self-attention with deeps which has the form:
Attn. ((x)
Wo
w
(L.))
Σ 2
exp ( (w(()))
w K
a. + +p(1n))))
h=1
==0
By Lemma F.2 (for
1), there exists constant C > 0 and function
H
exp (1; B)
Σ
an exp - B))
Σ an exp (3,B 3rtt
such that B > 0 and
Ce 0.01-222
sup BSB
[T[ B3
(x B) B)lle, 5
0
H
33

---

Moreover, Noticing that 0 - ((x)) v 2 holds for any X = (xa)eEz E X, the following holds:
sup x
||[ = g(xx)) - - &0 (1g(2)))eMM))
1
sup ||| = B} xx 2 5o 05852
H
Therefore, for attention heads (1 < h S H), we can choose:
((),A) Bi: Wo (1, E 2 w( =0,0 (1x))) ER
W (1.A)
= (1,, Rx21, w((h) Vv,(0,1) E T221
where 8 ((xx))
(2).P2) means that: equals rxr for the (21,2))-th r x r blocks, and 0rxr for the other r x r blocks.
Then it is easy to verify:
(1A) (0) Q of W
(( (1,b)
K ( + ((2h) =pplin)
-plli)) (s (s- (I: + 11) = -p(l.n) (0-g(x)))
Thus, the following estimate holds:
Attn
DP (X)
xz -z-1(z0)l2
H
+00
(a(x-g(as)))
xi-0 It- g((e))
==0
ahe (n(x0g(a))) 1{s =((x)}
x4-6
2
+00
are (x-9)()))) - Ifs = g(xe)}
( -(==g(x)))) 5o
H
Due to the arbitrariness of f and X, the proof completed: for any e > O, we only need to use H Q(1/c) heads to approximate it.
Part (B). The Hardness Result of Attn without DP.
We consider one-layer Dot-product-fre Self-attention with dexp or Ólog- For any input X, the corresponding output can be written
+00
Attn DPF
(X)
Σ
pa (W bR).
For simplicity, denote:
z = Wg + bg.
then we have the following estimate:
H Attn DPF ||| = sup sup |H| (I)PP(()== (X) Attn;(X) 2 sup [o(()) - Attn DPF (x)
34

---

t00
Px. (0)
sup
T- g(
(u a 2 1:
fixing _-. 0 for
2
Σ
(0)
2
sup
I -
Part -8
(a- (1_
6=0
mo
-1 (pol-WE+ + + + (0) + p2xl1?
max
max
(x-2.2
② (00) (pobe + p1 + p2al
max
(#-2.2-1)
② (11) (po(Wo + +bb) + piz + p2 122
max
(x-2.7-1)
x- (pODE + p1 + p22 -
max max
(m-2
- 1 (po[-W + bg) + pM (0) + p2x (0)
x- 2 (po + +
+ - (0) + p2 (0)
max(a,b,0) 2((bb++)))
(
x (pube + p1- + p2a
max
(2-2.2-1)
-1 (po(- WE + bE) + p (0) + 02:t -
+ r-2 (po(WE + +bb) + p1 (0) - 22 (0)
|0|+10/2/+b/
| (oob + p1 (0) + p2u
max
(r 2 1)
x- (pode p1 (1) + p2 (0)
2
1
max
x-
(pobe + p1 + p2r!1)
(x (x=
1
1
Pube + p1 (0) /ي (12
+
12(+0/2aa-b]
1
x-2
2
max (x-2
1- 1
+
2
2
3
C,3 Proof of Proposition 4.3
In this subsection, we propose structurally simpler yet effective alternative to traditional Dot-product in Self-attention. This alternative is proposed based interaction between the temporal-space and the token-space, Specifically, we propose a more direct structure to achieve the interaction (type (s) étype (w" æz)..
insights into the role of Attn in facilitating
Definition C.5 (TMX Transformer). We define the TMX ("t minus x") Transformer as follows. In standard Transformer (2), we modify the term
w (-.. Zt W (1,b) 22-0) + +p (MMM @uppe (s)
(LA)
in Multi-head Dot-product Self-attention to the new formulation:
(0.h) (uupp (8) - Deype (w) T =x:))
35

---

where the parameters w((hh) E RDx1
Notice that in TMX Transformer, the revised requires only O(D) parameters, much less than ((D)) in standard Dot-product Transformer.
Consequently, define the following TMX Transformer hypothesis class.
TF type = TF :TF is a 1-layer, H-head, m-width (L.H.))
(17)
(normalization-free) TMX Transformer with type-RPE).
Proposition C.6 (The formal version of Proposition 4.3), Under the same conditions in Theorem 4.1, there exists a two-layer TMX Transformer TF E FFF.X. (17) such that it can achieve the same approximation rate as standard Transformer presented in Theorem 4.1.
Proof of Proposition C.6.
is worth noting that TMX Transformer only replaces (wilk)) in standard Transformer with pll.h) (pup (s) Otype (wilhh) T xx)) Therefore, the proof is highly similar that of Theorem C.2. We only need to prove that TMX Attn can also achieve Step and Step III in the proof of Theorem C.2.
It, K - + p plt.A) (cype
Step I. Step is trivial due the same use of the residual block.
Step III. Extract the adaptive memories by the second Attn layer.
We still consider to use H2 attention heads (from Σ H4 + 1-th head to Σ Hi,th head) to extract it, and it satisfies to Σx= H₃ H.
Now we consider the extraction of k-th adaptive memory It (m,)) (1 k S M).
Case type lin.
For the proof of standard Transformer (the proof Theorem C.2), for the attention heads
(2/+1 H. 11+1- < Σ Hi),, we can construct specific ((2.h), (2.h)) w (2,4) (2.
such that
W (2
w (2,M) x.
+ +2 (iul))) = -B gx (aze))
In this proof, only need prove that also construct specifie whl)), w w (2,N) such that
()2,0) (Oni (s) onnn (2)( Ta.")) = -33 (3 gr (x((2)))
Recalling the proof of Theorem C.2,
(x O .g (x,), ". (x,) E RRD.
Therefore, we can choose
(2.6) = 3h. w (2h) = 6
(1x1)
(DD-++k-11) R.,
w (2.4) = ano(dxe) g(dxe] (k+1,)) e RXD.
where (xxx) (P1.P2) means that: it equals to I for the (P1,P2) P2)-th r x blocks, and 0,xr for the other r x blocks.
The the following holds:
(22,)) (1))(()) Hinn (2)) T (1)
36

---

p(2.h) (s w(2. Ta!")) = -Br (x-(
Case type log.
For the proof of standard Transformer (the proof of Theorem C.2), for the attention heads
(E/=) H,+1 & $ Σi= H,), we can construct specific p(2.), w w(2.b) (2.
K
such that
W zt Wh ( 2 ) +
(1)
(2
(1og) -Balog log (s/ox(zz))
In this proof, we only need to prove that we can also construct specific w((h,) W (2.1) that
such
p (22.)) (olog (s) Glog (w)2.h) T ==(")) -3h log (s/9n(zz))
Recalling the proof of Theorem C.2,
# (1) (az OT, loggi (xx),... (zgg)
Therefore, we can choose
(2.h)) Sh: w (2.h)
(1x1) (D (D-M++111) TRD w
(dxxd) RDD
where ((xx)) (p).pz) means that: it equals to L for the (p1, P2) p2)-th x r blocks, and 0,xr for the other r x blocks.
The the following holds:
(2.A) (DroR(s) cloR (wo(..t) Ta((1))
(2.)) log (s/ w (2,b) T xx
(1)) (((1)) = -n log (s/9)(z)))
The rest of the proof is exactly the same as the proof of Theorem C.2, and we do not repeat it.
37

---

D Proof of Section 4.3
D.1 Proof of Theorem 4.4
In this subsection, we give the detailed proofs for the general case of K-adaptive, long but M -ssparse memory:
y: f P4-t11"" Ft-ss)
where the adaptive memories satisfy:
1 91 (x:);
12 92 D2s Ftt Bt-tt));
tK+1 9K+1 (Zt. -t-ti It-b
fK+2 9K+2
xz-tk);
tM 9K+1 (a Tt Tt- ( xi-tx)
where 1 S 4 < Ty holds for any k E [M]
Theorem D.1 (Restatement of Theorem 4.4). For any target H H Hadhup
(K,M) rale n. E N4, and H,m m
N4, there exists an L-layer (L K + + I[M + 13) Transformer TF TF....ypp and a constant (n) such that: the width satisfies
(L,H.m) (12)
M Σ
2 max V
l1
type lin,
m 2
(E[K]
k=K+1
M
1 max V
Σ
|llog 9. 11 T?).
type log
[E[K]
k=K+1
then the following approximation rate holds:
TF
S EPEN Estt (type)
[lfll
where EPEN
and
Vm
2n+2
0 C(n)
Σ K
1.02(n++i)
(EM c0.01Ti)
type lin
H
EAtu(type)
C(n)
E1=1 (2200((+1)
+ EM T7.01)
2n+2
type log
Proof of Theorem D.I. First, we choose the embedding dimension D (M 1) + 1), and select the same embedding matrix WF (La, T)T E Dxd by 0 =E RDD as the proof of Theorem C.2. Moreover, we still use the network with precision FFN defined in Appendix C.1 tackle the discrete values of memories.
Then for any input sequence X (æx) the token after embedding satisfies:
00) Wg + bg [x) 0 )T
D....
Thus, for L-layer K + HM K + +1)) normalization free Transformer TF TJ with Prype: the output token x
NP NF sype (L.H.m)
(K+1) of t-th input token satisfies:
"
(1-1/2)
xz + W
(1)
Attn (L.b)
(
1515
38

---

(1) 11-1/2)
FFN (a. (a((-1/2)) 1315L
11)
Et Zt
(T++) FFN (+11 (x) 11
Zt
where
Attn, (1hh) Attn (X)
w
a exp (woli
Te, W wr))
ve-s) > + pl.N)) Despa (5)
s=0
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 2 K +1
(0)
Ft
Step 1. 1-st Attn +
(1/2)
(U)
Step
2. 1-st FFN +
(1/2)
+ (0T (0T,4,00 ,4,00 1)T
Step
3. 2-st Attn +
(3/2)
(1)
(0) -tt 0 TT
Dt
Step
4. 2-st FFN |
(3/2)
+ +00 12, 0
Lz
Step 5. 3-st Attn
+
(5/2)
(2)
(0 x. -,,,, 0 0'7
Ft
xz
Step 2K + 1. K + 1-st Attn +
1K+1/2)
(K) + (0 x. xx O)
Ft
xz
Step 2K + 2. K + 1-st FFN +
(K+1)
(K+1/2) + (0 ,tK+1,.. .tM,
x
Step 2K 3.3. K + 2-st Attn +
(K+3/2)
(K+1) (0 " 2 0)T
Step 2K + 4. K + FFN +
x (K+2) f(z
Regime M K.
(0)
Step 1. 1-st Attn $
(1/2)
(0)
Step
2. 1-st FFN $
a
(1)
x
(1/2)
+ +00 (0T,4,0%_-->
0/--; T)T
Step 3. 2-st Attn
(3/2)
+ (0) x T
tt-t, 0 TJT
x
x
39

---

Step 4. 2-st FFN +
(2)
(3/2)
+ +(0 .t. 0, T
at = Zt
Step 5. 3-st Attn +
(5/2)
(2) It
(024: T
12 0
zt
Step 2K + 1. K + 1-st Attn +
(K+1/2) (K)
0T)
Zt
Step 2K + K + 1-S + [K+1)
Case type log.
Regime M 2 K + 1.
(0)
Zt
Step 1. 1-st Attn +
(1/2)
(0)
Step
2. 1-st FFN +
x
(1)
x
(1/2)
+ +00 (0",logt nigtt, 0 - log 2)
Step
3. 2-st Attn +
(3/2)
+ (0) 2. T
Lttt 0 T)
zt
Dz
Step
4. 2-st FFN 1
(2)
x2
(3/2)
+ +00
log 12, 01)-1)
Step 5. 3-st Attn +
(5/2)
(2)
+ (0) L,, 0 0
zz
Step 2K + 1. K + 1-st Attn +
(K (1/2)
(K)
+ =0
2 2lgg 0 TTT
Zt
xz
Step 2K + K + 1-st FFN +
(K+1) at
+ (0 .llogt dogtk+1,"" pegtm.07 0) T (K+1/2)
xz
Step 2K + 3. K + 2-st Attn +
+3/2) at
(K
(K+1)
+ (0 +1jd - - 0)T
Zz.
Step 2K + 4. K + 2- FFN + (K+2)
x
2 f f( Bt- , (11)))
Regime M- K.
Step 1-st Attn
(1/2)
(0)
x
x
Step 2. 1-st FFN
(1)
(1/2) + (0 (.o. f1. 1, T
x
= x
Step
2-st Attn
(3/2)
(1)
(0 - 0 TTT
Step 4. 2-st FFN
40

---

(2)
(3/2)
+ (0
log L2 0 0
Step S. 3-st Attn
[5/2)
(2)
+ (0 22 12, 0
2 x
x
Step 2K + 1. K + 1-st Attn
K 1/2)
(K)
+ 2/ 0J)
Et
se ai
Step 2K + K st FFN
[K+1)
zt
(i Ft-
For simplicity, we denote the following projection matrices:
p(k) (Oaxkd
Iaxd 0) RdxD 1sks M;
p(()
Tkdxkd
Oaxd
0
(DDD))) 15 S M;
0 Oaxd (DD-
Q(h) = (Ha+t))xxa411 0) R 1sks M:
Q (k) (0 (DD-AADDXXD-RADD)) RRDD-DD 1s S M:
= (O(M-K)xx(KtDd (MM- 0) (M(M-)
R [[K++))x(K-I)) I(M+H)((41) E (RID-MM-XA))D,
Step 1 is trivial due to the use of the residual block.
Step 2. In the same way Step II in the proof of Theorem C.2, obtain the conclusion in this step: the width of FFN satisfies
Ω 11 l1:
type lin
m 2
|log 91 11 TP)
type = log
then the following holds:
z (1) (1/2)
+ (OT 4, T, T) Di
Thus, (E1) holds for / = 2.
Step 3 Step 2K 1.
Case type lin.
FFN layers.
We use 1-th (2 $ 1 K) FFN layer to express 1-th memory exactly.
By Lemma G.6, there exists a two-layer neural network with m neurons defined on Rddd
2NN (x) Σ a (bb
T + c(
such that
1NNN 9t
(1-221))
For 1-th FFN layer, we only need to arrange the parameters a (1) and o
( (k:
[m], 2 < 1 S M).
41

---

Denote 6 (61"", .OOT E RDD for k E [m], < < K - 1. Consider the
following two-layer neural network with m neurons defined on RD:
m
1 ( T 11) FFN (ax) = EDDMM-I-
ck
It is easy to verify
FFN (z) = (oT .0) (Q
0 ( 0 E ER.
Va E R
Notice that the width mn satisfies
1g:l vm
1
<
4'
and the input x!" 112))) satisfies
1lallrap I ... I. - 1)T T (11-11)2
-2) (1-1/2)
...
the following holds:
9r (t: 0t-t 1) - 1())
2NN (Q (0((((11))))
<< (x).. ... x01-)-))= (: z1 112))
(1-
+ +10(Q0 (11))) x 1111) - {()
2NNN (Q (1- x
11 (-11))
< 1119111rapp (10] ... 10, T - ((1-1)x((
x (1-1/2)
11, + +1|00 22N
1
1
< + 4 2'
Noticing t = gi
1t 11- E N+. we have
(()) (Q(1))))) (1-2(1112))) 4
Thus, holds that:
FFN (x) (1-1/2)) = =OT,, ti, 0o TT
Attn layers. By Lemma F22, for any rate n E N,, there exists a constant ((n) and K functions
11
(I;
=
ona o exp(-BLA - B))
h=1
H
Σ
an exp B Bind),
151SK
such that B1,, > 0 and
01 (1: B)lle x C(m)euo1(n11))
sup ISB
[T = B)
Ha 1glSK. K.
Moreover, Noticing that 1 < gl()) Ti holds for any X (xx))ez E X and 2 < I K, the following holds:
sup |I[. - o xx (:: (1:t))ll,
x
|I[ = B} + exp (:: S (1+11000
< sup
1SBTT
11"
42

---

Therefore, for the attention heads (h [H] in each layer / (1 < S K), we can choose:
p p = BL wo =I W w1l+1.h)
a0, ((xxd)
((+1,)) ER DxD
w v 0 (1xI)
EDDX(D/H),
(D- M+01)
(+++) V /
(0.1) E DX(D/H)
( where (p).Ps) means that: it equals to fxr for the (p1, P2) r blocks, and 0,xr for the other blocks.
Case type log.
FEN layers.
We use 1-th (2 SIS K) FFN layer to express 1-th memory 4 exactly.
By Lemma G.6, there exists a two-layer neural network with m neurons defined on Rdd
(x)
a o(b (1) x + x++ )
such that
[loggsillee
|oo gills vm
log 91 - 22NN
-(()
For 1-th FFN layer, only need to arrange the parameters d (1) t and ol (k
[m], 2 < 7 S M).
Denote 0 following /-th layer 2NN with m neurons defined R:
(b% (1)
оT) E RD for k [m]. 2 K 1. We consider the
FFN (x)
Σ
eD- SD-MMH-10 (1) (b)) x + di7)
is easy to verify
FFN = (OT f 12NN (Q()))) (07 -0b- CRD. Vz E RD.
Notice that the width satisfies
(Hlosalll) sills vm
87i
and the input n. (1-1/2) satisfies
|log 9i <i
[o)) ... 2 (1
(1-1/2)
<
2
8T8
the following holds:
log gi (a,....
Ft -
-(()
2NN (Q (")) (1 (1-1/2))
go (z,,
,I log gi (1) (1) (1-
(1- 11/21)
+ gg 20 1 (Q (1) xt
(1 (111/21)
43

---

||oo gi Lip
(x) .... x -Q"0 2x 111122 xx111111)
logg: -
-f() -
2
1
1
871 8Ti
47i
which ensures
(() (Q (1) xi
2 - - (a ... -
exp
(ONN (Q xt - - exp (log (g) (2) 22 x((-)))))) 1))
exp
maxx { 12NN (Q
[ (x ( log (Z). , xx--)=)))
S exp
|aAN (0 (121 log (91 (2t; " "
log (ai( .. I 0z- 1) + 8) 4T,
Sexp
1 <e1/8 T. 4T, 2
Noticing g I1- E N,, we have
Qual 112)) log (exp FFN") (ar,, (ar,,.. - log 41
Thus, it holds that:
FFN (1) (a) (1121) (0 log 41, 0b-
Attn layers.
By Lemma F.5, for any rate E N+, there exists constant C(n) and K functions
o (t;
Σ
(t/BBBB))
Br,
h=1
"
01 exp
BL Br log(t/B))
13ISK
h=1
such that Br, > 0 and
C(n)T (01+11
sup 15BST
- (: 17 1
11555 K.
H
Moreover, Noticing that 1 I s1(-) Ti holds for any X (xI)LEZ E X' and 1 1 I K, the following holds:
sup |[| 41 o poly (: (::44 (::0)
II|- B} opoty (-: (+BB l)
sup <<BTT
(844
H
Therefore, for the attention heads h (h E [H] in each layer I (1 S 1 < K), we can choose:
p (HIM = BL... ((++1) =1, W (1+.N)) = =
(141,1) E RR DxD
w (1+M)) /B E DDX(/HH)
(1xl)
w (++ / 0 (D.1)
Dx(DHH)
where ((rx))) (p1.2)) means that: it equals to Ixxr for the (p1, -th x r blocks, and 0,xr for the other blocks.
44

---

Similar to the estimate in Step II and Step III in the proof of Theorem C.2, it is easy to prove the following estimates by induction.
the width satisfies
max [E[K]
|
= (119x 11:),
type lin
m 2
Ω
max [E[K]
||oo 118 17 = Si (1log 9k 16 Tx)
type = log
and the head number satisfies
C(s)
K
2.02(n+11)7
S
type lin
H
4 max 18 -E
1ip
C(n)
K- T2 220
5
type log
max
log 9i gilp
then the following estimates hold:
(E1) for any < L K,
(1) (1-1/2) +00 44, 035-141) x Zi
(E2) for any I K,
p( p00 (1+1/2) 200)200
x
* (E3) for any < I K,
Cin)e
p(() ( (1+1/2)
x (1)
+ (O a -.)
Hh C(n)T (1(441)
type lin
type log
(Q())
(1+1/2)
xz,0 1 5
C(n)
f=1 c0.02(m+1)Ti, 7, 12.02(nt1),
type lin
C(n)
Σ f=1
type log
The Remained Steps.
Regime M 2 K + 1.
Step 2K and 2K +
In the similar way as Step 3 ~ Step 2K- - 1 in this proof and Step I1, Step III in the proof of Theorem C.2, it is easy verify the following estimate.
If the width satisifes
>
J= K+1 [1a)
type lin
m
Ω
J= K+1 [log 91 (
type log
and the head number satisfies
C(n)
K
0.,0(n++1))
<
type lin
H
max |o laap [E(K]
C(n)
1=1
K
(2200((+11)
max log 91 hhp
type log
then the following estimates hold:
(K+1)
(K+1/2) + (0 "x.,,".,,,.. O)
x
xt
45

---

(K43/2) R R 21
R. 2/ (K+1))
R
(K+3/2) 2
x
(K+1)
(0 (OK+I)DD x - (
00017
C(n)
-
type lin
Hn+ T7 2
n+1
Ei=k41
C(n)
type log
Q(())
(K+3/2) x )
2n+2
C(n)
c0.02(n+1)7) -1=1
K
+ T2202(n+11)
Ei= c0.077)
M
type = lin
n
Cin)
EE=K+ T7.01)
2n+2
type = log
H
Step 2K + 4 and the final bound.
In the same way Step IV in the proof of Theorem C.2, there exists FFN, such that the following estimate holds for any and X:
Hx(X)
[K+2)
S Illfl (M))) (KK43/22) - 2!(")) EFEN
Llip Esua (type) + EFFN,
where
(0(111
[1ffl18 vm
EEFN =
Eut (tyn) |Q(AN) (a) (K+3/2)
xz (0)
2n+2
Cin)
>K K
c0.02(n41)T + 1==1
1 canIT:
type lin
C(n)
K T2.
(E T7.01
2n+2
type log
n"
Recalling our analysis, we need the head number satisfies
C(n)
Σk
c0,0((n+))m
<
type lin
Hm
1=1
max
K
C(n)
2.200((+11)
type log
H"
1==1
max kc
log Lip
Due
C(a)
K -==
1002(n+
S Extra (type)
type lin
C(n)
EE=
K
T,
2002(++11
(tyne)))e),
type log
when is large enough, this condition holds naturally and do affect the approximation rate.
Moreover, we need the following condition on the width:
46

---

Ω2 max (E(K]
E -i=K+1 |1sill
type = lin
m
52
max V E L1=K+1 |llog all 17)
type log
[E[K]
Regime .M K.
Step 2K + 2 and the final bound.
In the same way Step IV in the proof of Theorem C.2, there exists FFN, such that the following estimate holds for any t and X:
(x)
(K+1) 2x
$ If l (2/ - xx 2 + EFFN
II Lip EAttuttype) + EYFN.
where
|1
lss
EEFN = O
m
Extta (type)
QM x
(K+1/2) (0)
C(n)
c0,02(++))Ti, type = lin 1=1
H
C(u)
7/2
22202(++11) type log
H
21=1
Recalling our analysis, we need the head number satisfies
C(m)
K-
e.02(n-11)1
type lin
1=1
max 16(K
[9t llpp
C(n)
T
2.0((++1)
<
type log
H
1=1
11og
18
Due
C(n)
K -=
0002(n+1)4
< EstrH (type),
type lin type = log
H"
C(n)
K
T
2.02(n+1)
< EsuD (type),
H"
1==
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:
max [E[K]
1gt 1
type = lin
m >
max [E[K]
llo 91 [| 1?²
type = log
Combining these two regimes, we complete our proof.
47

---

D.2 Proof of Proposition 4.5
Proof of Proposition 4.5.
This proposition is direct corollary of Theorem 4.4. It can be seen special case of M = K in Theorem 4.4.
Therefore. under the same conditions, there exists a K + 1-layer Transformer TF TF..F.typ (12) and constant (nn) such that: if the width satisfies (K+))
i max iE[K]
9 1l
type lin,
2
52 max |log gills T?)
type log
iE[K]
then the following approximation rate holds:
H
TF - EPEN + II Estta (type);
where EprN = ①
lifll
and
Cin) H=
Σ K
c0.0((n+1)7
type lin
Exuta Etua(type)
0
C(n)
H
21=1
T/
T(2-2((nt))
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 med proportionally linked to the sum of all the memory functions' complexity:
Σ
type lin,
kE[K]
need
Σ [E[K]
|log 9:11 7,3)
type log
(M+1) correlates
For M + 1-layer Transformer, the required width of FFN layers m need with the maximum complexity of the memory functions:
h max (E(K]
1g::1
type = lin,
(M+1) nood
m
h max (E[K]
|log 9i 11s 17).
type = log
It is easy that:
(M+1) m need
max (01, .as)
m
(2) need
Σ ak
M
max(a1.
am} } S
ak
The required number of Attn heads. To achieve the same Extaa (type) =
48

---

for 2-layer Transformer, the required number of Attn heads Heed satisfies:
Cin) (eed
K 21=1
e0.02(n+1)2;
type lin
C(n)
Ei=1 Ti
K 2200((+t)
type log
(eed
for M + 1-layer Transformer, the required number of Attn heads H (1+
satisfies:
C(n)
DM e0.011;)
a+1
type lin
Hodd H(M++))
a+1)
O
C(n)
Σ M
Ei=1 177011
type log
H(2(+2))
nood
It is easy to see that:
H (M+1)
need
2x
1i + 8
H H(2)
(b1 + ... bm )2
need
bj + bi
(b) +... bas)
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.
49

---

E Proof of Section 5
E.1 Proof of Theorem 5.1
In this subsection, we give the detailed proofs of the warm-up case of (fixed) essentially sparse memories as follows:
y: ((X (t) (X pas) (t)),
where pı())... (M(() e! (N) serve memory kernels, and (X pk)(t) Ex=0 (p=) denotes the convolution of the inputs with kernel Pk.
Theorem E.1 (Restatement of Theorem 5.1).
(A) Consider H. (14) with exponentially decayed memory kernels, i.e., there exists 3 >> 0 such that Pi(t). .Pa (t) O(e-*t) ).) Then for any target H HPss, rate n E [[99]]], and H, m N+, exp (7) and a constant ((n) such that there exists 1-layer DP-free Transformer TF E TTF.HH, (1.H.m)
H TF S. EFEN
IIf (tuua(typ)):
(B) Consider Ess (14) with palynomially decayed memory kernels, i.e., there exists B such that Pi
= (t- Then for any target H E H.Es, rate E [L0.993] - 11. and H. m E N,, there exists a 1-layer DP-free Transformer TF E &TD.PE (7) and constant C(n) such that
(1.H,m)
H - TF S EFFN || It Extta (type);
where EPPN
Ô (
[ vm
and
(C(n)Mrt)) H
Symeet
Proof of Theorem E.I.
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 pa(-) instead of simple 1f-= = Tx). But for the completeness the proof this section, we still provide the detailed proof.
First, we choose the embedding dimension D Md, and select the simple embedding We (Taxd, 0)T Dxd bg 0 E RRD.
For any input sequence X = (æx)e the token after embedding satisfies:
x F
= Wg + bg = (a, OT E R.P.
Then for one-layer Dot-product-free Transformer TF E T TFDPF DPF.typ output token TF, (X) t-th input token 24 satisfies:
without residual blocks, the (1,H.m)
a (1/2)
(())
Attn (1,b) (x
x (1) FFN (1) (x) (122)
where
Fr exp (p(1.t) Deypa (s))
Attn, (1,h) (1.))
(X) = w (1.)
too j=o exp (p(l. Pleypo ( (i))
This proof can be summarized the following process:
E
50

---

Step I. Attn layer
2i (1/2) ((X pi)(t) ... ,(x pM)(())
Step II. FFN layer
(1) 1 ~ f(X pz)(tt) -M , (X pM)(t))
Now give the formal proof.
Step I. Extract the memory locations by (Dot-product-fred Attn layer.
We consider to use H3 attention heads (from Σ H; + 1-th head to E H,-th head) extract and it satisfies to Ek H
H.
( (0ax(x-1)d
(k-(I-1)d I)d
Iaxd 0) RdxD
Isks M.
(
(kk-1)dx(
Oaxd Oaxd (MMAA-I)X(MM---1))
ER(M-IjaxD 1 M.
Now we consider the extraction k-th memory (X pt) (1 S S M).
Case (A). Approximating exponentially decayed memories by type lin. Because there exists such that (x((t) Ole 8t), by Lemma F.,, for any [[99]]]
and m E N4, there exists an absolute constant ('n)) only depending on n and a function
Pk (t)
Σ
Oge -hat
Σ HittshsE M;
such that B, > 0 and
C(n) m
(lxx()) - 1o0
(Oll,,) Σ (px(s) 20 ps)( S
Therefore, for these attention heads
( k-1 Hi 15 Σ
H:). we can choose
to0
((L))) Sh.
W
Σ exp(- (xp(-3Bn))
8dxd
ahh
(k,
where (k.1) RR DDD means that: it equulss to Idxa for the (k, 1)-th d d blocks, and Oaxd for the other d blocks.
Then it holds that:
m H; Σ
D H:
400
(k-11)d
(x(0))
(1,b)
Σ
Σ
BAN
E RRD.
Oh
st-s
Am Ek-l He+1
hm E 11+1
==0
This implies:
> Hi
E H.
p()
Attn. (1,h)
(x()))
9,.5 x B-
1= H,+1
h= -
H.+1
s=0
51

---

E H.
P(
(1.1) (x (0) = 0,
Attn,
>=
H,+1
moreover, the following estimate holds:
H:
plk) Attn, (1.1) (x(1) (X pt)
H1-1
Hi
+00
Oh
Di
34 pt ph (8)
H
H,
ane ahe 3ns - 11s Tk} 21-8
h= H,+1
Ei Hi
one one 8ns Pk((s)
==0
h Ei=l
Het1
C(n)
=+) Pk (l
Case (B), Approxpmating polynomially decayed memories by type = log.
Because there exists B >> 0 such that px(() ((L-)), by Lemma F.6, for any [[0.993] - 1] and m N4, there exists an absolute constant C(n) only depending on n and a function
pooly (t)
Σ
agt 8
E M.+
H:
such that Br > 1 andd
[px() - sBoty
= (x((s)
Σ
to0
(p)ol(s)) -
spoly (s)
C(n) m
(1444
1=1
Therefore, for these attention heads
[x==] H4 + 1 h < Σ Ha) we can choose
to0
p (2,) -Bb,
w( =0h
Σj-
8
where (1,,1) E RR DDD means that: equals Iaxa for the (k. 1)-th d d blocks, and Oaxd for the other d x d blocks.
Then it holds that:
Σ H. Σ
K H.
+:00
0 O 1)d
Attn. (L.b) (x())
9n
Tc -s
Am Ei-l #1+1
h
Ek-1 He+1
0
This implies:
E H, Σ
Dt Hi
p(k)
Attn, (1,h)
(x (x))
8x 1--
h= h= H.+1
1= H,+1
52

---

Σ
p(k)
Attn; (1,1) (2) (x = 0,
h=
>t H,+1
Hi
plk) Attn, ( (x(1)) (X pt)(t)
-x
11-1
H
+
04h
8h Di-s Σ
x - (P)
H,-1
8=1
==0
H;
Oh8 0h8 8h - p1(()
31-5
H,+1
H:
aAs Br ps(s)
==1
Diel
H1+1
C(n)
tH (-) p&())
H
Then we combine the estimate for all & E [M] for these two cases. By choose Wo = Lp. we have:
(X * pt)(t)
(1/2)
(X * pas pL))
> H4
Σ
Attn, (1,A) (X) (X) - (X
(t)(t)
0d
H1+1
Σ H. Σ
(2--)d
Attn, (1.10 (x) -
Xx
(x*pa)]0 (2))(1)
M= Eis H,+1
0g
M
E H:
Σ
Σ
p(t) Attn (1.b) ( (x(1)) - (X * px)(1)
k=1
> Het1
M
C(n)
EEEtt
for both Case (A) and Case (B).
H
Consequently, one detail is to assign the head number ( (H&) ) M small as possible. Here, simply choose the same Hę:
k=1 such that the error's 's sum EsSta (type)
H Hs = M'
k [M].
Thus, we obtain the bound in Step I:
M
C(n)
C(n)Mm+
Extta
Σ
H
H
km
53

---

Furthermore, by choosing EattA I 1, it holds that
X pz)((t) (Xx pM)
(x (x+ + : (x pas)
(1/2))
1
(2/2)
S Estn +152.
Step II. Approximate the readout function by FFN layer.
In this step. aim to approximate the function using two-layer network. By Lemma G.6, there exists a two-layer neural network with m neurons defined on IR
FFN Σ
(bb
such that
EENN = FFN -
1 (0((22))))))
lill mm
The final bound.
For any and X E X, it holds that
(X) x (2) = 5((X * p1)(t), ... ,X PM)(t) FFN()) a (2.1/21)
S((X * (.)((),.....)))) (X pM)( - (z.f + (2/01/2)
FFN (2)122)
|[(X * (.)((),.....) (X pM)(t)) -1( (x1112)) ) + (z)!/21 - FFFN (1/2)
1 $1 1(X pi)(() (X )P) _ma [1/2)
+ || /FFFN())
(=122-)))
$ III/Iliip Est + EYEN.
where
lf mm
C
EPEN
Eatth
for both Case (A) and Case (B).
11"h
Due to the arbitrariness of and X, the proof is completed.
54

---

Key Lemmas about Approximation
F.1
Approximation by the sum of exponential decay
Lemma F.1 (Exp decay, fixed Delta function). For any T E N., m, N4, there exists and
absolute constant ((n) only depending and dm (t) E age Out such that
C(m)c
||[ T om (-)le where BR > holds for any k E [mm]
m
Proof of Lemma F.I.
Let at, Y > O be constants, and they will take specific values at the end of the proof.
First, recall the standard bump function on [-1, 1]:
exp 0, otherwise
x (-1,1)
(x)
and we can define the following constants for T 2
HT = of = e af e aa(++))
Then we consider the following bump function T E C
([0. C²0 1)):
V
- I E (UT OT, OT, T
(x(
of
0, otherwise
where Vr is scaling constant such that Vrr(eaa) ET, First, we consider the approximation of V on [0, 1].
Notice that VT E ((0, 1)), and Th(h) (0) = 0 for any l E N. For the standard bump function
V, for any n N4. there exists an absolute constant M (n) > only depending on n, such that
max sup (k) (x) (n).
0gAg10 11111,1
Notice that for any E and x [0, 1].
w (k) (x)
VT (R)
x xz- MT
of
OT
Therefore, the following upper bound holds:
VT Mr(n) max M(m) ( EπT
Vir
oSkSn of
07
(e-aT - a((+))) M(n) = M M(ne
e(Ttna)T = C(n, a)e (7
(1 1/e)n
m-
By Lemma G.5, for any m E N4, there exists a polynomial Qm (x)
Σ
aya such that
My(n) m
C(n, a(n,a)elrtno) m
sup (T(x)) Qm(x)) < ze|o.]]
Now we use the transform z aat on the function V and consider
(t) == e-- - ( -at) t E +00).
55

---

It is easy to verify that Pr satisfies that
(r(() = I(t T-).
Moreover, consider the function
(t) = em t [0, +o0).
Then by choosing a = y 0.01, the following error estimate holds:
to0
(+) - T(. = (l)
Pm (1) +T((1)
+00
+00
n Mr (n)
Σ
12 1mm
VT(E (a)c
S
mn
1=
1=0
C Cl,, ane(taa
t00
C(n)c0.0((x11))
Eone =
m
m
1-0
1=
m
m-1
Finally, notice that (t) = 7m (e (E)
Σ
age (0.01+0.01k), so we can select (%)(()
k=0
(m)
Lemma F.2 (Exp decay, adaptive Delta function). For any E N, n. m N4, there exists an
absolute constant ((n) only depending n and deep B) Σ ane B) such that
max B
|||[- = =3) p-; (;)le 5 n
where Bk holds for any le E [m]]
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.I. For the same V-(()), for any n. m E N4. there exists an absolute
m-1
constant C(n) only depending on and polynomial (m
Σ
agz such that
sup (T(xx) Qm (x)) Cin)euuun++1 =E
m
Moreover, using the transform 0 (t2 the function V and consider
Φr(1; B) -U.01((-B+T ( (.0. E (00+)))
It is easy to verify that ( satisfies that
Φ (t: (t: =I(t B).
And we consider the function
Pm (1; B) - -0.0000-++ Qm (e-OUI((-B+T)) 1 t00)
56

---

Then, for any 1 B S T, the following error estimate holds:
[ B) I(. BB)ll = Σ
Pm B) (t: B)
1=
0.01(t (+1[t-B+7] Qm (e (c-0001t-++7i)) Ur vr(e- (c-001(3-B+77)
t=
0.01f
sup
Qm(x) - (x)(
=E[0,1]
C (n+ 1)T
+00
0.01t
m
m
Due to the arbitrariness of B, the proof is completed.
Lemma F.3 (Exp decay, fixed Delta function). Consider exponentially decayed memory pl-): there
exists 3 > O such that p(t) (()= Then for any E [[99]]] and m N4, there exists
absolute constant (nn) only depending on n and a o (t) = Σ age Bat such that
C(n)
IIp(-) O (1), S
m
where Bx holds for any k [m]]
Proof of Lemma F.3.
There exists C' such that [p(t)] & Ct-
Let o > 0 be constants, and they will take specific values at the end of the proof.
First, recall the standard bump function on [-1, 1]:
(xr)
exp 0, otherwise
x (-1,1)
and we can define the following constants for T > 1:
= oT
2 (e - -
and we consider the following bump function V E ((0,
VT
E- (μT OT, ouT + OT)
V (x)
oT
0. otherwise
where Vr is a scaling constant such that (r = ETT P(T).
Consequently, we consider the sum of bump functions on [0, 1]:
(xxx)
(r(x).
T=1
It is easy to verify that (μT, oT, PT, oT, ) (MT, oT, PT, + or,) 0 for any Ti T3 and
x(x)= = (T((), pr - or S x S pm or
0, otherwise
57

---

First, we study the property of :p()). We denote the absolute constants M₁. = supp, (x))))
Notice that for any & E N,
V (x:)
Vi (k)
2 pT
Tf
OT
Therefore, it holds that
sup "E(r tor)
10 (k) (x)
sup
(k)
(x)]
VT
Ex P(T)
CM3ee (1 e-
Mr
MrE
(e-aT e-((T+))))
TT
Therefore, if321= + ka, then the following uniform bounds holds:
sup (x()(()) =
10! (x)]
sup T21 Tel
sup
=E(U,1]
CM
CM&e
sup (1 - (1- (Itka-9y2
(1 - c-aa = a(k,
Consequently, consider the smoothness of + & 0.
Recalling the previous results, for any x E (0, 1]. we have
(x)) < Clki (x)
e ko-kko--99 ByT
(k (1+( x E (uT - oT, PT + oT);
NT OT
(kp(+) (x:) 0. otherwise
Thus, by induction, is easy verify that for any B-1
a (ie
(0) = 0.
Therefore, for any < A-9 (n E N), (0) 0 holds for any 0 S k S n. Moreover, there exists absolute constant C'n,, a) such that:
(x(( S C(n,a).
max sup osksn ze(0,1]
m-
By Lemma G.5, for any m E N4, there exists a polynomial Qm (z) = Σ oga such that
km
[((xx) - (m)) C(n a) m
sup =E(U,1]
Now the transform x = -- (t 2 0) the function & and consider
1
(t) e cl0
t [0, +00).
is easy to verify that + satisfies that
4+)) N p(t)
Moreover, we consider the function
1
Pm (f) = eve Qm
t +oo).
cat
58

---

Then for any < A-7 (n N), the following error estimate holds:
+00
Pm ())())p(-)eess
Σ (t) +())
+ Σ
C(n, a)) m
toc
71 Qm (c-at) v/r (e: (e=at)] S
By choosing = 5 10 and 10 23- it holds that 99/ < _ 8_
Thus, obtain our result: for any [[993]] (3 1/99), the following error estimate holds:
C(n)
+o0
((n) 1
((n)
(+) p0) S
m Σ v xt
m
6 10 23
m
F.2 Approximation by the sum of polynomial decay
Lemma F.4 (Poly decay, fixed Delta function). For any n, m N4, there exists an absolute
constant ((n) only depending on and opoly (1) = Σ aut 8x such that
k=1
||T( - ppols () S where Bk > holds for any le E [m]].
m
Proof of Lemma F.4.
Let at, y > 0 be constants, and they will take specific values the end of the proof First, recall the standard bump function [-1, 1]:
exp 1- x
(-1,1)
(xx)
0, otherwise
and we can define the following constants for T' 2
PT
Ta
Ta
(T + 1)a
Then we consider the following bump function Vr E C ([0, 1]):
V ) x E (IT - oT, oT, (T)
v (x)
0. otherwise
where Vr is scaling constant such that Vr (= T
First, we consider the approximation of V on [0. 1].
(0) Notice that Ve E (0o( 1)), and (0) 0 for any & E N. For the standard bump function
V. for any n N,, there exists an absolute constant M (n) > only depending on n, such that max sup (T(() < M().
osksn 2E|-1.11
Notice that for any l: E N and x E [0, 1].
Vr (k)
x PT
(x)
T
OT
59

---

Therefore, the following upper bound holds:
VT ((n) = Vr
T
Mr(n) = max K uSkSn T
M(n = (1/7a= 1/(7 + 1)a M(n)
of
TT
2" Mn)e ( p == a
a
a
By Lemma G.5, for any m E N+, there exists a polynomial Qm (x) = m- Σ
og such that
(x(x - (x)) S m I C(n,a)
Mr(n)
sup ==
Now we use the transform
x
1 pa (t 2 1) on the function and consider
1 Wr
1
T == 1I+y
6 [1,
la
It is easy to verify that or satisfies that
2T(())__ = 1(t T).
Moreover, we consider the function
(l( = +
Qm
LE (o,+
ta
Then by choosing a 0.01, the following error estimate holds:
(.m(.) - II(.- = T)ll) =
(m) (t)
4000
+
Mr(n)
Σ t=1
Qm
Vr
gl
ts
ta
+l
m"
C(n, a) + (7++((+4))
t00
1
m
814y
m
100011
m
m-1
Finally, notice that Pmn(-) satisfies to (l)()) p p- Qm (1=) select @poly (1) = (m)
Σ
on (1.00000))01)
so we can
Lemma F,5 (Poly decay, adaptive Delta function). For any T, n, m E N4, there exists an absolute constant (nn) only depending on and opoly (t; an (t/B)-BB such that
((x)71.000++1
||[[ B) opoly (:: B) (8,4))
(:B))le,()))
max
STST
m
where Bg holds for any l [m]]
Proof of Lemma F.5. The key point the proof to note that the adaptability of B can be eliminated by the rescaling operator t/B
60

---

First, recall our proof of Lemma F.4. For the same (-((), for any m E N.,, there exists an absolute
m-1
constant (nn) only depending on and polynomial Qm = Σ agr such that
[v(x)) - Qm()) C(n)T1.1((41)) =E(0,1]
sup
m
We the transform - 2 1) on the function v and consider
1.11
0.01
pr B) =
E
[1. +00).
tT
FT
is easy to verify that (r(:)) satisfies that
(r B)l
I[t B).
And we consider the function
1.01
0.01
(t ==
Qm
EE [1,
tT
tT
Then, for any 1 B < T, the following error estimate holds:
+000
(: B) 1(-- B))l
Σ
Pm
DT B)
1=1
1.11
B
0.011
B
0.01
Qm
Vrr
FT
FT
sup
1m((x) (T(2))
11.01
2E(0,1]
toc
((n)TI01(x+1))
m
11.01
m
Due to the arbitrariness of B, the proof is completed.
Lemma F.6 (Poly decay, fixed Delta function). Consider a polynomially decayed memory p()): there
exists 8 > 1 such that p(t) S). Then for any [[0.993] - and m 44, there exists
m
absolute constant ((n) only depending on n and opely (t) = Σ
agt 8x such that
1=1
C(n)
[lp(.) opoly (-)lle <
m
where 3k holds for any l [m]]
Proof of Lemma F.6.
There exists C' such that (p(t) C/t².
Let a, Y > 0 be constants, and they will take specific values the end of the proof First, recall the standard bump function on 1];
(- 1 x (-1,1)
exp
(x)
0, otherwise
61

---

and we can define the following constants for T
2 1:
1
PT
T
oT
2
Ta (T + 1)a
and consider the following bump function Vr
C000 ((0, 1)):
VT V
(uT OT,PT + TT))
V (x)
or
0,
otherwise
where Vr is scaling constant such that Wr (r(+t) = T p(T).
Consequently, we consider the sum of bump functions on [0, 1]:
+000
(xxx = vr(x).
T=1
It is easy verify that (er, oTi o. n (MT, T72 MT2 + oT,) Ø for any Ti T2 and
(v(()), -r or S x S pr + or
((z)= 0, otherwise
First, we study the property of (p().
We denote the absolute constants Ma- sup, (x))
Notice that for any lo E N.
(x) = VT (A))
x PT
of
OT
Therefore, holds that
(x)) =
v (k) (x)
sup #E(pr or NoT tOT)
sup
T
xE(er (ro
VT
p2+>p(T)
Ma
2t M
0f
+ -+
(T' + 1)((tt))patt M&e
Mre
20(2ta) pattkatta)))
a
a
Therefore, if k < 8 8-(1+)) Ita
the following uniform bounds hold:
kp (k) (x)
(k( (x)
sup
sup
sup T21 DE -oT
=E(0.1]
2k(2+a) CMre (
2k(2+a) CM+e a(k,a).
sup T21
k
a
Consequently, consider the smoothness of 4 at z = 0. Recalling the previous results, for any & E (0, 1]. we have
(x))
< C(k,a) a) - Clk, 2 T (+++)))))))) x E (NT - or, OT,PT + oT);
T
(k) (x)) 0, otherwise
Thus, by induction, is easy verify that for any i 8-(1+7)
(i E N), Ita
( (0) = 0.
62

---

Therefore, for any ادداا (n E N4), (0)
holds for any 0 S l < n. Moreover, the
I+c
following uniform bound holds:
max sup (x)) (z) C(n,
ssk osksm=elo..l se/0.1]
m-
By Lemma G.5, for any E N4, there exists polynomial Qm (z)
Σ
og such that
k=
sup 1x(x) (m()) C(n, a)) =e(0.1]
m"
Now the transform
p/ (t 2 the function yp and consider
1 (0)
2t) = n+ 40
EE [L,
It is easy to verify that & satisfies that
e(t) p(t)lN,
Moreover, we consider the function
1
(m) == 11+7
Qm
tE [1, +o0).
ja
Then for any n <
B (-(1+)
(n E N), the following error estimate holds:
Ita
+00
(P - p())lle((a))
Σ
(m)(t) +())
400
C(n, a)
+00
Qm
VT
s
fl4y
toc
ta
m
f14y
By choosing 10-2 and 7 10-18, we have 0.99, 1 8-1
8-(1+++a)
1+a
1+a
I+a
Thus, obtain our result: for any [[0.993] 1] (3 2 2/0.99), the following error estimate holds:
C(n)
C(n) 1
Ö(n)
(.) p()))e,(7)))
t +
1++11
63

---

G Some Background and Proof Preparation
G.1
T5's relative positional encoding
The T3's Relative Positional Encoding is primary focus of this study. Its standard form in practical applications (Raffel et al., 2020) adheres to Re,s r(t s), where
Y1, log(n /8) (D/BB
if < B
-r(n) =
[B.
if < D. n
2B 1,
Here, is large integer, signifying the longest distance of concern, while B is small integer. One can see that for n < B, r(.) exhibits polynomial decay, whereas for B < n < DD r(.)) demonstrates logarithmic decay. Consequently, the overall decay rate of r(-) is logarithmic.
The following Table further provides an example standard T5's Relative Positional Encoding.
Table I: An example of standard T5's Relative Positional Encoding
t
0
1
2
3
4
5
7
8
9
10
11
12
13
14
15
r((
8)
0
1
2
3
8
9
9
9
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
8)
10
10
10
11
11
11
G.2 Barron space theory
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 certain approximation accuracy? This gap was addressed by the Barron space theory (E et al., 2019; 2021). that for any function within Barron space f B, 2NNs with neurons (denoted by Hm)) can approx- imate them efficiently, at a rate of fnff f I O(IIfl / /m). remarkably independent of the input dimension d, thus avoiding the Curse of Dimensionality (Bellman, 1966; Bach, 2017). Specifically, the Barron space defined by:
established
Definition G.1 (Barron space (E et al., 2019; 2021; Ma et al., 2020)). Consider functions f X + R that admit the following representation:
/ ao x + c)p(da, db, de), x E X.
f(x)
For any p [1, +00], define the Barron norm:
M = inf (R, [|aP(([bb]] + 1c))))) 1/8
Then the Barron space are defined as:
Bp = E < <ox]..
Proposition G.2. For any p [1, t2) B, = Boo and |l,ll = ll
Remark G.3. From the Proposition above, the Barron spaces B, are equivalent for any p E [1, +oo]. Consequently, in this paper, we use B and || to denote the Barron space and Barron norm.
Remark G.4. For Barron space B. both Direct and Inverse Approximation Theorems hold et al., 2021). In this paper, we mainly utilize the Direct Approximation Theorem, stated in Lemma G.6.
64

---

G.3 Useful approximation lemmas
Lemma G.5 (Jackson (1930)). Let f E ( 11) with f(0) (0) = (() 0. Then
m-1
for any m Na, there exists a polynomial Qm (x)
Σ axæ such that
M(n)
Ilf - (m..1 S
m
where (() max (())
kSn
L ([0,1))
Lemma G.6 (Ma et al. (2020)). For any E B and m E N, there exists two-layer ReLU neural
m
network fm fm) Σ
ab x + c*) with m neurons such that
[Iflll vm
|| - 1-mmll2=(001))) S
65

---

H Experiments
H.1 Restatement of our theoretical insights
As detailed in Section I, our theoretical analysis reveals the following novel insights into the expressive power and mechanisms of Transformer:
Insight (1). The distinet roles of the number of layers, the number of Attn heads, and the width of FFN layers. (Ia) 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), 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 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 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). The efficiency of Relative Positional Encoding (RPE) modeling long-range correlations. The primary role of RPE is to approximate the memory kernels. (4a) Transformer with log-type RPE can handle heavy-tailed memories. (4b) Transformer with lin-type RPE can handle light-tailed memories.
H.2
Experimental Validation
To validation of our theoretical insights (1a)~(4b), we conduct experiments, from simple toy models to more complex LLM pre-training. The experiments are conducted A100.
H.2.1 Validation of Insight (1a)
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 (la): 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 al., 2017) with different L and H on the Open Web dataset (Gokaslan and Cohen, 2019) for 10,000 iterations (approximately IB tokens) on A000, using cross-entropy loss and Adam 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 (la).
Table 2: Results of the experiment supporting Insight (la).
L 1, H (26M)
1, L=
(29M)
1, 1, =
(32M)
5.796 (baseline)
5.689 (L 0.107)
5.660 (L 0.136)
1, HI (26M)
4, II = 8 (29M)
8, (32M)
5.796 (baseline)
5.374 0.422)
4.994 (1 0.802)
H.2.2 Validation of Insight (1b)
Objective. As mentioned in Section 3, sparse Boolean functions have no interactions among the memories and belong to our Task I. This experiment aims to verify our Insight (1b): for such tasks, a single-layer Transformer equipped with a sufficient number of Attn heads and FFN width m suffices, and there is no need to increase the number of layers L.
66

---

Setup. Specifically, we train single-layer DP-free Transformers with different H and m to learn sparse Boolean target function f:: (*)) = g (14s- I56 Tgg) :=
Σ R (Ias, T56. Tyy. for input sequence a = (01, 220000 E {+1} 100000000 where
wi generated by wt (N, Is). Training proceeds for 10,000 iterations (IM samples) using
squared loss and Adam with the same hyperparameters.
Results and conclusion. The final validation losses are shown in Table 3. As shown in this table, single-layer Transformer equipped with sufficient H (32) and m (256) is adequate for representing this sparse Boolean function. This empirical evidence supports our Insight (1b).
Table 3: Results of the experiment supporting Insight (lb).
π 2. 16
H
64
H
32,
256
0.21
0.04
0.01
H.2.3 Validation of Insight (2a)
Objective. This experiment aims to verify our Insight (2a): to learn sparse Boolean function with "complex" readout function and "simple" memories, increasing the FFN width m can significantly improve the performance, whereas increasing the number of Attn heads H brings almost no benefit.
Setup. Specifically, we train single-layer DP-free Transformers with different H and m learn sparse Boolean function with a "complex" readout function (g") and a "simple" single memory (I99): (=) 9 (199)= := 1=1 ReLU(wt xgg) for any input sequence (xI,' , .00 E {+1] 1000 where w are generated by w ~ (0, 1). Training proceeds for 10,000 iterations (IM 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 sparse Boolean function with "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 yield substantial improvement. This empirical evidence supports our Insight (2a).
Table 4: Results of the experiment supporting Insight (2a).
8
64
m7
512
11 8
H1 1/=00
64
11 = 512
8
0.49
0.006
0.002
m =
0.49
0.49
0.52
H.2.4 Validation of Insight (2b)
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 FEN width m will offer almost no benefit.
Setup. Specifically, we train single-layer DP-free Transformers with different H and m to learn sparse Boolean function with "simple" linear readout function (g") and relatively "complex" memories (I48, T56, T. (x) == g" (148 T56 To9) == I48 D55 + 2gg for any input sequence = (=,,.... 10000) [==1]1000 Training processes for 10,000 iterations (IM samples), using squared loss and Adam W 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 can significantly improve the performance (1.16 + 10 10-6) "), closely achieving task perfection. In contrast, increasing m brings almost no benefits. This empirical evidence supports our Insight 2(b).
H.2.5 Validation of Insight (3a)
Objective. As mentioned 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
67

---

Table 5: Results of the experiment supporting Insight (2b).
m = 2
m
64
m = 256
H = 2
H = 64
= 256
1.16
0.81
1.23
1.16
<le-6
<le-6
tasks, DP-free Transformer equipped with sufficient number of Attn heads H and FFN width m sufficiently capable. Moreover, there no need to use DP structure in Attn.
Setup. Specifically, we train single-layer DP-free Transformers with different H and and with DP or without DP to learn a sparse Boolean target function f*: f=(x)) == g (I44: 1556 T99) ==
E ReLU((W). (Iass, 256. Xg9))) for input sequence æ = (I1, ............ "I0000) E {+1] 1000, where
we generated by w (0, I3). Training proceeds for 10,000 iterations (1M samples) using squared loss and AdamW W with the same hyperparameters.
Results and conclusion. The final validation losses are shown in Table 6. The findings illustrate that a DP-free Transformer equipped with a sufficient И (32) and m (256) 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).
Table 6: Results of the experiment supporting Insight (3a).
H = 2, 16
H = 8, m
64
H = 32, m 256
with DP
0.21
0.04
0.01
without DP
0.17
0.11
0.02
H.2.6 Validation of Insight (3b)
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 without DP on the OpenWebTer dataset for 10,000 iterations (approximately IB tokens) on A A100, using cross-entropy loss and Adam 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).
Table 7: Results of the experiment supprooii Insight (3b).
L 111,H=
L=
H,
8,
8
with DP
5.796
5.374
4.994
without DP
5.830
5,486
5.274
H.2.7 Validation of Insight (4a)
Objective. This experiment aims 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, train single-layer, FFN-fre free. DP-free Transformers with log-type RPE lin- type RPE and varying numbers of Attn heads H. The target function involves a heavy-tailed memory kernel p(t) + --5.5 (*) = 1000 x.p( (100000 s) for any input sequence æ = (II, ... I1000) E {+1} 1000 Training processes for 10,000 iterations (IM samples) using squared loss and AdamW with the same hyperparameters.
Results and conclusion. The final validation losses are shown Table As shown in the table, to learn heavy-tailed memories, even single-head Transformer with log-type RRE can complete
68

---

perfectly (< 10 10. Conversely, Transformers employing lin-type RRE exhibit limited improvement even with up to 64 heads (0.19). This empirical evidence supports our Insight (4a).
Table 8: Results of the experiment supporting Insight (4a).
=
H
4
H 16
H
64
type=log type=lin
<le-5
<le-5
<lc-5
<le-5
0.73
0.68
1.16
0.19
H.2.8 Validation of Insight (4b)
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, train single-layer, FFN-free, DP-free Transformers with log-type RPE lin- type RPE and varying numbers of Attn heads H. The target function involves a heavy-tailed memory kernel p(l) e e5 I" (a) == Σ140 x (1000- s) for any input sequence æ = (I1, ... F1 E {=1] 1000 Training processes for 10,000 iterations (IM samples) using squared loss and AdamW with the same hyperparameters.
Results and conclusion. The final validation losses are shown in Table As shown in the table, to learn light-tailed memories, even single-head Transformer with lin-type RRE can complete it perfectly (< 10-"). Conversely, Transformers employing log-type RRE exhibit limited improvement even with up to 64 heads (5.3 x 10- This empirical evidence supports our Insight (4b).
Table 9: Results the experiment supporting Insight (4b).
H =
H =
4
H = 16
H = 64
type=log
9.1e-4
3.7e-3
2.6e-3
5.3e-4
type=lin
<le-7
<le-7
<le-7
<le-7
H.3 Practical Implications
Our theoretical insights and empirical evidence directly lead the following 8 practical implica- tions, such as the strategic selection of Transformer hyperparameters for specific tasks.
Implication (1a). (supported by Insight (Ia) and Experiment (1a))
For sequence modeling tasks with complex interrelations between memories, such many NLP applications, enhancing the number of layers more beneficial than increasing the number of Attn heads H and FFN width
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 single-layer Transformer, without need increase T.
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))
69

---

For sequence modeling tasks with complex correlations between memories, such as many NLP tasks, preserving the DP structure 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)) 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 TS's RPE and KERPLE (log)).
70

---

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

---

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

---

Answer:
[No]
Justification: The code or data of the experiments are simple and easy to reproduce following the description in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
public/guides/ Stwiiidee/ooSSSuiisstttt. soiooiiisss for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https: CCodeSubmiis
httpps.ccppubiic//eecc / ssi wwwinnsssnniiiiiioooooooo sesionnlocy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: In Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: the approximation error is deterministic and there is no need to consider the eгror bars here.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
73

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
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 compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https :tap::://neure http//eeurip...e cc cctpppbccc/tthiicccceeeeeeeeee
Answer: [Yes]
Justification:
We have confirmed that the research is conducted with the NeurlPS 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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
74

---

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

---

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


Reviews:
[{"review_id": "lktuTxFy9P", "reviewer": "Reviewer_xF1Y", "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.", "questions": "See weaknesses section.", "limitations": "The limitations of the paper are discussed in section 7", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "* The paper meaningfully contributes to the very relevant research line on theoretical analysis of transformers models. \n* The paper originally addresses important questions, such as the relative role of different components in the transformer architecture and the necessity of the dot-product attention, through a principled approach and in a controlled framework.\n* Generally the paper is very well written (modulo some sparse and minor typos) and pleasant to read.", "weaknesses": "* 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.\n* 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?\n* 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's recognition of our work and helpful comments. Below, we offer detailed responses to the reviewer’s questions:\n\n- **W1.** 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.\n\n    **Response:** Thank the reviewer for this helpful suggestion. In our paper, \"memories\" generally refer to the sparse \"tokens\" that sequence modeling relies on. For example, for the simplest Task I (sequence modeling with fixed memories), the number of memories is $M$, and they are located at fixed positions $t_1,\\cdots,t_M$ (which can be very large). In the revised version, we will introduce this concept in Section 1 to enhance clarity.\n    \n\n- **W2.** 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?\n\n  **Response:** We thank the reviewer for this insightful question.\n  - First, we would like to clarify that *the primary reason for not including Layer normalization (LN)* in our analysis is: LN is typically employed to accelerate and stabilize the training of Transformers, whereas our paper focuses on the issue of expressiveness. In fact, previous works about the expressiveness of Transformers have also omitted LN [1][2]. \n  - Now we discuss the *potential impact of LN on our results*. From an approximation theory perspective, LN introduces certain nonlinearity. However, our Transformers include FFN layers, which are already capable of effectively approximating nonlinear functions. Therefore, incorporating LN seems unlikely to significantly improve the network's expressiveness. Technically, LN introduces a coordinate-wise normalization operation, which cannot be analyzed using our current methodology. We leave this analysis for future work.\n\n- **W3.** 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?\n\n  **Response:** We thank the reviewer's insightful question. To clarify, let the dimension of a single token be $d$, the input sequence length be $T$ (where $T=\\infty$ in our paper) the number of memories be $M$ ($M\\ll T$), and the embedding dimension of Transformer be $D$.\n\n  - *Conjecture: increasing the embedding dim $D$ can effectively reduce the requirement on the number of layers but may not decrease the total number of parameters needed.* \n        \n  - *Theoretical evidence (Comparison with [3]).* In our paper, we consider embedding dim $D_1\\sim M d$, which is notably independent of the sequence length $T$ and almost the minimum embedding dim required to extract $M$ $d$-dim memories simultaneously. In contrast, in [3], the authors consider a large embedding dim $D_2\\sim T^2 d$ ($D_2\\gg D_1$ due to $T\\gg M$), and prove that, in this setting, 1-layer Transformers are sufficient to perform sequence modeling with sequence length $T$, whereas our results require multiple layers (for Task II).\n\n  - *Empirical evidence:* the \"scaling law\" (see Fig. 6 in [4]) partially supports this conjecture: 1-layer Transformes indeed demonstrate the scaling law. However, with the same total number of parameters, 1-layer Transformers (with larger $D$) slightly underperform compared to 6-layer Transformers (with smaller $D$). Additionally, [5] highlights that for solving iGSM math problems, given the same total number of parameters, deep Transformers (with smaller $D$) perform much better than shallow Transformer (with larger $D$).\n        \n  We will discuss this open issue in Section 7 in the revised version and leave further analysis for future work.\n\n[1] Yun et al. Are transformers universal approximators of sequence-to-sequence functions? (ICLR 2020)\n    \n[2] Bai et al. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. (NeurIPS 2023)\n\n[3] Jiang and Li. Approximation Rate of the Transformer Architecture for Sequence Modeling. (2023)\n    \n[4] Kaplan et al. Scaling Laws for Neural Language Models. (2020)\n\n[5] Ye et al. Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process. (2024)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GW10GGvD5l", "reviewer": "Reviewer_iDXk", "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.\nEach 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).", "questions": "- Please see some questions in the Weaknesses part. \n\n- What do you mean by rate $n$ in all the theorems ? Is there an optimal choice for $n$ ? \n\n- What is the main reason why you did not consider the SoftMax in section 4 ? \n\n- How does $C(n)$ behaves with $n$ ? \n\n- Could you approximate the model with specific precision with another Transformer which does not rely on specific precision ?  \n\n- 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": "Yes, the authors adequately addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and easy to follow. \n\n- The mathematical results are all supported with detailed and rigorous proofs.\n\n- Each Theorem is structured in the same way which eases the understanding of the whole paper. \n\n- The paper adresses the important question of approximation rates of Transformers in sequence modeling.\n\n- The paper establishes rigorous approximation results for Transformers on sequences modeling tasks. These results are significant and give insights on the role of the different Transformer components on their approximation capabilities. \n\n- The three problem formulations are clearly defined and commented.", "weaknesses": "- 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. \n\n- 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? \n\n- 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? \n\n- Paragraph l. 274 to l. 277 is unclear. When do you use this alternative in the rest of the paper? \n\n- Typo in l. 281\n\n- l. 282, I don't understand the notation for the lower bound on $m$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of our work and insightful comments. We answer the reviewer's questions in the following.\n\n- **W1.** Never consider transformers with all the bells and whistles.\n\n  **Response:** The reviewer is correct. Simplifying models appropriately in different settings helps avoid complex technical proofs and, more importantly, can accurately reveal the distinct roles and necessity of various components in Transformers. In the revised version, we will clarify this point in Remark 2.2.\n\n\n- **W2.** Embeddings dim.\n\n  **Response:** Thank the reviewer for this insightful comment. \n\n  *Comparison with [1]:* For the Transformer $f$ in our paper, we consider embedding dim $D(f)\\sim M d$. Notably, this is independent of the sequence length $T$ and represents almost the minimum embedding dim required to extract $M$ $d$-dim memories simultaneously. In contrast, the Transformer $g$ [1] considers a larger embedding dim $D(g)\\sim T^2 d$ ($D(g)\\gg D(f)$ due to $T\\gg M$) and prove that in this setting, 1-layer Transformers are sufficient for sequence modeling, whereas our results require multiple layers for our Task II.\n\n\n- **W3.** The number of heads.\n\n  **Response:** Thank the reviewer for this insightful question. The reviewer is correct that our required number of heads is due to the use of a specific RPE.\n\n  *Comparison with [2]*, which considers Transformer with absolute position encoding (APE) to study Task I. For a fair comparison, let $T:=\\max_{i} T_i$. In our work, the model $f$ requires at least $H(f)\\sim\\text{poly}(T)$ heads, with the number of position parameters $N_p(f)=H(f)\\sim\\text{poly}(T)$. In contrast, the model $g$ (using APE) in [2] has $N_p(g)\\sim Td$ position parameters, and $1$-head Transformers ($H(g)=1$) are sufficient for perform sequence modeling, whereas our model requires $H(f)\\sim\\text{poly}(T)$ heads. Therefore, model $g$ in [2] requires fewer heads than our model $f$. However, the relationship between the number of position parameters $N_p(f)$ and $N_p(g)$ remains uncertain.\n\n- **W4.** l.274-l.277, alternative.\n\n  **Response:** Thanks for this inquiry. To clarify, this alternative is only used in Prop. 4.3; all other results do not utilize this alternative.\n\n- **W5.** Typo in l. 281.\n\n  **Response:** We are grateful to the reviewer for identifying the typo. We will carefully read through the whole paper and correct all typos.\n\n\n- **W6.** l. 282, lower bound on $m$.\n\n  **Response:** We apologize for the confusion. For example, for type = lin, this lower bound should be $m\\gtrsim\\max\\Big\\\\{\\max_{i\\in[K]} ||g_i||_B^2,\\sum\\_{i=K+1}^M ||g_i||_B^2\\Big\\\\}$.\n\n- **Q1.** Optimal choice for $n$.\n\n  **Response:** Thanks for the inquiry. Given $T_1,\\cdots,T_M$, and $H$, there exits an optimal choice for $n$ that minimizes the error term $\\mathcal{E}_\\text{Attn}(\\text{Type})$, although calculating it may not be straightforward. \n\n- **Q2.** The reason for removing SoftMax in section 4 ?\n\n  **Response:** Thank the reviewer for this question. This is a technical operation to simplify the proof. Generally, we use the numerator of SoftMax in a series of attention heads to approximate the memory locations. Hence, we need to cancel the normalization in the SoftMax in each attention head by using $W_V$. However, in Sec.4, the existence of Dot-product results in the normalization in SoftMax depending on the tokens, which cannot be canceled by constant $W_V$. For more details, please refer to our proofs.\n\n- **Q3.** How does $C(n)$ behaves with $n$?\n\n  **Response:** Thanks for the inquiry. $C(n)\\leq A^n$, where $A$ is an absolute constant. Notably, although $C(n)$ grows exponentially with $n$, our approximation results remain efficient because the denominator term $H^n$ also grows exponentially, resulting in $\\frac{C(n)}{H^n}\\leq(\\frac{A}{H})^n$.\n\n- **Q4.** Could you approximate the model with specific precision with another Transformer which does not rely on specific precision ?\n\n  **Response:** Thank the reviewer for their insightful comment. First, we would like to clarify that FFN with specific precision is a technical trick to handle the discrete values of the time. \n\n  Let the two-layer FFN with specific precision be $\\tilde{f}:=[f]$. Notably, in our setting, we require an *exact representation* of $\\tilde{f}$ rather than an approximation. Note that $\\tilde{f}$ is a \"step function\", which is discontinuous at \"step points\". Thus, any FFN $g$ with continuous activation (such as ReLU and Sigmoid) cannot represent $\\tilde{f}$ because $g$ is continuous.\n\n\n- **Q5.** Do you think this is the \"optimal\" way ? And if so, what are the reasons behind it ?\n\n  **Response:** Thank the reviewer for this enlightening question.\n  -  We believe this approach is general and natural. As the reviewer commented, our main idea is to form $(x_t,x_{t-t_1},\\cdots,x_{t-t_M})$ using multi-layer Transformers. In this process, FFN layers and Attn layers work together, each performing their respective strengths: FFN layers approximate complex nonlinear memory functions, and Attn layers are responsible for extracting tokens at the memory locations. Additionally, our Experiment G2 and G3 verify these insights into the roles of FFN and Attn.\n  - However, it should be noted that we make minimal assumptions about the data. Therefore, we do not rule out the existence of better way for special problems. For example, if the data is distributed on a simple low-dimensional manifold $S$ with dimension $r$ ($r<d$), we only need to form $(P_S x_{t-t_1},\\cdots,P_S x_{t-t_M})$ using attention and apply an FFN on top of it, where $P_S$ is the projection to the manifold $S$. In this case, the embedding dim only needs to be $rd$, which is smaller than our $Md$.\n\n[1] Jiang and Li. Approximation Rate of the Transformer Architecture for Sequence Modeling. (2023)\n\n[2] Edelman et al. Inductive Biases and Variable Creation in Self-Attention Mechanisms. (ICML 2022)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UQIk64IIfM", "reviewer": "Reviewer_Fdzw", "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.", "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?\n\n2) The tightness of the bound is also uncertain. Could the authors provide a numerical result demonstrating the bound in a toy case?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper appears to be technically solid. It provides a detailed formulation of the problem and explores the expressive capabilities of Transformers across various tasks. Notably, it includes experiments in Appendix H to validate its theoretical insights. However, I have not verified the correctness of the proofs.\n\nThe paper contains some intriguing findings. I particularly want to highlight the exploration between dropout (DP) and relative position encoding (RPE), which I find especially interesting.", "weaknesses": "The key weakness of this paper lies in its unclear presentation of motivation, innovation, and contributions. The detailed reasons are as follows:\n\n1) 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.\n\n2) 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.\n\n3) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's recognition of our work and helpful comments. Below, we provide detailed responses to the reviewer’s questions.\n\n- **W1.** The motivation of this paper appears weak.\n\n   **Response:** Thank the reviewer for this inquiry.\n   While Transformer shows remarkable capabilities in long-sequence modeling, its underlying mechanisms remain poorly understood. Specifically, several key questions inspire our work, as detailed in l.15–l.30:\n  - How do the key hyper-parameters, for example, the number of layers ($L$), the number of Self-attention (Attn) heads ($H$) and the with of feed-forward network (FFN) layers ($m$), affect the performance of the Transformer network?\n  - How do Attn and FFN layers contribute differently to the overall performance?\n  - How does Dot-product (DP) self-attention work, and is the DP structure necessary?\n  - How efficient is positional encoding (PE) in modeling long-range correlations?\n\n  Furthermore, Appendix A contains a detailed investigation of related works on the expressive power of Transformers. To the best of our knowledge, our manuscript is the **first work** that comprehensively addresses **all the above questions** within the scenario of long-sequence modeling.\n\n\n- **W2.** The technical contributions of this work are not clearly presented.\n\n  **Response:** Thanks for this question. At a high level, our proofs belong to approximation theory, which inevitably involves the use of some standard approximation theory results, such as Lemma G.5 and G.6. However, the most critical step in our main theorems is based on constructive proofs. Our construction employs the specific structure of RPE, DP, and the modeling task, in contrast to many previous proofs such as those in [1][2]. In the revised version, we will add a remark to clarify our technical contributions.\n\n\n- **W3.** The necessity of this categorization and the relationships between these tasks are unclear.\n\n  **Response:** Thanks for this question. We would like to clarify the necessity and relationships of our three task categories:\n  - **Task Complexity and Relevance:** The three tasks exhibit varying complexity, with Task II and III being more complex than Task I. They are relevant to a wide range of application areas: Task I relates to sparse Boolean functions and the traditional n-gram model in NLP; Task II pertains to various NLP tasks, such as dependency parsing, sentiment analysis, part-of-speech tagging, and continuation writing; Task III includes feature representation in CV and wavelet analysis in classical signal processing. Please refer to Section 3-5 in our manuscript for more details.\n  - **Insights from Separate Analysis:** More importantly, analyzing these distinct tasks separately provides insights into different components of the Transformer architecture. For example, studying Task III reveals the efficiency of positional encoding (PE) in modeling long-range correlations, which can not be covered by studying Task I/II; Analyzing Task II illustrates how the number of layers and the number of Attn heads affect the expressivity of Transformers, which can not be revealed by studying Task I/III; Comparing the analysis of Task I and Task II shows when DP is necessary and how DP and PE work together.\n\n- **Q1.** Proof sketch for Theorem 4.4.\n\n  **Response:** Thank the reviewer for this question. Below, we provide a proof sketch for Theorem 4.4. Please refer to our proof route in l.967 to follow this sketch:\n  - Under the setting of Theorem 4.4, the memories are $K$-Adaptive, long but M-sparse (see l.200). We consider the case where $M>K+1$. For the initial $K$ memories, there exits a nested structure, while this nested structure does not exist for the $(K+1,\\cdots, M)$-th memories.\n  - In our proof, the nested structure within the initial $K$ memories mandates sequential processing in the first $K$ layers, one by one. Then, in the $(K+1)$-th layer, the remaining $M-K$ non-nested memory functions $t_{K+1},\\cdots,t_M$ are processed concurrently.\n  - In each layer, the FFN sublayer is tasked with approximating nonlinear memory functions, such as $t_i=g_i(X)$ and the readout function $f$, while the Attn sublayer is responsible for extracting the tokens from these memory locations, such as $x_{t-t_i}$.\n\n  In our revised version, we will include more proof sketches in the main text for clarity.\n\n- **Q2.** The tightness of the bound is also uncertain. Could the authors provide a numerical result demonstrating the bound in a toy case?\n\n  **Response:** Thank the reviewer for offering this constructive suggestion. We have conducted a new experiment to verify the tightness of our bound. Due to time constraints, we focus on Theorem 3.1 for the case \"type=lin\". \n  - **Objective.** For simplicity, we consider a single memory $T$. We aim to verify the following two bounds are tight: (i)*$H$ v.s. error*. Given a memory location $T$, the error $\\epsilon\\lesssim\\frac{1}{{\\rm poly}(H)}$; (ii) *$H$ v.s. $T$*. To achieve the same error $\\epsilon$, we need $H\\gtrsim\\exp(T)$ heads.\n  - **Setup.** We train single-layer DP-free Transformers with different numbers of heads ($H$) to learn a simple sparse Boolean function, which is within our theoretical framework. Specifically, the input sequence $X=(x_1,\\cdots,x_{10})\\in\\\\{\\pm1\\\\}^{10}$, the target output is $x_{11}^*=x_{10-T}$, where $T\\in[9]$ reflects the memory location.\n  - **Results & Conclusion.** The results are shown in **the PDF** in our **Global Response to All Reviewers**, supporting the tightness of our bounds: (i) given a memory location $T$, the error $\\epsilon\\sim\\frac{1}{{\\rm poly}(H)}$. On the other hand, to achieve the same error $\\epsilon$, we need at least $H\\sim\\exp(T)$ heads. \n\n\n[1] Jiang and Li. Approximation Rate of the Transformer Architecture for Sequence Modeling. (2023)\n\n[2] Edelman et al. Inductive Biases and Variable Creation in Self-Attention Mechanisms. (ICML 2022)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
### **Global Response to All Reviewers.**

- First, we sincerely thank all the reviewers for their appreciation of our results, i.e., theoretical analysis of the expressive power of Transformer for sequence modeling. Our analysis provides valuable insights (also supported by experiments) into the underlying mechanisms of Transformer components, including:
  - The distinct roles of the number of layers ($L$), the number of self-attention (Attn) heads ($H$), and the width of feed-forward network (FFN) layers ($m$). 
  - The different roles of Attn layers and FFN layers.
  - The functionality and necessity of dot-product (DP).
  - The efficiency of relative positional encoding (RPE) in modeling long-range correlations.

- We also express our gratitude to the reviewers for their comments and suggestions for improving our paper. In the revised version, we will correct all typos, include the proof sketches, provide complete experimental settings and results, and incorporate the discussions with the reviewers.

- The attached PDF reports a new experimental result addressing Reviewer Fdzw's Question 2 regarding the tightness of our bounds.

- We have addressed each concern raised by the reviewers through separate responses provided below.

Meta-review: 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.
Decision: Accept (poster)