Technical Summary: ExpGraph

Problem Statement

Large Language Model (LLM) agents have demonstrated strong capabilities in reasoning, tool use, and multi-step environment interaction. However, a critical bottleneck remains: most agents operate as "one-shot executors," solving each task from scratch without systematically reusing successful strategies or lessons learned from failure. While fine-tuning an executor on collected experience is a common remedy, it becomes increasingly inflexible as LLMs evolve rapidly. When a stronger or more suitable executor emerges, the experience learning process often requires retraining the specific model instance, making the system tightly coupled to a particular model. Furthermore, many capable LLMs are closed-source, too large, or expensive to update, rendering parameter-level modification impractical.

The core challenge addressed by this work is: How can an LLM agent learn from accumulated experience while keeping the executor itself frozen and replaceable? Existing methods often treat reusable experience as isolated records or rely on flat nearest-neighbor matching, failing to capture the relational nature of strategies, constraints, and failure patterns. Additionally, surface semantic relevance does not always equate to downstream utility; a similar-looking experience may offer little benefit, while a structurally related one might provide a crucial transferable strategy.

Methodology: ExpGraph

The authors propose ExpGraph, a model-agnostic experience learning framework that improves frozen LLM executors through a self-evolving relational memory and a trainable retrieval copilot. The framework decouples execution from experience learning, allowing the same external system to improve different frozen executors without modifying their parameters.

Core Components

1. Experience Graph Construction:

   • Historical trajectories ($\tau = (x, \xi, y, s)$) are summarized into compact natural-language experience units ($e$).
   • High-scoring trajectories are distilled into skills (successful patterns, heuristics), while low-scoring ones are distilled into lessons (failure modes, constraints).
   • These units form nodes in a sparse, undirected graph. Edges connect semantically or strategically related experiences based on cosine similarity thresholds, creating a structure that goes beyond flat lists.

2. Utility-Guided Graph Retrieval:

   • Retrieval Copilot: A lightweight, trainable policy ($\pi_{ret}$) predicts two adaptive control variables for each task:
     • $R$ (Diffusion Depth): Controls the breadth of graph exploration.
     • $W$ (Utility-Utility Trade-off): Controls the balance between semantic similarity and historical utility.
   • Semantic Seeding: The system first identifies top-$M$ seed nodes via cosine similarity to the task embedding.
   • Graph Diffusion: Using Personalized PageRank, the system expands from the seed set across the graph. The restart probability is controlled by $R$, allowing the retrieval to either stay local or propagate further to find structurally related experiences.
   • Utility-Aware Ranking: Candidates are re-ranked using an Upper Confidence Bound (UCB) score that combines semantic relevance with an estimated utility score ($u_v$). This encourages exploiting high-value experiences while exploring under-tested nodes.

3. Learning from Utility Feedback:

   • The system employs a utility-grounded reward mechanism. For each task, the frozen executor is evaluated twice: once with retrieved experiences ($s_{with}$) and once without ($s_{without}$).
   • The reward is calculated as $r = (s_{with} - s_{without}) + \eta s_{with}$, measuring the marginal gain of retrieval while ensuring absolute task quality.
   • Copilot Optimization: The retrieval copilot is optimized using Proximal Policy Optimization (PPO) to maximize this reward, learning to retrieve experiences that genuinely improve execution rather than just matching semantics.
   • Online Graph Evolution: Retrieved nodes are updated with new utility statistics based on the reward. New trajectories are summarized and inserted into the graph, while low-utility nodes are pruned, allowing the memory to self-evolve.

Key Contributions

• Model-Agnostic Design: ExpGraph is the first framework to jointly support graph-structured experience, graph diffusion, utility-aware ranking, and adaptive retrieval for frozen executors. It does not require retraining the underlying LLM.
• Relational Memory: Unlike flat memory systems, ExpGraph organizes experiences as a graph, enabling the discovery of transferable strategies and failure patterns that are not immediate semantic neighbors.
• Adaptive Retrieval Policy: The introduction of a retrieval copilot that dynamically controls diffusion depth and the relevance-utility trade-off allows the system to adapt to both task complexity and executor capabilities.
• Utility-Grounded Learning: By optimizing retrieval based on actual downstream performance gains (rather than just similarity), the system learns to distinguish between merely relevant and truly useful experiences.

Experimental Results

The authors evaluated ExpGraph on ExpSuite, covering single-turn static tasks (Question Answering, Mathematical Reasoning, Code Generation) and multi-step agentic environments (ALFWorld, AppWorld).

• Performance Gains:
  • Static Tasks: ExpGraph improved the average score over the strongest baseline by 12.2% with a smaller executor (Llama-3.2-3B) and 4.7% with a larger executor (Llama-3.1-8B).
  • Agentic Environments: Gains were more pronounced, improving the weighted average score by 21.4% (small executor) and 12.7% (large executor) over the strongest baseline.
  • Efficiency: ExpGraph reduced average interaction steps by 12.7% and 21.6% compared to the most efficient competing baselines in agentic settings.
• Generalization: The framework demonstrated strong zero-shot transfer capabilities. Experience components learned from smaller executors transferred effectively to larger ones, and components from non-reasoning executors generalized well to reasoning-capable models.
• Ablation Studies: Removing any key component (graph structure, diffusion, utility ranking, or similarity filtering) consistently degraded performance, confirming that the joint design is essential for effective experience reuse.

Significance and Claims

The paper claims that ExpGraph provides a practical and executor-agnostic path for LLM agents to learn from experience without retraining the underlying executor. The authors emphasize that:

1. Experience Reuse is Critical for Weaker Executors: The relative gains are significantly higher for smaller, less capable models, suggesting that external experience can compensate for weaker built-in reasoning or planning abilities.
2. Value in Long-Horizon Tasks: The benefits are most pronounced in agentic environments requiring long-horizon decision-making, where prior trajectories can directly guide actions and reduce unnecessary exploration.
3. Decoupling Learning from Execution: By treating the executor as a replaceable task solver and learning how to provide context via an external system, ExpGraph addresses the inflexibility of fine-tuning-based approaches in a rapidly evolving LLM landscape.

The authors conclude that modeling relations among experiences and learning utility-aware adaptive retrieval are essential for enabling LLM agents to accumulate and transfer task knowledge effectively, particularly in settings where the executor cannot be updated.