Developer/AI/VectorStores/Fundamentals/vector-index-selection-hnsw-vs-ivf

Vector Index Selection: HNSW vs IVF

Concept

A vector database's job is approximate nearest-neighbor (ANN) search: given a query embedding, find the k stored vectors most similar to it, fast, without literally comparing the query against every stored vector (a linear scan is exact but stops scaling once the collection reaches more than a few hundred thousand vectors — every RAG or "find similar X" feature past a trivial dataset size needs an actual index). Two index families dominate production usage, and they trade off recall, query latency, memory, and write behavior in different directions — there is no index that wins on all four simultaneously.

HNSW (Hierarchical Navigable Small World) builds a multi-layer graph where each vector is a node connected to its approximate nearest neighbors; a query walks the graph greedily from a coarse top layer down to a fine bottom layer, following edges toward closer and closer vectors. This structure is what gives HNSW its strengths: it reaches 95%+ recall largely out of the box with little tuning, and because it's a graph rather than a fixed partitioning, new vectors can be inserted directly without a full index rebuild — a real advantage for a corpus under active write load. The cost is memory: the graph's edges have to live alongside the vectors themselves, and HNSW typically uses 2-5x more memory than IVF-based alternatives for the same vector count.

IVF (Inverted File Index) takes a different approach: it clusters the vector space (typically with k-means) into a fixed number of partitions ("cells") ahead of time, and at query time first identifies the few cells closest to the query, then does an exact or near-exact scan only within those cells. This is far more memory-efficient than HNSW — there's no graph to store, just cluster assignments — and a typical configuration searching 10 of 1,000 cells inspects roughly 1% of all vectors while still holding recall above 90%. The cost shows up on writes: because the clustering is computed up front, adding vectors after the fact means either accepting a stale clustering (a new vector doesn't perfectly fit its assigned cell) or periodically re-running k-means and rebuilding the index — IVF is a better fit for large, relatively static datasets than for a corpus with a continuous write stream.

Tradeoffs

Index	Recall	Query speed	Memory	Write behavior
HNSW	Excellent (95%+ out of the box, minimal tuning)	Fast, consistent	High — 2-5x IVF for the same vector count, whole graph typically resident in memory	Handles inserts directly, no rebuild required — good fit for actively-written corpora
IVF (IVFFlat)	Good, tunable via number of cells searched (`nprobe`) — more cells searched trades speed for recall	Fast when few cells searched; degrades as more cells are searched for higher recall	Low — no graph overhead, scales more cheaply to very large collections	Degrades under continuous writes without periodic re-clustering/rebuild — better suited to mostly-static datasets
Brute-force / flat (linear scan)	Exact (100%)	Scales linearly with collection size — becomes the bottleneck past a few hundred thousand vectors	Lowest — no index structure at all	Trivial — no index maintenance

When to use / when not to

Default to HNSW for most production workloads under roughly 10M vectors with an active write stream — it needs the least tuning to get strong recall and doesn't require a rebuild strategy for ongoing writes, which is the common case for a RAG system whose source documents keep changing.
Reach for IVF (or IVF variants) when the dataset is very large and comparatively static — memory or build time is the binding constraint rather than write throughput, e.g. a large archival corpus re-indexed on a schedule rather than continuously.
Skip an ANN index entirely below roughly a few hundred thousand vectors — a brute-force/flat scan is exact (no recall loss at all) and at that scale is often fast enough that the added complexity of tuning an approximate index isn't worth it yet.
At billion-vector scale, neither plain HNSW nor plain IVFFlat is usually the final answer — quantization techniques (binary/product quantization) layered on either, or newer designs (DiskANN, ScaNN), close the memory gap that pure HNSW pays and are worth evaluating specifically once true billion-vector scale is a real requirement, not a hypothetical one.
Don't pick an index family by reputation alone ("HNSW is the standard") without checking the write pattern — a write-heavy IVF deployment that never re-clusters silently degrades in recall over time as the data distribution drifts from the original clustering, which is a much harder failure to notice than a slow query.

Common pitfall

Tuning an index's parameters once at initial setup and never revisiting them as the underlying data changes shape. IVF's cluster count and HNSW's graph-construction parameters (M, ef_construction) are both fit to the vector distribution at the time they're chosen; a corpus that grows 10x, or whose embedding model changes (a new embedding model produces a differently-shaped vector space even at the same dimensionality), can leave a previously well-tuned index with materially worse recall or latency than a fresh one built against current data — and because ANN search degrades gracefully rather than failing loudly, this typically shows up as "search feels worse lately" rather than an alert. Re-evaluate index parameters (and for IVF, re-run clustering) after a material change in corpus size or embedding model, not only at initial launch.

Engineering Lens

The HNSW-vs-IVF decision is really a decision about which resource is scarcer for a given deployment: memory, or write-time index maintenance. Neither index is universally "better" — the honest framing in a design review is naming the actual constraint (a memory-constrained deployment with heavy write traffic genuinely has no free option, only a chosen tradeoff) rather than defaulting to whichever index a tutorial happened to use. The same instinct that applies to picking a database engine applies here: understand what the data access pattern actually looks like (write frequency, corpus size, latency budget) before picking the index, not after a slow or memory-starved system in production forces the question.