PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yu Bai, Yukai Miao, Dawei Wang, Li Chen, Yanyu Ren, Yuqian Shi, Dan Li, Ying Xiong, Chengqiu Tan, Run Zhou, Li Li

arXiv:2609.12404v1cs.AI

TL;DR

Failure-derived verbal memory may help later attempts, but its reliability across models and environments—and when replaying its advice helps rather than hinders—remains unclear. The paper introduces VRL-BENCH and proposes VEX2, a language-model scheduler for selecting policies and allocating remaining trials. VEX2 is the only evaluated update with positive observed success-rate gains over retry in all six settings.

  • Problem

    It remains unclear how reliably failure-derived updates improve trial-and-error learning across models and environments, and when replaying their advice helps rather than hinders.

    Source: §1 · p. 1

  • Method

    The paper introduces VRL-BENCH for fair finite-budget evaluation and proposes VEX2, which uses a language model to select policies to explore or exploit within the remaining trials.

    Source: §1 · pp. 1–2, §5 · p. 7

  • Results

    VEX2 is the only evaluated update with positive observed success-rate gains over retry in all six settings.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Replay experiments reveal an empirical exploration–exploitation trade-off between using failure feedback and exploring alternative continuations.

    Source: §7 · p. 9

    The evaluation covers three models, MiniWoB and WebShop, six-trial budgets, and visible feedback; it matches trial and interaction opportunities, not model calls or token use.

    Source: §7 · p. 9

Abstract

from arXiv · show

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$^2$, a verbal exploration--exploitation scheduler that uses a language model to jointly select policies and allocate the remaining trial budget. VEX$^2$ is the only evaluated update to achieve positive observed success-rate gains over retry in all six settings.

1 Introduction

Failure-derived memory can guide later attempts, but it may also anchor an agent to a poor route when a fresh retry could find an alternative. The paper introduces a fair finite-budget evaluation harness, reports mixed results for existing updates, and proposes VEX2 as a scheduler of exploration and exploitation.

1 Introduction

  • In the illustrated WebShop pair, REFLEXION remains unsolved through T6 while memory-free retry explores a different product and succeeds at T2.Both conditions share T1.Source: Figure 1 · p. 2
  • Replay experiments show that using reflections can reduce success rates, with different replay schedules recovering different failed cases.The findings point to a trade-off between using failure feedback and exploring alternative continuations.Source: §1 · p. 2
  • VEX2 uses a language model to choose which policies to explore or exploit within the remaining trials.The paper reports it as the only evaluated update with positive observed success-rate gains over retry in all six settings.Source: §1 · p. 2
  • VRL-BENCH finds that existing memory updates improve over retry in some settings but fall below it in others across three models on MiniWoB and WebShop.The comparison matches trial and interaction budgets while preserving each strategy’s update.Source: §1 · p. 2

2 VRL-BENCH: Fair Evaluation of Trial-and-Error Learning

VRL-BENCH standardizes repeated-trial evaluation while preserving each strategy’s cross-trial update. Its primary study compares adapted verbal updates and memory-free retry across three models and two benchmarks under matched six-trial budgets.

2.1 Task and Trial Formulation

  • VRL-BENCH gives each unchanged-parameter agent at most T complete trials, stopping at first success, and defines SR@T as the fraction of tasks solved within that budget.Model calls, tokens, and action–observation transitions are reported separately rather than counted as attempts.Source: §2.1 · p. 3
  • For fair comparison, conditions share the realized first trial and, after failure, begin from the same external state with the same remaining trial and interaction budgets.Later trials are fresh and stop at success; trajectories may diverge. The reset model does not permit rollback to an intermediate state.Source: §2.1 · p. 3

2.2 Benchmarks, Conditions, and Outcomes

  • The primary study pairs three models on MiniWoB and WebShop at T = 6, comparing retry, REFLEXION, DC-Cu∗, and ACE∗ under matched cases and interaction limits.DC-Cu∗ and ACE∗ are adapted to use within-case failures and reset memory between cases; ExpeL is excluded because it requires successful trajectories. Outcomes include SR@6, RR@6, and censored AvgT@6, with paired intervals.Source: §2.2 · pp. 3–4

3 Existing Verbal Updates Do Not Consistently Outperform Retry

Across the six model–environment settings, none of the three existing verbal updates improves SR@6 over memory-free retry in every setting. Update effects vary by model, and no existing update lowers censored AvgT@6 in all six settings.

