# 4 and 7-bit Labeling for Projective and Non-Projective Dependency Trees

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 22 Oct 2023.

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

- [Unsupervised Cross-lingual Representation Learning at Scale](https://mlsanity.com/paper/1911.02116/) (2019)
- [Massive Choice, Ample Tasks (MaChAmp): A Toolkit for Multi-task Learning in NLP](https://mlsanity.com/paper/2005.14672/) (2020)
- [Viable Dependency Parsing as Sequence Labeling](https://mlsanity.com/paper/1902.10505/) (2019)
- [Constituent Parsing as Sequence Labeling](https://mlsanity.com/paper/1810.08994/) (2018)
- [Tetra-Tagging: Word-Synchronous Parsing with Linear-Time Inference](https://mlsanity.com/paper/1904.09745/) (2019)
- [Bracketing Encodings for 2-Planar Dependency Parsing](https://mlsanity.com/paper/2011.00596/) (2020)
- [A Unifying Theory of Transition-based and Sequence Labeling Parsing](https://mlsanity.com/paper/2011.00584/) (2020)
- [How to best use Syntax in Semantic Role Labelling](https://mlsanity.com/paper/1906.00266/) (2019)
- [A Modest Pareto Optimisation Analysis of Dependency Parsers in 2021](https://mlsanity.com/paper/2106.04216/) (2021)
- [Not All Linearizations Are Equally Data-Hungry in Sequence Labeling Parsing](https://mlsanity.com/paper/2108.07556/) (2021)
- [Distilling Neural Networks for Greener and Faster Dependency Parsing](https://mlsanity.com/paper/2006.00844/) (2020)
- [A Falta de Pan, Buenas Son Tortas: The Efficacy of Predicted UPOS Tags for Low Resource UD Parsing](https://mlsanity.com/paper/2106.04222/) (2021)

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

- [A Syntax-Injected Approach for Faster and More Accurate Sentiment Analysis](https://mlsanity.com/paper/2406.15163/) (2024)
- [Dancing in the syntax forest: fast, accurate and explainable sentiment analysis with SALSA](https://mlsanity.com/paper/2406.16071/) (2024)
- [Dependency Graph Parsing as Sequence Labeling](https://mlsanity.com/paper/2410.17972/) (2024)
- [Hierarchical Bracketing Encodings for Dependency Parsing as Tagging](https://mlsanity.com/paper/2505.11693/) (2025)
- [Bringing Emerging Architectures to Sequence Labeling in NLP](https://mlsanity.com/paper/2509.25918/) (2025)
- [Hierarchical Bracketing Encodings Work for Dependency Graphs](https://mlsanity.com/paper/2509.09388/) (2025)
- [Translation via Annotation: A Computational Study of Translating Classical Chinese into Japanese](https://mlsanity.com/paper/2511.05239/) (2025)
- [Formal Constraints on Dependency Syntax](https://mlsanity.com/paper/2604.04542/) (2026)

## Abstract (arXiv)

We introduce an encoding for parsing as sequence labeling that can represent any projective dependency tree as a sequence of 4-bit labels, one per word. The bits in each word's label represent (1) whether it is a right or left dependent, (2) whether it is the outermost (left/right) dependent of its parent, (3) whether it has any left children and (4) whether it has any right children. We show that this provides an injective mapping from trees to labels that can be encoded and decoded in linear time. We then define a 7-bit extension that represents an extra plane of arcs, extending the coverage to almost full non-projectivity (over 99.9% empirical arc coverage). Results on a set of diverse treebanks show that our 7-bit encoding obtains substantial accuracy gains over the previously best-performing sequence labeling encodings.