acceptodds
Under review as a conference paper at ICLR 2027

Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba

Abstract

We study efficiency as a first-class objective in Neural Combinatorial Optimization (NCO) and present ECO, an efficient learning framework that combines batched preference optimization with a Mamba backbone. Instead of tightly interleaving every policy update with on-policy rollouts, ECO decouples trajectory generation from gradient updates through two stages: supervised warm-up on pre-computed solutions and iterative Direct Preference Optimization (DPO) on batched candidate sets generated by the current policy. We pair this learning pipeline with a mixed Mamba encoder-decoder that reduces encoder memory growth and recurrent decoding-state cost on long sequences while retaining the standard autoregressive candidate-scoring step. A local-search-guided bootstrapping strategy is further used during training to widen preference margins and stabilize iterative improvement. Importantly, local search is only used to construct stronger preference pairs during training and is never invoked at inference time. On TSP and CVRP, ECO is best or competitive across most compared neural baselines, with clear advantages in memory usage and throughput. We provide additional analysis on complexity decomposition, permutation sensitivity, evaluation fairness, and the contribution of each design component.

Primary area:
optimization
Keywords:
NCO

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_duZNOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this paper, the authors focus on the efficiency of NCO models and set aside their performance. Specifically, they point out that efficiency is generally compromised by two fundamental aspects of the proposals: on the one hand, the learning technique; and on the other, the architecture employed in the model. To achieve a qualitative leap in terms of efficiency, the authors propose a model that addresses both of these points. Specifically, they propose using a Mamba-type model and, furthermore, a two-phase learning process comprising a supervised phase and a preference optimisation phase. The experimental results on the TSP and CVRP demonstrate that the proposed model does indeed require less inference time than competing models; moreover, the performance achieved is not compromised compared with the other models.

Critical strengths
  • The paper highlights an aspect of NCO that is rarely discussed, namely efficiency.
  • The experimental comparison takes into account various problems and a range of state-of-the-art models. Furthermore, for reference purposes, meta-heuristics and benchmark solvers for the TSP and CVRP are included.
Critical weaknesses
  • One aspect that gives pause for thought is the performance results. Even today, in the VRP, we observe that the proposed model lags behind the HGS, and falls far short of Concorde in the TSP; in both cases, it appears that the gap widens as the problem size increases. Furthermore, it seems that the experiments carried out are, in some ways, pushing the limits of the models used (Figure 3).
Questions for authors

Bearing in mind the previous weakness, it seems that every time an even more complex model is being proposed by the community. However, the table of results evidences that gap is reducing from model to model. It looks that the progress is good. But I am wondering is the computational cost of the models in terms of memory. Where are the limits? I say this because the paper has made me reflect on the future steps.

1 comment
AuthorsOpenReview ↗

Response to Reviewer duZN

Dear Reviewer duZN,

We thank the reviewer for taking the time to carefully review our manuscript and for the constructive feedback that has helped improve its quality and clarity. We also appreciate the reviewer's recognition of our focus on computational efficiency and of the breadth of our experimental comparisons across TSP and CVRP, including neural baselines, metaheuristics and classical reference solvers.

The reviewer's question highlights an important issue for future NCO research. The useful operating range is jointly determined by memory capacity, inference latency and the required solution quality. Our experiments and complexity analysis characterize these constraints from complementary perspectives.

1. Solution quality and runtime relative to classical solvers

The results quantify the trade-off between constructive inference time and solution quality. For 1,000 TSP5000 instances, greedy ECO reaches a 5.49% gap in 2.5 min, while Concorde takes 18.4 h and LKH-3 takes 9.6 h. On CVRP1000, ECO reaches a 2.87% gap in 1.8 min, compared with 13.7 min for HGS. These times describe the reported hardware configurations: ECO runs on one A800 GPU, while the classical solvers run on the Xeon CPU node.

The quality gap also changes with scale. ECO's greedy TSP gap increases from 0.37% at 200 nodes to 5.49% at 5,000 nodes; Table 3 reports 5.77% at 10,000 nodes. The CVRP gap increases from 0.86% at 100 customers to 2.87% at 1,000 customers. Consequently, the acceptable solution gap is part of the practical scaling boundary.

2. The measured memory range

