codegraph/docs/design/adaptive-explore-sizing.md

# Design + status: adaptive `codegraph_explore` sizing (sibling skeletonization)

**Status:** Implemented & validated, **default-on**, on branch
`feat/adaptive-explore-sizing` (initial commit `d6d059f`; **refined 2026-05-29**
after a real-agent A/B exposed a read-back regression — see
"Refinement" below). Escape hatch: `CODEGRAPH_ADAPTIVE_EXPLORE=0`.
**Motivation:** make `codegraph_explore` size its output to the *answer* rather
than always filling the budget cap — so a "sibling-heavy" flow (many
interchangeable implementations of one interface) stops costing *more* than
plain grep/read, without starving "diffuse" flows that genuinely need broad
source.

> **Refinement (2026-05-29) — the read-back regression.** The first cut gated
> only on *off-spine + polymorphic-sibling*. A real-agent A/B (not the
> deterministic probe) showed that this skeletonized two files the agent then
> **Read back**, defeating the point: OkHttp's `RealCall` (it implements the
> 9-impl `Lockable` *mixin*, so it tripped the sibling signal even though it's
> the orchestrator) and Django's `compiler.py` (it *defines* `SQLCompiler` and
> co-locates its subclasses). Two conditions fixed it — a file skeletonizes only
> if it is **not spared**, where **spared = the agent NAMED a callable in it**
> (`getResponseWithInterceptorChain`, `SQLCompiler.execute_sql` → keep it full)
> **UNLESS the file DEFINES a ≥3-impl supertype** (a base+subclasses "family"
> file is huge and Read-anyway, so skeletonizing it *frees explore budget* for
> the sibling files the agent would otherwise Read). Result: OkHttp **3%
> costlier → ~10% cheaper** (RealCall full, 0 read-backs); Django **10% costlier
> → ~10% cheaper** (compiler.py skeleton frees ~6.5 KB of the 28 KB budget; half
> the runs answer with 0 reads). The supertype signal was initially used as a
> *spare* — that was backwards and regressed Django to 9% costlier by starving
> its budget; it is now an *override* of the named-callable spare. The
> single-condition history below is kept for context.

