acceptodds
Under review as a conference paper at ICLR 2027

Learn Where to Store: Query-Aware IVF

Abstract

Approximate nearest neighbor (ANN) vector search is an essential primitive in modern AI and ML applications, e.g., to support retrieval augmented generation. For very large datasets, one of the most popular ANN methods is the inverted-file (IVF) index, which performs locality-friendly contiguous scans, can run on GPUs and on disk, and can serve as the first filtering step in ANN search pipelines. IVF clusters vectors by -means and stores each vector in the list of its nearest centroid. Achieving high recall typically requires scanning more clusters; an alternative is to place copies of a vector in several lists. We present query-aware IVF, which learns where to store copies from a sample of the query distribution, formulating the allocation as a maximum coverage problem that we solve greedily. On the 24 datasets of the Vector Index Benchmark for Embeddings (VIBE), at recall@100 = 0.9, our query-aware index is faster than the IVF baselines on all 24 datasets: a median 1.63 faster than the best query-agnostic replication and up to 21.9 faster, and a median 1.79 faster than vanilla IVF on the 21 datasets where vanilla IVF reaches that recall, at a median 2.58 the memory of vanilla IVF.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Nearest Neighbor Search, Query-Aware Indexing

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_eehfOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a query aware IVF that learns how to apply spillage (i.e., document duplication across cells) using a set of training queries and an approximation of the maximum coverage problem. The idea is to optimally place copies of vectors in significant cells in order to scan less cells at search time while achieving the same effectiveness.

Critical strengths
  • The formulation of the problem is neat and elegant.
  • The authors clearly frame the problem and compare against graph-based baselines.
  • The experimental evaluation is extensive.
Critical weaknesses
  • The speedup comes at high cost in terms of memory usage and building time. With very large collections (and on a machine less powerful than the one the authors employs) efficiency comes from fitting the index into memory.
  • The authors claim that IVF has some advantages wrt to HNSW, which I partially agree with, but I don't think that the evaluation protocols adopted (full in memory index) actually works as an example for those case. I understand that improving IVF has its merit per se, but I would have liked to see IVF applied to case where it actually shines.
Questions for authors

I think that the proposed method requires too much memory wrt to the advantages it gives in terms of efficiency-effectiveness tradeoff, especially for in domain queries. Doubling the memory of IVF also weakens some of the (correct) the motivations reported in the intro, like the fact that IVF can be memory efficient. Can your method use less memory while still providing significant advantages wrt to the IVF baselines?

Is it possibile to evaluate your method in a hybrid disk-memory settings, where maybe the benefits of using IVF would be more evident?

The first question has been addressed in the rebuttal, which made me change my decision to weak accept.

4 comments

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.

thanks for the comment. The answer provided to "Q1-Q2" is an important message that answers my main concern (and concerns from other reviewers). I understand that with the strict time given for the rebuttal it is hard to provide a hybrid disk-memory evaluation, even I am convinced that in this way the message of the paper would have been stronger. It is true that IVF has advantages on GPU. For filtered data, HNSW is still competitive. We could dicuss a lot about what it is better to use, but I guess that this strongly depends on the use case. As I said in my original review, improving IVF is still a merit per se. Any chance you could provide more results similar to the ones provided for "Q1-Q2" but at different recall cut, or for more datasets?

We appreciate the reply! We agree that various tradeoffs should be considered when deciding between partition-based and graph-based indices. We would like to highlight that our query-aware placement strategy isn't necessarily limited to optimizing IVF -- it can be used to optimize most partition-based indices, such as ScaNN. In fact, we have some preliminary results that ScaNN with query-aware point placement can be competitive with graph-based methods (though we would need to flesh these results out before sharing them).

More results of the previous form. Yes, we are happy to include more results of this form. Here are the same results on more datasets. Each cell contains the QPS ratio of query-aware over the fastest other placement allowed under the cap (IVF, top-r, SOAR, SPANN, ε-closure; either centroid source), at recall@100 = 0.9. In the parentheses are the measured index sizes of the best query-aware configuration and best baseline configuration, written as a multiple of the index size of plain IVF.