At a fixed inference batch size of eight on an 80 GB A800, ECO uses approximately 21 GB at 5,000 nodes and 40 GB at 10,000 nodes. The original Transformer implementation uses 43.1 GB at 5,000 nodes and reaches out-of-memory around 7,000–7,500 nodes. The matched fused-attention control reduces the Transformer's TSP5000 memory to 39.9 GB, while ECO retains its memory advantage.

These measurements establish that ECO remains within the memory budget at 10,000 nodes. They do not establish its maximum feasible instance size. Such a maximum depends on batch size, precision, model dimensions and implementation.

3. Remaining computational constraints and future directions

At fixed model dimensions, ECO's encoder uses linear sequence-modeling memory, and its recurrent decoder maintains a fixed-size state per trajectory. Full route construction nevertheless requires sequential decisions and candidate scoring. Dense scoring requires O(DN2)O(DN^2) work for TSP and O(DTN)O(DTN) for CVRP, where DD is the embedding dimension and TT includes customer visits and depot returns. These terms remain sources of computational growth as instances become larger.

The required solution quality introduces an additional budget constraint. On TSP1000, greedy ECO reaches 4.84% in 0.90 min per 1,000 instances. Additional sampling improves the gap to 3.78% at 20 min and 3.66% at 30 min. These measurements show how tighter quality targets require additional inference resources under the tested decoding configuration.

This analysis suggests three directions for extending the demonstrated operating range:

  • Candidate filtering, to reduce the number of actions scored at each decoding step.
  • Hierarchical or decomposed construction, to manage larger instances while maintaining global routing consistency.
  • Adaptive allocation of sampling or refinement budgets, to concentrate additional computation on instances that benefit most.

We see these as promising directions for improving the quality–cost trade-off while explicitly controlling memory and latency.

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

This paper focuses on the training efficiency of NCO and proposes ECO, a framework that combines a spatially ordered Mambaencoder-decoder model with supervised initialization and iterative DPO on buffered trajectory pairs. Since candidate data are refreshed by the policy periodically, training is batched during updates. Local search supplies stronger preferred trajectories during training, while inference remains constructive. Experiments on TSP and CVRP compare solution quality and time cost, architecture and objective ablations, permutation tests and limited uncertainty analysis. Under the tested implementations, ECO reports improved performance and efficient training on TSP and CVRP.

Critical strengths
  1. This paper treats efficiency of NCO as the first-class objective, which matters for practival deployment on large instances.
  2. The paper goes further beyond reporting only gains, it also analyzes how LS-guided preference construction empowers the training signal by widening preference margins, which may give insight to other NCO methods.
Critical weaknesses
  1. The improvement on inference efficiency is modest, from Table1, there seems no significant advantage on inference stage, especially for CVRP1000.
  2. The novelty of this paper is limited, the framework combines the existing components together, with Mamba as backbone, SFT, DPO and LS. And some of the ideas have already been adopted in prior works[1].
  3. The author emphasizes large scale efficiency, but experiment size capped at TSP5000 and CVRP1000. Comparison with other large-scale baselines [2] can also be mentioned.
  4. [1, 3] are mentioned as concurrent work, but they have been published more than one year ago, which are the most related methods worth comparison.
  5. The transformer baseline in Fig. 3 might be weak because the paper attributes the transformer's OOM to quadratic memory, however, FlashAttention[4] have already capable of reducing the memory growth linearly.
Questions for authors
  1. For larger scales and stronger baselines, in Table 1, can authors report results beyond TSP5000 and CVRP1000 and compare against more recent baselines such as SIL[2], BOPO[3]?
  2. In Fig. 3, can the author provide the memory and inference throughput of more competitive baselines? Consider adding efficient attention baselines would be better.
  3. Although this paper discusses alternative node orderings, it remains unclear whether the encoder's unidirectional scan limits the representation capability of the models. What if using a bidirectional encoder, which would help have a better understanding?

[1] Pan, Mingjun, et al. "Preference optimization for combinatorial optimization problems." arXiv preprint arXiv:2505.08735 (2025). [2] Luo, Fu, et al. "Boosting neural combinatorial optimization for large-scale vehicle routing problems." International Conference on Learning Representations. Vol. 2025. 2025.

[3] Liao, Z., Chen, J., Wang, D., Zhang, Z. & Wang, J.. (2025). BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:37456-37475.

