Flat checks everything and is always right. IVF checks a few neighbourhoods. HNSW walks a graph. The differences are entirely about what you are willing to give up.
Every vector database markets itself on the same three words — fast, accurate, scalable — and every one of them is quietly picking two. The picking happens in the index structure, and once you can see which trade a given index is making, choosing between them stops being a vendor comparison and becomes an engineering decision you can make from your own numbers.
Start from the problem. You have n vectors of dimension d. A query arrives and you want the k closest. The exact answer requires comparing the query to all n vectors: O(n·d) per query, no way around it. For a million 1024-dimensional vectors that is a billion floating-point operations per query — genuinely fast on modern SIMD hardware, and genuinely too slow at scale or at high query rates.
So we approximate. Approximate nearest neighbour search gives up the guarantee of correctness in exchange for sublinear search. The currency you spend is recall — the fraction of the true top-k your index actually returns — and the whole discipline is deciding how much of it to spend and where.
Flat: the baseline you should not skip
A flat (brute-force) index stores vectors and compares against all of them. It sounds like the naive option and it is frequently the right one.
- Recall is 1.0. Not “high” — exact, by construction. There is no quality question to investigate, ever.
- Zero build time and zero tuning. No training, no parameters, no rebuild when the distribution shifts.
- Instant updates. Append a vector and it is immediately searchable. No graph to patch, no clusters to rebalance.
- Trivially parallel. It is a dot product over a contiguous array; hardware loves it.
The reason to leave is latency, and only latency. Work out your actual number before you go: n × d multiply-adds per query, against a machine that does billions per second. A few hundred thousand vectors is often comfortably under 50 ms single-threaded, and faster with SIMD and batching.
Build the flat index first regardless, even when you know you will outgrow it. It is your ground truth: the only way to compute the recall of an approximate index is to compare its results against exact ones on the same queries. Teams that skip this step end up running an ANN index with no idea what it is returning — and “our retrieval got worse” becomes unfalsifiable.
IVF: only search the neighbourhoods that matter
The inverted file index applies an old idea. Cluster the vectors — usually k-means into nlist centroids — and store each vector in the list belonging to its nearest centroid. At query time, find the nprobe centroids closest to the query and scan only those lists.
The speedup is a ratio you control directly. With nlist = 4096 and nprobe = 16, you scan roughly 16/4096 of the corpus — about 0.4% of the vectors, a ~250× reduction in comparisons. Turn nprobe up and you scan more, find more, and go slower. It is a single, legible, tunable dial, and that legibility is IVF’s underrated virtue: you can explain to a colleague exactly what changed and why.
Where it costs you:
The training step. k-means has to run over a representative sample before you can index anything. That is real wall-clock time up front, and more importantly it bakes in an assumption about your data distribution. Index a corpus of Kubernetes runbooks, then add a million vectors of financial filings, and the original centroids no longer describe the space. Recall degrades quietly, without an error anywhere. IVF indexes need periodic retraining as the corpus drifts — put it on a schedule, and monitor recall against a fixed held-out query set so you notice the decay before your users do.
The boundary problem. A query near the edge of a cluster has true neighbours sitting just across the border in a cluster you did not probe. They are simply invisible. Raising nprobe mitigates it by probing more neighbours, which is exactly the recall-for-latency trade in its clearest form.
IVF’s compensating strength is memory. The index overhead is nlist centroids plus one list assignment per vector — tiny. And it composes beautifully with quantization, which is where it becomes indispensable at genuinely large scale.
HNSW: walk a graph, from coarse to fine
Hierarchical Navigable Small World, introduced by Malkov and Yashunin, is the structure most vector databases default to, and the reason is that it tends to sit on a better point of the recall-latency curve than the alternatives.
The construction is a hierarchy of proximity graphs. The bottom layer contains every vector, each linked to its approximate nearest neighbours. Each layer above holds an exponentially smaller random sample, with longer-range links. Search starts at a single entry point in the sparse top layer and greedily hops to whichever neighbour is closer to the query; when it can get no closer, it drops a layer and repeats on a denser graph.
The useful intuition: the top layers are the motorway network and the bottom layer is the local streets. You cover most of the distance in a few long hops, then refine. Search cost scales roughly logarithmically with n, which is what makes it feel fast on large corpora.
Two parameters carry almost all the behaviour:
M — links per node per layer. This is the memory-versus-recall dial. A denser graph means more routes toward any given query, so greedy search is less likely to get stuck in a local minimum — which matters more as dimensionality rises. Memory overhead is roughly 8 × M bytes per vector (bidirectional links, 4-byte ids, doubled at the base layer). Typical values run 16 to 64.
efConstruction / ef — the size of the candidate list kept during build and during search respectively. efConstruction buys graph quality with build time, once. ef buys recall with latency, per query, at runtime with no rebuild — which makes it the dial to reach for when recall is short in production. ef must be at least k, and raising it is usually the cheapest recall you can buy.
Where HNSW costs you:
Memory, and it is the main event. You hold the full vectors plus the graph, in RAM, or search degrades catastrophically when it starts hitting disk — a graph traversal is a random-access pattern, which is the worst possible case for a page cache. The arithmetic is worth doing before you commit:
10 million vectors × 1024 dims × 4 bytes (float32) = ~41 GB of vectors plus 10M × 8 × 32 (M=32) = ~2.6 GB of graph ≈ 44 GB resident, before your process, your runtime, or any headroom.
That is a memory-optimised instance for a corpus many teams would describe as medium-sized. It is the single most common surprise in a vector-search budget.
Build time. Constructing the graph means running a search for every inserted vector. Building a large index is hours, not minutes, and that lands on your reindexing story: a schema change or an embedding-model swap means paying it again.
Deletes are soft. You cannot cleanly cut a node out of a proximity graph without risking disconnection, so implementations tombstone instead. Deleted vectors keep occupying memory and keep participating in traversal until a compaction rebuilds the index. A workload with heavy churn accumulates tombstones and degrades, in both memory and recall, and the fix is a periodic rebuild you have to schedule deliberately. If your corpus has high turnover, this is the factor that should push you toward IVF.
Quantization: buying memory back
When 44 GB is not acceptable, you compress the vectors themselves. This is orthogonal to the index structure — you can quantize under IVF or under HNSW — and it is what makes billion-scale search affordable.
Scalar quantization maps each float32 dimension to int8. 4× smaller, cheap to compute, and the accuracy loss is usually small because embedding values cluster in a narrow range. It is the low-risk first move: try it before anything more exotic.
Product quantization, from Jégou et al., is the aggressive option. Split each vector into m subvectors, run k-means on each subspace to build a codebook of 256 centroids, and store each subvector as a single byte identifying its nearest centroid. A 1024-dimensional float32 vector at 4 KB becomes m bytes — with m = 64, 64 bytes, a 64× reduction. Distances are computed against a precomputed lookup table rather than the original vectors, so it is fast as well as small.
The loss is real: two vectors that map to the same codes become indistinguishable. Near-ties get reordered. IVF + PQ is the standard billion-scale recipe precisely because the two compose — IVF narrows the candidate set, PQ makes each candidate cheap to hold and compare.
Binary quantization goes furthest, reducing each dimension to a single bit and computing distance with XOR and popcount. 32× smaller than float32 and extremely fast. On its own the precision loss is substantial; it works in practice because of what comes next.
Over-retrieve, then rerank
This is the pattern that makes aggressive quantization safe, and it is the shape of most production retrieval:
- Retrieve a wide candidate set — say 100 — from the compressed index. Fast and cheap.
- Rescore those 100 against full-precision vectors, kept on disk or in a cheaper tier.
- Return the top
k.
You pay for exact distances on 100 vectors instead of 10 million, and you recover most of the precision the compression cost you. Swap step 2 for a cross-encoder and you get a further quality jump at a higher price. The RAG pipelines that work well almost all have this shape, and the ones that disappoint usually retrieve narrowly from an over-compressed index and hand the result straight to the model.
The comparison
| Flat | IVF | IVF + PQ | HNSW | |
|---|---|---|---|---|
| Recall | 1.0, exact | Tunable via nprobe | Lower, rerank to recover | Best at a given latency |
| Query cost | O(n·d) | O(nprobe/nlist · n · d) | Same, cheaper per comparison | ~O(log n) |
| Memory | vectors only | vectors + tiny | smallest | vectors + graph — largest |
| Build | none | k-means training | k-means + codebooks | slowest |
| Updates | instant | cheap | cheap | graph patch; deletes tombstone |
| Tuning | none | nlist, nprobe | + m, bits | M, efConstruction, ef |
| Use when | < ~100k vectors | large corpus, tight RAM, churn | billions of vectors | quality-first, RAM available |
Choosing, in practice
Under ~100k vectors: use flat. No index, no tuning, no recall question. Revisit when you have measured a latency problem, not before.
100k to ~10M, recall matters, RAM available: HNSW. This is the default for a reason. Start at M = 16, efConstruction = 200, and tune ef at query time against measured recall.
Large corpus, constrained memory, or heavy churn: IVF, with PQ if needed. Cheaper to hold, cheaper to update, retrainable. Accept the tuning and schedule the retraining.
Billions: IVF + PQ, with reranking. There is not really a second option at that scale on commodity hardware.
Two habits that matter more than the choice itself:
Measure recall against your own data. Public numbers from ANN-Benchmarks are excellent for understanding the shape of each algorithm’s curve, and they are measured on standard datasets that are not yours. Embedding distributions differ enormously by domain, and a structure that shines on one can sit in an awkward spot on another. Build a flat index, sample a few hundred real queries, compute exact top-k, and measure. It is an afternoon of work and it converts every later decision from argument to arithmetic.
Recall is not relevance. An index with 0.95 recall returns 95% of the vectors your embedding model thinks are nearest. Whether those are the right documents is a question about the embedding model, the chunking, and the query — not about the index. Teams routinely tune ef for weeks when the actual problem is 2000-token chunks that dilute every embedding into mush. Fix retrieval quality upstream first; tune the index when you have confirmed the index is what is losing you results.
The infrastructure part nobody budgets for
Two operational realities that turn up late and hurt.
Reindexing is a first-class workflow, not a one-off. You will change embedding models — a better one ships, or a cheaper one becomes good enough. New embeddings are not comparable to old ones, so the entire index must be rebuilt, and for a large HNSW index that is hours of compute during which queries still have to be served. Plan for a dual-index cutover: build the new index alongside the old, validate recall against held-out queries, then switch reads. Discovering this during an incident is a bad afternoon.
Sharding changes the recall story. Past a single machine, you shard — and each shard returns its own approximate top-k, which are then merged. The errors compound: a true neighbour missed by its shard’s approximate search cannot be recovered by the merge. Over-retrieve per shard (k × 2 or more) to compensate, and keep shards balanced — consistent hashing is what keeps a resharding event from becoming a full reindex.
The honest summary: a vector index is a knob that trades correctness for money. Flat spends CPU to be right. HNSW spends RAM to be fast. IVF spends recall to be cheap. Quantization spends precision to be small, and reranking buys some of it back. Know which currency you have most of, measure in your own domain, and the choice usually makes itself.
Comments