VeriCUA: Verification as Agentic Exploration for Computer-Using Agents

Qiushi Sun; Da Yu; Alexander Knop; Amer Sinha; Lingpeng Kong; Ben Kao; Ravi Kumar; Pritish Kamath

cs.AIOct 29, 2026

VeriCUA: Verification as Agentic Exploration for Computer-Using Agents

Authors: Qiushi Sun, Da Yu, Alexander Knop, Amer Sinha, Lingpeng Kong, Ben Kao, Ravi Kumar, Pritish Kamath

Organizations: Google · The University of Hong Kong

Abstract

Building and scaling computer-using agents (CUAs) across desktop, mobile, and web environments requires reliable task-completion verification for data curation, evaluation, and reinforcement learning. Typical automated approaches prompt vision-language models (VLMs) to judge trajectories or generate programs to inspect application state. However, both rely on partial views of complex digital environments. VLM judges are restricted to supplied observations, while generated programs depend on accessible state. These views can omit decisive evidence or leave completion judgments unsupported. Tailoring separate verifiers to different platforms and access settings adds further engineering cost. We present VeriCUA, a platform-agnostic framework for verification through agentic exploration. It treats verification as dynamic evidence gathering and assessment within a shared procedure for online and offline settings across platforms and observation modalities. After inspecting the available context to construct a task rubric, the verifier selects GUI or code checks for unresolved requirements and combines their findings under explicit evidence rules. Experiments show improved agreement with reference labels over the compared baselines across these settings, with the largest offline gains on hard cases and stronger rejection of false completion claims online. Further analyses connect these gains to complementary evidence and test-time exploration.

Figures & tables

Figure 1: VeriCUA inspects the available environment or recording before constructing a rubric, then gathers evidence to verify its requirements.

Figure 2: VeriCUA gathers evidence from retained trajectories and, when accessible, the current interface and underlying machine state. Each read retains its source attributes.

Environment	Judge	Prec	Rec	F1	Acc	False Positive Rate $\downarrow$	Decided	Decided Acc
AndroidWorld	VLM judge	79.3	69.7	74.2	78.4	15.4	100%	78.4%
	Auto-Generated verifier	77.8	84.8	81.2	82.4	16.9	100%	82.4%
	VeriCUA	90.6	87.9	89.2	90.5	7.7	82%	95.1%
OSWorld	VLM judge	68.2	75.0	71.4	73.4	27.9	100%	73.4%
	Auto-Generated verifier	70.6	78.1	74.2	75.9	25.9	100%	75.9%
	VeriCUA	80.3	71.3	75.5	79.5	13.9	78%	88.7%

Table 1: Performance in online environments.

Judge	OSReward-Hard		OSReward		WebArena		AndroidWorld		OSWorld
Judge	Acc	BalAcc	Acc	BalAcc	Acc	BalAcc	Acc	BalAcc	Acc	BalAcc
TRM	57.4	64.8	82.2	83.1	79.6	79.8	88.3	89.6	80.3	73.7
CUAJudge	63.4	62.5	83.7	82.6	81.3	81.8	91.2	90.7	83.4	78.2
OS-Themis	65.7	63.2	80.2	79.8	75.4	74.3	89.4	89.0	82.1	79.0
VeriCUA	70.4	68.3	87.2	86.3	82.7	83.1	94.3	94.1	86.3	81.2

Table 2: Performance in offline verification.

Figure 3: Each metric of VeriCUA with GUI actions alone and with the hybrid action space on the online AndroidWorld suite. Hollow markers are GUI only, filled markers the hybrid space, and the column at the right gives the change.

Figure 4: More observation for a single-call judge. (a) The OSReward judge reading the last

N

frames of each trajectory, with VeriCUA at the right; OSReward’s default is five. (b) The WebArena judges reading a11ytrees alone or with screenshots, against VeriCUA (dashed).

Figure 5: (a) Combining verifier passes improves agreement and decision rate. (b) Rejection of the agent’s false completion reports.

