PaperlayerView exact revision on arXiv

Source-linked AI summary

LEANN: 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

arXiv:2506.08276v2cs.DBcs.LG

TL;DR

Vector indices can require several times more storage than the underlying data, limiting vector search on personal devices and large datasets. LEANN addresses this by recomputing embeddings on demand and compressing graph structure, achieving large storage reductions while preserving reported accuracy and practical RAG latency.

  • Problem

    Vector indices store high-dimensional embeddings and metadata that can substantially exceed raw-data size, constraining deployment on personal devices and large datasets.

  • Method

    LEANN combines on-demand embedding recomputation, two-level search, dynamic batching, and high-degree-preserving graph pruning.

  • Results

    LEANN operates below 5% of raw-data size and achieves up to 50× storage reduction while maintaining reported accuracy and comparable RAG latency.

  • Takeaways & Limitations

    LEANN enables compact vector search for storage-constrained deployments by trading a small amount of search latency for substantial storage savings.

  • Takeaways & Limitations

    At high compression ratios, product quantization introduces errors that can degrade vector-search accuracy below BM25, while HNSW metadata remains difficult to compress.

Abstract

from arXiv · show

Embedding-based vector search underpins many important applications, such as recommendation and retrieval-augmented generation (RAG). It relies on vector indices to enable efficient search. However, these indices require storing high-dimensional embeddings and large index metadata, whose total size can be several times larger than the original data (e.g., text chunks). Such high storage overhead makes it difficult, or even impractical, to deploy vector search on personal devices or large-scale datasets. To tackle this problem, we propose LEANN, a storage-efficient index for vector search that recomputes embeddings on the fly instead of storing them, and compresses state-of-the-art proximity graph indices while preserving search accuracy. LEANN delivers high-quality vector search while using only a fraction of the storage (e.g., 5% of the original data) and supporting storage-efficient index construction and updates. On real-world benchmarks, LEANN reduces index size by up to 50x compared with conventional indices, while maintaining SOTA accuracy and comparable latency for RAG applications.

1 INTRODUCTION

LEANN addresses the storage burden of vector indices by recomputing embeddings during search and pruning graph metadata, while targeting accurate, reasonably low-latency retrieval for storage-constrained deployments.

  • 173 GB of embeddings plus 15 GB of HNSW metadata are required for a 76 GB text corpus, more than doubling the data size.
  • 35× product-quantization compression can reduce vectors to 5 GB, but quantization errors degrade vector-search accuracy below BM25 while HNSW metadata remains burdensome.
  • LEANN recomputes embeddings on demand, using two-level search and dynamic batching to reduce recomputation overhead during graph traversal.
  • High-degree-preserving graph pruning removes low-utility edges from low-degree nodes while retaining edges of frequently visited hub nodes.
  • LEANN supports storage-constrained index construction and updates through sharded merging and an update pipeline.
  • Over 90% top-3 recall within one second is achieved using less than 5% of raw-data storage, with comparable RAG latency and over 50× lower storage than state-of-the-art indexes.RAG end-to-end latency incurs about 10% overhead.

2 BACKGROUND

Vector search retrieves semantically similar objects through approximate nearest-neighbor methods, trading exactness for efficiency; indexes and graph traversal determine the storage and computation costs.

  • Vector search returns the k vectors most similar to query vector q from dataset X, typically using distance or similarity in embedding space.
  • Exact search requires a linear scan in high-dimensional spaces, motivating approximate nearest-neighbor search that trades minor inaccuracies for lower latency.
  • Recall measures the fraction of ground-truth top-k neighbors contained in the retrieved approximate-neighbor set, and RAG commonly requires recall of at least 0.9.
  • IVF searches cluster centers and selected clusters, whereas proximity graphs perform best-first traversal and achieve state-of-the-art efficiency with fewer distance computations.
  • Best-first graph search maintains a bounded priority queue, explores the closest unvisited node, computes unseen neighbor distances, and returns the k closest candidates.
  • Graph-based indexes can achieve high recall with only O(log N) embedding extractions and distance computations because traversal moves toward increasingly similar neighbors.

3 LEANN OVERVIEW

