From Experience to Strategy: Empowering LLM Agents with Trainable Graph Memory

Motivation

• The paper addresses unstable long-horizon agent decisions by asking whether structured explicit memory can guide implicit policy learning.Agents may produce inefficient action sequences, repeat mistakes, or fail completely.Source: §1 · pp. 1–2

Experience reuse

• Explicit prompting exposes reasoning but adapts poorly, whereas implicit training generalizes but is opaque, lossy, and vulnerable to catastrophic forgetting.Source: §1 · pp. 1–2

Framework

• The proposed framework converts agent trajectories into finite-state-machine paths and distills them into high-level, generalizable meta-cognitive strategies.Source: §1 · p. 2
• Reinforcement-driven weight optimization estimates each stored strategy’s utility from downstream performance and selectively calibrates memory connections.Source: §1 · p. 2
• The graph acts as an explicit policy prior during RL, dynamically injecting high-quality strategies into training to improve policy learning and final performance.Source: §1 · p. 2

2.1 LLM AGENTS AND PLANNING WITH EXTERNAL TOOLS

• Tool-augmented agents interleave reasoning with search, while RL-based frameworks train autonomous query generation and tool use for multi-step problem solving.Source: §2.1 · p. 2
• The related work identifies missing explicit long-term memory for reusable tool-use patterns and proposes graph-based strategic priors to generalize planning across domains.Source: §2.1 · p. 3

2.2 MEMORY ARCHITECTURES AND STRATEGIC LEARNING

• Existing memory methods include self-feedback, reusable trajectories, evolving long-horizon memories, dynamic notes, and logic-aware graphs.Source: §2.2 · p. 3
• Unlike largely static or task-specific approaches, the proposed trainable graph evaluates memory utility and updates strategies through reinforcement learning.Source: §2.2 · p. 3

3.1 HETEROGENEOUS GRAPH STRUCTURE

• A heterogeneous graph consists of typed nodes, directed typed edges, and node contents, with each edge specifying a relation between nodes.Source: §3.1 · p. 3
• Type-specific adjacency matrices encode connectivity, while coupled weight matrices determine effective information flow over feasible graph paths.Source: §3.1 · p. 3

3.2 LLM AGENTS WITH TOOL-AUGMENTED REASONING

• Tool-augmented reasoning represents each agent step using dialogue history and an action that may be internal reasoning, tool invocation, or answer generation.Source: §3.2 · pp. 3–4
• Agents continue until producing an answer or reaching a tool-use limit, and each trajectory records states, actions, observations, and reward for policy optimization.Source: §3.2 · p. 4

4.1 STAGE 1: HIERARCHICAL MEMORY GRAPH CONSTRUCTION

• The memory graph links query nodes to canonical transition paths and then to meta-cognition nodes encoding generalized strategic principles.Its directed structure uses weighted query-to-transition and transition-to-meta-cognition connections.Source: §4.1 · p. 4
• Raw execution trajectories are mapped to finite-state-machine paths, filtering execution noise while preserving semantically meaningful decision points for cross-query comparison.The FSM represents abstract cognitive states, actions, and transitions.Source: §4.1 · p. 4
• Meta-cognitions arise by contrasting successful and failed paths, or by transferring patterns from successful paths of semantically similar queries when only failures exist.The graph also reinforces useful principles, adds novel patterns, and discards redundant or low-confidence paths.Source: §4.1 · pp. 4–5

4 METHOD

• The framework has three stages: graph construction from trajectories, reinforcement-based weight optimization, and top-k strategy injection during RL policy optimization.Figure 2 summarizes the end-to-end pipeline.Source: §4 · p. 4, Figure 2 · p. 5

4.2 STAGE 2: TRAINABLE GRAPH WEIGHT OPTIMIZATION

• For a new query, the system selects top-k relevant neighbors and samples candidate meta-cognitions according to learned relevance scores derived from graph path strengths.Selection probabilities use a softmax over the relevance scores.Source: §4.2 · p. 6
• Strategy utility is estimated by the reward gap between trajectories with and without a candidate meta-cognition, then used to update graph weights through REINFORCE.Positive reward gaps strengthen supporting paths, whereas negative gaps weaken them.Source: §4.2 · p. 6

4.3 STAGE 3: MEMORY-GUIDED POLICY OPTIMIZATION

• During RL training, optimized meta-cognitive strategies are retrieved, verbalized, prepended to the query, and supplied as strategic context to the policy network.This integrates structured memory into training rather than using it only during inference.Source: §4.3 · p. 6
• The memory-augmented policy is optimized for expected cumulative reward with policy gradients, using GRPO with an advantage estimator and clipping parameter.The retrieved strategies provide dynamically evolving guidance during policy learning.Source: §4.3 · pp. 6–7

