On the Computational Power of Transformers and Its Implications in Sequence Modeling

Proceedings of the 24th Conference on Computational Natural Language Learning, pages 455–475 Online, November 19-20, 2020. c⃝2020 Association for Computational Linguistics https://doi.org/10.18653/v1/P17 455 On the Computational Power of Transformers and its Implications in Sequence Modeling Satwik Bhattamishra Arkil Patel Navin Goyal Microsoft Research India {t-satbh,t-arkpat,navingo}@microsoft.com Abstract Transformers are being used extensively across several sequence modeling tasks. Sig- nificant research effort has been devoted to experimentally probe the inner workings of Transformers. However, our conceptual and theoretical understanding of their power and inherent limitations is still nascent. In partic- ular, the roles of various components in Trans- formers such as positional encodings, atten- tion heads, residual connections, and feedfor- ward networks, are not clear. In this paper, we take a step towards answering these ques- tions. We analyze the computational power as captured by Turing-completeness. We first provide an alternate and simpler proof to show that vanilla Transformers are Turing-complete and then we prove that Transformers with only positional masking and without any positional encoding are also Turing-complete. We further analyze the necessity of each component for the Turing-completeness of the network; inter- estingly, we find that a particular type of resid- ual connection is necessary. We demonstrate the practical implications of our results via experiments on machine translation and syn- thetic tasks. 1 Introduction Transformer (Vaswani et al., 2017) is a recent self- attention based sequence-to-sequence architecture which has led to state of the art results across vari- ous NLP tasks including machine translation (Ott et al., 2018), language modeling (Radford et al., 2018) and question answering (Devlin et al., 2019). Although a number of variants of Transformers have been proposed, the original architecture still underlies these variants. While the training and generalization of machine learning models such as Transformers are the cen- tral goals in their analysis, an essential prerequisite to this end is characterization of the computational POS(1) POS(2) POS(3) (a) (b) Figure 1: (a) Self-Attention Network with positional encoding, (b) Self-Attention Network with positional masking without any positional encoding power of the model: training a model for a certain task cannot succeed if the model is computation- ally incapable of carrying out the task. While the computational capabilities of recurrent networks (RNNs) have been studied for decades (Kolen and Kremer, 2001; Siegelmann, 2012), for Transform- ers we are still in the early stages. The celebrated work of Siegelmann and Sontag (1992) showed, assuming arbitrary precision, that RNNs are Turing-complete, meaning that they are capable of carrying out any algorithmic task for- malized by Turing machines. Recently, P´erez et al. (2019) have shown that vanilla Transformers with hard-attention can also simulate Turing machines given arbitrary precision. However, in contrast to RNNs, Transformers consist of several components and it is unclear which components are necessary for its Turing-completeness and thereby crucial to its computational expressiveness. The role of various components of the Trans- former in its efficacy is an important question for further improvements. Since the Transformer does not process the input sequentially, it requires some form of positional …

Content truncated to 500 words