Skip to main content
Back
45 XP

Lesson 3 · 11 min

ANN algorithms — HNSW, IVF, PQ

Exact nearest-neighbor doesn't scale. The three approximate techniques every vector DB is built on, with the trade-offs each makes.

Why approximate

Exact nearest-neighbor on N vectors is O(N) per query. At 100M vectors that's not happening in 50ms. Approximate nearest neighbor (ANN) trades a small recall loss for orders of magnitude speedup.

Three techniques dominate:

  • HNSW (Hierarchical Navigable Small World) — the default in 2026. Graph-based. Build a multi-layer graph where each node points to its near neighbors; search by walking the graph from a top-layer entry point. Fast recall (>95%) at sub-50ms on 10M+ vectors.
  • IVF (Inverted File) — partition the space into K clusters; at query time, search only the closest few. Cheap memory; slightly worse recall than HNSW.
  • PQ (Product Quantization) — compress vectors by splitting into sub-vectors and quantizing each. Reduces memory 8-32×; pairs with IVF for IVF-PQ.