MemTrace: State-Consistent Memory for Long-Horizon Coding Agents

AI summary

Overview

Research area: AI agents for software engineering — long-horizon memory and context management for coding agents.

Technical level: Advanced (assumes familiarity with LLM agent harnesses, context windows, retrieval, and code-graph representations).

Scope: MemTrace is a provenance-aware memory system that stores coding-agent execution history as immutable, repository-bound traces and validates that evidence against the current repository state before reusing it after a context refresh.

What This Paper Is About

Coding agents that work on long, multi-file software tasks accumulate interaction histories that strain the context window, and the repository keeps changing underneath them — so earlier observations, test results, and decisions can become stale or wrong. The paper's goal is to make agent memory state-consistent: after a context refresh, the agent should be able to reconstruct where the task actually stands and restore only the historical evidence that still applies to the current code, rather than replaying outdated evidence as if it were still valid.

Key Contributions

1. A state-bound execution-memory representation. Completed units of work are sealed as immutable Memory Traces, each binding execution evidence to the repository state in which it was produced, and recording how later execution supports, revises, or supersedes earlier evidence.
2. MemTrace itself, a system that links a Memory Trace Graph (MTG, recording execution order and dependencies) with a Repository State Graph (RSG, recording current files, symbols, and tests) through shared repository references, so task state can be reconstructed and applicable evidence selectively restored after a context refresh.
3. Empirical validation on three long-horizon coding benchmarks — DeepSWE, SWE-EVO, and SWE-Milestone — where MemTrace outperforms all fully evaluated baselines under matched backbone and agent harness.
4. Ablations and state-alignment diagnostics confirming that persistent storage alone is insufficient, and that structured execution memory and repository-state grounding play complementary roles.

Main Findings

• Headline gains under Codex CLI: MemTrace improves DeepSWE pass@1 by 21.2 points, SWE-EVO Resolved Rate by 4.4 points, and SWE-Milestone Score by 17.8 points, reaching a 46.4% overall score on SWE-Milestone under Codex.
• Consistent wins across harnesses: MemTrace achieves the best primary metric in every benchmark–harness setting (Codex CLI v0.144.4 and mini-swe-agent v2.4.6). Under mini-swe-agent, deltas versus the best baseline are +17.7 (DeepSWE pass@1), +10.8 (SWE-EVO Resolved Rate), and +13.8 (SWE-Milestone Score).
• Baselines are harness-sensitive; MemTrace is not. On SWE-EVO, Observation Masking improves over Native by 17.4 points under Codex CLI but falls 28.3 points below Native under mini-swe-agent. RepoGraph shows a similar reversal.
• Gains persist on Python, where RepoGraph applies. On the DeepSWE Python subset, MemTrace exceeds RepoGraph by more than 26 points under Codex CLI and 32 points under mini-swe-agent.
• Partial progress is not the same as resolution. On SWE-EVO under Codex CLI, Observation Masking has a higher Fix Rate than MemTrace (72.1% vs. 70.6%) but a lower Resolved Rate (65.2% vs. 69.6%). Under mini-swe-agent, MemTrace has a lower Apply rate (93.5% vs. 97.8%) but a much higher Resolved Rate (63.0% vs. 52.2%).
• Milestone conversion: On SWE-Milestone under Codex CLI, MemTrace and RepoGraph are nearly tied on Python Score, Precision, and Recall, yet strict Resolved Rate rises from 8.3% to 16.7%.
• Structured memory matters, and RSG grounding matters most on broad repositories. Ablation under Codex CLI: Trace Store Only reaches 32.1% pass@1 on DeepSWE; adding the MTG raises it to 44.2%; adding the RSG raises it further to 56.6%. On SWE-EVO, removing the RSG leaves Resolved Rate unchanged at 69.6%.
• Stored evidence frequently goes stale. Among 9,226 eligible file-bound Memory Traces, 57.0% see a later change to at least one bound file (95% CI: 52.8–61.3%). The estimated probability that bound files remain unchanged falls to about 0.50 after 1,000 logged event steps (Kaplan–Meier estimate 0.495, 95% CI 0.456–0.530, 3,654 traces at risk).
• More repository revisions means more exposure. Task-level Spearman correlation between revisions and exposure is 0.487 (95% CI 0.305–0.642) over 84 tasks; between revisions and invalidations it is 0.837 (95% CI 0.741–0.899) over 85 tasks.
• Longer execution accumulates more history, not more per-trace exposure. Median stored Memory Traces across short/medium/long DeepSWE groups rise 79 → 102.5 → 129; repository revisions 21 → 30 → 41; semantic evidence invalidations 122 → 142 → 223. The exposure rate itself shows no clear monotonic increase with execution length.
• Wall-clock trade-offs vary by harness and benchmark. MemTrace takes 54.17 minutes per DeepSWE task under Codex CLI versus 42.02 for Native, but 75.30 versus 103.77 under mini-swe-agent; on SWE-EVO it takes 82.05 minutes under Codex CLI versus 30.00 for Native, and 114.03 versus 170.97 under mini-swe-agent.

