The Recall Ceiling

An HNSW index over 4 million 768-dimension vectors was built with $M = 8$ and $efConstruction = 64$ . Product requires recall@10 of at least 0.97 against exact search, and p99 query latency under 40 ms. You sweep the search parameter:

efSearch	recall@10	p99 latency
16	0.71	3.1 ms
40	0.83	6.0 ms
100	0.89	13 ms
250	0.925	31 ms
600	0.937	74 ms
1200	0.941	148 ms

What gets you to the target?

Switch to IVF-PQ with $nprobe = 64$ , which searches a much larger candidate set per query.

Rebuild the index with a larger $M$ (the paper's usable range runs to 48) and a larger $efConstruction$ . The 0.94 plateau is a property of the graph, not of the search.

Set $efSearch$ to 4,000 and add read replicas so the extra latency is absorbed by fanning queries out.

Reduce the vectors to 256 dimensions with PCA before indexing, so each graph hop touches a third of the memory and you can afford a much larger $efSearch$ .