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

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.