Pith. sign in

REVIEW 4 major objections 6 minor 73 references

Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization

T0 review · 4 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A consistency-trained GNN can map any noisy version of an instance directly to the optimal solution, so one forward pass plus one gradient step matches diffusion solvers that use 50-100 steps.

desk verdict A useful consistency-training adaptation for discrete diffusion CO solvers, backed by strong empirical results, but with a hand-wavy theory step and an untested distribution shift in the gradient search. read the letter →

arxiv 2502.02941 v1 pith:ACP2WLMA submitted 2025-02-05 cs.LG

Yang Li , Jinpei Guo , Runzhong Wang , Hongyuan Zha , Junchi Yan This is my paper · ORCID
classification cs.LG
keywords combinatorialoptimizationdiffusionmodelsconsistencytravelingsalesmanproblemmaximumindependentsettraining-to-testinggradientsearchgraphneuralnetworks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Diffusion-based neural solvers for combinatorial optimization traditionally pay a large inference cost: they reconstruct a solution by denoising across 50 to 100 steps. This paper argues that such a long chain is unnecessary. It defines an 'optimization consistency' training objective in which, for a given problem instance, every noised version of the optimal solution at every noise level is forced to map back to that optimum in a single network evaluation. The trained consistency GNN then generates solution distributions in one forward pass, and a one-step objective-guided gradient search at test time refines them. On TSP and MIS benchmarks, Fast T2T with one generation step plus one search step is reported to mostly outperform diffusion solvers requiring hundreds of steps, while running tens of times faster.

What carries the argument

The load-bearing object is the optimization consistency condition (Definition 4.1) and its surrogate loss (Eq. 4). Instead of enforcing self-consistency along a single trajectory as in standard consistency models, the network is trained so that all noisy points from all trajectories of instance $G$ collapse onto the optimum $x^*$, measured by binary cross-entropy to the one-hot optimum. The noising process is the multinomial diffusion transition $x_t \sim \mathrm{Cat}(x_t; p = x^* \overline{Q}_t)$ with doubly stochastic mutation matrices $Q_t$, and the network is an anisotropic edge-gated GNN that outputs $N$ Bernoulli distributions over decision variables. The second mechanism is the consistency-based gradient search (Eq. 8), which updates the latent probability vector $p_x = \eta Q_{\alpha T}$ by exponential gradient descent on a weighted sum of a consistency distance to $\eta$ and the objective $\ell(\cdot; G)$, evaluating the model on the continuous vector $p_x$, then sampling and re-decoding. This couples the learned prior with instance-specific objective guidance, which is what lets one-step generation be refined into a competitive solver.

What would settle it

On TSP-100, rerun the $T_s=1, T_g=1$ pipeline with the continuous evaluation $f_\theta(p_x, \alpha T, G)$ in Eq. 8 replaced by an average of $f_\theta$ over many categorical samples $x_{\alpha T} \sim p_x$. If the direct continuous-input version is not at least as good as this sampling-based estimate, the Eq. 8 update is not the mechanism behind the reported one-step gains; if it is, the continuous-input assumption stands.

Watch

Extended reading notes

Core claim

The central claim is that the step-by-step denoising chain of diffusion models is unnecessary for combinatorial optimization. Fast T2T trains a conditional GNN as a consistency function $f_\theta(x_t, t, G)$ that maps any point on any noising trajectory of a given instance directly to that instance's optimal solution $x^*$. The training loss, Eq. 4, computes binary cross-entropy between the model prediction and $x^*$ for two noise points sampled from different trajectories at different time steps, effectively enforcing $f_\theta(x_t, t, G) = \delta(x - x^*)$ along every trajectory. With that mapping learned, sampling reduces to one forward pass: take uniform noise $x_T$ and read off $p_\theta(x_0|G) = f_\theta(x_T, T, G)$. The paper adds a test-time gradient search that updates a latent probability vector by exponential gradient descent on a free energy combining a consistency distance to the current solution with the optimization objective, then re-decodes feasible solutions. On TSP-50/100/500/1000 and MIS benchmarks, one generation step plus one search step is reported to match or beat 50-100-step diffusion baselines, with additional steps trading runtime for further quality.

Load-bearing premise

The load-bearing premise is that a network trained on discrete one-hot noisy samples will still produce reliable solution estimates when, during the one-step test-time search, it is given a continuous weighted average of those samples; the paper does not directly validate that transfer.

