acceptodds
Under review as a conference paper at ICLR 2027

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

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() 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 with DAG depth , replacing temporal distance with structural proximity. We formalize this setting as an Exogenous-Context MDP, separating externally supplied tasks from the evolving memory store, and represent retrieval-set values by a first-order mean of per-memory values plus an explicit approximation residual. Across five interaction, code-generation, and agentic benchmarks, MemQ improves average held-out, final runtime, and cumulative success rates over the baseline with the highest average for each metric by 2.53, 4.23, and 2.13 percentage points, respectively. Ablations on LiveCodeBench, BFCL, and DSBench support the benefit of bootstrapping and multi-depth credit propagation. Analyses of Q-values and runtime learning show that learned memory values are associated with subsequent success and that MemQ retains more of its historical task coverage. We also explore the limits of MemQ's benefits using multiple-choice reasoning tasks, where limited interaction offers fewer opportunities to reuse procedural experience.

Primary area:
reinforcement learning
Keywords:
Memory Agents, Self-Evolving Agents, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_ZaZyOpenReview ↗
Rating
3
Confidence
4(+1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies multi-step credit assignment in the external episodic memory of LLM agents. Existing non-parametric memory-value learning methods usually update only the memories retrieved for the current task, making it difficult to handle long dependency chains in which an old memory helps create an intermediate memory that becomes useful in a future task. MemQ introduces an Exogenous-Context MDP to separate the externally supplied task stream from internal memory evolution. It records the retrieved parent memories used when each new memory is created, thereby constructing a provenance DAG. MemQ then replaces the temporal distance used by conventional TD(λ) eligibility traces with structural depth in this DAG, propagating TD errors to ancestor memories with weight (γλ)^d. The LLM remains frozen; the system only maintains per-memory Q-values and retrieves memories using semantic similarity, learned Q-values, and ε-greedy exploration. Across five interaction, code-generation, and agentic benchmarks, MemQ generally outperforms MemP, MemRL, and other baselines in held-out, final-runtime, and cumulative success rates. Ablations on γ/λ, bootstrapping, and multi-depth propagation support the main mechanism.

Critical strengths
  1. MemQ transfers TD(λ) credit propagation from a temporal sequence to a memory-construction provenance DAG. Eventual rewards can therefore reach ancestor memories that indirectly enabled later useful memories, addressing dependency chains that single-step updates over currently retrieved items cannot capture.
  2. The evaluation spans eight benchmarks and reports held-out performance, runtime learning, cumulative success, historical coverage, and token usage. The ablations cover bootstrapping, propagation depth, γ/λ, Q-value initialization, and retrieval weights. The limited gains on weakly interactive multiple-choice tasks also help delimit the settings in which the method is likely to be useful.
Critical weaknesses
  1. The similarity + Q policy may let high-Q memories from easy early tasks dominate later Top-k retrieval. New memories may therefore be under-exposed and under-evaluated, creating a frequency lock-in for early memories. We suggest reporting retrieval counts, Q-values, and success rates by task_id, and considering a frequency reward term.
  2. The paper lacks a cross-benchmark OOD evaluation: it does not test a protocol in which memories are acquired on one benchmark and then transferred to and evaluated on another benchmark. It is therefore unclear whether the learned Q-values, provenance credit, and procedural memories transfer across task distributions rather than only improving retrieval within the same benchmark.
Questions for authors
  1. Why not evaluate the complete evaluation set under a one-pass test-time augmentation protocol in which the agent processes one task at a time, receives feedback, writes the resulting memory, and uses that memory for the next task? The current terminal experiments pre-collect a sufficiently large memory bank from the training split at substantial cost before formal evaluation. Does this create an unfair resource or information advantage over no-memory methods, and how do the results change under a matched online budget?
  2. Successful experiences and failure lessons may both be important for the current inference. Have the authors considered retrieving separate quotas of successful experiences and failure lessons, and organizing them in separate prompt sections rather than retrieving and managing both types uniformly? How would such a separated design affect success rate, error rate, and memory interference?
  3. The paper does not report performance on Search-Agent tasks. It would be useful to add a Search-Agent benchmark covering search, fetch, and multi-step retrieval, and report held-out, runtime, and cumulative success rates together with per-task comparisons against the strongest baseline.
6 comments
AuthorsOpenReview ↗

Response to Reviewer ZaZy (1/3)

Dear Reviewer ZaZy,

We sincerely thank you for the careful review and constructive suggestions. To keep tables inline for easier reading, we split our response into three comments.

W1 & Q2: The similarity + Q policy may let high-Q memories from easy early tasks dominate retrieval, leaving new memories under-exposed; please report retrieval statistics by task_id and consider a frequency reward term. Have the authors considered separate quotas for successful experiences and failure lessons, organized in separate prompt sections?

A1: Thank you for both suggestions.

  1. Early-memory lock-in and recency (W1). On DSBench, we tracked how quickly memories are first retrieved and how retrieval is distributed, grouping memories by creation epoch (MemRL/MemQ per cell, %, mean±SD over three seeds):
Created inRetrieved within one epoch of creationNever retrieved by epoch 10Share of final-epoch retrievals
Epochs 1–366.94±0.59/95.24±0.4817.97±1.32/1.81±0.5380.30±0.41/45.10±0.83
Epochs 4–615.90±1.98/72.51±0.9563.08±1.05/16.19±0.2913.79±1.22/28.61±1.51
Epochs 7–108.42±0.96/43.49±3.1689.83±1.14/60.07±2.025.90±0.96/26.29±0.75

MemQ shows no lock-in: new memories are exposed quickly, and retrieval is spread across creation epochs. Two properties explain this. First, new memories inherit the mean Q-value of their parents (Sec. 4.1) and enter at about the 50th percentile of the bank's Q-values, versus the 19th–34th percentile under MemRL's fixed initialization. Second, MemQ's learned values are nearly independent of memory age (Spearman ρ between Q and age at epoch 10: 0.12±0.02 vs. 0.60±0.01 for MemRL), so value-based ranking does not systematically favor old memories. Since MemQ already provides the exposure a recency term would encourage, we did not add one; it remains compatible with MemQ's scoring rule, and we will discuss it as an extension.

  1. Separate quotas for successes and failures (Q2). Retrieved memories are already presented in separate prompt sections (successful approaches and failures to avoid), but retrieval ranks both types by the same learned score without fixed quotas (Sec. 4.2). The table shows the resulting mix on DSBench (MemQ, training split, %, mean±SD over three seeds):
MetricEpoch 1Epoch 10
Successful memories: share of bank65.81±2.7268.56±2.15
Successful memories: share of retrievals61.07±4.1673.26±0.94
Failure-derived memories: share of retrievals38.93±4.1626.74±0.94

Without quotas, failure lessons still make up about a quarter of retrievals, and 53.05% of tasks retrieve at least one in the final epoch. Meanwhile, the share of successful experiences among retrievals rises by 12.2 pp while their share of the bank rises by only 2.8 pp, so the learned values adapt the mix over training. A fixed quota would preclude this adaptation, although it could be combined with MemQ by ranking each type within its quota. We will discuss this as future work.

AuthorsOpenReview ↗

Response to Reviewer ZaZy (2/3)

W2 & Q1: The paper lacks a cross-benchmark OOD evaluation, so it is unclear whether learned Q-values, provenance credit, and procedural memories transfer across task distributions. Why not evaluate under a one-pass protocol in which the agent processes one task at a time and writes memory for the next? Does pre-collecting a memory bank on the training split create an unfair resource or information advantage over no-memory methods?

A2: Thank you for these questions on our evaluation protocol. We follow the protocol of the memory methods we compare with, including MemRL and MemP: memories are accumulated on a training split and evaluated on a disjoint held-out split, with the same backbone, splits, and budget for all methods.

  1. Transfer across task distributions (W2). Actually, our held-out splits already involve distribution shift, especially on DSBench. DSBench is split by challenge, and each challenge is a separate ModelOff case study with its own scenario, workbook, and rules. Memories are accumulated on 30 challenges and evaluated on 8 totally unseen ones, some with no counterpart in training, such as allocating vehicles across depots under transport and penalty costs, or counting valid words in a 267k-word dictionary. On these unseen challenges, MemQ achieves the best held-out SR (47.70% vs. 45.40% for the strongest baseline and 43.97% without memory, Table 1), indicating that its learned values and procedural memories transfer beyond the tasks they were built from.

    Following your suggestion, we further ran a cross-benchmark evaluation: the final DSBench memory banks are evaluated directly on the AutomationBench held-out set, with the same backbone (%, mean±SD over three seeds; No Mem. from Table 1):

SettingNo Mem.RAGSelf-RAGMem0MemPMemRLMemQ
DSBench→AutomationBench30.28±1.7433.33±3.0033.89±4.8835.00±4.4135.56±2.1036.67±0.8338.61±1.27

MemQ again performs best, 8.33 pp above No Mem. and 1.94 pp above MemRL, so its learned values and procedural memories also transfer across benchmarks. By the way, under larger shifts, MemQ's locality filter (Sec. 4.2) applies: when a task has low similarity to all stored memories, the candidate set is empty and the agent falls back to zero-shot solving, so unrelated memories are not imposed.

  1. One-pass evaluation (Q1). This is a helpful suggestion, and the first epoch of our runtime learning actually closely matches the one-pass protocol you describe: each training task is attempted once, and memories written from earlier tasks are available to later ones. Under this single pass over the 350 DSBench training tasks, with the same number of task attempts as No Mem., MemQ already leads (%, mean±SD over three seeds):
MethodOne-pass SRTasks 1–120Tasks 121–240Tasks 241–350
No Mem.58.76±0.87–––
RAG59.62±3.4460.00±1.6755.56±6.7463.64±4.81
Self-RAG61.43±1.7160.28±5.4258.33±4.1766.06±5.48
Mem060.76±2.5960.83±3.0058.89±5.0962.73±5.53
MemP60.76±3.1557.50±5.4658.89±6.1466.36±8.77
MemRL61.62±2.2259.44±3.9460.28±5.8565.45±4.55
MemQ65.81±2.7261.11±5.5565.28±3.4771.52±3.78

MemQ leads in every segment and improves steadily within the pass, from 61.11% on the first 120 tasks to 65.28% and 71.52% on the next two segments. Its advantage therefore already holds under the one-pass protocol, with the same task budget as No Mem., and does not rely on multiple epochs.

  1. Fairness (Q1). All memory-based methods use the same training split, number of epochs, batch size, and backbone, so their budgets are matched, and MemQ is compared primarily against them. No Mem. serves as a reference for the backbone's capability without memory rather than a budget-matched competitor. As for information leakage, memories come only from the training split, and no method sees a held-out task before it is evaluated on it.

Following your comments, we will (i) describe the challenge-level split of DSBench and list the challenges of each split in Appendix G, (ii) add the cross-benchmark and one-pass results and analysis to the appendix, and (iii) state in Sec. 5.1 that all memory-based methods share the same budget, with No Mem. serving as a capability reference.

AuthorsOpenReview ↗

Response to Reviewer ZaZy (3/3)

Q3: The paper does not report performance on Search-Agent tasks. It would be useful to add a Search-Agent benchmark covering search, fetch, and multi-step retrieval, and report held-out, runtime, and cumulative success rates.

A3: Thank you for this suggestion. Following it, we added experiments on HotpotQA. Since the full dataset is large, we randomly sampled 500 questions from its training set for runtime learning and 150 questions from its FullWiki development set for held-out evaluation, so that the experiments could be completed within the rebuttal period. In the FullWiki setting, the agent must search the entire Wikipedia corpus, fetch relevant pages, and integrate evidence across multiple documents through multi-hop reasoning, which makes it well suited for evaluating multi-step retrieval. We use three seeds and the same protocol as our main experiments, and no method is tuned specifically for HotpotQA.

MetricNo Mem.RAGSelf-RAGMemPMemRLMemQ
Runtime SR (500 tasks)71.53±0.3176.13±0.3176.73±0.3180.13±0.3182.80±0.4084.07±0.23
Cumulative SR (500 tasks)N/A77.27±0.5078.53±0.3182.33±0.2383.40±0.2084.53±0.12
Held-out SR (150 tasks)63.33±0.6765.78±1.5464.22±2.1466.00±1.7667.33±0.6768.22±0.77

MemQ achieves the best results on all three metrics. Compared with the strongest baseline, MemRL, it improves runtime SR by 1.27 pp, cumulative SR by 1.13 pp, and held-out SR by 0.89 pp, and it improves held-out SR over No Mem. by 4.89 pp. We will add these results to the revised manuscript.

Thank you again for your thoughtful review. Your suggestions on retrieval dynamics, memory organization, the evaluation protocol, and Search-Agent tasks have helped us examine MemQ's behavior more closely and broaden its evaluation. We will incorporate these analyses and the new cross-benchmark and HotpotQA results into the revised manuscript.

Reviewer_HwcHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces MemQ, a novel runtime learning framework for memory-augmented LLM agents which learns a non-parametric memory retrieval policy in memory-augmented generation tasks. Their method combines a similarity metric against task/trajectory embeddings and a running estimate of a memory's value estimate to select appropriate memories with which a frozen LLM uses to complete a task. Importantly, their memory value estimates are updated using eligibility traces over a given memory's structural ancestry, allowing them to more efficiently update several past memories without explicitly retrieving them in a given trajectory. Experiments on several benchmarks against multiple state-of-the-art baselines suggests MemQ to be a consistent improvement upon existing methods.

Critical strengths
  • The experiments are pretty exhaustive, and covers a wide range of relevant benchmarks and baselines, showing consistent results in favor of their suggested method: its average performance is higher than all other baselines in all benchmarks on both training and evaluation metrics, with no exception. These results demonstrate a strong conclusion that MemQ is indeed better than current state-of-the-art methods.

  • The proposed method is sound and seems easy to implement when compared to existing approaches such as MemRL. The addition of using eligibility traces for credit assignment is well-studied and used effectively in this work without adding a lot of unnecessary complexity both in terms of implementation and compute, making it an attractive method for future practitioners.

Critical weaknesses
  • The Exogenous-Context MDP problem formulation introduced in this work is not very easy to follow, and it is unclear whether its introduction and definitions add much to the paper's central results despite its place as a main contribution according to the authors. In its current state, the notation and definitions provided in this section seem disconnected from the rest of the paper, and made it more difficult to understand MemQ's contributions despite its conceptually simple motivation: applying eligibility traces to a memory's ancestry for more efficient credit assignment. I encourage the authors to further clarify this section and its contribution. For example, relating it to the existing problem formulation of an Memory-MDP [1], using a concrete example to explicitly ground the different definitions, or added discussions around why the additional formalism is important to their framework.

  • Outside of the theoretical contributions surrounding the Exogenous-Context MDP which is addressed above, MemQ is very closely related to MemRL and the paper seems to undersell this incremental relationship. The paper can benefit from making this relationship more explicit, and clarifying which parts of MemQ are novel and which are taken directly from prior work such as MemRL, which would further contextualize its place among the other baselines. As per my understanding, the main differences with MemRL is a bootstrapped target controlled with γ\gamma, an additional update rule for all retrieved memories' ancestors controlled with λ\lambda, and a smarter initialization of Q(mnew)Q(m_{new}) using its ancestors values instead of a fixed initialization. If this is the case, the ablations in section 5.3 and Appendix F.1 can be better contextualized with this in mind.

[1] Zhou, Huichi, et al. "Memento: Fine-tuning llm agents without fine-tuning llms." arXiv preprint arXiv:2508.16153 (2025).

Questions for authors
  • The number of seeds used for all experiments should be noted clearly, especially when providing statistics such as standard deviations which are relatively tight with many of the results. I assume the results in Table 1, Table 2 and the last column of Figure 4 are reported against three seeds based on the caption in Table 16, but that is not currently clear. If this is the case, standard deviations are difficult to interpret with such small sample sizes, and a min/max statistic can be represent a more straightforward statistic of your experiments.

  • Similarly, why are there only confidence intervals in the DSBench experiments of Figure 4? Were the other ablations run on a single seed?

  • How were the weights for mixing the similarity metric and q-values (wsw_s, wqw_q) chosen? Since this is shared with MemRL, were these hyper-parameters swept for both methods, or similar values were used in both cases? How sensitive is the method to the choice of this interpolation beyond either extremes of setting them to 0?

  • A central motivation for eligibility traces is improved credit assignment over longer trajectories. In the context of this work, this translates to better credit assignment over memories further down in the retrieval DAG's depth. Is there any evidence suggesting that MemQ is more likely to use older memories?

  • Lines 317-321 suggest an interesting hypothesis surrounding memory retrieval and model size. This would be interesting to substantiate further if true. The results in DSBench when comparing the No Mem. baseline versus memory retrieval baseliens such as MemRL seem to. suggest the opposite, where the memory-augmented agent actually performs worst.

  • Lines 428-431 state that MemQ uses memory more efficiently. Beyond the observed effect, could the authors provide an intuition as to why MemQ is more likely to be more token efficient in its retrieved memories? Or is there generally a negative correlation between better performance and number of tokens used across methods and hyperparameters that is not related to the mechanisms of MemQ?

8 comments
AuthorsOpenReview ↗

Response to Reviewer HwcH (1/3)

Dear Reviewer HwcH,

We sincerely thank you for the careful review and constructive suggestions. To keep tables inline for easier reading, we split our response into three comments.

W1: The EC-MDP formulation is hard to follow and seems disconnected from the rest of the paper. Please clarify its contribution, e.g., by relating it to the Memory-MDP [1], grounding it with a concrete example, or explaining why the formalism matters.

A1: Thank you for this constructive suggestion. We will add a paragraph at the end of Sec. 3 to handle this. The EC-MDP mainly serves the derivations in Appendix B, so its role in the method is not visible in the main text. Concretely, it is what grounds MemQ's design:

  1. Bootstrapping through the new memory. Because the next task is drawn exogenously (Eq. 1), a retrieval cannot affect future tasks, only the memory store. Its long-term value therefore flows through the memory it helps create, which gives the target Rj+γQ(mnew,j)R_j+\gamma Q(m_{\mathrm{new},j}) in Eq. 5 and, recursively, credit along provenance edges.
  2. Per-memory values. With the memory store in the state, the action value is a function of the retrieved set, which yields the first-order decomposition in Eq. 3 that MemQ learns.
  3. Theory. The memory-lineage Bellman operator, its fixed point, and the convergence results in Appendix B are all defined on this process.

Relation to the M-MDP of Memento [1]. The M-MDP ⟨S,A,P,R,γ,M⟩\langle\mathcal S,\mathcal A,\mathcal P,\mathcal R,\gamma,\mathcal M\rangle augments an environment MDP with a case bank. A case-retrieval policy μ(c∣s,M)\mu(c\mid s,M) is learned by soft Q-learning over Q(s,M,c)Q(s,M,c), while the next state follows the action-dependent dynamics P(⋅∣s,a)\mathcal P(\cdot\mid s,a). The EC-MDP differs in two ways. (i) Tasks arrive exogenously, so the memory store is the only state component the agent affects; this factorization yields the bootstrap through mnewm_{\mathrm{new}}. (ii) Values are attached to individual memories rather than to state–case pairs, and set-valued retrieval is handled by the decomposition in Eq. 3.

We will add a paragraph at the end of Sec. 3 linking the EC-MDP to Eqs. 3 and 5 and Appendix B, and add a worked example together with the comparison to the M-MDP in the appendix.

W2 & Q3: MemQ is closely related to MemRL; clarify which parts are new (as I understand it, the γ-controlled bootstrap target, the λ-controlled ancestor update, and parent-based initialization of Q(mnew)Q(m_{\mathrm{new}})) and frame the ablations accordingly. How were the shared weights wsw_s and wqw_q chosen, were they swept for both methods, and how sensitive is MemQ to them beyond setting either to 0?

A2: Thank you for this suggestion. Your understanding of the differences from MemRL is correct.

  1. Relationship with MemRL (W2). The table below lists the components of all compared methods.
MethodProcedural memoryLearned value in retrievalBootstrapped target (γ\gamma)Multi-depth DAG credit (λ\lambda)Parent-based adaptive Q(mnew)Q(m_{\mathrm{new}}) init.
RAG✗✗✗✗✗
Self-RAG✗✗✗✗✗
Mem0✗✗✗✗✗
MemP✓✗✗✗✗
MemRL✓✓✗✗✗
MemQ✓✓✓✓✓

Self-RAG and Mem0 focus on per-query critique and memory curation, respectively, which are orthogonal to value learning. MemQ builds on MemRL's procedural memory and value-aware retrieval; its new components are the last three columns and the EC-MDP formulation. The ablations isolate each: γ=0\gamma=0 (Sec. 5.3) removes bootstrapping and multi-depth credit, λ=0\lambda=0 removes only multi-depth credit, and Appendix F.1 isolates parent-based initialization. We will add this table to Appendix C alongside the baseline descriptions, and frame Sec. 5.3 and Appendix F.1 around these three components.

  1. Choice and sensitivity of wsw_s/wqw_q (Q3). For MemQ, we swept ws∈{0,0.2,0.4,0.6,0.8,1.0}w_s\in\{0,0.2,0.4,0.6,0.8,1.0\} with wq=1−wsw_q=1-w_s. Since both weights lie in [0,1][0,1], this uniform grid covers the full range without requiring a prior. For MemRL, whose paper reports the best performance around wq=0.5w_q=0.5, we tested several settings around this value and selected the best-performing one.

    Appendix F.6 (Tables 4–5) shows that performance degrades at either endpoint but is comparatively stable across interior mixtures. In final runtime SR, every interior mixture exceeds both endpoints on both benchmarks (LCB: 58.57–61.79% vs. 52.86%/55.00%; BFCL: 67.17–73.60% vs. 61.56%/65.75%). With wq=0w_q=0, retrieval ignores the learned values, so the values evolved by MemQ are never used; with ws=0w_s=0, retrieval may select high-value but less relevant memories, violating local consistency. The two signals are thus complementary. We will state the tuning procedure of both methods in Appendix G.


[1] Zhou, Huichi, et al. "Memento: Fine-tuning llm agents without fine-tuning llms." arXiv preprint arXiv:2508.16153 (2025).

AuthorsOpenReview ↗

Response to Reviewer HwcH (2/3)

Q1 & Q2: State the number of seeds for all experiments. If Tables 1–2 and the last column of Fig. 4 use three seeds, standard deviations are hard to interpret and min/max may be clearer. Why does only DSBench in Fig. 4 show confidence intervals; were the other ablations single-seed?

A3: Thank you for pointing this out. The missing seed information is an oversight in our writing.

  1. Number of seeds. Your reading is correct: the main experiments (Tables 1–2), the ablations in Fig. 5a, and the DSBench column of Fig. 4 use three seeds, while only the LCB and BFCL sweeps in Fig. 4 use one seed per setting. We will state this in the captions. These sweeps characterize how performance varies with γ\gamma and λ\lambda; the method comparisons rest on the three-seed results in Tables 1–2. Moreover, the main finding of the sweeps, that intermediate trace decay works best, holds on all three benchmarks, including the three-seed DSBench sweep (70.29% at λ=0.5\lambda=0.5 vs. 65.81% at λ=0\lambda=0 and 64.95% at λ=0.9\lambda=0.9).

  2. Statistics with three seeds. Using three seeds follows the protocol of prior work such as MemRL, and balances statistical reliability against cost: our experiments run multi-turn agents with large backbones (up to 284B parameters), and a single MemQ run on DSBench alone consumes about 313M LLM tokens over 10 training epochs (Table 16). We believe three seeds are sufficient for our conclusions, since they rest on a consistent pattern rather than any single comparison: MemQ attains the highest mean held-out, final runtime, and cumulative SRs on all eight benchmarks.

  3. SD vs. min/max. We agree that min/max can be more intuitive. With three seeds, however, the SD conveys essentially the same spread: the range (max − min) always lies between 3\sqrt{3} and 22 times the sample SD. Reporting the mean, min, and max for every method and benchmark would not fit the main tables, so we report mean±SD, together with 95% confidence intervals for the averages.

Q4: Eligibility traces should improve credit assignment for memories deeper in the DAG. Is there evidence that MemQ is more likely to use older memories?

A4: Thank you for this insightful question. We analyzed the final-epoch memory banks on DSBench for MemQ and MemRL, three seeds each, grouping memories by the epoch in which they were created (MemRL/MemQ per cell, %, mean±SD over three seeds):

Created inQ-value changed in final epochChanged but not directly retrievedRetrieved at least onceShare of retrievals
Epochs 1–353.16±1.53/95.17±1.140.00±0.00/33.50±1.5658.11±1.32/63.30±2.1980.30±0.41/45.10±0.83
Epochs 4–611.21±0.88/73.59±1.050.00±0.00/40.26±2.2914.73±0.57/43.97±2.0013.79±1.22/28.61±1.51
Epochs 7–104.76±0.67/43.97±0.850.00±0.00/24.10±2.275.41±1.01/27.29±0.075.90±0.96/26.29±0.75
  1. The values of older memories stay up to date. In the final epoch, 95.17% of MemQ's oldest memories (created in epochs 1–3) still change value, versus 53.16% for MemRL. Among these, 33.50% are not retrieved in that epoch and are updated through credit from their descendants. Under MemRL, a memory's value changes only when it is retrieved (0.00%).
  2. Older memories remain in use without crowding out new ones. MemQ retrieves a larger fraction of its oldest memories at least once in the final epoch (63.30% vs. 58.11%). MemRL concentrates 80.30% of its retrievals on these oldest memories and rarely uses those created after epoch 6 (5.90%), whereas MemQ spreads retrieval across ages. In short, MemQ does use more of its older memories, but in proportion to their current value rather than their age.

We will add this analysis to Appendix E.

AuthorsOpenReview ↗

Response to Reviewer HwcH (3/3)

Q5: Lines 317–321 hypothesize that stronger models benefit more from memory retrieval. On DSBench, however, memory baselines such as MemRL underperform No Mem., which seems to suggest the opposite.

A5: Thank you for the careful reading.

  1. Model size. Thank you for pointing this out. You are right that this is only a hypothesis so far. It came from an observation in our results: MemQ's two largest held-out margins occur on DSBench and AutomationBench, the two benchmarks using the 284B DeepSeek backbone. We agree that confirming it requires a controlled study across model sizes. We would very much like to run such a study, but given the cost of agentic benchmarks with multiple large backbones, it cannot be completed within the rebuttal period. We will revise lines 317–321 to state it explicitly as a hypothesis and include it in the discussion.

  2. MemRL below No Mem. on DSBench. This is a good catch, and it has to do with how DSBench is split. Each challenge is a separate case study with its own scenario and data, and we accumulate memories on 30 challenges and evaluate on 8 totally unseen ones (Appendix G). On the accumulation split, MemRL clearly outperforms No Mem. (final SR 68.00% vs. 58.36%, Table 2); the drop appears only on unseen challenges. There, retrieved memories can hurt rather than help: memories built for other challenges may not fit the new scenario, yet they still enter the agent's context, where agents tend to follow retrieved experience closely [2] and irrelevant context distracts LLMs [3]. No Mem. is not exposed to this interference, so whether memory helps on unseen challenges depends on which memories are retrieved. MemRL values a memory only by the immediate outcome of the tasks it was retrieved for, so its highest-valued memories are those that worked on the accumulation challenges, and each retrieval further reinforces their values. MemQ also credits a memory when memories derived from it later succeed on other tasks, favoring experience that remains useful beyond its original tasks. Consistent with this, MemQ improves over No Mem. by 3.73 pp on the held-out challenges, whereas MemRL falls 1.44 pp below it. We will add this discussion to Sec. 5.2.

Q6: Lines 428–431 claim MemQ uses memory more efficiently. Why would MemQ be more token-efficient, or is better performance generally associated with fewer tokens regardless of method?

A6: Thank you for this insightful question, which prompted us to pin down where MemQ's token savings come from.

By propagating credit along provenance chains, MemQ learns memory values both faster and more accurately than single-step updates: each outcome also updates the ancestors of the retrieved memories, and values reflect a memory's downstream contribution rather than only its immediate outcome (MemQ's Q-values predict subsequent task success, Pearson r=0.640r=0.640, Sec. 5.4). Retrieval thus concentrates earlier on memories that lead to correct solutions, and the agent spends fewer turns on incorrect attempts. Consistently, most savings come from input tokens (280.68M for MemQ vs. 317.11M for MemRL and 340.01M for MemP; Table 16), which grow with the number of turns as each turn re-sends the accumulated context.

