Research map / Adversarial robustness and security / Certified and empirical robustness
Certified Robustness Under Bounded Levenshtein Distance
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 LipsLev, the first Lipschitz-constant-based certifier for convolutional text classifiers under Levenshtein distance, using ERP-distance layer bounds and 1-Lipschitz training to certify in one forward pass.
Problem
Certifying the robustness of text classifiers against Levenshtein distance perturbations (insertions, deletions, substitutions) deterministically and efficiently, which existing IBP and randomized smoothing methods cannot do at scale.
Approach
Bound the global Lipschitz constant of a character-level convolutional classifier with respect to the Levenshtein distance by composing per-layer Lipschitz bounds measured in the ERP distance, then enforce 1-Lipschitzness during training so the certified radius follows from a single forward pass.
Key results
- LipsLev reaches 38.80% verified accuracy at Levenshtein distance 1 and 13.93% at distance 2 on AG-News (p=2).
- LipsLev is roughly 4 to 7 orders of magnitude faster than brute-force and IBP verification (e.g., 0.0097s vs 29.12s on AG-News at k=1).
- IBP cannot verify beyond k=1 and brute force/IBP are out of time for k=2 on the tested datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LipsLev instead of IBP | Character-level convolutional classifier · AG-News, k=1, p=2 | verified accuracy: 29.10 -> 38.80 | Helped |
| Use LipsLev instead of IBP | Character-level convolutional classifier · Fake-News, k=1, p=2 | verified accuracy: 87.33 -> 87.33 | No clear effect |
| Verify with LipsLev at distance k=2 | Character-level convolutional classifier · AG-News, SST-2, Fake-News, and IMDB | verified accuracy: 13.93%; 1.83%; 75.33%; 6.80% | Mixed |
| Increase the number of convolutional layers (ablation) | 1-Lipschitz character-level convolutional classifier · AG-News and SST-2, k=1 | clean and verified accuracy | Hurt |
| Use p=2 rather than p=1 or p=∞ for deeper models (ablation) | 1-Lipschitz character-level convolutional classifier · AG-News and SST-2, k=1 | clean and verified accuracy | Helped |
| Regularize G during training with λ values from 0 to 0.1 (ablation) | Character-level convolutional classifier · SST-2 validation | verified accuracy: 0.0 -> 55.7 | Mixed |
| Enforce 1-Lipschitzness instead of regularizing G (ablation) | Character-level convolutional classifier · SST-2 validation, p=∞ | verified accuracy: 0.0 -> 7.3 | Helped |
| Use randomization in RS-Del instead of deterministic LipsLev | Character-level convolutional classifier · SST-2, all p values | verified accuracy: 14.68 -> 21.98; 18.69 -> 21.10; 14.57 -> 22.40 | Helped |
| Use randomization in RS-Del instead of deterministic LipsLev | Character-level convolutional classifier · IMDB, p=2 | verified accuracy: 8.67 -> 33.67 | Helped |
Surprising findings
- Regularizing the Lipschitz constant instead of enforcing 1-Lipschitzness yields either near-constant classifiers or near-zero verified accuracy.
- Deeper convolutional models (more layers) degrade both clean and verified accuracy for all p values.
Limitations
- Only single- and few-layer convolutional classifiers are covered; transformers and tokenizers are not supported.
- Enforcing 1-Lipschitzness reduces clean accuracy relative to standard training.
- Deeper models lose performance, linked to gradient attenuation.
Experimental setup
Datasets: AG-News SST-2 IMDB Fake-News
Benchmarks: AG-News SST-2 IMDB Fake-News
Metrics: clean accuracy verified accuracy adversarial accuracy runtime
Baselines: BruteF IBP Charmer RS-Del
Builds on: Interval Bound Propagation ERP distance Charmer randomized smoothing
Closest papers by meaning
- Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective (NeurIPS 2022 · similarity 0.91)
- Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization (NeurIPS 2023 · similarity 0.90)
- ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks (NeurIPS 2024 · similarity 0.89)
- A Recipe for Improved Certifiable Robustness (ICLR 2024 · similarity 0.89)
- The Lipschitz-Variance-Margin Tradeoff for Enhanced Randomized Smoothing (ICLR 2024 · similarity 0.87)
- Some Fundamental Aspects about Lipschitz Continuity of Neural Networks (ICLR 2024 · similarity 0.86)
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.