[CVPR 2026] OS-Themis: Breaking the Reward Bottleneck for Generalist GUI Agents

TL;DR

OS-Themis is a scalable, multi-agent critic framework that transforms how we reward GUI agents. By shifting from a monolithic "single-judge" approach to a structured pipeline of Milestone Verification and Verdict Calibration, it eliminates the "evidence dilution" that plagues long-horizon tasks. It delivers SOTA results on the new OmniGUIRewardBench and drives a 10.3% improvement in Reinforcement Learning (RL) performance on AndroidWorld.

The "Evidence Dilution" Crisis in GUI RL

Training a robust GUI agent is notoriously difficult. While Reinforcement Learning offers a path to self-improvement, it requires a near-perfect reward signal. Current "LLM-as-a-judge" methods suffer from two fatal flaws:

1. Contextual Loss: Sparse sampling (looking only at the last few frames) misses the "how."
2. Evidence Dilution: In a 30-step trajectory, 28 steps might look perfect, but a single missed "Save" button in step 15 makes the entire mission a failure. Standard LLMs often get "distracted" by the 28 successful steps and provide a false-positive reward.

Methodology: The Multi-Agent Audit

OS-Themis replaces the single judge with a specialized "courtroom" of agents.

1. Milestone Verification Module (MVM)

Instead of judging the whole video at once, the Selector Agent picks out 5-7 "milestones" (e.g., "App opened," "File located," "Text entered"). The Verifier Agent then looks at the local transition (Before vs. After) of just those steps. This ensures salient signals are isolated from the noise.

2. Verdict Calibration Module (VCM)

This is where the "Themis" (Justice) happens. The Reviewer Agent acts as a suspicious auditor. It hunts for case-sensitivity errors, missing save actions, or UI hallucinations. It forces the MVM to "re-verify" questionable steps. Finally, the Judge Agent synthesizes this entire deliberation history—not just the final state—to issue a robust reward.

Figure 1: The OS-Themis pipeline, showing the iterative interaction between Milestone Verification and Verdict Calibration.

Experiments & Results

The authors introduced OmniGUIRewardBench (OGRBench), the first large-scale, cross-platform benchmark for GUI rewards spanning Android, Windows, macOS, Ubuntu, and Web.

• Precision and Stability: OS-Themis achieved a staggering 90.9% average precision, significantly reducing the false positives that typically ruin RL gradients.
• Online RL Impact: When used as the reward function for training a Qwen3-VL-8B policy, performance on AndroidWorld jumped by 7.1% compared to standard baselines.
• Scalability: In exploration scaling tests, training on 1,024 tasks with OS-Themis feedback yielded a 10.3% total gain over the baseline.

Figure 2: Comprehensive results on OGRBench showing OS-Themis outperforming DigiRL and ZeroGUI across all platforms.

Why It Works: A Case Study

Consider a task to "Edit a note and add 'Hello, World!' to the top."

• Standard Critic: Sees the editor open and "Hello, world!" written. Returns "Success" (False Positive).
• OS-Themis Reviewer: Notices the user requested an uppercase "W" but the agent typed lowercase "w." It also notices the agent never hit the "Save" icon. It flags these as Blockers, and the Judge correctly marks the task "Not Completed."

Critical Analysis & Conclusion

Takeaway

OS-Themis proves that Reward Modeling is as much about "Search" as it is about "Inference." By searching for the most critical milestones and auditing them, we can build agents that truly learn from their mistakes.

Limitations

• Inference Cost: Multi-agent loops consume significantly more prompt tokens and have higher latency (~117s per evaluation) compared to one-shot judges.
• Privacy: High-fidelity screenshots are required for verification, necessitating strict local deployment or sanitization in real-world apps.

Future Outlook

The move toward "Zero-human-cost" learning for GUI agents is now viable. OS-Themis provides the "stable compass" needed for agents to wander into the stochastic wild of real-world software and successfully self-evolve.