EMG: Transforming Agent Failure into One-Shot Success via Graph Matching

Executive Summary

TL;DR: The "Trial-and-Error" era of LLM agents is being challenged by a more deterministic approach. Experience Memory Graph (EMG) replaces brittle, iterative self-reflection loops with a graph-theoretic framework that computes the exact "edit path" needed to turn a failure into a success. By shifting memory construction offline, EMG enables agents to correct errors in a single, loop-free execution, significantly reducing API costs while boosting success rates on complex benchmarks like ScienceWorld.

Background: Current agents are often "looped" until they succeed—a process that is slow, expensive, and often fails for smaller models. EMG moves from heuristic guessing to algorithmic exactness in the agentic memory space.

Problem: The Fragility of Reflection

Most current agents (e.g., Reflexion) follow a "Reflect-Replay" loop. When an agent fails, it is asked to "think" about why it failed and try again. This has three critical flaws:

1. Reasoning Bottleneck: Smaller LLMs (e.g., 4B/7B) aren't good at identifying their own root errors.
2. Inference Tax: Each "try again" costs time and money (API calls).
3. Cross-Task Amnesia: Reflections are usually discarded or task-specific, offering little help when a similar but new task appears.

Methodology: The Action Decision Graph (ADG)

The core innovation of EMG is treating an agent's life as a Graph. Instead of a simple sequence of text, EMG builds an Action Decision Graph (ADG) where:

• Nodes: Represent specific actions (e.g., "take apple").
• Edges: Represent the observations/states that triggered that action.

One-Shot Correction via Graph Matching

To learn from a mistake, EMG compares a "Failed Graph" with an "Expert Graph" using the Fused Gromov-Wasserstein (FGW) distance.

By matching these two graphs, the system extracts a Graph Edit Path:

• Action Deletion: "When you see X, stop doing Y."
• Action Insertion: "When you see X, you missed step Z."
• Action Relabeling: "Instead of action A, do action B."

These structural edits are then "distilled" into natural language insights and stored in a global memory graph.

Experiments: Superiority in Long-Horizon Tasks

The authors tested EMG on ALFWorld (household tasks) and ScienceWorld (complex science experiments).

Key Findings:

• Efficiency: EMG achieves higher Success Rates in one shot than baselines do in five attempts.
• Model Agnostic: Smaller models (Qwen3-4B) equipped with EMG insights outperformed larger models (DeepSeek-V4) using standard reflection.
• Cross-Task Transfer: By connecting similar tasks via edges in the memory graph, the agent can apply "Lessons Learned" from a "boil water" task to a "melt chocolate" task.

The figure above illustrates that EMG's one-shot success rate consistently exceeds the terminal success rate of iterative methods.

Critical Insight & Conclusion

The true value of EMG lies in Amortized Intelligence. By spending computational effort offline to match graphs and build a robust memory structure, the "online" execution becomes lean and efficient.

Limitations: Currently, EMG relies on having "Expert Trajectories" during the training phase. Future work will likely focus on how to build these graphs in a completely unsupervised manner, perhaps through multi-agent reinforcement learning or self-curated success.

In the landscape of AI Agents, EMG suggests that the path to reliability isn't just "more tokens" or "more reflection," but better structural representations of experience.