EvoGraph-Mem: Failure-Aware Editable Graph Memory for Long-Term Language Agents

arXiv:2608.11248 · cs.AI, cs.MA · Submitted 2026-08-03 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "EvoGraph-Mem: Failure-Aware Editable Graph Memory for Long-Term Language Agents".

Jane: The paper was written by Yuxiang Ren and Yuxi Qian from.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title and Authors: Tom: Alright, welcome back to the show, everybody. Today we're cracking open a fresh one from the arXiv: "EvoGraph-Mem: Failure-Aware Editable Graph Memory for Long-Term Language Agents." Jane, this title is a mouthful, but I think it's hiding something really cool.

Jane: It really is, Tom. And I love the name "EvoGraph" because it hints at the core idea — memory that evolves. We're not just talking about a notebook that an AI agent writes in and never looks back at. We're talking about a living document that gets edited, corrected, and pruned as the agent learns from its mistakes.

Tom: Exactly. And the authors, Yuxiang Ren and Yuxi Qian, they're tackling a problem that I think a lot of people don't even realize exists. We all assume that if an AI remembers something, that's a good thing. But what if the memory is wrong? Or what if it was right for one situation but completely wrong for another?

Jane: That's the "failure-aware" part. The paper points out that a lot of memory systems just store stuff and retrieve it. But they never check if that stored insight is actually still useful. It's like keeping a map from one thousand nine hundred ninety in your car. It worked great back then, but now it's leading you into a lake.

Tom: Ha! That's the perfect analogy. So the authors are saying, look, we need to treat memory like a quality-controlled database, not a junk drawer. They're specifically looking at "insights" — those high-level lessons an agent distills from past tasks. And they're arguing that those insights can go bad.

Jane: Right. An insight might be "when verifying a claim, check multiple sources." That's great for a fact-checking task. But if you apply that same insight to a task where you need to be fast and decisive, it might slow you down or cause you to overthink. So the memory system needs to track when an insight helps and when it hurts.

Tom: And that's what makes this paper so exciting to me. It's not just about making a bigger memory; it's about making a smarter, more honest memory. It's about admitting that the AI might have been wrong, and fixing that memory before it causes more damage down the line.

Jane: Exactly. And the authors have built a whole framework around this. They call it an "editable insight graph." Each insight is a node, and it tracks positive evidence — times it helped — and negative evidence — times it failed. And there's an on/off switch, basically, so if an insight is doing more harm than good, it gets archived.

Tom: So it's like a library that not only shelves books but also checks them out, reads them, and if a book turns out to be full of lies, it gets moved to a locked basement where nobody can check it out again.

Jane: That's the gist. And they've tested this on some pretty tough benchmarks — PDDL planning tasks, HotpotQA multi-hop questions, and FEVER fact verification. The results are impressive, but we'll get into the nitty-gritty of that in a bit.

Tom: I can't wait. So, the big picture here is that we're moving from "memory as storage" to "memory as a living system." And that's a huge shift in how we think about AI agents. Stick around, because next we're going to break down exactly how this graph memory works under the hood.

Summary: Tom: Welcome back. So, Jane, we've set the stage. Now let's get into the meat of "EvoGraph-Mem." How does this thing actually work? Because the summary in the paper is dense, but the core idea is pretty elegant.

Jane: It really is. The framework builds on an existing system called G-Memory, which organizes an agent's history into a graph with different layers — queries, interactions, and insights. But EvoGraph-Mem adds a critical twist. Instead of just storing insights, it makes them editable.

Tom: Right. So each insight node now has three key parts. First, a set of positive evidence — the queries where that insight was genuinely useful. Second, a set of negative evidence — the queries where it was useless or even harmful. And third, an activation state — whether the insight is "live" and can be retrieved, or "archived" and locked away.

Jane: And that changes how retrieval works. Normally, you'd just grab the most similar memory to the current query. But here, they do something smarter. They score each candidate insight by looking at how much positive evidence it has for this type of task, and then they subtract a penalty if there's conflicting negative evidence.

