VeriCUA: Verification as Agentic Exploration for Computer-Using Agents

Paper: 2610.40578
Authors: Qiushi Sun, Da Yu, Alexander Knop, Amer Sinha, Lingpeng Kong, Ben Kao, Ravi Kumar, Pritish Kamath (Google, The University of Hong Kong)
Categories: cs.AI, cs.CL

The Gap

The emergence of Computer-Using Agents (CUAs)—agents capable of controlling operating systems, web browsers, and mobile devices through mouse clicks, keystrokes, and API calls (e.g., OSWorld, AndroidWorld, WebArena)—has exposed a glaring bottleneck in the AI lifecycle: how do we reliably verify whether an agent has actually completed its task?

Accurate verification is not merely an academic benchmarking metric; it is the fundamental ground truth required for trajectory filtering in synthetic data pipelines, safe human-in-the-loop deployment, and reward modeling in reinforcement learning (RL).

Existing verification paradigms suffer from severe structural failures:

1. Passive Vision-Language Model (VLM) Judges:

   • Single-pass VLM evaluators inspect captured screenshots or video trajectories.
   • However, digital environments are partially observable. Crucial task outcomes (e.g., whether a file was saved in SQLite, whether a background daemon terminated, or whether an off-screen document was corrupted) are completely invisible in screen frames.
   • Consequently, VLM judges frequently hallucinate task completion based purely on superficial UI cues, yielding high false positive rates (up to 28% on OSWorld).

2. Handcrafted Programmatic Evaluators:

   • Traditional benchmarks rely on hardcoded Python/Bash scripts that query specific application states or databases.
   • However, writing custom evaluators for thousands of open-ended software tasks requires enormous engineering effort and breaks as soon as application UI layouts or internal storage schemas change.
   • Furthermore, programmatic scripts cannot evaluate offline recorded human trajectories or legacy execution logs where direct runtime machine access is unavailable.

                  THE CUA VERIFICATION DILEMMA

  Passive VLM Judge                      Programmatic Evaluators
  (Screenshots only)                     (Hardcoded scripts)
        │                                        │
        ▼                                        ▼
  - Sees only surface UI                 - Extremely brittle
  - Cannot query file systems/DBs        - Requires manual code per task
  - Blind to off-screen mutations        - Incompatible with offline traces
  - Up to 28% False Positive Rate        - Fails when schemas slightly shift
        │                                        │
        └──────────────┬─────────────────────────┘
                       │
                       ▼
          NEED: A Platform-Agnostic,
          Autonomous Verification Agent

---

The Increment

One sentence: VeriCUA formalizes verification as an autonomous agentic exploration process that synthesizes environment-grounded rubrics, probes both GUI and system code interfaces to gather decisive evidence, and adjudicates task success under rigorous evidence rules.

                              VERICUA WORKFLOW

  [Task Instruction g + Context c]
               │
               ▼
      [Rubric Synthesis] ──> Extracts Hard (Must-Have) & Soft (Negative) Requirements
               │
               ▼
     ┌─────────────────────────────────────────────────────────┐
     │           Active Agentic Exploration Loop               │
     │                                                         │
     │   Hypothesis Selection: Pick unresolved requirement r_i │
     │                           │                             │
     │       Action Space A(S): Hybrid GUI & Code Tools        │
     │       ├── GUI: zoom, crop, OCR, read_a11y, screenshot   │
     │       └── Code: find, read_file, sqlite_query, CLI      │
     │                           │                             │
     │       Observation: Extract Attested vs Asserted Evidence│
     └───────────────────────────┬─────────────────────────────┘
                                 │
                                 ▼
                     [Rule-Based Arbitration]
              ┌──────────────────┴──────────────────┐
              ▼                                     ▼
      All Requirements Met?               Corroborating Refutation?
      ──> [SUCCESS]                        ──> [FAIL]
              │
              └── Unsettled / Insufficient Evidence ──> [ABSTAIN]

---

The Anatomy

1. Verification as Active Evidence Gathering

