acceptodds
Under review as a conference paper at ICLR 2027

Threshold-Mass CROWN: Direction-Dependent Softmax Bounds for Transformer Verification

Abstract

Attention is difficult to bound because its weights change together: increasing one score changes the probability assigned to every token. A robustness verifier must account for these interactions and their effect on the network's output. We introduce Threshold-Mass CROWN, which uses the coefficients supplied by backward verification to bound a weighted sum of attention probabilities as a whole. The method sorts tokens by these coefficients and bounds the total attention assigned to tokens above each cutoff in the ordering. These bounds combine into one affine function of the attention scores. Propagating this function toward the input can preserve relationships between scores that independent score ranges discard. We prove that this affine function is a lower bound throughout the allowed score ranges. For an attention row with tokens, sorting and cumulative sums take time and working storage per coefficient vector. Across five independently trained one-block models, Threshold-Mass certifies 103 of 500 examples, compared with 49 for the CROWN-LSE baseline, at additional runtime cost. On a 200-property transformer benchmark, it certifies 143 properties. A control that performs the same additional calculation but returns the baseline bound certifies 127. The results show that retaining score relationships can improve certification, although stronger attention bounds alone remain insufficient for some more demanding architectures.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
neural network verification, certified robustness, transformer verification, softmax relaxation, linear bound propagation, CROWN

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_DS2DOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents Threshold-Mass, a verification approach that groups tokens according to the verification objective and derives score-dependent attention bounds. By combining these bounds into an affine function of the scores and using cumulative sums, the method achieves near-linear computation with linear working storage. Experiments show that retaining score dependence can improve certification, although stronger attention bounds alone remain insufficient for more demanding architectures.

Critical strengths
  • This paper is targeting at an important and timely problem for verifying the LLMs.
  • The design can help reduce the overall complexity of the verification and potentially become useful at scale.
  • Evaluation also shows the benefits of algorithmic and runtime effectiveness compared with some baselines.
Critical weaknesses
  • The paper writing is poor and very hard to follow and understand.
  • Many claims are heuristic and empirical and could hardly generalize.
  • Evaluation is largely on small scale datasets and benchmarks.
Questions for authors
  • The writing of this paper is poor, as the first paragraphs of this paper mention about the how to perform the bound verification based on the input changes, however, it is hard to understand the later-on part of backward propagation to achieve the same goal. The author throw out many undefined terms and jargons that make the writing very confused. I would suggest the author to give more background information regarding the backward-based verification and how it work differently compared to the conventional verification solution and its advantages.

  • Also before giving the revised/improved workflow of proposed solution in Figure-1, the author should give a standard workflow for backward propagation for verification.

  • What is the "nested group" here means and how does it actually shows in the Figure 1 is unclear to me.

  • How to handle those overlapped higher coefficient scores? Such as Token 4 and 5 what is the design motivation and intuition behind this?

  • How to handle those cases with non-continuously aligned higher-coefficient tokens, where their index’s are not sequentially aligned, in those cases, how should we define the “group”? Should we have to maintain more fragile and small groups or should we still combine them alongside with other lower-coefficient tokens.

  • Rather comparison with self-built baseline CROWN-LSE, I would suggest author to compare their design with more popular solution w/ or w/o the backward propagations design strategy, so that we can better understand for the design benefits.

  • What is the major evaluated platforms? Also given the current workload, I am wondering what is the utilization of the GPU hardware given the current relatively small workload? Including but not limited to computing and memory resources on the GPU.

  • What is the performance of proposed solution under larger and more popularly used datasets like CIFAR-10/100 or ImageNet?

2 comments

We thank the reviewer for recognizing the importance of verification, the efficient construction, and the reported gains. We also thank them for asking about the workflow, token groups, baselines, GPU use, and larger datasets. We have added clearer explanations and a matched GaLiLeo comparison.

Standard backward verification workflow

