Vector Database Index Types - HNSW vs IVF

Choosing the right index type is the most important performance decision when building a vector database. Flat indexes (brute force) guarantee 100% recall but take O(n) time per query - acceptable for thousands of vectors but unusable at millions. Approximate Nearest Neighbour (ANN) indexes like HNSW and IVF trade a small accuracy loss for orders-of-magnitude faster query times, enabling sub-millisecond search across millions of product embeddings.

HNSW (Hierarchical Navigable Small World) builds a graph structure that enables logarithmic search time. It delivers the best query speed and recall but requires significant memory for the graph structure. IVF (Inverted File Index) partitions vectors into clusters and only searches the nearest clusters at query time - lower memory usage but slightly slower and less accurate than HNSW. IVF+PQ (Product Quantisation) compresses vectors further, enabling billion-scale indexes on a single machine.

The below example benchmarks Flat, IVF, and HNSW indexes using FAISS on a simulated ShopMax India product catalogue to show the speed and recall tradeoffs at different scales.

It gives the following output,

Index      | Latency (ms) | Recall@5
----------------------------------------
Flat       |        38.21 | 1.000 (exact)
IVF        |         1.84 | 0.800
HNSW       |         0.43 | 1.000

HNSW is 89x faster than Flat with perfect recall at this scale. IVF is 20x faster but misses 1 in 5 results with nprobe=10 - increase nprobe to improve recall at the cost of speed. For ShopMax India, use HNSW for catalogues up to 10 million products where memory allows (HNSW uses roughly 1.5GB per million 384-dim vectors). Use IVF+PQ for catalogues above 10 million products where memory is the binding constraint.