cs.LGSep 29, 2026

Iterative Exact Discrete Guidance for Energy-Based Sampling

Authors: Yuwen Qian, Yidong Ouyang, Zhengyan Wan, Hongyuan Zha

Organizations: School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen · Department of Statistics, University of California, Los Angeles · School of Data Science, The Chinese University of Hong Kong, Shenzhen

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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/rESS1/\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×44\times4, while substantially reducing one-shot errors on Ising/Potts 16×1616\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.

Figures & tables

Figure 1: IEDG training. Samples from the current buffer Bk\mathcal{B}_{k} estimate rESS and set the next annealing increment Δαk\Delta\alpha_{k} . The energy weight wkw_{k} and frozen posterior ratio Ak−1,tdA_{k-1,t}^{d} form the regression response Rk,tdR_{k,t}^{d} , whose conditional mean is learned by positive Bregman regression as the accumulated guide GψkG_{\psi_{k}} . Combined with the analytic reference posterior, this defines qψk,1∣tdq_{\psi_{k},1\mid t}^{d} , whose direct- qq rollout produces the next buffer Bk+1\mathcal{B}_{k+1} .
MethodTV\mathrm{TV}KL(p^∥π)\mathrm{KL}(\widehat{p}\|\pi)χ2(p^∥π)\chi^{2}(\widehat{p}\|\pi)
Exact MC0.00411±0.000190.00411{\pm}0.000190.00426±0.000060.00426{\pm}0.000060.0515±0.01220.0515{\pm}0.0122
One-shot DGM0.7792.55722
UDNS (reproduced)0.1500.1650.237
MDNS ( FWDCEF_{\rm WDCE} ) †0.04180.02821.66
IEDG0.03140.009930.229
Table 1: Distribution-level errors on exactly enumerated Ising 4×44\times 4 at β=0.6\beta=0.6 (lower is better). Exact MC is the equal-budget i.i.d. reference; †\dagger marks the MDNS-reported FWDCEF_{\rm WDCE} result. Bold marks the best neural sampler.
Figure 2: Phase coverage on 16×1616\times 16 lattices: Ising x↑x_{\uparrow} histograms (a–c) and Potts sorted dominant-mode mass residuals relative to SW (d–f) across three regimes. In (a–c), the upper subpanels show the full distributions, while the maps below show signed per-bin residuals on a common symmetric-log scale (red: excess; blue: deficit). Panel (f) omits the off-scale one-shot curve.
 β=0.28\beta=0.28β=0.4407\beta=0.4407β=0.6\beta=0.6
MethodMag.Corr. agg.x↑x_{\uparrow} JS Mag.Corr. agg.x↑x_{\uparrow} JS Mag.Corr. agg.x↑x_{\uparrow} JS 
Analytic preconditioner0.006151.510.0863 0.0040916.50.609 0.016927.10.693 
MDNS (official ckpt.)0.01120.1610.00937 0.01050.1710.00980 0.01730.05820.00336 
MetaDNS (official ckpt.)0.008390.1950.00889 0.03170.1240.0132 0.004900.08920.00574 
One-shot DGM0.01120.4020.0159 0.058716.30.599 0.17026.80.693 
IEDG0.006130.2420.00742 0.01060.1500.0252 0.01570.05370.0193 
Table 2: Sampling 16×1616\times 16 lattice models across thermodynamic regimes (lower is better). Bold marks the best result.
 n∈[20,32]n\in[20,32]n∈[40,64]n\in[40,64]n∈[100,128]n\in[100,128]
MethodMax.Avg.Max.Avg.Max.Avg.
Uniform0.8880.6960.8250.6870.7690.678
One-shot DGM0.9620.8540.8840.7980.8140.748
PDNS †0.9630.9110.8970.8690.8760.840
IEDG1.000.9650.9870.9200.9150.871
Table 3: BA Max-Cut approximation ratios on 32 held-out graphs (higher is better), using 512 samples per graph. †\dagger marks PDNS values ( Guo et al., 2025 ) . Bold marks the best result.
Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

 Rk,td←wk(X1)c^kp^k−1,1∣td(X1d∣Xt)pref,1∣td(X1d∣Xt)R_{k,t}^{d}\leftarrow\frac{w_{k}(X_{1})}{\widehat{c}_{k}}\frac{\widehat{p}_{k-1,1\mid t}^{d}(X_{1}^{d}\mid X_{t})}{p_{\mathrm{ref},1\mid t}^{d}(X_{1}^{d}\mid X_{t})} 
