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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Mielke, A., Bauknecht, U., Strauss, T., & Niepert, M. (2026). Parallel Tempering for Diffusion-Based Combinatorial Optimization. https://omanscience.com/en/articles/parallel-tempering-for-diffusion-based-combinatorial-optimization
MLA 9
Mielke, Arman, et al. "Parallel Tempering for Diffusion-Based Combinatorial Optimization." https://omanscience.com/en/articles/parallel-tempering-for-diffusion-based-combinatorial-optimization.
Chicago (author–date)
Mielke, Arman, Uwe Bauknecht, Thilo Strauss, and Mathias Niepert. 2026. "Parallel Tempering for Diffusion-Based Combinatorial Optimization." https://omanscience.com/en/articles/parallel-tempering-for-diffusion-based-combinatorial-optimization.
Harvard
Mielke, A., Bauknecht, U., Strauss, T. and Niepert, M. (2026) 'Parallel Tempering for Diffusion-Based Combinatorial Optimization', Available at: https://omanscience.com/en/articles/parallel-tempering-for-diffusion-based-combinatorial-optimization.
Vancouver
Mielke A, Bauknecht U, Strauss T, Niepert M. Parallel Tempering for Diffusion-Based Combinatorial Optimization. https://omanscience.com/en/articles/parallel-tempering-for-diffusion-based-combinatorial-optimization
IEEE
A. Mielke, U. Bauknecht, T. Strauss, and M. Niepert, "Parallel Tempering for Diffusion-Based Combinatorial Optimization," https://omanscience.com/en/articles/parallel-tempering-for-diffusion-based-combinatorial-optimization.