M1. Query-aware placement is not compared with the right baselines, under a fair protocol
The central claim is that query-aware placement beats query-agnostic placement. The experiments do not test this claim properly.
Stronger baselines are needed. The motivation names SPANN (ε-closure assignment) and SOAR (orthogonality-amplified spilling) as the existing query-agnostic placement rules. Yet the main experiments (Sec. 4, Tables 1–3) compare only against vanilla IVF and uniform top-r replication. Table 1 shows that top-r replication barely helps: on most datasets "agnostic" QPS equals vanilla IVF, so the best r is 1. The headline "dominates query-agnostic replication on all 24 datasets" therefore amounts to beating vanilla IVF.
- SOAR can be used in 23 of the 24 datasets. It handles the inner-product datasets directly, and most unit-norm datasets, where cosine and Euclidean ranking reduce to inner product. In Appendix D, SOAR runs inside ScaNN with anisotropic quantization and reordering, against a float IVF, so the comparison mixes placement, quantizer and engine. Even so, SOAR is a median ~3.4x faster than query-aware IVF and 1.41x faster than query-aware IVF + RaBitQ. So that comparison does not settle the algorithmic differences.
- RAIRS (Yang & Chen, SIGMOD 2026) optimizes redundant assignment for general Euclidean IVF. Its AIR metric selects the secondary list using direction as well as distance. It also proposes a list layout (SEIL) that avoids recomputing distances for vectors scanned in several lists, which is a cost that query-aware replication increases. RAIRS has been on arXiv since January 2026 but appeared at SIGMOD in June 2026, so I will not hold the authors accountable for adding an empriical comparison, but a careful discussion is a fair ask.
- SPANN could have been used as another strong baseline with no caveats.
- More importantly, some newer query-aware IVF baselines are also missing. Learned probing (Vecchiato et al., 2024, which is cited) and learned partitions with redundancy (LIRA, see M6) are not compared.
The method's main tradeoff is index footprint, whether the lists live in RAM or on disk. Footprint is higher by 2.58x (median), and 5–21x on many datasets. Yet every headline comparison picks the fastest configuration regardless of footprint, so in Table 1 a 21x-footprint index competes with a 1x index. The paper should report QPS at recall 0.9 under footprint caps (for example, 1.5x, 2x, 3x vanilla IVF) against baselines under the same caps. Adding a constraint on |S| to the greedy assignment, or using it as a cutoff, seems doable. Table 7 also has no index-size column. The introduction says IVF is preferable "when memory is constrained". But in RAM, query-aware IVF has a larger footprint than vanilla IVF, and likely than HNSW at M = 32 for d \geq 512, while being ~3x slower than HNSW (median). On disk, the footprint grows by the same factor, and lists that are 2–21x larger also mean more bytes per probed list. The claimed niche needs evidence in both settings.
The paper needs an implementation-independent protocol based on probe counts. The method's premise is that storing copies lets a query reach its neighbors while probing fewer lists. However, the paper never reports the probe count \ell needed to reach the target recall, for any method. Table 6 lists \ell_train for the chosen indices, but not the search-time \ell. All placement methods share the same structure: one set of centroids, one probe rule, and only the assignment differs. Each method can therefore be simulated on the same centroids, with flat lists and exact distances: vanilla IVF, top-r, SOAR, RAIRS (AIR), SPANN closure, and query-aware IVF. For each, report the \ell and the scanned candidates needed to reach recall@K = 0.9, together with the entries per vector. Also report recall vs. \ell along the greedy prefix A(s), i.e., as replication grows. This is cheap, exact, independent of hardware and engine, and isolates the contribution of placement. Probe counts also matter on their own: on disk, each probed list costs at least one random IO. Probe count alone is not enough, though, because more copies trivially need fewer probes (replicating every vector into every list gives \ell = 1). The comparison should therefore operate at matched replication (e.g., query-aware IVF limited to the 2 entries per vector of SOAR/RAIRS), or shown as a Pareto front over (\ell, candidates, entries per vector).
M2. The source of the OOD gains is not identified, and the theory does not cover the experiments
On OOD datasets, query-aware IVF always uses centroids fit on the learning set (App. C, Table 6). Query-trained centroids are a query-aware ingredient in their own right, separate from the placement. A 2x2 ablation on the OOD datasets is needed: {base-trained, query-trained centroids} x {vanilla, query-aware placement}. The vanilla IVF column of Table 1 takes the better of the two centroid options, so the comparison is not unfair. But the paper never reports which option wins per dataset, nor query-aware placement with base-trained centroids. Without this, we cannot tell how much of the headline OOD gain (median 3.88x) comes from placement and how much from clustering the queries.
The theory assumptions do not hold in both experimental settings. Both theorems assume the centroids are independent of Q. In the OOD experiments, centroids are fit on the learning set, which is exactly where the main gains are. Hence, no reported OOD result falls under the theorems. In the ID experiments, the learning set is a subset of the base, k-means runs on the base, and learning queries stay in the base. So the centroids depend on Q there too, and the learning queries are not i.i.d. draws from the test-query distribution independent of P.
The sample requirement is much larger than "logarithmic in n" suggests. Here, I find are two separate issues:
- (i) Within the theory, Thm 3.2 needs m to grow linearly with the number of copies b. Here b = \Theta(n), so the sentence "only logarithmically with the size n of the dataset" is misleading. Moreover, the bound appears to be vacuous at the operating points used: plugging the constants in the experiments, the bound exceeds 1 on every dataset.
- (ii) Outside the theory, if OOD centroids are fit on the query vectors (option (a) in M5, as Appendix C suggests), the method needs m \geq t = \sqrt(n) just to define the partition. In practice it needs far more, in the order of ~100\sqrt(n) learning queries are needed before any placement is learned, and the requirement grows with t (see S3). Table 5 also hides this cost: I assume the centroids need to be trained on the full learning set even in the 10–50% conditions. Query-aware placement with base-trained centroids would avoid the issue entirely, which makes the ablation above doubly important.
M3. Build cost excludes the dominant term: ground truth for the learning set
Every build time in the paper excludes computing exact 100-NN for the learning queries. That cost is m x n x d and dominates everything else. For the ID and OOD datasets, m = O(n), so the cost is quadratic in n. Saying this cost is "amortized" does not settle it, especially when the paper argues that periodic rebuilds handle distribution shift. Requests:
- (a) Report ground-truth computation time alongside build time.
- (b) Add an ablation where the learning-set "ground truth" comes from an approximate index (e.g., the natural candidate is the vanilla IVF, which is built anyway, at high \ell). This is how a deployment would actually do it. It should not only report the end-to-end effect on recall. For each ground-truth source and accuracy level (e.g., ground-truth recall 0.9 / 0.95 / 0.99), it should report:
- the cost of producing that ground truth (wall-clock time, plus probe counts or candidates scanned for the approximate index);
- the resulting query-aware index's search cost at the target recall (QPS, \ell and candidates);
- its footprint.
Only then can the trade-off be judged: cheaper ground truth vs. a possibly worse placement.
M4. The effect on list sizes and tail latency is not reported
IVF deployments usually aim for balanced lists so that per-query latency is tightly controlled. The paper reports only aggregate replication (entries per vector, and "the most replicated vector appears in a median 35 lists"). It gives no list-size distribution after replication. The cost function suggests a specific imbalance: the greedy assignment favors adding copies to rarely probed lists, which grow, while frequently probed lists stay small. This minimizes average candidates, but queries that do probe the inflated lists, which are likely the rare and OOD-like ones, pay much more. The objective is an expectation and does not control the tail. Please report:
- (i) list-size statistics before and after replication (max/mean, Gini or coefficient of variation, histograms);
- (ii) per-query distributions of candidates and latency (p50/p95/p99), not only means;
- (iii) whether tail latency gets worse relative to vanilla IVF at matched recall.
If imbalance turns out to be a problem, a per-list capacity constraint (or a convex penalty on |L_j|) would fit naturally into the formulation.
M5. The learning setup is underspecified
Several distinct algorithms are consistent with the text.
-
"Fit on the learning set" (Sec. 4.1) is never defined. Section 4.1 defines the OOD learning set as "queries along with their 100 nearest neighbors". So "fitting on the learning set" could mean any of three things:
- (a) k-means on the query vectors, which puts the centroids in query space; with a modality gap, base vectors are then assigned to centroids in a different region of the space;
- (b) k-means on the base vectors that are the queries' ground-truth neighbors (with or without multiplicity), which keeps the centroids in base space, weighted by query demand;
- (c) k-means on the union of both.
These are different algorithms. Appendix C ("clusters the learning queries") and Table 6 ("queries") suggest (a), but do not rule out (b). Please state which one is used in the main text, together with how inner-product queries are handled (are they normalized?), how many points are clustered, the number of iterations, initialization and seeds.
-
It is unclear whether the 20% learning subset, which stays in the base set, takes part in k-means.
-
It is unclear whether baselines choose their centroid type per dataset using the test queries.
-
Centroids are trained on the full learning set even in the 10–50% conditions, so those conditions do not reflect learning from a smaller sample.
M6. Novelty and related work
The footnote claims this is "the first work to learn dataset placement using the query distribution". That claim is too strong:
- LIRA (Zeng et al., WWW 2025, arXiv:2503.23409) is described as a "learning-based query-aware partition framework". It uses a learned probing model to find long-tail points and replicate them into additional partitions. That is learned, query-aware redundant placement for IVF-style indices. It needs to be discussed and ideally compared against.
- Quake (Mohoney et al., OSDI 2025) adapts partitioned indices using a cost model built from partition sizes × access frequencies. This is essentially the π_j · |L_j| cost of Eq. 3, but used for split/merge rather than replication.
- Spill trees (Liu et al., 2004) and workload-aware replication in databases are also natural antecedents.
The set-cover formulation and LP certification may still be new, but the positioning should be revised. I am not suggesting that the provided references "spoil" this paper, just that query-aware IVF has a history.
Secondary weaknesses
These matter for the paper's broader claims but are not decisive for my assessment.
S1. Gains depend heavily on the size of the learning set, and those sizes are large
The learning sets are large relative to n: 20% of the base for ID; for OOD, 96k–1.33M queries, often ≈ n. Table 5 shows the gains shrink a lot with less data. This raises the following questions:
- What happens at learning-set sizes a practitioner would plausibly label exactly (e.g., 1k–10k queries)?
- Because the gains grow with learning-set size, did the authors check how close test queries are to learning queries (e.g., the fraction of test queries with a near-duplicate in the learning set, or overlap between their ground-truth neighbors)? This would help separate learning the query distribution from memorizing nearby queries.
S2. Near-optimality is certified for a different problem than the one used
The LP certifies coverage at a fixed budget (Problem 6). But the method solves and is used as minimum cost at a fixed recall (Problem 7). The abstract-level claim "always within 1.3% of optimal" should say which problem it refers to. Ideally, add an LP lower bound on cost for Problem (7).
S3. Scope of the evaluation is narrower than the motivation
- Only t = sqrt(n) is used. This is the classical setting, but it is not typical of current deployments. Disk-resident and large-scale IVF systems (e.g., SPANN-style) use many small lists (t \gg sqrt(n)) to bound per-list IO, and FAISS guidelines suggest a larger t in RAM. A study over t is needed, because t affects the method in competing ways. With more, smaller lists, more query–neighbor pairs get closer to the Voronoi boundaries, so replication may help more. But each list is probed by fewer learning queries, so the frequencies become noisier: Thm 3.1's own condition worsens linearly in t. The learning-set size needed may therefore grow with t. Whether the gains persist, grow or vanish at different t values is a central question for the disk use case the paper motivates.
- The demand pairs are built from the K = 100 ground-truth neighbors, and evaluation uses recall@100, so the two are always matched. In practice the index is built once and serves different K: K = 10 for direct retrieval, K \gg 100 as a candidate generator before re-ranking (which the abstract presents as a key use of IVF). Two directions should be tested. (i) Train with K = 100, evaluate at K = 1 and 10. Covering the 100th neighbor may waste copies on pairs that matter little for recall@10. (ii) Train with K = 10, evaluate at K = 100 or more. Neighbors outside the training K get no copies, so recall could fall below that of a well-tuned vanilla IVF.
- The motivation rests on disk-resident, GPU and "very large dataset" settings. All experiments are in-RAM, single-threaded CPU, at ~0.2–21M scale. A billion-scale or at least 10–100M OOD benchmark (e.g., Text2Image from Big-ANN) would strengthen the claim, and would also stress the mn ground-truth cost and the O(|C| + \ell|D|) build memory. Please report peak build memory; |D| reaches 161M pairs.
- Results are only at recall@100 = 0.9. What happens at recall 0.95 or 0.99?
- Shift is given as the main risk and handled by "rebuild periodically", but it is never tested. Examples: train on an ID proxy (base vectors) and test on OOD queries; train on one query modality and test on another; temporal splits.
S4. The role of the primary assignment F deserves an explicit discussion.
It is presented as a convenience ("we retain the primary placement F"), but it carries a key assumption. The set-cover formulation only creates entries for vectors that appear in the ground truth of some training query. A vector that is never among any learning query's K nearest neighbors has no demand pairs and would get no list at all. F is what guarantees that every vector stays reachable. This should be properly discussed and acknowledged.
Thank you for the thoughtful review!
Memory efficiency of our method. We acknowledge that our approach of replication weakens the memory footprint advantage of IVF over, say, graph-based methods. As the reviewer points out, we believe that evaluating our algorithm would shine in a hybrid system where the index is stored on disk and only the probed clusters are loaded into RAM, but we did not test our algorithm in this setting. In a follow-up experiment, we did demonstrate that our algorithm yields substantial gains over the baselines even under a capped memory footprint (see the response to Q1-2 of Reviewer 1). Lastly, we would like to point out that IVF has several advantages beyond memory-efficiency, such as better compatibility with search-time filters and GPU-acceleration.