PaperlayerView exact revision on arXiv

Source-linked AI summary

Iterative Exact Discrete Guidance for Energy-Based Sampling

Yuwen Qian, Yidong Ouyang, Zhengyan Wan, Hongyuan Zha

arXiv:2609.37043v1cs.LGstat.ML

TL;DR

Poor overlap makes sampling from unnormalized, multimodal targets difficult because learning the global correction from a tractable reference is unstable. IEDG uses rESS-controlled incremental posterior corrections accumulated in one guide. It improves distribution recovery and sampling outcomes across the reported Ising, Potts, and Max-Cut evaluations, with rESS not covering conditional-category or rare-phase coverage.

  • Problem

    Poor overlap makes the global source-to-target density ratio concentrate on rare source states, destabilizing learning and mode coverage for unnormalized targets.

    Source: §1 · pp. 1–2

  • Method

    IEDG applies rESS-controlled incremental Boltzmann tilts, learning stage-local posterior corrections that accumulate relative to a fixed analytic posterior base.

    Source: §1 · p. 2

  • Results

    IEDG improves full-distribution recovery, substantially reduces one-shot errors on large lattices, and achieves stronger BA Max-Cut ratios than other baselines.

    Source: §1 · p. 2, §7 · p. 12

  • Takeaways & Limitations

    IEDG's stagewise posterior updates provide a population-exact route to the intended reverse dynamics when the frozen posterior matches that induced by the current source.

    Source: §7 · p. 12

    rESS controls endpoint overlap but not conditional-category coverage or rare phases, so posterior errors may propagate across stages.

    Source: §7 · p. 12

Abstract

from arXiv · show

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\'enyi-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/\sqrt{\mathrm{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\times4$, while substantially reducing one-shot errors on Ising/Potts $16\times16$ 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.

1 Introduction

Sampling unnormalized targets requires matching probability mass across configurations, but poor overlap makes the global reference-to-target correction difficult to learn. IEDG replaces that one-shot correction with ESS-controlled stagewise posterior tilts whose population-optimal updates compose exactly.

1 Introduction

  • Unnormalized energy specifies a target only up to a proportionality constant, while sampling must reproduce its probability mass across configurations.The target may include uncertainty, coexisting phases, and diverse near-optimal solutions.Source: §1 · p. 1
  • Poor overlap concentrates the source-to-target density ratio on rare source states, destabilizing learning and mode coverage.Directly applied DGM must learn the entire reference-to-target correction.Source: §1 · pp. 1–2
  • IEDG replaces the difficult global reference-to-target correction with local posterior corrections along an annealing trajectory, accumulated in one guide for terminal inference.At the population optimum, exact stagewise Bayes updates compose exactly.Source: §1 · p. 2
  • IEDG selects annealing increments by rESS, which defines a finite-step Rényi-2 trust region and locally recovers equal thermodynamic-length increments.Limited overlap amplifies stagewise Bregman fitting error in the multistage total-variation analysis.Source: §1 · p. 2
  • Across exact-distribution recovery, lattice sampling, and graph optimization, IEDG improves one-shot guidance on enumerated Ising 4 × 4 and Max-Cut, while remaining competitive on Ising and Potts 16 × 16.It improves several reported local-statistic and phase-coverage metrics on the larger lattices.Source: §1 · p. 2

2 Related Work

Discrete diffusion and flow models learn reverse dynamics or endpoint posteriors, and guidance can reweight those dynamics. IEDG differs from existing neural samplers and progressive transport by learning incremental posterior tilts relative to a fixed analytic base.

Discrete diffusion, flow, and guidance.

  • Discrete diffusion and flow models amortize transport from a simple reference by learning reverse rates or endpoint posteriors; guidance can reweight reverse dynamics through classifiers or CTMC rate corrections.DGM provides an exact posterior correction from a terminal density ratio (Wan et al., 2026).Source: Discrete diffusion, flow, and guidance · p. 2

Neural samplers for unnormalized discrete targets.

3 Preliminaries

The paper targets an energy-tilted distribution using a tractable reference and discrete flow posteriors. Posterior guidance converts a terminal density ratio into a conditional correction, which can be learned with a positive Bregman loss.

3.1 Discrete energy-based sampling

  • The target π is the normalized energy tilt of a tractable reference, with access assumed to reference samples and pointwise energy evaluations but not target samples or the partition function.In the experiments, the reference is a product of uniform distributions.Source: §3.1 · p. 3

