- 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
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:
| Method | BrowseComp-Plus | AppWorld-N | AppWorld-C | Avg | Δ Avg |
|---|---|---|---|---|---|
| GraphPTC | 42.2 | 92.9 | 87.6 | 74.2 | – |
| w/o Cross-Block Dependency | 38.6 | 89.5 | 84.7 | 70.9 | −3.3 |
| w/o State Versioning | 42.2 | 90.2 | 84.1 | 72.2 | −2.0 |
| w/o Equivalence Detection | 36.4 | 92.0 | 86.8 | 71.7 | −2.5 |
| w/o Progress Assessment | 37.5 | 91.0 | 85.3 | 71.3 | −2.9 |
| w/o Recovery Guidance | 40.6 | 89.6 | 84.2 | 71.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/reusesedges 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.
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
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 Signal | BrowseComp-Plus | Extra LLM Calls |
|---|---|---|
| w/o Progress Assessment | 37.5 | 0 |
| No-error execution | 37.9 | 0 |
| LLM-judged intent realization | 42.8 | +1 per round |
| (Ours) | 42.2 | 0 |
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 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:
| Indicator | Precision |
|---|---|
equivalent_to edge | 98.1% |
| (no progress) | 96.2% |
| Stagnation-triggered REPLAN prompt | 93.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 , 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.
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:
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:
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.