acceptodds
Under review as a conference paper at ICLR 2027

CCTC: Constructive–Corrective Transition Calibration for Unsupervised Combinatorial Optimization

Abstract

Diffusion models have recently shown promise for unsupervised combinatorial optimization (CO), learning to generate high-quality solutions without labeled optimal solutions. However, we find that their training signals can exhibit substantially different discriminative quality across transition directions, a phenomenon we term Constructive-Corrective Transition Asymmetry. Specifically, learned policies exhibit substantially weaker target-conditioned discrimination for constructive transitions than for corrective ones, which our analysis relates to a directional scale asymmetry in the underlying transition signals. These findings highlight a gap between effective trajectory-level credit assignment and discriminative transition-level supervision. To address this problem, we propose Constructive-Corrective Transition Calibration (CCTC), which calibrates transition-level supervision according to signal magnitude and transition direction. CCTC combines bounded calibration with direction-conditioned weighting to selectively strengthen target-favored constructive transitions. Experiments on four node- and edge-selection CO problems across eight settings show that CCTC consistently outperforms existing unsupervised state-of-the-art methods while achieving stronger constructive transition discrimination.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Unsupervised Combinatorial Optimization, Diffusion Models, Transition Calibration

Reviews

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

This paper propose a method called Constructive-Corrective Transition Calibration (CCTC) to improve diffusion-based method for CO. The authors observe that the model can become too reluctant to add nodes or edges while building a solution. They then propose CCTC, which limits large training signals and gives more weight to useful additions. The method changes only training and reports improvements on MIS, Max-Cut, TSP, and CVRP.

Critical strengths

The paper identifies a concrete training problem and provides useful diagnostics. Examining individual transitions offers insight into training behavior that final solution quality alone does not reveal.

The proposed fix is simple and practical. It retains CAM’s architecture and sampling procedure, adds no inference-time operations, and improves the reported results across several optimization tasks.

Critical weaknesses
  1. The reliability of the improvements is unclear. Some gains are small, such as reducing TSP-500 tour length from 16.91 to 16.89, but the main results do not report variation across training seeds. The component ablation also uses only one run per setting. The additional CAM runs demonstrate that the training problem can recur, but do not establish that CCTC consistently resolves it.

  2. The motivation and comparisons need strengthening. The paper should better explain the practical advantages of diffusion for combinatorial optimization and why this framework’s training limitations are worth addressing? why we want to use diffusion model for CO?

  3. Its broad performance claims are not sufficiently supported by comparisons with relevant non-diffusion methods, such as UTSP/ATT-GCN for TSP. Reinforcement-learning methods are also grouped under “UL” without clearly explaining the distinction.

Questions for authors
  1. How does CCTC compare with simpler alternatives, such as clipping, normalization, or giving more weight to all useful transitions rather than only useful additions?

  2. Some baseline results appear substantially different from those reported in the original papers. Could you explain these differences and rerun the relevant baselines on the same hardware with matched settings to ensure a fair comparison of solution quality and runtime?

  3. What practical advantages motivate using diffusion for these tasks? How does CCTC compare with relevant non-diffusion methods, including UTSP and ATT-GCN, under comparable inference budgets?

  4. Given the cost of multi-step diffusion sampling, what advantages does diffusion over search-based methods?

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

This paper examines the gap between trajectory-level credit assignment and individual transition discrimination in unsupervised diffusion models for combinatorial optimization. Building on CAM, the authors derive an asymmetry in supervision magnitude between constructive and corrective transitions for MIS and investigate its training behavior through direction-conditioned discrimination, constructive activity, and validation solution quality. The proposed CCTC calibrates training supervision using a bounded signal transformation and selective weighting of target-favored constructive transitions, without changing the architecture or inference procedure. CCTC outperforms CAM across eight settings covering four problems, with additional component ablations, hyperparameter sensitivity analysis, and size generalization results. The mechanistic evidence is strongest for MIS, while the other tasks primarily establish improvements in final solution quality.

Critical strengths
  • Equations (7)–(9) connect the MIS constraint penalty to direction-dependent supervision magnitudes. Figures 1, 2, and 4 link this asymmetry to policy discrimination and training behavior, providing insight beyond an empirical loss modification.
  • CCTC improves upon CAM across all eight settings under the same inference procedures and task-specific budgets, including size generalization. Component ablations support its practical value, although some gains are small.
Critical weaknesses
  • Detailed mechanistic validation is concentrated on MIS. The encoding symmetry of Max-Cut and the bounded probabilistic targets in edge-selection tasks limit the transfer of this explanation. Cross-task effectiveness does not establish a shared mechanism.
  • Comparisons against ordinary scaling, target smoothing, and direction-independent weighting are missing. Policy-dependent diagnostic state distributions complicate attribution, and Figure 6 lacks a CAM continuation baseline with the same training budget.
Questions for authors
  • What thresholds, sampling procedures, and aggregation rules are used in Equation (10) and Figure 1(c)? Does CCTC retain stronger constructive discrimination when evaluated on the same fixed set of states?
  • Are the edge-selection targets q_{t,e} binary? If so, how can the benefits of target smoothing in Equation (16) be distinguished from those of direction-conditioned calibration? What task-specific rationale supports selectively strengthening (0->1) transitions in Max-Cut?
  • Are there targeted comparisons against ordinary normalization, direction-independent weighting of target-favored transitions, or standard target smoothing that establish the need for direction conditioning?
  • What happens if CAM is continued with the same optimizer reset, learning-rate schedule, and additional training budget used in Figure 6? Could the current conclusion be limited to demonstrating the feasibility of continued training?