Appendix
Algorithm 1 Iterative Exact Discrete Guidance training
BenchmarkSize∣S∣|\mathcal{S}|Target parameterReferenceGeneratedNFE
Ising-exact4×44\times 42β=.28,.4407,.6\beta=.28,.4407,.6Enumeration2202^{20}128/256/256
Ising16×1616\times 162β=.28,.4407,.6\beta=.28,.4407,.6SW4096256
Potts16×1616\times 163β=.5,1.005,1.2\beta=.5,1.005,1.2SW4096256
BA Max-Cut[20,32][20,32]2λcut=5\lambda_{\rm cut}=5Certified optimum512/graph128
 [40,64][40,64]2λcut=5\lambda_{\rm cut}=5Certified optimum512/graph128
 [100,128][100,128]2λcut=5\lambda_{\rm cut}=5Certified optimum512/graph128
Appendix
Table 4: Benchmark and terminal-evaluation configurations. “Reference” denotes the distribution used to compute evaluation errors.
TargetStatesMag.Corr. agg.x↑x_{\uparrow} JSMode ℓ1\ell_{1}CV JS
Ising β=.4407\beta=.44074,096.00416.190.0144––
 65,536.00201.0573.00102––
Potts β=1.005\beta=1.0054,096.0635.143–.0244.0555
 65,536.0280.0183–.00497.00379
Appendix
Table 5: Near-critical SW reference stability (seed 0 versus seed 1; zero is ideal). Metrics use the same fixed definitions as model evaluation; dashes denote inapplicable phase statistics.
BenchmarkMain-text metricsSupplemental evidence
Ising 4×44\times 4TV, KL, χ2\chi^{2}regime sweep; observables
Ising 16×1616\times 16Mag., Corr. agg., x↑x_{\uparrow} JSJEJ_{E} , Corr.-curve; marginal plots
Potts 16×1616\times 16Mag., Corr. agg., Mode ℓ1\ell_{1}JEJ_{E} , Corr.-curve, CV JS; marginal/CV plots
BA Max-CutRmax⁡R_{\max} , RavgR_{\rm avg}stage-count and path-schedule ablations
Appendix
Table 6: Metric map. Main-text columns are the primary evidence for each benchmark; Appendix G.4 reports the listed complementary distributional diagnostics.
Reported targetBackboneW/D/HBatchUpdatesOptimizerLREMASource buffer
Ising 4×44\times 4 , β=.28\beta=.28tiny MLP–51290000Adam10−410^{-4}.9991000000
Ising 4×44\times 4 , β=.4407\beta=.4407tiny MLP–102465000Adam10−410^{-4}.9951000000
Ising 4×44\times 4 , β=.6\beta=.6tiny MLP–102470000Adam10−410^{-4}.9951000000
Ising 16×1616\times 16 , β=.28\beta=.28RoPE DeiT2D64/4/4102435000Adam4 ⁣× ⁣10−54\!\times\!10^{-5}.999131072
Ising 16×1616\times 16 , β=.4407\beta=.4407RoPE DeiT2D64/4/451265000Adam4 ⁣× ⁣10−54\!\times\!10^{-5}.999100000
Ising 16×1616\times 16 , β=.6\beta=.6RoPE DeiT2D64/4/451265000Adam4 ⁣× ⁣10−54\!\times\!10^{-5}.999100000
Appendix
Table 7: Training configurations for the formal IEDG results. Each lattice row is the path segment ending at the reported β\beta ; “updates” is its realized segment budget or global cap. Width/depth/heads (W/D/H) describes the principal guide; LR and EMA denote learning rate and exponential-moving-average decay, and source buffer is the number of initially generated source states (per graph for Max-Cut).
Reported targetFrozen segment endpointsStages KK
Ising 4×44\times 4 , β=.28\beta=.280,.1,.19,.280,.1,.19,.283
Ising 4×44\times 4 , β=.4407\beta=.4407.28,.36,.4407.28,.36,.44072
Ising 4×44\times 4 , β=.6\beta=.6.4407,.50232,.6.4407,.50232,.62
Ising 16×1616\times 16 , β=.28\beta=.280,.0769,.1502,.2186,.280,.0769,.1502,.2186,.284
Ising 16×1616\times 16 , β=.4407\beta=.4407.28,.3195,.3555,.3865,.413,.4407.28,.3195,.3555,.3865,.413,.44075
Ising 16×1616\times 16 , β=.6\beta=.6.4407,.472,.51,.552,.6.4407,.472,.51,.552,.64
Appendix
Table 8: Frozen ESS-controlled path segments used for the formal IEDG results. Lattice endpoints are inverse temperatures β\beta ; Max-Cut endpoints are effective inverse temperatures λ\lambda in Equation F.1 . The adaptive Ising- 16×1616\times 16 , β=.28\beta=.28 interior endpoints are rounded to four decimals.
ComparisonParameters or sourceTerminal generationEvidence
Uniform (Max-Cut)nonei.i.d. base sampleslocal
Analytic preconditionerfixed BP field, Δψ≡0\Delta_{\psi}\equiv 0direct- qq , matched samples/NFElocal
One-shot DGMtrained by usdirect- qqlocal
UDNSDASBS-based reproductionfactorized uniform CTMClocal
MDNS (Ising 4×44\times 4 )value from MDNSreported native setuppublished †
MDNS ( 16×1616\times 16 lattices)released checkpointsnative samplerlocal
Appendix
Table 9: Baseline provenance and terminal generation protocol.
Setting{θk}k=0K\{\theta_{k}\}_{k=0}^{K}KKMag.Corr. agg.Phase error
Ising 0.28 ⁣→ ⁣0.44070.28\!\to\!0.4407{.280,.329,.373,.409,.441}\{.280,.329,.373,.409,.441\}47.26×10−37.26{\times}10^{-3}5.38×10−15.38{\times}10^{-1}6.37×10−26.37{\times}10^{-2}
 {.280,.320,.356,.387,.413,.441}\{.280,.320,.356,.387,.413,.441\}5 (canonical)1.06×10−21.06{\times}10^{-2}1.50×10−1\mathbf{1.50{\times}10^{-1}}2.52×10−2\mathbf{2.52{\times}10^{-2}}
 {.280,.313,.344,.373,.398,.420,.441}\{.280,.313,.344,.373,.398,.420,.441\}65.42×10−3\mathbf{5.42{\times}10^{-3}}2.10×10−12.10{\times}10^{-1}3.75×10−23.75{\times}10^{-2}
