acceptodds
Under review as a conference paper at ICLR 2027

Tool Graph Complexity for LLM Tool-Calling: A Reproducible Benchmark Auditing and Generation Framework

Abstract

Language-model agents are increasingly evaluated by how many tools a task requires: benchmarks stratify difficulty by tool count, and leaderboards report accuracy falling as tool lists grow. We argue that this number conflates two different things. One is a property of the benchmark: the reference tool set an agent is scored against often lists tools the task does not need, so recall penalizes any agent that finds a shorter correct plan. The other is a property of the task: how the required tools must compose. We introduce AgentGraphBench, a framework that separates them. It builds a dependency graph over a tool catalog directly from tool schemas, audits an existing benchmark's reference sets against an executable runtime and human-anchored judges, and generates new tasks whose reference set is a sampled subgraph of chosen topology. On StableToolBench, a third to a half of reference tools turn out to be unnecessary, and scoring against the necessary ones raises every agent's recall by about a quarter: much of the reported count-driven degradation is an annotation artifact. On generated tasks with clean references, difficulty is dominated by subgraph size, but at equal size sequential composition stays harder than fan-out or fan-in, and the penalty disappears once dependencies are written out explicitly. What makes tool use hard, then, is inferring dependencies that tool descriptions leave implicit, and the tools agents omit are precisely those the instruction fails to motivate, not those the runtime can do without. We release the framework, a cleaned StableToolBench subset and 2,180 topology-controlled tasks, and we map where the structural ranking transfers: to execution and to a second catalog only in coarse form.

Primary area:
datasets and benchmarks
Keywords:
tool calling, LLM agents, benchmarks, knowledge graphs

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_sZ2tOpenReview ↗
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

1 comment
AuthorsOpenReview ↗

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:

MotifFull AGB (2,180 tasks)AGB-STRICT (451 tasks)
Chain−1.48 [−2.02, −0.95]−2.46 [−3.25, −1.66]
Hourglass−1.20 [−1.73, −0.67]−1.74 [−2.46, −1.01]

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.

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

This paper introduces the AgentGraphBench framework, aiming to resolve the long-standing "tool count" confounding effect in large language model (LLM) tool-calling benchmarks. In my view, the core idea of the framework is to automatically construct port compatibility graphs through the JSON schemas of tools, thereby auditing the reference set annotations of existing benchmarks (such as StableToolBench) and generating multi-tool test tasks with controlled topological structures. The authors find that a considerable proportion of reference tools in traditional benchmarks are non-essential, and scoring solely against necessary tools significantly improves model recall. Meanwhile, after controlling for confounding variables such as subgraph size, the graph topology remains an important difficulty axis affecting tool selection. Finally, the paper releases the audited StableToolBench subset, 2,180 generated tasks covering nine graph motifs, and related replication scripts.

Critical strengths

I believe the biggest highlight of this paper is its sharp focus on the pain point of "non-minimal reference sets" in set-based tool selection metrics. Through a joint audit combining multi-model judges and human studies, the authors powerfully demonstrate that a large number of redundant tools exist in the original benchmarks, and this finding remains highly consistent across different agents and scoring standards.

I appreciate the rigor and restraint demonstrated by the authors in defining the boundaries of their study. For instance, the paper clearly distinguishes between pure tool selection and actual execution phases, acknowledging that motif rankings shift during execution, thereby avoiding the over-generalization of selection accuracy.

Critical weaknesses

I noticed that the judge prompts in the paper provide only isolated tool names and descriptions. In my view, this can only test whether an instruction "motivates" the tool at a literal level, but fails to prove at the execution layer the actual existence of an alternative plan once that tool is removed.

Although the authors claim the generated set is clean, the appendix tables show that up to 79.3% of the validated AGB entries contain removable tools. This largely weakens the core claim of "isolating topological effects via clean reference sets."

There are significant differences in semantic validation rates and generation models across different graph motifs. Covariate regression indicates that some of the so-called "topological difficulty" is essentially a reflection of instruction coverage or text style, lacking cross-generator control experiments, making it difficult to directly attribute it to the graph structure itself.

The authors rely excessively on rule matching and embedding similarity thresholds (such as τ=1.5\tau=1.5) when constructing the tool graph, lacking necessary sensitivity analysis and manual verification. When facing deep nested fields, generic output names (such as result, data), or field aliases in real-world scenarios, such automated graph construction is highly susceptible to misjudgments, introducing false compatibility edges and polluting downstream graph motifs. Furthermore, the evaluation is strictly limited to a small pool of 25 candidate tools, which to some extent curtails the difficulty of open retrieval. More importantly, the framework relies entirely on static topological structures. In practical applications, real-world APIs frequently experience schema updates, parameter changes, or temporary service outages. When migrating from a closed simulation environment to an open and dynamic API ecosystem, what is the robustness of this framework? When underlying APIs dynamically change, how should it cope with the resulting refactoring overhead?