As for the general phenomenon, we found that spending more tokens does not necessarily lead to better performance, and can even hurt: prior work shows that low-quality accumulated experience can propagate errors in memory agents [2], irrelevant context easily distracts LLMs [3], and longer reasoning can lower accuracy [4]. In our case, MemP, MemRL, and MemQ use the same procedural memory pipeline on DSBench, so the token gap comes from how MemQ values and selects memories, not from a generic link between tokens and performance.

We will add this explanation and these references to Sec. 5.4.

Once again, we sincerely thank you for the careful reading and constructive suggestions. Your comments on the role of the EC-MDP, the relationship with MemRL, the statistical reporting, and the mechanisms behind MemQ's gains have helped us present the paper more clearly and ground its claims more carefully. We will incorporate these clarifications and analyses into the revised manuscript.


[2] Xiong, Zidi, et al. "How Memory Management Impacts LLM Agents: An Empirical Study of Experience-Following Behavior." arXiv preprint arXiv:2505.16067 (2025).

[3] Shi, Freda, et al. "Large Language Models Can Be Easily Distracted by Irrelevant Context." ICML (2023).

[4] Gema, Aryo Pradipta, et al. "Inverse Scaling in Test-Time Compute." TMLR (2025).

Reviewer_ctXqOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MemQ, a reinforcement learning framework for episodic memory in LLM agents. Unlike prior methods that evaluate memories in isolation without temporal credit assignment, MemQ constructs a provenance DAG to track how existing memories enable the creation of new ones. However, this also means that the performance of this method can be highly dependent on the extracted DAG. It propagates TD eligibility traces backward along this graph using structural depth rather than time steps to reward ancestor memories. Evaluated across diverse interaction, coding, and agentic benchmarks, MemQ generally shows consistent performance gains over existing memory baselines.

