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

AI summary

Overview

• Research area: Machine learning for combinatorial optimization, specifically neural methods for the Capacitated Vehicle Routing Problem (CVRP), combining latent recursive reasoning with reinforcement learning.
• Technical level: Intermediate. The core idea is explained accessibly, but the paper assumes familiarity with reinforcement learning (REINFORCE), graph encodings and routing benchmarks.
• Scope: A proof-of-concept study showing that a small (0.53M-parameter) latent-recursive transformer can learn to produce CVRP solutions from edge heatmaps, transfer zero-shot to much larger instances, and improve with extra recursion depth at inference time.

What This Paper Is About

Neural routers typically build a route step by step or repeatedly refine a complete solution, which throws away intermediate reasoning stored only in the model's internal state. This paper asks whether "latent recursion" — repeatedly running the same small network over an internal state instead of over a candidate solution — can work for graph combinatorial optimization, using CVRP as the testbed. The goal is to see whether such a model can learn to route at all, how far it generalizes beyond its training size, and how it compares with an established neural baseline, DeepACO.

Key Contributions

1. A new architecture, RELAGRAM, that applies latent recursion to routing: each CVRP instance is encoded as sparse directed edge tokens, and a shared two-block transformer alternately updates a workspace state and an answer state across recursion depths.
2. A heatmap-to-route pipeline in which a linear head maps the answer state to edge logits, and an autoregressive decoder with masking for visited customers and remaining capacity turns those logits into a feasible route.
3. A training scheme combining REINFORCE (with a same-instance mean baseline over 16 sampled routes) and a self-imitation auxiliary loss (cross-entropy toward the shortest sampled route, weight λ_SI = 0.3), with latent states detached between depths so gradients never propagate down the recursive chain.
4. Empirical evidence of depth and size scaling: zero-shot transfer from CVRP-100 training to CVRP-500 and CVRP-1000, plus improvements from running the recursion beyond the trained depth of four, together with a matched single-pass control comparison.

Main Findings

• Gaps on CVRP-100: With 160,000 optimizer updates, RELAGRAM reaches gaps to the PyVRP reference of 13.40% (greedy), 9.77% (eightfold symmetry augmentation) and 8.30% (256-candidate search). The abstract rounds these to 13.4%, 9.8% and 8.3%.
• Zero-shot transfer: Trained only on CVRP-100, the model achieves gaps of 15.64% on CVRP-500 and 21.65% on CVRP-1000 under 256-candidate decoding, without retraining.
• Test-time scaling with candidates: Expanding one greedy decode to 256 candidates improves the gap by 5.10 points on CVRP-100 and 8.26 points on CVRP-1000 (29.91% to 21.65% on the latter).
• Depth scaling beyond training: RELAGRAM keeps improving past its trained depth of four. The best observed gaps beyond depth four improve on the depth-four gap by 0.05, 0.74 and 1.45 points on CVRP-100, CVRP-500 and CVRP-1000, at depths six, eleven and ten respectively. On CVRP-1000 the best greedy gap is 28.45% at depth ten, six stages deeper than training.
• Progress is non-monotonic: A later recursion stage can worsen the gap before producing a better route, so the deepest output is not always the strongest (for example, CVRP-100 greedy rises from 13.35% at depth six to 15.49% at depth sixteen).
• Depth gains are significant only at larger sizes: The paired t-test against depth four gives p = 0.822 on CVRP-100, p = 0.015 on CVRP-500 and p < 0.001 on CVRP-1000.
• DeepACO is generally stronger: At matched 40,000 optimizer updates, DeepACO wins eight of nine size–decoder regimes, including 3.94-point and 3.49-point lower gaps on CVRP-100 under greedy and 256-candidate decoding, and a 9.33-point lower greedy gap on CVRP-1000. RELAGRAM is ahead on CVRP-500 under 256-candidate decoding (17.11% versus 17.38% at 40k; 15.64% versus 17.38% at 160k).
• The comparison is not compute-matched: The models use similar numbers of training trajectories (9.60M for DeepACO, 10.24M for RELAGRAM), but DeepACO sees twice as many base graphs and takes 1.87 times longer to train.
• No significant advantage over a single-pass control: A matched direct model with the same 0.526M-parameter transformer achieves slightly lower greedy gaps at 10k updates (18.467% versus 18.886%, p = 0.226) and 20k updates (17.596% versus 17.857%, p = 0.406); neither difference is statistically significant, so the paper reports no evidence of a recursion advantage in that setting.
• Recursive steps are cheaper than decoding: One recursive step takes 2.60, 36.32 and 131.40 ms for n = 100, 500 and 1000, versus 36.39, 169.04 and 331.91 ms for one greedy decode.
• Self-imitation weight matters: On CVRP-32 with a 1.707M-parameter model at 20k batches, λ_SI = 0.3 gives the best greedy gap (7.577%), and all non-zero weights beat λ_SI = 0 (12.124% greedy, 7.237% Aug8).
• Augmentation beats extra depth at equal decoding count, but is not latency-matched: Aug8 gaps are 9.77%, 17.61% and 24.36%, versus 13.35%, 21.81% and 28.45% at the best tested depths on CVRP-100, CVRP-500 and CVRP-1000.

Methodology in Plain English

Each CVRP instance is turned into a set of edge tokens rather than a set of node tokens: every customer is linked to the depot and to its k − 1 = 20 nearest neighbours, the depot is linked to every customer, and opposite directions are encoded separately. Each edge carries nine features (coordinates, demands and depot indicators of its two endpoints, plus their Euclidean distance), projected to a d-dimensional vector.

The model keeps two d-dimensional states — an answer state y and a workspace state z — both initialized as fixed random vectors. At each recursion depth, the same small two-block transformer first updates z using the input plus both states, then updates y using y plus the refreshed z. A linear head converts the answer state into scores for each edge; edges outside the sparse encoding receive a logit of −10 as a fallback. Routes are decoded from this heatmap one vertex at a time, starting at the depot, with visited and capacity-infeasible customers masked out.

Training uses no optimal labels. At every depth the model samples 16 routes, scores them by cost, and applies REINFORCE with the mean reward of those same 16 routes as the baseline. An auxiliary cross-entropy term additionally pushes the heatmap toward the single shortest sampled route. Every depth receives one optimizer update, after which the latent states are detached, so the model learns successive corrections without backpropagating through the recursion chain. Training runs on CVRP-100 in the RL4CO CVRPEnv, with a batch size of 16 and 16 sampled routes per instance; across four recursion depths that yields 1,024 routes per batch. Two budgets are used: 40,000 updates (2.98 hours) for the DeepACO comparison and 160,000 updates (11.94 hours) for the main results, on a 10 GB A100 GPU slice. Evaluation covers three decoders — greedy, eightfold symmetry augmentation, and a 256-candidate combination of symmetry, per-step latent noise and forced different starts — on 256 fixed instances per size, with PyVRP 0.13.4 references under per-instance time limits of 5 s at n = 100, 20 s at n = 500 and 40 s at n = 1000.

Why This Matters

The paper tests whether an idea that works on supervised reasoning puzzles (Sudoku, mazes, ARC-AGI) transfers to reinforcement learning for graph combinatorial optimization. The answer is a qualified yes: a very small model learns to route, transfers without retraining to instances ten times larger, and gains from extra inference-time depth. It also documents a negative result — no significant advantage over a matched single-pass model under greedy decoding — which is useful for anyone deciding whether to invest in recursive architectures.

Real-world applications:

• Logistics and last-mile delivery: routing fleets under vehicle capacity constraints, where a single trained model could be redeployed on depots and customer sets of varying size.
• Dynamic dispatch and re-optimization: the authors suggest the recurrent loop could process an updated problem together with the last latent state, which suits settings where orders arrive or change during the day.
• Field service and maintenance scheduling: technicians or service vehicles with capacity limits and many stops.
• Warehouse and internal transport routing: picker or automated guided vehicle routing where instance sizes vary widely.

Industry relevance: the small parameter count (0.53M) and the ability to trade more inference compute for better solutions without retraining point toward deployable models that adapt at test time rather than requiring training runs per instance size. The gaps reported (8.30% to 21.65% depending on size and decoder) are not yet competitive with the DeepACO baseline, so the paper positions the work as a proof of concept rather than a production-ready solver.

Future Directions

• Richer learning signal: the authors hypothesize that the sparse RL signal is an important limitation, since the y and z states receive only indirect RL signal; better credit assignment for latent recursion is an open engineering problem.
• Closing the gap to DeepACO: RELAGRAM's candidate scaling weakens less with instance size while DeepACO's weakens more, which raises the question of whether longer training or more recursion depths could make RELAGRAM competitive at large sizes.
• Depth as a controllable compute axis: best depth varied by instance size (six, eleven and ten on CVRP-100, CVRP-500 and CVRP-1000), and progress is non-monotonic, so how to select depth per instance without evaluation is unresolved.
• Dynamic and changing problems: the authors propose testing whether the loop can handle an updated instance as well as extra depth, enabling a single model plus decoder to solve dynamic problems end to end.

Target Audience

Graduate students and researchers in machine learning for combinatorial optimization, reinforcement learning, and neural combinatorial solvers who want a compact, clearly scoped case study of latent recursion applied to routing. It is also useful for practitioners evaluating whether recursive or iterative neural architectures are worth adopting over simpler single-pass models, and for readers familiar with Tiny Recursive Models, DIFUSCO, the Attention Model or DeepACO who want to see how those ideas combine.

Authors’ 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.