- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes PrefixCO, a prefix-autoregressive framework designed to improve the scalability and solution quality of autoregressive neural combinatorial optimization solvers. To address the challenges of limited expressiveness, inefficient decoding, and unstable RL training, PrefixCO adopts a prefix-transformer architecture with KV caching and a pointer-style decoder for efficient solution construction. It further combines imitation warm-starting with non-negative reward shaping to stabilize RL training. The reported results demonstrate substantial improvements in solution quality and inference efficiency compared with selected solvers.
Critical strengths
S1: The proposed PrefixCO has a certain degree of novelty.
S2: Ablation experiments validated the effectiveness of each module.
Critical weaknesses
W1: The methodology section relies heavily on textual descriptions and lacks rigorous mathematical formulations of several key components and procedures. This makes it difficult to fully understand the proposed framework and reproduce its implementation. Furthermore, the source code has not been made publicly available, further limiting the reproducibility of the reported results.
W2: Although PrefixCO claims to reduce the average per-step decoding complexity from O(N^2) to O(N) through KV caching, this improvement does not necessarily translate into lower overall computational or memory requirements. In particular, PrefixCO employs relatively large models with 47M parameters for TSP and 95M for CVRP, while the computational costs of prefix encoding and the memory overhead of KV caching remain insufficiently analyzed. Moreover, the experiments are limited to TSP-1000 and CVRP-500, leaving its scalability to substantially larger instances, such as TSP-10K, unclear.
W3: The experimental evaluation lacks comparisons with several recent state-of-the-art NCO methods, such as [1, 2].
W4: PrefixCO exhibits relatively weak cross-scale generalization compared with existing methods. As shown in Table 11, a model trained on TSP-100 achieves an optimality gap of 7.089% when evaluated on TSP-1000. In contrast, several existing methods [3, 4] can generalize from TSP-100 to TSP-1000 and even substantially larger instances, such as TSP-10M.
[1] Learning to Insert for Constructive Neural Vehicle Routing Solver. NeurIPS 2025.
[2] NExCO: Native Solution Expansion for Diffusion-based Combinatorial Optimization. ICLR 2026.
[3] INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer. ICML 2024.
[4] Learning to Reduce Search Space for Generalizable Neural Routing Solver. SIGKDD 2026.
Questions for authors
Why are the experiments on TSPLIB and VRPLIB restricted to relatively small-scale instances? Furthermore, why does the manuscript lack comparisons with state-of-the-art autoregressive NCO solvers on these benchmarks? Such comparisons would provide stronger evidence of the effectiveness and practical applicability of PrefixCO on real-world instances.
5 comments
Response to Reviewer Zoma (Part 2/3)
W2.2 & W4. Problem-size Scalability and Generalization to 10M instance.
Thank you for raising these questions and for pointing us to successful approaches for large-scale routing. Scaling an end-to-end autoregressive solver is challenging. As construction trajectories grow longer, the model must learn dependencies across more decisions, and the consequences of early choices may only become apparent much later in the tour. These challenges have made it difficult for previous autoregressive solvers (e.g., [9, 10]) to scale training to substantially larger instances. Methods such as INViT [8] and L2R [3] have made substantial progress through designs specifically tailored to large-scale generalization. Our work focuses on improving the solution quality and decoding efficiency of the autoregressive backbone itself. We appreciate your comments, which helped us clarify this goal and motivated us to evaluate both direct transfer across instance sizes and PrefixCO's performance on much larger instances when combined with segment-based reconstruction.
Direct transfer and performance at the target size. We agree that the 7.089% gap for TSP-100 → TSP-1000 in Table 11 indicates weak direct transfer across a tenfold increase in instance size. Under the same sampling budget (), a checkpoint trained on TSP-500 achieves a 0.089% gap on TSP-1000. When trained directly on TSP-1000, PrefixCO-SL solves instances of that size end to end with a 0.0076% gap in 14 seconds (Table 1, aug×8, ). The target-size result shows that the backbone can solve TSP-1000 efficiently when trained at that scale, while Table 11 shows how its performance depends on the training scale when the checkpoint is transferred directly.
PrefixCO-Segment: scaling to larger instances through segment reconstruction. To evaluate PrefixCO beyond TSP-1000, we combine it with the segment-based training and reconstruction used in LEHD [7] and SIT [6]. PrefixCO reconstructs segments of an existing tour, using 1,000-node segments by default. Each pass reconstructs all non-overlapping segments once. The 2Opt variant additionally applies sparse 2-opt restricted to the 16 nearest neighbors. We evaluate on TSP-10K from ML4CO-Bench-101 [5], TSP-100K from SIT [6], and the ten-million-node instance E10M.0 from FrontierCO [4]. All PrefixCO runtimes below are measured on a single RTX 4090.
The TSP-10K test set is from ML4CO-Bench-101 [5], and the TSP-100K test set is from SIT [6].
| TSP-10K | TSP-100K | |
|---|---|---|
| PrefixCO-Segment (pass=5) | 1.444 %, 1.4m | 2.105 %, 5.8m |
| PrefixCO-Segment (pass=10) | 1.232 %, 1.8m | 1.725 %, 9.5m |
| PrefixCO-Segment (pass=20) | 1.128 %, 2.5m | 1.565 %, 16.8m |
| PrefixCO-Segment (pass=40) | 1.064 %, 4.0m | 1.472 %, 31.4m |
| PrefixCO-Segment 2Opt (pass=5) | 0.837 %, 1.4m | 1.098 %, 5.6m |
| PrefixCO-Segment 2Opt (pass=10) | 0.704 %, 1.8m | 0.939 %, 9.2m |
| PrefixCO-Segment 2Opt (pass=20) | 0.649 %, 2.5m | 0.872 %, 16.6m |
| PrefixCO-Segment 2Opt (pass=40) | 0.622 %, 4.0m | 0.838 %, 31.4m |
Here one pass denotes performing reconstruction [6, 7] on N/segment_size non-overlapping tour segments, and "2Opt" denotes a sparse 2-opt restricted to the 16 nearest neighbors. Instance E10M.0 and its reference optimal value are taken from FrontierCO [4].
| E10M.0 | |
|---|---|
| INViT-Greedy* | OOM |
| L2R-Greedy* | 5.048 %, 96h |
| PrefixCO-Segment (pass=5) | 2.307 %, 26.0m |
| PrefixCO-Segment (pass=10) | 2.074 %, 47.7m |
| PrefixCO-Segment (pass=20) | 1.803 %, 91.2m |
| PrefixCO-Segment (pass=40) | 1.709 %, 178.2m |
| PrefixCO-Segment 2Opt (pass=5) | 1.177 %, 32.4m |
| PrefixCO-Segment 2Opt (pass=10) | 1.029 %, 55.5m |
| PrefixCO-Segment 2Opt (pass=20) | 0.936 %, 101.5m |
| PrefixCO-Segment 2Opt (pass=40) | 0.898 %, 191.4m |
Impact of Segment Size (TSP-10K).
| Segment Size 500 | Segment Size 1000 | |
|---|---|---|
| pass=20 | 1.456 % | 1.128 % |
| pass=40 | 1.437 % | 1.064 % |
| pass=20 + 2Opt | 1.234 % | 0.649 % |
| pass=40 + 2Opt | 1.200 % | 0.622 % |
Segment Size Matters. The results in the table demonstrate that increasing the segment size significantly improves performance. PrefixCO provides a backbone that scales the tour/route lengths the model actually processes up to 1000, with both efficiency and expressiveness.
Response to Reviewer Zoma (Part 3/3)
W3 & Q2. Add state-of-the-art NCO baselines, such as [1, 2].
Thanks for this suggestion. Since both [1] and [2] are non-autoregressive solvers trained with SL, we have added these baselines to Table 1 of the manuscript. For the reviewer's convenience, we also include the results below.
| TSP-100 | TSP-500 | TSP-1000 | |
|---|---|---|---|
| L2C-Insert RRC-100 | 7.75614, 0.0037%, 4.3m | 16.61020, 0.3892%, 3.8m | 23.41306, 1.2758%, 3.9m |
| L2C-Insert RRC-1000 | 7.75588, 0.0004%, 41.4m | 16.56461, 0.1137%, 37.8m | 23.23150, 0.4905%, 38.1m |
| NExCO Ds=5, 1×sampling | 7.75685, 0.0129%, 5.7m | 16.56737, 0.1303%, 2.1m | 23.17545, 0.2480%, 6.7m |
| NExCO Ds=5, 4×sampling | 7.75639, 0.0069%, 11.8m | 16.55772, 0.0720%, 6.7m | 23.14777, 0.1282%, 24.7m |
Q1. Large-scale TSPLIB and VRPLIB instances.
Thanks for your suggestion. We evaluated PrefixCO on large-scale TSPLIB and VRPLIB, with results as follows.
| TSPLIB-[201-1000] | |
|---|---|
| PrefixCO (S=32) | 0.1680% |
| VRPLIB-[201-500] | |
|---|---|
| PrefixCO (S=32) | 3.171% |
| VRPLIB-[501-1000] | |
|---|---|
| PrefixCO (S=32) | 4.637% |
Thank you again for helping us clarify the scope of our claims. Table 11 measures how a checkpoint transfers directly to a different instance size. The segment reconstruction experiments show how PrefixCO can be used within a solver for much larger instances. We hope that this distinction, together with the added baselines and real-world results, helps you assess the method’s practical performance.
[1] Learning to Insert for Constructive Neural Vehicle Routing Solver. NeurIPS 2025.
[2] NExCO: Native Solution Expansion for Diffusion-based Combinatorial Optimization. ICLR 2026.
[3] Learning to Reduce Search Space for Generalizable Neural Routing Solver. SIGKDD 2026.
[4] FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization. ICLR 2026.
[5] ML4CO-Bench-101: Benchmark Machine Learning for Classic Combinatorial Problems on Graphs. NeurIPS 2025.
[6] Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems. ICLR 2025.
[7] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.
[8] INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer. ICML 2024.
[9] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS 2020.
[10] Preference Optimization for Combinatorial Optimization Problems. ICML 2025.
Response to Reviewer Zoma (Part 1/3)
Thank you for your detailed review and for recognizing the contribution of PrefixCO's design and the value of the ablations. We appreciate your suggestions for making the method easier to reproduce and for evaluating its computational cost, cross-scale transfer, and performance on real-world instances.
Thank you for your suggestion regarding readability and reproducibility. In the revised manuscript, we have added Appendix B to provide a formal treatment of the components described in Sec. 3. It covers the embedder and prefix construction, the attention mask and the cached decoding recursion, the pointer output layer with the feasible action sets of TSP and CVRP, both training objectives in step-wise form, and the resulting complexity: O(N2) per constructed solution with O(N) cache memory, against O(N3) without the prefix factorization. With regard to the source code, we will make the full code available as soon as the paper is accepted. For the large-scale problem solving you are concerned about, we will release a demonstration code via a confidential comment.
Thank you for your nice question. We study the concrete computation requirements brought by the architecture via parameter count control. We trained a 1.8M-parameter model on TSP-100 using RL, comparable to BQ-NCO (3.1M), LEHD (1.4M), and POMO (1.4M). The training time is 17 hours for RL and 3.0 hours for SL on a single 4090.
This could be less than the training cost of previous RL-based autoregressive methods. If SL is used instead, the consumption of rollouts and the additional cost of exploration are avoided, and the time required to reach the same performance would be much less than 17 hours on a single 4090.
The architecture itself brings concrete computational improvement when parameters are matched. We further scale the model in this paper for its large scaling benefits (e.g., sublinear inference time scaling with respect to parameter count in the range of 1.8M to 47M), but this is optional.
In addition, although our paper presents an end-to-end approach, the decoder can in fact serve as a plugin for light-encoder methods: replacing their original decoder, which can only have one attention layer, with our decoder provides flexible control over dynamic expressivity (e.g., 2 or 3 layers if one does not want much extra computational cost).