[4] Dao, Tri, et al. "Flashattention: Fast and memory-efficient exact attention with io-awareness." Advances in neural information processing systems 35 (2022): 16344-16359.

6 comments
AuthorsOpenReview ↗

Response to Reviewer 5aE2 (1/2)

Dear Reviewer 5aE2,

We thank the reviewer for dedicating valuable time to evaluating our manuscript and for the thoughtful suggestions that have helped improve its quality and presentation. We also appreciate the reviewer's recognition of the practical importance of prioritizing efficiency in neural combinatorial optimization, as well as the value of our analysis of how local-search-guided preference construction widens preference margins and strengthens the training signal.

W1. How much does ECO improve inference on CVRP1000?

For 1,000 CVRP1000 instances, greedy ECO reaches a 2.87% gap in 1.8 min, while greedy SIL reaches 5.01% in 3.33 min. ECO reduces the gap by 2.14 percentage points and takes less elapsed time. Our locally reproduced GFlowNet-HBG reaches 2.89% in 1.7 min with test-time local search, following its paper's evaluation setting. ECO reaches its result through constructive inference and uses LS during training. The gap difference is 0.02 percentage points. ECO without local-search bootstrapping takes 1.2 min. Main Results Analysis identifies these decoding and training settings.

ECO's largest controlled saving is in training. On TSP1000, DPO and PPO with the same Mamba backbone reach gaps of 4.84% and 4.88% in 10.2 h and 34.5 h, respectively. Table 4 gives a PPO-to-DPO training-time ratio of 3.38 at comparable final quality. Figure 1 identifies policy training separately from initial label preparation. Accounting for the cost of supervision reports measured TSP5000 first-run costs, including shared labels, of 58.3 h for ECO and 125.8 h for PPO, a 2.16-fold ratio. The appendix subsection Training-cost and implementation records gives the cost breakdown.

W2 and W4. What does ECO contribute beyond Pan et al. and BOPO?

ECO contributes a training-efficient routing design whose architecture and preference objective are tested through controlled ablations. It couples a spatially ordered state-space policy with reference-anchored DPO and search-guided preference construction. With the same Mamba backbone and buffered pairs on TSP1000, DPO reaches 4.84%, compared with 5.31% for reference-free logistic ranking and 5.58% for hinge ranking. Increasing the fraction of search-refined pairs from 0 to 0.3 raises the mean preference margin from 0.22% to 1.87% and improves the greedy gap from 9.55% to 4.84%. Together with the matched PPO comparison, these results identify how the design improves training cost, preference quality and constructive solution quality.

The revised Related Work identifies Pan et al. and Liao et al. as ICML 2025 work. The appendix subsection Preference Learning explains the objective and training differences. Pan et al. use local search to construct preference pairs during fine-tuning. BOPO pairs the best candidate with lower-ranked candidates and uses objective values to scale a reference-free preference loss. ECO's reference-anchored objective is assessed against reference-free losses on the same buffered data.

AuthorsOpenReview ↗

Response to Reviewer 5aE2 (2/2)

W3 and Q1. What happens beyond TSP5000 and CVRP1000, against SIL and BOPO?

Table 3 reports measured larger-scale comparisons with BOPO and SIL. ECO reaches gaps of 5.77% on TSP10K and 2.92% on CVRP5K, with lower gaps and shorter runtimes than the corresponding baselines under the reported decoding configurations. Time is minutes per 1,000 instances.

Task and methodGapTime (min/1,000)
TSP10K · ECO, greedy5.77%3.88
TSP10K · BOPO, multi-start and augmentation6.12%15.22
CVRP5K · ECO, greedy2.92%23.07
CVRP5K · SIL, greedy5.08%42.69

Table 3 uses Concorde-based TSP gaps and HGS-based CVRP gaps, with capacity 500 at CVRP5K. ECO and SIL use greedy decoding; BOPO uses multi-start and augmentation.

Appendix J reports measured gaps and runtimes for batches of 16 instances under the stated decoding configurations.

Task and methodGapTime for 16 instances (min)
TSP10K · ECO, greedy5.77%0.0621
TSP10K · BOPO, multi-start and augmentation6.12%0.2435
CVRP5K · ECO, greedy2.92%0.3691
CVRP5K · SIL, greedy5.08%0.6830

