Memory-Enhanced Neural Solvers for Routing Problems

We thank the reviewer for their constructive comments and insightful suggestions regarding formulation clarity, methodological comparisons, and applicability to broader settings.

> W1: Section 3.1 – Policy conditioning and formulation

We agree that this could be made clearer. While the base policy is auto-regressive (i.e., conditioned on prior actions within the same trajectory), the adaptation mechanism introduced by MEMENTO is conditioned on prior trajectories, that is, on data from previous solution attempts. These prior attempts are stored and retrieved from the memory, and used to correct the action logits at each step.

To reflect this more precisely, we will clarify that the policy is conditioned not only on the current state but also on the retrieved memory​, which encodes relevant prior experience for that state. The final logit used is the sum of base and memory-derived logits. This interaction will be made explicit in a revised paragraph and aligned with the formalism introduced in Section 3.

> W2: Comparison with REINFORCE – clarification of intent and purpose

MEMENTO’s learned rule does differ in intent: it aims to refine the action distribution online during inference, whereas REINFORCE is typically used for parameter updates via stochastic gradient ascent over full episodes.

Our Figure 4 illustrates how MEMENTO’s learned rule differs structurally from REINFORCE, especially in how it leverages return and log-prob information differently at various stages of the budget. We will add this nuance when discussing Figure 4. Nonetheless, the structural similarity remains instructive: MEMENTO reinforces high-return, low-probability actions and discourages low-return, high-probability ones, akin to the REINFORCE direction. This shows that MEMENTO rediscovered a REINFORCE-like mechanism, while optimizing for max-over-returns rather than average return.

We also thank the reviewer for pointing us to the work by Macfarlane et al. (NeurIPS Deep RL 2022). We will include this in our related work section as a notable exception that explores policy gradient updates for tree search strategies, and clarify how our approach differs by operating directly at inference and modifying logits without gradient flow.

> W3: Clarifying “budget” and abstract wording

We agree this is important. We will update the abstract to state: “MEMENTO adapts the action distribution over repeated attempts on the same problem instance, leveraging data collected online.” We will also define ‘budget’ explicitly as the number of solution attempts allowed per instance, consistent with the usage in RL-based combinatorial optimisation literature.

> W4: Suggested structure and placement of figures

We acknowledge the reviewer’s point and will revise the paper layout accordingly. Specifically:

• Figure 1 will be moved to Section 4, where it is better aligned with the experimental results to avoid flow of the introduction.
• Remove forward references from Section 2 (e.g., Fig. 4).
• Clarify in the caption of Figure 1 (left) that “Number of times ranked best” is computed by comparing methods across 12 benchmark tasks under different evaluation budgets.

These changes should improve the structure and clarity of the presentation.

> Q1: Using richer representations of state (e.g., partial solution embeddings) instead of just nodes.

Yes, as discussed in Appendix I, we experimented with retrieving based on partial solution embeddings, for example, decoder attention outputs. This approach is theoretically attractive but proved prohibitively costly in practice, especially in batched inference settings. In contrast, retrieving data by node (i.e., which city or customer is currently being visited) yielded similarly relevant information at far lower cost. We find this strategy to be a strong proxy for local similarity. We will expand this discussion slightly in the main text and clarify the rationale.

> Q2: Why is the remaining budget used as an input feature to the MLP? Could other features like “best return so far” be helpful?

We find that the remaining budget is a strong signal for shaping the exploration–exploitation trade-off. As shown in Fig. 8, this allows MEMENTO to explore early and gradually refine later, an emergent behavior aligned with human intuition and meta-RL literature.

We did not consider “best return so far” because we believe that the normalisation we apply to the input values achieve a similar effect as giving access to the best return so far: it compares the return to the typical return obtained, through the mean and standard deviation of the returns, and can hence get a sense of the advantage over the other returns. We agree that comparing with the best return instead could be beneficial, although potentially more prone to instabilities. All in all, it is a direction worth exploring further.

> Q3: Generalization to other routing and non-routing problems

We agree that broader applicability is important. MEMENTO is fully compatible with other CO problems, including non-routing tasks. Its architecture-agnostic design, relying only on access to logits makes it broadly applicable. The only change required for a new domain (e.g., JSSP) is to adapt the retrieval index (e.g., by job or machine id instead of node id).

We chose TSP and CVRP to align with standard benchmarks and focus on pushing scale (n = 500) rather than breadth. We are the first to train RL solvers at this scale for both problems and to release the resulting checkpoints. As mentioned in our conclusion, we view applications to other domains (e.g., scheduling, packing) as a promising avenue for future work, and we are happy to include additional discussion in the final version.

