acceptodds
Under review as a conference paper at ICLR 2027

Efficient Approximate Vector Search via Adaptive Result Feedback on Graphs

36 views

Abstract

Graph-based approximate nearest neighbor search is a fundamental component of vector retrieval in modern AI systems. Efficient search requires adapting exploration to the needs of individual queries, whose results may improve at different rates throughout execution. Conventional search-width and frontier-based controls do not explicitly track this temporal progress, limiting their ability to identify when additional exploration remains productive. We propose feedsearch, a query-state-aware search strategy that accelerates search on proximity graphs through online result feedback. Feedsearch characterizes a query's evolving search state using the magnitude and temporal history of improvements to its current top- results. A lightweight, training-free controller inspired by Adam maintains decaying statistics of these improvements and normalizes recent progress against a query-specific scale. This feedback determines how long exploration continues, allowing the strategy to adjust search effort as the query progresses. A lazy implementation skips repeated statistic updates during zero-gain intervals. Experiments across diverse datasets, graph indexes, and similarity measures demonstrate improved recall–throughput trade-offs on a range of workloads.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Vector Search, RAG, Adam

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_nosGOpenReview ↗
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

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:

DatasetRecall PiP / FeedFeed QPS change
DEEP1M0.9510 / 0.9510-7.18%
SIFT10M0.9501 / 0.9517+8.32%
GIST1M0.9502 / 0.9503-5.52%
Tiny5M0.9500 / 0.9500-7.05%
Hard1M0.9500 / 0.9500+83.69%

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:

DatasetFewer/equal/more hitsQueries below recall 0.9, PiP/Feed
DEEP1M15/966/1911.9%/12.0%
SIFT10M26/956/188.1%/8.3%
GIST1M17/964/1911.6%/11.8%
Tiny5M12/969/1911.6%/11.7%
Hard1M0/4000/00.0%/0.0%

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.

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.

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

The paper proposes FEEDSEARCH, a training-free, query-adaptive early-termination strategy for graph-based approximate nearest-neighbor search. It monitors improvements to the current top-k results and feeds them into an Adam-inspired controller; search stops once a normalized progress score drops below a threshold. The method adds only O(1)O(1) state, requires no index rebuild, and works with existing HNSW/NSG/Vamana indexes. On 24 graph–dataset workloads across L2/cosine/MIPS, it reports 5–40% higher throughput at Recall@10 ≈0.95\approx 0.95.

Critical strengths

S1. The method is training-free, requires no index rebuild, and adds only O(1) controller state.

S2. It is validated across 24 graph–dataset workloads spanning L2/cosine/MIPS against five baselines with fair comparison.

Critical weaknesses

W1. §2.2 discusses PiP (patience/stagnation, Teofili & Lin 2025) and Terminus (rank-weighted gains, Lu et al. 2026), and §1 motivates the method with a stagnation counter — yet none appears in §5.3, which compares only Native, Ada-ef, DARTH, LAET, and DABS.

W2. sts_t is not a recall estimate; Λ\Lambda re-parameterizes the tuning problem. sts_t tracks the magnitude and history of distance improvements, not recall, so reaching a target Recall@10 still requires sweeping Λ\Lambda per operating point. The Λ\Lambda-vs-recall mapping and its tuning cost relative to a fixed width (efSearch/L\texttt{efSearch}/L) should be made explicit, or the "adaptive, training-free" advantage is overstated.

Questions for authors

Q1. Why are PiP and Terminus absent from §5.3, and can you add them (or justify exclusion)?

Q2. How is Λ\Lambda selected to hit a target Recall@10 in practice? Please report the Λ\Lambda values used per dataset, the cost of choosing them versus tuning \texttt{efSearch}, and a sensitivity analysis over β1\beta_1, β2\beta_2, and Λ\Lambda.

Q3. Does query-adaptive stopping inflate tail latency, and what is the worst case frontier memory from unrestricted candidate retention? Please report per-query latency percentiles (p50/p99) and frontier sizes from the 24-workload sweep.

1 comment

We thank the reviewer. We will add stopping-rule comparisons, calibration/sensitivity results, and tail/memory measurements. We disagree with making direct recall prediction a prerequisite for useful adaptive search. The practical criterion is achieved quality and query cost. Graph search is mainstream, as illustrated by Qdrant's HNSW index. Improving existing indexes without rebuilding them has value within this scope.

Q1. PiP and Terminus

The PiP comparison shares graph topology, entries, candidate admission/order, and distance computation. Both policies are independently tuned; PiP uses six gamma values with dense patience refinement.

