PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, Junchi Yan

arXiv:2502.02941v1cs.LG

TL;DR

Diffusion-based CO solvers incur overhead from iterative denoising, motivating faster instance-specific solution generation. Fast T2T learns optimization-consistent mappings for one-step generation and adds objective-guided test-time gradient search. On TSP and MIS, it mostly outperforms diffusion-based counterparts with far fewer steps and substantially lower inference time, while its speed advantage attenuates as problem scale grows.

  • Problem

    Diffusion-based CO solvers require denoising across multiple noise levels, while training performance does not ensure optimal performance for every test instance.

  • Method

    Fast T2T trains optimization-consistent mappings from varying noise levels to instance-conditioned optimal solution distributions and applies objective-guided gradient search during testing.

  • Results

    Fast T2T mostly outperforms diffusion-based counterparts on TSP and MIS with one-step generation and one-step gradient search, requiring significantly less inference time.

  • Takeaways & Limitations

    Fast T2T provides an efficient neural-solver backbone that retains multi-step sampling for further quality enhancement.

  • Takeaways & Limitations

    As problem scale increases, serial processing occupies a larger share of runtime, attenuating Fast T2T’s overall speed improvement.

Abstract

from arXiv · show

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.

1 Introduction

Fast T2T addresses diffusion-based CO solvers’ sampling overhead by learning optimization-consistent mappings from noise to instance-specific optimal solutions. It combines rapid generation with test-time objective-guided search and demonstrates strong quality and efficiency on TSP and MIS.

  • Motivation: CO solvers must balance difficult instance-specific optimization with efficient test-time performance.Learning-based solvers can optimize average training performance without ensuring optimality on every test instance.
  • Approach: Fast T2T learns conditional mappings from varying noise levels directly to high-quality solution distributions for each problem instance.The approach builds on discrete diffusion’s transition from uniform noise to high-quality solutions.
  • Approach: Optimization consistency aligns samples across trajectories and noise steps with the optimal solution, enabling one-step generation from random noise.Multi-step sampling remains available by alternating noise introduction and solution reconstruction to trade speed for quality.
  • Test-time search: Fast T2T adds instance-specific objective gradient search on the learned solution prior during testing.The search updates intermediate noisy-point probabilities through objective-guided exponential gradient updates during alternating noise injection and denoising.
  • Results: Fast T2T mostly outperforms diffusion-based counterparts using one-step generation and one-step gradient search, while requiring substantially less inference time.Experiments cover TSP and MIS, with additional steps available for quality enhancement.

2 Related Work

Prior CO learning methods include constructive and improvement-based solvers, while generative approaches model instance-conditioned solution distributions. Diffusion models provide strong representations but motivate more efficient and instance-specific solving strategies.

  • Machine Learning for CO: Learning-based CO solvers comprise constructive methods that build or predict solutions and improvement-based methods that iteratively refine them.Constructive methods include autoregressive and non-autoregressive approaches.
  • Generative modeling for CO: Generative CO modeling treats solving as conditional generation of solution distributions given problem instances.DIFUSCO is identified as achieving state-of-the-art performance on TSP and MIS.
  • Diffusion and consistency models: Diffusion models learn data distributions through alternating noise injection and denoising across steps, including discrete-data variants.This iterative formulation underlies diffusion-based solution trajectories.

3 Preliminaries and Problem Definition

The paper represents CO instances as graphs and solutions as binary one-hot decision variables subject to feasibility constraints. The objective is to find a feasible solution minimizing a graph-dependent objective, with TSP and MIS illustrating edge- and node-decision cases.

  • Problem representation: CO instances are represented as graphs G(V, E), where V and E denote nodes and edges.The paper distinguishes edge-decision problems from node-decision problems by the composition of their solutions.
  • Decision variables: The optimization variable x is a collection of binary one-hot decisions, with N=n2 for edge decisions and N=n for node decisions.For edge problems, x_i,j indicates whether edge E_i,j is selected; for node problems, x_i indicates whether node V_i is selected.
  • Optimization objective: A feasible solution belongs to the constraint-defined set Ω, and CO seeks a feasible x minimizing the objective l(·; G).Feasibility and objective minimization jointly define the optimization problem.
  • Representative problems: TSP minimizes the total weight of a Hamiltonian cycle, whereas MIS maximizes the cardinality of an independent vertex set.TSP is defined on a weighted complete graph; MIS forbids adjacent vertices within the selected set.

