acceptodds
Under review as a conference paper at ICLR 2027

GRAFT: Graph-Tokenized LLMs for Tool Planning

Abstract

Large language models (LLMs) are increasingly used to complete complex tasks by selecting and coordinating external tools across multiple steps. This requires aligning tool choices with subtask intent while satisfying directional execution dependencies among tools. To do this, existing methods model these dependencies as tool graphs and incorporate the graphs with LLMs through retrieval, serialization, or prompt-level injection. However, these external graph-use strategies all follow a matching paradigm, which often fails to align tool choices with the underlying subtask structure, producing semantically plausible plans that violate graph constraints. This issue is further exacerbated by error accumulation, where an early incorrect tool selection shifts the plan into an invalid graph state and causes subsequent predictions to drift away from the valid execution path. To address these challenges, we propose GRAFT, a graph-tokenized language model framework for dependency-aware tool planning. GRAFT internalizes the tool graph by mapping each tool node to a dedicated special token and learning directed tool dependencies within the representation space. It further introduces on-policy tool context distillation, training the model on its own sampled trajectories while distilling stepwise planning signals. Experiments show that GRAFT not only achieves state-of-the-art performance in exact sequence matching and dependency legality, but also improves end-to-end task execution on a realistic interactive agent benchmark, highlighting its potential for reliable real-world workflows.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM, task planning, tool use, graph-tokenised LLM

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_fquPOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies dependency-aware tool planning for LLM-based agents. Existing methods often rely on external tool graphs for retrieval or planning, while autoregressive tool generation may suffer from error accumulation when an incorrect tool is selected early in the sequence.

To address these issues, the authors propose GRAFT, which represents each tool as a dedicated token and uses graph-token edge reconstruction to learn directed tool dependencies within the LLM. The method further introduces on-policy tool context distillation, where a student generates tool sequences from user queries, while a frozen teacher receives additional information, including decomposed subtasks and ground-truth tool sequences, to provide step-level supervision.

The authors evaluate GRAFT on four tool-planning datasets using three LLM backbones. Results show consistent improvements in sequence accuracy and dependency-related metrics over existing baselines. An additional evaluation on τ²-bench Retail reports higher task completion rates than PLaG and ToolGen.

Critical strengths
  1. S1: Method Design.

    The idea of learning directed tool dependencies within the LLM is interesting and well motivated. The combination of graph-token edge reconstruction and on-policy distillation is reasonable, and the paper is clearly presented. Compared with methods that rely on external graph information, GRAFT can generate tool plans directly from user queries without requiring additional graph context at inference time. The ablation and link prediction experiments also provide evidence that graph supervision contributes to planning performance.

  2. S2: Experimental Results and Efficiency.

    The experiments are generally well designed and cover four tool-planning datasets and three LLM backbones. GRAFT consistently outperforms ToolGen in sequence accuracy, while reducing inference-time token consumption. The authors also provide ablation studies and additional analyses of learned tool dependencies and graph robustness. The evaluation on τ²-bench Retail is a useful addition, as it shows improvements in task completion beyond offline sequence matching.

Critical weaknesses
  1. W1: Contribution of On-Policy Distillation.

    While the ablation results show that distillation improves performance, the contribution of the on-policy strategy remains unclear. In Eq. (9), the teacher has access to both the subtasks and the ground-truth tool sequence, providing strong supervision. The current experiments do not sufficiently distinguish the benefit of on-policy training from that of privileged teacher supervision. More direct comparisons with alternative training strategies would strengthen the claimed contribution.

  2. W2: Scope of Dependency-Aware Planning.

    Appendix B states that the evaluation retains samples with chain-structured dependencies, which simplifies the original graph planning problem. Real workflows may involve multiple prerequisites, branching, or parallel tool calls. Although the τ²-bench results are encouraging, the evaluation is limited to one domain with 15 tools. It remains unclear how well GRAFT generalizes to more complex dependency structures.

Questions for authors
  1. Q1: On-Policy Distillation.

    The teacher has access to the ground-truth tool sequence during distillation. Could the authors compare OPD with off-policy distillation and budget-matched SFT? A comparison with gold-label supervision on student-generated prefixes, with appropriate handling of off-path states, would also help clarify the specific benefit of the proposed distillation strategy.

  2. Q2: General Tool Dependencies.

    Appendix B indicates that the evaluation mainly uses chain-structured tool sequences. How would GRAFT handle workflows involving multiple prerequisites, branching, or parallel tool calls? It would be helpful to clarify whether the current planning formulation can represent and enforce such dependencies.

  3. Q3: Error Recovery.

    Although the interactive evaluation includes replanning after execution failures, it does not isolate the model's ability to recover from incorrect tool prefixes. Could the authors evaluate GRAFT on deliberately corrupted prefixes and compare it with the SFT-only model? This would provide more direct evidence of the robustness gained from OPD.

  4. Q4: Interactive Evaluation.

    The interactive evaluation in Section 4.7 only compares against PLaG and ToolGen. Since other graph-based methods, such as GTool and GNN4Plan, are already included in the offline experiments, why are they not evaluated in the interactive setting? Including these baselines under the same executor setup would make the end-to-end results more convincing.

  5. Q5: Code Availability and Reproducibility.

    I was unable to access the anonymous code repository linked in the paper. Could the authors check the link and make the implementation available? While Section 4.1 describes the shared experimental setup, some details of how ToolGen was adapted to the current planning task remain unclear, particularly its training and decoding settings.

3 comments

Thank you for your thoughtful review and useful suggestions.

W1 / Q1. Contribution of on-policy distillation.

We compare GRAFT with the SFT-only baseline and an off-policy distillation variant. The off-policy variant uses the same frozen teacher and privileged context as GRAFT, but replaces student-generated prefixes with gold prefixes. We also evaluate OPD without the gold tool sequence in the teacher prompt. Results on Llama-3.2-3B are:

MethodHuggingFace EMNEDACPLMultimedia EMNEDACPL
SFT-only (w/o distill.)59.810.172.4171.760.152.88
Off-policy distillation61.700.162.4873.300.142.91
OPD w/o gold tools62.000.162.5473.050.152.91
GRAFT (OPD)62.400.132.6274.800.113.09

Off-policy distillation outperforms SFT-only, showing the benefit of privileged teacher supervision. With identical teacher context, OPD further improves EM and ACPL. This supports learning from student-generated prefixes. OPD without gold tools also outperforms SFT-only, showing that the gains do not rely solely on the reference tool sequence.

W2 / Q2. General tool dependencies.

Our offline evaluation focuses on chain-structured tool sequences, as described in Appendix B. However, our interactive evaluation on τ²-bench Retail includes conditional workflows, where tool selection depends on order status, user confirmation, and execution feedback. GRAFT handles these scenarios through stepwise planning based on execution outcomes. The results are show in Table 3.

For branching dependencies, different branches can be serialized into valid tool sequences. However, a branching workflow may have multiple valid execution orders. Therefore, evaluating such workflows requires metrics that account for multiple valid execution paths. Our experiments across multiple benchmarks have demonstrated GRAFT's ability to model tool dependencies. We leave a systematic evaluation of branching dependencies to future work.

Q3. Recovery from incorrect tool prefixes.

We add a corrupted-prefix experiment. After generating the first tool token, we insert a random incorrect tool token and continue decoding. For each test sample, GRAFT and SFT-only receive the same injected token. We measure the exact match of the generated continuation against the ground-truth suffix (Suffix EM).

MethodHuggingFace original EM (%)HuggingFace Suffix EM (%)Multimedia original EM (%)Multimedia Suffix EM (%)
SFT-only59.8151.2071.7662.30
GRAFT62.4055.6074.8066.40

Under corrupted prefixes, GRAFT exceeds SFT-only by more than 4 points on both datasets in Suffix EM. This provides direct evidence of greater robustness to erroneous prefixes. Original EM and Suffix EM use different evaluation targets, so we report them separately.

Q4. Additional interactive baselines.

We now add GNN4Plan and GTool under the same interactive evaluation setup on τ²-bench Retail:

MethodTCR (1) (%)VGER (%)TCR (5) (%)
PLaG12.575.052.5
GNN4Plan17.582.460.0
GTool20.088.865.0
ToolGen30.092.980.0
GRAFT40.098.785.0

GRAFT achieves the best task completion rate and valid graph edge rate among the evaluated methods.

Q5. Code availability and reproducibility.

The anonymous repository link expired in early November. Access has now been restored.

For a fair comparison, we adapt ToolGen's tool-token generation approach to our tool-sequence planning task. Each tool is represented by a dedicated token, and the model is trained to generate an ordered tool sequence directly from the user query. This follows ToolGen's retrieval-oriented formulation but extends the output from individual tools to complete tool sequences. We do not use its end-to-end agent-tuning stage, which additionally models tool arguments and execution feedback. We will clarify this in the paper.

