acceptodds
Under review as a conference paper at ICLR 2027

BOLT: Breadth-Oriented Learning via Training-Time Exploration for Unsupervised Neural Combinatorial Optimization

Abstract

Unsupervised neural combinatorial optimization (NCO) avoids the need for costly high-quality solution labels, but it also removes the supervisory signals that facilitate learning. Existing unsupervised solvers often compensate for this missing guidance through iterative exploration at inference, requiring repeated neural network evaluations. Direct inference avoids such iterative computation, but also removes the opportunity for inference-time exploration. We introduce BOLT, a breadth-oriented learning framework that moves solution exploration from iterative inference to training time while retaining direct inference at test time. To enable this, we introduce self-improving population guidance to progressively construct improved targets relative to the current generator, and decoder basin matching to transfer these improvements back to the generator. Experiments on three graph optimization problems and two graph scales show that BOLT consistently improves solution quality over prior direct unsupervised NCO methods while retaining efficient inference.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural Combinatorial Optimization, Generative Models, Unsupervised Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_zPMAOpenReview ↗
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.

Reviewer_vLY1OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BOLT, which improves the solution quality of the direct generator through self-improvement training without relying on external high-quality solution labels. The generator outputs the priorities of all nodes at once, and then a problem-specific greedy decoder generates feasible solutions. SIPG samples the priority vector from the current model and expands the candidate pool through differential evolution-style perturbation. The weights of the candidate solutions are then optimized, using an energy objective to encourage high-quality solutions and MMD regularization to limit the deviation of the target distribution from the current empirical distribution. DBM expresses the priority relationship that can reproduce the target solution as a decoder-compatible loss and uses Hungarian matching to match the model output with the target solution, avoiding regression to a unique priority representation. These two approaches alternate to form a self-improvement loop; during testing, only one network forward pass and greedy decoding are needed. Experiments cover two graph scales for MIS, MaxCl, and MDS. Under a unified single-sample direct inference setting, BOLT achieves the lowest gap in all six settings and has the lowest execution time among methods tested in the same environment.

Critical strengths
  1. BOLT achieves the lowest gap in all six direct inference settings.
  2. Ablation supports the role of target distribution construction and decoder-compatible supervision.
Critical weaknesses
  1. Existing experiments support specific improvements in self-improvement training, but the stated motivation of “transferring inference-time exploration to training” does not align well with the actual methodological contribution. (main)
  2. Total training cost is not reported; training steps, batch size, energy coefficient A, and Frank-Wolfe stopping conditions are missing.
Questions for authors
  1. Please explain how the motivation to “transfer inference-time exploration to training” specifically guides the design of SIPG and DBM.
  2. Please complete the above training and optimization settings and report the total training cost of BOLT and the baselines.
  3. Please provide a sensitivity analysis of the MMD regularization coefficient λ, report the solution quality under different values, and explain the basis for choosing λ=10.
Reviewer_VLkiOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2(+1)
Soundness
3(+1)
Read review
Paper summary

The paper studies neural combinatorial optimization, focusing on direct generators that use a single forward pass for each solution. During inference the proposed generator predicts a latent vector h and problem specific non-differentiable decoder transforms this into a single discrete solution, without iterative refinement or multi seed sampling. These types of models are sometimes called non-autoregressive or single step diffusion models as well. The paper proposes BOLT, a breath-oriented training framework that uses exploration during training to discover better solutions compared to current ones and then use that as supervision to improve the generator inside a self-improvement loop. During training-time exploration, BOLT generates a solution pool by first sampling solutions from the current model and then expanding these with a differential-evolution-style population operator. Then BOLT creates a new target distribution by solving an optimizing problem for promoting lower energy target distributions and likeliness under the current generator. This stage is referred to it as self-improving population guidance. Then the following stage aims to use this as a supervision to improve the generator. Due to the degeneracy in the decoder, a solution can be represented with different latents. The authors propose penalizing latents that are not decoded to the matched target solution rather than forcing a specific one. For a solution x, its decoder basin represents the set of all possible h that maps to x. For the Maximum Independent Set (MIS) and Maximum Clique (MaxCl) problems, this means a latent variable corresponding to a node in the solution must be larger than its neighbors’ latents, which translates into a loss function resembling contrastive loss. The Hungarian algorithm is used to find the minimum cost matching between generated latents and sampled solutions from the target distribution to remove ordering dependency. BOLT is quite fast and outperforms compared unsupervised direct baselines on Minimum Dominating Set (MDS), MIS, and MaxCl on synthetic instances.

Critical strengths

The decoder basin and transfer objective that penalizes solutions that violate this definition is novel and could be applied to other problems under supervised or self-supervised learning.

BOLT outperforms compared unsupervised direct baselines on MIS, MaxCl, and MDS problems on synthetic instances and it is quite fast since it is a direct generator.

Critical weaknesses

The experimental results are obtained from a single seed and ablation experiments such as Best-candidate target and Pointwise regression leads to very similar results compared to the full configuration. It is unclear whether these are statistically significant or whether the introduced complex machinery worth the improvement. Compared to state-of-the-art NCO frameworks that are not bounded by direct generation substantially outperforms BOLT. The paper does not claim outperforming those methods, but it also does not compare against them at al. BOLT does not have to outperform other baselines but not mentioning them at all makes position and takeaways of the paper less clear. Comparing them across other papers actually shows that BOLT moves direct generators closer to iterative methods. This could have been a strength if presented but unfortunately the current version of the paper makes these deductions impossible for readers that are not familiar with the literature and decreases the informativeness of the paper.

The paper is written in a way that makes simple things sound complex, and this makes it hard to understand. The contributions or takeaways of the paper are not highlighted. The motivation for direct generation is unclear, given that diffusion or iterative refinement-based baselines offer time-quality trade-off, which is essential for combinatorial optimization. The main claim is improving the performance over unsupervised direct generators, which limits the impact of the paper. I think the paper could compare against other NCO baselines and claim that BOLT unlocks a new quality-time trade-off by outperforming other NCO methods at a matched budget if it is supported. This would help motivate direct generation and connects the paper to the general NCO literature.

Questions for authors

Another strength of diffusion or iterative refinement-based methods is that they can spend more time during inference to adapt to out-of-distribution instances. How does the proposed approach impact generalization?

Could the authors compare against non-direct NCO approaches?

Could the authors explain what the self-labelling method used to replace SIPG mean in more detail? How does it use the found improved solution for supervision? It is not clear whether this just removes distance criteria or change the supervision completely. I think an experiment matching the claims should only remove MMD term from equation 6 (set lambda to 0) and leave everything else the same.

Could you give more details about pointwise regression ablation? Do you use the standardized scores? What are the targets? A more standard loss would be to applying sigmoid to individual variables and use cross entropy.

Could the authors clarify how many test and training examples are there for each dataset? The appendix mentions 500 test instances but not how many training examples were used or how long the training takes? Mentioning these as one sentence in main text would help readers.

Does BOLT generate different solutions for different seeds? Could authors measure and report variance among generated solutions for different seeds.

Did the authors analyze the training dynamics? Is learning stable or sensitive to the hyperparameters like K, L, F and lambda?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.