HNSW vs IVF: Vector Index Tradeoffs Compared

Choosing between a graph index and a cluster index is usually framed as a recall question. It is mostly a memory and write-pattern question. Both families reach high recall if you let them; they differ in what they cost to get there, what happens when data changes, and how badly they fail when the workload shifts.

The two designs in one paragraph each

HNSW builds a multi-layer proximity graph. Each vector links to a bounded set of neighbours, sparse upper layers let a search jump across the space, and the query walks greedily downhill toward the target while maintaining a candidate list. There is no training step: the structure emerges from insertion. Recall is controlled at query time by how large that candidate list is allowed to get.

IVF (inverted file) partitions the space with a clustering pass, assigns every vector to its nearest centroid, and stores an inverted list per centroid. A query compares against the centroids, picks the closest few, and scans only those lists. There is a training step, because the centroids have to be learned before anything can be indexed. Recall is controlled at query time by how many lists get probed.

IVF is often paired with product quantization (IVF-PQ), which replaces each vector with a short code, and that pairing is what makes it the memory-efficient option rather than the algorithm itself.

Side by side

	Flat (exact)	HNSW	IVF-Flat	IVF-PQ	Disk-based graph
Recall ceiling	100% by definition	Very high	Very high	Capped by code loss	Very high
Memory per vector	Full vector	Full vector + ~`2 x M x 4` bytes	Full vector + list id	Short PQ code	Compressed resident, full vector on SSD
Build cost	None	High	Moderate, plus training	Moderate, plus training	High
Training required	No	No	Yes	Yes	No
Main recall knob	None	Search candidate list (`ef`)	Lists probed (`nprobe`)	`nprobe` + rescoring	Search list size
Incremental inserts	Trivial	Supported, graph degrades slowly	Supported, quality drifts from centroids	Same, plus code drift	Supported, periodic rebuild
Deletes	Trivial	Tombstoned, needs compaction	Cheap	Cheap	Needs consolidation
Fails badly when	Corpus grows	Memory runs out	Data distribution shifts	Precision matters	Storage is not NVMe-class
Natural fit	Under ~100k vectors	Latency-critical, fits in RAM	Mid-size, rebuildable	Very large, memory-bound	Larger than RAM, cost-bound

Memory is the real dividing line

The published guidance from the Faiss project puts it plainly: if memory is not a concern, use an exact index or a graph index, and reach for quantized inverted-file variants specifically when memory is the binding constraint. That framing is more useful than a recall comparison, because both families can be tuned to the same recall and then compared on cost.

The arithmetic backs it up. HNSW keeps full-precision vectors plus a per-vector graph cost of roughly 2 x M x 4 bytes. IVF-Flat keeps full-precision vectors plus a list assignment, so it is slightly cheaper than HNSW in memory, not dramatically so. The order-of-magnitude difference only appears with product quantization, where a vector is replaced by a code of a few bytes regardless of its original dimensionality. That is the tradeoff being bought: an index that fits, at a recall ceiling set by how much the code discards.

Postgres makes the same distinction inside a single extension. pgvector’s documentation describes IVFFlat as building faster and using less memory than HNSW, while giving worse query performance at a given recall. The relational engine does not change the underlying economics.

Work the numbers for your own corpus before choosing; vector database memory sizing has the formulas, and the HNSW index sizer applies them.

Build cost and the training trap

HNSW construction is the expensive one. Every insert searches the graph to find neighbours, so build time grows with corpus size and with the construction effort parameter. Building a large graph is measured in hours, and it is CPU-bound.

IVF’s build is cheaper but has a precondition that trips people up: the centroids must be trained on representative data. The Faiss guidance is that the training set should scale with the number of centroids, in the range of tens to a couple of hundred vectors per centroid. Train on too little data and the partitions are poor. Train on data that does not match production and the partitions are poor in a way that only shows up as mediocre recall later.

pgvector encodes the same warning operationally: build an IVFFlat index after the table has data, not before, because an index built on an empty or unrepresentative table has nothing useful to cluster on. It also ties list count to table size, with a different rule below and above a million rows.

This is the failure mode that separates the families in production. A graph index degrades gradually as data drifts. A cluster index degrades against a fixed set of centroids that were correct at training time and are quietly wrong a quarter later. Corpora that turn over need a retraining plan, and that plan is an operational commitment, not a configuration value.

Updates, deletes and churn

If the corpus is append-mostly, HNSW is comfortable: inserts are supported natively and the graph tolerates growth.

If the corpus churns, look harder. Graph indexes generally handle deletion by tombstoning, which leaves the removed element in the structure until a compaction or rebuild. Memory is not reclaimed in the meantime, and the graph slowly accumulates dead ends that cost traversal effort. Inverted lists handle deletion more cheaply because removing an entry from a list is local.

The honest summary: HNSW favours read-heavy, append-mostly workloads. IVF favours workloads that are rebuilt on a schedule anyway.

Filtering behaviour differs, and it matters

Neither family filters for free. A metadata filter applied after retrieval can return fewer than the requested number of results, because the index committed to candidates before the filter was known. Applied during traversal, it constrains the search: a graph walk restricted to a rare subset can wander without finding valid neighbours, and a cluster scan restricted the same way may find the matching rows are concentrated in lists that never got probed.

Engines diverge sharply here, and the difference is worth checking in documentation before committing, because a highly selective filter is exactly where an otherwise well-tuned index starts returning short or empty result sets. Low vector search recall: causes and fixes covers how to tell which behaviour an engine implements.

A decision path

Under roughly 100,000 vectors: use exact search. It is simple, correct, and often fast enough. An ANN index at this size adds failure modes and saves little.
Fits in RAM comfortably, latency matters, corpus is append-mostly: HNSW. It is the default in most engines for good reason.
Fits in RAM but is rebuilt on a schedule, or writes are bulk-loaded: IVF-Flat. Cheaper build, cheaper deletes, one fewer resident structure.
Does not fit in RAM: IVF-PQ or a disk-based graph. Choose PQ when cost per vector dominates and a recall ceiling is acceptable. Choose the disk-based graph when recall must stay high and NVMe storage is available.
Whatever you pick, tune both configurations to the same recall before comparing latency. A benchmark that compares an index at 92 percent recall against one at 99 percent is not a comparison.

That last point matters more than the choice itself. Most published index comparisons are unreproducible because they report latency without the recall it was achieved at. Measure recall against exact search on a sample of your own queries, then compare. Vector search fundamentals explains why that measurement is the only one that settles the question.