acceptodds
Under review as a conference paper at ICLR 2027

Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning

Abstract

Graph-based approximate nearest neighbor search (ANNS) is widely used for large-scale semantic search. Its indices are constructed primarily based on geometric relationships among embeddings of an input dataset (e.g., documents or images), rather than explicitly optimizing for semantic relevance. However, when using these indices for downstream query retrieval, performance is evaluated based on the semantic relevance of the retrieved results to the query. This creates a fundamental "geometry-semantic" mismatch between how the indices are constructed and how their retrieval results are evaluated. While existing LLM-based reranking methods can partially mitigate this mismatch at query time, they leave this underlying structural problem in the graph unresolved. We therefore propose LLM-Guided Graph Pruning (LGP), a general framework that addresses this mismatch directly by leveraging LLM reasoning to refine an existing ANN graph index itself. LGP identifies structurally "low-value" neighbors of nodes and replaces them with LLM-selected alternatives that provide useful semantic information while retaining desired geometric structures of the original graph, including sparsity and efficient navigability. Experiments on representative semantic retrieval benchmarks show that LGP consistently improves end-to-end retrieval performance over both vanilla greedy graph search and LLM-based reranking across widely used graph-based ANN indices such as DiskANN and HNSW.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Approximate Nearest Neighbor Search, Graph-Based ANN Indexes, Information Retrieval, Large Language Models, Graph Pruning

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_j4CtOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper identifies a fundamental "geometry-semantic" mismatch in graph-based approximate nearest neighbor search, where index construction relies on geometric proximity while downstream retrieval is evaluated on semantic relevance. To address this, the authors propose an LLM-guided graph pruning framework. This offline method leverages large language model reasoning to replace structurally redundant, low-value neighbors with semantically more informative alternatives, while preserving graph sparsity and navigability. The method is instantiated on DiskANN and HNSW indices and validated on textual and multimodal benchmarks. Results demonstrate consistent improvements in both greedy search and reranking stages under constrained computation budgets.

Critical strengths

S1. The paper accurately articulates the inherent misalignment between geometric index construction and semantic retrieval goals, offering a novel and precise problem definition.

S2. Extensive experiments cover textual and multimodal datasets, two mainstream graph indices, various embedding models, and different computation budgets, proving strong generalization and robustness.

S3. The method introduces model calls only during the offline index construction phase. The query-time greedy search algorithm remains unchanged, ensuring high practical value for deployment.

Critical weaknesses

W1. While the paper claims offline costs are acceptable, experiments are limited to small-scale datasets (e.g., thousands to tens of thousands of nodes). There is a lack of detailed analysis and estimation of total latency, memory footprint, and financial costs of model calls on industrial-scale datasets (e.g., millions or billions of nodes).

W2. The method relies on two-hop neighborhoods and specific geometric ranking signals to shortlist candidates. The paper does not sufficiently discuss whether this local candidate pool can provide high-quality semantic alternatives when the initial graph quality is poor or the data distribution is extremely sparse, posing a risk of introducing noise or degrading graph connectivity.

W3. The paper mainly compares against vanilla indices and query-time reranking. Although it mentions the high cost of purely semantic graph construction, it lacks quantitative comparison with recent baseline methods that optimize graph structures using lightweight semantic models or contrastive learning, leaving the technical boundaries unclear.

Questions for authors

Q1. Regarding offline costs, please provide an estimation of the expected time complexity, resource consumption, and financial cost of running the framework on larger-scale datasets (e.g., millions or billions of nodes).

Q2. Regarding candidate construction, if the local two-hop neighborhood of the initial graph lacks highly semantically relevant nodes, could the replacement mechanism introduce noise or degrade graph navigability? Please provide analysis or supplementary experiments on such edge cases.

Q3. Please provide quantitative comparisons with recent baseline methods that also utilize semantic information to optimize graph index structures, to further clarify the technical boundaries and advantages of the proposed method.

2 comments

W1&Q1. Regarding offline costs, please provide an estimation of the expected time complexity, resource consumption, and financial cost of running the framework on larger-scale datasets (e.g., millions or billions of nodes).

A: Thank you for your comments. The LLM pruning overhead of LGP scales as O(n)O(n) under fixed inference settings. Graph and embedding storage requires O(n(R+d))O(n(R+d)) space, where nn is the number of nodes, dd is the embedding dimension, and RR is the maximum out-degree. Under the hardware settings used in our experiments, LGP takes approximately 0.785 seconds per node for graph pruning. This corresponds to approximately 218 GPU-hours for one million nodes, or $172 at Nebius's published H200 spot rate of $0.79/GPU-hour. Importantly, this cost is incurred entirely offline. Once constructed, the refined graph can serve subsequent queries without additional LLM pruning calls, allowing the construction cost to be spread across many queries over the index's lifetime.

W2&Q2. The method relies on two-hop neighborhoods and specific geometric ranking signals to shortlist candidates. .....Regarding candidate construction, if the local two-hop neighborhood of the initial graph lacks highly semantically relevant nodes, could the replacement mechanism introduce noise or degrade graph navigability? Please provide analysis or supplementary experiments on such edge cases.

A: Thank you for your comments. LGP refines an existing embedding-based ANN graph. While there is a gap between geometric similarity and semantic relevance, this does not mean that the initial graph lacks useful semantic connections. LGP aims to improve these connections through neighborhood-aware pruning.

Furthermore, to evaluate LGP's robustness to weaker initial graphs, we reduced DiskANN's construction width on Pony from Lbuild=125L_{\mathrm{build}}=125 to 11, keeping all other settings unchanged. This parameter controls how broadly the algorithm searches for neighbors during graph construction. Setting it to 11 greatly limits the candidate search and can result in weaker graph quality. At a fixed budget of 200 distance computations, Vanilla's exact-neighbor Recall@10 drops from 72.77% to 26.52%, confirming that the resulting graph provides substantially weaker retrieval support. We then evaluated LGP on this weaker graph using the same distance budget. The results are shown below:

MethodNDCG@10Document Recall@10Exact-neighbor Recall@10
Vanilla11.495.3926.52
LGP15.437.1433.48

Despite the substantially weaker initial graph, LGP improves all three metrics, including exact-neighbor Recall@10. These results demonstrate its robustness to variations in initial graph quality.

W3&Q3. ...it lacks quantitative comparison with recent baseline methods. Please provide quantitative comparisons with recent baseline methods that also utilize semantic information to optimize graph index structures, to further clarify the technical boundaries and advantages of the proposed method.

A: Thank you for the suggestion. We conducted an additional comparison with RoarGraph [1], a query-aware graph construction method that optimizes graph connections using query–document similarities. We use its official implementation with Mpjbp=16M_{\mathrm{pjbp}}=16 and evaluate greedy search under a fixed budget of 200 distance computations. Each entry reports NDCG@10 / document Recall@10:

MethodPonyPsychology
Vanilla19.16 / 9.5314.92 / 15.49
RoarGraph15.65 / 8.5318.20 / 19.83
LGP19.70 / 9.8021.24 / 24.95

LGP achieves the highest NDCG@10 and Recall@10 on both datasets, outperforming both Vanilla and RoarGraph. These results demonstrate the benefit of LGP's semantic-guided pruning. We will include these results in the revision.

[1] Chen, Meng, et al. "Roargraph: A projected bipartite graph for efficient cross-modal approximate nearest neighbor search." arXiv preprint arXiv:2408.08933 (2024).

Dear Reviewer j4Ct,

As the public discussion period is coming to a close tomorrow, we wanted to kindly follow up and ask whether you have any remaining questions or concerns that we could address. We would be happy to provide further clarification. Thank you again for your time and consideration.

Best regards,

The authors

Reviewer_gNQSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces LGP (LLM-Guided Graph Pruning), an offline framework that refines graph-based ANN indices to reduce the mismatch between embedding-based graph construction and semantic relevance. For each node, LGP builds a candidate set from its two-hop neighborhood, shortlists candidates with structural signals such as two-hop coverage and redundancy, uses an LLM to select semantically useful candidates, and replaces low-value existing neighbors while keeping the degree bound and the query-time search unchanged. Experiments on BRIGHT and M-BEIR with DiskANN and HNSW demonstrate the effectiveness of the proposed method under both greedy search and LLM reranking.

Critical strengths
  1. The paper moves LLM reasoning from query time to index construction without changing the query-time search, so the refined graph can be used directly in existing retrieve-then-rerank pipelines.
  2. LGP improves the average NDCG@10 under both greedy search and reranking on text and multimodal benchmarks and with two embedding models (Tables 1-3 and 6), which suggests that it is not tied to one setting.
Critical weaknesses
  1. I understand that the paper targets a constrained search budget, as stated in Lines 65-67, but the gains shrink quickly outside it. On BRIGHT, the gain is only 1.8% at search width 200 in Table 3 and 0.6% at 1,600 distance computations in Table 4, and LGP is worse than Vanilla on Psychology at R=32R=32 in Table 7. In addition, the corpora in Table 8 are small (8K-414K documents), where exact search seems affordable and outperforms LGP at all tested widths in Table 3, while Table 16 shows that LGP needs one LLM call per node and takes 691 minutes to build Psychology, compared with 12 minutes for Vanilla. Evaluating on larger corpora with larger RR and search width would make the practical benefit more convincing.

  2. Although Table 7 shows that a larger LLM helps, the paper lacks a baseline that isolates the role of the LLM. LGP also changes edges with structural signals, such as two-hop coverage, separation, and gming_{min}, which may improve navigability on their own, as the large gains at R=8R=8 in Table 7 suggest. Replacing LLMSelect with random selection from the same shortlist, and reporting the recall of the exact top-10 neighbors, would show whether the gains come from semantic selection.

Questions for authors
  1. In Figures 4 and 11, the default BB, MM, KK, and gming_{min} appear to be the best values on Pony and Psychology, which are also evaluation datasets. How were the defaults chosen, and was a held-out set used?

  2. Consider another approach with the same one LLM call per document: generate pseudo-queries, as the LLMSelect prompt already does privately, and use them for document expansion [1] or query-aware graph construction [2, 3]. What is the advantage of LGP over this approach?

  3. Lines 186-189: Oracle picks the best of many one-edge variants for each query using ground-truth labels, so it may beat Vanilla even if the variants differ only by chance. Does an edge chosen by Oracle for one query also help other queries?

  4. Lines 94-95: The "up to 50% fewer distance computations" claim seems to come from Economics only, as stated in Lines 411-413, while in Table 4, LGP at 800 computations is still below Vanilla at 1,600 on average (26.61 vs. 27.11). Could the paper report the per-dataset budget results?

[1] Nogueira, Rodrigo, et al. "Document expansion by query prediction." arXiv preprint arXiv:1904.08375 (2019).

[2] Jaiswal, Shikhar, et al. "Ood-diskann: Efficient and scalable graph anns for out-of-distribution queries." arXiv preprint arXiv:2211.12850 (2022).

[3] Chen, Meng, et al. "Roargraph: A projected bipartite graph for efficient cross-modal approximate nearest neighbor search." arXiv preprint arXiv:2408.08933 (2024).

5 comments
AuthorsOpenReview ↗

Rebuttal (1/2)

W1: ...but the gains shrink quickly outside it... In addition, the corpora in Table 8 are small (8K-414K documents), where exact search seems affordable and outperforms LGP at all tested widths in Table 3, while Table 16 shows that LGP needs one LLM call per node and takes 691 minutes to build Psychology, compared with 12 minutes for Vanilla. Evaluating on larger corpora with larger RR and search width would make the practical benefit more convincing.

A: Thank you for your comments. We would like to clarify that our evaluation already includes EDIS, which contains 1,047,067 indexed documents. On this dataset, LGP at search width 50 achieves NDCG@10/Recall@10 of 16.29/20.17, compared with 15.82/20.00 for Vanilla at width 100, while reducing measured CPU search latency by 29.1%. This directly demonstrates our main objective: achieving better retrieval quality with less search computation.

We additionally tested R=32R=32 on Biology and Economics without retuning the pruning hyperparameters. At search width 20, LGP improves both NDCG@10 and Recall@10. The results in the following table show that LGP's improvements are not limited to R=16R=16.

DatasetVanilla NDCG@10LGP NDCG@10Vanilla Recall@10LGP Recall@10
Biology43.2544.6050.8152.20
Economics29.0229.4431.4632.25

Regarding exact search, we agree that it provides higher retrieval quality. However, exact search can be much slower in practice, making it less suitable for latency-sensitive applications. On EDIS, exact search takes 121.00 ms, compared with 5.26 ms for LGP at width 50 under the same setting. Thus, approximate retrieval remains valuable when strict latency constraints make exact search impractical. Although LGP requires additional offline construction time, the refined graph improves retrieval across subsequent queries without query-time LLM calls. For static or infrequently updated indices, this investment can be spread across many queries over the index’s lifetime.