DatasetRecall PiP / FeedFeed QPS change
DEEP1M0.9510 / 0.9510-7.18%
SIFT10M0.9501 / 0.9517+8.32%
GIST1M0.9502 / 0.9503-5.52%
Tiny5M0.9500 / 0.9500-7.05%
Hard1M0.9500 / 0.9500+83.69%

The methods perform comparably on these real-data points. FeedSearch helps when long exploration tails contain frequent tiny improvements: it uses gain magnitudes/history at distance-evaluation events, whereas PiP counts successful collections at expansion boundaries.

On Hard1M, QPS rises from 3,502.7 to 6,434.0 and mean computations fall from 2,949.91 to 1,653.54, with identical hit counts for all 4,000 queries. A tuned binary-gain variant retaining the controller 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. At shared recall 0.99125, Feed is 15.53% slower. New QPS results use one 160-worker round for both selection and reporting.

We also added a coarse-grid Terminus utility port, observing top-10 results per graph expansion instead of its original I/O/top-L setting. This tests a mapped signal, not the disk-based system. GIST costs are 5,521.16 computations at recall 0.9509 for the port versus 5,550.83 at 0.9500 for Feed. Tiny does not reach 0.95 within the declared grid; refinement remains incomplete.

Q2. Lambda selection and query adaptation

Lambda selects a global operating point; each query's progress determines its stopping time. Calibration therefore retains query-dependent computation. We fix beta_1=0.9 and beta_2=0.99, sweep Lambda on representative queries with exact neighbors, and freeze a setting meeting the required aggregate recall.

DatasetLambdaAchieved Recall@10
DEEP1M40.44920.9510
SIFT10M46.90630.9517
GIST1M121.61720.9503
Tiny5M281.97660.9500

We will report the Lambda-recall curves and nine-pair beta sweep, recalibrating Lambda for each pair.

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 end-to-end results demonstrate useful adaptation without direct recall prediction.

Explicit targets also require 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 per-query prediction errors; tuning improves the mapping. LAET predicts effort rather than numerical recall.

For the disclosed grids, evaluation costs in DEEP/SIFT/GIST/Tiny order are 11.82/11.41/64.49/66.33 seconds for Feed and 6.90/9.83/40.84/55.05 for native-width tuning, excluding loading/warmup/serialization. Grid sizes differ. Feed requires no predictor training or index rebuilding; Lambda still needs calibration and possible recalibration under distribution changes, without a per-query recall guarantee.

Q3. Tail latency and frontier memory

FeedSearch at the Q1 recalls; measured search-call latencies in milliseconds:

Datasetp50/p99, 1 workerp50/p99, 160 workersPeak queue KiB
DEEP1M1.20/2.995.93/17.00128.2
SIFT10M1.34/3.503.10/8.93128.2
GIST1M6.58/15.5650.05/152.22256.2
Tiny5M11.44/30.2156.39/215.44512.2

Peak queue sizes are 4,609/6,241/13,719/29,623 nodes. Queue capacities exclude visited state (separately 4*N bytes/worker), allocator overhead, and index storage. Only controller state is O(1); the frontier can grow to O(|V|). Observed peaks are not worst-case bounds. Diagnostics cover four HNSW/L2 workloads, not all 24 combinations; latency excludes external queuing/networking.

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

This paper proposes FEEDSEARCH, a stopping rule for graph search that uses the size and history of improvements in the current top k results. It compares a moving average of improvements with a decaying maximum to decide when to stop. The authors also reduce repeated calculations when results do not improve. Experiments use HNSW, NSG, and Vamana on eight datasets and compare FEEDSEARCH with several existing search methods.

Critical strengths

(1) FEEDSEARCH can be used on existing graph indexes without rebuilding them. The comparisons use the same graph for the proposed method and the original search method. This makes the measured difference useful for assessing changes to search. Testing several graph types and similarity measures also gives the method a broad evaluation.

(2) The method does not require training a model to predict when search should stop. Its stopping rule and updates are clearly described. Appendix B.2 also compares methods at the same measured recall. These results support the claim that the complete method can answer queries faster than several tested alternatives.

Critical weaknesses

(1) The experiments do not show why the stopping rule needs both the size and history of improvements. A simpler rule can stop after a fixed number of distance computations without a result change. The paper shows that this rule already saves work on one query. However, it does not compare the two rules across the datasets or test what happens when parts of FEEDSEARCH are removed. This leaves the benefit of the proposed design unclear.

(2) FEEDSEARCH also changes which points are kept for later search. It puts every newly discovered point into the candidate queue, while the original methods limit the points they keep. This change can itself affect recall and speed. The paper states that memory can grow with the number of discovered points, but does not measure the largest memory use or the times for slower queries. The contribution of the stopping rule and the memory cost of the complete method therefore remain unclear.

Questions for authors