dataset≤ 1.25×≤ 1.5×≤ 2×≤ 3×
llama17.65× (1.25 / 1.00)11.04× (1.25 / 1.43)11.04× (1.25 / 1.43)11.04× (1.25 / 1.43)
yi1.66× (1.25 / 1.00)2.93× (1.50 / 1.00)4.37× (2.00 / 2.00)4.49× (3.00 / 2.00)
yandex1.66× (1.25 / 1.03)1.66× (1.25 / 1.03)2.18× (2.00 / 2.00)2.49× (3.00 / 3.00)
coco1.01× (1.25 / 1.20)1.01× (1.25 / 1.20)1.64× (2.00 / 1.20)3.82× (3.00 / 1.20)
laion0.97× (1.25 / 1.01)1.50× (1.50 / 1.01)1.50× (1.50 / 1.01)1.96× (3.00 / 1.01)
imagenet-clip1.56× (1.25 / 1.00)1.56× (1.25 / 1.00)1.48× (1.25 / 1.69)1.48× (1.25 / 1.69)
landmark-nomic1.60× (1.25 / 1.00)1.60× (1.25 / 1.00)1.35× (1.25 / 1.56)1.35× (1.25 / 1.56)
landmark-dino*1.56× (1.25 / 1.00)1.56× (1.25 / 1.00)1.54× (1.25 / 2.00)1.54× (1.25 / 2.00)
celeba*0.97× (1.25 / 1.05)1.49× (1.50 / 1.05)1.39× (1.50 / 2.00)1.49× (3.00 / 2.00)
yahoo*1.69× (1.25 / 1.00)1.40× (1.25 / 1.46)1.13× (2.00 / 2.00)1.13× (2.00 / 2.00)
ccnews*0.92× (1.25 / 1.00)1.47× (1.50 / 1.00)1.47× (1.50 / 1.00)1.27× (1.50 / 3.00)
glove*1.40× (1.25 / 1.00)2.45× (1.50 / 1.00)2.45× (1.50 / 1.00)2.45× (1.50 / 1.00)

One conclusion from these results is that extra copies often fail to improve non-query-aware strategies. We will make sure to include these types of capped results in the final revision. To address your other point, here are results at four recall@100 thresholds: 0.80, 0.90, 0.95, 0.99. Each cell contains "speedup at 2x memory cap / speedup at no memory cap".

dataset0.800.900.950.99
llama6.62 / 6.6211.04 / 11.0416.85 / 16.8511.39 / 11.39
yi3.27 / 3.804.37 / 4.494.60 / 6.142.81 / 4.08
yandex2.01 / 2.012.18 / 2.492.21 / 2.441.67 / 2.12
coco3.53 / 9.511.64 / 6.731.09 / 4.950.74 / 3.06
laion1.85 / 13.781.50 / 5.791.86 / 3.931.40 / 1.40
imagenet-clip1.36 / 1.171.48 / 1.481.54 / 1.361.04 / 1.18
landmark-nomic1.49 / 1.461.35 / 1.351.73 / 1.721.39 / 1.39
landmark-dino*1.53 / 1.531.54 / 1.541.41 / 1.341.07 / 1.07
celeba*1.34 / 1.411.39 / 1.491.70 / 1.701.48 / 1.48
yahoo*1.34 / 1.341.13 / 1.131.13 / 1.131.23 / 1.23
ccnews*1.96 / 1.641.47 / 1.271.50 / 1.501.57 / 1.57
glove*2.48 / 2.442.45 / 2.451.58 / 1.581.06 / 1.06
median1.91 / 1.831.52 / 2.001.64 / 1.711.40 / 1.44

Under a 2× cap, query-aware is faster on all 12 datasets at 0.8, 0.9 and 0.95. The 0.99 threshold is more difficult for a few datasets likely due to generalization error.

Thanks for the detailed comment. The matched-memory evaluation is convincing and I changed my evaluation to weak accept.

Reviewer_GyhMOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a query aware IVF index that learns where to store extra copies of vectors. It formulates this task as a partial set cover problem and uses a greedy algorithm to choose the copies. The authors analyze recall and search cost and compare the greedy solutions with a linear programming bound. Experiments on 24 VIBE datasets report a median speedup of 1.63 times over the best query agnostic replication baseline at Recall@100 of 0.9.

