Cruxly › AI engineering › Retrieval and RAG

ANN Indexes in Depth: HNSW, IVF-PQ, DiskANN and the Recall/Latency/Memory Triangle

307 GB of vectors, a 25.6 GB graph, a 9.6 GB code table, and why a filter returns 3 results instead of 10

Prompt: "We have 100 million chunks embedded at 768 dimensions and the infra lead has one box. Explain how HNSW search works, then tell me whether you would use HNSW or IVF-PQ, how you would cut index memory by 10x, and why a filtered query for one customer returns 3 results instead of 10. How do you know the index is accurate?"

40 minutes first. Do the memory arithmetic for three index types and one filtered-query calculation on paper. The trap is treating "HNSW" as a synonym for "vector search"; the right answer names a budget and a recall target.

Why exact search stops working, and what the triangle is

Exact nearest-neighbour search is a full scan, and a full scan at this scale is both a memory problem and a bandwidth problem. One hundred million vectors at 768 dimensions in float32 is 100,000,000 x 768 x 4 = 307.2 GB. A query compares against every one: 100M x 768 = 76.8 billion multiply-adds, and every byte of the 307 GB must stream through the CPU or GPU. Even at an assumed 100 GB/s of memory bandwidth, that is three seconds per query, for one query, with nothing else running. Chunks of this scale are not exotic: a 20M-chunk corpus at 3,072 dimensions is already 245.76 GB, as the previous lesson, Choosing, Evaluating and Fine-Tuning an Embedding Model, computed.

Approximate nearest-neighbour (ANN) indexes buy speed by looking at a small part of the data and accepting that they will sometimes miss. Every design is a point in a triangle with three corners: recall (how many of the true nearest neighbours you return), latency or throughput, and memory (RAM, or RAM plus SSD). You can improve two at the cost of the third, and every parameter you will meet in this lesson moves you along one edge.

Two different "recalls" get confused in interviews, so name them. ANN recall@10 asks: of the 10 vectors an exact scan would return, how many did the index return? That measures the index against brute force and says nothing about whether the results are relevant. Retrieval recall@k, from the previous lesson, asks whether the chunk that answers the question was in the top k, measured against human labels. An index can have an ANN recall of 0.95 and still fail users because the embedding model is wrong, and a mediocre embedding model can hide a poor index. Measure them separately; Evaluation Gates That Actually Block a Bad Deploy is where the retrieval number belongs in your release gate, and this lesson owns the ANN one.

HNSW: a layered graph you walk greedily

HNSW (Hierarchical Navigable Small World, Malkov and Yashunin) stores each vector as a node in a layered proximity graph, and a search is a greedy walk from the sparse top layer down to the dense bottom layer. Every vector lives in layer 0. A random few also appear in layer 1, a random few of those in layer 2, and so on, with the probability falling geometrically so the top layers are a handful of long-range "highway" nodes. Search starts at an entry point in the top layer, hops to whichever neighbour is closer to the query until no neighbour improves, drops one layer, and repeats. At layer 0 it switches from a single greedy path to a beam: keep the best ef_search candidates seen so far and expand the closest unexpanded one until none can improve the list. Return the top 10 of those.

Three parameters, with defaults you can check.

• M: maximum neighbours per node. Layer 0 allows up to 2M. More neighbours means better recall and more memory.
• ef_construction: beam width while inserting. Higher builds a better graph, slower.
• ef_search: beam width while querying, the live dial: raise it for recall, lower it for speed. The pgvector README gives its defaults as m = 16, ef_construction = 64, hnsw.ef_search = 40.

Memory is the vectors plus the edges, and the vectors dominate. Take M = 32. Layer 0 holds up to 64 neighbour IDs per vector at 4 bytes each: 64 x 4 = 256 bytes per vector, so 100M x 256 B = 25.6 GB of graph. The vectors themselves are 307.2 GB, so the whole index is roughly 332.8 GB in RAM, since HNSW must follow edges to random vectors with no locality. (Upper layers hold about one node in 32 and add under a gigabyte.) The graph is 8 percent of the bill; this is why the memory levers are about vectors, not about M.

