acceptodds
Under review as a conference paper at ICLR 2027

Improving Partition Routing in Approximate Nearest Neighbor Search with Query Expansion Routing

Abstract

Approximate Nearest Neighbor (ANN) search methods often rely on space partitioning, where clusters are formed and partition routing is typically based solely on the query distance to cluster centroids. This approach neglects the incremental information gained during the search process. We present a novel query-expansion strategy that dynamically expands the set of scanned partitions using partial results from intermediate search stages. During indexing, we precompute neighborhood relationships between vectors and the partitions containing their nearest neighbors. At query time, initial results are retrieved based on centroid distances. Subsequently, an iterative expansion phase leverages these initial results to extend the partition ranking. This feedback loop can improve the recall–throughput trade-off by reducing unnecessary partition scans while maintaining high accuracy. We refer to this method as Query Expansion Routing (QER). We implemented QER in ScaNN and LoRANN, observing improvements on 14 of the 19 evaluated datasets for ScaNN-QER and 16 of 19 for LoRANN-QER. The gains are most pronounced in the high-recall regime. Across the five datasets with the largest gains for each method, ScaNN-QER and LoRANN-QER achieve geometric-mean QPS speedups of and , respectively, computed for each dataset over the recall range jointly attainable by the baseline and the QER variant, within . We designed experiments to isolate the influence of approximate distance computation in ScaNN and LoRANN from QER. These experiments show that the method achieves the same recall while analyzing fewer partitions and scanning fewer vectors, demonstrating the value of candidate-driven feedback as a complementary signal for partition selection in clustering-based ANN search.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Approximate Nearest Neighbor Search, ScaNN, LoRANN, Query Expansion, Partition Routing, Vector Search, Inverted File Index

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_fkEyOpenReview ↗
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
  1. 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.
  2. The hardware and setup are very clean: Isolating scoring errors with exact distance computations on GPU to check routing alone is smart and convincing.
  3. 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
  1. 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.
  2. 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 (NN, MM, patience, kqek_{qe}) 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
  1. 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?

  2. 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.

  3. (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

We appreciate the thorough evaluation and the recognition of the extensive nature of our assessment and the value of the exact-scoring experiments.

  1. Algorithmic novelty

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.

  1. Choice of ScaNN and LoRANN

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.

  1. We have revised the figures throughout the manuscript to improve readability.

Thanks for the clarification. I can slightly raise the score.

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

The paper proposes Query Expansion Routing (QER) for clustering-based approximate nearest neighbor search. During index construction, each vector stores the IDs of other partitions that contain some of its nearest neighbors. During search, QER first uses centroid-based routing, then uses these stored IDs to decide which additional partitions to scan. The method is implemented in ScaNN and LoRANN and evaluated on 19 VIBE datasets and GloVe. The results show that QER can reduce the number of scanned vectors and improve query speed, especially on some datasets.

Critical strengths
  1. The experimental results are convincing. Table 2 uses exact scoring, at Recall@100 ≥ 0.98, QER scans fewer vectors on 18 of the 19 datasets.

  2. The idea is simple and keeps the existing IVF memory layout. The authors implement it in both ScaNN and LoRANN, and Table 1 reports a relatively small memory overhead.

  3. The evaluation includes many recent datasets, including out-of-distribution data. The paper also reports datasets where QER does not help, such as celeba, coco, llama, and yi. This makes the results easier to assess.

Critical weaknesses
  1. LoRANN-QER includes a new cross-partition pre-filter that the original LoRANN does not have. The paper also suggests that this pre-filter may explain part of the larger LoRANN improvement. Therefore, I cannot tell how much of the reported 1.94× speedup comes from QER itself. An experiment with LoRANN plus the pre-filter, but without QER, is needed.

  2. The experiments compare QER only with the original ScaNN and LoRANN implementations. Other approaches to improving partition routing are discussed but not tested. I would like to see comparisons with SOAR or SPANN-style spilling under the same memory budget, Quake’s adaptive scanning, LIRA’s learned probing, and a tuned adaptive nprobe baseline. The paper should also discuss the related learning-to-rank IVF routing work by Vecchiato et al. (SIGIR 2024). Without these comparisons, it is hard to know whether QER is better than simpler ways of handling vectors near partition boundaries.

  3. The tuning does not seem fully balanced. The baselines use the fixed VIBE parameter grid, while QER has additional parameters that are tuned. In Table 3, base LoRANN does not reach recall of 0.99 on several datasets, although Figure 2 suggests that more centroid probes could reach it. I would like the authors to tune both sides to the same recall target. The reported results also appear to be single runs with --parallelism 4 on an eight-core desktop. Variance and more details about threads and query batching would make the speed comparisons more reliable.

  4. The abstract reports speedups for the five datasets with the largest gains. Across all evaluable datasets, the geometric-mean speedups are closer to about 1.12× for ScaNN and 1.44× for LoRANN. These are still useful improvements, but they give a different picture of the typical gain. The paper also does not report index construction time. Building the M=100 nearest-neighbor graph on a GPU may have a substantial cost, especially for the billion-scale setting used to motivate the work.

Questions for authors

Please see above weaknesses.

3 comments

We thank you for your valuable feedback. It has led us to reassess our experimental setup, expand the evaluation, and refine the presentation of the results.

  1. Contribution of pre-filtering to LoRANN-QER performance

We implemented the pre-filtering mechanism in LoRANN without QER and performed the suggested experiment. The results show an approximately 10% throughput improvement over the original implementation for configurations with Recall@100 ≥ 0.95. The detailed comparison is included in the revised manuscript.

  1. Comparison with alternative routing and spilling methods

We attempted to reproduce the SOAR results using the original ScaNN implementation and the parameter settings reported in the paper. However, we were unable to reproduce the reported results. We contacted the authors in July 2026 to request guidance, but have not yet received a response.

SPANN is designed for hybrid memory/SSD search, with particular attention to the storage and retrieval of posting lists. A comparison with its spilling strategy under a matched memory budget would be informative. For the current revision, we prioritized additional comparisons with LIRA’s probing model, Quake’s APS, and an oracle variant of adaptive CBR. The corresponding experiments and discussion are now included in the revised manuscript. The oracle adaptive-CBR variant serves as an idealized reference for centroid-based routing. We have also added a discussion of the learning-to-rank approach to IVF routing proposed by Vecchiato et al. (SIGIR 2024).

  1. Parameter tuning, measurement protocol, and implementation corrections

Following the suggestion, we expanded the parameter grids so that each baseline and its corresponding QER variant cover the same recall targets. This addresses the limitation of the original grid, under which some baseline configurations did not reach the recall levels attained by their QER counterparts. Please note, we used parallelism 4 on 8-core CPU because of memory limit.

(a) Measurement protocol. Our measurements followed the benchmark protocol: each query configuration was evaluated over five repetitions of the query set, and the best mean query time was retained. Here, --parallelism 4 specifies four concurrent benchmark processes. For a small number of configurations, we observed substantial timing variability during concurrent execution. The benchmark processes complete their work independently, which can change contention for shared hardware resources over the course of the experiment.

(b) Implementation correction. During this analysis, we also identified and fixed a bug that sometimes prevented QER from being activated on high-dimensional data. The issue was confined to ScaNN-QER and affected a subset of the datasets. Preliminary measurements of the corrected implementation show improved performance on six datasets and lower performance on two, relative to the previous implementation. These corrected results are not yet included in the revised manuscript.

To reduce interference between concurrent benchmark runs, we have decided to repeat the full evaluation with --parallelism 1, using the corrected implementation and the expanded parameter grids. We estimate that this evaluation will require up to eight days and intend to include the results in the final version of the paper.

  1. Reporting of speedups and index construction overhead

The revised abstract now explicitly reports the average speedup over the datasets on which the methods improve performance, identifying the subset used for this summary. We have also added measurements of index construction time. Relative to the corresponding baselines, construction takes approximately 16.7% longer for ScaNN-QER and 23.0–23.5% longer for LoRANN-QER, on average across the evaluated datasets. The measurements separately account for computing the (M) nearest neighbours and for the remaining index-construction stages. This breakdown shows the contribution of neighbourhood precomputation to the additional construction cost. The reported overheads apply to the dataset sizes covered by our evaluation.

Thank you for the detailed response and the additional experiments.

On SOAR (W2): My request was not to reproduce the numbers reported in the SOAR paper, but to compare QER with SOAR under the same memory setting. SOAR is open source and is part of the same ScaNN library used in this paper (see https://research.google/blog/soar-new-algorithms-for-even-faster-vector-search-with-scann/, which links to the official ScaNN code). Since ScaNN-QER is built on this library, it should be feasible to enable SOAR and report its recall and throughput under a matched memory budget.

On W3: I appreciate the authors’ honesty in reporting the ScaNN-QER bug and the timing variability under concurrent runs. This kind of transparency is valuable, and I hope the AC will take the authors’ effort into account. As a reviewer, however, I need to base my score on the evidence available at this stage. The corrected implementation and the corresponding results are not yet included in the revised manuscript, so I cannot verify whether the main conclusions still hold. For this reason, I will keep my current score.

We would like to clarify our earlier response regarding SOAR. We agree that reproducing the exact published numbers is not required for a matched-memory comparison. In our experiments with the official ScaNN implementation and the reported parameter settings, SOAR improved performance, but substantially less than reported in the paper. This discrepancy prompted us to seek guidance from the authors in July 2026 and defer further comparisons until we could better understand its cause, with the aim of ensuring a fair assessment of SOAR. We acknowledge that the requested matched-memory comparison is not included in the current revision.

We would also like to clarify that the bug identified in ScaNN-QER affected only a subset of datasets in the QPS–recall trade-off experiments conducted using the VIBE benchmark. All other experiments were unaffected by this bug.

Reviewer_H3p7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a query expansion routing method that builds upon traditional centroid-based routing. The main idea is to leverage intermediate search results to explore and identify additional promising partitions, thereby improving the efficiency and accuracy of approximate nearest neighbor search. The experimental results demonstrate improvements in efficiency and the recall.

Critical strengths
  1. The overall idea is simple and clear, and the proposed method can be easily integrated into existing ANN systems.

  2. The experiments evaluate the method from multiple perspectives, including queries per second (QPS) and recall. The results demonstrate that QER is particularly beneficial in high-recall scenarios.

Critical weaknesses
  1. The main idea is relatively straightforward, as it essentially expands the search space iteratively based on previously retrieved candidates.

  2. The experiments mainly compare QER with traditional CBR, without providing direct comparisons with other relevant or more advanced routing approaches.

  3. The paper introduces several predefined parameters but does not provide sufficient ablation studies or sensitivity analyses to demonstrate how these parameters affect performance.

  4. The index construction process introduces additional computational costs, but these costs are not thoroughly analyzed. Furthermore, the iterative partition expansion during online queries also incurs additional latency, which is not sufficiently quantified or discussed.

  5. The presentation and organization of the paper could be further improved to enhance clarity and readability.

Questions for authors
  1. Could the authors further clarify the key differences between QER and existing query expansion or adaptive partition routing methods? What are the main novel contributions beyond iteratively expanding the search space based on previously retrieved candidates?

  2. Why does the experimental evaluation mainly focus on comparisons with traditional CBR? How does QER compare with other existing adaptive partition routing approaches? Could the authors provide additional comparisons or explain why such comparisons are not included?

  3. How sensitive is QER to the selection of its key parameters, such as M,N ? Could the authors provide ablation studies to demonstrate their individual effects on recall, throughput, and memory consumption?

  4. What is the additional index construction time required by QER compared with the baseline methods? Furthermore, could the authors quantify the computational overhead introduced by iterative partition expansion during online queries, and clarify how this overhead affects the overall performance gains?

4 comments

We appreciate your questions and are glad to provide answers below.

  1. Differences from existing query expansion and adaptive partition routing methods.

The central contribution of QER is a routing mechanism that uses precomputed neighbourhood information associated with candidates retrieved during search. For each indexed vector, QER stores a compact list of partition identifiers derived from its neighbourhood outside its own partition. At query time, the lists associated with retrieved candidates identify additional promising partitions to scan. Routing therefore adapts to the neighbourhood revealed by the evolving candidate set. This mechanism differs from the routing signals used by the methods discussed below. LIRA’s probing model predicts the probability that each partition contains neighbours of the query, using the query vector and its distances to partition centroids as inputs (Zeng et al., 2025). The learning-to-rank approach of Vecchiato et al. (2024) learns a linear mapping from the query to partition-ranking scores. Quake’s APS uses intermediate search results and partition geometry to estimate recall and adapt partition scanning to a target recall (Mohoney et al., 2025).

QER contributes a concrete way to translate the local neighbourhood information of retrieved candidates into partition-selection decisions. Its online expansion operates on stored partition identifiers, requires no separate learned routing model, and preserves the underlying partition-scanning routines, as demonstrated by our integrations with ScaNN and LoRANN.

  1. Comparisons with other routing approaches.

The original evaluation focused on centroid-based routing (CBR) because QER builds upon CBR by using centroid distances for initial partition selection and subsequently expanding the search using neighbourhood information from retrieved candidates. Comparing the two allows us to isolate QER's contribution and demonstrate the complementarity of centroid-based and candidate-driven routing signals, while retaining the underlying partition-search mechanisms.

To extend this evaluation, we have added experiments and discussion comparing QER with LIRA’s probing model and Quake’s APS. These comparisons examine partition-routing effectiveness, while the computational cost of routing is evaluated separately, as discussed in our response to Question 4. The results and accompanying discussion are included in the revised manuscript.

  1. Sensitivity to (M) and (N).

We plan to provide separate ablations of (M) and (N) to assess their individual effects on recall and throughput. The memory overhead is already discussed in the manuscript: the storage required per vector is determined directly by (N) and the padding applied to the array of 16-bit partition identifiers.

We estimate that preparing and completing these experiments will require up to three weeks. We plan to include the resulting sensitivity analysis in the camera-ready version, should the paper be accepted.

  1. Additional index construction time and online routing overhead.

The revised manuscript includes measurements of index construction time. Relative to the corresponding baselines, QER increases construction time by approximately 16.7% for ScaNN and 23.0–23.5% for LoRANN, on average across the evaluated datasets. We have also added a separate benchmark of routing execution time. Fine-grained timing instrumentation inside highly optimized search loops can introduce measurement overhead and perturb execution. We therefore isolate the routing code from the remaining search components and measure its execution time separately.

This benchmark characterizes the computational cost of routing in isolation, but does not account for the costs of integrating routing with partition scanning. Together with the end-to-end throughput results, these measurements provide a more complete picture of the trade-off between reduced scanning and the computational cost of iterative partition expansion.

Thank you for the detailed responses and additional experiments. However, I feel that my concerns regarding Questions 2 and 3 have not been adequately addressed. Additionally, I still believe that the novelty of the proposed method is limited. Therefore, I will maintain my original score.

Thank you for the follow-up. To clarify our response to Q2, Section 5 and Appendix C of the revised manuscript directly compare QER with LIRA’s learned probing model and Quake’s adaptive partition scanning (APS). The methods use the same partition assignment, queries, and exact candidate scoring, without vector replication. For each method and target mean Recall@100, we report the lowest mean number of scanned vectors per query among the evaluated configurations that attain the target. We measure routing latency separately on a single CPU thread, using LIRA’s original Python/PyTorch implementation and the original implementation of Quake APS provided by its authors.

  • LIRA. QER scans fewer vectors than LIRA in 69 of 76 dataset–recall settings: on 18, 16, 17, and 18 of 19 datasets at recall targets of 0.95, 0.97, 0.99, and 0.999, respectively. At the first three targets, the geometric means of the LIRA/QER routing latency ratios are 10.55×, 10.15×, and 10.04×, respectively.
  • Quake APS. At the same four targets, QER scans fewer vectors in 12/15, 14/15, 12/13, and 8/8 comparisons, respectively. The denominators include only datasets on which both methods reach the target; an unreached target is not counted as a QER win. At 0.95, 0.97, and 0.99, the geometric means of the APS/QER routing latency ratios are 4.06×, 4.94×, and 10.15×, based on 15, 14, and 11 datasets with validated timings, respectively.
  • Oracle adaptive CBR (ACBR). We additionally compare against ACBR, which uses ground-truth neighbours to choose a query-specific stopping point but is restricted to scanning a prefix of the centroid ranking. QER scans fewer vectors than this oracle at one or more tested recall targets on 5 of 19 datasets. Because the comparison is based on mean recall across queries, this advantage can reflect both which partitions QER visits and how it distributes scanning effort across queries. This advantage is not uniform: at 0.999, ACBR has the lowest scanning cost on all 19 datasets.

The timing ratios characterize routing latency in the evaluated implementations. They exclude vector scanning and feedback generation and do not represent end-to-end ANN speedups.

Could you help us better understand which aspects of Q2 you consider not yet fully addressed by these comparisons, and which specific limitations of the evaluation are most relevant to your remaining concerns?

Thank you for your patient and detailed explanation. I now understand your response to my second question.

Comments on the paper

1 comment

Dear Reviewers H3p7 and JRok, can you please clarify whether the author response addresses your concerns, and whether that affects your scores?

Participating in discussion period is a part of the duties of the Reviewers.

Thanks in advance.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.