acceptodds
Withdrawn from ICLR 2027

The Direction Convention That Tour Cost Hides in Neural TSP Solvers

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Neural solvers for the traveling salesman problem are compared by the cost of their tours, but one of their choices is invisible to that cost: the direction of travel. A tour and its reverse cost the same, yet on our 1,024 test instances with 100 cities, greedy POMO constructs every tour clockwise and Sym-NCO every tour counterclockwise. We call the direction in which a model constructs its tours its convention. We give a model the first cities of an optimal tour, a prefix, traveled clockwise or counterclockwise, and let it complete the tour. With 15 cities left, POMO and Sym-NCO complete it almost optimally with their convention and, against it, worse than when they construct whole tours. LEHD and BQ-NCO, whose tours cost within a fraction of a percent of POMO's, have no convention and complete closer still to optimal in both directions. One part of the score with which POMO and Sym-NCO pick the next city, the priority, ranks the cities left largely in the order of each model's own tours. On a given input, the priority depends only on which cities are left, so it ranks them the same from either endpoint of the prefix. Against the convention, where removing the priority changes the first choice, the priority usually favors the city whose optimal completion costs more. The priority thus shows one place where, in models that encode the cities once, the convention enters a choice. Models that are handed a prefix should therefore be tested in both directions.

Primary area:
optimization
Keywords:
neural combinatorial optimization, traveling salesman problem, interpretability, attention decoders, symmetry, direction of travel, prefix completion, evaluation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_xd6nOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies direction preferences in neural TSP solvers that are hidden by tour cost. It shows that POMO and Sym-NCO complete partial tours much worse when given a direction opposite to their preference. The authors identify a term in the decoder score that contributes to this behavior, but removing it does not reliably improve final tour quality. The paper suggests testing partial-tour completion in both directions.

Critical strengths

S1. The paper shows that similar tour costs can hide large differences in how models complete partial tours in opposite directions.

S2. The paper includes noise controls, confidence intervals, and checks on additional checkpoints and TSPLIB instances.

Critical weaknesses

W1. Limited practical impact. The paper identifies a direction bias but does not propose and validate a way to address it. Removing the priority term does not reliably improve tour quality, and the authors failed to develop a new method to address this bias and show that it improves final tour quality. Without a tested improvement based on the analysis, it is unclear how these findings would help build better TSP solvers.

W2. The main analysis focuses on POMO and Sym-NCO, two relatively early RL-based solvers. Although the paper tests other models and checkpoints, it does not establish whether newer RL-based solvers have the same direction bias. This makes it hard to judge whether the findings describe a broader problem or mainly a weakness of the models studied.

W3. The experiments do not include a final tour-quality comparison with current state-of-the-art neural TSP solvers under the same computing budget. It therefore remains unclear whether the findings offer any benefit for solving TSP beyond explaining the behavior of the selected models.

Questions for authors

Please address the weaknesses W1-W3.

Reviewer_1v88OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates directional conventions in neural TSP solvers, showing that whole-tour costs can conceal substantial asymmetries in prefix-completion performance. Endpoint-reversal and coordinate-reflection experiments demonstrate that POMO and Sym-NCO complete prefixes much less accurately against their preferred direction. An exact decomposition of decoder scores identifies an endpoint-independent priority term that influences next-city choices. Targeted interventions show that removing this term can favor cities with cheaper optimal completions, but subsequent model decisions often offset these gains. Validation covers five neural solvers, 1,024 TSP100 instances, additional problem sizes and distributions, multiple checkpoints, and planar TSPLIB instances. The findings motivate evaluating prefix-completion models in both directions.

Critical strengths
  1. Endpoint reversal preserves the cities, distances, and optimal completion cost while substantially changing completion performance. Complementary reflection experiments further support the role of direction relative to the model’s convention. These controlled comparisons establish that whole-tour cost can overlook important differences in conditional solving ability, making the findings consequential for evaluating prefix-completion models.
  2. The exact score decomposition identifies an endpoint-independent priority term, and targeted ablations with noise and permutation controls connect it to next-city choices. The distinction between optimal completion cost and the model’s own continuation also explains how subsequent decisions can offset local gains. This provides substantive insight into the relationship between internal scores, individual choices, and final solution quality.
