Certified Robustness Under Bounded Levenshtein Distance
Authors: Elias Abad Rocamora
Grigorios Chrysos
Volkan Cevher
Venue: ICLR 2025 Poster (2025)
Keywords: Robustness verification
Text classifiers
Lipschitz constant
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We propose the first method for Lipschitz constant based verification with Levenshtein distance constraints for convolutional text classifiers.

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$% and $13.93$% verified accuracy at distance $1$ and $2$ respectively in the AG-News dataset, while being $4$ orders of magnitude faster than existing approaches. We believe our work can open the door to more efficient verification in the text domain.

Published conference paper at ICLR 2025
CERTIFIED ROBUSTNESS UNDER BOUNDED LEVENSHTEIN DISTANCE
Elias Abad Rocamora Grigorios G. Chrysos Volkan Cevher
EPFL: LIONS École Polytechnique Fédérale de Lausanne, Switzerland
Department of Electrical and Computer Engineering, University of Wisconsin- Wisconsin-Madison, USA {el Tas abadrocamora vol holkan.cemt cevher @epf1 ch, chrysos@wi wesoswwisc.ee
ABSTRACT
Text classifiers suffer from small perturbations, that if chosen adversarially, can dramatically change the output of the model. Verification methods can provide ro- bustness certificates against such adversarial perturbations, by computing a sound lower bound the robust accuracy. Nevertheless, existing verification meth- ods 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-L.ischitz classifiers. This enables com- puting the certified radius of classifier in a single forward pass. Our method, LipsLev, able to obtain 38.80% and 13.93% verified accuracy distance 1 and 2 respectively in the AG-News dataset, while being 4 orders of magnitude faster than existing approaches. We believe our work can open the door to more efficient verification in the text domain.
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
ct 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 model should be robust to (Morris 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 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 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 al.. 2019). unlike in the image domain where a single forward pass is enough for verification (Wang et al." (018)). Moreover, IBP has been shown to provide suboptimal verified accuracy the image domain (Wang et al., 2021).
In the image domain, 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 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 4p space such Rdd, 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, introduce the first method able provide deterministic Levenshtein distance certi- ficates for convolutional classifiers. This is achieved by computing the Lipschitz constant interme- diate layers with respect the ERP distance (Chen and Ng 2004). Our Lipschitz constant estimates

---

Published conference paper at ICLR 2025
Table State of the art in Levenstein distance verification and our contributions: LipsLev is the first to verify deterministically against Levenshtein distance constraints in single forward pass.
Method
Insertions/delctions
Deterministic
Single forward pass
Huang ct al.
2019
V
X
Huang ct al.
2023
Liv (Ours)
allow enforeing I-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 the only one able to verify under Levenshtein distance larger than 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 X RR lowercase bold letters for vectors R and lowercase letters for numbers E R. Accordingly, the 7th row and the element in the i,j position of a matrix X are given by æ, and Zij respectively. We use the shorthand n - 1} for any natural number π. Given two matrices A E Rm and B
[n] = 10,1,-.
A
Raxd A B
IR (m)d) Concatenating with the empty sequence 0 results in the identity
B
A = A. We denote as A2: E (mm-1)xe the matrix obtained by removing the first row. We denote the zero vector O with dimensions appropriate to context. We use the operator for the size of sets, egg, (S(T) and the length of sequences, e.g., for X E mRxx,, we have X = m.
2 RELATED WORK
Hein and Andriushchenko (2017) the Lipschitz constant in order to provide formal guarantees of the robustness of support vector machines and two-layer nueral networks. [Tsuzuuu 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 al.) 202T] Fazlyab et al. 2019 Latorre et al. 2020 Shi et al., 2022). A variety of works propose constraining the Lipschitz constant be during training in order to have automatic robustness certificates (Cisse et al. 2017 Qian and Wegman 2019]
Lipschitz verification:
the first study the computation of
2019 Gouk et al. 2021] Xu et al.) (022). All previous works center in the standard E, 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 English keyboard. BBnaert et al. (202T); (Shi al. (2000) propose zonotope abstractions and IBP for verifying against synonym substitutions in transformer models. IZhang et al.) (202T) propose a verification procedure that can handle small number of input perturbations for LSTM classifiers. Deviating from these approaches, Ye et al. (2020) propose using randomized smoothing techniques Cohen et (2019) in order to verify probabilistically against character substitutions. Huang al. (2023) used similar techniques in order to probabilistically verify under Levenshtein distance spe- eifccations. Zhao et al. (2022) propose framework verify under word substitutions via Causal Interventions. Sun and Ruan (2023) derive probable upper and lower bounds of the certified radius under word substitutions. /Zhang et (2024) employ randomized smoothing verify against word (synonym) substitutions, insertions, deletions and reorderings. Zeng et al. (2023) propose ran- domized smoothing technique that does not rely on knowing how attackers generate synonyms. In Table I we highlight the differences with existing works in NLP verification.
PRELIMINARIES
Let S(T) = fc102... ... Cm : 4 E I Vm E N 03 be the space of sequences of characters in the alphahet set T. We represent sentences S E S(T) sequences of one-hot vectors, i.e., S
2

---