W2: Replacing LLMSelect with random selection from the same shortlist, and reporting the recall of the exact top-10 neighbors, would show whether the gains come from semantic selection.

A: Thank you for the suggestion. We replace LLMSelect with uniform random selection of up to two candidates from the same shortlist, keeping all other settings fixed. We evaluate on Pony and Psychology with a budget of 200 distance computations. Exact-neighbor Recall@10 measures overlap with the exact embedding-space top-10.

DatasetMethodNDCG@10Document Recall@10Exact-neighbor Recall@10
PonyVanilla19.169.5372.77
PonyRandom18.179.7670.36
PonyLGP19.709.8069.20
PsychologyVanilla14.9215.4942.18
PsychologyRandom17.4818.8549.39
PsychologyLGP21.2424.9552.48

As shown in the table, LGP outperforms random selection in NDCG@10 and document Recall@10 on both datasets, confirming the benefit of LLM semantic selection. On Pony, LGP improves semantic retrieval despite lower exact-neighbor recall, further highlighting the gap between geometric similarity and semantic relevance.

Q1: How were the defaults chosen, and was a held-out set used?

A: Thanks for your comments. We selected the default hyperparameters on Pony and kept them fixed across all remaining datasets.

AuthorsOpenReview ↗

Rebuttal (2/2)

Q2: Consider another approach with the same one LLM call per document: generate pseudo-queries, as the LLMSelect prompt already does privately, and use them for document expansion [1] or query-aware graph construction [2, 3]. What is the advantage of LGP over this approach?

A: Thank you for the suggestion. The main advantage of LGP is that it directly uses LLM semantic reasoning to select graph edges, rather than relying on embedding similarity to capture the generated semantic information. Specifically, document expansion encodes LLM-generated pseudo-queries into document representations, while query-aware graph construction uses query–document embedding similarities to guide graph connections. Both approaches still rely on embeddings to capture semantic relevance and may therefore retain the misalignment we aim to address. In contrast, LGP directly uses LLM reasoning to select edges that improve the existing graph structure.

To validate this advantage, we additionally evaluated both suggested approaches: pseudo-query expansion [1] and RoarGraph [3], a query-aware graph construction method, with Mpjbp=16M_{\mathrm{pjbp}}=16. We conducted experiments on Pony and Psychology using a fixed budget of 200 distance computations. Each entry reports NDCG@10 / Recall@10 under greedy search.

MethodPonyPsychology
Vanilla19.16 / 9.5314.92 / 15.49
Pseudo-query expansion13.18 / 6.774.99 / 6.27
RoarGraph-M1615.65 / 8.5318.20 / 19.83
LGP19.70 / 9.8021.24 / 24.95

As shown in the table, LGP achieves the best NDCG@10 and Recall@10 on both datasets, outperforming both alternatives.

Q3: Lines 186-189: Oracle picks the best of many one-edge variants for each query using ground-truth labels, so it may beat Vanilla even if the variants differ only by chance. Does an edge chosen by Oracle for one query also help other queries?

A: Thanks for your comments. We would like to clarify that Oracle setting used in the section 3 is only for the motivation analysis, not a specific method. It intentionaly selects the best evaluated one-edge variant for each query. This intentionally optimistic comparison straghtforward shows geometry-semantic misalignment and leads to the insights of the following design of LGP. More importantly, LGP does not perform per-query pruning: it refines the graph offline without evaluation queries or relevance labels, and all queries use the same fixed graph. Section 5 evaluates this shared index, demonstrating significant and general gains without per-query Oracle selection.

Q4: Lines 94-95: The "up to 50% fewer distance computations" claim seems to come from Economics only, as stated in Lines 411-413, while in Table 4, LGP at 800 computations is still below Vanilla at 1,600 on average (26.61 vs. 27.11). Could the paper report the per-dataset budget results?

A: Thank you for the comments. The “Up to 50%” refers to the largest reduction we observed for one dataset, not the benchmark average. On Economics and OVEN Task 8, LGP achieves higher NDCG@10 and Recall@10 than Vanilla with half the distance-computation budget (800 versus 1,600). We will include the complete per-dataset budget sweeps in the revision.

