What Limits Virtual Agent Application? OmniBench: A Scalable Multi-Dimensional Benchmark for Essential Virtual Agent Capabilities

What Limits Virtual Agent Application? OmniBench: A Scalable Multi-Dimensional Benchmark for Essential Virtual Agent Capabilities

Speakers: Wendong Bu, Yang Wu, Qifan Yu, Minghe Gao, Bingchen Miao, Zhenkui Zhang, Kaihang Pan, liyunfei, Mengze Li, Wei Ji, Juncheng Li, Siliang Tang, Yueting Zhuang (Presented by Yaoxin Li, University of Waterloo)

Conference: ICML 2025

YouTube: https://slideslive.com/39044103

Overview

This talk introduces OmniBench, a novel subtask-based benchmark designed to provide a scalable and multi-dimensional evaluation framework for virtual agents. Presented by Yaoxin Li from the University of Waterloo on behalf of the original authors, the research addresses critical limitations of existing benchmarks, which often suffer from static complexity, reliance on manual annotation, and inadequate evaluation metrics. OmniBench represents tasks as interconnected subtask graphs, allowing for the definition and assessment of five distinct dimensions of task complexity and 10 core agent capabilities.

The significance of OmniBench lies in its ability to offer a fine-grained and comprehensive understanding of agent performance, revealing the specific strengths and weaknesses of current models. By enabling the generation of tasks with controllable complexity and providing a robust graph-based evaluation mechanism, OmniBench aims to keep pace with the rapid advancements in AI agents. The benchmark's insights are crucial for advancing the development of more robust, generalizable, and intelligent virtual agents capable of navigating complex, real-world environments.

Background

▶ Watch: Introduction and limitations of current agent benchmarks (0:00)

The rapid evolution of AI agents, particularly in the realm of large language models (LLMs) and multimodal agents, has outpaced the capabilities of traditional evaluation benchmarks. The presentation highlights three primary shortcomings of existing benchmarks, which collectively impede the accurate and scalable assessment of agent performance and progress.

Firstly, many existing benchmarks rely on static tasks with fixed complexity. A stark example provided is MiniWoB, where the state-of-the-art (SOTA) performance surged from 8.2% in November 2022 to an astonishing 96.3% in just six months. This dramatic improvement renders fixed-complexity benchmarks quickly obsolete, as agents rapidly achieve near-perfect scores, making it impossible to differentiate between advanced models or identify areas for further improvement. This lack of adaptive complexity prevents benchmarks from keeping pace with the dynamic landscape of AI research.

Secondly, the construction of tasks in most benchmarks is labor-intensive and heavily reliant on manual annotations. Benchmarks like OSWorld necessitate experiment experts to painstakingly design evaluation functions, while AITW employs crowdsourcing teams to generate demonstration trajectories. This manual overhead severely limits the scalability of task scenarios. It restricts the diversity and complexity of environments that can be modeled, consequently making it difficult for benchmarks to accurately reflect an agent's real-world performance in intricate and varied settings. The cost and time associated with manual annotation bottleneck the creation of sufficiently large and diverse datasets needed for robust agent training and evaluation.

Thirdly, existing evaluation methodologies are often inadequate, failing to capture the nuances of agent performance. Result-based evaluation, which solely focuses on the final outcome, frequently overlooks the progress made during task execution. For instance, two agents might both fail a task, but one might have completed several prerequisite steps, indicating a higher level of capability that a simple pass/fail metric would miss. Conversely, trajectory-based evaluation relies on predefined ground truth trajectories, which can be problematic due to the inherent existence of multiple valid paths to complete a task. Relying on a single ground truth trajectory can lead to inaccurate assessments, penalizing agents that find equally valid, yet different, solutions. These limitations collectively underscore the urgent need for a more sophisticated, scalable, and fine-grained evaluation framework like OmniBench.

Key Findings

▶ Watch: OmniBench's 5 dimensions of task complexity (3:00)

OmniBench's comprehensive evaluations reveal significant insights into the current state of virtual agent capabilities, exposing clear performance gaps and identifying critical areas for improvement across various models.

