STRATA: Self-Maintaining Structured Experience Graphs for Self-Evolving Language Agents

Guanhua Zhu; Hanwen Li; Zhi Wei; Mengnan Du; Chenxi Yuan

cs.AIOct 14, 2026

STRATA: Self-Maintaining Structured Experience Graphs for Self-Evolving Language Agents

Authors: Guanhua Zhu, Hanwen Li, Zhi Wei, Mengnan Du, Chenxi Yuan

Organizations: Department of Informatics, New Jersey Institute of Technology · Department of Computer Science, New Jersey Institute of Technology · School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen

Abstract

Large language model (LLM) agents can self-evolve at test time by accumulating experience: retrieving relevant memories before acting and writing new lessons back afterwards. Yet most are single-level: trajectories, distilled workflows and reasoning items all land in one undifferentiated pool indexed by embedding similarity, with no typed abstraction hierarchy. They never forget or deduplicate, and are prone to negative transfer, where a superficially similar but directionally opposite experience is recalled and its concrete steps are copied verbatim, actively harming the agent. We introduce STRATA, a structured, outcome-grounded, self-maintaining memory that organizes experience into a three-layer graph of atomic skills and code snippets, task workflows and generalized meta-frameworks, connected by typed edges. STRATA maintains itself through five mechanisms sharing one similarity geometry: a multi-dimensional similarity that scores retrieval by operation and target; a typed reflector crystallizing procedures from successes and pitfalls from failures; community detection that induces meta-frameworks; pressure-triggered garbage collection with articulation-point protection; and contrast edges that flag confusable, direction-opposite experiences. Across four interactive benchmarks (AppWorld, WebArena, ALFWorld, ScienceWorld), two frozen backbones and seven baselines, STRATA attains the best average score while simultaneously using the lowest latency and fewest environment steps of any memory-augmented method, and 44% fewer lines of injected memory than the most context-hungry baseline. We isolate two failure modes of prior memories: single-level memory degrades sharply as the task set grows, and single-level concrete memories suffer catastrophic negative transfer, which contrast edges repair, lifting ScienceWorld from 78.7 to 96.7 within the same system.

Figures & tables

Figure 1: Agent memories are asked to serve tool calling, experience reuse and role-based decomposition at once (left). Existing memories are either flat lists or generic graphs, which mix content of different granularity, dilute retrieval as they grow, and are never maintained (right). STRATA unifies the three in a single three-layer self-evolving graph (middle).

Figure 2: Overview of STRATA. Middle: the three-layer memory, comprising a tool layer (code, skills, agent roles), an experience layer (workflows and their call edges; similarity links belong to the derived graph $W$ and are not stored), and an abstraction layer (meta-workflows over the tag vocabulary; tags are node attributes, not nodes). Right: one episode, in which the main agent retrieves a subgraph, acts, and a master reflector dispatches to typed sub-reflectors. Left: graph evolution, where community detection induces meta nodes and pressure-triggered collection deletes stale leaves while protecting bridge nodes.

		AppWorld Test-Normal		AppWorld Test-Challenge		WebArena	ALFWorld	ScienceWorld
