Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Contributions:
This paper develops an algorithm for verifying the robustness of transformers with self-attention layers when the inputs for one input word embedding are perturbed. Unlike previous work the present work can deal with cross nonlinearity and cross position dependency and the lower bounds derived in the paper are much tighter than the Interval Boundary Propagation (IBP) method which uses backward propagation. The core contribution is expounded by developing bounds for multiplication (xy) and division (x/y) and using this to compute tight bounds on self-attention layer computations. Further by introducing a forward process then combining it with a backward process, they can substantially reduce computation time as compared to the IBP method (in experiments demonstrated to be over an order of magnitude). 

Experimental results: Very reasonable and well thought out experiments demonstrate that a) the lower bounds produced by the method are very tight (much better than IBP for instance), and the backward&forward approach is an order of magnitude faster than the fully backward approach though they are both equally tight (the fully forward method is much looser by contrast)

The experiments on using the bound to detect the word whose perturbation will cause biggest impact (ie the most important word for explaining the decision) is much less convincing. In particular in Table 3, the second example shows that the method identifiews "a", "the" "our" etc, which at least do not appear to be most salient to this reviewer. [Question to authors: perhaps I misunderstood something here -- if so please explain and help me understand it better]. 

Evaluation / Suggestions. 
Overall I liked the paper quite a bit. I may not have fully understood something about table 3 and would welcome some explanation about why the results shown there indicate that their method works better int he second example. 


review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 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.  

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: Overview:

This paper is dedicated to developing robustness verification techniques. They claim their methods can deal with verification problems for Transformers which includes cross-nonlinearity and cross-position dependency. The paper solves these key challenges which are not traceable for previous methods. Moreover, the author demonstrates their certified robustness bounds are significantly higher than those by naive Interval Bound Propagation. They also point out the practice meaning through sentiment analysis.

Strength Bullets:

1. It is an interesting design that combines the backward process with a forward process. The author also conducts an ablation experiment to show its advantages both in the bound estimation and computation time cost.
2. The derivation is very solid and detailed. The author not only gives the certified bounds but also further analyzes whether the bounds are reasonable.

Weakness Bullets:

1. For comparison experiments, especially in Table 2, the author doesn't compare with other previous state-of-the-art methods. It just an ablation among fully forward, fully backward and combine two. To be more convincing, the author needs to post not only bounds but also time costs cross several methods on one or two datasets.
2. The experiment only uses a single-layer transformer, I don't think it contains much more nonlinear operations then MLP, CNN or RNN in the previous work. The author needs to add experiments of multi-layer transformers. 
3. The author doesn't list all famous previous verification framework, like MILP (EVALUATING ROBUSTNESS OF NEURAL NETWORKS WITH MIXED INTEGER PROGRAMMING), even doesn't give a cite. MILP is a powerful verification technique that can deal with cross-position dependency, which can be potentially applied to transformers. The author needs to compare these methods to prove the advantages of the paper's approach.
4. The novelty of the main contribution of the paper is arguable. Although it is the first one who does robustness verification on transformers, the linear relaxation is similar to previous work just deal with different nonlinearity. The author may provide more detail and explanation about the creative modification in relaxation or other parts of the proposed verification framework.

Recommendation:

For lack of necessary experiments and limit novelty, even if I like part of the approach design, this is a weak reject.
review_title: Official Blind Review #2

Meta-review: A robustness verification method for transformers is presented. While robustness verification has previously been attempted for other types of neural networks, this is the first method for transformers. 

Reviewers are generally happy with the work done, but there were complaints about not comparing with and citing previous work, and only analyzing a simple one-layer version of transformers. The authors convincingly respond to these complaints.

I think that the paper can be accepted, given that the reviewers' complaints have been addressed and the paper seems to be sufficiently novel and have practical importance for understanding transformers.
Decision: Accept (Poster)