Despite their impressive performance in NLP, self-attention networks were recently proved to be limited for processing formal languages with hierarchical structure, such as Dyck k , the language consisting of well-nested parentheses of k types. This suggested that natural language can be approximated well with models that are too weak for formal languages, or that the role of hierarchy and recursion in natural language might be limited. We qualify this implication by proving that self-attention networks can process Dyck k,D , the subset of Dyck k with depth bounded by D , which arguably better captures the bounded hierarchical structure of natural language. Specifically, we construct a hard-attention network with D + 1 layers and O (log k ) memory size (per token per layer) that recognizes Dyck k,D , and a soft-attention network with two layers and O (log k ) memory size that generates Dyck k,D . Experiments show that self-attention networks trained on Dyck k,D generalize to longer inputs with near-perfect accuracy, and also verify the theoretical memory advantage of self-attention networks over recurrent networks. 1 1 Introduction Transformers (Vaswani et al., 2017) are now the undisputed champions across several benchmark leaderboards in NLP. The major innovation of this architecture, self-attention , processes input tokens in a distributed way, enabling efficient parallel computation as well as long-range dependency modelling. The empirical success of self-attention in NLP has led to a growing interest in studying its properties, with an eye towards a better understanding of the nature and characteristics of natural language (Tran et al., 2018; Papadimitriou and Juraf-sky, 2020). In particular, it was recently shown that self-attention networks cannot process various kinds of formal languages (Hahn, 2020; Bhattamishra et al., 2020a), among which particularly notable is Dyck k , the language of well-balanced brackets of k types. By the Chomsky-Schtzenberger Theorem (Chom-sky and Schtzenberger, 1959), any context-free language can be obtained from a Dyck k language through intersections with regular languages and homomorphisms. In other words, this simple language contains the essence of all context-free languages, i.e. hierarchical structure, center embedding, and recursion  features which have been long claimed to be at the foundation of human language syntax (Chomsky, 1956). Consider for example the long-range and nested dependencies in English subject-verb agreement: ( Laws ( the lawmaker ) [ writes ] [ and revises ]) [ pass ] . . . . The sentence structure is captured by Dyck 2 string (()[][])[]. Given the state-of-the-art performance of Transformers in parsing natural language (Zhang et al., 2020; He and Choi, 2019), the Dyck k blind spot seems very suggestive. If the world's best NLP models cannot deal with this simple language  generated by a grammar with k + 2 rules and recognized by a single-state pushdown automaton  does this not mean that the role of hierarchy and recursion in natural language must be limited? This question has of course, been extensively debated by linguists on the basis of both theoretical and psycholinguistic evidence (Hauser et al., 2002; Frank et al., 2012; Nelson et al., 2017; Brennan and Hale, 2019; Frank and Christiansen, 2018). So, what can self-attention networks tell us about natural language and recursion? Here we provide a new twist to this question by considering Dyck k,D , the subset of Dyck k with nesting depth at most D , and show that Transformers can process Input ( [ ] { [ ] ( ) } ) Layer 1 ( [ ] { [ ] ( ) } ) Layer 2 ( [ ] { [ ] ( ) } ) Layer 3 ( [ ] { [ ] ( ) } )  3,3 Input [ ] [ ( ( [ ] ) ) Layer 1 1 0 1 2 3 4 3 2 1 Layer 2 1 0 1 2 3 4 3 2 1  2,4 it. Dyck k,D models bounded (or finite) recursion, thus captures the hierarchical structure of human language much more realistically. For example, center-embedding depth of natural language sentences is known to rarely exceed three (Karlsson, 2007; Jin et al., 2018), and while pragmatics, discourse, and narrative can result in deeper recursion in language (Levinson, 2014), there is arguably a relatively small limit to the depth as well. In particular, we prove that self-attention networks can both recognize and generate Dyck k,D , with two conceptually simple yet different constructions (Figure 1). The first network requires D + 1 layers and a memory size of O (log k ) (per layer per token) to recognize Dyck k,D , using a distributed mechanism of parenthesis matching. The second network has two layers and memory size O (log k ) . It works by attending to all previous tokens to count the depth for each token in the first layer, and then uses this depth information to attend to the most recent unclosed open bracket in the second layer. Our constructions help reconcile the result in Hahn (2020) with the success of Transformers in handling natural languages. Our proof requires certain assumptions about the positional encodings, an issue that is often considered in empirical papers (Ke et al., 2021; Shaw et al., 2018; Wang et al., 2020; Shiv and Quirk, 2019) but not in the more theoretical literature. First, positional encodings must have log n bits when the input length is n , as otherwise different positions would share the same representation. More importantly, positional encodings should support easy position comparisons, since token order is vital in formal language processing. Our experiments show that two standard practices, namely learnable or fixed sine/cosine positional encodings, cannot generalize well on Dyck k,D beyond the training input lengths. In contrast, using a single fixed scalar monotonic positional encoding such as pos / n achieves near-perfect accuracy even on inputs significantly longer than the training ones. Our findings provide a novel perspective on the function of positional encodings, and implies that different applications of self-attention networks (in this case, natural vs. formal language) may require different model choices. Our theoretical results also bring about interesting comparisons to recurrent networks (e.g. RNNs, LSTMs) in terms of the resource need to process hierarchical structure. While recurrent networks with finite precision need at least ( D log k ) memory to process Dyck k,D (Hewitt et al., 2020), our second construction requires only O (log k ) memory but a O (log n ) precision. In experiments where precision is not an issue for practical input lengths ( < 10 4 ), we confirm that a Transformer requires less memory than a LSTM to reach high test accuracies. This may help explain why Transformers outperform RNNs/LSTMs in syntactical tasks in NLP, and shed light into fundamental differences between recurrent and non-recurrent sequence processing. Our work primarily relates to the ongoing effort of characterizing theoretical abilities (Prez et al., 2019; Bhattamishra et al., 2020b; Yun et al., 2020) and limitations of self-attention networks, particularly through formal hierarchical structures like Dyck k . Hahn (2020) proves that (even with positional encodings) hard-attention Transformers cannot model Dyck k , and soft-attention Transformers with bounded Lipschitz continuity cannot model Dyck k with perfect cross entropy. Bhattamishra et al. (2020a) prove a soft-attention network with positional masking (but no positional encodings) can solve Dyck 1 but not Dyck 2 . Despite the expressivity issues theoretically posed by the above work, empirical findings have shown Transformers can learn Dyck k from finite samples and outperform LSTM (Ebrahimi et al., 2020). Our work addresses the theory-practice discrepancy by using positional encodings and modeling Dyck k,D . A parallel line of work with much lengthier tradition (Elman, 1990; Das et al., 1992; Steijvers and Grnwald, 1996) investigates the abilities and limitations of recurrent networks to process hierarchical structures. In particular, RNNs or LSTMs are proved capable of solving context-free languages like Dyck k given infinite precision (Korsky and Berwick, 2019) or external memory (Suzgun et al., 2019; Merrill et al., 2020). However, Merrill et al. (2020) also prove RNNs/LSTMs cannot process Dyck k without such assumptions, which aligns with experimental findings that recurrent networks perform or generalize poorly on Dyck k (Bernardy, 2018; Sennhauser and Berwick, 2018; Yu et al., 2019). Hewitt et al. (2020) propose to consider Dyck k,D as it better captures natural language, and show finite-precision RNNs can solve Dyck k,D with ( D log k ) memory. For the broader NLP community, our results also contribute to settling whether self-attention networks are restricted to model hierarchical structures due to non-recurrence, a concern (Tran et al., 2018) often turned into proposals to equip Transformers with recurrence (Dehghani et al., 2019; Shen et al., 2018; Chen et al., 2018; Hao et al., 2019). On one hand, Transformers are shown to encode syntactic (Lin et al., 2019; Tenney et al., 2019; Manning et al., 2020) and word order (Yang et al., 2019) information, and dominate syntactical tasks in NLP such as constituency (Zhang et al., 2020) and dependency (He and Choi, 2019) parsing. On the other hand, on several linguistically-motivated tasks like English subject-verb agreement (Tran et al., 2018), recurrent models are reported to outperform Transformers. Our results help address the issue by confirming that distributed and recurrent sequence processing can both model hierarchical structure, albeit with different mechanisms and tradeoffs. Consider the vocabulary of k types of open and close brackets  =  i  [ k ] {(cid:104) i , (cid:105) i } , and define Dyck k      ( ,  being special start and end tokens) to be the formal language of well-nested brackets of k types. It is generated starting from X through the following context-free grammar: X  (cid:15) | (cid:104) i X (cid:105) i X ( i  [ k ]) (1) where (cid:15) denotes the empty string. Intuitively, Dyck k can be recognized by sequential scanning with a stack (i.e., a pushdown au-tomaton). Open brackets are pushed into the stack, while a close bracket causes the stack to pop, and the popped open bracket is compared with the current close bracket (they should be of the same type). The depth of a string w 1: n at position i is the stack size after scanning w 1: i , that is, the number of open brackets left in the stack: d ( w 1: i ) = count ( w 1: i , (cid:104) )  count ( w 1: i , (cid:105) ) (2) Finally, we define Dyck k,D to be the subset of Dyck k strings with depth bounded by D : Dyck k,D = (cid:26) w 1: n  Dyck k (cid:12)(cid:12)(cid:12)(cid:12) max i  [ n ] d ( w 1: i )  D (cid:27) That is, a string in Dyck k,D only requires a stack with bounded size D to process. We consider the encoder part of the original Transformer (Vaswani et al., 2017), which has multiple layers of two blocks each: (i) a self-attention block and (ii) a feed-forward network (FFN). For an input string w 1: n    , each input token w i is converted into a token embedding via f e :   R d model , then added with a position encoding p i  R d model . Let x i,(cid:96)  R d model be the i -th representation of the (cid:96) -th layer ( i  [ n ] , (cid:96)  [ L ] ). Then x i, 0 = f e ( w i ) + p i (3) a i,(cid:96) = Att (cid:96) ( Q (cid:96) ( x i ) , K (cid:96) ( x ) , V (cid:96) ( x )) (4) x i,(cid:96) +1 = F (cid:96) ( a i,(cid:96) ) (5) Attention In each head of a self-attention block, the input vectors x 1: n undergo linear transforms Q, K, V yielding query, key, and value vectors. They are taken as input to a self-attention module, whose t -th output, Att( Q x i , K x , V x ) , is a vector a i = (cid:80) j  [ T ]  j V x j , where  1: n = softmax ( (cid:104) Q x i , K x 1 (cid:105) ,    , (cid:104) Q x i , K x n (cid:105) ) . The final attention output is the concatenation of multihead attention outputs. We also consider variants of the basic model along these directions: (i) Hard attention , as opposed to soft attention described above, where hardmax is used in place for softmax (i.e. Att( Q x i , K x , V x ) = V x j (cid:48) where j (cid:48) = arg max j (cid:104) Q x i , K x j (cid:105) ). Though impractical for NLP, it has been used to model formal languages (Hahn, 2020). (ii) Positional masking , where  1: i (past) or  i : n (future) is masked for position i . Future-positional masking is usually used to train auto-regressive models like GPT-2 (Radford et al., 2019). Feed-forward network A feed-forward network F transforms each self-attention output vector a i  F ( a i ) individually. It is usually implemented as a multi-layer perceptron (MLP) with ReLU activations. Residual connections (He et al., 2016) and layer normalization (Ba et al., 2016) are two optional components to aid learning. Positional encodings Vaswani et al. (2017) proposes two kinds of positional encoding: (i) Fourier features (Rahimi and Recht, 2007), i.e. sine/cosine values of different frequencies; (ii) learnable features for each position. In this work we propose to use a single scalar i/n to encode position i  [ n ] , and show that it helps process formal languages like Dyck k,D , both theoretically and empirically. Precision and memory size We define precision to be the number of binary bits used to represent each scalar, and memory size per layer ( d model ) to be the number of scalars used to represent each token at each layer. The memory size ( L  d model ) is the total memory used for each token. For a Transformer with L layers and input w 1: i , we can use a decoder (MLP + softmax) on the final token output x i,L to predict w i +1 . This defines a language model f  ( w i +1 | w i ) where  denotes Transformer and decoder parameters. We follow previous work (Hewitt et al., 2020) to define how a language model can generate a formal language: Definition 3.1 (Language generation) . Language model f  over  (cid:63) generates a language L   (cid:63) if there exists (cid:15) > 0 such that L = { w 1: n   (cid:63) |  i  [ n ] , f  ( w i | w 1: i  1 )  (cid:15) } . We also consider language recognition by a language classifier g  ( w 1: i ) , where a decoder on x i,L instead predicts a binary label. In this section we state our theoretical results along with some remarks. Proof sketches are provided in the next section, and details in Appendix A,B,C. Theorem 4.1 (Hard-attention, Dyck k,D recognition) . For all k, D  N + , there exists a ( D + 1) layer hard-attention network that can recognize Dyck k,D . It uses both future and past positional masking heads, positional encoding of the form i/n for position i , O (log k ) memory size per layer, and O (log n ) precision, where n is the input length. Theorem 4.2 (Soft-attention, Dyck k,D generation) . For all k, D  N + , there exists a 2-layer soft-attention network that can generate Dyck k,D . It uses future positional masking, positional encoding of form i/n for position i , O (log k ) memory size per layer, and O (log n ) precision, where n is the input length. The feed-forward networks use residual connection and layer normalization. Theorem 4.3 (Precision lower bound) . For all k  N + , no hard-attention network with o (log n ) precision can recognize Dyck k, 2 where n is the input length. Required precision Both constructions require a precision increasing with input length, as indicated by Theorem 4.3. The proof of the lower bound is inspired by the proof in Hahn (2020), but several technical improvements are necessary; see Appendix C. Intuitively, a vector with a fixed dimension and o (log n ) precision cannot even represent n positions uniquely. The required precision is not unreasonable, since log n is a small overhead to the n tokens the system has to store. Comparison to recurrent processing Hewitt et al. (2020) constructs a 1-layer RNN to generate Dyck k,D with ( D log k ) memory, and proves it is optimal for any recurrent network. Thus Theorem 4.2 establishes a memory advantage of self-attention networks over recurrent ones. However, this is based on two tradeoffs: (i) Precision . Hewitt et al. (2020) assumes O (1) precision while we require O (log n ) . (ii) Runtime . Runtime of recurrent and self-attention networks usually scale linearly and quadratically in n , respectively. Comparison between two constructions Theorem 4.2 requires fewer layers ( 2 vs. D ) and memory size ( O (log k ) vs. O ( D log k ) ) than Theorem 4.1, thanks to the use of soft-attention, residual connection and layer normalization. Though the two constructions are more suited to the tasks of recognition and generation respectively (Section 5), each of them can also be modified for the other task. Connection to Dyck k In Hahn (2020) it is shown that no hard-attention network can recognize Dyck k even for k = 1 . Theorem 4.1 establishes that this impossibility can be circumvented by bounding the depth of the Dyck language. Hahn (2020) also points out soft-attention networks can be limited due to bounded Lipschitz continuity. In fact, our Theorem 4.2 construction can also work on Dyck k with some additional assumptions (e.g. feed n also in input embeddings), and we circumvent the impossibility by using laying normalization, which may have an O ( n ) Lipschitz constant. More details are in Appendix B.4. Our insight underlying the construction in Theorem 4.1 is that, by recursively removing matched brackets from innermost positions to outside, each token only needs to attend to nearest unmatched brackets to find its matching bracket or detect error within D layers. Specifically, at each layer (cid:96)  D , each token will be in one of three states (Figure 2 (c)): (i) Matched , (ii) Error , (iii) Unmatched , and we leverage hard-attention to implement a dynamic state updating process to recognize Dyck k,D . Representation For an input w 1: n      , the representation at position i of layer (cid:96) has five parts x i,(cid:96) = [ t i , o i , p i , m i,(cid:96) , e i,(cid:96) ] : (i) a bracket type embedding t i  R (cid:100) log k (cid:101) that denotes which bracket type ( 1    k ) the token is (or if the token is start/end token); (ii) a bracket openness bit o i  { 0 , 1 } , where 1 denotes open brackets (or start token) and 0 denotes close one (or end token); (iii) a positional encoding scalar p i = i/n ; (iv) a match bit m i,(cid:96)  { 0 , 1 } , where 1 denotes matched and 0 unmatched; (v) an error bit e i,(cid:96)  { 0 , 1 } , where 1 denotes error and 0 no error. Token identity parts t i , o i , p i are maintained unchanged throughout layers. The match and error bits are initialized as e i, 0 = m i, 0 = 0 . The first D layers have identical self-attention blocks and feed-forward networks, detailed below. Attention Consider the (cid:96) -th self-attention layer ( (cid:96)  [ D ] ), and denote x i = x i,(cid:96)  1 , m i = m i,(cid:96)  1 , a i = a i,(cid:96) , y i = x i,(cid:96) for short. We have 3 attention heads: (i) an identity head Att id , where each token only attends to itself with attention output a id i = x i ; (ii) a left head Att left with future positional masking; (iii) a right head Att right with past positional masking. The query, key, and value vectors for Att left are defined as Q x i = 1  R , K x i = p i  m i  R , V x i = x i  R d model , so that a left i = x j 1 , j 1 = arg max j<i ( j/n  m j ) is the representation of the nearest unmatched token to i on its left side. is the representation of the nearest unmatched token to i on its right side. The attention output for position i is the concatenation of these three outputs: a i = [ a id i , a left i , a right i ] = [ x i , x j 1 , x j 2 ] . Feed-forward network (FFN) Following the notation above, the feed-forward network F : a i  y i serves to update each position's state using information from x j 1 , x j 2 . The high level logic (Fig-ure 2 (c)) is that, if w i is an open bracket, its potential matching half should be w j = w j 2 ( j 2 > i ), otherwise it should be w j = w j 1 ( j 1 < i ). If w i and w j are one open and one close, they either match (same type) or cause error (different types). If w i and w j are both open or both close, no state update is done for position i . Besides, token identity parts t i , o i , p i are copied from a id i to pass on. The idea can be translated into a language of logical operations (  ,  ,  ) plus a SAME ( t , t (cid:48) ) operation, which returns 1 if vectors t = t (cid:48) and 0 otherwise: y i = [ t i , o i , p i , m (cid:48) i , e (cid:48) i ] m (cid:48) i = m i  ( o i   o j 2  s 1 )  (  o i  o j 1  s 2 ) e (cid:48) i = e i  ( o i   o j 2   s 1 )  (  o i  o j 1   s 2 ) s 1 = SAME ( t i , t j 1 ) s 2 = SAME ( t i , t j 2 ) ( [ ] ( ] ) Layer 1 ( [ ] ( ] ) Layer 2 ( [ ] ( ] ) Layer 3 output: 0/1 ( [ ] ( ] ) FFN ([](]) ( [ ] ( ] ) ([](]) ( [ ] ( ] ) ([](]) ( [ ] ( ] )       ( [ ] ( ] ) matched error unmatched unmatched w 1: n x 1: n ( [ ] ( ] ) As we show in Appendix A, a multi-layer perception with ReLU activations can simulate all operations (  ,  ,  , SAME ) , thus the existence of our desired FFN. Final layer At the ( D + 1) -th layer, the self attention is designed as Q x i = 1  R , K x i = e i +1  m i  R , V x i = ( e i , m i )  R 2 . If all brackets are matched without error ( ( e i , m i ) = (0 , 1) ), all keys would be 0 , and the attention output of the last token a n would be (0 , 1) . If any bracket finds error ( e i = 1) or is not matched ( m i = 0) , the key would be at least 1 and a n would not be (0 , 1) . An FNN that emulates ( a, b ) (cid:55)  a  b will deliver y n as the recognition answer. Our Theorem 4.2 construction takes advantage of soft attention, residual connection, and layer normalization to calculate each token depth and translate it into a vector form at the first layer. Using the depth information, at the second layer each w i can attend to the stack-top open bracket at the position, in order to decide if open brackets or which type of close brackets can be generated as the next token (Figure 3). bracket type embedding t i , bracket openness bit o i , position encoding p i already specified in Section 5.1. The last part d i,(cid:96)  R 2 is used to store depth information for position i , and initialized as d i, 0 = (0 , 0) . First Layer  Depth Counting The first self-attention layer has two heads, where an Att id head is still used to inherit t i , o i , p i , and a future positional masking head 2 Att d aims to count depth with Q x i = K x i = 1 and V x i = 2 o i  1 , resulting in uniform attention scores and attention output a di = (cid:80) j  i 1 i  (2 o j  1) = d ( w 1: i ) /i . However, our goal is to enable matching based on depth d i = d ( w 1: i ) , and the attention output d i /i isn't readily usable for such a purpose: the denominator i is undesirable, and even a scalar d i cannot easily attend to the same value using dot-product attention. Thus in the first feed-forward network, we leverage residual connection and layer normalization to transform d i /i (cid:55) d i = (cos(  ( d i )) , sin(  ( d i ))) (6) where  ( d ) = arctan (cid:16) d D +2  d (cid:17) has an unique 2 Here we assume w i +1: n is masked for position i , just for convenience of description. value for every d  { 0 ,    , D + 1 } , so that d i  d j (cid:40) = 1 d i = d j < 1  1 10 D 2 d i (cid:54) = d j (7) The representation by the end of first layer is x i, 1 = [ t i , o i , p i , d i ] . The full detail for the first FFN is in Appendix B.1. Second layer  Depth Matching The second self-attention layer has a depth matching hard-attention head Att match , with query, key, value vectors as Q x i = [20 D 2  d i , 1 , 2]  R 4 , K x i = [ d i , p i , o i ]  R 4 , V x i = x i , so that attention score (cid:104) Q x i , K x j (cid:105) = 20 D 2 d i  d j + j/n + 2 o j (cid:40) = 20 D 2 + 2 + j/n d i = d j , o j = 1  20 D 2 + 1 otherwise would achieve its maximum when w j ( j  i ) is the open bracket (or start token) closest to w i with d j = d i . The attention output is a i = [ a id i , a match i ] = [ x i , x j ] where j = max { j  i | d i = d j  o j = 1 } . With such a [ x i , x j ] , the second-layer FFN can readily predict what w i +1 could be. It could be any open bracket when d i < D (i.e. cos(  ( d i )) > cos(  ( D )) ), and it could be a close bracket with type as t j (or end token if w j is start token). The detailed construction for such a FFN is in Appendix B.2. On Dyck k Generation In fact, this theoretical construction can also generate Dyck k , as intuitively the O (log n ) precision assumption allows counting depth up to O ( n ) . But it involves extra conditions like feeding n into network input, and may not be effectively learned in practice. Please refer to details in Appendix B.4. Connection to Empirical Findings Our theoretical construction explains the observation in Ebrahimi et al. (2020): the second layer of a two-layer Transformer trained on Dyck k often produces virtually hard attention, where tokens attend to the stack-top open bracket (or start token). It also explains why such a pattern is found less systematically as input depth increases, as (6) is hard to learn and generalize to unbounded depth in practice. Our constructions show the existence of self-attention networks that are capable of recognizing and generating Dyck k,D . Now we bridge theoretical insights into experiments, and study whether such networks can be learned from finite samples and generalize to longer input. The answer is af-firmative when the right positional encodings and memory size are chosen according to our theory. We first present results on Dyck 8 , 10 (Sec-tion 6.1) as an example Dyck k,D language to investigate the effect of different positional encoding schemes, number of layers, and hidden size on the Transformer performance, and to compare with the LSTM performance. We then extend the Transformer vs. LSTM comparison on more Dyck k,D languages ( k  { 2 , 8 , 32 , 128 } , D  { 3 , 5 , 10 , 15 } ) in Section 6.2. Finally, we apply 1 2 3 4 5 10 # Layers 0.6 0.7 0.8 0.9 1.0 C l o s e A cc u r a cy the novel scalar positional encoding to natural language modeling with some preliminary findings (Section 6.3). Setup For Dyck 8 , 10 , we generate training and validation sets with input length n  700 , and test set with length 700 < n  1400 . We train randomly initialized Transformers using the Huggingface library (Wolf et al., 2019), with one future positional masking head, L  { 1 , 2 , 3 , 4 , 5 , 10 } layers, and a default memory size d model = 30 . We search for learning rates in { 0 . 01 , 0 . 001 } , run each model with 3 trials, and report the average accuracy of generating close brackets, the major challenge of Dyck k,D . More setup details are in Appendix D.1. Positional Encodings We compare 3 types of positional encodings: (i) Fourier features ( COS ); (ii) learnable features ( LEARN ); (iii) a scalar i/ 6000 for position i ( POS /N ). Note that (i, ii) are original proposals in Vaswani et al. (2017), where positional encoding vectors are added to the token embed-dings, while our proposal (iii) encodes the position as a fixed scalar separated from token embeddings. On the validation set of Dyck 8 , 10 (see Appendix D.2), all three models achieve near-perfect accuracy with L  2 layers. On the test set (Fig-ure 4(a)) however, only POS /N maintains near-perfect accuracy, even with L = 10 layers. Meanwhile, LEARN and COS fail to generalize, because encodings for position 700 < i  1400 are not learned (for LEARN ) or experienced (for COS ) during training. The result validates our theoretical construction, and points to the need for separate and systemic positional encodings for processing long and order-sensitive sequences like Dyck k,D . Memory Size and Comparison with LSTM We compare a two-layer Transformer ( POS /N ) with a one-layer LSTM 3 (Hochreiter and Schmidhu-ber, 1997) using varying per-layer memory sizes d model  { 10 , 20 ,    , 100 } . As Figure 4 (b) shows, the Transformer consistently outperforms the LSTM on the validation set. On the test set (Figure 4 (c)), the Transformer and the LSTM first achieve a > 90% accuracy using d model = 20 and 40 respectively, and an accuracy of > 95% with d model = 30 and 50 , respectively. These findings agree with our theoretical characterization that self-attention networks have a memory advantage over recurrent ones. Setup In order to generalize some of the above results, we generate a wide range of Dyck k,D languages with different vocabulary sizes ( k  { 2 , 8 , 32 , 128 } ) and recursion bounds ( D  { 3 , 5 , 10 , 15 } ). We continue to compare the one-layer LSTM versus the two-layer Transformer ( POS /N ). For each model on each language, we perform a hyperparameter search for learning rate in {0.01, 0.001} and memory size d model  { 10 , 30 , 50 } , and report results from the best setting based on two trials for each setting. 3 LSTMs only need one layer to process Dyck k,D (Hewitt et al., 2020), while Transformers at least need two in our constructions. We also experimented with two-layer LSTMs but did not find improved performance. Results The validation and test accuracy of the models are reported in Figure 5, and more fine-grained results for each d model  { 10 , 30 , 50 } are in Appendix D.2. The Transformer attains a > 99 . 9% validation accuracy and a > 94% test accuracy across all languages, strengthening the main claim that self-attention networks can learn Dyck k,D languages and generalize to longer input. On the other hand, the validation and test accuracy of the LSTM model are less than 80% when the vocabulary size and recursion depth are large, i.e. ( k, D )  { (32 , 15) , (128 , 10) , (128 , 15) } 4 , which reconfirms Transformers' memory advantage under limited memory ( d model  50 ). In Section 6.1, we show a Transformer with the scalar positional encoding scheme ( POS /N ) can learn Dyck k,D and generalize to longer input, while traditional positional encoding schemes (( COS ), ( LEARN )) lead to degraded test performance. To investigate whether such a novel scheme is also useful in NLP tasks, we train two RoBERTa 5 models ( POS /N , LEARN ) from scratch on the WikiText-103 dataset (Merity et al., 2017) for 150 epochs. Figure 6 shows the masked language modeling loss on both training and validation sets. By the end of the training, POS /N has a slightly larger validation loss (1.55) than LEARN (1.31). But throughout the optimization, POS /N shows a gradual decrease of loss while LEARN has a sudden drop of loss around 20-30 epochs. We believe it will be interest-4 Note that Hewitt et al. (2020) only reports D  { 3 , 5 } . 5 We also tried language modeling with GPT-2 models, and POS /N has slightly larger train/validation losses than LEARN throughout the training. Interestingly, using no positional encoding leads to the same loss curves as LEARN , as positional masking leaks positional information. ing for future work to explore how POS /N performs on different downstream tasks, and why POS /N seems slightly worse than LEARN (at least on this MLM task), though theoretically it provides the complete positional information for Transformers. These topics will contribute to a deeper understanding of positional encodings and how Transformers leverage positional information to succeed on different tasks. In this paper, we theoretically and experimentally demonstrate that self-attention networks can process bounded hierarchical languages Dyck k,D , even with a memory advantage over recurrent networks, despite performing distributed processing of sequences without explicit recursive elements. Our results may explain their widespread success at modeling long pieces of text with hierarchical structures and long-range, nested dependencies, including coreference, discourse and narratives. We hope these insights can enhance knowledge about the nature of recurrence and parallelism in sequence processing, and lead to better NLP models. Our work is mainly theoretical with no foreseeable ethical issues.
abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain method abstain abstain abstain result method abstain abstain result abstain objective result abstain method abstain abstain other other other other method other other other other abstain other other abstain abstain abstain abstain abstain method method abstain abstain abstain abstain other other abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain method abstain method result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain 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 abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain other abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain method abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain result abstain result abstain result abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain