acceptodds
Under review as a conference paper at ICLR 2027

GraphPTC: Guiding Programmatic Tool Calling with Dynamic Execution Graphs

Abstract

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 of comparisons, by as much as 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 and percentage points over Direct Tool Calling and PTC, respectively. In the efficiency evaluations, it uses – fewer input tokens than Direct Tool Calling.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, programmatic tool calling, dynamic execution graphs, graph-guided action selection, tool-use efficiency

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_woBZOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

The paper introduces GraphPTC, a framework designed to improve PTC by explicitly tracking execution effects and dependencies across program blocks. The authors argue that conventional PTC relies on linear execution histories, making it difficult for LLM agents to track intermediate results, state changes, and failures. To address this, GraphPTC constructs a dynamic execution graph that captures tool calls, artifacts, state changes, and cross-block dependencies. It also tracks execution progress and provides structured feedback to guide the agent in continuing execution, repairing failed steps, or replanning. The authors evaluate GraphPTC across seven benchmark settings and five backbone models, reporting consistent improvements over both Direct Tool Calling and standard PTC. They also report reduced input token usage and generally fewer interaction rounds compared with Direct Tool Calling.

Critical strengths
  • Important problem and practical solution: The paper addresses an important challenge in programmatic tool calling, where tracking execution effects and dependencies across program blocks can be difficult. The proposed framework provides a practical approach to improving execution tracking and guiding subsequent agent actions, including failure recovery.

  • Comprehensive evaluation and consistent improvements: The paper evaluates GraphPTC across seven benchmark settings and five backbone models, covering different tool-use scenarios. The results show consistent improvements over both Direct Tool Calling and standard PTC, along with reduced input token usage compared with Direct Tool Calling. This relatively broad evaluation and the consistent performance gains provide meaningful evidence of the framework's practical effectiveness.

Critical weaknesses
  • Limited comparisons with simpler alternatives and unclear graph-specific novelty: Although the paper discusses related approaches, it remains unclear whether the improvements come specifically from the proposed graph structure or simply from providing more structured execution feedback. The evaluation only compares GraphPTC against Direct Tool Calling and standard PTC, without considering simpler PTC variants using structured execution summaries, failure tracking, or basic recovery guidance. This limits the evidence supporting the necessity and novelty of the proposed graph-based approach.

  • Insufficient component-level ablations: Although the paper includes an ablation study, removing the execution graph also removes its associated feedback and recovery mechanisms. As a result, it is difficult to determine which components are responsible for the reported improvements. More targeted ablations on cross-block dependency tracking, state versioning, equivalence detection, progress assessment, and recovery guidance are needed to better understand the contribution of each component and justify the proposed design.

Questions for authors
  • How can the authors distinguish the benefits of the proposed graph structure from those of simply providing more structured execution feedback? Have they considered comparisons with simpler PTC variants, such as structured execution summaries, explicit failure tracking, or basic recovery guidance, to better establish the necessity and novelty of the proposed approach?

  • What is the individual contribution of each major component of GraphPTC? Could the authors provide more targeted ablations on cross-block dependency tracking, state versioning, equivalence detection, progress assessment, and recovery guidance to clarify which components drive the reported improvements?

  • How reliably do the proposed progress and intent-realization indicators reflect actual task progress? For example, how does the method distinguish between retrieving new but irrelevant information and making meaningful progress toward the task objective? Have the authors evaluated the accuracy of these indicators?

  • Given that several improvements are relatively small, could the authors provide confidence intervals, statistical significance tests, or information about run-to-run variability to better establish the reliability of the reported improvements?

  • How much manual effort is required to define the tool-specific contracts used for execution tracking and equivalence detection? How sensitive is GraphPTC to incomplete or inaccurate contracts, and what challenges might arise when applying the framework to new or more complex tool environments?

7 comments
AuthorsOpenReview ↗

Response to Reviewer woBZ(1/5)

We sincerely thank you for recognizing the importance of the problem, the practicality of our method, and the breadth and consistency of our evaluation. Your questions on the necessity of the graph structure, the contribution of each component, and the reliability of our indicators help us present the design of GraphPTC more clearly. Please find our responses below.

Q1: Comparison with simpler PTC variants (structured execution summaries, explicit failure tracking, and basic recovery guidance), and the necessity and novelty of the graph-based approach.

