> [!abstract] 概要(arXiv abstract の日本語訳) > 埋め込みベースのベクトル検索は、推薦や検索拡張生成(RAG)といった多くの重要なアプリケーションを支えている。ベクトル検索は効率的な探索を可能にするためにベクトルインデックスに依存する。しかし、これらのインデックスは高次元埋め込みと大規模なインデックスメタデータの両方を保存する必要があり、その総サイズは元のデータ(例: テキストチャンク)より数倍大きくなり得る。このような高いストレージオーバーヘッドは、パーソナルデバイスや大規模データセットへのベクトル検索の展開を困難、あるいは実質的に不可能にする。この問題に取り組むため、我々はLEANNを提案する。LEANNは、埋め込みを保存する代わりにオンザフライで再計算し、検索精度を維持しながら最先端の近接グラフインデックスを圧縮する、ストレージ効率の高いベクトル検索インデックスである。LEANNは、ストレージのごく一部(例: 元データの5%)しか使用しないにもかかわらず高品質なベクトル検索を提供し、ストレージ効率の良いインデックス構築と更新をサポートする。実世界のベンチマークにおいて、LEANNは従来のインデックスと比較してインデックスサイズを最大50倍削減しながら、最先端の精度とRAGアプリケーションにおける同等のレイテンシを維持する。 ## 論文情報 - タイトル: LEANN: A Low-Storage Vector Index(論文本文タイトルは "LEANN: A Low-Storage Overhead Vector Index"、arXiv/HuggingFace/MLSys 2026 会議掲載タイトルは "A Low-Storage Vector Index" と若干の表記揺れがある) - 著者: Yichuan Wang†・Zhifei Li・Shu Liu・Yongji Wu†・Ziming Mao・Yilong Zhao・Xiao Yan・Zhiying Xu*・Yang Zhou・Ion Stoica・Sewon Min・Matei Zaharia・Joseph E. Gonzalez(† corresponding authors, * 本研究はAmazon在籍時の所属業務とは無関係) - 所属: UC Berkeley(Sky Computing Lab)・The Chinese University of Hong Kong(CUHK)・Amazon Web Services・UC Davis - 媒体: arXiv プレプリント(投稿時 Under Review)、MLSys 2026 Oral(2026-05-19 発表) - arXiv ID: 2506.08276(v1: 2025-06-09、v2: 2025-11-25) - コード: https://github.com/yichuan-w/LEANN(MIT License、11.4k+ stars、1k+ forks、40+ contributors、発表スライド時点で570 commits) ## 概要 LEANNは、埋め込みベクトルを事前計算・保存する代わりにクエリ時にオンザフライで再計算し、近接グラフ(proximity graph)インデックスのメタデータも高次数保存枝刈りで圧縮するストレージ効率型ベクトルインデックスである。76GBのRPJ-Wikiデータセットに対し、既存のHNSW(188GB)やDiskANN(270GB)が生データの2倍以上のストレージを要するのに対し、LEANNはわずか4GB(生データの5%未満)で同等の検索精度を達成する。RAGパイプラインでは生成(LLM推論)がレイテンシの大部分(HNSW構成で99.8%)を占め検索は0.24%に過ぎないという観測(Figure スライド10枚目)に基づき、わずかなレイテンシ増加とストレージの大幅削減をトレードする設計思想を取る。 ## 問題設定 **入力**: チャンク化された未構造テキスト(または画像)データセットと、埋め込みモデル。**出力**: クエリベクトルに対する top-k 近傍チャンク。**前提条件**: パーソナルデバイス(ノートPC・ワークステーション)やコールドデータセット(データレイク内の低頻度アクセスデータ)など、ストレージ容量がRAM/ディスク容量に対して厳しく制約される環境。**必要なデータ**: 生テキスト/画像ストア、埋め込みモデル(論文では Contriever 110M パラメータを標準採用、Appendix D.1 では GTE-small 34M も評価)。 ## 提案手法 - **アーキテクチャ**: オフラインステージ(埋め込み計算→近接グラフ構築→高次数保存枝刈り→PQ埋め込みテーブル構築→圧縮グラフとPQテーブルの永続化)とオンラインステージ(二段階探索→動的バッチング→ローカル埋め込み生成器での再計算→埋め込みキャッシュ)の2段構成(Figure 1)。オフラインステージ終了時にLEANNが永続化するのは「枝刈り済みグラフの隣接リスト」と「PQ圧縮埋め込みテーブル」の2つのみで、生の高次元埋め込みは保存しない。 **Figure 1: LEANNシステム図** ![[_attachments/59_LEANN_A_Low_Storage_Overhea/fig01-system-diagram.png]] (Figure 1. LEANN System Diagram. オフラインステージ(高次数保存グラフ枝刈りで最小ストレージ足跡を実現)とオンラインステージ(グラフベース再計算・二段階探索・動的バッチングで効率的なクエリ処理を実現、Steps 1-4)の全体構成。Source: Adapted from Figure 1.) - **二段階探索(Two-Level Search、§4.1、Algorithm 2)**: HNSW系のベストファースト探索(Algorithm 1)を土台に、各探索ステップで全近傍ノードに対しPQ(Product Quantization)による近似距離をまず計算し近似キュー(AQ)に蓄積する。そのうち再ランキング比率α%の上位候補のみを厳密再計算し、正確キュー(EQ)へ挿入する。既存のDiskANN流「近似距離で探索→上位候補だけ厳密再ランキング」という分離型設計とは異なり、LEANNは近似距離と厳密距離の計算を各探索ステップで交互に(interleave)行う。これは、LEANNのPQコードが高圧縮率(100倍小さいコードブック)ゆえに量子化誤差が大きく、既存の分離型設計では探索が迂回(detour)して劣った候補を訪問し、再ランキング候補数を増やしても回復しない場合がある(Figure 4の議論)ためである。 - **動的バッチング(Dynamic Batching、§4.2)**: 単一の探索ステップ内(1ホップ内)でのバッチ化に加え、複数の探索ステップ(複数ホップ)をまたいでノードをバッチ化し、GPU利用率を高める。優先度キューから最も近い候補を動的に集め、目標バッチサイズ(例: 64、オフラインプロファイリングで決定)に達するまで蓄積してから一括再計算する。探索順序にわずかな「staleness」(古さ)が生じるトレードオフと引き換えに、有効バッチサイズとスループットを改善する。 - **高次数保存グラフ枝刈り(High-Degree Preserving Graph Pruning、§5、Algorithm 3)**: HNSWグラフのノード次数分布とアクセス確率を分析すると(Figure 2)、次数の高いノード(次数上限60近辺)ほど探索で頻繁に訪問される「ハブ」であることが分かる。 **Figure 2: HNSWグラフのノード次数分布とアクセス確率** ![[_attachments/59_LEANN_A_Low_Storage_Overhea/fig02-hnsw-degree-access.png]] (Figure 2. HNSW graph analysis reveals skewed access and degree distributions, with node degrees capped at 60 by HNSW. (a)ノード次数分布は低次数側に偏り、次数60付近にHNSWの次数上限による突出が見られる。(b)訪問確率は次数の高いノードほど大きく、高次数ノードが探索の「ハブ」として機能することを示す。Source: Adapted from Figure 2.)この観測に基づき、ノード集合の上位β%(3〜5%が有効な操作点)を高次数ノードとして最大次数Mまで接続を許容し、残り(1-β)%のノードは低次数m(m=M/5)に制限する。ノード挿入時は下限mで新規接続を制限する一方、既存ノードから新規ノードへの逆方向リンクはMまで許容し(Algorithm 3, Line 11)、RNGスタイル枝刈り(Appendix A、Figure 11)で過剰接続を整理する。ストレージ予算Bと精度閾値τの下で再計算コストT(G1)を最小化する制約付き最適化として定式化される(式3)。 - **ストレージ効率インデックス構築(§6)**: ピークストレージ使用量を抑えるため、shard-wise merging pipeline を導入する。(1) 小規模サンプルでk-meansソフト割り当てを行い、各パッセージを最近傍2centroidに割り当てる、(2) 各shardごとにグラフを個別構築(パッセージは平均で最大3回埋め込まれるが、埋め込みは使用後即座に破棄される)、(3) shardグラフをマージし、次数上限を超えるノードはランダムにエッジを削除する。15shardへの分割でピークストレージ使用量を約5倍削減できることをFigure 8で確認。 - **効率的インデックス更新(Appendix B)**: 単一ノード追加のナイーブな計算量O(M·efC + efC²+M³)を、距離キャッシュとRNG枝刈りの単純化によりO(M·efC)まで削減(3次から1次への低減)。削除はソフト削除(バイナリフラグ、隣接リストは変更せず検索時にフィルタ)で行い、閾値超過時のみバックグラウンド再構築を検討する(実装は将来課題)。バッチ追加操作では、埋め込みを一時バッファに蓄積し検索時にグラフとバッファの両方から結果をマージする遅延挿入(delayed insertion)で更新コストを償却する。 ## 新規性 既存のストレージ削減手法との対比が明確に整理されている。(1) ベクトル量子化(PQ、RabitQ): 高圧縮率で大きな量子化誤差が生じ、BM25以下まで精度が劣化しうる。(2) ディスクベースインデックス(DiskANN、Starling): メモリオーバーヘッドは削減するがディスク容量は依然として大きく、DiskANNは元データの76GBに対し270GBという既存手法中最大のフットプリントになる(セクター整列レイアウトによる4KBパディングと30GBの追加PQ埋め込みが原因)。(3) IVF-Recompute(EdgeRAGにインスパイア): LEANNと同様に埋め込みをオンザフライ再計算するが、IVF系インデックスはO(√N)の再計算を要し、LEANNのグラフベースO(log N)再計算より最大200倍遅い(N=60M)。LEANNの新規性は、埋め込み非保存(オンザフライ再計算)とグラフメタデータ圧縮(高次数保存枝刈り)を単一システムとして組み合わせ、二段階探索と動的バッチングで再計算コストを実用的な水準まで下げた点にある。 ## 実験設定 - **実験環境**: (1) NVIDIA RTX 4090 GPU・32GB RAM・1TB ディスク(WSL2)のワークステーション、(2) AWS EC2 M1 Mac インスタンス(Apple M1 Ultra Arm64、macOS、128GB RAM、512GB EBS)。 - **データセット**: RPJ-Wiki(RedPajama由来、約76GBの生Wikipediaテキストを256トークンチャンクに分割、Contrieverで768次元埋め込みを生成、N=60M パッセージ、埋め込み総量約173GB)。QAベンチマークはNQ・TriviaQA・GPQA・HotpotQAの4種、加えてFinanceBench(金融文書検索)・Enron Email Corpus(メール検索)・LAION(画像検索)のパーソナルデータセットでも評価。 - **比較対象**: HNSW(faiss.IndexHNSWFlat, M=30, efConstruction=128)、IVF(faiss.IndexIVFFlat, nlist=8192)、DiskANN(M=60, efConstruction=128)、IVF-Disk(mmap経由)、IVF-Recompute(EdgeRAGにインスパイアされたベースライン)、PQ Compression(5GB圧縮)、BM25(Pyserini実装)。 - **評価指標**: Recall@3(k=3で正解ラベル代わりに厳密探索結果を使用)、90%目標recallに到達するための平均検索レイテンシ(20クエリの二分探索でefを決定)、ダウンストリームRAG精度(Exact Match・F1、生成モデルはQwen3-4B、マルチモーダルはQwen2.5-VL-7B-Instruct)。 ## 実験結果 - **ストレージ消費(Figure 3)**: LEANNとIVF-Recomputeのみが生データサイズ(76GB)の5%未満に収まる。LEANNは4GB、DiskANNは270GB(最大)、HNSWは188GB。HNSWの15GBグラフメタデータを含めても、LEANNはHNSW比97%以上のストレージ削減を個人データセット(FinanceBench・Enron・LAION、Table 3)でも一貫して達成する。 **Figure 3: RPJ-Wikiデータセットにおけるストレージ消費比較** ![[_attachments/59_LEANN_A_Low_Storage_Overhea/fig03-storage-comparison.png]] (Figure 3. Storage consumption of different vector index methods on the RPJ-Wiki dataset. 黒破線は生データサイズ(76GB)、赤破線は典型的なRAM容量(32GB、RTX 4090構成)を示す。DiskANN(270GB)・HNSW(188GB)・IVF系(172GB)はメモリ集約的でRAM上限を超えるが、LEANN(4GB)は生データの5%に収まる最小フットプリントを達成。Source: Adapted from Figure 3.) - **レイテンシ(Table 2・3)**: LEANNはRAGパイプライン全体に対し20%未満のレイテンシオーバーヘッドしか追加しない。GPQAのような長い chain-of-thought を要する推論集約タスクでは3%未満に収まる(生成時間が支配的なため)。IVF-Recomputeはaccuracy面でLEANNに匹敵するがNQで最大200倍遅い(307.61秒 vs 2.48秒)。 - **ダウンストリームRAG精度(Figure 4)**: LEANNはBM25比EM最大11.8%・F1最大12.0%、PQ比EM最大11.3%・F1最大11.1%改善。90%目標recallを課すとLEANNの精度はHNSWとほぼ一致する(NQでEM 38 vs 38、TriviaQAでF1 70 vs 70)。改善幅はNQ・TriviaQA(事実回答型)で大きく、GPQA(RPJ-Wikiに対し分布外の大学院レベル問題)・HotpotQA(マルチホップ推論を要するが本実験は単一ホップ検索)では小さい。 **Figure 4: 4つのQAベンチマークにおけるEM/F1比較** ![[_attachments/59_LEANN_A_Low_Storage_Overhea/fig04-accuracy-comparison.png]] (Figure 4. Comparison of Exact Match and F1 scores for downstream RAG tasks across four methods: BM25・PQ・HNSW・LEANN。HNSWとLEANNは目標recall 90%で設定、PQは到達可能な最高recallまで拡張探索。生成モデルはQwen3-4B。NQ・TriviaQAではLEANNがHNSWとほぼ同一の精度でBM25/PQを上回る。Source: Adapted from Figure 4.) - **アブレーション(Figure 5)**: 二段階探索単体で平均1.4倍(最大1.6倍)、動的バッチングを加えると平均1.8倍(最大2.0倍、HotpotQAで2.02倍)のスピードアップ。 - **枝刈り品質比較(Figure 6・7)**: 平均次数18→9への半減において、提案手法はランダム枝刈り比最大5.76倍・次数制限縮小(Small M)比最大1.81倍少ない再計算ノード数で同等recallを達成する唯一の手法。 **Figure 6: 枝刈り手法間の再計算コスト比較** ![[_attachments/59_LEANN_A_Low_Storage_Overhea/fig06-pruning-quality.png]] (Figure 6. Comparison of pruned graph quality against two heuristic methods using the datastore in §7.1. NQデータセットの各recall目標において、最小再計算ノード数(少ないほど良い)を比較。灰色破線は2倍のストレージ(平均次数18)を使う元のHNSWグラフを基準として示す。提案手法(赤)はランダム枝刈り(青)より最大5.76倍、Small M(緑)より最大1.81倍少ない再計算で同等recallに到達。Source: Adapted from Figure 6.) - **インデックス構築・更新(Figure 8・9)**: k-means shard-wise構築はランダム割り当てshardingより大幅に少ない再計算コストで元のHNSWに近いrecallを達成。更新はキャッシュ・非同期挿入等の最適化を段階的に有効化することでナイーブな再計算比最大63.3倍のスピードアップ。 - **緩やかなストレージ予算下でのトレードオフ(Figure 10)**: 元埋め込みの10%だけをキャッシュとして保持すると最大1.5倍のスピードアップ(キャッシュヒット率最大41.9%)。ストレージとレイテンシの間に滑らかなトレードオフ曲線が存在する。 - **軽量埋め込みモデル(Figure 12)**: ContrieverからGTE-small(34Mパラメータ、110Mの約1/3)へ置き換えると2.3倍のスピードアップを、ダウンストリーム精度をContriever比2%以内に保ったまま達成。 - **再計算のレイテンシ内訳(Figure 13)**: バッチ化されたクエリのレイテンシは、I/O(テキスト取得+PQルックアップ、8.0%)・CPU(トークナイズ+距離計算、16.1%)・GPU(埋め込み再計算、76.0%)の3段に分解され、埋め込み再計算がボトルネックだがI/O・CPU・GPUにまたがるためオーバーラップの余地があることを示す。 ## 考察 論文はLEANNの適用範囲を明示的に限定している(§9)。有利なワークロード特性として、(1) LLM中心パイプライン(RAG・エージェントメモリ・検索拡張エージェント)のように生成がレイテンシを支配する場合、(2) パーソナル検索・アドホックログ解析・オンデバイス文書検索のようにQPSが低くストレージが律速する場合、(3) 再計算をオーバーラップ可能でストレージが依然コスト要因であるデータセンター環境、の3つを挙げ、これらは「5分ルール」(Gray & Graefe, 1997)と整合すると位置づける。一方、生成時間が短いワークロードでは検索オーバーヘッドが相対的に顕在化するため、PipeRAGのような検索・生成パイプライン化(LEANNとは直交)が緩和策として示唆される。純粋な検索専用・高スループット・厳格なテールレイテンシ要求のワークロード(リアルタイムコンテンツ検索、推薦システム)はLEANNの主対象外と明記されている。 将来方向として、LEANNのコア技術(オンザフライ再計算・ハブ保存枝刈り・再計算考慮探索)はグラフベースANN全般に一般化可能であるとし、Model2Vecのようなルックアップベースの軽量埋め込みモデルと組み合わせることでニューラルアクセラレータ非依存(CPUのみ)の展開も視野に入れている。 ## MLSys 2026 発表スライドからの補足(論文本文に無い情報) 論文出版後、LEANNはオープンソースリポジトリ [[LEANN (repository)|LEANN]] として公開され、発表時点(MLSys 2026、2026-05-19)で11.4k+ stars・1k+ forks・40+ contributors・570 commitsに成長した。スライドは実運用における採用状況を示す一次情報として以下を含む(論文には無い内容のため、本節で明示的に区別する)。 - **コミュニティ実測による追加検証**: LinkedIn上の実践者(Muthu Kumaran, Staff Data Engineer)が同一データ(1MB PDF、nomic-embed-text埋め込み)でLEANN(0.3MB)とChromaDB(41MB)を比較し136倍のストレージ削減を報告。別の実践者(Ivan Groenewald, CTO)はOllama+qwen3:4bをバックエンドにMac Mini M2 Proでの完全ローカル・オンデバイス動作を報告した。論文提示のGoogle Formsアンケート(108〜111件の回答)では、インデックス対象データとしてPersonal Knowledge(PDF等、77.5%)・Codebase(54.1%)・Enterprise Data(43.2%)が上位を占めた。 **実運用比較: LEANN vs ChromaDB(コミュニティ計測)** ![[_attachments/59_LEANN_A_Low_Storage_Overhea/slide-real-world-storage-comparison.png]] (ユーザーレポートによるストレージ比較表(DPR・Wiki・Chat・Email・Browser の5データセットで91〜97%のストレージ削減)と、LinkedIn実践者による136倍改善レポートのスクリーンショット。論文本文には無い、公開後のコミュニティ実測値。Source: MLSys 2026 発表スライド(スライド25枚目)。) - **Claude Code連携(MCPベース)**: LEANNはClaude Code向けの最初のMCPベースセマンティック検索エンジンとして機能拡張されており、ASTチャンカー・MCPサーバー・Merkle Tree統合・リポジトリ横断検索を提供する。コミュニティのSWE-bench計測ではPass@1が0.63→0.73に、平均トークンコストが29,448→18,033に改善したと報告されている(スライドの引用元コミュニティリンクは検証未実施)。 - **将来方向 DS-Serve**: 発表チームは低ストレージベクトルインデックスを本番規模のセマンティック検索(ログ解析・Parquet互換等)へスケールする "DS-Serve" という次期プロトタイプをMLSys 2026ポスターセッションで発表した(論文・スライドとも技術詳細は含まれず、ロードマップとしての言及のみ)。 **GitHubコミュニティの成長(発表時点)** ![[_attachments/59_LEANN_A_Low_Storage_Overhea/slide-community-adoption.png]] (発表時点で11.4k+ stars・1k+ forks・40+ contributorsに成長したLEANNリポジトリのGitHub star history(2025年10月〜2026年4月にかけて急成長)。論文出版後の実コミュニティ採用を示す一次情報。Source: MLSys 2026 発表スライド(スライド24枚目)。) ## 強み / 弱点・課題 **強み**: - ストレージ削減(最大50倍)とダウンストリーム精度維持(HNSW同等)を両立し、既存のPQ/RabitQ(精度劣化)・DiskANN/Starling(依然大きいディスク使用量)のいずれとも異なるトレードオフ点を実現。 - FAISS上に実装しRTX 4090・Apple M1 Ultra双方で一貫した傾向を確認しており、ハードウェア汎化性を実証。 - オープンソース公開後の実コミュニティ採用(11.4k+ stars、Claude Code連携等)により、学術的評価にとどまらない実運用面での有効性が補強されている。 **弱点・課題(論文が明示するもの)**: - 純粋な検索専用・高スループット・厳格テールレイテンシ要求のワークロードには非対象と明記(§9)。 - ソフト削除は閾値超過時のバックグラウンド再構築ポリシーの検討を将来課題として残す(Appendix B.3)。 - shard-wiseインデックス構築は各パッセージを最大3回埋め込む追加計算コストを要する(§6)。 **読み取れる懸念(論文からは直接述べられていないが構造上生じうる点)**: - 二段階探索の再ランキング比率αや動的バッチングの目標バッチサイズはオフラインプロファイリングで決定するとされており、データセット・ハードウェアが変わるたびの再チューニングコストは定量化されていない。 - 高次数保存枝刈りのハイパーパラメータ(β=3〜5%、m=M/5)はNQデータセットでの実験に基づく推奨値であり、他ドメイン・他規模データセットでの汎化性は本文中で厳密には検証されていない。