Codebase Knowledge Base Series (05): Vector Retrieval vs Knowledge Graph — Adding a Call Graph Didn't Help?

That One Query That Keeps Coming Back

If you've followed this series, one query is burned into your memory — Q8: process payment and create Stripe charge.

It's a ghost. It haunted Articles 03 and 04. Every time, vector retrieval tripped over it: Recall@5 = 0.50, hitting only one of the two relevant functions.

The one it missed was calculate_order_total. Its job is "sum item prices, apply discount, compute tax" — its body is full of sum, discount, tax, with no trace of payment or Stripe. In vector space, it's separated from the query "create Stripe charge" by a chasm. No embedding strategy, no chunking strategy could close that semantic gap.

At the end of Article 04, I left a cliffhanger: since semantic similarity fails, switch weapons — use the code's structural relationships. Semantically, calculate_order_total and create_payment_intent have nothing in common, but on the call graph they're neighbors: both are called by the checkout flow process_checkout. That deterministic edge should, in theory, pull the missed function back.

So for this article I built a graph-augmented retrieval system and pointed it at Q8. The result — Q8 did get fixed. But the total score didn't move an inch, and it stumbled on Q1.

This article is the story of that "one-for-one swap," and the truth it reveals about how you should actually use a graph.

Knowledge Graphs Aren't That Mystical

Say "knowledge graph" and many people picture Neo4j, graph databases, elaborate ontology modeling. Applied to code, it's actually much lighter.

A code knowledge graph, in its most basic form, is a call graph: nodes are functions, edges are "who calls whom." process_checkout calls calculate_order_total, so draw a CALLS edge; conversely, calculate_order_total is called by process_checkout, so that's a CALLED_BY edge.

You can build this graph in a few dozen lines with Python's ast module:

def parse_call_graph(source: str) -> dict[str, list[str]]:
    tree = ast.parse(source)
    # First collect all function names
    all_funcs = {n.name for n in ast.walk(tree) if isinstance(n, ast.FunctionDef)}

    call_graph = {}
    for node in ast.walk(tree):
        if not isinstance(node, ast.FunctionDef):
            continue
        callees = []
        for child in ast.walk(node):
            if isinstance(child, ast.Call) and isinstance(child.func, ast.Name):
                if child.func.id in all_funcs and child.func.id != node.name:
                    callees.append(child.func.id)
        call_graph[node.name] = list(dict.fromkeys(callees))
    return call_graph

The idea is straightforward: first walk the tree once to collect all function names (so you can tell whether a call is an "internal" one), then inspect each ast.Call node inside a function body — if the callee's name is in the function set, record an edge. CALLED_BY is just CALLS reversed.

For this experiment's payment module, the parsed call graph looks like this:

create_payment_intent   CALLS → (none)    CALLED_BY ← process_checkout
calculate_order_total   CALLS → (none)    CALLED_BY ← process_checkout
process_checkout        CALLS → [calculate_order_total, create_payment_intent]
process_refund          CALLS → (none)    CALLED_BY ← (none)

Note that this dataset has a new function, process_checkout — a "checkout flow" function that strings together "compute the order total → create a Stripe payment intent" into one complete business flow. It's the intermediate node linking calculate_order_total and create_payment_intent. Remember this node — it's the protagonist of what follows.

[Image: payment module call graph. process_checkout at the top, two CALLS edges pointing to calculate_order_total and create_payment_intent; process_refund sits alone off to the side with no edges. A dashed circle groups process_checkout / calculate_order_total / create_payment_intent into a "payment flow" business cluster.]

Graph-Augmented Retrieval: Seed → Expand → Re-rank

With this graph in hand, retrieval goes from "one shot" to three steps:

Step 1 (seed): Run plain vector retrieval, take the top-3 as "seed nodes." This step is identical to the baseline in previous articles — AST function-level chunking, raw-code embedding.

Step 2 (expand): From the seeds, do a BFS along the call graph, expanding 2 hops outward. Each hop walks both CALLS and CALLED_BY — looking at both "who I call" and "who calls me."

Step 3 (re-rank): The expanded candidate set is now larger; re-rank the whole set by vector score and take the top-5.

Here's the code:

