acceptodds
Under review as a conference paper at ICLR 2027

Scaling Autoregressive Models for Neural Combinatorial Optimization

Abstract

Autoregressive (AR) models have long served as a flexible and general paradigm for neural combinatorial optimization (NCO), naturally constructing feasible solutions through sequential decisions. However, scaling AR solvers to larger instances remains challenging, especially under Reinforcement Learning (RL), where long horizons, sparse rewards, and expensive decoding limit both efficiency and performance. We argue that this limitation is not inherent to autoregression, but arises because existing AR designs do not jointly support expressive decision modeling, efficient incremental decoding, and stable long-horizon training. We propose PrefixCO, a prefix-autoregressive paradigm for scaling AR models for routing-style NCO. PrefixCO encodes problem instance attributes into reusable prefix representations and causally generates solutions with cached key-value states, computing static instance information once while allowing each step to condition on the evolving partial solution. This preserves AR flexibility and reduces the average per-step decoding complexity to from . PrefixCO further adopts a cache-compatible pointer decoder that matches prefix-derived candidate-node keys with a trajectory-conditioned query, producing a step-specific distribution over feasible next nodes while preserving incremental decoding efficiency. For training, PrefixCO introduces a scalable RL protocol that combines imitation warm-starting with non-negative improvement-based reward shaping. Experiments on TSP and CVRP show that PrefixCO establishes a strong quality-efficiency trade-off: under RL, it reduces the optimality gap on 1000-node TSP by 30 over prior AR baselines and achieves a 2 reduction on CVRP.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Autoregressive

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_ZomaOpenReview ↗
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
AuthorsOpenReview ↗

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.

W1. Mathematical Formulations & Source Code Availability.

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)O(N^2) per constructed solution with O(N)O(N) cache memory, against O(N3)O(N^3) 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.

W2.1 Concrete computation requirements.

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.

TSP-100
POMO aug×80.13%, 8s
POMO+PO aug×80.0425%, 8s
LEHD RRC 1000.0101%, 0.90m
LEHD RRC 10000.0019%, 7.9m
PrefixCO-1.8M (S=32)0.0053%, 13s
PrefixCO-1.8M (S=128)0.0019%, 53s
PrefixCO-1.8M (S=512)0.0011%, 3.5m
PrefixCO-1.8M-SL (S=32)0.0052%, 13s
PrefixCO-1.8M-SL (S=128)0.0008%, 53s
PrefixCO-1.8M-SL (S=512)0.0001%, 3.5m

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).

AuthorsOpenReview ↗

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 (S=32S=32), 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, G=1G=1). 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-10KTSP-100K
PrefixCO-Segment (pass=5)1.444 %, 1.4m2.105 %, 5.8m
PrefixCO-Segment (pass=10)1.232 %, 1.8m1.725 %, 9.5m
PrefixCO-Segment (pass=20)1.128 %, 2.5m1.565 %, 16.8m
PrefixCO-Segment (pass=40)1.064 %, 4.0m1.472 %, 31.4m
PrefixCO-Segment 2Opt (pass=5)0.837 %, 1.4m1.098 %, 5.6m
PrefixCO-Segment 2Opt (pass=10)0.704 %, 1.8m0.939 %, 9.2m
PrefixCO-Segment 2Opt (pass=20)0.649 %, 2.5m0.872 %, 16.6m
PrefixCO-Segment 2Opt (pass=40)0.622 %, 4.0m0.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 500Segment Size 1000
pass=201.456 %1.128 %
pass=401.437 %1.064 %
pass=20 + 2Opt1.234 %0.649 %
pass=40 + 2Opt1.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.

AuthorsOpenReview ↗

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-100TSP-500TSP-1000
L2C-Insert RRC-1007.75614, 0.0037%, 4.3m16.61020, 0.3892%, 3.8m23.41306, 1.2758%, 3.9m
L2C-Insert RRC-10007.75588, 0.0004%, 41.4m16.56461, 0.1137%, 37.8m23.23150, 0.4905%, 38.1m
NExCO Ds=5, 1×sampling7.75685, 0.0129%, 5.7m16.56737, 0.1303%, 2.1m23.17545, 0.2480%, 6.7m
NExCO Ds=5, 4×sampling7.75639, 0.0069%, 11.8m16.55772, 0.0720%, 6.7m23.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.

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

