Certified Robustness Under Bounded Levenshtein Distance

Authors: Elias Abad Rocamora, Grigorios Chrysos, Volkan Cevher
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Robustness verification, Text classifiers, Lipschitz constant

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.

Decision: accept (poster)
Reviewer scores: 8, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1730179220155

thread_type:
official_review

<thread_object>
creator: reviewer_pa7t

<content>
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.

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.

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.
2. 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.
3. Line 173: "tenths". It looks like you probably meant "tens of thousands."
4. 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?
5. 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").
6. 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}$.
7. 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.
8. "Our method, LipsLev, is able to provide the best performance in AG-News" Isn't BruteF providing the best performance for AG-News?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730354532684

thread_type:
official_review

<thread_object>
creator: reviewer_u4sy

<content>
summary:
This work presents a convolutional text classifier which is certifiably robust to Levenshtein-distance perturbations.

strengths:
Overall, this work is a solid academic contribution, albeit with limited prospects for scalability.

1. 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.
2. The paper writing is clean and structurally sensible. The problem setting is well-motivated and the necessary prior work is precisely and clearly introduced.
3. Figure and table presentation is thoughtful -- I appreciate the coordinated highlighting between Table 2 and Table 3.
4. Method runtime is orders of magnitude faster than baselines; this is expected as the Lipschitzness constant is enforced by construction.
5. 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.
2. 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.
3. 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.
4. 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). 
 
[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

questions:
1. To confirm: Theorem 4.3 holds for any choice of $p$ and $r$ which satisfy $1/p + 1/r = 1$?
2. 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).
3. 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.
4. 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.

Minor notes:
1. "English" on line 92 should be capitalized.
2. 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)$.

[1] Zou, Andy, et al. "Universal and transferable adversarial attacks on aligned language models." arXiv preprint arXiv:2307.15043 (2023).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730623752326

thread_type:
official_review

<thread_object>
creator: reviewer_mjg7

<content>
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.

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.
2. The proposed solution is interesting, efficient, and simple. This is a major advantage of this paper compared with prior approaches.
3. 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?

Reference: [Zhang et al. 2022] Rethinking lipschitz neural networks and certified robustness: A boolean function perspective. NeurIPS 2022.

2. 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.

questions:
1. Why on FakeNews dataset LipsLev has exactly the same performance as IBP when the Levenshtein distance is 1?

Miscellaneous:
1. Line 108: $s_i$ should be $S_i$?
2. Line 240: $\mathbb R^{m+(q-1)\times d}$ should be $\mathbb R^{m+2(q-1)\times d}$?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730715993294

thread_type:
official_review

<thread_object>
creator: reviewer_39zs

<content>
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).
In NLP, the Levenshtein distance is a natural way to measure the distance between two strings.
Existing verification approaches, that often rely on interval bound propagation (IBP), are however prohibitively expensive when using the Levenshtein distance to measure robustness radia.
To 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.
For 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.
Compared 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.
Remarkably, the proposed method is the only one which can provide robustness guarantees for a Levenshtein distance of 2.

strengths:
The authors address an interesting problem in NLP, which is of great relevance given the prevalence, and related risks, of large language models.
From a wider perspective, it is important to devise techniques to provide robustness certifications which are practically computable.
The paper has thus a strong motivation.
With respect to the approach, the paper clearly presents the limitations of existing techniques and orderly discusses the proposed solution.
The paper is well structured, and it seems sound and of potential practical relevance to me.

weaknesses:
**Relevance of ReLU-activated convolutional networks**

While 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.
Specifically, it is not clear how practically useful ReLU-activated, fully-connected convolutional networks are in text classification.
As 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.


**Definition of terms**

Some notions and terminology used require more explicit definition.
Firstly, Lipschitz continuity, as well as related concepts such as the "local Lipschitz constant", is never explicitly introduced.
As the paper heavily relies on these concepts, they should be introduced.
Similarly, the notions of "clean accuracy" and "verified accuracy" are not clearly defined. 
As these are used as the main performance metrics, they should be properly described as well.



