LEANN: A Low-Storage Vector Index

Vector search without storing the vectors.

Semantic search keeps an embedding for every chunk of your documents, and those embeddings take more disk than the documents do. LEANN deletes them, keeps a pruned graph and a 31-byte compressed code per chunk, and recomputes at query time only the embeddings a search visits. On a 76 GB Wikipedia corpus the index is 4 GB, and retrieval quality matches HNSW, the standard graph index that stores every vector.

It spends a few seconds of GPU time per query (2.48 s on NQ) to save 184 GB of disk, and places that time inside a chat request that already waits about 20 s for the language model.

Every "chat with your documents" app does the same thing. To search text by meaning instead of by keyword, it runs each chunk of text through an embedding model, an encoder that maps a passage to a vector of numbers so that passages about the same thing land near each other. It stores all those vectors. At query time it embeds the question the same way and looks for the stored vectors nearest to it. Those neighbors are the passages handed to the language model, the setup called retrieval-augmented generation (RAG).

The paper's running example is a 76 GB dump of Wikipedia text cut into 256-token chunks, about 60 million of them. Each chunk goes through Contriever, a 110M-parameter retrieval encoder built on BERT, which outputs 768 numbers per chunk. At 4 bytes per number that is 3,072 bytes of vector for roughly 1 KB of text: the searchable copy is three times larger than the data. Across the corpus the paper counts about 173 GB of embeddings, and HNSW, the standard graph index, adds 15 GB of structure on top, for 188 GB in total. The paper's test machine has 32 GB of RAM, and HNSW runs out of memory on it. LEANN, from UC Berkeley, serves the same corpus at the same retrieval quality from a 4 GB index.

The page follows the paper's argument in order: why the index is so large, why a graph search reads so little of it, the decision to recompute embeddings instead of storing them, the two mechanisms that make recomputation fast (a quantized filter and batching), the graph pruning that removes most of what is left, how the index is built and updated without ever holding every embedding, and what a query costs at the end.

Why a vector index outweighs the data

Exact vector search returns, for a query vector $q$, the $k$ stored vectors closest to it. The paper writes the exact answer as a set $S_q$ of size $k$ in which every member is at least as close to $q$ as every non-member:

Computing that set exactly means comparing the query against all 60 million vectors. Every practical system uses approximate nearest neighbor search (ANNS) instead: an index that computes only a small fraction of the distances and returns a set $S'_q$ that contains most of the true one. The fraction it gets right is the recall:

The paper evaluates at $k=3$ and a 90% recall target. Averaged over queries, the index returns 2.7 of the 3 passages an exact search would have returned. Every latency number on this page is measured at that target: the paper tunes each method's search effort by binary search until it just reaches 90%, then times it over 20 random queries.

An index stores two things: the vectors, and metadata that tells a search which vectors to compare. The arithmetic for the Wikipedia corpus fits in five lines:

# what each piece costs for N = 60M passages (Contriever, d = 768)
N = 60_000_000
vectors_fp32 = N * 768 * 4        # 184 GB  (the paper reports "about 173 GB")
hnsw_graph   = N * 60 * 4         # 14.4 GB: 60 neighbor slots of 4-byte ids
pq_codes     = N * 4 * 768 / 100  # 1.8 GB: ~31 bytes per passage
pruned_graph = N * 9 * 4          # 2.2 GB: packed lists at average degree 9

Multiplying 60 million by 3,072 bytes gives 184 GB; the paper reports about 173 GB, and it gives the passage count only as "about 60 million", so the gap is within its rounding. The graph line assumes HNSW pads every node's neighbor list to its maximum of 60 slots, which is how the paper explains HNSW's storage, and 14.4 GB matches the 15 GB it measures. Figure 1 puts these numbers next to the other indexes the paper tests.

DiskANN is the largest at 270 GB: it pads each node's vector and neighbor list to a 4 KB disk sector and keeps an extra 30 GB of compressed vectors in memory. BM25, the keyword-ranking function from the 1990s, needs 59 GB for its inverted index.

