PaperlayerView exact revision on arXiv

Source-linked AI summary

Odysseys: Benchmarking Web Agents on Realistic Long Horizon Tasks

Lawrence Keunho Jang, Jing Yu Koh, Daniel Fried, Ruslan Salakhutdinov

arXiv:2604.24964v1cs.LGcs.CL

TL;DR

Existing web-agent benchmarks underrepresent long-horizon, multi-site workflows that require sustained context and cross-site reasoning. Odysseys introduces a live-Internet benchmark with rubric-based evaluation, finding that the strongest tested models achieve 44.5% perfect task success while long-horizon interaction remains unsolved.

  • Problem

    Current benchmarks largely emphasize short, single-site episodes, leaving realistic long-horizon workflows across multiple pages, tabs, and domains underexplored.

  • Method

    Odysseys derives 200 multi-site web tasks from real browsing behavior and evaluates task progress with rubric-based requirements rather than only trajectory-level judgments.

  • Results

    44.5% perfect task success is achieved by the strongest tested model, Opus 4.6, while rubric-based evaluation aligns more closely with human judgments.

  • Takeaways & Limitations

    Odysseys provides a realistic benchmark for measuring progress on long-horizon computer-use agents operating across the open web.

  • Takeaways & Limitations

    The benchmark uses controlled research prototypes and mostly read-only or low-impact live-Internet tasks, not actions with real-world side effects.

Abstract

from arXiv · show

Existing web agent benchmarks have largely converged on short, single-site tasks that frontier models are approaching saturation on. However, real world web use consists of long-horizon, multi-site workflows. Common web navigation tasks, such as comparing products across different domains, planning trips across multiple services, or summarizing information from multiple search queries, require sustained context and cross-site reasoning over potentially hours of browsing. To capture and evaluate such behaviors, we introduce Odysseys: a benchmark of 200 long-horizon web tasks derived from real world browsing sessions evaluated on the live Internet. We find that binary pass/fail evaluation is inadequate for long-horizon settings and introduce a rubric-based evaluation, annotating each Odysseys task with an average of 6.1 graded rubrics. We demonstrate that this yields higher agreement with humans and provides a more fine-grained signal than commonly used trajectory-level LLM-as-a-judge evaluation metrics. We tested several leading frontier models and find that the strongest models achieve a success rate of 44.5%, which leaves substantial room for future improvements. Beyond task success, we argue that efficiency is a first-class concern for long-horizon agents. We introduce a Trajectory Efficiency metric (rubric score per step) and find that even frontier agents achieve only 1.15%, marking an evident need for agents that can succeed efficiently and not simply eventually. Odysseys isolates the critical evaluation of long-horizon proficiency in open-web environments, providing a realistic benchmark to measure progress towards computer-use agents that can potentially productively operate for hours. We release our tasks, evaluation scripts, and other results at https://odysseys-website.pages.dev

1 Introduction

Odysseys targets the underexplored problem of long-horizon web workflows spanning many pages, tabs, and domains. It combines realistic browsing tasks with rubric-based evaluation and finds substantial remaining difficulty for current agents.

  • Real-world web use requires sustained context, cross-site reasoning, open-ended decomposition, and decisions about when to stop exploring.Examples include product comparison, travel planning, and information synthesis across sites.
  • Odysseys benchmarks 200 long-horizon web tasks derived from real-world browsing behavior and evaluated on the live Internet.Tasks require multi-step workflows across multiple websites rather than synthetic templates.
  • Rubric-based evaluation decomposes complex tasks into specific requirements, producing more informative partial-success measurements than binary trajectory judgments.The authors report closer alignment with human judgments.
  • 44.5% perfect task success is achieved by the strongest tested model, Opus 4.6, indicating substantial headroom for progress.The benchmark also exposes difficulties in long-horizon web navigation and common failure modes.

2 Related Work

Prior benchmarks cover computer-use agents across synthetic, operating-system, mobile, enterprise, and web settings, but long-horizon live-web interaction remains distinct. Related work also separates GUI navigation from multi-hop web information synthesis.

  • Computer-use benchmarks progressed from synthetic environments such as MiniWoB and WebShop to realistic operating-system, office-suite, mobile, and enterprise tasks.Examples include OSWorld, Windows Agent Arena, Gym-Anything, MacOSWorld, AndroidWorld, and WorkArena.
  • Web benchmarks evaluate screenshot-based navigation and task completion using static pages, synthetic dynamic sites, or live Internet environments.These settings differ in verification precision, scalability, and grading noise.
  • GAIA and BrowseComp evaluate multi-hop information synthesis from the open web but shift away from GUI interaction toward API- or text-based access.They target the deep-research paradigm rather than full browser-level interaction.
  • METR measures long-horizon capability through task-completion time horizons and reports exponential growth in frontier-agent duration from 2019 to 2025.The passage places this progress within broader work on expanding LLM agent horizons.

