Vector Search Is a Recall/Latency Trade, Not a Database Feature
ef_search, nprobe, and PQ are three dials on one curve. Measure recall against exact search, then choose where to sit.
Every vector database demo shows a query returning in 2ms. Almost none of them show what fraction of the true nearest neighbours it returned.
That fraction — recall@k against exact search — is the only number that makes the latency meaningful. A 2ms query with 0.72 recall is not a fast database; it is a random number generator with good PR.
The three dials
For HNSW:
M: edges per node. Higher means better recall and more memory.ef_construction: candidates during build. Higher means a better graph and a slower build.ef_search: candidates during query. Higher means better recall and slower queries. Runtime-tunable.
For IVF:
nlist: number of clusters.nprobe: clusters searched per query. This is the recall/latency dial.
For PQ/SQ:
- Compression ratio versus accuracy. PQ at 96 bytes per vector fits 1M × 768-dim vectors in about 96MB instead of 3GB, at a measurable recall cost.
What the curve looks like
1M vectors, 768 dimensions, 10-NN, one 16-core node:
| Config | Recall@10 | p99 latency | Index size |
|---|---|---|---|
| Exact (flat) | 1.00 | 240ms | 3.0GB |
| HNSW M=16, ef=32 | 0.91 | 2.8ms | 3.9GB |
| HNSW M=16, ef=64 | 0.96 | 4.2ms | 3.9GB |
| HNSW M=32, ef=64 | 0.98 | 6.1ms | 4.8GB |
| IVF nprobe=8 | 0.87 | 1.9ms | 3.0GB |
| IVF nprobe=32 | 0.96 | 5.4ms | 3.0GB |
| HNSW + PQ96 | 0.88 | 1.1ms | 0.1GB |
The knee is usually between 0.95 and 0.97. Past that, each additional point of recall costs disproportionate latency. For most search UIs 0.95 is plenty, because the ranking model and the user's tolerance are both noisier than that. For deduplication or legal discovery, 0.99 may be mandatory.
Measure recall; do not assume it
Ground truth is cheap on a sample:
# sample 1,000 queries; exact top-10 via brute force on the same vectors
truth = exact_topk(queries_sample, vectors, k=10)
approx = index.search(queries_sample, k=10)
recall = mean(len(set(t) & set(a)) / 10 for t, a in zip(truth, approx))Do this on the actual data distribution, not a random slice of the embedding space. Clustered data is where approximate indexes fail, and production data is clustered.
Filtering is where recall quietly dies
The common failure: a tenant filter applied after the vector search. The index returns 100 neighbours, the filter keeps 3, and everyone calls it a day. With selective filters you are effectively asking for the global top-100 and hoping your tenant appears in it.
Options, in order of preference:
- Partition the index by tenant or category, and search the partition.
- Pre-filter with a bitmap and search inside it, if the engine supports it.
- Over-fetch aggressively (k = 1000) and pay the latency.
- Do not post-filter and call it done.
Hybrid search is usually worth it
Vector similarity alone is bad at exact identifiers, rare terms, and negations. BM25 plus vector with reciprocal rank fusion is a few lines and usually beats either alone:
score = 1 / (60 + rank_bm25) + 1 / (60 + rank_vector)The constant 60 is arbitrary but robust; rank fusion does not need calibrated scores between the two systems.
What I would ship
- HNSW, M=16, ef_construction=200, ef_search tuned to the latency budget.
- Monthly recall measurement on 1k real queries with exact ground truth.
- Partition by tenant before the index gets big.
- Hybrid with BM25 for anything user-facing.
- Alert on recall, not just latency. A silent recall drop is worse than a slow query.
A vector index is a compression of a search problem. The compression is the product decision; the latency is the bill.