3 Existing Verbal Updates Do Not Consistently Outperform Retry

  • None of the three existing verbal updates improves SR@6 over memory-free retry in every setting.Figure 2 reports paired retry-relative differences in percentage points, with setting-specific 95% intervals.Source: Figure 2 · p. 4, §3 · p. 4
  • REFLEXION improves SR@6 on both environments with DeepSeek-V4-Flash and GPT-5.4 nano, but lowers it on both with GLM-4.7-FlashX.ACE∗ is positive in five settings but drops from retry’s 50% to 45% on GLM-4.7-FlashX WebShop; DC-Cu∗ falls below retry in all three MiniWoB settings.Source: §3 · p. 4
  • REFLEXION gains 16 points on GPT-5.4 nano WebShop (95% CI [+8, +25]), while DC-Cu∗ has negative intervals excluding zero for GLM-4.7-FlashX in both environments.No existing update lowers censored AvgT@6 in all six settings; REFLEXION’s WebShop AvgT@6 falls from 4.81 to 4.19 with GPT-5.4 nano but rises from 4.39 to 4.46 with GLM-4.7-FlashX.Source: §3 · pp. 4–5, Table 1 · p. 5

4 Replay Exposure Changes the Value of Reflection

A controlled replay intervention varies whether the agent sees reflections after a shared first-trial failure while holding the writer, Actor, and trial limits fixed. Replay’s value changes across trials, and different schedules recover different failures.

4 Replay Exposure Changes the Value of Reflection

  • The replay intervention varies exposure to stored reflections after a shared first-trial failure, while failures continue to update memory and the Actor and trial limits stay fixed.Interior conditions expose reflections with probability 1 − ε; the endpoints reuse full-replay and no-memory runs.Source: §4 · pp. 5–6, Figure 3 · p. 5
  • On HotPotQA, full replay leads no replay by 1, 2, and 1 percentage points at trials 2–4, then finishes at 49% versus 50%; on AlfWorld, ε = .25 reaches 81.3% versus 74.6% for no replay.Full replay reaches 76.1% on AlfWorld at T3 and then plateaus.Source: §4 · p. 6, Figure 4 · p. 6
  • Across the full budget, AlfWorld ε = .25 improves mean cumulative success (AUC) over no replay by 7.1 percentage points, with a selection-adjusted 95% paired interval of [+0.9, +13.3].The HotPotQA terminal difference is −1.0 point with a 95% paired interval of [−5.0, +3.0].Source: §4 · p. 6
  • Across five schedules, their union recovers 49 of 58 shared-T1 AlfWorld failures and 18 of 64 HotPotQA failures, exceeding the best single schedule’s recoveries.Full replay and no replay also recover some cases the other misses.Source: §4 · pp. 6–7
  • The results reveal an empirical exploration–exploitation trade-off: using failure feedback can improve the next attempt, but alternative continuations recover failures that replay misses.The design question is how to use supported lessons without committing all remaining trials to one account of failure.Source: §4 · p. 7

5 VEX2: A Language Model as an Exploration–Exploitation Scheduler

VEX2 uses a language model to choose which policies to explore or exploit across remaining trials, expressing the decision as a policy tree, allocation, and next-trial guidance. It is the only evaluated failure-derived update with positive retry-relative SR@6 point estimates in all six primary settings.

5 VEX2: A Language Model as an Exploration–Exploitation Scheduler

  • VEX2 schedules exploration and exploitation from failure history and the remaining budget, returning a semantic policy tree, trial allocation, and guidance for the next attempt.The complete response passes unchanged to the Actor; only eligible failures extend the history.Source: §5 · p. 7, Figure 5 · p. 7
  • The scheduler allocates the same remaining opportunities among competing complete-trial policy hypotheses, selecting one policy for the immediate attempt rather than searching a restorable action–observation tree.Allocation expresses which alternatives to pursue now, retain for later, or leave aside.Source: §5 · p. 7

