- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper "TaylorSSM: Dependence-Preserving Robustness Certification for Selective State-Space Models" tackles the robustness verification problem for Mamba-style models under - bounded embedding perturbations. The authors identify limitations of current approaches for this task, since these cannot maintain non-linear input dependencies across time steps and accumulate severe approximation errors throughout time steps. The authors propose the TaylorSSM representation of all reachable states to improve on these challenges, which represents intermediate network states as quadratic polynomials together with bounds on appoximation errors. They complement this construction with architecture-specific tricks for Mamba models, such as combining transition, injection and readout contributions before bounding them, thereby not having to bound potentially cancelling expressions. For verification, the representation can be used to lower-bound the output margin directly and, alternatively, can be used within Full-QC which constructs quadratic constraints that link nonlinear residuals to inputs, yielding a SDP problem. Across the conducted experiments, TaylorSSM demonstrates superiority over standard bound propagation and an adapted bound propagation baseline based on transformer verification.
Critical strengths
- The contribution tackles an important problem (verification of SSMs), identifies important problems that hinder the application of standard approaches and resolves those in their method. The construction appears to be correct and sound and the reported certification gains are substantial.
- The analysis is substantive, with an extremely extensive appendix including ablations, measurements, different architectures, etc.
- The proposed TaylorSSM representation is general and can in principle be used within other certification frameworks, such as GenBaB (as demonstrated by the authors.)
Critical weaknesses
- There are some concerns regarding the conducted experiments. It is unclear why Table 1 compares against IBP and CROWN-IBP. It is well-known that these bound propagation approaches are quite weak, introduce considerable overapproximation errors and are not state-of-the-art. This raises the question whether this comparison was chosen to demonstrate improvements over particularly weak baselines. Furthermore, the main comparisons in the main text are made using a modified Mamba architecture where selectors are computed before SiLU. In the Appendix, the standard architecture is evaluated as well for the proposed methods, but here, a comparison against baselines is missing. This also raises concerns regarding performance on standard Mamba architectures. Lastly, GenBaB uses potentially loose CROWN or IBP for intermediate bounds, so it is questionable whether this is actually the best-performing configuration of that verifier.
- Scalability does seem to be a major limiting factor. TaylorSSM stores coefficients per scalar and constructs injection–readout pairs. Since certification already takes minutes or hours for the small models investigated in the paper, practical usability appears to be far out of reach.
- The investigated setting is narrow -- perturbations in embeddings do not allow for semantically similar word substitutions and it might not be the case that there exists a set of discrete inputs (words) that maps to the perturbation set around the embedding.
Questions for authors
- Do any other vocabulary embeddings actually fall within the certified regions and, given the results in Appendix F1.2, do the certificates cover any non-trivial token substitutions?
- How was GenBaB configured in the experiments. In particular, why did it not use alpha-CROWN for intermediate bounds?
- Why did you choose CROWN-IBP and IBP as baselines in Table 1? Why not stronger bound propagation methods such as -CROWN?
- Can you provide results of the baseline approaches on the more realistic checkpoint with bounds after the SiLU activation?
- What are practical limits in sequence length and model size given the unfavorable scaling behaviour?
4 comments
Response to Reviewer derX (2/2): Vocabulary coverage (Q1, W3) and practical limits (Q5, W2)
Q1 & W3: Vocabulary embeddings and token substitutions
No: in the analyzed pre-SiLU radius-search panel, none of the certified boxes contains another distinct non-padding, non-CLS vocabulary embedding.
The largest ratio of certified radius to nearest-vocabulary distance in the norm is below 3.85% (Appendix F.1.2). We therefore report these certificates as guarantees of local robustness in continuous embedding space (Section 5.2).
On tasks with both a certificate and a validated attack, the larger certified radius from the two routes reaches at least 26% of the true robustness radius on average (Appendix F.2).
The input representation can also express sets containing specified substitutions. Our analysis requires an affine image of a box, with . For a position with candidate substitutes, inserting their embedding differences at that position in the columns of gives a set containing every candidate, with variables (Section 6). Certification of these candidate-substitution sets is not evaluated in the current experiments.
Q5 & W2: Practical sequence and model-size limits
At the main four-layer scale, a 32-step affected suffix takes tens of minutes to about two hours; eight-layer certification is demonstrated at a smaller radius and a short suffix.
Each represented scalar stores coefficients, and constructing all recurrent readouts requires injection-readout pairs. Here is the suffix length beginning at the earliest perturbed position, and for jointly perturbed positions of embedding width .
For the four-layer, width-384 model at and , the two-input diagnostic takes a median of about 21 minutes for the direct bound and two hours for Full-QC, with approximately 33 GiB of peak host memory (Table 19). The boundary evaluation shows both rising computation cost and loosening enclosures as , width, or depth increase; Table 15 reports joint perturbations at two and four positions, including the accompanying decline in coverage.
The revision adds certificates from both routes on an eight-layer, width-384 instance at and (Appendix F.6.1). The original larger-radius depth diagnostics remain unresolved, confirming that the operating boundary depends on perturbation size as well as model scale.
Revisions in the updated manuscript
The same-scale post-SiLU comparison (Table 1), intermediate-bound optimization diagnostics (Appendix F.4.2), vocabulary-distance analysis (Section 5.2, Appendix F.1.2), and eight-layer certificates (Appendix F.6.1) are the main updates. We are happy to discuss any remaining questions.
References
[1] Z. Shi, H. Zhang, K.-W. Chang, M. Huang, and C.-J. Hsieh. Robustness verification for transformers. In ICLR, 2020.
[2] K. Xu, H. Zhang, S. Wang, Y. Wang, S. Jana, X. Lin, and C.-J. Hsieh. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. In ICLR, 2021.
Kindly Requesting Your Valuable Feedback
Dear Reviewer derX,
Thank you again for your detailed and constructive assessment. We have addressed your main experimental concerns in the revised manuscript and our responses, particularly the same-scale standard post-SiLU evaluation (Table 1) and stronger baseline optimization comparisons (Appendix F.4.2).
We would greatly appreciate any further feedback on whether these additions address your primary concerns, or whether any important issues remain unresolved.
Thank you for your time and consideration.
Reviewer derX, thanks for your review. Could you take a look at the authors’ response and comment on which of your concerns have or have not been resolved?
Response to Reviewer derX (1/2): Baseline comparisons and intermediate-bound optimization (Q2-Q4, W1)
We appreciate the thorough technical assessment and the specific questions on experimental configuration. Below we address the baseline and optimization concerns, followed by the threat-model and scaling questions in Part 2.
Q4 & W1: Baseline comparisons on standard post-SiLU Mamba
The revised Table 1 reports baseline comparisons on a standard post-SiLU Mamba-1 checkpoint with the same four layers and width 384 as the original main model.
On the 256-task panel, Table 1 reports the following coverage by attained certified radius:
The selectors are computed from SiLU outputs, so the certificates cover the standard computation. Sections 5.1 and 5.2 present both models side by side, with baseline comparisons on each.
Q2-Q3 & W1: GenBaB, α-CROWN, and intermediate-bound optimization
Our GenBaB comparison already includes α-CROWN-style relaxation optimization followed by nonlinear branch-and-bound; the revision also tests optimization of the intermediate bounds.
The general-purpose baselines apply local relaxations to the unrolled selective scan. TaylorSSM constructs bounds for the combined injection, transition history, and readout. IBP and CROWN-IBP serve as stepwise references in Table 1, while SSM-Affine provides a graph-specific affine comparison.
The original GenBaB configuration fixes CROWN/IBP intermediate intervals so that the optimization budget targets the final bound and nonlinear branching. Under the same four-hour budget per task, neither GenBaB configuration certifies any of the 16 pre-SiLU tasks at εin=0.1, whereas Full-QC certifies 11 (Appendix F.4.2).
On the standard four-layer post-SiLU model, joint intermediate-bound optimization exceeds the tested memory or time budgets. Fixing the intermediate intervals permits final-bound optimization, but the resulting bound remains nonpositive. These costs prevent the tested joint optimization from supporting the full radius-search panel, so Appendix F.4.2 reports the targeted trials separately.
Supplying TaylorSSM value intervals to the same GenBaB root calculation raises the number of positive FP64 root bounds from 0/8 to 4/8 on the short-suffix tasks (Table 11). This shows that TaylorSSM's intermediate information also strengthens GenBaB before branching.