- 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
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 budget | Certified | Timeout | Out of memory |
|---|---|---|---|
| Native CROWN-LSE | 113/200 | 55 | 32 |
| CROWN-LSE Shadow | 127/200 | 73 | 0 |
| TM | 143/200 | 57 | 0 |
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 experiment | Certified properties |
|---|---|
| GaLiLeo | 121/200 |
| TM | 128/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.
| Method | 64 calls, s | Mean GPU busy | Allocated peak, MiB | Reserved peak, MiB |
|---|---|---|---|---|
| Native | 5.839 | 11.93% | 240.42 | 268 |
| TM | 11.361 | 6.61% | 240.42 | 272 |
| GaLiLeo | 5.415 | 10.33% | 240.42 | 268 |
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 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 panel | Radius | Certificates per method: Native, GaLiLeo, TM |
|---|---|---|
| CIFAR-100 | 3/4 | |
| CIFAR-100 | , 1/4096, 1/255 | 0/4 at each radius |
| ImageNetV2 | 1/4096, 1/255 | 0/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.
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.
Define the input region and compute forward activation ranges.
Select a margin and propagate an affine lower bound backward.
Use lower operator relaxations for positive coefficients and upper relaxations for negative coefficients.
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.