Vector Database Interview Questions: HNSW, IVF and Product Quantization Explained With a Measured Toy

If an interviewer asks "HNSW or IVF for 50 million vectors?", the answer is not a name. It is a recall target, a memory budget and a statement of what happens when the data changes. This post gives you the questions that cluster around vector databases, an answer outline for each, and a script I ran on 2026-10-09 that measures recall against latency for flat, IVF, IVF-PQ and HNSW indexes so you can quote real shapes of curves.

These are practice questions I wrote for this site. They aren't leaked and they aren't from any company. Each has a strong answer outline, the follow-up an interviewer tends to ask next, and a common wrong answer. For the wider loop see AI engineer interview questions on RAG, agents and evals, and for the embedding side tokenization and embeddings interview questions. For where the vector store sits in a whole design, see the RAG chatbot system design walkthrough. If you want to build something with these indexes first, the vector store guide covers FAISS, Chroma and Pinecone.

Why not just do exact search over all the vectors?

Strong answer outline

• Exact (flat) search compares the query with every stored vector. Cost per query is N times d multiply-adds, so it grows linearly with the collection.
• Below roughly a few hundred thousand vectors, flat search is often fine and has perfect recall. Don't reach for an approximate index until you've measured that flat is too slow or too expensive.
• Approximate nearest neighbour (ANN) search gives up a little recall for a large cut in work. The interview skill is naming the trade explicitly: recall at k, queries per second, memory, build time, update cost.

In my toy test, flat inner-product search over 100,000 vectors of 128 dimensions took about 6 ms per query on one thread. That is fast enough for many apps. At 100 million vectors, the same arithmetic gives roughly 1,000 times more work per query, which is where the approximate structures earn their keep.

Follow-up: How would you decide if you need ANN at all? Measure flat latency at your real size on your real hardware, compare against your latency budget, and only then compare indexes by recall at the budget.

Common wrong answer: "ANN is always better because it's faster." It's faster and it can miss true neighbours. If your retrieval step feeds a reranker, a few percent of missed neighbours may not matter. If it feeds a lookup where one exact match must be found, it might.

How does HNSW work?

Strong answer outline

• HNSW (hierarchical navigable small world) is described in Malkov and Yashunin, 2016 (I read the arXiv abstract on 2026-10-09, not the full paper). It builds a multi-layer graph over nested subsets of the vectors. Each vector's top layer is drawn at random with exponentially decaying probability, so upper layers are sparse and the bottom layer holds everything.
• A query enters at the top, moves greedily to the closest neighbour it can find on that layer, drops a layer, and repeats. At the bottom it widens into a best-first search that keeps a candidate list of size efSearch. The authors' claim is roughly logarithmic scaling, which is why upper layers act like a skip list.
• Build-time parameters: M (links per node) and efConstruction (candidate list size while inserting). Query-time parameter: efSearch. Bigger M means better recall at a given ef, more memory and a slower build. You can change efSearch at any time.
• Memory is the vector plus the links. The FAISS wiki's rule of thumb is d * 4 + M * 2 * 4 bytes per vector.

I checked the memory rule by saving indexes and dividing file size by vector count (20,000 random vectors, 128 dimensions):

hnswlib M=8: file 597 bytes/vector vs raw 512 bytes/vector, overhead 85 B
hnswlib M=16: file 660 bytes/vector vs raw 512 bytes/vector, overhead 148 B
hnswlib M=32: file 788 bytes/vector vs raw 512 bytes/vector, overhead 276 B
faiss HNSWFlat M=16: 656 bytes/vector

The wiki formula predicts 640 bytes at M=16, and the saved files came out near 660, so use the formula for planning and add a few percent for bookkeeping. At 50 million 768-dimension float32 vectors with M=16, the formula gives about 3,072 + 128 = 3,200 bytes each, or roughly 149 GiB before any replicas. That arithmetic is the real answer to "can we keep it in RAM?"

Follow-up: What happens when you delete or update vectors? The FAISS wiki notes its HNSW index doesn't support removing vectors. Many databases handle deletes with tombstones and periodic rebuilds or compaction. State that you'd check how your specific engine does it, and plan for rebuild time.

Common wrong answer: "HNSW is a tree." It's a graph of proximity links across layers. Trees partition space and graphs navigate neighbourhoods.

How does IVF work, and what do nlist and nprobe do?

Strong answer outline

• IVF (inverted file) runs k-means on a training sample to find nlist centroids, then files each vector under its nearest centroid. At query time it finds the nprobe closest centroids and scans only those lists.
• A common starting point for nlist is on the order of the square root of N. The FAISS wiki suggests between 4 and 16 times the square root of N, and training on roughly 30 to 256 vectors per centroid.
• If a true neighbour sits just across a cluster boundary, nprobe=1 misses it. Raising nprobe costs time linearly and buys recall.
• IVF needs a training step. If your data distribution shifts a lot after training (a new language, a new document type), the centroids go stale and recall quietly drops until you retrain.

