Source-linked AI summary
Theoretical Limitations of Self-Attention in Neural Sequence Models
Michael Hahn
TL;DR
The paper asks whether self-attention can model formal languages that capture periodic finite-state behavior and hierarchical recursion. It mathematically analyzes hard and soft attention and finds that transformers cannot robustly model noncounter-free regular languages or basic hierarchical structure without resources that grow with input length. The authors frame these asymptotic limitations as compatible with good performance on shorter natural-language sequences.
Problem
The paper addresses whether self-attention can theoretically model hierarchical structures involving unbounded recursion and formal languages such as PARITY and DYCK.
Method
The paper uses mathematical analyses and different proof methods for hard and soft self-attention in incremental sequence modeling.
Results
Transformers cannot robustly model noncounter-free regular languages or basic hierarchical structure, including PARITY and 2DYCK, even with infinite precision.
Takeaways & Limitations
Self-attention cannot in general emulate stacks or general finite-state automata, whereas the paper notes that recurrent networks can model these structures under stated conditions.
Takeaways & Limitations
The results are asymptotic: transformers may perform perfectly on inputs up to any fixed bound N, but layers, heads, or parameter norms must increase with N.
Abstract
from arXiv · showhide
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.
1 Introduction
This section motivates a theoretical study of self-attention's ability to model hierarchical structure and formal languages. It introduces the paper's focus on bracket closure, iterated negation, and limitations across attention settings.
- Motivation: Transformers achieve state-of-the-art results while relying entirely on parallel self-attention rather than recurrent computation.This design enables scaling to very long sequences but has prompted concerns about expressiveness for sequential processing.
- Motivation: Hierarchical structure and recursion are considered important for modeling natural-language syntax.Prior research has therefore examined recurrent models' ability to capture context-free languages and hierarchical linguistic phenomena.
- Research questions: The paper theoretically tests whether self-attention can model unbounded recursion through bracket closure in DYCK and iterated negation represented by PARITY.These computations are presented as basic components of hierarchical structure and logical-formula evaluation.
- Main result: Transformers and similar self-attention models cannot solve DYCK or PARITY unless parameter number or size increases with input length.The results extend to large classes of regular and context-free languages.
- Approach: The study provides theoretical results for both hard and soft attention using different proof methods.The hard-attention results require no further assumptions on activation functions or parameter norms, while the soft-attention results assume smooth activations.
- Organization: The paper proceeds from related work and self-attention definitions to formal languages, hard- and soft-attention proofs, and discussion.This organization mirrors the progression from model specification to formal limitations.
2 Related Work
Prior work studied recurrent networks, transformers, and self-attention through experiments and theory. This paper addresses a comparatively new theoretical question about self-attention's language-recognition limitations.
- Self-attention studies: Earlier literature repeatedly suggested that self-attention restricts computation because transformers cannot process inputs sequentially.Some claims were proposed without detailed proofs.
- Empirical comparisons: Experiments found that LSTMs were better than transformers at learning hierarchical structure in tasks including subject-verb agreement and logical-formula evaluation.Other experiments examined word-order information and syntactic representations in self-attention models.
- Theoretical scope: Theoretical transformer research included unbounded autoregressive decoding for emulating Turing machines, whereas this paper studies incremental sequence modeling bounded by input length n.The distinction is between language recognition and computation with an unbounded number of decoding steps.
- Recurrent architectures: Recurrent-network theory has examined non-regular context-free languages as simple models of recursion and hierarchical structure.Experimental studies considered counter languages such as a^n b^n, well-bracketed strings, and hierarchical phenomena in natural-language data.
- Recurrent architectures: Finite-precision LSTMs recognize a subset of counter languages, while arbitrary-precision RNNs can emulate pushdown automata and recognize all deterministic context-free languages.The cited results distinguish recurrent architectures by precision and computational capability.
3 Self-Attention
The paper defines transformer self-attention over embedded input and positional sequences, then describes layered multi-head computation. It analyzes both soft and hard attention for sequence classification.
- Input representation: Each input symbol comes from a finite alphabet, is mapped to an embedding, and is combined with a positional embedding.The end-of-sequence symbol is included in the input sequence.
- Input representation: Layer 0 represents each position by applying a function to its input and positional embeddings.The resulting vectors initialize the subsequent transformer layers.
- Layered computation: A transformer has a fixed number L of layers, each containing H attention heads that compute position-dependent attention scores.The scores combine activations from the previous layer and may use dot-product or additive attention.
- Layered computation: Each head computes activations by weighting value vectors according to attention weights, followed by a feedforward activation function with a skip connection.The formulation includes linear transformations of previous-layer activations.
- Attention variants: Soft attention obtains weights through softmax, whereas hard attention selects an actual maximum attention value.The paper analyzes both variants; ties in hard attention are resolved by selecting the earliest maximal position, though other tie rules also work.
- Language recognition: Language recognition is formalized as sequence-to-sequence classification into labels 1 or 0 using the final activation after reading the end-of-sequence symbol.A softmax probability vector is computed for the label.
4 Regular and Context-Free Languages
The paper uses PARITY and 2DYCK as representative regular and context-free languages. Their roles connect finite-state periodicity and hierarchical bracket structure to the broader limitations studied.
- Representative languages: The paper analyzes regular and context-free language recognition through two prominent representatives.PARITY represents a regular language, while 2DYCK represents a context-free language.
- PARITY: PARITY contains bit strings with an even number of 1s and is recognized by a two-state finite-state automaton.It is described as the simplest noncounter-free, or periodic, regular language.
- PARITY: PARITY also models whether iterated negations contain an even or odd number of nested negations.Thus, inability to compute PARITY implies inability to evaluate logical formulas accurately in that setting.
- 2DYCK: 2DYCK consists of correctly bracketed words using two bracket types and serves as a simple model of hierarchical structure.The cited Chomsky-Schützenberger theorem connects variants of 2DYCK to context-free languages through regular intersection and homomorphisms.
- PARITY: Failure to compute PARITY extends to almost every regular language that is not counter-free.The formal qualification is that the language's syntactic morphism is not quasi-aperiodic.
5 Results for Hard Attention
For hard attention, the paper uses input restrictions to iteratively reduce transformer depth until predictions depend on only a bounded number of input positions. This proves that hard-attention transformers cannot recognize PARITY or 2DYCK, while some less-sensitive languages remain representable.
- Depth reduction: The depth-reduction method repeatedly captures attention with fixed inputs, removes layers, and leaves predictions dependent on a bounded number of positions independent of input length.At each stage, heads depend on boundedly many lower-layer activations or inputs, allowing the preceding layer to be collapsed and removed.
- Input restrictions: Input restrictions fix selected symbols, leaving the restricted transformer's output dependent only on unfixed inputs.A restriction maps each position to a fixed symbol or ∗; only positions mapped to ∗ remain variable.
- Main results: Hard-attention transformers cannot model PARITY or 2DYCK.The proof uses combinatorial arguments without assumptions about activation functions, parameter norms, or discrete internal representations.
- Applications: For PARITY, unrestricted bits that do not influence the output can still change language membership, preventing correct recognition for sufficiently large inputs.After restriction, the output depends on c inputs, whereas flipping any single PARITY bit changes membership.
- Applications: For 1DYCK, and therefore 2DYCK, restricted inputs remain compatible with both well- and nonwell-bracketed strings while predictions depend on boundedly many positions.The construction fixes an initial block to opening brackets and a final block to closing brackets before applying the theorem's restriction.
- Scope: The method applies generally to sufficiently sensitive languages, whereas 1∗ and anbn can be modeled because fixing a few symbols can force nonmembership.These languages are described as immune to the depth-reduction method and recognizable with suitable hard-attention constructions.
6 Results for Soft Attention
For soft attention, fixed-depth transformers cannot robustly model distributions over PARITY and 2DYCK as inputs grow, because each individual symbol has vanishing influence on the final prediction.
- Scope of the soft-attention results: Soft attention limitations are weaker than the hard-attention results: the paper proves cross-entropy bounds rather than recognition-accuracy bounds.Perfect-accuracy bounds for Boolean formulas would separate LTC0 and NC1, an open complexity-theory problem.
- Main results: As n →∞, PARITY next-symbol cross-entropy converges to unigram chance level, while 2DYCK remains at least ε above optimal cross-entropy.The 2DYCK gap is a constant ε > 0.
- Mechanism: Because prediction functions are Lipschitz-continuous, similar activations cannot yield sharply different predictions for inputs differing in one symbol.This blocks robust predictions for tasks whose correct output is highly sensitive to individual symbols.
- 2DYCK analysis: For 2DYCK, some prefixes require distinguishing closing-bracket types after changing one earlier symbol, but soft attention changes the corresponding predictions only by O(1/n).On correctly typed closing brackets, the second prediction task incurs asymptotic cross-entropy of at least log2.
- Activation-sensitivity bound: Exchanging one input symbol changes the final activation by O(1/n), with constants depending on parameter-matrix norms and the number of layers.This follows from an induction over the fixed L layers.
- Assumption and scope: The proof assumes a number of layers L bounded independently of input length, and the strategy also applies to other fixed-depth smooth architectures.The paper gives one-dimensional temporal convolutions with average pooling as an example.
7 Discussion
The results establish strong theoretical limitations for self-attention, while leaving open how much these asymptotic constraints affect practical language modeling. They also suggest that successful natural-language modeling may not require the full formal power often assumed in theoretical linguistics.
- Theoretical implications: Even with infinite precision, transformers cannot robustly model noncounter-free regular languages or basic hierarchical structure.Hard-attention results also hold independently of activation functions and parameter magnitude; soft-attention results rule out perfect cross-entropies for these formal-language distributions.
- Asymptotic scope: The limitations are asymptotic: sufficiently long PARITY and 2DYCK inputs force errors, although finite-length performance can remain perfect.For any length bound N, a transformer can be constructed to achieve perfect accuracy or cross-entropy for all n ≤ N.
- Comparison with recurrence: Avoiding recurrence may leave self-attention formally weaker than recurrent architectures for modeling finite-state and hierarchical computations.The paper contrasts these limitations with recurrent networks such as LSTMs, which can perfectly emulate finite-state automata under Markovian state-transition and emission distributions.
- Practical implications: Whether these theoretical limitations hinder practical syntactic generalization remains unresolved.Empirical work reports that both recurrent and transformer models can struggle with syntactic generalization, while perplexity can be partly dissociated from syntactic knowledge.
- Practical implications: Many aspects of natural language may be modeled well by methods formally too weak for the languages typically assumed in theoretical linguistics.Restricted use of recursive structure due to cognitive factors is proposed as one possible explanation.
8 Conclusion
The paper formally investigates self-attention's ability to model regular languages and hierarchical structure, finding limitations across hard and soft attention even with infinite precision.
- 8 Conclusion: Transformers cannot model periodic regular languages or basic recursion with hard or soft attention, even when infinite precision is allowed.The result implies that self-attention cannot generally emulate stacks or general finite-state automata.