acceptodds
Under review as a conference paper at ICLR 2027

Affine Vertex: Directional Softmax Bounds for Transformer Verification

Abstract

Transformer robustness verification requires bounds on attention that remain useful as they propagate through the network. We introduce Affine Vertex, a method that tightens affine softmax bounds while preserving the slopes supplied by an existing verifier. We use exact ranges of weighted softmax outputs to construct a convex lower bound on the residual, the difference between the weighted softmax output and the fixed linear term. Each tangent gives a valid bound, even if the search for a stronger tangent is stopped early. We evaluate these bounds without forming matrices of pairwise interactions between attention scores. For an attention row with scores and a fixed number of optimization steps, this reduces the work from to and the working storage from to . On the official vision-transformer benchmark, Affine Vertex certifies 134 of 200 properties, compared with 127 for a matched control under the same computational budget. Experiments on independently trained models also show certification gains. Controlled comparisons demonstrate gains from convexification and further tangent optimization on selected properties. Independent interval checks validate sampled local bounds. These results show that refining softmax bounds can improve transformer verification, although tighter local bounds do not always yield additional certificates.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
neural network verification, certified robustness, transformer verification, softmax relaxation, affine bounds, convex relaxation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_CQnJOpenReview ↗
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

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 SS is the reachable set, we require

S⊆B=[ℓ,u].S\subseteq B=[\ell,u].

Scores may share inputs and remain correlated. We prove the bound on every point in BB, so it also holds on SS. No probabilistic independence is needed.

For scores (t,t)(t,t) with t∈[−1,1]t\in[-1,1], both probabilities always equal 1/21/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 −∞-\infty 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 α,β\alpha,\beta-CROWN/GenBaB. For output weights cc and inherited slope aa, we bound:

b∗(a)=min⁡s∈Bra(s),ra(s)=c⊤softmax⁡(s)−a⊤s.b^*(a)=\min_{s\in B}r_a(s),\qquad r_a(s)=c^\top\operatorname{softmax}(s)-a^\top s.

We construct a convex hh below the residual. Its tangent at any anchor in BB 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/2551/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/2551/255 without normalization:

Rebuttal Table 1

BlocksShadowAV
247.452.0
337.644.8
431.637.0

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

AV versusTighter returned bounds
Shadow22/22
Midpoint22/22

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).B=[-0.5,0.5]^2,\quad c=(1,0),\quad a=(0.1,-0.1).

cc selects the first softmax probability. Write q=s1−s2q=s_1-s_2. 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.

4 Depth and practical cost

The local cost depends on the number of scores KK and anchor updates TT. We proved

ConstructionWork per rowWorking storage
Dense AVO(K2+TK)O(K^2+TK)O(K2)O(K^2)
Structured AVO(Klog⁡K+TK)O(K\log K+TK)O(K)O(K)

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 1/2551/255 and 2/2552/255 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

BudgetAV versus Shadow: tighter/equal/weaker class-margin bounds
100 s195/66/27 of 288
300 s125/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 m=(ℓ+u)/2m=(\ell+u)/2. We choose nonnegative shifts did_i to make

h(z)=ra(z)+12∑idi(ℓi−zi)(ui−zi)h(z)=r_a(z)+\frac12\sum_i d_i(\ell_i-z_i)(u_i-z_i)

convex and below the residual on BB. The correction is nonpositive inside the box.

Step 2. Compute the gradient. Set p=softmax⁡(z)p=\operatorname{softmax}(z) and Fc(z)=c⊤pF_c(z)=c^\top p. Then

gi(z)=pi(z)(ci−Fc(z))−ai+di(zi−mi).g_i(z)=p_i(z)\bigl(c_i-F_c(z)\bigr)-a_i+d_i(z_i-m_i).

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

Λ=max⁡(0,max⁡i(Hii++di+Ri)).\Lambda=\max(0,\max_i(H_{ii}^{+}+d_i+R_i)).

Here HH is the curvature matrix of the weighted softmax:

H(z)=∇2Fc(z).H(z)=\nabla^2F_c(z).

Throughout BB, Hii+H_{ii}^{+} bounds diagonal entry Hii(z)H_{ii}(z), and RiR_i bounds the sum of absolute off-diagonal entries in row ii. For positive, non-negligible Λ\Lambda,