4 Training-Stage Optimization Consistency Modeling

Fast T2T models CO solutions with optimization consistency: conditioned on an instance, points from different trajectories and noise steps map toward its optimal solution. Training uses discrete diffusion trajectories and consistency losses, while sampling supports one or multiple denoising steps.

  • 4.1 Solution Encoding and Noising Process: CO solutions are represented as binary variables, with neural models learning a high-quality solution distribution conditioned on instance G.The discrete diffusion process progressively noises an initial solution through categorical transitions toward a uniform prior.
  • 4.2 Optimization Consistency Training Scheme: Optimization consistency maps points from any trajectory and noise step, conditioned on G, to the optimal solution x∗.This extends ordinary consistency from points on one trajectory to all trajectories associated with the same optimization instance.
  • 4.2 Optimization Consistency Training Scheme: The training objective incorporates x∗ to optimize an upper bound on consistency-mapping variation through distance-based comparisons.The resulting objective directly disperses information about the optimal solution across noise time steps.
  • 4.2 Optimization Consistency Training Scheme: Training samples independently draw noisy states from different trajectories and time steps, with a rescheduled cosine time horizon enforcing consistency across noise levels.The schedule divides the horizon into Nt −1 sub-intervals and avoids overly easy comparisons between nearby times.
  • 4.2 Optimization Consistency Training Scheme: Although training targets a Dirac distribution at x∗, the model can estimate a solution distribution centered on the optimum, preserving diversity for parallel sampling.The implementation uses binary cross entropy against the optimal-solution target and an anisotropic graph neural network conditioned on the instance.

5 Testing-Stage Problem Solving via Consistency-Based Gradient Search

Fast T2T combines consistency sampling with instance-specific gradient search guided by the objective. It updates latent solution probabilities through the learned prior and objective feedback, while allowing feasible lower-cost solutions to be selected after each iteration.

  • 5 Testing-Stage Problem Solving: Solving begins with consistency sampling and then applies objective-feedback gradient search to improve the instance-specific solution.The initial solution can be generated in one forward pass, while multiple alternating denoising and noise-injection steps trade runtime for quality.
  • 5.1 Consistency Sampling: Consistency sampling starts from uniform noise and maps it to an initial solution through fθ, with optional multistep inference using sampled noisy states.Algorithm 1 repeatedly samples xτn from the current solution distribution and re-estimates pθ(x0|G).
  • 5.2 Consistency-based Gradient Search with Objective Feedback: The search targets a posterior pθ(x|y∗,G) by combining the learned solution prior with an objective-derived compatibility model.The energy function reaches zero when the candidate objective equals the target objective score, and the corresponding Gibbs distribution favors compatible solutions.
  • 5.2 Consistency-based Gradient Search with Objective Feedback: Latent continuous probabilities px are updated by exponential gradient descent to minimize consistency and objective-related free-energy terms.Here px parameterizes Bernoulli distributions over noisy variables, while fθ estimates the expected distribution of x0 for gradient computation.
  • 5.2 Consistency-based Gradient Search with Objective Feedback: Each iteration combines current and re-sampled consistency predictions, converts their logits into confidence heatmaps, and outputs the lower-cost feasible solution.Post-processing is used to obtain feasible solutions from edge or node confidence scores.

6 Experiments

