RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem

arXiv:2610.15106 · cs.LG, cs.NE, math.OC · Submitted 2026-10-10 · Read on arXiv

Listen

Transcript

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

Tom: Today's paper: "RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem".

Jane: The gist: RELAGRAM introduces Recursive Latent Graph Model for graph combinatorial optimization,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: Moving on from the architecture, the authors discuss their objective function. They’re not just using standard reinforcement learning; they combine it with self-imitation, which is a pretty unique twist for this kind of optimization task >

Jane: That self-imitation part is key. They define a loss function that combines the reinforcement learning term with a self-imitation loss on the edge heatmap, specifically L edge(H t, tau elite t). This pushes the unmasked heatmap toward the shortest sampled route tau elite t using cross-entropy loss >

Lu: That self-imitation term is designed to pull the learned edge scores towards a known good solution, which is something they do by optimizing with that specific loss structure >

Meng: From a production standpoint, it’s interesting how they manage this. They update every recursion depth with one optimizer update, but crucially, they detach the latent states between steps so gradients never propagate down the recursive chain >

Jane: That detachment is important because it keeps things computationally manageable during training; you don't have to calculate gradients all the way back through every recursive layer for every single token >

Tom: So, they are managing a lot of complexity by keeping the states detached between steps while still having a continuous recursive update loop. It’s a clever way to balance learning and computational efficiency >

Lu: That's how they handle the tiny recursive model, or TRM. The Tiny Recursive Model keeps those two states, y and z, initialized as fixed random vectors y zero z zero in R d, and the network F theta is a two-block transformer that applies self-attention and SwiGLU sublayers >

Jane: And they use RMSNorm without learned scale, as in TRM, to keep things stable during training. This stability helps ensure the learning process doesn't explode when you’re running these deep recursive passes >

Meng: I worry about the initialization of those vectors. If y zero and z zero are poorly chosen, it could just lead to unstable latent states that never converge on a useful solution, Meng would say.

Tom: They initialize them as fixed random vectors in R d, so they rely on the network F theta to learn the necessary structure from scratch during training rather than starting with something specific >

Lu: And then they map the answer state y t to an edge heatmap H t,ij using a bias-free linear head that takes the score of moving from i to j and projects it into R d scaled by sqrt d >

Jane: That linear projection is what creates the actual scores for those edges, which then feed into the autoregressive decoder to build the final solution route >

The paper's summary: Tom: Now let’s talk about some of the specific ways they show improvement in this RELAGRAM model. They highlight that by tuning the self-imitation weight lambda SI, they can get much stronger results >

Lu: They found that setting lambda SI = zero point three gives them the strongest greedy result, which suggests it’s a pretty good starting point for optimizing this specific loss function >

Jane: So, if you are trying to tune the model for real-world routing problems, you start by focusing on that weight setting because it seems to be the most effective way to align the model with practical route lengths >

Meng: Tuning hyperparameters is always a headache. If one small parameter like lambda SI dictates whether you get a good result or not, that makes deployment much riskier, Meng would say.

Tom: It’s a trade-off between learning the underlying structure and just forcing it toward known short routes through the self-imitation term >

Jane: And they show that this tuning works across different problem sizes. They test it on CVRP-one hundred CVRP-five hundred and CVRP-one thousand instances >

Lu: They are showing that this hyperparameter tuning strategy isn't just a trick for one small instance; it’s a method that generalizes the optimization across these different problem sizes >

Tom: And they also show robust scaling across those problem sizes when using two hundred fifty-six-candidate decoding, achieving gaps of fifteen point six four percent and twenty-one point six five percent on CVRP-five hundred and CVRP-one thousand without retraining >

Jane: That zero-shot performance across those scales is really what makes this paper stand out for me when thinking about how we apply these kinds of models to real infrastructure problems >

The paper's improvements: Tom: So to wrap up the RELAGRAM paper, the main message is that a small latent-recursive model successfully learns to route a solution for graph combinatorial optimization >

Jane: It’s a proof of concept for applying latent recursion to graph combinatorial optimization. The authors hypothesize that an important limitation is the sparse reinforcement learning signal, which they suggest needs further engineering for latent recursion >

Lu: They also point out that the recursive nature of RELAGRAM may be very useful for dynamic problems because it already runs zero-shot past the conditions it was trained under >

Meng: So if we take that idea and combine it with a decoder, a single model could solve dynamic problems end-to-end without needing to constantly retrain >

Tom: It seems like a promising direction for neural routing, especially given the evidence they’ve shown on CVRP instances >

Jane: The matched greedy comparison doesn't find any significant advantage from recursion, which is an interesting finding, but overall, RELAGRAM shows that latent recursion is a promising approach to neural routing >

Lu: I think it sets a clear direction for how we should think about using recurrent networks in these scenarios >

Meng: From an engineering standpoint, the idea of inference-time depth scaling is still something we need to figure out how to make practical and reliable at scale, Meng would say.

Conclusion: Tom: I think the most exciting thing here is that the ability of this model to handle dynamic instances because it already runs zero-shot past its training conditions >

Jane: That means a single model with a decoder could solve dynamic problems end-to-end, which is a huge implication for real-world routing systems >

Lu: It also shows that latent recursion is a promising approach to neural routing, and we should be paying attention to how this concept evolves >

Meng: I still think we need more engineering on the sparse reinforcement learning signal before it becomes something you can actually ship reliably in production, Meng would say.

Tom: That’s the balance we have right now: a small latent-recursive model that shows real promise for complex routing problems >

Jane: The paper is RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem, and it’s definitely something worth following as we look ahead >

Vladimir Kirill Bickov, Neil Yorke-Smith

Delft University of Technology

cs.LG, cs.NE, math.OC

Submitted: 2026-10-10

Updated: 2026-10-10

Comments: Accepted to the NeurIPS 2026 MLxOR workshop. Paper contains 6 pages (4 main text, 1 references, 1 appendix); 1 figure and 3 tables

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

The gist: The gist: RELAGRAM introduces Recursive Latent Graph Model for graph combinatorial optimization, demonstrating that latent recursion is a promising approach to neural routing by encoding capacitated

Key concepts

Edge Tokens: The CVRP instance is encoded into discrete 'edge tokens,' which represent potential movements between locations. These tokens serve as the input units for the model, allowing it to process the entire graph structure as a sequence of potential edges rather than just nodes.
Compact Transformer Recurrent Update: This is a transformer network that processes the edge tokens sequentially. It uses two internal states ('answer state y' and 'workspace z') that are updated at each step using a specific recursive formula. This allows the model to maintain context across different depths of the search.
Latent Recursion: This is the core mechanism where the model updates its internal representations based on previous states in a recursive manner. The state update formula dictates how information flows from one step to the next, enabling deep, structured reasoning about finding optimal routes without propagating gradients through the entire chain.
Reinforcement Learning with Self-Imitation: The learning objective combines standard reinforcement learning (favoring shorter routes) with self-imitation. The model also uses cross-entropy loss to pull unmasked heatmaps toward the shortest sampled route, encouraging it to learn solutions that resemble high-quality examples.

Summary

The gist: RELAGRAM introduces Recursive Latent Graph Model for graph combinatorial optimization, demonstrating that latent recursion is a promising approach to neural routing by encoding capacitated vehicle routing problem instances as edge tokens and using a compact transformer recurrently updating latent representations.

RELAGRAM Architecture

RELAGRAM encodes a CVRP instance as edge tokens and uses a compact transformer recurrently updates the latent representations of these tokens. The model maintains two states, the answer state y and workspace z, which are updated recursively at each depth using the formula zt = Fθ(zt−1 + yt−1 + x), yt = Fθ(yt−1 + zt). A linear head maps yt,e to Ht,ij, the score of moving from i to j. Edges absent from the sparse encoding receive a logit of −10, providing a fallback when every encoded move is masked.

Learning and Self-Imitation

The model learns through an objective that combines reinforcement learning with self-imitation. The loss function is defined as Lt = −(Rt,s − R¯t) log πΘ(τt,s Ht) + λSI Ledge(Ht, τ elite t). The REINFORCE favours routes shorter than the same-instance mean. Furthermore, the Self-imitation pulls the unmasked heatmap toward the shortest sampled route τ elite t using cross-entropy loss. Every recursion depth receives one optimizer update, but latent states are detached between steps, so gradients never propagate down the recursive chain.

Experimental Results on CVRP Instances

On CVRP-100 instances, the 0.53M-parameter RELAGRAM achieves gaps to a PyVRP reference of 13.4%, 9.8%, and 8.3% under greedy decoding, eightfold symmetry augmentation, and 256-candidate search, respectively. When trained only on CVRP-100, RELAGRAM generalizes zero-shot to CVRP-500 and CVRP-1000, achieving gaps of 15.6% and 21.7% under 256-candidate search. On CVRP-100, the Combined256 uses symmetry, noise, and starts yields a gap of 8.30%.

Comparison with Baselines and Scaling

When compared to DeepACO after training for 40,000 optimizer updates, RELAGRAM does not yet achieve solution quality competitive with DeepACO. However, RELAGRAM nevertheless provides an additional test-time scaling axis: greater depth can improve solution quality without retraining. The best observed gap beyond depth four improves on CVRP-100, CVRP-500, and CVRP-1000 at depths six, eleven, and ten, respectively. The model's recursive step is cheaper at every size but its cost rises on the larger transferred instances.

Conclusion

RELAGRAM shows that a small latent-recursive model successfully learns to route. The work serves as a proof of concept for applying latent recursion to graph combinatorial optimization. The authors hypothesize that an important limitation is the sparse RL signal, which needs further engineering for latent recursion. The recursive nature of RELAGRAM may be very useful for dynamic problems. The loop already runs zero-shot past the conditions it was trained under; if it handles an updated instance as well as extra depth, a single model with a decoder could solve such problems end-to-end. The paper concludes by noting that the matched greedy comparison finds no significant advantage from recursion. The model's performance suggests that latent recursion is a promising approach to neural routing. The paper was supported by the EFFILOAT project under the MOOI programme, funded by the Netherlands Enterprise Agency (RVO). The work was presented at the 40th Conference on Neural Information Processing Systems (NeurIPS 2026). Workshop: Second Workshop on ML×OR. The paper is available as arXiv:2610.15106v1 [cs.LG] 10 Oct 2026. The authors acknowledge the anonymous reviewers of the NeurIPS’26 MLxOR workshop. The work is supported by funding from the Netherlands Enterprise Agency (RVO). The paper references several key works including Attention, learn to solve routing problems! and DeepACO: Neural-enhanced ant systems for combinatorial optimization. The paper also references the work of PyVRP: A high-performance VRP solver package. The paper was published in the INFORMS Journal on Computing, 36(4):943–955, 2024. The paper references the work of DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. The authors cite Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. The paper also cites Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! and Noam Shazeer. GLU variants improve transformer. The paper also references the work of Biao Zhang and Rico Sennrich. Root mean square layer normalization. The paper also references Alexia Jolicoeur-Martineau. Less is more: Recursive reasoning with tiny networks and Jonathan Pirnay and Dominik G. Grimm. Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. The paper also references Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. The paper cites the work of Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! and DeepACO: Neural-enhanced ant systems for combinatorial optimization. The paper cites the work of PyVRP: A high-performance VRP solver package. The paper also references the work of DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. The paper cites the work of DeepACO: Neural-enhanced ant systems for combinatorial optimization.

Improvements for AI systems

Bold header: Latent Recursion for Dynamic Problem Solving

The system can handle an updated instance as well as extra depth by recurrently processing the last latent state and the updated problem, allowing a single model with a decoder to solve dynamic problems end-to-end.

Bold header: Inference-Time Depth Scaling

The model can improve beyond its trained depth, achieving the best greedy gap of 28.45% at depth ten — six stages deeper than seen during training on CVRP-1000, suggesting promising inference-time depth scaling.

Bold header: Enhanced Route Quality via Self-Imitation

By tuning the self-imitation weight, specifically finding that λSI = 0.3 gives the strongest greedy result, the system can be optimized to favor routes that are not only short but also better aligned with learned edge representations.

Bold header: Robust Scaling Across Problem Sizes

The model demonstrates strong generalization, achieving gaps of 15.64% and 21.65% on CVRP-500 and CVRP-1000 under 256-candidate decoding without retraining, indicating improved performance on larger instances.

Abstract

Latent recursion repeatedly processes internal representations through the same neural network. Recent work has shown this approach to be effective on structured reasoning tasks such as Sudoku and maze solving. However, whether latent recursion can support neural routing remains unclear. We introduce RELAGRAM (Recursive Latent Graph Model), a novel approach that brings latent recursion to graph combinatorial optimization. RELAGRAM encodes a capacitated vehicle routing problem (CVRP) instance as edge tokens; a compact transformer recurrently updates the latent representations of these tokens. An output head maps the answer state to an edge heatmap, from which an autoregressive decoder constructs a feasible solution. On CVRP-100 instances, the 0.53M-parameter RELAGRAM achieves gaps to a PyVRP reference of 13.4%, 9.8%, and 8.3% under greedy decoding, eightfold symmetry augmentation, and 256-candidate search, respectively. Trained only on CVRP-100, RELAGRAM generalizes zero-shot to CVRP-500 and CVRP-1000, achieving gaps of 15.6% and 21.7% under 256-candidate search. Together, these results demonstrate that latent recursion is a promising approach to neural routing.