acceptodds
Under review as a conference paper at ICLR 2027

PITON: Anchored Dependency Repair for Multi-Tool Planning

Abstract

Tool-planning models expand a natural-language request into an ordered sequence of structured tool calls. Correct plans often require tools the request never mentions. Prior work supplies this knowledge with a dependency graph built from gold plans, joining any two tools called one immediately after the other. Treating every such adjacent pair as the same dependency conflates two situations: (1) within-goal dependency: two adjacent tools may serve one requested goal from the query, one tool being an unnamed prerequisite of the other; (2) cross-goal adjacency: two adjacent tools simply serve two different goals, requested back to back. The graph alone therefore cannot tell whether an observed adjacency represents a dependency needed by the current query or merely connects two consecutive goals. This distinction matters because frozen planners fail disproportionately on the former: on UltraTool, they recall 64.6% of cross-goal adjacencies but only 23.7% of within-goal dependencies, where the unnamed prerequisite is often missing. Motivated by this gap, we propose PITON, a model-agnostic repair framework for dependency-aware plan refinement. PITON anchors on a planner's draft, using the tools already selected as clues to missing prerequisites. It alternates an insertion reranker that recovers missing dependencies from the anchors' one-hop graph neighbourhood with a symmetric deletion reranker, until the plan stabilises. PITON is especially natural for masked diffusion models. They progressively commit confident tools and refine the remaining plan. We evaluate ten diffusion, autoregressive and closed-source planners on UltraTool, ShortcutsBench and MCP-Atlas, and show PITON raises edge F1 in all eighteen settings. The gain over the unrepaired draft reaches +26.0, +10.1 and +24.3 points on the three benchmarks. PITON requires only lightweight rerankers while keeping the base planner frozen, introducing minimal additional training overhead. Code is available at https://anonymous.4open.science/r/anchor-anon-6006.

Primary area:
foundation or frontier models, including LLMs
Keywords:
tool-planning, large language model agents, tool dependency graph, diffusion language models, reranking

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_h5KWOpenReview ↗
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
AuthorsOpenReview ↗

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:

Inserted toolCellsC−B [95% CI]
Gold tool113+7.84 [+2.49, +13.40]
of which not mentioned in the query79+6.52 [+0.50, +13.19]
Non-gold tool60+1.93 [−4.77, +6.94]

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.

Drafter87 queries, firing cells: C−B [95% CI]All 151 queries, non-firing = 0 [95% CI]
Devstral+8.60 [+1.24, +17.00]+3.59 [+0.45, +7.07]
Mistral+5.16 [−2.56, +13.58]+2.84 [+0.03, +5.82]
GLM+4.10 [+0.58, +8.42]+2.76 [+0.92, +4.97]
Nemotron+3.66 [−5.59, +12.80]+1.55 [−2.05, +5.41]
DeepSeek+0.16 [−5.19, +5.90]+1.04 [−1.71, +3.95]
Kimi−0.74 [−2.50, +0.00]+0.13 [−0.72, +1.34]
gpt-oss−4.00 [−13.33, +3.47]+0.59 [−1.98, +3.06]
All+2.83 [+0.38, +5.25]+1.82 [+0.82, +2.91]

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.

AuthorsOpenReview ↗

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 F1UltraTool within-edge recallShortcutsBench edge F1ShortcutsBench within-edge recallMCP-Atlas edge F1MCP-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 keptPITON gain over the draftFixed parametersEstimated too poorEstimated too good
UltraTool+12.4594%98%92%
ShortcutsBench+7.3278%81%87%
MCP-Atlas+20.3382%96%91%
Mean of 12 cells+13.3785%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).

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

Summary: This paper analyzes why tool-planning models fail on complex user requests. The authors distinguish between two types of tool relationships 1) Cross-Goal Adjacency: Executing separate tasks sequentially where Current planners perform well here. and 2) Within-Goal Dependency: Executing a single task that implicitly requires prerequisite steps (e.g., modifying a hotel reservation, which requires first retrieving the reservation). Current planners frequently fail here because they omit the unstated prerequisite tools. To address this, the authors develop PITON, a model-agnostic repair framework that post-processes the draft plans of any frozen planner to identify and insert missing dependency tools.

