Let Agents Know how Hard this Work is

In LLM-based agent system, effective task planning is essential for accurate and successful execution. This requires the agent to accurately understand the complexity of current task and decompose it appropriately. Most of the existing agent systems rely on the inherent capabilities of large language models to address the problem of understanding task complexity. However, because LLMs lack an explicit and measurable task-complexity signal for determining an appropriate planning depth, agent systems may produce inappropriate planning. In this paper, we propose a measurable notion, termed “Task Complexity”, for evaluating task difficulty. We define task complexity as: the minimum number of planning steps required for a fixed agent system to complete a given task with a success rate threshold. This notion of Task Complexity provides an agent-dependent characterization of task difficulty and offers empirical insight into the capability limits of an agent system across different tasks. Experiments across multiple tasks and agents show that Task Complexity produces stable task-difficulty rankings, predicts execution success under different planning steps, and reveals systematic differences between the capability boundaries of agent systems. We further demonstrate that Task Complexity can guide task decomposition by adapting planning steps to the demands of individual tasks. These results establish Task Complexity as a measurable foundation for complexity-aware planning and agent-system evaluation.