Federated Retrieval Over Embedding-Heterogeneous Vector Databases

Vector databases are increasingly used to manage unstructured data by mapping them into high-dimensional embeddings and enabling efficient similarity retrieval. Many realworld applications, such as legal document retrieval and medical question answering, require embedding-based retrieval in federated environments where data are distributed across autonomous silos. We formulate this setting as Federated Approximate Nearest Neighbor Search (FANNS), where a server issues a query along with a query embedding model, aiming to retrieve the top- $k$ nearest objects from datasets across all silos. A key challenge in FANNS is embedding heterogeneity, where silos and the server employ different embedding models, a problem overlooked in prior research. To address this challenge, we exploit the nonIID nature of federated data and propose two novel adaptive algorithms for FANNS queries. The first is a competition-based method that dynamically adjusts retrieval sizes across silos, though it can be sensitive to misleading candidates. The second is a contribution-based method that samples promising silos based on their accumulated contributions, and we provide theoretical guarantees on its latency reduction. Evaluations on four datasets show that our method achieves over 90% retrieval accuracy and $\mathbf{2. 3} \times$ to $\mathbf{6. 2} \times$ speedups over existing solutions.