- 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- 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
-
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.
-
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
- 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.
- 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
-
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?
-
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.
-
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?
-
With the temperature ladder and exchange opportunities held fixed, do energy-dependent exchanges outperform temperature reassignment that does not depend on intermediate energy?
-
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
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 (). 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:
| Source | Variance | Standard Deviation |
|---|---|---|
| Pretrained checkpoint | 0.0018 | 0.043 |
| Inference randomness | 0.0007 | 0.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.
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
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.
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.