Critical strengths

(1) The method chooses copies based on the queries that need them. Its objective accounts for both the neighbors that can be found and the vectors that must be scanned. This gives a clear reason for each additional copy and directly connects the proposed method to search accuracy and cost.

(2) The experiments cover 24 datasets, and the speed improvements are supported by fewer scanned candidates. This helps show that the gains come from the placement of copies. The comparison with a linear programming bound also gives useful evidence that the greedy algorithm makes good choices on the tested datasets.

Critical weaknesses

(1) The theory does not directly apply to an important part of the experiments. Theorems 3.1 and 3.2 require centroids to be computed without using the learning queries. The OOD experiments use those queries to compute the centroids, so the stated guarantees do not directly cover these indexes. The recall bound also becomes larger when more copies are stored. The paper does not report whether it gives useful values for the tested indexes.

(2) The faster search comes with costs that are not fully compared. The method uses 2.58 times the storage of vanilla IVF in the median case. Reported build times also leave out the cost of finding exact neighbors for the learning queries. The authors discuss these costs and add RaBitQ compression, but do not compare the methods with the same memory limit and complete build cost. Without this comparison, the overall benefit is difficult to judge.

Questions for authors

(1) The paper proposes collecting new queries and rebuilding the index. How often is rebuilding needed when later queries differ from the learning queries? Please report the loss in speed and recall before rebuilding, together with the full rebuilding cost. The current OOD experiments do not test this change in queries.

(2) What guarantees hold for indexes whose centroids are computed from the learning queries? Please also give numerical values of the recall bound for representative indexes. Does it give an upper bound below one on the fraction of missed neighbors? A larger value would not give useful information about recall.

(3) At Recall@100 of 0.9, how much faster is the proposed method when all methods use the same memory limit? Please include the RaBitQ versions and add exact neighbor computation to the build times. These results would show whether the faster queries justify the extra memory and preparation time.

3 comments

Thank you for the thoughtful and detailed review!

Distribution shift in queries. We appreciate your question, and it gets at a practical consideration we didn’t mention in our paper: shift in the query distribution. While the datasets we tested don’t have distribution shift, measuring our robustness to it (and the tradeoff with rebuilding cost) would be a good next step for future work.

Guarantees for indexes whose centroids depend on learning queries. We don’t have theoretical guarantees if centroids depend on learning queries. However, we don’t anticipate that this is a big problem in practice, given that we would expect k-means not to be very sensitive to the sample drawn from the query distribution. We had limited data such that clustering the queries we were given made sense (as opposed to splitting the training queries), and in general, choosing the partition was not a focus of this work.

Numerical recall bound. We would not expect our theoretical recall bound to give a non-vacuous guarantee given the scale of training data in our experiments. We include this bound primarily for theoretical completeness and to demonstrate the convergence of the error, not to claim that the data supplied by the benchmarks was enough for a strong guarantee.

Performance under capped memory. In a follow-up experiment, we compared our method with the baselines under a capped memory footprint — see the table in our response to Reviewer QFKT. We did not compare the RaBitQ versions.

Thank you for your response. I have three follows-up questions about your response to my Q3. (1) Can you show the actual memory cost for every method, since ≤ X only shows the upper bound? (2) How about the results on the remaining datasets? (3) Regarding my question, "Please add exact neighbor computation to the build times," do you have any results?

Thank you for the reply! We are attaching responses to the follow-up questions here.

Memory cost and more datasets. We are attaching the memory cost information here, as well as results on some of the in-distribution datasets. As before, each cell contains the QPS ratio of query-aware over the fastest other placement allowed under the cap (IVF, top-r, SOAR, SPANN, ε-closure; either centroid source), at recall@100 = 0.9. In the parentheses are the measured index sizes of the best query-aware configuration and best baseline configuration, written as a multiple of the index size of plain IVF.

