Skip to content
AI Engineer Guide.

concept · concepts · intermediate · concept 13 of 57

HNSW/IVF/PQ

0 of 57 complete

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

Graph and lists · same points, two pruningsInteractive

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.

  1. Compute the raw vector memory first: count times dimension times bytes per component, then add index overhead.
  2. Choose HNSW when latency matters and the corpus fits in memory, and budget for its link storage and slow deletes.
  3. Choose IVF when memory is tight, tuning the number of lists against the number of probes per query.
  4. Add PQ only after measuring the accuracy loss on your own queries, since compression error is data-dependent.
  5. Build on a representative sample and measure build time, because graph construction is much slower than writing flat vectors.
  6. Plan rebuilds and deletes explicitly; every family degrades differently under churn.

Trade-offs

ChoiceGood forCostFails when
HNSWLow latency and high recallMemory per vector plus graph links; costly deletesThe corpus must stay in RAM on a fixed budget
IVF flatLower memory than a graphRecall depends on nprobe and list balanceQueries cluster unevenly across lists
IVF with PQVery large corpora on modest memoryApproximate distances and reranking neededThe task needs fine-grained score ordering
Flat exact indexPerfect recall and simple updatesLinear scan per queryConcurrency or corpus size grows
Trade-off mapInteractive

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

  1. The corpus must stay in RAM on a fixed budget
  2. Queries cluster unevenly across lists
  3. The task needs fine-grained score ordering
  4. 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.