Thank you for your sincere response and additional experiments. This rebuttal has addressed most of my concerns. Although generalization to branching and parallel dependencies remains insufficiently evaluated, I am satisfied overall and I will raise my rating.

We sincerely thank you for your constructive feedback and for recognizing our efforts by raising the score.

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

This paper proposes GRAFT for dependency-aware multi-step tool planning. It uses dedicated tool tokens and subtask grounding to associate tools with their intended operations, and graph-token edge reconstruction to learn directed tool dependencies. It further introduces On-Policy Tool Context Distillation, which trains on student-generated prefixes using a teacher given reference subtasks and tool sequences to reduce error accumulation. Experiments on HuggingFace, Multimedia, UltraTool, and ToolBench with three LLM backbones show consistent improvements in sequence accuracy and correct prefix length over the evaluated baselines. An additional evaluation on the retail domain of τ²-bench suggests that these planning improvements can also benefit interactive execution.

Critical strengths
  1. The paper explores how to incorporate directed tool dependencies into LLMs to improve planning reliability. This addresses a practical challenge, since selecting appropriate tools is not enough when their execution order must also satisfy dependencies.

  2. The method combines tool grounding, dependency learning, and on-policy training in a coherent way. Reconstructing valid successors provides structural supervision beyond individual training trajectories, while distillation addresses the mismatch between training on correct prefixes and generating potentially incorrect ones at inference.

  3. GRAFT consistently improves over the evaluated baselines across four datasets and three backbones. The interactive evaluation further strengthens the empirical results, with task completion rates of 40% using one prediction attempt per step and 85% using up to five.

Critical weaknesses

W1: The comparison with related tool-tokenization methods is limited. Section 4.1 includes ToolGen, but Section 2 does not sufficiently discuss approaches such as ToolkenGPT, ToolWeaver, and Toolscaler. Their settings may differ, so not all are directly comparable. Nevertheless, a clearer account of these differences and comparisons where applicable would help establish GRAFT’s contribution beyond existing tool-tokenization approaches.

W2: The source of the distillation gains remains unclear. The teacher in Section 3.4 receives both reference subtasks and ground-truth tool sequences. The ablations in Section 4.3 and teacher accuracy analysis in Section 4.5 do not separate the benefit of on-policy training from this privileged supervision. Comparing on-policy and gold-prefix distillation with identical teacher context would more directly establish the contribution of training on student-generated prefixes.

W3: The efficiency comparison in Section 4.4 omits ToolGen, despite it being the strongest planning baseline and also representing tools as dedicated tokens. Comparisons against methods requiring graph serialization or repeated LLM calls do not establish whether GRAFT offers an efficiency advantage over tool-token generation alone. Reporting ToolGen’s token consumption and latency under the same setup would make this claim more convincing.

Questions for authors
  1. Do you have results comparing GRAFT with ToolGen using graph-constrained decoding, to distinguish the benefits of learned dependency representations from simply enforcing valid tool transitions?
  2. With identical teacher context, does on-policy distillation outperform gold-prefix distillation? How does student performance change when gold tool sequences are removed from the teacher prompt?
  3. Does the current evaluation include branching or conditional dependencies beyond chain-structured plans? If so, how does GRAFT perform on those cases?
2 comments

Thank you for your detailed review and specific suggestions.

W1. Related tool-tokenization methods.

We will expand Section 2 to distinguish GRAFT from other tool-tokenization methods:

  • ToolkenGPT learns tool embeddings for tool invocation.
  • Toolscaler focuses on scaling tool representations to large tool pools.
  • ToolWeaver uses hierarchical tool representations to improve scalability.

These methods focus on representing or scaling tools. GRAFT instead learns directed tool dependencies for autoregressive tool-sequence planning and addresses error accumulation through OPD. We will make this distinction clearer in the related work.

W2 / Q2. On-policy versus off-policy distillation.

We add an off-policy distillation baseline. It uses the same frozen teacher and privileged context as GRAFT, but replaces student-generated prefixes with gold prefixes. We also remove the gold tool sequence from the teacher prompt while retaining subtasks. Results on Llama-3.2-3B are:

MethodHuggingFace EMNEDACPLMultimedia EMNEDACPL
SFT-only (w/o distill.)59.810.172.4171.760.152.88
Off-policy distillation61.700.162.4873.300.142.91
OPD w/o gold tools62.000.162.5473.050.152.91
GRAFT (OPD)62.400.132.6274.800.113.09