Work per query is small and nearly independent of corpus size. A rough count: the beam examines on the order of ef_search x M = 40 x 32 = 1,280 candidate distance computations, against 100 million for a scan. That is where the speed comes from, and the "nearly" hides the effect of cache misses on a graph this size.

:::warn HNSW's operational weaknesses are writes and deletes. Inserting rewires the neighbours of every node it links to, which means lock contention under heavy concurrent writes. Deleting usually marks a node as a tombstone, and the graph around it degrades until a rebuild or compaction. A corpus with constant churn needs a tested compaction schedule; one that is mostly append-only barely notices. Ask which you have before choosing. :::

IVF-PQ: scan a few clusters, store tiny codes

IVF (inverted file) partitions the vectors into nlist clusters with k-means, and a query scans only the nprobe clusters whose centroids are nearest to it. Rule of thumb for nlist is about the square root of N (the pgvector README suggests the same shape: rows/1000 up to 1M rows, sqrt(rows) above that). For 100M vectors, nlist = sqrt(100,000,000) = 10,000, an average of 10,000 vectors per cluster. With nprobe = 16 the query scans 16 x 10,000 = 160,000 vectors, which is 16 / 10,000 = 0.16% of the corpus.

Product quantisation (PQ) compresses each vector into a short code. The idea comes from Jegou, Douze and Schmid's "Product Quantization for Nearest Neighbor Search" (IEEE TPAMI, vol. 33, no. 1, 2011, pages 117 to 128; there is no arXiv version, but an open copy is on the HAL archive as inria-00514462). Split the 768-dim vector into m = 96 sub-vectors of 8 dimensions. For each sub-space, run k-means to learn 256 centroids (a codebook). A vector is stored as the 96 centroid indices, one byte each: 96 bytes instead of 3,072, so 100M x 96 B = 9.6 GB of codes, a 32x cut.

Asymmetric distance is why PQ search is fast and fairly accurate. The query is not compressed. For each of the 96 sub-spaces, precompute the distance from the query's sub-vector to all 256 centroids: a table of 96 x 256 = 24,576 numbers, built once per query. The distance to any stored vector is then 96 table lookups and additions, with no 768-dim arithmetic. Residual encoding improves it further: encode vector - its cluster centroid, a smaller-magnitude quantity, so the same 256 centroids cover it more finely.

The cost per query, counted. Comparing the query to 10,000 centroids: 10,000 x 768 = 7.68M operations. Scanning 160,000 codes: 160,000 x 96 = 15.36M lookups. About 23 million operations against 76.8 billion for the exact scan, roughly 3,300 times fewer. The price is recall: PQ error means the true neighbour is sometimes ranked 30th, so production systems rerank. Take the top 200 by PQ distance, fetch their full float32 vectors from SSD (a 3,072-byte vector fits inside one 4 KB page, so that is 200 page reads, 614 KB), and compute exact distances. Recall recovers; RAM holds only the 9.6 GB of codes plus centroids.

Two ways IVF-PQ fails.

• Training data. k-means for 10,000 centroids needs far more than 10,000 samples, so train on a random sample of at least a few hundred thousand vectors, commonly a million or more, drawn from the same distribution as production. Train on a tiny or unrepresentative sample and clusters are lopsided: some hold 200,000 vectors, so a probe is slow, others are empty.
• Drift. Centroids are frozen at training time. As the corpus changes, vectors pile into a few clusters and recall at fixed nprobe falls; plan a scheduled retrain and rebuild, measured by watching cluster-size skew.

Disk-based indexes, and how to cut memory 10x