A1: Thanks for raising this question. The simpler PTC variants you suggest are the most direct way to test the necessity of the graph structure. We first explain the novelty of GraphPTC, then add the comparison with these variants as you suggested, and finally use concrete cases to show that they cannot replace the execution graph.

1. The novelty of GraphPTC lies beyond structured feedback

Structured feedback is not new. The novelty of GraphPTC is a closed loop that uses an execution graph to connect agent intents, actual execution effects, and subsequent decisions. In each round, the agent first declares an intent and its target node. After execution, the runtime trace is added to the execution graph and linked to earlier blocks through cross-block relations such as result equivalence, artifact consumption, and state supersession. The system then assesses progress based on these relations and gives repair or replanning hints tied to specific nodes.

2. Simpler PTC variants: the graph structure brings most of the gain

Following your suggestion, we add structured execution summaries, explicit failure tracking, and basic recovery hints to PTC step by step. These variants receive the same intra-block information as GraphPTC but no cross-block relations. We also add a variant that rewrites the graph feedback as plain text, which rules out the effect of feedback format. All variants share the same feedback budget and use MiMo-V2.5 as the backbone:

MethodBrowseComp-PlusAppWorld-NAppWorld-CAvgInput Tokens
PTC30.184.580.264.91.00×
+ Structured Summary31.685.881.366.21.17×
+ Failure Tracking & Recovery Hint32.487.282.667.41.21×
Linearized GraphPTC40.391.486.172.61.30×
GraphPTC42.292.987.674.21.24×

Together, the three simpler alternatives improve PTC by only 2.5%, about 1/4 of the total gain of GraphPTC (9.3%). They share the same intra-block information with GraphPTC and differ only in cross-block relations, yet they still fall behind by 6.8% at a similar token cost. Meanwhile, Linearized GraphPTC keeps most of the gain, so the improvement comes from the content provided by the graph rather than the feedback format. These results confirm that the graph structure is necessary for the gains of GraphPTC, and structured feedback alone cannot match them.

3. Execution graph: irreplaceable by simpler variants

Simpler variants describe each block in isolation and cannot connect one block to another. The three cases in the appendix compare PTC with GraphPTC. Simpler variants also lack cross-block relations and therefore face the same problems:

  • Repeated retrieval (Case 1). Two differently phrased searches return the same page. Without cross-block relations, they are recorded as two separate results. GraphPTC detects the repetition through an equivalence relation, and the agent stops the redundant search.
  • Targeted repair (Case 2). After a send operation fails, the agent without cross-block relations often reruns the lookups that already succeeded. GraphPTC locates the failure at the exact call, so PATCH retries only the failed send and reuses the existing results.
  • State update (Case 3). A write updates the phone number of a contact. Without cross-block relations, the old and new numbers both remain in the history, and the agent may use the old one. GraphPTC links the two through a state version relation and points to the updated value.

All three judgments rely on the execution graph accumulated across blocks. They also match the largest gaps in the table above: BrowseComp-Plus, which requires detecting repeated retrieval (9.8%), and AppWorld, which depends on state tracking and targeted repair (5.0% to 5.7%).

Thanks again for your suggestion. We will add these simpler variants as baselines and include a discussion of structured-feedback methods in the revision.

AuthorsOpenReview ↗

Response to Reviewer woBZ(2/5)

Q2: Targeted ablations on cross-block dependency tracking, state versioning, equivalence detection, progress assessment, and recovery guidance, and the individual contribution of each component.

A2: Thanks for your suggestion. Following your list, we ablate each of the five components from the full GraphPTC. We first explain the design motivation of each component, then report its individual contribution, and finally show how the components work together as a whole.

1. Design motivation: each component addresses one failure mode

The five components address the three layers of limitations of linear execution histories identified in Sec. 1, and each one solves a specific problem:

  • Cross-Block Dependency (representation layer): lets a later block directly locate the earlier artifacts it needs, instead of searching through the linear history.
  • State Versioning (representation layer): separates old and new versions after a write, so later operations do not read stale values.
  • Equivalence Detection (analysis layer): recognizes differently phrased retrievals that return the same results, so repeated results are not counted as progress.
  • Progress Assessment (analysis layer): detects stagnation, where execution runs without errors but produces no new effect, and prompts replanning.
  • Recovery Guidance (decision layer): locates a failure at the exact call and repairs only the failed part, keeping the results that already succeeded.

