acceptodds
Under review as a conference paper at ICLR 2027

MiLoop: Selective Memory Propagation for Neural Combinatorial Optimization

21 views

Abstract

Constructive neural combinatorial optimization (NCO) has emerged as a promising paradigm that learns to construct solutions to combinatorial optimization problems (COPs) step by step, which reduces reliance on handcrafted rules and enables fast inference. While many methods with dynamic embeddings generalize well, they typically rebuild subproblem representations from scratch at each step using deep attention stacks. Many high-performing methods in this category rely on solution labels or pseudo-labels for efficient training, or on aggressive search space pruning during reinforcement learning (RL). To address these limitations, we propose **Memory-in-the-Loop (MiLoop)**, a purely RL-based constructive framework that leverages the multi-step computation already required by a rollout for selective memory propagation. Each rollout provides solution-quality feedback for learning while propagating historical representations, thereby enabling a shallow policy to learn effective dynamic embeddings without external solution labels or training-time search-space pruning. Specifically, MiLoop fuses current embeddings with historical memory before the attention layers and applies adaptive gated updates afterward. The updated representations support both current decisions and stepwise reuse. Extensive experiments across four COPs demonstrate that MiLoop consistently produces high-quality solutions on instances **ranging from 100 to 10 million nodes**, highlighting its strong generalization ability.

Primary area:
optimization
Keywords:
neural combinatorial optimization, selective memory prapagation, vehicle routing problem

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_NUAGOpenReview ↗
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-10710^7 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.

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

This paper proposes MiLoop for constructive neural combinatorial optimization. MiLoop combines current inputs with node memories from previous steps and applies gated updates to reuse representations throughout solution construction. It is trained through reference-free DPO using pairs of self-generated solutions without external solution labels. Experiments on TSP, CVRP, PDTSP, and KP evaluate generalization from small training instances to larger problems and examine the contributions of the memory components.

Critical strengths
  1. Representation reuse is effective across multiple problems and supports generalization to larger instances. Under greedy decoding, routing policies trained on 100-node instances are applied to problems with 10K or more nodes. Performance degradation with increasing size is smaller than that of several baselines on TSP, while the CVRP gap decreases from 2.87% at 100 nodes to 1.09% at 10K nodes. These results demonstrate the transfer of representations learned on small instances to larger problems. (§4.1–4.2, Tables 1–3)
  2. Ablations support the contribution of selective memory. Removing memory fusion or gated updates degrades performance. In comparisons corresponding to greedy decoding, three-layer MiLoop achieves lower gaps than a six-layer memory-free model, with approximately half the inference time on TSP10K. This supports the effectiveness of representation reuse over simply increasing depth in the evaluated setting. (§4.3–4.4, Tables 4–5)
Critical weaknesses

  1. The practical advance over existing methods with stronger inference procedures is insufficiently established. TSP and CVRP are extensively studied, and existing methods include inference procedures that improve solution quality, such as beam search for BQ and RRC for LEHD. However, these methods are primarily evaluated with greedy decoding in the main comparisons, whereas MiLoop reports both greedy and 100-start results. The results therefore establish strengths of the greedy policy but do not sufficiently demonstrate a meaningful solution-quality–compute advantage when existing methods also use additional inference computation. This concerns the evaluation needed to establish the practical contribution of representation reuse, rather than a requirement to propose a new sampling method. (§4.1–4.2, Tables 1–2)
Questions for authors
  1. What solution-quality–inference-time advantage does MiLoop offer when established inference procedures, such as beam search for BQ and RRC for LEHD, are included? Could comparisons under similar time budgets at representative problem sizes clarify this?
  2. How do you explain the relatively robust performance as problem size increases under greedy decoding, including the decreasing CVRP gap? To what extent do the existing analyses explain these observations?
Reviewer_psJ4OpenReview ↗
Rating
3(+2)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Dynamic NCO (sometimes called decoder-only) methods are well known for their excellent ability to generalize to larger sizes, but also for their complexity. Another drawback is that they are typically trained using labeled data, with expensive self-improvement algorithms, or by applying different pruning strategies. This work addresses an important question: how to make these models faster and better at generalization, and how to train them more efficiently. The authors propose a novel framework, called Memory-in-the-Loop (MiLoop), that reuses computation across different construction steps. Experiments show that the proposed method generalizes well, but the experimental settings and the list of baselines raise many questions about the real performance of the proposed model.

Critical strengths
  • This work is well motivated. NCO methods with dynamic embeddings show very good generalization ability, but they are very expensive, and reusing computation across construction steps is the right way to improve these models.

  • Training does not require labeled data, and the model performs well in large-scale generalization.

Critical weaknesses