def graph_retrieve(query_emb, indexed, call_graph, called_by, k=5, seed_k=3, hops=2):
    # Step 1: vector retrieval for seeds
    scored = sorted(indexed, key=lambda x: cosine_sim(query_emb, x[1]), reverse=True)
    seeds = {func["name"] for func, _ in scored[:seed_k]}

    # Step 2: BFS expansion
    candidates = set(seeds)
    frontier = set(seeds)
    for _ in range(hops):
        next_f = set()
        for name in frontier:
            next_f.update(call_graph.get(name, []))
            next_f.update(called_by.get(name, []))
        new = next_f - candidates
        candidates.update(new)
        frontier = new

    # Step 3: re-rank by vector score
    scores = {func["name"]: cosine_sim(query_emb, emb) for func, emb in indexed}
    return sorted(candidates, key=lambda n: scores.get(n, 0), reverse=True)[:k]

The design intuition: vector retrieval "roughly finds the right region" (seeds), the call graph "pulls in the neighbors vector missed" (expansion), and finally vector score does one quality pass (re-rank). Sounds airtight.

I ran it against plain vector retrieval on the same data and the same 12 queries. Approach A is vector-only (baseline); Approach B is graph-augmented (seed_k=3, BFS 2 hops).

The Results: Identical Overall Score

First, the totals:

Approach                                R@3      R@5
─────────────────────────────────── ───────  ───────
A_vector_only                         0.889    0.958
B_graph_augmented (seed=3)            0.889    0.958

Identical. Recall@3 both 0.889, Recall@5 both 0.958. Adding a call graph, running BFS expansion — all that work, and the total moved not a single point.

Looking only at this table, it's tempting to conclude: "Graph augmentation is useless, waste of effort." — but that conclusion is wrong, and interestingly so. Because an identical total does not mean the two methods behave identically on every query.

I broke down all 12 queries and found that 10 of them were identical between the two methods (both perfect at 1.00), but 2 queries diverged:

Per-query Recall@5 (divergent cases):
Query                                               Vector    Graph
────────────────────────────────────────────────── ───────  ───────
verify user identity and check JWT token validity     1.00     0.50  ← (graph regresses)
process payment and create Stripe charge              0.50     1.00  ← (graph improves)
(the other 10 queries: identical, both 1.00)

See it? This isn't a "tie" — it's a one-for-one swap:

• Q8 (Stripe payment): vector 0.50, graph 1.00. Graph retrieval fixed the ghost.
• Q1 (verify identity + JWT): vector 1.00, graph 0.50. Graph retrieval broke a query that was already perfect.

Two queries, one up and one down, canceling out exactly — so the total doesn't budge. But what's happening underneath is far more interesting than the total.

[Image: one-for-one swap diagram. Left, Vector-only bar chart: Q1=1.00 (green), Q8=0.50 (red); right, Graph-augmented bar chart: Q1=0.50 (red), Q8=1.00 (green). A bidirectional arrow in the middle labeled "fix one, break one," with "total unchanged: R@5=0.958" below.]

Q8: How Graph Retrieval Fixed It

The good news first. Q8 is the ghost that kept getting missed, and graph retrieval finally caught it. I traced the expansion:

Seeds (vector top-3): ['process_checkout', 'process_refund', 'create_payment_intent']
process_checkout  CALLS→['calculate_order_total', 'create_payment_intent']
create_payment_intent  CALLED_BY←['process_checkout']
Candidates after expansion: ['calculate_order_total', 'create_payment_intent', 'process_checkout', 'process_refund']

Vector top-5: ['process_checkout', 'process_refund', 'create_payment_intent', 'get_payment_history', 'verify_webhook_signature']
Graph top-5:  ['process_checkout', 'process_refund', 'create_payment_intent', 'calculate_order_total']

Stare at these lines. Vector's top-3 seeds include process_checkout — a checkout-flow function that's semantically close to "process payment." Then BFS walks down its CALLS edge and discovers process_checkout calls calculate_order_total. That single hop drags the orphan function — the one stranded outside the semantic gap — into the candidate set.

Compare the top-5 of both methods:

