Certified Robustness Under Bounded Levenshtein Distance

Elias Abad Rocamora, Grigorios G. Chrysos, Volkan Cevher : LIONS - École Polytechnique Fédérale de Lausanne, Switzerland : Department of Electrical and Computer Engineering, University of Wisconsin-Madison, USA {elias.abadrocamora, volkan.cevher}@epfl.ch , [email protected] · 2025

Read Certified Robustness Under Bounded Levenshtein Distance by Elias Abad Rocamora, Grigorios G. Chrysos, Volkan Cevher : LIONS - École Polytechnique Fédérale de Lausanne, Switzerland : Department of Electrical and Computer Engineering, University of Wisconsin-Madison, USA {elias.abadrocamora, volkan.cevher}@epfl.ch , [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13676.txt.

Introduction

Elias Abad Rocamora, Grigorios Chrysos, and Volkan Cevher work on proof of safety for text classifiers in a 2025 paper. Small edits to a text, such as swapping or dropping letters, can flip a model's verdict if chosen with malice. Proof methods exist, but their cost explodes when edits are counted by a standard distance measure.

Their method, LipsLev, first estimates how sharply the model can react to such edits. That estimate guides training of models whose reactions are capped by design. Safety proof then takes a single pass through the model. On a news dataset the method certified solid accuracy at one and two edits, while running far faster than past approaches. The authors see a path to practical proof for text systems.

Catalog record

CREATORElias Abad Rocamora, Grigorios G. Chrysos, Volkan Cevher : LIONS - École Polytechnique Fédérale de Lausanne, Switzerland : Department of Electrical and Computer Engineering, University of Wisconsin-Madison, USA {elias.abadrocamora, volkan.cevher}@epfl.ch , [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13676

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Certified Robustness Under Bounded Levenshtein Distance Elias Abad Rocamora, Grigorios G. Chrysos, Volkan Cevher : LIONS - École Polytechnique Fédérale de Lausanne, Switzerland : Department of Electrical and Computer Engineering, University of Wisconsin-Madison, USA {elias.abadrocamora, volkan.cevher}@epfl.ch , [email protected] Abstract Text classifiers suffer from small perturbations, that if chosen adversarially, can dramatically change the output of the model. Verification methods can provide robustness certificates against such adversarial perturbations, by computing a sound lower bound on the robust accuracy. Nevertheless, existing verification methods incur in prohibitive costs and cannot practically handle Levenshtein distance constraints. We propose the first method for computing the Lipschitz constant of convolutional classifiers with respect to the Levenshtein distance. We use these Lipschitz constant estimates for training 1-Lipschitz classifiers. This enables computing the certified radius of a classifier in a single forward pass. Our method, LipsLev , is able to obtain 38.80 % 38.80\% and 13.93 % 13.93\% verified accuracy at distance 1 1 and 2 2 respectively in the AG-News dataset, while being 4 4 orders of magnitude faster than existing approaches. We believe our work can open the door to more efficient verification in the text domain. 1 Introduction Despite the impressive performance of Natural Language Processing (NLP) models ( Sutskever et al., 2014 ; Zhang et al., 2015 ; Devlin et al., 2019 ) , simple corruptions like typos or synonym substitutions are able to dramatically change the prediction of the model ( Belinkov and Bisk, 2018 ; Alzantot et al., 2018 ) . With newer attacks in NLP becoming stronger ( Hou et al., 2023 ) , verification methods become relevant for providing future-proof robustness certificates ( Liu et al., 2021 ) . Constraints on the Levenshtein distance ( Levenshtein et al., 1966 ) provide a good description of the perturbations a model should be robust to ( Morris et al., 2020 ) and strong attacks incorporate such constraints ( Gao et al., 2018 ; Ebrahimi et al., 2018 ; Liu et al., 2022 ; Abad Rocamora et al., 2024 ) . Despite the success of verification methods in the text domain, existing methods can only certify probabilistically via randomized smoothing ( Cohen et al., 2019 ; Ye et al., 2020 ; Huang et al., 2023 ) , or can only handle specifications such as replacements of characters/words, stop-word removal or word duplication ( Huang et al., 2019 ; Jia et al., 2019 ; Shi et al., 2020 ; Zhang et al., 2021 ) . On the performance side, most successful certification methods rely on Interval Bound Propagation (IBP) ( Moore et al., 2009 ) , which in the text domain requires multiple forward passes through the first layers of the model ( Huang et al., 2019 ) , unlike in the image domain where a single forward pass is enough for verification ( Wang et al., 2018 ) . Moreover, IBP has been shown to provide a suboptimal verified accuracy in the image domain ( Wang et al., 2021 ) . In the image domain, a popular approach to get fast robustness certificates is computing upper bounds on the Lipschitz constant of classifiers, and using this information to directly verify with a single forward pass ( Hein and Andriushchenko, 2017 ; Tsuzuku et al., 2018 ; Latorre et al., 2020 ; Xu et al., 2022 ) . These methods cannot be trivially applied in NLP because they assume the input to be in an \ell_{p} space such \mathbb{R}^{d} , which is not the case of text input, where the input length can vary and inputs are discrete (characters). Therefore, we need to rethink Lipschitz verification for NLP. In this work, we introduce the first method able to provide deterministic Levenshtein distance certificates for convolutional classifiers. This is achieved by computing the Lipschitz constant of intermediate layers with respect to the ERP distance ( Chen and Ng, 2004 ) . Our Lipschitz constant estimates allow enforcing 1 -Lipschitzness during training in order to achieve a larger verified accuracy. Our experiments in the AG-News, SST-2, Fake-News and IMDB datasets show non-trivial certificates at distances 1 and 2 , taking 4 to 7 orders of magnitudes less time to verify. Furthermore, our method is the only one able to verify under Levenshtein distance larger than 1 . We set the foundations for Lipschitz verification in NLP and we believe our method can be extended to more complex models. Notation: We use uppercase bold letters for matrices \bm{X}\in\mathbb{R}^{m\times n} , lowercase bold letters for vectors \bm{x}\in\mathbb{R}^{m} and lowercase letters for numbers x\in\mathbb{R} . Accordingly, the i^{\text{th}} row and the element in the i,j position of a matrix \bm{X} are given by \bm{x}_{i} and x_{ij} respectively. We use the shorthand [n]=\{0,1,\cdots,n-1\} for any natural number n . Given two matrices \bm{A}\in\mathbb{R}^{m\times d} and \bm{B}\in\mathbb{R}^{n\times d} \bm{A}\oplus\bm{B}=\left[\begin{matrix}\bm{A}\\ \bm{B}\end{matrix}\right]\in\mathbb{R}^{(m+n)\times d} . Concatenating with the empty sequence \emptyset results in the identity \bm{A}\oplus\emptyset=\bm{A} . We denote as \bm{A}_{2:}\in\mathbb{R}^{(m-1)\times d} the matrix obtained by removing the first row. We denote the zero vector as \bm{0} with dimensions appropriate to context. We use the operator |\cdot| for the size of sets, e.g., |\mathcal{S}(\Gamma)| and the length of sequences, e.g., for \bm{X}\in\mathbb{R}^{m\times n} , we have |\bm{X}|=m . Table 1: State of the art in Levenstein distance verification and our contributions: LipsLev is the first to verify deterministically against Levenshtein distance constraints in a single forward pass. Method Insertions/deletions Deterministic Single forward pass Huang et al. (2019) ✗ ✓ ✗ Huang et al. (2023) ✓ ✗ ✗ LipsLev (Ours) ✓ ✓ ✓ 2 Related Work Lipschitz verification: Hein and Andriushchenko (2017) are the first to study the computation of the Lipschitz constant in order to provide formal guarantees of the robustness of support vector machines and two-layer nueral networks. Tsuzuku et al. (2018) compute Lipschitz constant upper bounds for deeper networks and regularize such upper bounds to improve certificates. Since then, tighter upper bounds for the Lipschitz constant have been proposed ( Huang et al., 2021 ; Fazlyab et al., 2019 ; Latorre et al., 2020 ; Shi et al., 2022 ) . A variety of works propose constraining the Lipschitz constant to be 1 during training in order to have automatic robustness certificates ( Cisse et al., 2017 ; Qian and Wegman, 2019 ; Gouk et al., 2021 ; Xu et al., 2022 ) . All previous works center in the standard \ell_{p} norms and cannot be applied to the NLP domain. Our work provides the first 1 -Lipschitz training method for the Levenshtein distance. Verfication in NLP: Jia et al. (2019) propose using Interval Bound Propagation via an over-approximation of the embeddings of the set of synonyms of each word. Concurrently, Huang et al. (2019) incorporate this technique for verifying against replacements of nearby characters in the E nglish keyboard. Bonaert et al. (2021) ; Shi et al. (2020) propose zonotope abstractions and IBP for verifying against synonym substitutions in transformer models. Zhang et al. (2021) propose a verification procedure that can handle a small number of input perturbations for LSTM classifiers. Deviating from these approaches, Ye et al. (2020) propose using randomized smoothing techniques Cohen et al. (2019) in order to verify probabilistically against character substitutions. Huang et al. (2023) used

Read the complete text