2. Component ablations: every component contributes on its own

Using MiMo-V2.5 as the backbone, we remove one component at a time from the full GraphPTC. Each variant removes only the relations or mechanism of one component, while the other components still run on the execution graph:

MethodBrowseComp-PlusAppWorld-NAppWorld-CAvgΔ Avg
GraphPTC42.292.987.674.2–
w/o Cross-Block Dependency38.689.584.770.9−3.3
w/o State Versioning42.290.284.172.2−2.0
w/o Equivalence Detection36.492.086.871.7−2.5
w/o Progress Assessment37.591.085.371.3−2.9
w/o Recovery Guidance40.689.684.271.5−2.7

Removing any single component lowers the average performance by 2.0% to 3.3%, and each contribution shows up mainly on the tasks the component is designed for:

  • Cross-Block Dependency contributes the most. Removing the consumes/reuses edges lowers all three tasks by about 3% to 4%, since later blocks can no longer directly locate the earlier artifacts they rely on.
  • State Versioning mainly helps AppWorld, which requires persistent writes (−3.5% on Challenge), and has no effect on the read-only BrowseComp-Plus.
  • Equivalence Detection mainly helps retrieval. Removing it lowers BrowseComp-Plus by 5.8%, but AppWorld by less than 1%.
  • Progress Assessment matters most in long-horizon retrieval. Removing it lowers BrowseComp-Plus by 4.7%, since such tasks are the most prone to unproductive loops.
  • Recovery Guidance mainly helps AppWorld (−3.3% to −3.4%), where failures often occur in writes that need repair.

Each component therefore makes a clear and distinct contribution, and the contributions match the design motivations.

3. Component synergy: the graph mechanism works as a whole

The drops from removing each component add up to 13.4%, more than the total gain of the graph mechanism over PTC (9.3%). The components do not simply add up but depend on each other. Equivalence detection allows progress assessment to recognize repetition correctly, cross-block dependencies let PATCH reuse the results that already succeeded, and state versions let recovery use the correct values. All of them run on the same execution graph. The effectiveness of GraphPTC therefore comes from the coordination of these components rather than from any single one.

Thanks again for your suggestion. We will add the component ablations, along with the design motivation and contribution of each component, to the revision.

AuthorsOpenReview ↗

Response to Reviewer woBZ(3/5)

Q3: Reliability of the progress and intent-realization indicators, including the distinction between new but irrelevant information and meaningful progress, and the accuracy of these indicators.

A3: Thanks for this important question. The progress and intent-realization indicators in GraphPTC are execution-level signals that reliably detect repetition and stagnation. The relevance of new information to the task is judged by the agent, which sees the actual content. We first explain this division of labor, then validate it experimentally, and finally report the accuracy of each indicator.

1. Role of the indicators: the system detects execution effects, and the agent judges relevance

ptp_t checks whether the current round produces new execution effects. Repeated retrievals with equivalent results are not counted as new artifacts, and writes that leave the state unchanged are not counted as state changes. The intent realization flag builds on this and depends on the action type (Appendix B). For example, a PATCH is realized when the repair block runs successfully. Both indicators are computed by deterministic rules without extra model calls.

Judging the relevance of new information requires understanding its content, which rules cannot do reliably. GraphPTC therefore leaves this judgment to the agent. In each round, the feedback shows the declared action and expected change together with the new artifacts, equivalent artifacts, state changes, and failures of the current round. With the content of new artifacts in view, the agent decides whether the outcome moves the task forward and then chooses CONTINUE, PATCH, or REPLAN.

2. Effectiveness of this design: close to per-round semantic judgment at no extra cost

We compare different progress signals with MiMo-V2.5, including an extra LLM call in every round that checks intent realization against the expected change:

Progress SignalBrowseComp-PlusExtra LLM Calls
w/o Progress Assessment37.50
No-error execution37.90
LLM-judged intent realization42.8+1 per round
ptp_t (Ours)42.20

ptp_t improves performance by 4.7% over the variant without progress assessment, while checking only for errors brings almost no benefit. Per-round LLM judgment is only 0.6% better than ptp_t but needs one more model call in every round. This shows the agent already makes most semantic judgments when reading the feedback, and the division of labor effectively separates irrelevant information from real progress.

3. Accuracy: repetition and stagnation are detected with high precision

We randomly sample 300 blocks from the execution logs and manually label whether each block advances the task and whether its equivalence edges are correct:

IndicatorPrecision
equivalent_to edge98.1%
pt=0p_t=0 (no progress)96.2%
Stagnation-triggered REPLAN prompt93.1%

All three signals reach over 93% precision, so the system rarely misjudges repetition or stagnation and can safely trigger replanning. The new but irrelevant retrievals you mention are counted as new effects by ptp_t, which are exactly the cases left to the agent. In addition, Figure 3(c) shows that recovery actions are 3.4 to 5.2 times more likely after an unrealized intent than after a realized one. These results show that the indicators reliably reflect execution progress and effectively support subsequent decisions of the agent.

Thanks again for your question. We will clarify the role of these indicators and their division of labor with the agent, and include these experiments and the accuracy evaluation in the revision.

Reviewer_4kakOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors propose the GraphPTC framework, which extends Programmatic Tool Calling (PTC) by dynamically converting runtime traces into a typed execution graph comprising intents, program blocks, calls, artifacts, state versions, and failure information. By leveraging graph differencing and bounded graph feedback to guide execution continuation, targeted repair, replanning, or answering, GraphPTC is able to automatically track dependencies and guide decision-making in multi-step tool-calling tasks.

Critical strengths
  • This work captures the persistent pain points of persistent code execution (PTC)—namely cross-block artifact reuse, state changes, and long-term implicit failure information—and provides compelling improvements through an explicit typed execution graph.
  • The authors conduct extensive evaluations across 7 benchmarks and 5 backbone models, demonstrating comprehensive performance gains and significant input token efficiency optimization.
Critical weaknesses

Frankly speaking, the core causal mechanism is not cleanly isolated. In the ablation study of Table 2, the authors simultaneously remove the "execution graph" along with the graph feedback and recovery mechanisms, which essentially ablates the entire packaged solution. It is hard for me to determine from these results whether the performance boost stems from the graph structure itself or from the carefully tuned text feedback templates or prompt engineering. At a minimum, the authors should provide a control experiment, such as serializing the structured graph feedback into plain text trajectories for comparison.

