Abstract
We introduce a novel dependency parser, the hexatagger, that constructs dependency trees by tagging the words in a sentence with elements from a finite set of possible tags. In contrast to many approaches to dependency parsing, our approach is fully parallelizable at training time, i.e., the structure-building actions needed to build a dependency parse can be predicted in parallel to each other. Additionally, exact decoding is linear in time and space complexity. Furthermore, we derive a probabilistic dependency parser that predicts hexatags using no more than a linear model with features from a pretrained language model, i.e., we forsake a bespoke architecture explicitly designed for the task. Despite the generality and simplicity of our approach, we achieve state-of-the-art performance of 96.4 LAS and 97.4 UAS on the Penn Treebank test set. Additionally, our parser’s linear time complexity and parallelism significantly improve computational efficiency, with a roughly 10-times speed-up over previous state-of-the-art models during decoding.
Introduction
Dependency parsing is a fundamental task in natural language processing, identifying the grammatical relationships between words in a sentence. However, achieving high accuracy typically comes at a high computational cost. Existing state-of-the-art parsers generally fall into two categories: graph-based methods, which score every possible word pair, and transition-based methods, which build trees sequentially. Both approaches are difficult to parallelize effectively during training and can be slow during inference.
While previous research has attempted to frame parsing as a sequence tagging task to leverage parallelism, these methods often required an "infinite" set of tags that grew with sentence length, leading to inefficiencies and poor generalization on long sequences. Hexatagging addresses these issues by distilling the complexity of projective dependency trees into a fixed set of just six tags.
Methodology: The Hexatagging Scheme
The core innovation of this work is the conversion of dependency trees into a sequence of six unique tags. This is achieved through an intermediate representation called a Binary Head Tree (BHT). In a BHT, internal nodes indicate whether the "head" of a phrase resides in the left or right subtree.
The process involves three main stages:
- Linearization: A dependency tree is converted into a BHT and then flattened into a sequence of hexatags using a left-corner shift-reduce logic. This specific ordering minimizes the distance between related words, making the tagging task easier for the model.
- Parallel Training: Because the task is reduced to independent tagging decisions, the model architecture is remarkably simple: a pretrained language model (e.g., BERT or XLNet) followed by a single linear classifier. This allows for full parallelization across the sentence during training.
- Efficient Decoding: To ensure the predicted tags form a valid tree, the authors employ a linear-time dynamic programming algorithm that finds the highest-scoring valid sequence.
Experimental Results
The Hexatagger was evaluated across diverse benchmarks, including the English Penn Treebank (PTB), the Chinese Penn Treebank (CTB), and 12 languages from the Universal Dependencies (UD 2.2) collection.
Key findings include:
- State-of-the-Art Accuracy: On the PTB, the model achieved a Labeled Attachment Score (LAS) of 96.4, matching or exceeding the performance of far more complex, specialized architectures.
- Computational Efficiency: The parser delivers a 10x speedup during decoding compared to previous state-of-the-art models.
- Memory Savings: The system is highly memory-efficient, requiring approximately 3.0 GB of memory compared to the 10.6 GB typically required by standard biaffine parsers.
Conclusion
Hexatagging demonstrates that complex structural prediction tasks can be simplified into efficient tagging tasks without sacrificing accuracy. By utilizing a small, fixed tag set and a general-purpose transformer architecture, the Hexatagger achieves state-of-the-art results with significantly improved speed and memory efficiency. While currently limited to projective trees, the success of this approach suggests a promising path for future research into extending tagging-based logic to non-projective structures.
Summary updated