ANN Indexes: HNSW, IVF and PQ

Exact nearest neighbour search over \(N\) vectors of dimension \(d\) costs \(O(Nd)\) per query. At 10 million chunks and 1024 dimensions that is roughly 40 GB of float32 arithmetic per query, which is fine as a batch job and hopeless at 50 queries per second. Every vector database is therefore an approximate index, and the approximation is not a defect to be engineered away. It is the product: you choose how much recall to give up for latency and memory, and the choice is different for a 100k-chunk internal wiki than for a billion-vector web index.

Three families

Graph-based: HNSW. Hierarchical Navigable Small World builds a multi-layer proximity graph where each node links to its approximate neighbours; upper layers are sparse and used for coarse navigation, lower layers dense for refinement (Malkov & Yashunin, 2016, arXiv:1603.09320). Search is greedy descent, roughly logarithmic in \(N\). It dominates recall-per-query-time benchmarks and is the default in FAISS, Qdrant, Weaviate, Milvus and pgvector. The cost is memory: the full float vectors plus the graph, typically \(M \times 2\) links per node, all of which wants to be in RAM.

Cluster-based: IVF. An inverted file index runs k-means over the corpus, assigns each vector to a centroid, and at query time scans only the nprobe nearest lists. It builds fast and uses far less memory than a graph, but its recall degrades badly when the query lands near a cluster boundary, and it needs a training pass whenever the data distribution shifts.

Quantisation: PQ and friends. Product quantisation splits each vector into subvectors, replaces each with a codebook index, and computes distances from lookup tables (Jégou, Douze & Schmid, 2011, Product Quantization for Nearest Neighbor Search, IEEE TPAMI 33(1)). A 1024-dim float32 vector at 4 KB becomes 64 bytes at 64x compression. PQ is not an index by itself; it is a compression layer usually stacked on IVF (IVF-PQ) or on a graph. Google's ScaNN improves the quantisation objective by weighting errors along the query direction that actually change the inner product ranking (Guo et al., ICML 2020, arXiv:1908.10396).

Disk-resident: DiskANN. For corpora that will not fit in RAM at any price, DiskANN keeps a compressed representation in memory for navigation and reads full vectors from SSD only for the candidates it must rerank, serving billion-point indexes from a single node (Subramanya et al., NeurIPS 2019).

The knobs that actually matter

ef_search is the one to remember: it is a per-query runtime parameter, so recall can be traded for latency on the fly, per tenant or per query class, without rebuilding anything. M and ef_construction are baked in at build time.

Filtering is where indexes fail

Real queries are rarely pure vector search. They are "nearest neighbours where tenant_id = 42 and updated_at > 2026-01-01". Two naive approaches both break: pre-filtering to a candidate set destroys the graph's connectivity assumptions, and post-filtering the top-k can return nothing at all if the filter is selective. Production systems use filtered search that evaluates the predicate during traversal, and this is the axis on which vector stores genuinely differ. Benchmark filtered recall on your own filter distribution, because published QPS numbers are almost always unfiltered.

When it breaks

Recall is measured against exact search on a sample, and most teams never measure it. An index quietly running at 0.8 recall@10 loses one relevant document in five before the reranker ever sees the candidates, and no amount of downstream cleverness recovers it.

Other failure modes: deletion in a graph index is usually a tombstone, so a high-churn corpus fragments and needs periodic rebuilds; PQ recall collapses on out-of-distribution data because the codebooks were trained on the old distribution; and normalising for cosine similarity but querying with L2 (or the reverse) produces a working system with silently wrong rankings. See cosine similarity vs dot product for why that mismatch matters.