💻 computer science

SkeletonGraph: A Zero-LLM Structural Retrieval Engine for Coding Agents, and Why Its Gains Land in the Cost Tail, Not the Median

This paper introduces SkeletonGraph, a structural retrieval engine that significantly improves function-level code localization and reduces costs for coding agents in the expensive tail of task distributions, yet fails to lower median costs or boost solve rates because its effectiveness is constrained by repository familiarity and cannot replace the agent's own learning from reading code.

Original authors: Yash Doke

Published 2026-08-20

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Yash Doke

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a team of highly skilled digital assistants, each equipped with a vast library of code and a powerful brain capable of understanding complex instructions. These assistants are tasked with fixing bugs in massive software projects, a job that requires them to find the exact piece of code that is broken, understand how it fits into the whole system, and then rewrite it correctly. For a long time, the industry believed that the biggest bottleneck for these assistants was simply finding the right file. The prevailing theory was that if we could build a better map or a smarter search engine to hand the correct file to the assistant immediately, we would save a tremendous amount of time and money. It seemed logical: if the assistant doesn't have to wander through thousands of files to find the one it needs, it should finish the job faster and cheaper.

This belief drove a wave of new tools designed to act as structural retrieval engines. Instead of letting the assistant read through text line by line, these tools analyze the code's architecture, understanding how functions call one another, and serve up the exact function the assistant needs to edit. The promise was dramatic: some developers claimed these systems could cut costs by ninety-nine percent. But a new study challenges this optimistic view, suggesting that while these tools do find the code better, they do not necessarily make the job cheaper for the average task. The researchers found that the savings are not spread evenly across all jobs; instead, they appear only in the most difficult, expensive cases, leaving the typical task just as costly as before.

The study, conducted by independent researcher Yash Doke, set out to test these claims in a real-world setting. The team built a system called SkeletonGraph, which acts as a specialized librarian for coding agents. Unlike standard search tools that look for keywords in text, SkeletonGraph understands the structure of the code. It knows that a function is a specific unit of work and can trace how different parts of a program connect. To test its effectiveness, the researchers pitted this new system against a standard, built-in text search tool used by a leading coding agent, Claude Code. They ran both systems through one hundred real-world coding tasks, ensuring that every proposed fix was actually tested by running the project's own software tests to see if it worked. This was crucial, as it meant they were measuring the actual cost and success of the entire process, not just how well a search engine performed in isolation.

The results were striking in their precision but surprising in their financial impact. When it came to finding the right file to edit, the new structural system was significantly better. On its very first try, it located the correct file for eighty-six percent of the tasks, whereas the standard text search only found the right file sixty-six percent of the time. The difference was even more dramatic when it came to identifying the specific function within a file that needed changing. The new system identified the correct function about eighty percent of the time, while the standard text search, which is designed to match lines of text rather than logical blocks of code, could not name a single correct function. In this sense, the structural tool was undeniably superior at its primary job: it found the right neighborhood and pointed directly to the right house.

However, when the researchers looked at the cost, the story changed. They expected that because the new system found the code so much faster, the total bill for each task would drop significantly. Instead, they found that for the typical, medium-difficulty task, the cost actually went up slightly, by about two percent. The massive savings did not appear in the middle of the pack; they were hidden entirely in the tail end of the most expensive, difficult tasks. For the hardest twenty-five percent of tasks, the new system reduced costs by roughly sixteen percent, and for the most difficult five percent of tasks, it slashed costs by forty-two percent. The average saving across all tasks was about fifteen percent, but this number was misleading because it was driven almost entirely by a few runaway cases where the standard system had gotten lost and spent a fortune. For the vast majority of tasks, the new system did not make the job cheaper; in fact, for the easiest tasks, it made them slightly more expensive.

The researchers discovered the reason for this disconnect by looking at how the coding agents actually worked. They found that the total amount of information the agent had to hold in its memory at any one time remained almost exactly the same, whether it used the new structural tool or the old text search. The agent still needed to understand the same amount of context to write the fix. The new system simply delivered that context earlier in the process. Because the agent had to re-send all the information it had gathered so far with every new step it took, delivering the right file early did not reduce the total volume of data processed; it only reduced the number of steps the agent took to get there. The agent still had to spend time writing the code and running tests, which made up the bulk of the work. The new system saved the time spent wandering, but it could not save the time spent building the solution.