zk+1=clip⁡(zk−g(zk)Λ,ℓ,u).z^{k+1}=\operatorname{clip}\left(z^k-\frac{g(z^k)}{\Lambda},\ell,u\right).

We subtract the gradient to seek a smaller hh. Clipping puts each coordinate back between its score limits. Near zero curvature, we choose the lower endpoint when gi≥0g_i\ge0 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.
Reviewer_EQ9rOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes Affine Vertex, which tightens softmax bounds in Transformer verification. It preserves the slopes of existing CROWN-LSE relaxations while improving their intercepts using exact directional softmax ranges, convex underestimation, and tangent optimization. A structured implementation reduces the per-row complexity from O(K^2) to O(Klog K). Experiments on Fashion-MNIST Transformers of varying depths and the VNN-COMP ViT benchmark demonstrate improvements in certified properties over existing softmax relaxations.

Critical strengths
  • The paper makes a novel technical contribution to Transformer verification by developing tighter softmax relaxations that preserve existing slopes. The construction is theoretically justified and can be integrated into existing bound-propagation verifiers.

  • The structured implementation reduces the computational complexity from O(K^2) to O(Klog K) and memory usage from O(K^2) to O(K), while preserving the same bounds in exact arithmetic.

Critical weaknesses
  • Affine Vertex falls back to existing CROWN-LSE bounds when the proposed bounds are weaker, so the reported certification results may largely depend on the existing verifier. Although Affine Vertex certifies 7 additional properties on the ViT benchmark, its improvement appears modest and its effectiveness is still unclear. Moreover, in the ablation (Tab. 3b) with 32 problems, tighter bounds produce no additional certifications.

  • Affine Vertex reuses the relaxation parameters optimized for CROWN-LSE instead of optimizing them jointly with the proposed bounds. This means the proposed relaxation uses parameters optimized for a different set of bounds. The paper does not justify this choice or investigate its impact on the tightness of the resulting bounds.

  • The evaluation lacks a direct comparison with state-of-the-art verifiers, e.g., the official α,β-CROWN. Instead, the paper compares against CROWN-LSE and a weaker GaLiLeo-style baseline. Furthermore, all 21 additional certifications over Native CROWN-LSE occur on properties where the baseline runs out of memory. Furthermore, at epsilon=2/255, neither Affine Vertex nor the matched baseline certifies any of the 200 properties, e.g., all are unknown/timeout. Overall, the experimental results provide limited evidence that the proposed bounds substantially improve verification.

Questions for authors
  • Q1: Why does Matched Shadow certify more properties than Native CROWN-LSE (127 vs. 113), despite retaining the same CROWN-LSE bounds?
  • Q2: How are the attention softmax nodes selected for refinement during verification?
  • Q3: Why does Eq. (6) require all three conditions to accept a new bound? In particular, why reject L_V when it improves L_opt but fails another condition?
  • Q4: Why does the anchor optimization minimize the convex underestimator instead of directly maximizing the tangent intercept in Eq. (4)?
  • Q5: What motivates using exactly eight anchor updates, and how sensitive is the bound tightness to this choice?
4 comments

We thank the reviewer for recognizing our fixed-slope contribution, theory and structured implementation. We also thank them for raising questions on parameter reuse, baseline comparisons and anchor optimization.

1 Added contribution

CROWN-LSE gives

a⊤s+b≤c⊤softmax⁡(s).a^\top s+b\le c^\top\operatorname{softmax}(s).

Here ss holds scores, cc weights outputs, aa is the slope and bb is the intercept. AV keeps aa fixed and seeks a larger valid bb. It keeps CROWN-LSE if its candidate is weaker.

We construct a convex hh below the residual

ra(s)=c⊤softmax⁡(s)−a⊤sr_a(s)=c^\top\operatorname{softmax}(s)-a^\top s

on the finite score box BB. An anchor is where we evaluate a tangent. Tangents stay below hh. Their minima over BB give valid intercepts under Theorem 3.1’s curvature conditions, even if we stop after fixed updates.

