Video-Based Reward Modeling for Computer-Use Agents

This paper introduces the Execution Video Reward Model (ExeVRM), a scalable and model-agnostic framework that leverages a new 53k video-task-reward dataset and spatiotemporal token pruning to accurately assess computer-using agent trajectories from execution videos, outperforming leading proprietary models in task success prediction.

The Gist

Imagine you are teaching a robot to use a computer. You tell it, "Please book a flight to Paris and save the confirmation email." The robot starts clicking, typing, and navigating. But how do you know if it actually did the job correctly?

This is the problem the paper "Video-Based Reward Modeling for Computer-Use Agents" tries to solve. Here is a simple breakdown of their solution, using everyday analogies.

1. The Problem: The "Black Box" of Robot Thinking

Currently, when we try to grade a robot's performance, we often look at its internal "thoughts" or the code it wrote. But different robots think differently. One might write code, another might click buttons, and a third might just "feel" its way through. It's like trying to grade two different students' math tests when one uses algebra and the other uses a calculator; it's hard to compare them fairly.

The Paper's Idea: Instead of looking at how the robot thought, let's just watch the movie of what it did.

• The Analogy: Imagine a teacher grading a student's essay. Instead of asking the student to explain their brain chemistry while writing, the teacher just reads the final draft. If the story makes sense and answers the prompt, it's a good essay.
• The Solution: The researchers built a system that watches a video recording of the computer screen as the robot works. It ignores the robot's internal code and only judges the visual result: "Did the robot actually book the flight?"

2. The Challenge: Too Much Noise, Too Little Signal

Computer screens are messy. If you record a 5-minute video of someone using a computer, 90% of the screen might be static (like a blank white background, a toolbar that never moves, or a logo in the corner). The real action—the tiny moment where the robot clicks the wrong button or types a single letter—might happen in a tiny corner of the screen for just one second.

The Analogy: Imagine trying to find a specific needle in a haystack, but the haystack is a giant, moving video of a field. Most of the video is just green grass (the static background). You need to ignore the grass and only focus on the tiny moment the needle drops.

The Solution: "Token Pruning" (The Smart Filter)
The researchers invented a special filter called Spatiotemporal Token Pruning.

• Spatial Pruning (The "Eraser"): It looks at a single frame and says, "This big blue background is boring and hasn't changed. Let's erase it to save space."
• Temporal Pruning (The "Skipper"): It looks at the video over time and says, "This sidebar has been the same for the last 10 seconds. Let's skip those frames."
• The Result: The system keeps only the "decisive" moments—the cursor moving, a new window popping up, or a text box changing color. It turns a heavy, slow video into a lightweight, high-speed highlight reel.

3. The Data Problem: How to Teach the Robot What Not to Do

To teach a robot what a "bad job" looks like, you need examples of failure. But most existing data only shows robots doing things perfectly. It's like trying to teach a driving instructor by only showing them videos of perfect drivers; they won't know how to spot a student who forgot to use their turn signal.

The Solution: "Adversarial Instruction Translation"
The researchers used a clever trick to create fake "bad" examples.

• The Analogy: Imagine you have a video of someone perfectly making a sandwich. You then ask a smart AI: "Write a recipe that looks like it belongs in this video, but is actually wrong."
  • Video: Someone puts ham on bread.
  • Fake Instruction: "Please make a peanut butter and jelly sandwich."
  • The Mismatch: The AI realizes, "Hey, the video shows ham, but the instruction asked for peanut butter! That's a failure!"
• The Result: They created 53,000 of these "mismatched" pairs. This teaches their model to spot subtle errors, not just total failures.

4. The Result: The "ExeVRM" Model

They combined all these pieces into a model called ExeVRM (Execution Video Reward Model).

• What it does: You feed it a user's instruction and a video of a robot trying to do it. The model watches the video and says, "Success" or "Failure," and even points out exactly when the robot messed up.
• How good is it? It beat the biggest, most expensive AI models (like GPT-5 and Gemini) at this specific task.
  • The Analogy: It's like a new, specialized referee who only watches the game tape. Even though it's smaller and cheaper than the "Super Referees" (the big models), it's actually better at spotting fouls because it was trained specifically on the video footage, not just general knowledge.

Summary

This paper is about building a specialized video referee for computer-using robots.

1. Ignore the thoughts: Just watch the screen video.
2. Cut the fluff: Use a smart filter to remove boring, static parts of the video so the computer doesn't get overwhelmed.
3. Create fake failures: Use AI to invent "wrong" instructions to teach the model what mistakes look like.
4. The Winner: The result is a model that is faster, cheaper, and more accurate at grading computer tasks than the current giants of the AI world.

It's a step toward making sure our future AI assistants don't just look like they are working, but actually are working.

Technical Summary

Here is a detailed technical summary of the paper "Video-Based Reward Modeling for Computer-Use Agents".

1. Problem Statement

Computer-Use Agents (CUAs) are increasingly capable of executing complex tasks on desktops, mobile devices, and web browsers. However, evaluating whether an agent successfully fulfills a user instruction remains a significant bottleneck.

