Your HNSW index hits 95% recall at 10M vectors but drops to 78% at 100M. Users start missing answers. How do you maintain retrieval quality as your vector DB scales?

What you need to know

How HNSW finds neighbours

Recall@k is the share of the true top-k neighbours (found by exact, brute-force search) that the index returns. At 10M vectors, a given search effort explores enough of the graph. At 100M, the same effort explores a proportionally smaller neighbourhood, so the greedy walk more often stops at a "good enough" region and misses the true neighbours.

The knobs

Names vary by database (hnsw.ef_search in pgvector, hnsw_ef in Qdrant), but the ideas are the same.

Measure it: sweep ef against exact search

1import faiss, numpy as np23xb = np.load("sample_vectors.npy").astype("float32")   # a sample of real vectors4xq = np.load("real_queries.npy").astype("float32")      # 1,000 real query embeddings5exact = faiss.IndexFlatIP(xb.shape[1]); exact.add(xb)6_, truth = exact.search(xq, 10)78hnsw = faiss.IndexHNSWFlat(xb.shape[1], 32, faiss.METRIC_INNER_PRODUCT)9hnsw.hnsw.efConstruction = 20010hnsw.add(xb)11for ef in (64, 128, 256, 512):12    hnsw.hnsw.efSearch = ef13    _, got = hnsw.search(xq, 10)14    recall = np.mean([len(set(g) & set(t)) / 10 for g, t in zip(got, truth)])15    print(f"ef={ef:4d} recall@10={recall:.3f}")

Use real queries, not random vectors: real data has clusters, and recall behaves differently. Pick the smallest ef that meets your recall target within the latency budget, then time it on the production database.

Structural fixes when tuning is not enough

• Quantise and rescore. If a 100M index no longer fits in RAM, the database pages to disk, and both latency and effective recall fall. Quantised vectors keep it in memory; rescore the top 100 candidates with full vectors.
• Partition by metadata. If queries always filter by tenant, language or year, give each partition its own smaller graph. Smaller graphs reach higher recall for the same effort, and filtering inside one huge graph can itself hurt recall.
• Over-fetch and rerank. Retrieve 100, rerank with a cross-encoder, keep 10. A reranker cannot recover a document the ANN step missed, so this helps ranking, not recall.

A real-life example

Scenario, numbers made up. A job portal's semantic search grows from 10M to 100M resume chunks in a year. Recruiters complain that obvious candidates are missing. A recall check against exact search on 1,000 real queries shows recall@10 at 78%, down from 95% at launch.

The team sweeps ef_search from 64 to 512. At 256, recall is 91% and p95 search latency moves from 12 ms to 31 ms, inside the 50 ms budget. For the rest, they partition by country (most searches are within India) and rebuild with M = 48. Recall reaches 96%. A nightly job now runs the recall check and alerts below 92%.

Follow-up questions to expect

• "Why not always use exact search?" — At 100M vectors, brute force means scanning every vector per query, far too slow and costly for live traffic. It is perfect for measuring recall on a sample, though.
• "What else can lower recall at scale?" — Restrictive metadata filters inside a large graph, many deletes that leave the graph poorly connected, and index settings copied from a small test set.
• "When would you switch index type?" — When memory cost dominates, a disk-based index such as DiskANN, or IVF with product quantisation, trades a little recall for much lower cost.