GraphPTC: Guiding Programmatic Tool Calling with Dynamic Execution Graphs

Programmatic Tool Calling (PTC) allows large language models to compose multiple tool calls with control flow and intermediate data processing within a single program block executed in a persistent runtime. Although PTC reduces model-tool interaction rounds, execution across blocks is represented as a linear history of code, standard output, and errors, leaving execution effects and dependencies implicit. Across seven benchmark settings and five backbone models, PTC underperforms Direct Tool Calling in $14$ of $35$ comparisons, by as much as $34.5$ percentage points, indicating that programmatic execution alone does not consistently improve performance. We introduce Graph-Structured Programmatic Tool Calling (GraphPTC), a framework that augments PTC with a task-level dynamic execution graph incrementally constructed from runtime traces. The typed graph captures tool effects, artifacts, states, and failures within blocks and explicitly links dependencies across blocks. It links declared intents to observed effects and provides structured feedback for continuing execution, patching failed steps, replanning dependency paths, or producing an answer. Across all evaluated benchmark–backbone combinations, GraphPTC outperforms both baselines, with average gains of $6.8$ and $6.3$ percentage points over Direct Tool Calling and PTC, respectively. In the efficiency evaluations, it uses $1.7$–$2.3\times$ fewer input tokens than Direct Tool Calling.