💬 NLP

EvoArena: Tracking Memory Evolution for Robust LLM Agents in Dynamic Environments

This paper introduces EvoArena, a benchmark suite for evaluating LLM agents in dynamic environments, and proposes EvoMem, a patch-based memory paradigm that tracks environmental evolution to significantly improve agent performance on both evolving and standard tasks.

Original authors: Jundong Xu, Qingchuan Li, Jiaying Wu, Yihuai Lan, Shuyue Stella Li, Huichi Zhou, Bowen Jiang, Lei Wang, Jun Wang, Anh Tuan Luu, Caiming Xiong, Hae Won Park, Bryan Hooi, Zhiyuan Hu

Published 2026-06-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jundong Xu, Qingchuan Li, Jiaying Wu, Yihuai Lan, Shuyue Stella Li, Huichi Zhou, Bowen Jiang, Lei Wang, Jun Wang, Anh Tuan Luu, Caiming Xiong, Hae Won Park, Bryan Hooi, Zhiyuan Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Static Snapshot" Trap

Imagine you hire a very smart personal assistant (an AI agent) to manage your life. You give them a list of rules: "I drink coffee on Mondays," "My office is on the 3rd floor," and "I use the blue pen."

In most current tests, researchers give this assistant a static snapshot of your life. They ask, "What do you drink on Monday?" The assistant looks at the snapshot and says, "Coffee." Perfect!

But in the real world, life isn't a snapshot; it's a movie.

On Tuesday, you get a new job on the 5th floor.
On Wednesday, you decide you hate coffee and switch to tea.
On Thursday, your office building changes its security rules, so you can't use the blue pen anymore.

The paper argues that current AI assistants are terrible at handling this "movie" version of reality. If you ask them on Friday, "What do you drink on Monday?" they might still say "Coffee" because they only remember the latest thing they were told, or they get confused because their memory got overwritten. They fail to realize that the rules changed over time.

The Solution: EvoArena (The "Time-Travel" Test)

To fix this, the authors built a new testing ground called EvoArena. Think of this as a video game level where the rules of the game change every time you play a round, but the goal stays the same.

They created three specific "worlds" to test the AI:

The Terminal World: Imagine a computer command line where the file paths, passwords, and software versions change every time you try to run a script. The goal (e.g., "upload this file") stays the same, but the how changes.
The Code World: Imagine a software project where the codebase is constantly being updated. A fix you made yesterday might break a feature you need to build today. The AI has to know which old code is still valid and which is obsolete.
The Social World: Imagine a long conversation where a user's preferences slowly shift. "I used to like spicy food, then I got a stomach ache, now I like mild food, but only on weekends." The AI has to track this history to give the right recommendation.

The Result: When they tested top-tier AI agents on EvoArena, they struggled. They only got about 40% of the tasks right. They kept trying to use old rules for new situations, like trying to open a modern door with an ancient key.

The Innovation: EvoMem (The "Git for Memory")

The authors realized the problem was how the AI stored its memory. Most AIs work like a whiteboard: you write something new, and it erases the old stuff. If you write "I like tea" over "I like coffee," the coffee is gone forever.

They proposed a new memory system called EvoMem.

The Analogy: Git for Your Brain
Think of EvoMem like Git, a tool programmers use to track changes in code.

Normal Memory (The Whiteboard): You write "I like tea." The old "coffee" note is erased.
EvoMem (The Git Log): You don't erase "coffee." Instead, you add a new note: "Update: User switched from coffee to tea on Tuesday because of a stomach ache."

EvoMem keeps a patch history. It records:

What changed? (Coffee $\to$ Tea)
Why did it change? (Stomach ache)
When was the old rule valid? (Before Tuesday)

When the AI needs to answer a question, it doesn't just look at the "current" state. It looks at the history of changes. If the question is about "Monday morning" (before the stomach ache), EvoMem helps the AI remember, "Ah, on Monday, the rule was still coffee!"

How It Works in Practice

The paper tested this new memory system on the same difficult EvoArena tests.

The "Step" Test: Can the AI solve one specific task in the changing environment?
- Result: EvoMem helped slightly (about 1.5% better).
The "Chain" Test: Can the AI solve a whole sequence of related tasks without messing up? This is the hard part.
- Result: EvoMem helped a lot! It improved the success rate by 3.7% on average.