What puzzled me during reading is that key contents—such as extensive core statistical data, detailed robustness analyses, dataset cleaning details, partial control-variable regressions, as well as knowledge graph and execution-phase evaluations—are heavily piled up in the lengthy appendices. This causes the main text to appear insufficiently supported and fragmented when arguing its core claims, forcing readers to frequently jump back and forth between the main text and the lengthy appendices, which seriously impairs reading fluency. I suggest the authors appropriately bring some of the more persuasive core analyses back into the main text.

Questions for authors

please refer to Weaknesses

1 comment
AuthorsOpenReview ↗

Response to Reviewer RFEG

We agree that "clean references" claims more than the construction guarantees. What it does guarantee is that each reference set matches its sampled subgraph exactly. In 79.3% of the 2,180 executable tasks, we could remove at least one non-sink tool, replay the plan, and still get a final output with the same keys and value types (Table 11), though the values themselves could differ. On the 451 tasks where no tool met this removal criterion, Chain was still harder than Star-out for tool selection (log-odds −2.46, 95% CI [−3.25, −1.66], Table 26).

For StableToolBench, the human majority marked 34.4% of 189 query-tool pairs as optional or unnecessary (Table 8), and restricting the reference to tools judged necessary raised recall by 24.0 to 26.2 percentage points across four agents (Table 18). Showing that a tool is dispensable at execution would take a verified alternative plan.

Chain and Star-out share a generator. Hourglass used a different one, and its semantic-validation rate was 46%, compared with 98% for Star-out (Table 9). When success means selecting only the tools the judge left unflagged, the Hourglass coefficient is −0.14 [−0.68, +0.41] (Table 26). We will qualify the topological interpretation to reflect this.

Table 6 reports a threshold of 1.5 on the summed compatibility score and zero penalty for generic names. We will bring §2 in line with these settings and move the recall and strict-subset comparisons to §5. Edge direction and threshold sensitivity have not been independently validated. The fixed 25-tool evaluation tests selection within a known candidate set; open retrieval, schema changes, and service outages are outside its scope.

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

As a dataset and benchmark-related paper, this paper introduces AgentGraphBench, a framework for auditing tool-use benchmarks and generating tasks with controlled tool-graph structure. Its central motivation is that reference-tool count conflates two properties: potentially unnecessary tools included in benchmark annotations, and the composition structure of tools needed to solve a task. To address these 2 issues, the authors construct a compatibility graph from tool schemas, samples subgraphs from motif classes, generates instructions, and provides validators for execution, semantic alignment, minimality, and other properties.

Critical strengths
  1. As highlighted, the paper identifies a practical limitation of reference-set recall: a valid solution can be penalized for omitting a tool included in one reference plan. The scoring sensitivity is demonstrated across four agents, three LLM judges, and human annotations.
  2. Extensive investigation of alternative explanations and limits of generalization for the tool call-related experiments
Critical weaknesses

Some claims are not fully validated. For instance, for the StableToolBench audit, human annotators and LLM judges receive the query and an individual tool description, without the full reference plan or execution evidence. Agreement under this shared information restriction supports reproducibility of the judgment, but does not establish whether a tool is dispensable in a valid solution. A

Questions for authors

As mentioned in the weakness point, have the authors comprehensively validated the claims?

1 comment
AuthorsOpenReview ↗

Response to Reviewer akQR

We agree: what the StableToolBench audit shows is that recall is sensitive to how the reference is defined. Whether a given tool can be dropped at execution time is a different question and needs its own test. Our annotators saw only the query and a single tool description, so their labels tell us whether the request gives a reason to use that tool.

The human study covered 200 query-tool pairs, and 189 of them received a majority label. Of those 189, the human majority marked 34.4% as optional or unnecessary (Table 8). When we kept each agent's selections fixed and restricted the reference to the tools judged necessary, recall rose by 24.0 to 26.2 percentage points across the four agents (Table 18). With the LLM consensus labels on the executable subset, the increase was still 24.5 to 26.0 percentage points (Table 2), so filtering for tool availability leaves the scoring effect largely intact.

We also checked what happens when the judge gets more context. Showing one judge the full reference tool set changed 58 of the 189 labels (Appendix K, Table 21), so the assessment does depend on what the judge can see. To establish that a tool is dispensable, we would need a plan that omits it and still answers the original request correctly.

We will reword the abstract and §5.1 to state the supported conclusion more precisely: across four agents, measured recall increases substantially when the reference is restricted to tools judged necessary from the request.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.