Technical Summary: SpIDER - Spatially Informed Dense Embedding Retrieval for Software Issue Localization

Problem Definition

The paper addresses the critical challenge of software issue localization for Large Language Model (LLM)-based coding agents. The specific task is to retrieve the top-$K$ relevant code functions, classes, or files from a large codebase given a user query, bug report, or feature request.

Current approaches face three primary limitations:

1. Neglect of Structural Context: Existing dense retrieval methods (based on contrastive learning) rely solely on semantic similarity between issue descriptions and code embeddings. They overlook the graph-structured nature of codebases, where buggy modules are often spatially proximate (e.g., within the same file or neighboring functions) to highly ranked candidates, even if their semantic similarity scores are slightly lower.
2. Language Bias: Most evaluations are confined to Python (specifically SWEBench-Lite/Verified), leaving the performance of these methods on other languages (Java, JavaScript, TypeScript) underexplored.
3. Granularity Gap: Function-level retrieval, which is the most granular and challenging level compared to class or file retrieval, remains understudied.

Methodology: SpIDER

The authors propose SpIDER (Spatially Informed Dense Embedding Retrieval), a neurosymbolic framework that augments standard dense retrieval with graph-aware spatial exploration and LLM-based reasoning. The method operates under a fixed retrieval budget $K$.

1. Code Graph Construction

The codebase is represented as a graph $G = (V, E)$ where nodes are code entities (functions, classes, files, directories) and edges represent structural relationships (contains, invokes, imports, inherits).

• Parsing: Python files are parsed using the built-in ast module; Java, JavaScript, and TypeScript files use Tree-sitter.
• Focus: The system focuses on retrieving functions, as they constitute the majority of ground-truth edits in datasets like SWE-PolyBench.

2. The SpIDER Workflow

The retrieval process involves four stages:

1. Semantic Retrieval: A bi-modal encoder computes relevance scores $s_Q(v)$ for all nodes. The top-$N$ nodes ($N > K$) are selected to form a candidate pool $S_N(Q)$, and the top-$K$ nodes form the baseline set $S_K(Q)$.
2. Seed Selection: The top-$C$ nodes from $S_K(Q)$ are selected as "seed centers" ($C_Q$) for graph exploration.
3. Neighborhood Exploration: For each seed, a Breadth-First Search (BFS) is performed up to a depth $d$ along contains edges to identify structurally proximate functions.
4. Two-Stage Filtering:
   • Semantic Filtering: Neighbors are restricted to those also present in the top-$N$ semantic pool ($\hat{C}_Q = \Gamma_d(C_Q) \cap S_N(Q)$).
   • LLM Selection: An LLM evaluates the remaining candidates (source code + issue description) to determine relevance, filtering out false positives and identifying "near-miss" candidates that semantic similarity alone missed.
5. Output Construction: The final set $S^{LLM}_K(Q)$ is constructed by inserting the LLM-selected neighbors into the top-$K$ list, displacing the lowest-ranked non-center nodes to maintain the fixed budget $K$.

3. Theoretical Justification

The paper provides a proposition (Proposition 4.2) stating that if relevant functions form a localized region in the code graph, dense retrieval places at least one seed in that region, and the LLM selector has a higher true-positive rate than false-positive rate, then SpIDER strictly improves expected recall at a fixed budget $K$.

Key Contributions

1. SpIDER Framework: A novel, simple graph-aware dense retrieval strategy that jointly exploits semantic content and code structure to determine relevant functions under a fixed budget.
2. SpIDER-Bench: A heterogeneous, graph-structured evaluation benchmark for multi-language code localization. It aggregates data from SWEBench-Verified, SWE-PolyBench, and Multi-SWEBench, covering Python, Java, JavaScript, and TypeScript. It includes code graphs with source code as node features.
3. Empirical Validation: Comprehensive evaluation showing SpIDER's superiority over existing dense and sparse (BM25) baselines across all four languages.

Experimental Results

The authors evaluated SpIDER against baselines including SweRankEmbed-Small, CodeSAGE-Small (zero-shot and PEFT), and BM25.

• Performance Gains: SpIDER consistently improves dense retrieval performance by at least 13% in Recall@20 and 14% in Accuracy@20 across programming languages and benchmarks.
• Cross-Language Robustness: The zero-shot SweRankEmbed-Small model (trained only on Python) remains competitive on non-Python codebases when augmented with SpIDER, outperforming BM25 and other baselines. This suggests that structural signals help mitigate domain shifts caused by language differences.
• Downstream Impact: Improved retrieval directly translates to better code generation. On the SWE-Bench-Verified benchmark, using SpIDER with a retrieval budget of $K=10$ resulted in a +2.74 percentage point increase in pass rate (12 additional resolved instances) compared to standard dense retrieval.
• Ablation Studies:
  • Increasing the number of seed centers ($C$) improves performance up to saturation (around $C=5$).
  • Increasing exploration depth ($d$) improves recall but increases LLM token consumption significantly.
  • The method is robust across different retrieval budgets ($K$) and is compatible with downstream LLM rerankers.

Significance and Claims

The paper claims that SpIDER effectively bridges the gap between semantic retrieval and structural reasoning. By incorporating spatial locality as a complementary signal, the method recovers relevant functions that are structurally close to high-ranked candidates but semantically distinct, a scenario where pure embedding-based methods fail.

The authors emphasize that their approach is agnostic to downstream rerankers and generalizes across programming languages, addressing a critical gap in the current literature which is heavily Python-centric. They position SpIDER not as a replacement for LLMs, but as an efficient augmentation that leverages the "commonsense reasoning" of LLMs combined with structural graph signals to create more invariant representations for code retrieval. The work establishes a new standard for evaluating code localization in multi-language, function-level settings.