Experiments on TSP and MIS show that Fast T2T preserves or improves solution quality while substantially reducing inference time, including under one-step sampling and gradient search. It also generalizes across TSP scales and outperforms LKH3 early in solving.

  • TSP-50/100: Fast T2T with one-step sampling gains 5.7% performance and achieves 82.8x speedup on TSP-50/100 versus diffusion-based solvers with 100 sampling steps.With gradient search, the average gain is 4.5% and speedup is 35.4x.
  • TSP-500/1000: Fast T2T with one-step sampling gains 10.1% performance and achieves 16.8x speedup on TSP-500/1000 versus diffusion-based solvers with 100 sampling steps.With gradient search, the average gain is 14.9% and speedup is 8.5x.
  • Generalization: Training on TSP-1000 achieves less than a 0.6% optimality gap on every other tested TSP scale.The evaluation covers TSP-50, TSP-100, TSP-500, and TSP-1000.
  • Runtime comparison: Fast T2T surpasses LKH3 during the early solving stage and performs comparably later on TSP-100 and TSP-1000.The comparison uses runtime–optimality-drop curves.
  • Ablation and hyperparameters: Ablations identify α = 0.2 as relatively superior and stable, while varying sampling and gradient-search steps measures the quality–cost trade-off.The study directly compares Fast T2T with diffusion-based methods under minimal-step settings.
  • MIS: Fast T2T with one-step sampling and gradient search gains 2.5% performance and achieves 26.3x speedup on MIS versus diffusion-based counterparts with approximately 100 sampling steps.More sampling and gradient-search steps yield a 23.7% performance gain with 9.1x speedup.

7 Conclusion

Fast T2T adds optimization consistency to diffusion-based training-to-testing solving for efficient combinatorial optimization. Experiments on TSP and MIS report quality and speed gains over prior neural solvers, with early-stage superiority over LKH3.

  • Conclusion: Fast T2T enables rapid single-step solving with comparable or superior performance to state-of-the-art diffusion-based counterparts.It is presented as an alternative backbone for neural solvers.
  • Conclusion: Consistency-based gradient search complements the learned prior and improves test-time exploration for individual instances.The scheme is introduced within the training-to-testing solving framework.
  • Conclusion: Experiments on TSP and MIS show gains in solution quality and speed, while Fast T2T is superior to LKH3 during early solving stages.These conclusions are reported across the evaluated datasets.

A Training Details

Optimization consistency training samples two noisy versions of an optimal solution and trains the model to map both toward a shared target. The procedure uses a consistency loss with specified scaling, weighting, and learning-rate settings.

  • Optimization Consistency Training: Optimization consistency training samples an optimal solution, two noise levels, and trains both model outputs against a shared target distribution.The time points satisfy t2 = ⌈αt1⌉, and the parameters are updated by gradient descent on the consistency loss.
  • Design choices: The listed hyperparameters correspond to the algorithm used in the paper’s training and experimental sections.The appendix supplements the specific design choices of the optimization consistency models.
  • Design choices: The training configuration uses binary cross-entropy, α = 0.5, λ(t) = 1, and an initial learning rate of 0.0002.The learning rate follows cosine decay with decay rate ω = 0.0001.
  • Sampling schedule: The sampling schedule uses sinusoidal time points, with guided weighting parameters λ1 = 50 and λ2 = 50 on TSP and λ1 = 2 and λ2 = 2 on MIS.The rewrite ratio is ϵ = 0.2 for TSP and ER-[700-800], and ϵ = 0.3 for RB-[200-300].

B.1 Results on TSP Real-World Data

Fast T2T is evaluated on real-world TSPLIB TSP instances and the SATLIB MIS dataset, including settings that test transfer across instance scales. The supplied passages emphasize benchmark scope and experimental configurations, but provide few numerical outcomes.

  • TSPLIB TSP: TSPLIB evaluations test models trained on random 100-node problems against real-world instances with 50–200 nodes.The compared methods include DIFUSCO, T2T, Fast T2T, and additional baselines.
  • TSPLIB TSP: Additional TSPLIB experiments evaluate models trained on random 500-node problems on instances ranging from 200 to 1000 nodes.
  • SATLIB MIS: SATLIB results are reported despite insufficient data for learning Fast T2T’s consistency mapping, and Fast T2T still outperforms previous baselines.The authors state that the consistency mapping is more challenging to learn and requires more data.
  • Scale transfer: Figure 7 compares models trained at one TSP scale with greedy-decoding performance at another, reporting drops relative to exact solvers.