The paper proposes PrefixCO, a prefix autoregressive approach to scaling AR models for routing-style NCO. Their scaling method is based on the requirements of expressive decision modeling, efficient incremental decoding, and stable long-horizon training. They solve this by encoding continuous instances into prefix representations, then generating solutions via a KV cache and decoding using a pointer-decoder. They reduce the per-step decoding complexity from O(N2)O(N^2) to O(N)O(N). Their experiments on TSP and CVRP show improvements over existing neural solvers. Reducing the optimality gap by 30x30x on TSP over AR baselines and a 2x2x over CVRP baselines.

Critical strengths
  1. The paper addresses a practical bottleneck combined with convincing evidence of reducing the complexity and improving the efficiency. The proposed method addresses large-scale CO, and the authors show impressive speedups on these large instances.
  2. The authors evaluated on both TSP and CVRP, across numerous instances and sizes, showing a broad evaluation coupled with useful ablations that explain the roles of each part of the method. This gives confidence that their proposed choices do contribute to their reported results.
Critical weaknesses
  1. I believe the ablations can be more thorough. It's still somewhat unclear how much of the improvement comes from the main architectural idea and how much from optimization of the other components and their interaction. More comprehensive ablations that isolate the contributions of each component would help clarify where the improvements come from.
Questions for authors
  1. Could you clarify how your proposed method compares to the baselines when the model size and computational budgets are taken into account?
  2. How consistent are the results across independent training runs? How much variation is there in the results?
  3. Can you clarify/explain the complexity of your method beyond the per-step decoding complexity?
4 comments
AuthorsOpenReview ↗

Response to Reviewer MoAa (Part 1/2)

Thank you for your thoughtful review and for recognizing the gains in decoding efficiency and the breadth of the TSP and CVRP experiments. Your questions help us connect each design choice to its experimental evidence and explain how the comparison changes when model size and compute budgets are taken into account.

W1. More thorough ablations.

Thanks for your question. We agree that our component studies are currently spread across the main text and the appendix. We summarize them below along the component axis, so that each study, the single variable it controls, and the finding it yields are visible at a glance.

Ablations in the paper (each controls for one component):

#ComponentStudy (location)Controlled variableFinding
1Continuous prefix embedderEmbedder ablation, Sec. 4.3Input representation only: a UniCO-style discrete tokenizer vs. the continuous embedder, same backbone and recipeContinuous prefix drives the gap from 0.2076% to 0.0000% (TSP-100) and from 6.0322% to 0.0239% (TSP-500); the benefit grows with scale
2Prefix design / KV cachingKV-cache ablation, Sec. 4.3Decoding path only: identical weights, with vs. without the cache31 min → 4 s (≈465x) with identical solutions; the efficiency gain is architectural and fully decoupled from solution quality
3Non-negative reward shapingFig. 3 and Sec. 3.2, with the entropy diagnostic in the appendixReward objective only: the POMO group-relative objective vs. non-negative clamping vs. self-improvement, from the same warm-started policyThe unshaped objective exhibits reward hacking (mean cost rises while the group-best stays flat) and entropy divergence; both non-negative variants train stably, with entropy decreasing smoothly (0.0593 → 0.0387) and without mode collapse (the model still benefits from multi-trajectory decoding in Table 2)
4Imitation warm-startingFig. 5 (IL ablation) and the warm-up diagnostic table in the appendixWarm-start on vs. offWithout warm-start, RL on the 64-layer backbone fails to reach a reasonable gap; the warm-start checkpoint itself is weak (5.23% on TSP-500 with cheap 2-opt labels, vs. 0.0093% for the final model), so warm-start is a trainability enabler, not a quality source
5GQAGQA ablation, appendixAttention variant only: GQA-1 vs. MHA4 s vs. 14 s at S=1 with identical (or slightly better) gaps; a pure inference-speed gain