Critical strengths

After careful consideration, I think the paper has the following strengths. The first is that this paper proposes these ancestor memories, which can be a novel concept that can provide insights into how the reward should be provided, given to the specific earlier memories instead of only the current memory.

1 Principled Credit Assignment: Adapting eligibility traces to a provenance DAG provides a sound and very intuitive mechanism for rewarding ancestor memories that enable downstream success.

2 Clean MDP Formulation: The Exogenous-Context MDP formalization cleanly separates external environment tasks from internal memory evolution.

3 Empirical Validation: The method demonstrates consistent gains across diverse interactive and agentic benchmarks, supported by meaningful depth ablations.

Critical weaknesses

As I mentioned before, the critical weakness is still centered on the DAG extracted. Since the reward is calculated based on the DAG, this quality can be very important.

Additionally, since this is a long-horizon reward, questions can also be raised about scalability. The details are as follows:

1 Long-Horizon Scalability: The paper lacks analysis of the memory footprint and runtime latency of recursive DAG updates as the graph grows over extended deployments.

2 Additive Set Assumption: Decomposing the value of a retrieved memory set into a linear sum of individual values overlooks potential synergies or redundancies among co-retrieved items. A potential way is to maybe further explore the correlations with some nonlinear estimations about these values in the set.

3 Risk of Credit Misallocation: Success-driven backward propagation might inadvertently reinforce irrelevant ancestor memories that happened to be co-retrieved during intermediate steps. So this kind of analysis can be important for the irrelevant memories. It is still centered on the same question: How can we ensure the quality of the DAG, and if some of the edges or the connections in the DAG are incorrect, how would this credit reward affect the training process?

