Research map / Learning theory and algorithms / Prediction and decision losses

Cluster with Auctions for Vector Search

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Approximate nearest neighbor indexing · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Cluster with Auctions (CwA), which separates a neural query probing function from a balanced database partition and optimizes both alternately via a unified cross-entropy loss, solving the partition step as a capacitated linear assignment with the auction algorithm.

Problem

Partition-based approximate nearest neighbor search typically uses the same assignment for database vectors and queries (e.g., K-Means/IVF), ignoring the query distribution (OOD) and cluster balance, and neural partitioning methods conflate partition and probing function.

Approach

Decouple the partition (a balanced assignment of database vectors found by a capacitated linear assignment solved with the GPU auction algorithm) from a neural probing function trained on the query distribution with cross-entropy against the distribution of queries' k' nearest neighbors over clusters; alternate both steps to decrease a shared loss. A product-key variant (CwA-Prod) and an HNSW-inde

Key results

• On TextToImage1M at 256 clusters, CwA (2 FFN) reaches 3240 QPS vs 1338 for K-Means at Recall@10=0.8 (~2.4x).
• On LAION1M at 256 clusters, CwA reaches 1295-1225 QPS vs 276 for K-Means (~4.7x).
• On 100M vectors with 262k clusters, CwA-Prod reaches 671 QPS vs 60 for Residual Quantization on Text-to-Image at Recall@10=0.8 (~11x).

Surprising findings

• A linear probing function (0 FFN layers) outperforms deeper neural baselines (Neural LSH, USP, BLISS) on all four 1M datasets.
• Neural baselines (Neural LSH, USP) collapse below K-Means on out-of-distribution datasets.

Limitations

• Only a single partition is evaluated; multi-partition combination is left as future work.
• Results only on fixed databases; no out-of-sample extension for new database vectors.
• Training time is one to two orders of magnitude higher than K-Means; kNN graph construction dominates large-scale cost.

Experimental setup

Datasets: SIFT Deep Text-to-Image LAION

Benchmarks: SIFT1M Deep1M TextToImage1M LAION1M Deep10M TextToImage10M LAION10M SIFT100M Deep100M TextToImage100M LAION100M

Metrics: Recall@10 QPS selectivity

Baselines: K-Means USP Neural LSH BLISS Residual Quantization Inverted Multi-Index IVF-HNSW

Builds on: IVF Neural LSH BLISS USP inverted multi-index

Closest papers by meaning

• Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All (ICML 2025 · similarity 0.84)
• Machine Learning-Powered Combinatorial Clock Auction (AAAI 2024 · similarity 0.84)
• Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.82)
• Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search (NeurIPS 2025 · similarity 0.82)
• Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.81)
• LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table (CVPR 2025 · similarity 0.81)