Choosing an Index Family

Approximate nearest-neighbour indexes trade three quantities against each other: recall, query latency and memory. No index optimises all three, so the choice is determined by which one the workload cannot compromise on, and by properties of the collection that most benchmarks do not vary.

The families and what selects them

Flat, meaning exact search, computes every distance. Perfect recall, no build time, trivially supports any filter, and linear query cost. It is the right answer below roughly a hundred thousand to a million vectors depending on dimension and latency budget, and it is chosen far less often than it should be.

Graph indexes such as HNSW navigate a proximity graph from an entry point. Excellent recall at low latency, native support for incremental insertion, and high memory cost because the graph is stored alongside the vectors. It is the default for a collection that fits in memory and needs low latency.

Inverted file partitioning clusters vectors and searches only the nearest partitions. Lower memory than a graph, tunable recall through the number of partitions probed, and it degrades as the data distribution drifts from the clustering. It suits large collections where memory matters and a periodic rebuild is acceptable.

Quantisation-based indexes compress vectors into codes and compute approximate distances on them. Dramatic memory reduction, at a recall cost usually recovered by reranking the top candidates with full-precision vectors. Product quantisation combined with IVF is the standard construction for collections too large to hold uncompressed.

Disk-resident graph indexes such as DiskANN keep the graph on SSD with a compressed in-memory representation for routing, which changes the memory constraint from collection size to a fraction of it, at a latency cost bounded by SSD random-read performance.

Reading a benchmark

Published comparisons report recall against queries per second, and the curve's shape matters more than any point on it. Two things need checking before a number transfers.

The build configuration, since HNSW at a high connectivity parameter and a high construction effort is a different index from the same algorithm at low settings, and the memory and build time differ by multiples.

The dataset's dimensionality and intrinsic structure, because index behaviour depends heavily on both. A method that wins on 128-dimensional SIFT descriptors may lose on 1,536-dimensional text embeddings, whose intrinsic dimension and neighbourhood structure differ substantially.

When it breaks

Benchmarks measure the wrong workload. They use a fixed collection, no filters, no updates and single-tenant access. Filtering and mutation both degrade every family, and they degrade them differently, so a benchmark ranking does not predict a production ranking.

Recall is reported at a convenient operating point. A method's advantage frequently exists only in one region of the recall-latency curve, so a comparison at 90 percent recall can reverse at 99 percent. The operating point your application needs is the one to compare at.

Build time is omitted and is operationally significant. An index that takes eight hours to build constrains how often you can rebuild, which interacts directly with how much index degradation you must tolerate between rebuilds.

Parameter sensitivity differs by family. Graph indexes are relatively forgiving; partition and quantisation methods have parameters whose wrong setting costs a great deal of recall. A family that performs well only under careful tuning is a different operational commitment from one that works at defaults.