(1) When all methods keep the same candidate points, how does FEEDSEARCH compare with a rule that stops after a fixed number of computations without a result change? Please also include a comparable PiP rule and report speed at the same recall. This would test the value of using improvement size and history.

(2) What happens to recall and speed if the moving average or the division by the decaying maximum is removed? Please also measure the time used by the stopping rule with and without the shortcut for steps that do not improve results. The existing mathematical analysis does not provide these measurements.

(3) How much memory does the candidate queue use at its largest size? Please also report the times within which 95 percent and 99 percent of queries finish, including the setting with 160 workers. Average query speed does not show whether a few difficult queries need much more time or memory.

3 comments

We thank the reviewer. We will add controlled stopping-rule comparisons, ablations, controller timings, and tail/memory measurements. Improving the recall-throughput trade-off on existing graph indexes without rebuilding them is a practical contribution, independently of direct recall prediction or an IVF extension.

Q1. Controlled stopping comparisons

FeedSearch, PiP, and the ablations share the graph, entries, candidate admission/order, and distance implementation. PiP is tuned over six gamma values with dense patience refinement. Near a 95% Recall@10 requirement:

DatasetRecall PiP / FeedFeed QPS change
DEEP1M0.9510 / 0.9510-7.18%
SIFT10M0.9501 / 0.9517+8.32%
GIST1M0.9502 / 0.9503-5.52%
Tiny5M0.9500 / 0.9500-7.05%
Hard1M0.9500 / 0.9500+83.69%

Real-data performance is comparable at these points. The distinction matters during long search tails with frequent tiny improvements: PiP counts successful collections at expansion boundaries; FeedSearch uses improvement magnitudes and history at distance-evaluation events.

On Hard1M, FeedSearch obtains 6,434.0 versus 3,502.7 QPS and uses 1,653.54 versus 2,949.91 distance computations. All 4,000 queries retain identical hit counts. Independently tuned fixed-counter and binary-gain variants require 2,950.57 and 2,941.24 computations at the same recall. The binary variant retains the controller and observation clock, isolating gain magnitudes. New QPS results use one 160-worker timing round, also used for configuration selection.

Q2. Components and controller cost

Without the moving average or an added patience rule, instantaneous normalized gain gives maximum scanned recalls of 0.0509, 0.0393, 0.0241, and 0.0184 on DEEP/SIFT/GIST/Tiny: intermittent zero gains cause premature stopping. This tests smoothing within our formulation.

Removing normalization while retaining the moving average gives these independently tuned minimum-distance points with recall >= 0.95; entries are Feed / unnormalized EMA:

DatasetRecallQPS
DEEP1M0.9502 / 0.950019968.4 / 19333.3
SIFT10M0.9500 / 0.950232936.9 / 36132.3
GIST1M0.9500 / 0.95012286.4 / 2275.4
Tiny5M0.9500 / 0.95002020.0 / 2005.3

These single-round results do not establish an independent speed benefit for every component. On Hard1M, removing normalization increases mean computations from 1,653.54 to 1,693.55 at recall 0.95.

We replayed 32 predeclared trajectories per dataset, 200 times each, to isolate controller execution. Median lazy / ordinary-double eager costs in ns/event are 19.57/7.05, 36.92/13.38, 10.91/6.26, and 17.75/39.41 on DEEP/SIFT/GIST/Tiny. All 32 first-stop positions match on each dataset. Lazy updates preserve stopping behavior in this sample but do not consistently reduce runtime; we will qualify the claim.

Q3. Tail latency and candidate memory

For FeedSearch at the Q1 recalls, directly measured search-call latencies are in milliseconds:

Datasetp95/p99, 1 workerp95/p99, 160 workersPeak queue KiB
DEEP1M2.27/2.9912.91/17.00128.2
SIFT10M2.60/3.506.62/8.93128.2
GIST1M12.01/15.56107.49/152.22256.2
Tiny5M22.77/30.21139.00/215.44512.2

Peak queue sizes are 4,609/6,241/13,719/29,623 nodes in the same order. Queue capacities exclude visited state, allocator overhead, and index storage; visited-state payload is separately 4*N bytes/worker. Only controller state is O(1); the candidate frontier can grow to O(|V|). Observed maxima are not worst-case bounds. Latency excludes external queuing/networking. These diagnostics cover the four supplemental HNSW/L2 workloads, not all 24 graph-dataset combinations.

Thank you for the response. Based on the additional results, the proposed method does not consistently outperform the much simpler PiP baseline at comparable recall. The large improvement on Hard1M alone is insufficient to establish that this advantage generalizes to common datasets. I therefore maintain my rating.

