REVIEW 3 major objections 6 minor 17 references
This paper claims that vector search improves when database partitioning and query probing are learned jointly — the partition via a balanced auction — yielding up to 4.7× throughput when query and database distributions differ.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
CwA jointly learns a balanced database partition and a query-adapted neural probing function, achieving up to 4.7x higher ANNS throughput at equal recall.
T0 review reviewed 2026-08-02 challenge →
load-bearing objection CwA is a genuine advance in query-aware partition-based ANNS with a clean formulation and strong OOD gains; it deserves a serious referee, who should push on the K-Means sparsification and the asymmetric supervision. the 3 major comments →
Cluster with Auctions for Vector Search
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
Core claim
The paper's central claim: jointly optimizing a database partition h and a neural probing function f_θ against a unified query-dependent cross-entropy loss is tractable and beats the inherited practice of using the same assignment rule for both roles. The enabling step is a loss decomposition showing that, for fixed f_θ, the joint loss over h is exactly a capacitated linear assignment problem solved by the auction algorithm, whose capacity quotas enforce near-perfect balance. The paper reports that CwA beats K-Means, Neural LSH, USP, and BLISS in-distribution even with a linear probe, and dominates out-of-distribution: ~2× over K-Means on Text-to-Image and 4.7× on LAION at Recall@10 = 0.8, w
What carries the argument
The central object is the joint loss L(θ, h) = Σ_i CE(p_{h,q_i}, f_θ(q_i)) with a hard quota Q on cluster size — where p_{h,q_i} is the distribution of a query's k′-nearest neighbors over clusters under the current partition, i.e., supervision derived from ground-truth neighbor sets. Its role is to make the partition and the probing function answer to the same objective, measured for the query distribution rather than for the database. The machinery that makes this tractable is the auction algorithm (Bertsekas, 1988) solving the partition step as a capacitated linear assignment; it is GPU-parallel, enforces balance by design, and in the product variant the score matrix factorizes into two n
Load-bearing premise
The load-bearing premise is that the optimal partition is reachable through a K-Means-restricted candidate set: every database vector may only be assigned to its κ nearest K-Means centroids (κ set around 5–10% of the cluster count), and the paper provides no sensitivity analysis or bound on how close this restricted optimum is to the unconstrained one.
What would settle it
Two concrete checks would settle the claim. First, rerun CwA on a fixed out-of-distribution benchmark with κ ranging from 1% to 100% of |C|: if throughput at equal recall keeps improving as κ grows, the reported 4.7× is an artifact of the sparsification restriction. Second, on a small instance (roughly 10k vectors, 64 clusters), compare the auction's assignment to the exact optimum of the same score matrix from a general-purpose solver: a non-negligible gap would mean the partition is not actually optimizing the stated loss, and the reported gains would need re-benchmarking against that gap.
If this is right
- Partition-based ANNS systems can be built whose probing function is explicitly trained on the queries users actually issue, so index quality need not degrade when the query stream drifts from the database distribution.
- Cluster balance is enforced by construction rather than hoped for, capping per-query candidate-list size and therefore worst-case latency — relevant to serving systems with tail-latency budgets.
- Even a linear probe with the same parameter count as K-Means outperforms deep neural baselines in-distribution, which the paper reads as evidence that previous approaches left significant room for improvement in learned partitioning.
- The product-key variant transfers the same joint optimization to ~262k clusters on 100M vectors, where fine-grained multi-codebook partitions are the norm, so the approach composes with large-scale inverted multi-index designs.
- The throughput gains come at a one-time indexing cost: training remains one to two orders of magnitude slower than K-Means, which the paper reports explicitly.
- The method is metric-agnostic, needing only ground-truth neighbors for training queries, so in principle it applies to any relation for which such neighbors can be obtained.
Where Pith is reading between the lines
- Because the probing function is trained on the query distribution, the framework could in principle be re-run when the query stream drifts further, yielding an adaptive index whose partition is refreshed by re-auctioning on new queries — a dynamic setting the paper does not evaluate.
- The sub-linear training-data scaling law (roughly 4× more queries per 100× index growth) is an empirical fit on one dataset; if it holds across modalities, learned partitioning becomes practical at web scale, but that generalization is untested.
- A natural stress test outside the paper's four benchmarks: vary the degree of query–database shift continuously and measure how the OOD gain decays toward the in-distribution gain, which would separate the benefit of query-aware probing from that of balanced assignment.
- The sparsification step (each vector eligible only for its κ nearest K-Means centroids) couples CwA's partition quality to an initialization it later claims to improve upon; testing whether the auction escapes that candidate set would reveal how much of the gain is genuinely learned versus inherited.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes CwA, a partition-based approximate nearest neighbor search (ANNS) method that jointly learns a database partition h and a neural probing function f_theta. The joint objective is the cross-entropy between the probe prediction f_theta(q) and the distribution of the query's k'-nearest neighbors over clusters, subject to a cluster-size quota. The authors show (Eqs. 5-7) that, for fixed f_theta, optimization over h is a capacitated linear assignment problem, which they solve with a GPU-friendly auction algorithm; for fixed h, f_theta is trained by backpropagation. Two variants are introduced: CwA-HNSW for large cluster counts and CwA-Prod, a product-key extension that scales to about 262k clusters. Experiments on 1M-100M databases in in-distribution (SIFT, Deep) and out-of-distribution (Text-to-Image, LAION) settings report up to 4.7x throughput over K-Means at equal recall in OOD settings, and strong ID results including a linear probe beating deep baselines.
Significance. If the empirical claims hold, CwA is a valuable contribution to learned partition-based indexing: it cleanly separates the partition and the probe, enforces balance, and reduces the partition update to a tractable combinatorial problem with a clean derivation in Eqs. (5)-(7). The auction pseudo-code and the product-key extension are useful methodological pieces. The headline result—that query-aware probing plus a jointly optimized partition gives large OOD gains—is falsifiable and interesting. However, the strength of the empirical claim is currently undercut by two issues: the actual implementation restricts the auction to a K-Means-defined feasible set without sensitivity analysis, and the method is given access to millions of labeled training queries that the baselines do not use. The central derivation is sound; what is needed is additional analysis and fairer comparisons, not a correction of the proof.
major comments (3)
- [Appendix F.3; Section 4.3] The objective in Eq. (3) and the derivation in Eqs. (5)-(7) are written for the full set of assignments h satisfying the quota. In the actual implementation, however, Appendix F.3 replaces the score matrix S with a sparse matrix: each database vector can be assigned only to the kappa closest preliminary K-Means centroids, with kappa about 5-10% of |C|, and the preliminary K-Means is never updated. The feasible set of the auction is therefore a small, K-Means-dependent subset of the feasible set of Eq. (3). Consequently, the h-step is no longer the global minimizer of the stated objective, so the 'consistent decrease' claim in Section 4.3/Figure 3 is not guaranteed under this restriction. This matters for the headline results: Table 1 (|C|=256) and Table 2 (|C|=65536) are exactly in the regime where the sparsification is active, and no sensitivity analysis over kappa or a suboptimality bo
- [Section 5.2 and Appendix D.4] CwA is trained on ntrain=5M-50M queries with ground-truth k'-NN supervision (Dtrain, Eq. (2)), while the reported baselines—Neural LSH, USP, BLISS—are trained without query labels, as described in Appendix D.4. Since the paper's central claim is that probing should be adapted to the query distribution, this comparison conflates the proposed method with unequal access to supervision. The 4.7x OOD improvement could in principle be obtained by any method if it were given the same labeled training queries. Please add a supervised baseline (e.g., train the baseline probe on the same Dtrain labels for a fixed partition, or fine-tune the baseline probe with Eq. (4)) and/or an unsupervised CwA ablation, and report these in Tables 1-3.
- [Appendix G; Section 5.2] The hyperparameters k' and ntrain are not independently chosen per dataset: Eqs. (10)-(11) are fitted on the Deep dataset and then used to set k' and ntrain for all datasets (Section 5.2 states that the values were chosen following the scaling law). This makes the scaling-law claim a fit, not an independent prediction, and leaves open the possibility that the OOD results are sensitive to the chosen k'/ntrain. Please provide cross-dataset validation (e.g., report the chosen values, and a sensitivity sweep on Text-to-Image and LAION), or re-tune k' for each dataset and show that the headlined gains persist.
minor comments (6)
- [Limitations, p.10] The limitations paragraph uses 'CWA' in uppercase ('out-of-sample variant of CWA'); should be 'CwA' for consistency.
- [Figure 1 caption] The legend 'K-Means Neural LSH USP BLISS' is missing separators; consider using commas or a column layout for readability.
- [Eq. (8)] The parameter count statement in Section 4.4 would benefit from an explicit note that gamma is a full |C|-sized matrix, so the reduction is from d|C| to 2d sqrt(|C|)+|C|, which is still a large saving but should be stated precisely.
- [Algorithm 3, Appendix F.1] The handling of the slot index s*_c and the final assignment of unassigned vectors is somewhat terse; a short explanation of why the final 'fill' step does not violate the quota would help.
- [Appendix D.4] For BLISS, the text says the parameter K was swept over powers of two and chosen by 'best recall'; please specify which evaluation set was used for this selection to avoid any appearance of test-set tuning.
- [Table 1] USP is reported as '—' for LAION in both cluster counts; a footnote explaining why (e.g., method did not complete or was not run) would make the table self-contained.
Circularity Check
No significant circularity: the CwA derivation is a self-contained coordinate-descent loop; auxiliary scaling-law fits and self-citations are not load-bearing.
full rationale
The paper's central chain is a coordinate-descent derivation, not a circular one. In Eq. (3) the objective is an explicit cross-entropy loss between the query-neighbor cluster distribution p_{h,q} (built from the current h) and the probe f_theta. Step A minimizes this over theta with h fixed; Step B, via Eqs. (5)-(7), rewrites the loss (plus the quota constraint) exactly as a capacitated linear assignment and solves it with the auction algorithm. The score matrix S in Eq. (7) depends only on the current f_theta and the training query neighborhood sets N_{k'}(q_i); none of the reported test metrics (Recall@10, QPS, selectivity) appears in the optimization objective or in the score matrix, so there is no fitted-input-called-prediction loop. The Appendix F.3 K-Means sparsification restricts the feasible assignments, but it is an implementation constraint on the same objective, not a quantity fitted to the headline result; any suboptimality is an empirical sensitivity issue, not circularity. The scaling laws in Eqs. (10)-(11) are in-sample log-linear fits on the Deep dataset used to choose k' and ntrain; the paper presents them as empirical heuristics rather than as evidence for the main benchmark claims, so this is a mild hyperparameter-tuning concern, not a reduction of a prediction to its inputs. Self-citations (Faiss, the cluster-count power law, prior neural-indexing work) are contextual and non-load-bearing, and the main claims are validated against external baselines. Overall, the derivation chain is self-contained.
Axiom & Free-Parameter Ledger
free parameters (6)
- k' (supervision neighborhood size) =
50 (1M), 100 (10M/100M)
- ntrain (number of training queries) =
5M (1M), 20M (10M), 50M (100M)
- κ (candidate clusters per vector in sparsified score matrix) =
5-10% of |C|
- Quota Q =
1.05 nindex/|C|
- Auction epsilon and iterations =
epsilon=1e-2, 10,000 bidding steps
- Number of FFN blocks M =
0 or 2
axioms (5)
- standard math Auction algorithm converges to a near-optimal solution of the capacitated linear assignment problem within 10k steps.
- domain assumption Training queries with accurate k'-NN ground truth are available for the training distribution.
- domain assumption The test query distribution matches the training query distribution in each benchmark.
- ad hoc to paper The K-Means-based sparsification of the score matrix does not exclude the optimal partition.
- domain assumption Cross-entropy between ph,q and fθ is a valid proxy for Recall@k under top-m probing.
Cite this review
Pith. "Pith review of Cluster with Auctions for Vector Search." pith.science (2026). https://pith.science/paper/2WYVA75Z
@misc{pith2026260713728,
author = {Pith},
title = {Pith review of: Cluster with Auctions for Vector Search},
year = {2026},
howpublished = {\url{https://pith.science/paper/2WYVA75Z}},
note = {Machine review of arXiv:2607.13728}
}
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.
Reference graph
Works this paper leans on
-
[3]
The coefficient ϵ, which represents the level of approximation in the auction (see Bertsekas (Bertsekas, 1988)), is set to1× 10−2
Additional detailsThe auction algorithm is executed with niter = 10, 000bidding steps. The coefficient ϵ, which represents the level of approximation in the auction (see Bertsekas (Bertsekas, 1988)), is set to1× 10−2. If some items remain unassigned at the end of the auction algorithm, we choose to assign them to the most appropriate (highest entry in the...
1988
-
[7]
Unsupervised space partitioning for nearest neighbor search, 2022.https://arxiv.org/abs/2206.08091
Abrar Fahim, Mohammed Eunus Ali, and Muhammad Aamir Cheema. Unsupervised space partitioning for nearest neighbor search, 2022.https://arxiv.org/abs/2206.08091. Lars Gottesbüren, Laxman Dhulipala, Rajesh Jayaram, and Jakub Lacki. Unleashing graph partitioning for large-scale nearest neighbor search, 2024.https://arxiv.org/abs/2403.01797. Gaurav Gupta, Thar...
Pith/arXiv arXiv 2022
-
[16]
To choose parameter K (see Gupta et al
Training parameters were kept the same as in the original paper. To choose parameter K (see Gupta et al. (Gupta et al., 2022)), we swept on powers of 2 and chose the value with best recall. E HNSW plugged on CwA: CwA-HNSW When plugging a graph index on the last linear layer ofCwA, the goal is to retrieve the top-m scoring clusters without computing all sc...
2022
-
[31]
Stanislav Morozov and Artem Babenko
Curran Associates, Inc., 2018.https://proceedings.neurips.cc/paper_files/paper/ 2018/file/229754d7799160502a143a72f6789927-Paper.pdf. Stanislav Morozov and Artem Babenko. Unsupervised neural quantization for compressed-domain similarity search. In ICCV,
2018
-
[200]
•BLISS: We use the architecture described in Gupta et al
Training parameters are kept the same as in the original paper. •BLISS: We use the architecture described in Gupta et al. (Gupta et al., 2022), an MLP with 1 hidden layer of hidden size
2022
-
[512]
eco" configuration because the
Training parameters are kept the same as in the original paper. For graph partitioning with KaHiP (Sanders and Schulz, 2012), we chose the "eco" configuration because the "strong" configuration did not complete after 72 hours on the smallest datasets. • USP: We use the architecture described in Fahim et al. (Fahim et al., 2022), an MLP with 1 hidden layer of size
2012
-
[1988]
doi: 10.1007/BF02186476. Dimitri P. Bertsekas. The auction algorithm for the transportation problem.Annals of Operations Research, 20:67–96, December
-
[1989]
Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X
doi: 10.1007/BF02021667. Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X. Sean Wang. Roargraph: A projected bipartite graph for efficient cross-modal approximate nearest neighbor search.Proceedings of the VLDB Endowment, 17(11):2735–2749, July
-
[1991]
Romain Tavenard, Hervé Jégou, and Laurent Amsaleg
doi: 10.1007/BF01759061.https://doi.org/10.1007/BF01759061. Romain Tavenard, Hervé Jégou, and Laurent Amsaleg. Balancing clusters to reduce response time variability in large scale image search. In2011 9th International Workshop on Content-Based Multimedia Indexing (CBMI), pages 19–24. IEEE,
work page doi:10.1007/bf01759061.https://doi.org/10.1007/bf01759061
-
[2005]
Association for Computing Machinery. ISBN 1595930469. doi: 10.1145/1060745.1060840. https: //doi.org/10.1145/1060745.1060840. Dimitri P. Bertsekas. The auction algorithm: A distributed relaxation method for the assignment problem.Annals of Operations Research, 14(1):105–123,
-
[2010]
17 • Neural LSH: We use the architecture described in Dong et al
and the Inverted Multi-Index (Babenko and Lempitsky, 2012). 17 • Neural LSH: We use the architecture described in Dong et al. (Dong et al., 2020), an MLP with 3 hidden layers of size
2012
-
[2012]
Artem Babenko and Victor Lempitsky
doi: 10.1109/CVPR.2012.6248038. Artem Babenko and Victor Lempitsky. Additive quantization for extreme vector compression. InCVPR,
arXiv 2012
-
[2014]
doi: 10.1007/978-3-662-44415-3_4
ISBN 978-3-662-44414-6. doi: 10.1007/978-3-662-44415-3_4. Yu A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.IEEETransactions on Pattern Analysis and Machine Intelligence, 42(4):824–836,
-
[2017]
Learning space partitions for nearest neighbor search, 2020.https://arxiv.org/abs/1901.08544
Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search, 2020.https://arxiv.org/abs/1901.08544. Matthijs Douze. Machine learning and high dimensional vector search, 2025.https://arxiv.org/abs/2502.16931. Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Ma...
Pith/arXiv arXiv 2020
-
[2018]
Inference-time sparse attention with asymmetric indexing, 2025.https://arxiv.org/abs/2502.08246
Pierre-Emmanuel Mazaré, Gergely Szilvasy, Maria Lomeli, Francisco Massa, Naila Murray, Hervé Jégou, and Matthijs Douze. Inference-time sparse attention with asymmetric indexing, 2025.https://arxiv.org/abs/2502.08246. Stanislav Morozov and Artem Babenko. Non-metric similarity graphs for maximum inner product search. In S. Bengio, H. Wallach, H. Larochelle,...
Pith/arXiv arXiv 2025
-
[2019]
Peter Sanders and Christian Schulz. Think locally, act globally: Perfectly balanced graph partitioning.CoRR, abs/1210.0477, 2012.http://arxiv.org/abs/1210.0477. Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki. LAION-400M: open dataset of clip-filtered 4...
Pith/arXiv arXiv 2012
-
[2024]
doi: 10.14778/3681954.3681959.http://dx.doi.org/10.14778/3681954.3681959
ISSN 2150-8097. doi: 10.14778/3681954.3681959.http://dx.doi.org/10.14778/3681954.3681959. Yongjian Chen, Tao Guan, and Cheng Wang. Approximate nearest neighbor search by residual vector quantization. Sensors, 10(12):11259–11273,
This paper was first reviewed by deepseek-v4-flash on August 2, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.