The obvious fix is to compress the vectors. Product quantization (PQ), covered properly in a later section, replaces each vector with a short code. The paper's PQ baseline needs about 35× compression to bring the vectors down to 5 GB, and at that compression downstream question-answering accuracy on NQ (Natural Questions, a factual QA benchmark) falls from 25.5% to 17.9%, below BM25's 18.3%. Compression also does nothing to the graph. The 15 GB of neighbor lists stays whatever the vectors cost, so PQ's total is 20 GB (15 + 5), and no quantizer, however good, gets an HNSW index below 15 GB. Getting to 4 GB requires removing the vectors from disk entirely and shrinking the graph as well.

How graph search visits a small fraction of the corpus

There are two main families of vector index. An inverted file index (IVF) clusters the vectors with k-means, stores one centroid per cluster, and answers a query by comparing it against the centroids and then against every vector in the few nearest clusters. A proximity graph links each vector to a few dozen of its near neighbors and answers a query by walking the links. Graphs reach a given recall with fewer distance computations than any other family, and LEANN builds on the most widely used one, HNSW (Hierarchical Navigable Small World graphs).

The walk is best-first search (the paper's Algorithm 1). It keeps a candidate list of at most ef nodes, sorted by distance to the query, starting from a fixed entry node. At each step it takes the closest candidate it has not yet expanded, computes the distance from the query to each of that node's neighbors, and inserts any neighbor that is closer than the worst entry on the list, which pushes the worst entry off. The search stops when every node on the list has been expanded, and the top $k$ of the list are the answer. ef sets the trade: a longer list keeps more runner-up paths alive, so the walk can back out of a dead end, at the cost of more distance computations.

The walk works for the same reason as the six-degrees game, where you reach a stranger by passing a letter to whichever acquaintance lives closest to them. Each node links to its own neighborhood, so each hop to a closer node brings the next set of neighbors closer too. The analogy stops at dead ends: in the game every acquaintance can pass the letter on, while in the graph a node whose neighbors are all farther from the query would stop a purely greedy walk, and the ef runner-ups are what let the search continue from an earlier node.

Figure 2 runs this search on a 900-point toy corpus wired the way HNSW wires its bottom layer. Watch the counter in the top-left corner, which tallies how many of the 900 embeddings the search has needed so far.

A few dozen of the 900 nodes get computed. At full scale the fraction is far smaller: the paper states that graph indexes reach high recall with $O(\log N)$ distance computations, an empirical regularity rather than a theorem, and its ablation plots put the count at 90% to 96% recall on the order of ten thousand recomputed nodes per query, under 0.1% of 60 million. For any single query, more than 99.9% of the 173 GB of stored embeddings is never read.

A conventional index cannot delete the unread part, because which 0.1% a query needs depends on the query and is revealed one hop at a time. The search cannot know which nodes it will visit until it has computed the distances of the nodes it is at, so a conventional index keeps every embedding on disk in case it is needed.

How LEANN works: recompute embeddings instead of storing them

LEANN stores the graph and the original text, and no embeddings. When the walk needs a node's embedding, LEANN runs that node's text through the same encoder that built the index. The same model on the same text produces the same vector, so the walk computes the same distances it would have read from disk and returns the same neighbors. The two inputs needed to recreate any embedding are already on the machine: the text is the user's data, and the encoder has to be there anyway, because a dense retriever embeds every query with it.

Anyone who has trained a large model has seen this trade as gradient checkpointing: discard activations during the forward pass and recompute them during the backward pass, paying compute to save memory. The two differ in what gets recomputed. Checkpointing re-runs a fixed schedule that is known before training starts. LEANN re-runs a small, query-dependent subset that the search discovers as it goes, and the design only works because that subset stays small.

Each recomputation is a forward pass of a 110M-parameter encoder over a 256-token chunk, so a search that took HNSW 0.05 s takes LEANN 2.48 s on NQ, about 50 times longer. The paper argues this is acceptable because of where retrieval sits in a RAG request. Search runs first, then a local 4B-parameter model (Qwen3-4B on an RTX 4090) generates the answer, and generation takes 20.86 s. HNSW's search is 0.2% of that request. End to end (the paper's Table 1), the request goes from 20.95 s with HNSW to 23.34 s with LEANN, which the paper calls about 10% overhead. The 184 GB of disk that LEANN saves is paid for with about 2.4 seconds per query.

