Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics
Authors: Sebastian Sanokowski
Wilhelm Franz Berghammer
Haoyu Peter Wang
Martin Ennemoser
Sepp Hochreiter
Sebastian Lehner
Venue: ICLR 2025 Poster (2025)
Keywords: Combinatorial Optimization
Diffusion Models
Statistical Physics
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: Realizing discrete Diffusion Samplers with more diffusion steps with the application in combinatorial optimization and statistical physics.

Abstract: Learning to sample from complex unnormalized distributions over discrete domains emerged as a promising research direction with applications in statistical physics, variational inference, and combinatorial optimization. Recent work has demonstrated the potential of diffusion models in this domain. However, existing methods face limitations in memory scaling and thus the number of attainable diffusion steps since they require backpropagation through the entire generative process. To overcome these limitations we introduce two novel training methods for discrete diffusion samplers, one grounded in the policy gradient theorem and the other one leveraging Self-Normalized Neural Importance Sampling (SN-NIS). These methods yield memory-efficient training and achieve state-of-the-art results in unsupervised combinatorial optimization.
Numerous scientific applications additionally require the ability of unbiased sampling. We introduce adaptations of SN-NIS and Neural Markov Chain Monte Carlo that enable for the first time the application of discrete diffusion models to this problem. We validate our methods on Ising model benchmarks and find that they outperform popular autoregressive approaches. Our work opens new avenues for applying diffusion models to a wide range of scientific applications in discrete domains that were hitherto restricted to exact likelihood models.