Critical weaknesses
  1. The decomposition and interventions establish that the priority affects individual choices, but do not quantify how much of the overall completion gap it explains. Removing it also does not consistently improve final tour cost. Since directional preferences were previously recognized, this unresolved connection between the identified score component and the principal performance failure limits the explanatory novelty of the work.
  2. Reflection augmentation largely eliminates the adverse-direction gap for POMO and Sym-NCO in the main TSP100 comparison, while actual tour-reconstruction pipelines are not evaluated. It therefore remains unclear how consequential the identified convention is under the inference procedures used in practice, limiting the demonstrated impact on the applications motivating the study.
Questions for authors
  1. Does the existing analysis compare the proposed priority with the endpoint-independent ranking obtained directly from the column means of the unprojected interaction matrices? What explanatory value do the cyclic and D4D_4 projections add beyond this simpler ranking, and do the existing controls establish that distinction?
  2. Which inference settings in the reconstruction methods motivating this study leave the directional convention exposed? For example, by excluding reflections or completion from both endpoints? Given the substantial mitigation from reflection augmentation in Table 1, please clarify where the observed asymmetry would remain consequential under those methods’ actual inference procedures and budgets.
Reviewer_7pSdOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies common neural constructive TSP solvers. The authors experimentally demonstrate that some common neural constructive TSP solvers have an orientation preference when constructing the solution. As an example, POMO generates solutions in a clockwise order while Sym-NCO follows a counterclockwise orientation. A lot of experiments are conducted.

Critical strengths
  • It is interesting to be aware about such bias in our NCO solvers and that is interesting to see it experimentally. It could help understanding some failures such as when the solver is used within a random reconstruct decoding scheme.
Critical weaknesses
  • (On presentation) The paper is difficult to read. A large number of sentences are difficult to understand and overly complex. See examples below. Moreover, it is assumed for the reader to jump back and forth between the Appendix and the main content of the paper. The paper is not understandable otherwise.
  • (On soundness) A number of experiments seem redundant. For example Experiments 3.1 and 3.2 are almost the same and test the same phenomenon (tips: 3.2 could be moved to the Appendix to gain some space and put more explanations in the main content for example).
  • I would have liked to understand what is the source of that phenomenon. The authors show that BQ-NCO has no convention, maybe they could start from there. My best guess is that when the model is trained with RL, it gets a particular preference over the tour orientation initially during training and never explores the other orientation from there. They could train a POMO again and randomly reverse the endpoints during the tour construction as a way to remove that convention.
  • It is not clear what is the usefulness of the discovery of this direction convention. It does not appear like a significant contribution to the field.

Additional comments: abstract: l14 and below you discuss algorithms without having introduced them, e.g. “greedy POMO” and “Sym-NCO”

Introduction l35 “Models are compared by the cost of their tours, and probes and sparse autoencoders read what their embeddings contain” I do not understand this sentence. l36: “Neither splits the score with which a model chooses one city over another.” Again, I do not understand.

p2 l79 “POMO, Sym-NCO and AM compute city embeddings once (Huang et al., 2025), and each candi- date’s raw score (before clipping) splits exactly into parts” This should not be part of an introduction. This is specific to some solutions and does not describe a general contribution.

l81 “We remove the priority, replacing each candidate’s priority by the candidates’ mean (a mean ablation), and see which choices change.” Hard to follow.

Section 2

l103 “Models. The five models construct a TSP tour one city at a time.” This sounds more like an experiment report than a paper.

l107 “Each model is a publicly released checkpoint decoded greedily, so it is a deterministic policy π.” I do not understand the meaning of this sentence and why it is here.

p3l145 “When no optimal tour keeps the prefix, part of the gap is a cost forced by the prefix” Hard to understand.

Section 3: There should be a small introduction of what is in Section 3. The beginning of Section 3.1 is very abrupt.

l199 “Does the gap follow the prefix or its direction? Reversed endpoints (Figure 1) separate the two: they keep the input, the prefix’s,,, prefix’s direction”. Hard to understand.

Section 4: “We examine one term of the decoder’s raw score, the priority, through its exact share of the margin between any two candidates and the choices that its removal changes.” A section introduction should state the high level results of the section in clear terms. This is not the case here.

Questions for authors

Q1. Have you tried to train a model yourself and understand why some neural solvers have a particular convention while others do not? Q2 Could you explain in simpler terms what is the priority score that you compute from the decoder logits (Section 4)?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.