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

Abstract: Transformers are being used extensively across several sequence modeling tasks. Significant 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 particular, the roles of various components in Transformers such as positional encodings, attention heads, residual connections, and feedforward networks, are not clear. In this paper, we take a step towards answering these questions. 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; interestingly, we find that a particular type of residual connection is necessary. We demonstrate the practical implications of our results via experiments on machine translation and synthetic tasks.

## introduction transformer @xcite is a recent selfattention based sequence-to-sequence architecture which has led to state of the art results across various nlp tasks including machine translation @xcite , language modeling @xcite and question answering @xcite . 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 central goals in their analysis, an essential prerequisite to this end is characterization of the computational pos (1) pos ( 2 power of the model: training a model for a certain task cannot succeed if the model is computationally incapable of carrying out the task. while the computational capabilities of recurrent networks (rnns) have been studied for decades @xcite , for transformers 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 formalized by turing machines. recently, @xcite 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 transformer 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 information. various positional encoding schemes have been proposed to capture order information @xcite @xcite . at the same time, on machine translation, @xcite showed that the performance of transformers with only positional masking @xcite is comparable to that with positional encodings. in case of positional masking (fig. 1 ), as opposed to explicit encodings, the model is only allowed to attend over preceding inputs and no additional positional encoding vector is combined with the input vector. @xcite raised the question of whether explicit encoding is necessary if positional masking is used. additionally, since @xcite 's turingcompleteness proof relied heavily on residual connections, they asked whether these connections are essential for turing-completeness. in this paper, we take a step towards answering such questions. below, we list the main contributions of the paper, ## definitions and preliminaries all the numbers used in our computations will be from the set of rational numbers denoted q. for a sequence @xmath0, . . . , x n ), we set x j := (x 1 , . . . , x j ) for 1 ≤ @xmath1. we will work with an alphabet σ of size m, with special symbols # and $ signifying the beginning and end of the input sequence, respectively. the symbols are mapped to vectors via a given 'base' embedding f b : σ → q d b , where d b is the dimension of the embedding. e.g., this embedding could be the one used for processing the symbols by the rnn. together, these provide embedding for a symbol s at position i given by f (f b (s), pos(i)), often taken to be simply f b (s) + pos(i). vector @xmath2. ## experiments in this section, we explore the practical implications of our results. our experiments are geared towards answering the following questions: q1. are there any practical implications of the limitation of transformers without decoder-encoder residual connections? what tasks can they do or not do compared to vanilla transformers? q2. is there any additional benefit of using positional masking as opposed to absolute positional encoding @xcite ? although we showed that transformers without decoder-encoder residual connection are not turing complete, it does not imply that they are incapable of performing all the tasks. our results suggest that they are limited in their capability to make inferences based on their previous computations, which is required for tasks such as counting and language modeling. however, it can be shown that the model is capable of performing tasks which rely only on information provided at a given step such as copying and mapping. for such tasks, given positional information at a particular step, the model can look up the corresponding input and map it via the ffn. we evaluate these hypotheses via our experiments. ## discussion and final remarks we showed that the class of languages recognized by transformers and rnns are exactly the same. this implies that the difference in performance of both the networks across different tasks can be attributed only to their learning abilities. in contrast to rnns, transformers are composed of multiple components which are not essential for their com-putational expressiveness. however, in practice they may play a crucial role. recently, @xcite showed that the decoder-decoder attention heads in the lower layers of the decoder do play a significant role in the nmt task and suggest that they may be helping in language modeling. this indicates that components which are not essential for the computational power may play a vital role in improving the learning and generalization ability. take-home messages. we showed that the order information can be provided either in the form of explicit encodings or masking without affecting computational power of transformers. the decoder-encoder attention block plays a necessary role in conditioning the computation on the input sequence while the residual connection around it is necessary to keep track of previous computations. the feedforward network in the decoder is the only component capable of performing computations based on the input and prior computations. our experimental results show that removing components essential for computational power inhibit the model's ability to perform certain tasks. at the same time, the components which do not play a role in the computational power may be vital to the learning ability of the network. although our proofs rely on arbitrary precision, which is common practice while studying the computational power of neural networks in theory @xcite @xcite , implementations in practice work over fixed precision settings. however, our construction provides a starting point to analyze transformers under finite precision. since rnns can recognize all regular languages in finite precision (korsky and berwick, 2019), it follows from our construction that transformer can also recognize a large class of regular languages in finite precision. at the same time, it does not imply that it can recognize all regular languages given the limitation due to the precision required to encode positional information. we leave the study of transformers in finite precision for future work.