New component analyses added in the rebuttal:

  • Model size is matched, not conflated (our response to Q1): PrefixCO-1.8M outperforms the similarly sized POMO/LEHD/BQ-NCO under matched decoding budgets, and a 19M SL model outperforms the similarly sized GenSCO under a comparable training budget. So the improvement does not come from parameter count; scale merely widens the margin.
  • Seed-level consistency (our response to Q2): three independent training runs per setting, std ≤ 0.0103% everywhere and shrinking with larger inference budgets.

If there are any specific experiments you would like us to conduct, please let us know and we would be glad to include them.

Q1. Matched model size and computational budgets.

Although one of PrefixCO's advantages is its strong scaling benefits, our method also performs well when the parameter count is limited.

For comparison with representative AR solvers, we trained a 1.8M-parameter model on TSP-100, 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.

The training budgets reported for previous AR methods are largely inaccessible. The only reference we found is a GitHub issue in the POMO repository, where a user reports approximately 15 days on a single V100 for TSP-100. We therefore consider our training time to be comparable to or shorter than that of representative RL-based methods.

TSP-100
POMO aug×80.13%, 8s
POMO+PO aug×80.0425%, 8s
LEHD RRC 1000.0101%, 0.90m
LEHD RRC 10000.0019%, 7.9m
PrefixCO-1.8M (S=32)0.0053%, 13s
PrefixCO-1.8M (S=128)0.0019%, 53s
PrefixCO-1.8M (S=512)0.0011%, 3.5m
PrefixCO-1.8M-SL (S=32)0.0052%, 13s
PrefixCO-1.8M-SL (S=128)0.0008%, 53s
PrefixCO-1.8M-SL (S=512)0.0001%, 3.5m

We also note that inference speed is not proportional to the parameter count. On TSP-100, PrefixCO-1.8M (S=512) takes 3.5 min, whereas PrefixCO-47M takes 23.0 min. The parameter count increases by 26.1x, but the time increases by only 6.57x. This indicates that PrefixCO naturally favors models with more parameters via increasing the embedding dimension.

For comparison with non-autoregressive solvers, we choose GenSCO (one of the SOTA methods) as the baseline (19M), since it has reported training times of 1 day for TSP-500. We train a PrefixCO-19M model on TSP-500 under the same training time.

TSP-500
GenSCO (C=160) 2Opt0.012%, 18s
GenSCO (C=160) 2Opt0.010%, 1.2m
PrefixCO-19M-SL (S=32)0.0062%, 38s
PrefixCO-19M-SL (S=128)0.0022%, 2.5m
AuthorsOpenReview ↗

Response to Reviewer MoAa (Part 2/2)

Q2. How consistent are the results across independent training runs? How much variation is there in the results?

Thank you for your question regarding variance. For fast experiments covering several training setups, we reduce the number of layers from 64 to 8, and reduce the number of training steps to 1/4 for TSP-100 (RL), 1/6 for TSP-100 (SL), and 1/12 for TSP-500 (SL).

Each cell corresponds to one training seed (an independent checkpoint), averaged over its 3-seed evaluations; mean and std (ddof=1) are computed over the three training seeds.

Results across independent training runs (Gap in %)

modelbudgetseed 0seed 1seed 2meanstd
TSP-100 (RL)S=320.00960.00830.00960.00910.00077
TSP-100 (RL)S=1280.00380.00320.00440.00380.00060
TSP-100 (SL)S=320.000390.000470.000790.000550.00021
TSP-100 (SL)S=128-0.0000120.0000680.000120.0000600.000068
TSP-500 (SL)S=320.29620.31310.29440.30120.0103
TSP-500 (SL)S=1280.20030.21250.19820.20370.0077

Analysis. The results are consistent across independent training runs, with small standard deviations in all settings. In addition, with other configurations fixed, a larger inference budget leads to smaller variance. This is because a larger inference budget results in more sampling steps, which averages out the randomness in individual samples and thus yields more stable results.

Q3. Can you clarify/explain the complexity of your method beyond the per-step decoding complexity?

Thanks for your question. All stages of our algorithm, including both inference and training, keep the time complexity of a single instance at O(N2)O(N^2) while maintaining O(N)O(N) memory complexity, where NN is the number of nodes of one instance and model hyperparameters (e.g., the layer count LL and embedding dimension dd) are treated as constants.

