# CERT-ED: Certifiably Robust Text Classification for Edit Distance

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 61 references that are in the map.
- First posted on arXiv 1 Aug 2024.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [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)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [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)
- [Generating Natural Language Adversarial Examples](https://mlsanity.com/paper/1804.07998/) (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)
- [Adversarial Example Generation with Syntactically Controlled Paraphrase Networks](https://mlsanity.com/paper/1804.06059/) (2018)
- [Adversarial Training Methods for Semi-Supervised Text Classification](https://mlsanity.com/paper/1605.07725/) (2016)
- [FreeLB: Enhanced Adversarial Training for Natural Language Understanding](https://mlsanity.com/paper/1909.11764/) (2019)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Gradient-based Adversarial Attacks against Text Transformers](https://mlsanity.com/paper/2104.13733/) (2021)
- [Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/1909.00986/) (2019)
- [Mind the Style of Text! Adversarial and Backdoor Attacks Based on Text Style Transfer](https://mlsanity.com/paper/2110.07139/) (2021)
- [Contextualized Perturbation for Textual Adversarial Attack](https://mlsanity.com/paper/2009.07502/) (2020)
- [Is LLM-as-a-Judge Robust? Investigating Universal Adversarial Attacks on Zero-shot LLM Assessment](https://mlsanity.com/paper/2402.14016/) (2024)
- [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)
- [Perturbation Sensitivity Analysis to Detect Unintended Model Biases](https://mlsanity.com/paper/1910.04210/) (2019)
- [SAFER: A Structure-free Approach for Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/2005.14424/) (2020)
- [Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation](https://mlsanity.com/paper/1911.09272/) (2019)
- [Certified Robustness to Text Adversarial Attacks by Randomized [MASK]](https://mlsanity.com/paper/2105.03743/) (2021)
- [Training on Synthetic Noise Improves Robustness to Natural Noise in Machine Translation](https://mlsanity.com/paper/1902.01509/) (2019)
- [Training verified learners with learned verifiers](https://mlsanity.com/paper/1805.10265/) (2018)
- [CAT-Gen: Improving Robustness in NLP Models via Controlled Adversarial Text Generation](https://mlsanity.com/paper/2010.02338/) (2020)

## Built on by (most cited first, 2 of 2)

- [AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness](https://mlsanity.com/paper/2511.09316/) (2025)
- [What Was That Again? Certified Robustness for Automatic Speech Recognition](https://mlsanity.com/paper/2606.27698/) (2026)

## Abstract (arXiv)

With the growing integration of AI in daily life, ensuring the robustness of systems to inference-time attacks is crucial. Among the approaches for certifying robustness to such adversarial examples, randomized smoothing has emerged as highly promising due to its nature as a wrapper around arbitrary black-box models. Previous work on randomized smoothing in natural language processing has primarily focused on specific subsets of edit distance operations, such as synonym substitution or word insertion, without exploring the certification of all edit operations. In this paper, we adapt Randomized Deletion (Huang et al., 2023) and propose, CERTified Edit Distance defense (CERT-ED) for natural language classification. Through comprehensive experiments, we demonstrate that CERT-ED outperforms the existing Hamming distance method RanMASK (Zeng et al., 2023) in 4 out of 5 datasets in terms of both accuracy and the cardinality of the certificate. By covering various threat models, including 5 direct and 5 transfer attacks, our method improves empirical robustness in 38 out of 50 settings.