STRATA: Self-Maintaining Structured Experience Graphs for Self-Evolving Language Agents
STRATA tackles the problem of scalable, self-maintaining memory for test-time self-evolving LLM agents. Instead of a flat, monotonic pool of episode summaries, it organizes experience as a typed three-layer directed graph of atomic skills, task workflows, and meta-frameworks, maintained by five mechanisms including multi-dimensional similarity, adaptive reflection thresholds, community detection, pressure-triggered garbage collection with articulation-point protection, and contrast edges that warn against directionally opposite experiences. The authors show that this structured memory attains the best average accuracy across four interactive benchmarks while simultaneously using the lowest latency, fewest environment steps, and fewer injected memory lines than seven memory-augmented baselines.
The paper presents a carefully motivated and mechanism-rich agent memory architecture. Its central claim—that typed, layered, actively maintained graphs outperform flat memories—is broadly supported by ablations and aggregate results, though limited by three-seed variance, uncontrolled scaling confounds, and evaluation on only one model family. The authors are commendably transparent about which gaps do not survive seed noise. "Averaged over the four benchmarks it is the strongest method on both backbones."
The mechanism design and diagnostic analyses are the clearest strengths. The ablation in Appendix B isolates the tag term as the dominant signal, and the contrast-edge ablation in Appendix F shows concentrated gains exactly where directionally opposite operators exist, providing strong mechanistic evidence for the claimed repair. Efficiency claims are also robust: STRATA records the lowest latency and fewest output tokens among all memory-augmented methods. "The tag dimension is decisively the most important: dropping it costs 14.4 average points, more than the other three dimensions combined."
First, the argument that single-level memory suffers a scale failure relies on benchmark-level comparisons that entangle task count, difficulty, and distribution shift; the authors acknowledge this plainly, yet the narrative still leans on A-Mem’s rank drop without a controlled scaling experiment. Second, the contrast-edge mechanism depends on a hand-specified lexicon of opposite operators, which limits generalization beyond the evaluated domains. Third, the headline ScienceWorld gain of 78.7 to 96.7 is explicitly noted as not statistically separable from baselines due to only 23 tasks and high variance, despite its prominence in the abstract. "We therefore do not claim a ScienceWorld win from Table 1; the ScienceWorld evidence we do rely on is the within-method contrast ablation of the next sections, where the same seeds are compared under a single mechanism change."
The evidence strongly supports the tag term’s role and the existence of negative transfer, but cross-method comparisons are fair in protocol yet uneven in architectural capacity. For example, A-Mem is a linked note network, MemEvolve meta-evolves its own memory architecture, and STRATA treats them as interchangeable memory baselines despite differing design goals. The per-category breakdowns show gains concentrated in low-frequency task families, consistent with abstraction, but also suggest many high-frequency categories are near ceiling for all methods. "on Flash a method that ranks first at 168 tasks ranks seventh at 812."
Reproducibility is mixed: the full hyperparameter table, mathematical formulations, and example memory nodes are disclosed, but no code, prompts, or environment snapshots are released. Independent reproduction is further blocked by reliance on an unspecified local sentence-embedding model and frozen DeepSeek-V4 checkpoints. The typed reflection and community detection stages depend on LLM calls whose prompts, temperatures, and parsing logic are not provided, which matter more for replication than the numerical weights. "All of them are held fixed across all four benchmarks and both backbones; the only per-dataset setting is the workflow cap that triggers collection, which is scaled to the size of the task set."
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.