3.2 Discrete flow models

  • Discrete flow models define a conditional path from noise to an endpoint, then marginalize endpoint-conditional rates using coordinate posteriors when the path factorizes across coordinates.For the reference endpoint law, the path is stationary and its coordinate posterior is available analytically, with full categorical support for t < 1.Source: §3.2 · pp. 3–4

3.3 Posterior-exact guidance and Bregman learning

  • Under shared conditional paths and target support contained in source support, DGM's posterior guidance identity uses a conditional expectation of the terminal density ratio to reweight the source posterior.The positive Bregman loss has a population optimum equal to the guidance term; IEDG uses the same conditional-mean property for stagewise responses.Source: §3.3 · p. 4

4 Iterative Exact Discrete Guidance

IEDG replaces one-shot reference-to-target correction with local Boltzmann tilts whose posterior corrections are accumulated relative to one analytic reference posterior. It adapts annealing steps to source-target overlap and uses the accumulated guide for terminal sampling.

4.1 Ideal annealing and the stage-local target

  • IEDG replaces one global reference-to-target correction with local Boltzmann tilts along an annealing path, expressing each updated posterior relative to the same analytic reference posterior.The ideal path starts at πref and ends at π; each stage tilts its current source.Source: §4 · p. 4, §4.1 · p. 4

4.2 Stage-local posterior correction

  • Each stage targets the exact Boltzmann tilt of its promoted source and learns a posterior correction by reweighting the source posterior with a conditional expected stage weight.The normalizer cancels under posterior normalization, so the exact stage posterior can be learned without evaluating it.Source: §4.2 · p. 5

4.3 Same-base accumulated bridge

  • IEDG accumulates stage corrections relative to one analytic posterior because successive source posteriors change and their stagewise functions cannot simply be multiplied.It freezes the fitted guide and uses direct-q sampling to produce the next stage's buffer.Source: §4.3 · pp. 5–6
  • The fixed-base posterior induced by the unique positive population minimizer equals the exact stage posterior.This is the exact same-base bridge result under the stated support conditions.Source: §4.3 · p. 6

4.4 ESS-controlled thermodynamic path

  • An rESS threshold imposes a finite-step Rényi-2 radius and locally approximates equal thermodynamic-length increments along the ideal path.IEDG chooses each increment from the current source because overlap can vary along the path.Source: §4.4 · p. 7

4.5 Sampling with the accumulated guide

  • At inference, the final guide defines posterior-marginal CTMC rates, and direct-q tau-leaping samples from them starting at πref.Final inference evaluates only the analytic reference posterior and final accumulated guide, independent of the number of training stages.Source: §4.5 · p. 7

5 Learning Error and Stagewise Stability

The analysis bounds stagewise sampling error by separating guide-fitting error from posterior mismatch, simulation, and truncation discrepancies. Limited overlap amplifies fitting error, while a stability recursion propagates prior-stage error through the annealing path.

One-stage Bregman-to-sampling bound

  • Guide-fitting error scales as ΔLk/√rESSk(Δαk), so poor overlap amplifies the sampling error; posterior, simulation, and truncation discrepancies contribute separately.The one-stage result assumes full categorical support on training contexts and positive training-time density over [0,T].Source: §5 · p. 8

Stagewise stability

  • The stagewise stability recursion separates the current fitting penalty ηk^-1/2 from remaining local discrepancies and prior-stage error propagated by Λk.The theorem assumes the support and finite-coverage conditions at every stage and rESSk(Δαk) ≥ ηk.Source: §5 · p. 8

Exact recovery

  • With exact source posteriors, population-optimal guides, and exact posterior-marginal simulation, each stage recovers its target as T approaches 1, yielding μK = π.The conclusion is conditional on these exactness assumptions and the untruncated limit.Source: §5 · p. 8

6 Experiments

The experiments evaluate IEDG on exact distribution recovery, high-dimensional lattice sampling, and graph-conditioned Max-Cut, comparing it with neural baselines and evaluation references. Results show lower distribution errors than neural baselines on enumerated Ising 4 × 4 and stronger Max-Cut ratios than one-shot DGM and PDNS.

