acceptodds
Under review as a conference paper at ICLR 2027

CorpusWalker: Reasoning-Guided Graph Exploration for Search

12 views

Abstract

Retrieve-then-rerank pipelines are limited by the recall of the first-stage retriever. Graph-based adaptive reranking alleviates this issue by expanding the candidate pool at test time. Existing adaptive reranking approaches are driven by the reranker's relevance score as a feedback signal over a single, fixed neighborhood graph. This poses a challenge for reasoning-intensive retrieval tasks (such as those covered in the BRIGHT benchmark) because reasoning-intensive relevance depends on the reasoning path needed to arrive at the answer. This breaks the assumption of standard reranker-guided graph exploration techniques, since similar documents are not necessarily both relevant in a reasoning setting. In this work, we argue that graph exploration is itself a reasoning task. Therefore, we propose CorpusWalker, which separates graph exploration from document ranking. During traversal, an LLM agent reads offline-extracted document features of the current pool and, at each turn, reasons about information needs, chooses which document to expand and the corresponding relation to follow. The trace of this exploration tracks the documents the agent expanded, and the corresponding reasoning serves as context for our Meta Reranker, which ranks the entire pool in one pass. On reasoning-intensive retrieval benchmarks (BRIGHT and FreshStack), CorpusWalker outperforms retrieve-then-rerank and graph-based adaptive reranking baselines under the same document budget, improving nDCG@10 on BRIGHT by points and Recall@100 by points over the strongest of them, with up to points gain in nugget coverage on FreshStack.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Reasoning IR, Adaptive Re-ranking, Graph Exploration

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_1sNGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

CorpusWalker separates graph-based candidate discovery from final ranking. Starting from BM25 seeds, an LLM agent reads cached, query-independent document summaries and decides which document and which lexical or semantic neighborhood to expand. A Meta Reranker then ranks the resulting candidate pool using summaries, expansion rationales, and provenance from the traversal. The design aims to find useful evidence beyond an initial retrieval pool and reuse information already obtained during exploration. Experiments on BRIGHT and FreshStack compare candidate discovery, final ranking, and online computational cost under a 100-document candidate budget.

Critical strengths
  1. Evidence for both candidate discovery and reuse of traversal information (PDF pp. 6–9, Figure 2 and Tables 1–3). On BRIGHT, candidate Recall@100 increases from RGS's 50.1 to 54.8, while final nDCG@10 increases from 33.0 to 36.1. Reporting both measures is valuable: it distinguishes whether useful documents enter the pool from whether the final ranker places them near the top. The strongest component evidence is Table 3, which holds the candidate pool fixed and improves nDCG@10 from 32.8 with summaries and keywords to 36.1 with the complete traversal-information input. Because candidate discovery is held constant in this comparison, the ranking gain cannot be explained simply by supplying a better pool. This supports the practical value of reusing the traversal information package, including its provenance, ordering, and reasons for expansion. I regard that package as a supported contribution; isolating the prose rationale from every other trace element is not a prerequisite for recognizing this result.

  2. Complementary tasks and useful evidence about practical operation (PDF pp. 8–9 and Appendices A–G). FreshStack tests a different aspect of retrieval by rewarding coverage of distinct answer nuggets. CorpusWalker obtains alpha-nDCG@10 of 41.3 versus RGS's 39.3 and Coverage@20 of 67.8 versus 65.0. These results broaden the empirical case beyond BRIGHT's document-relevance measurements. The paper also provides the traversal and ranking prompts, illustrative walks, edge-use and traversal statistics, query-reasoning comparisons, and an agent-size study with the Meta Reranker fixed. Online token and call accounting includes invalid-action retries. Together, these analyses make the system's operation more inspectable and show how compressed document representations can reduce repeated reading during search and ranking. The cost results concern online operation; the summaries themselves are constructed offline. This is a useful deployment distinction, and the reported online savings deserve credit within that scope.

Critical weaknesses
  1. The exploration gain is not separated from the change in available representations and graph resources (PDF pp. 1–2, 6, 9 and 15–18, Figures 1–3/5–6 and Appendix D). The central hypothesis concerns reasoning about where to expand, rather than expanding according to current relevance. However, the comparison with RGS changes several ingredients at once: CorpusWalker uses compressed summaries instead of raw documents and can traverse lexical as well as semantic neighborhoods, whereas the evaluated RGS uses its semantic graph. The common BM25 seeding method, listwise LLM, and 100-document budget are useful controls. They make the comparison between the implemented systems informative, but they do not isolate the additional value of the proposed expansion decisions.

    The resource difference is consequential rather than merely hypothetical. Figure 1 and the example walks in Figure 6 show relevant documents reached through lexical edges that RGS cannot use. These examples explain a plausible advantage of the complete design, while leaving open whether a simpler policy with the same dual-graph access and summaries would recover much of the gain. The agent-size study and traversal statistics characterize the proposed agent; they do not provide that alternative-policy comparison. Likewise, Table 3 establishes the value of the trace package for ranking a fixed pool, but cannot determine why the exploration procedure found that pool.

    A focused comparison with a competitive relevance-guided or simple hybrid-graph policy, supplied with the same summaries and both graphs, would directly address this uncertainty. Candidate-pool recall or nugget coverage is the most informative first outcome, because it measures discovery before a different ranking input can affect the result. Reporting token and call costs alongside it would clarify whether the extra deliberation buys useful evidence. This concern limits the evidence for the paper's central exploration claim; it does not imply that the reported system improvements are incorrect or that the implemented baselines are illegitimate.