Editorial extensions

If this is right

  • Fast T2T at $T_s=1, T_g=1$ achieves 0.03% drop on TSP-50 and 0.10% on TSP-100 with greedy decoding, versus 0.45% and 1.21% for DIFUSCO at 50 steps, in the paper's tables.
  • On TSP-500 and TSP-1000, $T_s=1, T_g=1$ roughly halves DIFUSCO's optimality gap (e.g., 4.28% vs 9.82% at TSP-500) while reducing solving time from minutes to tens of seconds.
  • Multi-step variants extend the same recipe: $T_s=5, T_g=5$ gives 0.39% drop on TSP-500 and 0.58% on TSP-1000 with 2-opt post-processing, beating T2T at $T_s=50, T_g=30$ in both quality and time.
  • On MIS, $T_s=1, T_g=1$ reaches 3.51% drop on RB graphs and 10.30% on ER graphs, beating DIFUSCO at 100 steps while being tens of times faster.
  • With equal time budgets, Fast T2T beats the LKH3 heuristic solver on TSP-100 and TSP-1000 in the early phase of solving.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same consistency loss is a direct recipe for other discrete CO problems such as Max-Cut, SAT, and vehicle routing: it only needs an instance, an optimal-solution label, and a post-processing decoder, so the method is largely problem-agnostic.
  • The gradient update evaluates the network on the expected probability vector rather than on sampled latents; if that continuous-input evaluation is truly valid, a similar expected-denoiser operation could accelerate other consistency or diffusion solvers beyond this paper.
  • Training cost is about twice that of DIFUSCO because each instance needs two forward passes, so the practical win is inference-time; the method is most attractive for deployment where a trained model is reused many times, and less so when training budget dominates.
  • The reported generalization across TSP scales suggests consistency-trained heatmaps carry scale-invariant structural information, raising the testable possibility that the one-step heatmap itself can seed strong local-search solvers to close the remaining gap to exact solvers.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper proposes Fast T2T, a consistency-model variant of diffusion-based neural solvers for combinatorial optimization. For a given instance, the model is trained so that all noisy versions of a solution map directly to the optimal solution, enabling one-step solution generation. A consistency-based gradient search is then applied at test time to update a latent probability vector under objective guidance. Experiments on TSP (up to 1000 nodes) and MIS (RB and ER graphs) report that one-step Fast T2T is competitive with or better than diffusion baselines requiring 50-100 sampling steps, with large inference speedups, and that additional sampling/search steps further improve quality.

Significance. If the empirical results are reproducible, the paper is a significant practical contribution: it offers a way to obtain diffusion-level solution quality with one or few forward passes, which matters for the deployment of neural CO solvers. The experimental scope is unusually broad, covering multiple problem scales, two problem types, cross-scale generalization, TSPLIB and SATLIB transfer, runtime-quality curves against LKH3, and ablations of step counts and noise levels. The claimed speedups are large and the central empirical pattern is consistent across tables. The main weaknesses are in the theoretical justification of the consistency upper bound and in the unspecified behavior of the gradient-search update on continuous inputs; both are localizable and testable.

major comments (4)
  1. [Sec. 4.2, Eq. (3)] The paper justifies the optimization-consistency loss as an upper bound on the pairwise consistency loss via the triangle inequality, but Eq. (3) requires d to be a metric. The actual loss in Eq. (4) and Appendix A.2 uses binary cross entropy, which is not a metric and does not satisfy the triangle inequality. The formal upper-bound claim is therefore unsupported as written. Either replace d with a true metric (e.g., total variation or Jensen-Shannon divergence) in the derivation, or explicitly present Eq. (3) as a heuristic objective that does not rely on the triangle inequality.
  2. [Sec. 5.2, Eq. (8)] The one-step gradient search evaluates f_theta on the continuous vector px = eta Q_{alpha T}, while the training loss in Eq. (4) only feeds the network one-hot categorical samples x_t ~ Cat(.; x* Q_t). The GNN uses sinusoidal input embeddings and nonlinear gated layers, so there is no guarantee that the network's output on these continuous off-distribution inputs represents the learned solution distribution. This issue is load-bearing: for example, in Table 1 the TSP-100 drop improves from 1.31% with Ts=1 to 0.10% with Ts=1,Tg=1, so the reported gain of the gradient-search component depends on this unverified forward pass. Please provide evidence that this gradient is meaningful, for example by comparing with a gradient computed from a sampled one-hot x_{alpha T}, by training on continuous inputs, or by reporting distribution-shift diagnostics.
  3. [Sec. 5.2, Eq. (8)] The multiplicative update px <- px ⊙ exp(-gradient) does not, as written, preserve the row-stochasticity of px or keep its entries in [0,1]. The subsequent instruction to sample x_{alpha T} ~ px is therefore not defined on a valid Bernoulli/categorical distribution unless a projection or renormalization is applied. Please specify the normalization or constrained-update procedure; without it the update rule is incomplete and the experiments are not fully reproducible.
  4. [Sec. 4.2 vs. Algorithm 2 and Appendix A.2] The main text describes a cosine-rescheduled time horizon t_1 = 1 < ... < t_{N_t} = T and a loss over n ~ U[1, N_t - 1], but Algorithm 2 and Appendix A.2 describe a different procedure: t_1 is sampled uniformly from [1, T] and t_2 is set to ceil(alpha t_1). These two training procedures are not equivalent, and the paper does not state which one produced the tables. Please align the main-text description with the implemented algorithm and report the actual training schedule used for the reported results.
