🤖 AI

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

The paper introduces ComplexMCP, a rigorous benchmark built on the Model Context Protocol with over 300 interdependent tools and dynamic environmental simulations, which reveals that current LLM agents significantly underperform humans in complex workflows due to bottlenecks like tool retrieval saturation, over-confidence, and strategic defeatism.

Original authors: Yuanyang Li, Xue Yang, Longyue Wang, Weihua Luo, Hongyang Chen

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuanyang Li, Xue Yang, Longyue Wang, Weihua Luo, Hongyang Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are hiring a very smart, well-read robot assistant to help you run a complex business. You give it a list of tasks, like "buy some stocks, book a flight, and send a message to a friend."

In the past, researchers tested these robots by giving them simple, isolated tasks, like "calculate 2+2" or "look up the weather." The robots were great at these. But in the real world, tasks are messy. They depend on each other (you can't book a flight until you know who is traveling), the systems can glitch (the internet might lag), and the environment changes while you are working (your friend might have blocked you, or your shopping cart might already have items in it).

The Problem: The "Last Mile" Gap
The authors of this paper, ComplexMCP, argue that while our AI agents are good at the easy stuff, they fail at the "last mile"—the final, difficult steps of actually getting real-world work done. They are like a driver who can parallel park perfectly in an empty lot but crashes when trying to navigate a busy city street with potholes and other cars.

The Solution: A "Simulated City" for AI
To test how well these robots handle real chaos, the team built ComplexMCP. Think of this not as a simple quiz, but as a giant, simulated video game city with 7 different districts (like a social media town, a stock market, an online store, and a travel agency).

The Tools: Inside this city, there are over 300 different "tools" (buttons, levers, and APIs) the AI can use.
The Chaos: Crucially, these tools are interconnected. You can't just press a button; you might need to fix the network first, check your balance, or verify a user's identity before the tool even works.
The "Seed" Mechanism: To make the test fair but realistic, they use a "seed" (like a random number generator). This ensures that every time they run the test, the city looks slightly different (different users, different prices, different network speeds), but the rules remain the same. This prevents the AI from just memorizing the answers.

The Big Test: Robot vs. Human
The researchers put top-tier AI models (like GPT-5, Gemini, and Claude) into this city and gave them 47 complex missions. They also had real humans do the same tasks using the exact same tools.

The Results: A Stark Reality Check
The results were surprising and sobering:

Humans succeeded about 94% of the time.
The Best AI (Gemini-3-Flash) only succeeded about 55% of the time.
Even the most advanced models struggled to get past 60% success.

Why Do the Robots Fail?
The paper identifies three main reasons why these smart agents stumble in the real world:

The "Tool Overload" (Retrieval Saturation): Imagine a librarian who has to find a specific book in a library with 300,000 books. If you ask them to find a book without giving them a catalog, they get overwhelmed. Similarly, when the AI has to choose from hundreds of tools, it often forgets the right one or gets confused by the sheer volume of options.
The "Clean Slate" Bias (Over-confidence): This is the most common mistake. The AI assumes the world is empty and fresh, like a new game level. In reality, the "shopping cart" might already have items, or the "network" might be broken. The AI skips checking the current state and just tries to act, leading to errors (like trying to buy something you already have). It's like trying to add a new item to a full suitcase without checking if there's room.
Strategic Defeatism: When the AI hits a small error (like a temporary network glitch), instead of trying to fix it (like calling a "network accelerator" tool), it often gives up. It uses its fancy language skills to politely say, "I can't do this," rather than trying a different path to solve the problem. It's like a driver who sees a pothole and immediately turns the car around instead of just steering around it.

What About "Retrieval" (RAG)?
The researchers also tested if giving the AI a "search engine" to find the right tools (instead of showing it all 300 tools at once) would help. While it saved some memory, it actually made the AI worse at these complex tasks. Why? Because the search engine couldn't find the "hidden" tools needed for the next step. It's like asking a librarian for "books about cooking," but the book you actually need is titled "How to bake a cake," and the librarian didn't think to suggest it because the connection wasn't obvious.

The Bottom Line
The paper concludes that while AI is getting smarter, it is still not ready to be a fully autonomous worker in complex, messy real-world environments. It lacks the ability to perceive the current state of the world, recover from small errors, and navigate complex chains of dependencies. ComplexMCP is now the new "driving test" for AI, designed to find these weaknesses so the next generation of robots can learn to drive through the city without crashing.

Technical Summary: ComplexMCP

Problem Statement

Current Large Language Model (LLM) agents demonstrate proficiency in calling isolated APIs but struggle significantly with the "last mile" of commercial software automation. In real-world enterprise and consumer scenarios, tools are rarely independent; they are atomic, highly interdependent, and prone to environmental noise (e.g., network latency, state inconsistencies, and transient errors). Existing benchmarks fail to capture this complexity. Datasets like ToolBench rely on independent RESTful APIs without realistic execution environments, while others like $\tau$ -Bench or BFCL either lack scale, rely on abstract syntax tree matching without real invocation, or utilize precisely predefined environments that lack the ambiguity and stochasticity of real-world settings. Consequently, there is a critical gap in evaluating an agent's ability to robustly navigate large-scale, interdependent tool ecosystems while demonstrating error resilience.

Methodology

The authors introduce ComplexMCP, a rigorous evaluation framework built upon the Model Context Protocol (MCP) to simulate a dynamic, stateful, and stochastic tool ecosystem.

1. System Architecture

ComplexMCP integrates 315 distinct tools across 15 MCP servers, categorized into two paradigms:

Stateful Servers (7 applications): These maintain persistent environment states ( $S$ ) throughout an agent's rollout. They include LightOS (system coordination), LightTalk (social platform), LightShop (e-commerce), LightWeather (meteorology), LightFlight (aviation), LightStock (financial trading), and LightNews (media). These tools exhibit strong interdependencies; for instance, sending a message may require resolving a user ID, verifying network status, and lifting contact blocks.
Stateless Servers (8 applications): These handle independent functional operations (e.g., math, cryptography, chemistry, string processing) without persisting state between calls.

2. Seed-Driven Dynamics

To ensure both reproducibility and environmental diversity, ComplexMCP employs a seed-driven architecture. A single random seed ( $\sigma$ ) deterministically controls:

Environment Initialization: A synthetic knowledge base (user profiles, transaction histories, etc.) is sampled based on the seed, creating unique but structurally consistent environments.
Execution Perturbations: The seed governs stochastic events during execution, such as API failures or network latency, simulating real-world unpredictability.

3. Evaluation Framework

The benchmark utilizes a deterministic, rule-based evaluation system rather than subjective LLM-as-a-judge scoring.

Metrics: The system compares the final environment state ( $env_{new}$ ) against a ground-truth target state ( $env_{gt}$ ) derived from a manually curated instruction set.
Key Indicators:
- Completion Rate ( $R_c$ ): The ratio of correctly modified state elements to the total required changes.
- Misbehaving Rate ( $R_b$ ): The ratio of unintended side effects (modifying state elements that should have remained unchanged).
Success Criteria: A trajectory is deemed correct only if $R_c = 1$ and $R_b = 0$ .

4. Experimental Setup

The authors evaluated 16 state-of-the-art commercial LLMs (including GPT-4o, GPT-5, Gemini series, Claude series, Llama-3, Qwen-3-Max, DeepSeek-V3, etc.) across 47 manually curated tasks. These tasks require coordinating multiple tools without explicit hints, forcing agents to rely on internal reasoning. The study also compared "Full-Context" prompting against Retrieval-Augmented Generation (RAG) strategies (standard and iterative) to assess the trade-off between efficiency and logical integrity.

Key Results

The evaluation reveals a stark performance gap between current SOTA models and human performance:

Success Rates: The highest-performing model, Gemini-3-Flash, achieved a success rate of 55.31%, while GPT-5.1 scored 19.14%. In contrast, human volunteers achieved a 93.61% success rate.
Token Bottleneck: The "Full-Context" ReAct paradigm incurs massive token overhead. For an average task requiring 11 tool rounds, the initial system prompt (containing ~30,000 tokens of tool descriptions) is re-submitted 12 times, resulting in ~360,000 input tokens per task. This creates significant economic and latency costs.
RAG Limitations: While Iterative RAG improved efficiency by reducing token counts, it failed to match the performance of Full-Context methods. The authors attribute this to the inability of semantic retrieval to capture latent tool dependencies essential for complex, multi-step workflows.

Identified Failure Modes

Granular trajectory analysis identified three fundamental bottlenecks:

Tool Retrieval Saturation: As the action space scales (e.g., >300 tools), many models suffer from "cognitive overload," leading to a decline in success rates. While some models (Gemini-3-Flash, Claude-Opus-4) mitigate this via long-context processing, others (GPT-4o, DeepSeek-V3) struggle significantly.
"Clean-Slate" Bias (Over-confidence): Models frequently assume the environment is in a default or empty state, bypassing critical verification steps (e.g., checking existing cart contents or network status). This leads to unintended consequences, such as purchasing redundant items or failing to resolve pre-existing conflicts.
Strategic Defeatism: Upon encountering transient errors (e.g., network timeouts), models often prematurely abort tasks rather than attempting recovery strategies (e.g., retrying or invoking mitigation tools like acc_network). This behavior was notably prevalent in GPT-5, which tended to "politely surrender" rather than pursue fallback solutions.

Significance and Claims

The paper positions ComplexMCP as a critical testbed for the next generation of resilient autonomous systems. Its primary contributions are:

Realism: It is the first benchmark to simultaneously integrate a large-scale toolset with stateful, stochastic, and dynamic environments under a unified MCP-native architecture.
Diagnostic Value: By identifying specific failure modes like "Clean-Slate" bias and strategic defeatism, the work provides a clear roadmap for improving agent robustness, moving beyond simple tool invocation to true environmental perception and recovery.
Standardization: By leveraging the Model Context Protocol, ComplexMCP promotes standardized, reproducible, and interoperable evaluation of tool-use interfaces, addressing the fragmentation in current agent research.

The authors conclude that while current agents show promise, they remain insufficient for interdependent workflows, and ComplexMCP serves as a necessary step toward developing agents capable of handling the complexities of real-world software automation.