Backbone	Method	TGC $\uparrow$	SGC $\uparrow$	TGC $\uparrow$	SGC $\uparrow$	SR $\uparrow$	Score $\uparrow$	Score $\uparrow$
DeepSeek-V4-Flash	No-Memory	62.8 ${\scriptstyle\pm\,2.9}$	42.1 ${\scriptstyle\pm\,3.3}$	39.8 ${\scriptstyle\pm\,2.1}$	21.4 ${\scriptstyle\pm\,1.9}$	24.7 ${\scriptstyle\pm\,1.4}$	76.8 ${\scriptstyle\pm\,3.3}$	75.7 ${\scriptstyle\pm\,8.7}$
	Flat-Memory	66.4 ${\scriptstyle\pm\,3.7}$	48.7 ${\scriptstyle\pm\,4.3}$	43.8 ${\scriptstyle\pm\,2.7}$	27.9 ${\scriptstyle\pm\,2.7}$	30.7 ${\scriptstyle\pm\,2.0}$	82.4 ${\scriptstyle\pm\,3.8}$	80.4 ${\scriptstyle\pm\,10.4}$
	ReasoningBank	69.6 ${\scriptstyle\pm\,3.3}$	55.1 ${\scriptstyle\pm\,3.9}$	48.2 ${\scriptstyle\pm\,2.5}$	34.7 ${\scriptstyle\pm\,2.6}$	32.9 ${\scriptstyle\pm\,1.8}$	91.0 ${\scriptstyle\pm\,2.6}$	87.9 ${\scriptstyle\pm\,7.8}$
	Hermes	30.4 ${\scriptstyle\pm\,4.4}$	20.7 ${\scriptstyle\pm\,4.3}$	23.9 ${\scriptstyle\pm\,2.8}$	15.4 ${\scriptstyle\pm\,2.6}$	31.6 ${\scriptstyle\pm\,2.4}$	84.5 ${\scriptstyle\pm\,4.4}$	48.3 ${\scriptstyle\pm\,15.0}$
	A-Mem	75.2 ${\scriptstyle\pm\,3.2}$	65.7 ${\scriptstyle\pm\,3.9}$	49.6 ${\scriptstyle\pm\,2.6}$	37.5 ${\scriptstyle\pm\,2.7}$	28.4 ${\scriptstyle\pm\,1.8}$	93.4 ${\scriptstyle\pm\,2.4}$	88.2 ${\scriptstyle\pm\,8.1}$

Table 1: Main results: mean

\pm

sample standard deviation over three seeds. Bold is best, underlined second best within each backbone. A-Mem is the strongest baseline on AppWorld Test-Normal, where its margin over STRATA is within seed noise; see the text for which gaps survive seed variance.

Figure 3: Per-category scores on DeepSeek-V4-Pro. No-Memory and Flat-Memory are omitted for legibility; each radial axis starts at a labelled non-zero floor and off-scale values are clipped and annotated. Gains concentrate on long-tail categories. Per-backbone versions for all four benchmarks are in Appendix H.

Variant	AW-TN	AW-TC	WebA.	ALF.	SciW.	Avg
Full STRATA	71.7	51.9	45.6	98.6	96.7	72.9
w/o tag term	55.0	38.8	35.7	89.1	80.3	59.8
w/o contrast edges	69.7	50.1	43.8	89.5	78.7	66.4
w/o adaptive threshold	64.9	46.5	40.1	94.2	89.3	67.0
w/o meta layer	66.8	47.7	40.8	95.1	90.8	68.2
w/o pressure GC	70.6	50.8	41.0	96.6	94.4	70.7

Table 2: Component ablation on DeepSeek-V4-Pro (AppWorld columns are the TGC/SGC mean). Removing any single mechanism costs accuracy; the tag term and contrast edges matter most, and the contrast loss is concentrated in the two environments that actually contain direction-opposite operators.

Method	Lat.	In tok	Out tok	Steps	Mem lines
	(s)	/task	/task	/task	/task
No-Memory	52.4	17,850	6,020	13.2	0
Flat-Memory	64.8	45,120	6,137	12.8	35.6
ReasoningBank	65.1	35,472	5,813	12.3	16.1
Hermes	60.2	21,964	5,856	13.4	7.8
A-Mem	62.5	38,960	5,480	12.0	41.9

Table 3: Cost per task on DeepSeek-V4-Pro. Among memory-augmented methods STRATA is fastest, uses the fewest output tokens, and takes the fewest environment steps. Mem lines counts lines of retrieved memory in the prompt, not tokens.

Figure 7: AppWorld per-application scores for both splits and both backbones.

LLM Agent Self-Improvement

Large language model agent self-improvement studies how agents use experience and feedback to improve their behavior, tools, and workflows.

See all 276 papers

Jun 2, 2026

DELTAMEM: Incremental Experience Memory for LLM Agents via Residual Trees

Large Language Model (LLM)-based agents increasingly rely on memory to learn from experiences over continual interactions. However, storing experiences as independent, flat units leads to substantial redundancy and retrieval conflicts, as similar episodes repeat overlapping content and subtle scene variations cause retrieved memories to offer contradictory guidance. To address this, we introduce residual experience, positing that newly acquired experience is often an incremental variation of existing knowledge. We propose DeltaMem, a framework that organizes experience memory into two independent residual trees, one storing goal-conditioned task experience as reusable skills and another for scene-level environment knowledge. Each tree uses a root node for generalized base experiences and incremental delta nodes for subsequent variations, allowing related experiences to share a common foundation without duplication. For retrieval, a failure-penalized similarity scan locates the best match, reconstructing the full experience via root-to-match chain composition. An autonomous consolidation mechanism distills high-frequency paths into new root nodes, enabling the trees to self-organize from general heuristics to specialized variants. Experiments across diverse interactive environments show that DeltaMem consistently outperforms existing baselines. To facilitate future research, we release the code at https://github.com/import-myself/DeltaMem.

