Generalization Error Analysis for Selective State-Space Models Through the Lens of Attention
Authors: Arya Honarpisheh
Mustafa Bozdag
Octavia Camps
Mario Sznaier
Venue: NeurIPS 2025 poster ()
Keywords: Generalization Bounds
State-Space Models
Selective Scan
Stability
Transformers
Rademacher Complexity
Covering Numbers
Primary area: theory
TL;DR: The paper derives generalization bounds for selective SSMs using connections to self-attention, showing that spectral properties of the state matrix influence generalization.

Abstract: State-space models (SSMs) have recently emerged as a compelling alternative to Transformers for sequence modeling tasks. This paper presents a theoretical generalization analysis of selective SSMs, the core architectural component behind the Mamba model. We derive a novel covering number-based generalization bound for selective SSMs, building upon recent theoretical advances in the analysis of Transformer models. Using this result, we analyze how the spectral abscissa of the continuous-time state matrix influences the model’s stability during training and its ability to generalize across sequence lengths. We empirically validate our findings on a synthetic majority task, the IMDb sentiment classification benchmark, and the ListOps task, demonstrating how our theoretical insights translate into practical model behavior.

Generalization Error Analysis for Selective State-Space Models Through the Lens of Attention
Arya Honarpisheh
Mustafa Bozdag
Octavia Camps
Mario Sznaier
Department of Electrical and Computer Engineering Northeastern University, Boston, MA 02115 (honarpisheh.c a, bozdag m) morthheeeer... edu, {camps, msznaier)@coe. neu, edu
Abstract
State-space models (SSMs) have recently emerged as a compelling alternative Transformers for sequence modeling tasks. This paper presents theoretical generalization analysis of selective SSMs, the core architectural component behind the Mamba model. We derive novel covering number-based generalization bound for selective SSMs, building upon recent theoretical advances in the analysis of Transformer models. Using this result, we analyze how the spectral abscissa of the continuous-ting time state matrix influences the model's stability during training and its ability to generalize across sequence lengths. We empirically validate our findings synthetic majority task, the IMDb sentiment classification benchmark, and the ListOps task, demonstrating how our theoretical insights translate into practical model behavior.
Introduction
Foundation models trained on large-scale datasets have become the dominant paradigm in modern machine learning following the introduction of the Transformer architecture [1]. Although they very effective in sequence processing, the global nature of self-attention imposes limitations: finite sequence window and quadratic scaling w.r.t. the window length. Recently, new family of models named state-space models (SSMs) became popular alternative address this problem [2. 3]. These models are rooted in the classical state-space representations from control theory introduced by Kalman et [4]. Theoretical analysis of SSMs has primarily focused on linear time-invariant (LTI) settings. Rácz et al. [5] derive enggth-nndependent generalization bound for deep stable LTT SSMs using Rademacher contraction techniques, while Liu and Li [6] establishes a length- dependent bound and proposes corresponding initialization and regularization schemes. These results rely on system stability from control theory, ensuring that operator norms remain well-defined and finite. LTI architectures allow for an easy imposition of the stability assumption, making them well-suited for bounded-norm analysis.
The state-of-the of-the-rrt SSMs that form the core of the Mamba and Mamba-2 architectures are selective and inherently nonlinear [7, 8]. They employ a selective-scan mechanism to capture long-term dependencies, allowing for adaptive and efficient sequence processing. This design, however, makes their analysis distinct from LTI SSMs and more closely aligned with self-attention. Despite their growing empirical success, theoretical understanding of their capabilities remains limited, with the exceptions of Ali et al. [9] and Dao and Gu [8], who establish connection between Transformers and SSMs, Yu et al. [10] who studies the initialization and training behavior of SSMs, and other recent works that examine their expressive power [1 [11-15].
Alongside expressive power, which characterizes model bias, an equally important question is that of generalization, which captures the variance component the bias-variance tradeoff, and it is central
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in theoretical machine learning. Recently, generalization bounds have been developed across various domains, including graph neural networks [16], large language models [17]. meta-learingg [18], recommender systems [19], representation learning [20], and various neural network architectures [21-23]. Work on the generalization capabilities of attention models often builds on the covering- based framework of Zhang [24] and Bartlett et al. [25], originally developed for linear models and deep networks. Recent adaptations include Edelman et al. [26], which studies inductive bias in Transformers; Trauger and Tewari [27], which establishes sength-independent bounds; and Truong [28], which derives rank-dependent bounds.
In this work, we investigate the generalization properties of selective SSMs. Unlike prior work on LTI SSMs that relies on classical tools from control theory and stability assumptions, our approach builds on recent theoretical developments for Transformers and self-attention mechanisms. By unrolling the selective SSM into an attention-like formulation, we enable the use of covering number techniques originally developed for Transformer models. This connection introduces new technical challenges: selective SSMs feature input-conditioned dynamics,
B and C' matrices, and discretization from continuous- timeinuous-timee systems. We address these by developing unified covering argument that combines tools from both RNN and attention-based analyses. In particular, we handle the state matrix A through stability and discretization, while treating the input projections W B and We as linear function classes, analogous to the key-query structure in attention. This results in a two-tiered covering construction that captures the hybrid structure of selective SSMs and is central to our generalization bound, allowing us to study how model characteristics influence generalization and training behavior. We support our theoretical findings with experiments synthetic and real-worll sequence classification tasks. Our main contributions can be summarized as follows:
Theoretically, we derive novel covering number-based generalization bound for selective SSMs by unrolling their structure and leveraging their connection to attention mechanisms. We also provide a bound for linear attention rigorously demonstrate the link between the two model classes
Analytically, we investigate the implications of our bound to understand how generalization depends on the sequence length T and the spectral abscissa 8 of the state matrix. In particular, we show how training can fail to stabilize unstable models when T is large, resulting in poor generalization despite the expressivity of the model.
Empirically, we validate our analysis on synthetic majority task, the IMDb sentiment classification benchmark, and the ListOps task. These experiments demonstrate how model behavior varies with sequence length and stability, highlighting the practical impact of our theoretical insights.
2 Preliminaries
2.1 Notation
We denote the real and imaginary parts of complex number by R(-) and 3(-). We use I,, R"", Raxm to denote the set of real numbers, n-dimensional real vectors, and n X m real-valued matrices, respectively. Lowercase letters like r refer to scalars or vectors, while bold uppercase letters like X denote matrices. The l, f,-norm of vector x is written as ||-|| and the p-operator norm of matrix X is written as l|p-- For a matrix X with column vectors Ti, .i....... Tn, the mixed norm | is defined as || |||æ ... | llg. The Kronecker product of matrices X and Y is denoted by X & Y. Continuous-time state-space matrices are written as Ae, Be, Co. while their discrete-time counterparts are denoted by A, B,C. The variable N represents the number of states per channel, T' is the sequence length, d is the number of channels, and m is the number of samples. We use (t) to denote continuous time indexing and [t] for discrete time. Lastly, we denote by SA == max, { (A)) the spectral abscissa of matrix A E R= the largest real part among the eigenvalues of A. This quantity is commonly used stability analysis, since a continuous-time system with state matrix A is asymptotically stable in the sense of Lyapunov if and only if S < O.
2.2 State-Space Models
LTI SSMs are based on the classical single-input single-output (SISO) state-space representation:
(t) 10)) (t) + BBO (t)))
(1)
(1) = o

---