Potts 0.5 ⁣→ ⁣1.0050.5\!\to\!1.005{.500,.637,.759,.865,.946,1.005}\{.500,.637,.759,.865,.946,1.005\}51.30×10−11.30{\times}10^{-1}6.32×10−16.32{\times}10^{-1}3.91×10−23.91{\times}10^{-2}
 {.500,.625,.738,.839,.920,.970,1.005}\{.500,.625,.738,.839,.920,.970,1.005\}6 (canonical)1.08×10−1\mathbf{1.08{\times}10^{-1}}1.23×10−1\mathbf{1.23{\times}10^{-1}}1.09×10−2\mathbf{1.09{\times}10^{-2}}
 {.500,.598,.692,.775,.851,.914,.963,1.005}\{.500,.598,.692,.775,.851,.914,.963,1.005\}73.93×10−13.93{\times}10^{-1}4.91×10−14.91{\times}10^{-1}9.62×10−29.62{\times}10^{-2}
Appendix
Table 10: Sensitivity to the number of annealing stages. Paths are shown in the result rows (endpoints rounded to three decimals); lower lattice errors and higher Max-Cut ratios are better. The phase metric is x↑x_{\uparrow} JS for Ising and Mode ℓ1\ell_{1} for Potts.
SettingSchedule{θk}k=0K\{\theta_{k}\}_{k=0}^{K}KKMag.Corr. agg.x↑x_{\uparrow} JS
Ising 0.28 ⁣→ ⁣0.44070.28\!\to\!0.4407Matched- KK uniform{.280,.312,.344,.376,.409,.441}\{.280,.312,.344,.376,.409,.441\}55.58×10−3\mathbf{5.58{\times}10^{-3}}3.17×10−13.17{\times}10^{-1}2.61×10−22.61{\times}10^{-2}
 ESS-controlled (canonical){.280,.320,.356,.387,.413,.441}\{.280,.320,.356,.387,.413,.441\}51.06×10−21.06{\times}10^{-2}1.50×10−1\mathbf{1.50{\times}10^{-1}}2.52×10−2\mathbf{2.52{\times}10^{-2}}
