PaperlayerView exact revision on arXiv

Source-linked AI summary

How Much Static Structure Do Code Agents Need? A Study of Deterministic Anchoring

Zhihao Lin, Mingyi Zhou, Yizhuo Yang, Li Li

arXiv:2606.26979v2cs.SE

TL;DR

Code agents relying on keyword search lack stable structural context, making repository navigation difficult to reproduce. This paper tests lightweight static-analysis annotations as deterministic anchors and finds that they improve localization while making trajectories more disciplined and stable.

  • Problem

    Grep-first agents lack structural context, and stochastic trajectories make their repository navigation difficult to predict and reproduce.

  • Method

    CodeAnchor extracts repository relationships offline and injects them as compact plain-text comments that grep-driven agents consume without changing their control loop.

  • Results

    +2.2 pp Func@5 and −1.6 rounds accompany lightweight topology, while tags roughly halve run-to-run variance and scale-dependent directionality favors inverse-only links in hub-heavy projects.

  • Takeaways & Limitations

    Default to lightweight topology, prune forward edges in large hub-heavy repositories, and reserve dense tags for implicit-dependency cases.

  • Takeaways & Limitations

    The study evaluates only one agent, Codex, and only Python repositories, so effects across agents and languages remain untested.

Abstract

from arXiv · show

LLM-based code agents navigate repositories through keyword search but miss the structural relationships, such as call graphs, inheritance hierarchies, and configuration dependencies, that define how software actually works. This makes agent navigation stochastic and difficult to reproduce across runs. We investigate whether lightweight static analysis can provide deterministic anchors for these agents: stable structural facts injected as plain-text comments that constrain probabilistic exploration and make navigation more predictable. Starting from a strong baseline, Codex from OpenAI, we systematically inject varying granularities of structural annotations and measure their effects on localization, trajectory behavior, and run-to-run stability. Our study identifies what we call the deterministic anchoring effect: static structure helps less by making agents "smarter" and more by making their navigation disciplined and reproducible. Three observations support this finding: (1) Anchoring works: lightweight call/inheritance topology improves function-level localization (+2.2pp Func@5) and shortens trajectories (-1.6 interaction rounds); (2) Anchoring is scale-sensitive: the optimal granularity and directionality depend on repository characteristics, where denser semantics show diminishing returns and hub-heavy projects benefit from inverse-only links that expose "who-calls-me" without forward edges; (3) Anchoring stabilizes: tags raise link-following rate from 0.15-0.18 to 0.21-0.24, roughly halve run-to-run variance, and improve single-run reliability (Pass@1 +3.4 pp) on medium-scale repositories, at the cost of roughly 10% more input tokens. These observations suggest practical guidelines: default to lightweight topology on medium projects, prune forward edges in large repositories, and reserve dense tags for implicit-dependency cases.

1 Introduction

Code agents’ grep-first retrieval misses the structural relationships that govern software, making navigation fragmented and unpredictable. CodeAnchor addresses this mismatch by injecting deterministic static-analysis facts as plain-text tags, and the study finds that lightweight topology improves localization while making trajectories more disciplined and reproducible.

  • Motivation: Grep-first retrieval exposes lexical matches but misses call, inheritance, configuration, and data-flow relationships, forcing agents to rediscover links through fragmented multi-hop queries.This representation mismatch contributes to locally myopic context and unpredictable behavior.
  • Approach: Deterministic anchors are stable repository-level structure facts injected directly into an agent’s text view to constrain probabilistic exploration.The approach preserves text retrieval rather than replacing it with a graph-guided controller.
  • Approach: CodeAnchor performs offline lightweight static analysis and colocates compact plain-text tags encoding calls, inheritance, data flow, and configuration usage.The framework injects these comments into functions, classes, and configuration entries without changing the agent loop.
  • Evaluation: The study instantiates CodeAnchor on Codex and evaluates localization, interaction efficiency, granularity, directionality, trajectory behavior, and run-to-run stability on SWE-bench Lite and SWE-bench Verified.The research questions examine topology, repository-scale sensitivity, and behavioral stability.
  • Findings: +2.2pp Func@5 and −1.6 interaction rounds result from lightweight call/inheritance topology, supporting the deterministic anchoring effect.The introduction characterizes the effect as improved navigation discipline and reproducibility rather than simply greater agent intelligence.

2 Background

