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
probesnearest 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_searchcandidates. - 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
m16,ef_construction64,ef_search40; IVFFlatprobes1. - 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.
Connections
- Part of
- Vector Search
- In real systems
- pgvectorElasticsearch
Recall
These cards are also in your review deck, scheduled with spaced repetition.