Theoretical Limitations of Self-Attention in Neural Sequence Models

By Michael Hahn. 2019

401 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Model Architectures

Citations in the corpus

Explainable Multi-hop Verbal Reasoning Through Internal Monologue (2021, methodology): “Finally, it has been shown theoretically and empirically that neural networks suffer from the compositionality generalization problem (Hupkes et al., 2020; Hahn, 2020).”
PnG BERT: Augmented BERT on Phonemes and Graphemes for Neural TTS (2021, background): “The top 2 Transformer layers in PnG BERT were fine-tuned, with the rest part frozen.”
What Context Features Can Transformer Language Models Use? (2021, background): “While input sequences x can in principle be made arbitrarily long, there are both theoretical and practical limits to transformers’ ability to make effective use of it (Hahn, 2020; Wang et al., 2019).”
Reasoning with Transformer-based Models: Deep Learning, but Shallow Reasoning (2021, background): “Hahn [2020] studied the theoretical limitations of transformers.”
Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective (2023, result): “Besides affirmative results, other works characterized the expressivity limitation of Transformers via the perspective of modeling formal languages [23, 6, 57] or simulating circuits [24, 37, 36].”
A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions (2023, neutral): “A potential cause is the limitations of soft attention (Hahn, 2020; Chi-ang and Cholak, 2022), where attention becomes diluted across positions as sequence length increases.”
Hallucination is Inevitable: An Innate Limitation of Large Language Models (2024, background): “Attention mechanism, a key component of transformer-based LLMs, can also contribute to hallucination [36], possibly because attention across tokens is diluted as the sequence length grows [10, 22].”
$O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers (2020, background): “Hence, our result does not contradict a recent paper by Hahn [12] which studies the limitation of Transformers for varying n.”
Can Transformers Learn to Solve Problems Recursively? (2023, background): “Understanding Transformers Work on understanding the underlying mechanisms of transformers spans many angles, from categorizing computational capabilities [10, 44, 45, 43] by measuring performance on synthetic tasks, to deriving theoretical arguments [22, 25, 30, 31, 18], to analyzing the functional”
Generating bug-fixes using pretrained transformers (2021, background): “In general we relieve the model of some of the difficulty of parsing the language’s formal grammar, which is disproportionately difficult for transformers (Hahn, 2020).”
TransNeXt: Robust Foveal Visual Perception for Vision Transformers (2023, neutral): “RepLKNet-31B shows a more exaggerated performance decay, with a top-1 accuracy of only 0.9% at a resolution of 640 2 , which to some extent reveals the limitations of the super-large convolution kernel scheme.”
Faith and Fate: Limits of Transformers on Compositionality (2023, methodology): “We observe that all analyzed models match the Relative Information Gain prediction that o 1 (whether the first element goes into the output sequence or not) should be the easiest value to predict (see Figures 30, 31, and 32).”
Transferring Inductive Biases through Knowledge Distillation (2020, background): “While theoretically, both recurrent neural networks (RNNs) and Transformers can deal with ﬁnite hierarchical structures, empirical results indicate the superiority of RNNs over Transformers [37, 6, 14].”
Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (2024, background): “The ability of self-attention to create low-complexity circuits has been recognized (Edelman et al., 2022; Hahn, 2020; Merrill et al., 2021), as well as its capacity to form declarative programs (Weiss et al., 2021), and Turing machines (Dehghani et al., 2018; Giannou et al., 2023; Pérez et al.,…”
A Review on Language Models as Knowledge Bases (2022, background): “Furthermore, previous work demonstrates that there are theoretical limitations to transformers that prevents them from performing certain types of reasoning tasks (Hahn, 2020; Bhattamishra et al., 2020; Helwe et al., 2021).”
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes (2022, background): “There is a long line of work investigating the capabilities [69, 15, 77, 51, 76, 7, 78], limitations [25, 6], applications [37, 17, 49], and internal workings [19, 65, 71, 18, 48] of Transformer models.”
CRANE: Reasoning with constrained LLM generation (2025, unknown): “However, following existing works (Hahn, 2020; Merrill & Sabharwal, 2023; Li et al., 2024) and for simplicity in the theoretical setup in Section 3, we assume that the output of L on any input string xxx is deterministic in both constrained and unconstrained settings.”