We bound each class margin: the correct-class score minus a competing score. A positive lower bound on every margin, over all allowed inputs, proves the property.

  1. Define the input region and compute forward activation ranges.

  2. Select a margin and propagate an affine lower bound backward.

  3. Use lower operator relaxations for positive coefficients and upper relaxations for negative coefficients.

  4. Minimize the resulting affine function over the input region.

An affine bound is a weighted sum plus a constant. Backward CROWN can retain dependencies lost by separate forward intervals. TM supplies the weighted-softmax bound. Branch-and-bound splits unresolved regions. A budget limit leaves the result unknown.

Nested groups and token order

We sort objective coefficients in ascending order with permutation π. Hₘ contains tokens above cutoff m; Lₘ contains the rest. Each mass uses the original full-row softmax probabilities:

q_m(s)&=\sum_{j\in H_m}p_j(s),\\\\ F_c(s)=\sum_j c_jp_j(s) &=c_{\pi(1)}+\sum_{m=1}^{K-1}\Delta c_m q_m(s),\\\\ \Delta c_m&=c_{\pi(m+1)}-c_{\pi(m)}\geq0. \end{aligned}$$ Raising the cutoff removes tokens, so the groups are nested. For coefficients (1,2,4), the identity is 1+(p₂+p₃)+2p₃. Overlap reconstructs each coefficient from successive increases. It creates no extra probability. For coefficients (1,5,2,3,4), sorted token order is (1,3,4,5,2). Cutting after the third coefficient gives H₃={5,2}, with mass p₂+p₅. Lower-coefficient tokens stay outside that group. Only the bound uses the sorted order. Token order, positional encoding, and the mask stay fixed. We restore affine coefficients to the original score order. No extra groups are needed. Figure 1 will show the standard workflow first. Ranked groups, original indices, and shared-input score relationships will follow. **Bound validity and slope selection** In Theorem 3.2, we prove validity in real arithmetic for any real coefficient vector and finite valid score box. Each mass is qₘ=σ(dₘ), where σ is the sigmoid and dₘ=LSE(s_Hₘ)−LSE(s_Lₘ). LSE is the logarithm of a sum of exponentials. A lower high-group bound minus an upper low-group bound gives an affine d̲ₘ≤dₘ. Let [aₘ,bₘ] contain the true log ratio. For any λₘ in [0,1/4], set: $$\begin{aligned} \kappa_m&=\min_{z\in[a_m,b_m]}\\{\sigma(z)-\lambda_m z\\},\\\\ q_m(s)&\geq\lambda_m d_m(s)+\kappa_m \geq\lambda_m\underline d_m(s)+\kappa_m. \end{aligned}$$ Endpoints and interior points where σ′(z)=λₘ give the minimum. Only the true dₘ must lie in the interval. The affine bound may extend below it; λₘ≥0 still gives the second inequality. Nonnegative coefficient gaps complete the proof. The default selects among six valid lines at a reference point. Selection affects tightness; validity needs no convergence.

Verification framework and comparison methods

CROWN-LSE combines CROWN backward bounds (Zhang et al., 2018) with Wei et al.'s LSE softmax bounds (2023). The official verifier is α,β-CROWN/GenBaB with auto_LiRPA. Native adds no TM pass. CROWN-LSE Shadow computes TM's candidate but returns CROWN-LSE's bound. It is the submitted Threshold-Mass shadow arm.

Submitted RTX 5090 study; 100-second budgetCertifiedTimeoutOut of memory
Native CROWN-LSE113/2005532
CROWN-LSE Shadow127/200730
TM143/200570

TM retains every Shadow certificate. Native's memory outcomes also depend on execution conditions. They do not isolate the formula's memory cost.

We add a separate A100 40 GB comparison on all 200 official properties. It uses our validated implementation of GaLiLeo's published relaxation in the same verifier. Both arms share models, input boxes, solver settings, and a 100-second solver limit. Both optimize CROWN-LSE, then add a candidate pass at fixed relaxation parameters. The pass is used before branching and during branch-and-bound.

Additional A100 40 GB experimentCertified properties
GaLiLeo121/200
TM128/200

TM retains every GaLiLeo certificate and adds seven. This is separate from the submitted RTX 5090 Shadow control.