Dear Reviewer gNQS,

As the public discussion period is coming to a close tomorrow, we wanted to kindly follow up and ask whether you have any remaining questions or concerns that we could address. We would be happy to provide further clarification. Thank you again for your time and consideration.

Best regards,

The authors

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

This paper aims to improve the retrieval performance of graph-based approximate nearest neighbor search (ANNS). The key idea is to update the edge connections of graph indexes using LLM as a judge for semantic relevance. Experiments are conducted on multiple datasets to test the proposed solution LGP.

Critical strengths

S1. The studied problem ANNS is important for many real-world applications.
S2. The paper proposes a new solution to enhance the edge selection in graph-based vector indexes.
S3. Experiments are conducted on multiple public datasets.

Critical weaknesses

W1. The paper mis-frames a deliberate engineering trade-off as an unaddressed defect.
W2. The motivation experiment is unclear, and its key observation is not novel.
W3. The index construction cost is prohibitive and is not analyzed.
W4. The gains are concentrated in a regime where the method is least needed.
W5. Experiments are conducted mainly on medium-scale datasets.

Questions for authors

Q1. The existence of vector databases and graph-based ANNS indexes is itself a deliberate trade-off: embedding distance is a cheap, precomputable, scalable proxy for semantic relevance, and “ANNS-then-rerank” is a very effective framework to bridge this semantic gap. “Geometry–semantic mismatch” is therefore not a newly discovered defect; it is the known premise on which vector DBs are built.

The paper’s framing implies that this trade-off should be resolved at index-construction time by injecting LLM semantics into graph edges. It does not justify why the trade-off should be resolved there, rather than other alternatives, such as query time via reranking, query rewriting, and multi-vector retrieval. Moreover, the comparison results clearly demonstrate that query time via reranking is sufficiently effective, even compared with LGP.

Q2. The motivation experiment in Section 3 is obscure for two reasons: (1) the parameter configurations of the queries and graph indices are not diverse enough, and (2) changing edges to improve search performance is well known for graph indices. Based on these reasons, many heuristic algorithms have been proposed for neighbor selection in graph indices for ANNS. Unfortunately, neither Section 3 nor the evaluation covers this line of research.

Q3. The data scale is below 200k, which is much smaller than the scale of benchmark datasets (e.g., the Big ANN benchmark) used in prior work. Thus, it is unclear whether the advantage of LGP persists on large-scale datasets.

Q4. Table 3 shows +32.3% greedy search NDCG@10 at width 10 but +1.8% at width 200 on BRIGHT. Table 4 shows +33.2% at 200 distance computations but +0.3% at 3200. A similar pattern also holds for the baseline rerank. The method’s benefit is largest when the search budget is small or the candidate set before reranking is limited. These comparisons demonstrate that reranking is a quite effective method as long as the candidate set is sufficient.

Q5. Table 16 reports 109 minutes for 7,894 nodes and 691 minutes for 52,835 nodes, with more than 96% of the time spent waiting on LLM responses. The index construction time is roughly 58–73× longer than Vanilla’s build time. The paper calls the cost “offline” but does not discuss practical issues:
(1) How to handle dynamic updates, including both insertion and deletion?
(2) Why is the trade-off acceptable in practice?
(3) Whether the gap can be further enlarged on large-scale datasets.

Q6. Section 5 should also evaluate efficiency metrics, such as search latency and QPS. Moreover, it would be better to present QPS–recall and QPS–NDCG curves to illustrate the trade-off.

Q7. Since LGP dramatically increases index construction time, the paper should provide a re-analysis of index-construction complexity, which is currently missing.

11 comments

W1&Q1. The paper mis-frames a deliberate engineering trade-off as an unaddressed defect.

A: Thank you for your comment. We respectfully disagree that this is merely an engineering trade-off. While existing graph indices involve engineering trade-offs, the gap between vector similarity and semantic relevance remains a fundamental scientific problem that our work explicitly investigates and addresses at the graph-index level through LLM-guided edge pruning. First, our experiments show that this gap is substantial and can be effectively reduced by our method. Therefore, even if this gap can be mitigated by existing design choices such as query-time reranking, it is still a limitation that can and should be improved.

