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.