Vector Index Structures: HNSW, IVF, and Friends

Every vector database is built on three ideas. Once they click, every decision downstream gets easier.

HNSW is a multi-level road network. The top layer has a handful of nodes wired together with long-range links, the highways. Each layer below adds more nodes with shorter links, the state roads and side streets. A search starts at the top, greedily works toward the right neighborhood, then drops down through the layers to find the exact neighbors. You get recall above 0.99 at around 1ms. You pay for it in memory, since you're holding the full graph plus every vector.

IVF is a library split into sections. You cluster all the vectors into partitions around centroids, and at query time you find the nearest centroids and only search those partitions. The nprobe setting is the dial: search more partitions for higher recall, fewer for lower latency. Moderate memory, very tunable.

PQ is lossy compression for vectors. You chop each 1024-dimensional vector into subvectors and snap each one to a codebook entry, so a 4KB vector shrinks to a 128-byte code, 32 times smaller. You compute approximate distances on the compact codes, then re-rank the top candidates with the full vectors to get the precision back.

The interesting part is that these compose. IVF plus PQ partitions and then compresses, which is the standard for billion-scale search. HNSW plus PQ navigates on compressed distances and verifies with full vectors. Every production system is really just picking a point on one triangle: recall, latency, memory.