acceptodds
Under review as a conference paper at ICLR 2027

Parallel Tempering for Diffusion-Based Combinatorial Optimization

Abstract

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.

Primary area:
optimization
Keywords:
Diffusion, Parallel Tempering, Replica Exchange, Combinatorial Optimization, Graph, Machine Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_BWRtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces PT-Denoise, an inference-time procedure for diffusion-based combinatorial optimization. The method maintains concurrent denoising trajectories at the same denoising time, uses different logit temperatures to control sampling randomness, and proposes energy-dependent state exchanges between slots at neighboring temperatures. Maintaining multiple replicas per temperature rung decouples the temperature ladder from population size. All replicas are ultimately decoded using the same conditional expectation decoder to obtain feasible solutions, and the best decoded solution is returned.

The method requires no retraining or architectural modifications. Experiments use pretrained DiffUCO and SDDS models on MIS, minimum dominating set (MDS), maximum cut, and maximum clique. The main comparisons use 100 replicas and 18 diffusion steps, with results reported across three pretrained reference models trained with different seeds. The complete procedure improves the reported mean best-of-NN solution quality in every evaluated setting. The paper also includes a temperature-ladder ablation without exchanges on MIS and a solution-quality versus wall-clock comparison in one setting. The method is explicitly presented as an optimization heuristic under a finite budget, without claiming the equilibrium sampling guarantees of classical parallel tempering.

Critical strengths
  1. The method can be applied directly to existing models, and the backbone comparisons control major confounding factors. PT-Denoise requires no retraining or fine-tuning. The experiments reuse the same architectures, pretrained weights, and conditional expectation decoder, while matching the number of replicas and diffusion steps. This makes the gains of the complete procedure over the original inference protocol reasonably interpretable and makes the method straightforward to adopt.

  2. The complete procedure shows positive results across multiple tasks and two backbones, with additional evidence under wall-clock budgets. The evaluation covers four combinatorial optimization problems and seven problem–size settings, with 1,000 instances in each test set. Across the 14 backbone–setting comparisons, adding PT-Denoise improves the reported mean solution quality. In particular, the mean maximum-clique size obtained by DiffUCO increases from 18.24 to 18.91, showing that the procedure can provide a noticeable benefit in some settings. Figure 2 further shows that, for SDDS on MIS RB Small, the complete procedure outperforms the original sampler within the displayed wall-clock budgets.

Critical weaknesses
  1. The incremental contribution of temperature exchange and the robustness of its gains are not sufficiently established.

The paper includes an important ablation that retains the temperature ladder while disabling exchanges. However, this control appears only for MIS in Table 1; corresponding controls are missing for MDS, maximum cut, and maximum clique. Calculated from the rounded means in the table, the improvements achieved by the temperature ladder without exchanges are approximately 70% and 60% of the total improvements on MIS RB Small for DiffUCO and SDDS, respectively. These percentages are descriptive comparisons of the reported means. Exchanges still provide additional mean improvements, but their incremental contribution has been directly tested only on MIS.

This omission is particularly consequential for the maximum-clique results. The improvement from 18.24 to 18.91 for DiffUCO is one of the paper's more compelling results, but the absence of a corresponding no-exchange temperature-ladder baseline prevents an assessment of how much of this improvement comes from exchanges. Figure 2 also omits a solution-quality versus runtime curve for the temperature ladder without exchanges. Since coordinating trajectories is the central contribution, these controls are needed to establish the magnitude of the benefit attributable to that mechanism.

In addition, the reported error terms are standard deviations across three pretrained models. The paper does not report uncertainty in paired method differences on matched checkpoints and test instances, or state whether inference was repeated with different random seeds and what those repetitions showed. This information is consequential for changes such as the increase from 18.98 to 18.99 in SDDS maximum-clique size and the gain of 0.02 nodes over the no-exchange ladder on MIS RB Large. Small improvements can still be valuable when performance is already close to the best reported results, but they require more precise quantification. Because the methods share pretrained models and test instances, overlapping marginal standard deviations do not establish a lack of statistical significance.

  1. Comparisons with recent strong methods are missing, leaving the method's practical competitiveness unclear.

The main diffusion baselines are DiffUCO and SDDS. The evaluation does not include recent competitive generative approaches to combinatorial optimization, such as GenSCO and MaskCO. Both include MIS experiments on RB-[200–300], which overlaps with a task and graph-size range studied here. GenSCO also reports maximum-clique experiments on RB-[200–300], making these methods directly relevant comparison points. [1,2]

Although GenSCO is discussed in the related work, it is not included in the experiments. The current results support the claim that PT-Denoise improves the selected diffusion backbones, but they do not establish where the resulting solver stands relative to recent methods in terms of solution quality and runtime. Given the paper's emphasis on inference-time optimization and computational efficiency, this omission limits the assessment of its practical value.

Comparisons with GenSCO and MaskCO should at least be provided on the overlapping MIS benchmarks, with GenSCO also included for maximum clique. These comparisons should use identical test instances, comparable hardware, and matched wall-clock budgets, and should report solution quality as a function of runtime. Differences in training data, supervision, and training cost should be stated explicitly, so that PT-Denoise's ability to reuse a pretrained denoiser without retraining is recognized while the resulting solution quality is assessed fairly. GenSCO and MaskCO use their own training procedures and reference solutions; they cannot simply be treated as training-free plug-ins for the original backbones.

[1] Li Y, Chen L, Wang H, et al. Generation as search operator for test-time scaling of diffusion-based combinatorial optimization[J]. Advances in Neural Information Processing Systems, 2026, 38: 127168-127196.

[2] Chen L, Li Y, Yan J. Maskco: Masked generation drives effective representation learning and exploiting for combinatorial optimization[C]//International Conference on Learning Representations. 2026, 2026: 133725-133753.

