- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposed MiLoop, a autoregressive neural solver for combinatorial optimization. MiLoop embeds the current residual problem, fuses current features with stored node representations, processes them with a shallow attention stack, and uses feature-wise gates to combine the resulting representations with the previous memory. And the memory is used for both updating the information for next step and scoring for the current step. The model is trained with a reference-free DPO algorithm and the experiments on TSP, CVRP, PDTSP and KP, on TSPLib/CVRPLib benchmarks, and on DIMACS TSP instances with up to 10M nodes report lower gaps than the neural baselines.
Critical strengths
-
Controlled evidence for useful memory reuse. The distinction between fusing history before the backbone and selectively retaining representations afterward is technically coherent. Table 5 tests both components separately and together across three scales, rather than relying only on comparisons with unrelated architectures. On TSP10K, full three-layer MiLoop obtains a 2.56% gap, compared with 5.63% without either memory component and 4.39% for a six-layer memory-free model; the reported times are 2.96s versus 5.84s for the latter comparison. Table 4 also tests an existing recurrent embedding design.
-
Strong large-scale generalization. In table 1, the model is trained on TSP100, but it achieves 1.56% and 1.81% gap on TSP5K and TSP10K, respectively. Sec 4.2 shows that the model can reaches high quality solutions in ultra large instances.
Critical weaknesses
-
The main comparisons are not matched in decoding strategy or time. The headline claims ("MiLoop (M=100) outperforms all neural baselines across all settings", Sec. 4.2; the lowest average gaps in all scale groups of Table 2) compare MiLoop with 100-start decoding against baselines run with greedy decoding or ×8 augmentation. None of the baselines is given a comparable search budget, e.g., beam search for BQ, RRC for LEHD, sampling for SIGD, or multi-start for the static-embedding models. M=100 is also far more expensive: 1.27m on TSP1K vs. 0.8s for LEHD and 0.9s for BQ (greedy), and 20.99m on CVRP5K, longer than the 5-minute HGS run used as the reference.
-
The large-scale evaluation omits a directly relevant baseline and provides limited evidence for CVRP scalability. “Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems” (Luo et al., 2025a) is cited but not compared, despite targeting efficient large-scale TSP/CVRP and reporting greedy construction results up to 100K nodes. MiLoop’s synthetic CVRP experiments stop at 10K customers, with CVRPLIB evaluations extending to 30K; its 10M-node results concern TSP only. Consequently, its quality–efficiency advantages over this existing scalable solver, particularly on larger CVRP instances, remain insufficiently established.
-
Several experimental details needed to interpret the results are missing or not discussed. The benchmark and ultra-large-scale comparisons (Tables 2-3, with per-instance results in Tables 11-12) report no runtime, include no classical solver (LKH3 for TSP, HGS for CVRP), and do not state what the gap is computed against (optimal or best-known solutions, or LKH3/HGS runs). Table 3 compares only against LEHD, INViT and L2R under greedy decoding on instances with up to 10M nodes. Fast inference is the main argument for a constructive solver, so runtimes at 105- nodes and a classical-solver reference are needed to judge the practical value of these results. The ablation does not discuss its most surprising result. In Table 5, keeping only the gated update (no fusion) is worse than using no memory at all: 1.79% / 7.93% / 9.98% vs. 1.61% / 6.59% / 5.63% on TSP100 / 1K / 10K. The paper reads Table 5 only as showing "complementary roles" of fusion and update. A gated update that by itself hurts generalization needs an explanation, because it bears directly on whether the proposed update mechanism helps on its own or only in combination with fusion.
Questions for authors
Q1. Budget-matched comparison. Could you compare MiLoop and the baselines under matched decoding or matched wall-clock time? For example: BQ with beam search, LEHD with RRC, SIGD with sampling, and multi-start or ×8 augmentation for the static-embedding models, at a time budget similar to MiLoop (M=100); or, conversely, MiLoop with a budget matched to the baselines (e.g., M=8 vs. ×8 augmentation). A gap-vs-time plot for TSP/CVRP at 1K-10K would make the trade-off clear.
Q2. CVRP gap decreasing with N. MiLoop's CVRP gap is lower at 5K/10K than at 1K. L2R, INViT, GLOP-G and ICAM show the same pattern, while BQ, LEHD, SIGD and L2C-Insert degrade. Since this pattern underlies MiLoop's large-scale advantage on CVRP, could you explain it?
Q3. Reference, runtime and classical solvers in Tables 2-3. What is the gap computed against in each table (optimal / best-known solutions, or LKH3/HGS runs)? Please report wall-clock time per method and instance group, and add LKH3 (TSP) and HGS (CVRP) under stated time budgets.
Q4. Update-only vs. no memory. Why is keeping only the gated update worse than using no memory at all, especially on TSP10K (9.98% vs. 5.63%)?
Q5. Role-specific parameters. Separate fusion matrices 𝑊𝑓𝑢𝑠𝑖𝑜𝑛1,2,3 and role-specific gates are used, although the start and current roles are already encoded by 𝑊𝑓𝑖𝑟𝑠𝑡 / 𝑊𝑙𝑎𝑠𝑡. In TSP, moreover, the memory of 𝜋𝑡−1 is written in the unvisited role and used only once in the "last" role. Please ablate shared vs. separate fusion matrices and gates.
Q6. Baseline. Could the authors compare against Luo et al. (2025a) on common datasets and extend the CVRP evaluation to 50K/100K, or explain the current scale limit? Please report greedy solution quality, runtime, and peak memory under consistent capacities and reference solutions, explicitly disclose differences in training scale, and report reconstruction-based results separately under comparable time budgets.
Minor (presentation). The introduction says that constructive models produce complete feasible solutions in a single rollout without iterative search, and it lists NAR methods (Joshi et al., 2019; DIFUSCO) in this category. This does not hold for NAR methods. They output an edge heatmap that is not itself a feasible solution, and feasibility comes only from a separate decoding or search step (greedy decoding with masking, beam search, MCTS or sampling, often followed by 2-opt). DIFUSCO also needs several denoising steps. Appendix A.1 describes heatmaps the same way, as guiding subsequent construction and search, so the introduction is inconsistent with the paper’s own related-work section. Please revise the taxonomy or the claim.
Dear authors,
Thank you for your answers.
We could continue to discuss pruning - I know you claim that pruning during training is a limitation because it can restrict exploration. But if you use the same pruning during inference, the policy also cannot go to the areas that were restricted in training. So I do not see a limitation here, because these areas are usually not important in this type of problem. However, this is not a crucial part of the work, but I still think that claim that pruning is bad, and then using it yourself, can lead to wrong conclusions.
I am happy to see the updated experiments. Now the methodology is correct and the comparison is fair.
In the pruning setting, the gain in performance is small, and the running time is about the same as BQ-NCO. But your method has an important advantage - you trained it without solved instances.
However, it is still unclear why your model is not competitive in the in-distribution setting but works very well on larger sizes. This remains an open question.
Considering all of the above, I support acceptance of this work and I increased my score to 3.