Follow-up: Why would you choose IVF over HNSW? Lower memory when combined with compression, cheap to rebuild by batch, and no need for a graph in RAM. It also parallelises well across machines because lists are independent.

Common wrong answer: "nprobe is the number of results returned." That's k. nprobe is how many clusters you scan.

What is product quantization and what does it cost in recall?

Strong answer outline

• PQ splits each vector into m sub-vectors and replaces each with the id of its nearest entry in a small learned codebook (256 entries means 1 byte). A 128-dimension float32 vector (512 bytes) becomes 16 bytes with m=16, a 32 times reduction.
• Distances are then computed from the codes with lookup tables, so you never touch the full vector. IVF-PQ combines the two: IVF narrows to a few lists, PQ makes the scan cheap and the storage small.
• The cost is accuracy. Because the distance is approximate, candidates get ranked wrongly. The standard remedy is to retrieve more than k from the compressed index, then re-score that shortlist with the original vectors, which you keep on disk or in a slower store.
• For tuning guidance, the FAISS index-choice wiki is the source I read (as summarised by a fetch tool on 2026-10-09; check the page for exact wording).

Follow-up: Your IVF-PQ recall is stuck at 0.3 no matter how high nprobe goes. Why? The ceiling is the quantisation error, not the cluster probing. More lists scanned can't fix a ranking made from lossy codes. You need more bytes per code or a re-rank step. My numbers below show exactly this.

Common wrong answer: "PQ is like truncating the dimensions." PQ keeps all dimensions, but each chunk of dimensions is approximated by a codebook entry.

What does the recall versus latency curve actually look like?

Here is the experiment. It uses 100,000 synthetic vectors in 128 dimensions, drawn from 200 Gaussian clusters with noise of 2.0 per dimension, then normalised, with 500 queries drawn the same way and k=10. Ground truth comes from exact flat search. Everything ran on one CPU thread with faiss-cpu 1.15.1 and hnswlib 0.8.0.

This is synthetic data, not real embeddings. Real text embeddings have different structure, so the exact numbers won't transfer. The shape of the trade-offs, and how to measure them, will.

exact flat: 6.201 ms/query (1 thread), N=100000 D=128
IVF-Flat (nlist=316) nprobe -> recall@10, ms/query
  nprobe=  1 recall=0.667 0.028 ms
  nprobe=  4 recall=0.842 0.095 ms
  nprobe= 16 recall=0.911 0.280 ms
  nprobe= 64 recall=0.970 1.311 ms
IVF-PQ (m=16, 8 bit)
  nprobe=  4 recall=0.312 0.031 ms
  nprobe= 64 recall=0.316 0.397 ms
IVF-PQ + exact re-rank, nprobe=16
  k_factor=  1 recall=0.314 0.090 ms
  k_factor=  4 recall=0.618 0.099 ms
  k_factor= 10 recall=0.792 0.115 ms
  k_factor= 40 recall=0.901 0.183 ms
HNSW M=16 efConstruction=200: build 55.0s
  efSearch= 10 recall=0.491 0.045 ms
  efSearch= 50 recall=0.802 0.137 ms
  efSearch=200 recall=0.905 0.547 ms
HNSW M=32 efConstruction=200: build 87.5s
  efSearch= 10 recall=0.593 0.078 ms
  efSearch= 50 recall=0.862 0.239 ms
  efSearch=200 recall=0.957 0.851 ms

I trimmed rows for space. The full run also included HNSW with M=8 (recall 0.832 at efSearch 200) and more nprobe and efSearch values.

What to take from it, as claims about this toy:

• Recall is a dial, not a property. Each index has a query-time knob, and every point on the curve is a different system. "HNSW has 90% recall" means nothing without efSearch.
• IVF-Flat was competitive here. At 0.911 recall it took 0.28 ms, while HNSW M=16 needed efSearch 200 (0.547 ms) to reach 0.905. On this data and size, IVF won on speed. That surprised me, since HNSW is often the default winner. It depends on the data, so measure.
• HNSW build time is real. 55 seconds for M=16 versus about 1.3 seconds to train and fill IVF-Flat. If you re-index often, that matters.
• PQ's recall ceiling is flat. Raising nprobe from 4 to 64 moved recall by 0.004. Re-ranking 400 candidates (k_factor 40) took it from 0.314 to 0.901. Memory for the codes was 1.5 MiB against 48.8 MiB of raw vectors, but the re-rank step needs the originals somewhere.
• Data difficulty changes everything. I ran the same script at two other noise levels. With noise 0.7, IVF-Flat hit recall 0.993 at nprobe=2. With noise 3.0 (close to structureless), IVF-Flat reached only 0.691 at nprobe=64. If your embeddings aren't clusterable, IVF needs to scan a large fraction of the data.

