{"id":"7474f3f8-ea0a-4941-b6f3-a29d566add62","arxiv_id":"2501.13767","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A one-step discrete diffusion model with an alternating add/remove noise schedule, paired with a dual-modality graph transformer, matches or beats prior neural TSP solvers in quality and speed.","lead":"DEITSP is a diffusion-based neural solver that predicts TSP tours in one fast denoising step, then refines by exploring multiple candidate tours. It reports near-optimal solutions up to 1000 nodes and strong generalization to real-world instances, faster than prior diffusion solvers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's inference loop adds noise around the ground-truth optimal tour a0, which is unavailable at test time; if the released code does the same, the reported quality/generalization results are not from a deployable solver.","rationale":"The reader's verdict is CONDITIONAL and lists the ambiguous `a_0` in Algorithm 2 among several issues, but its weakest_assumption focuses on distribution shift. I regard the Algorithm 2 ground-truth reference as the single most load-bearing concern because it sits exactly at the interface between the claimed method and the evidence: the iterative add/remove-noise mechanism, the multiple-solution aggregation, and the zero-shot generalization results all assume that the network can be re-noised from its own previous output. If line 7 actually uses the ground-truth optimal tour, then the inference loop is an oracle-aided procedure and Tables 1–3 do not measure the proposed solver at all; the runtime comparisons would also be meaningless because the expensive part (searching for the optimal a0) is assumed given. If, as the surrounding text suggests, line 7 is a typo for the predicted heatmap, the issue is addressable, but the exact form of the corrected distribution matters: sampling from a categorical distribution parameterized by a continuous heatmap is not the same as sampling from a one-hot row vector times Q_t, and the ablation in Table 4 could be sensitive to that choice. This is why the first check should be to run the released code with the ground-truth tour withheld and compare against the published gaps. I do not claim the authors are dishonest; the pseudocode may simply be sloppy. But as written, the paper does not describe a deployable inference algorithm, and resolving this should be an explicit condition for acceptance. The other reader concerns (missing lambda, no error bars, baseline fairness, one runtime inconsistency) are secondary and do not change this assessment. If the code check confirms the corrected behavior preserves the published gaps, the conditional verdict can be lifted after minor revisions; if not, the central claim fails.","tokens_in":23336,"tokens_out":8764,"duration_ms":77723,"concrete_test":"Inspect the released code and instrument the inference loop corresponding to Algorithm 2, logging the tensor passed as the categorical parameter in line 7. Then rerun the TSP100 and TSPLIB experiments from Tables 1 and 3 with the ground-truth optimal tour `a_0` withheld, replacing line 7's parameter with the predicted heatmap `tilde_a0` (or the previous sample) and using the published seeds. Compare the Gap columns: if they stay within 0.1% of the published values, the `a_0` reference is a notation error and the central claim survives; if gaps degrade materially (e.g., >0.5% on TSP100 or >1% on TSPLIB), the published numbers depend on oracle access to optimal solutions.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Algorithm 2 (Section 3.4) is the specification of the deployed inference procedure, but its line 7 reads `a_t ~ Cate(a_t ; p = a_0 Q_t)`, where `a_0` is the ground-truth optimal tour used in training (Algorithm 1, line 3). At test time, `a_0` is unknown; hence the inference loop as written re-noises around the optimal solution rather than around the previous denoising output. The accompanying text (Section 3.4.1) says the method 'add[s] noise to the denoised data from the previous time step,' so the pseudocode is internally inconsistent: either the paper misdescribes the algorithm, or the reported results are obtained with oracle access to the optimal tour. This matters because the central empirical claim—single-step denoising plus iterative add/remove noise achieving high quality and zero-shot generalization—depends on the input to line 7 being obtainable without knowing the answer. A corrected line would need to sample from a categorical distribution whose parameter is the predicted heatmap (e.g., `tilde_a0 Q_t`), which is a different stochastic process and may change the exploration/refinement behavior shown in Tables 1–3.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DEITSP, a non-autoregressive diffusion-based solver for two-dimensional Euclidean TSP. The method trains a dual-modality graph transformer to denoise corrupted adjacency matrices in a single step, using a consistency loss that ties predictions across noise levels. At inference, DEITSP iteratively adds and removes noise according to a custom schedule, aggregates the predicted heatmaps, and decodes them greedily with 2-opt to select the best tour. Experiments compare DEITSP against 16 neural baselines and Concorde on TSP20-1000, TSPLIB instances, and country-level real-world maps, claiming superior solution quality and inference speed, as well as zero-shot generalization to larger and non-uniform instances.","tokens_in":23649,"tokens_out":3799,"duration_ms":34018,"significance":"If the central claim holds, DEITSP would be a valuable NAR solver: single-step denoising plus iterative exploration provides a favorable solution-quality/latency trade-off, and the reported zero-shot generalization to TSP200-1000, TSPLIB, and real-world maps is practically relevant. The paper's strengths include extensive benchmarking, clear ablations of the network and iteration strategy, a public code release, and a genuine attempt to address the exploration problem in diffusion-based CO solvers. However, the inference pseudocode's use of ground-truth optimal tours makes the headline claim conditional on a clarification or correction; this issue is load-bearing for the paper's main contribution.","major_comments":[{"comment":"Algorithm 2 specifies the test-time inference procedure, but line 7 samples a_t from Cate(a_t; p = a0 Q_t), where a0 is the ground-truth optimal tour used in training (Algorithm 1, line 3). At test time a0 is unknown, so the pseudocode as written gives the solver oracle access to the optimum. This contradicts the accompanying text in Section 3.4.1, which says the method adds noise to the denoised data from the previous time step. If the released code follows the pseudocode, the reported results in Tables 1-3 and Table 6 are not from a deployable solver; if the code instead uses the predicted heatmap (e.g., sampling from tilde_a0 Q_t), the pseudocode must be corrected and the reported results confirmed to match that corrected procedure. This issue is central to the paper's empirical claim and must be resolved before the results can be interpreted.","section":"Section 3.4, Algorithm 2, line 7"},{"comment":"Several baselines are marked with a dagger (TRANSFORMER, CNN_Transformer, ELG, NAR4TSP) and are tested on TSP20/50 using pre-trained TSP50 weights provided by the original papers. Using TSP50-trained weights on TSP20 puts these baselines at a systematic disadvantage, which is not acknowledged in the main comparison. This weakens the claim that DEITSP outperforms all neural baselines on TSP20. Please either run these baselines with models trained on the same TSP20 distribution or clearly state this limitation in the experimental protocol and in the conclusions drawn from Table 1.","section":"Section 4.1, Table 1"},{"comment":"The central empirical claims are based on mean performance over a single run: no standard deviations, no number of seeds, and no statistical significance tests are reported. Several key comparisons involve very small gap differences (e.g., DEITSP(16 Iter) at 0.01% versus Sym-NCO at 0.04% on TSP50, or 0.10% versus 0.12% on TSP100), which may be within run-to-run noise. Please report means and standard deviations over at least five seeds for DEITSP and for the closest baselines, so the claimed improvements are not attributable to randomness.","section":"Tables 1-3 and Table 4"},{"comment":"The inverse-function schedule with c_i in [0.25, 1.5] is selected after comparing schedules (linear, cosine, inverse) on the TSP50 test set, which constitutes test-set model selection and may inflate the reported TSP50 results. Additionally, the loss weight lambda in Eq. (3) is never given a value, although it affects the balance between cross-entropy and self-consistency terms and is part of the reported hyperparameter configuration. Please specify lambda and either use a held-out validation set for schedule selection or justify why the schedule choice is not overfitting to the test distribution.","section":"Section 4.5, Figure 4 and Eq. (3)"}],"minor_comments":[{"comment":"The sentence \"? ] also indicates that the attention mechanism demonstrate slower rates of oversmoothing compared to GCNs\" contains an unresolved citation placeholder and a subject-verb agreement error; please fix the reference and wording.","section":"Section 3.3"},{"comment":"The baseline \"BQ-NCO\" is cited as \"[? ]\" in the text and does not appear in the reference list; this needs to be completed.","section":"Section 4.1, Baselines paragraph"},{"comment":"The header for DEITSP(16 Iter) is missing the \"(%)\" label on the Gap column, and the timing for eil51 (e.g., 2.646s for DEITSP(1 Iter)) is inconsistent with the sub-second timings of all other instances in that table; please check whether this reflects a one-time initialization cost or a typo.","section":"Table 6"},{"comment":"The phrase \"degressively insert them into the partial solution\" appears to be a typo for \"progressively insert\"; please correct it.","section":"Appendix A"},{"comment":"The ablation table reports Gap and Time but does not state the number of test instances or seeds; adding this information would improve interpretability of the reported differences.","section":"Section 4.5, Table 4"}],"recommendation":"major_revision","confidential_remarks":"The main risk in this manuscript is the Algorithm 2 ground-truth issue. I would ask the editor to require the authors to confirm, by inspecting the released code, whether inference actually uses the predicted heatmap or the ground-truth tour a0. If the code uses a0, the empirical results must be re-run with a corrected procedure; if the code already uses the predicted output, the pseudocode and text need a straightforward correction. The other concerns (seed-level statistics, baseline weight fairness, and the unreported lambda) are important but less likely to change the overall verdict once addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result is a non-autoregressive diffusion solver for Euclidean TSP that is fast and, in the reported tables, competitive with or better than prior neural diffusion methods. That is a real contribution if it holds. What's genuinely new: the combination of consistency-model self-consistency loss with a discrete diffusion formulation over adjacency matrices, a dual-modality graph transformer that processes node and edge features separately, and an inference-time scheme that alternates adding and removing noise to generate multiple candidate tours. The evaluation is extensive: 16 baselines, sizes 20 to 1000, plus TSPLIB and real-world country instances, with code released. The empirical claims look honestly presented, though the comparison has some rough edges.\n\nThe soft spots are not minor. Algorithm 2, line 7, specifies `a_t ~ Cate(a_t ; p = a_0 Q_t)` inside the inference loop. But `a_0` is the ground-truth optimal tour used in training (Algorithm 1) and unavailable at test time. The surrounding text says the method adds noise to the denoised data from the previous time step, which would mean using `~a_0 Q_t`. As written, the inference algorithm has oracle access to the optimum. This is not a cosmetic issue: if the released code does this, the solution-quality and generalization tables are not measuring a deployable solver. If it is a pseudocode error, the authors must correct it and verify that the reported numbers are unchanged. Without that, the central argument cannot be assessed.\n\nOther concerns are smaller but real. No standard deviations or seeds are reported, so gap differences of a few tenths of a percent may be noise. Some baselines (Transformer, DIFUSCO, T2TCO) are tested on TSP20/50 with pretrained TSP50 weights, which is not like-for-like. Table 6 has an odd runtime for DEITSP(1 Iter) on eil51 (2.6 s vs ~0.02 s elsewhere) that is unexplained. The loss weight lambda in Eq. (3) is unreported. The inverse-function noise schedule was chosen after comparing schedules on the test set, which is mild selection but should be disclosed.\n\nWho is this for? Researchers in learning-to-optimize and diffusion-based combinatorial solvers. It would get attention if the algorithm bug is resolved. My recommendation: send it to peer review, but with a strong request that the authors fix Algorithm 2, check the code, report variances, and rerun the mismatched baselines. As it stands, I would not rely on the results.","headline":"Fast NAR diffusion TSP solver with strong empirical claims, but Algorithm 2's inference loop is specified using the ground-truth tour a0; that must be fixed before the results can be trusted.","tokens_in":24158,"tokens_out":3386,"would_cite":false,"duration_ms":26227,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"DEITSP claims that a single denoising forward pass, followed by alternating noise re-addition and removal, yields near-optimal TSP solutions with far less inference time than prior diffusion-based solvers.","keywords":["Traveling Salesman Problem","diffusion models","non-autoregressive","combinatorial optimization","graph transformer","self-consistency","noise scheduling","zero-shot generalization"],"falsifier":"On a fixed set of TSP500 instances with known Concorde optima, run DEITSP with one iteration and with sixteen iterations and record the gap of every greedy-decoded candidate: if the one-iteration heatmap decodes to a gap far above the reported 2.15 percent, or if adding fifteen more candidates does not lower the gap toward that figure, the claim that one-step denoising is the source of solution quality would be refuted. An even sharper check is to remove 2-opt entirely and see whether single-step denoising plus greedy decoding alone can stay within a few percent of optimal on TSP100.","tokens_in":2192,"feed_emoji":"🗺️","tokens_out":7519,"duration_ms":115406,"temperature":0.7,"pith_summary":"DEITSP claims that a Traveling Salesman Problem solver does not need a long Markov-chain denoising process: a network trained to map any noised version of the optimal tour's adjacency matrix back to that matrix in one forward pass can already produce near-optimal heatmaps, and greedily decoding those heatmaps with 2-opt yields tours competitive with much slower autoregressive and diffusion baselines. The paper argues this works because the network is trained with a self-consistency objective across noise levels, so one denoising step is meaningful at any noise intensity, and because a dual-modality graph transformer lets six layers fuse node and edge information efficiently. It adds an inference loop that alternates noise removal with controlled noise re-addition under a decreasing inverse-function schedule, collecting several decoded tours and returning the shortest; this turns extra compute directly into better solutions. The reported consequence is that DEITSP reaches 0.00 to 0.10 percent gaps to Concorde on TSP20-100, generalizes zero-shot to TSP200-1000 and to real-world and TSPLIB instances, and does so with 7 to 28 times faster inference than strong diffusion and transformer baselines. If the claims hold, the method offers a practical knob: one iteration for speed, more iterations for quality.","feed_headline":"One denoising step finds near-optimal TSP tours fast","feed_subtitle":"A non-autoregressive diffusion model cuts TSP inference to seconds while keeping tours within 0.1 percent of optimal.","key_machinery":"The load-bearing object is the trained one-step denoiser $\\theta(a_t,g)$, a dual-modality graph transformer that takes node coordinates, a noisy adjacency matrix, and a time-step embedding, and outputs edge heatmaps $\\tilde{a}_0$. A discrete categorical diffusion process with transition matrix $Q_t$, parameterized by noise rates $\\beta_t$, creates noisy states $a_t \\sim \\mathrm{Cate}(a_0 \\bar{Q}_t)$, and self-consistency training enforces $\\theta(a_{t+k},g)=\\theta(a_t,g)=a_0$ across paired noise levels, with the squared term $\\lambda\\|\\theta(a_{t+k},g)-\\theta(a_t,g)\\|^2$ in Eq. (3). At inference the same network is reused in an alternating add/remove loop: uniform noise is denoised to a heatmap, a decreasing inverse-function schedule $\\tau_i$ chooses how much noise to add back, each denoised heatmap is greedily decoded with 2-opt, and the best tour among all decoded candidates is returned. The dual-modality graph transformer carries the feature extraction: edge features and node features are updated in separate mixing modules and fused through attention, allowing multi-hop information flow with only six layers.","core_discovery":"DEITSP treats TSP solution generation as edge classification: each edge of the tour is a Bernoulli variable, and the network is trained to predict the adjacency matrix of the optimal tour from a noised version of it. The training loss combines two cross-entropy terms tying the network's output to the Concorde ground truth at two noise levels with a self-consistency term that forces the outputs from different noise levels to agree, so a single forward pass can denoise from any point on the noise trajectory. At inference, the model starts from uniform noise, denoises in one step, greedily decodes a feasible tour, then repeatedly re-adds noise at schedule-controlled levels and denoises again, collecting every decoded tour and returning the shortest. The paper reports that this beats all sixteen neural baselines on TSP20-100 solution quality, achieves the best or second-best results on TSP200-1000 while being far faster than tree-search methods, and outperforms baselines on real-world country maps and TSPLIB instances.","pith_inferences":["An implication the authors leave implicit is that the alternating add/remove loop is effectively a randomized local-search restart mechanism: each noise level seeds a different greedy tour, so solution quality should track the diversity of the decoded candidates rather than the accuracy of any one denoising pass; a reader could test this by comparing DEITSP with 16 iterations against 16 independen","Because the supervised target is the Concorde optimal tour at the training size, the method's ceiling is tied to the availability of exact labels; a natural extension, not explored in the paper, is to replace the cross-entropy terms with an unsupervised or policy-gradient cost so the same one-step denoiser can be trained on TSP sizes where exact labels are unavailable.","The decreasing inverse-function noise schedule is motivated by the sparsity of TSP optimal adjacency matrices; the same sparse-solution argument applies to other permutation problems with Hamiltonian-cycle structure, such as vehicle routing or the quadratic assignment problem, so transferring the schedule and the candidate-collection loop to those settings is a concrete testable next step."],"forward_implications":["With 16 iteration steps, DEITSP reaches tour-length gaps of 0.00%, 0.01%, and 0.10% to Concorde on TSP20, TSP50, and TSP100, while a single iteration step still beats every learning-based baseline in wall-clock time.","Trained on TSP100 and applied zero-shot, DEITSP gets the best gaps on TSP200 (0.40%) and TSP500 (2.15%) and the second-best gap on TSP1000 (3.68%), with the leading method's better result coming from a Monte-Carlo-tree-search solver that is far slower.","On real-world country maps and TSPLIB instances, DEITSP with 16 iterations achieves the lowest average gap among neural baselines: 0.85% on Japan, 1.89% on USA, 2.30% on Burma, and 0.78% on the 26 TSPLIB instances.","The ablation shows that the alternating add/remove iteration beats standard DDIM sampling: DEITSP's 1-step result outperforms DDIM's 10-step result, and DEITSP's 5-step result outperforms DDIM's 50-step result.","Users can choose 1, 4, or 16 iterations to trade a few seconds or minutes for better tours, because the same network is reused and each extra denoising pass adds one more candidate solution to the set."],"supporting_citations":[{"why":"Supplies the Concorde exact solver that generates the supervised ground-truth adjacency matrices used as training targets and the optimal-length values used for gap reporting.","marker":"[1]"},{"why":"Supplies the categorical transition-matrix formulation and Bernoulli noise addition for discrete diffusion, which DEITSP uses to build noised states $a_t$ from $a_0$.","marker":"[2]"},{"why":"Supplies the self-consistency principle that all states on a noise trajectory map to the same origin, which DEITSP uses to justify one-step denoising at any noise level.","marker":"[43]"},{"why":"The graph-based discrete diffusion TSP solver whose heatmap formulation, 2-opt decoding, and DDIM-style sampling DEITSP extends and competes against.","marker":"[44]"},{"why":"The graph-network non-autoregressive solver that established the supervised heatmap-prediction paradigm for TSP tours, which DEITSP's edge classification and greedy decoding build on.","marker":"[23]"},{"why":"Defines the standard DDIM multi-step Markov sampling paradigm that DEITSP's alternating add/remove iteration is designed to replace.","marker":"[42]"},{"why":"The gradient-guided diffusion solver, used as a baseline and as the representative DDIM-style iteration in the ablation that DEITSP outperforms.","marker":"[31]"},{"why":"Supplies the linear beta schedule with $\\beta_1=10^{-4}$ and $\\beta_T=0.02$ that controls how fast the discrete noise process converges to uniform.","marker":"[17]"}],"fun_headline_variants":["Diffusion model achieves near-optimal TSP tours in one denoising step","Non-autoregressive diffusion cuts TSP inference while keeping quality","One denoising step predicts optimal TSP tours fast","DEITSP: fast non-autoregressive diffusion for near-optimal TSP"],"cache_read_input_tokens":26240,"weakest_assumption_plain":"The load-bearing premise is that a network trained on TSP100 instances with Concorde-optimal adjacency matrices as targets, seeing only synthetically noised versions of those matrices, learns a single-step denoiser that stays accurate enough for greedy-plus-2-opt decoding when the test size grows to 1000 nodes or the node distribution shifts to real-world maps.","fun_headline_variants_meta":{"raw":{"variants":["Diffusion model achieves near-optimal TSP tours in one denoising step","Non-autoregressive diffusion cuts TSP inference while keeping quality","One denoising step predicts optimal TSP tours fast","DEITSP: fast non-autoregressive diffusion for near-optimal TSP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000284,"raw_usage":{"total_tokens":1711,"prompt_tokens":1016,"completion_tokens":695,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":632,"completion_tokens_details":{"reasoning_tokens":617}},"tokens_in":632,"tokens_out":695,"duration_ms":6429,"temperature":1.0,"reasoning_tokens":617,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:36:54.321335+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a fixed set of TSP500 instances with known Concorde optima, run DEITSP with one iteration and with sixteen iterations and record the gap of every greedy-decoded candidate: if the one-iteration heatmap decodes to a gap far above the reported 2.15 percent, or if adding fifteen more candidates does not lower the gap toward that figure, the claim that one-step denoising is the source of solution quality would be refuted. An even sharper check is to remove 2-opt entirely and see whether single-step denoising plus greedy decoding alone can stay within a few percent of optimal on TSP100.","supporting_citations":[{"cited_title":"Applegate, Robert E","cited_arxiv_id":null,"evidence_quote":"Supplies the Concorde exact solver that generates the supervised ground-truth adjacency matrices used as training targets and the optimal-length values used for gap reporting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the categorical transition-matrix formulation and Bernoulli noise addition for discrete diffusion, which DEITSP uses to build noised states $a_t$ from $a_0$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The graph-based discrete diffusion TSP solver whose heatmap formulation, 2-opt decoding, and DDIM-style sampling DEITSP extends and competes against."},{"cited_title":"Joshi, Thomas Laurent, and Xavier Bresson","cited_arxiv_id":null,"evidence_quote":"The graph-network non-autoregressive solver that established the supervised heatmap-prediction paradigm for TSP tours, which DEITSP's edge classification and greedy decoding build on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The gradient-guided diffusion solver, used as a baseline and as the representative DDIM-style iteration in the ablation that DEITSP outperforms."}],"review_version":1}