Certifiably Robust Transformers with 1-Lipschitz Self-Attention
Authors: Xiaojun Xu
Linyi Li
Yu Cheng
Subhabrata Mukherjee
Ahmed Hassan Awadallah
Bo Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: Certified robustness
Transformers

Abstract: Recent works have shown that neural networks with Lipschitz constraints will lead to high adversarial robustness. In this work, we propose the first One-Lipschitz Self-Attention (OLSA) mechanism for Transformer models. In particular, we first orthogonalize all the linear operations in the self-attention mechanism. We then bound the overall Lipschitz constant by aggregating the Lipschitz of each element in the softmax with weighted sum. Based on the proposed self-attention mechanism, we construct an OLSA Transformer to achieve model deterministic certified robustness. We evaluate our model on multiple natural language processing (NLP) tasks and show that it outperforms existing certification on Transformers, especially for models with multiple layers. As an example, for 3-layer Transformers we achieve an ℓ2 deterministic certified robustness radius of 1.733 and 0.979 on the word embedding space for the Yelp and SST dataset, while the existing SOTA certification baseline of the same embedding space can only achieve 0.061 and 0.110. In addition, our certification is significantly more efficient than previous works, since we only need the output logits and Lipschitz constant for certification. We also fine-tune our OLSA Transformer as a downstream classifier of a pre-trained BERT model and show that it achieves significantly higher certified robustness on BERT embedding space compared with previous works (e.g. from 0.071 to 0.368 on the QQP datasets).

Under review as a conference paper at ICLR 2023
CERTIFIABLY ROBUST TRANSFORMERS WITH 1- LIPSCHITZ SELF-ATTENTION
Anonymous authors Paper under double-blind review
ABSTRACT
Recent works have shown that neural networks with Lipschitz constraints will lead to high adversarial robustness. In this work, we propose the first One-Lipschitz Self-Attention (OLSA) mechanism for Transformer models. In particular, we first orthogonalize all the linear operations in the self-attention mechanism. We then bound the overall Lipschitz constant by aggregating the Lipschitz of each element in the softmax with weighted sum. Based on the proposed self-attention mechanism, we construct an OLSA Transformer to achieve model deterministic certified robustness. We evaluate our model on multiple natural language processing (NLP) tasks and show that outperforms existing certification on Transformers, especially for models with multiple layers. As example, for 3-layer Transformers we achieve an f2 deterministic certified robustness radius of 1.733 and 0.979 on the word embedding space for the Yelp and SST dataset, while the existing SOTA certification baseline of the same embedding space can only achieve 0.061 and 0.1 In addition, our certification significantly more efficient than previous works, since we only need the output logits and Lipschitz constant for certification. We also fine-tune our OLSA Transformer as downstream classifier of pre- pre-trained BERT model and show that it achieves significantly higher certified robustness on BERT embedding space compared with previous works (e.g. from 0.071 0.368 on the QQP dataset).
INTRODUCTION
Deep neural networks (DNNs) have been widely applied different domains in recent years, including face recognition (He et al. 2016). machine translation (Bahdanau et al.) (014). and recommendation systems (Zhang et al., 2019b Specifically, on natural language processing (NLP) tasks, Transformer models (Vaswani et al., 2017) have been proposed and achieved outstanding performance on a variety tasks. Despite its impressive performance, people have shown that these NLP models suffer from adversarial attacks (Zhang et al. 2020). where adversary intentionally inject unnoticcable perturbations on the inputs to fool the model to provide incorrect predictions. Several works have been proposed to improve the empirical robustness of Transformers (Alzantot) jet al. 2018), but few have studied its certified robustness, i.e. theoretically guarantee that the model will not be attacked under certain conditions (e.g. within some perturbation range). Recently, Shi ct al. (2020) proposes to rely on -oudd-poopagtionn techniques to derive certified robustness for Transtormers, which leads to a relatively loose bound and cannot certify on deep models given the looseness induced by propagating from each component in the attention.
In this work. we propose a One-Lipschitz Self-Attention (OLSA) algorithm which provides robustness certificate for Transformers by bounding the Lipschitz constant of the model. The Lipschitz constant of model naturally related to robustness, as both require that model's output should not change much when the input slightly changes. Previous works (Tsuzuku et al.] 2018 Singla and Feizi 202 have investigated the I-Lipschitz property on fully-connected and convolution neural networks, but the study of I-Lipschitz on Transformer remains unexplored as its complicated non-linear self- olff-attention mechanism are difficult to analyze and constrain. Thus, in this work, we will propose the first 1 l-Lisschitz Transformer network which allows us achieve tighter deterministic certified robustness against adversarial attacks under different settings (c.g., training from scratch and fine-tuning).

---