The 16-instance evaluation uses Concorde-based TSP gaps and HGS-based CVRP gaps at capacity 500. ECO and SIL use greedy decoding; BOPO uses multi-start and augmentation.

Table 1 adds BQ-NCO, INViT-2V and BOPO on TSP1000 and SIL on CVRP1000. On TSP1000, greedy ECO reaches 4.84% in 0.90 min, BQ-NCO 5.41% in 15.6 min, INViT-2V 6.15% in 17.50 min and BOPO 5.13% in 2.58 min, each per 1,000 instances. BOPO uses the INViT-2V backbone; both use multi-start and augmentation. ECO's gap is 0.57 percentage points lower than BQ-NCO's, and BQ-NCO takes 17.3 times as long. The CVRP1000 comparison with greedy SIL is given above.

Table 2 reports measured outcomes at 20- and 30-minute deadlines per 1,000 instances, including sampling and refinement in elapsed time. Initial gaps and times match Table 1. The TSP1000 gaps at the two cutoffs are ECO 3.78/3.66%, LEHD 3.61/3.18%, BQ-NCO 5.41/5.41%, INViT-2V 6.15/6.15% and BOPO 5.13/5.13%. On CVRP1000, ECO reaches 2.87/2.87% and SIL reaches 5.01/5.01%. TSP ECO sampling and LEHD RRC use additional inference time. BQ-NCO and SIL retain greedy decoding, INViT-2V and BOPO retain multi-start and augmentation, and CVRP ECO retains greedy decoding. Fixed native results repeat at both deadlines; each deadline caps elapsed time without requiring every method to use the full allowance. Figure 1 plots approximately the first 10 training hours; Tables 1 and 2 measure inference minutes using completed-training checkpoints. Related Work now discusses ELG's local/global policy ensemble for routing generalization; the quantitative additions focus on the baselines listed above.

W5 and Q2. Would an efficient attention implementation change Figure 3?

ECO's memory advantage persists with the matched fused-attention control in Appendix J. At TSP5000 with the same Transformer weights, precision, masks and batch size eight, fused attention uses 39.9 GB instead of 43.1 GB. It reduces peak memory by 3.2 GB and reaches 1.14× the original Transformer's end-to-end throughput. ECO uses approximately 21 GB in this comparison.

FlashAttention computes exact dense attention with auxiliary storage linear in sequence length, while its arithmetic remains quadratic. Figure 3 therefore reports the original Transformer's measured memory curve separately from the fused-attention control. Its memory measurements use batch size eight on an 80 GB A800; throughput uses each model's largest fitting batch. The original Transformer uses about 43 GB at 5,000 nodes and reaches OOM around 7,000–7,500, while ECO uses about 21 GB at 5,000 nodes and 40 GB at 10,000. The revised caption and Efficiency and Throughput Analysis distinguish these measurements and their configurations.

SIL supplies an additional routing baseline with lightweight cross-attention. Tables 1 and 2 report its local CVRP1000 results. Table 3 reports its measured CVRP5K comparison with runtimes per 1,000 instances, and Appendix J gives measured batch-of-16 results.

Q3. Could a bidirectional encoder improve representation?

Bidirectional encoding is a natural extension for providing each node with context from both directions of the spatial ordering. ECO uses a unidirectional scan together with a global mean of node embeddings, giving the decoder both node-specific representations and shared graph-level context.

With scan direction held fixed, the TSP1000 ordering ablation yields gaps of 5.31% for raw order, 4.84% for Morton order and 4.82% for Hilbert order. Spatial ordering therefore improves the measured quality of the unidirectional architecture.

A bidirectional design would add a reverse scan and a fusion step. At fixed width, two directional scans retain linear encoder scaling in node count, with additional scanning and fusion cost.

Thank the author for the detailed response and additional experiments. Some of my concerns have been addressed, however, two concerns still remains after reading the response and refined paper:

  1. The contribution of Mamba in ECO is limited compared with other components, based on Weakness 2 in my review above, the effect of Mamba is smaller than LS in terms of gap and DPO in terms of training time from Table 4 in paper, which differs from the paper's claims, although Mamba is declared as the main conrtibution, the performance improvement mainly comes from other components.
  2. Part of the design overlaps with [1], and no comparison is provided.

I think this paper would benefit from rearrange and examining the contribution of each component, and adjust the claims accordingly. as a result, I decide to keep my score.