where A E RNNNN, B E R C. E RIXN and D E R represent the dynamics of a continuous- LTI system corresponding to the 5th channel (feature) u, (t) of the input signal u(t) using the hidden states z0) (t) E R. With the notable exception of S5 [29]. most SSM implementations use d SISO SSMs in (1) in single block, one for each channel respectively.
Selective SSMs, introduced with Mamba [7], make the model parameters and discretization step size input-dependent to increase expressive power. In particular, for the 1 channel, the continuous- time state-space parameters _ (t), cla and the step size A (t) are:
B = WB u(t) C (t) = utt)tT("e"" T W
A( - ( + utt))
Here, WB, We E B . E Rd and p E IR are learnable weights and Ta(x) = In(1 + e*) ) the softplus function. The input and output matrices _! and c. are linear projections of the input (t).. Thus, the state-space model for the 1 channel is:
+l0) = A 2 ())) + (B)(()us(()
yاو u T W (t).
To derive state-space model including all states and imputs, we stack the states (3) to get one single state vector [(x(2))T (x(()) T]
R Nd that satisfies the following state-space model:
+(1) Aax(t) Bau(t)
s(1) = Caa(1)
in which
(
0
(
B.(() = L & WBu(t)
A.
(5)
C.(t) = I @ u(t) W
0
(d)
For the discretization step, we follow the official implementation of Mamba [7]:
B = A.) C C.
A = cxp(A(t)A.))
(6)
which uses a zero-order hold (ZOH) for the matrix A, and a simplified Euler discretization for the matrix B. The matrix C remains the same as C. since it represents static relationship between the output y and state x. Utilizing this discretization procedure and the selective SSM architecture in (4) results in the following snscrete-time state state-space model:
xlt Alt A. x Alt] wBl
y[t] = (Ia & m|4 Wi)
A = T (p + Tutt)
Assuming z0) = 0, we can unroll this recursive relation:
y/t'l (Ia 2 uft' wo)
A'A - - & WBult' -1 tl)ult' - 1 -1 t1)
(8)
t=u
in which A' is shorthand notation for
A II A' (All' +11'-(() for / 0.
(9)
For classification tasks requiring scalar output, an additional parameter E Idd is introduced. This parameter corresponds to linear layer applied the last time step of the output sequence obtain label as 2 = w b[T), which captures all past information. The space of all selective SSMs FSsM as defined in (7) parametrized by
OSSM (Ac, WB, Wc.p.q.w.
(10)
3

---

3 Generalization Bounds for Selective SSMs
To quantify generalization, we study the gap between the empirical training loss and the true expected loss over unseen data. Following standard results from statistical learning theory, we upper bound this generalization gap using the Rademacher complexity of the functiin class. Rademacher complexity of function class J for given dataset S, denoted as [ad(F, S)) measures the average ability of function class to fit random noise and serves as data-dependent notion of capacity. For completeness, we include the formal definition of Rademacher complexity and the precise statement of the theorem that bounds the generalization gap in terms of it in Appendix E.
Bounding the Rademacher complexity of complex function classes, such as foundation models, is challenging. common approach is to break down the model into smaller components and analyze each of them separately by employing covering numbers. Covering numbers quantify the size of each component's s function class by determining how many smaller subsets, or "balls", are needed cover it. Formally, the covering number is defined as follows.
Definition 3.1 (Covering number). Let M be a metric space with metric A subset H. C M is an 6-cover for M for every h E M, there exists h H such that p(h, Ri) S The covering number (,M,,, p) is the lowest cardinality of an e-cover of M.
Remark 3.1 (Types of covering numbers). our analysis, two distinct types covering numbers are employed. The metric space M in Definition 3.1 can be chosen as collection of matrices equipped with the metric induced by a matrix norm. We deploy this definition to construct cover for the parameters A. and p, similar to the existing covering techniques developed for RNNs. On the other hand, let = {f
2} denote a function class, where 2 is equipped with a norm and let S = [1()) lm be dataset. By equipping F with the following metric
||.
1/P
f(ur))) f( -(um)))
(11)
m
we obtain a data-dependent covering number for a function class, to construct covers for WB, Wc, 4- and w. This is parallel to the cover construction for the query, key, and value weight matrices in self-attention. For convenience, we denote the covering number of function class ((F, (p..H))) by (Fis,, ss, e, I]).
The covering numbers outlined in Remark (3.1) can be utilized to bound the Rademacher complexity of selective SSM parametrized as (10) via Dudley's integral theorem, stated below.
Theorem 3.2 (Bartlett et al. [25], Lemma A.5). Given real-valued functioon class {f :2:4 + R}
such that Vu E U, If(()) S 6 and set of vectors S {u()) } we have
In InNa(Fis: is:
12)
Rad(F, inf a>0
4a + 12
de
(12)
m
3.1 Main Result
In this section, we present an upper bound on the generalization error for selective SSMs. Before that, we outline and justify the assumptions necessary for deriving the bound. These assumptions are needed mostly to construct suitable covers through the lemmas presented in Appendix D.
Assumption 3.1 (Input). The input sequence [|x[t]]l2 < B., for all f.
Assumption 3.2 (Parameters). The parameters obey W < BB. | 11.11 Mg. Wolla < Bc. Well,, S Nc. ||w||2 I B., ||w||| 2. || I By. and ||q|| S M.g
Assumption 3.3 (Loss function). The loss function I(.) is bounded by c and Lipschitz continuous with constant 4-
Assumption 3.4 (State Matrix A.). The continuous time state matrix A, satisfies ||
| S B A
and Acll2,1 < MA
'This is modified version of Dudley's integral theorem [30]. The proof presented in [25] ignored the normalization by m in (11) and takes b = in (12).

---

The bounds on the norms || - 112.. || 11, and || |111 in Assumptions 3.1 and 3.2 are standard and chosen to enable the use of Lemma D.3, adapted from [27] originally developed for Transformers. This result provides a covering number bound for linear function classes with bounded || ||1,1 norm, without introducing sample size or sequence length dependencies. While alternative norms can be used, they typically lead to looser or length-dependent bounds. The Lipschitz continuity of the loss function in Assumption 3.3 ensures that small changes in the input lead to controlled changes in the loss, which is essential for bounding the model's generalization error in Lemma D.4. Assumption 3.4 employs different norms than 3.2 (Il Il2,1 rather than || Il1,)) because we cover A with a distinct strategy (Lemma D.2) from the other parameters. With these in place, we now state the following theorem, whose proof is provided in Appendix E.
Theorem 3.3. Let S = {u(a =(0)= 1m be the training set and FssM be all selective SSM blocks described in (7), If Assumptions 3-1-3.4 are satisfied, then with probability more than 1 - 6 the following bound for any h E F ssM holds:
Eu. (I(h(u),
m Σ (h(u))))
m
F2
1 In
9ym m
Ciy
))
+ +301
In (2)
m
3C
2m
(13)
in which
CFsu= Ö B 2/3 N1/3 1
22/3332/333///
(14)
and
S2 PA(1- 1 P(A)
TPA
(1+ (1,) satn MA = In(1 + p+ 2.,,,
PA -1 PA =
(15)
where 1) > 0 is any arbitrarily small positive number chosen in a way that SA + 11 + 0. The notation (()) ignores the logarithmic dependencies on N and d, but not T. The terms 2). does not appear in the capacity expression Crisus with the exception of Mi This is the result of an assumption terms are handled separately throughout the proof, and the assumption is incorporated only at the final stage.
m) = B) made for the ease of presentation in the proof. To ensure clarity in the derivation, these
Proof Sketch of Theorem 3.3. The class of all Selective SSMs, denoted by FSSM is parameter- ized by OSSM = (Ae, WB, Wo, P: q, w). We bound the generalization gap [B(((h(u)) - m E 1(h(u(0)), 2(0 by controlling the Rademacher complexity of FSSM-
The first challenge is to bound the distance between A' and its cover A'. Unlike LTI SSMs and RNNs, where the fixed number || bounds ||,2 here || || as defined by the shorthand in (9), has an input-dependent structure and must be controlled via the learnable parameters {p. q, Ac). In Lemma E.3 we construct the appropriate PA (as defined in (15)) using Gelfand's formula (Corollary 5.6. 14 in [31]) and bounds on p. g. A. to show || < p'a. revealing the role of the spectral abscissa of A.- Gelfand's s formula characterizes the growth of Afll2 terms of the spectral radius of A, which is why the small positive number 17 > 0 appears in (15). Then Lemma E.5 establishes an upper bound on || A' Á' 2|2 through telescoping-sun Lemma E.7, shows how the cover radius for the whole model decomposed as the sum of the cover radii of each parameter in OssM. Additionally, the structure of the neput-dependent time step A||] should be taken into account, as affects both A[t) and B jtt). The bounded norm assumptions on the input and g, together with the presence of the bias term p in A [t]. ensure the existence of uniform lower bound on the step size. As shown in Lemma E.3, this bound is essential for the application of Gelfand's formula to control the growth of ||A' 1|2-
argument. Finally, Lemma E.6, followed by
Next, individual covers are constructed: A. is covered in Lemma D.2 as an element of the matrix space equipped with its matrix norm. Recognizing the attention mechanism in (8), Lemma D.3 covers the parameters (Wn, n, Wc.y, w) } by treating them as linear function classes. These individual covers are combined via Cartesian product to cover OssM, and the cover radii are chosen optimally according to Lemma C.9 to yield global e-cover of FSSM- Finally, Lemma D.4, a standard corollary of the Dudley integral bound on Rademacher complexity. yields the claimed bound.
5

---

Remark 3.2 (Lens of Attention). A novel component of the proof of Theorem 3.3 lies in recognizing the attention mechanism (8), which guides us to cover the parameter set {WB, B, Wc.9. 9. w) as function class. In particular, the line of work by [24, 26, 27] on generalization in Transformers presents numerous govering-number bounds for such parameters. We utilize these results to establish our theorem, obtaining a length-indepene independent generalization bound under the condition 8 < 0. This result attainable only by revealing the underlying attention mechanism. To show this connection explicitly, we make the following assumptions to single out the attention in selective SSMs:
Assumption 3.5. Set q 0 and e, yielding a constant step size A = =1. Assumption 3.6. Assume A. 0, so that A = I for all t.
Under Assumptions 3.5 and 3.6, the selective SSM reduces linear attention with a causal mask [8]. In particular, the output at time I admits the representation
(Ia
WB u - 1)) u
(16)
Query
Key
Value
By fixing A[t] = I and A|| = 1, we obtain significantly simpler derivation of the generalization error bound for linear attention given below, with its proof presented in Appendix
Proposition 3.4. Let S {u())= 2(0) ( and suppose Assumptions 3.1-3.4 hold with the simplifica- tions made in Assumptions 3.5 and 3.6. Then, for the class of linear attentions FLA parametrized by the generalization bound in (13) holds, where Cres (We. B: w), with probability at least is replaced by
Cru = OTBB.BBBBBB
(17)
4 Analysis
In this section, we draw insights from Theorem 3.3: we interpret the dependency of the bound on its parameters and compare to similar bounds derived for other architectures. Table 1 summarizes the dependency of the generalization error bound on the sequence length T, the input dimension d, and the input magnitude B,, for different architectures.
Length Independence. As shown in Theorem 3.3 and Table 1, when the spectral abscissa satisfies < O, the generalization bound is length-independent, whereas if S O. the bound grows exponentially in T. This aligns with prior results for RNNs [32, 33] and LTI SSMs [5, 34), which similarly emphasize the importance of the Lipschitz constant of the activation function and norm of the state matrix. In our setting, the Mamba construction (6) ensures that the stability properties of the continuous-time matrix A. carry over to the discrete-time matrix A). directly controlling the generalization gap.
Attention. We now compare the bounds we derived in Theorem (3.3) for selective SSMs and Proposition (3.4) for linear attention. The gap between their capacity terms, CF and Cr arises from simplifying assumptions used to reduce selective SSM to linear attention structure. First, Assumption 3.5 removes dependence on the input-conditioned discretization A [t], eliminating the MA term and its associated input-norm B,, scaling, resulting in B dependence- gefieetceerrfleeiingggg the three linear projections of attention (query, key, value). In contrast, selective SSMs incur an extra B, factor embedded in Ai due to dynamic input influence. Second, Assumption 3.6 further simplifies the bound by removing the need to cover the state matrix A, reducing the S2 term to a lincar dependence T due projection accumulation. Lastly, comparing linear to softmax attention, the key difference lies in normalization. Softmax reweighs the sequence, removing any explicit T-dependence in the bound and effectively decoupling capacity from sequence length.
RNNs. Consider the vanilla RNN model
x r[t]
o. (A 1] + B u(ff), yit] = or (C
(18)
where a. is L,-Liischitz and bounded. When ( 4111 A|l < 1, the bound is length-independent, whereas for 1, 2a > it exhibits linear dependence on T. The key mechanism RNNs avoid exponential dependence is the bounded activation [36]. Unfortunately, incorporating a bounded activation into selective SSMs degrades their training efficiency, the very advantage that motivated their design.

---

Table Generalization bound scaling for different eqquence-t-sequeene models. Dependencies are shown with respect to sequence length T, hidden dimension d. and input magnitude B., (logarithmic terms in d and Bu omitted). f The term PA depends on the spectral abscissa SA. as defined in (15). When S < 0, we can choose ') 0 to be arbitrarily small so that A 1, yielding a iegettinndeendent bound. l, is the Lipschitz constant of the activation function used the RNN as defined (18). The bounds for LTI SSMs are derived under different assumptions as explained in Remark 4.1.
Model
Specification
T
d
B.
Selective SSM (Theorem 3.3)
SA <
$ 2
TpA
1
1
///2
d²/2
23
25
Linear Attention (Proposition 3.4)
N.A.
T
1
23
Sofimax Attention [27]
N.A.
1
1
23
L
|
2a
<
1
d
Vanilla RNN [32]
A
2
T
d
||
12
>
T
63/2
Discrete-time LT1 SSMs [5)$
max;
[Ax(A)]
<1
1
Bounded
Σx= [|u[]]]]
Continuous- time LTI SSMs [35]
$A <
(TT)
Holder continuous
Another distinction is that RNN bounds hinge on contractivity- the induced norm of the matrix being less than or related to the singular falues-whill our bound depends on the spectral properties of A.. This difference stems from our analysis, which begins with a continuous-tim state-space model and discretizes via the matrix exponential, operation governed by eigenvalues rather than singular values. We believe that the distinctive parameter for RNNs (L, ||A|])) can be improved in a similar way to our approach, where took advantage of Gelfand's formula. This allows replacing ||||| with max, (a, which is an improvement since the spectral radius of a matrix is lower bound on any induced matrix norm.
Remark 4.1 (LTI SSMs). One of the recent generalization bounds for LTI SSMs the length- independent result of Rácz et al. [5], which applies exclusively to stable discrete-time LTI systems. Their bound relies on the f-rnorm of the system's impulse response and the H2-norm of its transfer function, both of which are finite for only strictly stable systems. Extending this result to selective SSMs nontrivial, as there is no direct analogue of these norms for general nonlinear systems. Moreover, they assume that the input satisfies =k= [|](x]]] < co, which is generally not satisfied in deep learning applications unlike our Assumption 3.1. Liu and Li [6] derive another generalization bound for L.T SSMs, but they aim to consider the temporal dependencies in the input signal via its mean and variance, leading to a Hölder continuity condition. Their bound, under a stability assumption, scales logarithmically with I and is derived for continuous-time SSMs. Thus, in practice, only applies when the discretized model remains close to its continuous-timg counterpart. In contrast, we directly consider continuous-time SSM with an input-dependent time scale, and derive a generalization bound for the resulting discrete-time model an assumption more aligned with how such models are used in practice. In summary, while existing techniques for SSMs leverage system- theoretic properties unique to LTI systems, the nonlinearity of selective SSMs requires deriving bounds that are better suited to modern deep learning architectures.
Overall, our results complete the picture of generalization for deep sequence models. Strongest generalization occurs in selective SSMs with 8 < 0, softmax-attention. and RNNs with |||| < 1, all benefiting from implicit normalization stabilization. In contrast, selective SSMs with $ 0 generalize poorly. We revisit this in the next section, showing that no sub-exponential bound can be derived using Rademacher complexity in this regime. Later on in Section 5, we observe that the training error grows rapidly unless SA is driven negative, as seen in Figure 1.
4.1 A Lower Bound on the Rademacher Complexity
In this section, we present theorem that establishes a lower bound on the Rademacher complexity for the case where the spectral abscissa satisfies SA& 2 0.
7

---

