Paper deep dive

Theory of Code Space: Do Code Agents Understand Software Architecture?

Grigory Sapunov

Year: 2026Venue: arXiv preprintArea: cs.SEType: PreprintEmbeddings: 47

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%

Last extracted: 7/20/2026, 5:04:44 AM

Summary

The paper introduces Theory of Code Space (ToCS), a benchmark evaluating AI code agents' ability to construct and maintain architectural understanding in procedurally generated codebases under partial observability. Key findings include a model-dependent Active-Passive Gap, varying self-scaffolding effects from structured belief maps, and dramatic differences in belief state stability, where smaller models sometimes outperform larger ones in maintaining coherent architectural beliefs.

Entities (12)

Theory of Code Space · benchmarkframework · 98%Active-Passive Gap · conceptphenomenon · 95%Claude Sonnet 4.6 · model · 92%Gemini 2.5 Flash · model · 92%Gemini 2.5 Pro · model · 92%GPT-5.3 Codex · model · 92%Architectural Constraint Discovery · taskdimension · 90%Belief State Maintenance · capability · 90%calls_api · edge-type · 85%data_flows_to · edge-type · 85%imports · edge-type · 85%registry_wires · edge-type · 85%

Relation Signals (6)

Theory of Code Space → evaluates → Architectural Understanding

confidence 95% · We introduce Theory of Code Space (ToCS), a benchmark that evaluates whether agents can construct, maintain, and update coherent architectural beliefs during codebase exploration.

Gemini 2.5 Pro → exhibits → Belief State Collapse

confidence 92% · Gemini 2.5 Pro builds a reasonable map... then destroys it in a single probe... catastrophic belief collapse

Gemini 2.5 Flash → exhibits → Stable Belief State

confidence 92% · Gemini 2.5 Flash—the smallest model—loses zero correct edges across all probes.

Theory of Code Space → defines → Edge Types

confidence 90% · Our 'environment' consists of procedurally generated codebases with controlled architectural structure... four typed edge categories

Theory of Code Space → includes → Architectural Constraint Discovery

confidence 90% · Beyond the spatial analogy, we introduce Architectural Constraint Discovery—a dimension absent from spatial benchmarks.

GPT-5.3 Codex → demonstrates → Active-Passive Gap

confidence 88% · one model builds better maps through active exploration than from seeing all files at once... GPT-5.3-Codex... surpasses all baselines

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:AI code agents excel at isolated tasks yet struggle with multi-file software engineering requiring architectural understanding. We introduce Theory of Code Space (ToCS), a benchmark that evaluates whether agents can construct, maintain, and update coherent architectural beliefs during codebase exploration. Agents explore procedurally generated codebases under partial observability -- opening files under a budget -- and periodically externalize their belief state as structured JSON, producing a time-series of architectural understanding. Three findings emerge from experiments with four baselines and six frontier LLMs. First, the Active-Passive Gap is model-dependent: one model builds better maps through active exploration than from seeing all files at once, while another shows the opposite -- revealing that active exploration is itself a non-trivial capability absent from some models. Second, retaining structured belief maps in context acts as self-scaffolding for some models but not others, showing that the mechanism is model-dependent. Third, belief state maintenance varies dramatically: a smaller model maintains perfectly stable beliefs across probes while its larger sibling suffers catastrophic belief collapse -- forgetting previously-discovered components between probes. We release ToCS as open-source software. Code: this https URL

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

45,733 characters extracted from source content.

Expand or collapse full text