Methodology in Plain English

The research team treats long-horizon memory as a state-alignment problem rather than a storage problem.

Sealing evidence instead of summarizing it. When a unit of work finishes — an edit, a test outcome, a failure diagnosis, a correction — MemTrace seals it as an immutable record. Each record stores the evidence and its provenance, the repository state at the time it was produced, the files/symbols/tests it references, and a compact anchor that acts as a stable pointer to it. Sealed records are never modified; later edits or corrections create new records and new relations instead.

Two graphs, one projection. A Memory Trace Graph records execution order and four relation types: depend, verify, correct, and supersede. A Repository State Graph records the current files, symbols, and tests, connected through defines, calls, imports, and covers relations (where "covers" means a test-to-code association, not measured coverage or a passing result). The two graphs keep separate nodes; a projection links trace references to repository entities.

Offloading without losing addressability. When working memory approaches the context budget, the bodies of completed traces are removed from the active context while their full records stay in the persistent store. Compact trace synopses and memory anchors remain in context, and omitted anchors stay recoverable through the persistent index.

Retrieval and validation. Retrieval starts from anchored traces, from traces supporting the current frontier, or from repository references. RSG expansion follows a bounded, request-specific sequence of relations, and candidates then expand by at most two MTG hops. A trace is restored only if it passes an applicability check — the recorded source conditions must align with the current repository, and the trace must not be explicitly marked superseded for the current frontier. Temporal order alone is not treated as supersession. Evidence that does not fit the remaining budget is deferred rather than truncated, and if applicable evidence is unavailable, the agent reads the current file or reruns the test.

Evaluation setup. The backbone is deepseek-v4-flash-0731-high with a 200K-token context window and no explicit step limit. Harnesses are Codex CLI v0.144.4 and mini-swe-agent v2.4.6. Baselines are Native (default harness context management), Observation Masking, and RepoGraph (evaluated only on Python tasks per its implementation scope). DeepSWE has 113 tasks across 91 repositories and five languages; SWE-EVO has 48 tasks from seven Python projects, of which two already pass all FAIL_TO_PASS tests without code changes, leaving 46 evaluated; SWE-Milestone has 98 human-verified milestones across seven continuous evolution itineraries spanning five languages. Statistical work uses task-level Spearman correlations and 95% percentile bootstrap intervals from 5,000 resamples with base seed 20260926.

Why This Matters

Impact on research. The paper reframes agent memory from "how do we store and retrieve more history" to "how do we know whether recovered history is still true." That distinction — the authors call the mismatch state-memory misalignment and the resulting symptom task-state drift — is not captured by prompt compression, retrieval systems, or code graphs alone, as the paper's comparison table over Observation Masking, MemGPT, Context as a Tool, Self-GC, Scroll, Zep, MAGE, Ledger, and RepoGraph argues. This gives future memory research a concrete validation criterion to build against.

