TL;DR
MEMOREPAIR introduces a formal framework for managing "cascade updates" in AI agent memory, ensuring that when information is deleted or corrected, all derived artifacts—like summaries, cached outputs, and learned skills—are also repaired or removed. By framing memory maintenance as a graph optimization problem solvable via s-t min-cut, it eliminates stale information exposure while recovering over 90% of memory utility at a fraction of the cost of exhaustive recomputation.
What Problem Does This Paper Address?
Modern AI agents don't just store raw data; they transform it into "derived artifacts" like summaries of past conversations, cached tool outputs, and reusable skills. This creates a complex web of dependencies.
The authors identify a critical failure mode called the cascade update problem. In current systems, if a piece of source information is deleted (e.g., a user revokes a preference) or corrected (e.g., a tool API changes), the change is usually local. However, the descendants of that information—the summaries or skills built upon it—remain in the agent's memory. These "stale" artifacts continue to steer the agent's future actions, leading to privacy leaks, hallucinated tool calls, or broken workflows.
Methods
The authors propose MEMOREPAIR, which treats agentic memory as a directed provenance graph where nodes are artifacts and edges represent causal influence. When a "root" artifact is invalidated, the system follows a "barrier-first" repair contract:
- Withdrawal Barrier: The system immediately hides the entire affected "cascade" (the root and all its descendants) from the agent. This ensures the agent never acts on partially stale information.
- Artifact-Aware Candidate Construction: For every withdrawn artifact, the system generates a potential "successor." Depending on the artifact type, it might recompute (replay tool calls), regenerate (re-summarize using valid data), or perform parametric repair (using machine unlearning techniques for neural network weights).
- Cost-Aware Publication Selection: Repairing everything is computationally expensive. The authors prove that selecting the optimal subset of repairs to republish—subject to the constraint that a child can only be published if its parents are also valid—is a "predecessor-closed selection problem." They show this can be solved exactly and efficiently using a single s-t min-cut algorithm.
- Validation & Republishing: Selected candidates are executed and validated against schemas or behavioral checks. Only those that pass are "republished" to the active memory store.
Datasets
The researchers evaluated MEMOREPAIR across two primary benchmarks:
- ToolBench: A dataset focused on complex tool-use trajectories involving API calls, cached outputs, and executable procedures.
- MemoryArena: A benchmark for long-horizon agentic tasks that involve evolving user preferences, episodic records, and retrieval traces.
They tested three types of events: deletion (removing a preference/record), correction (updating a tool response), and migration (updating an API contract).
Key Insights and Ideas
- Isolation is Mandatory: Simply updating a record isn't enough. Without a "barrier" that hides the entire dependency chain during repair, agents are highly likely to retrieve stale descendants.
- The "Knee" of the Curve: You don't need to repair every single artifact to restore most of the agent's utility. By sweeping a tradeoff parameter ($\lambda$), the authors found a "knee" in the cost-benefit frontier where they could recover ~94% of the utility for ~60% of the cost.
- Synergy in Repair: The paper shows that "store-level" repair (fixing summaries/records) and "parameter-level" repair (fixing neural weights) are complementary. Using both together significantly outperforms using either in isolation.
Key Results
- Zero Exposure: While standard memory systems leave 92.4–99.7% of post-event actions exposed to stale information, MEMOREPAIR reduces this "stale-use" to 0% by guarantee.
- High Recovery, Low Cost: Compared to an exhaustive "Repair All" strategy, MEMOREPAIR recovers 91.1–94.3% of validated successors.
- Efficiency: It achieves these results while reducing the normalized repair-operator cost from 1.00 down to 0.57–0.76.
- Task Utility: The diagnostic task scores ($\Delta$Task) remained within 0.08 points of the exhaustive repair ceiling, proving that the cost-aware selection doesn't significantly hurt agent performance.
Limitations and Future Work
- Provenance Dependency: MEMOREPAIR relies on complete influence provenance. If the system fails to record a dependency edge, stale information can "leak" past the barrier. The authors show that even a 1% drop in provenance fidelity leads to a significant increase in leakage.
- Validation Oracle: The system is only as good as its validation checks. If a repaired artifact passes the schema check but is still semantically subtly wrong, the agent may still fail.
- Neural Skill Inheritance: For neural artifacts, the system inherits the specific strengths and weaknesses of the underlying parameter-level repair operator (like LUNE or NPO). Future work could explore more robust "unlearning" methods integrated into the cascade framework.
Summary updated