# Leveraging Recursive Gumbel-Max Trick for Approximate Inference in Combinatorial Spaces

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

## Key facts

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

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

- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Show, Attend and Tell: Neural Image Caption Generation with Visual Attention](https://mlsanity.com/paper/1502.03044/) (2015)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Importance Weighted Autoencoders](https://mlsanity.com/paper/1509.00519/) (2015)
- [Neural Relational Inference for Interacting Systems](https://mlsanity.com/paper/1802.04687/) (2018)
- [Rationalizing Neural Predictions](https://mlsanity.com/paper/1606.04155/) (2016)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Backpropagation through the Void: Optimizing control variates for black-box gradient estimation](https://mlsanity.com/paper/1711.00123/) (2017)
- [REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models](https://mlsanity.com/paper/1703.07370/) (2017)
- [VarGrad: A Low-Variance Gradient Estimator for Variational Inference](https://mlsanity.com/paper/2010.10436/) (2020)
- [Reparameterizable Subset Sampling via Continuous Relaxations](https://mlsanity.com/paper/1901.10517/) (2019)
- [Differentiable Patch Selection for Image Recognition](https://mlsanity.com/paper/2104.03059/) (2021)
- [Gradient Estimation with Stochastic Softmax Tricks](https://mlsanity.com/paper/2006.08063/) (2020)
- [Non-Monotonic Sequential Text Generation](https://mlsanity.com/paper/1902.02192/) (2019)
- [Insertion-based Decoding with automatically Inferred Generation Order](https://mlsanity.com/paper/1902.01370/) (2019)
- [Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator](https://mlsanity.com/paper/2010.04838/) (2020)
- [Learning to Compose Words into Sentences with Reinforcement Learning](https://mlsanity.com/paper/1611.09100/) (2016)
- [Cooperative Learning of Disjoint Syntax and Semantics](https://mlsanity.com/paper/1902.09393/) (2019)
- [Differentiable Perturb-and-Parse: Semi-Supervised Parsing with a Structured Variational Autoencoder](https://mlsanity.com/paper/1807.09875/) (2018)
- [Differentiable Top-k Operator with Optimal Transport](https://mlsanity.com/paper/2002.06504/) (2020)
- [Discovering Non-monotonic Autoregressive Orderings with Variational Inference](https://mlsanity.com/paper/2110.15797/) (2021)
- [Low-variance Black-box Gradient Estimates for the Plackett-Luce Distribution](https://mlsanity.com/paper/1911.10036/) (2019)
- [Latent Template Induction with Gumbel-CRFs](https://mlsanity.com/paper/2011.14244/) (2020)
- [Coupled Gradient Estimators for Discrete Latent Variables](https://mlsanity.com/paper/2106.08056/) (2021)

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

- [MIST: Multi-modal Iterative Spatial-Temporal Transformer for Long-form Video Question Answering](https://mlsanity.com/paper/2212.09522/) (2022)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [Differentiable Clustering with Perturbed Spanning Forests](https://mlsanity.com/paper/2305.16358/) (2023)
- [GeoPhy: Differentiable Phylogenetic Inference via Geometric Gradients of Tree Topologies](https://mlsanity.com/paper/2307.03675/) (2023)
- [Large (Vision) Language Models are Unsupervised In-Context Learners](https://mlsanity.com/paper/2504.02349/) (2025)
- [ReCache: Learning Budget-Aware Caching Schedules for Diffusion Models via REINFORCE](https://mlsanity.com/paper/2606.06060/) (2026)
- [Latent Optimal Paths by Gumbel Propagation for Variational Bayesian Dynamic Programming](https://mlsanity.com/paper/2306.02568/) (2023)

## Abstract (arXiv)

Structured latent variables allow incorporating meaningful prior knowledge into deep learning models. However, learning with such variables remains challenging because of their discrete nature. Nowadays, the standard learning approach is to define a latent variable as a perturbed algorithm output and to use a differentiable surrogate for training. In general, the surrogate puts additional constraints on the model and inevitably leads to biased gradients. To alleviate these shortcomings, we extend the Gumbel-Max trick to define distributions over structured domains. We avoid the differentiable surrogates by leveraging the score function estimators for optimization. In particular, we highlight a family of recursive algorithms with a common feature we call stochastic invariant. The feature allows us to construct reliable gradient estimates and control variates without additional constraints on the model. In our experiments, we consider various structured latent variable models and achieve results competitive with relaxation-based counterparts.