Questions for authors

What is the general computational cost for this as this DAG grows larger and larger, and how do we ensure the quality?

5 comments
AuthorsOpenReview ↗

Response to Reviewer ctXq

Dear Reviewer ctXq,

We sincerely thank you for the careful review and constructive suggestions.

W1 & Q1 (cost): What are the memory footprint and runtime latency of recursive DAG updates as the graph grows over extended deployments?

A1: The short answer is, DAG maintenance adds negligible overhead. We measured it from the training logs of 27 DSBench runs (main and ablation experiments, 10 epochs each); per-epoch statistics are in Table R1 below. As the bank grows from 350 to 3,500 memories, the DAG update time rises from 0.041 s to 0.292±0.123 s per epoch, and the DAG index reaches 0.646 MiB, negligible compared with LLM inference. We will add this analysis to Appendix B.4.

Table R1. Per-epoch DAG update cost on DSBench (27 runs, mean±SD; SD<0.001 MiB for index memory). Times include bookkeeping. Index memory covers only the DAG structure, excluding memory content, embeddings, and caches, which are shared by all memory-based methods and are not introduced by the DAG.

Epoch#Memories#Updated memoriesAvg. ΔQ contributions per memoryDAG computation (s)Q-value writeback (s)Total DAG update (s)DAG index memory (MiB)
1350.0±0.0240.1±4.027.62±8.420.014±0.0070.023±0.0450.041±0.0470.050
2700.0±0.2530.8±3.832.70±10.820.054±0.0250.030±0.0370.086±0.0430.105
31049.9±0.3827.8±8.330.04±10.140.064±0.0300.029±0.0090.096±0.0370.176
41399.9±0.31097.7±37.225.65±8.730.079±0.0310.081±0.0760.163±0.0890.272
51749.9±0.31358.8±69.722.49±7.690.085±0.0290.093±0.0810.182±0.0910.318
62099.9±0.31600.4±109.320.42±6.970.090±0.0180.117±0.1070.212±0.1110.363
72449.9±0.41766.7±164.719.13±6.520.100±0.0310.165±0.1320.269±0.1350.408
82799.9±0.41920.0±205.918.14±6.210.122±0.0710.144±0.1090.271±0.1180.555
93149.9±0.42066.2±263.517.29±5.900.105±0.0370.132±0.1090.246±0.1330.601
103499.9±0.42208.5±328.116.42±5.570.103±0.0240.183±0.1120.292±0.1230.646