Tom: So it's not just "is this memory similar?" It's "has this memory actually worked for this kind of problem before, and has it ever failed?" That's a much more nuanced question. It's like asking a friend for advice, but only if they've successfully handled that exact situation before, and ignoring them if they've messed it up.

Jane: Exactly. But the real magic happens after the task is done. That's where the "graph controller" comes in. It's a second LLM call that looks at what just happened and decides what to do with each retrieved insight.

Tom: And it has four operations. KEEP — the insight worked, so we add this query to its positive evidence. ARCHIVE — the insight was wrong or misleading, so we add the query to negative evidence and deactivate the node. REVISE — the insight was partially right but too broad or outdated, so we archive the old one and create a new, corrected version. And ADD — if the task revealed a brand new reusable lesson, we create a fresh insight node.

Jane: That's the "failure-aware" part in action. The system doesn't just blindly accumulate. It actively corrects itself. And the paper shows that this matters. In their experiments, they found that append-only memory — just adding stuff and never removing it — is not enough for long-horizon tasks.

Tom: Right. And the numbers back that up. On the HotpotQA dataset with GPT-4o-mini, they got an exact match accuracy of forty-three point four three percent, compared to thirty-five point six seven percent for the best baseline, G-Memory. That's a huge jump. And on PDDL, they got a thirty point six seven percent progress rate versus twenty-seven point seven seven percent for G-Memory.

Jane: Those are solid gains. And it's not just about one model. They tested with Qwen2 point 5-7B as well, and the improvements held up. The framework consistently beat all the baselines across all three datasets.

Tom: So the summary is: memory needs maintenance. It's not a "set it and forget it" kind of deal. The authors are showing that a little bit of extra computation — in the form of this graph controller — pays off big time in terms of task performance.

Jane: And that's the key insight. We're moving from passive memory to active memory management. Next, we're going to dig into the specific improvements this paper suggests and what they mean for the future of AI agents.

Improvements: Tom: Alright, we're back. So we've covered the basics of "EvoGraph-Mem." Now, let's talk about the improvements it brings to the table. Jane, what do you think is the biggest win here?

Jane: I think the biggest win is the explicit modeling of negative evidence. Most memory systems only track what worked. They never track what failed. And that's a huge blind spot. By tracking both, EvoGraph-Mem can avoid the "memory pollution" problem, where a bad insight keeps getting retrieved and keeps causing failures.

Tom: And that's a real problem. The paper calls it "over-generalization." An insight might be true for one narrow case, but the agent applies it to everything. It's like learning that a specific mushroom is edible, and then assuming all mushrooms are edible. That's a recipe for disaster.

Jane: Exactly. So the graph controller's ability to ARCHIVE and REVISE is a game-changer. It's not just about deleting bad memories; it's about refining them. The REVISE operation is particularly clever because it keeps the old, flawed insight around for traceability, but it creates a new, corrected version that's actually useful.

Tom: And that leads to the "editable" part of the title. The graph is not a static structure. It's constantly being updated based on real-world feedback. The paper shows a case study where an insight about verifying claims evolves over time. First, it says "consult multiple sources." Then, after a failure, it gets revised to "consult multiple sources and consider the context." That's a more nuanced, more useful insight.

Meng: Hey, Tom, Jane — can I jump in here? I'm looking at the token consumption numbers in Table two and I have to ask about the cost. The paper shows that EvoGraph-Mem uses more tokens than any other method. Is that a fair trade-off?

Jane: Great question, Meng. Yeah, the token usage is higher — about 6 point 4M on GPT-4o-mini versus 6 point 2M for G-Memory. But the performance gains are significant. It's a classic cost-benefit analysis. You're spending a bit more compute to get much better reliability.

Meng: I get that, but in a real-world deployment, that extra cost adds up. If you're running an agent at scale, a three percent increase in tokens per task could be a big deal. I'd love to see some analysis on whether the performance boost justifies the cost in a production setting.