The experimental settings lead to the wrong conclusion that the proposed method is much better than existing state-of-the-art methods.

  1. The authors criticize pruning in previous works, claiming that it is not a good idea, and then use the same technique: during inference, they limit the candidate set to 200/400 nodes. It seems this pruning is applied only to their method and not to the other baselines, which could explain why other baselines run out of memory (OOM) on large instances.

  2. The claim that MiLoop consistently produces high-quality solutions is not supported by the experiments. MiLoop with M=100 beats all greedy baselines, but this comparison is extremely unfair. All baselines can be run in the same setting, and I doubt that MiLoop would still be consistently better. Across all results, we see that MiLoop performs very poorly on small instances. The running times are also misleading: M=100 should be 100x slower than greedy decoding. This can probably be sped up by carefully packing instances into a batch and running them in parallel, but this can make the proposed method look faster than it is.

  3. There are a few papers specialized in solving large-scale TSP and CVRP, and they are not reported among the baselines. The paper by Luo et al. (2025a) is cited and discussed in the manuscript, but not included in Tables 1 and 2. Judging from the results reported in that paper, it appears to outperform MiLoop on large-scale CVRP under the same time budget, which raises the question of why it was excluded.

Questions for authors

Q1 (most important): Can you perform the “pruning to 200/400 candidates” and “M=100” experiments for the existing baselines? If not, you should stick to a greedy-vs-greedy comparison and revise your manuscript and claimed contributions. Luo et al. (2025a) should be added to the list of baselines.

Q2: It is not explained how the candidate set is limited to 200 nodes per step. Is it the same approach as in the reference (Chen et al., 2025), i.e., a simple nearest-neighbor heuristic? Whatever the pruning algorithm is, it is unclear how it is implemented. Is the restriction applied only to action scoring, or before the attention (I suppose the latter, otherwise the attention memory would explode)? If so, nodes outside the candidate set do not exist in the memory table, and at every step some unseen nodes will appear. How are their memories initialized? Section 3.1 states that TSP uses the current embeddings as initial memories, while Appendix B.1.2 states that CVRP initializes memories to zero. Is that really the case to have different memory initialization for different problems? On the other hand, it seems it is possible that node memory can be updated at some step, and then that node may not be selected (and updated) for a long time. How are these cases handled?

Q3: Is there any explanation for why MiLoop performs poorly on small problem sizes (see the greedy numbers for TSP100, CVRP100, KP200, and the small TSPLib and CVRPLib instances) but outperforms all baselines on larger sizes? I strongly suspect that all these inference tricks are responsible for this, and not the method itself. Only a fair comparison can answer this question.

Q4: What does the parameter M mean for CVRP? M is the number of distinct starting nodes in decoding, but in CVRP, don’t all solutions start from the depot? Also, why is the CVRP inference time for 1K instances much faster than for TSP1K? Since the method uses 400 candidate nodes for CVRP and 200 for TSP, it should be at least 2x slower.

Q5: What is the motivation for the analysis presented in Figure 3? It is expected that your model’s embeddings are more similar to those from the previous step than the embeddings of traditional dynamic-embedding models are. Dynamic models recompute embeddings at every step, whereas your model updates memory through a learnable gate. It is completely expected behavior, but I do not see why this is important, or why more similar embeddings should lead to better decisions. Can you elaborate on this? In addition, it would be interesting to plot the adaptive gate values for each node throughout the construction process, to see when the previous memory is retained and when it is overwritten.

Q6: PDTSP is not a “well-studied COP” in NCO; even the results table has only one neural baseline for it. It would be more useful to apply your method to some scheduling problems (JSSP, FJSP, etc.), as they are very important and genuinely well-studied in the NCO community. But this raises another question: would your method work for these types of problems? It seems that your method would fail if there is no simple heuristic for reducing the candidate set. Since a kNN heuristic does not exist for such problems, your method could not scale to larger instances.

Another remark: Rec-NCO is the work most closely related to yours, and you use it as a reference point in the discussion. However, it is not mentioned in the introduction or in the related work. It should be introduced and positioned there, since it also reuses embeddings across construction steps.

1 comment

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.

Comments on the paper

1 comment

The additional experiments support MiLoop’s advantage on large-scale TSP and substantially address my main concern. I will therefore raise my rating from Weak Reject to Weak Accept.

However, comparisons with stronger inference procedures are limited to TSP5K and TSP10K, leaving relative performance on TSP100, TSP1K, and CVRP unclear. Table 1 of the original LEHD paper reports gaps of 0.0016% on TSP100 and 0.719% on TSP1K with 1,000 RRC iterations. Could you clarify why these settings were excluded from the additional comparisons and whether MiLoop’s principal contribution should be understood as generalization from small training instances to large problems, rather than improved solution quality across problem sizes?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.