PaperlayerView exact revision on arXiv

Source-linked AI summary

MiLoop: Selective Memory Propagation for Neural Combinatorial Optimization

Changliang Zhou, Yuanyao Chen, Rongsheng Chen, Zhiyun Lin, Zhenkun Wang

arXiv:2610.01685v1cs.LG

TL;DR

Constructive NCO offers stepwise solution generation, but dynamic-embedding methods often rebuild representations with deep attention stacks and may rely on labels or pruning. MiLoop uses rollout-based RL with selective memory propagation to reuse representations, and experiments report high-quality solutions across four COPs and scales from 100 to 10 million nodes.

  • Problem

    Dynamic-embedding methods can rebuild subproblem representations at each step using deep attention stacks, while many high-performing approaches rely on solution labels, pseudo-labels, or training-time search-space pruning.

    Source: §1 · p. 2

  • Method

    MiLoop uses rollout-based RL to propagate and selectively update historical representations alongside current embeddings, enabling a shallow policy to reuse them across decisions without external labels or training-time pruning.

    Source: §1 · pp. 2–3, §5 · p. 10

  • Results

    Across four COPs and instances from 100 to 10 million nodes, MiLoop is reported to produce high-quality solutions with strong cross-size generalization.

    Source: §1 · p. 3, §5 · p. 10

  • Takeaways & Limitations

    MiLoop's rollout-based memory propagation supports a three-layer policy that learns dynamic embeddings without external solution labels or training-time search-space pruning.

    Source: §5 · p. 10

    Some instances were skipped because of an out-of-memory issue.

    Source: §4.1 · p. 8

Abstract

from arXiv · show

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.

1 INTRODUCTION

Constructive NCO reduces reliance on handcrafted rules, but dynamic-embedding methods can incur deep computation and depend on labels or search-space pruning. MiLoop uses rollout-based RL with selective memory propagation, and is reported to produce high-quality solutions across four COPs and scales from 100 to 10 million nodes.

1 INTRODUCTION

  • Constructive NCO learns heuristic rules from data and builds feasible solutions in a rollout, while many COPs remain computationally demanding and classical heuristics require handcrafted, problem-specific expertise.These needs are especially salient when domain expertise is unavailable or expensive to acquire.Source: §1 · p. 1
  • Dynamic embeddings can generalize to larger instances, but often rebuild representations at every step with deep attention stacks; high-performing methods may rely on labels, pseudo-labels, or aggressive training-time pruning.The passage notes that aggressive pruning may exclude actions needed for high-quality solutions.Source: §1 · p. 2
  • The paper asks whether the multi-step computation already required by RL rollouts can support selective memory propagation for a shallow policy learning effective dynamic embeddings.Historical information may vary in relevance across nodes, feature channels, and construction steps.Source: §1 · p. 2
  • MiLoop uses rollout-based RL to reuse representations across decisions with fewer attention layers than dynamic-embedding baselines, without external solution labels.It fuses current embeddings with memory before attention and applies adaptive gated updates afterward, supporting current decisions and subsequent reuse.Source: §1 · pp. 2–3
  • Across four COPs and instances from 100 to 10 million nodes, MiLoop is reported to produce high-quality solutions and show strong generalization.The evaluation spans the full stated size range.Source: §1 · p. 3

2 PRELIMINARIES

The preliminaries describe dynamic-embedding constructive solvers as repeatedly representing the current subproblem, then scoring feasible actions. They also frame autoregressive construction as a sequential decision process, which provides a basis for reusing representations across steps.

2.1 CONSTRUCTIVE NEURAL SOLVER WITH DYNAMIC EMBEDDINGS

  • Dynamic-embedding solvers represent the current subproblem, apply attention layers to node embeddings, and map the resulting representations to logits for feasible-node selection.The TSP example initializes node features, processes them through an attention stack, and scores candidate actions.Source: §2.1 · p. 3

