🤖 AI

CoEvo-Mem: Co-Evolving Retrieval Policy and Memory Bank for LLM Agents

CoEvo-Mem is a closed-loop framework that simultaneously optimizes retrieval policies and memory bank evolution through alternating updates and trajectory-conditioned feedback, achieving state-of-the-art performance across diverse benchmarks by addressing the fundamental interdependence between memory access and refinement in long-term LLM agents.

Original authors: Bowen Ye, Yongchao Xu, Zhijian Li, Xiang Yin, Junkai Ma, Wenzhao Li

Published 2026-08-04

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Bowen Ye, Yongchao Xu, Zhijian Li, Xiang Yin, Junkai Ma, Wenzhao Li

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

Imagine you are teaching a brilliant but forgetful robot to play a complex video game. The robot has a massive brain (a Large Language Model) that knows how to talk and think, but it can only hold a tiny amount of information in its "working memory" at once—like trying to solve a puzzle while only seeing the last three pieces. To play well over a long time, the robot needs a library of past experiences to look up. This is where Retrieval-Augmented Generation (RAG) comes in: it's like the robot asking a librarian, "Hey, have we seen a puzzle like this before?"

But here's the tricky part: the robot needs two things to work perfectly. First, it needs a Librarian (the retrieval policy) who is really good at finding the right old notes for the current question. Second, it needs a Note-Taker (the memory bank) who is good at organizing those notes, deciding which ones are actually useful, and updating them as the game gets harder. For a long time, scientists tried to make the Librarian smarter while keeping the Note-Taker static, or they made the Note-Taker better while keeping the Librarian the same. But what if the Librarian needs to know how the notes are organized to find them, and the Note-Taker needs to know what the Librarian is looking for to organize them better? They need to learn together, in a loop.

This is exactly what the paper CoEvo-Mem explores. The authors propose a system where the "Librarian" and the "Note-Taker" evolve together, constantly teaching each other how to do their jobs better. They tested this idea on seven different types of challenging tasks, ranging from writing computer code and solving science questions to controlling a computer's operating system. The results suggest that when these two parts learn in sync, the robot becomes significantly better at solving long, complex problems than when they learn separately.

The Problem: The Broken Feedback Loop

Imagine you are studying for a huge history exam. You have a stack of flashcards (your memory) and a study guide (your retrieval policy). If your study guide is bad, you might pick the wrong flashcards to review. But if your flashcards are messy and disorganized, even a good study guide might struggle to find the right one.

In the world of AI agents, existing methods usually fix one side of the problem while ignoring the other. Some methods try to make the AI better at asking for memories (retrieval), while others try to make the AI better at storing and organizing memories (evolution). The authors of this paper argue that this separation is a mistake. They point out a "fundamental feedback loop" that was being ignored:

Retrieval decides what gets used: If the AI picks the wrong memories, those memories don't get any "credit" for helping (or hurting) the task.
Memory updates change the future: If the AI updates its memories based on what happened, the way those memories are organized changes, which makes it harder or easier to find them next time.

If you only fix the retrieval method without letting the memory change, or vice versa, you miss out on the chance for them to get better together. It's like trying to tune a guitar while the strings are constantly changing thickness; you can't get a perfect sound unless you adjust both at the same time.

The Solution: CoEvo-Mem

The authors built a framework called CoEvo-Mem (Co-Evolving Memory). Think of it as a dance between two partners: the Router (the Librarian) and the Memory Bank (the Note-Taker).

Here is how the dance works:

1. The Frozen Brain and the Smart Router
The main "brain" of the AI (the Large Language Model) stays frozen—it doesn't learn anything new. Instead, the system uses a tiny, lightweight "Router" to decide how to ask for help.

When a question comes in, the frozen brain suggests a few ways to rewrite the question (some focusing on the meaning, others on specific keywords).
The Router then learns to tweak these suggestions based on whether the AI got the answer right or wrong. It's like a coach whispering, "Try asking it this way next time," based on the game's outcome.

2. The Memory Bank as a Living Map
The memories aren't just a list of notes; they are a Relational Graph. Imagine a map where every memory is a city, and the roads between them show how they are related.

Dense roads connect memories that mean the same thing (semantic).
Sparse roads connect memories that share specific words or names (lexical).
Time roads connect memories that happened in a sequence (temporal).

When the AI solves a task, it doesn't just save the answer. It updates the "value" of the cities it visited. If a memory helped the AI win, that city gets a higher score. If it helped, but only a little, the score goes up a bit. Crucially, this credit doesn't just stay with that one memory; it travels along the roads to neighboring cities, helping the whole neighborhood get smarter.