A primary finding is the identification of distinct capability profiles among different agent types. GPT-4o with accessibility tree emerges as the highest-performing non-human model overall, demonstrating strong general capabilities. In contrast, supervised fine-tuned agents like Omni-U-Ground exhibit particular strengths in planning and decision-making, suggesting that targeted training can yield specialized proficiencies. Conversely, open-source LLMs generally lag behind across most evaluated dimensions, indicating a substantial gap in their ability to handle complex, multi-step tasks compared to more advanced or specialized models.

A critical discovery pertains to the impact of task graph structure on agent performance. The research observes a consistent and significant performance drop across nearly all agents when transitioning from tasks with a simple chain structure to those with a more complex graph structure. For example, GPT-4o with an accessibility tree achieved a 48.8% success rate on chain-structured tasks but saw its performance plummet to 20.5% on graph-structured tasks. Similar declines were noted for both LLMs and GUI-based agents. This gap highlights that the increased complexity and interdependent subtask relationships inherent in graph structures pose a substantial challenge for current agents, underscoring their limitations in handling non-linear, branching task flows.

Furthermore, OmniBench reveals crucial insights into agent robustness against linguistic perturbations. When models trained solely on chain-structure tasks were subjected to variations in word order within instructions, they exhibited significant sensitivity. For instance, OS-Atlas-Pro and Argoverse showed average sensitivity scores of 90.7 and 129, respectively. However, fine-tuning these models on graph-structure tasks dramatically reduced this sensitivity. Omni-OS-Atlas and Omni-Argoverse, the fine-tuned counterparts, achieved much lower sensitivity scores of 34.9 and 26.7, respectively. This demonstrates that exposure to and training on graph-structured tasks significantly improves an agent's ability to generalize to instructional variations and enhances their overall robustness against linguistic noise.

Finally, a detailed analysis of agent failure modes identifies five main causes, with hallucinatory success being the most prevalent. This failure mode, where an agent mistakenly believes a task is complete when it is not, accounts for 36% of all failures. This finding underscores a fundamental challenge in agent development: the accurate understanding of environmental state and the reliable determination of task completion. Other significant failure causes include instruction misunderstanding, lack of knowledge, grounding errors, and environmental errors.

Technical Deep Dive

▶ Watch: Experimental results: Identifying capability gaps across models (6:10)

OmniBench introduces a sophisticated, subtask-based approach to benchmark virtual agents, fundamentally shifting from static, monolithic tasks to dynamic, decomposable task graphs. This design enables both fine-grained evaluation and scalable task generation.

At its core, OmniBench represents each task as a task graph, composed of interconnected subtasks. The structure of these graphs is crucial, as it allows for the precise definition and control of task complexity. The framework defines five distinct dimensions of task complexity, all derived from the task graph's structural properties:

1. Dependency Complexity: Quantified by the number of edges in the task graph. A higher number of edges indicates more interdependencies between subtasks, requiring more intricate planning and execution order.
2. Hierarchical Complexity: Related to the depth of the graph, representing nested subtasks or multi-level dependencies.
3. Branching Complexity: Measured by the width of the task graph, indicating the number of parallel paths or choices an agent might face at certain stages.
4. Sequential Complexity: Reflects the length of the longest path in the graph, corresponding to the number of sequential steps required.
5. Resource Complexity: (Implicit from the transcript, but typically relates to the number and type of entities/tools involved).

Each of these complexity dimensions is further categorized into three levels: easy, medium, and hard, based on specific structural criteria. This multi-dimensional approach allows researchers to precisely control the challenge level of generated tasks and isolate the specific capabilities being tested.

To enable comprehensive and fine-grained evaluation, OmniBench introduces OmniEval, a sophisticated evaluator that defines 10 core agent capabilities from a graph-based perspective. These capabilities are designed to assess various aspects of an agent's intelligence, such as long-range planning, decision-making, error recovery, and context understanding. The evaluation tasks for each capability are meticulously composed based on the interplay of the defined task complexity dimensions. For instance, tasks designed to test "long-range planning ability" might be composed of subtasks exhibiting both hard dependency complexity and hard hierarchical complexity, forcing the agent to reason over extended sequences of interdependent actions.

The graph-based evaluator within OmniEval is inspired by systems like CRAB and operates by tracking the state of individual subtasks. It defines three primary subtask states:

1. Waiting: A subtask is in this state if it has prerequisites that have not yet been marked as completed.
2. Evaluating: A subtask transitions to this state only when all its prerequisite subtasks have been successfully completed. This ensures that the agent follows the logical flow of the task graph.
3. Completed: A subtask enters this state upon successful execution.