W3 & Q1 (quality): Backward propagation may reinforce irrelevant ancestors that were merely co-retrieved. How can DAG quality be ensured, and how would incorrect edges affect credit assignment and training?

A2: A provenance edge records that a retrieval occurred, parents(mnew,j)=Aj\mathrm{parents}(m_{\mathrm{new},j})=A_j (Sec. 4.3), i,e., it does not assert that the parent was useful. Edges are therefore not incorrect per se. The actual risk you might want to ask is credit misallocation: an unhelpful memory credited for a success, or a useful one penalized for a failure.

MemQ mitigates this through aggregation. A memory receives TD contributions from multiple retrieval events, both directly and through its descendants, and these are averaged before an update (Sec. 4.3): Q(m)←Q(m)+clip⁡(ΔQ(m)Nm,−ϵclip,ϵclip),Q(m)\leftarrow Q(m)+\operatorname{clip}\left(\frac{\Delta Q(m)}{N_m},-\epsilon_{\mathrm{clip}},\epsilon_{\mathrm{clip}}\right), where ΔQ(m)\Delta Q(m) sums the depth-weighted TD contributions and NmN_m counts them. In the DSBench runs of Table R1, each updated memory receives 16.42–32.70 contributions per epoch on average. Averaging over these signals reduces the effect of any single misleading outcome, and depth decay (γλ)d(\gamma\lambda)^d and clipping bound each contribution.

