Generation as Search Operator for Test-Time Scaling of Diffusion-based Combinatorial Optimization
Authors: Yang Li
Lvda Chen
Haonan Wang
Runzhong Wang
Junchi Yan
Venue: NeurIPS 2025 poster ()
Keywords: Neural Combinatorial Optimization
Generative Model
Inference-Time Scaling
Diffusion Model
Primary area: deep_learning

Abstract: While diffusion models have shown promise for combinatorial optimization (CO), their inference-time scaling cost-efficiency remains relatively underexplored. Existing methods improve solution quality by increasing denoising steps, but the performance often becomes saturated quickly. This paper proposes GenSCO to systematically scale diffusion solvers by an orthogonal dimension of inference-time computation beyond denoising step expansion, i.e., search-driven generation. GenSCO takes generation as a search operator rather than a complete solving process, where each operator cycle combines solution disruption (via local search operators) and diffusion sampling, enabling iterative exploration of the learned solution space. Rather than over-refining current solutions, this paradigm encourages the model to leave local optima and explore a broader area of the solution space, ensuring a more consistent scaling effect. The search loop is supported by a search-friendly solution-enhancement training procedure that incorporates a rectified flow model learning to establish diffusion trajectories between suboptimal solutions and the optimal ones. The flow model is empowered by a lightweight transformer architecture to learn neural ODEs that linearize solution trajectories, accelerating convergence of the scaling effect with efficiency. The resulting enhanced scaling efficiency and practical scalability lead to synergistic performance improvements. Extensive experiments show that GenSCO delivers performance improvements by orders of magnitude over previous state-of-the-art neural methods. Notably, GenSCO even achieves significant speedups compared to the state-of-the-art classic mathematical solver LKH3, delivering a 141x speedup to reach 0.000% optimality gap on TSP-100, and approximately a 10x speedup to reach 0.02% on TSP-500.

Generation as Search Operator for Test-Time Scaling of Diffusion-Based Combinatorial Optimization
Yang Li Lvda Chen ', Haonan Wang', Runzhong Wang', Junchi Yan
School of Computer Science & School of Artificial Intelligence, Shanghai Jiao Tong University
Shanghai Innovation Institute
fyanglily, chenl Madelvdd,,n wrw.ddycogggooeooooooooooo runzhong. wang, yan junch jas tu. edu.ed..com cn
https://githun
com www.:ut....ooooninoi.aeettca Bttp:t/too..oo/iiaaaaaa--SA////
Abstract
While diffusion models have shown promise for combinatorial optimization (CO), their inference-time scaling cost-efficiency remains relatively underexplored. Ex- isting methods improve solution quality by increasing denoising steps, but the performance often becomes saturated quickly. This paper proposes GenSCO systematically scale diffusion solvers by an orthogonal dimension of inference-time computation beyond denoising step expansion, i.e., search-driven generation. Gen- SCO takes generation as a search operator rather than complete solving process, where each operator cycle combines solution disruption (via local search operators) and diffusion sampling, enabling iterative exploration of the learned solution space. Rather than over-refining current solutions, this paradigm encourages the model to leave local optima and explore broader area of the solution space, ensuring a more consistent scaling effect. The search loop is supported by search-friendly training procedure that incorporates rectified flow model learning to establish diffusion trajectories between suboptimal solutions and the optimal ones. The flow model is empowered by lightweight transformer chitecture to learn neural ODEs that linearize solution trajectories, accelerating convergence of the scaling effect with efficiency. The resulting enhanced scaling efficiency and practical scalability lead to synergistic performance improvements. Extensive experiments show that GenSCO delivers performance improvements by orders of magnitude over previous state-of-the-ar neural methods. Notably, GenSCO even achieves significant speedups compared the state-of-thh-art classic mathematical solver LKH3, delivering a 141 x speedup to reach 0.000% optimality gap on TSP-100, and approximately a 10x speedup to reach 0.02% on TSP-500.
Introduction
Combinatorial Optimization (CO), which seeks optimal solutions in discrete spaces under complex constraints, underpins critical applications in vehicle routing 2 chip design 4 (5), and drug discovery [6]. However, the NP-hard nature of many CO problems renders them computationally intractable, traditionally requiring hand-crafted heuristics that demand substantial domain exper- tise and time to design. Recent advances in deep learning have revolutionized this landscape by automating heuristic design through data-driven neural solvers 7 I
10 These ML-based approaches minimize human intervention while achieving competitive or superior solution quality and solving speed, particularly for instances following structured distributions. By learning generalizable frameworks directly from data, they also adapt seamlessly to unseen problem variants.
"Corresonddecce author. i denotes equal contribution. Runzhong Wang is currently affiliated with MIT; part of this work done when he SJTU.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

