LEANN Architecture: Query-Time Embedding Recomputation, High-Degree-Preserving Graph Pruning, and the Latency Ledger Behind a 97% Storage Cut for Vector Search

RETRIEVAL SYSTEMS

The MLSys 2026 best-paper vector index deletes the one thing every ANN system assumed it had to keep: the embeddings. What remains is a pruned proximity graph, coarse codes for pruning, and an encoder that runs at query time.

By Ossam Hashim

KEY FINDINGS

What the paper and the project establish

• LEANN removes stored embeddings entirely: it keeps a compressed proximity graph plus high-ratio product-quantization codes, and recomputes exact embeddings on the fly with the same encoder used at build time.
• On the paper's reference RAG workload (76 GB text corpus, Qwen3-4B, RTX 4090) the index drops from 188 GB for HNSW (173 GB vectors + 15 GB graph) to 4 GB, while downstream QA accuracy matches HNSW exactly at 25.5% - and product quantization alone at the same budget falls below BM25 keyword search.
• The enabling observation is a latency ledger: generation dominates RAG end-to-end time (~21 s vs ~0.05 s search), so LEANN spends about 2.4 s of extra search time - roughly 10% end-to-end - to buy more than 50x storage reduction.
• Two mechanisms make recomputation affordable: a two-level search that uses coarse PQ distances to prune which nodes get recomputed, and dynamic batching that aggregates recomputation across graph hops to keep the GPU busy.
• Graph metadata is attacked separately: a high-degree-preserving pruning keeps hub-node edges (hubs carry most search traffic) while dropping low-utility edges of low-degree nodes, with the graph stored in CSR format and built through a storage-bounded sharded merge pipeline.
• The project is moving fast in the open: MLSys 2026 best paper per the repository, v0.3.9 on October 27, and a Claude Code integration whose repo-reported ContextBench run shows 2.1x initial relevant-code recall over BM25 on 30 SWE-Bench Pro tasks at equal retrieval budget.

The Storage Wall in Vector Search