Key Contributions:

  1. The authors quantify the performance gap between cross-goal and within-goal tool composition, establishing that within-goal dependency omission is a primary source of planner failure.
  2. PITON treats the correctly identified tools in a draft plan as "anchors." It then utilizes a tool dependency graph to trace backward from these anchors and infer which prerequisite tools were omitted. 3.The framework employs a two-stage reranking process: a deletion reranker to remove redundant or unsupported tools, and an insertion reranker to add missing prerequisites. This loop repeats until the plan stabilizes.
  3. PITON is implemented as an external, lightweight layer that operates on top of any existing planner without requiring model retraining.

Evals: The framework was evaluated by applying it to ten different planning models across three benchmarks (UltraTool, ShortcutsBench, and MCP-Atlas).

  1. PITON improved planning metrics across all 18 tested configurations, specifically correcting missing dependencies and within-goal edges
  2. In execution tests, the plans repaired by PITON led to higher task completion rates when deployed in active agent environments
Critical strengths
  1. The paper clearly identifies and isolates a specific failure mode in LLM planners: the contrast between "cross-goal adjacency" (which models handle well) and "within-goal dependency" (where models fail to infer unstated prerequisite steps).
  2. Because PITON acts as an external post-processing layer, it can patch the outputs of any existing, frozen planner. This design avoids the high computational cost of retraining or fine-tuning the underlying models.
  3. Using correctly predicted tools as "anchors" to trace backward through a dependency graph provides a structured, logical mechanism to infer missing prerequisites.
  4. The authors validated the framework across ten distinct planning models and three different benchmarks (UltraTool, ShortcutsBench, and MCP-Atlas), demonstrating the generalizability of the repair mechanism.
  5. The paper evaluates both static plan metrics and active downstream execution, showing that repaired plans lead to higher final task success rates in dynamic agent environments.
Critical weaknesses
  1. The framework assumes access to a complete and accurate tool dependency graph. In real-world enterprise applications where APIs change, are updated, or lack clear documentation, constructing and maintaining this graph is a major bottleneck.
  2. The iterative refinement loop (alternating between deletion and insertion rerankers until the plan stabilizes) introduces multiple sequential model calls. This iterative process increases inference latency, which can impact real-time agent deployments.
  3. The repair mechanism depends on the planner getting at least some "anchor" tools correct in the initial draft. If the primary planner fails completely on a highly complex query and generates zero correct anchor tools, PITON has no starting point to reconstruct the path.
  4. Lack of Algorithmic novelty: The core pipeline of generating a draft, ranking, and inserting missing components relies heavily on established sequence-refinement and correction techniques used in grammar spelling correction and program repair.
  5. While tested across many models, the evaluation focuses on existing benchmarks with structured APIs. The paper does not explore how PITON scales to open-ended web environments where the "tool catalog" consists of millions of unmapped endpoints.
Questions for authors
  1. How does PITON handle scenarios where the primary planner fails to generate any correct "anchor" tools in its initial draft, leaving the framework with no starting points to trace the dependency graph?
  2. Since the iterative loop of alternating between deletion and insertion rerankers requires multiple sequential model calls, what is the exact computational and latency overhead introduced by PITON, and how does this affect its feasibility for real-time, low-latency agent deployments?
  3. The framework assumes the existence of a complete and static tool dependency graph. How does PITON handle dynamic environments where APIs are frequently updated, deprecated, or added without manual graph maintenance?
  4. Have you explored training the planner itself on the dependency graph transitions directly (e.g., via supervised fine-tuning or reinforcement learning) to prevent the initial omission of within-goal prerequisites, rather than relying on a separate post-hoc repair layer?
8 comments
AuthorsOpenReview ↗

