- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies whether memory-based trial-and-error learning reliably improves language agents beyond simply trying again under a finite trial budget. It introduces VRL-Bench, an evaluation harness (not a new dataset) that matches trial and interaction budgets across strategies while preserving each strategy's own cross-trial update, using memory-free retry as the no-update reference. Across three models (DeepSeek-V4-Flash, GPT-5.4 nano, GLM-4.7-FlashX) on MiniWoB and WebShop with T=6, the paper finds that none of the evaluated existing verbal updates like reflextion consistently outperforms retry as each helps in some settings and hurts in others, with the direction depending on the model. A controlled replay-exposure sweep on AlfWorld and HotPotQA separates having a reflection from using it, revealing an exploration-exploitation trade-off where reflection's early advantage can disappear and different schedules recover complementary failures. The paper then proposes VEX2, which uses an LM to jointly select policies and allocate the remaining trial budget; VEX2 is the only evaluated update with positive retry-relative SR@6 point estimates and lower censored AvgT@6 in all six settings.
Critical strengths
- The question is important and the result is counterintuitive and well-executed.
- VRL-Bench's fairness protocol is clean. They share the realized T1, matching trial and interaction budgets, defining reset-without-rollback, and preserving each strategy's own update together isolate what learning across attempts adds beyond another chance. This is a reusable contribution.
- The replay-exposure sweep is an elegant controlled intervention. Varying exposure probability epsilon while continuing to write memory cleanly separates 'having a reflection' from 'using it to guide each attempt', and the analysis provided evidence for the EE trade-off.
- VEX2 is a concrete and practical response to the diagnosed trade-off, jointly deciding policy selection and budget allocation in one LM response, and it produces positive point estimates in all six settings with lower AvgT@6 everywhere.
Critical weaknesses
- The baselines DC-Cu* and ACE* are ADAPTED versions (within-case failures only, memory reset between cases), not the original methods as published. The negative result may therefore partly reflect the adaptation rather than the methods themselves; the paper would be stronger with a matched-budget comparison against the original setups, or at least a clearer statement of how much the adaptation changes behavior.
- VEX2 is the authors' own method, so tuning effort and prompt engineering are unlikely to be equal across conditions. The claim that VEX2 is "the only evaluated update with positive gains in all six settings" should be tempered.
- The replay sweeps use a different Actor (GPT-4o-mini) and different task sets (AlfWorld, HotPotQA) from the main experiments, so they establish schedule sensitivity rather than a result transferable to the primary settings. The link between the sweep's diagnosis and VEX2's design is suggestive but not directly validated in the same configurations.
Questions for authors
- Can you report the original (unadapted) Dynamic Cheatsheet and ACE under matched trial/interaction budgets, to separate "the adaptation weakens them" from "the methods do not help"?
- How robust is VEX2's semantic policy tree and advisory allocation to using a different scheduler LM or a different prompt author? A small ablation would address W4.
Before discussion closes, we follow up on our 9 November response, which has not yet received further feedback.
Determining whether memory actually enables agents to benefit from past failures is essential to fair evaluation of future memory research. Our Datasets and Benchmarks contribution builds on three stages of evidence.
D/G/L denote DeepSeek-V4-Flash/GPT-5.4 nano/GLM-4.7-FlashX; M/W denote MiniWoB/WebShop.
1. Controlled evaluation reveals that memory updates can hurt recovery.
M covers 64 task families × 10 paired seed sequences/model (Synapse [4] task-count scale); W covers 100 goals/model (Reflexion [1] scale). Actor, cases, shared T1, resets, T=6 and interaction limits are matched. DC-Cu*/ACE* [2–3] are failure-only within-case adaptations; memory resets between cases.
ΔSR@6 vs Retry, pp [95% paired CI] — Table 7
None of these updates consistently beats Retry; some regressions have CIs excluding zero. Standard Reflexion’s mixed results are independent of the adaptations.
Token budgets and evaluation.
Retry has the lowest observed mean token use in all six settings, yet still outperforms memory updates in some settings. On W–L, Retry achieves 50% with 46,880 tokens; DC-Cu* achieves 39% with 109,954, a statistically supported regression.
Mean total tokens/instance — Tables 11–12
Tokens include provider-reported prompt+completion usage for action and memory-update calls, with early stopping. Our protocol matches trial and per-trial interaction budgets and reports token costs separately. A token cap requires an allocation/stopping policy; truncating reflections, cheatsheets or policy trees changes the mechanism being evaluated.
2. Further investigation of Reflexion reveals sensitivity to memory use.
We revisit Reflexion’s AlfWorld/HotPotQA task settings with GPT-4o mini (N=134/100; T=6/5). Actor, reflection writer, cases, T1 and limits are fixed. ε is the probability of withholding reflection. Interior conditions continue writing; endpoints reuse full-replay/no-memory runs.
Complete exposure grid: terminal SR% — Table 15
Revisiting these settings with a newer model reveals a different pattern: greater memory exposure does not consistently improve recovery. HotPotQA’s replay-minus-no-replay difference is −1.0 pp (95% CI [−5.0,3.0]). On AlfWorld, ε=.25 improves mean cumulative SR over no replay by 7.1 pp [0.9,13.3], with fixed-grid selection adjustment (Table 4).
Schedules recover complementary failures: best-single/union recovery counts are 33/49 on AlfWorld and 14/18 on HotPotQA (Figure 7). This investigation identifies an empirical exploration–exploitation tension.
3. VEX² empirically tests the resulting design direction.
VEX² is an LM-based exploration–exploitation scheduler, jointly generating a policy tree, trial allocation and guidance.
ΔSR@6, pp [95% CI]; censored AvgT@6 — Tables 6, 8
All six Retry-relative point estimates are positive; four CIs exclude zero. In table order, gains over the strongest existing baseline are 4.5/1.1/1.4/2.0/1.0/8.0 pp (Table 2).
The comparison with Reflexion evaluates this integrated scheduling policy. An input-matched next-step-only variant would provide a further ablation.
We will maintain VRL-Bench as a long-term open-source resource, including prompts, per-case results and analysis code. We believe this evidence merits renewed consideration and would appreciate your final assessment and any specific remaining concerns before discussion closes.
[1] Shinn et al. Reflexion. NeurIPS, 2023.
[2] Suzgun et al. Dynamic Cheatsheet. EACL, 2026.
[3] Q. Zhang et al. Agentic Context Engineering. ICLR, 2026.
[4] Zheng et al. Synapse. ICLR, 2024.