Monte Carlo Tree Diffusion for Combinatorial Optimization

Diffusion-based methods have recently shown great promise in solving combinatorial optimization (CO) problems, but reaching high solution quality typically requires aligning the denoising process with the optimization objective. Existing inference-time alignment approaches rely primarily on gradient-based guidance. However, such methods are inherently limited: they require differentiable energy functions, which are often unavailable or difficult to construct for general CO problems. We therefore propose Monte Carlo Tree Diffusion for Combinatorial Optimization. Instead of relying on gradient information, our method performs look-ahead planning using value function evaluations that estimate the quality of future denoising outcomes, with a selection temperature controlling how strongly these estimates steer sampling. Treating the temperature as the search action, our method integrates Monte Carlo tree search into the denoising procedure, enabling adaptive exploration and recovery from suboptimal intermediate decisions under high noise levels. Beyond inference-time alignment, we incorporate this alignment method into training through trajectory-level weighting and auxiliary objectives, improving the base diffusion model without additional inference cost. Experiments on four standard CO benchmarks show that our method improves the unsupervised diffusion solver it builds on in every setting tested, outperforms prior unsupervised baselines on TSP, CVRP and STP, and is competitive with supervised approaches; on MIS, where the base solver is already near saturation, the gains are smaller.