Cluster with Auctions for Vector Search
Swann Bessa, Pierre Fernandez, Gergely Szilvasy, Matthijs Douze, Hervé Jégou
cs.IR, stat.ML
Submitted: 2026-07-15
Comments: 10 pages, 6 figures. Under review at NeurIPS 2026
License: http://creativecommons.org/licenses/by/4.0/
The gist: Large-scale approximate nearest neighbor search commonly relies on partitions for indexing: database vectors are partitioned into clusters, and for each query a probing function selects the clusters
Terminology
Abstract
Large-scale approximate nearest neighbor search commonly relies on partitions for indexing: database vectors are partitioned into clusters, and for each query a probing function selects the clusters to be scanned. The query probing function and the database partition are rarely treated as separate entities: most techniques assign queries with the same assignment function as the database vectors, which is suboptimal especially when database and query distributions differ. This paper introduces CwA (Cluster with Auctions), which addresses this limitation by jointly learning a balanced database partition and a neural probing function. CwA optimizes search performance directly for the query distribution. It minimizes its objective by alternating two steps: (i) gradient descent on the neural network of the probing function, and (ii) a large-scale combinatorial optimization of the cluster assignment for the database vectors. We solve the latter with a parallelizable auction algorithm that balances the partition by design. To further scale CwA, we extend the method to a Cartesian product of clusters that increases the partition's granularity. When database and query distributions differ, CwA achieves up to 4.7 times throughput over the state-of-the-art at equal recall. In the in-distribution (ID) setting, even a simple linear probing function trained with CwA outperforms competing deep neural methods.
Sources
- Learning Space Partitions for Nearest Neighbor Search
- Machine learning and high dimensional vector search
- Unsupervised Space Partitioning for Nearest Neighbor Search
- Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search
- The Faiss library
- Inference-time sparse attention with asymmetric indexing
- Think Locally, Act Globally: Perfectly Balanced Graph Partitioning
- LAION-400M: Open Dataset of CLIP-Filtered 400 Million Image-Text Pairs
Related papers
- The Price of Isolation: Estimating the Ecosystem Cost of Symmetric Two-Sided A/B Testing
- SCAR: Semantic Continuity-Aware Retrieval for Efficient Context Expansion in RAG
- MixLoRA-DSI: Dynamically Expandable Mixture-of-LoRA Experts for Rehearsal-Free Generative Retrieval over Dynamic Corpora
- QProtFuse: Query-Guided Layer Fusion for Retrieval-Augmented Protein Function Prediction
- DualView: Adaptive Local-Global Fusion for Multi-Hop Document Reranking
- How Do LLM-Generated Texts Impact Term-Based Retrieval Models?