Grep-first code agents iteratively use keyword search and snippet inspection to navigate repositories, but this text-oriented approach leaves software’s structural relationships implicit. Agents must therefore rediscover connectivity through ad-hoc multi-hop queries, producing fragmented context and unpredictable navigation paths.

  • Grep-first code agents: Grep-first agents iteratively issue keyword queries, inspect matching snippets, refine hypotheses, and search again.This tool-using architecture is adopted for simplicity, language-agnosticism, and robustness to incomplete code.
  • The connectivity gap: Grep-based retrieval provides high-recall keyword matching but treats the codebase as an unstructured collection of text.The architecture leaves relationships such as calls, inheritance, and configuration propagation implicit.
  • The connectivity gap: Agents must rediscover structural links through ad-hoc multi-hop queries, resulting in fragmented context and unpredictable navigation paths.The connectivity gap motivates investigating whether structural information can improve agent navigation.

3 Motivation and Problem Analysis

Code agents combine lexical retrieve-then-read search with stochastic decision-making, but miss the structural connectivity needed for multi-hop reasoning and reproducible navigation. CodeAnchor addresses this gap by passively injecting lightweight, deterministic structure inline with repository code.

  • Structural mismatch: Agents use a retrieve-then-read loop in which grep or BM25 ranks lexical matches while the LLM supplies precision, leaving code connectivity underrepresented.The baseline treats the repository primarily as unstructured text, despite structural relationships that connect relevant snippets.
  • Structural mismatch: Configuration-driven bugs require tracing values from definitions through transformations and downstream components, a structural chain that structure-blind agents can miss.A single YAML timeout may affect database pools, circuit breakers, and load balancers implemented across different modules.
  • Trajectory instability: Small differences in early queries or summaries can send repeated runs down different branches, making agent trajectories stochastic even for the same issue and configuration.The paper frames a run as an interleaving of tool calls and model invocations rather than a single response.
  • Deterministic anchoring: Deterministic anchors surface stable call, inheritance, data-flow, and configuration structure inline to constrain an otherwise stochastic navigation process.CodeAnchor runs lightweight static analysis offline and injects compact structured comments while preserving grep-based retrieval.
  • Deterministic anchoring: Low optional-tool usage motivates passive injection, placing structural context beside opened code so agents need not decide to invoke an explicit structure-retrieval tool.In a pilot on 20 SWE-bench tasks with an optional call-graph tool, agents typically relied on plain grep instead.
  • Failure modes: Grep-based failures include stopping at call sites and confusing similarly named functions, motivating minimal static structure for multi-hop navigation and disambiguation.The design keeps grep-first tools fixed and injects only enough structure to repair these failure modes.

4 Approach

CodeAnchor adds an offline, task-agnostic static-analysis pipeline that encodes repository structure as removable comments, while preserving a grep-driven agent’s existing control loop and tools. The approach varies structural relation density and directionality across four retrieval views, from raw grep to inverse-only links.

  • System design: CodeAnchor combines offline static analysis with an agent integration layer that exposes structural relationships as structured comments without changing the agent’s high-level control loop.The offline pipeline runs once per repository snapshot or incrementally after code changes and depends only on repository contents.
  • System design: At runtime, grep remains the retrieval primitive: tags appear beside source code as ordinary text, requiring no new tools, APIs, embedding index, or reranking stage.The agent continues using rg and file I/O, while only the repository view changes.
  • Tag representation: Tags use stable entity identifiers and normalized relationship fields for functions, classes, and files, with uniform delimiters that support straightforward identification and removal.Relationships include usedby, invokes, inherits, and imports; tags can be reverted cleanly to untagged code.
  • Configurations: Anchor-Topo exposes containment, imports, calls, and inheritance, whereas Anchor-Dense adds configuration, data-flow, I/O, and selected domain-specific relationships.Dense domain links include test-to-code mappings and plugin registrations for repositories with substantial test harnesses or plugin systems.
  • Configurations: The study compares Baseline raw grep, bidirectional Anchor-Topo, denser Anchor-Dense, and inverse-only Anchor-Inv retrieval views within an otherwise unchanged Codex-style agent.Anchor-Inv retains CALLED_BY while dropping CALLS to isolate hub-heavy search effects.

5 Evaluation · 5.1 Experimental Setup · 5.2 RQ1: Does Topology Help?