Responses to Reviewer nuhS [Q1, Q2 and Q3]

We thank reviewer nuhs for the careful summary and for the questions, which touch on exactly the deployment issues we care about. We answer the four questions first and then the remaining weaknesses.

[Q1 Draft Without a Correct Anchor]

It is true that PITON does not fix it, but the case where the planner cannot name even one tool the request asks for directly is rare. We counted it in the twelve open-weight cells of Table 3: a draft shares no tool with the gold plan for 5.7% of query-cell pairs (203 of 3,568). We thank the reviewer for raising this practical concern, and we will add this count to Appendix H.

[Q2 Computational and Latency Overhead]

[CPU-only repair loop] One iteration of PITON runs quickly on a CPU and contains no LLM call in its default form. On an 8-core Apple M2 CPU, the full loop over the 489 UltraTool test queries on average takes under 50 ms per query. Each query is also embedded once by a small sentence encoder (MiniLM). We will add the inference figures to Appendix F.

[Optional model call] The one variant that does call the model is the model-executed insertion for diffusion drafters (Section 4.2), which adds one short masked-decoding pass per round. That step is optional. Without it, the loop keeps all but 0.51 edge F1 of the gain on average (Appendix E.4). A deployment that cannot afford extra model calls can therefore run PITON on the CPU alone and get most of the gain.

[Q3 Dynamic Environments: APIs Added, Updated or Deprecated]

[No manual graph maintenance] The graph is never edited by hand. It is a table of adjacency counts over the logged trajectories (Section 4.1), and neither reranker has a tool-identity feature (Appendix D.3). When an API is added, updated or deprecated, the deployment keeps logging trajectories as it does anyway, and PITON recounts the graph and retrains both rerankers from the log in under two minutes on a CPU.

[Simulating the three changes] We simulated each change on UltraTool, keeping the drafts of the four open-weight drafters from Table 3 and the configuration of the main results; only the log changes. For an added tool, we took the ten tools that the full graph adds back to drafts most often, one at a time, deleted every training trajectory that contains the tool, and returned 25% of them; since the deployment knows the tool is new, the stale graph does not delete it. For an updated tool, we use the same ten tools except account_login itself, again one at a time. After the update, the tool requires the existing tool account_login right before it; for example, hotel_booking_query now needs a login first. The trajectories logged before the update no longer show how to call the tool, so all of them are dropped, 25% come back in the new form, and the test plans are rewritten the same way. For a deprecated tool, UltraTool has none, so we built the world before a deprecation: three tools that used to be required steps (flight_seat_hold before book_flight, file_backup before file_modify, alarm_sync_device after clock_alarm_set) are inserted into every training trajectory of their partner tool. Deprecating them returns UltraTool as released, so the refitted graph is the one in our main results. In each case we compare the graph fitted before the change (stale) with the graph refitted on the log after the change.

Table S1 Adding, updating and deprecating tools on UltraTool, pooled over the four open-weight drafters. Edge F1 is on the affected queries, whose gold plan contains the changed tool (for deprecation, its partner tool).

changemeasuredraft, no repairstale graphgraph refitted on the new log
added (25% of its trajectories logged)edge F136.035.548.2
updated (25% of its trajectories in the new form)edge F117.626.155.9
deprecated (three tools)edge F159.319.672.8

[Results] In all three changes, refitting on a small portion of new log is enough, and no manual graph maintenance is needed. The stale graph cannot follow a change. It never inserts the new tool or the new dependency, and after a deprecation it keeps calling the removed tools, which puts it 40 points below the unrepaired draft. After the refit, edge F1 on the affected queries is 12.7, 29.8 and 53.2 points above the stale graph for the added, updated and deprecated tools, and above the unrepaired draft in all three. Edge F1 on the other queries does not drop in any case. PITON therefore follows all three changes from the log alone, and for an added or updated tool a quarter of the new trajectories is enough.

AuthorsOpenReview ↗

