Learning a Diffusion-Native Latent Space for Neural Combinatorial Optimization

Diffusion-based neural combinatorial optimization requires specifying how combinatorial solutions should be corrupted and subsequently denoised. Generic variable-wise noise ignores the structured geometry of feasible solutions, while search-oriented methods rely on task-specific perturbations such as masking or local-search moves, which can also be difficult to define when solutions lack a meaningful notion of perturbation. We instead learn a targeted space in which diffusion should operate. We introduce LCO-Diff, which uses an instance-conditioned variational autoencoder to transform discrete combinatorial solutions into a diffusion-native latent space. The latent representation is trained to remain sufficient for reconstructing the solution while being regularized toward a Gaussian geometry, so that standard continuous transport becomes native to the learned solution representation rather than being imposed on the original discrete space. In this latent space, we train an instance-conditioned rectified-flow model using a canonical Gaussian interpolation, yielding the same generative dynamics across different combinatorial problem classes. Denoised latents are decoded into solution scores and converted into feasible solutions via constraint-aware decoding and repair. The learned latent geometry also turns the training-time diffusion process into a natural test-time search mechanism. A candidate solution can be re-encoded into the latent space, partially renoised along the same Gaussian path used during training, and denoised again to generate improved candidates, without introducing a separate solution-space perturbation operator. Across problem sizes and inference budgets, our latent-space diffusion achieves state-of-the-art solution quality at low sampling cost and improves further with renoise-based test-time scaling.