Inference. Before the per-step decoding, there is a one-time prefill stage. The NN-node prefix is processed by a single bidirectional forward pass, costing O(N2)O(N^2), and this single pass produces both the KV cache and the decoding keys (the projected prefix outputs) for all NN candidate nodes at once. Each of the subsequent ≈N\approx N decoding steps then costs O(N)O(N): one token passes through the deep decoder with attention restricted to the cached prefix plus the already-generated tokens (total length at most 2N2N), and the pointer output layer computes one query against the NN decoding keys. The two pointer projections cost O(d2)O(d^2) per step, which is constant in NN. Hence prefill and decoding contribute O(N2)+N⋅O(N)=O(N2)O(N^2) + N \cdot O(N) = O(N^2) per solution construction, and the total for SS sampled trajectories is O(SN2)O(SN^2), i.e., linear in the sampling budget (with the augmentation factor being another constant multiplier, as reflected by the reported times in the main results table). Memory is O(N)O(N) per instance: the KV cache holds one key-value pair per layer per (prefix or trajectory) token, and the trajectory has at most NN tokens. The complexity is matched by the measurements: the KV-cache ablation in the paper shows that removing the cache, which forces full recomputation at each step and effectively makes construction O(N3)O(N^3), inflates TSP-100 inference (aug$\times$ 8, S=1) from 4 seconds to 31 minutes, a ∼465×\sim465\times slowdown.

Training. The same cache-compatible design also makes training parallelizable. In SL, teacher forcing lets the whole sequence (prefix + [SEP] + the NN ground-truth action tokens) be processed in a single causal forward pass, costing O(N2)O(N^2), with O(N2)O(N^2) cross-entropy for the NN pointer softmax distributions and a backward pass of the same order. Memory is O(N)O(N) in instance size (sequence length 2N+12N + 1). Without the prefix design, a deep decoder cannot reuse cached states, so the loss must be computed token by token, degrading training to O(N3)O(N^3) per instance, which is why LEHD- and BQ-NCO-style training does not parallelize across the construction trajectory. In RL, rollouts generate MM trajectories per instance at O(N2)O(N^2) each, and with our self-improvement reward shaping only the best trajectory requires a backward pass (Sec. 3.2), so training stays O(MN2)O(MN^2), linear in the rollout count with the per-instance cost level still O(N2)O(N^2).


We thank you again for the detailed suggestions. The component studies clarify which choices affect solution quality, training stability, and decoding speed. The complexity analysis also accounts for prefix encoding and the cost of constructing a complete solution. We appreciate the opportunity to make these comparisons easier to assess.

Reviewer_MoAaOpenReview ↗

Reply to Rebuttal

Thank you for your response/explanation and for providing the results tables. They address my concerns.

Thank you for your valuable feedback and for acknowledging our work. Your suggestions help us make the component-wise ablations, matched model-size/compute comparisons, variance analysis, and complexity discussion substantially clearer and easier to assess.

Reviewer_W4QLOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2(+1)
Presentation
3
Soundness
3
Read review
Paper summary

This work proposes PrefixCO, a prefix-autoregressive paradigm for scaling AR models for routing-style NCO.

Critical strengths

S1: This paper is well written and easy to understand.

S2: This paper reports multiple hyperparameter combinations for each baseline method.

Critical weaknesses

W1 (lack of scalability): The main promise of neural combinatorial optimization is to solve large instances because small instances can already be solved by classical solvers. However, this work only experimented with at most TSP-1000 while many existing works have been successfully demonstrated on TSP-10000. This seems to suggest that the proposed method sacrifices the scalability.

W2 (limited novelty): This work is a straightforward combination of a few existing ideas. The only novelty seems to be the reward shaping scheme. The paper should focus more on the novel idea instead of spending substantial effort in explaining how existing methods are used in this work.

W3 (marginal improvement): The reported improvements seem very marginal even though it is already scaling compute substantially (Table 1, Table 2). Considering the relatively large variance of compute scaling, it is a bit hard to distinguish the reported improvements from randomness.

Questions for authors

See weaknesses.

5 comments
AuthorsOpenReview ↗

Response to Reviewer W4QL (Part 1/3)