GPU runtime and memory

We use RTX 5090 GPUs for the submitted runs. The main study reports 1.64× baseline runtime for TM.

We profile one two-block, 49-token LayerNorm property on A100 40 GB at 1/255, with all nine class margins. We time 64 raw calls after two warm-ups. Ranges and optimized parameters stay fixed. Memory columns give worker peaks.

Method64 calls, sMean GPU busyAllocated peak, MiBReserved peak, MiB
Native5.83911.93%240.42268
TM11.3616.61%240.42272
GaLiLeo5.41510.33%240.42268

GPU busy uses nominal 200 ms driver windows, not SM occupancy. Device-memory peaks are 839 MiB for Native/GaLiLeo and 843 MiB for TM.

Local O(K)O(K) storage excludes the model, activation bounds, and search state. This earlier profile is separate from the refined LayerNorm tests and submitted timings.

CIFAR and ImageNet experiments

CIFAR-10 is covered by the official suite. CIFAR-100 uses six blocks, 65 tokens, and 13 genuine LayerNorms. The pretrained ViT-S/32 has 12 blocks, 50 tokens, and 25 LayerNorms.

Fixed panelRadiusCertificates per method: Native, GaLiLeo, TM
CIFAR-1002−242^{-24}3/4
CIFAR-1002−162^{-16}, 1/4096, 1/2550/4 at each radius
ImageNetV21/4096, 1/2550/4 at each radius

CIFAR-100 proofs cover all 99 competing classes before branching. TM strengthens 99/1,584 final margins, with no losses, within one shared successful proof.

Model weights and native LayerNorm parameters stay fixed.

ImageNetV2 is separate from ImageNet validation. Two inputs are clean-correct and two are clean errors in FP32 and FP64. All 12 full-class point controls pass. Across both radii, all 999 bounds on each clean-correct box complete and tie. Four boxes remain unknown; four contain clean errors.

Practical-radius certification on these larger models remains open.

Scope and applications

CCT provides compact image classifiers. Zerveas et al. study time-series classification and regression. PatchTST studies forecasting.

TM can bound their weighted softmax attention when valid score bounds are available. Complete verification also needs sound bounds for the other operations.

Reviewer_cHjLOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an affine relaxation for weighted softmax objectives in Transformer verification. The method sorts attention tokens by incoming verification coefficients, rewrites the weighted softmax objective as a sum of cumulative attention masses, and constructs affine lower bounds on these masses. The resulting bound can be propagated backward through the attention-score computation. The paper provides validity proofs and an O(Klog⁡K)O(K\log K) implementation using cumulative sums.

Critical strengths

The proposed affine bound is clean and appears sound. The coefficient-ordering decomposition is easy to understand, and preserving score dependence can improve a backward verification bound. The paper also provides clear validity arguments and a more efficient cumulative-sum implementation.

Critical weaknesses
  1. The experimental validation is far too limited. The main experiment uses one very small architecture: a one-block Fashion-MNIST Transformer without LayerNorm. The VNN-COMP study contains only two small vision-transformer models, with 5 and 17 tokens respectively. The Qwen2.5 experiment is only a local attention-bound comparison and does not perform verification of the language model.

  2. The method largely fails once the architecture becomes slightly more realistic. It certifies only 2/500 examples in the two-block setting, 0/500 with pre-LayerNorm, and 0/500 in the 49-token setting. These results make it difficult to argue that the method is practically useful for Transformer verification beyond very small toy-scale architectures.

  3. The comparison with prior methods is too narrow, without enough discussion in introduction and related work. The main baseline is CROWN-LSE, while stronger or more directly related Transformer-specific relaxations are not compared in the main experiments.

Questions for authors
  1. Why is the main experiment on a one-block Fashion-MNIST Transformer without LayerNorm? Can the authors provide meaningful complete-verification results on standard Transformer architectures with LayerNorm and multiple blocks?

  2. Given the results, what evidence supports the practical relevance of the method for realistic Transformer verification? It looks like the method largely fails once the architecture becomes slightly more realistic.

  3. Why are stronger Transformer-specific baselines such as GaLileo not included in the main end-to-end comparison? The current comparison against CROWN-LSE is not sufficient to establish the benefit.

  4. What is the novelty over Vertex-Softmax? If coefficient ordering and the limitations of independent score boxes are already known, is the main contribution simply an affine relaxation that can be inserted into CROWN?