B.4 Results for Generalization on MIS

Fast T2T generalizes across MIS graph densities, sizes, and graph families while retaining reported gains in solution quality and speed over diffusion-based counterparts.

  • Within-family generalization: Fast T2T generalizes from ER 700–800 graphs with p = 0.15 to different edge probabilities and graph sizes, outperforming DIFUSCO and T2T in quality and speed.
  • Within-family generalization: In ER 350–400 sampling, Fast T2T improves the reported pair from (23.28%, 24m31s) to (11.45%, 1m1s).
  • Cross-dataset generalization: Across RB and ER graph families, Fast T2T outperforms previous diffusion-based methods by a clear margin.
  • Cross-dataset generalization: For Train:ER; Test:RB sampling, the reported pair improves from (23.24%, 30m13s) to (9.10%, 4m20s).
  • Evaluation setup: The evaluations use a single RTX 4090 for TSP-50/100 and MIS, while TSP-500/1000 evaluations use a single Tesla A100.

C.4 Training Resource Requirement

Fast T2T requires substantial offline training resources: approximately twice the training time and GPU memory of DIFUSCO under the same settings, while benchmark comparisons use varied solver baselines and inference budgets.

  • Resource requirement: Fast T2T requires approximately double DIFUSCO’s training time and GPU memory under the same settings.The authors attribute this to two forward passes for each training instance during consistency training.
  • Resource requirement: AM, POMO, and Sym-NCO also require substantial training resources, including 45.8 hours, approximately one week, and approximately two weeks in reported settings.
  • Benchmark setup: TSP-50/100 comparisons include exact, heuristic, and learning-based solvers, with greedy sampling and 2OPT refinement applied during post-processing.
  • Benchmark setup: TSP-500/1000 comparisons include Concorde, Gurobi, LKH-3, Farthest Insertion, and six learning-based methods.
  • Benchmark setup: MIS comparisons cover RB-[200-300] and ER-[700-800] against exact, heuristic, and learning-based frameworks, using greedy sampling or tree search.

D Network Architecture Details

The network uses graph convolution with sinusoidal embeddings for node, edge, and timestep inputs, then predicts edge heatmaps for TSP and node heatmaps for MIS.

  • Input embeddings: Node vectors, weighted edge vectors, and denoising timesteps receive sinusoidal feature embeddings before graph convolution.For TSP, edge inputs represent pairwise distances; for MIS, edge embeddings are initialized to zero.
  • Graph convolution: The architecture uses cross-layer convolution that integrates edge features to represent edge significance in routing problems.
  • Task-specific updates: Timestep features are aggregated with edge convolutional features for TSP and node convolutional features for MIS.
  • Output prediction: The model predicts an edge heatmap for TSP and a node heatmap for MIS after the graph-convolution layers.
  • Architecture settings: Both tasks use a 12-layer GCN, with embedding dimension d = 256 for TSP and d = 128 for MIS.

E Limitations and Broader Impacts

Fast T2T’s efficiency advantage is constrained at larger problem scales, while its consistency training increases offline cost. The paper also positions the method as a broadly applicable neural CO backbone and reports reproducibility and limitations disclosures.

  • Limitations: As problem scale increases, Fast T2T’s speed improvement over diffusion-based methods attenuates because serial processing occupies a larger share of the pipeline.The authors leave combining the model with more efficient traditional solving strategies for future work.
  • Limitations: Consistency training requires twice the original diffusion model’s training cost because it uses predictions at two noise levels.This overhead is offline, while inference remains more efficient than diffusion.
  • Broader impact: The authors describe Fast T2T as an efficient, versatile backbone that can be integrated into existing and future neural CO solving frameworks.This is presented as the work’s broader applicability within neural combinatorial optimization.
  • Reproducibility: The paper reports that experimental details are provided in Sections 6 and the appendices, with source code planned for public release upon acceptance.The checklist responses state that the main claims match the experimental results.
Loading 2502.02941v1…