SpIDER: Spatially Informed Dense Embedding Retrieval for Software Issue Localization

Retrieving code functions, classes or files relevant to a 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 methods like BM25 or dense embedding strategies to identify semantically relevant units. While dense embedding approaches can outperform BM25 by large margins, both ignore the graph-structured characteristics of the codebase. To address this, we propose SpIDER (Spatially Informed Dense Embedding Retrieval), a dense retrieval approach that integrates LLM-based reasoning with graph-based exploration of the codebase. We further introduce SpIDER-Bench, a graph-structured benchmark curated from SWEPolyBench, SWEBench-Verified and Multi-SWE-bench, spanning Python, Java, JavaScript and TypeScript repositories. SpIDER's graph-based candidate expansion attaches a structural reason for inclusion to each surfaced function (its seed and the edge type linking them), making the candidate set auditable while keeping the retrieval budget fixed. The graph is built from per-repository syntax trees, so it can be constructed on-demand at the start of a developer session rather than precomputed offline. Empirical results show that SpIDER consistently improves dense retrieval Recall@20 across every language and benchmark in SpIDER-Bench: by at least 13% relative (+0.05 to +0.12 absolute) along containment edges, rising to at least 27% relative (+0.11 to +0.19 absolute) once call edges are explored.