The evaluation tests CodeAnchor with GPT-5.1-codex on SWE-bench Lite and Verified, comparing raw-code retrieval with topology, dense, and inverse-only structural views. Basic bidirectional call/inheritance tags improve function localization and shorten trajectories over a strong grep baseline, while structural detours can reduce early file hits but improve downstream function identification and repair.

  • 5 Evaluation: The study evaluates CodeAnchor in a Codex-style agent on SWE-bench Lite and Verified, benchmarks pairing real GitHub issues with tests.The raw baseline achieves approximately 83.2% Func@5 on SWE-bench Lite.
  • 5.1 Experimental Setup: GPT-5.1-codex operates with high thinking effort and navigation-only tools, while patching and tests are disabled to isolate localization effects.All configurations use the same task-oriented prompt; tags are the only experimental variable in retrieved code context.
  • 5.1 Experimental Setup: The evaluation uses 274 SWE-bench Lite instances, 500 Verified instances, and 50-instance-per-dataset stability subsets with k=10 repeats.The stability subsets prioritize cases where Baseline and Anchor-Topo disagree, then add uniform random samples.
  • 5.1 Experimental Setup: Four retrieval views are compared: Baseline, bidirectional Anchor-Topo, denser Anchor-Dense, and inverse-only Anchor-Inv without forward call edges.RQ1 focuses on Baseline versus Anchor-Topo, while RQ2 compares structural variants across repository scales.
  • 5.1 Experimental Setup: Localization success requires all ground-truth files or functions to appear within the top-k retrieved entities, measured by File@k and Func@k.Rounds measures average tool calls; Hops counts navigation transitions, and Link Following Rate classifies structural versus lexical transitions.
  • 5.2 RQ1: Does Topology Help?: +2.2pp Func@5: Anchor-Topo improves function-level recall on Lite over Baseline, with Func@5 reaching statistical significance (McNemar p=0.041).Verified shows smaller but consistent gains: +1.2pp Func@5 and +1.4pp Func@10, with McNemar p=0.023 for Func@10.
  • 5.2 RQ1: Does Topology Help?: −1.6 rounds: Anchor-Topo reduces average trajectory length on Lite, while Verified decreases by −1.5 rounds, indicating more direct navigation.The corresponding averages are 33.7 versus 35.3 on Lite and 40.9 versus 42.4 on Verified.
  • 5.2 RQ1: Does Topology Help?: +12.5 pp repair success: Anchor-Topo resolves 60.0% versus Baseline’s 47.5% on 80 differential Verified instances, despite a possible File@1 detour.Anchor-Topo slightly lowers Lite File@1 by −1.5pp, but agents can still reach the target function within the top few opens.

5.3 RQ2: Granularity and Directionality

Basic topology generally captures most of the benefit, while dense annotations add overhead except for a small set of implicit-dependency tasks. Directionality is scale-dependent: bidirectional links suit medium-scale repositories, whereas inverse-only links perform better in larger hub-heavy repositories.

  • Granularity: Dense annotations leave Lite function accuracy unchanged but add 4.9 rounds and 18.8% more input tokens than basic topology.On Lite, Func@5/10 remain 0.8540, while input tokens rise from 446k to 530k.
  • Granularity: Dense tags rescue 3/274 Lite and 15/500 Verified implicit-dependency instances involving multi-hop value propagation.They can also redirect attention toward high-degree helper functions, causing exploration of utility modules before the bug site.
  • Directionality: On Lite, inverse-only links reduce Func@5 to 0.8242 and increase rounds to 55.0 versus Anchor-Topo.Lite repositories average 35k LOC; removing forward edges eliminates explicit next-step guidance and increases keyword exploration.
  • Practical implication: The practical implication is to adapt structural configuration to repository scale: use bidirectional links for medium repositories and inverse-only links for large hub-heavy repositories.The reported Verified advantage is +0.2pp Func@5 at input-token parity with Anchor-Topo.
  • Directionality: On Verified, inverse-only links reach Func@5 0.6329 and Func@10 0.6389 with 620k tokens versus 618k for Anchor-Topo.Verified repositories average 120k LOC and contain 23% hub nodes, where forward links can overexpose structurally central helpers.

5.4 RQ3: Behavioral Change & Stability