We thank the reviewer for their thoughtful feedback highlighting both the strengths and areas for improvement in our work, and the opportunity to clarify design choices of our approach. Below, we address each concern.

> W1: Performance gain of MEMENTO over EAS

We understand the concern and agree that performance improvements must justify the added modeling effort. MEMENTO introduces a memory-based module, but this added complexity brings capabilities that static fine-tuning approaches like EAS cannot offer.

In particular, MEMENTO:

• Conditions on remaining budget, allowing it to shift behavior over time (e.g., explore early, refine later), unlike fixed-update methods.
• Operates without backpropagation at inference, making it significantly faster and more scalable in large-instance or large-model settings (Fig. 7).
• Can be used zero-shot with new base policies like COMPASS, highlighting its modularity, a generality not afforded by EAS.

These advantages are reflected empirically. On standard benchmarks (Table 1), MEMENTO consistently outperforms EAS across all 8 tasks. On large-scale tasks (n=500), it achieves state-of-the-art single-agent results. Moreover, Fig. 6 shows MEMENTO maintains its advantage even in low-budget or few-shot settings, where EAS fails to improve over the base.

While performance is one dimension, we believe MEMENTO’s broader modeling capacity and scalability make it a more robust and versatile tool for inference-time adaptation in neural combinatorial optimization.

> W2: Evaluation across a wide range of computational budgets

Indeed, MEMENTO was trained with an explicit goal to shift behavior over time, using the remaining budget as input. Figure 8 (Appendix G) is a training curve that illustrates this shift: early in the budget, MEMENTO promotes broader exploration; later, it focuses on exploiting promising trajectories. This is also reflected in the learned update rule (Figure 4), which shows asymmetry with respect to advantage: only actions with strictly positive normalized return are reinforced.

Additionally, we report performance across a wide range of sequential attempt budgets (e.g., 200 to 1200 shots) and batched settings (20–80) in Figure 6. In those plots, we observe that MEMENTO learns a strategy that performs moderately at first and progressively improves as the budget grows, contrasting with methods like EAS that optimize for single-shot performance and plateau earlier.

We will make this budget-sensitivity aspect more prominent in the main paper.

> W3: Clarification of Figure 4

We thank the reviewer for the interest in the learned update rule. Figure 4 was created by averaging the MLP’s logit correction output across 10,000 transitions, conditioning on two inputs: the normalized return and the log-probability of the action. All other features were fixed at their mean value. This allows us to isolate the learned update pattern across return-logprob space, similarly to what was done in Fig. 3 of the EAS paper. We will clarify this process in the caption and text.

> W4: Interpretability of the learned update rule

While the MLP operates as a black box, we have conducted a structured analysis of its outputs that reveals interpretable behavior.

Specifically, we compute the MLP’s logit correction values over a grid of inputs by varying normalized return and log-probability, while fixing all other inputs at their mean (see Figure 4). This reveals that MEMENTO strongly upweights low-probability, high-return actions, a pattern that aligns with a form of advantage-weighted reinforcement, but with a sharper focus on exploitation.

Beyond this static view, we have also examined how the learned updates change over the course of the budget. When conditioning on remaining budget (low, mid vs. high), we observe a shift in the MLP’s response: early on, the MLP tends to assign nonzero weights even to uncertain or suboptimal transitions, supporting broad exploration; later, it sharply concentrates weights around high-return, high-confidence actions. We thank the reviewer for the additional analysis they suggested, we will add these dynamic response plots to the appendix and clarify the mechanisms behind this progression.

This progression is not hardcoded, it emerges from training and supports the idea that MEMENTO learns to adaptively balance exploration and exploitation through its memory module.

We sincerely thank the reviewer for raising these thoughtful points, especially concerning memory design and practical efficiency.

> W1 & Q1: Memory content and retrieval strategy

We fully agree that alternative memory retrieval strategies are worth exploring. As discussed in Appendix I, we did consider using partial solution embeddings (e.g., from the decoder’s attention module) and k-nearest neighbor (k-NN) retrieval in that latent space. However, even when using approximate nearest neighbor search in JAX, this strategy incurred significantly higher compute and memory cost during inference, especially under batching. Surprisingly, we observed that retrieving from the same node as the current state consistently returned highly relevant transitions, serving as a strong proxy for similarity. Hence, the node-based retrieval strategy offered the best trade-off between relevance and computational efficiency.

That said, MEMENTO’s framework is modular. We encourage future work or domain-specific applications to instantiate richer retrieval mechanisms when appropriate. We will add a short discussion and a pointer to Appendix I in the main paper to make this design choice more explicit.