Second, as discussed in our paper, addressing this problem at query time is not always ideal. Query-time methods such as reranking introduce additional computational costs, whereas improving the graph at indexing time allows us to return more relevant results directly, without additional query-time overhead. This is especially important when the query-time budget is limited. Also, reranking can only reorder retrieved candidates and it cannot recover relevant documents missing from the candidate set. Moreover, our method remains effective even when reranking is applied, outperforming the baseline with reranking. These results show that improving the index directly provides clear benefits beyond query-time reranking.

W2&Q2. The motivation experiment is unclear, and its key observation is not novel. The motivation experiment in Section 3 is obscure for two reasons: (1) the parameter configurations of the queries and graph indices are not diverse enough, and (2) changing edges to improve search performance is well known for graph indices. Based on these reasons, many heuristic algorithms have been proposed for neighbor selection in graph indices for ANNS. Unfortunately, neither Section 3 nor the evaluation covers this line of research.

A: Thank you for your comments. We clarify that the experiment in Section 3 is intended as a simple motivating example, rather than a comprehensive method and evaluation. We deliberately use a small and controlled setting to clearly illustrate the gap between vector similarity and semantic relevance. We believe the current experiment is sufficient to demonstrate this gap, while adding more configurations would not provide much additional insight into the main observation. To address concerns about robustness and generalization, our main evaluation already includes extensive experiments across different datasets and settings, showing that LGP consistently improves over the baselines. These results further support that the observed gap exists across different settings.

Regarding novelty, we clarify that the purpose of Section 3 is not to propose a new method, but to illustrate the specific problem that motivates our work. We agree that modifying graph edges to improve search performance has been widely studied, and we do not claim this general idea as our contribution. Furthermore, identifying the best "ideal" graph we could ever hope for, is useful because it is about studying the limits of all method. Specifically, Section 3 uses a simple example to highlight the misalignment between vector similarity and semantic relevance, while our proposed method and its technical contributions are presented in Section 4. We will further clarify this distinction and expand our discussion of existing methods in the related work section.

W3&Q5&Q7. The index construction cost is prohibitive and is not analyzed.

A: Thank you for your comments. We agree that LLM inference accounts for most of the construction overhead. However, we respectfully disagree that this cost is necessarily prohibitive in an offline setting. First, in many retrieval systems, low query latency is more important than short indexing time. For stable indices serving many queries, longer construction can be worthwhile when it improves online retrieval performance. This has precedent in industrial systems: [1] report approximately 12 hours of indexing per partition in Taobao's NSG deployment, with an average query response time of 5 ms at 98% precision. Similarly, LGP performs semantic refinement offline, and the resulting graph can serve many queries without additional LLM calls. Therefore, its construction cost can be spread across many queries when the index is infrequently updated. Second, our main goal is to demonstrate that foundation-model semantics can guide graph pruning to improve retrieval quality without adding query-time overhead. While LLM inference is expensive, LGP requires at most one LLM call per refined node. These calls could be processed in parallel to reduce construction time, while techniques such as quantization may further reduce the overhead. Finally, we will add an explicit complexity analysis in the revision. LGP introduces local candidate processing and at most one LLM call per refined node. Under fixed candidate sizes and LLM inference settings, the LLM component scales as O(n)O(n), where nn is the number of refined nodes. Our current work focuses on static graph indices, and we leave efficient support for dynamic insertions and deletions to future work.

W4&Q4. The gains are concentrated in a regime where the method is least needed.

A: Thank you for your comments. We respectfully disagree that LGP is least needed under limited search budgets. In practice, retrieval systems often operate under strict latency constraints. For example, Taobao's retrieval system required responses within 10 ms at 98% precision [1]. LGP directly addresses this practical need by achieving comparable retrieval quality with fewer distance computations. For instance, LGP requires approximately 800 distance computations to achieve the similar quality as Vanilla with 1600 computations. The smaller gains at larger search budgets are therefore expected, as the main benefit of LGP is to achieve high retrieval quality with less computation. Furthermore, LGP's benefits are not limited to vanilla greedy search. As shown in Table 4, LGP also significantly improves NDCG@10 when combined with reranking, outperforming the baseline with reranking. This further demonstrates that LGP provides benefits beyond reducing the search budget.

[1] Fu, Cong, et al. "Fast approximate nearest neighbor search with the navigating spreading-out graph." arXiv preprint arXiv:1707.00143 (2017).

