The Implicit Bias of Structured State Space Models Can Be Poisoned With Clean Labels

Authors: Yonatan Slutzky, Yotam Alexander, Noam Razin, Nadav Cohen
Primary area: learning theory
Keywords: Structured State Space Models, Implicit Bias, Implicit Regularization, Clean Label Poisoning

Abstract:
Neural networks are powered by an implicit bias: a tendency of gradient descent to fit training data in a way that generalizes to unseen data. A recent class of neural network models gaining increasing popularity is structured state space models (SSMs), regarded as an efficient alternative to transformers. Prior work argued that the implicit bias of SSMs leads to generalization in a setting where data is generated by a low dimensional teacher. In this paper, we revisit the latter setting, and formally establish a phenomenon entirely undetected by prior work on the implicit bias of SSMs. Namely, we prove that while implicit bias leads to generalization under many choices of training data, there exist special examples whose inclusion in training completely distorts the implicit bias, to a point where generalization fails. This failure occurs despite the special training examples being labeled by the teacher, i.e. having clean labels! We empirically demonstrate the phenomenon, with SSMs trained independently and as part of non-linear neural networks. In the area of adversarial machine learning, disrupting generalization with cleanly labeled training examples is known as clean-label poisoning. Given the proliferation of SSMs, particularly in large language models, we believe significant efforts should be invested in further delineating their susceptibility to clean-label poisoning, and in developing methods for overcoming this susceptibility.

Decision: reject
Reviewer scores: 8, 6, 6, 3

Reviews and discussion:
<thread>
creation date:
1730419403462

thread_type:
official_review

<thread_object>
creator: reviewer_mxtt

<content>
summary:
This paper shows that when learning certain linear state-space models, gradient flow converges to solutions that generalize well with certain training trajectories but to those that do not when some specific trajectory is appended.

strengths:
Data poisoning attacks are one of the practical concerns in training machine learning models, this paper studies some theoretical aspects of this issue for state-space models.

weaknesses:
The result shown in this paper comes from an extremely contrived example and the reviewer has strong concerns regarding its practical significance.

1. Theorem 1 states that the learned student SSM generalizes "under various choices of training sequence" (line 258), the truth is these training sequences are $\left\lbrace p_i\mathbf{e_1},p_i\right\rbrace_{i=1}^n$, where $p_i\in\mathbb{R}$ (line 857, Definition 2 in Appendix), i.e., the input sequences to the teacher SSM are the same up to some scaling. Since the SSM to be learned is linear, these $n$ training sequences are effectively single sequences. It is not a big surprise if student SSM generalizes when this single training trajectory is crafted to guide the GF to the generalizing solutions, and then it is even less surprising if another crafted training trajectory is added to steer GF to other solutions. There are effectively only two training trajectories, after all.

2. Another reason this example is contrived is that there is no persistence of excitation (Green&Moore, 1986) in the input sequence used for training, which is fundamentally needed to identify linear systems. 

3. The state matrix $A$ is assumed diagonal, the $B,C$ matrices are fixed during training. However, these are of less concern than the previous points.

4. The reviewer does not appreciate the presentation in this paper where assumptions ($A$ being diagonal) are not stated as proper assumptions (line 112), and key definitions (precise definitions of the training trajectories) are written in the Appendix. 

**References**:

M Green and J Moore, Persistence of excitation in linear systems, Systems & Control Letters, 1986

questions:
See "Weakness".
</content>
</thread_object>

</thread>
<thread>
creation date:
1730443642479

thread_type:
official_review

<thread_object>
creator: reviewer_kj3p

<content>
summary:
This paper investigates the implicit bias of Structured State Space Models (SSMs), an emerging and efficient alternative to transformers. Previous research suggested that the implicit bias of SSMs enables good generalization when data is generated by a low-dimensional teacher model. However, this study revisits that assumption and uncovers a previously undetected phenomenon: while implicit bias generally promotes generalization, certain special training examples can completely distort this bias, causing generalization to fail. Notably, this failure occurs even when these examples have clean labels provided by the teacher model. The authors empirically demonstrate this effect in SSMs trained both independently and within non-linear neural networks. In adversarial machine learning, disrupting generalization with cleanly labeled examples is known as clean-label poisoning. Given the growing use of SSMs, especially in large language models, the authors emphasize the need for further research into their vulnerability to clean-label poisoning and the development of strategies to mitigate this susceptibility.

strengths:
1. This paper presents a solid theoretical work, extending the results on the gradient descent (GD) implicit bias of Structured State Space Models (SSMs) from the population risk setup, as discussed in [1], to the finite empirical risk setup. The authors demonstrate that training a student SSM on sequences labeled by a low-dimensional teacher SSM exhibits an implicit bias conducive to generalization. Their dynamical analysis also establishes a connection with greedy low-rank learning.

2. Using an advanced tool from dynamical systems theory—the non-resonance linearization theorem—the authors prove that adding a single sequence to the training set, even if labeled by the teacher SSM (i.e., with a clean label), can completely distort the implicit bias to the point where generalization fails. This finding highlights the need for significant research efforts to better understand SSMs' vulnerability to clean-label poisoning and to develop effective methods to counteract this issue.

3. Overall, the paper is very well written.

**Reference**

[1] Cohen-Karlik, E., Menuhin-Gruman, I., Giryes, R., Cohen, N., & Globerson, A. (2022). Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Nets. arXiv preprint arXiv:2210.14064.

weaknesses:
1. The assumptions in Theorem 1 are overly restrictive, particularly as the structures of $ A^* $, $ B^* $, and $ C^* $ seem to be very simple, and there is a lack of detailed explanation as to why such a simplified setup is justified in this context.