3. The Alternating Dance (The Secret Sauce)
You might think, "Why not update the Router and the Memory at the exact same time?" The authors found that this causes chaos. If both change at once, it's like trying to learn to ride a bike while the bike is also changing its shape. The system gets confused and unstable.

Instead, CoEvo-Mem uses an alternating schedule:

Phase 1: The Memory Bank is frozen (locked in place). The Router practices finding the best memories using this fixed map.
Phase 2: The Router is frozen (locked in place). The Memory Bank updates its organization and values based on what the Router just found.
They switch back and forth. This allows each partner to learn from the current state of the other without the confusion of both changing simultaneously.

What They Found

The team tested CoEvo-Mem on seven very different challenges:

Operating System Interaction: Controlling a computer to do tasks.
Code Generation: Writing working computer programs.
Multimodal Reasoning: Solving puzzles that involve both text and images.
Scientific Questions: Answering hard questions about physics, chemistry, and biology.
Function Calling: Teaching the AI to use tools and APIs correctly.
Long-Term Conversation: Remembering details from long chats.

In every single one of these tests, CoEvo-Mem performed better than the best existing methods.

On the GPQA Diamond (hard science questions), it improved the score by 7.50 percentage points over the strongest baseline.
On LiveCodeBench (coding), it improved by 3.81 percentage points.
On Long-term Conversational Memory (LoCoMo), it reached a score of 81.71, beating the next best method by nearly 5 points.

The authors also ran "ablation studies" (experiments where they removed parts of the system) to prove why it worked.

When they removed the query rewriting (the part that changes how the question is asked), performance dropped significantly.
When they removed the memory evolution (the part that updates the graph and values), performance also dropped, especially on complex tasks like coding and science.
When they tried to update both the Router and Memory at the same time (instead of alternating), the system performed worse than the alternating method.

The Takeaway

The paper suggests that for AI agents to truly master long-term tasks, we can't just build a better search engine or a better database. We have to build a system where the search engine and the database learn to adapt to each other. By letting the "Librarian" and the "Note-Taker" take turns learning while the other stays still, CoEvo-Mem creates a stable, improving loop that helps AI agents remember better, think clearer, and solve harder problems.

The authors are careful to note that while the results are strong across these seven benchmarks, this is a specific framework for co-evolution. They don't claim it solves every problem in AI, but they do show that this specific way of linking retrieval and memory is a powerful step forward for building agents that can learn and adapt over time.

Technical Summary: CoEvo-Mem

Problem Statement

Long-term Large Language Model (LLM) agents face a critical challenge: as interactions accumulate across tasks and sessions, retaining all historical information within a single context window becomes inefficient and often infeasible. Effective agents require memory mechanisms to preserve useful experience and retrieve it when relevant. However, existing approaches typically optimize memory access (retrieval) and memory evolution (storage/refinement) in isolation.

Retrieval-focused methods (e.g., RAG, query reformulation) optimize how to access a fixed or independently maintained collection but do not adapt the collection itself based on usage.
Memory-centric methods (e.g., value-based evolution, structured graphs) improve how experiences are updated or organized but often rely on predefined or separately optimized retrieval policies.

This separation overlooks a fundamental feedback loop: retrieval decisions determine which memories receive usage signals and credit, while updates to the memory bank (values and relations) reshape the landscape for future retrieval. Optimizing one component against a permanently fixed counterpart leads to a mismatch with the evolving state of the other.

Methodology: CoEvo-Mem

CoEvo-Mem is a closed-loop framework designed to co-evolve the retrieval policy and the memory bank through interaction feedback. The framework maintains a frozen answering LLM ( $F_{ans}$ ) and focuses on learning a lightweight retrieval policy and a persistent, typed relational memory graph.

1. Core Components

Frozen LLM & Route-Specialized Query Rewriting (SR-QR): For each query, a frozen LLM generates route-specific query rewrites (dense for semantic intent, sparse for exact lexical cues) and an initial routing prior.
Prior-Guided Residual Router: A trainable, lightweight module learns a residual correction to the LLM's initial routing prior. It produces fusion weights ( $w_t$ ) that control a hybrid retriever.
Q-Weighted Hybrid Retriever: This retriever integrates dense similarity, sparse matching (BM25), and learned memory utility. It uses Weighted Reciprocal Rank Fusion (WRRF) to combine rankings from different rewrites and routes, weighted by the router's output.
Typed Relational Memory Graph: Memories are stored as nodes in a graph containing content, descriptions, keywords, and temporal metadata. Edges encode semantic (dense), lexical (sparse), and temporal relations. Each node holds a learned utility value ( $Q_t(m)$ ) representing its discounted downstream retrieval utility.