5.1 Success and Trial Efficiency

  • VEX2 is the only one of four evaluated failure-derived updates with a positive retry-relative SR@6 point estimate in every primary setting; gains range from 1.6 to 6.6 points on MiniWoB and 8.0 to 17.0 on WebShop.It improves observed SR@6 by 1.0–8.0 points over the best Table 1 result and lowers censored AvgT@6 in all six settings.Source: Table 2 · p. 8, §5.1 · p. 8
  • On DeepSeek-V4-Flash and GPT-5.4 nano WebShop, VEX2 recovers 16 and 17 goals that retry misses while retaining every retry success; GLM-4.7-FlashX recovers 15 but misses 7 retry successes.On DeepSeek-V4-Flash MiniWoB, VEX2 recovers 118 of 157 shared first-trial failures, compared with 76 for retry.Source: §5.1 · p. 8
  • Lower censored AvgT@6 primarily reflects recovery of more failures, not necessarily faster completion on cases solved by both methods.On DeepSeek-V4-Flash WebShop, changed terminal outcomes account for 0.64 of the 0.65 reduction; common successes contribute 0.01.Source: §5.1 · p. 8

6 Related Work

Related work spans evaluation of interactive agents, verbal feedback and memory, and search or exploration methods. VRL-BENCH focuses on whether cross-trial memory updates improve success and trial efficiency beyond retry under shared budgets.

6 Related Work

  • VRL-BENCH evaluates trial-and-error learning beyond simply trying again, whereas Terminal-Bench and HAL address terminal-agent evaluation and standardized evaluation across models, scaffolds, and benchmarks.AI Agents That Matter motivates strong baselines and cost-aware comparisons.Source: §6 · p. 9
  • Verbal feedback methods operate at different time scales, from revising outputs with linguistic or tool-grounded feedback to carrying reflections across complete trials or reusing experience across tasks.Dynamic Cheatsheet and ACE are adapted to REFLEXION’s cross-trial setting using failures from the current task or task-family case.Source: §6 · p. 9
  • Unlike rollback-based inference-time search over action–observation states, VEX2 constructs semantic policies and allocates fresh complete trials among them.Its exploration–exploitation decision concerns which policy to pursue with the remaining trial budget.Source: §6 · p. 9

7 Discussion and Limitations

The replay sweeps frame the key decision as which failure-supported policy to pursue and which alternatives to keep available. The evaluation’s scope and replay findings limit how broadly its results can be generalized.

7 Discussion and Limitations

  • Action-sequence novelty alone does not capture the cross-trial choice of which failure-supported policy to pursue and which alternatives to retain.Most changed sequences still fail, despite fewer exact repeats with replay than without it.Source: §7 · p. 9
  • The evaluation covers three models, MiniWoB and WebShop, six-trial budgets, and visible environment feedback; other models, budgets, reset semantics, irreversible actions, and hidden feedback remain open.The replay sweeps use separate agent configurations and task sets and establish schedule sensitivity, not a universal schedule.Source: §7 · p. 9

8 Conclusion

Across three models and two benchmarks, existing updates do not consistently outperform memory-free retry, while VEX2 has positive retry-relative SR@6 estimates and lower observed censored AvgT@6 in all six settings. VRL-Bench provides a common framework for evaluating trial-and-error learning under finite budgets.

8 Conclusion

  • VEX2 is the only evaluated update with positive retry-relative SR@6 point estimates and lower observed censored AvgT@6 in all six settings.Existing updates do not consistently outperform memory-free retry in success or trial efficiency.Source: §8 · p. 9

A Formal Details of the Cross-Trial State

  • The remaining trial budget Rt is a state coordinate, and methods may project shared external information into different internal contexts rather than using a common prompt or memory format.Exposing Rt alone does not establish improved outcomes.Source: A Formal Details of the Cross-Trial… · p. 12

B Existing Methods Under a Common Finite-Trial Evaluation

  • VRL-Bench aligns finite trial budgets while preserving method updates; REFLEXION enters directly, DC-Cu* and ACE* adapt to within-task failures, and LATS and Agent-Pro remain outside the matrix.LATS and Agent-Pro require different task-feedback opportunities; the adaptations’ results apply to their within-task forms.Source: B Existing Methods Under a Common… · p. 12, Table 3 · p. 13

C Additional Analyses of Exploration–Exploitation

  • The additional analyses provide process and diagnostic views of replay exposure and VEX2, with settings and numerical results expanded in later appendices.Source: C Additional Analyses of… · p. 13

C.1 Replay-exposure surface and case structure

Replay outcomes vary non-monotonically with exposure, and different schedules recover complementary first-trial failures. In the VEX2 examples, one response combines policy hypotheses with a trial allocation, and VEX2 has the highest observed post-T1 recovery among evaluated conditions in all six settings.

