[
    {
        "id": "osp-21788",
        "type": "article-journal",
        "title": "Parallel Tempering for Diffusion-Based Combinatorial Optimization",
        "author": [
            {
                "family": "Mielke",
                "given": "Arman"
            },
            {
                "family": "Bauknecht",
                "given": "Uwe"
            },
            {
                "family": "Strauss",
                "given": "Thilo"
            },
            {
                "family": "Niepert",
                "given": "Mathias"
            }
        ],
        "URL": "https://omanscience.com/en/articles/parallel-tempering-for-diffusion-based-combinatorial-optimization",
        "language": "en",
        "issued": {
            "date-parts": [
                [
                    2026
                ]
            ]
        },
        "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."
    }
]