Theoretical Limitations of Self-Attention in Neural Sequence Models (2020)

Abstract: Transformers are emerging as the new workhorse of NLP, showing great success across tasks. Unlike LSTMs, transformers process input sequences entirely through self-attention. Previous work has suggested that the computational capabilities of self-attention to process hierarchical structures are limited. In this work, we mathematically investigate the computational power of self-attention to model formal languages. Across both soft and hard attention, we show strong theoretical limitations of the computational abilities of self-attention, finding that it cannot model periodic finite-state languages, nor hierarchical structure, unless the number of layers or heads increases with input length. These limitations seem surprising given the practical success of self-attention and the prominent role assigned to hierarchical structure in linguistics, suggesting that natural language can be approximated well with models that are too weak for the formal languages typically assumed in theoretical linguistics.

## introduction transformers are emerging as the new workhorse of nlp, achieving the state-of-the-art in tasks such as language modeling, machine translation, and creating pretrained contextualized word embeddings. eschewing recurrent computations, transformers are entirely based on self-attention, performing their computations largely in parallel. this enables them to scale to very long sequences @xcite @xcite . on the other hand, it has been suggested that this limits their expressiveness, as they cannot process input sequentially @xcite @xcite @xcite . one aspect thought to be challenging for sequence models is hierarchical structure and recursion. hierarchical structure is widely thought to be essential to modeling natural language, in particular its syntax @xcite . consequently, many researchers have studied the capability of recurrent neural network models to capture context-free languages (e.g., @xcite @xcite @xcite and linguistic phenomena involving hierarchical structure (e.g., @xcite . some experimental evidence suggests that transformers might not be as strong as lstms at modeling hierarchical structure @xcite , though analysis studies have shown that transformer-based models encode a good amount of syntactic knowledge (e.g., @xcite @xcite . in this work, we examine these questions from a theoretical perspective, asking whether models entirely based on self-attention are theoretically capable of modeling hierarchical structures involving unbounded recursion. formally, we study their ability to perform two computations that are thought to be essential to hierarchical structure: first, their ability to correctly close brackets, a basic problem underlying all nonregular context-free languages and formalized by the dyck language @xcite . second, their ability to evaluate iterated negation, a basic component of the task of evaluating logical formulas, amounting to evaluating the parity of bitstrings. we show that neither of these problems can be solved by transformers and similar models relying entirely on self-attention, unless the number or size of parameters increases with the input length. besides representing basic building blocks of hierarchical structure, these languages also represent large classes of regular and context-free languages, meaning that our results carry over to classes of other formal languages. our results therefore also yield more generally limitations on the ability of self-attention to model finite-state languages and context-free languages. although theoretical work has investigated the power of recurrent neural networks in depth (e.g., @xcite @xcite @xcite , the theoretical study of selfattention has begun only recently @xcite . our study provides the first theoretical results on limitations in the power of self-attention. we will provide results both for hard and soft attention settings, using different proof methods. our results are strongest in the hard attention setting, holding without further assumptions on activation functions and parameter norms. in the soft attention settings, we still obtain results assuming smoothness of activation functions as used in practical implementations. after discussing related work (section 2), we introduce self-attention (section 3) and two fundamental formal languages representing regular and context-free languages (section 4). we then prove that self-attention cannot model these languages using either hard (section 5) or soft (section 6) attention. finally, we discuss our results (section 7). a few studies have experimentally tested the abilities of transformers to learn structures. most related to our work, @xcite compared the ability of transformers and lstms to learn hierarchical structure, specifically, english subject-verb agreement and evaluating logical formulas. their experimental results suggested that lstms are better at learning hierarchical structure. @xcite experimentally investigated the power of self-attention to extract word order information, finding differences between recurrent and self-attention models; however, these were modulated by the training objective. @xcite and @xcite show that bert @xcite encodes syntactic information. theoretical study of transformers was initiated by @xcite , who theoretically studied the ability of seq2seq transformers to emulate the computation of turing machines. while we consider incremental modeling of sequences, where the number of computation steps is bounded by the input length n, they study the setting in which the transformer computes an unbounded number of autoregressive decoding steps, not bounded in the input length n. even more recently, and more closely related to our interest here, @xcite studied the adversarial robustness of transformers. although they focused on experiments on nlp tasks, they also provided a theoretical analysis, showing that a single self-attention layer with a single head will be robust against input perturbations, assuming that input embeddings are drawn uniformly from the unit sphere. one of our results, lemma 5, can be seen as considerably widening the scope of their result, both by avoiding distributional assumptions, and by applying to transformers with arbitrary numbers of heads and layers. ## self-attention here we define self-attention as used in transformers, following @xcite , with some changes in the notation to simplify arguments in our proofs. we have an input @xmath0. . . x n , where all x i come from some finite alphabet v, and x n is an end-of-sequence symbol. this input is then encoded into a sequence of input embeddings v 1 , . . . , v n using some embedding map @xmath1. we furthermore have a sequence p 1 , p 2 , . . . of positional embeddings p @xmath2. these are independent of the input x, and can be computed through some predefined scheme, or could be learned for each position occurring in the training data @xcite . input and positional embeddings are combined (e.g., via addition or concatenation) to vectors y (0) @xmath3, p i ) (@xmath4, . . . , n), which we will refer to as layer 0. a transformer has a fixed number l of layers; the activations y (k) i at position i of the k-th layer (@xmath5, . . . , l) are defined as follows. each layer has a set of h attention heads; we first compute attention scores for the h-th head: we note that the implementation described by @xcite first linearly transforms the activations y (k-1) j into 'value vectors' before multiplying with â(k,h) i,j ; this is mathematically equivalent to applying this linear transformation to b i,k,h as part of the map f act we describe below. in the hard attention variant @xcite , one takes the actual maximum attention values: hard and soft attention there is a choice between soft attention and hard attention @xcite . the one prior theoretical study of transformers @xcite assumes hard attention. in practice, soft attention is easier to train with gradient descent; however, analysis studies suggest that attention often concentrates on one or a few positions in trained transformer models @xcite and that the most important heads are those that clearly focus on a few positions @xcite , suggesting that attention often behaves like hard attention in practice. we will examine both hard (section 5) and soft (section 6) attention. formalizing language recognition we consider the problem of language recognition, the task of classifying input strings as belonging to or not belonging to a formal language. following @xcite , we formalize this as the sequence-to-sequence task of mapping words to labels 1 ('in the language') and 0 ('not in the language'). following the construction of transformers in sequence-to-sequence tasks @xcite , we compute a softmax probability vector for this label from the last activation y (l) n , obtained after reading the end-of-sequence symbol. ## regular and context-free languages we will analyze the ability of transformers to recognize regular and context-free languages, using two prominent representatives. parity is the set of bit strings such that the number of 1s is even. this is a very simple regular language, recognized by a finite-state automaton with two states. the regular languages form the lowest layer of the chomsky hierarchy, and even simple rnns can compute all regular languages. within the regular languages, a particularly basic class is formed by the counter-free or star-free languages @xcite , which can be expressed by regular expressions using only union, complementation, and concatenation. in some sense, parity is the simplest non-counterfree, or periodic, regular language. this means, if transformers cannot compute parity, they cannot recognize (almost) foot_1 any regular language that is not counter-free. in the context of natural language, parity naturally arises in the context of evaluating logical formulas: evaluating iterated negations is tantamount to counting whether the number of nested negations is even or odd. if transformers cannot compute parity, they also cannot evaluate logical formulas accurately. ## results for hard attention we will start our analysis with the study of hard attention @xcite . we show that hard attention transformers cannot represent parity or 2dyck. to keep the results maximally general, our analysis will use combinatorial arguments and make no assumption about, for example, activation functions and the norms of parameter matrices. in fact, we do not even assume that the internal position-wise representations y (k) j in each layer are vector-valued, as opposed to, say, discrete structures. we aim to prove that no hard-attention transformer is capable of representing parity or 2dyck, by constructing-for any given candidate transformer model-a set of input words that this model will have to misclassify. the basic idea (see figure 1 ) behind the proof is that, by fixing a small fraction of the input symbols in a particular way, we can ''capture the attention'' of the transformer in such a way that it ends up ignoring almost all remaining input symbols. this shows that the transformer could not have solved a problem such as parity, where every single input bit matters. in order to formalize the idea of ''fixing'' a few input bits, we introduce the notion of input restrictions: an input restriction (short: restriction) ρ is a family of maps ρ n : {1, . . . , n} → { * , 0, 1} for @xmath6. an input restriction ρ is applied to a transformer by fixing, when the input length is n, the input symbol x i to the value ρ n (i) whenever ρ n (i) ∈ {0, 1}. the output value of the resulting transformer only depends on those inputs x i such that ρ n (i) = * . the idea of using such input restrictions has been successful in the theory of boolean circuits @xcite . in particular, @xcite famously used it to prove that polynomial-size bounded-depth boolean circuits with ∧, ∨, and ¬ gates cannot compute parity. we describe a new method to prove existence of suitable restrictions appropriate to transformers, as the proof approaches from the boolean circuit literature do not seem to generalize to networks with real-valued activations. the following result formalizes the claim that any transformer can be forced to ignore input bits by fixing some inputs in a particular way: theorem 1. let any hard attention transformer be given, and let @xmath7, 1). then there is a restriction ρ and an integer @xmath8: ρ n (i) = * }| ≥ cn (for all sufficiently large n) and such that the function computed by the transformer on the restricted input depends only @xmath9, independent of input length n. we first show how this entails that transformers do not recognize the two formal languages: corollary 2. transformers with hard attention cannot model parity or 2dyck. proof. for parity, after applying a restriction, the transformer's output depends on c inputs. an input of sufficiently large size n thus has unrestricted inputs that do not influence the output. but flipping a single input bit changes the value, so the transformer's output cannot match membership in parity beyond chance for such n. for 2dyck, we show that hard attention transformers cannot even solve the simpler variant 1dyck with a single bracket type ('(', ')'). we first restrict the first 0.2n input positions to '(' and the last 0.2n positions to ')'. after then applying the restriction provided by the theorem with @xmath10.9, the resulting restricted input will still be compatible with both well-bracketed and non-well-bracketed inputs, but the prediction will depend only on a bounded number of positions. as the prediction depends on only a bounded number of positions, this shows the transformer could not recognize 1dyck, and thus also not 2dyck. discussion it may be instructive to compare to similar languages that can be modeled by hardattention transformers. first, 1 * (over the alphabet {0, 1}) is the regular language of words that have only ones and no zeroes; its minimal automaton has two states, like parity. a transformer can recognize this by having an attention head that attends to a position with zero input if it exists, and rejects if the head found such a position. second, a n b n is a very basic context-free language. it can be recognized using suitable positional embeddings by (1) having one head attend to the largest position n, (2) using this information to attend to any b at @xmath11. if such a symbol is found, the model rejects, else it accepts. a crucial difference between these languages and parity / 2dyck is that fixing a few inputs in any part of an input string can easily force nonmembership, e.g., a single 0 for 1 * , and an a in the second half for a n b n . therefore, such simple languages are immune to the depth reduction method, and indeed can be modeled perfectly with self-attention. in general, the depth reduction method applies to languages that are sufficiently sensitive: if, for some @xmath12, 1), fixing cn input symbols cannot force a word to be inside or outside of the language, then hard-attention transformers cannot recognize this language. sensitivity of functions has been studied in computational complexity @xcite and more recently linked to generalization in feedforward networks @xcite . we intend to investigate these connections in future work. proof idea of the theorem our approach for proving theorem 1 will be to construct input restrictions in a layerwise manner, starting from layer 1. in order for this construction to go through, the main challenge is to construct a suitable restriction at a given layer: as shown in figure 2 , this restriction should only affect a few input bits (about (1 -c 1/l )n many input bits), while forcing each attention head in the first layer to ignore all but c input bits. perhaps surprisingly, this is possible; the idea is to fix input bits that achieve high attention scores for several heads, so that input bits that cannot achieve such high attention scores will be ignored. once we have shown that such a restriction always exists, we can use this technique to iteratively remove layers, as illustrated in figure 1 : after we have applied the first such restriction, each of the heads in the first layer will only depend on a bounded number c of input positions. in the second step, we apply the same argument to the heads in the second layer, so that each head in the second layer only depends on a bounded number c ′ of heads in the first layer. after this step, we can collapse the first layer into a collection of feedforward networks that transform a bounded @xmath13. after this step, the first layer has been entirely removed. iterating this argument, we remove all layers until the prediction output only depends on a bounded number of input positions, bounded independently of input length. we now make these ideas formal. after the removal of the first layer of a transformer, the resulting structure is not a transformer any more, as each head in the lowest layer now depends on a combination of input positions. we introduce a technical definition to make this concept precise: definition 3. (c-transformer). let c be a positive integer. a c-transformer with l layers is one in which the layer-0 activations y (0) j depend on the embeddings not just at one position j, but are a function of the embeddings @xmath14: for some indices i j,n @xmath15, . . . , n} (@xmath16, . . . , c). with this technical notion, we show that we can reduce layers, iteratively removing the lowest layer until no self-attention layer is left: lemma 4. (depth reduction lemma). given a c-transformer with l layers, and some restriction ρ such that for all sufficiently large n, and such that the resulting function is computed by a (c • (2 c kh + 1))-transformer with l-1 layers, for some integer k (depending on c ′ ), where @xmath17. the lemma implies theorem 1: proof of theorem 1. the output of the transformer is determined by the last activation y (l) n . apply the depth reduction lemma iteratively, choosing the constants c ′ in the lemma appropriately, until only the zero-th layer remains. then, after applying the resulting restriction, the final activation y (l) n is now computed by y (0) n , which is determined by a bounded number of input bits. ## results for soft attention in the previous section, we showed that transformers using hard attention are not able to recognize a range of core formal languages. in this section, we study soft attention. it turns out that proving limitations as strong as what we found in the hard attention setting would settle a major open problem in computational complexity, and may therefore be extremely hard to attain with currently available mathematical methods. 3 this barrier prevents us from proving bounds on the accuracy that soft attention transformers can achieve; nevertheless, we will be able to prove limitations on the achievable cross-entropy in modeling distributions over the formal languages. we will use the smoothness of the operations used in transformers to show that any transformer, as inputs get longer, will not be able to robustly model such distributions. the idea behind the proof is that the impact of any single input symbol on the output of the transformer is small if the input is long: lemma 5. let a soft attention transformer be given, and let n be the input length. if we exchange one input symbol x i (@xmath18, then the change in the resulting activation y (l) n at the decoder layer is bounded as o( 1 n ) with constants depending on the parameter matrices. this contrasts with recurrent networks: changing a single input can have nonnegligible impact on the final state even for very long input. for example, an rnn recognizing parity through a hidden state that encodes parity of the current prefix will flip its hidden state if a single input bit is flipped. lemma 5 entails that, as inputs become longer, soft attention transformers cannot achieve good cross-entropies on prediction problems that are very sensitive to individual input symbols: a lipschitz-continuous prediction function, such as a relu mlp with a softmax output, will not be able to make very different predictions for inputs that are encoded into similar activations y (l) n . to make all our assumptions explicit, we will assume the following setting, though the results do not depend on the specific details. for parity, we consider the distribution over bitstrings generated by a two-state automaton that -if the number of 1s emitted so far is even -terminates with probability p, and otherwise emits a 1 or 0 with equal probability each. given a prefix of a string drawn from this distribution, we ask the transformer to predict the next symbol from σ = {0, 1, endofsequence}. note that the next symbol can be endofsequence if and only if the prefix has an even number of 1s. for 2dyck, we follow the experimental study of @xcite and take the distribution generated by a pcfg that expands @xmath19, and @xmath20. we ask the model to predict the next character among σ = {(, ), [, ], endofsequence}. theorem 6. let a soft attention transformer be given for parity or 2dyck. as @xmath21, crossentropy on predicting the next symbol converges to unigram chance level (parity), or is at least separated from the optimal cross-entropy by some constant ǫ > 0 (2dyck). proof. first, let us consider parity. exchanging a single bit flips membership in parity. thus, for any @xmath22, there is a string x ′ ∈ parity, differing only in one bit. as x and x ′ differ only in one bit, the transformer's output activations differ by o( 1 n ). therefore, a lipschitz-continuous prediction function cannot robustly assign different next-symbol probabilities after even and odd numbers of 1s, and cross-entropy will converge to unigram chance level. for 2dyck, consider a string x of length n, known to be the prefix of a word generated by the pcfg. one can show that there is a constant p 0 ∈ (0, 1) (dependent on p but not n), such that x both ends with a closing bracket, and is unbalanced, with @xmath23. 4 after such 4 one can show this formally using a markov chain argument. let the height h(x) of a word x be the number of opening brackets minus the number of closing brackets in x. when iteratively sampling a symbol sequence using a pushdown automaton for 2dyck, the height h n of the prefix x up to length n forms a markov chain taking values in n. the prefix x is unbalanced if and only if h @xmath24, this is always the case whenever n is odd. restricting to even n, the chain {h n : @xmath25, 2, 4, ...} is aperiodic and takes values in {0, 2, 4, . . . }. it is also positive recurrent, as words sampled from the pcfg have finite expected length @xcite 2.1). therefore, the markov chain {h n : @xmath26, 2, 4, ...} converges to its stationary distribution @xcite , which -by positive recurrence -must assign some nonzero weight an x, the next symbol is a closing bracket with constant nonzero probability (1p). if x can be followed by, say, ')' but not ']', then there is a string x ′ , differing only in one input position, but for which the next symbol can be ']' but not ')'. as x was assumed to end with a closing bracket, the exchanged symbol is not the last symbol of x, and thus the transformer's predictions on x and x ′ differ only by o( 1 n ). we can decompose the prediction task into predicting (1) whether an opening or closing bracket, or endofsequence, follows, and (2) whether a round or square bracket follows, in case a bracket follows. the crossentropy loss is the sum of the cross-entropies incurred on these two successive predictions tasks. therefore, when such a prefix x is followed by the correct closing bracket, say ')', the model will incur, as @xmath27, a cross-entropy loss on the second task of at least log 2, reflecting atchance performance in choosing between the two possible closing brackets. in contrast, optimal cross-entropy loss on (2) would be 0, as the bracket type (round or square) is actually fully determined by x. thus, the overall cross-entropy on all prefixes x of length n is, asymptotically as @xmath28, at least p 0 • (1p) • log 2 > 0 more than the optimal cross-entropy. we proceed to proving lemma 5. proof of lemma 5. we compare the activations at the decoder layer for two inputs that only differ in the input at the i-th position. the norm of the difference of the input embeddings at this position. we show by induction over @xmath29, . . . , l that, for some @xmath30, y (k) j ′ are bounded as: once we have shown this, we know that the influence of any individual input on the final prediction is o( 1 n ), with constants depending on π 2i to each height 2i (@xmath31. hence, even when n is even, the prefix x is unbalanced with nonzero probability 1π 0 asymptotically independent of n. also, since the transition probabilities p (h n+1 |h n ) are independent of n, there is an asymptotically constant nonzero probability that x 1 . . . x |x|-1 has height larger than x, i.e., the last bracket of x is a closing one. the norms of parameter matrices and the number of layers. at this point, it is worth remarking that a key property of transformers for this proof is that the number l of layers is bounded independently of the input length. a similar proof strategy can also be applied to other fixed-depth architectures that combine unboundedly many inputs in a smooth manner, such as 1d temporal convolutions with average pooling. ## discussion we have shown that, even with infinite precision, transformers cannot robustly model non-counterfree regular languages, nor basic hierarchical structure. in the hard attention setting, our results hold independently of activation functions and the magnitude of the parameters, and show that no transformer can accurately classify strings as belonging to such languages. in the soft attention setting, our results are slightly less general, but still show that transformers cannot achieve perfect cross-entropies when modeling distributions over these formal languages. our results are asymptotic, in the sense that they show that any transformer will make mistakes on modeling parity and 2dyck when the input is sufficiently long. a transformer may nonetheless be able to perform well on on short inputs; indeed, given any bound n on the input length, it is possible to construct a transformer that will achieve perfect accuracy or cross-entropy on all examples of length @xmath32; our results show that the number of heads and layers, or the parameter norms, will have to increase with n . practical implementations of transformers might thus be able circumvent such asymptotic limitations by using large numbers of layers and heads, in relation to the sentence lengths typically occurring in natural language. therefore, pending tighter nonasymptotic bounds, the results reported here need not constitute conclusive evidence for practical limitations of real-world nlp systems. we believe that the most imminent implications of our results are theoretical in nature. they showcase mathematical techniques for analyzing the capabilities of self-attention, an architecture at the heart of recent advances in nlp. these tools provide theoretical understanding of differences between self-attention and theoretically more wellstudied recurrent architectures: recurrent networks such as lstms can perfectly emulate finite-state automata, and therefore can model any finite state language with optimal cross-entropy, as long as the state transition and symbol emission distributions are markovian. in particular, parity of i.i.d. bitstrings can be predicted with perfect accuracy and cross-entropy, independent of the input length. furthermore, infinite-precision rnns and lstms can model stacks @xcite @xcite and thus are theoretically capable of modeling 2dyck and other deterministic context-free languages perfectly. the results presented here thus theoretically confirm the intuition that models entirely built on self-attention may have restricted expressivity when compared to recurrent architectures @xcite @xcite @xcite . complementing the asymptotic methods developed here with empirical studies or nonasymptotic extensions is an interesting avenue for future research. while finite languages are sufficient to model language up to any finite bound on sequence length, it has typically been argued that asymptotically more powerful formalisms at the level of contextfree grammars or beyond are necessary to properly capture generalizations about the syntax and meaning of natural language (e.g., @xcite . our results entail that self-attention is limited in its ability to model context-free languages or evaluate logical formulas. in particular, self-attention cannot in general emulate stacks or arbitrary finite-state automata. whether this hinders its capacity for syntactic generalization in practice is an interesting question; empirical research suggests that models with strong quantitative performance-both recurrent and transformer models-continue to struggle with syntactic generalization and that quantitative performance metrics such as perplexity can partly be dissociated from syntactic knowledge displayed on more challenging benchmarks (e.g., @xcite @xcite . nonetheless, the success of transformers across nlp tasks suggests that many aspects of natural language can be modeled well with methods that are formally too weak for the formal languages typically assumed in theoretical linguistics. beyond general limitations of asymptotic analysis, a possible reason for this phenomenon is that language uses recursive structure only in restricted ways due to cognitive factors. for instance, it has long been noted that center embeddings, syntactic structures exhibiting iterated bracketing, are very challenging for humans to process @xcite . intriguingly, self-attention bears some resemblance to psycholinguistic models of memory in human sentence processing that assume that humans, while processing a word, attend to chunks that were stored in memory when processing some previous words @xcite . such processing models predict difficulty with center embedding because they cannot count brackets @xcite , akin to what we have shown theoretically for neural network models based on self-attention. ## conclusion we formally investigated the capabilities of selfattention in modeling regular languages and hierarchical structure. we showed that transformers cannot model periodic regular languages or basic recursion, either with hard or soft attention, and even if infinite precision is allowed. this entails that self-attention cannot in general emulate stacks or general finite-state automata. our results theoretically confirm the idea that self-attention, by avoiding recurrence, has quite limited computational power.