• Vector top-5's slots 4 and 5 are get_payment_history and verify_webhook_signature. These look like "payment" and "Stripe" on the surface, so their vector scores aren't low — but they're useless for this query; they aren't ground truth.
• Graph top-5 has calculate_order_total bumping out those two "semantically related but useless" functions, scoring a hit.

This is exactly the value of the call graph: process_checkout calling calculate_order_total means the two functions collaborate at the business level. Vector space can't see that collaboration (the vocabulary doesn't overlap), but the call graph sees it plainly. A function that's semantically distant but structurally close gets pulled back by that deterministic edge.

Here the story could have ended perfectly — "graph retrieval filled vector's semantic gap." But Q1 disagrees.

Q1: The Price of Graph Retrieval

Now the bad news. Q1 is verify user identity and check JWT token validity, and its ground truth is two functions: validate_jwt_token and verify_password.

Plain vector retrieval scored a perfect 1.00 here — it placed both functions firmly in the top-5. But graph-augmented retrieval scored only 0.50, missing verify_password.

A query that was originally correct became wrong once the graph was added. How?

The problem is a chain reaction between seeds and expansion. In vector's ranking, validate_jwt_token ranks high (making the top-3 seeds), but verify_password ranks slightly lower — around slot 4 or 5. In plain vector's top-5, slots 4 and 5 were exactly where it landed, so it hit.

But graph augmentation adds the "expand" step. BFS starts from the seeds and stuffs every function the seeds call, and every function that calls the seeds, into the candidate pool. The pool suddenly grows. Then during re-ranking, these newly expanded functions also compete for position — and some of them happen to have higher vector scores than verify_password, crowding it out of the top-5 where it had firmly held slots 4-5.

In one sentence: graph expansion inflated the candidate set, and during re-rank the newcomers — "structurally related but query-irrelevant" — diluted the ranking and bumped a function that would otherwise have hit.

[Image: Q1 crowd-out diagram. Left column, Vector top-5: validate_jwt_token at slot 1 (green), verify_password at slot 5 (green, barely on the list); right column, Graph top-5: two gray "structurally-related but query-irrelevant" functions expanded in at slots 4 and 5, pushing verify_password to slot 6 (red, off the list).]

This is the price of naive graph expansion. It's no free lunch — every real-relevant function you recall from outside the semantic gap comes at the risk of crowding out a function that vector ranking would have hit on its own.

Double-Edged: Expanding the Candidate Set Is a Scalpel With a Cost

Put Q8 and Q1 side by side and the nature of graph-augmented retrieval is clear: it's a double-edged sword.

The sharp edge (Q8): it finds functions that are semantically distant but structurally close. calculate_order_total has no semantic tie to "Stripe" — plain vector can never reach it — but it's hit in 2 hops via the intermediate node process_checkout. That's a gain above vector retrieval's ceiling.

The cutting edge (Q1): expanding the candidate set introduces "structurally related but query-irrelevant" functions. When this noise enters re-ranking, it dilutes the precision of vector ranking and crowds out functions vector would have hit on its own.

The key point: both effects use the same mechanism — enlarging the candidate set. You can't take Q8's benefit without Q1's cost, because they're two sides of one coin. The bigger the candidate set, the greater the chance of recovering a missed function, and the greater the risk of crowding out a correct one.

So the seemingly bland result of "total unchanged" is actually the product of these two forces canceling precisely — not "the graph is useless." On this small dataset of only 28 functions, it happened to be one up and one down; on another dataset, the scale could tip either way.

This also explains why so many teams enthusiastically adopt GraphRAG, add call-graph traversal to retrieval, and then find the A/B metrics flat or even slightly down — naive graph traversal bolt-ons tend to bring gains and noise of the same magnitude.

So How Should You Actually Use a Graph?

The conclusion isn't "graphs are useless" — quite the opposite. Q8 proves the structural information a call graph carries is a truth that vector retrieval can't reach. The problem is the usage: crudely doing BFS expansion and re-ranking at retrieval time is the roughest way to use it.

First, let's be clear about when naive graph expansion helps and when it hurts.

When graph expansion helps:

• The query points at an "entry function," while the real implementation function is its dependency. Query "process payment," hit the entry process_checkout, and the function that actually does the work, calculate_order_total, hides under its CALLS edge — expanding along the edge scoops it up. That's Q8.
• Multiple functions in one business flow. create_payment_intent + calculate_order_total + process_checkout in the payment flow form a cluster; they naturally should be recalled together.