Under review as a conference paper at ICLR 2023
In order to bound the Lipschitz of a self-attention layer, will first enforce all the linear operations (keys, queries, values) to be orthogonal via re- re-parametrization techniques (Huang et al. (020). Next, we will upper bound the input norm by normalizing the word embedding layer. As result, we will be able to bound the overall Lipschitz. by aggregating the change on each component of the softmax weighted sum. Finally,
add scaling factors ensure 1-L.ipcchitzeess of the OLSA layer. In addition, we also bound the Lipschitz of the pooling layer and aggregate the component to get the final OLSA Transformer classification model.
We evaluate our OLSA Transformer model under both traii--fromscrracch and fide--tum fine-tuning scenarios. In both settings, we show that OLSA achieves significantly higher certified robustness compared with existing bound- proudddapagationn based methods (Shi et al. (2200). The improvement is larger, especially on deeper models. For example, 3-layer Transformer OLSA Transformer achieves an average certified radius of 1.733 on Yelp, while previous works can only achieve 0.061 under the train-from- scratch setting. When fine-tuning over a BERT pre-trained model, OLSA Transformer achieves radius of 0.071 the QQP dataset while previous works can only achieve 0.368. In addition, we show that our certification is 10,000x faster than previous approaches, since we do not need complicated bound propagation processes and only need one forward pass to perform the certification. Finally, we also evaluate different methods under adversarial attacks and show that OLSA achieves much higher empirical robustness than baselines well. Meanwhile, we acknowledge 1 to 2% performance drop on the clean accuracy for OLSA, as we impose the extra I-L-pschitzz constraint which limits the model expressiveness slightly.
Technical contributions, We summarize our contributions as follows:
We propose the first One-Lipschitz Self-Attention mechanism (OLSA) and prove its Lips- chitz bound with corresponding analysis.
We evaluate the proposed OLSA Transformer model on various NLP tasks and observe that it outperforms the sate-offtheearr baselines. In particular, the performance gap is larger on deeper models (e.g on 3-layer Transformers on Yelp, we achieve over 25x average certified radius than previous works).
The OLSA model requires significantly less time certify the robustness radius as it only requires a forward pass to calculate the prediction gap.
2 RELATED WORK
Adversarial Robustness for NLP Models Existing works have shown that NLP models suffer from adversarial attacks (Zhang et al. 2019c 2020). Adversarial training-basse bbssed approaches have been proposed to enhance the model robustness during training (Alzantot al. 2018). In particular, Ren et al.] propose to generate adversarial examples with word saliency information. To improve the efficiency adversarial training, WWang et al.) propose a fast gradient projection method. Besides these empirical robustness algorithms, different approaches have been proposed to provide certified robustness on NLP models with smoothing techniques (Ye et al. 2020 Wang et al., 2021a) or bound- propagation techniques (Ji et al.) 2019 Shi et al.) 2020)) However, the smoothing techniques cannot provide deterministic certification, while the bound propaagatoiooon techniques are relatively loose and cannot certify for deep models. Recently, (Xu et al. (020)) also proposes bound- poodd-prrootnnaaaasssseess technique for NLP models. Their certification is against word substitution attacks and does not directly apply to our scenario.
Lipschite-constraince Models and Certified Robustness The Supschitz-constraimn models have been studied for their smoothness and robustness; however, existing works all focus on constraining the Lipschitz constant for fully-connected and convolutional neural networks. Tsuzuku et al. (2018) first bridges the Lipschitz constant of a network with its robustness and propose a Lipschitz-relater loss to improve model robustness. In order to achieve I-Lipschitzness, multiple works (Cisse et al. 2017 Miyato et al. 2018 Qian and Wegman 2018) propose to regularize the spectral norm of the linear matrices for fully fully-connected layers so that the Lipschitz constant is smaller than 1. For convolution neural networks, simple approach is applied unroll the convolution into an equivalent linear layer, but this is shown to have a loose Lipschitz bound (Wang et al., 2020). Recent works (Li et al. 2019 Trockman and Kolter 2021 (ingla and Feizi 2021) have proposed to directly parametrize
2

---

Under review as a conference paper at ICLR 2023
I-Lipschitz convolutional neural network which achieves good certified robustness on vision tasks. In addition, existing activation functions such as ReLU are shown not suitable for the 1-Lipschitz models, and better activation functions such GroupSort (Anil al. 2019) and Houscholder (Singla et al., 2021) are proposed. Kim et al. (202T) indeed focuses on the L. Lipschitz constant of Transformer models. They propose to use l distance instead of multiplication in the attention mechanism and show that the Lipschitz constant of such variant can be bounded. However, they aim to analyze and provide a (not necessarily tight) upper bound of the Transformer model, but propose construction methods for models with small Lipschitz constants.
3 BACKGROUND
3.1 I-LIPSCHITZ NEURAL NETWORKS AND CERTIFIED ROBUSTNESS
In this work, we focus on the Lipschitz measured under f2-norm. We define the Lipschitz constant of function f f 1 + R" as:
Lip(f) = sup [lf(x) f(x')l2
Vx, E Rm.
2 x2112
We can observe that the Lipschitz property of neural network naturally related with its ro- bustness property both require that the model output should not change much when the input changes by a certain magnitude. Specifically, If we define the prediction margin f on a cer- tain input x by My(a)) = max; f((x); maxg max, f(x), f(x) where f(z);; refers to the indexing operation, then we can guarantee that fxx will not change its output class within ra- dius x ='1 x'| < (M(x)/(V2Lipp((
Therefore, people have proposed to enforce I-Lipschitz for models to achieve robustness. Note that the Lipschitz of a composed function f a g satisfies Lip(f g) S Lip())) As result, we can upper bound the Lipschitz of model by bounding the Lipschitz each layer in the neural networks.
3.2 ORTHOGONAL LINEAR LAYER IN DNNS
Consider a linear layer y = Wr v where x E RT, W E RR and E R", People have proposed stronger constraint ensure the I-Lipschitz property: require that W is orthogona The orthogonality not only guarantees that the layer is 1 I-Lipschitz but also ensures that the gradient norm preserved during the backward pass, which helps with the training stability (Anil al. 2019). Several works have proposed re-parametrization techniques to achieve an orthogonal linear layer. For instance, Huang et al. propose to parametrize the orthogonal matrix W with an unconstrained matrix V R2xm by W (VVT)- V, where the inverse square root can be calculated by Newton's iteration. In practice, observe that the following Newton's iteration (Lin and Maji 2017) achieves a more stable result in calculating the inverse square root, given Yo- VVT and Zu I:
1 - Y1+1 ; -2 ZxYYk)
Zx+1
2
(31 Zz Zzn
Z will converge quadratically to (VVT)- when I|VVT- -|12 < which in practice is achieved by scaling the parameter V to be small.
Existing works focus on constraining the Lipschitz constant on such linear operation or convolution operation (which is type of linear operator in a more compact form). However, no one has studied the Lipsehitz property of the self-attention mechanism which a non-linear function. The focus of this paper is to construct the first I-Lipschitz Transformer model, which we will introduce next.
Strictly speaking, we require W to be ooti-ortl when n a m, which means either WWT or WT
3

---

Under review as a conference paper at ICLR 2023
4 ONE-LIPSCHITZ SELF-ATTENTION (OLSA) TRANSFORMER
As we can see, the property of 1-Lipschitz for neural networks can improve model smoothness and provide certified robustness. However, is often challenging to enforce the Lipschitz constraint while maintaining a good model capacity. In this section, we will introduce the first I-Lipschitz Transformer One-L.ipschizz Self-Attention (OLSA) Transformer. We will first introduce the Lipschitz property in a self-attention layer with sequential input and output. Then we introduce how we achieve Lipschitzness for self-attention layers and pooling layers. Finally, compose these layers and construct the I-Lipschitz Transformer model.
4.1 LIPSCHITZ PROPERTY SELF-ATTENTIN PIPELINE
First, we describe the setting of the self-attention pipeline follows. Suppose we have a sequence of imput X & [21, P2,,,,........
where zę IR The self-attention pipeline can be formalized function F : Rxd -> N. where the output Y (2,. UN F(X). Under this setting,
we define the Lipschitz of the pipeline based on the overall changes in the input sequence:
Definition 4.1. Given X [xi, 22, (2, [NN] and y
uNN = F(X), we define the
Lipschitz of the function as:
| - Y |X
Lip(F) sup T.
sup X,X'
X
where ||
|| denotes the Frobenius norm of matrix.
We can see that such definition Lipschitz considers the overall potential changes within the input sequence. We aim to bound such Lipschitz constant of the overall model so that we can provide certified robustness for the model against perturbations on the input sequence.
4.2 ONE-LIPSCHITZ SELF-ATTNN (OLSA) LAYER
The standard self-attention mechanism Y F(X) in Transformer with input ''s and output y; can be formalized as:
8i (W²x))(W*>))
Vd
Pij softmax([san 8:2 ................................ smn))s
= Eps x,)
In order achieve tight bound of the Lipschitz constant, will make two changes the pipeline. First, we use additive attention instead of dot-product attention in order to provide a tighter bound. As shown /Vaswani et al. (0177, these two mechanisms do differ lot in performance. Second, we add two scaling factors and ag to control the Lipschitz of the model. The modified self-attention mechanism Y F(X) as follows:
1 (WS o
Wº xx + WK Iz
Súj a1
2
Pij softmax 8:2..... 812 ,in)))))
smn))s
Σ Piy (WV xy))
y/ a2
where (-) denotes some non-linear activation function. After we consider the multi-head mechanism with H headers, the final OL-SA layer will be defined as follows:
4

