Generalization Error Analysis for Selective State-Space Models Through the Lens of Attention

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.

Weaknesses:

1. 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.

2. 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:

As 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.

3. 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.

Still, 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.

The 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.

4. 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.

Questions:

1. Broadening the empirical study:

• 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.

• 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.

We 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.

• 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.

These 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.

2. 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.

3. 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.

We thank the reviewer for their positive feedback and insightful comments.

Weaknesses:

1. 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.

2. 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.

3. 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.

Below, 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.

As 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.

Questions:

1. 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:

$$S_2 = \frac{\rho_A\left(1 - \rho_A^T\right)}{(1 - \rho_A)^2} - \frac{T \rho_A^T}{1 - \rho_A}.$$

There 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.

2. 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.

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.

(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: ``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.''

(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:

(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.

(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.

(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$.

(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$.

(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.

We 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.

(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.

(W4) Thank you for pointing out this mistake, we will fix it in the revised manuscript.

(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.

(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.

(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.

I appreciate the authors’ clear response. Since the trade-off between the expressivity of SSMs and their learnability (including generalization) is often discussed, I think that addressing this point somewhere would increase the impact of the paper.

I have reconsidered my rating and will increase it by one point.

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:

Weaknesses:

1. 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:

• 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.

• 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.

Regarding 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.

2. 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.

3. 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.

Questions:

1. 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.

2. 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.

3. 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.