TaylorSSM: Dependence-Preserving Robustness Certification for Selective State-Space Models

Robustness certification is well studied for feedforward networks, Transformers, and recurrent networks. In selective state-space models, the same input perturbations affect both recurrent states and the input-dependent rules for updating and reading them. Bounding these effects separately can weaken certificates, motivating verification methods that exploit their shared dependence. To our knowledge, we present the first end-to-end robustness verifier tailored to Mamba-style classifiers. We propose TaylorSSM as the verifier's core method for constructing sound polynomial bounds that preserve shared input dependence. These bounds support direct certification and enable joint analysis across blocks to certify larger perturbation regions. We certify cases unresolved by IBP and GenBaB's nonlinear branch-and-bound. Our intermediate bounds also strengthen affine bound propagation and tighten GenBaB's bounds before branching. These results highlight the value of combining contributions from shared perturbations before bounding their joint effect.