Memory-Enhanced Neural Solvers for Routing Problems

arXiv:2406.16424 · cs.AI, cs.LG · Submitted 2026-08-24 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Memory-Enhanced Neural Solvers for Routing Problems".

Jane: The paper was written by Felix Chalumeau, Refiloe Shabe and Noah De Nicola from University of Cape Town and InstaDeep.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Paper discussion segment 2: Tom: Now that we know the concept, let's talk about what MEMENTO actually *is*—it’s not just memory in general, but a specific way of using it. The authors explain that MEMENTO allows the AI to look at its history when making a decision on any given step in the route.

Jane: It’s like if you are trying to decide where to go next, and instead of just looking at where you are right now, you check a notebook of past journeys that had similar turns.

Lu: The paper describes this process as dynamic adjustment based on online data, which is a huge step up from static pre-training. It’s essentially saying: "Based on what we have done so far, how should I adjust my next move?"

Meng: In practice, that means the AI isn't just guessing; it’s making an informed decision by integrating its past performance into its current choice. That adds a layer of reliability to real-world deployment.

Lalam: It’s a beautiful form of self-correction, Lalam feels, where the system is constantly learning from its own mistakes in the way it navigates the problem space.

Tom: The mechanism is quite clever because you aren't just recalling random facts; you are retrieving specific patterns that occurred when similar features were present.

Jane: And I think the summary highlights that this isn's just keyword matching, but a sophisticated recognition of patterns based on features collected at that moment in time.

Lu: Once those relevant patterns are pulled from memory, they aren't just shown as raw data; they are processed through a Multi-Layer Perceptron—a small neural network—that acts as the logic to make the decision.

Meng: That’s right, taking historical context and converting it into actionable guidance is what makes this feasible for industry because we can see exactly how that past knowledge translates into current action.

Lalam: It's a powerful abstraction layer, suggesting that based on everything the AI has seen before in situations like this, it can boost one path and slightly discourage another.

Paper discussion segment 3: Tom: We have a great handle on how MEMENTO works, but now we need to discuss the actual improvements. The authors show that MEMENTO is much better than the methods that came before it, especially those relying on standard policy gradient updates.

Jane: The key difference is that MEMENTO doesn't just use the old data; it learns a dynamic update rule from that data. It's like learning how to weight your decisions based on past results, rather than just relying on hope that the initial training was sufficient.

Lu: It’s not a simple policy gradient update, which is what many methods use; MEMENTO learns a flexible function that allows the AI to calculate how much it should change its mind about the next best action based on specific evidence.

Meng: And I think this addresses a huge practical issue: since we are dealing with messy, real-world problems that aren't perfectly represented in our training data, this ability to adapt makes MEMENTO far more robust for production use than static models.

Lalam: It’s about moving away from the idea of an AI that has a fixed "brain" and toward one where it can dynamically refine its intelligence based on how it performs in real-world scenarios.

Tom: The data retrieval and processing steps are absolutely crucial to understanding this improvement, as they are the core to MEMENTO's design.

Jane: The system pulls relevant past attempts from memory based on where we are now, which is a very targeted search for specific patterns that occurred before this exact point in the route.

Lu: It then processes this retrieved information through an MLP to generate "correction logits," which are essentially a calculated boost or drag on the current actions—a mathematical way of weighting the options available to us.

Meng: I see they also use the remaining budget as part of those features, allowing MEMENTO to change its strategy based on how much time is left in the task at that exact moment.

Lalam: It’s like having a memory that not only remembers what happened but also knows exactly how much time is left to make an informed choice about future success.

Paper discussion segment 4: Tom: The results are impressive, showing real strength when MEMENTO faces large, complex datasets. The authors tested it on instances with up to five hundred nodes for both the Traveling Salesman and the Vehicle Routing problems.

Jane: And a huge part of the story is that MEMENTO consistently outperformed other methods like Efficient Active Search, even when facing problems that looked totally different from its training data.

Lu: We’ve seen the performance on massive instances—up to five hundred nodes—and the results are incredibly competitive with traditional solvers and are often state-of-the-art.