Theory of Code Space: Do Code Agents Understand Software Architecture? Grigory Sapunov Intento gs@inten.to Work in progress. All LLM results are preliminary (single run, single prompt, one pattern); model comparison at scale is future work. Collaborations welcome. Abstract AI code agents excel at isolated tasks yet struggle with multi-file software engineering requiring architectural understanding. We introduce Theory of Code Space (ToCS), a benchmark that evaluates whether agents can construct, maintain, and update coherent architectural beliefs during codebase exploration. Agents explore procedurally generated codebases under partial observability—opening files under a budget—and periodically externalize their belief state as structured JSON, producing a time-series of architectural understanding. Three findings emerge from experiments with four baselines and six frontier LLMs. First, the Active-Passive Gap is model-dependent: one model builds better maps through active exploration than from seeing all files at once, while another shows the opposite—revealing that active exploration is itself a non-trivial capability absent from some models. Second, retaining structured belief maps in context acts as self-scaffolding for some models but not others, showing that the mechanism is model-dependent. Third, belief state maintenance varies dramatically: a smaller model maintains perfectly stable beliefs across probes while its larger sibling suffers catastrophic belief collapse—forgetting previously-discovered components between probes. We release ToCS as open-source software.111Code: https://github.com/che-shr-cat/tocs 1 Introduction Large language models achieve remarkable scores on code generation benchmarks (Chen et al., 2021; Austin et al., 2021), creating an expectation that they possess deep understanding of software architecture. Yet practitioners report a persistent gap: models that solve HumanEval problems with ease produce incoherent results when modifying real codebases with dozens of interdependent modules (Jimenez et al., 2024). This gap has resisted satisfying explanation. Recent work on spatial reasoning offers a compelling diagnostic framework. Zhang et al. (2026) introduced the Theory of Space (ToS) benchmark, demonstrating that multimodal models fail to maintain coherent internal “cognitive maps” when actively exploring partially observable environments. They identified two core phenomena: an Active-Passive Gap (models degrade when they must gather information themselves rather than receiving it upfront) and Belief Inertia (models cannot update their spatial beliefs when the environment changes). We hypothesize that the same latent state maintenance failures explain the struggles of code agents. The term “cognitive map” traces to Tolman (1948); in program comprehension, Pennington (1987) and von Mayrhauser and Vans (1995) showed that developers build layered mental models of code—our benchmark operationalizes and measures this process for AI agents. We propose Theory of Code Space (ToCS), a benchmark that transplants this diagnostic framework to software engineering. Rather than grid worlds, our “environment” consists of procedurally generated codebases with controlled architectural structure. Rather than allocentric spatial maps, our “cognitive maps” are structured representations of module dependencies, typed edges, cross-cutting invariants, and design intent. The agent explores under partial observability—opening files one at a time under a budget—and must externalize its architectural belief as structured JSON at regular intervals. Beyond the spatial analogy, we introduce Architectural Constraint Discovery—a dimension absent from spatial benchmarks. In code, architectural decisions encode checkable constraints: a forbidden dependency enforces a service boundary; a validation chain ensures data integrity. We plant explicit, verifiable constraints in our generated codebases and measure whether agents can discover them. Our contributions: (1) the ToCS benchmark framework for active architectural belief construction in code (§3); (2) a procedural codebase generator with four typed edge categories and planted invariants (§4); (3) pilot experiments with four baselines and six LLMs showing a wide capability spread and three surprising findings—a model-dependent Active-Passive Gap, model-dependent self-scaffolding effects, and dramatic belief state instability differences across models (§6–6.5); (4) an open benchmark released for community evaluation (§7). 2 Related Work Code Generation Benchmarks. SWE-bench (Jimenez et al., 2024) evaluates bug-fixing in real GitHub repositories but measures patch correctness, not evolving architectural understanding. ContextBench (Li et al., 2026) advances this by logging agent trajectories and scoring context retrieval precision/recall against human-verified gold contexts—measuring what the agent looked at but not what the agent believes about architecture. SWE-ContextBench (Zhu et al., 2026) tests cross-task experience reuse. RepoBench (Liu et al., 2024) and LoCoBench-Agent (Qiu et al., 2025) evaluate repo-level completion and long-context interaction respectively, with LoCoBench observing a “comprehension-efficiency trade-off” that we formalize as the Active-Passive Gap. RefactorBench (Masai et al., 2025) targets multi-file refactoring but evaluates output correctness without probing belief state. None of these benchmarks require agents to externalize a revisable architectural belief state, impose exploration budgets, or score against typed dependency graphs with planted constraints. We note that our own belief externalization finding (§6) reveals a complementary limitation: even when agents do externalize beliefs, what they report may not reflect what they internally represent. Code Understanding Tools. CodePlan (Bairi et al., 2024) augments LLMs with static-analysis dependency graphs for change propagation—an engineering solution that validates our premise: agents need architectural maps but currently cannot build them alone. Aider’s RepoMap (Gauthier, 2024) uses tree-sitter parsing and PageRank to construct repository context. Code World Models (FAIR CodeGen team et al., 2025) train LLMs on execution traces to improve code reasoning. ToCS provides the diagnostic benchmark to test whether such approaches actually improve architectural belief quality. Spatial Reasoning. Theory of Space (Zhang et al., 2026) demonstrated Active-Passive Gap and Belief Inertia in grid-world environments with multimodal models. Related spatial benchmarks include SpatialVLM (Chen et al., 2024), Habitat (Savva et al., 2019), and OpenEQA (Majumdar et al., 2024), which evaluate spatial reasoning and embodied question answering but do not require constructing revisable belief states. We transplant this framework to code, adding architectural constraint discovery (absent from spatial domains where object placement “why” is rarely meaningful). TOM-SWE (Zhou et al., 2025) models the user’s mental state in SWE agents—complementary to our focus on the agent’s belief about the codebase. 3 Theory of Code Space 3.1 Problem Formulation We formalize codebase understanding as belief construction over a latent architectural state. Let S denote the ground-truth architecture, comprising a typed dependency graph G=(V,E)G=(V,E) with edge types τ∈imports,calls_api,data_flows_to,registry_wiresτ∈\ imports, calls\_api, data\_flows\_to, registry\_wires\, a set of cross-module invariants ℐI, and exported contracts C. At time t, the agent has history ht=(o0:t,a0:t)h_t=(o_0:t,a_0:t) and we evaluate three operations on its belief ℳt(S)M_t(S). Since ℳtM_t is a latent internal state, we measure it through probing: periodically asking the agent to externalize its belief as structured JSON (§3.3). We evaluate: Construct Build ℳtM_t from partial observations gathered through active exploration. Revise Update ℳt→ℳt+ΔtM_t _t+ t when the environment mutates (S→S′S→ S ) and the agent encounters evidence of the change. Exploit Use ℳtM_t to perform a downstream engineering task correctly (v1.0; v0.1 uses counterfactual probes as a proxy). This paper evaluates Construct; Revise and Exploit are implemented in the framework but reserved for future evaluation (§7.5). 3.2 Environment and Action Space The agent interacts with the codebase through five actions with fixed tool semantics: • LIST(d): Filenames in directory d (no contents, no recursion). • OPEN(f): Full contents of file f. Costs 1 action. • SEARCH(q): Matching filepaths + line numbers. No content snippets. Costs 1 action. • INSPECT(f, s): Type signature + docstring of symbol s. No body. Costs 1 action. • DONE(): Terminate. Costs 0 actions. The agent operates under a budget B (default B=20B=20). Critically, SEARCH returns only locations, never content—ensuring that architectural understanding requires deliberate OPEN decisions. INSPECT provides a lightweight discovery channel: docstrings often describe module purpose and relationships (e.g., “wraps stage X”), allowing agents to gather architectural hints at the cost of one action without reading full file contents. 3.3 Cognitive Map Probing Every K=3K=3 actions, the harness interrupts the agent with a structured prompt requesting it to externalize its current architectural belief as JSON. Critically, probing is free: it does not consume an action from the budget B, and the agent retains the same remaining budget before and after a probe. This ensures that measurement does not interfere with exploration strategy—agents are evaluated on their understanding, not on a trade-off between exploring and reporting. The externalized cognitive map ℳ^t M_t contains: (1) component beliefs with status (observed/inferred/unknown), purpose, exported symbols with typed signatures, and typed dependency edges with per-element confidence; (2) invariant beliefs with structured canonical form (type, src, dst, via, pattern) and evidence pointers; (3) uncertainty tracking—explicit list of unexplored regions. The resulting time-series of maps (one every K steps) captures how understanding develops, not just the final state. 3.4 Evaluation Modes ToCS decomposes the Active-Passive Gap through four conditions: • Active: Agent chooses actions under budget B. • Passive-Full: Agent receives the entire codebase; probed once. • Passive-Oracle: Agent receives B files selected by oracle (maximum ground-truth connectivity); one file per step, probed every K. • Passive-Replay: Agent receives the exact observation trace from a prior active run, without making decisions. Each observation counts as one step. This decomposes: APGtotalAPG_total (passive-full −- active) into APGselectionAPG_selection (passive-oracle −- active, the cost of choosing which files) and APGdecisionAPG_decision (passive-replay −- active, the cost of deciding what to do with observations). We report APG decomposition results for GPT-5.3-Codex and Gemini 2.5 Flash in §6.4. 3.5 Architectural Constraint Discovery Beyond structural mapping, we probe whether agents discover planted architectural constraints: • Forbidden dependency: “Module A must not import module C directly.” • Interface-only access: “Module X must access Y only through interface Z.” • Validation chain: “Data must pass through validation before reaching module W.” Each constraint has a discoverability requirement: test evidence, structural patterns, or documentation in the codebase. Scored via counterfactual multiple-choice probes (“Which change would violate an architectural constraint?”). 4 Procedural Codebase Generation 4.1 Architecture Grammar Our v0.1 generator produces Pipeline architecture codebases with controlled anti-triviality measures. A PipelineTemplate grammar defines: • Domain pools: Three domains (data ETL, log processing, text processing), each with 8 semantically coherent processing stages. Medium complexity selects 6–8 stages. • Module roles: Infrastructure (models, base class, config, exceptions, registry), stages (processing steps implementing a common ABC), adapters (wrapping stages with additional behavior), middleware (cross-cutting decorators), utilities, and legacy/distractor modules. • Anti-triviality: (1) Registry wiring—stages connected via config, not direct imports; (2) Adapter indirection—ABC interface layer; (3) Distractor modules—files not in the main pipeline; (4) Neutral naming—mod_a.py, not extract.py; (5) Hidden invariants—constraints discoverable only by reading function bodies or tests. 4.2 Four Edge Types Each generated codebase contains edges of four types, reflecting different methods of discovery: • imports (∼ 67%): Python import statements. Discoverable by AST parsing. • calls_api (∼ 17%): Runtime function calls between modules. Requires reading function bodies; docstrings may provide hints (e.g., “delegates to module X”). • registry_wires (∼ 9%): Config-driven connections where a registry module dynamically loads stages via importlib based on names listed in a JSON config file. No static import statement exists. Requires reading both the config and the registry’s loading logic. • data_flows_to (∼ 7%): Data dependency where one module’s output feeds another’s input. Requires understanding orchestration logic; docstrings on the orchestrator may describe the data flow. These proportions emerge from the Pipeline template: static imports dominate, while semantic edges arise only at architectural boundaries. Crucially, roughly one-third of edges are invisible to import-following, creating a meaningful gap between syntactic analysis and semantic understanding. 4.3 Invariant Planting Each codebase contains 15–16 planted constraints across five types: boundary (forbidden dependencies), dataflow (required processing chains), interface (access-only-through-ABC), invariant (naming/structural conventions), and purpose (design rationales). Every constraint has a structured canonical form with five fields for machine-comparable scoring: type (constraint category), src and dst (the modules involved), via (the intermediary or mechanism, e.g., an ABC interface), and pattern (the structural rule, e.g., “no direct import”). For example, a boundary constraint might be (boundary, mod_a, mod_c, base.StageBase, ‘must access only through ABC’). Each constraint has at least one evidence source (test file, structural pattern, or documentation). 4.4 Generation Statistics Table 1: Generated codebase characteristics (medium complexity, 3 seeds). Metric Seed 42 Seed 123 Seed 999 Modules 27 30 27 Total edges 70 84 70 imports 47 (67%) 56 (67%) 47 (67%) calls_api 12 (17%) 15 (18%) 12 (17%) data_flows_to 5 (7%) 6 (7%) 5 (7%) registry_wires 6 (9%) 7 (8%) 6 (9%) Invariants 15 16 15 Sub-packages 5 5 5 5 Metrics Dependency F1. Compare predicted edges from the cognitive map against ground truth. An edge matches if (source, target, type) all agree via exact string matching. Targets must be specific file paths: a directory-level edge (e.g., registry.py → stages/) does not match file-level ground truth (e.g., registry.py → stages/mod_a.py). Similarly, symbol-qualified targets (e.g., base.py::StageBase instead of base.py) do not match even when the file path portion is correct. This strict matching is deliberate—our ground truth is component-level (one file = one node)—but means that models reporting correct relationships at the wrong granularity or format receive no credit. We report precision, recall, and F1 separately. Invariant F1. Match agent-discovered constraints against planted constraints via structured form comparison on (type, src, dst, via), not text similarity. Strict matching requires exact agreement on all four fields. Relaxed matching normalizes paths (directory prefix stripped), treats empty ground-truth fields as wildcards, and uses greedy 1-to-1 assignment—accommodating models that identify the correct constraint type and endpoints but use slightly different path formats. We report relaxed F1 in the main tables; strict scores are near-zero for all models due to compounding format mismatches. Confidence Calibration. Expected Calibration Error (ECE) between agent-stated per-edge confidence and actual correctness, binned into 5 confidence intervals. Two Efficiency Curves. Action-efficiency: AUC(F1 vs. total actions)—the headline metric. Observation-efficiency: AUC(F1 vs. OPEN count)—diagnostic, isolating information gain per file opened. Belief is piecewise-constant between probes; integration is trapezoidal. Active-Passive Gap. For each metric m: APGm=mpassive−mactiveAPG_m=m_passive-m_active, decomposed into selection and decision components as described in §3. Belief Revision Score (BRS). After a mutation at time tmt_m: BRS=|correctly updated|/|affected elements|BRS=|correctly updated|/|affected elements|. Decomposed into Inertia-proper (correctly-believed elements not updated after evidence) and Impact-discovery (missing elements newly found). A sham condition (evidence without actual change) measures Gullibility. (BRS evaluation is implemented but reserved for future work.) 6 Experiments We evaluate four rule-based exploration strategies and six frontier LLM agents from three providers on three generated codebases (seeds 42, 123, 999) under identical conditions: budget B=20B=20, probe interval K=3K=3. 6.1 Methods Rule-based baselines. • Oracle: Outputs the ground-truth graph directly. Upper bound (F1 = 1.0). • Config-Aware: Lists all directories, opens config/registry files first, parses module references, then follows imports BFS. • Random: Lists root, then opens files uniformly at random until budget exhausted. Builds map from observed imports. • BFS-Import: Opens files breadth-first following import chains. All baselines build cognitive maps from AST-parsed imports and config references. LLM agents. • GPT-5.3-Codex: OpenAI’s code-specialized reasoning model (gpt-5.3-codex). A reasoning model (temperature fixed at 1 per API constraint). • Claude Sonnet 4.6: Anthropic’s frontier coding model (claude-sonnet-4-6). • Gemini 2.5 Flash: Google’s reasoning-optimized flash model (gemini-2.5-flash). A “thinking” model with extended internal reasoning. • Gemini 2.5 Pro: Google’s reasoning-optimized pro model (gemini-2.5-pro). Larger sibling of 2.5 Flash. • Gemini 3 Flash: Google’s frontier flash model (gemini-3-flash-preview). • Gemini 3.1 Pro: Google’s most capable model (gemini-3.1-pro-preview). The flagship of the Gemini 3 family. All models receive identical prompts: a system prompt describing the partial observability environment and available actions, per-turn action prompts showing remaining budget and opened files, and structured JSON probe prompts with schema, per-type field semantics, and worked examples for each invariant type (Appendix A). Relative to an earlier prompt version, the current probe includes explicit edge type decision rules and pairwise invariant decomposition instructions. Temperature is set to 0 except for GPT-5.3-Codex (reasoning model constraint). All probe responses were parsed successfully via the deterministic repair parser (zero format failures across all runs). 6.2 Results Table 2: Performance over 3 codebases (mean ± half-range). Baselines use AST parsing; LLM agents use prompted JSON externalization with improved probe prompts (per-type field semantics, pairwise invariant decomposition). Best non-Oracle in bold. Inv F1 uses relaxed matching (§3.3). Method Type Dep F1 Precision Recall AUC Inv F1 Files Oracle baseline 1.000 1.000 1.000 — — — Config-Aware baseline 0.577 ± .014 0.736 0.475 0.212 ± .007 0.000 13 Random baseline 0.538 ± .028 1.000 0.368 0.142 ± .008 0.000 13 BFS-Import baseline 0.293 ± .060 1.000 0.173 0.079 ± .003 0.000 13 GPT-5.3-Codex LLM 0.676 ± .059 0.782 0.597 0.306 ± .018 0.739 ± .067 15 Claude Sonnet 4.6 LLM 0.664 ± .026 0.983 0.502 0.350 ± .005 0.778 ± .025 13 Gemini 2.5 Flash LLM 0.470 ± .100 0.642 0.373 0.259 ± .037 0.517 ± .154 14 Gemini 3.1 Pro LLM 0.321 ± .128 0.764 0.212 0.140 ± .049 0.423 ± .209 11 Gemini 2.5 Pro LLM 0.242 ± .034 1.000 0.138 0.205 ± .027 0.376 ± .034 12 Gemini 3 Flash LLM 0.147 ± .012 0.897 0.080 0.133 ± .016 0.125 ± .000 12 Table 3: Edge type recall by method (aggregated over 3 codebases). n = total ground-truth edges of each type. Bold = best non-Oracle recall per type. Method imports calls_api data_flows reg._wires (n=150n=150) (n=39n=39) (n=16n=16) (n=19n=19) Config-Aware 0.58 0.00 0.00 1.00 Random 0.55 0.00 0.00 0.00 BFS-Import 0.25 0.00 0.00 0.00 GPT-5.3-Codex 0.69 0.15 0.31 1.00 Claude Sonnet 4.6 0.56 0.15 0.00 1.00 Gemini 2.5 Flash 0.47 0.18 0.00 0.37 Gemini 3.1 Pro 0.27 0.00 0.50 0.00 Gemini 2.5 Pro 0.12 0.08 0.00 0.53 Gemini 3 Flash 0.11 0.00 0.00 0.05 (a) F1 vs. exploration steps. Dashed = LLM agents, solid = baselines. GPT-5.3-Codex reaches highest final F1; Claude Sonnet 4.6 leads on efficiency (AUC). (b) Edge type discovery heatmap. Cells show raw count / ground truth. LLM agents (⋆ ) discover all four edge types; baselines find at most two. (c) Precision, recall, and F1 per method. GPT-5.3-Codex and Claude Sonnet 4.6 surpass all baselines; weaker LLMs show high precision but low recall. Figure 1: Exploration analysis across 4 baselines and 6 LLM agents on medium-complexity codebases (n=3n=3, budget B=20B=20). 6.3 Analysis Two LLM agents surpass all baselines. GPT-5.3-Codex (F1 = 0.676) and Claude Sonnet 4.6 (F1 = 0.664) both exceed Config-Aware (0.577) by 9–10 points. GPT favors broad coverage (highest recall, 0.597); Claude favors targeted exploration (near-perfect precision, 0.983). Both discover all ground-truth REGISTRY_WIRES edges. LLM agents discover all four edge types. LLM agents collectively discover all four edge types (Table 3), while baselines find at most two. The most distinctive capability is DATA_FLOWS_TO discovery—requiring multi-hop reasoning through the orchestrator—where Gemini 3.1 Pro achieves 50% recall and GPT-5.3-Codex 31%. Claude found zero DATA_FLOWS_TO edges despite reading the runner code, illustrating an exploration-comprehension tradeoff: understanding the orchestrator is insufficient without also opening the linked stage modules. Improved prompts unlock invariant discovery. With improved probe prompts, LLM agents achieve substantial invariant F1 under relaxed matching: Claude leads (0.778), followed by GPT (0.739) and Gemini 2.5 Flash (0.517). All models scored zero under the earlier prompt version, confirming this was primarily a prompt specification problem (§7.3). Belief state instability. Gemini 2.5 Pro and 3 Flash reveal catastrophic belief state instability despite opening comparable numbers of files (Figure 2). Gemini 3 Flash exhibits recency bias—each probe reports only recently-examined components. Gemini 2.5 Pro builds a reasonable map (peak F1 = 0.33 at step 9), then destroys it in a single probe. In contrast, Gemini 2.5 Flash—the smallest model—loses zero correct edges across all probes. This suggests belief state maintenance is not a function of model scale but may depend on training objectives. Figure 2: Belief trajectory: Dependency F1 at each probe step (mean over 3 codebases, shaded = std). GPT-5.3-Codex and Claude Sonnet 4.6 accumulate steadily; Gemini 2.5 Flash grows monotonically. Gemini 2.5 Pro peaks at step 6–9 then collapses; Gemini 3.1 Pro shows high variance (stable on one codebase, collapse on another); Gemini 3 Flash remains flat throughout (recency bias). Precision-recall decoupling. Claude Sonnet 4.6 and Gemini 2.5 Pro both achieve near-perfect precision (≥ 0.98), but with dramatically different recall (0.502 vs. 0.138)—high precision alone does not indicate strong understanding. GPT trades precision (0.782) for the highest recall (0.597). Budget effects. Random exploration (F1 = 0.538) performs nearly as well as Config-Aware (0.577) at B=20B=20, but at B=10B=10 Config-Aware’s advantage grows to 3× (Appendix C). The meaningful discrimination at B=20B=20 lies in understanding what you’ve seen: LLM agents discover qualitatively different edge types despite comparable file coverage. 6.4 Active-Passive Gap Decomposition We evaluate the APG decomposition (§3) on two models—GPT-5.3-Codex and Gemini 2.5 Flash—across all three codebases. Table 4 reports Dependency F1 under each condition. Table 4: Active-Passive Gap decomposition (mean ± half-range over 3 codebases, B=20B=20). APGtotal_total = passive-full −- active; APGselection_selection = oracle −- active; APGdecision_decision = active −- replay. Model Condition Dep F1 Inv F1 Description GPT-5.3 Passive-full 0.457 ± .147 0.757 ± .028 All files at once Passive-replay 0.665 ± .034 0.752 ± .036 Same trace, no decisions Active 0.676 ± .059 0.739 ± .067 Agent chooses actions Passive-oracle 0.737 ± .043 0.683 ± .091 Oracle-selected files Gem. 2.5F Passive-full 0.696 ± .125 0.696 ± .120 All files at once Passive-replay 0.561 ± .141 0.665 ± .037 Same trace, no decisions Active 0.469 ± .099 0.516 ± .155 Agent chooses actions Passive-oracle 0.641 ± .058 0.349 ± .079 Oracle-selected files APG decomposition (Dep F1): APGtotalAPG_total −-0.219 / ++0.226 GPT: active >> full; Gemini: full >> active APGselectionAPG_selection ++0.060 / ++0.172 Oracle helps both; larger gap for Gemini APGdecisionAPG_decision ++0.011 / −-0.092 GPT: ≈ 0; Gemini: passive-replay >> active The APG direction is model-dependent. In Theory of Space (Zhang et al., 2026), models consistently degrade in active mode (APG>0APG>0). In code, the direction depends on the model. GPT-5.3-Codex exhibits APGtotal=−0.219APG_total=-0.219: active exploration outperforms receiving the entire codebase at once, consistent across all three codebases. The likely explanation is information overload: presenting 27–30 files simultaneously overwhelms the model’s ability to identify dependency relationships, while sequential exploration allows focused processing. Gemini 2.5 Flash shows the opposite pattern (APGtotal=+0.226APG_total=+0.226): passive-full substantially outperforms active (Dep F1 0.696 vs. 0.469). This suggests that Gemini benefits from seeing all files at once rather than exploring incrementally—consistent with its strong “thinking” reasoning capabilities but weaker exploration strategy. Selection cost is positive for both models. Passive-oracle exceeds Active for both GPT (+0.060) and Gemini (+0.172), indicating suboptimal file selection in both cases. The larger gap for Gemini suggests its exploration strategy is more inefficient, opening less informative files relative to the oracle ordering. Decision cost reveals a qualitative difference. For GPT-5.3-Codex, Active ≈ Passive-replay (0.676 vs. 0.665): the cognitive overhead of making exploration decisions is negligible. For Gemini 2.5 Flash, the pattern reverses: Passive-replay (0.561) exceeds Active (0.469) by 9 points (APGdecision=−0.092APG_decision=-0.092). When given GPT’s observation trace without having to make decisions, Gemini builds better maps than when exploring on its own. This “negative decision cost” suggests that Gemini’s exploration decisions actively hurt its comprehension—perhaps by directing attention to less informative files or by the cognitive overhead of action selection competing with architectural reasoning. Invariant discovery patterns. For both models, passive-full yields the highest invariant F1 (GPT: 0.757, Gemini: 0.696). Passive-oracle scores lowest for both (GPT: 0.683, Gemini: 0.349). Seeing all files at once provides the global context needed for cross-cutting constraint discovery, while sequential presentation—even with optimal file ordering—limits the model’s ability to synthesize invariants spanning multiple modules. Gemini’s invariant scores under passive-oracle are notably low (0.349), suggesting it struggles to combine evidence presented incrementally. 6.5 Probe Condition Ablation We evaluate the effect of probe conditions on both GPT-5.3-Codex and Gemini 2.5 Flash by comparing three tracking modes: probe_as_scratchpad (baseline—JSON map retained in context), no_probe (final map only, no intermediate probes), and probe_only (JSON collected but stripped from context after each probe). Table 5 reports results across 3 codebases. Table 5: Probe condition ablation (mean ± half-range over 3 codebases, B=20B=20). Scratchpad effect = scratchpad −- no-probe. Model Track Dep F1 Inv F1 GPT-5.3-Codex Probe-as-scratchpad 0.676 ± .059 0.739 ± .067 No-probe 0.538 ± .127 0.570 ± .191 Probe-only 0.464 ± .056 0.447 ± .028 Gemini 2.5 Flash Probe-as-scratchpad 0.469 ± .099 0.516 ± .155 No-probe 0.480 ± .161 0.273 ± .040 Probe-only 0.401 ± .143 0.481 ± .222 Scratchpad effect (scratchpad −- no-probe): GPT-5.3-Codex ++0.138 ++0.169 Gemini 2.5 Flash −-0.011 ++0.243 Scratchpad provides a substantial boost for GPT but not for Gemini. For GPT-5.3-Codex, retaining probe JSON in context improves Dep F1 by 13.8 points over the no-probe baseline. The model uses its own prior maps as external working memory, scaffolding subsequent exploration and maintaining belief coherence across probes. This quantitatively confirms the mechanism described in L6 (§7): the probe is not a passive measurement but an active intervention that shapes exploration. For Gemini 2.5 Flash, the scratchpad effect on Dep F1 is negligible (−-0.011): no-probe (0.480) and scratchpad (0.469) perform comparably. However, scratchpad provides a large boost to invariant discovery (++0.243), suggesting that Gemini uses the retained map primarily for cross-cutting reasoning rather than dependency tracking. This model-dependent pattern reveals that the scratchpad mechanism works through different channels for different models. Probe-only is consistently the weakest condition. For both models, probe-only yields the lowest Dep F1 (GPT: 0.464, Gemini: 0.401). Producing structured output consumes attention and context budget without the compensating benefit of self-reference. For GPT, probe-only is even below no-probe (−-0.074), confirming that the overhead of generating structured JSON without retention is actively harmful. For Gemini, the gap is smaller but in the same direction (−-0.079). Implications. For GPT, the ordering is clear: scratchpad >> no-probe >> probe-only, with a 14-point F1 gap between scratchpad and no-probe. For Gemini, the ordering is no-probe ≈ scratchpad >> probe-only, with the primary scratchpad benefit appearing in invariant discovery rather than dependency tracking. This model-dependent pattern complicates benchmark design: the “best” probe condition is not universal. We retain probe-as-scratchpad as the default because it enables the richest trajectory analysis and provides the strongest results for the highest-performing model, but report all three conditions for transparency. 7 Discussion 7.1 Implications for Code Agent Design Current code agents (SWE-agent, Aider, Claude Code, Cursor) use tool-augmented retrieval to navigate repositories, but none explicitly construct or maintain a structured architectural belief. Our results show that the strongest LLM agents can surpass rule-based strategies when they combine semantic comprehension with reliable belief externalization (GPT-5.3-Codex and Claude Sonnet 4.6 both exceed all baselines), but that weaker models fail at the externalization step despite demonstrating code understanding in their exploration behavior. This suggests four improvement paths: (1) hybrid approaches combining AST-level import extraction with LLM semantic analysis, ensuring structural completeness while adding semantic depth; (2) belief externalization training—explicitly optimizing models to faithfully serialize architectural knowledge into structured formats; (3) exploration strategy optimization—our APG decomposition (§6.4) shows a 6–17-point gap between oracle and agent file selection across models, confirming that which files to open is a key bottleneck; and (4) explicit state management—our probe ablation (§6.5) shows that retaining structured belief maps in context yields a 14-point F1 boost for GPT, empirically validating the value of persistent, accumulative state structures—though the effect is model-dependent, indicating that self-scaffolding is itself a capability that varies across models. 7.2 The Belief Externalization Problem GPT-5.3-Codex recalled 69% of IMPORTS edges while Gemini 3 Flash and 2.5 Pro recalled only 11–12% despite opening similar numbers of files. This 6× gap—for edges the models demonstrably saw—shows that belief externalization capability varies dramatically across model families. Both GPT and Claude demonstrate that faithful externalization is achievable: the challenge is model-specific, not fundamental. Belief state instability. The Gemini family reveals three distinct instability patterns. Gemini 2.5 Pro shows catastrophic collapse: building a map by step 9 (peak F1 = 0.33), then losing 12 correct edges in a single probe. Gemini 3 Flash shows recency bias: each probe reports only 3–5 recently-examined components. Gemini 3.1 Pro shows variable instability: monotonic accumulation on its best codebase but collapse to zero edges on its worst. Critically, Gemini 2.5 Flash—the smallest model—exhibits zero correct-edge loss across all probes. This suggests belief state maintenance depends on training objectives, not model scale, and may stem from treating each probe as “summarize from scratch” rather than “incrementally update.” Externalization quality is also likely prompt-dependent; future work should include prompt ablation studies to disentangle model capability from prompt sensitivity. Error analysis: prompt ambiguity drives false positives. Of Gemini 2.5 Flash’s 40 false positive edges, only 2 (5%) are true hallucinations. The dominant failure (45%) is edge type confusion: reporting both IMPORTS and CALLS_API when code both imports and calls a symbol—arguably reasonable given underspecified definitions. Another 22% come from treating non-component files as edge endpoints. This reveals that prompt specification is a first-order variable: what looks like an externalization failure may be a legitimate alternative interpretation. Table 6: Error analysis: edge type confusion on cli.py edges. Gemini reports both IMPORTS and CALLS_API for the same target (symbol-qualified), producing false positives; Claude merges into a single file-level edge. Edge Gemini 2.5 Flash Claude Sonnet 4.6 cli → config IMPORTS IMPORTS cli → runner IMPORTS IMPORTS cli → config::PipelineConfig CALLS_API (FP) — cli → runner::run_pipeline CALLS_API (FP) — cli → runner — CALLS_API (TP) 7.3 Benchmark Design Lessons Building ToCS v0.1 exposed several pitfalls in belief-probing benchmark design: L1: Edge type decision rules. When code both imports and calls a symbol, the prompt must specify which edge type to report. Ambiguity here caused 45% of Gemini 2.5 Flash’s false positives. Fix: explicit decision trees. L2: Component boundaries. Without defining whether test files or configs count as “components,” 22% of FPs came from including non-component endpoints. Fix: explicit inclusion rules in the probe. L3: Invariant field semantics. Generic fields without per-type definitions yielded Inv F1 = 0.0 for all models. Adding worked examples jumped scores to 0.52–0.78 under relaxed matching. L4: Alternative correct answers. Strict exact-match scoring penalizes semantically correct but differently-formatted answers. Fix: tiered or normalized scoring. L5: Prompt specification as experimental variable. What looks like a model capability gap may be a prompt specification gap. A single prompt change moved Gemini 2.5 Flash’s F1 by ++0.141 while barely affecting Claude (++0.012; Table 8 in Appendix). L6: Probes as active interventions. In scratchpad mode, improved probe prompts change not just serialization quality but exploration behavior—on one codebase, GPT-5.3-Codex opened 4 additional stage modules after a more structured probe revealed gaps in its own map (F1: 0.392 → 0.636). The probe condition ablation (§6.5) quantifies this: scratchpad boosts GPT by 14 F1 points but has no dependency-level effect on Gemini—suggesting different models leverage self-scaffolding through different channels. 7.4 Limitations ToCS v0.1 evaluates a single architectural pattern (Pipeline) in a single language (Python) with neutral filenames (mod_a.py), no standalone documentation, and no organic complexity. Six models from three providers are each evaluated on 3 codebases with a single run per model-codebase pair. All results use a single prompt design; different formulations could yield substantially different rankings. The cognitive map externalization is a proxy for internal representation—a model may “know” more than it serializes. 7.5 Roadmap Phase 1 (current): benchmark construction—stress-test the framework with diverse models. Phase 2: community-contributed codebase patterns, additional languages, documentation as a discovery channel, and REVISE mode evaluation. Phase 3: large-scale controlled experiments with repeated runs, open-weight models, and prompt ablation studies. We release the complete toolkit as open-source and invite contributions. 8 Conclusion We introduced ToCS, the first benchmark for active architectural belief construction in code. Three findings stand out. First, the Active-Passive Gap is model-dependent: GPT-5.3-Codex builds better maps through active exploration (APG=−0.22APG=-0.22) while Gemini 2.5 Flash does better receiving all files at once (APG=+0.23APG=+0.23)—showing that active exploration is itself a non-trivial capability. Second, self-scaffolding through belief externalization is model-dependent: scratchpad mode boosts GPT by 14 F1 points but not Gemini. Third, belief state maintenance varies dramatically: the smallest Gemini model maintains perfectly stable beliefs while its larger sibling suffers catastrophic collapse. These findings validate the benchmark’s design—periodic probing reveals dynamics invisible to final-snapshot evaluation—while the design lessons learned from building it (§7.3) are themselves a contribution. We release ToCS as an open benchmark and invite community contributions. References J. Austin, A. Odena, M. Nye, et al. (2021) Program synthesis with large language models. arXiv preprint arXiv:2108.07732. Cited by: §1. R. Bairi, A. Sonwane, A. Kadam, A. I. Daware, S. Upasani, S. K. Rajamani, M. Raghothaman, and C. Shet (2024) CodePlan: repository-level coding using LLMs and planning. In Proceedings of the ACM International Conference on the Foundations of Software Engineering (FSE), Note: arXiv:2309.12499 Cited by: §2. B. Chen, Z. Xu, S. Kirmani, et al. (2024) SpatialVLM: endowing vision-language models with spatial reasoning capabilities. arXiv preprint arXiv:2401.12168. Cited by: §2. M. Chen, J. Tworek, H. Jun, Q. Yuan, et al. (2021) Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374. Cited by: §1. FAIR CodeGen team, J. Copet, Q. Carbonneaux, G. Cohen, J. Gehring, J. Kahn, et al. (2025) CWM: an open-weights LLM for research on code generation with world models. arXiv preprint arXiv:2510.02387. Cited by: §2. P. Gauthier (2024) Aider: AI pair programming in your terminal. Note: https://aider.chatIncludes RepoMap: repository map generation using tree-sitter and PageRank Cited by: §2. C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. Narasimhan (2024) SWE-bench: can language models resolve real-world GitHub issues?. In International Conference on Learning Representations (ICLR), Note: arXiv:2310.06770 Cited by: §1, §2. H. Li, L. Zhu, B. Zhang, R. Feng, J. Wang, Y. Pan, E. T. Barr, F. Sarro, Z. Chu, and H. Ye (2026) ContextBench: a benchmark for context retrieval in coding agents. arXiv preprint arXiv:2602.05892. Cited by: §2. T. Liu, C. Xu, and J. McAuley (2024) RepoBench: benchmarking repository-level code auto-completion systems. In International Conference on Learning Representations (ICLR), Cited by: §2. A. Majumdar, A. Ajay, X. Zhang, P. Putta, S. Yenamandra, M. Henaff, S. Silwal, P. Mcvay, O. Maksymets, S. Arnaud, K. Yadav, et al. (2024) OpenEQA: embodied question answering in the era of foundation models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 16488–16498. Cited by: §2. K. Masai, A. Guha, J. Henkel, and P. Devanbu (2025) RefactorBench: evaluating stateful reasoning in language agents through code. In International Conference on Learning Representations (ICLR), Note: arXiv:2503.07832 Cited by: §2. N. Pennington (1987) Stimulus structures and mental representations in expert comprehension of computer programs. Cognitive Psychology 19 (3), p. 295–341. Cited by: §1. J. Qiu, Z. Liu, Z. Liu, R. Murthy, J. Zhang, H. Chen, S. Wang, M. Zhu, L. Yang, J. Tan, et al. (2025) LoCoBench-Agent: an interactive benchmark for LLM agents in long-context software engineering. arXiv preprint arXiv:2511.13998. Cited by: §2. M. Savva, A. Kadian, O. Maksymets, et al. (2019) Habitat: a platform for embodied AI research. arXiv preprint arXiv:1904.01201. Cited by: §2. E. C. Tolman (1948) Cognitive maps in rats and men. Psychological Review 55 (4), p. 189–208. Cited by: §1. A. von Mayrhauser and A. M. Vans (1995) Program comprehension during software maintenance and evolution. IEEE Computer 28 (8), p. 44–55. Cited by: §1. P. Zhang, Z. Huang, Y. Wang, J. Zhang, L. Xue, Z. Wang, Q. Wang, K. Chandrasegaran, R. Zhang, Y. Choi, R. Krishna, J. Wu, L. Fei-Fei, and M. Li (2026) Theory of space: can foundation models construct spatial beliefs through active exploration?. arXiv preprint arXiv:2602.07055. Cited by: §1, §2, §6.4. X. Zhou, V. Chen, Z. Z. Wang, G. Neubig, M. Sap, and X. Wang (2025) TOM-SWE: user mental modeling for software engineering agents. arXiv preprint arXiv:2510.21903. Cited by: §2. J. Zhu, M. Hu, and J. Wu (2026) SWE context bench: a benchmark for context learning in coding. arXiv preprint arXiv:2602.08316. Cited by: §2. Appendix A Evaluation Prompts System prompt (excerpt). The agent is told: “You are an expert software engineer exploring a codebase you have never seen before. You are operating under PARTIAL OBSERVABILITY […] Available actions: LIST, OPEN, SEARCH, INSPECT, DONE. […] Your goal is to build a complete and accurate ARCHITECTURAL UNDERSTANDING.” The full prompt describes action semantics and exploration strategy tips. Cognitive map probe. After every K actions, the agent receives: “Externalize your current architectural belief as JSON matching the following schema […]” The schema specifies components with status/purpose/exports/edges/confidence, invariants with structured canonical form, and an uncertainty summary. A worked example demonstrates the expected format (see supplementary materials). Appendix B Generated Codebase Example A medium-complexity codebase (seed 42, text processing domain) generates the following structure: text_processor/ +-- __init__.py +-- middleware/ +-- models.py | +-- mod_i.py (logging) +-- base.py | +-- mod_j.py (retry) +-- config.py +-- utils/ +-- exceptions.py | +-- helpers.py +-- registry.py | +-- formatters.py +-- stages/ +-- legacy/ | +-- mod_a.py | +-- old_pipeline.py | +-- mod_b.py | +-- compat.py | +-- mod_c.py +-- runner.py | +-- mod_d.py +-- cli.py | +-- mod_e.py +-- pipeline_config.json | +-- mod_f.py +-- test_smoke.py +-- adapters/ | +-- mod_g.py | +-- mod_h.py Stages implement a StageBase ABC. The registry loads stage ordering from pipeline_config.json. Stages cannot import each other directly (enforced by test). Legacy modules are distractors not in the pipeline flow. Appendix C Budget Sweep To characterize how exploration budget affects discrimination between strategies, we ran all four baselines at B∈10,15,20,25B∈\10,15,20,25\ across 3 codebases. Table 7 reports mean Dependency F1. Table 7: Dependency F1 vs. exploration budget (mean over 3 codebases). Method B=10B=10 B=15B=15 B=20B=20 B=25B=25 Oracle 1.000 1.000 1.000 1.000 Config-Aware 0.175 0.492 0.577 0.626 Random 0.056 0.317 0.538 0.632 BFS-Import 0.078 0.157 0.293 0.603 At tight budgets (B=10B=10), Config-Aware’s strategy of prioritizing registry files yields a 3× advantage over Random (0.175 vs. 0.056). As budget increases, raw coverage dominates: at B=25B=25, Random matches Config-Aware. The meaningful discrimination at B=20B=20 lies in semantic edge discovery by LLM agents. Appendix D Prompt Sensitivity Table 8: Effect of improved probe prompt on Dependency F1 (same 3 codebases, same models, only probe prompt changed). Δ = new −- old. Model Old Prompt New Prompt F1 Gemini 2.5 Flash 0.328 0.469 +0.141 GPT-5.3-Codex 0.564 0.676 +0.113 Claude Sonnet 4.6 0.639 0.664 +0.025 Models with weaker baseline externalization benefit disproportionately from prompt improvements. Claude Sonnet 4.6, which already externalized comprehensively under the old prompt, showed minimal change (++0.025). Main-text results use the improved prompt throughout.

Instant research discovery