Why the "Chain" test matters:
Imagine you are building a house.

Step 1: You lay the foundation.
Step 2: You realize the ground is wet, so you change the foundation plan.
Step 3: You build the walls.

If your memory is a whiteboard, by Step 3, you might forget that the ground was wet and try to use the original foundation plan, causing the house to collapse.
If your memory is EvoMem, you have a log that says, "We changed the foundation in Step 2 because of wet ground." When you get to Step 3, you remember to keep the new foundation.

The Key Takeaways

Current AIs are "Amnesiacs": They are great at static tasks but terrible at tracking how the world changes over time. They often forget that a rule they learned yesterday might not apply today.
EvoArena is the Stress Test: It proves that real-world deployment requires agents to handle evolving environments, not just static snapshots.
EvoMem is the Fix: By treating memory as a history of updates (patches) rather than a single current state, agents can reason better. They know what changed, why it changed, and when the old rules still apply.
It Works Everywhere: This improvement wasn't just for the new tests; it also made the AIs slightly better at standard, non-changing tasks (like GAIA and LoCoMo), suggesting that having a "history log" helps the AI think more clearly in general.

In short, the paper says: To build a reliable AI assistant for the real world, we need to stop treating its memory like a whiteboard and start treating it like a version-controlled history book.

Technical Summary: EvoArena and EvoMem

Problem Statement

Large Language Model (LLM) agents have demonstrated strong performance on benchmarks involving web navigation, software engineering, and tool use. However, these evaluations predominantly assume static environments, where interfaces, rules, code states, and task distributions remain fixed once the benchmark is constructed. In real-world deployment, agents operate in dynamic environments where conditions evolve persistently over time (e.g., API updates, workflow changes, codebase refactoring, and shifting user preferences).

Current agent systems often fail in these settings due to state collapse. Most memory-based agents maintain a single latest state (e.g., a retrieved memory bank or episodic store). While effective when new information safely supersedes old information, this design becomes brittle when different environment versions require different behaviors. For instance, a workflow permission update might overwrite an earlier rule that remains valid for a specific legacy release or organization. Consequently, agents lose the context explaining when previous behaviors were valid, leading to the reuse of obsolete procedures. There is a critical gap in evaluating and improving agent robustness under persistent environment evolution.

Methodology

1. EvoArena: A Benchmark Suite for Persistent Evolution

To address the lack of dynamic evaluation, the authors introduce EvoArena, a benchmark suite that models environment changes as sequences of progressive updates across three domains:

Terminal-Bench-Evo (Executable Workflow Evolution): Converts static terminal tasks into versioned chains. The underlying objective remains constant, but operational constraints evolve across versions, including changes to I/O paths, CLI/API interfaces, dependencies, workspace layouts, and security policies. Each chain consists of 4–5 versions where later versions inherit the realized environment of earlier ones.
SWE-Chain-Evo (Software Evolution): Organizes software repositories into chronological chains of milestones. Agents must solve localized development objectives (e.g., bug fixes, feature additions) where the codebase accumulates changes from previous milestones. The evaluation tests whether agents can implement new requirements without regressing previously established behaviors (measured via Pass-to-Pass tests).
PersonaMem-Evo (Social Intelligence Evolution): Extends personalization benchmarks to model evolving user preferences. Instead of static profiles, agents interact with long-horizon conversations where user preferences shift over time (e.g., changing drink preferences based on new experiences). The benchmark includes questions requiring agents to infer current preferences from dispersed historical evidence, distinguishing between outdated and valid states.

EvoArena evaluates agents using two metrics:

Step Accuracy: Success on individual evolved tasks.
Chain Accuracy: Success on a sequence of linked tasks, requiring the agent to maintain reliability across the entire evolution history without error.

2. EvoMem: A Patch-Based Memory Paradigm

To improve agent performance in these dynamic settings, the authors propose EvoMem, a lightweight, git-like memory paradigm. Unlike standard memory systems that consolidate updates into a single state, EvoMem treats memory updates as an append-only patch history.