A RAG index is usually larger than the data it indexes. The paper's reference point makes it concrete: a 76 GB text corpus needs 173 GB of embeddings plus 15 GB of HNSW graph metadata - 188 GB of index for 76 GB of content, which is what keeps serious semantic search off personal devices. The standard answer is vector quantization, but the arithmetic turns hostile at the required ratios: squeezing those vectors to about 5 GB demands roughly 35x compression, and at that ratio the paper's own table shows PQ accuracy degrading past keyword search (17.9% versus BM25's 18.3%). Our Matryoshka and binary-quantization analysis covered the smarter end of that compression family; LEANN sidesteps the family entirely. And the 15 GB graph cannot be quantized away at all - it needs its own treatment.

Recompute, Don't Store

The first insight is that a graph index query touches very few vectors: an HNSW search visits a small candidate set along its hops. So why store every embedding? LEANN stores none of them. At query time it navigates using cheap approximate distances from high-ratio PQ codes, and only for the nodes that survive pruning does it call the encoder to recompute the true embedding - the two-level search. Because a naive recompute-per-hop would serialize encoder calls, a dynamic batching mechanism pools recomputation across hops so the GPU sees batches instead of singletons. The encoder must be the same one used at build time; the index is effectively the graph, the codes, and the model.

Prune the Graph, Keep the Hubs

The second insight targets the graph itself. Adjacency lists are not cheap: a node with 64 neighbors costs 256 bytes of metadata, a quarter of a typical 1 KB text chunk. But proximity graphs are heavy-tailed - high-degree hub nodes are visited far more often than low-degree ones - so LEANN prunes asymmetrically: hub nodes keep their edges, low-degree nodes lose their low-utility ones. The pruned graph is stored in CSR form, index construction runs as a sharded merging pipeline that never exceeds a small storage budget, and updates are supported on the compressed index. The worked example below reproduces both the two-level recomputation trade and the degree-aware pruning on toy data.

What the Latency Ledger Buys

LEANN's whole design is a bet on workload shape. On the reference setup, search goes from 0.05 s to 2.48 s - a 50x slowdown that costs about 10% end-to-end because response generation already takes 21 s. Interactive pure-search workloads would not accept that trade; agentic and RAG workloads, where an LLM dominates the bill, barely notice it. The return is deployment surface: private on-device RAG over email, files, and browser history with no cloud and no embedding store to sync. The repository's Claude Code integration benchmark (30 SWE-Bench Pro tasks, fixed model and 8,192-token retrieval budget) reports 24.2% versus 11.4% initial relevant-code recall against BM25 and 8.4% fewer tokens spent - repo-reported, macro-averaged gold-line metrics, and the authors themselves note better context access does not guarantee issue resolution.

Assumptions and limitations: the example is a didactic toy - real LEANN uses learned PQ codebooks, HNSW/DiskANN graphs, GPU-batched encoder calls, and benchmark corpora. All figures cited (188 GB vs 4 GB, accuracy and latency numbers, 97% savings, ContextBench recall) are from the paper or the repository README and are author-reported, not independently verified here. Latency acceptability depends on workload shape; pure low-latency search is not the target use case.

Worked Example: Two-Level Recompute and Degree-Aware Pruning

The script models LEANN's two trades at toy scale. Forty deterministic vectors stand in for a corpus; three-bit codes rank all of them cheaply, exact distance is "recomputed" only for the twelve best candidates, and we measure recall against a full exact scan. Then a tiny heavy-tailed graph loses the adjacency lists of its low-degree nodes while the hub keeps its edges.

import random

def vec(i):
    r = random.Random(i)
    g = r.random
    return [g() for _ in range(8)]

def d2(a, b):
    s = 0.0
    for x, y in zip(a, b):
        s += (x - y) ** 2
    return s

def q(v):
    return [int(x * 8) for x in v]

def rank(cand, t, store):
    def key(i):
        return d2(t, store[i])
    return sorted(cand, key=key)

vecs = [vec(i) for i in range(40)]
qv = [q(v) for v in vecs]
query = [x + 0.01 for x in vecs[3]]
qq = q(query)
ids = list(range(40))
top5 = rank(ids, query, vecs)[:5]
cand = rank(ids, qq, qv)[:12]
approx = rank(cand, query, vecs)[:5]
hit = len(set(top5) & set(approx))
print("recall@5:", hit / 5)
n = len(cand)
print("recomputed:", n, "of 40")

g = {0: [1, 2, 3, 4], 1: [0, 2],
     2: [0, 1], 3: [0], 4: [0]}
deg = {}
for i, e in g.items():
    deg[i] = len(e)
hub = max(deg, key=deg.get)
kept = {}
for i, e in g.items():
    if deg[i] >= 2 or i == hub:
        kept[i] = e
n0 = sum(deg.values())
n1 = 0
for e in kept.values():
    n1 += len(e)
print("edges:", n0, "->", n1)

Assumptions and limitations: the example is a didactic toy - real LEANN uses learned PQ codebooks, HNSW/DiskANN graphs, GPU-batched encoder calls, and benchmark corpora. All figures cited (188 GB vs 4 GB, accuracy and latency numbers, 97% savings, ContextBench recall) are from the paper or the repository README and are author-reported, not independently verified here. Latency acceptability depends on workload shape; pure low-latency search is not the target use case.

Sources & Provenance

• LEANN paper (arXiv, MLSys 2026 best paper per repository) - mechanism, Table 1 figures
• StarTrail-org/LEANN repository - README claims, ContextBench numbers, release v0.3.9
• MarkTechPost coverage (Oct 27, 2026) - news report on the MLSys 2026 award

Analysis is based on the primary sources listed above; benchmark claims are attributed to their authors and not independently verified.