StruDiCO: Structured Denoising Diffusion with Gradient-free Inference-stage Boosting for Memory and Time Efficient Combinatorial Optimization
Authors: Yu Wang
Yang Li
Junchi Yan
Yi Chang
Venue: NeurIPS 2025 poster ()
Keywords: Neural Combinatorial Optimization
Generative Modeling
Primary area: machine_learning_for_sciences
TL;DR: We propose a structured denoising diffusion model, StruDiCO, which incrementally constructs solutions through step-wise variable selection.

Abstract: Diffusion models have recently emerged as powerful neural solvers for combinatorial optimization (CO). However, existing approaches fail to reveal how variables are progressively determined during inference, making the final solution opaque until the last step. To address this limitation, we propose a structured denoising diffusion model, StruDiCO, which incrementally constructs solutions through step-wise variable selection. This is achieved via a variable-absorption noising model, wherein the forward process simulates gradual variable deactivation, converging to an empty solution, while the reverse process incrementally selects variables to reconstruct the final solution. This design induces structural continuity across intermediate states, enabling interpretable and trajectory-consistent partial solutions throughout inference. To further improve the reliability of reverse inference, we introduce a constrained consistency sampling strategy, which suppresses low-confidence variable selection at each step to stabilize the reverse process. Leveraging the structure-preserving reverse process, we further propose a lightweight, gradient-free, objective-aware refinement framework, which iteratively improves solution quality by applying structure-aware perturbations to the current solution, performing reverse inference through the constraint consistency model, and decoding with an objective-guided scoring scheme. Extensive experiments on two canonical CO tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), show that StruDiCO outperforms state-of-the-art diffusion-based solvers, achieving up to $3.5\times$ faster inference, 70\% lower GPU memory usage, and significantly improved solution quality, with up to 37.7\% drop reduction on TSP and an average 38.1\% improvement on MIS.
The codes are publicly available at https://github.com/yuuuuwang/StruDiCO.