Appendix
Table 11: ESS-controlled and uniform schedules at matched stage count and total training/evaluation budgets. Paths are rounded to three decimals.
SettingλCR\lambda_{\mathrm{CR}}Mag.Corr. agg.Phase error
Ising 0.28 ⁣→ ⁣0.44070.28\!\to\!0.44070.52.37×10−22.37{\times}10^{-2}3.14×10−13.14{\times}10^{-1}4.01×10−24.01{\times}10^{-2}
 1.0 (canonical)1.06×10−21.06{\times}10^{-2}1.50×10−1\mathbf{1.50{\times}10^{-1}}2.52×10−22.52{\times}10^{-2}
 2.05.73×10−3\mathbf{5.73{\times}10^{-3}}9.59×10−19.59{\times}10^{-1}1.89×10−2\mathbf{1.89{\times}10^{-2}}
Potts 0.5 ⁣→ ⁣1.0050.5\!\to\!1.0050.51.99×10−11.99{\times}10^{-1}2.81×10−12.81{\times}10^{-1}1.24×10−21.24{\times}10^{-2}
 1.0 (canonical)1.08×10−1\mathbf{1.08{\times}10^{-1}}1.23×10−1\mathbf{1.23{\times}10^{-1}}1.09×10−2\mathbf{1.09{\times}10^{-2}}
 2.03.31×10−13.31{\times}10^{-1}1.231.231.53×10−21.53{\times}10^{-2}
Appendix
Table 12: Sensitivity to conditional-reweight strength. All other components, including analytic preconditioning and stagewise response normalization, remain enabled at their canonical settings.
Settingρpre\rho_{\mathrm{pre}}Mag.Corr. agg.Phase error
Ising 0.28 ⁣→ ⁣0.44070.28\!\to\!0.44070.5 (canonical)1.06×10−2\mathbf{1.06{\times}10^{-2}}1.50×10−1\mathbf{1.50{\times}10^{-1}}2.52×10−2\mathbf{2.52{\times}10^{-2}}
 1.01.73×10−21.73{\times}10^{-2}1.431.438.92×10−28.92{\times}10^{-2}
Potts 0.5 ⁣→ ⁣1.0050.5\!\to\!1.0050.5 (canonical)1.08×10−1\mathbf{1.08{\times}10^{-1}}1.23×10−1\mathbf{1.23{\times}10^{-1}}1.09×10−2\mathbf{1.09{\times}10^{-2}}
 1.03.38×10−13.38{\times}10^{-1}2.842.844.26×10−24.26{\times}10^{-2}
Appendix
Table 13: Sensitivity to the analytic-preconditioner ratio scale in the near-critical regime; preconditioning remains enabled in every row.
β\betaMethodTV\mathrm{TV}KL(p^∥π)\mathrm{KL}(\widehat{p}\|\pi)χ2(p^∥π)\chi^{2}(\widehat{p}\|\pi)
0.28Exact MC0.0664±0.000180.0664{\pm}0.000180.0323±0.000210.0323{\pm}0.000210.0626±0.000640.0626{\pm}0.00064
 One-shot DGM0.1930.1490.341
 UDNS (reproduced)0.09090.04120.0931
 MDNS ( FWDCEF_{\rm WDCE} ) †0.07990.03820.0868
 IEDG0.08600.03800.0823
0.4407Exact MC0.0221±0.000240.0221{\pm}0.000240.0193±0.000100.0193{\pm}0.000100.0627±0.002850.0627{\pm}0.00285
Appendix
Table 14: Full-distribution recovery in the remaining Ising 4×44\times 4 regimes (lower is better). Exact MC is the equal-budget i.i.d. reference; UDNS is our DASBS-based reproduction and †\dagger denotes values reported by MDNS. Bold marks the best neural sampler.
β\betaMethod∣ΔE∣|\Delta E|∣ΔCnn∣|\Delta C_{\rm nn}|
0.28Exact MC0.00523±0.006090.00523{\pm}0.006090.000150±0.0001880.000150{\pm}0.000188
 One-shot DGM3.530.108
 UDNS (reproduced)0.7400.0224
 IEDG0.6610.0203
