# On Finding the K-best Non-projective Dependency Trees

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 39 references that are in the map.
- First posted on arXiv 1 Jun 2021.

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

- [Stanza: A Python Natural Language Processing Toolkit for Many Human Languages](https://mlsanity.com/paper/2003.07082/) (2020)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [Efficient Marginalization of Discrete and Structured Latent Variables via Sparsity](https://mlsanity.com/paper/2007.01919/) (2020)
- [Please Mind the Root: Decoding Arborescences for Dependency Parsing](https://mlsanity.com/paper/2010.02550/) (2020)
- [Global Neural CCG Parsing with Optimality Guarantees](https://mlsanity.com/paper/1607.01432/) (2016)
- [Neural Probabilistic Model for Non-projective MST Parsing](https://mlsanity.com/paper/1701.00874/) (2017)
- [A Re-ranking Model for Dependency Parser with Recursive Convolutional Neural Network](https://mlsanity.com/paper/1505.05667/) (2015)

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

- [LasUIE: Unifying Information Extraction with Latent Adaptive Structure-aware Generative Language Model](https://mlsanity.com/paper/2304.06248/) (2023)
- [Measuring and Reducing Model Update Regression in Structured Prediction for NLP](https://mlsanity.com/paper/2202.02976/) (2022)
- [Unbiased and Efficient Sampling of Dependency Trees](https://mlsanity.com/paper/2205.12621/) (2022)
- [Transferring Neural Potentials For High Order Dependency Parsing](https://mlsanity.com/paper/2306.10469/) (2023)

## Abstract (arXiv)

The connection between the maximum spanning tree in a directed graph and the best dependency tree of a sentence has been exploited by the NLP community. However, for many dependency parsing schemes, an important detail of this approach is that the spanning tree must have exactly one edge emanating from the root. While work has been done to efficiently solve this problem for finding the one-best dependency tree, no research has attempted to extend this solution to finding the K-best dependency trees. This is arguably a more important extension as a larger proportion of decoded trees will not be subject to the root constraint of dependency trees. Indeed, we show that the rate of root constraint violations increases by an average of 13 times when decoding with K!=!50 as opposed to K!=!1. In this paper, we provide a simplification of the K-best spanning tree algorithm of Camerini et al. (1980). Our simplification allows us to obtain a constant time speed-up over the original algorithm. Furthermore, we present a novel extension of the algorithm for decoding the K-best dependency trees of a graph which are subject to a root constraint.