Memory-Enhanced Neural Solvers for Routing Problems
Authors: Felix Chalumeau
Refiloe Shabe
Noah De Nicola
Arnu Pretorius
Thomas D Barrett
Nathan Grinsztajn
Venue: NeurIPS 2025 spotlight ()
Keywords: reinforcement learning
combinatorial optimisation
routing
memory
Primary area: reinforcement_learning
TL;DR: MEMENTO improves neural routing solvers by using memory to adapt decisions at inference time, outperforming fine-tuning and search methods while pushing SOTA on 11 of 12 tasks.

Abstract: Routing Problems are central to many real-world applications, yet remain challenging due to their (NP-)hard nature. Amongst existing approaches, heuristics often offer the best trade-off between quality and scalability, making them suitable for industrial use. While Reinforcement Learning (RL) offers a flexible framework for designing heuristics, its adoption over handcrafted heuristics remains incomplete. Existing learned methods still lack the ability to adapt to specific instances and fully leverage the available computational budget. Current best methods either rely on a collection of pre-trained policies, or on RL fine-tuning; hence failing to fully utilize newly available information within the constraints of the budget. In response, we present MEMENTO, an approach that leverages memory to improve the search of neural solvers at inference. MEMENTO updates the action distribution dynamically based on the outcome of previous decisions. We validate its effectiveness on Traveling Salesman and Capacitated Vehicle Routing problems, demonstrating its superiority over tree-search and policy-gradient fine-tuning; and showing that it can be zero-shot combined with diversity-based solvers. We successfully train all RL auto-regressive solvers on large instances, and verify MEMENTO's scalability and data-efficiency: pushing the state-of-the-art on 11 out of 12 evaluated tasks.

