{"id":"3c947a42-99ed-4d80-a45f-57de8ad800fb","arxiv_id":"2412.15537","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A Delaunay-triangulation-based framework scales pretrained TSP solvers to 10,000-node instances without retraining, using subgraph fusion and a warm-up heuristic.","lead":"This paper presents a way to make existing AI-based traveling-salesman solvers handle much larger problems (up to 10,000 points) by splitting the map into connected pieces, solving each piece, and merging the results with a heatmap. The approach could make route-planning algorithms for drones and delivery vehicles more practical at real-world scales.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The SOTA claim rests on an unverified geometric assumption: Eq. (3) zeroes all non-Delaunay edges, and the warm-up in §III-F cannot systematically resurrect them, so no edge outside the DT can reliably be proposed by the search.","rationale":"The reader's verdict is CONDITIONAL, and I agree. The single most load-bearing point is not just typographical: it is the DT-containment assumption, because without it the divide-and-conquer construction cannot reach a valid tour. My reading of §III-F sharpens the reader's concern: the text promises a back-propagation remedy for non-DT edges, but Eq. (3) zeroes those edges before the warm-up loop, and the selection criterion Aij=Pij*dij makes them invisible. The only escape route is accidental via 2-OPT, which is not guaranteed and not quantified. This is an internal tension in the method as specified, not merely a missing citation. The proposed check is cheap and decisive: either every optimal edge used in the benchmark experiments is in the DT, or the framework must demonstrate recovery of zeroed edges. Without that, the SOTA results are conditional on a geometric fact that the paper neither proves nor measures. I am not calling for rejection because the idea is plausible and the reader's requested corrections (fix Table I, report hyperparameters) are also necessary; the DT check is a sufficient additional condition to move from conditional to acceptance. Hence UNCHANGED relative to the reader's CONDITIONAL verdict.","tokens_in":12118,"tokens_out":11432,"duration_ms":109992,"concrete_test":"Using the provided code and benchmark generator [35], for all TSP-500/1000/10000 instances compute near-optimal tours with Concorde or LKH-3, construct the Delaunay triangulation D, and run DTTGF's warm-up exactly as implemented. Count (1) the fraction of optimal-tour edges with Dij=0 before warm-up, and (2) how many of those zeroed edges receive nonzero Pij after warm-up. If any instance has an optimal edge outside D that remains at Pij=0, the framework cannot propose that edge and the 'outperforms SOTA' claim lacks a necessary condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that DTTGF lets any embedded TSP solver scale to 10,000 nodes and 'consistently outperforms SOTA' (Abstract, Table I)—requires that a near-optimal tour's edges survive the Delaunay filter. Eq. (3) sets Pij = 0 for every edge not in the DT, so the final heatmap assigns zero probability to all non-DT edges. The only support offered is an appeal to refs. [28]–[30] and [32]; the paper never reports what fraction of optimal-tour edges are contained in the DT on TSP-500/1000/10000, nor what happens on instances where some are not. This is the reader's weakest assumption, and it is load-bearing: if even one long optimal edge lies outside the DT, the fused heatmap cannot propose it. The warm-up section claims to fix exactly this: 'potential edges not in the DT results but filtered during fusion can enhance their P-value via back-propagation' (§III-F). It cannot, as written. After Eq. (3), a non-DT edge has Pij=0, hence Aij=Pij*dij=0; the warm-up loop selects the edge with largest Aij, so a zeroed edge is never directly selected or updated. It could re-enter only if some 2-OPT move happens to create it in Tb or Tdel and the Eq. (5) update then applies to it. Long, non-local edges—precisely the ones at risk—are unlikely to appear in such local improvements. Thus the warm-up does not relieve the DT-containment assumption; it merely adds an untested recovery path. Without a quantitative containment check, the SOTA claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces DTTGF, a training-free divide-and-conquer framework for extending existing TSP solvers to large instances (up to 10,000 nodes). The pipeline is: Delaunay triangulation of the instance, graph sampling into subgraphs, solving subgraphs with an embedded one- or two-stage solver, merging sub-solutions/sub-heatmaps into a global heatmap, a \"warm-up\" pseudo-reinforcement-learning correction of the heatmap, and a final search by S+2-opt or MCTS. The authors embed Att-GCN, POMO, AM, and GCN into the framework and report average gaps of roughly 1–3% on TSP-500, TSP-1000, and TSP-10000, outperforming recent learning-based baselines.","tokens_in":12508,"tokens_out":8231,"duration_ms":41549,"significance":"The framework addresses a real bottleneck: learned TSP solvers trained on small instances do not scale to thousands of nodes. If the numerical results hold, the contribution is valuable because it is solver-agnostic and does not require retraining or fine-tuning; the use of standard benchmarks, the inclusion of multiple embedded solvers, a public code link, and ablation of the warm-up module are all positive features. However, the paper currently contains load-bearing reporting errors and an internally inconsistent update rule, so the empirical claims cannot be taken at face value until those are fixed.","major_comments":[{"comment":"The warm-up back-propagation formula is internally inconsistent. The text says Tdel is the improved tour and that back-propagation should \"enhance\" promising edges, yet the assignments α=1 for edges in Tb and α=−1 for edges in Tdel add probability mass to the baseline tour and remove mass from the improved tour, the opposite of the intended reinforcement. The exponent D(Tb)−D(Tdel)/D(Td) also uses an undefined quantity D(Td). Since the warm-up is claimed to improve accuracy and to recover edges removed by the Delaunay filter, this formula must be corrected and the ablation re-run.","section":"§III-F, Eq. (5)"},{"comment":"The Delaunay filter is load-bearing but unvalidated. Setting Pij=0 for every non-DT edge makes it impossible for the fused heatmap to propose any edge outside the DT; the paper cites refs. [28]–[30] and [32] but does not report, for the benchmark suites, what fraction of optimal-tour edges are contained in the DT or what happens on instances where they are not. The warm-up cannot systematically repair this after zeroing because Aij=Pij*dij=0, so the argmax selection in §III-F never picks a zeroed edge; it can only re-enter accidentally via 2-opt moves. A quantitative containment check is required to support the SOTA claim.","section":"§III-E, Eq. (3)"},{"comment":"Several entries in Table I are numerically impossible. Farthest Insertion on TSP-500 shows length 18.30 with drop 0.00% although the stated optimum is 16.55; DTTGF+POMO RL+MCTS shows length 24.77 with drop 9.40% (the correct gap relative to 16.55 is 49.70%); DTTGF+POMO RL+WU+S+2-OPT shows length 1.03, below any feasible Euclidean tour length. These errors make the headline comparisons unreliable and require a full re-computation of the table.","section":"Table I"},{"comment":"The warm-up time reporting is contradictory. The ablation text states warm-up times of 1.22s, 7.23s, and 5.12min for TSP-500/1000/10000, while Table I lists supplementary warm-up times of 2.70m, 15.44m, and 1.58h for the same datasets. If one set is per-instance and the other cumulative, the caption must say so; as written the numbers are incompatible and prevent assessment of the claimed time efficiency.","section":"Table I and §IV-C"},{"comment":"The framework depends on hyperparameters that are not specified: subgraph size and overlap, warm-up iteration count or stopping criterion, learning rate β, and the MCTS and S+2-opt budgets. These settings govern both solution quality and total runtime, so the abstract's scalability and efficiency claim cannot be reproduced from the paper alone; report them in the main text or appendix.","section":"§III-C, §III-F, Algorithm 1"}],"minor_comments":[{"comment":"The title contains a typo (\"Planing\" should be \"Planning\"), and throughout the text \"UA V\" appears with an unintended space (e.g., Abstract and Section I).","section":"Title and throughout"},{"comment":"References [15] and [35] appear to refer to the same Att-GCN paper with inconsistent author strings and years; please merge them and use one consistent citation.","section":"References [15] and [35]"},{"comment":"Table II's header says \"embedding AM and GCM\", but the rows and the surrounding text refer to GCN; this should be corrected.","section":"Table II"},{"comment":"In Eq. (1), the denominator Sij is the number of times edge (i,j) was selected across subgraphs, so for any edge never selected the probability is formally 0/0; please define how such entries are handled.","section":"§III-E, Eq. (1)"},{"comment":"The phrase \"potential edges not in the DT results but filtered during fusion can enhance their P-value via back-propagation\" is the only description of the recovery mechanism; after correcting Eq. (5), please also provide a step-by-step numerical example to explain how a zero-probability edge can receive a nonzero update.","section":"§III-F"}],"recommendation":"major_revision","confidential_remarks":"The table errors are extensive, and some citations do not support the claims (ref. [32] is a cross-modality attack paper, not a DT-TSP reference; refs. [15] and [35] duplicate the same source). I would ask the authors to re-verify all numerical entries and citations before resubmission, and to add the requested DT-containment experiment even if the code is available."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is genuinely useful: use Delaunay triangulation to extract overlapping subgraphs, let an existing solver produce sub-solutions or sub-heatmaps, fuse them into a global heatmap, and search. Embedding POMO, Att-GCN, AM, and GCN this way and showing large-instance gains without retraining is real value, and the ablation separating the warm-up contribution is the right instinct. The code link is a plus.\n\nThe problems start with the numbers. Table I lists a TSP-500 length of 1.03 for DTTGF+POMO with warm-up and S+2-OPT; the optimum is 16.55. That is not a typo in a decimal place, it is an impossible value. Farthest Insertion is given a 0.00% drop on TSP-500 when its length is 18.30 versus the 16.55 optimum, which should be about 10.6%. The warm-up times in Table I (2.70m, 15.44m, 1.58h) contradict the ablation section, which reports 1.22s, 7.23s, and 5.12min. A reader cannot take the SOTA claim seriously until these are reconciled.\n\nThe stress-test concern about Eq. (3) holds up. Setting Pij=0 for every non-DT edge makes Aij=Pij*dij zero, so the warm-up loop that selects the largest Aij can never pick a non-DT edge. The paper's claim that filtered edges can \"enhance their P-value via back-propagation\" is therefore not supported as written. The warm-up may still improve quality by cleaning misleading DT edges, and the results without warm-up are already decent, but the paper should either remove that claim or redesign the update so zeroed edges can re-enter.\n\nWhat is missing: any quantification of how many optimal-tour edges actually lie in the DT on these benchmarks, and any statement of subgraph size, overlap, beta, iteration count, or search budgets. The first is load-bearing for the whole DT-filter step; the second is needed for reproducibility even with code.\n\nThis deserves a serious referee, but it needs major revision first. The framework is worth engaging; the reporting is not.\n\nRecommendation: send to peer review, but require corrected tables, a fix or explicit retraction of the warm-up recovery claim, and a DT-containment analysis before acceptance.","headline":"A practical DT-based framework for scaling TSP solvers, but the tables contain impossible numbers and the warm-up's claimed ability to restore non-Delaunay edges is not supported by its own equations.","tokens_in":13058,"tokens_out":2629,"would_cite":false,"duration_ms":25145,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a Delaunay-triangulation-based divide-and-conquer framework can extend any existing TSP solver to instances of up to 10,000 points without retraining, producing tours that match or beat specialized large-scale TSP…","keywords":["UAV route planning","large-scale TSP","Delaunay triangulation","graph fusion","heatmap","reinforcement learning","divide-and-conquer","combinatorial optimization"],"falsifier":"Run an exact solver on several 1,000- to 10,000-city Euclidean TSP instances, compare every optimal-tour edge against the Delaunay triangulation, and count the fraction of optimal edges missing from the triangulation; if that fraction is above a small threshold, or if removing the DT filter materially shortens DTTGF's tours on the benchmark sets, the containment premise fails.","tokens_in":11917,"feed_emoji":"✈️","tokens_out":6746,"duration_ms":46802,"temperature":0.7,"pith_summary":"The paper sets out to close the scalability gap between TSP solvers trained on small instances and the large patrol-planning instances that arise in UAV route planning. It proposes DTTGF, a three-stage framework that decomposes a large Euclidean TSP instance along its Delaunay triangulation, solves the resulting overlapping subgraphs with an off-the-shelf TSP solver, and fuses the sub-results into a global heatmap of edge probabilities. A warm-up procedure, cast as pseudo-reinforcement learning, then prunes misleading edges and restores promising ones before a standard search (S+2-OPT or MCTS) produces the final tour. The authors claim that with two very different embedded solvers—the two-stage supervised Att-GCN and the one-stage reinforcement-learning POMO—the framework consistently outperforms state-of-the-art large-scale methods (DIMES, H-TSP, Att-GCN) on TSP-500, TSP-1000, and TSP-10000 benchmarks, with deviations from optimality of about 1–3%. The central payoff of the claim is that any existing or future TSP solver can be reused for large-scale routing without retraining or fine-tuning.","feed_headline":"Delaunay triangulation lets small TSP solvers scale to 10,000 cities","feed_subtitle":"A training-free wrapper that embeds existing solvers and beats specialized large-instance methods on benchmark tours.","key_machinery":"The Delaunay triangulation of the city set is the load-bearing object. It serves a dual role: as the adjacency guide for sampling overlapping subgraphs (preserving global edges that k-nearest-neighbour methods miss), and as a hard filter on the fused heatmap, setting $P_{ij}=0$ for every edge not in the triangulation (Eq. 3). The warm-up strategy, formulated as pseudo-reinforcement learning, defines a fitness $A_{ij}=P_{ij}\\times d_{ij}$, iteratively deletes the highest-fitness edge, re-solves with the S+2-OPT decoder, and back-propagates the tour-length gain via Eq. (5) with $\\alpha \\in\\{-1,0,1\\}$ depending on whether the edge belongs to the baseline tour, the new tour, both, or neither. This mechanism is what the paper claims upgrades any embedded solver to large-scale performance without retraining.","core_discovery":"The paper's core claim is that the Delaunay triangulation of the city set preserves enough of the optimal tour structure to serve as both a decomposition guide and a hard filter for large Euclidean TSP. Specifically, the framework zeroes out the heatmap probability of every edge that is not in the Delaunay triangulation (Eq. 3), on the strength of prior empirical evidence that optimal tours concentrate on triangulation edges. The fused heatmap from subgraph solutions is then refined by a warm-up loop that treats the heatmap as a policy: it repeatedly removes the edge with the largest fitness $A_{ij}=P_{ij}\\times d_{ij}$, re-solves with the sampling decoder plus 2-OPT, and back-propagates the tour-length improvement through Eq. (5) to adjust the probabilities of the removed edge and of tour edges. The authors report that this pipeline, with Att-GCN or POMO embedded, beats or matches all compared baselines on the three benchmark sizes, including large-instance specialists, and that the warm-up specifically rescues one-stage solvers like POMO, whose own scaling is otherwise poor.","pith_inferences":["The DT filter assumption implies the framework's success is tied to the geometry of Euclidean TSP; on non-Euclidean or clustered instances where optimal edges cross large empty regions, the filter could remove needed edges—a testable limitation.","The warm-up's fitness $A_{ij}=P_{ij}d_{ij}$ biases toward deleting long, infrequent edges; a natural extension would be to make the learning rate adaptive per instance or to replace the binary $\\alpha$ with a graded reward.","Because the framework is training-free, future improved neural solvers could be dropped in as a wrapper without re-engineering, yielding an ongoing performance dividend the paper does not claim explicitly.","The same triangulate-solve-fuse-warm-up loop might transfer to other Euclidean combinatorial problems such as capacitated vehicle routing, though the DT optimal-edge property would need re-checking there."],"forward_implications":["Any existing TSP solver that outputs tours or heatmaps can be embedded into DTTGF and extended to up to 10,000 cities with no additional training.","The DT filter plus warm-up yields tours within roughly 1–3% of the optimal benchmark length on TSP-500 and TSP-1000, and outperforms DIMES, H-TSP, and Att-GCN on TSP-10000 in the reported comparisons.","POMO, a one-stage solver that fails to scale to TSP-1000 and TSP-10000 on its own, becomes competitive when embedded, which suggests the framework can rescue otherwise unscalable solvers.","The framework is agnostic to the solver's training paradigm, as demonstrated by successful embedding of a supervised two-stage model (Att-GCN) and a reinforcement-learning one-stage model (POMO)."],"supporting_citations":[{"why":"Supplies the empirical evidence that optimal TSP tours tend to lie within the Delaunay triangulation, justifying the filter in Eq. (3).","marker":"[28]"},{"why":"Establishes that good triangulations yield good tours, the premise for using DT as a subgraph extractor.","marker":"[29]"},{"why":"Recent confirmation of DT-guided TSP solving, supporting the framework's reliance on DT containment.","marker":"[30]"},{"why":"The two-stage Att-GCN solver embedded in the framework; also the divide-and-conquer baseline that DTTGF improves on via DT-based decomposition.","marker":"[15]"},{"why":"The DIMES baseline and the source of the benchmark datasets and baseline numbers used in comparison.","marker":"[27]"},{"why":"Supplies the Attention Model baseline and the S+2-OPT decoder used in the warm-up and final search.","marker":"[10]"},{"why":"The POMO one-stage reinforcement-learning solver that DTTGF rescues to large-instance performance.","marker":"[24]"}],"fun_headline_variants":["Delaunay fusion scales TSP solvers to 10,000 cities","Scaling TSP to 10k cities: Delaunay extraction and graph fusion","Training-free Delaunay framework extends TSP solvers to 10k points","Small TSP solvers go large: Delaunay and graph fusion do the trick","Delaunay triangulation unlocks 10,000-point TSP for existing solvers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The framework assumes that every edge of an optimal large-scale Euclidean TSP tour lies within the Delaunay triangulation of the city set, so discarding all other edges cannot remove needed tour edges.","fun_headline_variants_meta":{"raw":{"variants":["Delaunay fusion scales TSP solvers to 10,000 cities","Scaling TSP to 10k cities: Delaunay extraction and graph fusion","Training-free Delaunay framework extends TSP solvers to 10k points","Small TSP solvers go large: Delaunay and graph fusion do the trick","Delaunay triangulation unlocks 10,000-point TSP for existing solvers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000239,"raw_usage":{"total_tokens":1572,"prompt_tokens":1061,"completion_tokens":511,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":677,"completion_tokens_details":{"reasoning_tokens":403}},"tokens_in":677,"tokens_out":511,"duration_ms":4076,"temperature":1.0,"reasoning_tokens":403,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:20:19.545658+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exact solver on several 1,000- to 10,000-city Euclidean TSP instances, compare every optimal-tour edge against the Delaunay triangulation, and count the fraction of optimal edges missing from the triangulation; if that fraction is above a small threshold, or if removing the DT filter materially shortens DTTGF's tours on the benchmark sets, the containment premise fails.","supporting_citations":[{"cited_title":"Delaunay-triangulation-based variable neighborhood search to solve large-scale general colored traveling salesman problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the empirical evidence that optimal TSP tours tend to lie within the Delaunay triangulation, justifying the filter in Eq. (3)."},{"cited_title":"Good triangulations yield good tours,","cited_arxiv_id":null,"evidence_quote":"Establishes that good triangulations yield good tours, the premise for using DT as a subgraph extractor."},{"cited_title":"TSP in a Simple Polygon,","cited_arxiv_id":null,"evidence_quote":"Recent confirmation of DT-guided TSP solving, supporting the framework's reliance on DT containment."},{"cited_title":"Generalize a small pre-trained model to arbitrarily large TSP instances,","cited_arxiv_id":null,"evidence_quote":"The two-stage Att-GCN solver embedded in the framework; also the divide-and-conquer baseline that DTTGF improves on via DT-based decomposition."},{"cited_title":"DIMES: A differentiable meta solver for combinatorial optimization problems,","cited_arxiv_id":null,"evidence_quote":"The DIMES baseline and the source of the benchmark datasets and baseline numbers used in comparison."},{"cited_title":"Attention, learn to solve routing problems!,","cited_arxiv_id":null,"evidence_quote":"Supplies the Attention Model baseline and the S+2-OPT decoder used in the warm-up and final search."},{"cited_title":"Pomo: Policy optimization with multiple optima for reinforcement learning,","cited_arxiv_id":null,"evidence_quote":"The POMO one-stage reinforcement-learning solver that DTTGF rescues to large-instance performance."}],"review_version":1}