acceptodds
Under review as a conference paper at ICLR 2027

VRL-Bench: Benchmarking agents on computer control tasks under finite trial budgets

Abstract

Learning from trial and error is a promising way to improve language agents on complex tasks such as computer control. Reflexion introduced verbal reinforcement learning, which turns failed trials into text that guides later attempts without updating model parameters. We introduce VRL-Bench, a harness for fair evaluation of trial-and-error learning under finite trial budgets. Across three models on MiniWoB and WebShop, we evaluate updates from several prominent verbal-memory methods spanning Reflexion and later work: each improves observed success over memory-free retry in some settings but reduces it in others. Replay experiments show that using reflection can reduce success rates, revealing a trade-off between exploiting experience and continued exploration. We propose VEX², a verbal exploration–exploitation scheduler that uses a language model to jointly select policies and allocate the remaining trial budget. VEX² is the only evaluated update to achieve positive observed success-rate gains over retry in all six settings.

Primary area:
datasets and benchmarks
Keywords:
language agents, agent memory

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_DMeoOpenReview ↗
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
  1. The question is important and the result is counterintuitive and well-executed.
  2. 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.
  3. 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.
  4. 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
  1. 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.
  2. 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.
  3. 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
  1. 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"?
  2. 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.
Reviewer_hkFQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces VRL-BENCH, a harness for fair evaluation of trial-and-error learning under finite trial budgets. It also introduce VEX2, a verbal exploration-exploitation scheduler that uses a language model to jointly select policies and allocate the remaining trial budget. Overall, it tries to understand, when an rollout failed, is it better to just retry or do the reflexion style rollout again, or something else as they proposed the VEX2 method. Across three models and two environments in the experimental setups, experiment results show some positive results.

Critical strengths

1, the problem it tries to explore is important and interesting, and the motivation is reasonable it explores that does reflecting on failure actually help, or do agents just benefit from getting more attempts? Comparing against plain retry helps separate these two effects, which can guide for actual harness designs. 2, the evaluation protocol seems carefully controlled, which can provide cleaner signals, also the eval converge seems good, with 3 models across 2 environments. It also showcased where memory helps as well as cases where it hurts with the confidence intervals.

Critical weaknesses

1, presentation can be improved, for example, the figure 1 is a bit less intuitive when reading. 2, the improvements over the strongest existing baseline is small in several settings, like 1-2 points 3, The methods get the same number of attempts, but could be different inference budget, the number of tokens might not be controlled, but the number of tokens are actually directly related to the cost at inference, so the actual adoption of this method is bit unclear.

Questions for authors
  1. Could you compare VEX**2 with retry and Reflexion under the same total token budget, counting both action generation and reflection or planning calls? The current results match the number of attempts, but leave this comparison open.

  2. How much do the policy tree and trial allocations help? Could you compare VEX2 with a simpler planner that receives the same failure history and remaining budget, but only suggests what to try next? Whether a simpler scheduler also works? What is the VEX2's limitation and generalization capability.

1 comment

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

SettingReflexionDC-Cu*ACE*
M–D+1.6 [−0.6,4.1]−1.6 [−5.5,1.7]+2.0 [0.2,4.4]
M–G+3.4 [−0.3,8.1]−0.9 [−3.1,1.7]+2.0 [−0.9,5.5]
M–L−1.3 [−3.3,0.8]−3.3 [−6.3,−0.3]+0.2 [−1.7,2.2]
W–D+6.0 [0.0,12.0]+1.0 [−6.0,8.0]+14.0 [7.0,22.0]
W–G+16.0 [8.0,25.0]+6.0 [−2.0,14.0]+11.0 [2.0,20.0]
W–L−4.0 [−12.0,4.0]−11.0 [−19.0,−3.0]−5.0 [−13.0,3.0]

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

SettingRetryReflexionDC-Cu*ACE*VEX²
M–D5,4816,70011,6688,52914,089
M–G5,8479,84913,22513,37023,932
M–L6,90210,62215,07413,40326,047
W–D39,118120,54598,671155,55694,558
W–G21,70378,50650,31592,10652,291
W–L46,88096,955109,954117,70974,602

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

ε0: full replay0.250.500.751: no replay
AlfWorld76.181.377.676.174.6
HotPotQA49.045.049.046.050.0

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

