Theoretical Limitations of Self-Attention in Neural Sequence Models

Theoretical Limitations of Self-Attention in Neural Sequence Models Michael Hahn Stanford University mhahn2@stanford.edu Abstract Transformers are emerging as the new work- horse of NLP, showing great success across tasks. Unlike LSTMs, transformers process input sequences entirely through self-attention. Previous work has suggested that the compu- tational capabilities of self-attention to pro- cess hierarchical structures are limited. In this work, we mathematically investigate the com- putational power of self-attention to model formal languages. Across both soft and hard attention, we show strong theoretical limita- tions of the computational abilities of self- attention, finding that it cannot model periodic finite-state languages, nor hierarchical struc- ture, unless the number of layers or heads in- creases with input length. These limitations seem surprising given the practical success of self-attention and the prominent role assigned to hierarchical structure in linguistics, suggest- ing that natural language can be approximated well with models that are too weak for the for- mal languages typically assumed in theoretical linguistics. 1 Introduction Transformers are emerging as the new work- horse of NLP, achieving the state-of-the-art in tasks such as language modeling, machine transla- tion, and creating pretrained contextualized word embeddings. Eschewing recurrent computations, transformers are entirely based on self-attention, performing their computations largely in parallel. This enables them to scale to very long sequences (Vaswani et al., 2017; Dai et al., 2019; Child et al., 2019). On the other hand, it has been suggested that this limits their expressiveness, as they can- not process input sequentially (Tran et al., 2018; Dehghani et al., 2019; Shen et al., 2018a; Chen et al., 2018; Hao et al., 2019). One aspect thought to be challenging for sequencemodels is hierarchi- cal structure and recursion. Hierarchical structure is widely thought to be essential to modeling nat- ural language, in particular its syntax (Everaert et al., 2015). Consequently, many researchers have studied the capability of recurrent neural net- work models to capture context-free languages (e.g., Kalinke and Lehmann, 1998; Gers and Schmidhuber, 2001; Gr¨uning, 2006; Weiss et al., 2018; Sennhauser and Berwick, 2018; Korsky and Berwick, 2019) and linguistic phenomena involving hierarchical structure (e.g., Linzen et al., 2016; Gulordava et al., 2018). Some experimen- tal evidence suggests that transformers might not be as strong as LSTMs at modeling hierarchical structure (Tran et al., 2018), though analysis stud- ies have shown that transformer-based models encode a good amount of syntactic knowledge (e.g., Clark et al., 2019; Lin et al., 2019; Tenney et al., 2019). In this work, we examine these questions from a theoretical perspective, asking whether models entirely based on self-attention are theoretically capable of modeling hierarchical structures involv- ing unbounded recursion. Formally, we study their ability to perform two computations that are thought to be essential to hierarchical structure: First, their ability to correctly close brackets, a basic problemunderlying allnonregular context-free languages and formalized by the DYCK language (Chomsky and Sch¨utzenberger, 1963). Second, their ability to evaluate iterated negation, a basic component of the task of evaluating logical formulas, amounting to evaluating the PARITY of …

Content truncated to 500 words