MemQ: Integrating Q-Learning into Self-Evolving Memory Agents over Provenance DAGs

# MemQ: Integrating Q-Learning into Self-Evolving Memory Agents over Provenance DAGs
Source: [https://arxiv.org/html/2605.08374](https://arxiv.org/html/2605.08374)
Junwei Liao1,2Haoting Shi1Ruiwen Zhou3Jiaqian Wang4Shengtao Zhang1 Wei Zhang1Weinan Zhang1,2Ying Wen1,2Zhiyu Li6Feiyu Xiong6 Bo Tang5,6Muning Wen1 1Shanghai Jiao Tong University2Shanghai Innovation Institute 3National University of Singapore4Xidian University 5University of Science and Technology of China6MemTensor \(Shanghai\) Technology Co\., Ltd\. jwliao\.ai@sjtu\.edu\.cn tangb@memtensor\.cn muningwen@sjtu\.edu\.cn

###### Abstract

Episodic memory allows LLM agents to accumulate and retrieve experience, but current methods treat each memory independently, i\.e\., evaluating retrieval quality in isolation without accounting for the dependency chains through which memories enable the creation of future memories\. We introduceMemQ, which applies TD\(λ\\lambda\) eligibility traces to memory Q\-values, propagating credit backward through a*provenance DAG*that records which memories were retrieved when each new memory was created\. Credit weight decays as\(γ​λ\)d\(\\gamma\\lambda\)^\{d\}with DAG depthdd, replacing temporal distance with structural proximity\. We formalize the setting as an*Exogenous\-Context MDP*, whose factored transition decouples the exogenous task stream from the endogenous memory store\. Across six benchmarks, spanning OS interaction, function calling, code generation, multimodal reasoning, embodied reasoning, and expert\-level QA, MemQ achieves the highest success rate on all six in generalization evaluation and runtime learning, with gains largest on multi\-step tasks that produce deep and relevant provenance chains \(up to \+5\.7 pp\) and smallest on single\-step classification \(\+0\.77 pp\) where single\-step updates already suffice\. We further study howγ\\gammaandλ\\lambdainteract with the EC\-MDP structure, providing principled guidance for parameter selection and future research\. Code will be available soon\.

## 1Introduction

Large language models \(LLMs\) deployed as agents cannot adapt to novel tasks or changing environments without costly weight updates\. A growing line of work addresses this by equipping agents with external*episodic memory*stores that accumulate experience—recording successes, failures, and discovered strategies—and retrieving relevant memories to guide future behavior\(park2023generative;packer2023memgpt;shinn2023reflexion;zhao2024expel;wang2023voyager;zhong2023memorybank;sumers2023cognitive\)\. A common limitation is that retrieval relies on fixed heuristic scoring—typically embedding similarity—with no learning signal from task outcomes to adjust which memories are considered valuable\.

More recently, RL\-based methods have begun to learn which memories are worth retrieving\. One line learns a*parametric*policy over memory operations\(yan2025memoryr1;zhang2025memact;ma2026finemem;shen2026membuilder;zhang2026retroagent\); a complementary line attaches non\-parametric value estimates directly to individual memory entries\(pritzel2017neural;guu2020realm\)\. Most closely related, MemRL\(zhang2026memrl\)attaches Q\-values to memory entries in a vector store and updates them via single\-step exponential moving average \(EMA\), formulating retrieval as a contextual bandit withγ=0\\gamma=0\. This provides the first mechanism for a memory\-augmented agent to learn retrieval from experience—but it leaves a critical gap\.

The gap is a*credit assignment*problem\. Memories are not independent: when memories are retrieved for a task, the outcome produces a new memory, which may itself be retrieved for future tasks, creating chains such asma→mb→mc→rm\_\{a\}\\to m\_\{b\}\\to m\_\{c\}\\to r\. A memorymam\_\{a\}that contributed*indirectly*to a downstream memorymcm\_\{c\}and the ultimate rewardrr, by enabling the creation of the intermediate memorymbm\_\{b\}, receives no feedback from downstream successes under single\-step updates\. Its Q\-value stagnates whilembm\_\{b\}accumulates credit\. This is precisely the setting where eligibility traces excel: when rewards are sparse and causal chains are long, propagating credit across multiple steps yields faster, more accurate value estimation than single\-step updates\(sutton2018reinforcement;sutton1988learning;singh1996reinforcement;schulman2016gae;espeholt2018impala;watkins1989learning;peng1996incremental;vanseijen2014true;munos2016safe\)\. Yet no prior work has applied trace\-based credit assignment to episodic memory management\.

We introduceMemQ, a method that closes this gap by propagating credit through the*provenance DAG*, a directed acyclic graph recording which memories were retrieved when each new memory was created\. We formalize the setting as an*Exogenous\-Context MDP*, which factors the state into an exogenous task stream \(beyond the agent’s control\) and an endogenous memory store \(fully determined by the agent’s retrieval actions and the frozen LLM’s responses\)\. Within this framework, MemQ extends single\-step Q\-value updates with TD\(λ\\lambda\) eligibility traces that flow backward through the provenance DAG, crediting ancestor memories proportionally to their structural distance from the outcome\. The key insight is that DAG depth replaces temporal step count as the notion of proximity\.

![Refer to caption](https://arxiv.org/html/2605.08374v1/x1.png)Figure 1:High\-level and conceptual illustration of MemQ\.Our contributions are as follows:

1. 1\.We identify the*multi\-step credit assignment problem*in episodic memory and formalize the setting as an*Exogenous\-Context MDP*, whose factored transition decouples exogenous task dynamics from endogenous memory evolution, motivating value decomposition over individual memories\.
2. 2\.We developMemQ, a provenance\-based credit propagation mechanism that applies TD\(λ\\lambda\) eligibility traces through the memory construction DAG, replacing temporal distance with structural depth, the first provenance\-based credit assignment method for episodic memory valuation\.
3. 3\.Across six benchmarks, MemQ achieves the highest success rate on all six in runtime learning and five of six in transfer evaluation, with gains largest on multi\-step tasks that produce deep and relevant provenance chains \(up to \+5\.7 pp\) and smallest on single\-step classification \(\+0\.77 pp\), confirming that the improvement is structural\.

## 2Related Works

### 2\.1Self\-Evolving Memory Agents

Early memory\-augmented agents rely on fixed heuristic retrieval—embedding similarity or hand\-crafted scores\(park2023generative;packer2023memgpt;shinn2023reflexion;zhao2024expel;wang2023voyager;zhong2023memorybank;kynoch2023recallm;sumers2023cognitive\)—with no learning signal from task outcomes\. More recent work makes memory*self\-evolving*along two paradigms\.*Parametric approaches*\(yan2025memoryr1;zhang2025memact;ma2026finemem;shen2026membuilder;zhang2026retroagent;zhou2025mem1;yue2026memt\)learn network parameters for memory operations, requiring gradient\-based optimization\.*Non\-parametric approaches*avoid weight updates, attaching value estimates or update rules directly to memory entries: REMEMBERER\(zhang2023rememberer\)equips a frozen LLM with experience memory updated via RL without weight modification; MemRL\(zhang2026memrl\)further attaches Q\-values with single\-step EMA \(γ=0\\gamma=0\); Memento\(zhou2025memento\)learns a case\-selection policy with memory rewriting; other systems employ rule\-based curation\(mem0\), cognitive self\-organization\(nan2025nemori\), meta\-evolution\(zhang2025memevolve\), learnable skills\(zhang2025memskill\), online experience weighting\(zhang2026liveevo\), Hebbian graphs\(zhu2026helamem\), utility\-based pruning\(cao2025reme\), or procedural memory distillation\(fang2026mempexploringagentprocedural\)\. None propagates credit*across*memory creation events—each memory’s value is updated in isolation\. MemQ follows the non\-parametric paradigm but introduces multi\-step credit propagation through the provenance DAG via TD\(λ\\lambda\) eligibility traces, a signal invisible to existing methods\.

### 2\.2Reinforcement Learning for Memory

RL for memory spans from episodic control methods\(blundell2016model;pritzel2017neural;lin2018episodic\)and differentiable memory architectures\(graves2014neural;guu2020realm;schaul2016prioritized\)to recent LLM\-agent\-specific methods\. The parametric methods in §[2\.1](https://arxiv.org/html/2605.08374#S2.SS1)train neural policies for memory operations\. On the non\-parametric side, MemRL uses TD\(0\) withγ=0\\gamma=0, and Memento 2\(wang2025memento2\)optimizes retrieval via supervised learning within the Reflected MDP formalism—absorbing the frozen LLM into environment dynamics so that the retrieval policy becomes the sole decision variable and the memory store a valid MDP state\. Other work applies RL to memory\-augmented retrieval\(yuan2025memsearcher;ouyang2025reasoningbank;wei2025evomemory\), focusing on what to store and when to retrieve rather than credit assignment\.

To our knowledge, no prior work applies TD\(λ\\lambda\)\-style eligibility traces to episodic memory management\. Classical trace theory\(sutton1988learning;singh1996reinforcement;sutton2018reinforcement;peng1996incremental;vanseijen2014true;schulman2016gae\)operates over temporal steps; MemQ adapts it to a structural domain where traces propagate through the provenance DAG and DAG depth replaces temporal step count\.

## 3Problem Formulation

We consider a frozen LLM agent tackling tasks from an unknown distribution\. Unable to learn via gradient updates, it relies on a continually growing episodic memory store\. The core challenge is assigning credit across multi\-step memory chains: because early retrievals can indirectly enable future success, a principled solution must account for the downstream impact of every retrieval on future rewards, rather than just crediting the final step\.

##### Exogenous\-Context MDP\.

A key structural feature of this setting is that the state factors into two components with fundamentally different dynamics: the*exogenous*task stream, which the agent cannot influence, and the*endogenous*memory store, which evolves as a direct consequence of the agent’s retrieval actions\. We make this factorization explicit by defining the*Exogenous\-Context MDP*\(EC\-MDP\)\.

###### Definition 1\(Exogenous\-Context MDP\)\.

The EC\-MDP is a tuple⟨𝒮,ℳ,𝒜,Pexo,Pendo,R,γ⟩\\langle\\mathcal\{S\},\\mathcal\{M\},\\mathcal\{A\},P\_\{\\mathrm\{exo\}\},P\_\{\\mathrm\{endo\}\},R,\\gamma\\ranglewhere𝒮\\mathcal\{S\}is theexogenous state space\(the set of all tasks\) with evolution governed byPexo​\(st\+1\)=ρ​\(st\+1\)P\_\{\\mathrm\{exo\}\}\(s\_\{t\+1\}\)=\\rho\(s\_\{t\+1\}\), independent of the agent’s actions or memory;ℳ⊆2ℳ∞\\mathcal\{M\}\\subseteq 2^\{\\mathcal\{M\}\_\{\\infty\}\}111Intuitively, since the memory bank is a collection of past interaction experiences, any valid memory stateℳ\\mathcal\{M\}is a finite subset of the universe of all theoretically possible experiencesℳ∞\\mathcal\{M\}\_\{\\infty\}\.is theendogenous state space\(the memory store\), whose evolution is fully determined by the current task, memory, and retrieval action;𝒜​\(ℳ\)=\{A⊆ℳ:\|A\|≤k\}\\mathcal\{A\}\(\\mathcal\{M\}\)=\\\{A\\subseteq\\mathcal\{M\}:\|A\|\\leq k\\\}is theaction spaceof retrieval subsets of size at mostkk;Pendo​\(ℳt\+1∣st,ℳt,At\)P\_\{\\mathrm\{endo\}\}\(\\mathcal\{M\}\_\{t\+1\}\\mid s\_\{t\},\\mathcal\{M\}\_\{t\},A\_\{t\}\)is theendogenous transition kernel, absorbing the frozen LLM:

Pendo​\(ℳt\+1∣st,ℳt,At\)=∑τπLLM​\(τ∣st,At\)⋅𝟏​\[ℳt\+1=ℳt∪\{Build​\(st,τ\)\}\];P\_\{\\mathrm\{endo\}\}\(\\mathcal\{M\}\_\{t\+1\}\\mid s\_\{t\},\\mathcal\{M\}\_\{t\},A\_\{t\}\)=\\sum\_\{\\tau\}\\pi\_\{\\mathrm\{LLM\}\}\(\\tau\\mid s\_\{t\},A\_\{t\}\)\\cdot\\mathbf\{1\}\\\!\\bigl\[\\mathcal\{M\}\_\{t\+1\}=\\mathcal\{M\}\_\{t\}\\cup\\\{\\mathrm\{Build\}\(s\_\{t\},\\tau\)\\\}\\bigr\];R​\(st,At\)=𝔼τ∼πLLM\(⋅∣st,At\)​\[r​\(τ\)\]R\(s\_\{t\},A\_\{t\}\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\_\{\\mathrm\{LLM\}\}\(\\cdot\\mid s\_\{t\},A\_\{t\}\)\}\[r\(\\tau\)\]is thereward; andγ∈\[0,1\]\\gamma\\in\[0,1\]is the discount factor\. A retrieval policyπret​\(A∣s,ℳ\)\\pi\_\{\\mathrm\{ret\}\}\(A\\mid s,\\mathcal\{M\}\)serves as the agent’s*sole optimized policy*: whileπLLM\\pi\_\{\\mathrm\{LLM\}\}remains frozen,πret\\pi\_\{\\mathrm\{ret\}\}maps the current task and memory store to a distribution over retrieval actions\.

![Refer to caption](https://arxiv.org/html/2605.08374v1/x2.png)Figure 2:The EC\-MDP\. The state factors into an exogenous task streamst∼ρs\_\{t\}\\sim\\rhoand an endogenous memory storeℳt\\mathcal\{M\}\_\{t\}\. The retrieval policyπret\\pi\_\{\\mathrm\{ret\}\}selects memoriesmtm\_\{t\}, the frozen agentπLLM\\pi\_\{\\mathrm\{LLM\}\}produces a trajectoryτt\\tau\_\{t\}and receives rewardrtr\_\{t\}, and the memory is built and stored\.The defining feature of the EC\-MDP is that the joint transition kernel factors:

P​\(st\+1,ℳt\+1∣st,ℳt,At\)=Pexo​\(st\+1\)⋅Pendo​\(ℳt\+1∣st,ℳt,At\)\.P\(s\_\{t\+1\},\\mathcal\{M\}\_\{t\+1\}\\mid s\_\{t\},\\mathcal\{M\}\_\{t\},A\_\{t\}\)=P\_\{\\mathrm\{exo\}\}\(s\_\{t\+1\}\)\\cdot P\_\{\\mathrm\{endo\}\}\(\\mathcal\{M\}\_\{t\+1\}\\mid s\_\{t\},\\mathcal\{M\}\_\{t\},A\_\{t\}\)\.\(1\)Unlike the Reflected MDP ofwang2025memento2—which couples task dynamics with agent actions—this factorization explicitly decouples the next taskst\+1s\_\{t\+1\}from the current state and action\. The EC\-MDP recovers the Reflected MDP as a special case when the exogenous dynamics are i\.i\.d\. and the endogenous transition uses a frozen LLM\. Monotonic memory growth \(ℳt\+1⊇ℳt\\mathcal\{M\}\_\{t\+1\}\\supseteq\\mathcal\{M\}\_\{t\}\) ensures the process satisfies the Markov property\. Furthermore, the factorization guarantees that the stochastic rewardrt=r​\(τt\)r\_\{t\}=r\(\\tau\_\{t\}\)and newly constructed memorymnew=Build​\(st,τt\)m\_\{\\mathrm\{new\}\}=\\mathrm\{Build\}\(s\_\{t\},\\tau\_\{t\}\)depend solely on the current task and the retrieved setAtA\_\{t\}, establishing conditional independence from unretrieved memories:

P​\(rt,mnew∣st,ℳt,At\)=P​\(rt,mnew∣st,At\)\.P\(r\_\{t\},m\_\{\\mathrm\{new\}\}\\mid s\_\{t\},\\mathcal\{M\}\_\{t\},A\_\{t\}\)=P\(r\_\{t\},m\_\{\\mathrm\{new\}\}\\mid s\_\{t\},A\_\{t\}\)\.\(2\)

##### Value functions and learning objective\.

The*state\-value*captures the long\-term value of the memory store via the expected cumulative discounted reward:

Vπret​\(ℳt\)=𝔼sk∼ρ,Ak∼πret,τk∼πLLM​\[∑k=0∞γk​r​\(τt\+k\)\|ℳt\]\.V^\{\\pi\_\{\\mathrm\{ret\}\}\}\(\\mathcal\{M\}\_\{t\}\)=\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}s\_\{k\}\\sim\\rho,\\,A\_\{k\}\\sim\\pi\_\{\\mathrm\{ret\}\},\\,\\tau\_\{k\}\\sim\\pi\_\{\\mathrm\{LLM\}\}\\end\{subarray\}\}\\\!\\biggl\[\\sum\_\{k=0\}^\{\\infty\}\\gamma^\{k\}r\(\\tau\_\{t\+k\}\)\\,\\bigg\|\\,\\mathcal\{M\}\_\{t\}\\biggr\]\.The*action\-value*for retrieving setAAisQ​\(s,A;ℳ\)=𝔼τ​\[r​\(τ\)\+γ​Vπret​\(ℳ′\)\|s,A,ℳ\]Q\(s,A;\\mathcal\{M\}\)=\\mathbb\{E\}\_\{\\tau\}\\\!\\bigl\[r\(\\tau\)\+\\gamma\\,V^\{\\pi\_\{\\mathrm\{ret\}\}\}\(\\mathcal\{M\}^\{\\prime\}\)\\,\\big\|\\,s,A,\\mathcal\{M\}\\bigr\], whereℳ′=ℳ∪\{mnew​\(τ\)\}\\mathcal\{M\}^\{\\prime\}=\\mathcal\{M\}\\cup\\\{m\_\{\\mathrm\{new\}\}\(\\tau\)\\\}\. The learning objective is thus to maximize the initial state value:

maxπret⁡Vπret​\(ℳ0\)\.\\max\_\{\\pi\_\{\\mathrm\{ret\}\}\}V^\{\\pi\_\{\\mathrm\{ret\}\}\}\(\\mathcal\{M\}\_\{0\}\)\.To bypass the intractable combinatorial action space2ℳ2^\{\\mathcal\{M\}\}without updating the LLM’s weights, we project this MDP onto the memory provenance DAG\. Assuming retrieved memories contribute independently, we approximate the set\-level value via a first\-order decomposition:

Q\(s,A;ℳ\)≈1\|A\|∑mi∈AQ\(mi\),A∼πret\(⋅∣s,ℳ\)\.Q\(s,A;\\mathcal\{M\}\)\\approx\\frac\{1\}\{\|A\|\}\\sum\_\{m\_\{i\}\\in A\}Q\(m\_\{i\}\),\\quad A\\sim\\pi\_\{\\mathrm\{ret\}\}\(\\cdot\\mid s,\\mathcal\{M\}\)\.\(3\)Here, each scalarQ​\(m\)∈ℝQ\(m\)\\in\\mathbb\{R\}captures a*provenance value*: its marginal contribution to future rewards along causal generation chains\. Consequently,Q​\(m\)Q\(m\)satisfies a structural Bellman equation over the DAG:Q​\(m\)=𝔼s,A∋m,τ​\[r​\(τ\)\+γ​Q​\(mnew\)\|m∈A\]Q\(m\)=\\mathbb\{E\}\_\{s,A\\ni m,\\tau\}\\\!\\bigl\[r\(\\tau\)\+\\gamma\\,Q\(m\_\{\\mathrm\{new\}\}\)\\,\\big\|\\,m\\in A\\bigr\], withmnew=Build​\(s,τ\)m\_\{\\mathrm\{new\}\}=\\mathrm\{Build\}\(s,\\tau\)\. By structurally replacing the temporal bootstrapγ​Vπret​\(ℳ′\)\\gamma V^\{\\pi\_\{\\mathrm\{ret\}\}\}\(\\mathcal\{M\}^\{\\prime\}\)with the downstream memory’s valueγ​Q​\(mnew\)\\gamma Q\(m\_\{\\mathrm\{new\}\}\), this framework enables efficient, per\-memory credit propagation\.

## 4Method

![Refer to caption](https://arxiv.org/html/2605.08374v1/x3.png)Figure 3:MemQ Framework Overview\. The continuous learning loop features three stages: Retrieve: Following locality filtering, anϵ\\epsilon\-greedy policy selects memories via learnedQQ\-values to contextualize the LLM\. Build: Task trajectories are distilled into new memories \(via proceduralization or reflection\) and integrated into the provenance DAG, linked to their parents\. Update: TD errors backpropagate through the DAG to assign multi\-step credit and update theQQ\-values of all contributing ancestors\.Section[3](https://arxiv.org/html/2605.08374#S3)formulated retrieval as an EC\-MDP whose action\-value decomposes over individual memories \(Eq\.[3](https://arxiv.org/html/2605.08374#S3.E3)\)\. MemQ is a method for learning per\-memory Q\-values in this setting\. Its key idea is that when a retrieval setAAis used for a task and produces a new memorymnewm\_\{\\mathrm\{new\}\}, we recordparents​\(mnew\)=A\\mathrm\{parents\}\(m\_\{\\mathrm\{new\}\}\)=A, inducing a*provenance DAG*, i\.e\., a directed acyclic graph over memory entries whose edges indicate “was retrieved for a task that produced the next memory\.” This DAG provides the structural substrate for multi\-step credit assignment: instead of updating only the directly retrieved memories, MemQ propagates TD\(λ\\lambda\) eligibility traces backward through the DAG, crediting ancestor memories proportionally to their structural depth from the outcome\. We describe MemQ in three parts: the Q\-augmented memory store, a two\-phase retrieval policy, and credit propagation via the provenance DAG\.

Algorithm 1MemQ1:Task set

𝒟\\mathcal\{D\}, memory store

ℳ\\mathcal\{M\}, frozen agent

πLLM\\pi\_\{\\mathrm\{LLM\}\}
2:Hyperparameters:

α,γ,λ,ε,k,θsim,ws,wq,ϵclip\\alpha,\\gamma,\\lambda,\\varepsilon,k,\\theta\_\{\\mathrm\{sim\}\},w\_\{s\},w\_\{q\},\\epsilon\_\{\\mathrm\{clip\}\}
3:Initialize DAG

←∅\\leftarrow\\emptyset;

Δ​Qi←0\\Delta Q\_\{i\}\\leftarrow 0;

Ni←0N\_\{i\}\\leftarrow 0for all

mim\_\{i\}
4:foreach epoch

ℓ=1,2,…\\ell=1,2,\\ldotsdo

5:Shuffle

𝒟\\mathcal\{D\}into mini\-batches

ℬ1,…,ℬL\\mathcal\{B\}\_\{1\},\\ldots,\\mathcal\{B\}\_\{L\}of size Batch size

6:

𝒯←∅\\mathcal\{T\}\\leftarrow\\emptyset⊳\\trianglerighttransition buffer

7:foreach mini\-batch

ℬb=\{s1,…,sB\}\\mathcal\{B\}\_\{b\}=\\\{s\_\{1\},\\ldots,s\_\{B\}\\\}do

8:// Trajectory sampling

9:foreach task

sj∈ℬbs\_\{j\}\\in\\mathcal\{B\}\_\{b\}do⊳\\trianglerightin parallel

10:

𝒞j←\{m∈ℳ:sim​\(ϕ​\(sj\),𝐞m\)≥θsim\}\\mathcal\{C\}\_\{j\}\\leftarrow\\\{m\\in\\mathcal\{M\}:\\mathrm\{sim\}\(\\phi\(s\_\{j\}\),\\mathbf\{e\}\_\{m\}\)\\geq\\theta\_\{\\mathrm\{sim\}\}\\\}⊳\\trianglerightlocality filter

11:

score​\(m\)←ws⋅sim​\(sj,m\)\+wq⋅Q​\(m\)\\mathrm\{score\}\(m\)\\leftarrow w\_\{s\}\\cdot\\mathrm\{sim\}\(s\_\{j\},m\)\+w\_\{q\}\\cdot Q\(m\)for all

m∈𝒞jm\\in\\mathcal\{C\}\_\{j\}⊳\\trianglerightQ\-guided scoring

12:

Aj←ε​\-greedy top\-​kA\_\{j\}\\leftarrow\\varepsilon\\text\{\-greedy top\-\}kfrom

𝒞j\\mathcal\{C\}\_\{j\}
13:foreach step

t=1,2,…t=1,2,\\ldotsdo⊳\\trianglerightagent\-environment interaction

14:

at←πLLM​\(sj,Aj,h<t\)a\_\{t\}\\leftarrow\\pi\_\{\\mathrm\{LLM\}\}\(s\_\{j\},A\_\{j\},h\_\{<t\}\);

ot←Environment​\(at\)o\_\{t\}\\leftarrow\\mathrm\{Environment\}\(a\_\{t\}\)
15:endfor

16:

Rj←Environment\.reward​\(\)R\_\{j\}\\leftarrow\\mathrm\{Environment\}\.\\mathrm\{reward\}\(\)
17:endfor

18:

c​\(mnew\)←Build​\(sj,τj\)c\(m\_\{\\mathrm\{new\}\}\)\\leftarrow\\mathrm\{Build\}\(s\_\{j\},\\tau\_\{j\}\);

Q​\(mnew\)←1\|Aj\|​∑mi∈AjQ​\(mi\)Q\(m\_\{\\mathrm\{new\}\}\)\\leftarrow\\frac\{1\}\{\|A\_\{j\}\|\}\\sum\_\{m\_\{i\}\\in A\_\{j\}\}Q\(m\_\{i\}\);

ℳ←ℳ∪\{mnew\}\\mathcal\{M\}\\leftarrow\\mathcal\{M\}\\cup\\\{m\_\{\\mathrm\{new\}\}\\\}⊳\\trianglerightbuild new memories

19:

𝒯←𝒯∪\{\(Aj,mnew,j,Rj\)\}j=1B\\mathcal\{T\}\\leftarrow\\mathcal\{T\}\\cup\\\{\(A\_\{j\},m\_\{\\mathrm\{new\},j\},R\_\{j\}\)\\\}\_\{j=1\}^\{B\}⊳\\trianglerightstore transitions

20:endfor

21:Record

parents​\(mnew,j\)←Aj\\mathrm\{parents\}\(m\_\{\\mathrm\{new\},j\}\)\\leftarrow A\_\{j\}for each transition in

𝒯\\mathcal\{T\}⊳\\trianglerightconstruct DAG

22:// Value update using MemQ

23:Compute

δ​\(m0,j\)←Rj\+γ​Q​\(mnew,j\)−Q​\(m0\)\\delta\(m\_\{0\},j\)\\leftarrow R\_\{j\}\+\\gamma\\,Q\(m\_\{\\mathrm\{new\},j\}\)\-Q\(m\_\{0\}\)for each

m0∈Ajm\_\{0\}\\in A\_\{j\}⊳\\trianglerightEq\.[5](https://arxiv.org/html/2605.08374#S4.E5)

24:BFS backward from each root

m0m\_\{0\}, up to depth

DD:⊳\\trianglerighttraverse DAG

25:foreach ancestor

mmat depth

ddfrom

m0m\_\{0\}do

26:

Δ​Q​\(m\)←Δ​Q​\(m\)\+α⋅\(γ​λ\)d⋅δ​\(m0,j\)\\Delta Q\(m\)\\leftarrow\\Delta Q\(m\)\+\\alpha\\cdot\(\\gamma\\lambda\)^\{d\}\\cdot\\delta\(m\_\{0\},j\);

Nm←Nm\+1N\_\{m\}\\leftarrow N\_\{m\}\+1⊳\\trianglerightEq\.[6](https://arxiv.org/html/2605.08374#S4.E6)

27:endfor

28:

Q​\(mi\)←Q​\(mi\)\+clip​\(Δ​QiNi,−ϵclip,ϵclip\)Q\(m\_\{i\}\)\\leftarrow Q\(m\_\{i\}\)\+\\mathrm\{clip\}\\\!\\left\(\\frac\{\\Delta Q\_\{i\}\}\{N\_\{i\}\},\\,\-\\epsilon\_\{\\mathrm\{clip\}\},\\,\\epsilon\_\{\\mathrm\{clip\}\}\\right\)for all

mim\_\{i\};

Δ​Qi←0\\Delta Q\_\{i\}\\leftarrow 0;

Ni←0N\_\{i\}\\leftarrow 0⊳\\trianglerightflush

29:endfor

### 4\.1Procedural Construction of Q\-Augmented Memory

Letℳ=\{m1,m2,…,mN\}\\mathcal\{M\}=\\\{m\_\{1\},m\_\{2\},\\ldots,m\_\{N\}\\\}denote the episodic memory store, whereNNgrows as the agent accumulates experience\. Each memory entry is a tuple

mi=\(ci,𝐞i,Qi\),m\_\{i\}=\(c\_\{i\},\\mathbf\{e\}\_\{i\},Q\_\{i\}\),whereci∈Σ∗c\_\{i\}\\in\\Sigma^\{\*\}is the memory content \(natural language text encoding a past experience\),𝐞i=ϕ​\(ci\)∈ℝd\\mathbf\{e\}\_\{i\}=\\phi\(c\_\{i\}\)\\in\\mathbb\{R\}^\{d\}is an embedding computed by a frozen encoderϕ\\phi, andQi∈ℝQ\_\{i\}\\in\\mathbb\{R\}is the*Q\-value*, the agent’s current estimate ofmim\_\{i\}’s value when retrieved for a relevant task\.

After each interaction with the environment, the system constructs a new memory based on the sampled trajectory\. The memory builder applies*proceduralization*: an LLM distills the trajectoryτ\\tauinto an abstract 3 to 5 step script, storing both the script and the raw trajectory as memory content\. Successful trajectories are stored directly; on failure, an LLM generates a*reflection*\(an analysis of what went wrong\), which is stored as a separate memory\. The initial Q\-value of each new memory is set to the average Q\-value of the memories that contributed to its creation:

Q​\(mnew\)=1\|Aj\|​∑mi∈AjQ​\(mi\),Q\(m\_\{\\mathrm\{new\}\}\)=\\frac\{1\}\{\|A\_\{j\}\|\}\\sum\_\{m\_\{i\}\\in A\_\{j\}\}Q\(m\_\{i\}\),whereAjA\_\{j\}is the retrieved set for taskjj\. When no memories are retrieved \(Aj=∅A\_\{j\}=\\emptyset\),Q​\(mnew\)Q\(m\_\{\\mathrm\{new\}\}\)is initialized randomly, analogous to the random initialization of value functions in deep Q\-networks\. Each memory’s retrieval key is derived from the task descriptionssthat generated it\.

### 4\.2Q\-integrated Retrieval Policy within Local Consistency

The retrieval policy decomposes the action selectionA⊆ℳA\\subseteq\\mathcal\{M\}into two phases addressing orthogonal concerns:*locality*, ensuring that retrieved memories lie within a neighborhood where the LLM can reliably generalize, and*Q\-guided selection*, selecting among those local candidates the memories whose RL\-learned Q\-values indicate high long\-run value\.

##### Locality filtering\.

Capable LLMs can act near\-optimally by interpolating from similar past experiences, eliminating the need for exact memory matches\. This relies on the*LLM local consistency*property\(wang2025memento2\): if a retrieved memory lies within distancerr\(the*radius of competence*\) of the current statess, the LLM’s optimality gapεLLM​\(r\)\\varepsilon\_\{\\mathrm\{LLM\}\}\(r\)remains small\. Locality filtering operationalizes this by identifying the local neighborhood ofss\. While any state\-space metric suffices, we instantiate it using cosine similarity in embedding space:sim​\(s,mi\)=ϕ​\(s\)⊤​𝐞i/\(‖ϕ​\(s\)‖⋅‖𝐞i‖\)\\mathrm\{sim\}\(s,m\_\{i\}\)=\\phi\(s\)^\{\\top\}\\mathbf\{e\}\_\{i\}/\(\\\|\\phi\(s\)\\\|\\cdot\\\|\\mathbf\{e\}\_\{i\}\\\|\)\. This forms the candidate set𝒞s=\{mi∈ℳ:sim​\(s,mi\)≥θsim\}\\mathcal\{C\}\_\{s\}=\\\{m\_\{i\}\\in\\mathcal\{M\}:\\mathrm\{sim\}\(s,m\_\{i\}\)\\geq\\theta\_\{\\mathrm\{sim\}\}\\\}, where the thresholdθsim\\theta\_\{\\mathrm\{sim\}\}represents the radius of competence in similarity space\. If no memories meet this threshold, the task is considered novel, and the agent defaults to a zero\-shot fallback\.

##### Q\-guided selection\.

Once locality filtering ensures all candidates fall within the LLM’s radius of competence, the second step leverages reinforcement learning to discriminate among them\. Both similarity scores and Q\-values are normalized to\[0,1\]\[0,1\]so that they contribute on an equivalent scale\. Each candidate is then scored by a composite function:

score​\(s,mi\)=ws⋅sim​\(s,mi\)\+wq⋅Q​\(mi\),\\mathrm\{score\}\(s,m\_\{i\}\)=w\_\{s\}\\cdot\\mathrm\{sim\}\(s,m\_\{i\}\)\+w\_\{q\}\\cdot Q\(m\_\{i\}\),wherewsw\_\{s\}andwqw\_\{q\}control the trade\-off between relevance and learned value\. The Q\-valuesQ​\(mi\)Q\(m\_\{i\}\)are learned via the TD updates developed below, capturing long\-run value beyond surface\-level similarity\. Selection follows anε\\varepsilon\-greedy policy:

A=\{Top​\-​k​by​score​\(s,mi\)with probability​1−ε,Uniform sample of​k​from​𝒞swith probability​ε,A=\\begin\{cases\}\\mathrm\{Top\}\\text\{\-\}k\\;\\text\{by\}\\;\\mathrm\{score\}\(s,m\_\{i\}\)&\\text\{with probability \}1\-\\varepsilon,\\\\ \\text\{Uniform sample of \}k\\text\{ from \}\\mathcal\{C\}\_\{s\}&\\text\{with probability \}\\varepsilon,\\end\{cases\}ensuring continued exploration of currently undervalued memories\.

### 4\.3Provenance\-Based Credit Assignment

In classical TD\(λ\\lambda\)\(sutton2018reinforcement;sutton1988learning\), the*λ\\lambda\-return*Gtλ=\(1−λ\)​∑n=1∞λn−1​Gt\(n\)G\_\{t\}^\{\\lambda\}=\(1\{\-\}\\lambda\)\\sum\_\{n=1\}^\{\\infty\}\\lambda^\{n\-1\}G\_\{t\}^\{\(n\)\}interpolates between the one\-step bootstrapGt\(1\)=rt\+γ​Q​\(st\+1,at\+1\)G\_\{t\}^\{\(1\)\}=r\_\{t\}\+\\gamma\\,Q\(s\_\{t\+1\},a\_\{t\+1\}\)and the Monte Carlo returnGt\(∞\)=∑k=0∞γk​rt\+kG\_\{t\}^\{\(\\infty\)\}=\\sum\_\{k=0\}^\{\\infty\}\\gamma^\{k\}r\_\{t\+k\}\. Theλ\\lambda\-return advantage is standardly expressed as a discounted sum of future TD errors:

Gtλ−Q​\(st,at\)=∑k=0T−t−1\(γ​λ\)k​δt\+k,G\_\{t\}^\{\\lambda\}\-Q\(s\_\{t\},a\_\{t\}\)=\\sum\_\{k=0\}^\{T\-t\-1\}\(\\gamma\\lambda\)^\{k\}\\,\\delta\_\{t\+k\},\(4\)whereδt=rt\+γ​Q​\(st\+1,at\+1\)−Q​\(st,at\)\\delta\_\{t\}=r\_\{t\}\+\\gamma\\,Q\(s\_\{t\+1\},a\_\{t\+1\}\)\-Q\(s\_\{t\},a\_\{t\}\)\. This telescoping decomposition underpins eligibility traces, propagating credit temporally by weighting a future TD error att\+kt\+kby\(γ​λ\)k\(\\gamma\\lambda\)^\{k\}\. MemQ adapts this principle to episodic memory by replacing the temporal chain with a provenance DAG, i\.e\., credit flows backward along DAG edges, substituting the temporal stepkkwith structural depthdd\.

##### Per\-memory TD error\.

For tasksjs\_\{j\}with retrieved setAjA\_\{j\}, outcomeRjR\_\{j\}, and constructed memorymnew,jm\_\{\\mathrm\{new\},j\}, the per\-memory TD error is

δ​\(mi,j\)=Rj\+γ​Q​\(mnew,j\)−Q​\(mi\),∀mi∈Aj\.\\delta\(m\_\{i\},j\)=R\_\{j\}\+\\gamma\\,Q\(m\_\{\\mathrm\{new\},j\}\)\-Q\(m\_\{i\}\),\\quad\\forall\\,m\_\{i\}\\in A\_\{j\}\.\(5\)Allmi∈Ajm\_\{i\}\\in A\_\{j\}share the same reward and bootstrap target but differ in their current Q\-value estimates\. Settingγ=0\\gamma=0discards the bootstrap termγ​Q​\(mnew\)\\gamma Q\(m\_\{\\mathrm\{new\}\}\)and reduces the update to single\-step exponential moving average, crediting each memory only with the immediate reward\.

##### Credit propagation via the provenance DAG\.

Single\-step updates credit only directly\-retrieved memories\. To propagate credit to ancestors, we exploit the provenance DAG, which recordsparents​\(mnew\)=A\\mathrm\{parents\}\(m\_\{\\mathrm\{new\}\}\)=Afor each newly constructed memory \(§[3](https://arxiv.org/html/2605.08374#S3)\)\. For each tasksjs\_\{j\}, the TD errorδ​\(m0,j\)\\delta\(m\_\{0\},j\)is computed for each directly retrieved memorym0∈Ajm\_\{0\}\\in A\_\{j\}\(Eq\.[5](https://arxiv.org/html/2605.08374#S4.E5)\), then a BFS backward from eachm0m\_\{0\}propagates it to all reachable ancestors:

ΔQ\(m\)\+=α∑m0∈Aj\(γλ\)d​\(m,m0\)⋅δ\(m0,j\),\\Delta Q\(m\)\\mathrel\{\+\}=\\alpha\\sum\_\{m\_\{0\}\\in A\_\{j\}\}\(\\gamma\\lambda\)^\{d\(m,m\_\{0\}\)\}\\cdot\\delta\(m\_\{0\},j\),\(6\)whered​\(m,m0\)d\(m,m\_\{0\}\)is the shortest path length fromm0m\_\{0\}tommin the DAG\. The structural discount\(γ​λ\)d\(\\gamma\\lambda\)^\{d\}directly instantiates the\(γ​λ\)k\(\\gamma\\lambda\)^\{k\}decay in Eq\.[4](https://arxiv.org/html/2605.08374#S4.E4), with DAG depthddreplacing temporal step countkk\. Credit accumulates over all paths from each root to the ancestor, analogous to every\-visit Monte Carlo\. The BFS is bounded by maximum depthDDand a discount floor\(γ​λ\)d<10−12\(\\gamma\\lambda\)^\{d\}<10^\{\-12\}\. Updates are accumulated in a buffer within each training epoch, along with the update countNiN\_\{i\}\. At epoch boundaries, the buffer is flushed:

Q​\(mi\)←Q​\(mi\)\+clip​\(Δ​Q​\(mi\)Ni,−ϵclip,ϵclip\)\.Q\(m\_\{i\}\)\\leftarrow Q\(m\_\{i\}\)\+\\mathrm\{clip\}\\\!\\Bigl\(\\frac\{\\Delta Q\(m\_\{i\}\)\}\{N\_\{i\}\},\\;\-\\epsilon\_\{\\mathrm\{clip\}\},\\;\\epsilon\_\{\\mathrm\{clip\}\}\\Bigr\)\.Averaging byNiN\_\{i\}normalizes for retrieval frequency, analogous to batch gradient descent\. Deferred writes ensure a stable retrieval landscape within each epoch\. The full procedure is summarized in Algorithm[1](https://arxiv.org/html/2605.08374#alg1)\.

## 5Experiments

We evaluate MemQ on six benchmarks spanning interactive agents, function calling, code generation, multimodal understanding, embodied reasoning, and expert\-level QA\. Our experiments address two questions: \(1\) Does MemQ outperform single\-step baselines and transfer to held\-out tasks? \(2\) How do the discount factorγ\\gammaand eligibility trace decayλ\\lambdaaffect performance?

### 5\.1Experimental Setup

##### Baselines\.

We compare against six baselines\.No Memory: a frozen LLM without retrieved context\.RAG: retrieves the top\-kkmemories via cosine similarity without quality re\-ranking\.Self\-RAG\(asai2024selfrag\)222We reproduce its pipeline using the same frozen LLM, without the benchmark\-specific fine\-tuned critique model\.: generates queries and filters unhelpful retrieved memories via self\-evaluation\.Mem0\(mem0\): manages episodic memory lifecycles through extraction, updates, and deletion\.MemP\(fang2026mempexploringagentprocedural\): distills past trajectories into step\-by\-step instructions and script\-like abstractions as procedural memory, with dynamic update, correction, and deprecation rules\.MemRL\(zhang2026memrl\): a closely related approach that updates per\-memory utility values via single\-step EMA without eligibility traces\.

##### Benchmarks and LLM backbones\.

We use six diverse benchmarks, splitting each into training sets \(for memory accumulation\) and held\-out test sets \(for generalization ability evaluation\)\. LifeLongAgentBench \(LLAB\)\(zheng2026lifelongagentbench\)tests multi\-step OS\-level agent planning across sessions\. BFCL v3\(patil2025bfcl\)evaluates multi\-turn function calling and error recovery across diverse APIs, measuring correctness via backend state comparisons against ground truth\. LiveCodeBench v6\(jain2025livecodebench\)assesses contamination\-free competitive code generation\. MMMU Pro\(yue\-etal\-2025\-mmmu\)tests 10\-choice multimodal reasoning\. ERQA\(geminiroboticsteam2025geminiroboticsbringingai\)evaluates multimodal, physically grounded question\-answering, and GPQA\(rein2024gpqa\)contains graduate\-level, Google\-proof questions spanning physics, chemistry, and biology, requiring expert\-level reasoning\. All methods use frozen LLM backbones: GPT\-4o\-mini for LLAB; Qwen3\.5\-35B\-A3B\(qwen3\.5\)for BFCL; and Gemma\-4\-E4B\-it\(gemma\_4\_e4b\_it\)for the remaining four benchmarks\.

### 5\.2MemQ Outperforms All Baselines in Generalization and Runtime Evolving

##### Evaluation on held\-out tasks\.

Table[1](https://arxiv.org/html/2605.08374#S5.T1)reports success rates \(SR\) on held\-out tasks using a frozen memory store and greedy retrieval\. MemQ achieves the highest SR on five of six benchmarks and ties MemRL on GPQA \(with lower variance\)\. Standard retrieval methods \(RAG, Self\-RAG, Mem0\) provide modest gains over No Memory, but struggle to filter harmful memories without quality ranking\. MemP distills procedural instructions for further improvements \(e\.g\., on MMMU Pro and BFCL\) but lacks a prioritization mechanism\. MemRL introduces per\-memory utility values, yielding a significant jump on LLAB and confirming the necessity of ranking\. MemQ further outperforms MemRL wherever provenance chains are deep: \+5\.7 pp on LiveCodeBench, \+4\.6 pp on ERQA, and \+2\.3 pp on BFCL\. On tasks requiring only shallow, single\-step updates, the gap narrows: both methods converge to 60\.8% on GPQA \(leaving little room above MemP’s 59\.2%\), and MemQ leads by just 0\.77 pp on MMMU Pro\. Ultimately, these results demonstrate that the benefits of structural credit assignment scale with task complexity, driving substantial improvements in multi\-step tasks while offering negligible gains in single\-step ones\.

Table 1:Evaluation results on held\-out test tasks \(success rate, %\)\. We select the best\-epoch memory bank from each training run and evaluate it on the test split\. Results are computed over 3 seeds\. Best inbold; second\-bestunderlined\.BenchmarkModelNo Mem\.RAGSelf\-RAGMem0MemPMemRL*MemQ*LLABOS Interaction4o\-mini66\.89±1\.2668\.89±0\.3870\.45±0\.3970\.00±0\.6771\.11±0\.3874\.44±1\.0274\.67±0\.67LiveCodeBenchCoding44\.76±2\.2950\.48±1\.6549\.52±1\.6547\.62±1\.6549\.52±1\.6545\.71±2\.8651\.43±2\.86MMMU ProMultimodalGemma\-4\-E4B\-it48\.46±0\.7653\.76±1\.0453\.57±0\.8449\.90±1\.3754\.24±1\.4253\.66±1\.0154\.43±0\.88ERQAEmbodied Reasoning41\.67±1\.2444\.58±1\.4450\.42±2\.8948\.33±1\.9145\.00±3\.3146\.67±1\.9151\.25±2\.17GPQA DiamondScience QA47\.50±3\.0158\.33±3\.8258\.33±3\.8258\.33±1\.1859\.17±1\.4460\.83±5\.2060\.83±3\.82BFCLFunction CallQwen3\.5\-35B\-A3B56\.71±1\.7155\.45±2\.6260\.07±2\.4954\.79±1\.6861\.39±0\.9960\.07±2\.2962\.38±1\.71

##### Runtime learning\.

As a self\-evolving agent, MemQ continuously accumulates memories and updates their Q\-values during training\. Table[2](https://arxiv.org/html/2605.08374#S5.T2)reports final\-epoch SR and cumulative SR on the training set\. MemQ achieves the highest SR on all six benchmarks\. The gains over MemRL are largest on tasks that produce deep provenance chains through multi\-step tool use: BFCL \(\+3\.8 pp SR, \+0\.6 pp CSR\), LLAB \(\+3\.2 pp SR, \+1\.5 pp CSR\), and ERQA \(\+4\.2 pp SR, \+5\.9 pp CSR\)\. On ERQA, the CSR gap is especially notable, indicating that memory provenance credit not only improves final performance but compounds over the training trajectory\. On GPQA Diamond, both methods converge near ceiling, leaving little room for improvement\. On MMMU Pro, the gap shrinks to 0\.15 pp SR, because single\-step updates already suffice\. Across all benchmarks, MemQ’s advantage is most pronounced where it matters most, i\.e\., on the complex, multi\-step tasks that are the primary target of memory\-augmented agents\. The learning curves \(Figure[6](https://arxiv.org/html/2605.08374#A1.F6), Appendix[A](https://arxiv.org/html/2605.08374#A1)\) show that structural credit assignment does not merely improve final performance but accelerates the entire learning process\.

Table 2:Runtime learning results on the training set \(%\)\. For each benchmark, the first row reports final\-epoch success rate \(SR\) and the second row reports cumulative success rate \(CSR\) over all epochs\. Results are computed over 3 seeds\. Best inbold; second\-bestunderlined\.BenchmarkModelNo Mem\.RAGSelf\-RAGMem0MemPMemRL*MemQ*LLABOS Interaction4o\-mini63\.60±0\.2865\.20±1\.1462\.33±0\.6262\.53±0\.2576\.07±0\.5277\.13±0\.6880\.34±2\.22–68\.47±0\.8475\.27±0\.7478\.40±0\.4379\.27±0\.5280\.80±0\.9182\.27±1\.88LiveCodeBenchCodingGemma\-4\-E4B\-it47\.14±1\.4351\.96±2\.1145\.89±2\.7849\.52±1\.6853\.04±0\.7858\.93±0\.6261\.79±0\.80–57\.38±0\.8965\.00±2\.4256\.19±0\.3455\.48±0\.8966\.19±1\.4767\.62±0\.67MMMU ProMultimodal48\.92±0\.5049\.98±0\.7949\.33±0\.6249\.18±0\.7751\.37±0\.7257\.68±0\.6657\.83±0\.32–51\.81±0\.6862\.04±0\.3653\.40±0\.7253\.47±1\.0462\.93±0\.6163\.39±0\.19ERQAEmbodied Reasoning39\.38±0\.0039\.61±1\.6640\.31±1\.0237\.81±1\.0241\.80±0\.9557\.11±2\.5061\.33±1\.76–50\.78±0\.9062\.42±1\.8049\.17±1\.0350\.31±1\.5577\.08±1\.3183\.02±1\.85GPQA DiamondScience QA52\.53±1\.1065\.19±3\.6285\.02±1\.3064\.86±1\.3193\.46±1\.3097\.05±0\.5298\.52±1\.37–68\.99±3\.2395\.99±0\.3071\.94±1\.6695\.99±1\.4997\.89±0\.3098\.95±0\.60BFCLFunction CallQwen3\.5\-35B\-A3B54\.52±1\.3055\.28±2\.3164\.91±0\.7857\.37±0\.8365\.91±1\.2071\.27±0\.4775\.04±0\.31–70\.77±0\.3180\.99±1\.3373\.62±1\.2880\.15±1\.1485\.85±1\.4486\.43±1\.13

### 5\.3A Deeper Look at the Roles ofγ\\gammaandλ\\lambdain Memory Provenance

MemQ introduces two key hyperparameters absent from single\-step methods: the discount factorγ\\gammaand the eligibility trace decayλ\\lambda\. Together, they determine how far credit propagates through the provenance DAG: the effective credit reach is governed by\(γ​λ\)d\(\\gamma\\lambda\)^\{d\}, whereddis the DAG depth \(Eq\.[6](https://arxiv.org/html/2605.08374#S4.E6)\)\. Yetγ\\gammaandλ\\lambdaplay fundamentally different roles:γ\\gammacontrols the*structural*horizon by weighting the bootstrap targetγ​Q​\(mnew\)\\gamma Q\(m\_\{\\mathrm\{new\}\}\)\(Eq\.[5](https://arxiv.org/html/2605.08374#S4.E5)\), whileλ\\lambdacontrols the*empirical*horizon by decaying how far each observed TD error propagates \(Eq\.[6](https://arxiv.org/html/2605.08374#S4.E6)\)\. We sweep each hyperparameter individually\.

##### Largerγ\\gammapropagates credit more effectively in deep provenance chains\.

The discount factorγ\\gammashapes both the bootstrap targetγ​Q​\(mnew\)\\gamma Q\(m\_\{\\mathrm\{new\}\}\)and the structural discount\(γ​λ\)d\(\\gamma\\lambda\)^\{d\}in credit propagation \(Eqs\.[5](https://arxiv.org/html/2605.08374#S4.E5)–[6](https://arxiv.org/html/2605.08374#S4.E6)\)\. Figure[4](https://arxiv.org/html/2605.08374#S5.F4)reveals a cross\-benchmark reversal: LiveCodeBench peaks at a moderateγ≈0\.5\\gamma\\approx 0\.5and degrades sharply atγ=0\.9\\gamma=0\.9\(∼\\sim63% vs\.∼\\sim56%\), whereas BFCL favors a higherγ∈\[0\.8,1\.0\]\\gamma\\in\[0\.8,1\.0\]\(∼\\sim76% vs\.∼\\sim73% atγ=0\\gamma=0\)\. This reflects task structure\. BFCL’s multi\-turn nature creates deep provenance chains, necessitating largerγ\\gammato propagate credit across the full DAG\. In contrast, excessiveγ\\gammain single\-turn LiveCodeBench tasks amplifies noise from distant ancestors\. Ultimately, largerγ\\gammaimproves performance proportionally to DAG depth, confirming that provenance structure carries genuine causal signals regarding influential ancestor memories\.

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/lcb_lambda0.95_sr_13579.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/lcb_lambda0.3_sr_13579.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/bfcl_lambda0.5_sr_03581.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/bfcl_lambda0.3_sr_03581.png)

Figure 4:Success rate under differentγ\\gamma\.
##### Exogenous task transitions inflate variance, shifting the optimalλ\\lambdadownward\.

The trace decayλ\\lambdadictates backward TD error propagation through the provenance DAG, weighting an ancestor at depthddby\(γ​λ\)d\(\\gamma\\lambda\)^\{d\}\(Eq\.[6](https://arxiv.org/html/2605.08374#S4.E6)\)\. Unlikeγ\\gamma, which shapes the bootstrap target,λ\\lambdastrictly governs credit assignment\. Sweepingλ\\lambdaon LiveCodeBench \(Figure[5](https://arxiv.org/html/2605.08374#S5.F5),γ=0\.3\\gamma=0\.3\) reveals that lower values excel:λ=0\.3\\lambda=0\.3achieves the highest SR \(∼\\sim65\.8%\), whileλ=0\.9\\lambda=0\.9performs worst \(∼\\sim59\.5%\)\. This downward shift of the optimalλ∗\\lambda^\{\*\}relative to standard MDPs aligns with the EC\-MDP’s factored transition \(Eq\.[1](https://arxiv.org/html/2605.08374#S3.E1)\)\. Because the next taskst\+1∼Pexos\_\{t\+1\}\\sim P\_\{\\mathrm\{exo\}\}is independent of the current retrieval action, propagating credit across task boundaries introduces pure variance without causal signal\. Consequently, while the classical TD\(λ\\lambda\) bias–variance tradeoff holds\(kearns2000bias;sutton2018reinforcement\), the exogenous task stream inflates variance, shifting the U\-shaped optimum leftward\. Results on BFCL \(Figure[10](https://arxiv.org/html/2605.08374#A2.F10)\) confirm this: extremes suffer from excessive bias \(λ=0\.0\\lambda=0\.0\) or variance \(λ=0\.8\\lambda=0\.8\), making the intermediateλ=0\.5\\lambda=0\.5optimal\.

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_lambda/lcb_gamma0.3_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_lambda/lcb_gamma0.3_td_error.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_lambda/lcb_gamma0.3_td_variance.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_lambda/lcb_gamma0.3_td_bias.png)

Figure 5:SR, TD error, TD variance, and TD bias under differentλ\\lambda\.γ\\gammaandλ\\lambda: Trusting Structure, Distrusting Noise\. Ultimately, the interplay betweenγ\\gammaandλ\\lambdareflects the core premise of the EC\-MDP\. Because endogenous memory evolution is inherently Markovian, MemQ leverages a highγ\\gammato confidently assign structural credit backward along the causal provenance DAG\. However, since exogenous tasks are independently drawn from a distribution, cross\-task transitions introduce pure variance without causal signal\. MemQ counters this by maintaining a relatively lowλ\\lambda, thereby isolating the structural credit assignment from the empirical noise of unrelated tasks\.

## 6Conclusion

In this paper, we identified the multi\-step credit assignment problem in episodic memory for LLM agents, where existing methods update each memory in isolation despite the dependency chains through which memories enable one another\. We formalized this setting as the Exogenous\-Context MDP and developed MemQ, which propagates TD\(λ\\lambda\) eligibility traces backward through a provenance DAG, replacing temporal distance with structural depth\. Across six benchmarks, MemQ achieves leading success rates on all six benchmarks, in both generalization evaluations and runtime evolution\. Ablations show that largerγ\\gammatrusts the provenance structure while smallerλ\\lambdadistrusts cross\-task noise, shifting optimalλ∗\\lambda^\{\*\}downward in the EC\-MDP\. These results establish structural credit assignment over memory dependency graphs as the key missing ingredient for self\-evolving memory agents\.

## 7Limitations

Several limitations remain\. First, maintaining the provenance DAG incurs continuous storage overhead, and the BFS\-based credit propagation costsO​\(\|Aj\|⋅D\)O\(\|A\_\{j\}\|\\cdot D\)per task\. Scaling to lifelong learning may require approximate propagation mechanisms, such as ancestor sampling or dynamic depth truncation\. Second, MemQ assumes monotonic memory growth without explicitly addressing memory consolidation or deletion\. While essential for bounded\-capacity systems, designing memory management mechanisms \(e\.g\., value\-based eviction\) is orthogonal to our core focus of multi\-step credit assignment\. Third, our locality filter relies strictly on embedding cosine similarity; exploring alternative distance metrics could further refine the agent’s radius of competence\. Finally, the Exogenous\-Context MDP assumes task states are independently drawn from an external distribution\. Extending this framework to environments where agents influence the task sequence \(e\.g\., active curriculum learning\) would require revisiting the state factorization\. Addressing these open challenges presents promising directions for future work\.

#### Broader Impact Statement

This work advances memory management for LLM agents through reinforcement learning\. While the method improves agent capabilities in general\-purpose benchmarks, we do not foresee direct negative societal impacts beyond those inherent to LLM\-based agent systems\. We encourage responsible deployment practices\.

## References

## Appendix AAdditional Learning Curves

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/OS_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/LCB_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/MMMU_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ERQA_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/GPQA_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/BFCL_sr.png)

Figure 6:Runtime learning dynamics \(success rate vs\. epoch\) across six benchmarks\.![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/OS_csr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/LCB_csr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/MMMU_csr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ERQA_csr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/GPQA_csr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/BFCL_csr.png)

Figure 7:Cumulative success rate \(CSR\) over epochs across six benchmarks, complementing the per\-epoch SR curves in Figure[6](https://arxiv.org/html/2605.08374#A1.F6)\. MemQ’s per\-epoch advantage accumulates into a sustained overall improvement, with the CSR gap widening most on benchmarks with deep provenance chains \(ERQA, BFCL, LifeLongAgentBench\)\.
## Appendix BMore Ablation Experiment Figures

### B\.1TD Error Analysis forγ\\gammaAblation

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/lcb_lambda0.95_td_135.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/lcb_lambda0.95_td_579.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/lcb_lambda0.3_td_135.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/lcb_lambda0.3_td_579.png)

Figure 8:TD error under differentγ\\gammaon LiveCodeBench\.![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/bfcl_lambda0.5_td_035.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/bfcl_lambda0.5_td_581.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/bfcl_lambda0.3_td_035.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_gamma/bfcl_lambda0.3_td_581.png)

Figure 9:TD error under differentγ\\gammaon BFCL\.
### B\.2λ\\lambdaAblation on BFCL

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_lambda/bfcl_gamma0.8_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_lambda/bfcl_gamma0.8_td_error.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_lambda/bfcl_gamma0.8_td_variance.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/experiments/ablations_lambda/bfcl_gamma0.8_td_bias.png)

Figure 10:SR, TD error, TD variance, and TD bias under differentλ\\lambdaon BFCL \(γ=0\.8\\gamma=0\.8\)\.
### B\.3DDAblation on BFCL

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/Depth/bfcl_gamma_sweep_lambda03_gamma05_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/Depth/bfcl_gamma_sweep_lambda05_gamma05_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/Depth/bfcl_gamma_sweep_lambda08_gamma05_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/Depth/bfcl_gamma_sweep_lambda10_gamma05_sr.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/Depth/bfcl_gamma_sweep_lambda03_gamma05_td_error.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/Depth/bfcl_gamma_sweep_lambda05_gamma05_td_error.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/Depth/bfcl_gamma_sweep_lambda08_gamma05_td_error.png)

![Refer to caption](https://arxiv.org/html/2605.08374v1/figures/Depth/bfcl_gamma_sweep_lambda10_gamma05_td_error.png)

Figure 11:SR \(top row\) and TD error \(bottom row\) under differentDDon BFCL\.

## Appendix CBaseline Implementation Details

RAG: We use the official MemRL codebase for the RAG experiments because it has already integrated RAG by disabling the value\-related hyperparameters and doing raw trajectory saving\.

Self\-RAG: We reproduced Self\-RAG pipeline, including on\-demand retrieval, relevance, support, utility critiques, and selection according to the critiques\. In their original paper, they fine\-tuned models for critique and reflection generation, but the open\-sourced fine\-tuned models can only work well on the benchmarks their paper conducted on\. So we only produced the Self\-RAG pipeline without fine\-tuning models, and we assume that a powerful model like Qwen3\.5\-35B\-A3B has the ability to recognize when to retrieve and generate high\-quality critiques\.

Mem0: We use the official mem0 repository for its experiments\. All the hyperparameters shared with other baselines align with those baselines\.

MemP: We use the official MemRL codebase for the MemP experiments because it has already integrated MemP\.

MemRL: We use the official MemRL codebase for the MemRL experiments\.

## Appendix DHyperparameter Configurations

We report hyperparameters for each benchmark separately, since key parameters \(γ\\gamma,λ\\lambda,wsw\_\{s\},wqw\_\{q\}, Batch size,θsim\\theta\_\{\\mathrm\{sim\}\}, Initial Q, epochs\) vary across benchmarks\. Table[3](https://arxiv.org/html/2605.08374#A4.T3)lists settings shared across all benchmarks\. Tables[4](https://arxiv.org/html/2605.08374#A4.T4)–[9](https://arxiv.org/html/2605.08374#A4.T9)give per\-benchmark configurations for each method\.

Table 3:Settings shared across all benchmarks and methods\.ParameterValueDescriptionnormalize\_dqtrueNormalize Q\-value deltassuccess\_reward1\.0Reward for correct answerfailure\_reward0\.0Reward for wrong answernormalize\_simfalseRaw similarity scores \(already in\[0,1\]\[0,1\]\)normalize\_qtrue \(value\-based methods\)Normalize Q for retrieval scoringtemperature0\.0Deterministic LLM generationDD4Maximum BFS depth for DAG traversalDiscount floor\(γ​λ\)d<10−12\(\\gamma\\lambda\)^\{d\}<10^\{\-12\}Prune deep BFS paths##### LifeLongAgentBench\.

LLM backbone: GPT\-4o\-mini\. Embedding model:text\-embedding\-3\-large\(d=3072d=3072\)\. Training on the full 500\-sample dataset; no validation split\. Max agent steps per task: 15\.

Table 4:LifeLongAgentBench hyperparameters\.MemQMemRLMemPMem0Self\-RAGRAGα\\alpha0\.30\.3N/AN/AN/AN/Aγ\\gamma0\.5N/AN/AN/AN/AN/Aλ\\lambda0\.7N/AN/AN/AN/AN/Aε\\varepsilon0\.010\.010\.010\.00\.010\.01kretk\_\{\\mathrm\{ret\}\}10101051010ktopk\_\{\\mathrm\{top\}\}555555θsim\\theta\_\{\\mathrm\{sim\}\}0\.50\.50\.50\.00\.50\.5wsw\_\{s\}0\.50\.5N/AN/AN/AN/Awqw\_\{q\}0\.50\.5N/AN/AN/AN/ABatch size646464646464Max tokens102401024010240102401024010240Initial Q0\.660\.66N/AN/AN/AN/ABuildproceduralizationproceduralizationproceduralizationtrajectorytrajectorytrajectoryUpdateadjustmentadjustmentadjustmentvanillavanillavanillaEpochs202020202020
##### LiveCodeBench\.

LLM backbone: Gemma\-4\-E4B\-it\. Embedding model: Qwen3\-Embedding\-8B\. 175 problems \(140 train / 35 valid\)\.

Table 5:LiveCodeBench hyperparameters\.MemQMemRLMemPMem0Self\-RAGRAGα\\alpha0\.30\.3N/AN/AN/AN/Aγ\\gamma0\.3N/AN/AN/AN/AN/Aλ\\lambda0\.95N/AN/AN/AN/AN/Aε\\varepsilon0\.00\.00\.00\.00\.00\.0kretk\_\{\\mathrm\{ret\}\}555555ktopk\_\{\\mathrm\{top\}\}333533θsim\\theta\_\{\\mathrm\{sim\}\}0\.60\.60\.60\.00\.60\.6wsw\_\{s\}0\.40\.4N/AN/AN/AN/Awqw\_\{q\}0\.60\.6N/AN/AN/AN/ABatch size323232323232Max tokens102401024010240102401024010240Initial Q0\.370\.37N/AN/AN/AN/ABuildproceduralizationproceduralizationproceduralizationtrajectorytrajectorytrajectoryUpdateadjustmentadjustmentadjustmentvanillavanillavanillaEpochs100100100100100100
##### MMMU Pro\.

LLM backbone: Gemma\-4\-E4B\-it\. Embedding model: Qwen3\-Embedding\-8B\. 1730 problems \(1384 train / 346 valid\)\.

Table 6:MMMU Pro hyperparameters\.MemQMemRLMemPMem0Self\-RAGRAGα\\alpha0\.30\.3N/AN/AN/AN/Aγ\\gamma0\.5N/AN/AN/AN/AN/Aλ\\lambda0\.7N/AN/AN/AN/AN/Aε\\varepsilon0\.00\.00\.00\.00\.00\.0kretk\_\{\\mathrm\{ret\}\}555555ktopk\_\{\\mathrm\{top\}\}333533θsim\\theta\_\{\\mathrm\{sim\}\}0\.550\.550\.550\.00\.500\.55wsw\_\{s\}0\.50\.5N/AN/AN/AN/Awqw\_\{q\}0\.50\.5N/AN/AN/AN/ABatch size128128128128128128Max tokens409640964096409640964096Initial Q0\.5260\.526N/AN/AN/AN/ABuildproceduralizationproceduralizationproceduralizationtrajectorytrajectorytrajectoryUpdateadjustmentadjustmentadjustmentvanillavanillavanillaEpochs505050505050
##### ERQA\.

LLM backbone: Gemma\-4\-E4B\-it\. Embedding model: Qwen3\-Embedding\-8B\. 400 problems \(320 train / 80 valid\)\.

Table 7:ERQA hyperparameters\.MemQMemRLMemPMem0Self\-RAGRAGα\\alpha0\.30\.3N/AN/AN/AN/Aγ\\gamma0\.5N/AN/AN/AN/AN/Aλ\\lambda0\.99N/AN/AN/AN/AN/Aε\\varepsilon0\.00\.00\.00\.00\.00\.0kretk\_\{\\mathrm\{ret\}\}555555ktopk\_\{\\mathrm\{top\}\}333533θsim\\theta\_\{\\mathrm\{sim\}\}0\.60\.60\.60\.00\.50\.6wsw\_\{s\}0\.40\.5N/AN/AN/AN/Awqw\_\{q\}0\.60\.5N/AN/AN/AN/ABatch size646464646464Max tokens409640964096409640964096Initial Q0\.370\.37N/AN/AN/AN/ABuildproceduralizationproceduralizationproceduralizationtrajectorytrajectorytrajectoryUpdateadjustmentadjustmentadjustmentvanillavanillavanillaEpochs100100100100100100
##### BFCL\.

LLM backbone: Qwen3\.5\-35B\-A3B\. Embedding model: Qwen3\-Embedding\-8B\. 500 problems \(400 train / 100 test\)\.

Table 8:BFCL hyperparameters\.MemQMemRLMemPMem0Self\-RAGRAGα\\alpha0\.30\.3N/AN/AN/AN/Aγ\\gamma0\.5N/AN/AN/AN/AN/Aλ\\lambda0\.8N/AN/AN/AN/AN/Aε\\varepsilon0\.010\.010\.010\.00\.010\.01kretk\_\{\\mathrm\{ret\}\}1010105105ktopk\_\{\\mathrm\{top\}\}555555θsim\\theta\_\{\\mathrm\{sim\}\}0\.50\.50\.50\.00\.50\.5wsw\_\{s\}0\.70\.7N/AN/AN/AN/Awqw\_\{q\}0\.30\.3N/AN/AN/AN/ABatch size100100100100100100Max tokens409640964096409640964096Initial Q0\.50\.5N/AN/AN/AN/ABuildproceduralizationproceduralizationproceduralizationtrajectorytrajectorytrajectoryUpdateadjustmentadjustmentadjustmentvanillavanillavanillaEpochs202020202020
##### GPQA Diamond\.

LLM backbone: Gemma\-4\-E4B\-it\. Embedding model: Qwen3\-Embedding\-8B\. 198 problems \(158 train / 40 test\)\.

Table 9:GPQA Diamond hyperparameters\.MemQMemRLMemPMem0Self\-RAGRAGα\\alpha0\.30\.3N/AN/AN/AN/Aγ\\gamma0\.5N/AN/AN/AN/AN/Aλ\\lambda0\.7N/AN/AN/AN/AN/Aε\\varepsilon0\.010\.010\.010\.00\.010\.01kretk\_\{\\mathrm\{ret\}\}10101051010ktopk\_\{\\mathrm\{top\}\}555555θsim\\theta\_\{\\mathrm\{sim\}\}0\.50\.50\.50\.00\.50\.5wsw\_\{s\}0\.50\.7N/AN/AN/AN/Awqw\_\{q\}0\.50\.3N/AN/AN/AN/ABatch size40100100100100100Max tokens163841638416384163841638416384Initial Q0\.50\.5N/AN/AN/AN/ABuildproceduralizationproceduralizationproceduralizationtrajectorytrajectorytrajectoryUpdateadjustmentadjustmentadjustmentvanillavanillavanillaEpochs353535353535