MiLoop: Selective Memory Propagation for Neural Combinatorial Optimization
MiLoop addresses a key inefficiency in constructive neural combinatorial optimization: dynamic-embedding methods typically rebuild subproblem representations from scratch at each step with deep attention stacks, and often depend on external solution labels or aggressive training-time pruning. The paper proposes Memory-in-the-Loop (MiLoop), an autoregressive framework that propagates a global node-wise memory matrix across construction steps, fusing current inputs with historical context before shallow attention layers and updating memory selectively via adaptive gates. By leveraging the multi-step rollouts already required for RL, MiLoop enables a three-layer policy to learn effective dynamic embeddings without external labels. Strong results on four COPs from 100 to 10 million nodes demonstrate both high solution quality and cross-scale generalization.
MiLoop is a well-motivated and empirically strong contribution. Its central idea—turning construction rollouts into a selective memory loop—is conceptually elegant and backed by extensive scaling experiments across four COPs. The ablation studies robustly isolate the value of the proposed fusion and gating mechanisms compared to both static baselines and naive recurrence. That said, the paper makes no theoretical claims about why or when memory propagation converges to useful representations, and the framing of its training objective as "reference-free DPO" conflates a pairwise rollout-ranking loss with the standard DPO framework that relies on a reference policy and KL constraint.
The strongest aspect of MiLoop is its clear architectural decomposition, validated by ablations showing that removing either memory fusion or gated updates degrades performance across all scales. The model achieves impressive out-of-domain generalization, outperforming prior neural methods on benchmark libraries and scaling gracefully to instances with up to 10 million nodes while remaining purely autoregressive. The comparison with Rec-NCO is particularly helpful: Table 4 shows that MiLoop’s specific pre-attention fusion and post-attention gating matter beyond generic recurrent state reuse, and the use of only three attention layers highlights genuine computational efficiency rather than simply trading depth for width.
Despite its strengths, several issues temper the claims. First, the paper criticizes prior RL-based dynamic-embedding methods for relying on "aggressive search space pruning during reinforcement learning," yet MiLoop itself depends on inference-time candidate-set pruning to 200 nodes (400 for CVRP) for all instances with $N>1{,}000$ (Section 4.1); while this is a training-versus-inference distinction, the ability to report results on 10-million-node instances is enabled by this heuristic pruning rather than by memory propagation alone. Second, the training objective, described as a "reference-free variant" of DPO, drops the reference-policy ratio central to standard DPO theory; it amounts to a pairwise logistic loss over self-sampled rollouts, which is reasonable but not rigorously grounded as RL in the policy-gradient sense. Third, the paper never analyzes the memory footprint of the global $M_t(\mathcal{G}) \in \mathbb{R}^{N \times d}$ matrix: at $N=10^7$ and $d=128$, storing a single instance’s memory in float32 requires over 5 GB of GPU memory, which severely limits batching and practical deployment even if per-step attention is shallow.
The experimental evidence broadly supports the paper’s empirical claims. MiLoop outperforms prior RL-based dynamic-embedding methods such as L2R on large-scale routing problems and surpasses static-embedding baselines on cross-distribution benchmarks (Tables 1 and 2). The comparison to Rec-NCO in Table 4 is especially illuminating, isolating the benefit of selective updates over generic recurrent inputs. However, comparisons are imperfect: some baselines (ICAM, Omni-VRP, ELG) are either retrained under restricted conditions or suffer out-of-memory errors, and classical solvers such as LKH3 and HGS still dominate on smaller instances where they can be run to completion. The paper is generally transparent about these caveats, but the headline claim of handling up to 10 million nodes should be read with the caveat that inference-time nearest-neighbor pruning is doing significant heavy lifting.
The paper provides detailed architectural equations and hyperparameters—model depth, embedding dimension $d=128$, learning rate schedule, and per-problem batch sizes—which aids replication. However, no code release, training scripts, or data generation seeds are mentioned, which represents a significant barrier to independently reproducing the 10-million-node results. Moreover, the exact criterion for selecting the 200-node candidate set at inference time is only cited to external works ([Chen et al., 2025]; [Zhou et al., 2026b]) rather than fully specified in the paper, and the "reference-free DPO" loss, while concise in Eq. 10, lacks discussion of how the preference scaling $\beta=0.1$ was chosen or how sampling variance across rollouts affects gradient variance.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.