AgentProofBench: Benchmarking Reusable Verifiers for Web Agents

AI summary

Overview

Research area: Web agents, executable verifier generation, and execution-based agent evaluation (multi-agent systems / software verification).

Technical level: Advanced. The paper assumes familiarity with agent benchmarks, balanced accuracy, bootstrap confidence intervals, and API-grounded task verification, though its core idea is explained concretely.

Scope: AgentProofBench is a 97-task, four-service benchmark that tests whether a frozen acceptance program for a Web agent can follow a changed initial-state requirement and whether its decisions support correct downstream execution.

What This Paper Is About

Web agents increasingly rely on reusable "acceptance programs" — code that checks whether a task was completed — but the public instruction can stay the same while the required business state changes (a name now belongs to a different person, a collection has different members, an initial value must be preserved). A verifier that memorizes an earlier answer can confidently approve the wrong thing.

The paper builds a benchmark that pairs a fixed instruction and fixed program with deliberately altered initial states, then replays the program's decisions inside real execution histories to see what happens when an agent is stopped, continued, or allowed to deliver. The goal is to make reusable verification measurable at both the requirement level (does the rule track the current obligation?) and the policy level (does using that rule produce correct delivered work?).

Key Contributions

1. A paired initial-state reuse test. The public instruction and the generated program are held fixed while the required initial-state binding changes (entity identity, initial value, collection membership, or preservation condition). Two complementary obligations are measured: complete outcome panels and replayed earlier decisions ("source-decision witnesses"), where a previously valid decision becomes invalid under the related state.

2. An execution-validity study linking panel correctness to policy outcomes. Across 22 families the study preserves 44 program assignments, two saved openings per assignment, and 352 policy outcomes, comparing four branches: actor stop, fixed continue, program gate, and online gate.

3. A released executable resource. 97 tasks across 79 families and four Web services, including versioned reference rules, legal alternatives, reconstructable business states, programs, and full action histories. The verify(task, before, after) interface evaluates frozen programs without model calls.

4. Operating profiles for the same verification interface. Fixed-instance acceptance and repeated-check cost analysis (construction fee versus online-judgment fee, amortized over reuse) describe the tradeoffs that accompany reuse and execution.

Main Findings

• Reuse is roughly cost-neutral against rebuilding, not clearly better. Source programs reach related-state balanced accuracy of 93.23% for DeepSeek Flash and 90.36% for Pro. The prespecified reuse-minus-rebuild estimates are −1.56 points with interval [−5.47, 1.57] and −4.95 with [−10.16, 0.00]; both intervals include equal mean BA, and the Pro range extends to −10.16 points.

• Joint correctness is retained for most but not all programs. Complete main-panel correctness drops from 89/96 to 83/96 source programs for Flash and from 83/96 to 81/96 for Pro. Related main-panel correctness is 83/96 Flash and 81/96 Pro, versus 85 and 87 for rebuilds; joint correctness is 82 and 79 for source programs versus 82 and 86 for rebuilds. Conditional on a fully correct source panel, the retained counts are 83/89 and 80/83, spanning 45 and 46 source-qualified families.

• Witness replays expose errors that panels miss. Source programs accept 92/96 valid source witnesses for Flash and 89/96 for Pro, but after the related change they falsely accept 6/96 and 5/96 replays (related rebuilds accept 5/96 and 2/96). Pro source programs also return two Unknown and two Error verdicts on related witnesses.

• Panel correctness strongly tracks execution. Of 33 assigned programs with error-free related panels, 32 correctly deliver both their natural ending and checkpoint; of eleven assignments with a panel error, one does. At the opening level the counts are 64/66 and 2/22. The associated correct-delivery difference is 87.9 percentage points with a pointwise family-cluster interval of [68.8, 100.0].

