# Enhanced gradient-based MCMC in discrete spaces

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 44 references that are in the map.
- First posted on arXiv 29 Jul 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [A Complete Recipe for Stochastic Gradient MCMC](https://mlsanity.com/paper/1506.04696/) (2015)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Rank-normalization, folding, and localization: An improved widehatR for assessing convergence of MCMC](https://mlsanity.com/paper/1903.08008/) (2019)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Generalized Energy Based Models](https://mlsanity.com/paper/2003.05033/) (2020)
- [Generalizing Hamiltonian Monte Carlo with Neural Networks](https://mlsanity.com/paper/1711.09268/) (2017)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [Auxiliary gradient-based sampling algorithms](https://mlsanity.com/paper/1610.09641/) (2016)
- [The Hamming Ball Sampler](https://mlsanity.com/paper/1504.08133/) (2015)
- [Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC](https://mlsanity.com/paper/2102.02374/) (2021)

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

- [Unlocking Guidance for Discrete State-Space Diffusion and Flow Models](https://mlsanity.com/paper/2406.01572/) (2024)
- [Energy-Based Modelling for Discrete and Mixed Data via Heat Equations on Structured Spaces](https://mlsanity.com/paper/2412.01019/) (2024)
- [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)
- [Entropy-Guided Sampling of Flat Modes in Discrete Spaces](https://mlsanity.com/paper/2505.02296/) (2025)
- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)
- [Slithering Through Gaps: Capturing Discrete Isolated Modes via Logistic Bridging](https://mlsanity.com/paper/2604.10821/) (2026)
- [Training Discrete Energy-Based Models with Energy Discrepancy](https://mlsanity.com/paper/2307.07595/) (2023)
- [Preconditioned Discrete-HAMS: A Second-order Irreversible Discrete Sampler](https://mlsanity.com/paper/2507.21982/) (2025)

## Abstract (arXiv)

The recent introduction of gradient-based MCMC for discrete spaces holds great promise, and comes with the tantalising possibility of new discrete counterparts to celebrated continuous methods such as MALA and HMC. Towards this goal, we introduce several discrete Metropolis-Hastings samplers that are conceptually-inspired by MALA, and demonstrate their strong empirical performance across a range of challenging sampling problems in Bayesian inference and energy-based modelling. Methodologically, we identify why discrete analogues to preconditioned MALA are generally intractable, motivating us to introduce a new kind of preconditioning based on auxiliary variables and the `Gaussian integral trick'.