Track manipulation, locomotion and embodied systems.
Search papers, labs, and topics across Lattice.
MiLoop introduces a novel constructive neural combinatorial optimization framework that addresses the computational inefficiency of rebuilding subproblem representations from scratch at each step by selectively propagating memory across rollout steps. This approach enables a shallow policy to learn effective dynamic embeddings using purely reinforcement learning signals, eliminating the need for solution labels or aggressive search space pruning. Experimental results demonstrate MiLoop's ability to generate high-quality solutions for combinatorial optimization problems with up to 10 million nodes, showcasing its robust generalization capabilities.
LLMs can learn effective dynamic embeddings for massive combinatorial optimization problems with a shallow policy by selectively propagating memory across rollout steps, bypassing the need for expensive full recomputation or external labels.
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.