- Rating
- 3
- Confidence
- 1
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper introduces AGENTGRAPHBENCH, a framework for auditing tool-use benchmarks and generating tasks with controlled tool-dependency structures. It distinguishes non-minimal reference tool sets from the difficulty of composing tools. The framework constructs a port-level Tool Graph from JSON schemas, audits StableToolBench, and generates tasks by sampling subgraphs from nine topology families with execution, semantic and minimality checks. The audit finds that 34–59% of reference tools are non-essential under the adopted judging protocol, and restricting recall to necessary tools increases reported recall by about 0.24–0.26 across four agents. On the generated tasks, subgraph size explains most of the variation in tool-selection difficulty, while topology provides additional information after controlling for size. Sequential motifs, particularly chains, are harder than stars or trees. The paper also includes boundary checks to clarify where these findings transfer.
Critical strengths
The benchmark audit is the strongest part of the paper for me. If the reference set contains tools that are unnecessary, low recall can reflect a problem with the annotation rather than a failure to solve the task. The authors investigate this directly and distinguish non-minimality from executability cleaning. Human and LLM judgments, agreement statistics and bootstrap confidence intervals give the audit a useful empirical basis. The audit results gives a concrete reason to reconsider how tool-count difficulty and recall are interpreted in existing benchmarks. This is consequential even without the task-generation component.
I also appreciate the care taken in interpreting the topology results. The analysis controls for size, depth, width and question length, and the conclusion is appropriately qualified: size dominates, with additional difficulty associated mainly with sequential composition. The nine-way taxonomy adds a smaller amount beyond that distinction. The execution and transfer checks are useful because they make the limits of the findings visible. Combined with the released auditing and generation artifacts, this gives other researchers a practical way to study structural difficulty under more controlled conditions.
Critical weaknesses
My main concern is whether the generated dependencies consistently represent tools that are necessary to produce the answer. The simulated runtime can return sink answers despite weak input bindings, and 79% of items reportedly contain an answer-removable tool. This makes the distinction between structural minimality and answer-grounded necessity important to the interpretation of the results. The AGB-STRICT subset is a useful response, but I would like a more direct comparison of the main size and topology findings on that subset. The graph constructor also relies on a heuristic compatibility score whose edge quality and directionality have limited validation. Together, these issues leave uncertainty about how closely the generated structures capture genuine tool dependencies.
The topology comparison remains partly confounded by the task generator. Several motif families use different generating LLMs, and semantic-validation quality varies across the same boundary. Although the regressions partially address this, it is difficult to tell how much of a motif’s apparent difficulty comes from its structure and how much comes from differences in the generated questions. A matched generation experiment would make the interpretation more convincing. The fixed 25-tool candidate list also limits the scope of the results. It is a reasonable choice for isolating selection, but conclusions about larger tool registries should remain tentative.
Questions for authors
How do the estimated size and topology effects change on AGB-STRICT? Could you show the relevant coefficients and confidence intervals alongside the full-set results? Given the high proportion of answer-removable tools under the simulated runtime, this comparison would help assess whether the main structural conclusions survive a stricter notion of necessity
Can you disentangle generator effects from motif effects on a matched subset? In particular, does the Hourglass penalty remain when the same generator produces tasks across motif families with comparable sizes? Please report semantic-validation outcomes seperately, since these also seem to vary with the generator–motif assignment
How sensitive are the structural findings to the compatibility function κ and threshold τ? A small manual check of edge correctness and directionality, together with a sensitivity analysis of the construction settings, would help establish whether the conclusions depend on a particular heuristic graph
Response to Reviewer sZ2t
Chain and Hourglass are both still harder than Star-out on AGB-STRICT. Table 26 gives the log-odds coefficients for selecting all reference tools, with 95% confidence intervals:
The strict-subset model has fewer controls, which limits how directly the magnitudes in the two columns can be compared. On full AGB the size coefficient is −0.70 per additional tool (95% CI [−0.84, −0.56], Table 1); we did not report the corresponding adjusted coefficient for AGB-STRICT. Going from two to eight tools, pooled complete-set success drops from 95.0% to 53.5% on full AGB and from 92.1% to 60.6% on AGB-STRICT (Tables 4 and 30).
The case for an effect that does not depend on the generator is stronger for Chain. Chain and Star-out come from the same generator, and the contrast between them survives adjustment for the number of tools the judge flagged as unnecessary (−1.12 [−1.63, −0.60]). Hourglass came from a different generator, and its semantic-validation rate was 46%, compared with 96% for Chain and 98% for Star-out (Table 9). If success is defined as selecting only unflagged tools, the Hourglass coefficient is −0.14 [−0.68, +0.41] (Table 26). We cannot yet say whether the Hourglass contrast would hold under matched generation.
Table 6 lists the graph construction settings. We did not test sensitivity to the threshold, and we did not manually check edge direction. The second catalog uses declared dependencies (Table 31), so it cannot serve as independent validation of the inferred edges.