Thank you for your careful review and for noting the clarity of the presentation and the range of baseline configurations. We appreciate your questions about what the prefix architecture contributes, how far the solver scales, and how consistently the reported gains hold.

W1. Scalability.

Thank you for raising this question regrading scalability. 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., [1, 2]) to scale training to substantially larger instances, and in practice they often struggle to train on instances beyond 100 nodes. Methods such as INViT [3] and L2R [4] 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 PrefixCO's performance on much larger instances when combined with segment-based reconstruction.

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 [5] 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 [8], TSP-100K from SIT [6], and the ten-million-node instance E10M.0 from FrontierCO [7]. All PrefixCO runtimes below are measured on a single RTX 4090.

The TSP-10K test set is from ML4CO-Bench-101 [8], and the TSP-100K test set is from SIT [6].

TSP-10KTSP-100K
PrefixCO-Segment (pass=5)1.444 %, 1.4m2.105 %, 5.8m
PrefixCO-Segment (pass=10)1.232 %, 1.8m1.725 %, 9.5m
PrefixCO-Segment (pass=20)1.128 %, 2.5m1.565 %, 16.8m
PrefixCO-Segment (pass=40)1.064 %, 4.0m1.472 %, 31.4m
PrefixCO-Segment 2Opt (pass=5)0.837 %, 1.4m1.098 %, 5.6m
PrefixCO-Segment 2Opt (pass=10)0.704 %, 1.8m0.939 %, 9.2m
PrefixCO-Segment 2Opt (pass=20)0.649 %, 2.5m0.872 %, 16.6m
PrefixCO-Segment 2Opt (pass=40)0.622 %, 4.0m0.838 %, 31.4m

Here one pass denotes performing reconstruction [5, 6] 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 [7].

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 500Segment Size 1000
pass=201.456 %1.128 %
pass=401.437 %1.064 %
pass=20 + 2Opt1.234 %0.649 %
pass=40 + 2Opt1.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.

AuthorsOpenReview ↗

Response to Reviewer W4QL (Part 2/3)

W2. Novelty.

Thank you for raising this point. Our main contribution is an autoregressive architecture that can scale to deeper, more expressive models and push the solution quality attainable by autoregressive solvers for combinatorial optimization. Achieving this is non-trivial because the architecture must accommodate continuous instance features, instance-specific action spaces, and feasibility constraints that evolve during solution construction, while keeping decoding efficient as model capacity grows. These requirements shaped how we designed the components to work together. The substantial improvements in solution quality over prior autoregressive solvers in our experiments demonstrate the value of this architectural adaptation. We appreciate that reward shaping stood out in your reading, and we would like to clarify how it fits into the paper’s contributions. The architecture is the primary contribution (Sec. 3.1). Reward shaping is a secondary contribution motivated by a training failure mode we observed with PrefixCO (Sec. 3.2). The supporting and exploratory techniques are discussed in Sec. 3.3 and the accompanying appendix.

The central novelty is a CO-native architectural factorization. In prior AR solvers, expressiveness and incremental caching are mutually exclusive rather than independently tunable: light-decoder models (AM, ReLD) retain O(N) decoding only by restricting the decoder to a single layer, capping their representational capacity over the evolving trajectory, while heavy-decoder models (BQ-NCO, LEHD) buy capacity at O(N2)O(N^2) per step and O(N3)O(N^3) per solution because their decoders inherently preclude KV reuse. PrefixCO's prefix-autoregressive factorization, where static instance information is computed once and reused as a cached prefix while the deep decoder operates causally over the trajectory, is precisely the move that dissolves this trade-off rather than trading along it. That this is not a routine assembly of existing pieces is evidenced by the state of the art itself: UniCO attempted the same transplant from LLM practice, but without the CO-native adaptations it suffered from a discrete tokenizer and feature flattening; in our ablation (Table 3), the discrete tokenizer loses 6.03% on TSP-500.

