- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper aims to improve formal robustness verification of transformer-based model. In particular, the paper provides an optimization on the bound computation during the softmax enclosure. This is realized via a convex relaxation of the residual and updating its tangent, which also acts as a lower bound of the residual.
Critical strengths
- Analyzing robustness properties of transformers is a timely and necessary topic
- Improving computation and memory constraints helps theoretically with scalability to larger models.
- The derived results seem sound to me, but a Lean formalization would strengthen the result.
Critical weaknesses
- I have found the paper incredibly difficult to read. It is overloaded with exhaustive explanations with awkward phrasings. For example, what does "A box encloses the scores without assuming probabilistic independence; infinite masking logits are outside these assumptions" (l.172) mean? The first part seems to say there is no assumption, but the second part says something is outside of multiple (?) assumptions.
- From what I understood, the paper is incremental at most. It optimizes some bounds of the softmax enclosure, which is only one step of verifying the entire model.
- While such relatively small improvements can obtains significant improvements, the paper fails to show this as even the headline result in the abstract says it barely improves over the baseline (+5%) .
- Moreover, only models with up to 4 transformer blocks were analyzed, while the cited related work can verify up to 12 blocks. This makes the improved memory and runtime questionable.
Questions for authors
- l.231: How is the location for stronger tangents updated? I can't seem to find a formula.
- Appendix B talks about floating point evaluation of the algorithm Why is it necessary to refine the float32 used by the verifier to float64?
- Can you add a running example for you algorithm? I would expect that iterative bound optimizations with subsequent tighter enclosures to be easy to illustrate.
2 comments
4 Depth and practical cost
The local cost depends on the number of scores and anchor updates . We proved
| Construction | Work per row | Working storage |
|---|---|---|
| Dense AV | ||
| Structured AV |
We process anchors sequentially. More Transformer blocks add rows and other verifier operations; four blocks is a tested depth, not a method-imposed limit. A fair comparison with twelve blocks needs matched width, token count, normalization, properties and resources. We do not yet report that matched comparison.
Whole-verifier memory remains mixed.
We tested genuine pre-LayerNorm at depths two and four: two seeds each, 49 tokens, width 16 and two heads. Four images at and give 32 properties and 288 class margins. The 300-second panel reuses the original 16 depth-four properties. All arms share the corrected verifier.
Rebuttal Table 4
| Budget | AV versus Shadow: tighter/equal/weaker class-margin bounds |
|---|---|
| 100 s | 195/66/27 of 288 |
| 300 s | 125/19/0 of 144 |
A class margin subtracts a competing-class score from the correct-class score. We retain completed output bounds with interval bound propagation. At 100 seconds these include returns before and during search; at 300 seconds we use final search bounds. The 27 weaker bounds reflect missing completed returns before the deadline.
These results show refinement through standard LayerNorm. The panels have no complete certificates: all competing-class bounds must become positive to certify an input.
5 Anchor update step by step
Appendix A.3, Equation (18), gives the formula.
Step 1. Build the convex function. Let . We choose nonnegative shifts to make
convex and below the residual on . The correction is nonpositive inside the box.
Step 2. Compute the gradient. Set and . Then
The terms differentiate the weighted softmax, subtract the fixed slope, and differentiate the convex correction.
Step 3. Set the step scale and move. We use
Here is the curvature matrix of the weighted softmax:
Throughout , bounds diagonal entry , and bounds the sum of absolute off-diagonal entries in row . For positive, non-negligible ,
We subtract the gradient to seek a smaller . Clipping puts each coordinate back between its score limits. Near zero curvature, we choose the lower endpoint when and the upper endpoint otherwise.
Step 4. Evaluate the tangent and keep the best. We compute
\min_{s\in B}\left[h(z)+g(z)^\top(s-z)\right].$$ Each feasible anchor gives a valid candidate (Theorem 3.1). We retain the strongest evaluated tangent, together with the decomposed and Taylor bounds. The decomposed bound handles the residual’s terms separately. A later anchor need not improve the intercept. Eight updates evaluate nine tangents, including the midpoint. The coefficients, slope and box remain fixed. **6 Why the local calculation uses float64** We use float64 to reduce loss of digits in local arithmetic. Positive and negative terms can nearly cancel, leaving a small difference. Float32 can lose useful digits in that difference. Residual and curvature calculations have the same sensitivity. Only the local bound calculation uses float64. The verifier’s parameters stay in float32. We apply numerical allowances and round lower bounds downward on return. More precision cannot recover earlier lost information or prove soundness alone. Appendix G independently checks unchanged emitted bounds using outward-rounded intervals. All 112 listed local cases, covering 2,416 rows, pass at 128-bit precision. The checks assume valid incoming boxes and the interval library. Structured equivalence remains an exact-arithmetic result. **7 Lean formalization** We appreciate the Lean suggestion. Our theorems prove validity and structured equivalence. Interval checks test listed numerical outputs. Lean formalization would add assurance and remains future work.
We thank the reviewer for recognizing the importance of Transformer verification, soundness and reduced construction cost. We also appreciate the questions on assumptions, anchor updates, precision and scale, and the request for a running example.
We will add the worked example to the paper and place the update formula beside the main-text anchor description.
1 Score boxes and dependence
We separate two conditions. First, the box must contain every reachable score vector. If S is the reachable set, we require
S⊆B=[ℓ,u].
Scores may share inputs and remain correlated. We prove the bound on every point in B, so it also holds on S. No probabilistic independence is needed.
For scores (t,t) with t∈[−1,1], both probabilities always equal 1/2. The enclosing box also contains unreachable pairs. This can weaken tightness, while preserving validity.
Second, finite endpoints are needed for curvature and anchor calculations. A masking value of −∞ is outside this theorem. A fixed mask admits a reduced problem over nonempty finite scores, with the slope and coefficients reduced consistently. This mathematical reduction does not claim automatic mask removal by our code.
2 Contribution and complete certificates
AV adds fixed-slope intercept refinement to α,β-CROWN/GenBaB. For output weights c and inherited slope a, we bound:
b∗(a)=mins∈Bra(s),ra(s)=c⊤softmax(s)−a⊤s.
We construct a convex h below the residual. Its tangent at any anchor in B gives a valid intercept under Theorem 3.1’s curvature assumptions. Stopping after fixed updates preserves validity. Theorem 3.2 gives the same construction as dense AV in exact arithmetic, with lower local cost.
Shadow runs Full’s extra AV calculations but returns its saved CROWN-LSE bound. Paper Table 2 gives Full (eight updates) 134/200 versus Shadow 127/200 on the official CIFAR-10 Vision Transformer (ViT) benchmark at 1/255, with a configured 100-second RTX 5090 limit. Full retains every Shadow certificate and resolves seven timeouts. Neither arm runs out of memory.
Seven additional certificates mean 3.5 percentage points or 5.51% relative to Shadow. Paper Table 1 shows certified accuracy (%) at 1/255 without normalization:
Rebuttal Table 1
Each row includes 500 cases across five training seeds, including incorrect original predictions and verification failures. Every seed at depths three and four improves over Shadow.
Appendix H.3 tests 11 unresolved properties at two solver seeds:
Rebuttal Table 2
These are output-bound gains. Paper Table 3(a) shows selected certificate gains. Paper Table 3(b) retains the same 21/32 certificates, while Full tightens local bounds whenever it refines (42/64 property/seed runs).
3 Running example step by step
Step 1. Fix the scores and slope. Take
B=[−0.5,0.5]2,c=(1,0),a=(0.1,−0.1).
c selects the first softmax probability. Write q=s1−s2. Then
r_a(s)=\frac{1}{1+e^{-q}}-0.1q.$$ We seek a larger constant $b$ in the bound $F_c(s)\ge0.1q+b$. The box and slope stay fixed. **Step 2. Start at the midpoint.** The initial anchor is $z^0=(0,0)$. For this example we use $$d\approx(0.49395,0.33783),\qquad h(z^0)\approx0.3960.$$ The midpoint tangent gives about 0.2460. We also evaluate a Taylor bound using the midpoint value, gradient and curvature bound. It gives 0.2586, so we retain 0.2586. **Step 3. Move and evaluate again.** The initial gradient is $(0.15,-0.15)$ and the step scale is about 0.8318. The update explained below gives $$z^1=\operatorname{clip}\left((0,0)-\frac{(0.15,-0.15)}{0.8318},-0.5,0.5\right) \approx(-0.1803,0.1803).$$ We minimize its tangent over the box and keep a stronger intercept when found: **Rebuttal Table 3** | Updates | Approximate retained intercept | | --- | ---: | | 0 | 0.2586 | | 1 | 0.3136 | | 8 | 0.3460 | Each retained gain raises the affine bound. The box does not shrink. The fixed-slope ceiling is $$b^*(a)=\frac{1}{1+e}+0.1\approx0.36894.$$ The example shows progress toward that ceiling. Its rounded values omit numerical allowances; it illustrates the local mechanism, not a network certificate.