Questions for authors
  1. On MDS, maximum cut, and maximum clique, what are the paired gains of PT-Denoise over independent sampling on the same temperature ladder, with identical pretrained weights, replica counts, diffusion steps, and decoder? In particular, how much of the DiffUCO maximum-clique improvement remains when this control is included? Could this baseline also be included in the wall-clock comparisons?

  2. Could the authors report paired method differences with confidence intervals and explain how inference randomness was handled? For the smaller gains, do repeated inference runs yield stable positive improvements? Please distinguish variation across pretrained model seeds from variation due to stochastic inference.

  3. On overlapping tasks and identical test instances, how does PT-Denoise compare with GenSCO and MaskCO under matched wall-clock budgets? Could the authors include these comparisons and clearly state differences in supervision, training requirements, and post-processing costs to establish the advantages and scope of the proposed method relative to recent solvers?

  4. With the temperature ladder and exchange opportunities held fixed, do energy-dependent exchanges outperform temperature reassignment that does not depend on intermediate energy?

  5. How were the maximum temperatures of 5.0 and 2.5 for small and large graphs in Appendix B selected, and was a separate validation set used? Do the runtimes in the tables and Figure 2 include decoding, intermediate energy evaluations, matching, and state exchanges, with consistent batching and GPU synchronization?

5 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/3)

We sincerely thank reviewer BWRt for their thorough and insightful feedback. We will now address their concerns in detail.

The reviewer suggested a number of new baselines and ablations, which we consider helpful inclusions. We show the corresponding results on MIS RB small as an example here. The updated paper’s experiments section contains these results on all CO problems and datasets we experiment on: Table 1 (page 7) for MIS, Table 2 (page 7) for MDS, Table 3 (page 8) for maximum cut, and Table 4 (page 8) for maximum clique. We will refer to these results in our discussion as we respond to each individual point.

MethodIS Size ↑Relative Gap ↓Time
DiffUCO + PT-Denoise20.01±0.010.47%±0.03232ms
DiffUCO + Temp. Ladder19.93±0.040.83%±0.18230ms
DiffUCO + Fixed Swap Prob.19.98±0.010.62%±0.06232ms
SDDS + PT-Denoise20.05±0.020.26%±0.08231ms
SDDS + Temp. Ladder20.01±0.020.44%±0.12230ms
SDDS + Fixed Swap Prob.20.03±0.010.34%±0.04232ms
GenSCO19.59±0.012.56%±0.06228ms
MaskCO19.91±0.010.94%±0.04226ms

An important note on timings: The hardware we used for the experiments in the paper is temporarily unavailable to us. The timings presented here were taken on different hardware (an Nvidia GeForce RTX 4090 and an AMD EPYC 7742 64-Core Processor). These timings are comparable with each other but not with the ones in the paper. We will re-time everything on the same hardware for the camera-ready version.

Weakness 1 (Fixed temperature ladder ablation without swaps)

We evaluated the fixed temperature ladder ablation ("Temp. Ladder") without swaps on the remaining CO problems and added them to Tables 2 through 4. We also added it to Figure 2. This ablation performs worse than PT-Denoise on these other CO problems, too, though on maximum cut the differences are small.

The reviewer specifically mentioned the setting DiffUCO on maximum clique, where PT-Denoise improves the base model’s performance of 18.24 (relative gap 4.27%) to 18.91 (relative gap of 0.75%). DiffUCO + Temp. Ladder results in a clique size of 18.85 (relative gap 1.04%), showing that part, but not all, of the improvement can be attributed to the temperature ladder.

Weakness 1, Question 1 (Paired gains)

We thank the reviewer for the suggestion of a paired per-instance test, and report the results in the table below. For each given combination of model checkpoint and test instance, we measured whether using PT-Denoise improved the final decoded solution quality. The table reports the percentage of instances where the solution quality has improved as a result of using PT-Denoise, where it stayed unchanged, and where it worsened. We also report the mean gain in solution quality alongside the 95% confidence interval, as well as the raw p-value of a two-sided sign test on the per-graph differences. We added these results to a new appendix section, Appendix D.

Base ModelSettingImprovedTiedWorseMean gain [95% CI]Sign test p
DiffUCOMIS RB small42%58%0%+0.267 [+0.244, +0.290]1e-126
DiffUCOMIS RB large29%46%25%+0.024 [+0.003, +0.045]0.064
DiffUCOMaxCl RB small36%64%0%+0.573 [+0.505, +0.642]1e-107
DiffUCOMDS BA small22%78%0%+0.108 [+0.094, +0.122]2e-65
DiffUCOMDS BA large23%73%4%+0.079 [+0.066, +0.092]1e-30
DiffUCOMaxCut BA small35%65%1%+0.389 [+0.342, +0.437]6e-94
DiffUCOMaxCut BA large34%53%13%+0.249 [+0.199, +0.300]6e-23
SDDSMIS RB small16%84%0%+0.084 [+0.071, +0.098]5e-42
SDDSMIS RB large30%50%21%+0.052 [+0.031, +0.072]7e-05
SDDSMaxCl RB small2%98%0%+0.008 [+0.004, +0.012]3e-04
SDDSMDS BA small7%93%0%+0.035 [+0.026, +0.044]6e-19
SDDSMDS BA large20%73%8%+0.052 [+0.039, +0.065]3e-14
SDDSMaxCut BA small31%69%0%+0.282 [+0.247, +0.319]3e-90
SDDSMaxCut BA large56%34%10%+0.594 [+0.531, +0.657]5e-79
AuthorsOpenReview ↗

Rebuttal (Part 2/3)

In every single setting, applying PT-Denoise improves the results on more graphs than it worsens, and the mean gain is positive in all settings. Even after applying the Holm–Bonferroni method to correct for the fact that we are making multiple tests simultaneously, 13 out of 14 improvements are statistically significant. The one setting where the improvement is not significant is when applying PT-Denoise to DiffUCO on MIS RB large, though applying our method to SDDS on MIS RB large does result in a significant improvement. Another thing to note is that on the two settings SDDS on MaxCl RB small as well as SDDS on MDS BA small, there is no change in solution quality on more than 90% of graphs. Regardless, the improvement is still significant.