LEANN builds a compact pruned graph and approximate embedding table offline, then combines approximate filtering with on-demand exact recomputation and batching online.

  • Offline construction retains pruned graph adjacency lists and a PQ-compressed embedding table instead of the full embedding set.
  • Online search first estimates distances with PQ embeddings, exactly recomputes only the most promising candidates, and finally ranks visited nodes by exact distance.
  • LEANN combines high-degree-preserving pruning, graph-based recomputation, and two-level search with dynamic batching in its end-to-end workflow.
  • Dynamic batching groups candidate computations across exploration steps to improve GPU utilization and reduce end-to-end latency.
  • The pruned graph uses O(N × |D|) integer entries, while the PQ table uses a 100× smaller codebook and together reduces storage by up to 50×.
  • LEANN targets storage-limited devices, cold datasets, and skewed-access workloads where infrequent or cold entries can use recomputation instead of stored exact vectors.

4 GRAPH-BASED RECOMPUTATION

LEANN reduces embedding recomputation through hybrid approximate-exact search and dynamic batching. These mechanisms preserve traversal quality while improving recomputation efficiency and GPU utilization.

  • 4.1 Two-Level Search with Hybrid Distance: LEANN interleaves exact distances for graph traversal with approximate distances for pruning unnecessary recomputations, balancing accuracy and efficiency.Approximate distances alone can cause detours and missed neighbors under high compression, whereas selective exact recomputation restores ranking fidelity.
  • 4.1 Two-Level Search with Hybrid Distance: At each exploration step, LEANN recomputes only the top α% of approximate candidates not already in the exact queue, rather than every neighbor.The selected candidates are inserted into the exact queue for further exploration.
  • 4.2 Dynamic Batching for Recomputation: Dynamic batching accumulates recomputation candidates across exploration steps until a target batch size, such as 64, is reached.This relaxes strict best-first dependencies, introducing slight staleness while increasing effective batch size and GPU utilization.
  • 4.2 Dynamic Batching for Recomputation: Dynamic batching improves GPU utilization across graph exploration steps regardless of individual node degrees, trading slight exploration-order staleness for throughput.HNSW analysis shows skewed access and degree distributions, with node degrees capped at 60.

5 COMPACT GRAPH STRUCTURE

LEANN compresses graph metadata under a storage budget while preserving navigability and retrieval accuracy. Its pruning strategy retains high-degree hubs and gives them more connections than ordinary nodes.

  • 5 COMPACT GRAPH STRUCTURE: LEANN formulates graph pruning as minimizing recomputation cost while keeping metadata within budget B and recall above threshold τ.The pruned graph's recomputation cost depends on nodes recomputed per exploration step, while metadata is stored in CSR format.
  • 5 COMPACT GRAPH STRUCTURE: High-degree nodes act as navigation hubs, so LEANN preserves their edges while pruning edges from low-degree nodes to protect graph connectivity.Random edge removal and uniformly lowering degree limits significantly degrade search accuracy because they harm traversal connectivity.
  • 5 COMPACT GRAPH STRUCTURE: LEANN assigns most nodes a lower degree limit m while allowing the top β% highest-degree nodes to retain up to M connections.The method empirically sets m = M/5 and determines M for a storage budget through offline profiling.
  • 5 COMPACT GRAPH STRUCTURE: Bidirectional links let nodes connect to newly inserted high-degree hubs up to threshold M, preserving navigability with minimal impact on search quality.This design gives each node an opportunity to connect with hub nodes even when its own outgoing degree is restricted.

6 INDEX BUILDING AND UPDATE