StruDiCO: Structured Denoising Diffusion with Gradient-free Inference-stage Boosting for Memory and Time Efficient Combinatorial Optimization
Yu Wang', Yang LI, Junchi Yan"*, Yi Changl:34* 1.3,
'School of Artificial Intelligence, Jilin University
School of Artificial Intelligence, Shanghai Jiao Tong University "Ineeraational Center of Future Science, Jilin University
"Enginecring Research Center of Showledge-Driven lu..lu.ucc. {yanglily, yanjunchi]> Cs
Intelligence, MOE, China Gs jujttu. edu. cn
Abstract
Diffusion models have recently emerged powerful neural solvers for combinato- rial optimization (CO). However, existing approaches fail to reveal how variables are progressively determined during inference, making the final solution opaque until the last step. To address this limitation, we propose structured denoising diffusion model, StruDiCO, which incrementally constructs solutions through step-wise variable selection. This is achieved via variable-absorption noising model, wherein the forward process simulates gradual variable deactivation, con- verging to empty solution, while the reverse process incrementally selects variables to reconstruct the final solution. This design induces structural conti- nuity across intermediate states, enabling interpretable and sejjectory-consistee partial solutions throughout inference. To further improve the reliability of re- verse inference, introduce constrained consistency sampling strategy, which suppresses low-confidence variable selection at each step to stabilize the reverse process. Leveraging the untucture-prsservve reverse process, further propose lightweight, gradient-frea objective-aware refinement framework, which iteratively improves solution quality by applying structure-aware perturbations to the current solution, performing reverse inference through the constraint consistency model, and decoding with an objective-guided scoring scheme. Extensive experiments on two canonical CO tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), show that StruDiCO outperforms state-of the-art diffusion- based solvers, achieving up to 3.5x faster inference, 70% lower GPU memory usage, and significantly improved solution quality, with up to 37.7% drop redue- tion TSP and an average 38.1 % improvement on MIS. The codes are publicly available httttttt//// / thub... com//uuuuuaag/Stru...C...
Introduction
Combinatorial optimization (CO) entails optimizing discrete decision variables toward specified objectives and serves as a cornerstone for numerous practical applications requiring efficient decision- making II 3 However, the inherent NP-hardness of CO problems renders large-scale CO instances particularly challenging to solve efficiently, traditionally necessitating the design handcrafted
Corresponding authors: Junchi Yan and Yi Chang (yanjunchi(-sjuucduuuu yichang @ (ll.cdu..c)) This work was partly supported by MOST of China (Grant 2023YFF0905400) NSFC (Grant U2341229, 92370201), and the China Postdoctoral Science Foundation Fellowship (Grant GZC20230947),
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

X
X0
X0
Denoising Step
fx t, G)
yxxx-11x 1x0)
Noising Step
Graph
Instance G
Solution
XT
X13
Xt2
Xt1
X
Figure 1: Overview of the structured denoising diffusion framework for combinatorial optimization. Structured denotes the preservation and progressive evolution of solution structures across timesteps. The forward process (0 + ' gradually removes selected edges through a variable-absoortion noising model, while the reverse process incrementally reconstructs the solution by selecting edges.
heuristics. Recently, neural combinatorial optimization (NCO), including both direct solvers 4 7 [ and methods that support solving ( 10 has emerged as a data-driven paradigm, offering notable improvements in both solution quality and computational efficiency.
5
6
Existing NCO solvers can be broadly categorized based on their solution construction paradigm: autoregressive and non-autoregressive. Autoregressive constructive solvers 112 13 15 16].
formulates the task as an n-step sequential variable selection problem, where at each step the model produces prediction heatmap over variables, conditioning on the current partial solution to decide the next inclusion. While this step-wise generation enables fine- aie--griied control and interpretability, incurs significant computational overhead due to its inherently sequential nature, limiting scalability to larger instances. In contrast, non-autoregressive solvers [17 18] 19 20 21 adopt a one- shot generation strategy. These models directly generate neural heatmaps indicating the predicted likelihood of each variable being part of the solution, followed by heuristic decoding to enforce
feasibility. Among them, generative models, such diffusion- based models [2 23 24 have shown strong performance by modeling instance-conditions sequential denoising process. However, these models still suffer from opaque intermediate states, providing little insight into how the final solution is gradually formed-since decisions are not explicitly revealed until the final step. In summary, autoregressive models provide step-wiss sep-wise interpretability but suffer from sequential computational overhead, whereas non-autoregressvv generative models offer efficient global modeling but lack transparency in the solution trajectory. Bridging this gap is essential for developing NCO solvers that are both interpretable and efficient.
distribution over high-quality solutions through
To bridge the gap between step-wise interpretability and global distribution modeling, propose a structured discrete diffusion framework tailored for CO. Specifically, we introduce a variable- absorption noising model, which progressively deactivates variables during the forward process, ensuring that each intermediate state corresponds to a structurally valid partial solution. Rather than treating such interpretability as end in itself, this structure-preserviin design enables more informed and reliable decision-making throughout the inference trajectory. To enhance the reliability of reverse inference, we introduce a constrained consistency sampling strategy that masks low- confidence variables at each step. By narrowing the effective search space, this strategy improves structural continuity across intermediate states and stabilizes the solution trajectory. Building on this structure- preserving foundation, we propose a lightweight gradient-free framework that directly incorporates task objectives into the decoding process. Unlike prior refinement methods (23 24 that rely on gradient- based search over relaxed continuous objectives, our approach eliminates the need for backward computation entirely. The refinement proceeds in three stages: first perturbs feasible solution using structure-awart noise, then performs reverse inference via the consistency model, and finally reconstructs new solution through objective-guided greedy decoding. Together, these innovations yield diffusion- feffusiion-baeed solver that achieves high-quality solutions with
ebjective-aware refinement

---

significantly reduced computational overhead, while preserving structural interpretability and aligning inference with task objectives. effectively combining the complementary strengths of autoregressive and non-autoregressive paradigms. Our contributions toward building an interpretable and efficient neural solver for CO are summarized as follows:
We propose a prreerine discrete diffusion framework and develop StruDiCO, which leverages aariable-absorptig forward diffusion and constrained reverse sampling produce interpretable, high-quality solutions for combinatorial optimization tasks.
We introduce a gradient-free, objective-aware refinement framework that efficiently incorporates task objectives without requiring backward gradient computation 23
We evaluate our method on TSP and MIS tasks, demonstrating superior solution quality, 3.5x faster inference, and 70% lower memory usage compared to state-of-the- art neural solvers.
2
Preliminaries, Problem Definition and Related Works
2.1 Combinatorial Optimization on Graphs
Following the notations adopted in [22 23 24), define G as the universe of CO problem instances represented by graphs G(V, E) E G. where V and E denote the node set and edge set respectively. CO problems can be broadly classified into two types based on the solution composition: edge- selecting problems which involve selecting subset of edges, and mode-selecting problems which select subset of nodes, both subject the feasibility constraints of the problem. Let E 10.1)* denote the optimization variable. For edge-sclecting problems, .N = n² and Xin+j indicates whether Faj is included in x. For pede-selecting problems, N and x; indicates whether V; is included in x. The feasible set f2 consists of x satisfying specific constraints as feasible solutions. A CO problem on G aims to find feasible x that minimize the given objective function I(::G): {0, 1 + R2o
min 1(x; S.L. X xE(O.1)
In this paper, we study two primary and representative CO problems: TSP and MIS. TSP defines on an undirected complete graph G = (V, E), where V represents n cities and each edge E, has non non-negative weight Wij representing the distance between cities i and j. The problem can then be formulated as finding a Hamiltonian cycle of minimum weight in For MIS, given an undirected graph G (V, F), an independent set is subset of vertices S C V such that no two vertices in S are adjacent in G. MIS is the problem of finding an independent set of maximum cardinality G.
2.2 Optimization Consistency
Given a problem instance G and its corresponding optimal solution x", the discrete diffusion noising process defines a trajectory X4:T Xg.X1, xx.....XXp. Xy, where X = x" and each x, is sampled from the conditional distribution q(x: Xo). In standard diffusion models, generating samples requires modeling the reverse transitions (x, xx, x2, G)) through multiple iterative steps, which can be computationally expensive. To enable efficient inference, Consistency Models [25) introduce the notion of self-consistency, where the model learns to map any noised state x; at time directly back to the clean source Xg. Building on this idea, Fast T2T (24] gives the notion of optimization consistency for CO, which all states along a noising trajectory are mapped to the same optimal solution x" conditioned the instance G. Formally, the consistency function fø(X,, I, G). parameterized by 0, maps a noisy input to a denoised prediction. Under self-consistency, the training objective is to minimize the discrepancy between any two mappings along the same trajectory:
[())= = 3x,,, [d (Xx, t1, G), fe fe f2, G))],
(I)
where d(.,.) is a distance function, e.g., binary cross-entropy. To better leverage the supervision from x", an alternative minimizes the distance between each mapping and the ground-truth:
( = E, [d (fa (x t, G), x")].
This formulation can be justified by the triangle inequality, which upper-bounds the original objective:
L())= < Ee, [d ( t1, G), x") + d (fo(Xi), t2, G), x")]
3

---

This reformulation reduces the problem to supervised learning of the mapping fo using a standard loss, such as binary cross-entropy, and allows the model to generalize across different noise levels while consistently recovering the optimal solution.
2.3 Related Work
Neural combinatorial optimization (NCO) has emerged as promising alternative traditional heuristics such as LKH [7] Existing neural solvers can be broadly categorized into autoregressive (AR) and non-autoregressive (NAR) paradigms. An illustrative comparison with our structured diffusion approach is provided in Appendix A highlighting key differences in solution construction.
AR methods sequentially construct solutions by selecting decision variables step-by-step Representa- tive works include the Attention Model (AM) [12), which first applied transformer-base architectures to routing problems, and POMO [3], which leverages policy optimization with multiple optima for reinforcement learning. Sym-NCO [14] exploits problem symmetry to enhance generalization capability, while BQ-NCO [155] formulates CO problems under bisimulation-quee -uuutitttnninntttttt MDP to improve robustness. The RL4CO repository [16] systematically benchmarks AR-based methods.
NAR methods aim to predict soft-constrained solutions in one-shot manner, followed by post- processing to ensure feasibility. Early works such as GCN [17 and Att-GCN [8] employ graph neural networks [28] 29, 30) for edge prediction under supervised learning. UTSP 220 adopts
an unsupervised learning framework with scattering attention GNNs, and DIMES [9] proposes
mneaa-reinfrreemenl learning strategy combined with active search. Recently, generative mod- els [3 32] have shown promise in improving prediction [33], and for CO, graph diffusion- based distributions over gigh-tualtty solutions. DIFUSCO [2 achieves SOTA performance on TSP and MIS but lacks instance- speciei-eeeciceeee search. T2T
generative approaches [22
23 24 34 model
jnjjectiveggiieer gradient search, and Fast T2T 24 further applies consistency training to accelerate diffusion sampling and advance NCO performance, Unify ML4TSP (35) advances unified modular streamline incorporating existing technologies in both learning and search for both AR and NAR methods.
23 addresses this via
3 Methodology
We propose structured diffusion framework for combinatorial optimization. The process begins with a variable-absorption noising model, which defines a struccure-preserving forward process and its reverse counterpart. To guide the reverse trajectory toward coherent solutions, we introduce constrained consistency sampling strategy that selectively activates high-confidence variables at each step. Finally, we refine the decoded solutions through an objective-aware, gradient-free method that integrates task objectives directly into decoding without backward computation. Together, these components form lightweight and interpretable neural solver.
3.1 Variable-Absorpttonn Noising Process
Our objective is to design a forward diffusion process that generates noisy graph states while strictly respecting combinatorial constraints, c.g. preserving the validity of partial solutions throughout the noising trajectory]] We adopt a discrete diffusion model [22 23 24]. tailored for structured combinatorial problems where solutions encoded as binary vectors E (0, 1) This formulation naturally applies to edge-selection tasks such as
TSP and node-selection tasks such as MIS.
It begins with initial state Xo g(xo G) sampled from data-dependent distribution that yields a feasible solution. Then, a sequence of latent states x1:T = X .2...., is generated by progressively injecting noise while maintaining structural validity. The forward process factorizes as q(xET xo) I q(x; xx-1), where each q(x, xx-1) is categorical distribution over binary states. Using a one-hot encoding x E 13 Nx2, where each row denotes the selection status of variable, the transition is defined as:
g(xx xx-1)) = Cat(xe;
x Qr), g(xx xo)
Cat(xi; p X Q,),
(4)
"Since the process begins from a feasible solution Xa and injects noise solely by deactivating selected variables, each x, along the trajectory is guaranteed to be structurally valid. This guarantee holds only for the forward process; feasibility in the reverse process typically requires post-processing.

---

where Q E [0, 1]]x2 is the forward transition matrix at time i, and Q. = Q1 Q2.
... Q₁ is the cumula- the transition matrix Q, typically symmetric 24).
tive transition up time In prior works
[2
23
and doubly stochastic: Q: 1
3
B.
where 3r [0, 1] denotes the transition rate step t. This formulation enables reversible transitions and yields a uniform stationary distribution, but does not guarantee structural validity of intermediate states.
B 1-3:]
Variable-Absorption Noising Model. To enforce structural validity at all timesteps, we propose a variable-absorpae noising model that induces monotonic decay in variable activations. Specifically, a variable can remain unselected (x; = 0) or transition from selected (x; = 1) to unselected, but cannot revert once dropped. This yields valid absorption trajectory from X to the null solution Xy ON E 0%, in which each intermediate state is feasible partial solution. We implement this
0
behavior using the following asymmetric transition matrix: Q: Be 1- where 3r E [0. 1]
denotes the absorption rate at step t. Under this formulation, unselected variables are frozen, and selected variables are independently dropped with probability S.. This directional and irreversible transition enforces monotonic variable deactivation and ensures that combinatorial constraints are respected throughout the forward trajectory.
3.2 Constrained Consistency Sampling for Reverse Optimization
we adopt a multi- step consistency sampling procedure to progressively construct the reverse tra- jectory of solutions. The process be-
Following
24 25
Algorithm 1 Multistep Constrained Consistency Sampling
Require: Consistency model fe(+ ") graph instance G,
time sequence Ti > ... >> TN,-1, threshold
gins from the empty solution XT ON. and at each timestep Tu we aim gen- erate more refined intermediate state
1: XT ON
2: Po (xo G) + fx(x,, G)
3: Xu ~ (x G)
XT, Accordingly, we use a consistency
4: for = to N₂ do
model fe to predict a clean solution X from the current noisy input: po
5:
// variable-absorptionn process
6:
x,, Cat(p x0 Q.,
XT.: Tu. G) fx( Tn. G), Xo
7:
px G) + (x, Two G)
1 G)). This pre- dicted xo serves as a high-confidence proxy, guiding the sampling of the next intermediate state Xr,:1 via the variable-absorption process: XT. ~ Cat(p = Xo Q......) ) where Q, denotes the cumulative absorption transition matrix. The key modeling goal is to construct a trajectory of that exhibit increasing structure and semantic coherence,
(xo
8:
I/ constrained sampling over m
9:
m t I(po(Xn, = 1 G) > 5)
10:
Xy Bernouli(m O po (Xu = G
11: end for
12: return Solution Xo
intermediate states XT, X ultimately leading to a high-quality solution. This construction process alternates between denoising (via fo) and noise injection (via variable-absorption) forming a progressive trajectory over X,- Although each X. prediction is discarded after use. it plays crucial role in steering the generation of the next X,. As illustrated in Fig. [ this reverse process forms zigzag pattern between model pre- dictions xo and intermediate states X., with increasing structural coherence, progressively guiding the construction of the final solution. It is important note that structural coherence across reverse steps is primarily induced by the variable-atee abbooptt-a process, which softly enforces a monotonic selection trajectory (x+.. S XT.+1). For stricter structural guarantees, see our discussion in Appendix B
Constrained Sampling. To reduce noise and improve the stability of this process, we introduce a threshold-bast based constrained sampling strategy. After obtaining the prediction po(xo = G). we suppress low-confidence variables by applying a hard threshold 8:
m T(po (xo = 1 G) 6), X Bernoulli(m @ po = 1 G))-
(5)
The constrained sampling strategy is also supported by theoretical insights. Combinatorially, reduces
the candidate solution space from 2 to at most Σn (i) Statistically, thresholding the predicted heatmap can seen as truncating the predictive distribution
(N) for thresholded fraction E (0, 1).
to high-confidence region, reducing entropy and sample variance. See proof in Appendix C
5

---

TSP-50
TSP-100
TSP-500
TSP-1000
MIS RB
MIS
Time (S1
Time (il
Time
Time (A
Time Est
Time (st
Perrory
Hernery
Herfory
tann
Dmmp
Dwnp
Drno
Figure 2: Relative comparison of StruDiCO and Fast T2T across six combinatorial optimization tasks. Metrics include GPU memory usage, inference time, and performance drop (all normalized to Fast T2T 100%). Lower values indicate improved efficiency or solution quality.
Table 1: Summary of objective- guided refinement framework. StruDiCO enables multi-step structure construction, where intermediate states are valid subsets of the soft-constrained solution. B: batch size; L: number of layers; N: number of nodes; d: hidden dimension.
Multi-Step Structure Construction
Objective-Guide
Complexity
Method
Gradient-Iree Forward
Backward
Time
Memory
Fast T2T StruDiCO (Ours)
O(3BLN'd)
O(2BLN')
O(BLN' O(BLN'
Theorem 3.1 (Constrained Sampling Reduces Divergence). Let qxx G) denote the true distribution and xx Xr; T G) the model prediction. Let Po Masks(po) be the renormalized distribution ob- tained by thresholding low-confidence variables, po (xn) = [pe(xo)22) po(xa), Zs = Exo (xp) > 6] pe (x)),), where Zg is the normalization constani representing the retained probability mass. Then, in terms of the reverse KL divergence, we have DKL (Pe || q) I DKL(Pe || q) + Eg, where the slack
Zi
term vanishes as the discarded probability mass Z8 + 0.
Remark. Theorem 3.1 formally shows that threshold- constrained sampling reduces the divergence between the model and the true solution distributions. Specifically, by masking out low-confidence regions (probability d) and renormalizing the remaining mass, the KL divergence decreases whenever the retained region has higher expected likelihood than the discarded region, condition that is naturally satisfied during inference where gigh-confidence variables dominate. Importantly, while constrained sampling can also be applied to uniform noise diffusion models 22] 24,, its benefits are substantially amplified under the structure- prreservigg variable-absorption which provides monotonic and semantically consistent reverse trajectory (see Sec.
process,
3.3 Objective-Aware Gradient-Fres Refinement
Following the reverse sampling process in Algorithm [ we finally sample a soft-
Algorithm 2 Objective-Aware Gradient-Fres Refinement
constrained solution Xo ~ po (x5 G). To obtain a feasible solution E Ω, we apply greedy decoding by sequen- tially inserting edges (for TSP) or nodes (for MIS) with the highest confidence if there are no conflicts, enforcing task- specific constraints. This step ensures hard feasibility and is commonly used
Require: Consistency model fe. graph instance G, pre- diction po. score function score; pt/ Pt/Ø,, number of iterations T.g perturbation ratio a 1: for t 1 to Tg do
2:
m < [( (Xo = G) >
3:
4:
8 + ONEHOTENCODE(S
5:
//apply variable-absorption noise
19
22 23 24). While feasible, it
6: SaT Cat(S QaI)
does not explicitly optimize the task ob- jective and often yields suboptimal solu- tions. Recent methods like T2T (23 and Fast T2T 244 address this by incorporat- ing task-level supervision via gradient- guided refinement. These methods itera-
7:
Po < fo(sar G)
8:
GREEDY
9: end for
10: return s
tively perturb solution and reverse denoising guided by objective gradients to refine solution, but at the cost of repeated making them computationally expensive and less suited discrete combinatorial settings.
passes and reliance on differentiable approximations,
To overcome these practical inefficiencies, we propose a lightweight objective-aware gradient-free refinement strategy. Rather than backpropagating gradients, we integrate task objectives directly into

---

Table 2: Results on TSP-50 and TSP-1100. G: Greedy Decoding.
TSP-50
TSP-100
Algorithm
Type
Length
Dropl
Timel
Length
Dropi
Time
Concorde
36
Exact
5.688
0.00%
0.074s
7.756
0.00%
0.404s
LKH3 26
Hcuristics
5.688
0.00%
0.058s
7.756
0.00%
0.176s
GCN 17
SL+G+20pt
5.694
0.115%
0.009s
7.807
0.649%
0.019s
GNNGLS 37
SL+G+20pt
5.707
0.333
0.019s
7.857
1.295%
0.129s
DIMES 19
Mel++RL+G+20pt
5.823
2.387%
0.018s
8.007
3.232%
0.057s
AM 12
RL+G+20pt
5.679
0.167%
0.048s
7.826
0.898%
0.438s
POMO 13
RL4G+20pt
5.693
0.102%
0.019s
7.854
1.253%
0.116s
Sym-NCO 14
RL+G+20pt
5.694
0.122%
0.198
7.818
0.796%
0.634s
BQ-NCO* 15
RL+G+20pt
5.795
1.894%
0.205s
7.893
1.772%
0.387s
DIFUSCO
22
ST.+G
5.692
0.076%
0.229.
7.851
1.216%
0.591
Fast T2T (T]=3)
24
SL+G
5.694
0.111%
0.024s
7.798
0.537%
0.038s
StnDDCCO
SL++
5.692
0.071%
0.023s
7.786
0.392%
0.037s
T2T [7,77.500,
22
SI.+G
5.688
0.015%
0.717s
7.765
0.125%
1.559s
Fast T2T (T,=3,7,)
24
SL++
5.688
0.014%
0.139s
7.760
0.052%
0.182s
SL+G
5.688
0.014%
0.051S
7.758
0.036%
0.082s
DIFUSCO
SL+G+20pt
5,690
0.046%
0.23g
7.776
0.262
0.3%0s
T2T (2)=3)
[2
SL+G+20pt
5.689
0.031
0.026s
7.764
0.101%
0.037s
StraDiCO (7,=3)
SL+G+2Opt
5.689
0.019%
0.026s
7.761
0.067%
0.038s
12T (T,=50.7,=30) [3
SL+G+20pr
5.688
0.012
1.098s
7.760
0.058%
1.57ls
Fast T2T (3,=377,=3)
24
S1.+G+20pt
5.688
0.012%
0.139k
7.759
0.036%
0.
StruDCCO (2, (T,=37
SL+G+20pt
5.688
0.011%
0.059s
7.756
0.024%
0.083s
greedy decoding using a objective-aware scoring scheme. Inspired by the relaxed objective redefined [33, we combine task rewards and constraint penalties to form guidance signals. Specifically, we define the variable-wise score as score; pp/ (Ø; + e), where serves as a balancing term,
P: (x] G¹) denotes the predicted confidence, and Ø, encodes task-specific penalties:
d())SSP = d(i) (edge distance),
(i)MMs
Σ Pj (conflict potential)
(6)
JEN()
This scoring scheme favors confident variables that contribute positively to the task objective, e.g.. shorter edges in TSP or nodes likely to form larger independent sets in MIS, thus guiding decoding in an objective-aligned direction without requiring gradient computation.
Gradient- Iterative Refinement. Building on the proposed objective-aware scoring scheme, we further introduce an iterative refinement strategy to improve solution quality. Starting from feasible solution Sg, we apply structure-aware perturbations via variable-absorption noise, denoise the perturbed state using the consistency model, and greedily decode aware score. This process explores a local neighborhood around the current solution and concentrates inference within high-confidence regions. The refinement is fully forward-pan pass and can be iterated with minimal overhead, as detailed Algorithm We justify this procedure through the following informal proposition.
solution using the objective-
Proposition 3.1 (Refinement Enhances Solution Reliability, Informal). Let s be feasible solution decoded from a predictive distribution Py using an objective-awarr greedy strategy. Assume that noise operator Q., introduces bounded perturbations that preserve the the high-coofidence regions of pa. and that the consistency model fo is locally Lipschitz continuous under such perturbations. Then, iterative refinement converges toward fixed points that remain within locally stable, high-coofidence regions of the predictive space.
Remark. Our gradient-free refinement strategy is fundamentally enabled by the structural consis- tency of the variable-absorptionn noising model. Since each refinement step perturbs only subset of already selected variables, the resulting inputs remain semantically aligned with the current solution. This local consistency is preserved by the denoising process and reinforced by objective aware greedy decoding, enabling stable and meaningful refinement across iterations. In contrast, prior diffusion apply symmetric noise to all variables regardless of selection status, which destroys partial solution structure and produces perturbed inputs that are poorly aligned with the original solution. As a result, consistency denoising from such noisy inputs lacks directional guidance, and greedy decoding does provide reliable improvement. Therefore, while
models based on uniform noise [22 23 24
7

---

Table 3: Results TSP-500 and TSP-1000. S: Sampling Decoding.
TSP-500
TSP-1000
Algorithm
Type
Length|
Dropl
Time
Length
Drop.
Time
Mathematical Solvers or Heuristics
Concorde 36
Exact
16.546
0.00% 0.00%
18.672s 1.848s
23.118 23.119
0.00%
84.413s
LKH-3 26
Heuristics
16,546
0.00%
4.641s
Leasning-bused Solvers with Greedy Decoding
GCN 17
SL+G+2OPT
16.899
2.121%
0.128s
DIMES 19
Rl++G+2pt
17.165
3.742%
0.453s
BQ-NCO* 15
RL+G+20pt
16.838
1.766%
2.454s
23.647
2.287%
5.722s
DIFUSCO (T,=50) 22
SL+G
18.136
9.611%
1.442s
25.667
11.022%
4,982s
Fast T2T (T,=5) [2
SL+G
17.467
5.551%
0.251s
24.698
6.831%
0.971s
StruDiCO (T,=5)
SL+G
17.404
5.172%
0.239s
23.118
5.967%
0.900s
12f (7,30T0
SL+G
17,470
3.378%
5.334s
25.168
8.868%
12.871s
Fast T2T (5,
24
SL+G
16.919
2.244%
1.426s
23.936
3.539%
5.988s
StruDiCO (T,,,,7,-)
SL+G
16.887
2.045%
0.651s
23.755
2.753%
2.533s
DIFUSCO 22
SL=++20pt
16.817
1.61%
1.433s
23.567
1.936%
5.036s
Fast T2T (7;=5) (4
S1.+G+2pt
16.701
0.922%
0.261s
23.388
1.167%
0.979s
StnDDCCO
S1.+G+2ppt
16,669
0.728%
0.247s
23.348
0.996%
0.915s
T2T (7,=30,77=300 [23]
SL+++20pt
16.677
0.793%
3.367s
25.397
1.209%
13.089s
Fast T2T (7,=5,7,=55)
24
SL+G+20pt
16.611
0.383%
1.387s
23.257
0.603%
5.779s
StruDiCO (T,=5,1,=5)
SL+G+20pt
16.602
0.326%
0.674s
23.242
0.535%
2.614s
Learning-based Solvers with 4x Sampling Decoding
DIFUSCO (T,=550 22
SL+S
17.533
5,959%
2.131s
25.059
8.399
19.023s
Fast T2T (T,=5) [24
SL+S
17.024
2.874%
0.877s
24.096
4.231%
3.635s
StraDiCO (T,=5)
SL+S
16.995
2.696%
0.839s
24.007
3.849%
3.430s
[T,
SL+S
17.034
3.070%
9.f22s
24.838
7.444%
33.8113s
Fast T2T (T, (T,=5,T,-5)
24
SL+S
16.710
0.978%
5.216s
23.712
2.570%
13,346s
StraDiCO (T,=5,7,-5)
SL+S
16.688
0.846%
2.312s
23.471
1.527%
6.520s
DIFUSCO [2
SL+S+20pt
16.694
0.893%
4.941s
23.425
1.326%
19,217s
Fast T2T (7,=5) 24
S1AS+20pt
16.633
0.509%
0.911s
23.286
0.726%
3.733s
StnDDCCO
S1=S+20pt
16.611
0.383%
01.87s
23.273
0.670%%
3.541s
T2T (7,=50,7)=300 23
SL=S+20pt
16.621
0.453%
12,636s
25.371
1.070%
36,271s
Fast T2T 55,=
24
SL+S+20pt
16.580
0. 1944
5.095s
23.287
0.419%
13.029s
StruDiCO (T,=5,,,=5)
SL+S+20pt
16.575
0.16%%
2,437s
23.178
0.261%
6.836s
refinement can in principle also be applied to uniform-noise models, its effectiveness is substantially amplified under the monotonic, structure- strueture-preserving property of variable-absorption diffusion.
We summarize the key differences between StruDiCO and prior work (24 in Table I Unlike Fast T2T, which incorporates objective guidance during the denoising process, StruDiCO integrates task objectives directly into the decoding stage. This design eliminates the need for backward gradient computation, resulting in significantly lower time and memory complexity while enabling finer control over structure-aware refinement. In addition, Fig. plpreeenss comparative evaluation across six benchmark tasks terms of GPU memory usage, inference time, and solution quality (Drop), with all metrics normalized to Fast T2T (100%). StruDiCO consistently achieves superior efficiency and performance, with notable improvements on large-scale instances such TSP-1000 and MIS-ER.
Experiment
We evaluate method on two classic combinatorial optimization tasks- Traveling Salesman Problem (TSP) and Maximum Independent Set (MISS- a wide range of graph sizes and difficulty levels. Our evaluation includes comparisons against state-of-the-art (SOTA) exact solvers, heuristics, and neural baselines. For fair comparison, we adopt the standard diffusion based configuration where T, denotes the number of initial inference steps and Tg the number of guided refinement steps.
We report three metries across all settings: (1) Objective, the value of solution (tour length for TSP. subset size for MIS); (2) Drop, the relative performance degradation compared to reference solutions; and (3) Time, the average runtime per instance. All models are evaluated with batch size and in single-the thread mode unless otherwise specified. More details are provided in the Appendix

---

0.05
TSP100
0.05
TSP100
1.75
0.040
TSP1000
TSP1000
1150
0.035
(8)
ca 2.
Drop (%)
Drop (%)
9.04
1.25
Or0g 1992
0.04
Drop
Drop
0.020
1.00
0.08
0.03
0.75
0.025
TSP100
TSP1000
0.5
0.020
0.2
0.4
3.6
0.4
Step
Threshoid
Alpha
(a) Inference step.
(b) Mask threshold.
(c) Perturbation ratio
Figure 3: Hyperparameter study on different aspects of our method.
4.1 Results on TSP
Datasets. We follow prior works 12
to generate TSP instances with N E (50, 100, 500, 1000} nodes, uniformly sampled from the unit square. A TSP instance includes N 2-D coordinates and a reference solution obtained by heuristics.
23
24 351
Main Results. As shown in Tables and 3 our method achieves highly competitive solution quality under both greedy and sampling decoding (x4). For example, on TSP-1000, our method achieves relative drop of 0.535%, outperforming Fast T2T's 0.603% under the same T, 5. T = 5 configuration. terms of runtime, our method is 2.2x faster on average compared to Fast T2T and over 5x faster than T2T. Moreover, Fig. presents radar plots for memory, runtime, and drop across TSP variants, normalized to Fast T2T. Our method consistently reduces GPU memory by 30%-70% % achieves 40 90%65% % faster runtime, and improves solution quality, highlighting the benefit of our gradient-free refinement and constrained denoising.
Hyperparameter Study. We conduct hy- perparameter studies on TSP-100 and TSP- 1000 to analyze the impact of three core hyperparameters in our method: (1) Infer- ence step and guided step (T, ). As shown in Fig. 3al increasing the number of steps improves solution quality up to point, with performance saturating around T, Ty for both instance sizes. (2)
Table 4: Generalization results with Greedy Decoding.
Training
Testing
TSP-50
TSP-100
TSP-500
TSP-1K
DIFUSCO (7.-50)*
33
0.09%
0.25%
2.55%
2.71%
T2T (T, 3-=
0.02%
0.11%
1.60%
1.10%
T2T (T)
5y-5)
X
0.09%
0.36%
1.02%
1.26%
StnDDCO
0.01%
0.01% %
%
0.80%
DIFUSCO (T,=5))
1.44%
0.23%
3,44%
3.31%
T2T 12, T,-30)
23
0.56%
0.17%
2.47%
2.19%
TSP
12T
0.12%
0.02%
StuDDCO (2)=5 7,=5
0.16%
0.02%
0.34%
0.55%
Mask threshold (6). Fig. (3b indicates that setting appropriate threshold d is criti- cal. Low thresholds retain excessive noise, while overly high values limit exploration. The results demonstrate the tradeoff exis- tence and indicate that 8 0.8 achieve relatively better performance. (3) Perturba-
DIFUSCO
2X
4.16%
3.04%
1.40%
1.85%
(T,-00, T,
23
2.25%
T2T (T,-5 T--5) X
2.67%
1.77 %
0.38%
0.95%
StraDiCO (T,-5.
7,-5)
3.46%
2.96%
0.33%
0.49%
DIFUSCO (7,=50y
3.98%
T2T (T,=000 3,=30
23
4.66%
3.81%
1.61%
1.30%
Fast TMT (7, S, T.
A
3.46%
3,08% %
1.06%
0.58%
St,
4.31%
3.222
0.75%
0.54%
tion ratio (a). As shown Fig. 3c| the refinement quality depends sensitively on the perturbation ratio. Too small values fail to explore alternative candidates, while too large values destroy prior structure. moderate value (0.2
S 0.5) leads the lowest Drop for TSP-100 and TSP-1000.
Results for Generalization. We evaluate the cross-scale generalization ability of models by testing on TSP instances of varying sizes, while keeping the training set fixed. Table Table reports the Drop (%) under greedy decoding. StruDiCO achieves the lowest performance drop in most settings. Notably, when tested on TSP-50, the model trained TSP-1000 yields drop only 0.80%, outperforming Fast T2T (1.28 (1.26%) and DIFUSCO (2.71%) %).. Similar trends are observed on other test sizes (e.g.. TSP-500 or TSP- demonstrating that StruDiCO generalizes well across scales.
4.2 Results on MIS
Datasets. Following prior work [19
22 23
24
40
41 42).
use two types of graphs: random RB 44 with 700-800 nodes, where each
graphs [43] with 200-300 nodes and Erdös Berdös-Rényi (ER) graphs
edges appears independently with probability p 0.15.
Main Results. shown in Ta StruDiCO consistently outperforms diffusion-based baselines in both solution quality and efficiency. On ER graphs, it achieves the best Drop across all decoding

---

Table 5: Results on MIS. * quoted from 22 24
RB-[200-300]
ERR-700-800]
Algorithm
Type
SIZE1
Drop.
Time
SIZE
Drop.
Time
KaMIS 38 39
Heuristics Exact
20.0900*
0.00%
45.80%s
44.969'
0.00%
60.753s
Gurobi
Exact
20.090
0.00%
22.033s
41.28
8.203%
23,437s
DIFUSCO (T, 100)
22
SL+G
18.52
7.81%
36,667
18.462%
4.923s
Fast T2T (T,=5)
24
SL++
18.875
6.023%
0.085s
37.820
15.898%
0.262s
StruDICO (1,=5
SL+G
19.308
3.899%
0.086s
39,820
11.450%
0.261s
T2; 30,
30)
SL+G
18.98
5.49%
39 39.833
11.419%
6.253s
Fast T2T (T,
24
S1.+G
19.578
2.540%
0.399s
40.781
9.313%
1.217s
StruDiCO (7,55,0
SL.+G
19.748
1.707%
0.181s
42.125
6.324%
0.552s
DIFUSCO (T, 100)
SL+S
19.13
4,79%
39.083
13.092%
17.939s
Fast 12T (T,=5) [24
SL4S
19.430
3.29%
0.228s
39.767
11.568%
1.0466s
StruDiCO (7,=5)
19.756
1.687%
0.229s
41,531
7.645%
0.941s
12r (I, 30,7, 30
SL+S
19:38
3.53%
41.417
7.899%
22,4268
Fast T2T (T,=5.1.555)
SL+S
19.748
1.715%
1.079s
41.651
7.378%
4.379s
(1,
SL4S
19,900
0.934%
0.492s
43.265
3.789%
1.988s
Table 6: Ablation study on TSP and MIS tasks (Gap, J).
Variant
TSP-50
TSP-100
TSP-500
TSP-1000
MIS-RB
MIS-ER
Uniform CM (Fast T2T, 7,=5)
0.031%
0.101
0.922%
1.167%
6.023%
15.898%
VA CM (StrDDCCO)
0.032%
0.163%
1.091
1.183%
7.476%
23,461%
Uniform + CCS VA CCS (StruDiCO, 75=5)
0.025%
0.081%
0.898%
1.074%
5.878%
16.522%
0.019%
0.067%
0.728%
0.797%
3.899%
11.450%
modes: 6.324% under greedy decoding and 3.789 % under sampling, compared 9.313% 7.378% from Fast T2T and 11.419% / 7.899 % from T2T. In terms of runtime, StruDiCO is 11x faster than T2T and over 2x faster than Fast T2T under the same refinement setup (T, 5, T. = 5).
Generalization. Figures 6 show generalization performance on ER graphs with varying edge density (p from 0.2 to 0.4) and graph size (from 350-400 to 1400-1600). Our method achieves consistently better solution sizes, outperforming Fast T2T by up to 8% and DIFUSCO by over 20 % in sparse settings, while maintaining superior scalability.
4.3 Ablation Study
We conduct detailed ablation study to disentangle the contributions of the Variable-Ahsorptioo (VA) mechanism and Constrained Consistency Sampling (CCS). The results are summarized in Table 1) Replacing the uniform consistency model (CM) with VA slightly degrades performance. This is because the monotonic absorption process (1 + 0) produces conservative trajectories, structurally coherent but with limited exploration. By contrast, the uniform CM allows symmetric noise injection (0 + 1), which supports broader exploration. 2) Although CCS improves both uniform and VA models, the gain is substantially larger when combined with VA. This highlights that VA provides semantically consistent intermediate states, enabling CCS to operate in a low-noise, structured space. Overall, the ablation confirms that VA and CCS complementary: VA provides structural continuity, CCS leverages it for reliable variable selection, together accounting for the strong performance.
5
Conclusion
We have introduced a structured denoising diffusion framework tailored for CO problems. By modeling the forward process as variable absorption process and the reverse process as progressive variable selection mechanism, it enables the construction of interpretable partial solutions at each inference step. We also propose a gradient-free objective-aware decoding strategy that explicitly incorporates objective constraints to enhance inference quality unseen instances. Extensive experiments on TSP and MIS show the superior efficiency and effectiveness, achieving up to 3.5x faster inference, 70% lower memory usage, and substantial improvements in solution quality.
10

---

References
[1] Léo Baty, Kai Jungel, Patrick S Klein, Axel Parmentier, and Maximilian Schiffer. Combinatorial optimization-enriceed machine learning to solve the dynamic vehicle routing problem with time windows. Transportation Science, 58(4):708-725, 2024.
[2] Guman Singh and Mohammad Rizwanullah. Combinatorial optimization of supply chain networks: A retrospective & literature review. Materials today: proceedings, 62:1636-1642, 2022.
[3] Guyue Huang, Jingbo Hu, Yifan He, Jialong Liu, Mingyuan Ma, Zhaoyang Shen, Juejian Wu, Yuanfan Xu, Hengrui Zhang, Kai Zhong, et al. Machine learning for electronic design automa- tion: A survey. ACM Transactions on Design Automation of Electronic Systems (TODAES), 26 (5):1-46, 2021.
[4] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
[5] Michele Lombardi and Michela Milano. Boosting combinatorial problem modeling with machine learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 5472-5478, 2018.
[6] Andoni I. Garmendia, Josu Ceberio, and Alexander Mendibura. Applicability of neural com- binatorial optimization: a critical view. ACM Transactions on Evolutionary Learning and Optimization, 4(3):1-26, 2024.
[7] Wenzheng Pan, Hao Xiong, Jiale Ma, Wentao Zhao, Yang Li, and Junchi Yan. Unico: On unified combinatorial optimization via problem reduction matrix-encoded general tsp. In International Conference on Learning Representations, 2025.
[8] Haoyu Geng, Hang Ruan, Runzhong Wang. Yang Li, Yang Wang, Lei Chen, and Junchi Yan. Benchmarking pto and pno methods in the predictive combinatorial optimization regime. Advances in Neural Information Processing Systems, 37:65944 65971, 2024.
[9] Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and strong structure- hww.uure-aardness-awaaaaa baseline. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 441 1414-4425, 2023.
[10] Xinyan Chen, Yang Li, Runzhong Wang, and Junchi Yan. Mixsatgen: Learning graph mixing for sat instance generation. In The Twelfth International Conference Learning Representations, 2024.
[11] Ziao Guo, Yang Li, Chang Liu, Wenli Ouyang, and Junchi Yan. Acm-milp: Adaptive constraint modification via grouping and selection for hardness-preserving milp instance generation. In Forty-first International Conference on Machine Learning. 2024.
[12] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
[13] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 21 188 188821998,,,11111111111111111118 2020.
[14] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 35, pages 1936-1949, 2022.
[15] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances Neural Information Processing Systems, volume 36, pages 77416-77429, 2023.
11

---

[16] Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang. Haoran Ye. Minsu Kim, Sanghyeok Choi, et al. RI4co: an extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint arXiv: 2023.
[17] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: urXiv:/906.0122)) 2019.
[18] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7474-7482, 2021.
[19] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems, volume 35, pages 25531-25546, 2022.
[20] Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. In Advances in Neural Information Processing Systems, volume 36, pages 47264-47278, 2023.
[21] Scbastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffuuson model framework for unsupervised neural combinatorial optimization. In International Conference on Machine Learning, pages 43346 43367, 2024.
[22] Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. In Advances in neural information processing systems, volume 36, pages 3706- 3731, 2023.
[23] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 36, pages 50020-50040, 2023.
[24] Yang Li, Jinpei Guo, Runzhong Wang. Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion-based maining-to--estiigg solving for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 37, pages 30179-30206, 2024.
[25] Yang Song, Prafulla Dhariwal, Mark Chen, and Ilya Sutskever. Consistency models. In International Conference on Machine Learning, pages 32211-32255 1-2252.. PMLR, 2023.
[26] Keld Helsgaun. An extension of the lin-kemighann-helsgann tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017.
[27] Shipei Zhou, Yuandong Ding, Chi Zhang, Zhiguang Cao, and Yan Jin. Dualopt: A dual divide- and-optimize algorithm for the large-scale traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 37178-27186 2025.
[28] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[29] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[30] Yu Wang, Liang Hu, Xiaofeng Cao, Yi Chang, and Ivor W Tsang. Enhancing locally adaptive smoothing of graph neural networks via laplacian node disagreement. IEEE Transactions on Knowledge and Data Engineering, 36(3):1099-11) 2023.
[31] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances nearal information processing systems, 33:684006851, 2020.
[32] Yang Li, Yichuan Mo, Liangliang Shi, and Junchi Yan. Improving generative adversarial networks via adversarial learning in latent space. Advances in neural information processing systems, 35:8868-888 8881, 2022.
12

---

[33] Yang Li, Jiale Ma, Yebin Yang, Qitian Wu, Hongyuan Zha, and Junchi Yan. Generative modeling reinvents supervised learning: Label repurposing with predictive consistency learning. In Forty-second International Conference Machine Learning.
[34] André Hottung, Bhanu Bhandari, and Kevin Tiemey. Learning a latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2021.
[35] Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang, Haoyu Geng, Nianzu Yang, and Junchi Yan. Unify ml4tsp: Drawing methodological principles for tsp and beyond from streamlined design space of learning and search. In The Thirleenth International Conference on Learning Representations, 2025.
[36] David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver. https: https://www.mathh www..math... wwaterloo. wwtttptcctccooreee////ooococccae iiweeeiiidxxx.eee html 2006. Accessed: 2025-
04-21.
[37] Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. In International Conference on Learning Representations, 2022.
[38] Sehastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. In 2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX), pages 350. SIAM, 2016.
[39] Gurobi Optimization. Gurobi optimizer reference manual. http:://ww.guret com 2020. Accessed: 2025-04-21.
[40] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. In Advances neural information processing systems, volume 31, 2018.
[41] Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. In International Conference Learning Representations, 2022.
[42] Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what defer for maximum in- dependent sets. In International Conference on Machine Learning, pages 134-144. PMLR, 2020.
[43] Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. In Advances in neural information processing systems, volume 36, pages 1 11952-11996 2023.
[44] Paul Erdós and Alfréd Rényi On the evolution random graphs. Publ. Math. Inst. Hungar. Acad, Sci, 5:17-61, 1960.
[45] Christian Prins. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers operations research, 31(12):1985-21) 2004.
[46] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):61 1-644, 2012.
[47] Jiale Ma, Wenzheng Pan, Yang Li, and Junchi Yan. Coexpander: Adaptive solution expansion for combinatorial optimization. In Ferty- International Conference on Machine Learning. PMLR, 2025.
13

---

A Discussion on the Construction Paradigms of NCO
As illustrated in Fig- autoregressive (AR) methods construct solutions by selecting decision variables (nodes or edges) in a strictly sequential manner, typically requiring ((N) decoding steps, where N is the number of decision variables. In contrast, non-autoregressive (NAR) methods predict soft-constrained solutions in a one-shot pass, followed by heuristic post-processing to ensure feasibility, effectively reducing two extremes of variable selection granularity in neural combinatorial optimization (NCO).
single step. These paradigms represent the
Naturally, this raises the question: Can we design a construction paradigm that balances granularity and efficiency. lying between these two extremes? ? Recently, generative approaches based on diffusion models have achieved state-of-the-art performance and offer promising direction. However, they suffer from two critical limitations:
1. Excessive inference steps. Traditional diffusion models typically involve hundreds or thousands of steps (e.g., T = 1000), often exceeding the number of variables in the problem, which introduces significant inefficiency.
2. Lack of structural interpretability in intermediate states. As shown in Fig. inter- mediate solutions during denoising are usually dense and noisy (e.g., full graphs for TSP), offering little insight into how variables are progressively determined.
The recent introduction of consistency models 25
has mitigated the first issue by enabling high- quality solutions with as few as 3-5 inference steps, refered as FastT2T [24]. Building on this progress, work addresses the second issue by proposing structured diffusion framework with step-wise interpretability.
As shown in Fig. 5b our model begins from empty solution and progressively activates decision variables with high predicted confidence at each inference step. This process can viewed as variable selection trajectory, where each intermediate state incrementally extends the previous one, forming structurally consistent sequence of partial solutions.
Jo(G,X x
= #nodes
Input X
x
Neural Network
x!-1
Solution x
(a) The solving pipeline Autoregressive construction.
fo
T=1
Graph
Neural Network
Solution
(b) The solving pipeline of Non-Autoregressive construction.
Figure Comparison solving pipelines between Autoregressive and Non- Con-Autrregressvee construc- tions.
14

---

e)
T=Inference Steps
Input X7
Neural Network
X
Solution
(a) The solving pipeline of FastT2T.
fo X.C.X',O E)
T=Inference Steps
InputX!
X
Neural Network
X
Solution x
(b) The solving pipeline of StruDiCO (Ours).
Figure Comparison of solving pipelines between FasTT2T and StruDiCO. Green solid lines indicate newly added edges, while green dashed lines represent deleted edges.
B Discussion on Structural Consistency in Denoising
B.1 Limitations of Vanilla Reverse Sampling
Most diffusion based CO solvers, including our main pipeline (see Sec. 3.2 follow the standard
multistep consistency sampling protocol 24 25], as shown in Algorithm which iteratively denoises and resamples Xo given intermediate states While this process can recover high-quality solutions, does not strictly enforce any structural constraints on the reverse trajectory, such as feasibility preservation across steps.
Algorithm 3 Multistep Consistency Sampling
Require: Consistency model fo(t..s), graph instance G, time sequence T1 > ... > NN-1
1: Sample XT ~ U
2: (xo G) f- fx
(xr, G) 3: Xo (x G)
4: for
N, do
5: Xr, Cat(p X0 20.)))
6: Po G) fo (X,,, Tn: G)
7: Xo pe(xo G)
8: for
9: return Solution Xo
B.2 Step-Wise Decoding Sampling for Intermediate Feasibility
To further improve step-wise feasibility, explore stronger variant: step-wise greedy decoding. At each reverse step т, we rank the predicted heatmap Pa (X, = X,, T, G)) in descending order and activate the top n., variables to form x,, subject task-specific constraints (e.g., no subtours or conflicts). Here, ny is determined by the expected number of active variables given by the cumulative transition matrix Q under the reverse schedule.
This approach better aligns the reverse process with the semantics of the variable-absorptinn forward process and can combined with feasibility filters (e.g., constraint checks) to construct strictly valid x, at every step. However, systematic exploration of this strategy is left future work.
15

---

C Full Proof of Theorem 3.1
We provide the complete mathematical proof Theorem 3.1 which formally analyzes the effect of threshold-base masking on the KL divergence between the predicted and true solution distributions.
Theorem C.1 (Constrained Sampling Reduces Divergence, Full Version). Let q(xo G) be the true distribution and pe(xo Xx, T, G) the model prediction. Fix a threshold å E (0, and define the constrained support
M3 E [M] (x = 1 x,, G) > 8), So = (xo : supp(xo) S Ms}.
(7)
(8)
Let the masked (renormalized) model be
Po (xo) = po po(Xo) l[xo E Sss
(9)
Zs
Z8
Σ (xo) E (0, 1].
(10)
XnESA
and define the log-likelihood ratio f(xe) log (Xo) Assume q(xx) > O whenever po (Xx) > 0 (so g(xo)
that DKL (KL(Pol)g) < 0o). Then the reverse-KL. difference admits the exact decomposition
DKL(Fellg DKL(pollq) (1 Zz) (As + ca).
(11)
where
As ((((11))(((xo)] Epoc (8x) [((x))];
(12)
log Zi8
C5
(2 0). 28
(13)
Consequently,
(xo(lll)4) (RO(Pollg) Eb;
(14)
EB (1 Ls) (As + c5)]
(15)
and in particular, if A. 2 -cg then DKL (pell) I DKL (pollq), with strict inequality whenever Zg < 1 and the inequality is strict.
Proof. All sums below are over the discrete space of Xg. We use the shorthand p(xo) = po (Xo
X,, G), q(x)) q(x, G). and p(xx) po (xo), suppressing the conditioning for readability.
Step 1: Reverse-KL under masking. By definition of ğ and Zz,
p(xo)
Xu Ss.
p(x))
Za
(16)
0,
Xn E Ss-
Since q > 0 wherever p > O, we have > on Sz (because p > 0 there if and only if > 0). Then
Σ p(xu) log p(xo)
(kl() =
(17)
g(xo)
E&
p(xo)
log p(xo) /Zs
(18)
Z8
((xo)
XoSS;
p(X))
log p(xn)
p(xp)
log Zs
(19)
Zs
((xo)
Zo
No XoES,
Xo ES,
log p(Xo)
Ep(((S))
log 2o8
(20)
{(xo)
(o(1s))(((xn)) - log Zz.
(21)
16

---

Step 2: Reverse-KL of the original model. Decompose into its mass on Sj and S.:
(RL(Pll1)= = Ep(xo) log p(xo) q(xx)
(22)
Σ p(xo) {(xo) + Σ p(xo) l(xo)
(23)
xoES$
Xo
Zg Ept p( [[(xo]] + (1 (1)) E Ep() ((xx))-
(24)
Step 3: Taking the difference. Subtracting (B) from (A) gives
(xl()) (pllg)
(25)
(Ep(1s) (s,) log Zz) - Zo E (p( + (1 Σσ) Bp((1s5)
(26)
(1 7s6) Ep(-(sa) - Zz) Ep(-1sp) [e) -log Za
(27)
= --(1- - Es) [p(-1sg)(11 -Ep(-1.))( llog Zo
(28)
As = -11 - Z As log Z8-
(29)
When Za the mask is identity and both sides equal; for Zg E (0, 1) rewrite the last term
log Zs
log ZB = (1 Zx)
(1 Zs) Co.
(30)
7
which yields the exact decomposition Eq.
DKL (fllg) = DKL (pllg) (1 Zs) (As ca).
(31)
Step 4: Upper bound and sufficient condition. Since for any real x. x x4 (-x)+ with
x. max (I. 0}, we get the one-sided bound
DKL (gllg) < (pll)) + +1 Zz) [- (As + cs)
(32)
Moreover, whenever As 2 (equivalently Bp(-ss9(e]] 2 Ep(()) - cs), the difference in Eq. (11) is nonpositive and thus (xu(fll4) & (pl(p)))) with strict improvement if Z3 < and the inequality is strict.
D Supplementary Experiments
D.1 Applied to Capacitated Vehicle Routing Problem
To further demonstrate the generality of StruDiCO beyond classical edge-selection (TSP) and node- selection (MIS) tasks, we extend it to the Capacitated Vehicle Routing Problem (CVRP), a more challenging CO task that involves both global routing structures and hard feasibility constraints, such customer demands and vehicle capacities. The refinement procedure for CVRP follows the same design as that for TSP: greedy decoding is performed based on the learned heatmap, with the objective guided by a distance-based penalty term. We evaluate StruDiCO CVRP-50. CVRP- 100, and CVRP-200 under standard benchmark settings [16]. To further improve both solution feasibility and cost, incorporate local search heuristic (Classic-LS (45)) during inference. As summarized in Table 7 these results demonstrate that StruDiCO effectively generalizes to CVRP, consistently improving over learning-based baselines while remaining efficient.
D.2 Results on Real- World Data
We evaluate our model trained on randomly generated 100-node instances against real-world TSPLIB benchmarks containing 50-200 nodes. For fair comparison, we adopt the same hyperparameter settings as (44) with T, = Tg 10. As shown in Table 8 StruDiCO demonstrates superior performance, achieving an average optimality gap of only 0.13%
17

---

Table 7: Results on CVRP. LS: Local Search.
CVRP
CVRP 200
Algorithm
Type
Length4
Dropl
Time
Length)
Drop.
Time
Length
Dropl
Time
HGS 46
Heuristies
10.37
0.00%
15.56
0.00%
20s
19.63
0.00%
60s
Sym-NCO
RL+LS
10.57
1.95%
0.09s
15.93
2.37%
0.19s
20.19
2.86%
0.36s
COExpander 47
SL+LS
10.77
3.90%
0.04s
16.22
4.25%
0.06s
20.59
4.89%
0.15s
StruDiCO (3-77 =3)
SLAL
10.48
1.12%
0.05s
15.85
1.88%
0.11s
20.25
3.19%
0.26s
StruDiCO (7, (7,55
SL+LS
10.45
0.85%
0.07s
15.80
1.53%
0.17s
20.16
2.71%
0.38s
Table 8: Solution quality for methods trained on random 100-node problems and evaluated on TSPLIB instances with 50-200 nodes. * denotes results quoted from previous works (24]
Instances
AM*
GCN+
Learn20PT
GNNGLS
DIFUSCO
T2T
Fast T2T*
Ours
cil51
16.767%
40.025%
1.725%
1.529%
2.82%
0.14%
0.00%
0.00%
berlin52
4.169%
33.225%
0.449%
0.142%
0.00%
0.00%
0.00%
0.00%
st70
1.737%
24.785%
0.040%
0.764%
0.00%
0.00%
0.00%
0.00%
ci176
1.92%%
27.411%
0.096%
0.163%
0.34%
0.00%
0.00%
0.00%
pr76
0.816%
27.793%
1,228%
0.039%
0.40%
0.00%
+0.00%
ra199
2.645%
17.633%
0.123%
0.550%
0.09%
0.09%
0.00%
0.00%
kroA100 100
4.017%
28.828%
18.313%
0.728%
0.10%
0.00%
0.00%
0.00%
kroB100
5.142%
34.686%
1.119%
0,147%
2.29%
0.74%
0.65%
0.00%
kroC100
0.972%
35,506%
0.349%
1.571%
0.00%
0.00%
0.00%
0.00%
kroD100
2.717%
38.018%
0.866%
0.572%
0.07%
0.00%
0.00%
0.00%
kroE100
1.470%
26.589%
1.82%%
1.216%
3.83%
0.27%
0.13%
2.15%
rd100
3,407%
50.432%
1.725%
0.003%
0.08%
0.00%
0.00%
0.11%
eil101
2.994%
21.776%
1.529%
0.03%
0.03%
0.00%
0.00%
0.00%
lin105
1.739%
34.902%
1.867%
0.606%
0.00%
0.18%
pr107
3,933%
80.564%
0.898%
0.439%
0.91%
0.61%
0.62%
0.18%
pr124
2.677%
70.146%
10.232%
0.755%
1.02%
0.08%
0.08%
-0.00%
bier127
5,908%
45.561%
3.044%
1,948%
0.94%
0.54%
1.50%
0.045
ch130
3.182%
39.090%
0.709%
3.519%
0.29%
0.06%
0.00%
0.24%
pr136
5.064%
58.673%
0.000%
3.387%
0.1%
10%
0.01 %
0.04%
pr144
7.641%
55.837%
1.526%
3.581%
0.80%
0.50%
0.39%
0.00%
ch150
1.584%
49.743%
0.321
2.113%
0.57%
0.49%
0.00%
0.04%
kroA
3.784%
45.411%
0.724
2.984%
0.34%
0.14%
0.00%
0.24%
kroB150
2,437%
56.745%
0.886%
3.258%
0.30%
0.00%
0.07%
0.00%
pr152
7.494%
49.376%
3.119%
3.119%
1.69%
0.83%
0.19%
0.69%
u159
7.551%
38.338%
0.054%
1.020%
0.82%
0.00%
0.00%
0.00%
rat195
6.893%
24.968%
0.743%
1.666%
1.48%
1.27%
0.79%
-0.00%
d198
373.020%
62.952%
0,522%
4.727%
3.32%
1.97%
0.86%
-0.00%
kroA200
7.106%
40. 8855
1.441%
2.029%
2.28%
0.57%
0.49%
0.00%
kroB200
8.541
43.643%
0.646%
2.589%
2.35%
0.92%
2,50%
-0.00%
Mean
16.767%
40.025%
1.725%
1.529%
0.97%
0.35%
0.28%
0.13%
D.3 Supplementary Results of Generalization Study
To further evaluate the generalization ability of StruDiCO, conduct additional experiments MIS instances with varying edge densities and graph sizes. Specifically, we test models trained on ER graphs with p 0.15 and 700-800 800 out-of-distribution graphs with different values (0.2, 0.3, 0..4) and node counts (350-400, 1400-1600). As shown in Figures 6 StruDiCO consistently outperforms prior diffusion-basee baselines (e.g., DIFUSCO (22). T2T [23], Fast T2T (24) under both greedy and sampling decoding, demonstrating superior adaptability to distribution shifts in both graph sparsity and scale.
E Experimetnal Details
E.1 Hardware
All models are trained and tested using NVIDIA A40 (48G) GPUs and Intel(R) Xeon(R) Gold 5220
CPU @ 2.20GHz.
18

---

Greedy Decoding
Greedy Decoding
25.28 30 52
30.25
50
50.95
TZT
Ours
30
76
KaMiS
19.20
36.M5
34.03
34.29
18 17.37
16.0
32.56
15.84
30
10.10
u1
12.77
$5
10
CCM
p= 0.2
0.3
0=0.4
350-400
1400-1600
Figure 6: Generalization performance from p
Figure Generalization performance from ER
0.15 to p = 0.2, = 0.3, and = 0.4.
700-800 to ER 350-400 and 1400-1600.
Sempling Decoding
Sampling Decoding
35
28.0g00. 5d
4..4
DIFUICOO
Fast T2T
MUS
KaMIS
40
37.96
33:51
20
17.37
KaMIS
29.12
12 18.03
20
0=02
0.3
0=0.4
350-400
1400-1600
Figure 8: Generalization performance from
Figure 9: Generalization performance from ER
0.15 p 0.2, p 0.3, and p 0.4.
700-800 to ER 350-400 and 1400-1600.
E,2 Sparsification
For large-scale TSP problems, we follow 22 23 24 to employ sparse graphs, as sparsified by constraining each node connect only nearest neighbors, determined by Euclidean distances. For TSP-500, we set k 50, and for TSP- 1000, k = 100. This strategy prevents the exponential increase in edges typical in dense graphs as node count rises.
E.3 Dataset
Our dataset settings follow previous works 22 23 24 to ensure fair and consistent comparisons.
The reference solutions for TSP-50/100 are labeled using the Concorde exact solver [6], while TSP. 500/1000 solutions are generated by the LKH-3 heuristic solver (26). The test sets for TSP-50/100 contain 1280 instances sourced from [12 17], and those for TSP-500/1000 contain 128 instances
from [18]. For the MIS task, we use KaMIS 38 to generate reference solutions for both RB and graphs. The training set consists of 90,000 randomly generated instances, and the test set includes 500 instances. For ER graphs, generate 163,840 training instances, and the test set is obtained from [19
E.4 Hyperparameters
We have organized the training settings and model parameters of StruDiCO in Table 9
19

---

Table 9: Details about the training hyperparameters of StruDiCO.
Problem
Dataset Size
Batch Size
Epoch
Learning Rate
Hidden Dimension
Noise Degree
TSP-50
1.502k
32
50
2c-4
256
0.5
TSP-100
1,502k
I2
50
2c-4
256
0.5
TSP-500
128k
6
50
2e-4
256
0.5
TSP-1000
64k
50
2e-4
256
0.5
MIS-RB
90k
50
2e-4
256
0.3
MIS ER
163k
50
2e-4
128
0.5
F Network Architecture Details
F.1 Input Embedding Layer
Given node vector RNx2 weighted edge vector E R., denoising timestep & frr...., TM }. where N denotes the number nodes in the graph, and E' denotes the number of edges, we compute the sinusoidal features of each input element respectively:
34 concat(T;.on T4,1)
(21)
sin Dig Tu/d" COS
Fng
Fi.j
Zij
テij concat
Tu/d T2/d
sin
COS
72/d
sin
Ta/a'
COS
Td/d
(22)
sin E;
e
E;
6;
e
& concat
To/d
1 COS
To/a
sin
72/d CO8
72/d
sin
Tdjd 1 COS
Tddd
(23)
t
= concat
sim
Toya
COS
To/d
sin
72/d 1 COS
T2/d
sin
Ta/á
COS
Tajd
(24)
where d the embedding dimension, T is a large number (usually selected as 10000), and concat()) denotes concatenation.
Next, we compute the input features of graph convolution layer:
2 Wfi;
(25)
0 W
(26)
(ReLU((()))))
(27)
where e E Rd, de is the time feature embedding dimension. Specifically, for TSP, the embedding input edge vector is weighted adjacency matrix, which represents the distance between different nodes, and e is computed above. For MIS, we initialize e to zero matrix 0
F22
Graph Convolution Layer
Following 17 the cross-layer convolution operation is formulated as:
2 L ReLU Σ Th O Wsr)))
(28)
ij cy + ReLU(BN(WWe) + W
(29)
a(e'))
The Ey (ely) +
(30)
where af and cly denote the node feature vector and edge feature vector layer 1, Wi,... Ws Rlxh denote the model weights, and v/ denotes the dense attention map. The convolution operation integrates the edge feature to accommodate the significance of edges in routing problems.
20

---

For TSP, we aggregate the timestep feature with the edge convolutional feature and reformulate the update for edge features follows:
1/ c/y + ReLU + + Wga()) + (REL(((())
(31)
For MIS, aggregate the timestep feature with the node convolutional feature and reformulate the update for node features as follows:
2 24 Re
Σ The o w)xs)) W
(32)
jm
E.3
Output Layer
The prediction the edge heatmap in TSP and node heatmap in MIS as follows:
Ei,j Softmax/nomm(RLLLWW......
(33)
24
(34)
where L is the number of GCN layers and norm is layer normalization.
F4 Hyper-parameters
For both TSP and MIS tasks, we construct 12-layer GCN derived above. We set the node, edge, and timestep embedding dimension 256, 128 for TSP and MIS tasks, respectively.
G Limitations and Broader Impacts
Despite the effectiveness of our proposed method, several limitations remain. First, our model is trained under a supervised learning paradigm, which relies on access to a substantial number of labeled optimal near-optimal solutions. While this setting is practical for many standard CO benchmarks, may present limitations when extending to domains where high- high-quality supervision is difficult expensive to obtain. Second, although demonstrate improved generalization over existing diffusion-basee solvers [24] in fixed-scale settings, the model still faces challenges in handling real-world CO problems with unknown variable instance sizes. Third, while diffusion process incrementally constructs solutions in a structured manner, it still follows a non- autoregressive paradigm and thus requires heuristic post-processing (e.g., greedy decoding) to enforce final feasibility. This dependency may constrain its applicability in tasks where domain-specific heuristics unavailable or expensive to design.
This work contributes to the growing field of learning-bat based combinatorial optimization, with potential applications in logistics, circuit design, scheduling, and operations research. By introducing interpretable and efficient generative methods, our approach can improve decision-making in domains that require both scalability and transparency.
21

---

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: Sec. and Sec.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Appendix G
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create 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 (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
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?
Answer: [Yes]
22

---

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

---

Answer:
[No]
Justification:
The source code will be made publicly available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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
cttppsscccpbbbccpppeeccccc guwdes/ddeeeeee Cooeeeoodeesssseeeeee / cassiicyncccyy for more details.
The authors should provide instructions on 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Appendix Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, 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 solution quality over 128 or 1,280 instances Sec.
22
23
24
report the average
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).

---

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

---

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 or 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: no such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
Answer: [Yes]
Justification: The original papers that introduce models and datasets used in the paper have been cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

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

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neure wwwparippps..coooeeeeeeeee for what should or should be described.
28


Reviews:
[{"review_id": "pfUix0yxAZ", "reviewer": "Reviewer_Z5NJ", "summary": "The paper introduces StruDiCO, a structured denoising diffusion framework designed to solve combinatorial optimization (CO) problems efficiently and interpretably. StruDiCO uses Structured Forward Diffusion to ensure that every intermediate state remains a structurally valid partial solution. This “structure-preserving” approach allows the model to maintain interpretability and stability across the denoising trajectory. In the reverse process, StruDiCO selectively includes variables based on a confidence threshold, avoiding low-confidence predictions. In addition, StruDiCO uses an objective-aware refinement framework that efficiently incorporates\n task objectives without requiring backward gradient computation. Empirical results on standard benchmarks - including the Traveling Salesman Problem (TSP) and Maximum Independent Set (MIS) - demonstrate that StruDiCO outperforms prior diffusion models in both solution quality and inference speed, while using significantly less memory.", "questions": "- The authors can provide a more detailed explanation of why their method outperforms T2T and DIFUSCO in terms of accuracy.\n\n- How much labeled data is enough for your method?", "limitations": "Yes, the paper addressed the limitations at Appendix G", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The paper proposes a new solution for CO to bridge the gap between step-wise interpretability and global distribution modeling. Their solution, StruDiCO introduces a variable absorption noising process that gradually deactivates variables during the forward diffusion stage. Unlike prior methods (e.g., T2T, DIFUSCO) that apply random or uniform noise, this approach ensures that each intermediate state remains a structurally valid partial solution. In the reverse process, StruDiCO only selects variables whose predicted confidence exceeds a set threshold (δ), discarding low-confidence choices. \n\n- StruDiCO achieves a significantly faster inference and lower memory usage than prior diffusion-based models.\n\nWeaknesses:\n\n- It lacks a valid explanation on why their method is empirically strong compared to other diffusion-based methods\n\nThe refinement step in StruDiCO is based on heuristics. It is unclear how their method is efficient for the new CO problem\n\n- Like other diffusion-based methods, their solution needs a substantial number of labeled optimal or near-optimal solutions.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Z5NJ,\n\nThanks for your recognition and valuable questions.\n\n---\n\n> **Q1: Clarification on why the proposed method achieves higher accuracy than other diffusion-based methods.**\n\nTo better explain the performance gain of our method over existing diffusion-based approaches (e.g., those using uniform diffusion), we performed an ablation study to isolate the individual contributions of Variable Absorption (VA) and Constrained Consistency Sampling (CCS).\n\n**Ablation Study (Gap, %↓):**\n\n| Variants          | TSP 50    | TSP 100   | TSP 500   | TSP 1000  | MIS RB    | MIS ER     |\n| ----------------- | --------- | --------- | --------- | --------- | --------- | ---------- |\n| Uniform CM        | 0.031     | 0.101     | 0.922     | 1.167     | 6.023     | 15.898     |\n| VA CM             | 0.032     | 0.163     | 1.091     | 1.183     | 7.476     | 23.461     |\n|Uniform+CCS |     0.025 | 0.081   | 0.898   | 1.074  | 5.878  | 16.522 |\n| **VA+CCS (Ours)** | **0.019** | **0.067** | **0.728** | **0.797** | **3.899** | **11.450** |\n\nAs shown, replacing the uniform noise (used in DIFUSCO, T2T, and FastT2T) with the Variable-Absorption (VA) mechanism alone leads to a performance degradation. This is because VA introduces a monotonic absorption process, where variables are only deactivated (i.e., 1 → 0) during the forward diffusion. While this preserves structural continuity at each timestep, it results in overly conservative trajectories when used alone, **limiting exploration and diversity in the reverse process**. In contrast, the Uniform Consistency Model (CM) allows symmetric noise injection (both 0 ↔ 1), which encourages broader exploration and increases the chance of reaching high-quality solutions.\n\nThe key point we emphasize is that **VA was not designed to be effective in isolation**. Rather, its role is to create structurally consistent and interpretable intermediate states, serving as a reliable foundation for the reverse process when combined with CCS. Once CCS is applied, which **selectively activates only high-confidence variables at each step**, the VA framework’s structure-preserving property becomes crucial: **it ensures that CCS operates over a low-noise, semantically meaningful space**. Notably, while CCS also improves performance when applied to the Uniform CM baseline, the gain is significantly amplified when combined with VA.  This confirms that these two components are complementary and jointly responsible for the observed performance gains.\n\nThis response primarily addresses your concern regarding the **impact of diffusion model variations on accuracy**. For a more comprehensive ablation analysis, please refer to our response to Reviewer XM73, Q1.\n\n---\n\n> **Q2: How much labeled data is enough for your method?**\n\nFor fairness, we adopt the **same** training set sizes as those used in DIFUSCO and FastT2T.\n\n\n| Problem  | # Train Instances |\n| -------- | ----------------- |\n| TSP-50   | 1.58M             |\n| TSP-100  | 1.58M             |\n| TSP-500  | 128K              |\n| TSP-1000 | 64K               |\n| MIS-RB   | 90K               |\n| MIS-ER   | 163K              |\n\n---\n\n> **W2: The refinement step in StruDiCO is based on heuristics. It is unclear how their method is efficient for the new CO problem.**\n\nIn fact, StruDiCO can handle a wide range of constrained combinatorial optimization (CO) problems. Leveraging the expressive capacity of generative models, our approach learns to approximate the underlying constraint structure, producing heatmaps that are already close to feasible. We then apply lightweight heuristic post-processing (e.g., greedy decoding) to convert these outputs into strictly feasible solutions. This paradigm enables general applicability to arbitrary constraints and aligns with the inference strategies adopted in prior representative works such as Diffusco, T2T, and Fast T2T.\n\nTo further demonstrate the generality of StruDiCO beyond classical edge-selection (TSP) and node-selection (MIS) tasks, we extend it to the **Capacitated Vehicle Routing Problem (CVRP)**—a more challenging CO task that involves both global routing structures and hard feasibility constraints, such as customer demands and vehicle capacities. The **refinement procedure for CVRP follows the same design as that for TSP**: greedy decoding is performed based on the learned heatmap, with the objective guided by a distance-based penalty term. We evaluate StruDiCO on CVRP-50, CVRP-100, and CVRP-200 under standard benchmark settings \\[1]. To further improve both solution feasibility and cost, we incorporate a local search heuristic (Classic-LS \\[2]) during inference.\n\n**To the best of our knowledge, StruDiCO is the first heatmap-based model that surpasses sequence-based models on VRPs.**\n\n\n| Algorithm                            | Type       |  Length↓ | Drop↓     | CVRP 50 Time  |  Length↓ | Drop↓     | CVRP 100 Time  |  Length↓ |  Drop↓     | CVRP 200 Time  |\n| ------------------------------------ | ---------- | --------------- | --------- | ----- | ---------------- | --------- | ----- | ---------------- | --------- | ----- |\n| HGS \\[3]                                 | Heuristics | 10.37           | 0.00%     | 1s    | 15.56            | 0.00%     | 20s   | 19.63            | 0.00%     | 60s   |\n| Sym-NCO \\[1]                             | RL+LS      | 10.57           | 1.95%     | 0.09s | 15.93            | 2.37%     | 0.19s | 20.19            | 2.86%     | 0.36s |\n| StruDiCO ($T_s=3$,$T\\_g=3$) | SL+LS      | 10.48       | 1.12% | 0.05s | 15.85        | 1.88% | 0.11s | 20.25        | 3.19% | 0.26s |\n| StruDiCO ($T\\_s=5$,$T\\_g=5$) | SL+LS      | **10.45**       | **0.85%** | 0.07s | **15.80**        | **1.53%** | 0.17s | **20.16**        | **2.71%** | 0.38s |\n\n---\n\n#### **References**\n#### \\[1] RL4CO: An Extensive Reinforcement Learning for Combinatorial Optimization Benchmark, 2024\n\n#### \\[2] A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem, 2004\n\n#### \\[3] A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems, 2012\n\n---\n\nWe hope this response could help ease your concern and wish to receive your further feedback soon.\n\nBest regards,\n\nThe Authors"}, {"review_id": "X9UvxlFkBo", "reviewer": "Reviewer_RWGz", "summary": "This paper proposes StruDiCO, a structured denoising framework for combinatorial optimization (CO). Its two main novelties are:\n- A structured noising process that enforces monotonicity in the forward and reverse directions, aiming to make the denoising path more efficient.\n- A gradient-free decoding approach, with no dependency on the gradients from objectives.\nIt claims significant improvements in speed (3.5x) and memory saving (70%), and improved solution quality as well", "questions": "- The improvements in TSP and MIS looks minimal. Can you elaborate on why the performance gap is small, and under what settings the proposed method provides more substantial benefits?\n- Can you provide a more detailed ablation that showcase the contribution of the gradient-free refinement? How much does each component in StruDiCO contribute to the final performance improvement?\n- Could StruDiCO be generalized well to more CO problems?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The gradient-free refinement framework with eliminated back-propagation is a practical contribution\n- The paper proposes a threshold-based constrained sampling strategy with theoretical grounding\n\nWeaknesses:\n- Marginal empirical improvements: while the method is cleanly designed, its gains over strong baselines are often small or inconsistent, making it difficult to justify the additional complexity of introducing the structured process.\n- Gradient-free approach is not critical in tested examples: the tested tasks TSP and MIS do not present known issues with gradient use, so it’s unclear when this feature would be critical.\n- The results are based on TSP and MIS which are two common tasks in CO. More diverse tasks would show broader applicability of the proposed method", "was_revised": true, "final_justification": "The authors have provided thorough responses to the questions raised during the review, effectively addressing my concerns. As a result, I have updated my rating.", "rebuttal": "Dear Reviewer RWGz,\n\nThanks for the thorough review and valuable comments. Below we respond to your specific comments.\n\n--- \n\n> **Q1: The improvements in TSP and MIS look minimal. Can you elaborate on why the performance gap is small, and under what settings the proposed method provides more substantial benefits?**\n\nWe respectfully disagree with the view that the improvements on TSP and MIS are minimal. Across various settings, **StruDiCO achieves average relative performance gains of 19.6% (TSP) and 38.1% (MIS)** over the strongest diffusion-based baselines (e.g., Fast T2T). While the absolute reductions in optimality gap may appear numerically small, it is important to recognize that these improvements are achieved in an **extremely low-error regime**, where prior methods were already within 1% of optimality. Improving further under such conditions is inherently more challenging and thus more meaningful.\n\nMoreover, **StruDiCO delivers substantial improvements in efficiency**. In particular, StruDiCO introduces a gradient-free refinement mechanism that significantly accelerates inference compared to existing gradient-based refinement methods (e.g., T2T, Fast T2T). Specifically, we observe up to 70\\% reduction in GPU memory usage and a 3.5$\\times$ speedup in inference time, as shown in Tables 2–5 and Fig. 2 of the main paper. These results demonstrate that StruDiCO advances both solution quality and computational efficiency, offering a practical and scalable alternative to gradient-based refinement.\n\nBeyond performance, **StruDiCO also enhances interpretability** by maintaining structurally valid intermediate states throughout the diffusion process. This structure-preserving design facilitates step-wise understanding of the solution construction, enabling deeper analysis of combinatorial patterns—an aspect particularly valuable for operations research and scientific decision-making applications.\n\n Please kindly note that reviewers Z5NJ, XM73, and 2ZPS all acknowledge the empirical results of our method.\n\nAs for the settings under which our method offers more substantial benefits, we observe that the improvements are especially **pronounced in larger-scale and structurally complex problem instances**—such as **TSP-1000** and **MIS-ER** (see Fig. 2). In these challenging scenarios, the advantages of structure-preserving diffusion and gradient-free objective-aware refinement become more evident, leading to larger gains in both solution quality and efficiency.\n\n---\n\n> **Q2: Can you provide a more detailed ablation that showcases the contribution of the gradient-free refinement? How much does each component in StruDiCO contribute to the final performance improvement?**\n\nThank you for the thoughtful question. We provide a detailed ablation study to isolate the contribution of each component in our method. The analysis focuses on two parts:\n\n1. The effect of **Constrained Consistency Sampling (CCS)** in the main inference process, and  \n2. The contribution of the **gradient-free objective-aware refinement** module applied on the initial solution solved by StruDiCO with $T_s=5$.\n\nSpecifically, we compare several variants, including:  \n- **VA only**: using the Variable-Absorption diffusion with greedy decoding;  \n- **+CCS**: where low-confidence variables are masked;  \n- **Vanilla Refinement**: which refines the initial solution without gradient-free objective guidance (OG).\n\n#### Table: Ablation Study (Gap, % ↓)\n\n| Variant                      | TSP-50 | TSP-100 | TSP-500 | TSP-1000 | MIS-RB | MIS-ER |\n|-----------------------------|--------|---------|---------|----------|--------|--------|\n| VA only                     | 0.032  | 0.163   | 1.091   | 1.183    | 7.476  | 23.461 |\n| + CCS (StruDiCO, \\$T\\_s\\$=5)      | 0.019  | 0.067   | 0.728   | 0.797    | 3.899  | 11.450 |\n| Vanilla Refinement          | 0.012  | 0.033   | 0.381   | 0.672    | 1.922  | 7.611  |\n| + OG (StruDiCO, \\$T\\_s\\$=\\$T\\_g\\$=5)    | **0.011** | **0.025** | **0.319** | **0.473**  | **1.707** | **5.579** |\n\nFrom the results, we first observe that incorporating **Constrained Consistency Sampling (CCS)** significantly enhances the performance of Variable Absorption (VA), yielding up to a **51% reduction in optimality gap** (e.g., MIS-ER: 23.461 → 11.450). This improvement arises because CCS prevents low-confidence variables from being prematurely activated, resulting in more stable and reliable inference trajectories.\n\nBuilding on these improved initial solutions, the introduction of **Vanilla Refinement** further boosts solution quality. On top of that, the addition of **Objective Guidance (OG)** steers the refinement process by prioritizing variables with both high model confidence and low surrogate cost—in a fully **gradient-free manner with negligible runtime overhead**.\nFor example: TSP-500 improves from 0.381 → 0.319 ; MIS-ER improves from 7.611 → 5.579  \n\n\nIn summary, this ablation study highlights the **modular and complementary design** of our method:  \n- **VA + CCS** collaboratively ensure structural reliability, enabling better solution space exploration and improved outcomes;\n- **OG** promotes objective alignment effectively and efficiently, resulting in better solutions.\n\nOwing to space limitations, this response primarily focuses on clarifying the contribution to performance improvements. For a **more comprehensive ablation analysis**, please refer to our response to Reviewer XM73, Q1. In addition, Fig. 2 in the main paper provides a detailed comparison with **gradient-based refinement** methods, demonstrating that our gradient-free refinement consistently outperforms them in both solution quality and computational efficiency.\n\n\n---\n\n> **Q3: Could StruDiCO be generalized well to more CO problems?**\n\nIn fact, StruDiCO can handle a wide range of constrained combinatorial optimization (CO) problems. Leveraging the expressive capacity of generative models, our approach learns to approximate the underlying constraint structure, producing heatmaps that are already close to feasible. We then apply lightweight heuristic post-processing (e.g., greedy decoding) to convert these outputs into strictly feasible solutions. This paradigm enables general applicability to arbitrary constraints and aligns with the inference strategies adopted in prior representative works such as Diffusco, T2T, and Fast T2T.\n\nTo further demonstrate the generality of StruDiCO beyond classical edge-selection (TSP) and node-selection (MIS) tasks, we extend it to the **Capacitated Vehicle Routing Problem (CVRP)**—a more challenging CO task that involves both global routing structures and hard feasibility constraints, such as customer demands and vehicle capacities. The **refinement procedure for CVRP follows the same design as that for TSP**: greedy decoding is performed based on the learned heatmap, with the objective guided by a distance-based penalty term. We evaluate StruDiCO on CVRP-50, CVRP-100, and CVRP-200 under standard benchmark settings \\[1]. To further improve both solution feasibility and cost, we incorporate a local search heuristic (Classic-LS \\[2]) during inference.\n\n**To the best of our knowledge, StruDiCO is the first heatmap-based model that surpasses sequence-based models on VRPs.**\n\n\n| Algorithm                            | Type       |  Length↓ | Drop↓     | CVRP 50 Time  |  Length↓ | Drop↓     | CVRP 100 Time  |  Length↓ |  Drop↓     | CVRP 200 Time  |\n| ------------------------------------ | ---------- | --------------- | --------- | ----- | ---------------- | --------- | ----- | ---------------- | --------- | ----- |\n| HGS \\[3]                                 | Heuristics | 10.37           | 0.00%     | 1s    | 15.56            | 0.00%     | 20s   | 19.63            | 0.00%     | 60s   |\n| Sym-NCO \\[1]                             | RL+LS      | 10.57           | 1.95%     | 0.09s | 15.93            | 2.37%     | 0.19s | 20.19            | 2.86%     | 0.36s |\n| StruDiCO (\\$T\\_s\\$=3,\\$T\\_g\\$=3) | SL+LS      | 10.48       | 1.12% | 0.05s | 15.85        | 1.88% | 0.11s | 20.25        | 3.19% | 0.26s |\n| **StruDiCO (\\$T\\_s\\$=5,\\$T\\_g\\$=5)** | SL+LS      | **10.45**       | **0.85%** | 0.07s | **15.80**        | **1.53%** | 0.17s | **20.16**        | **2.71%** | 0.38s |\n\n---\n\n> **W2: Gradient-free approach is not critical in tested examples: the tested tasks TSP and MIS do not present known issues with gradient use, so it’s unclear when this feature would be critical.**\n\nWe respectfully clarify that although TSP and MIS are inherently discrete and non-differentiable problems, recent diffusion-based solvers, such as **T2T and FastT2T**, still **rely on gradient-based refinement** over relaxed continuous representations to improve solution quality. In contrast, our method achieves superior performance without any gradient computation, demonstrating that a gradient-free refinement framework can be both effective and efficient. This not only avoids the complexity and overhead associated with backpropagation through relaxed spaces but also enhances the method’s applicability to a broader range of combinatorial problems where gradient-based refinement may be infeasible or suboptimal.\n\n---\n\n#### **References**\n#### \\[1] RL4CO: An Extensive Reinforcement Learning for Combinatorial Optimization Benchmark, 2024\n\n#### \\[2] A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem, 2004\n\n#### \\[3] A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems, 2012\n\n---\n\nWe hope our point-by-point clarificaitons and supplementary experiments have satisfactorily addressed your concerns. We remain fully committed to involving further discussions with you towards an elevated evaluation of our work.\n\nBest regards,\n\nThe Authors"}, {"review_id": "17ZEEnxKjd", "reviewer": "Reviewer_XM73", "summary": "This paper proposes a structured discrete diffusion framework, StruDiCO, tailored for combinatorial optimization (CO) problems. It employs Variable-Absorption as the forward noising strategy during training and Constrained Consistency Sampling for reverse inference during testing. Leveraging the structural consistency throughout the inference process, the authors further introduce a gradient-free refinement method to enhance solution quality. While the paper presents a novel and promising approach, the reviewer has some concerns regarding the completeness of the experimental analysis and the clarity of the objective-aware decoding mechanism.", "questions": "1. The proposed Variable-Absorption Diffusion and Constrained Consistency Sampling seem to be the core innovations. However, the experimental section lacks clear ablation studies isolating their contributions. This makes it difficult to assess which component contributes most to the performance gains.\n2. The decoding strategy is guided by a multiplicative score between model confidence and task-specific penalties. This formulation seems simplistic and may bias the search toward either confidence or task cost. The authors are encouraged to elaborate on how this trade-off is balanced.\n3. The reviewer is surprised that the gradient-free refinement achieves significant quality improvements in only 3–5 steps. Typically, gradient-free methods (e.g., 2-opt) require more iterations to converge. The authors should provide a more detailed explanation or empirical evidence to justify this rapid convergence.\n4. Gradient-free methods often scale poorly to large problem instances, which raises concerns from the reviewer about the applicability of StruDiCO in such settings. The authors are encouraged to compare against recent CO solvers. In particular, the reviewer notes that recent work has explored the use of diffusion solvers for tackling large-scale combinatorial optimization problems—such as ‘DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems’. Comparing StruDiCO with these approaches would further strengthen the contribution of this paper.\n5. Given the fast evolution of recent combinatorial optimization research, the reproducibility of results is crucial for future comparison and follow-up work. The reviewer recommends that the authors consider releasing their codebase to strengthen the impact and reproducibility of their contributions.", "limitations": "This paper provides an insightful approach to designing diffusion solvers for combinatorial optimization. It outperforms recent methods in terms of both solution quality and inference efficiency. However, the reviewer believes that additional ablation studies and clarifications regarding the decoding process would substantially improve the clarity and credibility of the work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "1. The paper proposes a structured diffusion solver with a novel variable-absorption mechanism. It further integrates a gradient-free local refinement strategy that improves performance over recent advances while offering a faster inference advantage.\n2. Compared to gradient-based methods, the proposed gradient-free refinement appears easier to implement and more applicable in practice. This increases the potential applicability of StruDiCO.\n3. The paper provides clear methodological details and supports the algorithmic design with theoretical analysis.", "was_revised": true, "final_justification": "The reviewer has carefully read the authors' response, including the questions and replies addressed to other reviewers. The authors have provided thorough answers to my concerns. In addition, the performance of StruDiCO on the CVRP task, beyond TSP and MIS, further supports the method's effectiveness. My concerns have been largely addressed, and I maintain my original positive score.", "rebuttal": "Dear Reviewer XM73,\n\nThanks for your insightful comments and for acknowledging model design and empirical performance. Below we respond to the specific comments.\n\n> **Q1: Clarifying the individual contributions of Variable-Absorption and Constrained Consistency Sampling via ablation.**\n\nWe provide a detailed ablation study to isolate the contribution of each component in our method. The analysis focuses on three parts:\n\n1. The role of **Variable-Absorption (VA)** mechanism, \n2. The effect of **Constrained Consistency Sampling (CCS)** in the main inference process, and  \n3. The contribution of the **Objective-Aware Refinement** module applied on the initial solution solved by StruDiCO with $T_s=5$.\n\nSpecifically, we compare several variants, including: \n- **Uniform CM**: the uniform cosistency model (CM) proposed in Fast T2T;\n- **VA CM**: replacing the uniform CM with the Variable-Absorption CM;  \n- **+CCS**: where low-confidence variables are masked;  \n- **Vanilla Refinement**: which refines the initial solution without gradient-free objective guidance (OG).\n\n#### Table: Ablation Study (Gap, % ↓)\n\n| Variant                      | TSP-50 | TSP-100 | TSP-500 | TSP-1000 | MIS-RB | MIS-ER |\n|-----------------------------|--------|---------|---------|----------|--------|--------|\n| Uniform CM (Fast T2T,  \\$T\\_s\\$=5)       | 0.031     | 0.101     | 0.922     | 1.167     | 6.023     | 15.898     |\n| VA CM (StruDiCO)               | 0.032  | 0.163   | 1.091   | 1.183    | 7.476  | 23.461 |\n|Uniform +CCS |     0.025 | 0.081   | 0.898   | 1.074  | 5.878  | 16.522 |\n| VA + CCS (StruDiCO, \\$T\\_s\\$=5)      | 0.019  | 0.067   | 0.728   | 0.797    | 3.899  | 11.450 |\n| Vanilla Refinement          | 0.012  | 0.033   | 0.381   | 0.672    | 1.922  | 7.611  |\n| + OG (StruDiCO, \\$T\\_s\\$=5, \\$T\\_g\\$=5)    | **0.011** | **0.025** | **0.319** | **0.473**  | **1.707** | **5.579** |\n\nAs shown, replacing the uniform noise (used in DIFUSCO, T2T, and FastT2T) with the Variable-Absorption (VA) mechanism alone leads to a performance degradation. This is because VA introduces a monotonic absorption process, where variables are only deactivated (i.e., 1 → 0) during the forward diffusion. While this preserves structural continuity at each timestep, it results in overly conservative trajectories when used alone—**limiting exploration and diversity in the reverse process**. In contrast, the Uniform Consistency Model (CM) allows symmetric noise injection (both 0 ↔ 1), which encourages broader exploration and increases the chance of reaching high-quality solutions.\n\nThe key point we emphasize is that **VA was not designed to be effective in isolation**. Rather, its role is to create structurally consistent and interpretable intermediate states, serving as a reliable foundation for the reverse process when combined with CCS. Once CCS is applied, which **selectively activates only high-confidence variables at each step**, the VA framework’s structure-preserving property becomes crucial: **it ensures that CCS operates over a low-noise, semantically meaningful space**. Notably, while CCS also improves performance when applied to the Uniform CM baseline, the gain is significantly amplified when combined with VA. This confirms that these two components are complementary and jointly responsible for the observed performance gains.\n\nBuilding on these improved initial solutions, the introduction of **Vanilla Refinement** further boosts solution quality. On top of that, the addition of **Objective Guidance (OG)** steers the refinement process by prioritizing variables with both high model confidence and **low surrogate cost**, in a fully **gradient-free manner with negligible runtime overhead**. \n\nIn summary, this ablation study highlights the **modular and complementary design** of our method:  \n- **VA + CCS** collaboratively ensure structural reliability, enabling better solution space exploration and improved outcomes;\n- **OG** promotes objective alignment effectively and efficiently, resulting in better solutions.\n\nWe will include this extended analysis and clarification in the final version to better support the empirical strength of our approach.\n\n---\n\n> **Q2: The decoding strategy is guided by a multiplicative score between model confidence and task-specific penalties. This formulation seems simplistic and may bias the search toward either confidence or task cost.**\n\nThank you for your constructive comment. To better explore the trade-off between model confidence and task-specific penalties, we extended our original formulation. Specifically, we tested a generalized decoding score defined as: $confidence / (\\epsilon + penalty)$, \nwhere `ε` serves as a balancing term. Notably, our original multiplicative form can be viewed as a special case: `ε = 0` for TSP and `ε = 1` for MIS.\n\nIn our new experiments, we found that the TSP task is insensitive to ε due to its relatively smooth objective landscape. However, for MIS, tuning ε led to noticeable improvements. As shown in the table below, setting ε = 10⁻² for RB graphs and ε = 10⁻³ for ER graphs yielded better results than the original ε = 1 setting.\n\n#### Table: Effect of ε on MIS Gap (% ↓)\n\n| ε         | 1e-8  | 1e-5  | 1e-4  | 1e-3  | **1e-2** | 0.1  | **1**   | 10     |\n|-----------|-------|-------|-------|-------|----------|-------|--------|--------|\n| MIS-RB    | 1.673 | 1.644 | 1.650 | 1.636 | **1.596** | 1.692 | 1.707  | 1.709  |\n| MIS-ER    | 5.363 | 5.492 | 5.246 | **4.970** | 5.231  | 5.413 | 5.413  | 5.468  |\n\nThese results suggest that our decoding formulation is not inherently biased, but rather flexible and tunable to different CO tasks. We will include these findings and the general formulation in the final version.\n\n---\n\n> **Q3: Explaining the fast convergence of gradient-free refinement.**\n\nThank you for the insightful question. Unlike classical local search methods such as 2-opt, which typically apply a **single** local perturbation per step and require thousands of iterations to converge, our refinement mechanism performs a **batch update**: at each step, it simultaneously perturbs all low-confidence variables using variable-absorption noising, followed by selection based on objective-aware decoding. This parallel refinement strategy significantly accelerates convergence.\n\nTo support this, we present the following results on TSP-500, showing the trade-off between performance and computation time over different refinement steps:\n\n#### Table: Refinement Step Efficiency (TSP-500)\n\n| Steps     | 0     | 1     | 2     | 3     | 4     | 5     | 6     | 7     | 8     |\n|-----------|-------|-------|-------|-------|-------|-------|-------|-------|-------|\n| Gap (%)   | 0.732 | 0.534 | 0.448 | 0.377 | 0.322 | 0.315 | 0.292 | 0.248 | 0.238 |\n| Time (s)  | 0.255 | 0.339 | 0.415 | 0.491 | 0.569 | 0.640 | 0.724 | 0.823 | 0.902 |\n\nAs shown, the refinement process leads to steady improvements over steps. Notably, the most significant quality gains are achieved within the first 3–5 steps, making this range a good trade-off point between performance and efficiency. Although further steps continue to improve the solution, the **marginal gain diminishes**, while the **computational cost increases linearly**.\n\n---\n\n> **Q4: Scalability of StruDiCO and comparison with large-scale CO solvers (e.g., DISCO).**\n\nTo evaluate the scalability of our method, we conducted additional experiments on the large-scale **TSP-10,000** dataset. We compare StruDiCO with diffusion-based baselines, including **DIFUSCO** and **DISCO**, and a divide-and-conquer (DC) approach, **GLOP** [1].\n\n#### Table: Results on TSP-10000\n\n| Method                 | Type         | Length ↓ | Drop ↓ | Time   |\n|------------------------|--------------|----------|--------|--------|\n| LKH   | Heuristics   | 71.77    | 0.00%  | 332s   |\n| GLOP (more revisions)  | DC           | 75.29    | 4.90%  | 15s    |\n| DIFUSCO ($T_s$=100)    | SL+G+2OPT    | 73.91    | 2.98%  | 124s   |\n| DISCO                  | SL+G+2OPT    | 73.84    | 2.88%  | 92s    |\n| **StruDiCO ($T_s$=5)** | SL+G+2OPT    | **72.90**| **1.57%** | **60s** |\n\nIt is important to note that as the problem size increases (e.g., 100K nodes), the primary bottleneck during inference is not the diffusion (or consistency) model itself. Rather, **the major computational overhead arises from the greedy decoding procedure**, where edges or nodes with the highest confidence are sequentially inserted into a partial solution until a feasible one is constructed. This step can become prohibitively time-consuming in large-scale instances. We believe that the scalability of StruDiCO could be further improved by combining its backbone generative model with a more efficient decoding strategy or a divide-and-conquer approach. This presents a promising direction for future research.\n\nWe will include these large-scale results and comparisons with DISCO in the final version to strengthen the contribution.\n\n---\n\n> **Q5: Code release.**\n\nWe appreciate your suggestion. We are committed to releasing our full codebase and pretrained models upon publication. The objective of this work is to provide reference and contributions for the ML4CO community. Open-sourcing the code is a fundamental obligation we undertake.\n\n---\n\n>**Supplementary Experiments on a New Problem: Capacitated Vehicle Routing Problem**\n\nAt the end of this rebuttal, we present an additional experiment on the CVRP, which we believe would provide additional strong empirical support for our methodology. **Due to space limitations, please refer to our response to Reviewer RWGz, Q3, for the results.**\n\n---\n#### **References**\n\n#### \\[1] GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time, AAAI, 2024.\n---\nWe hope this response could help address your concerns, and we are more than happy to address any further concerns you may have.\n\nBest regards,\n\nThe Authors"}, {"review_id": "X9oezqj95j", "reviewer": "Reviewer_2ZPS", "summary": "This work focuses on designing diffusion-based solvers for combinatorial optimization (CO) problems. Compared to recent diffusion solvers, its main innovation lies in a novel structure-erasing noising strategy: instead of adding discrete noise directly to label data during the forward process, the model randomly masks a subset of edges in the solution graph. During the reverse denoising process, the model starts from an empty graph and progressively predicts which edges should be recovered to reconstruct a complete solution.\n\nBuilding on this structured modeling approach, the authors further introduce a gradient-free post-optimization strategy, which repeatedly masks parts of the current solution and refines it through a guided search process using a custom-designed scoring function (confidence divided by task objective). The authors claim their method achieves state-of-the-art (SOTA) performance in both solution quality and inference speed.", "questions": "Some recent diffusion-based solvers have been overlooked in the comparison, such as DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems, which also explores improving both solution quality and inference speed for CO problems. A technical discussion of the differences from these works, along with public performance comparisons, would further strengthen the completeness and positioning of this work.", "limitations": "The reviewer finds the idea of a structured denoising process compelling and is generally supportive of the paper. Ablation studies should be included to clarify the contributions of key components. The current score may be raised depending on the authors’ responses in the rebuttal phase.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The reviewer appreciates the idea of structurally designing the diffusion process. While diffusion models have recently shown strong potential as general-purpose function approximators in CO, prior diffusion solvers typically add discrete noise directly to the initial solution, which leads to a lack of interpretability in both the noising and denoising stages, limiting the integration of search-based enhancements. The structured design proposed here alleviates this issue.\n2. The proposed solver outperforms recent neural CO solvers in both solution quality and inference speed, validating the effectiveness of the structured solver design tailored for combinatorial optimization.\n3. Compared to gradient-based search strategies, the gradient-free post-optimization approach introduced here is more convenient to implement and apply, highlighting StruDiCO's practical advantage in broader applications.\n\nWeaknesses:\n1. The reviewer is curious about the contribution of the two key diffusion design components, Variable-Absorption and Constrained Consistency Sampling, to the overall performance. Conducting a thorough ablation study would help clarify their individual effects.\n2. Whether the inference cost of StruDiCO increases significantly with problem size, such as TSP-10000. While this does not affect the rating, clarifying this point would be helpful.", "was_revised": true, "final_justification": "The reviewer appreciates the detailed and thoughtful response. All of my concerns have been addressed. In particular, I am impressed by StruDiCO’s strong performance on large-scale combinatorial optimization problems, which clearly demonstrates the method’s scalability. I believe this work establishes a new state-of-the-art in the CO domain. Based on these clarifications and results, I am updating my score from 4 to 5.", "rebuttal": "Dear Reviewer 2ZPS,\n\nThanks for your insightful comments and for acknowledging novelty, model design, and empirical performance. Below we respond to the specific comments.\n\n---\n\n> **Q1&W2: Some recent diffusion-based solvers have been overlooked in the comparison, such as DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems, which also explores improving both solution quality and inference speed for CO problems. A technical discussion of the differences from these works, along with public performance comparisons, would further strengthen the completeness and positioning of this work. Whether the inference cost of StruDiCO increases significantly with problem size, such as TSP-10000. While this does not affect the rating, clarifying this point would be helpful.**\n\nThanks for providing the related work. DISCO improves inference efficiency and solution quality on large-scale CO problems (e.g., TSP, MIS) via residue-constrained denoising and multi-modal graph search. We have now incorporated a discussion of DISCO in the related work section.\n\nWe have extended our model training to **TSP-10,000** and compared it with diffusion-based baselines, including **DIFUSCO** and **DISCO**, and a  divide-and-conquer (DC) approach, **GLOP** [1].\n\n\n| Method                         | Type         | Length ↓ | Drop ↓  | Time  |\n|--------------------------------|--------------|----------|---------|--------|\n| LKH           | Heuristics   | 71.77    | 0.00%   | 332s   |\n| GLOP (more revisions)          | DC           | 75.29    | 4.90%   | 15s    |\n| DIFUSCO ($T_s = 100$)             | SL+G+2OPT    | 73.91    | 2.98%   | 124s   |\n| DISCO                          | SL+G+2OPT    | 73.84    | 2.88%   | 92s    |\n| **StruDiCO ($T_s = 5$)**          | SL+G+2OPT    | **72.90**| **1.57%** | **60s** |\n\nIt is important to note that as the problem size increases (e.g., 100K nodes), the primary bottleneck during inference is not the diffusion (or consistency) model itself. Rather, **the major computational overhead arises from the greedy decoding procedure**, where edges or nodes with the highest confidence are sequentially inserted into a partial solution until a feasible one is constructed. This step can become prohibitively time-consuming in large-scale instances. We believe that the scalability of StruDiCO could be further improved by combining its backbone generative model with a more efficient decoding strategy or a  divide-and-conquer approach. This presents a promising direction for future research.\n\nWe will include these large-scale results and comparisons with DISCO in the final version to strengthen the contribution.\n\n---\n\n> **W1: The reviewer is curious about the contribution of the two key diffusion design components, Variable-Absorption and Constrained Consistency Sampling, to the overall performance. Conducting a thorough ablation study would help clarify their individual effects.**\n\nWe provide a detailed ablation study to isolate the contribution of each component in our method. The analysis focuses on three parts:\n\n1. The role of **Variable-Absorption (VA)** mechanism, \n2. The effect of **Constrained Consistency Sampling (CCS)** in the main inference process, and  \n3. The contribution of the **Objective-Aware Refinement** module applied on the initial solution solved by StruDiCO with $T_s=5$.\n\nSpecifically, we compare several variants, including: \n- **Uniform CM**: the uniform cosistency model (CM) proposed in Fast T2T;\n- **VA CM**: replacing the uniform CM with the Variable-Absorption CM;  \n- **+CCS**: where low-confidence variables are masked;  \n- **Vanilla Refinement**: which refines the initial solution without gradient-free objective guidance (OG).\n\n#### Table: Ablation Study (Gap, % ↓)\n\n| Variant                      | TSP-50 | TSP-100 | TSP-500 | TSP-1000 | MIS-RB | MIS-ER |\n|-----------------------------|--------|---------|---------|----------|--------|--------|\n| Uniform CM (Fast T2T, \\$T\\_s\\$=5)       | 0.031     | 0.101     | 0.922     | 1.167     | 6.023     | 15.898     |\n| VA CM (StruDiCO)               | 0.032  | 0.163   | 1.091   | 1.183    | 7.476  | 23.461 |\n|Uniform +CCS |     0.025 | 0.081   | 0.898   | 1.074  | 5.878  | 16.522 |\n| VA + CCS (StruDiCO, \\$T\\_s\\$=5)      | 0.019  | 0.067   | 0.728   | 0.797    | 3.899  | 11.450 |\n| Vanilla Refinement          | 0.012  | 0.033   | 0.381   | 0.672    | 1.922  | 7.611  |\n| + OG (StruDiCO, \\$T\\_s\\$=5, \\$T\\_g\\$=5)    | **0.011** | **0.025** | **0.319** | **0.473**  | **1.707** | **5.579** |\n\nAs shown, replacing the uniform noise (used in DIFUSCO, T2T, and FastT2T) with the Variable-Absorption (VA) mechanism alone leads to a performance degradation. This is because VA introduces a monotonic absorption process, where variables are only deactivated (i.e., 1 → 0) during the forward diffusion. While this preserves structural continuity at each timestep, it results in overly conservative trajectories when used alone—**limiting exploration and diversity in the reverse process**. In contrast, the Uniform Consistency Model (CM) allows symmetric noise injection (both 0 ↔ 1), which encourages broader exploration and increases the chance of reaching high-quality solutions.\n\nThe key point we emphasize is that **VA was not designed to be effective in isolation**. Rather, its role is to create structurally consistent and interpretable intermediate states, serving as a reliable foundation for the reverse process when combined with CCS. Once CCS is applied, which **selectively activates only high-confidence variables at each step**, the VA framework’s structure-preserving property becomes crucial: **it ensures that CCS operates over a low-noise, semantically meaningful space**. Notably, while CCS also improves performance when applied to the Uniform CM baseline, the gain is significantly amplified when combined with VA. This confirms that these two components are complementary and jointly responsible for the observed performance gains.\n\nBuilding on these improved initial solutions, the introduction of **Vanilla Refinement** further boosts solution quality. On top of that, the addition of **Objective Guidance (OG)** steers the refinement process by prioritizing variables with both high model confidence and **low surrogate cost**, in a fully **gradient-free manner with negligible runtime overhead**. \n\nIn summary, this ablation study highlights the **modular and complementary design** of our method:  \n- **VA + CCS** collaboratively ensure structural reliability, enabling better solution space exploration and improved outcomes;\n- **OG** promotes objective alignment effectively and efficiently, resulting in better solutions.\n\nWe will include this extended analysis and clarification in the final version to better support the empirical strength of our approach.\n\n---\n\n>**Supplementary Experiments on a New Problem: Capacitated Vehicle Routing Problem**\n\nAt the end of this rebuttal, we would like to present an additional experiment on the Capacitated Vehicle Routing Problem (CVRP), which we believe provides further strong empirical support for our methodology.  **Due to space limitations, detailed results are provided in our response to Reviewer RWGz, Q3.**\n\n**To the best of our knowledge, StruDiCO is the first heatmap-based model to surpass sequence-based methods on CVRP, highlighting the potential of structure-guided global prediction in solving combinatorial optimization problems with complex constraints.** \n\n\n---\n#### **References**\n\n#### \\[1] GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time, AAAI, 2024.\n\n---\n\nWe hope this response could help ease your concern and wish to receive your further feedback soon.\n\nBest regards,\n\nThe Authors"}]

Author rebuttal:

Meta-review: The paper proposes a structured denoising diffusion model for incrementally decoding solutions for combinatorial optimization problems, here MIS and TSP.
Reviewers note improvements upon Difusco, being faster, theoretically grounded sampling, improved performance, nice idea. On the other hand, marginal improvements are noted, lacking explanations, ablations, limited experiments.
Given the reviewer consensus, nice theoretical contribution and experimental results, the paper merits acceptance at NeurIPS.
Decision: Accept (poster)