**Empirical evaluation**

Related to my previous comment, further explanations on the behaviour of the clean accuracy for networks with more than one layer is necessary.
In figure S4, the clean accuracy drops significantly as more than 2 layers are used: why is this behaviour observed?


**Minor comments**

* line 52, of with -> with
* (several places) Related works -> related work

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?

* The approach you propose is sound, can you discuss completeness too?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731949679539

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
Dear reviewers,

We are thankful for the thorough reviews that helped us improved the quality of our work and for the positive comments. We are happy you enjoyed reading our work, recognized the efficiency of our approach and its potential. Here, we summarize our changes in the manuscript:

- **Empirical robustness evaluation with character-level attacks**

Following the suggestion of Reviewer U4sY, we have ran Charmer [1] with its standard hyperparameters, k=1 and k=2 for all datasets in Table 2. The results have been included in Table 2 and with standard deviations in Table S4. As expected, the Charmer adversarial accuracy is always above every verification method. We find that the gap between the Charmer adversarial accuracy and the LipsLev verified accuracy at $k=2$ is large for the AG-News, SST-2 and IMDB datasets. It is likely that this large gap is a combination of Charmer being a looser upper bound and LipsLev being a looser lower bound of the true rubust accuracy for $k=2$. Nevertheless, for the Fake-News dataset, the gap between the LipsLev verified accuracy and the Charmer verified accuracy is as close as $75.33$% v.s. $79.33$% for $p=1$.

- **Remarks regarding global and local Lipschitz constants**

Let us clarify the difference between global and local Lipschitz constants. We have included a detailed discussion on this topic in Appendix B.1. Here we present a small summary taking Remark 4.5 as an example.


Local Lipschitz constants are important as they can give tighter bounds when additional conditions are met. Note that the Lipschitz constant in Remark 4.5 ($M(\mathbf{E}, \mathbf{P})$) depends on $\mathbf{P}$. Therefore, even though the bound holds for any $\mathbf{P}, \mathbf{Q}$, the specific constant $M(\mathbf{E}, \mathbf{P})$ might not be valid for another pair of sentences $\mathbf{P}', \mathbf{Q}'$, i.e., it could exist some $\mathbf{P}', \mathbf{Q}'$ so that
$$
    d_{\text{ERP}}(\mathbf{P}'\mathbf{E}, \mathbf{Q}'\mathbf{E}) > M(\mathbf{E}, \mathbf{P})\cdot d_{\text{Lev}}(\mathbf{P}', \mathbf{Q}')\,.
$$
That is why $M(\mathbf{E})$ and $M(\mathbf{E}, \mathbf{P})$ are the global and local Lipschitz constants respectively, with $M(\mathbf{E}) \geq M(\mathbf{E}, \mathbf{P})$. While $M(\mathbf{E})$ is looser, it is valid for any $\mathbf{P}$. In practice, $M(\mathbf{E}, \mathbf{P})$ can be computed with little overhead while doing the forward pass of $\mathbf{P}$ through the model. Therefore, local Lipschitz constants of the model can be computed for every sentence in the dataset.

- **Definitions of Clean, Adversarial and Verified accuracy**

Following the suggestion of Reviewer 39zs, we have defined these three terms in Appendix A.1. 

- **Correction of typos**

Reviewers pointed out some typos and notation ambiguities that have been corrected in the text.

We have included all of the differences between the original submission and the rebuttal updates in blue color to ease up the reading. We remain available for discussion in case reviewers have remaining concerns.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This work proposes a convolutional text classifier which can provide certified robustness under Levenshtein distance.
Reviewers considered this a strong work — the problem is well-motivated and the technical methods overcome challenges from prior work. The proof involves bounding the Lipschitz constant of a network, and requires careful relaxations and estimates to handle the Levenshtein distance. The certificate is deterministic, in contrast to many other robustness certificates which are inherently randomized.
All reviewers recommend this for acceptance, and I agree.