EMG Turns Agent Self-Correction Into a Graph Matching Problem

Introduction

LLM agents can plan and act across multi-step environments, but long-horizon tasks remain fragile. A small mistake early in a trajectory may cascade into a sequence of wrong decisions, leaving the agent unable to recover. Many existing systems address this with prompt-based reflection: the model analyzes its failure, tries again, and repeats the process until it improves.

The arXiv paper “Experience Memory Graph: One-Shot Error Correction for Agents” argues that this loop is costly and brittle. Its proposed framework, Experience Memory Graph, or EMG, reframes failure recovery as a graph matching problem rather than a purely language-based introspection process.

Key ideas

• Trajectory-to-graph conversion: During training, EMG converts both failed exploration traces and successful expert traces into directed action-decision graphs. These graphs represent how observations, states, and actions connect over time.
• Learning from the difference between failure and success: By matching failed and successful graphs, EMG identifies common subgraphs that correspond to successful workflows. It also extracts graph edit paths that describe concrete repairs, such as adding an action, deleting an action, or relabeling an action under a specific observation.
• A memory graph beyond one task: The extracted experience is stored in a memory graph containing intra-task nodes and cross-task edges, allowing the agent to retrieve potentially reusable correction knowledge in new scenarios.
• One-shot test-time guidance: Instead of running multiple reflection-and-retry cycles, the agent retrieves relevant experience from EMG and executes once, without test-time trial and error.

Why it matters

The main contribution of EMG is not simply adding more memory to an agent. It changes the form of memory: from free-form textual notes to structured representations of what went wrong and how the action sequence should be edited. That makes correction more explicit and may reduce the cost associated with repeated API calls and iterative replanning.

According to the paper, experiments on ALFWorld and ScienceWorld show consistent improvements over state-of-the-art reflection baselines in success rate and average reward, while avoiding test-time retry loops. Still, the results are reported in benchmark environments, so broader questions remain: how expensive graph construction is, how well the memories generalize to messier real-world tasks, and how robust retrieval is when observations are ambiguous.

Even with those open questions, EMG highlights an important direction for agent research. Future agent memory may look less like a transcript of past attempts and more like a structured map of workflows, failures, and repair operations.

Source: arXiv