# Unbiased and Efficient Sampling of Dependency Trees

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 55 references that are in the map.
- First posted on arXiv 25 May 2022.

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

- [Stanza: A Python Natural Language Processing Toolkit for Many Human Languages](https://mlsanity.com/paper/2003.07082/) (2020)
- [Universal Dependencies v2: An Evergrowing Multilingual Treebank Collection](https://mlsanity.com/paper/2004.10643/) (2020)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Transformer Grammars: Augmenting Transformer Language Models with Syntactic Inductive Biases at Scale](https://mlsanity.com/paper/2203.00633/) (2022)
- [Torch-Struct: Deep Structured Prediction Library](https://mlsanity.com/paper/2002.00876/) (2020)
- [Estimating Gradients for Discrete Random Variables by Sampling without Replacement](https://mlsanity.com/paper/2002.06043/) (2020)
- [Incremental Sampling Without Replacement for Sequence Models](https://mlsanity.com/paper/2002.09067/) (2020)
- [Differentiable Perturb-and-Parse: Semi-Supervised Parsing with a Structured Variational Autoencoder](https://mlsanity.com/paper/1807.09875/) (2018)
- [Efficient Computation of Expectations under Spanning Tree Distributions](https://mlsanity.com/paper/2008.12988/) (2020)
- [Please Mind the Root: Decoding Arborescences for Dependency Parsing](https://mlsanity.com/paper/2010.02550/) (2020)
- [Sampling Random Spanning Trees Faster than Matrix Multiplication](https://mlsanity.com/paper/1611.07451/) (2016)
- [On Finding the K-best Non-projective Dependency Trees](https://mlsanity.com/paper/2106.00780/) (2021)

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

- [SynJax: Structured Probability Distributions for JAX](https://mlsanity.com/paper/2308.03291/) (2023)
- [Syntactic Belief Update as the Driver of Garden Path Processing Difficulty](https://mlsanity.com/paper/2606.27206/) (2026)

## Abstract (arXiv)

Most computational models of dependency syntax consist of distributions over spanning trees. However, the majority of dependency treebanks require that every valid dependency tree has a single edge coming out of the ROOT node, a constraint that is not part of the definition of spanning trees. For this reason all standard inference algorithms for spanning trees are suboptimal for inference over dependency trees. Zmigrod et al. (2021b) proposed algorithms for sampling with and without replacement from the dependency tree distribution that incorporate the single-root constraint. In this paper we show that their fastest algorithm for sampling with replacement, Wilson-RC, is in fact producing biased samples and we provide two alternatives that are unbiased. Additionally, we propose two algorithms (one incremental, one parallel) that reduce the asymptotic runtime of algorithm for sampling k trees without replacement to O(kn3). These algorithms are both asymptotically and practically more efficient.