# An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem

arXiv: https://arxiv.org/abs/2501.13767 · HTML: https://mlsanity.com/paper/2501.13767/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 30 of its 54 references that are in the map.
- First posted on arXiv 23 Jan 2025.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning](https://mlsanity.com/paper/2208.04202/) (2022)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Diffusion models as plug-and-play priors](https://mlsanity.com/paper/2206.09012/) (2022)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy](https://mlsanity.com/paper/2308.14104/) (2023)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem](https://mlsanity.com/paper/2304.09407/) (2023)
- [Guiding Non-Autoregressive Neural Machine Translation Decoding with Reordering Information](https://mlsanity.com/paper/1911.02215/) (2019)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speed](https://mlsanity.com/paper/2312.12469/) (2023)
- [Hierarchical Neural Constructive Solver for Real-world TSP Scenarios](https://mlsanity.com/paper/2408.03585/) (2024)
- [Divide and Conquer Networks](https://mlsanity.com/paper/1611.02401/) (2016)
- [Incorporating Surprisingly Popular Algorithm and Euclidean Distance-based Adaptive Topology into PSO](https://mlsanity.com/paper/2108.11173/) (2021)

## Built on by (most cited first, 9 of 9)

- [Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2510.04792/) (2025)
- [GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales](https://mlsanity.com/paper/2506.06634/) (2025)
- [Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2507.21386/) (2025)
- [Mechanistic Interpretability for Neural TSP Solvers](https://mlsanity.com/paper/2510.21693/) (2025)
- [CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization](https://mlsanity.com/paper/2602.08210/) (2026)
- [RsGCN: Subgraph-Based Rescaling Enhances Generalization of GCNs for Solving Traveling Salesman Problems](https://mlsanity.com/paper/2506.00533/) (2025)
- [Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling](https://mlsanity.com/paper/2603.02846/) (2026)
- [WeCon: An Efficient Weight-Conditioned Neural Solver for Multi-Objective Combinatorial Optimization Problems](https://mlsanity.com/paper/2605.22876/) (2026)
- [GeoRouteNet: A Geometry-Aware Non-Autoregressive Neural Solver for the Euclidean Traveling Salesman Problem](https://mlsanity.com/paper/2606.22776/) (2026)

## Abstract (arXiv)

Recent advances in neural models have shown considerable promise in solving Traveling Salesman Problems (TSPs) without relying on much hand-crafted engineering. However, while non-autoregressive (NAR) approaches benefit from faster inference through parallelism, they typically deliver solutions of inferior quality compared to autoregressive ones. To enhance the solution quality while maintaining fast inference, we propose DEITSP, a diffusion model with efficient iterations tailored for TSP that operates in a NAR manner. Firstly, we introduce a one-step diffusion model that integrates the controlled discrete noise addition process with self-consistency enhancement, enabling optimal solution prediction through simultaneous denoising of multiple solutions. Secondly, we design a dual-modality graph transformer to bolster the extraction and fusion of features from node and edge modalities, while further accelerating the inference with fewer layers. Thirdly, we develop an efficient iterative strategy that alternates between adding and removing noise to improve exploration compared to previous diffusion methods. Additionally, we devise a scheduling framework to progressively refine the solution space by adjusting noise levels, facilitating a smooth search for optimal solutions. Extensive experiments on real-world and large-scale TSP instances demonstrate that DEITSP performs favorably against existing neural approaches in terms of solution quality, inference latency, and generalization ability. Our code is available at hrefhttps://github.com/DEITSP/DEITSPhttps://github.com/DEITSP/DEITSP.