Seonglae ChoExisting compression techniques such as Product Quantization (PQ) can drastically reduce storage, but they often cause a large drop in retrieval accuracy. Moreover, the metadata of approximate nearest-neighbor graph indexes such as Hierarchical Navigable Small World (HNSW) is not itself compressed, which still makes on-device deployment burdensome. However, in RAG workloads, LLM text generation dominates end-to-end latency far more than vector search does, implying a new trade-off: we can sacrifice a small amount of retrieval speed to achieve dramatic storage savings.
LEANN proposes a storage-efficient vector index that avoids storing embedding vectors on disk by recomputing them on the fly during search, while also compressing the approximate graph index. Concretely, LEANN recomputes embeddings in real time by invoking the original embedding encoder to obtain exact distances for candidate vectors during graph traversal. To minimize unnecessary recomputation, it uses a hybrid two-level search: (1) compute approximate distances using a highly compressed PQ codebook, select the top promising candidates, and (2) recompute exact embeddings only for those candidates. In addition, to reduce the graph index size without losing traversal performance, it formulates an optimization problem that minimizes the total number of nodes whose embeddings are recomputed during search, under a disk budget and an accuracy threshold : . Here, denotes the total recomputation cost, is the pruned graph, and is the number of nodes recomputed at the -th step of a best-first search with queue size . The metadata size is computed as the sum over nodes of the out-degree multiplied by the per-neighbor ID storage cost .
To better preserve graph connectivity, LEANN introduces a High-Degree Preserving Graph Pruning algorithm: it analyzes node out-degrees, keeps edges for the top high-degree hub nodes, and aggressively limits the out-degree of the remaining nodes. To address GPU underutilization caused by on-the-fly recomputation, it applies a Dynamic Batching mechanism that dynamically accumulates nodes requiring recomputation across multiple traversal steps and feeds them to the encoder in batches. Finally, to overcome peak-memory pressure during large-scale index construction, it proposes a Sharded Merging Pipeline: perform k-means–based soft assignment, build shard-local graphs independently, and then merge them.
LEANN: A Low-Storage Vector Index
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....
https://arxiv.org/abs/2506.08276
