Recurrent State Encoders for Efficient Neural Combinatorial Optimization

Tim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme · 2025

Read Recurrent State Encoders for Efficient Neural Combinatorial Optimization by Tim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-05084.txt.

Introduction

Neural solvers that build a route one stop at a time recompute almost the same state at every step. Tim Dernedde, lead author with two co-authors, propose a recurrent state encoder to reuse that computation in a 2025 paper on neural combinatorial optimisation. Their encoder builds each state embedding from the previous one as well as the current state.

The recurrent model matches or beats a non-recurrent encoder with far fewer layers, cutting latency in their tests. Results cover travelling salesman, capacitated vehicle routing, and orienteering problems. The authors also plug the models into a large neighbourhood search algorithm to show practical value.

Catalog record

CREATORTim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-05084

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Recurrent State Encoders for Efficient Neural Combinatorial Optimization Tim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme Abstract The primary paradigm in Neural Combinatorial Optimization (NCO) are construction methods, where a neural network is trained to sequentially add one solution component at a time until a complete solution is constructed. We observe that the typical changes to the state between two steps are small, since usually only the node that gets added to the solution is removed from the state. An efficient model should be able to reuse computation done in prior steps. To that end, we propose to train a recurrent encoder that computes the state embeddings not only based on the state but also the embeddings of the step before. We show that the recurrent encoder can achieve equivalent or better performance than a non-recurrent encoder even if it consists of 3 × 3\times fewer layers, thus significantly improving on latency. We demonstrate our findings on three different problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Orienteering Problem (OP) and integrate the models into a large neighborhood search algorithm, to showcase the practical relevance of our findings. Our code, checkpoints, and datasets are publicly available at https://github.com/TimD3/Recurrent-NCO . 1 Introduction Neural Combinatorial Optimization (NCO) is concerned with learning heuristics parameterized by deep neural networks for hard combinatorial optimization problems (COPs). The motivation is twofold: First, tailoring traditional heuristics to the exact problem at hand can be a difficult and time-consuming task, requiring specialized knowledge. If data-driven methods can be designed that are able to automatically learn high quality heuristics, development effort could be significantly reduced. Second, NCO uses the fact that for applications there always exists an implicit distribution over the instance space. Given the NP-hard nature of most problems, it is unlikely that there exists a single method that solves all instances efficiently. Thus, being able to specialize to any particular instance distribution by learning from data is a desirable property. The primary paradigm currently are construction methods, where a neural network sequentially adds to a partial solution until some completion criterion is met. In the Traveling Salesman Problem (TSP), for example, the model would start at some node and iteratively add one of the not yet chosen nodes to the solution until all nodes are visited. Given that the goal is to solve optimization problems and with infinite time even naive enumeration of the solution space would yield the optimal solution, it is clear that finding good solutions quickly is the main goal. In the described construction process many problems inhibit the property that subsequent states are very similar. In the TSP for instance, every node that gets added to the solution, can be removed from the state, since it is already decided on and not relevant for future decision-making. This makes all pairs of subsequent states very similar, since they only differ in the one node. Past approaches [ 30 , 32 , 51 , 5 ] have therefore mainly relied on an encoder-decoder architecture, where the encoder computes a set of node embeddings only in the first step and the decoder computes the action probabilities based on these embeddings for all following steps. While efficient, it was observed that the models can struggle to learn with increasing problem size [ 25 ] since the embeddings also contain information about increasingly less relevant interactions of components not present in the state anymore and recent work has shown that the more model capacity is added to the decoder instead of the encoder [ 36 ] or the more frequently the encoder is recomputed [ 43 ] , the better. In particular, Luo et al. 2023 only utilize a single encoder layer and Drakulic et al. 2023 remove the split between encoder and decoder entirely and apply a singular model at every step. While this works well, it is significantly more expensive and ignores the similarity between the states. In order to still make use of this property and build a more efficient model, without losing the ability to adjust to changes in the state at every step, we instead propose to learn the difference between subsequent states . In order to do so, we train a recurrent encoder that computes the state embeddings not only based on the current state but also the embeddings of the step before, allowing it to reuse computation done in prior steps. We show that such an embedding update does not compromise on accuracy and decreases latency. Our contributions can be summarized as follows: • We propose a novel recurrent state encoder for neural combinatorial optimization , which updates the node embeddings at every step based on the current state and the prior node embeddings. A hyperparameter k controls the number of steps after which a non-recurrent base encoder is used to recompute the embeddings, allowing a flexible trade-off between both encoders. • We demonstrate that the recurrent encoder can achieve equivalent or better performance to the non-recurrent encoder with significantly smaller number of parameters and thus improves on the latency accuracy trade-off. Depending on the exact model and problem, we find latency decreases of 1.8-4\times at no significant accuracy drop . Crucially, non-recurrent encoders of the same size and latency are not able to achieve the same performance. Additionally, the models are surprisingly robust, often delivering stable performance, even if the recurrent encoder is used with much larger k than seen during training. • Finally, we integrate our recurrent models into a large neighborhood search algorithm, showcasing how our improvements impact practically relevant search methods in terms of performance and latency. We demonstrate that our findings hold on three different combinatorial optimization problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Orienteering Problem (OP). 2 Related Work Neural Combinatorial Optimization NCO has seen a diverse set of methodologies in recent years. In our work we focus on the very common constructive paradigm, where solutions are sequentially constructed with a neural network. Note however that various approaches exist, such as parameterizing a local search operator [ 38 , 39 ] , learning a local search meta controller [ 15 , 52 ] , parameterizing insertion operators [ 22 , 27 ] , learning heatmaps [ 16 , 24 , 40 , 47 , 52 , 35 , 53 ] , learning to select subgraphs or decompositions [ 14 , 19 , 34 , 36 , 53 ] and various hybridizations thereof. In the domain of constructive methods our main contribution lies in the way the neural network processes the state. We propose a novel model that computes state embeddings from the current state and previous embeddings, thus only having to learn the difference between two states. In contrast, most prior work has focused on an encoder-decoder model [ 30 ] and variations of it [ 5 , 13 , 21 , 23 , 31 , 43 , 51 ] , where the encoder computes a set of static node embeddings in the first step and the decoder computes the action probabilities based on these embeddings and some dynamic context information for all subsequent steps. It was shown however that such approaches struggle with

Read the complete text