1240
2014
3014
10"4
2012
22-4
609
107
201
Epoch
Epoch
Epoch
0.150
0.225
0.25
6.155
0.00
397
3025
550
0.55
-1025
Epach
Epoch
Epoch
Training loss vs epochs for Left: Majority, Middle: IMDb, Right: ListOps. Bottom: Evolution of A vs epochs for the same datasets. All runs use an unstable initialization with &л 0.1. Whenever training successfully reduces the loss, the spectral abscissa is driven toward zero, indicating that the system becomes stable. In cases where does not decrease toward training is not successful.
Figure Experiment 1. Top:
3.300
5.375
5,750
0.8
Accuracy
5.325
3,200
0.7
9.375
5.150
0.6
9:325
05
50
150
150
200
250
300 350
450
05
250
550 750
1850 1250 1503 1750 2000
5.300
200
400
600
630
1000
Sequence Length
Sequence Length
Sequence Length gth
Figure 2: Experiment Left: Majority, Middle: IMDb, Right: ListOps. Train test accuracy versus se- quence length T for models initialized with 8л = 0. The results demonstrate length-independenl generalization. Each experiment is repeated five times with different random seeds; the dashed line denotes the mean accuracy across runs, and the shaded region represents standard deviation.
Theorem 4.1. Let SA be fixed spectral abscissa and S (((() p C 117 then
If/wl s B...
Rads( > BB, (1+ 8A) -
V
2
(19)
SA
km
Moreover, if = 0, then
Radg(FFsM) 2 23 T
(20)
mm
The proof of the theorem is provided in Appendix G. is based on the construction of restricted subclass of selective SSMs in which the step size is fixed and the output grows unboundedly as function of a single parameter w. In this simplified setting, the Rademacher complexity can be computed explicitly, yielding a lower bound on the Rademacher complexity of the broader class FSSM- Unfortunately, these lower bounds are looser than corresponding upper bounds by factor of OTT), suggesting that there is room for improvement in at least one of the bounds. Nevertheless, they demonstrate an important fact: the dependence on in the Rademacher complexity cannot be eliminated when A 0. Specifically, it must grow at least exponentially when 8 0.

---

5 Experiments
To validate our theoretical findings, we conduct two sets of experiments on three datasets 2. The first experiment examines the effect of a positive spectral abscissa. demonstrates that when the system matrix is initialized with positive SA. training may fail, especially for longer sequences, rendering the generalization gap ill-defined. Since this gap is defined as the difference between train and test error, if one of these two terms is not well-defined, it would be meaningless to evaluate their difference. In the second experiment, we initialize the state matrix with 8 A = 0 and study how the generalization gap evolves with increasing sequence length. The model architecture used in the experiments consists of an embedding layer, followed by a single selective SSM block. The model is trained using cross-entropy loss. To stabilize training, we employ a regularization function from Keller [37]. Below, we describe the tasks with their corresponding datasets, followed by our analysis of each experiment.
The first task employs synthetic "majority" dataset, where each input sequence consists of binary symbols {0, J. embedded into a d-dimensional vector. The objective is to predict whether the sequence contains more ones than zeros. The output depends uniformly on all input positions: no single position has disproportionate influence, and the prediction is not determined by small subset of the input sequence. This makes the task well-suited for measuring trends in generalization gap w.r.t. the sequence length T. During training, noise is introduced by randomly flipping small percentage of the inputs after labeling, adding a layer of difficulty. The noise limits the model's accuracy around 95%, preventing it from overfitting despite the simplicity of the task.
Majority:
IMDb: The second task is binary sentiment classification using the IMDb large movie review dataset [38] containing 50K reviews. Each review is labeled as positive negative based on its sentiment. This task poses a real-world challenge due to its high variability sequence lengths and the need for contextual understanding. To control sequence length during training and evaluation, we pad/truncate sequences to fixed T. For shorter sequences (T S 300), sentiment indicators are often clear early, aiding prediction, while longer sequences often require retaining more context for accuracy. Thus, truncating them leads to substantial decrease in model performance, as seen in the test loss in Figure 2. The average review length in the dataset is around T 300. Therefore, the test loss and generalization gap both stabilize after T = 300, indicating that enough information is preserved for the model to generalize effectively. This is explained thoroughly in Appendix B.2.
ListOps: The third task uses the ListOps dataset [39], a synthetic benchmark that evaluates a model's ability to reason over hierarchical sequences. Each input is bracketed expression with nested operations, for example [MIN 1 [MAX 2 9] O], which evaluates to a single-digit integer. The challenge lies in the fact that the correct output depends on the entire nested structure rather than local context. We use the version from Tay et al. [40] to align with standard long-sequence benchmarks.
This experiment investigates the behavior of the spectral abscissa SA during training. To better understand the role of stability in training selective SSMs, we deliberately initialize all models in an unstable regime with S 0.1. The key observation here that successful training accompanied by SA being driven toward zero. We observe that as the sequence length T increases, the initial loss grows exponentially, making it increasingly difficult for the model to escape instability. This ultimately causes training to fail for longer sequences. Since successful training consistently corresponds to S approaching zero, we consider the regime with SA < as the stable operating region when analyzing the generalization gap in the next experiment. These results are illustrated in Figure 1.
Experiment 1 (Stability Under Training):
Experiment 2 Senggth-Indepnneen Generalization): Here we evaluate the generalization behavior across varying sequence lengths. Unlike Experiment 1, we initialize the models in marginally stable regime with SA= = 0, which results in smoother training. The models are trained and tested on sequences of different lengths, and we measure the generalization gap as the difference between training and test losses. As shown in Figure 2, this gap remains relatively stable across sequence lengths, with no consistent increasing or decreasing trend. These results support our theoretical claim that selective SSMs exhibit length-independen generalization behavior.
Interestingly, the mechanism behind this behavior is foreshadowed in Experiment I: when initialized in an unstable regime, the model naturally pushes S below zero during training, moving toward
Our code is available at pattps//githhn com

---

stability to enable learning. However, it stabilizes just enough to preserve rich temporal information. This suggests that selective SSMs are implicitly biased toward operating near the stability bound- ary. where they can extract long-range dependencies without incurring the exponential instability associated with longer sequences. This is manifestation of the trade-off between expressivity and generalization. In Experiment 2, starting near this boundary allows the model to train smoothly, leading to consistent generalization across different sequence lengths.
Conclusion and Future Work
In this paper, we derived new generalization gap bounds for selective SSMs by leveraging their embedded linear-attention mechanism. As corollary to our main result, we obtained a bound for linear attention, which illustrates the underlying connections explicitly. Our analysis revealed that the spectral abscissa A of the continuous-time state matrix A. governs selective SSMs' generalization behavior: models with A 0 enjoy length-independent guarantees, while those with 8 > 0 suffer exponential growth in error. Finally, our experiments supported these theoretical findings, showing that models satisfying $ < 0 indeed generalize well on long inputs. An important direction for future work is to improve these generalization error bounds. This could involve refining the analysis under alternative assumptions exploring different techniques, such directly bounding the Rademacher complexity instead of relying on covering- arguments. Another promising avenue is extend generalization analysis other variants of deep architectures.
7 Limitations
This work considers a selective SSM as the discretization of a continuous-ting state-space model, following the formulation used in Mamba. Hence, the theory developed here does not directly apply other variants of selective SSMs where, for example, the matrix A(u) exhibits a different dependency on the input. This work assumes that the training and test data drawn from the same distribution. -uttof-disttibuttin generalization of selective SSMs is not addressed. For a recent analysis of length generalization, specific type of out-of-distribution setting where test sequences are longer than those seen during training, the interested reader is referred to Buitrago and Gu [41].
8 Acknowledgments
This work was partially supported by NSF grants CNS-2038493 and CMMI--208188, AFOSR grant FA9550-19-1-0005, and ONR grant N00014-21-1-24311
References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Informa- tion Processing Systems, volume 30, page 6000-6010, 2017.
[2] Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré. Combining recurrent, convolutional, and continuous-time models with linear state space layers. Advances neural information processing systems, 34:572-5855 2021.
[3] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022.
[4] Rudolph Emil Kalman et al. new approach to linear filtering and prediction problems [j]- Journal of basic Engineering, 82(1):35-44 1960.
[5] Dániel Rácz, Mihály Petreczky, and Bálint Daróczy. Length independent generalization bounds for deep ssm architectures. In Next Generation of Sequence Modeling Architectures Workshop at ICML 2024, 2024.
[6] Fusheng Liu and Qianxiao Li. From generalization analysis to optimization designs for state space models. Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMgR.org, 2024.
10

---

[7] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces, In First Conference on Language Modeling, 2024.
[8] Tri Dao and Albert Gu. Transformers are ssms: generalized models and efficient algorithms through structured state space duality. In Proceedings of the 41st International Conference on Machine Learning, pages 10041-10071. JMLL.. 2024.
[9] Ameen Ali, Itamar Zimerman, and Lior Wolf. The hidden attention of mamba models, arXiv preprint arXiv:2403.00 01..000.0099..0. 5900, 2024.
[10] Annan Yu, Michael W Mahoney, and N Benjamin Erichson. Hope for a robust parameterization of long- memory state space models. In The Thirteenth International Conference on Learning Representations.
[11] Nicola Muca Cirone, Antonio Orvieto, Benjamin Walker, Cristopher Salvi, and Temy Lyons. Theoretical foundations of deep selective state-space models. In The Thirty-eighte Annual Conference Neural Information Processing Systems, 2024.
[12] Yash Sarrof, Yana Veitsman, and Michael Hahn. The expressive capacity of state space models:
A formal language perspective. In The Tiiht Annual Conference on Neural Information Processing Systems, 2024.
[13] Vinoth Nandakumar, Qiang Qu, Peng Mi, and Tongliang Liu. State space models can express n-gram languages. Transactions on Machine Learning Research, 2025.
[14] Aleksandar Terzic, Michael Hersche, Giacomo Camposampiero, Thomas Hofmann, Abu Sebas- tian, and Abbas Rahimi. On the expressiveness and length generalization of selective state space models on regular languages. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages
2025.
[15] Annan Yu and N. Benjamin Erichson. Block-biased mamba for long-range sequence processing. In Proceedings of the 39th Conference on Neural Information Processing Systems (NeurIPS), 2025.
[16] Zhiyang Wang, Juan Cerviño, and Alejandro Ribeiro. Generalization of graph neural networks robust model mismatch. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 21 21402-21410, 2025.
[17] Sanae Lotfi, Yilun Kuang. Mare Finzi, Brandon Amos, Micah Goldblum, and Andrew G Wilson. Unlocking tokens as data points for generalization bounds on larger language models. Advances in Neural Information Processing Systems, 37:9229-999 122622999956,.. 2024.
[18] Yunjuan Wang and Raman Arora. On the stability and generalization of meta-learning. Advances in Neural Information Processing Systems, 77:83665-83771 2024.
[19] Jin Zhang, Ze Liu, Defu Lian, and Enhong Chen. Generalization enror bounds for two-stage recommender systems with tree structure. Advances in Neural Information Processing Systems, 37:37070-37099, 2024.
[20] Yi-Fan Zhang and Min-Ling Zhang. Generalization analysis for label-specific representation learning, Advances in Neural Information Processing Systems, 37:104904-104933, 20244
[21] Rayna Andreeva, Benjamin Dupuis, Rik Sarkar, Tolga Birdal, and Umut Simsekli. Topological generalization bounds for discrete-tima stochastic optimization algorithms. Advances in Neural Information Processing Systems, 37:4765-4815 2024.
[22] Kaibo Zhang, Yunjuan Wang, and Raman Arora. Stability and generalization of adversarial training for shallow neural networks with smooth activation. Advances in Neural Information Processing Systems, 37:161 16-11699 2024.
[23] Uday Kiran Reddy Tadipatri, Benjamin David Haeffele, Joshua Agterberg, and Rene Vidal. convex relaxation approach to generalization analysis for parallel positively homogeneous networks. In The 28th International Conference Artificial Intelligence and Statistics, 2025.
11

---

[24] Tong Zhang, Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-550, 2002.
[25] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Speccrally-norrmaiizedd margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[26] Benjamin L. Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and vari- able creation in self-attention mechanisms. In International Conference on Machine Learning, pages 5793-5831. PMLR, 2022.
[27] Jacob Trauger and Ambuj Tewari. Sequence length independent norm-based generalization bounds for transformers, In International Conference on Artificial Intelligence and Statistics, pages 1405 1413. PMLR, 2024.
[28] Lan V Truong. On den-deeendent generalisation error bounds for transformers. arXiv preprint arXiv:2410.11500, 2024.
[29] Jimmy T.H. Smith, Andrew Warrington, and Scott Linderman. Simplified state space layers for sequence modeling. In The Eleventh International Conference on Learning Representations. 2023.
[30] Richard M Dudley. The sizes of compact subsets of hilbert space and continuity of gaussian processes, Journal of Functional Analysis, 1(3):290-330, 1967.
[31] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[32] Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds of family of recurrent neural networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020, 2020.
[33] Jiong Zhang, Qi Lei, and Inderjit Dhillon. Stabilizing gradients for deep neural networks via efficient svd parameterization. In International Conference on Machine Learning, pages 5806-5814. PMLR, 2018
[34] Shida Wang and Qianxiao Li. StableSSM: Alleviating the curse of memory in stace-space models through stable reparameterization. In Forty-first International Conference on Machine Learning, 2024.
[35] Fusheng Liu and Qianxiao Li. Autocorrelation matters: Understanding the role of initialization schemes for state space models. In The Thirteenth International Conference Learning Representations, 2025. URL /ttt:p::///peereiieie
[36] Xuewei Cheng, Ke Huang, and Shujie Ma. Generalization and risk bounds for recurrent neural networks. Neurocomputing, page 128825, 2024.
[37] Yannik Keller. Solving vanishing gradients from model parameter collapse. substack. com/ hhmm/p/oolving-..ee http://slvinggvaiihinng www.ge/aisnnngggggtttttsss----oe gradients-from?r- attps://yanmikkellles suw.sstall.r..s.ckk...aaa
Savpp/ttti.odledireece..... 2024.
[38] Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pages 142-150, 2011.
[39] Nikita Nangia and Samuel Bowman. Listops: A diagnostic dataset for latent tree learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pages 92-99, 2018.
[40] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena : A benchmark for efficient transformers. In International Conference on Learning Representations, 2021.
[41] Ricardo Buitrago and Albert Gu. Understanding and improving length generalization in recurrent models. In Forty- International Conference on Machine Learning.
12

---

[42] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. 3rd International Conference on Learning Representations (ICLR), Conference Track Proceedings, 2015.
[43] Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXi:: 2018.
[44] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 13:1877-1901, 2020.
[45] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
[46] William Peebles and Saining Xie. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4195-4205, 2023.
[47] Jinyang Liu, Wondmgezahu Teshome, Sandesh Ghimire, Mario Sznaier, and Octavia Camps. Solving masked jigsaw puzzles with diffusion vision transformers. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 23009-23018 2024.
[48] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: with optimal polynomial projections. Advances in neural information processing systems, 33: 1474 1487, 2020.
Recurrent memory
[49] Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the parameterization and initialization of diagonal state space models. Advances in Neural Information Processing Systems, 35:35971-35988 2022.
[50] Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. In International Conference Machine Learning. PMLR, 2023.
[51] Pierre Alquier. User-friendly introduction to pac-bayes bounds. Foundations and Trends@ in Machine Learning, 17(2):174-333 2024. doi: 10. 10.1561/2200000100.
[52] David A McAllester. Some pac-bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory, pages 230-234, 1998.
[53] Aolin Xu and Maxim Raginsky. Information- analysis of generalization capability of learning algorithms. Advances in neural information processing systems, 30, 2017.
[54] Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, pages 3437-3452. PMLR, 2020.
[55] Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy. and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. Advances in Neural Information Processing Systems, 2020.
[56] Marek Karpinski and Angus Macintyre. Polynomial bounds for ve dimension of sigmoidal and general pfaffian neural networks. Journal of Computer and System Sciences, 54(1):169-176. 1997.
[57] Pascal Koiran and Eduardo D Sontag. Neural networks with quadratic dimension. journal of computer and system sciences, 5401):190-198, 1997.
[58] Eduardo D Sontag. A learning result for comtinuous-time recurrent neural networks. Systems & control letters, 34(3):151-158 1998.
[59] Eric Baum and David Haussler. What size net gives valid generalization? Advances in neural information processing systems, 1, 1988.
13

---

[60] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11. 1998.
[61] Roman Vershynin. Hligh-dimensional probability: An introduction with applications data science, volume 47. Cambridge university press, 2018.
[62] Shai Shalev-Shwarlh and Shai Ben-David. Understanding machine learning: From theory algorithms. Cambridge university press, 2014.
[63] P.I.. Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 44(2):525-536, 1998. doi: 10.1 10.1109/1..66 1..11..2..
[64] Peter L Bartlett, Olivier Bousquet, and Shabar Mendelson. Local rademacher complexities. The Annals of Statistics, 33(4): 147--1377 2005.
[65] Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks lipschitz augmentation. Advances in neural information processing systems, 32, 2019.
[66] Mehryar Mohri Foundations of machine learning, 2018.
14

---

A Related Work
Self-attention is the core mechanism behind the Transformer architecture, introduced as an alterna- tive to RNNs and CNNs for sequence processing [1, 42]. While the concept of attention predates the Transformer, its introduction marked pivotal shift in the scale of large models. An attention mechanism assigns scores to each pair of elements in sequence to measure their relevance to each other. The self-attention mechanism, drawing inspiration from the key-query analogy used in rela- tional databases, captures dependencies between elements of an input sequence, where inputs attend to each other within the same sequence. Since their introduction, Transformers have been extensively studied and refined, leading to numerous variants, including sparse and low-rank adaptations and widespread applications across domains such as natural language processing [43, 44] and computer vision [45-47] Related to our work is the connection between SSMs and attention [8, 9].
State-space models are a new class of foundation models, introduced by Gu et al. [2] as an alternative to Transformers for sequence processing. Rooted in the classical state-space representations intro- duced by Kalman et al. [4] control theory. SSMs leverage state-space representations to efficiently model long-range dependencies in sequential data. The foundation of SSMs can be traced to the HiPPO framework, which established mathematical basis for encoding and preserving long-range dependencies using orthogonal polynomial projections [48]. Building on this foundation, the first practical implementation of SSMs is the S4 model, which utilized HipPO as an initialization scheme [3]. With the empirical success of S4 on the Long Range Arena benchmark [40], SSMs gained widespread attention, prompting several extensions and refinements. S4D simplified training with diagonal initializations [49], S5 introduced multi-input multi-output structure for greater flexibility [29], and Hyena explored hierarchical convolutions [50]. Selective SSMs introduced in the Mamba model by Gu and Dao [7] extend LTI SSMs by using linear projections of the input to construct and discretize SSMs, resulting in a nonlinear time-varian architecture. These properties make selective SSMs closely resemble self-attention, highlighted by Dao and Gu [8] while introducing Mamba-2.
Generalization bounds are central the probably approximately correct (PAC) learning frame- work, which formalizes model's ability to achieve low error on unseen data with high probability, provided sufficient training data. The PAC-Bayes framework provides probabilistic guarantees on generalization through a KL divergence between posterior and prior distributions [51, 52]. In the information-theoreee framework, the generalization gap is controlled by the mutual information between training data and model parameters [53-55]. Earlier studies explored statistical guarantees based on VC-dimension and shattering bounds extensively [56-60]. A related line of work uses Rademacher complexity to control the generalization gap, often through chaining and Dudley's integral, leading to margin- or norm- norm-based bounds [30, 61-63, 25]. This framework was later refined through local Rademacher complexity [64], which focuses on subsets of the hypothesis class near the empirical minimizer, yielding sharper bounds for deep models [65]. The recent works on norm-based generalization bounds utilize covering numbers, fundamental tool for bounding the capacity of function classes [61]. Zhang [24] laid the groundwork for understanding the capacity of regularized
linear function classes through covering numbers. Later, Bartlett et al. [25] established generalization bounds for neural networks using covering numbers based on the work of Zhang [24]. These methods have been extended Transformers in recent studies [26-28], where different aspects such as length or rank dependency have been emphasized. For LTI SSMs, the works of Rácz et al. [5], Liu and Li
[6] draw inspiration from this line of research but primarily leverage the structure of LTI systems to derive their bounds from a state-space perspective.
B Experimental Details
In both experiments, we employ an embedding layer implemented using torch. nn. nn....n.... Embedd ing, which maps input tokens into a continuous vector space. This is followed by selective SSM block, configured with N = states per channel and d 16 channels. The selective SSM block is parameterized as
store A. structured as a d matrix OssM = (A., WB, w.
where each component is defined in Section 2.2. The matrix A. E Ndx.N represents the state matrices across channels. In the code implementation, where each row of A. corresponds to the diagonal elements of a distinct diagonal state matrix (J) E NxN for channel j. where j {l....,dl d). This parameterization follows the official A
15

---

implementation of Mamba [7], ensuring computational efficiency while maintaining expressive capacity. The remaining parameters in θssM have the exact dimensions described in Section 2.2:
WB. We E RNNdd Q E Rd, and p R. The first experiment investigates how the stability margin affects training, particularly showing that the initial loss grows exponentially with sequence length T when A 0. To focus on early training dynamics, we train for only 10 epochs using 10% of the dataset, balanced across labels, to control loss magnitude and avoid label bias. In contrast, the second experiment uses the full datasets to train models to convergence and evaluate the generalization gap. The second experiment is repeated five times with different random seeds. For very long sequences in the IMDb dataset, preventing the model from stabilizing during the first few epochs. In such cases, we retry with a different seed that yields non-NaN value in the first epoch. The final results are reported as the mean over five successful runs + one standard deviation.
with S = 0 initialization, training may fail even at the very first stage,
B.1 Majority Dataset
Train
Test
12-
Frequency
8-
2-
25 50
75
1000
125
150
175
200
Number of
Figure 3: Majority. Histogram of ones, m 1000 samples each for train and test, sequence length T 200.
Majority is synthetic dataset similar to the dataset used in the experiments of Trauger and Tewari [27]. but with modifications. Each sample consists a sequence of ones and zeros, forming the basis of binary classification task. The class label indicates whether sequence contains more ones than zeros. A sample sequence i1 with T = 20 and its label 2 would be as the following:
U1
[, 1, 0, 1, 1, 0, 1, 0. 1, 1,
0,
1, 1, 0, 1,0,,
21
Since the task involves only two unique elements, the vocabulary size is set to 2, and each element in the sequence is projected into embeddings of dimension d when they pass the embedding layer. Both the training and test sets contain ones and zeros across sequence lengths, we generate sequences such that the number of ones varies approximately evenly from 0 to T. To introduce some imbalance, we modify the training set by randomly flipping 10% of ones to zeros after generating the sequences and labels. As shown in Figure 3, this results in noticeable reduction in sequences with high number of ones. Specifically, towards the maximum sequence length T, fewer samples retain exactly I' ones due to these perturbations, altering the original distribution.
1000 samples. To ensure uniform distribution of
B.2 IMDb Large Movie Review Dataset
IMDb large movie review dataset [38] is standard benchmark for sentiment analysis models and part of the RangeRange Arena (LRA) benchmark [40]. The dataset contains 50,000 movie reviews, evenly split between positive and negative labels, and is divided into training and test sets of 25,000 reviews each. The task is binary sentiment classification, aiming to predict whether a review expresses a positive negative sentiment. The dataset's balanced nature ensures unbiased model evaluation.
We chose IMDb for its diverse sequence lengths, as shown in Table and Figure To train effectively, we used the entire dataset, truncating or padding sequences to fixed length. For our experiments,
16

---

7000
Train
Test
5000
Frequency
4000
3000
1000
500
1000
1500
2000
2500
3000
Sequence Length
Figure IMDb. Histogram of sequence lengths for both the training and test splits.
chose sequence lengths between 100 and 2000 tokens, based on the distribution observed in Figure 4. As shown in Figure 2 (bottom), test accuracy increases from 100 to 300 tokens, then stabilizes. The generalization gap, visible in the bottom plot, reflects this trend. The average sequence length is 314 tokens, with many sequences exceeding 300 tokens (Figure 4). Truncating sequences longer than 300 tokens results in the loss of valuable information, potentially reducing predictive accuracy, as demonstrated by the following examples.
Short Sample
Text: "I don't 't know why like this movie so well, but never get tired of watching it."
Label: Positive (1)
Length: 24
Long Sample
Text: "This movie was recently released DVD in the US and finally got the chance..."
Label: Negative (0)
Length: 1833
For shorter sequences, key indicators of the sentiment label often appear early in the text, making it easier for the model make predictions. However, for longer sequences, these indicators may not be immediately apparent, as the sentiment may be spread across the entire review. In such cases, retaining full context of the sequence becomes crucial for accurate prediction. This is particularly evident in the test loss observed in the bottom Figure 2, where truncating longer sequences results in a loss of critical context, reducing the model's 's accuracy.
Max
Min
Average
Median
Train 3127
13
314
233
Test
3157
10
307
230
Table 2: IMDb. Sequence length details for training and test splits.
B.3
ListOps Dataset
ListOps is a synthetic benchmark designed to evaluate a model's ability to perform hierarchical reasoning over long sequences first introduced in Nangia and Bowman [39]. Each sample in this dataset is a bracketed expression consisting nested mathematical operations, such as
MED 4 8 [MIN 2) 3].
which evaluates to single-digit integer. The correct label depends on the complete nested structure, making the task dependent on the entire length of the sequence. We adopt the preprocessed version provided by Tay et al. [40]. The vocabulary consists of digits, "l", "("""""")"" and operator tokens (MAX, MIN, MED, SUM). Sequence lengths are set between T 100 and T 1000 in increments of 100. For each sequence length, we generate data in the range [100k 5, 100k + 5).
17

---

B.4 Experiment 1: Bounded Parameter Norms
The following table provides an example training log from Experiment (IMDb, = 350). The spectral abscissa 9 is already plotted in Figure (bottom middle, orange line). At the beginning of a stable training cycle, in which A is successfully pushed toward from above and the loss drops significantly within 10 epochs, the parameter norms do not show strictly increasing trends. This supports the claim that these norms remain bounded. Additional logs are available in our GitHub repository.
epoch
4
P
1
Wall 2
Wa 1.1
We
Well
Aa 2
max x
Loss
0
0.100
1.43
4.12
7.68
51.0
7.40
48.5
9.51
7.39
1
0.069
1.46
3.89
7.12
45.9
6.85
43.4
9.41
7.07
6.4 x
10
3
0.005
1.62
3.56
6.53
41.4
6.33
39.1
9.21
6.49
347.7
5
-0.006
1.58
3.44
6.21
39.5
6.15
39.0
9.01
6.19
2.04
7
-0.009
1.58
3.37
6.05
38.6
6.13
39.0
8.84
6.00
1.00
9 -0.010
1.61
3.33
5.91
37.5
6.12
39.0
8.66
5.82
0.67
Table 3: IMDb. Parameter logs during training epochs for Experiment 1, 350.
B.5
Experiment 1: Sweeping Spectral Abscissa with Constant Sequence Length
12th
124
1071
1071
209
161
Epoch
0.2
0.15
0.30
0.0
0.05
0.00
0.55
0.02
0.00
-0.05
1.02
-0.05
-5.22
-015
Epoch
Epoch
Epoch
Figure 5: Experiment 1. Top: Training loss epochs for Left: Majority, T 250, Middle: IMDb. T 500. Right: ListOps, T 300. Bottom: Evolution of SA vs epochs for the same datasets. Wc sweep the 8 values from -0.1 to 0.1 in 0.02 increments.
To understand the effect of different initialization regimes in more detail, we conduct Experiment 1 again, but this time we sweep the S values while keeping T fixed. In order observe the full effect without encountering runs that diverge (i.e., contain NaN losses), we choose T 250 for 300 for ListOps. The results Figure are consistent 0) often lead to training failure due to exploding losses, as other parameters have not yet adapted to stabilize the system. In cases where training succeeds, A is quickly pushed toward zero from above, restoring stability. In contrast, stable initializations (s A < 0) enable smooth training and remain stable throughout for IMDb and ListOps.
Majority, T 500 for IMDb, and with those in Figure 1. Unstable initializations (where
For Majority, stable initializations below zero are also pushed toward zero, and some even end up slightly above (around S R 0.05), which is acceptable since other parameters (2 . B.,, and p) can compensate according to (15). The key insight is that initialization determines whether training can proceed stably. When A starts in an unstable region, large initial losses arise before other parameters can adapt, often causing divergence. In contrast, initializing in the stable regime enables smooth optimization and coordinated parameter adaptation, allowing PA to remain balanced through (15). Thus, proper initialization of A is essential for both convergence and stable expressivity.
18

---

C Useful Lemmas
Lemma C.I. Let B Ia @ WBu(t). Then, ||Ba|l2 B..
Proof.
BB 12 La W W W 1412 WB [B < B
(21)
Lemma C.2. Let C.
2 v( We. Then, ||Ca||2 < B.....
Proof.
||Col22= = | @ ult] we l1 = |u[|]] w = [| [oll23] s B2
(22)
Lemma C.3. Let and Y be matrices such that ||e* 112 S p and (cMl22 112 S p. Then,
|1e e e S P X 1/22-
(23)
Using the fundamental theorem of calculus, we express the difference as Proof.
+ + - X) dl.
(24)
Taking the spectral norm on both sides and applying submultiplicatiiity, we obtain
1 cx 1
11+11-1)x(- ( -X)
$ ((' ||( x) dt
(25)
/ 1exx+(1-11x 12 dl
I -1122
$ pl X112.
Lemma C.4. Let p be an ey-cover for p and be an cover for q. Then,
A|t A cp Cq.
(26)
Proof. The derivative of the soft plus function, In(1 + e²), is Ite= which is bounded by 1. Thus, In(1 + e²)) is 1-Lipschitz. using this property, we obtain
o"
| A[t]l In(1 + "+v alt) In(1 + e0t0 wwll]]]]]]
$ pp p+ + (q - 9) Tu([]]
(27)
< lp ø + (1( ④) T u[[]]l2
Lemma C.5. Let d be an -w-eover for w. Then,
|w" vT u y [
< Bw Blll i[T|Ila + cw
(28)
Proof. Rewriting the LHS, we obtain
w T y[T]- - o T ./T ww T (3[["] T(Tl) + (w w) "/7
(29)
Applying triangle inequality results in wo Tv[ i [
||l|||| Iyy T o + [(w u) [[
(30)
B [|][[]]
- si[]]l2 + cw-
19

---

Lemma C.6. Let Ce be an cc-cover C.. Then,
- - - BcBull[[T] - - ccc.
(31)
Proof. The LHS can bounded as follows:
- C (-[ X[T]) + (C, C.)&(T]l
(32)
- - + lI(C Cc)
Applying Lemma (C.2) completes the proof.
Lemma C.7. Let WR be a cover for WB. Then, for any E R&d such that ||li|2 = Bv we obtain
[I - B,)ull2 - B.llWWB - WB)uul2-
(33)
Proof. We use the Kronecker product property (X & Y) veo = vec (VVXT). Take X as La.
V UT, and Y (Wn n Wn, n)u obtain
[Be B.)ulle
La 2 (WB WB)u) u/12
(34)
vec (WB WB)Ur 112.
From the definition of the Frobenius norm, we obtain
([ - WB)wi T || I (I(
[[ Wn)ul/a/ell
(35)
< B.ll(WB WB)ull2.
Lemma C.8. Let We be a cover for We. Then, for any v E Rd such that ||l||2 = B,, we obtain
II(C. - (cCc-C,)ulle S B.ll(Wc - We)ullz.
(36)
Proof. Similar Lemma C.7.
Lemma C.9 (Edelman al. [26], Lemma A.8). For ai Br the solution the following optimization
Σ
min
o
Clomn i=l
(37)
subject to
Σ Bie =c
is 2xx and is achieved at E; 0x
where = Ei= a,
1/3
D Covering Numbers
Lemma D.1 (Bartlett et al. [25], Lemma 3.2). Let conjugate exponents (p,4) and (r, 8) be given
with < 2, as well as positive reals (a, b, E) and positive integer dy. Let matrix X E gdd xda be Then,
given with [ IIppp $
d2b2dd/
In (fXA: AE dada ||Algg. S [efte,l (1 <
1n(2dg)z).
(38)
Lemma D.2. Let FA. (A. E NdxNd ||Ac|12 S A and ||Ac|221 S MA Then,
112) 29n Nd
InA(FA. EA.ll
In In(V2Nd).
(39)
20

---

Proof. Note that every с ex-covering number for the Frobenius norm is also an eo-crrnnnng number for the spectral norm, as |
2 I
A A|l I cΛ. Therefore,
(F 112) < (F cA, -
(40)
< <InW([A, ({A. E EIR NaxNd ||A.|12. S MA). lIr).
Thus, we instantiate Lemma D.1 with b = vNd which results in
2 and & = 1,r = co. Take to be identity and thus
22 (V
InA[ E N.NdNd ||A.|22, S eA, 1l
In(2NdNd).
(41)
2
Lemma D.3 (Trauger and Tewari [27], Lemma 3.6). Let m 2 d2. Fw = {Wu w E
Rd xd2 W 111 S Mwwh }. If [|llll22 I B.. then
B (FW, ew, (12) 5
1n(2dgd2 + +
(42)
W
Remark. The removal of the dependency on m in the log covering number for function class is nontrivial and requires specific assumptions about the norm bounds. For similar log covering bounds that are independent of m, refer to [27] and the lemmas therein.
Lemma D.4. Let F be a function class such that In No. 11212) S f and let S be the training set {uee, =(t) j=r- Assume the loss function 1: Z x 2 - IR is upper bounded by the constant and Lipschitz continuous with constant 4, Then, with probability at least 1-
m E., ((((()))) 2)) m Σ (M(U()) 200)
12hCr vm
(
))
In
1 In
+ 30/
(43)
3CF
2m
Proof. By Theorem 3.2, and the fact that InN F, (12) s In (1 F,,,,, (12) (check Definition 1 in [24]), we have
4a + 12 1
NN de
Rad(I F, & inf as0
(44)
m
Upper bound (F,, e, m, (12) as specified by the lemma to obtain
Vm [0
12 s 4CF de
4a + 12CCF
(a))
s inf as0
4a
inf aso
(45)
e
Vm
in which we used No (1 F,6, || l12) s (F
112). The minimum of (45) occurs at
34Cz Thus, vm
a
124Cr 124C, Vm
+
In
Ci Ciym
124C,
1 (1+10)
Ci Ciym m
(46)
Vm
3C,
vm
3C,
Combining this bound the Rademacher complexity with Theorem E.2 concludes the proof.
E
Proof for Theorem 3.3: Generalization Error Bound for Selective SSMs
Before presenting the proof of Theorem 3.3, we provide preliminary background, including the definition of Rademacher complexity and a standard theorem establishing connection to the generalization gap. Then, we introduce four intermediate lemmas tailored to the selective SSMs. The first lemma establishes an upper bound on the spectral norm of the state matrix after repetitions, namely || | The second lemma bounds the distance between the time-varying product A' and its corresponding cover, accounting for the input-dependent nature of the state matrices. These two lemmas necessary and specific to selective SSMs, since, unlike standard RNNs, the state matrix
21

---

A is not fixed. As result, classical norm bounds do not directly apply, and we must instead derive upper bounds terms of the model parameters Acs p. and 9. which govern the input-dependent dynamics. The third and fourth lemmas build upon the first two to inductively bound the distance between the output of selective SSM and that of its corresponding cover. These results culminate in the proof of Theorem 3.3 provided at the end of this section.
Definition E.1 (Rademacher complexity). For a given real- real-valued Function class F and a set of vectors S (=)))) the empirical Rademacher complexity
Rad(F, -E,
sup /EF
orf(u()))
(47)
where E 1- are uniformly distributed i.i.d Rademacher random variables.
Theorem E.2 (Mohri [66]. Theorem 3.3). Let F be hypothsis class {f u + 2), and S be the training set {u(a) z(0) )t0 Assume the loss function : Z + is upper bounded by the constant Then, with probability more than 1 8
Bu. ((F(u))) - 1 Σ (f(u()) 20)
In(3) 2m
S 2 Rad(l F, + 301
(48)
Lemma E.3. Let SA be the spectral abscissa of Ag i.e max, (A.)). Suppose u[t] S B., and |llll2 S B. Then, given any arbitrary small > 0, there exists sufficiently large t such that
A 112 S p'a.
(49)
where
PA (1 + - B, 2.) eatn
(50)
Proof. From (9), we have
T-1
A 2|2
II i=T't
- jj4
(51)
Given the assumptions of the lemma, and noting that the softplus function, In(1 + e²), ), increasing, we derive the following lower bound:
ADJ 2 In(1 + el BBB.
(52)
Since the spectral abscissa of A. is sA. the spectral radius of e. would be e*A, By Gelfand's formula (Corollary 5.6. 14 in [31]), have that [1(AA.)'1 - e as co. Consequently, for an arbitrary small positive number > 0, there exists a sufficiently large 4a such that for all 2 4o. the following bound holds:
( S (e
This yields the desired exponential norm bound for large I:
|| A 1|2 = ((a)) Abil
< (e*a+))* 2 -00
(53)
= (1 + 6 -- B. (ea (ea+n)) = -pA--
Lemma E.4. We have the following upper bound on a:[]:
x [T]]l < 27 Bg 22 1- P3/
(54)
1-PA
in which PA (1+ ep- BB eatt )eatt and MA In(1 BB,
22

---

Proof.
x
A' WBulT 10---u--ff tl)u(T 1 1-1)
1111111111 @ WBu/T - - 1allal1 +]]l2)
(55)
S2A Br
Σ
||4'|12/Ta @ WBulT - 1
t=0
T-1
1- P²A
AA B B
Σ
A'A
2 B
PA
where we used Lemma E.3 to bound A and Lemma C.I to upper bound the term involving the Kronecker product derive the last inequality.
Lemma E.5. Let Ag be an eA-cover for A p be an c--cover for p, and q be an -o-eeveroor for Then,
|| 1 S (2T BAEA)
(56)
where Mi In(1 + ep+ 2,22)
Proof. We start with
A
A' 1
AIMA
II
AMA
k=
k=T-t
i-1 II k=T--
Σ
AbI
A AKi
(57)
T=
T-1 II j=++1
AAIAA
II CAMA h-T-t
Factor common terms to obtain
T-1
Σ
(AARAA- - AWA.)
II
2
(58)
II
AGIA
| -
11
II
1=
K=T-t
Applying Lemma E.3, we get
Σ
T-i-1 Ie - AVA.. 1120 I-I+
PA
T-
(59)
T-1
Σ PA
1 - _
T
Use Lemma C.3 derive
|| A 2 v A
Σ
A - ÁljAA11.
(60)
T=T-t
23

---

Apply triangle inequality:
A'A
[IA A.)ll2 || Ao1))
S AAA
Maca + - ((113))
(61)
-
S PAA
Σ
(MACA + B
At last, we obtain the final bound:
A
A' l S t AM + BACA).
(62)
Lemma E.6. Let A, B, Å be covers for A, B, Then,
T-1
Σ
A'A(T
1-1 (1 Σ Á' 1 (
1
- -1
(63)
1=0
2
MICBI
BB + BB u
(S1 + 2A82)
1-ph and S2 PA(t-PA) Tph
where S
I-PA
(I-PA)- 1-PA"
Proof.
Write the LHS as follows:
Σ
((''/T-1--D -1-AT-1-fH BB. Á'Â -1- 1 u(T ul
(64)
t=
Add
and
subtract the
terms
ΣTD 1 ult t
1] and
E (A' - -)) u(l 1-- 1] to derive
-'AfT-1-th A'AT- u(T u|T- - --11
A - 11..) u|T - -
(65)
u(T u/TT- ('' -1 B AAT - -1. - + 11]l22-
Apply the triangle inequality to get
[IA'AIT - 1- (B. B.)u(T 1- 1-1]1l2
(66)
+ +IA''A - 1 - 1 Å - -1 B)) - t- 1]]l2
+ +I(AA - A' - B.u - -- 1]11a) -11]ll1)
which is upper bounded by
(1 ABI[ B.)u(T 1|112
(67)
+ +1
11- 7 1 :|I|B.uu 1]1l2
+ IIAA' -A Â[T Bu -1]]ll)
24

---

The application of Lemmas E.3 and E.5 to bound | and cover || A' results in
P'' AEB Be (D 244s))Da/1B..l225)
(68)
Apply Lemma C.I to bound |
Σ
MAB / 2 B, + BAa)))
(69)
t=0
Breaking the summation into two parts leads to
T-1
T-1
< BB
Σ
P'A
+
BB BACa)
Σ
1p's
t=
1=0
PTA
PA(1 PAA
TPA
< (MaE + BBB
M2 BBBB (2N + BACA)
PA
(1-PA))
1 PA
which completes the proof.
Remark. Lemma E.3 is stated for sufficiently large t. In Lemmas E.5 and E.6 we still apply that bound when summing over all time indices. The step is legitimate because any >/-1 (.) be split at an index in for which the hypothesis of Lemma E.3 holds for f 2 In:
T-1
ΣO= t=0
E=
The first term involves only finitely many values of and therefore contributes constant that is absorbed into the leading O(-) -) rate. The second (tail) term is where the bound of Lemma E.3 is used, and it determines the asymptotic dependence on I'. Hence, omitting the constant part does affect the final Big-O expression in the main theorem.
Lemma E.7. Let A., Wn, Wo, P. be covers for Ao, B, Wc, P. q. Then,
JwTT[p [TT] T '[T]| = B., B
21 B.,, BB + BB. (S1 BAS (cp + Eg)
(70)
+ B,,, B.WWe + Ex:
where S₁ and S2 are defined as in Lemma E.6.
Proof. The proof follows from the sequential application of Lemmas C.5, C.6, and E.6, yielding:
w v[T] - á [[T < B., B.. (MA 2012 B BB + B (S) + 22 B BA)) + ew-
(71)
Finally, apply Lemmas C.7, C.8, and C.4 to relate the covers for B, A the covers for
WB. Wc,P,4 P,4. completing the proof.
Li
Proof of Theorem 3.3. We aim to construct a cover for the space of all selective SSMs FSSM (=[T] w y[ y(T) is descrihed in (8)) which is parametrizes by OSsM {A WB, Wc.P.q.ur w.. Let's look at how much the output w y[T] changes if move to the points in the c-net constructing the cover. This is done Lemma E.7. Thus, we need to choose CA. CWny Cues Eg. Ep and ew subject to the following:
= B,, BBB M. Stewa M2 B, BB BB B3 S
+ BBBB Be B:) (S1 + MA AA) (cp + cg)
(72)
+ B,, BREWe + Em
25

---

which relates the e-cover of a selective SSM to corresponding covers for each parameter in OSs as in (70).
Choose the covering for WB according to Lemma D.3 such that
2
Nn (Fwa: w |l
(122) S
In(2Nd+1),
(73)
CWn
Similarly, choose the covering for We by replacing in Lemma D.3 with x[[] which is bounded as in Lemma E.4 to derive
(Ma 2 (3,5,
20
N (Fwo: 11)))))
In(2dNd
WW B2
(74)
21 2n 2 S2
B
In(2Nd 1).
We
Likewise, choose the cover for w such that
(M Bc 2B 20
In (Fre w. Cas 111122 =
Ind + 1)
(75)
22 22 B B 2 Sf
In + 1).
Lemma D.2 gives the upper bound on the covering number for A.:
20023 Nd
InN Aor CA.ll (122) S
In In(V2Nd).
(76)
A
We may use Lemma D.3 again to cover q:
In (Fa (12)
(nd + 11
(77)
and p is covered simply by
2/pl
Noc (F:: Cp. 12)
(78)
Ep
Ignore the logarithmic dependencies and assume Wc = Bc, My BB, My, = Bw. My
BB, Bg. A B A for simplicity. Construct the cover for the space of all selective SSMs FSsM as the Cartesian product of all covers for each parameter in OssM- Then, the log covering number would be the sum of the log covering numbers of all parameters. Use Lemma C.9 find 6,, eWg Cueo Egg Eqp. and e such that the size of total cover would be minimum:
2 Wn (FssM, e, (12)
< ő ((8
1/3 (B, B
+ (B 2% (B 27/
+ (23, Ne)
B
2/3
(B) 23 23
(79)
+ (2 ( B
(S + M 22
in which ignored the cover for it is dominated by other terms.
6 ( ( 22 23
2/3 52/5 + //// 52/3
+ an 3 2/3
2/3 22 /1/3
22 22233//////2222 23 2/3 5213 C
(80)
+ on 2/3 23 2/3 B² 2/
B 8 2/3 2/3
where we used the fact that S is dominated by S2 for large T to obtain the last term. Therefore, we have
< S m B2 B B2
22/ + 2/33 my 2 5213 1/
(81)
+1+ B² 2/33 /3353/3
3/33 3
26

---

Ignoring the constant terms and S1 compared to S₂ results in
S S 2 B B 22 2 S2 (Mm /3 /1/3 +B2 22/33///33
(82)
The square root of this expression is Cy. The proof is complete by the application of Lemma D.4.
F Proof for Proposition 3.4: Genralization Error Bound for Linear Attentions
Proof of Proposition 3.4. The proof that follows is similar to the proof of Theorem 3.3 with modifi- cations accounting for the simplifications made Assumptions 3.5 and 3.6. Specifically, we do not need to cover Ac, P. q. Therefore, Lemma E.6 simplifies to
Σ (WB- WB) ulT
T EWa
(83)
Consequently, Lemma E.7 becomes ww" T [[ - T ल[7)
& T., Bc 2², CWn + Bw Bn CWe + Cw-
(84)
Also, Lemma E.4 reduces to
| < T T B
(85)
which is used to cover We. Hence (79) becomes
(FLA., l12) s Ō (B) 1 Bc
(T B2 B 33 (Bw 3 (T B
(86)
o B3 By 8 B
By applying Lemma D.4, the proof is complete.
G Proof for Theorem 4.1: Lower Bound on the Rademacher Complexity
Proof of Theorem 4.1. We consider restricted class of scalar (d N 1) selective SSMs defined by
- In(1 SA), WB We p == e, q 0, w S B
(87)
Since θ OSMM the Rademacher complexity of this restricted class provides lower bound for that of the full class FSsM- For this class the step size would be fixed A [k] 1, and the discretized matrices become
AK 1 +
B u(k:),
C(k] m((A)-
(88)
Thus, the resulting state space recurrence is
[t] (1 =k 1] n (R]),,
y k n [R.)
<|<] w
(89)
With constant input u[[:] 1, the closed-form expression for the output becomes
(1 SA) T
T = w
(90)
3
Hence, the hypothesis class can be expressed
+ SA)T
F
|w] S B
(91)
SA
The empirical Rademacher complexity is then
(Fi) = -
1
E,
sup W
[T)
(1 (L+ SA)A
E
sup
W
m
0:
(92)
m
8A
m
[w|5
i=1
27

---

The supremum is achieved when = Bw sign (Ei=1 σi), yielding
(1 SA)
2
(ads(Fi) = Bir
(93)
$A
mm
When SA O, the recursion becomes =[k] r(k 1] 1, x x| T. and hence =[7] wT.
The resulting hypothesis class is {wT] [/ S B..) , and similar argument yields
2
Rads(Fi) B mm
(94)
H
Extra Discussion
Note that the term S2 in Theorem 3.3, derived in Lemma D.6) is
S PA p²)
TØT
(1 PA)²
PA
This expression does diverge as PA + even though there - PA in the denominator. Applying I''Hôpital's 'ss rule twice yields
T T
S2
2
which is finite. Therefore, although increasing PA degrades generalization, the generalization bound does not blow up at Pa 1; rather, it remains bounded and grows quadratically with T. The generalization becomes severely damaged only when PA > 1, where the bound becomes exponentially increasing in OTTP)))
Proof that the bound remains finite as p 1.
We compute
lim p(1 p(1-pT)
Tp lim
Tpp + (T - 11p
p] p) 1 1-p) p)
p+1
(1 p1
First derivatives:
numerator) =1 2-11
TT + (T 1)p"
dp (denominator) -22(1 p).
Second derivatives:
dp numerrator) -1)
7'-2 12p + T(T - 1)p²-1
(denominator) = 2.
Evaluating at p - gives
p(1 pF) Tp²
T T
lim p+l (1 p)
1 0
2
28

---

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

---

Answer: [Yes]
Justification: We present the assumptions for the main theorem in Assumptions 3.1-3.4, and justify them immediately following their statement. A proof sketch is included in the main text, while the full proof, with all technical details and supporting lemmas, is provided in the Appendix. Assumptions for other theoretical results are also stated precisely, and all corresponding proofs are given rigorously in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our code is accessible at: https://github: com/ Arya Howaooonnsseeeeeeeeeeeee _oo_err_se____
The model used in the experiments is implemented exactly as described in Section 2.2. Training follows standard procedures, and all necessary information for reproducibility is provided the paper. Additional implementation details are included in Section B, they could not fit within the main paper due to space constraints.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., s., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
30

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our code is accessible at: httpa:///gttab...oomm/rrrrraappp ren_err_sel_see
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ mhips.cc/publle wwwpg//gg////ee/eee/oeecceeses CoodeSubeeeeeeee wwttamiissiiooooiiiiiiio
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provided all the relevant details of the experiments. Note that additional implementation details provided in Section as they did not fit within the page limit of the main paper.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The main experiment of this paper is repeated five times. The corresponding figures include error bars to illustrate the statistical significance of the theoretical claims.
31

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Our experiments were conducted solely to evaluate the generalization perfor- mance of the model, without considering any metrics related to computational efficiency. Therefore, did not report compute resources, they irrelevant in the absence of compute time or related performance indicators, which fall outside the scope of our interest.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: https://neete httt::::///eripps/
Answer: [Yes]
Justification: The research presented this paper is fully consistent with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
32

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper focused on understanding deep learning models, and it poses no societal impact concerns.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This a theoretical study focused on understanding the fundamental properties of deep learning models. As such, it does not involve any high risk misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
33

---

Justification: We implemented our models and experiments in Python using Py Torch. We used the IMDb dataset [38] and ListOps Nangia and Bowman [39], which are publicly available and were used under their standard terms of use. Additionally, we used small code snippet from Substack article by Keller [37], which publicly available. The author retains ownership of the content, and no explicit license is provided. We have credited the author in our paper and provided a link to the source. The code was used solely for research purposes and was not redistributed or modified beyond what is permitted under fair use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. ctt..coo//ccoooo.oooo datasatee has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have provided the code to reproduce the experiments of this paper. It comes with the same license as the paper: CC BY-NC-SA 4.0.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
34

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpas://///pss///eeee cc/ oc//oonferncccs/2225///////// for what should or should be described.
35


Reviews:
[{"review_id": "jr50YEMO3H", "reviewer": "Reviewer_h1Pz", "summary": "The paper derives covering number-based generalization bounds for selective SSMs by connecting them to attention mechanisms. The main result shows that generalization depends on the spectral abscissa $s_A$ of the continuous-time state matrix: when $s_A < 0$, the bound is length-independent, but when $s_A > 0$, it grows exponentially with sequence length $T$.", "questions": "* In the IMDB experiment- why truncate at 300? why not use the maximal sequence length?\n* I'm not sure what is the purpose of Figure 1 - if you use unstable initialization for $s_A$, what is the experiment supposed to convey? The conclusion I can draw from this experiment is that optimization fails when the sequence length is too large.\n* The experiments that demonstrate $s_A>0$ leads to the conclusion that \"generalization is bad\" cannot be decoupled from the question of optimization. Do the authors have other means to show that generalization is bad in the unstable case?", "limitations": "This work is theoretical and assumptions are stated clearly.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths:\n\n- The paper is well written.\n- The topic of generalization bounds and guarantees that can be obtained for selective SSMs such as Mamba is important as our theoretical understanding of these models is still lagging behind their immense popularity.\n\n\n## Weaknesses:\n- The paper is overly complicated. While the reviewer can appreciate the technical difficulties in the analysis of such models and incorporating the selectivity mechanism. The authors could convey the main ideas behind the theoretical claims without the technical overhead introduced in Section 2 (specifically, many of the notations presented are not used in the main paper).\n- The paper lacks an in-depth discussion of related works. While many relevant works are discussed for the sake of the presentation and comparison in Table 1 - a dedicated section that discusses different theoretical results on the theory of generalization and optimization of sequential models is missing.\n- Experimental section is very weak - the first experiment does not prove anything about generalization. When using unstable initialization for $s_A$ the authors are simply showing that optimization fails, this has nothing to do with generalization.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the clarity and significance of our work and for their constructive feedback. Below, we address the weaknesses and questions raised:\n\nWeaknesses:\n\n1. We thank the reviewer for their time and for raising this point, which allows us to clarify the motivation behind the structure of our paper. The main finding of this paper is a generalization error bound where all of our analysis and experiments revolve around. While the high-level idea is simple, the derivation requires a deep understanding of specific topics in both learning theory and dynamical systems. We agree with the reviewer that these topics might be complicated for the readers, and to avoid this problem we took the following measures:\n\n- Section 2 provides a mathematically rigorous background on selective SSMs, ensuring all components are well-defined. This was intended to remove ambiguity present in prior works, including foundational SSM papers, where key concepts are often described visually or heuristically.\n\n- Section 3 conveys the intuition behind Rademacher complexity, covering numbers, and their connection to generalization in a verbal manner before presenting our main result. The detailed technical proof is omitted from the main body for accessibility and presented in the appendix instead.\n\nRegarding notation, all introduced symbols are used in the paper except for $\\Im$, which was included for completeness alongside $\\Re$. We believe introducing notation upfront promotes clarity, even if some terms are referenced only once. Further simplification would risk omitting critical definitions and make the main contribution, our generalization analysis, difficult to follow. Our intent was to provide a clear and self-contained exposition without overwhelming the reader with technical details in the main text.\n\n2. We thank the reviewer for this valuable feedback. The paper already contains a significant amount of material, so a dedicated Related Work section with detailed discussion was omitted to keep the main text concise. Instead, we aimed to include recent and significant works in the Introduction and provide direct comparisons with SOTA results on other models in Table 1 and the analysis section to show how our results extend them. Nonetheless, we agree with the reviewer that a more in-depth discussion of related work would be beneficial. In the revision, we will include a dedicated Related Work section, placed in the appendix to maintain readability. This section will survey generalization error and sample complexity bounds across several fields, including machine learning, deep learning, system identification, and reinforcement learning. It will review generalization bounds based on model architecture, covering neural networks, RNNs, LTI-SSMs, and Transformers. In addition, it will discuss key analytical tools such as VC dimension, covering numbers, Rademacher complexity, and information-theoretic approaches.\n\n3. We thank the reviewer for this important observation and the opportunity to clarify the purpose of Experiment 1. As the reviewer noted, this experiment illustrates stability during training and does not directly address generalization. At first glance, a comprehensive generalization experiment might seem to require evaluating the generalization gap for both stable ($s_A \\leq 0$, or more precisely, $\\rho_A \\leq 1$ where $\\rho_A$ is defined in Theorem~3.3) and unstable ($s_A > 0$) regimes across varying sequence lengths. However, it is important to note that the generalization gap is meaningful only after training has converged. Experiment 1 is included to demonstrate that, in practice, the unstable case does not arise: regardless of the initial spectral abscissa, training pushes $s_A$ toward negative values to adjust $\\rho_A$ within the first few epochs. Its purpose is to justify why we do not report generalization gaps for the unstable region. In that regime, training does not succeed, so the model does not perform well on the training data, and thus it is meaningless to talk about how well it performs on the test data. With this clarification, we proceed to Experiment 2, which focuses on the stable regime ($s_A \\leq 0$ or $\\rho_A \\leq 1$) where the generalization bounds are meaningful and empirically supported. We will revise the text to make this reasoning explicit so that readers clearly understand the role of Experiment 1 and its connection to Experiment 2.\n\nQuestions:\n\n1. For the IMDb dataset, in the first experiment, input sequences are truncated to lengths $300, 350, \\ldots, 550$. For longer sequences, training fails at the initial stage, with the loss diverging to infinity. The second experiment truncates sequences to lengths ranging from $300$ to $2000$ to demonstrate the length-independence of generalization, which is the main objective of that experiment. Therefore, we do not limit truncation to length 300; rather, we go beyond it based on the experimental goal.\n\n2. We tried to address this point in our response to the third weakness, as it is closely related. We agree with the reviewer’s conclusion that Figure 1 demonstrates training failure rather than generalization performance. The purpose of Figure 1 is to show that it is not possible to obtain a well-trained unstable model. When the model does not perform well on the training data, it is not informative to evaluate its performance on the test data, rendering the generalization gap meaningless. This supports our focus on the stable regime in Experiment~2, where training succeeds and generalization can be meaningfully evaluated.\n\n3. We appreciate the reviewer’s insightful question. To support the claim that generalization degrades in the unstable regime, we provide a theoretical justification in Theorem 4.1. This result establishes a lower bound on the Rademacher complexity of the selective SSM class when $s_A > 0$, showing that it grows exponentially with the sequence length $T$. Since the generalization error is upper-bounded by the Rademacher complexity, this implies that no sub-exponential upper bound is possible in this regime. As for experimental validation, we agree with the reviewer that optimization and generalization are inherently coupled in this setting: meaningful generalization analysis requires successful training. Moreover, the bounds derived in our theorems are asymptotic and become valid only for large values of $T$, precisely where training fails when $s_A > 0$. For these reasons, it was not feasible for us to conduct empirical generalization experiments in the unstable regime."}, {"review_id": "0CGYuRB67D", "reviewer": "Reviewer_Bnv5", "summary": "This paper studies the generalization ability of selective state space models (selective SSMs), such as Mamba. Specifically, the authors derive an upper bound on the covering number of selective SSMs and use it to evaluate their generalization error. The key finding is that the generalization error is governed by the spectral abscissa $s_A$, i.e., the largest real part of the eigenvalues of the parameter matrix $A$ that appears in selective SSMs. The authors show that when $s_A > 0$, the generalization error grows exponentially with the sequence length, while when $s_A < 0$, the error becomes independent of sequence length. The proof leverages the structural similarity between selective SSMs and Transformers, enabling to use existing theoretical results for Transformers. The empirical section evaluates how $s_A$ affects the generalization ability of selective SSMs using both synthetic and real-world datasets.", "questions": "(Q1) When $s_A$ is small, it is expected that the model’s expressivity for long sequences is limited. Can the authors provide any insights into the trade-off between expressivity and generalization with respect to $s_A$?\n\n(Q2) In Experiment 1, the model failed to generalize for long sequences, but in Experiment 2, it did generalize. Is it correct to understand this as showing that initializing at $s_A = 0$ makes the model more likely to generalize even for long sequences?\n\n(Q3) Why did you plot the loss in Experiment 1 and the accuracy in Experiment 2?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n(S1) The main theoretical result is novel in showing that SSM-based models can achieve length-independent generalization error for $s_A < 0$.\n\n(S2) The experiments provide practical insights. Specifically, when initialized with $s_A > 0$, the model drives $s_A$ below zero during training if the sequence length is short enough for sufficient stabilization, while for longer sequences, $s_A$ remains positive. Additionally, it is shown that initializing $s_A$ near zero leads to generalization even for long sequences.\n\n**Weaknesses:**\n\n(W1) The abstract claims “we analyze how the spectral abscissa of the continuous-time state matrix governs the model’s training dynamics and its ability to generalize across sequence lengths.” However, the paper does not actually analyze the training dynamics.\n\n(W2) The fact that the properties of the matrix $A$ are important for the generalization of RNNs is already known in prior work. The authors likely consider it important that they extend this discussion to selective SSMs, and I agree. However, the paper lacks sufficient explanation of how the proof differs from those for RNNs. If similar techniques are used, this should be made explicit.\n\n(W3) As noted in Remark 3.2, the phrase “through the lens of attention” appears to refer to the use of generalization error analysis techniques for Transformers. However, it is not clear from the main text exactly which results from Transformer theory are used. Although the proof sketch of Theorem 3.3 contains the sentence “Recognizing the attention mechanism in (8), Lemma C.3 covers the parameters {WB, WC, q, w} by treating them as linear function classes,” this explanation is too abstract and difficult to understand.\n\n(W4) Minor: The $A$ in $s_A$ in eq. (15) should be bold.", "was_revised": true, "final_justification": "This paper theoretically investigates the generalization ability of selective SSMs, exemplified by Mamba. The claims are mathematically rigorous; in particular, the paper provides a novel result: for $s_A < 0$, the upper bound on the generalization error is independent of sequence length. It is also commendable that the authors empirically show that the value of $s_A$ at initialization influences subsequent training.\n\nOn the other hand, I have the following concerns about the submission:\n\n* The technical differences from existing work on generalization error in RNNs are unclear.\n* The paper does not sufficiently explain in what sense the analysis is “through the lens of attention.”\n* There is no discussion of how the conditions imposed for the error analysis affect expressivity.\n\nThe authors provided adequate explanations for these points in the rebuttal, and improvements are expected in the final version. While the current lack of clarity keeps my overall evaluation borderline, considering the paper’s strengths, I will assign an accept-leaning rating.", "rebuttal": "We appreciate the reviewer for their thoughtful comments, recognizing the novelty of our work and the insights we provide. Below, we address the weaknesses and questions they raised.\n\n(W1) We appreciate the reviewer’s observation. We agree that the paper does not provide a formal analysis of training dynamics. Our focus is on generalization. Nonetheless, Experiment 1 was included to show that the spectral abscissa $s_A$ influences whether training succeeds, particularly as sequence length increases. In this sense, $s_A$ indirectly governs whether the model enters the regime where generalization bounds apply. Following this, Experiment 2 focuses on the stable regime, where training converges and generalization can be meaningfully evaluated (More elaborate discussion on this is included in our response to Reviewer h1Pz). To avoid misinterpretation of this connection, we will revise the abstract as follows:\n``Using this result, we analyze how the spectral abscissa of the continuous-time state matrix *influences the model’s stability during training* and its ability to generalize across sequence lengths.''\n\n(W2) Thank you for recognizing the value of extending generalization analysis from RNNs to selective SSMs. We attempted to outline the distinct challenges posed by selective SSMs in the proof sketch, but we appreciate the opportunity to clarify them more explicitly here:\n\n(i) In RNNs, the state matrix $A$ is a learnable parameter and can typically be treated as fixed when analyzing generalization. Its effect is often controlled by bounding its operator norm $\\|A\\|_2$ directly.\n\n(ii) In contrast, selective SSMs involve an input-dependent state matrix $A$, which varies with the input sequence through $A[k] = \\exp(\\Delta[k] A_c)$. Because no fixed bound on $\\|A\\|_2$ applies across all inputs, we cannot treat $A$ as a constant in the analysis, which poses a new challenge. To address this, we treat $A$ (as well as $B$ and $C$) as linear function classes, similar to attention mechanisms. This part of the proof is therefore fully based on results from generalization for attention. This is a technical departure from standard RNN analysis toward the methods developed for Transformers.\n\n(iii) We then observe that the spectral abscissa of the continuous-time state matrix $A_c$ provides an input-independent upper bound on the spectral radius of the discrete-time matrix $A$: $\\max_i(|\\lambda_i(A)|)$. This contrasts with the use of $l_2$ norm $\\|A\\|_2$ in RNNs. We believe there is no straightforward way to relate properties of $A_c$ directly to $\\|A\\|_2$.\n\n(iv) After the above steps, we use a telescoping summation. As the reviewer noted, this step is indeed similar to the treatment in RNN generalization bounds. There is a novel technical subtlety here: we use the Gelfand formula to relate the spectral radius of $A^t$ to its norm $\\|A^t\\|_2$ for a sufficiently large $t$, which allows this step. Remember in the previous step, from the continuous-time matrix $A_c$ we could bound the spectral radius, not $\\|A\\|_2$.\n\n(v) Finally, we combine the covering numbers, bound the Rademacher complexity, and derive the generalization bound. This part follows standard techniques established in the study of neural networks.\n\nWe will revise the main text to explicitly mention the connection to RNN generalization bounds, especially in the telescoping step, and clarify where our techniques diverge from and extend prior approaches.\n\n(W3) We thank the reviewer for raising this concern and understand that this connection deserves a clearer explanation. Overall, selective SSMs differ from RNNs in the broader sense that $A$, $B$, and $C$ are input-dependent rather than fixed. To handle this, we treat these components as *linear function classes*, an approach directly inspired by the treatment of $Q$, $K$, and $V$ in generalization analysis for Transformers. This is most clearly reflected in Equation (16), where the structure mirrors linear attention: $B$ can be viewed as analogous to keys, $C$ as queries, and the inner product $C^T A^t B$ resembles the attention with a causal mask. This analogy allows us to apply existing bounds on the covering numbers of attention mechanisms. Specifically, Lemma C.3 draws from such results to bound the complexity of the input-dependent parameterizations. Without adopting this perspective, one would need to develop entirely new theorems and lemmas to handle such input-dependent operators. This connection is further validated in Proposition 3.4, where under simplifying Assumptions 3.5 and 3.6, our bound recovers the generalization result for linear attention. To clarify this connection, we will revise the proof sketch and Remark 3.2 to state explicitly that step (i) of our proof (as outlined in W2) is where the attention-based generalization framework is applied.\n\n(W4) Thank you for pointing out this mistake, we will fix it in the revised manuscript.\n\n(Q1) We appreciate the reviewer’s insightful question. When $s_A$ is highly negative or positive, the induced critical quantity $\\rho_A$ (as defined in Theorem 3.3) becomes $\\ll 1$ or $\\gg 1$, respectively. This causes the influence of past inputs on the output at time $T$ to decay or grow exponentially, limiting the model’s ability to balance information across time. Specifically, when $\\rho_A \\ll 1$, the model primarily focuses on recent inputs, whereas when $\\rho_A \\gg 1$, early inputs dominate. In both extremes, expressive power suffers. For a formal result on this phenomenon, we refer the reviewer to Theorem 2 in *Block-Biased Mamba for Long-Range Sequence Processing* by Annan Yu (2025), which analyzes expressivity in the setting of diagonal $A_c$. While their setting differs from ours, the core intuition carries over to general selective SSMs. The combination of this result with the contributions of our paper suggests a natural trade-off: to achieve good generalization, $s_A$ is driven toward negative values (to ensure $\\rho_A \\leq 1$), but it operates near zero to preserve expressivity by keeping $\\rho_A$ close to 1. This conclusion is highlighted in bold in the final paragraph of Section 5.\n\n(Q2) Yes, the results support the conclusion that initializing $s_A$ near zero makes the model more likely to generalize for long sequences. In Experiment 1, $s_A$ starts positive and is pushed toward zero within the first few epochs for shorter sequences, allowing training to succeed. However, for longer sequences, this stabilization fails, leading to divergence. The key takeaway is that generalization can only be meaningfully evaluated when training succeeds, which happens when $s_A$ is small enough by the end of training. In Experiment 2, initialization at $s_A = 0$ makes training more likely to complete successfully across all sequence lengths.\n\n(Q3) The loss is inversely related to accuracy. In Experiment 1, we plotted loss versus epochs because it is standard practice to track loss during training. In contrast, Experiment 2 evaluates already trained models, where reporting train/test accuracy is more common, especially in classification tasks."}, {"review_id": "ZAy0Hh4ovI", "reviewer": "Reviewer_WxU3", "summary": "This work derives a probabilistic generalization error guarantee for the class of discretized continuous-time selective SSMs, precisely the Mamba architecture. The generalization gap is upper bounded by the function classes Rademacher complexity, which is in turn upper bounded by the use of a covering argument in conjunction with Dudley’s integral formula. Parts of the analysis are adapted from a framework previously developed for a similar analysis of linear Transformers. The authors run two sets of experiments aimed at understanding the relationship between system “stabilization” and training sequence length, as well as the effect of the sequence length on the generalization error when the SSM’s continuous time transition matrix has a negative spectral abscissa, in which case the error is independent of the sequence length.", "questions": "- I cannot entirely clearly see why the generalization bound is length-independent when the spectral abscissa of A is negative. In the $S_2$ factor in the generalization bound, assuming that $s_A<0$ in which case $\\rho_A<1$ , we obtain $\\lim_{T \\rightarrow \\infty}\\frac{ \\rho_A(1- \\rho_A^T)}{(1- \\rho_A)^2}- \\frac{T \\rho_A}{ \\rho_A-1}=\\frac{ \\rho_A}{(1- \\rho_A)^2}-\\lim_{T \\rightarrow \\infty}\\frac{T \\rho_A}{ \\rho_A -1}$. Asymptotically, the behaviour seems to be linear in $T$. Could the authors please comment on this aspect, seeing as it’s possibly **the** core message of the paper.\n- How do the authors explain the model’s length-independent high performance on majority? In my understanding, predicting majority seems to require an overview of the entire sequence, yet the state of an SSM with a negative spectral abscissa should exhibit an exponentially decreasing dependence on distant past states, at least in the case of an LTI system. Is the situation drastically different with selective SSMs, and do you think that the SSM behaviour will stay consistent on the majority task even with significantly longer inputs?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The paper employs relatively demanding technical concepts in its derivations, yet the main text is still written clearly and accessibly.\n- The results in Figure 1 are very interesting. Not only does training with overly long sequences fail to stabilise an unstably initialized system, but the spectral abscissa monotonously increases with the sequence length for lengths in which a stable point is reached through training. As the authors mention, the training “stabilizes the system **just enough** to preserve rich temporal information”, and more information tends to be preserved with longer training sequences.\n- The paper seems to propose the first generalization bound on selective SSMs derived through a covering-based upper bound on the function class’ Rademacher complexity. By doing this, it fills an important knowledge gap in the statistical learning theory of foundation models.\n- Figure 2 experimentally confirms the authors’ main finding, that SSMs with a negative spectral abscissa will exhibit a length-independent generalization error. It is a novel and interesting result.\n\n**Weaknesses**\n- The analysis only considers SSMs obtained through the discretisation of a continuous-time SSMs, in particular Mamba. While the authors are correct in stating that this assumption is more aligned with how such models are used in practice, a more general result should perhaps directly consider discrete-time time-variant SSMs in full generality. Similarly to the evolution from S4 and related models to the LRU (Orvieto et al. 2023), we might expect to see an evolution from Mamba to models that discard the assumption of a discretised continuous-time system.\n- While Figure 2 does demonstrate that, with a stable system, the generalization error tends to be constant with respect to the sequence length, the exponential dependence of the generalization error on the sequence length with unstable systems was not experimentally shown. The results shown in Figure 1 seem to point to a phase transition, rather than smooth, albeit very rapid, exponential growth.\n- Ideally the length-independence of the generalization gap such as shown in Figure 2 would have been analysed on a more diverse set of tasks.", "was_revised": true, "final_justification": "The paper appears to present the first generalization bound for selective SSMs, derived via a covering-based upper bound on the function class’s Rademacher complexity.\nThis contribution addresses a notable gap in the statistical learning theory of foundation models and represents a meaningful theoretical advancement. On the downside, the experimental evaluation is relatively limited, with modest results likely due to the use of small-scale models.", "rebuttal": "We thank the reviewer for their positive feedback and insightful comments.\n\nWeaknesses:\n\n1. Thanks for raising the very interesting idea of directly considering discrete time systems.  In this case, the discrete-time counterpart of the discretized continuous-time state-space model (SSM) would be a parameter-dependent system, where the system matrix $A(u)$ depends on the input $u$ at each time step. In principle, the stability of such a model can be assessed by replacing the continuous-time spectral abscissa $s_A$ with the spectral radius $\\rho(A)$ and requiring that $\\rho(A(.)) <1 $ for all possible values of $u$. However, this condition could be potentially very conservative,   depending on the nature of the dependence of $A(.)$ on $u$. We believe that a less conservative approach could be based on imposing that the joint spectral radius of the product $\\rho(\\mathcal{A}) = \\lim_{T \\\\rightarrow \\infty} \\rho(A(u_1)A(u_2)....A(u_T))< 1$. Computing this spectral radius is, in general, intractable. However, in the case where the input $u$ can be associated with the nodes of a graph, then one can use the approach introduced by A. A. Ahmadi et. al. in ``Joint Spectral Radius and Path-Complete Graph Lyapunov Functions,\" SIAM J. Control and Optimization, 52,1, pp. 687-717, 2014. Nevertheless, pursuing this approach would require defining a new class of Mamba models with a specific dependence of $u$ that allows for exploiting these results. In turn, this would require first considering different models $A(u)$, including the simpler case where $A$ is constant, and benchmarking their performance and the tradeoff complexity of the model versus generalization properties. While we agree that this is a research question worth pursuing, it is beyond the scope of the present paper.\n\n2. We agree with the reviewer that Experiment 1 does not directly measure the generalization error in the unstable regime. Its purpose is to demonstrate that when $s_A > 0$, training fails for long sequences and for short sequences, $s_A$ quickly moves toward negative values during early training. This means that in practice, the unstable regime is not sustained, especially for longer sequences. Importantly, our theoretical bounds are asymptotic and become meaningful only at long sequences, precisely where training fails in the unstable regime. This makes it infeasible to conduct experiments to validate the generalization bounds in that setting. Since test error evaluation is only meaningful if training is successful, generalization behavior cannot be studied when training fails. For further clarification, please refer to our response to the third weakness raised by Reviewer h1Pz.\n\n3. Our work is primarily theoretical, following a research tradition where results are supported through rigorous analysis or minimal experimental validation, as in [Bartlett 2017], [Edelman 2022], and [Trauger 2024]. That said, we fully acknowledge the importance of empirical validation, particularly for the length-independence of generalization. Such validation is challenging because it requires evaluating the same task across varying sequence lengths, a difficult goal for real-world datasets due to truncation, padding, or information loss. Synthetic datasets offer a controlled setting where sequence length can be varied without altering the task content. Accordingly, we include experiments on ListOps, as suggested by Reviewer vv3d. This task, part of the Long Range Arena benchmark, requires hierarchical reasoning over long sequences. Unlike simpler synthetic tasks, ListOps evaluates a model's ability to maintain long-range dependencies over nested structures, making it a meaningful test for generalization across sequence lengths.\n\nBelow, we present our results on ListOps for sequence lengths ranging from 100 to 1,000 tokens, with significance analysis performed by averaging over five different seeds.\n\n| Seq Len    | 100   | 200   | 300   | 400   | 500   | 600   | 700   | 800   | 900   | 1000  |\n|----------|-----|-----|-----|-----|-------|-------|-------|-------|-----|----|\n| Train Mean | 0.2154| 0.2106| 0.1980| 0.2040| 0.2154| 0.2012| 0.2156| 0.1974| 0.2150| 0.2218|\n| Train Std  | 0.0150| 0.0068| 0.0134| 0.0070| 0.0050| 0.0128| 0.0069| 0.0154| 0.0096| 0.0112|\n| Test Mean  | 0.1578| 0.1638| 0.1488| 0.1662| 0.1528| 0.1638| 0.1468| 0.1666| 0.1694| 0.1498|\n| Test Std   | 0.0236| 0.0124| 0.0119| 0.0132| 0.0116| 0.0103| 0.0119| 0.0137| 0.0061| 0.0091|\n| Gen Gap    | 0.0576| 0.0468| 0.0492| 0.0378| 0.0626| 0.0374| 0.0688| 0.0308| 0.0456| 0.0720|\n\nAs the results show, the generalization gap does not exhibit a clear trend with respect to sequence length. While the accuracy values may seem low, it is important to note that even full-scale multi-layer models like Linear Transformer and Performer perform similarly or worse on this task, with 0.16 and 0.18, respectively, than our single-layer selective SSM block with N=4 states per channel and d=16 channels [Tay 2020]. This highlights the inherent difficulty of the task.\n\nQuestions:\n\n1. We genuinely appreciate the reviewer for pointing out this issue. The term $S_2$ appears in the proof as a result of evaluating the sum $\\sum_{t=0}^T t \\rho_A^t$ at the end of Lemma D.6 (line 611). From that derivation, it follows that $S_2$ is given by:\n$$\nS_2 = \\frac{\\rho_A\\left(1 - \\rho_A^T\\right)}{(1 - \\rho_A)^2} - \\frac{T \\rho_A^T}{1 - \\rho_A}.\n$$\nThere was a typo in the main theorem where the exponent $T$ in the numerator of the second term is missing. When this is corrected, it becomes clear that the bound asymptotically approaches $\\frac{\\rho_A}{(1 - \\rho_A)^2}$ as $T \\rightarrow \\infty$, confirming that the generalization bound becomes independent of sequence length in the stable regime.\n\n2. The majority task is essentially counting the number of ones in a sequence, which corresponds to the state-space model $x(k+1) = x(k) + u(k)$. This is the discretized form of an integrator, which has spectral abscissa $s_A = 0$. In theory, given sufficient training data and successful optimization, the learned model should converge to this form, yielding $s_A = 0$. In practice, however, due to numerical errors and finite data, we rarely observe $s_A = 0$ exactly; instead, $s_A$ tends to be a very small value close to zero. For extremely long sequences, where even not just exponential but linear accumulation of error is not tolerable, we agree with the reviewer that training may fail. Additionally, compared to LTI SSMs, the selective ones have more freedom to adjust the determining quantity $\\rho_A$ as defined in Theorem 3.3 to stabilize training. They may perform better by adjusting $u$, $q$, $p$, and $A_c$, as opposed to relying solely on $A$ in LTI SSMs."}, {"review_id": "Ijwv4hVI85", "reviewer": "Reviewer_vv3d", "summary": "This paper investigates how well selective SSMs generalize as the sequence length grows.\n\nThe authors reuse covering-number tools developed for Transformer theory.\nThey give generalization upper (Theorem 3.3) and lower (Theorem 4.1) bounds for selective SSMs, showing that when the transition matrix has non-negative spectral abscissa, an exponential dependence on sequence length is tight and unavoidable.\n\nThe authors ground their theory with two experiments, each initialized with a different spectral abscissa s_A:\n- Experiment 1 (unstable start, s_A>0) – The model stays in the unstable regime on long sequences, so training diverges.\n- Experiment 2 (stable start, s_A\\le 0) – The model remains stable, and its train-test gap stays flat as sequence length grows, demonstrating length-independent generalization.", "questions": "Suggestions:\n1. Broaden the empirical study:\n- Train deeper selective-SSM stacks (6–8 blocks) to test whether instability compounds with depth.\n- Add matched-parameter baselines—Transformer, Performer, and S4D—on standard long-range tasks such as ListOps and PG-19.\n- Sweep the initial spectral abscissa s_A while holding all other hyperparameters fixed to isolate the stability factor.\n2. Clarify theory: Either tighten the lower bound to close the residual O(T) gap or argue why that gap is information-theoretic and cannot be removed.\n3. Verify assumptions: Log input-token norms and key parameter magnitudes during training; confirm they stay within the theoretical bounds or explain any deviations.", "limitations": "The authors do not adequately address the paper’s limitations. \nWhile they point to Section 4, it only compares their bounds to prior work and omits key issues like limited experiments, unverified assumptions, and evaluation scope. There is no dedicated limitations section, despite the checklist guidance to include one.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths.\n- Novel theory: Theorems 3.3 and 4.1 give the first length-independent generalization bound for selective SSMs, plugging a gap left by prior LTI-SSM work.\n- Insight: The bound scales as e^{s_A T} for s_A>0 but is flat in T when s_A<0, pinpointing stability as the decisive factor in SSM initialization.\n- Transparency: Assumptions 3.1–3.6 state all Lipschitz and norm constraints, and every proof step in App. A cites them, making the analysis easy to audit.\n\nWeaknesses.\n- Narrow empirics: Only two tasks and a single-block model; no Transformer or S4 baseline, so real-world relevance is unclear.\n- No statistical rigor: All plots come from one seed, with no error bars or significance tests.\n- Assumptions unverified: The paper never logs input-token norms or Δ parameters, so it’s unknown whether training stays within the bound’s regime.\n- Related-work coverage is thin, and the limitations section is vague.", "was_revised": true, "final_justification": "I thank the authors for their detailed rebuttal. They addressed several concerns, including statistical rigor (by reporting results over multiple seeds), empirical verification of theoretical assumptions (via parameter norm logs), and additional results on ListOps. While these clarifications improve the presentation and strengthen the empirical support, the scope of evaluation remains narrow and the relevance to full-model SSM architectures is still limited. \n\nGiven the paper’s theoretical novelty and the transparent analysis of selective SSM generalization, I am maintaining my borderline accept rating.", "rebuttal": "We thank the reviewer for recognizing the novelty and clarity of our theoretical contributions. Due to character limits, we kindly refer the reviewer to our responses to other reviewers for some overlapping points, and we apologize for any inconvenience this may cause. Below is our response to the weaknesses and questions.\n\nWeaknesses:\n\n1. Our work focuses on the theoretical analysis of a single selective SSM block rather than extensive empirical benchmarking. However, we acknowledge the limited number of baselines in this paper and address this concern by providing additional empirical results on the ListOps benchmark, as detailed in our response to the third weakness raised by Reviewer WxU3.\n\n2. We agree with the reviewer that statistical rigor is important. To address this, we repeated the length-independence experiment for the majority task using five different random seeds and ensured that training was successful in each run. The table below reports the mean and standard deviation across seeds:\n\n| Seq Len   | 50    | 100   | 150   | 200   | 250   | 300   | 350   | 400   |\n|------|----|----|-----|----|----|----|----|-----|\n| Train Mean| 0.95  | 0.96  | 0.96  | 0.97  | 0.98  | 0.98  | 0.97  | 0.98  |\n| Train Std | 0.013 | 0.008 | 0.008 | 0.009 | 0.015 | 0.008 | 0.006 | 0.007 |\n| Test Mean | 0.88  | 0.87  | 0.89  | 0.89  | 0.87  | 0.87  | 0.87  | 0.88  |\n| Test Std  | 0.028 | 0.013 | 0.018 | 0.019 | 0.027 | 0.018 | 0.014 | 0.015 |\n| Gen Gap   | 0.0758| 0.0926| 0.0732| 0.0790| 0.1024| 0.1068| 0.0996| 0.1044|\n\nAs shown in the table, the generalization gap shows no clear trend, and the small standard deviations indicate statistical significance. Similar results for ListOps are reported in the response to Reviewer WxU3. IMDb is omitted due to space constraints.\n\n3. We thank the reviewer for this valuable comment and fully agree that logging parameter norms to verify theoretical assumptions is important. Our main assumptions (3.1-3.4) require certain SSM parameter norms to remain bounded by constants. However, these constants are neither universal nor predetermined, which makes direct verification against a single fixed numerical threshold less intuitive.  \n\nStill, we were on the same page with the reviewer and had already checked these norms during experiments. We monitored $s_A$, $\\|p\\|$, $\\|q\\|_2$, $\\|W_B\\|_2$, $\\|W_B\\|_1$, $\\|W_C\\|_2$, $\\|W_C\\|_1$, and $\\|A_c\\|_2$ throughout training. Our observations confirm that these norms remain stable and do not exhibit unbounded growth. Regarding the input tokens, they are generated via a learnable linear projection layer. As such, their norm is controlled by design, and our boundedness assumption is satisfied by construction. For completeness, we include the input norm $\\max{\\|u[t]\\|_2}$ here.\n\nThe logs are available in the GitHub repository linked in Footnote 2 (page 8). As a minor note, the repository records $-s_A$ (instead of $s_A$) due to an earlier version of our code that computed stability margins directly via negative spectral abscissa values. These results were omitted from the main paper due to space constraints, but we will include a section in the appendix during revision. Additionally, we provide an example log table in our response to Question 3 below.\n\n4. We thank the reviewer for this feedback. For Related Work, please refer to our response to the second weakness raised by Reviewer h1Pz. Regarding Limitations, we opted to discuss them within their respective sections, but we agree that a dedicated Limitations section would improve clarity and will include one in the appendix of the revised manuscript.\n\nQuestions:\n\n1. Broadening the empirical study:\n\n- We appreciate this suggestion and agree that exploring the effect of depth is an interesting direction. However, selective SSM blocks by themselves are not typically stacked to form complete models. Architectures such as Mamba use more complex blocks that include additional components such as convolution layers, projection layers, and residual connections. Our work focuses on the role of the selective SSM block within such models, so the current analysis does not directly extend to multi-block architectures. Investigating these interactions at the full-model level is an important avenue for future work.\n\n- We thank the reviewer for the suggestion. However, we would like to clarify that our work focuses on theoretical analysis rather than empirical benchmarking. The goal is to understand the generalization behavior of selective SSMs, not to propose a new algorithm to improve performance metrics and compare it empirically against other architectures. In this setting, models are evaluated based on the structure and dependencies of their generalization bounds, not performance metrics. Therefore, matching parameter counts is not particularly informative, as there is no performance index to optimize. Instead, we compare theoretical bounds directly, as shown in Table 1. The softmax attention bound included there corresponds to Transformers, while the LTI-SSM bound captures models like S4D. To our knowledge, there are currently no generalization error bounds for Performer that would allow a fair comparison.\n\nWe agree with the reviewer that verifying our analysis on a task like ListOps would be valuable. For an additional experiment on ListOps, please refer to our response to the third weakness raised by Reviewer WxU3. Regarding PG-19, we note that the generalization assumptions and theorems used in our analysis, which are based on Rademacher complexity, are developed for supervised learning settings and rely on conditions like Assumption 3.3 regarding the loss function. Since PG-19 is a generative language modeling task, it does not fit within this theoretical framework.\n\n- We thank the reviewer for the insightful suggestion. The following table presents the results of sweeping the initial $s_A$ on the IMDb dataset with the sequence length $T=500$, while holding all other hyperparameters fixed.\n\n| epoch | 1     | 3     | 5     | 7     | 9     |\n|--|--|--|---|---|---|\n| 0.1   | 0.078 | 0.119 | 0.125 | 0.126 | 0.126 |\n| 0.08  | 0.078 | 0.099 | 0.102 | 0.103 | 0.013 |\n| 0.06  | 0.086 | 0.103 | 0.105 | 0.106 | 0.106 |\n| 0.04  | 0.082 | 0.097 | 0.100 | 0.100 | 0.100 |\n| 0.02  | -0.012| -0.031| -0.063| -0.068| -0.057|\n| 0     | -0.027| -0.066| -0.073| -0.072| -0.068|\n| -0.02 | -0.024| -0.053| -0.046| -0.061| -0.057|\n| -0.04 | -0.029| -0.070| -0.067| -0.065| -0.048|\n| -0.06 | -0.056| -0.078| -0.026| -0.068| -0.082|\n| -0.08 | -0.068| -0.037| -0.043| -0.046| -0.033|\n| -0.1  | -0.065| -0.060| -0.113| -0.119| -0.086|\n\nThese results correspond to the left plots in Figure 1 of the paper and show consistent trends. Unstable initializations ($s_A > 0$) generally lead to training failure, except for $s_A = 0.08$ and $s_A = 0.02$, where the spectral abscissa is effectively driven toward zero from above, stabilizing the system. In contrast, stable initializations ($s_A \\leq 0$) remain stable throughout training. The corresponding loss curves (shown in the right plots of Figure 1) decrease drastically for $s_A \\leq 0$ and $s_A = 0.02$ from the first epoch, and for $s_A = 0.08$ after epoch 7, while remaining high for the rest. Due to space constraints, these loss curves are omitted here. We have also performed the same analysis for the Majority task and will include those results in the appendix of the revised manuscript.\n\n2. The lower bound we provide is on the Rademacher complexity, not directly on the generalization error. This approach is inspired by [Bartlett et al., 2017, Spectrally-normalized margin bounds for neural networks], where a similar lower bound is derived to assess the tightness of the upper bound. In their work, as in ours, the lower bound is not tight but still provides valuable theoretical insights. Our result shows that, under the current analysis based on Rademacher complexity, the upper bound is tight up to a factor of $\\mathcal{O}(T)$. We have explicitly noted this as a limitation in the paper (line 277). Nonetheless, the lower bound highlights a key contribution of the paper: for the case $s_A > 0$, the exponential dependence in the upper bound cannot be removed.\n\n3. The following table provides an example log from Experiment 1 (IMDb, $T = 350$). The spectral abscissa $s_A$ is already plotted in Figure 1 (bottom left, orange line). At the beginning of a stable training cycle, in which $s_A$ is successfully pushed toward $0$ from above and the loss drops significantly within 10 epochs, the parameter norms do not show strictly increasing trends. This supports the claim that these norms remain bounded. Additional logs are available in the anonymous GitHub repository linked on page 8, footnote 2.\n\n| Epoch | $s_A$  | $\\|p\\|$ | $\\|q\\|_2$ | $\\|W_B\\|_2$ | $\\|W_B\\|_{1,1}$ | $\\|W_C\\|_2$ | $\\|W_C\\|_{1,1}$ | $\\|A_c\\|_2$ | $\\max{\\|u[t]\\|_2}$ | Loss |\n|---|---|---|---|---|---|----|---|---|---|---|\n| 0     | 0.100  | 1.43    | 4.12      | 7.70        | 51.00           | 7.40        | 48.50           | 9.51        | 7.39       | –    |\n| 1     | 0.069  | 1.46    | 3.89      | 7.12        | 45.90           | 6.85        | 43.40           | 9.41        | 7.07       | $6.4 \\times 10^{20}$ |\n| 3     | 0.005  | 1.62    | 3.56      | 6.53        | 41.40           | 6.33        | 39.10           | 9.21        | 6.49       | 347.71 |\n| 5     | -0.006 | 1.58    | 3.44      | 6.21        | 39.53           | 6.15        | 39.03           | 9.01        | 6.19       | 2.04  |\n| 7     | -0.009 | 1.58    | 3.38      | 6.05        | 38.56           | 6.13        | 39.01           | 8.84        | 6.00       | 1.00  |\n| 9     | -0.012 | 1.61    | 3.35      | 5.97        | 38.03           | 6.12        | 40.00           | 8.67        | 5.82       | 0.67  |"}]

Author rebuttal:

Meta-review: This paper provides a theoretical generalization analysis of selective state-space models (SSMs), which form the core of the Mamba architecture. The authors derive a novel covering number–based bound for selective SSMs, extending recent theoretical results on Transformers. A central insight is that the spectral abscissa of the continuous-time state matrix governs both training dynamics and the model’s ability to generalize across sequence lengths. Overall, the work offers a clear and timely theoretical contribution to understanding SSMs and their generalization properties.

While there are some limitations–particularly that the experimental results are not very strong–the reviewers agree that the paper tackles an important problem (generalization in SSMs) with a novel and well-founded methodology (covering numbers applied to selective SSMs). Therefore, in line with reviewers WxU3, Bnv5, and vv3d, I recommend acceptance of this paper.
Decision: Accept (poster)