Graph indexes improve multi-tenant vector search under concurrent updates
Recall-Bounded Staleness for Filtered Multi-Tenant ANN Graph Indexes under Concurrent Updates
DatabasesDistributed, Parallel, and Cluster Computing
Summary
Searching for similar items in large collections of data points is tricky when updates happen all the time. The authors created a graph-based index that keeps track of many users’ data while updates come in, all without losing accuracy on search results. They developed a way to understand and limit how much search quality drops due to data updates that haven’t been fully integrated yet. They also built system tools that keep search fast and accurate for each user, even under heavy data changes.
What this means in practice
- •For cloud service engineers: Maintain high-quality vector search results across many users while continuously updating and filtering their data without breaking service guarantees.
- •For recommendation system developers: Support real-time updates and multi-tenant filtering in approximate nearest neighbor search to improve personalized recommendations under workload churn.
Authors
Namrata Das, Kailas Devadkar, Anand Godbole
Abstract
Production vector search must continuously ingest, delete, and re-tenant vectors while serving low-latency, high-recall, metadata-filtered approximate nearest-neighbor (ANN) queries for many tenants with per-tenant service-level objectives. Existing graph-based ANN systems address these requirements largely in isolation, leaving recall during concurrent re-optimization without an analytical bound. We develop a graph-based index that combines streaming updates, filtered search, and multi-tenancy, with one theoretical result and two system mechanisms. Our theory decomposes per-tenant recall loss into staleness from updates not yet integrated into the graph and filtered navigability determined by the local density of points satisfying a tenant's predicate. The staleness component exhibits anti-amortization on a merge-based graph, integrating a larger batch of inserts increases recall degradation super-linearly, so larger merges do not reduce total staleness loss. Holding the insert horizon fixed while increasing merge size 20x, we observe a monotonic decrease in terminal recall@10 from 99.44% to 99.01%. For filtered search, the theory gives a parameter-free frontier-mass relationship in local predicate density and a query-averaged per-tenant recall bound. We instantiate the bound with a filter and tenant-aware staging cache and a select-not-resize scheduler with per-tenant staleness ceilings. On a FreshDiskANN substrate, the ceiling eliminates tight-tier SLA violations under the evaluated churn workload, while merge reordering changes terminal recall by only 0.02 percentage points. The results show how recall bounds can guide background maintenance without relying on merge resizing as a recall control mechanism.