- 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
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
Rebuttal
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) under fixed inference settings. Graph and embedding storage requires O(n(R+d)) space, where n is the number of nodes, d is the embedding dimension, and R 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=125 to 1, keeping all other settings unchanged. This parameter controls how broadly the algorithm searches for neighbors during graph construction. Setting it to 1 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:
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=16 and evaluate greedy search under a fixed budget of 200 distance computations. Each entry reports NDCG@10 / document Recall@10:
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).