- 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
- 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.
- 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
- 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. - 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
- 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?
- 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?
- 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
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.
-
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):
| Setting | No Mem. | RAG | Self-RAG | Mem0 | MemP | MemRL | MemQ |
|---|---|---|---|---|---|---|---|
| DSBench→AutomationBench | 30.28±1.74 | 33.33±3.00 | 33.89±4.88 | 35.00±4.41 | 35.56±2.10 | 36.67±0.83 | 38.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.
- 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):
| Method | One-pass SR | Tasks 1–120 | Tasks 121–240 | Tasks 241–350 |
|---|---|---|---|---|
| No Mem. | 58.76±0.87 | – | – | – |
| RAG | 59.62±3.44 | 60.00±1.67 | 55.56±6.74 | 63.64±4.81 |
| Self-RAG | 61.43±1.71 | 60.28±5.42 | 58.33±4.17 | 66.06±5.48 |
| Mem0 | 60.76±2.59 | 60.83±3.00 | 58.89±5.09 | 62.73±5.53 |
| MemP | 60.76±3.15 | 57.50±5.46 | 58.89±6.14 | 66.36±8.77 |
| MemRL | 61.62±2.22 | 59.44±3.94 | 60.28±5.85 | 65.45±4.55 |
| MemQ | 65.81±2.72 | 61.11±5.55 | 65.28±3.47 | 71.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.
- 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.
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.
| Metric | No Mem. | RAG | Self-RAG | MemP | MemRL | MemQ |
|---|---|---|---|---|---|---|
| Runtime SR (500 tasks) | 71.53±0.31 | 76.13±0.31 | 76.73±0.31 | 80.13±0.31 | 82.80±0.40 | 84.07±0.23 |
| Cumulative SR (500 tasks) | N/A | 77.27±0.50 | 78.53±0.31 | 82.33±0.23 | 83.40±0.20 | 84.53±0.12 |
| Held-out SR (150 tasks) | 63.33±0.67 | 65.78±1.54 | 64.22±2.14 | 66.00±1.76 | 67.33±0.67 | 68.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.
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.
A1: Thank you for both suggestions.
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.
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.