I lean toward weak rejection, close to the acceptance boundary. The improvements on two benchmarks, the useful online-cost analysis, and especially the same-pool trace-reuse result give the paper clear positive value. My reservation is concentrated on the exploration contribution: the current comparisons do not sufficiently distinguish better expansion decisions from better representations and additional graph access. A meaningful gain in pool quality over a competitive policy using the same resources would substantially strengthen the case for acceptance. If that policy instead recovered most of the gain at comparable or lower online cost, the contribution would be better supported as a system integration and ranking result, with a narrower claim about reasoning-guided discovery.

Questions for authors

For W1 — main priority: How does CorpusWalker compare with a competitive relevance-guided or clearly specified simple hybrid-graph policy using the same BM25 seeds, summaries, lexical/semantic graphs, LLM, and 100-document budget? Please prioritize candidate-pool Recall@100 or nugget coverage and token/call costs, which assess discovery before reranking. For the simple policy, state how it chooses both the expansion document and edge type. If final ranking is also compared, use a shared ranker with matched inputs so that trace availability does not introduce a second difference. This focused comparison would clarify whether the expansion policy itself is responsible for a meaningful portion of the observed gain.

6 comments
AuthorsOpenReview ↗

Response to Reviewer 1sNG (1/2)

Thank you for your valuable feedback. We would like to clarify the queries raised in the review as follows. We would like to clarify that we call the agent-based expansion mechanisms as strategy and not policy.

Q1. How does CorpusWalker compare with a competitive relevance-guided or clearly specified simple hybrid-graph policy using the same BM25 seeds, summaries, lexical/semantic graphs, LLM, and 100-document budget? For the simple policy, state how it chooses both the expansion document and edge type.

Response. We thank the reviewer for the feedback. We ran the experiment as requested: the same BM25 seeds, the same 100-document budget, the same two graphs, the same summaries, the same LLM and the same ranker, with the only difference being the expansion strategy. We report pool quality by Recall@100, LLM calls and token cost per query.

Expansion strategy (same seeds, budget, summaries, both graphs)Pool R@100nDCG@10LLM calls / queryTokens / query
CorpusWalker agent (paper)54.836.19.1 (+1 ranking)107k
RGS as published (raw text, semantic graph), for reference50.133.020.0122k
RGS's search strategy, both graphs (union)50.030.114.741k
RGS's search strategy, both graphs (alternating)50.530.318.050k
BM25 top-100, no expansion (reference)38.2–0–
Random document and edge (mean of 5 seeds)33.3–0–
Breadth-first (lexical / semantic / alternating / both graphs per turn)40.7 / 38.3 / 39.4 / 40.3–0–
Relevance-guided with perfect relevance labels (lexical / semantic / alternating edges)49.6 / 49.4 / 50.0–0–
We provide a brief summary of the methods in above comparison.
Simple Expansion Strategies: Random expands a uniformly random unexpanded pool document along a random edge type (mean of 55 seeds). Breadth-first expands pool documents in the order they entered the pool, along a fixed edge type (lexical or semantic), alternating edge types, or both graphs (hybrid neighbors after removing the duplicates) in the same turn.

Relevance Guided Expansion Strategies: Relevance-greedy with perfect labels expands the earliest-pooled unexpanded document that the qrels mark relevant, along a fixed or alternating edge type; it knows the true relevance of every document already in the pool, so it is an upper bound on any reranker-guided strategy. We agree that this is not practically possible but we want to see how much we gain from this expansion baseline. If there is no (more) gold document in the pool at any turn t, the first document in the unexpanded pool is expanded. RGS relies on re-ranker signal to guide exploration over document summaries and both the graphs. RGS performs this iteratively using either of the graphs in an alternating manner or union of 2 neighborhoods from both the graphs during each expansion.

The simple hybrid graph strategies barely beat the non-expanding baseline (BM25). The Breadth-first expansion reaches Recall@100 of 40.3% and random strategy degrades the BM25 baseline by 4.94.9 points which concludes that the availability of the graphs does not help if the expansion strategy is not good.