> **Further refinement (2026-05-29) — per-symbol focused view + named-cluster
> survival.** Whole-file skeleton/spare was still too coarse on a real Django
> A/B: the agent Read back `compiler.py` (collapsed → its `execute_sql`/`as_sql`
> bodies elided) and `query.py` (a non-sibling god-file whose `_fetch_all` cluster
> got trimmed). Four changes took both repos from ~9–10% to **~14–17% cheaper**
> with **median 0 reads**:
> 1. **Uniqueness-aware spare** — only a (near-)UNIQUE named callable spares a
>    file. `as_sql` has **110 defs** across every Compiler/Expression subclass;
>    naming it must not keep every backend variant full (it was flooding Django's
>    budget). `getResponseWithInterceptorChain` (1 def) still spares RealCall.
> 2. **Per-symbol focused view** — a collapsed family file shows the **full body**
>    of on-spine / unique-named / canonical-base-supertype methods and only
>    **signatures** for the rest. So `SQLCompiler.execute_sql`/`as_sql` survive
>    while the 80 other symbols + redundant subclasses collapse → no Read-back.
> 3. **Test-file exclusion on all tiers** — a test file (`custom_lookups/tests.py`)
>    was eating 2.3 KB of Django's 28 KB budget; tests rarely answer an
>    architecture question. (Previously only the <500-file tiers excluded them.)
> 4. **Named-cluster survival in non-sibling files** — inject agent-named method
>    defs into a file's clusters even when the gather missed them, rank them at
>    importance 9, and cap cluster selection at `min(per-file, remaining-total)`
>    so high-importance named clusters survive instead of being source-order
>    trimmed (Django's `_fetch_all`, L2237, the last of four big files emitted).
> Controls held: OkHttp 14% cheaper / 0 RealCall read-backs; Excalidraw 31%
> cheaper / 0 reads (god-file clustering unaffected — its big file is emitted
> first, so the budget cap never binds it). OkHttp's interceptors stay a pure
> signature skeleton (no named callable in them, don't define a supertype).

> **Refinement (2026-09-28) — exact targets.** The per-symbol view above still
> lost the one method the agent asked for by its qualified name. On a fresh django
> index `SQLCompiler.as_sql pre_sql_setup get_select` returned `get_select` and
> `pre_sql_setup` in full and `SQLCompiler.as_sql` — step 1 of the rendered Flow,
> 226 lines — as its signature line, on main and on every branch since. Bodies
> were chosen in SOURCE order within a tier, so the unnamed bridge
> `get_qualify_sql` and `get_select` (both above `as_sql` in the file) took the
> cap. The agents' follow-ups (`SQLCompiler.as_sql full body compiler.py:776`,
> `compiler.py lines 900-1003 as_sql tail`) pinned the file but dropped the line
> numbers, returning `SQLInsertCompiler.as_sql` and friends instead; every run
> Read compiler.py. The fix:
> 1. **Exact targets** — a qualified name that resolves to ≤3 callables
>    (`SQLCompiler.as_sql`: 1 of 110), or the callable enclosing a line anchor
>    (`compiler.py:776`). A bare `as_sql` is NOT exact, so the family rules above
>    still keep the 110 overrides as signatures.
> 2. **Tiers in the focused view:** exact → spine step the agent named → unnamed
>    spine bridge → uniquely-named off-spine → family co-named; the spine in CALL
>    order within its tier.
> 3. **Window, never signature, for tiers 0–1.** A body too big for what is left
>    is cut to its head plus the lines where it calls the question's other
>    symbols, and each hole names the explore query that returns it
>    (`codegraph_explore \`compiler.py:871-1001\``).
> 4. **Line anchors** (`query-paths.ts`): `file:line`, `file:a-b`, `#La-Lb`, and
>    prose `lines a-b` / `L a-L b` next to a path. A range renders as exactly that
>    span (cluster path, ranked first).
> 5. **Priced in rendered chars.** The view counted raw source while it rendered
>    line numbers and ~20 signature lines; once windows fill the cap the
>    undercount became a 19% overshoot that zeroed four excalidraw files below it.
>
> Deterministic replay (54 queries × 8 repos): 43 byte-identical; `as_sql`
> complete in all 5 distinct django queries that single it out (was 1, 0, 175,
> 0 and 226 of 226 lines), the `lines 900-1003` span 104/104 (was 1); named-body
> lines 8,706 → 9,443. The trade: where the file's budget cannot hold everything, a large named
> step now wins over several small off-spine bodies (`pb-compiler`: `as_sql` whole,
> `execute_sql`/`results_iter` to signatures).
>
> Agent A/B (`ab-new-vs-baseline.sh`, django, README question pair, Sonnet /
> `--effort high`, RUNS=3, baseline `e63fe2ec`): **Read 0 in 3/3 new runs vs a
> Read of compiler.py in 2/3 baseline runs** — each right after the agent's own
> `SQLCompiler.as_sql … compiler.py:776` explore, the exact follow-up the report
> described. Tool calls 3 → 4 median, retrieval residual 19.5K vs 22.9K tokens,
> median cost $0.195 vs $0.229 and 30s vs 35s (n=3, the last two within noise).
>
> Rebased onto #2062 (protected members paid before incidental ones across
> clusters), which leaves this gap open — `as_sql` 1/226 on that main. The two
> compose: #2062's protected/incidental rule is the cluster path's base, and
> exact targets sit on top of it (ranked first, every member priced in rendered
> chars, held back for lower exact clusters). Re-measured against that main, 59
> queries: 43 byte-identical, named-body lines 9,804 → 10,731, every target span
> above complete.

---

## TL;DR

`codegraph_explore` returned full source for **every** relevant file up to its
char budget. On a question whose answer spans many *same-shaped* classes — e.g.
"how does OkHttp process a request through its interceptor chain?", which touches
~14 `class … : Interceptor` implementations — that meant ~28 KB of mostly
**redundant full bodies**. Because those bodies ride in the context window for
the rest of the session, the WITH-CodeGraph arm cost *more* than the WITHOUT arm
(which answers the well-named interceptor question in ~10 cheap greps). OkHttp
was the benchmark's cost outlier (−3% — i.e. *costlier* than native search).