Full is AV with eight updates. Shadow runs its extra calculations but returns its saved CROWN-LSE bound. At 1/2551/255, Full certifies 134/200 official Vision Transformer (ViT) properties versus Shadow’s 127/200 under the configured 100-second RTX 5090 limit. Full retains all 127 certificates and resolves seven timeouts. Neither arm runs out of memory.

Paper Table 3(a): three repeats per selected case. The midpoint is the center of BB.

Rebuttal Table 1

PropertyMidpoint anchorEight updates
1630/33/3
1751/33/3

Paper Table 3(b)’s broader panel contains none of the seven benchmark gains. All four variants certify the same 21/32 properties. Full tightens local bounds in all 42/64 property/seed runs that use refinement. Appendix H.3 gives tighter output bounds than both Shadow and midpoint in all 22 unresolved comparisons.

2 Reusing relaxation parameters

Parameters α\alpha choose verifier bounds. They differ from trained weights and AV anchors. We optimize α\alpha with CROWN-LSE, then freeze it during extra LSE and AV passes. Updating anchors tests intercept refinement without a new α\alpha search.

We tested one trained two-block Transformer input at 1/40961/4096 before branching. A class margin compares the correct-class and competing-class scores. Certification needs positive lower bounds for all nine margins. Frozen Full improves seven and ties two against continued CROWN-LSE. Joint α\alpha optimization gives zero gains, six ties and three weaker bounds. It uses AV candidates even when locally weaker and has different final retention rules. This pilot supports fixed-α\alpha refinement. It does not isolate freezing alone or rule out better joint schemes.

3 Baseline comparisons

We use α,β\alpha,\beta-CROWN with GenBaB. Native uses CROWN-LSE and the paper’s configuration, without AV passes. GaLiLeo uses our integration of its published softmax bounds in this verifier, rather than the authors’ complete software.

Paper Table 2 gives Full 134/200, Native 113/200 and GaLiLeo 127/200. Paper Table 1 gives certified accuracy (%) at 1/2551/255 without normalization:

Rebuttal Table 2

BlocksNativeGaLiLeoAV
164.264.264.4
247.448.652.0
337.639.044.8
431.233.037.0

Each Paper Table 1 row includes 500 cases across five training seeds. Incorrect original predictions and verification failures remain included. Full beats Shadow at depths three and four in all five training seeds at 1/2551/255.

4 Memory use

Full retains Native’s 113 certificates and adds 21 on Native out-of-memory (OOM) cases. Timeouts and failures remain included.

Our O(K)O(K) storage result concerns one local AV construction, with KK scores per softmax row. Total memory also includes model and search state; its measured peaks are mixed.

On 16 depth-four LayerNorm properties at 300 seconds, AV tightens 125/144 class-margin bounds versus Shadow and ties 19. Both use the same corrected verifier.

5 Radius 2/2552/255

At 2/2552/255, Full and Shadow each certify 0/200 with the 100-second limit on the enlarged official benchmark. All time out, with no OOMs or errors. Unresolved cases are not counterexamples.

Paper Table 1 separately tests models without normalization. Certified accuracy (%) at 2/2552/255 is:

Rebuttal Table 3

BlocksShadowAV
156.257.2
218.223.0
37.010.0
43.23.4

These are separate models from the 200-property benchmark.

6 Shadow versus Native

Our implementation delivers a practical memory advantage on the official ViT benchmark. Native CROWN-LSE has out-of-memory failures; our Shadow implementation has none. Shadow retains CROWN-LSE bounds and certifies 127/200 properties, compared with Native’s 113/200.

Both use the same CROWN-LSE method and compatibility code. Shadow runs extra passes and discards AV’s improvements. The extra execution can change memory use and search progress.

We tested property 158 for 10 seconds without AV refinement. An extra CROWN-LSE-only pass reduced peak memory allocated to live tensors from 25,130 to 13,222 MiB. Both returned saved baselines, completed three optimized calls, processed two domains and timed out.

The diagnostic confirms an execution-related memory reduction. We are testing whether this explains the original 127-versus-113 gap.

7 Softmax node selection

We select all BoundSoftmax nodes, the graph’s softmax operations, including pooling softmax. We do not rank nodes by predicted gain.

After each eligible CROWN-LSE optimization call, we run extra LSE and AV passes with saved α\alpha. This includes smaller regions created during search. Backward bound propagation starts at the final classification condition and reaches earlier softmax layers. We sum the relevant rows across queries and heads before comparing the total intercept with the baseline.