Tom: That's a fair pushback, Meng. And the authors acknowledge this in the limitations section. They say the overhead comes from the evidence-aware retrieval and the graph controller. But they argue that the improved reliability is worth it. And I tend to agree — a mistake in a long-horizon task can be way more expensive than a few extra tokens.

Lu: If I could add to that — the real value here isn't just the performance on these benchmarks. It's the architectural insight. This paper is showing us that memory should be treated as a first-class citizen in agent design, with its own lifecycle and maintenance routines. That's a philosophical shift that could have huge implications for how we build AI systems.

Jane: Absolutely, Lu. And that's what makes this paper so exciting. It's not just a tweak; it's a new way of thinking about memory. Alright, let's wrap this up in our final segment.

Conclusion: Tom: And we're back for the final stretch. We've been talking about "EvoGraph-Mem: Failure-Aware Editable Graph Memory for Long-Term Language Agents," and honestly, Jane, I think this is one of the more important papers we've covered in a while.

Jane: I completely agree, Tom. The core message is simple but profound: memory isn't just about storage; it's about maintenance. The authors have shown that by making memory editable — by tracking positive and negative evidence, and by actively archiving, revising, and adding insights — we can build agents that learn more reliably over time.

Tom: And the results speak for themselves. Across PDDL, HotpotQA, and FEVER, with two different backbone models, EvoGraph-Mem consistently outperformed every baseline. The ablation study was particularly telling — removing the archive operation caused performance to drop, which proves that append-only memory is fundamentally flawed.

Jane: Right. And while there are limitations — the dependency on task feedback, the extra token cost, the limited scope of the benchmarks — the direction is clear. We need to move from passive accumulation to active correction.

Lu: I'd just add that this opens up a whole new research area. How do we make these edits more efficient? How do we handle noisy feedback? How do we scale this to even more complex, open-ended environments? This paper lays the groundwork for all of that.

Meng: And from an engineering standpoint, I'm curious to see how this integrates with existing agent frameworks. The graph controller is a nice, modular component, so it should be portable. I'd love to see some open-source implementations.

Tom: Great points from everyone. So, as we say goodbye to "EvoGraph-Mem," let's remember the key takeaway: a good memory isn't just big; it's honest. It knows when it's wrong and it's willing to change. That's the future of long-term AI agents.

Jane: Well said, Tom. Thanks to everyone for tuning in. We'll be back soon with another paper, but for now, this is Tom and Jane, signing off.

Yuxiang Ren, Yuxi Qian

cs.AI, cs.MA

Submitted: 2026-08-03

Comments: 10 pages, 3 figures

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 63/100

The gist: positive evidence records queries for which the insight provides useful guidance, negative evidence captures cases where the insight is ineffective or harmful, and the activation state distinguishes

Key concepts

EvoGraph-Mem
This is a framework for long-term AI agent memory. It stores 'insights' (high-level lessons) as nodes in a graph. Crucially, it tracks both positive evidence (when an insight helped) and negative evidence (when it failed), allowing the memory to be actively managed and corrected.
Failure-Aware Memory
This concept addresses the flaw where traditional AI memory systems store information without checking its usefulness. EvoGraph-Mem ensures that insights are not just stored, but are constantly evaluated for whether they remain accurate or if they have become misleading over time.
Graph Controller
This is a secondary LLM component used after an agent performs a task. It decides what to do with retrieved memories using four operations: KEEP (if it worked), ARCHIVE (if it failed), REVISE (to correct outdated insights), or ADD (a new, reusable lesson).
Over-generalization
This is a problem where an insight true for a narrow case is applied broadly. For example, assuming all mushrooms are edible because one was. EvoGraph-Mem prevents this by tracking negative evidence and allowing the system to archive or revise flawed insights.

Terminology

Summary

Summary

