acceptodds
Withdrawn from ICLR 2027

Let Agents Know how Hard this Work is

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
applications to robotics, autonomy, planning
Keywords:
LLM, agent, mulit-agent, planning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_iNfTOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This main contribution of this paper is to propose a measurement for agent task complexity in the multi-agent system. The main evaluation metrics is the minimum number of planning steps required for a fixed agent system to achieve a prescribed success probability. The authors empirically validate this quantity through repeated executions of CAMEL and MetaGPT on GSM8K and HotpotQA subsets, and examine its repeatability, and present a small case study predicting complexity from similar historical tasks.

Critical strengths
  • Defining difficulty for an entire multi-agent system, including its executor, tools, and interaction protocol, is conceptually reasonable, and can be used for further investigation.

  • The measurement procedure correctly allows success probability to be non-monotonic in planning length. The reported results illustrate why simply allocating more planning steps can be counterproductive.

  • The paper distinguishes tasks that reach the reliability threshold from those that remain unsolved within the evaluated budget.

Critical weaknesses

While the problem studied in the paper is important, I do not think the authors provide a comprehensive studies and enough novelty for the paper to be accepted.

  • The empirical task complexity estimator lacks adequate uncertainty control. Each success probability is estimated from only 20 executions, and 13 successes are sufficient to cross the threshold of 0.65. At a true success probability of 0.65, the std is approximately 0.107. Even when the true probability is only 0.60, the probability of observing at least 13 successes is approximately 41.6%. Selecting the smallest qualifying budget across several candidates introduces additional selection effects. This makes the results less convincing

  • The threshold was selected after inspecting the results. Section 4.2 states that 0.65 was chosen to retain many tasks with finite empirical complexity. This makes the reported coverage and complexity distributions dependent on a data-informed evaluation choice.

  • The existence of a minimum qualifying budget is largely definitional. For a finite set of candidate budgets, a minimum exists whenever the qualifying set is nonempty. The substantive contribution therefore depends on showing that this quantity is reliably estimable and useful for prediction or planning. The current experiments provide limited evidence for these stronger claims.

  • The practical planning benefit is not established. The main evaluation contains only 35 task instances and one backbone model. The prediction study has five target tasks and evaluates agreement with measured complexity, rather than downstream success and cost. It does not establish whether allocating the predicted budget improves the success–cost trade-off over fixed-budget, unconstrained, or adaptive planning baselines.

  • Planning-step count is not a sufficient measure of cross-system efficiency. Comparing systems requires matching executor budgets or measuring total tokens, tool calls, and latency. Fewer steps need not imply lower computational cost when individual steps differ across frameworks.

Questions for authors
  • How stable are the complexity labels and system rankings under independent confirmation runs and different reliability thresholds?

  • Can uncertainty-aware estimation substantially be provided together and to the change of the reported minimum budgets?

  • Does complexity-guided planning improve actual task success and cost on a substantially larger held-out evaluation?

Reviewer_rpZuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes an agent-relative measure of task difficulty: the smallest number of executable planning steps at which a fixed agent system attains a specified success probability. It estimates this quantity by repeatedly executing each task at every candidate step count, selecting the first empirical threshold crossing, and recording tasks that never cross as outside the tested range. Experiments use CAMEL and MetaGPT with GPT-4o-mini on 25 GSM8K and 10 HotpotQA instances, with 20 trials per task and step count. The paper reports non-monotonic success profiles, differences in the systems' complexity distributions despite equal coverage rates, and a repeatability study. A five-target case study predicts complexity from similar historical tasks, achieving four exact matches.

Critical strengths
  1. A concrete system-relative measurement. Sections 3.1-3.2 include the planner, executor, tools, memory, and execution policy in the evaluated system. A step corresponds to one bounded executor invocation, preventing unlimited work within a nominal step. Exhaustive scanning accommodates non-monotonic success and records failure to reach the threshold, giving the metric a clear operational meaning. This is its strongest conceptual contribution.

  2. Controlled planning-length variation exposes over-decomposition. Both frameworks share the backbone and task instances, with configurations fixed as step count varies. In Table 2, MetaGPT falls from 74.0% at two steps to 13.4% at six on GSM8K, and from 67.5% at four to 12.5% at eight on HotpotQA. Despite the small task sample, these results motivate studying planning granularity.