Published conference paper at ICLR 2025
{0, 1) [] ||s: I, Vi [m]. Given a classification model f S(T) - IR" assigning scores to each of the classes, the predicted class for some S E S(T) is given by arg |e|o J(S); Our goal is to check whether for given pair (S, y) E (S(L)) [o]):
f(S') max f(5") > 0, AS' E S(T) deev (5,5') S k. jy
(1)
where diev is the Levenshtein distance defined as follows:
(Levenshtein et al.
1966). The Levenshtein distance is
S
if S = 0 if [S] = 0 if 81 8/
S
dLev (S2. S2
(s.v(S =
dl S2 St
1 min
d S S*)
otherwise
deev S, Sy))
The Levenshtein distance captures the number of character replacements, insertions or deletions needed in order to transform S into S' and vice-versa. Such constraints are employed in popular NLP attacks in order to enforce the imperceptibility of the attack (Gao et al.) 2018 [Ebrahimi et al.)
2018
Liu et al. 2022 Abad Rocamora et al., 2024) following the findings of Morris et al. (2020).
3.1
INTERVAL BOUND PROPAGATION (IBP)
Existing robustness verification approaches rely on IBP for verifying the robustness of text models (Huang et al. 2019 Jia et al. 2019). IBP relies on the input being constrained in a box. Let x, I, u E
R. every element of assumed be in an interval given by I and u. i.c., 4 S x, I u, Vi E [d] or x E [, u) for short. These constraints arise naturally when studying robustness in the foo norm, as the constraint æ E (xx(0) + 8 ||0||g S { can exactly be represented as a E [xx(0) - (0)) +e]. IBP consists in set of rules to obtain interval constraints of the output of function, given the interval constraints of the input. In the case of an affine mapping f(x)= Wæ + b, we can easily obtain the interval constraints f(x) E (xx), u (x)),, Vo E [L. ul with:
(x W+++ W + b, uy(x) W+ W L
where W and W are the positive and negative parts W. In the case of the ReLU activation function or = max x) ) we have that:
(x)x) = ol),, Uo (x) = (u)
(3)
By applying recursively the simple rules in Eqs. and one can easily verify robustness prop- erties of ReLU fully-connected and convolutional networks (Wang et al. 2018).
Nevertheless, IBP has two main limitations:
a) IBP assumes the input space to be of fixed length, e.g., Rdd
b) IBP can only handle interval constrained inputs, e.g., x E [4, u4..
Limitation a) makes it impossible to verify Levenshtein distance constraints as they include insertion and deletion operations, which change the length of the input sequence. the literature, limitation a) forces existing verification methods to only consider replacements of Sharacters/words (Huang
al. 2019 Jia et al. 2019: Shi et al. 2020 Bonaert et al. 2021 Zhang et al. 2021).
Limitation b) can be circumvented by building an over approximation of the replacement constraints that can be represented with intervals. the case of text, one can directly build an over approxima- tion of the embeddings. Let Z SE E gm where S S(I') is the sequence of one-hot vectors representing each character/word, and E E R[ is the embedding matrix. Let dedit be the edit distance without insertions and deletions, our constraint in the edit distance (Eq. (T) translates in the embedding space to the set:
(S) = (S'E: (S, S k S(T))
where ( overapproximate this set with interval constraints such that 2 [L, UJ, with lij min ze Zij
(S,S') Em ||s || -s/llo for any length m sequences of one-hot vectors S, S'. We can
3

---

Published conference paper at ICLR 2025
and Uij (2) Zij. But, because we can replace any character/word any position, we end up with L = - (Q) ... () 1 and U ex G re ( ... { u. where:
1 min CRis kE(
max CAdr kEllElI
ViE (d.
Therefore, this overapproximation contains the embeddings of any S' E {0, 1 ||
1, Vi E [m., i.e., every sentence of length m, making verification impossible. To circumvent this, existing methods focus the synonym replacement task, further restricting (S) only replace words for word in small set of synonyms (Jia et al. 2019; Shi et al. 2020 Bonaert et al. 2021). Alternatively, Huang et al. (2119) compute the over approximation after the pooling layer of the model, circumventing this problem. Nevertheless, their approach requires (5)) forward passes.
This number of forward passes can be the order of tens of thousands for large m and [T].
Our Lipschitz constant based approach, LipsLev, can handle sequences of any length and requires a single forward pass through the model.
METHOD
In Section 4.1 we cover the verification procedure once the Lipschitz constant classifier known. In Section 4.2 we cover the convolutional architectures employed in Huang et al. (2019) and our Lipschitz constant estimation for them. Lastly, we introduce our training strategy order to achieve non-trivial verified accuracy in Section 4.3
We defer proofs to Appendix B
4.1 LIPSCHITZ CONSTANT BASED VERIFICATION
Motivated by the success and efficiency of Lipschitz constant based certification in vision tasks (Huang et al. 202I; Xu al. 2022). we propose a method of this kind that can handle previously studied models in the character-level classification task (Huang et al. 2019), and provide Leven- shtein distance certificates.
Our goal is to compute the global Lipschitz constant. Let 99.0 (S) = f(S), f(S) be the margin function for classes y and y. we would like have for some S:
19 (S) Fu.i (S.)(S')l S Gy.i (S, VS' E S(T),
for some Gy.9 E R Given Eq. is satisfied, the maximum distance up to which we can verify Eq. (T), is lower bounded by:
gv.0(
max(k: (S.)(S") > VS' E E (S, S
(5)
Gy
9v. Let kt v.u Gy.p
(S) =
we denote (S) == mingzy k (
(S) to be the certified radius.
4.2 LIPSCHITZ CONSTANT ESTIMATION FOR CONVOLUTIONAL CLASSIFIERS
Let S E S(() be a sequence one-hot vectors, our classifier defined as:
m++l-(g-1
f(S) Σ
(()(S)
W, where (() = {o (C (FU-M(S)))
Vj =j= 1,..,..... j ==0
SE
where E E Ruxd the embeddings matrix, CO, Vi 1, ,I are convolutional layers with kernel size q and hidden dimension k. is the ReLU activation function and W e & is the last classification layer. This architecture was previously studied in verification by (Huang et al. 2019 Jia et al. 2019).
Our approach to estimate the global Lipschitz constant of such a classifier is to compute the Lipschitz constant of each layer. Then, since the overall function in Eq. (6) is the sequential composition of all of the layers, we can just multiply the Lipschitz constants to obtain the global one. However, in order to be able do this, need some metric with respect which we can compute the Lipschitz
4

---

Published conference paper at ICLR 2025
constant. The Levenshtein distance cannot be applied, as can only measure distances between one-hot vectors and the outputs of intermediate layers are sequences of real vectors. For this task, we select the ERP distance (Chen and Ng 2004):
Definition 4.1 (ERP distance (Chen and Ng. 2004)). Let A E R and B Rexd be two sequences of m and n real vectors respectively and 2 1. The ERP distance is defined as:
i-1 aalllp
if n 0 (B 0) if m 0 (A 0)
Σ 1i=1 lbillp
P A, B)
||
ERP A2. B);
=
min
b1 p + R A, B2.),
otherwise
||a
billp + d (Az., B2.)
The ERP distance is a natural extension of the Levenshtein distance for sequences of real valued vectors. In fact, the case we compare sequences of one-hot vectors and we set = oc, we recover the Levenshtein distance, see Lemma S4
In the following we define a useful representation convolutional layers.
Definition 4.2 (1D Convolutional layer with zero padding). Let A E Rmxd be sequence of d- dimensional vectors. Let & be the number of filters and the kernel size, convolutional layer with parameters K. E Rexkxd can be represented as;
C: mxd + R (m)+
m+2-(g-1) Σ Kijāj, where Kij
[K]-i+1 00
if f vi pm 1],
(A)
otherwise
and Á (g-1)x @ A + 0 (x) (1x is the zero-padded input. We denote the parameter tensor corresponding to every layer C K(0)
In Theorem 4.3 we present our Lipschitz constant upper bound. In Corollary 4.4 the Lipschitz
constant upper bound employed to compute the certified radius sentence P. The Lipschitz constant upper bound can be further refined considering the local Lipschitz constant of the embed- ding layer around sentence P, see Remark 4.5
Theorem 4.3 (Lipschitz constant margins of convolutional models), Let f be defined as in Eq. (6). Let (S) = f(S), f(S), be the margin function for classes y and ÿ. Let 2 1. Let P and Q be sequences of one-hot vectors, we have that for any y and ÿ:
( M (xC(O)
199. 9y.0 (Q) S ||w0 wyll.
MMEE) dia (P,Q),
where (K) E Kilpp M(E)- max max
||eilpp
max (]E[[r]
|le; ejl1,)
} and
xe[[r]]
Proof. See Appendix B
Corollary 4.4 (Certified radius of convolutional models). Let f be defined as in Eq. 6 and the Lipschitz constant of 9v.6 be:
Gy.6 = =wwg-- wyll. ( M (M((XC))) (X)10) M(E..
(M())))((E))
Then, the certified radius of f at the sentence P given by: k5,g(S) mingyy
G..v
Remark 4.5 (Local Lipschitz constant of the embedding layer). Let the embeddings of a sentence S be given by SE, we have that for any two sentences P and Q:
diRP (PE, QE) < (E, P) di de
where M ME P) = max max T
leallp
max "ke (1
Ip.EE e, e satisfying M M(E,P) & M(E).
In the case 1 and p Do, we have and respectively.
5

---

Published conference paper at ICLR 2025
4.3 TRAINING I-LIPSCHITZ CLASSIFIERS
Models trained with the standard Cross Entropy loss and Stochastic Gradient Descent (SGD) recipe are not amenable to verification methods, resulting in small certified radiuses. This has motivated the use of specialized training methods in the image domain (Mirman al., 2018 Gowal et al. 2018 Mueller et al. 2023 Palma et al. 2024). Verification methods in the text domain also require tailored training methods achieve non-zero certified radiuses (Huang al., 2019
Dia al. 2019).
Motivated by methods enforcing classifiers to be I-Lipschitz in the image domain (Xu et al.
2022
we enforce this constraint during training in order improve certification.
In order to achieve a I-Lipschitz classifier, we enforce 1 I-Lipschitzness of every layer by dividing the output of each layer by its Lipschitz constant. This results in our modified classifier being:
( (q-1)
((U0 (F)-)(())) M(KO) SE
f(S)
Σ 1=1
(S)
W
where (()
Vj
1,
(W)
j = 0
M((E)
where M (W) y.efl |,,, wyll, Note that the last layer is made I-Lipschitz with respect
to the worst pair of class labels. Incorporating this information and Remark 4.5 we end up with the final Lipschitz constant for the classifier:
Corollary 4.6 (Local Lipschitz constant of modified classifiers). Let f be defined as in Eq. 7 Let l be the margin function for classes y and g. Let P and Q be sequences
(S. = f(S), f(S) of one-hor vectors, we have that for any y and g:
11g wyll. M( P)
(Pu - -9.. S
die (P.Q).
M(W) M(E)
where MEE) is defined as in Theorem M(E, P) is in Remark 4.5 and MW) maxy, 11w0y - will,,- Note that this Lipschitz constant is local as it depends on P.
Note that the local Lipschitz constant estimate in Corollary 4.6 is guaranteed be at most as ||wg w,yl_ < (W) and ME P) < (E). Given this estimate, we can proceed similarly to Corollary 4.4 in order to obtain the certified radius of the modified model. Note that in the forward pass of Eq. (7 we need to compute M (E), M (XC5)) and M (W). which increases the complexity observe this can be efficiently done during training as seen in Appendix A.6 Then, the weights of each layer can be divided by its Lipschitz
of forward pass with respect to Eq. 66. Nevertheless,
constant, resulting in the same architecture in Eq. 66) with the guarantees of Corollary 4.6
EXPERIMENTS
In this section, we cover our experimental validation. In Section 5. we cover the experimental setup and training mechanisms shared among all experiments. In Section 5.2 we compare performance of our approach with existing IBP approaches and the naive brute force verification bascline. Lastly, in Section [5.3 we cover the hyperparameter selection of our method. We define our performance metrics and perform additional experiments in Appendix A
5.1 EXPERIMENTAL SETUP
We train and verify our models in the sentence classification datasets AG-News (Gulli 2005 Zhang ct al. (2015), SST-2 (Wang et al. 2019). IMDB (Maas et al., (011]) and Fake-News (Lifferth 2018). We consider all of the characters present in the dataset except for uppercase letters, which we token- ize as lowercase. Each character is tokenized individually and assigned one embedding vector via the matrix E. For all our models and datasets, following Huang et al. (2019), we train models with a single convolutional layer, an embedding size of 150, hidden size of 100 and a kernel size of 5 for the SST-2 dataset and 10 for the rest of datasets. Following the setup used in Andriushchenko and Flammarion 2020) for adversarial training, we use the SGD optimizer with batch size 128 and a 30-epoch cyclic learning rate scheduler with maximum value of 100.0, which select via grid search in a validation dataset, see Appendix(A.5 For every experiment, we report the average results over three random seeds and report the performance over the first 1, 000 samples of the test set. Our

---

Published conference paper at ICLR 2025
standard deviations are reported in Appendix A.3 Due to the extreme time costs of the frute-force and IBP approaches in the Fake-News dataset, we reduce to 50 samples in this dataset. We compute
the adversarial accuracy with Charmer (Abad Rocamora et al.) [2024]. For completeness, we report
the performance of LipsLev over the full 1, 000 samples and & up to 10 in Appendix [A.4 All of
our experiments are conducted in a single machine with an NVIDIA A100 SXM4 40 GB GPU, Our implementation is available in
Table 2: Verified accuracy under bounded diev: We report the Clean accuracy (Acc.), Adversarial Accuracy (Adv. Acc.) with Charmer (Abad Rocamora et al. 2024), Verified accuracy (Ver.) and the average runtime in seconds (Time) for the force approach (BruteF), IBP (Huang et al. 2019) and LipsLev. OOT means the experiment was Out Of Time. X means the method does not support diev > 1. Our method, LipsLev, is the only method able provide non-trivial verified accuracies for any k in a single forward pass.
Dataset
p
Acc.(%)
Adv. (%)
Charmer
Time(s)
(er
Brutef
Time(s)
Ver.%)
Time(s)
Ver(%%
Lips Lev Time(s)
20
65.23
32.97
5.70
5.70
47.87
OOT
27.77
X
16.76
32.33
11.60
0.0015
0.0015
AG-News
69.63
37.77
54.47
5.43
5.43
54.43
15.33
18.93
17.56
34.50
12.53
0.00140
0.00140
2
74.80
62.20
46.47
7.32
7.32
62.07
00T
29.12
29.10
X
31.54
38.80
13:93
0.00970
0.00970
2
63.95
39.68
19.92
1.84
1.84
39.68
OOT
2.27
33.94
2.58
14.68
0.99
0.00084
0.00084
SST-2
69.69
26.11
1.91
1.91
45.22
OOT
2.31
19.00
X
2.99
18.69
1.83
0.0022
0.0022
69.95
30.70
48.81
2.09
2.09
48.78
4.23
16.06
5.22
14.57
0.73
0.0047
0.0047
100.00
76.00
86.67
66.82
66.82
86.67
OOT
972.46
85.33
989.84
68.67
85.33
0.017
0.017
Fake-News
98.00
92.00
67.11
92.00
978.94
91.33
990.32
91.33
0.014
79.33
67.11
OOT
75.33
0.014
2
98.00
78.00
58
73.52
73.52
88.67
0OT
1224.45
87.33
1466.38
87.33
71.33
0.0089
0.0089
74.37
67
14.16
67.43
130.49
61.50
138.20
31.37
0.0017
59.77
14.16
00T
5:90
0.0047
IMDB
69.37
61.17
52.20
14.44
14.44
61.00
OOT
134.23
47.30
135.22
28.73
6.80
0.0027
0.0027
2
60.60
35.10
46.87
16.24
16.24
46.73
00T
261 .99
37.37
308.73
0.87
8.67
0.0019
0.0019
5.2 COMPARISON WITH IBP AND BRUTE FORCE APPROACHES
In this section, compare our verification method against brute-force approach and modifica- tion of the IBP method in (Huang et al. 2019) to handle insertions and deletions of characters.
With the brute-force approach, for every sentence P in the test dataset, we evaluate our model in every sentence in the set (Q : thev P, Q) < k} and check if there is any missclassification. Since the size of this set grows exponentially with k. we only evaluate the brute-force accuracy for k 1.
In the case of IBP, we evaluate the classifier up to the pooling layer in every sentence of {Q (P. ()) < k} and then build the overapproximation. In (Huang et al., 2019) was enough to build this overapproximation for k = and re- re-scale it to capture larger Ks. This is not the case for insertions and deletions, this constrains IBP with Levenshtein distance specifications to work only for A -= 1. Overall, the complexity of IBP is the same as the brute-force approach without providing the exact robust accuracy. Because Huang et al. (2019) only considered perturbations of characters nearby in the English keyboard, the maximum perturbation size at l: was very small, e.g., 206 and 722 sentences for SST-2 and AG-News respectively In our setup, the maximum perturbation sizes are 33, 742 and 85, 686. This makes it impractical to perform IBP verified training. We train 3 models for each dataset and E (1, oc) and verify them with the three methods. We report the average time to verify and the clean, adversarial and verified accuracies at k E (1,2).
"See Table in Huang al. 2019
7

---

Published conference paper at ICLR 2025
Table 3: Regularizing v.s. enforcing Lipschitzness in SST-2: We compare the performance when regularizing the Lipschitz constant (G) during training with À E {0, 0.001, 0.01, 0.1 against enfor- cing I-Lipschitzness through Eq. (7) Regularizing G leads to either models with similar perform-
ance to a constant classifier (55.7% % for SST-2), or more accurate but non-verifialle models than when using the formulation in Eq.
00
= 2
A
(l
Ver.
G
Clean(%)
G
Clean(
Ven(%)
G
89.02c0.5)
g0000
2850.2
86. 26.14
(.0
449.6g(5.0)
(7.2
0.0
129. (:2.0)
0.001
80.8
(.0
65.0g10s)
84.5
(.0
41.1
86.22(04)
0.0g(0.0)
37.7a003:
0.01
60. (0.1)
1.7
144.0.1)
79. (9.7.
0.14:000)
6.9
81. (10.4
0. 0.12(0.0)
8.8
0.1
56.2 2002)
55.7200.0
0.0.00.0)
57-3
53. 23.2
0. (:
57.5
34.1 ap.1o
0.1.0000
Eq.
62.8
7.3
1.00
65.6 65.6g(0.1)
10.7..0.2
1.00
66.62
7.2
1.00
In T we can observe that the p value has a big influence in the clean accuracy of the models and the verification capability of each method. With p = 2, we observe the highest clean accuracy AG- News and SST-2, with average of 74.80% and 69.95% respectively. In the case of Fake-News and IMDB, p = oC provided the best accuracy with 100% and 74.57% respectively. In terms of robust accuracy (BruteF), p = 2 also provides the best performance with 62.07% for AG-News and 48. 48%78% for SST-2, while for Fake-News and IMDB, the best performance was achieved with p and p oo respectively (92% and 74.57%). We observe that IBP obtains the best ratio between clean and verified accuracy when employing p = co, providing the best performance in the IMDB and SST-2 datasets at k = 1. Our method, LipsLev, is able to improve over IBP in AG-News and match IBP in Fake-News at k = 1, being the only method able to verify for k >> 1. At distance = 2. we can observe that the Charmer adversarial accuracy in AG-News, SST-2 and IMDB is significantly larger than the verified accuracy given by Lipslev. Contrarily, for the Fake-News dataset, Li Lev is able to have a gap as close as 75.33% v.s. 79.33% with p p
In terms of runtime, method is from 4 to orders of magnitude faster than brute-force and IBP, which attain similar runtimes. The impossibility of IBP to verify for & > and its larger runtime than brute-force, poses as an impractical tool for Levenstein distance verification. Our method is the only one able to verify for k > 1, with 13.93% verified accuracy for AG-News, 1.83% for SST-2, 75.33% for Fake-News and 6.80% for IMDB at k =
5.3 REGULARIZING THE LIPSCUITZ CONSTANT
we describe how to enforce our convolutional classifier to be 1-Lipschitz. But, is there a better way of improving the final verified accuracy of our models? Because our Lipschitz constant estimate in Theorem 4.3 its differentiable with respect to the parameters of the model, we can regularize this quantity during training in order to achieve a lower Lipschitz constant and hopefully better verified accuracy. In practice we regularize G = M(W) ((C()) M(E) as defined in Theorem 4.3 and Corollary 4.6
In Section 4.3
We train single-layer models with a regularization parameter of E {0, 0.001, 0.01, 0.1). where X = is equivalent to standard training. We initialize the weights of each layer so that their Lipschitz constant is 1. We use a learning rate of 0.01. We measure the final Lipschitz constant of cach model and their clean and verified accuracies in a validation set of 1, 000 samples left out from the training set. As a baseline, we report these metrics for the models trained with the formulation in Eq. (7).
In Table 3 we observe that for all the studied norms, when regularizing the Lipschitz constant G, we cannot easily match the performance when using Eq. (7). Regularized models converge to either coss-to--cnstanl classifiers (55.7% clean accuracy for SST-2) or present a close-to te-rro verified accuracy, This behavior has also been observed practically and theoretically for Lp spaces (Zhang et al., 2022). The formulation in Eq. allows us to obtain verifiable models without the need to tune hyperparameters.
5.4 THE INFLUENCE OF SENTENCE LENGTH IN VERIFICATION
In this section we study the qualitative characteristics of a sentence leading to better verification properties, specifically, study the influence of the sentence length in verification. We compute
8

---

Published conference paper at ICLR 2025
AG-News
SST-2
1,00
Average Lentgh
Verified
Datasct
Method
Ner
0.50
Vet.
AG-News
LipsLev
228.0
221.4
258.9
SST-2
90.2
109.5
LipaLev
98.3
126.8
0.00
230
0.0
200
Sentence length
Sentemce length
Figure Sentence length distribution for verified and not verified sentences: We report the verified accuracy v.s. sentence length with LipsLev (Left), and the average length of verified and verified sentences (Right)
in the models trained with p Shorter sentences are harder to verify in both SST-2 and AG-News with both LipsLev and the brute-force approach.
the verified accuracy v.s. sentence length at k for the models in Section 5.2 with LipsLev and p = 2. For the AG-News we remove the outlier sentences with length larger than 600 characters. The full length distribution is displayed in Appendix
In Fig. J we can observe that for both verification methods on both datasets, the verified sentences present larger average length. Additionally, there is clear increasing tendency in the verified accuracy v.s. sentence length. We believe this is reasonable as single characters perturbations are likely introduce smaller semantic change for longer sequences.
CONCLUSION
In this work, we propose the first approach able to verify NLP classifiers using the Levenshtein distance constraints. Our approach is based on an upper bound of the Lipschitz constant of convolu- tional classifiers with respect to the Levenshtein distance. Our method, LipsLev is able to obtain verified accuracies at any distance & with single forward pass per sample. Moreover, our method the only existing method that practically verify for Levenshtein distances larger than k 1. We expect our work can inspire a new line works on verifying larger distances and more broadly verifying additional classes of NLP classifiers. We will make the code publicly available upon the publication of this work, our implementation is attached with this submission.
Future directions and challenges: A problem shared with verification methods in the image do- main is scalability (Wang et al. 2021). Scaling verification methods to production models a challenge, that becomes more relevant with the deployment of Large Language Models and their re- cently discovered vulnerabilities (Zou et al.] (202)). Even though our method is the first to practically provide Levenshtein distance certilicates NLP, neither the formulation of Huang et al. (2019) or our formulation covers modern architectures Transformers Vaswani et al. 2017). We highlight the main challenges as follows:
i) Tokenizers: Modern Transformer-basee classifiers utilize popular tokenizers such as Sen- tencePiece (Kudo and Richardson 2018), which aggregate contiguous characters in tokens before feeding them to the model. In order to deal with such non-differentiable piece, methods for computing the Lipschitz constant tokenizers are needed.
ii) Poor performance on character-level tasks: In the case no tokenizer' is used, transformers are known to fail in character-level classification tasks like the IMDB classification problem of Long Range Arena (Tay al. 202T).
iii Non-Lipschitzness of Transformers: Transformers are known to have non-bounded Lipschitz constant (Kim et al.) 202T). In the image domain, verification methods modify the model to be Lipschitz (Qi et al. [202]] Bonaert et al.) (021)) compute local Lipschitz constants (Havens et al., 2024). Nevertheless, it is non-trivial to extend such approaches from indindd distances to the Levenshtein distance.
Our work sets the mathematical foundations of Lipschitz verification in NLP, opens the door to addressing these challenges and achieving verifiable architectures beyond convolutional models.

---

Published conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Elias is thankful to Adrian Luis Müller and Ioannis Mavrothalassitis for the amazing discussions in the whiteboard of the Lab. Authors acknowledge the constructive feedback of reviewers and the work of ICLR") 25 program and area chairs. We thank Zulip for their project organization tool. ARO Research was sponsored by the Army Research Office and was accomplished under Grant Number W91 INF-24-1-0004 Hasler Al This work was supported by Hasler Foundation Program: Hasler Responsible AI (project number 21043). SNF project Deep Optimisation This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 200021_205011 205011.
BROADER IMPACT
In this work, we tackle the important problem verifying the robustness NLP models against adversarial attacks. By advancing in this area, we can positively impact society by ensuring NLP models deployed in safety critical applications are robust to such perturbations.
REFERENCES
Elias Abad Rocamora, Yongtao Wu, Fanghui Liu, Grigorios G. Chrysos, and Volkan Cevher. Re- visiting character-level adversarial attacks for language models. In International Conference on Machine Learning (ICMI.), 2024.
Moustafa Alzantot, Yash Sharma, Ahmed Elgohary, Bo-Jhang Ho, Mani Srivastava, and Kei-Wei Chang. Generating natural language adversarial examples. In Empirical Methods in Natural Language Processing (EMNLP), 2018
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. Advances in neural information processing systems (NeurIPS), 2020.
Yonatan Belinkov and Yonatan Bisk. Synthetic and natural noise both break neural machine trans- lation. In International Conference on Learning Representations (ICLR), 2018.
Gregory Bonaert, Dimitar I. Dimitrov, Maximilian Baader, and Martin Vechev. Fast and precise cer- tification of transformers. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2021.
Lei Chen and Raymond Ng. On the marriage Ip-norms and edit distance. Proceedings of the Thirtieth International Conference on Very Large Data Bases Volume 30, VLDB '04, page 903-803. VLDB Endowment, 2004.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International conference on machine learning, pages 854-863. PMLR, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (ICML), 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume (Long and Short Papers), 2019.
Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. HotFlip: White-box adversarial ex- amples for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume Short Pupers), 2018.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani. Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances neural information processing systems (NeurIPS), 32, 2019.
10

---

Published conference paper at ICLR 2025
Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi. Black-box generation of adversarial text sequences to evade deep learning classifiers. In IEEE Security and Privacy Workshops (SPW), 2018.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree. Regularisation of neural net- works by enforcing lipschitz continuity. Machine Learning, 110:393-416, 2021.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovie, Timothy Mann, and Pushmeet Kohli. On the effectiveness of in- terval bound propagation for training verifiably robust models. arXiv preprint arXiv: 2018.
Antonio Gulli. Ag's corpus of news articles, 2005. URL http::/ di wnt.:iiii.uiiiiii.m.....
-qulli/AC corpus of news art articles html
Aaron J Havens, Alexandre Araujo, Huan Zhang, and Bin Hu. Fine-grained local sensitivity analysis of standard dot-product self-attention. In International Conference on Machine Learning (ICML), 2024.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of classifier against adversarial manipulation. Advances in neural information processing systems (NeurIPS), 30, 2017.
Bairu Hou, Jinghan Jia, Yihua Zhang, Guanhua Zhang, Yang Zhang, Sijia Liu, and Shiyu Chang- Textgrad: Advancing robustness evaluation in NLP by gradient-driven optimization. In Interna- tional Conference on Learning Representations (ICLR), 2023.
Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krish- namurthy Dvijotham, and Pushmeet Kohli. Achieving verified robustness to symbol substitutions via interval bound propagation. In Empirical Methods in Natural Language Processing (EMNLP), 2019.
Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. Training certifi- ably robust neural networks with efficient local lipschitz bounds. Advances in neural information processing systems (NeurIPS), 2021.
Zhuoqun Huang. Neil G Marchant, Keane Lucas, Lujo Bauer, Olga Ohrimenko, and Benjamin I. P. Rubinstein. RS-del: Edit distance robustness certificates for sequence classifiers randomized deletion. In Advances in neural information processing systems (NeurIPS), 2023.
Robin Jia, Aditi Raghunathan, Kerem Göksel, and Percy Liang. Certified robustness to adversarial word substitutions. In Empirical Methods in Natural Language Processing (EMNLP), 2019.
Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention. In International Conference on Machine Learning (ICML), 2021.
Taku Kudo and John Richardson. SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations. Association for Computational Linguistics, 2018
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference on Learning Representations (ICLR), 2020.
Vladimir Levenshtein et al. Binary codes capable of correcting deletions, insertions, and reversals. Soviet physics doklady, volume 10, pages 707-710. Soviet Union, 1966.
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jöm-Henria Jacobsen. Preventing gradient attenuation in lipsehitz constrained convolutional networks. Advances in neural information processing systems (NeurIPS), 32, 2019.

---

Published conference paper at ICLR 2025
William Lifferth. Kaggle fake news, 2018. URL httpps///kgglle.ccm/cmoopooeeeee
fake- news
Aiwei Liu, Honghai Yu, Xuming Hu, Shu ang Li, Li Lin, Fukun Ma. Yawen Yang. and Lijie Wen. Character-level white-box adversarial attacks against transformers via attachable subwords sub- stitution. In Empirical Methods in Natural Language Processing (EMNLP), 2022.
Changliu Liu, Tomer Arnon, Christopher Lazarus, Christopher Strong, Clark Barrett, Mykel J Kochenderfer, et Algorithms for verifying deep neural networks. Foundations and Trends@ in Optimization, 4, 2021.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Association for Computational Linguist- ics, 2011.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks, In International Conference on Machine Learning (ICML). PMLR,, 2018.
Ramon E. Moore, R. Baker Kearfott, and Michael Cloud. Introduction to Interval Analysis. Society for Industrial and Applied Mathematics (SIAM), 2009.
John Morris, Eli Lifland, Jack Lanchantin, Yangfeng Ji, and Yanjun Qi. Reevaluating adversarial examples natural language. In Findings of the Association for Computational Linguistics: EMNLP 2020, 2020.
Mark Niklas Mueller, Franziska Eckert, Marc Fischer, and Martin Vechev. Certified training: Small boxes are all you need. In International Conference on Learning Representations (ICLR), 2023.
Alessandro De Palma, Rudy R Bunel, Krishnamurthy Dj Dvijotham, M. Pawan Kumar, Robert Stan- forth, and Alessio Lomuscio. Expressive losses for verified robustness via convex combinations. In International Conference on Learning Representations (ICLR), 2024.
Xianbiao Qi, Jianan Wang, Yihao Chen, Yukai Shi, and Lei Zhang. Lipsformer: Introducing lipschitz continuity to vision transformers. In International Conference Learning Repres- entations (ICLR), 2023.
Haifeng Qian and Mark N. Wegman. 1.2-nonexpansive neural networks. In International Conference Learning Representations (ICLR), 2019.
Zhouxing Shi, Huan Zhang, Kai- Chang, Minlie Huang, and Cho-Jui Hsieh. Robustness verific- ation for transformers. In International Conference on Learning Representations (ICLR), 2020.
Zhouxing Shi, Yihan Wang, Huan Zhang. J Zico Kolter, and Cho-Jui Hsieh. Efficiently computing local lipschitz constants of neural networks via bound propagation. Advances in neural informa- tion processing systems (NeurIPS), 35:2350-2364. 2022.
Siqi Sun and Wenjie Ruan. TextVerifier: Robustness verification for textual classifiers with certifi- able guarantees. In Findings of the Association for Computational Linguistics (ACL), 2023.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems (NeurIPS). 27, 2014.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena : A benchmark for efficient transformers. In International Conference Learning Representations (ICLR), 2021.
Yusuke Tsuzuku. Issei Sato, and Masashi Sugiyama. Lipschitz-marghh training: Scalable certi-
fication of perturbation invariance for deep neural networks. Advances in neural information processing systems (NeurlPS), 31, 2018
12

---

Published conference paper at ICLR 2025
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, f. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems (NeurIPS), 2017.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: multi-task benchmark and analysis platform for natural language understanding. In International Conference on Learning Representations (ICLR), 2019.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In USENIX Conference Security Symposium, 2018.
Shiqi Wang. Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and Zico Kolter. Beta- CROWN: Efficient bound propagation with per-neuron split constraints for complete and incom- plete neural network verification. Advances in neural information processing systems (NeurIPS), 34, 2021.
Michael S Waterman, Temple F Smith, and William A Beyer. Some biological sequence metrics. Advances in Mathematics, 20(3):67-337, 1976.
Xiaojun Xu, Linyi Li, and Bo Li. LOT: Layer-wise orthogonal training on improving 12 certified robustness. In Advances in neural information processing systems (NeurIPS), 2022.
Mao Ye, Chengyue Gong, and Qiang Liu. SAFER: A structure-fres free approach for certified robust-
ness to adversarial word substitutions. In Annual Meeting of the Association for Computational Linguistics, 2020.
Jiehang Zeng, Jianhan Xu, Xiaoqing Zheng, and Xuanjing Huang. Certified robustness to text adversarial attacks by randomized [MASK]. Computational Linguistics, 2023.
Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Rethinking lipschitz neural networks and certi- fied robustness: A boolean function perspective. In Advances in neural information processing systems (NeurIPS), 2022.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. Advances in neural information processing systems (NeurIPS), 28, 2015.
Xinyu Zhang, Hanbin Hong, Yuan Hong, Peng Huang, Binghui Wang. Zhongjie Ba, and Kui Ren. Text-crs: A generalized certified robustness framework against textual adversarial attacks. In IEEE Symposium on Security and Privacy (SP), 2024.
Yuhao Zhang, Aws Albarghouthi, and Loris D' Antoni. Certified robustness to programmable trans- formations in LSTMs. In Empirical Methods in Natural Language Processing (EMNLP), 2021.
Haiteng Zhao, Chang Ma, Xinshuai Dong. Anh Tuan Luu, Zhi Zhi-Hong Deng, and Hanwang Zhang. Certified robustness against natural language attacks by causal intervention. In International Conference on Machine Learning (ICML), 2022.
Andy Zou, Zifan Wang, J Zico Kolter, and Matt Fredrikson. Universal and transferable adversarial attacks on aligned language models, arXiv preprint arXiv:2307.1500 2023.
13

---

Published conference paper at ICLR 2025
A ADDITIONAL EXPERIMENTAL VALIDATION
present the definition of the performance metries employed in this work. In Appendix A.5 we present our grid search for selecting the best learning rate for each dataset and value in the ERP distance Definition 4.1 In Appendix A.6 we evaluate the effect of training with different number of layers and report their latencies.
In Appendix A.I
A.1 DEFINITION OF PERFORMANCE METRICS
In this section define the key metries used to evaluate models and verification methods. Let 1 () be the indicator function, given a classification model f S(T) + IR" assigning scores to cach of the o classes and dataset D = {S(()) , J with S E S(T) and y( E [o], the clean, adversarial and verified accuracy defined
Definition S1 (Clean accuracy). The clean accuracy is percentage in [0, 100] that is computed as:
Acc.(f,D) =
100
1 y
arg max f(s
jE(o)
=11
Definition S2 (Adversarial accuracy). Given an adversary A S(T) - S(T) that perturbs a sen- The adversarial accuracy is a percentage in [0, 100] that computed as:
tence")
Adv. Acc. (,)) =
100
Σ ==1
y
arg max f (A((()))) jE(()
Definition (Verified accuracy). Given verification method v returning the certified radius (see Section 4.1 for a given model and sample (S, y) as v(f, S, {0} UN. The verified accuracy at distance a percentage in [0, 100) that is computed as:
Ver. Acc. (f,
100
(0))
For simplicity, the arguments of each accuracy function are omitted in the text as they can be inferred from the context.
A.2 SENTENCE LENGTH DISTRIBUTION
In this section, we provide additional details about the sequence length distribution of verified and not verified sentences. Specifically, in Fig. S2 we provide the full distribution of lengths from the experiment in Fig.
A.3 STANDARD DEVIATIONS
In Table S4 we report the results from Table with standard deviations for completeness.
A.4 LARGER DISTANCES FOR FAKE-NEWS
In Section 5.2 we reported the performance in the Fake-News dataset over the first 50 samples of the test set and only up 2. Nevertheless, the speed LipsLev allows for more samples and
larger distances. In Table $5 we evaluate the performance of LipsLev over the first 1, 000 test
samples and up to
Thhe adversary will usually adhere constraints such as (S, A(S)) k.
14

---

Published conference paper at ICLR 2025
AG-News
SST-2
100
Not verilied
Not verified Verilied
Verified
80-
75-
Rog.
20+
25
400
600
100
200
Sentence length
Sentence length
Figure S2: Sentence length distribution for verified and not verified sentences: We report the histogram of the lengths for verified and not verified sentences & with LipsLev in the models trained with 2. Shorter sentences are harder to verify in both SST-2 and AG-News with both LipsLev and the brute force approach.
Table $4: Verified accuracy under bounded d We report the Clean accuracy (Acc.), Adversarial Accuracy (Adv. Acc.) with Charmer (Abad Rocamora et al. 2024), Verified accuracy (Ver.) and the average runtime in seconds (Time) for the brute-force approach (BruteF), IBP (Huang et al.] 2019) and LipsLev. OOT means the experiment was Out Of Time. X means the method does not support diev > 1. Our method, Li LipsLev is the only method able to provide non-trivial verified accuracies for any l in a single forward pass.
Daraect
1e Acc.%%
Adv: (ox-(55)
Charmer
Time(s)
BruseF
Timets)
Ver
IBP
Timefsi
Vor(5)
Sipsley Time(s)
65. 10)
32 97
47. m0
1.70010465)
47.87g:000
001
16:35am
27 27.77amm
16.70ggp
11,00g00
0.0015 aaams
0.001
Mi-News
69. m0
54.47
54.40g
001
10.35mm00
18.50 18.50gma0
17 17.56 (8)
28.50
12 2355
0.001
0.001 all
74. 74.80
46.47 2m0
62 ma
7.32
7.39-10-4))
G2.07g:0599
OOT
29 (0.
29 29.30am.41
31 31.54 (a)
28 28,80
13.93
0. 0.00070
0.00010
63 (0)00)
50 10050
10 92
184 11000))
30 20.00)
GOT
2:27 227aram::
33.94an..3)
2 2.88
1 16.68
0 2.90
0 0.0008
0.00084
SST-2
69 20
26. 20050)
45 2mm.20
99 al
19 21000))))
45 45.22
OOT
2.51
19.00.)..0)
2.50 2:00
18 18.60
1.88
0. 0.002
0. 0022
2
60. a0.
50.00 (2
68 51 am0440
2.00 2.00
2.00
48 28:78
OOT
4 1100m
16.06.n.m
5:20
16.57
0. 0.75
0. 00007
0. 0.407 2100022
2
100.00
Mu 80.57 am
76. 76.00gr
0682
00.2211194)
86.67
00T
U72.46g
85 (0.30
980 84
08,67
M5.33 9x)
1,017
IL
Pake-News
2
98 08.00ac1.co
79. 33gr
92 m0
67.11
67.11
67.
92.001g:e00
001
91 ma
75,33
M1 13.33
1.0144.0
2 98.00 ueg
78 18.00grss0
88 57
7A54
(8.79
88.67
00T
1221 122166
S7 (1)
1466.88
NT. 38.3
71333
00089
2 (4.077
50
07 43
14.102/044)
14.10.)440
67. 67.4432:400
150-10a1339) HOT
50
158 20250.23
31 37 ac4.5
6,90g.1..0
0. 0.0047, 200000)
0.007,
IMDB
69. 60.07ac7
61 17
52
14.Mg.a27)
61.00
OOT DOT
131 131.23 47.30
155 22
28. 23
6. 1.80gzz
0. 0027
60. (0
35. 10
66
16.242(449)
46. 16.79
DOT
261.00aaa14
57 57
908 70
0.87 100.000
8.67 5:3.00
0.00 190000000001
0.00 19
Table S5: LipsLev verified accuracy in FakeNews over the first 1, 000 validation samples and up to t 10. We observe method is able to verify non-trivial accuracy with even up to 10 character changes.
Clean Ave.
Verilsed Ace.
10
45.63 am 05.
57:50.mm 21.50
72.48
49.37 a:3.4)
31 31.03 (3,33
20.03 an
14.07 a1 9.77 6.67 a 5.00 3.60
75.97 72.97
56.55 56.551:430
38
15.89 11,30
7.77 ar on
5.50 4.27
06.000g0000g
87.502 70.77 mn
48.07gm
m)
30.97 (000)
20.57 ogg
10.07 wy 9.20 6.10g my 4p 2,50gg my
A.5 HYPERPARAMETER SELECTION
In order to select the best learning rate in each dataset and p norm for the ERP distance, we compute the clean and verified accuracy at & 1 in validation set of 1, 000 samples extracted from each training set. We test the learning rate values {0.1, 0.5, 1, 5, 10, 50, 100, 500, 1000). We train convo- lutional models with 1 convolutional layer and the standard embedding, hidden and kernel sizes in Section 5.I We notice these large learning rates are needed due to the 1-Lipschitz formulation in Eq. (
15

---

Published conference paper at ICLR 2025
SST-2
AG-News
0.75
Clen Age
0.61
0.70
6.02
0.65
6,00
0.55
0.08
11.00
11.20
6.02
1.0
1000.0
Learning
Leaming
Figure S3: Learning rate selection for the SST-2 and AG-News datasets: We report the clean and verified accuracy in a validation set of 1,000 sentences extracted from the training split of each data- set and set aside during training. We set the learning rate equal to 100 in the rest our experiments as it provides a good trade-off between clean and verified accuracy for all norms and datasets.
Clean
Verified (k 1)
60
31-
Acc.
Acc.
20-
00
10
20
Layers
Layers
Figure $4: Training deeper models in AG-News: We report the clean and verified accuracies with LipsLev at k for E {1, 2, oo). Clean and verified accuracies decrease with the number of layers. With p the performance is less degraded with the number of layers.
Based on the results from Fig. S3 we select 100 as our learning rate for the rest of experiments in this work.
A.6 TRAINING DEEPER MODELS
In this section, we study the performance of models with more than one convolutional layer. We train with 1, 2. 3 and convolutional layers with hidden size of 100 and kernel size of 5 and 10 for SST-2 and AG-News respectively. We train the models with the I-Lipschitz formulation in Eq. 7 with
21,2,00).
we can observe that increasing the number of layers degrades the clean and verified accuracy for every value of Nevertheless, for = 2, the effect is diminished. Jointly with the improved performance when using p = Section we advocate for its use in the ERP distance. We believe this performance degradation is related to the gradient attenuation phenomenon (Li et al., 2019]. It remains an open problem to avoid gradient attenuation the case where the Lipschitz constant of the ERP distance is enforced to be
In Figs. S4 and S5
In Table S6 we can observe that our models have low latencies. Noticeably, with p = 2 we observe larger latency than with (1, oo). This is due the need to compute the espectral norm each
16