8 Acceptance checks

For the same output and region, LoptL_{\mathrm{opt}} is the optimized CROWN-LSE bound. LsameL_{\mathrm{same}} is the extra LSE bound with saved α\alpha. LVL_V is the AV bound with that α\alpha.

Equation (6) accepts an entry when both comparisons hold:

\qquad L_V>L_{\mathrm{same}}.$$ The first requires an output-bound improvement. The second requires a gain beyond repeat LSE evaluation. We also require at least one local objective to improve anywhere in the AV pass. The comparisons apply per output entry; the local check applies to the whole pass. These checks credit gains to AV. They are separate from validity. If $$L_{\mathrm{same}}\ge L_V>L_{\mathrm{opt}},$$ $L_V$ can be valid but does not beat the AV-off control. We then retain $L_{\mathrm{opt}}$. We also reject it when no local gain is observed. A less restrictive rule could retain valid gains. **9 Anchor objective** Fix $h$ and $B$. The tangent intercept at anchor $z$ is $$b_{\mathrm{tan}}(z)= \min_{s\in B}\left[h(z)+\nabla h(z)^\top(s-z)\right].$$ Every anchor satisfies $$b_{\mathrm{tan}}(z)\le\min_{s\in B}h(s).$$ At a constrained minimizer $z^*$, the tangent cannot decrease in any feasible direction. Its minimum is therefore $h(z^*)$, even at a box boundary. Thus $$\max_{z\in B}b_{\mathrm{tan}}(z)=\min_{s\in B}h(s).$$ Minimizing $h$ targets the same best tangent value for fixed $h$. Direct intercept maximization can be nonsmooth because gradient sign changes switch box endpoints. Search on $h$ is smooth and convex. We evaluate each tangent and retain the strongest. The value $h(z)$ alone does not certify a lower bound on its minimum. Anchor search can close the gap to the minimum of $h$, but cannot remove the gap between $h$ and the residual. **10 Eight updates** $T$ counts anchor updates. $T=0$ evaluates the midpoint tangent and retains the decomposed and Taylor bounds. Decomposed bounds the residual’s terms separately. Taylor uses a midpoint expansion and curvature allowance. $T=8$ evaluates nine tangents. We tested $T\in\{0,1,2,4,8,16\}$ on 30 local problems selected using earlier outcomes, with fixed coefficients, slopes and score limits. Gain is the mean retained-intercept increase over $T=0$. **Rebuttal Table 4** | $K$ | 8-update share of 16-update gain | Local time at 8 / 16, ms | | --- | ---: | ---: | | 5 | 94.71% | 10.05 / 13.15 | | 17 | 82.63% | 10.09 / 13.22 | We used eight updates as a fixed refinement budget. Our additional sensitivity study supports this choice. Eight updates capture much of sixteen updates’ tightening at lower local cost. This is a measured local tradeoff, not a universal optimum.

I maintain my score for the following reasons:

  • The rebuttal does not follow the order of weaknesses and questions in my review and does not address them directly, IT COST ME TIME TO LOCATE AND VALIDATE THE EVIDENCES.
  • W1: The gain over Matched Shadow is marginal (only 7 out of 200 properties), and the broader results in Tab. 3b still show no gain at all.
  • W2: Reusing the CROWN-LSE parameters remains unjustified. The only evidence provided is a pilot test on a single input (nine margins), which is far too limited to generalize.
  • W3 and Q1: The comparison with Native CROWN-LSE does not show that the proposed bounds actually help, as all 21 gains is from baseline OOMs rather than bound precision. The authors in their own words admit that they still running experiment to find an explaination why Shadow improved over CROWN-LSE. At the larger radius 2/2552/255, there is still no benefit, as both methods certify 0 out of 200 properties.

