SpIDER: Spatially Informed Dense Embedding Retrieval for Software Issue Localization
Shravan Chaudhari, Rahul Thomas Jacob, Jiajun Cao, Shihab Rashid, Mononito Goswami, Christian Bock
EMNLP 2026 camera-ready
cs.SE, cs.LG
2025-12-18
SpIDER fixes the budget at 20 functions, swaps in missed graph neighbors, and lifts Recall@20 at least 13% relative across four languages, 27% with call edges.
A coding agent that edits the wrong function wastes the patch and the tokens spent writing it. BM25 ranks by lexical overlap. Dense retrieval embeds the issue and each function in one space and sorts by cosine similarity, and it usually beats BM25 by a wide margin. Both still ignore the repository graph: which function sits inside which class, and which function calls which.
The missed function is often next to a high-scoring hit. On SWE-PolyBench, dense retrieval places the edited function in the top 100 for 67% of single-function Python instances, 77% of Java, and 75% of JavaScript. On multi-function instances those rates fall to 18%, 15%, and 41%. Even when every edited pair is at most two containment hops apart, the top 100 contains all of them in only 34%, 30%, and 53% of cases. The embedder finds a seed. It does not rank the structural neighbors into the top K.
Function-level localization is harder than file or class localization, and most published numbers stop at Python. SpIDER holds the retrieval budget K fixed and spends that budget on graph neighbors the embedding ranked too low.
The graph is built at the start of a session from that repository's syntax trees. Python uses the standard ast module. Java, JavaScript, and TypeScript use Tree-sitter. Nodes are directories, files, classes, and functions. Edges are contains, invokes, imports, and inherits. Only the primary language is parsed. The schema matches LocAgent. SpIDER does not walk the graph across many LLM rounds. It makes one exchange inside a fixed list.
Recall@K rises only when the precision of admitted functions, η, exceeds the hit rate of the frontier they evict, τ. The comparison is the rank-K dense hit, not a random function in the repo. A neighbor can clear the repository base rate and still lose to τ. The selector exists to push η over that line.
C, d, and N were grid-searched on the Python split of SWE-PolyBench and then frozen: C=5, d=4, N=500, K=20. A query makes five LLM calls, about 3K to 6K input tokens each.
The main table expands along contains edges only. The encoder is zero-shot SweRankEmbed-Small, trained on about 3,300 Python repositories. At K=20, Recall@20 rises on every language and every benchmark in SpIDER-Bench, by at least 13% relative and by 0.05 to 0.12 absolute.
| Setting | Metric | Dense | +SpIDER |
| Verified, Python | Recall@20 | 0.54 | 0.61 |
| PolyBench, Python | Recall@20 / Acc@20 | 0.42 / 0.35 | 0.49 / 0.40 |
| PolyBench, Java | Recall@20 / Acc@20 | 0.31 / 0.24 | 0.36 / 0.27 |
| PolyBench, JavaScript | Recall@20 / Acc@20 | 0.52 / 0.45 | 0.60 / 0.52 |
| PolyBench, TypeScript | Recall@20 / Acc@20 | 0.29 / 0.21 | 0.35 / 0.28 |
| Multi-SWE, Java / JS / TS | Recall@20 | 0.32 / 0.31 / 0.40 | 0.37 / 0.39 / 0.52 |
Acc@20 is 1 only when every edited function is inside the top K. The paper puts the relative Acc@20 floor at 14%. The same exchange improves CodeSAGE and BM25 from a lower base. Zero-shot SweRank still leads both on non-Python repositories.
An LLM reranker that keeps 3 of the 20 candidates preserves the gap. On Python SWE-PolyBench, SweRank Recall@3 moves from 0.38 to 0.44 and Acc@3 from 0.31 to 0.36.
Call edges, tested only on SWE-PolyBench, beat containment in every language. Using both raises the worst-language relative Recall@20 gain from 13% to 27%: Python 0.42 to 0.60, Java 0.31 to 0.42, JavaScript 0.52 to 0.66, TypeScript 0.29 to 0.48. Absolute gains are 0.11 to 0.19. A paired bootstrap with 10,000 draws gives p < 0.01 on Recall@20 in all four languages. Java Acc@20 under contains alone is the one non-significant cell. Import and inherits edges add nothing. No inherits edge touches a function node.
Tokens jump by about an order of magnitude. Containment costs 7.8K to 14.9K tokens per issue. Call edges cost 55.5K to 109.9K. The main table therefore reports containment.
The gain reaches patch generation when the agent cannot search on its own. mini-swe-agent may read only the retrieved functions. On a SWE-bench Verified subset, the better SpIDER variant resolves more instances at every K. The widest gap is at K=10: containment resolves 0.681 versus 0.611 for dense retrieval, 7.0 points and 18 instances. That run spends 81.5K tokens and beats dense retrieval at K=20 (0.650, 185.3K tokens) at 44% of the cost.
The encoder stays frozen. The graph is parsed from the repository in front of the developer, with no offline corpus index. Inserted functions carry a seed and an edge type, so a reviewer can see why they were added.
Five extra LLM calls put SpIDER about two orders of magnitude below iterative graph-search agents, and one round trip above plain embedding retrieval. Containment at K=10 already resolves more issues than dense retrieval at K=20, with fewer tokens. Call edges are more accurate and about an order of magnitude more expensive. They are the wrong default.
Headroom depends on the language. JavaScript leaves less on the table because dense retrieval already covers many instances. Java is the opposite: invoke connectivity is 0.63, the highest of the four, and dense top-100 coverage is 29%, the lowest. Containment cannot reach those cross-file functions. Multi-function, cross-file bugs are where the exchange pays.
The dense ranker sets a hard ceiling. Exploration never leaves the top 500. The share of instances with at least one edited function ranked worse than 500 is 38% on SWE-bench Verified and 51%, 62%, and 22% on SWE-PolyBench Python, Java, and JavaScript. No graph walk recovers them.
The selector drops another slice. If every structural neighbor were kept, SpIDER would still hold only 79% to 89% of that recall inside budget K. The appendix shows both failure modes: a tangential seed whose true neighbor is rejected, and a loose filter whose neighbors evict a correct function that was already on the list.
The 27% figure does not apply to the main table. The call-edge ablation ran on SWE-PolyBench only. SWE-bench Verified and Multi-SWE-bench stay on containment. Graphs ignore every non-primary language, so cross-language edits are invisible. Inheritance is empty at function granularity. Raising depth from 4 to 8 multiplies Python input tokens by 8.2, from 3.6K to 29.7K. Depth 4 is a budget choice. Neighboring depths differ by about 0.01, inside the noise of the selector.
Table 4 disables free grep, so the resolve-rate gap belongs to retrieval. How much of the 7 points survives once the agent can search again is not answered by that table. MRR@20 falls in a few cells because a promoted neighbor is inserted under its seed. Coverage can rise while the first correct function ranks worse.