Chapter 9 — Graph Engineering

"Code localization — identifying precisely where in a codebase changes need to be made — is a fundamental yet challenging task in software maintenance." — Chen et al., LocAgent [B]

"GraphRAG frequently underperforms vanilla RAG on many real-world tasks despite its conceptual promise." — When to use Graphs in RAG [B]

Both are true, and the space between them is this chapter.

9.1 The question grep answers badly

Chapter 4 identified the mechanism driving structural decay, and left this chapter a specific debt.

An agent needs behaviour that already exists somewhere, slightly differently. Two implementations are correct: duplicate and modify, or extract and reuse. Extraction requires knowing every call site. That is a repository-wide question answered from a bounded view, so extraction is expensive and risky while duplication is cheap and safe. The gradient points at duplication, and Chapter 4 argued no instruction reverses a gradient.

Chapter 6 then closed the obvious escape. You cannot fix this by showing the agent more: the whole file scored 12.7% against 18.0% for a hundred-line window, and there is no reason to expect the whole repository to behave better.

So the question is what does answer "where is every call site" well. And the honest answer about grep is more specific than "it is not good enough."

grep gives you recall without a guarantee. It finds lexical matches. Real call sites hide from lexical search in entirely ordinary ways: dynamic dispatch, interface implementations, re-exports through an index module, aliased imports, string-keyed dispatch tables, dependency injection, reflection, code generation, test doubles that shadow the real name.

A graph is not perfect either — static analysis of a dynamic language is undecidable, and every real code graph misses some edges. But the difference is not degree, it is kind:

grep has an unknowable failure mode. A graph has a knowable one.

A graph returns a typed, enumerable answer with documented limits: these are the call edges I can resolve, and here is the class of dispatch I cannot. You can reason about that. You can even test it. With lexical search you receive a list and no information whatsoever about what is missing from it.

This is the answer to Chapter 4's debt, and it is more interesting than "graphs make search better." The cost gradient exists because extraction demands completeness, and lexical search supplies recall. An agent that finds three of six call sites, extracts, and breaks production has learned something true about its own situation: given its instruments, extraction is riskier than duplication.

Which means the gradient is not a fact about agents. It is a fact about the instruments we gave them.

A graph does not merely make extraction cheaper. It makes extraction safe, which is the only thing that flattens the gradient.

And that converts Chapter 4's open question into something testable: repositories with graph-backed reference tooling should show less of the duplication signature than matched repositories without it. Nobody has run that study. It is the cleanest available test of Chapter 4's mechanism.

9.2 What a code graph is

The definition: representing a repository as a typed graph — nodes for the things that exist, edges for the relationships between them — so an agent can navigate rather than guess.

LocAgent's construction is the clearest verified instance. It parses a codebase into directed heterogeneous graphs: nodes for files, classes, and functions; edges capturing imports, invocations, and inheritance. The authors describe it as a lightweight representation enabling hierarchical navigation, and its purpose as bridging natural-language problem descriptions to code elements through multi-hop reasoning "rather than simple keyword matching" [B].

The systems worth knowing, with verification status stated honestly:

RepoGraph deserves particular attention for what kind of claim it makes. It is not a competing agent that scores higher. It is a plug-in added to existing agents that improved all of them. That is the strongest available form of evidence that the graph is supplying something orthogonal to whatever the agent was already doing — and it is exactly the shape of Chapter 2's founding result, where the model was held constant and the environment varied.

A correction for the record, since this book prints only verified figures: the "≈32.8% relative improvement" widely attributed to RepoGraph is not in its abstract, and I have not retrieved it from the paper. The qualitative claim — a plug-in that improved four methods — is verified and is enough.

9.3 A context problem before a search problem

The instinct is to file graphs under retrieval. That undersells them, and LocAgent's most striking number shows why.

Consider how an agent without a graph answers a multi-hop question — find the handler for this route, then the service it calls, then that service's repository, then the tests covering each.

LocAgent reports an ≈86% cost reduction against proprietary baselines. That is not an accuracy result; it is a payload result. The graph reduced what had to be in context to answer the question — which is precisely Chapter 6's dilution problem attacked at the root rather than managed after the fact.

Chapter 6 called progressive disclosure the only lever that addresses both starvation and dilution, and named this chapter as its realisation. Now the identification can be stated exactly:

A code graph is progressive disclosure with a typed index. Carry pointers, not payloads; make the pointers navigable by relationship rather than by string; fetch bodies only when the traversal says they matter.

The second LocAgent figure is worth as much as the first. A fine-tuned 32-billion-parameter open model reached results comparable to state-of-the-art proprietary models on this task. The graph substituted for model scale. That is the SWE-agent result again, in a different key: the environment is a lever with a large coefficient, and here the coefficient was large enough to close a gap between model tiers.

9.4 The one guide that does not depreciate

Now the property that, I think, makes this pillar the most under-valued in the book. It requires refining something Chapter 2 established.