SettingVEX²−RetryVEX²−ReflexionAvgT: Retry/Reflexion/VEX²
M–D+6.6 [2.2,12.0]+5.0 [1.9,8.8]1.99/1.92/1.75
M–G+4.5 [0.5,9.4]+1.1 [−0.9,3.7]2.46/2.25/2.23
M–L+1.6 [−1.1,4.4]+2.8 [0.8,5.2]2.40/2.46/2.37
W–D+16.0 [9.0,23.0]+10.0 [5.0,16.0]4.41/4.14/3.76
W–G+17.0 [10.0,25.0]+1.0 [−8.0,10.0]4.81/4.19/4.17
W–L+8.0 [−1.0,17.0]+12.0 [2.0,22.0]4.39/4.46/4.08

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.

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

This paper aims to help AI agents better utilize their previous failures. The authors first introduce VRL-Bench, an evaluation framework that measures whether agents can effectively learn from previous failures under limited trial budgets in computer control tasks. The authors find that existing reflection-based methods sometimes perform worse than simply retrying without using memory. To address this issue, the authors propose VEX2, which uses an LLM to generate a semantic policy tree, allocate the remaining trial budget, and provide guidance for subsequent attempts based on previous failures. The goal is to balance exploration and exploitation. Experimental results show that VEX2 improves task success rates.

Critical strengths

The paper investigates an interesting problem: whether learning from previous failures consistently improves LLM agent performance. The idea behind VEX2 is simple and easy to implement. The paper is also well organized.

Critical weaknesses
  1. Based on my experience using AI agents, even without explicitly adopting the prompting structure proposed in VEX2, the agents I use are already capable of balancing the exploration-exploitation trade-off. They sometimes question their previous conclusions and explore alternative approaches without relying on the lessons learned from earlier failures. Therefore, I am not fully convinced of the necessity of the proposed method.

  2. I find the technical novelty of VEX2 rather limited. The proposed method appears to be a structured extension of Reflexion, where the LLM is explicitly prompted to consider exploration, exploitation, and the remaining trial budget. Furthermore, the proposed trial-budget allocation is advisory rather than algorithmically enforced. Therefore, it is unclear whether VEX2 introduces a genuinely new exploration–exploitation mechanism or primarily represents a prompt modification of existing reflection-based methods. It is also unclear why exploration–exploitation considerations need to be explicitly prompted, or why existing reflection-based methods would not already be capable of reasoning about this trade-off.

  3. The experimental evaluation is conducted on a relatively small number of test cases. For example, only 100 tasks are used for WebShop. Some of the reported performance differences are very small, corresponding to only a few additional successfully completed tasks. This raises concerns about the robustness and significance of the reported improvements.

Questions for authors

Please see the weaknesses above.

1 comment

As discussion closes, we restate our evidence and await your assessment.

Our work asks whether memory actually enables agents to benefit from past failures. We invest substantial effort because a reliable answer is essential to fair future evaluation and has far-reaching implications. Failure-derived memory is not free. Retry is a strong baseline. A longstanding lack of matched Retry controls confounds memory gains with retry gains. Our evaluation of Reflexion and subsequent advanced memory methods establishes higher token costs without consistent recovery gains.

Controlled parallel evaluations use fixed cohorts. MiniWoB: 64 families (Synapse's task count), ten paired seed sequences/model (episode indices 20 to 29). WebShop: official 500-goal human-test split, goals 0 to 99 (Reflexion's scale). Three models, five conditions, T=6: 16,946 distinct complete trials. Five ε values on AlfWorld (N134,T6) and HotPotQA (N100,T5): 3,324 recorded episodes.

Reflexion's reported HotPotQA recovery pattern does not reproduce with GPT-4o mini. We retain its prompts and reflection/reset procedure. Retry recovers 14/64 T1 failures (36% to 50%); full replay reaches 49%. On AlfWorld, ε=.25 gains 7.1 AUC points over no replay after correction. VEX² empirically tests adaptive scheduling.

M/W=MiniWoB/WebShop; D/G/L=DeepSeek-V4-Flash/GPT-5.4 nano/GLM-4.7-FlashX. Conditions share Actor, realized first trial (T1), resets and interaction limits. DC-Cu*/ACE*: within-case failure-only adaptations.

SR/RR=SR@6/RR@6 (%); RR after T1 failure; AvgT assigns unsolved cases 7. A–O=transitions. Resources: means/case, success-stop; tokens=Actor+update input/output.

1. Memory updates (Tables 6,7,11,12)

