CodeCompass: Navigating the Navigation Paradox in Agentic Code Intelligence

AI summary

Overview

Research area: Agentic code intelligence — specifically how LLM coding agents discover which files in a repository they need to read or edit, and whether graph-based structural navigation beats lexical/semantic retrieval.

Technical level: Intermediate. The paper assumes familiarity with retrieval methods (BM25, embeddings), LLM context windows, and agent tool use, but explains its graph machinery and metrics concretely.

Scope: A 258-trial controlled benchmark evaluating an MCP-based code dependency graph tool (CodeCompass) against vanilla Claude Code and BM25-augmented prompting on a 30-task benchmark built from the FastAPI RealWorld example app.

What This Paper Is About

The paper challenges the common assumption that as LLM context windows grow toward millions of tokens, the problem of finding the right files in a codebase simply disappears. It argues that fitting a whole codebase into context does not guarantee the model attends to the architecturally critical files, and it names this gap the "Navigation Paradox": expansion shifts the failure mode from retrieval capacity to navigational salience. To test this, the author builds CodeCompass, an MCP server that exposes static code dependencies (imports, inheritance, instantiation) as a navigable graph, and measures whether Claude Code uses that graph to find files that keyword and vector retrieval cannot surface.

Key Contributions

1. The Navigation Paradox — a theoretical framing of why expanded context windows do not eliminate structural navigation failures in agentic coding systems.
2. A three-group task taxonomy (G1/G2/G3) that operationalizes dependency discoverability and enables controlled measurement of when structural navigation beats retrieval.
3. CodeCompass — an open-source MCP server exposing AST-derived dependency graphs via Neo4j 5.15, evaluated in a fully automated harness across 270 planned trials (258 completed).
4. Empirical evidence that graph navigation yields a 23.2 percentage-point ACS improvement on hidden-dependency tasks with zero benefit on semantic tasks, plus the Veto Protocol — a metric quantifying cases where internal search tools return zero matches for required files but graph traversal successfully surfaces one.

Main Findings

• BM25 dominates on semantic tasks. On G1, BM25 reached 100.0% ± 0.0% ACS (n=24) versus 90.0% ± 20.3% for Vanilla (n=30) and 88.9% ± 21.2% for the Graph condition (n=27).
• Retrieval provides no advantage on hidden-dependency tasks. On G3, BM25 scored 78.2% ± 22.9% (n=28) versus Vanilla's 76.2% ± 23.6% (n=29) — essentially flat.
• Graph navigation delivers a 23.2 percentage-point gain on G3. CodeCompass reached 99.4% ± 3.6% ACS (n=31) on hidden-dependency tasks, versus 76.2% (Vanilla) and 78.2% (BM25).
• The improvement is statistically robust. Welch's t-test: Graph vs Vanilla t=5.23, p<0.001 (n C=31, n A=29); Graph vs BM25 t=4.83, p<0.001 (n C=31, n B=28). The effect exceeds one standard deviation of the baseline distribution (σ_A = 23.2%).
• Tool adoption, not tool quality, is the bottleneck. Across Condition C, 58.0% of trials (51) made zero MCP calls and averaged 80.2% ACS — indistinguishable from Vanilla. The 42.0% of trials (37) that used the tool averaged 99.5% ACS.
• Adoption varies sharply by task group. G1: 22.2% adoption (6/27), 0.22 average calls. G2: 0.0% adoption (0/30), 0.00 average calls. G3: 100% adoption (31/31), 1.16 average calls, 99.5% mean ACS when used.
• The most striking anomaly: zero G2 trials used the tool (0/30), even though structural dependencies are the graph's primary design purpose. The author attributes this to a rational but architecturally incomplete heuristic — Glob+Read already achieves roughly 80% ACS on G1/G2, so the extra step is not judged worthwhile.
• G2 regression. Condition C underperformed both baselines on structural tasks: 76.4% ± 19.7% (n=30) versus 79.7% Vanilla and 85.1% BM25. G2 trials in Condition C used 12.5 mean tool calls versus 12.1 for Vanilla, read 4.0 files, and hit 0.568 required files per file accessed versus 0.580 for Vanilla — the paper attributes the drop to prompt overhead with no graph benefit.
• Prompt engineering substantially fixes adoption. An improved prompt placing a mandatory checklist at the END (to mitigate Lost in the Middle effects) achieved 100% adoption on G3 (31/31 trials), raising mean G3 ACS from 96.6% to 99.4%, after initial G3 adoption sat at 85.7% (30/35).
• The FCTC paradox. Condition C had the highest completion rate (66%, 58/88; versus 62% for BM25 and 54% for Vanilla) but the slowest path to the first required file (1.93 mean steps; versus 1.36 for BM25 and 1.67 for Vanilla). On G3 specifically, C took 2.23 steps versus A's 1.31, yet finished at 99.4% versus 76.2% coverage.
• BM25 is the fastest first-step heuristic, taking 1.14–1.79 steps to the first required file across groups.
• The Veto Protocol pattern is consistent. Task 23 is the clearest case: Conditions A and B globbed and read across app/db/repositories/ but never surfaced database.py, while Condition C's graph call returned it first. Across all G3 trials, every file missed by Condition A but found by Condition C was reachable in 1–2 graph hops from the task's named file and shared fewer than 2 tokens with the task description after stopword removal.

Methodology in Plain English

