# Hexatagging: Projective Dependency Parsing as Tagging

arXiv: https://arxiv.org/abs/2306.05477 · HTML: https://mlsanity.com/paper/2306.05477/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 44 references that are in the map.
- First posted on arXiv 8 Jun 2023.

## Builds on (most cited first, 16 of 16)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [Muppet: Massive Multi-task Representations with Pre-Finetuning](https://mlsanity.com/paper/2101.11038/) (2021)
- [Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations](https://mlsanity.com/paper/1603.04351/) (2016)
- [Efficient Second-Order TreeCRF for Neural Dependency Parsing](https://mlsanity.com/paper/2005.00975/) (2020)
- [Head-Driven Phrase Structure Grammar Parsing on Penn Treebank](https://mlsanity.com/paper/1907.02684/) (2019)
- [Viable Dependency Parsing as Sequence Labeling](https://mlsanity.com/paper/1902.10505/) (2019)
- [Scheduled Multi-Task Learning: From Syntax to Translation](https://mlsanity.com/paper/1804.08915/) (2018)
- [Tetra-Tagging: Word-Synchronous Parsing with Linear-Time Inference](https://mlsanity.com/paper/1904.09745/) (2019)
- [Second-Order Neural Dependency Parsing with Message Passing and End-to-End Training](https://mlsanity.com/paper/2010.05003/) (2020)
- [Please Mind the Root: Decoding Arborescences for Dependency Parsing](https://mlsanity.com/paper/2010.02550/) (2020)
- [Headed-Span-Based Projective Dependency Parsing](https://mlsanity.com/paper/2108.04750/) (2021)
- [Global Neural CCG Parsing with Optimality Guarantees](https://mlsanity.com/paper/1607.01432/) (2016)
- [Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication](https://mlsanity.com/paper/1504.08342/) (2015)

## Built on by (most cited first, 3 of 3)

- [Dancing in the syntax forest: fast, accurate and explainable sentiment analysis with SALSA](https://mlsanity.com/paper/2406.16071/) (2024)
- [Reduction of Supervision for Biomedical Knowledge Discovery](https://mlsanity.com/paper/2504.09582/) (2025)
- [Formal Constraints on Dependency Syntax](https://mlsanity.com/paper/2604.04542/) (2026)

## Abstract (arXiv)

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.