SpIDER: Spatially Informed Dense Embedding Retrieval for Software Issue Localization

Retrieving code functions, classes or files that are relevant in order to solve a given user query, bug report or feature request from large codebases is a fundamental challenge for Large Language Model (LLM)-based coding agents. Agentic approaches typically employ sparse retrieval methods like BM25 or dense embedding strategies to identify semantically relevant units. While embedding-based approaches can outperform BM25 by large margins, they often don’t take into consideration the underlying graph-structured characteristics of the codebase. To address this, we propose SpIDER (Spatially Informed Dense Embedding Retrieval), an enhanced dense retrieval approach that integrates LLM-based reasoning along with auxiliary information obtained from graph-based exploration of the codebase. We further introduce SpIDER-Bench, a graph-structured evaluation benchmark curated from SWE-PolyBench, SWEBench-Verified and Multi-SWEBench, spanning codebases from Python, Java, JavaScript and TypeScript programming languages. SpIDER’s graph-based candidate expansion gives each surfaced function a structural reason for inclusion (the seed it neighbors and the edge type linking them), making the candidate set auditable by a developer reviewing the agent’s actions while keeping the retrieval budget fixed. The code graph is built from per-repository syntax trees, so it can be constructed on-demand at the start of an interactive developer session rather than precomputed offline across an entire codebase corpus. Empirical results show that SpIDER consistently improves dense retrieval performance by at least 13% across programming languages and benchmarks in SpIDER-Bench.