{"id":"16d06cb8-dff5-4031-8739-83f49891c14a","arxiv_id":"2506.06634","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"GELD solves Euclidean TSPs from 100 to 10,000 nodes with one pre-trained model and refines other solvers' solutions by 35-97 percent, reaching 744,710 nodes when combined with a heuristic.","lead":"GELD is a neural network that solves traveling salesman problems across very different sizes with a single pre-trained model, using a lightweight global attention and a fast local decoder. It also acts as an add-on that improves routes produced by other neural solvers by 35 to 97 percent for a modest amount of extra computing time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Decoder's k-nearest-neighbor mask (Eq. 9) excludes optimal long edges, so reported gaps are partly a representational ceiling, not learned quality.","rationale":"The reader's weakest_assumption identifies the k-nearest-neighbor decoder restriction as the load-bearing concern; I agree. This is the single most fundamental issue because it caps the set of representable tours independently of training data, learning algorithm, or search budget. The paper provides strong empirical support for the uniform-distribution middle-scale claims, and the open-source code is a point in its favor, but the locality mask makes the cross-distribution and 'solving TSPs across different scales' claims overbroad. The clustered results in Table 3 and the ablation in Table 9 (where larger k improves quality) corroborate the ceiling. The 744,710-node claim is also overstated because it relies on RI initialization plus reconstruction, and the PRC mechanism is arguably a form of divide-and-conquer; however, that is a secondary issue compared to the structural representational bound. The authors should compute and disclose the constrained-optimal ceiling, report the fraction of optimal edges excluded by the mask, and reword the abstract to state the distribution-dependent nature of the gaps. This does not overturn the reader's CONDITIONAL verdict; it reinforces the conditions needed for acceptance.","tokens_in":34385,"tokens_out":6175,"duration_ms":64964,"concrete_test":"On the 20 clustered TSP-5000 test instances, compute for each directed consecutive edge (u,v) in the LKH3 near-optimal tour whether v is among the 100 nearest neighbors of u (using all nodes, which only relaxes the k-set because visited nodes are excluded in the model). Report the fraction of optimal edges that violate the k=100 window. If this fraction is non-negligible (>1%), GELD cannot represent those edges and the observed clustered gap (11.62% for GELD+G) is partly forced by the architectural mask rather than learned routing quality. Additionally, compute the constrained optimal tour under the same k=100 mask (dynamic programming or MILP with allowed transitions) and compare its gap to GELD's; if GELD's gap is close to this ceiling, the model's reported performance is primarily an artifact of the locality constraint.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decoder restricts the allowed next node to the k nearest available nodes (k_m = 100, Section 4.1, Eq. 9). Consequently, any tour that uses an edge from a to b with b not among the k nearest neighbors of a is unreachable by the model, regardless of training, beam search, or reconstruction. This hard action mask, not the learned policy, sets a lower bound on the achievable gap. The paper never quantifies this ceiling. The clustered-distribution results in Table 3 (e.g., GELD+G gap 11.62% at TSP-5000 vs. 7.62% uniform) are consistent with the mask blocking inter-cluster edges, since in dense clusters the k nearest neighbors of a node often all lie within the same cluster. The abstract's claim of solving TSPs with gaps 0.06 to 2.8 percent is therefore only valid for distributions where optimal tours are locally realizable; for other distributions the model cannot express the optimal tour at all. This is a structural limitation, not a training artifact, and it directly bounds the headline claims of universal scale generalization and of post-processing quality improvement.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces GELD, a neural TSP solver combining a Global-view Encoder (GE) with a Region-Average Linear Attention (RALA) mechanism and a Local-view Decoder (LD) that restricts the next-node candidate set to the k-nearest neighbors of the current node. A two-stage training scheme first supervises on small instances (n ≤ 100) and then self-improves on larger instances using beam search and parallel reconstruction (PRC). The authors claim that a single pre-trained checkpoint solves Euclidean TSPs from 100 to 10,000 nodes with gaps of 0.06–2.8% (with BS and PRC), outperforms seven state-of-the-art models in solution quality and inference speed, and, when combined with a random-insertion heuristic, produces tours for instances up to 744,710 nodes without divide-and-conquer. The empirical study covers synthetic uniform/clustered/explosion/implosion instances, TSPLIB, National TSPs, and four VLSI instances, with ablations on RALA, the second training stage, the global view, the local view, and the hyperparameters m and k_m.","tokens_in":34535,"tokens_out":6274,"duration_ms":69535,"significance":"If the claims hold, GELD is a meaningful advance: the O(n) encoder complexity, the cross-scale generalization of a single checkpoint, and the demonstrated post-processing gains are all valuable for practical neural TSP solving. The paper ships source code and evaluates against external references (LKH3, Concorde, best-known values), so the headline gaps are not circular. The ablation suite is unusually thorough, covering the major architectural choices and the sensitivity of m and k_m. However, the significance is currently tempered by two issues that are load-bearing for the central claims: the decoder's k-nearest-neighbor mask is a hard representational ceiling that is never quantified, and the claimed superiority over seven SOTA models is established only for the computationally expensive BS+PRC variant, not for the greedy variant that the text sometimes invokes. These issues are fixable with additional analysis and careful qualification, but they must be addressed before the claims can be accepted as stated.","major_comments":[{"comment":"The decoder restricts the candidate set to the k nearest available nodes of the current node, with k_m=100. This is a hard action mask: any optimal tour edge from a to b where b is not among the k nearest neighbors of a is unreachable by the model, regardless of training, beam search, or reconstruction. The manuscript never quantifies this representational ceiling. The clustered-distribution results in Table 3 are consistent with the mask blocking inter-cluster edges (e.g., GELD+S* at TSP-5000 is 4.27% on clustered versus 2.77% on uniform; GELD+G at TSP-5000 is 11.62% versus 7.62%). The authors should either (a) report, on the test distributions, the fraction of optimal (or LKH3) tour edges that fall inside the k-nearest-neighbor set, (b) ablate with a global candidate set that always includes the destination or a sampled set of far nodes, or (c) explicitly restrict the paper's claims to distributions where optimal tours are locally realizable. Without this, the headline '0.06 to 2.8 percent' gaps are partly an artifact of the action-space restriction rather than a measure of learned policy quality.","section":"Section 4.1, Eq. (9), and Table 3"},{"comment":"The abstract and the concluding text of Section 5.2 state that GELD outperforms seven state-of-the-art models considering both solution quality and inference speed, without specifying the inference strategy. In Table 3, the greedy variant GELD+G has an average gap of 4.68% on uniform instances, worse than both UDC (4.07%) and INViT-3V (4.42%); on clustered, explosion, and implosion distributions GELD+G is also worse than INViT-3V. The real-world results in Table 4 are starker: GELD+G has an average gap of 14.39% on National TSPs versus INViT-3V's 8.75%. The claim is only supportable for GELD+S*, which uses beam search with width 16 and 1,000 PRC iterations, giving it substantially more compute than the baselines' default greedy or simple-rollout strategies. The paper must either qualify the claim to the specific inference budget used, or provide a controlled comparison where all methods are given a comparable post-processing/search budget.","section":"Abstract and Section 5.2, Tables 3 and 4"},{"comment":"The abstract's statement that 'GELD is shown as capable of solving TSPs with up to 744,710 nodes' should be qualified. The results in Table 7 are for the pipeline 'RI + GELD', where a random-insertion heuristic constructs the initial tour and the neural model repeatedly reconstructs random sub-tours. The neural model alone is not evaluated on these instances, and the text itself describes this as integration with a conventional heuristic. In addition, the claim of being 'first-of-its-kind to solve this large size TSP without relying on divide-and-conquer strategies' is debatable: PRC repeatedly extracts and re-solves sub-solutions, which is structurally similar to a decomposition strategy even if the paper defines D&C more narrowly. The authors should state precisely what GELD alone does and what the hybrid pipeline does, and should temper the 'first-of-its-kind' wording accordingly.","section":"Section 5.3, Table 7, and Abstract"}],"minor_comments":[{"comment":"The expression 'epoch ⋅ (nmax − km) ∣ ne2' uses an unclear division symbol; this should be written as an explicit integer division or a floor operation.","section":"Algorithm 1, line 7"},{"comment":"The description of baseline inference settings is incomplete: for Omni-TSP, ELG, and UDC the number of rollouts is not reported, and for INViT-3V the number of data-augmentation repetitions is not specified. This makes the timing comparisons hard to reproduce.","section":"Section 5.1.3"},{"comment":"The average gap in Table 4 is computed only over instances that each model successfully solves, and the number of solved instances is not always displayed. This can make a model with frequent memory failures look better than a model that solves all instances; the authors should report the full per-instance coverage in the main table or at least state the count explicitly in every cell.","section":"Table 4"},{"comment":"The masking operation uses -inf inside the softmax but then declares the output to be in R^k; the notation should clarify that the probability mass is renormalized over the candidate set Kset.","section":"Section 4.1, Eq. (10)"},{"comment":"The ablation 'w/o local view' extends the decoder to a global candidate set and reports OOM at TSP-10000 for S*. This result is interesting, but the discussion could more explicitly interpret it as evidence that the k-restriction is what enables large-scale inference, rather than as evidence about solution quality.","section":"Section 5.4, Table 6"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid empirical contribution with a well-designed architecture and a broad evaluation, and the source-code release is a clear strength. The main reasons for major revision are the unquantified representational ceiling of the decoder mask and the overbroad 'outperforms seven SOTA' claim, which is only true for the computationally expensive inference mode. Both issues are addressable with additional analysis and careful rewriting. I do not see grounds for rejection: the empirical results on uniform and real-world instances are competitive, and the ablations are informative. The editor may also wish to ask the authors to soften the 'first-of-its-kind' wording for the 744k-node results, since the evaluation is a hybrid pipeline rather than the standalone neural model."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read GELD. The genuinely new piece is RALA, the region-average linear attention: n-by-m proxies and m-by-n key weights, O(n m h) time and O(n h) space without extra parameters. That part is novel and clean. The global-encoder/local-decoder split with k-NN candidate set is also a real design departure from LEHD/BQ, and the two-stage SL+SIL training is well-motivated. The empirical work is unusually thorough for this area: comparisons to LKH3, Concorde, TSPLIB, World TSP, ablations for RALA, second stage, global view, local view, and sensitivity analyses for m and k_m. The middle-scale claim (100-10,000 nodes with gaps 0.06-2.8% using BS+PRC) is supported by the tables. The post-processing results (35-97% improvement) are also credible because they are measured against fixed references, not the model's own outputs.\n\nThe soft spots are local but real. The abstract's 'solving TSPs with up to 744,710 nodes' is misleading: that number comes from RI+GELD with 19.7 minutes of sub-tour reconstruction, not a single neural solve. The complexity analysis reports O(n m h) for RALA but omits the cost of building the k-NN candidate set at each decoding step, which is O(n) per step unless a spatial index is used; no index is described. There are no error bars anywhere, and for a benchmark with 20 instances at 5k/10k, that matters. The k-NN mask (k_m=100) is a hard representational ceiling: any tour requiring an edge to a node outside the local window is unreachable, so the reported gaps are partly an artifact of that mask, not pure learned quality. The clustered-distribution results show exactly this (gaps roughly double uniform), and the paper never quantifies the ceiling. Finally, Section 3.3 justifies RC by claiming the optimal solution comprises optimal sub-solutions; that is false for TSP in general and should be restated as a heuristic rationale.\n\nOverall, the core architecture and the empirical comparison for the BS+PRC variant hold up. The abstract and the optimal-substructure claim need rephrasing, k-NN complexity needs reporting, and variance should be included. This deserves a serious referee, likely conditional accept after revision. I'd cite the RALA module and the post-processing pipeline; I'd bring it to a reading group if we were surveying neural TSP.","headline":"A genuine architectural contribution with solid middle-scale evidence; the 744k headline is the weakest sentence, but the rest withstands review.","tokens_in":35196,"tokens_out":2494,"would_cite":true,"duration_ms":26377,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"One pre-trained network solves TSPs from 100 to 744,710 nodes.","keywords":["Traveling Salesman Problem","neural combinatorial optimization","large-scale generalization","linear attention","self-improvement learning","re-construction post-processing","Euclidean TSP","unified model"],"falsifier":"Construct a Euclidean instance with two well-separated clusters arranged so that the optimal tour leaves one cluster through a city that is not among the $k$-nearest neighbors of the city it departs from; if GELD's decoder is restricted to those neighbors, it cannot output that tour, and its gap on such instances will stay bounded away from zero regardless of beam-search width or reconstruction iterations.","tokens_in":34056,"feed_emoji":"🧠","tokens_out":11152,"duration_ms":93898,"temperature":0.7,"pith_summary":"This paper tries to establish that one neural network, trained once, can solve Euclidean Traveling Salesman Problems at many sizes at once—100, 500, 1,000, 5,000, and 10,000 nodes—and scale far beyond that, without the usual divide-and-conquer decomposition. The model, GELD, pairs a lightweight global encoder with a local decoder that only considers the nearest neighbors of the current city, which keeps each decision fast. On uniformly random instances, the same pre-trained checkpoint stays within 0.06 to 2.8 percent of strong reference solutions when beam search and reconstruction are added, and as a post-processor it cuts the gaps of other neural solvers by 35 to 97 percent. Combined with a simple insertion heuristic, it solves instances up to 744,710 nodes, which the paper reports as a first for a non-divide-and-conquer neural model. If true, this means a single checkpoint could replace a zoo of size-specific neural TSP solvers and make neural TSP solving practical for real logistics and routing.","feed_headline":"One neural model scales TSP solving from 100 to 744,710 nodes","feed_subtitle":"Same checkpoint stays within 0.06-2.8% of best routes and lifts other solvers' quality by 35-97%.","key_machinery":"The load-bearing object is the broad-global-assessment/refined-local-selection loop. The encoder's Region-Average Linear Attention (RALA) divides the normalized node coordinates into $m = m_r m_c = 9$ rectangular regions, forms one proxy embedding per region by averaging the query embeddings of its nodes, and then exchanges information between nodes and proxies through two softmax weight matrices; this costs $\\mathcal{O}(n m h)$ time and $\\mathcal{O}(n h)$ space with no extra learnable parameters. The decoder, in turn, restricts every step to the available $k$-nearest neighbors of the previously selected node, $k = \\min\\{k_m, n_t\\}$ with $k_m = 100$, and scores those candidates with attention that folds in the distance matrix and uses RMSNorm. The third mechanism is reconstruction: randomly selected sub-tours are fed back through the model after re-normalizing coordinates, which reassigns nodes to different RALA regions and diversifies inputs so that beam search and parallel reconstruction can improve solutions. A two-stage training schedule—supervised on small instances, then self-improvement on larger ones with curriculum scaling—is what lets one checkpoint cover all scales.","core_discovery":"GELD's central claim is that global assessment and local selection can be separated without losing solution quality: a single lightweight attention layer gives the model a coarse view of the whole instance, and a heavier decoder then chooses among only the $k$-nearest neighbors of the last visited city. To make the global view cheap, the encoder uses Region-Average Linear Attention (RALA), which partitions the plane into a fixed $3 \\times 3$ grid, averages query embeddings into regional proxies, and performs attention between nodes and proxies in $\\mathcal{O}(n)$ time and space instead of quadratic cost. To make the local view effective, the decoder is trained first by supervised learning on up to 100-node instances and then by self-improvement on larger instances up to 1,000 nodes. With these ingredients plus beam search and parallel re-construction, the paper reports average gaps of 0.06 to 2.8 percent on uniform instances from 100 to 10,000 nodes, and shows that the same model improves other solvers' routes by 35 to 97 percent with tens of seconds of extra compute.","pith_inferences":["A natural stress test is to push beyond uniform distributions: because RALA's $3\\times3$ grid is fixed in normalized coordinates, adaptive or data-dependent region partitioning could reduce the near-doubling of gaps observed on clustered instances.","The $k$-nearest restriction means GELD's ceiling is the locality of the optimal tour; pairing the model with a rare global edge-insertion or 2-opt step could close the remaining gap without much latency.","The same broad-assessment/refined-selection pattern could transfer to other routing problems, and the paper itself points to capacitated vehicle routing as the next target.","Because GELD's improvement comes from diversifying inputs during reconstruction rather than from model size, the lesson may be that input-space diversification during inference is a cheaper route to better solutions for learned combinatorial solvers."],"forward_implications":["A single pre-trained GELD checkpoint can replace separate small-scale and large-scale neural TSP solvers, because it covers 100- to 10,000-node instances with the same parameters.","GELD as a post-processor makes weak, fast solvers practical: applying it to their outputs yields 35 to 97 percent gap reductions at the cost of tens of seconds, as demonstrated on real-world benchmark instances.","The linear-complexity encoder lets GELD run with large batch sizes on a 24 GB GPU, so instances that make quadratic-attention baselines run out of memory can still be solved.","The two-stage training recipe—supervised labels on small instances followed by self-improvement on larger ones—produces cross-scale generalization without expensive ground-truth tours for large TSPs.","When combined with a simple random-insertion heuristic, GELD solves extremely large instances up to 744,710 nodes, a scale the paper reports no non-divide-and-conquer neural solver has reached before."],"supporting_citations":[{"why":"Supplies the heavy-decoder design and the public supervised training data that GELD's first stage uses, and it defines the LEHD baseline.","marker":"Luo et al., 2023"},{"why":"Provides the BQ baseline and the recursion-based view that motivates restricting decoding to a local candidate set.","marker":"Drakulic et al., 2023"},{"why":"Supplies the POMO-style data augmentation and multiple-rollout baselines used in GELD's evaluation.","marker":"Kwon et al., 2020"},{"why":"Defines the standard quadratic-complexity attention mechanism that RALA is designed to replace.","marker":"Vaswani et al., 2017"},{"why":"Offers the INViT-3V baseline and the local-views idea that GELD's global-plus-local design directly responds to.","marker":"Fang et al., 2024"},{"why":"Gives the GD baseline and the self-improvement learning paradigm that GELD's second training stage adapts.","marker":"Pirnay and Grimm, 2024"},{"why":"Provides the UDC divide-and-conquer baseline that GELD claims to beat without decomposition.","marker":"Zheng et al., 2024"},{"why":"Introduces parallel reconstruction (PRC) and argues that divide-and-conquer neglects dependencies between sub-problems.","marker":"Luo et al., 2025"},{"why":"Supplies RMSNorm, used inside the decoder attention to prevent value overflow.","marker":"Zhang and Sennrich, 2019"}],"fun_headline_variants":["TSP at any scale: one model tackles 100 to 744k nodes","Neural TSP solver scales to 744k nodes without divide-and-conquer","GELD: unified TSP solver from small to massive instances","One model, any TSP size: from 100 to 744,710 nodes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The model can only pick the next city from the $k$-nearest neighbors of the current city, so if the optimal tour needs a long edge to a city outside that local window, the model can never produce that edge and its achievable gap is bounded below by that locality error.","fun_headline_variants_meta":{"raw":{"variants":["TSP at any scale: one model tackles 100 to 744k nodes","Neural TSP solver scales to 744k nodes without divide-and-conquer","GELD: unified TSP solver from small to massive instances","One model, any TSP size: from 100 to 744,710 nodes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000763,"raw_usage":{"total_tokens":3448,"prompt_tokens":1069,"completion_tokens":2379,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":685,"completion_tokens_details":{"reasoning_tokens":2294}},"tokens_in":685,"tokens_out":2379,"duration_ms":15562,"temperature":1.0,"reasoning_tokens":2294,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:54:28.932097+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a Euclidean instance with two well-separated clusters arranged so that the optimal tour leaves one cluster through a city that is not among the $k$-nearest neighbors of the city it departs from; if GELD's decoder is restricted to those neighbors, it cannot output that tour, and its gap on such instances will stay bounded away from zero regardless of beam-search width or reconstruction iterations.","supporting_citations":[{"cited_title":", author Lin, X","cited_arxiv_id":null,"evidence_quote":"Supplies the heavy-decoder design and the public supervised training data that GELD's first stage uses, and it defines the LEHD baseline."},{"cited_title":", author Michel, S","cited_arxiv_id":null,"evidence_quote":"Provides the BQ baseline and the recursion-based view that motivates restricting decoding to a local candidate set."},{"cited_title":", author Choo, J","cited_arxiv_id":null,"evidence_quote":"Supplies the POMO-style data augmentation and multiple-rollout baselines used in GELD's evaluation."},{"cited_title":", author Shazeer, N","cited_arxiv_id":null,"evidence_quote":"Defines the standard quadratic-complexity attention mechanism that RALA is designed to replace."},{"cited_title":", author Song, Z","cited_arxiv_id":null,"evidence_quote":"Offers the INViT-3V baseline and the local-views idea that GELD's global-plus-local design directly responds to."},{"cited_title":", author Grimm, D.G","cited_arxiv_id":null,"evidence_quote":"Gives the GD baseline and the self-improvement learning paradigm that GELD's second training stage adapts."},{"cited_title":", author Zhou, C","cited_arxiv_id":null,"evidence_quote":"Provides the UDC divide-and-conquer baseline that GELD claims to beat without decomposition."},{"cited_title":", author Lin, X","cited_arxiv_id":null,"evidence_quote":"Introduces parallel reconstruction (PRC) and argues that divide-and-conquer neglects dependencies between sub-problems."},{"cited_title":", author Sennrich, R","cited_arxiv_id":null,"evidence_quote":"Supplies RMSNorm, used inside the decoder attention to prevent value overflow."}],"review_version":1}