2.2 AUTOREGRESSIVE CONSTRUCTION

  • Autoregressive construction selects actions from the feasible set based on the partial solution and constraint state, extending the solution until termination.Infeasible actions are masked from selection.Source: §2.2 · p. 3
  • Because autoregressive solvers recompute contextual representations rather than reuse them, their sequential decision process offers a basis for propagating memory across construction steps.MiLoop's overview shows memory fusion before attention and selective updating afterward for current scoring and cross-step reuse.Source: §2.2 · p. 4, Figure 2 · p. 4

3 METHODOLOGY

MiLoop carries node-wise memory through construction rollouts, fusing historical representations with current inputs before attention and adaptively updating memory afterward. Updated representations inform both action selection and subsequent steps, while trajectory-level preference training uses solution quality without externally labeled solutions.

3 METHODOLOGY

  • MiLoop fuses current inputs with historical node memory before attention, then reuses updated representations for action scoring and later construction steps.The method is described using TSP, with task-specific implementations for other evaluated COPs in Appendix B.Source: §3 · p. 4

3.1 STEPWISE MEMORY FUSION; 3.2 SELECTIVE MEMORY UPDATE

  • Memory fusion combines current inputs with retained context before attention, while adaptive, role-specific gates control how candidate representations revise each node’s memory.Larger gate values favor candidate representations; smaller values retain more historical information.Source: §3.2 · pp. 5–6

3.3 MEMORY-GUIDED ACTION SELECTION

  • Updated memory states contribute directly to current action selection and are carried forward by node identity for reuse in later construction steps.Scores are computed over the feasible action set.Source: §3.3 · p. 6

3.4 TRAINING

  • MiLoop’s reference-free DPO training compares two sampled complete solutions by objective value and jointly optimizes the policy through trajectory-level comparisons.The current policy generates new preference pairs during training; the paper also evaluates a REINFORCE-trained variant.Source: §3.4 · p. 6

4 EXPERIMENTS

Experiments compare MiLoop with classical and neural solvers across four combinatorial optimization problems, synthetic scales, and external benchmarks. They report cross-scale and cross-distribution performance, then examine memory propagation and ablate the model’s components.

4.2 PERFORMANCE EVALUATION

  • 11 of 12 KP settings and every tested TSP and CVRP setting favor MiLoop among neural baselines; MiLoop also achieves the smallest neural gaps across PDTSP scales.The TSP and CVRP tests span 100–10K nodes; the PDTSP tests span 100–1K nodes, and KP tests span 200–1K items.Source: Table 1 · p. 7, §4.2 · p. 8

4.1 EXPERIMENTAL SETUP

  • Tests cover synthetic TSP and CVRP sizes, larger PDTSP and KP instances, and four external benchmarks; training uses 100-node VRP and 200-item KP instances.For N > 1,000, inference limits the candidate set to 200 nodes per step, or 400 for CVRP; some instances are skipped due to OOM.Source: §4.1 · pp. 7–8

4.2 PERFORMANCE EVALUATION

  • 81 TSPLib and 110 CVRPLib instances are solved; MiLoop has the lowest reported average gaps across scale groups and the highest quality among comparable neural methods up to 10 million TSP nodes.The paper reports these results for a solver trained only on uniformly distributed 100-node instances.Source: Table 2 · p. 8, Table 3 · p. 8, §4.2 · p. 8

4.1 EXPERIMENTAL SETUP

  • Comparisons span classical solvers, static- and dynamic-embedding constructive NCO, and two-stage NCO methods.ICAM is retrained only on N = 100 instances without vary-scale training for a fair comparison.Source: §4 · p. 7, §4.1 · p. 8

4.3 DISCUSSION

  • MiLoop’s embeddings remain locally similar across adjacent construction steps but diverge from their first-step representations after multiple steps.The dynamic-embedding baseline has greater adjacent-step fluctuations while remaining relatively similar to its first-step representations.Source: Figure 3 · p. 9, §4.3 · p. 9

4.4 ABLATION STUDY

  • On TSP10K, MiLoop’s gap is 2.56% versus 4.39% for a six-layer no-memory model, with approximately half the inference time.Removing either memory component increases gaps across tested scales; increasing depth from three to six layers helps without memory, but still falls short of three-layer MiLoop. REINFORCE remains robust across scales, while DPO further improves overall results.Source: Table 5 · p. 9, §4.4 · p. 9