5.2 BASELINE EVALUATION

• The evaluation measures both zero-training direct inference impact and RL-training impact, including convergence speed and final performance.The experiments use seven QA datasets spanning general and multi-hop question answering.Source: §5.2 · p. 7, §5.1 · p. 7

5.3 MAIN RESULTS

• On direct inference, the method ranks first on the 8B model with an average score of 0.365, a +9.3% relative improvement over ITR, and gains +25.8% on Qwen3-4B.The inference evaluation covers seven QA datasets, including single-turn and multi-hop reasoning tasks.Source: §5.1 · p. 7, §5.3 · p. 8
• Using memory constructed only from HotpotQA, the method reaches state-of-the-art or highly competitive performance across out-of-domain datasets including NQ, TriviaQA, PopQA, and 2wiki.The reported transfer is presented as evidence that the learned reasoning structures are not merely overfitted patterns.Source: §5.3 · p. 8
• The method achieves 0.408 average performance on Qwen3-8B, improving over Search-R1 by 3.29%, while Qwen3-4B gains 13.60% over Search-R1.The trained Qwen3-4B model scores 0.426 versus 0.395 for the baseline Qwen3-8B model.Source: §5.3 · p. 8
• Training-curve comparisons are reported separately for 4B and 8B models, while Table 2 compares training performance across seven QA datasets.Table 2 marks in-domain and out-of-domain datasets and reports average relative improvement against Search-R1.Source: Figure 3 · p. 8, Table 2 · p. 8

5.4 ABLATION STUDIES

• Freezing graph weights causes significant performance drops, especially on 2WikiMultiHopQA, showing that learned edge confidence is important for strategy reuse.Uniformly weighted edges retrieve strategies by structural presence rather than learned utility.Source: §5.4 · p. 9
• On the 4B model, increasing retrieved meta-cognitions from k = 0 to 3 steadily improves average accuracy, whereas larger k values yield diminishing returns and possible noise.The ablation identifies k = 3 as the best balance between strategy diversity, guidance, and prompt efficiency.Source: §5.4 · p. 9
• The same memory graph outperforms its non-memory counterpart with Gemini-2.5-pro, although absolute results differ slightly across backends.This supports model-agnostic, plug-and-play use of the structured memory and retrieval-guided prompting strategy.Source: §5.4 · p. 9

• The framework structurally encodes historical queries, policy trajectories, and metacognitive strategies in a multi-level graph that guides policy optimization.It addresses inefficient decision-making and poor experience reuse through explicit strategy recall integrated into the RL loop.Source: §6 · p. 9
• Dynamic memory weights updated by RL signals selectively reinforce high-utility strategies and re-inject them through prompt augmentation.The mechanism unifies explicit memory with dynamic learning rather than relying on static prompting or implicit optimization alone.Source: §6 · p. 9
• The method improves reasoning accuracy at inference time, accelerates RL convergence, and yields superior final performance with strong generalization across diverse tasks.Source: §6 · p. 9

A.1 MULTI-TURN TOOL-INTERGRATED QA

• The framework uses the 2018 Wikipedia dump with the E5 retriever, encapsulating retrieval as an MCP tool that the LLM can invoke autonomously.Source: §A.1 · p. 12
• Qwen3 separates reasoning, tool calls, tool responses, and final answers with dedicated tags while permitting up to six tool invocations.The protocol supports multiple interaction rounds before producing an answer or stopping at the limit.Source: §A.1 · p. 12
• A representative table and case study illustrate how structured tool interactions retrieve external knowledge for informed reasoning.Source: §A.1 · p. 12

A.2 EXPERIMENTAL SETTINGS

• The study compares direct-inference baselines, trajectory memory, A-MEM, Expel, and RL agents with or without memory support.Baselines include CoT, tool-integrated reasoning, Search-R1, and three memory designs.Source: §A.2 · pp. 12–13
• The setup reports Exact Match as the primary metric and uses GPT-4o when constructing memory for A-Mem, Expel, and the proposed method.Source: §A.2 · p. 13
• Experiments use Qwen-3-4B and Qwen-3-8B across seven datasets, with HotpotQA as the in-domain set and six datasets for out-of-domain evaluation.HotpotQA supplies 1,000 examples for memory construction and 5,000 for weight training.Source: §A.2 · p. 13

B.1 THE CONSTRUCTION OF PATH IN FINITE STATE MACHINE

• Raw agent executions are produced by Qwen3 and then mapped by a powerful language model from reasoning and tool-call sequences to FSM paths.The resulting paths encode cognitive states such as planning, tool execution, analysis, diagnosis, and answer generation.Source: §B.1 · p. 14

B.2 META-COGNITION CONSTRUCTION

