CorpusWalker: Reasoning-Guided Graph Exploration for Search

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 $3.1$ points and Recall@100 by $4.7$ points over the strongest of them, with up to $2.8$ points gain in nugget coverage on FreshStack.