• Limitations of Current Evaluation: Existing benchmarks rely on hand-crafted scripts, task-specific rules, or final-state checks. These methods lack scalability, do not transfer well to new environments, and often fail to capture subtle, localized cues (e.g., cursor focus shifts, small text edits) that determine success.
• The Need for Method-Agnostic Evaluation: To serve as a universal evaluator, a reward model must rely on representations independent of the agent's internal reasoning (e.g., thoughts, tool calls, code traces).
• Key Challenges:
  1. Redundancy: CUA trajectories contain highly redundant visual information (static toolbars, backgrounds) where correctness depends on subtle, transient changes.
  2. Scarcity of Negative Supervision: Public datasets are dominated by successful trajectories. Failure cases are rare and often lack explicit annotations regarding when and why the trajectory diverged from the goal.

2. Methodology

The authors propose a comprehensive framework centered on Execution Video Reward Modeling, which takes a user instruction and a video sequence of the agent's execution to predict task success.

A. Dataset: ExeVR-53k

To address data scarcity, the authors constructed Execution Video Reward 53k (ExeVR-53k), a dataset of 53,000 high-quality video–task–reward triplets.

• Sources: Aggregated from AgentNet (human demos), ScaleCUA, and OSWorld (agent rollouts from 30 diverse models).
• Representation: Trajectories are converted into compact video summaries (1 FPS) by extracting representative keyframes for each atomic interaction step.
• Adversarial Instruction Translation: To generate hard negative samples, the authors use a Vision-Language Model (VLM) to synthesize "unpaired" instructions that are plausible within the interface context but semantically inconsistent with the observed trajectory. This process includes step-level justification and identifies the exact step where the mismatch occurs, providing dense temporal supervision.

B. Spatiotemporal Token Pruning

To handle long-horizon, high-resolution (720p) videos without exceeding memory budgets, the authors designed a two-stage pruning strategy:

1. Spatial Token Pruning (STP): Removes visually homogeneous regions within a single frame (e.g., large static backgrounds) by constructing a UI-connected graph and pruning large components that lack discriminative signal.
2. Temporal Token Pruning (TTP): Suppresses tokens that remain nearly unchanged across consecutive frames. It maintains a reference token for each spatial location and only keeps tokens that deviate significantly from the reference, effectively focusing on state transitions (e.g., menu expansion, cursor movement).

• Result: This allows the model to process 720p videos efficiently, preserving fine-grained UI cues while discarding redundant data.

C. Model Architecture: ExeVRM

The authors fine-tuned ExeVRM (Execution Video Reward Model) based on the Qwen3-VL architecture (4B and 8B variants).

• Input: User instruction + Execution video sequence (after STP+TTP).
• Output: Binary judgment (Success/Failure) and temporal attribution (localizing the first error).
• Training: Supervised Fine-Tuning (SFT) using the ExeVR-53k dataset, leveraging the synthetic negative pairs for contrastive learning.

3. Key Contributions

1. ExeVR-53k Dataset: A large-scale, diverse corpus of instruction-video-reward triplets covering Windows, macOS, Ubuntu, Android, and Web, featuring both human and agent trajectories.
2. Adversarial Instruction Translation: A novel technique to synthesize hard negative samples with step-level mismatch annotations, solving the scarcity of failure data in CUA training.
3. Spatiotemporal Token Pruning: A specialized mechanism tailored for GUI videos that enables training on high-resolution, long-horizon videos by reducing token redundancy while preserving decisive UI changes.
4. ExeVRM Model: A state-of-the-art reward model that operates purely on visual execution videos, independent of agent internals.

4. Experimental Results

The model was evaluated on ExeVR-Bench, a held-out test set covering multiple platforms.

• Performance:
  • ExeVRM 8B achieved 84.7% Accuracy and 87.7% Recall.
  • It outperformed strong proprietary models, including GPT-5.2 (75.0% Acc / 66.5% Rec) and Gemini-3 Pro (75.1% Acc / 76.7% Rec).
  • It significantly surpassed open-weight baselines like Qwen3-VL 8B (+17.1% accuracy gain).
• Temporal Attribution: ExeVRM demonstrated superior ability to localize the exact time span of failure (measured by temporal IoU), achieving a tIoU of 0.3332, compared to 0.2494 for Gemini 3 Pro and 0.0862 for Qwen3-VL 8B.
• Ablation Studies:
  • Video vs. Snapshots: Dense video context significantly outperformed sparse snapshot-based methods (e.g., AER, Simplified Judge), proving that causal transitions are critical for evaluation.
  • Resolution: 720p inputs with pruning yielded better recall than 360p, highlighting the importance of fine-grained visual details.
  • Pruning Efficiency: Combining STP and TTP reduced GPU memory usage by ~30% and training time by ~25% compared to using only one pruning method, making 720p training feasible on 8x A100 GPUs.

5. Significance and Future Work

• Scalable Evaluation: This work establishes a scalable, model-agnostic paradigm for evaluating CUAs. By relying solely on execution videos, it can assess any agent regardless of its underlying architecture or reasoning style.
• Debugging Aid: The model's ability to precisely localize errors (temporal attribution) provides actionable feedback for developers to debug agent failures.
• Future Directions: The authors note limitations in handling very long-horizon trajectories with extensive trial-and-error (where intermediate failures are part of a successful process). Future work aims to bridge outcome-level reward modeling with process-level credit assignment (Process Reward Models) and explore reinforcement learning with strict thinking budgets.

In conclusion, ExeVRM demonstrates that video-based reward modeling is a robust, high-performance alternative to traditional rule-based evaluation, offering a path toward more reliable and generalizable computer-use agents.