Summary (Overview)

• MemTrace is a provenance-aware memory system for long-horizon coding agents that addresses the dual challenges of context budget strain and repository-change-induced evidence invalidation.
• It introduces state-bound Memory Traces (immutable execution records anchored to repository state) organized in a Memory Trace Graph (MTG) that captures execution order, dependencies, verification, correction, and supersession relations.
• A complementary Repository State Graph (RSG) tracks current files, symbols, tests, and their structural relations, with a projection $\Pi_t$ linking traces to repository entities for evidence validation.
• MemTrace consistently outperforms all fully evaluated baselines across three benchmarks and two harnesses, 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.
• Ablations confirm that persistence alone is insufficient: both structured execution memory (MTG) and repository-state grounding (RSG) are essential for state-consistent memory over long-horizon execution.

Introduction and Theoretical Foundation

The paper addresses a critical gap in long-horizon coding agents: as agents move from isolated bug fixing to cross-file, multi-stage software maintenance, they face two coupled challenges:

1. Context budget strain: Accumulated interaction histories exceed context windows.
2. Evidence invalidation: Repository changes make earlier observations, test outcomes, and decisions inapplicable to the current state.

The authors identify a core problem called state-memory misalignment: the mismatch between recovered history and the current task/repository state. For example, a refreshed context may retrieve an earlier test failure even after a repair and a passing rerun—without relations to later events, the failure may be mistaken for an unresolved issue.

Existing approaches address only parts of this problem:

• Longer context windows accommodate more history but don't validate evidence.
• Prompt compression (LLMLingua, LongLLMLingua) condenses earlier context.
• Observation masking (SWE-Pruner) selectively removes prior observations.
• External memory systems (MemGPT, ReadAgent, MemWalker, RAPTOR) ofload history for later retrieval.
• Repository graphs (CodexGraph, RepoGraph, LocAgent) represent code entities for localization.

However, as the paper states: "access alone does not determine which historical evidence still supports the task state being resumed."

The key theoretical contribution is framing long-horizon coding memory as a state-alignment problem rather than mere history retention—the system must reconstruct the current task state and identify which prior evidence remains valid in the current repository and relevant to the next action.

Methodology

State-Bound Memory Traces

MemTrace organizes history into immutable Memory Traces, each represented as:

$$\tau = \big (x_{\tau}, \rho_{\tau}, \mathcal{E}(\tau), \alpha_{\tau} \big)$$

where:

• $x_{\tau}$: execution evidence and its provenance
• $\rho_{\tau}$: repository state at evidence creation
• $\mathcal{E}(\tau)$: files, symbols, and tests referenced in the body
• $\alpha_{\tau}$: compact Memory Anchor providing stable reference

Traces are sealed (never modified) when a unit of work is complete. Subsequent edits produce new traces and relations, preserving original evidence for provenance while enabling later validation.

Memory Trace Graph (MTG) and Repository State Graph (RSG)

The system maintains two complementary graphs:

• MTG $G_t^M$: one node per trace, with relations for execution order, dependencies, verification, correction, and supersession.
• RSG $G_t^R$: connects task-relevant files, symbols, and tests through defines, calls, imports, and covers relations.

The trace–repository projection is defined as:

$$\Pi_t = \bigl \{(\tau, e) | \tau \in \mathcal{H}_t, e \in \mathcal{E}(\tau) \bigr \} \tag{1}$$

Validated Restoration

A trace is applicable when:

$$\text{applies}(\tau; R_t, m_t) \iff \text{aligned}(\tau, R_t) \land \neg \text{superseded}(\tau, m_t) \tag{2}$$

• aligned: checks recorded source conditions against current repository state $R_t$ using $\rho_\tau$, $\mathcal{E}(\tau)$, and provenance. For test results, both the test and its recorded dependencies must be checked.
• superseded: requires an explicit MTG relation indicating replacement for the current frontier; temporal order alone is insufficient.

Recovery Algorithm

Algorithm 1 (MTG–RSG context recovery) proceeds by:

1. Checkpointing frontier $m_t$ and anchors; offloading completed bodies
2. Initializing queue with anchored/frontier-related traces
3. Expanding via MTG hops and RSG/$\Pi_t$ for query-relevant traces
4. Restoring traces that pass the applicability check and fit the context budget

Empirical Validation / Results

Main Results (Table 2)

Numbers in parentheses are Python-only subsets; SWE-EVO is Python-only.

Component Ablation (Table 3)

Key Findings

1. Harness robustness: Baselines show strong harness sensitivity (e.g., Observation Masking improves SWE-EVO by 17.4 points under Codex CLI but falls 28.3 points below Native under mini-swe-agent), while MemTrace remains effective across both.
2. Python-only gains: MemTrace exceeds RepoGraph by >26 points (Codex) and >32 points (mini-swe-agent) on DeepSWE Python subset.
3. Partial vs. complete resolution: Higher partial-progress metrics don't necessarily translate to higher resolution—MemTrace converts partial progress into complete solutions more effectively.
4. State–memory alignment: Among 9,226 eligible file-bound traces, 57.0% encounter a later change to at least one bound file; the probability that bound files remain unchanged falls to ~0.50 after 1,000 logged event steps (Spearman ρ = 0.49 with repository revisions).
5. Long-horizon scaling: Median stored traces increase (79 → 102.5 → 129), repository revisions (21 → 30 → 41), and semantic invalidations (122 → 142 → 223) across short/medium/long horizons.

Theoretical and Practical Implications

Theoretical implications:

• Shifts the memory paradigm from history retention to state alignment—the critical question is not "what happened?" but "what still applies?"
• Establishes that execution relations (verification, correction, supersession) are essential for reconstructing task state, not just chronological order.
• Demonstrates that repository grounding is task-dependent: more valuable for heterogeneous, repository-level tasks (DeepSWE) than release-level evolution within a small project set (SWE-EVO).

Practical implications:

• MemTrace provides a concrete architecture for state-consistent memory that can be integrated with existing agent harnesses (Codex CLI, mini-swe-agent).
• The MTG–RSG projection enables efficient, selective restoration of evidence rather than wholesale context reloading.
• The system's harness-agnostic performance suggests it addresses a fundamental limitation in current agent memory management rather than being tuned to a specific execution policy.
• The high rate of evidence invalidation (57% of traces affected by later changes) validates the practical necessity of provenance-aware validation.

Conclusion

MemTrace introduces a state-consistent memory system that treats long-horizon coding memory as a state-alignment problem. By binding immutable execution traces to repository state, recording execution relations in an MTG, and validating evidence against the current RSG before restoration, it achieves consistent improvements across three complementary benchmarks and two agent harnesses.

Key takeaways:

• Persistence alone is insufficient—both structured execution memory and repository-state grounding are necessary.
• Evidence validation before reuse is critical given the high rate of repository-driven invalidation.
• Task scope matters: repository grounding is more valuable for heterogeneous, multi-repository tasks.

Future directions include evaluating with additional backbone models and context-window sizes, and extending to persistent development settings spanning multiple tasks and sessions within the same repository.