dataset≤ 1.25×≤ 1.5×≤ 2×≤ 3×
llama17.65× (1.25 / 1.00)11.04× (1.25 / 1.43)11.04× (1.25 / 1.43)11.04× (1.25 / 1.43)
yi1.66× (1.25 / 1.00)2.93× (1.50 / 1.00)4.37× (2.00 / 2.00)4.49× (3.00 / 2.00)
yandex1.66× (1.25 / 1.03)1.66× (1.25 / 1.03)2.18× (2.00 / 2.00)2.49× (3.00 / 3.00)
coco1.01× (1.25 / 1.20)1.01× (1.25 / 1.20)1.64× (2.00 / 1.20)3.82× (3.00 / 1.20)
laion0.97× (1.25 / 1.01)1.50× (1.50 / 1.01)1.50× (1.50 / 1.01)1.96× (3.00 / 1.01)
imagenet-clip1.56× (1.25 / 1.00)1.56× (1.25 / 1.00)1.48× (1.25 / 1.69)1.48× (1.25 / 1.69)
landmark-nomic1.60× (1.25 / 1.00)1.60× (1.25 / 1.00)1.35× (1.25 / 1.56)1.35× (1.25 / 1.56)
landmark-dino*1.56× (1.25 / 1.00)1.56× (1.25 / 1.00)1.54× (1.25 / 2.00)1.54× (1.25 / 2.00)
celeba*0.97× (1.25 / 1.05)1.49× (1.50 / 1.05)1.39× (1.50 / 2.00)1.49× (3.00 / 2.00)
yahoo*1.69× (1.25 / 1.00)1.40× (1.25 / 1.46)1.13× (2.00 / 2.00)1.13× (2.00 / 2.00)
ccnews*0.92× (1.25 / 1.00)1.47× (1.50 / 1.00)1.47× (1.50 / 1.00)1.27× (1.50 / 3.00)
glove*1.40× (1.25 / 1.00)2.45× (1.50 / 1.00)2.45× (1.50 / 1.00)2.45× (1.50 / 1.00)

One conclusion from these results is that extra copies often fail to improve non-query-aware strategies. We will make sure to include these types of capped results in the final revision.

Cost of computing ground-truth. The OOD VIBE datasets were prelabeled with the top-100 neighbor labels of every query, so we didn’t measure the time for generating these labels. We agree that in practice, computing the ground-truth can be costly, but that can be done offline and should be considered part of the preprocessing time (the cost can be amortized over many queries).

Reviewer_QFKTOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper argues that redundant assignment in IVF indices, i.e., storing a vector in more than one list, should be decided by the query workload rather than by the geometry of the data alone. It frames choosing where to store copies as a data-driven combinatorial optimization that trades index footprint (memory or disk) for fewer scanned candidates at a target recall.

Concretely, the paper fixes the k-means centroids and the probe count \ell of an IVF index. It keeps every vector's primary assignment and then adds extra copies (p, j). These copies are chosen from a sample of queries with exact ground truth, so that the query–neighbor pairs vanilla IVF misses (the "demand pairs") get covered. The cost of a copy in list j is the probe frequency, so the cost of the index equals the expected number of scanned candidates. The problem becomes partial set cover or budgeted maximum coverage, which is solved with a cost-benefit greedy that produces the whole recall–cost trade-off in one run. The paper also:

  • uses an LP relaxation to certify that the greedy is near-optimal on the instances it solve;
  • gives two generalization bounds, one for cost (Thm 3.1) and one for recall (Thm 3.2);
  • evaluates on the 24 VIBE datasets. At recall@100 = 0.9, query-aware IVF is faster than vanilla IVF and top-r replication on all 24 (median 1.63x, up to 21.9x), with gains concentrated on OOD datasets. Its index footprint is a median 2.58x that of vanilla IVF, and up to 21.4×.

An appendix compares against HNSW, DiskANN, RoarGraph, ScaNN, SOAR and a RaBitQ-quantized variant.

Critical strengths
  1. The formulation is clean and natural. The linearization in Eq. 3 is neat. The reduction to partial set cover is exact under the stated cost model, and the nested-prefix property that gives the whole frontier in one run is useful in practice.
  2. The LP certification is carefully done. The Lagrangian decomposition per vector, the two-sided bounds and the cross-check against a full HiGHS solve are convincing (this level of detail is rarely seen in ANN papers). It convinced me that the greedy assignment is not the bottleneck.
  3. The paper uses all 24 VIBE datasets, both ID and OOD, and reports candidate counts next to wall-clock time, which separates algorithmic gains from engineering gains.
  4. In Appendix D, the paper openly shows that graph indices and SOAR are usually faster. It also discusses timing artifacts, such as concurrent measurement inflating IVF by 4x. I appreciated the candor.
  5. Cross-modal retrieval is a real pain point for partition-based indices and the gains in that regime are large and relevant.
