Iterative Exact Discrete Guidance for Energy-Based Sampling
Abstract
Sampling from unnormalized distributions over large discrete state spaces becomes difficult when a multimodal target is far from a tractable reference. We introduce Iterative Exact Discrete Guidance (IEDG), a population-exact, trajectory-wise guidance framework for unnormalized discrete targets. Rather than learn the full reference-to-target correction in one step, IEDG introduces a global Boltzmann tilt along an annealing trajectory. Each stage learns a stage-local posterior correction for an incremental Boltzmann tilt of the current source, while the resulting corrections are accumulated relative to a fixed analytic posterior. At the population optimum, exact stage posteriors recover the correct reverse dynamics, whose exact simulation reproduces the target distribution. IEDG chooses stage increments by relative effective sample size (rESS), which controls Rényi-2 displacement and locally adapts the step size to the thermodynamic geometry of the annealing path. Our stagewise total-variation analysis shows that limited overlap amplifies Bregman fitting error by 1/√(rESS), while posterior, simulation, and truncation errors enter additively. IEDG improves all distribution-level errors over the neural baselines on ordered, exactly enumerated Ising 4×4, while substantially reducing one-shot errors on Ising/Potts 16×16 across thermodynamic regimes and attaining the best neural-sampler result on several reported local-statistic and phase-coverage metrics. On Max-Cut, its best-of-512 and average-sample ratios exceed all the baselines. Code and artifacts are available at https://github.com/StillFantasy123/iterative-exact-discrete-guidance.
Related
- Variational Contraction Conditions for Iterative Algorithms in Multi-Population Discrete-Time Regularized Mean-Field Games
- Continuous meets discrete: geometry dependence of the performance of iterative solutions for nonsymmetric PDEs in terms of Laplace eigenvalues
- Steering sequence generation in protein language models through Iterative Lookback Monte Carlo Sampling
- Interacting particle guidance for sampling reward-tilted generative priors
- Internal Guidance as a Sampling Method for Tilted Diffusion Models
BibTeX
@misc{qian2026iterative,
title = {{Iterative Exact Discrete Guidance for Energy-Based Sampling}},
author = {Yuwen Qian and Yidong Ouyang and Zhengyan Wan and Hongyuan Zha},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37043},
eprint = {2609.37043},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37043},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Iterative Exact Discrete Guidance for Energy-Based Sampling
AU - Yuwen Qian
AU - Yidong Ouyang
AU - Zhengyan Wan
AU - Hongyuan Zha
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37043
UR - https://arxiv.org/abs/2609.37043
AB - Sampling from unnormalized distributions over large discrete state spaces becomes difficult when a multimodal target is far from a tractable reference. We introduce Iterative Exact Discrete Guidance (IEDG), a population-exact, trajectory-wise guidance framework for unnormalized discrete targets. Rather than learn the full reference-to-target correction in one step, IEDG introduces a global Boltzmann tilt along an annealing trajectory. Each stage learns a stage-local posterior correction for an incremental Boltzmann tilt of the current source, while the resulting corrections are accumulated relative to a fixed analytic posterior. At the population optimum, exact stage posteriors recover the correct reverse dynamics, whose exact simulation reproduces the target distribution. IEDG chooses stage increments by relative effective sample size (rESS), which controls Rényi-2 displacement and locally adapts the step size to the thermodynamic geometry of the annealing path. Our stagewise total-variation analysis shows that limited overlap amplifies Bregman fitting error by 1/√(rESS), while posterior, simulation, and truncation errors enter additively. IEDG improves all distribution-level errors over the neural baselines on ordered, exactly enumerated Ising 4×4, while substantially reducing one-shot errors on Ising/Potts 16×16 across thermodynamic regimes and attaining the best neural-sampler result on several reported local-statistic and phase-coverage metrics. On Max-Cut, its best-of-512 and average-sample ratios exceed all the baselines. Code and artifacts are available at https://github.com/StillFantasy123/iterative-exact-discrete-guidance.
ER -