Fix: when a file is **both (a) off the synthesized flow spine and (b) a
polymorphic sibling**, render it as a **skeleton** (class + member *signatures*,
bodies elided) instead of full source — keeping the on-spine exemplar and the
mechanism in full.

- **OkHttp:** the interceptor-chain flow skeletonizes the 5 redundant
  `: Interceptor` impls while keeping `RealInterceptorChain` (the dispatch
  mechanism) and `RealCall` (the orchestrator the agent named) full → **~10%
  cheaper than native, 0 RealCall read-backs** (see Refinement for the corrected
  numbers; the original `28.5k → 16.6k` / "reads 1 vs 3" figures came from a
  deterministic probe query, not the agent's real query).
- **Django:** the QuerySet→SQL flow skeletonizes `compiler.py` (a
  base+subclasses family file), freeing budget → **~10% cheaper**. (The earlier
  claim that Django was "byte-identical / 0 skeletons" was an artifact of the
  *probe* query; the agent's real query DOES surface the SQLCompiler family.)
- **Excalidraw / Tokio / VS Code / Gin:** explore output is **byte-identical**
  with the flag on/off (0 skeletons) — their flows have no off-spine
  ≥3-implementer sibling group. The corrected gate only *adds* a spare
  condition, so it skeletonizes a **strict subset** of the original gate → these
  repos provably stay at 0 skeletons (verified by probe).

---

## The problem in one picture

`handleExplore` gathers relevant files, sorts by relevance, and fills up to
`maxOutputChars` (the "whole-small-file rule" dumps any relevant file ≤220 lines
in full). The budget is a **target**, not a ceiling:

```
OkHttp explore (shipped):  RealCall (full) + RealInterceptorChain (full)
                         + CallServerInterceptor (full, 8.7k)
                         + Bridge/Connect/Cache/… (full, ~4-5k each)   ← all ~same shape
                         = ~28k, most of it redundant interceptor bodies
```

The agent only needs the **mechanism** (`RealInterceptorChain.proceed` iterating
the chain) + the **contract** every interceptor implements + maybe one concrete
example. The other five full bodies are padding — but only *because they're
interchangeable*. On a diffuse question (Excalidraw's render pipeline:
`mutateElement → … → renderStaticScene`), the off-spine files are **distinct
steps**, and their bodies do real work — eliding them just makes the agent
reconstruct them from signatures (more reasoning, net costlier; see "Dead ends").

So the whole game is: **tell "interchangeable sibling" apart from "distinct
step," cheaply.**

## The gate (refined)

A file is skeletonized iff **all** hold (and `CODEGRAPH_ADAPTIVE_EXPLORE != 0`):

1. **A spine exists.** `buildFlowFromNamedSymbols` returns its path node set
   (`pathNodeIds`) and the full set of agent-named callables (`namedNodeIds`). If
   no spine forms, nothing skeletonizes.

2. **Off the flow spine.** No symbol in the file is on the traced chain — that
   chain is the mechanism the agent is walking, always kept full.

3. **A polymorphic sibling.** The file's class `implements`/`extends` a supertype
   with **≥ 3 implementers** (`MIN_SIBLINGS`) — the signal that it's one of many
   *interchangeable* impls. From real `implements`/`extends` edges, cached.

4. **Not spared.** A file is **spared** (kept full) iff the agent **named a
   callable in it** — a named method/function is something the agent asked to
   *see* (`getResponseWithInterceptorChain`, `SQLCompiler.execute_sql`), not an
   interchangeable leaf — **UNLESS the file itself DEFINES a ≥3-impl supertype**.
   That last clause is the override: a base+subclasses "family" file (Django's
   `compiler.py`) is huge and Read-anyway, so a full copy just eats explore
   budget; skeletonizing it *frees* that budget for the sibling files the agent
   would otherwise Read. So: *named ⇒ spare, unless it's a family file ⇒
   skeletonize anyway.*

Worked through the two repos:

- **`RealInterceptorChain`** — `proceed` is on the spine → kept full (cond. 2).
- **`RealCall`** — off-spine, and it trips the sibling signal via the **9-impl
  `Lockable` mixin** (not because it's an interchangeable interceptor). But the
  agent named `getResponseWithInterceptorChain`/`execute`/`enqueue` in it, and it
  defines no ≥3-impl supertype → **spared, kept full** (cond. 4). This is the fix
  for the read-back: before cond. 4 it skeletonized and the agent Read it back.
- **`BridgeInterceptor` & the other 4** — off-spine, ≥3-impl siblings, named only
  by *type*, define no supertype → **skeletonized**. The win.
- **Django `compiler.py`** — off-spine, a sibling (its subclasses extend
  `SQLCompiler`), the agent named `execute_sql` in it — *but it defines the
  `SQLCompiler` supertype*, so the override fires → **skeletonized** (frees
  budget). Sparing it instead (the wrong first attempt) cost MORE and Read MORE.

## Why "shared supertype with ≥3 implementers" is the signal

The thing that makes OkHttp's interceptors interchangeable is precisely that
they're **N implementations of one interface**, invoked polymorphically. That is
a *structural* property the graph records as `implements`/`extends` edges:

```
14 classes ──implements──▶ Interceptor      (BridgeInterceptor, CacheInterceptor,
                                              CallServerInterceptor, … )
```

Excalidraw's `renderStaticScene`, `Scene`, `Collab` share **no** common
supertype — the ≥3-implementer query returns nothing for them. So the signal
cleanly separates the two repos, and (validated below) leaves every non-sibling
flow untouched.

The `≥ 3` threshold matters: 1:1 "service interface → single impl" pairs (the
common Spring/Java shape) are **not** siblings and stay full. Only genuine
many-impl families (interceptor chains, strategy/visitor families, codec
registries) trip the gate.

## Skeleton rendering

For a skeletonized file we emit the class + member **signature lines** (not
bodies). Because a symbol node's `startLine` can point at a decorator/annotation
(`@Throws`, `@Override`, `@objc`), we scan forward up to 4 lines for the line
that actually *names* the symbol, so the skeleton shows the real signature:

```
#### …/CallServerInterceptor.kt — CallServerInterceptor, intercept, … · skeleton (signatures only; Read for a full body)
```kotlin
30  object CallServerInterceptor : Interceptor {
32  override fun intercept(chain: Interceptor.Chain): Response {
194 private fun shouldIgnoreAndWaitForRealResponse(code: Int): Boolean =
```
```

The header still lists the file's symbols and says `Read for a full body`, so the
agent can pull one specific implementation if it truly needs it.

## Validation (refined gate)

Headless `claude -p`, Opus 4.8, **WITH vs WITHOUT** CodeGraph (the real benchmark
arm, not the on/off probe the first cut used). Cost = median `total_cost_usd`.

| Repo | WITH→WITHOUT cost | WITH reads | WITHOUT reads | RealCall/compiler read-back |
|---|---|---|---|---|
| **OkHttp** (n=4) | **$0.45 → $0.50** (~10% cheaper) | 2 | 3.5 | **0 / —** (RealCall full) |
| **Django** (n=6) | **$0.56 → $0.63** (~10% cheaper) | 2 | 8.5 | half the runs read 0 |

Both were the README's **cost outliers** (OkHttp 3% costlier, Django 10%
costlier) and both flipped to clear wins. OkHttp WITH was cheaper in all 4 runs;
Django in 5 of 6 (n=6 to see through its high variance). WITHOUT baselines match
the README ($0.50/$0.63 vs $0.57/$0.64), so the gain is the WITH-arm improving.

The **decisive check now passes for the right reason**: with the named-callable
spare, OkHttp's `RealCall` stays full and is **never** Read back (it was Read
back in 3/4 runs before the fix). The inert repos (Excalidraw / Tokio / VS Code /
Gin) stay at **0 skeletons** — verified by probe — because the refined gate
skeletonizes a strict subset of the original. (The first cut's "on vs off, reads
flat 1 vs 3" claim came from a deterministic probe query and did **not** hold for
the agent's real query — that mismatch is what this refinement corrects.)

## Dead ends (don't re-attempt these)

1. **Demote/rank low-value files** (e.g. broaden `isLowValuePath` to drop
   `*-testing-support/` fixtures). Improves *content quality* but **not size** —
   explore refills the freed budget with other full bodies (28,478 → 28,424).
   Ranking ≠ shrinking; you must *skeletonize* to shrink.
2. **Gate on entry-node membership.** A precise symbol-bag explore query *names*
   every chain participant, so they're all "entry nodes" — no separation, nothing
   skeletonizes.
3. **Rely on interface-impl synthesizer edges** (`synthesizedBy:'interface-impl'`)
   for the sibling signal. They were **not** created for OkHttp's `Interceptor`
   (a Kotlin `fun interface`), so the signal must come from the real
   `implements`/`extends` edges, not synth edges.
4. **A plain "core-floor" gate** (keep first N full, skeletonize the rest) —
   skeletonized Excalidraw's *distinct* steps → **+17% cost regression**. The
   sibling condition is what makes it safe.
5. **Sparing a file because it DEFINES the supertype** (the first refinement
   attempt). Backwards: a base+subclasses *family* file (Django's `compiler.py`,
   2,266 lines) is huge and Read-anyway, so keeping it full just **eats the 28 KB
   explore budget and starves the sibling files** the agent then Reads — it
   regressed Django to **9% costlier** ($0.71). Defining a supertype is instead
   an **override** that lets a named family file skeletonize anyway.
6. **Validating skeletonization with the deterministic probe query only.** The
   probe (`probe-explore.mjs "<symbol bag>"`) and the *agent's* real explore
   query name symbols differently, so they form different spines and skeletonize
   different files. The probe said "Django: 0 skeletons / reads flat"; the real
   agent query skeletonized `compiler.py` and Read it back. **Always confirm with
   a real-agent A/B (`run-all.sh`), not just the probe.**

## Code

- `src/mcp/tools.ts`
  - `adaptiveExploreEnabled()` — the flag (default on).
  - `buildFlowFromNamedSymbols()` — returns `{ text, pathNodeIds, namedNodeIds }`.
    `namedNodeIds` is every callable the agent named (a superset of the spine) —
    the named-callable spare reads it.
  - `handleExplore()` — two cached helpers: `isPolymorphicSibling()` (a node has
    an outgoing `implements`/`extends` to a ≥3-impl supertype) and
    `definesPolymorphicSupertype()` (a node HAS ≥3 incoming `implements`/`extends`
    — i.e. the file is the family base). The skeleton branch:
    `off-spine && isPolymorphicSibling && !(namedInFile && !definesSupertype)`.
    `exactNodeIds` / `anchorSpans` (the exact targets) and `bodyFocusLines()`
    (what a window of an oversize body must reach) are shared by the focused
    view and the cluster path.
- `src/search/query-paths.ts` — `lineAnchors`: `file:line` / range parsing.
- `__tests__/adaptive-explore-sizing.test.ts` — 7 cases incl. the named-callable
  spare (RealCall) and the supertype-family override (compiler.py).
- `__tests__/explore-exact-target.test.ts` — the django shape in miniature:
  qualified body whole, subclass overrides still signatures, blast-radius lead,
  `file:line` and `lines a-b` anchors, and a windowed body keeping its tail call.

## Frontier / future work

- **Per-symbol skeletonization within a family file.** `compiler.py` is
  skeletonized whole, so `SQLCompiler.execute_sql` (the base mechanism) becomes a
  signature too and *is* Read back in ~half the Django runs. The ideal is to keep
  the base class's methods full and elide only the redundant subclass bodies —
  shrinking the payload without eliding the answer. Whole-file skeletonization
  can't express that yet.
- **Big non-sibling files dominate Django's residual reads.** `query.py` (3,040
  lines) and `sql/query.py` are not polymorphic families, so skeletonization
  can't touch them; the agent Reads them when the 28 KB clustered view is
  insufficient. That's the explore-budget / big-file-clustering frontier, not
  skeletonization.
- **Non-interface sibling families** (Go `HandlerFunc` slices, function-pointer
  registries) aren't caught — they have no `implements`/`extends` edge. Gin's
  middleware chain, for instance, doesn't trip the gate (its handlers are funcs,
  not interface impls).
- **Exemplar selection** when *no* interceptor is on the spine: today all siblings
  skeletonize and the agent leans on the interface contract; showing one as a
  forced exemplar might read slightly better (untested).