# A Langevin-like Sampler for Discrete Distributions

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 62 references that are in the map.
- First posted on arXiv 20 Jun 2022.

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

- [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)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [Texygen: A Benchmarking Platform for Text Generation Models](https://mlsanity.com/paper/1802.01886/) (2018)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [Your Classifier is Secretly an Energy Based Model and You Should Treat it Like One](https://mlsanity.com/paper/1912.03263/) (2019)
- [SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient](https://mlsanity.com/paper/1609.05473/) (2016)
- [Probabilistic Backpropagation for Scalable Learning of Bayesian Neural Networks](https://mlsanity.com/paper/1502.05336/) (2015)
- [VAE with a VampPrior](https://mlsanity.com/paper/1705.07120/) (2017)
- [Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning](https://mlsanity.com/paper/1902.03932/) (2019)
- [BERT has a Mouth, and It Must Speak: BERT as a Markov Random Field Language Model](https://mlsanity.com/paper/1902.04094/) (2019)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Understanding Knowledge Distillation in Non-autoregressive Machine Translation](https://mlsanity.com/paper/1911.02727/) (2019)
- [Enabling Language Models to Fill in the Blanks](https://mlsanity.com/paper/2005.05339/) (2020)
- [Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networks](https://mlsanity.com/paper/1512.07666/) (2015)
- [Generative Flow Networks for Discrete Probabilistic Modeling](https://mlsanity.com/paper/2202.01361/) (2022)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Post-training Quantization with Multiple Points: Mixed Precision without Mixed Precision](https://mlsanity.com/paper/2002.09049/) (2020)
- [Probabilistic Binary Neural Networks](https://mlsanity.com/paper/1809.03368/) (2018)
- [The Hamming Ball Sampler](https://mlsanity.com/paper/1504.08133/) (2015)
- [Stein Variational Inference for Discrete Distributions](https://mlsanity.com/paper/2003.00605/) (2020)
- [Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC](https://mlsanity.com/paper/2102.02374/) (2021)
- [LSB: Local Self-Balancing MCMC in Discrete Spaces](https://mlsanity.com/paper/2109.03867/) (2021)

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

- [Automatically Auditing Large Language Models via Discrete Optimization](https://mlsanity.com/paper/2303.04381/) (2023)
- [Unlocking Guidance for Discrete State-Space Diffusion and Flow Models](https://mlsanity.com/paper/2406.01572/) (2024)
- [Informed Correctors for Discrete Diffusion Models](https://mlsanity.com/paper/2407.21243/) (2024)
- [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)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [Plug & Play Directed Evolution of Proteins with Gradient-based Discrete MCMC](https://mlsanity.com/paper/2212.09925/) (2022)
- [Discrete Neural Flow Samplers with Locally Equivariant Transformer](https://mlsanity.com/paper/2505.17741/) (2025)
- [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)
- [Masked Bayesian Neural Networks : Theoretical Guarantee and its Posterior Inference](https://mlsanity.com/paper/2305.14765/) (2023)
- [Gradient-based Discrete Sampling with Automatic Cyclical Scheduling](https://mlsanity.com/paper/2402.17699/) (2024)
- [Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation](https://mlsanity.com/paper/2302.13929/) (2023)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Reheated Gradient-based Discrete Sampling for Combinatorial Optimization](https://mlsanity.com/paper/2503.04047/) (2025)
- [Energy-Based Modelling for Discrete and Mixed Data via Heat Equations on Structured Spaces](https://mlsanity.com/paper/2412.01019/) (2024)
- [Contrastive Distribution Matching for Amortized Sequential Monte Carlo in Discrete Diffusion](https://mlsanity.com/paper/2605.23346/) (2026)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Structured Voronoi Sampling](https://mlsanity.com/paper/2306.03061/) (2023)
- [Principled Gradient-based Markov Chain Monte Carlo for Text Generation](https://mlsanity.com/paper/2312.17710/) (2023)
- [Gradient GA: Gradient Genetic Algorithm for Drug Molecular Design](https://mlsanity.com/paper/2502.09860/) (2025)
- [Differentiable Constraint-Based Causal Discovery](https://mlsanity.com/paper/2510.22031/) (2025)
- [Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces](https://mlsanity.com/paper/2404.03867/) (2024)
- [Interpolation and differentiation of alchemical degrees of freedom in machine learning interatomic potentials](https://mlsanity.com/paper/2404.10746/) (2024)
- [A Family of Distributions of Random Subsets for Controlling Positive and Negative Dependence](https://mlsanity.com/paper/2408.01022/) (2024)
- [Entropy-Guided Sampling of Flat Modes in Discrete Spaces](https://mlsanity.com/paper/2505.02296/) (2025)
- [Learning with Local Search MCMC Layers](https://mlsanity.com/paper/2505.14240/) (2025)
- [Discrete diffusion samplers and bridges: Off-policy algorithms and applications in latent spaces](https://mlsanity.com/paper/2602.05961/) (2026)
- [A Blueprint for Equilibrium-Based Differentiable Continuous-Variable Thermodynamic Computing](https://mlsanity.com/paper/2607.16183/) (2026)
- [Evaluation of human-model prediction difference on the Internet Scale of Data](https://mlsanity.com/paper/2312.03291/) (2023)

## Abstract (arXiv)

We propose discrete Langevin proposal (DLP), a simple and scalable gradient-based proposal for sampling complex high-dimensional discrete distributions. In contrast to Gibbs sampling-based methods, DLP is able to update all coordinates in parallel in a single step and the magnitude of changes is controlled by a stepsize. This allows a cheap and efficient exploration in the space of high-dimensional and strongly correlated variables. We prove the efficiency of DLP by showing that the asymptotic bias of its stationary distribution is zero for log-quadratic distributions, and is small for distributions that are close to being log-quadratic. With DLP, we develop several variants of sampling algorithms, including unadjusted, Metropolis-adjusted, stochastic and preconditioned versions. DLP outperforms many popular alternatives on a wide variety of tasks, including Ising models, restricted Boltzmann machines, deep energy-based models, binary neural networks and language generation.