State Space Models are Provably Comparable to Transformers in Dynamic Token Selection
Authors: Naoki Nishikawa
Taiji Suzuki
Venue: ICLR 2025 Poster (2025)
Keywords: State Space Model
Transformer
Nonparametric regression
Primary area: learning theory

Abstract: Deep neural networks based on state space models (SSMs) are attracting significant attention in sequence modeling since their computational cost is much smaller than that of Transformers. While the capabilities of SSMs have been demonstrated through experiments in various tasks, theoretical understanding of SSMs is still limited. In particular, most theoretical studies discuss the capabilities of SSM layers without nonlinear layers, and there is a lack of discussion on their combination with nonlinear layers. In this paper, we explore the capabilities of SSMs combined with fully connected neural networks, and show that they are comparable to Transformers in extracting the essential tokens depending on the input. As concrete examples, we consider two synthetic tasks, which are challenging for a single SSM layer, and demonstrate that SSMs combined with nonlinear layers can efficiently solve these tasks.  Furthermore, we study the nonparametric regression task, and prove that the ability of SSMs is equivalent to that of Transformers in estimating functions belonging to a certain class.

Published as a conference paper at ICLR 2025
STATE SPACE MODELS ARE PROVABLY COMPARABLE TO TRANSFORMERS IN DYNAMIC TOKEN SELECTION
Naoki Nishikawa
Taiji Suzuki
The University of Tokyo
The University of Tokyo
RIKEN ATP
RIKEN AIP
n
t di@mistt st.iss.ii wwt.ss....utt......o to..ooo..ac.....
ABSTRACT
Deep neural networks based on state space models (SSMs) are attracting signifi- cant attention in sequence modeling since their computational cost is much smaller than that of Transformers. While the capabilities of SSMs have been demonstrated through experiments in various tasks, theoretical understanding of SSMs is still limited. particular, most theoretical studies discuss the capabilities of SSM layers without nonlinear layers, and there is lack of discussion on their combi- nation with nonlinear layers. this paper, we explore the capabilities of SSMs combined with fully connected neural networks, and show that they are compara- ble to Transformers extracting the essential tokens depending on the input. As concrete examples, single SSM layer, and demonstrate that SSMs combined with nonlinear layers can efficiently solve these tasks. Furthermore, we study the nonparametric regression task, and prove that the ability of SSMs equivalent to that of Transformers estimating functions belonging to a certain class.
consider two synthetic tasks, which challenging for
INTRODUCTION
Foundation models based on Transformers have achieved remarkable success in various sequence
modeling tasks such as natural language processing (Vaswani et al. 2017), computer vision (Doso- vitskiy al. 2020), and speech recognition (Radford et al. [023). The superior performance of Transformers is attributed the self-attention mechanism, which enables the model to aggregate information from the input sequence.
In contrast to its success, the self-attention mechanism has a potential problem that it requires large amount of computation and memory. To deal with this issue, many studies have attempted to develop efficient models that can replace Transformers. Among them, State Space Models (SSMs) have gar- nered considerable interest recently. One advantage of SSMs is that the output can be computed with a significantly small time using convolution via the FFT algorithm or recursive computation. Based on the original SSMs, many improvements have been proposed, such HiPPO-based in- tialization (Gu et al. 2021) and architectures using gated convolutions (Fu et al. 2022 Poli et al., 2023
Networks based on SSMs have achieved high performance in various applications such as gene analysis (Nguyen et al. 2024), audio generation (Goel et al. 2022) and speech recognition (Saon) et al. 2023). On the other hand, some of the recent studies pointed out the limitations of SSMs to solve tasks. For example, Merrill al. (2024) show that SSMs cannot solve sequential problems from the view of computational complexity theory. Additionally, Jelassi et al. (2024) demonstrate that SSMs are inferior to Transformers solving the task to copy the input sequence.
One of the major differences between SSMs and Transformers lies in how they aggregate infor- mation from the input sequence tokens. The output of Transformers is computed as a weighted sum of the input tokens, where the weights are determined depending on the input. This allows the Transformer to dynamically determine which tokens to extract based on the inpur, leading to its high performance. SSMs also compute their output weighted sum of the input tokens, but the weights do not depend on the input. Therefore, a single SSM layer cannot perform dynamic token extraction, which limits its capability.

---

Published as a conference paper at ICLR 2025
Nonlinear Φ1 Ø2
SSM
Transformer
y/
2
(Z,))
V/
A -..u.... 24
Comparable
j
Data-independent
Data data-dependent
p 1
u
V
W
t
u
7
1
7
V
4
W
7
t
9
7
3
5
9
3
6
4
2
S
9
a 6 h s
d
w
s
3
a
6
h
4
s
3
d
9
1 s
3
Both models can switch the tokens they pay attention to.
Figure 1.1: Conceptual illustrations of our theory. The abilitics of SSMs are said to be limited since their filter is not data-dependent. However, when combined with nonlinear layers, SSMs are compa- rable to Transformers in terms of dynamic token selection. Indeed, experiments on associative recall tasks show that SSMs capture the important tokens in the sequence depending on the input, which is similar to the behavior of Transformers. The heatmap in the figure represents the importance of the token when the model predicts the output. Note that these are artificial figures, but the actual results of the experiments.
However, in typical architectures. SSMs repeatedly applied alternately with fully connected neural networks (FNNs), similar to the attention mechanism. This raises the following question:
Can SSMs combined with FNN layers perform dynamic token selection similar Transformers?
This paper provides positive theoretical result for this question. Specifically, we demonstrate that SSMs, when combined with FNNs, can exhibit dynamic token selection with performance equiva- lent to Transformers.
To demonstrate the claim, we consider two synthetic tasks (input copying and associative recall), and non-parametrie regression problem. Input copying is the task of generating the sequence as the given input. Jelassi et al. (2024) intensively studied this task and showed that a single SSM layer underperforms compared to Transformers in solving this task. In this paper, show that two- layer SSMs combined with FNN layers can achieve performance comparable to Transformers in this task. In associative recall, the models as input. We demonstrate that the performance of SSMs combined with FNN layers is better than that of SSMs without FNNs shown in Massaroli et al. (202)). As for the non-parametric regression, we consider the estimation of piecewise 7-smooth functions, which is defined in Takakura & Suzuki (2023). Takakura Suzuki (2023) shows that Transformers can efficiently estimate functions this class. We show that SSMs combined with FNN layers can achieve the same convergence rate the rate for Transformers shown in Takakura & Suzuki (2023).
required infer the answer from a pair of words provided
In solving the three problems above, the models have to determine which tokens extract based on the input data. Therefore, these results imply that SSMs possess dynamic token extraction capabil- ities comparable to Transformers. We give some examples of associative recall task in Figure I.I We trained SSMs and Transformers on the task and draw heatmaps to show which tokens the trained observe that both models pay attention to similar parts
models focus From the figures, of the input. This verifies that SSMs possess dynamic feature extraction capabilities comparable to Transformers. See Section 3.2 for more details of the associative recall task.
The contributions of this paper are summarized as follows:
1. We theoretically study the abilities SSMs to solve two artificial tasks, input copying and asso- ciative recall, and prove that SSMs FNNs can solve these tasks efficiently (Section 3.1 3.2).
2. To prove the above results, we provide a theoretical result that shows SSMs combined with FNNs can mimic the dynamic token selection mechanism of Transformers (Section (3.3).
3. As general example, also consider the cormmaraettric regression for the function class defined in Takakura & Suzuki (2023), and demonstrate that SSMs can achieve the same estimation error Transformers (Section
2

---

Published as a conference paper at ICLR 2025
Other related works. Some studies have theoretically investigated the abilities of SSMs recently. For instance, Waan & Xue (2023) show that SSMs are universal approximators for continuous eqquence-to-sequenee functions. Moreover, Cirone et al. (2024) studied the abilities of SSMs using rough path theory. Furthermore, Aloono et al. analyzed the abilities of SSMs with the use of the control theory. However, these studies (i) do not give quantitative evaluations comparing SSMs to Transformers, and/or (ii) only consider SSM layers without nonlinear layers.
There are some previous studies for the estimation error bound for non-parametric regression, for example, Suzuki (218);; SchmiddtHHibber 2020); Suzuki & Nitanda (202T) for FNNs and Okumoto Suzuki (2021) for CNNs. These studies do not consider the case where the positions of essential
features change depending on the input. The function classes with piecewise smoothness are also considered in Petersen & Voigtlaender (2018) and [maaizumi Fukumizu (2019). They do not consider anisotropic smoothness or sequence inputs, whereas we consider such situations.
Notations. For 1 E (1 S r). let [I] be the set {I,...,() .I. and [ r] be the set (l...., For set S R and d, E N, let Sdx(-V:0] == (s-v,,..., so] 8, 54) and let Suxc0 = {[..., 8-2; 8-1, sol 8 E 5 For F: : Ω + R², let |l = supxen [ For a matrix A, let |Allo = ((( A. * O}}. For X E Rdxx X1. E IR xx represents its i-th row.
2 THE DEFINITION OF DEEP NEURAL NETWORKS WITH SSMS
In this section, we provide the formal definition of deep neural networks with SSMs. State space models with the input [uo]p=- the latent vectors [2=]|=-1 and the output [yo] (Ur R, R. yt E I), are represented as follows:
Ti+1 Ar, + Bu,, Ve = Co, + Due (L (1= (L=-L...,--))
where A,B,C, E TR are learnable parameters. Then, the output Ye can be written explicitly as _ (CA' D6,_n) (0k_n)_u un. By setting h, == CA'B + DŌ, and h = [he] we can rewrite the output as y/ = (h * u): = -t using convolution operation *, If the filter [hr]/-n is precomputed, the output can be computed with OLL log L) time complexity using FFT algorithm, which is much faster than the computation cost Transformers, OLL²).
In this paper, we consider the architectures consisting of the following three types of layers: (i) FNN layers, (ii) convolution layers, and (iii) an embedding layer.
(i) FNN layer An FNN with depth L and width W is defined as f(x) = (Amn(-) + by) where 77 ReLU, and A; E xd b, E Rd+++ with max; d, S W. Then, define the class of FNN with depth L, width W, norm bound B and sparsity 5 by
(Air + +b),
V (L, WL, := { max f1 look s B, Σ |A.lo + 11b.11 S $8
(ii) Convolution layer Next, we define the convolution layers. Let W E R be learnable weights, and D be the embedding dimension. Then, given the input X E Dxx, the output of the convolution layer g: Dxxe Dxxx with window size U is computed
2Tj a1,k U+1
2 02
g(X) = * (WX),
HaJ = C1, Co8
02 sin
U +
where H (xU++1 is filter controlled by learnable parameters C1 C22 01, a2 E R., The oper- ator DxU+1) x RDxx -> TR Dx represents element-win convolution. Note that assume the finite window size U, i.e., the output of position -i (i E Nxo) is computed with the tokens at position- -i,..., -i- U. Such setting is also considered in the analysis of Transformers (Takakural & Suzuki 2023). Then, we define the class of convolution layers with window size U, embedding dimension D and norm constraint B by
D,B) = {g max [1 lbo || |callso 1c22ll < B}.
The definition of the convolution filter includes several important settings. First, our setting includes the case where the convolution filter h, CA'B DØ, of ordinary SSMs. Indeed, by
3

---

Published as a conference paper at ICLR 2025
constructing the parameters A, B, C, D in the filter appropriately, we can obtain the same architecture as the convolution layer we consider (see Appendix Afoor the details). Moreover, our setting includes the filter used in Hyena (Poli et al. 2023), in which the filter is defined by neural networks with sin- activation.
(iii) Embedding layer
Finally, the embedding layer with embedding dimension D is defined as Emb(X) [ + =2
where Ej E Dxd and Eg E RD are learnable parameters.
We first feed the sequence into Emb, and then alternateyy apply convolution layers and FNN layers. Note that the FNN layers are applied in a token-wise manner. Thus, we define class of deep neural networks using SSMs, denoted as S, as follows:
Ji E VI,, W, B),
S.M.U.D.LWWSSBR
fM gMs ..... f o 91 o Emb
9i E C,U,D,B)
|| S B, 12 S B.
We remark that the number of parameters of the model is (MM + D2)), and does not depend on the window size U, since the parameters are shared among the tokens.
3 SYNTHETIC TASKS: INPUT COPYING AND ASSOCIATIVE RECALL
In this section, we consider the two tasks of (i) input copying and (ii) associative recall, and show that SSMs combined with FNNs can solve these tasks efficiently. In both of these tasks, the position of the important token is different for each input. Therefore, the fact that SSMs can solve these tasks suggests that SSMs have dynamic token extraction capabilities comparable to those of Transformers.
Throughout this section, we assume that an input is given as sequence words in the dictionary W, where W is finite set. Each word in the sequence is first converted into [W| -ddmenniioa one-hot vector. Then, the tokens are transformed to D-dimensional vectors by the embedding layer, and fed into subsequent convolution layers and FNN layers. Thus, obtain a sequence of D-dimensional tokens as a model's output. We consider the setting where the model generates sequences by autore- gressively outputting the words, i.e., next-token prediction. To do this, we introduce an additional decoding layer, which we denote by Dec. This layer has learnable parameter WDee R>X/W and linearly transforms the final token of the model's output into a vector in R RRW Then, the word corresponding to the largest component this vector is regarded as the model's prediction.
3.1
INPUT COPYING
The input copying is a task in which the model is required to output exactly the same sequence as the input via autoregressive inference. As an example, consider the situation where the model receives the input sequence " "(BOS> с d b e (COPY)", where a, b, c, d, e are the words in W, and (BOS) and (COPY) are special tokens, which are also included W. Then, the model first needs to output "c". Next, the model receives the input ((BOS) с d b (COPY) c"., and the model required to generate "a". This process repeated until the number of tokens the model generates becomes equal to the number of words in the input sequence.
To evaluate the model for this task, we consider the probability that the model generates the correct sequence for a certain input distribution. More precisely, suppose that input sequences are given in the form of " (BOS) 21 x22 ... zy (COPY)", where T1, .2...., zy are independently generated from the uniform distribution generated by the model, and evaluate the model by the metric erry defined as follows, which mea- sures the probability that the model does not correctly copy the input sequence:
W \ { (BOS), (COPY>} }. Then, set y/..... yv the sequence
erry (( yy)) # (21 (21....zy))
Jelassi et al. (2024) intensively studied the capabilities of SSMs and Transformers to solve this task. They theoretically showed that Transformers with (llog(V/e) log [W]) parameters can achieve erry < c. In their proof, they leverage the dynamic token extraction ability of the attention mech- anism. More specifically, they demonstrate that Transformers can solve the copying task by look- ing up the n sequential tokens that match the last n tokens. In addition, they discuss the lower bound of the accuracy of SSMs, and showed that SSMs need O log (W]) memory size achieve
4

---

Published as a conference paper at ICLR 2025
errv I 1/2. These results suggest that single SSM layer is inferior to Transformers in terms of the dynamic token extraction abilities.
In contrast to these results, we investigate the case where nonlinear layers placed before and after the SSM layer, and obtain the following result.
Theorem 3.1. For any > there exists an SSM À ES,, D, I,W, B) with
M 2, UV D, L, W, S, log B log - log" 42 V log [W], and decoding layer Dec with [e I 1 such that supvrg[]] CITY' C.
This result shows that, two layer SSMs combined with FNNs, we can achieve the error with poly log(e (1,, V, (VV]) parameters, and avoid the necessity of the memory size increasing linearly with V.
In the proof of this theorem, it essential that there are FNN layers before and after the second SSM layer. As will show later in Lemma 3.3, the SSM combined with the preceding and following FNN layers has the ability to extract tokens based on the inner product of keys and queries, similar to Transformer, Delassi et al. (2024) demonstrates that two-layer Transformer copying task. Thus, by replacing the attention layer with FNN + SSM + FNN, the above theorem
solve the input
can be proved. The detailed proof can be found in Appendix H
3.2 ASSOCIATIVE RECALL
Next, we investigate the task called associative recall. this task, we assume that the set of words W is divided into two disjoint sets Wkey and Wvalue The input sequence is given in the form of "kı U1 ... kv uy q", where ki,.... ......,ky ky E Wkey (k; & kj if o j), UI...., uy E Wvalue and E Waey matches one of the K; [V]). Then, the model is required to output the corresponding eú for the given kg For example, if the model receives the input "c 2 5 needs to output "5".
a", the model
Similarly to the input copying task, this task also requires the model to dynamically extract the important tokens. Indeed, solve this task, the model needs focus on three tokens: (i) the last token of the input, (ii) the token with the same word the last one, and (iii) the token that follows (ii). Since the locations of (ii) and (iii) change depending on (i), the model needs to pay attention to different locations depending the input.
We proved the following theorem, which shows that Opoly log([W])) parameters are sufficient to solve the associative recall task when using SSMs combined with FNNs.
Theorem 3.2. There exists an SSM F S(M, U, D, L, W, S, B) with
M 2,
= D, L,, W, S, log B S log 13 ((W),
and decoding layer Dec with [e S 1 such that, for any input sequences of associative recall task, the model generates the correct output.
Massaroli et al. (2024) showed that based SSMs can solve the associative recall task with O(VW log" [W]) parameters. In contrast, we proved that we require only Oppoly log (W]) pa- rameters, thanks to the nonlinear layers. This indicates that combining SSMs with nonlinear layers can improve the dynamic token extraction ability of SSMs.
In this theorem well, the essence of the proof is the ability of the SSM with preceding and
following FNN layers, as described in Lemma 3.3 The proof can be found in Appendix H
3.3 SSMS MIMIC ATTENTION MECHANISMS TO SELECT IMPORTANT TOKENS
In this subsection, we discuss why SSMs combined with FNNs can perform dynamic token selection similar to Transformers.
The dynamic token selection abilities Transformers stem from the attention mechanisms. Indeed, attention mechanisms compute the weighted sum of the values (i.e., projected input tokens), where the weights are determined based on the input. The weights are computed by applying the softmax function to the inner product between keys and queries. This means that the attention mechanism prioritizes the tokens where the key and query have a high inner product. The following statement shows that SSMs combined with FNN layers mimic this functionality.
5

---

Published as a conference paper at ICLR 2025
Lemma 3.3 (Dynamic Token Selection by SSMs).
Suppose that the input sequence X is given by
q
X = K-v
k-1 ko
E IR (2
V-v
v-1
20_
where q, ki Rdd and U1 E Rd with Iall I 1, 1.11kylla, I 11551l0 =1
Ler
b = q"k, (j -V...... and j = arg maxx= -V..... (l-- Suppose that, for any j E [-V 0 H holds μ4 Mj 8 for some 8 0. Then, for any e O, there exist FNN layers f1.f2 E U, and a convolution layer g E C,U,D, B) with
U = D D= d 8-2 (log² E- +log" v),
L S d' 8- (log" 1 +og voogv) v), W x d (log² [ + log v),
5 d 8- (log c- + log v), log B S d 8-2 2 (log"c+ E log v).
such that l190 uz- 11x S where yyv...., y-1, yol f2 o fi(X).
We provide the proof in Appendix G From this theorem, can that SSMs preceded and followed by FNN layers can dynamically change the positions of tokens to focus on based on the value of the inner product between the key and query, similar to the attention mechanism. Thus, SSMs demonstrate dynamic token selection abilities similar to Transformers.
4 NONPARAMETRIC REGRESSION PROBLEM
In this section, we consider non-parametric regression problem with sequence inputs, and show that SSMs are comparable to Transformers in estimating piecewise y-smooth functions. As we will explain later, in functions belonging to this class, the positions of important tokens vary depending on the input. Therefore, the dynamic token selection ability is essential for estimating a piecewise 7 smooth function. In Appendix we provide a visual explanation of the motivation for considering this class of functions.
Due to the technical convenience to analyze the estimation error, we consider the setting where the output of the network is bounded. For this purpose, assume that the output of the model is fed into the function clip, defined by clipæ(2) == max {-R, min { R, =] Since clip, can be implemented by the FNN with depth 1 and width 2, this assumption is not far from the practical setting. Furthermore, to predict real value, the final token (i.e., index 0) in the sequence output by the model is regarded the predicted value. We define the class of clipped networks S' by S' S'(M, U. D, L, W, S, B) = {(clip F)o F E SEM, U, D, L, W.S.B),
4.1 PROBLEM SETTING
We consider the situation where the input X == [0:1__>>0 E dxdx0 a sequence of d-dimensional tokens, and they are generated from a probability measure Px on ((0. 1] (i 1jdxc))). In the following, denote Ω = supp Px and define the norm 11:11p, by |l 1l
1/p
As in the usual nonparametric regression setting, suppose that we observe n i.i.d. inputs x(i) ~ Px (i = 1,..., n) and the corresponding outputs (() E R generated by y = (x(() + g(), where g(0) E R is the iidd noise generated from o0 (o > 0). We further assume that (g(1)) 1t=1 is independent of the inputs [x(]] y Given the pairs of inputs and outputs {(X() y()) we obtain the estimator F² of the target function F through empirical risk mini- mization:
1 Σ (y ((x))))))))
= arg min FES
where S' is the class of networks that we defined above. To measure the statistical performance of the estimator F, we utilize mean squared error (MSE) defined by
R(F F. F9) = E | - F (X) 2.Px

---

Published as a conference paper at ICLR 2025
where the expectation is taken for {x())
I==1 and {E(0)) i==1'
4.2 PIECEWISE 7-SMOOTH FUNCTION CLASS
To compare the estimation ability of SSMs with that of Transformers, we assume that the target function F belongs to the function class called piecewise ?-smooth. The function class was intro- duced in Takakura & Suzuki (2023), and they showed the estimation error bound of Transformers for the functions in the class. In this function class, the importance of the tokens (or coondinates) is characterized by the smoothness of the function. We describe the details in the following.
y-smooth function class. Before introducing the piecewise y-smooth function class, we first de- fine the 7-smooth function class, which was first proposed by Okumoto & Suzuki (202T). This
function class can be seen as an extension of the well-known function spaces, such as the mixed- Besov space and (anisotropic) Sobolev space.
Zdx00 we define Vri : 10, + I by Vry (2) = { First, for E 20
V (2co((21))))))) (ry S 0), Vi 2n
(ryj > 0), and dh+ [0, 1]dx00 + R. by 4/ (X) = II. I1 thro (Xtj). Then, ( fehrreeaxx forms a complete
(
orthonormal system of I,2 (10, 1jdxo)), Therefore, any f E (2, 1j0x00) can be expanded f
Erezgro (f,4)) 1h. For E No Ndx00 we define
8.)
Σ
(f. vr-
rE20* 122 Isn, <2"
Then, we define the 7-smooth function class as follows.
Definition 4.1 (y-smooth function class), For a given Noxx0 + R which is monotonically non- decreasing with respect each coordinate and p 2 2, 1, we define the -moohhh function space as follows:
(1, 11xx000 = {s (10, x 11ffl < <00
where the norm IIf is defined as | = (Evenga 20x (16, )² define the finite dimensional version F7,0 (10, 1jdxl) for I E N in the same way.
1/0
We also
Note that (f) can be as the frequency component of with frequency |rael 2% for each coordinate (i. Therefore, we can interpret that y controls the amplitude of each frequency component through weighting the term ||ō, (f) in the definition of the norm I1-11 pp.""
In other
words, if (ss) is larger, the norm of frequency component (f( is smaller.
As special case of 7, we consider the following two types of smoothness:
(a.
(Mixed smoothness),
(s) max (arjsts j [d].j E Z}
(Anisotropic smoothness).
where a E Rd is the smoothness parameter, which determines the smoothness of the function for each coordinate. To provide the intuition of the smoothness, let consider the extreme case, ag + oo for (i,j) with Sij * 0. Then, it holds 7ss) + oc, both for mixed and anisotropic smoothness, which implies 27(*) -> co. This indicates that a strong "penalty" is imposed on the component (f) and the function f does not have the frequency component Sij along the direction of (i.7). Since the norm |I/l|>;, has to be finite, it holds (1).()) - 0. This means that the function has to be smooth for the input coordinate (i,j). Therefore, large aı implies that the function is smooth towards the coordinate (i.j), and this indicates that the value of function does not change much for the input coordinate (i,j), which means that X,y is not an important feature. In contrast, small a;j implies that the coordinate Xi, is an important feature.
As we stated above, the function class (1,, 1jdx=o) can be seen as an extension of some well- known function spaces to the infinite-dimensional setting. Indeed, if Px is a uniform distribution on [0, 1| and p oc, then Fr Pp,0((0 1|2x1) with mixed smoothness is equivalent the mixed-Besov space. Moreover, if Px is uniform distribution, then the anisotropic Sobolev space is included in the unit ball of F2 with anisotropic smoothness.

---

Published as a conference paper at ICLR 2025
Piecewise y-smooth function class. Now, ready to define the piecewise ymsoohhh function class. The functions in this class have different smoothness depending on the input unlike y-smooth functions. Therefore, the models have to choose appropriate tokens to extract depending the inpur when estimating a function in this class.
The rigorous definition of piecewise y-smooth function class is given follows. In the following, we denote x_; = --..,,----1 1. x for i E N and X = , 1,
Definition 4.2 (Piecewise 7y-mooohh function class). Let / be function that belongs to Po,o(1, 1)dx which we call the importance function. Additionally, let πx [-V : :0] + (-V
be the map that sorts the indices E [-V : 0] in ascending order of the importance ((X;), i.e., (-x) < ... < 14(X.. (x)
Then, we define the map IT: |0, 1j + [0, (0,1jxx[-V by
(I)) == [ (-V) xx xx)
Then, for 2 2,0 2 and y Nox00 - IR, the function class p7,, (10, 1jdxcc) with piecewise
y-smoothness is defined as follows:
( [
(-= =
E (2, 11911p < <00}
where the norm |19l|p p.o
is defined by IIall p..0 = (Esentx-va)) 200(0 MI p.px
In simple terms, when an input X [..., ., I-V I
V..,..,, is fed into a function g E ([, 1)dxoo),
the tokens x .-v..... are first sorted in ascending order of the importance yu(X v), .... (Xo). and the resulting sequence [V)x(-V))--. - -xx is fed into the 7-smooth function f. The impor- tance of each token F is determined by the preceding tokens, i.c., x- T-i-1.... Since the order of the sorted tokens changes depending on the input, the smoothness of the function g = foll E GT differs for different inputs.
In the definition, tokens with higher importance are placed closer to index 0 after sorting. In the latter subsection, assume that the smoothness of the function f for coordinate is smaller for the tokens with indices closer to O, which implies that the tokens with higher importance are more essential estimate the function f.
As in Takakura & Suzuki (2023), we assume that an importance function is well-separated, i.e., for some constant c, 3 > O. J satisfies (x )) 2 p((xxx(i-1)) + ci ci-# for any X E Ω2x, This implies that X satisfies u(X=;) = (((-;)) -)) (i of j) with probability zero. A similar assumption can be found in the literature of statistics such as Hall & Horowitz (007)).
4.3 APPROXIMATION AND ESTIMATION ABILITY OF SSMS
In this subsection, we show the theoretical results the ability of SSMs to approximate and estimate the function in the piecewise 7-smooth function class.
To establish the theories, we make the following assumptions, all of which are also imposed in Takakura & Suzukil (2023).
Assumption 4.3. The true function F belongs to Ti. where is mixed or anisotropic amiotrropic.moottnnees smoothness.
Moreover, F and the importance function μ satisfy the following conditions:
(i) | |1
Ro, ||11157, 1, || S 1 for some constant Ro > 0.
(ii) For the smoothness parameter a, it holds aij = 2(log((il + +)) for μ E Fy.o and a:j = )( for F E Eg..0 where a > 0 is constant. Moreover, it holds ||albuta S 1 for both and F where ||a||an= == sup, jaa² and 0, the j-th smallest element of a. (iii y is mixed smoothness, we assume ā1 < āzz-
Remark 4.4. The assumption ||a|| wtt < 1 implies that the j-th smallest element of smoothness parameter a increases polynomially with respect to j. which indicates the sparsity of the important features. This assumption is natural in real-world applications, as we check in Section [ Moreover, the assumptions a; = (llog(IJ] 1)) and a; 2(j mean that the token placed far from the final token is less important. Note that the condition agj 2(j**) ) for F f II G7 is imposed on the function f Fr and the input of the function is sorted by the importance.
8

---

Published as a conference paper at ICLR 2025
Then, have the following theorem the approximation ability of SSMs for piecewise y-smooth functions.
Theorem 4.5. Let F be a function satisfying Assumption 4.3 Then, for any T > 0, there exists
SSM E (M, U, D, L, W,S, B) with
M S T2/a U =V DST log" V, L LS T log" V,
(4.1)
W S 2T/a 700.0 log V, s 2 Team log V, log S T log V,
such that p - /
S 2- Here, Ca,3 a constant depending on a and 3 such that Ca.B S
2,
5 + 2/a + 53/a.
This result reveals that the number of parameters to achieve the emror is O((1/E)TT poly log(L/e, V)), which is the same as that of Transformers shown by Takakura & Suzuki (202)) Similarly to T. Theorem 3.2 to prove this theorem, we utilize the similar argument as Lemma 3.3] which establishes the dynamic token selection ability of SSMs combined with FNNs. The detailed proof can be found in Appendix
Using the approximation theory above, we obtain the following results, which state the estimation ability of SSMs for piecewise y-smooth functions.
Theorem 4.6. Suppose that the target function Fe satisfies Assumption 4.3 Let al āg for mixed
smoothness, and at = -Eie a, a for anisotropic smoothness. Moreover let F be an ERM estimator in L,MUUDDL, W. S, B), with M,U, L, S, B defined as (4.1 for T = 20 41 Then, holds
3et
(log (logn)* ) log" 13 V, where La,g is a constant such that <a, S 21 + 10/a + 20/3/a.
R(F, Fo) S 2n
The proof can be found in Appendix J We can see that the convergence rate with respect to matches that of Transformers shown in Takakura & Suzuki (2023). This indicates that SSMs possess the ability to select important tokens based on the inputs, similarly to Transformers. Moreover, since the estimation error bound depends on V with only poly-log factor, if V = poly(n), the estimation error rate does not change up to poly-log factor. This also aligns with Transformers and shows that, even when estimating functions that depend on long ranges of the input sequence, SSMs are as efficient as Transformers. Overall, we can conclude that SSMs can estimate the function in the piecewise "msshoohh function class with the same efficiency as Transformers.
5 EXPERIMENTS SPARSITY OF IMPORTANT TOKENS
In the tasks we theoretically study, the number of essen- tial tokens in the sequence is small. We conducted simple numerical experiments and confirmed that (i) such spar- sity of important tokens also holds in real-world tasks, and that (ii) SSMs can indeed extract these important to- kens depending on the input.
Correct probability
0.8
We use the dataset of DNA base sequences in Genomic Benchmark Dataset (Grešová al. 2023). The base se- quences are treated as sequences where each nucleic acid
tanget sequerces
other sequences (mean)
other seqquences (mir)
considered a single token, and we consider a binary classification task based on the role of the base sequences. We employ the pre-trained Hyena provided by Nguyen al. (2024), and fine-tune it on the dataset.
200
sce
Number of masked tokens
Figure 5.1: The transition of the prob-
ability of correct classification when repeatedly mask the input tokens.
To investigate which tokens the model focuses on for clas- sification, we selected correctly classified data sample (we refer to this as the target sequence) and masked unimportant tokens one by one. More precisely, we repeatedly masked the token that causes the smallest decrease in accuracy when masked. The change in accuracy is shown by the blue line in Figure [..]] We can see that, even when most of the tokens are masked, the model is still able to classify correctly. This indicates that the important tokens in the input sequence are sparse.

---

Published as a conference paper at ICLR 2025
Furthermore, investigate the ability of SSMs to dynamically extract important tokens, exam- ined how the accuracy changes by masking the tokens at the same positions as in the target sequence for other data samples. The average and minimum changes in accuracy are shown with the red and green lines, respectively. The figure shows that although the accuracy was high before masking, decreases more tokens masked. This demonstrates that the positions of important tokens vary across different data samples, and that SSMs are able to dynamically extract important tokens based on the input to perform correct classifications.
CONCLUSION
In this study, we theoretically investigated the capabilities of SSMs compared to Transformers. Specifically. we focused on the ability dynamically extract tokens based the input, which is an essential strength of Transformers, and clarified that SSMs combined with FNN layers can emulate such mechanism. Using this insight, we analyzed three cases: input copying, associative recall, and nonparametric regression, and showed that SSMs exhibit performance comparable to Transformers.
Limitations and future work We studied approximation and estimation abilities of SSMs to solve the tasks, and did not discuss whether SSMs can be optimized efficiently. Analyzing how the op- timization algorithm works for SSMs is a possible direction for future work. Additionally, we did not investigate the other types of efficient sequence models, such SSMs with data-dependent filters (like Mamba (Gu & Dao 2023)) and linear attention (Katharopoulos et al., (020). Future re- search could focus on the comparison of those models and SSMs. Moreover, we did not consider specific parameterization known in practical applications of SSMs. Specifically, we did not impose constraints such as A being diagonal matrix in the filter CAt-BB + D8,_n- Instead, as described in Appendix A, we considered cases where A is a block diagonal matrix. It remains future work to explore how we can constrain the structure of A to solve the tasks.
ACKNOWLEDGMENT
NN was partially supported by JST, ACT-X (JPMIAX24CK). TS was partially supported by JSPS KAKENHI (24K02905) and JST CREST (JPMICR2015).
REFERENCES
Dimitris Achlioptas. Database-frieet friendly random projections: coins. Journal of computer and System Sciences, 66(4):671-687, 2003.
with binary
Carmen Amo Alonso, Jerome Sieber, and Melanie Zeilinger. State space models as foundation models: A control theoretic overview. arXiv preprint arXiv:2403.16899 2024.
Nicola Muca Cirone, Antonio Orvieto, Benjamin Walker, Cristopher Salvi, and Terry Lyons. Theo- retical foundations of deep selective state-space models. arXiv preprint 4xXhv:2402.19047, 2024.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 218-248225 255. leee, 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An im- age is worth 16x16 words: Transformers for image recognition at scale. In International Confer- ence on Learning Representations, 2020.
Daniel Y Fu, Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re. Hungry hungry hippos: Towards language modeling with state space models. In The Eleventh International Conference Learning Representations, 2022.
Karan Goel, Albert Gu, Chris Donahue, and Christopher Ré. It's raw! audio generation with state- space models. In International Conference Machine Learning, pp. 7616-7633. PMLR, 2022.
10

---

Published as a conference paper at ICLR 2025
Katarina Grešová, Vlastimil Martinek, David Čechák, Petr Simeček, and Panagiotis Alexiou. Ge- nomic benchmarks: a collection datasets for genomic sequence classification. BMC Genomic Data, 24(1):25, 2023.
Albert Gu and Tri Dao. Mamba: Linear-ting sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00772. 2023.
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2021.
Peter Hall and Joel L Horowitz. Methodology and convergence rates for functional linear regression. 2007.
Masaaki Imaizumi and Kenji Fukumizu. Deep neural networks learn non non-smooth functions effec- tively. In The 22nd international conference on artificial intelligence and stafisfics, pp. 869-878. PMLR, 2019.
Samy Jelassi, David Brandfonbrener,, Sham M Kakade, and Eran Malach. Repeat after Trans- formers are better than state space models at copying. arXiv preprint arXiv:2402.01332, 2024.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers rnns: Fast autoregressive transformers with linear attention. In International conference on ma- chine learning, pp. 5156-5165, PMLR, 2020.
Stefano Massaroli, Michael Poli, Dan Fu, Hermann Kumbong, Rom Parnichkun, David Romero, Aman Timalsina, Quinn MeIntyre, Beidi Chen, Atri Rudra, Laughing hyena distillery: Extracting compact recurrences from convolutions. Advances in Neural Information Processing Systems, 36, 2024.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. arXiv preprint arXiv:2404 00800,,,8...... 2024.
Eric Nguyen, Michael Poli, Marjan Faizi, Armin Thomas, Michael Wornow, Callum Birch- Birch-Sykes. Stefano Massaroli, Aman Patel, Clayton Rabideau, Yoshua Bengio, al. Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution. Advances in neural information processing systems, 36, 2024.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distri- bution estimators. International Conference on Machine Learning, pp. 26517-26582 PMLR, 2023.
Sho Okumoto and Taiji Suzuki. Learnability of convolutional neural networks for infinite dimen- sional input via mixed and anisotropic smoothness. In International Conference on Learning Representations, 2021.
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint
2022.
Dmytro Perekrestenko, Philipp Grohs, Dennis Elbrächter, and Helmut Böleskei. The universal ap- proximation power of finite-width deep relu networks. arXiv preprint arXiv:1806.01522 2018.
Philipp Petersen and Felix Voigtlaender. Optimal approximation piecewise smooth functions using deep relu neural networks. Neural Networks, 108:296 200000,,, 2018.
Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. arXiv preprint arXiv:2302.10866. 2023.
Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. In International Conference on Ma- chine Learning, pp. 28492-28511 PMLR, 2023.

---

Published as a conference paper at ICLR 2025
George Saon, Ankit Gupta, and Xiaodong Cui. Diagonal state space augmented transformers for speech recognition. ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5. IEEE, 2023.
Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with relu activation function. 2020.
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representa- lions, 2018.
Taiji Suzuki and Atsushi Nitanda. Deep learning is adaptive intrinsic dimensionality of model smoothness in anisotropic besov space. Advances in Neural Information Processing Systems, 34: (609-3621,2 2021.
Shokichi Takakura and Taiji Suzuki. Approximation and estimation ability of transformers for sequence-to-sequees functions with infinite dimensional input. In Proceedings of the 40th Inter- national Conference on Machine Learning, pp. 13416-33447, PMLR, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Shida Wang and Beichen Xue. State-space models with layer-wise nonlinearity are universal ap- proximators with exponential decaying memory. Advances in Neural Information Processing Systems, 36, 2023.
12

---

Published as a conference paper at ICLR 2025
Appendix
A EXTENSION TO ORDINARY SSM FILTER
In this section, we describe how to extend our setting to the ordinary SSM filter. More specifically, our setting with embedding dimension can be extended to the ordinary SSM filter with embedding dimension 4D.
For simplicity, we consider the case 1. We constuct the parameters A, B, C, D 2 make
the filter h4 = CA'B + D6 same as the filter defined in Section Let us set D = 0, and
cos
2
U+1
sin
2 U+1
sin 2ma1
cos
2ma1.1 1 U+1
0
0
A
0
COS
2mmay U+1
sin
U+1
2
2
sin
U+1
cos
U+1
Then, we have
CO8
2m
U+1
sin
U+1
0
0
sin
2
U+1
cos
2
U41
0
2mo1
2x01.2t
cos
U+1
sin
U+1
2na1.2!
2ma1.22
U+1
cos
U+1
Therefore, if we set
1
0
07
C1.1
0
0
07
0
0
0
B
C
0
1
0
0
0
0
C1,2
0
0
then we have
C1,1 cos
2na
0
U+1
h4
0 0
2
C1,2 sin
0
U+1
Then, if we appropriately set WV and W this filter can realize the same output with setting.
While we do not show the estimation ability for the filter above, we can easily extend our proof to derive the almost same estimation error bound for it.
B REPRODUCTION OF THE FINITE WINDOW SETTING
For mathematical simplicity, assumed in Section that the convolution of the SSM layers performed within finite windows, which can be smaller than the sequence length. However, in practical applications, the window size equal to the sequence length. In the theorem presented in Section 3 we consider the case where the window size matches the sequence length, and this aligns with realistic problem settings. On the other hand, in the nonparametric regression discussed in Section 4 since we consider infinitely long sequences, it is impossible to set the window size equal sequence length.
In the problem setting of Section we can obtain the same output as when using finite window size by performing some additional calculations with standard SSMs. Let [ureeso be the input sequence, and [zzleso- [yelsso be the sequence states and outputs of standard SSMs, respectively. other
words, for any S 0, we have
Øt+1 = Ar + Bug
1/1 Cr. + Dut,
13

---

Published as a conference paper at ICLR 2025
and
24 = Σ AA...
SSt
Next, let [2tleso [Bless be the sequence of states and outputs when the shifted input sequence [u-UU-1ee -leso are fed into the same SSMs. Then, it holds
2 Az! Bu-U-1;
3/ Cr² DUt-U-1
and
Σ
A -
Σ
A A U--UU11
Bug
85t
3st-U-1
Therefore, have
24
A U4
Σ
BB,
A'
-=t-U
Let le/ be the output sequence of SSMs with the finite window size of length U + 1. Then, have
vi- Σ (CA' DŌ. Dō._.)u. C(x: UU+ x4) + Du.-
8=1-U
Since U++ can be pre-computed, we can obtain the output of SSMs with the window by performing recurrent calculations for two SSMs.
C EMPIRICAL RESULTS ON THE SYNTHETIC TASKS
In order empirically demonstrate the dynamic token selection ability of SSMs, conducted experiments on the input copying, associative recall, and nonparametric regression.
We consider three types of models: (i) single-layer SSMs (SSM + FNN), (ii) two-layer SSMs (SSM + FNN + SSM + FNN), and (iii) Transformers. As we proved theoretically in Lemma 3.3 to exhibit dynamic token selection ability in SSMs, it is essential that SSMs preceded and followed by FNN layers. Therefore, theoretically, (ii) two-layer SSMs are expected to perform similarly to (i) Transformers. Moreover, since (i) single-layer SSMs do not have the dynamic token selection ability, they are expected to perform worse than two-layer SSMs and Transformers.
To demonstrate the effectiveness of adding FNN layers SSMs, vary the dimension of the hid- den states (i.e., dimension of the states in SSMs). Then, we observe the changes in the performance.
Input Copying and Associative Recall We first conducted experiments on the input copying and associative recall tasks. Results are shown in Figure C.1 We can see that the performance of (ii) two-layer SSMs is better than (i) single-layer SSMs, particularly when the dimension of the hidden states is small and the FNN layers have sufficient expressive power. This means that the alternation of SSM layers and FNN layers essential to exhibit SSMs' dynamic token selection ability. Moreover, we observe that the performance of (ii) two-layer SSMs is comparable to (iii) Transformers. This result empirically supports our theoretical analysis that SSMs combined with FNN layers can mimic the dynamic token selection ability of Transformers.
Nonparametric Regression We also conducted experiments on the nonparametric regression task. In this experiment, we consider the following setting: let us consider the situation where inputs are given as sequences of words from the set W. For each word wo E W, we assign a value Tw E [0, 1]. When the imput sequence X [w1, W2..... wz], the output y given y = f(max Tww
where f is non-linear function. The function to be estimated,
X + (max (rar...... .w,, }),
can be framed piecewise smothh function. Indeed, the values assigned to the words can be seen as the importance each token, and the input to the smooth function ff is the token with the highest importance.
14

---

Published as a conference paper at ICLR 2025
Input Copying
Associative Recall
1.00
Accuracy
6.8-
Accuracy
0.89
Tranformer
0.79
SSM FNNI2)
SSM4 FNIN2))
4 FNNN4)
0.6
SSM+ -MM-
SSM4 FNN FNNII)
0.85
SSM FJ FNNN44
0.50
Dimension of the hidden states
Dimension of the hidden states
Figure C.I: Empirical results for input copying task (left) and associative recall task (right). We compare the performance of single-layer SSMs (SSM FNN), two-layer SSMs (SSM FNN SSM + FNN), and Transformers. The number in parentheses following "FNN" indicates the depth of the FNN. We can see that two-layer SSMs with sufficiently expressive FNN layers exhibit performance comparable to Transformers, and outperform single-layer SSMs.
Loss of Nonparametric Regression
1.2
SSM + FNN(4)
1.0
SSM FNN(Z) + SSM+ FNNI2)
0.8
LOSS
0.6
Dimension of the model
Figure C.2: Empirical results for nonparametric regression. We that two-layer SSMs (with
FNNs) perform better than one-layer SSMs, similar to input copying and associative recall.
Results shown in Figure C.2 For single-layer SSM. the loss increases sharply the dimension of the hidden state decreases. In contrast, when using a two-layer SSM, the rise in loss due to reducing the hidden state dimension is mitigated. This suggests that stacking two SSM layers helps improve performance in nonparametric regression. This observation aligns with our theoretical findings that having FNN layers both before and after the SSM is crucial.
D ADDITIONAL RESULTS ON SYNTHETIC TASKS
In this section, provide additional results the SSMs' ability solve synthetic tasks. Specifi- cally, we consider the two tasks: induction heads and selective copying.
D. INDUCTION HEAD
The induction heads Olsson al. 2022 is task to recall the word that appears immediately after a specific keyword. For example, if the keyword is x and the input sequence "a a d c", the model have output the word "b", which is the word that appears after "c".
15

---

Published as a conference paper at ICLR 2025
To formalize the task, suppose that input sequences given by the form "x1 22 zv k", where I1...., ,,,, k E W. Moreover, we assume that, for each sequence, there exists a unique j E [V - such that 2; = k. Then, the model is required to output 1j+1-
In this task, the position of the token to extract changes for each input sequence. Therefore, to solve this task, the model has to change which token focus based on the input, i.e., the dynamic token selection ability is required.
For induction heads, obtain the following result.
Theorem D.I. There exists an SSM F E U,
with 2, U= D, L, W, S. log B S log" Vlog" [W],
and decoding layer Dec with [eDlel Σ such that, for any input sequences of induction heads task, the model generates the correct oulput.
The proof is provided in Appendix H
D.2 SELECTIVE COPYING
The selective copying (Gu & Dao 2023) is variant of the input copying task, where there are some empty tokens between the tokens to copy. For example, if the input sequence is " "(BOS) a (PAD) (PAD) b (PAD) a (PAD) (COPY)", the model have generate the quence "a b c" in an auto-regressive manner.
Similarly to the input copying task, since the models have to change the position of the token to copy, the dynamic token selection ability is required to solve this task. Moreover, since the model needs to avoid empty tokens at different positions for each sequence and copy only the necessary tokens. Therefore, it requires capturing the context of the sequence, making it a more challenging than input copying task.
To provide formal definition of the task, suppose that the special tokens (BOS), (PAD), and (COPY) are included in the vocabulary W. Then, us consider the input sequence of the form "(BOS)
(COPY)", where æ1..... by E W (BOS), (COPY)). For each E [V], Iy is a random variable that matches (PAD) with probability a (> 0). Otherwise, 2; is generated from the uniform distribution over W (BOS), (COPY), (PAD)), Let i1...., ... [V] be the indices such that Fi, * (PAD) (k E [K].. Then, the model required to output the sequence "r,, Tix"
For the task described above, we obtain the following result.
Theorem D.2. Let
Suppose that [W] 2 loge(V/e). Then, there exists an SSM f
S(M,U, D, L, W, S, B) with
M 2, U D, L, W. S, log B log Vlog c log [W],
and decoding layer Dec with [ee lloe. such that, the model generates the correct sequence for selective copying task with probability 1 e.
In this theorem, compared to the case of input copying, we additionally assume that |W] 2 log" (V/e). This is mainly due to the existence of empty tokens in the input sequence, and is not due to the problems specific to the SSMs, i.e., the same problem would occur in the case of Trans- formers. More concretely, in the proof of the theorem, similarly to the proof of Theorem 3.1 consider the n-gram immediately before the token, and construct a network that can find the same n-gram (excluding empty tokens) in the input sequence. Since there empty tokens in the input sequence in selective copying, n-gram overlapping (excluding empty tokens) can easily occur com- pared the case without empty tokens. In particular, when the vocabulary size [W] is small, n n-gram overlapping much more likely to occur, thus it is difficult to copy the sequence correctly.
The proof is provided in Appendix
H
16

---

Published as a conference paper at ICLR 2025
X
x
x_3
X
x
#(X
p(X.
JOX
p(X_,
X
(2))
Sort by the importance
(0L,) < m(X.)) ((X_)) #0X.s)
II
X_3
x_2
(x1 13 x2)
f: r-smoohh function
II X
(13, (33)
g(X) = -1x 44
(xz, X2. x1)
Figure E.1: Intuitive explanation of piecewise 7-smooth functions. Left: For simplicity, consider finite-length input sequence [x [2--4-..., I- mn]. . An importance function takes the sequence input and determines the importance of the last token. Using the function μ., the importance values of each token, (x__)),...
Xo). are determined. permutation map rearranges the tokens in ascending order of their importance. Finally, the rearranged tokens are fed into a 7-mmooth function f. In the sorted sequence, tokens in the right have higher importance, and the function f becomes less smooth for tokens positioned further the right. Right: An intuitive explanation of how the smoothness of function changes due to token reordering. As an example, consider function with a 3-dimensional input vector X (I1, 23). Assume I is only non-smooth in the direction of the second coordinate, while is smooth in all other directions. If X is directly fed into f. the second coordinate, 22 is always the non-smooth direction. On the other hand, the coordinates are rearranged by mnputdepenneett permutation map II before being passed to f. the smoothness of the function changes. For example, in the top-left region of the domain, the reordering might cause the second coordinate correspond to 23, making 23 the non-smooth direction.
E THE INTUITION BEHIND PIECEWISE SMSOOTHH FUNCTIONS
In this chapter, we provide intuitive explanation of the definition of piecewise m-smooth functions introduced in Section 4.2
The goal of our study is to demonstrate that SSMs possess the ability to focus on important tokens in the input sequence, similar to Transformers. To achieve this, we formulate the importance each token in terms of the smoothness of function. Specifically, let us consider a function f that takes a sequence of tokens X = smooth with respect to token (coordinate) 24, regard that token unimportant; conversely, if f is not smooth with respect to Ti, we consider the token to be important. This is because, when f smooth with respect Iú, the value of does not change significantly with variations in 24s and vice versa.
[ ,_.., I- Fnl as input and outputs y = f(X). If the function f is
To quantitatively handle the smoothness of a function, first consider 7-smooth functions. As described in Section 4.2 ?-smooth functions form a class of functions that includes spaces such as mixed-Besov spaces and Sobolev spaces. While this class includes wide variety of functions, once specific function is fixed, its smoothness is also fixed. In other words, the locations of important tokens are independent of the input. Thus, even we demonstrate the capability of SSMs to estimate functions in this class, it does not reveal whether SSMs possess the ability to dynamically adjust their focus based on the input, i.e., the dynamic token selection ability.
To reflect the dynamic token selection ability of Transformers and SSMs, we introduce piecewise y-smooth functions. We provide an illustrative explanation in Figure E. To make the smoothness of function dependent the input, we consider rearranging the input tokens. If we rearrange the tokens using a permutation map II based on the input X and apply the function f. the smoothness changes depending the input, while the smoothness of the smoohh function itself is fixed. We define the composition of the permutation map II and the smosohhh function f. i... f o II, as a piecewise 7-smooth function.
17

---

Published as a conference paper at ICLR 2025
Bob was born in New York. After graduating from university, he became a lawyer.
What is Bob's occupation? In which city Bob born?
Lawyer
New York
Figure E.2: Real-world tasks where piecewise y-smooth functions can be applied. Left: There are different type of bird in each of the two images. The images are taken from ImageNet (Deng et al.) 2009). When considering a task of classifying these two types of birds, the important region is only the part containing the bird, highlighted by the red box. By defining an importance function that assigns larger values to this region, the task can be framed within the framework piecewise 7- smooth functions. Right: A passage and two related questions are given. Depending on the question, the important parts of the passage are different. Let us define the importance function that assigns larger values to the relevant parts of the passage based the given question. Then, this problem setting can also be framed within the framework of piecewise y-smooth functions.
To define the permutation map II, we introduce an importance function μ. The function takes sequence of tokens as input and returns the importance of the last token as a real number. Given The importance of token The map rearranges the tokens in
sequence X = [ 22 2, 1. let X_; - I- ------------ 2-1-1,
x-; is then computed as u(X-;), as shown in Figure E.1 ascending order of their importance scores u(X-.).
As assumed Assumption 4.3 the function f becomes smoother with respect to tokens located farther from position O. Thus, tokens with higher importance as defined by μ rearranged to positions closer to position after the permutation. Consequently, these tokens are considered more critical for the function f.
Thus, the piecewise 7-smooth function g = f 11 is defined. The following two points are particu- larly important:
While 7-smooth functions have fixed smoothness, piecewise 7-smooth functions have smooth- ness depending on the input. This is because the tokens are sorted by the order of importance.
The importance of tokens are determined by the importance function μ.. If a token has high importance, it is significant token for the function f.
In Figure E.2 present concrete examples of real-world problems where piecewise 7-smooth functions are applicable.
In the example on the left, there are two images with birds. We consider the task of predicting the species of the bird in each image. For this task, only the regions containing the bird are relevant, while the other parts of the images are not essential. Since the locations of the birds differ between the two images, the important regions vary depending on the input. By defining an importance function that assigns higher importance to tokens corresponding to the regions containing the bird, this problem can be framed within the framework of piecewise 7-smooth functions.
In the example on the right, a passage and related questions are provided. We consider the task of inferring appropriate answers to the questions based on the passage. For the first question, which asks about Bob's profession, the focus should be on the blue-highlighted part of the passage. For the second question, which asks about Bob's hometown, the focus shifts to the highn-higllighted part. We can define an importance function that takes the passage and the question as input and assigns higher values to tokens corresponding the relevant parts of the passage (c.g., the blue part for the first question and the green part for the second question). Then, we can interpret the problem within the framework of piecewise y-smooth functions.
18

---

Published as a conference paper at ICLR 2025
F AUXILIARY LEMMAS
In the following discussion, to simplify the notation, we define the function class (D B) by
V B), = + [c1, cos (2ta + C2 sin (2 xt)=== ||e|loo B, |a S B.).
First, we prove the following lemma, which states the properties of the Softmax and multi-variate Swish function.
Lemma F.1 (Properties of Softmax and Multi-variate Swish function). Fix 0 E R Assume that there exists an index i* E [d] and >> 0 such that 0,- > 0, + ô for all + it. Then, the following two statements hold:
1. (Lemma C.I of lakakura & Suzuki (2033 It holds
Softmax (0); 61,5-1 edx(x(-)
2. For any 10,, it holds
Softmax(()) (f); 24 Iz- S 2d exp(-5).
Proof. We prove the second one. Using the first argument, we have Softmax(0);
Softmax 0); + (Softmax(O)=- xz-)
$
Softmax(()) (0); (Softmax(0): Ij. - 5.
Σ
Softmax(0); 61,5-1 | oy + |Softmax(0))- 81-,501 Dz
< [Softaax(0); - - -
< 2d exp(-6),
which completes the proof.
The following famous fact that there exists neural network that realize the clipping function.
Lemma F2. Let a, E R. There exists neural neural network felip E (L, W, B) with
L 11,,
W W1, SS1, B |a/a+ +||+
such that, for any R, it holds
a
if x < a ia < x b.
fei =
b
ifb x.
The following lemma shows the approximation ability of FNN for some elementary functions. Lemma F.3 (Lemma F.6, Lemma F.7, Lemma F.12 of Oko et al. (2023), Corollary 4.2 of Perekrestenko et al. (2018)). The following statements hold:
(mult) Let d > 2, C > ee E (0. For any 0, there exists neural network fmult
(L, W, S, B) with
L. S (loge" -1 + dlog C): log d. W S d S dllgg - dlog C, log B S d log C,
19

---

Published as a conference paper at ICLR 2025
such that, for any [0, C1 and R with || x lo I Cervor, it holds
d II 2i c d. Cdd Cerror.
funlt (a')
1=1
(rec) For any e E (0, there exists free E VL, W, B) with
L L log²=" E- W S log 6- S log c-1, such that, for any
log B S loge
[c, (5,c44anddd and x' E BR it holds
|x' x
[foo((e))
S c
22
(exp) For any >> 0, there exists Seep E (I, W, S, B) with
L H log E W S loge S S log' E
log B S log² E
such that, for any x, x 2 O. it holds
1fexp(x') exp(x)) S set I zz/. z/.
(cos) For any 0,a 0,b E R, 1, there exists foos E VLL, W, B) with
L - log c- + log( (a + +),
W - 1,
S 5 log 2 c- 1 + loog(Da + b), log B s max f1, log [b/a|},
such that, for any D-, it holds
[ (x) - cos(ax + 6) se.
We also use the following lemma, which gives the approximation error of (1r, v) + y/a.
Lemma F.4. For any E E (0, 1), there exists neural network (L, W, S, B) with
L S log" c-_ W S log"e" e- S log -!_ log B S loge"!
such that, for any F. U, x' , E TR with E 1,y 10,
6-) 1 it holds
p(2',)/) y s e
x'
y --
x
e
2
Proof. From (rec) of Lemma
F33 there exists neural network Φi WL, B) with
L x log-
s log" 3 e-1
S S log" c-1,
log B S loge"!
such that, for any E [e,
11 C
[e
e 3
and x' E R, holds
< 3 x x-
(1
x
Next, using (mult) of Lemma F3 there exists a neural network &₂ E VL, W,S, B) with
W 1 S S loge-1 log B S loge such that, for any y, E [0, '1 and y/,2' 2 R. holds
L S log
22 - 2'
+ y v/l
(22(z',))) zyع S c
2
Therefore, we have
" S
2 Φ1(xx)
1
1
+ v1)
x
1 x-xx x'|
11 nー v'
S E +
+
22
Lastly, we state the following lemma, which shows that the Gaussian kernel can be approximated expressed as the sum of the product of neural networks.
20

---

Published as a conference paper at ICLR 2025
Lemma E.5 There exists N N and FNNs on &n 0 W,,, Vnn 1/2
B), (n = 1...., N) with
N S "ogg"_!
L x log a E log Ki
W S 1, S log log2N, k. log B S log² e- log n.
L' = 1,
W S log' S' S logg E
such that,
for any t, E 11-1, 1]. it holds
N Σ
exp (-n- sin? 2 (2
T (1 - (1--))))
Un (n)n)()))) Sc
n=1
. for any x, y E [-1, 1), it holds
N Σ
ạT (x(--1)) exp -k -inn
o (x)o(())))
Se.
for any 1. E [-1, 1), it holds
N S.
exp -K sin?
(t)
n=1
Proof. The first part of the proof inspired by Lemma F.12 of Oko al. (202)). Let set A log 3e The Taylor expansion of exp shows that, for any x E [0, A,. it holds
N-1
1))
AN
exp( (pp((>))
n S
n!
N
Additionally, we can evaluate the right-hand side as A&/k! S (eA/k)". Therefore, if we set N
max {2e.A, [log, 3e "1.. the error can be bounded by e/3. Moreover, for x > A, we have
N-1
N
1)
exp(-2) (xx)
x
S
|exp(- -x) - exp(-AA) + exp(-A)
Σ
n
n!
n=0
2=0
+ 2e
Next, let us approximate
(-x)*
sin
2n
(t .)).
We use the fact that
sin 2m (x)
cx
c
iz
1
2n
(-1) (22
2
22n
k=
(-1)n
(2n)
kk
(2n)
+
Σ
k: cos ((2h 2n)ar),
22n
11
22n-1 I
A2n+1
where Ca
if is even and Cn 0 if n is odd. Thus, have
N
R n
sin
(t- x))
n!
N-1
2n
N-1
RR)" 1
(2m
cos (TT n)(1 x))
2!22n
n!
22n 1
1:
n=0
n=U 1
N N
R
22
N-1
(-R)" 1
(2n)
A cos (T n)t) cos (= n))))
nl22n
n!
22n-1 1
n=0
n=0
k2n+1
sin (n n))) sin (= m)xx)
21

---

Published as a conference paper at ICLR 2025
which is decomposed into the sum of products of functions of and Since
k)
2n 2 k:
(2n)!
A" 2 (n!)2
16"h
2 2"(n1)
S K
n!
n!2" kl(2n - k). n!2" (max (k, 2n - k))! n!2" n!!
we can see that, there exists Co, Cr. (n .....,NN 1: ......N
.N.
N-11 --1) 1) with
CD S N
Cn. S S
such that
N-1
k))
sin
2n
π (t
2)) = Co +
N-1N-1
Σ Σ
Cn,(cos (T(K - n)tt cos (T - n)x)
n!
2
n=0
m=0 K=0
+ ssin (T n1)( sin (T - m)))).
The second item to be proved is already obtained setting 0.
To prove the first item, we approximate each term using neural networks. Lemmal F3 implies that, for any n, k and > 0, there exists neural network k,, P2,n, IL, W, S,S.B) with
L log" k + log² c W 1.
S N2 S Nol + log² log²c= c- log B 1
such that
[cos(T(K: n)x) (z)) <<(N2x2))
|sin(T n)z) (2)) S <N
Then, if we approximate exp(- cos(mm x))) by
N-1
Co + ΣΣΣ
( (a - n)t + sin (T n)) (x)),
n=U A=
the error can be bounded by
N-IN-1
+ ΣΣ
2e Cr.
N2 Se+
2e N2 S 3e,
n= A=
which gives the desired result.
For the third item, if we utilize 01,, and 02,n, to approximate cos(T(k: n)y) and sin sin(TTk - n)yy, respectively, we can obtain the desired result.
The following lemma is the multi-dimens dinlesioinmn version of Lemma
F5
Lemma F.6. There exists N E N and FNNs on,i on.s v V,,1 (, B) with
N $ log? c- + log2 d, L dt log e log K,
WSC d, such that, for any x, y E [-1, 11d, , holds
S dt lo c log² K,
log B S dlog c log K.
2 (x, mil)
exp
sin
nn (n) Se. Σ n=1
Proof. The proof of Lemma F.5 shows that, for N ~ log² c- + log² d, there exists oi,..., o and
Cr, ,CN with CC,l S x such that
exp (-x K sin? (5 vil) Co s e d'
where 6f is a function represented as sin(a + bn) with some an bn E R. Therefore,
N
II Σ
Σ
C., One (21) .0...- (xa)o% (.1)... (va),
22

---

Published as a conference paper at ICLR 2025
which have Nd terms, an approximation of exp
-K Σ
n
sin?
(2 wi)) and the error
i=1
bounded
N
exp
i=1 (2(1:
sim
wi))
II 1=1
Σ
Cn
S d sd.ē= =E
m=
Using (cos) Lemma
F.3
we can see that, for any n E [N] and 0, there exists a neural network
11.. E a,,1 S, B) with
L S d² log"
log Ki
I, S S dt log e log
log B S log²
log Ki
such that
(z) - (1,1 S dx Na
Moreover, using (mult) of Lemma F.3 (L, W, S, B) with
we can see that there exists neural network v/2 ma 1/3
L L d log" c- log2 K.
W S d, d e- logg log B S d,
such that
... -.. 2 kdN e Ta) - 21 ... F.l S RdN for any x E with |x|| S 1. for any 21...., ddd E I with | S Then, we have
|122211............ xa) Onl ...
e
Σ M (Wr, (x1).... nn (2a)) (11.m (V1).... Vi, (Ua))
-exp - Σ sin 2 (" (xxx; y6.)
S AdN
Σ
O. ... ...C V/ (01) .. Vi,n 222 (1/1) ... 2/2 (va)
Mi
-exp -K Σ
sin?
T (x: y1))
KdN + dndN Nd.
I KdN
dRdN Nd
+
Σ
On. ... Ona (i(1)) ... ()((a))) (i(1)) ... (3(a)
Bin....
-exp
sin"
(a; yh)
2
SC, which completes the proof.
G PROOF OF LEMMA 3.3
First, for any * j*, it holds
G
- Ilal |k 1gg k; ( 11a112 1a11
1
1
+
111g 112
2 2111 ky- 112
Ro ---- Tky 5 55
Now, since it is hold that
4
1
cos 2u
2
< sin 2 (u)
< 22
3
2
23

---

Published as a conference paper at ICLR 2025
for E [02) for A > 0.j E [-V : 0) E [d"], we have
[Asin (
π
(kiz - -i))) ; -
2 (Nis - )
2A
A2 sin? ( π
2A (kiss - u))
AP( π
AP(2A
(kizs (
21
S A2
( (T
(kzz 9:))
2A
A
Therefore, if we set A =
16m2d'
it holds
1 2 Iell + [kyb11
1
1
4
A sin
(kzz
4i))
2
2 i=1
2A
d'
1
|aull
+
+22111 211kz-11 11?
1
-
1 4
Assin (2A (ki- (.))
72 i=1
( ||ll
1 1 kj 12
1
kil13) - -(51ee1 + 1/2 =1kk-11 11=
1 211o - kg.
q
2
4d'
(A
sin
π
(kig
4:) m))) 2 - -(5 (kis .:)) )
72
24
+
4d'
ssin
π
(ky- ))))²² 2
(σ (ky- -.)) !
72
2A
4d n²
4d'm
8
5
8
6-6+
+
6
+
A²
A²
4
4
2
In the following, we denote
|191|
2
+
1
|1:;111
1
4
Σ
(Asin
(Rije - a)))
2
2
x²
2A
Using Lemma F.I
we have
Σj=-v exp (xp(1<pg)
8k
I 2(V + +)) exp
expexpp
Vz-
Σ - exp (Kit(s))
2
20
for any > 0. Therefore, if we set k: = s2 log +log v)
the right-hand side is less than
Next, let us consider approximating exp(Ks))) -yg = uj exp
d'
2 |lal12 2 - -2
1
11,
1
Σ
Assin
π (kize - q:)) 2
2
2A
1=1
d'
= - - exp
K5 exp
(11113))
exp
32nd'
sin
n kis 4i 2
8
A
Combining (mult) and (cxp) in Lemma (L. W, S, B) with
F33 we can see that there exists neural network Φ1 E
s d
W - d'
82 (log² c- + +log v),
8 (logc+++ogg
s S d²
d² log B S 8z (log² c- log" V),
8z (log²
-1 + log V),
such that
01 (I) exp
k [1ا1
s (V= - 1)22 9 exp(-9rdd - 46)
24

---

Published as a conference paper at ICLR 2025
for any E R with ||>|| < 1. Moreover, using Lemma F.6 we see that there exists neural networks 22 H3,n E (V, S, B) (n = I...., N) with
d 86
2 (log² - + log V),
I. S
(log 5 E + +logg Vog'V),
W sdd
d'
d
S (log -1 + +log v),
log x
(log - + log v),
85
82
such that, for any 2. E [-1,
N
32nd d'
Σ (2n(())ssn - exp n=1
π sin 2
2
2 (V 1)2 " exp(-99ad - 40).
Note that, by clipping the output appropriately, we can ensure that
Rdl'
32ndd' d'N
+32kd' d'N
10111 S exp
| lac
10 S
2
without changing the approximation error. Therefore, we have
kj
oy (1)))))))))) (Ki))
Σ
2n
- exp(kn()) U/
A
A
n=1
=
eg (1))
Σe
22,0
9
23,50
k2
A
n=1
32nd d'
1i -Ug exp [1a((3)
5
12)
exp (5
K [1b;,11 I1))
exp
sin
Tkis q:
8 1=1
2
A
1
S exp(xdd). (V 1)2 exp(p- 9rad"
45)
exp(-88kad + 8//2).
(V 1)2
Using (mult) of Lemma F33 we can see that there exists a neural network de E (L, W.S, B) with
L dr3 (log² c- =og" V). W WSI,
d
S
83 (log² c + +og log B S 1,
such that (,, v) - -ayl 2 e
N exp(-(17kd) + 6)) for any x. y E TR
NVV+ d'N
32kd'
with [a]| exp
nal' 2 )1111
lvvl S
32ndd' b
Additionally, there exists neural network Φs
I (L, W, B) with
W WSI, SS d
L S 83
(log* 1 +-1+log log" v).
(log coggc-1 +lgg v). log B S 1, (pp(-(17kd' + 5))2) for any v Using these networks,
Jz
d'N
such that (0s(1, -v.xyl xyl x e MV+1J (auRd))
).11l 1v1 1 (3nnd' d'N
Rdd 2, E R with ||olbxo S 1 and |o|| s exp
Rd 2
we have the following approximation:
(21(1) 22.n (2)) - (1) !
1
6
d'N cxp(-(17kdd + +8)2),
N(V + 1)2
32ndd'
Os Uj 02 (ki)) 03,1 03,m
)= U3 (Kig) 1s.n
kj
A
A
8 d'N
5e
exp(- (17kd' + +8)/2).
N(V + 1)2 32ndd
This implies that there exist neural networks 41, 1/ E VL, UWL,WWS. W, B3 with
L S d'
85 (log 5 - + log'v), v), W s d'
8 (loge- + V),
25

---

Published as a conference paper at ICLR 2025
S x d's
d'3
(log² e- log v),
log B x
82 c= + +lg" v).
83
such that
p1 (k3,
25) (k),,)))
- exp(ri(() 131100
N
(g), 22 (2)) Φ5 uz, (kg)) (1g) 03.0
) vy exp(Fa())
kig
(1)),
24
A
Σ
N
Φ
Φ1 (g), 82,m (2)) Øs
Uj 01 (kig): 0s
kij
A
n=1
Mi Φ1 (1)))) (Kz))
Σ
2220
(1)
$3
hig
A
A
n=1
U/ Φ1 (k)) Σ
22
9
03,m
kg
Vy exp(Nip())
A
1
(V + 1)2 " exp( 8(kdd - 8/2)),
where 4 (kz, 12) E RdN and (1))= E R. Summing up the error for j = -V...., O, we have
0 [ [[2,
(1(0) Σ exp(kp()) oj
V+1 è exp((=8(xx)) + 6/2)).
Similarly, there exist neural networks 22, vs3 E W, B) with
ds
d'
L L
85 (log c- + log v),
W z (loge + log V),
8
S d
d
(log" e1 + log v), log B x (log² -- + +og V).
85
8²
such that
T (o((
(ke(k) - Σ exp(Ku()) U3 S V+ exp((-((kd + 8/2)),
5=-V
where el2()))) (4) E RN Note that (k(,, U/) E Rd xN and (k,) E RN are the output of the convolution layer.
From (mult) in Lemma
we can see that there exists a neural network @e E VLL W,S, with
S d' (log c -1 + log V),
W W
S d'
(loge + log V), such that (66(x,))) Xyy x V+I e exp((8((sd' + 5/2)) for any X E Rd' .y
log B S 1,
R- with
d' N'
|| Ilvlloo < (V + 1)
32nd'
exp
4 Similarly, we have the network Φ7 that approx-
32nd' d'N
imates x Tyy y for any y E R with || |aol Ilvll S (V + 1) have
exp
Rd' 2
Then, we
Σ
L1 (k,,, U5), (ky,,,),, (210))
Σ
@i U/) (2((1)
< V + 1
9 exp(p=8(ki)) + 8/2)),
Φ7 cir(g); Σ Ma(((z)
(T()TT Σ e)2(k))
e + 8/2)).
V +
-= v
v
26

---

Published as a conference paper at ICLR 2025
Now, from Lemma
F.4
there exists neural network 68 (L, W, B) with
d'3
L 5 82 (log²e e- + log v), W
83 (log² e- + log v),
d'
S 2 84 (log* -1 + log v),
log B x 8
(loge- + log V).
such that
V/ x¹
r'l
1 s/l
(ds('', ./)
S c
78
72
for any a, U. ,',y/ of
with x E ( and y E [0, where
T == min (c, exp(, (ndd + 6/2))/(V + +1)
Since holds
Σ
exp(K())) . Viga - Σ exp(K)()) S (V + 1) exp(nd' + 8/22)
-=-V
==-V
for any i E [d"]. and
exp(KILy) exp(K)p).) 2 exp(-kdd - -)/2).
we have
Σ Φ (Kis 15)), (1) .77 vb(()), Σ (bo(k;)) ))
- exp(K(()) V/
the
Φ6
Σ expl (kppl))
-=ーV
-=-V
Se+ e eeepp(-8p 8(nd' + 6 / +1 1)
e eexp(= -((rd' + 6/2))/(VV +1) Se.
+
8
72
which completes the proof.
H PROOF OF THEOREM 3.1 3.2 D. AND D.2
H.1 CONSTRUCTING THE EMBEDDINGS
To construct the embeddings, we use the following lemma.
Lemma H.1. Let S be an arbitrary set of n points in Rd, and m be integer. Suppose that, for any x E S, it holds ||>|| I 1. Then, there exists a matrix R E fgd with k S 512m" log + satisfying the following:
Any elements of R +1/Vkor-l1y
For any x, y E S, holds (Rx) (Ry) IT S 8mm
To prove Lemma H.T
the following proposition.
Proposition H.2 (Theorem 1.1 in Achlioptas (..03)). Let P be an arbitrary set of n points in Rdd
Given c, 0, let k be an integer such that l 1429 log Let R be k d matrix whose entries
are independent random variables drawn from the uniform distribution on { 1l/Vk.-1/VB Then, with probability at least 1 - n -8 for any x, P.
(1 <) | v1l2 < Rr Ryll? s (1 + +c]lax v12.
Proof of Lemma
H.l
We apply Proposition H.2 with
P= s S}.
B = 1.
Sm2
Let be an integer such that
4 2
h: 2 512m log n
2
log
2 3
27

---

Published as a conference paper at ICLR 2025
and R. be the random matrix defined in Proposition H.2
With probability at least 1
2n for any
I, y E P.
Rx Ryl2 - || v112 v
1
ylla.
(H.1)
8m2
2
|| Rr + Ryll - || v112
|
v1l2-
(H.22
8m2 2
Since
2ha for any positive integer n. kr d. we can choose R such that HH.1) holds. For
such R, it holds
(Rr) (Ry) x y-
1
(1 + Ryyl2 - -| Ryl2 || + v112 >| w1))
4
1
(1IReC + Rull2 - || + w11 + |||/a Ry 11 || m/b3]
4
1
1
||00 w112
|| u12
4
4m
4m
1
||a:112
+
11s12
16m
16m
1
8m2
which completes the proof.
H.2 PROOF OF THE THEOREMS
The following is the essential lemma to prove the theorems.
Lemma H.3. Let m E Ny and Z = [z_v...., 20] E [-1,1]]ix(-vv) be a sequence of one-hot
vector representing the alphabets set S. Suppose that there uniquely exists j E [-V --1] such that
[zj--mo m. Fz mm 2---1] = [2-m+1, 7-m =0),
where: 2j 0 for $ [-m + 0j. Then, there exists F E U, L,,,U, and W W with
M = 2, U V, D= = m log" V pW
L L log V Vlogg [W
W S m 15 log 3 Vlog" [W] S m 37 log Vlog $ [W], log B S m 10 log" V [W],
such that jr = arg va..==V.....o (W F(2)))s
Proof. Set K (log + log V + log WI). Additionally, let us set embedding E₁ R R Dx in Lemma H.l and set Eb = O. We define xy Rz, for j V,..., O. The third item of Lemma F.5 we can see that there exists vi. E (D B) with
2 v + log² log [W], S log" m + log² V + +og² log [W], D=1, log B $ log m + log²
2
such that
π T k)) 1
2(V + 11 ))
N Σ
exp
K sin?
Un
S Sm²d(V + +1)
V +
n=1
for any j
-V..., O. Since
π (k . 13.(k-1)) )
1
exp
K sin?
2(V + 1)
Sm2'(V + 1)
holds
0
N
j
1
V +
.z Fk
Am?d'
V n=1
Therefore, there exists 91 E C(U, D, B) with
U = V, D m,
log B S m² log V,
28

---

Published as a conference paper at ICLR 2025
such that
V
g(X)
R 8' A
k
Kg
V+1
V+1
10
g'v v
q' v+1
46
q-v q-v+1
90
k V
k V+1
Kg
k- k-
kn
2m2d'
r'vv
n' V+
10
L 1-V+1
vto.
where
9j [t]] J- m- m- 43
kj [n]] m1, Di
and 2j = 0 for j $ m + 11:10 0). Then, holds,
% ky 2 10 kg- md
4m2d 2
8m?
m
4m
8m
and, for any j [-V V 0] }
T Kj S 20 kj md 2m2d m d
1
1
5
8m2
m
4m
8m
Therefore, due to Lemma 3.3 there exists f1, f2 (L, W, S, B) and 92 E C(U, D, B) with
== V,
m log log" [W], LS m log V log [W],
W S m 15 log" V log" [W) S m log" Vlog [W], log B S m log² V log" [W],
such that
|1 92 o S1 gn (X)
Tz- 100 4
Therefore, (F(2))) 2/ Io
smzs which completes the proof.
Now, we prove Theorem 3.1 Theorem 3.2 and Theorem D.I
Proof of Theorem
Due to Lemma 2.4 of Jelassi et al. (2024). we set m S log(V/e)/ log [ we can achieve errv S Therefore, the result follows.
3.7
in Lemma H.3
Proof of Theorem 3.2
Applying 1 and V < |W] directly gives the result.
Proof of Theorem D.1 associative recall the special case of induction heads where the set keys and the set queries are completely split.
The proof is completely the same as the proof of Theorem 3.2 Note that
Finally, we prove Theorem D.2
Proof of Theorem D.2 The probability of having M or more consecutive (PAD) tokens in the input sequence is at most as Therefore, if log V + log this probability becomes less than c/2. Hence, in the following discussion, consider situations where (PAD) does not appear consecutively times or more.
Let "Su, $1...., Sy sv" be the input sequence, and take arbitrary index i VV. Fix positive integer K. Due to the definition of M, if we set m = K M, there are at least K tokens that are not (P (PAD) in the sequence [8:m++1; m 88].
Now, let us upper bound the probability that there exists + j (i.j E [V] such that two sequences [si-m+1s 4 ......... ., st] and [sj-m+1, $j-m-2..... ... sy] have common K elements (including du- plicates) that are not (PAD). First, we have [W] choices for the common K elements. Then, we have (ml/(m- 2)) choices for the positions of the common K elements in the sequence of length
29

---

and Published as a conference paper at ICLR 2025
Each choice of the positions occurs with probability most 1/ Moreover, there are most 22 choices for the indices and j. Therefore, the probability can upper bounded by
m!?
V
m!?
22 |M (m K)P² 222K
WI
(m
K)
V2
e + 1/e) 2
WI
@ K)/e) ((m-X)
V2
(m + 1)2(m+t))
e2(m-KK)
WI
e2(m+1)
(m K)2(m-K)
V2
(MK- - K)
(m 1)2(m+1)
e²
(m K)2m
V2 (KM + 1)²
[ 1)2
KM +1 KM K
2KM
6²
(²KKM + 1)²
K² 1)²
M +1 M -
2²
(2 1)2
(C. KM - 1)2 K
[W] where 0 universal constant. Therefore, if [W] K2 (M-1)² and ~ -ooge-+log V. the probability is less than e/2.
e²
81, is fed into the model. Let us set E D as Lemma H.1 and set Eg Additionally, let xy be the embedding of 8, for = =. 0...., L. Let us consider the model that finds 8 with the index / E [Z] such that the partial sequence [s S1-m4: same K elements that are not (PAD).
Let us consider the situation where the input embedding E
and 1 1 2.........5 81. have the
The similar discussion in the proof of Lemma H.3 reveals that there exists th E VDD,, B) with
N < log" log" V,
D ==1, log B S log" m + log V,
such that
ΣV Σ Vn
1
V V+1
Tj m
Tz
4m
j=L-m+1
Therefore, there exists 91 E C(U, D, B) with
U= L,
S log m + log² V,
log B S log m + log V,
such that
T
d
(x) =
by
h
U/
Tqo
Q1
q1.
1
ko
k1
ki
4m
L10
0
UU0
U1
Vr.
00
where
Qt
Tj
hi
Ej
Ut St
j= m=
m+1
Then, if [sy [sy-m+1, 8) 8 m- s5] and [8] m1-m 8L 3L-m+22 holds
81 have the common K elements,
K
dr K3 m 4m
Moreover, if the number of common elements [81-m m 81, 20-mm22...... .,, 81. is less than K, holds
in
[s} (sjmm+1:8 mt
K
K
3
11 k3 <
m2
4m
m2
4m?
30

---

Published as a conference paper at ICLR 2025
Therefore, due to Lemma 3.3. there exists f1, f2 W, W, B) and 92 C(U, D, C,U, with
= V, D = m
log V log" [W], L m log" V log [W/,
W S m 18 log V log [
S S m 42 log" Vlogg [W], log B S m 16 log V log [W],
such that
1
//2 o 92 o fi (x) x1 $ 4'
Therefore, ||AT (F(2))) xz 1lo $ + 1
sm which completes the proof.
I PROOF OF THEOREM 4.5
I.1 PREPARATION: APPROXIMATION OF 7-SMOOTH FUNCTIONS
Before proving Theorem 4.5 we prove the following theorem Theorem about the approximation of y-soooth functions.
1.2 under Assumption
L.
Assumption 1.1.
The true function F satisfies Fo E FF. where is mixed or anisotropic smooth- Suppose that it holds [| S 1 and [| R. where R 0 is constant. Addition- ally, we assume the smoothness parameter satisfies ||allut- 1)). Moreover, i is mixed smoothness, we assume a₁ < 02.
wt S 1 for some 0
< co and
Theorem I.2. Suppose that target function F satisfies Assumption L. Then, for any T > 0, there exists an SSM F S(M, U, D, L, W, S, B) with
M 1, logu ~ T, D T L~ W~ T2/a
W' ~ T//2///a S~ T2/ max {12/0 (2 12]211d, log B ~ T2/a
(L.I)
such that || 1l,,, 2-T
Given a smoothness function 7: 2:Nox Noxx + R, we define
I(T,)) {(i,j) 3s E xo such that sij + 0, 0,7(s) T},
dmax = (T)
The feature extraction map 1: 1R + Rdmax is defined as T(X) = [Xinsh..... Xisams Simoas
The following lemma shows that, if FNN receives finite number of "important" features, it can approximate 7-smooth functions and piecewise y-smooth functions. This is mainly due to the con- dition |all I 1, which induces sparsity of important features.
Lemma 1.3 (Theorem D.3 in Takakura Suzuki Suzuki(2023),, Suppose that the frncctiont f E Fp. and g E PT, satisfy |[ S R and Iogl S R, where > O and y is the mixed or anisotropic smoothness and the smoothness parameter a satisfies ||a]het I 1. For any T >> 0, there exist FNNs fr, gT E VLL W, B) such that
$2-T,
2,Px
11 Iool. 9112, 52-1
where
L ~ max {Te/a Te) W ~ TT/a2T/aa
S ~ 22/a max {Ta/a TOe 22)2 log B ~ T//
From this lemma, that, if the the convolution layer approximate I, the SSM can give important features to the FNN, and the FNN can approximate the target function.
Now, we prove Theorem 1.2
31

---

Published as a conference paper at ICLR 2025
Proof of Theorem 1.2
Firstly, construct the embedding layer Emb: R - Rxx, Set the
embedding dimension D as max (d, dmax) | + 1. We set E1 E Rxdd to satisfy
E [21,
Lids O, 0, 0...., l
D-d-1
for [2,,..., Fa] Rd. Additionally, we set Eg RD satisty
En
00...., 0, 1,
0, 0 lT.
delemennts
D D-d-1 elements
Note that |F1llo = |2 = 1. Then, the constructed embedding layer Emb is represented as follows:
Zt
Emb(X) =
E RR Dx00
Secondly, we construct the convolution layer. The role of this layer is to approximate the fea- ture extractor т. The weight matrix WV E DDx is set to extract the important "dimen- sions" (i1,..., idmax). More precisely, set Wv satisfy
WV
Wi::
Viamaxx?
O |ERD
D- dmax elements
for y ......., [y]] E D. Then, the resulted projection is represented as follows:
X
Xi.d
WV (Emb(X))
E ERR Dx00
=
Next, construct the convolution filter. From the assumption aij M(ogllbi 1)), choose the window size U E N such that
logU ~ T and au x-=jsu
Lemma F.5 shows that, for each Jm (m I...., dmaa), for any 0, > 0, there exists kim V V'WW,, B) with
W' S log²
cl,
B S loge log
such that
max
kim
j -
exp
- sin?
π
Im
Sc.
;=
2
U
U
Now, if j jml 2 1, it holds
Jm
1)
2 π
2 U ) ') = =exp(
1 2
K (xp(-1²2)
exp - . sin?
U
2
U
U
= exp
-
-
and, if = Jm. holds
{ j
Im
))) =
exp
R sin
2 U
U
Therefore, if we set
U2 loge
we have
max
kim
1
8pm (i) S 2E,
where 8y is the function defined by
[ j = j"
8 (i) =
0
otherwise.
This inequality show that the filter l can approximately extract the important tokens.
32

---

Published as a conference paper at ICLR 2025
Finally, set the weight matrix W by
=
Wo
1
0
otherwise,
which results in W (Emb(()) = [T...., 1 and
91 Emb(X) - Wº (Emb(X)) o (80), w (Emb(X))
g(L)) (()) (Emb((X)
[21]=- R Dx00
U-I
D
2:
Σ k(s))
Xi,t
==0
1=1
E (k(s)) Xist
(k()) X Xidmmatto
Thirdly, we construct the FNN layer. From Lemma such that
I.3
there exists an FNN f E VLL S)
| Fo
(1.2)
2,px
where
L ~ max {reta 12) W T1/a2T/al
(1.3)
S ~ 22/a max {re/a T 211100 log B ~ T1/a.
Let C: RDD - RRd be a linear map such that
Cy = [y ......... Mddmax] for y [y ....... yD! E RD, and set fi = f C. Note that E VL B) for L, W.S.B
defined in (I.). The constructed SSM F represented follows:
f(x)= (z0) f C(zo) ff iX)).
where
C-- f(x) Σ (m)))
dmma
Rddmav
m=11
Now, we evaluate the eтrоr between the target function F and the constructed model F. We evaluate the error by separating into terms:
p for 12Px
+ +|
1,Px
12Px
The second term can be bounded by so we evaluate the first term. Since f
(BW)* "err'--llschhtt.. continuous, for any X [0, 10dx00, we have
f(X) - f r(x) f((()) (((xx))-(((x)))) s (BW) -
Since X [0, 1]dx00, it holds
[((x) ((x))r(x)
(k(s)) (Xm)))m ()) (s) I.m..
(k(s)) -8 (s)
max
m=1,.. m=l...ddmm
< Uc.
33

---

Published as a conference paper at ICLR 2025
By setting = 22-/UU we have
F(x) - fo for( - (rx))-(xx) =2-
for any X E [0, 11
Therefore, it holds
p F
F f for
+ +1[ior- F
2,Px
2,Px
2,
F(X) - ffo((x) + fot F
sup
P,
22-
Finally, we evaluate the parameters L, W, S, B which controls the class of k E VWWW B). Since |a/lett = sup, a S 1, it holds
dmax (i, ) Es E co Sij (,,((s) < <T}
T2/a
Therefore, have
W dmax log c s T2+1/a
log ~ loge - log (U: loge= 2 ST2
This completes the proof.
1.2
PROOF OF THEOREM 4.5
Proof of Theorem 4.5
For T > 0, we define
T,( = (i (i.j) E [(T, = (11)) ( 01 LIf
:...... Tmax (T, == max [j E [M] (T, *
Note that Finx (T,7) T1/a since a.j = 2(j)).
Theorem 1.2 implies that there exist an embedding layer Emb, an FNN fi E (LL W, S, B) and convolution layer 9i E C(U, D, L' W S. B) with
M
log U T, D~ T~
~ T, WI~Ta/a
L' ~ max [T2/a ra]. W ~ TT/agt//l
S ~ T2/a max (12/0 (/2/,,T2000 2 log B ~ T/l/a
such that
fi o 91 o Emb(X), = -x, O,....0 -
danx elementt Tmax elements
for all i E Z, where (X) satisfies
[x) 1))
Intuitively, the i-th elements for = 3,...
dmax are used to store the feature X for j E [d].
and the i-th elements for i = 3 + dm ... 2 dmax Timxx buffers store which elements are already selected. Note that, for any i S. Tmax. it holds
((X) mx)))) ((X) 2 (u(X)x(0) - 2- - (u(X) and x(X), [- for all & E [0: VJ.
T-
In the following, we set
U=V V.
Let us set Xi T log 2 + 2 log V
Using Lemma R33 we see that, there exists a neural network
T-8/a
pexp (L, W. 5, B) with L S 221++8/a) log² V, W S T1+3// log V, S S 221+818/ log" V, log B S 2(1+)))) log? V,
such that, for any 0, it holds
(xxx)( exp(XT=) x 22- =2 /V3.
34

---

Published as a conference paper at ICLR 2025
Moreover, using Lemma F.3 again, see that there exists neural network Øx with
L ( log" V, W I, S S (2(++80)) log" V, log B S T log V,
such that, for any f S V exp (T - - 1, holds
1 (a, y) zyl - 2 22 IV¹.
Then, for any S 0 and y [0, 1 it holds
16x (dexp(xxx); exp(xr=)y) S 1 (dexp XT v) Pexp (xrz)yl (xex((Xx exp(xr=)M)
2 271+8/0
/v3 +2 2/0 1V3
2 27 0/40
/v3.
Then, let us define fi be FNN layer such that it holds fi o fi o (X)) Emb(X), = 1 (dexp (Px (X)), xz), 0......
-... Tmax elements
dmax elements
Additionally, we define
Zm == (fmn o 9m o fm) o ..... (fi 91 f1) o Emb(X), We construct remaining layers f2, 92, f2. frmattl Prmax Frmue +1 to
for m E [1 : Fmax]
make them satisfying
Zm 1 (dexp (P: x;), X
8
X (m) Sm
X (m) Im
o,...,, 0
danx mm
[1y] elements
-1, -.,..,--
Timox 12 elements
where 8
X,(m)) amm Im the approximation of X (imm) sm -mm (m -,..., 1,.... [
respectively such that
X (mm 5m
X
(im) sim
(Lm/V Fhn/V-jm/l jm/V $ 2--3344//1 SV5.
Then, we see that
2M
[2] (x),
(
((rmas)) Jrrmax
(rmax)
3ns/VJ] /VJT.
Praax
Jrmax
Hence, Lemma 1.3 shows that there exists a FNN the E M(L W,S, with
L S max {12 r2)]. W TTllo////a
s S T2/a max (pelane]2211n
log B S T2//
such that
(Z - fll, 1112-2-
The same discussion Theorem 1.2 gives the desired result.
In the following, we construct an FNN fm and a convolution layer 9m for m E [1 [ Tmax]. The proof mainly divided into two parts: (i) obtaining X ((m) j..." i.e., the approximation of important features
X (m)) Jm (k:
1....,, Im.) and (ii) getting Jm. i.e., recording which token jm was selected.
Picking up the important features X X,ao Jm (A= 14=1...., (mm Due to Lemma F.1 and the fact
that im [0 VJ is index such that 14- (Pr-z) is the largest in pe-s (T-ss) (j + J..... in for any t E [0 V] with t * to, it holds
Ey= Xi. exp(xr Tr-r)) (1 - Is(t))
Xi.jm
222 exp (-x-- Xx B-8/a) S 2-T
- exp(xT pe-;)) (1 Ts(
where S = Jm- Now, let us approximate
Ey= Xis Xisexp(xT exp(XT P..) (1 - -ls(s))
1 Ek= Xi, explxr (..)) .1 (1-Ts(i))
Eyzoeepo ph- (1-I(()))) ITs())
=
1 e ph-1) -(1 (1-Ts(())
35

---

Published as a conference paper at ICLR 2025
using neural networks. (L, W, B) with S T20+9/a) log? 2 V, W T log" V, S log" V, log x T1+8/a log V, such that, for any x E (exp(-XT).xo exp(xxx) [0, Vl. > 0.y' > 0. it holds
Using Lemma F.4 we that there exists neural network Φx
6.(2,, v/ y # 2 + V22 (1x x1 + 1y v/1).
Next, Lemma
R55
implies that there exists a neural networks on E (1, and on E
(L, B) n
1, ,,..., .N) with
N s T log T Tlg
L _ ( log log d V,
W S 1, log B S T3(+)//)) log Tlog" V,
$ (11+0/0)) log Tlog 3 V,
such that, for any t, 2 E [0, 1]. it holds
(² log T + 27 8/aa + 2og V) sin" (3 z))
Σ (3) - exp
$ TT-1/ag-2211 22112-22--101- /v2 + T - 2).
Since
logT (/ log T + 2T2 + 2og V) sin (z(t= - x²)
exp
2
< T 1/22 21 10/0 /V2
(1-x) 2 2 1/V), (1 = x),
have
(22 log + 2T1+9/a + 2og V) sin?
(g [{-=x))
= ) [(a
S 27 2T 1/0-11/2-27-44 1/222222+ 27 /V2
exp
2
Therefore, we have
Σ (T) - (1=)(1)) x ST-1/22- /v2 T1+8/a - 2/.
Summing up over r = JiV,..... ..... 1/V, we have
m-1
(m (t) Gn /V) - Is(t)
%
mm'l
S Fmax
T-1//22
271+0/a 1/21//2222+/// /V2 + T1+.9/ 3m -nen Smm/VV)
22 22-2//00/4 /v2
Combining the results above, we have
Φx (X.,
1 Σ
Σ
90
Unedd)
(1)
Xi.s exp(xT De-r)) (1 - Is(i))
1=0
m-1
Øx (Dxx T(--)))
Σ
(im
(1)
()) (Vm -
0
1=0
1(xx (Pexp(X x( - X2, exp(xr P(-
22 52-27148/0 /V2
36

---

Published as a conference paper at ICLR 2025
Similarly, we have
m-1 1
Pexp (xr (1-
Σ
Σ
3m (mm (m)
(1)0)
1=0
m'=1 i=1
V
Σ 1=0
exp(XT Th--s) (1 (1-IIs(a Is(i))
S 2 2T IVa
Using the facts that
1 exp(-x2) -
Σ
exp(xr p(tt) S 1,
V
1=
v
1
u|t] exp(XT A S
exp(XT (lt))
we have
m-
Σ 1=0
xx (X Texpler pe-1))
(1-
Σ
Σ
fm ( Sm GGm//)) Φ
(1)
m'=1 i=1
Dexp (XT me-s))
(1
m-1
Σ
(1) Um (1) (00mmmm)))) Gme/
Σ1 uld exp(xr Al) (1 Is()))
Σi exp(xT Al)) (1-Is(i)
22T V22T1t8/o 2-271+0/0 /v2 S 2-
Overall, we can see that, there exist neural networks do E VLL W,,,W,,, B) and Φ on, dc E (L, W, S, B) with
L S 5 ///4//0 log T log V,
W S T411//+33/0 log Toog V.
$ 7541/0+50/a log T Tlog $ V,
log B S 73+1/a+38/o log log 3 V,
such that
dCc
Xjmmd S2-
4 .....fmm pm f
I
1==
Recording which token was picked up Similar discussion above shows that there exist neural networks % E V (L, W, S, B) and o' 2' & E (LL W, B) with
s 1541/o458/a log Tlog" V,
W $ T3+1/a+38/a log Tlog V,
s S r 1 log T l'g V,
log B S 2341/443//0 log I log V,
such that
d'
Σ 7=0
- sin π Jm
2--T.
Lemma F33 shows that there exists neural network Parcsin E (L, W, S, B) with
L LS 7 (11-//a) log² V,
W SS S S (21+8/a) log? V, log B S 2 log V,
for any E [0, /4], it holds
| (I)) arcsin(x))
2 37 - /V5.
37

---

Published as a conference paper at ICLR 2025
Using this network, we can obtain mm/V such that [im/V VaoVV-ia - jmmV
S 2-33---30 /Va.
Finishing the proof We can easily see that, constructing the weight matrix in the convolution layers appropriately, we can obtain Zm from Zm-1 using the neural networks constructed above. This completes the proof.
PROOF OF THEOREM 4.6
J.1 PREPARATION
In this subsection, we prove the following theorem.
Theorem J.1. Let F E S(M, U, D, W.S, S, B) be an ERM estimator which minimizes the emprical cost. Then, for any E (0, 1), it holds that
(F, FR) S
|R - P912, FES r 1-1+1 Σ
inf
+ 1
M D)
DULWB
+
5
To prove the theorem, we use the following proposition.
Proposition J.2 (Theorem 5.2 in Takakura & Suzuki (2023)). For a given class F of ofnctions from [0. 1] to R let F E F be an ERM estimator which minimizes the empirical cost. Suppose that there exists constant R > such that || S R. || R for any F E F, and
N(F, 11-11 2 3. Then, for any 0 < 8 < 1, it holds that
F. Fi12, (R² + log (FF (R+
Rg (F, Fo) S inf PEFr-I+14
where N(F, 5, II-II) is the 8-covering number of the space F associated with the norm ||- defined by
WFF IH-I) = inf {m E ENI FF...... Fm F, E F, Bi [m] s.A. | F. s d}.
Thanks to this proposition, problem to obtain the upper bound of the excess risk of the estimator f is reduced to the problem to evaluate the covering number the function class S. The covering number of the function class S can be evaluated follows.
Theorem J.3 (Covering number of SSMs). The covering number of the function class
S(M,U, D. W,S, B) can be bounded as
DULWB 8
log.N Pog.NSS(M,UU D, W, B), 1HI M Do)
This theorem implies that the upper bound of the covering number of the function class S polyno-
mially increases with respect to the embedding dimensions D, the number of layers M, L and the sparsity S of the parameters. This result is similar the result by Takakura & Suzuki (203)) on the covering number of Transformers.
A large difference of the covering number between the SSMs and Transformers is the dependence on the window size U:: the covering number of the SSMs depends on U logarithmically, while that of the Transformers does not depend on U. This is because SSMs sum up the tokens the convolution without normalization. Whereas it is prefered that the covering number does not depend on U, the logarithmic dependence U is not serious problem for the estimation ability, as we will see later.
In the following, prove Theorem J.3 First of all, we introduce the lemma below, which is useful to evaluate the covering number.
class from [0, 1]dxoo Re,, Suppose that the parameter space θ satisfies @ C [-B, B) for some > 0, D > 0. Additionally, suppose that K10 0 # 0, 0 E θH S.
Lemma J.4. Let (Jo)ee be parametrized function functiioo
Moreover, assume that there exists constant > 0 such that
So føll r 0 0 for any 0,0 E O.
38

---

Published as a conference paper at ICLR 2025
Then, it holds
rBB log (Fg,N(F,,,, 6F S Slog 6
The following lemma is drawn from Takakura & Suzuki (2023). which evaluates the norm of the output of FNN, the lipschitz constant with respect the input, and the lipschitz constant with respect to the parameters.
Lemma J.5 (Lemma E.3 in Suzuki 2018)). Suppose that two FNNs S,I with L layers and W hidden unils is given by
f(x) (A + bL) ................................ (A1o(x) + b1),
f(x) = (A) + b,.)....... .... (x) + +b,).
where a is the ReLU activation function. Assume that for any 1 = l...., L, it holds
|| B,
S B, Au 00
| s B,
3
S B.
00
Additionally, let 2 be a constant.
1. For any x E IR Dx.00 with ||0| Sr, it holds
Il E (2BW)+r.
2. For any X, E RR it holds
11f(x) f(x')) 2l S <BW)4||X Illlo
3. Assume that, for any 1 1,... L, it holds
Ai - A S 8,
11 by
88.
Then, for any x E RDD with |||||| S r, it holds
[(s)) [(0)
We also evaluate them for the convolution layers.
Lemma J.6. Suppose that two convolution layers g, 9 with window size U and embedding dimention D is given by
9(X) = ((X) (WyX),
g(X) = x)) (WvX).
Let r 2 1 be constant. Assume that it holds
|| S
SB B,
Wv S B,
and, for any h = O...., H and X E Rddx with || 00 S it holds
[|3(X))l Sc, c, for some B > 1, 2 1. Then, the following statements hold.
[((x) S c,
1. For any X E Dx00 with || Sr, it holds
Ilo(X))l S BDrc.
2. Suppose that X'X E Dx satisfies || Sr, ||''l S r and
[|8(X) 3(X' || S x||X X'1l
for some K 2 Then, it holds
llg(X) (1 S (B2rc+ + Br I|I X'1l
3. Assume that, for any h 0,... H. it holds
Wv - Wv|l ///l0 66 -B(x) <6..
If the filter is data-dependent, then 0.
39

---

Published as a conference paper at ICLR 2025
for > O. Then, it holds
1 (xX)l S <Brrc ( (Br)
Proof.
We use frequently the following three inequalities:
| S || S D- DIII 1X
| X I ||
where W R
X x Dxxc Y E Dx00 ,3 E D
Proof of 1
We have
[lx(()) = 1(8(X) * (W) oc
I [18(X) * (Wyx))l
I [Wyx -118(X)11
S BDr e5 BDre.
Proof of 2 We have
(X) - (l [18(X)) * (WvX)-B(X)) (Wv -Vxx
[I8(X) (Wv.)) B(X') (WVxX))l
+ [1(3(X)) (W) - (3(X') * (WVX)))
* (WVx))) + +1(((x')
$ 1 -((') |W + +118(X0111 (W
-
S Br--/l x Br + -r.c- -
B|| -X'llo
(B2re+ Br Br. brrx)]|X- - - 1
Proof 3
We have
lØ(X)
((X) (WvX) -xx3)
3(X)* (wvx)] ((()) * (WvX)- - ((X) * (Wrx))
10
+ +|[((x * (Wvx) - 3(x)+ * (Wixx) |
< (B(X) -m(x) (wVxx)/ + +|[3(x)
((Nv- (Wv-
[(X) -3(X)) 1| + | || Wrr x
S .8. Br + Br cr ôr
(Br²c- - (Br)² 1)
Subsequently, we evaluate the lipschitz constant of the composition of the layers with respect to the input and the parameters.
Lemma J.7. Let (f1, (SM, JM) be pairs of two FNNs which satisfy the same condition of (as) be convolution layers which
the pair f) in Lemma J.5) Additionally, let (g1,91), satisfy the same condition of the pair (g.g) in Lemma J.6
Suppose R > 0 be constant, and
F. F.F: [0, l]xxo + R are two functions defined by
F = clip o sM o 9M .....
clip o fi og
F = clipn Far 9M o olipo o fi gr.
Moreover, assume that B > 1, 1,r 2 1. Then, it holds |F(x)-((X))
52 (2BW)
MI
(M+ 8.
40

---

Published as a conference paper at ICLR 2025
Proof. For ,,..., M, we define
Fm == clip o fm Im .... o clipR o fi 91.
Fm == c fm Im o.. o clip f I1.
and Po = id, Fo = id. Then, it holds
Fm = clipæ o fm o 9m o Fm-1i
Fm = clip, o Fm o Im o Fm-1
for 1, M. Note that 1o S R and clipping.
Fm S R for any I,..,, M due to the
For any X E Rdxx with || ao S and m -,...,, N...,,,, have
(X) - Fm (X)
clip o fm o Im o ( clip o Fm Im o Fm Fmx)
Im Im Fm-1(X) fm Im F F
(:clip is I-lipschitz continuous.)
$ fm Im Fm-1(X) Fm Im F Fm (X)
10
F. F I' o gm o Fm (X) I'm o gm
[mm o Im o F F' o Im o Fm- (x)
For the first term, since ll.m o Fm (x)Il I (BDRc)² due to the first argument of Lemma J.6 using the third argument of Lemma [.5
we have
[I Im Fm-1(X) Fm o Im o F
S 2(2BW) (BDRc)3 8.
For the second term, the second argument of Lemma J.5 and the third argument of J.6 yield
fm o 9m FX)) - -fm o Im o F
(BW) o Fm-1(X) In (
(BW)+ (2BR2 + (BR)² .)) 8.
For the thrid term, the third argument of Lemma J.5 and the third argument of Lemma J.6 imply
Im o Im Fm- (X) - F'm o Fm F Fx)
s (BW) fm o Fm- (X) - Im o Fm-1(())
(BW) R2 BR. x) -I - 1
Let d1, d2 be the constants defined by
A = ( + (BW)+ (BR)) .
A2 = (BW)+. (2 Rc BR.K).
Then, we have
F Fx)
S + A2.
[m-i(X)- Fmm (x)
80
This implies
Fm
+
d1
S S22
Px-1 -|
+ Xx )
d1
A2 -
Thus, by induction, we have
(116(x)-F6(44)
\m d A2 1
[x((X) Fm (x)
+
I Nm
+
A2 -
00
A2 -
Since Ae= > 1, it holds
Am
1
(x) - (X)
< A1
= >1 11-11+22
+ XT +.
S mmd1
2- - 1
Now, using
\ < 3(2BW)
(1 (1+ +1) (
41

---

Published as a conference paper at ICLR 2025
have F(X))-F(x]
2 MA < 22 (DBW (1+x) m)
(1+1 +1) 1)-6,
which completes the proof.
Finally, we prove Theorem
Proof of Theorem 1,3
In the model we consider, it holds
0,
1 5 2U (2BW")"
c es U(2WW))
Therefore, we have
F(X) - F(x) S 22 (2BW) ML (BDR (2-20(2BW))))
-2M+3 ML (2BW1)) (BDRU)2M+1.
The number of parameters in FNN is LW Additionally, the number of parameters in a convo- lution layer is 2D2. Moreover, the number of nonzero parameters in whole network is bounded by M(S + 2D Therefore, the covering number can be evaluated as log. (S U, D, L, W. S,S, l1
$ M(S + 2D2)
M22 D9) B + (BWW)" (BDRU)aM++
+ log
DULW B
< MS + D2) log
which completes the proof.
J.2 PROOF OF THEOREM
Theorem 4.5
implies that, for any > O, there exists an SSM F E W, with
M T2/a, U D T log² V,
L ~ T log" V, W N 2T/a T log V,
8 ~ 2 T/al Trau log" V, log B ~ T log V,
such that |F - F0l12, Px 2-T Therefore, it holds
|F 1F-F 122.2p 2-
Next, Theorem shows that holds
1 log (S, I1=11bo) S 2T/a² T (log V) 1) log
8"
Using Theorem J.1 we can show that
2// T2/2/22/// (log 13
+
+ 8.
By setting
at 2at+1 log n and 8 1/n, we have
tet
R(F, Fo) S n
Zel zel+T
(log n)
122/a log 13 V.
K ADDITIONAL DETAILS ON THE EXPERIMENTS
All the code was implemented in Python 3.10.14 14 with Pytorch 1.13.1 and CUDA ver 11.7. The experiments were conducted Ubuntu 20.04.5 with A 100 PCIe 40GB.
42

---

Published as a conference paper at ICLR 2025
Genomic Benchmark dataset (Grešová al.] 2023) is given with the Apache License Version 2.0 and can be accessed from stttps://gt hub com/ wtt.:/Liiiio--CCCCCCCC-------- gew.miiceeiiiccccooo//o//...ccce benchmarks The pretrained model of Hyena is given with the Apache License Version 2.0 and can be accessed from readme-ov-f11.
?tab=
For the training and evaluation of models, we utilized the code provided at https:///c//ooo //claab///cco... eeseaacchggooge.coom httpa///........o////.//////.//.
We used the dataset coimmaneehanncerrs cohn of Genomic Benchmark dataset. As for the pre- trained model of Hyena, used hyenadna-tiny-1k -ee-lk-sseleeeee The model fine-tuned for 100 epochs. Then, we sampled 20 different test sequences whose correct probability is larger or equal 0.95, For each sequence, we repeatedly mask the tokens that maximize the correct proba- bility. The error bar is calculated by the standard deviation of these 20 samples. The source code for the experiment is found in the supplemental material. Finetuning needs around one hour, and masking needs around 90 minutes.
py and downst ream_ma sk py, which can be
43


Reviews:
[{"review_id": "TO3SepzC9b", "reviewer": "Reviewer_Z8kP", "summary": "This paper theoretically studies the expressive power of State Space Models (SSMs) and compares them with transformers. This papers consider three representative tasks in language modeling: input coping, associative recall, and non-parametric regression. For each task, this paper gives an architectural configuration on model depth, width, vocabulary size, weight norm/sparsity, etc. that can accomplish the task up to a given precision. In particular, the SSM architectures considered in this paper involve nonlinear layers, which are shown to improve the expressiveness of SSMs by enabling dynamic token selection.", "questions": "1. In HiPPO theory [1], the authors demonstrate that certain parameterizations of A, B, C in SSMs can guarantee long-range modeling capabilities. Do the authors see any connection between the proposed parameterization (Lines 151–152) and the HiPPO framework, or similar properties in modeling long-range dependencies?\n\n2. This paper focuses on input-independent SSMs. However, as shown in [2], data-dependent convolution can significantly enhance associative recall performance. Do the authors believe that the use of multi-layer SSMs with nonlinearity is sufficient to compensate this performance gap?\n\n3. The proofs of Theorems 1 and 2 appear to follow a similar structure. Does this imply that the underlying network construction could be shared between the two results?\n\n[1] HiPPO: Recurrent Memory with Optimal Polynomial Projections\n\n[2] Zoology: Measuring and Improving Recall in Efficient Language Models", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "+ The topic of this paper is both timely and important. SSMs have become increasingly popular and are widely used in many language and vision applications. Providing theoretical guarantees for these models is therefore crucial.\n\n+ The paper is well-written, with precise and clear mathematical notations and definitions. While the claims are intricate, they are supported by comprehensive explanations and well-motivated interpretations.\n\n+ The synthetic tasks considered in the theoretical analysis are popular yet insightful choices for analyzing language models. The results are solid and offer valuable insights into the comparative strengths of different sequence architectures. I reviewed the proofs for Theorems 3.1 and 3.2, and they appear correct.", "weaknesses": "- The assumptions in this paper appear to deviate from practical scenarios. Specifically, the paper assumes that the convolutional filter formed by SSMs has a defined \"window size,\" whereas in practice, this window size is often as large as the sequence length. Additionally, it relies on a particular parameterization of SSMs (Lns 151–152) that has not been commonly adopted in real-world applications.\n\n- While the piecewise smooth function class is convenient for theoretical comparison with prior work, it would be helpful to provide more background on this assumption. In particular, the authors should relate this function class to practical scenarios, explaining how the piecewise gamma-smooth function class aligns with real-world applications.\n\n- The results in the paper seem more pertinent to understanding how combining convolution and nonlinear MLPs can perform synthetic sequence tasks while being not closely and directly related to the SSM models.\n\n- The paper's proof techniques and settings closely resemble those in [1]. It remains unclear how SSMs differ from transformers in solving comparable tasks with similar complexity. Furthermore, Lemma 5.1 seems disconnected from the proofs of earlier results, failing to elucidate the underlying mechanism that distinguishes SSMs from transformers.\n\n- A minor point: the analysis highlights a potential technical contribution, suggesting that nonlinear layers play an essential role in SSMs. This claim would be more convincing if supported by empirical evidence.\n\n[1] Approximation and estimation ability of transformers for sequence-to-sequence functions with infinite dimensional input.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HlKP7cG54Q", "reviewer": "Reviewer_uwcy", "summary": "This paper provides a theoretical investigation into the capabilities of State Space Models (SSMs) compared to Transformers in their ability to dynamically extract tokens based on the input. The authors prove that SSMs combined with Feedforward Neural Network (FNN) layers can achieve performance comparable to Transformers in three cases: input copying, associative recall, and nonparametric regression.", "questions": "- Could the authors clarify the differences between the results in this paper and those presented in [A] (see weaknesses)?\n\n- Could the authors discuss the difficulty of generalizing these results to selective SSMs?\n\n- In Line 405, could the authors explain the origin of the expression inside the big-O notation?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper establishes a rigorous theoretical foundation, demonstrating that SSMs combined with FNNs can emulate the dynamic token selection mechanism of Transformers. This theoretical analysis bridges a gap in understanding the potential of SSMs in sequence modeling.\n\n- The paper evaluates the proposed method across multiple tasks—input copying, associative recall, and nonparametric regression—showing that SSMs can achieve performance on par with Transformers.", "weaknesses": "- The paper is challenging to read due to dense technical details. It would be helpful if the authors could include a figure or remark after each theorem to illustrate the reasoning and provide an intuitive explanation.\n\n- The input-independent SSMs used in this paper are somewhat outdated, given recent developments in selective SSMs (e.g., Mamba) and their variants. Additionally, the authors compare a combination of SSM and FNN with only the self-attention component of Transformers. This comparison may not be entirely fair, as the strength of a Transformer block lies in the combination of self-attention and FNN layers.\n\n- A deeper comparison of the results presented here with those in [A] is necessary. In fact, the authors of [A] consider a more general version of selective SSMs, called Generalized State Space Models (GSSMs), which includes SSMs with FNN as a subclass. The results in [A] show that GSSMs do not outperform Transformers on tasks such as input copying, whereas the current paper suggests a different perspective.\n\nReference: [A] Jelassi, Samy, et al. \"Repeat after me: Transformers are better than state space models at copying.\" arXiv preprint arXiv:2402.01032 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "47hrh2YXE5", "reviewer": "Reviewer_8hKM", "summary": "This paper explores the performance comparison between state space models and transformers in dynamic token selection. The study shows that the ability of SSMs combined with  FNNs to extract key tokens is comparable to that of transformers.", "questions": "- Are there additional experimental results, for instance, would applying the improvements to Mamba enhance model performance?\n- Are there any ablation study results demonstrating the effectiveness of adding FFNs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The article presents a novel perspective by demonstrating that the combination of SSMs with nonlinear layers can simulate the dynamic token selection mechanism of transformers.\n- It provides a detailed theoretical proof with a rigorous mathematical derivation process.\n- The proposed theory is validated through experimental results.", "weaknesses": "- There is a lack of relevant experiments to validate the theoretical effectiveness, with the only experiments conducted on DNA base sequences. More experiments in settings such as LLMs are needed.\n- The integration of SSMs and FNNs may increase the model's complexity, which could impact training and inference times.\n- Although the article compares SSMs with transformers, it does not discuss comparisons with other sequence models, such as RNNs or LSTM.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YFyfFsGGci", "reviewer": "Reviewer_Byu5", "summary": "This work presents a theoretical investigation into the capabilities of State Space Models (SSMs) for dynamic token selection. While previous research has established that standalone SSM layers exhibit inferior performance compared to Transformers, the authors demonstrate that SSMs combined with Fully-connected Neural Networks (FNNs) achieve comparable capabilities in dynamic token selection. The theoretical contributions are substantiated through rigorous mathematical analyses across three fundamental scenarios: input copying, associative recall, and non-parametric regression.", "questions": "1. This paper theoretically compares input copying capabilities against [1] and associative recall capabilities against [2]. However, unlike [1] and [2] which provide comprehensive experimental validations, this paper lacks empirical results. To substantiate the theoretical findings, the authors should provide **experimental results** comparing the performance of (i) SSM, (ii) SSM+FNN, and (iii) Transformer on both input copying and associative recall tasks.\n2. **The choice of non-parametric regression** as a case study for demonstrating the dynamic token selection capabilities of SSMs **requires further justification.** This analysis appears loosely related to the paper's main contribution and occupies a disproportionate amount of space. While valuable, it would be more suitable as a separate study. The authors should either better justify this choice or focus on more relevant scenarios that directly showcase dynamic token selection capabilities of SSMs.\n    * Instead of non-parametric regression, the paper would benefit from extending its theoretical analysis to the synthetic tasks introduced in Mamba [3] - a seminal work that has become one of the most representative studies in the SSM literature. Specifically, its **selective copying** and **induction heads** tasks align with input copying and associative recall capabilities, respectively. Including these analyses would strengthen the connection between the paper's theoretical framework and contemporary SSM research.\n3. It seems that the problem setting of this paper (Section 2, Appendix A) for theoretical analysis **overlooks the structural constraints of the state matrix A** (e.g., diagonal or other structured forms) that enable efficient SSM training, which was one of the key points for the practical success of SSMs. While prior work [1] analyzing generalized SSMs without structural constraints was suitable for claiming SSM limitations, this paper's goal of establishing SSM-Transformer comparability requires considering these practical aspects. Consequently, without incorporating the structural constraints, the theoretical claims may not translate to implementable architectures in practice. Please correct me if I'm wrong.\n4. The theoretical foundation appears inconsistent: while the paper references the theoretical results from [1] which analyzes a single SSM layer [page 2, line 84], the current analysis assumes two SSM layers with additional FNN layers [page 5, line 222] (please correct me if I'm wrong). As the superior performance of (multi-layer) SSM+FNN over (single-layer) standalone SSM is self-evident (adding layers naturally increases modeling capacity), the current theoretical analysis alone offers limited practical insights. The paper would benefit from **extended theoretical analyses in terms of architectural design choices,** such as comparing SSM, SSM+FNN, and Transformer architectures under equal parameter budgets. Furthermore, an examination of optimal parameter allocation between SSM and FNN components under fixed budgets would be valuable.\n\n  \n  \n\n[1] Repeat after me: Transformers are better than state space models at copying  \n[2] Laughing hyena distillery: Extracting compact recurrences from convolutions  \n[3] Mamba: Linear-Time Sequence Modeling with Selective State Spaces", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. **The paper is well-motivated:** while prior theoretical works focus on standalone SSM layers and their limitations compared to Transformers, the authors insightfully observe that practical architectures combine SSMs with FNN layers and raise the important question in [page 2, line 77].\n2. **Theoretical rigor:** The paper presents a rigorous theoretical analysis to demonstrate their claims, grounded in well-established mathematical foundations with detailed proofs.", "weaknesses": "1. **Lack of empirical validation:** The paper lacks sufficient experimental evidence for its theoretical claims. As the paper did not discuss whether SSMs can be optimized efficiently (limitation section), there are serious concerns whether SSMs can actually demonstrate comparable dynamic token selection capability to Transformers in practical scenarios, or at least in synthetic tasks which they studied theoretically (input copying, associative recall).\n\n2. **Imbalanced analysis of scenarios:** Among the three scenarios (input copying, associative recall, and non-parametric regression) studied in this paper, the paper allocates excessive attention to non-parametric regression, which is less central to the paper's primary contribution - SSMs' dynamic token selection capabilities. A more concise treatment of non-parametric regression would have allowed for deeper analysis of the more fundamental scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)