We thank the reviewer for the additional feedback. We understand the concerns about the contribution of our method, the effect of the reported improvements. For a more clear ablation study we are presenting the table below , for an extended version of the ViT competition benchmark with 24 blocks deep transformer model. By native we mean the official implementation of method (alpha beta crown and GenBaB) and by shadow we mean our implementation, but the improvement by Affine Vertex (AV) is discarded. The table results show that AV improves 98.3–100% of class bounds for the IBP and 21.4–38.7% for the PGD. This signifies the gain our algorithm offer compared to the state of the art transformer verifier methods. We performed these tests on a A100 80GB (compared to rtx5090 32GB), so we would not have the memory restriction for the native method which is the official implementation of the CROWN LSE.

Each triplet is better / tied / worse (%)

αβGenBaBPGD vs NativePGD vs ShadowIBP vs NativeIBP vs Shadow
OFFOFFOFF38.7 / 61.3 / 0.038.7 / 61.3 / 0.099.2 / 0.8 / 0.099.2 / 0.8 / 0.0
OFFOFFON36.4 / 61.3 / 2.238.1 / 61.3 / 0.698.6 / 0.0 / 1.499.7 / 0.0 / 0.3
OFFONOFF38.7 / 61.3 / 0.038.7 / 61.3 / 0.099.1 / 0.6 / 0.398.3 / 0.4 / 0.2
OFFONON36.4 / 61.3 / 2.238.6 / 61.3 / 0.1100.0 / 0.0 / 0.0100.0 / 0.0 / 0.0
ONOFFOFF21.4 / 76.8 / 1.822.3 / 77.7 / 0.099.6 / 0.1 / 0.399.9 / 0.1 / 0.0
ONOFFON23.3 / 76.7 / 0.023.3 / 76.7 / 0.0100.0 / 0.0 / 0.0100.0 / 0.0 / 0.0
ONONOFF21.9 / 76.4 / 1.722.2 / 77.8 / 0.099.4 / 0.1 / 0.499.6 / 0.1 / 0.3
ONONON23.3 / 76.7 / 0.023.3 / 76.7 / 0.0100.0 / 0.0 / 0.0100.0 / 0.0 / 0.0
Reviewer_6QsHOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Affine Vertex, a method for tightening affine softmax bounds in transformer verification while preserving the slopes of existing affine relaxations. The approach formulates the problem as an intercept optimization, using directional softmax ranges and a convex underestimator to derive sound affine bounds. The authors also present a structured implementation with (O(K\log K)) complexity for a fixed number of optimization steps and integrate the method into a CROWN-based verifier.

Experiments show improvements in certification, including 134 versus 127 certified properties on the official ViT benchmark under a matched comparison.

Critical strengths
  • Interesting formulation. The fixed-slope intercept optimization perspective is appealing and provides a natural way to strengthen existing softmax relaxations without changing their slopes. The formulation is well motivated in the context of backward bound propagation.

  • Sound technical development. The convexification and tangent-based construction provide valid bounds without requiring convergence of the optimization procedure. The structured implementation is also a useful technical contribution.

  • Encouraging empirical results. The method improves certification on several small transformer architectures and the official benchmark. I particularly appreciate the matched Shadow experiment, which performs the additional bound computations but discards their improvements. This provides a meaningful control for isolating the contribution of the tighter bounds from the additional computation.

  • Clear presentation. The paper is generally well organized, with mathematical proofs, implementation details, and appropriate discussion of limitations.

Critical weaknesses
  • Moderate novelty. Several ingredients have connections to established convexification and softmax relaxation techniques. The contribution appears to lie primarily in combining and adapting these ideas to fixed-slope intercept refinement, rather than introducing a fundamentally new relaxation framework. I would appreciate a clearer high-level distinction from existing approaches, particularly CROWN-LSE and GaLiLeo.

  • Limited experimental scale. The evaluated transformers are relatively small, with short attention sequences and limited depth. In particular, standard LayerNorm architectures are not covered. It remains unclear how the approach performs on more realistic transformer models.

  • Unclear practical efficiency advantage. The reduction from quadratic complexity to (O(K\log K)) is a useful result, but this comparison is against the dense implementation of the proposed construction. It does not necessarily establish improved efficiency relative to existing softmax relaxations. Runtime and memory comparisons at larger sequence lengths would make this contribution more convincing.

  • Modest certification gains and mixed ablations. The matched benchmark improvement is seven additional certificates out of 200. While positive, the improvement is relatively modest. Additionally, the broader ablation panel shows no differences in certified-property counts among the variants, despite local bound improvements. The conditions under which the additional optimization meaningfully improves certification are not yet fully characterized.

