# ComplexMCP: Evaluation of LLM Agents in Dynamic, Interdependent, and Large-Scale Tool Sandbox

arXiv: https://arxiv.org/abs/2605.10787 · HTML: https://mlsanity.com/paper/2605.10787/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Tool learning and function calling, one of 16 directions in LLM agents and tool use.
- Builds on 27 of its 36 references that are in the map.
- First posted on arXiv 11 May 2026.

## Placed in

- LLM agents and tool use / [Tool learning and function calling](https://mlsanity.com/agents/tool-learning-and-function-calling/)

## Builds on (most cited first, 27 of 27)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [Mind2Web: Towards a Generalist Agent for the Web](https://mlsanity.com/paper/2306.06070/) (2023)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [ChatDev: Communicative Agents for Software Development](https://mlsanity.com/paper/2307.07924/) (2023)
- [τ2-Bench: Evaluating Conversational Agents in a Dual-Control Environment](https://mlsanity.com/paper/2506.07982/) (2025)
- [Kimi K2: Open Agentic Intelligence](https://mlsanity.com/paper/2507.20534/) (2025)
- [GLM-4.5: Agentic, Reasoning, and Coding (ARC) Foundation Models](https://mlsanity.com/paper/2508.06471/) (2025)
- [WebVoyager: Building an End-to-End Web Agent with Large Multimodal Models](https://mlsanity.com/paper/2401.13919/) (2024)
- [Search-o1: Agentic Search-Enhanced Large Reasoning Models](https://mlsanity.com/paper/2501.05366/) (2025)
- [ToolSandbox: A Stateful, Conversational, Interactive Evaluation Benchmark for LLM Tool Use Capabilities](https://mlsanity.com/paper/2408.04682/) (2024)
- [Model Context Protocol (MCP): Landscape, Security Threats, and Future Research Directions](https://mlsanity.com/paper/2503.23278/) (2025)
- [Survey on Evaluation of LLM-based Agents](https://mlsanity.com/paper/2503.16416/) (2025)
- [AnyTool: Self-Reflective, Hierarchical Agents for Large-Scale API Calls](https://mlsanity.com/paper/2402.04253/) (2024)
- [MCP-Bench: Benchmarking Tool-Using LLM Agents with Complex Real-World Tasks via MCP Servers](https://mlsanity.com/paper/2508.20453/) (2025)
- [TRAJECT-Bench:A Trajectory-Aware Benchmark for Evaluating Agentic Tool Use](https://mlsanity.com/paper/2510.04550/) (2025)
- [LiveMCPBench: Can Agents Navigate an Ocean of MCP Tools?](https://mlsanity.com/paper/2508.01780/) (2025)
- [MCPWorld: A Unified Benchmarking Testbed for API, GUI, and Hybrid Computer Use Agents](https://mlsanity.com/paper/2506.07672/) (2025)
- [MCPEval: Automatic MCP-based Deep Evaluation for AI Agent Models](https://mlsanity.com/paper/2507.12806/) (2025)
- [RAG-MCP: Mitigating Prompt Bloat in LLM Tool Selection via Retrieval-Augmented Generation](https://mlsanity.com/paper/2505.03275/) (2025)

## Built on by (most cited first, 4 of 4)

- [What Makes Good Agentic Data? An ACE Lens on Data Generation for LLM Agents](https://mlsanity.com/paper/2608.27260/) (2026)
- [DuMateBench: Evaluating Autonomous Agents in Complex Real-World Workflows](https://mlsanity.com/paper/2608.26546/) (2026)
- [Beyond Prompt-Based Planning: MCP-Native Graph Planning-based Biomedical Agent System](https://mlsanity.com/paper/2606.04494/) (2026)
- [Why Static Skill Inconsistencies Do Not Equate to Runtime Risks: A Behavioral Analysis of LLM Agent Execution](https://mlsanity.com/paper/2610.18927/) (2026)

## Abstract (arXiv)

Current LLM agents are proficient at calling isolated APIs but struggle with the "last mile" of commercial software automation. In real-world scenarios, tools are not independent; they are atomic, interdependent, and prone to environmental noise. We introduce ComplexMCP, a benchmark designed to evaluate agents in these rigorous conditions. Built on the Model Context Protocol (MCP), ComplexMCP provides over 300 meticulously tested tools derived from 7 stateful sandboxes, ranging from office suites to financial systems. Unlike existing datasets, our benchmark utilizes a seed-driven architecture to simulate dynamic environment states and unpredictable API failures, ensuring a deterministic yet diverse evaluation. We evaluate various LLMs across full-context and RAG paradigms, revealing a stark performance gap: even top-tier models fail to exceed a 60% success rate, far trailing human performance 90%. Granular trajectory analysis identifies three fundamental bottlenecks: (1) tool retrieval saturation as action spaces scale; (2) over-confidence, where agents skip essential environment verifications; and (3) strategic defeatism, a tendency to rationalize failure rather than pursuing recovery. These findings underscore the insufficiency of current agents for interdependent workflows, positioning ComplexMCP as a critical testbed for the next generation of resilient autonomous systems.