6 Experiments

  • The experiments cover exact Ising 4 × 4 distribution recovery, 16 × 16 Ising and Potts phase transitions, and BA Max-Cut, comparing IEDG with one-shot DGM and other neural samplers.The exact-distribution experiment uses enumeration; the Max-Cut evaluation uses held-out graphs.Source: §6 · p. 9, §6.1 · p. 9, §6.3 · p. 11

6.1 Exact distribution recovery

  • IEDG achieves the lowest TV, KL, and χ2 errors among evaluated neural baselines on ordered Ising 4 × 4, but remains above the equal-budget Exact-MC floor.The reported endpoint is β = 0.6.Source: §6.1 · p. 9, Table 1 · p. 9

6.2 High-dimensional lattice models

  • The lattice evaluation uses 16 × 16 Ising and Potts models across disordered, near-critical, and ordered regimes, with local and phase-sensitive errors compared against independent SW samples.The phase-sensitive measures assess relative masses of two Ising phases and three Potts phases; all reported metrics are minimized.Source: §6.2 · pp. 9–10, Table 2 · p. 11
  • Near criticality, IEDG repairs one-shot Ising correlation and phase-coverage failures and improves Corr. agg. over MDNS; at the ordered endpoint it has the lowest Corr. error, but MDNS and MetaDNS better recover phase weights.In the disordered regime, IEDG leads learned samplers in Mag. and x↑JS.Source: §6.2 · p. 10, Figure 2 · p. 10
  • For Potts, IEDG repairs near-critical one-shot mode collapse and leads learned samplers in Mag. and Mode ℓ1 while matching the best Corr. agg.; at the ordered endpoint it improves one-shot Mag. and Corr. errors while covering all sectors.MDNS retains more accurate Mag. and phase weights.Source: Figure 2 · p. 10, §6.2 · p. 11

6.3 Graph-conditioned Max-Cut sampling

  • Across all three graph-size ranges, IEDG improves both Max-Cut ratios over one-shot DGM and PDNS, reaching the certified optimum within budget on the smallest graphs.The benchmark evaluates 512 samples per held-out graph.Source: §6.3 · p. 11, Table 3 · p. 11

7 Conclusion

IEDG accumulates ESS-controlled stagewise posterior updates in one guide, with population-optimal updates recovering intended reverse dynamics when the frozen posterior matches that induced by the current source. The conclusion reports improved distribution recovery and benchmark performance, while noting that endpoint overlap does not control conditional-category coverage or rare phases.

7 Conclusion

  • Experiments demonstrate improved full-distribution recovery, substantial gains over one-shot guidance on large lattices, and stronger BA Max-Cut ratios than other baselines.The conclusion also relates Bregman fitting error, overlap, and stagewise stability when the frozen posterior is not the current source's induced posterior.Source: §7 · p. 12
  • rESS controls endpoint overlap but not conditional-category coverage or rare phases, so posterior errors may propagate across stages.The conclusion identifies stronger variance reduction and online joint guide-and-source updates as promising directions.Source: §7 · p. 12

A Algorithms

  • Algorithm 1 adapts annealing endpoints using rESS thresholds, freezes a source-buffer posterior, trains a stage guide, and generates the next buffer when the target endpoint remains unreached.The procedure returns the final guide and annealing endpoints.Source: A Algorithms · p. 16
  • Algorithm 2 holds state-dependent rates fixed on each interval, allows at most one jump per coordinate, and uses N posterior evaluations without terminal denoising.Its finite-step error is analyzed separately.Source: A Algorithms · p. 17

A.1 ESS path construction and experimental conventions

The appendix describes groupwise empirical rESS constraints for selecting annealing increments and notes a finite-model source-promotion heuristic used in two lattice transports. It also distinguishes IEDG's accumulated posterior corrections from progressive transport methods that compose transport maps.

A.1 ESS path construction and experimental conventions

  • The applied increment is selected using the largest candidate satisfying groupwise overlap constraints, with finite-buffer group statistics estimating population rESS.Lattice buffers are split into contiguous groups, while each graph and its source states form one group; bisection evaluates the candidate using log-sum-exp.Source: §A.1 · pp. 17–18
  • For two lattice transports, an intermediate source buffer may use γsrc ∈ {1, 1.1}, but terminal sampling uses γterm = 1; nonunit source promotion is a finite-model bias-compensation heuristic.The selected source checkpoint and exponent are used only to construct the next buffer and its frozen posterior.Source: §A.1 · p. 18