Questions for authors
  1. Could the authors clarify the main conceptual differences from existing softmax relaxation methods, particularly CROWN-LSE and GaLiLeo?

  2. Can the authors provide runtime and memory comparisons against existing methods, especially as the number of attention tokens increases? The asymptotic improvement over the dense formulation does not necessarily imply an advantage over existing verifiers.

  3. How does the method behave on larger transformers and architectures with standard LayerNorm?

  4. Can the authors further characterize when convexification and anchor optimization improve certification, given the mixed results in the ablation study?

3 comments

We thank the reviewer for recognizing the fixed-slope idea, valid tangent construction, structured algorithm and matched Shadow control. We also appreciate their positive assessment of our presentation and certification results.

1 Contribution relative to CROWN-LSE and GaLiLeo

Our verifier uses α,β\alpha,\beta-CROWN with GenBaB and CROWN-LSE softmax bounds. We implement GaLiLeo’s published bounds in this framework. GaLiLeo constructs affine bounds from the joint score inputs. AV starts from an existing affine bound and strengthens its intercept for the current weighted objective, while keeping its slope fixed.

For incoming coefficients c, inherited slope a and finite score box B, we form:

ra(s)=c⊤softmax⁡(s)−a⊤s,b∗(a)=min⁡s∈Bra(s).r_a(s)=c^\top\operatorname{softmax}(s)-a^\top s,\qquad b^*(a)=\min_{s\in B}r_a(s).

The affine lower bound is a⊤s+ba^\top s+b. Thus, a larger valid b raises the bound throughout B without changing its slope. We use directional ranges and curvature bounds to construct a convex underestimator of r_a. We then minimize each anchor tangent over B to obtain an intercept candidate.

Theorem 3.1 gives a valid bound at each anchor inside the finite score box under the stated curvature conditions. Updates seek stronger bounds. We can stop after a fixed number of updates and retain the best valid candidate and inherited baseline.

During backward bound propagation, AV refines the local intercept without changing the slope coefficients passed to earlier layers.

Theorem 3.2 proves that the structured calculation preserves the dense construction in exact arithmetic.

2 Runtime and memory

Full AV adds curvature calculations and eight anchor updates to CROWN-LSE. Seeking a stronger intercept at the same slope adds local time and memory. For K scores and T updates, structured AV uses O(Klog⁡K+TK)O(K\log K+TK) work and O(K)O(K) storage. Dense AV uses O(K2+TK)O(K^2+TK) work and O(K2)O(K^2) storage. We process anchors one at a time.

Local costs (K=1024, RTX 5090): median of 3 seed medians. Memory is cold-call peak PyTorch allocation, including resident inputs.

Rebuttal Table 1

CalculationTime, msPeak allocation, MiB
CROWN-LSE1.380.44
GaLiLeo5.15777.27
Dense AV11.68449.60
Structured AV11.732.60

Structured AV cuts local allocation from 449.60 to 2.60 MiB. Whole-verifier peaks are mixed. At 300 s on 16 LayerNorm properties, AV’s allocated peaks are lower/equal/higher than Native’s on 9/2/5 cases and Shadow’s on 7/2/7. Native is CROWN-LSE without AV’s extra passes.

Separately, Paper Table 2 tests 200 official CIFAR-10 ViT properties at 1/255 with a configured 100-second RTX 5090 limit. Shadow computes Full’s extra AV candidates but discards their improvements and returns the saved CROWN-LSE bound. AV certifies 134/200 versus Shadow’s 127/200, retaining every Shadow certificate and resolving seven timeouts. Neither arm has an OOM. This shows a certification gain while paying for bound construction.

3 Model scale and standard LayerNorm

We used five training seeds per depth in Paper Table 1 to test whether gains survive propagation through one to four blocks. Each depth/radius row contains 500 cases, including clean errors and verification failures. Paper Table 1 reports paired certification gains and seed SD. It shows that the benefit is not confined to one checkpoint or one block.

We tested mean-only normalization at 1/255 on correctly classified inputs:

Rebuttal Table 2

Shadow certificatesAV certificates
163/240174/240

AV retains every Shadow certificate. We test standard LayerNorm separately.

