- 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?