Responses to Reviewer nuhS [Q4 and W1]

[Q4 Training the Planner on Graph Transitions]

[Supervised fine-tuning] We did, and it is shown in the paper as the training intervention of Section 3 (Insight 3, Appendix B.5). We fine-tune Qwen3-8B on UltraTool trajectories with and without exposure to 30 held-out tool pairs. With exposure the model recalls a within-goal dependency 70.5% of the time; with the pair erased from training, 20.8%, barely above the untrained 18.3%.

We additionally compared the two directly on UltraTool. The fine-tuned planner is Dream-7B-Instruct, trained with LoRA for 600 steps (about four epochs) on the same 2,339 training trajectories that PITON is fitted on.

Table S4 UltraTool (489 test queries), Dream-7B-Instruct.

MethodNeeds model weightsTrainingedge F1node F1EM
Draftnonone54.2878.9143.97
PITONno1.8 min on a CPU62.1882.3455.42
Fine-tuningyes71 min on one 48 GB GPU67.9186.2254.81
Fine-tuning + PITONyes71 min on a GPU + 1.9 min on a CPU70.6487.9261.96

We agree that fine-tuning is stronger when the planner can be trained: it is 5.7 edge F1 above PITON (95% CI [+2.0, +9.6]), although the two reach the same exact match (55.4 vs 54.8). PITON gets most of the way in under two minutes on a CPU, without access to the model weights. The two can also be combined: added on top of the fine-tuned planner, PITON raises edge F1 by a further 2.7 ([+0.7, +5.0]) and exact match by 7.2. Fine-tuning and PITON therefore serve different settings. Fine-tuning needs open weights and a GPU, and has to be repeated for every planner and every tool catalogue. PITON does not train the planner and is plug-and-play, so it also applies to closed-source planners and to catalogues that change. We will revise the paper to present PITON this way, as a lightweight layer for the general setting rather than as an alternative to fine-tuning.

[Reinforcement learning] We also ran GRPO with Qwen3-8B on UltraTool. We first fine-tune the model with eight frequent tool pairs erased, and then train it with GRPO on the 914 training queries that contain these pairs. GRPO never sees their plans as demonstrations; it only receives a reward, the node and edge F1 of each sampled plan against the gold plan. Recall of the erased dependencies was 54.4% before RL, against 88.6% when the pairs are kept in fine-tuning. GRPO reached only 54.8%. We think RL does not recover the dependency because it can only reinforce what the model already samples: for the largest gap, search_train before train_ticket_booking, the prerequisite appeared in only 5% of the model's samples before RL. The missing dependency is knowledge the model does not have, and an outcome reward cannot supply it.

[W1 Assumption of a Complete and Accurate Graph]

PITON assumes neither. The graph is counted from trajectories and needs no manual maintenance (Q3). Section 3 shows that the graph is ambiguous by construction: it records cross-goal adjacencies and within-goal dependencies as the same edge. That is why PITON scores every candidate against the query instead of trusting the graph (Insight 4). PITON is also robust to imperfect trajectories. In Section 5.4 we remove the gold trajectories altogether, and PITON learns the graph and both rerankers from LLM-written plans for the unlabelled training queries, taken either from a vote of four drafters (T2) or from a stronger teacher model (T3). These plans are not gold and contain errors, yet with T3, PITON still raises edge F1 on MCP-Atlas by 8.5 to 13.7 points for all four drafters (Table 4).

AuthorsOpenReview ↗

Responses to Reviewer nuhS [W4 and W5]

[W4 Algorithmic Novelty]

We respectfully disagree with the reviewer that we only combine standard operators. We do not claim the operators as new; the novelty is when PITON uses the graph, and this design follows from a finding that existing graph-based methods do not account for: a prerequisite usually comes before the tool that reveals it. Yet all existing graph-based planners that target tool dependencies read the graph during generation (Appendix A). They pick each next tool from the graph neighbours of the previous one, so when a prerequisite is needed, the primary tool that reveals it is usually not yet written and the graph cannot lead to it. We call this the information-timing mismatch (Section 1), and PITON is designed to remove it. The model finishes the draft first, and PITON then reads the graph from the draft to add the missing prerequisites.