We then quantify the impact of relevance-guided expansion strategy, mainly relevance greedy that uses the gold labels and RGS that uses the ranker’s relevance. The relevance greedy achieves the Recall@100 of 49.6% lexical edges, 49.4% on semantic and 50.0% using alternating edges. Our CorpusWalker expansion outperforms this by 4.8 points and on 11 out of 12 subsets (we report per subset performance in Table 5 in revised pdf) except pony where the majority of the gold documents are 1-hop away from seed documents. In comparison to RGS, where it uses its own expansion strategy, when given the same resources as CorpusWalker, the pool quality does not change (50.0 Vs 50.5 and 50.1) when compared with given full document texts and single graphs. It even degrades the ranking performance when document summaries are used for reranking, nDCG@10 drops from 33.0 to 30.1, which shows that the documents summaries are not enough to get better ranking. The same observation we made in Table 3 when the same pool with document summaries was reranked using MetaReranker.

AuthorsOpenReview ↗

Response to Reviewer 1sNG (2/2)

Q2. If final ranking is also compared, use a shared ranker with matched inputs so that trace availability does not introduce a second difference. This focused comparison would clarify whether the expansion policy itself is responsible for a meaningful portion of the observed gain.

Response. We ran the shared listwise reranker (RankGPT or MetaReranker) over the matched inputs (raw texts or summaries). We only change the pool retrieved by RGS and CorpusWalker. We found that the CorpuWalker’s (ours) pool helps in improving the nDCG@10 by 1.4 points and Recall@10 by 2.1 points over the RGS baseline. We report per-subset performance in the updated version on Table 3 in the revised pdf. Next, we use the one-shot MetaReranker over a fixed pool and we compare the impact of availability of traces (similar to Table 3 in paper). The traces add 1.7 points gain in nDCG@10 and 2.1 in Recall@10. Hence these gains in the pool and ranking are separable and the Corpuswalker agent provides the gains as observed from our experiments.

PoolRankerdoc representationtraces (yes/no)nDCG@10R@10
CorpusWalkerRankGPTraw textno34.437.2
RGS as publishedRankGPTraw textno33.035.1
CorpusWalkerMetaRerankersummariesno32.836.1
CorpusWalkerMetaRerankersummariesyes36.139.3

Q3. A meaningful gain in pool quality over a competitive policy using the same resources would substantially strengthen the case for acceptance. If that policy instead recovered most of the gain at comparable or lower online cost, the contribution would be better supported as a system integration and ranking result, with a narrower claim about reasoning-guided discovery.

Response In comparison to the simple and relevance guided strategies, the ranker guided graph expansion strategy provides better performance, Recall@100 of 50.5% Vs Recall@100 of 40.3% by Breadth-first selection which comes at no cost (it is independent of document representations, e.g, raw or summary). On the other hand, RGS applies listwise ranking over the pool at each iteration resulting in more expensive LLM calls. In vanilla setup, RGS uses raw text of the documents exacerbating token costs and LLM calls in comparison to the CorpusWalker. However, our proposed document summaries help RGS to maintain the pool quality and reduce the token cost from 122k tokens/query to 50k tokens/query which makes the proposed component suitable for system integration to existing graph expansion strategies. But, since the vanilla RGS does not disentangle the exploration and ranking, these summaries degrade the ranking quality, for example with summaries nDCG@10 is 30.3 in comparison to the vanilla RGS over raw document text nDCG@10 is 33.0. However, this still falls behind the CorpusWalker’s pool quality which uses 107k tokens per query. But, the extra tokens leads to gains of 4.84.8 points in Recall@100 and 6.06.0 points in nDCg@10 in fewer LLM calls (10.1 Vs 14.7-20).

Thanks again for the feedback. We have tried to address all the concerns. We have also uploaded the revised pdf. We keep all changes in blue fonts. We look forward to answer any further queries.

AuthorsOpenReview ↗

A gentle reminder

Greetings Reviewer 1sNG,

Thank you for your time and valuable feedback. We have tried to address your queries regarding the contribution of the expansion strategy and comparison with relevance-guided strategies.. We have also uploaded the updated version of the paper. We would like to request if we have addressed your concerns. We are happy to answer any further queries. If we have addressed your concerns, we politely and respectfully request a reassessment of the rating in light of our response. Thank you for your time and consideration.

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

This paper proposes CorpusWalker, a framework for reasoning-intensive retrieval that separates graph exploration from document ranking. Starting from BM25 seed documents, a prompted LLM agent reads cached document summaries and selects which document to expand and whether to follow lexical or semantic edges. A Meta Reranker then ranks the expanded candidate pool in a single call using document summaries and exploration traces. Experiments on BRIGHT and FreshStack show improvements over retrieve-then-rerank and graph-based adaptive retrieval baselines.

Critical strengths

None

