Research map / Multi-agent systems and games / LLM agents

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

ICML 2026 · Multi-agent systems and games › LLM agents · approach: Robust and efficient agent execution · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces ComplexMCP, a seed-driven, MCP-based benchmark of 47 tasks over 315 tools in 7 stateful sandboxes, with rule-based state-diff evaluation; top models reach ~55% success versus 93.6% for humans.

Problem

LLM agents struggle with large-scale, interdependent, stateful tool ecosystems with environmental noise and API failures, which existing tool-use benchmarks do not realistically simulate.

Approach

A seed-driven MCP benchmark combining stateful sandboxes with interdependent tools, stochastic perturbations, and deterministic key-path state-diff evaluation (completion and misbehaving rates) instead of LLM judges.

Key results

• Gemini-3-flash achieves the highest success rate at 55.31% under full-context ReAct, versus 93.61% for human volunteers.
• Iterative RAG with Gemini-3-flash reaches 36.88% success at lower prompt tokens (334) than full-context, but below full-context performance.
• GPT-5.1 reaches only 19.14% success, with the paper attributing failures to premature giving up ('strategic defeatism').

Surprising findings

• GPT-5.1 often gives up politely after transient token errors instead of recovering, yielding mediocre success despite strong reasoning.
• Retrieval-based RAG (including iterative RAG) fails to match full-context performance because interdependent prerequisite tools are not surfaced by semantic retrieval.

Limitations

• Only 47 manually curated test instructions, limiting scale.
• Manual annotation of ground-truth trajectories is labor-intensive and costly.
• Human baseline uses only three volunteers with one attempt per task.

Experimental setup

Datasets: Synthetic Knowledge Base (LLM-generated entities)

Benchmarks: ComplexMCP

Metrics: success rate completion rate misbehaving rate valid invocations invalid invocations token length

Baselines: GPT-4o GPT-5.1 Gemini-2.5-pro Gemini-3-pro Claude-sonnet-4.5 Claude-opus-4 Llama-3.1-405B-Instruct Qwen-3-max DeepSeek-V3 Kimi-K2 GLM-4.7

Builds on: ReAct Model Context Protocol ToolLLM tau-bench

Closest papers by meaning

• MCPMark: A Benchmark for Stress-Testing Realistic and Comprehensive MCP Use (ICLR 2026 · similarity 0.90)
• MCP-Atlas: A Large-Scale Benchmark for Tool-Use Competency with Real MCP Servers (NeurIPS 2026 · similarity 0.89)
• OSWorld-MCP: Benchmarking MCP Tool Invocation In Computer-Use Agents (ICLR 2026 · similarity 0.89)
• Why Do Multi-Agent LLM Systems Fail? (NeurIPS 2025 · similarity 0.89)
• Claw-Eval: Towards Trustworthy Evaluation of Autonomous Agents (NeurIPS 2026 · similarity 0.89)
• General Agent Evaluation (NeurIPS 2026 · similarity 0.88)