{"id":"36bb011a-62dc-4509-83c4-32e465076ff2","arxiv_id":"2412.13858","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"IDEQ improves neural TSP solving by applying Hamiltonian reconstruction and 2-opt during diffusion inference and retraining on 2-opt-equivalent near-optimal tours, achieving new state-of-the-art optimality gaps among neural methods.","lead":"IDEQ is a diffusion-model solver for the Traveling Salesman Problem that enforces the tour structure during generation and fine-tunes existing models on near-optimal tours. On random instances of 500 and 1000 cities it reports optimality gaps of 0.3% and 0.5%, and on some TSPlib instances it finds slightly shorter tours than the LKH3 heuristic.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's core retraining objective is not implemented as stated: two random 2-changes from the optimum do not sample the claimed uniform distribution over the 2-opt equivalence class, so the mechanism behind the reported retraining gains remains unidentified.","rationale":"The reader's weakest assumption is exactly this: the two-2-change implementation does not approximate a uniform distribution over the 2-opt equivalence class. My stress-test concurs, and I frame the issue as a mechanism-attribution failure. The empirical results in Tables 1, 2, and 4 are internally consistent, the ablations are informative, and the TSPlib comparison against LKH3 is disclosed as using LKH3 default settings rather than true optimality for the larger instances. Thus I do not see a ground for rejecting the headline empirical claim. However, because the paper's stated training objective is not what is implemented, the central methodological contribution is not established; a concrete retraining experiment with true equivalence-class sampling would settle whether the effect is real and attributable. This is the same concern the reader identified, so the CONDITIONAL verdict remains appropriate.","tokens_in":14951,"tokens_out":9511,"duration_ms":94497,"concrete_test":"Retrain from the same DIFUSCO TSP-100 checkpoint on TSP-500 with three label-generation schemes: (a) the current two-random-2-change labels; (b) samples drawn from the claimed uniform distribution over the true R2-equivalence class, obtained by a sufficiently long random walk of 2-changes followed by complete 2-opt and rejection unless the 2-opt fixed point is exactly the optimal tour; (c) a control of random Hamiltonian tours matched to (a) in length distribution. If (a) and (b) produce statistically indistinguishable optimality gaps on the 2048-instance TSP-500 test set and both outperform (c), the two-change heuristic is a sufficient surrogate and the empirical results survive. If (b) is better than (a), the paper's stated objective is not the mechanism driving the reported gain and the central methodological claim fails as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.3 defines the training target as a uniform distribution over the R2-equivalence class of the optimal tour, i.e., tours from which repeated applications of the 2-opt operator reach the optimum. The actual implementation, described in the same section and in Section 3.4, is \"2 consecutive randomly sampled 2-change\" applied to the optimal tour. A 2-change is a perturbation move, not an application of the 2-opt local-search operator; a tour obtained this way is not guaranteed to be in the claimed orbit, and the paper gives no argument that two random 2-changes avoid the local minima it itself warns about. The claim that this \"creates a set of diverse members of the equivalence class\" is therefore unsupported. The ablation in Table 4 shows that retraining with this label transformation improves the final gap, but that gain cannot be attributed to the stated equivalence-class objective: it could equally come from label smoothing, increased diversity, or simply training the model to produce tours that 2-opt can repair. The measured SOTA numbers in Tables 1 and 2 are internally consistent and include the appropriate 2-opt post-processing, so the empirical central claim is plausible; the load-bearing weakness is that the paper's principal methodological novelty, the uniform-orbit objective, is not what is actually trained. This is a scientific attribution failure rather than a direct invalidation of the reported results.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes IDEQ, a discrete diffusion model for the Euclidean TSP built on DIFUSCO and T2TCO. IDEQ introduces two modifications: at inference time, the denoising process is guided by applying a Hamiltonian reconstruction operator followed by 2-opt at every reverse step (Section 3.2); and at training time, the later curriculum stages are fine-tuned with a target distribution that, according to the paper, is uniform over the equivalence class of the optimal tour under the 2-opt operator, but is implemented by applying two random 2-change perturbations to the optimal tour (Sections 3.3 and 3.4). Experiments on random TSP-500 and TSP-1000 instances and on TSPlib report improved optimality gaps over DIFUSCO and T2TCO, with gaps of 0.3% and 0.5% respectively, and on two TSPlib instances the method finds tours shorter than the LKH3 reference.","tokens_in":15259,"tokens_out":7880,"duration_ms":62968,"significance":"If the reported results are reproducible, the paper would be a meaningful step for neural TSP solvers: it demonstrates that a diffusion model with 2-opt post-processing can approach the solution quality of classical heuristics on structured instances, and the larger test set and re-run baselines strengthen the empirical comparison. The ablation study (Table 4) attempts to separate the contributions of the two ingredients, which is commendable. However, the stated methodological novelty of ingredient 2 is not actually what is implemented, so the attribution of the gains to the uniform-orbit objective is unsupported. The empirical central claim is plausible but the paper needs either a corrected implementation or a revised claim and analysis.","major_comments":[{"comment":"The training objective is stated as a uniform distribution over the equivalence class of the optimal tour under the 2-opt operator R2, but the implementation samples tours by applying two randomly chosen 2-change moves to the optimal tour. A 2-change is a single edge-exchange move, while R2 in Section 2.1 is the local-search operator that repeatedly applies the most length-decreasing 2-change until a local optimum; a tour obtained from two random 2-changes need not lie in the equivalence class from which R2 converges to the optimum, and the text itself acknowledges that inverting 2-changes can generate local minima. The claim in Section 3.3 that this 'creates a set of diverse members of the equivalence class' is therefore unsupported. Because this objective is the core of key ingredient 2, the improvements in Table 4 cannot be attributed to the stated uniform-orbit target; they may result from label smoothing or from training the model to produce tours that 2-opt can repair. The authors should either implement the actual uniform sampling over the equivalence class or reframe the method as an approximate label augmentation with an explicit justification and an analysis of the bias it introduces.","section":"Section 3.3 and Section 3.4"},{"comment":"The sentence 'while creating O(N−1) local minimal which is at least one order of magnitude lower than the number of epoches for TSP instance ≥ 500 as considered here' is incomplete and does not provide an argument for the adequacy of the two-2-change approximation. It does not define what quantity is O(N−1), how the number of local minima is counted, or why comparing it with the number of training epochs is relevant to whether the sampled set is representative of the equivalence class. This is load-bearing because it is the only justification offered for replacing the uniform distribution by two random 2-changes; please replace it with a precise statement, ideally with a formal or empirical analysis of the distance between the implemented label distribution and the claimed uniform distribution.","section":"Section 3.3"}],"minor_comments":[{"comment":"The phrase 'up to a 7397 cities' should read 'up to 7,397 cities'.","section":"Section 1"},{"comment":"The header '100- 104' is ambiguous; it should be '100 to 10^4' or similar.","section":"Table 2"},{"comment":"There are missing citations indicated by '[?]' (for example, 'and further expanded by various authors [5, 26, 20, ?]' and in the reference list); these should be completed.","section":"Sections 2.2 and 2.3"},{"comment":"The term 'optimality gap' is used for comparisons against LKH3 reference tours; for fl1577 and fl3795 the reported gaps are negative. Please state explicitly that these gaps are relative to the LKH3 reference (default settings) rather than to a proven optimum, to avoid confusing readers.","section":"Section 4.3 and Appendix A"},{"comment":"The reported running times for the IDEQ rows appear inconsistent with Table 1: IDEQ 0.41% is paired with 3.7 mn in Table 4 but with 1.3 mn in Table 1 for the non-sampling configuration, and similar discrepancies appear for TSP-1000. Please check and correct these entries.","section":"Section 4.4, Table 4"},{"comment":"The claim that T2TCO's gradient-based search is not responsible for its improvement is stated without experimental support; since this motivates the IDEQ inference design, a brief description of the experiment would strengthen the paper.","section":"Section 2.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript appears to be an INRIA research report version and contains a number of typos and incomplete citations; however, the main concern is the mismatch between the claimed training objective and the implementation, which is a scientific attribution issue rather than a simple presentation problem. I recommend major revision. In addition, the claim of outperforming LKH3 on fl1577 and fl3795 should be treated cautiously, as LKH3 with default settings is a single run and the paper does not report LKH3 with more extensive search; this does not affect the main empirical conclusions but should be phrased carefully."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nYou should know about this paper because it reports the strongest numbers yet for a neural diffusion solver on the TSP: 0.29% gap on TSP-500 and 0.49% on TSP-1000 with sampling, beating T2TCO by a wide margin, and the first reported case of a neural method beating LKH3 on two TSPlib instances. The ablation study is real and separates the two ingredients. If those numbers are reproducible, this is a meaningful step for neural combinatorial optimization.\n\nWhat is genuinely new is the combination: (1) injecting a Hamiltonian reconstruction and 2-opt into the diffusion inference loop, and (2) fine-tuning the later curriculum stages on optimal tours perturbed by two random 2-changes. The first ingredient is in the spirit of the usual post-processing, but applying it inside the iterative denoising is a concrete change. The second is essentially a data augmentation trick, but the empirical gain is substantial and the authors show it is independent of the inference change.\n\nThe soft spots are in the framing. The abstract says the retraining objective is a uniform distribution over Hamiltonian tours whose orbits by 2-opt converge to the optimal tour. That is not what is implemented: Section 3.3 literally says \"we use only 2 applications of 2-change.\" Two random 2-changes do not uniformly sample the equivalence class, and there is no argument that they avoid the local minima the paper itself warns about. So the reported gains cannot be attributed to the equivalence-class objective. The gains may come from label smoothing, increased diversity, or simply providing tours that 2-opt can repair — all plausible, but unidentified. This is an attribution problem, not a falsification of the numbers.\n\nThe paper also makes a strong claim that T2TCO's gradient search is not responsible for its improvement, but gives no quantitative support. And the statement in Section 3.2 that the reconstruction operator leaves the optimal theta unchanged is confusing — you are not training with that operator, so the point is moot.\n\nWho should read this? Anyone working on neural TSP or diffusion for combinatorial optimization. It is a solid empirical paper with a clear ablation, but the methodological story needs rewriting. I would send it under conditional acceptance with a demand to either fix the description or provide evidence that the approximation captures the intended distribution.\n\nRegards.","headline":"Strong empirical results for a diffusion-based TSP solver, but the paper's headline mechanism — a uniform distribution over 2-opt orbits — is not actually implemented; the numbers still deserve a serious look.","tokens_in":15753,"tokens_out":2895,"would_cite":true,"duration_ms":25484,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","68T07","05C45"],"pacs":[],"model":"deepseek-v4-flash","headline":"IDEQ, a diffusion-based neural solver for the TSP, enforces Hamiltonian structure at every denoising step and retrains on the 2-opt equivalence class of optimal tours, reaching 0.3% optimality gap at 500 cities and beating LKH3 on two…","keywords":["diffusion models","traveling salesman problem","combinatorial optimization","2-opt","Hamiltonian tours","curriculum learning","TSPlib","neural solvers"],"falsifier":"Retrain the same IDEQ pipeline with labels drawn from a longer random walk in the 2-opt equivalence class instead of only two 2-changes; if the optimality gaps stay unchanged, the equivalence-class objective is not what causes the improvement, and if they improve, the two-change sampler is leaving performance unused.","tokens_in":14752,"feed_emoji":"🗺️","tokens_out":8149,"duration_ms":69765,"temperature":0.7,"pith_summary":"The paper proposes IDEQ, a diffusion-model solver for the Euclidean Traveling Salesman Problem that improves on the DIFUSCO and T2TCO lines of work. Its first ingredient constrains the reverse diffusion: every predicted adjacency matrix is passed through a Hamiltonian-tour reconstruction operator and then refined by one 2-opt step, so the model never samples an invalid tour. Its second ingredient changes the training objective in the later curriculum stages: instead of teaching the network a single optimal tour per instance, IDEQ labels each instance with tours obtained by two random 2-changes from the optimum, i.e. members of the equivalence class of tours that 2-opt collapses to the optimum. On random instances IDEQ reports a 0.3% optimality gap (excess tour length over the optimum) at 500 cities and 0.5% at 1,000 cities, which the paper counts as a new state of the art for neural methods, and on TSPlib it is close to LKH3, finding shorter tours than LKH3 on instances fl1577 and fl3795.","feed_headline":"Diffusion TSP solver beats LKH3 on two classic instances","feed_subtitle":"A neural diffusion model hits 0.3% optimality gap at 500 cities and rivals LKH3 on TSPlib.","key_machinery":"The load-bearing object is the 2-opt equivalence relation on Hamiltonian tours: two tours are equivalent when repeated applications of the 2-opt operator send one to the other, and every locally optimal tour is a fixed point of that operator. IDEQ uses this relation in two places: at inference, the operator $R_2 \\circ H$ is applied at every reverse-diffusion step to guarantee Hamiltonian validity and local improvement; at training, two random 2-change moves from the optimal tour generate labels from the equivalence class, so the network learns a distribution over many tours that all collapse to the optimum. The argument works because the inference projection changes only the estimator of $x_0$ and not the training loss, so existing DIFUSCO checkpoints can be fine-tuned rather than retrained from scratch.","core_discovery":"The central claim is that a diffusion model for the TSP becomes markedly better when the solution-space geometry is respected in both directions of the process. During generation, the standard denoising step is replaced by the composition $\\hat{x}_0 = R_2 \\circ H \\circ NN_\\theta(x_t, t, I)$, where $H$ reconstructs a Hamiltonian tour from the predicted heatmap and $R_2$ applies 2-opt; because an optimal tour is a fixed point of 2-opt, this projection lets every intermediate prediction remain a genuine tour and pushes the walk toward locally optimal adjacency structures. During training, the one-point target distribution on the optimal tour is replaced by a uniform distribution over its 2-opt equivalence class, implemented by sampling two random 2-changes from the optimal tour as the label. The authors argue that this enlarges the support of the target distribution, making the learned denoiser more robust, and their experiments attribute the final gap reduction to the two ingredients adding up independently.","pith_inferences":["A consequence the authors leave implicit is that the practical value of the diffusion model may lie mainly in producing a good starting tour for local search: iterating 2-opt from a random Hamiltonian tour alone leaves gaps of a few percent, so the diffusion component is what makes the small final gaps possible.","The sampler uses only two random 2-changes per label rather than the full uniform distribution over the equivalence class; testing longer random walks in the class would show whether the reported gains track the intended objective or merely the diversity of a few nearby tours.","The LKH3 comparisons use default solver settings, so a natural extension is to measure how much of the two 'wins' survives when LKH3 is tuned for those specific instances.","The recipe's applicability claim suggests a concrete test: apply the same constrained-diffusion plus equivalence-class fine-tuning to vehicle routing or maximum cut, where the corresponding local-search operator plays the role of 2-opt."],"forward_implications":["If the reported gaps hold, a neural diffusion solver with 2-opt post-processing becomes the first neural method effectively competing with LKH3-class heuristics on structured TSP instances with thousands of cities.","The gains come from fine-tuning existing DIFUSCO checkpoints with a modified objective, not from training a new diffusion model from scratch, so the improvement is comparatively cheap.","The two ingredients are additive: the ablation study shows that inference-time projection and equivalence-class retraining each improve T2TCO, and combining them yields IDEQ.","Because optimal tours are 2-opt fixed points, the same equivalence-class retraining recipe transfers to other combinatorial problems that admit a similar invertible local transformation.","Reduced variance across repeated solves indicates that constraining the search space makes the denoising process less sensitive to the initial random noise."],"supporting_citations":[{"why":"DIFUSCO supplies the base discrete diffusion solver, the TSP-100 checkpoint, and the TSP-500/TSP-1000 training sets that IDEQ fine-tunes.","marker":"[27]"},{"why":"T2TCO provides the inference procedure with partial re-noising and denoising that IDEQ adopts and improves with its projected steps.","marker":"[15]"},{"why":"LKH3 is the classical heuristic baseline whose TSPlib tour lengths and default-settings performance IDEQ compares against, beating it on fl1577 and fl3795.","marker":"[4]"}],"fun_headline_variants":["Diffusion TSP model leverages solution geometry","Neural TSP solves 1577-city instance beat LKH3","IDEQ: diffusion TSP hits 0.3% gap at 500 cities","2-opt guided diffusion matches LKH3 on TSPlib","Uniform 2-opt targets train better TSP diffusion"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The retraining gain rests on the assumption that sampling two random 2-changes from the optimal tour is a faithful enough stand-in for a uniform distribution over the whole 2-opt equivalence class of that tour.","fun_headline_variants_meta":{"raw":{"variants":["Diffusion TSP model leverages solution geometry","Neural TSP solves 1577-city instance beat LKH3","IDEQ: diffusion TSP hits 0.3% gap at 500 cities","2-opt guided diffusion matches LKH3 on TSPlib","Uniform 2-opt targets train better TSP diffusion"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000671,"raw_usage":{"total_tokens":3095,"prompt_tokens":1022,"completion_tokens":2073,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":1984}},"tokens_in":638,"tokens_out":2073,"duration_ms":13397,"temperature":1.0,"reasoning_tokens":1984,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:42:47.442295+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Retrain the same IDEQ pipeline with labels drawn from a longer random walk in the 2-opt equivalence class instead of only two 2-changes; if the optimality gaps stay unchanged, the equivalence-class objective is not what causes the improvement, and if they improve, the two-change sampler is leaving performance unused.","supporting_citations":[{"cited_title":"& Yang, Y","cited_arxiv_id":null,"evidence_quote":"DIFUSCO supplies the base discrete diffusion solver, the TSP-100 checkpoint, and the TSP-500/TSP-1000 training sets that IDEQ fine-tunes."},{"cited_title":"& Yan, J","cited_arxiv_id":null,"evidence_quote":"T2TCO provides the inference procedure with partial re-noising and denoising that IDEQ adopts and improves with its projected steps."},{"cited_title":"An Extension of the Lin-Kernighan-Helsgau n TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems","cited_arxiv_id":null,"evidence_quote":"LKH3 is the classical heuristic baseline whose TSPlib tour lengths and default-settings performance IDEQ compares against, beating it on fl1577 and fl3795."}],"review_version":1}