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, et al.
cs.AI
Quick verdict
VRL-Bench finds verbal-memory updates inconsistently beat retry; proposed VEX2 positive in all 6 settings, but 2 CIs cross zero and token costs rise 2-4x.
Summary
This paper introduces VRL-Bench, a harness for fairly evaluating trial-and-error (verbal reinforcement) learning of language agents under finite trial budgets, and proposes VEX², a language-model exploration–exploitation scheduler. All conditions share the same first trial and matched trial and interaction limits, so differences measure what failure-derived memory adds over memory-free retry. Across MiniWoB (640 cases) and WebShop (100 goals) with three models (DeepSeek-V4-Flash, GPT-5.4 nano, GLM-4.7-FlashX), no existing update — Reflexion or failure-only adaptations of Dynamic Cheatsheet and ACE — improves SR@6 over retry everywhere: Reflexion gains 16 points on GPT-5.4-nano WebShop (95% CI [+8,+25]) but hurts both GLM-4.7-FlashX settings, and DC-Cu* is negative on all MiniWoB settings. Replay-exposure sweeps (3,324 episodes with GPT-4o-mini on AlfWorld and HotPotQA) show reflection's early advantage can vanish and different schedules recover complementary failures. Motivated by this trade-off, VEX² produces a semantic policy tree, a remaining-budget allocation, and next-trial guidance in one response; it attains the highest observed SR@6 in all six settings (+1.6 to +17.0 points over retry), though both GLM-4.7-FlashX intervals include zero, and it uses roughly 2–4× more tokens than retry. Main limitations: compute is not matched, no multiplicity adjustment, and the replay study uses different models and tasks than the primary matrix.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Under matched finite trial budgets with exactly shared first trials, none of Reflexion, DC-Cu*, or ACE* improves SR@6 over memory-free retry in all six model–environment settings; each helps somewhere and hurts elsewhere (Table 1, Figure 2).
- Replay-exposure sweeps show that using reflections can reduce success (HotPotQA full replay 49% vs no replay 50% at trial 5) and that different replay schedules recover complementary subsets of shared first-trial failures, revealing an empirical exploration–exploitation trade-off (Section 4, Figure 4).
- VEX², which uses a language model to jointly emit a semantic policy tree, an allocation of the remaining trial budget, and next-trial guidance, is the only evaluated update with positive retry-relative SR@6 point estimates in all six settings (+1.6 to +17.0 pp) and the lowest censored AvgT@6 everywhere (Table 2).
- Exact repetition of a previously failed action sequence never led to recovery (0/304 AlfWorld and 0/157 HotPotQA later episodes), while most changed sequences also failed — action novelty is necessary but not sufficient (Appendix E.4, Figure 8).
Strengths
Paired shared-T1 design isolates learning from another chance
All conditions for a case share the same realized first trial and matched trial (T=6) and interaction limits (Sections 2.1–2.2), so SR@6 differences measure what failure-derived memory adds over memory-free retry — directly addressing the confound in prior Reflexion-style evaluations that the paper documents in Table 5.
Unusually rigorous and honest uncertainty reporting
Paired bootstrap with 100,000 resamples (seed 0), exact sign tests on 64 MiniWoB family means, exact McNemar tests on 100 WebShop goals (Table 7), and selection-adjusted simultaneous intervals for post-hoc grid contrasts (Table 4). The paper openly reports where CI and sign test disagree (ACE* DeepSeek MiniWoB: CI [+0.2,+4.4] but sign p=.227) and states that no multiplicity adjustment is applied.
Full resource ledgers, including unflattering ones
Careful method-adaptation taxonomy
Negative headline result is a useful field corrective
Weaknesses
Headline six-for-six claim rests on point estimates in two settings
Budget fairness stops at trials; compute is not matched
No multiplicity control across many setting-specific contrasts
Motivating replay study is disjoint from the primary matrix
Single seed and single first-trial realization
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper contributes two things: **VRL-Bench**, a harness that standardizes what counts as an attempt, when environments reset, and how budgets are matched when evaluating trial-and-error (verbal reinforcement) learning of LLM agents; and **VEX²**, a scheduler that hands the exploration–exploitation decision to a language model. The central empirical claim (Section 3, Table 1, Figure 2) is a negative result: under matched T=6 budgets with an exactly shared, memory-free first trial, none of Reflexion, DC-Cu* (failure-only Dynamic Cheatsheet), or ACE* (failure-only, ADD-only ACE) beats memory-free retry on SR@6 in all six model×environment settings. A secondary claim (Section 4) is that replaying reflections can *hurt*: on HotPotQA, full replay finishes at 49% versus 50% for no replay. The headline positive claim (Section 5, Table 2) is that VEX² is the only evaluated update with retry-relative SR@6 point estimates positive in all six settings (+1.6 to +17.0 pp).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is VRL-Bench?
VRL-Bench is an evaluation harness for measuring trial-and-error learning of language agents (e.g., Reflexion-style verbal reinforcement) under equal finite trial budgets. Its key device is a shared, memory-free first trial across all methods plus matched trial and interaction limits, so that measured differences isolate what failure-derived memory adds over simply retrying without memory.
Does Reflexion actually improve agent success rates?
According to this paper's controlled re-evaluation, not reliably: Reflexion improved SR@6 over memory-free retry in some settings — by up to 16 percentage points on WebShop with GPT-5.4-nano (95% CI [+8,+25]) — but reduced it in both GLM-4.7-FlashX settings. The authors argue earlier evaluations partly confounded the value of memory with the value of simply getting another attempt.
What is VEX² and how well does it work?
VEX² is a scheduler in which a language model, after each failed trial, produces one response containing a semantic tree of candidate policies, an allocation of the remaining trial budget across them, and guidance for the next attempt. It achieved the highest observed success rate in all six tested model-environment settings (+1.6 to +17.0 points over retry), though two GLM-4.7-FlashX confidence intervals included zero, and it consumed roughly 2–4× more tokens than retry.
Is the code or data for this paper available?
The paper references an accompanying supplement (vex2_code_data_supplement) containing pinned code and dependency files for the harness, diagnostics, MiniWoB, and WebShop pipelines. Re-running the evaluation requires access to commercial LLM APIs (DeepSeek, OpenAI, Zhipu) plus browser automation for MiniWoB; the benchmarks MiniWoB and WebShop themselves are public.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided extraction ends at page 33, immediately after Appendix G.1; any content beyond that point of the PDF was not available for review.
- Figures were available only through their captions and extracted numeric labels (e.g., Figure 10 recovery counts), not as rendered images; figure-internal claims were cross-checked against the corresponding appendix tables where possible.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.