• Withholdings and regressions concentrate in the error group. All seventeen program-gate withholdings and all three reference-defined regressions belong to the panel-error group. Thirteen withheld terminal states actually satisfy the reference, so withholding and reference failure are distinct outcomes. The two incorrect deliveries among error-free programs are the same Flash Linear27 assignment at its two openings.

• Neutral continuation beats both gates under generic feedback. At checkpoints, neutral continuation repairs 14/16 Flash failures and 16/16 Pro failures, delivering 20/22 and 22/22 openings correctly. Program gating delivers 17/22 and 16/22; online gating delivers 20/22 and 21/22. Neutral continuation's paired gain over program gating is 13.64 points [0.00, 27.27] for Flash and 27.27 [9.09, 45.45] for Pro.

• Programs are conservative: they reject failures better than they accept valid alternatives. On the shared collection comparison (99 failed states, 36 successful anchors, 36 tasks, 29 families), B12 false acceptance is 3.5% versus 31.7% for API12, a paired task-mean difference of −28.2 points [−40.7, −16.7]. Valid-anchor acceptance is 77.8% versus 98.6%.

• Online judging is more accurate but far slower. On the shared natural panel, B12 BA is 92.1 [87.7, 95.9]% and API12 BA is 99.0 [97.7, 99.9]%; on the anchored hard suite, 87.1 [80.6, 93.6]% and 96.2 [93.8, 98.1]%. Median standalone assessment on the 24-state timing panel is 0.58 s for B12 and 20.69 s for API12.

• Break-even horizons are short. Median source construction costs are USD 0.0173 (Flash) and 0.0765 (Pro); a fresh online pass over the corresponding panel costs USD 0.0188 and 0.0980. Median API-fee break-even horizons are twelve assessments for Flash and ten for Pro, with ranges 2–29 and 2–36. At ten uses, Flash program-gate means are USD 0.0195 (natural endings) and USD 0.0189 (checkpoints), against cold means of USD 0.1396 and 0.1390; Pro's ten-use means are USD 0.0509 and 0.0478.

