Indexing: HNSW, IVF and Quantization

Brute Force Isn't Enough

Searching millions of vectors linearly costs billions of operations per query. Approximate nearest neighbour (ANN) indexes trade a little recall for enormous speed.

HNSW

Hierarchical Navigable Small World builds a layered graph of vectors. Search starts at the top layer and navigates down to find neighbours. Tune the graph size M and the search budget efSearch.

IVF

Inverted File indexes cluster the data first. A query checks its nearest clusters, set by nprobe, and searches only inside them. nlist sets the number of clusters built at index time.

Product Quantization (PQ)

PQ splits each vector into sub-vectors and stores short codes per part. This shrinks memory dramatically, sometimes 10x or more, at a small recall cost.

Choosing a Strategy

• Under a million vectors - HNSW or plain brute force.
• Millions of vectors - HNSW or IVF with PQ.
• Tight memory budget - PQ or scalar quantization.
• Maximum recall - Small M, high efSearch, no quantization.

Key Points

• ANN gives speed while sacrificing a little accuracy.
• HNSW is graph based and easy to start with.
• IVF clusters data and probes the nearest groups.
• PQ compresses vectors to save memory.