Given a user task instruction $g$, an agent executes trajectory $\tau = [o_0, a_0, \dots, o_T]$ and leaves the environment in post-execution state $s_T$. VeriCUA evaluates whether $g$ was fulfilled using available sources $\mathcal{S} = \{S_1, \dots, S_m\}$, outputting a ternary decision: $y \in \{\text{success}, \text{fail}, \text{abstain}\}$

The verification proceeds through four distinct stages:

1. Context Inspection: Probes the operating system environment or recording metadata to construct initial context $c$ (e.g., active window, directory structures, platform type).
2. Rubric Synthesis: Uses $g$ and $c$ to synthesize an explicit set of requirements $R = \{r_1, r_2, \dots, r_n\}$, distinguishing hard requirements (necessary task completions) from soft constraints (side-effect prohibitions, e.g., “no unrelated files modified”).
3. Active Exploration: At step $k$, the verifier policy $\pi_V$ selects an inspection action $\alpha_k = (v_k, x_k) \in \mathcal{A}(\mathcal{S})$ pairing a tool $v_k$ with arguments $x_k$: $\alpha_k \sim \pi_V(\cdot \mid g, c, R, \mathcal{E}_{k-1})$ $\text{Execute}(\alpha_k, \mathcal{S}) \longrightarrow (\tilde{o}_k, t_k)$ where $\tilde{o}_k$ is the returned tool output and $t_k$ represents the evidence type and source metadata tracked by the harness.
4. Rule-Based Arbitration: Aggregates the findings record $\mathcal{E}_L$ to adjudicate requirement satisfaction without trusting unaudited model intuitions.

2. Hybrid Action Space: GUI + Code State

Unlike prior methods that strictly silo GUI inspection from code inspection, VeriCUA provides a unified action space $\mathcal{A}(\mathcal{S})$:

• Code Probes (Online Settings):
  • find(path, pattern): Scans filesystem hierarchies for generated output files.
  • read_file(path, offset, length): Directly inspects configuration files, scripts, or persistent documents.
  • sqlite_query(db_path, query): Validates database records (e.g., contacts, calendar events, settings tables).
  • cli_command(command): Executes sandboxed commands to inspect running processes or network ports.
• GUI Probes (Online & Offline Settings):
  • screenshot(), get_frame(t): Captures live desktop screens or temporal video frames.
  • zoom(box), crop(box): Zooms in on high-density UI elements (e.g., small checkboxes or fine text).
  • ocr(box): Extracts localized optical character recognition tokens.
  • read_a11y(): Dumps structured accessibility trees to parse exact UI widget states.

3. Strict Evidence Discipline: Attested vs Asserted Evidence

A primary driver of VLM judge error is conflating an agent’s intent with actual environment state. VeriCUA introduces an explicit evidence typology:

• Asserted Evidence: The agent’s natural language thoughts, pre-action planned tool calls, or completion claims (“I have successfully changed the brightness”). Asserted evidence can propose hypotheses for exploration but can never alone satisfy a hard requirement.
• Attested Evidence: Verified physical facts verified via independent sensors—a filesystem byte match, an SQL record timestamp, or a post-execution cropped UI element.

To mark a requirement $r_i$ as met, VeriCUA requires attested support. Conversely, marking a requirement unmet requires corroborating refutations across multiple probes to avoid false negatives due to minor tool syntax variations.

---

Quantitative Evaluation

The authors evaluate VeriCUA across three live online interactive environments (AndroidWorld, OSWorld, ScienceBoard) and two offline trajectory datasets (WebArena, OSReward).

1. Online Benchmark Performance

Environment	Judge	Precision (%)	Recall (%)	F1 Score	Accuracy (%)	False Positive Rate (FPR) ↓	Decided Acc (%)
AndroidWorld	VLM Judge	79.3	69.7	74.2	78.4	15.4%	78.4%
	Auto-Generated Script	77.8	84.8	81.2	82.4	16.9%	82.4%
	VeriCUA (Ours)	90.6	87.9	89.2	90.5	7.7%	95.1%
OSWorld	VLM Judge	68.2	75.0	71.4	73.4	27.9%	73.4%
	Auto-Generated Script	70.6	78.1	74.2	75.9	25.9%	75.9%
	VeriCUA (Ours)	80.3	71.3	75.5	79.5	13.9%	88.7%
