# Scaling Structured Inference with Randomization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 52 references that are in the map.
- First posted on arXiv 7 Dec 2021.

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

- [End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF](https://mlsanity.com/paper/1603.01354/) (2016)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Optimus: Organizing Sentences via Pre-trained Modeling of a Latent Space](https://mlsanity.com/paper/2004.04092/) (2020)
- [Telescoping Density-Ratio Estimation](https://mlsanity.com/paper/2006.12204/) (2020)
- [Gradient Estimation with Stochastic Softmax Tricks](https://mlsanity.com/paper/2006.08063/) (2020)
- [Learning Neural Templates for Text Generation](https://mlsanity.com/paper/1808.10122/) (2018)
- [Fast Structured Decoding for Sequence Models](https://mlsanity.com/paper/1910.11555/) (2019)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [Efficient Second-Order TreeCRF for Neural Dependency Parsing](https://mlsanity.com/paper/2005.00975/) (2020)
- [Unsupervised Recurrent Neural Network Grammars](https://mlsanity.com/paper/1904.03746/) (2019)
- [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)
- [Rao-Blackwellized Stochastic Gradients for Discrete Distributions](https://mlsanity.com/paper/1810.04777/) (2018)
- [Randomized Automatic Differentiation](https://mlsanity.com/paper/2007.10412/) (2020)
- [Scaling Hidden Markov Language Models](https://mlsanity.com/paper/2011.04640/) (2020)
- [PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols](https://mlsanity.com/paper/2104.13727/) (2021)
- [Efficient Marginalization of Discrete and Structured Latent Variables via Sparsity](https://mlsanity.com/paper/2007.01919/) (2020)
- [Differentiable Perturb-and-Parse: Semi-Supervised Parsing with a Structured Variational Autoencoder](https://mlsanity.com/paper/1807.09875/) (2018)
- [The Return of Lexical Dependencies: Neural Lexicalized PCFGs](https://mlsanity.com/paper/2007.15135/) (2020)
- [Posterior Control of Blackbox Generation](https://mlsanity.com/paper/2005.04560/) (2020)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [A Smoother Way to Train Structured Prediction Models](https://mlsanity.com/paper/1902.03228/) (2019)
- [Latent Template Induction with Gumbel-CRFs](https://mlsanity.com/paper/2011.14244/) (2020)
- [Conditional Random Field Autoencoders for Unsupervised Structured Prediction](https://mlsanity.com/paper/1411.1147/) (2014)
- [Efficient Optimization of Loops and Limits with Randomized Telescoping Sums](https://mlsanity.com/paper/1905.07006/) (2019)
- [CRF Autoencoder for Unsupervised Dependency Parsing](https://mlsanity.com/paper/1708.01018/) (2017)
- [A General Algorithm for Approximate Inference and its Application to Hybrid Bayes Nets](https://mlsanity.com/paper/1301.6709/) (2013)

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

- [Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs](https://mlsanity.com/paper/2205.00484/) (2022)
- [Latent Topology Induction for Understanding Contextualized Representations](https://mlsanity.com/paper/2206.01512/) (2022)

## Abstract (arXiv)

Deep discrete structured models have seen considerable progress recently, but traditional inference using dynamic programming (DP) typically works with a small number of states (less than hundreds), which severely limits model capacity. At the same time, across machine learning, there is a recent trend of using randomized truncation techniques to accelerate computations involving large sums. Here, we propose a family of randomized dynamic programming (RDP) algorithms for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference (partition, marginal, reparameterization, entropy) and different graph structures (chains, trees, and more general hypergraphs). It is also compatible with automatic differentiation: it can be integrated with neural networks seamlessly and learned with gradient-based optimizers. Our core technique approximates the sum-product by restricting and reweighting DP on a small subset of nodes, which reduces computation by orders of magnitude. We further achieve low bias and variance via Rao-Blackwellization and importance sampling. Experiments over different graphs demonstrate the accuracy and efficiency of our approach. Furthermore, when using RDP for training a structured variational autoencoder with a scaled inference network, we achieve better test likelihood than baselines and successfully prevent posterior collapse. code at: https://github.com/FranxYao/RDP