More broadly, transferring a mature modeling paradigm into CO is itself a non-trivial contribution when it requires careful redesign around continuous problem attributes, instance-specific and dynamically constrained action spaces, and feasibility. The Attention Model is the canonical example: the Transformer was not new, yet its CO-specific adaptations had a lasting impact on the field. Our contributions should be read in the same spirit, component by component:

  • Pointer-style output layer. Borrowing only the high-level "select from input elements" idea, not the RNN-era formulation, we replace the LM head with a mechanism that matches prefix-derived candidate keys against a trajectory-conditioned query. This is a necessity, not a convenience: the continuous embedder makes an LM head infeasible (no fixed vocabulary), and the prefix outputs double as decoding keys, which eliminates the separate encoder entirely. As detailed in the appendix, the embedder and the pointer decoder are inherently coupled by design, which is also why we report controlled single-component studies (Table 3) rather than a sequential ablation.
  • Continuous embedder. We show empirically that discrete tokenization rounds away exactly the geometric information that matters, with the damage growing as instances densify (Table 3).
  • KV-cached O(N) decoding for a deep decoder. KV caching is standard in LLM inference, but making it valid for a 64-layer expressive decoder over a constrained action space is exactly what the prefix factorization buys; the same weights take 31 min without the cache and 4 s with it (Table 4).
  • Non-negative reward shaping. We agree this one is recognized; we would add that it is not an isolated contribution either: in matched experiments the reward-hacking failure mode appears under the prefix transformer but not under POMO (appendix), i.e., it characterizes what the new architecture requires to be trainable, not a generic shaping trick.
AuthorsOpenReview ↗

Response to Reviewer W4QL (Part 3/3)

W3. Magnitude of Improvement.

Thanks for the question. Even with a minimal computational budget (G=1/S=1) and without inference-time compute scaling, PrefixCO still delivers substantial improvements over strong baselines in both solution quality and inference speed.

  • TSP-1000 (Table 1). Against the strongest non-AR baseline, GenSCO (C=160, 2Opt), PrefixCO-SL (aug×8, G=1) attains a 4.7x lower gap at 16.7x faster inference: 0.0076% in 14 s vs. 0.036% in 3.9 min.
  • TSP-500 (Table 2). Against LEHD at its heaviest budget (RRC-1000), PrefixCO (aug×8, G=1) reaches 14% of its gap with 450x faster inference: 0.0246% in 5 s vs. 0.175% in 37.5 min.
  • CVRP-500 (Table 2). PrefixCO (aug×8, S=1) already outperforms LEHD RRC-1000 with a lower gap and a 247x speedup: 1.322% in 8 s vs. 1.561% in 33 min.

Furthermore, when scaling inference-time compute via independent runs as in the paper, the variance tends to decrease, and this trend holds across problems and training methods.

Variance of Obj.

TSP-500 (SL)CVRP-500
S=10.00260.0144
S=80.00020.0064
S=320.00010.0046

Thank you again for your constructive feedback. We hope the comparisons with identical model weights clarify the effect of caching, and that the larger-instance experiments and results across seeds help you assess the scope and consistency of the gains. We would appreciate your considering these results and clarifications when reassessing the paper.

[1] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS 2020.

[2] Preference Optimization for Combinatorial Optimization Problems. ICML 2025.

