Abstract
Theoretical limitations have long suggested that Transformers are incapable of processing hierarchical structures like Dyck languages. However, this work demonstrates that self-attention networks can effectively recognize and generate hierarchical languages when the nesting depth is bounded ($\mathsf{Dyck}_{k,D}$). Through theoretical constructions and empirical validation, we show that Transformers are not only capable of handling these structures but are also more memory-efficient than LSTMs. Furthermore, with appropriate positional encodings, these models exhibit near-perfect generalization to longer sequences.
Introduction
A significant "theory-practice gap" exists in Natural Language Processing: while Transformers dominate the field, theoretical work (notably by Hahn, 2020) suggests they cannot process the hierarchical structures essential to human syntax, specifically the $\mathsf{Dyck}_k$ language of well-balanced parentheses. This paper by Yao et al. resolves this tension by focusing on $\mathsf{Dyck}_{k,D}$, where the nesting depth $D$ is bounded.
Human language is rarely infinitely recursive; center-embedding typically stays within a few levels of depth. By limiting depth, the problem shifts from a theoretical impossibility to a practical computational task that Transformers can solve efficiently.
Theoretical Constructions
The authors bridge the gap using two primary constructions for recognition and generation:
1. Recognition via Hard-Attention
The researchers prove that a $(D+1)$-layer Transformer using "hard" attention (selecting a single token) can recognize $\mathsf{Dyck}_{k,D}$. The mechanism is recursive: each layer identifies and "cancels out" the innermost matched brackets. This process reduces the effective depth of the string for subsequent layers until the entire hierarchy is processed.
2. Generation via Soft-Attention
For the task of predicting the next valid token, a 2-layer "soft" attention network is shown to be sufficient. In this model, the first layer calculates the current nesting depth for every token in the sequence. The second layer then utilizes this depth information to identify the most recent unclosed bracket, determining the valid next token.
The Role of Positional Encodings
A key finding is that the failure of Transformers to generalize in previous studies was often due to positional encodings rather than the attention mechanism itself. Standard learnable or sinusoidal encodings do not provide a systematic way to compare distances outside the training range. The authors propose a simple scalar monotonic encoding ($i/n$), which allows the model to compare relative positions effectively, leading to near-perfect generalization on sequences twice as long as those seen during training.
Results and Memory Efficiency
Empirical tests on synthetic $\mathsf{Dyck}_{k,D}$ datasets (with $k$ up to 128 types of brackets and depth $D$ up to 15) confirmed the theoretical sufficiency of 2-layer models for generation.
A major insight is the architectural advantage of Transformers over Recurrent Neural Networks (RNNs). While an RNN requires $\Omega(D \log k)$ memory to process these languages, the Transformer construction requires only $O(\log k)$ memory per token per layer. In head-to-head comparisons, Transformers achieved high accuracy with significantly smaller hidden dimensions than LSTMs, particularly as the complexity ($k$ and $D$) increased.
Conclusion and Future Work
This research demonstrates that Transformers are theoretically and practically equipped to handle the bounded hierarchical nature of human language. While the proposed $i/n$ positional encoding is highly effective for formal languages, it showed a slight performance trade-off on natural language tasks like WikiText-103. Future research will focus on developing positional encodings that combine the generalization capabilities of scalar methods with the optimization ease of standard Fourier-based encodings.
Summary updated