B.1 Discrete diffusion, flow, and guidance

  • DGM provides an exact endpoint-posterior correction from a terminal density ratio; IEDG uses that identity with local ratios defined against the available sampler and accumulated on a shared posterior base.The passage contrasts IEDG's multistage construction with the DGM identity it builds upon.Source: §B.1 · p. 18

B.2 Neural samplers for unnormalized discrete targets

The related-work discussion contrasts neural samplers and local Markov transitions with progressive transport methods, then distinguishes IEDG’s posterior-correction approach. The appendix also explains how endpoint-conditional rates yield marginal rates and separates exact identities from numerical simulation.

B.2 Neural samplers for unnormalized discrete targets

  • Neural samplers span variational and reward-based models, combinatorial-optimization objectives, and learned CTMC rates, while locally balanced and gradient-informed proposals retain target stationarity but require per-sample chains.Variational autoregressive networks and GFlowNets provide examples of the first group; DiffUCO, SDDS, LEAPS, and DNFS illustrate other objectives.Source: §B.2 · p. 19

B.3 Progressive tempering and learned transport

  • ESS-based temperature adaptation predates IEDG; progressive alternatives use importance-weighted flow fitting, reverse-SDE self-training, MCMC-refined temperature transfer, or annealed map composition.IEDG instead learns posterior-exact local Boltzmann tilts on a common analytic base, with terminal inference using one accumulated guide.Source: §B.3 · pp. 19–20

C Extended Background: Marginalizing Conditional Rates

  • Marginalizing endpoint-conditional rates yields rates for the marginal process, but Euler or tau-leap simulation remains a separate numerical approximation.The appendix derives the identity using finite-state marginalization and Bayes’ rule.Source: C Extended Background: Marginalizing… · pp. 20–21

D Complete Proofs

The proofs connect positive Bregman regression to posterior guidance, characterize overlap-controlled annealing, and bound how fitting and implementation errors propagate across stages. Under population-optimal guides and exact terminal simulation, the stage updates recover the target.

D.1 Bregman conditional mean and excess identity

  • The positive population Bregman-loss minimizer is the conditional mean of the response, uniquely among positive predictors up to null sets.The excess-risk identity is nonnegative and vanishes only at that predictor.Source: §D.1 · p. 21

D.2 DGM posterior reweighting identity

  • The DGM posterior-guidance identity reweights the source posterior by a conditional expected density ratio, with the terminal normalizer cancelling inside the posterior.The identity uses source and target distributions sharing the same conditional path.Source: §D.2 · pp. 21–22

D.3 Posterior-exact bridge and same-base accumulation

  • With the assumed posterior equality, the population-optimal stage guide yields the exact posterior-marginal bridge, and common guide rescaling cancels from the update.The proposition’s positivity and finite-risk assumptions are stated for rate-relevant contexts.Source: §D.3 · pp. 22–23

D.4 ESS-controlled annealing geometry

  • Constant rESS matches squared thermodynamic line elements through second order, while the forward kernel contracts order-2 Rényi change of measure.The analysis also relates normalized-weight variance to rESS and uses convexity to justify the rESS search.Source: §D.4 · p. 23

D.5 Positive-tilt perturbation

  • The positive-tilt stability bound supports error propagation, while the frozen-teacher result concerns posterior stability rather than an additional exactness claim.The proposition treats the population minimizer induced by the frozen posterior.Source: §D.5 · p. 24

D.6 One-stage Bregman-to-sampling bound

  • The one-stage bound separates Bregman fitting error from posterior mismatch, simulation, and truncation terms, under stated support, training-time, and finiteness conditions.Its frozen-posterior-to-learned-posterior control does not require the frozen posterior to equal the current-source posterior.Source: §D.6 · pp. 25–27

D.7 Multistage propagation and exact recovery

  • The multistage recursion propagates stage-local errors, while its D∞ envelope is a uniform worst-case bound rather than a prediction of realized terminal error.Under population-optimal guides and exact terminal simulation, induction gives exact recovery of the target.Source: §D.7 · pp. 28–29

E Practical Training Components

The practical components add analytic local preconditioning and conditional-reweight auxiliary supervision to the core bridge objective. The appendix also outlines the experimental configurations, metrics, training protocol, baselines, and held-out reporting.

