OS-Marathon: Benchmarking Computer-Use Agents on Vast-Horizon, Repetitive Tasks

AI summary

Overview

• Research area: Computer-use agents (CUAs) — vision-language models that operate desktop software through screenshots and mouse/keyboard actions — and the benchmarks used to evaluate them.
• Technical level: Intermediate. The framing is accessible, but some sections assume familiarity with agent evaluation protocols (POMDP formalization, field-level vs. subtask-level scoring, orchestrator frameworks).
• Scope: The paper defines a new class of agent task ("vast-horizon, repetitive" workflows), introduces a 100-task benchmark called OS-Marathon to measure it, benchmarks leading agents against human performance, and tests one personalization method (GraphDemo) for adapting off-the-shelf agents from a single human demonstration.

What This Paper Is About

Everyday and professional workflows often involve doing the same small procedure over and over: entering a stack of receipts into one expense report, grading a class of exam papers, or reorganizing a set of PDF annotations into a notes format. The length of these tasks scales with how much data you have, and the instruction is high-level ("file an expense report from the receipts on the desktop") rather than a step-by-step list. The paper argues that no existing benchmark measures this capability, so it builds one (OS-Marathon) and tests whether state-of-the-art agents can handle it.

Key Contributions

1. A formal definition of vast-horizon, repetitive CUA tasks, decomposing a workflow into a pre-subtask phase, N repetitive per-instance subtask phases, and a post-subtask phase, with reward given only at completion.
2. OS-Marathon, the first benchmark for this setting, comprising 100 tasks across 5 scenarios, 10 domains, and 12 execution environments.
3. A multi-granularity evaluation of leading agents against human performance, reporting field-level and subtask-level success (and task-level success in the appendix), with failure analysis of where and why agents break down.
4. GraphDemo, a personalization strategy, which encodes a single human demonstration as a causal graph with on-demand retrieval, as a first step toward bridging the gap between general-purpose agents and user-specific repetitive workflows.

Main Findings

• Vast-horizon tasks are much longer than prior benchmarks: OS-Marathon subtasks alone match the horizon of full OSWorld and OdysseyBench tasks (typically fewer than 30 steps), with a non-trivial fraction exceeding them, while full OS-Marathon tasks span roughly 50 to 200 steps end-to-end and scale further with the number of data instances N.
• Humans still largely outperform SOTA agents. Overall field-level / subtask-level success: human 88.38 / 80.52, versus the best agent, GPT-5.4 Native Computer Use, at 68.29 / 51.39.
• End-to-end task completion is rare. Only GPT-5.4 Native Computer Use reaches a non-trivial task-level success rate (11.53%); every other baseline falls below 3%, and humans complete 82.62% of tasks.
• Different agents fail at different levels. OpenCUA-7B, UI-TARS-7B, o3, and GPT-5.4-nano are bottlenecked at the atomic-operation level, partly because they cannot decompose a high-level intention into concrete steps. Stronger agents execute atomic actions but fail at subtask and task level.
• Two failure modes dominate for stronger agents: visual-salience bias with downstream hallucination (the agent clicks "Upload Receipt" because of training-data associations with "Expense Report," then hallucinates plausible dates and amounts), and weak global planning and persistence (agents process instances opportunistically and terminate the loop before all N instances are done). Agents also lack an ordered processing strategy.
• Education and insurance are the hardest scenarios, attributed to stronger cross-referencing dependencies. Success drops sharply and near-monotonically as the number of apps a task must cross-reference grows.
• Web workflows are more manageable than spreadsheet and document workflows, because web actions are bounded and reversible while a stray drag or misdirected paste can corrupt the environment beyond recovery.
• Naive decomposition backfires. Wrapping AgentS2.5 + GPT-5 in a task orchestrator reduced overall field/subtask success from 33.90 / 25.31 to 29.07 / 16.01, because a solver agent's error corrupts the shared environment and the next solver reasons from that corrupted state without context of the error.
• GraphDemo helps substantially. Applied to the vanilla agent it lifted overall field/subtask success from 33.90 / 25.31 to 50.95 / 41.24, bringing a weaker agent close to SOTA native-agent performance; combined with the orchestrator it reached 40.78 / 27.40, still better than the orchestrator alone but weaker than the vanilla + GraphDemo setting.
• Cost is a barrier. The cheapest agent with non-trivial subtask-level performance costs roughly $5 to $10 per task on average, scaling linearly with N, and cost is not tightly correlated with accuracy (UiPath + Opus 4.5 costs comparably to GPT-5.4 but is substantially outperformed).
• Difficulty tiers behave as expected. On OS-Marathon-Lite versus OS-Marathon-Pro, task-level success for the strongest agents drops (AgentS2.5: 5.56% to 0%; UiPath: 1.11% to 0%; GPT-5.4 NCU: 16.22% to 6.83%).