Off-policy distillation improves on SFT-only, showing the value of privileged teacher supervision. OPD performs better with the same teacher context, especially in ACPL. This supports the benefit of training on student-generated prefixes. Removing gold tools still gives competitive results, so the improvement is not solely due to access to the reference tool sequence.

We also evaluate how different teacher prompt variants affect teacher prediction accuracy:

Teacher contextHuggingFace accuracy (%)Multimedia accuracy (%)
Query only59.671.5
Query + Tools80.288.8
Query + Subtasks82.484.6
Query + Subtasks + Tools93.099.0

The two datasets show different trends: tool sequences are more helpful on HuggingFace, while subtasks are more helpful on Multimedia. However, combining both provides the strongest teacher predictions.

W3. Efficiency relative to ToolGen.

For a fair comparison, we adapt ToolGen's tool-token generation approach to our tool-sequence planning task. Both the adapted ToolGen baseline and GRAFT take only the user query as input and autoregressively generate tool-token sequences. Therefore, we expect comparable inference costs and do not claim an efficiency advantage over ToolGen. We will clarify this in Section 4.4.

Revised text for Section 4.4. The adapted ToolGen baseline follows the same inference procedure as GRAFT, directly generating tool-token sequences from user queries. We therefore omit it from the efficiency comparison, as both methods have comparable inference procedures without additional graph inputs or inference steps.

Q1. ToolGen with graph-constrained decoding.

We add ToolGen + Graph Constraint, which restricts each next-tool prediction to the outgoing neighbors of the previously generated tool. Results with Qwen2.5-1.5B are:

MethodHuggingFace EMNEDACPLMultimedia EMNEDACPL
ToolGen50.000.192.2855.200.182.61
ToolGen + Graph Constraint51.300.192.3057.000.182.65
GRAFT53.200.182.3364.000.162.75

Graph constraints slightly improve ToolGen's EM by restricting the decoding space, but its performance remains below GRAFT. Such hard constraints can propagate early prediction errors by limiting subsequent tool choices. In contrast, GRAFT learns directed dependencies during training while preserving query-conditioned tool generation.

Q3. Branching and conditional dependencies.

Our offline evaluation focuses on chain-structured tool sequences, as described in Appendix B. However, our interactive evaluation on τ²-bench Retail includes conditional workflows, where tool selection depends on order status, user confirmation, and execution feedback. GRAFT handles these scenarios through stepwise planning based on execution outcomes. The results are show in Table 3.

For branching dependencies, different branches can be serialized into valid tool sequences. However, a branching workflow may have multiple valid execution orders. Therefore, evaluating such workflows requires metrics that account for multiple valid execution paths. Our experiments across multiple benchmarks have demonstrated GRAFT's ability to model tool dependencies. We leave a systematic evaluation of branching dependencies to future work.

Dear Reviewer RME8,

As the author–reviewer discussion period closes soon, we would greatly appreciate your feedback on whether our response has adequately addressed your concerns.

Should any concern remain, we would be glad to provide further clarification within the remaining window. If our responses have resolved your concerns, we would be grateful if you would consider inceasing your score.

Thank you for your time and consideration.

Best,

Authors

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

This paper proposes a graph-tokenized language model framework for dependency-aware tool planning. Compared to ToolGen, it includes tool dependencies for tool tokens and on-policy distillation for its own trajectories. Extensive experiments demonstrate the effectiveness of the proposed methods compared to SOTA.

Critical strengths
  • This paper is well-organized and easy to follow.
  • This paper introduces an effective way to include dependencies for tool tokens by graph-token edge reconstruction and context distillation.
  • This paper achieves performance improvements in both experiments and end-to-end real-world workflows.
  • Code is provided.
Critical weaknesses
  • Compared to ToolGen, this paper includes dependencies between tool tokens. It seems straightforward to utilize contrastive learning and OPD to conduct edge reconstruction and further learning. Are there any challenges or insights used in these procedures?
  • The tokens are fixed, leading to low scalability. Also, there might be overfitting among these fixed tool dependencies.
  • Based on edge reconstruction, the dependencies are learned with supervision. If there are new dependencies or even new tools in the real world, should the whole learning process be conducted from scratch? Please discuss the cost.
Questions for authors

Please see the weaknesses.

5 comments

Thank you for your careful review and constructive comments.

R1. Technical challenges and design choices.