Published as a conference paper at ICLR 2025
SCALABLE DISCRETE DIFFUSION SAMPLERS: COMBI- NATORIAL OPTIMIZATION AND STATISTICAL PHYSICS
Sebastian Sanokowski'
Wilhelm Berghammer
Martin Ennemoser
Haoyu Peter Wang
Sepp Hochreiter 1,3
Sebastian Lehner
1 ELLIS Unit Linz, LIT AI Lab, Johannes Kepler University Linz, Austria 2 Department of Electrical Computer Engineering, Georgia Institute Technology
NXAI Lab NXAI GmbH, Linz, Austria
ABSTRACT
Learning to sample from complex unnormalized distributions over discrete do- mains emerged as promising research direction with applications in statistical physics, variational inference, and combinatorial optimization. Recent work has demonstrated the potential of diffusion models in this domain. However, exist- ing methods face limitations in memory scaling and thus the number of attainable diffusion steps since they require backpropagation through the entire generative process. To overcome these limitations introduce novel training methods for discrete diffusion samplers, one grounded in the policy gradient theorem and the other one leveraging Self-Normalized Neural Importance Sampling (SN-NIS). These methods yield memory- mnemory-efficient training and achieve state-of ttate-of-thee of-the-art results in unsupervised combinatorial optimization. Numerous scientific applications ad- ditionally require the ability of unbiased sampling. We introduce adaptations of SN-NIS and Neural Markov Chain Monte Carlo that enable for the first time the application of discrete diffusion models to this problem. We validate our methods on Ising model benchmarks and find that they outperform popular autoregressive approaches. Our work opens new avenues for applying diffusion models to wide range of scientific applications discrete domains that were hitherto restricted to exact likelihood models.
INTRODUCTION
Sampling from unnormalized distributions crucial in a wide range scientific domains, including statistical physics, variational inference, and combinatorial optimization (CO) (Wu et al. 2019
Shih & Ermon 2020, Hibat-Allah et al., [02II.. We refer to research on using neural networks to learn how to sample unnormalized distributions Neural Probabilistic Optimization (NPO). In NPO, a target distribution is approximated using probability distribution that is parameterized by neural network. Hence, the goal is learn approximate distribution in setting, where only unnormalized sample probabilities can be calculated. Importantly, no samples from the target distribution are available, i.c. we are working in the data-free problem setting. the following, we consider binary state variables X E {0, 1J where N represents the system size. The unnormalized target distribution is typically implicitly defined by an accessible energy function H {0, 1) R. The target distribution is defined to be the corresponding Boltzmann distribution:
exp (-3H(X))
Pn
where
2= = Σ exp (xH((-3
(1)
Z
"Code availahle at: pettss:/ggithe com.m/ jku/D Ffuco Correspondance sanokowski [at]m]. jku.at

---

Published as a conference paper at ICLR 2025
Here 3 : 1/T is the inverse temperature, and 2 is the partition sum that normalizes the distribution. An analogous formulation applies to continuous problem domains. Unbiased sampling from this distribution is typically computationally expensive due to the exponential number (2 of states. Sampling techniques, such as Markov Chain Monte Carlo (Metropolis et al., 1953) are employed with great success in applications in statistical physics. Nevertheless, their applicability is typically limited due to issues related to Markov chains getting stuck in local minima and large autocorrelation times (Nicoli al. 2020 McNaughton et al. 2020). Recently, the application of deep generative models has gained increasing attention as an approach to this problem. Initial methods in NPO relied on exact likelihood models where 90 (x( could be efficiently evaluated. Boltzmann Generators (Noé & Wu 2018) are a notable example in the continuous setting, using normalizing flows to approximate Boltzmann distributions for molecular configurations. In the discrete setting, Wu et al. (2099); Hibattiiaat-Allln Hibat-Allah et al. (202T) use autoregressive models to approximate Boltzmann distributions of spin systems in the context of statistical and condensed matter physics. Inspired by the success of diffusion models (Sohs-Dickstein et al. 2015: Ho et al. 2020) in image generation, there is growing interest in so-called diffusion samplers where these models are applied to NPO problems in discrete (Sanokowski al.) 2024) and continuous settings (Zhang & Chen 2022). Diffusion models particularly intriguing in the discrete setting due to the lack of viable alternatives. Normalizing flows, which are a popular choice for continuous problems, cannot be directly applied in discrete settings, leaving autoregressive models as the most popular alternative. However, autoregressive approaches face significant limitations. They become computationally prohibitive as the system size grows. There are complexity theoretical results (Lin et al.) 202T) and empirical results (Sanokowski jet al., 2024) that suggest that they are less efficient distribution learners than latent variable models like diffusion models. Consequently, we consider diffusion models as more promising approach to discrete NPO. However, existing diffusion-basee methods for sampling on discrete domains face two major challenges:
1. Memory Scaling: They rely on a loss that is based on the reverse Kullback-Leibler (KL) diver- gence which necessitates that the entire diffusion trajectory is kept in memory for backpropaga- tion (see Sec. 2.1). This linear memory scaling limits the number of applicable diffusion steps and hence the achievable model performance. This is in sharp contrast diffusion models in e.g. image generation, which benefit from the capability of using a large number of diffusion steps.
2. Unbiased Sampling: For many scientific applications, learned distribution is only valuable if it allows for unbiased sampling, i.e., the unbiased computation of expectation values. Autore- gressive models allow this through importance sampling or Markov Chain Monte Carlo methods based on their exact sample likelihoods. However, unbiased sampling with approximate likeli- hood models on discrete domains remains so far unexplored.
We introduce our method Scalable Discrete Diffusion Sampler (SDDS) by proposing two novel training methods in Sec. 3.1 to address the memory scaling issue and the resulting limitation on the number of diffusion steps in NPO applications of discrete diffusion models:
1. reverse KL objective: Employs the policy gradient theorem for minimization of the reverse KL di- vergence and integrates Reinforcement Learning (RL) techniques to mitigate the aforementioned linear memory scaling.
forward KL objective: Adapts Self- Normalized Neural Importance Sampling to obtain asymptot- ically unbiased gradient estimates for the forward KL divergence. This approach mitigates the linear memory scaling by using Monte Carlo estimates of the objective across diffusion steps.
In Sec. we compare our proposed objectives to previous approaches and demonstrate that the reverse based objective achieves new state-of-the-an results on 6 out of 7 unsupervised Combi- natorial Optimization (UCO) benchmarks and on par on one benchmark.
Secondly, to eliminate bias in the learned distribution, we extend two established methods Self- Normalized Neural Importance Sampling (SN-NIS) and Neural Markov Chain Monte Carlo (NM- CMC)- to be applicable to approximate likelihood models such as diffusion models. We introduce these methods in Sec and validate their effectiveness using the Ising model in S.2 highlight- ing the advantages of diffusion models over autoregressive models. Our experiments show that the forward KL divergence- based objective excels in unbiased sampling. We hypothesize that this is due to its mass-covering property. Our experiments show that the mass-covering property is also
2

---

Published as a conference paper at ICLR 2025
beneficial in UCO when sampling many solutions from the model obtain optimal solution. Conversely, the reverse KL-based objective performs better in UCO contexts where only a few so- lutions are sampled when good average solution quality is prioritized.
2 PRELIMINARY: NEURAL PROBABILISTIC OPTIMIZATION
The goal of NPO is to approximate a known target probability distribution (X) using probabilis- tic model parameterized by a neural network. This technique leverages the flexibility and expressive power of neural networks to model complex distributions. The objective is to train the neural net- work to represent a probability distribution go( (X) that approximates the target distribution without requiring explicit data from the target distribution. This approximation can generally be achieved by minimizing a divergence between the two distributions. One class of divergences used for this purpose alpha divergences (Minka al. 2005
Amari 2012):
( (x(() -dx
Da (a (X)))(XX))g0gX))
(1-a)
By selecting a specific value of a, this divergence can be used as a loss function for training the model, and the choice of influences the bias of the learned distribution. For instance, for a S 0 the resulting distribution is mode seeking, which means the model focuses on the most probable modes of the target distribution, potentially ignoring less probable regions. Whereas, for covering, meaning the model spreads its probability mass to cover more of the state space, including less probable regions. As a - 1 the divergence equals the forward Kullback-Leibler divergence (fKL) DEL (P& (X) qo(()) and as a - 0 it equals the reverse Kullback-Leible divergence (rKL) DKL (ge(X) PB (X)) (Minka et al., (2005). The two divergences, rKL and fKL are particularly convenient in this context due to the product rule of logarithms that we utilize in this paper to realize diffusion models with more diffusion steps (see Sec. 3.1)
it is mass-
2.1 DISCRETE DIFFUSION MODELS FOR NEURAL PROBABILISTIC OPTIMIZATION
In discrete time diffusion models, forward diffusion process transforms the target distribution (Nx) into a stationary distribution q(Xr) through iterative sampling of a noise distribution p( p(X.)X,-1) where E {1,T) for total of T iterations. The diffusion model is supposed to model the reverse process, iec to map samples XT g(XT) to Xo ~ PB(Xo by iteratively sampling (X) The probability of a diffusion path Xo.T (Xo. .... XT) of the reverse process can be calculated with (x)r) = ((r)) II (X(x_1|) and (X,- is chosen so that samples Xo.r (o(oo) be efficiently drawn. Usually, in the reverse process, the diffusion model is explicitly conditioned on the diffusion step i, such that the distribution of the reverse diffusion step be written qo (X,-1 X,, t). However, in the following.
will drop the dependence on to simplify the notation. The unnormalized probability of a diffusion path of (n( IT p( (X-.)...... )- In the data-
the forward process can be calculated with P(X..T) free setting samples Xo.T ~ p( (())r)) are not available. (Sanokowski et al. (2024) invoke the Data Processing Inequality to introduce diffusion models in discrete NPO by proposing to use the rKI. of joint probabilities DKL 1 (Xo.r) p(Xo:T) as a tractable upper bound of the rKL of the marginals DKL (go((g)Xo)) (Xo)). They further simplify this objective to express in the following form:
T DEl (go (ooXoo))ll((xz)))) -T
T.
x Ex (Xerr) (X(90(X(-1Xx)))
t=1
(2)
T
E X 1rr [log (xrrpp(X111 X,(X,-1)]
( ((x))) C,
where T is the temperature, C' parameter independent constant and S(.) the Shannon entropy. In practice, the expectation over Xo:r ~ qo (xxo:)) ) is estimated using M diffusion paths, where each diffusion path corresponds to sample of Xe-r from the model. The objective is optimized using the log-derivative trick to propagate the gradient through the expectation over qa- Examination of Eq, shows that the memory required for backpropagation scales linearly with the number of diffusion
3

---

Published as a conference paper at ICLR 2025
steps, since backpropagation has to be performed through the expectation values for each time step t. Within a fixed memory budget, this results in a limitation on the number of diffusion steps and hence the model performance. To address these issues, we propose two alternatives to this objective, which are discussed in Sec. 3
2.2 UNSUPERVISED COMBINATORIAL OPTIMIZATION
Sanokowski et al. (2024) apply diffusion models in UCO by reformulating as an NPO prob- lem. There is wide class of CO problems that can be described in QUBO formulation (Lu-
cas 2014; Glover et al. 2022). In this case, the CO problem is described by an energy function
HQ: {0, 1 + R which is given by:
==(x)=
= E i.
(3)
where Q E R NxN is chosen according to the CO problem at hand. A table of the QUBO formula- tions of the CO problem types studied in this paper given in Tab. [ UCO the goal is to train a conditional generative model [X]6 ()) on problem instances Q that are drawn from a distribution D(Q) (see Sec. 5.1 and App. A.6) for more information on D(Q)). After training the model can be used on unseen L.I.d CO problems to obtain solutions of high quality within a short amount of time. This can be realized by using the expectation of (x) with respect to a parameterized probability distribution which is used as loss function and minimized with respect to network parameters 6:
L(()= =
(Hq
(4)
For notational convenience the conditional dependence of de on the problem instance Q is sup- pressed in the following. As minimizing the expectation value of Hx(X) in Eq. 4is prone getting stuck in local minima, numerous works (Hlbat-Allah et al. 2021; Sun et al. 2022] Sanokowski et al.
2023 2024) reframe this problem as an NPO problem and minimize TT D K (go Px
E Ex-qs (x) (X) + T log go [X) + C' instead, where C is constant which is independent of e. The optimization procedure of this objective is combined with annealing, where the objective first optimized at high temperature, which is then gradually reduced to zero. At T 0 this objective re- duces to the unconditional loss in Eq. Sanokowski et al. (2023) motivate this so-called variational annealing procedure theoretically from curriculum learning perspective and the aforementioned works show experimentally that it yields better solution qualities.
2.3 UNBIASED SAMPLING
When a parameterized probability distribution (X) is used to approximate the target distribu- tion (X) the learned distribution will typically be an imperfect approximation. Consequently, samples from go (X) will exhibit a bias. When the model used to infer properties of the system that is described by the target distribution, it is essential to correct for this bias. The following paragraphs revisit two established unbiased sampling methods namely Self-Normalized Neural Im- portance Sampling (SN-NIS) and Neural Markov Chain Monte Carlo (NMCMC) that can be used to achieve this goal. These methods serve as the basis for our diffusion-basee unbiased sampling methods which are introduced in Sec. 3.2
Self-Normalized Neural Importance Sampling: SN-NIS allows asymptotically unbiased com- putation of expectation values of target distribution. Given observable O {0, 1] + R, an exact likelihood model (X) can be used to calculate expectation values ) =
[px(x)[((X)) in the following way:
M
(O(X))) (n Σ w (X') O(x)).
where X corresponds to the i-th of M samples from (X). The importance weights are com-
[x] (for a derivation we refer to App. A.2 The probability distribution that is proportional to pn (X) [X(X) yields the minimum variance es- minimum--variance timate of (O(X)) (x) (Rubinstein & Kroese 2016). However, in our experiments, focus
puted with (X*) = Σ, W where ((X) = xx(X)
=(xi)
4

---

Published as a conference paper at ICLR 2025
distribution that approximates (x(X) since this allows the computation of expectations for various different O. An attractive feature of importance sampling is that it provides an unbiased estimator of the partition sum Z that is given by = N7 Σ ( This estimator is used in the experiment
section estimate free energies (Sec. S.2p
Neural Markov Chain Monte Carlo: NMCMC represents an alternative to SN-NIS which can be realized with the Satropolis-Hasting algorithm (Metropolis al. [953). Here, given a starting state X proposal state X' is sampled from go which is accepted with the probability
A(X' xx) min (1, p(X) (X'))
p(X))qo(X)
For more details on MCMC and Neural MCMC we refer to App. A.2.2 This process repeated simultaneously for batch of states until convergence criterion met (see App. A.3.4. After convergence the resulting samples can be considered to be approximately distributed as X ~ PB (X)
and these samples can be used estimate (O(X)) (n Since diffusion models likelihood models, i.e. infeasible compute (x( exactly, neither SN-NIS nor NMCMC
approximate
directly applicable to them. In Sec. 3.2 we propose techniques that overcome this limitation.
3 METHODS
3.1 SCALABLE DISCRETE DIFFUSION SAMPLERS
Sanokowski et al. 2024) demonstrate that increasing the number of diffusion steps in UCO improves the solution quality of the diffusion model, as it enables the model to represent more complex dis- tributions. However, as discussed Sec. [.1 the loss function in Eq. 2 used in their work inflicts memory requirements that scale linearly with the number of diffusion steps. Given a fixed memory budget, this limitation severely restricts the expressivity the diffusion model. the following sections, we introduce training methods that mitigate this shortcoming.
Forward KL Objective: One possibility to mitigate the linear scaling issue to use the forward Kullback-Leibler divergence (fKL). In contrast to the objective in Eq. 2 the gradient can be pulled into the expectation:
V However, since in NPO samples Xo.T p(XorT) are not available, we employ SN-NIS to rewrite the expectation with respect to Xo.r go (Xur)) Note that this is feasible with dif- fusion models since they do provide exact joint likelihoods. In analogy to data-based diffusion models (Ho et al.] (020)) one can now use Monte Carlo estimates of the sum over time steps log qo( (XooT))) Σ'= (X to mitigate the aforementioned memory scaling issue. The resulting gradient of the fKL. objective is given by (see A.2.6)
= -Exo:r=x(xx. Vo log (X
V VoDKL(p(Xor))
= -T Σ E.-UIL.... [w(Xor) Vo log qo (X;_ X:))
where wo ((6o))) ge (XoTT)) and U UL,,..,, Tn} is the uniform distribution over the set {I...,,?).
5(X; D Te (
are importance weights with w(Xi (o))) = ((X (x(x)r)
X
0:7
In the following, we will refer to this method as SDDS: w/ MC since it realizes Scalable Discrete Diffusion Samplers (SDDS) using an objective that is based on the fKL, where the linear memory scaling issue is addressed with Monte Carlo estimation over diffusion steps. A pseudocode of the optimization procedure is given in App. A.3.5
Reverse KL Objective: The minimization of the reverse Kullback-Leible divergence (rKL) based objective function L(A) introduced by Eq. 2 can be shown to be equivalent to parameter updates using the policy gradient theorem (Sutton & Barto 2018) (see App. A.2.5). The resulting gradient updates are expressed as:
Vol(O)= - -E Exx (X,)) N (X- X,) Volooo
(5)
where:
5

---

Published as a conference paper at ICLR 2025
t T in the first step and 1 is the terminal step,
(X X;) =
0 (Xr-1),
(X,)) = =xx,, qo (X (X,-1, where (Xoo) =0,
((-1,XX-1)) is defined as:
Tllo pl (x go X Xx)1
if <IST if
R(Xe,XX-1))
[Tlog ((oogpp(xiln x1 log yo
H(X,
Here dl (XX, t) represents the stationary state distribution of the state (X, t) and the policy qo in the setting of episodic RL environments.
This formulation suggests leveraging RL techniques to optimize Eq. where Q" is the Q-function, T the value function, and R(X, X 1 the reward. The usage of RL training methods addresses the linear memory scaling issue associated with Eq. aas sampling from the stationary state distribution d corresponds in this setting to uniformly sampling diffusion time steps L. We chose to optimize 5q.5lvia via the Proximal Policy Optimization (PPO) algorithm [chulman et al. (2017) (for details and pseudocode see App. A.3.6). In the following, we will refer to this method as SDDS: rKL. w/ RI. to emphasize that SDDSs are trained with the usage of RL methods.
3.2 UNBIASED SAMPLING WITH DISCRETE ISING MODELS
As concluded in Sec. 2.3 neither SN-NIS nor NMCMC can be applied with diffusion models. In the following, we introduce adapted versions each of these methods that allow us to perform unbiased sampling, i.e. unbiased computation of expectation values, with diffusion models.
Self-Normalized Neural Importance Sampling for Diffusion Models:
Given a diffusion model qe that is trained approximate target distribution pa (Xo), we can this model calculate unbiased expectations (O(X))) (X()) with SN-NIS in the following way (see App. A.2.
(0(Xo))
Σ (xxT
where (o(6)r)
@(X and Xar go (X(r)) with @ (Xir) no ( Using these
F(X
EN ((x)r)
importance weights the partition sum of (Xo) can be estimated with 2 EM @(H.r))
Neural MCMC for Diffusion Models: Starting from an initial diffusion path Xo:r, we propose a state by sampling XoT 9(X..T). This diffusion path is then accepted with the probability (see App: A.2.4.
A(X',X) min (1, ((x.)) go (o(o)))) ((Xor)) 4o (X()))))
This process is repeated until the Markov chain meets convergence criteria and samples Xo.7 are distributed as p(Xo.T) and Xo can be considered to distributed as pppppooo These samples can be used to approximate expectations with (O(Xo)) Xompe(XX) (see App. A.2.4
4 RELATED WORK
Neural Optimization:
Besides their predominance in supervised and unsupervised learning tasks, neural networks become an increasingly popular choice for wide range data-free optimization tasks, i.c. scenarios where an objective function can be explicitly expressed rather than implicitly via data samples. Physies Informed Neural Networks (Raissi et al., 2019) models are trained to represent the solutions of differential equations. Here the loss function measures the adherence of the solution quality. Similarly, [Bezzins et al.] (2024) propose a neural optimization approach for generating shapes under geometric constraints. Recently, there has been increasing interest in using probabilistic generative models to generate solutions to neural optimization. Here the learned models do not directly represent solution but rather probability distribution over the solution space. We refer to this endeavor as Neural Probabilistic Optimization (NPO). In the following, we discuss two important NPO application areas in discrete domains.

---

Published as a conference paper at ICLR 2025
Neural Combinatorial Optimization: Neural CO aims at generating high-quality solutions to CO problems time-efficiently during inference time. The goal is to train a generative model to generate solutions to a given CO problem instance which it is conditioned. Supervised CO (Sun & Yang. 2023 Li et al. 2018 Böther et al., 2022a) typically involves training a conditional generative model using training dataset that includes solutions obtained from classical solvers like Gurobi (Gurobi Optimization. 2023). However, as noted by Yehuda et al. (2020), these supervised approaches face challenges due to expensive data generation, leading to increased interest in unsupervised CO (UCO). In UCO the goal is to train models to solve CO problems without relying on labeled training data but only by evaluating the quality of generated solutions /Beggio et al. (2021b). These methods often utilize exact likelihood models, such as mean-field models (Karalias & Loukas| 2020] Sun
jt al. 2022 Wang Li 2023). The calculation of expectation values in UCO is particularly con- venient with mean-field models due to mathematical simplification arising from their assumption of statistical independence among modeled random variables. However, Sanokowski et al. (2023) demonstrate that the statistical independence assumption in mean-field models limits their perfor- mance on particularly challenging CO problems. They show that more expressive exact likelihood models, like autoregressive models, offer performance benefits, albeit at the cost of high memory quirements and longer sampling times, which slow down the training process. These limitations can be addressed by combining autoregressive models with RL methods to reduce memory requirements and accelerate training as it is done in Khalil et al. (2017) and Sanokowski et al. (202)). Sanokowski al. (2023) additionally introduce Subgraph Tokenization to mitigate slow sampling and training in autoregressive models. Zhang et al. (2023) utilize GFlow networks (Bengio et al. (222a)), imple- menting autoregressive solution generation UCO. [Sanokowski et al. (2024) introduce a general framework that allows for the application of diffusion models to UCO and demonstrate their superi- ority on a range of popular CO benchmarks.
Unbiased Sampling: In this work, unbiased sampling refers to the task of calculating unbiased expectation values via samples from an approximation of the target distribution. Corresponding methods rely far primarily
exact likelihood models, i.e. models that provide exact likelihoods for samples. Unbiased sampling plays a central role in a wide range of scientific fields, including molecular dynamics (Noé & Wu 2018; Dibak et al., 2022), path tracing (Müller al., 2019). and lattice gauge theory (Kanwar et al. 2020). These applications in continuous domains are suitable for using exact likelihood models like normalizing flows which are popular model class in these domains. More recently approximate likelihood models became increasingly important in these applications since their increased expressivity yields superior results (Dibak al., 2022] Zhang &
Chen 2022 Berner et al. [202aa] Jing et al. 2022] Berner et al., Richh] Richter et al. [023]] Vargas
al. 2023: 2024] Akhound -Sauunnd-Sadhhhhhhh et al., 2024). In discrete domains, unbiased sampling arises
as a key challenge in the study of spin glasses (Nicoli et al. 2020; McNaughton et al. 2020 Inack
eet al. 2022] Bialas et al.) 2022 Biazzo et al. 2024). many-body quantum physics (Sharir et a
2020 Wu et 2021), and molecular biology (Cocco et al. 2018). In these settings, autoregressive models are the predominant model class. We are not aware of works that explore the applicability and performance of approximate likelihood models like diffusion models for unbiased sampling on discrete problem domains.
EXPERIMENTS
We evaluate our methods on UCO benchmarks in Sec. 5.1 and on two benchmarks for unbiased sampling Sec. 5.2 and in A.8.2 In all of our experiments, we use time-conditioned diffusion model go( x () that realized either by a Graph Neural Network (GNN) (Scarselli et al., 2009) in UCO experiments or by a U-Net architecture (Ronneberger et al., 2015) in experiments on the Ising model (see App. A.4). In our experiments the probability distribution correspond- ing to individual reverse diffusion steps is parametrized via a product of Bernoulli dsitributions go (X,__1lXX, = II," (X,)) (1-9) (X,)), ( where qo (X,); := qo (X, X t). As a noise distribution, we use the Bernoulli noise distribution from (Sohl-Dickstein et al. 2015) (see App. A.
5.1 UNSUPERVISED COMBINATORIAN OPTIMIZATION
In UCO the goal is to train a model to represent a distribution over solutions, which conditioned on individual CO problem instances (see Sec. 2.2). Since each CO problem instance corresponds to
7

---

Published as a conference paper at ICLR 2025
graph is natural and popular choice to use GNNs for the conditioning the CO problem instance Cappart et al., 202I). Our experiments in UCO compare three objectives: the original DiffUCO objective as in Eq.2 and the two newly proposed methods SDDS: rKL w/ RL and SDDS: fKL w/ MC.
We evaluate these methods on benchmarks across four CO problem types: Maximum Independent Set (MIS). Maximum Clique (MaxCI), Minimum Dominating Set (MDS), and Maximum Cut (MC). For detailed explanations of these CO problem types see App. A Following Zhang et al. (2023)
and Sanokowski et al. (2024), we define the MIS and MaxCl problems on graphs generated by the RB-model (RB) which is known for producing particularly challenging problems (Xu et al., 2005),
The MaxCut and MDS problem instances are defined on Barabasi-Albert (BA) graphs (Barabási & Albert 1999). For each CO problem type except MaxCI, we evaluate the methods on both small and large graph datasets. The small datasets contain graphs with 200-300 nodes, while the large datasets have 800-1200 nodes. Fach dataset comprises 4000 graphs for training, 500 for evaluation and 1000 for testing. To ensure a fair comparison in terms of available computational resources, we maintain constant number of gradient update steps and comparable training time across DiffUCO, SDDS: rKL w/ RL and SDDS: fKL w/ MC (see App. (.7.... In our experiments, we first evaluate DiffUCO with fixed computational constraints. Using the same computational constraints, our proposed methods SDDS: rKL w/ RL and SDDS: JKL w/ MC with twice as many diffusion steps compared to DifUUC.. This is possible since these methods are designed to enable more diffusion steps with the same memory budget. Compared to the original DiffUCO implementation (DiffUCO (r). Sanokowski et al. (2024) )
then evaluate
we also add cosine learning rate schedule (Loshchilov & Hutter, 2017) and graph normalization layers (Cai et al., (021) since this was found to improve the obtained results App. A.7.2 Additionally, the computational constraints between our DiffUCO evaluation and DifUUO (r) are different. These two factors explain the superior performance of DiffUCO with respect to the reported values of DiffUCO (r) in Tab. [ and Tab. _ Sanokowski et al. (2024) have shown empirically that increasing the number of diffusion steps during inference improves the solution quality in UCO. In accordance with these insights, we evaluate the performance of the diffusion models with three times as many diffusion steps as during training.
We report the average test dataset solution quality over 30 samples per CO problem in- stance. We include results for all three objectives and also include for reference the results from the two best-performing methods in DiffUCO (Sanokowski et al.) 2024), and LTFT (Zhang et al. 2023). Results for the MIS and MDS problems are shown in Tab. 1 and for the MaxCl and MaxCut problems in Tab. 2 In these tables, we also show the solution quality of the classical method Gurobi, which is if computationally feasible run until the optimal solution is found. These results are intended to showcase the best possible achievable solution quality on these datasets. Since Gurobi runs on CPUs it cannot be compared straightforwardly to the other results which were obtained under specific con- straints for GPUs. To ensure the feasibility of solutions and to obtain better samples from a product distribution deterministic way the final diffusion step is decoded with the Conditional Expec- tation (CE) (Raghavan] 1988) algorithm (see App: A.3.2). We optionally apply this method in the last diffussonn step. However, we find that in our experiments the improvement by using Conditional Expectation (see App: A.3.2) is much smaller than the improvements reported in SSanokossii et al. (2024). We attribute this finding to the higher solution quality of our models. Secondly, we see that SDDS: rKL w/ RL outperforms all other methods in terms of average solution quality significantly in out of 7 cases and insignificantly in 2 out of 7 cases. Only on MaxCut BA-large DiffUCO and SDDS: fKL. w/ MC perform insignificantly better than SDDS: rKL w/ RL. In most cases, DiffUCO is the second best method and SDDS: fKL w/ MC performs worst. When increasing the number of samples from 30 to 150 sampled solutions (see Tab SDDS: fKL w/ MC and SDDS: rKL w/ RL are the rest-performing objectives in 6 of 7 cases and insignificantly the single best objective in 4 out of 7 cases. This finding to be expected due to the mass-covering behavior of the fKL. which allows the distribution go to put probability mass on solutions where the target distribution has vanishing probability. As a result, the IKL-based training yields a worse average solution quality but due to the mass-covering property, the distribution covers more diverse solutions which makes it more likely that the very best solutions are within the support of qe. In contrast to that, DiffUCO and SDDS: rKL w/ RL are mode seeking which tend to cover fewer solutions but exhibit higher average solution quality. Our experimental results in Tab. and Tab. 2 show consistent improvements over the results reported by Sanokowski al. 2024).
Results:
8

---

Published as a conference paper at ICLR 2025
MIS
RB -mall
RB large
MDS
BA-small
BA--lagge
Method
Type
Size 1
time 1
Size 1
time
Mechod
Type
Size J
time 1
Size J
time
Gurohi
OR
20.13
+ 0.03
6:29
42.51
= 0.06"
14:19:23
Gurobi
OR
27.84
0.000
1:22
104.01 + 0.27
3:35:15
LTFT (a)
UL
19.15
1:04
37.48
8:44
LIFT (e)
UL
28.61
4:16
110.26
1:01:24
DITUCO (r)
UL
18.88 1. 0.06
0:14
38 10.10- 0.13
0:20
DiTUCO o7
UL
0:10
107.
4: 0.31
0:10
DiTUCD: CI (n)
0.06
1:48
38.87
0.13
9:54
DITUCO:
28.20
1:48
106.61
0.30
6:56
DiRUCO
19.42
0.00
30.44
0:03
DiffUCO
0:01
105
0.21
0:01
SDDS; rKL w/ RL
UL
19.62 =: 0.01
0:02
39. 97 0.08
0:03
SDDS: rKL w/ RL
UL
28.03 0.00
0:02
105
16 0.21
0:02
SDDS: (KL of MC
UL 19:27
1: 0.08
0:02
36.
14
- 0.06
0:03
SDDS: JKL W/CC
UL
28.31
0.00
0:01
105.70
1 0.25
0:02
DiMICO CF
UI.
19.42
+ 0.03
0:20
39.40
- 0.00
6:38
DiRUCOO CE (KL RL-CE
LT.
28.00=00001
0:16
105,
21 + 0.21
1:45
SDDS: IKL w/ RLCCE
UL
19.62
0:20
90 0.08
6:35
SDDS:
2.002
0:16
105.15 0.20
1:11
SDDS: W/
UL
19.27 0.08
0:19
38.61 0.06
6:31
SDDS: JKL W/MC-CE
28.33 0.02
0:16
105.7 0.25
1:41
Table I: Left: Average independent set size on the test dataset of RB-small and RB-large. The
higher the better. Right: Average dominating set size on the test dataset of BA-small and BA- large. The lower the set size the better. Left and Right: Total evaluation time is shown in himrs. (r) indicates that results are reported as in SSankkowskki et al. (2024). + represents the standard error over three independent training seeds. (CH) indicates that results expectation. The best neural method is marked as bold. Gurobi results with indicate that Gurobi was run with time limit. On MIS RB-large the time-limit is set to 120 seconds per graph.
reported after applying conditional
MaxCI
RB-small
MaxCut
BA-small
BA-large
Method
Type
Size f
time
Method
Type
Size
time
Size t
time J
Gurobi
OR
19.06
0.03
11:00
Gurobi (r)
790.87
2.35"
17:00:00
2944.38
0.86
2:35:10:00
LTFT (r)
UL
16:24
1:24
LTFT (r)
UL
704
5:54
2864
42:40
DifiUCO (r)
UL
14.51
0.39
0:08
DiffUCO (c)
UL 727 11 = 2.31
0:08
2947.27 = 1.30
0:08
DiAUCO: CE (r)
UL
16.22
0.09
2:00
DiffUCO: CE (r)
UL 727. + 2.33
2:00
2947 53 # 1.48
7:34
DO
UL 17.40 i: 0.02
0:02
DifTUCO
UL 731.30 i: 0.75
0:02
2974 60 1: 7.73
0:02
SDDS: rKI. w/ RT.
UL 18.89 0.04
0:02
SDDS: rKI w/ RI.
UL 731.93
0.74
0:02
2971.62 62 1 8.15
0:02
SDDS: JKL w/ MC
UL 18.40 1: 0.02
0:02
SDDS: fKL w/ MC
UL 731.48
1: 0.69
0:02
2973.80 00773.8021 1: 7.57
0:02
DiAUCO: CE SDDS: KKL w/ RL-CE
UL. 17.40 + 0.02
0:38
DiAUCO: CE SDDS: rKL w/ RL-CE
UL. 731 30 + 0.75
0:15
2974.64-2 + 7.74
1:13
UL 18 0.04
0:38
UL 731.93 93 + 0.74
0:14
2971.62
+ 8.15
1:08
JKL MC-CE
UL 18.41 0,02
SDDS: JKL MC-CE
731.48 0.69
0:14
2973.
80 + 7.57
1:08
Testset average clique size on the RB-small dataset. The larger the set size the better. Right: Average test set cut size on the BA-small and BA-large datasets. The larger the better. Left and Right: Total evaluation time is shown in d:h:m:s. (CE) indicates that results are reported after applying conditional expectation. Gurobi results with * indicate that Gurobi was run with a time limit. On MDS BA-small the time limit is set to 60 and on MDS BA-large to 300 seconds per graph.
Table 2: Left:
5.2 UNBIASED SAMPLING OF ISING MODELS
In the discrete domain, the Ising model frequently studied in the context of unbiased sampling (Nicoli et al., 2020 McNaughton et al. 2020). The Ising model is discrete system, where the energy function H, 1-1,11 + IR is given by H, = J Et,, 0: where (i, runs over all neighboring pairs on a lattice. At temperature T the state of the system thermal equilibrium
is described by the Boltzmann distribution from Eq. [ Analogously to Nicoli et al. (2020), we explore unbiased sampling using finite-size Ising models (see Sec. 2.3) on a periodic, regular 2D grid of size L with a neiiest- coupling parameter of J I. We experimentally validate our unbiased sampling approach with diffusion models by comparing the estimated values of the free energy F = log 2, internal energy 4 = Σx (x H, (X), and entropy S = (4 - F) against the theoretical values derived by Ferdinand & Fisher (1969). We also report the effective of each method. For the best possible model, the effective sample size per sample equals one as w; 1/M V E {1,..., M). For the worst possible model Gedt /M In our experiments, we train diffusion models using 300 diffusion steps and a U-net architecture (details in App. A.44 and App. [.7.3)). Tab. presents our results where each model is evaluated over three independent sampling seeds. We compare our methods to two other methods that both rely on the rKL objective. First, the AR models by (Wu et al.) 2019) which we label as VAN (r), and second the NIS method with AR models by (Nicoli al. 2020) which we label as AR (r). We also evaluate an AR reimplementation of (Nicoli et al. 2020) using the same architecture and computational constraints the diffusion models.
1 C ar," "² sample size per sample eaft catt/M == M En'"
1/M as there is one weight which is equal to and all others are O.
Results: We find that the diffusion model outperforms the AR baseline reported in Nicoli et al. 2020). Our method SDDS: fKI. w/ MC yields the best performance, producing values closest to
9

---

Published as a conference paper at ICLR 2025
CO problem
MaxCI 1
MaxCutt 7
MIST
MDS
Graph Dataset
RB-small
BA-small
BA-large
BA-small
BA-large
BA-small
BA-largo
Gurobi Set Size
19.06 2: 0.03
730,87 =: 2.35"
2911.38 4: 0.86"
20.14 4: 0.04
42.51 1: 0.06"
27.81 2: 0.08
101.01 2: 0.27
DifUUCO: CE
18.34 + 0.07
732.64 + 0.74
2979.09
6.69
19.79 + 0.04
41.84 +: 0.07
27.97 +
104.36 0.22
SDDS rKL RLAC
19.05 0.03
732.78
+: 0.74
2979.05
6.69
20.02
0.02
42.12 0.06
27 37.89-
104:26 0.21
SDDS. JKL w/ MC-CB
19.06 19.06:100 0.04
733.06 1: 0.69
2979.88
6.65
20.05 1: 0.03
11.23 0.05
2..89:10.01
101.3 1: 0.23
Table 3: Comparison of the best solution quality out of 150 samples for each CO problem instance
averaged over the test dataset. Arrows J, f indicate whether higher or lower is better. Gurobi results with indicate that Gurobi was run with a time limit (see Tab. I and Tab.
24 24 grid
Free Energy 7/1²"
Internal Energy 21/12
Entrops 5/1²
M
Optimall value
22.112
-144
0.29611
VAN (1) Nicoll 2020
2.10715
0.0000
1.5068
0.0001
0,265005 + 0.00004
Unb, sampling Mothods
SN-NIS
SN-NIS
NMCMC
SN-NIS
AR Nicoli 2020
2.1128 0:0008
1.43 0.02
1.448
0.007
0.200 + 0.007
N/A
AR SDDS: rKL w/ RL.
2.09344 + 0.00063
1.65420 + 0.00562
1.68479
0.00198
0,19357 + 0.002
0,0006
0,00002
2.11150 + 0.00062
-1.49900 0.01412
-145525
0.00152
0. 0,29192 + 0.00615
0.00023
0.00017
SDDS:
2.11209 0.00008
-1.4410 0.0008
-1.44264
0.00187
0.29678 0.0004
0.0102 0.0024
Table 4: Comparison of estimated observables 1 8/22 and the effective sample size per
sample Eeit MM of Ising model of size 24 x 24 at critical inverse temperature 3e 0,4407 using SN-NIS and NMCMC methods.
theoretical predictions. This aligns with expectations due to fKL's mass-covering property, which should improve the model's coverage of the target distribution which is beneficial in unbiased sam- pling. The diffusion model trained with SDDS: rKL w/ RL performs better than our AR reimple- mentation but worse than both the SDDS: fKL w/ MC model and the reported AR baseline (AR (r))- We do not report the performance of DiffUCO as this method suffered from severe mode-seeking behavior in this setting, where it only predicted either +1 or -1 for every state variable, result- ing in poor behavior for unbiased sampling- Our experiments demonstrate that discrete diffusion models offer promising alternative to AR models for unbiased sampling. Key advantages of dif- fusion models include ficxibility in the number of diffusion steps and forward passes, which can hyperparameter. In contrast, the number of forward passes in AR models is fixed
be adjusted to the dimension of the Ising model state. Our diffusion models achieve better performance while significantly fewer than the 576 forward passes required
using only 300 diffusion steps, which by the AR baseline. Since (Nicoli et al., (2020) ran their experiments on different types of GPUs it is in principle not possible to deduce from these results that AR models are inferior diffusion models. Therefore, we complement our experimental evaluation with our own implementation of an AR approach. We utilize the same U-net architecture as for our diffusion models and the same computational resources. The corresponding results (AR in Tab. 4 indicate that also under these conditions the diffusion model approaches excel.
6 LIMITATIONS AND CONCLUSION
This work introduces Scalable Discrete Diffussion Samplers (SDDS) based on novel training methods that enable the implementation of discrete diffusion models with an increased number of diffusion steps in Unsupervised Combinatorial Optimization (UCO) and unbiased sampling problems. We demonstrate that the reverse KL objective of discrete diffusion samplers can be optimized efficiently using Reinforcement Learning (RL) methods. Additionally, we introduce an alternative training method based on Self-Normalized Importance Sampling of the gradients of the forward KL diver- gence. Both methods facilitate mini mini-batching across diffusion steps, allowing for more diffusion steps with given memory budget. Our methods achieve state-of-the-art on popular challenging UCO benchmarks. For unbiased sampling in discrete domains, we extend existing importance sam- pling and Markov Chain Monte Carlo methods to be applicable to diffusion models. Furthermore, we show that discrete diffusion models can outperform popular autoregressive approaches in es- timating observables of discrete distributions. Future research directions include leveraging recent advances in discrete score matching (Lou et al. (0244) to potentially improve the performance of SN- NIS-based objectives in UCO. While the reverse KL-based objective introduces new optimization hyperparameters, our experiments suggest that these require minimal fine-tuning (see App. App. A.. Overall, SDDS represents a principled and efficient framework for leveraging diffusion models in discrete optimization and sampling tasks.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The ELLIS Unit Linz, the LIT AI Lab, the Institute for Machine Learning, are supported by the Federal State Upper Austria. We thank the projects INCONTROL-RL, (FFG-88 1064), PRI- MAL (FFG-873979). S3AI (FFG-872172), DL for GranularFlow (FFG-871302), EPILEPSIA FFGG,22171,, FWF AIRI FG 9-N (10.55776/FG9), AlAGrrenHeetingGnid (FFG-899943), INTE- GRATE PTFG-892418) ELISE (H22000-ICT-2019-3 ID: 951847), Stars4Waters (HORIZON-CL.6 2021- CLIMATE-01-01), We thank NXAI GmbH, AudiJJKL Deep Learning Center, TGW L.- GISTICS GROUP GMBH, Silicon Austria Labs (SAL), FILL Gesellschaft mbH, Anyline GmbH, Google, ZF Friedrichshafen AG, Robert Bosch GmbH, UCB Biopharma SRL, Merck Healthcare KGaA, Verbund AG, GLS (Univ. Waterloo), Software Competence Center Hagenberg GmbH, Bo- realis AG, TÚV Austria, Frauscher Sensonic, TRUMPF and the NVIDIA Corporation. We ac- knowledge EuroHPC Joint Undertaking for awarding us access to Meluxina, Vega, and Karolina at IT4Innovations.

---

Published as a conference paper at ICLR 2025
REFERENCES
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum independent sets. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13- 18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 134- 144. PMLR, 2020. URL httptttp//proreecnns...... mwr.agssmmr....m
www.9/hhnnCaaa..m html
Tara Akhound- -Sadegh, Jarrid Rector-Brooks Avishek Joey Bose, Sarthak Mittal, Pablo Lemos, Cheng-Hao Liu, Marcin Sendera, Siamak Ravanbakhsh, Gauthier Gidel, Yoshua Bengio, et al. Iterated denoising energy matching for sampling from boltzmann densities. arXiv preprint arXiv:2402.06121, 2024.
Shun-ichi Amari. Differential-geomeeine methods statistics, volume 28. Springer Science & Business Media, 2012.
Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. abs/1607.064500 2016. /ttp:://////x hts///b///// /anes/16607 06450
CoRR,
Albert-Láázıó Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286 (5439):509-512, 1999. doi: 10. 2..1126/sciencee28855549999
URL RtLhttt::// wwww/ science.
286 5439.50 509
Yoshua Bengio, Tristan Deleu, Edward J. Hu, Salem Lahlou, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. CoRR, 0bss2211.09266,, 2021a. URL https: org/ abs/
09266
Yoshua Bengio. Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d'horizon. European Journal of Operational Research, 290(2): 405 2021b.
Julius Berner, Lorenz Richter, and Karen Ullrich. An optimal control perspective on diffusion-based generative modeling. arXiv preprint (.0i::22//1013660 2022a.
Julius Berner, Lorenz Richter, and Karen Ullrich. An optimal control perspective on diffusion-based generative modeling. arXiv preprint arXiv:2211.01364 2022b.
Arturs Berzins, Andreas Radler, Sebastian Sanokowski, Sepp Hochreiter, and Johannes Brandstetter. -eometry-informed neural networks. arXiv preprint 24t.::2202./40090 2024.
Piotr Bialas, Piotr Korcyl, and Tomasz Stebel. Hierarchical autoregressive neural networks for statistical systems. Computer Physics Communicationss 281:108502, 2022.
Indaco Biazzo, Dian Wu, and Giuseppe Carleo. Sparse autoregressive neural networks for classical spin systems. Machine Learning: Science and Technology, 2024.
Griff L. Bilbro, Reinhold Mann, Thomas K. Miller III, Wesley E. Snyder, David E. van den Bout, and Mark W. White. Optimization by mean field annealing. In Advances in Neural Information Processing Systems 1. [NIPS Conference, Denver, Colorado, USA, 1988], pp. 91-98. Morgan Kaufmann, 1988. URL httt:://papese 127- imi zat tottiionn ion-by-mean
lnn
Maximilian Böther, Otto KiBig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. In The Tenth Inter- national Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022a. StRl:ttps:/// /ttp:/:://///eeeeeeeeeeee wew.:e/oomiidmmnneee.e..e...eeee
Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's 's wrong with deep learning in tree search for combinatorial optimization. In The Tenth Inter- national Conference Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022b.
wttp::/wwwwweeeeuuueeeeeaam net Eorum 2id www.:iiidmmdmddmmm1..
James Bradbury. Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- Milne, and Qiao Zhang. JAX: composable transformations Python+NumPy programs, 2018. URL http:
7 thub. com ///a///oogllaaaaooo/
12

---

Published as a conference paper at ICLR 2025
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang. Graphnorm: A prin- cipled approach to accelerating graph neural network training. In International Conference on Machine Learning, pp. 1204-1215. PMLR, 2021.
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Velickovic. Combinatorial optimization and reasoning with graph neural networks. In Pro- ceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pp. 4348 4355. ijcai.org, 2021. doi: 20296///5cai2222/55222 URLpttps:: /ttp://s/....ooooo0/./////////// 200.2222296//1..22222///222 2021/595
Simone Ciarella, Jeanne Trinquier, Martin Weigt, and Francesco Zamponi. Machine-learning- assisted monte carlo fails at sampling computationally hard problems. Machine Learning: Science and Technology, 4(1):01050,, 2023.
Simona Cocco, Christoph Feinauer, Matteo Figliuzzi, Rémi Monasson, and Martin Weigt. Inverse statistical physics of protein sequences: key issues review. Reports Progress in Physies, 81 (3):032601, 2018.
Luca Maria Del Bono, Federico Ricci-Tersenghi, and Francesco Zamponi. Nearest-neighhour neural network architecture for efficient sampling of statistical physics models. arXiv preprint arXiv:2407.19483, 2024.
Manuel Dibak, Leon Klein, Andreas Krämer, and Frank Noé. Temperature steerable flows and boltzmann generators. Physical Review Research, 4(4):L042005, 2022.
Arthur E Ferdinand and Michael E. Fisher. Bounded and inhomogeneous ising models. specific- heat anomaly of finite lattice. Physical Review, 185(2):332, 1969.
Fred W. Glover, Gary A. Kochenberger, Rick Hennig, and Yu Du. Quantum bridge analyt- ies I: tutorial on formulating and using QUBO models. Ann. Oper. Res., 314(1):141- URL
183, 2022. doi: 10.1007/510449-022-66666 s10479- 022 04634-2
Joseph Gomes, Keri A McKiernan, Peter Eastman, and Vijay S Pande. Classical quantum optimiza- tion with neural network quantum states. arXiv preprint 1xXiv:1910.10611 2019,
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https: //tp:://wwww gurobi... com
Aric Hagberg and Drew Conway, Networkx: Network analysis with python. URL: https://networkk. github. io, 2020.
Mohamed Allah, Estelle M. Inack, Roeland Wiersema, Roger G. Melko, and Juan Car- rasquilla. Variational neural annealing, Nat. Mach. Intell,, 3(11):952 961, 2021. doi: 10.1038/ 122256-021-00401-3, URL htt.s: http:::/ddo..rgg// 10. 000..0000000222---0-0--4553
Jonathan Ho, Ajay Jain, and Picter Abbeel. Denoising diffusion probabilistic mod- els. In Advances in Neural Information Processing Systems 33: Annual Conference
Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020,
cc//paper/222/haahh/ virtual, 2020. URL ab1 79c444-99999-b-- - Abstract. html
Estelle M Inack, Stewart Morawetz, and Roger G Melko. Neural annealing and visualization of autoregressive neural networks in the newman-moore model. Condensed Matter, 7(2):88, 2022.
Bowen Jing, Gabriele Corso, Jeffrey Chang, Regina Barzilay, and Tommi Jaakkola. Torsional dif- fusion for molecular conformer generation. Advances in Neural Information Processing Systems, 35:24240-24253, 2022.
Gurtej Kanwar, Michael S Albergo, Denis Boyda, Kyle Cranmer, Daniel C Hackett, Sébastien Racaniere, Danilo Jimenez Rezende, and Phiala Shanahan. Equivariant flow-based sampling for lattice gauge theory. Physical Review Letters, 125(12):121011, 2020.
13

---

Published as a conference paper at ICLR 2025
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: unsupervised learning framework for combinatorial optimization on graphs. In Advances in Neural Information Processing Systems 33: Anmual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL /
httptpp::/ppooceeeiiii ngs nwwripu.......
www.inggg.eee...ooommmmmmm cc/ /eauripp.cc//pppe///0//// pappp//ppr/////////
htmll
Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial
optimization algorithms over graphs. Advances in Neural Information Processing Systems 30; Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6348 -358-6358, 2017. URL pttpp:///pccccc.ggg....... neuripss...nri.p...mmm.m.......s ca/
paper 2oper/2017/0 2017 htw.///ah//a// http///80000000000000000606664.0 - Abbt .html
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances Neural In- formation Processing Systems 31: Annuul Conference on Neural Information Pro- cessing Systems 2018, NeurIPS 2018, December 3-8, 2018. Montréal, Canada, pp- 537-546, 2018. URL https: https::/proceeeiiiiii
Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R Gormley, and Jason Eisner. Limitations of au- toregressive models and their alternatives. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolo- gies, pp. 5147-5173, 2021.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenRe- view.net, 2020. URL (tRLhttps::// htattps://openrevieee
net iot
Iya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In In- ternational Conference on Learning Representations, 2017. URL httttst///peeeeeiieee
net/Eorum?ide Skqg399
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. stat, 1050:21, 2024.
Andrew Lucas. Ising formulations of many np problems. Frontiers in Physics, 2, 2014. ISSN
2296-424X. doi: 2..339//phhy.2014.0000
URL
articles/10.3388 www.89/fphy.... wt1.:/hyyy.22.....0
Roman Martoñák, Giuseppe E Santoro, and Erio Tosatti. Quantum annealing by the path-integral monte carlo method: The two-dimensional random ising model. Physical Review B, 66(9): 094203, 2002.
B. McNaughton, M. V. Milošević, A. Perali, and S. Pilati. Boosting monte carlo simulations of spin glasses using autoregressive neural networks. Phys. Rev. E, 101:053312, May 2020. doi: 10. Re.1100yyss 101.053311 URL https::tp///.. /opos://ling aps httpp///n........oo///////// PhysRevE. 101. 053312.
Nicholas Metropolis, Arianna Rosenbluth, Marshall N Rosenbluth, Augusta Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6):1087-1092, 1953.
Tom Minka et Divergence measures and message passing. Technical report, Technical report, Microsoft Research, 2005.
Thomas Müller, Brian McWilliams, Fabrice Rousselle, Markus Gross, and Jan Novák. Neural im- portance sampling. ACM Trans. Graph., 38(5): 14:111145: 2019. doi: 10. (0.1145/3341156 URL
Kim A. Nicoli, Shinichi Nakajima, Nils Strodthoff, Wojciech Samek, Klaus- RobsrR Müller, and Pan Kessel. Asymptotically unbiased estimation of physical observables with neural samplers. Phys. Rev. E. 101:023304, Feb 2020. doi: 10.1103/PhysRevE..r 101.023304. URL :tttpps://ikk.... 023304
aps. aps.org//6i/110 http:///oo.o11111//////a//o///
14

---

Published as a conference paper at ICLR 2025
Frank Noć and Hao Wu. Boltzmann generators sampling equilibrium states of many- systems with deep learning. CoRR, abs/1812.01129,, 2018. URL http::/aaxx...oo///bb.....
01729
Art Owen. Monte carlo theory, methods and examples. 2013.
Prabhakar Raghavan. Probabilistic construction of deterministic algorithms: approximating packing
integer programs. Journal of Computer and System Sciences,
1988.
Maziar Raissi, Paris Perdikaris, and George Karniadakis. Physics-informedt neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational physics, 378:686-707, 2019.
Lorenz Richter, Julius Berner, and Guan- Huan--Hongg& Liu. Improved sampling via learned diffusions. arXiv preprint arXhv:2307.01198 2023.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomed-
ical image segmentation. CoRR, abs/1505.04597, 2015. URL
1505. 04597
Reuven Rubinstein and Dirk Kroese. Simulation and the Monte Carlo method. John Wiley & Sons, 2016.
Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Vari- ational annealing on graphs for combinatorial optimization. In Advances in Neu- ral Information Processing Systems 36: Annual Conference on Neural Information Pro- cessing Systems 2023, NeurIPS 2023, New Orleans, LA, USA. December 10 16, 2023, 2023. URL http::/ http://apprrrr.s.cc..pesee wwtppppppp.cppppeeeppppppp.ppe.. fil 22tps//eeeeeeeee222333////////
html
Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner A diffusion model framework for unsupervised neural combinatorial optimization. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 43346-43367. PMLR, 21-27 Jul 2024. URL https::////.... htttps://proceedingg: mll. p v235 7735/sanckowskk24aa html
Franco Scarselli, Marco Gori, Ah Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks / publication of the IEEE Neural Networks Council, 20:61-80, 01 2009, doi: 20009//TNN.00000005550000
Lisa Schneckenreiter, Richard Freinschlag, Florian Sestak. Johannes Brandstetter, Günter Klam- bauer, and Andreas Mayr. Gnn-vpa: variance-preservingg aggregation strategy for graph neural networks. arXiv preprint arXiv:2403.04747, 2024.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.06344 2017. URL http::/arxivg org/ abs
7777. 06347
Or Sharir, Yoav Levine, Noam Wies, Giuseppe Carleo, and Amnon Shashua. Deep autoregressive models for the efficient variational simulation of many-body quantum systems. Physical review letters, 124(2):020503, 2020.
Andy Shih and Stefano Ermon. Probabilistic circuits for variational inference in discrete graphical models. Advances in neural information processing systems, 33:4635-466 2020.
Semyon Sinchenko and Dmitry Bazhanov. The deep learning and statistical physics applications to the problems of combinatorial optimization. arXiv preprint arXiv: 2019.
Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsu- pervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd Inter- national Conference Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, vol- ume 37 of JMLR Workshop and Conference Proceedings, pp. 2256 2265. JMLR.org, 2015. URL http:/ Tktt:://rrocest ngs ml www.lr.ppsssssi wttps/s.....rre/.///////oo.. wic.:////eeiiiiiiitttieeeeeeee html
15

---

Published as a conference paper at ICLR 2025
Alan D. Sokal. Monte carlo methods in statistical mechanics: Foundations and new algorithms note to the reader. 1996. URL //api.//ppp.... http:////w....aoooooooooaooo/r//
14817657
Haoran Sun, Etash Kumar Guha, and Hanjun Dai. Annealed training for combinatorial optimization graphs. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022. URL /tttps:///penrevviiei
net htt///ormmm//// fo jTkU
Zhiqing Sun and Yiming Yang. DIFUSCO: graph-based diffusion solvers for combinatorial op- timization. CORR, abs/2302.08224, 2023. doi: 10.48550/ARXIV223020022222 URL https:
7/doi. orgiioorg/10 48550/ 2302. 2302.08224
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL htttp://inccoppeettt deas
html
Francisco Vargas, Will Grathwohl, and Arnaud Doucet. Denoising diffusion samplers. arXiv preprint UrX1v:23302.3333,, 2023.
Francisco Vargas, Shreyas Padhy, Denis Blessing, and N Nüsken. Transport meets variational in- ference: Controlled monte carlo diffusions. In The Twelfth International Conference on Learning Representations, 2024.
Haoyu Peter Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta learning. In The Eleventh International Conference Learning Representations, 2023. URL
https: // http:s::/ppeeeevieeeee wwt.v/ewwweee/orrreeeeeeeeee forum ?id=
net.
E
Dian Wu, Lei Wang, and Pan Zhang, Solving statistical mechanics using variational autoregressive networks. Phys. Rev. Lett., 122:080602, Feb 2019. doi: 10. 10/1100 122.080602. URL 122. 080602
https: aps org wttp:////c........///////.eeeee.
Dian Wu, Riccardo Rossi, and Giuseppe Carleo. Unbiased monte carlo cluster updates with autore- gressive neural networks. Physical Review Research, 3(4):L042024, 2021.
Ke Xu, Frédéric Boussemart, Fred Hemery, and Christophe Lecoutre. A simple model to generate hard satisfiable instances. In IJCAI-05, Proceedings of the Nineteenth International Joint Confer- ence on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 August 5, 2005, pp. 337-342. Professional Book Center, 2005. URL
1989.pdF
Gal Yehuda, Moshe Gabel, and Assaf Schuster. It's not what machines can learn, it's what we can- not teach. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Re- search, pp. 10831-1083 PMLR, 2020. URL URLhtt:: htEtp::/proceedinnge mlr malr.ppn ml..ppess/vvi9/ yehuda20ea html
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C. Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. In Ad- vances in Neural Information Processing Systems 36: Annual Conference Neural Infor- mation Processing Systems 2023, NewrIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL http:: nips httpappppesspppspppaapeeeeeeeeee http://aaaeeae///22///aaaaaee
html
Qinsheng Zhang and Yongxin Chen. Path integral sampler: stochastic control approach for sam- pling. In The Tenth International Conference on Learning Representations. ICLR 2022, Vir- Tual Event, April 25-29, 2022. OpenReview.net, 2022. URL jtttp:://cpeneeviee..n wat.ummidd_uuuhhyuuuuuuu
Corum?ide wCb2
Tianchen Zhao, Giuseppe Carleo, James Stokes, and Shravan Veerapaneni. Natural evolution strate- gies and variational monte carlo. Machine Learning: Science and Technology, 2(2):02LT01, 2020.
16

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 DERIVATIONS
A.1.1 IMPORTANCE SAMPLING AND NEURAL IMPORTANCE SAMPLING
Importance Sampling (IS) is a well-cstablished Monte Carlo method used estimate expectations of observables ( under a target distribution p(X) when direct sampling from p is challenging. The core idea is to samples where pl X) or ideally p(X) [O(X)] is large. IS can be used to calculate the expectation of
proposal distribution q(X) which is easy to sample from and proposes
an observable ((X) in the following way:
- - -xxx)x)) Ex(x) 0(x) -xx=e(X)
P(X) ((X)
((X) ((X) O(x)
(6)
However, this approach makes it necessary to design suitable proposal distribution (X),, which not possible in many cases. Therefore, Neural Importance Sampling can used instead, where a distribution qo ()) is parameterized using Neural Network and trained to approximate the target distribution. By replacing (XX) in Eq. 6 with (X) the Neural Importance Sampling estimator is then given by:
p(x) (x) o(x)
( = Ex (x)
A.2 SELF-NORMALIZED NEURAL IMPORTANCE SAMPLING
In some cases, when an unnormalized target distribution is given, i.c. infeasible calculate the normalization constant 2, IS or NIS cannot straightforwardly be applied, as this requires the computation of p(X) and therefore Z. To mitigate this issue, Normalezdl Importance Sampling (SNIS) can be employed Rubinstein & Kroese (2016). The estimator is given by:
E Ex(x) = Σ ((X)((X)
w(X))O(X))
((X.)) where w(X)) = Σ, ((()) with ((x))
p(X.) x(x) are the importance weights, and X; g(X).
Derivation: When p(X) is unnormalized, i.e., p(X) = p(X)/2, where p(X) is the unnormalized distribution and Z is the unknown normalization constant, the weights w(X,) 2g(X,] depend on
p(X;)
Z, which cannot be computed. To circumvent this, Self-Normalized Importance Sampling redefines the weights as normalized importance weights:
p(X)) ((x))*
T (X))
(X.)))
w(X))
マ== ((₂))
1 (Xx))
Using these normalized weights, the expectation can be estimated as:
Bp(x) = Σ (X))x(X)((x = Ex (x))0(( Ex (X))(X)
(xx)0(X)
EN @ (X,))((X) Σ ((X))
N
Σ (X,))
Ex~g(x) [w(X]]
This approach avoids the need to compute Z explicitly, the normalization is handled by the sum of the unnormalized weights w (X)). practice, this is particularly useful for unnormalized target distributions when Z is computationally expensive estimate.
17

---

Published as a conference paper at ICLR 2025
When using Neural Importance Sampling, the proposal distribution q(X) is replaced with param- eterized distribution (X),, and the SNIS estimator becomes:
N B(X)) O(X,) 1= [x
E [p(x)
FIX,1
2/=1 (o(X;)
A.2.1 NEURAL IMPORTANCE SAMPLING WITH DIFFUSION MODELS
In the following. it will be shown that the expectation an observable O {0, 13 R can be computed with:
(O(Xo)) ((
o(.. and Xioo ~ 40 (Xo.) with ((( where w/( (o(X)o))) Σ, ((..)))))
(X..0.)
To show that we start with
(O(Xo)) = P Σ ((Xo:T)O(Xo)
(8)
Xo
Xo.r
where we introduce new variables X1. which are distributed according to the distri- then used that p(Xor) Ex,r (X (o) pn((o) = (Xo). Finally, we estimate the right hand side of Eq. 8 with
bution pl p(Xi.T(Xo)
Pn(Xo) and that
go(Ne.) to arrive at Neural Importance Sampling by inserting w((or))
((Xor) o(Xo)
(O(o)))pa(Xo) E Exxr
go (Xorr)
As pp((x) is only known up its normalization constant Z employ SN-NIS (see Sec.
2.3
A.2.2 MCMC
The Metropolis- Hastings algorithm (Metropolis et al. 1953) is standard method to obtain unbiased samples from a target distribution p(X). Starting from an initial state X, a proposal state X' accepted with the acceptance probability of
A(X' X) = min (1.
where wxX is the transition probability from X' to X and is often chosen so that it is symmetric and satisfies w (X]X') (X Here, A(X', XX) is chosen in way so that the detailed balance condition A(X, X') (XXX'') = A(X', (X'
is satisfied.
A.2.3 NEURAL MCMC
This acceptance probability can be adapted to Neural MCMC by replacing o(XX'' with a proba- bility distribution that is parameterized by neural network (x(),, which approximates the target distribution (Nicoli et al. 2020). The acceptance probability is then given by:
A(X' miin (1, go (X) (X)) P(X')
qo (X') p(X)
However, for diffusion models (x) is intractable and the formulation above therefore not be applied to diffusion models. We will derive Neural MCMC for diffusion models in the following section.
18

---

Published as a conference paper at ICLR 2025
A.2.4 NEURAL MCMC WITH DIFFUSION MODELS
We adapt NMCMC to diffusion models to obtain trajectories that are approximately distributed according to the target distribution p( p(Xo.) and show that these samples can be used to compute
Xorppa (Xe)'
This process is usually repeated until convergence criterion is met. The resulting final state approximately distributed according to the target distribution p. In NMCMC w(X]X") is set to the approximating distribution (x()), so that the acceptance probability given by
, min (1, qe (XooT) ((((:r))
go (X):)) ((Xor))
where is substituted with Xo:r and with X6.r- Thus it becomes apparent that these updates
can be used to obtain unbiased diffusion paths Xo.T p(Xo:r) of which Xo pm (Xo).
The resulting diffusion paths Xo.r are then distributed as p( ((oTr) and samples Xo can then be used to calculate expectations (O(Xo)) (Xx))(X))
Proof. The statement follows from
(O(o)) p(Xor)) ((Xor))
Σ ((Xo:T)O(Xo)
Xn:r
Σ PPB(X))((X)) (O(X)))
Xn
where we have used that O(Xo) does not depend on X which is why Ex I(Xi.))= =1
A.2.5 POLICY GRADIENT THEOREM FOR DATA PROCESSING INEQUALITY
To prove that the Data Processing Inequality (see Sec. 3.1 can be optimized with the usage of RL we first define
vO = Σ (x(x-11X))) ("
(9)
Xe-1
where
t = T in the first step
is the terminal step
(X) R(Xe, X + (9 v*(X)) = Ex,,, (x 12 (X,,,, (X
where vo =0
R(X,,X,-11) is defined as:
[[log (x,1) log go (X/-11XX,) X, [Tlog p( X1,1) - log qo (X-- (Xx-1))
if F
ift=
Then with the recursive application of Eq. 9on (V can be shown that
-Ex (V =T
Σ
Ex
[log go (X,,1
T
Ex, I 12)
(10)
+ EE Ex, ro [1(())]
T D (go (Xo.)) (((X:))) Ō
Where -T = -T [log
(X))
T log Z
19

---

Published as a conference paper at ICLR 2025
Proof. In the following, will prove the first equality of Eq. 10 by induction. First show that this equality holds for T 1:
-Exi x1) (X])] -xxi
Σ (X(XXo/X)) X1)]
Xo
--Exio(Xi) (x Xo) + (X.)]
Xo
-Ex
9o (X ) [7 log pl X1 Xo) log g0 (XooX (Xx)l
Xo
= T- Exx (oo.amo(Nool) [log go (x)] T Ex (x (Xx)
+ EX (Xor) [Xo)]
Where it apparent that this expression is equal to the right-hand side of Eq. Next, we have to show that assuming it holds for I' it also holds for T + 1.
10 when 1.
-Exmer-a(x++)) (XT+1)]
(XT==1)) -Exp1rn((X7=))
E (11 V
-Exr4
Xr
llo (Xr XT+))] (xT +V (x
T+1
E Exriaa 10 lo (Xc-1(Xx)))
T41
E Ex Ex 1m pl (xx
Ex [(())]
Therefore we have proven the statement by induction.
As we have shown that the objective T D (go (Xxxr)) can be minimized by minimiz- ing Exyeg(X ( (Xr).. Applying the Policy Gradient Theorem for episodic Markov Decision Processes (MDP) (Sutton & Barto 2018); Sec. 13.2), it can be shown that
VgL(0)= = - V Xx
-Ex,,aa' (X (x. Ix
log go (x
where de (X,() is the stationary distribution for d under the episodic MDP. We use the PPO algo- rithm to minimize this objective explained in A.3.6
Usually, the reward is not allowed to depend on network parameters 9, but the entropy regularization in the form of T log qe (X) is exception due to the property that VelEx~g(Xx [log ge (X) (x) V log go (X) Σx
x go [X) Vogo Vo Σx qo (X) V 0.
A.2.6 NEURAL IMPORTANCE SAMPLING GRADIENT OF FORWARD KL DIVERGENCE
In the following, we will show that the gradient of the IKL between the forward and reverse diffusion path can be approximated with:
voD (xlLx(((oo)))) (oox)) = -T' Σ
E E.JU [w(Xtx) Vo log go (Xx,
20

---

Published as a conference paper at ICLR 2025
where w ((X))))
((xg Mn ((X).r)
and Xbr ~ (Xorr) with T0 (Xorr)) do (x.z)
P(X
This follows from
VoDxi(P(Xone (Xorr) = -IEx==EExxeeeeee Exr Vo log go (Xo.T)]
p(Xo.r) Ve log qo (Xo.r) (o(T))
- go
((Xor))
-
V log go (x
yo (X(T))))
= = E-TEER E.LUA
[w(X V log qo (X;-
where we have used in the first equality that log Xo.r) does not depend network parameters. In the second equality we have insert 96 (Xar) and rewrite the expectation over go (Xor)) In qs (X
the third equality we use that log (Xo.T) >t log ( We can then make a Monte Carlo estimate of this sum with log go (Xo.T) = T (u.U(U log (xxx))(XX)) In the fourth equality we apply SN-NIS so that the partition sum in p( (o:r) cancels out.
A.3
ALGORITHMS
A.3.1
NOISE DISTRIBUTION
The Bernoulli Noise Distribution is given by:
P(X (1 (z) -1))- Xe-1 Nx 1. for X,,; = 0
(1 Xe B. 1 for Xt,i
where Be the noise parameter. Sanokowski al.
(224)) use a noise schedule of 3e T-142- However, we instead use an exponential noise schedule which is given by 6; = exp (- (1 4)) with & 61og(2). Our experiments are always conducted with this schedule.
A.3.2 CONDITIONAL EXPECTATION
Conditional Expectation (CE) is an iterative method for sampling from product p(X) = 1 ((X,)
distribution to obtain solutions of above-average quality Raghavan (1988); Karalias & Loukas
(2020). We define a vector v of Bernoulii probabilities, where each component 2/2 = p(X)). The CE process involves these steps:
1. Sort the components of descending order obtain sorted probability vector p
2. Starting with 0, create two vectors:
why Set the i-th component to 0
Set the i-th component to
Initially, wi (0, Pl. ................................ .N) and W1 (1, (I.
3. Compute H (wo) and (w1).
4. Update e to the configuration wj, where j = arg (in H(w)).
5. Increment to i + 1.
6. Repeat steps 2-5 until all v; either 0 or 1.
This process progressively yields better-than-average values for each component of With the choice of energy functions taken in App A.5 CE always removes constraint violations from gener- ated solutions. In experiments, speed up the CE inference time by large factor by providing a fast GPU implementation that leverages jax. lax.scn (see time column results denoted with -CE in Tab. and Tab. IT.
21

---

Published as a conference paper at ICLR 2025
A.3.3 ASYMPTOTICALLY UNBIASED SAMPLING
Autoregressive Asymptotically Unbiased Sampling:
While SN-NIS and NMCMC can be used to remove some of the bias, the bias cannot be com- pletely removed when the model suffers from lack of coverage, i.c. 3X such that (x(X) = and (B(X) O(x) * (Owen 2013). way to mitigate this issue is to adapt the model so that (x) > 0 A X. In autoregressive models (x(X) = II (xx Nicoli et al. (2020) enforce this property by adapting the parameterized autoregressive Bernoulli probability go <x) = (x(x<)) (x=))x. (1 To (x(xx))) wee.see..eeeeeeeeeeeeeeeeeeeeeee
by setting To (x(x) = clip(go (x<)); e, e)- This adapted probability then used in NMCMC and NS-NIS ensure asymptotically unbiased sampling. In Sec. 3.2. we will propose a way how to realize asymptotically unbiased sampling with
diffusion models which experimentally validated in Sec. 5.2
Asymptotically Unbiased Sampling with Diffusion Models: We propose to address asymptoti- cally unbiased sampling with diffusion models by introducing a sampling bias с at each diffusion step 1. This sampling bias is then used to smooth out the output probability of the conditional diffusion step @o (Xx=
II: qo (,( where (0 (X,) (Xe)s X1-1. (X (1 To (xXX)))))Xxxx111 and (X,,; asymptotically unbiased sampling is ensured.
(Xi)), 6x). By choosing a sampling bias e,
In practice, we have not found any for autoregressive models or diffusion models, which has improved the model in the setting of unbiased estimation.
A.3.4 MARKOV CHAIN CONVERGENCE CRITERION
To assess the convergence of MCMC chains, we use the integrated autocorrelation time, TO, which quantifies the correlation between samples of chain Sokal (1996). It is defined as:
TO
PO(T),
where (T( is the normalized autocorrelation function of the stochastic process generating the chain for quantity For finite chain of length N, the normalized autocorrelation function (o(T) approximated as:
(o(T) (0)
Po(T)=
where
1 Le-t
Lc Lc
O co(T) Le Σ (01-10)(0t=-11)) no
1=1
and Le is the length of the Markov chain. Rather than summing the autocorrelation estimator (o(T) up Lc. which introduces noise as Le finite, we truncate the sum K < Le balance variance and bias. The integrated autocorrelation time fo is then estimated as:
(o( 1 Σ Po(T),
where K is chosen K CTO for constant C 5, following the recommendations of Sokal 1996).
A.3.5 FKL W/ MC ALGORITHM
The following pseudocode shows how we minimize the fKL w/ MC objective for an unconditional generative diffusion model.
22

---

Published as a conference paper at ICLR 2025
Algorithm Diffusion Model Training based on JKL w/ MC
initialize learning rate 7, number of diffusion trajectories N,
2: diffusion trajectory mini-batch size n, and mini-batch diffusion time step size т
3: DB =
4: for each epoch in epochs do
5: Sample X ~ (Xorr)
6: Store (XT ge (Xo:r) {O,.... TO...N O:N) in data buffer DB
7: while data buffer not empty do
8:
sample {-] = (..,,)))))) obtain corresponding (XD:T 9aaaa (Xo.r)
DB w/o replacement
9:
10:
compute importance weights w ((oT))
@(Xūr)
with 0 (x,T) = ((X 4oaia (:
Σ, ((x).))
compute loss L(0) - -T Ei Eee(r) 12: Update + 0 - VVLL(0)
11:
[w(X V log 2o (Xi-
end while
14:
end for
In UCO we additionally condition the generative model on the CO problem instance and the exten- sion of this algorithm to a conditional generative diffusion model is trivial.
A.3.6 PPO ALGORITHM
The following pseudocode shows how we minimize the rKL w/ RL objective for an unconditional generative diffusion model. In the following, 0:N denote indices of different samples so that, for example, X (X) x
In PPO, an additional set of hyperparameters introduced: a, X, C1, and K. Here, the mov- ing average parameter, which is used to compute the rolling average and standard deviation of the reward. À is the trace-decay parameter used to compute eligibility traces in the temporal differ- ence learning algorithm, TD(A). e₁ is the relative weighting between the loss of the value func- tion Lv and the loss of the policy (0), so that the overall loss Lppo(O) computed with LPPo(O) (1 L, (0) (v).
The value function loss (0) is defined as the squared error between the predicted value of the state and the TD(A)-estimated return:
1 (v =, [(Vo(X,) G
where (X,) the predicted value of state X,, and G is the TD(A)-estimated return, which combines the immediate rewards and bootstrapped value estimates of future states.
The TD(A) return G is computed as:
G = -1- x1--)>x>
(n) (()
where ((+) the n-step return defined as:
((1)) = rt + 7T++1 + + r 1 + Vo(Xe+n),
with y being the discount factor which we always set to 1.0.
Finally, K. is the value that is used for clipping in the policy loss function, which is given by:
I (0) E, min(r:(0)))))))) (0) A., clip(r.()))))))) K. x)
where A, is the normalized estimator of the advantage function at time step t, and r, (0) 1a (Xx)
23

---

Published as a conference paper at ICLR 2025
The advantage function Ag is computed using TD(A), and represents how much better an action is compared to the expected value of a given state. It is given by:
A G. Vo(X,),
where G. is the TD(A) return estimate, which is a weighted sum multi-step returns, and (o())) is the value function. A, is computed by normalizing the advantage for each batch.
Algorithm 2 Diffusion Model Training based on rKL w/ RL
1: initialize learning rate 7,, Number of diffusion trajectories N, mini-batch sizes n,,
2: initialize PPO hyperparameters o, X, C1, K
3: DB= = 0
4: for each epoch in epochs do
5: Sample X (X
O:T v-,0:N in data buffer DB 7: update moving average statistics of the reward using R0:N and previous statistics normalize reward according to moving averages
6: Store (X 0:T 9o (Xo:r)) )o:N, (o...,, TT.N,, RO:N
8:
compute estimates of 40:A
9:
10:
compute AG.N by normalizing 0:7 while data buffer not empty do
12:
sample 1r)0mm = {t..... tr 10a DB w/o replacement
13: Update 5 0 - VoLPPO
14: end while
15:
end for
A.4 ARCHITECTURES
A.4.1 GNN ARCHITECTURE
The architecture we employ is simple Graph Neural Network (GNN). The process begins with linear transformation of each node's input features using layer of ny neurons. These transformed features, now serving as node embeddings, are then multiplied by weight matrix also consisting of пu neurons. Following this, variance preserving aggregation (Schneckenreiter et al. (022)) is performed over the neighborhood of each node. After message aggregation, we apply the Graph Normalization (Cai et al.) 2021). To preserve original node information, skip connection is in- corporated for each node. The aggregated node data, combined with the skip connection, is then processed through Node Multi-Layer Perceptron. This sequence of operations constitutes single message passing step. which is repeated n times. After completing all message-passinng steps, each resulting node embedding is input into final three-layer MI.. This MLP computes the probabil- ities for each solution variable X,. To normalize the data and improve training stability, we apply Layer Normalization Ba al. (2016) after every MLP layer, with the exception of the final layer in the terminal MLP. When we train the objective using RL methods, we compute the value function by applying an additional three-layer value network on top of global variance- prreeeevigg graph aggregation (Schneckenreiter et al. (2024). Here, we use neurons, except in the last layer where only one output neuron used. Across all our experiments, we consistently use n, 64 neurons in the hidden layers.
A.4.2 U-NET ARCHITECTURE
For the experiment on the Ising model, we use simple U-Net architecture Roitturrrernrnbeeerrrree et al. 2015) with overall three convolutional blocks which consist of two convolutional layers with a kernel size of 3 3 each. After the first convolutional block, we apply a max pooling operation with window size of 2 x 2. The second convolutional block is applied to the downsampled grid. Finally, after upsampling the last convolutional block is applied. For the diffusion model, we then apply three- layer neural network with 64 neurons the first two layers on each node of the grid, which predicts the Bernoulli probability of each state variable. For the autoregressive network, we apply mean aggregation on all of the nodes which we then put into a three-layer neural network to predict the Bernoulli probability of the next state variable.
24

---

Published as a conference paper at ICLR 2025
A.5 CO PROBLEM TYPES
All CO problem types considered in this paper are given in Tab.
Maximum Independent Set: The Maximum Independent Set problem is the problem of finding the largest set of nodes within a graph under the constraint that neighboring nodes are not in the set.
Maximum Cut: The Maximum Cut problem the problem of partitioning all nodes of a graph into two sets so that the edges between these two sets are as high as possible.
Minimum Dominating Set: The Minimum Dominating Set problem the problem of finding the smallest set of nodes so that every node in the graph is either in the set or adjacent to at least one node in the set.
Maximum Clique: The Maximum Clique problem is the problem of finding the largest set of nodes within a graph so that every node within the is connected every other node within the
Problem Type
Objective: min me H(X)
MIS
H(X) -A E
N X, + B Σ GUNEE X1 X,
MDS
H(X) A A X
2h (1 X.) x.) 1L]LENN X,)
MaxC1
H(X) = - X B Eianss X; XX,
MaxCut
H(o) = - 1-9.0 where Ø; = 2
Table Table with energy functions of the MIS, MDS, MaxCl and MaxCut problems (Lucas) 2014 Choosing A < B ensures that all minima of the energy function are feasible solutions. In all of our Experiments, we chose 1.0 and 1.1. The table is taken from Sanokowski et (2024).
A.6 GRAPH DATASETS
RB dataset: In the RB model, each graph is generated by specifying generation parameters n, ks and With the number of cliques, i.e. set of fully connected nodes, and with k the number of nodes within the clique is specified, p serves as parameter that regulates the interconnectedness between cliques. The lower the value of p the more connections are randomly drawn between cliques. If = 1 there are no connections between the cliques at all. To generate the RB- 100 dataset with graphs of an average node size of 100, we generate graphs with E [0.25.... ..., 1]. On the RB-small dataset E {5, [.... 12] and n E {20, 25} and graphs that are smaller than 200 nodes larger than 300 nodes resampled. On BA-large
{9, ..., 15). h {8, ..., 11], and
{20,..., .... 25) and E {40, ..., 55} and graphs that are smaller than 800 nodes or larger than 1200 nodes are resampled. For both of these datasets p [0.3, 1].
The BA dataset is generated using the networkx graph library Hagberg & Conway (2020) with the generation parameter m 4. BA-small number of nodes within each graph is sampled within the range (200, 300}, and in BA-large number of nodes is sampled within the range of {800,.. ..., 12003.
Marabasi-Albert dataset:
Ultimately, the matrix Q in D(Q) can be interpreted as a weighted adjacency matrix. for each CO problem instance, this adjacency matrix is defined by the corresponding graphs of each graph dataset as described in App. A.6 and its weights are given by the CO problem type definition as described in App. A.5
A.7 EXPERIMENTS
A.7.1 UCO EXPERIMENTAL DESIGN
The experiments in Sec. 5.1 are designed to maintain consistent memory requirements, gradient up- date steps, and training time across all objectives. For DiffUCO, fix these requirements by setting the batch size to n x ng x nair where n is the number of independently sampled trajectories, ng is the number of distinct CO problem instances, and nai is the number of diffusion steps in
25

---

Published as a conference paper at ICLR 2025
each batch. For the rKL w/ RL and fKL w/ MC objectives, can a minibatch of diffusion steps MAdif. which is not possible with DiffUCO. This allows us to increase the number of diffusion steps by factor of k while maintaining the same memory requirements during backpropagation. The batch size for these methods becomes B. X nG x N'ddiff where r'ddiff = Raiitt /k. As the number of diffusion steps increases by a factor of k the training time would normally increase accordingly. To counteract this and keep training time consistent across all objectives, we adjust the batch pa- rameters by decreasing ng by factor of k and increasing ng by the same factor. All computations across the batch size are conducted in parallel, and by increasing the batch size the number of up- dates per epoch is reduced, which reduces the training time per epoch. Therefore, these adjustments maintain constant overall batch size while reducing training time due to the increased ng.. This experimental design ensures that memory requirements, gradient update steps, and training time re- main constant across all objectives. It is important to note that with DifFUCO, it is not possible to increase the number of diffusion steps while keeping the training time constant at constant memory requirements. This is because memory requirements would increase by factor of k. which can only be mitigated by reducing either nG or ng by a factor of k. Reducing ng would increase the training time by an additional factor of k; leading to an overall increase of 122 in training time. Reducing B would not decrease the training time as these computations happen in parallel. Consequently, in this case, the computational time overhead would increase by a factor of k. Across all of these experiments, the architecture remains the same, except for the experiments with SDDS: rKL w/ RL, where an additional variance preserving aggregation Scchneckenreiter et al. (0224) on all nodes is applied after the last message passing layer. After that, this embedding is fed into a small Value MLP network with two layers.
In all of the UCO experiments we run on each dataset iterative hyperparameter tuning of the learning rate 7 and starting temperature Tstart for a short annealing duration of Neuning. Here, we first find an optimal Nopp such that we find a 1/1 and for which ? S 'opp.. S 7/2 but the average solution quality best for Tlopt- After that, we do the same for Tstart. We always chose Nruning = 500 except for the RB-large MIS dataset, where we chose Nuuning 200 due to higher computational demands. After obtaining the best hyperparameters we run the final experiments on three different seeds for Nnmeal epochs (see. App/A.1)
A.7.2 ABLATION ON LEARNING RATE SCHEDULE AND GRAPH NORM LAYER
We provide an ablation on the learning rate schedule (see App. A. A0 and the graph normalization layer. The comparison is conducted on MIS on small dataset of RB-graphs with an average graph
size 100 nodes. For each setting, we optimize iteratively first the temperature and then the learning rate for annealing runs with 500 annealing steps we have done in App. A.7.1] Results are shown in Tab. ( where we see that the cosine learning rate schedule and the Graph Normalization layer both lead to significantly better models.
DiffUCO: CE
vanilla
w/ Graph Norm w/ Ir schedule
RB-100 MIS t 9.63 1 0.05 9.71 + 0.02 9.73 + 0.04
Table 6: Ablation on learning rate schedule and Graph Normalization layer the RB-100 MIS dataset. The larger the MIS size the better. The discrete diffusion model is trained on the dataset without the learning rate schedule (vanilla), with the learning rate schedule (w/ Ir schedule), and with the Graph Normalization layer (w/ Graph Norm). Average MIS size is shown over three independent seeds. The standard error is calculated over two independent seeds.
A.7.3 UNBIASED SAMPLING EXPERIMENTAL DESIGN
For all of our experiments on the Ising model we follow (Nicoli et al. (2020) and use an annealing schedule which is given by T(n) = T. 1-0.998htm42y where ni is the current epoch and is a hyperparameter that defines how fast the temperature decays to the target temperature J. In our experiments on the Ising model, we keep the overall memory for each method the same. Each experiment fits on an A100 NVIDIA GPU with 40 GB of memory. In unbiased sampling, we use 400 iterations for NMCMC with batch size of 1200 states. In SN-NIS estimate the observables
26

---

Published as a conference paper at ICLR 2025
with 480.000 states. Nicoli al. (2020) 500.000 states in their experiments. Error bars calculated over three independent SN-NIS and MCMC runs.
A.8 ADDITIONAL EXPERIMENTS
A.8.1 STUDY ON NUMBER OF DIFFUSION STEPS AND MEMORY REQUIREMENTS
We provide further experiments on the RB-small MIS problem, evaluating the relative error 6yel Eupt Emodeil and the best relative error Gel := Eopt Emodall, where Eopt is the optimal set size [Eapel
[Bopsl
on this dataset and Emmodel is the average and model the best-set size out of 60 states of the trained model. We train DiffUCO, SDDS: rKL w/ RL, and SDDS: fKL w/ MC for 2000 epochs and plot these metrics over an increasing number of diffusion steps. The results are shown in Fig. [ We train each method on 4, 8, 12, and 16 diffusion steps, keeping the overall batch size constant each method. For DiffUCO, the memory requirements scale linearly with the number of diffusion steps, as indicated by the size of the marker in Fig. [ In contrast, for SDDS: rKL w/ RL and SDDS: fKI. w/ MC, keep the mini-batch size fixed at 4, so the memory requirement does not increase, hence the marker size stays the same. Specifically, the memory requirements are here the same as for DinUCO with 4 diffusion steps. We observe that for DiffUCO and SDDS: rKL w/ RL of the methods and eet improved with an increasing number of diffusion steps and that SDDS: rKL w/ RL performs better than DifTUCO in most cases. For SDDS: IKL w/ MC érel does not improve after 12 diffusion steps. We additionally show in Tab. the runtime per epoch for each run in Fig, which shows empirically that SDDS: rKL RL enables superior trade-offs between training and memory requirements. For instance, SDDS: rKL w/ RL with 12 diffusion steps exhibits better performance than DiffUCO with 16 diffusion steps while consuming slightly less training time (see Tab, 7 and four times less memory (see Fig.
10
SDDS: fKL w/
SDDS: fKL MC
DiffUCO
3x
DiffUCO
SDDS: rKL w/ RL
SDDS: rKL w/ RL
2 10
2 60-2
10-2
4 10-
3x-10-
6 10
10
12
14
16
10
12
14
16
Diffusion Steps
Diffusion Steps
Figure 1: (left) and d'el (right) on the MIS RB-small dataset over increasing amount of diffusion steps. The marker size proportional the memory requirements that are needed during training.
Method
Diffusion Steps
12
16
DiATCO
Runtime (d:h:m) 0:12:46 0:22:13
1:09:53
1:21:00
SDDS: rKL RL Runtime (d:h:) 0:16:06 1:07:06 1:20:26
2:11:26
SDDS: FKI. MC Runtime (d:h:m) 0:16:06 1:04:06 1:22:40 2:08:06
Table 7: Comparison of training time in d:h:m for different methods across various diffusion steps on the experiment from Fig. D
A.8.2 SPIN GLASS EXPERIMENTS
Unbiased Sampling:
We follow Del Bono et al. (2024) and conduct experiments on the Edwards-Anderson (EA) spin glass model in the context of unbiased sampling. Here, this model is defined periodic 2-1>
27

---

Published as a conference paper at ICLR 2025
grid, where neighboring spins interact with each other via random couplings Ji sampled from normal distribution with zero mean and variance of one. We consider this problem at B ~ 1.51 as sampling from this model at this temperature is known to be particularly hard for local MCMC samplers (Ciarella et al. 2023). Since this model cannot be solved analytically, we cannot compare ground truth values for free energy, internal energy, or entropy. Therefore, we use the free energy and the effective sample size as baseline, as a lower free energy and larger effective sample size generally better. We evaluate the performance of DinUCO, SDDS: rKL w/ RL and SDDS: fKL w/ MC under the same computational constraints. All models use GNN architecture with 6 message passing steps (see App. A..4 AA.) to incorporate the neighboring couplings as edge features. We train each method under the same computational budget and similar training time, which means that we train SDDS: rKL. w/ RL and SDDS: fKL. w/ MC with 150 diffusion steps for 400 epochs and DiffUCO with 50 diffusion steps and 1200 epochs. In each case, we use 200 samples during training and evaluate the free energy and effective sample size using 480000 samples. The results these experiments are shown in Tab. g where we observe that SDDS: IKL w/ MC performs best in terms of free energy and SDDS: rKL w/ RL performs best in terms of effective sample size.
EA 16 x 16
Free Energy F/L²
Car f
DiffUCO
-0.329 = 0.008
5.22 10 + 1.3 10-6
SDDS: rKL w/ RL
-1.09 + 0.003
8.56 x 10 2.29 x 10
SDDS: IKL. w/ MC
-1.165 = 0.003
3.2 10 4 10-7
Table 8: Free Energy per size and effective sample size per sample of different diffusion samplers on the Adtwards-Andesoo model of size 16 x 16.
Ground State Prediction: We also conduct experiments on the Edwards-Anderson model to pre- dict the lowest energy configurations. Here, we follow the setting from Hibat-Allah et al. (2021) and sample neighboring couplings from a uniform distribution [ on a 2-D grid of size 10 x 10.
We train SDDS: rKL w/ RL and SDDS: fKL w/ MC at 100 diffusion steps and 25 mini-batch diffu- sion steps. We follow Allat et al. (02T)) and train the model using 25 states and use 10000
cquilibrium steps Tstart 1.0 and anneal the temperature down zero. Our models use GNN architecture with message passing steps (see App. A.4) and are trained for 4000 training steps. We compare to the result of classical-quantum optimization (CQO) (Martoñák et al. 2002 Gomes et al.] 2019 (Sinchenko & Bazhanov] 2019: Zhao et al. 2022)). Variational Quantum Anneal- ing (VQA), regularized Variational Quantum Annealing (RVQA) and Variational Neural Annealing (VNA) as reported in Allat el al. (2021) at the same amount of training steps. Results of the
average energy value over 200 samples are shown in Tab. g
where we see that SDDS: rKL w/ RL
significantly outperforms all other methods.
EA 10 10
(QA
RVQA
VNA
SDDS: IKL w/
SDDS: FKL, MC
Ga/l24 2 10 10 2 10 1e-1
10
10 2 to-1 1.98
10
10-* 9.23 10 19 1014
Table 9: Average ground state energies of different diffusion samplers on the 2-D Edwards-Anderson model of size 10 x 10. (r) indicates that results are taken from (Hibat-Allah et al. 2021
A.8.3 TIME MEASUREMENT
We follow Sanokowski et al. 2024) and perform all time measurements for Deep Learning-bass methods on an A100 NVIDIA GPU and perform the time measurement after the functions are com- piled with jax.jit.
A.9 MEMORY REQUIREMENTS
The experimental setups for various datasets and models have specific GPU requirements. For the RB-small dataset, two A100 NVIDIA GPUs with 40GB of memory each are necessary. The RB- large MIS experiment demands four such GPUs In contrast, the smll dataset can be processed using a single A100 GPU, while the BA-large dataset requires two A100 GPUs. The Ising model experiments can be conducted efficiently with one A A100 GPU.
28

---

Published as a conference paper at ICLR 2025
A.10 HYPERPARAMETERS
For all of our experiments, we use one iteration of cosine learning rate (Loshchilov & Hutter 2017) with warm restarts, where start low learning rate of 10-19 and increase it linearly to a learning rate of Amaz for 2.5% of epochs. After that, the learning rate is reduced via co- sine schedule Xmex/ /10. 10. We use Radam as an optimizer Liu et al. (2020). All hyperparame- ters and commands to run all of our experiments can be found in the fxtt files within our code in /argparselexprrieentttU
and /argaars/experiment///nng In our experiments, we always use diffusion steps for DiffUCO and 12 diffusion steps for SDDS: rKL w/ RL and SDDS: fKL w/ MC, except on the BA-small MDS and BA-small MaxCut dataset where we use and 14 diffusion steps respectively. Compared to (Sanokowski al., 2024) we use up a factor of 4 times more diffusion steps, as they use only between 3 and 6 diftusion steps under similar computational constraints. We always keep PPO-related hyperparameters to the default value, except RB- RB-large MIS, where have adjusted the hyperparameter a (see App. A.3.6
A.11 CODE
The code is written in jax (Bradbury et al. 2018).
A.12 EXTENDED TABLES
For completeness we include in Tab.
Tab. 10 and in Tab. 12 other baseline methods reported
in Sanokowski et al. 2024).
MIS
RB-small
RB-large
Method
Type
Size
time
Size
time
Gurobi Gurohi Optimization. 1.I.
2023
OR
20.13 + 0.03
6:29
42.51 0.06"
14:19:23
LwtD (n)
Abn al.
2020
UL
19.01
2:34
32.32
15:06
INTEL
La 2018
SL
18.47
26:08
34.47
40:34
DGL. (r)
Bother el al.
2122b
SL.
17.36
25:34
34.50
47:28
LTFT
[Zhang
UL
19.18
1:04
37.48
8:44
DifTUCO (r)
(Sahokowsk et al
2024
UL
18.88
0.06
0:14
38. 10 = 0.13
0:20
DiffUCO: CE
SSaokowws ai.
UL
0.05
1:48
9:54
DiATCCO
UL.
19.42 + 0.03
0:02
39.44 +: 0.12
0:03
SDDS: rKL w/ RL
19.62
0.01
0:02
39. + 0.08
0:03
SDDS: JKL w/ MC
UL 19.27
+ 0.03
0:02
38.41 =: 0.06
0:03
DitUCO: CE SDDS: rKL w/ RLCC
UL.
19.42
0.03
0:20
39.49 1: 0.09
6:38
UL
19.62
0.01
0:20
39.99 + 0.08
6:35
SDDS: JKL w/ MC-CE
UL
19:27
+ 0.03
0:19
38.61 = 0.03
6:31
Table 10: Extended result Avera. independent set size on the whole test dataset on the RB- small and RB-large datasets. The higher the better. The total evaluation time shown in h:m:s. (r) indicates that results are reported in Sanokowwki et al. (2024). + represents the standard error over three independent training seeds. (CE) indicates that results are reported after applying conditional expectation. The best neural method is marked as bold. Gurobi results with indicate that Gurobi was run with a time limit, On MIS RB RB-large the time- is set to 120 seconds per graph. this table, SL is for supervised learning and UL is for unsupervised learning methods.
29

---

Published as a conference paper at ICLR 2025
MDS
BA-small
BA-large
Method
Type
Size
time 4
Size 4
time
Gurobi Gurobi Optimization, LLC
2023 OR
27.
84 0.00
1:22
104.01 0.27
3:35:15
Greedy (r)
H
37.39
4:26
140.52
1:10:02
MFA (r)
BBilro el al
1988
II
36.36
5:52
126.56
1:13:02
EGN: CE (r)
Karahas & Loukas
2020
UL 30.68
2:00
116.76
7:52
EGN-Amneal: (E Sun et al LTFT (r)
2022
UL. 29.24
2:02
111.50
7:50
Zhang el m 202.5
UL 28.61
4:16
110:28
1:04:24
DiffUCO (r)
(Sanokowski al. 2024
UL
0.10 28.30
0:10
107.01
0.33
0:10
DifTUCO: CF ().
Sanokowski
2024
UL. 28.20 +.20++0.000 0.09
1:48
106.61
6:56
DiflUCO SDDS: rKL RL
UL 28.1011.00
0:01
21 1 0.21
UL
28.03
0:02
105.16
0.21
0:02
SDDS: fKL w/ MC
UL
2.00
0:01
105.70 : 0.25
0:02
DifUUO: CE SDDS: şKI. w/ RI-CE
UL 28.09 0.01
0:16
105. 21 0.21
1:45
UT. 28.02 0.01
0:16
105.15 15-1--1 0.20
1:41
SDDS: JKL w/ MC-CE
UL 2
0:16
105.7 = 0.25
1:41
Table 11: Extended result table. Average dominating set size the whole test dataset on the BA- small and BA-large datasets. The lower the set size the better. Total evaluation time is shown in ham:s. (r) indicates that results reported in (annoooskii et al. (2024). + represents the standard error over three independent training seeds. (CE) indicates that results are reported after applying conditional expectation. The best neural method is marked bold. In this table, H stands for heuristic, SL for supervised learning and UL for unsupervised learning methods.
MaxCI
RB-small
MaxCat
BA-small
BA-large
Method
Type
Size
time 1
Method
Size
Size
time
Gunoes Gurobi Girrbii Optimization,
2023
19.06
11:00
Gurobi
730.87 2.35* 17:0000
2:35:10:00
Greedy
Greedy
2786.00
MFA (c)
Balbro et al
1988
H
14.52
1:28
MFA (O)
701.00
3:12
2833.86
14:32
EGN: (E
Kardlay & 2okg
2020
UL
12.02
1:22
EGN: CE (c)
UL
693.15
1:32
2870.34
5:38
EGN-Ammon
UL
14.10
4:32
BON-Ameeal CE
UL 606.73
1:30
2863.23
5:36
LTFT
16:24
1:24
LTFT
5:54
14.51 0.39
0:08
DIfTUCO
2347.22
1.50
DiFUCO: CE
Sannknostt 2024
UL
16.22 0.00
2:00
DiFUCO: CE
UL
T27
2:33
2:00
2947 =:: 1.48
7:34
DiTUCO SDDS: #KT w/ RT. SDDS: MC
UL 17.40
0.02
0:02
DITUCO
UL 751
0.75
0:02
2974 60
7.73
0:02
UL. 18.80
+ 0.04
DH22
SDDS: 187 w/ RI.
UE.
751
93 0.74
D:02
2971 62 8.
0:02
0:02
0.02
2973
DiBUCO:
DiEUCO:
2974
SDDS: rKL w/ RL-CE SDDS: w/ MC-CE
UL 18.90 0.04
0:38
SDDS:
(KL w/ RL-CE
UL 731.93
0.74
0:14
2971 62 8.15
1:08
UL 18:41=000
0.02
0:38
SDDS: JKL MC-CE
UL 751. 0.69
0:14
2973. 80
7.57
1:08
Table 12: Extended result table: Left: Testset average clique size on the whole on the RB-small
dataset. The larger the set size the better. Right: Average test set cut size on the BA-small and BA-large datasets. The larger the better. Left and Right: Total evaluation time shown in d:h.m:s. (r) indicates that results are reported as in [Sanokowski et al. (2024). (CE) indicates that results are reported after applying conditional expectation. Gurobi results with indicate that Gurobi was run with time limit. On MDS BA-small the time limit is set 60 and on MDS BA-large to 300 seconds per graph. The best neural method is marked as bold. In these tables, H stands for heuristic, SL for supervised learning and UL for unsupervised learning methods.
30


Reviews:
[{"review_id": "WQBVxIRh4Y", "reviewer": "Reviewer_vFfF", "summary": "This paper presents improvements to existing diffusion-based methods for sampling from discrete unnormalized distributions by introducing two techniques that reduce memory requirements for training the forward and reverse KL objectives. For the reverse KL objective, the authors utilize the policy gradient theorem to lower memory costs, which typically scale linearly with the number of diffusion steps in most samplers. In addressing the forward KL objective, they reformulate the loss using importance sampling and employ Monte Carlo estimation to compute the sum over diffusion steps, thereby minimizing memory usage during backpropagation. The authors validate their methods through experiments on Ising model benchmarks.", "questions": "* I am interested in the memory usage for each set of experiments reported in the paper. Including this information would enhance the presentation. Additionally, it would be valuable to see how model performance varies with the number of diffusion steps and memory budget. Specifically, I wonder if the memory budget is genuinely a bottleneck for standard diffusion-based samplers in the experiments presented.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The innovative approach to computing the forward and reverse KL loss functions is the paper's main strength. Developing memory-efficient loss functions is particularly important for diffusion models.\n* The paper is clearly written and all the results are well presented.", "weaknesses": "* The empirical validation of the proposed algorithms is insufficient to convincingly demonstrate their practical benefits. It would be more compelling if the authors included comparisons to standard diffusion-based samplers under the same computational constraints or memory budget in the Ising model experiments. The current comparisons against the AR baselines do not adequately highlight the potential advantages of the proposed methods over conventional diffusion-based samplers.\n\n* The experiments conducted do not appear to be sufficiently challenging, and the memory requirements of standard diffusion-based samplers in these cases may not pose significant issues in practice. It would be beneficial for the authors to test their methods in more complex settings in statistical physics (e.g., the phi-4 model) or on image generation tasks (e.g., CIFAR-10).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DEiX07eIe5", "reviewer": "Reviewer_RMkz", "summary": "This paper introduces Scalable Discrete Diffusion Samplers (SDDS) for generating samples from complex, unnormalized distributions over discrete domains, with applications in combinatorial optimization and statistical physics. Traditional methods in this area are limited by memory scaling issues and lack of unbiased sampling capability. To address these challenges, the authors propose two new training methods for diffusion samplers: one based on policy gradient reinforcement learning (RL) for minimizing the reverse KL divergence and another using Self-Normalized Neural Importance Sampling (SN-NIS) for unbiased forward KL divergence estimation. These approaches enable more diffusion steps within fixed memory constraints and allow for unbiased sampling, which is crucial for many scientific applications. Experiments on combinatorial optimization benchmarks show that SDDS achieves state-of-the-art performance, and unbiased sampling evaluations on the Ising model demonstrate improved accuracy over traditional autoregressive models.", "questions": "- How do the proposed methods affect overall computational efficiency? Specifically, does the integration of PPO in SDDS: rKL w/ RL significantly increase training time compared to standard diffusion models or autoregressive approaches?\n- Why was PPO specifically chosen for optimizing the rKL-based objective?\n- Can the authors provide theoretical or empirical insights into the convergence properties of the proposed methods? Specifically, under what conditions do the RL-based training procedures converge, and how stable are they across different problem instances?\n- How does varying the number of diffusion steps during training and inference influence the model's performance? Is there an optimal range of steps beyond which improvements plateau or diminish?\n- Why was DiffUCO the primary(or only) comparison, and have the authors considered additional benchmarks such as those in Zhang et al. (2023)? Given that MDS results might not be state-of-the-art, how would the method perform against others besides DiffUCO?\n\n[1] Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C. Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. NeurIPS 2023", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper introduces two novel methods (RL-based reverse KL and SN-NIS-based forward KL) to address memory scaling issues, enabling the use of more diffusion steps while staying within fixed memory constraints.\n- By extending importance sampling and Markov Chain Monte Carlo methods to diffusion models, the authors enable unbiased sampling—a critical requirement for scientific applications that require accurate expectation estimates.", "weaknesses": "- Although the paper reports inference time alongside results, a more comprehensive analysis of computational costs is needed, particularly in terms of training time and overall efficiency.\n- The paper would benefit from a deeper theoretical exploration of the convergence properties of the proposed methods, especially the RL-based approach. Clarifying the conditions under which convergence is guaranteed would strengthen the paper's contributions.\n- The experiments lack ablation studies to isolate the effects of individual components of their models.\n- The paper primarily compares the proposed methods with DiffUCO.\n- The presentation of the experimental results could benefit from clearer organization and more detailed explanations to improve readability and interpretability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Kc6uLzA1Yp", "reviewer": "Reviewer_UBbm", "summary": "The article considers the task of learning to sample from complex unnormalized distribution for discrete variables, with application to optimization and sampling problems. The problem in this kind of task is the need to keep track of the entire diffusion trajectory, making it very demanding in memory. The authors alleviate this problem by using Importance Sampling (in one case) or Reinforcement Learning techniques in another one. More precisely, they propose two kinds of modification: first to use the forward KL (instead of the reverse one) in order to remove the problem of having to save the whole trajectory, at the cost of needed to use sampling from the target distribution (here done with importance sampling); second they reformulate the optimization problem on the reverse KL as a Reinforcement Learning problem, allowing to deal with the optimization using technique coming from RL.", "questions": "- I guess the reason why the whole trajectory is needed to optimize eq. 2 is because the gradient will be applied to the expectation value, from which all steps will be affected. Is that correct ? if yes, it might be clearer to specify it right after eq. 2 (using main text, footnote or a reference to the supplementary materials).\n\n- In 2.2, the distribution $\\mathcal{D}(Q)$ is not specified. It might be useful to put a bit of precision, since I imagine that the goal is to use an ensemble of similar optimization problem. For instance, a reference to sec. 4 of the appendix with a detail on the distribution of Q for the different considered cases.\n\n- What is exactly the difference between IS and SN-NIS ? it would be good for clarity to add an explanation in the article on that point.\n\n- Same comment for neural MCMC, how is it any different from classical MCMC ? it would be good for clarity to add an explanation in the article on that point.\n\n- The part 2.3 is a bit misleading, it seems to describe classical method of sampling while it is not even clear at that point where it will be used for. In fact, most of it is repeated in sec. 3.2...\n\nMinor comment:\n- eq. line 114, p should be p_B no ?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides two different ways of solving the memory issue in the context of discrete diffusion model when using the reverse KL. \nA reasonable list of optimization's benchmarks are provided.", "weaknesses": "The benchmark of sampling on Ising is ok, but we could have expected more difficult cases. For instance, the 2D spin glass ($J= \\pm 1$) might be\n* a more challenging task not too different from the Ising case considered in the paper\n* and for which the polynomial algorithm exists at least for the ground states. \n\nIn relation to both their work and this case, they can also refer to the following article: https://arxiv.org/pdf/2407.19483 which study using a different approach the sampling on the 2D Ising spin glass for comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)