Can the Transformer Learn Nested Recursion with Symbol Masking?

Jean-Philippe Bernardy, Adam Ek, Vladislav MaraevACL 2021 · DOI

TL;DR

This paper investigates whether Transformer models, trained with a BERT-like masked language modeling objective, can learn to match nested parentheses in generalized Dyck languages. While Transformers show promising accuracy above random chance, their performance suggests they learn a simple counting strategy rather than true recursive parsing, limiting their ability to generalize to deeper or longer-nested structures.

What Problem Does This Paper Address?

The remarkable success of Transformer models in various NLP tasks has led to their widespread adoption. However, a key question remains: can these models truly understand and generalize complex linguistic structures, particularly those involving recursion? Context-free languages, characterized by nested structures like matching parentheses, serve as a crucial benchmark for testing this capability. Previous work has explored this, but this paper specifically examines the effectiveness of the popular BERT-style masked language modeling (MLM) approach for learning generalized Dyck languages, focusing on generalization to deeper nesting and longer distances than seen during training.

Methods

The researchers employed an encoder-only Transformer architecture, similar to BERT. For training, they used a masked language modeling strategy: 15% of closing parenthesis tokens were randomly masked. These masked tokens were replaced with a special mask token (80% of the time), a random token (10%), or the original token (10%). For testing, a random closing parenthesis was masked, and the model was tasked with predicting its correct matching opening parenthesis. The model's performance was evaluated based on its accuracy in predicting the correct closing parenthesis type.

Datasets

The study generated custom datasets of strings composed of five types of matching parentheses (e.g., (), [], {}, <>, «»). These datasets were specifically constructed to control for:

  • Maximum distance: D[MaxDist = d] limits the distance between a closing parenthesis and its corresponding opening parenthesis.
  • Maximum depth: D[MaxDepth = d] limits the nesting level of parentheses.

The training and testing sets were varied in terms of these parameters to assess generalization capabilities. For instance, models were trained on D[MaxDepth = 3] and tested on D[MaxDepth = 9].

Key Insights and Ideas

  • Above-chance performance, but not true recursion: Transformers trained with MLM can achieve accuracy significantly above random baselines when generalizing to longer distances and deeper nesting. However, the analysis suggests this performance stems from a simple parenthesis counting strategy rather than a true understanding of recursive structure.
  • Masking strategy matters: The BERT-like MLM strategy, while effective for some tasks, appears to hinder the learning of genuine recursive parsing. The paper suggests that auto-regressive models might be better suited for tasks requiring deep generalization of recursive structures.
  • Model architecture influences generalization: Different configurations of layers and heads in the Transformer showed varying degrees of generalization. The (2,8) model (2 layers, 8 heads) generally performed best, suggesting that a wider attention mechanism might be more beneficial for this task.
  • Attention patterns reveal strategy: Analysis of attention heads indicated that shallower layers often focus on immediate neighbors, while deeper layers might distribute attention more broadly. In some configurations, attention heavily focused on masked symbols, which aligns with a counting strategy.

Key Results

  • Generalization to longer distances: Models trained on D[MaxDist = 9] and tested on D[MaxDist = 19] achieved accuracies consistently above 50%, with the (2,8) model showing the best performance. Interestingly, accuracy was better for very long distances (beginning to end of sequence) than for intermediate ones.
  • Generalization to deeper nesting: When trained on D[MaxDepth = 3] and tested on D[MaxDepth = 9], the (2,8) model again performed best, followed by (4,4) and then (8,2). The (8,2) model struggled particularly with shallow nesting in this scenario.
  • Accuracy breakdown: The (8,2) model showed a peculiar pattern where it performed poorly at short distances but better at longer ones, while (4,4) and (2,8) models performed well at short distances but saw accuracy drop before recovering at very long distances.

Limitations and Future Work

The primary limitation identified is that the Transformer, under the tested MLM strategy, does not appear to learn true recursive parsing. Instead, it relies on a simpler counting mechanism. This limits its ability to generalize to structures significantly more complex than those seen during training.

The authors recommend that for tasks critically requiring generalization to longer distances or deeper nesting, auto-regressive models (either Transformer-based or RNNs) should be preferred over BERT-like masked models. Future work could explore different masking strategies or alternative training objectives to better equip Transformers for recursive structure learning.

Summary updated

BibTeX
@inproceedings{bernardy2021can,
  author = {Jean-Philippe Bernardy and Adam Ek and Vladislav Maraev},
  title = {{Can the Transformer Learn Nested Recursion with Symbol Masking?}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  doi = {10.18653/v1/2021.findings-acl.67},
}
Figure