[Comparison with GNN4Plan] Among all previous methods, GNN4Plan is conceptually the closest to PITON: both take the tools already chosen as anchors and pick the next tool among their graph neighbours by matching the query against tool descriptions. The main difference is the order, so PITON stays simple, yet it is both effective and efficient. With the same LLM, it is 6.0 to 21.1 edge F1 above GNN4Plan (Table 3). It fits on a CPU in under two minutes and repairs a query in under 50 ms, while GNN4Plan is trained on a GPU. We added the ablation below to verify that the gain comes from the order.

[Ablation: changing only the order] Forward-only changes only the order in which the graph is read. As in forward graph completion, a candidate can only be inserted after the drafted tool it neighbours. The drafts, the deletion step and everything else are unchanged.

Table S2 Change from PITON, averaged over the four open-weight drafters, with insertions executed by the reranker for all four (Appendix E.4). ShortcutsBench and MCP-Atlas are one run on the first set of drafts, within 1.1 points of the three-run means. Each cell is edge F1 / within-edge recall.

UltraToolShortcutsBenchMCP-Atlas
PITON, gain over the draft+12.45 / +11.41+7.32 / +4.52+20.33 / +18.53
forward-only−2.54 / −8.61−4.63 / −4.62−11.65 / −13.01

Forward-only is below PITON in all 12 cells, and the losses are large. On within-edge recall, which counts exactly the within-goal edges our finding is about, it loses 75%, all and 70% of PITON's gain on the three benchmarks; on edge F1, it loses 20%, 63% and 57%.

[W5 Open-ended Environments with Very Large Catalogues]

We thank the reviewer for raising this. "Unmapped" is not itself a problem for PITON, because its graph is not annotated by hand but counted from trajectories, which a deployment logs anyway. For a setting with many more APIs, we ran the experiment below.

[Setup] We use StableToolBench (Guo et al., 2024). Its catalogue has 13,247 APIs, about 50 times UltraTool's. To our knowledge, it is the public benchmark closest to the setting the reviewer describes, with one of the largest catalogues. The planner sees only the top 50 APIs returned by a MiniLM retriever that is not fine-tuned. This is the standard practice for large catalogues (Qin et al., 2024; Patil et al., 2023; Du et al., 2024), because the detailed descriptions of more than ten thousand APIs cannot fit into a prompt. No parameter is tuned for ToolBench. Test queries come from G1/G2/G3-instruction. The gold plan follows the GPT-4 trajectory released with StableToolBench.

Table S3 StableToolBench (330 test queries), k = 50. Δ is the change from repair; brackets give the 95% CI (query-paired bootstrap).

PlannerMetricDraftPITONΔ [95% CI]
Dream-7B-Instructnode F146.6949.06+2.38 [+1.27, +3.53]
edge F118.6822.48+3.80 [+1.89, +5.95]
Qwen2.5-7B-Instructnode F141.6044.18+2.58 [+0.61, +4.45]
edge F115.5718.42+2.85 [+0.14, +5.29]

Both drafters improve significantly on both metrics, though by less than in the main table, likely because of how ToolBench is built. It first samples a set of APIs and then asks ChatGPT to write a query for them, so the query names almost every gold API and leaves few of the unnamed prerequisites that PITON targets.


We thank the reviewer again for these questions. They led us to test PITON on changing tools, against fine-tuning and on a catalogue of more than ten thousand APIs, and we believe these results strengthen the work. 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.

Reviewer_pg2nOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper provides several interesting insights on two kinds of dependencies, i.e., within-goal and cross-goal ones. Specifically, it finds that tools in within-goal dependencies may not be explicitly recalled in the query. Thus, based on an initial draft, it proposes a lightweight model to delete irrelevant tools, and add the correct ones based on the anchor. Experiments demonstrate that it generally can outperform other models with much lower training costs.

