On the A bility and L imitations of T ransformers to R ecognize F ormal L anguages (2020)

Abstract: Transformers have supplanted recurrent models in a large number of NLP tasks. However, the differences in their abilities to model different syntactic properties remain largely unknown. Past works suggest that LSTMs generalize very well on regular languages and have close connections with counter languages. In this work, we systematically study the ability of Transformers to model such languages as well as the role of its individual components in doing so. We first provide a construction of Transformers for a subclass of counter languages, including well-studied languages such as n-ary Boolean Expressions, Dyck-1, and its generalizations. In experiments, we find that Transformers do well on this subclass, and their learned mechanism strongly correlates with our construction. Perhaps surprisingly, in contrast to LSTMs, Transformers do well only on a subset of regular languages with degrading performance as we make languages more complex according to a well-known measure of complexity. Our analysis also provides insights on the role of self-attention mechanism in modeling certain behaviors and the influence of positional encoding schemes on the learning and generalization abilities of the model.

## introduction transformer @xcite is a selfattention based architecture which has led to stateof-the-art results across various nlp tasks @xcite @xcite . much effort has been devoted to understand the inner workings and intermediate representations of pre-trained models; @xcite is a recent survey. however, our understanding of their practical ability to model different behaviors relevant to sequence modeling is still nascent. on the other hand, a long line of research has sought to understand the capabilities of recurrent neural models such as the lstms @xcite . recently, @xcite , @xcite showed that lstms are capable of recognizing counter languages such as dyck-1 and a n b n by learning to perform counting like behavior. @xcite showed that lstms can recognize shuffles of multiple dyck-1 languages, also known as shuffle-dyck. since transformer based models (e.g., gpt-2 and bert) are not equipped with recurrence and start computation from scratch at each step, they are incapable of directly maintaining a counter. moreover, it is known that theoretically rnns can recognize any regular language in finite precision, and lstms work well for this task in practical settings. however, transformer's ability to model such properties in practical settings remains an open question. prior to the current dominance of transformers for nlp tasks, recurrent models like rnn-based models such as lstms were the most common choice, and their computational capabilities have been studied for decades, e.g., @xcite . in this work, we investigate the ability of transformers to express, learn, and generalize on certain counter and regular languages. formal languages provide us a controlled setting to study a network's ability to model different syntactic properties in isolation and the role of its individual components in doing so. recent work has demonstrated close connections between lstms and counter automata. hence, we seek to understand the capabilities of transformers to model languages for which the abilities of lstms are well understood. we first show that transformers are expressive enough to recognize certain counter languages like shuffle-dyck and n-ary boolean expressions by using self-attention mechanism to implement the relevant counter operations in an indirect manner. we then extensively evaluate the model's learning and generalization abilities on such counter languages and find that models generalize well on such languages. visualizing the intermediate representations of these models shows strong correlations with our proposed construction. although transformers can generalize well on some popularly used counter languages, we observe that they are limited in their ability to recognize others. we find a clear contrast between the performance of transformers and lstms on regular languages (a subclass of counter languages). our results indicate that, in contrast to lstms, transformers achieve limited performance on languages that involve modeling periodicity, modular counting, and even simpler star-free variants of dyck-1, which they were able to recognize effortlessly. our analysis provides insights about the significance of different components, namely self-attention, positional encoding, and the number of layers. our results also show that positional masking and positional encoding can both aid in generalization and training, but in different ways. we conduct extensive experiments on over 25 carefully chosen formal languages. our results are perhaps the first indication of the limitations of transformers for practical-sized problems that are, in a precise sense, very simple, and in particular, easy for recurrent models. ## related work numerous works, e.g., @xcite ; @xcite ; @xcite , have attempted to understand the capabil-ities and inner workings of recurrent models by empirically analyzing them on formal languages. @xcite showed that lstms are capable of simulating counter operations and explored their practical ability to recognize languages like a n b n and a n b n c n . @xcite further showed that lstms can learn to recognize dyck-1 and shuffle-dyck and can simulate the behavior of k-counter machines. theoretical connections of recurrent models have been established with counter languages @xcite @xcite ). it has also been shown that rnn based models can recognize regular languages @xcite and efforts have been made to extract dfas from rnns trained to recognize regular languages @xcite @xcite . we are not aware of such studies for transformers. recently, researchers have sought to empirically analyze different aspects of the transformer trained on practical nlp tasks such as the information contained in intermediate layers @xcite @xcite . @xcite studied the role of different types of attention heads. @xcite ; @xcite examined the ability of the model to learn order information via different positional encoding schemes. complementary to these, our work is focused on analyzing transformer's ability to model particular behaviors that could be relevant to modeling linguistic structure. recently, it has been shown that transformers are turing-complete @xcite and are universal approximators of sequence-to-sequence functions given arbitrary precision @xcite . @xcite shows that transformers cannot recognize languages parity and dyck-2. however, these results only apply to very long words, and their applicability to practical-sized inputs is not clear (indeed, we will see different behavior for practicalsized input). moreover, these results concern the expressive power of transformers and do not apply to learning and generalization abilities. thus transformers' ability to model formal languages requires further investigation. ## definitions we consider the transformer as used in popular pretrained lm models such as bert and gpt, which is the encoder-only model of the original seq-to-seq architecture @xcite . the encoder consists of multiple layers with two blocks each: (1) self-attention block, (2) a feed-forward network (ffn). for 1 ≤ @xmath0, at the i-th step, the model takes as input the sequence s 1 , s 2 , . . . , s i where @xmath1. each input s i is first converted into an embedding vector using the function f e : σ → r d model and usually some form of positional encoding is added to yield the final input vector x i . the embedding dimension d model is also the dimension of intermediate vectors of the network. let x i := (x 1 , . . . , x i ) for @xmath2. in the self-attention block, the input vectors undergo linear transformations q(•), k(•), and v (•) yielding the corresponding query, key and value vectors, respectively. the self-attention mechanism takes as input a query vector q(x i ), key vectors k(x i ), and value vectors v (x i ). an attentionhead denoted by att(q( the output of a layer denoted by z i is computed by z @xmath3. the complete l-layer model is a repeated application of the single-layer model described above, which produces a vector z l i at its final layer where l denotes the last layer. the final output is obtained by applying a projection layer with some normalization or an ffn over the vectors z l i 's and is denoted by y @xmath4. residual connections and layer normalization are also applied to aid the learning process of the network. in an lm setting, when the transformer processes the input sequentially, each input symbol can only attend over itself and the previous inputs, masking is applied over the inputs following it. note that, providing positional information in this form via masked self-attention is also referred to as positional masking @xcite . a transformer model without positional encoding and positional masking is orderinsensitive. ## expressiveness results proposition 4.1. there exists a transformer as defined in section 3 that can recognize the family of languages shuffle-dyck. proof. let s 1 , s 2 , . . . , s n denote a sequence @xmath5, . . . , [ k-1 , ] 0 , . . . , ] k-1 }. the language shuffle-1 is equivalent to dyck-1. for any shuffle-k language, consider a model with d @xmath6, where the embedding function f e is defined as follows. for each type of open bracket [ j where,0 ≤ @xmath7, the vector f e ([ j ) has the value +1 and -1 at the indices 2j and 2j + 1, respectively. it has the value 0 at the rest of the indices. similarly for each closing bracket, the vector f e (] j ) has the value -1 and +1 at the indices 2j and 2j + 1, and it has the value 0 at the rest of the indices. for dyck-1, this would lead to f e ([) = [+1, -1] t and f e (]) = [-1, +1] t (with d @xmath8. we use a single-layer transformer where we set the matrix corresponding to linear transformation for key vectors to be null matrix, that is k(x) = 0 for all x. this will lead to equal attention weights for all inputs. the matrices corresponding to q(•) and v (•) are set to identity. thus, att(q( hence, at the i-th step, the selfattention block produces a vector a i which has the values σ([ j )-σ(] j ) i at indices 2j and the values σ(] j )-σ([ j ) i at indices 2j + 1, where σ(s) denotes the number of occurrence of the symbol s. for instance, in dyck-1, if in the first i inputs, there are σ([) open brackets and σ(]) closing brackets, then in a i , the value σ([) -σ(]) represents the depth (difference between the number of open and closing brackets) of the dyck-1 word at index i. hence, the first coordinate is the ratio of the depth of the dyck-1 word and its length at that index, while the other coordinate is its negative. we then apply a simple ffn with relu activation over the vector a i . the vector z @xmath9. the even indices of the vector z i will be nonzero if the number of open brackets of the corresponding type is greater than the number of closing brackets. a similar statement holds for the odd indices. thus, for a given word to be in shufflek, the values at odd indices of the vector z i must never be nonzero, and the values of all coordinates must be zero at the last step to ensure the number of open and closing brackets are the same. for an input sequence s 1 , s 2 , . . . , s n , the model will produce z 1 , . . . , z n based on the construction specified above. a word w belongs to language shuffle-k if z i,2j+1 = 0 for all 1 ≤ @xmath10, 0 ≤ @xmath11. this can be easily implemented by an additional layer of self-attention and feedforward network to classify a given sequence. the bottleneck for precision in the construction above is the calculation of values of the form in the vector a i . since in a finite precision setting with r bits, this can be computed up to a value exponential in r, our proof entails that transformers can recognize languages in shuffle-dyck for lengths exponential in the number of bits. using a similar logic, one can also show that transformers can recognize the family of languages boolexp-n (refer to lemma c.2). by setting the value vectors according to the arities of the operators, the model can obtain the ratio of the counter value of the underlying automata and the length of the input at each step via self-attention. although the above construction is specific to these language families, we provide a proof for a more general but restricted subclass of counter languages in the appendix (refer to lemma c.1). the above construction serves to illustrate how transformers can recognize such languages by indirectly doing relevant computations. as we will later see, this will also help us interpret how trained models recognize such languages. ## experimental setup in our experiments, we consider 27 formal languages belonging to different parts in the hierarchy of counter and regular languages. for each language, we generate samples within a fixed-length window for our training set and generate multiple validation sets with different windows of length to evaluate the model's generalization ability. for most of the languages, we generate 10k samples for our training sets within lengths 1 to 50 and create different validation sets containing samples with distinct but contiguous windows of length. the number of samples in each validation set is 2k, and the width of each window is about 50. for languages that have very few positive examples in a given window of length, such as (ab) * and a n b n c n , we train on all positive examples within the training window. similarly, each validation set contains all possible strings of the language for a particular range. ## results on counter languages we evaluated the performance of the model on 9 counter languages. figure 2: values of different coordinates of the output of self-attention block of the models trained on shuffle-2 and boolexp-3. the dotted lines are the scaled depth to length ratios for shuffle-2 and scaled counter value to length ratios for boolexp-3. we observe a near perfect pearson correlation coefficent of 0.99 between outputs of self attention block and the dl and cl ratios. ## results on regular languages we first examine the popular benchmark of tomita grammars. while the lstms generalize perfectly on all 7 languages, transformers are unable to generalize on 3 languages, all of which are non-starfree. note that, all star-free languages in tomita grammar have dot-depth 1. recognizing non-starfree languages requires modeling properties such as periodicity and modular counting. consequently, we evaluate the model on some of the simplest nonstar-free languages such as the languages (aa) * and parity. we find that they consistently fail to learn or generalize on such languages, whereas lstms of very small sizes perform flawlessly. ## discussion we showed that transformers can easily generalize on certain counter languages such as shuffle-dyck and boolean expressions in a manner similar to our proposed construction. our visualizations imply that transformers do so with a generalizable mechanism instead of overfitting on some statistical regularities. similar to natural languages, boolean expressions consist of recursively nested hierarchical constituents. recently, @xcite showed that pretraining lstms on formal languages like shuffle-dyck transfers to lm performance on natural languages. at the same time, our results show clear limitations of transformers compared to lstms on a large class of regular languages. evidently, the performance and capabilities of transformers heavily depend on architectural constituents e.g., the positional encoding schemes and the number of layers. recurrent models have a more automata-like structure wellsuited for counter and regular languages, whereas self-attention networks' structure is very different, which seems to limit their abilities for the considered tasks. our work poses a number of open questions. our results are consistent with the hypothesis that transformers generalize well for star-free languages with dot-depth 1, but not for higher depths. clarifying this hypothesis theoretically and empirically is an attractive challenge. what does the disparity between the performance of transformers on natural and formal languages indicate about the complexity of natural languages and their relation to linguistic analysis? (see also hahn (2020)). another interesting direction would be to understand whether certain modifications or recently proposed variants of transformers improve their performance on formal languages. regular and counter languages model some aspects of natural language while contextfree languages model other aspects such as hierarchical dependencies. although our results have some implications on them, we leave a detailed study on context-free languages for future work.