Hexatagging: Projective Dependency Parsing as Tagging

Afra Amini, Tianyu Liu, Ryan Cotterell

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—the task of identifying grammatical relationships between words in a sentence—is a cornerstone of natural language processing. Traditionally, this task requires complex structured prediction models to identify which words serve as the "head" or "dependent" of others. While current state-of-the-art (SOTA) parsers achieve high accuracy, they often suffer from two primary bottlenecks: limited parallelization during training and the use of tag sets that grow with sentence length. These factors increase computational overhead and hinder generalization to long-form text.

Hexatagging addresses these challenges by recasting projective dependency parsing as a sequence tagging problem using a fixed set of only six unique tags. This approach enables fully parallelizable training and linear-time decoding, achieving SOTA accuracy while running significantly faster than previous top-tier models.

The Hexatagging Framework

The core innovation of this work is the hexatagger, which utilizes an intermediate representation known as a Binary Head Tree (BHT) to map dependency trees to a sequence of tags.

The Six-Tag System

Unlike previous tagging-based parsers that used unbounded tag sets, the hexatagger uses exactly six distinct tag types. These tags describe the actions of a "left-corner shift-reduce" parser, indicating whether a node is a left or right child of its parent and identifying the location of the "head" within the current phrase. By proving that any projective dependency tree can be represented by a sequence of just six tags, the authors eliminate the complexity of sentence-length-dependent tag sets.

The Pipeline

The Hexatagging process follows a streamlined four-step pipeline:

  1. Conversion: A dependency tree is converted into a Binary Head Tree (BHT).
  2. Linearization: The BHT is linearized into a sequence of $2N-1$ hexatags for a sentence of length $N$.
  3. Feature Extraction: A standard pretrained language model (such as XLNet or BERT) serves as a feature extractor.
  4. Prediction: A simple linear classifier predicts the tags for each word independently.

Efficient Decoding

Because the model predicts tags independently, the raw output may not inherently form a valid tree. To resolve this, the authors employ a linear-time dynamic programming algorithm—specifically a shortest-path approach—to identify the highest-scoring valid sequence of tags that can be reconstructed into a proper dependency tree.

Experimental Evaluation

The Hexatagger was evaluated across several standard benchmarks to demonstrate its accuracy and cross-linguistic generality:

  • English Penn Treebank (PTB): The primary benchmark for English parsing.
  • Chinese Penn Treebank (CTB): Used to evaluate performance on non-Western linguistic structures.
  • Universal Dependencies 2.2 (UD2.2): A collection of 12 diverse languages (including Bulgarian, Catalan, Czech, German, Spanish, French, Italian, Dutch, Norwegian, Romanian, and Russian).

Key Results

Hexatagger matched or exceeded the performance of much more complex models while providing substantial efficiency gains:

  • State-of-the-Art Accuracy: On the English PTB test set, the model achieved 96.4 LAS (Labeled Attachment Score) and 97.4 UAS (Unlabeled Attachment Score).
  • Computational Speed: During decoding, Hexatagger is approximately 10 times faster than the popular Biaffine parser, processing 3,176 sentences per second compared to the Biaffine's 338 sentences per second.
  • Memory Efficiency: The model requires significantly less memory—roughly 3.0 GB compared to the 10.6 GB required by Biaffine models—making it highly suitable for resource-constrained environments.

Discussion and Future Work

The success of Hexatagging suggests that complex, task-specific neural architectures may not be necessary for high-performance dependency parsing. Instead, a clever framing of the problem allows a simple linear layer on top of a standard language model to achieve SOTA results. The independence of tag prediction aligns perfectly with the parallel nature of Transformer-based models, maximizing hardware utilization.

However, the current framework is limited to projective dependency trees, where dependency arcs do not cross. While many languages are predominantly projective, others (such as German or Czech) frequently utilize non-projective structures. Extending the hexatagging scheme to accommodate non-projective parsing remains a primary goal for future research. Additionally, because the parsing logic is embedded within the tag sequence, the model's decision-making process is less explicitly interpretable than traditional graph-based parsers.

Summary updated

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.
BibTeX
@inproceedings{amini2023hexatagging,
  author = {Afra Amini and Tianyu Liu and Ryan Cotterell},
  title = {{Hexatagging: Projective Dependency Parsing as Tagging}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2023},
  url = {https://openreview.net/forum?id=uqGXIjEyeg},
}
Figure