# Headed-Span-Based Projective Dependency Parsing

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 86 references that are in the map.
- First posted on arXiv 10 Aug 2021.

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

- [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)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [Constituency Parsing with a Self-Attentive Encoder](https://mlsanity.com/paper/1805.01052/) (2018)
- [A Minimal Span-Based Neural Constituency Parser](https://mlsanity.com/paper/1705.03919/) (2017)
- [Fast and Accurate Neural CRF Constituency Parsing](https://mlsanity.com/paper/2008.03736/) (2020)
- [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)
- [Torch-Struct: Deep Structured Prediction Library](https://mlsanity.com/paper/2002.00876/) (2020)
- [Stack-Pointer Networks for Dependency Parsing](https://mlsanity.com/paper/1805.01087/) (2018)
- [Dependency-Guided LSTM-CRF for Named Entity Recognition](https://mlsanity.com/paper/1909.10148/) (2019)
- [Enhancing Machine Translation with Dependency-Aware Self-Attention](https://mlsanity.com/paper/1909.03149/) (2019)
- [Left-to-Right Dependency Parsing with Pointer Networks](https://mlsanity.com/paper/1903.08445/) (2019)
- [Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles](https://mlsanity.com/paper/1612.06475/) (2016)
- [Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement](https://mlsanity.com/paper/2003.13118/) (2020)
- [Second-Order Neural Dependency Parsing with Message Passing and End-to-End Training](https://mlsanity.com/paper/2010.05003/) (2020)
- [Dependency Parsing as MRC-based Span-Span Prediction](https://mlsanity.com/paper/2105.07654/) (2021)
- [Multitask Pointer Network for Multi-Representational Parsing](https://mlsanity.com/paper/2009.09730/) (2020)
- [Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)](https://mlsanity.com/paper/2003.13785/) (2020)
- [Hierarchical Pointer Net Parsing](https://mlsanity.com/paper/1908.11571/) (2019)
- [Approximation-Aware Dependency Parsing by Belief Propagation](https://mlsanity.com/paper/1508.02375/) (2015)
- [Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Set](https://mlsanity.com/paper/1708.09403/) (2017)
- [Dependency Parsing with Bottom-up Hierarchical Pointer Networks](https://mlsanity.com/paper/2105.09611/) (2021)
- [Recursive Subtree Composition in LSTM-Based Dependency Parsing](https://mlsanity.com/paper/1902.09781/) (2019)
- [Global Transition-based Non-projective Dependency Parsing](https://mlsanity.com/paper/1807.01745/) (2018)
- [The (Non-)Utility of Structural Features in BiLSTM-based Dependency Parsers](https://mlsanity.com/paper/1905.12676/) (2019)

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

- [Semantic Role Labeling as Dependency Parsing: Exploring Latent Tree Structures Inside Arguments](https://mlsanity.com/paper/2110.06865/) (2021)
- [Combining (second-order) graph-based and headed-span-based projective dependency parsing](https://mlsanity.com/paper/2108.05838/) (2021)
- [ChatGPT is a Potential Zero-Shot Dependency Parser](https://mlsanity.com/paper/2310.16654/) (2023)
- [Hexatagging: Projective Dependency Parsing as Tagging](https://mlsanity.com/paper/2306.05477/) (2023)
- [Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective](https://mlsanity.com/paper/2305.15057/) (2023)
- [Revisiting Structured Sentiment Analysis as Latent Dependency Graph Parsing](https://mlsanity.com/paper/2407.04801/) (2024)
- [The Fragility of Multi-Treebank Parsing Evaluation](https://mlsanity.com/paper/2209.06699/) (2022)
- [High-order Joint Constituency and Dependency Parsing](https://mlsanity.com/paper/2309.11888/) (2023)
- [Scaling Graph-Based Dependency Parsing with Arc Vectorization and Attention-Based Refinement](https://mlsanity.com/paper/2501.09451/) (2025)
- [Dependency Parsing with the Structuralized Prompt Template](https://mlsanity.com/paper/2502.16919/) (2025)
- [Weakly Supervised Fine-grained Span-Level Framework for Chinese Radiology Report Quality Assurance](https://mlsanity.com/paper/2508.08876/) (2025)

## Abstract (arXiv)

We propose a new method for projective dependency parsing based on headed spans. In a projective dependency tree, the largest subtree rooted at each word covers a contiguous sequence (i.e., a span) in the surface order. We call such a span marked by a root word textitheaded span. A projective dependency tree can be represented as a collection of headed spans. We decompose the score of a dependency tree into the scores of the headed spans and design a novel O(n3) dynamic programming algorithm to enable global training and exact inference. Our model achieves state-of-the-art or competitive results on PTB, CTB, and UD. Our code is publicly available at urlhttps://github.com/sustcsonglin/span-based-dependency-parsing.