Meng: The fact that MEMENTO achieves state-of-the-art performance on large instances is a massive practical win for my industry, as running these complex simulations is often constrained by time and budget.

Lalam: This capability of scaling up suggests that the AI isn't just for small test cases but has the potential to support global logistics operations across an entire continent or even a world scale.

Tom: We also saw this amazing zero-shot combination, where MEMENTO was applied without any extra training to a pre-trained model called COMPASS.

Jane: That means we can use the existing knowledge of other AI models and give them Memento's adaptive brain without having to retrain them entirely, which is a massive efficiency gain for the whole system.

Lu: The performance metrics are fantastic; Table one clearly shows that MEMENTO outperforms policy gradient methods by significant margins across different instance sizes.

Meng: And since it handles these large batches efficiently, I think it has a viable path for deployment in real-time systems, which is critical for large-scale operations.

Lalam: It’s not just about getting a better score; it’s about achieving a more reliable and scalable system that benefits everyone involved in logistics.

Conclusion: Tom: So, after all this discussion, it seems clear that MEMENTO is doing something genuinely transformative in how we approach complex logistics problems.

Jane: It's a shift from simply training an AI model to give it the ability to learn and evolve based on its own real-world experiences while solving tasks like the Traveling Salesman problem.

Lu: I see this as a fundamental leap, moving away from static solutions towards building solvers that can adapt, which is necessary for tackling global challenges in routing.

Meng: The fact that MEMENTO scales to handle these huge instances without needing constant retraining is a massive practical win for my industry right now.

Lalam: It suggests that AI isn't just a tool we use, but a system that can grow and improve over time, which is exactly the kind of intelligence we need.

Tom: That’s an incredibly optimistic view, Lalam; I think the practical application of this technology is what makes it so exciting to hear about.

Jane: It’s certainly not just a theoretical improvement; MEMENTO' robust performance in both training and out-of-distribution tests prove its real-world potential.

Lu: We have seen how it handles the "out-of-distribution" data, which is a huge indicator that it can handle messy or unexpected problems we haven't seen before.

Meng: And since efficiency is key, MEMENTO’s time complexity makes it suitable for production environments where budget constraints are always tight.

Lalam: This whole concept of dynamic learning helps us think about how AI can better support human decision-making in complex supply chains across various industries.

Tom: We've got a lot to wrap up with this paper, "Memory-Enhanced Neural Solvers for Routing Problems." It’s truly an impressive piece of work that opens up so many new possibilities.

Lu: I think it's worth seeing what further research is possible, especially regarding combining these self-improving methods.

Meng: I am ready to see how this technology translates into real-world deployment in commercial systems.

Lalam: A more adaptive and efficient future, that's what I hope we are moving towards with these kinds breakthroughs.

Felix Chalumeau, Refiloe Shabe, Noah De Nicola

University of Cape Town · InstaDeep

cs.AI, cs.LG

Submitted: 2026-08-24

Updated: 2026-08-25

Code: https://github.com/instadeepai/memento

Importance score: 85/100

The gist: Combinatorial Optimization (CO) problems, which encompass applications ranging from logistics to energy management, are typically NP-hard with a solution space that grows exponentially with problem

Key concepts

MEMENTO: The core mechanism allows the AI to look at its history when making a routing decision. Instead of just looking at the current location, it retrieves specific patterns from memory based on features present at that moment. This is a sophisticated recognition of patterns, not just keyword matching.
Dynamic Adjustment: This process moves beyond static pre-training. MEMENTO learns a dynamic update rule from past data, allowing the AI to calculate how much it should change its mind about the next best action based on specific evidence. It integrates past performance into current choices for reliability.
Out-of-Distribution Performance: This refers to MEMENTO's ability to perform well on large, complex datasets that look different from its original training data. Its robust performance allows it to handle messy or unexpected real-world problems, making it highly practical for scalable logistics.

Terminology

