codemap's call-graph is a static lower bound, and it says so — every call-graph answer that can be
incomplete carries an epistemic: partial label (R1-C13) and the prose caveat "a call resolution can miss
dynamic edges". This page backs that honesty with numbers: how accurate the call graph actually is, where
the ceiling is and why, and what the graph buys you over grep.
Two things are measured here, both reproducible:
- (a) Call-graph accuracy — against a hand-labeled ground truth, plus the intrinsic resolution rate on a real package. Are the edges right, and how many of the true edges do we get?
- (b) grep-vs-graph value — the cost of answering "what breaks if I change this?" with the graph vs with
grep. Is the graph worth building?
TL;DR. On statically-decidable calls the deep tier is sound (100% precision, 100% recall on the labeled suite) and it marks what it cannot resolve. Overall recall against all true edges is ~68% on the suite and ~26% of raw call-sites resolve to internal targets on a real package — the rest are calls into third-party libraries (~46%) or genuinely undecidable dynamic dispatch (~28%). That gap is the price of Python's dynamism, not a bug, and it is the same ceiling every sound static tool hits (~99% precision / ~70% recall in the PyCG literature). For impact questions the graph is ~2× cheaper than grep on unique names and tens of × on polymorphic ones; for "where is X defined" it is no cheaper — grep already nails that.
The natural oracle is PyCG — the academic reference for Python call graphs. It
does not run on Python 3.12: its import-hook machinery collides with the modern stdlib and fails even on
a 3-line file (three layered breakages, the last structural — see the card). Rather than treat a second
imperfect static tool as ground truth, we measure against a hand-labeled micro-suite we own
(research/bench/callgraph_truth/) whose true edges are known by
construction. This is more honest than a cross-check: the labels are auditable and the undecidable cases are
marked, so the ceiling is explicit.
We still cite PyCG's published ceiling as the field's reference point: ~99.2% precision / ~69.9% recall on its own benchmark (Salis et al., ICSE 2021). ~70% recall is not a PyCG weakness — it is the practical limit of sound static analysis on a dynamic language.
12 cases span the spectrum from trivially-decidable to provably-undecidable. Metrics per tier
(fast = stdlib-ast resolver, deep = jedi type inference):
| Tier | Precision | Recall (decidable) | Recall (all true) | Phantom edges |
|---|---|---|---|---|
| fast | 100% | 100% | 66.7% | 0 |
| deep | 100% | 100% | 68.4% | 0 |
Reading it:
- Precision (deep) = 100% — every emitted edge is a real call. No invented edges.
- Recall on decidable edges = 100% — the deep tier misses none of the statically-resolvable calls. This is the "no bugs" metric.
- Recall on all true edges = 68% — the honest number. The missing third are edges no sound analyzer can
resolve: a function passed as a parameter and called via it (higher-order),
getattr(obj, name)()(dynamic dispatch), and value-flow through a string-keyed registry. The suite labels these asceiling, so the gap is visible, not hidden. - The two tiers are close on this suite, and that is recent. Two cases were deep-only until the day
they were not, and neither turned out to be about type inference.
c11_local_import— a callee imported inside the calling function (R1-C30, issue #11) — was a missing per-function name map.c12_reexport— a callee reached through a module that only re-exports it, the most ordinary shape in Python — was a lookup nobody performed: the target the fast tier computed (api.helper) is not a definition, and the re-export it needed was already an edge in the graph (R1-C30-f1, issue #13). Each case carries its own trap for the cheap fix: a sibling function calling the same bare name without importing it, and a call to a name the re-exporting module does not carry. Buying either recall by guessing shows up as a precision loss instead of a better score. - Phantom edges = 0 — no
callsedge points at a non-node on either tier. This did not start clean: the first run of this suite surfaced two soundness warts, both since fixed —- fast tier, inheritance (R1-C13-f1) —
self.<inherited_method>()was over-approximated to a same-class id that doesn't exist (the fast resolver ignored the MRO). Fixed:_class_membersnow maps each inherited member to the base class that defines it, so the edge lands on the real method. Fast precision went 87.5% → 100%. - closure (R1-C13-f2) — a call to a nested inner function emitted an edge to the closure's
unmaterialized id. Fixed by a general guard: an internal edge whose target is not a graph node is
downgraded to unresolved rather than emitted, so the graph never points at nothing (this also removed
40 latent phantom edges on the bquant graph — locals that
jedityped to their own scope-path).
- fast tier, inheritance (R1-C13-f1) —
An accuracy benchmark that only ever prints 100% isn't measuring anything; this one found real bugs on its first run, and now guards against their return in CI. Run it yourself:
python research/bench/callgraph_accuracy.py # human table
python research/bench/callgraph_accuracy.py --check # assert the invariants (also in CI)The micro-suite proves correctness on hard cases; the intrinsic rate shows the shape of the tail on real
code. Aggregated over the bquant deep graph (bquant@cb89a24, the canonical benchmark scope), across
6 323 call-sites in 833 functions:
| Outcome | Share | Meaning |
|---|---|---|
| resolved (internal) | 25.3% | edge into the analyzed package — the call graph you query |
| external | 46.1% | resolved to a third-party library (pandas, numpy, …) — correctly not an internal edge |
| unresolved | 28.6% | local-variable / dynamic call the static tiers can't type — the ceiling tail |
| dynamic | 0.0% | — |
So of the call-sites that could be internal (resolved + unresolved = 3 407), the deep tier resolves ~47%. That is the real-world echo of the suite's 60% — and exactly why the graph is labeled a lower bound. Reproduce:
python - <<'PY'
import json, collections
g = json.load(open("graph.json")) # a bquant deep graph
agg = collections.Counter()
for n in g["nodes"]:
for k, v in (n.get("extras", {}).get("calls") or {}).items():
agg[k] += v
print(dict(agg))
PYThe rate above answers "how much of the call graph is there". The next question is "how was
each piece of it found", and every edge has carried that answer all along in
extras.resolution — six distinguishable routes on calls alone. What it did not carry is
what a route is worth, so an edge found by reading an import binding and an edge produced
by fanning a factory out across a registry family read identically.
Each (edge type, resolution) pair now has a grade — an ordinal, never a probability
(a computed 0.92466… claims a precision that is not there):
| Grade | What produced the edge | Values |
|---|---|---|
exact |
a binding read from the source | self, module, imported, registry, flat, string-key, annotation, name, doc |
inferred |
a type-inference engine (jedi, deep tier) | deep |
heuristic |
a name match, not a binding — an honest over-approximation | registry-candidate |
The vocabulary is closed (codemap/model.py: RESOLUTIONS) and guarded in both directions: a
value the table does not know fails the suite, and so does a row that stops appearing in any
build. The grade is derived, not stored — the graph bytes do not move, and there is no
second copy to disagree with the first.
One caveat the table states rather than hides: on references the field answers a different
question. Three of its four values (annotation, name, doc) name the kind of site, not
the route — so "filter by resolution" is a meaningful request across calls and accesses,
and a confused one across every edge type at once.
Two places use it:
codemap serve … # stats → confidence.by_grade / by_pairq.callers(symbol, min_confidence="exact") # only calls a binding foundMeasured on bquant (fast tier): 5 533 exact, 49 heuristic, 3 021 edges with no route
at all (contains, inherits, … — syntax, nothing to resolve). Those 49 are the whole
difference the filter makes: across the 25 symbols reached by a registry fan-out, callers
returns 50 and callers(min_confidence="exact") returns 1.
The benchmark reproduces, on codemap's ops, the finding from the 936-run apache/superset study: a resolved
call-graph is far cheaper than grep for impact questions and no cheaper for location questions. The
unit is candidates an agent must inspect. Measured on bquant (bquant@cb89a24); auto-picked targets,
no cherry-picking:
| Task | Symbol kind | grep candidates | graph candidates | grep cost multiplier |
|---|---|---|---|---|
| "what breaks if I change the signature?" | unique name | 2 188 | 198 | ~11× |
| polymorphic name | 1 015 | 27 | ~38× (tens of ×; calculate: 5 real sites vs 278 grep lines = 56×) |
|
| "where is X defined?" | any | ≈ real defs | = real defs | ~1× (no advantage) |
Why the split:
- Impact —
grepcannot tell a call from a mention, nor which receiver's method a name refers to. ForBaseIndicator.calculate,grep '\bcalculate\b'returns 278 lines across the 36 classes that define acalculate; the graph's deep type-resolution returns the 5 that actually call this one. grep's precision as a call-finder is 0.02–0.5; most reads are wasted rejecting noise. (Even a unique name can be grep-hostile:logmatches 1 698 lines — a common English word — for 30 real call-sites, 56×.) - Location —
grep 'def NAME'is already precise (~1.0): a definition line is unambiguous. The graph knows nothing grep doesn't, so it earns no advantage. Stating this null result is what keeps the impact claim credible.
The graph's leverage is on relationships, not locations. Reproduce (any git repo + its graph):
python research/bench/grep_vs_graph.py --graph graph.json --repo /path/to/bquant
python research/bench/grep_vs_graph.py --build ./codemap --repo . # dogfood on codemap itselfThe two sections above are about how well calls resolve. A second, independent thing can make an answer a lower bound: a result limit. It is not an accuracy problem at all — the graph knew the whole answer — which is exactly why it slipped past the machinery built for accuracy.
Found by measuring someone else's tool and then asking the same question of our own
(R2 / CodeGraph; post
Two empty columns). search "zone" on a 5 113-node graph
returned 50 of 1 259 matches under an envelope that read, in full, {"ok": true} — in the one op
whose entire job is to tell a cold agent what exists.
The rule now:
Whenever an op accepts a limit, the envelope carries a
limitblock — always, including when nothing was cut.
{"ok": true,
"result": ["…"],
"limit": {"applied": 50, "returned": 50, "total": 1259, "truncated": true}}- Always, not only on truncation: an absent field forces a machine consumer to distinguish "nothing was cut" from "this build does not report cuts", and it cannot.
total: nullis a legitimate answer and is never an omission.semanticis the honest case — the retrieval adapter applies the limit itself, so when it hands back a full page the pre-limit total was never observed. The block says so (total: null,truncated: null, plus anote), and a caller that sees it can widen the limit instead of trusting a number nobody counted.- Orthogonal to
epistemic. An answer can be resolution-partial and limit-truncated; the two say different things, and collapsing them loses which one bit. - Ops bounded by something that is not a slice of a computed list —
pack's token budget,impact's andflows' depth — are exempt in writing (_UNLIMITED_BY_DESIGN), with the reason, so the guard test can tell a deliberate exemption from a forgotten one.
Surfaces: search, semantic, tests, covers, and the MCP transport caps on impact /
call_contract. The CLI prints a one-line footer on truncation only — a person re-reads the command
they just typed; a machine consumer cannot. Enforced by
tests/test_r1c28_limit_envelope.py, whose last test reads the
ops' own source and fails when a new op learns a limit without declaring it. Gap:
gaps/limit_truncation_2026-08-28.md.
- Believe a present edge: precision is 100% on the labeled suite (both tiers) — codemap does not invent calls, and no edge points at a non-node (the two phantom cases the suite first surfaced are fixed and guarded in CI).
- Treat an absent edge as "not proven", never "proven absent": recall against all true edges is
~60%. That is why
impact,callers,callees,flowsandcall_contractall carryepistemic: partial. - Use the graph where it wins — impact / blast-radius / signature-change — and don't bother reaching for
it to locate a well-named symbol;
grepis fine there. - Read the
limitblock before concluding a list is complete.epistemic: partialsays the resolution was a lower bound;limit.truncatedsays the delivery was. An answer can be either, both, or neither.
Harnesses: research/bench/callgraph_accuracy.py,
research/bench/grep_vs_graph.py. Both are guarded in CI
(tests/test_r1c13_*.py). Deterministic — re-run to refresh.