This led to a counterintuitive finding about how these agents learn. When the standard text search system was allowed to search and read files on its own, it often ended up reading more files than the structural system, but in doing so, it learned the specific vocabulary and patterns of that particular codebase. This "learning by doing" allowed it to search more effectively as the task progressed. The structural system, by handing over a ranked list of files immediately, sometimes prevented the agent from exploring and learning the code's unique language. In three out of four conditions tested, the standard system eventually found the correct files just as often as the structural system by the end of the task, simply because it had explored more. The structural system was faster to the starting line, but the finish line was the same.

The study also tested whether the quality of the problem description mattered. They stripped away technical details like error logs and code snippets from the task descriptions, leaving only plain English explanations. They expected this would make the structural system struggle, but it did not. The system's ability to find the right code remained stable, suggesting it relies on the structure of the code itself rather than the specific clues in the problem description. However, they found that the system performed significantly worse when the codebase was completely new and unfamiliar to the model, dropping its success rate from nearly eighty-eight percent to about fifty-nine percent. This showed that the system's success depends heavily on the model's prior knowledge of the repository, not just the quality of the search tool.

Ultimately, the paper concludes that structural retrieval is a tool for preventing disasters rather than optimizing the average. It acts as a safety net that stops the most expensive, difficult tasks from spiraling out of control, but it does not make the routine tasks cheaper. The researchers argue that the industry has been measuring the wrong thing. By focusing on how many tokens are saved in a single search, developers have been ignoring the fact that the total cost is determined by how many steps the agent takes and how much context it must carry. The new system shortens the path to the answer, but it does not shrink the size of the answer itself. For the typical user, the bill will not go down; for the user facing a complex, broken system, the bill will be significantly lower. The value of this technology is not in making the easy jobs cheaper, but in ensuring that the hard jobs do not become impossible.

Technical Summary: SkeletonGraph: A Zero-LLM Structural Retrieval Engine for Coding Agents

Problem Statement

The paper addresses the efficacy of structural code retrieval in reducing the operational costs of AI coding agents. While the prevailing industry hypothesis suggests that providing agents with precise code context (functions, files) via retrieval significantly reduces token consumption and cost, existing evaluations often rely on flawed metrics. Common claims of "order-of-magnitude" savings are typically derived by comparing the token count of a structured query against the token count of reading entire files end-to-end. The author argues this calculation ignores the agent's actual workflow: agents do not read whole files by default, they do not stop after finding code, and they are billed for the entire conversation history (which re-sends all accumulated context on every turn). Consequently, the paper seeks to measure the actual economic value of improved retrieval within a deployed agent loop, specifically examining whether retrieval accuracy gains translate to proportional cost reductions or solve-rate improvements.

Methodology

System Architecture: SkeletonGraph

The author developed SkeletonGraph, a zero-LLM structural retrieval engine that operates in three stages:

Index Build (Offline): Uses tree-sitter parsers (supporting 10 languages) to generate symbol tables, call graphs, and PageRank centrality metrics. It builds a BM25 lexical index and optional dense semantic embeddings (using jina-code). Crucially, this process invokes no language models, making the index rebuildable from source without LLM costs.
Retrieval (Per-Query): Executes three parallel retrieval legs:
- Lexical: BM25 matching.
- Semantic: Dense vector search.
- Structural: A reranker that reorders the lexical recall pool using entity anchoring, PageRank, and call-graph proximity.
- Fusion: Results are combined using Reciprocal Rank Fusion (RRF) to produce a ranked list of functions.
Serving: Exposes the retrieval results to agents via the Model Context Protocol (MCP).

Experimental Setup

The study employs two distinct evaluation harnesses to ensure robustness:

Frontier-Agent Deployment: SkeletonGraph is deployed against Claude Code (headless mode) on 100 SWE-bench Verified tasks. The baseline is the agent's native built-in tools (text search, file glob, file read). Every candidate fix is adjudicated by executing the project's real test suite in a container.
React Loop (Controlled Ablation): A custom loop using an open-weight model (nemotron-3-super-120b-a12b) to compare SkeletonGraph against other retrieval strategies (grep, BM25, graph queries, repository maps) without MCP handshake constraints. This includes a "none" control (closed-book) to measure benchmark contamination.

Cost Model

The author introduces a cost model where the total billed tokens $N$ are the sum of context sizes $c_t$ over $T$ turns. They posit that cost is driven by two factors:

Trajectory Length ( $T$ ): The number of turns required to localize and implement.
Context Size ( $\bar{c}$ ): The amount of material carried in the prompt, which is re-sent on every subsequent turn.
The paper argues that retrieval primarily affects the localization prefix of $T$ , but if the agent still requires the same amount of context to implement the fix, the context term $\bar{c}$ remains unchanged, limiting total cost savings.