Adaptation — 23× in this paper · explained in 1 episode
Benchmark — 23× in this paper · explained in 2 episodes
Combinatorial Optimization — 20× in this paper · explained in 2 episodes
Reinforcement Learning — 15× in this paper · explained in 4 episodes
Fine-Tuning — 12× in this paper · explained in 5 episodes
Generalization — 12× in this paper · explained in 13 episodes
Ablation — 7× in this paper · explained in 1 episode
Ablation study — 6× in this paper · explained in 1 episode
Efficient Active Search — 4× in this paper
Capacitated Vehicle Routing Problem — 3× in this paper
Reinforcement Learning (RL) — 3× in this paper · explained in 25 episodes
Benchmarking — 2× in this paper · explained in 3 episodes
Core — 2× in this paper · explained in 2 episodes
Deep Reinforcement Learning — 2× in this paper · explained in 2 episodes
Latent Space — 2× in this paper · explained in 7 episodes
Monte Carlo Tree Search — 2× in this paper
Online Adaptation — 2× in this paper · explained in 3 episodes
Traveling Salesman Problem — 2× in this paper
While Reinforcement Learning — 2× in this paper
Abstraction — 1× in this paper · explained in 1 episode
Aggregation — 1× in this paper · explained in 1 episode
Computational overhead — 1× in this paper · explained in 2 episodes
Credit assignment — 1× in this paper · explained in 3 episodes
Distribution Shift — 1× in this paper · explained in 6 episodes
Loss Function — 1× in this paper · explained in 2 episodes
Markov Decision Process — 1× in this paper
Markov Decision Process (MDP) — 1× in this paper · explained in 11 episodes
Meta-learning — 1× in this paper · explained in 2 episodes
Parameter-Efficient Fine-Tuning — 1× in this paper · explained in 2 episodes
Regret — 1× in this paper · explained in 3 episodes
Reward Function — 1× in this paper · explained in 2 episodes
Robustness — 1× in this paper · explained in 5 episodes
Scaling Laws — 1× in this paper · explained in 4 episodes
Transformer — 1× in this paper · explained in 2 episodes
Transformer Architecture — 1× in this paper · explained in 2 episodes

Summary

Combinatorial Optimization (CO) problems, which encompass applications ranging from logistics to energy management, are typically NP-hard with a solution space that grows exponentially with problem size, making traditional optimal solutions intractable. Consequently, industrial solvers rely on sophisticated heuristic approaches and Reinforcement Learning (RL). While RL offers a versatile framework for learning these heuristics, the paper identifies that existing learned methods lack the ability to adapt to specific instances and fully leverage the available computational budget. Current approaches either rely on pre-trained policies or require RL fine-tuning, failing to utilize newly available information within constraints.

In response, the authors introduce MEMENTO, an approach that leverages memory to improve the search of neural solvers at inference. MEMENTO’s core function is to use online data collected across repeated attempts to dynamically adjust the action distribution based on previous decisions.

MEMENTO Methodology

The implementation of MEMENTO involves a memory module that stores information about past attempts. For each transition experienced while constructing a solution, the memory stores several crucial pieces of information: "(i) node visited (i.e., current city or customer location), (ii) action taken, corresponding to the node that the policy decided to visit next, (iii) log-probability given to that action by the model, (iv) return of the entire trajectory (negative cost of the solution built), and (v) budget at the time that solution was built."

When making a decision in a given state, MEMENTO retrieves relevant data from this memory. This retrieved data is then processed by a Multilayer Perceptron (MLP) to derive correction logits for each possible action. The resulting policy' update is achieved by summing these new correction logits with the original base model logits: logits final = logits base + logits M.

The authors detail a training procedure designed for multi-shot optimization, where the goal is to find a policy that maximizes the maximum return over B attempts: pi* = pi E tau about pi [i=1,,B R(tau i)]. The loss function used for updating the policy is derived from REINFORCE: L = - sum i=1 B (1 + epsilon + i) R̃(tau i) t pi M (a t s t).

Key Contributions and Performance

The paper highlights several major contributions:

Introducing MEMENTO: A memory and processing module enabling efficient adaptation of policies at inference time.
Empirical Superiority: MEMENTO outperforms policy-gradient methods like Efficient Active Search (EAS) and tree-search methods, achieving state-of-the-art (SOTA) on 11 out of 12 tasks across various benchmarks.
Training Capability: The authors successfully trained RL auto-regressive solvers on large instances (size 500), outperforming all existing RL methods.
Zero-Shot Combination: MEMENTO can be combined with diverse pre-trained policies, such as COMPASS, without additional retraining, achieving new SOTA on 11 out of 12 tasks.

Scaling and Complexity Analysis

The authors demonstrate that MEMENTO’s adaptation mechanism scales favorably compared to EAS. For an instance size of 1000, MEMENTO becomes 20% faster than EAS. The memory footprint scales linearly with the instance size, but remains independent of the base policy size. Regarding computational cost, the primary overhead is processing retrieved entries through the MLP, which does not depend on the instance size or the policy’s parameter count.

Conclusion

The authors conclude that MEMENTO provides a robust and efficient solution to improve adaptation of neural CO solvers to unseen instances. It proves superior performance over stochastic sampling, tree search, and policy-gradient fine-tuning, while maintaining favorable time performance scalability.

Improvements for AI systems

As an expert researcher, I have analyzed the paper Memory-Enhanced Neural Solvers for Routing Problems (MEMENTO). This work presents a highly specific and generalizable framework for improving sequential decision-making systems operating under computational budget constraints.

The following improvements are derived directly from MEMENTO's core mechanism, moving beyond the scope of combinatorial optimization (CO) to enhance various AI systems that require dynamic, adaptive decision-making.

This improvement involves replacing static or purely gradient-based policy updates with a dynamic, memory-augmented approach applied directly at inference time.

Specific Implementation:

Dynamic Logit Correction Module: Introduce an auxiliary processing module (MLP) that operates at inference time rather than during training. This module takes retrieved past experience data and calculates a corrective weight (l M) for every possible action in the current state.
Augmented Action Distribution: The final action distribution is determined by summing the original base policy logits (l) and the learned correction logits (l M). This creates an immediate, dynamic adjustment to the probability of selecting each action based on historical success/failure in l + MLP(Retrieved Memory).
Memory Structure: The memory must store comprehensive transition data: (a) the current node/state, (b) the action taken, (c) its log-probability, (d) the total return of the trajectory, and critically, (e) the remaining computational budget.

What this Improved AI System Can Do:

Adaptive Search: The system can dynamically adjust its exploration/exploitation trade-off based on real-world performance. It prioritizes actions that have historically yielded high returns under similar conditions but low initial probability, rather than relying solely on the base model's inherent biases.
Zero-Shot Adaptation: The system can be successfully deployed onto pre-trained, memory-less models (e.g, large language models or standard RL agents) without requiring any additional retraining or fine-tuning for specific problem instances.

This improvement specifically leverages the remaining computational budget as a critical input feature for policy adjustment.

The MEMENTO framework can be applied to any sequential decision-making problem that requires an adaptive response to past experience.

Specific Applications and Capabilities:

Large Language Models (LLMs) for Planning: An LLM used for complex, multi-step planning (e.g., software deployment or scientific hypothesis generation) could be augmented with MEMENTO memory. It would store past successful/failed reasoning chains, and when faced with a new state, dynamically adjust the probability of choosing certain reasoning paths based on historical success rates under similar contextual constraints.
Autonomous Agents in Dynamic Environments: In autonomous robotics or drone navigation (e.g., pathfinding around unexpected obstacles), MEMENTO would store past successful maneuvers and associated environmental conditions (memory). When a new obstacle is encountered, it dynamically adjusts its action distribution to favor previously successful evasive actions under similar circumstances, rather than defaulting to a static, learned policy.

3 Complex Resource Scheduling: For dynamic scheduling problems (like job-shop scheduling), MEMENTO would store past task sequences and their associated delays/success rates. When assigning the next task, it dynamically prioritizes tasks that historically performed well in those specific resource states, even if the base policy currently suggests a different choice.