# LEANN: A Low-Storage Overhead Vector Index > [!info] Talk metadata > - **会議:** [[MLSys2026]] Day 2 (May 19 / Tue)、Grand Ballroom 1、Best Paper Session（08:45 PDT 開始、第2発表、Best Paper 受賞） > - **登壇者:** Yichuan Wang（UC Berkeley SkyLab, second-year PhD student, advised by Ion Stoica & Joseph Gonzalez） > - **URL:** https://mlsys.org/virtual/2026/session/3659 > - **関連研究:** GitHub `https://github.com/yichuan-w/LEANN`、arXiv 2506.08276 > [!abstract] 概要（論文 PDF アブストラクト） > 埋め込みベースのベクトル検索は、推薦や RAG（Retrieval-Augmented Generation）など多くの重要なアプリケーションを支えている。これは効率的な検索を実現するためにベクトルインデックスに依存するが、こうしたインデックスは高次元埋め込みと大きなインデックスメタデータの保存を要し、総サイズは元データ（例: テキストチャンク）の数倍に達しうる。この高いストレージオーバーヘッドのため、個人デバイスや大規模データセットへのベクトル検索の展開は困難、あるいは非現実的になる。この課題に対し、本論文では LEANN を提案する。LEANN はストレージ効率の高いベクトル検索インデックスで、埋め込みを保存する代わりに**オンザフライで再計算**し、SOTA の近接グラフインデックスを検索精度を保ちつつ圧縮する。LEANN はストレージの一部（例: 元データの 5%）のみを用いて高品質なベクトル検索を実現し、ストレージ効率の高いインデックス構築・更新をサポートする。実世界のベンチマークにおいて、LEANN は従来インデックス比で**最大 50x** のインデックスサイズ削減を達成しつつ、RAG アプリケーションで SOTA 精度と同等のレイテンシを維持する。 > [!note] 出典に関する注記 > 公式論文タイトルは "LEANN: A Low-Storage **Overhead** Vector Index"（論文 PDF）。スライド表紙は "LEANN: A Low-Storage Vector Index" と "Overhead" を省略している。ノートでは論文タイトルを採用。 ## 背景・問題: ベクトルインデックスの「隠れたコスト」 - ベクトル検索は LLM/エージェント時代の中心。RAG・エージェントメモリ・検索エージェント/検索エンジン・コーディングエージェントのパイプラインで使われ、キーワードベース手法より高次元の意味的類似を自然に捉えられる（スライド「Vector Search is Central to the LLM and Agent Era」）。 - しかし大半のベクトルインデックスはレコメンド/大規模検索由来の「レイテンシ優先」設計を継承し、隠れたストレージコストを伴う。 - 具体例（スライド「Secret Cost」/ 論文 Table 1、76 GB テキストデータストア + Qwen3-4B + RTX 4090）: **76 GB の文書 → 約 200 GB のインデックスストレージ、270% のストレージオーバーヘッド**。これは現代のベクトルインデックスに一貫して見られる。 - 論文 Table 1 の内訳: HNSW のストレージ 188 GB（index metadata 15 GB + vectors 173 GB）。PQ は 20 GB だが downstream accuracy が 17.9%（HNSW/LEANN は 25.5%）に低下。BM25 は 18.3%。 - オーバーヘッドの分解（2 要因）: - **高次元埋め込みベクトル**を全チャンク/パッセージ分保存（スライド5）。 - HNSW（Hierarchical Navigable Small World）等の**複雑なグラフ構造**。entry vector から貪欲探索で最近傍へ navigate し、レイテンシを劇的に削るが、ストレージを爆発させる（"HNSW cuts latency, but blows up storage"、スライド6）。 - 目標: **すべてのもの・あらゆる場所でベクトル検索を可能にする**（"Enable Vector Search Over Everything"）。クラウドでは本番ログや DB エントリ等の非構造化データを全インデックス化したいが、3x〜5x の追加インデックス維持が高コストで実際には行われない（1 TB データに +5 TB は非現実的）。エッジ（ラップトップ等）では on-device ベクトル検索/RAG は不可能に近い。**主たる焦点は on-device（impossible → possible にする）**（スライド「Goal」、Main focus = on-device）。 ## 既存手法とその限界 - **DiskANN / Starling**: フル精度ベクトルをディスクへオフロードしメモリだけ削減 → メモリオーバーヘッドは減るが**ディスク容量を依然多く消費**（スライド「Existing Solution」）。 - **量子化（PQ / RabitQ）**: ベクトルをスパース/低精度化 → 信頼できる recall の再現が難しく**recall 精度が低下**。論文では PQ はベクトルを 5 GB にするのに約 35x 圧縮が必要で、高圧縮比では downstream 精度が BM25 以下まで劣化。 ## 機会: on-device RAG/エージェントの新たな観察 - **生成が E2E RAG レイテンシを支配**。スライド「RAG Latency Breakdown on RTX 4090」では Retrieval 0.05s（0.24%）に対し Generation 20.90s（99.8%）。推論モデル・長コンテキスト入力でさらに顕著。 - **on-device の QPS は高くない**（同時に 1 クエリ程度）。 - DB の **5-minute rule** の類比: アクセス頻度が低いデータは下位メモリ階層へオフロードしレイテンシ SLA を緩められる。 - → 機会: **レイテンシを増やすことで大幅なストレージ削減を解禁し "Index Everything!" する**（スライド11）。 ## 二つの洞察と設計（LEANN） - **洞察1**: HNSW のグラフ走査は**クエリ毎に少数のベクトルしか触れない** → ベクトルを保存せず**オンザフライ再計算**（"Don't save vectors → recompute them"）。 - **洞察2**: HNSW グラフ構造の多くが**冗長** → **グラフを枝刈り**（"Prune the graph"）。 - トレードオフ: わずかなレイテンシ増で大幅なストレージ削減（"Enable state-of-the-art RAG!"、スライド12）。 - システム全体像（スライド13「LEANN - Solution」、76 GB の Personal Data の例）: - **Fast HNSW Graph-Based Recomputation**（two-level search + batched execution）で事前計算埋め込みの保存を不要化、低レイテンシ維持。埋め込み 180 GB → **0 GB**（Smart Recomputation）。 - **High-Degree-Preserving Graph Pruning** でグラフの冗長を除きストレージ削減。グラフ構造 5 GB → **2 GB**（品質劣化最小）。 - 結果: iPhone/Mac 等で **2 秒未満で SOTA 精度に到達**。 ### 技術1: Two-level search - 全候補に対し**高速な近似評価**（PQ 埋め込みによる近似距離）を行い、最も有望な候補のみ**実際の再計算（exact）**を適用（スライド「two-level search」、詳細アルゴリズムは論文）。 ### 技術2: Dynamic Batching（GPU の batch effect） - 1 埋め込みの計算は複数並列計算と概ね同レイテンシ → **1 ホップ内・ホップ間のノードをバッチ化**して再計算しレイテンシ削減。 - スライド「Dynamic Batching」（RTX 4090）: Base=1.00 に対し Base+Two-level / +Batch の高速化は NQ 1.64/1.86、TriviaQA 1.42/1.57、GPQA 1.35/1.59、HotpotQA 1.19/2.02。**全技術合わせて最大 2x speedup**（HotpotQA で 2.02x）。 ### 技術3: High-Degree Preserving Graph Pruning - HNSW のグラフメタデータは依然大きい。観察: **ノード out-degree 分布とアクセスパターンが大きく歪んでいる**（高 degree ノードほど訪問頻度が高い。スライド「Graph Pruning」の (a) out-degree 分布 / (b) visit probability、最大 degree 60 付近で visit probability が突出）。 - 解決: 少数の人気ノードに高 out-coming edge を残し、大半のノードは out-coming edge を制約（他からの追加は許可）。 - 結果（スライド「Graph Pruning」の評価図）: LEANN は**グラフを 2x 圧縮しつつほぼロスレス**（Avg Degree 18 → 9）。同じ Avg Degree 9 で、recall 92% 時の再計算ノード数は LEANN が他手法より少なく、Small M に対し約 **5.76x**、Random Prune に対し約 **1.81x** 有利。degree 分布図でも **LEANN のみが高 degree ノードを保持**（Small M / Random Prune は高 degree ノードを失う）。 ## ストレージ効率の良い構築・更新 - 構築時の**ピークストレージオーバーヘッド削減**（スライド「Storage Efficient Build and Update」）: sampled k-means によるソフト割当、**shard-wise graph construction**、**graph merging**（小さな予算を超えないようシャードを逐次構築・マージ）。 - **Storage Efficient Add**: 一時バッファを用いた更新（圧縮インデックスへのデータ追加を高速・省ストレージに）。 - 実装は **FAISS 上**。評価環境は NVIDIA RTX 4090 と M1 ベース Mac。 ## 結果 - スライド「Results」（NQ/TriviaQA/GPQA/HotpotQA、Target Recall 85%/90%、比較対象 DiskANN, FAISS-HNSW, FAISS-IVF, FAISS-IVF-Disk, IVF-Recompute (EdgeRAG), LEANN）: - **インデックスサイズを元の生データの 5% 未満に削減**。 - **最大 50x 小さいストレージ**（>200 G データ）。 - 実世界ベンチで **1 秒未満で検索**（RTX 4090）、**E2E RAG レイテンシ増は +5%**。 - 精度（スライド「Accuracy Results」、EM/F1）: LEANN は **BM25・PQ（LEANN より大きいストレージ）より高精度**で、HNSW とほぼ同等（NQ F1: BM25 29 / PQ 28 / HNSW 38 / LEANN 38、TriviaQA F1: 58/59/70/70、GPQA F1: 39/38/41/41、HotpotQA F1: 34/29/35/35）。BM25 はキーワードベース（Grep 的）、PQ は圧縮ベクトル法。 ## コミュニティへの影響 - LEANN はベクトル検索/RAG の**軽量・プライベートなツールキット**として OSS 公開され、リリース後数ヶ月で大きなユーザベースを獲得（スライド: **11k+ stars / 1k+ forks**、Contributors 40 名）。on-device システムの personal context 管理を解禁。 - 実環境での効果がコミュニティで検証され、報告される削減幅は論文の数値を上回るケースもある（スライド「It works!」: コミュニティ報告で **136x improvement**、ChromaDB 41 MB に対し LEANN 0.3 MB 等）。 - **Claude Code 向けの最初の MCP ベース意味検索エンジン**（2025年8月）。AST chunker・MCP server・Merkle tree によるファイル同期、リポジトリ横断検索をサポート。Claude Code で精度向上とトークン削減: コミュニティの SWE-bench 結果で **Pass@1 0.63 → 0.73**、Avg Token Cost **29,448 → 18,033**（**2x cost saving / 4x latency saving**）。多くのスタートアップが追随。 - （※トランスクリプトでは "first ACP semantic retrieval engine for cloud code" と聞こえるが、スライド/論文の正は **"first MCP-based semantic retrieval engine for Claude Code"**。"ACP"→MCP、"cloud code"→Claude Code は文字起こしの誤り。） - 多様な応用: email・chat history・file system（spotlight 代替）・codebase・images・agent memory・外部知識ベース（6,000 万文書規模）・live application（slack/twitter）。高度機能として metadata filter（range filter）、hybrid search（grep + vector / BM25 + vector）、instruct embedding model をサポート。 - デモ: "How many classes recommend to take for incoming EECS PhD" を自分の email に対して問い、LLM 単体では答えられない情報（学期あたり 2 コース以下、等）を返す例を提示。 ## 結論 - **問題**: 現代のベクトル検索はインデックスストレージがボトルネック。 - **解決**: LEANN は埋め込みを効率的にオンザフライ再計算し、グラフ構造を圧縮する。 - **結果**: HNSW の精度を維持しつつ **E2E RAG レイテンシ +5%** で**インデックスサイズ最大 50x 削減**。 ## Q&A - **Q1（Chun-Tag, Northeastern ※氏名は文字起こし）— tail recall / tail latency:** コミュニティは平均 recall ばかり議論するが、tail 性能（特に tail recall）は検証したか。手法が平均を上げるために一部 tail クエリを犠牲にしていないか。 - **A:** LEANN は HNSW アルゴリズムを忠実に踏襲するため、レイテンシは HNSW と線形にスケールする。HNSW 自体が tail latency の上界を理論的に持たないので、その限界は LEANN にも当てはまり、極端なケースでは問題が出うる（tight な tail latency 上界はアルゴリズム側の課題）。recall については、HNSW を忠実に踏襲するため**同等の recall を維持**。HNSW 同様、同じ graph search step では一部クエリの recall が低くなるが、その分のクエリは search step を延ばし（レイテンシを増やし）recall を上げられる。 - **Q2（Feifei, 所属名 音声不鮮明）— object-store ベクタDB との比較 / 産業展開のコスト:** S3 等で cold data を保存し warm 部分だけキャッシュする object-store ベースのベクタ DB とインデックスフットプリントを比較したか。また、インデックスサイズを計算（GPU 等）とトレードオフする方式は、大規模産業展開でドル換算で経済的に成立するか。 - **A:** object-store/S3 ベースは**クラウド**前提で課金され private でないのに対し、LEANN は**個人デバイス上で完全ローカル**に最小フットプリントで動く。経済面では S3 は既に安価で、LEANN は GPU を埋め込み加速に使う。クラウドで広く動かす方法は今後の課題だが、クラスタに余剰計算があれば展開可能。アクセス頻度が低くペタバイト級インデックスを月内に常時保持したくない（月数回しか引かない）ような ad-hoc クエリ + 再計算のシナリオでは非常にコスト効率が良い。 - **Q3（An-Ho, SAP ※氏名は文字起こし）— モバイル端末への適用:** さらに小さいデバイス（モバイル）を検討したか。LEANN はモバイルで動くか。 - **A:** 論文で評価したのは広く普及した個人デバイス（Apple M シリーズ、NVIDIA GPU のワークステーション/エンタープライズ）。スマホへの拡張は自然だが、エネルギーコストと計算能力の制約が課題。より小さい埋め込みモデルが必要になりうる。トークンの低次元射影で埋め込みを生成する計算効率の良い新興技術もあり、その方向のフォローアップで全てをスマホに載せられる見込み。