Critical weaknesses

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.

Questions for authors
  1. How does query-aware placement compare with SOAR, RAIRS (AIR assignment, with and without the SEIL layout) and SPANN-style closure assignment implemented in the same flat-IVF engine with the same centroids, at matched footprint? (M1)
  2. What are QPS and candidates at recall 0.9 under footprint caps of 1.5x, 2x and 3x vanilla IVF? (M1)
  3. What search-time \ell does each method need for recall@100 = 0.9? How does recall vs. \ell change along the greedy prefix A(s)? (M1)
  4. On the OOD datasets, what are the results of the 2x2 ablation {base-trained, query-trained centroids} x {vanilla, query-aware placement}? Which centroid option does vanilla IVF pick per dataset in Table 1? (M2)
  5. What is the training vs. test recall gap for the chosen indices at \ell_train? (M2)
  6. How do results change when the learning-set ground truth is approximate (e.g., from HNSW or high-\ell IVF)? What is the wall-clock time of the exact ground truth you used? (M3)
  7. What do the list sizes look like after replication (max/mean, coefficient of variation), and what are the p95/p99 per-query latency and candidates compared with vanilla IVF? (M4)
  8. Which data are the OOD centroids fit on: the query vectors, their ground-truth neighbors, or both? (M5)
  9. How does the method relate to LIRA, and how does it compare empirically? (M6)

Related to the secondary weaknesses:

  1. Did you measure how close test queries are to learning queries (near-duplicates, overlap of ground-truth neighbors)? (S1)
  2. How sensitive are the gains to t and to mismatches between training and evaluation K? (S3)
  3. Can the cost model be the I/O pages read for disk-resident lists (footnote 4), and do the gains survive in a disk setting? (S3)
  4. Please discuss why the primary assignment is a key step, instead of side-stepping the topic.
3 comments

Thanks for all the detailed feedback! We address each question individually.

Q1-Q2. Stronger baselines and replication caps. We evaluated our method against vanilla IVF, top-r replication, SOAR, and two SPANN placement variants. We imposed several replication caps and measured QPS at recall@100 = 0.9. Each entry is the QPS of query-aware IVF divided by that of the fastest baseline under the cap:

dataset≤ 1.25×≤ 1.5×≤ 2×≤ 3×
llama17.6×11.0×11.0×11.0×
yi1.66×2.93×4.37×4.49×
yandex1.66×1.66×2.18×2.49×
coco1.01×1.01×1.64×3.82×
laion0.97×1.50×1.50×1.96×
imagenet-clip1.56×1.56×1.48×1.48×
landmark-nomic1.60×1.60×1.35×1.35×

At the 2× cap, query-aware IVF improves QPS on all datasets, with speedups of 1.35–11.0× and a median of 1.64×. At the 3× cap, the median speedup is 2.49×. These results show that the gains on these datasets do not require the largest replication factors from our original evaluation.

Q3. Search-time probe counts. Across all datasets, the median ratio of the search-time probe count required by vanilla IVF to that required by query-aware IVF is approximately 4, at recall@100 = 0.9. In the final version, we will attach recall-versus-ℓ)\ell) curves for greedy prefixes spanning 1.25–4 entries per vector.

Q4. Query-trained centroids. Choosing the centroids and partition was not an emphasis of our work. We included results on query-trained centroids because they helped our query-aware method. To isolate the gains from point placement, we ran baseline methods with both choices of centroids and reported the best one. The best choice for vanilla IVF’s centroids was the corpus on 8 of 9 OOD datasets.

Q5. Training versus test recall. For our query-aware method, test recall@100 is lower than training recall by a median of 7.7 percentage points on ID datasets and 6.3 percentage points on OOD datasets; we will make sure to include these numbers in the final version of the paper.