[1] Pan, Mingjun, et al. "Preference optimization for combinatorial optimization problems." arXiv preprint arXiv:2505.08735 (2025).

Reviewer_Y1j7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes ECO, a neural solver for routing problems that aims to be efficient as well as accurate. It has three parts:

  1. A Mamba (state-space model) encoder-decoder in place of a Transformer. Nodes are put into Morton (spatial) order before encoding. This reduces encoder memory and the cost of each decoding step; choosing the next node still scales quadratically.

  2. Two-stage training: supervised warm-up on LKH-3 solutions, then iterative DPO on winner/loser solution pairs that the current policy generates in batches. This replaces online RL (PPO/REINFORCE).

  3. Local search used only during training, to build winner/loser pairs with a larger cost gap. No search is used at inference. Validation covers uniformly random TSP (200-5000 nodes) and CVRP (100-1000 nodes) against AM, POMO, LEHD, CNF and GFlowNet-HBG. It also includes memory/throughput comparisons against a Transformer version of the same pipeline, and ablations on TSP1000: backbone, PPO vs. DPO vs. other pairwise losses, SFT warm-up, local-search ratio, and node ordering. Reported results: 4.84% gap on TSP1000, 5.49% on TSP5000, the fastest neural inference, and PPO-level quality in about 3.4x less training time (10.2h vs. 34.5h).

Critical strengths

The two primary strengths I have identified are:

  1. Controlled evidence that batched DPO matches PPO at much lower cost. With the same Mamba backbone, DPO reaches 4.84% vs. PPO's 4.88% in 10.2h vs. 34.5h, and it beats reference-free pairwise losses trained on the same data. This is the paper's best-controlled result and directly supports its main efficiency claim.

  2. Using local search only during training measurably improves the policy. The ablations (ratio alpha, choice of operators, SFT on local-search routes vs. DPO pairs, winner/loser margin statistics) consistently show the benefit, TSP1000 gap drops from 9.55% to 4.84% with no search at test time. The idea is simple, reusable and practically useful.

Critical weaknesses

The primary weaknesses I have identified are:

  1. The baseline numbers reported are a bit confusing the state-of-the-art quality claim. Some examples are: LEHD greedy is reported at 3.20% / 6.83% on TSP500 / TSP1000. LEHD's own paper reports 1.56% / 3.17%. Against the published numbers, ECO (2.59% / 4.84%) is not the best method.

  2. The evaluation is narrow and incomplete. Only uniformly random TSP/CVRP instances. It is missing TSPLIB/CVRPLIB, distribution shift, cross-size generalization, and TSP10K solution-quality results even though memory is shown at 10K. Strong and directly relevant baselines are missing: BQ-NCO [1], INViT[2], ELG [3], SIL [4], and the concurrent DPO-for-NCO method BOPO[5]. Are inference budgets matched across methods? Training-time comparisons leave out the cost of generating LKH labels, which is substantial (about 40 CPU-hours for 100k TSP1000 instances, far more at TSP5000). It is unclear whether ECO's efficiency/quality trade-off holds outside the chosen setting.

[1] Drakulic, D., Michel, S., Mai, F., Sors, A. and Andreoli, J.M., 2023. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems, 36, pp.77416-77429.

[2] Fang, H., Song, Z., Weng, P. and Ban, Y., 2024. Invit: A generalizable routing problem solver with invariant nested view transformer. arXiv preprint arXiv:2402.02317.

[3] Gao, C., Shang, H., Xue, K., Li, D. and Qian, C., 2023. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. arXiv preprint arXiv:2308.14104.

[4] Luo, F., Lin, X., Wang, Z., Tong, X., Yuan, M. and Zhang, Q., 2024. Self-improved learning for scalable neural combinatorial optimization. arXiv preprint arXiv:2403.19561.

[5] Liao, Z., Chen, J., Wang, D., Zhang, Z. and Wang, J., 2025. BOPO: Neural combinatorial optimization via best-anchored and objective-guided preference optimization. arXiv preprint arXiv:2503.07580.

Questions for authors