minor comments (6)
  1. [Sec. 6.1, Table 3] The text says the model trained on TSP-1000 achieves less than a 0.6% optimality gap on all other problem scales, but the TSP-1000 row of Table 3 for Fast T2T (Ts=20,Tg=20) reports 3.22% on TSP-50 and 3.87% on TSP-100. Please correct either the claim or the table.
  2. [Algorithm 2, line 6] The loss expression in Algorithm 2 uses delta(z1 - x*) where Eq. (4) uses delta(x - x*); this notation should be fixed so the target is the optimal solution rather than a noisy sample.
  3. [Sec. 5.2, Eq. (5)-(7)] F2 is written as l(eta; G) - log Z - y*, but Eq. (5) gives c proportional to exp(-|y* - l(eta; G)|). Unless the assumption l(eta; G) >= y* is stated explicitly, the absolute value should appear in F2.
  4. [Sec. 5.2] The definition l_TSP = x ⊙ D appears to yield a matrix rather than a scalar tour length; please include the summation over the selected edges so the notation is consistent with a scalar objective.
  5. [Tables 1 and 4] The paper reports averages without error bars or statistical significance tests. Some of the headline comparisons, such as the TSP-100 difference between Fast T2T (Ts=1,Tg=1, 0.10%) and T2T (Ts=50,Tg=30, 0.11%) in Table 1, are small and may be within run-to-run variability; at least a statement about variance or a significance test would strengthen the claim that Fast T2T 'mostly outperforms' the baselines.
  6. [Appendix C.4] The training cost table reports very large one-GPU training times (e.g., 488 hours for TSP-100) and states that Fast T2T costs about twice DIFUSCO; the abstract and introduction should clarify that the 'tens of times speedup' refers to inference/solving time, not total training time.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the consistency objective is trained against external reference solutions, and the self-referential search term is a generalization concern rather than a circular derivation.

full rationale

Fast T2T's load-bearing training target is external: Eq. 4 minimizes binary cross-entropy between f_theta(xt, t, G) and delta(x - x*), with x* supplied by Concorde, LKH-3, or KaMIS reference solutions (Sec. 6 and App. C.3). The one-step generation f_theta(xT, T, G) is therefore a supervised regression from noise to a reference solution, not a quantity equivalent to its own inputs by construction. The test-time gradient search in Eq. 8 does contain a self-referential F1 term d(f_theta(px, alpha T, G), delta(x - eta)) that uses the current iterate eta as target, and the inputs to f_theta at search time are continuous probability vectors while training used one-hot samples; however, this is a generalization and robustness concern about whether the learned map transfers to the search distribution, not a case where a claimed prediction is identical to a fitted input by the paper's own equations. The self-citations to the authors' prior T2T work [8] supply the energy-based posterior formulation, the objective surrogates, and baseline settings, but the core consistency objective is trained against external optimal or reference labels and is benchmarked against independently published DIFUSCO results, so no load-bearing claim reduces to a self-citation. Appendix E's stated limitations concern training cost and scale-dependent speedup, neither of which implicates circularity. Accordingly, no circular step meeting the quoted-evidence bar is present.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central method depends on several hand-set hyperparameters (alpha, lambda1/lambda2, k, epsilon) and on assumptions that the supervised Dirac target and the continuous-input evaluation are benign. No new physical or mathematical entities are introduced.