The author built a 30-task benchmark on the FastAPI RealWorld example app — a production-quality Python blogging API of roughly 3,500 lines across 40 source files. Each task pairs a natural-language modification request with a gold-standard list of files that must be read or edited. Tasks are split into three groups by how the required files can be discovered: G1 (tasks 01–10) where keyword search finds them, G2 (tasks 11–20) where they sit 2–4 import hops away from named files, and G3 (tasks 21–30) where they share no vocabulary with the prompt at all.

Dependencies were extracted by parsing the repository with Python's built-in ast module into three edge types — IMPORTS, INHERITS, INSTANTIATES — resolved to canonical repo-relative paths and stored in Neo4j 5.15. The resulting graph holds 71 nodes and 255 edges (201 IMPORTS, 20 INHERITS, 34 INSTANTIATES). CodeCompass exposes a get_architectural_context(file_path) tool returning the 1-hop neighborhood of a file in both directions.

Three conditions were compared: A (unaugmented Claude Code using claude-sonnet-4-5, with Glob, Grep, Read, Edit available), B (top-10 BM25-ranked files prepended to the prompt, computed over 339 function/class-level chunks with rank-bm25 and aggregated to file level by maximum chunk score), and C (CodeCompass registered as an MCP server, with the agent instructed to call the tool on the primary task file first). Trials ran via claude -p in non-interactive mode with a clean git checkout before each run, and results were extracted from JSONL transcripts. The main metric, Architectural Coverage Score (ACS), is the fraction of required files the agent actually accessed. Secondary metrics are First Correct Tool Call (FCTC), MCP call counts, and Veto Protocol events. The author notes ACS measures navigational completeness, not implementation correctness — a read-but-unedited file still counts.

Why This Matters

Impact on research. The paper reframes the long-context debate from a capacity question to a salience and tool-adoption question. It provides a controlled task taxonomy that predicts in advance where retrieval methods will and will not help — and validates those predictions empirically. It also turns agent tool-adoption behavior into a measurable research variable rather than an implementation detail.

Real-world applications:

• Repository-level refactoring agents that must find every instantiation site when a base class, config key, or payload shape changes.
• Code review and impact-analysis tooling that flags architecturally connected but semantically distant files a reviewer would miss.
• Onboarding and navigation assistants for large or legacy codebases where domain vocabulary does not match file paths.
• CI/CD pipelines that structurally mandate dependency mapping before an automated agent is allowed to edit.

Industry relevance. For teams shipping coding agents, the practical takeaway is that graph infrastructure has high measured value (99.5% ACS when invoked) but near-zero realized value without workflow enforcement — the author notes 38% adoption under an explicit instruction. The paper also argues that a production graph requires domain-expert validation at construction time and ongoing maintenance, framing graph curation as a core engineering practice rather than one-time preprocessing. It notes a stale graph may be worse than no graph because it confidently points agents at wrong dependencies.

Future Directions

1. Structural workflow enforcement. Instead of asking agents to optionally call the graph tool, use tool_choice to force an initial get_architectural_context call, or a multi-agent pipeline where a planning agent always maps dependencies before an execution agent edits.
2. Human-validated graphs. The study used an automated AST graph as a reproducible lower bound; the author argues an SME-curated graph encoding ownership boundaries, change risk, and semantic groupings would narrow the remaining gap further (the paper reports G3 Condition C variance at ±3.6% in the results table and ±7.7% in the discussion).
3. Generalization beyond one codebase. All 30 tasks come from a single Python web application; behavior on other languages, architectural patterns, and repository sizes is untested.
4. Beyond navigation to correctness. ACS does not measure implementation correctness, and no pass@1 or execution-based results are reported. Measuring whether graph-guided discovery produces working patches is an open question, as is whether other models exhibit different tool-adoption heuristics — every trial here used claude-sonnet-4-5.

Target Audience

Researchers and engineers working on LLM coding agents, retrieval-augmented generation for code, and agent tool-use behavior. It is most valuable to practitioners building repository-scale developer tools — IDE assistants, automated refactoring systems, code review platforms — and to researchers interested in long-context limitations, knowledge graphs for code, and the emerging study of agent tool adoption. Readers without a background in retrieval or agent architectures will need some grounding, but the paper's core argument and metrics are explained without heavy formalism.

Authors’ abstract

Modern code intelligence agents operate in contexts exceeding 1 million tokens--far beyond the scale where humans manually locate relevant files. Yet agents consistently fail to discover architecturally critical files when solving real-world coding tasks. We identify the Navigation Paradox: agents perform poorly not due to context limits, but because navigation and retrieval are fundamentally distinct problems. Through 258 automated trials across 30 benchmark tasks on a production FastAPI repository, we demonstrate that graph-based structural navigation via CodeCompass--a Model Context Protocol server exposing dependency graphs--achieves 99.4% task completion on hidden-dependency tasks, a 23.2 percentage-point improvement over vanilla agents (76.2%) and 21.2 points over BM25 retrieval (78.2%).However, we uncover a critical adoption gap: 58% of trials with graph access made zero tool calls, and agents required explicit prompt engineering to adopt the tool consistently. Our findings reveal that the bottleneck is not tool availability but behavioral alignment--agents must be explicitly guided to leverage structural context over lexical heuristics. We contribute: (1) a task taxonomy distinguishing semantic-search, structural, and hidden-dependency scenarios; (2) empirical evidence that graph navigation outperforms retrieval when dependencies lack lexical overlap; and (3) open-source infrastructure for reproducible evaluation of navigation tools.