I have the following primary questions:

  1. Were the GFlowNet-HBG and POMO numbers reproduced, or taken from the HBG paper? Does the HBG row use local search at test time?

  2. Why is LEHD's gap about twice its published value (3.20% vs. 1.56% on TSP500; 6.83% vs. 3.17% on TSP1000)? Was the official checkpoint used or did authors reproduce the results?

  3. Does the Transformer control in Figure 3 use FlashAttention or another memory-efficient attention? If not, how much of the out-of-memory gap remains with it?

  4. In Table 2, Transformer+PPO is trained without local-search pairs while Mamba+PPO uses them. What is Transformer+PPO's result with local search?

  5. How do the training-time comparisons (Figure 1, Table 2) change when LKH label generation is included, especially at TSP5000?

Requested experiments that could change my assessment and score:

  1. A comparison with BQ-NCO, INViT/ELG and BOPO at matched inference budgets, ideally as gap-vs-time curves (e.g., ECO with sampling vs. LEHD with its RRC refinement).
  2. Results on TSPLIB/CVRPLIB and in the train-on-100 / test-on-1000+ setting.

Potential future experiments (not required for acceptance/changing my rating). Evaluations on other problem types (VRP with time windows, pickup-and-delivery, scheduling).

5 comments
AuthorsOpenReview ↗

Response to Reviewer Y1j7 (1/3)

Dear Reviewer Y1j7,

We thank the reviewer for the time and care devoted to reviewing our manuscript and for the constructive comments that have helped us improve its quality and clarity. We also appreciate the reviewer's recognition of the controlled evidence that batched DPO achieves quality comparable to PPO at substantially lower training cost, and of the practical value of using local search during training to improve the policy without test-time search.

On TSP1000, batched DPO reaches a 4.84% gap in 10.2 h, while online PPO reaches 4.88% in 34.5 h. Both use the same Mamba backbone, SFT initialization and training-time local search (LS). ECO saves 24.3 h on one A800, a 70.4% reduction, at a gap difference of 0.04 percentage points. On the same buffered pairs, reference-free logistic and hinge ranking take 10.0 and 9.8 h and reach 5.31% and 5.58%. Table 4 and the matched preference-objective controls in the appendix isolate the training benefit of batched updates and the quality contribution of the DPO objective.

Q5 and Weakness 2. What changes when label generation is counted, especially at TSP5000?

The subsection Accounting for the cost of supervision separates shared SFT-label preparation from policy training. Figure 1 includes training rollout or candidate generation and excludes preparation of the shared labels. For a shared label-generation job taking L elapsed hours, the first-run speed ratio is (34.5 + L) / (10.2 + L), while the absolute training-time saving remains 24.3 h. With reusable labels, the ratio of the reported training times is 3.38. The approximately 40 CPU-hours cited in the review is aggregate CPU work; its contribution to elapsed time depends on the worker count.

At TSP5000, the measured first-run cost, including label generation, is 125.8 h for PPO and 58.3 h for ECO, a 2.16-fold speed ratio and a 67.5 h saving. The revised Accounting for the cost of supervision paragraph and the appendix subsection Training-cost and implementation records report the breakdown for a 100,000-instance label-generation job and one policy-training run.

MethodLabels (h)Policy (h)Total (h)
ECO30.028.358.3
PPO30.095.8125.8

Label preparation is shared by both methods. Counting this first-run cost preserves ECO's training advantage while making the total elapsed cost explicit.

Weakness 1 and Q2. Why do the LEHD numbers differ from the published results?

We retrained LEHD from scratch and tested it locally for every LEHD entry in Table 1. The TSP500 and TSP1000 gaps of 3.20% and 6.83% are results of those locally trained models. The table uses neither values copied from the LEHD paper nor evaluation of its released checkpoints. LEHD's published greedy gaps are 1.560% and 3.168%, while ECO reaches 2.59% and 4.84% on our test sets. We now identify the local retraining protocol explicitly and distinguish it from the published results in the Controls paragraph. Table 1 compares the locally evaluated implementations under its stated protocol.

Q1. Were POMO and GFlowNet-HBG rerun? Did HBG use test-time LS?

We locally reproduced both POMO and GFlowNet-HBG for Table 1. HBG uses local search at test time, following the evaluation setting in its paper. Its mean objectives on TSP200, TSP500 and TSP1000 are 10.78, 17.05 and 24.42. ECO uses LS to construct training preferences and performs constructive greedy inference without test-time search. The revised protocol description makes these decoding settings explicit so that the quality and timing results can be read together.