ScienceBoard	VLM Judge	42.9	60.0	50.0	71.6	24.8%	71.6%
	Auto-Generated Script	50.9	72.5	59.8	76.9	21.7%	76.9%
	VeriCUA (Ours)	77.4	60.0	67.6	86.4	5.4%	91.6%

Key Result: VeriCUA cuts the False Positive Rate on OSWorld from 27.9% to 13.9% (a 50.2% reduction) and on ScienceBoard from 24.8% to 5.4% (a 78.2% reduction). When VeriCUA is confident enough to decide, its accuracy exceeds 95% on AndroidWorld and 91.6% on ScienceBoard.

2. Offline Benchmark Performance (OSReward & WebArena)

Judge	OSReward-Hard Acc (%)	OSReward Full Acc (%)	WebArena Acc (%)	AndroidWorld Offline (%)	OSWorld Offline (%)
TRM (Single-pass VLM)	57.4	82.2	79.6	88.3	80.3
CUAJudge (Checklist)	63.4	83.7	81.3	91.2	83.4
OS-Themis (Milestone)	65.7	80.2	75.4	89.4	82.1
VeriCUA (Ours)	70.4	87.2	82.7	94.3	86.3

Key Result: On the OSReward-Hard subset, VeriCUA outperforms the strongest structured baseline (OS-Themis) by +4.7 percentage points and single-pass VLM by +13.0 percentage points, demonstrating that complex multi-step failures cannot be diagnosed without iterative exploration.

---

Key Takeaways

1. Verification is an Active Investigation, Not a Forward Pass: Passing an entire trajectory or final screenshot into a single LLM prompt fails because digital environments conceal state changes beneath superficial pixels. Active exploration is essential.
2. Hybrid Probing is Essential: Combining code-based filesystem checks with visual OCR/a11y checks resolves ambiguities that neither modality can solve alone. GUI checks confirm visual intent; code checks confirm data persistence.
3. The Value of Abstention: In automated RL fine-tuning and synthetic dataset curation, admitting ignorance (abstain) is far superior to asserting a false positive. By withholding judgment when evidence is ambiguous, VeriCUA delivers curated datasets with clean reward signals.

                  计算机操作智能体（CUA）评测的现实困境

     被动式 VLM 裁判                      硬编码测试脚本
    （仅看表面静态截图）                  （人工编写系统断言）
            │                                    │
            ▼                                    ▼
    - 仅能捕获屏幕表象                   - 极度脆弱，维护成本极高
    - 无法探查深层文件与数据库           - 依赖专有 API，跨软件即崩溃
    - 对屏幕外副作用完全致盲             - 无法复用于离线历史轨迹
    - 假阳性率高达 28%                   - 稍微改动 UI 属性即判失败
            │                                    │
            └─────────────────┬──────────────────┘
                              │
                              ▼
                 迫切需求：平台无关、主动探索的
                    通用智能体评测系统

                              VERICUA 工作流架构

  [任务指令 g + 初始环境上下文 c]
               │
               ▼
      [规约动态合成] ──> 提取强必要条件（Hard）与负面约束（Soft）
               │
               ▼
     ┌─────────────────────────────────────────────────────────┐
     │                主动智能体环境探索循环                    │
     │                                                         │
     │   假设与目标选取：锁定未解决的验收条件 r_i              │
     │                           │                             │
     │       混合动作空间 A(S)：GUI 与系统代码双通道           │
     │       ├── GUI 通道：zoom、crop、OCR、read_a11y、截屏     │
     │       └── 系统代码通道：find、read_file、sqlite_query   │
     │                           │                             │
     │       观测与证据提炼：严格区分【断言证据】与【确证证据】 │
     └───────────────────────────┬─────────────────────────────┘
                                 │
                                 ▼
                         [基于规则的最终仲裁]
              ┌──────────────────┴──────────────────┐
              ▼                                     ▼
        全部规约满足？                        出现反例证据？
        ──> [成功 SUCCESS]                    ──> [失败 FAIL]
              │
              └── 证据不足或存在冲突 ──> [弃权 ABSTAIN]