Critical strengths
  • This paper introduces interesting observations on within-goal and cross-goal dependencies, and draws convincing insights.
  • The proposed method is easy to implement with low training costs.
  • Even with low cost, the experimental results are promising.
  • Code is provided.
Critical weaknesses
  • The paper is not easy to follow. Figure 2 provides a good toy example to understand the algorithm, but it lacks explanation.
  • The connection between the insights and the proposed method should be clarified.
  • Although there are many experiments and interesting insights on within-goal and cross-goal dependencies, the proposed method seems not related to these distinctions. The authors should explicitly map how the design of the insertion/deletion operators targets the within-goal and cross-goal gap, rather than just evaluating the corresponding performance in Section 5.3.
Questions for authors

Please see the weaknesses.

7 comments
AuthorsOpenReview ↗

Responses to Reviewer pg2n [W1 and W2]

We thank the reviewer for finding the insights convincing and the method easy to use. We answer the three weaknesses in turn.

[W1 Explanation of Figure 2]

We thank the reviewer for pointing this out. We have added a step-by-step explanation of the example to the caption of Figure 2, as follows.

The query asks to check a card balance and to "select and handle a deposit product". The gold plan is bank_balance_query → deposit_product_search → fixed_deposit_transaction. Here deposit_product_search is a within-goal prerequisite of the transaction: the query asks to handle a product but never mentions searching for one first. The draft keeps the two primary tools (bbq, fdt) but writes deposit_product_selection where the search should be.

The top-left box shows the dependency graph G around the draft's tools (the anchors). Both rerankers use only this small part of the graph: the deletion reranker looks at the counts between adjacent tools in the draft, and the dependency reranker looks at the one-hop neighbours of the anchors.

The red box at the bottom left shows deletion. In the training plans, dp_sel is adjacent to its two neighbours only 0 and 1 times, while the two neighbours are directly adjacent to each other 8 times, so dp_sel is removed. bbq and fdt remain as anchors.

The blue box on the right shows the dependency reranker, which scores the graph neighbours of the anchors (deposit_product_search and account_login). account_login is the more frequent neighbour (adjacent to bbq 21 times), but it is adjacent to many tools (lift only 4x), and the query never asks to log in (similarity 0.11). deposit_product_search is rarer but specific to fdt (lift 31x), both anchors place it in the same slot, and it matches the underlined clause of the query (0.37). It scores 0.74, above the gate of 0.6, and is inserted before fdt. account_login scores 0.58 and is not inserted.

[W2 Connection Between the Insights and the Method]

We have added the following table to the beginning of Section 4. It maps each insight to the design that addresses it.

Table S1 Each finding of Section 3, the design of PITON that addresses it, and the supporting result.

FindingDesignResult
Dependency tools are missed while primary tools are kept (Insight 1).Keep the draft as anchors and add tools around them.78.4% of the 678 gold tools PITON restores are dependency tools (Section 5.3).
The same edge is recalled less often within a goal than across goals, so the edge alone does not tell whether a plan needs it (Insight 2).Score each candidate in the context of the plan: its lift to the anchors, the slot they place it in, and the query.A primary tool has 6.6 to 26.0 graph neighbours on average, yet 66% to 76% of adopted insertions are gold tools (Section 5.3).
A planner cannot infer an unseen dependency (Insight 3).Take the dependency from an external graph; keep the planner frozen.+8.62 edge F1 on six closed-source planners, without refitting (Appendix G).
A dependency usually precedes the primary tool that reveals it (Insight 4).Read the graph after the draft is finished, so a candidate can be inserted before an anchor.Exceeds GNN4Plan, which reads the graph in generation order, by 6.0 to 21.1 edge F1 with the same LLM (Table 3).
AuthorsOpenReview ↗

Responses to Reviewer pg2n [W3]

[W3 Within-goal and Cross-goal Dependencies in the Method]

