Bayesian Flow Networks for Combinatorial Optimization: An Edge-based Approach to the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a fundamental combinatorial optimization problem, and non-autoregressive generative models have recently demonstrated strong solving capabilities on this problem. Diffusion-based solvers generate tours by iteratively denoising sampled edge configurations, but they do not retain the probabilities of alternative edge selections as the state is progressively refined. However, many locally plausible edge selections in the TSP continue to compete before their global compatibility becomes clear, creating a need for a generation state that can explicitly represent and progressively update such uncertainty. To address this, we introduce Bayesian Flow Networks (BFNs), which use probabilistic beliefs over alternative edge selections as the generative state and progressively refine these beliefs during generation, and propose Edge-BFN (EBFN), a non-autoregressive solver operating in the edge space. EBFN continuously maintains probabilistic beliefs throughout the iterative process, allowing competing edge selections to be progressively distinguished as global information accumulates, and uses the beliefs to generate and select multiple candidate solutions. Experiments on multiple TSP benchmarks under different test-time search budgets show that EBFN achieves competitive results and outperforms recent diffusion-based solvers in some settings, suggesting that directly refining probabilistic confidence over edge selections holds substantial potential for exploring competing decision alternatives.