This state-tracking mechanism is fundamental to OmniEval's ability to capture fine-grained progress. Instead of merely checking the final task outcome, the system continuously monitors which parts of the task graph an agent has successfully traversed.

OmniEval also introduces two novel graph-based metrics to provide a multi-faceted view of agent performance:

1. Coverage Rate: This metric quantifies the proportion of the task graph (or its subtasks) that an agent successfully completes, even if the overall task is not finished. It provides insight into partial successes and the extent of progress made.
2. Logic Consistency: This metric assesses how well an agent adheres to the defined dependencies within the task graph. It evaluates whether the agent attempts subtasks only after their prerequisites are met, identifying instances of illogical or premature actions.

By combining these elements, OmniEval effectively merges the advantages of both result-based and trajectory-based evaluation. It captures granular progress during task execution, mitigating the "all-or-nothing" problem of result-based methods, while simultaneously avoiding the inaccuracies caused by multiple valid trajectories inherent in traditional trajectory-based approaches. This is achieved by evaluating adherence to the task graph's logical structure rather than a single predefined sequence of actions.

Experimental Setup & Results

▶ Watch: Performance drop from chain to graph structure tasks (7:00)

The research conducted comprehensive evaluations on OmniBench, utilizing a diverse set of virtual agents to identify capability gaps and validate the benchmark's efficacy. While specific hardware or framework versions were not detailed in the transcript, the experiments involved various agent architectures and models.

The primary models evaluated included:

• GPT-4o with accessibility tree: Representing a highly capable, potentially multimodal proprietary model, augmented with access to UI element information.
• Supervised fine-tuned agents (e.g., Omni-U-Ground): Agents that have undergone specialized training, likely on specific task domains or datasets.
• Open-source LLMs: A broader category encompassing general-purpose language models not specifically fine-tuned for the benchmark's task structures.
• GUI-based agents: A general category of agents designed to interact with graphical user interfaces.

Headline Results:

• Overall Performance: GPT-4o with accessibility tree achieved the highest overall performance among non-human models. Omni-U-Ground demonstrated strong planning and decision-making abilities. Open-source LLMs generally showed lower performance across most dimensions.
• Impact of Task Graph Structure (Figure 1): A critical finding was the consistent and significant performance degradation observed when agents transitioned from chain structure tasks to graph structure tasks.
• For example, GPT-4o with accessibility tree achieved a 48.8% success rate on chain-structured tasks, but this dropped sharply to 20.5% on graph-structured tasks.
• Similar declines were observed across open-source LLMs and other GUI-based agents, underscoring the challenge posed by interdependent subtask relationships and branching logic.
• Robustness to Instruction Variation (Table 2): Experiments explored agent sensitivity to changes in word order within task instructions.
• Models trained exclusively on chain-structure tasks, such as OS-Atlas-Pro and Argoverse, exhibited high sensitivity scores of 90.7 and 129 respectively. This indicates a fragility to linguistic perturbations.
• Crucially, after fine-tuning on OmniBench's graph-structure tasks, the sensitivity of these models significantly decreased. Omni-OS-Atlas achieved a much lower score of 34.9, and Omni-Argoverse improved to 26.7. This result strongly suggests that incorporating graph-structured tasks into training regimens enhances an agent's ability to generalize to varied instructions and improves its robustness against linguistic noise.

Analysis of Agent Failure Modes (Figure 2):

The research meticulously analyzed the execution progress of multiple models to identify common causes of failure. Five main categories were identified:

1. Hallucinatory Success (36%): The most common failure, where the agent mistakenly believes the task is complete when it is not. This highlights a significant challenge in agent self-monitoring and environmental understanding.
2. Instruction Misunderstanding: The agent misinterprets the task instructions.
3. Lack of Knowledge: The agent lacks the necessary domain-specific information or common-sense knowledge to proceed.
4. Grounding Error: The agent fails to correctly map abstract instructions or internal states to concrete actions or perceptions in the environment.
5. Environmental Error: The agent encounters unexpected or unhandled situations within the environment.

These results collectively demonstrate OmniBench's capability to provide detailed, actionable insights into agent performance, pinpointing specific areas where current models struggle and guiding future research and development efforts.

