Metraipolis › archive › dc_7fb5eca3b8d6

Parallel Tempering for Diffusion-Based Combinatorial Optimization — arXiv:2609.37323

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.37323
License (as archived)
CC0-1.0
Archived
2026-10-07T17:31:00.634Z
SHA-256 of the archived text
ccec08380958d41c8eef00125ca8696f8341c92bfa954f10d149c7c86f1fe6d4
Stable URL of this page
https://metraipolis.com/documento/dc_7fb5eca3b8d6

How to cite

Parallel Tempering for Diffusion-Based Combinatorial Optimization — arXiv:2609.37323 — arXiv (en), https://arxiv.org/abs/2609.37323 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7fb5eca3b8d6 (Metraipolis archive dc_7fb5eca3b8d6, sha256 ccec08380958d41c8eef00125ca8696f8341c92bfa954f10d149c7c86f1fe6d4)
BibTeX
@misc{dc7fb5eca3b8d6,
  title = {Parallel Tempering for Diffusion-Based Combinatorial Optimization — arXiv:2609.37323},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.37323},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7fb5eca3b8d6; sha256 ccec08380958d41c8eef00125ca8696f8341c92bfa954f10d149c7c86f1fe6d4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37323. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-30 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.37323 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T16:59:48.315Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).