4.3 DISCUSSION

  • Unlike Rec-NCO’s two-stage supervised training, MiLoop learns its shallow policy and memory jointly through RL rollouts, using fusion and gated updates.The comparison evaluates full-RSE and fusion-only variants without gated updates to assess the roles of fusion and selective updates.Source: §4.3 · p. 9

5 CONCLUSION

MiLoop uses RL rollouts to propagate selected representations across solution-construction steps, reducing reliance on deep per-step recomputation. The paper reports high-quality solutions and cross-size generalization across four COPs, and situates the approach among static and dynamic embeddings and looped Transformers.

5 CONCLUSION

  • MiLoop reuses rollout computation for selective memory propagation, enabling a three-layer policy to learn dynamic embeddings without external solution labels or training-time search-space pruning.The method fuses current embeddings with historical memory before attention, then applies adaptive gated updates; future work will explore improved updates and multi-task learning.Source: §5 · p. 10

A.1 CONSTRUCTIVE NCO WITH STATIC EMBEDDINGS

  • Static embeddings are reused throughout construction but do not explicitly adapt to evolving subproblems, potentially limiting generalization.The related-work discussion traces this encoding paradigm from Pointer Networks to self-attention and later structural-bias and multi-task methods.Source: §A.1 · p. 16

A.2 CONSTRUCTIVE NCO WITH DYNAMIC EMBEDDINGS

  • Dynamic methods recompute embeddings at each step; RL approaches such as L2R and INViT encode reduced subproblems, excluding actions needed for high-quality solutions.Other dynamic methods rely on labels or pseudo-labels, with the latter requiring extra iterations to produce higher-quality training targets.Source: §A.2 · p. 16

A.3 LOOPED TRANSFORMER

  • Looped Transformers reuse shared blocks to refine representations and increase effective depth (Dehghani et al., 2018); MiLoop propagates selective memory across NCO construction steps.Related approaches include token-adaptive recursion, budget-conditioned depth, and memory propagation across sequence positions or segments.Source: §A.3 · p. 16

B IMPLEMENTATION DETAILS

MiLoop adapts its memory-fusion, selective-update, and action-selection pipeline to CVRP, PDTSP, and KP, with task-specific inputs and feasibility rules. Across these implementations, updated representations support current action scoring and are reused in later construction steps.

B.1.2 MILOOP FOR CVRP

  • CVRP uses capacity-conditioned inputs and action scoring while carrying depot, current-node, and candidate memories forward across construction steps.Customer demands are normalized by vehicle capacity; selecting a customer reduces remaining capacity, while selecting the depot resets it.Source: §B.1.2 · p. 17

B.2.2 MILOOP FOR PDTSP

  • PDTSP memory fusion incorporates each pickup’s paired delivery, while feasibility masks prevent delivery selection before its pickup.All unvisited nodes, including not-yet-feasible deliveries, participate in memory updates and can contribute to current representations.Source: §B.2.2 · pp. 18–19, §B.2.1 · p. 18

B.3.2 MILOOP FOR KP

  • KP represents each unselected item using its value and weight relative to remaining capacity, then scores only items that fit.Unselected items—including currently infeasible ones—participate in attention and memory updates; construction stops when none fits.Source: §B.3.2 · p. 20

B.4.1 OVERVIEW

  • AAFM replaces dot-product attention with featurewise aggregation using an instance-dependent pairwise bias, with keys and biases determining normalized weights and queries gating output.The aggregation does not compute QK^T.Source: §B.4.1 · pp. 20–21

B.4.2 AAFM FOR TSP

  • For TSP, AAFM uses a scale–distance bias over normalized coordinates that favors nearby nodes when its learnable coefficient is positive.The bias scale adapts to the remaining problem size through γ_t = max{1, log_100 |A_t|}.Source: §B.4.2 · p. 21

B.4.3 AAFM FOR CVRP

  • CVRP uses the scale–distance bias with γ_t = 1, while capacity feasibility is enforced by the final action mask.Its candidate set includes unvisited customers and an available depot-return action; demands enter node embeddings.Source: §B.4.3 · p. 21

