What is recall decomposition across shards?
Recall decomposition across shards splits end-to-end ANN recall into staged probabilities – whether the right shards were probed, whether each probed shard’s local index found the true neighbors, and whether top-k merge kept those hits – so you can see which layer is actually dropping neighbors.
Why does distributed recall factor into separate stages?
On a single HNSW graph, “recall” mostly means the greedy walk with a given ef found the true neighbors. Once the corpus is partitioned, a miss can happen before any graph walk starts. A true neighbor that lives on shard B is invisible if the coordinator never contacts B; if B is contacted but local ANN under-explores or under-fetches, the neighbor never enters the candidate pool; if it enters the pool but ranks below the merge cutoff because other shards flooded better-looking approximate hits, it still disappears from the API response. Thinking in stages turns a vague “sharded search feels worse” symptom into a measurable product: coverage (routing / fan-out) × local ANN recall × merge retention. Research on partitioned ANNS evaluates routing independently – often with exhaustive search inside the selected shards as an oracle – then measures leaf-index recall given that oracle, exactly so the two failure modes are not conflated.
How those factors behave depends on the sharding policy.
How do random versus cluster-based layouts change the decomposition?
Under random hash sharding – Weaviate’s default UUID-based placement – a full fan-out means routing recall is essentially 1 for unfiltered search: every shard is probed, so end-to-end recall is dominated by per-shard HNSW quality, local k’/ef depth, filters, and merge. Raising shard count does not invent a routing problem, but it can change local graph quality and straggler behavior. Under cluster-based sharding, routing recall is the fragile term: nprobe too small, stale centroids, or boundary neighbors in an unprobed cell drive systematic misses that no amount of local ef can fix. Overlap (storing boundary vectors in multiple shards) and richer routing indexes raise that first factor at storage or CPU cost. HFresh-style posting search inside one Weaviate shard follows the same decomposition at a smaller scale: searchProbe is routing over postings; RQ rescoring and local scan depth are the leaf stage.
Filters, limits, and consistency add more terms that operators often misattribute to “HNSW.”
What other factors multiply into observed recall?
Pre-filters shrink the eligible set on each shard; if local search does not over-fetch enough candidates relative to filter selectivity, merge never sees survivors. Dynamic ef tied to limit in Weaviate means a smaller requested k can implicitly search less deeply – so changing limit changes not only truncation but exploration, which looks like recall decomposition between “search depth” and “final cut.” Partial fan-out from timeouts or failed shards zeros routing recall for those partitions for that query. Replica selection can query a stale HNSW copy that lacks recent inserts, which is a consistency miss rather than an algorithm miss. Quantization without enough rescore over-fetch is another leaf-stage loss. The diagnostic habit is to hold stages fixed while sweeping one knob: nprobe or shard set, then ef/k’, then merge k’, and record which sweep moves recall.
A practical playbook turns the decomposition into actions.
How should you diagnose and fix recall by stage?
Build a labeled query set with known neighbor IDs and the shard each neighbor lives on. Measure routing hit rate: fraction of queries where every needed shard (or posting) was probed. Measure conditional leaf recall: among probed shards, did local search return the neighbor when run with exhaustive or very high ef as a ceiling? Measure merge retention: was the neighbor present in some shard’s returned list but absent after global top-k? Fix routing with more probes, overlap, or full fan-out; fix leaf recall with higher ef/efConstruction, stronger build params, or less aggressive compression; fix merge with larger per-shard k’. Use Weaviate query profiles to see per-shard timing, but pair them with ID-level recall checks – fast shards can still be wrong. Never tune only end-to-end recall without knowing which factor moved.
Recall decomposition across shards is the product of coverage, local ANN success, and merge retention – fix the stage that is actually failing. Next, read load skew for when uneven shards distort both latency and local recall, fault tolerance for when missing fan-out arms zero coverage, and the fan-out / top-k merge pages for the mechanics behind the first and third factors.