- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
Unsupervised NCO removes the costly requirement of solution labels but also the explicit guidance from such labels. For models with iterative exploration and refinement, high-quality solutions are obtained at the cost of overhead during inference; for models with direct inference, discovering high-quality solutions is difficult, but inference is more efficient. BOLT aims to achieve high-quality solutions with training-time exploration and fast direct inference. At each training step, BOLT first constructs a target distribution close to the current solution distribution with relative improvement. It then trains the solution generator to match the target distribution. On three CO problems, BOLT achieves the best solution quality in the shortest time compared to other unsupervised NCO frameworks with direct inference.
Critical strengths
The conceptual framing of the paper is clear and principled. BOLT combines the strengths of both direct inference and iterative exploration and refinement. The high-level intuition of exploring and matching solution distributions with relative improvement is straightforward and well-motivated.
Critical weaknesses
- K solutions are drawn to form the empirical solution distribution, and K determines the number of permutations in computing the objective for matching target distributions. However, the analysis of the effects of different values of K is not provided.
- From the experiments, BOLT finds the best solutions in the shortest time in all settings. However, the setup for the baselines is unclear. Many NCO frameworks have hyperparameters that would significantly affect the solution quality and runtime. The solution quality and runtime reported do not seem to align with previous works (see questions below).
Questions for authors
- Could the authors provide an ablation study showing solution quality (and maybe training overhead) across different choices of K?
- Though it may not affect the conclusions, the solution sizes reported for the baselines do not seem to match those in [1, 2]; for example, EGN and EGN-Anneal achieve 30.68 and 29.24 on MDS on BA-small. EGN takes multiple seeds as input, and the best-performing one is reported. Could the authors clarify what caused the discrepancy in the numbers and what setting they used?
- For the EGN family, including Meta-EGN [3], they are applied by taking multiple seeds during inference to find better solutions. The original papers use 8 seeds as the default setting. From [4, 5], EGN and Meta-EGN can be very efficient, and [4] notes that Meta-EGN can achieve 17.856 on RB-SMALL in 0.065s. Hardware plays an important role, but it seems the authors use the same GPU as [5]. In [5], EGN and Meta-EGN inference time with 8 (resp. 256) seeds is only 0.12s (resp. 2.44s) on MaxCl on graphs with 500 nodes. In comparison, the reported runtime in the manuscript for EGN is 8-9 seconds on RB-SMALL, whose instances have 200–300 nodes. Similarly, the runtime reported in [1,2] is much lower than that in the manuscript. Could the author clarify why the reported runtime is so different?
[1] Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervised neural combinatorial optimization. In ICML, 2024.
[2] Sebastian Sanokowski, Wilhelm Franz Berghammer, Haoyu Peter Wang, Martin Ennemoser, Sepp Hochreiter, and Sebastian Lehner. Scalable discrete diffusion samplers: Combinatorial optimization and statistical physics. In ICLR, 2025.
[3] Haoyu Peter Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta learning. In The Eleventh International Conference on Learning Representations, 2023.
[4] Jiale Ma, Wenzheng Pan, Yang Li, and Junchi Yan. Ml4co-bench-101: Benchmark machine learning for classic combinatorial problems on graphs. In The Thirty-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2025.
[5] Yiqiao Liao, Farinaz Koushanfar,, Parinaz Naghizadeh. Test-Time Adaptation for Unsupervised Combinatorial Optimization. Transactions on Machine Learning Research, 2026.