> W2 & Q2: Computational overhead of memory and scaling with problem size (N) and attempts (K).

We appreciate this suggestion of how we can present a more quantitative analysis of the computational overhead. In summary, MEMENTO’s overhead scales linearly with the number of memory entries retrieved per action (typically 40) and is independent of the base model architecture.

For example, on CVRP100 with 100 nodes and 1600 attempts, the full memory size is ≈8MB (40 entries × 100 nodes × 5 float32 values × 100 starting points). The time to compute logit corrections via the MLP remains a small fraction of inference time for most architectures. For larger architectures (e.g., 10-layer decoders), MEMENTO becomes faster than EAS due to the latter’s backpropagation cost (see Fig. 7, Appendix A.4).

We agree that adding an explicit table showing inference time broken into solver time and memory overhead across {100, 200, 500}-node instances and several K values will improve the experimental transparency. Therefore, we will include this table in the updated appendix.

> W3: Limitations of “zero-shot” combination with diversity-based solvers

We agree that while MEMENTO can be combined with COMPASS or other diversity-based solvers in a zero-shot manner, it may not be optimal in all regimes. For example, if the best pre-trained policy found by COMPASS differs structurally from the one MEMENTO was trained with, the effectiveness of the logit updates may decrease.

To mitigate this, we activated MEMENTO only after COMPASS’s CMA-ES search had mostly converged, as discussed in Appendix I and Section 4.2. This yielded consistent improvements across all CVRP tasks (Table 2). We agree that an integrated design (e.g., co-training or fine-tuning MEMENTO on the COMPASS policy family) could further improve results, and we will mention this promising direction for future work in the conclusion.

We thank the reviewer for their detailed and thoughtful feedback.

> W1–W2: Clarity of the Method Section and Figures

We appreciate the reviewer’s emphasis on clarity and fully agree that the method section (Lines 129–195) should be more accessible and self-contained. We will revise this section to improve the logical flow of the presentation, reduce forward references (e.g., to Fig. 4, discussing zero-shot combination before introducing the method fully, etc), and provide a clearer step-by-step explanation of the inference-time adaptation process.

While we initially placed Algorithm 1 in the appendix to manage space constraints, we understand the value of a concrete procedural description in the main text. Instead of moving the full pseudo-code into the main body, we plan to integrate its structure more directly into the revised Section 3 by aligning the narrative with its logic, i.e. using it as an implicit scaffold while keeping the main text compact. This allows us to retain the balance between conceptual clarity and narrative flow.

Regarding Figure 3, we respectfully believe that it provides critical insight into the learned behavior of our approach, distinguishing it from baseline methods. It is the only figure in the paper that explicitly visualizes the logit update rule learned by MEMENTO’s memory module, and shows how it varies with return, log-probability, and budget. We have received positive feedback on this aspect from other reviewers as this level of interpretability is rarely available in adaptive NCO methods literature. We therefore prefer to retain it in the main body, though we are open to simplifying its caption or reordering the section to reduce any perceived disruption. We thank the reviewer again for highlighting areas of improvement, and will ensure the revised draft foregrounds the method more clearly, with minimized indirection.

> Q1: Generalisation to non-routing CO Problems

MEMENTO’s design is not tied to routing problems. The mechanism of storing transition-level data and applying logit corrections via memory is agnostic to the CO domain. As long as the base policy produces logits over discrete actions and the solution can be constructed incrementally, our memory-based logit correction can be applied without modification. For example, in the case of JSSP or knapsack-type problems, the retrieval strategy would need to change (e.g., grouping memory by machine or item id), but the memory processing and update logic remain the same. We provide this example of how the retrieval strategy can be adapted in Appendix I. We are currently investigating such extensions and will outline them in our conclusion.

> Q2: Clarification on the term “Node”

Thank you for pointing out this ambiguity. In the context of routing problems like TSP and CVRP, a “node” refers to a city or customer location, i.e., a decision variable in the CO instance. More generally, it is the element selected by the action at each step. We will explicitly state this early in Section 3 to avoid any confusion and ensure consistency throughout the manuscript.

> Q3: Interaction between base policy and memory module

As described in Section 3.2 and illustrated in Figure 2, the base policy first outputs action logits from the neural decoder, as usual. In parallel, the memory module retrieves transition-level data from previous trajectories (grouped by current node) and uses an MLP to compute correction logits. These corrections are added to the base logits to yield the final logits used to sample the next action. No gradient flows into the base policy at inference, and the memory module operates independently making this process lightweight. We will make this interaction clearer in the updated method section, in particular aligning Figure 2 more closely with Algorithm 1.