Fractional Langevin Dynamics for Combinatorial Optimization via Polynomial-Time Escape
Authors: Shiyue Wang
Ziao Guo
Changhong Lu
Junchi Yan
Venue: NeurIPS 2025 poster ()
Keywords: Franctional Langvin Dynamics
Combinatorial Optimization
Primary area: optimization

Abstract: Langevin Dynamics (LD) and its discrete proposal have been widely applied in the field of Combinatorial Optimization (CO). Both sampling-based and data-driven approaches have benefited significantly from these methods. However, LD's reliance on Gaussian noise limits its ability to escape narrow local optima, requires costly parallel chains, and performs poorly in rugged landscapes or with non-strict constraints. These challenges have impeded the development of more advanced approaches. To address these issues, we introduce Fractional Langevin Dynamics (FLD) for CO, replacing Gaussian noise with $\alpha$-stable L\'evy noise. FLD can escape from local optima more readily via L\'evy flights, and in multiple-peak CO problems with high potential barriers it exhibits a polynomial escape time that outperforms the exponential escape time of LD. Moreover, FLD coincides with LD when $\alpha = 2$, and by tuning $\alpha$ it can be adapted to a wider range of complex scenarios in the CO fields. We provide theoretical proof that our method offers enhanced exploration capabilities and improved convergence. Experimental results on the Maximum Independent Set, Maximum Clique, and Maximum Cut problems demonstrate that incorporating FLD advances both sampling-based and data-driven approaches, achieving state-of-the-art (SOTA) performance in most of the experiments.