Parameter caveat: I set nlist to 316, the square root of N, which is below the 4 to 16 times square root of N range the FAISS wiki suggests, so a larger nlist could change the IVF rows. Timing caveat: 500 queries batched per call, one thread, a shared cloud VM, no repeats. Treat differences under 20 percent as noise.

How do metadata filters interact with ANN indexes?

Strong answer outline

• Real queries say "nearest chunks where tenant = X and date after Y". There are two simple strategies. Pre-filter: restrict to the allowed set, then search. Post-filter: search, then drop disallowed hits.
• Post-filtering is easy but can return fewer than k results when the filter is selective, because most of your top candidates get discarded. You compensate by over-fetching, which costs latency.
• Pre-filtering on a graph can break connectivity: if most nodes are excluded, the greedy walk can't reach the allowed ones. Engines handle this in different ways (filtered traversal, per-partition indexes, falling back to brute force when the allowed set is small). I haven't benchmarked any of them, so in an interview say that you'd check how your engine does it.
• A practical pattern: partition by the field that is always in the filter, such as tenant, and build one index per partition.

Follow-up: Ten thousand tenants, each with 500 vectors. HNSW per tenant? Probably not. At that size, flat search per tenant is exact and fast, and you avoid managing ten thousand graphs. Do the arithmetic: 500 vectors times 128 dimensions is a trivial scan.

Common wrong answer: "Just filter the results afterward." That works until the filter removes 99 percent of results.

Which index would you pick for a given workload?

Use this as a starting decision table. It is my judgment, not an industry standard, and every row ends in "then measure".

Follow-up: Recall at 10 is 0.9. Is that good? Ask what the downstream step is. A separate recall metric means little unless you've measured answer quality on a labelled set. See building evaluation datasets for how to get one.

Common wrong answer: "Pick the one with the highest recall." Flat has the highest recall and is the right choice only when it is fast enough.

Run it yourself

Install with pip install faiss-cpu hnswlib numpy. This trimmed version measures the IVF-Flat and HNSW rows. I ran the longer script that produced the output above (Python 3.13, 2026-10-09).

import time, numpy as np, faiss, hnswlib

rng = np.random.default_rng(0)
N, D, NQ, K, NOISE = 100_000, 128, 500, 10, 2.0
centers = rng.normal(size=(200, D)).astype("float32")
X = centers[rng.integers(0, 200, N)] + NOISE * rng.normal(size=(N, D)).astype("float32")
Q = centers[rng.integers(0, 200, NQ)] + NOISE * rng.normal(size=(NQ, D)).astype("float32")
X /= np.linalg.norm(X, axis=1, keepdims=True)
Q /= np.linalg.norm(Q, axis=1, keepdims=True)

flat = faiss.IndexFlatIP(D); flat.add(X)
_, gt = flat.search(Q, K)
recall = lambda I: np.mean([len(set(I[i]) & set(gt[i])) / K for i in range(NQ)])

ivf = faiss.IndexIVFFlat(faiss.IndexFlatIP(D), D, 316, faiss.METRIC_INNER_PRODUCT)
ivf.train(X); ivf.add(X)
for nprobe in (1, 4, 16, 64):
    ivf.nprobe = nprobe
    t = time.perf_counter(); _, I = ivf.search(Q, K)
    print("ivf", nprobe, round(recall(I), 3), round((time.perf_counter() - t) / NQ * 1000, 3), "ms")

h = hnswlib.Index(space="ip", dim=D)
h.init_index(max_elements=N, M=16, ef_construction=200)
h.set_num_threads(1); h.add_items(X)
for ef in (10, 50, 200):
    h.set_ef(ef)
    t = time.perf_counter(); labels, _ = h.knn_query(Q, k=K)
    print("hnsw", ef, round(recall(labels), 3), round((time.perf_counter() - t) / NQ * 1000, 3), "ms")

Swap the random data for your own embeddings and your own held-out queries. That single change tells you more than any benchmark post, including this one.

How to prepare for this round

• Be able to state, from memory, what M, efConstruction, efSearch, nlist and nprobe each change, and which of them need a rebuild.
• Memorise the HNSW memory formula and the PQ code size, then do the 50-million-vector example aloud.
• Produce one recall-versus-latency table yourself, even a small one. Interviewers can tell the difference between recited and measured.
• Know your fallback sentence: "I'd measure on our data" is only good if you can name what you'd measure, which is recall at k against exact search, p95 latency, memory and build time.
• Revisit how chunking and embedding model choice affect what you are indexing, because index tuning can't fix poor chunks.

What I could not verify

The data is synthetic, so I make no claim about how these indexes behave on real text embeddings or at millions of vectors. I read the HNSW and FAISS (GPU) papers only through their arXiv abstracts and the FAISS index-choice wiki through a summarising fetch. I did not re-read the product quantization paper, so the PQ description is standard background rather than a cited claim. Filtered-search behaviour of specific vector databases is described conceptually and was not tested. Timings come from a single run on a shared virtual machine.