free parameters (4)
  • Noise degree alpha = 0.20 for TSP all scales and ER 700-800, 0.30 for RB 200-300
    Chosen by hyperparameter study in Fig. 5; controls how much noise is injected in the gradient search via px = eta Q_{alpha T}.
  • Gradient search weights lambda1, lambda2 = 50 for TSP, 2 for MIS
    Eq. 8 balances the consistency term and the objective term; set separately per problem without a principled selection rule.
  • Graph sparsification k = k=50 for TSP-500, k=100 for TSP-1000
    Restricts each node to its k nearest neighbors, changing the effective search space; chosen following prior work, not derived.
  • Rewrite ratio epsilon = 0.2 for TSP and ER, 0.3 for RB
    Used in the post-processing or rewriting during gradient search in Appendix A.2; no ablation is provided.
assumptions (5)
  • ad hoc to paper The distance d in Eq. 3 is assumed to satisfy the triangle inequality, but the implemented d is binary cross entropy, which is not a metric.
    This assumption is needed for the claim LOptCM >= LCM in Eq. 3. BCE between Bernoulli distributions does not generally satisfy the triangle inequality, so the stated theoretical grounding is unsupported.
  • domain assumption A single reference solution x* per instance is a sufficient training target, even when multiple optimal or near-optimal solutions exist.
    TSP tours and MIS solutions are often non-unique; the Dirac target in Definition 4.1 collapses multimodality that a generative solver might need.
  • domain assumption The network f_theta, trained on one-hot categorical samples, generalizes to continuous probability inputs px = eta Q_{alpha T} during gradient search.
    Sec. 5.2 evaluates f_theta(px, alpha T, G) on expected probability vectors; no analysis or auxiliary training is provided for this distribution shift.
  • domain assumption Reference solutions produced by LKH3 for TSP-500/1000 and KaMIS for MIS are close enough to optimal to serve as the consistency target x*.
    Appendix C.3 labels large instances with heuristic solvers, so the 'optimal solution' target is approximate.
  • standard math The forward noising matrices Q_t are doubly stochastic, so the stationary distribution is uniform.
    Invoked in Sec. 4.1 to justify the uniform noise prior; this is a standard property of the chosen transition matrices.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization." pith.science (2026). https://pith.science/paper/ACP2WLMA

@misc{pith2026250202941,
  author       = {Pith},
  title        = {Pith review of: Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ACP2WLMA}},
  note         = {Machine review of arXiv:2502.02941}
}
read the original abstract

Diffusion models have recently advanced Combinatorial Optimization (CO) as a powerful backbone for neural solvers. However, their iterative sampling process requiring denoising across multiple noise levels incurs substantial overhead. We propose to learn direct mappings from different noise levels to the optimal solution for a given instance, facilitating high-quality generation with minimal shots. This is achieved through an optimization consistency training protocol, which, for a given instance, minimizes the difference among samples originating from varying generative trajectories and time steps relative to the optimal solution. The proposed model enables fast single-step solution generation while retaining the option of multi-step sampling to trade for sampling quality, which offers a more effective and efficient alternative backbone for neural solvers. In addition, within the training-to-testing (T2T) framework, to bridge the gap between training on historical instances and solving new instances, we introduce a novel consistency-based gradient search scheme during the test stage, enabling more effective exploration of the solution space learned during training. It is achieved by updating the latent solution probabilities under objective gradient guidance during the alternation of noise injection and denoising steps. We refer to this model as Fast T2T. Extensive experiments on two popular tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrate the superiority of Fast T2T regarding both solution quality and efficiency, even outperforming LKH given limited time budgets. Notably, Fast T2T with merely one-step generation and one-step gradient search can mostly outperform the SOTA diffusion-based counterparts that require hundreds of steps, while achieving tens of times speedup.

Figures

Figures reproduced from arXiv: 2502.02941 by the authors.