GenSCO Operator
Random Local Scarch Operators
Disrupted Solution Newrr
Current Solution
Posts Post-PPrccee Pro.eecccingg
Xeurr
X
Knezi
Enhanced Solution
Instance
Rectified Flow Sampling
Nopt Ngubopt
75
Xxubopt
Nopt
Suhoptimal
Optinall
Xyubopt
X2 (t (N,, X2
Relaxed Solution Space
L(0)
F sasoppte lIvo -(0---xxxx (Xsubupe Xopt
GenSCO treats diffusion sampling as a search step, where each step combines solution dis- ruption through random local search operators and solution enhancement via rectified flow sampling. This GenSCO operator can be applied iteratively (or parallel as well) to effectively explore the solution space with stable scaling effect. The flow model learns neural ODEs that linearize the transition between suboptimal solutions and the optimal solution.
Figure I:
Leadningbbased CO solvers typically employ neural networks generate solutions either by directly minimizing objective scores via reinforcement learning 2 12
13
14
15
16
or by aligning
predictions with reference solutions via supervised learning 17
19
20
Recently,
generative models, diffusion models in particular, have shown promise in solving CO with potent rep- resentational capabilities and informative distribution estimation, which models CO conditional generation task for learning solution distributions conditioned on given instances 21
23
g [6].
Despite their promise, diffusion models primarily focus enhancing the prediction accuracy of single generation round, relying on the model's expressive power to refine solution feasibility and quality through multi-step denoising. While this framework inherently supports flexible inference- time computation via adjustable denoising steps, empirical evidence reveals a bottleneck in scaling up computation, i.e., scaling the number of steps yields rapidly diminishing returns, with performance saturating after only few steps of computation. Given that computational efficiency is central to CO, where the goal achieve the optimal solution in the shortest possible time, this observed saturation effect represents critical yet undercxplored opportunity for substantial performance enhancement.
Recent works 24 leverage diffusion models' distributional modeling capabilities to explore solution spaces during inference through alternating phases of disruption (perturbing candidate solutions) and reconstruction (guided by objective gradients). Our empirical results (as presented in Fig. 2 show that this target for solution space exploration provides superior scalability compared to simply increasing denoising steps, yet its full potential remains underexploited due to computationally expensive gradient updates during inference, creating critical scalability bottleneck. In this work, we propose GenSCO that systematically redesigns both the diffusion architecture and the solving pipeline particularly for search purposes, aiming to maximize the inference-tee time scaling effects regarding computation. We propose to integrate diffusion based generation into a novel search operator, where each operator performs three key functions in sequence shown in Fig. I solution disruption with controllable local search operators to escape from local minima and introduce diversity, solution enhancement through solution-to-solutin generation, and post-processing to ensure feasibility. This operator can be applied iteratively (or in parallel as well) to explore the solution space.
For cost-effectiveness and performance scaling, our design adheres to two core principles, i.e., ensuring stable per-cycle improvement and minimizing per-cycle computational cost to enhance scalability. Rather than focusing incremental improvements from extended denoising to emphasize over-pareee pre-pparameterized single-round generation, we reallocate computation to higher-level refinement cycles. Each cycle ensures reliable solutions with minimal inference-time -imenneee-mmeeeee cost, while repeated

---

cycles effectively unlock high-quality regions of the solution space, collectively enhancing both efficiency and solution quality. To maximize per-eycle improvement without introducing additional computational cost during inference, GenSCO adopts a rectified flow embodiment of the diffusion model, which transitions from the prior noise-to-solution paradigm to a more search-friendly solution- to-solution refinement target. It formulates a bias-rectified training process where the model receives a worse-quality solution as the initial source noise and learns to denoise it to the optimal, which shifts the optimization burden to the training phase. This naturally introduces solution enhancement capability and enables adaptive control over the intermediate solution states during the search process, For scalability of search cycles, the rectified flow model leverages neural ordinary differential equations (ODEs) to learn nearly straight solution trajectories, minimizing truncation errors and enabling high-quality generations with fewer inference steps, which ensures reliable denoising while maintaining cost-efficiency. To further enhance scalability, we implement lightweight transformer architecture that operates exclusively node embeddings, which minimizes computational overhead while enabling thousands of evaluations within practical time budgets.
The highlights include: (I) We pioneer inference-time scaling cost-efficiency perspective for diffusion solvers, challenging the conventional paradigm of allocating computation to maximize single-round generation quality. Instead, we propose novel framework that treats generation as search step, enabling systematic exploration of the solution space through refinement cycles. (2) We systematically redesign both the diffusion architecture and the solving pipeline specifically for search- driven optimization. Major designs include a -ontttooonto rectified flow model supported by a bias-rectifies training objective, and controllable search operator that enables efficient scaling. (3) Extensive experiments demonstrate that GenSCO significantly outperforms state-of-the-an methods in both solution quality and solving speed, achieving aeder-of-magnitude improvements.
2 Related Work
Neural Combinatorial Optimization. Learning-based methods for CO can be broadly categorized into constructive methods, improvement-basee methods, and divide-and-conquer frameworks. Con- structive methods generate solutions either autoregressively or non aanrarrrrrrrrsiilly. Autoregressive
methods 25 26 22 27 iteratively build solutions by selecting one variable each step while
maintaining feasibility. In contrast, con-autoreeressivee methods [8] 19 28 2 29
30
31] 32]
directly predict the probabilities of variables belonging to the optimal solution in a single pass. These methods often require post-process prst-processing to enforce feasibility due to the potential infeasibility of raw
[35 36 14] learn to iteratively refine solution through local search operators guided by neural networks while preserving or restoring feasibility. Rel- atively orthogonal to pure solving methods, divide-andd-coquer frameworks [35] 37 38,
predictions. Improvement-Be based solvers [33 15
34
39
40 41
adopt a hierarchical strategy to address scalability challenges. By decomposing large-scale problems into smaller subproblems, these methods leverage existing solvers (either classical or neural) on the subproblems and aggregate the results into global solution. Recent unified frameworks and benchmarks [42 43 45 have been developed to systematically analyze the design space of CO approaches, yielding principled insights and practical guidelines for method design.
Generative modeling
46
49
50
51
52
has shown promise in CO solving 21 16
53 544 and data supports 555
57 The work (21) highlights the potential of generative CO. utilizing the powerful representational capabilities and informative distribution estimation of diffusion models to learn solution distributions. [6] promotes the diffusion framework to the unsupervised CO solving scenarios. Furthermore, (24 introduces training consistency scheme ensuring that all noise trajectories for certain graph converge to the same initial solution, thereby significantly reducing the gradient search during solving through re- re-generation within the noisc-solution transition space to further explore the estimated solution distribution. While these techniques improve performance beyond denoising step scaling, they remain limited auxiliary modules due to their reliance costly gradient updates during inference, which creates a scalability bottleneck. Meanwhile, current models operate in the coise-to-solution transition space where the source noise distribution is stationary and intermediate states are untractable, lacking sufficient controllability.
56
number of denoising steps required. 99, 24] both introduce specific objective-
Diffusion Models and Flow Models. Diffusion models have emerged as a powerful framework for generative modeling, involving dual process: the forward diffusion process, which gradually adds noise to data, and the reverse denoising process, where model learns to reconstruct the
3

---

original data from noisy versions. For Diffusion in continuous space 58 59 60
61
62
63
64]
the solution trajectories can be modeled by Probability Flow ODE 655. Similar paradigms have also been adopted for discrete data using binomial or multinomial/categorin noises [S8 66
67
71 72 such as rectified flows [8]] build upon the diffusion framework by focusing on learning transport maps between distributions as a flow that follows nearly straight paths defined via neural ODEs. Rectified flows can learn smooth ODE trajectories that are less susceptible to truncation error, which allows for high-quality samples with fewer inference steps than diffusion models. Moreover, they can be generalized to map two arbitrary distributions to one another, making them particularly suited for search- search-friendly solution-to-solun toluuutoooooonnnno generation in CO.
Flow models 668 69 70
3 Preliminaries and Problem Definition
Combinatorial Optimization. Following the conventions of [73 74), we formalize CO over a family of problem instances represented as graphs G. where each instance G(V, E) E 9 consists of V and E denote the vertex set and edge set respectively. CO problems can be broadly classified into two types based on the solution composition: edge-decision and node-decision problems. Let x E {0, 1} denote the optimization variable, where each entry with 1 indicates that it is included in x and 0 indicates the opposite. For edge-decision problems, N = |V|2 and x indicates whether Ex, is included in x. For node-decision problems, N = and x; indicates whether V; is included in x. The feasible set Q contains all solutions satisfying specific constraints. A CO problem on G' aims to find feasible x that minimize the given objective function [(: G): {0, 1 + Rgo:
min 1(x; G) s.t. X xE(0,1)
(1)
The Travelling Salesman Problem (TSP) is defined on complete undirected graphs, where vertices represent cities and edges have non-negative weights (e.g., distances). The goal find a minimum- weight Hamiltonian cycle. For Maximal Independent Set (MIS), given an undirected graph G = (V, E), an independent set S C contains no adjacent vertices. MIS seeks the largest such set G. The Maximum Clique (MCI) problem, given an undirected graph G = (V, E), seeks a largest subset C V such that the subgraph induced by C is complete.
Diffusion Modeling for CO. The goal of diffusion modeling for CO is to learn the distribution G)) of high-quality solutions of instance G. This framework operates through a forward noising process that gradually corrupts an initial solution X ~ ((xo]G) over T timesteps to produce latent variables X1:T. and learned reverse process that reconstructs the solution by parameterizing the joint distribution pe (Xo.r) = 112"1Po ( (xx). The training optimization aims to align pe (Xo G)) with the data distribution (xxn G') using the variational upper bound of the negative log-likelihood.
Current implementations 21 employ either discrete or continuous diffusion approaches. In discrete diffusion, solutions are represented as N one-hot vectors {0, 1} Nx2, with the forward process applying multinomial noise through q(x, ix, = Cat(x;; = x,- Qt). where Q, =
B:
B. This process gradually randomizes the variables according to the corruption 3,
rate B3, eventually converging to uniform stationary distribution. Continuous diffusion models, on the other hand, map discrete solutions to the continuous domain [-1, to enable the use of Gaussian noise. The forward process in this case follows q(x, (x-1) = A (xx: vI fix,-1, 8,I), with the noise scale controlled by B, and the stationary distribution being Gaussian.
4 The GenSCO Framework: Generation as a Search Operator
In difffusion solvers, scaling the number of denoising steps is conventional strategy enhance single- round generation quality. By discretizing the diffusion process into finer time intervals, the solver theoretically achieves more precise noise estimation. However, as the number of steps increases, the solver's 's capacity to navigate sigh-dimensional, constrained solution spaces becomes the primary bottleneck rather than temporal resolution. The inherent task complexity leads to imperfect noise estimation, even with finer temporal granularity, and minor prediction errors accumulate across steps. Consequently, merely increasing computational resources for finer discretization yields diminishing returns, prompting the need for alternative scaling paradigms.

---

This section introduces the GenSCO framework, which treats generation as search operator within the near-optimal solution space and scales solving performance through corresponding search cycles. To address the bottleneck of scaling single-round prediction precision, GenSCO shifts the paradigm to systematic exploitation of the learned high-quality solution distribution. The subsequent subsections first present a lightweight rectified model that learns solution-to-solutie refinmmen,, supporting near-optimal search cycles with flexible control over exploration. Then, the specific search-based inference pipeline that integrates learned refinement policies is introduced to achieve more effective scaling of solving performance with respect to computation.
4.1 Learning Solution Enhancement with Lightweight Rectified Flow Model
Existing diffusion approaches for CO often anchor their generative processes to stationary noise distributions to enable standard sampling paradigms, exhibiting a disconnect between the diffusion trajectory and the structured nature of solution spaces, i.e., the generative process operates in the noise space rather than within the (relaxed) solution space. The heavy de novo generation process relying on Gaussian initialization restricts both the controllability of the intermediate states within generation and the exploitation of prior solution knowledge. For the search purpose, we redefine the diffusion paradigm as a guided transition process between suboptimal and optimal solutions, formulation that better aligns with heuristic search dynamics. We replace conventional noise injection with problem-speseeeeeeeeeeeeeeeeeeee local search operators (e.g., randomized 20pt moves for TSP or variable flipping for MIS and MCI) to simulate possible suboptimal solutions that the model may encounter during inference. This enables adaptive control over source distribution to balance tradeoffs and utilization of existing solutions as diffusion initializations. To improve cost-efficiency and scalability, implement rectified flow model that learns straight- line interpolation paths between perturbed solutions and optimal targets, achieving both model compactness and accelerated sampling, facilitating the scaling of search operator calls during inference.
pegloraation-xploittatiii
GenSCO adopts a continuous-time probability flow ODEs 68), where the transformation between solution distributions occurs along smooth trajectory parameterized by / E [0, 1). Given graph instance G, denote the target point distribution of the optimal solution as To. the distribution of suboptimal (feasible) solutions as Ti. In practice, for TSP, we perform 20pt operations optimal solution N. to 3.V times, and for MIS and MCI, we randomly flip between 1 and & of the 4
the
variables assigned with to 0 to get suboptimal solutions. To facilitate smooth transitions between these solutions, we relax the {0. 1 v--aulued solutions to the interval [o, 1] and treat the variables in the intermediate process real-valued. Given solutions Xopt ~ To. X.uhopt T1, the rectified flow induced from (Xope: Xanbop)) is an ordinary differentiable model (ODE) on time E [0, 1],
dx, v(x,, t, G)df
which converts solution Xopt from To to a Xsubopt following TT. We establish the solution transition as the linear trajectory to guarantee fast convergence:
X
tx + (1 - t)x E [0,
In this case, the drift force is set to drive the flow to follow the direction (Xanhopt Xaps) of the linear path pointing from Xupi to Xahhpp much as possible, i.e., dx: v(x,, f, G') = Xuutopt Xopt- di
Since Xopt is unknown for simulating this ODE flow, we parameterize the velocity field v with neural network with the following loss function:
(( E Xutonn G !h'' Iivoxxx t, (Xsuboope - x dt
In implementation, we represent Vo vo(xe, G) = X fo(Xe, 1, G) where fx(,,, 1, G) directly predicts the optimal solution given the graph instance and the current state. Given a sequence of time points 1 Ti > T2 > > TN > TN. O, the generation process defines a solution enhancement process where the ODE can be solved via numerical integration, c.g., Euler's method:
X XT. (Tn 7n+ Vo Tn, G), V (2, -1.
(5)
large value of N, results accurate but slow simulations, while a small value of N, leads to faster but less accurate simulations. Since the probability flows are ideally modeled as straight paths, a small number of steps can still yield plausible results. To improve scaling by redistributing single-cycle computations across more cycles, set N,- = 4 in the majority of our empirical evaluations.
5

---

Architecture. Prior work predominantly relies on deep anisotropic graph neural networks with edge gating mechanisms [1] to support reliable single-round heatmap prediction, particularly for edge-based decision tasks like TSP. It incurs significant computational overhead due to its quadratic complexity in handling edge features, leading to the compounding latency from iterative denoising, severely constraining the scalability of such approaches as practical search operators.
To ensure scalability, we propose a lightweight architecture centered on node-only feature processing via a transformer-based architecture, eliminating the need for explicit edge feature computation. For input processing, node features undergo linear projection into the model's embedding dimension. The
mechanism is augmented to explicitly encode graph structure through simple yet effective modification to the attention logits computation:
Attention( Q, K, V) softmax (QK (QKT/Vdr + AA) V
(6)
where A represents the adjacency matrix and À is a scaling parameter that balances the relative importance of learned attention patterns versus explicit graph connectivity. By convention, Q, K, V denote the query, key, value matrices for the vertices, respectively. dg denote the dimension of K.
Our model operates solely on node features E RNNx, where N is the number of nodes and f the feature dimension. The transformer layers capture global dependencies through self-attention, after which task-specific outputs are generated. For node-wise decisions (e-g.. MIS and MCI), we apply linear layers to project node embeddings directly into probability vectors. For edge-wise decisions (c.g., TSP), we compute pairwise connection logits (unnormalized log- prg-robabblities via an inner product hh RNXN, yielding a heatmap without explicit edge-level operations. This design preserves expressiveness while maintaining computational tractability in iterative refinement scenarios, enabling scalable operator calls (hundreds to thousands) during search.
4.2 Scaling Solving Performance with Search- Generation
Recent advances in diffusion models for image generation overcome quality plateaus by strate- gically leveraging sampling stochasticity during inference (75). Studies demonstrate that certain noise patterns yield superior outputs (76, (77), prompting methods to devote computation to identifying these preferable noise configurations through multi-sample exploration. Translating this insight to CO, where generative models ap- proximate nigh-performance solution distribu- tions, we argue that systematically exploiting the solution space, i.e., shifting from a focus on single-round prediction accuracy to exploring the breadth of the solution space, can unlock more effective search strategies, CO problems exhibit two distinctive characteristics over con- ventional generative tasks. The first one lies in the existence of deterministic solution verifiers, i.e., the optimization objective itself. This enables rapid quality evaluation of candidate solutions and facilitates flexible control over search processes through immediate feedback. Second, unlike generative tasks requiring broad mode coverage, CO prioritizes incremental refinement toward optimality. This permits focused search paradigm where minor perturbations to near-optimal solutions supersede full-space exploration.
Algorithm 1
GenSCO Framework for Solving
Input:
Flow model ve(:,-:). graph problem
instance G, number of cycles Ne. sequence of TN, = 0
time points 1 71 T2
Randomly initialize solution x for cycle c = to N. do
X,1 -- Disrupt(x)
for time step = 1 to N, do
d = V Tny G)
X = X - (T Tnt1)d,,
end for x + PostProcess(xxx.)
end for Output: Solution
Based on these considerations, we propose noural-based local search framework that iteratively refines solutions within near-optimal regions supported by search-driven generation. This method introduces an orthogonal dimension of inference-time computation beyond denoising step expansion, i... search cycles. This approach leverages the solution-to to--tooutoooo enhancement mapping (as introduced in Sec. 4. and the diversity of the learned solution space to design a structured search process. While a naive implementation might iteratively apply the learned solution enhancement mapping to the current solution, such a strategy risks stagnation at local optima. To address this, we introduce a search operator that synergizes two components, i.e., solution disruption (via classic local search operators) that perturbs solutions to escape suboptimal regions, and diffusion sampling that

---

leverages the generative prior to navigate toward bigh-potential regions. Raw model outputs require decoding (and optional local search p to become valid solutions. For valid search operator, we tightly integrate decoding and refinement steps directly into the search operator, ensuring feasible intermediate states while preserving real-time feedhack from solution quality evaluations.
As detailed in Alg. I the solving process initiates with a randomly initialized solution vector x, obtained through greedy decoding applied randomized variable heatmaps. Subsequently, the GenSCO framework performs N₂ search cycles. In each cycle, x undergoes disruption: for TSP, and AN
this involves executing between random selection of 25% to 40% of the variables assigned a value of I are flipped to O, resulting in a disrupted solution x for MCI, 25% to 40% of the variables are randomly selected and flipped. To enhance the solution, X is treated as a relaxed solution within the domain [0, 1 Given a sequence of time points = Ti > 72 > > TN.-1 > TN, = O, the enhancement process is modeled by an ODE, which is solved through numerical integration, such as Fuler's method, as expressed in Eq. The outcome is an enhanced solution X. residing within the relaxed solution space [0. 1) To derive a feasible solution, Xo is interpreted as a variable heatmap, where each element represents the confidence level of selecting the corresponding edge or node. Greedy decoding is then applied to sequentially select edges or nodes with the highest confidence, provided no conflicts arise. For TSP, the 20pt heuristic 78] is optionally employed within post-processing. Upon completion of Ne search cycles, GenSCO reports the best solution identified during the search process. Notably, the entire search procedure is amenable to parallel execution, leveraging complementary search effects. The pipeline of the proposed operator is presented in Fig. !
4 20pt operations to the existing solution; for MIS, a
5 Experiments
Sos Care 2 2004
Soaling dyc
Opiine yyoee 1o1
In this section, we empirically com- pare our proposed GenSCO with other bearning-based and classical solvers on TSP, MIS and MCI instances with var- ious sizes and distributions. Source code will be made publicly available.
Vamber Fundor bntustioe
(a) Scaling w.r.t. Runtime
(b) Scaling w.r.t. NFEs
5.1 Experiments for TSP
(a) Scaling curves for the traditional diffusion model, via denoising steps and gradient steps, and GenSCO through search cycles on TSP-1000 (b) The performance variation when scaling denoising steps in single generation round and scaling search cycles in GenSCO
Figure 2:
Datasets. A TSP instance includes N 2-D coordinates and a reference solu- tion. Instances are generated via uni- formly sampling N nodes from the unit square [0, 1J2. The training sets consist of 1, 1,280K instances for TSP-100, and 128K for TSP-500 and 1000. The test sets include 1, 1,280 instances for TS0-100, and 128 instances for TSP-500 and 1000. Reference solutions are obtained by Concorde 77). Results on TSPLIB? data are in the Appendix.
Metrics. 1) Objective: the average total distance cost of the solved tours w.r.t. the corresponding instances; 2) Gap: the relative performance drop with respect to length compared to the global optimality or the reference solution; 3) Time: the computational time to solve the problems.
Model Setting. We use 4 denoising steps in a single round of flow generation and run 8 GenSCO op- erators in parallel. In the post-processing step, we apply greedy decoding with optional N/50 steps of 20pt. The number of search cycles, denoted as C, is treated as a hyperparameter to control the extent of exploration. To configure the diffusion baselines, we adopt T, and Tg to represent the number of in- ference steps in initial solution sampling and the number of gradient search steps ( 24), respectively.
Main Results for TSP. Table D presents the solving performance comparison. As shown, GenSCO sigmificantly outperforms all previous baselines and even LKH3 within its solving time. For example. on TSP-100, GenSCO attains an optimality gap of 0.000% in just 6 seconds, whereas LKH3 [80] indeed requires 14.1 minutes to reach 0.000% (141x x slower), and the raw diffusion baseline DI- FUSCO [21] takes 52.1 minutes to achieve 0.06%. Similarly, on TSP-500, GenSCO achieves 0.012%
in 18 seconds, compared to DIFUSCO's 0.87% in 19.1 minutes, with a 72.5x reduction optimality
gap and a 60. speedup. Meanwhile, LKH3 requires 1.1 minutes (3.7x x slower) to match this
htttp:/ccmoppt. ifi unw- umi-heidelberg
7

---

Table 1: Results on TSP. AS: Active Search, G: Greedy, S: Sampling Decoding, BS:
Beam Search.
TSP-100 (1280 inst.)
TSP-500
(128 inst.)
TSP-1000
(128 inst.)
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Mathematical Solvers Heuristics
Concorde
79
7.76
0.000%
5.1m
16.55
0.000%
39.8m
23.12
0.000%
3.0h
LKH-3
(trials=32)
7.76
0.009%
52s
16.55
0.024%
42s
23.13
0.035%
2.2m
LKH-3
80
(trials=64)
7.76
0.006%
59s
16.55
0.015%
50s
23.12
0.025%
2.5m
LKH-3
80
(trials=128)
7.76
0.003%
1.2m
16.55
0.011% 1
1.1m
23.12
0.015%
3.1m
LKH-3
(trials=256)
7.76
0.002%
1.6m
16.55
0.006%
1.6m
23.12
0.009%
4.1m
LKH-3
(trials=512)
7.76
0.001%
2.5m
16.55
0.002%
2.5m
23.12
0.005%
6.2m
LKH-3
80
(trials=1096)
7.76
0.000%
14.1m
16.55
0.000%
15.0m
23.12
0.001 %
36.3m
Non-Generative Neural Solvers
AM 0
7.95
2.48%
12.9m
19.53
18.03%
2.8m
29.90
29.24%
12.6m
POMO 2 x8 augment
7.77
0.13%
8s
20.22
22.19%
1.0m
32.55
40.57%
8.0m
POMO+EAS [1 AS+G
7.76
0.05%
38.4m
24.54
48.22%
11.6h
49.56
114.36%
63.5h
GCN g BS
8.41
8.38%
6.0m
30.37
83.55%
38.0m
51.26
121.73%
51.7m
DIMES
12
S+20pt
7.98
2.88%
17.64
6.56%
1.1m
24.81
7.29%
2.9m
DIMES
12
AS+S+20pl
7.93
2.18%
3.2h
17.29
4.48%
2.1h
24.32
5.17%
4.5h
LEHD
X2
PRC 100
7.76
0.01%
1.8m
16.61
0.34%
8.0m
23,44
1.22%
43.0m
LEHD
32
PRC 1000
7.76
0.002%
16.9m
16.58
0.17%
1.2h
23.32
0.72%
7.0h
BQ-NCO
BS
7.76
0.01%
4.1m
16.64
0.55%
15m
23.47
1.38%
38m
GLOP 39
16.91
1.99%
1.5m
23.84
3.11%
3.0m
UDC 50
16.78
1.58%
4,0m
23.53
1.78%
8.0m
COExpander 53
7.76
0.01%
3.84m
16.59
0.25%
1.41m
23.27
0.64%
5.2m
Generative Neural Solvers
DIFUSCO (T,=50) A1
2+20pt
7.78
0.28%
18.9m
16,80
1.50%
4.7m
23.55
1.89%
14,4m
DIFUSCO 20
2+ptpt
7.76
0.06%
30m
16.69
0.87%
19.1m
23.42
1.31%
51.9m
T2T (T.=3000,,
9
G+20pt
7.76
0.07%
28.6m
16.68
0.82%
6,5m
23.44
1.40%
19.7m
T2T (T.550T,:33)0)
S+20pt
7.76
0.02%
45.1m
16.63
0.48%
19.7m
23.37
1.07%
51.1m
Fast T2T (T,=5.T,=5)
M G+20pt
7.76
0.03%
4.2m
16.61
0.39%
2.2m
23.25
0.58%
8.6m
Fast T2T (T:=5.T==5)
24
S+20pt
7.76
0.01% 1.01%
8.3m
16.58
0.21%
6.9m
23.22
0.42%
18.3m
GenSCO (C=10)
7,76
0.000%
6s
16.55
0.023%
5s
23.25
0.559%
12s
GenSCO (C=20)
16.55
0.020%
9s
23.21
0.390%
23s
GenSCO (C=40)
16.55
0.016%
18s
23.18
0.258%
46s
GenSCO (C=10) 20pt
7.76
0.000%
16.55
0.019%
5s
23.13
0.063%
16s
GenSCO (C=20) 20pl
16.55
0.016%
23.13
0.054%
30s
GenSCO (C=40) 20pl
16.55
0.012%
18s
23.13
0.046%
58s
GenSCO (C=80) 20pt
16.55
0.011% 1%
368
23.13
0.041%
2.0m
GenSCO (C=160) 20pl
16.55
0.010%
1.2m
23.13
0.036%
3.9m
solution quality (0.01 1)). Although LKH3 exhibits a steeper scaling slope and eventually surpass GenSCO at larger problem sizes, this work represents significant milestone where a neural solver genuinely outperforms LKH with sufficient time. Notably, within the high- accuracy regime of 0.02% optimality gap, GenSCO achieves approximately 10x speedup compared to LKH3.
Scaling Effect with Increased Computa-
Table 2: Generalization results. Objective and Opti- mality Gap metrics are reported.
(a) presents a comparison of scaling curves between GenSCO and the raw diffusion model as computation scales, with 20pt the post-processing technique. We scale previous diffusion models through denoising steps (DIFUSCO (1I) and gradi- ent search steps (T2T (9). The results show that while gradient search can overcome per- formance plateaus, its scaling effectiveness remains limited due the costly inference steps. In contrast, thanks to its lightweight operators, GenSCO efficiently scales to hun- dreds of function evaluations within a short
tion. Fig 2
Training
TSP-100
TSP-500
TSP-1000
Testing
TSPIK TSP300 TSP100 TSPS0
DIFUSCO (5.
21
5.70, 0.25%
5.83, 2.55%
5.84, 2.71%
T2T GenSCO (C-40)
g
5.70, 0.11%
5.78, 1.00%
5.75, 1.10%
$.69, 0.00%
5.69, 0.05%
5.69, 0.08%
DIFUSCO (T,=50)
21
7.78, 0.23%
8.03, 3.44%
8,02, 3.31%
121 (T,50) H00
7.77, 0 0.0%%
7.95, 7. 1.47%
7.91, 1 1.96%
GeaSCO (C=/l)
7.76, 0.00%
7.85. 1.16%
7,87, 1.42%
(5,) 21
17.05,
T2T (T,-50.1,-300
16.92, 2.25%
16.68, 0.8.%
16.72, 1.00%
GeaSCO (C=40)
16.99, 2.70%
16.55, 0.01
16.55, 0.02%
DIHUSOD 50, 21
24.04, 3.98%
2.30%
2.21%
T2T (T,
23.85, 3.16%
23:47, 1.51%
23.41. 1.23
GeaSCO (C=+i)
24.37, 5.40%
23.14, 0.11%
23.13, 0.05%
time frame, maintaining high performance with a nearly linear improvement trend. Fig 2 (b) illustrates the performance variation when scaling denoising steps in single generation round and scaling search cycles in GenSCO. Scaling search cycles results in more stable performance, overcoming the performance plateau that occurs when simply increasing inference steps.
8

---

Table 4: Results on MIS. G: Greedy, St Sampling, TS: Tree Search, UL: Unsupervised Learning.
RB-[200-300]
[R-[700-800]
Method
Type
Obj.
Gap
Time
Obj.
Gap
Time
KaMIS
87
Heuristics
20.10*
1.4h
44.87*
I2.Im
Gurobi
Exact
19.98
0.01%
47.6m
41.28
7.78%
50.0m
Intel 83
SL+G
34.86
22.31%
6.1m
DIMES
RL+G
38.24
14.78%
6.1m
Intel 83
SL+TS
18.47
8.11%
13.1m
38.80
13.43%
20.0m
DGL 85
SL+TS
17.36
13.61%
12.8m
37.26
16.96%
22.7m
LwD 84
RL+S
41.17
8.25%
6,3m
GFlowNets
26
UL++S
19.18
4.57%
32s
41.14
8.53%
2.9m
DIFUSCO (T,=100)
21
SL+G
18.52
7.81%
16.1m
37.03
18.53%
5.5m
DIFUSCO (I,=100) 21
SL+S
19.13
4.79%
20.5m
39.12
12.81%
21.7m
T2T (I,=501;;=30) 9
SL+G
18.98
5,49%
21.0m
39.81
11.28%
7.1m
T2T (T,=50TT;=3)0)
SL+$
19.38
3.53%
30.3m
41.41
7.72%
27.8m
Fast T2T (T,=5.TT=)
24
SI.+G
19.49
2.89%
4.7m
40.68
9.34%
1.5m
Fast T2T (T,=5.T,=)))
SL++
19.70
1 1.90%
7.0m
41.73
6.99%
5.9m
GenSCO (C=500)
SL+G
19.85
1.24%
1.1m
42.46
5.37%
40s
GenSCO (C=lk)
SL+G
19,91
0.96%
2.2m
42,91
4.38%
1.3m
GenSCO (C=2k)
SL+G
19.97
0.64%
4.4m
43.33
3,44%
2.7m
GenSCO (C=4k)
SL+G 20.01
0.43%
8.8m
43.77
2.46%
5.3m
GenSCO (C=8k)
SL+G 20.04
0.29%
17.6m
44.13
1.66%
10.7m
GenSCO (C=16k)
SL+G 20.06
0.22%
35.2m
44.41
1.03%
21.4m
Cross-Scale Generalization. We train the model a specifie problem scale and then evaluate on all problem scales. Table T presents the generalization results of GenSCO compared with diffusion counterparts. We discover that generalization performs well between large-scale datasets (TSP-500 and 1000) and also between small-scale datasets (TSP-50 and 100). However, generalization degrades across data distributions with large differences, unless the test set is simpler dataset like TSP-50. Nonetheless, GenSCO still exhibits superior performance compared to prior baselines.
Training with Suboptimal Supervision. We investigate the performance of GenSCO trained with worse-quality data produced by the 20pt heuristic (with 1.9% gap on TSP-100 and 7.0% gap on TSP- 500). Table 3 shows that even though the model is trained on worse-quality solutions, which results in a less reliable solution refinement mapping, the iterative search cycles can still effectively explore the solution space, thereby ultimately yielding performance that surpasses the original supervision source. We further employ the trained GenSCO to relabel a small subset (1/75) of the dataset, then iteratively fine-tune subsequent models 2GenSCO² and GenSCO²) to verify the capacity of self self-improving and gradually elevating the supervision quality.
5.2 Experiments for MIS
Table 3: Performance of models trained with lower-quality supervision.
Datasets. Two datasets are tested for the MIS problem
following 83
including RB graphs (3) (ER) graphs [86]. For RB graphs,
and
Method
TSP-100
TSP-500
we randomly sample 200 to 300 vertices uniformly to generate graph instances. For ER graphs, we construct random graphs with 700 to 800 nodes, setting the pair-
Obj.
Gap
Obj.
Gap
20pt
7.905
1.920%
17.703
6.994%
GenSCO
7.757
0.014%
16.823
1.676%
GenSCO
7.756
0.007%
16.699
0.927%
wise connection probability as 0.15.
GenSCO
7.756
0.005%
16.642
0.583%
Metrics. 1) Objective: the average size the solutions w.r.t. the corresponding instances; 2) Drop:
the relative performance drop w.r.t. size compared to the optimal solution or the reference solution; 3) Time: the computational time required solve all the test instances.
Model Setting. We use 3 denoising steps in a single round of flow generation and run the search oper- ator without parallelization. The number of search cycles, denoted C, is treated hyperparameter to control the extent of exploration. The configurations of the diffusion baselines follow those in TSP.
Main Results. Table demonstrates the effectiveness of GenSCO, showcasing both performance advantages and stable scaling behavior compared to the raw diffusion model. To ensure a fair comparison with neural solvers, Gurobi's solving time is limited, and thus it does not reach optimality.

---

Table 5: Results on MCI. G: Greedy, S: Sampling, UL: Unsupervised Learning.
RB-[200-300]
RB-(800-1200)
Method
Type
Obj.
Gap
Time
Obj.
Gap
Time
Gurobi
88
Exact
19.08
0.00%
7.5m
40.18
0.00%
38.4h
Meta-EOI EGN
88
UL
17.51
8.30%
2.3m
33.79
15.49%
4.5m
DiffUCO 16
UL
16.21
12.53%
11.8m
COExpander
bs
SL++
19.00
0.50%
5.4m
39.06
2.99%
53.0m
COExpander 53 more steps
SL+S
18.98
0.68%
30s
39.88
0.90%
3.1m
GenSCO (C=500)
SL+G
19.08
0.01% %
1.1m
40.22
-0.10%
6.9m
GenSCO (C=lk)
SL++
19.08
0.00%
2.2m
40.23
-0.13%
13.8m
GenSCO (C=500) achieves strong results within just 1.1 minutes on the RB dataset and 40 seconds on the ER dataset, reaching optimality gaps of 1.24% and 5.37%, respectively. This corresponds to a 3,99 reduction in gap with an 18.6x speedup RB, and a 2.4x gap reduction with 32.6x speedup ER, compared to the raw diffusion model baseline DIFUSCO (21] when scaling inference steps. Moreover, the number of search cycles increases, GenSCO consistently delivers performance gains. With comparable solving time, it reduces the optimality gap from 4. 4.79% to 0.29% (16.5x improvement) on RB, and from 12.81% % to 1.03% (12.4x improvement) ER, compared DIFUSCO.
5.3 Experiments for MCI
Datasets.
Two datasets, RB-Small and RB- RB-Large, tested for the MCI problem following [53] 23
[6]. The RB-Small dataset involves graph instances with 200 to 300 uniformly sampled vertices, and the RB-Large dataset involves graph instances with 800 to 1200 uniformly sampled vertices.
Metries. 1) Objective: the average size of the cliques w.r.t. the corresponding instances; 2) Drop: the relative performance drop w.r.t. size compared to the optimal solution or the reference solution: 3) Time: the computational time required to solve all the test instances.
Model Setting. We use 3 denoising steps in single round of flow generation and run the search operator without parallelization. The number of search cycles, denoted C, is treated as a hyper- parameter to control the extent of exploration. The configurations of the diffusion baselines follow those in TSP and MIS.
Main Results. Table 5 presents the significant performance advantages of GenSCO on the MCI problem. To ensure fair comparison with neural solvers, Gurobi's solving time is limited, and thus it does not reach optimality. GenSCO achieves strong results with the solution quality gap of 0.00% on RB-[200-300) and -0.13% on RB-[800- 1200] compared to Gurobi. This exceptional solution quality is delivered with remarkable efficiency. GenSCO can exceed Gurobi (-0.10% 10%) with just 6.9 minutes (334x speedup). which stands in stark contrast to the 38.4 hours needed by Gurobi to reach such solution quality. Compared to other learning-base -baeed solvers, this outcome marks step-change, offer-of-mmgnitudee improvement. From the perspective of the gap metric, it has reduced the learning-bar based solvers' performance from 0.90% to -0.13%.
Conclusion
This work presents a novel perspective on diffusion-based solvers by prioritizing inference-time cost- efficiency through scalable, search-driven optimization rather than focusing solely on maximizing singlc-round generation quality. We redesign both the diffusion architecture and the solving pipeline by introducing a colution-to-oluiin enabling systematic exploration of the solution space via iterative refinement cycles. Extensive experiments demonstrate that GenSCO delivers performance improvements by orders of magnitude over previous state-of of-th-a neural methods. Notably, GenSCO even achieves significant speedups compared to the state-of state-of-the -frthe--rt classic mathematical solver LKH3, delivering 141 x speedup to reach 0.000% optimality gap on TSP-100, and approximately 10x speedup to reach 0.02% on TSP- 500. These results potentially mark milestone in neural combinatorial optimization, showcasing the potential of scalable neural solvers for high-accuracy and high-speed problem solving and paving the way for future advances in combinatorial optimization through the lens of AI.
rectified flow model alongside a controllable search operator,
10

---

Acknowledgements
This work was partly supported by NSFC (92370201).
References
[1] W. Kool, H. Van Hoof, and M. Welling, "Attention, learn to solve routing problems!" arXiv preprint 1803.08804.444 2018.
[2] Y.-D. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, and S. Min, "Pomo: Policy optimization
with multiple optima for reinforcement learning," Advances in Neural Information Processing
Systems, vol. 33, pp. 21 188-21 198, 2020.
[3] S. Wang, H. Xu, Y. Zhang, J. Lin, C. Lu, X. Wang, and W. Li, "Where paths collide: A comprehensive survey of classic and learning- based multi-agent pathfinding," arXiv preprint arXiv:2505. 19219, 2025.
[4] S. Held, B. Korte, D. Rautenbach, and J. Vygen, "Combinatorial optimization in vlsi design." Combinatorial Optimization, pp. 33-96, 2011.
[5] R. Cheng. X. Lyu, Y. Li, J. Ye, J. Hao, and J. Yan, "The policy-gradient placement and generative routing neural networks for chip design," Advances in Neural Information Processing Systems, vol. 35, pp. 26 350-26 362, 2022.
[6] R. Liu, X. Li, and K. S. Lam, "Combinatorial chemistry in drug discovery," Current opinion in chemical biology, vol. 38, pp. 117-126, 2017.
[7] Y. Bengio, A. Lodi, and A. Prouvost, "Machine learning for combinatorial optimization: a methodological tour d' d'horizon," European Journal of Operational Research, 2021.
[8] C. K. Joshi, T. Laurent, and X. Bresson, "An efficient graph convolutional network technique for the travelling salesman problem," arXiv preprint arXiv: 012000022. 2019.
[9] Y. Li, J. Guo, R. Wang, and J. Yan, "T2t: From distribution learning in training to gradient search in testing for combinatorial optimization," in Advances in Neural Information Processing Systems, 2023.
[10] S. Wang, Z. Guo, C. Lu, and J. Yan, "Fractional langevin dynamics for combinatorial opti- mization via polynomial-tin escape." in Advances in Neural Information Processing Systems, 2025.
[11] M. Kim, J. Park, and J. Park, "Sym-neo: Leveraging symmetricity for neural combinatorial optimization," arXiv preprint 2220, 2022.
[12] R. Qiu, Z. Sun, and Y. Yang, "Dimes: A differentiable meta solver for combinatorial optimization problems," arXiv preprint arXiv:2210.04123; 2022.
[13] Y. Min, Y. Bai, and C. P. Gomes, "Unsupervised learning for solving the travelling salesman problem," Advances in Neural Information Processing Systems, vol. 36, 2024.
[14] Y. Ma, 7. Cao, and Y. M. Chee, "Learning search feasible and infeasible regions of routing problems with flexible neural k-opt," Advances in Neural Information Processing Systems, vol. 36, pp. 49 555-49 578, 2023.
[15] Y. Wu, W. Song, 7. Cao, J. 7hang, and A. Lim, "Learning improvement heuristics for solving routing problems," IEEE transactions on neural networks and learning systems, vol. 33, no. 9, pp. 5057-5069, 2021.
[16] S. Sanokowski, S. Hochreiter, and S. Lehner, "A diffuuson model framework for unsupervised neural combinatorial optimization," arXiv preprint arXiv:2406.01661, 2024.
[17] O. Vinyals, M. Fortunato, and N. Jaitly, "Pointer networks," Advances in neural information processing systems, vol. 28, 2015.
[18] B. Hudson, Q. Li, M. Malencia, and A. Prorok, "Graph neural network guided local search for the traveling salesperson problem." in International Conference on Learning Representations, 2022. [Online]. Available:
[19] Z.-H. Fu, K.-B. Qiu, and H. Zha, "Generalize a small pre-trained model to arbitrarily large tsp instances." in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 2021, pp. 7474-7482.
11

---

[20] F. Luo, X. Lin, F. Liu, Q. Zhang, and Z. Wang, "Neural combinatorial optimization with heavy decoder: Toward large scale generalization." Advances in Neural Information Processing Systems, vol. 36, 2024.
[21] Z. Sun and Y. Yang. "DIFUSCO: Graph-based diffusion solvers for combinatorial optimization." "
in Thirty-seventh Conference Neural Information Processing Systems, 2023. [Online]. Available:
VVFIDlgVV
[22] D. Drakulic, S. Michel, F. Mai, A. Sors, and J.-M. Andreoli, "Bq-neo: Bisimulation quotienting for efficient neural combinatorial optimization," Advances in Neural Information Processing Systems, vol. 36, pp. 77 47416-77 429, 2023.
[23] D. Zhang, H. Dai, N. Malkin, A. Courville, Y. Bengio, and L. Pan, "Let the flows tell: Solving graph combinatorial optimization problems with gilownets," " arXiv preprint arXiv:2305.17010 2023.
[24] Y. Li, J. Guo, R. Wang, H. Zha, and J. Yan, "Fast 12t: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization." Advances in Neural Information Processing Systems, 2024.
[25] A. Hottung, B. Bhandari, and K. Tiemeyy "Learning latent search space for routing problems using variational autoencoders," " in International Conference on Learning Representations. 2021.
[26] F. Chalumeau, S. Surana, C. Bonnet, N. Grinsztajn, A. Pretorius, A. Laterre, and T. Barrett, "Combinatorial optimization with policy adaptation using latent space search," Advances in Neural Information Processing Systems, vol. 36, pp. 7947-7959, 2023.
[27] Zhou, Y. Wu, Z. Cao, W. Song, Zhang, and Z. Shen, "Collaboration! towards robust neural methods for routing problems," arXiv preprint arXivv2440.0444 10.04668, 2024.
[28] S. Geisler, Sommer, J. Schuchardt, A. Bojchevski, and S. Günnemann, "Generalization of neural combinatorial solvers through the lens of adversarial robustness," in International Conference on Learning Representations, 2022.
[29] Y. Xia, X. Yang, Z. Liu, Z. Liu, L. Song, and J. Bian, "Position: Rethinking post-hoc search- based neural approaches for solving large-scale scale traveling salesman problems," arXiv preprint arXiv:2406.00 03500, 2024.
[30] R. Wang, Z. Guo, S. Jiang, X. Yang, and J. Yan, "Deep learning of partial graph matching via differentiable top-k," in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2023, pp. 6272-6281.
[31] R. Wang. Y. Li, J. Yan, and X. Yang. "Learning to solve combinatorial optimization under posi- tive linear constraints via non-autoregressive neural networks," arXiv preprint arXhv:2409.044999 2024.
[32] X. Zheng, Y. Li, C. Fan, H. Wu, X. Song, and J. Yan, "Learning plaintext-ciphertext crypto- graphic problems via anf- based sat instance representation," Advances in Neural Information Processing Systems, 2024.
[33] P. R. d O Costa, J. Rhuggenaath, Y. Zhang, and A. Akcay, "Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning," " in Asian Conference on Machine Learning, 2020, pp. 465-480.
[34] X. Chen and Tian, "Learning to perform local rewriting for combinatorial optimization," Advances in Neural Information Processing Systems, vol. 32, 2019.
[35] S. Li, Z. Yan, and C. Wu, "Learning to delegate for large-scale vehicle routing," Advances in Neural Information Processing Systems, vol. 34, pp. 26 198-262211 26,11,
[36] Q. Hou, J. Yang. Y. Su, X. Wang, and Y. Deng, "Generalize learned heuristics to solve large- scale vehicle routing problems in real-time," in The Eleventh International Conference on Learning Representations, 2023.
[37] Z. Zong, H. Wang, Wang, M. Zheng, and Y. Li, "Rbg: Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning," in Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022. pp. 4648-4658.
[38] Q Hou, J. Yang. Y. Su, X. Wang, and Y. Deng, "Generalize learned heuristics to solve large- scale vehicle routing problems in real-time," The Eleventh International Conference on Learning Representations, 2023.
12

---

[39] H. Ye, J. Wang, H. Liang, Z. Cao. Y. Li, and F. Li, "Glop: Learning global partition and local construction for solving large-scale routing problems in real-time," in Proceedings of the AAAI Conference Artificial Intelligence, vol. 38, no. 18, 2024, pp. 204-2420 292.
[40] Z. Zheng, C. Zhou, T. Xialiang, M. Yuan, and Z. Wang, "Ude: A unified neural divide- and-conquer framework for large-scale combinatorial optimization problems." arXiv preprint arXiv:2407.00312 2024.
[41] F. Luo, X. Lin, Y. Wu, Z. Wang. T. Xialiang, M. Yuan, and Q. Zhang, "Boosting neural combi- natorial optimization for large-scale vehicle routing problems," in The Thirteenth International Conference on Learning Representations.
[42] Y. Li, J. Ma, W. Pan, R. Wang, H. Geng, N. Yang, and J. Yan, "Unify ml4tsp: Drawing methodological principles for tsp and beyond from streamlined design space of learning and search," in International Conference on Learning Representations, 2025.
[43] H. Geng, H. Ruan, R. Wang. Y. Li, Y. Wang. L. Chen, and J. Yan, "Benchmarking pto and pno methods in the predictive combinatorial optimization regime," Advances in Neural Information Processing Systems, vol. 37, pp. 65 944-6946 65 971, 2024.
[44] F. Berto, C. Hua, J. Park, L. Luttmann, Y. Ma, F. Bu, J. Wang. H. Ye, M. Kim, S. Choi, N. G. Zepeda, A. Hottung. J. Zhou, J. Bi, Y. Hu, F. Liu, H. Kim, J. Son, H. Kim, D. Angioni, W. Kool, Z. Cao, J. Zhang, K. Shin, C. Wu, S. Ahn, G. Song, C. Kwon, L. Xie, and J. Park, "RLACO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark," in Proceedings of the s1 ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
[45] Ma, W. Pan, Y. Li, and Yan, "MI4co-bench- 101: Benchmark machine learning for classic combinatorial problems on graphs," in Advances in Neural Information Processing Systems, 2025.
[46] Y. Li. Y. Mo, L. Shi, and J. Yan. "Improving generative adversarial networks via adversarial learning in latent space," in Advances in Neural Information Processing Systems, 2022.
[47] Y. Li, L.. Shi, and J. Yan, "lid-gan: an iid sampling perspective for regularizing mode collapse." in International Joint Conference on Artificial Intelligence, 2023.
[48] Y. Li, J. Ma, Y. Yang, Q. Wu, H. Zha, and J. Yan, "Generative modeling reinvents supervised learning: Label repurposing with predictive consistency learning," in Forty-second International Conference Machine Learning, 2025.
[49] Y. Li, Z. Dong, Y. Sun, W. Wang. S. Xiong. Y. Luo, J. Liu, H. Lu, J. Wang, W. Su al., "Attention illuminates Ilm reasoning: The preplan-and and-anhhod rhythm enables fine-grained policy optimization," arXiv preprint arXiv:2510. 10. 13554, 2025.
[50] H. Wu, W. Liu, Y. Bian, J. Wu, N. Yang, and J. Yan, "Ebmdock: Neural probabilistic protein- protein docking via a diffcrentiable energy model," in The Twelfth International Conference on Learning Representationss 2024.
[51] H. Wu, X. Ye, and J. Yan, "Qvae-mole: The quantum vae with spherical latent variable learning for 3-d molecule generation," Advances in Neural Information Processing Systems, vol. 37, pp. 22 727--525 22 771, 2024.
[52] H. Wu, L. Li, H. Huang, T. Yi, J. Zhang, M. Yu, and J. Yan, "Hshare: Fast I1m decoding by hierarchical key-value sharing," in The Thirteenth International Conference on Learning Representations, 2025.
[53] J. Ma, W. Pan, Y. Li, and J. Yan, "Coexpander: Adaptive solution expansion for combinatorial optimization." " in The Forty-second International Conference on Machine Learning, 2025.
[54] W. Pan, H. Xiong, J. Ma, W. Zhao, Y. Li, and J. Yan, "Unico: On unified combinatorial opti- mization via problem reduction to matrix-encoded general tsp," in The Thirteenth International Conference on Learning Representations, 2025.
[55] Y. X. Chen, W. Guo, X. Li, W. Luo, J. Huang. H.-L. Zhen, M. Yuan, and J. Yan, "Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong sauuccure-hrrdnee aware baseline." in Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), 2023.
[56) X. Chen, Y. Li, R. Wang, and Yan, "Mixsatgen: Learning graph mixing for sat instance generation," in The Twelfth International Conference on Learning Representations, 2024.
13

---

[57] Z. Guo. Y. Li, C. Liu, W. Ouyang, and J. Yan, "Acm-milp: Adaptive constraint modification via grouping and selection for hurdness-preservin milp instance generation," in Forty-first International Conference on Machine Learning, 2024.
[58] J. Soo---oollssss Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli, "Deep unsupervised learning using nonequilibrium thermodynamics," " in International Conference on Machine Learning. 2015, pp. 2256-2265.
[59] Y. Song and S. Ermon, "Generative modeling by estimating gradients of the data distribution," Advances in neural information processing systems, vol. 32, 2019.
[60] J. Ho, A. Jain, and P. Abbeel, "Denoising diffusion probabilistic models," Advances in Neural Information Processing Systems, vol. 33, pp. 6840-6851, 2020.
[61] Song. C. Meng, and S. Ermon, "Denoising diffusion implicit models," arXiv preprint 200.050, 2020.
[62] Y. Song and S. Ermon, "Improved techniques for training score-based generative models," " Advances in neural information processing systems, vol. 33, pp. 12438-12 448, 2020.
[63] A. Q. Nichol and P. Dhariwal, "Improved denoising diffusion probabilistic models," in Interna- tional Conference on Machine Learning, 2021, pp. 8162-8171.
[64] Dhariwal and A. Nichol, "Diffusion models beat gans on image synthesis," Advances in Neural Information Processing Systems, vol. 34, pp. 3780-8794, 2021.
[65] Y. Song, J. fohk-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. "Score-based generative modeling through stochastic differential equations," arXiv preprint arXiv:2011.13450 2020.
[66] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg, "Structured denoising diffusion models in discrete state-spaces," " Advances in Neural Information Processing Systems, vol. 34, pp. 17 977981 993, 2021.
[67] E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling, "Argmax flows and multinomial diffusion: Learning categorical distributions," Advances in Neural Information Processing Systems, vol. 34, pp. 12 12 465, 2021.
[68] X. Liu, C. Gong, and Q Liu, "Flow straight and fast: Learning to generate and transfer data with rectified flow," arXiv preprint
2022.
[69] X. Liu, X. Zhang, J. Ma, J. Peng et al., "Instaflow: One step is enough for high-quality diffusion- text-to-image generation," " in The Twelfth International Conference on Learning Representations, 2023.
[70] Y. Lipman, R. T. Chen, H. Ben-Hamu, M. Nickel, and M. Le, "Flow matching for generative modeling," " arXiv preprint arXiv:2210.02747, 2022.
[71] M. S. Albergo and E. Vanden- Eijnden, "Building normalizing flows with stochastic interpolants." arXiv preprini arXiv:2209. (10009,,557/1 15571, 2022.
[72] A. Tong, K. Fatras, N. Malkin, G. Huguet, Y. Zhang, J. dector-Brooke G. Wolf, and Y. Bengio, "Improving and generalizing flow-based generative models with minibatch optimal transport," arXiv preprint 2rXiv 30280202..0...... 2023.
[73] N. Karalias and A. Loukas, "Erdos goes neural: an unsupervised learning framework for combinatorial optimization graphs," Advances in Neural Information Processing Systems, vol. 33, pp. 6679, 2020.
[74] H. Wang, N. Wu, H. Yang. C. Hao, and Li. "Unsupervised learning for combinatorial opti- mization with principled objective relaxation." in Advances in Neural Information Processing Systems, 2022.
[75] N. Ma. S. Tong, H. Jia, H. Hu, Y.-C. Su, M. Zhang, X. Yang, Y. Li, T. Jaakkola, X. Jia al., "Inference-time scaling for diffusion models beyond scaling denoising steps," arXiv preprint STti:25001097322 2025.
[76] Z. Qi. L. Bai, H. Xiong, and Z. Xie, "Not all noises are created equally: Diffussinn noise selection and optimization," arXiv preprint arXiv:2407.14400
2024.
[77] D. Ahn, Kang, S. Lee, J. Min, M. Kim, W. Jang, H. Cho, Paul, S. Kim, E. Cha et al., "A noise is worth diffusion guidance," arXiv preprint arX 2024.
14

---

[78] S. Lin and B. W. Kernighan, "An effective heuristic algorithm for the traveling-salesman salesman problem," Operations research, vol. 21, no. 2. pp. 498-516, 1973.
[79] D. Applegate, R. Bixby, V. Chvatal, and W. Cook, "Concorde tsp solver," 2006.
[80] K. Helsgaun, "An extension of the lin-kernihaan-heisaamn tsp solver for constrained traveling salesman and vehicle routing problems," Roskilde: Roskilde University, pp. 24-50, 2017.
[81] A. Hottung, Y.-D. Kwon, and Tiemey, "Efficient active search for combinatorial optimization problems," arXiv preprint
00560126, 2021.
[82] F. Luo, X. Lin, F. Liu, Q. Zhang, and Z. Wang, "Neural combinatorial optimization with heavy decoder: Toward large scale generalization," Advances in Neural Information Processing Systems, vol. 36, pp. 8845-8864, 2023.
[83] Z. Li, Q. Chen, and V. Koltun, "Combinatorial optimization with graph convolutional networks and guided tree search," Advances in neural information processing systems, vol. 31, 2018.
[84] S. Ahn, Y. Seo, and J. Shin, "Learning what to defer for maximum independent sets," in International Conference on Machine Learning, 2020, pp. 134-144.
[85] M. Böther, O. KiBig, M. Taraz, S. Cohen, K. Seidel, and T. Friedrich, "What's wrong with deep learning in tree search for combinatorial optimization," arXiv preprint arXiv:2201. 10494 2022.
[86] Erdós, A. Rényi et al., "On the evolution of random graphs," Publ. Math. Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17-60, 1960.
[87] S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck, "Finding near -ptrmoptimal indepen- dent sets scale," in 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2016, pp. 138-150.
[88] Gurobi Optimization, "Gurobi optimizer reference manual," http://www.gurobi.com 2020.
[89] H. Wang and Li, "Unsupervised learning for combinatorial optimization needs meta-learning." arXiv preprint 2rXiv:2330..3311, 2023.
[90] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song, "Learning combinatorial optimization algorithms over graphs," Advances in neural information processing systems, vol. 30, 2017.
[91] B. Hudson, Q. Li, M. Malencia, and A. Prorok, "Graph neural network guided local search for the traveling salesperson problem," arXiv preprint 2 2021.
15

---

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: The abstract and introduction explicitly state the claims made, including the contributions made in the paper (Sec. The claims match the experimental results in
Sec. 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
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 not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Appendix
Guidelines:
The answer NA means that the paper has 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer:
[NA]
Justification:
The paper does not include theoretical results.
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 or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The experimental details and model settings in Sec. and Appendix C We will make our source code publicly available upon acceptance.
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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
17

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes)
Justification:
The source code will be made publicly available htttps://github: com/
Sainklab-SJTU/Ger
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 be possible, so "No" is 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 NeurIPS code and data submission guidelines (https
/
Coaee//dddeSSbmmmcma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments 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 to the paper) 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:
The experimental details are in Sec. 5 and Appendix C
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 a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We follow the setting of previous works 90
1
25
19
12 21 29 to report the average solution quality 128 1,280 instances in Sec. 5
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, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
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 enror 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 range (e.g. negative enror 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 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: We provide the testing GPUs and cinecconsunttion our methods as well as
previous works in Sec. 5 The training resource requirement is in Appendix. D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttp:://neuriiii http://s.e..ppp..ttthhccccccleel
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the
NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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:
We discuss the borader impacts in 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.
19

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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 such risks.
Guidelines:
The answer NA means that the paper poses no 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 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. Licenses 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: The original papers that introduce models and datasets used in the paper cited in Sec. 5
Guidelines:
The answer NA means that the paper does use 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 (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
datasets.papersstt
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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: Currently, the paper does not release new assets. Our source code will be released upon the acceptance of the paper with comprehensive documents. As part documents, we formally describe our proposed model and the corresponding details.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: 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)?
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 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 NeurIPS 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
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
This paper does not incur such risks.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
21

---

Depending on 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 NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if 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.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
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 our LLM policy (https://neurips: hett::///eerrrps.ccc//ooeeereeee cc///onfereeeee//222////... for what should or should not be described.
22

---

Appendix
A Broad Impacts, Limitations and Future Work
This paper explores test-time scaling for generative neural solvers, demonstrating that generative models designed specifically with search-oriented scaling can significantly improve performance. Experiments show that the proposed algorithm achieves orders-of-magnitude improvements compared to state-of-the-ee machine learning solvers, and also exhibits notable ad advantages over LKH on TSP instances of size 500 and below. The algorithm reveals the great potential of neural network solvers to surpass the decades-refing mathematical heuristic algorithms like LKH on some classical problems that have been thoroughly studied.
Current limitations include that in larger-scale experiments, we observed that given more time, the improvement rate of GenSCO slows down, and eventually the improvement rate of LKH surpasses that of GenSCO. Maintaining an effective, continued search on larger-scale data is a target for future exploration. On the other hand, switching between neural network solvers and traditional solvers in a two-stage manner is a possible direction for further research. In generalization experiments, we found that the model suffers from performance degradation on certain hard TSPLIB instances, which impacts the average performance. Improving the robustness of neural network solvers is also future direction.
B Claim for the Utilization of Parallel GenSCO Operators
We note that the core logic of our methodology is: 1) to explore a new solving paradigm (generation search operator) that offers better scaling effects, and 2) to maximize the use of the proposed operator to significantly boost solving performance. In this design, the neural network's 's role is lightweight, with low number of inference steps per generation, which is designed reallocate the computation to more search cycles. Compared to previous methods that rely on the accuracy of single- round heavy generation, GenSCO's single neural network inference has low GPU computational density. Parallelism is necessary to ensure GenSCO fully utilizes the available GPU power, making the computational cost comparable other methods that rely on "heavy" networks for single model inference.
Thus, the results reported in the main experiments reflect the parallel execution of GenSCO operators. Here, []slos results for 1, 2, and 4 parallel operators to show the effect of varying parallel runs. As even with the num runs=1 setting, GenSCO still significantly outperforms other baselines (without full GPU utilization).
Table 6: Ablation studies of GenSCO with different parallel runs on TSP-500 and 100-
Runs
TSP-500
TSP- 1000
Method
Obj.
Gap (%)
Time (s)
Obj.
Gap (%)
Time (s)
16.550
0.028
2.408
23.137
0.083
7.609
2
16.549
0.021
4.383
23.133
0.065
12.372
GenSCO (C=40)
16.548
0.016
9.248
23.130
0.053
164
8
16.548
0.013
17.974
23.129
0.047
47.468
16.549
0.021
4.365
23.134
0.067
14.012
16.549
0.016
8.333
23.131
0.055
23.834
GenSCO (C=80)
4
16.548
0.012
17,904
23.129
0.047
47.327
8
16.548
0.011
35.541
23.127
0.040
93.989
16.548
0.016
8.226
23.131
0.056
27.741
16.548
0.013
16.160
23.129
0.047
46.770
GenSCO (C-160) 60)
16.548
0.011
35.375
23.128
0.041
93.904
16.548 8
0.010
70.923
23.126
0.034
187.634
23

---

C Supplementary Experiments
C.1 Results on TSP Soald Data
Results on TSPLIB 50-200. We evaluate our model trained with random 100-node problems on real-world TSPLIB instances with 50-200 nodes. The compared baselines include DIFUSCO [2]], T2T [9), Fast 12T
24, and baselines listed in 's Table 3. The hyperparameter settings of the compared baselines are: DIFUSCO: 1,=50; T2T: T,=50 and Tg=30; GenSCO (w/o GS): T,=10; Fast T2T (w/ GS): 1,=10 and Ig=10; GenSCO: we adopt 4 inference steps in one generation round, 200 search cycles, and 16 operators in parallel. The diffusion- bassod methods are compared in the same settings with greedy decoding and Two-Opt post-processing. For each instance, we normalize the coordinates [0,1]. The results are presented Table
Results on TSPLIB 200-1000. We also supplement the results (optimality drop) of diffusion-basee baselines and GenSCO on large-scale TSPLIB benchmark instances with 200-1000 nodes. The models are trained on TSP-500 and inference with greedy decoding and Two-Opt vost-processing. For each instance, normalize the coordinates [0,1]. The results presented in Table g
Table 7: Solution quality for methods trained random 100-node problems and evaluated TSPLIB instances with 50-200 nodes. denotes results quoted from previous works [T].
INSTANCES
AM*
GCN
Lear20PTT
GNNGLS
DIFUSCO
T2T
Fast T2T
GenSCO
eilS1 16.767%
40.025%
1.725%
1.529%
2.82%
0.14%
0.00%
0.000%
herlin52
4.169%
33.225%
0.449%
0.142%
0.00%
0.00%
0.00%
0.000%
st70
1.737%
24.785%
0.040%
0.764
0.00%
0.00%
0.00%
0.000%
ci176
1.992%
27.411%
0.096%
0.163%
0.34%
0.00%
0.00%
0.000%
pr76
0.816%
27.793%
1.228%
0.039%
1.12%
0.40%
0.00%
0.000%
ra199
2.645%
17.633%
0.123%
0.550%
0.09%
0.09%
0.00%
0.000%
KroA 100
4.017%
28.828%
18.313%
0.728
0.10%
0.00%
0.00%
0.000%
kroB 100
5. 5.142%
34.686%
1.119%
0.147%
2.29%
0.74%
0.65%
0.000%
kroC100
0,972%
35.506%
0.349%
1,571%
0.00%
0.00%
0.00%
O. 0.000%
kroD100
2.717%
38.018%
0.866%
0.572%
0.07%
0.00%
0.00%
0.000%
kroF100
1.470%
26.589%
1.832%
1.216%
3.83%
0.27%
0.00%
O. 0.000%
rd100
3.407%
50.432%
1.725%
0.003%
0.08%
0.00%
0.00%
0. 0.000%
eil101
2.994%
26.701%
0,387%
1,529%
0.03%
0.00%
0.00%
0. 2..00%
lin
1.739%
34,9025
1.867%
0.606%
0.00%
0.00%
0.00%
0.000%
pr107
3.933%
80.564%
0.898%
0.439%
0.91%
0.61%
0.62%
0.000%
1r1
3.677%
70.146%
10.322%
0.755%
1.02%
0.60%
0.08%
0.000%
bier
5.908%
45.561%
3.044%
1.948%
0.94%
0.54%
1.50%
0 0.000%
ch130
3.182%
39,090%
0.709%
3.519%
0.29%
0.06%
0.00%
O 0.000%
pr136
5.064%
58.673%
0.000%
3.387%
0.19%
0. 10%
0.01%
0.000%
pr144
7.641%
55.837%
1.526%
3.581%
0.80%
0.50%
0.39%
O. 0.000%
ch150
4.584%
49,743%
0.312%
2.113%
0.57%
0.49%
0.00%
O. 0.000%
kroA150
3.784%
45.411%
0.724%
2.984%
0.34%
0.14%
0.00%
0.000%
kroB 150
2.437%%
56.745%
0.886%
3.258%
0.30%
0.00%
0.07%
0.340%
pr152
7.494%
33.925%
0.029%
3.119%
1.69%
0.83%
0.19%
0. 0.187%
u159
7.551%
38.338%
0.054%
1.020%
0.82%
0.00%
0.00%
O. 0.000%
1at
6.893%
24.968%
0.743%
1.666%
1.48%
1.27%
0.79%
0. 194%
d198
373.020%
62.351%
0.522%
4.772%
3.32%
1.97%
0.86%
0.751%
kroA200
7.106%
40.885%
1.441%
2.029%
2.28%
0.57%
0.49%
0.160%
kroB200
8.541%
43.643%
2.064%
2.589%
2.35%
0.92%
2.50%
0. 0.098%
Mean
16.767%
40.025%
1.725%
1.529%
0.97%
0.35%
0.28%
0.061 %
C.2 Ablation Study on the Flow Modeling
Table 9 compares the flow model and the consistency model (from the state-of-the-an art Fast T2T 24) on TSP-500 under the same implementation and number of forward function evaluations (NFE). We treat the consistency model as an alternative diffusion model variant and enhance its competitiveness by applying more 2-opt cycles, though at the cost of increased runtime. The results demonstrate the effectiveness of our proposed flow model over the previous consistency model design.

---

Table 8: Solution quality for methods trained on random 500-node problems and evaluated on
TSPLIB instances with 200-1000 nodes.
INSTANCES
DIFUSCO
T2T
Fast T2T
GenSCO
a280
1.39%
1.39%
0.10%
0.000%
d493
1.81%
1.81%
1.43%
3.872%
d657
4.86%
2.40%
0.64%
0,457%
f1417
3.30%
3.30%
2.01%
0.596%
gil262
2.18%
0.96%
0.18%
0.000%
lin318
2.95%
1.73%
1.21%
0.025%
1
2.17%
1.11%
0.78%
0.025%
p654
7.49%
1.19%
1.67%
1.023%
pch442
2.59%
1.70%
0.61%
0.015%
pr226
4.22%
0.84%
0.34%
0.211%
pr264
0.92%
0.92%
0.73%
0.000%
pr299
1.46%
1.46%
1.40%
0.01 1%
pr439
2.73%
1.63%
0.50%
O. 106%
rat575
2.32%
1.29%
1.43%
0.000%
rat783
3,04%
1.88%
1.03%
0.068%
rd400
1.18%
0.44%
0.08%
0.030%
Is225
4.95%
2.24%
1.37%
0.517%
2sp225
3,25%
1.69%
0.81%
0.000%
u574
2.50%
1.85%
0.94%
O. 1.99%
u724
2.05%
2.05%
1.41%
0.040%
Mean
2.87%
1.59%
0.93%
0.355%
Table 9: Ablation studies of diffusion modeling design choices on TSP-500.
NFE=40
NFE=80
NFE=160
Method
Obj.
Gap
Time
Obj.
Gup
Time
Obj.
Gap
Time
Consistency
16.598
0.313%
7s
16.590
0.265%
14s
16.584
0.233%
28s
Consistency 24
20pt
16.550
0.028%
23s
16.549
0.022%
46s
16.549
0.021% %
1m33s
Flow
16.550
0.023%
5s
16.549
0.020%
9s
16.548
0.016%
18s
Flow 20pt
16.549
0.019%
5s
16.548
0.016%
9s
16.548
0.012%
18s
C.3
Ablation Study on the Architecture Choices
Table 10 compares different architecture choices within GenSCO to show the effectiveness of the proposed Transformer architecture compared to the classic Graph Convolutional Network (GCN). We reimplement the GCN following the specific settings in DIFUSCO [1] and Fast T2T [24 as an alternative backbone for the flow model. The GCN implementation takes much more runtime for the same iterations, and the efficiency of the proposed Transformer architecture allows for the maximization of the scaling benefits.
Table 10: Ablation studies architecture choices on TSP-500 and TSP-1000.
TSP-500
TSP- 1000
Method
Obj.
Gap
Time
Obj.
Gap
Time
GenSCO (C=40) with GCN
16.556
0.060%
1m45s
23.157
0.167%
6m50s
GenSCO (C=40) with Transformer
16.549
0.019%
Ss
23.133
0.063%
16s
GenSCO (C=80) with GCN GenSCO (C 80) with Transformer
16.553
0.045%
3m25s
23.147
0.127%
13m40s
16.548
0.016%
9s
23.131
0.054%
30s
GenSCO (6) with GCN GenSCO (C=10 (60) with Transformer
16.552
0.037%
6m.50
23.140
0.097%
27m20s
16.548
0.012%
18s
23.129
0.046%
58s
C.4 Ablation Study on the Augmentation Technique
In the implementation, at each search cycle, we apply symmetric transformation to the instance, such rotating the coordinates. This operation increases the diversity of the model prediction during
25

---

the intermediate process, ensuring the continuity of exploration ability throughout the search. We conduct an ablation study on this trick in Table
Table 11: Ablation study of the augmentation technique on TSP-100 and 500.
TSP-100
(1280 inst.
TSP-500
(128 inst.)
Method
Obj.
Gap
Time
Obj.
Gap
Time
GenSCO (C=10) w/ aug.
7.76
0.000%
6s
16.55
0.023%
5x
w/o aug.
7.76
0.004%
6s
16.55
0.047%
58
GenSCO (C=20) w/ aug-
7.76
0.000%
12s
16.55
0.020%
9s
w/o aug.
7.76
0.003%
12s
16.55
0.040%
9s
GenSCO 4C=40) aug.
7.76
0.000%
24s
16.55
0.016%
18s
w/o aug.
7.76
0.003%
24s
16.55
0.031%
18s
GenSCO (C=10) 20pt w/ aug.
7.76
0.000%
6s
16.55
0.019%
5s
w/o aug-
7.76
0.003%
6s
16.55
0.037%
58
GenSCO (C=20) 20pt w/ aug.
7.76
0.000%
16.55
0.016%
9s
w/o aug-
7.76
0.003%
16.55
0.032%
98
GenSCO (C=40) 20pt w/ aug.
7.76
0.000%
24s
16.55
0.012%
18s
w/o aug.
7.76
0.003%
24s
16.55
0.026%
18s
C.5 Ablation Study the Disruption Operator
In the implementation, each search cycle, apply disruption operator the obtained solutions to escape from local optima and achieve continuous improvement. Table [2] shows the results of GenSCO with and without the disruption operator. Without the disruption operator, observe varying degrees of performance degradation, especially on TSP500, where the gains from increasing search cycles show significant stagnation.
Table 12: Ablation study of the disruption operator on TSP-100 and 500.
TSP-100
TSP-500
Method
Obj.
Gap
Obj.
Gap
GenSCO (C=40) w/ disruption
16.549
0.019%
23.133
0.063%
w/o disruption
16.551
0.033%
23.137
0.083%
GenSCO (C=80) w/ disruption
16.548
0.016%
23.131
0.054%
w/o disruption
16.551
0.032%
23.134
0,067%
GenSCO (6=160) w/ disruption
16.548
0.012%
23.129
0.046%
w/o disruption
16.551
0.032%
23.131
0.056%
C.6 Ablation Study the Number of Sampling Steps
Table 13 shows the effect of varying the number of sampling steps for GenSCO. We observe that increasing the number of sampling steps generally improved performance for GenSCO with different numbers of cycles, though the gains diminished in later stages. We ultimately chose T 4 and allocated more computational resources to scaling the number of cycles.
Table 13: Ablation studies of the number of sampling steps on TSP-500.
C=40
C=80
C=160
T
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
16.561
0.091%
8.06s
16.558
0.072%
15.54s
16.556
0.059%
31.47s
16.549
0.018%
8.34s
16.549
0.017%
16.33s
16.548
0.015%
32.
16.548
0.013%
18.38s
16.548
0.011%
35.56s
16.548
0.010%
70.62s
6
16.548
0.013%
26.88s
16.548
0.011%
53.35s
16.547
0.009%
106.26s
8
16.548
0.012%%
35.60s
16.547
0.010%
70.66s
16.547
0.009%
140.92s
26

---

C.7 Visualization of the Generation
Fig. shows the interpolation achieved by neural predictions between suboptimal solution and the optimal one, which is typical process in inference. In the inference process, the search operator first disrupts the solution with random local search operators and then conducts the flow sampling process. As corresponding to this specific process, Fig. 5 presents the interpolation achieved by neural predictions between a disrupted suboptimal solution and the optimal one. Fig. 4 shows Flow-bat based interpolation between intermediate state (lying between suboptimal and the optimal solution) and the optimal solution, which is typical process in training.
Step
Step
Step
Step 4
Figure 3: Flow-based interpolation between a suboptimal solution and the optimal one.
Step
Stop
Stop
Step
Figure 4: Flow-based interpolation achieved by neural predictions between disrupted suboptimal solution and the optimal one.
Step
Step
Step
Step
Step
Step
Step 7
Step 8
Figure 5: Flow-base interpolation between suboptimal solution and the optimal one.
27

---

D Experimental Details
D.1 Computational Resources.
All test evaluations are performed on single GPU of the NVIDIA RIX 4090. The training costs of GenSCO on TSP-100/500/1000 are 2 days, <= day, and day on GTX 4090 24G. For comparison, DIFUSCO [21] takes 8.6 days, 2.7 days, and 5.1 days for training an A100 GPU, respectively.
on
D.2 Design Choices and Hyperparameters
To ensure fair and thorough evaluation across problem scales, we run multiple experiments on 1SP- TSP-500, and TSP-1000 using certain fixed hyperparameters and random seeds.
Two-opt steps are scaled with problem size: we set two_ opt_sppss n/50, where n the number of nodes in the TSP instance. This results in 2 steps for TSP-100, 10 steps for TSP-500, and 20 steps for TSP-1000.
Randomized 2-opt search is applied with range proportional to problem size, using _art:o___t__op______ _range [n/4, 3n/4].
Robustness is ensured by repearing each setting with 5 different random seeds, and giving the final result as the average across these five runs.
Adjacent matrix heatmap filtering selects top-k candidate edges using topk 20000 for TSP-500 and 1S0- and 5000 for TSP-100.
D.3 Datasets.
The reference solutions for TSP-100/500//000 are labeled by the Concorde exact solver [79]. The test for TSP-50/100) is taken from [ & with 1280 instances, and the test set for TSP-500/1000 is from 19 with 128 instances for the fair comparison.
The reference solutions for both RB graphs and ER graphs are labeled with KaMIS 87 For RB graphs, we randomly generate 90000 instances for the training set and 500 instances for the test set. For ER graphs, randomly generate 163840 instances for the training set, and the test is from [2]
D.4 Baseline Settings
The generative baselines are compared in the same running settings, while the results of other baselines are quoted from the best achieved results of their original papers.
D.4.1 TSP Benchmarks
In the evaluation of 100-500/00//00, we compare our proposed GenSCO against 15 baseline methods.
These baselines include exact solver, i.e., Concorde [79]; one heuristic solver, i.e., LKH-3 [80]:
nine non generative learning-base based solvers, i.e., AM []] POMO (2). POMO+EAS 81]
GCN [8]
DIMES [12]. LEHD 20). BQ-NCO [22] GLOP 39 and UDC 40) COExpander 53 and three
generative learning-basse baaed solvers, i.e., DIFUSCO
21 T2T 9 and Fast T2T 24]. These learning-
based methods can be further categorized into supervised learning (SL. and reinforcement learning (RL). Post-processing techniques employed encompass greedy decoding (Grdy, G), multiple sampling (S), 20pt refinement (2Opt), beam search (BS), active search (AS), and combinations thereof. We cap the number of inference steps for DIFUSCO at 100. For T2T, we fix the number of inference steps and guided search steps at 50 and 30, respectively. For Fast T2T, we fix the number of inference steps and guided search steps at 5 and 5, respectively.
D.4.2 MIS Benchmarks
We assess our method on two distinct benchmarks: RB-[200-300) and ER-[700-800), Across both benchmarks, we compare the performance of GenSCO against one exact solver, Gurobi [8 one heuristic solver, KaMIS 87 and learning-based frameworks: Intel [3] DGL.
LwD
DIMES 12), GFlowNets (23] DIFUSCO (21) T2T 19), and Fast T2T
24
These learning- based
28

---

methods can be further categorized into supervised learning (SL), reinforcement learning (RL), and unsupervised learning (UL). Post-processing strategies encompass greedy decoding (G), multiple sampling (S), and tree search (TS). Specifically, steps at 100 for DIFUSCO. For T2T, we set the number of inference steps and guided search steps at 50 and 30, respectively. For Fast T2T, we set the number of inference steps and guided search steps at and respectively.
both benchmarks, we set the number of inference
D.4.3 MCI Benchmarks
We assess our method on two distinct benchmarks: RB-[200-300] and [R-[800-1200], Across both benchmarks, we compare the performance of GenSCO against one exact solver, Gurobi [88]. and three bearningbbssed frameworks: Meta-EGN [89], DiffUCO [6), COExpander [53]. These learning-base based methods can be further categorized into supervised learning (SL) and unsupervised learning (UL).
E
Network Architecture Details
E.1 Network Architecture for TSP
Input Layer. The model takes raw features with dimensionality of 2 input, typically representing coordinate data. These raw inputs are first projected into a higher-dimensional embedding space via learnable linear layer. This initial projection maps the input the encoder's embedding dimension (default 256).
Attention Layers. The architecture comprises encoder-decoder Transformer. The encoder has 16 Transformer layers with attention heads, 256-dim hidden states. Feed-forwan layers use SwiGLU activations. The decoder has 6 layers with similar settings.
Output Layer. The output generated through MLP block that projects the decoder embeddings back into the model's 's embedding space. The logit representing the connection between two different nodes with transformed embeddings h and lig is computed via inner product (M1, hv2).
E,2 Network Architecture for MIS and MCI
The model accepts adjacency matrices representing graph connectivity. Initial node features are sampled from a standard normal distribution and linearly projected into the encoder embedding space. This initial embedding dimension (default 256) sets the feature size for subsequent Transformer encoding.
Input Layer.
We omit the encoder for MIS. The decoder uses 256-dimensional embeddings and 4 attention heads, with 12 and 8 layers employed for RB and ER graphs, respectively.
Attention Layers.
Output Layer. The model employs sigmoid output head, which applies a sigmoid activation to scalar logits produced by an MLP to generate predictions.
29


Reviews:
[{"review_id": "JQWrLVh7sV", "reviewer": "Reviewer_1QVA", "summary": "This paper introduces GenSCO, the key idea is to start from suboptimal solutions (not random noise) and train the model to recover the optimal solution. This change allows the model to explore a smaller, more relevant part of the solution space, leading to better performance. Experiments on TSP and MIS problems show that GenSCO outperforms strong baselines in both quality and speed.", "questions": "- Since the new method requires meaningful disruption of existing solutions and the way to achieve this is problem dependent, how could the proposed method be possibly applied to broader CO problems beyond TSP and MIS to improve its generality?\n- Is there any ablation study to analyze how much each part of the system (e.g., flow model, search cycles, architecture) contributes to the final result?\n- In Section 3.2, during each search cycle, the disruption rate for MIS seems to be an arbitrary constant from 25% to 40%. Is there any reasoning or justification on how the disruption rate is set?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- New training setup: training the model to go from suboptimal to optimal solutions (instead of noise to solution) is a clever shift that makes the search more efficient.\n- Strong results: GenSCO beats both neural baselines and classic solvers like LKH3 in quality and runtime on multiple problem sizes.\n\nWeaknesses\n- Table formatting and precision: some tables like Table 1 show the same objective value but different optimality gaps, which is confusing.\n- Limited problem coverage: the experiments focus only on TSP and MIS. These are standard, but don’t show how the method works on other types of problems.\n- No component ablation: it’s unclear how much each part of the system (e.g., flow model, search cycles, architecture) contributes to the final result.", "was_revised": true, "final_justification": "The authors have thoroughly addressed the major concerns raised in the review. The paper is solid with additional experiment and ablation study", "rebuttal": "Thanks for the valuable comments, nice suggestions, and for acknowledging our work. Below we respond to your comments.\n\n---\n\n### ***160× Faster Than Gurobi with -0.06% Gap! Supplementary Experiments on a New Problem: Max Clique***\n\nAt the beginning of the rebuttal, we would like to present an additional experiment evaluating GenSCO on the Max Clique problem to demonstrate its generality (as suggested by the reviewers), which we believe would be another firm empirical support of our methodology. **We are indeed very surprised to find that our method outperforms existing state-of-the-art learning-based and classic solvers on this problem by a large margin, and it did so with little hyper-parameter tuning.** We believe this strongly supports the versatility of our approach. The results are as follows:\n\n|   | | RB-Small  || | RB-Large  | |\n| - | - | - | - | - | -| -|\n| **Method**  | **Obj.↑** | **Drop↓** | **Time↓** | **Obj.↑** | **Drop↓** | **Time↓** |\n| Gurobi  | **19.08***    | **0.00%**     | **7.5m**      | **40.18***    | **0.00%**     | **38.4h**     |\n| Meta-EGN [1]  | 17.51     | 8.30%     | 2.3m      | 33.79     | 15.49%    | 4.5m      |\n| DiffUCO [2] | 16.21     | 12.53%    | 11.8m     | --        | --        | --        |\n| COExpander [3] more steps | 19.00     | 0.50%     | 5.4m      | 39.06     | 2.99%     | 53.0m     |\n| COExpander [3] bs | 18.98     | 0.68%     | 30s       | 39.88     | 0.90%     | 3.1m      |\n| GenSCO (C=500) | 19.08     | 0.03%     | 1.1m      | 40.18     | 0.01%     | 6.9m      |\n| GenSCO (C=1k) | **19.08**     | **0.00%**     | **2.2m**      | **40.20**     | **-0.06%**    | **13.8m**    |\n\nFor the Maximum Clique problem, we compared our method against baselines using the best parameters reported in their original papers. For Gurobi, we imposed a time limit of 300 seconds per instance. All methods are evaluated over a total of 500 instances and other experimental settings exactly follow COExpander [3].\n\n**We are very surprised to find that GenSCO not only closes the gap to the powerful Gurobi solver but surpasses its solution quality with a -0.06% relative gap on the RB-Large dataset, while being over 160× faster computationally.** Compared to other learning-based solvers, this outcome marks a step-change, order-of-magnitude improvement. From the perspective of the gap metric, it has reduced the learning-based solvers' performance by an infinite-fold margin (from 0.90% to -0.06%).\n\n---\n\n> **Q1: Table formatting and precision: Table 1 shows the same objective value but different optimality gaps.**\n\nThe value discrepancy in Table 1 arises from numerical precision. The objective values in the table are rounded to two decimal places for presentation, whereas the optimality gaps are calculated using the full-precision values.\n\nFor instance, consider the TSP-100 dataset, where the optimal solution is 7.75585. A solution with a length of 7.756 and another with 7.764 would both be displayed as \"7.76\" after rounding. However, their true difference is accurately captured by the optimality gap, which is calculated with the unrounded values, resulting in gaps of 0.002% and 0.105%, respectively.\n\n\n> **Q2: Limited problem coverage: the experiments focus only on TSP and MIS. These are standard, but don’t show how the method works on other types of problems.**\n\nThanks for the advice. To demonstrate the generality of our method, we conducted additional experiments on a new problem, the Maximum Clique Problem, within the limited rebuttal period. Please refer to the full results at the beginning of the rebuttal.\n\n\n> **Q3: Is there any ablation study to analyze how much each part of the system (e.g., flow model, search cycles, architecture) contributes to the final result?**\n\nThanks for the nice advice. We supplement ablation studies as follows, and we will include all these results in our paper.\n\n1. **Flow model vs. consistency model (Fast T2T [4])**\n\nWe compare the flow model and the consistency model on TSP-500 under the same implementation and number of forward function evaluations (NFEs). We treat the consistency model as an alternative diffusion model variant and enhance its competitiveness by applying more 2-opt cycles, though at the cost of increased runtime. The results demonstrate the effectiveness of our proposed flow model over the previous consistency model design.\n\n\n| NFEs | Method | Obj. | Gap | Time |\n| :--- | :--- | :--- | :--- | :--- |\n| 40 | Consistency | 16.598 | 0.313% | 7s |\n|  | Consistency 2opt | 16.550 | 0.028% | 23s |\n|  | Flow | 16.550 | 0.023% | 5s |\n|  | Flow 2opt | 16.549 | 0.019% | 5s |\n| 80 | Consistency | 16.590 | 0.265% | 14s |\n|  | Consistency 2opt | 16.549 | 0.022% | 46s |\n|  | Flow | 16.549 | 0.020% | 9s |\n|  | Flow 2opt | 16.548 | 0.016% | 9s |\n| 160 | Consistency | 16.584 | 0.233% | 28s |\n|  | Consistency 2opt | 16.549 | 0.021% | 1m33s |\n|  | Flow | 16.548 | 0.016% | 18s |\n|  | Flow 2opt | 16.548 | 0.012% | 18s |\n\n\n2. **Effect of Search Cycles**\n\nPlease refer to GenSCO results in Table 1 and Table 4, where we report the solving performance and runtimes of GenSCO with varying search cycles. As shown, scaling search cycles results in stable improvements.\n\n\n3. **Architecture: Transformer vs. GCN**\n\nWe implement the GCN following the specific settings in DIFUSCO [5] and Fast T2T [4] as an alternative backbone for the flow model. The GCN implementation takes much more runtime for the same iterations, and the efficiency of the proposed Transformer architecture allows for the maximization of the scaling benefits.\n\n\n| Method| Backbone| TSP-500| TSP-1000|\n| ----- | -- | --- | --- |\n| GenSCO (C=40)  | GCN| 16.556, 0.060%, 1m45s | 23.157, 0.167%, 6m50s  |\n|| transformer | 16.549, 0.019%, 5s    | 23.133, 0.063%, 16s    |\n| GenSCO (C=80)  | GCN| 16.553, 0.045%, 3m25s | 23.147, 0.127%, 13m40s |\n|| transformer | 16.548, 0.016%, 9s    | 23.131, 0.054%, 30s    |\n| GenSCO (C=160) | GCN| 16.552, 0.037%, 6m50s | 23.140, 0.097%, 27m20s |\n|| transformer | 16.548, 0.012%, 18s   | 23.129, 0.046%, 58s    |\n\n\n\n> **Q4: Since the new method requires meaningful disruption of existing solutions in a problem-dependent way, how could the proposed method be possibly applied to broader CO problems beyond TSP and MIS to improve its generality?**\n\nOur method’s generality lies in its high-level algorithmic framework, as shown in Fig. 1, which can be applied to a wide range of COPs. To adapt methods to different problems, it is necessary and actually standard to customize specific components. In our framework, the primary problem-specific adaptations are the local search operators and the post-processing step. Importantly, these customizations don’t affect the core neural network training method or the overall framework's operation. For many classical COPs, mature local search operators already exist. Even when they don't, creating simple operators to disrupt solutions is straightforward (as we do in MIS). For the post-processing step, it can be simply set as greedy decoding.\n\nThis need for problem-specific adaptation is standard for various methods (you have to make adaptations for different problems for different inputs/constraints/characteristics). For a more closely related diffusion-based example, T2T [6] must construct a gradient source loss for different problems by converting the original objective and constraints. Similarly, it also needs to consider different architectures and post-processing methods. This also holds for methods like DIMES [7], DIFUSCO [5], Fast T2T [4] (architectures and post-processing), AM [8], POMO [9] (input processing and intermediate action space control).  Despite these required customizations, these ML algorithms are still considered general at the architectural level, and our method is no different.\n\nPlease see Q2 for the supplementary experiments on a new problem, Max Clique, which achieves advantages over existing state-of-the-art learning-based and classic solvers by a large margin.\n\n> **Q5: In Section 3.2, during each search cycle, the disruption rate for MIS seems to be an arbitrary constant from 25% to 40%. Is there any reasoning or justification on how the disruption rate is set?**\n\nThe disruption rate is a hyperparameter that controls the size of the local search neighborhood, which is crucial for maintaining search efficiency. The range of 25% to 40% was determined experimentally to be a relatively more effective range for MIS. An intuition for selecting this parameter is that we initially refer to the 25% - 75% 2opt disruption in TSP. Considering that flipping variables in MIS has a greater impact on the solution, a smaller upper limit for the disruption rate is chosen.\n\n---\n\nWe hope this response clarifies your understanding and fully addresses your concerns and that a more unified understanding and stronger consensus could be fostered regarding the value of our contribution to the community. Please do not hesitate to reach out with any additional questions or for further discussion. Thanks again for your valuable comments and suggestions.\n\n---\n\n[1] Unsupervised Learning for Combinatorial Optimization Needs Meta Learning. ICLR 2023.\n\n[2] A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML 2024.\n\n[3] COExpander: Adaptive Solution Expansion for Combinatorial Optimization. ICML 2025.\n\n[4] Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization. NeurIPS 2024.\n\n[5] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. NeurIPS 2023.\n\n[6] T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization. NeurIPS 2023.\n\n[7] DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. NeurIPS 2022.\n\n[8] Attention, Learn to Solve Routing Problems! ICLR 2019.\n\n[9] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS 2020."}, {"review_id": "eddGuElGlN", "reviewer": "Reviewer_5uKj", "summary": "This paper introduces GenSCO, a diffusion-based solver that treats generation as a search operator within the near-optimal solution space. Extensive experiments on classic TSP and MIS problems demonstrate the superiority of GenSCO.", "questions": "- Line 302 states that 8 GenSCO operators are run in parallel. I would like to know whether the runtimes reported in Table 1 and Table 4 reflect this parallel execution. If so, the comparison with other solvers may not be entirely fair.\n- Can authors provide more discussions on which other more complex combinatorial optimization problem GenSCO can solve? \n- GenSCO is a test-time scaling method. Why don’t you compare it with using Euclidean distance as prior information instead of a diffusion model, as done in [1]? I’m unsure about the effectiveness of the learning component, especially since neural methods are a primary focus of this conference.\n[1] Rethinking the \"Heatmap + Monte Carlo Tree Search'' Paradigm for Solving Large Scale TSP", "limitations": "Main limitations lie at the limited datasets for the comparison with the exiting works", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Novel Approach: The paper introduces a novel approach called GenSCO, which systematically exploits the learned distribution of high-quality solutions.\n- Computational results: The paper claims to GenSCO achieve significant speedup on TSP and MIS.\n\nWeaknesses:\n- Limited Benchmark Problems: While the authors present results on TSP and MIS benchmarks, it would be helpful to evaluate GenSCO on more complex combinatorial optimization problems to better demonstrate its generalizability.\n- There is a misspelled word in line 138.", "was_revised": true, "final_justification": "The additional materials have addressed my concerns and so I raised my score accordingly.", "rebuttal": "Thanks for the valuable comments, nice suggestions, and for acknowledging our work. Below we respond to your specific comments.\n\n---\n\n### ***160× Faster Than Gurobi with -0.06% Gap! Supplementary Experiments on a New Problem: Max Clique***\n\nAt the beginning of the rebuttal, we would like to present an additional experiment evaluating GenSCO on the Max Clique problem to demonstrate its generality (as suggested by the reviewers), which we believe would be another firm empirical support of our methodology. **We are indeed very surprised to find that our method outperforms existing state-of-the-art learning-based and classic solvers on this problem by a large margin, and it did so with little hyper-parameter tuning.** We believe this strongly supports the versatility of our approach. The results are as follows:\n\n|                          |           | RB-Small  |           |           | RB-Large  |           |\n| ------------------------ | --------- | --------- | --------- | --------- | --------- | --------- |\n| **Method**              | **Obj.↑** | **Drop↓** | **Time↓** | **Obj.↑** | **Drop↓** | **Time↓** |\n| Gurobi                   | **19.08***    | **0.00%**     | **7.5m**      | **40.18***    | **0.00%**     | **38.4h**     |\n| Meta-EGN [1]              | 17.51     | 8.30%     | 2.3m      | 33.79     | 15.49%    | 4.5m      |\n| DiffUCO [2]               | 16.21     | 12.53%    | 11.8m     | --        | --        | --        |\n| COExpander [3] more steps | 19.00     | 0.50%     | 5.4m      | 39.06     | 2.99%     | 53.0m     |\n| COExpander [3] bs         | 18.98     | 0.68%     | 30s       | 39.88     | 0.90%     | 3.1m      |\n| GenSCO (C=500)           | 19.08     | 0.03%     | 1.1m      | 40.18     | 0.01%     | 6.9m      |\n| GenSCO (C=1k)            | **19.08**     | **0.00%**     | **2.2m**      | **40.20**     | **-0.06%**    | **13.8m**    |\n\nFor the Maximum Clique problem, we compared our method against baselines using the best parameters reported in their original papers. For Gurobi, we imposed a time limit of 300 seconds per instance. All methods are evaluated over a total of 500 instances and other experimental settings exactly follow COExpander [3].\n\n**We are very surprised to find that GenSCO not only closes the gap to the powerful Gurobi solver but surpasses its solution quality with a -0.06% relative gap on the RB-Large dataset, while being over 160× faster computationally.** Compared to other learning-based solvers, this outcome marks a step-change, order-of-magnitude improvement. From the perspective of the gap metric, it has reduced the learning-based solvers' performance by an infinite-fold margin (from 0.90% to -0.06%).\n\n---\n\n> **Q1: Can authors provide more discussions on which other more complex combinatorial optimization problems GenSCO can solve?**\n\nSimilar to previous generative model solvers, our framework uses a \"heatmap + post-processing\" approach to solve problems. This framework can, in principle, be applied to any problem that meets the following two conditions:\n\n1. The decision variables are limited to a countable and finite set of values. This can cover edge-selecting problems like TSP, and node-selecting problems like MIS, Max Clique.\n2. A problem-specific post-processing procedure is required to transform the prediction into feasible solutions. This prerequisite can be easily met with the greedy decoding strategy, which sequentially inserts variables (edges or nodes) with the highest confidence if there are no conflicts.\n\nIn theory, any problem satisfying these conditions can be tackled by GenSCO. However, a limitation arises with problems that have highly complex constraints, such as CVRP. Our current approach relies on a combination of a \"soft\" constraint satisfaction learned by the model and a \"hard\" guarantee from the post-processing step. Since the model's prediction process doesn't explicitly incorporate constraints, the prediction accuracy can degrade when dealing with intricate dependencies. Improving our method to handle such complex constraints more effectively is a key direction for future work.\n\n\nTo demonstrate the generality of our method, we conducted additional experiments on a new problem, the Maximum Clique Problem, within the limited rebuttal period. Please refer to the results in the beginning of the rebuttal.\n\n\n\n> **Q2: Line 302 states that 8 GenSCO operators are run in parallel. I would like to know whether the runtimes reported in Table 1 and Table 4 reflect this parallel execution. If so, the comparison with other solvers may not be entirely fair.**\n\n\nThe runtimes reported in Tables 1 and 4 do reflect the parallel execution of 8 GenSCO operators. However, we note that the core logic of our methodology is: 1) to explore a new solving paradigm (generation as a search operator) that offers better scaling effects, and 2) to maximize the use of the proposed operator to significantly boost solving performance. In this design, the neural network's role is lightweight, with a low number of inference steps per generation, which is designed to reallocate the computation to more search cycles. Compared to previous methods that rely on the accuracy of single-round heavy generation, GenSCO's single neural network inference has a low GPU computational density. Parallelism is necessary to ensure GenSCO fully utilizes the available GPU power, making the computational cost comparable to other methods that rely on \"heavy\" networks for a single model inference.\n\nTo ensure full clarity, we will add a statement to the paper explaining this parallel execution. Here, we also include results for 1, 2, and 4 parallel operators to show the effect of varying parallel runs. As seen, even with the num_runs=1 setting, GenSCO still significantly outperforms other baselines (without full GPU utilization).\n\n| Cycles | runs | TSP-500 Obj. | TSP-500 Gap | TSP-500 Time(s) | TSP-1000 Obj. | TSP-1000 Gap | TSP-1000 Time(s) |\n| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |\n| **C = 40** | 1 | 16.550 | 0.028 | 2.408 | 23.137 | 0.083 | 7.609 |\n| | 2 | 16.549 | 0.021 | 4.383 | 23.133 | 0.065 | 12.372 |\n| | 4 | 16.548 | 0.016 | 9.248 | 23.130 | 0.053 | 24.164 |\n| | 8 | 16.548 | 0.013 | 17.974 | 23.129 | 0.047 | 47.468 |\n| **C = 80** | 1 | 16.549 | 0.021 | 4.365 | 23.134 | 0.067 | 14.012 |\n| | 2 | 16.549 | 0.016 | 8.333 | 23.131 | 0.055 | 23.834 |\n| | 4 | 16.548 | 0.012 | 17.904 | 23.129 | 0.047 | 47.327 |\n| | 8 | 16.548 | 0.011 | 35.541 | 23.127 | 0.040 | 93.989 |\n| **C = 160** | 1 | 16.548 | 0.016 | 8.226 | 23.131 | 0.056 | 27.741 |\n| | 2 | 16.548 | 0.013 | 16.160 | 23.129 | 0.047 | 46.770 |\n| | 4 | 16.548 | 0.011 | 35.375 | 23.128 | 0.041 | 93.904 |\n| | 8 | 16.548 | 0.010 | 70.923 | 23.126 | 0.034 | 187.634 |\n\n\n\n> **Q3: Why don’t you compare it with using Euclidean distance as prior information instead of a diffusion model, as done in [4]? I’m unsure about the effectiveness of the learning component, especially since neural methods are a primary focus of this conference.**\n\n\nThanks for the valuable question. First and foremost, we would like to clarify a key distinction. Paper [4] discusses the role of neural networks in augmenting strong search methods like MCTS. MCTS is a powerful technique, and introducing neural network predictions as a guidance mechanism doesn't always guarantee a significant, or even limited, improvement. In contrast, GenSCO is an end-to-end neural solver, aligning with established works like DIFUSCO [5], T2T [6], AM [7], and POMO [8]. These methods rely solely on learned representations, using only lightweight post-processing (e.g., greedy decoding or optional 2-opt for TSP).\n\nThe solving capability of GenSCO stems entirely from its learned neural representations. Unlike [4], there is no search framework (e.g., MCTS) to refine weak priors. Replacing the diffusion model with Euclidean distances would reduce the approach to nearest insertion (a naive baseline), leading to >20% performance gaps on TSP100, which would be unacceptable.\n\n---\n\nWe hope this response provides the clarity you were seeking and fully addresses your concerns. We would be truly grateful if, with further consideration, a more unified understanding and stronger consensus regarding the value of our contribution to the community could be fostered. We welcome any further questions and are available for additional discussion. Thanks again for your valuable comments and suggestions.\n\n---\n\n[1] Unsupervised Learning for Combinatorial Optimization Needs Meta Learning. ICLR 2023.\n\n[2] A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML 2024.\n\n[3] COExpander: Adaptive Solution Expansion for Combinatorial Optimization. ICML 2025.\n\n[4] Rethinking the \"Heatmap + Monte Carlo Tree Search\" Paradigm for Solving Large Scale TSP.\n\n[5] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. NeurIPS 2023.\n\n[6] T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization. NeurIPS 2023.\n\n[7] Attention, Learn to Solve Routing Problems! ICLR 2019.\n\n[8] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS 2020."}, {"review_id": "3eO44JzWqF", "reviewer": "Reviewer_sQhg", "summary": "The authors present an improvement on the use of ML-based traveling salesman and maximally independent set solvers where they frame the use of a denoising diffusion model as a search operation to quickly explore the surrounding energy landscape and choose a good next update for the classical iterative energy-based solver. The model achieves this by using a Neural ODE formulation of the probability flow that is modeled with a simple transformer to predict the velocity field in the probability space. It is demonstrated on various tasks how this approach overcomes the denoising-step bottlenecks that many other diffusion-based solvers suffer. In particular, the model generalizes to some degree across scales (i.e. training on simpler problems generalizes to more complicated ones) and it seems to have some robustness in regard to the quality of the low-energy solution provided as a target.", "questions": "1.) How does the computational cost scale compared with just doing more solver steps in terms of FLOPS and energy. How big is the solution quality improvement?\n\n2.) Regarding table 1: Why is GLOP and UDC not solved on TSP-100? Same for GenSCO in some cases? Can you elaborate on this?\n\n3.) Did you ever try other neural network/ML models instead of the transformer to model the distribution?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1.) The work requires only a limited number of denoising steps (3-4) to already provide a measurable improvement on the performance of a solver. The linear scaling with denoising steps is impressive.\n\n2.) The demonstration of the algorithm's ability to exceeding the plateau seems to be a major improvement over other data-driven/ML/DL-based solvers.\n\n3.) The demonstration of cross-scale generalization of the method is another big plus of the paper.\n\n\n**Weaknesses:**\n\n1.) It seems that DIFUSCO is the biggest competitor to the presented algorithm. I think an in-depth comparison of the compute requirements in terms of FLOPS would have been appropriate. Similarly for a fair comparison to non-ML based solvers, FLOPS would have been a better and fairer metric since the ML-based solvers benefit from a high degree of parallelization that classical solvers, which typically run on CPUs can not take advantage of. \n\n2.) Since the evaluations do not take too much time to run, it would have been nice to have 95% confidence intervals on measurement values since the performance of the solvers partially depend on the initialization of the starting point.", "was_revised": true, "final_justification": "All questions were properly addressed and the additional results further emphasize the relevance of this original work. My recommendation stands.", "rebuttal": "Thanks for the valuable comments, nice suggestions, and for acknowledging our work. Below we respond to your specific comments.\n\n\n---\n\n### ***160× Faster Than Gurobi with -0.06% Gap! Supplementary Experiments on a New Problem: Max Clique***\n\nAt the beginning of the rebuttal, we would like to present an additional experiment evaluating GenSCO on the Max Clique problem to demonstrate its generality (as suggested by the reviewers), which we believe would be another firm empirical support of our methodology.  **Due to space limits, please refer to the beginning of the response to Reviewer 1QVA for the results.**\n\n**We are very surprised to find that GenSCO not only closes the gap to the powerful Gurobi solver but surpasses its solution quality with a -0.06% relative gap on the RB-Large dataset, while being over 160× faster computationally.** Compared to other learning-based solvers, this outcome marks a step-change, order-of-magnitude improvement. From the perspective of the gap metric, it has reduced the learning-based solvers' performance by an infinite-fold margin (from 0.90% to -0.06%).\n\n---\n\n> **Q1: FLOPs would have been a better and fairer metric since the ML-based solvers benefit from a high degree of parallelization that classical solvers.**\n\nThank you for raising the point about a fair comparison metric. We appreciate your aim to find an equitable way to assess the computational complexity of traditional and learning-based solvers. However, we contend that a direct FLOPs (Floating Point Operations) comparison may omit one of the most significant advantages of learning-based solvers, i.e., highly parallelizable computation. Neural networks are inherently designed for highly parallelizable computation, and leveraging GPUs is a significant advantage of these methods. If we were to compare FLOPs, ML-based approaches would show an explosively high count due to extensive matrix operations. Yet, much of this computation completes rapidly because of its parallel nature, not serial execution.\n\nIn response to your request, we compared the FLOPs of LKH and GenSCO on TSP100. Achieving the same 0.000% optimality gap, our perf tool measurements show LKH3 (max_trials=4096) with 357,716,687 FLOPs, while GenSCO (C=10) registered 1,624,669,544 FLOPs. Crucially, in terms of execution time, LKH took 14 minutes, whereas GenSCO completed the task in just 6 seconds.\n\nWe believe this is a critical topic that we will discuss in the paper, hoping to foster more community discussion. We also look forward to seeing the field of operations research increasingly embrace the new vitality brought by GPU computing. Thanks again for this valuable point.\n\n\n\n> **Q2: It would have been nice to have confidence intervals on measurement values since the performance of the solvers partially depend on the initialization of the starting point.**\n\nThanks for the suggestion! We agree that including confidence intervals is important. We have already run the GenSCO experiments 10 times to record the results and claculate the 95% confidence intervals of the GenSCO to show the performance variations of different initializations, where we discover consistent performance of GenSCO. \n\nRegarding the TSP-1000 testing times, our latest runs are slightly faster than what was presented in Table 1. This discrepancy likely stems from fluctuations in server computational resources or variations in CPU types and load (though the GPU type is consistent, i.e. RTX 4090) during this specific experiment set. We find that our newly measured results align with those obtained without 2-opt (where the computational cost of 2-opt is negligible), thus verifying the consistency of the current set of experimental results. We will update the original table accordingly to reflect these new, consistent results.\n\n| TSP-500 | Obj. | Gap (%) | Time (s) |\n| - | -| -| - |\n| C=10 | [16.549, 16.549] | [0.019, 0.020] | [4.901, 5.159]|\n| C=20 | [16.548, 16.549] | [0.015, 0.017] | [9.237, 9.275]|\n| C=40 | [16.548, 16.548] | [0.012, 0.014] | [17.966, 18.137] |\n| C=80| [16.548, 16.548] | [0.010, 0.012] | [35.523, 35.667] |\n| C=160| [16.547, 16.547] | [0.009, 0.010] | [70.705, 70.876] |\n\n| TSP-1000 | Obj. | Gap (%) | Time (s)  |\n| - | -| -| -|\n| C=10| [23.133, 23.134] | [0.063, 0.067] | [12.562, 12.691]|\n| C=20| [23.131, 23.131] | [0.054, 0.056] | [24.155, 24.432]|\n| C=40| [23.129, 23.129] | [0.046, 0.047] | [47.435, 47.810]|\n| C=80| [23.127, 23.127] | [0.039, 0.040] | [94.012, 94.349]|\n| C=160| [23.126, 23.126] | [0.034, 0.035] | [187.295, 187.693] |\n\n> **Q3: How does the computational cost scale compared with just doing more solver steps in terms of FLOPS and energy. How big is the solution quality improvement?**\n\nThank you for this insightful question. As shown in Fig. 2(b), scaling search cycles with GenSCO leads to a more stable performance and a higher quality of solution. This approach effectively overcomes the performance plateau that occurs when you simply increase the number of inference steps in a single generation round.\n\nTo compare the computational cost of these two methods (scaling denoising steps vs. scaling search cycles), we use the number of function evaluations (NFE) as the primary metric, which represents the number of times the neural network is executed. This is the unit used for the x-axis in Fig. 2(b). When measured by NFE, both methods have an identical computational cost in terms of FLOPS and energy consumption on the GPU. The main operations for both are the parallelizable matrix multiplications of the neural network, which are handled by the GPU. Any additional operations on the CPU are computationally negligible in a Big O notation sense. Therefore, from a computational complexity standpoint, the cost scales identically for both increasing search cycles and increasing solver steps.\n\n\n> **Q4: Regarding table 1: Why is GLOP and UDC not solved on TSP-100? Same for GenSCO in some cases?**\n\nBoth GLOP and UDC are divide-and-conquer methods designed specifically for very large-scale problems. Their original papers did not include implementations or results for the smaller TSP-100 scale, which is why those cells are empty.\n\nThe blank cells for GenSCO on TSP-100 are because GenSCO had already found the optimal solution at 10 cycles. Since increasing the number of cycles beyond this point would not have improved the solution quality, we omitted the redundant data for clarity.\n\n> **Q5: Did you ever try other neural network/ML models instead of the transformer to model the distribution?**\n\nThanks for the nice advice. We supplement ablation studies as follows:\n\n1. **Flow model vs. consistency model (Fast T2T [1])**\n\nWe compare the flow model and the consistency model on TSP-500 under the same implementation and number of forward function evaluations (NFEs). We treat the consistency model as an alternative diffusion model variant and enhance its competitiveness by applying more 2-opt cycles, though at the cost of increased runtime. The results demonstrate the effectiveness of our proposed flow model over the previous consistency model design.\n\n| NFEs | Method | Obj. | Gap | Time |\n| :--- | :--- | :--- | :--- | :--- |\n| 40 | Consistency | 16.598 | 0.313% | 7s |\n|  | Consistency 2opt | 16.550 | 0.028% | 23s |\n|  | Flow | 16.550 | 0.023% | 5s |\n|  | Flow 2opt | 16.549 | 0.019% | 5s |\n| 80 | Consistency | 16.590 | 0.265% | 14s |\n|  | Consistency 2opt | 16.549 | 0.022% | 46s |\n|  | Flow | 16.549 | 0.020% | 9s |\n|  | Flow 2opt | 16.548 | 0.016% | 9s |\n| 160 | Consistency | 16.584 | 0.233% | 28s |\n|  | Consistency 2opt | 16.549 | 0.021% | 1m33s |\n|  | Flow | 16.548 | 0.016% | 18s |\n|  | Flow 2opt | 16.548 | 0.012% | 18s |\n\n\n3. **Architecture: Transformer vs. GCN**\n\nWe implement the GCN following the specific settings in DIFUSCO [2] and Fast T2T [1] as an alternative backbone for the flow model. The GCN implementation requires significantly more runtime for the same iterations, whereas the proposed Transformer architecture's efficiency enables the maximization of scaling benefits.\n\n\n|Method| Backbone| TSP-500| TSP-1000|\n|-|-|-|-|\n|GenSCO (C=40)  | GCN| 16.556, 0.060%, 1m45s | 23.157, 0.167%, 6m50s  |\n|| transformer | 16.549, 0.019%, 5s| 23.133, 0.063%, 16s|\n| GenSCO (C=80)  | GCN| 16.553, 0.045%, 3m25s | 23.147, 0.127%, 13m40s |\n|| transformer | 16.548, 0.016%, 9s| 23.131, 0.054%, 30s|\n| GenSCO (C=160) | GCN| 16.552, 0.037%, 6m50s | 23.140, 0.097%, 27m20s |\n|| transformer | 16.548, 0.012%, 18s| 23.129, 0.046%, 58s|\n\n\n> **Q6: Ln 352: RB graphs and Erdos-Renyi graphs are introduced w/o explanation. How are they distinct from others?**\n\nThank you for this valuable question. We will add an explanation to the paper to clarify the distinction.\n\nRB graphs are a class of random graphs specifically designed to generate challenging problem instances stemming from constraint satisfaction problems. The RB model creates instances that are known to be computationally difficult to solve, making them ideal for evaluating the robustness of algorithms.\n\nErdos-Renyi (ER) graphs, on the other hand, are a classical and foundational model of random graphs. In this model, edges are formed independently and with a uniform probability between all pairs of nodes. They serve as a standard baseline but are not specifically tuned to produce hard problem instances like RB graphs.\n\n\n> **Q7: Other paper formatting concerns.**\n\nThanks for the detailed review. We will update our script according to your valuable comments.\n\n---\n\nWe sincerely hope this response clarifies your concerns. We also hope a unified understanding and a stronger consensus can be fostered among the reviewers regarding the value of our contribution to the community. Thanks again for your valuable review and support.\n\n---\n\n[1] Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization. NeurIPS 2024.\n\n[2] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. NeurIPS 2023."}, {"review_id": "GcpQT1aw4s", "reviewer": "Reviewer_vfnv", "summary": "This paper introduces GenSCO to solve the inference-time cost‐efficiency bottleneck of diffusion models on combinatorial optimization tasks. GenSCO treats each generation pass as a search operator and interleaves local search disruptions with learned diffusion sampling in lightweight refinement cycles. A rectified flow model is trained via a bias‐corrected objective to perform solution‐to‐solution refinements, enabling controllable exploration of the near‐optimal solution space. The key insight is to leverage the learned high-quality solution distribution across multiple fast, iterative steps rather than relying on a single expensive generation. Experiments on TSP-100 and TSP-500 benchmarks show that GenSCO outperforms prior neural methods by orders of magnitude and achieves up to 141× speedup to zero optimality gap on TSP-100 and ~10× speedup to 0.02 % gap on TSP-500, demonstrating both enhanced solution quality and practical scalability.", "questions": "1. The motivation for using a rectified flow model for generation is underdeveloped—why choose rectified flow instead of directly using an autoregressive model?  \n2. Please provide a detailed comparison of model parameter counts to ensure the comparisons are fair.  \n3. Ablation studies on different modules are insufficient; there is no empirical evidence showing how the disruption operator, number of sampling steps, and post-processing affect performance.  \n4. How does this scaling approach differ from the traditional diffusion model’s iterative re-noising and de-noising process? Does it offer any clear performance advantages?  \n5. Can you provide empirical evidence demonstrating the advantages of solution-to-solution denoising over the original noise-to-solution denoising?  \n6. In Lines 153–157, could the proposed disruption method generate invalid solutions, and if so, how would that impact overall performance?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. **Quality:** The writing and figures are complete and clear; method details are presented directly and are easy to understand.  \n2. **Significance:** The paper tackles an important combinatorial optimization problem and provides a comprehensive deep-learning–based approach.  \n3. **Originality:** Introducing the number of search cycles as a new scaling dimension—and demonstrating its effectiveness in Figure 2—along with using rectified flow in the relaxed solution space, improves cost-efficiency.  \n4. **Quality / Originality:** The authors systematically redesign both the diffusion architecture and the solving pipeline specifically for search-driven optimization.  \n5. **Significance:** Experimental validation on TSP and MIS datasets demonstrates the method’s practical effectiveness.\n\n### Weaknesses\n\n1. **Originality / Quality:** The motivation for using a rectified flow model for generation is underdeveloped—could an autoregressive model achieve similar refinements?  \n2. **Quality:** The paper lacks detailed profiling of training and inference overhead; multi-round refinements increase model calls but latency and cost breakdowns are not provided.  \n3. **Significance:** It is unclear whether this search-driven scaling offers substantial advantage over traditional diffusion’s iterative re-noising and de-noising strategies.  \n4. **Clarity / Quality:** Ablation studies are limited; there is insufficient evidence isolating the contributions of the disruption operator, sampling steps, and post-processing to overall performance.  \n5. **Significance / Originality:** The approach, while effective for TSP and MIS, may require extensive engineering for other CO tasks, potentially limiting broader applicability.", "was_revised": true, "final_justification": "Thank you to the authors for the detailed rebuttal and for providing substantial new experiments. Your responses were very effective and have resolved my primary concerns. I have raised my score accordingly.\n\nMy main initial reservations were about the method's generality, the motivation for using rectified flow, and the lack of detailed ablation studies. The rebuttal addressed these points convincingly:\n\nGenerality and Scalability: The new experiments on the Max Clique problem were a welcome and compelling addition. Seeing the method not only adapt to a different CO task but also outperform a strong commercial solver like Gurobi significantly strengthens the paper's claims about its broader applicability.\n\nMethodological Justification: Your clarification on using rectified flow to enable a more controllable, efficient, and scalable search process makes perfect sense. The comparison to traditional re-noising methods highlighted the advantages of your solution-to-solution refinement approach.\n\nAblation Studies: The new ablations on the disruption operator and the number of sampling steps provided the necessary evidence to understand the contribution of each component. It's now clear that the disruption operator is crucial for escaping local optima, especially on larger problem instances.\n\nAfter the rebuttal, I feel the paper is in a much stronger position. There are no major unresolved issues.", "rebuttal": "Thanks for the valuable comments, nice suggestions, and for acknowledging our work. Below we respond to your specific comments.\n\n---\n\n### ***160× Faster Than Gurobi with -0.06% Gap! Supplementary Experiments on a New Problem: Max Clique***\n\nAt the beginning of the rebuttal, we would like to present an additional experiment evaluating GenSCO on the Max Clique problem to demonstrate its generality (as suggested by the reviewers), which we believe would be another firm empirical support of our methodology.  **Due to space limits, please refer to the beginning of the response to Reviewer 1QVA for the results.**\n\n**We are very surprised to find that GenSCO not only closes the gap to the powerful Gurobi solver but surpasses its solution quality with a -0.06% relative gap on the RB-Large dataset, while being over 160× faster computationally.** Compared to other learning-based solvers, this outcome marks a step-change, order-of-magnitude improvement. From the perspective of the gap metric, it has reduced the learning-based solvers' performance by an infinite-fold margin (from 0.90% to -0.06%).\n\n---\n\n> **Q1: The motivation for using a rectified flow model for generation.**\n\nThe motivation for using a lightweight rectified flow model is discussed in lines 135-149. Here we summarize as follows:\n\n**In essence, the motivation for using rectified flow is to create a more efficient, controllable, and scalable generative model that can be scaled more efficiently, allowing for maximizing the advanced scaling effects achieved by \"generation as a search step\".**\n\nSpecifically, we are motivated by existing diffusion solvers' limitations:\n* Restricted Controllability: Relying on Gaussian noise initialization for *de novo* generation limits the ability to control intermediate states during generation.\n* Limited Exploitation of Prior Knowledge: It's difficult to effectively utilize existing solution knowledge.\n* Cost-Efficiency and Scalability: The generations follow complex, curved trajectories, which can be computationally expensive.\n\nGenSCO makes improvements accordingly, which we discuss in Q3.\n\n> **Q2: Profiling of training and inference overhead.**\n\nThanks for the valuable question. The training costs of GenSCO on TSP-100/500/1000 are <= 2 days, <= 1 day, and <= 1 day on a GTX 4090 24G. For comparison, DIFUSCO takes 8.6 days, 2.7 days, and 5.1 days for training TSP-100/500/1000 on an A100 GPU, respectively.\n\nFor inference cost, Fig. 2 shows the scaling curves of GenSCO, indicating the specific runtime and number of function calls of GenSCO for a given solving performance. Tables 1 and 4 show the runtimes for solving TSP and MIS with a varying number of search cycles. The inference cost of GenSCO is way smaller than that of previous state-of-the-art methods.\n\n\n> **Q3: Comparison to the traditional diffusion model’s iterative re-noising and de-noising process**\n\nIn Figure 2(a), we illustrate the performance of the prior iterative re-noising and de-noising method (T2T) compared to simply scaling the de-noising step (DIFUSCO), as well as a comparison with our proposed GenSCO model. While T2T shows a clear performance improvement over DIFUSCO, this gain is limited by its methodology design based on single-round heavy generation. Our method aims to maximize the scaling effect of \"generation as a search step\", allowing us to integrate various search-friendly optimizations.\n\nThe primary distinctions from previous approaches are as follows:\n1. Focused Search Space: Our generation process is specifically designed to convert suboptimal solutions into optimal ones. This provides a more focused search range, and our bias-rectified training objective is specifically adapted for this goal.\n2. Flow-Based Design for Speed: We employ a flow-based design, which ensures that generation follows a more direct trajectory, leading to faster inference.\n3. Lightweight Transformer Architecture: We redesign the architecture using a lightweight Transformer. This maintains effectiveness while significantly improving efficiency.\n4. Controllable Search Operator: During the inference phase, we design a controllable search operator that enables efficient scaling of the search process.\n\n\n> **Q4: Ablation studies are limited: the contributions of the disruption operator, sampling steps, and post-processing to overall performance.**\n\nThanks for the nice advice. We supplement ablation studies as follows:\n\n1. **w/  vs. w/o disruption operator**\n\nUsing the disruption operator can effectively escape local optima and achieve continuous improvement. Without the disruption operator, we observe varying degrees of performance degradation, especially on TSP500, where the gains from increasing search cycles show significant stagnation.\n\n|Method|Disruption|TSP-500|TSP-1000|\n|-|-|-|-|\n|GenSCO (C=40)|w/o|16.551, 0.033%|23.137, 0.083%|\n|| w/|16.549, 0.019%|23.133, 0.063%|\n|GenSCO (C=80)|w/o|16.551, 0.032%|23.134, 0.067%|\n|| w/|16.548, 0.016%|23.131, 0.054%|\n|GenSCO (C=160)|w/o|16.551, 0.032%|23.131, 0.056%|\n||w/|16.548, 0.012%|23.129, 0.046%|\n\n2. **Effect of sampling steps**\n\nWe observe that increasing num_sampling $t$ (at settings of $t=1, 2, 4, 6, 8, 16$) generally improved performance for num_cycles $C=40, 80, 160$, though the gains diminished in later stages. We ultimately chose $t=4$ and allocated more computational resources to scaling $C$.\n\n| C| t| Obj.| Gap| Time (s) |\n| - | -| -| -| -|\n| 40| 1   | 16.561  | 0.091% | 8.06|\n| | 2| 16.549  | 0.018% | 8.34 |\n| | 4| 16.548 | 0.013% | 18.38|\n| | 6| 16.548 | 0.013% | 26.88|\n| | 8| 16.548 | 0.012% | 35.60 |\n|80 | 1| 16.558  | 0.072% | 15.54|\n| | 2| 16.549  | 0.017% | 16.33|\n| | 4| 16.548  | 0.011% | 35.56|\n| | 6| 16.548  | 0.011% | 53.35|\n| |8| 16.547  | 0.010% | 70.66|\n|160 | 1| 16.556  | 0.059% | 31.47|\n| |2| 16.548  | 0.015% | 32.15|\n||4| 16.548  | 0.010% | 70.62|\n| |6| 16.547  | 0.009% | 106.26|\n| |8| 16.547  | 0.009% | 140.92|\n\n3. **Effect of post-processing**\n\nWe use greedy decoding to guarantee the feasible output of the search operator, which is an indispensable part of this algorithm. Regarding 2-opt ablation for the TSP experiments, the ablation is already presented in Table 1.\n\n> **Q5: The approach, while effective for TSP and MIS, may require extensive engineering for other CO tasks, potentially limiting broader applicability.**\n\nThe high-level algorithmic framework of our method shown in Fig. 1 is actually general, which can be applied to a wide range of COPs. To adapt methods to different problems, the major required effort is to customize specific components. In our framework, the primary problem-specific adaptations are the local search operators and the post-processing step. For many classical COPs, mature local search operators already exist. Even when they don't, creating simple operators to disrupt solutions is straightforward (as we do in MIS). For the post-processing step, it can be simply set as greedy decoding.\n\nTo demonstrate the generality of our method, we conducted additional experiments on a new problem, the Maximum Clique Problem, within the limited rebuttal period. Please refer to the beginning of this rebuttal.\n\n\n> **Q6: Comparison of model parameter counts to ensure the comparisons are fair**\n\nThanks for the advice on comparing the architectures. However, we must clarify that a direct comparison of parameter counts across all models in our study would be misleading due to fundamental differences in their underlying architectures. Unlike many NLP scenarios where comparisons are made between models of the same Transformer architecture, our baselines utilize diverse architectural designs. For instance, convolutional neural networks (GCNs) inherently possess fewer parameters than Transformer models thanks to repeated utilization of the same convolutional kernels. Directly comparing parameter counts between these distinct architectures would not accurately reflect their computational complexity or efficiency.\n\nMoreover, the lightweight Transformer architecture of our proposed Flow model represents a significant contribution. This emphasis on efficient and effective computation is crucial for maximizing the potential of our test-time scaling by \"generation as a search step\".\n\nTo provide a more meaningful assessment of computational cost, we compare the computational time and performance of our proposed Transforme against a GCN model implemented under identical settings (consistent with baselines like DIFUSCO and T2T). **Due to space limits, please refer to the response to Reviewer 1QVA (Q3.3) for the results.** GCN requires >27 times computational cost for the same number of iterations, while yielding inferior results. Despite this, the GCN model's performance still surpassed that of previous baselines.\n\n> **Q7: Empirical evidence: solution-to-solution denoising vs. original noise-to-solution denoising**\n\nThanks for the advice! We supplement the comparison to the SOTA noise-to-solution method, i.e., consistency model (Fast T2T), in our settings. **Due to space limits, please refer to the response to Reviewer 1QVA (Q3.1) for the results.** The results show the effectiveness of solution-to-solution denoising in our framework.\n\n> **Q8: In Lines 153–157, could the proposed disruption method generate invalid solutions?**\n\nThe disruption operators we adopt are guaranteed to produce valid solutions. In the case of TSP, we use a 2-opt swap. For MIS, we randomly select a subset of nodes already in the independent set and remove them. Both of these operations are designed to perturb the solution within the feasible space.\n\n---\n\nWe hope this response provides the clarity you were seeking and fully addresses your concerns and that a more unified understanding and stronger consensus could be fostered around the value of our contribution to the community. Please do not hesitate to reach out if you have any additional questions or require further discussion. Thanks again for your valuable comments and suggestions."}]

Author rebuttal:

Meta-review: This paper introduces GenSCO, a novel framework for scaling diffusion-based solvers in combinatorial optimization by treating generation as a search operator rather than a complete solving process. The method integrates local search disruption, diffusion sampling, and a rectified flow model with a lightweight transformer, enabling efficient exploration of the solution space. Strengths include its clear conceptual novelty, rigorous training design, and compelling experimental results demonstrating orders-of-magnitude improvements over prior neural methods and even substantial speedups against the strong classical solver LKH3. Weaknesses noted by reviewers focused on clarity of exposition and some missing ablations, but these were largely addressed during rebuttal with clarifications and additional evidence. Reviewers have actively participated in the discussion and reached a clear concensus to accept this paper. Overall, I recommend acceptance.
Decision: Accept (poster)