Transition-based Parsing with Stack-Transformers

Ramón Fernandez Astudillo, Miguel Ballesteros, Tahira Naseem, Austin Blodgett, Radu Florian

Abstract

Modeling the parser state is key to good performance in transition-based parsing. Recurrent Neural Networks considerably improved the performance of transition-based systems by modelling the global state, e.g. stack-LSTM parsers, or local state modeling of contextualized features, e.g. Bi-LSTM parsers. Given the success of Transformer architectures in recent parsing systems, this work explores modifications of the sequence-to-sequence Transformer architecture to model either global or local parser states in transition-based parsing. We show that modifications of the cross attention mechanism of the Transformer considerably strengthen performance both on dependency and Abstract Meaning Representation (AMR) parsing tasks, particularly for smaller models or limited training data.

Introduction

Transition-based parsing is a fundamental approach to converting natural language sentences into structured graphs, such as dependency trees or Abstract Meaning Representations (AMR). This method operates like a state machine, utilizing a buffer for unprocessed words and a stack for words currently being processed and linked. The parser executes a sequence of actions—such as shifting a word from the buffer to the stack or reducing stack elements into a parent-child relationship—to incrementally construct the final parse.

Transition-based parsing process showing SHIFT and REDUCE operations on stack and buffer states.

Historically, modeling the "parser state" at each step relied on hand-crafted features or Recurrent Neural Networks (RNNs) like the Stack-LSTM. While RNNs excel at global state modeling, they are computationally expensive and slow to train. Modern Transformers offer superior speed and capacity but typically treat input as a flat sequence, lacking the structural "priors" necessary to track the dynamic contents of the stack and buffer. The Stack-Transformer aims to bridge this gap by imbuing the Transformer architecture with structural awareness without sacrificing its inherent efficiency.

The Stack-Transformer Architecture

The core innovation of the Stack-Transformer is a modification of the cross-attention mechanism in a sequence-to-sequence Transformer decoder. Instead of allowing all attention heads to attend to the entire input sentence, the model introduces:

  1. Specialized Attention Heads: Specific heads are dedicated to focusing exclusively on the current contents of the stack or the buffer.
  2. Dynamic Masking: Based on the sequence of actions taken up to time step $t$, the model identifies which tokens reside in the stack and buffer. It then applies a dynamic mask to the specialized cross-attention heads, restricting their "view" to the relevant memory structure.
  3. Labeled SHIFT Multi-task Learning: To further refine internal representations, the authors experimented with a multi-task objective where the model predicts the Part-of-Speech (POS) tag or the specific word being moved during a SHIFT action.

This design allows the model to maintain a clear, structured representation of the parsing state while benefiting from the parallelizable nature of the Transformer.

Experimental Results

The Stack-Transformer was evaluated on the Penn Treebank (PTB) for dependency parsing and the AMR 1.0 and 2.0 datasets for semantic parsing.

Performance comparison of various Stack-Transformer configurations across PTB and AMR datasets.

Key Findings

  • Structural Bias Enhances Performance: Even when integrated with powerful pre-trained models, explicit modeling of the stack and buffer provides a significant performance boost. As shown in the results table, the Stack-Transformer (row c) consistently outperforms the vanilla Transformer baseline (row a) across all metrics.
  • The Importance of the Buffer: Ablation studies (comparing rows e and f) revealed that modeling the buffer (anticipating future tokens) is often more critical for overall performance than modeling the stack (tracking processed tokens).
  • Efficiency and Scalability: The Stack-Transformer achieved a 10x speedup in training compared to previous Stack-LSTM implementations. Furthermore, its advantages were most pronounced in low-resource settings—either with smaller datasets (AMR 1.0) or reduced model capacity (small models a-c).
  • State-of-the-Art Performance: On the Penn Treebank, the Stack-Transformer improved the Labeled Attachment Score (LAS) by over 2 percentage points. On the smaller AMR 1.0 set, the model saw a dramatic 5.8 point jump in Smatch score.

Conclusion

The Stack-Transformer demonstrates that incorporating structural priors into the Transformer architecture significantly improves transition-based parsing. By specializing attention heads to track the stack and buffer, the model achieves high accuracy and training efficiency. Future work may explore integrating recursive composition into the attention mechanism to further capture sub-graph structures without compromising the speed advantages of the Transformer architecture.

Summary updated

Abstract

Modeling the parser state is key to good performance in transition-based parsing. Recurrent Neural Networks considerably improved the performance of transition-based systems by modelling the global state, e.g. stack-LSTM parsers, or local state modeling of contextualized features, e.g. Bi-LSTM parsers. Given the success of Transformer architectures in recent parsing systems, this work explores modifications of the sequence-to-sequence Transformer architecture to model either global or local parser states in transition-based parsing. We show that modifications of the cross attention mechanism of the Transformer considerably strengthen performance both on dependency and Abstract Meaning Representation (AMR) parsing tasks, particularly for smaller models or limited training data.
BibTeX
@inproceedings{astudillo2020transition,
  author = {Ramón Fernandez Astudillo and Miguel Ballesteros and Tahira Naseem and Austin Blodgett and Radu Florian},
  title = {{Transition-based Parsing with Stack-Transformers}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=eRADsB1kpyw},
}
Figure