Weakness 2, Question 3 (GenSCO and MaskCO Baselines)

We thank the reviewer for suggesting these relevant baselines. We added comparisons with both GenSCO and MaskCO on MIS RB small, and a comparison with GenSCO on maximum clique. We evaluated the checkpoints using their codebase, but transferred over the same test instances that we used for our other experiments. Their data was drawn from the same distribution as ours. For a fair comparison, we adjusted the cycle counts of these two methods to match the per-instance computation time of our method as closely as possible on the same hardware. The resulting cycle counts are 121 for GenSCO and 335 for MaskCO. The results are shown in Tables 1 and 4 of our updated manuscript, and (for MIS) in the table at the beginning of our response. Note that the authors of these baselines only provide one checkpoint per setting; we therefore calculated the mean and standard deviation over three inference seeds instead of three trained checkpoints. We are careful to make this distinction clear in the paper. Both methods perform worse than DiffUCO + PT-Denoise and SDDS + PT-Denoise. We did not evaluate these two baselines on the other datasets and CO problems, as there were no trained checkpoints available, and training from scratch would not have been possible during the brief rebuttal period.

GenSCO and MaskCO both rely on supervised training, requiring expensive ground truth solutions that are hard to acquire for CO in practice. In contrast, PT-Denoise improves an existing base diffusion model with no additional training. The base models we use in our experiments were trained unsupervised on 4,000 unlabelled training graphs, compared to 90,000 labelled graphs for GenSCO and MaskCO. We note this in the updated manuscript in our comparison with these baselines (lines 405-409). The GenSCO and MaskCO papers do not report training costs for the settings we compare on.

Question 2 (Inference Randomness)

We refer to the table above (weakness 1, question 1) for paired method differences and confidence intervals. In the paper, each checkpoint was evaluated once, using a fixed seed derived from the checkpoint's training seed. Following your suggestion, we additionally evaluated five independent inference seeds for each of the three checkpoints on DiffUCO max cut BA-large, the setting where PT-Denoise shows the smallest relative improvement. All 15 combinations of checkpoint and inference seed show a positive mean gain in solution quality from PT-Denoise, ranging from +0.21 to +0.35 in cut size, and each is significant on its own under a sign test on the per-graph differences (p≤1.2⋅10−6p \leq 1.2 \cdot 10^{-6}). Pooled over all runs, the mean gain is +0.271 with 95% CI [+0.236, +0.308]. (This differs from the table above, which only includes one inference seed.)

The following table shows how the mean gain over the test set varies across checkpoints and across inference runs:

SourceVarianceStandard Deviation
Pretrained checkpoint0.00180.043
Inference randomness0.00070.027

The gain thus varies more across checkpoints than across inference runs. The difference is larger for the absolute objective values (rather than gain): within a checkpoint, the SD across inference seeds is ca. 0.03, compared to ca. 0.2 across checkpoints. The standard deviations reported in our tables therefore mainly reflect variation across pretrained models.

Question 4 (Temperature reassignment that does not depend on intermediate energy)

We ran a simple ablation that exchanges temperatures with a fixed probability of 0.5. The results are shown in Tables 1 through 4 in the updated manuscript, and for MIS RB small in the table at the beginning of our response. The ablation is referred to as “Fixed Swap Prob.” in the tables. It performs slightly worse than PT-Denoise, though we note that this ablation is very similar to PT-Denoise both conceptually and in performance, and the performance differences can be difficult to measure in some settings. Despite this, PT-Denoise performs noticeably better on MDS and maximum clique.

AuthorsOpenReview ↗

Rebuttal (Part 3/3)

Question 5 (Hyperparameter selection and timings)

We used the same datasets as [1, 2] (generated from the same script using the same seed). These each include a validation set of 500 graphs, drawn from the same distribution as the training and test graphs. We chose our hyperparameters using a grid search on the validation set. The hyperparameters were chosen on MIS, and the same values were then used for the other CO problems. The number of replicas was fixed a priori, as it controls the compute budget, and was therefore not subject to the grid search. We agree that this should be discussed in the paper, and added a paragraph on this topic to Appendix E (Hyperparameters).

The runtime measurements capture the full method, including denoising, intermediate energy evaluations, state exchanges, and decoding. Timings were taken with a batch size of 1 and with GPU synchronization. We added a sentence to the experiments section clarifying this.


[1] Sanokowski et al., “A diffusion model framework for unsupervised neural combinatorial optimization”, ICML 2024

[2] Sanokowski et al., “Scalable discrete diffusion samplers: Combinatorial optimization and statistical physics”, ICLR 2025

Reviewer_RGrkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes PT-Denoise, a procedure that runs at inference time on top of pretrained discrete diffusion solvers for graph combinatorial optimization (CO), here DiffUCO and SDDS. The usual approach draws NN independent trajectories at τ=1\tau=1 and keeps the best decoded solution. PT-Denoise instead runs N=RmN=Rm replicas on a geometric ladder of RR logit temperatures 1=τ1<⋯<τR1=\tau_1<\dots<\tau_R, with mm replicas per rung. Each replica samples from the temperature-scaled kernel K(τ)θ,tK^{(\tau)}{\theta,t} (Eq. 3). After each denoising step, it computes the relaxed energy HG(xt)H\mathcal{G}(x_t) of the intermediate state. States on neighboring rungs are then exchanged with a Metropolis-style rule (Eq. 6). Rungs are paired in alternating odd/even order, with a uniform random one-to-one matching inside each pair of rungs. Lower-energy states tend to move to colder rungs. The method needs no retraining and uses the same number of denoiser calls as independent sampling. The authors say it is a heuristic and does not keep the sampling guarantees of classical parallel tempering. Validation:

  • Setup: MIS on RB graphs (small and large), MDS and max cut on BA graphs (small and large), and max clique on RB small. Each test set has 1,000 instances. They use N=100N=100, T=18T=18, conditional-expectation decoding, and 3 published checkpoints per backbone.
  • Main result: PT-Denoise improves mean best-of-NN in every setting. Gains are large on small graphs (DiffUCO MIS RB-small gap 1.79% → 0.47%; max clique 4.27% → 0.75%). They are small on large graphs and on max cut. Overhead is at most 1 ms per instance.
  • Ablation: On MIS only, a ladder without swaps lands between the baseline and PT-Denoise.
  • Compute budget (Fig. 2): On MIS RB-small, SDDS + PT-Denoise beats plain SDDS at every budget from 10 to 20 ms.