LEANN provides storage-efficient index construction and updates in addition to compact query-time storage. Sharded merging limits construction requirements, while optimized updates reduce recomputation and preserve connectivity.

  • 6 INDEX BUILDING AND UPDATE: Sharded merging builds the index under a storage constraint by assigning passages to two k-means shards, constructing each shard separately, then merging the graphs.Embeddings are discarded after assignment or shard construction, reducing peak storage requirements.
  • 6 INDEX BUILDING AND UPDATE: LEANN achieves the lowest storage footprint in Figure 3 at 5% of the 76 GB RPJ-Wiki dataset size.The figure compares methods against raw dataset size and a 32 GB RAM capacity; memory-heavy HNSW exceeds that RAM limit.
  • 6 INDEX BUILDING AND UPDATE: The merge assigns shared nodes the higher HNSW level and combines lower-layer edge lists, randomly dropping excess edges above degree M.The resulting heuristic is described as producing a well-connected, high-quality graph, while more advanced merging is left for future work.
  • 6 INDEX BUILDING AND UPDATE: LEANN reduces single-update complexity from O(M · efC + efC^2 + M^3) to O(M · efC) through lightweight embedding, caching, and simplified neighbor selection.Soft deletion marks nodes inactive rather than reorganizing the graph, preserving connectivity while avoiding costly deletion operations.
  • 6 INDEX BUILDING AND UPDATE: Batched additions buffer incoming embeddings, merge buffer results with graph results during queries, and insert buffered entries asynchronously.This amortizes update costs while maintaining low search latency and reducing peak storage usage.

7 EVALUATION

LEANN is evaluated on storage, latency, downstream RAG accuracy, and component-level efficiency across multiple datasets and hardware platforms. It maintains high accuracy with substantially lower storage, while its optimizations improve recomputation and graph efficiency.

  • 7.1 Experiment Settings: The evaluation uses four QA benchmarks, additional retrieval datasets, two hardware platforms, and comparisons with graph, cluster, quantization, and lexical baselines.The setup includes RTX 4090 and Apple M1 Ultra systems, with RAG latency measured at 90% recall.
  • 7.2 Main results: LEANN maintains total storage overhead below 5% of the 76 GB raw dataset, matching IVF-Recompute among the evaluated methods.Compared with HNSW, LEANN achieves over 97% storage savings across diverse datasets.
  • 7.2 Main results: LEANN adds less than 20% end-to-end RAG latency overhead, while GPQA overhead remains under 3% because generation dominates total latency.Generation typically exceeds 10 seconds and can reach 70 seconds; IVF-Recompute is reported as up to 200× slower for retrieval.
  • 7.2 Main results: LEANN achieves the highest downstream QA performance and matches HNSW accuracy when both methods target 90% recall.It improves EM by up to 11.8% over BM25 and 11.3% over PQ, and F1 by up to 12.0% and 11.1%, respectively.
  • 7.3 Ablation Studies and Micro Benchmarks: LEANN’s two-level search raises average speedup to 1.4×, and dynamic batching raises it further to 1.8× while maintaining a fixed recall target.The corresponding peak speedups are 1.6× and 2.0×, respectively.
  • 7.3 Ablation Studies and Micro Benchmarks: High-degree-preserving pruning halves graph storage while remaining comparable to the original graph, whereas Random Prune and Small M require up to 1.8× and 5.8× more recomputations.The pruning methods reduce average degree from 18 to 9; Small M fails to reach the 94% and 96% recall targets.

8 RELATED WORK

LEANN combines on-the-fly embedding recomputation with a pruned graph index to reduce storage for vector search on personal devices. Its update pipeline also improves construction efficiency.

  • 8 RELATED WORK: LEANN combines on-the-fly embedding recomputation with a pruned graph index and optimized traversal for personal-device vector search.This contrasts with systems that retain embeddings or rely on compressed embeddings that lose accuracy under tight budgets.
  • 8 RELATED WORK: 63.3× speedup over the naive add operation is achieved through LEANN’s incremental update optimizations, while delayed batching further improves search speed without reducing accuracy.

9 CONCLUSIONS

LEANN reduces vector-index storage by recomputing embeddings and pruning graph structure while preserving high recall and low latency. Its design also includes RNG-based pruning and storage-efficient update mechanisms.

  • 9 CONCLUSIONS: An index smaller than 5% of raw data size delivers up to 50× storage reduction while preserving high recall and low latency.
  • A RNG PRUNING: RNG pruning removes an edge when a closer neighbor makes indirect traversal sufficient, producing a sparse proximity graph.
  • B LEANN UPDATE STRATEGY: LEANN’s update strategy includes a dedicated ADD algorithm for modifying the graph index.

B.1 Add Operation: Method and Time Complexity

