A multi-tenant assistant searches one HNSW index of 200M vectors and filters results to the requesting tenant. Large tenants are fine. For tenants with only a few thousand documents recall collapses and latency triples. Which change fixes it?
Show the full answer Hide the answer
The deciding property
Filter selectivity. A tenant with 5,000 documents in a 200M-vector index is one part in 40,000. An HNSW graph walk follows edges by vector similarity and knows nothing about tenants, so it explores a neighbourhood in which 39,999 of every 40,000 neighbours are discarded by the filter. The walk either terminates having found almost nothing that passes, or keeps expanding until latency blows out. That is both symptoms in one mechanism.
Large tenants are fine for the same reason: at one part in ten, the filter barely changes the walk.
Why partitioning is the answer
Give each tenant its own index, or place tenants in shards and route on tenant id. The filter stops being a filter and becomes a lookup. A 5,000-vector index is searched exhaustively in under a millisecond with perfect recall, and the small-tenant case becomes the cheapest case rather than the worst one. It also gives you per-tenant deletion, per-tenant rebuilds and a hard isolation boundary that a metadata field never provides.
The cost is real: thousands of small indexes mean per-index memory overhead and a routing layer, and one enormous tenant may still need its own sharded ANN index. A common shape is a dedicated index above a size threshold and a shared index for the long tail, since the long tail's tenants are individually tiny and exhaustive search over a shared partition is affordable.
Why the other options fail
- Raise ef_search globally. It does recover some recall, and it raises latency for every tenant including the ones that were healthy, to fix a problem only small tenants have. It is the tuning knob people reach for because it is the one exposed, and it treats the symptom.
- Fetch a much larger candidate set and post-filter. The arithmetic defeats it. To land 10 results for a one-in-40,000 tenant you need roughly 400,000 candidates before filtering, which is no longer approximate search in any useful sense.
- Exact brute-force search for every query. Correct for the small tenants and impossible for 200M vectors on every request. This is the right answer applied at the wrong scope, which is exactly what partitioning lets you do selectively.
- Change the distance metric. Cosine and inner product differ on normalised vectors only in scale. It changes nothing about graph traversal under a selective filter, and it is the option that sounds technical while touching nothing.
What would flip the decision
| If this changes | Choose | Because |
|---|---|---|
| Filters are low-selectivity (over ~10% pass) | Keep one index with filtering | The walk is barely perturbed and one index is far simpler |
| The engine supports filter-aware graph traversal | Re-measure before partitioning | Some engines push the predicate into the walk and hold recall to much lower selectivity |
| Tenant count grows past tens of thousands | Shard by tenant hash rather than per-tenant index | Per-index overhead starts to dominate memory |
| Queries must span tenants | Partitioning is wrong | Cross-partition search reintroduces the fan-out you removed |
Common weak answers
"Add more memory." The index already fits; the problem is graph traversal under a predicate, not capacity. "Use a different vector database." Most engines share this behaviour because they share the graph algorithm, and the selectivity arithmetic does not care about the vendor.