Research map / Architectures and efficiency / Attention and transformers
Fine-grained Local Sensitivity Analysis of Standard Dot-Product Self-Attention
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.
Derives fine-grained analytical local sensitivity bounds for unmodified dot-product self-attention (LoFAST) and uses them for fast, non-vacuous deterministic certified l2 robustness of ViTs on CIFAR-10 and SVHN.
Problem
Dot-product self-attention is not globally Lipschitz, so its sensitivity to input perturbations is hard to bound, and existing certification tools (CROWN, randomized smoothing) do not scale to ViTs on CIFAR-scale data.
Approach
Instead of modifying attention to be Lipschitz, bound the local deviation ||F(X')-F(X)|| around a fixed input X by splitting into two terms: an exact key sensitivity metric (a largest-singular-value problem via Kronecker structure) for the value/output term, and tractable upper bounds for the softmax-difference term; combine with Lipschitz-constrained layers (SLL, LayerProject) to certify ViTs.
Key results
- LoFAST gives non-vacuous deterministic certified l2 accuracy for ViTs on CIFAR-10 and SVHN, e.g., 29.1% at eps=0.02 for 3-layer ViT on CIFAR-10 (Table 1).
- On 3-layer ViT, LoFAST runs in 0.055 sec/sample versus CROWN's much larger cost, and CROWN+LoFAST gives 1.71 vs 4.33 sec/sample at eps=0.02 on CIFAR-10 (Table 2).
- At eps=0.05 on CIFAR-10, CROWN+LoFAST certified accuracy is 20.03% versus 14.35% for CROWN alone.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply LoFAST before CROWN | CROWN on CIFAR-10 3-layer ViT · CIFAR-10, ε = 0.05 | certified acc. (%): 14.35 -> 20.03 | Helped |
| Apply LoFAST before CROWN | CROWN on SVHN 3-layer ViT · SVHN, ε = 0.05 | certified acc. (%): 27.45 -> 29.51 | Helped |
| Apply LoFAST before CROWN | CROWN on CIFAR-10 3-layer ViT · CIFAR-10 | sec/sample: 4.33 -> 1.71 | Helped |
| Apply LoFAST before CROWN | CROWN on SVHN 3-layer ViT · SVHN | sec/sample: 5.68 -> 1.44 | Helped |
| Use LoFAST instead of α, β-CROWN | ViT 3-Layer · CIFAR-10 test subset (1000 samples), ε = 0.02 | certified robust accuracy (%): 41.2 -> 29.1 | Hurt |
| Use LoFAST instead of α, β-CROWN | ViT 3-Layer · CIFAR-10 test subset (1000 samples), ε = 0.05 | certified robust accuracy (%): 14.1 -> 16.0 | Helped |
Surprising findings
- The naive sensitivity bound is far looser; the residual-structure key sensitivity metric is essential for non-vacuous certification.
- Constraining attention weight norms too strictly (<=0.25) hurts clean accuracy enough to offset the sensitivity reduction.
Limitations
- Two-term bound for the softmax-difference term relies on dropping higher-order terms, so it is an approximation for large epsilon.
- Certified accuracy becomes low at larger perturbation radii and deeper ViTs; the bound compounds with depth.
- Requires Lipschitz-constrained layers (SLL, LayerProject) that alter the standard ViT architecture, so the certified model differs from the vanilla network.
Experimental setup
Datasets: CIFAR-10 SVHN
Benchmarks: CIFAR-10 SVHN
Metrics: certified robust accuracy upper bound tightness vs PGD lower bound sec/sample run-time
Baselines: alpha,beta-CROWN naive sensitivity bound (Eq. 12) PGD lower bound CROWN+LoFAST
Builds on: Kim et al. 2021 Lipschitz analysis of dot-product attention Tsuzuku et al. 2018 margin-based certification SDP-based Lipschitz layers (SLL) CROWN / alpha-beta-CROWN
Closest papers by meaning
- How Smooth Is Attention? (ICML 2024 · similarity 0.85)
- Transformers Learn Low Sensitivity Functions: Investigations and Implications (ICLR 2025 · similarity 0.84)
- Unveiling the Hidden Structure of Self-Attention via Kernel Principal Component Analysis (NeurIPS 2024 · similarity 0.84)
- Degrees of Freedom for Linear Attention: Distilling Softmax Attention with Optimal Feature Efficiency (NeurIPS 2025 · similarity 0.84)
- On the Role of Attention Masks and LayerNorm in Transformers (NeurIPS 2024 · similarity 0.83)
- Theory, Analysis, and Best Practices for Sigmoid Self-Attention (ICLR 2025 · similarity 0.83)
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.