Fractional Langevin Dynamies for Combinatorial Optimization via Polynomial-Time Escape
Shiyue Wang 1,3,, Ziao Guo Changhong Lu', Junchi 2.3 School of Mathematical Sciences, Key Laboratory of MEA, and Shanghai Key Laboratory of PMMP, East China Normal University School of Computer Science & School of Artificial Intelligence, Shanghai Jiao Tong University Shhanhaii Innovation Institute
(wangahiyuedstu, chlu@mathh wwn..cccdeii edu. en
{ziao (ziao.guo, guo, yanjunchi>&sjjt edu.
Abstract
Langevin dynamics (LD) and its discrete proposal have been widely applied in the field of Combinatorial Optimization (CO). Both sampling-basee and data- driven approaches have benefited significantly from these methods. However, LD's reliance on Gaussian noise limits its ability to escape narrow local optima, requires costly parallel chains, and performs poorly in rugged landscapes with non-strict constraints. These challenges have impeded the development of more advanced approaches. To address these issues, we introduce fractional Langevin dynamics (FLD) for CO, replacing Gaussian noise with a-stable Lévy noise. FLD can escape from local optima more readily via Lévy flights, and in multiple-peal CO problems with high potential barriers it exhibits polynomial escape time that outperforms the exponential escape time of LD. Moreover, FLD coincides with LD when 2, and by tuning it can be adapted to wider range of complex scenarios in the CO field. We provide theoretical proof that our method offers enhanced exploration capabilities and improved convergence. Experimental results on the Maximum Independent Set, Maximum Clique, and Maximum Cut problems demonstrate that incorporating FLD advances both sampling-bas based and data-driven approaches, achieving state-of-the-art (SOTA) performance in most of the experiments. The codes are publicly available at
Introduction
Combinatorial optimization (CO) problems, which involve finding optimal solution from finite set of possible configurations subject to a set of constraints, are of paramount importance and usefulness across fields, e.g. logistics 455 scheduling [59] network design [4] and finance [39].
There has been growing interest developing efficient algorithms for obtaining high-quality sub- optimal solutions. Among these efforts, sampling-based methods have shown considerable promise due their simplicity, ability to balance speed and solution quality, and training-free -free property. A fundamental approach is simulated annealing (SA) [28), which uses random local fluctuations guided by Cetropolis-Hastinge updates [36] 23 and probabilistically explores the solution space. Recent work [11 has demonstrated that incorporating Langevin dynamics (LD) and its discrete proposal 669 can vastly improve the sampling efficiency, thereby advancing sampling-hai based approaches for CO. The core idea of LD is to leverage the gradient to guide the sampling in each iteration, resulting in more efficient searching process. However, there are certain limitations
"Coreesonddncce author. i denotes equal contribution. This work partly supported by National Key R&D Program of China (Nos. Y0A 1000300 and 2021 YFA 100302) and National Natural Science Foundation of China (No. 12331014, 62222607).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

associated with LD. Firstly, it relies on Gaussian noise as a random perturbation, with the step size being coupled to the noise amplitude. As the Gaussian noise decays exponentially at the tail, reducing the step size also diminishes the noise, making it challenging to escape from 'deep and narrow" local optima. The time required to escape local minima grows exponentially with the energy barrier height. Moreover, to maintain sample diversity, LDD necessitates parallel independent chains, which can be computationally expensive. Furthermore, Gaussian noise assumes a locally smooth energy landscape, meaning that LD is less effective in scenarios where the energy function is rugged when non-strict constraints are present. These factors limit the effectiveness of LD in more complex optimization landscapes and the development of more advanced sampling- -ased approaches for CO.
Another trend is the data-driven approach learning for optimization. Early neural network (NN)- based methods [24] primarily relied on supervised learning [33] 18 21]. Subsequent works have
explored reinforcement learning 662 60 61] and unsupervised learning [27 57 52 techniques to
address the challenge of collecting labeled training data. More recently, diffusion models have been
introduced to the CO domain 53 44 45 demonstrating superior performance and promising potential. These approaches also implicitly incorporate LD, as diffusion models were initially derived from LD in the field of image generation. Unlike sampling-bas -bsed methods, NN-based approaches eliminate the need for explicit gradients of the problem, thereby enabling unification for variety of problems without relying on the problem structure, utilizing the network's 's automatic differentiation capabilities. We leave detailed related works in Appendix 2
In this paper, we introduce fractional Langevin dynamics (FLD) to address the propensity of con- ventional L.D) to become trapped in local optima. We incorporate symmetric o-stable (SoS) noise with truncation into FLD:; unlike Gaussian perturbations, SaS noise exhibits heavy-tailed jumps (Lévy flights), enabling instantaneous energy- barrier leaps that facilitate escape from local min- ima. Moreover, by setting a = 2, FLD reduces to standard LD, thus retaining efficient exploration in smoother strongly constrained settings. We propose the SaS-noise FLD sampling process and present both explicit- and implicit-gradient formulations to advance both sampling-basee data-driven approaches. We adopt the mean escape time as our convergence metric, and derive theoretical upper bounds in the discrete setting, showing a polynomial exponential bound for LD. Through comparative case studies on three prototypical CO problems, our methods outperform existing sampling-buus based and data-driven methods. Additionally, extensive trajectry experiments have been conducted vividly illustrate the enhanced escape ability of FLD, demonstrate the impact of varying a on escape performance, and confirm the effectiveness of our truncation strategy. Finally, we perform ablation studies on the best energy-function values over iterations, thereby validating superior convergence and exploration capabilities of FLD.
and
bound for FLD versus an
2 Related Work
Data-driven Approaches for CO. They involve training NN models for CO, commonly referred to as neural solvers. Significant efforts have been made to explore supervised learning [33 [8 21
53
20,, and reinforcement Our FLD-IG integrates FLD with simple reinforcement beanning-based approach. FL.D-IG achieves competitive performance with simple architecture and minimal training resources, resulting in faster convergence and improved training efficiency.
31
58
32
30
34 35), unsupervised learning (27 57 52 56
learning 40
Sampling- based Approaches for CO. Sampling- based approaches have been widely utilized for 336 23
65, 46). However, these previous approaches are generally less efficient than data-driven approaches. Recent work by (51] has advanced sampling-base methods, achieving comparable or even superior performance to data-driven approaches by introducing the discrete LD proposal 66 [50]. I7 further develops a regularized approach on discrete LD, resulting in improved performance. Our FLD-EG EG enhances the sampling- based approach by integrating FLD, which can be seen as a generalization of vanilla LD, leading to faster convergence and better performance.
CO
37
10,
Preliminaries
Baase Model (EBM). It defines an energy function H S R with the target distribution:
-H(x)/T
Pr (x(x):
(1)
Z

---

where S represents the energy state space, 7 is a temperature parameter controlling the smoothness of the distribution, and Z = Exes e e-H(u)/r is the partition function in statistical physics or normalization factor in probability theory.
Markov Chain Monte Carlo. Markov chain Monte Carlo (MCMC) techniques 63 54 which
grounded in continuous diffusion processes, have gained widespread popularity owing their demonstrated success in large-scale Bayesian machine learning [TT]. The goal of the MCMC is to generate samples from target distribution pr, by forming continuous diffusion that has pa stationary distribution. Given a current state Iy E S, a Metropolis-HHstingg (MH) sampler [36] 23 proposes candidate state y S from proposal distribution g s4)). Then calculate the Metropolis acceptance ratio:
Aly, xx) min {1,
Pr (v)g(( v)
Pr (xr)g(y xx))
With generating random number (O, 1), where (O, 1) is the uniform distribution within [0, if. u & A(y, 2,), then the proposal state is accepted and set 2++1 = y, otherwise, set Ze+1 = Ty.
Langevin Dynamics. Langevin dynamics (L.D) is an MCMC algorithm that has also been incor- porated in combinatorial optimization algorithms for better exploring the landscape of the energy function (x) [47]. LD methods are based constructing stochastic differential equations (SDEs)
equipped with Brownian motion (shown as Eq. (3), assuming that the particle is driven by an infinite number of small forces with finite variance.
dx. = s(xe)dt + V2dB.
where B, denotes the standard Brownian motion and s(.) = V (-) = - (z) represents the score function of EBM. With the condition of sampling state 2; be shown be ergodic with Pr (mz). The samples can be generated from pr by simulating the sampling process of continuous space discrete space 41, which is given by using first-order Marler-aruyyma discretization:
Tn+1 2n + ( + v 2m
where 7h1 denotes the step size of the sampling iteration and AB, = E is an i.i.d. standard Gaussian random variable, { (O0, INNN) when the state space S = R [69.
Simulated Annealing. Simulated annealing (SA) is variant of local search [4] that explores the solution landscape with probabilistic relaxation. As the temperature decreases, there is a tendency to sample points on the landscape to make the energy function H (x) value smaller; when the temperature equals zero, the solution æ will stop at the point where the H (x) has the lowest value (that is, the solution obtained by the SA algorithm converges the global optimum in probability) (55)
4 Methodology
4.1 Problem Formulation
Without loss of generality, we formulate CO problem as follows:
min = 1ES=(0,11a
a(x), s.t. b(x)
where the solution landscape S is an N v-dimensional vector such that each dimension takes a discrete value from (0, 1}. which is the most challenging to deal with, although will be possible extend.
To recast a constrained optimization problem as a sampling task, a penalty function (generally treated as the energy function of EBM) takes the form:
H(x) = a(x) + Ab(x)
(6)
where À is the penalty factor of the constraints. Furthermore, the attempt to directly sample from (x() with the small 7 makes the energy landscape highly nonsmooth; common remedy to incorporate the SA algorithm, progressively lowering toward zero as the chain evolves.
3

---

4.2 Fractional Langevin Dynamics
By Eq. ) it can be seen that the term (In+1 2n, "1++1((a))) /2m+)1/22m+++/ follows Gaussian. Thus the transition probability g( | zn,) in the LD algorithm can be interpreted as a Gaussian with mean di, + 7/++188 (1)))( and covariance 21/n+1 XNN [69] The discrete (gradient-based) proposal distribution with the explicit domain S = RR of L.D is:
exp
4
In+1 In m Tn+1s(En)13
( xnn)
ZRN (In)
where,
ZaN (In)
Σ exp
(-
|nn+1
77+ ( = (4Tma+1)
(8)
417
IHIEERN
Thus, can be factorized coordinate-wise into set of simple categorical distributions:
( In) & exp {
( - Ii, (0in++1 - xi.n.
(9)
Ma+1
with
(xn+1 xx) II g( 2n)
(10)
Typically, the iteration step size 7) = C. where is con- stant, is too stable due to the combination of a fixed step size and Gaussian noise. This stability makes it difficult for LD to escape from local optima on the energy surface during the iterative process, often causing the trajectory to remain trapped near suboptimal solutions, thereby signif- icantly degrading the quality of the final result. To address this issue, we introduce the stable Lévy noise [67] a type of stochastic process with heavy-tailed distribution. Unlike Gaussian noise, o-stable Lévy noise allows for occasional large jumps (Lévy flights), which increases the probability of escaping local optima and thus improves the exploration capability of the algorithm.
10"
10.0
259
259
15
20
In this work, we are interested the centered symmet- ric a-stable (SaS) distribution, which is special case of a-stable distribution. The definition of SaS random variables and SaS Lévy motion shown
Figure 1: Pdf of SaS distribution and a-stable Lévy motion.
The a--table distribution arises as the limiting distribution in the generalized Central Limit Theorem (CLT). A sealar random variable x E B is said to follow a SaS distribution its characteristic function takes the following form:
Definition I (SaS random variables 42
Elexp(iwxx) = exp(-low]()
(11)
Here, E (0, 2] is the characteristic exponent, which controls the tail heaviness of the distribution: smaller values of a result in heavier tails (shown Figure The parameter RR+ is the scale parameter, reflecting the dispersion of x around zero.
Definition 2 (SaS Lévy motion [1)). A scalar symmetric a-stable Lévy motion Li, with E {0,2]. stochastic process satisfying the following properties:
1. Ig = 0 almost surely.
2. For to < <h < ... <. LN. the increments (LG, - Ta -T (n 1,,,,,2,-
1,2, .., .N are independent.
3. The (L L and Lÿ_ have the same distribution SaS((t s)) (0 <tt).

---

4. Li has stochastically continuous sample paths (that is. continuous in probability): L >
lim PiLL
6) = 0, vg > 0,520, 0.
(12)
Similarly to the SaS distributions, the Sa8 Lévy motions LE coincide with scaled Brownian motion v2B, when a Thus, the SoS distribution can be seen as a heavy-tailed generalization of the centered Gaussian distribution. As an important special case of SaS, we obtain the Gaussian distribution (a)(r)= (0, 2 for a = 2.
The fractional Langevin dynamics (FLD) framework is driven by the SoS Lévy-based SDE as
dx; b + dLş
(13)
where, b(-) denotes the drift function shown in Theorem 1 zt- represents the left limit of the process at time t, and LE is the standard SaS Lévy motion shown as Definition] 2
Theorem (7
The function of the SDE (73) is defined below:
D D= fx) s(x(
a(z,a)
(14)
δ(x)
where, fp. (x) _ (bx)0, (()) integration Da-2 & F F-11 (x))), cx)(-H(x)}, Ca I(a 1)/T(a/2)). and F is the Fourier transforms.
x(x)
Detailed derivation and proof can be found in Appendix A
Proposition 1. The FLD-based SDE is the generalization of the LD-based SDE.
Proof. When a 2, the SDE driven by the FLD:
dz, = b(xx,, 2) + dL. + 2) x (2s(2;)dt + d + 2) = d(x))dt + v2dB (15)
Thus, the FLD-based SDE reduces to the LD-based SDE when a = 2, while for a # 2, the FLD-based SDE exhibits heavier tails.
Combining the Theorem and Eq. (13), the approximate SoS Lévy-based SDE and the first-order Euler- Maler-Maruyama discretized SaS sampling process be obtained as:
dx, c. (2,)) + dL, xL = In + (1.+1c. + m L L
(16)
The Proposition also demonstrates that the target distribution can be sampled more accurately by adaptively adjusting a during the sampling process. In regions where the energy function is locally smooth or tightly constrained, setting a enables efficient sampling. Conversely, when the sampling process becomes trapped in local optimum, decreasing a increases the probability of Lévy flights, thereby facilitating escape from the local minimum.
Moreover, although the probability density function (pdf) of the SaS distribution does not have a closed-form expression, is straightforward to generate random samples from stable distributions when a # 2. The sampling of SaS is given by Theorem 2 with = by the Chambers Mallowss- Stuck method, which is shown in Theorem 3
Theorem Let y be uniformly distributed on (- 3) and be an independent exponential
random variable with mean 1. The a-stable sampling is:
sin ain - 70) cos(( a(r 70))
(1 (1-a)/a
P (1,8,), a +
(c08 7)1/aa
W
7 =
(17)
π + 87) tan 7 - 3og
W cos
(1,1,,,0) a
2
By
where, To *BK(a)
K(a)= = a 1+ 1iggn - a). and sign(-) denotes the sign function.
2a
Theorem 3. Let y be uniformly distributed on --1 $ and W be an independent exponential
random variable with mean 1. The SaS sampling is:
sin s
cos(y a7))
(1-a)/a
A SaS(1), a a#1
Z
(cos 1//aa
W
(18)
tany & S18(1), a ==1
5

---

Since SaS distributions are special case of a-stable distributions, the detailed proof of Theorem and Theorem 3 is presented together Appendix B
Thus the discrete sampling process can be
rewritten as 48 where -n-1 SoS((1)
1/a Mn+ Co (H()))
1n++1 Zin
7h+ Ba+1
(19)
4.3 Comparative Analysis of Convergence
compare the convergence capabilities LD and FLD by analyzing the escape time from the local minima, which is defined as follows [5]:
Definition 3 (Escape Time). The escape time is random variable:
T inf > : Bs(y")
(20)
where, xx" two points x² and y" separately represent local minima under the assumption that the potential energy H has several (at least two) local minima, and Bs(y") denotes the ball of radius ó centered in y"
Under the low noise intensity e, the LD-based SDE can be rewritten as:
dx, (x + 22d
(21)
By Eyring-Kramnn Kramers law, the mean escape time of LD-based SDE in the continuous space IR- is:
2m
det (=))(v)((=")) Net(V=H((*)) (xp(((((="-H((()))) x (xp((((22)-H((x)) (22)
X(2*)
where =" is a unique saddle (that is the maximum of the potential energy barrier) and X(.) denotes the single negative eigenvalue of the Hessian matrix 7 H-))
The mean escape time of FL.D-based SDE
25 in the continuous space S E R is:
E 0
x w
(23)
where w denotes the "width" of the local minima to the boundary of potential well.
Similarly, we provide the discrete proposal for the escape time of both LD and FLD. We state upfront that the Markov chains of I.D and FL.D reversible if they satisfy the detailed balance conditions. Additionally, Pr (*r)) is positive stationary distribution, given that the symmetric proposal and the Eatropolis-Hastinge acceptance criterion satisfied for constructing discrete L.D and FLD. Thus, when the state space is a finite or countable set S = {0, 1) the symmetric Dirichlet form:
(f = 2
Σ (f(z) f()))pp
(24)
2.EES
where (a y) represents the transition matrix. Then, the conductance of an arbitrary non-empty truth subset
is:
$ (B) = -inf (A(1B, 18)
ΣΣ
(z,))
(25)
B (B(
(B)
ZEB y
The first non-trivial eigenvalue given by the Cheeger inequality of LD
29
49
is shown as follows:
(B))))²
A
(26)
2
By the same reasoning, the first non-trivial eigenvalue of FLD 2 is:
Q2
'T N+a
Af > CN... D. (B)
T. (B)
(27)
/1/2/( 9

---

Table 1: Results of compared methods for MIS problem.
MIS
RB-(200-300]
RB-1800-1200)
ER-[700-800]
ER-19000- 11000)
Method
Type
Size
Time
Size f
Time 4
Size
Time
Size
Time !
Gurobi
OR
19.98
47.57
40.90
2.17h
41.38
50.00 m
KaMIS OR
20.10
1,40
43.15
h,05h
44.87
52.13 m
381.31
7.60h
DGL
SL
17.36
12.78
34.50
23.90 m
37.26
22.71
INTEL
SL
18.47
13.07
34.47
20.28 m
34.86
6.06 m
284.63
m
DIFUSCO
SL
18.52
16.05
41.12
26.67
LTFT
UL 19.18
32
4.37 m
DiffUCO
UL 19.24
54
38.87
m
SDDS
UL
19.62
20
m
RL
19.01
1.28 m
32.32
7.55 m
DIMES
RL
42.06
12.01
332.80
12.72 m
RLNN
PRL
19.52
1.64 m
38.46
6.24 m
43.34
1.37 m
363.34
11.76m
SCO
19.29
2.71 m
11.26 m
42.18
1.45 m
365.37
1.10h
RLSA
19.97
35
40.19
1.85
44.10
20
375.31
1.66 m
FLD-IG
PRL
19.72
1.08
39.56
6.31
43.50
1.35 m
365.03
11.41
FLD-EG
H
20.02
38
40.25
1.93
44.37
19
377.50
1.12m
Derived via spectral expansion, the upper bound of mean escape time for L.D and FLD (42(
and Cv 4,, (B) Due the P2(B3) x exp(-AH] 88 [33 and (B. w [26]. as the potential barrier H increases linearly, the escape time of the LD increases exponentially. making it prone to becoming "trapped" at high potential barriers. In contrast, FLD-based SDE, the mean escape time is no longer governed exponentially by the barrier height Z but instead primarily influenced by the barrier width in polynomial manner. Consequently, in multiple-peal landscapes with high potential barriers, FLD-based sampling exhibits superior convergence properties compared to LD.
4.4 Enhanced Sampling- Sampling-Based Based Approach: FLD-EG
We aim to enhance campling-based approaches by introducing our FLD-EG (i.e., with explicit gradient). As discussed in Sec. 4.3 FLD exhibits a stronger ability to escape from local minima in multiple-peak and high-barrier CO landscapes compared to LD. Motivated by this, we employ FLD-based sampling to guide the assignment of variable values each iteration. To further enhance stability and reduce the impact of outlier samples that may hinder local exploration, we apply truncation scheme to remove extreme samples, as illustrated in Fig. 2b) This leads to a more stable and consistent sampling trajectory. Also, inspired by [17]. we update only the top-d variables that have the greatest influence on H (x) and determine the variable values based on the result of the sampling iteration. Specifically, truncated version of the drift term In4ic, (=) is applied, guided by top-d gradient indicator defined as Sigmoid(( + ((2x I)@ VH())), ((2x - 1 V
Similarly, the S&x noise is truncated based top-dnuise noise indicator: Sigmoid ((2r ④ (x)))) - ((2x- 1) @ V (d ). The final update rule is given in Eq. (19) Details on the algorithmic process can be found in Appendix [.I
Consistent with standard sampling-basee approaches, FLD-EG requires closed-form gradient the energy function for the CO problems it addresses. Case studies the energy functions of applied
CO problems are presented in Appendix C
4.5 Enhanced Data-Driven Approach: FLD-IG
Since the gradient (H()) is not available for all CO problems, we propose data-driven implicit- gradient FLD solver named FLD-IG. Inspired by (27] and [17], we introduce an NN-based framework whose training procedure resembles reinforcement learning. alternating between sampling and update steps (we denote this framework as PRL). We introduce the concept of flip probability for variables, as proposed by [17,, to mitigate numerical issues, and the network is designed to predict these flip probabilities. Additionally, SoS noise is incorporated into the flip decisions at each iteration. To match the FLD process, first apply linear transformation to rescale the noise from the range

---

Table 2: Results of compared methods for MaxCI and MaxCut problems.
MaxCI
RB-(200-300)
RB-(800-1200)
MaxCut
BA-(200-300]
BA-(800-1200)
Method
Type
Size
Time
Size f
Time 4
Method
Type
Size 1
Time !
Size 1
Time
Gurobi
OR
19.05
1.92
33.89
19.67 m
Gurobi
OR
730.87
8.50
2944.38
1.28h
ERDOES UL
12.02
4
25.43
2.27
ERDOES
UL
693.45
46s
2870.34
2.82
LTFT
UL
16.24
42s
31.42
4.83m
LTFT
UL
704.30
2.95
2864.61
21.33 m
DifUCO
UL
16.22
1.00 m
DIBUCO
UL
727.32
1.00 m
2947.53
3.78 m
SDDS
18.90
38
SDDS
UL
731.93
14s
2971.62
1.08
RLNN
PRL
18.13
1.36
35.23
7.83
RLNN
PRL
729.00
1.58
2907.18
3.67
Greedy
H
13.53
25
26.71
25
Greedy
H 688.31
13s
2786.00
3.12
MFA
H
14.82
27
27.94
2.32 m
MFA
H 704.03
1.60 m
2833.8G
7.27 m
ISCO
H
18.96
54s
40.35
11.37 m
iSCO
H 728.24
1.67 m
2919.97
4.18
RLSA
H
18.97
23
40.53
1.27
RLSA
H 733.54
27
2955.81
1.45
FLD-IG
PRL
18.52
1.40 m
37.40
6.89
FLD-IG FLD-EG
PRL
733.48
1.57 m
2922.54 2960.13
3.07
FLD-EG
H
18.97
s
40.63
1.91
H
734.18
25
1.70
[0, 1] to [-,, by multiplying 1 2x. The training loss function is defined as:
100 x, d, X) Eg (H +
Eoo(xi LiEV
(28)
where qo (Xa,n+1l xx) still satisfies the mean-field decomposition Eq. 10 Details the network architecture and the training and inference process can be found in Appendix D.2
Experiments
We evaluate our FLD-EG and FLD-IG three common CO problems, including maximum inde- pendent set (MIS), maximum clique (MaxCl) and max cut (MaxCut) problems. Furthermore, we demonstrate more analysis on the sampling trajectories and ablation studies.
Datasets. (1) MIS datasets: Following the benchmarks in [7.. we evaluate our algorithms on two Rényi (ER) random graphs [16] with node weight set to (2) Maximum Clique dataset: we use the single RB graph which is introduced in MIS datasets for the evaluation; (3) Max Cut dataset: we compare our algorithms with the baselines on the Barabási-Albert (BA) graphs B An additional point that warrants special attention is: The size of the training set and the validation set is separately 1000 and 500 graphs for all datasets except for ER-[9900. 11000] (that is, the ER graphs contain 9000 to 1 11000 nodes), and the test size 500 for RB and BA graphs; 128 for ER-[700-800) and 16 for ER-[9000, 11000].
graph classes: Revised Model B (RB) instances [66] and
Baselines. (1) Classical methods: we categorize them into two types: operation research (OR) methods; heuristic (H) methods. In the OR type, we give the general integer linear programming
representation of MIS, Maximum Clique, and Max Cut, solved by the Gurobi solver [22] as the OR
baseline; especially for MIS, we additionally give the MIS problem-specific solver KAMIS [19].
For the heuristic methods, we give two sampling methods iScO 51 and RLSA [17 with SA and discrete proposal of LD for all cases; additionally, the Greedy and MFA (Mean-Field Annealing) (6] methods are provided for Maximum Clique and Max Cut problems. (2) Learning- bbssd methods: we classify the baaning-based methods into four types: supervised learning (SL), unsupervised learning (UL), reinforcement learning (RL), and pseudo reinforcement learning (PRL) which uses the sample and update scheme similar to the RI. For SI., the INTEL with GCN and probability heatmap [3 DGL with Monte Carlo Tree Search and two GNN backbones 77]. and DIFUSCO with UNet-Style diffusion model (53) are given as SL basclines for the MIS problem. In the type of UL. the LIFT with GFlownets (68] DiffUCO with Utel-Style diffusion model 44. and SDDS with discrete presented for three case studies; beyond that, ERDOES with random graph model [16] is set for the case studies without the MIS problem. The RL methods, PPO with actor-and-crine [ and DIMES with reinforcement optimization combined with meta-learning [40), are introduced for the MIS problem. Similar to the FLD-IG, RLNN with the discrete proposal of LD the baseline method of the PRL for three case studies [17]
diffusion models 43
Main Results. the main experiments for the evaluation of our FLD-EG and FLD--G, we give two metrics: the objective value of each problem and the overall sequential testing time, which
8

---

a= 1.4
1.6
2-
2000
4000
10000
4000
6600
5000
10000
2.0
1.0
0..5
-1.0
2000
4000
6000
8000
10000
2000
4000
8000
8000
10000
(a) Typical trajectories for a 1.4, 1.6, 1.8, 2.0.
Without Truncation, = 1.4
15
10
Truncation, a
1.5
0.5
-0.5
-1.5
2000
4000
6000
5000
10000
(b) Trajectories w/ and w/o truncation for 1.4.
Figure 2: Sampling trajectories of the FLD-based SDE.
attracted the main concern in the field of CO. For three case studies in this work, the objective values separately represent the independent set size of MIS, the clique size of Maximum Clique, and the size of the Max Cut (the detailed formation can be seen in Appendix C). The reported results for each learning-basee based method correspond the longest runtimes and, accordingly, should also exhibit the highest objective values; with regard to heuristic methods, we fixed the number of iterations to be results on MIS, MaxCI and MaxCut. On most problems,
the same. Table [ and 2 demonstrate our FLD-EG and FLD-IG outperform the SOTA classical and learning-based methods, respectively, achieving higher objective values in shorter or comparable runtimes. For the classical methods, since OR methods can obtain the optimal solution given sufficient runtimes, report the results of

---

LD CD Noc
Guntaa Notec
LD Geastrr Kilwes Nr
dD Cauora Hote HRD Aarhee
BoiEarer
Thant Elanngy
Bes Eleage
Eppci
Spech
Epeck
Epads
(a) ER-17000-00).
(b) BA-1800-1220).
(c) BA-1200-300)
(d) RB-1200-300), MaxCI.
Figure 3: Ablation for our methods (FLD with Sa.) and LD sampling process method with Gaussian noise. The staircase curves show how the "Best Energy" evolves as the number of iterations ( ("epochs") " where the "Best Energy" is the minimum energy function value between last and current epoch.
OR methods solely to demonstrate the performance gap between the heuristic and learning- based methods relative to the optimum, rather than to make a direct comparison. In the competitive heuristic methods (i.e. iSCO, RLSA and our FLD-EG), our FL.D-EG can attain equal or superior objective values within the same sampling steps, while maintaining comparable or slightly reduced runtime. In methods, our FLDD-G achieves higher objective values than the others on 75% of datasets; among methods with comparable performance metrics, our FLD-IG achieves shorter runtimes on all datasets except the RB-[800- 1200] instance.
the field of learning-basse
Sampling Trajectories. We conduct FLD-based iterative sampling under different values of a to simulate the trajectory of a single variable during CO solving. Owing to the symmetry of the SaS, we shift and scale x from [0. 1] to [-1, 1] in our methods. As shown in Fig. 2a when a = 2 (i.c.. the process degenerates to LD sampling). z readily becomes trapped in local minima, leading to slow convergence; as a decreases intensifying the heavy tail of the SoS distribution-a2 r flips more frequently between- -1 and 1, promoting escape from local minima and accelerating convergence (theoretical justification is provided in Sec. [43). However, for very small a, the generation of large outliers can cause sampled points to deviate excessively, losing track of the underlying landscape. To remedy this, we introduce truncation strategy. As shown in Fig. [bb bounding the sampled points within a prescribed range yields a markedly more stable sampling process.
Ablation Studies. To rigorously validate the effectiveness of our SaS-noise sampling process, we conducted ablation studies comparing its convergence behavior against that of LD with Gaussian noise when solving CO problems (cf. Sec. 4.3) Specifically, in both FLD-EG and FLD-IG, we replaced the FLD sampling process driven by SaS noise with the LD sampling process driven by Gaussian noise, and designed comparative experiments to monitor the iterative descent of the energy function. As shown in Fig. 3 two panels on the left depict the ablation studies for FLD-EG, while the others depict the ablation studies for FLD-IG. Notably, since the optimal solution is not attained, there a gap between the best energy function value and the current objective value, which corresponds to the penalty term imposed by the constraints (i.e. Ab(x:) shown in Eq. (6). The results in the figure indicate that, whether using explicit gradient or implicit gradient, our method markedly outperforms LD with Gaussian noise; it not only demonstrates superior ability of FLD with SaS noise to escape local optima compared to LD, but also its capacity to converge to a lower energy function value.
Conclusion and Outlook
In this paper, we have addressed the limitations of L.D in CO, including its tendency to be trapped in local optima, slow convergence, and generally suboptimal iterative performance. To overcome these challenges, we propose a FLD sampling process driven by SaS noise, fortified with truncation strategy to ensure sampling stability. We theoretically prove that FLD achieves a polynomial mean escape mine-sinnificantly faster than the exponential escape time of LD, which depends on the energy barrier height -tterbyy enabling more rapid convergence. By integrating FLD into both -aased
sampling- based and data-driven frameworks, accommodating problems with or without explicit gradient information, we demonstrate its superior convergence and exploration capabilities on three case studies: MIS, MaxCI and MaxCut. Our FLD-EG and FLD-IG achieve SOTA or near-SOTA results compared to existing methods. Although our current FL.D design focuses on binary-variable CO problems, it has potential applicability to integer and aantinuous-variabie formulations. We plan to investigate these promising extensions in future work.
10

---

References
[1] Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum in- dependent sets. In International conference on machine learning, pages 134 PMLR, 2020.
[2] David Applebaum. Lévy processes and stochastic calculus. Cambridge university press, 2009.
[3] Álbert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-511 1999.
[4] Douglas Bauer, Frank Boesch, C Suffel, and Ralph Tindell. Combinatorial optimization problems the analysis and design of probabilistic networks. Networks, 15(2):257-271, 1985.
[5] Nils Berglund. Kramers' law: Validity, derivations and generalisations. arXiv preprint arXiv:1106.5799, 2011.
[6] Griff Bilbro, Reinhold Mann, Thomas Miller, Wesley Snyder, David van den Bout, and Mark White. Optimization by mean field annealing. Advances in neural information processing systems, 1, 1988.
[7] Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. arXiv preprint 2rXvv:2201.10494 2022.
[8] Anton Bovier, Michael Eckhoff, Véronique Gayrard, and Markus Klein. Metastability and low lying spectral in reversible markov chains. Communications in mathematical physics, 228:219-22 255, 2002.
[9] Cem Çelik and Melda Duman. Crank-nicolson method for the fractional diffusion equation with the riesz fractional derivative. Journal of computational physics, 177 2012.
[10] Vladimír Cerny. Thermodynamical approach the traveling salesman problem: An efficient simulation algorithm. Journal of optimization theory and applications, 45:41-51, 1985.
[11) Changyou Chen, David Carlson, Zhe Gan, Chunyuan L.i, and Lawrence Carin. Bridging the gap between stochastic gradient meme and stochastic optimization. Artificial Intelligence and Statistics, pages 1051-1060. PMLR, 2016.
[12] Mufa Chen and Fengyu Wang. Cheeger's inequalities for general symmetric forms and existence criteria for spectral gap. Chinese science bulletin, bulletin,33:151m 43:1516-1518, 1998.
[13] Emilio Nicola Maria Cirillo, Vanessa Jacquier, and Cristian Spitoni. Metastability of syn- chronous and asynchronous dynamics. Entropy, 24(4):450, 2022.
[14] KA Dowsland and JM Thompson. Simulated annealing. handbook of natural computing (pp. 1623-1655). Berlin: Springer. doi, 10:978-3,2011
[15] Jinqiao Duan. An introduction to stochastic dynamics, volume 51, Cambridge University Press, 2015.
[16] Paul Erdos, Alfréd Rényi, al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 5(1):17-60, 1960.
[17] Shengyu Feng and Yiming Yang. Regularized langevin dynamics for combinatorial optimization. arXiv preprint arXiv:2502.00277,, 2025.
[18) Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances neural information processing systems, 32, 2019.
[19] Ernestine GroBmann, Sebastian Lamm, Christian Schulz, and Darren Strash. Finding near- optimal weight independent sets at scale. Proceedings of the Genetic and Evolutionary Computation Conference, pages 293-302, 2023.

---

[20] Ziao Guo, Yang Li, Chang Liu, Wenli Ouyang, and Junchi Yan. Acm-milp: Adaptive constraint modification via grouping and selection for hardness- preesering milp instance generation. In Forty-first International Conference on Machine Learning, 2024.
[21] Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33:18087--8009 2020.
[22] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual. Gurobi Optimization, LLC, 2023.
[23] W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97-109 1970.
[24] Yixuan He, Quan Gan, David Wipf, Gesine D Reinert, Junchi Yan, and Mihai Cucuringu. Gnnrank: Learning global rankings from pairwise comparisons via directed graph neural networks. In international conference machine learning, pages 8581-8611 PMLR, 2022.
[25] Peter Inkeller and Ilya Pavlyukevich. First exit times of sdes driven by stable lévy processes. Stochastic Processes and their Applications, 116(4))111642, 2006.
[26] Milton Jara. Spectral gap inequality for long-range random walks. arXiv preprint arXiv: 12699, 2018.
[27] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs Advances in Neural Information Processing Systems, 33:6659-6672, 2020.
[28] Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario Vecchi. Optimization by simulated annealing. science, 220(4598):671 1-777118800 1-680, 1983.
[29] Gregory F Lawler and Alan D) Sokal. Bounds the 1 spectrum for markov chains and markov processes: a generalization of cheeger's inequality. Transactions of the American mathematical society, 309()):557-580, 1988.
[30] Yang Li, Lvda Chen, Haonan Wang, Runzhong Wang, and Junchi Yan. Generation as search operator for test-time scaling of diffusion- combinatorial optimization. In Advances in Neural Information Processing Systems, 2025.
[31] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36:50020-50040, 2023.
[32] Yang Li, Jinpei Guo, Runzhong Wang. Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion-based training-to-testinng solving for combinatorial optimization. Advances in Neural Information Processing Systems, 37:30179-30206, 2024.
[33] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
[34] Ziang Li, Mengda Yang, Yaxin Liu, Juan Wang, Hongxin Hu, Wenzhe Yi, and Xiaoyang Xu. Gan you see me? enhanced data reconstruction attacks against split inference. Advances in neural information processing systems, 36:54554-54566 2023.
[35] Ziang Li, Hongguang Zhang, Juan Wang, Meihui Chen, Hongxin Hu, Wenzhe Yi, Xiaoyang Xu, Mengda Yang, and Chenjun Ma. From head to tail: Efficient black- model inversion attack via long-tailed learning. In Proceedings of the Computer Vision and Pattern Recognition 2025.
Conference, pages
[36] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 1186):0087-102, 1953.
12

---

[37] Radford M Neal. Sampling from multimodal distributions using tempered transitions. Statisties and computing, 163.3-366, 1996.
[38] Manuel Duarte Ortigueira. Riesz potential operators and inverses via fractional centred deriva- tives. International Journal of Mathematics and Mathematical Sciences, 2006(1 10443911 2006.
[39] Aleksandar Pekeč and Michael H Rothkopf. Combinatorial auction design. Management science, 19:11)1485-- 2003.
[40] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35:25531-25544 2022.
[41] Gareth O Roberts and Osnat Stramer. Langevin diffusions and metropolis- algorithms. Methodology and computing in applied probability, 4:337-357, 2002.
[42] Gennady Samorodnitsky, Murad S Taqqu, and RW Linde. Stable non- non-gause con-gassiian random pro- cesses: stochastic models with infinite variance. Bulletin of the London Mathematical Society, 28((34):554- 555, 1996.
[43] Sebastian Sanokowski, Wilhelm Berghammer, Martin Ennemoser, Haoyu Peter Wang, Sepp Hochreiter, and Sebastian Lehner. Scalable discrete diffusion samplers: Combinatorial opti- mization and statistical physics. arXiv preprint 2rXivv2502.08696 2025.
[44] Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervised neural combinatorial optimization. arXiv preprint arXivv2406.01661, 2024.
[45] Abdelkader Sbihi and Richard W Eglese. Combinatorial optimization and green logistics. Annals of Operations Research, 175:159- 1171159911.7111 2010.
[46] Serap Ulusam Seçkiner and Mustafa Kurt. A simulated annealing approach to the solution of job rotation scheduling problems. Applied Mathematics and Computation, 188(1):31-44 2007.
[47] Umut Şimşekli. Fractional langevin monte carlo: Exploring lévy driven stochastic differential equations for markov chain monte carlo. In International Conference on Machine Learning. pages 2200-3209, PMLR, 2017.
[48] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5827-5837. PMLR, 2019.
[49] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and Computation, 82(1):93-133) 1989.
[50] Haoran Sun, Hanjun Dai, Wei Xia, and Arun Ramamurthy. Path auxiliary proposal for meme in discrete space. In International Conference on Learning Representations, 2021.
[51] Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale Schuurmans, and Hanjun Dai. Revisiting sampling for combinatorial optimization. In International Conference on Machine Learning. pages 32859-32874. PMLR, 2023.
[52] Haoran Sun, Etash K Guha, and Hanjun Dai. Annealed training for combinatorial optimization on graphs. arXiv preprint arXiv:2207.1 1552, 2022.
[53] Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in neural information processing systems, 36:3706-373,, 2023.
[54] Luke Tierney. Markov chains for exploring posterior distributions. the Annals of Statistics, pages 1701-1728, 1994.
[55] Peter JM Van Laarhoven, Emile HI. Aarts, Peter JM van Laarhoven, and Emile HI. Aarts. Simulated annealing. Springer, 1987.
13

---

[56] Haoyu Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta- learning. arXiv preprint arXiv:2301003/16 2023.
[57] Haoyu Peter Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. Advances in Neural Information Processing Systems, 35:31444-3 31458, 2022.
[58] Runzhong Wang. Ziao Guo, Shaofei Jiang, Xiaokang Yang, and Junchi Yan. Deep learning of partial graph matching via differentiable top-k. In Proceedings the IEEE/CVF conference computer vision and pattern recognition, pages 6272-6281, 2023.
[59] Shiyue Wang, Haozheng Xu, Yuhan Zhang, Jingran Lin, Changhong Lu, Xiangfeng Wang, and Wenhao Li. Where paths collide: comprehensive survey of classic and learning-based multi-agent pathfinding. arXiv preprint arXiv:2505. 19219, 2025.
[60] Yibin Wang, Zhimin Li, Yuhang Zang, Chunyu Wang, Qinglin Lu, Cheng Jin, and Jiaqi Wang. Unified multimodal chain-of-thouge reward model through reinforcement fine-tuning. arXiv preprint ArOiv:2505.0m 033318, 2025.
[61] Yibin Wang. Zhimin Li, Yuhang Zang, Yujie Zhou, Jiazi Bu, Chunyu Wang, Qinglin Lu, Cheng Jin, and Jiaqi Wang. Pref-grpo: Pairwise preference reward-based grpo for stable text-to-image reinforcement learning. arXiv preprint arXiv:2508.2077 2025.
[62] Yibin Wang, Yuhang Zang, Hao Li, Cheng Jin, and Jiaqi Wang. Unified reward model for multimodal understanding and generation. arXiv preprint arXiv:2503.052... 2025.
[63] Ronald L Wasserstein. Monte carlo methods, volume 1: Basics, 1989.
[64] Rafal Weron. On the chambers-mallows-Sung sttuk method for simulating skewed stable random variables. Statistics probability letters, 28(2):155-71,, 1996.
[65] DF Wong. Hon Wai Leong, and HW Liu. Simulated annealing for VLSI design, volume 42. Springer Science & Business Media, 2012.
[66] Ke Xu and Wei Li. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12:93-103, 2000.
[67] Nanyang Ye and Zhanxing Zhu. Stochastic fractional hamiltonian monte carlo. In IJCAI, pages 3019 3025, 2018.
[68] Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems, 36: 11111195211999 1996,, 2023.
[69] Ruqi Zhang, Xingchao Liu, and Qiang Liu. A langevin-like sampler for discrete distributions. In International Conference Machine Learning, pages 26375-26338 PMLR, 2022.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims are supported by theoretical proof in Sec. 4.3 and empirical results in Sec.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in the last part of the main paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
Critical theoretical proof can be found in Appendix A and B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All experimental settings included in Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification:
We will release the complete source code once the paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/twpsscccppbll//guuiii / Soaileesss/oSSSeeiiiseeeee
wwt.SSubmisioooooiiooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental settings are included in Sec. Appendix E.2 hyperparameter values.
presents
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The test set size is appropriate to demonstrate the statistical significance of the experiments, consistent with previous works.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Included in Appendix F.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: have read the NeurlPS Code of Ethics and am sure that our work fully adheres to its guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Discussed Appendix Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All models, data, and code used in this work properly cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The documentation is attached to our complete source code and will be released once the paper is accepted.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
20

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The LLM was used solely for grammar checking in this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy http:a/s/eaaarppsscc/o/oootteees for what should or should not be described.
21

---

A Proof of Theorem 1
Theorem 4
47
Consider the SDE (3) the drift b is defined by:
b(a,a) (x)=)
(29)
fx(x) = (zx)) ( and a an invariant measure of the Markov process.
Theorem 5 (138)) The Riesz derivative D of a function f(x can be defined the limit of the fractional centered difference operator D given;
D fi)(()
lim (7f((z) h-0
(30)
where,
O A7f(2) = (1/10)
Σ
g -ki)
(31)
k=-00
and
1
97,k (-1)*
(32)
11/22-k
Proof. Theorem guarantees the existence of equality on the left-hand side of Eq 1q.13
Next, we will give the proof of the right-hand side. The more computationally efficient variant of the first numerical scheme presented in Theorem 5|ss given as follows (
D fm (x) (z)
(33)
where 04.0 - 1)/T(//2 1)2 for E ER.
Then we get
Da- Sp, (x)
Da- (-0()))),, Ds(=2s())
b(x,a)
((x)
((x)
N(a 1)/T(a/2)) = (2)
(34)
where Ca =[(a-1)/T(a/2)
L
B Proof of Theorem 2 and Theorem
3
Definition
random variable is a-stable if and only if its charucteristic function is given
by
- (1 exp( - iBgsign(()) x K(a)} + ipt, a + 1
2
log (())
(35)
- 021 + i,gsiggn(t log [t|) + ipt, a
where, K(a)= a sign(1 a)), and sign(.) denotes the sign function. The parameters d2 and 32 are related to and B.
Case 1: for + 1, $2 is such that
tan B2 7 K(aa)
Ta
3 tan
(36)
2
2
and the new scale parameter
02 = o (1 (1+ 32 tan
no 2
(37)
Case 2: for a 83 and 02 20.
Lemma
(64) X is (1, 0) random variable if and only ffr > 0:
P(0< xxx -
exp --- Ua(7,70)
dr; <
(38)
P(X 2 x)
- Ual2 20) exp
dr a>
where, To
<3B((a
and U, (7,77770)
ssn (sin (cos
a/l cos(7-a
2a
cos 7
22

---

Proof. When > Yo then the right hand side of Eq. 17 (a & 1) is positive and can be expressed
as 66
((1))
a
(1-a)/a
(39)
W
where
a(7) (sin(a(y-77) -00) a/(l-a) cos(7 - a(7 10)
(40)
cos
Co8 y
Case 1: When 0 1, Eq.
17 (a # 1) implies that X 0 if and only if > Yo- Since
1-a > O, we can write
P(O < σt) = P(0 x sx, 22,,,,2 7> 70)
P(o < (a(7)/ (1 (1-a)/a 1x, 7> 70)
P(W 2 - a(7), y>1 70)
E, exp( -1 0 a(7)) 1 [
1 T/2
exp(-xx/(001) a(7)) dy.
π 70
From Lemma ! we conclude that X Sa,,, 0).
Case 2: For < a < 2, noting that a-1 > 0, we similarly deduce that for all x > 0,
P(X 2 2) = P(x 2 0, 7 70)
= -P((a(>)/11) (1 (1-a)/a 22, 7> 10) 7>10)
=P((W/((7)) (0- 13/a 2x, 7 > 70)
P(W 2 -a/(a- a(7); 7> 70)
Ey oxpp - x 2a/1a-11 (1-1) a(7)) 1 [
1
exp aap(-x0/le / 1) a(7)) d7.
Again by Lemma D we get X (1, 0).
Case 3: For the case a = 1, when Bng = 0 the right hand side of Eq. 17) (a = 1) simplifies to
tan 7, which has Cauchy law (ef. Eq. 35 If B2 f can instead be written
a1 a1(7)
B2 log
(41)
W
where
2 + 827
a1 (7)
exp
B2 (5 + B27) tan?).
(42)
COS 7
For B2 > 0, we have
P(X S xx) P(3 log (11 (7)/W) x)
P(W 2 e -0/00 01 (1))
= EE, [e,((xepee 1-----1180 2/83 a1 (7))
1 /m/ exp(-e =/ a (7:) d7.
-
Finally, we conclude that for all 82, X (1,
Due to the SaS distribution being the special case of a--taale distribution when / 0, thus Theorem 2 and Theorem 3 have been proven together.
D
23

---

C Case Study on Energy Functions
The problem formulations utilized in this paper are given below for three common case studies with closed form of the energy function (x)), which means (xx) is first-order derivable. Let G(V, E) be an undirected and unweighted graph, where V {1, ... N) denotes the node set of the graph G and E _ V gradient are given.
represents edge set. The problem descriptions, energy function, and its
Case Study 1: Maximum Independent Set (MIS). The independent set satisfied that Vi,j
S S V and j(i.j) E E, then i j. Thus the definition of MIS S arg maxsçv |S| () denotes the size of -). The formulation MIS is:
max (0,1)
Σ
C S.L.
Σ
Ie = 0
(43)
IN
SEV
e(t,))
The energy function of MIS formed Eq. (6 is:
2 - x X Ax
H(x)= = E
+
Σ e(G,)EE
xxx+xxxx
(44)
iEV
where (i E V) denotes the node weights of graph G and the content to the right of the last equal sign the energy function under the matrix form representation (the same goes for the following two cases). The gradient of the energy function can be presented readily:
VH(x) = c AAx
(45)
Case Study 2: Maximum Clique. The clique is the set C' C V satisfied that Vi,j E C, i i j. then e(i, E. Therefore, the definition of maximum clique C* arg maxsgv |C]. The formulation of maximum clique is:
max JE (0.1)*
Catli S.t.
Σ
Iy = 0
(46)
N
SV
c(F))EE
The energy function of maximum clique formed as Eq.
66 is:
X ((1 x)² [1)x)
H(x)
Σ CH A
Σ
JaTyy c x
-x=xxxxxXx Ax)
(47)
2
c(i.))E
The gradient of (x) is shown as:
VH(x)= - x(11x)x1
x)1 1)1-3 - x Ax)
(48)
Case Study 3: Max Cut. The max problem seeks partition (S, S) that maximizes the number of crossing edges:
max (e(i.)) E Eli e S.j e 5= SCV
(49)
The mathematical formulation, energy function, and its gradient can be presented as:
1 (2x; - 1)(2x, -1)
max =E(0,1JM
Σ
(50)
e(i.)EE
1- (2x; - 1)(2x, 1)
H(x)= = Σ
x TA Ax
(51)
2
e((J)EE
VH(2) = A(2x-1 1)
(52)
24

---

D Details on FLD-EG and FLD-IG
D.1 Algorithmic Process of FLD-EG
We now present the detailed implementation of the FLD-EG algorithm in Alg. The algorithm takes input the maximum number of iterations T, the number K of independent SA processes, the truncation parameter d for the closed-form gradient H. the truncation parameter duoise for the Sa8 noise, the initial temperature To for SA, the stability parameter a of the FLD sampling process, and the stepsize schedule parameters an and by. (For the specific values of these hyperparameters, see Appendix
The FLD-EG EG algorithm employs a near- couticontuuuuus sampling procedure to guide the assignment of binary variables. First, both the binary variable vector and the auxiliary continuous variable vector are initialized, and the initial energy is computed via the problem-spes sppecifi-piiicc function energy_ f__nc([n_. Each iteration then comprises two stages: (1) sampling update for h, and (2) update for based on the newly sampled h. After each update of x, we record the best observed energy. Once the maximum iteration count 7 is reached, greedy decoding step produces final, constraint-satisfinng solution.
The sampling update for h consists of four substeps:
1. Noise sampling. Sample the noise variable = =_iter from an Sao(1) distribution as pre- scribed by Theorem 3 with the sampling mechanism defined in Eq. (8). In practice, for convenience, we replace exponentially distributed sampling with uniformly distributed sampling for U.
2. Gradient truncation. Apply the Top-d truncated indicator to VHI ensuring that only the components with the largest magnitude influence the update.
3. Noise truncation. Apply the Top-dhoise truncated indicator to the sampled noise vector, truncating extreme values to stabilize the sampling process.
4. State update. Update h according to the FL.D update rule in Eq. 19
Finally, since the solution may still violate some problem constraints, perform greedy decoding step on x until all constraints are satisfied.
D.2 Details on FLD-IG
Training and Inference Process. In Alg. 2 we present the detailed training procedure for FLD-IG. The algorithm takes as input the maximum number of iterations T for training and for inference, the number of independent parallel sampling processes K' for training and K for inference, the truncation parameter for both the gradient and the SaS noise, the initial temperature To for the sampling process, and the stability parameter of the FLD sampling process. (For the specific values of these hyperparameters, see Appendix E.2 At each iteration, we sample SaS noise and incorporate it into the proposal distribution, allowing x' to be drawn from this voise-augmented proposal so as to compute flip probabilities and update x. Unlike FLD-EG, which applies truncation to both the gradient and the noise terms during sampling, and given that the noise samples independent at each iteration and no closed-form formulation exists for the energy- function gradient, instead perform unified truncation of the ausseeeeg proposal distribution directly within the loss function. After each update, we record the best-observed energy. Once the maximum training iteration step 7" is reached, save the best parameters for the inference process.
Similar to the training process, we first sample the SaS noise and incorporate it into the proposal distribution in the inference process. Next, we draw x' by sampling from this augmented proposal distribution to compute flip probabilities for updating x', and we record the best energy observed after each update. Once the maximum inference iteration count T' is reached, a final greedy decoding step generates a constraint satiiiiiiniiiiiigggggn solution which is similar to the greedy decoding step of FLD-EG.
Network Architecture. For the implementation of the network architecture, we adopt five-layer GCN with 128 hidden dimensions, which is consistent with [17.. We observe that our FLD-IG converges faster than 17.. Therefore, we set the number of training epochs to 30, which is adequate for convergence.
25

---

Algorithm FLD-EG
Require: T, K, d, dnoises TO, a, Oxp and by-
1: Initialize x E {0, 1] hxx;; x + x; Ca = -
2: Build adjacency matrix A from redge_index, edge_weight) True)
3: (energy, VH) t Envergyffun(AA_
4: best_sol t x; best_energy energy
5: for = 1, ... do
6: T T
T
7: for 1,2, ...
N do 8: Sample W 10--1-2:3 2),
U ~ 1(0,1)
sin sin(aW)
cos((1 - W)
1=0
9:
2_ s_tee-
D SaS Noise Sampling
cos (os by
- InU
an
17 t 1
11:
l f kthvalue ((2x 1) ① VH1
(1)* d, dim = 0)
> Top-d Truncated Indicator
Pg + Sigmoid (C} ((2x- - 3 VH),
1g)/7)
13:
Sample I Bernoulli(pg) -kthvalue( 1 (2x 3 VHI (i)* dnoise dim 0)
14:
Top-dnoise Truncated
Indicator
15:
+ Sigmoid( ( 12x -
@ VH (3) - t2)/T)
Sample I ~ Bernoulli(p:)
grad_ites + 17 Co (-+) VH
18:
-ilerr + 11 z_iler
h4 t h4 Ig Q grad iter + Ig @ x iter
Sampling Iterative Process
20:
h4 + Clamp 0,
21:
0; e where(rand() < h;, 0, 1)
end for
23:
(energy, VHI + energy energy_funce (, b, x, epoch < T)
24: if energy best_energy then
25:
best sol t x; best jest_energy-s +- energy
end if
27: end for
return best sol
(or return min _ if skip-decode)
E Details on Experiments
E.1 Hardware and Software Devices
Experiments are conducted on a Linux workstation using an H100 GPU and an Intel(R) Xeon(R) Platinum 8468 CPU, with programs implemented in PyTorch.
E.2 Hyperparameters
We show the utilized hyperparameter values of FLD-EG and FLD-IG in Table and Table respectively, The selection of perparaameter values partly refers to [17
F Broader Impacts
The FLD framework we introduce has the potential to substantially advance both the practical application and theoretical understanding of CO. By enabling reliable escape from deep local optima-and and doing so in polynomial time across range of problem landscapes- FL.D can drive more efficient logistic networks, reducing transportation costs and carbon emissions through better routing: streamline scheduling in manufacturing and cloud computing, leading higher resource utilization
26

---

Algorithm 2 FLD-IG (Training)
Require: T", K", d, X, TO Initialize 0
2: while stopping criterion not met do
3: Initialize x E {0,1) 1
+ {a}
4: for 1,2, T do
5: T + To 7"
6: Sample W (e)
L...
U 1 7), i= N
7: Sample U iid
u(0.1), 1), i= 1=1...,, N
8: Compute
sin(a (a))
[cos(( a In (()
cos( (os(W()))))))
D SaS Noise Sampling
9:
x' (x x TZ -xx))
Sample from proposal distribution with Sa Noise
10:
D DU
11:
x --xx x
12:
end for
13:
O a min EzED (4
14:
end while
15:
16:
return
Table 3: Hyperparameters used by FLD-EG on all datasets.
Problem
Dataset
To
T
dnoise
a
Qg
by
RB-[[200-300]
0.01
200
300
1.02
9
1.2
0.6
RB-[800-1200]
0.01
200
500
1.02
12
1.3
0.1
0.6
MIS
ER-[700-800]
0.01
20
200
500
1.001
20
1.5
0.1
0.6
ER-[9000-1100)
0.01
20
200
5000
1.001
60
1.1
0.1
0.6
RB-[200-300]
200
100
1.02
4
0.6
MaxCI
RB-[800-1200]
4
2
200
500
1.02
2
1.7
0.1
0.6
BA-1200-300)
5
20
200
200
1.02
33
1.01
200
0.6
MaxCut
BA-[800-1200]
5
20
200
500
1.02
35
1.01
200
0.6
Table 4: Hyperparameters used by FLD-IG on all datasets.
Problem Dataset
d
K
T
X
K'
T
X
RBB-1200-300]
0.25
5
20
100
1.02
10
50
0.5
1.7
RB-[800-1200]
0.25
5
20
200
1.02
10
300
0.5
1.7
MIS
ER-[700-800]
0.6
20
20
200
1.001
10
500
0.5
1.7
ER-19000-1100)
0.9
20
20
800
1.001
1.7
RB-1200-300]
0.25
2
20
100
1.02
10
100
0.5
1.7
MaxCI
RB-[800-1200]
0.25
2
20
200
1.02
300
0.5
1.7
BA-[200-300]
0.25
20
20
100
1.02
10
50
0.5
1.7
MaxCut
BA-[800-1200]
0.25
20
20
200
1.02
10
300
0.5
1.7
and energy savings; and enhance network-design and finacial-optimizztionn tools, yielding more robust communication infrastructures and investment strategies. Moreover, because FLDD naturally integrates with data-driven pipelines via its implicit-gradien formulation, it can be seamlessly
27

---

incorporated into emerging machine-learee learning platforms for applications such automated materials discovery, bioinformatics, and large-scale resource allocation, fostering interdisciplinary innovation.
At the same time, we acknowledge that any powerful optimization technology carries risks. Unchecked, FLD could be used to accelerate adversarial planning- in cyhersecurity, market manipulation, or autonomous weaponry-by quickly finding worst-case configurations. To mitigate misuse, recommend that practitioners pair FLD with domain-specific ethical guidelines and transparency mechanisms (e.g.. logging and audit trails for critical decision systems), and that the research community pursue formal verification methods to ensure that FLD-based solutions adhere to safety and fairness constraints. By proactively addressing these considerations, we believe FLD can serve as force for positive impact-improvine improving efficiency and sustainability in industrial and scientific upplications while minimizing potential harms.
28


Reviews:
[{"review_id": "hG98gZFlHz", "reviewer": "Reviewer_MK47", "summary": "The paper proposes a novel sampling technique based on fractional Langevin dynamics and incorporates it into a method for solving combinatorial optimization problems with binary variables and equality constraints. The key feature of this new sampling strategy is its ability to escape narrow local minima more quickly and better handle the challenging landscape of the objective function. The main math tool to develop such sampling is $\\alpha$-stable Levy noise, which replaces Gaussian noise in the classical Langevin dynamics. The authors theoretically show the polynomial time for escaping local minima, which is the solid basis for the presented approach. In experiments, the study demonstrates a better trade-off between the maximum values of objective functions and runtime compared to many competitors. The authors select MaxCut, MaxClique, and Maximum Independent Set problems as the benchmarks for testing the presented approach.", "questions": "1. Why Eq. (6) uses $+ \\lambda b(x)$. and not $ + \\lambda b^2(x)$ ? A large negative $b(x)$ leads to a small value of $H$, but it violates the constraint in the initial problem.\n2. In line 207, the authors first mention 'gradient' in the context of sampling and do not provide any clarification of what this term means. Please add necessary remarks about what gradient is used and why it is \"explicit.\"? Is it possible to use \"implicit gradient\"? I find this term in the next section; however, its meaning remains unclear to me.\n3. What is the effect of the truncation parameters $d, d_{noise}$ and $\\lambda$ in Eq. (29)?\n4. What $\\alpha$ is used in the ablation study for FLD?\n5. What is $d$ in Eq. (29)?\n6. Could the authors please perform an additional experiment on the toy problem to illustrate the feature of the fractional Langevin dynamics to escape from the narrow local minima faster than the classical Langevin dynamics? I think such a simple benchmark will not require too much space, but will serve as a bridge between advanced theory and challenging benchmark problems.", "limitations": "A limitation on the binary variables is mentioned in the conclusion section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strenghts\n1. The paper is mostly well-written, and the authors' motivation for developing a better sampling strategy is clear.\n2. The experimental evaluation looks convincing and promising since the proposed approach outperforms many learning-based competitors and the standard OR tool Gurobi.\n3. The theoretical introduction clearly explains the basic concepts and describes key advanced concepts, such as the symmetric $\\alpha$-stable distribution.  \n\nWeaknesses\n1. The description of the FLD-IG and FLD-EG methods is too brief. Since they build upon the central theoretical framework presented in the paper, a clearer exposition of these methods would strengthen the paper's impact. \n2. I do not find the explicit statement about the overall pipeline complexity and memory consumption. Is the total runtime smaller due to the smaller number of iterations or the lower cost of a single iteration?\n3. The authors compare the developed schemes with learning-based methods; however, it is unclear to me whether the proposed methods have a training stage. If yes, then how long is this stage? Is it included in the runtime comparison in Tables 1 and 2?", "was_revised": true, "final_justification": "The paper proposes a motivated modification to the noise distribution used in the sampling process for solving the combinatorial optimization problem. The study includes both solid theoretical analysis and convincing experimental evaluation of the suggested approach. The authors address my concerns in rebuttal, so I maintain my score and lean towards acceptance of this work.", "rebuttal": "We sincerely appreciate the effort you put into reviewing our paper. Below, we provide our responses to the weaknesses and questions you raised.\n\n> **W1: The description of the FLD-IG and FLD-EG methods is too brief.**\n\nWe sincerely apologize for not providing a detailed description of FLD-IG and FLD-EG in the main paper. Due to space limitation, we included the specific method details and pseudocode **in Appendix E**. However, we would like to provide a more detailed explanation of the FLD-IG and FLD-EG methods here:\n\nBased on the differentiability of the energy function, we divide the FLD-based approach to solving CO problems into explicit gradient (FLD-EG) and implicit gradient (FLD-IG) methods. For FLD-EG, we provide a recursive expression with gradient and noise truncation, where a multi-step sampling and recursion approach can approximate the optimal solution. For FLD-IG, when the energy function is not differentiable, we introduce an NN-based framework whose training procedure resembles reinforcement learning, alternating between sampling and update steps, and using auto-grad to approximate the gradient of the energy function.\n\nWe will include this detailed explanation of the FLD-IG and FLD-EG methods in the final version of our paper.\n\n> **W2: Not find the explicit statement about the overall pipeline complexity and memory consumption.**\n\nWe sincerely apologize for not providing the complexity and memory consumption of the method pipeline in the main paper. Compared with the RLSA and RLNN methods, the complexity in the single-step sampling phase of FLD-IG and FLD-EG is similar. However, due to the stronger escape ability of FLD with symmetric $\\alpha$-stable noise compared to LD with Gaussian noise, the FLD-IG and FLD-EG methods have fewer iteration steps. In contrast to other learning-based methods, FLD-IG and FLD-EG only involve sampling and updating steps, resulting in a lower cost in a single iteration.\n\nThe memory consumption is summarized in the table below:\n\n|        | MIS-RB-[200–300] | MaxCl-RB-[200–300] | MaxCut-BA-[200-300] |\n| ------ | ---------------- | ------------------ | ------------------- |\n| FLD-EG | 1576.96MB        | 1413.12MB          | 1372.16MB           |\n| FLD-IG | 1761.28MB        | 1536.00MB          | 1556.48MB           |\n\nHere, we report only a single result for each case; in the final version of our paper, we will include the complete set of experimental results.\n\n> **W3: Does the proposed methods have a training stage?**\n\nThe FLD-EG method is a training-free method, while the FLD-IG method involves a training stage. The time consumption is shown in the table below. In Tables 1 and 2, the runtime includes only the model inference time and does not account for the time spent in the training stage. However, the training stage does not take very long time, and for each problem, the training stage will be carried out only once.\n\n|        | MIS-RB-[200–300] | MaxCl-RB-[200–300] | MaxCut-BA-[200-300] |\n| ------ | ---------------- | ------------------ | ------------------- |\n| FLD-IG | 4.65h            | 7.83h              | 4.72h               |\n\nHere, we report only a single result for each case; in the final version of our paper, we will include the complete set of experimental results.\n\n**To Q1**: We sincerely apologize for any confusion caused by the phrasing in our paper. Equation (6) represents the Lagrangian function, not a pure penalty function. This linear term naturally arises from the dualized constraints in dual theory, ensuring that when the KKT conditions are satisfied, the primal and dual problems are equivalent (strong duality holds for convex problems).\n\n**To Q2**: In Equation (20), during the discrete sampling process, there is the gradient of the energy function. If the energy function is differentiable, the explicit gradient can be directly incorporated into the recursive expression, and the optimal solution is approximated through iterative updates in the sampling steps. This is referred to as FLD-EG. If the energy function is non-differentiable, the gradient of the energy function is implicitly approximated using auto-grad, which is referred to as FLD-IG.\n\n**To Q3&Q5**:  The truncation parameter $d$ is applied for both the gradient and the $\\mathcal{S}\\alpha \\mathcal{S}$ noise in the Equation (29). We apply the Top-$d$ truncated indicator to $\\nabla H$, ensuring that only the $d$ components with the largest magnitude influence the update and apply the Top-$d_{\\mathrm{noise}}$ truncated indicator to the sampled noise vector, truncating extreme values to stabilize the sampling process. The second term in the Equation (29) regularizes the expected Hamming distance between the two solutions, with $\\lambda'$ being the regularization coefficient.\n\n**To Q4**: The value of $\\alpha$ in the ablation study is consistent with the one presented in Table 3 and Table 4.\n\n**To Q6**: We sincerely appreciate your valuable suggestions. In the ablation study, we explored the use of \"fractional Langevin dynamics to escape from the narrow local minima faster than the classical Langevin dynamics.\" Below, we present specific data to demonstrate the escape ability of FLD.\n\nAs external links aren’t permitted in the rebuttal phase, we’re unable to include images here. Instead, we provide a textual description below to address your question: For the MIS problem on an ER‑[700–800] instance, LD required 50 steps to reach the Best Energy of –39, whereas FLD did so in just 16 steps. To attain the Best Energy of –41, LD needed 210 steps, compared to only 100 steps for FLD. Likewise, on a BA‑[200–300] instance of the MaxCut problem, LD took 32 steps to reach –800, while FLD achieved the same in just 8 steps.\n\n**To Paper Formatting Concerns**: Thanks for your kind suggestion. We have rewrite the sentence in lines 190-193: \"Similarly, we provide the discrete proposal for the escape time of both LD and FLD. We state upfront that the Markov chains of LD and FLD are reversible if they satisfy the detailed balance conditions. Additionally, $p_{\\tau}(x)$ is a positive stationary distribution, given that the symmetric proposal and the Metropolis-Hastings acceptance criterion are satisfied for constructing discrete LD and FLD.\"\n\nWe sincerely hope that our response provides you with a clearer and more thorough understanding of our work. If you have any additional questions, please don't hesitate to reach out. We would be more than happy to address any concerns."}, {"review_id": "2C7XqrMQG7", "reviewer": "Reviewer_YtYc", "summary": "This paper addresses a known limitation of the application of Langevin dynamics (LD) for Combinatorial Optimization (CO) : its poor ability to escape local optima, especially in rugged landscapes. To that end, they propose replacing the Gaussian noise with \\alpha-stable Lévy noise, introducing the Fractional Langevin Dynamics framework (FLD). This approach allows occasional large steps (Lévy flights) to escape local minima and provide a better coverage of the solution space. Authors compare the upper bounds of mean escape time and show that this quantity scales in polynomial time with FLD, an improvement over the exponential bound provided by LD.  Authors then show how to derive from FLD a sampling method, where stability is dealt with using a truncation scheme and a data-driven method based on [Feng and Yang, 2025]. Performance of the method is evaluated on 3 common CO problems, showing SOTA results in most applications. Impact of the \\alpha parameter is also investigated.", "questions": "See weaknesses", "limitations": "Authors have adequately addressed the limitations of their work, claims are theoretically justified and experiments are fair", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n    - The paper is mostly clear and well written\n    - Replacing Gaussian noise with \\alpha-stable Lévy noise is sound and is well justified\n    - Claims are theoreticvally and empirically justified, showing an clear improvement over SOTA\n    - Experiments are clean with a high number of baselines and it is appreciated that running time are provided.\n\nWeaknesses:\n    - Authors do not dive deep into the truncation strategy introduced to improve stability for low \\alpha. Does it potentially introduce a bias? Is it difficult to tune? \n    - Could authors add variance accross runs to ensure consistency?\n    - Is the idea of replacing the Gaussian noise with \\alpha-stable Lévy noise in LD novel? Has it been already done in adjacent fields? More generally, variants of LD could have been explored in the related work. \n    - Section 3.5 is unclear to me. Could the authors provide more details in the main paper to clarify it ? Especially regarding the PRL procedure", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the effort you put into reviewing our paper. Below, we provide our responses to the weaknesses and questions you raised.\n\n> **W1: Authors do not dive deep into the truncation strategy introduced to improve stability for low $\\alpha$.**\n\nWe sincerely apologize for the lack of clarity in our description, which may have caused confusion. Since we initially applied our method to 0-1 integer programming problems, for problems where the values are limited to 0 and 1, large outliers can cause the solution to remain stuck at 0 or 1, which goes against our intention of using noise to facilitate escaping from local minima. Therefore, applying reasonable truncation to the outliers allows the iteration process to more easily escape from local optima. We also show in the table below that $d_{\\mathrm{noise}}$ is easy to tune, and slight perturbations to $d_{\\mathrm{noise}}$ do not significantly affect the performance.\n\n| $d_{\\mathrm{noise}}$ | Problem             | Size   |\n| --------- | ------------------- | ------ |\n| 20        | MIS-ER-[700–800]    | 44.37  |\n| 30        | MIS-ER-[700–800]    | 44.34  |\n| 40        | MIS-ER-[700–800]    | 44.35  |\n| 2         | MaxCl-RB-[200–300]  | 18.96  |\n| 4         | MaxCl-RB-[200–300]  | 18.97  |\n| 6         | MaxCl-RB-[200–300]  | 18.97  |\n| 20        | MaxCut-BA-[200–300] | 734.06 |\n| 30        | MaxCut-BA-[200–300] | 734.13 |\n| 40        | MaxCut-BA-[200–300] | 734.16 |\n\n> **W2: Could authors add variance accross runs to ensure consistency?**\n\nWe sincerely apologize for not including the variance of the datasets in the paper to ensure consistency. We evaluate the variance of FLD-EG by using different seeds for 10 repeated experiments, and the results are reported below:\n\n| Problem              | Size         |\n| -------------------- | ------------ |\n| MIS-RB-[200–300]     | 20.02±0.03   |\n| MIS-RB-[800–1200]    | 40.24±0.04   |\n| MIS-ER-[700–800]     | 44.34±0.09   |\n| MIS-ER-[9000–11000]  | 377.28±1.07  |\n| MaxCl-RB-[200–300]   | 18.97±0.01   |\n| MaxCl-RB-[800–1200]  | 40.61±0.06   |\n| MaxCut-BA-[200–300]  | 734.09±0.25  |\n| MaxCut-BA-[800–1200] | 2960.06±1.68 |\n\nWe will include the variance for all results of our methods in the final version of our paper.\n\n> **W3: Is the idea novel? Has it been already done in adjacent fields?**\n\nThank you for your question. We sincerely acknowledge that replacing Gaussian noise with $\\alpha$-stable L\\'evy noise is not an entirely new strategy. However, it has not been explored in the field of CO problems. We recognized the potential of $\\alpha$-stable L\\'evy noise in CO problems and have made preliminary attempts. Moving forward, we plan to extend these experiments to more complex problems. We apologize for not providing a detailed discussion of the application of FLD in other fields due to space limitations. We will include a more comprehensive review of the related work in the final version of our paper.\n\n> **W4: Section 3.5 is unclear to me. Could the authors provide more details in the main paper to clarify it ?**\n\nWe sincerely apologize for not providing a detailed description of FLD-IG in the main paper. Due to space limit, we included the specific method details and pseudocode **in Appendix E.2**. However, we would like to provide a more detailed explanation of the FLD-IG methods here:\n\nBased on the differentiability of the energy function, we divide the FLD-based approach to solving CO problems into explicit gradient (FLD-EG) method in Section 3.4 and implicit gradient (FLD-IG) method in Section 3.5. In Section 3.5, when the energy function is not differentiable, we introduce an NN-based framework whose training procedure resembles reinforcement learning, alternating between sampling and update steps, and using auto-grad to approximate the gradient of the energy function. \n\nWe sincerely hope that our response provides you with a clearer and more thorough understanding of our work. If you have any additional questions, please don't hesitate to reach out. We would be more than happy to address any concerns."}, {"review_id": "FgqP336Vgz", "reviewer": "Reviewer_ymVV", "summary": "This paper introduces ​​Fractional Langevin Dynamics (FLD)​​ to address key limitations of traditional Langevin Dynamics (LD) in combinatorial optimization (CO). LD's reliance on Gaussian noise hinders its ability to escape deep local optima, requires expensive parallel chains, and struggles with rugged landscapes or strict constraints. FLD replaces Gaussian noise with ​​α-stable Lévy noise​​, enabling long jumps that facilitate escape from local minima. Theoretically, FLD achieves a ​​polynomial escape time​​ from local optima, outperforming LD's exponential escape time dependent on barrier height. FLD generalizes LD and adapts to diverse CO scenarios via α-tuning. The authors develop explicit-gradient (FLD-EG) and implicit-gradient/data-driven (FLD-IG) variants. Experiments on Maximum Independent Set, Maximum Clique, and Maximum Cut problems demonstrate that FLD advances both sampling-based and data-driven approaches, achieving ​​state-of-the-art performance​​ in most cases.", "questions": "See above.", "limitations": "See above.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n+ The paper provides rigorous analysis showing FLD achieves polynomial escape times (vs. LD's exponential dependence on barrier height) and generalizes LD (recovering it when α=2).\n\n+ The work develops both explicit-gradient (FLD-EG) and implicit-gradient/data-driven (FLD-IG) variants, broadening applicability to problems with/without closed-form gradients.\n\nWeaknesses:\n\n- The energy functions of the proposed method use simple penalty terms (Eq. 6); complex constraints (e.g., multi-objective or conditional) remain unaddressed.\n\n- The evaluations omit comparisons with evolutionary strategies (e.g., CMA-ES) or modern heuristics tailored to specific problems (e.g., MaxCut solvers).\n\n- FLD-IG’s training efficiency is noted, but inference scalability for massive graphs (e.g., >10k nodes) needs deeper analysis.\n\n- The proposed method has good theoretic results. However, the experimental results do not show significant advantage over existing methods.", "was_revised": true, "final_justification": "I appreciate the responses in the author rebuttal. They are satisfacotry to me.", "rebuttal": "We sincerely appreciate the effort you put into reviewing our paper. Below, we provide our responses to the weaknesses and questions you raised.\n\n> **W1: The energy functions of the proposed method use simple penalty terms (Eq. 6); complex constraints (e.g., multi-objective or conditional) remain unaddressed.**\n\nThanks for your constructive comment. While our paper employs a simple penalty term in the energy function and does not yet incorporate more sophisticated constraints, the scenarios we address are nonetheless highly challenging, and the case studies we present involve standard problems commonly used in prior work—on which we have achieved strong results. We believe that our proposed method can be extended to tackle more complex problems, and in future work we will expand our approach to include the elaborate penalty terms and complex constraints you mentioned.\n\n> **W2: The evaluations omit comparisons with evolutionary strategies (e.g., CMA-ES) or modern heuristics tailored to specific problems (e.g., MaxCut solvers).**\n\nThank you for raising this question. As far as we know, CMA‑ES is typically applied to continuous optimization problems, whereas our work focuses on discrete combinatorial optimization. If you could kindly point us to any relevant literature, we would be most grateful. Furthermore, our KaMIS baseline employs the ReduMIS algorithm, which conducts an evolutionary search on a reduced graph. As for MaxCut solvers, we present the results of a semi-definite programming method (SDP), which is a widely used baseline for MaxCut, in the table below and will include them in the final version of our paper.\n\n| Method | Problem              | Size    | Time   |\n| ------ | -------------------- | ------- | ------ |\n| SDP    | MaxCut-BA-[200–300]  | 700.36  | 35.78m |\n| SDP    | MaxCut-BA-[800–1200] | 2786.00 | 10.00h |\n\n> **W3: FLD-IG’s inference scalability for massive graphs (e.g., >10k nodes) needs deeper analysis.**\n\nWe apologize for any misunderstanding. In our ER‑dataset experiments, training was conducted on ER‑[700–800], while inference was performed on ER‑[9000–11000]. The results suggest that our method may exhibit reasonable inference scalability even on massive graphs.\n\n> **W4: The experimental results do not show significant advantage over existing methods.**\n\nThank you for your question. We fully acknowledge your point: although our theoretical contributions are strong, the empirical improvements may not appear dramatic. Since prior solvers already approach the optimal solution, we focused on improving performance in the near‑optimal regime—which is substantially more challenging than improving cases far from optimal. Although our method yields improved results over previous approaches on most datasets, these gains are moderate and indicate that there is still plenty of scope for further refinement.\n\nWe sincerely hope that our response provides you with a clearer and more thorough understanding of our work. If you have any additional questions, please don't hesitate to reach out. We would be more than happy to address any concerns."}, {"review_id": "ZbVLLrsqM2", "reviewer": "Reviewer_kHZa", "summary": "This paper studies combinatorial optimization and Langevin Dynamics and proposes FLD for CO. \n\nTheoretically the authors demonstrate that their algorithm enhances exploration and improves convergence. \n\nEmpirically, results on several problems (the Maximum Independent Set, Maximum Clique, and Maximum Cut problems) further demonstrate that incorporating FLD advances existing approaches and they achieve SOTA performance in most of the experiments.", "questions": "Could you make parentheses the big ones in equation (2), line 76?\n\nThe parentheses are not in the correct form in other places, e.g., line 111.\n\nThe topic of this paper is not very well align with my expertise, therefore I'm not able to evaluate it with much confidence.", "limitations": "n/a", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThis paper is well structured, clearly written, and easy to follow.\n\nThis paper presents both solid algorithmic design, theoretical proof and insights, plus comprehensive empirical results.\n\nWeaknesses:\n\nThe related work part seems to be too concise. It could be extended a little bit.", "was_revised": true, "final_justification": "The authors have addressed the questions I raised in my review. \n\nAfter checking the other reviews and the rebuttal, I believe this work makes a solid contribution.", "rebuttal": "We sincerely appreciate the effort you put into reviewing our paper. Below, we provide our responses to the weakness and questions you raised.\n\n> **W1: The related work part seems to be too concise. It could be extended a little bit.**\n\nThank you for your suggestion. We originally intended to include the Related Work in the main text, but due to space constraints we only provided a partial discussion and subsequently moved it **to Appendix A**. Unfortunately, submission time pressure prevented us from expanding it further. We apologize for this oversight and will fully supplement the Related Work section in the final version of our paper to provide a more comprehensive background review.\n\n**To Q1&Q2**: Thank you for catching this error. We will make the corrections in the final version of our paper and include the correct version in the final submission.\n\nIf you have any additional questions, please don't hesitate to reach out. We would be more than happy to address any concerns."}]

Author rebuttal:

Meta-review: This paper proposes Fractional Langevin Dynamics for the combinatory optimization problem. All reviewers acknowledge the technical contributions of this paper and are also satisfied with the empirical demonstration. The authors provide sufficient feedbacks during the rebuttal phase and the concerns of some reviewers are well addressed. Therefore, I would lean to accept this paper.
Decision: Accept (poster)