SeqDiCO: Sequence-oriented Diffusion for Scale-Generalizable Neural Combinatorial Optimization

Diffusion-based neural combinatorial optimization (NCO) has recently shown promise for routing problems by generating solutions through denoising or reconstruction. Most existing diffusion solvers, however, define the generative process over full-instance solution structures, such as adjacency matrices or heatmaps. This instance-level formulation ties the learned reconstruction distribution to the problem size observed during training, making it difficult to transfer models trained on small instances to substantially larger ones. In this paper, we propose SeqDiCO, a sequence-oriented diffusion framework for scale-generalizable neural combinatorial optimization. The key idea is to move diffusion from full-instance solutions to fixed-endpoint sequence subproblems. Given two endpoints and a set of intermediate nodes, SeqDiCO learns a local denoising operator that reconstructs the open path connecting the endpoints from corrupted structural observations. Since such local sequence patterns are reusable across instance sizes, the same operator trained on small instances can be repeatedly composed to solve larger routing problems. During inference, SeqDiCO uses this operator for both construction, by growing a solution through receding-horizon local reconstruction, and refinement, by replacing selected subpaths in an existing solution. Experiments on TSP and CVRP show that SeqDiCO consistently outperforms representative diffusion-based and autoregressive neural solvers under cross-scale evaluation. Trained only on 100-node instances, SeqDiCO generalizes to 10K-node problems, reducing the optimality gap by up to 51\% over SOTA neural solvers, while achieving up to $10\times$ faster inference on representative large-scale benchmarks.