---

Under review as a conference paper at ICLR 2023
Definition 4.2 (OLSA layer). Given X RNd, the OLSA layer F RNxd + Rxd with H headers is calculated by:
A 1
W 24 + WT, xz
3 ( a
2
Pú softmax (5/)) $/2:..., s/uls
1
(W 24)
a2
y Concat ..... yi "I)
where {(W W W W W W E ERAx xd
1 are model parameters in which W
I x df
and
For this mechanism, we can provide the following Lipschitz bound under the assumption that the linear transformations W's are orthogonal and the input norm is bounded.
Theorem 4.1 (Lipschitz bound of OLSA layer). Let w = Concar([W ,..... wH) Rdddd denote the concatenated parameters of W 's; and WK and WV are defined similarly. Assume 1 for all h E {l....,H 3) a
1) W WK WV are orthogonal matrices; 2) [ 1-Lipschitz activation function; 4) the overall inpul norm is bounded by ||X S then the Lipschitz constant of the function is bounded by:
Lip(F) 1 (1+
evn
02
4xr
where n is the length of the input sequence.
The main idea of the proof is to assume a perturbation å on X, and gradually bound the perturbation from s/j 's to y4 ss. The main non-linen non-linearity comes from the calculation of v which multiplies the calculated attention score pi3 with the original input Ty. This can be bounded by considering the perturbation on both parts individually, noticing that the norm of both parts is bounded (v,; is the output of SoftMax so it is boun-bbunded;-.. zry 's norm is bounded in the assumption). The full proof of the theorem is shown in Appendix [A] We can observe that the Lipschitz bound of the layer is related to the input sequence length and the input norm bound. We will discuss how we control the input norm for each layer in Section 4.4
Remark. (1) We will train the orthogonal matrices parametrized with W = (VVT) iV with Newton's 's iteration (Huang al. 2020). (2) We would like to get a I-Lipschitz layer such that the overall Lipschitz of the model is 1, and thus we will set Q22 + trainable parameter. Intuitively, on will control the trade-off between self self-attention expressiveness and linearity when a1 is very large, 02 will be close to 1 so that the expressiveness of the final output preserved, but šij will all be close to 0, so the attention becomes a simple averaging operation; when a is very small, the attention mechanism will work well, but the final output will be divided by a large a22 so the expressiveness final output is limited.
e (3) We will set on to
4cm
Comparison with the Lipschitz bound in (Kim et al. 2021) In (Kim et al. 2021), the authors also propose variant of the Transformer L22MHA and upper bounded its Lipschitz constant with a = VN (N 1) + 1) J(W where J(W) is some term related to the spectral norm of W and Φ (N) grows slower than Olog N). Note that they only provide an upper bound of the Lipschitz and do not constrain it to be small. We may also get I-Lipschitz model using their bound by orthogonalizing their weight matrices (such that (WW = 1) and re-scaling the output with 1/a. Theoretically, this bound ((VN log N) which is slightly favored than our bound O(N N 5 However,
II (im 2021 Theorem 3.2), the hound has factor Vatn
but this factor comes from the fact that
they divide their output F(X) with v d//H. For fair comparison, do consider this scaling factor the output (which is 02 in our case).
*Our bound + e/N is O(N) because we view the embedding norm each location ||æs||a be similar,
the input bound ||||| also O(VN).
5

---

Under review as a conference paper at ICLR 2023
our bound has significantly smaller constant factors than theirs, as observe the factor of in their bound and the factor of 1 in ours. As an example, under a popular case N = 20 and input norm is bounded to ||æi|2 = 1, their bound is VN 1) +) 32.28, while our bound 1+ eyN 6.0. Therefore, we can actually provide a tighter Lipschitz guarantee and robustness certification in practice. We include the comparison of using this bound to construct I-Lipschitz Transformers in Appendix D and observe that OLSA can indeed achieve higher certified robustness than directly adapting (Kim et al. 2021 for certification.
4.3 LIPSCHITZ POOLING LAYER
In many tasks, we need a pooling layer after several self-attention mechanisms in order to get a final embedding vector for the entire sequence: Raad - Rdd. The popular approach in standard self-attention layers is to add an extra output token into the sequence and use the embedding of that token for the overall sequence. We intuitively find this approach "waste of resource" in the 1-Lipschitz case only one token value is used for pooling while others are dropped, while such information usually important to achieve a tight bound. In practice, we propose to use the average of all the embeddings of the pooling layer, i.c. G(X) good Lipschitz properties:
E, Hy. We show that this approach has
Theorem 4.2. For the pooling function G(X) NV E T4, we have:
Lip(G)= S
VN
See Appendix B for the proof. Thus, can further multiply factor of VN to get I-Lipschitz pooling layer and maximize the output expressiveness. The resulting pooling layer is:
G(X) =
24
VN
4.4 OVERALL OLSA TRANSFORMER
Aggregating different layers introduced above, we can construct the overall OLSA Transformer, which consists of one word embedding layer, several OLSA layers, one pooling layer and a final linear layer f Ed R for prediction, where is the number of classes. However, there are still some challenges in constructing the OLSA Transformer. The first challenge is how to bound the input norm for each self-attention layer. Note that, the norm of the output layer of self-attention layers will not increase, since it is weighted average of all the processed input divided by factor a2 > Therefore, the norm each layer can be bounded as long as the input to the first layer is bounded. Thus, we will normalize the embedding vector for each token with norm c, that the input to each self-attention layer satisfies || VNc. The second challenge is how to simulate other components with I-Lipschitz constraint standard Transformer. We will remove the LayerNorm and Dropout layers and use the average y 0.5x + 0z5f(z) instead of the residual addition connections. We use GroupSort (Anil et al. 2019) as the activation function which is shown to work better than ReLU in 1-Lipschitz networks.
Let T : R Xxd - R denote the OLSA Transformer classification model. We can calculate the certified radius on given input X with T(X) and Lip(T). In particular, can certify that the model prediction will not change within ||X - X'| < where:
max, T(X); m max, T(x), T(X),
V2Lip(T)
Comparison with the certification in (Shi et al. 2020) As the best existing work on robustness certification for Transformers, (Shi et al.) 2020) provides certification assuming that only one two words are perturbed by the adversary. In particular, in their &, certification, they provide certificates that the prediction will not change within ||X X'Ile r, but with the restriction that X' differs with X on only one or two positions of word embedding. Therefore, our work provides a more generalized &g certification. In addition, explicitly impose the 1-Lipschitz constraint during

---

Under review as a conference paper at ICLR 2023
training, and therefore the model is optimized to have better certification radius; by comparison, they will directly certify on a vanilla-trainee model, so their certification might not be tight, especially for relatively deep models.
EVALUATION
In this section, we compare our OLSA Transformer with the state-of-the-art baseline on different datasets under different settings. We observe that model achieves much higher certified robustness under both train-from-scratth and fine-tuning scenarios. In addition, OLSA is much more efficient during the certification process. We also evaluate our model against the empirical attacks and observe that OLSA also enhances the model empirical robustness.
5.1 EXPERIMENTAL SETUP
Dataset We consider three datasets in our evaluation: Yelp (Zhang et al., 2015). SST (Socher et al. 2013) and QQP (Wang al. 2018). Yelp consists of 560, (00,00003800000 000 examples in the training/test set; SST consists of 7..349/872/1.88
examples in the training/developmennrer set; QQP consists of 363, (63,846/40,430 examples in the training/test set. Each example in Yelp and SST is sentence labelled with binary class for its sentiment; each example in QQP consists of two quora questions and labelled with a binary value on whether the two questions are equivalent.
Implementation Details We train and evaluate our 1-Lipschitz OLSA Transformer under both train- from-scratch and fine-tuning scenarios. In the sain-from-scratch scenario, we randomly initialize the model and word embeddings and train it from scratch. In the fine-tuning scenario, we pre-trained BERT model (Devlin et al. 2018) and use its output for a downstream OLSA Transformer model. The BERT model is kept unchanged and we only train the downstream model. In the train-from-scralt scratch setting, we use the Yelp and SST datasets which are also adopted in the baseline (Shi et al. 2020). We consider N N-layer models (N S 3) and normalize the word embedding and position embedding to norm of 2. so that the overall input norm is bounded by ||>; l| S 4. For the fine-tuning setting, we evaluate on Yelp, SST and QQP datasets. We normalize the output BERT to norm of 2 and use our OLSA Transformer as the downstream model. For both settings, we use the number of attention heads 8 and hidden dimension 256. We train the model with batch size 32 for 50 epochs on SST and 10 epochs on Yelp. For QQP at the 40-th epoch. We include certificate regularizer loss (Singla et al. 2021 which adds a term
Adam optimizer with learning rate 10 and decays by 0.1
-RReLU Twx), max.gy T(x),
to maximize the prediction margin with a gradually increasing ?
V2
with final value 2.0 for the train-from fwo----ooooooeee scrmscc case. We use = 0.0 in the fine-tuning scenario as the margin is already large. We will not orthogonalize the final prediction layer; instead, we calculate its Lipschitz and include it in the final certification. For the evaluation time, we compare the time to certify one batch evaluated on an RTX 3090 GPU.
Baselines There are few baselines the certifiable robustness of Transformer models and (Shi) et al. (020) achieved state-of-the-ee certification results. Their model is trained using the standard architecture and training algorithm. We will fix the word embedding be the same in our model to perform a fair comparison. To certify the robustness within the region, they propose a bound propagation-basee method that tightly bounds the cross-position dependency in the attention mechanism. They evaluate the certification on Yelp and SST datasets on which we will make the comparison and will also evaluate it on the QQP dataset. Note that since the certification time of their approach is slow, we will only evaluate on sampled test set with 5% instances for Yelp and QQP and. The comparison with the Lipschitz bound in Kim et al. (2021) shown in Appendix [ where adapt their bound to construct the I-Lipschitz model and observe that our bound provides better robustness guarantee.
To evaluate the certified robustness, we use the certified radius as the metric following the setting in (Sh et al., 2020). Given model and input X E Nxd on the word embedding space, the certified radius is defined the maximum perturbation radius within which
Evaluation Metrics
7

---

Under review as a conference paper at ICLR 2023
Table I: Certified radius of OL.SA and previous state-of-the-art in the train-from-scratch scenario. The certification time is evaluated on batch of test data.
Vanilla Accuracy
Certified radius
Certification Time (sec)
Robust Accuracy under
Dataset
Depth
Approach
6 6r-GGD@e 1.0
Shi et al.
89.1 %
0.476
676.8
33.5%
OLSA
87.7%
1.995
0.060
61.2 %
Shi et al.
90.3%
0.126
1164.2
26.0%
Yelp
OLSA
88.0%
1.845
0.078
59.7% %
Shi et al.
90.2% %
0.061
1470.7
21.5%
OLSA
88.1% 1%
1.733
0.105
60.1 %
Shi et al.
81.9%
0.923
627.8
33.1% 13.
OLSA
80.9%
1.146
0.021
54.3 %
Shi et al.
82.5%
0.429
1056.0
33.4%
SST
2
OLSA
81.1%
1.053
0.036
53.1 %
Shi et al.
82.5%
0.110
1807.7
34.9%
3
OLSA
81.2%
0.979
0.049
52.3% %
Shi et al.
78.8%
0.193
1527.0
6.9%
OLSA
76.8%
2.535
0.022
51.5% %
Shi et al.
79.4%
0.083
3165.2
8.6%
QQP
OLSA
76.6%
2.383
0.037
52.6 %
Shi et al.
79.5%
0.064
4782,
7.1%
OLSA
77.0%
2.116
0.054
47.3%
can guarantee that the model prediction will not be changed:
Rad X) sup s.t. T(X) T(X) VIX
X'I Sr
and we calculate the average certified radius over the test dataset.
5.2 TRAINING OLSA FROM SCRATCH
We show the results of certification on the -rai--hrom-scratch model in Table 1 We observe that our OLSA model indeed achieves higher certified robustness compared with Shi et al., especially on deeper layers. We owe to the reason that the OLSA network trained to achieve a tight Lipschitz bound and therefore more robust; by comparison, (Sh et al. verify on the vanilla model and therefore cannot guarantee tight bound for each layer. Note that we cannot directly use our certification method to certify their model given that their models do not satisfy 1- 1-Lipschitz so the bound will be very loose. As a cost of improved certified robustness, our models suffer from a 1% 2% vanilla accuracy drop compared with the vanilla (no regularization) model. We think this is an inevitable performance drop, as shown in previous works (Zhang al., 2019a) that there exists a trade-off between vanilla accuracy and robustness when comparing vanilla and adversarially robust models. As for the certification time, we can observe that our certification is over 10,000 times faster than previous works. This is because we only need one forward pass calculate the prediction gap for certification; by comparison, (hh et al. (2020) needs to do a binary search and hound-propagent on each location of the input, which leads to large number of forward passes.
Besides the certified accuracy, we also perform lg PGD attack (Madry et al. 2017) against models over the word embedding space check their empirical robustness as shown in Table We see that OLSA indeed achieves much higher empirical robustness compared with vanilla models. This confirms that enforcing the I-Lipschitz constraint indeed helps with the model robustness.
Empirical robustness
Ablation studies Different y The y in the certificate regularizer loss can control the tradeoff between vanilla accuracy and certified radius with larger 7, the model is trained to have larger
8

---

Under review as a conference paper at ICLR 2023
Table 2: Ablation study of 1-layer OLSA Transformer with different in the certificate regularizer.
Vanilla Accuracy
Certified
Robust Accuracy under
Dataset
Approach
Eg-PGD @ 1.0 radius
Shi et al.
89.1%
0.476
33.5%
0.2
90.2%
1.009
53.4%
Yelp
0.5
89.9%
1.274
63.3%
OLSA
1.0
89.0%
1.606
68.0% %
2.0
87.7%
1.995
61.2%
5.0
84.5%
2.768
50.9%
Table 3: Certified radius of 1-layer OLSA and previous wrate-of-the-are in the fine-tuning scenario, where we keep the pre-trained BERT model unchanged and only tune the downstream model.
Vanilla Accuracy
Certified radius
Robust Accuracy under
Dataset
Approach
b--PGD@c 1.0
Shi et al.
93.0%
0.169
59.2%
Yelp (fine-tuning)
OLSA
90.8%
0.613
84.4% %
Shi et al. OLSA
88.0%
0.367
52.5%
SST (fine-tuning)
86.2%
0.475
76.8% %
Shi et al. OLSA
83.7 %
0.071
26.2%
QQP (fine-tuning)
81.6%
0.368
66.8 %
output prediction gap and thus larger certified radius, at cost of vanilla accuracy. In Table 2 we show the performance of varying the value of 7. From the tables, we can indeed observe the trade-off between vanilla accuracy and certified radius. In particular, even with small y we can still achieve a large certified radius, while larger provides a higher certification result. We set 7 = 2.0 as a reasonable choice for the trade-off. Interestingly, the best empirical robustness achieved at some intermediate value of This may be because empirical robustness is not always aligned with certified radius and may be affected by the drop of vanilla accuracy.
5.3 FINE-TUNING OLSA OVER PRETRAINED BERT
We show the certified robustness in the fine-tuning scenario in Table 3 The certified robustness computed over the BERT output embedding space. We mainly evaluate the 1-layer case as is uncommon use multi-layer Transformers on top of BERT for downstream tasks (although expect a larger performance gap for those models). We can see that our OLSA model again achieves larger certified radius on all three tasks small cost of vanilla accuracy. Also, OLSA achieves higher empirical robustness compared with vanilla models. These results show that our OLSA model can applied in both train-rrom-t from-scratch and fine-tuning scenarios to enhance model robustness. We provide the training curve in Appendix [F] In addition, we evaluate the model robustness on PAWS-QQP (Zhang et al., 2019c), an adversarial dataset QQP, and also observe that OLSA achieves high empirical robustness, as we show in Appendix
6 CONCLUSION
In this paper, we propose OLSA, the first I-Lipschitz self-attention mechanism for sequential input. Based on OLSA layer and 1-Lipschitz pooling, we propose first 1-Lipschitz Transformer model for NLP classification tasks. We show that OLSA Transformer is able to achieve the state-of-thed the-art certified robustness on various tasks under both veii--fromsscree and fine-tuning scenarios. Our certification is also significantly more efficient. We believe this work will provide new research direction toward certifiably robust language models.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Moustafa Alzantot, Yash Sharma, Ahmed Elgohary. Bo-Jhang Ho, Mani Srivastava, and Kai- Wei Chang. Generating natural language adversarial examples. arXiv preprint arXiv:/804 004.07998, 2018.
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In International Conference on Machine Learning, pages 29 291-301. PMLR, 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. arXiv preprint 0400:::/40900475 2014.
Gregory Bonaert, Dimitar Dimitrov, Maximilian Baader, and Martin Vechev. Fast and precise certification of transformers. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pages 466-481, 2021.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. International Conference on Machine Learning, pages 854-863. PMLR, 2017.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Ming-Wei
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Lei Huang. Li Liu, Fan Zhu, Diwen Wan, Zehuan Yuan, Bo Li, and Ling Shao. Controllable orthogonalization in training dnns. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pages 6429-6438 2020.
Robin Jia, Aditi Raghunathan, Kerem Göksel, and Percy Liang. Certified robustness to adversarial word substitutions. arXiv preprint
2019.
Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention. In International Conference on Machine Learning, pages 5562-5571. PMLR, 2021.
Qiyang Li. Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jöm-Henrik Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. Advances in neural information processing systems, 32, 2019.
Tsung- Yu Lin and Subhransu Maji. Improved bilinear pooling with cnns. arXiv:1707.06772, 2017.
arXiv preprint
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.0608 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv: /rXi::/802.0597. 2018.
Haifeng Qian and Mark N Wegman. 12-nonexpansive neural networks. arXiv preprint
arXiv:1802.07884 07000.07796... 2018.
Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. Generating natural language adversarial examples through probability weighted word saliency. In Proceedings of the 57th annual meeting of the association for computational linguistics, pages 1085-1097, 2019.
Zhouxing Shi, Huan Zhang, Kai-Wei Chang, Minlie Huang, and Cho-Jui Hsieh. Robustness verifi- cation for transformers. In International Conference on Learning Representations, 2020. URL
https::/opeereviii net /tt.:eeettouureee ForummiddBBxwwddeoe De
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In International Conference on Machine Learning, pages 9756-9766. PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2023
Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness cifar- 10 and lifar-100. In International Conference on Learning Representations, 2021.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, pages 1631-1642, 2013.
Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. arXiv preprint arXiv:2104.07167, 2021.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. Advances in neural information processing systems, 31, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.07461, 2018
Jiayun Wang, Yubei Chen, Rudrasis Chakraborty, and Stella X Yu. Orthogonal convolutional neural networks. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pages 11505-11515, 2020.
Wenjie Wang. Pengfei Tang, Jian Lou, and Li Xiong. Certified robustness to word substitution attack with differential privacy. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pages 1102-1112,
2021a.
Xiaosen Wang, Yichen Yang. Yihe Deng, and Kun He. Adversarial training with fast gradient projection method against synonym substitution based text attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 13997-14005, 2021b.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai- Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certi- fied robustness and beyond. Advances in Neural Information Processing Systems, 33:1 18:1129-1141, 2020.
Mao Ye, Chengyue Gong, and Qiang Liu. Safer: A structure-free approach for certified robustness to adversarial word substitutions. arXiv preprint 44X4 2020.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning. pages 7472-7482. PMLR, 2019a.
Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Computing Surveys (CSUR), 52(1):1-38, 2019b.
Wei Emma Zhang, Quan Z Sheng, Ahoud Alhazmi, and Chenliang Li. Adversarial attacks on deep-learning models in natural language processing: A survey. ACM Transactions on Intelligent Systems and Technology (TIST), 11(3):1-41, 2020.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
Yuan Zhang, Jason Baldridge, and Luheng He. Paws: Paraphrase adversaries from word scrambling. arXiv preprint arXiv: arXiv:1904.00 1904.0 130, 2019c.
11

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM 4.1
Proof. Consider two inputs X and X + AX, where ||X||F F S c, || and || S 8. We will use the symbol to denote the changes given and X +AX it does not lead to confusion. For example, AY F(X AX) F Our goal is to bound the difference at the output layer (AY| First, we will define the symbols for intermediate results as follows:
Q Concat([W1 X,
WHX E RRdx
W XJ) E NRd S [st]] E RNNN
K Concat ( X,
p p/1l E ERNNN
y WK X (NN(//H))
V Concat([Wy X,... W, X]) R
5rh phyh E Nx(dHH)
Now, are going to bound the difference Sh and A step-by-step.
||||| by considering the perturbations of AQ, AK,
Step 1
| S 6. | & 8 and ||V 6.
We can observe that Q 4 K W X and WV X. Since all matrices are orthogonal,
the linear operation is I-Lipschitz. Thus |QQ|e I || AX |F S and same for AK and AV.
Step2 2 En AS
6. a1
First, notice that the operation a I-Lipschitz since | 2l and is I-Lipschitz. Next, notice that every entry in Q and will appear N times among the calculation of all the s/. Therefore, the overall change of Eij.A (Asly) is N/((22))²) times the overall change of ||]Q| F and AK Fr. So:
N
V (2a,)² [||]|]++||A]]]]]]) ||))))))
VN
6
01
Step 3
Σn ||P
NN ta1
8.
This can be proved by noticing that the Lipschitz constant of a SoftMax function is 1.
Step 4
|| || < ||V*||r + |lIl
Note that the change of h comes from both 4 and ph and the inequality ||AB| |A I S || S |||]]|||B||> holds true. Therefore, have:
- ph APT (V" + +VV")
< 21P*)||/A'' + ||AP" 1 + AV"IlF
S ||V* + <clAp F
The last inequality comes from (1) ph is the matrix after SoftMax, so its spectral norm is no larger than I; (2) || AV* ||X + AX F < c since V comes from an orthogonal operation of X.
Step 5
|AY
r
1
N 40.
6
02
12