Critical weaknesses
  1. Limited conceptual novelty and insufficient differentiation from prior work. The broad claim that graph exploration benefits from reasoning capabilities has already been explored. MoR [1] uses query planning to guide mixed structural and textual traversal and incorporates traversal trajectories into reranking, while Graph-S³ [2] learns an interactive graph exploration policy with stepwise supervision. Although these methods address different graph settings, they establish closely related principles. The paper should more clearly identify its methodological advances beyond combining existing ideas and provide stronger comparisons with relevant approaches.

  2. Missing downstream RAG evaluation. The experiments evaluate retrieval and ranking metrics without testing whether the improvements translate into better generated answers. Although FreshStack measures answer-nugget coverage, this remains a retrieval-level proxy. An end-to-end RAG evaluation using a shared generator and fixed context budget would strengthen the evidence for downstream utility.

  3. Incomplete characterization of efficiency. The paper provides the agent prompt and an online token-cost analysis, but the efficiency comparison excludes the corpus-wide LLM preprocessing required to generate document summaries. Moreover, the baselines are not evaluated with the same compressed representations, leaving unclear how much of the reported savings comes from compression versus the proposed exploration and ranking design. Reporting preprocessing costs, amortized costs across query volumes, and end-to-end latency would make the efficiency claims more convincing.

  4. Insufficient controlled ablations of graph construction and exploration. The agent is implemented through a pretrained LLM with handcrafted instructions, but its decision policy is not isolated from the dual-graph design and final reranking procedure. The paper should compare lexical-only, semantic-only, and dual-graph configurations; evaluate agent-guided exploration against random, breadth-first, and relevance-greedy policies under matched settings; and compare adaptive edge selection with fixed or rule-based alternatives. Baseline reranking and Meta Reranking should also be evaluated on identical candidate pools, with and without exploration traces. The existing trace ablation addresses final ranking but does not establish the superiority of the agent’s exploration decisions.

[1] Mixture of Structural-and-Textual Retrieval over Text-rich Graph Knowledge Bases, ACL Findings 2025. [2] Enhancing Agentic Textual Graph Retrieval with Synthetic Stepwise Supervision, ACL 2026.

Questions for authors

None

6 comments
AuthorsOpenReview ↗

Response to Reviewer 9xYW (1/3)

Thank you for your comments. In the following we provide a few clarifications and details about changes made in the paper. We are enthusiastically looking forward to any further discussion.

Q1. Limited conceptual novelty and insufficient differentiation from prior work. The broad claim that graph exploration benefits from reasoning capabilities has already been explored. MoR [1] uses query planning to guide mixed structural and textual traversal and incorporates traversal trajectories into reranking, while Graph-S³ [2] learns an interactive graph exploration policy with stepwise supervision. Although these methods address different graph settings, they establish closely related principles. The paper should more clearly identify its methodological advances beyond combining existing ideas and provide stronger comparisons with relevant approaches.

Response. We thank the reviewer for the pointers and will add both to the related work and discuss them explicitly. Both mentioned papers work in different settings. MoR operates on a text-rich knowledge graph with an explicit schema. The planner produces a structured plan over known relation types, its reasoning step mixes structural and textual retrievers along that plan, and its reranker uses the resulting trajectories. Graph-S³ learns an interactive exploration strategy on textual graphs with synthetic step-level supervision. Both assume the graph is given and carries meaning (entities, typed relations), and both use structure that CorpusWalker does not have.

CorpusWalker addresses a plain document corpus and can be adapted to any corpus (wiki, maths, coding, etc. ). There is no schema or no supervision. Both graphs are induced (lexical nearest neighbours and dense nearest neighbours) and encode no relation semantics beyond lexical or semantic. The decision the agent makes is therefore different due to lack of schema and also requires reasoning to determine which of up to 100 candidate documents, described by summaries, is the most promising point to spend one of a fixed number of expansions on, and under which of two similarity views. Three elements have, to our knowledge, no counterpart in MoR or Graph-S³: (1) the budgeted pool-level decision with an explicit objective of marginal discovery (see our response to 18vY Q2); (2) the use of the agent's reasoning trace and the provenance of every candidate as evidence for one shot Meta Reranker (Table 3, +3.3 nDCG@10 on identical pools); (3) the finding that this training-free strategy beats a relevance-guided strategy that is given perfect relevance labels (general response). Neither MoR nor Graph-S³ has an implementation on unstructured corpora or on BRIGHT; a direct comparison would require re-deriving a graph schema for BRIGHT, which would be a different method. We will make the methodological advances explicit in the introduction and add a comparison paragraph.

Q2. Missing downstream RAG evaluation. The experiments evaluate retrieval and ranking metrics without testing whether the improvements translate into better generated answers. Although FreshStack measures answer-nugget coverage, this remains a retrieval-level proxy. An end-to-end RAG evaluation using a shared generator and fixed context budget would strengthen the evidence for downstream utility.

Response: We would like to point out that our primary motivation is reasoning-intensive retrieval tasks where the core goal is search and retrieval of relevant documents followed by ranking to ensure the most relevant documents appear in the top positions in the ranking list. In reasoning-intensive retrieval tasks, search and ranking of such relevant documents requires going beyond simple surface-level Both benchmarks used in our evaluation are for retrieving the part of golden answers themselves (passages in BRIGHT and nuggets in FreshStack) or documents cited in the gold answers and hence there is little to no scope for a generation task. Moreover, generation is not a standard task on BRIGHT and FreshStack and is also not the core focus of our work. We would also like to point out that document ranking in reasoning-intensive tasks is still a challenging, unsolved problem with practical implications for enterprise or expert search applications.

AuthorsOpenReview ↗