Practical Implications

▶ Watch: Analysis of five main causes of agent failure (9:20)

OmniBench offers profound practical implications for various stakeholders involved in the development, deployment, and evaluation of virtual agents. Its multi-dimensional and scalable nature provides a robust framework for identifying limitations and driving improvements.

For practitioners and model builders, OmniBench provides a precise diagnostic tool. Instead of merely knowing that an agent fails, they can now pinpoint why it fails and where its capabilities are limited. The distinction between chain-structured and graph-structured task performance, for instance, highlights that current agents struggle significantly with complex interdependencies and non-linear logic. This indicates a need for architectural advancements or training methodologies that better equip agents to handle branching paths, conditional actions, and multi-step planning in real-world scenarios. The improved robustness to instruction variations after fine-tuning on graph-structured tasks offers a clear actionable strategy: incorporating diverse, structurally complex tasks into training datasets can significantly enhance an agent's generalization capabilities and reduce its sensitivity to subtle changes in user prompts.

For infrastructure teams and deployers, the findings underscore the importance of robust evaluation beyond simple task completion rates. The prevalence of "hallucinatory success" (36% of failures) means that agents might report task completion even when they haven't truly succeeded. This has critical implications for deploying agents in sensitive applications, where false positives could lead to incorrect operations or user dissatisfaction. Infra teams need to consider implementing more sophisticated verification mechanisms or integrating agent self-correction loops that leverage external feedback or more rigorous internal state checks, perhaps inspired by OmniEval's logic consistency metrics. The benchmark also implies that real-world environments, which often mirror graph-like complexities, will pose significant challenges for agents not adequately trained on such structures.

Tradeoffs and Limitations: While OmniBench is a powerful tool, its implementation and the insights it provides come with inherent tradeoffs. The creation of such a detailed, subtask-based benchmark is itself a complex undertaking, requiring careful design of task graphs and capability definitions. While it automates task generation to some extent, the initial design of complexity dimensions and core capabilities still requires expert input. For model builders, fine-tuning on OmniBench's graph-structured tasks, while beneficial, might require larger and more diverse datasets, potentially increasing training costs and time. The current analysis focuses on identifying failure modes; future work might explore how to best integrate OmniBench's fine-grained feedback directly into agent training loops for continuous improvement. The talk doesn't explicitly mention the computational cost of running OmniBench evaluations, which could be a factor for very large-scale assessments. Nevertheless, the benefits of more accurate diagnosis and targeted improvement heavily outweigh these considerations, paving the way for more reliable and intelligent virtual agents.

Key Takeaways

• OmniBench addresses critical limitations of existing virtual agent benchmarks, including static task complexity, reliance on manual annotation, and inadequate result-based or trajectory-based evaluation methods.
• It introduces a novel subtask-based framework, representing tasks as task graphs with five dimensions of complexity (e.g., dependency, branching) and three difficulty levels (easy, medium, hard).
• OmniEval defines 10 core agent capabilities and utilizes a graph-based evaluator with states (waiting, evaluating, completed) and metrics (coverage rate, logic consistency) for fine-grained progress tracking.
• Current SOTA agents, including GPT-4o, struggle significantly with complex, interdependent graph-structured tasks compared to simpler chain-structured tasks, revealing a critical capability gap in handling non-linear logic.
• Fine-tuning on graph-structured tasks substantially improves agent robustness to instruction variations, demonstrating the importance of diverse structural training for generalization and linguistic stability.
• "Hallucinatory success," where agents mistakenly believe a task is complete, is the most common failure mode (36%), highlighting an urgent need for better environmental understanding and accurate task completion detection in virtual agents.

About the Speaker(s)

The talk was presented by Yaoxin Li from the University of Waterloo, who stepped in on behalf of the original authors. The authors of the paper "What Limits Virtual Agent Application? OmniBench: A Scalable Multi-Dimensional Benchmark for Essential Virtual Agent Capabilities" are Wendong Bu, Yang Wu, Qifan Yu, Minghe Gao, Bingchen Miao, Zhenkui Zhang, Kaihang Pan, liyunfei, Mengze Li, Wei Ji, Juncheng Li, Siliang Tang, and Yueting Zhuang. No further biographical details or affiliations for the authors were provided in the transcript.