1 comment

Thank the authors for their detailed response and clarifications. Having carefully read the rebuttal and the other reviews, I maintain my current rating of weak acceptance.

Reviewer_XynrOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies a failure mode in CAM, an unsupervised diffusion solver for combinatorial optimization: the supervision can favor removing selected variables much more strongly than adding useful ones. For MIS, the authors derive a signed transition signal showing that encouragement for additions is bounded, while suppression grows with the number of conflicts. They connect this imbalance to weak discrimination between favored and suppressed additions, and in some training runs to nearly vanishing constructive activity. CCTC modifies the training supervision using a tanh transformation and extra weight on target-favored constructive transitions. It uses a signed matching loss for node-selection problems and weighted binary cross-entropy with transformed targets for routing problems. The architecture and inference procedure remain those of CAM. Experiments report improvements over CAM on four MIS settings, Max-Cut, two TSP sizes, and CVRP, with component ablations and training diagnostics concentrated on MIS ER-[700–800].

Critical strengths

The strongest part of the paper is the concrete diagnosis on MIS. The authors identify a specific imbalance in the training signal, measure transition discrimination and activity separately, and show how these quantities evolve alongside validation quality. Appendix D goes beyond a single illustrative failure by examining five CAM runs and acknowledging recovery. This gives the proposed modification a more substantive motivation than simply observing that a different loss works better.

The modification is also simple and potentially useful in practice. CCTC retains CAM’s sampling procedure and decoder, and the comparisons use the same task-specific inference budgets for diffusion methods. The reported gains cover all eight settings, including direct generalization from ER graphs with 700–800 nodes to graphs with 9,000–11,000 nodes, where the independent-set size improves from 384.38 to 388.88. A training-only change that improves solution quality without adding inference operations would be valuable if these gains are reproducible.

Critical weaknesses

My main concern is that the experiments do not establish how reliably CCTC improves over a well-tuned CAM baseline. Tables 1–4 give point estimates without variation across training seeds, while the component ablation explicitly uses one trajectory per configuration. Several differences are small: 19.91 to 19.92 on MIS RB-[200–300], 16.91 to 16.89 on TSP-500, and 23.70 to 23.65 on TSP-1000. The five-seed study documents instability in CAM, but does not provide a matched five-seed comparison with CCTC. The continued-training experiment also changes the loss while resetting the optimizer and scheduler and adding training, without a CAM continuation under the same conditions. Because tanh changes the matching signal’s scale relative to the fixed entropy and transition-rate terms, a CAM control with a tuned matching coefficient or regularization strength would help distinguish directional calibration from a more general change in loss balance. These controls are consequential because the method’s main contribution is an incremental training modification, so its value depends on robust improvements over simpler alternatives.

My second concern is the gap between the MIS explanation and the claimed applicability across problem classes. The conflict-amplified signed signal gives a clear motivation for MIS, but the routing target q is already bounded in [0,1], and its BCE logit gradient p−q is already bounded even before calibration. At γ=1, Eq. 16 maps q=0 and q=1 to approximately 0.119 and 0.881, respectively. That operation softens extreme targets; it does not bound an otherwise unbounded routing gradient. The paper should explain why this target transformation addresses the same directional problem and compare it with ordinary target smoothing. Max-Cut raises a related conceptual question: replacing every bit by its complement leaves the cut value unchanged but exchanges the labels “constructive” and “corrective.” Giving extra weight specifically to 0→1 transitions therefore depends on the encoding. This does not make the method invalid, but it weakens the interpretation that additions are intrinsically under-supervised across all these tasks. Evidence beyond MIS, together with controls that amplify all favored transitions or reverse the preferred direction, would materially strengthen the central claim.

Questions for authors

Could you report matched CAM and CCTC results across multiple training seeds, with variation in the final test objectives and the same validation-based checkpoint-selection rule? I would particularly like to know whether the small RB-[200–300] and TSP improvements persist across runs. For the continuation result in Fig. 6, how much improvement comes from continuing CAM itself with the same optimizer reset, scheduler reset, and additional training budget? These are requests to establish the robustness of the current claims.

Could you make the construction of the edge target q explicit and show whether TSP or CVRP exhibits the directional discrimination problem before applying CCTC? A comparison with ordinary target smoothing would help explain what Eq. 16 contributes beyond softening the targets. For Max-Cut, does the improvement persist when the binary encoding is complemented or when the extra weight is placed on favored 1→0 transitions instead? I am asking because these results could change my assessment of whether the proposed mechanism generalizes beyond MIS.

Finally, can the improvement on MIS be separated from a change in the matching-to-regularization balance by comparing with CAM using a tuned matching scale and a simple clipped-signal baseline? Please also specify η and the population over which the transition diagnostics are averaged. These clarifications would make it easier to judge whether the measured discrimination improvement supports the intended explanation.

Comments on the paper

1 comment
Area_Chair_kJihOpenReview ↗

Author-Reviewer discussion reminder

Dear Reviewers,

Please spend some time reading the rebuttal and indicate whether the authors have clarified your concerns. Please do so before Nov 18 AoE to give the authors the chance to further clarify.

Best,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.