Robustness verification that aims to formally certify the prediction behavior of neural networks has become an important tool for understanding the behavior of a given model and for obtaining safety guarantees. However, previous methods are usually limited to relatively simple neural networks. In this paper, we consider the robustness verification problem for Transformers. Transformers have complex self-attention layers that pose many challenges for verification, including cross-nonlinearity and cross-position dependency, which have not been discussed in previous work. We resolve these challenges and develop the first verification algorithm for Transformers. The certified robustness bounds computed by our method are significantly tighter than those by naive Interval Bound Propagation. These bounds also shed light on interpreting Transformers as they consistently reflect the importance of words in sentiment analysis.
Summary:
This paper builds upon the CROWN framework (Zhang et al 2018) to provide robustness verification for transformers. The  CROWN framework is based upon the idea of propagating linear bounds and has been applied to architectures like MLP, CNNs and RNNs. However, in Transformers, the presence of cross-nonlinearities and cross-position dependencies makes the backward propagation of bounds in CROWN computationally intensive. A major contribution of this paper is to use forward propagation of bounds in self attention layers along with the usual back-propagation of bounds in all other layers. The proposed method provides overall reduction in computational complexity by a factor of O(n). Although the fully forward propagation leads to loose bounds, the mixed approach (forward-backward) presented in this work provides bounds which are as tight as fully backward method. 
Strength:
Use of forward propagation to reduce computational complexity is non-trivial
Strong results on two text classification datasets:
Lower bounds obtained are significantly tighter than IBP
The proposed method is an order of magnitude faster than fully backward propagation, while still maintaining the bounds tight.
Weakness:
Experiments only cover the task of text classification. Experiments on other tasks utilizing transformers would have made the results stronger.
The paper makes the simplifying assumption that only a single position of an input sentence will be perturbed.  They claim that generalizing to multiple positions is easy in their setup but that is not supported.   The paper needs to declare this assumption early on in the paper (abstract and intro). As far as I could tell, even during the experiments they perturb a single word at a time.
The paper is more technical than insightful.  I am not at all convinced from a practitioners viewpoint that such bounds are useful.  However, given the hotness of this topic, someone or the other got to work out the details.   If the math is correct, then this paper can be it.  
The presentation requires improvement.  Some parts, example, the Discussion section cannot be understood.
Questions:
The set-up in the paper assumes only one position in the input sequence is perturbed for simplicity. Does the analysis remain the same when multiple positions are perturbed? 
Suggestions:
A diagram to describe the forward and backward process would significantly improve the understanding of the reader.
In Table 3, I am surprised that none of the sentiment bearing words were selected as the top-word by any of the methods.  Among the ‘best’ words,  the words chosen by their method does not seem better than those selected by the grad method.
Several typos in the paper: spelling mistakes in “obtain a safty guarantee”, poor sentence construction in “and independent on embedding distributions”, subject verb disagreement in “Upper bounds are discrete and rely on the distribution of words in the embedding space and thus it cannot well verify”.
I have not verified the math to see if they indeed compute a lower bound.