RELAGRAM
A neural network model that applies a latent recursion mechanism to graph-based combinatorial optimization. Centered on edge-token encoding, it repeatedly updates latent representations through recursion to produce edge heatmaps, and is used to solve the Capacitated Vehicle Routing Problem (CVRP).
Timeline (last 90 days)
RELAGRAM (Recursive Latent Graph Model) is the first to introduce latent recursion into the field of graph combinatorial optimization, specifically targeting the capacitated vehicle routing problem (CVRP).
RELAGRAM encodes CVRP instances as edge tokens (Edge Tokens) and uses a small Transformer network to repeatedly update the latent representations of the edge tokens.
RELAGRAM has only 0.53M parameters.
On the CVRP-100 benchmark, RELAGRAM's gaps relative to PyVRP are: 13.4% for greedy decoding, 9.8% for eight-fold symmetry augmentation, and 8.3% for 256-candidate search.
RELAGRAM is trained only on CVRP-100, yet generalizes zero-shot to CVRP-500 (15.6% gap under 256-candidate search) and CVRP-1000 (21.7% gap under 256-candidate search).
RELAGRAM's recursive iterations reuse the same set of network parameters, and the output head maps the final answer state to an edge heatmap, which is then used by an autoregressive decoder to construct a feasible solution satisfying capacity constraints.
RELAGRAM's current 21.7% gap on CVRP-1000 is still relatively large, and it is still some distance from practical deployment.
This work has so far been validated only on CVRP, and whether latent recursion can similarly handle more complex routing variants such as VRPTW and PDP remains to be explored.
RELAGRAM's edge token encoding is not tied to the total number of nodes, and the parameter count of the recursive Transformer is independent of instance scale, enabling it to achieve cross-scale transfer.
All Facts (9)
RELAGRAM (Recursive Latent Graph Model) is the first to introduce latent recursion into the field of graph combinatorial optimization, specifically targeting the capacitated vehicle routing problem (CVRP).
50%UnverifiedRELAGRAM encodes CVRP instances as edge tokens (Edge Tokens) and uses a small Transformer network to repeatedly update the latent representations of the edge tokens.
50%UnverifiedRELAGRAM has only 0.53M parameters.
50%UnverifiedOn the CVRP-100 benchmark, RELAGRAM's gaps relative to PyVRP are: 13.4% for greedy decoding, 9.8% for eight-fold symmetry augmentation, and 8.3% for 256-candidate search.
50%UnverifiedRELAGRAM is trained only on CVRP-100, yet generalizes zero-shot to CVRP-500 (15.6% gap under 256-candidate search) and CVRP-1000 (21.7% gap under 256-candidate search).
50%UnverifiedRELAGRAM's recursive iterations reuse the same set of network parameters, and the output head maps the final answer state to an edge heatmap, which is then used by an autoregressive decoder to construct a feasible solution satisfying capacity constraints.
50%UnverifiedRELAGRAM's current 21.7% gap on CVRP-1000 is still relatively large, and it is still some distance from practical deployment.
50%UnverifiedThis work has so far been validated only on CVRP, and whether latent recursion can similarly handle more complex routing variants such as VRPTW and PDP remains to be explored.
50%UnverifiedRELAGRAM's edge token encoding is not tied to the total number of nodes, and the parameter count of the recursive Transformer is independent of instance scale, enabling it to achieve cross-scale transfer.
50%