When even the compact codes will not fit in RAM, put the full vectors on SSD and keep only a compressed sketch in memory. The DiskANN paper (Subramanya et al., NeurIPS 2019) builds a graph called Vamana, keeps PQ-compressed vectors in RAM to steer the search, and stores the graph and full-precision vectors on SSD, reading them only for the nodes it visits. The authors' abstract reports serving a billion-point index on a single machine with 64 GB of RAM and an inexpensive SSD, with over 5,000 queries per second, under 3 ms mean latency and 95 percent or better 1-recall@1 on the SIFT1B benchmark (a 128-dimension dataset, on a 16-core machine; these are the authors' figures on their hardware, not a promise for your 768-dim embeddings). Quote it as "the design point exists", then measure.

:::key Verified October 2026 DiskANN figures are from the paper's abstract (NeurIPS 2019), retrieved October 2026, and are the authors' own benchmark on SIFT1B. The pgvector parameter defaults and iterative-scan details used in this lesson come from its README, retrieved October 2026, and change between releases (iterative scans arrived in 0.8.0). :::

Now answer "HNSW or IVF for 500M vectors on a budget". 500M x 768 float32 is 1.536 TB.

• HNSW in RAM needs the vectors plus about 128 GB of edges at M = 32: ~1.66 TB of RAM. Not a budget machine.
• Scalar int8 vectors cut it to 384 GB, still a large server, and quality loss must be measured.
• IVF-PQ with 64-byte codes needs 500M x 64 B = 32 GB of RAM for codes, with full vectors (1.536 TB) on SSD for reranking. This fits a commodity box with a big SSD.
• A DiskANN-style index sits between the two: graph quality, with PQ in RAM and the rest on disk.

The defensible answer is IVF-PQ or a disk graph with SSD reranking, chosen after a recall sweep, because RAM is the constraint and SSD is cheap.

The 10x memory-cut menu, from the 307 GB baseline. Each row is a measured trade, not a free win:

Filtered search: why you get 3 results instead of 10

Most ANN indexes find nearest neighbours first and apply your filter afterwards, so a selective filter leaves almost nothing. The pgvector README gives the exact example: with approximate indexes the filter is applied after the index scan, so a condition matching 10 percent of rows with the default ef_search = 40 returns about 4 rows on average. Arithmetic: the index hands back ~40 candidates; only the fraction s that pass the filter survive; 40 x 0.10 = 4. At a 1 percent filter it is 40 x 0.01 = 0.4 rows, usually zero or one. To get 10 results at selectivity s you must examine about 10 / s candidates: 100 at 10 percent, 1,000 at 1 percent, 10,000 at 0.1 percent, which is one tenant in a thousand. Cost grows as the filter gets tighter, and no ef_search setting is cheap at that depth.

Four strategies, and when each is right.

• Post-filter with oversampling or iterative scans. Ask for more candidates and keep scanning until enough pass. pgvector 0.8.0 added iterative index scans (strict_order or relaxed_order), bounded by hnsw.max_scan_tuples, default 20,000. Simple, but a tight filter can hit the cap with fewer than 10 hits.
• Pre-filter and brute-force. If the filter selects a small set, skip the ANN index. A tenant with 50,000 vectors costs 50,000 x 768 = 38.4M multiply-adds for an exact scan, about 40 times an unfiltered HNSW walk (1,280 x 768 = 0.98M, our arithmetic), but it is exact and needs no deeper beam to survive the filter. Many engines switch to this automatically below a threshold.
• In-graph filtering. Test the filter during the graph walk and only admit matching nodes. Better recall, but if the matching nodes are scattered, the filtered subgraph is disconnected and the walk dead-ends, which is why engines fall back to brute force for very selective filters.
• Partition. One index (or partition) per tenant or per tenant cohort, or a partial index per large tenant, as the README suggests (partial indexes for few distinct values, partitioning for many). The filter becomes a routing decision with zero recall cost, at the price of many small indexes to build and monitor. Multi-Tenant, Multilingual RAG at Scale covers the tenant-isolation reasons to do this anyway.

Diagnose it before you fix it. Log candidates returned by the index and rows after filter for each query. If the first is 40 and the second is 0 to 3 for small tenants, you have this bug, and the symptom is fewer results, not wrong ones, which is why it hides from accuracy dashboards.