AuthorsOpenReview ↗

Response to Reviewer Y1j7 (2/3)

Weakness 2 and Requested experiment 1. How do strong methods compare at matched inference budgets?

Tables 1 and 2 add BQ-NCO, INViT-2V, BOPO and SIL, with measured base decoding results and runtimes per 1,000 instances. For TSP, BOPO uses the INViT-2V backbone; INViT-2V and BOPO appear as separate methods.

TaskMethod and base decodingGapTime (min/1,000)
TSP1000ECO, greedy4.84%0.90
TSP1000BQ-NCO, greedy5.41%15.6
TSP1000INViT-2V, multi-start and augmentation6.15%17.50
TSP1000BOPO, multi-start and augmentation5.13%2.58
CVRP1000ECO, greedy2.87%1.80
CVRP1000SIL, greedy5.01%3.33

ECO reduces BQ-NCO's TSP1000 gap by 0.57 percentage points, and BQ-NCO takes 17.3 times as long. INViT-2V and BOPO use multi-start and augmentation; ECO, BQ-NCO and SIL use greedy decoding. These method-specific decoding configurations are retained in the timing comparison. Related Work now discusses ELG's local/global policy ensemble for routing generalization; the quantitative additions focus on BQ-NCO, INViT-2V, BOPO and SIL.

Table 2 reports measured outcomes at 20- and 30-minute deadlines for 1,000 instances per task, starting from the same initial gaps and times as Table 1. For TSP1000, ECO adds sampling after greedy construction and LEHD adds RRC. Other methods keep their native decoding configuration. The deadlines cap total elapsed inference time, including sampling and refinement.

Task and methodStart (min)Initial gap20-min gap30-min gap
TSP1000 · ECO, greedy then sampling0.904.84%3.78%3.66%
TSP1000 · LEHD, greedy then RRC2.506.83%3.61%3.18%
TSP1000 · BQ-NCO, greedy15.65.41%5.41%5.41%
TSP1000 · INViT-2V, multi-start and augmentation17.506.15%6.15%6.15%
TSP1000 · BOPO, multi-start and augmentation2.585.13%5.13%5.13%
CVRP1000 · ECO, greedy1.802.87%2.87%2.87%
CVRP1000 · SIL, greedy3.335.01%5.01%5.01%

ECO sampling improves the TSP1000 gap from 4.84% to 3.78% and 3.66% at the two cutoffs. LEHD with RRC improves from 6.83% to 3.61% and 3.18%. The TSP comparisons share instances and Concorde references; the CVRP comparisons share instances and HGS references. BQ-NCO and SIL retain greedy decoding, and INViT-2V and BOPO retain multi-start and augmentation. The locally measured 5.41% BQ-NCO result therefore appears in both deadline columns. Tables 1 and 2 measure inference in minutes using completed-training checkpoints. Figure 1 plots optimization progress over approximately the first 10 training hours, including intermediate baseline models before training is complete.

SIL's published CVRP1000 results provide further context for decoding cost. Ten parallel local reconstruction iterations (PRC10) reach 4.52% in 0.7 s per instance, compared with 5.01% in 0.2 s for greedy decoding. Those figures use SIL's original test protocol; Tables 1 and 2 identify our local greedy SIL evaluation.

AuthorsOpenReview ↗

Response to Reviewer Y1j7 (3/3)

Weakness 2 and Requested experiment 2. What happens on public instances, under size transfer, and at TSP10K?

Appendix J reports public-benchmark and frozen-checkpoint transfer measurements, together with the large-scale protocol and measured results for batches of 16. Table 3 reports measured TSP10K and CVRP5K comparisons with runtimes per 1,000 instances.

  • Public instances. ECO's 100-node checkpoint reaches 4.97% on the 70 TSPLIB instances and 11.03% on the 100 CVRPLIB Set-X instances with greedy decoding. Scoring uses each instance's prescribed edge weights and reference cost, together with its demands and capacity for CVRP. LEHD's published greedy gaps are 5.260% and 12.520%, respectively. ECO's gaps are lower by 0.29 and 1.49 percentage points.
  • Train on 100, test on 1,000. With the size-100 checkpoint frozen and no target-size tuning, ECO reaches 6.67% in 0.90 min on TSP1000 and 4.88% in 1.80 min on CVRP1000, each over 1,000 instances. The target-scale controls reach 4.84% in 0.90 min and 2.87% in 1.80 min. Both checkpoints use the same greedy decoder, test instances and references. CVRP capacity changes from 50 at training size to 250 at test size.
  • Batch-of-16 measurements. Appendix J reports measured gaps of 5.77% for ECO and 6.12% for BOPO on TSP10K, and 2.92% for ECO and 5.08% for SIL on CVRP5K. Measured times for 16 instances are 0.0621, 0.2435, 0.3691 and 0.6830 min, respectively. ECO and SIL use greedy decoding, and BOPO uses multi-start and augmentation. TSP gaps use Concorde references, and CVRP gaps use HGS references at capacity 500.

