Diffusion-based solvers have become a prominent approach to neural combinatorial optimization. At inference time, they assign each decision variable a prediction score. A greedy decoder ranks candidates by these scores and checks hard constraints to ensure feasibility. Top-ranked candidates should be both promising and jointly feasible, making prediction-constraint alignment critical. When this alignment is weak, greedy decoding skips constraint-violating candidates and falls back to lower-ranked alternatives, degrading solution quality. Existing test-time methods improve search, sampling, or decoding, but do not directly strengthen this alignment before decoding. We observe that trained denoisers already carry constraint-aligned structural signals. Building on this observation, we propose Perturbed Instance-Structure Guidance (PISG), a training-free method that amplifies these signals at test time. At each denoising step, PISG constructs a structure-degraded prediction and extrapolates the unperturbed prediction away from it. The resulting guided prediction improves candidate rankings before constrained decoding. Signal analysis shows that this guidance concentrates on constraint-critical variables rather than uniformly rescaling scores. Under greedy decoding and without downstream refinement, PISG improves all 16 TSP solver-scale pairs across DIFUSCO, T2T, FastT2T, and StruDiCO, and all four MIS-ER solvers, with MIS-ER solved-cost gains up to +4.8%. The gains persist on most large-scale settings after 2-opt, and a preliminary study extends PISG to a Transformer-based solver. These results identify prediction-constraint alignment as an effective test-time enhancement direction for diffusion-based combinatorial optimization. Code is available at https://github.com/Ming-321/PISG.
Figures & tables
Figure 1: Prediction quality governs decoder skips and final solution quality. (a) Schematic 10-node TSP (synthetic, not solver output). Top row : greedy tours are always feasible, but lower prediction quality leads to costlier tours ( 3.109<3.412<4.435 ). Bottom row : top- N selected edges. Normal already concentrates predictions on degree-compatible edges; weakening edge gating (Perturbed) visibly increases violations; Guided further reduces them to zero (no red nodes). (b) Quantitative evidence across four TSP scales and MIS: fewer decoder skips correspond to shorter tours and larger independent sets, confirming that prediction quality before decoding governs final solution quality. See Appendix D.1 .
Figure 2: Overview of PISG. (a) PISG is applied at every denoising step to form guided logits for the reverse transition. (b) At step t , PISG computes two parallel, parameter-sharing denoising branches: a normal branch with learned AGNN gates and a structure-degraded branch with weakened gates. Their logit discrepancy defines the PISG signal, and the guided logits extrapolate along this direction (Equation 2 ) for sampling xt−1 . (c) In selected AGNN layers, PISG replaces heterogeneous learned edge gates with spatially uniform weakened surrogates, removing edge-wise structural sensitivity.
Figure 3: Probability-space signal analysis ( δ~t ). (a) TSP: positive for top-2 edges, negative beyond (degree-2 split). (b) MIS: conflict-edge endpoint separation is 4.2× non-conflict at step 4.
TSP-50
TSP-100
TSP-500
TSP-1000
Method
Ts/Tg
Cost
Gap%
Time
Cost
Gap%
Time
Cost
Gap%
Time
Cost
Gap%
Time
Concorde
–
5.688
0.000
–
7.756
0.000
–
16.55
0.00
–
23.12
0.00
–
DIFUSCO
100/0
5.708
0.367
6.2m
7.864
1.388
6.7m
18.52
11.91
3.8m
26.19
13.31
9.6m
+PISG
100/0
5.699
0.203
6.2m
7.800
0.567
10.2m
18.11
9.44
5.8m
25.65
10.95
16.7m
T2T
50/0
5.727
0.683
3.5m
7.882
1.624
3.6m
18.42
11.33
76s
26.13
13.05
2.4m
+PISG
50/0
5.719
0.543
3.5m
7.815
0.758
5.0m
18.18
9.88
96s
26.09
12.87
3.6m
Table 1: TSP results across four solvers and four scales. Gap% = (cost − Concorde) / Concorde × 100. Bold : best gap within each solver block and scale.
ER
RB
Method
Ts/Tg
Cost ↑
Gap% ↓
Time
Cost ↑
Gap% ↓
Time
Reference
–
41.35
0.00
—
20.09
0.00
—
DIFUSCO
100/0
40.63
1.73
4.0m
—
—
—
+PISG
100/0
42.55
− 2.91
6.5m
—
—
—
T2T
50/0
36.50
11.74
1.5m
—
—
—
+PISG
50/0
38.25
7.50
2.3m
—
—
—
Table 2: MIS results on ER and RB. Cost is higher-better; gap% is lower-better and negative means exceeding the reference. Bold : best within each solver block.
Figure 4: Compute–quality trade-off on FastT2T. Solid: Ts scaling ( Tg=0 ); dashed: Tg scaling ( Ts=5 ). PISG shifts the frontier in later-budget regimes and adds 3–17% wall-clock overhead (Appendix B.5 ).
Appendix figures & tables36 assets
Supplementary material from the paper’s appendix.
Appendix
Gate-targeting
Non-gate
Task
Metric
Base
Unif.
Adpt.
Rand-g.
Inp-noise
TSP
gap ↓
0.086
0.057
0.056
0.046
0.077
MIS
cost ↑
37.81
39.30
33.48
38.58
37.81
Appendix
Table 3: Perturbation strategy comparison on TSP-100 and MIS-ER (FastT2T, Ts=5 , Tg=0 , greedy, seed 42). Strategies are grouped into gate-targeting (operating on the gate vector gij(ℓ) , Eq. ( 7 )) and non-gate (operating on the denoiser input, Eq. ( 8 )).
Task
2-opt
C=10
C=20
C=40
TSP-500
0
+ 0.00096 (3/5)
+ 0.00106 (5/5)
+ 0.00176 (5/5)
TSP-500
20
− 0.00003 (2/5)
+ 0.00049 (4/5)
− 0.00012 (2/5)
TSP-1000
0
+ 0.04718 (5/5)
+ 0.02012 (5/5)
+ 0.01427 (5/5)
TSP-1000
20
+ 0.00399 (5/5)
+ 0.00297 (4/5)
+ 0.00215 (4/5)
Appendix
Table 4: GenSCO TSP results with one frozen configuration (seeds 41–45). Entries are the mean paired gap reduction in percentage points ( >0 : PISG better) with paired wins out of 5. C : search cycles; 2-opt: GenSCO’s in-loop 2-opt steps.
Dataset
C=500
C=1000
C=2000
MIS-ER
+ 0.047 (4/5)
+ 0.080 (5/5)
− 0.036 (2/5)
MIS-RB
− 0.003 (2/5)
+ 0.004 (4/5)
− 0.005 (2/5)
Appendix
Table 5: GenSCO MIS results with one frozen configuration per distribution (seeds 41–45). Entries are the mean paired change in independent-set size ( >0 : PISG better) with paired wins out of 5. The baseline is evaluated at both the default and the PISG flip rate, and each row compares against the stronger one (default for ER, PISG flip rate for RB).
TSP-50
TSP-100
Method
Ts/Tg
Cost
Gap%
Time
Cost
Gap%
Time
Concorde
–
5.688
0.000
–
7.756
0.000
–
DIFUSCO
100/0
5.708
0.367 ± .044
6.2m
7.864
1.388 ± .067
6.7m
+PISG
100/0
5.699
0.203 ± .017
6.2m
7.800
0.567 ± .038
10.2m
T2T
50/0
5.727
0.683 ± .071
3.5m
7.882
1.624 ± .064
3.6m
+PISG
50/0
5.719
0.543 ± .034
3.5m
7.815
0.758 ± .039
5.0m
Appendix
Table 6: TSP small-scale results with standard deviations (gap%, 5-seed mean ± std). Extended version of Table 1 (TSP-50/100). Bold : best gap within each solver block and scale.
TSP-500
TSP-1000
Method
Ts/Tg
Cost
Gap%
Time
Cost
Gap%
Time
Concorde
–
16.55
0.00
–
23.12
0.00
–
DIFUSCO
100/0
18.52
11.91 ± .22
3.8m
26.19
13.31 ± .29
9.6m
+PISG
100/0
18.11
9.44 ± .38
5.8m
25.65
10.95 ± .10
16.7m
T2T
50/0
18.42
11.33 ± .42
76s
26.13
13.05 ± .12
2.4m
+PISG
50/0
18.18
9.88 ± .45
96s
26.09
12.87 ± .42
3.6m
Appendix
Table 7: TSP large-scale results with standard deviations (gap%, 5-seed mean ± std). Extended version of Table 1 (TSP-500/1000). Bold : best gap within each solver block and scale.
ER
RB
Method
Ts/Tg
Cost ± std ↑
Gap% ↓
Time
Cost ± std ↑
Gap% ↓
Time
Reference
–
41.35
0.00
—
20.09
0.00
—
DIFUSCO
100/0
40.63 ± .19
1.73
4.0m
—
—
—
+PISG
100/0
42.55 ± .09
− 2.91 ∗
6.5m
—
—
—
T2T
50/0
36.50 ± .16
11.74
1.5m
—
—
—
+PISG
50/0
38.25 ± .16
7.50 ∗
2.3m
—
—
—
Appendix
Table 8: MIS results with standard deviations (cost ↑ , 5-seed mean ± std). Extended version of Table 2 . Bold : best result within each solver block. ∗ Significant at α=0.05 (Table 9 ).
Solver
Task
Win
p
Δ (mean ± std)
DIFUSCO
TSP-50
5/5
0.031
0.1642 ± 0.0477
DIFUSCO
TSP-100
5/5
0.031
0.8211 ± 0.0696
DIFUSCO
TSP-500
5/5
0.031
2.4651 ± 0.2394
DIFUSCO
TSP-1000
5/5
0.031
2.3601 ± 0.2495
T2T
TSP-50
5/5
0.031
0.1397 ± 0.0886
T2T
TSP-100
5/5
0.031
0.8668 ± 0.0880
Appendix
Table 9: Statistical significance of PISG improvements. Win : seeds (out of 5) where PISG improves. p : one-sided Wilcoxon signed-rank. Δ : mean improvement ( >0 = PISG better; TSP: baseline gap% minus PISG gap%; MIS: PISG cost minus baseline cost). Bold p -values: significant at α=0.05 .
Solver
Task
Win ( n=20 )
p ( n=20 )
p ( n=5 )
Δ (mean ± std)
T2T
TSP-1000
17/20
0.0032
0.219
0.2648 ± 0.4110
StruDiCO
TSP-50
13/20
0.0615
0.219
0.0030 ± 0.0072
StruDiCO
TSP-100
17/20
0.0008
0.312
0.0248 ± 0.0310
StruDiCO
TSP-500
14/20
0.0120
0.406
0.1417 ± 0.2539
StruDiCO
MIS-ER
16/20
0.0047
0.156
0.1680 ± 0.2265
StruDiCO
MIS-RB
9/20
0.5298
0.406
− 0.0005 ± 0.0288
Appendix
Table 10: Follow-up test of the six cells that were not significant with five seeds (controlled isolation, seeds 41–60, one-sided Wilcoxon signed-rank). Δ as in Table 9 , computed over 20 seeds. Bold: p<0.05 .
Solver
Task
Baseline
PISG
Δ
Win
FastT2T
TSP-500
0.429
0.403
+ 0.026
4/5
FastT2T
TSP-1000
0.627
0.599
+ 0.028
4/5
StruDiCO
TSP-500
0.323
0.314
+ 0.009
4/5
StruDiCO
TSP-1000
0.518
0.595
− 0.076
0/5
Appendix
Table 11: Full deployment pipeline ( Ts=5 , Tg=5 , 2-opt to convergence; seeds 41–45). Gap% after the final rewrite and 2-opt. Δ : baseline gap minus PISG gap ( >0 : PISG better).
2-opt cap
Baseline
PISG
Δ
Win
0
8.60
6.72
+ 1.88
–
10
2.048
1.678
+ 0.370
5/5
20
0.864
0.783
+ 0.081
4/5
1,000 (converged)
0.518
0.595
− 0.076
0/5
Appendix
Table 12: StruDiCO TSP-1000 after rewrite under increasing 2-opt budgets (seeds 41–45). The cap-0 row is the StruDiCO TSP-1000 Tg=5 row of Table 1 ; the cap-1,000 row is the endpoint in Table 11 .
FastT2T
StruDiCO
Time (s)
Mem (GB)
Time (s)
Mem (GB)
Task
Base
+PISG
Base
+PISG
Base
+PISG
Base
+PISG
TSP-50
45
48
0.71
0.71
45
48
0.71
0.71
TSP-100
52
55
0.73
0.79
46
53
0.73
0.79
TSP-500
32
33
0.92
1.32
33
37
0.93
1.32
TSP-1000
48
56
1.57
3.10
46
58
1.57
3.10
Appendix
Table 13: PISG overhead (FastT2T and StruDiCO, Ts=5 , Tg=0 , batched, 4 × A100-40GB). Batch size follows each solver’s default; DIFUSCO/T2T overheads are proportional and can be read from Tables 1 – 2 time columns.
Task
PISG@5
Time
Closest base ( Ts )
Base@10
Outcome
TSP-50
0.0171%
52 s
Ts=5 : 0.0225%, 52 s
0.0152%, 71 s
Beats closest-time; base@10 better
TSP-100
0.051%
54 s
Ts=6 : 0.055%, 56 s
0.042%, 72 s
Beats closest-time; base@10 better
TSP-500
5.15%
35 s
Ts=8 : 5.48%, 34 s
5.74%, 38 s
Beats both
TSP-1000
5.93%
58 s
Ts=8 : 6.07%, 57 s
6.15%, 63 s
Beats both
MIS-ER
38.89
37 s
Ts=9 : 39.73, 37 s
39.79, 37 s
Both baselines better
MIS-RB
18.89
49 s
Ts=6 : 18.92, 53 s
19.16, 68 s
Both baselines better
Appendix
Table 14: Compute-matched comparison (FastT2T, Tg=0 , 5-seed mean). Closest-time: baseline Ts whose wall-clock ≈ PISG@ Ts=5 . Runtimes come from the dense Ts sweeps (independent measurements); absolute times can differ from Table 13 , so comparisons are made within each sweep. TSP: gap% ( ↓ ); MIS: solved cost ( ↑ ).
Figure 5: TSP-100 sensitivity heatmap (FastT2T, seed 42). The main text (Section 6.1 ) summarizes this sweep. 82% of 180 gate-level configurations improve over the baseline; 100% succeed in the safe zone (dashed box: scale ∈[1,3] , layers ∈[5,9] ).
Subtask
Baseline
Best PISG
Rel. imp.
Best config
TSP-50
0.0196 gap%
0.0143
−27.3%
adap / s1.0 / L5 / linear
TSP-100
0.0860 gap%
0.0414
−51.9%
rand / s3.0 / L7 / linear
TSP-500
5.6087 gap%
4.8040
−14.3%
uni / s3.0 / L7 / const
TSP-1000
6.3131 gap%
5.4532
−13.6%
adap / s1.0 / L7 / linear
MIS-ER
37.8125
39.2969
+3.9%
uni / s2.0 / L7 / const
MIS-RB
18.7740
19.1120
+1.8%
adap / s2.0 / L9 / const
Appendix
Table 15: Best FastT2T sweep configuration for each subtask. These are sweep optima, not necessarily the unified defaults used in the main tables (adap = adaptive, rand = random-gate, uni = uniform, const = constant).
Task
Config
Gap% or Cost
Time (s)
TSP-100
Baseline
0.081±.016 gap%
43
TSP-100
Paper default
0.051±.007 gap%
46
MIS-ER
Baseline
37.49±0.30 cost
28
MIS-ER
Paper default (= val optimum)
38.56±0.19 cost
32
TSP-50
Baseline
0.023±.005 gap%
44
TSP-50
Paper default (transfer)
0.017±.001 gap%
46
Appendix
Table 16: Held-out validation (5-seed mean ± std on the test split). On MIS-ER the paper default coincides with the validation optimum. TSP-50/500/1000 rows apply the TSP default without re-tuning.
DIFUSCO
T2T
Baseline
1.393
1.559
Default
0.561
0.812
Layer → 5
1.698
1.665
Layer → 9
0.845
1.437
Scale ↓
0.698
0.978
Scale ↑
0.472
0.741
Appendix
Table 17: TSP-100 cross-solver transfer (gap%, ↓ , seed 42). The shared default from FastT2T (adaptive/ s=2.0 /L7/linear) is applied to DIFUSCO and T2T. Each row varies one axis; bold indicates improvement over baseline. Scale variants: ↓=1.0 , ↑=3.0 .
DIFUSCO
T2T
Baseline
40.38
36.76
Default
42.59
38.20
Layer → 5
41.56
38.80
Layer → 9
39.78
39.98
Scale ↓
42.00
38.24
Scale ↑
42.86
38.47
Appendix
Table 18: MIS-ER cross-solver transfer (cost, ↑ , seed 42). The shared default from FastT2T (uniform/ s=2.0 /L7/constant) is applied to DIFUSCO and T2T. Each row varies one axis; bold indicates improvement over baseline. Scale variants: ↓=1.0 , ↑=3.0 .
Scale
TSP-100 gap% (↓)
MIS-ER cost (↑)
MIS-RB cost (↑)
Baseline
0.172
39.85
19.30
s=0.5
0.178
39.20
19.30
s=1.0
0.248
38.73
19.14
s=2.0
0.518
34.90
18.78
s=3.0
2.448
33.35
18.68
Appendix
Table 19: StruDiCO coarse transfer check (Stage 1, 3-seed mean on validation splits). Family default scale ( s=2.0 ) degrades all three tasks. Arrows indicate metric direction ( ↓ gap%, ↑ cost).
Table 20: StruDiCO frozen configurations from held-out calibration. “Transferred default” shows the family default axis value; boldface marks axes where calibration selected a different value.
p
Baseline
PISG
Relative gain (95% CI)
Win
0.100
50.85
52.17
+ 2.67% [0.98, 4.38]
5/5
0.125
44.84
46.50
+ 3.93% [2.99, 4.88]
5/5
0.150
37.59
38.64
+ 3.08% [1.90, 4.33]
5/5
0.175
31.47
32.03
+ 2.13% [0.86, 3.38]
5/5
0.200
25.35
24.69
− 2.28% [ − 3.49, − 0.99]
0/5
Appendix
Table 21: Density transfer on MIS-ER (FastT2T trained at p=0.15 , n=750 , frozen uniform / s=2.0 ). Relative gain =100×(PISG−baseline)/baseline .
Train \ Test
50
100
500
1000
50
+ 0.01 (5/5)
+ 0.43 (5/5) †
− 7.18 (0/5) †
− 7.45 (0/5) †
100
+ 0.01 (5/5)
+ 0.03 (5/5)
− 6.76 (0/5) †
− 2.78 (0/5) †
500
+ 0.89 (5/5)
+ 1.38 (5/5)
+ 0.69 (5/5)
+ 0.94 (5/5) †
1000
+ 0.71 (5/5)
+ 0.62 (5/5)
− 0.87 (0/5)
+ 0.53 (5/5)
Appendix
Table 22: Scale transfer on FastT2T with a frozen TSP-100-selected configuration. Entries are mean gap reductions in percentage points ( >0 : PISG better) with paired wins. † : test scale larger than training scale.
Band
Solver
Baseline
PISG
Δ
Win
50–200
DIFUSCO
4.51
4.05
+ 0.46
4/5
50–200
T2T
4.66
5.12
− 0.46
2/5
50–200
FastT2T
1.73
1.68
+ 0.05
4/5
200–1,000
DIFUSCO
19.77
19.91
− 0.14
3/5
200–1,000
T2T
38.77
40.62
− 1.85
1/5
200–1,000
FastT2T
30.87
32.11
− 1.24
2/5
Appendix
Table 23: TSPLIB transfer with frozen TSP defaults (controlled isolation, seeds 41–45). Gap% and mean gap reduction Δ in percentage points ( >0 : PISG better).
Scale
Branch
gap (%)
total skips
TSP-50
Perturbed
1.586
32.4
Normal
0.127
4.6
Guided
0.040
0.08
TSP-100
Perturbed
5.711
788.4
Normal
0.339
43.3
Guided
0.239
30.9
Appendix
Table 24: TSP raw-output metrics underlying Figure 1 (b) (128 instances per scale, single seed).
Table 26: sc@2 summary across denoising steps (TSP-100, 5 seeds, 6400 instance-seed pairs). Ratio = sc@2 / shuffled baseline. All permutation p<0.01 and Wilcoxon p<10−95 .
Step
δrank0>0
δrank1>0
δrank2<0
δrest<0
sc@2
0
91.8%
90.5%
85.5%
78.9%
76.4%
1
91.8%
90.5%
85.5%
78.9%
76.4%
2
92.0%
92.0%
86.8%
81.2%
78.2%
3
59.0%
72.9%
86.5%
86.5%
42.5%
4
9.8%
11.2%
85.1%
92.1%
2.1%
Appendix
Table 27: Three-condition decomposition of sc@2 (TSP-100). Each column shows the fraction of nodes satisfying that individual condition. sc@2 is the fraction satisfying all three conditions jointly.
Step
Pref. ratio
95% CI
∣δopt∣>∣δnonopt∣ frac.
opt. positive frac.
0
0.884
[0.873, 0.893]
99.97%
89.8%
1
0.883
[0.874, 0.892]
99.95%
89.8%
2
0.862
[0.851, 0.873]
99.92%
90.2%
3
0.501
[0.482, 0.521]
99.50%
63.1%
4
0.524
[0.506, 0.542]
94.12%
8.8%
Appendix
Table 28: Direction alignment on matched-subset TSP-100 trajectories (5 seeds, 6400 instance-seed pairs). Preference ratio is δopt/(∣δopt∣+∣δnonopt∣) averaged across instances.
Step
θ
nconflict
CMA conflict
CMA non-conf
CMA shuffled
Ratio
0
0.3
1823
0.056
0.037
0.037
1.5×
1
0.3
1883
0.056
0.038
0.037
1.5×
2
0.3
1934
0.086
0.029
0.029
2.9×
3
0.3
50639
0.189
0.070
0.070
2.7×
3
0.5
7382
0.200
0.072
0.072
2.8×
3
0.7
548
0.249
0.076
0.076
3.3×
Appendix
Table 29: CMA across denoising steps and thresholds (MIS-ER, 5 seeds, 640 instance-seed pairs). CMA = mean ∣δi−δj∣ . Ratio = conflict / non-conflict. Rows for θ=0.5 and 0.7 at steps 0–2 are omitted because conflict edges occur in at most 10 of the 640 instance-seed pairs.
Step
θ
Perm. p
Wilcoxon p
Ratio 95% CI
0
0.3
0.044
4.9×10−18
[1.39, 1.59]
1
0.3
0.043
1.1×10−19
[1.40, 1.60]
2
0.3
<0.003
6.8×10−55
[2.76, 3.13]
3
0.3
<0.002
8.9×10−107
[2.64, 2.80]
3
0.5
<0.002
4.8×10−95
[2.67, 2.87]
3
0.7
<0.005
1.4×10−31
[3.01, 3.55]
Appendix
Table 30: Hypothesis tests for CMA ratio (MIS-ER, 5-seed aggregate). Permutation: 100 shuffles of δ across nodes; Wilcoxon: one-sided paired test on per-instance CMA conflict vs. CMA non-conf ; Bootstrap: 1000 resamples of the ratio.
Step
t
sc@2
Shuffled
Ratio
sc@2 95% CI
1
691
0.568
0.044
12.9×
[0.559, 0.578]
2
413
0.277
0.045
6.2×
[0.269, 0.285]
3
191
0.021
0.024
0.9×
[0.019, 0.023]
4
49
0.003
0.016
0.2×
[0.002, 0.003]
Appendix
Table 31: StruDiCO sc@2 across denoising steps (TSP-100, 1280 instances, seed 42). Step indices start from 1 due to solver-specific trajectory conventions. Bootstrap 95% CI over instances.
Step
nconflict
CMA conf
CMA non-conf
Ratio
Perm. p
95% CI
0
11
0.061
0.021
2.9×
0.09
[2.01, 4.05]
1
8
0.078
0.024
3.3×
0.12
[2.04, 4.72]
2
28
0.103
0.029
3.6×
<0.036
[2.60, 4.63]
3
70
0.161
0.031
5.2×
<0.014
[4.62, 5.74]
4
105
0.140
0.022
6.5×
<0.010
[5.79, 7.40]
Appendix
Table 32: StruDiCO CMA ratio across denoising steps (MIS-ER, θ=0.3 , 128 instances, seed 42). Bootstrap 95% CI over instances.
Task
Baseline
Early
Late
All steps
TSP-100 gap ↓
0.0860
0.0640
0.0643
0.0560
MIS-ER cost ↑
37.81
39.17
38.80
39.30
Appendix
Table 33: Stage-wise activation ablation under the schedule-ablation protocol (FastT2T, seed 42). Lower is better for TSP gap; higher is better for MIS solved cost.
Gap% ( ↓ )
Degree violation ( ↓ )
Step
Guided
Normal
Δ (G − N)
Guided
Normal
Win%
0
2.023
2.023
0.000
0.0378
0.0378
—
1
2.170
1.982
+ 0.188
0.0514
0.0378
24%
2
1.994
1.731
+ 0.263
0.0808
0.0307
22%
3
0.696
0.448
+ 0.249
0.1551
0.0083
9%
4
0.176
0.206
− 0.030
0.0476
0.0017
3%
Appendix
Table 34: TSP-100 stepwise decode: solution quality (gap%, ↓ ) and structural feasibility (degree violation, ↓ ) at each step. Win%: percentage of instances where guided gap is lower than normal gap. Steps 1–3: guided is worse in both metrics; only at step 4 does guided narrowly improve.
IS size ( ↑ )
Conflict ( ↓ )
Skip ratio ( ↓ )
Step
Guided
Normal
Δ
Guided
Normal
Guided
Normal
Win%
0
24.03
1.78
+ 22.25
0.0197
0.0048
0.286
0.001
98%
1
23.99
1.88
+ 22.11
0.0182
0.0047
0.262
0.001
98%
2
19.95
4.71
+ 15.24
0.0049
0.0032
0.088
0.000
92%
3
36.54
31.99
+ 4.55
0.0349
0.0028
0.691
0.156
67%
4
38.35
37.80
+ 0.55
0.0165
0.0017
0.514
0.167
40%
Appendix
Table 35: MIS-ER stepwise decode: independent set size ( ↑ ), conflict rate ( ↓ ), and greedy skip ratio ( ↓ ) at each step. Win%: percentage of instances where guided IS size exceeds normal IS size. Guided achieves larger sets but with substantially worse feasibility.
Diagnostic
Raw ρ
Partial ρ (controlling baseline)
95% CI of partial ρ
TSP sc@2, steps 0–2 ( n=1,280 )
0.44–0.45
0.03–0.05
includes 0
MIS CMA, steps 3–4 ( n=127 )
0.34–0.39
0.33–0.36
excludes 0
Appendix
Table 36: Association between diagnostics and final PISG quality (FastT2T, seeds 41–45). Partial correlations control for the baseline’s final quality on the same instance.
Step
Normal R
Guided R
Shuffled R
ΔRt (95% CI)
1
0.5670
0.5345
0.5623
+ 0.033 [ − 0.007, 0.075]
2
0.4169
0.4406
0.4116
− 0.024 [ − 0.060, 0.015]
3
0.0973
0.1259
0.1022
− 0.029 [ − 0.046, − 0.012]
4
0.0325
0.0311
0.0335
+ 0.001 [ − 0.007, 0.011]
Appendix
Table 37: Fragment-closing rejections per instance during greedy decoding (FastT2T TSP-100, seeds 41–45). ΔRt>0 would indicate that guidance reduces premature cycle closure.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
Diffusion-based neural solvers have shown strong promise for combinatorial optimization (CO), but existing methods typically rely on supervised training with large collections of near-optimal solutions. In this work, we extend adjoint-based trajectory optimization methods to discrete combinatorial domains. We formulate diffusion-based CO as a stochastic control problem over Continuous-Time Markov Chains and introduce discrete adjoint dynamics for propagating optimization signals through discrete generative trajectories. Building on this formulation, we propose Combinatorial Adjoint Matching (CAM), an unsupervised training framework for discrete diffusion solvers with structured and low-variance trajectory-level optimization signals. Empirically, CAM consistently outperforms existing unsupervised diffusion baselines and achieves performance competitive with strong supervised diffusion solvers and even traditional solvers across diverse combinatorial optimization problems. Our code is available at https://github.com/Shengyu-Feng/CAM.
Shengyu Feng, Tarun Suresh, Yiming Yang
Language Technologies Institute, Carnegie Mellon University · University of Illinois Urbana-Champaign
Neural combinatorial optimization has recently achieved strong results on the Euclidean Traveling Salesman Problem (TSP) using generative models such as diffusion and consistency models. State-ofthe-art approaches like FT2T combine fast consistency-based prediction with gradient-based inference time refinement. However, gradient search often incurs significant computational overhead and may not align with the discrete structure of feasible solutions. We introduce Projected Consistency Inference (PCI), a plug-and-play, retraining-free alternative that replaces gradient refinement with structure-aware projections: PCI decodes valid Hamiltonian tours from the consistency model output and applies a lightweight local search (e.g., 2-opt). PCI achieves an average optimality gap (OG) of 0.17% on TSP with 500 cities, and 0.31% on TSP with 1000 cities, outperforming FT2T best settings (OG 0.22% and 0.36%, respectively) while reducing the inference time up to 30 to 40%. PCI also exhibits lower variance and memory usage, and can surpass classical heuristics such as LKH3 in rapid solution generation. Our results demonstrate that structure-aware inference time operations provide a practical and principled path for neural TSP solvers, complementing training time objectives.
Mickaël Basson, Philippe Preux
CRIStAL, Scool · Université de Lille, France · CNRS, France +2
Discrete diffusion models have emerged as a powerful paradigm for solving combinatorial optimization (CO) problems on graphs by learning to sample high-quality solutions. A common inference-time approach is to generate multiple candidate solutions independently and return the best-performing sample, improving solution quality at the expense of an increase in computational cost. In this work, we introduce PT-Denoise, an inference-time procedure that allows these concurrent denoising trajectories to interact through parallel tempering, without requiring retraining or fine-tuning of the underlying denoiser. Our method assigns a temperature to each diffusion process and allows processes to swap temperatures based on their relative performance. This dynamically reallocates promising, low-energy trajectories to colder, more concentrated sampling regimes while allowing higher-energy states to escape local minima through randomized exploration. Experiments on canonical graph-structured CO problems show that our approach consistently improves the quality of the best solution found, while only adding minimal computational overhead.
Arman Mielke, Uwe Bauknecht, Thilo Strauss +1
ETAS Research · University of Stuttgart · Max Planck Research School for Intelligent Systems (IMPRS-IS) +2