2. Regarding the special sequence data, Theorem 1 only provides an existence result without specifying a concrete construction method or offering a more detailed characterization, making it difficult for me to understand why the introduction of these clean data points leads to a failure in generalization.

3. The experiments in the paper seem to be conducted solely on synthetic datasets, which greatly limits their persuasiveness. The authors should consider using more real-world datasets to demonstrate the generality of the phenomenon they describe.

questions:
1. Could the authors provide a more formal statement regarding greedy low-rank learning and clarify whether the theoretical analysis can be observed in experiments on real-world datasets?

2. For real-world datasets, can the theoretical analysis and conclusions of this paper help design an algorithm to identify the so-called special sequence for poisoning?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730597646267

thread_type:
official_review

<thread_object>
creator: reviewer_jomp

<content>
summary:
This paper examines the vulnerability of SSMs to clean-label poisoning. While SSMs generally possess an implicit bias that promotes generalization when trained on low-dimensional data from a teacher model, this study demonstrates that the inclusion of carefully chosen, correctly labeled training examples can disrupt this bias, resulting in a failure to generalize.

strengths:
1). This paper discovered clean-label poisoning of SSMs, which is a vulnerability unrecognized by previous works, highlighting a potential risk in the safety, robustness, and reliability of SSMs.

2). This paper provides a strong theoretical foundation and empirical validation to show that generalization can be ruined by introducing certain clean-labeled sequences.

weaknesses:
This paper falls outside my current area of expertise.

questions:
This paper falls outside my current area of expertise.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730640112858

thread_type:
official_review

<thread_object>
creator: reviewer_qi9a

<content>
summary:
This paper presents a fundamental understanding of SSMs by investigating its implicit bias both theoretically and empirically. From the extended setting of the previous work [1], the authors address several theoretical findings which are corroborated with experimental evidence. First, the authors provide a dynamical characterization of gradient flow over SSM, which reveals that greedy learning can be implicitly induced under many choices of training sequences. Second, based on the first point, the authors prove the followings; (1) a collection of sequences labeled by a low dimensional teacher SSM leads to the implicit bias of the student SSM, (2) adding a certain single sequence labeled by the teacher to the training set ruins the implicit bias which fails the generalization. These analyses are supported by simple experiments that are well consistent with the theories.


[1] Edo Cohen-Karlik, Itamar Menuhin-Gruman, Raja Giryes, Nadav Cohen, and Amir Globerson. Learning low dimensional state spaces with overparameterized recurrent neural nets. In International Conference on Learning Representations (ICLR), 2023

strengths:
The theoretical analysis of the implicit bias of SSMs is a strength of this work. Providing a basic understanding of SSMs, which are often considered as an alternative to transformers, is indeed important for the community.

The paper is nicely written, while I'm not an expert in this area, I could easily follow the logical steps of the paper based on proper interpretation and the sketches of the mathematical details.

The experimental results that corroborates the theoretical analyses are a strength of this work. While the authors acknowledge the limitations of their work (to name a few, the experiments pertain near-zero initialization, the dimension of the teacher SSM is one in most settings), the identification of the phenomena and a theoretical modeling to explain such things is a meaningful contribution.

weaknesses:
Again, I'm not an expert in this area, but I'd like to make a few points that might be helpful to the authors and also clarify my understanding.

1. Is it possible to separately decompose and plot $\gamma^{(0)}(t)$ along with Figure 2? If so, I think it could give a more concrete explanation to aid the Interpretation part of Section 3.1.
2. Can the authors come up with a measure to qualitatively distinguish between the scenarios of the (leftmost) and (second) subplot of Figure 2? I'm aware that this might be an abrupt question, but it could be seen that the (second) subplot does not correspond to the case of 'not greedy', maybe close to 'less greedy' (especially for the case of Figure 4 in the supplementary material). 
3. (Slightly related to 2.) Adding results of more individual runs/seeds for Figure 2 could more strengthen the authors' explanation. Could be an indirect way to show this, but showing only one trial as confirmation to the theory seems less sufficient.
4. Out of the scope of the teacher-student setting (i.e. in the real-world scenario), what could be the interpretation or example for $(\mathbf{x}^{\dagger}, y^{\dagger})$ of Theorem 1 that harms the student from generalization?
5. Adding a short discussion of the limitations with respect to the corresponding results from the supplementary materials would make the paper more complete. In addition, could the authors provide more experimental results beyond the limitation setting made in the supplementary materials (i.e., results for the teacher dimension greater than 2)? Providing these additional results is not necessary, and I do not want this point to be an extensive burden. But I believe that effectively showing such limitations is indeed important from a completeness perspective.

questions:
Please refer to the weaknesses above.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary of Contributions:
This paper addresses the implicit bias in Structured State Space Models (SSMs) and demonstrates a theoretical phenomenon: while such models typically generalize when trained using sequences generated by a low-dimensional teacher, their generalization can break down upon adding certain carefully crafted but cleanly labeled examples. The authors provide a dynamical characterization of gradient flow on SSMs and prove a theoretical result that identifies the existence of so-called “clean-label poisoning” examples. Additionally, they support their theory with synthetic experiments and attempt to highlight relevance to scenarios outside simple teacher-student setups by experimenting on a real-world (sequential MNIST) setting.

Strengths:
	1.	Novelty and Insight: The paper sheds light on an under-explored aspect of SSMs—namely, their susceptibility to clean-label data poisoning. Prior work largely suggested that the implicit bias of these models leads to good generalization in low-dimensional teacher-student setups. This paper identifies a nuanced and previously unknown vulnerability.
	2.	Theoretical Rigor: The authors present a non-trivial dynamical characterization that employs advanced mathematical tools. The work extends the current theoretical understanding of the implicit bias in SSMs, linking it to a “greedy low-rank learning” phenomenon.