C.1 Replay-exposure surface and case structure

  • HotPotQA full replay ends at 49% versus 50% for withholding; on AlfWorld ε = .25 ends at 81.3%, above full replay’s 76.1% and withholding’s 74.6%.Source: Figure 6 · p. 14
  • Conditional recovery ht is an at-risk conversion rate, while fixed-budget AUC averages cumulative success over trials and the paired table reports its difference alongside terminal SR@T.Source: §C.1 · p. 14
  • The five-schedule union recovers 49/58 AlfWorld and 18/64 HotPotQA shared-T1 failures, versus 33 and 14 for the best single schedule in each setting.Source: Figure 7 · p. 15
  • Only the AlfWorld AUC gain for ε = .25 over no replay has an interval entirely above zero among six endpoint and AUC contrasts, including fixed-grid selection adjustment.Source: Table 4 · p. 15, §C.1 · p. 15
  • Exact-repeat later episodes recover 0/304 AlfWorld and 0/157 HotPotQA cases, versus 137/704 and 59/989 after changed sequences; these associations are descriptive, not causal.Source: Figure 8 · p. 16

C.2 VEX2 process path and post-T1 recovery

  • A VEX2 sample response combines policy hypotheses with allocation (3, 2, 0), summing to R1 = 5; VEX2 has the highest observed post-T1 recovery among five conditions in all six settings.Source: Figure 9 · p. 17, Figure 10 · p. 18

D.1 Original Evaluation Settings and VRL-Bench Adaptations

Under a shared finite-trial protocol, existing memory updates show mixed results, while VEX2 favors retry in all six primary settings. Replay experiments also expose a trade-off between using failure feedback and exploring alternative continuations.

D.1 Original Evaluation Settings and VRL-Bench Adaptations

  • VRL-BENCH standardizes trial budgets and feedback boundaries while retaining each strategy’s own update; earlier evaluations differed in stopping rules, experience lifetimes, and opportunity units.For example, LATS’s nominal k = 30 does not match task-dependent observations or calls, and its parameters allow up to 2,250 candidate A–O edges before early stopping.Source: §D.1 · pp. 18, 20, Table 5 · p. 19

D.2 Evaluated Primary Matrix

  • The primary matrix compares five conditions across three models and two environments, with at most six complete trials and a shared first trial within each paired cohort.Early stopping leaves 16,946 distinct complete-trial executions across 2,220 paired cases.Source: §D.2 · p. 20, Table 6 · p. 21

D.3 Existing-Update Comparison: Paired Inference

  • Existing updates vary by setting: REFLEXION has four positive and two negative estimates, DC-CU∗ two positive and four negative, and ACE∗ five positive and one negative.ACE∗’s positive mean-effect intervals exclude zero in three settings; REFLEXION’s do so in one, while DC-CU∗ has none.Source: §D.3 · p. 21, Table 7 · p. 22

D.4 Environment Feedback and Method-Internal Records

  • Only executed, eligible failures enter cross-trial failure history; VEX2 uses the current history and remaining budget to form the next policy context.Both eligible and ineligible failures consume a trial, and a zero-dispatch protocol failure leaves the history unchanged.Source: §D.4 · pp. 22–23, §D.5 · p. 24

D.7 VEX2 paired inference

  • All six point estimates favor VEX2 over memory-free retry and REFLEXION, with four of six paired intervals excluding zero in each comparison.Both GLM-4.7-FlashX intervals include zero against retry; both GPT-5.4-nano intervals include zero against REFLEXION.Source: §D.7 · p. 25, Table 8 · p. 25

D.9 Separating recovery from time to success

  • The recovery component dominates VEX2’s censored AvgT@6 difference in all six settings, while shared-success timing is analyzed separately.On GLM-4.7-FlashX MiniWoB, 513 cases solved by both methods require 18 more trials in total under VEX2, contributing +0.028; additional recoveries more than offset this timing difference.Source: §D.9 · p. 26, Table 10 · p. 26
  • VEX2 uses fewer executed trials than retry in each setting, but fewer trials do not imply fewer model calls or tokens.The VEX2-minus-Retry trial-use differences range from −0.013 to −0.490 across the six settings.Source: §D.9 · p. 26

E.1 Replay-Exposure Design

  • Replay frequency changes whether written reflections reach the next Actor; using reflections can reduce success, while different schedules recover different failed cases.The five gates range from ε = 0 full replay to ε = 1 no reflection visible to the next Actor.Source: §E.1 · p. 28

E.2 Full exposure grid and trial-index curves

The replay grid shows schedule-sensitive outcomes, and case-level and trajectory analyses reveal distinct recoveries and continuation patterns. The appendices also describe how VEX2 constructs, allocates, and passes its scheduler response under a finite trial budget.

