- 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
-
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 ? 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.
-
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?
-
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?
-
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).