Recomputation also decides which index family can be used. Once each distance costs an encoder pass instead of a memory read, the only thing that matters is how many vectors a query touches. An IVF index scans every vector in each cluster it probes. With the standard $\sqrt{N}$ clusters (the paper uses 8,192 at 60M), a cluster holds about 60M / 8,192 ≈ 7,300 passages, so each probe costs thousands of encoder passes. The paper's IVF-Recompute baseline, modeled on EdgeRAG's online embedding generation and built with LEANN's own IVF settings, takes 307.61 s per query on NQ against LEANN's 2.48 s. The paper attributes the gap to $O(\log N)$ recomputations for a graph against $O(\sqrt{N})$ for IVF, and reports IVF-Recompute as up to 200× slower across its datasets and machines (the largest ratio in its tables is about 185×, on the Mac).

A graph walk that recomputes naively still wastes encoder time in two ways. It recomputes every neighbor of every expanded node, although most neighbors are too far from the query to matter. And it sends them to the GPU a few at a time, since each hop only produces the neighbors of one node. The next two sections cover the fix for each.

Product quantization as a cheap distance filter

To decide which neighbors deserve an encoder pass, LEANN keeps one compressed form of every vector after all: a product quantization table. PQ works in three steps:

1. Cut each 768-dimensional vector into equal slices, for example 32 sub-vectors of 24 dimensions.
2. For each slice position, run k-means over the corpus to learn a codebook of 256 centroids, and replace each sub-vector by the one-byte id of its nearest centroid. A vector becomes a string of 32 bytes.
3. At query time, compute once the distance from each query slice to all 256 centroids of that slice. That fills a 32 × 256 lookup table. The estimated distance to any stored vector is then the sum of 32 table entries, one per byte of its code, with no encoder call and no 768-dimensional arithmetic.

The paper sizes its PQ table at $4N \times \mathrm{dim}/100$ bytes, about 31 bytes per passage for $\mathrm{dim} = 768$, and 2 GB for the corpus. That is 100 times smaller than 3,072 bytes of float32. The codebooks themselves are tiny: 768 dimensions × 256 centroids × 4 bytes ≈ 0.79 MB in total, however the dimensions are sliced.

At 100× compression the estimates are distorted. Each sub-vector is replaced by a centroid that may be some distance away, and those errors add up across the slices. The estimate still separates a close vector from a far one, but it cannot reliably order two vectors at similar distances, such as the third-nearest and the ninth-nearest. Figure 3 runs real PQ on a toy corpus (600 vectors, 32 dimensions, 16 centroids per slice) and scans all of it with PQ, without a graph, so the filter can be tested on its own.

At 128×, the setting closest to LEANN's, ranking the toy corpus by PQ alone finds 13% of the true top-3 averaged over 40 queries. The true neighbors are nearly always near the front of the PQ order, though: 92% of them fall inside PQ's top 10%, so recomputing that 10% exactly and re-sorting finds them.

Two-level search: exact distances steer, PQ nominates

LEANN now has two ways to measure distance: PQ, which costs a few table lookups and is often wrong about close calls, and recomputation, which costs an encoder pass and is exact. The design question is which of the two decides where the walk goes next.

DiskANN, the standard disk-based graph index, uses the cheap one. It keeps PQ codes in memory and lets them choose every hop; the full vectors, which arrive with the disk reads the walk makes anyway, re-rank the final candidates (for example the top 100 by PQ for a top-10 answer). That works at DiskANN's moderate compression. The paper finds it fails at LEANN's. The distorted distances lead the walk into detours, some true neighbors are never reached, and re-ranking more PQ candidates does not recover them. Re-ranking re-sorts the nodes the walk collected. If a PQ error made the walk turn away from the region holding the answer early on, the true neighbors were never collected, and no amount of exact sorting at the end brings them into the list.