Benchmark honestly: recall against exact, at fixed recall, on your vectors

Public ANN benchmarks tell you which algorithm families exist; only a run on your vectors tells you which parameters to ship. The community's ann-benchmarks project publishes recall-versus-queries-per-second curves across algorithms on standard datasets, which is the right place to learn the shapes of the curves. Your embeddings have their own distribution, dimensionality and cluster structure, so the knee of your curve sits somewhere else.

@@ 1 | Compute ground truth once Sample 1,000 real queries. For each, run an exact scan (on a GPU, or in batches over the 307 GB) and store the true top 10 IDs. This is an offline job and the output is reusable.

@@ 2 | Sweep the query knob For HNSW sweep ef_search (for example 20, 40, 80, 160, 320); for IVF sweep nprobe (4, 8, 16, 32, 64). For each setting record ANN recall@10 against the stored ground truth, plus p50 and p99 latency, not the mean.

@@ 3 | Compare at a fixed recall Pick a target (say 0.95) and compare indexes by QPS and p99 at that recall. A faster index at lower recall is not faster; it is a different operating point.

@@ 4 | Record the other axes Build time, peak build memory, steady-state RAM, index size on disk, and behaviour during inserts and deletes.

Compute the number like this. If the 1,000 queries return 9,420 of the 10,000 true neighbours in total, ANN recall@10 is 9,420 / 10,000 = 0.942. Report the per-query distribution too: an average of 0.94 can hide 5 percent of queries at zero, and the zero-recall queries often share a pattern (rare languages, very short queries, an out-of-distribution tenant).

Monitor it in production. The corpus and the query mix drift, and the index with them. On 0.1 percent of live traffic, run the exact search in the background (or on a GPU replica) and log the overlap with what the index returned. A dashboard line for ANN recall@10 catches IVF cluster skew and HNSW tombstone buildup long before users complain. When you compare engines (pgvector, FAISS, a managed vector database), run all of them through steps 1 to 4 on the same 1,000 queries; the ranking you get is the only one that applies to you.

How to say it in the interview

"Exact search reads every vector, 307 GB per query at 100 million by 768, so we trade a little recall for speed with an index. HNSW is a layered graph you walk greedily; it is fast and accurate but keeps every full vector in RAM plus about 256 bytes of edges each. IVF-PQ clusters the space, scans only a few clusters, and stores 96-byte codes instead of 3 KB vectors, then reranks the shortlist with full vectors from SSD. Filters break both because the index finds neighbours first and the filter removes them after, so I would partition by tenant or use iterative scans, and I would measure recall at 10 against exact ground truth on our own vectors."

Checklist

• Computed raw vector bytes (N x dims x 4) before choosing any index
• Separated ANN recall (index vs exact) from retrieval recall (results vs human labels)
• Sized HNSW as vectors plus about 2M x 4 bytes of edges per vector
• Tuned ef_search or nprobe per query class instead of treating the index as set-once
• Planned for HNSW churn: insert contention, delete tombstones and a compaction schedule
• Trained IVF-PQ on a large, representative sample and monitored cluster-size skew
• Reranked the PQ shortlist (for example the top 200) with full vectors from SSD
• Chose the index from the RAM budget (HNSW in RAM, IVF-PQ or a disk graph beyond it)
• Handled filters explicitly: partitions, exact scan for small sets, bounded iterative scans
• Logged index candidates versus rows-after-filter per query
• Benchmarked on my own vectors with exact ground truth, compared at fixed recall, reporting p99
• Shadow-checked 0.1 percent of live queries against exact search

Related lessons

• RAG From Scratch, No Framework
• Chunking and Document Parsing: Structure-Aware Splits, Parent-Child, Late Chunking and Contextual Retrieval
• Choosing, Evaluating and Fine-Tuning an Embedding Model
• Hybrid Search, Rerankers and Late Interaction
• Query Understanding and Agentic Retrieval: Rewriting, Routing, Multi-Hop and GraphRAG
• Multi-Tenant, Multilingual RAG at Scale