Although transformers are remarkably eective 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 become less and less confident (that is, with cross-entropy approaching 1 bit per string) 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 1 s, and FIRST , the language of bit strings starting with a 1 . We demonstrate three ways of overcoming the limitation suggested 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 oer a simple remedy to this problem that also improves length generalization in machine translation. Although transformers (Vaswani et al., 2017) are remarkably eective for many tasks, there are some surprisingly easy-looking formal languages that they struggle with. Hahn (2020) 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: PARITY = {     |  has an odd number of 1 s } FIRST = {     |  1 = 1 } where (here and throughout the paper)  = { 0 , 1 } . Hahn's lemma applies to PARITY because the network must attend to all the symbols of the string, and a change in any one of them changes the correct answer. We have chosen FIRST as one of the simplest examples of a language that the lemma applies to. It only requires attention on the first symbol, but the lemma still applies because a change in this symbol changes the correct answer. 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 Bhattamishra et al. (2020a), that transformers cannot learn PARITY . Perhaps more surprisingly, when learning FIRST , transformers can have diculty 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). If  is a true-or-false statement, we write For any ,  > 0, we write 0    for the    zero matrix and I    for the    identity matrix. Following Hahn (2020), we consider transformer encoders with a sigmoid output layer on a single position. Dierently from Hahn (2020), but in line with common practice (Devlin et al., 2019), we prepend a token CLS (for classification) and use the encoder output at this token's position for classifying the string. The input to the network is a string     . Let  = |  | + 1, let  0 = CLS , and let   be the  -th symbol of  . The input layer has a word embedding and positional encodings, WE:   R  PE: N  R  which are used to compute input vectors for  = 0 , . . .  : a 0 , = WE (   ) + PE (  ) . The word embeddings are typically learned, while the positional encodings vary somewhat. Originally (Vaswani et al., 2017), they were fixed and defined in terms of sine and cosine waves, but they can also be learned (Gehring et al., 2017), in which case they are defined only up to some maximum position. Here, we allow ourselves to define PE as an arbitrary function on all positions. It would seem that to remain in the spirit of the original paper, PE should be easy to compute, independent of  , and parallelizable over positions. The body of the encoder is a stack of  layers, each of which has a self-attention sublayer followed by a position-wise feedforward sublayer. For  = 1 , . . . ,  , layer  is defined as follows, where  = 1 , . . . ,  , and  = 0 , . . . ,  : q ,, = WQ ,, a   1 , K , = (cid:2) WK ,, a   1 , 0    WK ,, a   1 , (cid:3) (cid:62) V , = (cid:2) WV ,, a   1 , 0    WV ,, a   1 , (cid:3) (cid:62) c , = LN (cid:32)    = 1 Att ( q ,, , K , , V , ) + a   1 , (cid:33) h , = max (cid:16) 0 , WF ,, 1 c , + b F ,, 1 (cid:17) a , = LN (cid:16) WF ,, 2 h , + b F ,, 2 + c , (cid:17) where boldface lowercase letters stand for vectors in R  and boldface uppercase letters stand for matrices in R    . The learned parameters of the model are the W 's and b 's. The function Att is scaled dot-product attention, defined as Att: R   R (  + 1 )   R (  + 1 )   R  Att ( q , K , V ) = V (cid:62) softmax Kq   where the result of the softmax, sometimes written as  , is a vector of attention weights . The function LN is layer normalization, whose definition we defer to 4. Finally, the network linearly projects the encoding of CLS to a scalar and applies a sigmoid function: where W  + 1  R 1   and b  + 1  R 1  1 . The network accepts  i the output probability is greater than 12 . 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. Rumelhart et al. (1986) showed that for any  , there is a feedforward neural network (FFNN) that computes PARITY for strings of length exactly  . They 7655 also showed that a randomly initialized FFNN can learn to do this automatically. Since our construction is partially based on theirs, it may be helpful to review their construction in detail. Let  be the input string, |  | =  , and  be the number of 1 s in  . The input is a vector x such that x  = I [   = 1 ] . The first layer computes  and compares it against 1 , 2 , . . . ,  : W 1 =  1 1    1 1 1    1 ... ... . . . ... 1 1    1  b 1 =   0 . where  is the step function (  (  ) = I [  > 0 ] applied elementwise. The second layer adds up the odd elements and subtracts the even elements: W 2 = (cid:2) 1  1    ( 1 )  + 1 (cid:3) b 2 =  0 . Proposition 1. There is a transformer encoder with sigmoid output layer that recognizes (in the above sense) the language PARITY for strings of arbitrary length. Initially, we will construct a transformer encoder without layer normalization (that is, LN ( x ) = x ); then we will show how to add layer normalization (4). Let  be the number of occurrences of 1 in  . All vectors computed by the network have  = 9 dimensions; if we show fewer dimensions, assume the remaining dimensions to be zero. Since we are numbering positions starting from 0, dimension 4 ranges from 0 to   1  , and dimension 5 is + 1 for even positions and  1 for odd positions. We argue that dimension 5, being a cosine wave, is a fairly standard choice, although its period (2) is shorter than the shortest period in standard sinusoidal encodings (2  ). Dimension 4 is admittedly not standard; however, we argue that it is a reasonable encoding, and extremely easy to compute. Thus, the encoding of word   is: a 0 , =  I [   = 0 ] I [   = 1 ] I [   = CLS ]  cos   . The network has  = 2 layers and  = 2 heads. The first self-attention layer has one head which finds  , the number of 1 s. More precisely, because attention always averages, it must compute the average number of 1 s, that is,  , and stores it in dimension 6. It also stores 1  in dimension 7, which we will need later. The second head doesn't do anything ( WV , 1 , 2 = 0 the queries and keys can be anything). After the residual connection, we have: c 1 , =   I [   = 0 ] I [   = 1 ] I [   = CLS ]   cos   1    . In the construction of Rumelhart et al. (1986), the next step is to compute I [    ] for each  , using step activation functions. There are two differences in our construction. First, we have ReLU activation functions, not step activation functions. Second, because attention must sum to one, if  is odd then the even and odd positions will get different attention weights, so the trick of subtracting even positions from odd positions will not work. Instead, we want to compute I [  =  ] (Fig. 1). After the residual connection, we have: a 1 , =  I [   = 0 ] I [   = 1 ] I [   = CLS ]  cos   1  I [  =  ]   . The second self-attention layer tests whether position  is even or odd. It does this using two heads, one which attends more strongly to the odd positions, and one which attends more strongly to the even positions; both average dimension 8: WQ , 2 , 1 = (cid:2) 0 0    0 0 0 0 0 (cid:3) WK , 2 , 1 = (cid:2) 0 0 0 0  1 0 0 0 (cid:3) WV , 2 , 1 = (cid:20) 0 8  8 0 0 0 0 0 0 0 1 (cid:21) WQ , 2 , 2 = (cid:2) 0 0    0 0 0 0 0 (cid:3) WK , 2 , 2 = (cid:2) 0 0 0 0 1 0 0 0 (cid:3) WV , 2 , 2 = (cid:20) 0 8  8 0 0 0 0 0 0 0  1 (cid:21) where  > 0 can be any constant. The second FFNN doesn't do anything ( WF , 2 , 1 = b F , 2 , 1 = WF , 2 , 2 = b F , 2 , 2 = 0 ). The vector at CLS (posi-tion 0) is then a 2 , 0 =  0 0 1 0 1  1  I [  = 0 ]    where  has a somewhat complicated value. If  is even, it turns out to be  = ( 1 )  + 1 2 tanh   2 which is positive if  is odd and negative if  is even. As predicted by Hahn, it is in  ( 1 /  ) . If  is odd, the expression for  is more complicated (see Appendix A), but it is still positive i  is odd, and it is still in  ( 1 /  ) . Finally, the output layer is a sigmoid layer that just looks at dimension 9: W 3 = (cid:2) 0 0 0 0 0 0 0 0 1 (cid:3) b 3 = 0  = 1 1 + exp (  ) . So the output is greater than 12 i  is odd. Next, we construct a transformer for FIRST . In line with the common practice of learning per-position word embeddings (Gehring et al., 2017), we use position embeddings that test whether a word is at position 1: a 0 , =  I [   = 0 ] I [   = 1 ] I [   = CLS ] I [  = 1 ]  . (We have chosen WF , 1 , 1 in a slightly unusual way to avoid using the bias term b F , 1 , 1 , in anticipation of 4 when we will add layer normalization.) The second self-attention layer has a single head, which makes CLS focus on position 1. where  > 0 is a constant. The second FFNN doesn't do anything ( WF , 2 , 1 = b F , 2 , 1 = WF , 2 , 2 = b F , 2 , 2 = 0 ). So at CLS (position 0), a 2 , 0 =  0 0 1 0 0    = exp  exp  +   1 (cid:16) I [  1 = 1 ]  12 (cid:17) . The final output layer just selects component 6: So the output probability,  =  (  ) , is greater than 12 i  1 = 1 . However, it will get closer to 12 as  increases. We implemented both of the above constructions using modified versions of PyTorch's built-in implementation of transformers (Paszke et al., 2019). 1 1 The code for this and other experiments in this paper are available at https://github.com/ndnlp/parity . These constructions achieve perfect accuracy for strings with lengths sampled from [ 1 , 1000 ] . However, in Fig. 2, the red curves (no layer norm) show that, as strings grow longer, the cross-entropy approaches its worst possible value of 1 bit per string. We discuss this problem next. The second way to mitigate or eliminate the limitation of Hahn's lemma is layer normalization (Ba et al., 2016), which is defined, for any vector x , as where the functions mean and var compute the mean and variance, respectively, of the elements of x , and  is the elementwise (Hadamard) product. We fix  = 0 and  = 1, so that the result has approximately zero mean and unit variance. The constant  was not present in the original definition (Ba et al., 2016) but is added in all implementations that we are aware of, for numerical stability. The original transformer definition performs layer normalization immediately after every residual connection. 2 In this section, we modify our 2 It is also common to place layer normalization before residual connections (Wang et al., 2019; Nguyen and Salazar, 2019), but we follow the original transformer definition here. The first is to nullify the centering eect of layer normalization by making the network compute each value  as well as its negation   . The new word encodings are defined in terms of those in the original construction:  a 0 , = (cid:20) a 0 ,  a 0 , (cid:21) . Likewise for the self-attention parameters:  WQ ,, = (cid:2) WQ ,, 0 (cid:3)  WK ,, = (cid:2) WK ,, 0 (cid:3)  WV ,, = (cid:20) WV ,, 0  WV ,, 0 (cid:21) . Likewise for the position-wise FFNN parameters:  WF ,, 1 = (cid:2) WF ,, 1 0 (cid:3)  b F ,, 1 = b F ,, 1  WF ,, 2 = (cid:20) WF ,, 2  WF ,, 2 (cid:21)  b F ,, 2 = (cid:20) b F ,, 2  b F ,, 2 (cid:21) . The argument to LN always has zero mean, so that layer normalization does not add or subtract anything. It does scale the activations, but in the case of the two transformers constructed above, any activation layer can be scaled by any positive number without changing the final decisions (see Appendix B). Furthermore, in any transformer, we can use layer normalization to shrink the cross-entropy as small as we like, contrary to Hahn's Lemma 5. In Hahn's formulation, position-wise functions like layer normalization can be subsumed into his  act , but the lemma assumes that  act is Lipschitz-continuous, and layer normalization with  = 0 is not. Proposition 2. For any transformer  with layer normalization (  = 0 ) that recognizes a language L , and for any  > 0 , there is a transformer with layer normalization that recognizes L with cross-entropy at most  . Proof. Let  be the number of dimensions in the original vectors of activations, and let  be the number of layers. Then we add a new layer whose self-attention doesn't do anything ( WV , + 1 , = 0 ) and whose FFNN is defined in terms of the original output layer:  WF , + 1 , 1 = (cid:20) I   I  (cid:21)  b F , + 1 , 1 = (cid:20) 0  0  (cid:21)  WF , + 1 , 2 = (cid:2)  I  I  (cid:3) +  W  + 1  W  + 1  W  + 1 W  + 1 0 (   2 )  0 (   2 )    b F , + 1 , 2 =  b  + 1  b  + 1 0   2  . This causes the residual connection to zero out all dimensions except two, so that if  was the original output logit, the output of this new layer (before layer normalization) is  a  + 1 , = LN (cid:169)(cid:173) (cid:171)     0   2 (cid:170)(cid:174)(cid:172) . Finally, set  =  1   / 2 log ( exp   1 ) . If the input string is in L , then the cross-entropy is log  (    / 2 ) =  . Similarly, if the input string is not in L , then the cross-entropy is log ( 1   (    / 2 )) =  . (cid:3) We tested our exact solutions, modified as described above to use layer normalization. Figure 2 shows that layer normalization with  > 0 improves the cross-entropy, but it still grows with  and approaches 1. With  = 0, the cross-entropy is independent of  and, as argued above (Proposi-tion 2), can be made as low as desired. 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. We tried training transformers on both PARITY and FIRST. Each transformer had the same number of layers and heads and the same fixed positional encodings as the corresponding exact solution. We used  model = 16 for word encodings, self-attention, and FFNN outputs, and  FFNN = 64 for FFNN hidden layers. We used layer normalization (  = 10  5 ) after residual connections. We used PyTorch's default initialization and trained using Adam (Kingma and Ba, 2015) with learning rate 3  10  4 (Karpathy, 2016). We did not use dropout, as it did not seem to help. We found, like Bhattamishra et al. (2020a), that a transformer with the above settings was unable to learn PARITY . We tried many other settings as well, to no avail. To give an idea of why our constructed solution, in particular, is dicult to find, Fig. 3 shows the cross-entropy and accuracy of the model if we start with our solution (with layer normalization,  = 0) and vary the parameter  WV , 1 , 1 6 , 2 , which is responsible for computing  . At 1, it has a cross-entropy of 0 and accuracy of 1, which are both optimal, but the cross-entropy oscillates so rapidly that even a small perturbation of this parameter would make it dicult to recover the solution by gradient descent. FIRST is much easier to learn, but the bad news is that the learned transformers do not generalize well to longer sentences. Figure 4 (left column) shows that when a transformer is trained from scratch on shorter strings (  = 10 , 30 , 100 , 300) and tested on longer strings (  = 1000), the accuracy is not perfect. Indeed, for training  = 10, the accuracy is hardly better than random guessing. In our solution above (3.3), the second self-attention layer attended mostly to the first position, but not totally. It relied on the fact that in the second self-attention layer, the values of the non-first positions ( V 2 , 1 , 4 and V 2 , 1 , 5 for   1) are exactly zero and therefore do not contribute to the output. In practice, because word embeddings are randomly initialized in all dimensions, and are added to every layer via residual connections, it's unlikely for any activation to be exactly zero. This explains why our exact solution cannot be learned. But, as a further thought experiment about what the model might be learning instead, consider the following transformer, which uses only a single layer (  = 1) and does not zero out the values of the non-first positions. As we will see, it performs worse than the transformer of 3.3 for long strings. The FFNN doesn't do anything ( WF , 1 , 1 = b F , 1 , 1 = WF , 1 , 2 = b F , 1 , 2 = 0 ), and the final output layer just selects component 5. So if  is the total number of 1 s, the final logit at CLS (position 0) would be  = exp   1 exp  +   1 (cid:18) I [  1 = 1 ]  1 2 (cid:19) + 1 exp  +   1 (cid:16)    2 (cid:17) . If  > log (   1 ) , then this is positive i  1 = 1 . But if   log (   1 ) , the new second term can be big enough to make the model output an incorrect answer. This suggests that if we train a transformer on strings with length up to  , then the learned parameters will be large enough to classify strings of length up to  correctly, but may misclassify strings longer than  . weight on the first position of the test string (summed over layers, averaged over strings) as a function of training epoch (starting from random initial parameters). The training strings have varying length (  ) and the test strings have fixed length (1000). We might hope that the attention weight would converge to the same value independent of  . But the lower  is, the more the attention weight is diluted, making it easier for the value in position 1 to be outweighed by values in other positions. Fortunately, this problem is easy to fix by scaling the logits of each attention layer by log  , that is, redefining attention as Att ( q , K , V ) = V (cid:62) softmax log    Kq . (2) Then taking the model in 5.2 with  = 1 gives  =   1 2   1 (cid:18) I [  1 = 1 ]  1 2 (cid:19) + 1 2   1 (cid:16)    2 (cid:17) which is positive i  1 = 1 . Moreover, scaling is another way to make the cross-entropy low: Proposition 3. For any  > 0 there is a transformer with attention defined as in Eq. (2) , and with or without layer normalization, that recognizes FIRST with cross-entropy at most  . Proof. Without layer normalization, we can take the model in 3.3, set  = 1 and log-scale the attention weights, which changes  from Eq. (1) to  =  2   1 (cid:18) I [  1 = 1 ]  1 2 (cid:19) 1 4 < |  |  1 2 . With layer normalization (and  > 0), we can apply the modification of 4 to nullify the centering eect of layer normalization. Then since the variance of a 2 , 0 is 16 ( 1 +  2 ) , the layer-normalized final logit is   =  (cid:18) 1 6 ( 1 +  2 ) +  (cid:19)  12 and since |  | > 14 , |   | > 1 4 (cid:18) 5 24 +  (cid:19)  12 . In either case, since the final logit has a lower bound not dependent on  , the output layer weights can be scaled as in the proof of Proposition 2 to make the cross-entropy at most  . (cid:3) train all train short test all test long train tokens 3M+3M 1M+1M test tokens 32k+34k 24k+25k baseline 32.6 11.4 scaled 32.5 12.4 Table 1: When training and testing on data with the same length distribution, scaling attention logits has no significant eect on BLEU, but when training on short sentences (  20 tokens) and testing on long sentences ( > 20 tokens), scaling helps significantly (  < 0 . 01). Figure 4 (right column) shows the training of transformers with scaling of attention logits by log  . For all training lengths  , the model is able to learn with perfect test cross-entropy and accuracy. We see a similar eect on low-resource English-to-Vietnamese machine translation (Table 1), using Witwicky, an open-source implementation of transformers. 3 We use all default settings; in particular, residual connections come after layer normalization (  = 10  5 ). We measure translation accuracy using BLEU (Papineni et al., 2002) and use bootstrap resampling with 1000 samples for significance testing. When train and test length distributions are the same, scaling attention logits has no significant effect. But if we train only on sentences with median length or shorter (  20 tokens) and test only on sentences longer than median length ( > 20 tokens), scaling attention logits by log  improves BLEU by + 1, which is statistically significant (  < 0 . 01). Using very dierent assumptions on the form of transformers and inputs, a number of recent theoretical studies of transformers show that they can solve much more dicult 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 (Yun et al., 2020). Transformer encoderdecoders, where the decoder can run for an unbounded number of steps, have been shown to be Turing-complete (Bhattamishra et al., 2020b; Prez et al., 2021). RASP (Weiss et al., 2021) 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. Bhattamishra et al. (2020a) carry out theoretical and experimental studies of transformers for various formal languages. The theoretical results are for a dierent variant of transformers than ours (transformer encoders with self-attention masked so that each position attends only to previous po-sitions), and focus on such transformers' ability to maintain counters that are constrained to be nonnegative. Their experimental results suggest that transformers have diculty learning some regular languages, including PARITY . 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 cross-entropy (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 eective on a real machine translation task. We would like to thank Toan Nguyen for assistance with his machine translation code, and Gail Weiss for catching some mistakes. This paper is based upon work supported in part by the Oce of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via contract #FA8650-17-C-9116. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the ocial policies, either expressed or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
abstain abstain objective objective objective method objective abstain abstain abstain abstain objective abstain objective abstain result objective result method result result abstain abstain abstain abstain abstain abstain method method other other method other other method other other other other other abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain other abstain abstain abstain abstain abstain abstain abstain method method method abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain method abstain method abstain abstain abstain other abstain abstain method abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain abstain other abstain abstain result abstain abstain abstain result other other other other other other other other other other result abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result abstain abstain result abstain abstain objective other other other other