3 The Odysseys Dataset

The Odysseys dataset composes real browsing journeys into realistic multi-site workflows and evaluates them with verifiable rubrics. It spans diverse tasks and difficulty levels while addressing limitations of trajectory-level grading.

  • Dataset construction: Odysseys contains 200 long-horizon, multi-site tasks requiring agents to navigate websites, extract information, and satisfy verifiable criteria.Representative activities include product comparison, travel planning, and setting up video playlists or watching lectures.
  • Journey collection: 248 participants produced 2,380 labeled browsing journeys, which were refined through LLM screening and manual review to retain 696 high-quality journeys.Only 29.2% remained after filtering for label accuracy, feasibility, login requirements, and overall quality.
  • From journeys to Odysseys: The benchmark composes related journeys into coherent workflows using embedding similarity and GPT 5.4, with source reuse limited to three times and manual quality assurance.The composition pipeline generates prompts, step plans, rubrics, verification procedures, and coherence scores.
  • Evaluation motivation: Prior execution-based verification and trajectory-level LLM judging are unsuitable for Odysseys because long-term tasks require evaluation of partial progress.The proposed rubric structure addresses this by evaluating individual requirements rather than only entire trajectories.
  • Rubric evaluation: Each task contains 3–12 rubric items, averaging 6.1, with separate judge evaluations producing averaged and perfect rubric scores.Rubrics define individual verifiable checkpoints and explain how graders should verify them.
  • Dataset statistics: The benchmark spans easy, medium, and hard tasks across 22 top-level domains and 88 fine-grained SimilarWeb categories.It includes 1,225 rubric items and an average of 1.9 domains per task.

4 Experiments

Experiments evaluate frontier and open-weight agents on Odysseys using rubric-based scoring, efficiency analysis, step-budget scaling, difficulty breakdowns, and qualitative failure-mode analysis. Results show substantial capability gaps, efficiency limits, and model-specific strategies and failures on long-horizon web workflows.

  • Evaluation: Rubric-based evaluation scores partial and perfect task completion, with each task decomposed into independently verified requirements.The benchmark reports averaged rubric scores and perfect scores requiring every rubric to pass.
  • Evaluation: Trajectory Efficiency measures average rubric score per environment step, penalizing agents that require many steps to achieve comparable outcomes.The metric addresses the user-experience cost of long trajectories; a 100-step Opus 4.6 run takes roughly 30 minutes.
  • Efficiency: GPT-5.4 averages 2.03 actions per model call, whereas Opus 4.6 returns one action per call, reducing GPT-5.4’s model round-trips and wall-clock time.GPT-5.4 batches multiple interface actions in nearly half of its calls, while Opus uses an observe/act loop for each action.
  • Difficulty: Performance degrades substantially on hard tasks: Opus 4.6 reaches a 53.2 rubric score average and 11.0% perfect rate, versus GPT-5.4’s 33.8 score and 3.7% perfect rate.Harder tasks require more steps and traverse more unique website domains; Opus 4.6 and Sonnet 4.6 also tend to use more steps.
  • Step-budget scaling: Allowing more interaction steps produces broadly sigmoidal gains, with rates rising mainly from 20–70 steps and tapering beyond approximately 80 steps.Opus 4.6 eventually improves substantially with a 200-step budget, whereas Qwen 3.5 does not, while the overall findings still show room for trajectory-efficiency improvements.
  • Failure modes: Model-specific failures include Opus 4.6 over-investing in research until the 100-step cap and GPT-5.4 terminating after correct planning without acting.Opus hits the cap on 39% of tasks, while both models struggle with broad fanout tasks requiring effort across many parallel subtasks.

5 Conclusion

Odysseys shows that realistic long-horizon web interaction remains unsolved despite recent progress, with performance constrained by planning, cross-site coherence, and extended workflow execution.

  • Odysseys evaluates web agents on realistic long-horizon tasks drawn from real browsing behavior.
  • 44.5% perfect-task success is achieved by the best frontier models, with performance dropping on harder tasks and plateauing as step budgets increase.
  • Rubric-based evaluation decomposes long-horizon success into verifiable intermediate outcomes and agrees substantially more with human judgment than prior trajectory-level methods.
  • Current limitations involve long-context planning, maintaining coherence across sites, and reliably executing extended workflows.

Ethics Statement