Response to Reviewer 9xYW (2/3)

Q3 (a) The efficiency comparison excludes the corpus-wide LLM preprocessing required to generate document summaries. Moreover, the baselines are not evaluated with the same compressed representations, leaving unclear how much of the reported savings comes from compression versus the proposed exploration and ranking design.

Response: The document summarization is one LLM call document: We ask summaries in one or two sentences plus a keywords list. The input is 466 tokens per document on average and the summary 78 tokens on average. This cost is paid once per corpus and does not grow with the number of queries. Since these summaries are generated offline (without seeing a query), this step does not cost in latency overheads while query processing. Also these summaries can be integrated to any exploration strategy. The table in the response of Q3(b) quantifies the token cost by RGS when it uses these summaries vs. the whole document texts for exploration. The token cost per query reduces from 121.7k to 50-53k while maintaining the pool quality (50.1 Vs. 50.5-49.2).

We compare our method with RGS (strongest baseline) and others when provided with the same compressed representations.

systemLLM calls / querytoken cost / querypool R@100nDCG@10
RGS as published (raw text, DiskANN graph)20.0121.7k50.133.0
RGS + our summaries, both graphs (union)14.740.8k50.030.1
RGS + our summaries, both graphs (alternating)18.050.0k50.530.3
RGS + our summaries, its own graph (single change)19.953.0k49.228.4
CorpusWalker9.1 (+1 ranking)107.1k54.836.1

We also add per-subset performance in the revised version of the paper (Table 6). We find that the compressed representation alone does not contribute to better pool quality, and the exploration strategy plays an important role.

Q3 (b) Reporting preprocessing costs, amortized costs across query volumes, and end-to-end latency would make the efficiency claims more convincing.

Response: We would like to point out that our efficiency claims are in terms of token cost per query. Since our method generates more output tokens due the reasoning on what document to expand and why. Therefore, by design our method contributes to latency in comparison to RGS. Concretely, CorpusWalker takes 21.8 s per query in comparison to 9.2 s for RGS. CorpusWalker takes 20.1 s for the exploration (9.1 sequential LLM calls, about 2 s each) and 1.7 s for the one ranking call. This additional latency overhead buys the pool quality: 54.8 Recall@100 against 50.1 for RGS and 50.0 for a walk guided by perfect relevance labels (Q4(b)). We therefore read latency as quality at a stated time budget and report it to make the trade-off explicit.

CorpusWalker spends 88k tokens per query online (82k input, 6k output, walk and ranking together). From 12 subsets, BRIGHT has 1.15M documents and costs 623M tokens. Dividing that one-off cost by the number of queries the corpora serve gives the per-query total:

queries servedsummarization per querytotal per querysummarization share
1,384 (BRIGHT's query set once)450k539k84%
10,00062k151k41%
100,0006k95k7%
1,000,0000.6k89k1%

Q4 (a) / (c) The paper should compare lexical-only, semantic-only, and dual-graph configurations. Compare adaptive edge selection with fixed or rule-based alternatives.

We perform ablations where the CorpusWalker is provided access to only one graph at a time, everything else unchanged. We also ran when edge types are rule based, precisely, the agent decides which document to be expanded next but the edge type is selected alternatively.

CorpusWalker configurationPool Recall@100nDCG@10R@10
Adaptive, both graphs (paper)54.836.139.3
Fixed: lexical graph only50.933.035.3
Fixed: semantic graph only53.033.836.6
Rule: alternate by turn53.633.936.9

We also report per subset performance on BRIGHT (for single graph )in Table 4 of the revised version of the paper. Both single graph variants degrades on average (−3.9-3.9 and −1.8-1.8 pool Recall@100, −3.1-3.1 and −2.3-2.3 nDCG@10), and neither graph is an optimal choice, the lexical graph is the better single graph on earth-science and pony, the semantic graph on economics and theoremqa-questions, and each has a subset where it degrades (lexical-only −23.8-23.8 Recall@100 on theoremqa-theorems, semantic-only −6.4-6.4 on robotics). Next, in comparison to the rule based (alternate by turn), our agent makes better decision in selecting edge type. It improved Recall@100 by 1.21.2 and nDCG@10 by 2.22.2 points. By comparing different graphs availability and edge selection, we find that dual-graph agent is the optimal and robust choice.

AuthorsOpenReview ↗

Response to Reviewer 9xYW (3/3)

Q4 (b) Evaluate agent-guided exploration against random, breadth-first, and relevance-greedy policies under matched settings. We report the performance of CorpusWalker in comparison with relevance-guided graph exploration methods when both use the same resources (candidate pool, graphs, document summaries and reranker). We consider random selection, Breadth-first, Relevance-greedy with perfect relevance labels and RGS’s ranker’s relevance as baselines.

Expansion strategy (same seeds, budget, summaries, both graphs)Pool Recall@100 (avg. 12 subsets)
CorpusWalker agent (ours)54.8
BM25 top-100, no expansion38.2
Random document and edge (mean of 5 seeds)33.3
Breadth-first (lexical / semantic / alternating / both graphs per turn)40.7 / 38.3 / 39.4 / 40.3
Relevance-greedy with perfect relevance labels (oracle; lexical / semantic / alternating edges)49.6 / 49.4 / 50.0
RGS's search, doc summaries and both graphs (union)50.0
RGS's search, doc summaries and both graphs (alternating edges)50.5

The breadth-first expansion gains at most 2.5 Recall@100 over the BM25 top-100 baseline, and random expansion degrades by 4.9 points. The relevance-guided strategy uses the true relevance of every document in the pool, reaches 50.0% against the CorpusWalker's 54.8%. Finally, RGS, the strongest graph-retrieval baseline, given same document summaries and both graphs, the performance stays within the range of raw text and single graph setup (50.0% vs 50.1%), and nDCG@10 drops from 33.0 to 30.1 because its listwise reranker handles summaries worse than raw text. Letting RGS use one graph per expansion, alternating between the two so that each expansion adds as many candidates as one of the agent’s, does not help either (50.5%). We also report the per subset performance in the paper (see Table 5 in Appendix). The resources do not move a relevance-guided strategy; the decisions are where the gain comes from. We will also state the contribution in these terms in the introduction.

Q4 (d) Baseline reranking and Meta Reranking should also be evaluated on identical candidate pools, with and without exploration traces. The existing trace ablation addresses final ranking but does not establish the superiority of the agent’s exploration decisions.

We would like to point to Table 3 in our paper where we already compare the one-shot ranker with and without the exploration trace on identical pools. In addition, we now add the RankGPT baseline sliding-window listwise reranker on CorpusWalker's exact pools. We found that the CorpusWalker's (ours) pool helps in improving the nDCG@10 by 1.4 points and Recall@10 by 2.1 points over the RGS baseline. We report per-subset performance in the updated version on Table 3 in the revised pdf.

Next, we use the one-shot MetaReranker over a fixed pool and we compare the impact of availability of traces (similar to Table 3 in paper). The traces add 1.7 points gain in nDCG@10 and 2.1 in Recall@10. Hence these gains in the pool and ranking are separable and the Corpuswalker agent provides the gains as observed from our experiments.

PoolRankerdoc representationtraces (yes/no)nDCG@10R@10
CorpusWalkerRankGPTraw textno34.437.2
RGS as publishedRankGPTraw textno33.035.1
CorpusWalkerMetaRerankersummariesno32.836.1
CorpusWalkerMetaRerankersummariesyes36.139.3
Reviewer_18vYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes CorpusWalker, an LLM-based graph exploration framework for reasoning-intensive information retrieval. The central motivation is that conventional retrieve-then-rerank pipelines are constrained by the recall of their first-stage retrievers, while existing graph-based adaptive reranking methods primarily rely on document relevance scores to guide exploration, which could be ineffective for reasoning-intensive retrieval. The paper addresses this limitation by treating graph exploration itself as a reasoning task. Experiments demonstrate improvements over conventional retrieve-then-rerank pipelines and graph-based adaptive reranking methods.

Critical strengths
  1. The research problem is interesting and well-motivated.

  2. The technical framework looks reasonable, with a clear division of responsibilities.

  3. The combination of offline document compression and single-pass reranking is practically appealing.

Critical weaknesses
  1. Although the paper presents graph exploration as a reasoning task, its implementation primarily consists of prompting a general-purpose LLM to select a document and a graph relationship at each iteration. The main components (LLM agents, graph-based retrieval, lexical and semantic graphs, document summarization, LLM-based reranking, etc.) are established techniques. The contribution lies primarily in their integration and in assigning the LLM a different role during graph traversal.

  2. The proposed approach does not introduce a principled model of exploration utility. The traversal agent is instructed to identify promising documents based on their summaries, but there is no explicit formulation of what makes a document valuable for exploration. Without such a formulation, it is difficult to determine whether CorpusWalker constitutes a new reasoning-guided search methodology or primarily an application of LLM-based decision-making to an existing graph exploration framework.

  3. It is unclear how much of the improvement comes from reasoning-guided traversal rather than the availability of multiple graph relationships.

Questions for authors

How does CorpusWalker compare with relevance-guided graph exploration when both methods use the same candidate pool construction, graph infrastructure, and final reranker?

6 comments
AuthorsOpenReview ↗

Response to Reviewer 18vY (1/2)

Thank you for your comments. In the following we provide a few clarifications and details about changes made in the paper. We are enthusiastically looking forward to any further discussion.

Q1. Although the paper presents graph exploration as a reasoning task, its implementation primarily consists of prompting a general-purpose LLM to select a document and a graph relationship at each iteration. The main components (LLM agents, graph-based retrieval, lexical and semantic graphs, document summarization, LLM-based reranking, etc.) are established techniques. The contribution lies primarily in their integration and in assigning the LLM a different role during graph traversal.

Response: We would like to clarify that our approach is not merely focused on integration. One of our core contributions is decoupling graph exploration from relying solely on re-ranker feedback. We point out the limitation of re-ranker feedback-based graph expansion adopted in prior graph-retrieval works in Lines 66-69 and also Figure 1. Prior works iteratively sample the re-ranker feedback over a static graph and select the document to expand, and neighbors to explore from the static graph based on these scores. However, we argue that reasoning-based graph exploration, which entails agent-driven document selection for expansion and the edge type relationship (semantic /lexical) is critical for reasoning-intensive retrieval. This ensures that our agentic exploration is not bounded by limitations of a re-ranker or a narrow notion of relevance. The graph exploration is truly adaptive, where the reasoning LLM employed dynamically decides the document to expand and the graph type (semantic / lexical) to explore as shown in Figure 4.

Additionally, our approach only invokes the re-ranker once to rank the compressed snippets of the entire assembled candidate pool of documents after exploration, ensuring efficiency, unlike iterative re-ranker invocations in existing adaptive graph-based ranking methods.

Q2. The proposed approach does not introduce a principled model of exploration utility. The traversal agent is instructed to identify promising documents based on their summaries, but there is no explicit formulation of what makes a document valuable for exploration. Without such a formulation, it is difficult to determine whether CorpusWalker constitutes a new reasoning-guided search methodology or primarily an application of LLM-based decision-making to an existing graph exploration framework.

Response. Thank you for your feedback. We would like to clarify that the utility is determined by the reasoning agent which is seeded with a definition on what makes a document valuable for addition to pool (which is further refined by the agent itself through its reasoning) as explained below.

We will make the following formulation explicit in Section 3. At turn tt the agent holds a pool PP (the initial seeds and the documents explored so far, each with a summary and a provenance label) and a remaining budget c−∣P∣c-|P|. Each action outputs (d,e,r)(d,e,r) with d∈Pd\in P not yet expanded, e∈{lex,sem}e\in\{\mathrm{lex},\mathrm{sem}\}, and rr the reasoning trace explaining why that document and edge type were selected. The quantity the agent is asked to maximise is the marginal utility of the expansion, u(d,e)=E ∣(Ne(d)∖P)∩Rq∣u(d,e)=\mathbb{E}\,\bigl|(\mathcal{N}_e(d)\setminus P)\cap R_q\bigr|, the expected number of new relevant documents the expansion adds to the pool, where Ne(d)\mathcal{N}_e(d) is the neighbourhood of dd in graph type ee and RqR_q is the set of relevant documents and bridge documents that could lead to more documents relevant to qq. The prompt states this objective (it asks for the document whose neighbourhood is most likely to contain what is still missing, given what the pool already covers and how much budget remains), and the agent's trace records its estimate of it in words at every turn. Relevance of dd enters only as one input to that estimate. Moreover, the agent can change the action in the next iteration after knowing the results from previous expansion. However, both baselines SlideGAR and RGS simply consider the ranker’s relevance as the signal for graph neighbors lookup. As we reported the results in response of Q4, with perfect relevance labels RGS reaches 50.0% Recall@100 against 54.8%. Relevance of a node is a poor proxy for the relevance of its unseen neighbourhood, and the agent's reasoning over summaries is a better estimator.

AuthorsOpenReview ↗

Response to Reviewer 18vY (2/2)

Q3. It is unclear how much of the improvement comes from reasoning-guided traversal rather than the availability of multiple graph relationships.

Response: Thank you for raising this feedback. We perform ablations where the CorpusWalker is provided access to only one graph at a time, everything else unchanged.

CorpusWalker configurationPool Recall@100nDCG@10
Both graphs (paper)54.836.1
Lexical graph only50.933.0
Semantic graph only53.033.8

We also report per subset performance on BRIGHT in Table 4 of revised version of the paper. Both single graph variants degrades on average (−3.9-3.9 and −1.8-1.8 pool Recall@100, −3.1-3.1 and −2.3-2.3 nDCG@10), and neither graph is an optimal choice, the lexical graph is the better single graph on earth-science and pony, the semantic graph on economics and theoremqa-questions, and each has a subset where it degrades (lexical-only −23.8-23.8 Recall@100 on theoremqa-theorems, semantic-only −6.4-6.4 on robotics). The dual-graph agent is the optimal and robust choice, or within noise of the best, on every subset.

Two further results separate the reasoning from the availability of different graphs, as observed on Table 5. First, giving an expansion strategy both graphs without any reasoning does not help: breadth-first expansion over both graphs reaches 40.3 Recall@100 against 38.2 for the BM25 baseline, and the relevance-greedy oracle, which also has both graphs, still falls 4.8 points short of the CorpusWalker. The gain tracks the quality of the decision, not the number of graphs: random 33.3, breadth-first 40.3, perfect-relevance greedy 50.0, CorpusWalker 54.8. Second, holding the graphs fixed and shrinking the agent (Section 5, Figure 3: Qwen3.5-9B and 4B in place of the 35B-A3B agent) lowers pool Recall@100 by about 3.5 points and nDCG@10 by about 4 on StackExchange. Removing a graph costs recall on some subsets; removing the agent's reasoning costs recall on all of them.

Q4. How does CorpusWalker compare with relevance-guided graph exploration when both methods use the same candidate pool construction, graph infrastructure, and final reranker?

Response: Thanks for the questions. We report the performance of CorpusWalker in comparison with relevance-guided graph exploration methods when both use the same resources (candidate pool, graphs, document summaries and reranker). We consider random selection, Breadth-first, Relevance-greedy with perfect relevance labels and RGS’s ranker’s relevance as baselines.

Expansion strategy (same seeds, budget, summaries, both graphs)Pool Recall@100 (avg. 12 subsets)
CorpusWalker agent (ours)54.8
BM25 top-100, no expansion38.2
Random document and edge (mean of 5 seeds)33.3
Breadth-first (lexical / semantic / alternating / both graphs per turn)40.7 / 38.3 / 39.4 / 40.3
Relevance-greedy with perfect relevance labels (oracle; lexical / semantic / alternating edges)49.6 / 49.4 / 50.0
RGS's search procedure given doc summaries and both graphs (union)50.0
RGS's search procedure given doc summaries and both graphs (alternating edges)50.5

The breadth-first expansion gains at most 2.5 Recall@100 over the BM25 top-100 baseline, and random expansion degrades by 4.9 points. The relevance-guided strategy uses the true relevance of every document in the pool, reaches 50.0% against the CorpusWalker's 54.8%. Finally, RGS, the strongest graph-retrieval baseline, given same document summaries and both graphs, the performance stays within the range of raw text and single graph setup (50.0% vs 50.1%), and nDCG@10 drops from 33.0 to 30.1 because its listwise reranker handles summaries worse than raw text. Letting RGS use one graph per expansion, alternating between the two so that each expansion adds as many candidates as one of the agent’s, does not help either (50.5%). We also report the per subset performance in the paper (see Table 5 in Appendix). The resources do not move a relevance-guided strategy; the decisions are where the gain comes from. We will also state the contribution in these terms in the introduction.

We also add the table in our paper (Table 6) when RGS is given CorpusWalker’s resources. We report nDCG@10, Recall@10 and Recall@100 to judge the pool and ranking quality. We conclude that the relevance guidance is a poor proxy for graph exploration.

Thanks again for the feedback. We have tried to address all the concerns. We have also uploaded the revised pdf. We keep all changes in blue fonts. We look forward to answer any further queries.

AuthorsOpenReview ↗

A gentle reminder

Greetings Reviewer 18vY, Thank you for your time and valuable feedback. We have tried to address your queries regarding the novelty, principle of exploration. We have also added ablations to demonstrate the contribution of our exploration / reaosning strategy for traversal vs availability of multiple graphs. We have also uploaded the updated version of the paper. We would like to request if we have addressed your concerns. We are happy to answer any further queries. If we have addressed your concerns, we politely and respectfully request reassessment of rating in light of our response. Thank you for your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of authors responses

Dear ACs/SACs and PCs,

We have answered all concerns raised by all three reviewers to the best of our abilities, through additional experiments, clarification in the manuscript and detailed responses in the rebuttal. We present a brief summary of key concerns and how we had addressed them below:

For all reviewers: We performed additional experiments ablating different graph configurations of our proposed method CorpusWalker. We performed further experiments varying the setup in the comparison of CorpusWalker with the baselines such RSG when provided the same candidate pool, graphs and rerankers.

  1. For Reviewer 18vY:
  • We clarified the core novelty of our approach and that it is not a simple integration of parts. Our work builds upon well-established literature on re-ranker feedback-driven exploration of corpus graphs (like GAR, SlideGAR, GAREN etc. ) at inference time to scale and improve retrieval & ranking performance. We also highlighted that our literature review and introduction already point to limitations of re-ranker feedback-based graph expansion adopted in prior graph-retrieval works. One of our core contributions is decoupling graph exploration from relying solely on re-ranker feedback. We argue that reasoning-based graph exploration, which entails agent-driven document selection for expansion and the edge-type relationship (semantic /lexical) is critical for reasoning-intensive retrieval. Hence, our approach proposes a new training-free test-time approach to enable reasoning-driven exploration of graph exploration to improve retrieval and ranking performance.
  1. For Reviewer 9xYW:
  • We compare our method with RGS (strongest baseline) and others when provided with the same compressed representations.
  • We reported preprocessing costs, amortized costs across query volumes, and end-to-end latency.
  • We reported the baseline reranking and Meta Reranking under the identical candidate pools, with and without exploration traces, in order to differentiate the gains in the final ranking by CorpusWalker. During the discussion, the reviewer further asked for the main difference between our method and RGS (strong baseline). We provided the concrete differences in the response as well as we pointed out the reviewer to the corresponding part in the submitted manuscript.
  1. For Reviewer 1sNG,
  • The reviewer had only one major concern on separating the expansion strategy from document summaries and graphs access. We provided the detailed response along with experimental results and analysis. The reviewer also acknowledged that the main concern has been addressed.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.