- 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.
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) work for TSP and O(DTN) for CVRP, where D is the embedding dimension and T 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:
We see these as promising directions for improving the quality–cost trade-off while explicitly controlling memory and latency.