Chapter 2 argued that harness mass measures what the model cannot yet do for itself, so a mature harness shrinks as models improve. Chapter 7 sharpened it: guides age, sensors persist. Both are right, and both are stated at slightly the wrong grain, because they conflate two different things a control can supply.

Some controls compensate for a capability deficit. SWE-agent's edit command existed because 2024 models were poor at multi-line editing through shell primitives. Its linting guardrail existed because they could not recover from self-inflicted syntax errors. Training closed both. The compensation became overhead. This is Chapter 2's arc, and it is correct.

Some controls supply information the model cannot have. No amount of training tells a model your private repository's call graph. A model with flawless reasoning still does not know that validateOrder is reached through a string-keyed dispatch table in your codebase, because that fact is not in any training set and never will be. Information deficits are not closed by better models.

That distinction produces a three-way taxonomy, and the third row is nearly empty in practice:

This refines rather than contradicts Chapter 7. A graph is a guide — feedforward, acting before generation, telling the agent where things are. But its content is observed from the territory rather than written from memory. It therefore has a guide's function and a sensor's durability, and it occupies the cell that Chapter 7's quadrant does not distinguish.

The mechanism is simply that a graph is regenerated. A context file saying "the order pipeline lives in services/orders" is true when written and becomes a lie at some later date that nobody records. A graph does not make claims about the past; it is recomputed from what is there.

Which sets up the observation this chapter exists for.

9.5 The punchline

Recall two verified findings from earlier chapters, and put them next to each other.

From Chapter 7: Context Files are present in 90.6% of repositories using agentic coding tools — 4,768 files across 2,586 repositories — and they are overwhelmingly the mechanism. Hooks, by contrast, appear in 0.9%–3.2% [A].

From the content analysis: in a study of 328 CLAUDE.md files, architectural concerns dominate, followed by development guidelines, project overviews, and testing [B] 🔴 — unverified via secondary citation, and consistent with the related finding that repository-level context files describe project architecture, build commands, and contribution conventions.

So the field's single most-adopted harness mechanism is used primarily to hold hand-written prose describing architecture.

And architecture is a structural property of the code. It is derivable. It is exactly what row 3 of Figure 9.3 supplies durably and row 2 supplies with drift.

The dominant content of context files is a hand-maintained, silently ageing description of a structure that could be derived, kept fresh, and queried by relationship. Graph engineering is how you move that content from row 2 to row 3.

I want to be careful about the scope of this claim, because the strong version is wrong.

What a graph can take over from a context file: where things are, what calls what, what depends on what, what tests cover what, what the module boundaries are, what the type contracts are. All of it structural, all of it derivable, all of it currently prose.

What a graph cannot take over: why. Which technical debt is deliberately tolerated and why. Which convention is load-bearing and which is habit. What the team is trying to achieve. Chapter 5 established that this content cannot be recovered by interrogating an author any more, and Chapter 0 established it as the last human monopoly. A graph derives what is; it cannot derive what was intended.

So the correct conclusion is not "graphs replace context files." It is a division of labour that almost nobody currently draws:

A context file that describes structure is doing work a machine could do better, while occupying the scarce budget Chapter 6 measured. A context file that records why is doing work nothing else can do. Most context files today are mostly the first kind.

9.6 What belongs in the graph

Nodes are the things that exist; edges are the questions you want answered cheaply. The design discipline is to work backwards from the questions.

Three notes on that figure.

The covered_by edge pays for itself twice. It lets an agent run the right tests rather than the whole suite — which moves a sensor leftward in Chapter 8's Figure 8.3 by making it fast enough to run in-loop. And its absence is information: a symbol with no covering test is an uncovered symbol, which is a computational sensor for coverage gaps that needs no separate tool.

The decided_by edge is the underrated one. Chapter 5 §5.4 established that intent cannot be recovered by asking the author, and that architecture knowledge encodes why which is not recoverable from what. An architectural decision record linked to the modules it governs is how why becomes retrievable at the moment of the change rather than filed in a wiki nobody reads. This is the graph carrying row-2 content — genuine human intent — but indexed by structure so it arrives when relevant. It is the closest thing in this book to a solution for assumption 3's failure, and I have not seen it built anywhere.

The originated edge carries a hazard, marked ⚠ above and taken up in §9.8.

Two design rules, both inherited:

Build for traversals, not for completeness. Ashby's constraint from Chapter 8 applies to graphs as much as to harnesses: you cannot model everything, so model what you will query. A graph designed to be comprehensive is a graph nobody can keep fresh.

Expose it as a tool, not as a payload. The graph belongs behind an interface the agent queries — this is what Codebase-Memory does over MCP, and what Chapter 7 identified as MCP's role as a computational guide. Dumping the graph into context would recreate the dilution problem it exists to solve.

9.7 The case against

This is the section the enthusiasm usually omits, and the evidence for it is stronger than I expected when I started.