GRAFT is not a simple combination of contrastive learning and on-policy distillation. It addresses two challenges specific to tool-sequence planning:

  • Graph-to-generation alignment. Learning edge relations between tool-token embeddings alone does not ensure that an autoregressive LLM can use them to select the next tool. Unlike isolated tool matching, tool planning requires the model to use both the user query and the preceding tool sequence. We therefore sample variable-length directed paths through Training Sequence Generation and use Graph-Token Edge Reconstruction to predict all valid successors from contextual hidden states. Reverse-edge negatives capture dependency direction, while subtask-to-tool grounding connects tool tokens to task intent. This makes the learned graph relations usable during autoregressive generation.
  • Error accumulation in tool sequences. A wrong tool is more consequential than an isolated word error: it changes the planning state and can make subsequent tool transitions invalid. The model must then continue from an incorrect prefix, where errors can accumulate. To the best of our knowledge, GRAFT is the first work to explicitly address error accumulation in dependency-aware tool-sequence generation through on-policy distillation. Our On-Policy Tool Context Distillation uses student-generated trajectories and a frozen teacher with both privileged subtask and tool-sequence context.

Therefore. the challenge is not simply to encode graph edges or apply distillation, but to develop a framework tailored to dependency-aware autoregressive tool planning.

R2–R3. Fixed tool tokens, overfitting, and adaptation cost.

We agree that unseen tools require new tool tokens and additional training, but full retraining is not necessary. Appendix E.4 in paper evaluates GRAFT in an incremental adaptation setting. Specifically, we hold out 10% of the tools and update the model using trajectories involving the new tools and their dependencies.

DatasetJoint training EM (%)Incremental EM (%)Full retrainingIncremental adaptation
HuggingFace53.253.08.4 min2.2 min
Multimedia64.063.611.9 min3.1 min

Overfitting to fixed dependencies. GRAFT does not rely solely on graph edge reconstruction. It also learns tool semantics through subtask-to-tool grounding and query-to-tool SFT. In Appendix E.5, EM drops by at most 1.4 percentage points when 40% of graph edges are corrupted or removed. These results show that GRAFT is robust to imperfect dependency graphs rather than relying heavily on exact graph structures.

Adaptation cost. Incremental training retains nearly the same EM as joint training while reducing the training time from 8.4 to 2.2 minutes on HuggingFace and from 11.9 to 3.1 minutes on Multimedia. This supports efficient updates when the tool pool changes.

Dear Reviewer k2CG,

As the author–reviewer discussion period closes soon, we would greatly appreciate your feedback on whether our response has adequately addressed your concerns.

Should any concern remain, we would be glad to provide further clarification within the remaining window. If our responses have resolved your concerns, we would be grateful if you would consider inceasing your score.

Thank you for your time and consideration.

Best,

Authors

Dear Reviewer k2CG,

As the discussion period is coming to an end, we would really appreciate it if you could take another look at our rebuttal.

According to your comments, we have clarified the technical challenges and provided experimental evidence for efficient incremental adaptation and robustness to changing graph dependencies.

We have also addressed the main concerns of the other two reviewers with additional experiments, and both have kindly raised their scores from 2 to 3. If you have similar concerns, we would appreciate it if you could also check our responses to them.

We hope our responses have addressed your concerns and would be grateful if you could reconsider your score.

We would also be happy to discuss any further questions or concerns you may have. Thank you again for your time!

Regards,

Authors

Comments on the paper

1 comment

Dear Area Chair,

As the discussion period comes to an end, we would like to briefly summarize our rebuttal.

We have addressed all reviewers' concerns through additional experiments and clarifications. All three reviewers have raised their scores from 2 to 3.

One additional consideration raised during the discussion concerns branching and multi-prerequisite dependencies, which extends somewhat beyond the primary scope of our current study. Our framework can accommodate such workflows by converting valid execution paths into tool sequences, and we have also demonstrated its effectiveness in an interactive agentic setting. However, systematically evaluating these more complex scenarios requires additional baselines, datasets, evaluation metrics, and ground-truth definitions that account for multiple valid execution paths. We leave this extended evaluation to future work.

We would like to emphasize that dependency-aware tool planning is an important challenge for building reliable LLM agents. Our method introduces a novel approach to internalizing tool dependencies within LLMs and, to the best of our knowledge, is the first to explicitly address error accumulation in dependency-aware tool planning through on-policy distillation.

We sincerely hope you will give particular consideration to the novelty, significance, and practical value of our work in your final assessment.

Thank you very much for your time and consideration!

Best regards,

Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.