W5&Q3. Experiments are conducted on medium-scale datasets. The data scale is below 200k, which is much smaller

A: Thank you for your comments. We would like to clarify that the claim that all datasets contain fewer than 200K documents is factually incorrect. Our evaluation includes LeetCode from BRIGHT with 413,932 documents and EDIS from M-BEIR with 1,047,067 candidates (Tables 8–9). At a search width of 20, LGP improves greedy-search NDCG@10 over Vanilla by 93.8% and 67.0%, respectively (Tables 1–2). These results provide direct evidence that LGP's benefits extend to larger datasets, including the million-candidate scale.

Q6. Section 5 should also evaluate efficiency metrics, such as search latency and QPS. Moreover, it would be better to present QPS–recall and QPS–NDCG curves to illustrate the trade-off.

A: Thank you for the suggestion. We provide additional results on average search latency, QPS, NDCG@10, and Recall@10 across all 12 BRIGHT datasets. All experiments use the same single-threaded implementation and hardware for each Vanilla–LGP pair. Each entry reports Vanilla / LGP.

Distance budgetLatency (ms) ↓\downarrowQPS ↑\uparrowNDCG@10 ↑\uparrowRecall@10 ↑\uparrow
1000.599 / 0.5991784.8 / 1782.33.96 / 5.022.96 / 4.15
2001.204 / 1.204892.0 / 891.810.50 / 13.9811.62 / 15.60
3001.859 / 1.855572.3 / 574.016.69 / 19.8019.18 / 23.19
8005.096 / 5.073208.0 / 209.025.89 / 26.6130.66 / 31.37
1,60010.259 / 10.191102.5 / 103.127.11 / 27.2732.27 / 32.32
3,20022.018 / 21.87148.0 / 48.427.65 / 27.7432.90 / 32.96

These results show that LGP consistently improves retrieval quality while maintaining nearly identical search latency and QPS. The improvements are particularly clear under smaller distance budgets, where query-time efficiency matters most. We will also include QPS–NDCG and QPS–Recall curves in the revision to make this trade-off clearer.

Dear authors,

I have carefully reviewed the detailed feedback above and appreciate the authors' efforts. However, my major concerns remain unresolved, so I would like to maintain my current scores:

Q1 and Q2: Since the gap can also be addressed by existing techniques, you should at least prove that these techniques are not yet sufficient. That is why my suggestion is to cover more recent techniques (rather than simply ignore them) to convince the readers of your motivation.

Q3: 11 out of 12 datasets in Table 8 and several datasets in Table 9 contain fewer than 200k documents. EDIS is the only dataset in Table 9 that has 1M documents. If you check the Big ANN benchmark, you can easily find large-scale datasets, and many of them have been used as large-scale datasets with 10M–100M objects under the in-memory setting. I think conducting a real large-scale experiment would help answer my question Q5. Unfortunately, there is no additional result, complexity analysis, or even discussion. The only argument is "these (current) results provide direct evidence that LGP's benefits extend to larger datasets", a claim I disagree with (see below).

Q4: I appreciate the clarification, but the Taobao citation does not support the argument as used. Taobao requires 98% precision within 10 ms (i.e., high accuracy under a latency constraint), so the relevant operating point is the high-recall or high-NDCG regime, where LGP's gain is very marginal. Moreover, Table 3 reports Recall@10 and NDCG@10 generally below 40, far from Taobao's required precision. To reduce the distance-computation time spent on Vanilla, many recent techniques can be directly adopted, such as SIMD, DCO, sharding, and even hardware. Again, none of these techniques is evaluated or discussed in the paper.

Q5: Your response confirms my concerns: (1) your solution doesn't support dynamic updates, (2) the offline cost is likely to be significantly enlarged on a real large-scale dataset. What's worse, you use the Taobao case to demonstrate that this offline cost can be spread across many queries (let us suppose this is still true in Taobao, since your cited paper was published in 2017), but it seems that your evaluation protocol didn't follow this practice. Thus, the Taobao analogy remains unvalidated in your setting.

Q6: Although I expected the trade-off results under a fixed search width, the current result is okay for me. However, as shown in the table, when targeting high recall and NDCG (which align with real-world applications), the benefit of LGP over Vanilla is very marginal.

Q7: Index construction complexity is still missing.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.