PISG: Constraint-Aligned Signal Amplification for Diffusion-Based Combinatorial Optimization
Organizations: College of Science, National University of Defense Technology, Changsha, China
Abstract
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
| TSP-50 | TSP-100 | TSP-500 | TSP-1000 | ||||||||||
| Method | 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 |
| ER | RB | ||||||
| Method | 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 | — | — | — |
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 |
| Task | 2-opt | |||
|---|---|---|---|---|
| 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) |
| Dataset | |||
|---|---|---|---|
| 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) |
| TSP-50 | TSP-100 | ||||||
| Method | 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 |
| TSP-500 | TSP-1000 | ||||||
| Method | 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 |
| ER | RB | ||||||
| Method | 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 | — | — | — |
| Solver | Task | Win | (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 |
| Solver | Task | Win ( ) | ( ) | ( ) | (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 |
| 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 |
| 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 |
| 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 |
| Task | PISG@5 | Time | Closest base ( ) | Base@10 | Outcome |
| TSP-50 | 0.0171% | 52 s | : 0.0225%, 52 s | 0.0152%, 71 s | Beats closest-time; base@10 better |
| TSP-100 | 0.051% | 54 s | : 0.055%, 56 s | 0.042%, 72 s | Beats closest-time; base@10 better |
| TSP-500 | 5.15% | 35 s | : 5.48%, 34 s | 5.74%, 38 s | Beats both |
| TSP-1000 | 5.93% | 58 s | : 6.07%, 57 s | 6.15%, 63 s | Beats both |
| MIS-ER | 38.89 | 37 s | : 39.73, 37 s | 39.79, 37 s | Both baselines better |
| MIS-RB | 18.89 | 49 s | : 18.92, 53 s | 19.16, 68 s | Both baselines better |
| Subtask | Baseline | Best PISG | Rel. imp. | Best config |
|---|---|---|---|---|
| TSP-50 | 0.0196 gap% | 0.0143 | adap / s1.0 / L5 / linear | |
| TSP-100 | 0.0860 gap% | 0.0414 | rand / s3.0 / L7 / linear | |
| TSP-500 | 5.6087 gap% | 4.8040 | uni / s3.0 / L7 / const | |
| TSP-1000 | 6.3131 gap% | 5.4532 | adap / s1.0 / L7 / linear | |
| MIS-ER | 37.8125 | 39.2969 | uni / s2.0 / L7 / const | |
| MIS-RB | 18.7740 | 19.1120 | adap / s2.0 / L9 / const |
| Task | Config | Gap% or Cost | Time (s) |
|---|---|---|---|
| TSP-100 | Baseline | gap% | 43 |
| TSP-100 | Paper default | gap% | 46 |
| MIS-ER | Baseline | cost | 28 |
| MIS-ER | Paper default (= val optimum) | cost | 32 |
| TSP-50 | Baseline | gap% | 44 |
| TSP-50 | Paper default (transfer) | gap% | 46 |
| 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 |
| 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 |
| Scale | TSP-100 gap% | MIS-ER cost | MIS-RB cost |
|---|---|---|---|
| Baseline | 0.172 | 39.85 | 19.30 |
| 0.178 | 39.20 | 19.30 | |
| 0.248 | 38.73 | 19.14 | |
| 0.518 | 34.90 | 18.78 | |
| 2.448 | 33.35 | 18.68 |
| Axis | TSP | MIS-ER | MIS-RB |
|---|---|---|---|
| Perturbation | adaptive | uniform | adaptive |
| Scale ( ) | 0.1 | 0.1 | 0.2 |
| Layers | L7 | L9 | L5 |
| Schedule | linear | constant | constant |
| Fusion | logit | logit | logit |
| Transferred default: adaptive (TSP) / uniform (MIS-ER) / adaptive (MIS-RB) / / L7 / task-default schedule / logit | |||
| 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 |
| 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) |
| 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 |
| 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 |
| Branch | IS size | prob separation |
|---|---|---|
| Perturbed | 34.52 | 0.448 |
| Normal | 37.54 | 0.787 |
| Guided | 39.49 | 0.886 |
| Step | sc@2 | Shuffled | Ratio | sc@2 95% CI | Ratio 95% CI | |
|---|---|---|---|---|---|---|
| 0 | 1000 | 0.764 | 0.041 | [0.761, 0.767] | [18.3, 18.9] | |
| 1 | 691 | 0.764 | 0.041 | [0.761, 0.768] | [18.3, 18.9] | |
| 2 | 413 | 0.782 | 0.036 | [0.779, 0.785] | [21.7, 22.4] | |
| 3 | 191 | 0.425 | 0.020 | [0.420, 0.429] | [20.6, 21.5] | |
| 4 | 49 | 0.021 | 0.007 | [0.021, 0.022] | [2.9, 3.2] |
| Step | 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% |
| Step | Pref. ratio | 95% CI | 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% |
| Step | CMA | CMA | CMA | Ratio | ||
|---|---|---|---|---|---|---|
| 0 | 0.3 | 1823 | 0.056 | 0.037 | 0.037 | |
| 1 | 0.3 | 1883 | 0.056 | 0.038 | 0.037 | |
| 2 | 0.3 | 1934 | 0.086 | 0.029 | 0.029 | |
| 3 | 0.3 | 50639 | 0.189 | 0.070 | 0.070 | |
| 3 | 0.5 | 7382 | 0.200 | 0.072 | 0.072 | |
| 3 | 0.7 | 548 | 0.249 | 0.076 | 0.076 |
| Step | Perm. | Wilcoxon | Ratio 95% CI | |
|---|---|---|---|---|
| 0 | 0.3 | 0.044 | [1.39, 1.59] | |
| 1 | 0.3 | 0.043 | [1.40, 1.60] | |
| 2 | 0.3 | [2.76, 3.13] | ||
| 3 | 0.3 | [2.64, 2.80] | ||
| 3 | 0.5 | [2.67, 2.87] | ||
| 3 | 0.7 | [3.01, 3.55] |
| Step | sc@2 | Shuffled | Ratio | sc@2 95% CI | |
|---|---|---|---|---|---|
| 1 | 691 | 0.568 | 0.044 | [0.559, 0.578] | |
| 2 | 413 | 0.277 | 0.045 | [0.269, 0.285] | |
| 3 | 191 | 0.021 | 0.024 | [0.019, 0.023] | |
| 4 | 49 | 0.003 | 0.016 | [0.002, 0.003] |
| Step | CMA | CMA | Ratio | Perm. | 95% CI | |
|---|---|---|---|---|---|---|
| 0 | 11 | 0.061 | 0.021 | [2.01, 4.05] | ||
| 1 | 8 | 0.078 | 0.024 | [2.04, 4.72] | ||
| 2 | 28 | 0.103 | 0.029 | [2.60, 4.63] | ||
| 3 | 70 | 0.161 | 0.031 | [4.62, 5.74] | ||
| 4 | 105 | 0.140 | 0.022 | [5.79, 7.40] |
| 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 |
| 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% |
| 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% |
| Diagnostic | Raw | Partial (controlling baseline) | 95% CI of partial |
|---|---|---|---|
| TSP sc@2, steps 0–2 ( ) | 0.44–0.45 | 0.03–0.05 | includes 0 |
| MIS CMA, steps 3–4 ( ) | 0.34–0.39 | 0.33–0.36 | excludes 0 |
| Step | Normal | Guided | Shuffled | (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] |
Combinatorial Optimization
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
See all 412 papers