Theoretical Limitations of Self-Attention in Neural Sequence Models

Michael Hahn

Abstract Paper Share

Theory and Formalism in NLP (Linguistic and Mathematical) TACL Paper

Session 1A: Jul 6 (05:00-06:00 GMT)
Session 2B: Jul 6 (09:00-10:00 GMT)
Abstract: Transformers are emerging as the new workhorse of NLP, showing great success across tasks. Unlike LSTMs, transformers process input sequences entirely through self-attention. Previous work has suggested that the computational capabilities of self-attention to process hierarchical structures are limited. In this work, we mathematically investigate the computational power of self-attention to model formal languages. Across both soft and hard attention, we show strong theoretical limitations of the computational abilities of self-attention, finding that it cannot model periodic finite-state languages, nor hierarchical structure, unless the number of layers or heads increases with input length. These limitations seem surprising given the practical success of self-attention and the prominent role assigned to hierarchical structure in linguistics, suggesting that natural language can be approximated well with models that are too weak for the formal languages typically assumed in theoretical linguistics.
You can open the pre-recorded video in a separate window.
NOTE: The SlidesLive video may display a random order of the authors. The correct author list is shown at the top of this webpage.

Similar Papers

Self-Attention is Not Only a Weight: Analyzing BERT with Vector Norms
Goro Kobayashi, Tatsuki Kuribayashi, Sho Yokoi, Kentaro Inui,
A representative figure from paper srw.115
Quantifying Attention Flow in Transformers
Samira Abnar, Willem Zuidema,
A representative figure from paper main.385
DeFormer: Decomposing Pre-trained Transformers for Faster Question Answering
Qingqing Cao, Harsh Trivedi, Aruna Balasubramanian, Niranjan Balasubramanian,
A representative figure from paper main.411