DiskANN & Billion-Scale Search

Put the graph on SSD, keep a compressed copy in RAM to steer, and serve a billion vectors from one machine.

Advanced Vector Search · Advanced · ~6 min

In plain English

A library too big for your desk. You keep an index card for every book in a drawer you can reach, and walk to the shelf only for the handful you actually need.

Why it's worth your time

RAM costs about a hundred times what NVMe does per byte, and at a billion vectors that ratio decides whether the system is one machine or forty.

If you remember three things

Vamana graph: low diameter, because each hop is a disk read
RAM holds PQ codes for navigation only
Exact vectors are read from disk, so accuracy isn't capped by compression

Overview

HNSW assumes the graph and the vectors live in RAM, which caps a single node at tens of millions of vectors. DiskANN removes that assumption. It builds a Vamana graph — a single flat layer with a controlled long-range degree, designed so a greedy search converges in few hops, because each hop is now an SSD read. The full-precision vectors and adjacency lists live on disk; RAM holds only PQ-compressed vectors used to decide which neighbour to visit next. A search does a few dozen random reads instead of a few million, and the candidates it returns are rescored against the exact vectors it fetched along the way. FreshDiskANN adds in-place updates so the index isn't rebuild-only.

In an interview

DiskANN serves billion-scale vector search from a single machine by putting the graph and full vectors on NVMe and keeping only PQ-compressed vectors in RAM to guide traversal. Its Vamana graph is built to converge in few hops, because every hop is a disk read. Candidates are rescored with the exact vectors fetched during the walk, so the compression used for navigation doesn't determine final accuracy.

Production defaults

Build: graph_degree R ≈ 64, build complexity L ≈ 128. Higher R means bigger reads but fewer hops
Hardware: local NVMe, not network storage. Measure random-read IOPS first; the design lives or dies on it
Cache: pin ~1% of nodes (the hubs) in RAM — it removes a disproportionate share of reads

What breaks

Latency is hundreds of milliseconds — You're on network or spinning storage. This design assumes NVMe random reads; nothing else in the config will fix it.
Updates require a full rebuild — That's the static index. Use FreshDiskANN's in-memory delta with periodic merge if the corpus changes.

Watch it explained

Research talk: Approximate nearest neighbor search systems at scale — Microsoft Research, 9:33