The paper introduces EvoGraph-Mem, a failure-aware memory maintenance framework for long-term language agents, addressing the problem that memory is not only a problem of storage and retrieval, but also one of maintaining memory quality over time. The authors identify that as agents encounter diverse tasks, previously distilled insights may become outdated, overgeneralized, or harmful under new contexts, and that once such insights are repeatedly retrieved, they may introduce memory pollution and degrade downstream reasoning. This issue is particularly severe for high-level insights, which are intended to generalize across tasks but may cause greater harm when applied beyond their valid contexts.

The paper notes that existing graph-based memory systems, such as G-Memory, improve memory organization by structuring historical experience into insight, query, and interaction graphs, but existing memory systems remain limited in explicitly modeling whether a recalled insight was helpful, conflicting, or should be revised after task failure. The proposed framework is based on an editable insight graph, where "each insight node explicitly tracks positive evidence, negative evidence, and an activation state: positive evidence records queries for which the insight provides useful guidance, negative evidence captures cases where the insight is ineffective or harmful, and the activation state distinguishes active insights from archived ones to prevent invalid memories from being repeatedly retrieved."

The methodology builds on the graph-based historical memory of G-Memory, defining a query graph G query = (Q, E q) where each node q i (Q i, i, G inter(Q i)) consists of the original query Q i, its task status i in Failed, Resolved, and the corresponding interaction graph G inter(Q i). Retrieval of analogous queries is performed via cosine similarity, with an extension technique that adds neighboring nodes to form an expanded query subgraph S. The insight graph is defined as G insight = (I, E i) = kappa k, k k=1 I, E i, where " kappa k denotes the insight content, k+ denotes the set of queries for which the insight provides positive support, k- denotes the set of queries for which the insight is ineffective or harmful, and z k in 0, 1 denotes the activation state of the node."

The paper introduces utility-aware retrieval, where candidate insights are ranked by jointly considering positive support and conflicting evidence. The scoring function is r t,k = s t,k - lambda c t,k, where s t,k = k+ S measures relevant positive evidence and c t,k = k- S measures conflicting historical evidence, with lambda at least 0 controlling the strength of conflict penalization. The top-B insights are selected as I t ret = TopB iota k in I cand t r t,k.

The core contribution is the graph controller, instantiated as a prompt-constrained LLM, which evaluates whether each insight retrieved was helpful, harmful, or insufficient for the current query after task completion. The controller outputs operations restricted to KEEP, ARCHIVE, and REVISE for existing insights, with a separate binary ADD decision for new insight creation. The four operations are detailed: Archive deactivates a node and records the current query as negative evidence: (kappa k, k+, k-, z k) from (kappa k, k+, k- q, 0). Revise archives the old node and creates a revised node: (kappa k, k+, k-, z k) from (kappa k, k+, k- q, 0) and iota k' = (kappa k', k+ q,, 1). Add creates a new insight node iota new = (, q,, 1) when the task reveals a reusable pattern not covered by existing insights. Keep preserves the insight and strengthens positive evidence: (kappa k, k+, k-, z k) from (kappa k, k+ q, k-, 1). Additionally, the controller updates graph connectivity by adding edges E i from E i (iota a, iota b, q) iota a in I t ret, iota b in I new, = Resolved.

Experiments are conducted on PDDL, HotpotQA, and FEVER datasets, using exact match accuracy for FEVER and HotpotQA and progress rate for PDDL. The framework is compared against MemoryBank, Voyager, Generative Agents, and G-Memory, using GPT-4o-mini and Qwen2.5-7B as backbone models. The main results show that our failure-aware memory maintenance framework resolves these issues by introducing a dynamic Graph Controller and an extended Insight Node structure, yielding a 10.44% and 11.38% progress rate improvement on the multi-turn PDDL dataset, alongside a 21.75% and 5.03% exact match accuracy enhancement on the complex HotpotQA dataset across the two respective models. The paper also analyzes token consumption, noting that our method incurs the highest overall token usage, with a relative increase of 73.0% on GPT-4o-mini and 72.7% on Qwen2.5-7B compared with the no-memory setting, but this overhead is moderate compared to G-Memory, and these results suggest that our framework trades a limited amount of additional computation for more reliable memory utilization.

