Disk-Based ANN Search and DiskANN

A billion 1,536-dimensional float32 embeddings occupy about 6.1 TB. An in-memory graph index such as HNSW wants vectors and graph in RAM, so at this scale the choice is a cluster of large-memory machines or a different design. DiskANN is the different design: its authors indexed and searched a billion points on one workstation with 64 GB of RAM and an inexpensive SSD, serving over 5,000 queries per second at under 3 ms mean latency and above 95% 1-recall@1 on SIFT1B (Subramanya et al., 2019, DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, NeurIPS). Choosing an index family places this among the options.

The budget is round trips

On a retail SSD a random read takes a few hundred microseconds, far longer than a distance computation, so the cost that matters is how often search waits on the disk. The authors targeted under ten round trips per query, preferably five.

Five round trips at 300 microseconds each is 1.5 ms of waiting. The paper reports search threads spending 40 to 50% of query time in I/O, which puts such a query at roughly 3 ms end to end. Double the hops and latency roughly doubles.

Vamana: a graph built for few hops

Vamana, the graph, adds one parameter to pruning. For a node \(p\) with candidate neighbours \(V\), RobustPrune repeatedly takes the closest remaining candidate \(p^*\), adds it as an out-neighbour, and discards every remaining candidate \(p'\) for which

up to a maximum out-degree \(R\). With \(\alpha = 1\) this is the relative-neighbourhood pruning HNSW and NSG use implicitly. With \(\alpha > 1\) fewer candidates are discarded and more long-range edges survive. In the idealised case where pruning considers every point, the authors show greedy search then shrinks its distance to the target by a factor of \(\alpha\) per step and converges in logarithmically many steps. Construction makes two passes, the first at \(\alpha = 1\) and the second at the user's \(\alpha\); the billion-scale experiments used 2.

Measuring hops for 98% 5-recall@5 as maximum degree grew, the authors found HNSW and NSG stagnating while Vamana kept reducing hops: larger \(R\) with \(\alpha > 1\) buys long edges, not redundant short ones.

Layout: what lives where

In RAM: a product-quantised code per vector, for example 32 bytes, which is 32 GB for a billion points.

On SSD: each node's full-precision vector followed by up to \(R\) neighbour IDs, padded to a fixed size so offsets are computed, not looked up. At \(R = 128\) with 4-byte IDs the neighbour list is 512 bytes, and with the vector it fits in one 4 KB sector.

Beam search expands the \(W\) closest unvisited candidates per round, fetching their sectors in parallel, since reading a few random sectors costs about as much as one. \(W\) of 2, 4 or 8 balanced latency and throughput; 16 or more wasted compute and SSD bandwidth.

Implicit re-ranking comes free: each sector read for neighbours also delivers that node's full vector, so results are re-ranked with exact distances, recovering the recall PQ loses. Caching nodes within 3 or 4 hops of the entry point removes the first round trips from every query.

Build must fit the machine too. A one-shot SIFT1B build peaked near 1,100 GB of memory. The alternative assigns each point to its 2 nearest of 40 k-means shards, builds a graph per shard and unions the edges, finishing in about five days under 64 GB for at most about 20% extra latency.

Fresh and Filtered DiskANN

Graph indexes decay under churn: repeatedly deleting and re-inserting 5% of SIFT1M sparsifies HNSW, NSG and Vamana graphs under naive updates, and recall falls. FreshVamana keeps \(\alpha > 1\) pruning during updates, deletes lazily (deleted nodes stay navigable but are filtered from results) and consolidates in batches. FreshDiskANN pairs a small in-memory index for recent writes with the SSD index and merges them in the background; it sustained 1,800 inserts and 1,800 deletes per second alongside 1,000 searches per second at over 95% 5-recall@5 in under 128 GB of RAM (Singh et al., 2021, FreshDiskANN, arXiv:2105.09613). See freshness, deletes and index maintenance.

Filtered-DiskANN makes labels part of construction: each label gets its own start node, and pruning preserves edges between points sharing a label. The authors report order-of-magnitude gains over baselines, near-100% recall for filters matching as few as \(10^{-4}\) to \(10^{-6}\) of points, and 30 to 80% revenue gains in a sponsored-ads deployment, the last an internal production figure (Gollapudi et al., 2023, Filtered-DiskANN, WWW, doi:10.1145/3543507.3583552). See also filtered vector search.

When it breaks

Graph-on-disk is not the only answer. SPANN keeps cluster centroids in memory and posting lists on disk, and its authors report reaching 90% recall about twice as fast as DiskANN at equal memory (Chen et al., 2021, SPANN, NeurIPS, arXiv:2111.08566). Which family wins depends on recall target and hardware; the two camps' benchmarks do not settle it.

Out-of-distribution queries cost hops. When query embeddings differ in distribution from the indexed data, as with text queries against image vectors, graph search latency can worsen by an order of magnitude; OOD-DiskANN recovers part of it by using a query sample during construction (Jaiswal et al., 2022, arXiv:2211.12850).

Storage latency is the whole budget. A network volume with millisecond reads multiplies per-hop cost, and a saturated SSD pushes reads past a millisecond, which is why the paper held SSD load at 30 to 40%.

PQ routing degrades in high dimensions. When 32-byte codes summarise 1,536 dimensions poorly, the beam expands the wrong nodes; re-ranking fixes the final order, not the path.