Memory-Enhanced Neural Solvers for Routing Problems
Felix Chalumeau"
Refiloe Shabe'
Noah De Nicola**2
Arnu Pretorius'
Thomas D. Barrett
Nathan Grinsztajn
InstaDeep University of Cape Town
Abstract
Routing Problems are central to many real-world applications, yet remain challeng- ing due to their (NP-)hard nature. Amongst existing approaches, heuristics often offer the best trade-off between quality and scalability, making them suitable for industrial use. While Reinforcement Learning (RL) offers a flexible framework for designing heuristics, its adoption over handcrafted heuristics remains incomplete. Existing learned methods still lack the ability to adapt to specific instances and fully leverage the available computational budget. Current best methods either rely on a collection of pre-trained policies, or on RL fine-tuning; hence failing fully utilize newly available information within the constraints of the budget. response, we present MEMENTO, an approach that leverages memory to im- prove the search of neural solvers at inference. MEMENTO leverages online data collected across repeated attempts to dynamically adjust the action distribution based on the outcome of previous decisions. We validate its effectiveness the Traveling Salesman and Capacitated Vehicle Routing problems, demonstrating its superiority over tree-search and policy-gradient fine-tuning; and showing that it can be zero-shot combined with diversity- solvers. We successfully train all RI. auto-regressive solvers large instances, and verify MEMENTO's scalability and data-efficieney: pushing the state-of-ther oath-oof-the-att on 11 out of 12 evaluated tasks.
Time Scaling
(Secoett
20
200
600-
400
500
Largo Instanees
Boandars Augmentatioss
Budgeer
Bike (Playons
MEMENTO (Duns)
EAS
Figure 1: MEMENTO outperforms Efficient Active Search wide range of instance sizes and different evaluation budgets. Its time complexity makes it scalable to large instances and policies.
"Corresponding author: f. chalumeaud instideep.cdc.mm com "Work completed during an internship InstaDeep EEqual supervision
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
Combinatorial Optimization (CO) encompasses a vast range of applications, ranging from transporta- tion (J-F Audy and Rousseau, 201 and logistics (Dincbas et al., 1992) to energy management (Froger et al., 2016). These problems involve finding optimal orderings or labels to optimize given objective functions. Real-world CO problems are typically NP-hard with solution space growing exponen- tially with the problem size. making it intractable to find the optimal solution. Hence, industrial solvers rely sophisticated heuristic approaches to solve them in practice. Reinforcement Learning (RL) provides a versatile framework for learning such heuristics and has demonstrated remarkable success in tackling CO tasks (Mazyavkina et al., 2021).
Traditionally, RL methods train policies to incrementally construct solutions. However, achieving optimality in a single attempt for NP-hard problems is impractical. Therefore, pre-trained policies are often combined with search procedures. The literature introduces a range of these procedures, from stochastic sampling (Kool et al., 2019; Kwon et al., 2020; Grinsztajn et al., 2023), beam search (Steinbiss et al., 1994; Choo et al., 2022), Monte Carlo Tree Search (MCTS) (Browne et al., 2012) to online fine-tuning (Bello et al., 2016; Hottung al., 2022) and searching space of diverse pre- pre-trained policies (Chalumeau et al., 2023b). One popular online fine-tuning strategy, Efficient Active Search (EAS) (Hottung et al.. 2022), uses transitions from generated solutions to derive policy gradient updates. However, suffers from the inherent drawbacks of paok-propagation, in particular having each data point only impacting the update as much what is enabled by the learning rate. The leading strategy, COMPASS (Chalumeau et al., 2023b), relies on space of diverse pre-trained policies for fast adaptation, but is limited selecting the most appropriate one, and lacks an update mechanism using the collected data. Meanwhile, the use of memory has grown in modern deep learning, demonstrated by the success of retrieval augmented approaches in Natural Language Processing (Lewis et al., 2020), and to a smaller extent, its use in RL (Humphreys et al., 2022). These mechanisms create a closer link between collected experience and policy update, making them a promising candidate to improve adaptation.
In this vein, we introduce MEMENTO, method to update the action distribution of neural solvers online, leveraging a memory of recently collected data. The approach is model agnostic and can be applied to existing neural solvers. MEMENTO learns expressive update rules, which experimentally prove to outperform standard policy-gradies routing tasks, the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP). We evaluate all methods both in and out-of-distribution and tackle instances up to size 500 to better understand their scaling properties. We provide an analysis of the update rules learned by MEMENTO, examining how it enables to adapt faster than policy gradient methods like EAS.
updates. We evaluate our method on two popular
Our contributions come follows: (i) We introduce MEMENTO, memory and processing module, cnabling efficient adaptation of policies at inference time. (ii) We provide experimental evidence that MEMENTO can be combined with existing approaches to boost performance in and out-of-distributio even for large instances and unseen solvers, reaching state-of -f-te--f-th-arrr art (SOTA) on 11 out of 12 tasks. (iii) Whilst doing so, we train and evaluate leading construction methods on TSP and CVRP instances of size 500 solely with RL, outperforming all existing RL methods. (iv) We open-source our implementations in JAX (Bradbury al., 2018), along with test sets and checkpoints.
2 Related work
Construction methods for CO These refer to methods that incrementally build solution one action after the other. Hopfield and Tank (1985) was the first to use a neural network to solve TSP, followed by Bello al. (2016) and Deudon al. (2018) who respectively added an RL loss and an sreettion-bsed encoder. These works were further extended by Kool et al. (2019) and Kwon al. (2020) to use a general transformer architecture (Vaswani et al., 2017), which has become the standard model choice that we also leverage in this paper. These works have given rise to several variants, improving the architecture (Xin et al., 2021: Luo et al., 2023) or the loss (Kim et al., 2021, 2022; Drakulic et al., 2023; Sun et al., 2024). These improvements are orthogonal to our work and could a priori be combined with our method. Construction approaches are not restricted to routing problems: numerous works have tackled various CO problems, especially on graphs, like Maximum Cut (Dai et al., 2017; Barrett et al., 2020), or Job Shop Scheduling Problem (JSSP) (Zhang et al., 2020; Park et al., 2021).

---

Construction methods make use of a predetermined compute budget to generate one valid solution for problem instance, depending on the number of necessary action steps. In practice, it common to have a greater, fixed compute budget to solve the problem at hand such that several trials can be attempted on the same instance. However, continuously rolling out the same learned policy is inefficient as (i) the generated solutions lack diversity (Grinsztajn et al., 2023) and (ii) the information gathered from previous rollouts is not utilized. How to efficiently leverage this extra budget has drawn some attention recently. We present the two main types of approaches that augment RL construction methods with no problem-specific knowledge (hence excluding solution improvement methods).
Diversity-based methods The first type of approach focuses on improving the diversity of the generated solutions (Kwon et al., 2020; Grinsztajn et al., 2023; Chalumeau et al., 2023b; Hottung et al., 2024). POMO (Kwon et al., 2020) uses different starting points to enable the same policy to generate diverse candidates. POPPY (Grinsztajn et al., 2023) leverages a population of agents with a loss targeted at specialization on sub-distribution of instances. was extended in Chalumeau et al. (2023b) and Hottung et al. (2024), respectively replacing the population with a continuous latent space (COMPASS) or discrete context vector (PolyNet).
Policy improvement at inference time The second category of methods, which includes ME- MENTO, addresses the improvement aspect. These methods are theoretically orthogonal and can be combined with those mentioned earlier. EAS (Hottung al., 2022) and Meta-SAGE (Son et al., 2023) employ a parameter-effiiien fine-tuning approach on the test instances, whereas SGBS (Choo et al., 2022) enhances this strategy by incorporating tree search. While demonstrating good performance, they rely on rigid, handcrafted improvement and search procedures, which may not be optimal for diverse problems and computational budgets.
In contrast, several methods aim to learn these improvement mechanisms. Macfarlane et al. (2022) train a Graph Neural Network to perform tree search akin to MCTS. MOCO, FER, and MARCO (Dernedde et al., 2024; Jingwen et al., 2023; I. Garmendia et al., 2024) learn the policy improvement update. MOCO (Dernedde et al., 2024) introduces a meta-optimizer that learns to calculate flexible parameter updates based on the reinforce gradient, remaining budget, and best solutions discovered far. MARCO (I. Garmendia al., 2024) aggregates graph edges' features and introduce
similarity metrics to improve exploration of the solution space. Both approaches enable learn adaptation strategies but are tied to heatmap- based policies, preventing their applicability to certain CO problems like CVRP. FER (Jingwen et al., 2023) learns a rule to update the instance nodes' embedding, whereas MEMENTO directly updates the action logits, hence being architecture-agnosti
3 Methods
3.1 Preliminaries
Formulation A CO problem can be represented as Markov Decision Process (MDP) denoted by M = (S, A, R, H). This formulation encompasses the state space S with states 8; S, the action space A with actions a, E A, the reward function R(r]s, a), the transition function T( 1 8;, as). and the horizon H indicating the episode duration. Here, the state of a problem instance is portrayed as the sequence of actions taken within that instance, where the subsequent state 8 is determined by applying the chosen action a, to the current state 8t. An agent is introduced in the MDP engage with the problem and seek solutions by learning a policy x (a|s). The standard objective considered in RL works is the single shot optimisation, i.e. finding policy that generates trajectory which maximises the collected reward: π arg max, Ex~, [R(T)] where R(7) = Σ R(st, at).
The specificity of most practical cases in RI. for CO is that the policy is given a number of attempts allowed per instance (budget B). to find the best possible solution, rather than single attempt. Consequently, the learning objective should rather be : x² = arg max, Ey [max;=1..... R(Tx)).
3.2 MEMENTO
Adaptation to unseen instances is crucial for neural solvers. Even when evaluated in the distribution they were trained on, neural solvers not expected to provide the optimal solution on the first shot,
3

---

due to the NP- ha-hardness of the problems tackled. Making clever use of the available compute budget for efficient online adaptation is key to performance.
Problem Instance
Base policy
Data for each action
Solution
Resulting policy
m(cle) +(a[M)
M
Memory module
*(alML)
Reward
M
opiitrries
M, R(M, 8)
Retrieve memortes
Create features using
Rollout policy create solution
and go memory
from
from transiiions
Figure 2: MEMENTO uses memory to adapt neural solvers at inference time. When taking decision, data from similar states is retrieved and prepared (1,2), then processed by MLP to derive correction logits for each action (3). Summing the original and new logits enables to update the action distribution. The resulting policy is then rolled out (4), and transitions' data is stored in a memory (5,6), including node visited, action taken, log probability, and return obtained.
compelling approach is to store all past attempts in a memory that can be leveraged for subsequent trajectories. This ensures that no information lost and that promising trajectories can be used more than once. There are many ways of implementing such framework depending on how the information stored, retrieved, and used in the policy. We would like the memory-baset update mechanism to be (i) learnable (how to use past trajectories to craft better trajectories should be learnt instead of harcoded) (ii) light-weight to not compromise inference time unduly (iii) agnostic to the underlying model architecture (iv) able to leverage pre-trained memory-less policies.
Overview To this end, we introduce ME- MENTO, a method that dynamically adapts the action distribution of the neural solver using online collected data. This approach, illustrated on Fig. 2, achieves the four desiderata: it stores light-weight data about past attempts, and uses an auxiliary model to update the action logits based on the previous outcomes.
Probder Irsiance
Premns Indaes
light
can be used on top of any pre-trained policy (architecture- agnostic). In principle, MEMENTO can be combined with existing construction RL algorithms: Attention-Model (Kool et al., 2019), POMO (Kwon et al., 2020), POPPY (Grinsztajn et al., 2023), COMPASS (Chalumeau et al., 2023b), which we confirm experimentally, learns an update rule during training, enabling data-efficient adaptation compared to policy gradient methods. The data retrieved from the memory and used by the auxiliary model to compute the new action logits contains more than the typical information used to derive policy gradient update. For instance, the budget remaining, enabling to calibrate the exploration/explottttoo trade-off and discover superior update rules. We show in Appendix F that MEMENTO has capacity to at least rediscover REINFORCE, and we show empirically in Section 4.1 that we outperform the leading policy-gradient updates adaptation method.
Figure 3: Building a new action distribution using the memory. Relevant data is retrieved and processed by a MLP to derive logits for each possible action.
Storing data in memory In the memory, we store data about past attempts (Fig. 2, step 6). Akin to replay buffer, this data needs to reflect past decisions, their outcome, and must enable to take better future decisions. For each transition experienced while constructing a solution, the memory stores the following: (i) node visited (i.c., in the context of TSP CVRP, this corresponds to the

---

current city or customer location), (ii) action taken, corresponding to the node that the policy decided to visit next (iii) log- proorbbbybyl given to that action by the model (iv) return of the entire trajectory (negative cost of the solution built) (v) budget at the time that solution was built (vi) log-probabilityy that was suggested by the memory for that action (vii) log- proobbbbiility associated with the entire trajectory and (vii) the log-probor log-probability associated with the remaining part of the trajectory. We can observe that elements (ii, ii and iv) are those needed to reproduce a REINFORCE update, and other features are additional context that will help for credit assignment and distribution shift estimation. The remaining budget is also added to the data when deriving the policy update.
Retrieving data from the memory Each time an action is taken in a given state, we retrieve data from the memory as shown in step 1 of Fig. 2. We retrieve data that inform the policy on past decisions that were taken in similar situations. To achieve a good balance between speed and relevance, we retrieve data collected in the same node as we are currently in; showing to be significantly faster than k-nearest neighbour retrieval, while extracting data of similar relevance. More details and motivation for this design choice provided in Appendix I.
Processing data to update actions Once data has been retrieved, it is used to derive policy update. We separate the actions from their associated features (logp. return, etc.... We concatenate the remaining budget to the features. Each feature is normalised, and the resulting feature vector (Fig. 2, step 2) is processed by Multilayer Perceptron (MLP) Ho which outputs a sealar weight. We compute the logits from the MLP output (Fig. 2, step 3): each action is one-hot encoded, and a weighted average of the actions vectors is computed based on the scalar weight obtained. This aggregation outputs a new vector of action logits. We sum the new vector of logits with the vector of logits output by the base model. The following paragraph introduces the mathematical formalism, and Fig. 3 illustrates it schematically.
More formally, when visiting a node, with given state s, we retrieve from the memory data experienced in the past when visiting that same node. This data, M., is sequence of tuples (a., fa.). where a; are the past actions tried and fa, are various features associated with the corresponding trajectories, as discussed above. The update is computed by IM E. a; Ho (fa;), where a; is the one-hot encoding of action a, Let l be the logits from the base policy, the final logits used to sample the next action are given by 1 + IM. We show in Appendix F that MEMENTO has enough capacity to re-discover the REINFORCE update.
Training Existing construction methods are trained for one-shot optimization, with a few exceptions trained for few-shots (Grinsztajn al., 2023; Chalumeau et al., 2023b; Hottung et al., 2024). We adapt the training process to fit the multi-shot setting in which methods are used in practice. We rollout the policy (Fig. 2, step 4-5) as many times as the budget allows on the same instance before taking an update. Our loss is inspired by ECO-DQN (Barrett et al., 2020) and ECORD (Barrett et al., 2022): for new given trajectory, the reward is the ReLU of the difference between the return and the best return achieved so far. Hence, those summed rewards equal the best score found over the budget. In practice, to account for the fact that is harder to get an improvement as we get closer to the end of the budget, we multiply this loss with a weight that increases logarithmically as the budget is consumed. See Appendix B for explicit formula and pseudo-code.
Inference The memory processing module can be used with any neural solver. The parameters of the base neural solver and those of the memory processing module are frozen (no more backpropagation), and the action updates are derived by filling the memory with the collected attempts and by processing the data retrieved from the memory, as described in the previous paragraphs, until the inference budget is consumed. All hyperparameters can be found in Appendix C.
4 Experiments
We evaluate our method across widely recognized routing problems TSP and CVRP. These problems serve as standard benchmarks for evaluating RL-based CO methods (Deudon et al., 2018; Kool et al., 2019; Kwon et al., 2020; Grinsztajn et al., 2023; Hottung et al., 2022; Choo et al., 2022: Chalumeau et al., 2023b). In Section 4.1, we validate our method by comparing it to leading approach for single-policy adaptation using online collected data, EAS (Hottung et al., 2022). We present their comparative performance in line with established standard benchmarking from literature, and
5

---

elucidate the mechanisms employed to adapt the action distribution of the base policy during inference. We then demonstrate how MEMENTO can be combined with SOTA neural solver COMPASS with no additional retraining in Section 4.2. Finally, we scale those methods to larger instances in Section 4.3, outperforming heatmap-based methods.
Table I: MEMENTO against baselines on a standard benchmark comprising 8 datasets with 4 distinet instance sizes on (a) TSP and (b) CVRP. Methods evaluated on instances from the training distribution (100) and on larger instance sizes to test generalization. MEMENTO outperforms policy-gradien method EAS and tree-search SGBS, with significant improvement over the base policy POMO. SGBS results are reported from Choo et al. (2022) (bias discussed in Appendix A.1).
(a) TSP
Training distr.
Generalization
100
125
150
200
Method
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
LKHB
|
7.765
0.000%
8.583
0.000%
9.346
0.000%
10.687
0.000%
POMO (greedy)
7.796
114044%
0.607%
9.440
1.01%%
10.933
2.300%
POMO (sampling)
7.779
0.185%
8.609
0.299%
9.401
0.585%
10.956
2.513%
SGBS
7,769
0.058%
9,367
0.220%
10.753*
0.619%
EAS-Emb
7.778
0.161%
8.604
0.238%
9.380
0.363%
10.759
0.672%
MEMENTO
7.768
0,045%
8,592
0.109 %
9.365
0.202
10.758
0.664 %
(b) CVRP
Training distr.
Generalization
100
125
150
200
Method
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
LKH3
15.65
0.000%
17.50
0.000%
19.22
0.000%
22.00
0.000%
POMO (greedy)
15.874
1.400%
17.818
1.818%
19.750
2.757%
23.318
5,992%
POMO (sampling)
15.713
0.399%
17.612
0.642%
19.488
1.393%
23.378
6. 6.264%
SGBS
15.659*
0.08%
19.426*
1.08%
22.567
2.50%
Emmh
15.663
0.081%
17.536
0.146%
0.528
22.541
2.460%
MEMENTO
15.657
0,066 %
17.521
0.095%
19.317
0.478%
22,492
2.205 %
Code availability We provide access the code" utilized for training our method and executing all baseline models. We release our checkpoints for all problem types and scales, accompanied by the necessary datasets replicate our findings. We implement our method and experiments in JAX (Bradbury et al., 2018). The two problems are also JAX implementations from Jumanji (Bonnet al., 2023). We use TPU v3-8 for our experiments.
4.1 Benchmarking MEMENTO against policy gradient fine-tuning
The most direct way to leverage online data for policy update is RL/policy-gradiens. By contrast, MEMENTO learns an update based on the collected data. We therefore want to how these two approaches compare. Since EAS (Hottung et al., 2022) is SOTA method using policy gradient, we benchmark MEMENTO against it on standard set of instances used in the literature (Kool et al., 2019; Kwon et al., 2020; Hottung et al., 2022). Specifically, for TSP and CVRP, these datasets comprise 10 000 instances drawn from the training distribution. These instances feature the positions of 100 cities/customers uniformly sampled within the unit square. The benchmark also includes three datasets of distributions not encountered during training, each comprising 1000 problem instances with larger sizes: 125, 150, and 200, generated from a uniform distribution across the unit square. We employ the exact same datasets as those utilized in the literature.
For routing problems such as TSP and CVRP, POMO (Kwon et al., 2020) is the base single- agent, one-shot architecture that underpins most RL construction solvers. In this set of experiments, MEMENTO and EAS both use POMO as base policy. and adapt it to get the best possible performance within a given budget. We train MEMENTO until converges, on the same instance distribution as that used for the initial checkpoint. When assessing active-search performance, each method operates within a fixed budget of 1600 attempts, a methodology akin Hottung et al. (2022). In this setup, each attempt comprises of one trajectory per possible starting point. This standardized approach
Setup
Coode, checkpoints, and evaluation sets available at tttps://ggithin www.//nntaaddenee http///sstaeepaaaeeeenttoo

---

facilitates direct comparison to POMO and EAS, which also utilize rollouts from all starting points each step. We do use augmentations with symmetries in our main results since they consume 87.5% of the budget to exploit network variance, which blurs the efficacy of the comparison and creates impractical settings for larger instances. Nevertheless, we report them in Appendix A.1 for continuity with previous literature.
The average performance of each method across all problem settings presented in Ta- ble The observations we draw are three-fold. First, MEMENTO outperforms its hase model (POMO) the entire benchmark by significant margin: showing that its adaptive search is superior to stochastic sampling. Second, MEMENTO outperforms EAS on all 8 tasks (spanning both in- and out-of-distribution) for both environments, highlighting the efficacy of learned policy updates when compared to vanilla policy gradients. Finally, we note that this improvement is significant; for example, on TSP100, MEMENTO is doing 60% better than sampling, while EAS only 6%. We provide all time costs and performance comparison based on time budget in Appendix A.1.
Results
Analysing the update rule To understand how MEMENTO uses its memory to derive policy update, we analyse the logit update of an action with respect to its associated data, inspired by Lu al. (2022); Jackson et al. (2024), and compare it to the REINFORCE policy gradient. On Fig. 4, plot the heatmap of the logit update with respect to the log probability (logp) and return associated with action. We observe that the main rules learned by MEMENTO action with low logp and high return gets a positive update while an action with high logp and low return gets discouraged. It is interesting to see discrepancies. In particular, MEMENTO's 's rules symmetric with respect to x = 0, it only encourages action that are strictly above the mean return. similar dissymetry would be expected with EAS since combines REINFORCE with term that increases the likelihood to generate the best solution found. Appendix extends this analysis by visualising the evolution of the update rule for different remaining budget.
similar to REINFORCE: an
Additionally, MEMENTO uses more inputs than REINFORCE: current budget available, trajectory logp, age of the data, and previous MEMENTO logit also used to derive the new action logit. Appendix G provides an ablation study of these additional inputs, validating their importance.
REINFORCE Logit Update
MEMENTO Logit Update
1.0
135
-0
3.00
Log Probability
335
32
66-
-12
-06
18
6.5 Normalized Return
Advantage
Figure 4: Akin to REINFORCE (left), MEMENTO (right) encourages actions with high returns, particularly when they have low probability. MEMENTO learns asymmetric rule: requiring the normalised return to be strictly positive to reinforce an action, but encouraging it even more.
4.2 Zero-shot combination with unseen solvers
In this section, demonstrate zero-shot combination (no retraining) with COMPASS. COMPASS adapts by searching amongst a collection diverse pre-trained policies.
Although providing fast adaptation, it can hardly improve further once the appropriate pre-trained policy has been found. In particular, online collected data cannot used to update that policy's 's action distribution. We use MEMENTO'S memory module, trained with POMO base policy, apply
7

---

on COMPASS without additional retraining, and show empirically that we can switch on MEMENTO's adaptation mechanism during the search and reach a new SOTA on 11 out of 12 tasks.
Methodology We combine our check- point of MEMENTO with released model of COMPASS (Chalumeau et al., 2023b). For the first half of the budget, we do not use MEMENTO, to let COMPASS find the appropriate pre-trained policy. Once the
Last Sample Performance
23.8
23.6
Tour Length
23.4
search starts narrowing down, we activate MEMENTO to adapt the pre-trained policy, with no need to turn off COMPASS' search. Fig. 5 shows the typical trends observed at inference. We recognise the typical search reported in Chalumeau et al. (2023b). At 50% of budget consumption, MEMENTO is activated and one can observe a clear and significant drop in averaged tour length of the latest sampled solutions. The standard deviation also illustrates how the search is narrowed down.
23.2
23.0
22.8
COMPASS
MENENTO (COMPASS)
Search budget (%)
Figure 5: Combining MEMENTO and COMPASS during search on CVRP200, no re-training needed.
Results We evaluate the zero-shot combination of MEMENTO and COMPASS on the standard benchmark reported in Section 4.1. Results for CVRP are presented in Table 2, showing tour length and optimality gap in-distribution (CVRPI00) and out-of-distribution. Although requiring no re- training, MEMENTO's rules combine efficiently with COMPASS and achieves new SOTA. Results on TSP are reported in Appendix A, and results on larger instances (TSP& & CVRP) in Section 4.3.
Table SOTA performance on CVRP via zero-shot combination of MEMENTO and COMPASS.
The rules learned by MEMENTO transfer to the population- method COMPASS.
100
125
150
200
Method
Obj.
Gup
Obj.
Gap
Obj.
Gup
Obj.
Gap
COMPASS
15.644
-0.11%
17.511
0.064%
19.313
0.485%
22.462
2.098%
MEMENTO (COMPASS)
15.634
-0.082%
17.497
-0.041%
19,290
0.336%
22.405
1.808
4.3
Scaling RL construction methods to larger instances
Scaling neural solvers to larger instances is a crucial challenge for the field. Auto-regressive construction-basee solvers are promising approaches, requiring limited expert knowledge whilst providing strong performance. But are still hardly ever trained on larger scales with RL. As a result, their performance reported in the literature usually quite unfair, being evaluated on large scales instances (>500) although having been trained on 100 nodes (Qiu et al., 2022). In this section, we explain how we train construction solvers POMO and COMPASS on instances of size 500 with RL (on TSP and CVRP, checkpoints released); and use them as new base models to train and validate properties of MEMENTO at that scale.
RL training on larger instances Training POMO on instances of size 500 involves three main steps. First, inspired by curriculum- based methods, we start from checkpoint pre-traine pre-trained on TSP100. Second, we use Efficient Attention (Rabe and Staats, 2022) to reduce the memory cost of multi-head attention, enabling to rollout problems in parallel despite the O(n2) memory requirement. Third, we use gradient accumulation to keep good estimates despite the constrained smaller instance batch size. These combined tricks enable to train POMO till convergence within 4 days, and consequently train COMPASS and MEMENTO. We also build the zero-shot combined MEMENTO (COMPASS) checkpoint.
inference-time constraints On larger instances, the cost of constructing a solution is significantly increased (for POMO'S architecture: squared computation and memory, and linear in sequential operations). It is also harder to get numerous parallel shots, which most methods depend on. It hence becomes crucial to develop data-efficient methods which stay robust to low budget regimes; and important to know which method to use for each budget constraint.
8

---

TSP
CVRP
Number solutions per attempt
100
EAB NEMENTO
NEMENTO EAS
60
20
-11
200
400
600
800
200
400
600
800
Number sequential attempts
Figure 6: MEMENTO outperforms EAS on instances size 500 across batch sizes and sequen- tial attempts. Green areas indicate settings where MEMENTO adapts more efficiently. It consistently outperforms EAS on TSP and in most CVRP settings, with strong gains under low budgets.
MEMENTO on larger instances We compare MEMENTO and EAS on set of 128 unseen instances (of size 500), for a range budget expressed in number of sequential attempts and number of parallel attempts attempts. Figure 6 reports the percentage of improvement (in absolute cost) brought by MEMENTO over EAS. From this figure, we can observe three main tendencies. First, the data-efficiency of MEMENTO is illustrated by its consistent superiority on low budget (lower left of plots), reaching significant improvement compared to EAS. Then, we can see that, on CVRP, the gap increases with the sequential budget for low parallelism. It demonstrates that MEMENTO'S update stays robust, whereas the gradient estimates EAS get deteriorated and cannot bring further improvement despite additional sequential budget. To finish with, we on TSP, even for higher budget. However, when budget increased for CVRP, RAS is able to outperform MEMENTO, given large enough batches (> 80).
that MEMENTO fully dominates the heatmap
Results In Table 3 and Table 4, we re-
Table MEMENTO achieves SOTA performance on TSP500. It outperforms baselines in both budget regimes, attaining single-agent and overall SOTA when combined with POMO and COMPASS, respectively.
port performance of our checkpoints, ing datasets introduced in Fu et al. (2021) and commonly used in the literature. For each environment, we report the results on different setting: (i) Low Budget, where the methods are given 25 000 at- tempts, (ii) High Budget, where 100 000 at- tempts are available. We also report results from concurrent RL methods (Qiu et al., 2022; Dernedde et al., 2024; Sun and Yang, 2023; Ye al., 2023), without method- agnostic local search; and industrial solvers LKH3 (Helsgaun, 2017) and Concorde (Ap- plegate et al., 2006).
Method
Obj-
Gap
Time
Concorde
16.55
0.000%
38M
LKH-3
16.55
0.003%
46M
DIMES Difusco
17.80
7.55%
2H
17.23
4. 4.08%
11M
DeepACO
18.74
13.23%
MOCO
16.84
1.72%
Pointerformer
3.56%
Low Budget
POMO (sampling)
16,999
2.736%
4M
EAS
16.878
2.006%.
COMPASS
16.811
1.603%.
9M
First, observe that stochastically sam- pling solutions with POMO for less than 10 minutes already provides competitive re- sults, ranking second among the five leading neural solvers. Adding EAS on top of POMO enables to compete with leading method MOCO on TSP500. This shows that auto- regressive RL constructive methods are com- petitive at this scale, contradicting previous literature (Qiu al., 2022; Dernedde et al., 2024).
MEMENTO (POMO)
16.838
1.766%
9M
(COMPASS)
1.586
High Budget
POMO (sampling)
16.986
2.650%
9M
EAS
1.804%.
COMPASS
16,800
1.539%
22M
MEMENTO (POMO)
16.823
1.673%
23M
(COMPASS)
16.795
1.507%
29M
is the first time that POMO is trained at this scale, making it the first RL-trained neural solver that

---

can be used for large instances on both TSP and CVRP: most previous large scale RL methods are graph-specific, and hence cannot be applied on CVRP.
These results confirm that MEMENTO scales to instance size, and can be zero-shot combined with COMPASS. On this benchmark, MEMENTO achieved SOTA on 3 of the 4 tasks when zero-shot combined with COMPASS, showing significant improvement compared to previous SOTA MOCO: the gap to optimality is reduced by more than 10%. It is the best single agent method on all TSP instances, and on the low budget CVRP task.
Time complexity Time performance at scale is key to the adoption of neural solvers, because the number of sequential batches of attempts that can be achieved within time budget will mostly depend on it. Search methods must be able to tackle large in- stances in reasonable time, and must scale well with the size of the base policy used, since Luo et al. (2023) demonstrated the im- portance of using large and multi-layered decoders in neural CO.
Table 4: MEMENTO outperforms baselines on CVRP500. It achieves single-agent SOTA on low budget regime with POMO and overall with COMPASS.
Method
Obj.
Gap
Time
LKH-3
37.229
0.00%
6H
Low Budget
POMO (sampling)
37.501
0.731
9M
EAS
37.425
0.525%
16M
37.336
0.287%
10M
MEMENTO (POMO)
37.367
0.369%
16M
MEMENTO (COMPASS)
37.309
0.215%
12M
Hence, we evaluate MEMENTO and EAS a set of increasing instance sizes and de- coder sizes and report their time complexity on Fig. (right). These plots show that, despite being slower for small settings, ME- MENTO's 's adaptation mechanism scales bet- ter than EAS. For an instance size of 1000, MEMENTO becomes 20% faster. And even for small instances (size 100), using 10 layers in the decoder's 's architecture (IM parameters) makes EAS 40% slower than MEMENTO. These scaling laws illustrate another benefit of using an approach that learns the update rather than relying on back-propagation to adapt neural solvers at inference time.
High Budget
POMO (sampling)
37.456
0.608%
20M
EAS
37.185
-0.120%
36M
COMPASS
37.279
0.133%
25M
MEMENTO (POMO)
37,306
0.206%
65M
MEMENTO (COMPASS)
37.251
0.059%
36M
5 Conclusion
We present MEMENTO, method to improve adaptation of neural CO solvers to unseen instances by conditioning a policy directly on data collected online during search and search budget. In practice. it proves to outperform stochastic sampling, tree search and policy-gradien tine-tuning, and shows zero-shot combination with an unseen solver. Additionally, MEMENTO respects several key properties, like robustness low-budget regimes, and favourable time performance scalability. We demonstrate the efficacy of MEMENTO by achieving SOTA single-policy adaptation on a standard benchmark TSP and CVRP, both in and out-of-distribution Moreover, show that MEMENTO finds interpretable update rules to the underlying policy; trading off exploration and exploitation over the search budget and outperforming REINFORCE-style updates. We further demonstrate zero-shot combination of MEMENTO and COMPASS, achieving overall SOTA on a benchmark of 12 tasks.
Limitations and future work MEMENTO incurs additional compute and memory usage compared to the memory-less base policies which it augments. Practically, we find that the performance gain significantly outweighs these overheads. A potential mitigation could be to derive the mathematical update learned by MEMENTO to avoid relying on the MIP computation. While we demonstrate successful zero-shot combination of MEMENTO with COMPASS, training MEMENTO with diversity- based method or fine-tuning MEMENTO specifically on the COMPASS policy represents a promising direction for future work.
Acknowledgements
We thank the Python and JAX communities for developing tools that made this research possible. We thank the anonymous reviewers for their valuable comments and suggestions that helped improve the final version of this paper. Finally, we thank Google's TPU Research Cloud (TRC) for supporting our research with Cloud TPUs.
10

---

References
D. Applegate, Bixby, Chvatal, and Cook. Concorde TSP solver, 2006.
I. Babuschkin, K. Baumli, A. Bell, S. Bhupatiraju, Bruce, P. Buchlovsky, D. Budden, T. Cai,
A. Clark, I. Danihelka, A. Dedieu, C. Fantacci, J. Godwin, C. Jones, R. Hemsley, T. Hennigan, M. Hessel, Hou, S. Kapturowski,
Keck, I. Kemaev, M. King. M. Kunesch, L. Martens, H. Merzic, V. Mikulik, T. Norman, G. Papamakarios, J. Quan, R. Ring, F. Ruiz, A. Sanchez,
I.. Sartran, Schneider, E. Sezener, S. Spencer, S. Srinivasan, M. Stanojevié, W. Stokowiec,
L. Wang, G. Zhou, and F. Viola. The DeepMind JAX Ecosystem, 2020. URL http::/tp:tiee
com con/deepmind.
T. Barrett, W. Clements, J. Foerster, and A. Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3243-3250, 2020.
T. D. Barrett C. W. Parsonson, and A. Laterre. Learning solve combinatorial graph partitioning problems via efficient exploration. arXiv preprint arXiv:2205. 14105, 2022.
I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint www.v:1611.0999////11 2016.
C. Bonnet, D. Luo, D. Byrne, S. Abramowitz. V. Coyette, P. Duckworth, D. Furelos-Blanco, N. Grin- sztajn, Kalloniatis, V. Le, O. Mahjoub, L. Midgley, Surana, C. Waters, and A. Laterre. Jumanji: suite of diverse and challenging reinforcement learning environments jax, 2023. URL https:/ /ate:://itttttt com/ insiinneeaaaiiiinneeeeaa jump:ppaaajjmmjji....
Bradbury, Frostig. P. Hawkins, M. Johnson, Leary, Maclaurin, Necula, Paszke, J. VanderPlas, S. Wanderman-Milng and Q. Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http: http:///ittbbb com/ com//oogle/jar
C. B. Browne, Powley, D. Whitehouse, M. Lucas, P. I. Cowling, P. Rohlfshagen, Tavener, D. Perez, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
F. Chalumeau, B. Lim, R. Boige, M. Allard, I.. Grillotti, M. Flageat, V. Macé, A. Flajolet, T. Pierrot, and A. Cully. Qdax: A library for quality-diversity and population-based algorithms with hardware acceleration, 2023a.
F. Chalumeau, S. Surana, C. Bonnet, N. Grinsztajn, A. Pretorius. A. Laterre, and T. D. Barrett. Combinatorial optimization with policy adaptation using latent space search. In Thirty-seventh Conference Neural Information Processing Systems, 2023b.
J. Choo, Y.-D. Kwon, J. Kim, J. Jae, A. Hottung, K. Tiemney, and Y. Gwon. Simulation cimulation-guided guided beam search for neural combinatorial optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022. URL https: // /ttxxvxxivvv////////////////aava org/ higg/tbe abs/2207 06190.
H. Dai, F. B. Khalil, Y. Zhang, B. Dilkina, and L.. Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, 2017.
T. Dernedde, D. Thyssens, S. Dittrich, M. Stubbemann, and L. Schmidt-Thiemee Moco: A learnable meta optimizer for combinatorial optimization. arXiv preprint arXiv:2402.049155 2024.
M. Deudon, Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau. Learning heuristics for the tsp by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 170-181. Springer International Publishing. 2018
M. Dincbas, H. Simonis, and P. Van Hentenryck. Solving a cutting-stock problem with the constraint logic programming language chip, Mathematical and Computer Modelling, 16(1):95-105, 1992. ISSN 0895-7177. doi: http:://o...gg///..00////9111111 sciencedirect. wwtpaceddreet..oomccciiieeeeeeee http:///ww.....e.eeeee/c.///t//a
URL https://wwt
D. Drakulic, S. Michel, F. Mai, A. Sors, and J.-M. Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances Neural Information Processing Systems, 2023.

---

A. Froger, M. Gendreau, J. E. Mendoza, Eric Pinson, and L.-M. Rousseau. Maintenance scheduling in the electricity industry: A literature review. European Journal of Operational Research, 251 (3):695-706, 2016. ISSN 0377-2217. doi: https//ioo..rr///0000066////:::0 00.5 URL
hittps://ww. www.sccienneeiret...oo htt.apawww...........a.a..ttaata
Z.-H. Fu, K.-B. Qiu, and H. Zha. Generalize small pre-trained model to arbitrarily large tsp instances. the Proceedings the AAA/ Conference on Artificial Intelligence, 35(8),7474-7482, May 2021. doi: 10.16099aaai..3588.. 16916. URL https://oja aaai. .rgg htt///ndxxx.ae http:///ee..ppp//.ttttttttt///// 16916.
N. Grinsztajn, D. Hurelos-Blanco, Surana, C. Bonnet, and T. D. Barrett. Winner takes it all: Training performant rl populations for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
K. Helsgaun. An extension of the ti-kermighan-helgee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde University, Tech. Rep., 2017.
J. J. Hopfield and W. D. Tank. "neural" computation of decisions in optimization problems. Biological cybernetics, 52(3):141-152, 1985.
A. Hottung, Y.-D. Kwon, and K. Tierney. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
A. Hottung, M. Mahajan, and K. Tierney. Polynet: Learning diverse solution strategies for neural combinatorial optimization. arXiv preprint arXiv:2402./4048 Feb 2024.
P. C. Humphreys, A. Guez, O. Tieleman, L. Sifre, T. Weber, and T. P. Lillicrap. Large-scale retrieval for reinforcement learning. In A. H. Oh, A. Agarwal, D. Belgrave, and Cho, editors, Advances in Neural Information Processing Systems, 2022. URL Ya91ATuQ3gg.
net/ id=
A. I. Garmendia, Q. Cappart, J. Ceberio, and A. Mendiburu. Marco: A memory-augmented reinforcement framework for combinatorial optimization. In K. Larson, editor, Proceedings of the Thirty-Third International Joint Conference Artificial Intelligence, IJCAI-24, pages 6931 6939. International Joint Conferences on Artificial Intelligence Organization, 2024. doi: 0.244963/jcai.222447766 URL atttps://do: org/ 10. 24963/ /itt///jjaiii.i 2024/766. Main Track.
S. D. J-F Audy and L.-M. Rousseau. Cost allocation in the establishment of collabora- tive transportation agreement an application in the furniture industry. Journal of the Op- erational Research Society, 62(6))960-970, 2011. doi: 10.1057/jors.2010.5 URI. https:
//doi.org/ 10. (057/jors 2010.53.
M. T. Jackson, C. Lu, L. Kirsch, R. T. Lange, S. Whiteson, and J. N. Foerster. Discovering temporally- aware reinforcement learning algorithms. In The Twelfth International Conference on Learning Representations, 2024. URL https::/
L. Jingwen, Y. Ma. Z. Cao, Y. Wu, W. Song, J. Zhang, and Y. M. Chee. Learning feature embedding refiner for solving vehicle routing problems. IEEE Transactions on Neural Networks and Learning Systems, PP, 05 2023. doi: 10. 2..1109/TNLLS.22233338855
M. Kim, J. Park, and j. kim. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, volume 34, page 10418-10430. Cur- ran Associates, Inc., 2021. URL attps://ee p/troced//rooosiingg. www.ripscc.pappr////// pttaaperr/22////////// 220h//aa2//hh///2// 564
Abstract html.
M. Kim, J. Park, and J. Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimiza- tion. In Advances in Neural Information Processing Systems, 2022. doi: 10.48550//rX1v.2255. 13209.
W. Kool, H. van Hoof, and M. Welling, Attention, learn to solve routing problems! In International Conference Learning Representations, 2019.
12

---

Y.-D. Kwon, B. K. Jinho Choo, Y. G. Uijoo Yoon, and S. Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances Neural Information Processing Systems, 2020.
P. Lewis, E. Perez, A. Piktus, F, Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W.-t Yih, T. Rocktäschel, S. Riedel, and D. Kiela. Retrieval-angmented generation for knowledge- intensive nlp tasks. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9459- 9474. Curran As- sociates, Inc., 2020. URL httpp::/proocoedinggg neurips cc/ cc/paper__. fitess/pppe////000 pdf.
C. Lu, J. G. Kuba, A. Letcher, L. Metz, C. Schroeder de Witt, and J. Foerster. Discovered policy optimisation. In Advances in Neural Information Processing Systems. FLAIR, University of Oxford, 2022.
F. Luo. X. Lin, F. Liu, Q. Zhang, and Z. Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances Neural Information Processing Systems, 2023.
M. Macfarlane, D. M. Roijers, and H. van Hoof. Training graph neural networks with policy gradients to perform tree search. In Deep Reinforcement Learning Workshop NeurIPS 2022, 2022.
N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021. ISSN 0305- 0548. doi: com/science artaicteeeeppaaaaa http:///e/pp//000055548220000000
1054000. URL https: / /www./wwww///o///////// sciencedirett..
J. Park, J. Chun, S. H. Kim, Y. Kim, J. Park, al. Learning to schedule job-shop problems: represen- tation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59 53311)333603333 2021.
2021.
R. Qiu, Z. Sun, and Y. Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Infor- mation Processing Systems, 2022. URL httttp::/oppnreeiiee
M. N. Rabe and C. Staats. Self-attention does not need o(r²² memory, 2022.
J. Son, M. Kim, H. Kim, and J. Park. Meta-sage: scale meta-learning scheduled adaptation with guided exploration for mitigating scale shift on combinatorial optimization. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR. 2023.
V. Steinbiss, B.-H. Tran, and H. Ney. Improvements in beam search. In Third international conference on spoken language processing, 1994.
R. Sun, Z. Zheng, and Z. Wang. Learning encodings for constructive neural combinatorial optimiza- tion needs to regret. In Proceedings of the Thirty-Eightt AAAI Conference on Artificial Intelligence, 2024.
Z. Sun and Y. Yang. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In Seieth- Conference on Neural Information Processing Systems, 2023. URL https: // wwwp//peeee..eeeeeeeeeeeeeeeeeee
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. Gomez, L. Kaiser, and I. Polosukhin. Attention all you need. In Advances in Neural Information Processing Systems, 2017.
T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60:61 1-624, 06 2012. doi: 10. 10.1227//
L. Xin, W. Song. Z. Cao, and J. Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the 35th National Conference on Artificial Intelligence, AAAI, 2021.
H. Ye, J. Wang. Z. Cao, H. Liang, and Li. DeepACO: Neural-enhanced ant systems for combinato- rial optimization. In Thirth-seventh Conference on Neural Information Processing Systems, 2023. URL https:/ //wp://eee///eeeee//eeee net//oorum/iid-dddDDDD0222
13

---

C. Zhang, W. Song, Z. Cao. J. Zhang, P. S. Tan, and C. Xu. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
14

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
15

---

Justification:
No theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Code, model checkpoints and validation sets provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipp cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /Codeeuomiisseeeeeeee
/nips. wwtppclcccc/ccccccccccccccccclct /tneeeeeudeeeeeeeeeiiiiiiii ssssssolicyyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [No]
Justification: They are in the zip file containing the code, and will be made open source upon acceptance.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttpas////uuiu../eeeeeeeee httppppp.ccppppcpateeeeeee
ctcpp/llic//hhhcccullleeeee.eeee ctw.idheeeeellleeccccccc ines?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Not relevant.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https / 220 for what should or should not be described.
21

---

Appendix
A Extended results
In Section 4, we compare MEMENTO to popular methods from the literature in numerous settings. In particular, Table compares using stochastic sampling, MEMENTO and EAS to adapt POMO on the standard benchmark; and Figure 6 compares the relative performances of MEMENTO and EAS on larger instances of TSP and CVRP for several values of batch sizes and budget. In this section, we report additional values and results of other methods for those experiments.
A.1 Standard benchmark
We evaluate our method, MEMENTO, against leading RL methods and industrial solvers. For RL specific methods, we provide results for POMO with greedy action selection and stochastic sampling, and EAS; an active search RL method built on top of PоMO, that fine-tunes a policy on each problem instance. We also report population based method COMPASS and the zero-shot combination of COMPASS with MEMENTO.
We compare to the heuristic solver LKH3 (Helsgaun, 2017); the current leading industrial solver of both TSP and CVRP, as well as an exact solver Concorde (Applegate et al., 2006) which is TSP-specific industrial solver, and the CVRP-specific solver (Vidal et al., 2012).
We use datasets of 10,000 instances with 100 cities/customee nodes drawn from the training dis- tribution, and three generalization datasets of 1,000 instances of sizes 125, 150, and 200, all from benchmark sets frequently used in the literature (Kool et al., 2019; Kwon et al., 2020; Hottung et al., 2022; Grinsztajn et al., 2023; Chalumeau et al., 2023b). Table displays results for TSP and CVRP on the standard benchmark. The columns provide the absolute tour length, the optimality gap, and the total inference time that each method takes to solve one instance within the attempts budget.
Standard benchmark with augmentation trick Augmentation with symmetries is problem- specific trick that can only be used for a few CO problems. Most prior work assumes that this additional x8 batching can be achieved seamlessly, which is unlikely in practice, when simulating complex real-world scenarios. Using this trick means decreasing the room for search and adaptation, since 87.5% of the budget consumed squeeze performance through uncontrolled network variance, rather than letting methods use principled strategies. Nevertheless, we report the standard benchmark with the "augmentation trick" in Table 6. can be observed that MEMENTO outperforms EAS in distribution (CVRP 100), and for the large instances task (CVRP 200). EAS leads on the two other tasks. MEMENTO leads the augmented benchmark overall: it consistently leads in distribution, and both methods are competing closely distribtittiiitionn. It is to be noted that we have not tuned MEMENTO'S 's hyper-pase parameaaeessess for these runs.
Times reported When possible, we decide to report the time to solve one instance rather the entire dataset following four main observations: (i) First, the literature use datasets of varying sizes, e.g. 10k for TSP100, 1k for TSP200, 128 for TSP500, hence time reported can be confusing, and do not enable to clearly see how methods' solving time scale with instance size. (ii) Second, the default real-world application consist in solving one instance same time but on separated hardware. (iii) Additionally, measuring on the entire dataset mixes several aspects, i.e. the instance solving time is mixed with the batch scalability of the method. We do think that this property is very interesting to know, but should be considered on the side, rather than mixed with the instance solving time. (iv) Moreover, this property will express differently depending on the hardware available. For instance, on a small hardware POMO sampling with n attempts will be n times slower than PоMO greedy; but given large enough GPU, POMO sampling can be parallelised n times and hence take exactly the same amount of time as POMO greedy.
time, solving several instances at the
We were able to do so on the standard benchmark since we have implementations of most methods we were comparing in a single framework. Since we are reporting several external methods in Table 8, we could only report time taken for the full dataset in that case.
Performance with runtime as budget Expressing budget as time taken to solve one instance is subject to high biases but it is gives interesting perspectives on the time analysis and effects of
22

---

parallelism. In Table 7, we provide results of using runtime in stead of attempts as budget given to each methods solve TSP and CVRP instances. We use EAS runtime as the reference time. These results may only be considered moderately since they are subject to number of limitations: (i) different labs use different implementations and frameworks (ii) labs have access to different hardwares (iii) time is sensitive to parallelism, whereas number of attempts is not. Hence, comparing methods with time is subject to a higher number of biases, and would make it almost impossible to compare papers without common codebase and hardware. We observe that MEMENTO still leads the benchmark, with out of top results; and both methods are very close on the two tasks where EAS leads.
Additional comments about the results On Table 5, we can see that in the single-agent setting, MEMENTO leads the entire benchmark, and in the population-basee setting, MEMENTO (COMPASS) is leading the whole benchmark. MEMENTO is able to give significant improvement to COMPASS on CVRP, pushing significantly the oate--of-theaare
this benchmark. On TSP, the improvement is not significant enough to be visible on the rounded results. To finish with, we can observe that the time cost associated with MEMENTO is reasonable and is worth the performance improvement (except maybe for TSP results of MEMENTO (COMPASS)).
Notes concerning SGBS All neural methods reported in Table 5 are our own runs with standardised checkpoints and rollout strategies, except for the results of SGBS, which were taken from Choo et al. (2022). This introduces three biases: (i) the base POMO checkpoint used by SGBS not exactly the same as our re-trained POMO checkpoint (ii) SGBS uses the domain-speciff augmentation trick that we do not use (iii) SGBS pre-selects starting points in CVRP, which we do not do.
Overall, the results reported in SGBS show that SGBS alone is always outperformed by EAS; hence, it should be expected that in all the settings where we outperform RAS, we would significantly outperform SGBS if both methods were evaluated exactly in the same way. We hence expect the gap between MEMENTO and SGBS to be larger than the one reported here. Additionally, SGBS has yet never been validated on larger instances. Nevertheless, we think that SGBS is a very efficient method from the NCO toolbox and appreciate that MEMENTO and SGBS are orthogonal, and could be combined for further improvement. We leave this for future work.
A.2 Performance over different number of parallel and sequential attempts
In Section 4.3, we show performance improvement of MEMENTO over EAS on instances of size 500 on TSP and CVRP for increasing number of sequential attempts and size of attempt batch. We report extended results with an additional competitor, POMO. We compare the online adaptation of the methods over four different sizes of batched solutions across increasing sequential attempts for each CO problem. Results from Table 8 show results of the three methods on TSP and CVRP. The columns show the best tour length performance for various values of sequential attempts expressed as budget, and solution batches of size N. Performance is averaged over a set of 128 instances.
A.3 Evaluation over larger instances
In Section 4.3, we evaluate MEMENTO and baselines on instances of size 500. For TSP, we use the dataset from Fu et al. (2021). For CVRP, we use the dataset from Luo et al. (2023). We do not include LEHD in our results since we focus methods trained with Reinforcement Learning, and LEHD can only be successfully trained with supervised learning at the time of writing. Nevertheless, the good performance achieved by LEHD has motivated us to study the scaling law of MEMENTO as the number of layers in the decoder increases, reported on Appendix A.4.
In order to run COMPASS and MEMENTO (COMPASS) with the same batch sizes as other methods on those large instances, we reduced the number of starting points used by COMPASS ensure that this number multiplied by the number of latent vector sampled at the same time is equal to the number of starting point used by other methods (POMO, EAS, MEMENTO). In practice, we used a latent vector batch of size 10, and hence divided the number of starting points by 10. This is slightly disadvantaging COMPASS and MEMENTO (COMPASS) but enables to respect the constraint of number of parallel batches that can be achieved at once. Note that this slightly impacts the time performance reported since JAX jitting process will not fuse the operations in the same way, additionally, when combined with MEMENTO, this impact the size of the memory (we keep one per starting point to
23

---

Table 5: Results of MEMENTO against the baseline algorithms for (a) TSP and (b) CVRP. The methods are evaluated on instances from training distribution (n = 100) as well as on larger instance sizes to test generalization. We use the same dataset as the rest of the literature, those contain 10000 instances for n 100 and 1000 instances for n 125, 150, 200. Gaps are computed relative to LKH3. We report time needed to solve one instance. SGBS * results are reported from Choo et al. (2022), and do not use the same POMO checkpoint as other reported results. Additionally, they rely on problem-specific tricks that were not used by other methods. Details in Appendix A.I.
(a) TSP
Training distr.
Generalization
1000
125
150
200
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj-
Gap
Time
Obj.
Gap
Time
Concorde
2.765
0.495
8.583
0.000%
0.725
9.346
0.000%
0.000%
1,665
LKIIS
7.765
0.000%
2.95
8.583
0.000%
4.45
9.346
0.000%
10.687
0.000%
115
POMO (grcedy)
7.796
0.401%
0.165
8.635
0.607%
0.25
9.410
1.00%%
0
10.933
2.300%
0.455
POMO (campling)
1.779
0,185
165
8.609
0.299%
205
9:401
0.585%
29S
10.956
2.513%
45S
2,769*
0,058%
9.167-
0.220%
10,753*
0.6/9%/
EAS
2.778
0.161%
395
8.604
0.238%
46S
0.363%
0.672%
918
MEMENTO (POMO)
7,768
0.045%
435
8.592
0.109%
525
9.365
0.202%
778
10.758
0.6641%
1158
COMPASS
7.765
0.008 %
205
8.586
0,036 %
2455
9:354
0.078%
33S
10.721
0.319%
498
MEMENIO (COMPASS)
7.765
0.008 %
325
8.586
0,033 %
395
9.354
0.077 %
58S
10.724
0,348%
89S
(h) CVRP
Training distr.
Generalization
100
125
150
200
Method
Gap
Time
Obj.
Clap
Time
Obj.
Clap
Time
Ohj.
Giap
Time
HGS
15.563
-0.536%
19.055
-0.88455
335
21.766
-1.896%
61S
L.KH
15.646
0.00076
528
17,50
0.000%
19.222
0.000%
728
22,005
0.000%
90S
POMO (gnoeds)
15.874
1.130%
245
17,818
L8888
348
19.750
2.757%
528
23.318
5.992%
878
POMO (smplinng)
15,713
0.399%
24S
17,612
0,642%
348
19,488
1,3938
52S
23.378
6.264%
87S
15.69a
19.426
1.08%
22.5674
2.50g*
BAS
15,663
0.0815
17,5%
0.146%
19.321
0.5285
22,541
2,400%
1798
MEMENTO (PONS))
15.657
0.0664
1188
17.521
0.098%
1508
19.317
0.478%
1698
22,492
2,205%
392S
COMPASS
15.641
-0.019%
295
17,51]
0.06.1
395
19.313
0.185%
568
22.462
2.098%
858
MEMENTO (COMPASS)
15.634
-0.082%
828
17.497
-1,041%
1005
19,290
0,336%
1188
22,445
1.008 S:
2728
Table 6: Results of MEMENTO and the baseline algorithms with instance augmentation for (a) TSP and (b) CVRP.
(a) TSP
Training distr. = 100
Generalization
125
150
= 200)
Method
Obj.
Time
Obj.
Gap
Time
Obj.
Time
Obj.
Time
LKH3
7,765
0.800%
2.95
8,583
0.000%
4.48
9.346
0.000%
68
10.687
0.000%
118
SCBS
7.769
0.058%
9.367
0.220%
10.753
0.619%
POMO (sampling)
7.767
0.026%
165
8.594
0.128
205
9,376
0.321%
295
10.916
2.14%
455
EAS
1.768
0.038%
8,590
0.080%
468
9.361
0.159%
648
10.730
0.403%
918
MEMENTO (POMO)
7.765
0.008%
438
8.586
0.0055%
528
9.355
0.0991 %
778
10.743
0.526%
1158
(b) CVRP
Training distr:
Generalization 150
100
125
200
Method
Obj.
Gap
Time
Obg.
Gap
Time
Obj
Gap
Time
Objj.
Glap
Time
HGS
15.563
0.536%
19.055
0.854%
21.766
1.006%
LKH3
15.646
0.00016
17,50
0.000%
19,222
0.000%
22.003
0.000%
SGBS
15,659
0.08%
19.426
1.08%
2.59%
POMO (sampling)
15.67
0.18%
24S
17.56
0.33%
348
19.43
1.08%
528
23.24
5.64%
878
EAS
15.623
-D.175%
668
17:473
+0.153%
82S
19.261
0.213%
1238
22.556
2,49%
1798
MEMENTTO (POMO)
15.616
-0.196%
17.511
0.040%%
1508
19.316
0.477%
1698
22.515
2.308 %6
3928
adapt to POMO, although this is completely agnostic to MEMENTO's method in itself). Since those factors impacts TSP and CVRP performance in different ways, this explains why their relative speed differ, i.e. why MEMENTO (COMPASS) is slower on TSP but faster on CVRP.
A.4 Time and memory complexity analysis
Time complexity To get the time curves reported in Fig. 7, we used CVRP, since is the envi- ronment were MEMENTO was the slowest compared to EAS. We hence expect curves on TSP to be
24

---

Table Results MEMENTO and the baseline algorithms with budget expressed as runtime for (a)
TSP and (b) CVRP.
(a) TSP
Training
Generalization
no 100
125
N: = 150
1: = 200
Method
Obj
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Obi.
Gap
Time
LKHH
7.765
0.000%
8,583
0.000%
9.346
0.000%
10.687
0.000%
POMO (sampling)
7.779
0.216%
39S
8.609
0.299%
9.401
0.585%
64S
2.513%
EAS
7.778
0.16%%
39S
8.604
0.238%
468
9,380
0.363%
64S
10.759
0.672%
918
MEMENTO
7.768
0.046%
398
8,592
0.110%
468
9.365
0.203%
648
10.760
0.681%
915
(b) CVRP
Training
Generalization
N. = 100
125
n1 = 150
= 200
Method
Obj.
Time
Obj-
Gap
Time
Ohj
Gap
Time
Ohj
Gap
Time
LKH3
15.647
0.000%
17.504
0.000%
19.225
0.000%6
22.007
0.000%
POMO (sampling)
15.713
0.399%
0.642%:
825
1.393%
23.378
6.264%
1798
EAS
15.663
0.081%
668
17.536
0.146%
82S
19.321
0.528
1238
22.541
2.460
179S
15,660
0,086 %
17.526
0.127%
825
19.321
0.502%
22.546
2.450%
179S
Table 8: Results of MEMENTO, POMO and EAS on instances of size 500 of (a) TSP and (b) CVRP for increasing number of sequential attempts and sizes of attempt batch.
(a) TSP
N 20
N
Method
200
400
600
800
1000
200
400
600
800
1000
(sampling)
16,9707
16.9638
16.9619
16.9574
16.9717
16.96
16.9549
16.9523
16.9493
EAS
16,9223
16.8923
16.8754
16.864
16.8556
16.8777
16.8468
16.83
16.8208
16.8143
MEMENTO
16.8112
16.81
16.799
16,7939
16,7902
16.8187
16.8018
16.7926
16.7855
16.7815
N 60
Method
200
400
600
800
1000
200
400
600
800
1000
POMO (sampling)
16.9678
16.9587
16,9539
16.952
16:9503
16.9634
16.9547
16.9513
16.9495
16.9474
EAS
16.8616
16.8353
16.8211
16.8134
6688
16,8521
16,8234
16.8106
16.8014
16.7941
MEMENTO
16.8129
16.7966
16.7867
16.7816
16.7780
16,8087
16.7935
16.7854
16.7811
16.7770
(b) CVRP
N 20
N 40
Method
200
400
600
800
1000
200
400
600
800
1000
POMO (sampling)
37.5256
37.4917
37.4763
37.4633
37.4570
37,4858
37. 37.4599
37.44755
37.4372
37.4307
37.6107
37.5988
37.5914
582
37.5769
37.5022
37.4546
37.422
37,4017
37.3849
MEMENTO
37.3398
37.2992
37.2731
37.2589
37.2527
37.3172
37,2776
37.2515
37,2357
37.2260
N 60
N 80
Method
1000
1000
POMO (sampling)
37.4598
37.436
37.4228
37.4191
37:4135
37.4588
37.4335
37.4198
37.4113
37.4050
EAS
37,4569
37.3679
37.3248
37.2892
37.2624
37.3588
37,2804
37.2346
37.2021
37.1747
MEMENTO
37.292
37.2607
37.2305
37.2171
37.2092
37.2887
37,2556
37,2382
37.2268
37.2142
even better for MEMENTO. For the instance size scaling, we use 50 starting points and 100 sequential attempts, and 1 layer in the decoder, and evaluate several instance sizes going from 100 to 1000. For the decoder layer depth scaling, We then evaluate methods for a depth going from to 10.
CVRP100, 100 starting points and 160 sequential attempts.
Computational and memory complexity analysis The use of memory to compute corrected action logits (i.e., MEMENTO's policy update rule) introduces a computational overhead, whose scaling properties depend specific design choices and problem parameters.
Consider the TSP100 example with the memory design presented in the paper. The memory contains 100 slots (one per node), each storing 40 entries with 5 float32 values, repeated for each starting point (100). This results in roughly MB of memory data. The memory footprint therefore scales linearly with the instance size (since there is one slot per node), but remains independent of the base policy size. addition, the MI. module used to process memory entries small, consisting of two layers with eight hidden units.
25

---

Regarding computational cost, the main overhead comes from processing the retrieved entries through the MLP. At each step. 40 entries are retrieved and processed in parallel, so the effective cost that of 40 independent MIP forward passes. This operation does not depend on the instance size or the policy's parameter count, only on the number of retrieved entries. An additional cost arises from indexing the appropriate slice of the memory, which can grow slightly with the number of nodes.
In practice, these overheads make MEMENTO slower than EAS for small instance sizes or small neural networks. However, since its operations scale more favorably with instance size and parameter count (compared to backpropagation), MEMENTO becomes faster for larger problems.
Overall, the computational and memory overhead of MEMENTO is negligible when solving a few instances time, typical in practical settings where one receives new problem instance and limited compute budget, but it can become bottleneck when solving large batches of problems in parallel, as often done in research benchmarks.
To provide more concrete view of the report the runtime of POMO in Table 9. The difference between the two indicates the additional cost introduced by MEMENTO. Note that these values may depend on the backend: for example, JAX's jit compilation can impact relative timings, and alternative implementations (e.g.. PyTorch) could yield different ratios.
cost across instance sizes, we also
Table 9: Average inference time (in seconds) for each algorithm across instance sizes,
Instance Size
100
500
750
875
950
POMO
114
225
360
443
504
446
774
973
1122
MEMENTO
148
212
425
684
833
940
Tima Complexity Instance Size
Time Complexity Dacodar Layar Depth
EAS
250
225-
Timee (Secodd)))
(Seconat
175-
125-
100
Instance Sizu
Number Layars
Figure 7: Time complexity of MEMENTO and EAS for increasing values of decoder size, and instance size. MEMENTO is shown scale better in time than EAS.
B Training procedure
This section give detailed description of how an existing pre-trained model can be augmented with MEMENTO, and how we train MEMENTO acquire adaptation capacities.
Firstly, we take an existing single-agent model that was trained using the REINFORCE algorithm and reuse it base model. In our case, the base model is POMO. We augment POMO with memory module and begin the training procedure which aims to create a policy that able to use past experiences make decisions in multi-shot setting, We initialize the memory module weights with small values such that they barely affect the initial output. Hence, the initial MEMENTO checkpoint maintains the same performance the pre-trained POMO checkpoint.
In the training procedure, the policy is trained to use data stored the memory to take decisions and solve a problem instance. This is achieved by training the policy in budgeted multi-shot setting on problem instance where past experiences are collected and stored memory. The memory is organised by nodes such that only information about specific node is found in data row that
26

---

corresponds to that node. The policy retrieves data from the memory at each budget attempt and learns how uses the data to decide on its next action.
The details of the MEMENTO training procedure are presented in Algorithm and can be understood as follows. At each iteration, we sample batch B of instances from problem distribution D. Then, for each instance where E 1,..., B, for K budget attempts, we retrieve data from the memory. This is done follows; given that the current selected node is aj. we only retrieve data M(a)) associated with node Oj and its starting point. However, the method is agnostic to starting point sampling and would work without it. The features associated with the retrieved action are then normalised. We add remaining budget as an additional feature and process the data by Multilayer Perceptron (MLP) which outputs a scalar weight for each action. We compute correction logits by averaging the actions based on their respective weights. The correction logits are added to the logits of the base policy. We then rollout the resulting policy Th on the problem instance (i.e., generate a trajectory which represents a solution to the instance). After every policy rollout attempt, the memory updated with transitions data such as the action taken, the obtained return, the log- log-probability of the action and the log-probability of the trajectory. These data are stored in the row that corresponds to the current selected node.
Details about the loss For each problem instance, want optimise for the best return. At each attempt, we apply the rectified linear unit (ReLU) function to the difference between the last return and the best return ever obtained. We use the rectified difference compute the REINFORCE loss at each attempt to avoid having reward that is too sparse and perform back paok-propggttion through the network parameters of our model (including the encoder, the decoder and the memory networks). The sum of the rectified differences is equal to the best return ever obtained over the budget. As the budget is used, it becomes harder to improve over the previous best, the loss terms hence getting smaller. We found that adding weight to the terms, with logarithmic increase, helped ensuring that the last terms would not vanish, and thus improved performance. We provide the mathematical formulation below.
Given problem instance, we unroll B trajectories that we store iteratively in the memory. Each trajec- tory Ti generates a return R(T.). The advantage for each trajectory defined as R(T,)) = max(R(T)) Roest, 0), where Reest is the highest return found so far. The total loss for updating the policy is cal- culated using the REINFORCE algorithm: L = Σ log(1 + + R(,) Σ, log aM (ax st, Mc). where xM is the policy enriched with the memory M,, using the logits L defined in eq. in the paper. é is a small number ensuring that the first term is not zero.
To keep the computations tractable, we still compute loss at each step, estimate the gradient, and average them sequentially until the budget is reached, at which point we take a gradient update step and consider a new batch of instances.
In practice, we also observe that we can improve performance further by adding an optional refining phase where the base model is frozen, and only the memory module is trained, with a reduced learning rate (multiplied by 0.1), for few hours.
C Hyper-parameters
We report all the syper-parameet to report for instance sizes 125, 150, and 200 as the model there is no training used was trained on instances of size 100. The in Table 10. Since we also trained POMO and COMPASS larger instances, report hyper- parameters used for POMO and COMPASS in Table 11 and Table 12, respectively.
used during train and inference time. For our method MEMENTO,
used for MEMENTO are reported
D Model checkpoints
Our experiments focus on two CO routing problems, TSP and CVRP, with methods being trained on two distinct instance sizes: 100 and 500. Whenever possible, we re-use existing checkpoints from the literature; in the remaining cases, we release all our newly trained checkpoints the repository anonymised for the review process.
27

---

Algorithm MEMENTO Training
1: Input: problem distribution D, problem size N, memory M, batch size B, budget K, number of training steps T, policy Fy with pre-trained parameters 0.
2: initialize memory network parameters 6
3: combine pre-trained policy parameters and memory network parameters = (0, (0,
4: for step
do
5: < (ample(D) vi E .1....,
6: for attempt to K do
7:
for node 1 to N do
8:
m < Retrieve (M) Vj E I...,, (Retrieve data from the memory)
9:
-े + Rollout (pi, ma(-Im;)) Vi,j E : B
10:
mj + f(mg. n/)) (Update the memory with transition data)
R t- max(R2, R(T()) vi I.... B {Update best solution found so far)
12:
(0) + *BEisD REINFORCE((BLUUC
R,))) {Estimate gradient]
VI(0)) +- -KA *E VL(Ø) (Accumulate gradients)
14:
8 - aV (Update parameters)
Table 10: The TSP
used in MEMENTO
Phase
Hlype parameters
TSP100
TSP(125, 150)
TSP200
TSP50D
Train time
budget instances butch size
200
200
64
starting points gradient accumulation
100
30
200
400
memory size number of layers hidden layers activation
40
80
2
GELU
GELU
learning rate (memory)
0.004
0.004
learning rate (encoder)
0.0001
0.0001
learning (decooder)
0.0001
Inference
policy noise
0.2
0.1
0.8
memory size
40
40
40
40
(b) CVRP
Phuse
Hyper- prrre--arameters
CVRPI00 CVRP(125, 150)
CVRP200
CVRP500
budget
instances butch size starting points
64
8
gradient accumulation steps
200
800
memory size number of layers hidkle units activation learning rate (memory)
2
8
GELU
GELL
0.004
0.004
learning rale (encoder)
0.0001
0.0001
learning (decoder)
0.0001
0.0001
Inference time
policy noise memory size
0.1
0.1
0.1
0.3
40
40
40
40
We evaluate MEMENTO on CO problems, TSP and CVRP, and compare the performance to that of two main baselines: POMO (Kwon et al., 2020) and EAS (Hottung et al., 2022). The checkpoints used to evaluate POMO TSP and CVRP are the same as the one used in Grinsztajn et al. (2023) and Chalumeau et al. (2023b), and the EAS baseline is executed using the same POMO checkpoint. These checkpoints were taken in the publicly available repository https:// htpps:///ithhti com/ iiiitndnepai/pppeeecoe (as described in Appendix B). To combine MEMENTO and COMPASS on TSP100, we re-use COMPASS checkpoint available at attps://gt thub. com/ hwmm/iistadeppaii. petereppppccc/ppssse/e/eea compass and add the memory processing layers from the MEMENTO checkpoint trained on TSP100. This checkpoint also released at anonymised for the review process.
The POMO checkpoint is used in the initialisation step of MEMENTO
28

---

Table 11: The
used in POMO
Phase
Hlyper parameters
TSP500
CVRP500
Train time
starting points
200
200
instances batch size
64
32
gradient accumulation
2
policy noise
Inference time
sampling batch size
8
Table 12: The hyper- parereaaseeeerss used in COMPASS
Phase
Ilyper parameters
TSPS00 CVRP500
Train time
latent space dimension
16
16
training sample size
64
instances batch size
8
8
gradient accumulation steps
policy noise
0.5
0.3
Inference time
num. CMA-ES components
CMA-ES init. sigma
100
100
sampling batch size
For larger instances, we compare our MEMENTO method to three basclines: POMO, EAS and COMPASS. Since no checkpoint of POMO and COMPASS existed, we trained them with the tricks explained in Section 4. The process to generate the MEMENTO checkpoint and the MEMENTO (COMPASS) checkpoint then exactly the same. All those checkpoints are available, for both TSP and CVRP.
E
Implementation details
The code-base in written in JAX (Bradbury al., 2018), and mostly compatible with recent repositories of neural solvers written in JAX, i.e. Poppy and COMPASS. The problems' implementation are also written in JAX and fully jittable. Those come from the package Jumanji (Bonnet al., 2023). CMA-ES implementation to mix MEMENTO and COMPASS is taken from the research package QDax (Chalumeau et al., 2023a). Neural networks, optimizers, and many utilities are implemented using the DeepMind JAX ecosystem (Babuschkin et al., 2020).
F Can MEMENTO discover the REINFORCE update?
In Section 3.2, we presented the architecture used by the auxiliary model that processes the memory data to derive the new action logits. The intuition behind this architecture choice is that it should be able learn the REINFORCE update rule. Indeed the REINFORCE loss associated with new transition is Rlgg(Te (ogg((T(()))) (a)), such that AR (og((()(a)) R(1 (a)))). Therefore, simply having How (fa) macch R(1 To (a)) would recover REINFORCE- update. This is feasible, as R and log( no (a)) are included in the features fa.
Sl,
We compare the rule learned by MEMENTO to REINFORCE in Fig. 4 and provide analysis of how the rule learned by MEMENTO evolve over different budgets in Appendix J. In Appendix G, we present an ablation study of the features used in the update rule of MEMENTO, showing how much performance can be gained from the use of more information to derive the update rule.
G Ablation Study: MEMENTO input features
In Section 3.2, we present MEMENTO, in particular, we present all the inputs that are used by the neural module to derive the new action logits from the memory data. These inputs, or features, are information associated to each past action taken, and that help decide whether those actions should taken again or not. In Section 4. we compare the rule learned by MEMENTO compared to the baiiiegg update REINFORCE. This comparison is made on the features that both REINFORCE and MEMENTO use: i.e. the action log probability, and the return (or advantage if a baseline is used). Although REINFORCE only uses those two features, MEMENTO uses more, which enables refine even more the update, and also to adapt the budget remaining in the search process. As recall, in addition the log probability and return, MEMENTO uses: the log probability
29

---

of the full trajectory, the log probability of the rest of the trajectory after the action was taken, the budget at the time the action was taken, the action logit suggested by MEMENTO when the action was taken, and the budget currently remaining.
To validate the impact of all the features used in the memory, we provide ablation study of those features. To highlight the interest of using all the additional features, we report the performance of MEMENTO using only the return and the log probability, against the performance of MEMENTO with all features, on Fig. 8. We also report on Fig. a bigger ablation where components are added one after the others.
We can extract two main observations: (i) first, adding the remaining budget completely changes the strategy. We can MEMENTO to explore much more, and then to focus on high-performing solutions when gets closer the end of the budget; (ii) then, Fig. 9 confirms empirically that all features contribute improving the overall performance.
the right panel of Fig. 8 that having access to this additional feature enables
Last Sample Performance
HIRENTOER
10-1
Relative Average Length
MEMENTOCIIO
Relative Tour Length
10-2
10-1
10-3
6 10
4 x 10
0
500 1000
1500
0
500
1000
1500
Search Budget
Figure Ablation study of MEMENTO: comparing the impact of memory features that are not available in usual policy gradient estimations methods. The left plot reports the best solution found so far. The right plot shows the performance of the latest solution sampled. The plot illustrates how the additional features enable to achieve complex exploration strategy, reaching significantly more efficient adaptation mechanism.
Last Sample Performance
MEMENTO
1
Relative Mean Tour Length
Relative Tour Length
10
10-2
6 60
10-3
4 x 10
0
500
1000
1500
500
1000
1500
Search Budget
Figure 9: Full ablation study of MEMENTO: comparing the impact of memory features that available in usual policy gradient estimations methods. The left plot reports the best solution found so far. The right plot shows the performance of the latest solution sampled. A: return + logp; A + remaining budget; C: B + budget when action was taken; D: C memory logp + trajectory logp + end trajectory logp.
30

---

H Evaluation metrics during training phase
In this section, we provide two plots of MEMENTO's training phase. They show the evolution of performance over time during MEMENTO'S training on CVRPI00. The left plot reports the evolution of the best tour length obtained during validation over time. The right plot reports the evolution of the improvement delta over time, i.e. the difference between the quality of the best solution generated minus the quality of the first solution generated. This metric shows well how the training phase results in MEMENTO learning update rule that is able to significantly improve the base policy.
MEMENTO Training Phase
15.70
0.20
15.69
0.19
15.68
Improvement Delta
0.18
Tour Length
15.67
15.66
0.17
15.65
0.16
15.64
0.15
15.63
0.14
15.62
10
30
40
50
10
30
40
50
60
Training Budget
Figure 10: Evaluation metries during the training phase of MEMENTO.
I Memory retrieval mechanism
In this section, we provide additional motivation for the choice of the node retrieval mechanism used in MEMENTO.
Ideally, the retrieval mechanism should retrieve data based similarity to the current partial solution. But this comes with a computation cost since requires getting a similarity measure and extracting the k most similar points in the entire memory. We observe that retrieving from the same node is an excellent proxy for similarity, and that the most similar points are very likely to come from the same node. This retrieval strategy hence provides better trade-off between quality and computation cost, which is why it was selected as the final strategy for MEMENTO.
Nevertheless, MEMENTO comes framework, and each practitioner is free to change part of the method to fit each specific problem. One can hence update the retrieval mechanism if desired. Below is example of an alternative strategy for retrieval that does consider the partial solution constructed. Since the output of the multi-head attention of POMO decoder builds a oow-dimensional representation of the partial solution, can store this vector in the memory, and when building new solution, retrieve only the k-nearest neighbors of the current partial solution's 's representation. One could even apply further dimensionality reduction reduce the cost of the nearest neighbor search. This approach brings significant cost increase, even when using state-of-the nearest neighbor JAX implementation. This effect gets worse when batching the attempts, the problem instances. In the problems and settings considered in this paper, our simplified retrieval approach maintains similar results, while significantly improving scaling.
approximated
Evolution of MEMENTO learned update over budget
We further analyse how the update rule learned by the MLP evolves over the course of the budget. Specifically, we compute the MLP's logit correction values across a grid of inputs by varying the normalised return and the log probability of the action, while fixing all the other inputs. These allows us isolate the learned update pattern across the return and log probability space. As shown in Fig. 11, MEMENTO strongly upweights low-probability, high-return actions, consistent
31

---

with advantage- advantage-weighted updates, but exhibits a sharper concentration around high-value transitions. Importantly, we observe temporal shift: early in the budget, the MLP assigns nonzero corrections even to uncertain or suboptimal transitions promoting broad exploration. As the remaining budget decreases, the corrections become increasingly selective, focusing on high-return, high-confidence actions.
Budget
Log Frobabiltty
Mid Budget
Log Probsabiiig
Log Prabebilly
12
Figure 11: The update rule discovered by MEMENTO across different budget stages (low, mid, high). The learned update rule shifts from broad exploration to sharper exploitation as the budget decreases.
K Impact of train-time budget
The main experiments report results for MEMENTO trained with budget of 200 sequential attempts. In this analysis, we evaluate variants of MEMENTO trained under alternative training budgets, and evaluate their performance for increasing inference budgets. We report the results in Table 13.
Despite being trained with different budgets, all variants of MEMENTO exhibit stable performance across a wide range of inference budgets. This confirms that conditioning the remaining budget enables flexible behaviour even when the actual inference budget differs from that used in training. Overall, observe that MEMENTO performs robustly across budget mismatches and that all variants generalise reasonably well beyond their training budget. Notably, the model trained with 200 attempts consistently performs the best which attribute tuning bias: the hyperparameters were selected based on validation performance at budget 200, and were not re-tuned for other settings.
Table 13: Performance of MEMENTO on TSP100 across different inference budgets, trained with three budget settings.
Inforence
5 30
8 10C
B - 230
200
27
403
2
500
- 620
1930
2 1600
Bodgs
Okg
Cup
01g
Gop
Ol6
Gap
06g
Gap
0kg
Gap
Oli
Ga)
Ots.
Gap
06)
Gep
[ki
Cup
2,709
3.767
2.707
2068
04007495
7.769
01997555
2.999
0/06224
1.766
01909%
77665
0.03192 01811955
7 1W61
300
7.788
01079M
7.764
0./ceers
1.767
0.00963
7.967
010175
2.907
0.00975
7,267
00015:
1.MM
800013
7.766
0.00995
7 769
0.0999
32


Reviews:
[{"review_id": "ebU1MfRn7v", "reviewer": "Reviewer_VKs9", "summary": "RL agent to solve specific routing problems which also utilizes history of past decisions and their outcomes for crafting better updates.", "questions": "5. Do you see the proposed approach also being useful for other cases of CO (non-routing) problems?\n6. The word node occurs multiple times in the paper but it is not exactly defined anywhere. Does by node you mean a decision variable of the CO problem?\n7. How do base policy module and memory module interact to produce the resulting policy? (Seeing Figure 2).", "limitations": "8. Exposition of the paper needs to be improved.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1. I like the overall motivation of the approach to give history of previous time steps to derive a better 'update steps' for the CO solver. \n\n2. Extensive experimental evaluation shows promise. \n\nWeaknesses:\n\n3. I would have liked more details about the method itself in the main paper. The content between Lines 129 - 195 is too abstract to get the exact details of the approach. I know about more details in the Appendix but let us not underestimate the importance of sharing 'research thoughts/ideas/explanation' and overemphasize the importance of experiments. Even the teaser Figure in the first page is not so important.   \n\n4. Similar to above Figure 3 does not add a lot of value. I would rather prefer exact details in text. Similarly Lines 133-135: it can be combined with ...., should rather be elsewhere. I would like to know what is being done in this paper! I can keep going to give further examples but I think the above ones are enough to get my point across.  PS: I like Algorithm 1 in the Appendix, perhaps it can be put in the main paper and using that as means of describing the method?", "was_revised": true, "final_justification": "Raising my score since my concerns are resolved. I will look forward to a revised version of manuscript. It is also good that the source code of the approach would be made available.", "rebuttal": "We thank the reviewer for their detailed and thoughtful feedback.\n\n\\\n**> W1–W2: Clarity of the Method Section and Figures**\n\nWe 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.\n\nWhile 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.\n\nRegarding 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.\nWe thank the reviewer again for highlighting areas of improvement, and will ensure the revised draft foregrounds the method more clearly, with minimized indirection.\n\n\\\n**> Q1: Generalisation to non-routing CO Problems**\n\nMEMENTO’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.\n\n\\\n**> Q2: Clarification on the term “Node”**\n\nThank 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.\n\n\\\n**> Q3: Interaction between base policy and memory module**\n\nAs 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."}, {"review_id": "8CAj3Z7U5D", "reviewer": "Reviewer_HUQk", "summary": "This paper introduces MEMENTO (Memory-Enhanced Neural Solvers), a novel approach designed to enhance the search capabilities of neural solvers for Routing Problems, particularly at inference time. The core motivation is to improve the adaptability of learned heuristics to specific problem instances and better utilize available computational budgets, an area where existing Reinforcement Learning (RL) based methods often fall short compared to handcrafted heuristics.\n\nMEMENTO achieves this by integrating a memory mechanism into the neural solver's inference process. This memory dynamically updates the action distribution based on the outcomes of previous decisions, allowing the solver to learn from its own search history within a single instance. \n\nThe key contributions of this work are:\n\nA novel memory-enhanced framework: MEMENTO leverages a dynamic memory to guide the search process of neural solvers at inference time.\n\nDynamic action distribution update: The memory mechanism allows the model to dynamically update its action distribution based on previously visited nodes or partial solutions, enabling better adaptation to the current instance.\n\nSuperior performance and adaptability: MEMENTO is validated on Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP), demonstrating superior performance compared to traditional tree-search methods and policy-gradient fine-tuning.\n\nZero-shot combination with diversity-based solvers: The paper shows that MEMENTO can be effectively combined with diversity-based solvers, further improving solution quality.\n\nScalability to large instances: The approach successfully trains RL autoregressive solvers on large instances, indicating its potential for real-world applications.", "questions": "Question: The paper demonstrates that retrieving from the same node is an effective proxy for similarity. Have the authors explored more complex memory contents (beyond just the current node's representation) or retrieval strategies in detail, perhaps even briefly experimenting with them for smaller instances to understand their theoretical potential before dismissing due to computational cost? For example, storing more holistic partial solution embeddings or using different similarity metrics.\nSuggestion: Provide a brief qualitative or quantitative discussion (perhaps in the appendix) on the trade-offs involved in different memory content and retrieval strategies. While the chosen method is practical, demonstrating why others are less suitable (beyond just computational cost) would strengthen the design choices.\n\nQuestion: The paper mentions that the simplified retrieval approach was chosen for better scaling. Could the authors provide a more explicit quantitative analysis of the computational overhead introduced by the memory update, storage, and retrieval operations within MEMENTO? How does this overhead scale with the number of nodes (N) and the number of search attempts (K)?\nSuggestion: Include a table or graph in the appendix showing the breakdown of inference time, distinguishing between the core neural solver's time and the overhead incurred by MEMENTO's memory operations, across different problem sizes and K values. This would offer a clearer picture of MEMENTO's practical efficiency.\nCriterion for Score Change: A detailed computational analysis of the memory operations would improve the Quality of the experimental evaluation and enhance the paper's practical Significance.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nQuality: MEMENTO presents a well-conceived and technically sound approach to improve neural solvers. The integration of a memory mechanism at inference time is innovative and addresses a critical limitation of existing RL-based heuristics (lack of instance-specific adaptation). The experimental setup is robust, comparing MEMENTO against strong baselines including tree search (POMO with sampling), policy gradient fine-tuning, and combining it with diversity-based methods. The results consistently demonstrate MEMENTO's superiority across TSP and CVRP benchmarks, including larger instances, which strongly supports the claims.\n\nClarity: The paper is well-written and easy to follow. The problem statement regarding the limitations of current RL heuristics is clearly articulated. The MEMENTO framework, including the motivation for memory, the memory update mechanism, and its integration with the neural solver, is explained with excellent clarity. Figures (e.g., Figure 1 illustrating the framework) are highly effective and aid comprehension. The mathematical formulations are precise and enhance the understanding of the memory dynamics.\n\nSignificance: MEMENTO offers a significant contribution to the field of neural combinatorial optimization. By enabling instance-specific adaptation at inference time without requiring expensive retraining or complex tree-search algorithms, it bridges a crucial gap between learned heuristics and traditional handcrafted heuristics in terms of flexibility and budget utilization. This improvement in adaptability and quality, especially for larger instances, has immense practical implications for real-world routing problems. The ability to zero-shot combine it with diversity-based solvers further enhances its practical utility.\n\nOriginality: The core idea of \"memory-enhanced\" inference for neural combinatorial optimization is highly original. While memory networks exist in other domains, their specific application here to dynamically update action distributions in an autoregressive routing solver at inference time, based on an evolving partial solution, is novel. The method for deciding what to store and how to retrieve from memory is also an original design choice that leads to strong empirical results.\n\nWeaknesses:\n\nMemory Content and Retrieval Strategy: While the paper justifies the chosen retrieval strategy (retrieving from the same node), a more detailed exploration of alternative memory content (e.g., more complex partial solution representations beyond just the current node's embedding) and retrieval strategies (e.g., k-nearest neighbors based on solution embeddings, as briefly discussed but dismissed for cost reasons) could provide deeper insights. The current strategy might be optimal for the tested problems, but its generalizability to problems with richer state information is less clear.\n\nComputational Overhead of Memory: While the paper states that the simplified retrieval approach improves scaling compared to k-nearest neighbors, a more explicit quantitative analysis of the computational overhead introduced by the memory operations (storage, retrieval, update) as a function of problem size (N) and number of attempts (K) would be beneficial.\n\nLimitations of \"Zero-Shot\" Combination with Diversity: While MEMENTO can be combined zero-shot with diversity-based solvers, the paper could briefly discuss potential limitations or scenarios where this combination might not be as effective, or where a more integrated design might be preferable.", "was_revised": true, "final_justification": "Authors address my concerns and for providing additional context and clarification. Please ensure that all the promised improvements and additions, including the new table on inference time and the explicit discussion of design choices, are fully incorporated into the final version of the paper.", "rebuttal": "We sincerely thank the reviewer for raising these thoughtful points, especially concerning memory design and practical efficiency.\n\n\\\n**> W1 & Q1: Memory content and retrieval strategy**\n\nWe 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.\n\nThat 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.\n\n\\\n**> W2 & Q2: Computational overhead of memory and scaling with problem size (N) and attempts (K).**\n\nWe 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.\n\nFor 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).\n\nWe 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.\n\n\\\n**> W3: Limitations of “zero-shot” combination with diversity-based solvers**\n\nWe 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.\n\nTo 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."}, {"review_id": "H0AmHVSnrw", "reviewer": "Reviewer_C68N", "summary": "The paper introduces MEMENTO, a memory-based method for online fine-tuning of neural combinatorial optimization solvers. MEMENTO enhances a pretrained constructive policy by incorporating a learned residual policy that adjusts action probabilities during inference. A memory module is used to store features from past solution trajectories—such as actions taken, associated rewards, and contextual signals—which are processed by an MLP to guide future decisions. An improvement-based reward signal enables MEMENTO to adapt the policy on-the-fly to each problem instance. Experiments on TSP and CVRP instances with up to 500 nodes demonstrate that MEMENTO consistently outperforms strong baselines, achieving effective instance-specific adaptation within constrained computational budgets.", "questions": "none", "limitations": "none", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\n\n1) The paper is well-written, with clear exposition and strong organization. \n\n2) A notable contribution of this work is its focus on incorporating computational budget constraints into the design of a construction-based neural CO solver.\n\n\n## Weaknesses\n\n1) Despite the considerable additional effort—such as introducing a memory module, fine-tuning the base model while training the auxiliary MLP concurrently—the performance gain of MEMENTO over the much simpler baseline, EAS, is not particularly compelling.\n\n2) To better highlight what I believe is one of the core strengths of the method—the incorporation of budget constraints—the authors should evaluate performance across a wide range of computational budgets: low, moderate, and high. If the meta-learning approach of the authors are working as claimed, the results will show that the model trained for the large budget setting performs worse than the low-budget setting model in the short run, but eventually surpasses it as more computation is used.\n\n3) The improved update rule illustrated in Figure 4 is intriguing, but the methodology behind generating the figure is not well explained. To plot such a graph, one would need to fix all other input variables to the MLP. Was the figure created by averaging over all nodes? All trajectories? Clarifying this process would help readers better understand the nature of the learned update behavior.\n\n4) Furthermore, if the authors can extract and interpret the underlying logic of the MLP that leads to improved update rules over REINFORCE—as Figure 4 suggests—this direction deserves deeper exploration. For example, does the MLP promote stronger exploration early in the process and gradually shift toward exploitation? Does it induce more aggressive updates at the beginning or closer to the end of the budget? Addressing such questions would not only help validate the effectiveness of the method but also provide valuable insights for the broader research community.", "was_revised": true, "final_justification": "I hope the authors will incorporate the revisions they indicated during the discussion period into their final manuscript. \n\nGiven that the neural networks in this work were not trained under different budget settings, it is likely that successful training depends on substantial manual tuning of hyperparameters and heuristics (e.g., learning rate scheduling). This could make it challenging for readers to easily apply the algorithm to other applications. Nevertheless, the originality of the ideas presented in the paper outweighs this shortcoming, and I do not oppose the paper’s acceptance.", "rebuttal": "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.\n\n\\\n**> W1: Performance gain of MEMENTO over EAS**\n\nWe 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.\n\nIn particular, MEMENTO:\n- Conditions on remaining budget, allowing it to shift behavior over time (e.g., explore early, refine later), unlike fixed-update methods.\n- Operates without backpropagation at inference, making it significantly faster and more scalable in large-instance or large-model settings (Fig. 7).\n- Can be used zero-shot with new base policies like COMPASS, highlighting its modularity, a generality not afforded by EAS.\n\nThese 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.\n\nWhile 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.\n\n\\\n**> W2: Evaluation across a wide range of computational budgets**\n\nIndeed, 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.\n\nAdditionally, 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.\n\nWe will make this budget-sensitivity aspect more prominent in the main paper.\n\n\\\n**> W3: Clarification of Figure 4**\n\nWe 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.\n\n\\\n**> W4: Interpretability of the learned update rule**\n\nWhile the MLP operates as a black box, we have conducted a structured analysis of its outputs that reveals interpretable behavior.\n\nSpecifically, 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.\n\nBeyond 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.\n\nThis 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."}, {"review_id": "JCdvXDgUUp", "reviewer": "Reviewer_JcvL", "summary": "The paper proposes a new approach to solve routing problems using learning based methods. Existing methods include constructive heuristics, that learn a policy to construct a solution but do not leverage the insight from earlier tried solution on the same problem instance. Other existing methods do this, but with additional limitations such as being applicable only to heatmap-based policies or only learning embeddings. The proposed solution is architecture-agnostic: it learns to modify the logits generated by a 'base policy' based on memory of choices made at the same node on the same instance. The instances in this memory are combined using a learned 'rule'. Experiments show this method capable of improving the performance of the base method to the state of the art, even on large instances (500 nodes) and even if combined with a different base method at inference time.", "questions": "- As representation of the state, your method only uses the current node visited. Have you experimented with other representations of the state (such as an (embedding of) the sequence so far), and why do you think using only current node gives the best result? \n\n- Why do you think it helps the method to have as input the remaining budget when action in memory was taken? It seems to me that to maximize the reward function (improvement over best reward so far) this should not have impact on the optimal policy. Perhaps it is a proxy for \"best reward so far\" (which should help the policy)? Did you consider \"best reward so far\" as feature for the memory module?\n\n- How well do you expect this method to generalize to other routing problems and to non-routing optimization problems?What is the motivation for only considering TSP and CVRP?", "limitations": "The checklist mentions error bars are reported, however, none of the tables give error bounds (Fig. 5 does, though).", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality - Strenghts\n- The main claims in the paper are supported empirically. Experiments are well set up, thorough, on relevant and subfield-appropriate environments, with a suitable choice of and number baselines. (although only two different problems, TSP and CVRP, at different sizes, are used.) Relevant analysis and ablations are shown, such as the comparison to REINFORCE, the zero-shot combination, ablations on policy inputs.\n\nQuality - Weaknesses\n- Formulation: The formulation in 3.1 does not seem to accomodate the policy being conditioned on earlier samples, which does not seem to fit the approach proposed later. \n- The comparison to REINFORCE could perhaps be stated a bit more carefully. I understand the comparison of two processes that based on data would change the logit of future actions. However, it should also be stated that these were defined for very different purposes: long-term gradual improvement of a policy versus immediate (and somewhat greedy) selection of an action. While the comparsion this nuance could be better transmitted. \n-The paper states that existing work on leveraging prior samples have additional limitations such as being applicable only to heatmap-based policies or only learning embeddings. One exception that could be mentioned is \"training graph neural networks with policy gradients to perform tree search\" by Macfarlane at all (Neurips Deep RL workshop 2022). \n\nClarity - Strengths\n- The structure of the paper is generally clear, the use of language is generally clear and appropriate, figures are used effectively to illustrate the methods and results. \n\nClarity - Weaknesses\n- Abstract could make more clear that approach leverages earlier attempts on the same instance; also to readers who wouldn't immediately understand what 'budget' refers to in this setting. \n- Some discussion and presentation of the results is misplaced. The structure could be improved by moving Fig. 1 to Section 4 (now on the first page!) and to remove the forward reference to Fig.4 from Section 2. The metrics in Fig 1 (left) should be better explained. \n\nSignificance\nThe proposed method achieves a consistent performance across almost all conditions and environments investigated. The effect size is sometimes modest, which makes sense on these environments where performance is slowly satisfying. It was impressive to see good performance from the POMO family of auto-regressive methods on size-500 instances for the first time. Experiments are limited to TSP and CVRP so it is not known how significant the proposed method is on other routing problems or even non-routing combinatorial problems. Overall, I would consider the method to be a quite significant contribution to this subfield. \n\nOriginality\nThe main idea of the paper is somewhat similar to those of existing work, but getting this to work at state of the art level required several original insights, design choices, and modifications. Overall I'd rate the originality as good. \n\nMinor comments\n- line 157 mentiond only (ii, iii, iv) are sufficient for the reinforce update, but this should include the state as well.\n- sentence in line 293 lacks a subject\n- it is helpful to include the metric shown in the figure caption or legend. This is missing from figures 4, 6, for example (it is explained in the text, but that makes it a bit harder to find)", "was_revised": true, "final_justification": "I will maintain my score (5: Accept) as I think even with the changes the paper does not reach the level of 6: Strong Accept (requiring, among others, \"groundbreaking impact\" and \"exceptionally strong evaluation\").", "rebuttal": "We thank the reviewer for their constructive comments and insightful suggestions regarding formulation clarity, methodological comparisons, and applicability to broader settings.\n\n\\\n**> W1: Section 3.1 – Policy conditioning and formulation**\n\nWe 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.\n\nTo 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.\n\n\\\n**> W2: Comparison with REINFORCE – clarification of intent and purpose**\n\nMEMENTO’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.\n\nOur 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.\n\nWe 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.\n\n\\\n**> W3: Clarifying “budget” and abstract wording**\n\nWe 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.\n\n\\\n**> W4: Suggested structure and placement of figures**\n\nWe acknowledge the reviewer’s point and will revise the paper layout accordingly. Specifically:\n- Figure 1 will be moved to Section 4, where it is better aligned with the experimental results to avoid flow of the introduction.\n- Remove forward references from Section 2 (e.g., Fig. 4).\n- 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.\n\nThese changes should improve the structure and clarity of the presentation.\n\n\\\n**> Q1: Using richer representations of state (e.g., partial solution embeddings) instead of just nodes.**\n\nYes, 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.\n\n\\\n**> Q2: Why is the remaining budget used as an input feature to the MLP? Could other features like “best return so far” be helpful?**\n\nWe 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.\n\nWe 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.\n\n\\\n**> Q3: Generalization to other routing and non-routing problems**\n\nWe 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).\n\nWe 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."}]

Author rebuttal:

Meta-review: This work proposes MEMENTO, which is a memory-enhanced approach, to improve the performance of neural combinatorial optimization methods for routing problems. The key idea of MEMENTO is to memorize the past attempts of the neural solvers and leverage them to adapt the solver's decision at inference time. To be specific, it stores the past attempts of solution construction and retrieves the information contained in the node (of the past attempts) that the solver is currently in. It then builds and uses an auxiliary model to generate the action logits conditioned on the past attempts as well as the remaining computational budget. Finally, the MEMENTO logits are augmented to the policy logits (generated by the original neural solver) to make the action decision. In this way, MEMENTO satisfies 4 desiderata: learnable, light-weight, agnostic to the model, and can leverage pre-trained memory-less policies.

The reviewers find this work well-motivated and well-written, the proposed MEMENTO method is novel and original, and the experimental results are thorough and strong. This paper initially received mixed ratings with major concerns on the clarity of proposed methods and figures, computational overhead, performance gain over simple baselines, and incorporation of budget constraints. The rebuttal successfully addressed most concerns, and two reviewers voted to accept this work, while the remaining two reviewers leaned toward weak acceptance.

I read the paper myself and fully agree with the reviewers that this work is a promising contribution and offers a potentially impactful approach to the neural combinatorial optimization community. Therefore, I recommend a clear acceptance of this work as a spotlight. I am also curious to see how MEMENTO will perform on problems other than TSP and CVRP, and whether MEMENTO can be incorporated with the recent (non-RL) construction-based neural CO solvers that achieved strong performance on much larger-scale instances.

Please make sure all the discussion and promised revisions are carefully incorporated into the final paper.
Decision: Accept (spotlight)