Methodology in Plain English

The authors first formalized the task type as a POMDP in which a workflow splits into a one-time preparation step, N repetitions of the same per-instance procedure (only the data differs), and a one-time closing step. They then built 100 tasks from real daily workflows across five scenarios (Business, Academic Credentialing, Education, Note Taking, Insurance), covering 18 atomic actions in six categories and running in 12 interactive environments spanning web, spreadsheet, document, and markdown workflows. Supporting data (receipts, transcripts, exam papers, PDFs, insurance policies) was produced through a hybrid pipeline: editable documents were collected from public sources and edited with synthetic values, while uneditable data such as image receipts from existing OCR datasets were extended with extra annotations and anonymized; collection spanned roughly three months. Every annotation was cross-checked by three annotators, and five separate human evaluators completed each task end-to-end under the same setup given to agents, both as a feasibility check and as a way to split tasks into Lite (under 100 human steps) and Pro (100 to 200 steps). Agents were run on a local VMware virtual machine, with open-weight models hosted via vLLM, under budgets matched to human performance following the OSWorld protocol, and scored at field, subtask, and task granularity. Finally, the authors tested two interventions: an orchestrator that assigns per-instance subtasks to solver agents one at a time, and GraphDemo, which stores a single human demonstration as a causal graph (nodes hold a textual description plus screenshots, edges hold actions), places the text summary in the system prompt, and injects only the node matching the agent's planned action plus its neighbors at each step.

Why This Matters

The paper reframes a real gap in agent evaluation: prior benchmarks measure atomic tasks or enumerated long-horizon workflows, not the scalable, high-level-instruction, repeat-and-accumulate tasks that dominate actual office and personal work. It also shows that adding an orchestrator, a natural engineering instinct, can make things worse due to error propagation, and that a single human demonstration can recover much of the lost performance at low cost.

Real-world applications:

• Expense reporting and finance back-office processing, where receipts must be logged into portals or forms one at a time.
• Education, where teachers grade and record marks for an entire class in a fixed format.
• Insurance claims, where bookings and policies must be cross-referenced into a multi-page claim form.
• Personal knowledge management, such as reorganizing a set of PDF reading annotations into a preferred note format.

Industry relevance: the results quantify how far proprietary reasoning models, agentic frameworks, and native computer-use agents are from usable reliability on repetitive desktop work, and demonstrate that per-task cost (roughly $5 to $10 and scaling with data volume) is already prohibitive for everyday personal deployment, which motivates cheaper personalization rather than fine-tuning.

Future Directions

• Making demonstrations constraining rather than advisory. The authors explicitly note in the limitations that GraphDemo is only a soft guide: nothing forces the agent to follow it, and it cannot help the agent recover once it deviates.
• Handling cross-solver state corruption. The orchestrator failure cascade (one solver corrupts the environment, the next reasons from the corrupted state with no error context) is identified but not solved.
• Reducing inference cost. The paper poses two open questions directly: how to deliver competitive performance from cheaper open-weight models, and how to use a single human demonstration to reduce inference cost rather than only improve accuracy at the same cost.
• Improving subtask-internal logic and high-level intention decomposition, the bottleneck that orchestration does not address and that weaker agents fail on entirely.

Target Audience

Researchers and engineers working on computer-use agents, GUI agents, and agent benchmarks; practitioners deciding whether orchestrator-based decomposition or demonstration-based personalization is worth adopting for desktop automation; and product teams evaluating the reliability and cost of deploying general-purpose agents on repetitive, high-volume document and form workflows.

Authors’ abstract

Vast-horizon, repetitive workflows are common in daily routines, e.g., processing expense reports from a stack of receipts, organising a collection of PDF annotations into structured notes, and are tedious for humans, with execution length scaling with the volume of data to process. They are, however, well-suited to autonomous agents, since their structured, recurring sub-workflows follow a logic that can be systematically learned. Yet no existing benchmark evaluates agents specifically on vast-horizon, repetitive capabilities, leaving the problem largely underexplored. To bridge this gap, we establish OS-Marathon, comprising 100 vast-horizon, repetitive tasks across 5 scenarios and 10 domains, on which our evaluation reveals that leading state-of-the-art (SOTA) CUAs struggle substantially. We further find that introducing a task orchestrator to decompose the workflow into per-instance subtasks fails to mitigate the challenge: errors accumulate and propagate across solver agents, indicating that naive decomposition is insufficient for these tasks. We then explore a cost-friendly personalisation strategy, i.e. GraphDemo, that adapts general agents to such tasks from a single human demonstration of the recurring sub-workflow logic. Extensive experiments show both the real-world challenge of vast-horizon, repetitive tasks and the improvement provided by human demonstration in this setting. Project website: https://os-marathon.github.io/.