Structural tags shift navigation from keyword hopping toward reproducible structure-following walks, improving target hits, localization, and run-to-run stability. Their benefits depend on repository scale and topology: forward links help Lite, while inverse links avoid structural distraction on hub-heavy Verified repositories.

  • Trajectory Behavior: 0.236 overall LFR makes Anchor-Topo the strongest Lite configuration, while Anchor-Inv reaches only 0.186 without forward edges.Anchor-Topo also reaches 0.163 structural LFR, compared with Anchor-Dense’s 0.158 and Anchor-Inv’s 0.143.
  • Trajectory Behavior: 0.147 → 0.174–0.212 LFR shows that all tagged Verified configurations improve link following, although dense tags can divert agents into irrelevant utility hubs.Anchor-Inv avoids this hub-heavy structural distraction better than dense forward-link configurations.
  • Trajectory Behavior: 27.1% of tag-following hops on Lite and 26.6% on Verified land on ground-truth entities, showing that tags guide agents toward correct targets rather than being followed mechanically.At least one effective hop appears in 55.2% of Lite tasks and 58.7% of Verified tasks.
  • Run-to-Run Stability: Pass@1 +3.4 pp and Pass@3 +2.3 pp show that CodeAnchor improves single-run Lite reliability, while Verified Func@10 increases from 0.422 to 0.468 with smaller variance.On Verified, the paired Func@10 comparison is Δ= + 0.046 (𝑝=0.023, 𝑟𝑟𝑏=0.92), and Anchor-Topo trajectories have 7.2% lower cross-task diversity.

5.5 Case Studies: How Tags Reshape Agent Behavior

Across three SWE-bench Lite case studies, structural tags replace broad keyword search with targeted traversal, increasing relevant-entity discovery and reducing tool use. Their strongest benefit is inverse navigation from leaf functions to callers or enclosing classes, producing deterministic anchoring in medium-scale repositories.

  • Synthesis: Across cases, annotated agents found 2–6× as many relevant entities with fewer tool calls because structural traversal replaced broad keyword search.Inverse navigation via CALLED_BY and PARENT provided the largest advantage when locating callers or enclosing classes from leaf functions.
  • Entity discovery: Tags enabled discovering 8 entities versus 3 for baseline, with 28.6% fewer searches in the Django Http404 case.Inverse navigation from response_for_exception led directly to exception.py and the crash handler, then followed CALLS to RoutePattern.match.
  • Function recall gains: Functions located increased 1 → 6, with 26.7% fewer tool calls in the ImageGrid case.parent:Grid and used by: links enabled direct upward traversal to Grid.__init__ and Grid.set_label_mode, avoiding ambiguous class searches.
  • Tool-call efficiency: Tool calls fell from 34 → 20, searches decreased 30.8%, and discovered entities increased 3× in the SymPy case.Tags exposed the Mul ↔ Add ↔ Pow transformation graph and Basic dependencies, while input tokens fell 16.5% from 1.23M to 1.03M.
  • Synthesis: Tags changed visited files from lexically nearby paths to structurally correct ones, guiding agents toward the correct branch when keyword search produced plausible alternatives.This deterministic anchoring result is reported for medium-scale repositories of 10–50k LOC.

6 Discussion

The discussion concludes that lightweight structural anchoring improves navigation primarily through explicit, robust topology, but its benefits depend on repository scale and stabilize most reliably on medium-scale projects. It recommends topology-aware deployment policies while emphasizing structural augmentation’s selective value, modest token cost, and tolerance for imperfect static analysis.

  • Mechanisms: Call and inheritance edges provide a robust connectivity skeleton for multi-hop navigation, answering who-calls-whom and what-inherits-from-what without exhaustive keyword searches.Topology remains extractable with high precision from incomplete code, whereas data-flow analysis depends on whole-program assumptions that dynamic repositories often violate.
  • Granularity saturation: Func@5/10 remain 0.8540 with Anchor-Dense and Anchor-Topo, while Dense consumes +4.9 rounds and +18.8% more input tokens.On Verified, Dense rescues 15/500 implicit-dependency tasks and lowers Func@5 from 0.6308 to 0.6288.
  • Deployment heuristic: If average call out-degree < 5, use Anchor-Topo; if > 8, use Anchor-Inv; otherwise use capped Anchor-Topo.Lite favors Anchor-Topo at mean out-degree 4.2 and 8% hubs, whereas Verified favors Anchor-Inv at 9.7 and 23% hubs because dense forward links distract retrieval toward utility modules and re-exports.
  • Stability: Stability benefits are most reliable on medium-scale projects (10–50k LOC), while Verified shows per-task variance 0.0832 vs. 0.0916 with Wilcoxon p≈0.11.Hub-heavy repositories introduce additional variance through hub distraction and longer exploration horizons, which topology alone cannot fully constrain.
  • Practical implications: Anchor-Topo adds ∼10% input tokens on average and is most valuable for strong agents handling cross-file dependencies, inheritance, or stability-sensitive tasks.LLMs use imperfect tags as soft hints, biasing probabilistic search while falling back to lexical reasoning when static structure is missing.