Graph-based retrieval often loses. When to use Graphs in RAG asks whether GraphRAG is actually effective and reports negative results: GraphRAG "frequently underperforms vanilla RAG on many real-world tasks despite its conceptual promise" [B]. The authors build GraphRAG-Bench specifically to establish when graphs help — across fact retrieval, complex reasoning, contextual summarisation, and creative generation — precisely because practitioners cannot currently tell. An independent in-depth analysis of graph-based RAG in a unified framework reaches similar cautions 🟡.

There is a scoping argument available here, and I want to make it without hiding behind it. Most GraphRAG work builds knowledge graphs from unstructured text via LLM extraction — lossy, expensive, and unverifiable. Code graphs are derived from an abstract syntax tree — exact, cheap, and mechanically checkable. These are different enough that the negative result does not transfer wholesale, and the AST-derived versus LLM-extracted distinction is itself a live debate in the literature 🔴.

But the honest position is that the code-specific positive evidence is thin: RepoGraph and LocAgent, neither replicated, on public Python benchmarks with the known defects Chapter 2 documented. Two promising results are not a settled case, and the burden of the negative GraphRAG literature is that "add a graph" has a real failure rate.

Freshness is not an operational detail; it is the whole argument. Everything in §9.4 rests on the graph being re-derived. A stale graph is not a slightly worse graph — it is a row-2 asset wearing row-3 authority, which is worse than the context file it replaced, because prose reads as someone's recollection while a graph reads as a fact. Consequences:

• The graph must be regenerated in CI, on every merge, not on a schedule.
• Staleness must itself be a sensor. Chapter 8's drill logic applies directly: introduce a call site, verify the graph reflects it. A graph pipeline that has silently stopped is precisely Böckeler's silent sensor, and it will be discovered by an agent confidently reporting three call sites when there are six.

Sometimes grep wins, and it wins more often than graph advocates admit. The graph's value scales with hop depth, repository size, and the cost of an incomplete answer. In a small repository, for a one-hop lexical question, with an agent that has a competent shell, grep is free, exact for what it can express, and has no freshness cost at all. Chapter 2 is the standing warning: mini-swe-agent scores above 74% with bash and nothing else. Any argument that agents require a graph has to explain that result.

So the decision is a genuine trade-off rather than an upgrade:

9.8 The hazard nobody mentions

One consequence of §9.6's originated edge deserves its own section, because I have not seen it raised and it is not small.

Chapter 5 established that the trust boundary has moved: every artefact an agent reads is potential instruction, and OWASP ranks Agent Goal Hijacking first on the basis that agents cannot reliably distinguish instructions from data [C]. The canonical vector is issue text, because opening an issue requires no privilege.

Now consider a knowledge graph that links issues, pull-request comments, and commit messages to code entities. KGCompass does exactly this; it is a genuinely useful capability, and it improves localisation because issue text often names the right symbols.

It also builds a retrieval path from untrusted input to authoritative-seeming output.

The general form: a graph that mixes derived and asserted edges launders the provenance of the asserted ones. Structural edges are derived from an AST and are as trustworthy as the compiler. Edges from issue text are as trustworthy as whoever typed the issue. Merging them into one typed result set with one visual grammar destroys precisely the distinction Chapter 11 will argue must be preserved.

The mitigation is not to drop the useful edges. It is to keep the distinction in the data:

• Type every edge by provenance — derived (AST, compiler, test runner) versus asserted (human prose, issue text, external documentation).
• Make provenance visible in every query result, so the agent's context carries "this is a claim from issue #4412" rather than an undifferentiated fact.
• Never let asserted edges gate a decision that derived edges could gate. This is Chapter 8's ordering rule applied to graph data: prefer the deterministic source when one exists.

That third rule generalises the chapter's whole argument, which is a pleasant place to arrive: the value of a graph comes from the derived edges, and so does its safety.

9.9 Where this leaves the pillar

Graph engineering sits in the quadrant as a computational guide — feedforward, deterministic, acting before generation. Chapter 7's framing that graph engineering is feedforward guidance made computational is right, and §9.4 adds the reason it matters: computational guides are derived, and derived guidance does not age.

Its ceiling is the same one Chapter 6 hit, one level out. A graph answers where and what. It reduces the payload needed to answer relational questions, and it converts an unbounded retrieval problem into a bounded traversal. What it does not do is reduce the amount of structure there is to traverse. A graph over a codebase with four hundred modules, mutual dependencies, and no layering will faithfully report a tangle. It makes the tangle navigable; it does not make it small.

Which is Chapter 10's move, and the most radical answer in Part II. Rather than describing the structure better or navigating it faster, change the structure so that the context required to modify any module is bounded regardless of the repository's total size. Chapter 8 gave that its theoretical justification: Ashby forces variety reduction, and harnessability is variety reduction already banked. Chapter 10 asks what happens when you bank it deliberately — and, in the most honest section of Part II, admits that the mechanism is compelling and the causal evidence does not yet exist.