We will clarify the edge semantics and this aggregation in Sec. 4.3.

W2: Averaging individual memory values ignores synergy or redundancy among co-retrieved memories; nonlinear set-value estimation could be explored.

A3: Thank you for this insightful point. We agree that co-retrieved memories can help or hurt each other, and averaging their individual values does not capture this. We write the approximation out explicitly in Eq. 3: Qπ(s,A;M)=1∣A∣∑m∈Aqπ(m)+ξπ(s,A;M),Q^\pi(s,A;\mathcal M)=\frac{1}{|A|}\sum_{m\in A}q^\pi(m)+\xi^\pi(s,A;\mathcal M), where the residual ξπ\xi^\pi is exactly the synergy, redundancy, or distraction you describe. MemQ learns only the first term.

Proposition B.2 (Appendix B.3) bounds what this costs. If ∣ξπ∣≤εint|\xi^\pi|\le\varepsilon_{\mathrm{int}} over the candidate sets, the selection regret is at most 2εint2\varepsilon_{\mathrm{int}}, and MemQ still picks the optimal set whenever it leads the others by more than 2εint2\varepsilon_{\mathrm{int}}. Put simply, averaging works well as long as interactions are small compared with the value gaps between candidate sets. When interactions are strong, a nonlinear set-value model as you suggest is the natural extension. We will make this scope explicit in Sec. 3 and emphasize it in the theoretical analysis (Appendix B.3).

