In complex long-horizon tasks, Large Language Model (LLM) agents have demonstrated remarkable autonomous decision-making capabilities by generating sequential trajectories of states, actions, and observations. However, these agents often face compounding errors and struggle to recover from failures. Existing self-correction mechanisms rely on prompt-based reflection, which is inherently fragile and incurs high time and API costs due to iterative trial-and-error loops, producing task-specific memory that is challenging to generalize to new scenarios.
To tackle this, we propose the Experience Memory Graph (EMG), which reformulates agent failure recovery as a graph matching problem.
During training, we convert both failed exploration trajectories and successful expert trajectories into directed action decision graphs. By matching these graphs, we extract common subgraphs (successful workflows) and graph edit paths that explicitly indicate how to correct failures (e.g., which actions to add, delete, or relabel under a given observation), storing them in a memory graph with intra-task nodes and cross-task edges.
At test time, EMG retrieves relevant insights and guides the agent in a single, loop-free execution. Experiments on ALFWorld and ScienceWorld show that EMG consistently outperforms state-of-the-art reflection baselines in success rate and average reward, while requiring no test-time trial-and-error.
Blogger's Review: The introduction of the Experience Memory Graph offers an innovative approach to error recovery for agents, effectively leveraging successful experiences through graph matching, thus avoiding the inefficiencies of repeated trial-and-error. This method not only enhances agent performance but also provides a new direction for future agent designs, showcasing broad application potential.