arXiv:2607.13884v1 [cs.AI] 15 Jul 2026
Experience Memory Graph: One-Shot Error Correction for Agents Wenjun Wang∗
Yuchen Fang∗
Fengrui Liu
University of Electronic Science and Technology of China Chengdu, China [email protected]
University of Electronic Science and Technology of China Chengdu, China [email protected]
University of Electronic Science and Technology of China Chengdu, China [email protected]
Zibo Liang
Kai Zheng†
University of Electronic Science and Technology of China Chengdu, China [email protected]
University of Electronic Science and Technology of China Chengdu, China [email protected]
Abstract
Keywords
Large Language Model (LLM) agents have shown remarkable capabilities in autonomous decision-making by generating sequential trajectories of states, actions, and observations. However, in complex, long-horizon tasks, these agents frequently suffer from compounding errors and struggle to recover from failures. Existing self-correction mechanisms rely on prompt-based reflection, which is inherently brittle, incurs heavy time and API costs due to iterative trial-and-error loops, and produces task-specific memory that may be hard to generalize to new scenarios. To address this, we propose Experience Memory Graph (EMG), a framework that reformulates agent failure recovery as a graph matching problem. At training time, 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), and store 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.
Large Language Models, Agent, Agent memory
CCS Concepts • Computing methodologies → Artificial intelligence. ∗ Equal Contribution. † Corresponding author: Kai Zheng. Kai Zheng is with Yangtze Delta Region Institute (Quzhou), School of Computer Science and Engineering, UESTC. He is also with Shenzhen Institute for Advanced Study, UESTC.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. KDD ’27, San Jose, United States. © 2027 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN ...... https://doi.org/10.1145/......
ACM Reference Format: Wenjun Wang, Yuchen Fang, Fengrui Liu, Zibo Liang, and Kai Zheng. 2027. Experience Memory Graph: One-Shot Error Correction for Agents. In 33rd SIGKDD Conference on Knowledge Discovery and Data Mining, August 1–5, 2027, 2027, San Jose, United States.. ACM, New York, NY, USA, 11 pages. https://doi.org/10.1145/......
1
Introduction
Large Language Models (LLMs) have evolved from passive text assistants into autonomous agents with planning, memory, and tool-use capabilities, enabling closed-loop interaction with environments [3, 28]. This architecture has demonstrated strong zero-shot and few-shot performance across complex domains such as web navigation, multi-step mathematical reasoning, and automated software engineering [11, 16, 23]. As agents act iteratively, they generate long-horizon trajectories—sequential structures of states, actions, and observations. Rather than being mere logs, these trajectories contain rich, reusable experience. By systematically extracting successful workflows and failure patterns from past trajectories, agents can build experience memory that helps avoid repeated mistakes and improve task success rates on subsequent attempts [7, 14]. To construct experience memory from interaction trajectories, early approaches relied exclusively on extracting workflows from successful executions [22, 38]. Subsequent methods have increasingly leveraged failed trajectories to enhance learning. While some studies focus on isolating decisive erroneous actions or performing failure credit assignment [36, 39, 40], others extend this paradigm by actively rectifying failed trajectories to achieve task success [4–6, 8–10, 15, 17, 27, 29, 31, 32, 34]. Typically, these approaches prompt LLMs to reflect on the root causes of failure—specifically, identifying the erroneous action and hypothesizing a corrective counterpart. The model then replays the task grounded in this refined memory, thereby constituting an iterative reflect-and-replay mechanism, as illustrated in Fig. 1(a). While previous methods successfully construct memory by rectifying failed trajectories and achieve impressive performance, they suffer from three primary limitations. Limitation 1: Dependence on LLM Capabilities. This promptbased reflection paradigm can be sensitive to prompt design, and
KDD ’27, August 1–5, 2027, San Jose, United States.
Figure 1: Difference of error correction based on (a) reflectreplay loop and (b) Experience Memory Graph. Existing methods rely on iterative test-time reflection — the agent replans and re-executes after each failure, causing high latency and cost. Our Experience Memory Graph extracts error correction paths offline by computing graph edit paths that transform failed trajectories into successful ones from paired training trajectories of the same task, distills them into insights, and stores them in a memory graph. At test time, retrieval enables one-shot exectution without loops.
its effectiveness is often constrained by the model’s inherent capabilities.For instance, smaller LLMs usually struggle to break out of repetitive error cycles, which can hinder their ability to perform effective self-reflection and correction. Moreover, in long-horizon trajectories, accurately identifying the root cause of a failure — which may be deeply buried in a long sequence of states and actions — can be challenging for such models. Limitation 2: Inference Cost. After each failure, the model needs to reflect, adjust, and re-execute the trajectory. This iterative looping process multiplies both latency and API costs. In commercial or real-time scenarios, such back-and-forth loops may become less efficient, potentially limiting their practicality for time-sensitive applications. Limitation 3: Limited Cross-Task Generalization. Most existing approaches perform reflection and re-execution directly on the test set for individual failed tasks, rather than extracting reusable memory from training failures. Consequently, the synthesized memory is task-specific, resulting in limited transferability to unseen scenarios. To address these issues, we propose Experience Memory Graph (EMG), a novel framework that shifts the paradigm from online LLM reflection to offline, deterministic graph computation. EMG structures memory as a comprehensive network where nodes store localized task knowledge (successful workflows or corrective paths for individual tasks) and edges capture generalized action patterns across similar tasks. To construct each node in the experience memory graph, we convert both the failed exploration trajectory and the successful expert trajectory of the same training task into action decision graphs. By performing graph matching between them, we extract the common subgraph (representing correctly executed workflows) and compute the shortest graph edit path. This path
Wenjun Wang et al.
serves as a deterministic, one-shot error correction plan—dictating exactly which actions to retain, delete, or replace under specific observations. By relying on algorithmic exactness rather than promptbased guessing, this mechanism robustly localizes root errors and fully resolves the over-reliance on LLM capabilities (Limitation 1). To construct each edge in the experience memory graph, we further connect semantically similar task queries (via top-𝑘 nearest neighbors) and perform graph matching between their respective expert trajectories. This process extracts cross-task insights stored on the edges, capturing reusable, high-level action patterns that transfer across different scenarios. Crucially, the entire memory construction is performed offline on the training set. Once built, this memory graph can be applied to any test set, directly addressing the limited generalizability of task-specific memory (Limitation 3). During test-time inference, the agent simply retrieves the pre-computed correction paths and cross-task insights without any iterative trial-and-error, thereby circumventing the prohibitive inference overhead and API costs (Limitation 2). This makes EMG a highly efficient and accurate solution for real-time applications. In summary, our contributions are three-fold: • We propose Experience Memory Graph (EMG), a novel framework that structures experience for LLM agents as a relational graph. By organizing memory into nodes for localized task knowledge and edges for generalized action patterns, EMG enables robust cross-task generalization that surpasses traditional task-specific memory banks. • We introduce a deterministic memory acquisition mechanism based on graph matching to populate EMG. By extracting the common subgraph to preserve successful workflows and computing the shortest graph edit path for one-shot error correction, our approach replaces brittle, iterative LLM reflection loops with algorithmic exactness, significantly reducing API costs and latency. • Extensive experiments on challenging benchmarks demonstrate that EMG significantly outperforms state-of-the-art self-reflection baselines. Notably, EMG exhibits superior performance and computational efficiency in long-horizon tasks requiring complex reasoning.
2 Related Work 2.1 Experience Memory Experience memory aims at extracting the reusable workflow and insight from history trajectories. Early studies on experience memory construction mainly extract reusable workflows from successful trajectories [22, 38], assuming that successful executions directly encode high-quality procedural knowledge. However, such approaches ignore informative signals from failed trajectories. To leverage failures, some works focus on failure diagnosis. AgenTracer [36] leverages counterfactual replay and fault injection to perturb trajectories and trace back the root cause of failures, enabling fine-grained attribution to specific actions or modules. Trajectory graph copilot [39] models trajectories as a graph structure and applies graph neural networks to capture temporal dependencies and detect error-prone action patterns, allowing pre-action diagnosis. AgentDebug [40] further conducts a large-scale empirical
Experience Memory Graph: One-Shot Error Correction for Agents
study of LLM agent failures, categorizing error types and revealing common failure modes. Another line of work focuses on correcting failed trajectories via reflection [12, 21]. R2D2 [8] performs step-level reflection to locate the first erroneous action, truncates the trajectory from that point, and stores corrected sub-trajectories along with reflections for future reuse. ReasoningBank [15] goes beyond trajectory replay by abstracting experiences into reusable high-level reasoning strategies, improving generalization across tasks. Building on this paradigm, principles [9] learns synthetic strategy memory for proactive decision-making, Memp [4] introduces procedural memory that captures action-level execution knowledge, and some works [6, 26, 27] organize experiences into structured or graph-based skill representations to enhance compositionality. Moreover, CDMem [5] additionally improves context-aware memory retrieval, and [10] explicitly trains agents to learn sequential decision policies from failed attempts. These methods typically follow a reflect–replay paradigm, where the agent first analyzes failure causes (e.g., identifying erroneous actions and suggesting corrections), then re-executes the task using refined memory. Despite their effectiveness, they often rely heavily on the quality of reflection and may suffer from inefficient iterative correction or error propagation.
2.2
Graph for Agent Memory
Recent studies have explored graph memory mechanisms to enhance long-term reasoning and experience reuse in LLM agents [13]. AriGraph [1] constructs a unified graph that integrates semantic and episodic memories for planning and reasoning in interactive environments. A-Mem [28] further enables autonomous memory evolution by dynamically linking and restructuring memories into an interconnected knowledge network. G-Memory [35] extends graph-based memory to multi-agent settings through hierarchical interaction and insight graphs, facilitating cross-trial knowledge transfer. Recent efforts such as SGMem [24], GAM [25], and H-Mem [33] further investigate sentence graphs, hierarchical graph memories, and hybrid graph-based memory evolution mechanisms to enhance long-horizon retrieval and adaptive reasoning capabilities. Despite encouraging progress, existing methods mainly focus on memory storage and retrieval, while the extraction of reusable high-level insights and the modeling of transferable experience relationships remain underexplored. Our EMG fills this gap by using graph matching to derive common subgraphs and edit paths, transforming raw trajectories into transferable correction workflows.
3
Preliminary
We consider LLM-based agents that interact with environments to solve long-horizon tasks. Following prior work, we formulate such agentic tasks as a partially observable Markov decision process (POMDP) without explicitly modeling the latent state. The process is defined by the tuple (Q, A, O,𝑇 , 𝑅), where Q is the query (instruction) space, A the action space, O the observation space, 𝑇 : A × O → A a transition function that determines the next action given the current action and observation, and 𝑅 : A × O → [0, 1] the reward function. Since our focus is on
KDD ’27, August 1–5, 2027, San Jose, United States.
the task planning capability of LLM agents, Q, A, and O are subsets of the natural language space. Given a task query 𝑞 ∈ Q, the LLM agent 𝜋𝜃 interacts with the environment as follows. At each time step 𝑡, the agent samples an action 𝑎𝑡 ∼ 𝜋𝜃 (· | 𝑞, 𝜏𝑡 −1 ) based on the query and the history of previous interactions. It then receives environmental feedback as an observation 𝑜𝑡 ∈ O. The historical interaction trajectory up to step 𝑡 −1 is denoted by 𝜏𝑡 −1 = (𝑜 0, 𝑎 1, 𝑜 1, 𝑎 2, 𝑜 2, . . . , 𝑎𝑡 −1, 𝑜𝑡 −1 ), where 𝑜 0 is the initial observation of the environment before any action is taken. The interaction loop continues until the agent either completes the task or reaches the maximum allowed number of steps. The complete trajectory is written as 𝜏 = (𝑞, 𝑜 0, 𝑎 1, 𝑜 1, 𝑎 2, 𝑜 2, . . . , 𝑎𝑚 , 𝑜𝑚 ), where 𝑜 0 is the initial observation of the environment, and 𝑚 denotes the trajectory length. Finally, a reward 𝑟 (𝑞, 𝜏) ∈ [0, 1] is assigned to indicate whether the task is successfully completed or has failed.
4
Method
In this section, we present Experience Memory Graph (EMG), a framework that constructs structured experience memory from training tasks and applies it to new tasks, which is shown in fig. 2. The overall pipeline consists of three stages: (1) preparing training trajectories and converting them into action decision graphs; (2) constructing a memory graph where nodes store intra-task insights and edges store cross-task insights; and (3) retrieving relevant memory at test time to guide the agent without additional loops. We detail each stage below.
4.1
Preparation
Before constructing the experience memory graph, we first collect trajectories on the training tasks and convert them into action decision graphs. 4.1.1 Collecting Exploration Trajectories. For each training task query 𝑞 in the training set Qtrain , we let an LLM agent interact with the environment to produce a single exploration trajectory 𝑒𝑚 (which may either succeed or fail). For the same task 𝑡𝑖 , we assume access to a successful expert trajectory 𝜏𝑖∗ , provided by datasets such as ETO [19]. Thus, for each training task, we obtain a pair (𝜏𝑖 , 𝜏𝑖∗ ). Failed exploration trajectories are particularly valuable, as they contain mistakes that can be corrected; successful ones can be used as positive examples directly. We collect such pairs over all training tasks. 4.1.2 Transforming Trajectories into Action Decision Graphs. To explicitly model the decision process — which action should be taken under a given observation — we convert each raw trajectory into a directed action decision graph. A successful trajectory and a failed one often differ precisely in this decision mapping. By constructing a graph where nodes are actions and edges carry the preceding observation, we make explicit the rule: for a given state, which action is chosen. This decision-centric representation enables the graph edit path to learn meaningful correction insights — e.g., under a specific observation, which wrong action should be replaced by which correct action. Compared to raw sequential sequences, where the same action may appear in different contexts without a clear
KDD ’27, August 1–5, 2027, San Jose, United States.
Wenjun Wang et al.
Figure 2: Overall architecture of EMG (Experience Memory Graph). In the offline construction phase, we collect exploration trajectories on training tasks and convert them into action decision graphs. Graph matching on failed–successful pairs extracts edit paths for error correction, while matching on successful–successful pairs from similar tasks yields common subgraphs for transferable workflows. These structural insights are distilled into natural-language guidance and stored in a memory graph with intra-task nodes and cross-task edges. At test time, the agent retrieves relevant node and edge insights, enabling correct one-shot execution without trial-and-error loops. link to the triggering observation, our graph formulation yields far more actionable and transferable correction knowledge. Graph representation. We denote the action decision graph as 𝐺 = (𝑉 , 𝐸, 𝑞, 𝑟 ), where 𝑞 is the task query and 𝑟 is the final reward. Nodes represent actions, edges represent the observations preceding those actions. To obtain compact yet discriminative representations for labeling, we normalize each action into a tuple 𝑘 = (type, object, receptacle) (e.g., (take, apple, table)), capturing the action type and the objects it operates on; the raw action text 𝑎 raw (e.g., "take apple from table") is also kept. Each node is repre𝑣 sented as 𝑣𝑖 = (𝑘𝑖 , 𝑎𝑖raw, ℓ𝑛 (𝑣)) with node label ℓ𝑛 (𝑣𝑖 ) ∈ N. A virtual INIT node 𝑣 init (ℓ𝑛 (𝑣 init ) = 0) provides an incoming edge for the first action, carrying the initial observation 𝑜 0 . Each directed edge is denoted as 𝑒𝑖 = ((𝑣𝑖 , 𝑣𝑖+1 ), 𝑠𝑖 , ℓ𝑒 (𝑒𝑖 )) ∈ 𝐸. (𝑣𝑖 , 𝑣𝑖+1 ) represents the connection from action node 𝑣𝑖 to 𝑣𝑖+1 . So 𝑒𝑖 is both the observations resulting from the action 𝑣𝑖 and the preceding observation of the next action 𝑣𝑖+1 . 𝑒𝑖 also carries a normalized observation text 𝑠𝑖 derived from the raw observation 𝑜𝑖 (e.g., “kitchen: apple, potato”) and its edge label ℓ𝑒 (𝑒𝑖 ) ∈ N. Construction design. Two design choices ensure the action decision graph captures decision-level information. 1. node reuse: if the same normalized action tuple appears multiple times in the trajectory, we do not create a new node; instead, we reuse the existing node. This gives the node multiple incoming edges, each associated with a different preceding observation, thus capturing the decision
pattern that the same action may be taken under various observed states. 2. parallelizing consecutive invalid actions: when an action leads to an uninformative observation (e.g., “nothing happens”), the environment state does not change. We keep the current valid state unchanged and connect all such invalid actions from the same previous valid node, treating them as parallel attempts from the same decision point rather than a spurious chain. To implement these ideas, we scan the trajectory once, maintaining the current valid state 𝑠 (initialized as normalized 𝑜 0 ) and the node 𝑙𝑎𝑠𝑡 (initially 𝑣 init ) that produced it. A dictionary Φ maps each normalized action tuple to its node, enabling node reuse. The detailed Algorithm 1 and a concrete example is available in Appendix A. After building the structure, we assign labels: each distinct action tuple 𝑘 receives a unique positive integer as node label ℓ𝑛 (𝑣) (0 for 𝑣 init ), and each distinct normalized observation text 𝑠 receives a unique positive integer as edge label ℓ𝑒 (𝑒). Thus, identical contents yield identical labels, allowing graph matching to compare semantics by simple label equality. The resulting action decision graph abstracts raw action and observation texts into discrete labels (node labels for action tuples, edge labels for observation texts), enabling efficient structure comparison via label equality in the subsequent graph matching stage. At the same time, each node and edge preserves the original raw texts, which are later used to convert extracted common subgraphs and graph edit paths into natural-language insights.
Experience Memory Graph: One-Shot Error Correction for Agents
4.2
Construction of Experience Memory Graph
To move beyond test-time self-reflection, we build an offline experience memory graph that stores structured, reusable experience. This memory graph provides two key benefits: (1) it captures precise error corrections and successful workflows for individual tasks, and (2) it generalizes across similar tasks by extracting shared decision patterns. To construct such a memory graph, we leverage graph matching on the action decision graphs obtained from Section 4.1. By matching failed exploration graphs with their corresponding expert graphs, we extract intra-task common subgraphs and graph edit paths; by matching expert graphs of semantically similar tasks, we obtain cross-task insights. These structured pieces of knowledge are organized into the experience memory graph G𝑚 = (V, E), where each node 𝜈 ∈ V stores intra-task insights and each edge 𝜖 ∈ E stores cross-task reusable insights. We first define the experience memory graph formally. Let V = {𝜈 1, . . . , 𝜈 𝑁 } where each node 𝜈𝑖 is a tuple: 𝜈𝑖 = 𝑞𝑖 , 𝑒𝑚𝑏𝑒𝑑 𝑖 , 𝐼𝑖intra, 𝐺𝑖 , 𝐺𝑖∗, 𝑟𝑖 , (1) where 𝑞𝑖 is the task query, 𝑒𝑚𝑏𝑒𝑑 𝑖 the query embedding, 𝐼𝑖intra is the intra-task insight, and 𝐺𝑖 , 𝐺𝑖∗ are the action decision graphs of the exploration trajectory and the expert trajectory, respectively (built via Algorithm 1). 𝑟𝑖 ∈ {0, 1} is the reward (success/failure) of exploration trajectory 𝐺𝑖 , and the reward of expert trajectory is always 1 and we omit it here. Each edge 𝜖𝑖 𝑗 ∈ E connects 𝜈𝑖 and 𝜈 𝑗 and is defined as: 𝜖𝑖 𝑗 = 𝑠𝑖 𝑗 , 𝐼𝑖cross , (2) 𝑗 where 𝑠𝑖 𝑗 = cos(𝑒𝑚𝑏𝑒𝑑 𝑖 , 𝑒𝑚𝑏𝑒𝑑 𝑗 ) is the cosine similarity between query embeddings, and 𝐼𝑖cross is the cross-task insight text. 𝑗 4.2.1 Constructing Node Insights. Recall that 𝐺𝑖 and 𝐺𝑖∗ are the action decision graphs built from the raw exploration and expert trajectories using the method in Section 4.1. This graph representation allows us to compare them structurally via graph matching. Given a pair of exploration graph 𝐺𝑖 and expert graph 𝐺𝑖∗ , we can extract two kinds of structured knowledge: the common subgraph 𝐺𝑖𝑐 (the correct actions in the failed trajectory that should be maintained, revealing the successful workflow) and the graph edit path 𝐺𝑖𝑒 (a sequence of edit operations that transforms failed exploration 𝐺𝑖 into successful expert 𝐺𝑖∗ ), from 𝐺𝑖𝑒 we directly obtain: (a) which actions to add or avoid under specific observations (from node deletions/insertions), and (b) which action to replace with another under a given observation (from relabeled actions). To compute 𝐺𝑖𝑐 and 𝐺𝑖𝑒 , we first find a node matching between the two graphs via graph matching, then we compare the two graphs: the parts that are identical in both structure and labels form the common subgraph; the differences (mismatched nodes and edges) directly yield the graph edit path. Thus, instead of test-time trial-and-error, we directly obtain correction instructions and successful workflows. Concretely, we first obtain the node matching between 𝐺𝑖 and 𝐺𝑖∗ via graph matching. Since supervised matching heavily relies on ground-truth node correspondences, we adopt an unsupervised approach based on optimal transport (OT). Most OT-based methods adopt the Fused Gromov-Wasserstein (FGW) distance [2, 20], which jointly considers node labels and edge structures. For two graphs 𝐺
KDD ’27, August 1–5, 2027, San Jose, United States. ′
and 𝐺 ′ with soft assignment 𝜋 ∈ R |𝑉 | × |𝑉 | , our FGW objective is: ∑︁ ∑︁ 𝑔 𝑔′ FGW = min 𝐶 𝑖 𝑗 𝜋𝑖 𝑗 + |𝐴𝑖 𝑗 − 𝐴𝑘𝑙 | 2 𝜋𝑖𝑘 𝜋 𝑗𝑙 , (3) 𝜋
𝑖,𝑗
𝑖,𝑗,𝑘,𝑙
where 𝜋𝑖 𝑗 indicates the matching strength between node 𝑖 in 𝐺 and ′ node 𝑗 in 𝐺 ′ , 𝐶𝑖 𝑗 is the cost of relabeling node 𝑖 to 𝑗, and 𝐴𝑔 , 𝐴𝑔 are adjacency matrices. Unlike the standard FGW formulation which includes a factor 12 for undirected graphs where each edge is counted twice) [2, 20], our directed graphs require no such factor, and we drop it. We adopt the FGWAlign solver [20] to optimize this objective, which supports edge-labeled graphs. The time complexity of the solver is 𝑂 (|V | 3 · |L|), where |L| is the number of edge label types. Since our trajectory graphs typically contain at most a few dozen nodes, the solver is highly efficient. After obtaining the optimal soft plan 𝜋 ∗ , we discretize it into a ′ hard node matching matrix 𝑃 ∈ {0, 1} |𝑉 | × |𝑉 | via linear assignment: 𝑃 = arg max ⟨𝜋 ∗, 𝑃⟩, 𝑃 ∈P𝑛
(4)
where P𝑛 denotes the set of permutation (or partial permutation) matrices. Each entry 𝑃𝑖 𝑗 = 1 indicates that node 𝑖 in 𝐺 is matched to node 𝑗 in 𝐺 ′ . Given the node matching matrix 𝑃, we define a node matching 𝑀 : 𝑉 ↦→ 𝑉 ′ where 𝑀 (𝑢) = 𝑣 if 𝑃𝑢𝑣 = 1 (and 𝑢 is unmatched if no such 𝑣 exists), then we derive the graph edit path and the common subgraph by comparing the two graphs. Classical methods for extracting edit paths and common subgraphs are designed for undirected graphs with only node labels; they cannot handle edge labels and do not respect edge directions. Directly applying them to our directed edge-labeled action decision graphs would discard the semantic information carried by edge observations (the preconditions of actions). Therefore, we adapt these methods to our setting. Specifically, Algorithm 2 retains edges that exist in both graphs with identical labels under the matching (the correct workflow); Algorithm 3 collects unmatched or mismatched nodes and edges to form edit operations (deletions, insertions, relabelings), directly indicating the necessary corrections. The detailed algorithm is available in Appendix B. Finally, we generate the intra-task insight. If the exploration succeeded (𝑟𝑖 = 1), we retain the common subgraph 𝐺𝑖𝑐 (extracted via Algorithm 2) as the correct workflow. If it failed (𝑟𝑖 = 0), we use the graph edit path 𝐺𝑖𝑒 (via Algorithm 3) as the correction instructions. For environments with continuous reward (e.g., ScienceWorld), a partially successful trajectory (0 < 𝑟𝑖 < 1) contains both correct and incorrect actions; we therefore feed both 𝐺𝑖𝑐 (to preserve the correct actions) and 𝐺𝑖𝑒 (to correct the errors) to the LLM. In all cases, the LLM takes the task query 𝑞𝑖 as input, the original exploration graph 𝐺𝑖 , the expert graph 𝐺𝑖∗ , and the extracted structure(s) 𝑋𝑖 (where 𝑋𝑖 is 𝐺𝑖𝑐 (𝑟𝑖 = 1), or 𝐺𝑖𝑒 (𝑟𝑖 = 0), or both (0 < 𝑟𝑖 < 1)), and summarizes them into intra-task insight: (5) 𝐼𝑖intra = LLM intra-prompt(𝑞𝑖 , 𝐺𝑖 , 𝐺𝑖∗, 𝑋𝑖 ) . In summary, 𝐼𝑖intra supplies either the correct workflow or explicit corrections, enabling test-time guidance without trial-and-error. 4.2.2 Constructing Edge Insights. Using the action decision graph representation for all expert trajectories, we can compare the successful decision patterns of different tasks. We further aim to extract
KDD ’27, August 1–5, 2027, San Jose, United States.
Wenjun Wang et al.
generalizable knowledge that transfers across similar tasks (e.g., different environments with analogous goals). For two task nodes 𝜈𝑖 and 𝜈 𝑗 with similar queries in the memory graph, comparing their expert graphs 𝐺𝑖∗ and 𝐺 ∗𝑗 via graph matching reveals a common subgraph — actions that are correct under similar observations in different environments which should be learned and maintained. This provides cross-task insights that are robust to environmental variations. To realize this, after building all nodes we compute pairwise query embedding similarities 𝑠𝑖 𝑗 = cos(𝑒𝑚𝑏𝑒𝑑 𝑖 , 𝑒𝑚𝑏𝑒𝑑 𝑗 ), where 𝑒𝑚𝑏𝑒𝑑 𝑖 is the embedding of node 𝜈𝑖 ’s query. An edge 𝜖𝑖 𝑗 is added if 𝑠𝑖 𝑗 ≥ 𝜏, and we only connect each node to its top-𝑘 most similar neighbors. For each edge 𝜖𝑖 𝑗 connecting node task 𝜈𝑖 and 𝜈 𝑗 , we perform graph matching between the expert graphs 𝐺𝑖∗ and 𝐺 ∗𝑗 of 𝜈𝑖 and 𝜈 𝑗 , and use the same adapted FGW solver and Algorithm 2 to obtain the common subgraph 𝐺𝑖𝑐𝑗 . We then prompt an LLM to summarize 𝐺𝑖𝑐𝑗 into the cross-task insight: 𝐼𝑖cross = LLM cross_prompt(𝑞𝑖 , 𝑞 𝑗 , 𝐺𝑖∗, 𝐺 ∗𝑗 , 𝐺𝑖𝑐𝑗 ) . 𝑗
(6)
This insight is stored on the edge 𝜖𝑖 𝑗 , which can guide the agent when facing new tasks similar to either endpoint.
4.3
Retrieval of Experience Memory Graph
During test time, given a new task query 𝑞 test , we first embed it using the same embedding model to obtain 𝑒𝑚𝑏𝑒𝑑 test . The similarity to each memory node 𝜈𝑖 is computed as 𝑠𝑖 = cos(𝑒𝑚𝑏𝑒𝑑 test, 𝑒𝑚𝑏𝑒𝑑 𝑖 ). We retrieve the top-𝐾 nodes with the highest 𝑠𝑖 . For each such node 𝜈𝑖 , we also retrieve the most relevant cross-task insights: we look at all edges incident to 𝜈𝑖 , and for each neighbor 𝜈 𝑗 we compute its similarity to 𝑞 test as above. The edges with the top-𝑇 neighbor similarities are selected, and their stored cross-task insights are collected. Formally, the retrieval result for 𝑞 test is: R (𝑞 test ) =
Ø
𝐼𝑖intra, {𝐼𝑖cross | 𝜈 𝑗 ∈ TopT(𝜈𝑖 )} 𝑗
,
(7)
𝜈𝑖 ∈TopK
where TopT(𝜈𝑖 ) are the neighbors of 𝜈𝑖 with the highest query similarities. The retrieved insights, derived from structured graph comparisons, provide concrete decision rules, making them directly usable for the agent. For instance, when faced with a task such as “put some pencil on shelf,” the retrieved node insight may specify that once the agent is holding the pencil at the sidetable, the correct next action is to go directly to the shelf rather than placing it elsewhere, and that the action of taking the pencil must precede any movement toward the target. The retrieved edge insights further provide cross-task guidance, such as adapting the final navigation step when the target changes from shelf to desk, or expanding the search strategy when the object changes from pencil to pen. These insights are then passed to the agent’s prompt as guidance, eliminating any need for test-time reflection or trial-and-error loops. The complete Experience Memory Graph G𝑚 is built offline on the training set. Its construction cost is amortized over many test tasks, and the retrieval is fast (embedding similarity + neighbor lookup). This makes EMGboth efficient and scalable.
Table 1: Statistics of the datasets used for evaluation.
Dataset
#Train
#Test-Seen
#Test-Unseen
ALFWorld ScienceWorld
3321 1483
140 194
134 211
5 Experiments 5.1 Experimental Settings 5.1.1 Datasets. We conduct experiments across two mainstream datasets: ALFWorld and ScienceWorld. The detailed statistics are summarized in Table 1. ALFWorld provides embodied household tasks to assess the agent’s capacity for spatial memory and sequential execution in everyday scenarios. ScienceWorld simulates interactive science experiments and features the longest trajectories, serving as a rigorous benchmark for evaluating long-term memory retention, multi-step planning, and complex scientific reasoning. To measure both in-distribution learning and out-of-distribution generalization capabilities, we evaluate agent performance on both seen and unseen test splits for ALFWorld and ScienceWorld with the same split of ETO [19]. The reward of ALFWorld is either 0 or 1, and the reward of ScienceWorld is from 0 to 1. 5.1.2 Baselines. In this paper, we benchmark our EMG against a spectrum of representative frameworks, containing both methods with reflect-replay loop and memory construction. We first consider ReAct [30], a widely adopted prompting strategy that interleaves reasoning traces with task-specific actions, serving as our fundamental memory-less baseline. Reflexion [18] enables the agent to leverage short-term episodic memory of past mistakes to iteratively refine its behavior within a single environment. Extending beyond transient self-reflection, we evaluate ExpeL [37], which accumulates rules from historical trajectories, acting as an experiential learning baseline. Furthermore, we compare against recent CDMem [5], which constructs both short-term memory and long-term memory based on reflection, and MemP [4], which explicitly constructs procedural memory to reuse complex execution routines. Our EMG adopts ReAct as the base model and retrieves insights in the constructed memory graph when testing. Each baseline is equipped with few-shot examples. For baselines with reflect-replay loop (Reflexion, Expel and CDMem), we run for 5 iterations. 5.1.3 Evaluation Metrics and Settings. We employ two commonly used metrics: Success Rate (SR) and Average Reward (AR). While SR acts as the primary indicator of ultimate task completion, AR provides a granular assessment of partial progress and intermediate sub-goal achievement, reflecting the agent’s step-by-step reasoning and memory utilization throughout long-horizon interactions. We apply DeepSeek V3.2 (chat mode) to collect exploration trajectories, and construct the experience memory graph with DeepSeek V3.2 (chat mode) for Scienceworld, and Deepseek V4-flash (chat mode) for ALFWorld. For testing tasks, we use both the open-source small model Qwen3:4B-instruct-2507-q8 and the large model DeepSeekV4 flash (chat mode) to compare the performance of baselines.
Experience Memory Graph: One-Shot Error Correction for Agents
KDD ’27, August 1–5, 2027, San Jose, United States.
Table 2: Main results of our EMG compared with various baselines, where DeepSeek is abbreviated in DS. S-SR and U-SR denote Success Rate (%) on Seen and Unseen splits respectively, and S-AR and U-AR denote Average Reward (%) on Seen and Unseen splits.
S-AR
S-SR
U-AR
U-SR
Qwen3
S-AR
S-SR
U-AR
U-SR
Qwen3-4B
ReAct Reflexion ExpeL CDMem MemP EMG
29.29 34.29 38.57 27.14 37.86 53.57
21.64 39.55 39.55 32.84 42.54 60.45
33.19 39.25 39.94 29.99 26.83 49.74
11.86 14.95 13.40 13.92 9.28 17.53
30.57 30.06 35.69 23.13 25.20 46.76
8.53 8.06 11.85 8.53 8.53 16.11
22.51 27.69 29.83 22.59 25.04 40.69
ReAct Reflexion ExpeL CDMem MemP EMG
86.43 82.86 81.43 95.71 85.71 96.43
88.06 90.30 83.58 90.30 85.82 97.76
51.77 47.12 46.56 31.91 44.73 62.37
17.53 12.89 19.07 15.46 10.31 28.87
52.69 43.92 44.90 35.38 44.78 61.94
13.74 8.06 15.17 8.53 11.37 24.17
51.70 47.53 48.45 46.22 47.12 61.92
Main Results
The main results are presented in Table 2. An analysis of these results reveals three key insights as follows. Consistent Superiority over Iterative Paradigms. Across both datasets and all evaluation splits, EMG consistently outperforms all baseline methods in terms of SR and AR with both small and large models. Notably, our method demonstrates a clear advantage over frameworks based on reflect-replay loop such as Reflexion, ExpeL, and CDMem. Those baselines rely on reasoning about erroneous actions and re-executing attempts to self-correct. While our EMG directly uncovers the correct correction paths from the training set and constructs memory, thereby guiding test-time decisions more reliably and achieving higher success rates. Overcoming the Reasoning Bottleneck of Compact LLMs. The performance gap between EMG and the baselines is more evident for the smaller Qwen3-4B than for the larger DeepSeekV4-Flash, specially for ALFWorld. Iterative frameworks like expel require strong intrinsic reasoning to analyze past mistakes and derive alternative actions, the capacity that smaller LLMs often lack. By providing insights from error correction and workflow, EMG helps smaller models overcome this limitation, leading to substantially larger relative gains compared to large models. Moreover, when adopting DeepSeek for testing, although iterative baselines are equipped with DeepSeek model for better reflection, they still underperform EMG, suggesting that the structured extraction of corrections and workflows provides additional benefits that scaling alone and iterative reflection do not fully capture. Bridging the Scale Gap in Complex Tasks. The efficacy of EMG is highlighted in the highly demanding ScienceWorld environment, which necessitates intricate multi-step scientific reasoning. Remarkably, the 4B-parameter Qwen3 model equipped with EMG achieves performance comparable to—and in some metrics exceeding—the significantly larger DeepSeek model running standard baselines. This suggests that our EMG can effectively polish
ScienceWorld
U-SR
EMG w/o NE EMG w/o E EMG
29.29 48.57 53.57
21.64 52.99 60.45
33.19 34.84 49.74
11.86 12.37 17.53
30.57 35.77 46.76
8.53 9.48 16.11
DS-V4
U-SR
ALFWorld S-SR
EMG w/o NE EMG w/o E EMG
86.43 91.43 96.43
88.06 95.52 97.76
51.77 60.54 62.37
17.53 29.38 28.87
52.69 58.87 61.94
13.74 23.22 24.17
Avg.
S-SR
5.2
Table 3: Ablation study of EMG . Method
ScienceWorld
DS-V4-Flash
Method
ALFWorld
the capacity of small models when tackling complex, long-horizon decision-making problems.
5.3
Ablation Study
To isolate the contributions of each component, we evaluate two ablated variants: EMG w/o NE: removing both node’s intra-task insights and edge’s cross-task insights, and it is actually ReAct without memory; EMG w/o E: removing only the edge’s cross-task insights and retaining node’s intra-task insights. The results are detailed in Table 3, from which we draw three principal conclusions. Crucial Role of Intra-Task Node Memory. Comparing EMG w/o NE (no memory) with EMG w/o E (node only) shows that node memory alone brings substantial gains in most cases. For instance, DeepSeek’s Unseen SR in ScienceWorld jumps from 13.74% to 23.22%, and Qwen’s Unseen SR in ALFWorld from 21.64% to 52.99%. However, on ScienceWorld with the small Qwen model, the improvement is modest (Seen SR: 11.86% → 12.37%; Unseen SR: 8.53% → 9.48%), suggesting that extremely complex reasoning may still require additional cross-task support. Overall, node memory serves as a solid foundation, effectively preventing repeated failures where the task is within the model’s basic reasoning capacity. Differential Sensitivity to Cross-Task Insights. Adding edges (comparing EMG w/o E to full EMG) yields asymmetric gains. The small Qwen3-4B benefits noticeably from cross-task insights, e.g., ScienceWorld Unseen SR rises from 9.48% to 16.11%. In contrast, the large DeepSeek gains marginally (e.g., Unseen SR 23.22% → 24.17%), indicating that large models already possess strong generalization ability, while small models rely on explicit cross-task knowledge to compensate for limited parameters. Synergistic Superiority of Dual Memory. The full EMG (nodes + edges) achieves the best performance across all metrics. For Qwen in ALFWorld, Average Reward climbs steadily from baseline (w/o NE) to node only (w/o E) to full model, and the same trend holds for other settings. This demonstrates that local error correction (node) and global knowledge transfer (edge) work synergistically, leading to both high success rates and robust intermediate reasoning.
5.4
One-Shot Memory vs. Iterative Correction
We evaluate all methods on the seen splits of ALFWorld (with Qwen3-4B) and ScienceWorld (with DeepSeek-V4-Flash). For iterative baselines (Reflexion, ExpeL, CDMem), we allow up to five test-time iterations and report their final success rate. For one-shot memory, they perform a single execution per test task without online trial-and-error. The results are shown in figure 3.
KDD ’27, August 1–5, 2027, San Jose, United States.
Figure 3: Success rate between one-shot memory and iterative correction methods. The one-shot memory methods (EMG, ReAct and Memp) only run for 1 iteration, and the iterative methods (Reflexion, Expel and CDMem) run for 5 iterations. The results show that while some iterative baselines (e.g., Reflexion, ExpeL) can surpass simple one-shot methods like ReAct or MemP after several rounds of reflection, our one-shot EMG consistently achieves the highest success rate among all methods on both benchmarks. For instance, on ALFWorld with Qwen3-4B, the iterative success rates range from 27.14% to 38.57%, whereas EMG reaches 53.57% with a single execution. Similarly, on ScienceWorld with DeepSeek-V4-Flash, the iterative results vary between 12.89% and 19.07%, while EMG attains 28.87%. This demonstrates that our offline-structured memory not only provides more effective correction than online trial-and-error loops, but also eliminates the need for multiple test-time attempts, thereby significantly reducing both time and API costs.
Wenjun Wang et al.
Figure 5: Sensitivity analysis of EMG. We report the success rate of EM when the retrieved node counts change.
5.6
6
Figure 4: Time cost of EMG and iterative self-reflection baselines.
5.5
Time Cost Comparison
We evaluate the inference time efficiency of our EMG against iterative baselines (CDMem, Reflexion, ExpeL) on ScienceWorld using the Qwen3-4B model, as shown in figure 4. While iterative methods require up to five test-time attempts to self-correct, EMG performs only a single execution per task, leveraging offline-constructed memory. As a result, EMG incurs substantially lower total inference time than all baselines, while simultaneously achieving higher success rates (see main results). The time advantage of EMG is consistent across both seen and unseen splits. Notably, when deployed with larger closed-source models (e.g., DeepSeek-V4-Flash), the inference cost per attempt is considerably higher; EMG’s one-shot nature therefore multiplies the savings in both time and API expenses, further underscoring its practical efficiency.
Hyperparameter Sensitivity Analysis
We analyze the sensitivity of EMG to the number of retrieved nodes (top-𝑘) on two benchmarks: ALFWorld seen and ScienceWorld unseen, both using DeepSeek-V4-Flash. On ALFWorld, we vary top-𝑘 from 5 to 9; on ScienceWorld, we vary it from 2 to 6. Each node includes all of its connected edge insights for the retrieved memory, and we report the success rate as shown in figure 5. Overall, EMG exhibits strong robustness across the tested range of 𝑘. Performance remains consistently high with only minor fluctuations, and even the smallest retrieval sets achieve competitive results, indicating that the stored insights are highly informative and do not require many examples to be effective. A slight decline is observed when 𝑘 becomes too large, which may be due to the inclusion of too many examples that occasionally distract the model in selecting the most appropriate correction. Nevertheless, the variation is modest, confirming that EMG is not sensitive to the exact choice of 𝑘 and performs reliably without extensive tuning.
Conclusion
We propose Experience Memory Graph (EMG), a framework that constructs structured experience memory from training trajectories via graph matching. Unlike iterative self-reflection methods that rely on costly test-time trial-and-error, EMG formulates error correction as finding the shortest graph edit path between a failed exploration trajectory and a successful expert trajectory. By converting trajectories into directed action decision graphs and applying graph matching offline, we extract common subgraphs (successful workflows) and graph edit paths (correction instructions). These insights are organized into a memory graph where nodes store intra-task knowledge and edges store cross-task generalizable patterns, enabling one-shot test-time guidance without repeated loops. Experiments on extensive datasets demonstrate that EMG consistently outperforms strong iterative baselines in success rate and average reward, while requiring only a single test-time attempt. Ablation and sensitivity studies confirm the effectiveness and robustness of the proposed model. For future work, we plan to extend EMG to environments without expert trajectories.
Experience Memory Graph: One-Shot Error Correction for Agents
References [1] Petr Anokhin, Nikita Semenov, Artyom Y. Sorokin, Dmitry Evseev, Andrey Kravchenko, Mikhail Burtsev, and Evgeny Burnaev. 2025. AriGraph: Learning Knowledge Graph World Models with Episodic Memory for LLM Agents. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025. ijcai.org, 12–20. doi:10.24963/IJCAI.2025/2 [2] Qihao Cheng, Da Yan, Tianhao Wu, Zhongyi Huang, and Qin Zhang. 2025. Computing approximate graph edit distance via optimal transport. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–26. [3] Jizhan Fang, Xinle Deng, Haoming Xu, Ziyan Jiang, Yuqi Tang, Ziwen Xu, Shumin Deng, Yunzhi Yao, Mengru Wang, Shuofei Qiao, Huajun Chen, and Ningyu Zhang. 2026. LightMem: Lightweight and Efficient Memory-Augmented Generation. In The Fourteenth International Conference on Learning Representations. https: //openreview.net/forum?id=dyJ0GWpjJB [4] Runnan Fang, Yuan Liang, Xiaobin Wang, Jialong Wu, Shuofei Qiao, Pengjun Xie, Fei Huang, Huajun Chen, and Ningyu Zhang. 2025. Memp: Exploring agent procedural memory. arXiv preprint arXiv:2508.06433 (2025). [5] Pengyu Gao, Jinming Zhao, Xinyue Chen, and Long Yilin. 2025. An efficient context-dependent memory framework for llm-centric agents. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 3: Industry Track). 1055–1069. [6] Rui Ge, Yichao Fu, Yuyang Qian, Junda Su, Yiming Zhao, Peng Zhao, and Hao Zhang. 2026. Internalizing Agency from Reflective Experience. arXiv preprint arXiv:2603.16843 (2026). [7] Yuyang Hu, Shichun Liu, Yanwei Yue, Guibin Zhang, Boyang Liu, Fangyi Zhu, Jiahang Lin, Honglin Guo, Shihan Dou, Zhiheng Xi, et al. 2025. Memory in the age of ai agents. arXiv preprint arXiv:2512.13564 (2025). [8] Tenghao Huang, Kinjal Basu, Ibrahim Abdelaziz, Pavan Kapanipathi, Jonathan May, and Muhao Chen. 2025. R2d2: Remembering, replaying and dynamic decision making with a reflective agentic memory. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 30318–30330. [9] Namyoung Kim, Kai Tzu-iunn Ong, Yeonjun Hwang, Minseok Kang, Iiseo Jihn, Gayoung Kim, Minju Kim, and Jinyoung Yeo. 2025. PRINCIPLES: Synthetic Strategy Memory for Proactive Dialogue Agents. In The 2025 Conference on Empirical Methods in Natural Language Processing (EMNLP 2025). [10] Canasai Kruengkrai and Koichiro Yoshino. 2025. Teaching Text Agents to Learn Sequential Decision Making from Failure. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 31619–31635. [11] Xiaoxi Li, Wenxiang Jiao, Jiarui Jin, Guanting Dong, Jiajie Jin, Yinuo Wang, Hao Wang, Yutao Zhu, Ji-Rong Wen, Yuan Lu, et al. 2026. Deepagent: A general reasoning agent with scalable toolsets. In Proceedings of the ACM Web Conference 2026. 2219–2230. [12] Xuechen Liang, Meiling Tao, Yinghui Xia, Jianhui Wang, Kun Li, Yijin Wang, Yangfan He, Jingsong Yang, Tianyu Shi, Yuantao Wang, et al. 2025. Sage: Selfevolving agents with reflective and memory-augmented abilities. Neurocomputing 647 (2025), 130470. [13] Yixin Liu, Guibin Zhang, Kun Wang, Shiyuan Li, Shirui Pan, and Bo An. 2026. Graph-augmented large language model agents: Current progress and future prospects. IEEE Intelligent Systems 41, 2 (2026), 45–55. [14] Qirui Mi, Zhijian Ma, Mengyue Yang, Haoxuan Li, Yisen Wang, Haifeng Zhang, and Jun Wang. 2026. Skill-Pro: Learning Reusable Skills from Experience via Non-Parametric PPO for LLM Agents. In Proceedings of the 43rd International Conference on Machine Learning (ICML 2026). https://arxiv.org/abs/2602.01869 Spotlight. [15] Siru Ouyang, Jun Yan, I Hsu, Yanfei Chen, Ke Jiang, Zifeng Wang, Rujun Han, Long T Le, Samira Daruki, Xiangru Tang, et al. 2025. Reasoningbank: Scaling agent self-evolving with reasoning memory. arXiv preprint arXiv:2509.25140 (2025). [16] Revanth Gangi Reddy, Sagnik Mukherjee, Jeonghwan Kim, Zhenhailong Wang, Dilek Hakkani-Tur, and Heng Ji. 2025. Infogent: An agent-based framework for web information aggregation. In Findings of the Association for Computational Linguistics: NAACL 2025. 5745–5758. [17] Jie-Jing Shao, Haiyan Yin, Yueming Lyu, Xingrui Yu, Lan-Zhe Guo, Ivor Tsang, James Kwok, and Yu-Feng Li. 2026. Lifting Traces to Logic: Programmatic Skill Induction with Neuro-Symbolic Learning for Long-Horizon Agentic Tasks. arXiv preprint arXiv:2605.01293 (2026). [18] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: Language agents with verbal reinforcement learning. Advances in neural information processing systems 36 (2023), 8634–8652. [19] Yifan Song, Da Yin, Xiang Yue, Jie Huang, Sujian Li, and Bill Yuchen Lin. 2024. Trial and error: Exploration-based trajectory optimization of LLM agents. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 7584–7600.
KDD ’27, August 1–5, 2027, San Jose, United States.
[20] Jianheng Tang, Xi Zhao, Lemin Kong, Xiaofang Zhou, and Jia Li. 2025. Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond. Proceedings of the VLDB Endowment 18, 10 (2025), 3641–3654. [21] Hanlin Wang, Jian Wang, Chak Tou Leong, and Wenjie Li. 2025. Steca: Step-level trajectory calibration for llm agent learning. In Findings of the Association for Computational Linguistics: ACL 2025. 11597–11614. [22] Zora Zhiruo Wang, Jiayuan Mao, Daniel Fried, and Graham Neubig. 2025. Agent Workflow Memory. In International Conference on Machine Learning. PMLR, 63897–63911. [23] Zhepei Wei, Wenlin Yao, Yao Liu, Weizhi Zhang, Qin Lu, Liang Qiu, Changlong Yu, Puyang Xu, Chao Zhang, Bing Yin, et al. 2025. Webagent-r1: Training web agents via end-to-end multi-turn reinforcement learning. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 7920–7939. [24] Yaxiong Wu, Yongyue Zhang, Sheng Liang, and Yong Liu. 2025. Sgmem: Sentence graph memory for long-term conversational agents. arXiv preprint arXiv:2509.21212 (2025). [25] Zhaofen Wu, Hanrong Zhang, Fulin Lin, Wujiang Xu, Xinran Xu, Yankai Chen, Henry Peng Zou, Shaowen Chen, Weizhi Zhang, Xue Liu, et al. 2026. Gam: Hierarchical graph-based agentic memory for llm agents. arXiv preprint arXiv:2604.12285 (2026). [26] Siyu Xia, Zekun Xu, Jiajun Chai, Wentian Fan, Yan Song, Xiaohan Wang, Guojun Yin, Wei Lin, Haifeng Zhang, and Jun Wang. 2025. From experience to strategy: Empowering llm agents with trainable graph memory. arXiv preprint arXiv:2511.07800 (2025). [27] Tianle Xia, Lingxiang Hu, Yiding Sun, Ming Xu, Lan Xu, Siying Wang, Wei Xu, and Jie Jiang. 2026. GraSP: Graph-Structured Skill Compositions for LLM Agents. [28] Wujiang Xu, Zujie Liang, Kai Mei, Hang Gao, Juntao Tan, and Yongfeng Zhang. 2026. A-mem: Agentic memory for llm agents. Advances in Neural Information Processing Systems 38 (2026), 17577–17604. [29] Wei Yang, Jinwei Xiao, Hongming Zhang, Qingyang Zhang, Yanna Wang, and Bo Xu. 2025. Coarse-to-fine grounded memory for llm agent planning. arXiv preprint arXiv:2508.15305 (2025). [30] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. 2023. ReAct: Synergizing Reasoning and Acting in Language Models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net. https://openreview. net/forum?id=WE_vluYUL-X [31] Tianjun Yao, Yongqiang Chen, Yujia Zheng, Pan Li, Zhiqiang Shen, and Kun Zhang. 2026. ParamMem: Augmenting Language Agents with Parametric Reflective Memory. arXiv preprint arXiv:2602.23320 (2026). [32] Weiran Yao, Shelby Heinecke, Juan Carlos Niebles, Zhiwei Liu, Yihao Feng, Le Xue, Rithesh Ramapura Narasimha Murthy, Zeyuan Chen, Jianguo Zhang, Devansh Arpit, et al. 2024. Retroformer: Retrospective large language agents with policy gradient optimization. In International Conference on Learning Representations, Vol. 2024. 10091–10111. [33] Jiawei Yu, Yixiang Fang, Xilin Liu, and Yuchi Ma. 2026. H-Mem: A Novel Memory Mechanism for Evolving and Retrieving Agent Memory via a Hybrid Structure. arXiv preprint arXiv:2605.15701 (2026). [34] Dengjia Zhang, Xiaoou Liu, Lu Cheng, Yaqing Wang, Kenton Murray, and Hua Wei. 2026. SELAUR: Self Evolving LLM Agent via Uncertainty-aware Rewards. arXiv preprint arXiv:2602.21158 (2026). [35] Guibin Zhang, Muxin Fu, Kun Wang, Frank Wan, Miao Yu, and Shuicheng Yan. 2026. G-memory: Tracing hierarchical memory for multi-agent systems. Advances in Neural Information Processing Systems 38 (2026), 12988–13018. [36] Guibin Zhang, Junhao Wang, Junjie Chen, Wangchunshu Zhou, Kun Wang, and Shuicheng Yan. 2025. AgenTracer: Who Is Inducing Failure in the LLM Agentic Systems? arXiv preprint arXiv:2509.03312 (2025). [37] Andrew Zhao, Daniel Huang, Quentin Xu, Matthieu Lin, Yong-Jin Liu, and Gao Huang. 2024. Expel: Llm agents are experiential learners. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38. 19632–19642. [38] Longtao Zheng, Rundong Wang, Xinrun Wang, and Bo An. 2024. Synapse: Trajectory-as-exemplar prompting with memory for computer control. In International Conference on Learning Representations, Vol. 2024. 19036–19066. [39] Xu Zheng, Zhuomin Chen, Chaohao Lin, Hua Wei, Haifeng Chen, Wei Cheng, and Dongsheng Luo. 2026. Trajectory Graph Copilot: Pre-Action Error Diagnosis in LLM Agents. https://openreview.net/forum?id=ighxnB6nJF [40] Kunlun Zhu, Zijia Liu, Bingxuan Li, Muxin Tian, Yingxuan Yang, Jiaxun Zhang, Pengrui Han, Qipeng Xie, Fuyang Cui, Weijia Zhang, et al. 2025. Where llm agents fail and how they can learn from failures. arXiv preprint arXiv:2509.25370 (2025).
KDD ’27, August 1–5, 2027, San Jose, United States.
Figure 6: A concrete example for constructing action decision graph. Nodes/ Edges with different colors represent different types of actions/ observations. Algorithm 1 Building Action Decision Graph Input: Trajectory 𝜏 = (𝑞, 𝑜 0, 𝑎 1, 𝑜 1, . . . , 𝑎𝑚 , 𝑜𝑚 ) and its reward 𝑟 . Output: Graph 𝐺 = (𝑉 , 𝐸, 𝑞, 𝑟 ) with node attributes (𝑘, 𝑎 raw ) and edge attributes 𝑠; labels ℓ𝑛 , ℓ𝑒 assigned post-hoc. 1: 𝑠 ← normalize(𝑜 0 ) // current valid state 2: 𝑙𝑎𝑠𝑡 ← 𝑣 init // virtual INIT node 3: Φ ← {} // map from action tuple to node 4: for 𝑡 = 1 to 𝑚 do 5: 𝑘 ← normalize(𝑎𝑡raw ); keep raw text 𝑎𝑡raw 6: if 𝑘 ∉ Φ then 7: Create new node 𝑣 with (𝑘, 𝑎𝑡raw ); Φ[𝑘] ← 𝑣 8: else 9: 𝑣 ← Φ[𝑘] // reuse node 10: end if 11: Add edge (𝑙𝑎𝑠𝑡, 𝑣) with attribute 𝑠 (i.e., set 𝑠 (𝑙𝑎𝑠𝑡,𝑣) = 𝑠) 12: 𝑜˜ ← normalize(𝑜𝑡 ) 13: if 𝑜˜ is valid then ˜ 𝑙𝑎𝑠𝑡 ← 𝑣 14: 𝑠 ← 𝑜; 15: end if 16: end for 17: Set 𝐺 .𝑞 ← 𝑞, 𝐺 .𝑟 ← 𝑟 18: return 𝐺
A
Details for constructing action decision graph
Algorithm 1 details the procedure of constructing the directed action decision graph. Figure 6 demonstrates a concrete example of how to transform the sequential raw exploration trajectory 𝑒𝑛 into directed action decision graph 𝐺𝑛 , where 𝑜𝑖 represents observations and 𝑎𝑖 represents actions.
Wenjun Wang et al.
In the raw trajectory 𝑒𝑛 , observations 𝑜 2 and 𝑜 3 are uninformative (e.g., “nothing happened” in ALFWorld), indicating that actions 𝑎 2 and 𝑎 3 are both invalid attempts under the same valid observation 𝑜 1 . The subsequent action 𝑎 4 is a valid action also taken under 𝑜 1 . If we directly applied graph edit distance to the raw sequential trajectory, we would delete 𝑜 2, 𝑜 3, 𝑎 2, 𝑎 3 ; however, as 𝑜 2 and 𝑜 3 carry no meaningful information, the resulting edit path would produce an insight such as “under observation 𝑜 2 do not take 𝑎 3 ”, which is meaningless. The correct insight should be “under observation 𝑜 1 , avoid 𝑎 2 and 𝑎 3 ”. To capture this, we introduce parallelizing consecutive invalid actions: all actions that follow the same valid state 𝑜 1 without changing the environment are connected in parallel from the same previous valid node. Hence 𝑎 2 , 𝑎 3 , and 𝑎 4 all receive edges from 𝑎 1 with the same edge label 𝑜 1 . This makes the graph edit path directly indicate which actions are invalid under 𝑜 1 . Additionally, we observe that the same core action may be taken under different observations. To better model this, we propose node reuse: if a normalized action appears later in the trajectory (e.g., 𝑎 7 is the same action as 𝑎 4 ), we do not create a new node; instead, we connect the incoming edge (carrying 𝑜 6 ) directly to the existing node of that action (𝑎 4 ). This allows a single node to collect multiple incoming edges with different observation labels, revealing under which conditions that action is appropriate.
B
Algorithm of extracting common subgraph and graph edit path
Given a node matching 𝑀 between two directed labeled graphs 𝐺 and 𝐺 ′ (obtained via the FGW solver), the following two algorithms extract structured knowledge from the matched graphs. Algorithm 2 constructs the common subgraph by retaining only those edges in 𝐺 whose both endpoints are matched and whose corresponding edge exists in 𝐺 ′ with an identical edge label. This yields the set of actions that are already correct under the same observation, i.e., the successful workflow. Algorithm 3 derives a complete graph edit path from 𝑀. It collects unmatched nodes (deletions from 𝐺 and insertions from 𝐺 ′ ), node label mismatches (relabelings), and edge mismatches (missing edges, extra edges, or label differences) to produce edge deletions, insertions, and relabelings. All collected operations together form a legal edit path that transforms 𝐺 into 𝐺 ′ . Unlike classical methods designed for undirected graphs without edge labels, our algorithms explicitly handle directed edges and edge labels, preserving the semantic information carried by observations.
C
Discussion about the robustness of graph edit path
We further analyze the robustness of our graph edit path extraction (Algorithm 3). The overall graph matching procedure relies on the FGWAlign solver [20], which may not always produce the globally optimal node correspondence. According to the original FGWAlign evaluation, for graph pairs with tens of nodes, the recall of the predicted edit path against the ground-truth shortest path is around 90%. It is important to clarify that a recall below 100% does not imply an invalid edit path. Given any node matching 𝑀 (optimal or suboptimal), Algorithm 3 always generates a legal edit path: applying the returned insertions, deletions, and relabelings
Experience Memory Graph: One-Shot Error Correction for Agents
Algorithm 2 Extract Common Subgraph from Node Matching Input: Directed labeled graphs 𝐺 = (𝑉 , 𝐸, ℓ𝑛 , ℓ𝑒 ), 𝐺 ′ = (𝑉 ′, 𝐸 ′, ℓ𝑛′ , ℓ𝑒′ ), and a node matching 𝑀 : 𝑉 ↦→ 𝑉 ′ (injective on matched nodes). Output: Common subgraph 𝐺𝑐 = (𝑉𝑐 , 𝐸𝑐 ) where 𝑉𝑐 ⊆ 𝑉 (matched nodes) and 𝐸𝑐 ⊆ 𝐸 (edges preserved under matching). 1: 𝑉𝑐 ← {𝑢 ∈ 𝑉 | 𝑀 (𝑢) defined} 2: 𝐸𝑐 ← ∅ 3: for each edge (𝑢 1 , 𝑢 2 ) ∈ 𝐸 with 𝑢 1 , 𝑢 2 ∈ 𝑉𝑐 do 4: (𝑣 1, 𝑣 2 ) ← (𝑀 (𝑢 1 ), 𝑀 (𝑢 2 )) 5: if (𝑣 1, 𝑣 2 ) ∈ 𝐸 ′ and ℓ𝑒 (𝑢 1, 𝑢 2 ) = ℓ𝑒′ (𝑣 1, 𝑣 2 ) then 6: Add (𝑢 1, 𝑢 2 ) to 𝐸𝑐 7: end if 8: end for 9: return 𝐺𝑐 Algorithm 3 Derive Graph Edit Path from Node Matching Input: Same as Algorithm 2. Output: Graph edit operation sets Δ𝑛del, Δ𝑛ins, Δ𝑛relab, Δ𝑒del, Δ𝑒ins, Δ𝑒relab . del ← {𝑢 ∈ 𝑉 | 𝑀 (𝑢) undefined} 1: Δ𝑛 ins ← {𝑣 ∈ 𝑉 ′ | 𝑀 −1 (𝑣) undefined} 2: Δ𝑛 3: for each matched pair (𝑢, 𝑣) with 𝑀 (𝑢) = 𝑣 do 4: if ℓ𝑛 (𝑢) ≠ ℓ𝑛′ (𝑣) then 5: Add (𝑢, ℓ𝑛 (𝑢), ℓ𝑛′ (𝑣)) to Δ𝑛relab 6: end if 7: end for 8: for each edge (𝑢 1 , 𝑢 2 ) ∈ 𝐸 where 𝑀 (𝑢 1 ), 𝑀 (𝑢 2 ) defined do 9: (𝑣 1, 𝑣 2 ) ← (𝑀 (𝑢 1 ), 𝑀 (𝑢 2 )) 10: if (𝑣 1, 𝑣 2 ) ∉ 𝐸 ′ then 11: Add (𝑢 1, 𝑢 2 ) to Δ𝑒del 12: else 13: if ℓ𝑒 (𝑢 1, 𝑢 2 ) ≠ ℓ𝑒′ (𝑣 1, 𝑣 2 ) then 14: Add (𝑢 1, 𝑢 2, ℓ𝑒 (𝑢 1, 𝑢 2 ), ℓ𝑒′ (𝑣 1, 𝑣 2 )) to Δ𝑒relab 15: end if 16: end if 17: end for 18: for each edge (𝑣 1 , 𝑣 2 ) ∈ 𝐸 ′ where 𝑀 −1 (𝑣 1 ), 𝑀 −1 (𝑣 2 ) defined do 19: (𝑢 1, 𝑢 2 ) ← (𝑀 −1 (𝑣 1 ), 𝑀 −1 (𝑣 2 )) 20: if (𝑢 1, 𝑢 2 ) ∉ 𝐸 then 21: Add (𝑣 1, 𝑣 2 ) to Δ𝑒ins 22: end if 23: end for del , Δins , Δrelab , Δdel , Δins , Δrelab 24: return Δ𝑛 𝑛 𝑛 𝑒 𝑒 𝑒 to the source graph 𝐺 exactly yields the target graph 𝐺 ′ . The only difference is that a suboptimal matching may lead to a longer path (i.e., more edit operations) than the shortest possible one. Recall measures how many of the operations in the shortest path are preserved in our derived path; the remaining operations are legitimate but redundant alternatives. Consequently, our method is highly robust to matching inaccuracies. Even when the node matching is not optimal, the extracted correction instructions remain valid and can successfully repair the failed trajectory. In the extreme (and practically improbable) case
KDD ’27, August 1–5, 2027, San Jose, United States.
where the node matching is completely wrong — for instance, every node in 𝐺 is matched to an unrelated node in 𝐺 ′ — Algorithm 3 will produce an edit path that essentially deletes all actions of the failed trajectory and inserts (or relabels) all actions of the expert trajectory. The resulting insight reduces to “follow the successful trajectory entirely”, which, although not leveraging partial correctness, still provides a correct and executable plan. Hence, even under the worst possible matching, our framework offers a safe fallback. This robustness, together with the high empirical recall of the matching solver, guarantees that EMG reliably produces useful correction knowledge across a wide range of scenarios.
D
Notations Table 4: Summary of key symbols. Symbol 𝜏 𝑞 𝑎𝑡 𝑜𝑡 𝑟
Meaning Complete trajectory (𝑞, 𝑜 0 , 𝑎 1 , 𝑜 1 , . . . , 𝑎𝑚 , 𝑜𝑚 ) Task query / instruction Action at step 𝑡 Observation at step 𝑡 Reward (success/failure)
𝐺 = (𝑉 , 𝐸, 𝑞, 𝑟 ) 𝑣𝑖 𝑒𝑖 ℓ𝑛 (𝑣𝑖 ) ℓ𝑒 (𝑒𝑖 ) 𝑣init
Action decision graph Node in action decision graph (represents an action) Edge in action decision graph, connecting (𝑣𝑖 , 𝑣𝑖+1 ) Node label (integer) Edge label (integer) Virtual INIT node (ℓ𝑛 = 0)
G𝑚 = ( V, E ) 𝜈𝑖 𝜖𝑖 𝑗 𝐼𝑖intra 𝐼𝑖cross 𝑗
Experience Memory Graph Node in experience memory graph (one training task) Edge in experience memory graph, connecting 𝜈𝑖 and 𝜈𝑗 Intra-task insight on node 𝜈𝑖 Cross-task insight on edge 𝜖𝑖 𝑗
𝐺𝑖 𝐺𝑖∗ 𝐺𝑖𝑐 𝐺𝑖𝑒 𝐺𝑖𝑐𝑗 𝑃 𝜋
Exploration graph for task 𝑖 Expert graph for task 𝑖 Common subgraph (successful workflow) Graph edit path (correction instructions) Cross-task common subgraph Node matching matrix Soft assignment matrix (optimal transport)