Haoran Tan, Zeyu Zhang, Zhicheng Cao +2

Gaoling School of Artificial, Renmin University of China, Beijing, China · Beijing Key Laboratory of Research on Large Models and Intelligent Governance · Engineering Research Center of Next-Generation Intelligent Search and Recommendation, MOE +1

Continual Learning for LLM Agents LLM Agent Memory Agent Skill Learning Memory Consolidation

Ask PDF

Aug 17, 2026

HyperSkill: Self-Evolving LLM Agents via Hypergraph-Structured Skill Memory

As agentic tasks grow in complexity, LLM agents increasingly rely on experiential memory to reuse procedural knowledge across tasks. Effective memory design must jointly address what to store, how memory is structured and retrieved, and how memory evolves. Existing systems tackle each only partially: they store trajectories, insights, or workflows as isolated entries, discarding compositional relationships among subtasks and reusable skills; retrieve by flat embedding similarity that ignores relational signals; and maintain memory without leveraging its relational structure. We propose HyperSkill, a hypergraph-based memory framework that jointly improves all three. HyperSkill represents memory as a hypergraph with two node types, subtask steps and reusable skills, where each hyperedge links the subtasks and skills from a single trajectory. Dual-path retrieval queries both subtask and trajectory levels, ranking skills by co-occurrence across retrieved trajectories. Periodic structure-informed maintenance prunes low-utility nodes and merges redundant skills via quality-weighted propagation. Across xBench, GAIA, and WebWalkerQA with GPT-4o and Qwen3-30B-A3B, HyperSkill outperforms ten memory baselines, yielding gains of up to +11.51 on GAIA and +11.18 on WebWalkerQA.

Ruiyao Xu, Tiankai Yang, Wei-Chieh Huang

Northwestern University · University of Southern California · University of Illinois at Chicago

Agent Memory LLM Agent Memory Agent Memory Management LLM Agent Skill Retrieval Graph-Based Agent Memory

Ask PDF

Oct 19, 2026

More Memory, Worse Agents: Error Reproduction and Anti-Persistence in LLM Agents

LLM agents can improve across tasks without updating model parameters by storing experience from their own executions in external memory and reusing it to guide later decisions. A central design question is whether to retain only observed trajectories and outcomes or also the rules, summaries, and skills inferred from them. Retaining these abstractions allows agents to reuse strategies without repeatedly deriving them from raw trajectories. However, errors in stored abstractions can propagate to subsequent decisions through retrieval and reuse. They can also shape execution trajectories, which then become the basis for new abstractions that reproduce the original errors. We term this feedback mechanism error reproduction: errors are regenerated through a cycle of abstraction, execution, and re-abstraction, extending their persistence beyond direct reuse of the original faulty knowledge. We propose Anti-Persistence, a memory design that accumulates trajectories and outcomes while reconstructing task-specific guidance on demand. An adaptive selector uses prior outcomes to decide whether and how to synthesize guidance, which is discarded after execution. This prevents its direct reuse as a stored object, although indirect feedback through retained trajectories remains possible. Across different benchmarks and backbones, Anti-Persistence achieves higher overall held-out success and the lowest average LLM-call cost among the evaluated memory designs. These results support separating experience accumulation from abstraction persistence in memorybased self-improvement.

Ruhan Wang, Kishan Panaganti, Dongruo Zhou

Indiana University · Tencent HY

Memory-Augmented Language Model Agents LLM Agent Self-Improvement Memory Management for LLM Agents

Ask PDF

Abstract

LLM Agent Self-Improvement

Explore similar work

DELTAMEM: Incremental Experience Memory for LLM Agents via Residual Trees

HyperSkill: Self-Evolving LLM Agents via Hypergraph-Structured Skill Memory

More Memory, Worse Agents: Error Reproduction and Anti-Persistence in LLM Agents