[Why PITON does not label edges] PITON does not explicitly label an edge as within-goal or cross-goal, because the goal segmentation is unknown at both training and inference time. The benchmarks provide gold plans but no goal segmentation. The goal and role labels in the paper come from a three-pass LLM annotation (Appendix B.1) and are used only to analyse the results; neither PITON's training nor its inference uses them. Labelling edges explicitly would require running this annotation on the training data and on every new query, which adds cost and makes PITON less practical. Instead, PITON decides for each candidate whether the plan needs it (Table S1, row 2). It scores the candidate in the context of the plan, by its lift to the anchors, the slot they place it in, and its match to the query. A primary tool has 6.6 to 26.0 graph neighbours on average, yet 66% to 76% of the insertions PITON adopts are gold tools (Section 5.3).

[How PITON targets within-goal dependencies] PITON targets within-goal dependencies mainly through when it uses the graph (Table S1, row 4). Existing graph-based methods use the graph during generation: after each tool, they choose the next one from its graph neighbours. However, among within-goal edges that join a dependency tool to a primary tool, the dependency tool comes first in 83% to 93% of cases (Section 3). So when the graph is used in generation order, the primary tool that reveals the prerequisite has not been written yet at the step where the prerequisite is needed. PITON instead lets the model finish the draft first and then reads the graph from the draft to add prerequisites. The draft usually already contains the primary tools (Insight 1), so PITON treats them as anchors and adds within-goal dependencies from their neighbours. A cross-goal edge connects two goals rather than a prerequisite to its primary tool, so PITON does not target it. The results match this expectation. Of the 678 gold tools PITON restores, 78.4% are dependency tools (Table S1, row 1). Across the 12 cells, within-edge recall rises by 11.6 points on average and significantly in 11 cells, while cross-edge recall rises by 3.5 points and significantly in only 3.

[Ablation: changing only the order] To isolate the order, we re-ran PITON with only the graph-reading order changed. Forward-only reads the graph in generation order: a candidate can only be inserted after the drafted tool it neighbours, in training and at inference. The drafts and everything else are unchanged, so both versions have the same room for improvement. Forward-only is below PITON in all 12 cells and loses 75%, all and 70% of the within-edge recall gain on the three benchmarks.

Table S2 Within-edge recall gain over the draft, averaged over the four open-weight drafters. Insertions are executed by the reranker for all four (Appendix E.4).

UltraToolShortcutsBenchMCP-Atlas
PITON+11.41+4.52+18.53
Forward-only+2.80−0.10+5.52

We also want to mention that one of the previous methods, GNN4Plan, is conceptually very close to PITON: both take the tools already chosen as anchors and pick the next tool among their graph neighbours by matching the query against tool descriptions. The main difference is the order, yet with the same LLM, PITON is 6.0 to 21.1 edge F1 above GNN4Plan (Table 3). So most of PITON's within-goal gain comes from reading the graph after the draft is finished.

[Role of the deletion reranker] The deletion reranker does not target the within/cross gap directly. It removes tools that the graph does not support, so that wrong anchors do not bring in wrong candidates and insertion starts from the right positions.


We are grateful for the reviewer's valuable comments on the writing, and we believe the revisions based on them make the paper easier to read. We hope these revisions address your concerns and would appreciate it if you would consider raising your score. We are happy to answer any further questions.

Dear Reviewer pg2n,

Thank you once again for your valuable comments on our submission. In response, we have:

  1. explained the Figure 2 example step by step in its caption (W1);
  2. added a table that maps each finding to the design that addresses it (W2);
  3. clarified how PITON targets within-goal dependencies, supported by an order ablation (W3).

Since the discussion phase will close soon, we would like to ask whether these revisions have addressed your concerns, which were mainly about the presentation. Please feel free to let us know if any part still needs clarification. If the revisions have resolved your concerns, we would greatly appreciate it if you could reconsider your score.

We sincerely look forward to your feedback.

Best regards, The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.