Moreover, the mathematical definitions and key semantic operations appear insufficiently rigorous. Equation (3) introduces κ(v)=κ(v′)\kappa(v) = \kappa(v') for artifact equivalence, yet upon checking the main text, there is no explanation of the specific form of κ(⋅)\kappa(\cdot) or the tool contracts. Additionally, Equation (5) defines "progress" too broadly—any new artifact or state change is straightaway counted as pt=1p_t=1—which makes it feel more like "the code generated some activity" rather than a genuine realization of the declared intent.

The experimental protocol and efficiency attribution also have blind spots. The main text fails to clearly specify key operational parameters such as the feedback character budget BB and stagnation thresholds, and the results rely entirely on point estimates without variances or significance tests. What puzzles me is why the efficiency analysis in Table 3 compares performance and tokens exclusively against Direct Tool Calling; I would much rather see PTC included under identical conditions as a baseline control.

During my review, I also noticed that the paper completely lacks empirical comparisons or in-depth discussions against other contemporary SOTA graph-structured tool planning and dynamic runtime graph methods (such as GraSP[1], HyperAgent[2], or other recent advanced tool-orchestration frameworks). By exclusively comparing against its own stripped-down variants (Direct Tool Calling and PTC), the evaluation fails to demonstrate whether GraphPTC truly outperforms existing SOTA alternatives. Furthermore, the authors fail to clearly distinguish their runtime artifact/state lineage graph from existing tool schema graphs, skill taxonomies, or broader graph-based agent architectures.

[1] Xia et al.(2026), GraSP: Graph-Structured Skill Compositions for LLM Agents

[2] Zhai et al.(2026), HyperAgent: Planning and Acting over Tool-Schema Hypergraphs for Tool-Use LLM Agent

Questions for authors

please refer to Weaknesses

8 comments
AuthorsOpenReview ↗

Response to Reviewer 4kak(1/6)

Thank you for recognizing our work and for your in-depth, specific comments. Your points on isolating the causal mechanism, formal definitions, and baseline comparisons are very helpful for improving the paper. We address them one by one below.

Q1: About whether the gains come from the graph structure itself or from feedback templates and prompt engineering.

A1: Thanks for this frank and helpful comment. To clearly isolate the source of the gain, we first explain it from the mechanism design, then add the plain-text control you suggested, and finally use component ablations to locate the role of each part.

1. Source of the gain: the execution graph drives the mechanism, and templates only present its output

In GraphPTC, agent behavior is driven by the execution graph rather than the feedback template. In each round, the agent first declares an intent and its target node. After execution, the runtime trace is added to a typed execution graph and linked to earlier blocks. The system then checks progress on the graph and returns bounded feedback, together with the actions available next (CONTINUE, PATCH, REPLAN, or ANSWER).

The key information in the feedback is all computed from the graph, such as equivalent results across blocks, stalled targets, failed calls, and successful artifacts that can be reused for repair. The template only turns this information into text. Without the graph, none of this information is available, and equivalence detection, stagnation detection, and targeted repair cannot be triggered. In addition, the feedback templates and action rules of GraphPTC are fixed across all settings and backbones with no per-benchmark tuning.

2. Plain-text control: the gain comes from graph content, not templates

Following your suggestion, we serialize the graph feedback into a plain-text trajectory (Linearized GraphPTC). This removes typed fields and node references and keeps only the content derived from the graph. We also add controls from the opposite direction, where PTC uses the same structured feedback template as GraphPTC but receives no cross-block dependencies. All variants share the same feedback budget and use MiMo-V2.5 as the backbone:

  • Linearized GraphPTC: the same graph feedback, rewritten as plain text.
  • + Structured Summary: PTC with a structured execution summary (calls, read/write effects, success flags, and failures) but no cross-block relations.
  • + Failure Tracking & Recovery Hint: further adds explicit failure tracking and generic recovery hints.
MethodBrowseComp-PlusAppWorld-NAppWorld-CAvgInput Tokens
PTC30.184.580.264.91.00×
+ Structured Summary31.685.881.366.21.17×
+ Failure Tracking & Recovery Hint32.487.282.667.41.21×
Linearized GraphPTC40.391.486.172.61.30×
GraphPTC42.292.987.674.21.24×

The two controls point to the same answer. In plain text, Linearized GraphPTC still keeps about 83% of the gain (72.6 vs. 74.2). With the structured template but no graph content, the two summary variants improve PTC by only 2.5%. They also trail GraphPTC by at least 6.8% at a similar token cost. The gain of GraphPTC therefore comes mainly from the cross-block dependencies provided by the execution graph, not from feedback templates or prompt engineering.

AuthorsOpenReview ↗

Response to Reviewer 4kak(2/6)

A1 (continued)

3. Component ablations: locating the role of each part

To isolate the mechanism at a finer level, we remove each of the five components from the full GraphPTC. They address the three layers of limitations identified in Sec. 1:

  • Cross-Block Dependency (representation layer): lets each block directly find the earlier artifacts it relies on.
  • State Versioning (representation layer): separates old and new state versions so that later operations do not read stale values.
  • Equivalence Detection (analysis layer): recognizes differently phrased retrievals that return equivalent results.
  • Progress Assessment (analysis layer): detects stagnation without new effects and prompts replanning.
  • Recovery Guidance (decision layer): locates each failure at a specific node and repairs only the failed calls.

Each variant removes only the relations or mechanism of one component, while the other components still run on the execution graph.

MethodBrowseComp-PlusAppWorld-NAppWorld-CAvg
GraphPTC42.292.987.674.2
w/o Cross-Block Dependency38.689.584.770.9
w/o State Versioning42.290.284.172.2
w/o Equivalence Detection36.492.086.871.7
w/o Progress Assessment37.591.085.371.3
w/o Recovery Guidance40.689.684.271.5

Each removal hurts the tasks that the component is designed for. Without equivalence detection, the retrieval task BrowseComp-Plus drops by 5.8%. Without state versioning or recovery guidance, the loss mainly appears on AppWorld, which requires persistent writes. State versioning has no effect on the read-only BrowseComp-Plus. If the gain came from a generic template or prompt, removing a single component would not cause drops that align with its design purpose. The drops from removing each component also add up to 13.4%, more than the total gain over PTC (9.3%), so the components depend on each other. This further confirms that the effectiveness of GraphPTC comes from the execution graph and the full mechanism built on it.

Thanks again for your suggestion. We will add this explanation, the plain-text control, and the component ablations to the revision.

AuthorsOpenReview ↗

Response to Reviewer 4kak(3/6)

Q2: About the definitions of κ(⋅)\kappa(\cdot) and tool contracts, and whether ptp_t reflects a genuine realization of the declared intent.

A2: Thanks for your careful review. We provide the full formal definitions of κ(⋅)\kappa(\cdot) and tool contracts below. As for ptp_t, it detects new execution effects, while the declared intent guides progress assessment through target binding and the feedback. It does not simply record that the code generated some activity as you mentioned.

1. Formal definition of κ(⋅)\kappa(\cdot) and tool contracts

Equivalence detection targets differently phrased queries that return the same result, a kind of repetition that is hard to notice in a linear history (Appendix Case 1). Comparing raw strings misses such matches, and asking an LLM to compare every pair adds cost and uncertainty. We therefore use tool contracts to declare the identity semantics of each tool, which makes equivalence checks deterministic and reproducible. The contract of a tool ff is

Cf=(εf,df,Kf,nf,gf),\mathcal C_{f}=(\varepsilon_{f}, d_{f}, K_{f}, n_{f}, g_{f}),

where εf∈{read,write}\varepsilon_{f}\in\lbrace\text{read}, \text{write}\rbrace is the effect type, dfd_f marks whether a read is deterministic, KfK_f lists the identity-relevant argument fields, and nfn_f and gfg_f normalize the arguments and the result. For an artifact vv produced by call cc, the identity key combines the relevant arguments and the returned content:

κ(v)=canon(nf(args(c),Kf), gf(result(c))),\kappa(v)=\mathrm{canon}\big(n_{f}(\mathrm{args}(c), K_{f}),\ g_{f}(\mathrm{result}(c))\big),

where canon(⋅)\mathrm{canon}(\cdot) serializes them into canonical JSON. Artifacts with the same identity key are linked by an equivalent_to edge.

KfK_f keeps only the arguments that determine the identity of a result. For retrieval tools, it is the normalized search target rather than the exact query wording, so differently phrased queries that target the same entity and return the same results are treated as equivalent. For resource-specific reads, it is the resource ID, so identical content from different resources is not merged. Equivalence detection applies only to deterministic reads. Each successful write creates a new state version linked to the previous one by a supersedes edge, so a necessary state change is never skipped as a duplicate. Contracts are also cheap to write. Retrieval tools only need to be declared as deterministic reads with their identity-relevant fields, and the read/write types of AppWorld APIs follow directly from HTTP methods.

BenchmarkToolEffectDeterministicIdentity key κ\kappa
BrowseComp-Plussearchread✓Normalized search target + retrieved documents
BrowseComp-Plusfetchread✓Document ID + normalized content
FanOutQA/FRAMESwiki_searchread✓Normalized search target + retrieved pages
FanOutQA/FRAMESwiki_contentread✓Page title + normalized content
AppWorldGET APIsread✓Resource ID + normalized response
AppWorldPOST/PUT/PATCH/DELETE APIswrite✗N/A (creates a new state version)
Reviewer_Ln7DOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes GraphPTC, a framework that augments programmatic tool calling with a dynamic execution graph. The graph represents tool calls, artifacts, state versions, failures and declared intents and links dependencies across program blocks. Bounded graph-derived feedback helps the agent continue execution, patch failures, replan, or answer. Across seven benchmark settings and five backbones, the reported results consistently exceed both direct tool calling and standard PTC, with average improvements of 6.8 and 6.3 percentage points respectively.

Critical strengths
  1. The paper identifies implicit execution effects and cross-block dependencies as a motivating limitation of linear execution histories.

  2. The paper introduces GraphPTC, which organizes tool effects, artifacts, state versions and failures in a dynamic execution graph. Such method of linking declared intents to execution evidence and providing bounded feedback offers a coherent framework for progress assessment, targeted repair and replanning.

  3. Evaluation results illustrate that GraphPTC has higher scores than both baselines, while using fewer input tokens than direct tool calling in the reported efficiency evaluations.

Critical weaknesses
  1. The contribution of graph structure is not strictly ablated. The ablation in Table 2 removes the graph together with its feedback and recovery mechanisms, which is effectively equivalent to reducing the model to a baseline comparable to PTC. GraphPTC also exposes structured execution information like effects and localized failures which are not presented in the baseline. Therefore, it is unclear to distinguish the extent to which "graph-based dependency modeling" actually contributes to the results, as opposed to the performance gains stemming primarily from other, richer sources of information.

  2. Evaluation settings are insufficiently set. Some improvements are very small, such as 81.55 versus 81.43 on FRAMES with DeepSeek and 51.49 versus 51.34 on Agent-Diff with GPT. These are numerical improvements, but their reliability cannot be assessed from the reported results. More configuration details would also help interpret and reproduce the comparisons.

Questions for authors

For the rebuttal, I encourage the authors to further clarify these points mentioned in the weakness. I am open to revisiting my score if these concerns are adequately addressed.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Ln7D(1/3)

Thanks for your careful and valuable comments, and we will refine the paper following your suggestions. Below we respond to your questions in detail.

Q1: How to distinguish the contribution of graph-based dependency modeling from that of richer structured execution information.

A1: Thanks for this key question, which goes to the core of our work. We would first like to clarify that GraphPTC is not PTC plus a graph and some feedback, but a complete execution mechanism built around an execution graph. We then add controlled comparisons with PTC variants and component-level ablations, which show that the gain mainly comes from graph-based dependency modeling and all components work together as a whole.

1. GraphPTC is a complete execution mechanism built around an execution graph

In PTC, execution across blocks is kept as a linear history of code, outputs, and errors. The model has to work out from this text how the blocks relate to each other. GraphPTC turns each round into a closed loop. The agent first declares an intent and its target node. After execution, the runtime trace is added to a typed execution graph and linked to earlier blocks. The system then checks progress on the graph and returns bounded feedback, together with the actions the agent can take next (CONTINUE, PATCH, REPLAN, or ANSWER).

Every other mechanism in this loop is built on the execution graph. To detect equivalent results, we need artifact identities across blocks. To assess progress, we need to check for repeated results and locate stalled targets. To repair a failure, we need to find the exact call that failed and reuse the results that already succeeded. None of these can work without the graph. So GraphPTC does not simply add generic feedback rules to PTC. Its novelty is an execution graph that connects declared intents with execution results, so that the agent can decide its next action based on actual progress.

2. PTC variants: the gain mainly comes from dependency modeling

To answer your question directly, we build several PTC variants that receive the same intra-block structured information as GraphPTC but no cross-block dependencies. If richer information were the main driver, these variants should come close to GraphPTC. Otherwise, a clear gap should remain. All variants use the same feedback budget and MiMo-V2.5 as the backbone:

  • + Structured Summary: appends a structured summary after each block (calls, read/write effects, success flags, and failures) without cross-block relations.
  • + Failure Tracking & Recovery Hint: further adds explicit failure tracking and generic recovery hints.
  • Linearized GraphPTC: keeps the full graph feedback but rewrites it as a plain-text trajectory.
MethodBrowseComp-PlusAppWorld-NAppWorld-CAvgInput Tokens
PTC30.184.580.264.91.00×
+ Structured Summary31.685.881.366.21.17×
+ Failure Tracking & Recovery Hint32.487.282.667.41.21×
Linearized GraphPTC40.391.486.172.61.30×
GraphPTC42.292.987.674.21.24×

The two summary variants improve PTC by only 2.5% in total, about 1/4 of the total gain of GraphPTC (9.3%). The + Failure Tracking & Recovery Hint variant has exactly the same intra-block information as GraphPTC and differs only in cross-block dependencies, yet it still falls behind by 6.8%. On BrowseComp-Plus, which requires combining evidence across many retrieval rounds, the gap reaches 9.8%. Moreover, Linearized GraphPTC keeps most of the gain, while the summary variants perform clearly worse at a similar token cost. The improvement thus comes neither from the feedback format nor from more context. These results show that the gain of GraphPTC mainly comes from graph-based dependency modeling rather than richer execution information.

AuthorsOpenReview ↗

Response to Reviewer Ln7D(2/3)

A1 (continued)

3. Component ablations: the graph mechanism works as a coordinated whole

Inspired by your suggestion, beyond verifying the overall contribution of dependency modeling, we further ablate the five components inside the graph mechanism one at a time. They address the three layers of limitations identified in Sec. 1:

  • Cross-Block Dependency (representation layer): lets each block directly find the earlier artifacts it relies on.
  • State Versioning (representation layer): separates old and new state versions so that later operations do not read stale values.
  • Equivalence Detection (analysis layer): recognizes differently phrased retrievals that return equivalent results.
  • Progress Assessment (analysis layer): detects stagnation without new effects and prompts replanning.
  • Recovery Guidance (decision layer): locates each failure at a specific node and repairs only the failed calls.

Each variant removes only the relations or mechanism of one component, while the other components still run on the execution graph.

MethodBrowseComp-PlusAppWorld-NAppWorld-CAvg
GraphPTC42.292.987.674.2
w/o Cross-Block Dependency38.689.584.770.9
w/o State Versioning42.290.284.172.2
w/o Equivalence Detection36.492.086.871.7
w/o Progress Assessment37.591.085.371.3
w/o Recovery Guidance40.689.684.271.5

Removing any single component lowers the average performance by 2.0% to 3.3%, and the drops concentrate on the tasks each component is designed for. Without equivalence detection, BrowseComp-Plus drops by 5.8%. Without state versioning or recovery guidance, the loss mainly appears on AppWorld, which requires persistent writes, while state versioning has no effect on the read-only BrowseComp-Plus. More importantly, the drops from removing each component add up to 13.4%, exceeding the total gain of the graph mechanism over PTC (9.3%). The components depend on each other: equivalence detection decides whether progress assessment is reliable, and dependency edges let PATCH reuse the results that already succeeded. This shows that the components of GraphPTC work as a coordinated whole and together account for its effectiveness.

Thanks again for your suggestion. We will add the method clarification and both experiments to the revision.

AuthorsOpenReview ↗

Response to Reviewer Ln7D(3/3)

Q2: About the reliability of small improvements on some combinations, and more configuration details.

A2: Thanks for your careful review. Our conclusion does not rest on any single combination such as FRAMES/DeepSeek (81.55 vs. 81.43), but on consistent improvements across 7 settings and 5 backbones. We therefore add statistical tests and provide the full configuration.

1. Statistical tests: the overall improvement is significant and stable

Using the existing per-instance results, we pool the 5 backbones for each setting and report 95% confidence intervals from paired bootstrap (10,000 resamples) along with p-values from McNemar's test:

SettingGraphPTC vs. PTCp-valueGraphPTC vs. Directp-value
BrowseComp-Plus+11.7 [10.6, 12.8]<0.001+6.0 [4.9, 7.1]<0.001
AppWorld-N+8.3 [6.0, 10.6]<0.001+9.8 [7.3, 12.3]<0.001
AppWorld-C+4.7 [3.4, 6.1]<0.001+19.1 [17.3, 20.8]<0.001
Agent-Diff+5.4 [3.1, 7.6]<0.001+3.0 [0.9, 5.2]0.006
FanOutQA+8.5 [6.2, 10.9]<0.001+2.5 [0.4, 4.7]0.021
FRAMES+1.9 [1.0, 2.9]<0.001+1.6 [0.6, 2.5]0.002
AutomationBench+3.9 [1.2, 6.6]0.004+5.7 [2.9, 8.4]<0.001
Overall+6.3 [5.8, 6.9]<0.001+6.8 [6.2, 7.4]<0.001

GraphPTC improves over both baselines significantly on all 7 settings (p<0.05), including FRAMES. Across the 35 benchmark-backbone combinations, GraphPTC never falls below either baseline. We also rerun the combinations with the smallest gaps 3 times, and every standard deviation stays within 0.6%. These results confirm that the improvement of GraphPTC is reliable rather than random fluctuation.

2. Configuration details

The main settings are listed below, and the full setup will be added to the appendix. The interaction budget is set per benchmark and shared by all three methods. The parameters specific to GraphPTC are fixed across all settings and backbones with no per-benchmark tuning.

ConfigurationValue
Max interaction roundsPer benchmark (same for all methods)
Program output limit8,000 characters
Graph feedback budget BB3,200 characters
Stagnation threshold2 rounds
Decoding temperature0.0
Max completion tokens per round4,096

Thanks again for your suggestion. We will add confidence intervals and significance tests to the main results and include the full configuration in the appendix.

Thanks again for your careful and valuable comments, and we hope our responses address your concerns. If our responses answer your questions well and resolve your concerns, we would appreciate it if you could reassess our work and raise your rating.

Comments on the paper

1 comment

Dear Reviewers,

The authors have posted their responses to the reviews. Please go through their rebuttal at your earliest convenience, and engage in a discussion or leave any follow-up comments.

The discussion period ends on November 18.

Thanks,

Area Chair

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.