Thanks for the follow-up. FeedSearch's gains extend beyond Hard1M. On the original SIFT10M HNSW index at the 97.5% recall requirement, FeedSearch achieved 0.9757 Recall@10 versus PiP's 0.9750. With the same configurations across three rounds, its QPS was 6.6%, 10.6%, and 5.6% higher. On FIVR-5K queries from held-out videos, FeedSearch reduced p99 distance counts by 11.9% at nearly identical recall (0.9615 vs. 0.9614) and median QPS (5,982 vs. 5,993).

FeedSearch is a continuous counterpart to PiP's update-counting approach. It uses the magnitude and history of top-k improvements, so small and large updates can lead to different stopping decisions. This richer signal can also support future learning-based policies that adapt the stopping rule to each query.

FeedSearch already improves throughput over methods from leading database and AI venues. On SIFT10M, at pairwise matched Recall@10, it achieves 30.7% higher QPS than L2 Ada-ef (0.9689), 3.56x the QPS of LAET (SIGMOD, 0.9614), and 13.5% higher QPS than DABS (NeurIPS, 0.9738). It delivers these gains with a training-free controller on an existing index.

If these results address your concern about gains on real workloads, we would be grateful if you would consider raising your overall rating.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to the Reviewers

We thank the reviewers for their constructive feedback. We will revise the manuscript to add direct PiP comparisons and component ablations, clarify calibration and query-level quality, report controller overhead and tail/resource costs, and make the graph-specific scope and theoretical assumptions explicit.

We respectfully disagree with treating direct recall prediction or applicability to IVF as necessary conditions for a meaningful contribution to vector search. Graph-based indexing is a mainstream foundation of modern vector-search systems: HNSW is used in Elasticsearch and Qdrant, and is recommended for most use cases in Weaviate. Improving the achieved recall-throughput trade-off on existing graph indexes without rebuilding them has practical value in its own right. We ask that FeedSearch be assessed on its algorithmic contribution, evidence, and deployment benefits within this stated scope.

  1. PiP comparison and when magnitude-sensitive feedback helps

We added controlled comparisons sharing graph topology, entries, candidate admission/order, and distance computation. With independent tuning, PiP and FeedSearch perform comparably on the four real datasets near 95% Recall@10: Feed's QPS changes range from -7.18% to +8.32%.

The distinction matters when long search tails contain frequent but negligible improvements. PiP monitors successful-collection counts, while FeedSearch uses improvement magnitudes and recent history. On a 1M-vector workload at exactly the same Recall@10 of 0.95, FeedSearch raises QPS from 3,502.7 to 6,434.0 (+83.69%) and reduces mean distance computations by 43.95%, with unchanged hit counts for all 4,000 queries. A tuned binary-gain ablation retaining FeedSearch's controller requires 2,941.24 computations versus 1,653.54 for FeedSearch, supporting the contribution of magnitudes.

  1. Recall prediction and practical effectiveness

Realized recall depends on query distribution and search geometry; direct prediction does not remove the need for calibration. With nominal target 0.95 and the default statistics-window rule, our L2-adapted Ada-ef achieves 0.8608, 0.8733, 0.9891, and 0.9569 on DEEP, SIFT, GIST, and Tiny. These are aggregate target-to-achieved gaps in our adaptation, not per-query prediction errors. Window tuning improves the mapping. LAET predicts search effort rather than numerical recall, and its multiplier likewise requires operating-point selection.

The practical objective is to meet the required retrieval quality at low query cost. At exactly matched achieved recall on SIFT, FeedSearch provides 30.72% higher QPS than tuned Ada-ef at recall 0.9689, and 3.56x the QPS of tuned LAET at recall 0.9614. These existing comparisons use three-round median, end-to-end timings with the baseline search implementations retained. They establish useful measured gains without attributing them solely to prediction accuracy. FeedSearch remains subject to threshold calibration and possible recalibration under distribution changes; its progress score is not a per-query recall guarantee.

  1. Graph-specific contribution and deployment value

FeedSearch is tailored to nearest-neighbor graph traversal, where successive result improvements provide feedback on exploration. IVF requires separate reasoning about coarse partitions and unprobed lists, so applying the same stopping rule directly is not justified. An IVF extension would broaden the contribution, but is not required to establish its value for graph search.

Within this scope, FeedSearch combines magnitude- and history-sensitive feedback with a training-free controller, conditional guarantees for productive exploration and zero-gain tail cost, and graph constructions demonstrating equal-recall savings over native search-width control. Evaluation spans 24 workloads across HNSW, NSG, and Vamana. Existing graph edges and vectors are reused without index reconstruction. We believe this combination of algorithmic design, analysis, and practical integration supports a substantive contribution, and ask the reviewers to reassess the work in light of the new controlled evidence and clarified claims.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.