Judge	OSReward	OSReward-Hard
TRM (N=10)	83.5	58.5
CUAJudge	84.8	64.5
VeriCUA	86.4	68.7

Table 3: Accuracy under matched budgets.

Judge	Acc			BalAcc
Judge	Flash	Pro	$\Delta$	Flash	Pro	$\Delta$
CUAJudge	63.4	62.7	$-$ 0.7	62.5	58.4	$-$ 4.1
OS-Themis	65.7	66.1	+0.4	63.2	61.1	$-$ 2.1
VeriCUA	70.4	73.1	+2.7	68.3	69.2	+0.9

Table 4: Backbone comparison on OSReward-Hard.

Figure 6: Failure precision and retention.

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Stage	Aspect	Online environment	Recorded trajectory
Inspect context	application context	packages, directories, stores, and exposed schemas	recorded steps, frames, and structured observations
Synthesize rubric	grounded task requirements	instruction and observed machine context	instruction and observed recording context
Explore	evidence gathering	adaptive GUI reads and code checks, including synthesized checkers	up to $K$ audit paths, seeking support and refutations
	attested types	environment read, UI dump, harness artifact	post-effect frame, precise read, computation, structured state
	source attributes	persistence, persistent or volatile	frame timing, before or after the relevant action
Arbitrate	requirement confirmation	one persistent attested confirmation	attested support from every completed path

Appendix

Table A.1: What each setting determines in the shared procedure.

State Source	Modality	Verbs	Evidence Type	Class
actions and reasoning	text	find_steps , inspect_action	agent claim	asserted
	code	compute	sandboxed computation	attested
screen frames	GUI	overview , get_frame , zoom , ocr	post-effect frame; precise read	attested
			pre-action frame	asserted
a11ytrees	structured	read_a11y , search_a11y	structured state	attested
machine	code	file_exists , find , list_dir , file_stat , read_file , sqlite_query , content_query	environment read (persistent)	attested

Appendix

Table A.2: The action space by state source and modality, with the evidence type each verb stamps.

persistent	settings_get , getprop , file_exists , file_stat , read_file , list_dir , find , sqlite_query , content_query , pm_list , view_file_image
volatile	dumpsys , ui_dump , current_activity , clipboard_read , submitted_answer , screencap (the screenshot verb of Table A.2 )

Appendix

Table A.3 : Persistence tags of the online getter inventory.

Set	Size	Gold	Notes
OSReward-Hard	284	human labels	hard subset of OSReward
OSReward full	1019	human labels
WebArena	715	official checkers	239 / 235 / 241 rollouts by Claude Sonnet 4.6, Gemini 3.1 Pro, Gemini 3 Flash
AndroidWorld	116	official evaluator	M3A Agents
OSWorld, online	361	official evaluator	one rollout per task; actor success 44.3%
ScienceBoard, online	169	official evaluator	actor success 23.7%

Appendix

Table B.1 : Evaluation sets.

Action Space	Prec	Rec	F1	Acc	False Positives	Decided	Decided Acc
GUI only	86.4	57.6	69.1	77.0	3/41	45%	87.9%
Hybrid (default)	90.6	87.9	89.2	90.5	3/41	82%	95.1%

Appendix

Table C.1: Action-space ablation in the online AndroidWorld environment.

Figure C.1 : Evidence rules and recall on the first AndroidWorld suite.

Input	Acc	BalAcc	Decided	Structured Evidence	Tokens
Screenshots	80.0	80.0	33%	0%	234K
Screenshots + a11ytrees	80.0	80.0	75%	73%	252K
a11ytrees	76.7	76.7	85%	93%	178K

Appendix

Table C.2: VeriCUA by observation input on WebArena.

	Rollout Agent						Overall
	Claude Sonnet 4.6		Gemini 3.1 Pro		Gemini 3 Flash		Overall
	Acc	BalAcc	Acc	BalAcc	Acc	BalAcc	Acc	BalAcc
