CwA: New vector search method boosts throughput 4.7x with auctions
Jointly learns partitions and probing, beating deep neural methods even in-distribution.
A new paper from Meta AI researchers (Swann Bessa, Pierre Fernandez, Gergely Szilvasy, Matthijs Douze, Hervé Jégou) proposes CwA (Cluster with Auctions) to improve large-scale approximate nearest neighbor search. Traditional methods use the same function for both assigning database vectors to clusters and probing clusters for queries, which is suboptimal when query and database distributions differ. CwA addresses this by jointly learning a balanced database partition and a neural probing function, optimizing directly for the query distribution. It alternates between gradient descent on the probing network and a large-scale combinatorial optimization of cluster assignments solved via a parallelizable auction algorithm that naturally balances the partition.
CwA demonstrates significant gains: when query and database distributions differ, it achieves up to 4.7x higher throughput at equal recall compared to state-of-the-art methods. Even in the in-distribution setting, a simple linear probing function trained with CwA outperforms more complex deep neural methods. The approach also extends to Cartesian product clustering for finer granularity. The paper, submitted to NeurIPS 2026, offers a practical solution for vector search in scenarios like recommendation systems or retrieval where query patterns may shift over time.
- CwA jointly optimizes database partition and query probing, unlike conventional two-step methods.
- Uses a parallelizable auction algorithm for balanced cluster assignment at scale.
- Achieves up to 4.7x throughput improvement over state-of-the-art at equal recall when distributions differ.
Why It Matters
Enables faster, more accurate vector search for production systems with shifting query distributions, like recommendation engines.