Memory-Enhanced Neural Solvers for Routing Problems

TL;DR

MEMENTO is a novel approach that equips neural routing solvers with a "memory" to learn from their own mistakes during inference. By dynamically adjusting its search strategy based on previous attempts—without relying on slow backpropagation—it achieves state-of-the-art results on Traveling Salesman and Vehicle Routing problems, scaling efficiently to instances with hundreds of nodes.

What Problem Does This Paper Address?

Routing problems, such as the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are fundamental to logistics and manufacturing. However, they are NP-hard, meaning finding the optimal solution becomes exponentially difficult as the number of locations increases.

While Reinforcement Learning (RL) has produced "neural solvers" capable of learning strong heuristics, these models often struggle with two key limitations:

1. Instance Adaptation: They are typically "one-shot" models that fail to adapt their strategy to the specific quirks of the single problem instance they are currently solving.
2. Budget Efficiency: Given a computational "budget" of 1,000 attempts to find the best route, most models simply sample 1,000 times independently. They do not leverage the information gathered from the first 500 attempts to inform and improve the next 500.

Existing solutions like Efficient Active Search (EAS) attempt to address this by fine-tuning the model's weights during inference. However, this requires backpropagation, which is computationally expensive and scales poorly to larger, real-world problems.

Methods

To overcome these limitations, the authors introduce MEMENTO (Memory-Enhanced Neural Solvers), a framework that integrates a lightweight memory and an auxiliary processing module into existing neural solvers.

Expand

Source, p. 4

• The Memory Module: As the solver makes repeated attempts (rollouts) on a problem, it stores transition data: which node it visited, the probability assigned to that action, the final route length (return), and the remaining "search budget."
• The Update Rule: Instead of using backpropagation to update the entire model, MEMENTO employs a small Multi-Layer Perceptron (MLP). When the solver evaluates a specific city, it retrieves past data associated with that city. The MLP processes this "experience" and outputs a correction that is added to the original model's predictions (logits).
• Budget Awareness: Crucially, the model is trained to track its remaining time. This allows it to naturally transition from exploration (trying new routes early on) to exploitation (focusing on the best-known paths as the budget depletes).
• Architecture Agnostic: MEMENTO acts as a plug-and-play enhancement for standard RL construction models like POMO or COMPASS.

Datasets

The researchers rigorously evaluated MEMENTO on:

• TSP and CVRP: The two gold-standard routing benchmarks.
• Standard Sizes: Training and testing on 100-node instances.
• Generalization Tasks: Testing on 125, 150, and 200 nodes to evaluate zero-shot generalization to larger problems.
• Large-Scale Instances: The authors successfully trained models on instances of size 500—a significant milestone for RL-based solvers—using efficient attention mechanisms to manage memory overhead.

Key Insights and Ideas

• Learning to Search: Rather than relying on a handcrafted search algorithm (like Beam Search), MEMENTO learns how to search by observing which past decisions led to shorter routes.
• The Asymmetric Rule: Analysis revealed that MEMENTO learns an update rule similar to the REINFORCE algorithm, but with an asymmetric twist: it strongly reinforces actions that are significantly better than the average, making it more robust than standard policy gradients.
• Zero-Shot Synergy: One of the most impressive findings is that a MEMENTO module trained on one base model (e.g., POMO) can be combined with a different, more advanced solver (e.g., COMPASS) in a "zero-shot" manner, yielding immediate improvements without additional training.
• Efficiency over Backprop: By avoiding backpropagation at inference time, MEMENTO scales significantly better than EAS. For 1,000-node problems, MEMENTO is roughly 20% faster while delivering superior results.

Key Results

Expand

Source, p. 1

• State-of-the-Art: MEMENTO achieved SOTA performance on 11 out of 12 evaluated tasks across TSP and CVRP.
• Massive Improvement: On TSP100, MEMENTO improved the base model's performance by 60% compared to simple stochastic sampling. In contrast, the previous leading method (EAS) only managed a 6% improvement.
• Scalability: As shown in the scaling curves, MEMENTO consistently outperforms EAS on large 500-node instances, particularly in "low budget" scenarios where every attempt counts. Its time complexity grows much slower than EAS as instance and decoder sizes increase.
• Data Efficiency: It requires far fewer attempts to reach high-quality solutions compared to existing fine-tuning methods.

Limitations and Future Work

• Computational Overhead: While significantly faster than backpropagation, MEMENTO still introduces a small amount of compute and memory overhead compared to a "memory-less" vanilla policy.
• Retrieval Strategy: The current iteration retrieves data based solely on the specific node visited. The authors suggest that utilizing more complex "similarity-based" retrieval (finding similar partial solutions) could further improve performance, albeit at a higher computational cost.
• Mathematical Refinement: The authors aim to eventually derive a purely mathematical update rule based on their empirical findings, which could potentially eliminate the need for the auxiliary MLP entirely.

@inproceedings{chalumeau2025memory,
  author = {Felix Chalumeau and Refiloe Shabe and Noah De Nicola and Arnu Pretorius and Thomas D Barrett and Nathan Grinsztajn},
  title = {{Memory-Enhanced Neural Solvers for Routing Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=p7WHZy8TCG},
}