Table 3. Measured large-scale results. Time is minutes per 1,000 instances.

TaskMethod and native decodingGapTime (min/1,000)
TSP10KECO, greedy5.77%3.88
TSP10KBOPO, multi-start and augmentation6.12%15.22
CVRP5KECO, greedy2.92%23.07
CVRP5KSIL, greedy5.08%42.69

Table 3 uses Concorde-based TSP gaps and HGS-based CVRP gaps, with capacity 500 for CVRP5K. ECO reaches 5.77% in 3.88 min on TSP10K and 2.92% in 23.07 min on CVRP5K, compared with BOPO's 6.12% in 15.22 min and SIL's 5.08% in 42.69 min. Appendix J reports the measured batch-of-16 results under the stated reference definitions and decoding settings.

These experiments demonstrate constructive routing on public benchmarks and under changes in problem size.

Q3. Which attention kernel ran in Figure 3 and how much of the memory gap survives?

The matched fused-attention control in Appendix J tests how memory-efficient attention changes the comparison. It keeps Transformer weights, precision, masks and batch size fixed. At TSP5000 and batch eight, ECO uses approximately 21 GB, the original Transformer uses 43.1 GB and the fused version uses 39.9 GB. Fused attention reduces peak memory by 3.2 GB and gives 1.14× the original Transformer's end-to-end throughput. ECO retains its memory advantage in this control.

Figure 3 reports the original Transformer implementation, with memory measured at batch size 8 and throughput at each model's largest fitting batch on an 80 GB A800. Its OOM point is around 7,000–7,500 nodes, while ECO uses approximately 40 GB at 10,000 nodes. The revised discussion treats this OOM point as an implementation-specific measurement. It distinguishes dense attention's quadratic arithmetic from the storage saved by a fused attention backend.

Q4. What is the missing Transformer+PPO result with LS?

Thank you for highlighting this missing control. We have added the measured Transformer+PPO+LS result to Table 4. On TSP1000, this variant reaches a 5.2% gap in 44 h of policy training on a single A800 (80 GB). The relevant comparisons are summarized below. All rows use SFT warm-up.

Backbone and updateTraining-time LSGapTraining time
Transformer+PPONo9.73%38.7 h
Transformer+PPOYes5.2%44 h
Mamba+PPOYes4.88%34.5 h
Transformer+DPOYes5.47%14.6 h
Mamba+DPO (ECO)Yes4.84%10.2 h

Adding training-time LS to Transformer+PPO reduces the gap from 9.73% to 5.2%, an improvement of 4.53 percentage points, with training time changing from 38.7 to 44 h. With PPO, SFT and LS retained, replacing Transformer with Mamba reduces the gap from 5.2% to 4.88% and training time from 44 to 34.5 h, a 21.6% time reduction. With Mamba, SFT and LS retained, DPO reaches 4.84% versus PPO's 4.88%, while reducing training time from 34.5 to 10.2 h, a 70.4% reduction.

These controls distinguish the contribution of training-time LS from the backbone and update-rule comparisons. Training times include rollout or candidate generation and exclude the shared SFT-label preparation cost, following the accounting in the revised manuscript. Table 4 and the appendix subsection Backbone comparison now report the completed control.

Comments on the paper

1 comment

Dear reviewers,

We have now received the author responses to your raised questions and concerns. Please go through them. Also, have they answered your questions appropriately? Please also look other reviewers' strengths / concerns. Have they changed your perception of the paper? In all cases, please communicate with the authors. It is important that we let them know what relevant issues still exist or have been answered. Please remember we have limited time to get any further responses from them.

Regards,

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.