LEANN swaps the roles (Algorithm 2). The walk keeps two queues. The exact queue EQ is the usual best-first list of at most ef nodes, and only recomputed nodes enter it. The approximate queue AQ holds a PQ estimate for every neighbor the walk has reached. At each step:

1. take the closest unvisited node $u$ in EQ, by exact distance, and mark it visited;
2. PQ-score each neighbor of $u$ that has no estimate yet and add it to AQ;
3. take the top $\alpha\%$ of AQ's entries that are not already in EQ, recompute their embeddings, and insert them into EQ with exact distances.

As a worked step: if AQ holds 200 PQ-scored candidates outside EQ and $\alpha$ is 10%, the step recomputes the 20 with the best PQ estimates and leaves the other 180 in AQ, which never drops an entry. When the walk moves into their neighborhood, new and closer candidates join AQ, the ranking shifts, and a candidate that missed the cut earlier can be recomputed then. Every choice of the next hop is made on an exact distance, so a PQ error can cause a wasted recomputation (a candidate that turns out to be far) or a delayed one, but it cannot send the walk the wrong way. Figure 4 runs both designs on the Figure 2 corpus with the same simulated PQ error.

The second waste is batch size. A GPU running a 110M-parameter encoder on a handful of passages leaves most of its compute idle, and the time per passage falls as the batch grows until the GPU is full. Best-first search is sequential, since the next hop depends on the distances just computed, so a straightforward implementation sends the GPU one hop's worth of work at a time. Batching all neighbors of one expanded node helps, but that batch is capped by the node's degree, and after two-level filtering only the top $\alpha\%$ of it remains.

LEANN's dynamic batching relaxes the ordering. Nominated candidates accumulate across hops until a target batch size is reached (64 in the paper's example, chosen by offline profiling of the GPU), and one encoder call embeds them all. The walk meanwhile continues on the exact distances it already has, so a candidate may enter EQ a hop or two later than strict best-first order would put it; the paper calls this "slight staleness" and measures the speedups below at a fixed recall target. The full query:

# one LEANN query: the paper's Algorithm 2 plus dynamic batching
EQ = queue(ef)        # exact queue: only recomputed embeddings enter
AQ = heap()           # approximate queue: PQ distances, never discarded
push(EQ, entry, exact_dist(q, encoder(text[entry])))
pending = []
while EQ has an unvisited node:
    u = closest unvisited node in EQ      # the next hop uses exact distances
    mark u visited
    for v in neighbors(u):
        if v not in AQ:
            push(AQ, v, pq_dist(q, codes[v]))   # table lookups, no encoder
    pending += top alpha% of AQ not in EQ or pending
    if len(pending) >= 64 or no unvisited node left in EQ:
        embs = encoder(text[pending])     # one batched forward pass
        for c, e in zip(pending, embs):
            push(EQ, c, exact_dist(q, e))
        pending = []
return k closest nodes in EQ

On the real system, starting from a baseline that recomputes every neighbor of every hop, two-level search alone speeds retrieval up 1.4× on average (up to 1.6×). Adding dynamic batching raises the average to 1.8× and the peak to 2.0×. HotpotQA gains the most from batching; its multi-hop questions produce the longest search paths, which leave more candidates to group into each batch.

Pruning the graph while keeping the hubs

