- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
The paper presents a method for early terminating vector search queries on knn graphs, when these are not expected to improve the answer set.
Critical strengths
a. The authors tackle a significant and well motivated problem in modern vector search. b. The authors present a deep technical analysis of their solution. c. The authors use a wide variety of datasets.
Critical weaknesses
a. The method can be viewed as a conceptual refinement of what Patience In Proximity (PiP) does, and therefore the novelty appears somewhat limited, as both are saturation-based approaches that monitor how quickly the intermediate k-NN results of a query change. The main insight of the paper is that vector search can be terminated adaptively by monitoring the evolution of intermediate k-NN distances; however, this general idea has already been explored in prior work, including PiP for k-NN graphs and PatienceEarlyExit [1] for IVF.
b. The comparison of FeedSearch with other early-termination methods is based primarily on QPS and average achieved recall. However, this may provide an incomplete picture. When comparing adaptive early-termination methods that stop the search on a per-query basis, it is important to also report the performance at the individual-query level, for example through recall percentiles, distributions, or related statistics. Average recall across all queries can hide significant variation in per-query accuracy, making it difficult to assess the reliability of the method from aggregate recall alone. Prior work such as DARTH and AdaEf discuss this issue in detail.
c. The authors compare FeedSearch against a relatively limited set of early-termination methods. The evaluation would be strengthened by including additional relevant baselines, particularly methods such as PiP and ANNiE [2]. (I understand that ANNiE could not have been included in this submission, so this particular point is not affecting my score.)
d. The experimental evaluation is limited to a single class of index structures, k-NN graphs, since HNSW, NSG, and Vamana rely on very similar search procedures. While the authors explicitly define this as the scope of the paper, this choice limits the broader impact of the contribution, particularly since prior work already considers adaptive early termination for k-NN graphs (e.g., PiP) as well as for IVF indexes (e.g., PatienceEarlyExit). In addition, PiP has also been applied to improve index construction. A more general solution that supports adaptive early termination across both k-NN graphs and IVF indexes would greatly strengthen the contribution. If the authors extend FeedSearch to IVF, the evaluation should also include relevant IVF-oriented baselines, such as DARTH (IVF variant), LAET (IVF variant), Quake [3], ConANN [4], LIRA [5], and PatienceEarlyExit.
e. Another subtle point that deserves greater attention is the discussion of varying query difficulty. Query difficulty can indeed vary substantially even within standard query workloads, but this notion is closely tied to the corresponding recall target. In this respect, FeedSearch differs from methods such as DARTH, ANNiE, and AdaEf, which explicitly support recall-targeted search. FeedSearch does not provide the same capability, and this should be acknowledged as a limitation of the approach. The distinction should also be reflected more carefully in the paper’s framing and in the experimental comparison against methods that are designed to satisfy user-specified recall targets.
[1] Francesco Busolin, Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, and Salvatore Trani. Early exit strategies for approximate k-nn search in dense retrieval. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, 2024.
[2] Zeyu Wang, Manos Chatzakis, Qitong Wang, Themis Palpanas, Peng Wang, and Wei Wang. ANNiE: A learned query cost estimator for graph-based approximate nearest neighbor search. Proceedings of the VLDB Endowment, 19(11):3820–3833, 2026.
[3] Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. Quake: Adaptive indexing for vector search. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25), pages 153–169, 2025.
[4] Sonia Horchidan, Fabian Zeiher, Henrik Bostr¨om, and Paris Carbone. Conann: Conformal approximate nearest neighbor search. Proceedings of the VLDB Endowment, 19(1), 2025.
[5] Ximu Zeng, Liwei Deng, Penghao Chen, Xu Chen, Han Su, and Kai Zheng. Lira: A learning-based query-aware partition framework for large-scale ann search. In Proceedings of the ACM on Web Conference 2025, 2025.
Questions for authors
Please see the suggestions from above.
4 comments
Thanks for the additional work and clarifications. I did not claim that "treating direct recall prediction [or IVF] support as prerequisites for a meaningful contribution" is necessary. My point was that you are comparing methods that solve different problems (ie, FeedSearch that decides when an answer will not improve to Ada-ef/DARTH that decide when an answer has reached a user-defined recall target), and for this reason, the text should be clear on this point. Moreover, the individual query quality results should include all approaches. I have raised my overall score, but remain on the negative side.
Thank you for your follow-up and suggestions. Our previous reply went too far in attributing to you the view that recall prediction or IVF support is a prerequisite for a meaningful contribution.
We compare these methods because they address the same problem in proximity graph search. Different queries need different amounts of exploration, so the search needs a way to adapt when it stops. Consider Ada-ef. For a fixed HNSW index and a given k, efSearch is the standard search width used to trade query cost for recall. A larger efSearch lets HNSW retain more search alternatives and generally delays termination and improves recall. Two queries may need very different efSearch values to reach the same recall. Ada-ef uses early search statistics to assess query difficulty and a table of (efSearch, recall) pairs to select a width for each query. At execution time, this choice adapts the usual HNSW stopping condition to that query. Ada-ef, Sec. 6.2
DARTH uses an online recall estimate to decide when to stop, LAET predicts a distance-computation budget, and FeedSearch decides when to stop from the history of improvements to the current top-k. These are different ways of making a query-specific stopping decision. This common role motivates our comparison of end-to-end query cost at achieved recall. DARTH and LAET Even with perfectly accurate recall prediction, the system still has to execute the graph search to return the top-k items. The practical gain depends on how much search cost the stopping rule saves at the same measured recall. A nominal target can also differ substantially from achieved recall. At a target of 0.95, our L2 adaptation of Ada-ef with the default statistics window achieves mean Recall@10 of 0.8608, 0.8733, 0.9891, and 0.9569 on DEEP1M, SIFT10M, GIST1M, and Tiny5M, respectively. The first two fall short by 8.92 and 7.67 percentage points, which indicates the contribution from predicting a recall is limited.
FeedSearch contributes a training-free stopping rule that uses both the magnitude and history of top-k improvements. It can be applied to existing HNSW, NSG, and Vamana indexes without changing the graph or rebuilding the index. We give conditions for continued productive exploration, bound the additional distance computations once gains cease, and construct graphs where FeedSearch saves distance computations at equal recall. On SIFT10M, FeedSearch achieves 30.7% higher QPS than tuned L2 Ada-ef at the same measured Recall@10 of 0.9689.
Thank you for reconsidering our submission and raising your rating. If our follow-up addresses your remaining concerns, we would appreciate your considering a further one-point increase.
We thank the reviewer. We will strengthen PiP comparisons, report individual-query quality, and clarify recall targeting and graph scope.
We respectfully disagree with treating direct recall prediction or IVF support as prerequisites for a meaningful contribution. Graph-based indexing is mainstream: HNSW is used by Elasticsearch, Qdrant, and Weaviate. Improving existing graph search without rebuilding the index has practical value. We ask that FeedSearch be assessed within this stated scope.
(a, c) Contribution and PiP comparison
We will credit prior result-based early termination. FeedSearch contributes magnitude- and history-sensitive feedback: a replacement contributes (1/k) log(d_out/d_in), with the distance floor inactive, to a moving average normalized by a decaying maximum. Identical replacement events can yield different stopping decisions when gain magnitudes differ. Feed observes distance evaluations; PiP monitors successful-collection saturation at expansion boundaries.
The controlled comparison shares graph, entries, candidate admission/order, and distance implementation, with independent tuning and six gamma values for PiP:
Real-data performance is comparable at these points. On Hard1M, long search tails with frequent tiny improvements expose the distinction: Feed raises QPS from 3,502.7 to 6,434.0 and reduces mean computations from 2,949.91 to 1,653.54 (-43.95%). A tuned binary-gain ablation retaining the controller/clock requires 2,941.24 computations at the same recall.
Hard1M uses a constructed 16-NN+MST graph, favorable entries, and 32D geometry lifted to 1536 coordinates. Long paths alone do not ensure a gain; at shared recall 0.99125, Feed is 15.53% slower. New QPS results use one 160-worker round for selection and reporting.
(b) Individual-query quality
At the above operating points, paired exact top-10 hit counts under Feed versus PiP are:
Real-data rows contain 1,000 queries each; Hard1M contains 4,000. On Hard1M, the 83.69% QPS gain preserves every query's recall, directly addressing possible hidden accuracy losses behind an aggregate improvement. Real-data pairs identify both gains and losses. We will report these distributions explicitly.
(e) Recall targeting and practical value
We will define difficulty relative to the desired quality. Our score measures progress, not recall probability; achieved recall depends on query distribution and search geometry. At k=10, one missed neighbor changes individual recall by ten percentage points.
An explicit target also needs calibration. At nominal target 0.95, our L2-adapted Ada-ef with its default statistics window achieves 0.8608/0.8733/0.9891/0.9569 on DEEP/SIFT/GIST/Tiny. These are aggregate calibration gaps, not prediction MAE. Window tuning improves the mapping. LAET predicts effort, not numerical recall.
At exactly matched recall on SIFT, Feed obtains 23,458.8 versus 17,945.6 QPS for tuned Ada-ef at recall 0.9689 (+30.72%), and 31,151.7 versus 8,760.7 for tuned LAET at recall 0.9614 (3.56x). These are three-round median end-to-end results retaining baseline implementations. Recall prediction can aid allocation, but useful efficiency gains do not require it. Feed still needs threshold calibration and may need recalibration after distribution changes.
(d) Graph scope and contribution
FeedSearch is tailored to graph traversal: proximity edges generate a frontier whose result improvements guide stopping. IVF requires separate reasoning about unprobed lists; extending to it needs its own design and baselines.
Within graph search, the contribution combines magnitude-sensitive feedback, a training-free controller, sufficient conditions for productive exploration, a finite zero-gain tail bound, and graph constructions with equal-recall savings over native width control. These are conditional results. Evaluation spans 24 HNSW/NSG/Vamana workloads. Reusing graph edges and vectors without rebuilding the index makes the measured recall-QPS improvements practically useful within this widely adopted index family.