MemQ: Integrating Q-Learning into Self-Evolving Memory Agents over Provenance DAGs
Authors: Junwei Liao, Haoting Shi, Ruiwen Zhou et al.
Summary
The authors built MemQ, a system that makes LLM agents learn which memories are actually useful by treating memory retrieval like a reinforcement learning problem. Instead of scoring each memory in isolation, MemQ uses a "provenance DAG" — essentially a family tree showing which memories were retrieved to create new memories — and propagates credit backward through those dependency chains using TD(λ), a temporal-difference learning algorithm. When tested on six benchmarks (OS tasks, function calling, code generation, etc.), MemQ beats baselines across the board, with the biggest gains (+5.7 percentage points) on multi-step tasks where memories build on each other and smaller gains (+0.77 pp) on single-step classification where there's no chain to exploit.
Main takeaways:
- Memory retrieval is framed as a Markov decision process where the agent's memory store evolves separately from the external task stream (an "Exogenous-Context MDP").
- Credit flows backward through a directed acyclic graph that records which memories were used to create each new memory, with credit decaying by (γλ)^d where d is the graph depth.
- Performance gains are largest when tasks produce deep, relevant memory chains (multi-step reasoning) and smallest when memories are used independently (single-step classification).
- The approach outperforms baselines on all six benchmarks in both generalization and online learning settings.
Relevance
Not directly related to my persona/midtraining work — included because it's a memory architecture paper that might inform how context or retrieval mechanisms interact with installed behaviors, but it doesn't touch marker implantation, steering, or persona geometry.
Threat model
Potential threat/caveat for clean result "Fine-tuning one persona on a two-marker chunk and another on the start marker plants the end marker at every donor answer's end, not chained to the start (LOW confidence)": this item discusses evaluation, benchmark.
Abstract
arXiv:2605.08374v1 Announce Type: new 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 introduce MemQ, 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 $(\gamma\lambda)^d$ with DAG depth $d$, 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.7pp) and smallest on single-step classification (+0.77pp) where single-step updates already suffice. We further study how $\gamma$ and $\lambda$ interact with the EC-MDP structure, providing principled guidance for parameter selection and future research. Code will be available soon.