Research map / Adversarial robustness and security / Certified and empirical robustness
GaLileo: General Linear Relaxation Framework for Tightening Robustness Certification of Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GaLileo, an n-dimensional linear relaxation for softmax that exploits input dependencies to tighten robustness certification of Transformers, achieving up to 3.24x larger certified radii than CROWN-BaF at similar runtime.
Problem
Linear relaxation-based robustness certification of Transformers is imprecise because prior methods relax softmax via decomposition into unary functions, ignoring dependencies among softmax inputs; naive n-dimensional relaxations suffer the curse of dimensionality.
Approach
Decouples the nonlinearity of a generalized monotonic n-dimensional function (softmax) per input dimension so that linear bounds are computed independently per dimension (2n cases instead of 3n), enabling one-stage n-d relaxation of softmax that uses input dependencies within a CROWN-like framework.
Key results
- GaLileo achieves up to 3.24x larger certified radii than CROWN-BaF on SST and Yelp Transformers while running times stay similar (about 5-75 s per word).
- GaLileo's Zonotope variant gives up to 3.11x larger l-infinity certified radius than DeepT for 12-layer Yelp models but is worse in some settings (e.g., 0.82x for 6-layer l-inf).
- First certification of Transformers against multi-word (>=3 words) lp perturbations, with certified radii decreasing as more words are perturbed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GaLileo's n-dimensional softmax relaxation instead of CROWN-BaF's decomposed relaxation | Transformer robustness certification · SST and Yelp | certified radius: 1.686 -> 1.749; 0.573 -> 0.755 | Helped |
| Use GaLileo's n-dimensional softmax relaxation instead of CROWN-BaF's decomposed relaxation | Transformer robustness certification · SST and Yelp | running time: 5.8 -> 5.8; 5.5 -> 5.4 | No clear effect |
| Increase the number of simultaneously perturbed words from 2 to 5 | GaLileo · SST, ℓ1 | certified radius: 0.796 -> 0.186 | Hurt |
| Increase the number of simultaneously perturbed words from 2 to 5 | GaLileo · Yelp, ℓ1 | certified radius: 0.294 -> 0.061 | Hurt |
| Combine GaLileo with Zonotopes rather than using DeepT | Transformer robustness certification · Yelp, depth 3, ℓ1 | certified radius: 0.795 -> 0.863 | Helped |
| Combine GaLileo with Zonotopes rather than using DeepT | Transformer robustness certification · Yelp, depth 6, ℓ2 | certified radius: 0.088 -> 0.078 | Hurt |
| Combine GaLileo with Zonotopes rather than using DeepT | Transformer robustness certification · Yelp, depth 12, ℓ∞ | certified radius: 2.8e-3 -> 8.7e-3 | Helped |
Surprising findings
- Zonotope-based GaLileo variant does not uniformly beat DeepT; in some 6-layer settings it yields smaller certified radii.
- Straightforward extension of the n-d relaxation to Zonotope methods does not guarantee tighter bounds.
Limitations
- Zonotope-based extension does not consistently yield tighter bounds than DeepT.
- Evaluation uses small models trained on SST/Yelp and small MNIST ViTs, with certification on only 10 sentences per setting.
- Comparison limited mainly to CROWN-BaF and DeepT.
Experimental setup
Datasets: SST Yelp MNIST
Benchmarks: SST Yelp MNIST
Metrics: average certified radius running time ratio of certified radius
Baselines: CROWN-BaF DeepT
Builds on: CROWN CROWN-BaF Zonotope relaxation Cert-RNN relaxation
Closest papers by meaning
- Transformers Learn Low Sensitivity Functions: Investigations and Implications (ICLR 2025 · similarity 0.87)
- Provably Cost-Sensitive Adversarial Defense via Randomized Smoothing (ICML 2025 · similarity 0.86)
- Vision Transformers Beat WideResNets on Small Scale Datasets Adversarial Robustness (AAAI 2025 · similarity 0.86)
- Expressive Losses for Verified Robustness via Convex Combinations (ICLR 2024 · similarity 0.86)
- Probably Approximately Global Robustness Certification (ICML 2025 · similarity 0.85)
- Efficient Robustness Evaluation via Constraint Relaxation (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.