Self-Attention Networks Can Process Bounded Hierarchical Languages

Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, Karthik Narasimhan

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.

Hierarchical structure in natural language represented as nested dependencies.

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.

Theoretical mechanisms for (a) recognition through layer-wise bracket matching and (b) generation through depth tracking.

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

BibTeX
@inproceedings{yao2021self,
  author = {Shunyu Yao and Binghui Peng and Christos H. Papadimitriou and Karthik Narasimhan},
  title = {{Self-Attention Networks Can Process Bounded Hierarchical Languages}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=aMp0zJvD5u},
}

Loading related content...

Figure