PRIME: Efficient Algorithm for Token Graph Routing Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912955442921472 |
|---|---|
| author | Xu, Haotian Zhu, Yuqing Huang, Yuming Tang, Jing |
| author_facet | Xu, Haotian Zhu, Yuqing Huang, Yuming Tang, Jing |
| contents | Optimizing asset exchanges on blockchain-driven platforms poses a novel and challenging graph query optimization problem. In this model, assets represent vertices and exchanges form edges, recasting the graph query task as a routing problem over a large-scale, dynamic graph. However, the existing solutions fail to solve the problem efficiently due to the non-linear nature of the edge weights defined by a concave swap function. To address the challenge, we propose PRIME, a two-stage iterative graph algorithm designed for the Token Graph Routing Problem (TGRP). The first stage employs a pruned graph search to efficiently identify a set of high-potential routing paths. The second stage formulates the allocation task as a strongly convex optimization problem, which we solve using our novel Adaptive Sign Gradient Method (ASGM) with a linear convergence rate. Extensive experiments on real-world Ethereum data confirm PRIME's advantages over industry baselines. PRIME consistently outperforms the widely-used Uniswap routing algorithm, achieving up to 8.42 basis points (bps) better execution prices on large trades while reducing computation up to 96.7%. The practicality of PRIME is further validated by its deployment in hedge fund production environments, demonstrating its viability as a scalable graph query processing solution for high-frequency decentralized markets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_08337 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | PRIME: Efficient Algorithm for Token Graph Routing Problem Xu, Haotian Zhu, Yuqing Huang, Yuming Tang, Jing Databases 90C25, 90C35, 91G15 F.2.2; G.1.6; H.2.4 Optimizing asset exchanges on blockchain-driven platforms poses a novel and challenging graph query optimization problem. In this model, assets represent vertices and exchanges form edges, recasting the graph query task as a routing problem over a large-scale, dynamic graph. However, the existing solutions fail to solve the problem efficiently due to the non-linear nature of the edge weights defined by a concave swap function. To address the challenge, we propose PRIME, a two-stage iterative graph algorithm designed for the Token Graph Routing Problem (TGRP). The first stage employs a pruned graph search to efficiently identify a set of high-potential routing paths. The second stage formulates the allocation task as a strongly convex optimization problem, which we solve using our novel Adaptive Sign Gradient Method (ASGM) with a linear convergence rate. Extensive experiments on real-world Ethereum data confirm PRIME's advantages over industry baselines. PRIME consistently outperforms the widely-used Uniswap routing algorithm, achieving up to 8.42 basis points (bps) better execution prices on large trades while reducing computation up to 96.7%. The practicality of PRIME is further validated by its deployment in hedge fund production environments, demonstrating its viability as a scalable graph query processing solution for high-frequency decentralized markets. |
| title | PRIME: Efficient Algorithm for Token Graph Routing Problem |
| topic | Databases 90C25, 90C35, 91G15 F.2.2; G.1.6; H.2.4 |
| url | https://arxiv.org/abs/2603.08337 |