---

Under review as a conference paper at ICLR 2023
We notice that Y Concat([Y* ..... (".,,.,,"")).. In addition, we have inequality v (an + bn,)²
(v En of + En from Cauchy's inequality. Therefore, we have:
1
||Y|| F S
|AP^112
02
(IAVaIIE + c|AAP)lE))
022
||AV/11 +
E [(c||APA|1>) V
0/2
CVN N
5
(1
)o.
012
4a1
B PROOF OF THEOREM 4.2
Proof. Let ||AX||F VE
|
be the perturbation on the input. We have:
|
Ar
N
N
A
N
N
VN
where the last inequality is derived from the Cauchy's inequality.
C EVALUATION ON PAWS-QQP
Table 4: The results when we fine-tune on QQP and evaluate on the PAWS-QQP dataset.
Model
Shi al.
OLSA (y 0) OLSA (> 0.5)
OLSA (7 2.0)
Vanilla Ace
83.7%
81.6%
80.3%
75.4%
Robust Acc
40.9%
41.9%
50.8%
67.7%
We show the evaluation results where we fine-tun the model on QQP and evaluate on the adversarial dataset PAWS-QQP Zhang et al. (2019c) in Table 4 We can observe that OLSA model still achieves a better performance with arbitrary choice of 7. In particular, larger ? can provide better adversarial robustness, but it may hurt the vanilla accuracy.
D COMPARISON WITH (KIM ET AL.. 2021
We compare our bound with the one in (Kim et al. 2021 in Table 5 for the train www---foom--tttee scenario and Table the finetuning scenario, In particular, we will follow their L2-MHA pipeline and (1) orthogonalize all the linear matrices (2) divide the output by their Lipschitz constant bound in
13

---

Under review as a conference paper at ICLR 2023
Table 5: Comparison of certification on 1-Lipschitz model using Kim al. (202
Vanilla Accuracy
Certified radius
Dataset
Depth
Approach
Kim et
87.8%
1.048
OLSA
87.7%
1.995
Yelp
Kim et al.
87.6%
0.541
2
OLSA
88.0% %
1.845
Kim et al.
87.7%
0.272
3
OLSA
88.1
1.733
Kim et
80.8%
0.628
OLSA
80.9 %
1.146
SST
Kim al.
81.1%
0.324
2
OLSA
81.1 %
1.053
Kim et al.
80.7%
0.174
3
OLSA
81.2%
0.979
Kim et al.
76.2%
1.522
OLSA
76.8 %
2.535
QQP
Kim
76.0%
0.771
2
OLSA
76.6%
2.383
Kim et al.
75.6% 77.0%
0.413
3
OLSA
2.116
Table 6: Comparison of certification I-Lipschitz pretrained model using Kim et al. (202
Vanilla Accuracy
Certified radius
Dataset
Approach
Kim al. OL.A
88.6%
0.458
Yelp (finetuning)
90.8% %
0.613
Kim al. OLSA
85.8%
0.159
SST (finetuning)
86.2%
0.475
Kim al. OLSA
81.1%
0.251
QQP (finetuning)
81.6 %
0.368
14

---

Under review as a conference paper at ICLR 2023
Table 7: Certified radius of 1-layer OLSA and previous state-of-the-arts in the fine-tuning scenario, where we use the 11-layer BERT oulput for OLSA.
Vanilla
Certified radius
Robust Accuracy under
Dataset
Approach
Accuracy
E2-PGD@c 1.0
Shi et al.
93.0%
0.169
59.2%
Yelp (fine-tniig)
OLSA
90.9%
0.525
80.3 %
Shi et al. OLSA
88.0%
0.367
52.5%
SST (fine-tuning)
86.8%
0.410
73.4% %
Shi et al.
83.7 %
0.071
26.2%
QQP (fine-tuning)
OLSA
81.8%
0.329
60.4% %
Train-from-scracch
Train-from-scratch
Fine-tuning
Fine-tuning
1.0
1.0
1.5
Vanilla Accuracy
Certified Radlus
Vanilla Accuracy
Certified Radius
1.0
0.8
0.8
0.5
Train
Train
Train Test
Train
Test
Test
Test
0.0
7
Epoch
Epoch
Epoch
Epech
Figure 1: The curve of vanilla accuracy and certified radius of 1-layer OLSA on the Yelp dataset under froatscratch and fine-tuning settings.
order to get I-Lipschitz self-attention layer. Other settings follow the same way as OLSA. We can observe that our model achieves a larger certified radius as well as a vanilla model accuracy. This understandable as we discussed that our bound is tighter in practice.
E PERFORMANCE WITH DIFFERENT LAYERS OF BERT
In the previous evaluation, we use the standard 12-layer BERT architecture followed by downstream self-attention layer for fine-tuning, In Table show the results using the output of the 11-th layer in BERT and concatenate it with the downstream layer for finetuning. We view such architecture fair analogy of BERT, since it also consists of 12 layers in total. We can observe that there is slight performance drop compared with the original version, which is understandable as we are only using part of the pretrained BERT. Nevertheless, model still has good performance under such circumstance.
F TRAINING AND CERTIFICATION CURVE
We show the curve of vanilla accuracy and certified radius for the OLSA model on Yelp during training under both scenarios in Figure [ model can achieve good vanilla accuracy at early epochs, while the certified radius is gradually increased during the training process. Note that we have a gradually increasing 7 which may hurt vanilla accuracy, so the relatively stable accuracy indicates that the model is trained well. Second, we notice that the training and test performance trend is similar the I-Lipschitz constraint is strong regularizer on the model, and thus the model will not overfit on the training set which is desired.
We have two observations from the curves. First, the
G ABLATION STUDY
In Table 8 show the performance of the OLSA network with different features in the tranditional Transformers, including Dropout, ReLU and LayerNorm. In particular, 1) for dropout, we use the Py implementation where we randomly drop some neurons and scale up other neurons
15

---

Under review as a conference paper at ICLR 2023
during training, and perform identity transformation during evaluation; 2) for ReLU, replace all the GroupSort activation with ReLU activation; 3) for LayerNorm, we only include the bias term and not the variance term, which is also used in Shi al. 2020) We can observe that these features have little impact on the final model performance.
Table 8: The results of ablation study on the SST-2 dataset.
Approach
Vanilla Accuracy
Certified Radius
OLSA
80.9%
1.146
OLSA
80.7%
1.142
OLSA
80.5%
1.174
OLSA
80.9%
1.144
H
DEEPER MODELS
We provide the results with 4/5/6-layer Transformers on the SST-2 dataset as Table We can observe that model can still outperform Shi et al. 22020). In addition, the performance has slight drop as training deeper models on a single task usually cannot achieve good performance.
Table 9: The results of deeper models on SST-2 dataset.
Depth
Approach
Vanilla Accuracy
Certified Radius
Shi et
82.7%
0.068
OLSA
81.2%
0.919
Shi et al.
82.5%
0.036
OLSA
81.3%
0.867
Shi et al.
82.8%
0.021
6
OL.SA
81.2%
0.823
I EVALUATION ON ADVGLUE
In order to validate the empirical performance of our work, we evaluate our approach over the advGLUE Wang al. (2021b) dataset, which consists of adversarial examples on SST and QQP generated with different existing attacks. We show the results in Table We can observe that our approach indeed performs better these adversarially attacked datasets. These results show that Lipschitz is helpful in improving model robustness.
Table 10:
The accuracy on the advGLUE dataset.
advSST
advQQP
Shi et al.
37.8%
57.7%
OLSA
41.9%
59.0%
J COMPARISON WITH BONAERT ET AL.
As recent baseline, Bonaert al. 2021 improves over Shi al. (2020) to certify the robustness of
a Transformer with bounding propagation techniques. We evaluate their certification approach and provide the comparison of average certified radius in Table [1. Note that the models in this work
16

---

Under review as a conference paper at ICLR 2023
the same in Shi al. (2200, , so their vanilla accuracy is the same show in Table | We can observe that our approach still outperforms this work, since their approach still certifying the tunilla-raiined model which intrinsically does not have good robustness.
Table 11: The certified radius comparison vionert et al. on SST and Yelp datasets.
1-layer
2-layer
3-layer
Bonaert et al. SST
0.959
0.531
0.164
OLSA, SST
1.146
1.053
0.979
Bonaert et al. Yelp
0.875
0.317
0.204
OLSA, Yelp
1.995
1.845
1.733
17


Reviews:
[{"review_id": "keOM6GRn3q8", "reviewer": "Reviewer_QwhB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes OLSA, an algorithm to train transformers for 1-Lipschitzness in the l2 norm, which is directly linked to robustness to l2 perturbations. The authors show that OLSA attains stronger verified robustness than relevant previous work, at a minimal cost in standard accuracy.", "summary_of_the_review": "OLTA achieves state-of-the-art deterministic certified accuracy on transformers at a minimal cost in terms of standard accuracy. Nevertheless, the paper could benefit from a more recent baseline (see above), reporting and commenting on training runtimes, and an ablation study.", "strength_and_weaknesses": "OLTA achieves 1-Lipschitzness via a number of modifications to the standard training process. The authors enforce orthogonality in the self-attention layers (in their additive form), remove dropout and LayerNorm, and employ the GroupSort activation function. While each of the ideas was previously presented in the 1-Lipschitzness literature, this is the first application to training 1-Lipschitz transformers.\nIn spite of the modifications, the authors show that their method achieves larger certified robustness than the relevant previous work from Shi et al. 2020, with a minor cost in terms of standard accuracy. This is definitely a big strength of the work.\n\nNevertheless, I have the following comments/questions on the experimental section:\n- the authors should compare against the bounds from (Bonaert et al. 2021)[https://files.sri.inf.ethz.ch/website/papers/pldi21-transformers.pdf], which were shown to be more effective than those from Shi et al. 2020;\n- the speedup against previous certification methods is repeatedly stated. However, bounding algorithms do not necessarily require an ad-hoc training process, which might be more costly. Could the authors provide information on the training runtimes? What is the overhead of running the Newton's iteration?\n- it would be nice to present an ablation study of the non-standard components of the training process on standard accuracy. In other words, how does the use of GroupSort, the lack of dropout or LayerNorm, and the use of additive attention?\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Mb61ix2YgM", "reviewer": "Reviewer_XTXc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduces Lipschitz constraints into the transformer for higher adversarial robustness. The author proposes the first One-Lipschitz Self-Attention (OLSA) mechanism for Transformer models. The author orthogonalizes all linear operations in the self-attention mechanism and introduces Lipschitz constraints. The proposed method also provides certified guarantees. Experiments demonstrate the effectiveness of this method.", "summary_of_the_review": "We tend to accept this paper because the method is effective and the presentation is clear.", "strength_and_weaknesses": "Strength:\n1. This paper proposes the first One-Lipschitz Self-Attention mechanism (OLSA) and proves the Lipschitz bound.\n2. Because the prediction gap is only calculated on a forward pass in the OLSA model, the robustness radius can be certified in much less time.\n\nWeaknesses:\n1. Certified defense is usually divided into bound propagation and randomized smoothing (RS). The paper lacks a comparison with the RS method.\n2. The method is not evaluated on TectFooler, BERT-Attack and TextBugger.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BFVE7uFr3K", "reviewer": "Reviewer_UH8A", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes to use Lipschitz constraints to train certifiable robust transformers. With some modifications to the Transformers models, they bound the Lipschitz constant for each layer, which is related to the robustness of the model. Compared to previous work, their proposed model, named one-Lipschitz self-attention mechanism (OLSA) can achieve tighter bound (therefore larger robustness radius) as well as being more efficient, which is empirically verified on both training-from-scratch and fine-tuning scenarios.", "summary_of_the_review": "The model proposes a new method that guarantees the Lipschitz bound of the Transformer with a smaller robustness radius and efficient certifications. However, certain modifications to the Transformers are necessary under their settings, which could be harmful to its usefulness.", "strength_and_weaknesses": "Strengths:\n\n1. OLSA has advantages over its baseline, as it has a tighter Lipschitz bound (compared to Kim et al. (2021)) and requires only the forward pass (compared to Shi et al. (2020)). With those improvements, it achieves a higher robustness radius and gets faster than Shi et al. (2020), which is verified on two datasets in both training-from-scratch and fine-tuning scenarios.\n2. The modification OLSA makes to the Transformer model makes it easier to bound their 1-Lipschitz constant during training, which is well-designed and works well both theoretically and empirically.\n\nWeaknesses:\n\n1. While the changes on Transformers are necessary for the OLSA to achieve robustness, certain features in Transformers must be abandoned. E.g. only additive attention can be used, while most of the pre-trained transformers rely on the dot-product attention mechanism. LayerNorm is removed, which is important when many layers of transformers are stacked. Those changes might be acceptable for 3-layer transformers, but can be dangerous for larger models.\n2. Certain steps to bound the Lipschitz constant have dependencies on the sequence length, such as Theorem 4.1 and 4.2, which means the actual Lipschitz bound would differ for different lengths of the input sequences. \n\nTypo: In the last paragraph before the \"technical contributions\", the paper says OLSA Transformer achieves a radius of 0.071 ... previous work ... 0.368. Should it be 0.368 and 0.071?\n\nThe paper seems to use both n and N symbols to represent the sequence length. E.g. in Theorem 4.1 it uses \"n\" and the remark below 4.1 uses \"N\". Can you make them consistent? As a reference, N in Shi et al. represents the number of layers.\n\nQuestions\n\n1. I have a general question for this line of work: How is it practically useful to model defense? Lipschitz bound guarantees that the model is robust to slight changes in the embedding space, which is not naturally common in attacks. If one or two words are changed/added/deleted, the embeddings will be significantly changed, then how is Lipschitz helpful?\n2. Why do you put the comparison with Kim et al. (2021) in the appendix, and not show their efficiency?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7uLHGLH5VX3", "reviewer": "Reviewer_noPi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposed a new multi-head self-attention variant -- OLSA. The proposed method can satisfy the 1-Lipschitz constraint under certain conditions. Thus, the author further proposes a Lipschitz constrained Transformer model. The model achieves a strong certified radius and robust accuracy while maintaining a reasonable vanilla accuracy.", "summary_of_the_review": "Overall the paper proposed an interesting new variant of transformer that can easily satisfy the 1-Lipschitz constraint. The idea of building a robust transformer model could potentially have a big impact on many downstream tasks. However, the current method still has many limitations, especially since it's not compatible with some important components of SOTA models and its scalability is still unclear.", "strength_and_weaknesses": "Strength:\n1. The proposed method can achieve a strong certified radius and it is straightforward and easy to implement.\n2. The paper is well-written and easy to follow. The comparison with related works is comprehensive.\n3. Experiments show the good robustness of the proposed model.\n\nWeakness:\n1. The so-called fine-tuning experiment is not a standard fine-tuning setting used by modern works.\n2. The OLSA-based transformer model doesn't have layer norm and dropout. I suspect that's why the author is using a transformer with only 3 layers. In order to make this work has a broader impact, it's would be great the find an adequate substitute for these two modules and train a transformer model with more layers.\n3. The paper didn't explain how the method could be applied to natural language generation tasks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject