RELAGRAM: Recursive Latent Graph Model Revolutionizes Vehicle Routing Problem Solving

Can Latent Recursion Be Used for Neural Routing?

Latent Recursion is a technique that lets neural networks repeatedly process internal representations, and it has already shown significant results on structured reasoning tasks like Sudoku and mazes. But a key question remains unresolved: Can this recursive mechanism support Neural Routing?

A recent research effort gives an affirmative answer. The researchers propose RELAGRAM (Recursive Latent Graph Model), the first to introduce latent recursion into the field of graph combinatorial optimization, specifically targeting the Capacitated Vehicle Routing Problem (CVRP).

Technical Core: Edge Token Encoding and Recursive Transformation

RELAGRAM's design approach differs from traditional neural combinatorial optimization methods, with its core being the encoding of CVRP instances as Edge Tokens.

Specifically, the model uses a small Transformer network to repeatedly update the latent representations of these edge tokens. Each recursive iteration reuses the same set of network parameters, progressively refining its understanding of the problem structure. After multiple rounds of recursion, an Output Head maps the final answer state into an Edge Heatmap, which is then used by an autoregressive decoder to construct a feasible solution satisfying capacity constraints.

This "encode–recurse–decode" pipeline allows the model to complete complex combinatorial decisions within a compact parameter space.

Edge Tokens are a representation method in graph neural networks that uses "edges" as the basic processing unit. In typical node-centric graph networks, each node corresponds to a vector, and edge information serves as a channel for message passing. Edge token encoding, by contrast, directly maps each edge (i, j) into an independent feature vector, which can incorporate attributes such as endpoint coordinates, demands, distances, and capacity constraints. For CVRP, a solution is essentially a tour formed by a set of selected edges, so an edge-as-token representation naturally aligns with the decision space: the model only needs to output a probability of being selected for each edge (i.e., the edge heatmap), and then decode the route accordingly. This design is in line with recent architectures such as Edge Transformer and Anisotropic Graph Neural Network. Its advantage is that it avoids the information loss caused by indirectly inferring edge decisions from node representations, and it also makes the goal of recursive refinement more focused on the core question of "whether an edge should appear in the solution."

Performance: Small Models Can Also Be Competitive

RELAGRAM has only 0.53M parameters, making it extremely lightweight among deep learning models, but its performance on the CVRP-100 benchmark is noteworthy.

Using PyVRP as the reference baseline, RELAGRAM's gaps under different decoding strategies are as follows:

• Greedy decoding: 13.4% gap
• Eight-fold symmetry augmentation: gap reduced to 9.8%
• 256-candidate search: gap further reduced to 8.3%

From greedy decoding to candidate search, performance improves by more than 5 percentage points, indicating that the edge heatmap produced by latent recursion contains exploitable probabilistic information that can be further unlocked through search strategies.

PyVRP is a widely used open-source solver in the current vehicle routing problem field. It is based on metaheuristics such as HGS (Hybrid Genetic Search) and achieves near-optimal solution quality on multiple CVRP benchmarks, so it is often used as a strong baseline for neural combinatorial optimization methods. The so-called "gap of X%" usually refers to the relative gap between the model solution and the PyVRP solution (or the known optimal solution), calculated as (model cost − baseline cost) / baseline cost. It should be noted that neural methods often achieve this gap with a single forward inference or limited candidate search, whereas PyVRP usually requires tens of seconds or even longer to solve, so the speed-quality trade-offs of the two are not equivalent. Greedy decoding means directly selecting the edge with the highest probability at each step without backtracking; eight-fold symmetry augmentation exploits the property that CVRP solutions are equivalent under eight symmetric transformations such as rotation and flipping, performing multiple forward passes on the same instance and merging the results; candidate search samples multiple candidate routes from the edge heatmap and selects the best by cost. The stronger the decoding strategy, the more it can exploit the probabilistic information contained in the heatmap.

Zero-Shot Generalization: Cross-Scale Transfer from 100 to 1000

A common challenge for combinatorial optimization models is generalization ability—can a model trained on a fixed scale handle larger-scale problems?

RELAGRAM stands out on this point. The model is trained only on CVRP-100, yet it can generalize zero-shot to CVRP-500 and CVRP-1000:

• CVRP-500: 15.6% gap under 256-candidate search
• CVRP-1000: 21.7% gap under 256-candidate search

As the problem scale expands from 100 to 1000, the performance gap gradually increases from 8.3% to 21.7%, with the degradation remaining within an acceptable range. This cross-scale generalization ability indicates that what latent recursion learns is not memorization of a specific problem scale, but some transferable structured reasoning pattern.

Zero-shot Generalization in the context of combinatorial optimization refers to a model being trained at one scale (e.g., 100 nodes) and then directly inferring on larger-scale instances (e.g., 500 or 1000 nodes) without any fine-tuning or retraining. This stands in sharp contrast to traditional neural combinatorial optimization methods—many models experience sharp performance drops once the scale changes after training on small scales, because the model may implicitly rely on fixed-dimensional inputs or statistical regularities specific to a certain scale. RELAGRAM's ability to achieve cross-scale transfer lies mainly in the fact that its edge token encoding is not tied to the total number of nodes, and the parameter count of the recursive Transformer is also independent of instance scale, allowing structured reasoning patterns (such as "prioritize serving nodes that are close and have high demand") to be reused across scales. It should be noted that as scale increases, the candidate search space expands, and the structural information that a single recursion can cover is relatively diluted, which is precisely the main reason the gap monotonically increases from 8.3% to 21.7%.

Why Is Latent Recursion Suitable for Routing Problems?

The essence of routing problems is sequential decision-making on discrete graph structures, where each step's choice affects subsequent feasibility. RELAGRAM's latent recursion mechanism fits this characteristic well:

Repeated refinement—each recursive iteration updates the representation of the current problem state, similar to how humans repeatedly examine a map and adjust their plan when solving a route problem.

Parameter sharing—the same Transformer network is called repeatedly, allowing the model to perform multi-step reasoning under limited parameter count and avoiding the parameter explosion caused by stacking deep networks.

Structure awareness—the edge-as-token encoding method naturally preserves the graph's topological information, and the edge heatmap directly corresponds to the decision signal of "which edges should be selected."

The researchers conclude that these results collectively demonstrate that latent recursion is a promising technical route for neural routing. For vehicle routing applications that require real-time solving or deployment in resource-constrained environments, a model with 0.53M parameters supporting zero-shot cross-scale generalization offers a new option distinct from traditional heuristic algorithms and large neural solvers.

Limitations and Outlook

RELAGRAM's current 21.7% gap on CVRP-1000 is still relatively large, leaving a distance to practical deployment. Increasing the number of candidate searches from eight-fold symmetry augmentation to 256 candidates yields clear gains, but computational overhead also rises accordingly. How to strike a balance between inference efficiency and solution quality is a question that subsequent research needs to answer.

In addition, this work has so far only been validated on CVRP. Whether latent recursion can be equally effective on more complex routing variants such as VRPTW with time windows and pickup-and-delivery problems (PDP) remains to be further explored.

One-line Summary

RELAGRAM uses latent recursion and edge token encoding to solve CVRP, and with only 0.53M parameters it can generalize zero-shot to thousand-node scales.

Paragraph Summary

The article introduces a new work, RELAGRAM, that brings Latent Recursion into graph combinatorial optimization, aiming to answer the question of whether latent recursion can support neural routing. RELAGRAM encodes CVRP instances as edge tokens, repeatedly updates their latent representations with a small Transformer, and then generates an edge heatmap through an output head and autoregressively decodes a feasible solution. The model has only 0.53M parameters. On CVRP-100, with PyVRP as the baseline, the gaps under greedy decoding, eight-fold symmetry augmentation, and 256-candidate search are 13.4%, 9.8%, and 8.3%, respectively. It is trained only on CVRP-100 but can generalize zero-shot to CVRP-500 and CVRP-1000, with gaps of 15.6% and 21.7%, respectively. The article argues that latent recursion fits routing problems because of repeated refinement, parameter sharing, and structure awareness, but large-scale performance and inference efficiency remain unresolved challenges.