acceptodds
Under review as a conference paper at ICLR 2027

Monte Carlo Tree Diffusion for Combinatorial Optimization

Abstract

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.

Primary area:
generative models
Keywords:
Diffusion model, Combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_vfxxOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies diffusion models for combinatorial optimization without supervision from high-quality solver-generated solutions. Alignment is challenging when objective gradients are unavailable or guidance incurs substantial computational cost. The paper combines lookahead planning with MCTS-based sampling and incorporates this alignment approach into training. It evaluates the method on several classical combinatorial optimization problems.

Critical strengths
  • The writing is direct and fluent. I particularly appreciate the transparent reporting of cases where the method underperforms stronger baselines on MIS.

  • The ablations examine several major components and provide evidence that both search and the auxiliary loss improve performance.

  • The method accommodates objective feedback that becomes available only after decoding. It trains the value network using rewards from decoded solutions, without requiring the search to differentiate through the discrete objective or decoding procedure. This has practical value in the considered setting.

Critical weaknesses
  • The motivation for using generative models to solve these combinatorial optimization problems, and the advantages of this design choice, are not sufficiently clear to me.

  • The learned outcome network introduces additional complexity, and training it may be challenging. The rationale for using it within tree search, rather than directly optimizing the learned value function, needs clarification.

  • The existing CAM auxiliary loss contributes to the reported gains. However, the independent contribution of tree search and the precise implementation of the training procedure still need clarification.

  • Combining diffusion models with MCTS, guiding sampling with learned values, and avoiding objective gradients are not individually novel contributions.

  • The core search relies on intermediate-state value estimates, but direct evidence of their reliability is missing. The same outcome network performs both candidate selection and node evaluation. The paper does not report its ranking accuracy across noise levels or analyze how estimation bias affects search.

Overall, I remain unconvinced by the problem motivation and the fit between the method and the problem. The novelty of the individual components appears limited, and I do not see a clear insight.

Questions for authors
  1. IRED[1] learns annealed energy landscapes and improves reasoning by increasing test-time optimization steps. VFScale [2] further uses intrinsic model energy to evaluate candidates and guide tree search. Compared with these approaches that unify generation and evaluation, why does this method train a separate outcome network VϕV_\phi? A non-differentiable combinatorial objective does not preclude learning a differentiable energy surrogate. Is the main obstacle the lack of high-quality solution labels, the discrete diffusion parameterization, or the distinction between evaluating a current state and predicting eventual solution quality? Please clarify the advantages and applicable conditions of a separate value network relative to intrinsic energy-based evaluation.

  2. Can the value network reliably identify which of two candidates is more promising for further exploration? Beyond improvements in final solutions, is there evidence that its candidate rankings are informative at intermediate selection steps?

  3. How much do the proposed designs contribute beyond a direct combination of existing mechanisms? Please clarify their differences from, and connections to, previous work on diffusion models with MCTS, learned value-guided sampling, and guidance without objective gradients. For closely related approaches not included in the experiments, why were they not used as baselines?

  4. Does the choice of candidate values for the selection temperature affect performance? If so, why?

[1] Du, Y., Mao, J., & Tenenbaum, J. B. (2024). Learning iterative reasoning through energy diffusion. arXiv preprint arXiv:2406.11179.

[2] Zhang, T., Pan, J. S., Feng, R., & Wu, T. (2026, April). VFScale: Intrinsic reasoning through verifier-free test-time scalable diffusion model. In International Conference on Learning Representations (Vol. 2026, pp. 59758-59787).

Reviewer_KzSeOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The authors propose Monte Carlo Tree Diffusion for Combinatorial Optimization. It applies inference-time alignment to combinatorial optimization (CO), a setting where gradient-based guidance is hard to provide. The prior Monte Carlo Tree Diffusion (MCTD) [1] runs its tree search over different levels of guidance. This work instead searches through value-based diffusion alignment. It also uses a learned value function in the simulation phase in place of fast rollouts, which makes the search more efficient. The samples found by the search are then used for training, so the model learns from higher-quality solutions. With these components, the method outperforms existing diffusion-based CO methods that do not use inference-time alignment.

[1] Yoon, Jaesik, et al. "Monte carlo tree diffusion for system 2 planning." ICML 2025.

Critical strengths
  1. This paper proposes a new inference-time adaptation framework for diffusion models in combinatorial optimization.
  2. Samples obtained through search are reused for training, so the model can learn from better solutions.
  3. The evaluation step (the simulation phase in MCTS) uses a learned value function instead of rollouts, which makes the search more efficient.
  4. The experimental setup appears reproducible.
Critical weaknesses
  1. Insufficient attribution to prior work and an overlapping method name.
    “Monte Carlo Tree Diffusion” is already an established term in the literature [1]. The paper uses this exact name for its own method without stating that it comes from prior work, and it does not introduce a distinct name such as “MCTD-CO.” The proposed framework is also very similar to the original MCTD in two ways:

    • its action design for balancing exploration and exploitation
    • its architecture, which integrates tree search into the denoising process (cf. Figure 1 in [1])

    Despite this, the paper does not say which parts are inspired by or adopted from the earlier work. The authors should discuss the original MCTD clearly, position their contribution relative to it, and use a distinct name for their method.

  2. The paper is hard to follow.

    • Diffusion-based CO methods differ substantially from standard uses of diffusion models such as image generation. The paper only introduces them briefly in Section 3.1, which makes the rest of the paper hard to understand.
    • The paper does not describe how the proposed model is trained. For example, it appears to rely on PPO but does not say so.
    • The experiments report “Ours” and “Ours + MCTD sampling” separately, but the difference between these two settings is not explained.
  3. The experiments do not clearly show that the search is effective.
    With search, the method does generally outperform the methods without it (e.g., Ours, SDDS, CAM), but the margins are small and the inference time grows substantially. Performance seems to be close to saturation already in these settings, so they are not well suited to showing the benefit of search. Harder settings, where the base model leaves more room for improvement, would make the case more convincing.

Questions for authors
  1. Which values of α did you use in the experiments? Was it only 1 and 100, as in Figure 1? If so, would a more diverse set of α values help? A wider range would expand the search space and might make the search more efficient.
  2. Did you run any experiments where the evaluation phase ((3) in Figure 1) measures value through actual denoising instead of the learned value function? That comparison would show how much the value function approximation costs or saves.
  3. How accurate is the learned value function? Did you check how well its predictions match the true objective values?
Reviewer_k85xOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

MCTD tries to solve the suboptimality of unsupervised diffusion solvers for combinatorial optimization by casting diffusion guidance as sequential decision-making over denoising trajectories, using a learned outcome network to reweight candidate states according to a selection temperature that serves as a derivative-free analogue of a guidance scale. The contributions include, a derivative-free formulation of tree-search diffusion alignment in which search actions control the selection temperature of value-weighted resampling; a rollout-free search procedure that evaluates intermediate diffusion states with a single forward pass; a training-time alignment framework that converts tree-guided exploration into a learning signal. Across TSP, CVRP, STP, and MIS, MCTD consistently improves the unsupervised diffusion solver on which it is built in eleven evaluated settings at matched inference cost, outperforms prior unsupervised baselines on TSP, CVRP, and STP, and remains competitive with supervised solvers.

Critical strengths

The method design is reasonable and complete. The combination of value function guidance, temperature actions, MCTS, PPO trajectory weighting, and CAM is well justified. The components are self-consistent and well-motivated. The experiments cover four problems and eleven settings, with sufficient ablation studies. The method avoids the non-differentiability of CO objectives, and node evaluation requires only a single forward pass, making tree search cheap enough to run inside the training loop. It is competitive with supervised solvers. On TSP-1000, it surpasses DIFUSCO without using any solver-generated labels.

Critical weaknesses

Gains depend on the base solver having headroom. On MIS, the base solver is already near saturation, so the value function has little residual signal and reweighting has little to improve. On RB-large, MCTD performs worse than the simpler CAM (4.40% vs. 5.32%). The authors list this as a limitation, but it makes the method losing on saturated problems.

Tree search is not fully parallelizable, which restricts its application to instances with millions of variables.

Many components and complex tuning. CAM, MCTD, and trajectory weighting are ``critical'', which implies sensitivity to hyperparameters and training stability. Please discuss the robustness and dependence on parameters.

Time gains vary largely among scales. It is 5.6× on TSP-500 but only 1.4× on TSP-1000

Questions for authors

See above in Weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.