- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper looks at the partition routing problem in clustering-based vector search (IVF-style indexes). Instead of just routing queries by distance to cluster centroids, the authors propose Query Expansion Routing (QER). At build time, each vector remembers which partitions its nearest neighbors live in. At query time, after checking the first centroid-based partition, they take intermediate good candidates, see where their neighbors live, and probe those clusters next. They integrated QER into ScaNN and LoRANN, reporting good QPS and recall boosts on datasets from ANN-Benchmarks and VIBE, especially in high-recall zones.
Critical strengths
- The experiments are extensive and well-run: Testing on 19 VIBE datasets and ANN-Benchmarks is solid work. The authors didn’t just test one easy scenario; they tested a wide range of real data.
- The hardware and setup are very clean: Isolating scoring errors with exact distance computations on GPU to check routing alone is smart and convincing.
- Solid empirical gains: Cutting down scanned vectors by over 40% at ultra-high recall (0.999) is a real, measurable improvement. The code is also promised to be open-source.
Critical weaknesses
- Limited algorithmic novelty: Let’s be completely frank here. The core conceptual leap is quite thin to me. Pre-storing neighbor partition links to guide query-time expansion is essentially a hybrid between an inverted file and a coarse neighbor graph. In both DB and AI communities, this sort of dynamic candidate expansion and two-hop partition hop has been explored in various flavors for years. For an ICLR paper, this feels more like a good engineering trick or an incremental heuristic than a fundamentally novel research contribution.
- Narrow baseline scope: The practical evaluation is built almost entirely on top of ScaNN and LoRANN. While both are great systems, they do not represent the entire clustering-based or hybrid vector search landscape. Without showing how this behaves on standard Faiss IVF-PQ/IVF-FastScan baselines, or directly comparing performance trade-offs against established graph-IVF hybrids, it is hard to assess how general this strategy really is. 3.Overhead and hyperparameter sensitivity: QER introduces extra parameters (, , patience, ) and an iterative feedback loop. While memory overhead is small on high-dimensional data, the latency overhead hurts in low-to-medium recall ranges. If a method only shines at the extreme tail of recall (e.g., >0.98), its general utility in production vector databases is somewhat constrained.
Questions for authors
-
Are you truly the first to propose this? The core idea looks strikingly similar to classical materialized view maintenance in databases and work like the VLDB classic "Meet Me Halfway: Split Maintenance of Continuous Views", where precomputed intermediate links and partial results dynamically bypass full re-evaluations. Similar multi-stage candidate-driven graph/cluster hops have also been floating around the database and AI retrieval literature. Are there specific prior DB or AKNN approaches you considered, and why does QER represent an unprecedented conceptual breakthrough rather than a known cross-domain technique applied to modern SIMD kernels?
-
Why only ScaNN and LoRANN? Are these two really enough? Why pick just these two? How do you justify ignoring other major AKNN frameworks and standard IVF variants (like Faiss IVF-Flat / IVF-PQ / FastScan)? Furthermore, how does QER compare against graph-IVF hybrid methods or other partition-pruning works mentioned in your own related work (e.g., LIRA, Quake, or SPANN)? If QER cannot be readily adapted or does not beat those on identical hardware, the claim of general applicability remains incomplete.
-
(Minor questions) Could you please make your figures better to read? To me , the fonts are tooo small, and the overall picture is too large (e.g., Figure 2)
2 comments
Thanks for the clarification. I can slightly raise the score.
We appreciate the thorough evaluation and the recognition of the extensive nature of our assessment and the value of the exact-scoring experiments.
a) Relationship to materialized view maintenance. Winter et al. split continuous-view maintenance between incoming data and view queries: insertions update intermediate state, and queries complete the deferred computation to produce the current view result. QER uses retrieved candidates and their precomputed neighbourhood information to select additional partitions within an ANN query, without modifying the index. The distinction therefore concerns the algorithmic operation: maintaining a view as inputs arrive versus selecting which partitions to search. Both reuse previously available information, but this shared principle does not establish an equivalent routing mechanism. Specific references to the candidate-driven graph/cluster approaches mentioned in the review would help us examine any closer correspondence.
(b) Computational constraints are part of the research problem. In high-performance IVF search, improving search selectivity is only part of the design problem. An effective method must also operate efficiently under constraints imposed by memory access, data layout, and SIMD execution. André et al.’s PQ Fast Scan demonstrates substantial speedups through changes to computation and data access while returning the same PQ search results. The ScaNN paper explicitly distinguishes reducing the number of evaluated vectors from increasing their evaluation rate. Google’s ScaNN for AlloyDB report likewise explains how contiguous storage and SIMD execution can make evaluating more candidates computationally competitive with graph traversal. These considerations constrain algorithm design: a more selective routing rule is not necessarily a faster one.
(c) QER addresses partition selection within these constraints. QER uses neighbourhood information from retrieved candidates to select additional partitions while preserving the vector layout and scoring kernels of optimized IVF search..
(d) The experiments identify an algorithmic routing effect. CBR uses centroid proximity, whereas QER uses neighbourhood information associated with intermediate candidates. Our exact-scoring experiments provide evidence that these signals are complementary: QER can reduce the number of vectors scanned to attain a given recall even when distances are computed exactly. This identifies an effect on search decisions themselves. The integrations with ScaNN and LoRANN then examine how this routing mechanism operates within optimized search implementations.
(e) Simplicity and novelty are separate questions. In an extensively studied field such as ANN, identifying a simple, effective improvement under these constraints remains a meaningful achievement. For example, SPANN (Chen et al., NeurIPS 2021) explicitly presents its contribution as a “a simple but surprising efficient memory-disk hybrid vector indexing and search system”. Simplicity can be a useful property when a method must fit an efficient execution architecture. QER’s relationship to prior work should therefore be assessed through the specific routing information it stores and the way it uses retrieved candidates to select additional partitions.
(f) Algorithmic insight and computational design are complementary contributions. ScaNN, FastScan, and LoRANN illustrate how ANN research combines mathematical modelling and approximation with hardware-aware software design. Preserving computational efficiency while improving search decisions is an algorithmic design challenge in its own right. QER addresses this challenge by using candidate neighbourhood information to guide partition selection while retaining the underlying vector layout and scoring kernels. Our claim is a specific, experimentally supported routing contribution compatible with optimized ANN execution—not that precomputation or iterative expansion is itself unprecedented.
We selected ScaNN and LoRANN because they employ distinct scoring mechanisms, allowing us to evaluate QER across different architectures. Moreover, Faiss’s documentation confirms that its 4-bit PQ FastScan implementation was heavily inspired by ScaNN.
The revised manuscript includes additional comparisons with LIRA and Quake APS. SPANN focuses on hybrid memory/SSD search, making direct comparison less straightforward. While our results demonstrate QER’s compatibility with different scoring mechanisms, evaluation in Faiss and graph–IVF hybrids remains future work.