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

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

Hi everyone! We are excited to share MemQ, a framework that brings reinforcement learning to LLM agent memory — without any weight updates.

The Problem

Current episodic memory systems for LLM agents treat each memory independently, evaluating retrieval quality in isolation. But memories don't exist in isolation — they form dependency chains where retrieving one memory enables creating future ones. Existing approaches miss this structural relationship entirely.

Our Approach

MemQ applies TD(λ) eligibility traces to memory Q-values, propagating credit backward through a provenance DAG, a directed graph that records which memories were retrieved when each new memory was created. Instead of temporal distance, credit weight decays as (γλ)^d with DAG depth d, capturing structural proximity between memories.

*(Click image to enlarge)*

Key ideas:

• EC-MDP Formalization: We formalize self-evolving memory as an Exogenous-Context MDP, factoring state into an exogenous task stream and an endogenous memory store
• Q-Integrated Retrieval: Two-phase retrieval — locality filtering (cosine similarity) followed by Q-guided ε-greedy selection
• Provenance DAG Credit Assignment: BFS backward through memory creation chains for multi-step credit propagation
• No Weight Updates: The LLM backbone stays frozen — all learning happens through Q-value updates on episodic memories

Algorithm

*(Click image to enlarge)*

Results

MemQ achieves the highest success rate on all six benchmarks in both generalization evaluation and runtime learning:

Generalization Evaluation on Held-out Test Tasks

*(Click image to enlarge)*

Runtime Learning Results

*(Click image to enlarge)*

Benchmarks covered:

• Lifelong Agent Bench (OS Interaction / Database)
• Berkeley Function Calling Leaderboard (BFCL)
• Graduate-Level Google-Proof QA (GPQA)
• Embodied Reasoning QA (ERQA)
• MMMU Pro (Multimodal Understanding)
• LiveCodeBench (Code Generation)

Resources

• Paper: arXiv:2605.08374
• Code: jwliao-ai/MemQ | SII-MemQ/MemQ (Maintained in parallel)

We welcome any questions, discussions, or feedback. If you find this work useful, please consider giving us a star!