# Oops I Took A Gradient: Scalable Sampling for Discrete Distributions

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

## Key facts

- Cited by 92 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 8 Feb 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [Your Classifier is Secretly an Energy Based Model and You Should Treat it Like One](https://mlsanity.com/paper/1912.03263/) (2019)
- [VAE with a VampPrior](https://mlsanity.com/paper/1705.07120/) (2017)
- [On the Anatomy of MCMC-Based Maximum Likelihood Learning of Energy-Based Models](https://mlsanity.com/paper/1903.12370/) (2019)
- [Residual Energy-Based Models for Text Generation](https://mlsanity.com/paper/2004.11714/) (2020)
- [No MCMC for me: Amortized sampling for fast and stable training of energy-based models](https://mlsanity.com/paper/2010.04230/) (2020)
- [Stochastic Security: Adversarial Defense Using Long-Run Dynamics of Energy-Based Models](https://mlsanity.com/paper/2005.13525/) (2020)
- [Accurate and Conservative Estimates of MRF Log-likelihood using Reverse Annealing](https://mlsanity.com/paper/1412.8566/) (2014)
- [The Hamming Ball Sampler](https://mlsanity.com/paper/1504.08133/) (2015)
- [Stein Variational Inference for Discrete Distributions](https://mlsanity.com/paper/2003.00605/) (2020)
- [Joint Energy-based Model Training for Better Calibrated Natural Language Understanding Models](https://mlsanity.com/paper/2101.06829/) (2021)
- [Stein Variational Gradient Descent Without Gradient](https://mlsanity.com/paper/1806.02775/) (2018)
- [Generative Modeling by Inclusive Neural Random Fields with Applications in Image Generation and Anomaly Detection](https://mlsanity.com/paper/1806.00271/) (2018)

## Built on by (most cited first, 30 of 92)

- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (2021)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [Deep Generative Modelling: A Comparative Review of VAEs, GANs, Normalizing Flows, Energy-Based and Autoregressive Models](https://mlsanity.com/paper/2103.04922/) (2021)
- [Trajectory balance: Improved credit assignment in GFlowNets](https://mlsanity.com/paper/2201.13259/) (2022)
- [Automatically Auditing Large Language Models via Discrete Optimization](https://mlsanity.com/paper/2303.04381/) (2023)
- [Simple Guidance Mechanisms for Discrete Diffusion Models](https://mlsanity.com/paper/2412.10193/) (2024)
- [Concrete Score Matching: Generalized Score Matching for Discrete Data](https://mlsanity.com/paper/2211.00802/) (2022)
- [Unlocking Guidance for Discrete State-Space Diffusion and Flow Models](https://mlsanity.com/paper/2406.01572/) (2024)
- [Generative Flow Networks for Discrete Probabilistic Modeling](https://mlsanity.com/paper/2202.01361/) (2022)
- [Unleashing Transformers: Parallel Token Prediction with Discrete Absorbing Diffusion for Fast High-Resolution Image Generation from Vector-Quantized Codes](https://mlsanity.com/paper/2111.12701/) (2021)
- [Informed Correctors for Discrete Diffusion Models](https://mlsanity.com/paper/2407.21243/) (2024)
- [Differentiable DAG Sampling](https://mlsanity.com/paper/2203.08509/) (2022)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [Compositional Generative Modeling: A Single Model is Not All You Need](https://mlsanity.com/paper/2402.01103/) (2024)
- [Exposing the Implicit Energy Networks behind Masked Language Models via Metropolis--Hastings](https://mlsanity.com/paper/2106.02736/) (2021)
- [CANDI: Hybrid Discrete-Continuous Diffusion Models](https://mlsanity.com/paper/2510.22510/) (2025)
- [BayesDAG: Gradient-Based Posterior Inference for Causal Discovery](https://mlsanity.com/paper/2307.13917/) (2023)
- [Energy Matching: Unifying Flow Matching and Energy-Based Models for Generative Modeling](https://mlsanity.com/paper/2504.10612/) (2025)
- [Particle algorithms for maximum likelihood training of latent variable models](https://mlsanity.com/paper/2204.12965/) (2022)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [Gradient Estimation with Discrete Stein Operators](https://mlsanity.com/paper/2202.09497/) (2022)
- [Improving Protein Optimization with Smoothed Fitness Landscapes](https://mlsanity.com/paper/2307.00494/) (2023)
- [Plug & Play Directed Evolution of Proteins with Gradient-based Discrete MCMC](https://mlsanity.com/paper/2212.09925/) (2022)
- [CtrlDiff: Boosting Large Diffusion Language Models with Dynamic Block Prediction and Controllable Generation](https://mlsanity.com/paper/2505.14455/) (2025)
- [Discrete Neural Flow Samplers with Locally Equivariant Transformer](https://mlsanity.com/paper/2505.17741/) (2025)
- [Learning Neural Set Functions Under the Optimal Subset Oracle](https://mlsanity.com/paper/2203.01693/) (2022)
- [Enhanced gradient-based MCMC in discrete spaces](https://mlsanity.com/paper/2208.00040/) (2022)
- [Regularized Langevin Dynamics for Combinatorial Optimization](https://mlsanity.com/paper/2502.00277/) (2025)
- [Perturb-and-max-product: Sampling and learning in discrete energy-based models](https://mlsanity.com/paper/2111.02458/) (2021)
- [Optimal Scaling for Locally Balanced Proposals in Discrete Spaces](https://mlsanity.com/paper/2209.08183/) (2022)

## Abstract (arXiv)

We propose a general and scalable approximate sampling strategy for probabilistic models with discrete variables. Our approach uses gradients of the likelihood function with respect to its discrete inputs to propose updates in a Metropolis-Hastings sampler. We show empirically that this approach outperforms generic samplers in a number of difficult settings including Ising models, Potts models, restricted Boltzmann machines, and factorial hidden Markov models. We also demonstrate the use of our improved sampler for training deep energy-based models on high dimensional discrete data. This approach outperforms variational auto-encoders and existing energy-based models. Finally, we give bounds showing that our approach is near-optimal in the class of samplers which propose local updates.