Q6. Wall-clock time of exact ground-truth. The OOD VIBE datasets were prelabeled with the top-100 neighbor labels of every query, so we didn’t measure the time for generating these labels. We agree that in practice, computing the ground-truth can be costly, but that can be done offline and should be considered part of the preprocessing time (the cost can be amortized over many queries).

Q7. List size statistics. Across the datasets, the ratio of max to average list size ranges from 2.1–3.1 for vanilla IVF and 2.4–5.3 for query-aware IVF. This suggests that replication tends to increase list imbalance. Nevertheless, the ratio of query-aware IVF’s p99 latency to vanilla IVF’s p99 latency ranges from 0.09–0.64, meaning that tail latency improves despite the increased imbalance.

Q8. Which data are OOD centroids fit on. We fit the OOD centroids on the learning query vectors themselves, not on their ground-truth neighbors.

Q9. Comparison with LIRA. LIRA takes a different approach to query-aware IVF, namely, learning a rule for which clusters to probe for each query. In contrast, we consider a fixed probing strategy and optimize the point placement accordingly. We see this as an orthogonal approach to query-aware IVF and will make sure to cite it appropriately in the final version.

Q10. Similarity between training and test queries. For each test query, we measured the fraction of overlap between its top-100 neighbors and those of the closest learning query. Across OOD datasets, the median overlap ranges from 0.15-0.53, while the p95 overlap ranges from 0.51-0.96; on ID datasets these ranges are 0.12-0.49 and 0.53-0.92, respectively. This suggests that most queries don’t overlap too closely with any learning query and “memorizing” the training set is not enough for good performance.

Q11. Sensitivity to different tt and KK. In our paper, we used a basic rule-of-thumb t=nt = \sqrt{n}. We do not claim this setting is optimal; we tried to fix as many parameters as possible to isolate the effect of query-aware point placement. For the same reason, we did not evaluate our methods for K≠100K\ne 100. Changing KK from training to search time would change the distribution of demand pairs and move outside of our theoretical framework.

Q12. Adapting cost model to I/O pages. We appreciate this suggestion. We think hardware-aware cost models could be an interesting direction for future work, and we will mention this in the final version of the paper.

Q13. Reason for the primary assignment. We included primary assignments for a robustness guarantee: the recall of our method is never worse than vanilla IVF. The alternative of “cold starting” our method has several potential issues: without sufficiently many training queries, many points might simply not appear in any learning pair, in which case we would not index them. We will make this clear in the final version of the paper.

Thank you for response. I feel that a few points remain unanswered:

  • From M2, "The sample requirement is much larger than "logarithmic in n" suggests." Your Q1-Q2 answer does not cover this point. This is not a minor point, because the theory suggests that only a small portion of queries needs to be labeled. However, how fitting the theory is remains to be proven. Additionally, the empirical results seem to be using learning sets that way larger than logarithmic in n.
  • I do not think that claiming that "ground truth can be computed offline" is fair. The datasets include ground truth for learning as a convenience, but ANN is an unsupervised problem. If the authors need ground truth, either they need to account for it. Most if the baselines do not use this ground truth, they do the assignment purely using the index vectors. Using query-neighbor pairs, the main idea of the paper, is interesting but it does come with an index construction tradeoff that cannot be dismissed.

Thank you for getting back to us! Yes, we'll address these two points directly.

Sample complexity. The line in our paper where we say the sample complexity grows only "logarithmically with the size nn of the dataset" is misleading and inaccurate, since indeed b≥nb \ge n. We appreciate the reviewer for pointing this out, and we will make sure to remove this phrase in the next revision. The point of including a generalization bound was simply to characterize how many learning queries one would need, not to claim that a small amount of data (e.g., the amount of data in the evaluated benchmark datasets) is sufficient.

Ground truth computation. We acknowledge that ANN is an unsupervised problem, but we would like to state our perspective on how a query-aware ANN system might be deployed in practice and why ground-truth computation time may not be a major concern. We envision a system that periodically samples incoming queries, computes their ground truth offline (e.g., 1 per 100 queries). These queries and their ground-truth neighbors could then be used to periodically update the data structure (e.g., every few days). This approach addresses both (i) the practical challenge of ground-truth computation and (ii) potential shifts in the query distribution over time. We agree that ground truth computation is an additional system consideration which we use to obtain the observed query-time speedups.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.