[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.

[5] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.

[6] Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems. ICLR 2025.

[7] FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization. ICLR 2026.

[8] ML4CO-Bench-101: Benchmark Machine Learning for Classic Combinatorial Problems on Graphs. NeurIPS 2025.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response and Summary (1/2)

We thank the Area Chair and the reviewers for their thoughtful and constructive feedback on our paper. Overall, the reviewers found the presentation clear and easy to follow, the evaluation on TSP and CVRP broad, and the ablations informative about where the gains come from; they also credited PrefixCO with a degree of novelty. PrefixCO builds on a prefix-autoregressive factorization: static instance information is computed once and reused as a cached prefix, while a deep decoder constructs the solution causally over the construction trajectory. This design combines expressive decision modeling with O(N)O(N) per-step decoding instead of O(N2)O(N^2), and enables parallelizable and scalable training.

Across reviews, PrefixCO is acknowledged for its

  • "a certain degree of novelty" in the prefix-autoregressive design, together with "substantial improvements in solution quality and inference efficiency" (Zoma);
  • ablations that "validated the effectiveness of each module" (Zoma) and "useful ablations that explain the roles of each part of the method", evidence that "gives confidence that their proposed choices do contribute to their reported results" (MoAa);
  • "convincing evidence of reducing the complexity and improving the efficiency" for "a practical bottleneck", with "impressive speedups" and a "broad evaluation" on TSP and CVRP "across numerous instances and sizes" (MoAa);
  • a "well written and easy to understand" presentation, supported by reporting "multiple hyperparameter combinations for each baseline method" (W4QL).

Notably, under RL, PrefixCO substantially improves the optimality gap over prior autoregressive solvers on 1000-node TSP and on CVRP. The efficiency gain is architectural: with the cache removed, the model has to recompute at every step, which takes far longer but yields exactly the same solutions. And we confirm that source code will be released upon acceptance.

AuthorsOpenReview ↗

General Response and Summary (2/2)

Each concern raised is answered below, either by clarification or by additional evidence. The ratings now stand at 3, 3, and 3.

Major concerns and the corresponding responses:

  • Scalability to substantially larger instances (W4QL, Zoma): We evaluated PrefixCO-Segment, which combines our backbone with the segment-based training and reconstruction used in LEHD and SIT, on the TSP-10K and TSP-100K test sets and on E10M.0, an instance at the 10-million-node scale. At 40 passes the gaps are 1.064% on TSP-10K and 1.472% on TSP-100K, and 0.622% and 0.838% with the sparse 2-opt variant. On E10M.0, PrefixCO-Segment outperforms both baselines, INViT-Greedy and L2R-Greedy. PrefixCO performs well on large-scale TSPLIB and VRPLIB instances. In the main text we stated the limits of zero-shot transfer across sizes in a new subsection, Sec. 4.5, and restricted the scalability claim to autoregressive solvers trained with RL, so the scope of the claims is clearer.
  • Novelty of the contribution (W4QL): We made the architectural claim explicit in Sec. 3 and the related work: in earlier autoregressive solvers decoder capacity and cached incremental decoding are not simultaneously available, and the adaptations that let PrefixCO have both are the continuous embedder, the cached prefix with a pointer output layer, and the reward shaping and warm-start that keep a deep decoder trainable. The single-component studies in Table 3 and the appendix place the result with these components: solution quality with the embedder, decoding speed with the cached prefix and GQA, and stable training with the reward and the warm-start.
  • Model size, inference budget, and training randomness (W4QL, MoAa): We trained one model of the size of the autoregressive baselines (POMO, LEHD, BQ-NCO) and one of the size of GenSCO, within its reported training time; at a comparable decoding budget both outperform the methods they are matched with. Independent training runs on TSP-100 and TSP-500, reported in the appendix, give standard deviations below 0.011%, and the variance shrinks as the inference budget grows.
  • Complexity and concrete cost beyond the per-step term (Zoma, MoAa): We added an analysis of every stage, inference and training alike: inference takes O(N2)O(N^2) time per constructed solution with O(N)O(N) cache memory, against O(N3)O(N^3) without the prefix factorization, and training stays linear in the rollout count. Two measurements give the concrete cost. On TSP-100, with identical weights, construction takes 31 minutes without the cache and 4 seconds with it. A model of the size of POMO and LEHD trains in 17 hours under RL and 3.0 hours under SL on a single RTX 4090 to reach lower gaps than either of them, a budget we consider comparable to or shorter than that of the representative RL baselines.
  • Additional SOTA baselines (Zoma): We added L2C-Insert and NExCO, two recent supervised non-autoregressive solvers, to Table 1 of the manuscript; PrefixCO attains a lower gap and a shorter inference time on TSP-100, TSP-500, and TSP-1000.
  • Reproducibility and presentation (Zoma): We added an appendix giving the formal treatment of every component: 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, and the resulting complexity. The complete computational workflow is now in the main text, with the problem-size scaling extension section in the appendix, so the construction can be followed step by step and matched against the formal treatment there. Demonstration code for the large-scale solver is available for inspection.

We sincerely thank the Area Chair and the reviewers for their careful reports and for comments that have improved the paper substantially. We hope the new results and the added explanations above resolve the concerns each reviewer raised, and we are truly grateful for the time and consideration they devoted to our paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.