acceptodds
Under review as a conference paper at ICLR 2027

DriftCO: A Drifting Model-Based Solver for Combinatorial Optimization

Abstract

Diffusion model-based solvers have recently achieved strong performance in neural combinatorial optimization (CO). They generate candidates through stochastic denoising trajectories, which can provide both strong solution quality and useful candidate diversity. This makes them well suited to best-of-many pipelines, where multiple candidates are locally improved and the best solution is retained. However, multi-step denoising introduces substantial per-candidate inference cost. Recent acceleration methods distill the trajectory into fewer steps or even a single step, but such distillation can weaken the candidate diversity needed for effective best-of-many search. To mitigate this issue, we propose DriftCO, a drifting model-based one-step CO solver that promotes candidate quality and diversity through a training-time attraction–repulsion mechanism, rather than through long inference-time denoising trajectories. This mechanism encourages the model to favor high-quality solution regions while avoiding collapse into redundant search neighborhoods, allowing DriftCO to generate diverse candidates with strong solution quality in one step at inference time. Experiments on the traveling salesman problem and maximum independent set across multiple problem sizes demonstrate the effectiveness of DriftCO.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural Combinatorial Optimization, Drifting Models, One-step Generation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_1rVNOpenReview ↗
Rating
2
Confidence
3(−1)
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes DriftCO, a one-step heatmap generator for graph-based combinatorial optimization. It adapts drifting-model training through graph-conditioned generation, single-reference attraction, and a cosine similarity kernel. Generated heatmaps are decoded and locally improved before best-of-many selection. Experiments on Euclidean TSP and MIS report quality-runtime trade-offs and zero-shot transfer to larger instances.

Critical strengths

This work presents a practically relevant adaptation of drifting models to neural combinatorial optimization. DriftCO promotes candidate diversity without requiring multiple annotated solutions per training instance. Its same-instance formulation provides a coherent interface between continuous generative training and graph-specific decision representations.

The paper provides a comprehensive review of related work and is generally clear and well presented. But I recommend adding an overview figure to illustrate the framework and clarify the training and inference pipelines.

Critical weaknesses
  1. The central claim of useful structural diversity is insufficiently established. Under single-reference supervision, the field reduces to the reference minus a kernel-weighted generated mean. Repulsion in unconstrained heatmap space can produce variation that leaves decoded solutions unchanged, including positive rescaling. Fig. 1 measures best-of-many gains, while the ablations report final quality; neither directly isolates structural diversity from candidate quality or local-search effects. This limits confidence in the mechanism underlying the paper’s main contribution.

  2. The superiority claims need stronger evaluation controls and uncertainty reporting. Candidate budgets differ across methods, and matched-time comparisons are absent. The closest MIS margins are small: 10.87% vs. 10.94% gap on ER, without repeated-run uncertainty. Furthermore, the approximately 5.5% RB gap in Figure 1 at six candidates is not reconciled with the 2.63% main-table result using the same stated candidate count. These issues affect confidence in the robustness and interpretation of the reported advantages.

  3. The applicability to more complex constrained CO problems remains unclear. Validation is limited to standard Euclidean TSP and MIS, while feasibility is handled through task-specific decoding. This limits the claimed generality of the approach and leaves unresolved whether its efficiency and useful candidate diversity would survive more demanding feasibility handling.

  4. The experimental reporting is insufficiently precise. Table 1 neither defines “attain the reference solution quality” nor reports the achieved objectives and gaps. Since the main contribution is a training method, scale-specific IID training and evaluation on TSP-500/1000 are also needed. Following the cited baselines, consistently reporting objective values, gaps (preferably with standard deviations), and end-to-end time per instance would be better.

Questions for authors
  1. Are heatmaps or drifting fields normalized, bounded, or otherwise stabilized beyond the stated equations? What prevents repulsion from primarily producing score variation that leaves decoded solutions unchanged?

  2. Under identical candidate and local-search budgets, does adding repulsion increase the number of distinct decoded solutions or reduce edge/node overlap? How do candidate quality and diversity change before and after local search?

  3. What explains DriftCO’s approximately 5.5% RB gap in Figure 1 with six candidates versus 2.63% in Table 3? Please specify the decoding, refinement, and local-search settings used in each experiment.

  4. What is the intended scope of DriftCO beyond TSP and MIS? e.g. for problems with capacity, time-window, or precedence constraints. What evidence or argument supports retaining the reported efficiency and diversity benefits once the required feasibility handling is included?

  5. What precisely constitutes “attaining the reference solution quality” in Table 1? Please report the achieved objective values and gaps alongside the timings. Further, how does DriftCO compare with the baselines under scale-specific IID training on TSP-500 and TSP-1000, using comparable training and evaluation settings? Please report objective, gap, variability, and end-to-end time per instance to establish the effectiveness of the proposed training method at these scales. Additional suggestion: Models trained at these larger scales could also be evaluated on still larger instances to complement the current cross-scale generalization study.

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

DriftCO addresses a common problem in diffusion-based combinatorial optimization (CO) solvers, whose inference requires many denoising steps and whose distillation to one-step generation tends to collapse candidate diversity, undermining best-of-many search.

The paper proposes the first (claimed to be) drifting-model-based CO solver, which learns one-step candidate generation through a training-time attraction–repulsion mechanism.

Critical strengths

The paper is useful in motivation, it identifies that one-step CO generation needs more than trajectory distillation, and its attraction–repulsion formulation is a principled way to inject diversity during training rather than at inference. The structural cosine kernel is a sensible design choice, with a direct connection to the Ochiai coefficient and thus to overlap between discrete solutions, and the ablation shows it outperforms Gaussian and Laplacian kernels across TSP and MIS. From experiments, it delivers efficient one-step inference (13 s on TSP-50, 38 s on TSP-100, 36 s on TSP-500, 157 s on TSP-1000) with good zero-shot cross-scale and cross-distribution generalization.

Critical weaknesses

The evaluation is somewhat weak.

E.g., the core diversity claim is validated mainly through the operational proxy of best-of-N improvement rather than a direct diversity metric, on relatively small settings (TSP-50/100, RB-[200–300]); the novelty rests almost entirely on the repulsion term and the cosine kernel, and the ablation gain from removing repulsion is minor; the method is also evaluated only on TSP and MIS, leaving routing problems with richer constraints untested, it is good to try other CO problems.

Questions for authors

See above, it is good to add some evaluations to support the claims.

Reviewer_1SYAOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes DriftCO, a one-step generative framework for CO problems. This method learns to generate candidate heatmaps by attracting them towards a high-quality reference and pushing similar candidates apart. The heatmaps are decoded into solutions and then refined by local search. Experiments on TSP and MIS problems show that DriftCO can produce competitive solutions within reduced inference time.

Critical strengths

The paper targets a concrete and meaningful problem, since iterative generation for CO problems could be computationally expensive. DriftCO achieves competitive results with relatively lower inference time on TSP&MIS problems in experiments, and the cross-scale and cross-distribution experiments also show that the learned model can be useful beyond its training setting.

Critical weaknesses

My main concern is the overall computational cost of the method. Though DriftCO reduces inference time, it's unclear whether it requires a much larger training cost compared to the main baselines. Since the framework generates multiple candidates for each instance during training, it may introduce substantial overhead.

Questions for authors
  1. Could the authors report the training time and GPU usage of DriftCO and the main baselines? In which usage settings would the inference time savings outweigh the additional training cost

  2. Could the authors explain how the sampling budgets in Table 2 were selected? A comparison with a matched number of candidates on TSP-500/1000 would clarify how much of the improvement comes from the learned generator and how much comes from evaluating more candidates.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.