B.4.4 AAFM FOR PDTSP

  • PDTSP uses the distance bias with γ_t = 1 during training and a remaining-size-dependent γ_t during inference, while masking actions to enforce pickup-before-delivery precedence.All unvisited nodes contribute to aggregation, including deliveries whose pickups remain unvisited.Source: §B.4.4 · p. 21

B.4.5 AAFM FOR KP

  • For KP, AAFM aggregates unselected items using their values and weights, with the bias favoring pairs of higher combined value per unit weight when α_ℓ is positive.Self-interactions and padded items are masked, and capacity feasibility is enforced during action selection.Source: §B.4.5 · p. 21

C EXPERIMENTAL SETUP

The experimental setup uses established synthetic-data protocols for TSP, CVRP, and PDTSP, and follows prior work’s training-size protocol for KP. The dataset and model/training settings are summarized in Tables 6 and 7.

C.1 PROBLEM AND HYPERPARAMETER SETTINGS

  • TSP, CVRP, and PDTSP use uniformly distributed training instances, while KP follows Kwon et al. (2020) for training size.The same trained model is used in all evaluations.Source: §C.1 · p. 21
  • Table 6 summarizes the test datasets and evaluation settings.Source: Table 6 · p. 22
  • Table 7 summarizes MiLoop’s model and training settings.Source: Table 7 · p. 22

C.2 PSEUDOCODE FOR TRAINING

The reference-free DPO procedure samples paired tours under the current MiLoop policy, orders them by cost, and updates the policy from their sequence log-probabilities. Memories and environments remain separate across paired trajectories, while gradients flow through action probabilities and memory updates.

C.2 PSEUDOCODE FOR TRAINING

  • Each batch samples two tours per instance, constructs them with separate environments and memories, and performs one optimizer update by default.When configured for multiple updates per collected pair, stored actions are replayed with reset environments and memories to recompute log-probabilities.Source: §C.2 · p. 23
  • The preference loss uses the lower-cost tour as preferred, with equal-cost pairs assigned according to the implementation’s tie rule.The loss uses a numerically stable log-sigmoid and no reference-policy likelihood or reward baseline.Source: §C.2 · p. 23
  • During each rollout, the algorithm fuses retrieved memories with current embeddings, computes updated memories, scores actions, and writes memories back by node identity.The computational graph through action log-probabilities and memory updates is retained when differentiating the loss.Source: §C.2 · p. 23

D EFFECTIVENESS OF MEMORY

On TSP100, MiLoop’s node representations show greater similarity between adjacent construction steps but lower similarity to their first recorded representations than the dynamic-embedding baseline. Tour examples also report lower gaps for MiLoop at TSP100 and TSP1000.

D EFFECTIVENESS OF MEMORY

  • The analysis centers node embeddings over nodes shared between adjacent steps before comparing each node’s representation with its previous-step and first-recorded versions.Adjacent-step similarity measures continuity in relative representations; first-step similarity tracks directional change over the rollout.Source: D EFFECTIVENESS OF MEMORY · p. 24
  • 0.9159 versus 0.8480 mean adjacent-step similarity favors MiLoop over the traditional dynamic-embedding baseline, a difference of 0.0679.The more uniform MiLoop pattern in Figure 4a is described as supporting smoother representation evolution across successive decisions.Source: Table 8 · p. 24, D EFFECTIVENESS OF MEMORY · p. 24, Figure 4 · p. 25
  • 0.4497 versus 0.7655 mean similarity to the first recorded step is lower for MiLoop than the baseline, a difference of 0.3158.The baseline remains broadly aligned with initial embeddings, while MiLoop departs early and stays less similar through much of construction.Source: Table 8 · p. 24, D EFFECTIVENESS OF MEMORY · p. 24, Figure 4 · p. 25
  • Across the comparisons, MiLoop combines stronger adjacent-step continuity with greater accumulated departure from initial representations, while the route examples show lower gaps at both scales.Source: D EFFECTIVENESS OF MEMORY · pp. 24, 26
  • 0.00% versus 9.73% gap on TSP100 and 1.62% versus 7.19% on TSP1000 are the reported MiLoop and baseline tour gaps.Figure 5 compares the two methods’ tours at both instance sizes.Source: Figure 5 · p. 26, D EFFECTIVENESS OF MEMORY · p. 26