• Semantic audit corroborates the reference labels. A GPT-6 Astra LLM-as-a-judge audit of 195 states across 62 tasks agrees with 191 of 192 resolved labels (99.5%, Cohen's κ = 0.989), or 191/195 over the whole packet, with three indeterminate cases. It confirms all 48 requirement changes, rejects all 48 failed replays, and agrees with both delivered regressions.

• Prespecified tests are not significant. Holm-adjusted p-values for the two related reuse-minus-rebuild contrasts are 0.4350 for Flash and 0.1254 for Pro.

Methodology in Plain English

Each task comes with a public instruction, API documentation, and an ordinary authenticated interface. A host reference implementation decides whether the task was actually completed. A submitted verifier is code that looks at the "before" and "after" business state and returns Pass, Fail, or Unknown. It must derive its requirements from the runtime before state, and it runs frozen in a read-only sandbox with the actor's permissions, limited to one CPU, 1 GB of memory, 60 seconds, and 80 business operations.

To test reuse, the authors take each task's instruction and keep it identical, then construct three initial conditions. Source is the original construction state; background changes unrelated data; related changes something the instruction depends on — which object a name refers to, an initial value, a collection's contents, or a value that must be preserved. Qualification requires that services can actually build these states, that native and API references agree, and, crucially, that replaying an earlier valid decision becomes invalid under the related condition. That last property is the witness: it rules out success by memorization.

Outcome panels cover ordinary natural endings, native prefixes, typed faults, and legal alternatives. Scoring uses balanced accuracy, which weights valid acceptance and failed rejection equally within each panel, with Unknown and Error earning zero credit. Family-level bootstrap resampling (10,000 draws) keeps related tasks together.

For execution, the authors replay 88 saved openings through four policies: stop at the actor's final reply, allow neutral continuations, gate on a source-built program, or gate on a fresh online judgment. Gates deliver on Pass and otherwise permit up to two continuations, and the feedback is deliberately generic — it states nonacceptance without revealing the program's checks or entity names — so the unit of analysis is the whole feedback-and-stopping policy.

Why This Matters

Impact on research. Prior benchmarks test whether a verifier judges a fixed task well; this one tests whether the rule stays correct when the requirement moves underneath it, and then follows the decision into execution. That connects two literatures — generated-verifier evaluation and reusable agent policies — that have mostly been measured separately, and it provides released artifacts that let a failure be traced from a changed requirement to a rejected state to a delivered regression.

Real-world applications:

• Enterprise workflow automation: agents that complete requests against business systems (issue trackers, file storage, messaging, calendars) where names, ownership, and initial values drift between runs.
• Agent deployment gates: deciding whether a learned stopping check can be trusted to release downstream state, or whether neutral continuation is the safer default.
• Verifier generation tooling: comparing construction methods (cheap multi-call programs versus expensive repeated LLM judging) on cost, latency, and selectivity.
• Auditing and compliance: tracing each acceptance or rejection to the reference predicate, API evidence, and business state it relied on.

Industry relevance. The cost results matter for production design: a program that costs USD 0.0173 to build and 0.58 s to invoke breaks even against repeated online judging after roughly twelve assessments, while a highly discriminative judge remains more accurate on valid alternatives (98.6% versus 77.8% valid-anchor acceptance). The finding that neutral continuation outperformed both gates is a direct caution against assuming that adding a verifier improves outcomes.

Future Directions

1. Close the reuse gap for state-dependent bindings. Failures cluster around remembered constants (a stale user ID in linear_44, a hardcoded "Active" in linear_52) and around nested collection structures (the results[0] record missed in box_141). Construction methods that force runtime resolution of the before state are the obvious next target.

2. Design gates that add value over neutral continuation. Since generic-feedback neutral continuation achieved the highest correct-delivery rate, the open question is what feedback content — short of leaking identifiers the program should derive itself — would let a gate beat that baseline.

3. Extend beyond the four services and the two-model panel. The reported generator, judge, and actor results all use DeepSeek Flash/Pro with thinking disabled, and the execution study covers 22 families; broader model and service coverage would test whether the panel–delivery association holds.

4. Probe the boundary conditions explicitly excluded here. Three tasks were removed from the explicit-acceptance view for undeclared boundaries (a completion-text span, formatting around preserved sections, an event title versus attendee phrase), and one audit disagreement (Linear44) hinges on label uniqueness — both point to unresolved specification questions for reference semantics.

Target Audience

Researchers building or evaluating Web-agent verifiers and agent benchmarks; practitioners who deploy agent stopping or acceptance checks in production workflows; and anyone studying LLM-as-a-judge reliability, cost amortization for repeated verification, or the gap between benchmark scores and actual delivered work. Readers need comfort with balanced accuracy and bootstrap intervals to follow the statistical sections, but the central argument — that a rule can look right on a panel and still release a wrong state — is accessible without that background.

Authors’ abstract

Reusable Web-agent verification requires a rule to follow changing requirements and support subsequent execution. We introduce AgentProofBench, which connects paired tests of a frozen acceptance rule to execution from identical saved openings. The resource spans 97 tasks, 79 families, and four Web services. Experiments with DeepSeek Flash/Pro establish two linked measurements. Across 48 families, complete-panel and decision-replay tests retain 82/96 Flash and 79/96 Pro source programs; paired reuse-rebuild BA intervals are [-5.47, 1.57] and [-10.16, 0.00] percentage points. Across 22 execution families, deployment-state panel correctness separates program assignments whose two saved openings are both delivered correctly: 32/33 assignments with error-free panels, versus 1/11 with panel errors. All reference-defined program-gate regressions and withheld deliveries occur in the latter group. Neutral continuation attains the highest correct delivery under the tested generic feedback, providing a concrete baseline for measuring the value added by a gate. Released instructions, states, programs, reference rules, and trajectories connect each test failure to its execution consequences. AgentProofBench makes reusable verification assessable at both the requirement and policy levels.