Real-world applications:

• Long-running automated maintenance of large repositories, where an agent must resume work across many context refreshes without re-reporting already-fixed failures.
• Continuous release engineering, where an agent works through sequential version upgrades and must distinguish completed milestones from outstanding ones.
• CI/CD repair agents that need to know whether a previously recorded test pass still holds after subsequent code changes.
• Enterprise coding assistants operating under fixed context budgets on heterogeneous, multi-language codebases.

Industry relevance. Deployed systems such as Codex CLI already use context compaction to continue long tasks across context boundaries — the paper notes this preserves continuity but does not determine whether recovered evidence still applies. With a 57.0% exposure rate for stored traces and a roughly 0.50 retention probability after 1,000 event steps, stale-evidence reuse is a practical risk in production agents, not a hypothetical one. The code is released at https://github.com/Homy-Xu/MemTrace.

Future Directions

• Broader backbone and context-window coverage. The authors state that future work will evaluate MemTrace with additional backbone models and context-window sizes; all reported results use deepseek-v4-flash-0731-high with a 200K-token window.
• Persistent, multi-session development. Extending MemTrace to settings spanning multiple tasks and sessions within the same repository, rather than single long-horizon tasks.
• Cost–benefit calibration of validation. MemTrace is slower than Native on DeepSWE under Codex CLI (54.17 vs. 42.02 minutes per task) and on SWE-EVO under Codex CLI (82.05 vs. 30.00 minutes), while being faster on both benchmarks under mini-swe-agent. When validation overhead is worth paying remains an open question.
• Where repository grounding is unnecessary. The RSG ablation shows no benefit on SWE-EVO (69.6% either way) but a large gain on DeepSWE (44.2% to 56.6%), suggesting the value of explicit repository grounding depends on task scope. Characterizing that boundary more precisely is an open direction.
• The relationship between partial progress and resolution. The paper observes that higher Fix Rate or Apply rate does not necessarily translate into higher Resolved Rate, leaving open why MemTrace converts partial progress into complete solutions more effectively.

Target Audience

This paper is most useful to AI systems researchers and engineers building long-horizon LLM agents, particularly those working on agent memory, context management, or repository-level code agents. It will also interest practitioners deploying coding agents in production who need agents to survive context refreshes without acting on stale information, and benchmark designers concerned with multi-step software-evolution evaluation. Readers should be comfortable with agent harness architectures, graph-based code representations, and standard software-engineering benchmark metrics.

Authors’ abstract

As coding agents take on long-horizon software evolution tasks spanning multiple files and stages, longer execution trajectories introduce two coupled challenges: (1) accumulated histories strain context budgets, and (2) repository changes can invalidate earlier execution evidence. Existing approaches address these challenges through techniques like larger context windows, compression, retrieval, or repository representations, but often fail to reconstruct a consistent task state after a context refresh or verify whether recalled evidence remains valid. Thus, we introduce MemTrace, a provenance-aware memory system that preserves execution history and aligns its reuse with the evolving task (e.g., iterative cross-file repair) and repository state. MemTrace stores history as immutable Memory Traces anchored to key information (e.g., files, symbols, tests), and organizes their execution order and dependencies in a Memory Trace Graph. When context is constrained, working memory retains only compact Memory Anchors, from which the agent can reconstruct the latest execution state and locate evidence relevant to its next action. Before restoring historical evidence, MemTrace checks its validity against the current repository state and retrieves only what the next action requires. Across three complementary long-horizon coding benchmarks, MemTrace consistently outperforms all fully evaluated baselines under the same backbone and harness, improving DeepSWE pass@1 by 21.2 points, SWE-EVO Resolved Rate by 4.4 points, and SWE-Milestone Score by 17.8 points under Codex CLI.