Overcoming a Theoretical Limitation of Self-Attention (2022)

Abstract: Although transformers are remarkably effective for many tasks, there are some surprisingly easy-looking regular languages that they struggle with. Hahn shows that for languages where acceptance depends on a single input symbol, a transformer’s classification decisions get closer and closer to random guessing (that is, a cross-entropy of 1) as input strings get longer and longer. We examine this limitation using two languages: PARITY, the language of bit strings with an odd number of 1s, and FIRST, the language of bit strings starting with a 1. We demonstrate three ways of overcoming the limitation implied by Hahn’s lemma. First, we settle an open question by constructing a transformer that recognizes PARITY with perfect accuracy, and similarly for FIRST. Second, we use layer normalization to bring the cross-entropy of both models arbitrarily close to zero. Third, when transformers need to focus on a single position, as for FIRST, we find that they can fail to generalize to longer strings; we offer a simple remedy to this problem that also improves length generalization in machine translation.

## introduction although transformers @xcite are remarkably effective for many tasks, there are some surprisingly easy-looking formal languages that they struggle with. @xcite tries to explain some of these by showing (his lemma 5) that changing a single input symbol only changes the output of a transformer encoder by 𝑂 (1/𝑛), where 𝑛 is the input string length. thus, for a language where acceptance depends on a single input symbol, a transformer might accept or reject strings with perfect accuracy, but for large 𝑛, it must do so with low confidence, giving accepted strings a probability just above ½ and rejected strings a probability just below ½. more precisely, as 𝑛 increases, the cross-entropy approaches its worst possible value of 1 bit per string. here, we examine this limitation using two simple regular languages: although the lemma might be interpreted as limiting the ability of transformers to recognize these languages, we show three ways that this limitation can be overcome. first, we show by explicit constructions that transformers do in fact exist that can recognize both languages with perfect accuracy for arbitrary lengths. we have implemented these constructions and verified them experimentally ( §3). as predicted by hahn's lemma, our constructed transformers have cross-entropy that approaches 1 bit (that is, just barely better than random guessing) as input length increases. but we show that by adding layer normalization, the cross-entropy can be made arbitrarily close to zero, independent of string length ( §4). in practice, we find, like @xcite , that transformers cannot learn parity. perhaps more surprisingly, when learning first, transformers can have difficulty generalizing from shorter strings to longer strings. although this is not a logical consequence of hahn's lemma, it is a consequence of the behavior that hahn's lemma predicts. fortunately, this problem can be fixed with a simple modification, multiplying attention logits by log 𝑛. this modification also improves length generalization in machine translation ( §5). ## exact solutions the first way to overcome the limitation suggested by hahn's lemma is to show by explicit construction that our two languages can in fact be recognized with perfect accuracy by transformers. the second layer adds up the odd elements and subtracts the even elements: ## layer normalization the second way to mitigate or eliminate the limitation of hahn's lemma is layer normalization @xcite , which is defined, for any vector x, as the original transformer definition performs layer normalization immediately after every residual connection. in this section, we modify our it is also common to place layer normalization before residual connections @xcite , but we follow the original transformer definition here. ## learnability in this section, we turn to the question of learnability, which will lead to a third way of overcoming the limitation suggested by hahn's lemma. ## related work using very different assumptions on the form of transformers and inputs, a number of recent theoretical studies of transformers show that they can solve much more difficult problems than the ones studied here. transformer encoders can be shown to be universal approximators by fixing the string length and using a number of layers exponential in the length @xcite . transformer encoder-decoders, where the decoder can run for an unbounded number of steps, have been shown to be turing-complete @xcite . rasp @xcite is a simple programming language whose programs can be compiled into transformers. while parity can easily be written in rasp, this does not imply in itself the existence of transformers that can recognize parity, for two reasons. first, rasp's aggregate operation (which corresponds to attention) always attends uniformly to a subset of positions, unlike softmax attention. second, rasp's elementwise operations are embedded directly in the output transformer; they are not translated into ffnns. @xcite carry out theoretical and experimental studies of transformers for various formal languages. the theoretical results are for a different variant of transformers than ours (transformer encoders with self-attention masked so that each position attends only to previous positions), and focus on such transformers' ability to maintain counters that are constrained to be nonnegative. their experimental results suggest that transformers have difficulty learning some regular languages, including parity. ## conclusion we've seen that the questions of (a) whether a neural network can recognize a language, (b) whether it can achieve low cross-entropy on a language, and (c) whether it can learn to recognize a language are three separate questions, because we have given examples of (a) without (b) and (b) without (c). namely, our explicit construction for parity shows that a neural network can recognize a language with perfect accuracy (a) but poor crossentropy (b). adding layer normalization (𝜖 = 0) enables it to achieve low cross-entropy (b), but still does not learn well (c). we observe that because the answer to (b) can hinge on small details of the model, (b) is not probably not very useful as a way of measuring expressivity. however, we did find that the limited influence of a single input symbol, implied by hahn's lemma, has a serious practical implication for learnability (c). namely, transformers can fail to generalize from shorter training strings to longer testing strings. our proposed fix, scaling attention logits by log 𝑛, is easy to implement and very effective on a real machine translation task.