The paper frames Odysseys as a research benchmark with controlled, low-impact tasks, while noting misuse risks and privacy protections for the underlying browsing data.

  • Odysseys is intended to measure computer-use agents in research settings, not endorse their current deployment in practical applications.
  • Tasks emphasize read-only or low-impact browsing, searching, and comparison rather than purchases or form submissions with real-world side effects.
  • More capable web agents could enable personal-information scraping, phishing, or circumvention of website access controls, motivating safeguards such as respecting terms of service and robots.txt.
  • Odysseys may improve accessibility and automate repetitive workflows, but its 44.5% perfect-task success and observed failure modes warrant consideration of economic and social implications.
  • Browsing histories came from consenting participants, personally identifying content was removed or rewritten, and only de-identified prompts and rubrics are released.

A.1 Large Language Model Disclosure

The authors used Claude Code with human review to support plotting, qualitative trajectory analysis, and codebase and data checks.

  • Claude Code generated plots from numerical results and visualization instructions, flagged interesting trajectory examples, and drafted descriptions that the authors reviewed and polished.
  • Claude Code also accessed the codebase, results, and data to flag potential issues.

A.2 Data Collection Interface

Participants annotated Chrome browsing journeys through an interface that identified success states, automation preferences, task labels, and feasibility.

  • The interface displayed segmented URLs and guided participants through four annotation steps.
  • Participants selected the key URL representing task success, indicated automation preference, wrote an AI-style task label, and judged feasibility.

A.3 Journey Refinement

Odysseys refines participant browsing journeys through automated screening and manual review, reducing 2,380 raw journeys to 696 usable journeys.

  • 2,380 raw journeys required refinement before becoming Odysseys task building blocks.The journeys were collected from participant browsing sessions and needed substantial processing.
  • LLM screening assessed label accuracy, feasibility, login requirements, and overall quality while producing refined labels and justification notes.
  • 696 usable journeys remained after manual review filtered infeasible, login-gated, and low-quality tasks.Reviewers verified URLs, manually assessed feasibility, and selected or wrote task labels.

A.4 Task Composition Pipeline

The task composition pipeline clusters related short journeys, selects connected candidates, and uses an LLM to assemble them into coherent multi-step workflows.

  • Clustering and chaining: 696 refined journeys are clustered and chained into long-horizon tasks rather than used as isolated subtasks.
  • Clustering and chaining: Embeddings are reduced to 15 dimensions with UMAP and clustered using HDBSCAN, while a theme graph connects related cluster centroids.
  • Clustering and chaining: A 1–2 hop graph traversal gathers 3–6 related clusters and 12–24 candidate journeys for each task.
  • Task generation: GPT-5.4 selects and orders a subset into a coherent workflow, generating the prompt, step plan, rubric, verification procedures, and coherence score.
  • Task requirements: Composition requirements enforce sequential dependencies, a unified goal, geographic consistency, cross-site interaction, and at least 30% dependent steps.

A.5 Hard Long-Horizon CUA Task Pipeline

The hard-task pipeline expands browsing seeds into realistic, public-web, long-horizon workflows, then filters candidates through LLM judging and human quality assurance.

  • Generation: The pipeline preserves a seed’s user goal and decision axis while expanding short tasks into realistic multi-hour browser workflows.
  • Generation: GPT-5.4 rewrites 2,380 refined journeys into viable hard tasks or rejects them when credible public-page expansion is impossible.
  • Quality assurance: LLM judging rejected artificial, vague, stale, short, or rubric-misaligned candidates, producing 567 viable hard candidates.
  • Quality assurance: Manual QA removed inflated tasks, edited unclear prompts, and produced an 80-task final shortlist.
  • Rubric constraints: Viable tasks must contain 5 to 7 rubric items whose weights sum to exactly 1.0 and whose checks cover requested outputs and browser evidence.
  • Rubric constraints: Rubrics must mirror prompt quantities and cannot introduce hidden deliverables, sites, tabs, fields, or evidence requirements.

A.6 Odysseys Task QA Interface

Odysseys uses a dedicated QA interface and rubric-level trajectory judging to review task quality and evaluate agent behavior under extended step budgets.

  • Manual QA: Reviewers inspect each task’s prompt and rubric weights, requirements, and verification criteria before entry into the benchmark.
  • Rubric evaluation: Each rubric receives an independent binary judgment based on the task, requirement, verification description, full action history, and chronological screenshots.
  • Step scaling: 200 steps raise Opus 4.6 perfect task success from 44.5% to 76.5%, while 14.5% of runs still exhaust the budget.
  • Failure modes: Residual Opus failures commonly involve gathering information without producing the requested deliverable or abandoning browser work for a failed programmatic shortcut.
  • Failure modes: One Opus task consumed approximately 175 steps compiling one graduate program before missing the required cross-program comparison.
  • Failure modes: Qwen 3.5-9B gains essentially no additional progress from extending the budget from 100 to 200 steps on the hard tasks.
Loading 2604.24964v1…