We sincerely thank you for your positive assessment and thoughtful questions. Your comments on DAG scalability, credit assignment, and set-value interactions have helped us make the cost, behavior, and scope of MemQ clearer. We will incorporate these analyses and clarifications into the revised manuscript.

AuthorsOpenReview ↗

Revised Manuscript: Locations of Changes

Dear Reviewer ctXq,

We have uploaded the revised manuscript, with all new and revised content in blue. For your convenience, here is where each of our answers is reflected:

  • A1 (DAG cost): Appendix B.4 now reports the measured per-epoch DAG cost over 27 DSBench runs (Table 6, our Table R1).
  • A2 (DAG quality and credit misallocation): The edge semantics and the effect of aggregation are discussed in Appendix B.2 ("Edge semantics and credit misallocation"), where they build on the update rule and fixed point of the convergence analysis; the measured contribution counts are in Appendix B.4. We placed this discussion in the theoretical analysis rather than in Sec. 4.3 so that it could be stated in terms of these results.
  • A3 (set-value interactions): Sec. 3 now states the scope of the first-order approximation, and Appendix B.3 emphasizes when it is adequate and how a nonlinear set-value model would extend it.
AuthorsOpenReview ↗

We kindly inquire if the reviewer has any further comments or concerns regarding our responses

Dear reviewer ctXq,

We sincerely appreciate the time and effort you dedicated to our work and we have made every effort to address your concerns in our rebuttal submission. As the discussion deadline approaches, we want to kindly follow up to ask whether you have any remaining questions or concerns regarding our responses. Your insights are highly valued, and we want to ensure that all your points have been fully and adequately addressed. If you feel that our responses have resolved your concerns, we would be grateful if you could reflect that in your final evaluation of the manuscript.

Thank you again for your thoughtful and constructive feedback and support throughout this process. We look forward to hearing from you.

Best regards,

Authors

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Revisions in the Revised Manuscript

Dear Area Chair and Reviewers,

We have uploaded the revised manuscript, with all new and revised content shown in blue; changes made after the first revision, in response to the follow-up discussion, are shown in red. The table below lists each change, the reviewer comment that motivated it, and its location in the revision.

