Research map / Image generation / Fast diffusion sampling
Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Fast T2T, an optimization consistency model for diffusion-style neural combinatorial optimization that maps any noise level directly to the optimal solution, plus a consistency-based gradient search at test time, enabling one-step solving on TSP and MIS.
Problem
Diffusion-based neural solvers for combinatorial optimization need many iterative denoising steps per instance, making inference slow; the paper aims for fast, high-quality solution generation on TSP and MIS.
Approach
Adapts consistency models to optimization: for each training instance, all noisy points on any trajectory and at any time step are trained to map to the optimal solution, and at test time the latent solution probabilities are refined by exponential gradient updates using the learned consistency mapping and the objective (consistency-based gradient search).
Key results
- On TSP-50/100 greedy decoding, Fast T2T (Ts=1) reaches 0.31%/1.31% drop in ~11s/16s versus DIFUSCO (Ts=100) at 0.41%/1.16% in ~18m, and Fast T2T with Ts=Tg=3 reaches 0.01%/0.03% drop.
- On TSP-500/1000, Fast T2T with one sampling step outperforms DIFUSCO with 100 steps by 10.1% performance gain with 16.8x speedup (as reported by the authors).
- On MIS, Fast T2T (Ts=Tg=1) approximates diffusion baselines with ~100 steps, with 2.5% gain and 26.3x speedup; Fast T2T trails LKH3 in no case but outperforms it early in the TSP-100/1000 runtime curves.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Fast T2T instead of T2T with one sampling and one gradient-search step | TSP-50 · TSP-50 | Time: (26m) -> (54s) | Helped |
| use Fast T2T instead of T2T with one sampling and one gradient-search step | TSP-100 · TSP-100 | Drop: 0.11% -> 0.10% | Helped |
| increase sampling steps from 1 to 5 (ablation) | Fast T2T · TSP-50 | Drop: 0.31% -> 0.02% | Helped |
| increase sampling steps from 1 to 5 (ablation) | Fast T2T · TSP-100 | Drop: 1.31% -> 0.07% | Mixed |
| use Fast T2T instead of DIFUSCO with 100 sampling steps | TSP-50 and TSP-100 · TSP-50 and TSP-100 | Drop: 0.41% -> 0.31%; 1.16% -> 1.31% | Mixed |
| add consistency-based gradient search (ablation) | Fast T2T · TSPLIB 50-200 (Mean) | Drop: 0.41% -> 0.28% | Helped |
| add consistency-based gradient search (ablation) | Fast T2T · TSPLIB 200-1000 (Mean) | Drop: 2.20% -> 0.93% | Helped |
| use Fast T2T instead of T2T | ER 350-400 sampling · ER 350-400 (sampling) | Drop: 23.28% -> 11.45% | Helped |
| increase sampling and gradient-search steps from 1 to 5 (ablation) | Fast T2T · TSP-50 and TSP-100 | Drop: 0.31% -> 0.02%; 1.31% -> 0.07% | Helped |
| set the noise hyperparameter to α=0.2 (ablation) | Fast T2T · TSP | Drop | Helped |
Surprising findings
- Fast T2T is trained to map every noisy point to a single optimal solution, yet multi-sample parallel sampling still yields diverse solutions useful for performance.
- Fast T2T with only one sampling and one gradient-search step outperforms LKH3 in the early solving stage on TSP-100/1000.
Limitations
- Speedup over diffusion baselines diminishes as problem scale grows due to serial processing overhead.
- Training requires two forward passes per instance, roughly doubling training time and GPU memory versus DIFUSCO.
- On SATLIB, the small dataset is insufficient for training the consistency mapping, limiting performance on small real-world data.
Experimental setup
Datasets: TSP random uniform instances (TSP-50/100/500/1000) TSPLIB RB graphs Erdos-Renyi graphs SATLIB
Benchmarks: TSP-50 TSP-100 TSP-500 TSP-1000 TSPLIB RB-[200-300] ER-[700-800] SATLIB
Metrics: length drop (optimality gap) time size
Baselines: Concorde LKH3 2Opt AM POMO Sym-NCO DIFUSCO T2T Gurobi KaMIS
Builds on: consistency models DIFUSCO T2T discrete diffusion (multinomial) DDIM
Closest papers by meaning
- Efficient Combinatorial Optimization via Heat Diffusion (NeurIPS 2024 · similarity 0.88)
- A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization (ICML 2024 · similarity 0.87)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- A Unified Sampling Framework for Solver Searching of Diffusion Probabilistic Models (ICLR 2024 · similarity 0.87)
- TFG: Unified Training-Free Guidance for Diffusion Models (NeurIPS 2024 · similarity 0.87)
- Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.