Patch Recording: When an agent updates its memory, EvoMem captures non-additive changes (revisions, overwrites, reinterpretations) as explicit patches. Each patch $p_t$ $p_{t}$ records:
- $\tau_t$ : Temporal metadata (turn, session).
- $C^-_t, C^+_t$ : Memory content before and after the update.
- $r_t$ : The rationale for the update.
- $z_t$ : A semantic summary of the change.
- $e_t$ : Supporting evidence (triggering context, feedback).
Patch-Augmented Retrieval: At inference time, the agent retrieves the latest memory state by default. However, if a query depends on overwritten states, temporal changes, or version-specific behaviors, the system selectively retrieves relevant historical patches. This allows the agent to reason about why a state changed and when a prior state was valid.

EvoMem is instantiated across different agent architectures (Terminus2, OpenHands, A-Mem, Memento-Skill) by defining specific schemas for what constitutes a "patch" in that context (e.g., strategy shifts in terminal tasks, code logic revisions in software engineering, or preference updates in conversations).

Key Contributions

EvoArena Benchmark: A comprehensive suite evaluating agents under persistent environment evolution across terminal workflows, software repositories, and social preferences. It introduces Chain Accuracy as a stricter metric for sustained reliability.
EvoMem Paradigm: A memory architecture that preserves traces of environmental evolution. By recording memory updates as structured patches with rationales and evidence, it enables agents to reason over version-dependent states rather than relying solely on the latest consolidated state.
Empirical Analysis: Demonstrations that existing agents struggle significantly in evolving environments and that EvoMem consistently improves robustness, evidence retention, and chain-level performance.

Experimental Results

Performance on EvoArena

Experiments across multiple backbone models (GPT-5.5, Gemini-3.1-Pro, Kimi-K2.6, etc.) and agent frameworks reveal:

Baseline Struggles: Current agents achieve moderate step-level accuracy (averaging ~43.6% on Terminal-Bench-Evo, ~27.9% on SWE-Chain-Evo, and ~47.3% on PersonaMem-Evo) but suffer significant drops in Chain Accuracy (e.g., dropping to ~21.5% on Terminal-Bench-Evo). This indicates that solving isolated steps does not guarantee reliability across evolving chains.
EvoMem Improvements: Integrating EvoMem consistently improves performance:
- Step Level: Average gains of +2.4% (Terminal), +0.4% (SWE), and +1.7% (Persona).
- Chain Level: Larger gains are observed at the chain level, with average improvements of +6.1% (Terminal), +2.1% (SWE), and +3.2% (Persona). This suggests EvoMem is particularly effective for maintaining consistency across dependent task sequences.

Generalization to Standard Benchmarks

EvoMem also improves performance on standard, non-evolving benchmarks:

GAIA: +6.1% average improvement.
LoCoMo: +4.8% average improvement.
This suggests that preserving update history as retrievable evidence benefits agents even in static settings, likely by improving long-horizon reasoning and reducing hallucination of past states.

Mechanistic Analysis

Operationalization: In Terminal-Bench-Evo, gains are highest when agents not only retrieve patch examples but also operationalize them—incorporating the transition information into their reasoning and executed commands.
Regression Reduction: In SWE-Chain-Evo, EvoMem significantly reduces Pass-to-Pass failures (regressions), indicating better preservation of historical code constraints.
Evidence Preservation: In PersonaMem-Evo, EvoMem improves row-level evidence capture, meaning it better preserves the complete set of preference evidence required for downstream reasoning, particularly for temporal trajectory and multi-pattern synthesis questions.

Significance and Claims

The paper claims that reliable agent deployment in real-world settings requires treating memory not as a static snapshot but as an evolving history of grounded updates.

Bridging the Gap: EvoArena addresses the disconnect between static benchmark evaluations and the dynamic nature of real-world deployment, where APIs, workflows, and user needs continually change.
Version-Aware Reasoning: The results highlight that agents must retain the latest memory while being able to recover relevant prior states and reason over why updates occurred.
Design Implication: The authors posit that robust agent memory systems should preserve update histories as retrievable evidence. This approach allows agents to distinguish between current knowledge and previously valid knowledge, preventing the application of obsolete behaviors.

The work concludes that modeling evolution in both evaluation (via EvoArena) and memory architecture (via EvoMem) is essential for building agents that can adapt reliably to changing conditions.