3 comments

We thank the reviewer for recommending a direct comparison with GaLiLeo. We have added a matched A100 experiment on all 200 official benchmark properties. We also appreciate their recognition of our affine bound and its validity arguments. We thank them for noting the clear coefficient ordering, retained score dependence, and efficient cumulative-sum implementation.

Controlled study and harder architectures

The one-block Fashion-MNIST study isolates the attention bound during complete verification. It has no LayerNorm. It includes nonlinear attention, a residual connection, and a ReLU MLP. Methods share weights and inputs within each of five training seeds. All 500 attempts remain in the comparison, including 142 clean errors.

The official benchmark uses α,β-CROWN/GenBaB with auto_LiRPA. CROWN-LSE uses the LSE softmax relaxation. CROWN-LSE Shadow is the submitted Threshold-Mass shadow arm. It computes TM's extra bound but returns the CROWN-LSE bound. This tests the value of retaining TM's candidate.

StudyReferenceTMPaired gains / losses
Five-seed classifier studyCROWN-LSE: 49/500103/50054 / 0
Submitted official benchmark, RTX 5090CROWN-LSE Shadow: 127/200143/20016 / 0

The harder settings in Appendix D.8 use radius 0.02 and 500 attempts per row.

SettingTMNative LSEBest certificate count among Wei ER/LSE/LSE*
Two blocks2/5000/5000/500
Pre-LayerNorm0/5000/5000/500
49 tokens0/5000/50010/500

The table states the full certificate outcomes. Matched finite-bound comparisons add useful information: TM improves the minimum-margin bound over the strongest Wei reference on all 371 included two-block inputs and 386 pre-LayerNorm inputs. Each is clean-correct, with finite TM and all three Wei bounds. TM and Native exhaust memory on all 335 clean-correct long-row inputs; those calls provide no finite comparison.

New tests also use genuine LayerNorm with two/four blocks, 49 tokens, and hidden width 16. On 32 properties at radii 1/255 and 2/255, a shared intermediate-range refinement strengthens every weakest bound relative to the earlier profile. TM then adds 70/288 stronger final margins, with no losses. The weakest final margins still tie, giving zero certificates for all methods.

This occurs because the verifier returns the largest valid lower bound available. A stronger TM backward candidate can remain below the shared range bound. Across this panel, 207 of 277 raw TM gains stay below that bound; the other 70 reach the final result.

Input searches confirm violations on three clean-correct boxes and two clean-error boxes. Independent replays confirm them. The other 27 remain unresolved.

Complete proofs also extend to a six-block, 65-token CIFAR-100 model with 13 genuine LayerNorms. Each method certifies three boxes against all 99 competing classes at radius 2−242^{-24}. TM strengthens all margins on one certified box. Larger tested radii remain uncertified.

Local Qwen attention experiment

We test recorded attention from Qwen2.5-3B-Instruct. Objective coefficients come from the gradient of the final-token score gap with respect to an attention row. Both methods bound the same weighted softmax over the same score box.

At absolute tolerance 10−610^{-6}, TM gives 409 stronger bounds, 38 ties, and one weaker bound across 448 nonzero-direction cases. Another 64 zero-direction cases are kept separate. Rows have 64 or 128 tokens.

The objective coefficients and local regions stay fixed. Attention probabilities vary within those regions. This tests the relaxation on real model states and directions. A complete language-model proof also needs bounds through changing values, other layers, and the full input region.

Comparison with GaLiLeo and related methods

We use CROWN for backward affine propagation. Wei and GaLiLeo supply published softmax relaxations that account for score interactions. TM uses the incoming objective vector to define groups and bound their total attention.