• The memory graph contains query, transition-path, and meta-cognition layers linking task instances to canonical behavioral pathways and generalized strategic principles.Query nodes record inputs, trajectories, and outcomes; path nodes abstract execution traces; meta-cognition nodes encode human-readable heuristics.Source: §B.2 · p. 14
• Algorithm 1 updates the graph by sampling policy rollouts, grounding them in FSM paths, labeling success or failure, inducing meta-cognitions, merging matching principles, and linking paths to them.The procedure takes a graph, query, policy, FSM, rollout count, and similarity threshold, then returns an updated graph.Source: §B.2 · p. 15
• Meta-cognitions are induced by comparing successful and failed paths for the same query, contrasting failures with similar-query successes, or extracting principles from successful paths.Same-query contrasts support high-confidence induction, while similar-query transfer produces speculative heuristics.Source: §B.2 · pp. 15, 17

C.1 THE NUMBER OF THE META-COGNITION

• Top k=5 achieves the best overall result across the evaluated strategy-count configurations, balancing diversity and relevance.The comparison covers 0, 1, 3, and 5 retrieved strategies across seven QA benchmarks.Source: §C.1 · p. 17
• A single strategy improves over the no-memory ITR baseline, including +11.6% on Bamboogle and +2.9% on HotpotQA.Source: §C.1 · p. 17
• Increasing the number of strategies generally improves performance, but marginal gains shrink because of redundancy or prompt saturation.Source: §C.1 · p. 17
• Moderate numbers of well-curated strategies can improve generalization and decision quality without the risks of prompt overload or irrelevant-memory noise.Source: §C.1 · p. 17

C.2 CROSS-API MEMORY ROBUSTNESS

• Across seven QA datasets, Gemini- and GPT-4o-constructed memories produce only minor performance differences in the same Qwen3-4B and Qwen3-8B agent architecture.This supports portability across the APIs used to construct the memory graph.Source: §C.2 · p. 17
• Gemini-based memory slightly outperforms GPT-4o-based memory in most evaluated cases.The comparison uses identical downstream Qwen3-4B and Qwen3-8B agents, isolating variation in the API used to construct memory.Source: §C.2 · p. 17
• +0.043 on Bamboogle with Qwen3-8B is a notable gain for Gemini-constructed memory over its GPT-4o counterpart.Gemini-based memory maintains parity or marginal gains on TriviaQA and PopQA.Source: §C.2 · p. 17

D CASE STUDIES

• The meta-cognitive agent corrects “National Security Law” to the fully grounded “Macau National Security Law,” reducing synthesis ambiguity when internal confidence is high.The case aligns the corrected response with the ground truth and illustrates structured validation as a self-checking mechanism.Source: D CASE STUDIES · pp. 17, 19
• The optimization algorithm samples a relevant meta-cognition, compares guided and unguided rewards, and updates graph weights with a REINFORCE policy-gradient signal.Its inputs include the memory graph, training queries, agent model, reward function, and learning rate; its output is an optimized graph.Source: D CASE STUDIES · p. 18
• Guidance selection activates a semantically relevant subgraph, scores candidate meta-cognitions from query-path similarities and edge weights, then samples one using softmax probabilities.The procedure returns both the selected meta-cognition and its selection probability for subsequent weight optimization.Source: D CASE STUDIES · p. 18

E.1 MULTI-TURN TOOL-INTERGRATED QA PROMPT

• For multi-turn tool use, the prompt guides the LLM on which tools to use and how to use them, while responses are mapped onto predefined state-machine paths.These prompts operationalize tool-interaction traces as structured paths for later analysis.Source: §E.1 · p. 19, §E.2 · p. 19

E.3 META-COGNITION CONSTRUCTING

• Meta-cognitions are induced by contrasting successful and failed state-machine paths to extract reusable decision patterns and errors to avoid.The construction process also assesses state-transition optimization and whether patterns depend on particular knowledge domains.Source: §E.3 · pp. 19, 22
• The prompts require generalizable, directly usable, concise principles expressed with cautious language and supported by sufficient evidence.They explicitly discourage definitive conclusions and require uncertainty acknowledgment.Source: §E.3 · p. 21
• The metacognition output records a decision, optional update target, reasoning, strategy principles, confidence scores, evidence-path count, and an uncertainty note.This quantity-aware JSON structure supports controlled creation, updating, or skipping of extracted guidance.Source: §E.3 · p. 21
• When more than 30 meta-cognitions exist, the system strongly prefers updating low- or medium-confidence entries over creating new ones.It skips operations when evidence is poor, existing coverage is sufficient, path differences are unclear, or strategy effects cannot be separated from domain familiarity.Source: §E.3 · pp. 22–23