---

Published conference paper at ICLR 2025
Clean
Verified (A- = 1)
21
70-
15
65-
10
60-
00
55-
50
Layers
Layers
Figure S5: Training deeper models in SST-2: We report the clean and verified accuracies with Lipslev at k for p 21, so). Clean and verified accuracies decrease with the number of layers. With p 2 the performance is less degraded with the number of layers.
iteration. Nevertheless, this cost is still low and only incurred during training, as by rescaling the weights, we can any model in Eq. (7) formulation model in Eq.
Table S6: Latency in seconds for different p and number of layers.
Layers
2
3
4
1
0.0017 (0.019))
0.0015 (0.0007)
0.0015 100151100 (0.0003)
0.0019 (0.0002)
2
0.0225+ 0045)
0.03333=(0.000 0026)
00.008))
1.0740=(0.0000
30
0.0007
0.0011
0.0015
0.0019
A.7 COMPARISON AGAINST RANDOMIZED SMOOTHING
In this section, we analyze the differences in methodology and results, between our approach and the Randomized Smoothing approach in Huang et al. (2023): RS-Del.
As an advantage. RS-Del can be employed with any base classifier f (STT) Rº assign- ing scores to each of the o classes, without restrictions the architecture. Nevertheless, neither the classifier verified by RS-Del, nor the certified radius itself are deterministic. In Random- ized Smoothing, given classifier f and given set of perturbations P(S), smoothed classifier [(()] is constructed.
f(S) (.()
E
In practice, multiple perturbations (Mpred) are sampled from P(S) and the prediction is estimated through Monte-Carlo the average f(S) E f(S)), with S, sampled i.i.d uniformly from P(S). Similarly, a-confidence lower bound of the margin is estimated with Food samples, which then used obtain an a-confidence estimate of the certified radius. Therefore, the certificates provided with Randomized Smoothing are probabilistic and regarding the smoothed classifier f. not the original f.
Contrarily, LipsLev imposes the strong constraint of knowing an upper bound of the Lipschitz constant the margins of f. However, this enables the direct, non-probabilistic, estimate of certified radius in single forward pass through f.
Having these differences in mind, we compare the performance of Lipslev and RD-Del when verifying the models in Table 2 To do so, we run RS-Del with the recommended rpedd 1, 000, 7bbnd = 4, 000, Pael 0.9 and a 0.05.
In Table S7 we can observe that RS-Del significantly degrades the clean accuracy of the classifier. this is due to the randomization introduced in the prediction process. However, RS-Del able to improve the verified accuracy in SST-2 for all p and in IMDB for p 2. In terms of runtime, observe that, while being significantly slower than LipsLev, RS-Det able to provide certificates in time range from to 2 seconds, which is considerably faster than Brute-F and IBP.
17

---

Published conference paper at ICLR 2025
Table S7: Comparison against Randomized Smoothing: We report the Clean accuracy (Acc.),
Verified accuracy (Ver.) and the average runtime in seconds (Time) for LipsLev and RS-Del
(Huang et al. 2023). RS-Del reduces drops significantly the clean accuracy of the classifier RS-Del
improves the verified accuracy of Lev in SST-2 for all p and IMDB for 2.
LipsLev Ver.(%)
RS-Del (Huang et al.
2023
Dataset
P
Acc.(%)
Time(s)
A%c.(%)
Ver.(%)
Time(s)
20
65.23
11.60 (0.45)
0.0015 (0.33)
0.0015 (0.000000000000
(0.0003)
51.77
(.08 (0.44
0.27 (00.05)
(.08
AG-News
69.632.0.10)
34.50
0.00140 0.001-40
50.67
3. (0.19)
(.05+(00005)
0.001401(0.. (0.531(0.29)
00007)
0.80
1.051;00055
2
c4.800
38.80
13.93+
0.00970
0.00970
=8.30)
1.68+(0.07) (090
4.60
1. 1.68
14.68
0.00084410.00000
21 21.98 (1.37)
0.601 (0.04)
20
(3.95=((.30)
0.00084 (.99
57.11 (0.49)
3. (1.1
0.60+(0.04)
SST-2
18.69 (0.80)
(..027+
21.10
0.69
69.69
56. 36.422(1.00 (1.08))
(0.00
0.0022
3..2 76)
0.69
14.57 (0.34)
0.0047
22.40 20.99998)
0.941:0000)
(9.95_(0.32)
59.17 (0.90)
0.73
0.0047
4.80
0.94+(0.06)
85.33 94)
0.017
69.33
1.87 10)
00
(00.00
68.67 (0.944)
0.017 0.0171:000006)
80.67 (00.4)
56.67 56.671(0099) (00.94)
1.87
Fake-News
91.33+
2.0042(0.0058)
(.874(0.06) (6.00=(2.89)
98.00
77.33=
75.33+ (3.40)
0.014 (0.0004))
5+1.00((1.63)
(.87
87.33 (6. 80)
0.0089 (0.000)
62.67.18890)
2.24110011)
2
98.00
(5.33+
0.0089 0.0009_(0.010)
75.33=
57 (7.33_(6.60)
(.24+(0.11)
31.37 +
0.00 (0.00)))
0.90+
1.644
no
74.57 (5.222)
5.90I(1.36)
0.0047 0.0047 (0.0013)
(0.00)
0.00
1 1.641.00000
IMDB
28. (6.
0.0027
3.50
1.744(0.00)
1
60.37
6. (2.0))
0.0027 0.0027 (0.0025)
19.20 20.0000o.om (0.00)
0.40+
1. 1.74+(0.00)
60.60
0.0019 (.67))
48.36 (36.49)
33.67 ((2.67
2. 2.144(0.20)
(.87
0.0019
18. (15.88)
2.144
B PROOFS
In this section we introduce the mathematical tools needed to derive our Lipschitz constant upper bounds for each layer in Eq. (6) The section concludes with the proof of our main result in The- orem 4.3 In Appendix B.I we present some remarks to be considered regarding global and local Lipschitz constants.
Definition S1 (Zero-paddings). Let E Xx sequence of m non-zero vectors. Let / 2 m, a zero padding function Z Xa + R xd is some function defined by the tuple:
(ix) (ix)k=n
m > in > ig v1 <j k:
if in # if iz =
(1k
E [1] i i= 00
so that:
26 (x)
Tis 0
00
if in 0
Intuitively, a valid zero pero-ppdding function inserts - m zeros in between any vector of the sequence, the beginning the end. We denote Zm, the set of zero paddings from sequences of length m to sequences of length 1.
Remark S2. Given matrix A E mmmxm and zero padding Z Zm,,, we denote the column and row-wise padding Z(A)
(
Proposition S3 (Alternative definition of dERr)) Let dERp be as in Definition 4.1 Let A E Rd and B E Raxd be two sequences. Let Zm.m+n and Zn,ntn be the zero-padding fanctions from length m and respectively to length m + The ERP distance can be expressed as:
&eRr (A,))
min 2o ZZ mnnn ZoE Zn. mn
(A)( - =B)I1p
18

---

Published conference paper at ICLR 2025
Lemma S4 (Properties of the ERP distance), Some important properties of the ERP distance are summarized here:
(a) Generalization of edit distance:
In the case of having sequences of one-hot vectors A E [0,1]mxd ||: 1, and using
p == co, the ERP distance is equal to the edit distance (Levenshtein et al. 1966).
(b) Invariance to the concatenation of zeros:
Pep (A 2 O, B) = -Eear + A, B) = dERP( (A,)) B) VAE E Ru B E Rx
(c) Distance to the empty set:
d A, 0)
Σ
aiillp AA E Rm
1=1
(d) Symmetry: dERP( [, B) d'ERP( C A) AA E Rx B BERand
(e) Triangular inequality: For any A IR mmd
B E Raxd B E Rixd have:
depp(A (A S (e A. A) + dfEpp B).
(f) Subdistance:
The ERP distance is not distance because of its invariance to the concatenation of zeros:
ERP A, A 0) = deRp A, A) O AA E Rm
proof of Lemma S4 Properties (a), (b), (c), (d) and (f) are straightforward from the deffinition, we
will prove the triangular inequality (e). This proof follows similarly the one of Waterman et al. 1976) for the standard Levenshtein distance. Let = m + n + I, starting from the definition in Proposition S3
PERP A, B)
U ERP (B,C)=
min 2 Z'E2,,
Σ -={(A))=((BB))
k=1
- -0 -
J=1
Let Z 2 E 21.21 be two zero paddings so that Z (B)) = (z()
26
(A, + &eRp (
(BC)) =
min Zo Eem,m,i E 2.E 1., E 21,t.
12 (B))
k=
(Z -(0))))>=((((0) -
2L
(Triingular ineq. for ||-11,)]
min Z Z. L, En..
Σ) (=(((*((A) ==)(2(BB)
k=1
2 2c 2
+ =((((B)) =1(2<(0)
2L
(B) Z(
min
Σ
xx( - (Z(((()
z 2 E E de (A,C),
where the last equality follows from (Z and = (Zd) being valid zero paddings.
19

---

Published conference paper at ICLR 2025
Lemma S5 (Difference of sums). Let A, B E Rs. we have that:
m
n
ag
bj
S deppp( (, B)
/=1
proof of Lemma 55
m++
Σ 0j
bj
min
Σ 2((A) =B(B)
Z mm 2 mitton
==1
k=
min
= ([[A))=((BB]]
2 E. m, m+n E.n
RP (A, (A,
Lemma S6 (Difference of means). Let A, B Ny. we have that:
m
mm
n
m
1
bj
Σ
depp( (A, B)
71
11
n
j=1
and
a
1
bj
m
nl
Σ bj
m
CER (A, B).
m
n
m
n
m
In the case of A and B being sequences of one-hot vectors, we have that:
1
die (A, B)
if m=
Σ
by
diev A, B)
if m +
proof of Lemma 56
Starting with the first result:
1
b
(n
m
m)
m
t=
1=1
1=1
7
1
m
m
1
m n
a
+
Σ a
Σ bj
m n
j=1
mm n|
[Lemma
S5
<
d FRP
(A, B)
Note that since A and B are interchangeable, we immediately have:
1
m n
b
+
depp (A, B)
(8)
j=1
In the case A and are sequences one-hot vectors, if m = n, we can directly get the 1/m factor out of the norm and apply Lemma S5 to get the first case. For the o n, we can manipulate
20

---

Published conference paper at ICLR 2025
Eq. 8 get the desired result:
m n
bj
Σ
b
+ m
die (A, B)
71
m
1=1
j=1
j=1
1
1
[Im n/ s diev (A, Triang. ineq.] S
m 1bblls
diev (A, B)
2 m
[1 = [
diev (A, B)
Lemma S7 (Linear transformations). Let A, B E Ne be two sequences and V E Bdxk We have that:
(AV BV) S (A, (A,
In the case of sequences of one-hot vectors, we have that:
(AV BV) S (A, M(V).
where
MVV max max | pp max ||0, 05||p} /E|d]
(.E((d]
Proof. Follows immediately from Definition 4.1 and the fact that ||AB|| < |||||||||| for any matrices and B. The second result for one-hot hot vectors follows immediately from the fact that the biggest change in the embedding sequence that be produced from single-character change, is either given by inserting the character with the largest norm embedding (left side the max), or replacing character with the character that has the furthest away embedding in the l, norm (left side of the max).
Lemma S8 (Elementwise Lipschitz functions). Let deep be as in Definition 4.1 Let A E Rmxd and B E pa be two sequences. Let f Rdd + I2t be a finschitz,unction so that:
((a)- S L, L--lla- bll, Va, b E Ed
Let F(A) E Rmnk and F(B) E Bank be the application of f to every vector in both sequences, we immediately have that:
ERP (((A),(())) Ly (A,
( B)
Lemma 89 (Convolution). Let degr be in Definition 4.1 Let P {0, 13 and Q {0, 1 be two sequences of m and n one hot-vectors respectively. Let the function working with arbitrary sequence length be F {0. 1 + Rixr. Let the convolutional filter C. Rixr (1+--1) 1jxk with kernel K E Roxkxr where q is the kernel size and le is the number of filters. We have that:
d (CF(())) 5 MM(K) &enr (F(P), F(Q))
where:
2 M(K) Σ
Killp
21

---

Published conference paper at ICLR 2025
Proof of Lemma 59
Let L = m n 29 2. Starting from the definition of the ERP distance in Lemma S4 and the definition of the convolutional layer in Definition 4.2
EERP ((F()))C(((Q)))
min
Σ |[((C(F(()) (((((()))
2'E2ml4 1.k. k=1 2 1.t
m+4-1
min
2
Σ K (P))
2
Σ k))
2'E2ml4 1,b k=1 14 1.b
i=1
P
m++-1
12--11
9
min Z'E2mta-L,by
2k
Σ K,(t+J-1(P)
K Kfftss-1(Q)
1=1
2 2'E2nta-1,
i=1
4
Σ Kj (zk (Jitj- (P)) =2 (1)+)-1(Q))
- (2))=+1-111
min ZeE2mle L.k. 2'E2n19-1.2 k=
min ZaE2mia L.b. k=1jm1 Z2 1.2
K K1llpp
2 (1f+5- 2x (11tt-11Q0)111 1|
min
K
2 Σ
2 1 (F)+s-
')1,
Ze L.4. j=1
Z'E2,11 1.C
k=1
Klll dERP (F(P),
where the last equality follows from the fact that [fitj- (P) and [ (Q) are just windows F(P) and F(Q) respectively including the complete sequences F(P) and
F(Q). resulting in dERP (If+)- (1)+)11())111 dERe (F(P),F(()) Vj = 1,... .q.
Proof of Theorem 4.3 We will bound the absolute value of the difference of outputs for two sen- tences P.Q. S()) of lengths m and respectively. For any y and ÿ:
(a+1((-1)) (PE)
i+
(P). 90.s (Q.s(Q))=
Σ
10
Σ
o (cc)
(((()))
(wo wyy)
mm--0-1)
n+i-(g-1)
[Hölder's inequalityl $
km w mll
Σ
(c (PE)
Σ
(c (QE)
wg wall deer (a (c (PE) a (c (QE)
Lemma S5
[Lmma S8 and Lemma 89 recursively] S wy wyll. I (M((C))
dPsu (PE,
1
II ar((c1)))
[Lemma S7
Wg
wyll
.M(E) de (P.Q).
B. REMARKS REGARDING GLOBAL AND LOCAL LIPSCHITZ CONSTANTS
In this section we introduce some interesting remarks regarding how global and local Lipschitz constants are employed in this work. We define global and local Lipschitz constants as:
22

---

Published conference paper at ICLR 2025
Definition S10 (Global Lipschitz constant). Let g: :::g::00 S(T) + R and di be defined as in Section We say G is global Lipschitz constant if:
lg(P) - g(Q) S G (e, VP.QEEUI
The Lipschitz constant G in Definition S10 is valid for any two sentences P and Q, example is our Lipschitz constant in Theorem 4.3 When additional conditions are posed on the set of sentences where G is valid, say Lipschitz constant is local. A specific case of locality is when the Lipschitz constant depends on one the arguments of the distance as G(P), ,,, this is the kind of local Lipschitz constants we observe this work:
Definition S11 (Local Lipschitz constant). Let g S(T) - and dea defined as in Section We say G ST) > R is global Lipschitz constant if:
lo (P) s(Q) S G(P) drev (P. Q) VP, (P.QES())
Some examples such local Lipschitz constants are Jemark|4.5Jan Corollary 4.6 to consider regarding global and local Lipschitz constants are:
Some properties
Remark $12 (Global Lipschitz constants upper bound local Lipschitz constants). Let G be global Lipschitz constant as Definition $10 and G S(D) - IR+ local Lipschitz constant as in Defini- tion STI
we have that:
G(P) VPE)(T).
Remark S13 (Local Lipschitz constants might not hold everywhere). Let G: S(T) - R+ be a local Lipschitz constant as Definition S11 there might exist some P, Q, R 8(T) such that:
(g(Q) - s(R) G(P) (Q, R)
Remarks (ST and S13 highlight the two key aspects of local Lipschitz constants. While the bound is tighter than for global Lipschitz constants (eemark(S12)) these bounds can only be employed to give the certified radius around the sentence where compute the local Lipschitz constant G(P), otherwise, the Lipschitzness property is lost (Remark S13).
23


Reviews:
[{"review_id": "X9ZkxiGhy4", "reviewer": "Reviewer_39zs", "summary": "The paper introduces a technique to verify the robustness of a neural network for text classification tasks in a natural language processing setting (NLP).\nIn NLP, the Levenshtein distance is a natural way to measure the distance between two strings.\nExisting verification approaches, that often rely on interval bound propagation (IBP), are however prohibitively expensive when using the Levenshtein distance to measure robustness radia.\nTo address this, the authors present a Lipschitz constant-based verification technique that allows to compute a certified robustness radius for convolutional models, once the Lipschitz constant of the classifier is known.\nFor their verification procedure, the authors consider a real-valued extension of the Levenshtein distance and a specific convolutional architecture, for which they derive robustness radius bounds that can be computed with a single forward pass.\nCompared to existing IBP and brute force approaches, the proposed method is significantly faster and provides comparable clean/verified accuracy ratio for a Levenshtein distance of 1.\nRemarkably, the proposed method is the only one which can provide robustness guarantees for a Levenshtein distance of 2.", "questions": "* What is the relevance of methods that combine several algorithms such as alpha-beta-CROWN in your investigation? Can such approaches be adapted to the NLP setting?\n\n* The approach you propose is sound, can you discuss completeness too?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors address an interesting problem in NLP, which is of great relevance given the prevalence, and related risks, of large language models.\nFrom a wider perspective, it is important to devise techniques to provide robustness certifications which are practically computable.\nThe paper has thus a strong motivation.\nWith respect to the approach, the paper clearly presents the limitations of existing techniques and orderly discusses the proposed solution.\nThe paper is well structured, and it seems sound and of potential practical relevance to me.", "weaknesses": "**Relevance of ReLU-activated convolutional networks**\n\nWhile the paper is generally well motivated and an architecture similar to the one discussed has been previously investigated, I think that further details on the relevance of the method presented would be helpful.\nSpecifically, it is not clear how practically useful ReLU-activated, fully-connected convolutional networks are in text classification.\nAs part of the motivation is to make NLP verification practically achievable, I think that a more detailed discussion of the limitations of the proposed method should be part of the main body of the paper.\n\n\n**Definition of terms**\n\nSome notions and terminology used require more explicit definition.\nFirstly, Lipschitz continuity, as well as related concepts such as the \"local Lipschitz constant\", is never explicitly introduced.\nAs the paper heavily relies on these concepts, they should be introduced.\nSimilarly, the notions of \"clean accuracy\" and \"verified accuracy\" are not clearly defined. \nAs these are used as the main performance metrics, they should be properly described as well.\n\n\n\n**Empirical evaluation**\n\nRelated to my previous comment, further explanations on the behaviour of the clean accuracy for networks with more than one layer is necessary.\nIn figure S4, the clean accuracy drops significantly as more than 2 layers are used: why is this behaviour observed?\n\n\n**Minor comments**\n\n* line 52, of with -> with\n* (several places) Related works -> related work", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AetFkoEczv", "reviewer": "Reviewer_Mjg7", "summary": "This paper studies the certified robustness of convolutional neural networks for text classification under Levenshtein distance. The major challenge of this setting compared with standard certified robustness is twofold: one is the non-fixed length of text under perturbation, and the other is the discrete nature of tokens. The authors define the concept the Lipschitzness in this setting in terms of Levenshtein distance, and derived a relxation method for compute the Lipschitzness. The approach can be readily used to train certifiably robust models. Results show that the method is efficient and can achieve a performance on par with previous IBP-based certification and extend to larger perturbation scenarios.", "questions": "1. Why on FakeNews dataset LipsLev has exactly the same performance as IBP when the Levenshtein distance is 1?\n\nMiscellaneous:\n1. Line 108: $s_i$ should be $S_i$?\n2. Line 240: $\\mathbb R^{m+(q-1)\\times d}$ should be $\\mathbb R^{m+2(q-1)\\times d}$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem is significant and challenging. The original problem of certified robustness typically focuses on continuous, fixed-demension inputs, which is different from real-world NLP setting. The authors instead considered Levenshtein distance, which is a reasonable metric.\n2. The proposed solution is interesting, efficient, and simple. This is a major advantage of this paper compared with prior approaches.\n3. The writing is quite clear and readable. I enjoy reading this paper a lot.", "weaknesses": "1. One major problem is the Lipschitzness constraint is so strong and perhaps harms the expressive power of resulting model, thus hampering the clean accuracy. In the standard certified robustness community in CV, constraining the Lipschitz constant does not show performance comparable to IBP. This problem is also theoretically studied in [Zhang et al. 2022]. Do you think your models in experiment suffers from this problem in clean accuracy compared with other approaches in small perturbation scenario?\n\nReference: [Zhang et al. 2022] Rethinking lipschitz neural networks and certified robustness: A boolean function perspective. NeurIPS 2022.\n\n2. Regarding the experimental results, the performance where Levenshtein distance is 1 does not show the advantage of the proposed method. Although the training and verification is quite efficient, the performance on SST-2 and IMDB is not comparable with the simplest IBP.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hQ4hisKo9W", "reviewer": "Reviewer_U4sY", "summary": "This work presents a convolutional text classifier which is certifiably robust to Levenshtein-distance perturbations.", "questions": "1. To confirm: Theorem 4.3 holds for any choice of $p$ and $r$ which satisfy $1/p + 1/r = 1$?\n2. A suggestion for Figure 1: I think this would be better presented a line graph with the y axis as \"percent of sentences verified.\" That's what you're actually trying to communicate: that as the sentence length goes up, a high fraction are verified. Right now, readers have to mentally \"divide the columns\" to  back out what you're trying to say. Another alternative is a stacked bar chart based on proportions, e.g. something like [this](https://community.tableau.com/sfc/servlet.shepherd/version/renditionDownload?rendition=THUMB720BY480&versionId=0684T000002JELx&operationContext=CHATTER&contentId=05T4T000008xZ3u&page=0).\n3. Have the authors empirically verified their certificates by running inference on random string modifications within the Levenstein distance of the certificate? Just to check that there's no mistake in the proofs that is slipping through.\n4. Related to the previous point, I'd be curious to see the gap between the empirical and theoretical certificates, perhaps adapting a greedy coordinate-wise attacking strategy as in [1]. But I understand that this is orthogonal to the certified robustness focus of the paper, so this is just a suggestion to the authors if they are independently compelled to investigate.\n\nMinor notes:\n1. \"English\" on line 92 should be capitalized.\n2. In Definition 4.1, it seems that the notation of $d_{ERP}$ should also be dependent on $p$? I.e. $d_{ERP}^p(A,B)$.\n\n[1] Zou, Andy, et al. \"Universal and transferable adversarial attacks on aligned language models.\" arXiv preprint arXiv:2307.15043 (2023).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Overall, this work is a solid academic contribution, albeit with limited prospects for scalability.\n\n1. I like that this approach provides closed-form, deterministic certificates. It is the first paper that I have seen tackling the challenging Levenstein-distance setting without resorting to randomized approaches.\n2. The paper writing is clean and structurally sensible. The problem setting is well-motivated and the necessary prior work is precisely and clearly introduced.\n3. Figure and table presentation is thoughtful -- I appreciate the coordinated highlighting between Table 2 and Table 3.\n4. Method runtime is orders of magnitude faster than baselines; this is expected as the Lipschitzness constant is enforced by construction.\n5. The theory is carefully presented and a quick scan of the proof strategy in appendix B makes sense, although I haven't checked the proofs in detail.", "weaknesses": "1. My main concern with this approach is that a) the certified edit distances are very small (one or two characters), b) the models are tiny (only one convolutional layer), and c) I think possibility for future improvement is minimal. Layer-level Lipschitz constants have been more or less discarded by the image classification robustness community for several years now, as exponential signal attenuation makes it difficult to construct verifiable deep networks. This problem setting is arguably much more difficult, and since layer-wise Lipschitz approaches have proven intractable for images, I don't expect that this approach will be scalable to any reasonable network size.\n2. Section 6 discusses extensions to transformers, which is too far removed from what is presented in the paper. I understand the author's desire to connect their approach with SOTA language models, but a one-layer convolutional classifier is nowhere close to the complexity of a transformer.\n3. The literature review should be a little more comprehensive, and do a better job of grouping related works. For example, a quick google search for \"certifiable robustness text classifier\" yields [1], which is certainly related work.\n4. The authors don't evaluate against randomized methods. While I understand that deterministic methods are a more apples-to-apples comparison, some readers might appreciate fully comprehensive baselines (perhaps in the appendix). \n \n[1] Siqi Sun and Wenjie Ruan. 2023. TextVerifier: Robustness Verification for Textual Classifiers with Certifiable Guarantees. In Findings of the Association for Computational Linguistics: ACL 2023, pages 4362–4380, Toronto, Canada. Association for Computational Linguistics", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iIhZG7lmnD", "reviewer": "Reviewer_PA7T", "summary": "This paper derives the Lipschitz constant of convolutional networks with respect to the Levenschtein distance on its textual inputs. As a result, certified radii (in the Levenschtein distance) for robustness are provided. It is shown how to use the derived Lipschitz bound in order to train a 1-Lipschitz model (with respect to the Levenschtein distance). Furthermore, experiments are conducted to validate the effectiveness of the proposed robustness certificates.", "questions": "1. Line 161: How is $d_\\text{edit}$ defined? It would be good to explicitly define this for readers that are from outside the NLP community. It would also be good to clarify exactly what the embedding matrix $\\mathbf{E}$ is.\n2. Line 163: In the introduction, you said that you would denote the elements of a matrix by $x_{ij}$ (no comma in the subscript). However, you're now using commas in the subscripts (e.g., $z_{i,j}$ and $e_{k,i}$). It would be good to fix things to use consistent notation throughout the paper.\n3. Line 173: \"tenths\". It looks like you probably meant \"tens of thousands.\"\n4. In Section 4.1, you are concerned with local Lipschitz constants, but then in Section 4.2 you begin to discuss global Lipschitz continuity. Why the discrepancy?\n5. Line 253: The footnote 1 should be put after the punctuation. Otherwise, as it is now, it looks like it is part of the mathematical expression (i.e., it looks like \"one to the power of one\").\n6. Remark 4.5: Could you explain how this is a local Lipschitz constant? This seems like a global bound if it indeed holds for all $\\mathbf{P}$ and $\\mathbf{Q}$.\n7. Table 2 makes your method look quite loose, with IBP and BruteF attaining higher verified accuracies than yours in most of the $k=1$ settings. I understand that the other methods are more computationally expensive/are not applicable to $k=2$, but the results being displayed here are not very convincing.\n8. \"Our method, LipsLev, is able to provide the best performance in AG-News\" Isn't BruteF providing the best performance for AG-News?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The topic is certainly of interest to the ICLR community. The mathematical derivations appear correct. The proposed ideas are novel and well-motivated.", "weaknesses": "I have concerns regarding the presentation and performance limitations of the proposed method. See my Questions below for more details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)