E.1 Analytic local preconditioning

  • Local message passing preconditions the accumulated guide on 16 × 16 lattices, changing its parameterization but not the bridge objective or population target.Because the periodic lattice approximation can become overly sharp as correlations strengthen, the implementation softens it across the specified regimes.Source: §E.1 · pp. 29–30

E.2 Conditional-reweight auxiliary supervision

  • Conditional-reweight supervision Rao–Blackwellizes Gibbs records, but its finite-sample ratio estimate is not generally unbiased and targets an idealized physical source rather than the learned source.It is auxiliary supervision, not part of the exact bridge claim; the main experiments enable it only in near-critical Ising and Potts 16 × 16 regimes.Source: §E.2 · pp. 30–31

F Experimental Protocol and Reproducibility

  • The reproducibility appendix specifies benchmark configurations, reference distributions, metrics, training and model-selection protocols, baseline provenance, and held-out reporting.Controlled studies and additional diagnostics are collected separately in Appendix G.Source: F Experimental Protocol and… · p. 31

F.1 Benchmarks and reference construction

The appendix specifies benchmark references, metrics, and experimental protocols, then tests how path resolution and practical components affect results. These studies show target- and statistic-specific tradeoffs in stage count and component choices.

F.1 Benchmarks and reference construction

  • Ising 4 × 4 uses an enumerated target, large-lattice references use SW pools, and certified Max-Cut optima normalize optimization quality.The Ising reference is enumerated exactly; the Max-Cut solves have zero recorded MIP gap.Source: §F.1 · pp. 32–33

F.2 Evaluation metrics

  • Evaluation covers exact-state distribution errors, lattice magnetization, correlation and phase metrics, plus best-of-budget and average Max-Cut ratios.Source: §F.2 · pp. 33–35

F.3 Models, training, and model selection

  • IEDG uses frozen ESS-controlled paths and direct-q terminal sampling; validation selects checkpoints before test evaluation, while baselines use released or matched protocols.Source: §F.3 · pp. 36–37

F.4 Data separation and reporting

  • Independent SW and rollout seeds separate validation from test evaluation; Max-Cut test graphs and certified optima are excluded from training and model selection.Source: §F.4 · p. 38

G Additional Experimental Results

  • The ablations test stage count, fixed-count scheduling, two training components, and residual errors under shared budgets, architectures, and evaluation conditions.Source: G Additional Experimental Results · p. 38

G.1 How many annealing stages are needed?

  • Stage count is not monotone: canonical paths give the strongest joint correlation and phase recovery, while denser Max-Cut paths help and another Potts bridge weakens all three errors.The finer Ising path improves magnetization.Source: §G.1 · p. 39

G.2 Does ESS-controlled scheduling help at fixed stage count?

  • At matched stage count, ESS control improves Ising correlation and phase recovery and both Max-Cut ratios, while uniform spacing lowers Ising magnetization error.Source: §G.2 · p. 39

G.3 Which practical components matter?

  • λCR = 1 gives the best correlation recovery in both systems and Potts phase balance; half-scale preconditioning lowers errors across both near-critical transitions.Source: §G.3 · p. 40

G.4 What distributional errors remain?

The appendix checks Ising 4 × 4 observables and residual distributional errors on large lattices. IEDG improves on one-shot errors, but energy marginals and Potts phase geometry remain sources of discrepancy.

G.4 What distributional errors remain?

  • Table 14 completes the remaining Ising 4 × 4 distributional regimes; Table 15 evaluates energy and nearest-neighbor-correlation errors across the full sweep.Source: §G.4 · pp. 40–41, Table 14 · p. 41, Table 15 · p. 41
  • IEDG improves Ising energy and nearest-neighbor-correlation errors over one-shot DGM throughout the sweep; against UDNS, it wins in disordered and near-critical regimes, while ordered-regime energy and correlation favor different methods.Both IEDG and UDNS remain above the Exact-MC floor in the ordered regime.Source: Table 15 · p. 41, §G.4 · p. 41
  • Across large-lattice diagnostics, iteration largely repairs one-shot DGM’s near-critical correlation errors and preserves spatial structure, while residual errors concentrate in energy marginals and Potts CV-plane geometry.These discrepancies indicate residual phase-weight and within-mode errors rather than complete mode collapse.Source: Table 16 · p. 42, Table 17 · p. 42, §G.4 · p. 42

Related papers

Loading 2609.37043v1…