We add a direct matched comparison with GaLiLeo as an additional rebuttal experiment on A100 40 GB GPUs. The GaLiLeo arm uses our validated implementation of its published relaxation in the same verifier.

Both arms use identical models, input boxes, and solver settings for all 200 properties. Each property has a 100-second solver limit. Both arms optimize CROWN-LSE. An extra TM or GaLiLeo pass then uses fixed relaxation parameters. This pass runs before branching and during branch-and-bound.

Additional A100 40 GB experimentCertified properties
GaLiLeo121/200
TM128/200

TM retains every GaLiLeo certificate and adds seven. The submitted RTX 5090 table above reports the separate CROWN-LSE Shadow control.

Contribution beyond Vertex-Softmax

We credit Vertex-Softmax for ordering and the exact scalar minimum. TM returns an affine score function:

\leq F_c(s)=c^\top\operatorname{softmax}(s).$$ The scalar minimum is the strongest constant on the independent box. The affine function retains score coefficients for further propagation. Let x lie in [−r,r], with a>2r>0, and set s₁=x, s₂=x−a, c=(0,1). The score difference is fixed. TM can use a valid sigmoid tangent: $$\begin{aligned} g_c(s)&=\sigma(-a)+\sigma'(-a)(s_2-s_1+a),\\\\ \min_x g_c(s(x))&=\sigma(-a)>\sigma(-a-2r)=V_{\mathcal B}(c). \end{aligned}$$ Here σ is the sigmoid and V is the exact independent-box minimum. The tangent is valid because the difference interval lies in the sigmoid's convex part. Substitution cancels x. Proposition 3.3 thus proves a strict gain after shared-input composition. Minimizing over the same independent box cannot beat its exact minimum. Theorem 3.4 proves that the prefix–suffix scan returns the same affine coefficients as the direct construction. With a fixed candidate count, it uses $O(K\log K)$ work and $O(K)$ local storage per row and objective vector. | Separate exact-scalar control | Certified properties | | --- | ---: | | Scalar substitution | 110/200 | | TM | 143/200 | This control tests the value of retaining affine coefficients. TM retains every scalar-control certificate. Both arms optimize CROWN-LSE, then add a pass at fixed parameters with the same 100-second budget. **Scope and applications** [CCT](https://arxiv.org/abs/2104.05704) provides compact image classifiers. [Zerveas et al.](https://arxiv.org/abs/2010.02803) study time-series classification and regression. [PatchTST](https://arxiv.org/abs/2211.14730) studies forecasting. TM can bound their weighted softmax attention when valid score bounds are available. Complete verification also needs sound bounds for the other operations.

Thanks for the additional clarifications. But it looks like my main concerns were not addressed. I want to see whether the improvements can translate to more realistic transformers architectures. The current results still provide limited evidence about this point.

Reviewer_qnm7OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Threshold-Mass CROWN, an objective-dependent affine relaxation for the weighted softmax expression encountered during backward verification of transformers. It sorts the incoming objective coefficients and expresses the weighted softmax as a constant plus a nonnegative combination of nested group probabilities, then bounds each group through log-sum-exp and sigmoid relaxations. The authors prove validity in real arithmetic, derive an equivalent implementation requiring O(Klog⁡K)O(K\log K) work and O(K)O(K) auxiliary storage per attention row and coefficient vector, and show how retaining affine score dependence can improve subsequent propagation relative to an exact constant bound over independent score intervals. Experiments report an increase from 49 to 103 certificates across 500 one-block classifier attempts and from 127 to 143 certificates against a computation-matched shadow control on a 200-property verification benchmark, alongside local Qwen attention experiments and substantial limitations on more demanding architectures.

Critical strengths
  1. The objective-dependent construction is well motivated and technically meaningful.
  2. The empirical controls provide substantive evidence that using the new bound helps.
Critical weaknesses
  1. Baseline missing: GaLileo is cited in Section 2 but is not evaluated. It seems to be related.
  2. Limited empirical results: The empirical evaluation is not yet sufficient to establish the practical advantage of the proposed relaxation across representative transformer architectures and relevant competing methods. The one-block Fashion-MNIST classifiers omit LayerNorm. The successful VNN-COMP experiments include two- and three-block models, but these have only five and 17 tokens, respectively, and use robustness-oriented training. These are legitimate verification benchmarks, yet the positive evidence remains concentrated in small, specialized settings.
Questions for authors

See above

3 comments

We thank the reviewer for recommending a direct comparison with GaLiLeo. We have added a matched A100 experiment on all 200 official benchmark properties. We also appreciate their recognition of the objective-dependent construction and the value of our empirical controls. Submitted benchmark and Shadow control

The submitted official benchmark uses α,β-CROWN/GenBaB with auto_LiRPA. The baseline uses the LSE softmax relaxation and is called CROWN-LSE. CROWN-LSE Shadow adds the TM calculation but returns the original CROWN-LSE bound. This is the Threshold-Mass shadow arm in the submitted paper. TM can retain the stronger candidate. Both arms include all 200 properties and use a 100-second budget per property.

Submitted paper, RTX 5090TMCROWN-LSE ShadowPaired TM gains / losses
Official benchmark143/200127/20016 / 0

Additional comparison with GaLiLeo

GaLiLeo supplies a published softmax relaxation that captures interactions between scores. These interactions matter because all attention probabilities share a denominator and sum to one.

TM starts with the weighted attention sum that the verifier must bound. The incoming objective gives one coefficient for each attention entry. Each coefficient describes that entry's contribution to the sum. TM sorts the coefficients and groups entries above each coefficient threshold. It bounds the total probability assigned to each group. The group bounds then combine into one affine bound. This bound retains dependence on the scores for later backward propagation.

We add a direct matched comparison with GaLiLeo as an additional rebuttal experiment. This study runs on A100 40 GB GPUs. It covers all 200 official properties. Both arms use identical input boxes, models, solver settings, and a 100-second solver budget per property. The GaLiLeo arm uses our validated implementation of its published relaxation in the same verifier.

Both arms optimize the same CROWN-LSE baseline. An extra pass evaluates either TM or GaLiLeo, with those relaxation parameters fixed. The added pass is used before branching and during branch-and-bound.

Additional rebuttal experiment, A100 40 GBTMGaLiLeoPaired TM gains / losses
Certified before branching81/20071/20010 / 0
Final certificates128/200121/2007 / 0

The final row includes the properties certified before branching. The gain appears before search and remains under the full solver budget.

Model scale and standard LayerNorm

We construct bounds for weighted attention objectives with valid score bounds. The complete proof also depends on the bounds for other network operations. The table tests this distinction beyond one block.

Supplementary testScopeStronger final TM margins over both controlsCertificates per method
LayerNorm classifiers32 boxes; two/four blocks; 49 tokens70/2880/32
CIFAR-10016 boxes; six blocks; 65 tokens99/1,5843/16
ImageNetV2Eight boxes; pretrained 12-block ViT-S/320/3,996 compared margins0/8

The LayerNorm classifiers have hidden width 16. They use radii 1/255 and 2/255, with nine class margins per property. All methods receive the same tighter intermediate ranges for later LayerNorms and MLP activations. This shared refinement strengthens the weakest bound on every property relative to the earlier profile. TM adds the margin gains shown above, with no final losses. The weakest final margins still tie.

A separate input search confirms violations on three clean-correct boxes and two clean-error boxes. Exact domain checks and independent FP32/FP64 replays confirm them. The other 27 remain unresolved.

The CIFAR-100 model has 13 genuine LayerNorms. Its certificates cover all 99 competing classes and occur only at radius 2−242^{-24}. All methods remain unknown at 2−162^{-16}, 1/4096, and 1/255. The gain in the table strengthens margins within one shared successful proof.

The ImageNet test uses 25 genuine LayerNorms. Four clean-correct boxes complete all 999 bounds at radii 1/255 and 1/4096. Four clean-error boxes remain in the total. ImageNetV2 is separate from ImageNet validation.

The weights and native LayerNorm parameters stay fixed. These tests extend the bound evidence. Practical-radius certification on the larger models remains open.

Scope and applications

Our scope includes compact and task-specific Transformers. Published examples include compact image classifiers, such as CCT. Transformers also support multivariate time-series classification and regression, as shown by Zerveas et al.. PatchTST provides another example in time-series forecasting.

These applications motivate verification across model sizes and prediction tasks. TM develops a bound for weighted softmax attention within this verification process. The experiments above show its measured benefit in the tested verification pipelines.

Thank you for the additional experiments. The matched GaLiLeo comparison substantially addresses my missing-baseline concern.

However, the positive certification gains remain concentrated in highly simplified, arguably toy architectures: one-block models without LayerNorm and two-/three-block models with only five/17 tokens. Even the additional LayerNorm classifiers have a hidden width of just 16.

The larger-model experiments provide no additional certificates over the controls. The LayerNorm panel does not improve any property’s weakest margin; CIFAR-100 certificates occur only at 2−242^{-24} and are shared by all methods; and ImageNetV2 bounds remain unchanged. While the rebuttal strengthens the component-level evidence, my concern about its limited demonstrated practical significance remains.

Therefore, I remain my score.

Comments on the paper

1 comment

We thank the reviewers for their comments on Threshold-Mass CROWN. The main concerns cover related methods, novelty, model scale, clarity, and GPU cost.

TM constructs an objective-dependent affine bound for weighted attention. It retains score coefficients for backward propagation. The paper proves validity and gives an equivalent scan with O(Klog⁡K)O(K\log K) work and O(K)O(K) local storage.

The official benchmark uses α,β-CROWN/GenBaB with auto_LiRPA. Its baseline uses the LSE softmax relaxation, which we call CROWN-LSE. CROWN-LSE Shadow is the submitted paper's Threshold-Mass shadow arm. It computes the extra TM bound but returns the original CROWN-LSE bound. TM can retain the stronger candidate. Each run has a 100-second budget per property. This control tests the value of using TM's bound.

We also add a separate comparison with GaLiLeo on A100 40 GB GPUs. We use our validated implementation of GaLiLeo's published relaxation. Both methods run in the same verifier on all 200 official properties. Each has a 100-second solver budget per property.

TopicEvidence and explanation
Submitted official benchmarkSubmitted paper, RTX 5090: TM 143/200; CROWN-LSE Shadow 127/200. TM retains every Shadow certificate and adds 16.
Additional GaLiLeo comparison, A100 40 GBTM 128/200; GaLiLeo 121/200. TM retains every GaLiLeo certificate and adds seven. This directly compares the two relaxations in the matched verifier.
Contribution beyond Vertex-SoftmaxWe credit the earlier coefficient ordering and exact scalar minimum. TM supplies an affine bound. A shared-input example proves a strict gain after composition. A separate exact-scalar control gives 143 certificates for TM and 110 for the scalar substitution, with no paired losses.
Architecture coverageNew tests include genuine LayerNorm, two and four blocks, and 49 tokens. TM adds 70 stronger final margins out of 288 over both controls. All methods still have zero certificates on these 32 properties.
Larger image modelsA six-block CIFAR-100 model has three complete small-box proofs for every method. TM adds 99 stronger margins. A pretrained 12-block ImageNet model completes all 999 bounds on the clean-correct inputs, with no certificate gain.
Clarity and heuristic claimsThe responses define the standard backward workflow, nested groups, overlap, and nonadjacent indices. They separate the validity theorem from slope selection and measured performance.
Runtime and memoryWe report the paper's runtime tradeoff and add a matched A100 profile with GPU busy and memory measurements. Local construction storage is separated from total verifier memory.

The five-seed classifier study gives 103/500 certificates with TM and 49/500 with CROWN-LSE. This study tests the method across independently trained models.

The new experiments extend the architecture evidence. The CIFAR-100 proofs occur only at radius 2−242^{-24}, about 0.000000060 before normalization. Practical-radius certification on the larger LayerNorm models remains open. TM supplies a proven attention relaxation with measured gains in the tested complete-verification pipelines.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.