Figure 1
Figure 1. Optimization consistency models for CO solving where the model learns how to map from [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Vannila consistency models are trained to map points on any trajectory to its origin. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Effect of runtime to optimality drop for Fast T2T and LKH3 on TSP-100 [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Effect of runtime to optimality drop for Fast T2T and LKH3 on TSP-1000 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Effect of α to the performance drop. LKH3, which may find widespread applications requiring prompt responses. Other neural solver baselines fall far outside the comparable range; please refer to [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: Effect of step num￾ber to drop for diffusion/con￾sistency based methods. GS stands for gradient search. set as comparable to neural solvers, thus it does not reach optimality. Table. 4 shows that Fast T2T with merely one-step sampling and gradient search steps averagel…
Figure 7
Figure 7. Figure 7: Confusion matrix of four scales from TSP datasets. Models are trained on scales on [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

73 extracted references · 53 canonical work pages

  1. [1]

    Machine learning for combinatorial optimization: a methodological tour d’horizon,

    Y . Bengio, A. Lodi, and A. Prouvost, “Machine learning for combinatorial optimization: a methodological tour d’horizon,” European Journal of Operational Research, 2021

    work page 2021

  2. [2]

    Attention, learn to solve routing problems!

    W. Kool, H. Van Hoof, and M. Welling, “Attention, learn to solve routing problems!” arXiv preprint arXiv:1803.08475, 2018

    arXiv 2018

  3. [3]

    An efficient graph convolutional network technique for the travelling salesman problem,

    C. K. Joshi, T. Laurent, and X. Bresson, “An efficient graph convolutional network technique for the travelling salesman problem,” arXiv preprint arXiv:1906.01227, 2019

    arXiv 1906

  4. [4]

    Pomo: Policy optimization with multiple optima for reinforcement learning,

    Y .-D. Kwon, J. Choo, B. Kim, I. Yoon, Y . Gwon, and S. Min, “Pomo: Policy optimization with multiple optima for reinforcement learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 21 188–21 198, 2020

    work page 2020

  5. [5]

    Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization

    M. Kim, J. Park, and J. Park, “Sym-nco: Leveraging symmetricity for neural combinatorial optimization,” arXiv preprint arXiv:2205.13209, 2022

    work page Pith review arXiv 2022

  6. [6]

    Dimes: A differentiable meta solver for combinatorial optimization problems,

    R. Qiu, Z. Sun, and Y . Yang, “Dimes: A differentiable meta solver for combinatorial optimization problems,” arXiv preprint arXiv:2210.04123, 2022

    arXiv 2022

  7. [7]

    DIFUSCO: Graph-based diffusion solvers for combinatorial optimization,

    Z. Sun and Y . Yang, “DIFUSCO: Graph-based diffusion solvers for combinatorial optimization,” in Thirty-seventh Conference on Neural Information Processing Systems , 2023. [Online]. Available: https://openreview.net/forum?id=JV8Ff0lgVV 10

    work page 2023

  8. [8]

    T2t: From distribution learning in training to gradient search in testing for combinatorial optimization,

    Y . Li, J. Guo, R. Wang, and J. Yan, “T2t: From distribution learning in training to gradient search in testing for combinatorial optimization,” inAdvances in Neural Information Processing Systems, 2023

    work page 2023

Show all 73 references
  1. [9]

    Unsupervised learning for solving the travelling salesman problem,

    Y . Min, Y . Bai, and C. P. Gomes, “Unsupervised learning for solving the travelling salesman problem,” Advances in Neural Information Processing Systems, vol. 36, 2024

    2024

  2. [10]

    Pointer networks,

    O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer networks,”Advances in neural information processing systems, vol. 28, 2015

    2015

  3. [11]

    Graph neural network guided local search for the traveling salesperson problem,

    B. Hudson, Q. Li, M. Malencia, and A. Prorok, “Graph neural network guided local search for the traveling salesperson problem,” in International Conference on Learning Representations,

  4. [12]

    Generalize a small pre-trained model to arbitrarily large tsp instances,

    Z.-H. Fu, K.-B. Qiu, and H. Zha, “Generalize a small pre-trained model to arbitrarily large tsp instances,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 8, 2021, pp. 7474–7482

    2021

  5. [13]

    Neural combinatorial optimization with heavy decoder: Toward large scale generalization,

    F. Luo, X. Lin, F. Liu, Q. Zhang, and Z. Wang, “Neural combinatorial optimization with heavy decoder: Toward large scale generalization,”Advances in Neural Information Processing Systems, vol. 36, 2024

    2024

  6. [14]

    Neural combinatorial optimization with reinforcement learning,

    I. Bello, H. Pham, Q. V . Le, M. Norouzi, and S. Bengio, “Neural combinatorial optimization with reinforcement learning,” arXiv preprint arXiv:1611.09940, 2016

    2016 arXiv

  7. [15]

    Efficient active search for combinatorial optimization problems,

    A. Hottung, Y .-D. Kwon, and K. Tierney, “Efficient active search for combinatorial optimization problems,” arXiv preprint arXiv:2106.05126, 2021

    2021 arXiv

  8. [16]

    Consistency models,

    Y . Song, P. Dhariwal, M. Chen, and I. Sutskever, “Consistency models,” arXiv preprint arXiv:2303.01469, 2023

    2023 arXiv

  9. [17]

    Deep unsupervised learning using nonequilibrium thermodynamics,

    J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli, “Deep unsupervised learning using nonequilibrium thermodynamics,” in International Conference on Machine Learning, 2015, pp. 2256–2265

    2015

  10. [18]

    Structured denoising diffusion models in discrete state-spaces,

    J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg, “Structured denoising diffusion models in discrete state-spaces,” Advances in Neural Information Processing Systems, vol. 34, pp. 17 981–17 993, 2021

    2021

  11. [19]

    Argmax flows and multinomial diffusion: Learning categorical distributions,

    E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling, “Argmax flows and multinomial diffusion: Learning categorical distributions,” Advances in Neural Information Processing Systems, vol. 34, pp. 12 454–12 465, 2021

    2021

  12. [20]

    Learning combinatorial optimization algorithms over graphs,

    E. Khalil, H. Dai, Y . Zhang, B. Dilkina, and L. Song, “Learning combinatorial optimization algorithms over graphs,” Advances in neural information processing systems, vol. 30, 2017

    2017

  13. [21]

    Learning a latent search space for routing problems using variational autoencoders,

    A. Hottung, B. Bhandari, and K. Tierney, “Learning a latent search space for routing problems using variational autoencoders,” in International Conference on Learning Representations , 2021

    2021

  14. [22]

    Generalization of neural combinatorial solvers through the lens of adversarial robustness,

    S. Geisler, J. Sommer, J. Schuchardt, A. Bojchevski, and S. Günnemann, “Generalization of neural combinatorial solvers through the lens of adversarial robustness,” in International Conference on Learning Representations, 2022

    2022

  15. [23]

    Learning plaintext-ciphertext crypto- graphic problems via anf-based sat instance representation,

    X. Zheng, Y . Li, C. Fan, H. Wu, X. Song, and J. Yan, “Learning plaintext-ciphertext crypto- graphic problems via anf-based sat instance representation,” Advances in Neural Information Processing Systems, 2024

    2024

  16. [24]

    Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning,

    P. R. d O Costa, J. Rhuggenaath, Y . Zhang, and A. Akcay, “Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning,” in Asian Conference on Machine Learning, 2020, pp. 465–480

    2020

  17. [25]

    Learning improvement heuristics for solving routing problems,

    Y . Wu, W. Song, Z. Cao, J. Zhang, and A. Lim, “Learning improvement heuristics for solving routing problems,” IEEE transactions on neural networks and learning systems, vol. 33, no. 9, pp. 5057–5069, 2021

    2021

  18. [26]

    Learning to perform local rewriting for combinatorial optimization,

    X. Chen and Y . Tian, “Learning to perform local rewriting for combinatorial optimization,” Advances in Neural Information Processing Systems, vol. 32, 2019

    2019

  19. [27]

    Learning to delegate for large-scale vehicle routing,

    S. Li, Z. Yan, and C. Wu, “Learning to delegate for large-scale vehicle routing,”Advances in Neural Information Processing Systems, vol. 34, pp. 26 198–26 211, 2021. 11

    2021

  20. [28]

    Generalize learned heuristics to solve large- scale vehicle routing problems in real-time,

    Q. Hou, J. Yang, Y . Su, X. Wang, and Y . Deng, “Generalize learned heuristics to solve large- scale vehicle routing problems in real-time,” in The Eleventh International Conference on Learning Representations, 2023

    2023

  21. [29]

    The policy-gradient placement and generative routing neural networks for chip design,

    R. Cheng, X. Lyu, Y . Li, J. Ye, J. Hao, and J. Yan, “The policy-gradient placement and generative routing neural networks for chip design,” Advances in Neural Information Processing Systems, vol. 35, pp. 26 350–26 362, 2022

    2022

  22. [30]

    Hubrouter: Learning global routing via hub generation and pin-hub connection,

    X. Du, C. Wang, R. Zhong, and J. Yan, “Hubrouter: Learning global routing via hub generation and pin-hub connection,” in Advances in Neural Information Processing Systems, 2023

    2023

  23. [31]

    Let the flows tell: Solving graph combinatorial optimization problems with gflownets,

    D. Zhang, H. Dai, N. Malkin, A. Courville, Y . Bengio, and L. Pan, “Let the flows tell: Solving graph combinatorial optimization problems with gflownets,” arXiv preprint arXiv:2305.17010, 2023

    2023 arXiv

  24. [32]

    Generative modeling by estimating gradients of the data distribution,

    Y . Song and S. Ermon, “Generative modeling by estimating gradients of the data distribution,” Advances in neural information processing systems, vol. 32, 2019

    2019

  25. [33]

    Denoising diffusion probabilistic models,

    J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,”Advances in Neural Information Processing Systems, vol. 33, pp. 6840–6851, 2020

    2020

  26. [34]

    Denoising diffusion implicit models,

    J. Song, C. Meng, and S. Ermon, “Denoising diffusion implicit models,” arXiv preprint arXiv:2010.02502, 2020

    2010 arXiv

  27. [35]

    Improved techniques for training score-based generative models,

    Y . Song and S. Ermon, “Improved techniques for training score-based generative models,” Advances in neural information processing systems, vol. 33, pp. 12 438–12 448, 2020

    2020

  28. [36]

    Improved denoising diffusion probabilistic models,

    A. Q. Nichol and P. Dhariwal, “Improved denoising diffusion probabilistic models,” inInterna- tional Conference on Machine Learning, 2021, pp. 8162–8171

    2021

  29. [37]

    Diffusion models beat gans on image synthesis,

    P. Dhariwal and A. Nichol, “Diffusion models beat gans on image synthesis,” Advances in Neural Information Processing Systems, vol. 34, pp. 8780–8794, 2021

    2021

  30. [38]

    Score-based generative modeling through stochastic differential equations,

    Y . Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole, “Score-based generative modeling through stochastic differential equations,”arXiv preprint arXiv:2011.13456, 2020

    2011 arXiv

  31. [39]

    Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs,

    N. Karalias and A. Loukas, “Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs,” Advances in Neural Information Processing Systems, vol. 33, pp. 6659–6672, 2020

    2020

  32. [40]

    Unsupervised learning for combinatorial opti- mization with principled objective relaxation,

    H. P. Wang, N. Wu, H. Yang, C. Hao, and P. Li, “Unsupervised learning for combinatorial opti- mization with principled objective relaxation,” in Advances in Neural Information Processing Systems, 2022

    2022

  33. [41]

    A tutorial on energy-based learning,

    Y . LeCun, S. Chopra, R. Hadsell, M. Ranzato, and F. Huang, “A tutorial on energy-based learning,” Predicting structured data, vol. 1, no. 0, 2006

    2006

  34. [42]

    Diffusion models as plug-and-play priors,

    A. Graikos, N. Malkin, N. Jojic, and D. Samaras, “Diffusion models as plug-and-play priors,” arXiv preprint arXiv:2206.09012, 2022

    2022 arXiv

  35. [43]

    An effective heuristic algorithm for the traveling-salesman problem,

    S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations research, vol. 21, no. 2, pp. 498–516, 1973

    1973

  36. [44]

    Concorde tsp solver,

    D. Applegate, R. Bixby, V . Chvatal, and W. Cook, “Concorde tsp solver,” 2006

    2006

  37. [45]

    An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems,

    K. Helsgaun, “An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems,” Roskilde: Roskilde University, pp. 24–50, 2017

    2017

  38. [46]

    A method for solving traveling-salesman problems,

    G. A. Croes, “A method for solving traveling-salesman problems,”Operations research, vol. 6, no. 6, pp. 791–812, 1958

    1958

  39. [47]

    The transformer network for the traveling salesman problem,

    X. Bresson and T. Laurent, “The transformer network for the traveling salesman problem,” arXiv preprint arXiv:2103.03012, 2021

    2021 arXiv

  40. [48]

    Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning,

    P. R. d. O. da Costa, J. Rhuggenaath, Y . Zhang, and A. Akcay, “Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning,” arXiv preprint arXiv:2004.01608, 2020

    2004 arXiv

  41. [49]

    Gurobi optimizer reference manual,

    Gurobi Optimization, “Gurobi optimizer reference manual,” http://www.gurobi.com, 2020

    2020

  42. [50]

    Learning heuristics for the tsp by policy gradient,

    M. Deudon, P. Cournut, A. Lacoste, Y . Adulyasak, and L.-M. Rousseau, “Learning heuristics for the tsp by policy gradient,” in International conference on the integration of constraint programming, artificial intelligence, and operations research. Springer, 2018, pp. 170–181. 12

    2018

  43. [51]

    Finding near-optimal indepen- dent sets at scale,

    S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck, “Finding near-optimal indepen- dent sets at scale,” in 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2016, pp. 138–150

    2016

  44. [52]

    Combinatorial optimization with graph convolutional networks and guided tree search,

    Z. Li, Q. Chen, and V . Koltun, “Combinatorial optimization with graph convolutional networks and guided tree search,” Advances in neural information processing systems, vol. 31, 2018

    2018

  45. [53]

    What’s wrong with deep learning in tree search for combinatorial optimization,

    M. Böther, O. Kißig, M. Taraz, S. Cohen, K. Seidel, and T. Friedrich, “What’s wrong with deep learning in tree search for combinatorial optimization,” arXiv preprint arXiv:2201.10494, 2022

    2022 arXiv

  46. [54]

    Learning what to defer for maximum independent sets,

    S. Ahn, Y . Seo, and J. Shin, “Learning what to defer for maximum independent sets,” in International Conference on Machine Learning, 2020, pp. 134–144

    2020

  47. [55]

    On the evolution of random graphs,

    P. Erd˝os, A. Rényi et al., “On the evolution of random graphs,”Publ. Math. Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17–60, 1960

    1960

  48. [56]

    Graph neural network guided local search for the traveling salesperson problem,

    B. Hudson, Q. Li, M. Malencia, and A. Prorok, “Graph neural network guided local search for the traveling salesperson problem,” arXiv preprint arXiv:2110.05291, 2021

    2021 arXiv

  49. [57]

    Satlib: An online resource for research on sat,

    H. H. Hoos and T. Stützle, “Satlib: An online resource for research on sat,” Sat, vol. 2000, pp. 283–292, 2000. 13 Appendix A Training Details A.1 Training Algorithm Algorithm 2 Optimization Consistency Training 1: Input dataset D, consistency modelfθ(·, ·), initial model para...

    2000

  50. [59]

    Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The abstract and introduction explicitly state the claims made, including the contributions made in the paper (Sec. 1)...

  51. [60]

    Limitations

    Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We discuss the limitations in Appendix E. Guidelines: • The answer NA means that the paper has no limitation while the answer No means that the paper...

  52. [61]

    5, and there are no additional theorems needed to be proved

    Theory Assumptions and Proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 22 Answer: [Yes] Justification: The theoretical derivation of this paper has been given in Sec. 5, and there are no addit...

  53. [62]

    6 and Append

    Experimental Result Reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and da...

  54. [63]

    Guidelines: • The answer NA means that paper does not include experiments requiring code

    Open access to data and code 23 Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] Justification: The source code will be m...

  55. [64]

    6 and Append

    Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: The experimental details are ...

  56. [65]

    Experiment Statistical Significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [No] Justification: we follow the setting of previous works to report t...

  57. [66]

    Experiments Compute Resources Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: We provide the testing ...

  58. [67]

    Guidelines: • The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics

    Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The research conducted in the paper conform, in every respect, with the NeurIPS...

  59. [68]

    Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: We discuss the borader impacts in Appendix. E. Guidelines: • The answer NA means that there is no societa...

  60. [69]

    Guidelines: • The answer NA means that the paper poses no such risks

    Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses...

  61. [70]

    Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: The original pap...

  62. [71]

    Our source code will be released upon the acceptance of the paper with comprehensive documents

    New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: Currently, the paper does not release new assets. Our source code will be released upon the acceptance of the paper w...

  63. [72]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Crowdsourcing and Research with Human Subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? A...

  64. [73]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals...

  65. [2022]

    Available: https://openreview.net/forum?id=ar92oEosBIg

    [Online]. Available: https://openreview.net/forum?id=ar92oEosBIg

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.