Critical strengths
  1. A simple, cheap add-on with a clear win at matched compute on small graphs. It uses the same number of denoiser calls, and the only extra cost is energy evaluations and swaps (≤1 ms). Fig. 2 shows SDDS + PT-Denoise with about 120 replicas (13 ms) reaching about 0.26% gap, while plain SDDS with 400 replicas (20 ms) stays near 0.56%. So, in this setting, coordinating trajectories beats just increasing NN. This is the paper's main practical claim, and it is well supported here.
  2. The ladder-without-swaps ablation separates two effects. On MIS RB-small, adding swaps on top of a fixed ladder gives a clear extra gain: DiffUCO 0.83% → 0.47% and SDDS 0.44% → 0.26%. This shows that part of the improvement comes from the exchange step itself, not only from sampling at hotter temperatures.
Critical weaknesses
  1. Key baselines are missing, novelty is limited, and gains are small outside small graphs.
    • No comparison with close prior methods. The paper discusses inference-time methods that use the same intermediate energy signal but compares against none of them. These include Feynman–Kac steering / SMC resampling (Singhal et al. 2025), importance weighting (Ou et al. 2026), GenSCO, and CREPE (He et al. 2026). CREPE already applies replica exchange to pretrained discrete diffusion.
    • Novelty is a small step over prior work. The new parts are exchanging at the same denoising time across logit temperatures, plus several replicas per rung. The second is the ensemble-tempering idea of Vousden et al. (2016).
    • Too few baselines. The only baselines are independent sampling at τ=1\tau=1 and a fixed ladder. Without SMC/FK resampling at the same budget, and without a tuned single temperature (including τ<1\tau<1), we cannot tell whether PT-Denoise is the best use of the budget.
    • Gains on large graphs are within one std. MIS RB-large: DiffUCO 3.48 → 3.40 (±0.08 / ±0.06) and SDDS 2.73 → 2.64 (±0.16 / ±0.08). The no-swap ladder gets 3.45 / 2.69.
    • Gains elsewhere are tiny. Max cut improves by about 0.05% (734.18 → 734.55). MDS BA-large goes 104.01 → 103.92.
    • Statistics are thin. The std is over only 3 checkpoints, and there is no paired per-instance test.
    • So the claim "consistently improves" in the abstract is supported mainly on small graphs.
  2. The swap rule has little justification, and the analysis is thin.
    • The same τ\tau does two jobs. Eq. 6 uses τ\tau both to scale logits and as a Boltzmann temperature over HGH_\mathcal{G}. Eq. 4 itself shows these two are not linked. As a result, the acceptance rate depends on the arbitrary scale of HGH_\mathcal{G} (through AA, BB, and graph size). On large graphs, ∣ΔH∣|\Delta H| grows, so swaps likely become close to deterministic sorting.
    • Missing diagnostics and ablations. The paper reports:
      • no acceptance rates;
      • no comparison with a simpler deterministic rule (sort states by energy and assign the coldest rungs to the best states);
      • no measure of how well HG(xt)H_\mathcal{G}(x_t) predicts the final decoded objective at each tt. The authors list this as a limitation.
    • Contribution 2 is not tested. Decoupling RR from mm is a listed contribution, but there is no m=1m=1 vs. m>1m>1 comparison and no R/mR/m sweep.
    • Hyperparameter selection is not described. There is no procedure or validation set for τR\tau_R (5.0 small vs. 2.5 large) or R=10R=10, so they may have been tuned on the test set.
    • The ablation covers MIS only.
Questions for authors

Clarifications that could change my assessment:

  1. How were τR\tau_R, RR, and mm chosen? Was a validation set used that is separate from the 1,000 test instances?
  2. What are the swap acceptance rates per rung pair and per step, for small vs. large graphs? Is HGH_\mathcal{G} normalized in any way before Eq. 6?
  3. How well does HG(xt)H_\mathcal{G}(x_t) rank-correlate with the final decoded fGf_\mathcal{G} at each tt?
  4. Are the gains significant under a paired per-instance test (same checkpoint, with and without PT-Denoise), especially on RB-large and max cut?
  5. How does the best single tuned temperature, including τ<1\tau<1, compare to PT-Denoise? Did you try rungs below τ=1\tau=1?

Experiments that would materially strengthen the paper:

  1. Compare with SMC / FK-steering resampling using the same energy potential and denoiser budget, and with CREPE if feasible.
6 comments
AuthorsOpenReview ↗

Rebuttal (Part 1)

We sincerely thank reviewer RGrk for their time and their thorough review. It suggested multiple additional experiments and analyses, which we believe strengthened our paper’s evaluation and give new insight into our method. We apologize in advance for the lenghty response, as there are many points to address.

We show the results for the new baselines and ablations on MIS RB small as an example here. The updated paper’s experiments section contains these results on all CO problems and datasets we experiment on: Table 1 (page 7) for MIS, Table 2 (page 7) for MDS, Table 3 (page 8) for maximum cut, and Table 4 (page 8) for maximum clique. We will refer to these results in our discussion as we respond to each individual point.