The ablation study compares three variants: add+keep, add+keep+archive, and the full controller. Results show that the complete controller generally achieves the strongest performance across both backbone models, with the full variant obtaining 44%, 31%, and 68% on HotpotQA, PDDL, and FEVER on GPT-4o-mini, outperforming add+keep by 4, 5, and 5 points respectively. The comparison between add+keep and add+keep+archive demonstrates the importance of memory deactivation, as adding the archive operation improves performance in most settings, suggesting that long-term memory should not be treated as a purely append-only repository: obsolete or misleading insights can introduce noise into retrieval and harm downstream decision making.

A case study on FEVER tasks illustrates the dynamic evolution of insights, showing that upon receiving the initial task 'Mohra is a truck', the system retrieves the insight 'Verify claims by consulting multiple authoritative sources...' from memory, and during the execution of the second task, the recalled insight transitions to 'Verify claims by cross-referencing with multiple authoritative sources and considering the context...'. This demonstrates that the insights undergo dynamic self-evolution and refinement throughout the sequence of tasks, becoming increasingly fine-grained and better adapted to novel requirements.

The paper concludes that our work shifts long-term agent memory from passive accumulation toward corrective maintenance. The contributions are summarized as: identifying insight-level memory maintenance as a challenge, proposing an editable insight graph with positive evidence, negative evidence, and activation states, introducing a graph controller for corrective memory updates through keeping, archiving, revising, and adding insights, and demonstrating consistent improvements over representative memory-based agent baselines with ablations validating the importance of graph-level editing. The limitations acknowledged include dependence on post-task feedback quality, the simplicity of the evidence sets, the limited scope of experimental scenarios, and additional computational and storage overhead.

Improvements for AI systems

Based on the paper, here are the specific improvements I can implement and what the improved AI system can do:

Implementation: Replace simple memory entries with structured nodes containing:

  • Positive evidence set (queries where the memory was helpful)

  • Negative evidence set (queries where the memory was harmful or ineffective)

  • Activation state (active/archived)

What the improved system can do: Automatically track which memories are reliable vs. problematic. When a memory fails on a task, it gets flagged as negative evidence rather than remaining valid forever.

Implementation: Score candidate memories using:

  • Score = PositiveEvidenceCount - λ × NegativeEvidenceCount

  • Only retrieve memories with active state and at least one positive match

  • Apply conflict penalty (λ) to suppress polluted memories

Implementation: After each task, run a prompt-constrained LLM controller that outputs one of four operations:

  • KEEP: Strengthen positive evidence

  • ARCHIVE: Deactivate node, add current query to negative evidence

  • REVISE: Archive old node, create corrected node with narrowed scope

  • ADD: Create new node only for genuinely novel, reusable insights

Implementation: When a revised or new insight is created, connect it to the insights that contributed to the current task (if the task was resolved).

  1. Self-Correcting Memory: If an insight works for 10 queries but fails on the 11th, the system archives it and creates a revised version that accounts for the failure context—rather than continuing to retrieve the flawed version.

  2. Conflict-Aware Ranking: When multiple memories match a query, the system prioritizes those with strong positive track records and penalizes those with negative evidence, even if they're semantically similar.

  3. Prevention of Memory Pollution: Archived insights are excluded from retrieval entirely, preventing outdated or harmful knowledge from degrading future reasoning.

  4. Efficient Memory Growth: New insights are only added when they represent genuinely reusable patterns not covered by existing memories, avoiding redundant or task-specific clutter.

  5. Traceable Evolution: Every revision or archival is recorded, so you can audit why a memory was changed and what evidence triggered the change.

The controller prompt includes:

  • Current query

  • Full agent trajectory

  • Final answer

  • Task feedback (success/failure)

  • Retrieved insights in JSON format

It's constrained to output valid JSON with:


"insight edits": [

"insight id": "...", "operation": "KEEPARCHIVEREVISE", "revised insight text": null

],

"add new insight": "decision": false, "new insight text": null

This ensures stable, parseable updates to the memory graph.

Sources

Related papers