The update pipeline analyzes the costs of insertion, then reduces them through caching, simplified pruning, batching, delayed insertion, and soft deletion. These mechanisms target faster updates while preserving graph usability and search correctness.

  • B.1 Add Operation: Method and Time Complexity: The naive implementation recomputes all distances from scratch because only graph structure is stored.
  • B.1 Add Operation: Method and Time Complexity: O(M · efC + efC^2 + M^3) describes naive insertion, with reverse-edge updates causing the cubic term.SEARCHNEIGHBORSTOADD costs O(M · efC), while reverse-edge shrinking costs O(M^3).
  • B.1 Add Operation: Method and Time Complexity: Caching removes redundant SHRINK distance computations, reducing the overall insertion cost.
  • B.1 Add Operation: Method and Time Complexity: Randomized neighbor selection simplifies SHRINKNEIGHBORLIST and reduces complexity from cubic to linear in M while maintaining comparable graph connectivity.
  • B.2 Batched Add Operation: Optimization: When additions precede a query, delayed insertion buffers new embeddings, merges their results with the existing graph, and inserts them asynchronously afterward.
  • B.2 Batched Add Operation: Optimization: A global cache supports multiple add requests, but LEANN clears it when a predefined storage budget is reached to preserve storage efficiency.
  • B.3 Soft Deletion Strategy: Soft deletion marks nodes with a binary flag in O(1) without changing adjacency lists, while traversal still passes through deleted nodes.
  • B.3 Soft Deletion Strategy: Before returning results, LEANN filters deleted candidates and selects the top-k active entries; a background rebuild may start when deletions exceed 5%.

C EVALUATION DETAILS

The evaluation compares LEANN with graph, inverted-file, disk-based, recomputation, and lexical baselines using standardized recall and latency protocols. Experiments span GPU and Mac platforms, with low retrieval overhead reported on Mac.

  • C.1 Baseline Configurations: HNSW uses M=30 and efConstruction=128, while DiskANN uses M=60 and efConstruction=128 under recommended settings.
  • C.1 Baseline Configurations: The baselines include IVF, IVF-Disk, IVF-Recompute, DiskANN, PQ-based compression, and BM25, covering memory-mapped, recomputed, compressed, and lexical retrieval.
  • C.2 Latency Measurement and Evaluation Protocol: Recall@3 uses exact-search results as ground truth, while latency is measured at the minimum ef reaching each target recall over 20 random queries.
  • C.3 Latency Measurement in RAG Pipeline: RAG latency experiments evaluate LEANN at 90% recall with Qwen3-4B for text and Qwen2.5-VL-7B-Instruct for multimodal workloads.
  • C.4 RAG Latency on Mac Platform: On Mac hardware, LEANN maintains its efficiency advantages, with retrieval overhead remaining low relative to other methods.

D.1 Comparison of Index Construction

This section evaluates storage-efficient construction, relaxed-storage caching, embedding-model size, and graph-based recomputation to characterize LEANN’s efficiency trade-offs.

  • D.1 Comparison of Index Construction: The experiments compare storage-efficient construction variants against standard HNSW and examine PQ compression, sharded merging, caching, and embedding-model alternatives.The supplied table describes vector-search and end-to-end RAG latency at 90% recall, with several baselines omitted because they fail the accuracy target or run out of memory.
  • D.1 Comparison of Index Construction: The k-means–sharded graph achieves nearly the same recall as original HNSW with only a small recomputation increase, unlike random sharding.Partitioning into 15 shards provides about a 5× reduction in peak construction storage.
  • D.3 Relaxing Disk Constraint: Storing 10% of the original embeddings yields a 1.5× speedup and cache-hit rates up to 41.9% across four datasets.The skewed graph-traversal access pattern produces high cache hits, while SSD loading limits the corresponding latency gains.
  • D.2 Using Different Embedding Model Sizes: Smaller embedding models are explored specifically to reduce latency because recomputation is the system’s primary bottleneck.The supplied passages identify this as an evaluation direction but do not state its quantitative outcome.
  • D.4 Graph-based Recomputation Breakdown: Embedding recomputation is LEANN’s primary latency bottleneck, accounting for roughly 76% of batched-query latency.The pipeline comprises PQ lookup, text processing, and embedding recomputation with distance calculation, spanning I/O, CPU, and GPU resources.
Loading 2506.08276v2…