# AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness

arXiv: https://arxiv.org/abs/2511.09316 · HTML: https://mlsanity.com/paper/2511.09316/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 47 references that are in the map.
- First posted on arXiv 12 Nov 2025.

## Builds on (most cited first, 30 of 30)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment](https://mlsanity.com/paper/1907.11932/) (2019)
- [BERT-ATTACK: Adversarial Attack Against BERT Using BERT](https://mlsanity.com/paper/2004.09984/) (2020)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Black-box Generation of Adversarial Text Sequences to Evade Deep Learning Classifiers](https://mlsanity.com/paper/1801.04354/) (2018)
- [BAE: BERT-based Adversarial Examples for Text Classification](https://mlsanity.com/paper/2004.01970/) (2020)
- [Synthetic and Natural Noise Both Break Neural Machine Translation](https://mlsanity.com/paper/1711.02173/) (2017)
- [FreeLB: Enhanced Adversarial Training for Natural Language Understanding](https://mlsanity.com/paper/1909.11764/) (2019)
- [Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/1909.00986/) (2019)
- [Contextualized Perturbation for Textual Adversarial Attack](https://mlsanity.com/paper/2009.07502/) (2020)
- [Why Should Adversarial Perturbations be Imperceptible? Rethink the Research Paradigm in Adversarial NLP](https://mlsanity.com/paper/2210.10683/) (2022)
- [Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation](https://mlsanity.com/paper/1909.01492/) (2019)
- [SAFER: A Structure-free Approach for Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/2005.14424/) (2020)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Certified Robustness to Text Adversarial Attacks by Randomized [MASK]](https://mlsanity.com/paper/2105.03743/) (2021)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing](https://mlsanity.com/paper/1912.09899/) (2019)
- [PointGuard: Provably Robust 3D Point Cloud Classification](https://mlsanity.com/paper/2103.03046/) (2021)
- [Data-Dependent Randomized Smoothing](https://mlsanity.com/paper/2012.04351/) (2020)
- [Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attacks](https://mlsanity.com/paper/2307.16630/) (2023)
- [Intriguing Properties of Input-dependent Randomized Smoothing](https://mlsanity.com/paper/2110.05365/) (2021)
- [Achieving Model Robustness through Discrete Adversarial Training](https://mlsanity.com/paper/2104.05062/) (2021)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)
- [RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion](https://mlsanity.com/paper/2302.01757/) (2023)
- [Advancing the Robustness of Large Language Models through Self-Denoised Smoothing](https://mlsanity.com/paper/2404.12274/) (2024)
- [Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences](https://mlsanity.com/paper/2406.10427/) (2024)
- [Provable Adversarial Robustness for Group Equivariant Tasks: Graphs, Point Clouds, Molecules, and More](https://mlsanity.com/paper/2312.02708/) (2023)
- [CERT-ED: Certifiably Robust Text Classification for Edit Distance](https://mlsanity.com/paper/2408.00728/) (2024)

## Abstract (arXiv)

We consider the problem of certified robustness for sequence classification against edit distance perturbations. Naturally occurring inputs of varying lengths (e.g., sentences in natural language processing tasks) present a challenge to current methods that employ fixed-rate deletion mechanisms and lead to suboptimal performance. To this end, we introduce AdaptDel methods with adaptable deletion rates that dynamically adjust based on input properties. We extend the theoretical framework of randomized smoothing to variable-rate deletion, ensuring sound certification with respect to edit distance. We achieve strong empirical results in natural language tasks, observing up to 30 orders of magnitude improvement to median cardinality of the certified region, over state-of-the-art certifications.