7 Threats to Validity and Limitations

The study’s validity is bounded by its single-agent, Python-focused evaluation and conservative static analysis, while controlled configurations and behavioral metrics mitigate key internal and scope-related concerns. The results therefore describe deterministic anchoring under the tested benchmark, agent, language, and evaluation setup rather than universal guarantees.

  • Internal Validity: Configurations fix the agent, prompt, model, and tools while varying only tag presence, and the task-agnostic tagging pipeline uses no ground-truth information.These controls mitigate implementation bias and ground-truth leakage.
  • External Validity: Results are evaluated on SWE-bench Lite and Verified with a single Codex-style agent, so they may not generalize across project types or agents.The benchmarks stress cross-file reasoning but do not cover all project types.
  • External Validity: The evaluation reflects dominant grep-first retrieval rather than universal guarantees, and multi-language effectiveness remains unvalidated beyond Python.The tag schema is language-agnostic, with mature tools available for Java, JavaScript, C++, and Go.
  • Static Analysis Unsoundness: Fewer than 3% of ground-truth functions explicitly use dynamic dispatching constructs, which conservative PyCG and AST extraction can miss.CodeAnchor prioritizes precision over recall, so injected structure is unsound for features such as getattr, reflection, and monkey patching.
  • Evaluation Scope: Tags are intentionally searchable, preventing isolation of post-landing value, while behavioral metrics demonstrate navigational changes beyond first-hit effects.Localization is evaluated without end-to-end repair, and stability analysis uses a 50-task subset with k=10 runs.

8 Related Work

Related work improves code-agent navigation through tool-using systems, explicit code graphs, retrieval enhancement, static-analysis pipelines, and structured representations. CodeAnchor instead injects structural facts as plain-text comments within the grep-first workflow, complementing graph-based retrieval without requiring model or agent modifications.

  • LLM-based code agents: Tool-using code agents and repository-level systems establish the dominant grep-first paradigm that CodeAnchor augments with structural annotations.Related systems include SWE-agent and SWE-Gym, while other work studies alternative action spaces and systematic evaluation.
  • Graph-guided approaches: Graph-guided agents expose call, inheritance, and data-dependency edges through explicit graphs and specialized navigation operators.LocAgent, RANGER, and RepoGraph represent this line, while memory-augmented methods preserve context across navigation steps.
  • Graph-guided approaches: CodeAnchor is complementary to graph-based retrieval, with tags serving as a fast path and graph queries as a possible fallback.The paper treats these approaches as occupying different points and identifies their combination as a natural extension.
  • Retrieval-augmented code agents: Neural, hybrid, and embedding-based retrieval improves lexical matching but returns independent snippets, whereas CodeAnchor carries structural edges usable with plain grep or neural retrieval.Tags encode relationships that retrieval would otherwise need to reconstruct.
  • Static analysis and code representation: Unlike specialized fault-localization pipelines and structured code representations, CodeAnchor encodes static structure as comments without model or agent modifications.Related representations include spectrum-based, mutation-based, IR-based, learning-based, and LLM-based localization, plus serialized ASTs, graph neural networks, structured prompting, and repository summaries.

9 Conclusion

The study identifies a deterministic anchoring effect: static annotations primarily make grep-first code-agent navigation disciplined and reproducible rather than smarter. Lightweight topology improves localization and shortens trajectories, while optimal annotation granularity and directionality vary with repository scale.

  • Deterministic anchoring effect: Static structure makes code-agent navigation more disciplined and reproducible, rather than simply making agents smarter.The effect was observed by injecting structural annotations as plain-text comments at varying granularities.
  • Localization and efficiency: +2.2 pp Func@5 and −1.6 rounds result from lightweight topology annotations.These gains improve localization while shortening agent trajectories.
  • Scale sensitivity: Optimal annotation granularity and directionality depend on repository scale.The conclusion frames structural annotation design as scale-sensitive rather than universally fixed.
Loading 2606.26979v2…