Theoretical Limitations of Self-Attention in Neural Sequence Models

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.

Accepted by: Transactions of the Association for Computational Linguistics

References in corpus (6)

• A Structured Self-attentive Sentence Embedding
• Generating Long Sequences with Sparse Transformers
• On the Turing Completeness of Modern Neural Network Architectures
• BERT Rediscovers the Classical NLP Pipeline
• Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies
• On the Computational Power of RNNs

Cited by in corpus (26)

• A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions
• Screen Parsing: Towards Reverse Engineering of UI Models from Screenshots
• Addressing Some Limitations of Transformers with Feedback Memory
• Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages
• Transformer Grammars: Augmenting Transformer Language Models with Syntactic Inductive Biases at Scale
• Optimal Subarchitecture Extraction For BERT
• What Formal Languages Can Transformers Express? A Survey
• How Powerful are Decoder-Only Transformer Neural Models?
• Transferring Inductive Biases through Knowledge Distillation
• Going Beyond Linear Transformers with Recurrent Fast Weight Programmers
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers
• Formal Language Theory Meets Modern NLP
• Set-to-Sequence Methods in Machine Learning: a Review
• Recent Advances and Challenges in Deep Audio-Visual Correlation Learning
• PnG BERT: Augmented BERT on Phonemes and Graphemes for Neural TTS
• Understanding Cross-Lingual Syntactic Transfer in Multilingual Recurrent Neural Networks
• On the Dynamics of Training Attention Models
• I-BERT: Inductive Generalization of Transformer to Arbitrary Context Lengths
• Current Limitations of Language Models: What You Need is Retrieval
• Impartial Games: A Challenge for Reinforcement Learning
• N-ODE Transformer: A Depth-Adaptive Variant of the Transformer Using Neural Ordinary Differential Equations
• Using Artificial Populations to Study Psychological Phenomena in Neural Models
• Abstraction, Reasoning and Deep Learning: A Study of the "Look and Say" Sequence
• Enhancing Reinforcement Learning with discrete interfaces to learn the Dyck Language
• How LSTM Encodes Syntax: Exploring Context Vectors and Semi-Quantization on Natural Text
• How BPE Affects Memorization in Transformers