Source-linked AI summary
Self-Attention Networks Can Process Bounded Hierarchical Languages
Shunyu Yao, Binghui Peng, Christos Papadimitriou, Karthik Narasimhan
TL;DR
The paper asks whether self-attention’s known limits on unbounded hierarchical languages imply limits for modeling natural-language hierarchy. It proves constructions for bounded-depth Dyck languages and reports successful longer-input generalization and a memory advantage over recurrent networks in experiments.
Problem
Prior results showed self-attention networks cannot process Dyck_k, a formal language that captures hierarchical structure, center embedding, and recursion.
Source: §1 · p. 1Method
Results
Learnable and fixed sine/cosine positional encodings generalize poorly beyond training lengths, whereas fixed scalar monotonic pos/n achieves near-perfect accuracy on significantly longer inputs; experiments also find Transformers need less memory than LSTMs for high test accuracy.
Source: §1 · p. 2Takeaways & Limitations
The results indicate that distributed and recurrent sequence processing can both model hierarchical structure, with different mechanisms and tradeoffs.
Source: §7 · p. 9The theoretical comparison requires O(log n) precision for self-attention, while recurrent-network results assume O(1) precision; their runtimes typically scale quadratically and linearly in n, respectively.
Source: §4 · p. 5
Abstract
from arXiv · showhide
Despite their impressive performance in NLP, self-attention networks were recently proved to be limited for processing formal languages with hierarchical structure, such as $\mathsf{Dyck}_k$, the language consisting of well-nested parentheses of $k$ types. This suggested that natural language can be approximated well with models that are too weak for formal languages, or that the role of hierarchy and recursion in natural language might be limited. We qualify this implication by proving that self-attention networks can process $\mathsf{Dyck}_{k, D}$, the subset of $\mathsf{Dyck}_{k}$ with depth bounded by $D$, which arguably better captures the bounded hierarchical structure of natural language. Specifically, we construct a hard-attention network with $D+1$ layers and $O(\log k)$ memory size (per token per layer) that recognizes $\mathsf{Dyck}_{k, D}$, and a soft-attention network with two layers and $O(\log k)$ memory size that generates $\mathsf{Dyck}_{k, D}$. Experiments show that self-attention networks trained on $\mathsf{Dyck}_{k, D}$ generalize to longer inputs with near-perfect accuracy, and also verify the theoretical memory advantage of self-attention networks over recurrent networks.
1 Introduction
The paper addresses the tension between self-attention’s success in NLP and proofs that it cannot process unbounded Dyck languages, whose nested structure represents core features of context-free languages. It shows that self-attention can process depth-bounded Dyck languages and reports that positional-encoding choice matters for generalization and memory comparisons with recurrent networks.
1 Introduction
- Dyck_k is a notable formal-language test because context-free languages can be obtained from it through intersections with regular languages and homomorphisms.The passage connects its hierarchical structure, center embedding, and recursion with features claimed to underlie human syntax.Source: §1 · p. 1
- Dyck_k,D bounds nesting depth, an approximation the paper presents as more realistic for language because center embedding rarely exceeds depth three, though discourse can involve deeper recursion.The authors also note that pragmatics, discourse, and narrative can produce deeper recursion.Source: §1 · pp. 1–2
- Self-attention networks recognize and generate Dyck_k,D using distinct constructions: a D+1-layer hard-attention recognizer and a two-layer soft-attention generator, each with O(log k) memory per token per layer.Recognition uses distributed parenthesis matching; generation first counts depth, then finds the most recent unclosed open bracket.Source: §1 · p. 2
- Learnable and fixed sine/cosine positional encodings generalize poorly beyond training lengths, while fixed scalar monotonic encoding pos/n achieves near-perfect accuracy on significantly longer inputs.The paper argues that formal- and natural-language applications may require different positional-encoding choices.Source: §1 · p. 2
- Finite-precision recurrent networks need at least Ω(D log k) memory for Dyck_k,D, whereas the second self-attention construction uses O(log k) memory with O(log n) precision.For practical input lengths below 10^4, experiments confirm that a Transformer uses less memory than an LSTM to reach high test accuracy.Source: §1 · p. 2
2 Related work
Related work establishes both limits and capabilities for recurrent and self-attention models on hierarchical languages. This paper positions bounded-depth Dyck languages as a way to address the discrepancy between theoretical limits and empirical performance.
2 Related work
- Prior work proved that self-attention has limits on Dyck languages, while finite-sample experiments found Transformers can learn Dyck_k and outperform LSTMs; this paper addresses that discrepancy using positional encodings and bounded depth.Hahn (2020) proves hard-attention Transformers cannot model Dyck_k and soft-attention Transformers with bounded Lipschitz continuity cannot model it with perfect cross entropy; Bhattamishra et al. (2020a) show positional masking solves Dyck_1 but not Dyck_2.Source: §2 · p. 3
- RNNs and LSTMs can solve Dyck_k with infinite precision or external memory, but not without those assumptions; finite-precision RNNs solve Dyck_k,D with Θ(D log k) memory.The cited empirical findings also report recurrent models perform or generalize poorly on Dyck_k.Source: §2 · p. 3
- The paper frames its contribution as showing that distributed and recurrent sequence processing can both model hierarchical structure, but through different mechanisms and tradeoffs.The surrounding debate contrasts Transformer syntactic-task successes with reports that recurrent models outperform them on some linguistically motivated tasks.Source: §2 · p. 3
3 Preliminaries
The preliminaries define bounded-depth Dyck languages and specify the self-attention and language-modeling framework used in the paper. They distinguish language generation, in which a model predicts next tokens, from recognition, in which a classifier assigns a binary label.
3.1 Dyck Languages
- Dyck_k consists of well-nested brackets of k types, and Dyck_k,D is its subset whose nesting depth is bounded by D.The paper describes depth as the stack size after scanning a prefix: the number of open brackets remaining.Source: §3.1 · p. 3
3.2 Self-attention Networks
- The encoder adds positional encodings to token embeddings and processes them through self-attention and feed-forward blocks; attention combines value vectors using weights from query-key similarity.The paper also considers hard attention, positional masking, and a scalar position encoding i/n; memory size is counted as scalars per token per layer.Source: §3.2 · pp. 3–4
3.3 Language Generation and Recognition
- For generation, a decoder predicts the next token from the final representation of the input prefix, while recognition uses a decoder to predict a binary label for the input.The paper defines generation by a positive probability threshold for every token of strings in the language, and recognition by a classifier output of 1.Source: §3.3 · p. 4
4 Theoretical Results
The section proves that self-attention networks can recognize and generate bounded-depth Dyck languages, then compares their resource requirements with recurrent networks. The constructions require precision that grows with input length, and the comparison involves both memory and runtime tradeoffs.
Theoretical results
- A hard-attention network recognizes Dyck_{k,D} with D + 1 layers, while a two-layer soft-attention network generates it; both use O(log k) memory per layer.The hard-attention construction uses positional masking, and the soft-attention construction uses O(log n) precision.Source: §4 · p. 4
- No hard-attention network with o(log n) precision can recognize Dyck_{k,2}, and both constructions require precision that grows with input length.The paper explains that a fixed-dimensional vector with o(log n) precision cannot represent n positions uniquely.Source: §4 · p. 4
Comparison to recurrent processing
- The soft-attention construction uses O(log k) memory versus Θ(D log k) for recurrent networks, trading O(1) precision for O(log n) and linear for quadratic runtime in n.Hewitt et al. (2020) prove the recurrent memory requirement is optimal; the runtime comparison describes the usual scaling of the two architectures.Source: §4 · pp. 4–5
Comparison between two constructions
- The soft-attention construction requires fewer layers and less memory than the hard-attention construction, a difference attributed to soft attention, residual connections, and layer normalization.Each construction can also be modified for the other task, although they are better suited to generation and recognition, respectively.Source: §4 · p. 5
Connection to Dyck_k
- Bounding nesting depth circumvents the hard-attention impossibility result for Dyck_k; soft-attention generation also uses layer normalization, which may have an O(n) Lipschitz constant.The soft-attention construction can work on Dyck_k with additional assumptions, such as including n in the input embeddings.Source: §4 · p. 5
5 Constructions
The paper gives two constructions for bounded-depth Dyck languages: a hard-attention network recognizes them by iteratively matching brackets, while a soft-attention network uses token depths to identify the current stack top for generation.
5.1 (D + 1)-layer Hard-Attention Network
- At each of D matching layers, hard attention finds the nearest unmatched token on either side, and token states track matched brackets, errors, or unmatched brackets.The final layer returns recognition only when every bracket is matched and no error was detected.Source: §5.1 · p. 5
- The hard-attention construction updates a bracket’s state when it and its nearest candidate are opposite bracket types, marking a match or an error according to whether their types agree.The feed-forward network implements the state update using logical operations and a bracket-type equality test.Source: §5.1 · pp. 5–6
5.2 Two-layer Soft-Attention Network
- The soft-attention construction first counts each token’s depth, then uses that information to attend to the closest earlier open bracket at the same depth.Residual connections and layer normalization transform the first-layer depth output into a vector representation used for matching.Source: §5.2 · pp. 6–7
- Using the attended stack-top bracket, the second-layer feed-forward network predicts possible next tokens: an open bracket below depth D, or a close bracket of the stack-top type.If the attended position is the start token, the next token can instead be the end token.Source: §5.2 · pp. 6–7
- The soft-attention construction can also generate unbounded Dyck_k in theory, but this requires conditions such as supplying n as input and may not be learned effectively in practice.The construction relies on O(log n) precision to count depth up to O(n).Source: §5.2 · p. 7
6 Experiments
The experiments test whether self-attention networks can learn bounded Dyck languages and generalize to longer inputs, comparing positional encodings and memory requirements before a preliminary WikiText-103 evaluation. Across the Dyck evaluations, the Transformer generalizes well with POS/N and outperforms the LSTM under limited memory, while POS/N has higher validation loss than LEARN on WikiText-103.
6 Experiments
- The experiments test finite-sample learning and longer-input generalization, comparing encodings, depth, and memory across Dyck languages before a preliminary WikiText-103 evaluation.The study asks whether networks can learn the constructions and generalize beyond training input lengths.Source: §6 · pp. 7–8
6.1 Evaluation on Dyck8,10
- On longer-input Dyck8,10 tests, only POS/N retains near-perfect accuracy, even at 10 layers; COS and LEARN fail to generalize.All three encodings achieve near-perfect validation accuracy with at least two layers.Source: Figure 4 · p. 8, §6.1 · p. 8
Memory Size and Comparison with LSTM
- On longer-input tests, >95% accuracy requires dmodel=30 for the Transformer versus 50 for the LSTM.The compared models are a two-layer POS/N Transformer and a one-layer LSTM.Source: Figure 4 · p. 8, Memory Size and Comparison with LSTM · p. 8
6.2 Evaluation on More Dyckk,D Languages
- Across tested Dyckk,D languages, the Transformer reaches >99.9% validation and >94% test accuracy; LSTM accuracy falls below 80% on the largest settings.The LSTM falls below 80% for (k, D) ∈ {(32, 15), (128, 10), (128, 15)}.Source: Figure 5 · p. 9, §6.2 · p. 9
6.3 Evaluation on WikiText-103
- After 150 WikiText-103 epochs, POS/N has validation loss 1.55 versus LEARN's 1.31.POS/N loss decreases gradually, while LEARN has a sudden drop around epochs 20–30.Source: Figure 6 · p. 9, §6.3 · p. 9
7 Discussion
The paper concludes that self-attention networks can process bounded hierarchical languages, with a memory advantage over recurrent networks. The results may help explain their success on long text with hierarchical structures and nested dependencies.
7 Discussion
- Self-attention processes bounded hierarchical languages with a memory advantage over recurrent networks, potentially explaining success on long text with nested dependencies.The paper identifies coreference, discourse, and narratives as examples.Source: §7 · p. 9
Ethical Consideration
The authors report no foreseeable ethical issues for this mainly theoretical work.
Ethical Consideration
- The work is mainly theoretical and has no foreseeable ethical issues.Source: Ethical Consideration · p. 9
A Construction Details of Section 5.1
The appendix supplies gate-simulation details and elaborates on the recognition and generation constructions. It describes how position and depth information support bracket matching and output selection.
A Construction Details of Section 5.1
- A constant-layer neural network can simulate AND, OR, NOT, SAME, GREATERTHAN, and EQUAL gates.The construction details describe logical and arithmetic gate operations.Source: A Construction Details of Section 5.1 · p. 13
B Construction details of Section 5.2
- The generation construction records depth and matched-bracket information for the generation token, extending the recognition construction.The generation output is read from the generation token's representation at the last layer.Source: A Construction Details of Section 5.1 · p. 13
B.1 First Layer FFN
- The first attention layer represents depth at each position as d_i/i; an MLP transformation preserves the bracket-type, openness, and position entries.Source: §B.1 · p. 14
B.2 Second Layer FFN
- The final layer selects an open bracket or its matched close bracket, with special handling at maximum depth and sequence length.The construction uses n−i information to handle the sequence-length boundary.Source: §B.2 · p. 14
B.3 Extension to Recognition task
The appendix extends the constructions to recognition and to unbounded Dyck languages, using depth matching to select the relevant open bracket. It states a two-layer soft-attention construction for generating Dyck_k.
B.3 Extension to Recognition task
- A three-layer Transformer extends the construction to recognition by matching a close bracket to the nearest earlier open bracket at the required depth.The construction uses a final layer to separate error bits from matching bits.Source: §B.3 · p. 15
- A three-layer soft-attention network generates Dyck_k,D using future positional masking, i/n positional encodings, O(log k) memory, and O(log n) precision.The stated feed-forward networks use residual connections and layer normalization.Source: §B.3 · p. 15
B.4 Extension to Dyckk
- The Dyck_k extension bypasses Hahn's lower bound because its layer normalization is not constant-Lipschitz and can be O(n)-Lipschitz in the proof.The passage describes this as an extension of the recognition construction.Source: §B.4 · p. 15
- A two-layer soft-attention network generates Dyck_k using future positional masking, O(log k) memory, and O(log n) precision.Its feed-forward networks use residual connections and layer normalization.Source: §B.4 · p. 15
C Theoretical limits for finite position encoding
This section gives a precision lower bound for recognizing bounded-depth Dyck languages and sketches how fixing a small number of input positions limits attention. It also describes the experimental data and metric setup.
C Theoretical limits for finite position encoding
- No Transformer with o(log n) precision can recognize Dyck_k,D inputs of length more than n; the lower bound concerns the bounded-depth language and quantifies precision by input length.The result is incomparable with Hahn (2020): it gives a precision bound for bounded-depth Dyck_k,D, while Hahn’s applies to languages with depth Ω(n) and allows arbitrary positional-encoding precision.Source: C Theoretical limits for finite… · pp. 16–17
- The proof fixes o(n) input positions so attention heads can catch only a sublinear number of positions, limiting recognition of Dyck_k,D.The analysis permits arbitrary attention masking and positional encodings, residual connections, and arbitrary feed-forward functions.Source: C Theoretical limits for finite… · p. 17
D.1 Setup
- The experiments sample stack decisions for Dyck_k,D; training, validation, and test sets contain 2 × 10^6, 2 × 10^5, and 10^6 tokens, respectively.Performance is measured by close-bracket prediction accuracy; the paper reports E_l p_l rather than mean_l p_l.Source: §D.1 · pp. 18–19
D.2 More Results
The additional results report near-perfect validation accuracy for positional-encoding variants with at least two layers, and show similar performance for two- and five-layer Transformers across tested settings.
D.2 More Results
- All positional-encoding schemes reach near-perfect validation accuracy on Dyck8,10 with at least two layers.Figure 7 reports the validation results.Source: Figure 7 · p. 19, §D.2 · p. 19
- A five-layer Transformer performs similarly to a two-layer Transformer, and both can learn Dyck_k,D without overfitting or degraded performance.Figure 8 breaks down validation and test results across k ∈ {2, 8, 32, 128} and D ∈ {3, 5, 10, 15}.Source: Figure 8 · p. 19, §D.2 · p. 19