Self-Attention Networks Can Process Bounded Hierarchical Languages (2021)

Abstract: 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.

## introduction transformers @xcite 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 @xcite . in particular, it was recently shown that selfattention networks cannot process various kinds of formal languages @xcite , among which particularly notable is dyck k , the language of well-balanced brackets of k types. by the @xcite , 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 @xcite . consider for example the long-range and nested dependencies in english subject-verb agreement: 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 ## related work our work primarily relates to the ongoing effort of characterizing theoretical abilities @xcite @xcite and limitations of self-attention networks, particularly through formal hierarchical structures like dyck k . @xcite 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. @xcite 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 @xcite . 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 @xcite @xcite 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 @xcite . however, @xcite 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 @xcite @xcite . @xcite 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 @xcite often turned into proposals to equip transformers with recurrence @xcite @xcite . on one hand, transformers are shown to encode syntactic @xcite @xcite and word order @xcite information, and dominate syntactical tasks in nlp such as constituency @xcite and dependency @xcite parsing. on the other hand, on several linguistically-motivated tasks like english subject-verb agreement @xcite , 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. ## theoretical results 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, @xmath0, 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, @xmath1, there exists a 2-layer softattention 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 @xmath2, 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 selfattention 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 @xmath3. 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. ## experiments our constructions show the existence of selfattention 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 affirmative when the right positional encodings and memory size are chosen according to our theory. we first present results on dyck 8,10 (section 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 (@xmath4, 8, 32, 128}, @xmath5, 5, 10, 15}) in section 6.2. finally, we apply the novel scalar positional encoding to natural language modeling with some preliminary findings (section 6.3). ## discussion 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.