Parallel Tempering for Diffusion-Based Combinatorial Optimization

arXiv:2609.37323v1 Announce Type: new Abstract: Discrete diffusion models have emerged as a powerful paradigm for solving combinatorial optimization (CO) problems on graphs by learning to sample high-quality solutions. A common inference-time approach is to generate multiple candidate solutions independently and return the best-performing sample, improving solution quality at the expense of an increase in computational cost. In this work, we introduce PT-Denoise, an inference-time procedure that allows these concurrent denoising trajectories to interact through parallel tempering, without requiring retraining or fine-tuning of the underlying denoiser. Our method assigns a temperature to each diffusion process and allows processes to swap temperatures based on their relative performance. This dynamically reallocates promising, low-energy trajectories to colder, more concentrated sampling regimes while allowing higher-energy states to escape local minima through randomized exploration. Experiments on canonical graph-structured CO problems show that our approach consistently improves the quality of the best solution found, while only adding minimal computational overhead.

Related

• Tensor Train Diffusion: Leveraging Low-Rank Structures for High-Dimensional Score-Based Sampling
• Solving Integer Linear Programming with Parallel Tempering
• Learning Discrete Diffusion of Graphs via Free-Energy Gradient Flows
• Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion

Source: arXiv cs.LG | 2026-09-30