acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
neural network verification, certified robustness, selective state-space models, quadratic constraints, recurrent/sequence models, reliable numerical certification

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_derXOpenReview ↗
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 ℓ∞\ell_\infty - 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 O(s2)O(s^2) coefficients per scalar and constructs O(H2)O(H^2) 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
  1. 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?
  2. How was GenBaB configured in the experiments. In particular, why did it not use alpha-CROWN for intermediate bounds?
  3. Why did you choose CROWN-IBP and IBP as baselines in Table 1? Why not stronger bound propagation methods such as α\alpha-CROWN?
  4. Can you provide results of the baseline approaches on the more realistic checkpoint with bounds after the SiLU activation?
  5. What are practical limits in sequence length and model size given the unfavorable scaling behaviour?
4 comments
AuthorsOpenReview ↗

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:

MethodRadius ≥0.01\ge 0.01Radius ≥0.1\ge 0.1
IBP / CROWN-IBP / SSM-Affine00
Direct bound22340
Full-QC19296

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, α\alpha-CROWN, and intermediate-bound optimization

Our GenBaB comparison already includes α\alpha-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\varepsilon_{\mathrm{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.

AuthorsOpenReview ↗

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 ℓ∞\ell_\infty 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, X0+PξX_0+P\xi with ξ∈[−1,1]s\xi\in[-1,1]^s. For a position with kk candidate substitutes, inserting their embedding differences at that position in the columns of PP gives a set containing every candidate, with s=ks=k 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 O(s2)O(s^2) coefficients, and constructing all recurrent readouts requires O(H2)O(H^2) injection-readout pairs. Here HH is the suffix length beginning at the earliest perturbed position, and s=qds=qd for qq jointly perturbed positions of embedding width dd.

For the four-layer, width-384 model at H=32H=32 and εin=0.05\varepsilon_{\mathrm{in}}=0.05, 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 HH, 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 εin=0.01\varepsilon_{\mathrm{in}}=0.01 and H=2H=2 (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.

AuthorsOpenReview ↗

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?

Reviewer_T8HQOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes TaylorSSM, a robustness verifier for Mamba-style selective state-space models. It uses quadratic polynomial enclosures with sound remainders to preserve input dependencies and introduces Full-QC for joint certification using quadratic constraints. Experiments show improved certification over existing methods and demonstrate the usefulness of its intermediate bounds.

Critical strengths
  • The paper presents a dependence-preserving approach to SSM verification, particularly through quadratic polynomial enclosures, accumulated recurrent transitions, and shared remainder propagation.
Critical weaknesses
  • The paper is extremely difficult to follow due to convoluted explanations, notations, and repetitive derivations. A clearer algorithmic overview, a representative end-to-end example, and more intuitive explanations of the mathematical arguments and experimental results are needed. Some of the confusions are:

    • The relationship between TaylorSSM's polynomial enclosures and Full-QC's quadratic constraints is poorly explained, while essential details are scattered across numerous appendices.
    • The experimental presentation is confusing. The paper reports different metrics across tables, including certified radii, certification counts, margin bounds, and bound improvements, without clearly explaining how these results support the main claims.
    • Overall, the presentation substantially cripples the technical assessment of the work.
  • TaylorSSM requires O(s^2) quadratic coefficients per scalar and O(H^2) recurrent readout computations, which substantially limit scalability with perturbation dimension and sequence length. Full-QC adds substantial computational overhead, e.g., taking 4800s at H=32H=32. Moreover, neither method returns valid bounds for the evaluated 8-layer instances.

  • TaylorSSM's accumulated-transition construction requires commuting state-transition operators, which limits its generality. Full-QC requires positive-definiteness conditions on local and global quadratic forms, with no guarantee that suitable QC weights exist even for robust inputs.

Questions for authors
  • Q1: How are TaylorSSM's polynomial enclosures used to construct Full-QC's quadratic constraints? Could the authors illustrate this with a concrete toy example?
  • Q2: Which components require commuting state-transition operators? Can Full-QC handle noncommuting transitions independently of TaylorSSM?
  • Q3: Can Full-QC fail on a robust input because its mathematical conditions are too restrictive, or simply because suitable QC weights cannot be found?
7 comments
AuthorsOpenReview ↗

Response to Reviewer T8HQ (1/2): Presentation overhaul (W1) and toy example (Q1)

Thank you for the detailed feedback, especially the constructive suggestions on readability. Below we address each point.

W1: Readability, connection between methods, and experimental metrics

The revision reorganizes Sections 3 to 5 around a running example in Figure 1 (p. 3) that follows one computation through both certification routes.

Four structural changes address the presentation concerns:

  1. Concretizing Section 3. Starting from the two-step scalar recurrence in Figure 1(a), Section 3 develops TaylorSSM on one diagonal Mamba-1 channel (Section 3.1), deferring general matrix-state recurrences to Appendix A.2. Section 3.2 introduces shared remainders: when one remainder function enters through several fixed linear maps, the maps are combined before bounding so those paths share one remainder variable rather than independent copies. This principle is applied to recurrent readouts (Section 3.3) and RMS normalization (Section 3.4).

  2. End-to-end navigation. Figure 1 traces that same recurrence to both output bounds: panel (b) shows how accumulating step parameters tightens the polynomial enclosure for the direct bound, and panel (c) shows how Full-QC forms a joint bound from local constraints. Algorithm 1 (Appendix A) gives the full-network pass, and an Overview of the Appendices (p. 15) connects the proofs to Sections 3 to 5.

  3. Connecting TaylorSSM and Full-QC (Section 4). The revised text distinguishes three error notions: TaylorSSM remainders (deviations from quadratic polynomial approximations, Section 3.2), Full-QC residuals (deviations from fixed affine relaxations, Section 4.1), and discrepancies (uncovered nonlinear contributions and center offsets, Section 4.2). Section 4.2 derives the certificate in the exact case before introducing discrepancy corrections, and Section 4.3 brings blockwise residual elimination into the main text.

  4. Metric roles (Section 5). Section 5 (p. 7) states how each metric matches its question. Baseline comparisons (Section 5.2, Table 1) report certified counts and maximum certified radii to measure end-to-end verification coverage. When isolating constructions (Section 5.3) or supplying intermediate bounds to affine propagation (Section 5.4), looser variants often yield negative bounds where certified counts stay at zero; margin lower bounds on fixed boxes make tightening visible below the certification threshold.

Q1: Constructing Full-QC's quadratic constraints from TaylorSSM enclosures

TaylorSSM exports validated value intervals at intermediate nodes (Section 3.5), which Full-QC uses to center local affine relaxations and normalize the residuals that replace exact nonlinear relations (Section 4.1).

For positive operand radii, consider w=uvw=uv with TaylorSSM-exported intervals u∈[cu−dˉu,cu+dˉu]u\in[c_u-\bar d_u,c_u+\bar d_u] and v∈[cv−dˉv,cv+dˉv]v\in[c_v-\bar d_v,c_v+\bar d_v]. Writing du=u−cud_u=u-c_u and dv=v−cvd_v=v-c_v, Full-QC retains the affine relation and replaces the exact product definition with two QC inequalities: w=cucv+cvdu+cudv+dˉudˉv,ϵprod,ϵprod2≤du2dˉu2,ϵprod2≤dv2dˉv2.w = c_u c_v + c_v d_u + c_u d_v + \bar d_u\bar d_v\\,\epsilon_{\mathrm{prod}},\quad \epsilon_{\mathrm{prod}}^2 \le \frac{d_u^2}{\bar d_u^2},\quad \epsilon_{\mathrm{prod}}^2 \le \frac{d_v^2}{\bar d_v^2}.
Constraining ϵprod\epsilon_{\mathrm{prod}} by normalized input deviations (du=0d_u=0 forces ϵprod=0\epsilon_{\mathrm{prod}}=0) and sharing it across uses of ww preserves input dependence through the relaxation.

Figure 1 illustrates this on a two-step recurrence with ξ∈[−1,1]\xi\in[-1,1], Δ0,1=1.5±1.25ξ\Delta_{0,1}=1.5\pm 1.25\xi, h−1=2h_{-1}=2, and ϕ=3−o1\phi=3-o_1 (true minimum 0.7590.759). Accumulating Δ0+Δ1=3\Delta_0+\Delta_1=3 removes the prefix remainder, raising the direct bound from −0.25-0.25 to +0.34+0.34 (Figure 1(b)). TaylorSSM also exports the operand interval h0≈1.946±1.548h_0\approx 1.946\pm 1.548 for Full-QC (panel (c)), which relaxes the product e−Δ1h0e^{-\Delta_1}h_0 with an affine envelope plus a residual ϵprod\epsilon_{\mathrm{prod}} constrained by dˉh0≈1.548\bar d_{h_0}\approx 1.548, and similarly assigns residuals at each exponential. The QC through e−Δ1e^{-\Delta_1} receives negligible weight in this example.

The margin is then ϕ=c+ℓϕ\phi=c+\ell_\phi where ℓϕ\ell_\phi is linear in ξ\xi and the residuals. Positive QC weights yield a nonnegative energy J≥0J\ge 0 on original executions; verifying ℓϕ2+J≤U\ell_\phi^2+J\le U for all residual assignments and combining with J≥0J\ge 0 gives ϕ≥c−U≈+0.758\phi\ge c-\sqrt{U}\approx +0.758 (c≈2.566c\approx 2.566, U≈3.268U\approx 3.268).

AuthorsOpenReview ↗

Response to Reviewer T8HQ (2/2): Commutativity (Q2, W3), incompleteness (Q3, W3), and scalability (W2)

Q2 & W3 (Part 1): Role of commuting transitions and decoupling Full-QC

Commutativity is used only in TaylorSSM's accumulated-transition enclosure (Section 3.3); Full-QC's temporal construction accepts noncommuting response matrices (Section 4.3, Proposition 6).

In TaylorSSM, writing a transition product as one exponential of summed step parameters requires commuting step generators. This covers diagonal Mamba-1, scalar-decay Mamba-2, and rotational Mamba-3-style recurrences (eaδτ:te^{a\delta_{\tau:t}} in Eq.(4); Theorem 3, Appendix A.2). The ordered-product history identity (Appendix A.2) uses no commutativity assumption.

Full-QC compiles linear responses and eliminates residuals along the stepwise recurrence, where Proposition 6 (Appendix B.3) admits noncommuting transition matrices in the compiled responses. In our pipeline, the operand radii normalizing local QCs come from TaylorSSM's accumulated enclosures. Extending to architectures with noncommuting input-dependent transitions, such as DeltaNet (Section 3.3), would require both valid intermediate intervals and local affine-plus-residual representations with corresponding QCs at each step; the temporal block algebra itself does not impose commutativity.

Q3 & W3 (Part 2): Why Full-QC can fail to certify a robust input

Yes to both: Full-QC can fail on a robust input either because its quadratic-constraint formulation is a conservative relaxation where no admissible weights certify positivity, or because our finite-budget numerical search misses certifying weights that do exist.

The certificate conditions are sufficient conditions on a relaxed system. Even when optimizing over all admissible QC weights and scales, replacing exact nonlinearities by local QCs enlarges the set of admissible residual trajectories. Bounding the squared linear response ℓϕ2≤U\ell_\phi^2\le U around cc is also two-sided: if the margin rises substantially in part of the box, UU must cover that upward swing as well, lowering c−Uc-\sqrt{U} even when the minimum margin stays positive (and enclosed discrepancies widen this gap; Section 4.2). A robust box therefore need not admit certifying QC weights.

Even when certifying weights exist, solving a global semidefinite program at network scale is prohibitive. Full-QC proposes candidate weights via finite-budget search (Appendix G) and accepts a candidate only when all definiteness and bound-validation checks pass under outward rounding (Section 4.3, Appendix D and E). A candidate that passes can still return a valid but non-positive bound, leaving certification inconclusive. Poor conditioning can also make suitable weights harder to find within the search budget. Soundness holds in all cases.

W2: Scalability, operating boundaries, and 8-layer certification

Both methods now certify the 8-layer model (L=8,d=384L=8, d=384) at εin=0.01\varepsilon_{\mathrm{in}}=0.01. Retaining second-order cross-coordinate and cross-step dependencies carries O(s2)O(s^2) and O(H2)O(H^2) costs whose operating boundaries we document explicitly.

Using the current implementation on the same checkpoint, the direct bound returns +16.01+16.01 in 308308 s and Full-QC returns +12.32+12.32 in 1,0811{,}081 s, each using about 4.74.7 GiB of host memory (Appendix F.6.1). The submission's depth diagnostic tested this instance only at radii 0.050.05 and 0.10.1, where the direct bound encounters interval-arithmetic overflow and Full-QC's local temporal block fails the positive-definiteness check.

Existing verifiers (IBP, CROWN-IBP, GenBaB, and α\alpha-CROWN) already return vacuous bounds or exhaust memory on four-layer models at the tested radii (Section 5.2). Within the quadratic scaling in ss and HH, readout contraction (Eq.(5)) cuts construction time substantially (Section 5.3), while Section 5.5 and Appendix F.6 map our operating boundaries across suffix lengths (H≤32H\le 32), multi-position perturbations, widths, and depths.

Revisions in the updated manuscript

The four structural changes in W1, the 8-layer certificates (Appendix F.6.1), and the metric explanations (Section 5, p. 7) are the main updates. We are happy to discuss any remaining questions.

Thank you for the detailed rebuttal and revisions. The revised paper is substantially easier to follow, e.g., the new running example and the clearer connection between TaylorSSM and Full-QC. The improved presentation clearly shows that TaylorSSM builds on established Taylor-model and symbolic-remainder techniques, so its main contributions appear to be engineering for SSMs, which is perfectly fine as research is one more step towards the goal.

However, several concerns remain:

  1. Could Full-QC use intermediate bounds from existing methods, e.g., CROWN/DeepPoly or DeepZ, instead of TaylorSSM, and how would this affect certification performance?

  2. The paper briefly mentioned the performance differences to the relaxations, but why Full-QC is less effective than direct TaylorSSM at smaller perturbation radii remains unclear.

  3. Full-QC is substantially slower and less effective at smaller radii, and it fails at larger radii on 8-layer models, what is Full-QC's practical advantage?

  4. The experiments already showed failures at 8 layers (H=32). For 4-layer models, what is the maximum perturbed tokens that can be successfully verified?

  5. Mamba are often much deeper with much longer sequences, how can this work scale with its (O(s^2)) storage and (O(H^2)) computational costs? I would expect a credible direction to this problem.

Finally, I would appreciate the revision with the changes highlighted, as the paper is lengthy and it is difficult to identify changes.

Reviewer_f8aPOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents what it claims is the first end-to-end, formally sound robustness verifier for Mamba-style (selective state-space) classifiers. Its core idea, TaylorSSM, represents intermediate values as quadratic polynomials in the input perturbation, plus rigorously bounded error terms. It also combines contributions that share the same perturbation before bounding them, rather than bounding each path’s worst case separately. A second method, Full-QC, uses these bounds to build a joint quadratic-constraint certificate across layers, and the authors show certificates on Yelp/AG News models where IBP, CROWN-IBP and GenBaB fail.

Critical strengths
  • Clear, well-motivated core insight - to look at both state and update rules
  • Quite rigorous soundness: even floating point rounding is measured that is very important
  • Good improvements over standard baselines
  • Covering different Mamba versions
  • Rigorous ablations to separate each step in the proposed method
Critical weaknesses
  • Scalability seems like the main limitation - small models, perturbation is usually a single token, quadratic memory estimation
  • Need not only "pre-SILU", but also "post-SILU" careful evaluation (not on a smaller model only)
  • Baselines are weak (*IBP), and no honest comparison to POLAR/polynomial zonotopes
  • Contribution seems to be complimentary, not a novel method

Update 11/17: improving the score to "Weak Accept"

Questions for authors
  • The main results rely on a verification-friendly pre-SiLU variant rather than standard Mamba.
  • The baseline comparison is weak, especially the absence of POLAR or polynomial-zonotope methods.

These are the main topics to improve - please also consider the "Weaknesses" section

4 comments
AuthorsOpenReview ↗

Response to Reviewer f8aP (1/2): Standard post-SiLU evaluation (W2, Q1) and polynomial baselines (W3, Q2)

We appreciate the recognition of our core insight and the soundness of the floating-point analysis. The two directions you identified as priorities guided much of the revision; we address them first.

W2 & Q1: Standard post-SiLU evaluation at the main model scale

The revised Table 1 reports a standard post-SiLU Mamba-1 model with the same four layers and width 384 as the original main model.

The selectors are computed from SiLU outputs, so the certificates cover the nonlinear activation shared by selection and injection. On the 256-task panel, Table 1 reports the following coverage by attained certified radius:

MethodRadius ≥0.01\ge 0.01Radius ≥0.1\ge 0.1
IBP / CROWN-IBP / SSM-Affine00
Direct bound22340
Full-QC19296

Certification therefore carries over to the standard architecture. Sections 5.1 and 5.2 present both models side by side, with baseline comparisons on each.

W3 & Q2: Polynomial methods and stronger propagation baselines

The revision adds controlled comparisons with POLAR-style symbolic-remainder propagation, including Bernstein candidates, and polynomial zonotopes using CORA operations (Table 3; Appendix F.3.3).

Because each POLAR-style query takes hours on the selective scan, we use one review for a controlled comparison on three-layer, width-192 pre- and post-SiLU checkpoints (H=2H=2). All Taylor-model configurations share the same final direct-bound procedure, so differences in the lower bound isolate each construction. Polynomial zonotopes are evaluated on the post-SiLU checkpoint.

At εin=0.01\varepsilon_{\mathrm{in}}=0.01, every compared configuration returns a positive bound. TaylorSSM stays within 0.07% of the best compared bound while reducing query time from hours to about 20 seconds. The polynomial-zonotope FP64 reference gives a looser bound at substantially higher cost.

To measure what our constructions contribute, we add accumulated transitions, readout contraction, and projected RMS to the same symbolic-remainder implementation. At εin=0.1\varepsilon_{\mathrm{in}}=0.1, these additions raise the lower bound from −22.38-22.38 to −2.07-2.07 on pre-SiLU and from −50.97-50.97 to −15.53-15.53 on post-SiLU, with faster runtime on both checkpoints. POLAR-style propagation with Bernstein candidates gives the tightest post-SiLU bound at this radius, at substantially higher cost; all compared bounds remain negative.

We also compare against optimized propagation and nonlinear search. On the 16-task pre-SiLU panel at εin=0.1\varepsilon_{\mathrm{in}}=0.1, neither GenBaB configuration certifies a task within four hours per task, whereas Full-QC certifies 11. Additional tests of GenBaB intermediate-bound optimization and joint α\alpha-CROWN optimization on the standard four-layer model encounter memory or time limits. These costs prevent the tested joint optimization from supporting the full radius-search panel, so Appendix F.4.2 reports the targeted trials separately.

AuthorsOpenReview ↗

Response to Reviewer f8aP (2/2): Joint certification (W4) and scalability (W1)

W4: Joint certification from the structure of selective SSMs

TaylorSSM combines injection, transition history, and readout before bounding their approximation errors, preserving cancellations that separate stepwise bounds can lose. Prior work represents selective SSMs as input-dependent sequence-mixing operators whose coefficients combine injection, intervening transitions, and readout (Dao & Gu, 2024; Ali et al., 2025). Our work introduces joint remainder bounds for injection, accumulated transitions, and readout, preserving cross-step cancellations that stepwise propagation can lose even with the same quadratic polynomial and shared remainder identities, appling prior insights into the overall input–output structure of Mamba to network verification.

Stepwise and accumulated constructions can yield the same quadratic polynomial in the input perturbation but different remainder bounds. For example, expanding per-step exponentials independently produces remainder variables that cannot represent their cross-step cancellation; accumulating step parameters before the exponential removes that source of overestimation (Figure 1, Proposition 4). The distinction lies in what is bounded and in what order, which existing polynomial representations do not determine on their own.

The architecture literature views selective SSMs as input-dependent mixing operators whose kernels couple injection, transition, and readout [1, 2]. For certification, the input perturbation changes both the mixing coefficients and the signals they mix. Our contribution is to turn this complete relation into joint enclosure rules, building on Taylor models and POLAR's symbolic remainders. Three constructions realize this:

  1. Recurrent enclosures (Section 3.3). After accumulating step parameters, TaylorSSM contracts each readout over state coordinates, combining the injection, transition, and readout contributions before introducing remainder variables. This avoids propagating a separate polynomial for each hidden-state coordinate and bounds the contracted kernel directly (Eq.(5)).

  2. Projected RMS (Section 3.4). The same inherited input error enters both the numerator and denominator of normalization. TaylorSSM combines these two responses with the subsequent projection before bounding, preserving the cancellation between shared errors in the numerator and denominator.

  3. Joint residual certification (Section 4). Full-QC keeps shared signals as common variables when combining constraints from temporal and normalization blocks. Temporal elimination and low-rank RMS structure make this joint calculation possible without a dense global response matrix.

Exporting TaylorSSM bounds transfers the information retained by these constructions to affine propagation and GenBaB (Section 5.4).

W1: Scalability and operating boundaries

The evaluation establishes certificates on tasks unresolved by the tested general-purpose verifiers and explicitly documents the remaining operating boundaries.

O(s2)O(s^2) coefficient storage and O(H2)O(H^2) injection-readout work remain the main limitations. Section 5.5 and Appendices F.5-F.6 evaluate suffix length, model width, depth, and jointly perturbed positions, reporting unsuccessful cases alongside certificates.

The revision adds an eight-layer, width-384 instance certified by both routes at εin=0.01\varepsilon_{\mathrm{in}}=0.01 and H=2H=2 (Appendix F.6.1). The original larger-radius depth diagnostics remain unresolved.

Revisions in the updated manuscript

The same-scale post-SiLU comparison (Table 1), polynomial comparisons (Table 3), running example (Figure 1), and eight-layer certificates (Appendix F.6.1) are the main updates. We welcome any follow-up questions.

References

[1] T. Dao and A. Gu. Transformers are SSMs: Generalized models and efficient algorithms with structured state-space duality. In ICML, 2024.
[2] A. Ali, I. Zimerman, and L. Wolf. The hidden attention of Mamba models. In ACL, 2025.

Thanks to the authors for addressing my concerns. I will improve the score but I'm not an expert in the field of IBP - please take it for granted.

Thank you very much for reviewing our responses and updating your assessment. We appreciate your constructive feedback, particularly your suggestions on the evaluations, which helped us substantially improve the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.