We tested genuine pre-LayerNorm with input-dependent statistics. We used two training seeds at each of depths two and four, 49 tokens, width 16 and two heads. Four images at radii 1/255 and 2/255 give 32 properties with nine class margins each. The longer panel repeats the original 16 depth-four properties. Nine margins belong to each property. We report them as margin comparisons, not as 288 independent model trials. The certificate count uses the model/input/radius properties.

Rebuttal Table 3

BudgetAV versus Shadow: tighter/equal/weaker class-margin bounds
100 s195/66/27 of 288
300 s125/19/0 of 144

All arms use the same corrected verifier. We retained completed global-root/frontier bounds with interval bound propagation at 100 seconds and final frontier bounds at 300 seconds. Observations did not feed search; their overhead counted inside the budget. All shorter-budget regressions remain included.

A robustness certificate requires positive lower bounds for every competing class margin. Our results show that AV can tighten bounds through genuine LayerNorm. These panels still have zero certificates. Thus, tighter bounds and completed verification are distinct results.

4 When the components help

The selected-case study in Paper Table 3(a) compares decomposed/Taylor bounds (D+T), the midpoint and eight updates. On properties 142, 154 and 181, midpoint and AV certify 3/3 repetitions; D+T certifies 0/3 in a separate comparison. Anchor updates add certificates here:

Rebuttal Table 4

PropertyMidpointAV
1630/33/3
1751/33/3

Entries count certified repetitions on these selected gains.

We tested 32 properties at two solver seeds, giving 64 runs. The verifier evaluated AV refinement in 42 runs. AV tightened the local bounds in all 42.

In Appendix H.1, we repeated the local calculations with the same coefficients, slopes and score limits. This isolates the improvement from our bound construction. In Appendix H.3, we tested 11 properties from the broader panel at two solver seeds. AV returned tighter output bounds than both Shadow and the midpoint variant in all 22 comparisons. These results show stronger bounds in both local calculations and final verification outputs.

Reviewer_6QsHOpenReview ↗

Thanks for the rebuttal!

The rebuttal addresses several of my concerns with additional experiments, particularly on memory efficiency, LayerNorm, and the impact of anchor optimization on certification.

However, the contribution remains relatively incremental, with substantial runtime overhead and limited evidence of improved certification on realistic architectures. I therefore maintain my weak accept score.

Comments on the paper

2 comments

We thank the reviewers for recognizing the fixed-slope formulation, valid bound construction and structured implementation. They raised questions about the added contribution, baseline comparisons, practical cost, model scope and clarity. We address these points with the existing controlled experiments, additional bound tests and explicit mathematical explanations.

Contribution and comparisons

We strengthen a softmax intercept while preserving the slope supplied by the verifier. We form the residual c⊤softmax⁡(s)−a⊤sc^\top\operatorname{softmax}(s)-a^\top s and construct valid tangent lower bounds on its minimum over a finite score box. Theorem 3.1 gives a valid bound at each anchor inside the finite score box under the stated curvature conditions. The updates seek stronger bounds. Validity is preserved when we stop after a fixed number of updates. Theorem 3.2 proves that our structured calculation preserves the dense construction in exact arithmetic, with O(Klog⁡K)O(K\log K) work and O(K)O(K) working storage per row for a fixed update budget.

We use α,β\alpha,\beta-CROWN with GenBaB and CROWN-LSE softmax bounds as our verification framework. Native is this CROWN-LSE baseline without AV’s additional calculations. We implement GaLiLeo’s published softmax bounds in the same framework. Paper Table 2 separates these baseline comparisons from the matched Shadow control.

Evidence for the added bound

Full uses AV with eight updates. Shadow performs Full’s extra AV calculations but discards their improvements and returns the saved CROWN-LSE baseline. This tests the benefit of retaining tighter bounds. Paper Table 2 uses 200 official ViT properties at 1/255 and a configured 100-second RTX 5090 limit:

Rebuttal Table 1

ControlControl certificatesAV certificates
Native113/200134/200
GaLiLeo127/200134/200
Shadow127/200134/200

The Native/GaLiLeo and matched Shadow comparisons are separate. AV retains every Shadow certificate and resolves seven timeouts; neither matched arm has an OOM.