2. The Co-Evolution Mechanism

The framework addresses the non-stationarity caused by the mutual dependence of retrieval and memory through alternating training phases:

Router Phase: The memory graph is fixed (read-only). The router is updated using a reward-driven policy gradient (score-function estimator) based on task outcomes. The router explores continuous mixtures of dense and sparse retrieval routes.
Memory Phase: The router is frozen (using its deterministic mean policy). The memory graph evolves sequentially. New memories are distilled from interaction trajectories, and utility values are updated via a Temporal Difference (TD) style mechanism.
- Utility Update: $Q_t(m)$ is updated based on the immediate task reward, the attributed utility of the memory, and a bootstrap term from newly distilled experiences.
- Relational Credit Propagation: Feedback propagates to related memories (semantic, lexical, or temporal neighbors) based on path strength and relation-specific attenuation factors.

3. Training Objective

The system optimizes the expected task reward $J_{tr}$ over trajectories induced by the router, the evolving graph, and the phase schedule. By alternating updates, each component adapts to the latest state of the other without the instability of simultaneous joint optimization.

Key Contributions

Identification of a Feedback Loop: The paper identifies and formalizes the underexplored feedback loop between retrieval and memory evolution in long-term LLM agents, where retrieval determines credit assignment and memory updates reshape future retrieval.
CoEvo-Mem Framework: A novel framework that coordinates retrieval policy adaptation with relational memory evolution while keeping the answering LLM frozen. Key features include:
- Route-specialized query rewriting and residual adaptation of an LLM routing prior.
- Memory updates that propagate feedback across semantic, lexical, and temporal relations.
- An alternating training schedule to mitigate non-stationarity.
Empirical Validation: Extensive experiments across seven diverse benchmarks (spanning six evaluation settings, as BFCL includes both non-thinking and thinking configurations) demonstrate that CoEvo-Mem achieves state-of-the-art performance, validating the importance of joint optimization.

Experimental Results

CoEvo-Mem was evaluated on seven benchmarks spanning operating-system interaction (LLAB), code generation (LiveCodeBench), multimodal reasoning (MMMU Pro), scientific QA (GPQA Diamond), function calling (BFCL), and long-term conversational memory (LoCoMo, LongMemEval).

Performance: CoEvo-Mem achieved the highest mean score in all six evaluated settings (LLAB, LiveCodeBench, MMMU Pro, GPQA Diamond, BFCL non-thinking, and BFCL thinking). Compared to the strongest baseline in each row, the average improvement was 3.72 percentage points, with individual gains ranging from 1.06 to 7.50 points.
- Notable gains were observed in GPQA Diamond (+7.50) and BFCL non-thinking (+6.33).
Ablation Studies:
- Removing SR-QR (route-specific rewriting) reduced performance by 4.24 points on average, highlighting the importance of query reformulation.
- Removing Memory Evolution (relational updates) reduced performance by 4.80 points, confirming that typed relations and value propagation improve memory reuse beyond independent item-level updates.
- Alternating Co-Adaptation outperformed both simultaneous updates and two-stage training, demonstrating the necessity of the alternating schedule to manage non-stationarity.
Transferability: In fixed-memory protocols (LoCoMo-MC, LongMemEval-MC), CoEvo-Mem achieved strong results, and when the answering backbone was switched to GPT-4 without retraining the memory system, performance increased significantly, indicating the learned retrieval interface transfers well across backbones.

Significance and Claims

The paper claims that CoEvo-Mem advances the state of the art by demonstrating that retrieval access and memory evolution are mutually reinforcing and must be optimized jointly. The authors argue that:

Joint Adaptation is Critical: Isolating retrieval or memory optimization prevents the fixed counterpart from adapting to the changes induced by the other, limiting overall agent performance.
Structured Feedback Loops: By explicitly modeling the feedback loop where retrieval determines credit assignment and memory updates guide future retrieval, agents can sustain improvements over long horizons.
Generalizability: The framework's success across heterogeneous tasks (from code generation to scientific reasoning) and memory types suggests that co-adapting retrieval routing and memory evolution is a generalizable strategy for long-term LLM agents.

The authors conclude that future work should explore multi-agent memory sharing and theoretical guarantees for coupled retrieval-memory optimization, but the current work establishes the empirical foundation for this co-evolutionary approach.