Critical weaknesses
  1. Measurement reliability and stability remain insufficiently established. Eq. (5) accepts 13 successes in 20 trials; the approximate 95% Wilson interval [0.43, 0.82] leaves substantial uncertainty about reaching a true success rate of 0.65. Searching six or eight budgets adds opportunities for accidental crossings, potentially understating complexity or overstating coverage. Section 4.2 selects the threshold after inspecting results, without sensitivity analysis. Table 3 usefully repeats measurement, but omits task identities, distinct-task counts, success-rate margins, and uncertainty; its complexity-six cases are absent from Tables 4-5 and need clarification. These gaps matter because measurement stability is central and the reported system differences on these sampled tasks are small: mean complexity 1.63 versus 1.50 on covered GSM8K tasks and 3.50 versus 3.00 on covered HotpotQA tasks.

  2. Practical planning value is not demonstrated. Section 4.5 predicts labels for five targets using five historical tasks per group, but reports no execution outcomes or comparisons with fixed, unconstrained, or adaptive planning. Given non-monotonic success curves, prediction within one step does not establish reliability. Table 1's single-task token comparison establishes neither an overall success-cost advantage nor the amortization of offline measurements. The main study contains only 35 distinct instances, sampled using an unspecified preliminary agent; repeated execution does not establish task-level generality. ADaPT already adapts decomposition to executor capability, and Adaptive-RAG derives labels from the simplest successful retrieval strategy. The cited works differ from this reliability-conditioned metric, but stronger evidence is needed to establish its added value. This missing validation is decisive for my recommendation.

Questions for authors
  1. How robust are the complexity estimates and framework comparisons to sampling and threshold choice? Please provide the per-task success counts at each budget, uncertainty for the selected minimum and coverage, and results across several independently motivated thresholds. For Table 3, which tasks, systems, and datasets were used, how many distinct tasks contribute to each row, and where do the complexity-six cases come from? Evidence that the conclusions survive independent validation and threshold variation would materially improve my assessment.

  2. What exact execution protocol makes a step comparable and reproducible? Please specify the per-invocation token/action/tool/time caps, their equality or differences across frameworks, prompts and enforcement of exactly k non-empty executable steps, framework/model versions and decoding settings, and success evaluators. Which agent generated the preliminary stratification, and which benchmark splits and task IDs were sampled? These details would determine whether the measured differences reflect comparable resource constraints and a reproducible task distribution.

  3. Are there held-out execution results demonstrating the benefit of the predicted budgets? A comparison with fixed and unconstrained planning under the same executor would be particularly informative, reporting success and total tokens or latency, with offline label-generation cost identified separately. Please also specify task-group construction, the embedding and similarity-weight calculation, rounding to an integer budget, and how any selected budget that fails the threshold is handled. Such evidence could establish the proposed signal's utility beyond agreement with noisy measured labels and could change my recommendation.

Reviewer_yFWoOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces Task Complexity: the minimum number of planning steps a fixed agent system needs to reach a target success probability. Each step invokes a bounded executor, and complexity is measured through repeated executions across plan lengths. Experiments on arithmetic and multi-hop question answering show that additional steps can reduce success and that favorable plan lengths vary across datasets. A small study predicts the measured complexity of new tasks using similar historical tasks, matching four of five targets.

Critical strengths

The paper studies a worthwhile question within the plan-then-execute paradigm: how should task decomposition match an executor's capabilities? The observation that longer plans can reduce success, with different favorable lengths across datasets, motivates further investigation of this interaction.

Critical weaknesses
  • The roles of planner and executor capabilities remain unexplored. Both frameworks use GPT-4o-mini, so the observed sensitivity to plan length may reflect its planning or execution limitations. The paper does not examine how stronger models or better context handling change these patterns. Since the metric is explicitly agent-relative, this omission is not only a missing robustness analysis but limits its interpretation and the conclusions drawn from it.
  • The observations provide limited actionable insight. The paper does not explain why favorable plan lengths differ or how the findings should guide better plans and execution protocols. Measuring complexity also requires many executions in environments that allow repeated trials. The five-task prediction study reports agreement with complexity labels without demonstrating improved execution success or lower cost.
  • Poor reproducibility. The paper provides no code. Key details, including prompts, decoding settings, executor resource limits, and precise success-evaluation rules, are also missing.
  • The task sample provides limited evidence of broader applicability. The main evaluation covers only 25 GSM8K and 10 HotpotQA tasks, selected according to plan lengths observed in preliminary runs. It is unclear how representative this subset is or whether the findings extend to longer, interactive tasks.
Questions for authors

How would the success-versus-step curves change with a stronger planner or executor under matched resource limits? This would help clarify what drives the measured complexity.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.