Why architecture matters here
The architecture exists because two costs are in direct tension and the naive designs each lose one of them. Keep everything in RAM and you get low latency and high recall but pay for terabytes of memory per replica — a cost that scales linearly with corpus size and replica count and quickly dominates the entire system budget. Push everything to disk naively and RAM cost vanishes but each query becomes hundreds of random SSD reads, and even fast NVMe tops out at a few hundred thousand IOPS, so latency and throughput collapse. DiskANN's whole reason for being is to get most of the RAM savings while keeping the number of SSD reads per query small enough — single or low double digits — that NVMe latency stays inside the budget.
The key realization is that the number of SSD reads is a function of graph diameter and search width, and both are things you can engineer at build time. If the graph is navigable — if a greedy walk from an entry point reaches the neighborhood of any query in a few hops — then a search visits few nodes, and each visited node is one SSD read for its neighbor list and stored vector. Vamana is precisely a construction that trades a little extra work at build time to guarantee that navigability, using long-range 'shortcut' edges alongside local ones so the walk covers distance fast and then refines locally. A high-diameter graph would force many hops, many reads, and blow the latency budget; the whole design is organized around keeping the walk short.
The second realization is that you do not need full precision to decide where to walk next. Choosing which neighbor to expand only requires relative distance estimates, and product quantization gives you those cheaply from a compressed representation that fits in RAM at a fraction of the size — often 32× smaller than the raw vectors. So the search steers using PQ-estimated distances entirely in memory, and pays for exact distances (a full-vector SSD read) only at the very end, for the small candidate set it will actually return. This split — cheap approximate guidance in RAM, expensive exact confirmation on disk, minimized — is the heart of why DiskANN works, and getting the balance right is the whole game.
Understanding this changes how you reason about tuning. Every operational lever — beam width, PQ code length, node cache size — is really a knob on one of two quantities: how many SSD reads a query issues, and how accurate the in-memory guidance is. Latency and recall are the two outputs; SSD reads and PQ fidelity are the two inputs; and DiskANN operations is the art of trading between them for your specific corpus and SLA.
It also reframes what 'scaling' means. In a memory-resident index, scaling to more vectors means buying more RAM, linearly and expensively, until a single machine cannot hold the corpus and you shard across a fleet. In DiskANN the dominant cost is SSD capacity — dramatically cheaper per gigabyte than RAM — and the RAM requirement grows only with the compressed PQ footprint, a small constant fraction of the raw data. A corpus that would demand terabytes of RAM needs only tens of gigabytes of PQ codes plus an SSD large enough to hold the graph and vectors. That is why DiskANN turns a fleet-sized memory bill into a single-node disk bill, and why the design's economics, not just its algorithms, are the reason it exists.
The architecture: every piece explained
Top row: the query path in memory. A query vector enters at a fixed medoid entry point. The PQ table in RAM holds every database vector compressed into a short code — each vector split into sub-vectors, each sub-vector quantized to a centroid id — so an approximate distance from the query to any node is a few table lookups and additions, no SSD read required. Beam search is the driver: it maintains a candidate list of the closest-seen nodes and, each step, expands the best unexpanded ones, using PQ distances to rank. Expanding a node requires its neighbor list, which triggers SSD reads — and because Vamana keeps neighbor lists and the node's full vector co-located on disk, one read fetches both.
Middle row: the data on disk and the refinement. The Vamana graph is the on-disk adjacency structure — each node's out-neighbors, chosen at build time to include both nearby nodes (local refinement) and some distant ones (fast coverage), with the out-degree capped so a neighbor list plus vector fits in a single disk page. The full vectors sit beside their neighbor lists so no second read is needed. Once beam search has converged on a candidate set, re-rank computes exact distances using those full-precision vectors — correcting the approximation error PQ introduced — and produces the top-k result with the recall the SLA demands. The re-rank is why DiskANN's recall is not hostage to PQ's lossy compression: PQ only has to be good enough to get the right candidates into the beam, not to rank them perfectly.
Bottom rows: build and cache. Build uses Vamana's robust-prune rule with an alpha parameter that controls how aggressively edges are kept: alpha slightly above 1 forces the graph to retain longer 'diversifying' edges that shrink diameter, directly reducing query-time hops at the cost of a denser graph. Cache keeps the hottest nodes — the entry point's neighborhood and frequently traversed hubs — resident in RAM, cutting the SSD round-trips that every query would otherwise repeat near the entry point. The ops strip names the real dials: beam width (candidates expanded per step — more recall, more reads), the IOPS budget the SSD can sustain under concurrency, recall@k monitored against ground truth, and the strategy for handling inserts and deletes, which graphs handle far less gracefully than a flat index.
End-to-end flow
Trace a single k=10 query over a billion-vector index on one NVMe machine. The query embedding arrives and search starts at the precomputed medoid. Beam search initializes its candidate list with the medoid, whose neighborhood is warm in the RAM cache, so the first expansion costs no SSD read. Using PQ-estimated distances, the beam picks the most promising unexpanded candidates — say a beam width of 4 — and expands them.
Expanding a candidate not in cache issues one SSD read that returns both its neighbor list and its stored full vector. Those neighbors get PQ-scored against the query in RAM and inserted into the candidate list if they improve on the current worst. The walk proceeds greedily: a few hops of long shortcut edges cover most of the distance from the medoid to the query's region, then local edges refine within that region. Because Vamana kept the diameter small and the beam is narrow, the whole search converges after visiting on the order of a hundred nodes — but with caching and the beam's re-expansion of already-fetched nodes, the actual SSD reads number in the low tens, each a sub-100-microsecond NVMe access, pipelined so their latencies overlap.
When the beam stops improving, DiskANN has a candidate set of, say, the 40 closest nodes by PQ distance — deliberately larger than the final k because PQ is approximate and the true top-10 might be ranked slightly wrong under compression. Now re-rank runs: for each candidate, the full-precision vector (already fetched during traversal, or read now if not) is used to compute the exact distance, the 40 are re-sorted, and the true top-10 are returned. The re-rank is what turns 'PQ got roughly the right neighborhood' into 'the answer has the recall we promised.'
Now the stress cases. Suppose the query lands in a sparse region of the embedding space where the graph has few good edges; the beam wanders, issuing more reads and returning lower recall — visible as a latency and recall outlier that operations can trace to under-connected regions and fix by rebuilding with a higher degree or alpha. Suppose instead concurrency spikes: a thousand simultaneous queries each wanting a dozen SSD reads can exceed the drive's IOPS ceiling, and latency degrades not per-query but system-wide as reads queue. The fix is not code but capacity planning — the node cache absorbs the hottest reads, but sustained throughput is ultimately bounded by IOPS, which is why DiskANN deployments budget concurrency against measured drive performance rather than assuming reads are free.