Abstract
As Large Language Models (LLMs) evolve into autonomous agents, the research community has produced a wide array of benchmarks to evaluate their reasoning and execution capabilities. This paper provides a comprehensive taxonomy of these complex tasks, categorizing them by environment dynamics, goal specification, and action spaces. By formalizing the agent-task interaction within a POMDP framework, we identify current evaluation bottlenecks and highlight the shift from simple information retrieval to embodied reasoning in dynamic worlds.
Introduction: The Shift to Goal Delegation
The paradigm of human-computer interaction is shifting from low-level command execution to high-level goal delegation. Researchers are increasingly developing agents capable of reasoning, problem decomposition, and tool utilization. However, the rapid proliferation of benchmarks makes it difficult to compare performance across disparate environments. This survey addresses the need for a structured "task landscape" to help researchers understand the specific obstacles—such as partial observability or irreversible state changes—that define different agent benchmarks.
Formalizing the Task Landscape
To unify the study of interactive agents, we formalize the interaction using Partially Observable Markov Decision Processes (POMDPs). Tasks are categorized along several critical dimensions:
- Environment Modality: Tasks range from visual 3D simulations (e.g., Minecraft) to text-based worlds and digital interfaces (APIs, GUIs).
- Action Spaces: Agents may use parameterized actions (e.g.,
click(id)), natural language, or executable code (Python/SQL). - State Dynamics: A key distinction is whether actions result in irreversible changes (dead-ends) or are purely for information retrieval.
- Goal Specification: Goals can be direct instructions or indirect constraints requiring inference.
The Benchmark Landscape
The survey examines dozens of benchmarks, highlighting the diversity of challenges agents face today. These are broadly grouped into physical/simulated worlds, digital assistance, and reasoning-heavy tool-use tasks.
Key Dataset Categories
- Physical & Simulated Worlds: Benchmarks like
MINEDOJO(Minecraft) andALFRED(household tasks) test spatial reasoning and long-horizon planning. - Digital & Web Agents:
MIND2WEBandOSWORLDevaluate an agent's ability to navigate complex operating systems and live web interfaces. - Tool-Use & Multi-hop QA:
APPWORLDandHOTPOTQA_REACTfocus on API interaction and the ability to chain multiple reasoning steps to answer complex queries.
Key Insights and Challenges
Our synthesis reveals several fundamental tensions in current agent research:
- Embodied vs. Language Reasoning: There is a split between agents that change the world (physical state reachability) and those that retrieve information. The former involves "dead-ends" where an agent can break the environment, while the latter requires higher-order linguistic reasoning.
- The Evaluation Bottleneck: Reference-based evaluation (comparing to a "gold" trajectory) is often too conservative. Many tasks have multiple valid solutions, making exact-match metrics misleadingly low. Researchers are increasingly turning to LLM-as-a-judge or human evaluation.
- Reward Sparsity: While simulated physical worlds often provide intermediate rewards, digital assistance and QA tasks typically lack step-by-step feedback, making them significantly harder for reinforcement learning approaches.
Future Directions and Limitations
The survey identifies critical gaps for future work. Most current benchmarks assume static, well-defined goals. Real-world agents must handle ambiguity by asking clarifying questions (human-in-the-loop). Furthermore, digital benchmarks relying on live web APIs are fragile; moving toward "virtual API servers" is essential for reproducibility. Finally, as agents become more capable, the focus must shift from single-agent execution to multi-agent collaboration and social intelligence.
Summary updated