MethodIS Size ↑Relative Gap ↓Time
DiffUCO + PT-Denoise20.01±0.010.47%±0.03232ms
DiffUCO + PT-Denoise (m=1)19.97±0.010.64%±0.07231ms
DiffUCO + Tuned Temp. (τ\tau=1.7)19.82±0.041.37%±0.20231ms
DiffUCO + FK Steering19.64±0.022.27%±0.11233ms
DiffUCO + CREPE19.71±0.021.95%±0.11296ms
SDDS + PT-Denoise20.05±0.020.26%±0.08231ms
SDDS + PT-Denoise (m=1)20.03±0.010.33%±0.03231ms
SDDS + Tuned Temp. (τ\tau=1.7)20.00±0.020.48%±0.12230ms
SDDS + FK Steering19.79±0.041.53%±0.20232ms
SDDS + CREPE19.97±0.010.64%±0.07298ms
GenSCO19.59±0.012.56%±0.06228ms
MaskCO19.91±0.010.94%±0.04226ms

An important note on timings: The hardware we used for the experiments in the paper is temporarily unavailable to us. The timings presented here were taken on different hardware (an Nvidia GeForce RTX 4090 and an AMD EPYC 7742 64-Core Processor). These timings are comparable with each other but not with the ones in the paper. We will re-time everything on the same hardware for the camera-ready version.

Weaknesses 1a and 1c, Questions 5 and 6 (Baselines)

The reviewer brings up some very interesting baselines, which we believe to be useful points of comparison for PT-Denoise.

We had experimented with FK-steering [1] very early on in the project, and found that it did not work well in a CO setting. We reran the FK-steering baseline for all CO problems and datasets, using both DiffUCO and SDDS as base models. We allow for the same number of denoiser evaluations to match the compute budget. The results are shown in the summary tables above. FK-steering performs substantially worse than PT-Denoise at a matched compute budget, matching our initial findings. We hypothesize that FK-steering suffers from attempting to sample from the target distribution, as it does not make use of the best-of-N setting. The resampling that is part of FK-steering reduces the diversity of the samples, which is a hindrance when the best sampled solution is used as the final output.

We also implemented CREPE [2] as a baseline, again allowing the same number of denoiser calls (though this can result in longer wall clock times, as the calls can be sequential). The number of chains was tuned using a grid search on MIS RB small using a validation set, resulting in 3 chains. This value was used for all experiments, matching how we tuned our own method. CREPE performs better than FK-steering in most settings, but worse than PT-Denoise. With CREPE, all candidates come from a small number of warm starts (equal to the number of chains), limiting diversity. We hypothesize that this is disadvantageous in a best-of-N setting.

We were also able to compare against GenSCO [3] as well as MaskCO [4] (the latter of which was suggested by reviewer BWRt), as the authors provide a trained checkpoint for MIS on RB small, and GenSCO also provides a checkpoint for maximum clique. We evaluated these checkpoints using their codebase, but transferred over the same test instances that we used for our other experiments. Their data was drawn from the same distribution as ours. We adjusted the cycle counts of these two methods to match the per-instance computation time of our method as closely as possible on the same hardware. The resulting cycle counts are 121 for GenSCO and 335 for MaskCO. The results are shown in Tables 1 and 4 of the updated manuscript, and (for MIS) in the table above. Note that the authors of these baselines only provide one checkpoint per setting; we therefore calculated the mean and standard deviation over three inference seeds instead of three trained checkpoints. We are careful to make this distinction clear in the paper. Both methods perform worse than SDDS + PT-Denoise.

AuthorsOpenReview ↗

Rebuttal (Part 2)

We ran a simple ablation that uses a single, tuned temperature, τ=1.7\tau = 1.7, for all replicas. This temperature value was obtained using a grid search on MIS RB small using the validation set. Temperatures below 1 performed worse. This single-temperature ablation performs similarly to the fixed ladder ablation without replica swaps in most settings. The fixed ladder ablation can be seen as a variant of the single temperature ablation that reduces the reliance on tuning the temperature. Both ablations generally perform worse than PT-Denoise, though the differences are small in some settings.

On a related note, we saw no consistent benefits empirically in extending PT-Denoise’s temperature ladder below a minimum temperature of 1. Since 1 is a common choice of minimum temperature in the parallel tempering literature, we followed this for PT-Denoise. We discuss the choice of our temperature ladder in Appendix B of the original manuscript (Hyperparameters).

Weakness 1b (Novelty)

We agree that PT-Denoise builds on established methods: replica exchange [8,9], even/odd swap schedules [10], and groups of replicas per temperature [7]. We cite these papers. We respectfully disagree, however, that the method is a small step, for the following reasons.

  1. Our method differs in what is being tempered and where exchanges take place. In classical parallel tempering, Vousden et al. [7] included, each rung samples a tempered target with an MCMC kernel, and exchanges preserve a joint stationary distribution. PT-Denoise has no MCMC kernel and no stationary distribution at any rung. The replicas are partial trajectories of a pretrained discrete denoiser. We temper the denoiser's transition logits, not a density. Exchanges compare intermediate states at the same denoising step through a relaxed energy, which serves as a surrogate for final solution quality. This also differs from the closest diffusion-based work: CREPE exchanges replicas across diffusion times, preserving the target via path likelihood ratios. FK steering resamples particles, duplicating some states and discarding others; PT-Denoise instead permutes states among replicas.
  2. Different goal and setting. Classical parallel tempering, CREPE and FK steering aim at (asymptotically) exact sampling from a target distribution. PT-Denoise, on the other hand, is an optimization procedure for CO problems. It aims to improve the best out of N sampled solutions under a fixed number of denoiser evaluations. We believe this to be a contributing factor for PT-Denoise's better performance.
  3. On Vousden et al. [7]: Their contribution is dynamic temperature selection: adapting the ladder so that adjacent rungs swap at equal rates. In PT-Denoise, using multiple replicas per rung serves a different purpose: it decouples the sample budget NN from the number of temperatures RR, so the temperature ladder can be adjusted without changing the number of denoiser evaluations.

