Boosting Generalization in Diffusion-Based Neural Combinatorial Solver via Energy-guided Sampling

Haoyu LEI, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, Farzan Farnia · 2025

Read Boosting Generalization in Diffusion-Based Neural Combinatorial Solver via Energy-guided Sampling by Haoyu LEI, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, Farzan Farnia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12188.txt.

Introduction

Haoyu Lei and co-authors present a 2025 method that lets a diffusion-based puzzle solver jump to new puzzles without retraining. Such solvers learn to grow answers step by step and shine on hard routing tasks. But they tend to fail when the puzzle type or size shifts, and retraining costs dearly. The new frame steers the solver at run time with an energy guide, a nudge toward low-cost answers.

Theory in the paper backs the hope that skill can cross puzzles this way. A solver trained only on the classic traveling salesman task held its own on prize-collecting and orienteering kin, at fresh sizes, with no new training. Run-time steering could make one solver serve many routing jobs. The trick borrows from guided image models, now at work on discrete tasks.

Catalog record

CREATORHaoyu LEI, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, Farzan Farnia
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12188

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Boosting Generalization in Diffusion-Based Neural Combinatorial Solver via Energy-guided Sampling Haoyu LEI, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, Farzan Farnia Abstract Diffusion-based Neural Combinatorial Optimization (NCO) has demonstrated effectiveness in solving NP-complete (NPC) problems by learning discrete diffusion models for solution generation, eliminating hand-crafted domain knowledge. Despite their success, existing NCO methods face significant challenges in both cross-scale and cross-problem generalization, and high training costs compared to traditional solvers. While recent studies have introduced training-free guidance approaches that leverage pre-defined guidance functions for zero-shot conditional generation, such methodologies have not been extensively explored in combinatorial optimization. To bridge this gap, we propose a general energy-guided sampling framework during inference time that enhances both the cross-scale and cross-problem generalization capabilities of diffusion-based NCO solvers without requiring additional training. We provide theoretical analysis that helps understanding the cross-problem transfer capability. Our experimental results demonstrate that a diffusion solver, trained exclusively on the Traveling Salesman Problem (TSP), can achieve competitive zero-shot solution generation on TSP variants, such as Prize Collecting TSP (PCTSP) and the Orienteering Problem (OP), through energy-guided sampling across different problem scales. 1 Introduction Figure 1: Overview of energy-guided sampling framework for achieving cross-problem generalization. Left: Pre-trained diffusion model performs denoising on original problem G (TSP). Right: Proposed energy-guided sampling on target problem G^{\prime} (PCTSP) conducts K rewrite iterations of noise addition and guided denoising. Combinatorial optimization (CO) problems are fundamental challenges across numerous domains, from logistics and supply chain management to network design and resource allocation. While traditional exact solvers and heuristic methods have been widely studied, they often struggle with scalability and require significant domain expertise to design problem-specific algorithms [ 1 , 2 ] . Recent advances in deep learning have sparked interest in Neural Combinatorial Optimization (NCO), which aims to learn reusable solving strategies directly from data, eliminating the need for hand-crafted heuristics [ 3 ] . Among various deep learning approaches, diffusion-based models [ 4 , 5 ] have emerged as a particularly promising direction for solving combinatorial optimization problems. These models have demonstrated remarkable capabilities in learning complex solution distributions by adapting discrete diffusion processes to graph structures. Recent works like [ 6 , 7 ] have achieved state-of-the-art performance on classical problems such as the Traveling Salesman Problem (TSP), showcasing the potential of diffusion-based approaches in combinatorial optimization. However, the practical applicability of existing NCO approaches is limited by several generalization challenges. First, current models suffer from cross-scale generalization, with performance degrading significantly when applied to larger problem instances than those seen during training, especially for auto-regression-based solvers [ 8 , 9 ] including transformer and reinforcement learning methods. Second, these models show limited cross-problem transfer capabilities, struggling to adapt to problem variants with modified objectives or additional constraints. While several studies have attempted to enhance learning-based solvers’ generalization through approaches such as training additional networks [ 10 ] and fine-tuning [ 11 ] , these methods require substantial computational costs for training separate models for each problem type and scale. In parallel, recent advances in diffusion models, particularly in computer vision, have demonstrated the effectiveness of training-free guidance approaches for enhancing conditional generation [ 12 , 13 , 14 , 15 ] . These approaches leverage pre-defined guidance functions or pre-trained networks to enable zero-shot conditional generation without additional training overhead. Inspired by these developments, we explore the adaptation of energy-based guidance to address the generalization challenges in combinatorial optimization. In this work, we propose an energy-guided sampling framework (Figure 1 ) that enhances the generalization capabilities of diffusion-based NCO solvers without requiring additional training costs. By incorporating problem-specific objectives and constraints during inference time, this approach enables zero-shot cross-problem transfer while maintaining solution feasibility. We conduct theoretical analysis that deepen our understanding on the problem transfer capability of the energy-guided sampling framework. Through experimental evaluation of the TSP-trained diffusion model on more complex variants, the Prize Collecting TSP (PCTSP) and the Orienteering Problem (OP), we empirically demonstrate its effective zero-shot transferability across problem classes of increasing complexity, while maintaining consistent performance across different problem scales. Our work represents a significant step toward more flexible and generalizable diffusion-based combinatorial optimization solvers, potentially reducing the need for problem-specific model training while maintaining competitive performance. 2 Related Works Neural Network-based Combinatorial Solvers. Neural Combinatorial Optimization (NCO) approaches focus on leveraging neural networks to learn feasible solution distributions for combinatorial optimization problems [ 3 , 16 ] . Autoregressive construction solvers [ 8 , 9 , 17 , 18 , 19 ] are built upon the success of transformer-based [ 20 ] and reinforcement learning architectures in sequential generation tasks. However, non-autoregressive construction solvers [ 21 , 22 , 23 , 10 , 6 , 24 ] have also been proposed to learn high-quality solution distributions. Diffusion-based Generative Modeling. Recent advances in generative modeling have revolutionized various domains through diverse approaches, including Variational Autoencoders (VAE) [ 25 ] , Generative Adversarial Networks (GAN) [ 26 ] , Diffusion models [ 4 ] , and GFlowNet [ 27 ] . In particular, score-based diffusion models [ 4 , 5 , 28 , 29 , 30 ] have emerged as a powerful framework operating in continuous domains. Beyond their state-of-the-art performance in traditional generative tasks, these models have shown remarkable potential in combinatorial optimization (CO). Pioneering work by [ 6 ] established new state-of-the-art results for the Traveling Salesman Problem (TSP) by adapting discrete diffusion models [ 31 ] to graph structures. Building upon this foundation, [ 7 ] enhanced the framework’s performance through gradient search iterations during testing. [ 24 ] proposed the first diffusion-based unsupervised learning framework. Training-free Guidance for Diffusion Models. Conditional generation has emerged as a crucial component in real-world applications, enabling precise control over generated outputs. While traditional approaches such as classifier guidance [ 30 ] and classifier-free guidance [ 32 ] have proven effective, they require substantial computational overhead due to additional training requirements for either the classifier or the diffusion model. A promising alternative has emerged through training-free guidance methods [ 12 , 13 , 14 , 15 ] , which are guided by pre-trained networks or loss functions. In the context of discrete diffusion models, this approach remained largely unexplored until [ 7 ] pioneered the adaptation of loss-based guidance during inference, building upon the pre-trained discrete diffusion solver framework [ 6 ] . Our work demonstrates the significant potential of energy-guided sampling in enhancing the cross-problem generalization capabilities of diffusion-based NCO solvers. 3 Preliminaries 3.1 Variants of the Traveling Salesman Problem • Traveling Salesman Problem (TSP) requires finding the minimal-length Hamiltonian cycle in a complete graph, where the salesman must visit each city exactly once before returning to the starting point. • Prize Collecting TSP (PCTSP) [ 33 ] extends the classical TSP by introducing node-specific prizes and penalties. The objective is to optimize a trade-off between minimizing tour length and unvisited node penalties while ensuring collected prizes exceed a predefined threshold. This formulation creates a more complex optimization landscape where node visitation decisions must balance multiple competing factors. • The Orienteering Problem (OP) , first introduced by [ 34 ] , is a fundamental combinatorial optimization problem with widespread applications in real-world scenarios. In the OP, each node

Read the complete text