VeriCUA (GUI + a11ytree )	79.9	80.3	84.3	85.3	83.8	83.9	82.7	83.1
CUAJudge	79.1	79.8	82.1	83.4	82.6	81.9	81.3	81.8
TRM	76.2	77.0	79.1	80.8	83.4	81.0	79.6	79.8
OS-Themis	70.3	69.8	80.0	79.4	75.9	74.1	75.4	74.3

Appendix

Table C.3: WebArena results by rollout agent and overall.

	Claude Sonnet 4.6		Gemini 3.1 Pro		Gemini 3 Flash		Overall
	Acc	BalAcc	Acc	BalAcc	Acc	BalAcc	Acc	BalAcc
VeriCUA (GUI + a11ytree )	79.9	80.3	84.3	85.3	83.8	83.9	82.7	83.1
CUAJudge, tree-fed	77.8	77.9	83.0	84.3	82.6	80.0	81.1	80.8
TRM, tree-fed	74.5	74.9	80.4	81.4	80.9	77.4	78.6	78.1
OS-Themis, tree-fed	74.5	73.5	79.6	78.7	78.0	74.9	77.3	75.7

Appendix

Table C.4: Accuracy and balanced accuracy on WebArena with the judges reading a11ytrees .

Pass	Agreement	Decision Rate	Decided Acc	False Positives	Wrong fail s
draw 1	75.7	72.2	91.6	3	4
draw 2	79.1	77.4	92.1	3	4
draw 3	77.4	67.0	94.8	1	3
draw with vision fallback	76.5	73.0	90.5	3	5
three draws combined	80.9	78.3	95.6	2	2
three draws + vision fallback	87.0	87.0	96.0	2	2

Appendix

Table C.5 : Multi-pass combination in the online environment.

Configuration	BalAcc
OS-Themis, 4 milestones / 8 frames (used in the main text)	74.2
OS-Themis, 6 milestones / 12 frames (original budget)	75.9
CUAJudge	76.8

Appendix

Table C.6: OS-Themis budget ablation, mean balanced accuracy.

	OSReward-Hard		OSReward full
Judge	Acc	BalAcc	Acc	BalAcc
VeriCUA (Gemini 3 Flash)	70.4	68.3	87.2	86.3
Gemini 3 Flash	57.0	65.2	87.0	88.2
Gemini 3.1 Pro	61.6	61.6	87.9	88.2
Claude Sonnet 4.6	59.2	68.1	87.7	88.9
Claude Opus 4.6	67.3	68.6	89.5	90.2

Appendix

Table C.7: The OSReward single-call judge by backbone, with VeriCUA for reference.

Judge	Acc			BalAcc
Judge	Flash	Pro	$\Delta$	Flash	Pro	$\Delta$
VLM judge	78.4	79.7	+1.3	77.5	78.5	+1.0
Auto-generated verifier	82.4	85.1	+2.7	82.7	85.4	+2.7
VeriCUA	90.5	91.9	+1.4	90.3	91.8	+1.5

Appendix

Table C.8: Accuracy and balanced accuracy in the online AndroidWorld environment with each framework on the flash and pro tiers.

Setting	Method	Tokens
offline, WebArena (tree-fed, flash)	three judges together (4 calls)	43K–61K
offline, WebArena (GUI, pro)	three judges together (4 calls)	25K
offline, OSReward (GUI)	three judges together (4 calls)	33K–35K
offline, WebArena	VeriCUA	150K–208K
offline, OSReward	VeriCUA	345K–378K
online, first suite	auto-generated verifier	16.2K (60 s)

Appendix

Table C.9: Cost per trajectory or episode.

Dataset	Total $N$	Initial fail		Selected fail		Retained (%)
Dataset	Total $N$	Correct / $n$	Prec. (%)	Correct / $n$	Prec. (%)	Retained (%)
WebArena	715	381/431	88.4	195/212	92.0	49.2
OSReward full	1019	524/625	83.8	166/179	92.7	28.6
OSReward-Hard	284	148/185	80.0	48/54	88.9	29.2

