  Robustness verification that aims to formally certify the prediction behavior
of neural networks has become an important tool for understanding model
behavior and obtaining safety guarantees. However, previous methods can usually
only handle neural networks with relatively simple architectures. 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 works. We resolve these challenges and
develop the first robustness 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
different words in sentiment analysis.
