- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the problem of missing implicit prerequisites in multi-tool planning. The authors distinguish within-goal dependencies from cross-goal adjacencies and analyze how frozen planners struggle with tools that are not explicitly mentioned in the request. Through a systematic analysis of existing planners, the paper shows that within-goal dependencies are substantially more difficult to recover.
To address this problem, the authors propose PITON, a plan-repair framework that uses tools in an initial draft as anchors to retrieve candidate additions from a tool graph. PITON employs two lightweight gradient-boosted rerankers to iteratively insert missing tools and delete unsupported selections while keeping the base planner frozen.
The authors evaluate PITON on UltraTool, ShortcutsBench, and MCP-Atlas using diffusion, autoregressive, and closed-source planners. The results show consistent improvements in planning metrics across multiple planners, supported by component ablations, experiments without gold training trajectories, and downstream execution evaluations.
Critical strengths
S1: Solid problem analysis and well-motivated problem formulation.
The paper provides a systematic analysis of a failure mode in multi-tool planning. The discussion is detailed and supported by empirical evidence, offering a clear motivation for the proposed PITON framework.
S2: Lightweight, modular, and model-agnostic framework.
PITON provides a lightweight and modular approach to plan refinement without fine-tuning the underlying planner. Its compatibility with diffusion, autoregressive, and closed-source models demonstrates its flexibility and broad applicability.
S3: Rich empirical evaluation with targeted analyses.
The paper presents a rich set of experiments across multiple benchmarks and diverse planning models. The evaluation also includes ablation studies, targeted analyses, and downstream execution experiments, providing useful evidence for the effectiveness of the proposed framework.
Critical weaknesses
W1: The practical significance of the targeted problem is not fully established.
The paper demonstrates that implicit dependencies are frequently missed, but does not directly quantify how much these omissions contribute to end-to-end task failures. Although downstream execution experiments show benefits from PITON, these benefits reflect both insertion and deletion and are measured only on queries where reference plans help and repair is activated. The results therefore provide limited evidence of the impact of the targeted failure mode and the average benefit of addressing it across the broader task distribution.
W2: The effectiveness of the key methodological innovations is not fully validated.
The paper shows that PITON improves planning performance and recovers missing dependencies, but does not sufficiently isolate the benefits of its core design choices over simpler alternatives. The ablation studies mainly examine insertion, deletion, and their combination, without directly validating draft-anchored backward dependency inference or query-conditioned reranking. Since these choices are central to addressing the identified limitations of existing graph-based methods, the lack of controlled comparisons weakens the empirical support for the paper's main methodological contribution.
Questions for authors
Q1: How frequently do missing implicit dependencies lead to downstream task failures? To what extent are the observed execution improvements attributable specifically to recovering missing dependencies, rather than removing incorrect tools?
Q2: What is the average downstream coverage improvement across all executable MCP-Atlas queries, including those where the reference plan does not help or PITON makes no changes?
Q3: Under matched experimental settings, how does PITON compare with simpler alternatives, such as conventional forward graph-based completion or query-agnostic graph-based repair? To what extent do draft-anchored dependency inference and query-conditioned reranking each contribute to the overall performance gains?
Q4: How sensitive is PITON to errors in the estimated corruption rates? Would the improvements remain substantial under fixed, planner-independent synthetic corruption parameters?
4 comments
Response to Reviewer h5KW [Q3 and Q4]
[W2 / Q3 Forward Graph Completion and Query-blind Graph Repair under the Same Setting]
With the same frozen configuration and the same drafts, we change one thing at a time:
-
forward-only (forward graph completion): a candidate can only be inserted after the anchor it is adjacent to in the graph, the same as using the graph in generation order.
-
no query features (query-blind graph repair): both rerankers drop all similarity features between the query and tool descriptions and keep only the graph statistics.
| Gain over the draft (mean of 4 drafters) | UltraTool edge F1 | UltraTool within-edge recall | ShortcutsBench edge F1 | ShortcutsBench within-edge recall | MCP-Atlas edge F1 | MCP-Atlas within-edge recall |
|---|---|---|---|---|---|---|
| PITON | +12.45 | +11.41 | +7.32 | +4.52 | +20.33 | +18.53 |
| forward-only | +9.91 | +2.80 | +2.69 | −0.10 | +8.68 | +5.52 |
| no query features | +8.92 | +6.64 | +7.35 | +4.99 | +17.97 | +16.21 |
Forward-only is below PITON on both edge F1 and within-edge recall in all 12 cells, and on average it loses 76% of the within-edge recall gain and 47% of the edge F1 gain. Without query features, edge F1 drops in 10 of the 12 cells, losing 28% of the gain on UltraTool and 12% on MCP-Atlas. On ShortcutsBench it has almost no effect, because the lexical evidence between this benchmark's queries and tool descriptions is weak: retrieving by the query, the top-3 recall of primary tools is only 66.4%, against 93.4% on UltraTool (Appendix B.4).
In addition, GNN4Plan and ControlLLM-ToG in Table 3 of the paper are complete forward graph planners. GNN4Plan is close to PITON in spirit: both take the tools already chosen as anchors and, by matching the task against tool descriptions, look for the next tool among the anchors' graph neighbours. The main difference is the order. The forward-only ablation above is in effect PITON with its graph-reading direction switched to GNN4Plan's and everything else unchanged. On MCP-Atlas, where more than half of the gold tools are dependency tools, changing only the reading direction brings PITON down to the level of GNN4Plan.
[Q4 Sensitivity to Errors in the Estimated Corruption Rates]
PITON is not sensitive to them. We ran two tests on all 12 cells, keeping the drafts and the rest of the configuration fixed and changing only the corruption parameters of the synthetic corpus:
-
Fixed parameters: every cell uses the same keep 0.6 / extra 0.3 / exact 0.2, and the distractor tools in the deletion corpus are also drawn by a fixed rule.
-
Estimation error: we shift the measured keep and extra by 0.15 each, to simulate estimating the draft as too poor (keep −0.15, extra +0.15) and as too good (keep +0.15, extra −0.15).
| Share of the gain kept | PITON gain over the draft | Fixed parameters | Estimated too poor | Estimated too good |
|---|---|---|---|---|
| UltraTool | +12.45 | 94% | 98% | 92% |
| ShortcutsBench | +7.32 | 78% | 81% | 87% |
| MCP-Atlas | +20.33 | 82% | 96% | 91% |
| Mean of 12 cells | +13.37 | 85% | 94% | 90% |
With fixed parameters, PITON keeps 85% of its gain on average, and every cell stays clearly above the draft; an estimation error of ±0.15 keeps at least 90%. Per-cell calibration is better in 10 of the 12 cells, so calibration helps, but the gain does not come from calibration.
We thank the reviewer again for the suggestions. These new results make our claims more direct: the execution gain comes from restoring the right tools, mostly tools the query does not mention, and the gain depends on reading the graph backwards from the finished draft and on scoring candidates against the query. We hope these responses address your concerns and would appreciate it if you would consider raising your score. We are happy to answer any further questions.
Dear Reviewer h5KW,
Thank you again for your positive assessment of our work. With less than 24 hours left in the discussion period, we wanted to follow up once more in case our responses have not reached you yet.
Following your suggestions, we extended the execution experiment to all 151 executable MCP-Atlas queries (Q2), compared PITON with forward graph completion and query-blind repair (W2/Q3), and tested different corruption rates (Q4). We would value a brief note on whether these answer your questions.
If you feel the new results strengthen the paper, we would be grateful if you could reflect this in your final score and support the paper in the discussion with the AC.
Best regards, The Authors
Thank you for the detailed responses. I appreciate the authors' efforts in addressing my questions. The clarifications and additional experiments have largely addressed my concerns. I see value in this work, and after considering the authors' responses, I will maintain my original rating of 3 (Weak Accept).
Response to Reviewer h5KW [Q1 and Q2]
We thank reviewer h5KW for recognising our problem analysis, the light and modular design of the method, and the breadth of the experiments. We answer each point below. New results have been added to the revision (in blue).
[W1 / Q1 Missed Implicit Dependencies and the Source of the Execution Gain]
Repair in the execution experiment only inserts and never deletes: arm C adds the tool chosen by the dependency reranker to the draft and removes nothing (in each of the 173 cells it inserts exactly one tool). We made this choice because in an early small-scale pilot, the only clear loss after repair came from a deletion. The deleted tool was not in the reference plan, so by plan matching the deletion was correct, but the agent relied on exactly that tool to search the map by category and find the right place. The main reason is that the MCP-Atlas reference plan comes from one human-verified successful trajectory provided by the benchmark. It is only one legal way to complete the task and does not necessarily match how an agent works. When the agent actually executes, it often needs exploration tools that the reference trajectory does not contain (for example, search or listing) to locate its target. Deleting a tool outside the reference plan can remove exactly that step. The +5.79 execution gain therefore comes entirely from insertion. We have added this explanation to Appendix J and changed the description of arm C to "the draft with the dependency reranker's insertion". We thank the reviewer for helping us find this issue.
The gain comes from inserting the right tool. We split the cells by whether the inserted tool belongs to the gold plan:
Cells where a gold tool is inserted improve significantly. Cells where a wrong tool is inserted do not improve significantly, and on average they do not get worse either (+1.93, with an interval that includes 0).
Missing implicit dependencies is common. Among the cells where repair fires, 82.7% of the drafts miss at least one gold tool that the query does not mention, and on these cells replacing the draft with the reference plan raises coverage by +9.80. Of the 113 correct insertions, 79 (70%) are tools the query does not mention. The execution gain therefore comes mainly from restoring missed tools, most of which are dependencies the query does not mention.
[Q2 Average Gain over All Executable MCP-Atlas Queries]
The original execution experiment first kept the queries where a reference plan helps (D−A > 0, 64 queries). Following the reviewer's request, we have now run the other 87 queries, where the reference plan does not help, so the result covers all 151 executable queries. We kept the original setup: the same drafts and repair, three runs per arm with the median taken, and the same blind grading and exclusion rules.
Surprisingly, on the queries where the reference plan does not help (D−A ≤ 0), PITON's repair still helps, by about half of the +5.79 on the 64 queries, and five of the seven drafters are positive. We think the reason may be the one analysed in Q1: the reference plan provided by the benchmark lacks some exploration tools that the agent needs in actual execution, so injecting it does not necessarily help, while PITON adds the hidden dependencies to the drafter's own draft and therefore helps the agent complete the task.
When repair does not fire, arms B and C inject byte-identical prompts, so the effect is zero by construction; the null control in Appendix J confirms this. Of all 151 queries × 7 drafters = 1,057 pairs, PITON fires on 476 (45.0%). Therefore, the improvement across all executable MCP-Atlas queries, including those where the reference plan does not help or PITON makes no changes, is +1.82 [+0.82, +2.91]. We have added these numbers to Section 5.5 and Appendix J.