Key Contributions

Decoupling of Retrieval Accuracy and Cost: The paper demonstrates that significant improvements in retrieval accuracy (e.g., function-level localization rising from 0% to ~80%) do not yield proportional cost reductions in the median case. Instead, savings are concentrated entirely in the "cost tail" (expensive tasks).
A Cost Model for Agentic Retrieval: The author derives that an agent's context is bounded below by the task requirements ( $c^*$ ). If retrieval provides less than $c^*$ , the agent fetches the rest; if it provides more, the surplus is re-billed on every turn. Thus, payload shaping has bounded leverage, while reducing the turn count ( $T$ ) is the only unbounded lever.
Benchmark Contamination Evidence: A control group receiving no repository code solved 36–44% of tasks on SWE-bench Verified, indicating the benchmark is saturated with memorization. This invalidates solve-rate comparisons as a primary metric for retrieval quality in this context.
Determinants of Retrieval Quality: Through a 2x2 factorial experiment (varying issue text cues and repository familiarity), the author shows that retrieval quality depends primarily on repository familiarity (recall drops from 0.877 to 0.585 on unseen code) rather than the presence of specific location cues (tracebacks/code blocks) in the issue text.
Negative Results and Diagnostic Value: The paper reports five failed attempts to convert retrieval quality into savings (e.g., forcing retrieval-only paths, removing re-reads, routing tasks based on cost), demonstrating that the observed ceiling is structural, not a tuning failure.

Results

Retrieval Accuracy

First-Search File Recall: SkeletonGraph achieves 86.2% recall on the first search, compared to 66.3% for the agent's built-in text search.
Function-Level Localization: SkeletonGraph identifies the correct function in ~80% of tasks. The built-in text search scores 0% because it matches lines/files and cannot return function-level granularity.
Precision: SkeletonGraph has lower precision (34.2% vs 61.8%) because it returns the "neighbourhood" of code. However, this breadth often supplies context the agent would otherwise have to fetch manually.

Cost and Turn Reduction

Median Cost: The median task cost increased slightly (+1.9%) with SkeletonGraph. For easy tasks, the retrieval overhead outweighs the savings.
Tail Cost: The savings are concentrated in the expensive tail. At the 95th percentile, cost was reduced by 42.5%.
Overall Average: The mean cost across 100 tasks decreased by 14.6%, but this is driven entirely by the truncation of long, expensive trajectories.
Turns and Context:
- Turns: Reduced by 21.4% overall.
- Peak Context: Remained effectively identical (44.1k vs 44.9k tokens). Retrieval shortened the path to the answer but did not reduce the total amount of context the agent needed to carry to implement the fix.

Solve Rate

SWE-bench Verified: Solve rates were statistically indistinguishable (75/100 for SkeletonGraph vs. 74/100 for native).
Decontaminated Benchmark: On unseen repositories, SkeletonGraph achieved a genuine 7-point improvement (42.0% vs 35.0% for closed-book), but this was still a modest gain compared to the massive token savings claimed by other systems.

Significance and Claims

The paper claims that structural retrieval is an "anti-catastrophe layer" rather than a general cost optimizer. Its primary value is bounding the worst-case scenario by preventing agents from wandering aimlessly through large codebases on difficult tasks.

The "Tail" Phenomenon: The author argues that the field's focus on mean cost reduction is misleading. Retrieval does not make the "typical" task cheaper; it stops the "disaster" tasks from running away.
The Ceiling: There is a structural ceiling to cost savings. Because agents must acquire sufficient context to write a correct edit ( $c^*$ ), and because this context is re-sent on every turn, simply providing better context upfront does not reduce the total token bill unless it also reduces the number of turns required to reach implementation.
Practical Implication: For builders of code-context systems, the paper suggests optimizing the delivery schedule (when context is provided) is more critical than optimizing the ranking (how cleverly it is selected). A retrieval layer that returns the right function immediately collapses the localization prefix, but it cannot shorten the implementation and validation phases where the bulk of the budget is spent.

The author concludes that while retrieval quality is real and measurable, its translation into economic savings is non-linear and heavily dependent on the difficulty of the task and the agent's existing knowledge of the repository. The paper emphasizes honesty in reporting: retrieval is valuable for preventing catastrophic failures, but it is not a silver bullet for reducing the median cost of coding agents.