Paper Table 1 adds five-seed comparisons across one to four blocks. It reports paired certification gains with clean errors and verification failures included. Paper Table 2 also reports Full’s seven-certificate advantage over GaLiLeo. The separate 21-certificate gain over Native occurs on Native OOM cases; we treat it as a completion result rather than attributing it entirely to bound tightness.

We also explained Shadow’s call-level baseline restoration and tested an extra-LSE control. The diagnostic shows an allocation effect without AV mathematics. We keep it separate from an explanation of the exact original Shadow/Native count difference.

Components and parameter choices

The selected-case component study in Paper Table 3(a) tests which components explain the seven benchmark gains. Convexification and anchor updates can enable additional robustness certificates. The broader component study in Paper Table 3(b) reports the same 21/32 certificates for every variant, despite local improvements. Our fixed-input ablations and stronger negative returned bounds explain why tighter bounds need not cross the certification threshold.

We first optimize the CROWN-LSE relaxation parameters. We then keep them fixed during the additional AV calculations, while updating the anchors. This isolates the contribution of intercept refinement. We also reported a limited joint-optimization pilot with its different retention policy. A 30-group sensitivity study shows that eight updates capture much of the local gain from sixteen at lower local cost. We clarified node coverage, the three acceptance checks and why minimizing the convex underestimator targets its best tangent certificate.

Standard LayerNorm and scale

We tested four genuine pre-LayerNorm checkpoints at depths two and four with 49 tokens. Four images and two radii give 32 properties; the longer test repeats the 16 depth-four properties. All methods use the same corrected verifier implementation.

Rebuttal Table 2

BudgetAV versus Shadow: tighter/equal/weaker class-margin bounds
100 s, 32 properties195/66/27 of 288
300 s, 16 properties125/19/0 of 144

Our results show that AV can produce tighter class-margin bounds in models with standard LayerNorm.

Clarity and scope

We explain finite score boxes without imposing probabilistic independence. We give the anchor update, a running example and the reason for local float64. Appendix G checks emitted local bounds with independent interval arithmetic. We distinguish analytic proofs from a future Lean formalization.

Our results show two benefits. AV certifies seven more official benchmark properties than the matched control. In separate tests, AV also produces tighter bounds when the number of certified properties stays unchanged.

Since the reviewers asked for a more clear ablation study we are presenting the table below , for an extended version of the ViT competition benchmark with 24 blocks deep transformer model. By native we mean the official implementation of method (alpha beta crown and GenBaB) and by shadow we mean our implementation, but the improvement by Affine Vertex (AV) is discarded. The table results show that AV improves 98.3–100% of class bounds for the IBP and 21.4–38.7% for the PGD. This signifies the gain our algorithm offer compared to the state of the art transformer verifier methods.

Each triplet is better / tied / worse (%)

αβGenBaBPGD vs NativePGD vs ShadowIBP vs NativeIBP vs Shadow
OFFOFFOFF38.7 / 61.3 / 0.038.7 / 61.3 / 0.099.2 / 0.8 / 0.099.2 / 0.8 / 0.0
OFFOFFON36.4 / 61.3 / 2.238.1 / 61.3 / 0.698.6 / 0.0 / 1.499.7 / 0.0 / 0.3
OFFONOFF38.7 / 61.3 / 0.038.7 / 61.3 / 0.099.1 / 0.6 / 0.398.3 / 0.4 / 0.2
OFFONON36.4 / 61.3 / 2.238.6 / 61.3 / 0.1100.0 / 0.0 / 0.0100.0 / 0.0 / 0.0
ONOFFOFF21.4 / 76.8 / 1.822.3 / 77.7 / 0.099.6 / 0.1 / 0.399.9 / 0.1 / 0.0
ONOFFON23.3 / 76.7 / 0.023.3 / 76.7 / 0.0100.0 / 0.0 / 0.0100.0 / 0.0 / 0.0
ONONOFF21.9 / 76.4 / 1.722.2 / 77.8 / 0.099.4 / 0.1 / 0.499.6 / 0.1 / 0.3
ONONON23.3 / 76.7 / 0.023.3 / 76.7 / 0.0100.0 / 0.0 / 0.0100.0 / 0.0 / 0.0

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.