E.1 RESULTS ON SYNTHETIC PDTSP AND KP

MiLoop generalizes across PDTSP and knapsack scales despite training on smaller instances, with greedy decoding already outperforming evaluated neural baselines in the reported settings.

E.1 RESULTS ON SYNTHETIC PDTSP AND KP

  • 1.74% and 2.40% PDTSP gaps with greedy decoding compare with URS’s 12.67% and 14.98%; multi-start decoding reaches −0.27% and −0.35% relative to LKH3.These results are for PDTSP500 and PDTSP1K, respectively; MiLoop is trained only on 100-node instances and uses the same model at evaluation sizes.Source: Table 9 · p. 27, §E.1 · p. 27
  • Heter-AM’s N = 100 results come from Ma et al. (2022), because a pretrained model of its official implementation was unavailable.Source: §E.1 · p. 27
  • MiLoop has the lowest neural-solver gaps in 11 of 12 knapsack settings, with KP1K gaps below 1% across capacities.At C = 10, its 0.851% gap compares with 1.923% for BQ and 29.005% for POMO; at C = 100, its gap is 0.013%. MiLoop takes 10–25 s on KP1K, compared with 1.9–4.4 min for BQ; POMO has the lowest gap at KP200, C = 25 (0.014% versus MiLoop’s 0.080%).Source: Table 10 · p. 27, §E.1 · p. 27

E.2 RESULTS ON TSPLIB AND CVRPLIB

The section reports per-instance comparisons on TSPLib and CVRPLib, using one model trained on uniformly distributed 100-node instances to examine scale and distribution generalization.

E.2 RESULTS ON TSPLIB AND CVRPLIB

  • Tables 11 and 12 report per-instance solution gaps for MiLoop under greedy and M = 100 multi-start decoding against constructive neural solvers with dynamic embeddings.The evaluation covers symmetric EUC 2D TSPLib and CVRPLib instances, including Set-X and Set-AGS, across a broad range of sizes and spatial distributions.Source: §E.2 · p. 28, Table 11 · pp. 28–29, Table 12 · pp. 30–31
  • MiLoop uses the same model trained on uniformly distributed 100-node instances across the evaluated problems, enabling comparisons across scales and data distributions.The comparisons also assess the benefit of multi-start decoding.Source: §E.2 · p. 28

F.1 VISUALIZATION ON SYNTHETIC DATASET

The visualizations compare solutions on synthetic TSP and CVRP instances and benchmark datasets; a separate table lists baseline-code and dataset license terms.

F.1 VISUALIZATION ON SYNTHETIC DATASET

  • Rows show TSP100, TSP1000, and TSP10000, while columns compare LKH3, MiLoop, L2R, and LEHD on shared instances using greedy decoding.Panels report tour lengths and gaps relative to LKH3; dashed lines show the LKH3 tour and stars mark the starting node.Source: Figure 6 · p. 32
  • Synthetic CVRP rows show CVRP100, CVRP1000, and CVRP10000, with HGS references alongside MiLoop, L2R, and LEHD solutions on the same instances.Panels report route lengths and gaps relative to HGS; dashed lines mark reference routes and stars mark depots.Source: Figure 7 · p. 33

F.2 VISUALIZATION ON BENCHMARK DATASET

  • Figure 8 visualizes greedy-decoded solutions on TSPLib and CVRPLib, ordered by increasing instance size within each column.Red lines indicate solution edges and black squares indicate CVRP depots; instance names, sizes, and gaps appear in subcaptions.Source: Figure 8 · p. 34

G LICENSES

  • Table 13 lists baseline-code and benchmark-dataset licenses and their stated usage terms.Source: Table 13 · p. 35

Related papers

Loading 2610.01685v1…