PRIME: Efficient Algorithm for Token Graph Routing Problem

本論文は、暗号資産取引所における非線形なエッジ重みを持つ大規模グラフ上の経路探索問題(TGRP)に対して、剪定グラフ探索と適応符号勾配法(ASGM)を用いた二段階アルゴリズム「PRIME」を提案し、実世界のデータにおいて既存の Uniswap ルーティングアルゴリズムを上回る実行価格と計算効率を実現したことを示しています。

Haotian Xu, Yuqing Zhu, Yuming Huang, Jing Tang

公開日 Tue, 10 Ma
📖 1 分で読めます☕ さくっと読める

Each language version is independently generated for its own context, not a direct translation.

🍽️ 料理の例え:「最高の味」を見つける旅

想像してください。あなたが「WETH(イーサリアム)」という食材を持っていて、それを「USDC(ドルに連動した通貨)」という料理に変えたいとします。

しかし、この世界には**「Uniswap」「SushiSwap」**など、無数の「レストラン(流動性プール)」があります。

  • 小さなレストランは、少量の注文なら安くて美味しいですが、大量に注文すると「材料が足りなくなる」ため、値上がりしてしまいます(これを価格スリッページと呼びます)。
  • 大きなレストランは大量注文に強いですが、遠い場所にあるかもしれません。

従来の方法(Uniswap の SOR など)の問題点:
これまでのシステムは、「一番大きなレストラン」や「一番近いルート」をとりあえず選んで、そこに全部の食材を注文しようとしていました。

  • 問題 1: 一度に大量注文すると、そのレストランの価格が高騰してしまい、結果的に損をします。
  • 問題 2: 「A 店と B 店を組み合わせればもっと安くなる」というような、複雑で賢いルートを見つける計算に時間がかかりすぎます。
  • 問題 3: 食材の価格が「1 億円の金」と「0.0001 円の犬の絵文字」のように桁違いに違うため、計算が混乱して失敗することがあります。

🚀 新アルゴリズム「PRIME」の仕組み

この論文が提案するPRIMEは、そんな悩みを解決する「天才的な料理コーディネーター」のようなものです。

ステップ 1:地図を整理する(グラフの事前処理)

PRIME はまず、無数のレストランがある巨大な地図を整理します。

  • コア(中心): 主要な食材(WETH, USDC など)がつながる「主要な幹線道路」だけを残します。
  • ショートカット(近道): 主要な道にはないけど、実はすごくお得な「裏通りの近道」をメモ帳(インデックス)に記録しておきます。
    これにより、毎回最初から全ルートを探す必要がなくなり、「必要な場所だけ」を素早く探せるようになります。

ステップ 2:賢いルート探し(経路探索)

「全部の食材を 1 つの店に持っていく」のではなく、**「少量ずつ複数の店に分けて注文する」のがコツです。
PRIME は、
「今、どの店が最も安く買えるか?」**を常にチェックしながら、複数のルートを組み合わせていきます。

  • もしあるルートが「少しだけ高い」なら、そのルートは探さずに切り捨てます(剪定)。
  • これにより、無駄な計算を省き、「最もお得なルート」だけを瞬時に見つけ出します。

ステップ 3:完璧な配分(最適化)

見つけた複数のルートに、食材を**「どれくらい配分すればいいか」**を計算します。
ここが PRIME の最大の特徴です。

  • 従来の計算方法は、価格の桁が違いすぎると(1 億円 vs 0.0001 円)、計算が破綻したり、非常に時間がかかったりしました。
  • PRIME は**「ASGM(適応的符号勾配法)」**という新しい計算テクニックを使います。
    • 例え: 「値が安い店から値が高い店へ、食材を少しずつ移動させる」作業を、「数字の大きさ」を気にせず、「安い・高い」という「方向」だけを見て行います。
    • これにより、どんなに価格の差が激しくても、計算が安定して、かつ非常に速く「最もお得な配分」にたどり着きます。

🏆 PRIME がすごい点(結果)

実験結果(実際のイーサリアムのデータ)によると、PRIME は以下の点で業界標準(Uniswap の SOR)を大きく凌駕しました。

  1. よりお得な価格:
    • 大きな取引(1,000 WETH など)では、**8.42 bp(0.0842%)**も得する価格になりました。
    • 小さな取引でも、見落としがちだった「裏通りの近道」を見つけるため、より良い価格が見つかります。
  2. 圧倒的な速さ:
    • 計算時間が最大 96.7% 削減されました。
    • 従来の方法が 1 秒かかる計算が、PRIME では 0.03 秒で終わります。これは、高速で動く暗号資産市場において「生殺与奪を握る」ほどの速度です。
  3. 実用性:
    • このアルゴリズムはすでに、実際のヘッジファンド(投資会社)の現場で使われており、安定して動いています。

💡 まとめ

この論文が伝えているのは、**「暗号資産の交換は、単に『一番安い店』を探すだけでなく、『複数の店を賢く使い分け、食材を最適に配分する』ことが重要だ」**ということです。

PRIME は、**「巨大な地図を整理し」「賢く近道を見つけ」「価格の桁違いを無視して瞬時に計算する」という 3 つの魔法を使い、ユーザーにとって「より安く、より速く」**取引できる未来を実現しました。

まるで、**「世界中のスーパーマーケットの在庫と価格を瞬時に把握し、あなたのために『最も安く、最も美味しい買い物リスト』を 0.1 秒で作ってくれる AI ショッピング助手」**のような存在です。