0.4407Exact MC0.00940±0.005620.00940{\pm}0.005620.000284±0.0001770.000284{\pm}0.000177
 One-shot DGM10.70.319
Appendix
Table 15: Observable errors on Ising 4×44\times 4 (lower is better). Exact MC is the equal-budget i.i.d. reference; bold marks the best neural sampler.
β\betaMetricAnalytic precond.MDNSMetaDNSOne-shot DGMIEDG
0.28JEJ_{E}0.6200.002300.003770.01230.00433
 Corr.-curve0.04620.002350.001250.01210.00682
0.4407JEJ_{E}0.6930.001890.005480.6930.0223
 Corr.-curve0.5160.004670.003600.5070.00275
0.6JEJ_{E}0.6930.001170.003140.6930.00445
 Corr.-curve0.8480.001000.0009080.8030.000623
Appendix
Table 16: Two complementary residual diagnostics for the 16×1616\times 16 lattices: energy-marginal JS ( JEJ_{E} ) and translational correlation-curve MAE (Corr.-curve; lower is better). Bold marks the best result.
β\betaAnalytic precond.MDNSMetaDNSOne-shot DGMIEDG
0.50.01430.01040.01190.008970.00868
1.0050.6460.03470.05480.6580.0818
1.20.6930.003320.01110.6930.0329
Appendix
Table 17: Fixed-grid Potts CV JS across the disordered, near-critical, and ordered regimes (lower is better). Bold marks the best result.
Figure 3: Regime-wide one-dimensional marginals from the frozen 4,096-sample payloads. Columns traverse the disordered, near-critical, and ordered regimes; rows show Ising energy per site and x↑x_{\uparrow} , followed by Potts energy per site and mPm_{\mathrm{P}} . All methods share histogram edges fixed from the analytic support, with SW (black) as the test reference.
Figure 4: Near-critical signed-displacement correlation profiles for Ising at β=0.4407\beta=0.4407 and Potts at β=1.005\beta=1.005 . Unlike Corr. agg., these profiles resolve spatial dependence at each separation. Upper panels compare each empirical curve with SW; lower panels show ∣cmethod(r)−cSW(r)∣|c_{\rm method}(r)-c_{\rm SW}(r)| on a logarithmic scale. The deterministic self-correlation at r=0r=0 is omitted. Relative to one-shot DGM, the IEDG residual is reduced across separations rather than at a single displacement.
Figure 5: Potts phase geometry at β=1.005\beta=1.005 . Unlike Mode ℓ1\ell_{1} , which compares only ranked sector masses, the two-dimensional CV plane exposes within-sector geometry. IEDG recovers the three symmetry-related directions absent from one-shot DGM, while excess inter-sector probability explains its remaining CV JS gap. All methods use the same fixed 50×5050\times 50 grid and logarithmic probability scale.
Figure 6: Representative ordered-endpoint configurations. Columns denote methods; rows show Ising at β=0.6\beta=0.6 and Potts at β=1.2\beta=1.2 . Indices {973,2172,2598,4081}\{973,2172,2598,4081\} are drawn once with seed 2701 and reused across each method’s independently generated 4,096-state payload. This qualitative check is not used for checkpoint selection; Potts colors are shared across methods.

Explore similar work

CardsList

  1. One-Step Sampler for Boltzmann Distributions via Drifting

    Mar 18, 2026Wenhan Cao, Keyu Yan, Lin ZhaoOne-Step Generative Modeling

    Department of Electrical and Computer Engineering, National University of Singapore

  2. Fixed-point neural samplers on discrete spaces

    Oct 1, 2026Jiajun He, Denis Blessing, Mouyang Cheng +2Diffusion Models

    MIT · Microsoft Research New England

  3. A Generative Sampler for distributions with possible discrete parameter based on Reversibility

    Mar 10, 2026Lei Li, Zhen Wang, Lishuo ZhangGenerative ModelingMarkov Chain Monte Carlo

    School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai, 200240, P.R.China. · Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University, Shanghai, 200240, P.R.China.