What is the trade-off in choosing an ANN index?
The trade-off in choosing an ANN index is that every family buys speed, memory savings, or update flexibility by giving up something else – usually a slice of recall, build cost, implementation complexity, or exactness – so the “best” index is the one whose compromises match your workload rather than the one that wins a single benchmark chart.
Which axes actually move when you pick an index family?
Recall versus latency is the headline curve: how much of the exact top-k you recover at what delay, measured against a brute-force baseline. Memory footprint separates in-RAM graphs from partition-and-code designs. Build time and mutability separate incremental HNSW inserts from batch-trained IVF/PQ reclustering or immutable tree forests. Dimensionality sensitivity separates low-dimensional trees from methods that survive embedding-scale spaces. Operational axes – filtered search, multi-tenancy, sharding, and crash recovery – often dominate lab metrics once you leave a notebook. Choosing an index means ranking these axes for your product, then picking the taxonomy branch that fails least on the ones you ranked highest.
Those rankings push different teams toward different default families.
How do the main ANN families typically land on that trade-off surface?
Graph indexes such as HNSW often deliver strong recall at low latency for large dense embeddings with ongoing inserts, at the cost of substantial RAM for edges and vectors – the reason vector databases like Weaviate default many large collections there. Partition-based ANN (IVF and kin) and product-quantization indexes trade routing risk and training/recluster cost for tighter memory and explicit scan budgets via nprobe. Hashing-based ANN fits threshold-shaped similarities and sketches but can struggle on top-k embedding rankings without careful tuning. Trees excel in modest dimensions with geometric pruning and falter as dimensionality grows. Flat exact search maximizes recall and simplicity until N makes linear scans intolerable. Hybrids and two-level structures buy extra axes by stacking stages, paying in complexity and handoff bugs.
A fair choice therefore starts from constraints, not from algorithm fashion.
What decision process keeps the trade-off honest?
Write down non-negotiables first: target recall@k, p95/p99 latency, QPS, RAM ceiling, update freshness, and filter requirements. Generate ground truth with exact search on representative queries. Sweep the knobs that belong to each candidate family – efSearch for graphs, nprobe and lists for partitions, probes for hashes – and plot recall-versus-latency on the same hardware. Include build time and steady-state memory, not only query speed. Test the update path you will actually run; an index that wins a static snapshot may lose under continuous ingest. Prefer the simplest family that clears the SLO; add compression or a second level only when measurements show a specific gap. Revisit after embedding-model changes – the trade-off surface moves when the vector distribution moves.
The goal is an operating point you can defend, not a universal winner.
What mistakes commonly warp the choice?
Reporting peak QPS without a latency percentile, or singleton latency without concurrent load, hides the throughput-versus-latency trade inside serving. Comparing quantized search to a float baseline without saying so mixes compression error with index error. Ignoring deletes, filters, and cold cache produces optimistic lab numbers. Overfitting knobs to one dataset makes the next corpus look like a regression. The remedy is the same taxonomy discipline used throughout this chapter: name the candidate generator, measure against exact neighbors, and accept that every ANN index is a negotiated compromise.
Choosing an ANN index means picking which compromises – recall, memory, build cost, complexity – you can afford for the speed you need. From here, the taxonomy of ANN methods recaps the families you are choosing among, Navigable Small World and related graph algorithms open the next glossary section on graph ANN in more depth, benchmarking pages elsewhere quantify recall-versus-latency curves, and HNSW-focused chapters on this site show how one popular compromise is tuned in practice.