通过(高效的)LLM 引导剪枝改进最近邻图索引

arXiv cs.AI 论文

摘要

本文提出了 LLM 引导的图剪枝(LLM-Guided Graph Pruning,LGP)框架,利用 LLM 推理来优化基于图的 ANN 索引(如 HNSW、DiskANN),通过剪除低价值邻居,解决了这些索引在构建方式与评估方式之间存在的几何—语义不匹配问题,并在端到端检索中超越了传统贪婪搜索与 LLM 重排序方法。

arXiv:2609.36359v1 Announce Type: new 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.
查看原文
查看缓存全文

缓存时间: 2026/09/30 09:44

# Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning
Source: [https://arxiv.org/html/2609.36359](https://arxiv.org/html/2609.36359)
Haike XuAffiliation:MITEmail:[haikexu@mit\.edu](mailto:)Sandeep SilwalAffiliation:University of Wisconsin–MadisonEmail:[silwal@cs\.wisc\.edu](mailto:)

###### 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 unaddressed\. We therefore propose*LLM\-GuidedGraphPruning*\(LGP\), a general framework that addresses this mismatch directly by leveraging LLM reasoning to refine an existing ANN graph index itself\.LGPidentifies “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 thatLGPconsistently 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\. Our code is available at[https://github\.com/fzwark/LGP](https://github.com/fzwark/LGP)

## 1Introduction

Graph\-based Approximate Nearest Neighbor Search \(ANNS\) is a popular and foundational component of modern retrieval systems\([Douze et al\., 2026](https://arxiv.org/html/2609.36359#bib.bib22)\), including retrieval\-augmented search\([Arslan et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib6)\), and is an active area of research in the machine learning, algorithms, and database communities\.111See, e\.g\., the recent VecDB Workshop at VLDB26 \([https://vecdb\-ws\.github\.io/vldb2026/](https://vecdb-ws.github.io/vldb2026/)\)\.At a high level, this family of algorithms constructs a sparse, navigable graph \(i\.e\., one that enables greedy search to efficiently reach points close to a query\) over an input dataset \(e\.g\., documents or images\) during preprocessing, based on the geometric proximity of their embeddings[Malkov and Yashunin \(2020\)](https://arxiv.org/html/2609.36359#bib.bib3);[Jayaram Subramanya et al\. \(2019\)](https://arxiv.org/html/2609.36359#bib.bib5)\. When a query arrives, the prevailing paradigm is to perform a \(highly efficient\) greedy search over this graph based on embedding similarity, followed by a reranking step over the retrieved candidates\. This second step often utilizes a Large Language Model \(LLM\) or a more accurate similarity computation and is much more computationally expensive than the greedy search\([Sun et al\., 2023](https://arxiv.org/html/2609.36359#bib.bib21);[Pradeep et al\., 2023](https://arxiv.org/html/2609.36359#bib.bib12);[Qin et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib20);[Weller et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib17);[Shao et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib10)\)\. However, this reranking step is considered crucial because embeddings alone often fail to fully capture the complex semantic relationships between queries and the input dataset, and thus, a more “powerful” secondary semantic evaluator is necessary for accurate retrieval\([Chan et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib8);[Yao et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib9)\)\.

From this discussion, it is evident that there is a fundamental mismatch between*how graph indices are built and how they are ultimately deployed*\. They are built using embedding\-space geometry due to efficiency constraints, but actual query search requires refining the greedy search using LLMs or expensive similarity measures for the sake of accuracy\. This “geometry–semantic” mismatch is especially problematic under a limited search budget, where graph search can visit only a small fraction of the input dataset\([Yoon et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib18)\)\. Within this budget, the graph search may favor geometrically close but semantically less relevant documents while missing relevant ones\. Even though “post\-hoc” methods such as LLM\-based reranking can partially mitigate this problem, their effectiveness remains constrained by the recall of relevant documents in the initial candidate set\. If a relevant document is never reached initially, even a powerful LLM reranker cannot recover it afterward\. Although increasing the search budget can reduce this “candidate bottleneck”, doing so incurs prohibitive query\-time computation\.

Another possibility is to construct the graph directly according to semantic relationships among documents\. However, evaluating these relationships across a large dataset using expensive measures, such as LLM\-based reasoning, would again incur substantial computational costs\. More importantly, a graph created based on purely semantic relationships may no longer be compatible with the efficient geometric computations used by greedy search at query time\. Then navigating such a graph using greedy search may therefore reduce retrieval accuracy, whereas using stronger semantic measures to guide navigation would substantially increase query\-time latency and cost\.Our paper focuses on addressing this mismatch between geometry\-driven graph construction and downstream semantic retrieval under a constrained search budget\.

Our Results\.To understand how pronounced this mismatch is in practice and whether geometry and semantics can be better balanced in a single graph, we first conduct a controlled and idealized empirical analysis\. Our analysis shows that graph construction based on embeddings alone leaves substantial semantic search potential untapped: changing only a single outgoing edge to a local alternative \(from a two\-hop neighborhood\) can substantially improve ground\-truth recall under the same search budget, while preserving useful geometric properties\. These findings motivate performing targeted, “local” edge updates on top of an existing graph index to better reconfigure its edge connections with semantic relationships, while still preserving efficient navigation\.

Based on these insights, we propose*LLM\-Guided GraphPruning*\(LGP\), a general framework that moves beyond only using reranking at query time and uses LLM\-guided graph refinement*during the index construction itself*\.LGPoperates on top of existing embedding\-based graph indices and makes local edge changes\. At a high level,LGPconstructs a bounded candidate pool from local two\-hop neighborhoods, identifies structurally redundant neighbors that provide little additional reachability capabilities, and judiciously uses LLM reasoning to select candidates that add distinct semantic value beyond the current neighborhood\. These new candidates replace the identified “low\-value” neighbors\. Crucially,LGPis designed to preserve the geometric structure that supports efficient graph search \(i\.e\., navigability\) and leaves the query\-time greedy search procedure unchanged, while making local neighborhoods more semantically informative without sacrificing sparsity or introducing additional LLM inference at query time\. Furthermore, since it modifies only the graph index, it can be seamlessly integrated into existing retrieve\-then\-rerank pipelines\.

To show its versatility, we instantiateLGPon two widely used graph\-based ANN indices, DiskANN\([Jayaram Subramanya et al\., 2019](https://arxiv.org/html/2609.36359#bib.bib5)\)and HNSW\([Malkov and Yashunin, 2020](https://arxiv.org/html/2609.36359#bib.bib3)\), although the framework can be applied more broadly to other graph\-based ANN methods\. Extensive experiments demonstrate thatLGPaddresses limitations of prior embedding\-based graph constructions and improves end\-to\-end retrieval performance\. Specifically, relative to the vanilla baseline,LGPimproves average greedy\-search NDCG@10 by24\.4%on the textual BRIGHT and11\.7%on the multimodal M\-BEIR, with the improvements reaching26\.0%and13\.2%after reranking, respectively\. Furthermore,LGPsubstantially improves search efficiency, achieving comparable retrieval quality with up to50% fewer distance computations\. To summarize, our main contributions are:

1. 1\.We identify and formulate a fundamental*geometry–semantic mismatch*in graph\-based ANN retrieval, where graph indices are constructed based on embedding\-space geometry, while downstream retrieval is ultimately evaluated by semantic relevance\.
2. 2\.Through controlled one\-edge replacements, we empirically show that geometrically comparable edge choices give substantially different ground\-truth recall during search, revealing the potential for better trade\-offs between geometric navigation and semantic retrieval in a single graph\.
3. 3\.Guided by these findings, we proposeLGP, an offline graph\-refinement framework that selectively replaces structurally low\-value neighbors with LLM\-selected alternatives that provide more useful semantic connections, while leaving the query\-time search procedure unchanged\.
4. 4\.We instantiateLGPon two widely used graph\-based ANN indices, DiskANN and HNSW, and demonstrate consistent retrieval improvements across semantic retrieval benchmarks while preserving graph sparsity and achieving comparable retrieval quality with up to 50% fewer distance computations\.

## 2Preliminaries

Graph\-based approximate nearest neighbor search \(ANNS\) methods build sparse navigable graphs over dense vector representations to support efficient retrieval\([Jayaram Subramanya et al\., 2019](https://arxiv.org/html/2609.36359#bib.bib5);[Malkov and Yashunin, 2020](https://arxiv.org/html/2609.36359#bib.bib3)\)\. Here, navigability refers to the ability of greedy graph search to efficiently reach nodes that are close to a query in embedding space\. Given a corpus𝒟=\{d1,…,d\|𝒟\|\}\\mathcal\{D\}=\\\{d\_\{1\},\\dots,d\_\{\|\\mathcal\{D\}\|\}\\\}, each documentdi∈𝒟d\_\{i\}\\in\\mathcal\{D\}is encoded by a bi\-encoder into an embedding vector𝒆⁡\(di\)\\bm\{e\}\(d\_\{i\}\)\. A graph\-based ANN index is represented as a directed graphG=\(V,E\)G=\(V,E\), where each nodevi∈Vv\_\{i\}\\in Vcorresponds to a documentdid\_\{i\}, and\(vi,vj\)∈E\(v\_\{i\},v\_\{j\}\)\\in Edenotes a directed edge fromviv\_\{i\}tovjv\_\{j\}\. We useN⁡\(i\)=\{vj:\(vi,vj\)∈E\}N\(i\)=\\\{v\_\{j\}:\(v\_\{i\},v\_\{j\}\)\\in E\\\}to denote the outgoing neighborhood ofviv\_\{i\}with degree boundRR\. We useD⁡\(⋅,⋅\)D\(\\cdot,\\cdot\)to denote the embedding\-space distance \(e\.g\., cosine distance\) between two nodes or between a query and a node\.

Although graph\-based ANN indices differ in construction details, most follow a common pattern\. For each nodeviv\_\{i\}, the index first retrieves a candidate setUiU\_\{i\}through graph traversal or local search, then applies an index\-specific neighbor\-selection rule to form the outgoing neighborhoodN⁡\(i\)N\(i\)under degree limitRR\. For example, DiskANN uses geometric pruning on a flat graph, while HNSW combines hierarchical search with heuristic neighbor selection\.222Detailed algorithms for DiskANN and HNSW are provided in[AppendixD](https://arxiv.org/html/2609.36359#A4)\.In both cases, construction is based on embedding\-space geometry rather than explicit semantic relationships among documents\.

At query time, a queryqqis encoded as𝒆⁡\(q\)\\bm\{e\}\(q\)and greedy search is performed overGG\. Starting from an entry node, the search repeatedly expands promising frontier nodes according to their embedding\-space distance toqqand evaluates their outgoing neighbors\. We count each evaluation of the embedding\-space distance betweenqqand a previously unseen node as one query–node distance computation\. Under a finite computation budget, the search explores only part of the graph, producing candidates that are either returned directly or passed to a downstream reranker\.

Other Related Work on LLM\-Augmented and Query\-Time Retrieval Algorithms\.A separate line of work improves retrieval quality by adding stronger semantic reasoning at inference time, including query rewriting, reasoning\-aware retrievers, and reranking methods\([Ma et al\., 2023](https://arxiv.org/html/2609.36359#bib.bib26);[Chan et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib8);[Shao et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib10);[Zhang et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib24);[Liu et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib23)\)\. Other recent methods modify graph search itself: bi\-metric search uses a cheap proxy metric for indexing while adapting query\-time search toward a more expensive target metric\([Xu et al\., 2026](https://arxiv.org/html/2609.36359#bib.bib34)\), and RGS alters graph traversal to decide which candidates should be evaluated by a stronger reranker under a limited budget\([Xu and Chen, 2026](https://arxiv.org/html/2609.36359#bib.bib19)\)\. These approaches are complementary to ours: they primarily improve how a fixed graph is queried online, whereas our method improves the graph structure itself offline\. Thus, our refined graph remains compatible with standard greedy search and a broad class of query\-time retrieval algorithms that incorporate stronger semantic reasoning\. See extended related work in[AppendixF](https://arxiv.org/html/2609.36359#A6)\.

## 3Motivation: The Geometry–Semantic Mismatch

Figure 1:Alternate one\-edge replacements reveal a substantial geometry–semantic mismatch and potential for improvement\. Across both additional budgetsCCand initial budgetsPP,*Oracle*consistently achieves higher ground\-truth recall than*Vanilla*, while*Uniform*is close to*Vanilla*\.Embedding\-based graph indices connect each document to a small set of geometrically close neighbors, which may not align with its underlying semantic relationships\. This creates a mismatch because geometrically preferred edges are not necessarily the most useful for semantic retrieval\. It is therefore important to empirically investigate and quantify how pronounced this mismatch is in practice\. Furthermore, sparse ANN indices generally allow multiple edge choices that are similar under the geometric constraints used to build the index, so we naturally ask: can some of these alternative edge choices be a better fit with semantic relationships, and if so, to what extent? To this end, we design a controlled setup where we modify only a single edge of the vanilla index using alternatives from a bounded candidate set under the same geometric constraints\. This tests whether vanilla geometric construction leaves room for improving semantic retrieval without violating existing geometric constraints, and whether geometry and semantics can be balanced within a single graph\.

One\-Edge Replacement\.Specifically, for each queryqqand initial search budgetPP, we run greedy search on the Vanilla DiskANN graph until at leastPPunique embedding\-space distance computations have been performed, and save the search immediately before the next frontier nodeviv\_\{i\}is expanded\. LetN⁡\(i\)N\(i\)denote the outgoing neighbors ofviv\_\{i\}, and letN2​\(i\)N\_\{2\}\(i\)denote its two\-hop non\-neighbors:N2​\(i\)=\(⋃vj∈N⁡\(i\)N⁡\(j\)\)∖\(N⁡\(i\)∪\{vi\}\)\.N\_\{2\}\(i\)=\\left\(\\bigcup\_\{v\_\{j\}\\in N\(i\)\}N\(j\)\\right\)\\setminus\\left\(N\(i\)\\cup\\\{v\_\{i\}\\\}\\right\)\.Starting from this same point, for everyz∈N⁡\(i\)z\\in N\(i\)andc∈N2​\(i\)c\\in N\_\{2\}\(i\), we construct a one\-edge variant of the graph by replacing\(vi,z\)\(v\_\{i\},z\)with\(vi,c\)\(v\_\{i\},c\)and continue the greedy search for an additional budget ofCCquery–document distance computations\. By varying bothPPandCC, we examine whether a single local edge change can improve relevant\-document discovery across different stages of the search and different search budgets\.

Measuring the Geometry–Semantic Gap\.For each queryqqand each pair of initial and additional search budgets\(P,C\)\(P,C\), we evaluate the vanilla graph and every one\-edge variant by the fraction of ground\-truth relevant documents,GT⁡\(q\)\\operatorname\{GT\}\(q\), reached after the additionalCCdistance computations\. Specifically, for queryqqand graphGG, let𝒟Gseen​\(q,P,C\)\\mathcal\{D\}^\{\\mathrm\{seen\}\}\_\{G\}\(q,P,C\)denote the documents evaluated during the initialPPdistance computations together with those evaluated during the additionalCCcomputations\. We measure ground\-truth recall as

\|𝒟Gseen​\(q,P,C\)∩GT⁡\(q\)\|\|GT⁡\(q\)\|\.\\frac\{\\left\|\\mathcal\{D\}^\{\\mathrm\{seen\}\}\_\{G\}\(q,P,C\)\\cap\\operatorname\{GT\}\(q\)\\right\|\}\{\\left\|\\operatorname\{GT\}\(q\)\\right\|\}\.\(1\)To preserve the geometric constraints of the original graph, we keep only one\-edge variants whose recall of the exact top\-10 embedding\-space neighbors ofqqis no worse than that of the vanilla graph under the same\(P,C\)\(P,C\)budgets\. For each query and budget setting, we define the variant with the highest ground\-truth recall as*Oracle*and compare it with*Vanilla*to quantify the potential improvement under the same geometric constraints\. As a control, we report the average recall across all such one\-edge variants as the*Uniform*baseline\.

Geometry Leaves Semantic Retrieval Potential Untapped\.We conduct this analysis on three BRIGHT datasets, Biology, StackOverflow, and Psychology, using DiskANN as the underlying graph index\([SU et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib7)\)\. As shown in Figure[1](https://arxiv.org/html/2609.36359#S3.F1),*Oracle*consistently outperforms*Vanilla*in ground\-truth recall across varyingCCat fixedP=100P=100and varyingPPat fixedC=64C=64\. This consistent gap confirms that geometrically comparable edge choices can differ substantially in their semantic retrieval performance, directly demonstrating a substantial geometry–semantic mismatch in practice\. More importantly, these results indicate that graph construction based on embeddings alone leaves substantial potential for improving semantic relevance while satisfying the same geometric constraints\. Furthermore, the near\-zero improvement of*Uniform*shows that arbitrary one\-edge replacements do not perform well, and that realizing this potential requires selecting semantically useful alternatives\. These findings suggest that geometry and semantics can be combined and “harmonized” within a single graph and motivate our method,LGP, which selectively prunes local edges on top of the existing geometric index to incorporate more semantically useful connections\.

## 4Our Framework: LLM\-Guided Graph Pruning

Algorithm 1LLM\-Guided Graph Pruning \(LGP\)1:InputANN graph

GG, current node

viv\_\{i\}, neighborhood

N⁡\(i\)N\(i\), and index\-specific candidate set

UiU\_\{i\}
2:ParametersDegree cap

RR, shortlist budget

MM, and edit budget

BB
3:

⊳\\triangleright/\* Form a local replacement set \*/

4:

Ui←UiU\_\{i\}\\leftarrow U\_\{i\}together with directed two\-hop non\-neighbors of

viv\_\{i\}
5:

⊳\\triangleright/\* Shortlist local replacement candidates \*/

6:

Ui←U\_\{i\}\\leftarrowshortlist up to

MMcandidates based on additional two\-hop reachability and redundancy with

N⁡\(i\)N\(i\)
7:

⊳\\triangleright/\* Select semantically useful candidates with an LLM \*/

8:

𝒜i←LLMSelect​\(vi,N⁡\(i\),Ui,B\)\\mathcal\{A\}\_\{i\}\\leftarrow\\textsc\{LLMSelect\}\(v\_\{i\},N\(i\),U\_\{i\},B\)
9:

⊳\\triangleright/\* Local edge pruning and replacement \*/

10:foreach

vc∈𝒜iv\_\{c\}\\in\\mathcal\{A\}\_\{i\}do

11:Identify an existing neighbor

vwv\_\{w\}with little additional reachability and high redundancy

12:Update

N⁡\(i\)N\(i\)by adding

vcv\_\{c\}and, when necessary, removing

vwv\_\{w\}to satisfy the degree constraint

To address the geometry–semantic mismatch while preserving efficient graph navigation, we introduce*LLM\-GuidedGraphPruning*\(LGP\), a general framework for refining an existing ANN index by making its local neighborhoods better aligned with semantic relationships \([Algorithm1](https://arxiv.org/html/2609.36359#alg1)\)\. Rather than replacing the original indexing algorithm,LGPoperates on top of the existing graph index \(e\.g\., DiskANN and HNSW\), identifies neighbors that provide little additional reachability beyond the rest of the local neighborhood, and replaces them with LLM\-selected candidates that can help the search reach more relevant documents without violating the geometric constraints of the original index\. For each node in the index, our algorithm proceeds in three main steps\. First, it constructs a small set of local replacement candidates using directed two\-hop non\-neighbors\. It then uses efficient to compute “structural” signals, including additional two\-hop reachability and neighborhood redundancy, to shortlist promising candidates\. From this shortlist, LLM reasoning is used to select semantically useful alternatives\. Finally, the selected candidates are added to the neighborhood by replacing existing neighbors with little additional reachability and high redundancy\. A detailed version of the algorithm is provided in[Algorithm8](https://arxiv.org/html/2609.36359#alg8)in the appendix\.

Efficient Local Candidate Set Construction\.Given an ANN indexGG, for each nodeviv\_\{i\},LGPconsiders only a small set of local replacement candidates rather than all nodes in the graph\. Since most graph\-based ANN methods already produce a candidate set of geometrically close neighbors when selecting or updating the outgoing neighborhoodN⁡\(i\)N\(i\)ofviv\_\{i\},LGPreuses this set, denoted byUiU\_\{i\}, and augments it with directed two\-hop non\-neighbors, i\.e\., nodes reachable through a current neighbor but not already directly connected toviv\_\{i\}\. This provides a broader set of local alternatives from which the LLM can identify semantically useful replacements, while keeping candidate construction computationally inexpensive\. To further control the cost and context length of LLM selection,LGPprunes the augmented set to at mostMMcandidates using only graph connectivity and embedding distances, without invoking the LLM\. The pruning favors candidates that provide greater additional two\-hop reachability and are less redundant with the current neighborhood \(lines 7–15 in[Algorithm8](https://arxiv.org/html/2609.36359#alg8)\)\.

LLM\-Guided Semantic Selection\.From the shortlisted setUiU\_\{i\},LGPuses an LLM to identify replacement candidates that add useful semantic information beyond what is already represented in the current neighborhood\. The LLM is given the document represented byviv\_\{i\}, a small set of its current neighbors as context, and the documents in the shortlisted setUiU\_\{i\}\. It selects up toBBcandidates that extend rather than repeat the information already available through the current neighborhood, for example, by providing missing supporting context or connectingviv\_\{i\}to a related concept that is not well represented by its existing neighbors\. Here,BBis a small per\-node edit budget that limits the number of edge changes \(e\.g\.,B=2B=2\)\. Prompts forLLMSelectare provided in[AppendixC](https://arxiv.org/html/2609.36359#A3)\.

Figure 2:LGP\-refined DiskANN consistently improves recall over Vanilla across distance\-computation budgets\.Local Edge Replacement\.After LLM\-guided selection,LGPapplies a lightweight structural check to keep candidates that provide sufficient additional reachability\. Such a candidate is added directly when the neighborhood is below the degree limit\. Otherwise,LGPreplaces an existing neighbor that provides little additional two\-hop reachability beyond the other neighbors and is highly redundant with the current neighborhood\. This allowsLGPto introduce more semantically useful connections while preserving the sparsity and local geometric structure of the original index\.

Instantiation for Representative ANN Indices\.LGPis general and can be instantiated on different graph\-based ANN indices, including DiskANN and HNSW\. In DiskANN,LGPis applied immediately after RobustPrune during the second construction pass, taking the nodes visited by GreedySearch asUiU\_\{i\}\. In HNSW,LGPrefines only the base layer of the constructed index, taking the base\-layer nodes visited by hierarchical search asUiU\_\{i\}\. Both instantiations follow the shared pruning procedure in[Algorithm1](https://arxiv.org/html/2609.36359#alg1), with detailed algorithms provided in[SectionE\.1](https://arxiv.org/html/2609.36359#A5.SS1)\.

LGPRealizes the Semantic Improvement Potential\.To examine whether the improvement potential identified by the controlled one\-edge analysis in[Section3](https://arxiv.org/html/2609.36359#S3)can be realized byLGP, we compare the fixedLGP\-refined DiskANN index directly against the original vanilla index across total distance\-computation budgets\. As shown in[Figure2](https://arxiv.org/html/2609.36359#S4.F2),LGPconsistently achieves higher ground\-truth recall than*Vanilla*across all tested budgets and datasets\. These results show that the potential revealed by the one\-edge analysis translates into consistent retrieval gains withLGP, demonstrating that semantic relevance and geometric constraints can be better balanced within a single graph\.

## 5Empirical Results

Table 1:BRIGHT main results on DiskANN at search width 20 using Diver embeddings\. Each entry reports Vanilla /LGP\.Greensubscripts denote relative improvements over Vanilla\.Greedy searchRerankDatasetNDCG@10Recall@10NDCG@10Recall@10Biology24\.69 /37\.06\+50\.1%28\.66 /44\.63\+55\.7%28\.30 /41\.57\+46\.9%30\.71 /46\.19\+50\.4%Earth Science20\.60 /27\.92\+35\.5%22\.70 /30\.59\+34\.8%23\.29 /30\.06\+29\.1%25\.51 /33\.03\+29\.5%Economics19\.56 /22\.35\+14\.3%20\.77 /25\.61\+23\.3%19\.98 /25\.42\+27\.2%21\.92 /28\.84\+31\.6%Psychology28\.31 /34\.76\+22\.8%34\.51 /41\.61\+20\.6%32\.78 /41\.46\+26\.5%34\.40 /44\.10\+28\.2%Robotics19\.48 /21\.68\+11\.3%24\.83 /27\.12\+9\.2%25\.67 /28\.63\+11\.5%28\.61 /31\.16\+8\.9%StackOverflow10\.82 /17\.36\+60\.4%13\.87 /21\.37\+54\.1%11\.96 /19\.61\+64\.0%14\.66 /23\.73\+61\.9%Sustainable Living18\.09 /24\.33\+34\.5%22\.12 /29\.76\+34\.5%20\.20 /27\.43\+35\.8%22\.04 /30\.82\+39\.8%Pony17\.08 /17\.80\+4\.2%9\.06 /9\.40\+3\.8%19\.54 /20\.07\+2\.7%9\.73/ 9\.00LeetCode3\.20 /6\.20\+93\.8%4\.54 /9\.51\+109\.5%2\.97 /6\.37\+114\.5%4\.27 /10\.07\+135\.8%AoPS3\.13 /3\.36\+7\.3%4\.58 /5\.03\+9\.8%3\.12 /3\.23\+3\.5%4\.69 /4\.79\+2\.1%TheoremQA\-Theorems34\.70 /36\.35\+4\.8%46\.26 /47\.57\+2\.8%33\.57 /36\.44\+8\.5%45\.60 /48\.89\+7\.2%TheoremQA\-Questions5\.73 /6\.45\+12\.6%8\.24 /8\.36\+1\.5%5\.63 /5\.68\+0\.9%9\.24 /9\.49\+2\.7%Average17\.12 /21\.30\+24\.4%20\.01 /25\.05\+25\.2%18\.92 /23\.83\+26\.0%20\.95 /26\.68\+27\.4%We comprehensively evaluateLGPon textual and multimodal benchmarks using DiskANN and HNSW\. Across settings,LGPconsistently improves greedy\-search retrieval, and these gains persist after downstream reranking\. The improvements are most pronounced at narrow search widths\.

Benchmarks and Models\.We use BRIGHT\([SU et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib7)\)for reasoning\-intensive text retrieval and M\-BEIR\([Wei et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib13)\)for multimodal retrieval\. BRIGHT contains 12 datasets spanning diverse domains, while M\-BEIR contains 16 tasks covering text, image, and image–text retrieval\. We evaluate all BRIGHT queries and, following[Xu and Chen \(2026\)](https://arxiv.org/html/2609.36359#bib.bib19), uniformly sample 100 queries per M\-BEIR task using the same samples across all experiments\. For BRIGHT, we use Diver\-Retriever\-4B\-1020\([Sun et al\., 2026](https://arxiv.org/html/2609.36359#bib.bib11)\)and Qwen3\-Embedding\-4B as embedding models\. For M\-BEIR, following[Xu and Chen \(2026\)](https://arxiv.org/html/2609.36359#bib.bib19), we use CLIP \(ViT\-B/32\)\([Radford et al\., 2021](https://arxiv.org/html/2609.36359#bib.bib16)\)to encode all 16 task subsets\. For LLM\-guided semantic selection and downstream reranking, we use Qwen3\-32B\([Team, 2025](https://arxiv.org/html/2609.36359#bib.bib14)\)on BRIGHT and Qwen3\-VL\-30B\-A3B\-Instruct\([Bai et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib15)\)on M\-BEIR, both in non\-reasoning mode\. Detailed benchmark and model configurations are provided in[Tables8](https://arxiv.org/html/2609.36359#A0.T8),[9](https://arxiv.org/html/2609.36359#A0.T9)and[10](https://arxiv.org/html/2609.36359#A0.T10)\.

Index Configurations\.Our primary ANN index is DiskANN, with a maximum out\-degree of 16, a construction search width of 125, and a pruning parameter of 1\.2\. We additionally evaluate HNSW with connectivity 16 and construction search width 200\. We use an edit budget ofB=2B=2for both benchmarks, with a shortlist size ofM=24M=24on BRIGHT andM=12M=12on M\-BEIR\.

Retrieval Configurations and Metrics\.At query time, we evaluate greedy graph search and downstream reranking\. We use*search width*, the standard query\-time parameter for controlling search effort in graph\-based ANN indices, corresponding toLsearchL\_\{\\mathrm\{search\}\}in DiskANN ande​fsearchef\_\{\\mathrm\{search\}\}in HNSW\. With graph degree bounded byRR, the query\-time search cost grows roughly withsearch width×R\\text\{search width\}\\times Rin terms of distance computations\. For DiskANN, we varyLsearch∈\{10,20,50,100,200\}L\_\{\\mathrm\{search\}\}\\in\\\{10,20,50,100,200\\\}; for HNSW, we varye​fsearch∈\{10,12,14,16,18,20,50\}ef\_\{\\mathrm\{search\}\}\\in\\\{10,12,14,16,18,20,50\\\}, using 20 by default\. Greedy search returns candidate documents ordered by embedding distance\. We either evaluate the topkkdirectly or rerank the same candidate set before evaluating the resulting topkk\. We report NDCG@kkand document\-level Recall@kkfork∈\{5,10\}k\\in\\\{5,10\\\}on a 0–100 scale\. Recall@kkis the fraction of all ground\-truth documents that appear in the topkk, averaged over queries\. When a query has more thankkground\-truth documents, the maximum possible Recall@kkis below 100\. Full details are provided in[AppendixA](https://arxiv.org/html/2609.36359#A1)\.

Table 2:M\-BEIR results on DiskANN at search width 20 using CLIP\. Each entry reports Vanilla/LGP\.Greedy searchRerankDataset \(Task\)NDCG@10Recall@10NDCG@10Recall@10VisualNews \(0\)16\.41/ 15\.4521\.00/ 20\.0015\.23 /15\.97\+4\.9%21\.00 / 21\.00MSCOCO \(0\)32\.45 /32\.88\+1\.3%51\.00 /52\.00\+2\.0%45\.09 /46\.09\+2\.2%56\.00 /57\.00\+1\.8%Fashion200K \(0\)1\.80 /1\.82\+1\.1%2\.63 / 2\.634\.53/ 3\.564\.97/ 3\.97WebQA \(1\)5\.99 /6\.61\+10\.4%7\.50 /8\.00\+6\.7%8\.29 /8\.93\+7\.7%8\.00 /9\.00\+12\.5%EDIS \(2\)6\.76 /11\.29\+67\.0%9\.07 /14\.74\+62\.5%11\.02 /15\.67\+42\.2%12\.80 /18\.71\+46\.2%WebQA \(2\)15\.15 /22\.97\+51\.6%20\.50 /29\.50\+43\.9%20\.25 /29\.18\+44\.1%23\.50 /33\.50\+42\.6%VisualNews \(3\)3\.87 /7\.04\+81\.9%9\.00 /14\.00\+55\.6%5\.25 /10\.29\+96\.0%11\.00 /19\.00\+72\.7%MSCOCO \(3\)42\.42 /43\.00\+1\.4%42\.60 /42\.80\+0\.5%52\.63 /53\.92\+2\.5%49\.20 /49\.80\+1\.2%Fashion200K \(3\)2\.93/ 2\.866\.00 / 6\.003\.97 /4\.00\+0\.8%6\.00 / 6\.00NIGHTS \(4\)28\.73 / 28\.7351\.00 / 51\.0041\.99 /42\.51\+1\.2%61\.00 / 61\.00OVEN \(6\)0\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.00InfoSeek \(6\)0\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.00CIRR \(7\)6\.47 /7\.83\+21\.0%13\.00 /16\.00\+23\.1%10\.99 /12\.34\+12\.3%13\.00 /15\.00\+15\.4%FashionIQ \(7\)0\.67 /1\.12\+67\.2%2\.00 /3\.00\+50\.0%1\.61 /3\.66\+127\.3%4\.00 /6\.00\+50\.0%OVEN \(8\)0\.50 /1\.35\+170\.0%0\.75 /2\.08\+177\.3%1\.16 /3\.09\+166\.4%0\.75 /2\.08\+177\.3%InfoSeek \(8\)0\.48 /0\.93\+93\.8%1\.00 /1\.58\+58\.0%0\.45 /2\.53\+462\.2%1\.00 /2\.31\+131\.0%Average10\.29 /11\.49\+11\.7%14\.82 /16\.46\+11\.1%13\.90 /15\.73\+13\.2%17\.01 /19\.02\+11\.8%Table 3:Search\-width sweeps on BRIGHT and M\-BEIR with Diver and CLIP embeddings, respectively\.Greensubscripts denote relative improvements over the Vanilla baseline\.Grayvalues denote the average exact\-kkNN NDCG@10 / Recall@10 for each benchmark\.Benchmark\(ExactkkNN ref\.\)SearchwidthGreedy searchRerankNDCG@10Recall@10NDCG@10Recall@10VanillaLGPVanillaLGPVanillaLGPVanillaLGPBRIGHT\(28\.50 / 34\.18\)1011\.9015\.74\+32\.3%13\.5318\.27\+35\.0%13\.0117\.28\+32\.8%13\.5318\.27\+35\.0%2017\.1221\.30\+24\.4%20\.0125\.05\+25\.2%18\.9223\.83\+26\.0%20\.9526\.68\+27\.4%5023\.0925\.03\+8\.4%27\.4329\.51\+7\.6%26\.3128\.47\+8\.2%29\.9532\.56\+8\.7%10026\.1026\.87\+3\.0%31\.0531\.73\+2\.2%30\.2431\.28\+3\.4%34\.9435\.61\+1\.9%20026\.9427\.42\+1\.8%32\.1032\.47\+1\.2%31\.6432\.17\+1\.7%37\.1337\.66\+1\.4%M\-BEIR\(16\.16 / 22\.87\)109\.089\.47\+4\.3%13\.0713\.69\+4\.7%11\.0011\.49\+4\.5%13\.0713\.69\+4\.7%2010\.2911\.49\+11\.7%14\.8216\.46\+11\.1%13\.9015\.73\+13\.2%17\.0119\.02\+11\.8%5012\.9913\.68\+5\.3%18\.2819\.19\+5\.0%19\.0020\.17\+6\.2%22\.8124\.01\+5\.3%10014\.0014\.66\+4\.7%19\.6020\.47\+4\.4%20\.9322\.00\+5\.1%25\.6627\.08\+5\.5%20014\.8215\.23\+2\.8%20\.6221\.25\+3\.1%22\.2022\.68\+2\.2%27\.3027\.77\+1\.7%Main Results\.As shown in[Table1](https://arxiv.org/html/2609.36359#S5.T1),LGPimproves both greedy\-search and reranked NDCG@10 across all 12 BRIGHT datasets at the search width of 20\. Under greedy search,LGPincreases average NDCG@10 from 17\.12 to 21\.30 \(\+24\.4%\) and Recall@10 from 20\.01 to 25\.05 \(\+25\.2%\)\. Biology shows the largest absolute NDCG@10 gain, increasing from 24\.69 to 37\.06 \(\+50\.1%\)\. These gains persist after LLM reranking, where average NDCG@10 increases from 18\.92 to 23\.83 \(\+26\.0%\) and Recall@10 from 20\.95 to 26\.68 \(\+27\.4%\)\. As shown in[Table2](https://arxiv.org/html/2609.36359#S5.T2), across 16 M\-BEIR tasks,LGPimproves average NDCG@10 by11\.7%under greedy search and13\.2%after VLM reranking, with reranked Recall@10 improving by11\.8%\. WebQA Task 2 shows the largest NDCG@10 gains, improving by51\.6%under greedy search and44\.1%after reranking\. These results show thatLGPrefines the index with connections that better reflect semantic relationships, improving graph\-search retrieval and downstream reranking across both text and multimodal settings\.

Figure 3:Search\-width sweeps on 6 BRIGHT datasets using Diver embeddings\.LGPconsistently outperforms Vanilla under both greedy search and LLM reranking across search widths\.Table 4:Distance\-computation\-budget sweeps on BRIGHT using Diver embeddings\.Benchmark\(ExactkkNN ref\.\)ComputationbudgetGreedy searchRerankNDCG@10Recall@10NDCG@10Recall@10VanillaLGPVanillaLGPVanillaLGPVanillaLGPBRIGHT\(28\.50 / 34\.18\)1003\.965\.02\+26\.9%2\.964\.15\+40\.0%4\.285\.40\+26\.1%3\.074\.12\+34\.3%20010\.5013\.98\+33\.2%11\.6215\.60\+34\.3%11\.6715\.41\+32\.0%12\.3216\.40\+33\.1%30016\.6919\.80\+18\.6%19\.1823\.19\+20\.9%18\.7022\.46\+20\.1%20\.3524\.61\+21\.0%50022\.9224\.57\+7\.2%27\.1428\.83\+6\.2%26\.0427\.79\+6\.7%28\.7030\.82\+7\.4%80025\.8926\.61\+2\.8%30\.6631\.37\+2\.3%29\.0029\.92\+3\.2%32\.5933\.54\+2\.9%160027\.1127\.27\+0\.6%32\.2732\.32\+0\.2%30\.8330\.95\+0\.4%34\.6334\.71\+0\.2%320027\.6527\.74\+0\.3%32\.9032\.96\+0\.2%31\.2631\.28\+0\.1%35\.1535\.18\+0\.1%

Table 5:Cross\-index evaluation ofLGPon HNSW over BRIGHT datasets with Diver embeddings at search width 20\. Each entry reports Vanilla /LGP\.Greedy searchRerankDatasetNDCG@5NDCG@10Recall@5Recall@10NDCG@5NDCG@10Recall@5Recall@10TheoremQA\-Theorems38\.64 /39\.4742\.39 /43\.3445\.05 /45\.7154\.81 /56\.1238\.26 /40\.7641\.85 /43\.5244\.86 /48\.1555\.47 /56\.12Biology42\.71/ 42\.1948\.06/ 47\.3942\.13/ 41\.4057\.25/ 56\.0950\.85 /52\.8354\.67 /55\.7448\.63 /49\.2059\.90/ 58\.90Pony14\.84 /17\.1112\.83 /14\.483\.83 /4\.366\.71 /8\.0417\.82 /19\.9214\.80 /16\.284\.72 /5\.627\.37 /8\.78

Table 6:Embedding robustness on BRIGHT using Qwen3\-Embedding at search width 20\. Results are averaged equally over all 12 datasets\.NDCG@5NDCG@10Recall@5Recall@10RetrievalVanillaLGPVanillaLGPVanillaLGPVanillaLGPGreedy search10\.8912\.33\+13\.2%12\.0413\.81\+14\.7%11\.5213\.06\+13\.4%15\.3417\.60\+14\.7%LLM rerank15\.9118\.19\+14\.3%16\.3418\.70\+14\.4%15\.3117\.37\+13\.5%18\.1920\.66\+13\.6%Table 7:Ablations of model size \(left\) and graph degree \(right\) on Pony and Psychology using Diver embeddings at search width 20\. Entries report NDCG@10\.Greedy searchLLM rerankingDatasetModelVanillaLGPVanillaLGPPonyQwen3\-8B17\.0817\.0019\.5419\.83Qwen3\-32B17\.0817\.8019\.5420\.07PsychologyQwen3\-8B28\.3129\.8232\.5534\.75Qwen3\-32B28\.3134\.7632\.6941\.46
Greedy searchLLM rerankingDatasetRRVanillaLGPVanillaLGPPony85\.089\.805\.0810\.081617\.0817\.8019\.5420\.073215\.8716\.2818\.9719\.52Psychology86\.7418\.527\.7122\.681628\.3134\.7632\.6941\.463237\.6636\.2245\.1743\.78

Search Width\.To assess how the benefits ofLGPvary with query\-time search width, we evaluate performance across different widths\.[Table3](https://arxiv.org/html/2609.36359#S5.T3)shows thatLGPachieves its largest gains on BRIGHT at narrower widths: at width 10, average NDCG@10 improves by32\.3%under greedy search and32\.8%after LLM reranking, while remaining consistently better than Vanilla as the search width increases\. The per\-dataset curves in[Figure3](https://arxiv.org/html/2609.36359#S5.F3)exhibit the same pattern\. On M\-BEIR,LGPimproves average NDCG@10 under both greedy search and reranking at every tested width\. The task\-level results in[Figure8](https://arxiv.org/html/2609.36359#A1.F8)\(Appendix\) further show consistent gains across individual M\-BEIR tasks\. Furthermore, compared with Vanilla,LGPapproaches the exactkkNN faster as the search width increases and remains consistently closer to exact retrieval on both benchmarks\. These results show thatLGPprovides its strongest gains at narrower search widths while remaining consistently beneficial as the search width increases\. Dataset\-wise sweeps are provided in[SectionB\.1](https://arxiv.org/html/2609.36359#A2.SS1)\.

Explicit Distance\-Computation Budgets\.Search width is the standard control for query\-time search effort, while explicit distance\-computation budgets provide a complementary matched\-compute view\. We therefore compare Vanilla andLGPunder the same limit on the number of query–document distance computations\. As shown in[Table4](https://arxiv.org/html/2609.36359#S5.T4),LGPconsistently outperforms Vanilla across all tested budgets, with the largest gains at smaller and intermediate budgets\. At a budget of 200,LGPimproves greedy NDCG@10 and Recall@10 by33\.2%and34\.3%, respectively\. Moreover, on Economics from BRIGHT,LGPreaches the same greedy NDCG@10 as Vanilla using roughly 50% fewer distance computations \(800 vs\. 1,600\)\. These results demonstrate thatLGPimproves search efficiency by achieving higher retrieval quality for the same computation and comparable quality with*substantially fewer distance evaluations*\. Additional results are provided in[SectionB\.6](https://arxiv.org/html/2609.36359#A2.SS6)\.

Graph\-Based ANN Algorithms\.To evaluate whetherLGPgeneralizes beyond DiskANN, we additionally instantiate it on HNSW across three representative BRIGHT retrieval settings: Biology \(domain\-specific QA\), Pony \(code retrieval\), and TheoremQA\-Theorems \(theorem retrieval\)\. At search width 20,[Table5](https://arxiv.org/html/2609.36359#S5.T5)shows consistent improvements after reranking across datasets\. Under greedy search,LGPimproves TheoremQA\-Theorems and Pony, while remaining comparable to baseline on Biology\. The search\-width sweeps in[Figure6](https://arxiv.org/html/2609.36359#A1.F6)\(Appendix\) show that these gains generally persist across HNSW search widths, with larger improvements at narrower widths\. These results demonstrate thatLGPgeneralizes across different graph\-based ANN indices\.

Embeddings\.To evaluate robustness to the embedding model, we replace Diver with Qwen3\-Embedding\. As shown in[Table6](https://arxiv.org/html/2609.36359#S5.T6),LGPimproves every aggregate retrieval metric under both greedy search and LLM reranking\. Average NDCG@10 improves by14\.7%under greedy search and14\.4%after reranking\. These results show that the gains ofLGPremain robust across different embedding models\. Additional per\-dataset results are provided in[SectionB\.2](https://arxiv.org/html/2609.36359#A2.SS2)\.

Model Size and Graph Degree\.We further study the effects of model size and graph degree\. As shown in[Table7](https://arxiv.org/html/2609.36359#S5.T7), using Qwen3\-32B for semantic selection consistently yields stronger results than Qwen3\-8B\. Across graph degrees,LGPoutperforms Vanilla in most settings, with consistent gains on Pony and substantial improvements on Psychology in several configurations\. Notably,LGPsubstantially improves both datasets atR=8R=8\. These results show that stronger models can improve graph construction and that the benefits ofLGPextend across different graph\-degree settings\.

Figure 4:Hyperparameter ablation ofLGPon Pony and Psychology at search width 20\.Per\-Node Edit Budget, Shortlist Size, and Global Pruning Budget\.We further evaluateLGPunder different per\-node edit budgetsBB, shortlist sizesMM, and global pruning budgetsβ\\beta\. Here,β\\betadenotes the maximum fraction of graph nodes that undergo LLM\-guided pruning, withβ∈\{0\.25,0\.5,1\}\\beta\\in\\\{0\.25,0\.5,1\\\}corresponding to at most 25%, 50%, and 100% of the graph, respectively\. As shown in[Figure4](https://arxiv.org/html/2609.36359#S5.F4), the moderate local settingsB=2B=2andM=24M=24achieve the strongest greedy\-search and reranked NDCG@10 among the tested choices\. In contrast, increasing the global pruning budget improves performance, withβ=1\\beta=1achieving the strongest results on both Pony and Psychology\. These results suggest a clear trade\-off: local updates should remain selective, since too few edits or candidates may limit semantic coverage, while overly aggressive editing or excessively large shortlists may hurt geometric structure or LLM selection quality\. At the graph level, however, applying LLM\-guided pruning to more neighborhoods yields stronger retrieval performance\.

Additional Results\.Additional search\-width and distance\-computation\-budget sweeps, embedding\-model, design, and hyperparameter ablations, and pruning\-cost analysis are provided in[AppendixB](https://arxiv.org/html/2609.36359#A2)\.

## 6Conclusion and Limitations

We identify a fundamental*geometry–semantic mismatch*in graph\-based ANNS: indices are built using embedding\-space geometry but evaluated by semantic relevance\. Our analysis shows that geometrically comparable edge choices can yield substantially different retrieval performance, motivatingLGP, an offline framework that uses LLM reasoning to replace structurally low\-value neighbors with semantically more useful alternatives\. Across textual and multimodal benchmarks,LGPconsistently improves both greedy graph search and downstream reranking on DiskANN and HNSW while preserving graph sparsity and leaving the query\-time search procedure unchanged\.

Our current framework is limited to graph\-based ANN indices\. Its effectiveness also depends on the quality of LLM/VLM semantic judgments\. Extending this index\-level refinement paradigm to other ANN algorithms is a promising direction for future work\. More broadly, we viewLGPas a first step towards identifying and addressing the geometry–semantic mismatch rather than the end of the story\.

## References

- Arslanet al\.\(2024\)M\. Arslan, H\. Ghanem, S\. Munawar, and C\. CruzA survey on rag with llms\.Procedia Computer Science246,pp\. 3781–3790\.Note:28th International Conference on Knowledge Based and Intelligent information and Engineering Systems \(KES 2024\)External Links:ISSN 1877\-0509,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.procs.2024.09.178),[Link](https://www.sciencedirect.com/science/article/pii/S1877050924021860)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p1.1),[§1](https://arxiv.org/html/2609.36359#S1.p1.1)\.
- Baiet al\.\(2025\)S\. Bai, Y\. Cai, R\. Chen, K\. Chen, X\. Chen, Z\. Cheng, L\. Deng, W\. Ding, C\. Gao, C\. Ge, W\. Ge, Z\. Guo, Q\. Huang, J\. Huang, F\. Huang, B\. Hui, S\. Jiang, Z\. Li, M\. Li, M\. Li, K\. Li, Z\. Lin, J\. Lin, X\. Liu, J\. Liu, C\. Liu, Y\. Liu, D\. Liu, S\. Liu, D\. Lu, R\. Luo, C\. Lv, R\. Men, L\. Meng, X\. Ren, X\. Ren, S\. Song, Y\. Sun, J\. Tang, J\. Tu, J\. Wan, P\. Wang, P\. Wang, Q\. Wang, Y\. Wang, T\. Xie, Y\. Xu, H\. Xu, J\. Xu, Z\. Yang, M\. Yang, J\. Yang, A\. Yang, B\. Yu, F\. Zhang, H\. Zhang, X\. Zhang, B\. Zheng, H\. Zhong, J\. Zhou, F\. Zhou, J\. Zhou, Y\. Zhu, and K\. ZhuQwen3\-vl technical report\.External Links:2511\.21631,[Link](https://arxiv.org/abs/2511.21631)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p2.1),[§5](https://arxiv.org/html/2609.36359#S5.p2.1)\.
- Chanet al\.\(2024\)C\. Chan, C\. Xu, R\. Yuan, H\. Luo, W\. Xue, Y\. Guo, and J\. FuRQ\-RAG: learning to refine queries for retrieval augmented generation\.InFirst Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=tzE7VqsaJ4)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1),[§1](https://arxiv.org/html/2609.36359#S1.p1.1),[§2](https://arxiv.org/html/2609.36359#S2.p4.1)\.
- Chenet al\.\(2024\)J\. Chen, S\. Xiao, P\. Zhang, K\. Luo, D\. Lian, and Z\. LiuBGE m3\-embedding: multi\-lingual, multi\-functionality, multi\-granularity text embeddings through self\-knowledge distillation\.External Links:2402\.03216Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- Daset al\.\(2025\)D\. Das, S\. O’Nuallain, and R\. RahimiRaDeR: reasoning\-aware dense retrieval models\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,C\. Christodoulopoulos, T\. Chakraborty, C\. Rose, and V\. Peng \(Eds\.\),Suzhou, China,pp\. 19970–19997\.External Links:[Link](https://aclanthology.org/2025.emnlp-main.1011/),[Document](https://dx.doi.org/10.18653/v1/2025.emnlp-main.1011),ISBN 979\-8\-89176\-332\-6Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1)\.
- Douzeet al\.\(2026\)M\. Douze, A\. Guzhva, C\. Deng, J\. Johnson, G\. Szilvasy, P\. Mazaré, M\. Lomeli, L\. Hosseini, and H\. JégouThe faiss library\.IEEE Transactions on Big Data12\(2\),pp\. 346–361\.External Links:[Document](https://dx.doi.org/10.1109/TBDATA.2025.3618474)Cited by:[§1](https://arxiv.org/html/2609.36359#S1.p1.1)\.
- Fu and Cai \(2016\)C\. Fu and D\. CaiEFANNA : an extremely fast approximate nearest neighbor search algorithm based on knn graph\.External Links:1609\.07228,[Link](https://arxiv.org/abs/1609.07228)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- Fuet al\.\(2019\)C\. Fu, C\. Xiang, C\. Wang, and D\. CaiFast approximate nearest neighbor search with the navigating spreading\-out graph\.Proc\. VLDB Endow\.12\(5\),pp\. 461–474\.External Links:ISSN 2150\-8097,[Link](https://doi.org/10.14778/3303753.3303754),[Document](https://dx.doi.org/10.14778/3303753.3303754)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p1.1),[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- Gollapudiet al\.\(2023\)S\. Gollapudi, N\. Karia, V\. Sivashankar, R\. Krishnaswamy, N\. Begwani, S\. Raz, Y\. Lin, Y\. Zhang, N\. Mahapatro, P\. Srinivasan, A\. Singh, and H\. V\. SimhadriFiltered\-diskann: graph algorithms for approximate nearest neighbor search with filters\.InProceedings of the ACM Web Conference 2023,WWW ’23,New York, NY, USA,pp\. 3406–3416\.External Links:ISBN 9781450394161,[Link](https://doi.org/10.1145/3543507.3583552),[Document](https://dx.doi.org/10.1145/3543507.3583552)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- Harwood and Drummond \(2016\)B\. Harwood and T\. DrummondFANNG: fast approximate nearest neighbour graphs\.In2016 IEEE Conference on Computer Vision and Pattern Recognition \(CVPR\),Vol\.,pp\. 5713–5722\.External Links:[Document](https://dx.doi.org/10.1109/CVPR.2016.616)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- Indyk and Xu \(2023\)P\. Indyk and H\. XuWorst\-case performance of popular approximate nearest neighbor search implementations: guarantees and limitations\.InAdvances in Neural Information Processing Systems,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),Vol\.36,pp\. 66239–66256\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2023/file/d0ac28b79816b51124fcc804b2496a36-Paper-Conference.pdf)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- Jayaram Subramanyaet al\.\(2019\)S\. Jayaram Subramanya, F\. Devvrit, H\. V\. Simhadri, R\. Krishnawamy, and R\. KadekodiDiskANN: fast accurate billion\-point nearest neighbor search on a single node\.InAdvances in Neural Information Processing Systems,H\. Wallach, H\. Larochelle, A\. Beygelzimer, F\. d'Alché\-Buc, E\. Fox, and R\. Garnett \(Eds\.\),Vol\.32,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2019/file/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Paper.pdf)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p3.1),[Appendix F](https://arxiv.org/html/2609.36359#A6.p1.1),[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1),[§1](https://arxiv.org/html/2609.36359#S1.p1.1),[§1](https://arxiv.org/html/2609.36359#S1.p6.1),[§2](https://arxiv.org/html/2609.36359#S2.p1.1)\.
- Jegouet al\.\(2011\)H\. Jegou, M\. Douze, and C\. SchmidProduct quantization for nearest neighbor search\.IEEE Trans\. Pattern Anal\. Mach\. Intell\.33\(1\),pp\. 117–128\.External Links:ISSN 0162\-8828,[Link](https://doi.org/10.1109/TPAMI.2010.57),[Document](https://dx.doi.org/10.1109/TPAMI.2010.57)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p1.1)\.
- Johnsonet al\.\(2021\)J\. Johnson, M\. Douze, and H\. JégouBillion\-scale similarity search with gpus\.IEEE Transactions on Big Data7\(3\),pp\. 535–547\.External Links:[Document](https://dx.doi.org/10.1109/TBDATA.2019.2921572)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p1.1)\.
- Liuet al\.\(2025\)W\. Liu, X\. Ma, W\. Sun, Y\. Zhu, Y\. Li, D\. Yin, and Z\. DouReasonRank: empowering passage ranking with strong reasoning ability\.External Links:2508\.07050,[Link](https://arxiv.org/abs/2508.07050)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1),[§2](https://arxiv.org/html/2609.36359#S2.p4.1)\.
- Maet al\.\(2023\)X\. Ma, Y\. Gong, P\. He, H\. Zhao, and N\. DuanQuery rewriting in retrieval\-augmented large language models\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),Singapore,pp\. 5303–5315\.External Links:[Link](https://aclanthology.org/2023.emnlp-main.322/),[Document](https://dx.doi.org/10.18653/v1/2023.emnlp-main.322)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1),[§2](https://arxiv.org/html/2609.36359#S2.p4.1)\.
- Malkov and Yashunin \(2020\)Y\. A\. Malkov and D\. A\. YashuninEfficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs\.IEEE Trans\. Pattern Anal\. Mach\. Intell\.42\(4\),pp\. 824–836\.External Links:ISSN 0162\-8828,[Link](https://doi.org/10.1109/TPAMI.2018.2889473),[Document](https://dx.doi.org/10.1109/TPAMI.2018.2889473)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p3.1),[Appendix F](https://arxiv.org/html/2609.36359#A6.p1.1),[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1),[§1](https://arxiv.org/html/2609.36359#S1.p1.1),[§1](https://arxiv.org/html/2609.36359#S1.p6.1),[§2](https://arxiv.org/html/2609.36359#S2.p1.1)\.
- Menget al\.\(2024\)R\. Meng, Y\. Liu, S\. R\. Joty, C\. Xiong, Y\. Zhou, and S\. YavuzSFR\-embedding\-2: advanced text embedding with multi\-stage training\.External Links:[Link](https://huggingface.co/Salesforce/SFR-Embedding-2_R)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- OpenAI \(2024\)OpenAIText\-embedding\-3\-large\.External Links:[Link](https://platform.openai.com/docs/models/text-embedding-3-large)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- Pradeepet al\.\(2023\)R\. Pradeep, S\. Sharifymoghaddam, and J\. LinRankVicuna: zero\-shot listwise document reranking with open\-source large language models\.External Links:2309\.15088,[Link](https://arxiv.org/abs/2309.15088)Cited by:[§1](https://arxiv.org/html/2609.36359#S1.p1.1)\.
- Qinet al\.\(2024\)Z\. Qin, R\. Jagerman, K\. Hui, H\. Zhuang, J\. Wu, L\. Yan, J\. Shen, T\. Liu, J\. Liu, D\. Metzler, X\. Wang, and M\. BenderskyLarge language models are effective text rankers with pairwise ranking prompting\.InFindings of the Association for Computational Linguistics: NAACL 2024,K\. Duh, H\. Gomez, and S\. Bethard \(Eds\.\),Mexico City, Mexico,pp\. 1504–1518\.External Links:[Link](https://aclanthology.org/2024.findings-naacl.97/),[Document](https://dx.doi.org/10.18653/v1/2024.findings-naacl.97)Cited by:[§1](https://arxiv.org/html/2609.36359#S1.p1.1)\.
- Radfordet al\.\(2021\)A\. Radford, J\. W\. Kim, C\. Hallacy, A\. Ramesh, G\. Goh, S\. Agarwal, G\. Sastry, A\. Askell, P\. Mishkin, J\. Clark, G\. Krueger, and I\. SutskeverLearning transferable visual models from natural language supervision\.InProceedings of the 38th International Conference on Machine Learning,M\. Meila and T\. Zhang \(Eds\.\),Proceedings of Machine Learning Research, Vol\.139,pp\. 8748–8763\.External Links:[Link](https://proceedings.mlr.press/v139/radford21a.html)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p2.1),[§5](https://arxiv.org/html/2609.36359#S5.p2.1)\.
- Shaoet al\.\(2025\)R\. Shao, R\. Qiao, V\. Kishore, N\. Muennighoff, X\. V\. Lin, D\. Rus, B\. K\. H\. Low, S\. Min, W\. Yih, P\. W\. Koh, and L\. ZettlemoyerReasonIR: training retrievers for reasoning tasks\.InSecond Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=kkBCNLMbGj)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1),[§1](https://arxiv.org/html/2609.36359#S1.p1.1),[§2](https://arxiv.org/html/2609.36359#S2.p4.1)\.
- Singhet al\.\(2021\)A\. Singh, S\. J\. Subramanya, R\. Krishnaswamy, and H\. V\. SimhadriFreshDiskANN: a fast and accurate graph\-based ann index for streaming similarity search\.External Links:2105\.09613,[Link](https://arxiv.org/abs/2105.09613)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- SUet al\.\(2025\)H\. SU, H\. Yen, M\. Xia, W\. Shi, N\. Muennighoff, H\. Wang, L\. Haisu, Q\. Shi, Z\. S\. Siegel, M\. Tang, R\. Sun, J\. Yoon, S\. O\. Arik, D\. Chen, and T\. YuBRIGHT: a realistic and challenging benchmark for reasoning\-intensive retrieval\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=ykuc5q381b)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p1.1),[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1),[§3](https://arxiv.org/html/2609.36359#S3.p4.1),[§5](https://arxiv.org/html/2609.36359#S5.p2.1)\.
- Sunet al\.\(2026\)D\. Sun, M\. Long, D\. Yang, J\. Wang, Y\. Luo, Y\. Shen, J\. Wang, H\. Zhou, C\. Guo, P\. Wei, J\. Wang, and J\. GuDIVER: a multi\-stage approach for reasoning\-intensive information retrieval\.External Links:2508\.07995,[Link](https://arxiv.org/abs/2508.07995)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p2.1),[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1),[§5](https://arxiv.org/html/2609.36359#S5.p2.1)\.
- Sunet al\.\(2023\)W\. Sun, L\. Yan, X\. Ma, S\. Wang, P\. Ren, Z\. Chen, D\. Yin, and Z\. RenIs ChatGPT good at search? investigating large language models as re\-ranking agents\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),Singapore,pp\. 14918–14937\.External Links:[Link](https://aclanthology.org/2023.emnlp-main.923/),[Document](https://dx.doi.org/10.18653/v1/2023.emnlp-main.923)Cited by:[§1](https://arxiv.org/html/2609.36359#S1.p1.1)\.
- Taghaviet al\.\(2026\)Z\. S\. Taghavi, A\. Modarressi, H\. Schutze, and A\. MarfurtWith argus eyes: assessing retrieval gaps via uncertainty scoring to detect and remedy retrieval blind spots\.External Links:2602\.09616,[Link](https://arxiv.org/abs/2602.09616)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p2.1)\.
- Team \(2025\)Q\. TeamQwen3 technical report\.External Links:2505\.09388,[Link](https://arxiv.org/abs/2505.09388)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p2.1),[§5](https://arxiv.org/html/2609.36359#S5.p2.1)\.
- Weiet al\.\(2024\)C\. Wei, Y\. Chen, H\. Chen, H\. Hu, G\. Zhang, J\. Fu, A\. Ritter, and W\. ChenUniIR: training and benchmarking universal multimodal information retrievers\.InComputer Vision – ECCV 2024: 18th European Conference, Milan, Italy, September 29–October 4, 2024, Proceedings, Part LXXXVII,Berlin, Heidelberg,pp\. 387–404\.External Links:ISBN 978\-3\-031\-73020\-7,[Link](https://doi.org/10.1007/978-3-031-73021-4_23),[Document](https://dx.doi.org/10.1007/978-3-031-73021-4%5F23)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p1.1),[§5](https://arxiv.org/html/2609.36359#S5.p2.1)\.
- Welleret al\.\(2025\)O\. Weller, K\. Ricci, E\. Yang, A\. Yates, D\. Lawrie, and B\. V\. DurmeRank1: test\-time compute for reranking in information retrieval\.InSecond Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=Pg0PAvbhGv)Cited by:[§1](https://arxiv.org/html/2609.36359#S1.p1.1)\.
- Xu and Chen \(2026\)H\. Xu and T\. ChenBeyond sequential reranking: reranker\-guided search improves reasoning intensive retrieval\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=Fjw3OqdjTj)Cited by:[Appendix A](https://arxiv.org/html/2609.36359#A1.p1.1),[Appendix A](https://arxiv.org/html/2609.36359#A1.p2.1),[Appendix F](https://arxiv.org/html/2609.36359#A6.p5.1),[§2](https://arxiv.org/html/2609.36359#S2.p4.1),[§5](https://arxiv.org/html/2609.36359#S5.p2.1)\.
- Xuet al\.\(2026\)H\. Xu, S\. Silwal, and P\. IndykA bi\-metric framework for efficient nearest neighbor search\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=kBzzertldC)Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p5.1),[§2](https://arxiv.org/html/2609.36359#S2.p4.1)\.
- Yaoet al\.\(2025\)Y\. Yao, J\. Wan, Y\. Hong, M\. Zhang, J\. Yang, Z\. Jiang, Q\. Xu, K\. Lu, Y\. Xu, W\. Chu, E\. Wang, and Y\. QiINF\-x\-retriever: a pragmatic framework for reasoning\-intensive dense retrieval\.GitHub repository\.External Links:LinkCited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1),[§1](https://arxiv.org/html/2609.36359#S1.p1.1)\.
- Yoonet al\.\(2025\)S\. Yoon, G\. Kim, G\. Cho, and S\. HwangAcuRank: uncertainty\-aware adaptive computation for listwise reranking\.External Links:2505\.18512,[Link](https://arxiv.org/abs/2505.18512)Cited by:[§1](https://arxiv.org/html/2609.36359#S1.p2.1)\.
- Zhanget al\.\(2025\)L\. Zhang, B\. Wang, X\. Qiu, S\. Reddy, and A\. AgrawalREARANK: reasoning re\-ranking agent via reinforcement learning\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,C\. Christodoulopoulos, T\. Chakraborty, C\. Rose, and V\. Peng \(Eds\.\),Suzhou, China,pp\. 2458–2471\.External Links:[Link](https://aclanthology.org/2025.emnlp-main.125/),[Document](https://dx.doi.org/10.18653/v1/2025.emnlp-main.125),ISBN 979\-8\-89176\-332\-6Cited by:[Appendix F](https://arxiv.org/html/2609.36359#A6.p3.1),[§2](https://arxiv.org/html/2609.36359#S2.p4.1)\.

Table 8:Dataset statistics for the BRIGHT benchmark\.DatasetQueriesDocumentsBiology10357,359Earth Science116121,249Economics10350,220Psychology10152,835Robotics10161,961StackOverflow117107,081Sustainable Living10860,792Pony1127,894LeetCode142413,932AoPS111188,002TheoremQA\-Theorems7623,839TheoremQA\-Questions194188,002Table 9:Task subsets, retrieval modalities, and evaluation set sizes for the M\-BEIR benchmark\. I and T denote image and text, respectively\.DatasetTaskQuery→\\totargetQueriesCandidatesVisualNews0T→I\\mathrm\{T\}\\to\\mathrm\{I\}19,995542,246MSCOCO0T→I\\mathrm\{T\}\\to\\mathrm\{I\}24,8095,000Fashion200K0T→I\\mathrm\{T\}\\to\\mathrm\{I\}1,719201,824WebQA1T→T\\mathrm\{T\}\\to\\mathrm\{T\}2,455544,457EDIS2T→I\+T\\mathrm\{T\}\\to\\mathrm\{I\}\+\\mathrm\{T\}3,2411,047,067WebQA2T→I\+T\\mathrm\{T\}\\to\\mathrm\{I\}\+\\mathrm\{T\}2,511403,196VisualNews3I→T\\mathrm\{I\}\\to\\mathrm\{T\}20,000537,568MSCOCO3I→T\\mathrm\{I\}\\to\\mathrm\{T\}5,00024,809Fashion200K3I→T\\mathrm\{I\}\\to\\mathrm\{T\}4,88961,707NIGHTS4I→I\\mathrm\{I\}\\to\\mathrm\{I\}2,12040,038OVEN6I\+T→T\\mathrm\{I\}\+\\mathrm\{T\}\\to\\mathrm\{T\}50,004676,667InfoSeek6I\+T→T\\mathrm\{I\}\+\\mathrm\{T\}\\to\\mathrm\{T\}11,323611,651CIRR7I\+T→I\\mathrm\{I\}\+\\mathrm\{T\}\\to\\mathrm\{I\}4,17021,551FashionIQ7I\+T→I\\mathrm\{I\}\+\\mathrm\{T\}\\to\\mathrm\{I\}6,00374,381OVEN8I\+T→I\+T\\mathrm\{I\}\+\\mathrm\{T\}\\to\\mathrm\{I\}\+\\mathrm\{T\}14,741335,135InfoSeek8I\+T→I\+T\\mathrm\{I\}\+\\mathrm\{T\}\\to\\mathrm\{I\}\+\\mathrm\{T\}17,593481,782Table 10:Models used in the experiments\.BenchmarkRoleModelBRIGHTEmbeddingDiver\-Retriever\-4B\-1020BRIGHTEmbeddingQwen3\-Embedding\-4BBRIGHTGraph refinement / rerankingQwen3\-32BM\-BEIREmbeddingCLIP \(ViT\-B/32\)M\-BEIRGraph refinement / rerankingQwen3\-VL\-30B\-A3B\-Instruct## Appendix AExperimental Setup

Benchmarks\.We use BRIGHT\([SU et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib7)\)for reasoning\-intensive text retrieval and M\-BEIR\([Wei et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib13)\)for multimodal retrieval\. BRIGHT contains 12 datasets spanning diverse domains, while M\-BEIR contains 16 tasks covering text, image, and image–text retrieval\. For BRIGHT, we evaluate all queries in each dataset\. For M\-BEIR, following the setup of[Xu and Chen \(2026\)](https://arxiv.org/html/2609.36359#bib.bib19), we uniformly sample 100 queries from each task and use the same sampled queries across all experiments\. Following the task\-specific M\-BEIR preprocessing\([Wei et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib13);[Xu and Chen, 2026](https://arxiv.org/html/2609.36359#bib.bib19)\), we use the released text corpora for OVEN and InfoSeek Task 6, restrict retrieval to their corresponding candidate pools, and use the associated relevance labels for evaluation\. Detailed benchmark statistics are provided in[Tables8](https://arxiv.org/html/2609.36359#A0.T8)and[9](https://arxiv.org/html/2609.36359#A0.T9)\.

Models\.For BRIGHT, we use Diver\-Retriever\-4B\-1020\([Sun et al\., 2026](https://arxiv.org/html/2609.36359#bib.bib11)\)and Qwen3\-Embedding\-4B as embedding models\. For M\-BEIR, following[Xu and Chen \(2026\)](https://arxiv.org/html/2609.36359#bib.bib19), we use CLIP \(ViT\-B/32\)\([Radford et al\., 2021](https://arxiv.org/html/2609.36359#bib.bib16)\)to encode all 16 task subsets\. We follow the benchmark\-specific query formatting by prepending each text\-bearing query with its corresponding task instruction\. For single\-modality inputs, weℓ2\\ell\_\{2\}\-normalize the corresponding CLIP feature\. For image–text inputs, we firstℓ2\\ell\_\{2\}\-normalize the image and text features separately, sum the two normalized vectors, and then normalize the resulting vector again\. Retrieval is performed using cosine similarity\. For LLM\-guided semantic selection inLGPand downstream reranking, we use Qwen3\-32B\([Team, 2025](https://arxiv.org/html/2609.36359#bib.bib14)\)for BRIGHT and Qwen3\-VL\-30B\-A3B\-Instruct\([Bai et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib15)\)for M\-BEIR\. Both models are used in their non\-reasoning configuration\. For the model\-size ablation, we vary only the model used for semantic selection, using Qwen3\-8B or Qwen3\-32B, while keeping Qwen3\-32B fixed as the downstream reranker\.[Table10](https://arxiv.org/html/2609.36359#A0.T10)summarizes the specific model configurations\.

Index Configurations\.Our primary ANN index is DiskANN\([Jayaram Subramanya et al\., 2019](https://arxiv.org/html/2609.36359#bib.bib5)\), configured with a maximum out\-degree of 16, a construction search\-list size of 125, and a pruning parameter of 1\.2\. We additionally evaluate HNSW\([Malkov and Yashunin, 2020](https://arxiv.org/html/2609.36359#bib.bib3)\), using a connectivity parameter of 16 and a construction search width of 200\. For both indices,LGPperforms local graph pruning on top of the corresponding Vanilla index\. For the textual retrieval setting,LGPuses edit budgetB=2B=2, shortlist sizeM=24M=24, neighborhood\-context size\|Ki\|=4\|K\_\{i\}\|=4, and thresholdgmin=12g\_\{\\min\}=12\. For the multimodal setting, we useB=2B=2andM=12M=12, with the same context size and threshold\. For the graph\-degree ablation, we setgmin=6g\_\{\\min\}=6atR=8R=8to match the defaultgmin/Rg\_\{\\min\}/Rratio atR=16R=16, while usinggmin=12g\_\{\\min\}=12for all other degree settings\.

Retrieval Configurations and Metrics\.At query time, we evaluate two settings: \(i\) greedy search, and \(ii\) downstream LLM/VLM reranking of the candidate set returned by greedy search\. We use*search width*, the standard query\-time search\-effort parameter in graph\-based ANN indices, corresponding toLsearchL\_\{\\mathrm\{search\}\}in DiskANN ande​fsearchef\_\{\\mathrm\{search\}\}in HNSW\. Search width controls the breadth of candidates explored during graph traversal, with larger values generally requiring more node expansions and distance computations\. With graph degree bounded byRR, the distance\-computation cost grows roughly withsearch width×R\\text\{search width\}\\times R, making search width a practical control for query\-time search effort\. We therefore use search width as the primary query\-time search\-effort parameter throughout our main evaluation\. For DiskANN, we varyLsearch∈\{10,20,50,100,200\}L\_\{\\mathrm\{search\}\}\\in\\\{10,20,50,100,200\\\}; for HNSW, we varye​fsearch∈\{10,12,14,16,18,20,50\}ef\_\{\\mathrm\{search\}\}\\in\\\{10,12,14,16,18,20,50\\\}\. By default, we set the search width to 20 for both indices to target the budget\-constrained regime, where graph connectivity most strongly dictates which relevant documents are reached\. For reranking, we use the candidates returned by graph search, capped at 200 for text retrieval and 64 for multimodal retrieval\. At the default search width of 20, both rerankers therefore receive 20 candidates\. Both rerankers use listwise sliding windows of 10 candidates with a stride of 5\. For greedy search, the topkkdocuments are selected from the returned candidates according to embedding distance\. For reranking, the same candidate set is reordered by the model before evaluating the resulting topkk\.

Our primary retrieval metrics are NDCG@kkand document\-level Recall@kkfork∈\{5,10\}k\\in\\\{5,10\\\}, reported on a 0–100 scale\. NDCG@kkmeasures ranking quality within the topkk, normalized by the ideal ranking at the same cutoff\. Recall@kkmeasures the fraction of all ground\-truth documents that appear in the topkk, averaged over queries\. Because reranking can change which documents appear in the topkk, it can also change Recall@kkeven though the candidate set itself is unchanged\. When a query has more thankkrelevant documents, its maximum Recall@kkis below 100, so Recall@kkand NDCG@kkare not directly comparable in magnitude\.

Table 11:BRIGHT main results on DiskANN at search width 20 using Diver embeddings\. Each entry reports Vanilla /LGP\.Greedy searchRerankDatasetNDCG@5NDCG@10Recall@5Recall@10NDCG@5NDCG@10Recall@5Recall@10Biology22\.22 /32\.6624\.69 /37\.0621\.42 /32\.1028\.66 /44\.6326\.95 /39\.1528\.30 /41\.5726\.22 /38\.4730\.71 /46\.19Earth Science19\.80 /26\.3220\.60 /27\.9219\.13 /25\.8022\.70 /30\.5921\.91 /28\.0323\.29 /30\.0620\.62 /27\.3025\.51 /33\.03Economics18\.68 /21\.0019\.56 /22\.3515\.62 /18\.8120\.77 /25\.6118\.84 /24\.0119\.98 /25\.4216\.09 /22\.4621\.92 /28\.84Psychology26\.62 /32\.3728\.31 /34\.7626\.62 /31\.6234\.51 /41\.6132\.88 /40\.2032\.78 /41\.4629\.47 /35\.1134\.40 /44\.10Robotics19\.05 /21\.1919\.48 /21\.6820\.59 /22\.3524\.83 /27\.1225\.68 /28\.4725\.67 /28\.6324\.27 /25\.9828\.61 /31\.16StackOverflow8\.75 /14\.8310\.82 /17\.368\.71 /14\.7613\.87 /21\.3710\.22 /16\.8611\.96 /19\.619\.72 /15\.9414\.66 /23\.73Sustainable Living16\.35 /22\.3018\.09 /24\.3315\.09 /22\.1222\.12 /29\.7619\.32 /26\.0520\.20 /27\.4318\.21 /25\.0622\.04 /30\.82Pony20\.34 /20\.9917\.08 /17\.805\.29 /5\.369\.06 /9\.4024\.81 /26\.0419\.54 /20\.076\.56 /6\.739\.73/ 9\.00LeetCode2\.66 /4\.893\.20 /6\.203\.35 /6\.274\.54 /9\.512\.34 /5\.272\.97 /6\.372\.66 /7\.054\.27 /10\.07AoPS2\.67 / 2\.673\.13 /3\.363\.03 / 3\.034\.58 /5\.032\.39 /2\.463\.12 /3\.232\.52 / 2\.524\.69 /4\.79TheoremQA\-Theorems31\.23 /32\.6334\.70 /36\.3537\.16 /37\.4846\.26 /47\.5730\.36 /33\.1833\.57 /36\.4436\.31 /39\.2745\.60 /48\.89TheoremQA\-Questions5\.39 /6\.205\.73 /6\.457\.56 /7\.868\.24 /8\.364\.92/ 4\.905\.63 /5\.687\.52 /7\.569\.24 /9\.49Average16\.15 /19\.8417\.12 /21\.3015\.30 /18\.9620\.01 /25\.0518\.38 /22\.8818\.92 /23\.8316\.68 /21\.1220\.95 /26\.68

Table 12:M\-BEIR main results on DiskANN at search width 20 using CLIP \(ViT\-B/32\)\. Parentheses indicate the M\-BEIR task ID\. Each entry reports Vanilla /LGP\.Greedy searchRerankDataset \(Task\)NDCG@5NDCG@10Recall@5Recall@10NDCG@5NDCG@10Recall@5Recall@10VisualNews \(0\)15\.80/ 14\.5416\.41/ 15\.4519\.00/ 17\.0021\.00/ 20\.0014\.26 /15\.0215\.23 /15\.9718\.00 /18\.0021\.00 /21\.00MSCOCO \(0\)28\.26 /28\.3332\.45 /32\.8838\.00 /38\.0051\.00 /52\.0042\.72 /43\.7245\.09 /46\.0949\.00 /50\.0056\.00 /57\.00Fashion200K \(0\)1\.51 /1\.511\.80 /1\.821\.79 /1\.792\.63 /2\.634\.41/ 3\.414\.53/ 3\.563\.97/ 2\.974\.97/ 3\.97WebQA \(1\)5\.38 /6\.005\.99 /6\.616\.00 /6\.507\.50 /8\.008\.29 /8\.768\.29 /8\.938\.00 /8\.508\.00 /9\.00EDIS \(2\)5\.87 /9\.896\.76 /11\.296\.49 /10\.579\.07 /14\.7410\.33 /14\.2211\.02 /15\.6710\.63 /14\.0512\.80 /18\.71WebQA \(2\)12\.99 /21\.7315\.15 /22\.9714\.50 /26\.0020\.50 /29\.5019\.50 /28\.5620\.25 /29\.1821\.50 /32\.0023\.50 /33\.50VisualNews \(3\)2\.65 /5\.773\.87 /7\.045\.00 /10\.009\.00 /14\.003\.97 /7\.775\.25 /10\.297\.00 /11\.0011\.00 /19\.00MSCOCO \(3\)37\.05 /37\.5142\.42 /43\.0032\.80 /32\.8042\.60 /42\.8049\.83 /51\.1152\.63 /53\.9244\.20 /44\.8049\.20 /49\.80Fashion200K \(3\)1\.93/ 1\.862\.93/ 2\.863\.00 /3\.006\.00 /6\.003\.26 /3\.653\.97 /4\.004\.00 /5\.006\.00 /6\.00NIGHTS \(4\)23\.93 /23\.9328\.73 /28\.7336\.00 /36\.0051\.00 /51\.0038\.01 /39\.2241\.99 /42\.5149\.00 /51\.0061\.00 /61\.00OVEN \(6\)0\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.00InfoSeek \(6\)0\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.000\.00 / 0\.00CIRR \(7\)6\.16 /6\.866\.47 /7\.8312\.00 /13\.0013\.00 /16\.0010\.99 /12\.3410\.99 /12\.3413\.00 /15\.0013\.00 /15\.00FashionIQ \(7\)0\.00 /0\.430\.67 /1\.120\.00 /1\.002\.00 /3\.000\.63 /2\.631\.61 /3\.661\.00 /3\.004\.00 /6\.00OVEN \(8\)0\.25 /0\.590\.50 /1\.350\.25 /0\.270\.75 /2\.081\.20 /3\.391\.16 /3\.090\.75 /2\.080\.75 /2\.08InfoSeek \(8\)0\.26 /0\.410\.48 /0\.930\.50 /0\.581\.00 /1\.580\.26 /2\.820\.45 /2\.530\.50 /1\.621\.00 /2\.31Average8\.88 /9\.9610\.29 /11\.4910\.96 /12\.2814\.82 /16\.4612\.98 /14\.7913\.90 /15\.7314\.41 /16\.1917\.01 /19\.02

Figure 5:Search\-width sweeps on six BRIGHT datasets using Diver embeddings \(part 1 of 2\)\.Figure 6:HNSW search\-width sweeps on 3 BRIGHT datasets\. The left three panels show greedy\-search NDCG@10, while the right three show NDCG@10 after LLM reranking\.Figure 7:Search\-width sweeps on the remaining six BRIGHT datasets using Diver embeddings \(part 2 of 2\)\.Figure 8:Search\-width sweeps on 6 M\-BEIR tasks using CLIP embeddings\.LGPconsistently matches or outperforms Vanilla under both greedy search and VLM reranking across search widths\.
## Appendix BAdditional Results

### B\.1Search\-Width Results

[Figures5](https://arxiv.org/html/2609.36359#A1.F5)and[7](https://arxiv.org/html/2609.36359#A1.F7)show the per\-dataset search\-width sweeps using Diver embeddings on BRIGHT\. The gains are broadly consistent across datasets, showing that the aggregate improvements are not driven by a small subset of tasks\. This further supports thatLGPrefines graph connectivity in ways that better align with downstream semantic relevance\.

Figure 9:Search\-width sweeps on six BRIGHT datasets using Qwen3\-Embedding \(part 1 of 2\)\.Figure 10:Search\-width sweeps on the remaining six BRIGHT datasets using Qwen3\-Embedding \(part 2 of 2\)\.Table 13:Ablation of candidate shortlisting on Pony, Psychology, and Biology from BRIGHT at search width 20 using Diver embeddings\. Entries report NDCG@10\.PonyPsychologyBiologyVariantGreedyRerankGreedyRerankGreedyRerankProximity only16\.8918\.9433\.7139\.5233\.0737\.69Coverage only17\.8420\.2233\.1839\.3037\.0641\.17Separation only17\.1920\.0233\.4539\.6839\.2245\.71Balanced17\.8020\.0734\.7641\.4637\.0641\.57Table 14:Ablation of low\-value neighbor identification on Pony, Psychology, and Biology from BRIGHT at search width 20 using Diver embeddings\. Entries report NDCG@10\.PonyPsychologyBiologyVariantGreedyRerankGreedyRerankGreedyRerankRedundancy only17\.3620\.2232\.3838\.0433\.9339\.74Coverage only17\.7320\.0334\.3041\.1534\.4138\.86Lexicographic17\.8020\.0734\.7641\.4637\.0641\.57
### B\.2Embedding\-Model Ablations

Per\-dataset BRIGHT results using Qwen3\-Embedding are shown in[Figures9](https://arxiv.org/html/2609.36359#A2.F9)and[10](https://arxiv.org/html/2609.36359#A2.F10)\. Across datasets and search widths,LGPconsistently matches or outperforms Vanilla, further demonstrating that its gains are robust to the choice of embedding model\.

Table 15:Graph\-structure diagnostics for paired Vanilla andLGPindices on BRIGHT\. Each dataset contributes equally to the reported averages, and all indices use a maximum degree of 16\. Changed neighborhoods denote the percentage of nodes whose outgoing\-neighbor sets differ between the paired indices\.EmbeddingMean out\-degreeChanged neighborhoods \(%\)VanillaLGPDiver15\.6015\.6688\.5Qwen3\-Embedding15\.8815\.8088\.9
### B\.3Design Analysis ofLGP

Candidate Shortlisting\.We ablate the shortlisting strategy while keeping the other designs and parameters ofLGPfixed\. We consider three alternative shortlisting methods: \(i\)*Proximity only*selects candidates closest to the anchor in embedding space after excluding those geometrically covered by its current neighbors; \(ii\)*Coverage only*ranks candidates by decreasing additional two\-hop coverage; and \(iii\)*Separation only*ranks candidates by decreasing minimum embedding distance to the current neighbors\. The default*Balanced*strategy inLGPcombines candidates from all three rankings under the same shortlist budget\. As shown in[Table13](https://arxiv.org/html/2609.36359#A2.T13), the most effective shortlisting strategy varies across datasets, with coverage favored on Pony, balanced on Psychology, and separation on Biology\. This variation exactly motivates our balanced strategy, which combines all three signals and maintains strong performance across datasets and retrieval settings\. Thus, balanced shortlisting provides a robust default that generalizes across datasets without dataset\-specific tuning\.

Low\-Value Neighbor Identification\.We ablate the criteria used to identify low\-value existing neighbors for replacement while keeping all other components ofLGPfixed\. Besides our default*Lexicographic*rule, we consider two additional variants: \(i\)*Redundancy only*, which favors geometrically redundant neighbors, and \(ii\)*Coverage only*, which identifies neighbors with the smallest unique contribution to two\-hop coverage\. The default*Lexicographic*rule first prioritizes low unique coverage, then greater redundancy\. As shown in[Table14](https://arxiv.org/html/2609.36359#A2.T14), the lexicographic rule achieves the strongest greedy\-search performance on all three datasets and the strongest reranked performance on Psychology and Biology, while remaining close to the best result on Pony\. These results show that coverage and redundancy provide complementary signals for identifying low\-value neighbors, making the lexicographic rule a robust default across datasets\.

Graph Structure After Pruning\.As shown in[Table15](https://arxiv.org/html/2609.36359#A2.T15),LGPchanges approximately 88–89% of neighborhoods across BRIGHT, while the mean out\-degree remains nearly unchanged for both embedding models and stays below the maximum degree of 16\. Thus, the retrieval gains ofLGPcome from reconfiguring graph connectivity rather than increasing graph density\.

Figure 11:Additional hyperparameter ablations at search width 20\. The left two panels show Pony and the right two show Psychology, with dashed lines indicating the default settings\.Table 16:Offline graph\-construction cost using Diver embeddings and Qwen3\-32B on a single NVIDIA H200\. Build times are reported in minutes, token counts in millions, and per\-node time as totalLGPbuild time divided by the number of graph nodes\. LLM calls and token counts refer toLGP\.DatasetNodesBuild time \(min\)LGPtime\(s/node\)LLM callsTokens \(M\)VanillaLGPInputOutputPony7,8941\.49109\.460\.837,89423\.950\.22Psychology52,83511\.84691\.400\.7952,835124\.561\.50
### B\.4Additional Ablation on Hyperparameters inLGP

Neighborhood Context SizeKK\.We vary the neighborhood context sizeKK, which controls the number of current neighbors provided to the LLM/VLM when selecting new neighbors that add complementary semantic coverage\. As shown in[Figure11](https://arxiv.org/html/2609.36359#A2.F11), the defaultK=4K=4gives the strongest reranked NDCG@10 on both Pony and Psychology\. Increasing the context toK=8K=8provides no additional reranking benefit, suggesting that a small set of representative neighbors already captures most of the useful neighborhood context, while additional neighbors may introduce redundant information that makes semantic distinctions harder for the LLM/VLM\.

Coverage Thresholdgming\_\{\\min\}\.We vary the coverage thresholdgming\_\{\\min\}, which controls the minimum additional two\-hop coverage required for an LLM\-selected candidate to be accepted as a new neighbor\. As shown in[Figure11](https://arxiv.org/html/2609.36359#A2.F11), its effect varies across datasets: Pony performs best with the relaxed settinggmin=0g\_\{\\min\}=0, whereas Psychology performs best at the defaultgmin=12g\_\{\\min\}=12under both greedy search and reranking\. These results indicate that the preferred coverage constraint is dataset\-dependent rather than uniformly favoring stronger coverage requirements\. As shown in[Figure11](https://arxiv.org/html/2609.36359#A2.F11), the defaultgmin=12g\_\{\\min\}=12remains competitive on Pony and achieves the strongest performance on Psychology under both greedy search and reranking\.

### B\.5Pruning Cost Analysis

We profile the offline construction cost of Vanilla andLGPon Pony and Psychology using our Python DiskANN implementation with stored Diver embeddings\. We use the defaultR=16R=16,B=2B=2,M=24M=24,K=4K=4, andgmin=12g\_\{\\min\}=12, with the full pruning budgetβ=1\\beta=1\. Each run uses eight CPU cores and one NVIDIA H200, with Qwen3\-32B for semantic selection\. As shown in[Table16](https://arxiv.org/html/2609.36359#A2.T16),LGPconstructs the Pony and Psychology indices in 109\.46 and 691\.40 minutes, compared with 1\.49 and 11\.84 minutes for Vanilla\. More than 96% of theLGPconstruction time is spent waiting for LLM responses\. At the full pruning budget,LGPmakes one LLM call per node on average in both measured runs, with average graph\-construction times of 0\.83 and 0\.79 seconds per node on Pony and Psychology, respectively\. The additional cost is entirely offline: once constructed, the graph can be reused across queries without further calls to the semantic\-selection model, while the query\-time graph\-search procedure remains unchanged\.

Table 17:Distance\-computation\-budget sweeps on BRIGHT and M\-BEIR using Diver and CLIP embeddings, respectively\. Results are averaged equally across datasets and tasks\. Reranking uses the top 20 retrieved candidates at each budget\.Greensubscripts denote relative improvements over Vanilla, computed before rounding\.Grayvalues denote average exact\-kkNN NDCG@10 / Recall@10 without reranking\.Benchmark\(ExactkkNN ref\.\)ComputationbudgetGreedy searchRerankNDCG@10Recall@10NDCG@10Recall@10VanillaLGPVanillaLGPVanillaLGPVanillaLGPBRIGHT\(28\.50 / 34\.18\)1003\.965\.02\+26\.9%2\.964\.15\+40\.0%4\.285\.40\+26\.1%3\.074\.12\+34\.3%20010\.5013\.98\+33\.2%11\.6215\.60\+34\.3%11\.6715\.41\+32\.0%12\.3216\.40\+33\.1%30016\.6919\.80\+18\.6%19\.1823\.19\+20\.9%18\.7022\.46\+20\.1%20\.3524\.61\+21\.0%50022\.9224\.57\+7\.2%27\.1428\.83\+6\.2%26\.0427\.79\+6\.7%28\.7030\.82\+7\.4%80025\.8926\.61\+2\.8%30\.6631\.37\+2\.3%29\.0029\.92\+3\.2%32\.5933\.54\+2\.9%160027\.1127\.27\+0\.6%32\.2732\.32\+0\.2%30\.8330\.95\+0\.4%34\.6334\.71\+0\.2%320027\.6527\.74\+0\.3%32\.9032\.96\+0\.2%31\.2631\.28\+0\.1%35\.1535\.18\+0\.1%M\-BEIR\(16\.16 / 22\.87\)1002\.862\.97\+3\.8%3\.884\.14\+6\.8%3\.533\.69\+4\.4%4\.214\.59\+8\.9%2007\.607\.71\+1\.4%10\.8910\.97\+0\.8%10\.1310\.35\+2\.1%12\.4712\.56\+0\.7%3009\.5610\.04\+5\.0%13\.6114\.42\+5\.9%12\.6113\.49\+7\.0%15\.3216\.40\+7\.1%50011\.6012\.57\+8\.4%16\.5217\.69\+7\.1%15\.3317\.01\+11\.0%18\.5220\.41\+10\.2%80013\.2813\.70\+3\.2%18\.5019\.25\+4\.0%17\.7918\.58\+4\.5%21\.4622\.16\+3\.2%160014\.4414\.98\+3\.7%20\.1020\.85\+3\.7%19\.5320\.26\+3\.7%23\.5124\.12\+2\.6%320015\.2715\.51\+1\.6%21\.1721\.48\+1\.5%20\.5920\.80\+1\.0%24\.5924\.75\+0\.7%

### B\.6Evaluation under Fixed Distance\-Computation Budgets

Search width is the standard query\-time control parameter for graph\-based ANN indices such as DiskANN and HNSW\. By controlling the size of the candidate set explored during graph search, it directly regulates search effort: with graph degree bounded byRR, the number of distance computations scales roughly asO⁡\(search width×R\)O\(\\textsc\{search width\}\\times R\)\. We therefore use search width as the primary query\-time budget parameter throughout our main evaluation\. Because the exact number of distance computations at a fixed width may vary with the graph topology, we additionally provide a complementary comparison of Vanilla andLGPunder the same explicit query–document distance\-computation budgets\.

Specifically, we vary the distance\-computation budget over\{100,200,300,500,800,1600,3200\}\\\{100,200,300,500,800,1600,3200\\\}and evaluate Vanilla andLGPon BRIGHT and M\-BEIR using Diver and CLIP embeddings, respectively, with DiskANN\. We report both greedy\-search performance and performance after reranking the top 20 retrieved candidates\. As shown in[Table17](https://arxiv.org/html/2609.36359#A2.T17),LGPconsistently outperforms Vanilla at every tested computation budget under both greedy search and reranking on both benchmarks\. The gains are largest at smaller and intermediate budgets\. For example, on BRIGHT at a budget of 200 distance computations,LGPimproves greedy\-search NDCG@10 and Recall@10 by33\.2%and34\.3%, while reranked NDCG@10 and Recall@10 improve by32\.0%and33\.1%, respectively\. Moreover, on Economics from BRIGHT and OVEN Task 8 from M\-BEIR,LGPoutperforms Vanilla in NDCG@10 under both greedy search and reranking with only half the distance\-computation budget \(800 vs\. 1,600 per query\), corresponding to 50% fewer computations\. As the computation budget increases and both methods approach exact retrieval, the gap naturally narrows\. These results show thatLGPimproves search efficiency by achieving higher retrieval quality under the same computation budget and comparable quality with substantially fewer distance evaluations\.

## Appendix CPrompts

### C\.1Prompt used inLLMSelect

TheLLMSelectoperation in our algorithm uses the prompt below\.

System PromptYou are editing a theorem retrieval graph at indexing time\.There is no real user query available, and you must not assume a particular test query\.Instead, privately simulate plausible latent user queries / problem intents for which the ANCHOR might be retrieved as a nearby theorem\.Your goal is to improve query\-time routing from the ANCHOR to useful answers\.First, if helpful, optionally write a short latent query line beginning with QUERY: ; then select at most the best candidates for shortcut edges\.For each CANDIDATE, ask: would a user query that lands near the ANCHOR also reasonably need this CANDIDATE as the target theorem, a prerequisite theorem, a bridge theorem, a generalization/special case, or a theorem used in the same proof/problem\-solving route?Select a CANDIDATE only if adding an edge ANCHOR \-\> CANDIDATE would help query\-time graph search route from the ANCHOR’s local neighborhood toward useful answers that are not already covered by the ALREADY\-SELECTED LOCAL NEIGHBORS\.Do NOT select based on wording similarity alone\.Do NOT select broad but unrelated facts\.If no candidate has a clear latent\-query/use\-case connection, return NONE\.Return at most \{B\} candidate numbers, best first, or NONE\. Examples: \[3\] \[1\] or NONE

User PromptANCHOR:\{anchor\}ALREADY\-SELECTED LOCAL NEIGHBORS:\{keep\_block\}CANDIDATE SHORTCUTS:\{cand\_block\}Privately imagine the latent queries/use\-cases, then choose which candidates should be connected to the ANCHOR for query\-time routing\. Return only candidate numbers or NONE\.If you include a latent query, start it with QUERY: on its own line\.

### C\.2Text Reranking Prompt

Text Reranking: System PromptYou are an intelligent assistant that can rank answers based on their relevancy to the query\.I will provide you with \{N\} passages, each indicated by number identifier \[\]\.Rank the answers based on their relevance to query: \{QUERY\}\.

Text Reranking: User Prompt\[1\] \{passage\_1\}\.\.\.\[\{N\}\] \{passage\_N\}Query: \{QUERY\}\.Rank the \{N\} passages above based on their relevance to the query\.The passages should be listed in descending order using identifiers\.The most relevant passages should be listed first\.The output format should be like \[1\] \> \[2\] \.\.\. \> \[\{N\}\]\.Only response the ranking results, do not say any word or explain\.

### C\.3Multimodal Reranking Prompt

Multimodal Reranking: System PromptYou rank retrieval candidates for multimodal retrieval\.Given one QUERY and several CANDIDATES, rank the candidates from best to worst match\.Use all available evidence, including image and text when present\.Return only an ordering of candidate indices like \[2\] \[1\] \[3\]\.

Multimodal Reranking: User ContentQUERY:Task instruction:\{task\_instruction\}Query text:\{query\_text\}<query image\>CANDIDATES:\[1\]Candidate 1 text:\{candidate\_1\_text\}<candidate 1 image\>\.\.\.\[\{N\}\]Candidate \{N\} text:\{candidate\_N\_text\}<candidate N image\>Rank the CANDIDATES from best to worst match for the QUERY\.Use image and text jointly when available\.Return only candidate indices like \[2\] \[1\] \[3\]\.

## Appendix DAlgorithms of DiskANN and HNSW

We provide the detailed algorithms of DiskANN in[Algorithms2](https://arxiv.org/html/2609.36359#alg2),[3](https://arxiv.org/html/2609.36359#alg3)and[4](https://arxiv.org/html/2609.36359#alg4)and HNSW in[Algorithms5](https://arxiv.org/html/2609.36359#alg5),[6](https://arxiv.org/html/2609.36359#alg6)and[7](https://arxiv.org/html/2609.36359#alg7)\. For HNSW,Nℓ​\(i\)N\_\{\\ell\}\(i\)denotes the outgoing neighborhood ofviv\_\{i\}at layerℓ\\ell, and the unlayered notationN⁡\(i\)N\(i\)used in our base\-layer pruning refers toN0​\(i\)N\_\{0\}\(i\)\. We denote the construction search width byLbuildL\_\{\\mathrm\{build\}\}and use a generic width argumentLLin the search routines below\. DiskANN construction usesL=LbuildL=L\_\{\\mathrm\{build\}\}\. HNSW insertion usesL=1L=1when descending through layers above the new node’s maximum level, andL=LbuildL=L\_\{\\mathrm\{build\}\}when searching layers in which the node is inserted\. At query time, DiskANN usesL=LsearchL=L\_\{\\mathrm\{search\}\}\. HNSW usesL=1L=1for upper\-layer descent andL=e​fsearchL=ef\_\{\\mathrm\{search\}\}for base\-layer search\.

Algorithm 2DiskANN Indexing1:InputDocument embeddings

\{𝒆⁡\(di\)\}i=1\|V\|\\\{\\bm\{e\}\(d\_\{i\}\)\\\}\_\{i=1\}^\{\|V\|\}, degree budget

RR, construction search width

LbuildL\_\{\\mathrm\{build\}\}, pruning parameter

α\\alpha
2:ResultGraph index

G=\(V,E\)G=\(V,E\)with local neighborhoods

\{N⁡\(i\)\}i=1\|V\|\\\{N\(i\)\\\}\_\{i=1\}^\{\|V\|\}
3:Initialize

GGas a random

RR\-regular graph over

V=\{v1,…,v\|V\|\}V=\\\{v\_\{1\},\\dots,v\_\{\|V\|\}\\\}
4:Let

ssbe the vertex whose embedding is closest to the centroid of

\{𝒆⁡\(di\)\}i=1\|V\|\\\{\\bm\{e\}\(d\_\{i\}\)\\\}\_\{i=1\}^\{\|V\|\}
5:for

t=1t=1to

22do

6:Sample a random permutation

σ\\sigmaof

\{1,…,\|V\|\}\\\{1,\\dots,\|V\|\\\}
7:for

k=1k=1to

\|V\|\|V\|do

8:

i←σ⁡\(k\)i\\leftarrow\\sigma\(k\)
9:

Ui←GreedySearch​\(s,vi,Lbuild\)U\_\{i\}\\leftarrow\\textsc\{GreedySearch\}\(s,v\_\{i\},L\_\{\\mathrm\{build\}\}\)
10:

N⁡\(i\)←RobustPruning​\(vi,Ui,α,R\)N\(i\)\\leftarrow\\textsc\{RobustPruning\}\(v\_\{i\},U\_\{i\},\\alpha,R\)
11:foreach

vj∈N⁡\(i\)v\_\{j\}\\in N\(i\)do

12:

N⁡\(j\)←N⁡\(j\)∪\{vi\}N\(j\)\\leftarrow N\(j\)\\cup\\\{v\_\{i\}\\\}
13:if

\|N⁡\(j\)\|\>R\|N\(j\)\|\>Rthen

14:

N⁡\(j\)←RobustPruning​\(vj,N⁡\(j\),α,R\)N\(j\)\\leftarrow\\textsc\{RobustPruning\}\(v\_\{j\},N\(j\),\\alpha,R\)

Algorithm 3GreedySearchin DiskANN1:InputStart point

ss, query point

qq, search width

LL
2:ResultVisited vertex list

UU
3:

A←\{s\}A\\leftarrow\\\{s\\\},

U←∅U\\leftarrow\\varnothing
4:while

A∖U≠∅A\\setminus U\\neq\\varnothingdo

5:

vj←arg⁡minx∈A∖U⁡D⁡\(x,q\)v\_\{j\}\\leftarrow\\arg\\min\_\{x\\in A\\setminus U\}D\(x,q\)
6:

A←A∪N⁡\(j\)A\\leftarrow A\\cup N\(j\)
7:

U←U∪\{vj\}U\\leftarrow U\\cup\\\{v\_\{j\}\\\}
8:if

\|A\|\>L\|A\|\>Lthen

9:

A←A\\leftarrowthe

LLvertices in

AAclosest to

qq
10:Sort

UUin increasing distance from

qq
11:return

UU

Algorithm 4RobustPruningin DiskANN1:InputVertex

viv\_\{i\}, candidate neighbor set

UU, pruning parameter

α\\alpha, degree limit

RR
2:ResultUpdated

N⁡\(i\)N\(i\), the set of out\-neighbors of

viv\_\{i\}
3:

U←\(U∪N⁡\(i\)\)∖\{vi\}U\\leftarrow\\left\(U\\cup N\(i\)\\right\)\\setminus\\\{v\_\{i\}\\\}
4:

N⁡\(i\)←∅N\(i\)\\leftarrow\\varnothing
5:while

U≠∅U\\neq\\varnothingand

\|N⁡\(i\)\|<R\|N\(i\)\|<Rdo

6:

vj←arg⁡minx∈U⁡D⁡\(x,vi\)v\_\{j\}\\leftarrow\\arg\\min\_\{x\\in U\}D\(x,v\_\{i\}\)
7:

N⁡\(i\)←N⁡\(i\)∪\{vj\}N\(i\)\\leftarrow N\(i\)\\cup\\\{v\_\{j\}\\\}
8:

U←U∖\{vj\}U\\leftarrow U\\setminus\\\{v\_\{j\}\\\}
9:

U←\{vk∈U:α​D​\(vj,vk\)\>D⁡\(vi,vk\)\}U\\leftarrow\\\{v\_\{k\}\\in U:\\alpha D\(v\_\{j\},v\_\{k\}\)\>D\(v\_\{i\},v\_\{k\}\)\\\}
10:return

N⁡\(i\)N\(i\)

Algorithm 5HNSW Insertion1:InputVertex

viv\_\{i\}, current entry point

ss, neighbor budget

RR, base\-layer degree cap

R0R\_\{0\}, construction search width

LbuildL\_\{\\mathrm\{build\}\}, level\-scale parameter

mℓm\_\{\\ell\}, flagsExtendCandidatesandKeepPruned

2:ResultUpdated HNSW graph after inserting

viv\_\{i\}
3:Sample the maximum level

ℓi\\ell\_\{i\}of

viv\_\{i\}according to the level distribution parameterized by

mℓm\_\{\\ell\}
4:Let

ℓmax\\ell\_\{\\max\}be the level of the current entry point

5:

Sentry←\{s\}S\_\{\\mathrm\{entry\}\}\\leftarrow\\\{s\\\}
6:for

ℓ=ℓmax,ℓmax−1,…,ℓi\+1\\ell=\\ell\_\{\\max\},\\ell\_\{\\max\}\-1,\\dots,\\ell\_\{i\}\+1do

7:

W←Search\-Layer​\(vi,Sentry,1,ℓ\)W\\leftarrow\\textsc\{Search\-Layer\}\(v\_\{i\},S\_\{\\mathrm\{entry\}\},1,\\ell\)
8:

Sentry←\{arg⁡minx∈W⁡D⁡\(x,vi\)\}S\_\{\\mathrm\{entry\}\}\\leftarrow\\\{\\arg\\min\_\{x\\in W\}D\(x,v\_\{i\}\)\\\}
9:for

ℓ=min⁡\(ℓmax,ℓi\),min⁡\(ℓmax,ℓi\)−1,…,0\\ell=\\min\(\\ell\_\{\\max\},\\ell\_\{i\}\),\\min\(\\ell\_\{\\max\},\\ell\_\{i\}\)\-1,\\dots,0do

10:

W←Search\-Layer​\(vi,Sentry,Lbuild,ℓ\)W\\leftarrow\\textsc\{Search\-Layer\}\(v\_\{i\},S\_\{\\mathrm\{entry\}\},L\_\{\\mathrm\{build\}\},\\ell\)
11:

Nℓ​\(i\)←Select\-Neighbors​\(vi,W,R,ℓ,ExtendCandidates,KeepPruned\)N\_\{\\ell\}\(i\)\\leftarrow\\textsc\{Select\-Neighbors\}\(v\_\{i\},W,R,\\ell,\\textsc\{ExtendCandidates\},\\textsc\{KeepPruned\}\)
12:Add bidirectional connections between

viv\_\{i\}and all nodes in

Nℓ​\(i\)N\_\{\\ell\}\(i\)at layer

ℓ\\ell
13:foreach

vj∈Nℓ​\(i\)v\_\{j\}\\in N\_\{\\ell\}\(i\)do

14:Let

Nℓ​\(j\)N\_\{\\ell\}\(j\)be the current neighborhood of

vjv\_\{j\}at layer

ℓ\\ell
15:if

ℓ=0\\ell=0and

\|Nℓ​\(j\)\|\>R0\|N\_\{\\ell\}\(j\)\|\>R\_\{0\}then

16:

Nℓ​\(j\)←Select\-Neighbors​\(vj,Nℓ​\(j\),R0,ℓ,ExtendCandidates,KeepPruned\)N\_\{\\ell\}\(j\)\\leftarrow\\textsc\{Select\-Neighbors\}\(v\_\{j\},N\_\{\\ell\}\(j\),R\_\{0\},\\ell,\\textsc\{ExtendCandidates\},\\textsc\{KeepPruned\}\)
17:elseif

ℓ\>0\\ell\>0and

\|Nℓ​\(j\)\|\>R\|N\_\{\\ell\}\(j\)\|\>Rthen

18:

Nℓ​\(j\)←Select\-Neighbors​\(vj,Nℓ​\(j\),R,ℓ,ExtendCandidates,KeepPruned\)N\_\{\\ell\}\(j\)\\leftarrow\\textsc\{Select\-Neighbors\}\(v\_\{j\},N\_\{\\ell\}\(j\),R,\\ell,\\textsc\{ExtendCandidates\},\\textsc\{KeepPruned\}\)
19:

Sentry←WS\_\{\\mathrm\{entry\}\}\\leftarrow W
20:if

ℓi\>ℓmax\\ell\_\{i\}\>\\ell\_\{\\max\}then

21:Set the entry point of the graph to

viv\_\{i\}

Algorithm 6Search\-Layerin HNSW1:InputQuery

qq, entry\-point set

SentryS\_\{\\mathrm\{entry\}\}, search width

LL, layer

ℓ\\ell
2:ResultCandidate set

WW
3:

Vseen←SentryV\_\{\\mathrm\{seen\}\}\\leftarrow S\_\{\\mathrm\{entry\}\},

𝒞←Sentry\\mathcal\{C\}\\leftarrow S\_\{\\mathrm\{entry\}\},

W←SentryW\\leftarrow S\_\{\\mathrm\{entry\}\}
4:while

𝒞≠∅\\mathcal\{C\}\\neq\\varnothingdo

5:

vj←arg⁡minx∈𝒞⁡D⁡\(x,q\)v\_\{j\}\\leftarrow\\arg\\min\_\{x\\in\\mathcal\{C\}\}D\(x,q\)
6:

𝒞←𝒞∖\{vj\}\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\setminus\\\{v\_\{j\}\\\}
7:

vf←arg⁡maxx∈W⁡D⁡\(x,q\)v\_\{f\}\\leftarrow\\arg\\max\_\{x\\in W\}D\(x,q\)
8:if

D⁡\(vj,q\)\>D⁡\(vf,q\)D\(v\_\{j\},q\)\>D\(v\_\{f\},q\)then

9:break

10:foreach

vk∈Nℓ​\(j\)v\_\{k\}\\in N\_\{\\ell\}\(j\)do

11:if

vk∉Vseenv\_\{k\}\\notin V\_\{\\mathrm\{seen\}\}then

12:

Vseen←Vseen∪\{vk\}V\_\{\\mathrm\{seen\}\}\\leftarrow V\_\{\\mathrm\{seen\}\}\\cup\\\{v\_\{k\}\\\}
13:

vf←arg⁡maxx∈W⁡D⁡\(x,q\)v\_\{f\}\\leftarrow\\arg\\max\_\{x\\in W\}D\(x,q\)
14:if

\|W\|<L\|W\|<Lor

D⁡\(vk,q\)<D⁡\(vf,q\)D\(v\_\{k\},q\)<D\(v\_\{f\},q\)then

15:

𝒞←𝒞∪\{vk\}\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\cup\\\{v\_\{k\}\\\}
16:

W←W∪\{vk\}W\\leftarrow W\\cup\\\{v\_\{k\}\\\}
17:if

\|W\|\>L\|W\|\>Lthen

18:

vf←arg⁡maxx∈W⁡D⁡\(x,q\)v\_\{f\}\\leftarrow\\arg\\max\_\{x\\in W\}D\(x,q\)
19:

W←W∖\{vf\}W\\leftarrow W\\setminus\\\{v\_\{f\}\\\}
20:return

WW

Algorithm 7Select\-Neighborsin HNSW1:InputVertex

viv\_\{i\}, candidate set

𝒞\\mathcal\{C\}, neighbor budget

RR, layer

ℓ\\ell, flagsExtendCandidatesandKeepPruned

2:ResultSelected neighbor set

SS
3:

S←∅S\\leftarrow\\varnothing
4:

W←𝒞W\\leftarrow\\mathcal\{C\}
5:ifExtendCandidatesthen

6:foreach

vj∈𝒞v\_\{j\}\\in\\mathcal\{C\}do

7:foreach

vk∈Nℓ​\(j\)v\_\{k\}\\in N\_\{\\ell\}\(j\)do

8:if

vk∉Wv\_\{k\}\\notin Wthen

9:

W←W∪\{vk\}W\\leftarrow W\\cup\\\{v\_\{k\}\\\}
10:

Wdiscard←∅W\_\{\\mathrm\{discard\}\}\\leftarrow\\varnothing
11:while

W≠∅W\\neq\\varnothingand

\|S\|<R\|S\|<Rdo

12:

vj←arg⁡minx∈W⁡D⁡\(x,vi\)v\_\{j\}\\leftarrow\\arg\\min\_\{x\\in W\}D\(x,v\_\{i\}\)
13:

W←W∖\{vj\}W\\leftarrow W\\setminus\\\{v\_\{j\}\\\}
14:if

D⁡\(vj,vi\)≤D⁡\(vj,vk\),∀vk∈SD\(v\_\{j\},v\_\{i\}\)\\leq D\(v\_\{j\},v\_\{k\}\),\\ \\forall v\_\{k\}\\in Sthen

15:

S←S∪\{vj\}S\\leftarrow S\\cup\\\{v\_\{j\}\\\}
16:else

17:

Wdiscard←Wdiscard∪\{vj\}W\_\{\\mathrm\{discard\}\}\\leftarrow W\_\{\\mathrm\{discard\}\}\\cup\\\{v\_\{j\}\\\}
18:ifKeepPrunedthen

19:while

Wdiscard≠∅W\_\{\\mathrm\{discard\}\}\\neq\\varnothingand

\|S\|<R\|S\|<Rdo

20:

vj←arg⁡minx∈Wdiscard⁡D⁡\(x,vi\)v\_\{j\}\\leftarrow\\arg\\min\_\{x\\in W\_\{\\mathrm\{discard\}\}\}D\(x,v\_\{i\}\)
21:

Wdiscard←Wdiscard∖\{vj\}W\_\{\\mathrm\{discard\}\}\\leftarrow W\_\{\\mathrm\{discard\}\}\\setminus\\\{v\_\{j\}\\\}
22:

S←S∪\{vj\}S\\leftarrow S\\cup\\\{v\_\{j\}\\\}
23:return

SS

Algorithm 8LLM\-Guided Graph Pruning \(LGP\)1:InputANN graph

GG, current node

viv\_\{i\}, neighborhood

N⁡\(i\)N\(i\), and index\-specific candidate set

UiU\_\{i\}
2:ParametersDegree cap

RR, shortlist budget

MM, per\-node edit budget

BB, neighborhood context size

KK, and threshold

gming\_\{\\min\}
3:

⊳\\triangleright/\* Form a local replacement set \*/

4:

Ti←\(⋃vj∈N⁡\(i\)N⁡\(j\)\)∖\{vi\}T\_\{i\}\\leftarrow\\left\(\\bigcup\_\{v\_\{j\}\\in N\(i\)\}N\(j\)\\right\)\\setminus\\\{v\_\{i\}\\\}
5:

Ui←\(Ui∪Ti\)∖\(N⁡\(i\)∪\{vi\}\)U\_\{i\}\\leftarrow\\left\(U\_\{i\}\\cup T\_\{i\}\\right\)\\setminus\\left\(N\(i\)\\cup\\\{v\_\{i\}\\\}\\right\)
6:

⊳\\triangleright/\* Shortlist local replacement candidates without LLM calls \*/

7:foreach

vc∈Uiv\_\{c\}\\in U\_\{i\}do

8:

gi​\(c\)←\|N⁡\(c\)∖Ti\|g\_\{i\}\(c\)\\leftarrow\|N\(c\)\\setminus T\_\{i\}\|
9:

νi​\(c\)←minvj∈N⁡\(i\)⁡D⁡\(vc,vj\)\\nu\_\{i\}\(c\)\\leftarrow\\min\_\{v\_\{j\}\\in N\(i\)\}D\(v\_\{c\},v\_\{j\}\)
10:

δi​\(c\)←D⁡\(vi,vc\)\\delta\_\{i\}\(c\)\\leftarrow D\(v\_\{i\},v\_\{c\}\)
11:

Lg←Sort↓​\(Ui,gi\)L\_\{g\}\\leftarrow\\textsc\{Sort\}\_\{\\downarrow\}\(U\_\{i\};g\_\{i\}\)
12:

Lν←Sort↓​\(Ui,νi\)L\_\{\\nu\}\\leftarrow\\textsc\{Sort\}\_\{\\downarrow\}\(U\_\{i\};\\nu\_\{i\}\)
13:

Lδ←Sort↓​\(Ui,δi\)L\_\{\\delta\}\\leftarrow\\textsc\{Sort\}\_\{\\downarrow\}\(U\_\{i\};\\delta\_\{i\}\)
14:

msrc←⌊M/3⌋m\_\{\\mathrm\{src\}\}\\leftarrow\\lfloor M/3\\rfloor
15:

Ui←U\_\{i\}\\leftarrowthe first

MMdistinct candidates in

Lδ\[:msrc\]∥Lg\[:msrc\]∥LνL\_\{\\delta\}\[1\\\!:\\\!m\_\{\\mathrm\{src\}\}\]\\,\\\|\\,L\_\{g\}\[1\\\!:\\\!m\_\{\\mathrm\{src\}\}\]\\,\\\|\\,L\_\{\\nu\}
16:

⊳\\triangleright/\* Select semantically useful candidates with an LLM \*/

17:

𝒦i←\\mathcal\{K\}\_\{i\}\\leftarrowthe

min⁡\(K,\|N⁡\(i\)\|\)\\min\(K,\|N\(i\)\|\)nodes in

N⁡\(i\)N\(i\)closest to

viv\_\{i\}
18:

𝒜i←LLMSelect​\(vi,𝒦i,Ui,B\)\\mathcal\{A\}\_\{i\}\\leftarrow\\textsc\{LLMSelect\}\(v\_\{i\},\\mathcal\{K\}\_\{i\},U\_\{i\},B\)
19:

⊳\\triangleright/\* Local edge pruning and replacement \*/

20:

N′​\(i\)←N​\(i\)N^\{\\prime\}\(i\)\\leftarrow N\(i\)
21:foreach

vc∈𝒜iv\_\{c\}\\in\\mathcal\{A\}\_\{i\}in selection orderdo

22:if

vc∈N′​\(i\)v\_\{c\}\\in N^\{\\prime\}\(i\)or

gi​\(c\)<gming\_\{i\}\(c\)<g\_\{\\min\}then

23:continue

24:if

\|N′​\(i\)\|<R\|N^\{\\prime\}\(i\)\|<Rthen

25:

N′​\(i\)←N′​\(i\)∪\{vc\}N^\{\\prime\}\(i\)\\leftarrow N^\{\\prime\}\(i\)\\cup\\\{v\_\{c\}\\\}
26:continue

27:if

N′​\(i\)∩N⁡\(i\)=∅N^\{\\prime\}\(i\)\\cap N\(i\)=\\varnothingthen

28:continue

29:foreach original neighbor

vj∈N′​\(i\)∩N⁡\(i\)v\_\{j\}\\in N^\{\\prime\}\(i\)\\cap N\(i\)do

30:

ℓi​\(j\)←\|N⁡\(j\)∖\(\(⋃vk∈N′​\(i\)∖\{vj\}N⁡\(k\)\)∖\{vi\}\)\|\\ell\_\{i\}\(j\)\\leftarrow\\left\|N\(j\)\\setminus\\left\(\\left\(\\bigcup\_\{v\_\{k\}\\in N^\{\\prime\}\(i\)\\setminus\\\{v\_\{j\}\\\}\}N\(k\)\\right\)\\setminus\\\{v\_\{i\}\\\}\\right\)\\right\|
31:

νi−j​\(j\)←minvk∈N′​\(i\)∖\{vj\}⁡D⁡\(vj,vk\)\\nu\_\{i\}^\{\-j\}\(j\)\\leftarrow\\min\_\{v\_\{k\}\\in N^\{\\prime\}\(i\)\\setminus\\\{v\_\{j\}\\\}\}D\(v\_\{j\},v\_\{k\}\)
32:

vw←arg⁡minvj∈N′​\(i\)∩N⁡\(i\)lex⁡\(ℓi​\(j\),νi−j​\(j\)\)v\_\{w\}\\leftarrow\\arg\\min^\{\\mathrm\{lex\}\}\_\{v\_\{j\}\\in N^\{\\prime\}\(i\)\\cap N\(i\)\}\\left\(\\ell\_\{i\}\(j\),\\nu\_\{i\}^\{\-j\}\(j\)\\right\)
33:

N′​\(i\)←\(N′​\(i\)∖\{vw\}\)∪\{vc\}N^\{\\prime\}\(i\)\\leftarrow\\left\(N^\{\\prime\}\(i\)\\setminus\\\{v\_\{w\}\\\}\\right\)\\cup\\\{v\_\{c\}\\\}
34:return

N′​\(i\)N^\{\\prime\}\(i\)

## Appendix EDetailedLGPAlgorithms and Index\-Specific Instantiations

[Algorithm8](https://arxiv.org/html/2609.36359#alg8)provides the detailed algorithm forLGP\. We first describe its candidate construction, semantic selection, and edge\-replacement steps, and then show how the same local update is instantiated in DiskANN and HNSW\.

Efficient Local Candidate Set Construction\.For each nodeviv\_\{i\}in the given ANN graphGG,LGPforms a local set of possible replacement neighbors𝒞i\\mathcal\{C\}\_\{i\}rather than considering every node in the graph\. Since most graph\-based ANN methods already produce a candidate set when selecting or updating the outgoing neighborhoodN⁡\(i\)N\(i\)ofviv\_\{i\},LGPreuses this set, denoted byUiU\_\{i\}, as its initial replacement set and augments it with the nodes exposed throughN⁡\(i\)N\(i\)\(lines 3\-5 in[Algorithm8](https://arxiv.org/html/2609.36359#alg8)\):

Ti:=\(⋃vj∈N⁡\(i\)N⁡\(j\)\)∖\{vi\},Ui:=\(Ui∪Ti\)∖\(N⁡\(i\)∪\{vi\}\)\.T\_\{i\}:=\\left\(\\bigcup\_\{v\_\{j\}\\in N\(i\)\}N\(j\)\\right\)\\setminus\\\{v\_\{i\}\\\},\\qquad U\_\{i\}:=\\left\(U\_\{i\}\\cup T\_\{i\}\\right\)\\setminus\\left\(N\(i\)\\cup\\\{v\_\{i\}\\\}\\right\)\.\(2\)Here,TiT\_\{i\}contains the nodes reachable fromviv\_\{i\}in two directed hops through its current neighbors, excludingviv\_\{i\}itself\. After removing existing neighbors, the updatedUiU\_\{i\}therefore contains local non\-neighbor alternatives drawn from both the index\-specific candidate set and the directed two\-hop neighborhood\.

To bound the cost of LLM\-guided selection and avoid excessively long contexts,LGPfurther reducesUiU\_\{i\}to at mostMMcandidates\. \(lines 6–15 in[Algorithm1](https://arxiv.org/html/2609.36359#alg1)\)\. For each candidate nodevc∈Uiv\_\{c\}\\in U\_\{i\},LGPconsiders three complementary ranking signals:

δi​\(c\):=D⁡\(vi,vc\),gi​\(c\):=\|N⁡\(c\)∖Ti\|,νi​\(c\):=minvj∈N⁡\(i\)⁡D⁡\(vc,vj\)\.\\delta\_\{i\}\(c\):=D\(v\_\{i\},v\_\{c\}\),\\qquad g\_\{i\}\(c\):=\|N\(c\)\\setminus T\_\{i\}\|,\\qquad\\nu\_\{i\}\(c\):=\\min\_\{v\_\{j\}\\in N\(i\)\}D\(v\_\{c\},v\_\{j\}\)\.\(3\)Here,δi​\(c\)\\delta\_\{i\}\(c\)measures proximity toviv\_\{i\},gi​\(c\)g\_\{i\}\(c\)measures the additional two\-hop coverage introduced byvcv\_\{c\}, andνi​\(c\)\\nu\_\{i\}\(c\)is its distance to the closest current neighbor, with larger values indicating less geometric redundancy\. LetLgL\_\{g\},LνL\_\{\\nu\}, andLδL\_\{\\delta\}denote the rankings ofUiU\_\{i\}by decreasinggi​\(c\)g\_\{i\}\(c\), decreasingνi​\(c\)\\nu\_\{i\}\(c\), and increasingδi​\(c\)\\delta\_\{i\}\(c\), respectively\.LGPforms𝒫i\\mathcal\{P\}\_\{i\}by taking up toM/3M/3candidates fromLδL\_\{\\delta\}, up to⌊M/3⌋\\lfloor M/3\\rfloorfromLgL\_\{g\}, and filling the remaining positions fromLνL\_\{\\nu\}\.

LLM\-Guided Semantic Selection\.Given the compact candidate shortlist,LGPprovides the LLM with the document represented byviv\_\{i\}, a compact neighborhood context𝒦i\\mathcal\{K\}\_\{i\}consisting of themin⁡\(K,\|N⁡\(i\)\|\)\\min\(K,\|N\(i\)\|\)neighbors inN⁡\(i\)N\(i\)closest toviv\_\{i\}in embedding space, and the candidate documents inUiU\_\{i\}\. The LLM is then asked to select at mostBBcandidates that extend rather than repeat the information already represented in𝒦i\\mathcal\{K\}\_\{i\}, for example by providing missing supporting context, connectingviv\_\{i\}to a complementary concept, or extending its content toward a useful specialization or next step\. The selected candidates form a proposal replacement set𝒜i⊆Ui\\mathcal\{A\}\_\{i\}\\subseteq U\_\{i\}\(lines 16–18 in[Algorithm8](https://arxiv.org/html/2609.36359#alg8)\)\.

Algorithm 9DiskANN construction withLGP\.Coloredlines indicate operations introduced byLGP\.1:InputDocument embeddings

\{𝒆⁡\(di\)\}i=1\|V\|\\\{\\bm\{e\}\(d\_\{i\}\)\\\}\_\{i=1\}^\{\|V\|\}, degree budget

RR, construction search width

LbuildL\_\{\\mathrm\{build\}\}, pruning parameter

α\\alpha, andLGPparameters

\(B,M,K,gmin\)\(B,M,K,g\_\{\\min\}\)
2:ResultGraph index

G=\(V,E\)G=\(V,E\)with refined neighborhoods

\{N⁡\(i\)\}i=1\|V\|\\\{N\(i\)\\\}\_\{i=1\}^\{\|V\|\}
3:Initialize

GGas a random

RR\-regular graph and choose the centroid\-nearest entry point

ss
4:for

t=1t=1to

22do

5:Sample a random permutation

σ\\sigmaof

\{1,…,\|V\|\}\\\{1,\\dots,\|V\|\\\}
6:for

k=1k=1to

\|V\|\|V\|do

7:

i←σ⁡\(k\)i\\leftarrow\\sigma\(k\)
8:

Ui←GreedySearch​\(s,vi,Lbuild\)U\_\{i\}\\leftarrow\\textsc\{GreedySearch\}\(s,v\_\{i\},L\_\{\\mathrm\{build\}\}\)
9:

N⁡\(i\)←RobustPruning​\(vi,Ui,α,R\)N\(i\)\\leftarrow\\textsc\{RobustPruning\}\(v\_\{i\},U\_\{i\},\\alpha,R\)
10:

Npre​\(i\)←N​\(i\)N\_\{\\mathrm\{pre\}\}\(i\)\\leftarrow N\(i\)
11:if

t=2t=2then

12:N⁡\(i\)←LGP​\(G,vi,N⁡\(i\),Ui,R,M,B,K,gmin\)N\(i\)\\leftarrow\\textsc\{LGP\}\(G,v\_\{i\},N\(i\),U\_\{i\},R,M,B,K,g\_\{\\min\}\)

13:foreach

vj∈N⁡\(i\)v\_\{j\}\\in N\(i\)do

14:Insert

viv\_\{i\}into

N⁡\(j\)N\(j\)if absent

15:if

\|N⁡\(j\)\|\>R\|N\(j\)\|\>Rthen

16:if

t=2t=2and

vj∈N⁡\(i\)∖Npre​\(i\)v\_\{j\}\\in N\(i\)\\setminus N\_\{\\mathrm\{pre\}\}\(i\)then

17:N⁡\(j\)←RobustPruning\-Protected​\(vj,N⁡\(j\),α,R,vi\)N\(j\)\\leftarrow\\textsc\{RobustPruning\-Protected\}\(v\_\{j\},N\(j\),\\alpha,R,v\_\{i\}\)

18:else

19:

N⁡\(j\)←RobustPruning​\(vj,N⁡\(j\),α,R\)N\(j\)\\leftarrow\\textsc\{RobustPruning\}\(v\_\{j\},N\(j\),\\alpha,R\)
20:return

GG

Algorithm 10Layer\-0 HNSW pruning withLGP\.Coloredlines indicate operations introduced byLGP\.1:InputCompleted Vanilla HNSW graph

GG, construction search width

LbuildL\_\{\\mathrm\{build\}\}, andLGPparameters

\(B,M,K,gmin\)\(B,M,K,g\_\{\\min\}\)
2:ResultRefined HNSW graph

GGwith unchanged upper layers

3:Freeze all upper layers, node levels, and the entry point

4:Sample a random permutationσ\\sigmaof\{1,…,\|V\|\}\\\{1,\\dots,\|V\|\\\}

5:for

k=1k=1to

\|V\|\|V\|do

6:

i←σ⁡\(k\)i\\leftarrow\\sigma\(k\)
7:

ri←\|N0​\(i\)\|r\_\{i\}\\leftarrow\|N\_\{0\}\(i\)\|
8:if

ri=0r\_\{i\}=0then

9:continue

10:Ui←U\_\{i\}\\leftarrowthe base\-layer candidates reached by hierarchical search forviv\_\{i\}using widthLbuildL\_\{\\mathrm\{build\}\}

11:

Npre​\(i\)←N0​\(i\)N\_\{\\mathrm\{pre\}\}\(i\)\\leftarrow N\_\{0\}\(i\)
12:N0​\(i\)←LGP\-Local​\(G,vi,N0​\(i\),Ui,ri,M,B,K,gmin\)N\_\{0\}\(i\)\\leftarrow\\textsc\{LGP\-Local\}\(G,v\_\{i\},N\_\{0\}\(i\),U\_\{i\},r\_\{i\},M,B,K,g\_\{\\min\}\)

13:Assert\|N0​\(i\)\|=ri\|N\_\{0\}\(i\)\|=r\_\{i\}

14:foreach

vc∈N0​\(i\)∖Npre​\(i\)v\_\{c\}\\in N\_\{0\}\(i\)\\setminus N\_\{\\mathrm\{pre\}\}\(i\)such that

vi∉N0​\(c\)v\_\{i\}\\notin N\_\{0\}\(c\)do

15:Hc←Select\-Neighbors​\(vc,N0​\(c\)∪\{vi\},\|N0​\(c\)\|,0,false,false\)H\_\{c\}\\leftarrow\\textsc\{Select\-Neighbors\}\(v\_\{c\},N\_\{0\}\(c\)\\cup\\\{v\_\{i\}\\\},\|N\_\{0\}\(c\)\|,0,\\textsc\{false\},\\textsc\{false\}\)

16:if

vi∈Hcv\_\{i\}\\in H\_\{c\}then

17:if

N0​\(c\)∖Hc≠∅N\_\{0\}\(c\)\\setminus H\_\{c\}\\neq\\varnothingthen

18:vz←arg⁡maxvj∈N0​\(c\)∖Hc⁡D⁡\(vc,vj\)v\_\{z\}\\leftarrow\\arg\\max\_\{v\_\{j\}\\in N\_\{0\}\(c\)\\setminus H\_\{c\}\}D\(v\_\{c\},v\_\{j\}\)

19:N0​\(c\)←\(N0​\(c\)∖\{vz\}\)∪\{vi\}N\_\{0\}\(c\)\\leftarrow\\left\(N\_\{0\}\(c\)\\setminus\\\{v\_\{z\}\\\}\\right\)\\cup\\\{v\_\{i\}\\\}

20:Verify that all base\-layer degrees and all upper layers are unchanged

21:return

GG

Local Edge Replacement\.Before incorporating an LLM\-selected candidate,LGPapplies a lightweight structural filter with thresholdgming\_\{\\min\}, retaining only candidates that provide sufficient additional two\-hop coverage\. LetN′​\(i\)N^\{\\prime\}\(i\)denote the current working neighborhood ofviv\_\{i\}\. For each filtered candidatevc∈𝒜iv\_\{c\}\\in\\mathcal\{A\}\_\{i\},LGPadds it directly when\|N′​\(i\)\|<R\|N^\{\\prime\}\(i\)\|<R, and otherwise replaces a low\-value original neighborvwv\_\{w\}\(lines 19–33 in[Algorithm8](https://arxiv.org/html/2609.36359#alg8)\)\.

For each original neighborvj∈N′​\(i\)∩N⁡\(i\)v\_\{j\}\\in N^\{\\prime\}\(i\)\\cap N\(i\),LGPmeasures its unique two\-hop contribution and its redundancy with the remaining neighborhood:

ℓi​\(j\):=\|N⁡\(j\)∖\(\(⋃vk∈N′​\(i\)∖\{vj\}N⁡\(k\)\)∖\{vi\}\)\|,νi−j​\(j\):=minvk∈N′​\(i\)∖\{vj\}⁡D⁡\(vj,vk\)\.\\ell\_\{i\}\(j\):=\\left\|N\(j\)\\setminus\\left\(\\left\(\\bigcup\_\{v\_\{k\}\\in N^\{\\prime\}\(i\)\\setminus\\\{v\_\{j\}\\\}\}N\(k\)\\right\)\\setminus\\\{v\_\{i\}\\\}\\right\)\\right\|,\\qquad\\nu\_\{i\}^\{\-j\}\(j\):=\\min\_\{v\_\{k\}\\in N^\{\\prime\}\(i\)\\setminus\\\{v\_\{j\}\\\}\}D\(v\_\{j\},v\_\{k\}\)\.\(4\)Here,ℓi​\(j\)\\ell\_\{i\}\(j\)measures the unique two\-hop contribution ofvjv\_\{j\}relative to the remaining neighborhood, whileνi−j​\(j\)\\nu\_\{i\}^\{\-j\}\(j\)measures its distance to the closest remaining neighbor\.LGPselects the neighborvwv\_\{w\}to remove by lexicographically minimizing\(ℓi​\(j\),νi−j​\(j\)\)\\bigl\(\\ell\_\{i\}\(j\),\\nu\_\{i\}^\{\-j\}\(j\)\\bigr\)\. This identifies neighbors with little unique local coverage and high redundancy as the lowest\-value candidates for replacement\.

### E\.1Instantiation for Representative ANN Indices

[Algorithm8](https://arxiv.org/html/2609.36359#alg8)can be inserted into different graph\-based ANN indices without changing their query\-time search procedures\.[Algorithms9](https://arxiv.org/html/2609.36359#alg9)and[10](https://arxiv.org/html/2609.36359#alg10)give the concrete instantiations for DiskANN and HNSW, respectively\.

DiskANN\.As shown in[Algorithm9](https://arxiv.org/html/2609.36359#alg9),LGPis applied immediately afterRobustPruningduring the second DiskANN construction pass\. The vertices visited byGreedySearchare reused as the candidate setUiU\_\{i\}, after whichLGPrefinesN⁡\(i\)N\(i\)\. Newly introduced edges follow DiskANN’s usual reciprocal\-insertion step\. If a reciprocal insertion exceeds the degree bound, the newly inserted reciprocal edge is protected only during that immediate pruning operation\. The protected pruning operation retains this edge while pruning the other candidates to satisfy the degree boundRR\. This protection does not persist beyond that pruning operation\.

HNSW\.As shown in[Algorithm10](https://arxiv.org/html/2609.36359#alg10),LGPis applied as an offline pruning of layer 0 after the vanilla HNSW index has been constructed\. For each nodeviv\_\{i\}, hierarchical search is reused to obtain the candidate setUiU\_\{i\}, andLGPrefines only its base\-layer neighborhoodN0​\(i\)N\_\{0\}\(i\)while preserving its original degree\. For each newly introduced base\-layer edge, HNSW’s standardSelect\-Neighborsrule is applied to determine whether the corresponding reciprocal edge should be added\. All upper layers, node levels, and the entry point remain unchanged\.

## Appendix FExtended Related Work

Graph\-based Approximate Nearest Neighbor Search\.Approximate nearest neighbor search \(ANNS\) has been studied through several indexing paradigms, including partition\- and quantization\-based methods\([Jegou et al\., 2011](https://arxiv.org/html/2609.36359#bib.bib31);[Johnson et al\., 2021](https://arxiv.org/html/2609.36359#bib.bib32)\)as well as graph\-based methods\([Malkov and Yashunin, 2020](https://arxiv.org/html/2609.36359#bib.bib3);[Fu et al\., 2019](https://arxiv.org/html/2609.36359#bib.bib4);[Jayaram Subramanya et al\., 2019](https://arxiv.org/html/2609.36359#bib.bib5)\), among which graph\-based ANNS has emerged as one of the most effective and widely adopted approaches in practical tasks such document retrieval\([Arslan et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib6)\), offering a strong balance between search quality and efficiency\. These methods typically construct a proximity graph over high\-dimensional vector representations and answer a query by greedily traversing the graph toward its nearest neighbors\([Jayaram Subramanya et al\., 2019](https://arxiv.org/html/2609.36359#bib.bib5)\)\.

Early graph\-based approaches, such as FANNG\([Harwood and Drummond, 2016](https://arxiv.org/html/2609.36359#bib.bib1)\)and EFANNA\([Fu and Cai, 2016](https://arxiv.org/html/2609.36359#bib.bib2)\), accelerate search through neighbor expansion over approximate KNN graphs\. HNSW later introduced a hierarchical navigable small\-world graph that enables highly effective greedy search and has become a standard index for high\-recall in\-memory vector retrieval\([Malkov and Yashunin, 2020](https://arxiv.org/html/2609.36359#bib.bib3)\)\. NSG further improves this line of work by explicitly optimizing graph connectivity, path length, and index size, yielding a sparse yet highly navigable graph structure\([Fu et al\., 2019](https://arxiv.org/html/2609.36359#bib.bib4)\)\. At larger scales, DiskANN and its Vamana graph construction algorithm\([Jayaram Subramanya et al\., 2019](https://arxiv.org/html/2609.36359#bib.bib5)\)extend graph\-based ANNS to billion\-scale, SSD\-resident settings, demonstrating strong empirical performance in large\-scale retrieval despite limited theoretical guarantees\([Indyk and Xu, 2023](https://arxiv.org/html/2609.36359#bib.bib28)\)\. Building on this, FreshDiskANN supports real\-time insertions and deletions\([Singh et al\., 2021](https://arxiv.org/html/2609.36359#bib.bib29)\), while Filtered\-DiskANN further enables native support for filtered ANN queries\([Gollapudi et al\., 2023](https://arxiv.org/html/2609.36359#bib.bib30)\)\. Despite this progress, graph construction in existing ANNS methods remains fundamentally geometric and structural: edges are selected or pruned primarily based on vector proximity, graph sparsity, and navigability\. As a result, these methods do not explicitly account for whether neighboring nodes are semantically redundant, complementary, or equally useful for downstream retrieval\. Although stronger embedding models can improve the alignment between geometry and semantics\([Chen et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib33);[Meng et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib35);[OpenAI, 2024](https://arxiv.org/html/2609.36359#bib.bib36)\), a gap still remains between geometric proximity and semantic informativeness for retrieval\([Taghavi et al\., 2026](https://arxiv.org/html/2609.36359#bib.bib27)\)\. Our work complements this by introducing an*offline*LLM\-guided pruning paradigm on top of an existing vector\-based ANN graph, where, instead of modifying query\-time search, our method actively prunes local graph structure toward more semantically coherent neighborhoods while preserving the original navigation efficiency at test time\.

LLM\-Augmented Retrieval at Test Time\.A separate line of work improves document retrieval by introducing stronger reasoning at inference time, especially for complex queries where embedding similarity is insufficient for realistic tasks that require nontrivial reasoning to identify the most relevant documents\([SU et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib7)\)\. Existing LLM\-augmented retrieval methods mainly improve retrieval quality in three directions\. Some methods enhance the given queries by rewriting or reformulating the input before retrieval, with the goal of better aligning the search request with relevant documents\([Ma et al\., 2023](https://arxiv.org/html/2609.36359#bib.bib26);[Chan et al\., 2024](https://arxiv.org/html/2609.36359#bib.bib8)\)\. Another line of work strengthens the retriever itself by learning reasoning\-aware retrieval representations\. Representative examples include INF\-X\-Retriever\([Yao et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib9)\), a single\-stage dense retrieval framework for reasoning\-intensive search that emphasizes intent\-aligned retrieval, ReasonIR\([Shao et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib10)\), which trains retrievers specifically for general reasoning tasks, and RaDeR\([Das et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib25)\), which develops reasoning\-aware dense retrieval models using synthesized supervision from reasoning trajectories\. Furthermore, some approaches improve retrieval by introducing stronger reasoning at the reranking stage, where direct rerankers rescore an initial candidate set returned by a first\-stage retriever\([Sun et al\., 2026](https://arxiv.org/html/2609.36359#bib.bib11);[Zhang et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib24);[Liu et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib23)\)\. For example, REARANK\([Zhang et al\., 2025](https://arxiv.org/html/2609.36359#bib.bib24)\)performs listwise reasoning\-based reranking over retrieved candidates\.

While they show strong empirical performance, these approaches primarily inject additional semantic reasoning at test time, which increases latency and serving cost while leaving the fundamental mismatch between geometry and semantics in the underlying graph unresolved\. In contrast, our method uses LLM reasoning offline to refine local graph connectivity and address this structural misalignment at its root, thereby improving the retrieval index itself and reducing the need for further LLM assistance at test time\.

Query\-Time Graph Search Algorithms\.Recent work has also explored improving graph\-index retrieval from the query\-time side by changing the search algorithm rather than the graph construction process\. For example,[Xu et al\. \(2026\)](https://arxiv.org/html/2609.36359#bib.bib34)builds the data structure using a cheap proxy metric but modifies the query procedure to approximate an expensive ground\-truth metric, while reranker\-guided search[Xu and Chen \(2026\)](https://arxiv.org/html/2609.36359#bib.bib19)alters query\-time graph traversal to decide which candidates should be evaluated by a stronger reranker under a limited budget\. These methods are complementary to ours: they keep the graph largely unchanged but introduce a more involved online search procedure\. In contrast, our method uses LLM reasoning offline to refine the graph structure itself, without requiring any change to the query\-time search algorithm\. As a result, our refined graph remains compatible with standard greedy search and can also be combined with reranker\-guided or bi\-metric query\-time search strategies\.

相似文章

GraphInfer-Bench:在图上的LLM推理能力基准测试

arXiv cs.LG

介绍了GraphInfer-Bench,这是一个基准测试,用于评估LLMs是否能够进行图推理——生成关于节点及其邻域的开放式答案,这些答案无法从单个节点或路径中检索到。实验表明,即使是最前沿的LLMs在这些任务上也落后于普通GNNs,揭示了一个能力差距。