Technical Summary: ERSkill - Evolving for Skill-Guided Adaptive Memory Retrieval

Problem Statement

While Large Language Model (LLM) agents increasingly rely on long-term memory for persistent interactions, the retrieval mechanisms governing this memory are typically static. Existing self-evolving methods focus on refining memory content (e.g., distilling reasoning traces or updating memory items) but often rely on predefined, fixed retrieval strategies (such as dense retrieval or BM25) at query time. This static approach limits performance on heterogeneous memory queries, which demand diverse evidence construction strategies. For instance, a query requiring a specific event retrieval differs fundamentally from one requiring causal reasoning across multiple events. The central problem addressed is how an LLM agent can evolve and learn to compose complex retrieval actions so that its retrieval behavior adapts to the varying information demands of different queries.

Methodology: ERSkill Framework

The authors propose ERSkill (Evolving Retrieval Skill), a retrieval-centric framework that models agent memory access as skill-guided evidence construction. The system consists of three core components:

1. Structured Memory and Primitive Library

ERSkill compiles interaction histories into a structured memory store $M(D) = (A, I, G)$, comprising atom-level records ($A$), indexes ($I$), and graphs ($G$). Instead of treating memory as a passive store, ERSkill exposes it through a fixed library of retrieval primitives ($P$). These primitives act as state transitions ($p: (q, s, M(D)) \to s'$) and include:

• Search Primitives: entity_search (entity-based), lexical_search (BM25), and dense_search (semantic similarity).
• Expansion Primitives: temporal_focus_expand, similarity_expand, and relation_expand to grow evidence via graph edges.
• Process Primitives: llm_process for query rewriting, filtering, and dynamic control.

2. Retrieval Skills and Router

A retrieval skill ($\kappa$) is defined as an executable program composed of a sequence of primitives. This abstraction allows retrieval behaviors to be reusable, interpretable, and refinable.

• Skill Router: A trained model $R_\theta$ dynamically matches a query $q$ to the optimal skill $\kappa$ from the current set $K$. The router encodes both the query and skill descriptions into vector representations to compute compatibility scores, selecting the skill that best constructs the required evidence view for answer generation.

3. Skill-Router Co-Evolution

To overcome the limitations of a static skill set, ERSkill employs a co-evolution procedure that jointly updates the skill set and the router. This process is guided by two key mechanisms:

• Experience Trie: An efficient data structure that records explored primitive paths. It allows the skill generator to reuse past rollout experiences, detect duplicate candidates, and avoid redundant exploration.
• Double-Frontier Mechanism: This decouples capability expansion from deployment stability:
  • Capability Frontier ($C_t$): Maintains a compact set of skills with the best "oracle-side" value (i.e., the best possible performance if the optimal skill were always chosen). It tracks the maximum retrieval capability discovered.
  • Deploy Frontier ($B_t$): Maintains the skill set actually used at inference time. It contains only skills that the router can select reliably.
  • Evolution Process: New skill candidates are generated by editing paths from the capability frontier. Candidates are evaluated on training and validation batches. The capability frontier is updated to preserve oracle performance, while the deploy frontier is updated only if the new set improves routed performance or maintains compactness within a tolerance threshold. This ensures that the system can explore new capabilities without destabilizing the deployed agent.

Key Contributions

1. Retrieval-Centric Framework: The paper introduces a paradigm shift where memory access is treated as query-adaptive evidence construction rather than a fixed retrieval strategy.
2. ERSkill Architecture: A skill-guided framework that co-evolves retrieval skills and the router using an experience trie and a double-frontier design to balance exploration and stability.
3. Empirical Performance: Extensive experiments demonstrate that ERSkill substantially outperforms strong non-evolving and self-evolving baselines.

Experimental Results

The authors evaluated ERSkill on three agent memory benchmarks: LoCoMo, LongMemEval, and PerLTQA, using two backbone LLMs: Qwen3-Next-80B-A3B-Instruct and GPT-5.4-nano.

• Performance Gains: ERSkill achieved the best overall average across F1, BLEU-1, and LLM-as-a-Judge scores.
  • With Qwen3-Next-80B-A3B-Instruct, it improved the overall average by 31.3% over the strongest baseline.
  • With GPT-5.4-nano, it improved the overall average by 28.1%.
• Transferability: Skills trained on LoCoMo transferred effectively to LongMemEval without additional training, maintaining superior performance.
• Cost-Performance Trade-off: ERSkill demonstrated a favorable trade-off, achieving the highest L-J scores while remaining lightweight in both memory construction tokens and inference tokens compared to other LLM-based memory construction methods.
• Ablation Studies: Removing key components (skill evolution, the router, the double frontier, or the experience trie) resulted in significant performance drops, confirming the necessity of each design element.

Significance and Claims

The paper claims that ERSkill highlights retrieval-side evolution as a promising direction for long-term LLM agents. The authors argue that while memory content and reasoning guidance have become increasingly adaptive, retrieval behavior itself has remained largely predefined. By modeling retrieval as a skill-guided, evolvable process, ERSkill enables agents to construct tailored evidence for heterogeneous queries.

The significance lies in the demonstration that:

1. Adaptive Retrieval is Critical: Updating memory summaries or reasoning traces alone is insufficient if the retrieval mechanism remains fixed.
2. Stable Evolution is Possible: The double-frontier mechanism allows for the expansion of retrieval capabilities while ensuring that the deployed agent remains stable and reliable.
3. Efficiency: The framework achieves high performance without incurring prohibitive inference costs, suggesting that targeted evidence construction is more effective than simply retrieving more content.

The authors maintain a modest stance, noting that the current system relies on a fixed primitive library and rollout-based evaluation, which incurs training costs. They identify future work directions such as improving efficiency with cheaper evaluators, supporting primitive discovery, and extending adaptive retrieval to planning and tool use.