analiza aiqbench
This research introduces PT-Denoise, an inference-time technique that leverages parallel tempering to enhance discrete diffusion models for combinatorial optimization on graphs. By enabling concurrent denoising trajectories to swap temperatures based on performance, the method dynamically reallocates sampling resources without requiring model retraining. The approach consistently improves solution quality while maintaining minimal computational overhead compared to standard independent sampling strategies.
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.
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.
Machine Learning (cs.LG)
arXiv:2609.37323 [cs.LG]
(or arXiv:2609.37323v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.37323 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 242 cuvinte
Subiecte conexe
Compute Time Scaling with Recursive Models for Combinatorial Optimization
arXiv · 30 sept. 2026
Certifying RBMs Cut NPA Hierarchy Optimization Costs by 100×
Quantum Zeitgeist · 24 iul. 2026
Moment Optimization in the Navascu\'es-Pironio-Ac\'in Hierarchy
arXiv · 9 oct. 2026
Explore Broadly, Reason Sharply: Push Small Models toward the Frontier via Sampling
arXiv · 30 sept. 2026