ChangeReasonLocation
Edge semantics and why aggregation limits credit misallocation; measured DAG costctXq W1/W3/Q1App. B.2; App. B.4 (Table 6)
Scope of the first-order set-value approximationctXq W2Sec. 3; App. B.3
Transition paragraph on how MemQ follows from the EC-MDP; comparison with the Memory-MDP and a worked exampleHwcH W1Sec. 3; App. B.5
Component table of all compared methods; ablations framed around MemQ's three componentsHwcH W2App. C (Table 7); Sec. 5.3; App. F.1
Seed counts in the captions of Tables 1–2 and Figs. 4–5HwcH Q1/Q2Sec. 5
Grid of the retrieval-weight sweepHwcH Q3App. F.6
Value updates and retrieval of memories by creation epoch; success/failure memory mixHwcH Q4, ZaZy W1/Q2Sec. 5.4 (Table 3); App. E.1 (Tables 8–9)
Model-size explanation stated explicitly as a hypothesisHwcH Q5Sec. 5.2
Generalization to unseen DSBench challenges, MemRL vs. No Memory, and cross-benchmark transferHwcH Q5, ZaZy W2Sec. 5.2; App. G.3 (Table 16); App. H (Table 26)
Explanation of MemQ's token savings; coverage and token tables moved to the main textHwcH Q6Sec. 5.4 (Tables 4–5)
Sources of the token savings (retrieved-context length, turns) and training cost (red)HwcH follow-upSec. 5.4 (Table 5); App. E.2 (Table 10)
Shared evaluation protocol and one-pass resultsZaZy Q1App. C; App. G.4 (Table 17)
HotpotQA results and hyperparametersZaZy Q3App. G.2 (Table 15); App. H (Table 28)
Limitations and future directionsctXq W2, HwcH Q5, ZaZy W1/Q2App. J

Sincerely,

The Authors

AuthorsOpenReview ↗

Meta Response

Dear Area Chair and Reviewers,

We sincerely thank all reviewers for their careful reading and constructive feedback. In the discussion, all three reviewers maintained their positive assessments: ctXq appreciated the additional results, HwcH agreed that the EC-MDP plays an important theoretical role and found the experimental results strong, and ZaZy confirmed that our responses adequately addressed all of their concerns and recommends acceptance.

In their reviews, the reviewers found the provenance-DAG credit assignment principled and intuitive (ctXq, HwcH, ZaZy), the EC-MDP formulation clean (ctXq), the method easy to implement without unnecessary complexity (HwcH), and the evaluation extensive, with consistent gains across benchmarks (HwcH, ZaZy). We summarize the main points of the discussion below; the changes in the revised manuscript are listed in a separate comment titled "Summary of Revisions in the Revised Manuscript".

Summary of the discussion

  1. Negligible DAG overhead (ctXq). Across 27 DSBench runs, DAG maintenance takes 0.29 s per epoch and 0.65 MiB at 3,500 memories, negligible compared with LLM inference.
  2. Robust credit assignment (ctXq). Each updated memory aggregates 16–33 depth-weighted contributions per epoch, so no single misleading outcome dominates its value, and depth decay and clipping bound each contribution.
  3. Clear scope of the set-value approximation (ctXq). Proposition B.2 bounds the selection regret by twice the interaction magnitude, so MemQ still selects the optimal retrieval set whenever interactions among memories are small relative to the value gaps between candidate sets.
  4. From one-step to multi-step memory values, grounded in the EC-MDP (HwcH). Prior value-based memory agents learn each memory's value only from the immediate outcome of retrieving it. The EC-MDP shows that, since tasks arrive exogenously, a retrieval affects the future only through the memory it helps create. MemQ therefore values each memory by its long-term contribution through the memories it produces, a step analogous to that from bandits to Bellman-based RL. Its three key components, bootstrapped value estimation, provenance-based credit assignment, and parent-based adaptive initialization, follow from this view, are each isolated by an ablation, and come with convergence guarantees on this process.
  5. Older memories stay current without lock-in (HwcH, ZaZy). Credit through the DAG keeps older memories up to date: in the final epoch, 95.17% of MemQ's oldest memories still change value, vs. 53.16% for MemRL. MemQ's values are nearly independent of memory age (Spearman ρ = 0.12 vs. 0.60 for MemRL), so retrieval spreads across creation epochs, and the learned values adapt the mix of successful and failure-derived memories during training.
  6. Lower training cost (HwcH). A per-call analysis of the DSBench training logs traced MemQ's token savings to shorter retrieved context. MemQ's higher SRs come with 11% fewer tokens and 13% lower API cost per training run than MemRL (Table 5, Appendix E.2).
  7. Generalization across tasks and benchmarks (HwcH, ZaZy). On the 8 unseen DSBench challenges, MemQ improves over No Memory by 3.73 pp, while MemRL falls 1.44 pp below it. DSBench memory banks also transfer directly to AutomationBench, where MemQ performs best (38.61% vs. 36.67% for MemRL and 30.28% without memory). Under the one-pass evaluation suggested by ZaZy, where each task is attempted once with the same task budget as No Memory, MemQ also leads all baselines (65.81% vs. 61.62% for the strongest baseline).
  8. Effectiveness on Search-Agent tasks (ZaZy). On HotpotQA (FullWiki), a Search-Agent benchmark added as suggested by ZaZy, MemQ achieves the best runtime, cumulative, and held-out SRs without any tuning for this benchmark, improving held-out SR over No Memory by 4.89 pp.

Together with the highest mean held-out, final runtime, and cumulative SRs on all eight benchmarks, we believe these results further support MemQ's effectiveness and generality.

We thank the reviewers again for their thoughtful comments, which have helped us improve the paper.

Sincerely,

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.