When graph expansion hurts:

• A seed function happens to sit in the caller list of a hub node (a high out-degree node, like a execute_query utility called everywhere). Expanding along CALLED_BY drags in a pile of utterly unrelated business functions.
• Functions have a call relationship, but their business meanings differ wildly (utility vs business function). get_payment_history calls execute_query, but that edge is worthless for "payment business" retrieval.

Based on these two groups of scenarios, here are some engineering recommendations:

1. Expansion should be directional. Prefer walking only CALLS edges ("who I depend on"), and be cautious with CALLED_BY edges ("who depends on me"). "Who calls me" usually introduces more noise — one utility function may be called from dozens of places, and reverse expansion detonates the candidate set instantly.

2. Expansion should have module constraints. Only same-module expansion is meaningful. A cross-module call relationship (say, a payment-module function calling the database module's execute_query) expanded in is very likely noise. Add a same_module filter to expansion.

3. Control the hop count. One hop is usually enough. This experiment used 2 hops; Q8 needed exactly 1 hop (process_checkout → calculate_order_total). From 2 hops on, the candidate set inflates exponentially and noise rises sharply.

4. The best approach is to not traverse the graph at retrieval time at all.

This is the crucial one. Rather than doing ad-hoc BFS at retrieval time — traversing, expanding, and re-ranking on every query, which is both slow and noisy — encode the graph's structural information into the embedding content at index time.

Concretely: in each function's chunk, splice in its call-graph metadata fields:

{
    "content": (
        f"# module: payment\n"
        f"# called_by: process_checkout\n"      # who calls me — structure goes into the body
        f"# calls: (none)\n"
        f"def calculate_order_total(items):\n"
        f"    ...\n"
    ),
    "metadata": {"name": "calculate_order_total", "module": "payment"},
}

Now calculate_order_total's chunk carries the line called_by: process_checkout. When the query "process payment" hits process_checkout-related tokens, calculate_order_total's own embedding already contains the process_checkout signal — vector retrieval itself can now sense that structural relationship, with no need to separately traverse the graph at retrieval time.

The benefit is twofold:

• No candidate-set inflation: structural information is "fused" into the vector itself, so there's no need to expand the pool — and thus no Q1-style crowd-out noise.
• Re-rank precision untouched: vector ranking remains the sole ranking signal; structural information only pulls related functions' vectors closer together, rather than stuffing a pile of extra candidates in.

In other words: don't crudely bolt vector and graph together at retrieval time — teach the vector to "learn" the graph at index time. Structural information goes from "a retrieval-time add-on" to "part of the embedding."

Summary

1. The total is a liar. Vector-only and graph-augmented both score Recall@5 = 0.958, identical — but this isn't "the graph is useless"; it's two forces canceling precisely.
2. The failure modes swapped. Graph retrieval fixed Q8 (calculate_order_total hit via process_checkout in 2 hops) but broke Q1 (candidate-set expansion crowded verify_password out of the top-5). One up, one down, netting to zero.
3. The call graph's value is real. "A calls B" means B and A collaborate at the business level — a structural signal invisible in vector space. Q8 proves it can fill vector's semantic gap.
4. Naive graph expansion is double-edged. The single mechanism of enlarging the candidate set brings both the gain of "recovering missed functions" and the noise of "crowding out correct ones" — you can't take one without the other.
5. Engineering-wise, constrain expansion: prefer CALLS edges, restrict to the same module, cap hops at 1.
6. The optimum isn't traversing the graph at retrieval time — it's encoding structural information into embedding content. Add called_by / calls fields to the function chunk so vector retrieval itself senses call relationships — no candidate-set inflation, no re-rank noise, structure moving from "add-on" to "part of the embedding."

In the next article, we'll implement and validate this "encode structure into content" approach — and see whether it can fix Q8 solidly without introducing a Q1-style regression.

References

• Full demo code: codebase-kb-05-graph

Check out PrimeSkills — a curated marketplace of AI agents and skills that have been validated in real-world, enterprise-grade workflows. No fluff, just what actually works.

Find more useful knowledge and interesting products on my Homepage