We reworked the corresponding parts of our related-work section to make these distinctions explicit.

Weaknesses 1d, 1e and 1f, Question 4 (Small gains)

We agree that the gains appear small in some settings, and thank the reviewer for the suggestion of a paired per-instance test, which we followed. For each given combination of model checkpoint and test instance, we measured whether using PT-Denoise led to a better solution compared to using the base method. The table below reports the percentage of instances where the solution quality (measured after decoding) has improved, where it stayed unchanged, and where it worsened. We also report the mean gain in solution quality alongside the 95% confidence interval, as well as the raw p-value of a two-sided sign test on the per-graph differences. We added these results to a new appendix section, Appendix D.

Base ModelSettingImprovedTiedWorseMean gain [95% CI]Sign test p
DiffUCOMIS RB small42%58%0%+0.267 [+0.244, +0.290]1e-126
DiffUCOMIS RB large29%46%25%+0.024 [+0.003, +0.045]0.064
DiffUCOMaxCl RB small36%64%0%+0.573 [+0.505, +0.642]1e-107
DiffUCOMDS BA small22%78%0%+0.108 [+0.094, +0.122]2e-65
DiffUCOMDS BA large23%73%4%+0.079 [+0.066, +0.092]1e-30
DiffUCOMaxCut BA small35%65%1%+0.389 [+0.342, +0.437]6e-94
DiffUCOMaxCut BA large34%53%13%+0.249 [+0.199, +0.300]6e-23
SDDSMIS RB small16%84%0%+0.084 [+0.071, +0.098]5e-42
SDDSMIS RB large30%50%21%+0.052 [+0.031, +0.072]7e-05
SDDSMaxCl RB small2%98%0%+0.008 [+0.004, +0.012]3e-04
SDDSMDS BA small7%93%0%+0.035 [+0.026, +0.044]6e-19
SDDSMDS BA large20%73%8%+0.052 [+0.039, +0.065]3e-14
SDDSMaxCut BA small31%69%0%+0.282 [+0.247, +0.319]3e-90
SDDSMaxCut BA large56%34%10%+0.594 [+0.531, +0.657]5e-79
AuthorsOpenReview ↗

Rebuttal (Part 3)

In every single setting, applying PT-Denoise improves the results on more graphs than it worsens, and the mean gain is positive in all settings. Even after applying the Holm–Bonferroni method to correct for the fact that we are making multiple tests simultaneously, 13 out of 14 improvements are statistically significant. The one setting where the improvement is not significant is when applying PT-Denoise to DiffUCO on MIS RB large, though applying our method to SDDS on MIS RB large does result in a significant improvement. Another thing to note is that on the two settings SDDS on MaxCl RB small as well as SDDS on MDS BA small, there is no change in solution quality on more than 90% of graphs. Regardless, the improvement is still significant.

In the settings the reviewer asks about (MIS RB large and max cut BA small/large), SDDS + PT-Denoise improves significantly over plain SDDS, and improves the results on a substantial portion of test graphs.

Weakness 1g (Claim "consistently improves")

We believe that the additional experiments we provide in the previous section demonstrate that our method consistently improves the average quality of the best found solution over SDDS.

Weaknesses 2a and 2b, Questions 2 and 3 (Scale of HGH_\mathcal{G}, missing diagnostics)

We thank the reviewer for bringing up this point. The assessment that the swap acceptance rate depends on the scale of HGH_\mathcal{G} is correct. Our method is based on Parallel Tempering, where the energy represents a physical quantity. In combinatorial optimization, however, the scale of the energy function is arbitrary. Depending on the definition of HGH_\mathcal{G}, this scale can (but doesn’t have to) depend on graph size. An additional parameter normalizing the scale of HGH_\mathcal{G} could be used in equation 6 to remedy this. However, we found in practice that the swap acceptance rate does not reach abnormal levels on large graphs. The table below shows the average swap acceptance rate by rung pair for SDDS + PT-Denoise on MIS. Mean and standard deviation are given over three checkpoints.

PairRB SmallRB Large
0 (coldest)0.61 ± 0.040.64 ± 0.03
10.61 ± 0.040.70 ± 0.04
20.59 ± 0.040.69 ± 0.05
30.60 ± 0.040.69 ± 0.05
40.60 ± 0.050.65 ± 0.05
50.62 ± 0.050.63 ± 0.05
60.64 ± 0.060.58 ± 0.05
70.67 ± 0.050.56 ± 0.05
8 (hottest)0.69 ± 0.060.50 ± 0.04
Mean0.63 ± 0.050.63 ± 0.04

These are the swap acceptance rates by denoising step for SDDS + PT-Denoise on MIS, averaged over all rung pairs:

Step ttRB SmallRB Large
10.69 ± 0.060.56 ± 0.03
30.56 ± 0.020.50 ± 0.09
50.49 ± 0.020.40 ± 0.04
70.44 ± 0.010.37 ± 0.08
90.44 ± 0.030.47 ± 0.09
110.51 ± 0.080.60 ± 0.07
130.67 ± 0.120.76 ± 0.04
150.82 ± 0.140.89 ± 0.03
170.94 ± 0.040.96 ± 0.00

As these numbers show, swap acceptance rates generally stay in the range of 0.4 to 0.6, only reaching high rates in the final denoising steps. Graph size only has a small influence on the acceptance rate in practice. PT-Denoise is currently not normalizing HGH_\mathcal{G} before equation 6. We agree that normalization could be beneficial in cases where HGH_\mathcal{G} varies more strongly based on graph size, and added a brief discussion on this topic to the “Limitations and future work” paragraph.

The next table shows the rank-correlation (Spearman ρ\rho) between intermediate energies at denoising step tt and the final, decoded solution quality for SDDS + PT-Denoise on MIS.