Appendix

Table C.10: Initial failure judgments and the subset retained after exploration.

Panel of Figure 26 — Figure D.1 : A false completion claim refuted from the media store. The agent recorded three clips for one requested video, and both baselines certified the run.

Panel of Figure 27 — Figure D.2 : A success that only the app’s store can attest. The queue is read from the playback database in the asked order, while both baselines fail the run.

Panel of Figure 28 — Figure D.3 : A long desktop recording that every judge passes on the finished export. The verifier reads the preview frame and finds the text at the top rather than centered.

Panel of Figure 29 — Figure D.4 : A web trajectory whose final screen shows cheap shoes. The a11ytree names the page a keyword search rather than the category page and lists prices above the limit.

Panel of Figure 30 — Figure D.5 : A mobile recording whose answer reads well. The map 18 steps before the end shows a closer park than the one the agent chose, and two of three judges passed it.

Computer-Use Agent Evaluation

See all 38 papers

The Art of Building Verifiers for Computer Use Agents
Apr 5, 2026Corby Rosset, Pratyusha Sharma, Andrew Zhao +2LLM Agent Verification AI Agent Evaluation
Microsoft Research · Browserbase
VeriCUA: Learning Proactive Verification for Reliable GUI Agent Rewards
Oct 19, 2026Zhizhou Wang, Yaxi Lu, Zhong Zhang +4AI Agent Reliability RL for GUI Agents
Southwest Jiaotong University · Tsinghua University · University of Electronic Science and Technology of China +3
OpenComputer: Verifiable Software Worlds for Computer-Use Agents
May 19, 2026Jinbiao Wei, Qianran Ma, Yilun Zhao +4Computer-Use Agent Benchmarks Computer-Use Agents
Yale NLP Lab · University of Pennsylvania · University of North Carolina at Chapel Hill

Apr 5, 2026J/K move · Enter open · S save

The Art of Building Verifiers for Computer Use Agents

Corby Rosset, Pratyusha Sharma, Andrew Zhao, Miguel Gonzalez-Fernandez+1

Microsoft Research · Browserbase

LLM Agent Verification AI Agent Evaluation Web Agents Computer-Use Agent Benchmarks

Open paper AskPDF arXiv

Verifying the success of computer use agent (CUA) trajectories is a critical challenge: without reliable verification, neither evaluation nor training signal can be trusted. In this paper, we present lessons learned from building a best-in-class verifier for web tasks we call the Universal Verifier. We design the Universal Verifier around four key principles: 1) constructing rubrics with meaningful, non-overlapping criteria to reduce noise; 2) separating process and outcome rewards that yield complementary signals, capturing cases where an agent follows the right steps but gets blocked or succeeds through an unexpected path; 3) distinguishing between controllable and uncontrollable failures scored via a cascading-error-free strategy for finer-grained failure understanding; and 4) a divide-and-conquer context management scheme that attends to all screenshots in a trajectory, improving reliability on longer task horizons. We validate these findings on CUAVerifierBench, a new set of CUA trajectories with both process and outcome human labels, showing that our Universal Verifier agrees with humans as often as humans agree with each other. We report a reduction in false positive rates to near zero compared to baselines like WebVoyager (

\geq

45%) and WebJudge (

\geq

22%). We emphasize that these gains stem from the cumulative effect of the design choices above. We also find that an auto-research agent achieves 70% of expert quality in 5% of the time, but fails to discover all strategies required to replicate the Universal Verifier. We open-source our Universal Verifier system along with CUAVerifierBench; available at https://github.com/microsoft/fara.

Abstract

Computer-Use Agent Evaluation

Explore similar work

The Art of Building Verifiers for Computer Use Agents

VeriCUA: Learning Proactive Verification for Reliable GUI Agent Rewards

OpenComputer: Verifiable Software Worlds for Computer-Use Agents