With the embeddings gone, the graph's neighbor lists are the largest remaining piece of the index. The paper's HNSW baseline is faiss (Meta's vector-search library) with build parameter $M = 30$, which caps the bottom layer at $2M = 60$ neighbors per node. The paper's introduction gives the scale: a node with 64 neighbors needs 64 × 4 = 256 bytes for its neighbor list, 25% of a typical 1 KB chunk. Shrinking the graph means deleting edges, and the paper states the choice of which edges as an optimization problem:

$G_1$ is the pruned graph. $\lvert V_i\rvert$ is the number of nodes recomputed at exploration step $i$, so $T(G_1)$ is the total recomputation per search, which is LEANN's latency. Space counts every stored neighbor id at $s_{\mathrm{edge}} = 4$ bytes in a compressed sparse row (CSR) layout, where each node's list is packed end to end with no padding, and $B$ is the disk budget. $\tau$ is the recall floor. The paper does not solve (3) exactly; it uses a one-pass heuristic.

Two obvious heuristics fail. Deleting edges at random, or rebuilding with a uniformly lower degree cap, both lose accuracy even at mild reductions, because they remove connections the walk needs to cross from one region of the graph to another. The paper's Figure 2 shows why the edges are not equally valuable: a small fraction of nodes have degree at or near the cap, and those nodes are visited far more often than the rest. Most walks pass through some of these hubs on the way to the sparsely connected nodes near the answer. Munyampirwa and colleagues reported the same structure in 2024 as a "hub highway", a well-connected and frequently traversed set of hub nodes in high-dimensional graphs.

Hubs appear as a side effect of high dimensionality. In 768 dimensions distances concentrate: the nearest and farthest neighbors of a point differ by a small fraction of their distance. Points that sit slightly closer than average to the center of the data end up in the nearest-neighbor lists of many other points, and when a graph links each point to its nearest neighbors, those points collect many edges without any rule in the construction putting them there.

LEANN's pruning rule (Algorithm 3) keeps the hubs and cuts the rest. It rebuilds the graph by re-inserting every node, with two edge allowances: the top $\beta = 2\%$ of nodes by original degree may keep up to $M$ outgoing edges, and every other node keeps at most $m = M/5$. When a node is inserted, any existing node may accept a back-link from it up to the high cap $M$, not up to its own $m$. A low-degree node therefore picks few edges of its own, but it can still add an edge back to any later node that links to it, up to $M$ edges in total. So it can still point at hubs inserted after it, and hubs stay reachable from everywhere. Degree stands in for traffic because it can be read off the built graph without running any queries. Figure 5 prunes the toy corpus three ways at the same edge budget and searches each result.

The paper's ablation on the real graph starts from an average degree of 18 and halves it to 9 with each method. LEANN's pruning matches the unpruned graph's recall-versus-recomputation curve. To reach the same recall, Random Prune (50% of edges deleted at random) needs up to 1.8× more recomputed nodes, and Small M (a lower degree cap for every node) needs up to 5.8× more; Small M never reaches the 94% and 96% recall targets. At an average degree of 9, packed lists cost 60M × 9 × 4 bytes ≈ 2.2 GB, in line with the 2 GB of metadata the paper reports for LEANN, against HNSW's 15 GB.

Building and updating an index you never hold in full

Building the graph requires searching it, one insertion at a time, and each search needs the embeddings of the nodes it visits. A naive build therefore computes all 60 million embeddings first and holds them (about 173 GB) until the graph is finished, which would require the storage the index exists to avoid. LEANN builds in shards instead (Section 6):

1. Run k-means on a small sample of the corpus to get $k$ centroids.
2. Embed each passage once, record its two nearest centroids, and discard the embedding. Each passage now belongs to two shards.
3. Build one shard at a time: recompute the embeddings of its members, build its graph, discard the embeddings. Peak storage is one shard's embeddings.
4. Merge the shard graphs. A passage in two shards takes the higher of its two HNSW levels and the union of its two edge lists, with edges dropped at random when its degree exceeds $M$.

Assigning each passage to two shards stitches the shards together: passages near a cluster boundary belong to both neighboring shards, so the merged graph contains edges that cross every boundary. The k-means split means each shard links passages to their actual semantic neighbors. Figure 6 builds the toy corpus this way.

With 15 shards on the real corpus, peak construction storage drops about 5×, and the merged graph's recall-versus-recomputation curve nearly matches the original HNSW graph. A randomly sharded graph needs much more recomputation to reach the same recall. Each passage is embedded three times in total (once for the assignment and once in each of its two shards), so the sharded build trades encoder time for peak storage in the same way queries do.

Updates follow the same constraint. Inserting one passage into a graph without stored embeddings costs $O(M \cdot efC + efC^2 + M^3)$ embedding computations, where efC is the candidate-list length used during construction. The three terms are the search for candidate neighbors, the selection among them, and the re-selection of neighbors for every existing node that accepts a back-link. LEANN caches the distances it computes during one insertion so later phases reuse them, and replaces the careful neighbor selection (HNSW's geometric pruning rule) with random selection. Together these bring the cost to $O(M \cdot efC)$, and the paper measures up to a 63.3× speedup over naive insertion (32.91 s down to 0.52 s in its Figure 8).

Batched additions go to a buffer first. A query searches the buffer alongside the graph and merges the two result lists, and the buffered passages are inserted into the graph asynchronously afterwards. Deletion sets a flag on the node. The search still walks through deleted nodes to reach their neighbors, and filters them out of EQ before returning the top $k$. The paper suggests a background rebuild could run once deleted nodes pass a threshold such as 5%, and leaves that policy to future work.

What LEANN costs: storage, latency and accuracy

On the Wikipedia corpus LEANN's index is 4 GB against HNSW's 188 GB, a 47× reduction (the paper rounds to "up to 50×"), and about 5% of the 76 GB of raw text. On the paper's personal-scale datasets (FinanceBench financial filings, the Enron email archive, and LAION images) the storage savings against HNSW are 97%, 98% and 97%.

Latency depends on the dataset, because retrieval effort and generation length both vary. Figure 7 shows one RAG request per method, each tuned to 90% recall@3 on the 60M-passage corpus.

LEANN's retrieval takes 2.48 s on NQ, 2.96 s on TriviaQA, 1.12 s on GPQA and 7.12 s on HotpotQA, which is 10.6%, 14.7%, 1.6% and 23.4% of the request. Against HNSW's 0.04 to 0.05 s the ratio varies: about 50× on NQ, 74× on TriviaQA, 28× on GPQA and 142× on HotpotQA. GPQA, a set of graduate-level science questions, has the smallest overhead because the model reasons at length and generation takes 69.60 s. HotpotQA has the largest because its search is the longest.

Accuracy matches HNSW at the same recall target, 25.5% on NQ, which follows from the embeddings being identical. Against the two baselines that fit in comparable storage, LEANN improves exact match by up to 11.8 points over BM25 and 11.3 over 35×-compressed PQ (F1 by up to 12.0 and 11.1). The gains are largest on NQ and TriviaQA, factual benchmarks where finding the right passage is most of the task. They are smaller on GPQA, whose questions Wikipedia covers poorly, and on HotpotQA, whose multi-hop questions need several retrievals while this setup retrieves once.

The latency argument holds only while generation is slow. On LAION, where generation takes 6.6 s, the overhead is already 20%. On an Apple M1 Ultra, where the encoder runs slower, retrieval takes 13.84 s on NQ (23.4% of the request) and 44.80 s on HotpotQA (50.1%); HNSW and IVF do not run there at all, for lack of memory. A seconds-long search is the wrong tool for search-as-you-type or a server answering many queries per second, and it adds a visible delay in front of a fast cloud model.

The paper measures two further settings. Replacing Contriever (110M parameters) with GTE-small (34M) speeds search up 2.3× with accuracy within 2%, measured on a 2M-document datastore at a fixed ef of 50 rather than on the full corpus. Relaxing the disk budget to cache the embeddings of the highest-degree 10% of nodes gives a 1.5× speedup, with a cache hit rate of up to 41.9%; the same skew in traffic that justifies keeping the hubs makes a small cache effective.

Standard vector indexes treat a distance computation as a memory read, which requires the embeddings to exist on disk. LEANN treats it as an encoder call made on demand. That works because a graph search makes on the order of ten thousand such calls out of 60 million possible ones, and because the resulting seconds sit inside a RAG request whose generation step takes 17 to 70 seconds on the paper's four QA datasets. On the Wikipedia corpus that turns 188 GB of index into 4 GB at the same recall.