Step ttRB SmallRB Large
10.12 ± 0.030.00 ± 0.00
30.18 ± 0.040.02 ± 0.02
50.22 ± 0.040.05 ± 0.02
70.24 ± 0.030.09 ± 0.04
90.26 ± 0.020.15 ± 0.05
110.27 ± 0.000.27 ± 0.08
130.38 ± 0.060.50 ± 0.15
150.67 ± 0.130.87 ± 0.04
170.77 ± 0.060.94 ± 0.00

The table confirms the statement in our limitations paragraph. While the intermediate energy correlates well with final solution quality in later denoising steps, this does not hold in earlier steps. Part of the reason for this is that replicas can undergo larger changes over a larger number of denoising steps. We added the measurements for both the acceptance rates and the rank-correlations to Appendix D.

Reviewer_EDf8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This submission introduces parallel tempering into the inference stage of discrete diffusion-based combinatorial optimization. It coordinates multiple denoising trajectories through temperature exchanges, improving best-of-N solution quality under a fixed inference budget, without retraining or fine-tuning and with little additional overhead. It consistently improves DiffUCO and SDDS on MIS, MDS, max-cut, and max-clique. It is a practical method and could be useful in specific problem settings.

However, its weaknesses is also obvious. First, it has a weak theoretical foundation. It does not preserve Boltzmann distributions and does not inherit the sampling guarantees of parallel tempering. It has narrow problem coverage, targets only node-subset problems with no routing.

Critical strengths
  1. It is plug-and-play, with no retraining or fine-tuning. It acts directly on pretrained discrete diffusion solvers (DiffUCO, SDDS), so deployment cost is low.
  2. In all experiments it adds at most about 1 ms per instance, so the quality gains are essentially free.
  3. It has a good support since parallel tempering/replica exchange is a mature method in statistical physics and computational chemistry, and the exchange criterion has a Metropolis–Hastings justification.
  4. The experiments cover four graph-structured CO problems and two backbones, with consistent improvements, and the ablation shows that the exchange itself is useful.
Critical weaknesses
  1. Lack of theoretical guarantees. Temperature-scaled denoising generally does not preserve Boltzmann distributions, so the overall procedure does not inherit the sampling guarantees of classical parallel tempering. It borrows the exchange mechanism of PT but not its sampling guarantees, and is essentially heuristic trajectory coordination.

  2. It is evaluated only on node-subset problems on graphs (MIS, MDS, max-cut, max-clique), with no edge-decision or routing problems such as TSP/CVRP. Generality may be limited.

  3. Gains are minor on some problems like max-cut.

  4. The ``at most 1 ms'' claim was measured on small graphs with 18 diffusion steps, it is unclear how the extra time cost is on larger problems.

  5. It may be highly dependent on energy function design. Different CO problems require different energy functions (Appendix A), so the method is not fully problem-agnostic.

  6. It seems to have many hyperparameters to be tuned on different datasets, please discuss the dependence and robustness.

Questions for authors

See above in Weaknesses.

2 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/2)

We thank the reviewer for their feedback, which we will now address in detail.

Weakness 1 (Not preserving sampling guarantees)

It is true that our method does not inherit the sampling guarantees of parallel tempering. In particular, it does not preserve the diffusion model’s probability distribution. However, it is important to note that preserving this distribution is of no particular benefit in the CO settings we consider, where the only relevant metrics are solution quality and computation time/compute budget. When comparing PT-Denoise to methods like FK-steering [1] and CREPE [2], which sample from the target distribution, it can be argued that PT-Denoise performs much better for CO precisely because it does not prioritise sampling guarantees that aren’t directly relevant to CO. (Please see the table at the top of our response to reviewer RGrk for a direct comparison with FK-steering and CREPE). The base models we use, DiffUCO and SDDS, choose the Boltzmann distribution’s temperature such that some probability mass is placed on suboptimal solutions, as the model becomes too difficult to train otherwise. Strictly adhering to this distribution inherently means also sampling lower-quality solutions.

Weakness 2 (Choice of CO problems)

Evaluating on the node subset problems we chose is common in the ML for CO literature [3, 5, 7, 8, 9]. In particular, since our work builds on [7, 9], we follow their evaluation procedure as closely as possible (we mention this in lines 400-401 of the original manuscript). This same evaluation procedure was previously established by [3]. Our evaluation therefore follows the conventions established by prior work.

Weakness 3 (Small gains on some problems)

We conducted a paired per-instance test to more clearly illustrate the gains on problems like max cut, where the differences seem small. We report the results in the table below. For each given combination of model checkpoint and test instance, we measured whether using PT-Denoise led to a better solution compared to using the base method. The table reports the percentage of instances where the solution quality (measured after decoding) has improved as a result of using PT-Denoise, where it stayed unchanged, and where it worsened. We also report the mean gain in solution quality alongside the 95% confidence interval, as well as the raw p-value of a two-sided sign test on the per-graph differences. We added these results to a new appendix section, Appendix D.

Base ModelSettingImprovedTiedWorseMean gain [95% CI]Sign test p
DiffUCOMIS RB small42%58%0%+0.267 [+0.244, +0.290]1e-126
DiffUCOMIS RB large29%46%25%+0.024 [+0.003, +0.045]0.064
DiffUCOMaxCl RB small36%64%0%+0.573 [+0.505, +0.642]1e-107
DiffUCOMDS BA small22%78%0%+0.108 [+0.094, +0.122]2e-65
DiffUCOMDS BA large23%73%4%+0.079 [+0.066, +0.092]1e-30
DiffUCOMaxCut BA small35%65%1%+0.389 [+0.342, +0.437]6e-94
DiffUCOMaxCut BA large34%53%13%+0.249 [+0.199, +0.300]6e-23
SDDSMIS RB small16%84%0%+0.084 [+0.071, +0.098]5e-42
SDDSMIS RB large30%50%21%+0.052 [+0.031, +0.072]7e-05
SDDSMaxCl RB small2%98%0%+0.008 [+0.004, +0.012]3e-04
SDDSMDS BA small7%93%0%+0.035 [+0.026, +0.044]6e-19
SDDSMDS BA large20%73%8%+0.052 [+0.039, +0.065]3e-14
SDDSMaxCut BA small31%69%0%+0.282 [+0.247, +0.319]3e-90
SDDSMaxCut BA large56%34%10%+0.594 [+0.531, +0.657]5e-79

