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

arXiv: https://arxiv.org/abs/2609.36359 · HTML: https://mlsanity.com/paper/2609.36359/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 32 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 24 of 24)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Is ChatGPT Good at Search? Investigating Large Language Models as Re-Ranking Agents](https://mlsanity.com/paper/2304.09542/) (2023)
- [Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting](https://mlsanity.com/paper/2306.17563/) (2023)
- [Query Rewriting for Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2305.14283/) (2023)
- [UniIR: Training and Benchmarking Universal Multimodal Information Retrievers](https://mlsanity.com/paper/2311.17136/) (2023)
- [BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrieval](https://mlsanity.com/paper/2407.12883/) (2024)
- [RQ-RAG: Learning to Refine Queries for Retrieval Augmented Generation](https://mlsanity.com/paper/2404.00610/) (2024)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [ReasonIR: Training Retrievers for Reasoning Tasks](https://mlsanity.com/paper/2504.20595/) (2025)
- [RankVicuna: Zero-Shot Listwise Document Reranking with Open-Source Large Language Models](https://mlsanity.com/paper/2309.15088/) (2023)
- [Rank1: Test-Time Compute for Reranking in Information Retrieval](https://mlsanity.com/paper/2502.18418/) (2025)
- [ReasonRank: Empowering Passage Ranking with Strong Reasoning Ability](https://mlsanity.com/paper/2508.07050/) (2025)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [DIVER: A Multi-Stage Approach for Reasoning-intensive Information Retrieval](https://mlsanity.com/paper/2508.07995/) (2025)
- [RaDeR: Reasoning-aware Dense Retrieval Models](https://mlsanity.com/paper/2505.18405/) (2025)
- [REARANK: Reasoning Re-ranking Agent via Reinforcement Learning](https://mlsanity.com/paper/2505.20046/) (2025)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph](https://mlsanity.com/paper/1609.07228/) (2016)
- [AcuRank: Uncertainty-Aware Adaptive Computation for Listwise Reranking](https://mlsanity.com/paper/2505.18512/) (2025)
- [Beyond Sequential Reranking: Reranker-Guided Search Improves Reasoning Intensive Retrieval](https://mlsanity.com/paper/2509.07163/) (2025)
- [With Argus Eyes: Assessing Retrieval Gaps via Uncertainty Scoring to Detect and Remedy Retrieval Blind Spots](https://mlsanity.com/paper/2602.09616/) (2026)

## Abstract (arXiv)

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.