Why it matters
The index determines whether the corpus fits in memory and whether a rebuild is feasible during business hours. HNSW keeps a graph of neighbour links and needs memory per vector plus links; IVF keeps a coarse quantiser and scans a subset of lists; PQ stores short codes instead of full vectors. These are not interchangeable settings but different data structures with different failure curves under inserts, deletes and filters.
Mental model
Index families are filing strategies: a graph is a network of cross-references, IVF is a set of labelled drawers, PQ is a summary card in place of the full document. The metaphor breaks because a summary card can only be compared approximately, so the comparison itself becomes the source of error.
How it works
The interactive figure loads with JavaScript. The text version below describes the same frame.
Figure. Sixteen synthetic points indexed two ways. Graph mode draws one layer of the HNSW hierarchy with short-range links; list mode partitions the points into four IVF lists and probes only the query's list. Both modes search for the same five exact neighbours; the panel reports what each returns.
What to notice. The graph is a single layer with ef_search = 4: the walk keeps the four best candidates it reaches — n1, n3, n2, n4 — and stops. n5 has no edge to any returned node, so its branch is never entered; f is adjacent but scores below the four kept candidates. The probed list returns four chunks: three of the five exact neighbours plus f, a list member outside the exact five, because n4 and n5 sit in the neighbouring list that the probe never opens. The list mode's lower build and memory footprint buys that recall gap; these are structural trades, and the values beside the rank panel are illustrative, not a benchmark.
Text version
Sixteen synthetic points in a hand-placed layout, with a query in the upper right. In the default graph mode, one HNSW layer is shown: short-range links connect nearby points and a few bridges join the regions; the query's exact neighbours n1, n3, n2 and n4 are ringed and joined to it, while n5 is ringed with a dashed outline and marked missed in the rank panel, giving four of five, with illustrative recall, latency and memory values beside the list. n5 has no link to a returned node, so the walk cannot reach it at ef_search four. A mode control switches to lists: four dashed ellipses enclose the lists, only the query's top-right list is highlighted and its four members are returned, giving three of the five exact neighbours, with n4 and n5 missed and f marked as an extra result.
- Compute the raw vector memory first: count times dimension times bytes per component, then add index overhead.
- Choose HNSW when latency matters and the corpus fits in memory, and budget for its link storage and slow deletes.
- Choose IVF when memory is tight, tuning the number of lists against the number of probes per query.
- Add PQ only after measuring the accuracy loss on your own queries, since compression error is data-dependent.
- Build on a representative sample and measure build time, because graph construction is much slower than writing flat vectors.
- Plan rebuilds and deletes explicitly; every family degrades differently under churn.
Trade-offs
| Choice | Good for | Cost | Fails when |
|---|---|---|---|
| HNSW | Low latency and high recall | Memory per vector plus graph links; costly deletes | The corpus must stay in RAM on a fixed budget |
| IVF flat | Lower memory than a graph | Recall depends on nprobe and list balance | Queries cluster unevenly across lists |
| IVF with PQ | Very large corpora on modest memory | Approximate distances and reranking needed | The task needs fine-grained score ordering |
| Flat exact index | Perfect recall and simple updates | Linear scan per query | Concurrency or corpus size grows |
Good for
Low latency and high recall
Cost
Memory per vector plus graph links; costly deletes
Fails when
The corpus must stay in RAM on a fixed budget
- The corpus must stay in RAM on a fixed budget
- Queries cluster unevenly across lists
- The task needs fine-grained score ordering
- Concurrency or corpus size grows
Figure. Each choice with what it buys, what it costs, and the case where it loses.
What to notice. The fourth column is the decision: if the losing case describes your situation, the choice is wrong.
Text version
Four trade-offs: HNSW is good for Low latency and high recall, costs Memory per vector plus graph links; costly deletes, and fails when The corpus must stay in RAM on a fixed budget. IVF flat is good for Lower memory than a graph, costs Recall depends on nprobe and list balance, and fails when Queries cluster unevenly across lists. IVF with PQ is good for Very large corpora on modest memory, costs Approximate distances and reranking needed, and fails when The task needs fine-grained score ordering. Flat exact index is good for Perfect recall and simple updates, costs Linear scan per query, and fails when Concurrency or corpus size grows
Failure modes
- Memory underprovisioned for links. The graph is evicted to disk and latency collapses under load. Debug: compare resident memory with the vector-plus-links estimate at peak concurrency.
- Unbalanced IVF lists. A few lists hold most vectors, so probes scan far more than expected. Debug: plot the distribution of vectors per list after the build.
- PQ trained on unrepresentative data. Compression error is uneven and some regions of the space become indistinguishable. Debug: compare exact and PQ rankings for queries whose answers are known.
In production
Alert on index memory headroom and rebuild duration, not only on query latency. Keep a flat or higher-precision copy of a sample for recall checks, and rehearse a full rebuild before you need one.
Common misconceptions
People think: One index type suits every scale.
Actually: Graph, partition and compression families solve different constraints, and large systems often combine them.
People think: Quantisation only affects storage.
Actually: It changes distance estimates, so ranking near the decision boundary changes too.
Interview angle
Derive the memory budget from vector count, dimension and index overhead, then choose a family from the binding constraint. Say what each family prunes and how it degrades under churn. Naming HNSW as the default without mentioning its memory footprint or its delete cost is the common shortcut.
Sources
- Malkov & Yashunin, HNSW — layered graph construction, memory layout and search behaviour.
- FAISS wiki — index families, quantisers and the accuracy-speed knobs for each.
- pgvector — HNSW and IVFFlat parameters inside a relational database.