Notesstorage🌱 seedling

Approximate Nearest Neighbor

Also: ANN · Approximate Nearest Neighbour · HNSW · IVF · IVFFlat · Vector Index · Vector Quantization

A vector index that returns most of the true nearest neighbours for a tiny fraction of the work of a full scan. Every design exposes a dial that trades recall for speed and memory.

Why it exists

Exact Vector Search is linear in the data. Giving up a little accuracy, measured as recall@k (the fraction of the true top k returned), buys orders of magnitude in latency.

How it works

  • IVF: k-means clusters the vectors; each is filed under its nearest centroid. A query scans only the probes nearest clusters, and misses neighbours just across a cell boundary.
  • HNSW: a layered graph. Every vector is on layer 0, linked to near neighbours; exponentially fewer appear on each higher layer. Search enters at the top, hops greedily toward the query, drops a layer when stuck, and beam-searches layer 0 keeping ef_search candidates.
  • HNSW knobs: m (max links per node per layer), ef_construction (build quality), ef_search (query recall).
  • Quantization shrinks vectors (int8: 4×, binary: 32×); search the compressed copy, then rescore a few extra candidates at full precision.
  • Disk-based graphs (DiskANN) keep compressed vectors in RAM and the graph on SSD to reach billions of vectors per machine.

Trade-offs

HNSW IVF
Speed-recall best in memory lower
Build slow, memory-hungry fast, needs data to train on
Updates inserts costly, deletes awkward cheap; clusters drift over time

In practice

  • pgvector defaults: HNSW m 16, ef_construction 64, ef_search 40; IVFFlat probes 1.
  • Elasticsearch quantizes float vectors by default: int8 HNSW, binary-quantized HNSW for 384+ dimensions, and since 9.4 a disk-based binary-quantized index where licensed.

Pitfalls

  • Filtering after the index starves results: 40 candidates and a 10% filter leave about 4 rows. Use iterative scans, partial indexes, or filter-aware search.
  • Recall is data-dependent. Keep an exact-search ground-truth set and measure after every parameter change.

Recall

These cards are also in your review deck, scheduled with spaced repetition.