# Cluster with Auctions for Vector Search

arXiv: https://arxiv.org/abs/2607.13728 · HTML: https://mlsanity.com/paper/2607.13728/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 15 Jul 2026.

## Builds on (most cited first, 13 of 13)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [LAION-400M: Open Dataset of CLIP-Filtered 400 Million Image-Text Pairs](https://mlsanity.com/paper/2111.02114/) (2021)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [A Self-Supervised Descriptor for Image Copy Detection](https://mlsanity.com/paper/2202.10261/) (2022)
- [Large Memory Layers with Product Keys](https://mlsanity.com/paper/1907.05242/) (2019)
- [Spreading vectors for similarity search](https://mlsanity.com/paper/1806.03198/) (2018)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [Unsupervised Neural Quantization for Compressed-Domain Similarity Search](https://mlsanity.com/paper/1908.03883/) (2019)
- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [Inference-time sparse attention with asymmetric indexing](https://mlsanity.com/paper/2502.08246/) (2025)
- [Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search](https://mlsanity.com/paper/2403.01797/) (2024)
- [Unsupervised Space Partitioning for Nearest Neighbor Search](https://mlsanity.com/paper/2206.08091/) (2022)

## Abstract (arXiv)

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× 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.