SettingMethodSR%RR%AvgTA–OCallsTokensΔSR vs Retry
M/DRetry87.348.41.997.422.795481—
M/DReflexion88.954.81.925.972.896700+1.6 [−0.6,4.1]
M/DDC-Cu*85.8422.057.833.5411668−1.6 [−5.5,1.7]
M/DACE*89.456.71.916.073.438529+2 [0.2,4.4]
M/GRetry82.554.32.468.473.185847—
M/GReflexion85.963.32.257.504.019849+3.4 [−0.3,8.1]
M/GDC-Cu*81.651.82.488.414.4413225−0.9 [−3.1,1.7]
M/GACE*84.559.62.336.545.0513370+2 [−0.9,5.5]
M/LRetry82.553.52.4010.443.776902—
M/LReflexion81.250.22.4610.554.9310622−1.3 [−3.3,0.8]
M/LDC-Cu*79.244.82.5810.995.1015074−3.3 [−6.3,−0.3]
M/LACE*82.753.92.419.265.7513403+0.2 [−1.7,2.2]
W/DRetry459.84.4118.7918.7939118—
W/DReflexion5119.74.1430.1132.76120545+6 [0,12]
W/DDC-Cu*4611.54.4021.1924.0698671+1 [−6,8]
W/DACE*5932.83.9134.0639.13155556+14 [7,22]
W/GRetry3915.34.8115.1115.3421703—
W/GReflexion5537.54.1923.1126.0378506+16 [8,25]
W/GDC-Cu*4523.64.7416.0219.3650315+6 [−2,14]
W/GACE*5030.64.4024.9831.2092106+11 [2,20]
W/LRetry5025.44.3921.5121.7346880—
W/LReflexion4619.44.4629.6732.9596955−4 [−12,4]
W/LDC-Cu*3994.8422.9027.76109954−11 [−19,−3]
W/LACE*4517.94.5330.0238.24117709−5 [−13,3]

2. Reflection exposure

ε=withholding probability (0=full replay,1=none); interior gates retain reflection writing. AUC=mean cumulative SR over T.

εAlf SR@6%Alf AUC%Hot SR@5%Hot AUC%
076.171.644944.40
.2581.374.634542.80
.5077.672.014944.60
.7576.169.784643
174.667.545043.80

We extend Table 4 using released cases and original code. pp [95% CI]; 10,000 paired bootstraps. Alf interior: six-contrast simultaneous CIs; others: pointwise.

Envε target−baselineΔSRΔAUC
Alf.25−0+5.2 [−3.7,14.2]+3 [−3.2,9.2]
Alf.25−1+6.7 [−2.2,15.7]+7.1 [0.9,13.3]
Alf.50−0+1.5 [−7.5,10.4]+0.4 [−5.8,6.6]
Alf.50−1+3 [−6,11.9]+4.5 [−1.7,10.7]
Alf.75−00 [−9,9]−1.9 [−8.1,4.4]
Alf.75−1+1.5 [−7.5,10.4]+2.2 [−4,8.5]
Alf0−1+1.5 [−6,9]+4.1 [−1.5,9.8]
Hot.25−0−4 [−10,1]−1.6 [−5.4,2.2]
Hot.25−1−5 [−10,0]−1 [−4.2,2]
Hot.50−00 [−6,6]+0.2 [−4,4.6]
Hot.50−1−1 [−6,4]+0.8 [−3.2,4.6]
Hot.75−0−3 [−9,3]−1.4 [−5.2,2.2]
Hot.75−1−4 [−10,1]−0.8 [−5,3.2]
Hot0−1−1 [−5,3]+0.6 [−2.4,3.8]

3. VEX² (Tables 6,8,11,12)

SettingSR%RR%AvgTA–OCallsTokensΔSR vs RetryΔSR vs Reflexion
M/D93.975.21.756.902.8614089+6.6 [2.2,12]+5 [1.9,8.8]
M/G8766.12.238.514.1323932+4.5 [0.5,9.4]+1.1 [−0.9,3.7]
M/L84.157.72.3710.154.5926047+1.6 [−1.1,4.4]+2.8 [0.8,5.2]
W/D6136.13.7621.5223.9394558+16 [9,23]+10 [5,16]
W/G5638.94.1714.6617.5052291+17 [10,25]+1 [−8,10]
W/L5837.34.0819.3823.0374602+8 [−1,17]+12 [2,22]

Primary 95% CIs: 100,000 paired bootstraps, 64 M family means/100 W goals; unadjusted.

We would appreciate your updated assessment in light of these results and would be happy to address remaining concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.