In every single setting, applying PT-Denoise improves the results on more graphs than it worsens, and the mean gain is positive in all settings. Even after applying the Holm–Bonferroni method to correct for the fact that we are making multiple tests simultaneously, 13 out of 14 improvements are statistically significant. The one setting where the improvement is not significant is when applying PT-Denoise to DiffUCO on MIS RB large, though applying our method to SDDS on MIS RB large does result in a significant improvement. Another thing to note is that on the two settings SDDS on MaxCl RB small as well as SDDS on MDS BA small, there is no change in solution quality on more than 90% of graphs. Regardless, the improvement is still significant.

In the max cut settings the reviewer asks about, PT-Denoise improves significantly over the base models, and improves the results on a substantial portion of test graphs.

AuthorsOpenReview ↗

Rebuttal (Part 2/2)

Weakness 4 (Computation cost)

We thank the reviewer for this question. We note that the overhead incurred by PT-Denoise was at most 1ms on both small and large graphs in our experiments. To further illustrate the cost, we added the following analysis to a new appendix section (Appendix C), showing that the overhead added by PT-Denoise grows with the same quantities and at the same rate as the base model. In other words, the relative overhead added by PT-Denoise does not grow with graph size.

Let NN be the number of replicas, m<Nm < N the number of replicas per temperature, TT the number of denoising steps, and let the graph have ∣V∣|V| nodes and ∣E∣|E| edges. In each step, the base model evaluates the GNN on all NN replicas. With LL message-passing layers of width ww, this costs at least Θ(NLw(∣V∣+∣E∣))\Theta(NLw(|V|+|E|)). PT-Denoise adds three operations to each step:

  1. Calculating energies HG(xt(i))H_\mathcal{G}(x_t^{(i)}) of all replicas. For the energy functions we use in our experiments, this can be evaluated in Θ(N(∣V∣+∣E∣))\Theta(N(|V|+|E|)).
  2. Swap proposals and acceptance between adjacent temperature groups. Since they operate on NN scalar energies, they cost Θ(N)\Theta(N) for the acceptance tests and O(Nlog⁡m)\mathcal{O}(N \log m) for the random matching within each pair of groups.
  3. Applying the accepted swaps. This is a permutation of the replica states and costs Θ(N⋅∣V∣)\Theta(N \cdot |V|).

PT-Denoise adds no additional model evaluations, and scaling the logits by the temperature costs Θ(N⋅∣V∣)\Theta(N \cdot |V|).

The extra cost per step is therefore O(N(∣V∣+∣E∣)+Nlog⁡m)\mathcal{O}(N(|V|+|E|)+N \log m). The overhead added by PT-Denoise scales with the following quantities, and we compare this scaling to the denoiser:

  • Graph size: Both the denoiser and PT-Denoise are linear in ∣V∣+∣E∣|V|+|E|. The overhead is a fixed fraction of order 1/(Ld)1 / (Ld) of the denoiser's cost, independent of graph size and density.
  • Diffusion steps: Both grow linearly in TT, so the relative overhead does not depend on TT.
  • Number of replicas: Both are linear in NN, apart from an O(log⁡m)\mathcal{O}(\log m) factor applied only to NN scalars.

The overhead of PT-Denoise grows with the same quantities, and at the same rate, as the cost of the denoiser itself, therefore its relative cost does not grow with problem size. (Note that mm is a hyperparameter and does not grow with problem size).

Weakness 5 (Dependence on energy function design)

Reliance on a hand-crafted, relaxed version of the CO problem’s objective function (which we call energy function in our paper) is very common in ML for CO methods [4-9], though they are often called surrogate loss functions in the literature (among other terms). We chose the term energy function to align with the terminology used by [7, 9] as well as the parallel tempering literature. The concept of using a relaxed surrogate of the CO problem’s objective function has initially been popularized by [4], and has found wide adoption since. As many, if not most, of the recent methods in this field use energy functions, widely accepted formulations exist for many common CO problems. Even in cases where no such function exists in the literature, one can easily be designed by following the common template of relaxing the CO problem’s objective function to continuous inputs and adding a penalty term that disincentivizes constraint violations.

Weakness 6 (Hyperparameters)

We tuned our hyperparameters using a grid search on a validation set of 500 graphs, drawn from the same distribution as the training and test graphs. The hyperparameters were chosen on MIS, and the same values were then used for the other CO problems. The number of replicas was fixed a priori, as it controls the compute budget, and was therefore not subject to the grid search. We added a paragraph discussing this to Appendix E (Hyperparameters).

In our view, the fact that the same set of hyperparameters tuned on one CO problem also produces favorable results on the other three problems demonstrates the robustness of our method.


[1] Singhal et al., “A general framework for inference-time scaling and steering of diffusion models”, 2025

[2] He et al., “CREPE: Controlling diffusion with replica exchange”, 2026

[3] Zhang et al., “Let the flows tell: Solving graph combinatorial optimization problems with GFlowNets”, 2023

[4] Karalias & Loukas, “Erdos goes neural: An unsupervised learning framework for combinatorial optimization on graphs”, 2020

[5] Sun et al., “Annealed training for combinatorial optimization on graphs”, 2022

[6] Min et al., “Can hybrid geometric scattering networks help solve the maximum clique problem?”, 2022

[7] Sanokowski et al., “A diffusion model framework for unsupervised neural combinatorial optimization”, 2024

[8] Wenkel et al., “Towards a general recipe for combinatorial optimization with multi-filter GNNs”, 2024

[9] Sanokowski et al., “Scalable discrete diffusion samplers: Combinatorial optimization and statistical physics”, 2025

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.