E.2 Full exposure grid and trial-index curves

  • The evaluated replay grid shows an AlfWorld interior endpoint maximum and a HotPotQA endpoint reversal, without establishing a generally optimal schedule or causal harm from REFLEXION as a whole.On HotPotQA, full replay minus full withholding is −1.0 point, with an interval that includes zero.Source: §E.2 · p. 29

E.3 Case-level heterogeneity

  • Across shared first-trial failures, schedule overlap is incomplete: the best single schedule recovers 33 of 58 AlfWorld failures and 14 of 64 HotPotQA failures, while all five recover 49 and 18, respectively.The recovery-support counts show that schedules recover different subsets of failures.Source: §E.3 · p. 29

E.4 Realized replay behavior

  • Exact repeats recover none of 304 AlfWorld or 157 HotPotQA episodes; changed sequences recover 137/704 AlfWorld episodes and 59/989 HotPotQA episodes, though most changed sequences still fail.Replay versus withholding has exact-repeat rates of 10.9% versus 37.6% on AlfWorld and 4.9% versus 20.0% on HotPotQA.Source: §E.4 · p. 29
  • Novelty alone does not predict recovery consistently across tasks: AlfWorld recovery rises from 8.4% in the lowest novelty bin to 24.7% in the highest, while HotPotQA peaks at 8.9% in [.25, .5) and falls to 4.3% in [.5, .75).The exposure surface, case overlap, and realized trajectories together indicate an empirical trade-off between using failure feedback and preserving alternative continuations.Source: §E.4 · p. 30

F.1 VEX2 Runtime Loop

  • The runtime executes a complete Actor trial, records benchmark-visible traces after failure, and makes one scheduler call when another complete trial remains; it passes the response unchanged without parsing a textual search tree.The scheduler jointly selects policies and allocates the remaining trial budget without parameter updates.Source: §F.1 · p. 30

F.3 Prompt-defining decision semantics

  • The prompt designates a next-attempt policy, but that designation is not runtime-enforced; after failure, the scheduler rebuilds statuses and quotas from the updated history and smaller remaining budget.The runtime does not track reservations or repair an invalid semantic plan through an extra generation.Source: §F.3 · p. 31

F.4 Primary scheduler generation configuration

  • Primary MiniWoB and WebShop runs use the same three-shot VEX2 prompt; MiniWoB uses episode indices 20–29, while WebShop uses 100 goals from the official human-test split.A complete realized WebShop trajectory shows a scheduler allocation of (3, 2, 0) after the first purchase, followed by Actor success on the next trial.Source: §F.4 · p. 31, §F.5 · p. 32

F.6 Additional Paired VEX2 Cases

  • In 100 matched primary GPT-5.4-nano WebShop cases, VEX2 succeeds earlier than REFLEXION in 15; the paired examples illustrate differing continuations after a shared first attempt.The examples include preserving a verified option while changing product identity, and maintaining outcome-distinct alternatives rather than repeating one product.Source: §F.6 · p. 32, Table 21 · p. 32

G.1 Primary execution profiles

The primary execution profiles fix paired cohorts and trial budgets for MiniWoB and WebShop, while a secondary GLM-5.1 MiniWoB setting changes both model and cohort.

G.1 Primary execution profiles

  • Primary runs use CPU-only x86-64 hosts, provider-hosted model inference, and separate pinned dependency environments for analysis, diagnostics, MiniWoB, and WebShop.The MiniWoB and WebShop configurations use different Python versions and task-specific browser or Java dependencies.Source: §G.1 · p. 32
  • MiniWoB uses all 64 task families and episode indices 20–29, while WebShop uses goal indices 0–99 from the official 500-goal human-test split.MiniWoB pairs the full per-episode seed sequence across methods; WebShop resets each goal to its entry state.Source: §G.1 · p. 32
  • Both settings use a pre-specified budget of six complete trials, early stopping upon success, and identical method-level interaction limits within each benchmark.MiniWoB permits 128 dispatched action–observation transitions per episode plus family-specific Actor action-block limits; WebShop permits 15 transitions per trial.Source: §G.1 · p. 33
  • The secondary GLM-5.1 MiniWoB setting uses episode indices 10–19, so its comparisons change both model and cohort rather than isolating a backbone effect.The setting retains the same 64 task families and is paired within its own secondary cohort.Source: §G.1 · p. 33
Loading 2609.12404v1…