Can Graph Learning Improve Planning in LLM-based Agents?
Authors: Xixi Wu
Yifei Shen
Caihua Shan
Kaitao Song
Siwei Wang
Bohang Zhang
Jiarui Feng
Hong Cheng
Wei Chen
Yun Xiong
Dongsheng Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Task Planning
Language Agents
Graph Learning
Graph Neural Networks
Language Model
Primary area: graph_neural_networks
TL;DR: This paper presents an initial exploration into graph-learning-based approaches for task planning in LLM-based agents.

Abstract: Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs). It aims to break down complex user requests in natural language into solvable sub-tasks, thereby fulfilling the original requests. In this context, the sub-tasks can be naturally viewed as a graph, where the nodes represent the sub-tasks, and the edges denote the dependencies among them. Consequently, task planning is a decision-making problem that involves selecting a connected path or subgraph within the corresponding graph and invoking it. In this paper, we explore graph learning-based methods for task planning, a direction that is orthogonal to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs, which is adeptly addressed by graph neural networks (GNNs). This theoretical insight led us to integrate GNNs with LLMs to enhance overall performance. Extensive experiments demonstrate that GNN-based methods surpass existing solutions even without training, and minimal training can further enhance their performance. The performance gain increases with a larger task graph size.

Can Graph Learning Improve Planning in LLM-based Agents?
Xixi W3
Yifei Shen 2+
Caíhua Shan
Kaitao Song²
Siwei Wang?
Bohang Zhang'
Jiarui Feng"
Hong Cheng"
Wei Chen
Yun Xiong
Dongsheng Li
Fudan University
Microsoft Research Asia
Thhe Chinese University of Hong Kong
*Peking University
WWashingoon University, Saint Louis
Abstract
Task planning language agents is emerging as an important research topic along- side the development of large language models (LL.Ss). It aims to break down complex user requests in natural language into solvable sub-tasks, thereby fulfilling the original requests. In this context, the sub-tasks can be naturally viewed as graph, where the nodes represent the sub-tasks, and the edges denote the dependen- cies among them. Consequently, task planning is recision-making problem that involves selecting a connected path or subgraph within the corresponding graph and invoking it. In this paper, explore graph learning-based based methods for task planning, a direction that is orthogonal to the prevalent focus on prompt design. Our interest in graph learning stems from theoretical discovery: the biases of attention and auto-regressive loss impede L.Mss' ability to effectively navigate Docision-making on graphs, which is adeptly addressed by graph neural networks (GNNs). This theoretical insight led us to integrate GNNs with LLMs to enhance overall performance. Extensive experiments demonstrate that GNN-based methods surpass existing solutions even without training, and minimal training can further enhance their performance. The performance gain increases with larger task graph size."
Introduction
LLM--ased agents have recently emerged as a rapidly growing field of research and are considered significant step towards artificial general intelligence (AGI) [61, 7]. These agents have achieved remarkable successes across a variety of domains, as evidenced by their ability to address complex AI challenges (e.g., HuggingGPT [46]), excel in gaming environments (e.g., Voyager [58]), and drive innovation in chemical research (e.g., [5]). Within this burgeoning field, task planning in language agents emerges as a critical area of study. It involves LLMs autonomously interpreting user instructions, breaking user's s instructions in natural language into concrete and solvable sub-tasks, and then fulfilling the user's request by executing each sub-task [43, 46, 45J. For instance, in case of HuggingGPTT [46], task planning involves invoking expert Al models from the HuggingFace website to solve complex Al tasks beyond the capabilities of GPT alone.
Given its practical significance, numerous algorithms have been proposed, with a major focus on prompt design [45, 46, 33, 30, 60, 49, 71, 63]. This paper proposes to explore an orthogonal
denotes equal contributions. Work was done during Xixi Wu's (xxwuêse. cuhk. edu, hk) internship at Microsoft Research Asia. Corresponding authors (yifeishen@mi crosoft. com, yunx@fudan. edu, en)
Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University The code and datasets are available at https //g/thgh.t com hwom///whhharreey///aaaaaaaaa
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

direction, i.e., graph-learning- brase approaches. In task planning, solvable sub-tasks can be naturally represented as a task graph, wherein each node corresponds to a distinct sub-task, and each edge signifies the dependencies between these sub-tasks. The crux of task planning, therefore, involves selecting a connected path or subgraph to satisfy the user's request, which is a decision-making problem on graphs. Adopting this framework, we analyze the task planning capabilities of LLMs, specifically within the context of HuggingGPT [46]. Our empirical investigation uncovers that a con- siderable portion of planning failures can be ascribed to the LLMs' inefficacy in accurately discerning the structure of the task graph. This finding presents intriguing questions from both theoretical and empirical perspectives. Theoretically. it initiates discussion in processing task graphs. Empirically, it highlights the urgent need for developing effective and efficient strategies to mitigate this deficiency and improve task planning performance.
the inherent limitations of LLMs
For the theoretical question, we first investigate the expressiveness of Transformer architectures when applied to graph tasks with sequential graph input, such as edge list representations, which the graph input format for task planning. Our initial hypothesis is that the format of sequential graph input might not align with the inductive bias inherent graph structures, potentially reducing expressiveness. Contrary to this hypothesis, it is proved that by taking edge lists as the input, a widtt Transformer can solve graph decision-making problems by simulating dynamic programming algorithms on edge lists. Nevertheless, we find that LLMs' solutions lack invariance under graph isomorphism, an important property for graph decision-making problems. In addition, the expressiveness is weakened if the attention is sparse, which is typically observed in LLMs [66]. a
Beyond expressiveness, we also examine the influence of auto-regressive loss, demonstrating that it introduces spurious correlations that can be harmful to graph decision-making tasks. These insights expose the inherent limitations of LLMs in task planning and, more broadly, in graph-related problems (e.g., the challenges in [14, 59, 34)).
To tackle the limitations, we take the use of GNNs, which have been shown to adeptly handle graph decision-making problems, both in theory and in practice [24, 68]. Initially, we deploy LLMs to interpret an ambiguous user request, breaking it down into more detailed steps. Subsequently, we utilize a GNN to retrieve the relevant sub-tasks based on these detailed steps and the corresponding sub-task descriptions. Notably, this approach can be implemented without training if we adopt parameter-free GNN models such as SGC [65]. In the case of training- based methods, we apply the Bayesian Personalized Ranking (BPR) loss [41] facilitate learning from the implicit sub-task rankings. Extensive experiments demonstrate that the proposed methods achieve better performance than baselines. Specifically, our main contributions are summarized as follows:
Task Planning Formulation: This study presents a formulation of task planning as a graph decision decision-making problem. In the realm of task planning, our work initiates the exploration of graph learning methodologies to enhance performance. Concurrently, it introduces task planning
application in the graph learning domain.
2. Theoretical Insights: We prove that Transformers have expressiveness to solve graph Decision-making problems based on edge list input, but inductive biases of attention and the auto-regressive loss function may serve as obstacles to their full potential.
3. Novel Algorithms:
Based on the theoretical analysis, we introduce additional GNN for sub-task retrieval, available in both training-fres and training-based variants. The ex- periments on diverse L.MMs and planning datasets demonstrate that the proposed method outperforms existing solutions with much less computation time. Furthermore, the perfor- mance is further enhanced by improved prompts fine-tuned model.
2 Preliminaries
In this section, we introduce task planning in language agents and the current LLM-based solutions.
2.1 Task Planning in Language Agents
We start with the definition of task planning with concrete example of HuggingGPT [46]. In task planning, there a pool of pre-defined tasks. Task planning inputs include this task pool and user request. The user request is expressed in natural language, which is ambiguous and could encompass
2

---

User Request
Task Graph
Powe Dotection
Imasge Caption
Language Agents
Task Planning
Please generate an image where a girl reading book, and her pose the same as the boy in please
Summarization
Detection
Pose-to-Emago
Image- In-Text
Tranellation
"example.jpg deeccrine the new image with your voice.
Pose-to-Image-
to-Text
Imagge Classification
Audio Classification
Text-5p- Speech
Text-to- Speech
O lask node
Figure 1: Illustration of Task Planning in Language Agents (e.g., HuggingGPT [46])
multiple complex tasks, The output is a sequence of tasks and the order of their invocation to address the user's request.
Figure 1 features the task planning in HuggingGPT, with the pre-defined tasks corresponding to APIs from the HuggingFace website, such Translation and Pose-to- Image, accompanied by detailed descriptions. For instance, the detailed description for Translation is "Translation is the task of converting text from one language another". The request is "Please generate an image where a girl is reading a book, and her pose matches the boy in 'example.jpg', then describe the new image with your voice." The ground-truth output is sequence of four APIs (nodes): (Pose Detection, Pase-to-Ine to-Image, Image-ta Paage-to-Texte. -Text, Text-to-Speechi outlining the order of their invocation path). By invoking these APIS on HuggingFace, the user request can be fulfilled.
2.2 Current LLM-based Solution Task Planning
The current solution of task planning is purely based on LLMs and involves two stages [45, 46]. The first stage involves request decomposition, where user's ambiguous request is broken down into concrete steps via LLMs. For instance, the request illustrated in Figure is decomposed into the following steps: (1) analyze the pose of the boy; (2) take that pose and generate new image; (3) generate the caption for newly generated image; (4) convert the generated text into audio. The second stage is task retrieval. For each decomposed step, LLMs are employed to retrieve an appropriate task from the task pool and execute them in sequence. For example. "Analyze the pose of the boy" corresponds to Pose detection. The output tasks should be (1) Pose detection; (2) Pose-to-Image (3) Image-to- (4) Text-to-Speede Figure 6 illustrates this procedure.
3 Graph Formulation and Insights
3.1 Graph Formulation of Task Planning
In this subsection, we formulate the task planning as a decision maaiing problem on the task graph. The task graph is special kind of text-attributed graphs and we define it as G = (V, E, T'). Each node v E V represents pre-defined task in the task pool, associated with a text 1, function (e.g., "Translation. Translation is the task of converting text from one language to another."). Each edge (u, v) E indicates dependency between tasks (e.g., the output format of task matches the input format of task v). Task planning is to select path or connected sub-graph on the task graph.
describing its
Viewed from this angle, task planning bears resemblance traditional decision-making problems on graphs, such as planning for the shortest path. Compared with traditional planning, task planning in language agents involves diverse and open-ended goals due to the varied users' personal requests. For example, on platforms like HuggingFace, users' intentions span across video, text, and image domains. On the contrary, classic planning has fixed goal for given domain, which often explicitly expressed by mathematical formulas [55, 36].
3.2 Failures of LLMss in Planning: Empirical Findings
With the task graph at hand, we diagnose LLMs task planning in Figure We adopt the experimental settings as outlined in the work of HuggingGPT [46], where the prompts are specifically optimized for task planning on HuggingFace. The evaluation metric calculates the Fl score to assess the accuracy of the tasks identified by LLMs against the ground-trult tasks. Additionally, we report

---

80
Per Perfrmance-eun Task F2
Node (Hungtoghace
Fage ciagginghhee bdge (ultaatol)
Hallutnation Edge
Node (Uibukal _
Hallucinstion
Node Hallucination (%)
90
Score (%)
20
Batchuun--4 Vicuna 13B
Codetloma- Cootttom--BBarra-- GPT-3.5
Godellame-13
GPT-3.S4urba
GPT-b-turto
(a) Performance and Hallucination ratios
(b) Hallucination ratios across datasets
Figure 2: Illustration (a) LLMs' planning performance and hallucination in HuggingGPT, and (b) hallucination in relation to task graph size.
two graph--rehaledd metries: the node hallucination ratio and the edge hallucination ratio. These metrics measure the frequency of non-existent nodes (i.e., tasks) and edges (i.e., dependencies) outputted by LLMs, respectively, indicative of the models' misinterpretation of the graph input.
Our empirical findings reveal that (1) LLMs exhibit a certain hallucination ratio, and (2) there is strong correlation between the hallucination ratio and planning performance. This suggests that LLMs struggle to accurately interpret the task graph while the task graph is the key to the performance.
We further explore whether the incidence of hallucinations correlates with the number of sub-tasks. The HuggingGPT dataset contains 23 sub-tasks, and our analysis is expanded to incorporate the Tot dataset [20], which consists of 260 sub-tasks. Figure 2b illustrates that the hallucination ratio increases with a larger task graph size.
3.3 Failures of LLMs in Planning: Theoretical Insights
In this subsection, we provide theoretical insights into the limitations of LLMs in processing task graphs. In contrast to previous graph learning approaches for graph decision- making problems, LLMs process the graph input by flattening it into sequence and are trained using auto-regressive loss. We will then examine the impact of these two factors.
How does sequential graph input impact the expressiveness? We consider general graph decision- making problems that can be resolved using dynamic programming (DP) described (2). The input comprises the edge list and initial states:
U1 01 [[1] u1 12 clui][u]] ... u1 Answer(O] ... uh Answer(0][ua
(1)
edge list
initial states
The intended output format is u, Answer[k][uu]] ... u, Answer[k[[[u.] existing studies, task graphs often presented in (1), where the edge list is described by natural language and the initial states are the task descriptions each task node, detailed Appendix A.9 of [45].
As discussed in the previous subsection, task planning is decision- decision-making maaiing problem on the task graph. The decision-making problems on graphs are often solved by DP [3] and its general formulation is given by
Answer[k|[[] (Hjerto) A -aap:///wwwwwwww]]]]]]]]]]]] c(]1)))
where Answer[k][i] is the solution to state i in the k-th iteration, c[i][]] [j] is a cost associated with state i and j. T(i) is the set of state can be transited to i, LjeT(a) is an aggregation function such as MAX or SUM, and f.g are task-specific update functions. We give the formulation of typical DP algorithms in Appendix D.1 including some NPC problems. For the decision makinng problems on the text-attributed graphs (e.g., task planning), may conceptualize them DP in the feature space, as discussed in [68].
To our surprise, although the edge list input does not directly reflect the geometric structures of graphs, enables Transformers to simulate DP efficiently, in terms of expressiveness, as demonstrated by the following theorem.

---

Theorem 1. (LLMs have enough expressiveness) Assume the input format is given in (1) and f.g. D in DP update (2) satisfy the assumptions 1 and 2 in Appendix. There exists a log-precision constant- depth and constant-wer width Transformer that simulates one step of DP update in (2). As consequence, there exists a log-precision -le)-depth and constant-widle Transformer that simulates l steps of DP update in (2).
The proof is presented in Appendix D.2. However, certain aspects of the proof's constructions challenging to be realized in Transformers that have been pretrained on natural language. First, the embedding process must be carefully filtered ensure invariance under graph isomorphism. This invariance property does not align with the inductive biases inherent in natural language, making it difficult to achieve. Consequently, if an LLM can accurately produce the correct answer for specific ordering of nodes, it might not maintain this accuracy after the nodes have been reordered (experiments given in Appendix D.3). Second, each token needs to synchronize its hidden states with all other tokens sharing the same token ID, which is of order O(VV). In practice, the attention trained from natural language typically sparse [66], leading to intractability issues. The formal lower bound is provided in the following proposition and the proof is given in Appendix D.4.
Proposition 1. (Inductive bias of language hinders expressiveness) Assume the input format is described (1) and that the attention mechanism is limited to attending to constant number of tokens. There exists at least one instance of one-step DP update such that no log-precision constant-widnt constant-depth transformer can simulate.
How does auto-regressive Loss impact the generalization? Our investigation next focuses on the auto-regressive loss and considers the following scenario: given a fixed task graph, user data is collected to perform instruction tuning with next-token pereenctpeiiiionnnn loss. For a tractable theoretical study, we conceptualize this issue as a wath-planning problem, since the output of task planning is essentially path. We consider the training dataset comprises input sequences of the form s s U1 U2 ... t. where s represents the source node, the target node, and the sequence s 1 822 ... t is path that adheres 8 and 1, the model is expected to generate a path with the same constraint. Our findings indicate that auto-regressive loss can lead the emergence of frequency bbased spurious correlation, as substantiated by the following theorem and the proof is given in Appendix D.5.
specified constraints. During testing, given the initial and target nodes
Theorem 2. (Spurious correlations of auto-regressive loss) Assume (1) the loss employed is a next- token-prediction loss utilizing cross-entropy, applied to the sub-sequence U1 02 ... 1 during training; (2) the output logits determined by target node and the current node 1/-1- Let Ne a be the number of times in the training dataset such that t is the target node, Vi-1 is the current node and 0n the next node. The optimal logits for predicting the next node u from current node U
towards target node t is given by é. [.] NN,N 1.1
NN.;-1." 1115
E Ne > 0. 1f No, = O,
é [u] can be any non-negative number subject to E. 83 [u] 1.
In our setup, s t is the instruction and the third token is duplicate of the first token. It reasonable to exclude these tokens in the loss calculation, which is the first assumption. The second assumption assumes that the output only depends requirement for path-related problems. For DP problems, the frequency- bbssed prediction contradicts to the value-based ground-truth. We then give an example that auto-regressive loss even cannot find a valid path.
the current node and target node, which is minimal
Example 1. Consider training dataset consisting of sufficient number of valid paths. Suppose the dataset contains two paths a b e and b c d and there are no other paths such that t = d and the current node V.- = a for all i. Then we have Na.,, for all and the logits for the next node can be arbitrary. This results in the model's inability to predict the next node of a when given a as the source node and d as the target node.
To human, finding a path from a to d simply involves concatenating the paths a b e and e d. However, auto-regressive loss fails under such circumstances. In task planning datasets, we indeed observe that the performance of fine-tuned I.LMs is inferior to that of GNNs trained on the same dataset, shown in Figure 3b.
5

---

4 Integrating GNNs and LLMs for Planning
4.1 Motivations
In the last section, we find that a considerable portion of planning failures can be ascribed to the LLMs' inefficacy accurately discerning the structure of the task graph, due to the hallucination, the inductive bias of the attention, and next-token prediction loss. In contrast to LLMs, GNNs can strictly operate on the task graph, thereby avoiding hallucinations. Additionally, they leverage the graph structure as input, rather than flattening the graph into sequence, thus overcoming the theoretical limitations discussed previously. Furthermore, GNNs have demonstrated proficiency in handling graph decision-making problems, both theoretically and empirically [68, 11, 24]. As result, the simplest fix is to integrate GNNs into the task-planning algorithm.
In the following subsections, we propose both training-free and training- based approaches to enhance performance. Training-free methods are necessary when the available tasks are continuously changing, or new tasks are emerging constantly. This scenario is common when the task planning module is deployed in a new system. Once the task planning module has been deployed for a period. it becomes possible to collect users' requests and label a small proportion of the data, enabling lightweight training-basse methods.
4.2 A Training-free GNN-based Approach
As we discussed in Section 2.2, the current solution to task planning involves two stages. The first stage requires the ability understand users' requests in natural language and break them down into concrete instructions, which is the unique ability of LLMs. The second stage is to select a path on the task graph, where each node corresponds stage. The illustration of our framework is shown in Figure 7 in Appendix.
decomposed step. Thus, we can integrate GNNs in this
For each decomposed step outputted by the first stage, we use GNN to select a corresponding node within the task graph. Suppose we are selecting the node for the i-th decomposed step. First, we utilize a small pre-trained language model, c5- [62], embed the i-th decomposed step. The resulting embedding is denoted x; ste Second, for the task graph, we first the same pre-trained language model e5-335M to convert each node's description into embeddings, denoted as the node feature hy, where the superscript indicates the layer and the subscript represents the node. Then we adopt a K K-layer SGC [65] to compute the final node embeddings, resulting in h. = kk) Given a sequence of previously selected task nodes fer,--- U;-1), ). the next node v; is chosen according to v argmax (hh. a; !.P)) where h, is the final node embedding, and N ((v-1) denotes the neighbors of node f/-1 in the task graph. Particularly, U1 can be selected from the whole graph.
As e5-33MM pre-trained and SGC is parameter-free the proposed method requires no additional training and can be effectively applied in zero-shot manner.
4.3 A Training-required GNN-based Approach
The inference process in required methods mirrors that of the training- free approach, with the difference being the substitution of parameter-free GNNs with parametric counterparts, such as GAT [57] or GraphSAGE [15]. Here we specify the training process of GNNs.
We assume that each entry in the task planning dataset comprises a user re- quest, a sequence of decomposed steps, and the corresponding ground-truth tasks, denoted as (request, {si,..., 8n). (vI..... ). If the dataset does not adhere to this format, we reformat it accordingly using GPT-4 with details provided in Appendix C.2. It is important note that there is a one-to-one correspondence between the steps and tasks in the dataset. Therefore, the training dataset can be represented as {(;, e,)) where s; is step described in natural language, and v, is its corresponding invoked task.
Data Preparation:
Training Loss: The problem in the dataset can be viewed binary ranking problem, where the labeled node is and the other nodes are O. Therefore, we adopt the Bayesian Personalized Ranking (BPR) loss [41] designed for recommendation with binary rankings. The loss function is given by é -= (amtee
r.,o)) (omee,,ro log o a(h,, xep) (hor, ())),, where steep represents the embedding of the step's 's textual description generated by e5- is the ground- task, and e is a negative task.

---

We select negative tasks that are textually similar to the positive task, and for computational efficiency. we limit our selection 2 negative tasks per positive task. The trainable parameters may merely include GNNs or both GNNs and e5-335M with illustrative configurations shown in Figure 8 in Appendix.
5
Experiments and Analysis
5.1 Experimental Setup
Datasets: We utilize four datasets across two task planning benchmarks: HuggingFace tasks, Multimedia tasks, and Daily Life API tasks from TaskBench [45], as well as TMDB API tasks from RestBench [50]. The HuggingFace dataset includes Al models the HuggingFace. The Multimedia dataset provides a wide range of user-centric tasks, such as file downloading and video editing. The Daily Life APIS cater to everyday services like web search and shopping functionalities. TMDB focuses on movie-related search and retrieval tasks. Statistics for each dataset are presented in Table 7 with illustrative examples shown Figure 4 in Appendix. Other benchmarks, such ToolBench [39] and ToolAlpaca [54], are less suitable for our experiments due to (1) the absence of well-defined task graph detailing tasks and their dependencies, and (2) a scarcity of samples involving multi-task planning, with focus on single-task retrieval.
For the datasets from Task we split 3000 samples for training and 500 samples for testing, each containing an invocation path with at least two tasks. For the TMDB dataset, we first filter to include the samples with two or more invoked tasks, and then randomly select a sample served as the in-context learning example. The remaining 94 samples are designated for testing. We adopt the evaluation metric in TaskBench [45] and HuggingGPT [46], i.c., Node FI-Score (n-FI) and Link F1-Score (I-F1), which measure the accuracy of invoked tasks and invoked dependencies, respectively. Besides, the Accuracy (Ace) can measure the success rate from task level. We also measure the token consumption (# tok) as the efficiency metric.
Evaluation:
Choices of LLMs: We consider close-sourced LLMs, i.e., GPT-3.5-turbo and GPT-4-turbo, as well as open-sourced LLMS with different parameter scales, including Codel Jama-13B(or Ins--nsttutt- [42], Misttra--7B-Instrutt--dd
[23], Vicuna-13B-v1.. [72], and Baichuan2-13B-CCN [69].
Choices of GNNs: To comprehensively investigate the effectiveness of different graph learning methods for task planning, we consider wide range of graph neural networks, including SGC [65], GCN [26], GAT [57], GraphSAGE [15], GIN [67], and Graph Transformers [47].
5.2 Performance of the Training-free Approach
We compare the performance across three training-free methods: (1) LLM's Direct Inference is introduced in Section 2.2. (2) GraphSearch [33, 52, 32] leverages the classic graph search method to generate the candidate nodes and uses LLMs to give score for node selection. Given a step, GreedySearch consistently selects the node with the highest score and adjacent to the previous task node; AdaptiveSearch selects the nodes with scores above a fixed threshold, adjusting the breadth of the search space in an adaptive mode: BeamSearch retains the k nodes with highest scores. (3) SGC [65] employs training- maining-free SGC for task retrieval based on decomposed task steps. The details of baselines are given in Section E. and illustrated in Figure Table shows both the overall performance and token consumption costs, with results of Accuracy (Acc) moved to Table 9
in Appendix.
Compared with direct inference, integrating an SGC consistently improves performance, underscoring the effectiveness of the proposed method. GraphSearch-typ methods rely on beam search identify paths and employ LLMs for evaluation, where longer processing times generally lead to better outcomes. Notably, our proposed method achieves comparable or superior performance (Table I and Table 9) to BeamSearch while requiring 5-10 times fewer tokens (Table 1) and inference time (Table 10). The case studies are provided in Appendix H. However, we observed only marginal improvements with GPT-4-turbo. A unique feature of GPT-4-turbo is its ability to manage ChatGPT. plugins, and may have been specially trained on task planning datasets. In addition, the pre-trained language model used for feature extraction in SGC is e5-335M, which may not be sufficiently powerful to effectively analyze GPT-4's output. detailed diagnostic analysis of cases involving GPT-4 is provided in Figure 11 in Appendix.
7

---

Table Comparison of Training-free Methods: Overall Performance (Node-F1 and Link-F1 in %) and Token Consumption in x 10'. Performance of other LLMs are given in Table 8.
TaskBench Multimedia
RestBench TMDB
LLM
Method
HuggingFace
Daily Life
n-F1
I-F1
# Tok 4
R-F1
L-F1
Tok
n-F1"
I-F]
TTk
R-F1
I-F/ 1
*Tok
Direct
21.27
53.57
73.70
3.82
14.01
2,02
Vicuna 13B
AcaptreeSearch
GraedyySearch
54.36
52.94
25.75
25.67
9.81
6.23
51.24
46-19
24.32
23:11
11.25
5.55
62.71
42.98
31.15
13.33
13:92
7.18
41
45
45.22
13.69
7.02
6.51
3.42
BeamScarch
$6.64
26.93
24.11
54.55
15.41
7.79
SGC
59.62
31.98
2.31
61.78
37.60
83.33
63.77
3.82
15:99
1.89
Direct
60.60
30.23
2.49
69.83
39.85
2.64
84.26
53.63
3.77
62. 02.23
22.02
1.96
Mistral 7B
GreedySearch
65.91
38.13
6.52
58.92
34.72
10.66
6,26
75.
86.39
49.47
10.92
8.27
60.64
21.35
23.18
4.38
BeamSearch
67.13
36.73
25.66
73.55
47.12
31.10
85.87
61.53
39.1 19
63.41
26.79
11.26
SGC
67.43
42,08
2.32
74.07
49.90
2,43
87.13
66.49
3,54
64.72
255 .6.
1.89
Dircet
28.88
76.07
3,88
68.
43.74
2,02
CadeI.lama 13B
AdaptiveScarch
SrurolySeurch
60.85
61,67
31.66
34.072
11.10
5.95
67.90 98
14
42.04
11.71
6.77
4.95
91.34
91.50
76.09
76.56
7.18
5.54
66.
63.74
37.17
42.16
8.16
3.81
BeamScarch
62.65
34.31
20.14
69.53
43.35
19.51
91.74
76.60
19.19
68.
42.99
8.88
73.32
92.96
79.57
3.64
71.40
47.55
1.90
Direct
73.85
45.73
2.14
82.85
62.07
2.26
96.09
83.65
3.36
81.70
57.5
1.67
3.5-tucbo
GPT-
AcaptiveSearch
GreedySearch
72.18
62.75
43.88
47.55
7.47
5.29
81.86
81.11
62.71
63.012
5.71
4.92
93.79
93.77
81.41
81.26
8.53
7.36
76.
77.57
53.65
50.11
5.89
3.06
HeamSearch
75.51
49.62
83.57
64.50
12.91
95.
22.05
57. 9M
6,42
SGC
76.37
50.04
2.02
83.65
63.66
2.09
96.38
86.19
3.16
82.63
59.15
1.61
Direet
77.60
52.18
2.19
88.29
69.38
2.28
97.36
$4.58
3.37
82.56
56.67
1.75
4-turbo
GPT:
AduptivSSerrhh
SrarcyS
BeamScarch
76.17
77.56
50.44
52.54
$1.30
8.94
8.98
88, 16
88.02
70.39
69.99
6.90
7.14
97.35
97.30
85.78
85.80
7X
9.04
7.37
8.99
80.
75
81.78
51.00
55.15
6.35
3.73
5.18
SGC
77.79
52.20
2.03
88.54
69.83
2.10
97.35
85.76
3,16
82.27
36.37
1.62
5.3 Performance of the Training-based Approaches
Settings: We further explore the efficacy of training- based GNNs in three TaskBench datasets. The TMDB dataset is excluded due to its limited sample size. Throughout our experiments, we trained a spectrum of GNN variants, both with and without co-training the small LM (i.e., e5-335M), whose role is to generate node embeddings derived from task names and descriptions. Owing to space constraints, we only show the performance of GraphS AGE in the main text, relegating detailed comparison of all the situations to Table 11 and Table 12 in Appendix.
Compared Methods: Due to the lack of training- based baseline methods specifically for task planning, we adapt two existing approaches that combine LLMs and GNNs for graph-related tasks, including: (1) TAPE [16] employs a LLM + LM + GNN architecture for node classification task. In this framework, LLMs generate high-quality explanatory text for each predicted node, which is then fine-tuned by an LM to produce node embeddings. Finally, GNN performs the downstream classification. We adapt TAPE for task planning by reformulating the problem as classifying user requests into corresponding node labels within the task graph. (2) Graph [38] uses GNNs to tokenize graph nodes, which are then fed into LLMS to generate textual outputs. In our adaptation for task planning we treat the user request as the input question and the expected plan as the generated answer. Additional implementation details are provided in the Appendix F.2.
From Table 2, we observe significant improvement in performance when employing a training- based GraphSAGE approach over the training-fres free method. However, the co-training of GNNs with e5-335M does not yield marked improvement, suggesting that message passing is the crucial element for enhancing performance. Further analysis across broad spectrum of GNNs (as shown in Table 11 and Table 12) reveals that powerful GNNs, such as GINs, perform similarly to networks perceived as less complex, like GCNs, and even underperform compared to GraphSAGE. This pattern indicates that the task's challenge may not lie in the expressiveness of the models but rather in their ability to generalize. Regarding baselines, TAPE is unsuitable for task plamning as its classification approach simplifies task planning, overlooking task dependencies. While GraphToken demonstrates superior performance over LLMs' direct inference, we have noted instances of minor hallucination. This observation suggests that GraphToken's 's understanding of the task graph is not yet perfect. In addition, GraphToken is limited to open-sourced LLMs. Besides, our proposed approaches also greatly boost the parameter prediction performance, given in Appendix G (e.g. 9% improvement to GPT-3.5-turbe and 3% improvement to GPT-4-turbo).
Observations:
Efficiency: The details of the training time are given in Table 13. The training cost is remarkably low because we use e5-335M [62] as the text embedding model for GNNs. If the trainable parameters are limited to the GNNs alone, training typically concludes within just 3 minutes. Furthermore, the
8

---

Table Comparison with Training-based Approaches: Node-F1, Link-F1, and Accuracy are reported in %. TAPE [16] is designed for node classification task and cannot predict links, so we report Link-F1 as "NA". GraphToken [38] requires finetuning LLMs, which not compatible with
close-sourced LLMs. The performance of other GNNs and L.MSs are given in Table 11 and Table 12 the Appendix.
HuggingFace ace L.F
Multimedia I-FI
Daily Life I-F1
LLM
Method
m.PI
Acc t
n=FI
Acc
n-F7
Ace
Direct
50.46
21.27
8.72
53.57
23.19
11.20
73.70
45.80
24.43
TAPE 59.47
NA
5.07
54.97
NA
2.07
73.26
NA
12.50
Vicuma-13B
GraphToken
63.37
31.54
15.61
65.40
36.38
19.87
81.65
48
43.37
GraphSAGE
61.86
35,68
20.08
63.71
39.88
21.37
86.07
67.63
48.64
GraphSAGEeessu mnn
62.82
37.04
19.68
65.89
42.18
21.58
84,23
65. .4
47.81
Direct
60.60
30.23
16.36
69.83
39.85
25.11
84.26
53.63
44.52
TAPE
61.82
NA
6.13
58.92
NA
3.29
76.40
NA
16.44
Mistral-7B
GraphToken
64.42
32.04
18.60
72.31
42.60
30.31
86.82
57.06
53,99
GraphSAGE
68.12
43.09
25.77
75.51
52.94
34.29
87.51
66.57
52.74
GraphSAGEsssmin
67.61
43.14
27.20
76.96
55.46
33.26
87.61
66.75
52.97
Direct
57.55
28.88
14.29
68.57
41.79
24.10
91.20
76.07
66.40
TAPE
64.03
NA
8.05
58.27
NA
2.01
77.74
NA
17.37
1odeLJamm--13B
GruphToken
62.15
32.55
74.57
35.06
92.50
7.357
69,42
GraphSAGE
67.30
42.41
26.56
74.93
54.52
38.55
93.84
80.38
73.60
GraphSAGGEssmnn
68.92
44,85
29.58
76.28
55.41
37.75
93.30
79.51
74.00
Direct
73.85
45.73
28.95
82.85
62.07
47.96
96.09
83.65
81.30
GPT-3.5-turbo
TAPE
68.00
NA
62.43
NA
GraphSAGE
77.90
52.68
35.11
85.29
65.80
53.55
96.43
86.26
83.13
GraphSAAGP
77.87
53.04
35.32
85.51
66.56
55.91
96.34
86.09
83.13
Direct
77.60
52.18
33.68
88.29
69.38
60.56
97.36
84.58
86.77
GPT-4-turbo
TAPE
68.82
NA
9.50
63.94
NA
4.02
71.51
NA
9.40
GraphSAGE
78.76
52.53
34.09
88.63
69.65
60.36
97.34
85.67
86.97
GraphSAGFee main
78.49
52.62
33.88
88.86
70.25
62.37
97.42
85.80
86.57
Table 3: Performance Comparison of SGC and GraphSAGE on the UltraTool Benchmark [20].
Integrating GNNs can lead to more significant improvements in LLMs on larger task graphs.
O-shot
1-shol
LLM
Method
n-F1
I-F1
Acc 1
Tok
n-F1
I-FI
Acc
Tok
Direct
38.88
16.42
13.58
10,535
57.64
30.44
26.25
10,737
BeamScarch
49.71
22.51
17.08
26,008
64.93
36.23
33.47
23,023
CodeLlama-133
SGC
61.07
37.61
25.31
10,456
71.64
44.00
39.68
10,658
GraphSAGE
63.78
39.91
27.98
10,456
72.81
45.26
43.49
10,658
Direct
54.35
21.35
18.33
8,462
63.58
30.85
25.00
8,614
GPT-3,5-turbo
BeamScarch
55.40
28.02
19.76
21.979
63.41
34.05
26.28
20,813
SGC
59,80
37.82
25.87
8,352
64.96
37.96
29.70
8,504
GraphSAGE
63.97
42.26
30.35
8,352
70.49
47.79
39.74
8,504
Direct
68.63
40.01
27.20
8,513
69.54
41.79
28.17
8,693
BeamScarch
71.29
43.99
30.40
18,793
71.99
44.54
31.62
20,515
GPT-4-turbo
SGC
70.87
44.01
31.60
8,346
70.46
44.82
33.00
8,504
GraphSAGE
70.67
43.83
34.40
8,346
70.75
47.68
37.22
8,504
training duration extends to only 15 minutes when GNNs are jointly trained with c5-335M model.
This efficiency stands in stark contrast to the 10-20 hours required for tuning open-sourced LLMs.
5.4 Scaling to Large Task Graphs
To demonstrate the scalability of our method to larger task graphs, we conducted a supplementary experiment on the newly released planning benchmark UltraTool [20], which features a relatively large task graph with 260 nodes. Details on processing this dataset are provided in Appendix C.3.
We present a performance comparison of GNN models (training-free SGC and saiiinn-requiine GraphSAGE) against strong baselines like BeamSearch in Table 3. Among the metrics, accuracy (Acc) calculated based on whether the predicted tasks match the ground-truth tasks, measuring the success rate at each case level. In such conditions, integrating GNN significantly enhances performance and mitigates planning failures, e.g., GPT--4turbo undergoes 9.05 % accuracy improvement with the introduction of GraphSAGE.

---

CodeLlama-138
Mistral-77
HuggingFace
Multimedia
90
Driect GradhSAGE
Direct
Direct
Direct GraphSAGE
GraphSAGE
GraphSAGE
Node F1-5core (%6
70
Node F1 Score (9)
70
40
whot hrond Huu s.hct snat THo
colell cwwelle Sar Hagaarr
(a) Different Prompts
(b) Fine-tuned LLMs
Figure 3: Orthogonal Effectiveness to both Improved Prompts and Fine-tuned LLMs
The results indicate that (1) LLMs' performance is vulnerable to the scale of task graphs; (2) The performance gain of the proposed method increases with a larger task graph.
5.5 Improved Prompts and Fine-tuned L.LMs
In this subsection, we show that the proposed method is orthogonal to two dominant methods, i.e., prompt engineering and fine-tuning.
Orthogonal to Improved Prompts: We investigate GNN's effectiveness when applied to improved prompt templates, i.c., strategically designed prompts that enhance the task planning abilities of LLMs. Specifically, we consider two types of prompts: (1) In-context Learning with Increased Examples [45] During main experiments, we maintain the consistent 1-shot in-context learning example for LLM's direct inference. To realize further improvements, we increase the number of examples 2, and results under this setting are denoted "2-shot Prompt"; (2) Plan like Graph (PlaG) [30] We adopt the prompt in [30] to encourage LLM to think and plan in graph-like manner. Specifically, we convert the entire task graph into plain text and then integrate PlaG instructions to enhance LLM's planning. Results under this prompt template are denoted as "PlaG Prompt".
From the results shown in Figure 3a, where we apply three different prompts to CodeLlama-1e and Mistral-7B on HuggingFace, it is clear that applying GraphSAGB AGE to improved prompts, where task steps are more concisely decomposed and predictions are more accurate, can also boost performance.
Orthogonal to LLMs' Fine-tuning: To explore whether our framework maintains effectiveness on fine-tuned LLMs. which have acquired -ppaset- task planning capabilities, conduct further experiments. For each dataset, we use LoRA [19] to fine-tune two LLMs of different parameter scales, including lama-77B and Vieuna-138 based the same training data GNNs. Details of fine-tuning process are provided in Appendix F.3. The finetuned model is named as "FT-Codel and "FT "FT-Vicuna" in Figure 3b.
The results depicted in Figure 3b demonstrate that fine-tuning markedly enhances the task-planning capabilities of LLMs. Furthermore, applying GraphSAGE to the decomposed tasks of LLMs further improves the accuracy task planning.
Conclusions
This paper presents an initial exploration into graph-learningbaase based approaches for task planning in language agents. Through theoretical analysis, we demonstrate the inductive bias of the attention mechanism and the utility of auto-regressive loss impedes their effectiveness in task planning. We propose to integrate GNNs for task graph analysis, which yields performance improvements across a range of LLMs and planning benchmarks.
Despite the encouraging performance, there are limitations that highlight significant opportunities for enhancement. Firstly, our proposed method, while effective, straightforward; more sophisticated graph-learning-ban based decision-making algorithms could potentially offer further improvements. Secondly, the construction of the task graph currently requires manual effort. Investi- gating automated graph generation techniques for diverse applications is another promising direction for future work.
Limitations:
10

---

Acknowledgements
This work is partly supported by grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (No. CUHK 14217622).
References
Andrew Barto, Steven Bradtke, and Satinder P Singh. Learning using real-time dynamic programming. Artificial intelligence, 72(1-2):81-133 1995.
[2] Timothy EJ Behrens, Timothy H Muller, James CR Whittington, Shirley Mark, Alon Baram, Kimberly L Stachenfeld, and Zeb Kurth-Nelson. What is cognitive map? organizing knowledge for flexible behavior. Neuron, 100(2)490-509, 2018.
[3] Richard Bellman. Dynamic programming. science, 153(3731):34-3 1966.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyezyk, et al. Graph of thoughts: Solving claborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 17682- 17690, 2024.
[5] Daniil A Boiko, Robert MacKnight, Ben Kline, and Gabe Gomes. Autonomous chemical research with large language models. Nature, 624(7992):500-578 2023.
Blai Bonet and Hector Geffner. Labeled rtdp: Improving the convergence of real-time dynamic program- ming. In ICAPS, volume pp. 12-21, 2003.
[7] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Eee Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li. Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4, arXiv preprint arXiv:2303.12712, 2023.
[8] Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličkovic. Combinatorial optimization and reasoning with graph neural networks. Journal Machine Learning Research, 24(130): 1-61, 2023.
[9] Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. GraphLLM: Boosting graph reasoning ability of large language model. arXiv preprint arXiv:2310.05845, 2023.
[10] Dillon Z Chen, Sylvie Thiebaux, and Felipe Trevizan. Learning domain-independeri heuristics for grounded and lifted planning. In Proceedings the AAAI Conference Artificial Intelligence, volume 38, pp. 20078-20086, 2024.
[11] Andrew Dudzik and Petar Veličković. Graph neural networks are dynamic programmers. Advances in neural information processing systems, 35:20635-220 -06033,552277---- 2022.
[12] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di Hc, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024.
[13] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
[14] Jiayan Guo, Lun Du, and Hengyu Liu. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint 2.t.::335..5666 2023.
[15] William I.. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs In NIPS, 2017.
[16] Xiaoxin Hc, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi. Harnessing explanations: Lim-to-Im interpreter for enhanced aext-attributed graph representation leamning, 2023.
[17] Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh V Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. G-retriever: augmenee generation for textual graph understanding and question answering, arXiv preprint 4rXiv:2402.07630. 2024.

---

[18] Malte Helmert and Carmel Domshlak. Landmarks, critical paths and abstractions: what's 's the difference anyway? In Proceedings of the International Conference on Automated Planning and Scheduling. volume 19. pp. 162-169, 2009,
[19] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. ArXiv, abs/2106.09665 2021.
[20] Shijue Huang, Wanjun Zhong, Jianqiao Lu, Qi Zhu, Jiahui Gao, Weiwen Liu, Yutai Hou, Xingshan Zeng, Yasheng Wang. Lifeng Shang, Xin Jiang, Ruifeng Xu, and Qun Liu. Planning, creation, usage: Benchmarking Ilms for comprehensive tool utilization in real-world complex scenarios, 2024.
[21] Wenlong Huang. Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. In International Conference on Machine Learning, pp. 91 18-9147. PMLR, 2022.
[22] Xu Huang, Weiwen Liu, Xiaolong Chen, Xingmei Wang, Hao Wang, Defu Lian, Yasheng Wang, Ruim- ing Tang, and Enhong Chen. Understanding the planning of Ilm agents: A survey. arXiv preprint arXiv:2402.02716. 2024.
[23] Albert Qiaochu Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de Las Casas, Florian Bressand, Gianna Lengyel. Guillaume Lample, Lucile Saulnier, L'elio Renard Lavaud, Maric-Anne Lachaux, Pierre Stock, Teven I.c Scao, Thihaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b. ArXiv, abs/23 0.06825, 2023.
[24] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[25] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412,6980, 2014.
[26] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Leurning Representations (ICLR), 2017.
[27] Yuhan Li, Zhixun Li, Peisong Wang, Jia Li, Xiangguo Sun, Hong Cheng, and Jeffrey Xu Yu. A survey of graph meets large language model: Progress and future directions. arXiv preprint 11X1:9 2023.
[28] Yuhan Li, Peisong Wang, Zhixun Li, Jeffrey Xu Yu, and Jia Li. Zerog: Investigating cross-dataset zero-shot transferability in graphs. arXiv preprint arXiv:2402. 1235, 2024.
[29] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
[30] Fangru Lin, Emanuele La Malfa, Valentin Hofmann, Elle Michelle Yang, Anthony Cohn, and Janet B. Pier- rehumbert. Graph-enhanced large language models in asynchronous plan reasoning. ArXiv, abs/2402.02805. 2024.
[31] Liu, Yugian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone, Llm+ p: Empowering large language models with optimal planning proficiency. arXiv preprint arXiv:2304.11477 2023.
[32] Xukun Liu, Zhiyuan Peng, Xianyuan Yi, Xing Xie, Lirong Xiang, Yuchen Liu, and Dongkuan Xu. Toolnet: Connecting large language models with massive tools via tool graph. ArXiv, abs/2403.00839, 2024.
[33] Zhaoyang Liu, Zeqiang Lai, Zhangwei Gao, Erfei Cui, Xizhou Zhu, Lewei Lu, Qifeng Chen, Yu Qiao, Jifeng Dai, and Wenhai Wang. Controlllm: Augment language models with tools by searching on graphs. ArXiv, abs/2310.17791 2023.
[34] Zihan Luo, Xiran Song, Hong Huang, Jianxun Lian, Chenhao Zhang, Jinqi Jiang, Xing Xie, and Hai Jin. Graphinstruct: Empowering large language models with graph understanding and reasoning capability. arXiv preprint arXiv:2403.c 044433, 2024.
[35] Jiayuan Mao, Tomás Lozano- Pérez, Josh Tenenbaum, and Leslic Kaclbling. What planning problems can a relational neural network solve? Advances in Neural Information Processing Systems, 36, 2023.
[36] Jiayuan Mao, Tomas Lozano-Perezz Joshua B. Tenenbaum, and Leslie Pack Kaelbing. What Planning Problems Can A Relational Neural Network Solve? In Advances in Neural Information Processing Systems (NeurIPS), 2023.
12

---

[37] Ida Momennejad. Hosein Hasanbeig, Felipe Vieira Frujeri, Hiteshi Sharma, Nebojsa Jojic, Hamid Palangi. Robert Ness, and Jonathan Larson. Evaluating cognitive maps and planning in large language models with CogEval. Advances in Neural Information Processing Systems, 36, 2023.
[38]
Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami AI-Rfou, and Jonathan Halcrow. Let your graph do the talking: Encoding structured data for llms, 2024.
[39] Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang. Bill Qian, Sihan Zhao, Runchu Tian, Ruobing Xie, Jie Zhou, Mark Gerstein, Dahai Li, Zhiyuan Liu, and Maosong Sun. Toolllm: Facilitating large language models to master 16000+ real-worke apis. 2023.
[40] Nils Reimers and Iryna Gurevych. Sentence- Sentence embeddings using siamesc bert-networks. In Conference on Empirical Methods Natural Language Processing, 2019.
[41] Steffen Rendle, Christoph Freudenthaler, 7eno Gantner, and Lars Sichiid--Thieme Bpr: Bayesian personalized ranking from implicit feedback. arXiv preprint arXiv: 1205.2618, 2818, 2012.
[42] Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov. I. Evtimov, Joanna Bitton, Manish P Bhatt, Cristian Cantón Ferrer, Aaron Grattafiori, Wenhan Xiong. Alexandre D' efossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. Code llama Open foundation models for code. ArXiv, abs/2308. 12950, 2023.
[43] Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems, 36, 2024.
[44] William Shen, Felipe Trevizan, and Sylvie Thićbaux. Learning domain- inneeennendd planning heuristics with hypergraph networks. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pp. 574-584, 2020.
[45] Yongliang Shen, Kaitao Song, Xu Tan, Wengi Zhang, Kan Ren, Siyu Yuan, Weiming Lu, Dongsheng Li, and Yueting Zhuang. Taskbench: Benchmarking large language models for task automation. arXiv preprint S..iv:2311.187660 2023.
[46] Yongliang Shen, Kaitao Song. Xu Tan, Dongsheng Li. Weiming Lu, and Yueting Zhuang. Huggingept: Solving tasks with chatgpt and its friends in hugging face. Advances in Neural Information Processing Systems, 36, 2024.
[47] Yunsheng Shi, Zhengjie Huang, Wenjin Wang. Hui Zhong, Shikun Feng, and Yu Sun. Masked label prediction: Unified massage passing model for semi-supervised classification. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCA), 2021.
[48] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement leaming. Advances in Neural Information Processing Systems, 36, 2024.
[49] Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 11523-11534 IEEE, 2023.
[50] Yifan Song, Weimin Xiong, Dawei Zhu, Wenhao Wu, Han Qian, Mingbo Song, Hailiang Huang, Cheng Li, Ke Wang, Rong Yao, Ye Tian, and Sujian Li, Restgpt: Connecting large language models with real-world restful apis, 2023.
[51] Simon Ståhlberg, Blai Bonet, and Hector Geffner. Learning general optimal policies with graph neural networks: Expressive power, transparency, and limits. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 32, pp. 629 637, 2022.
[52] Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Sai Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung yeung Shum, and Jian Guo. Think-on-grapp on-gaph: Deep and responsible reasoning of large language model on knowledge graph. 2023.
[53] Jiabin Tang, Yuhao Yang. Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin. and Chao Huang. GraphGPT: Graph instruction tuning for large language models. arXiv preprint arXiv:2310. 13023, 2023.
[54] Qiaoyu Tang, Ziliang Deng, Hongyu Lin, Xianpei Han, Qiao Liang, and Le Sun. Toolalpaca: Generalized tool learning for language models with 3000 simulated cases, 2023.
13

---

[55] Sam Toyer. Felipe W. Trevizan, Sylvie Thiébaux, and Lexing Xie. Asnets: Deep learning for generalised planning, ArXiv, abs/1908.01362, 2019.
[56] Trieu H Trinh, Yuhuai Wu, Quee V Le, He He, and Thang Luong. Solving Olympiad geometry without human demonstrations. Nature, 625(7995):476-44 482, 2024.
[57] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference Learning Representations, 2018.
[58] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprint urXiv:2305.00291 2023.
[59] Heng Wang. Shangbin Feng. Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? Advances Neural Information Processing Systems, 36, 2023.
[60] Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka- Lee, and Ee- Ee-Peng Lim. Plan- and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. arXiv preprint 230502305, 2023.
[61] Lei Wang. Chen Ma. Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang. Xu Chen, Yankai Lin, et al. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):1-26, 2024.
[62] Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang. Rangan Majumder, and Furu Wei. Text embeddings by superv-s contrastive pre-training. ArXiv, abs/2212.03533 2022.
[63] Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, al. thain-of-thought prompting clicits reasoning in large language models. Advances in neural information processing systems, 35:24824- 24837, 2022.
[64] James CR Whittington, Timothy H Muller, Shirley Mark, Guifen Chen, Caswell Barry, Neil Burgess, and Timothy EJ Behrens. The eichenbauih machine: unifying space and relational memory through gencralization in the hippocampal formation. Cell, 183(5):1249-1265) 2020.
[65] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
[66] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks, arXiv preprint arXiv:2309. 000223099775333 17453, 2023.
[67] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[68] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? arXiv preprint arXiv: 1905. 2019.
[69] Ai Ming Yang, Bin Xiao, and et al. Baichuan 2: Open large-scale language models. ArXiv, hbss2309.110055 2023.
[70] Kai Yang. Jan Ackermaan, Zhenyu He, Guhao Feng. Bohang Zhang. Yunzhen Feng, Qiwei Ye, Di He, and Liwei Wang. Do efficient transformers really save computation? arXiv preprint UxXiv:2402.13922 2024.
[71] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
[72] Lianmin Zheng, Wei-Lin Chiang. Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin. Zhuohan Li. Dacheng Li, Eric P. Xing, Haotong Zhang, Joseph Gonzalez, and lon Stoica. Judging ilm-as-a-judge with mt-bench and chatbot arena. ArXiv, abs/2306.05685. 2023.
[73] Wanjun Zhong, Lianghong Guo, Qigi Gao, He Ye, and Yanlin Wang. Memorybank: Enhancing large language models with long-term memory. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 38, pp. 19724-19731, 2024.
14

---

Contents
1
Introduction
2
Preliminaries
2.1
Task Planning in Language Agents
2.2
Current LLM-based Solution Task Planning
3
Graph Formulation and Insights
3.1
Graph Formulation of Task Planning
3.2 Failures of LLMs in Planning: Empirical Findings
3.3 Failures of LLMs in Planning: Theoretical Insights
4
Integrating GNNs and LLMs for Planning
4.1
Motivations
4.2
A Traening-free GNN-based Approach
4.3
A Training-required GNN-based Approach
5
Experiments and Analysis
5.1
Experimental Setup
5.2
Performance of the Training-fres Approach
5.3
Performance of the Training-based Approaches
5.4
Scaling Large Task Graphs
5.5
Improved Prompts and Fine-tuned LLMs
10
Conclusions
10
Related Works and Discussions
17
A.1 Planning Algorithms LLMs
17
A.2 Task Planning in Traditional Al
17
A.3 Planning in Agents and Neuroscience
17
A.4 LLMs for Graphs
18
A.5 Theoretical Analysis of Reasoning
18
A.6 GNNs and GraphSearch for Combinatorial Optimization
19
Prompts
20
C Datasets
23
C.1 Overview
23
C.2 Reformatting Details of RestBench
23
C.3 Reformatting Details of UltraTool
23
D Supplementary Materials for Theoretical Results
25
15

---

D.1
Dynamic Programming
25
D.2 Proof of Theorem
25
D.3 Permutation Invariance Test of L.LMs
................................
26
D.4 Proof of Proposition
26
D.5 Proof of Theorem 2
27
Supplementary Materials for Training- free Methods
28
E.1
Implementation of Baselines
28
E.2 Results of All LLMS
28
E.3 Accuracy Results of Training-free Methods
29
E,4
Computational Cost Analysis
29
Supplementary Materials for Training-basee Methods
El
Implementation of Training-based GNNs
F2
Implementation of TAPE and GraphToker
31
E3
Implementation of Fine-tuning LLMs
................................
32
F4
Full Results of Training-based GNNs
32
F5
Performance of LM+GNN Co-trained Mode
35
F.6
Computational Cost Analysis
35
Experiments on Task Parameter Prediction
36
G.1
Prompting LLMs to Fill in Parameters
36
G.2 Empirical Results of LLMs Predicted Parameters
36
Case Studies
37
Broader Impacts
40
16

---

A Related Works and Discussions
A.1 Planning Algorithms in LLMs
The existing studies of task planning approaches can be categorized into several directions, including task decomposition, multi-plan selection, the use of external planners, reflection, and memory-aided planning [22]. Task decomposition methods, such as the chain-of-thought approach [63], employ the divide-anddconques strategy, utilizing LLMs for both task decomposition and sub-task planning. The application of this method to task planning is detailed in Section 2.2 and is referred to as "Direct" in the baseline comparison. Multí-plan selection strategies, exemplified by the tree-of-thought [71] and graph-of- of-thought [4], leverage besech-based methods to generate plans. Subsequently, LLMs evaluate these plans to select the most effective one. The "GraphSearchh methods used in our baselines fall into this category. External planner approaches [31] use LLMs convert the problem into Planning Domain Definition Language (PDDL) and then employ classic solvers to address the planning problem. PDDL requires a pre-defined goal, for example, moving the blocks from one state to another state. However, the goal of task planning investigated in language agents deals with more flexible and personal goals, spanning personal needs in video, text, and image processing. Translating these goals into formal PDDL is very difficult. We instead demonstrate that GNNs can serve as an effective external planner this application. Reflection-base methods [48] focus on reflecting upon experiences to refine the plan, while memory-aided planning approaches [73] utilize external experiences, such as those from search engines. These approaches are deployed in interactive environments and orthogonal to this paper.
A.2 Task Planning in Traditional AI
Apart from task planning in language agents, there is also domain in traditional AI called task
planning [1, 6, 18, 55, 44, 51, 35, 10]. Task planning in traditional Al is defined as (8, A, T, T,,,T,CC.. C, 8o). where S is the states, A is the action space, T S x S x A + [0, 1], cost function C : S x A > [0, oo), a set of goal states G C 8, and an initial state so- An agent following a policy т : A x S + [0, 1] will start in state 8o, then repeatedly choose new state s' ~ T(s'|s, a). incurring cost C(s, a) along its way. An optimal policy x (als) is one that reaches the goal state with probability while minimizing the total expected cost. Traditionally, task planning is solved by reinforcement learning approaches [6] and heuristic A approaches [18]. The neural network- based approaches are employed to accelerate the computation and improve the performance [55, 44, 51, 35, 10].
action
x(als) and execute it to reach
The task planning in language agents is a different application. It cannot be solved as a constraint satisfaction problem, since both the features of task graph and user request are expressed in natural language. Compared with traditional planning, task planning for language agents involves diverse and open-ended goals due to the varied personal requirements users have. For example, on platforms like Hugging Face, users' intentions span across video, text, and image domains. On the contrary, classic planning has a fixed goal for a given domain, e.g., in the n-puzzle [55], the goal is formally as placing the tiles in numerical order. Within this new application domain, while existing research primarily focuses on prompt design for pre-trained LLMs, our work underscores the importance of traditional planning methods, such as GNNs, in complementing L.MSs.
A.3 Planning in Agents and Neuroscience
Planning is pivotal topic in both agents and neuroscience, where graphs play an indispensable role. We believe the concepts and insights presented in this paper are useful to these fields.
The TaskBench, RestBench, and Totr dataset used in this paper belongs to the tool agents. The Math agent, AlphaGeometry, employs LLMs generate auxiliary constructions in geometry [56]. Considering lemmas as nodes and their interdependencies as edges, the endeavor to prove theorem resembles the task of identifying a route to the theorem node within the graph constituted by potential lemma nodes and the edges that represent their interdependencies. There are no explicit task graphs in game agents [58], embodied agents [21], and code agents [48]. The core strategy in these domains is to employ verbal reinforcement learning within LLMs. The state and transitions in reinforcement learning can be modeled as nodes and edges in the graph. In addition, there are case-by-case graph models in these agent applications. For example, in code agents, one can view the class as the nodes
17

---

and dependencies as the edges. In the embodied agents, the objects in the environment can be viewed as the nodes.
In the neuroscience, animal planning is often assessed through path planning in mazes [2, 64]. Inspired by these animal experiments, planning testbenches have been developed for LLMS [37]. A computational model known as the Tolman-Eichenbaum Machine (TEM) has been proposed to decipher the mechanisms of general planning in animals across various environments, such as mazes [64]. The TEM model posits that hippocampal cells, including place and landmark cells, remap between environments, while entorhinal cells exhibit a range of properties that mirror spatial responses, including grid, band, border, and object-vector cells. In essence, hippocampal cells map sensory inputs onto locations in abstract graphs and remap, and entorhinal cells execute graph operations.
A.4
LLMs for Graphs
With the breakthroughs in LLMs, there has been a surge of interest in applying LLMs to graph- related problems [27, 28]. GPT4Graph [14] and NLGraph [59] are two prominent benchmarks designed to evaluate the performance of LLMs in the context of graph tasks. They encompass wide spectrum of challenges, various input formats, and state-of-the-art prompting techniques, demonstrating that LLMs possess basic graph processing capabilities. Importantly, the choice of prompts and formats significantly influences performance. However, these benchmarks also expose the models' susceptibility to spurious correlations within graphs. For instance, GPT-4 achieves only about 50% accuracy on shortest-pat pooth tasks, even with the use of complex prompts. GraphInstruct [34] attempts to fine-tune LLMs on graph-theory-relate though it remains far from satisfactory. Despite these empirical efforts, there is limited theoretical understanding of these evaluation results. The analysis in Section 3.3 aims to shed light on the empirical observations reported in these studies.
tasks, resulting in improved performance,
Considering these negative results, a new line of research has emerged that utilizes the output of GNNs as tokens for L.LMs, seen in GraphGPT [53], GraphI.LM [9], Graph Token [38], and G-Retriever [17]. These approaches have demonstrated significant improvements in performance on GNN-related tasks. However, they have not yet been applied task planning due the lack of extensive training data. A promising future direction involves using task planning data generated by GPT to fine-tune graph foundation models, such as GraphGPT [53], and applying them task planning. This paper proposes to use task planning as new benchmark for this line of research.
A.5 Theoretical Analysis of Reasoning
Reasoning is closely related to task plamning and decision-making. The theoretical exploration of the reasoning abilities of neural networks was initiated by [68]. This work unifies various reasoning tasks, such as intuitive physics, visual question answering. and shortest path calculations, into DP problems. It then analyzes the generalization capabilities of MLPs, DeepSets, and GNNs. It is demonstrated that GNNs exhibit the best generalization bounds, attributed to their architecture 's resemblance to the Bellman-Forr algorithm, which is adept at solving DP problems. In terms of reasoning abilities within LLMs, [12] examines how the Chain of Thought (CoT) approach aids in solving arithmetic and DP problems without graphs. By decomposing challenging problems into simpler subproblems, CoT extends the expressive capabilities of Transformers from TC to P. This analysis is further applicd to linear and sparse Transformers in [70].
Our proof of Theorem I builds upon the proof of Theorem 4.7 in [12]. However, while [12] addresses DP problems without graph structures, Theorem specifically focuses on DP problems with graph edge list inputs. Moreover, unlike [12], which decomposes and solves the DP problem sequentially. Theorem proposes a method to simulate DP on edge lists in parallel. negative results rising from the inductive bias of attention mechanism and auto-regressive loss. These theoretical contributions are novel and promise be valuable for general reasoning and planning tasks.
addition, we analyze the
18

---

A.6 GNNs and GraphSearch for Combinatorial Optimization
GNNs are popular approaches for solving Recision-making problems on graphs. The problems investigated are typically NP-hard, such as the minimum vertex cover, maximum cut, and the traveling salesman problem [8]. The basic approach involves selecting nodes one by one manner
that satisfies the constraints [24]. In this paper, we adopt this method to sequentially select task nodes. Furthermore, reinforcement learning can he used to enhance the performance GNNs beyond what is achievable with supervised labels alone [24]. In [24], the node with the highest score is selected exclusively. Conversely, [29] employs beam search to improve performance by selecting the top-k nodes in single iteration. Additionally, GNNs are utilized as the method for variable selection in exhaustive searches for exact solutions to combinatorial optimization problems [13]. graph-based decision-making problem. Both greedy
This paper conceptualizes task planning and beam search algorithms have been adopted in task planning [33, 32]. Given this connection, promising future direction involves repurposing GNNs for decision-makee approaches in task- planning applications.
19

---

B Prompts
Table Prompt template for LLM's direct inference [45]
# TASK LIST # [( task list }}
GOAL #
Based on the above tasks, I want you to generate task steps and a task invocation graph (including nodes and edges) to address the # USER REQUEST # The format must be in strict JSON format, like:
"task "task_stepe" steps": step description for one more steps
"task nodes": H
"task": task name must he from # TASK LIST # "arguments": [a concise list of arguments for the task
}..
"task links": [[ "source": "task name "target": "task name j" }],
REQUIREMENTS
Generated task steps and task nodes can resolve the user request # USER REQUEST perfectly, Task name must be selected from TASK LIST #.
The task steps should strictly align with the task nodes, and the number of task steps should be same with the task nodes.
The task links should reflect the temporal and resource dependencies among task nodes, i.c., the order which the tasks are invoked.
# EXAMPLE #
[[ in-context learning examples }}
USER REQUEST
{{ user request }}
Now, please generate your response in strict JSON format: # RESULT
20

---

Table 5: Prompt templates of GraphSearch [33]
Scenario
Prompt
CANDIDATE TASK LIST #
{{ candidate tasks }}
GOAL
Based on the provided # CANDIDATE TASK LIST and the user's request descrihed the # STEP generate score dictionary to assess each task's ' prohlem-solving abilities. strict JSON format, like: "candidate task name I": score, ...
The output must
REQUIREMENTS #
1. The keys of the generated score dictionary must align with the provided candidate tasks, and you should output scores for all candidate tasks.
Task
2. The "score" field denotes concrete score that assesses whether each task can solve the given step's demand. The score should be the range of [1, 2, 3, 5), where a higher score indicates better task-solving and matching abilities.
Assessment
3. Carefully consider the user's 's intention in # STEP # to assign the score. If the STEP contains candidate task, its score should be >=
EXAMPLE #
{{ in-context learning examples }}
STEP
{{
step description }}
Now please generate your result in strict JSON format: # RESULT #
GOAL
Based on the provided # USER REQUEST and initially inferred STEPS #, select the best path solution list from SOLUTION LIST The selected solution should be the one that can perfectly solve user's request and strictly align with the inferred steps. The output must be in strict JSON format, like: { ("best_solution", solution": [list of invoked tasks ]}
REQUIREMENTS #
Carefully analyze both the user's request and previously inferred task steps. Select the best solution that can perfectly follow the inferred steps and solve user's request. Do not change their corresponding sequences.
2. Make sure that each task in the final solution list exists in the valid # TASK LIST {( task list }}.
Path Selection
USER REQUEST
{{ user request }}
STEPS {( steps }}
SOLUTION LIST #
{ list of searched solutions }}
Now please generate your result in strict JSON format: # RESULT
21

---

Table Prompt template for LLM's filling in invocation parameters [45]
# GOAL # Given a USER REQUEST and # PLANNED TASKS # to be invoked in sequence to solve this request, please fill up each invoked task's invocation parameters.
The format must be in strict ISON format, like:
"task_ bosk__ndess:: Hf
"task"; taas name must be from # PLANNED TASKS #", "arguments": concise list of arguments for this task
REQUIREMENTS
Consider each task's input output requirements, and carefully the arguments each task. Analyze the resource dependencies, keeping in mind that these tasks are invoked sequentially address the original request.
3. The number of predicted nodes must strictly align with the provided tasks.
USER REQUEST
{( user request }}
# PLANNED TASKS #
previously retrieved tasks }}
# DETAILS OFTASS #
[[ details, i.e., input and output requirements of each planned task }}
EXAMPLE
{[ in-contex: learning examples }}
Now, please generate your response in strict JSON format: # RESULT
22

---

Table 7: Statisties of Experimental Datasets
TaskBench Multimedia
RestBench TMDB
Type
Statistic
HuggingFace
Duily Life
UltraTool
# Node
23
40
40
46
260
Task Graph
# Links
225
449
1560
979
611
Link Type
Resource
Resource
Temporal
Resource / Category
Resource
All Data
Samples
7,546
5,584
4,320
100
3,527
Samples
500
500
500
94
500
Test Set
Avg Nodes
3.81
3.92
4.05
2.33
2.38
Avg Links
2.81
2.92
3.05
1.33
1.38
C
Datasets
C.1 Overview
We provide the statistics of experimental datasets from three task planning benchmarks in Table 7. The illustrative examples from each dataset are shown in Figure 4. For datasets from TaskBench [45], each sample consists of original user request, corresponding decomposed task steps, and ground- truth task invocation path. As RestBench [50] and UltraTool [20] include only user requests and corresponding API invocation sequences, we prompt GPT-4 to infer decomposed task steps aligned with each invoked API, thereby finalizing the dataset.
C.2 Reformatting Details of RestBench
The TMDB dataset from RestBench, focuses on movie-related searching and recommending functions. To align RestBench with our experiments, have implemented the following processing steps:
Reformatting original APIs by assigning unique task names and descriptions: APIs in RestBench represented by request paths, such "GET /movie/top coop_ratedd, referring to the API that retrieves top-rated movies on TMDB. To enhance semantic differentiation among APIs, we first prompt GPT-4 to assign unique name and a detailed functional description to each API. These names and descriptions were then manually verified and refined. For example, the API previously mentioned is renamed "Get Top-Rated Movies" with the description: "This API retrieves list of the highest-rated movies." Note that though the original TMDB dataset contains 54 APIs, some were never invoked in any data examples. Therefore, focus only those APIs that appeared in least one user request, resulting in a refined set of 46 APIs.
Constructing Task Graph: Each API is regarded as unique task node, and depict their relationships from two aspects: (1) categorical association, and (2) resource dependencies. For instance, APIs that provide movie-related functionalities, such retrieving movie details recom- mending films, are grouped under the movie category. Conversely, APIs focused on person-related functions, like searching for actors, classified under the person category. Additionally, if two APIs share a common parameter like move id, we establish a link between them to indicate a resource dependency.
Reformatting Raw Data Examples: The original data samples in RestBench included a single query and its corresponding API invocation sequence. To reformat this data into path structure, treated each invoked API as a node and the sequence of invocations as directed links from one API to the next. For example, TMDB data sample consists of the query "Who was the lead actor in the movie The Dark Knight" and corresponding ground-truth API solution ['GET /search/move moviee.. "GET /movie/ [movie_ sinovie_id//i ccddrreesss" We transform this solution into task invocation path as "[ "task nodes": ["Search Movie", "Get Movie Credit"], "task links"; [["source": "Search Movie", "target": "Get Movie Credit"]]]
C.3 Reformatting Details of UltraTool
Motivation: In our main experiments using TaskBench [45] and RestBench [50], we observed that strong LLMs like GPT-4-turbo already perform well. This may be attributed to two factors: (1) the training of GPT-4-turbo likely included knowledge relevent to these benchmarks, as both were released before GPT-4 and utilize popular platforms such as HuggingFace and TMDB; (2) the task
23

---

HagelngFace
Multimedia
Daily Life
TMDB
User Requea
have an image "example..jp" jps" I detect the objects the summary describing them, and then mudiff image accurdingly.
have old black and white photo "example.jpe" would like volorize imagee and then find other images that are colorized
Help me onder pizza from Uber Eats place (12 Main St.). Also, send an invitation email fhiend at #icelgeumpp my friend from her place.
I just finiched wasching Titanic and want some other movie recommendations.
image, generate
pick up
Siep Detect objects in the
Step Colorize the imput Step Perform similar image search using the colorized image ingun the Image Search tool
Call Order Food Delisery 'Pizor' Main SC, and platioom "Lber Eass Call Send Email with address and content
Stop / Call Search Movie to find the movie ID Titanic
lask Lav Luvocation Path Task Steps
Stop Apply Summarization
the output step I
Siop 2 Call Movic Revomment obtain list of recommended
Shep Modity the image based on
summarized
based
Stop Call Order Taxi with
location
Cijject Detection
Colorieer
Order Food Delivery
Scarch Movie
Summarization
Imasge Editing
image Search
Recomsnnend
By Image
Figure 4: Illustrative details of experimental datasets.
graphs are relatively small, containing no more than 50 tasks, which falls within the capabilities of LLMs. Therefore, aim evacuate planning performance as well as GNN's effectiveness in more challenging scenario, i.c., one that requires specific knowledge beyond the LLM's training and involves larger task graphs that possibly exceed its memory and reasoning capabilities.
We utilized UltraTool [20], released in March 2024, which features complex planning scenarios across thousands of tasks, including travel, tourism, and other daily life domains. The original UltraTool contains 5, 824 samples with 2, 032 available tasks across 22 distinct domains. However, we observed that some tasks appear in only one sample, making them quite rare. Therefore, we filtered this dataset as follows: first, we considered only tasks that appeared more than 5 times across all samples, focusing on more common tasks that cater daily life. Next, we retained samples that incorporated these filtered tasks, ensuring that the number of invoked tasks exceeded 2 to satisfy the multi-task planning scenario. After this filtering, we identified 260 distinet tasks. We then constructed the task graph by treating each task as a node and adding links between tasks that were invoked sequentially in the dataset. For each task, we further verified and refined its functional descriptions to ensure semantic suitability.
Constructing a Task Graph:
We allocated 500 samples for testing and 3. 000 samples for GNN training. Although the original UltraTool provided decomposed steps, we found them coarse-grained making it difficult to align step descriptions with suitable tasks. Therefore, employed similar strategy by prompting GPT-4 to infer decomposed task steps that align with each invoked task. As result, each data sample consists of the user request, corresponding steps, and fround-truth invoked tasks, ensuring high quality for GNN training.
Reformatting Raw Data Examples:
24

---

D Supplementary Materials for Theoretical Results
D.1 Dynamic Programming
The Longest Increasing Subsequence (LIS) problem is a classic dynamic programming problem that involves finding the length of the longest subsequence within given array arr where the elements are in strictly increasing order. The state transition function for the LIS problem can be expressed as:
Longest Increasing Subsequence:
Answer[k|[i]
max (Answer(k 1|[1 + (I( # x 1)), JET(#)
where (i)
and arr arr denotes the set of states that can transfer state i, the aggregation function g(z, y) is implemented as max(x, y), and the cost c[t][]] is 1 for those candidate states that are not equal to state adding the element leads longer subsequence while O for the state itself.
Bellman-Fort Algorithm: The Bellman-Ford algorithm is also a classic dynamic programming algorithm used to find the shortest paths from a single source vertex to all other vertices a weighted graph. The core idea behind the Bellman-Fone algorithm is that the distance from the source vertex to a target vertex can be computed as the minimum distance from the source to any of the target's neighboring vertices, plus the weight of the edge connecting the neighbor to the target. Therefore, the state transition function for the Bellman-Ford algorithm can be expressed as:
Answer(A: [+]
min (Answer(k: JET(E)
1][] + w/ ()])()),
where Answer[ki]t [i] represents the length of the shortest path from the source vertex to node at the k-th iteration, T(i) (i) denotes the set of in in-neighbors of node i, and w[i][t]] denotes the weight from node j to i. The aggregation function g(r, y) is implemented as min(2, y) as we try to find the shortest path.
This problem defined as, given a set of cities and the distances between every pair of cities, finding the shortest possible route that visits every city exactly once and returns to the starting point. If we regard the set of already visited city S ending at i-th city as the current state, then states that can transfer to current state are those that ending city can reach k. Therefore, the state transition function for the TSP problem can be expressed as:
Travelling Salesman Problem (TSP):
Answer[k][[[[[]
min (Answer(k- 1] \ {i)] + w: wi]l) jES
where [[]] represents the cost of the shortest tour that visits all the cities in the set S and ends at the i-th city, the aggregation function g(r, y) is still implemented as min(x, ar, y) since we aim to find the shortest path, and [i]][i] denotes the distance from city j to city i.
D.2 Proof of Theorem
Assumption 1.
Each function f.g in (2) can be approximated by constant size MLP.
Assumption 2. The aggregation function in (2) is one of min, max, sum, mean,
The first assumption is mild as MLPs are universal approximators. The second assumption is mild because these are the most commonly used aggregation functions.
Theorem 3. (Expressiveness) Assume the input format is given in (1) and f.g, O in DP update (2) satisfy the assumptions 1 and 2. There exists a log-precision constant-depth and constant-widue Transformer that simulates 1 steps of DP update in (2), As consequence, there exists a log-precision -eeph and constant-widf Transformer that simulates steps of DP update in (2).
Proof. Token Embedding and Positional Embedding: The ttree-dimensional token embedding includes the token type evell (0 for answer: 1 for node; 2 for edge cost), refined token type enyee) (0 for answer, for the node tokens initial states, for the target node tokens the edge list, 3 for the source node tokens in the edge list, 4 for edge cost), and the token id eooen (from 0 to
|VI - 1). The two-dimensional positional embedding includes the embedding for initial state tokens
eposl (0 for edge list tokens, 1 for the first two elements of initial states, for the second two elements
25

---

of initial states, etc.), embedding for edge list tokens e (0 for initial state tokens, 1 for the first three elements the edge list, for the second three elements of the edge list, etc.). There are also constant-dimensional placeholders to put the states of DP.
Block 1 Initial State Broadcast: The goal of the first block is broadcast the initial states from the initial state token to node tokens. (1) Use MLPs to recover the digits of the answer tokens and put them in the first placeholder if &
type = O: (2) Copy the first placeholder from answer token to its previous
node token by using COPY in Lemma and setting Sk [ji(e post )² 6): (3) Broadcast the first placeholder with SUM in Lemma and setting S₁: = (il(c typel tpply j2 + (cf (etakon ejoken )² < 6).
Now the state for every node token u, is [e!ypel, etyp22 e token e e Answer[0][u]]]]
The goal of the second block is to copy the edge features from the edge feature token to the corresponding node tokens. (1) Use MLPs to recover the digits of the edge feature tokens and put them in the second placeholder ebyel == 2; (2) Copy the
Block 2
Edge Feature Operations:
second placeholder from the edge feature token to the node token by using SUM in Lemma 1 and
setting Sk [il(ch E
22 )² < <d). Now the state for every node token u, of the i-th edge is [etsel, e.yp22, etoken ctoken cpos), cPoo2 Answer[O[[u:]] c(uu][us]]
Block 3 Message Preparation: (1) Use MLPs to compute g and place the results in the third placeholder. Now the state for every node token u, of the i-th edge is [etree e.yec, eloken ,eoos] epos2 Answer [0] [
(2) Use MLPs to clean Sop the first and second placeholder. Now the state for every node token u, is [etyel ebype, eloeen ePost epos2 .9( [[AAswer[[]] [u]] clus][]]]]
clus][[ss]]:
The goal of the fourth block is to compute O and f. (1) Use one or two attention heads (one for max, min, mean aggregations, and two for sum aggregations) to perform the aggregation operation. This achieved by using MEAN or MAX or SUM for the first placeholder and setting S₁ = (il(et ei elokeay2 22 + (elype2 - e2pe222 < 8). Now the state for every node token un is [elypel, ,buee,, eluken epust e e (2) Use MLPs to compute f. Now the state for every node token is [etyee, ,etVee2, etnken epos) ,e "F(e,,7
Block Message Passing:
c(u,][u;)))
After four blocks, the final state for every node token us is given by [ebre1 etypc2, etoken epost epes2 Answer[]][u]]] Answer(k[[[u] can be obtained by repeating
the above four blocks & times.
Lemma 1. [12] Let n E N be an integer and $1, In be a sequence of vectors where I; (āe, ri. 1) E [- M,, Mf d+2 where M is a large constant. Let K, Q,V V E Rd (d+2) be any matrices with [ oc $ 1 and let p, 8 < M be any real numbers. Denote qi Qæ, kj K Dj
Væy. Define matching set S [0,l ky S p}. Define two following operations
COPY: The output is a sequence of vectors u1, " with u; Upos(i)) where pos(i) arg maxjes; Tj.-
MEAN, MAX, SUM: The output is a sequence of vectors ui Uh where u, -jEs, 0i
and D is min or max or sum or mean.
Specifically, for any sequence of vectors F1, 22, ... Lnn denote the corresponding output of the attention layer 01, O2.............................. ,0,- Then, we have Iuu. 0illso I for all i E [n] and S + D.
D.3 Permutation Invariance Test of LLMs
We test whether LLMs respect the permutation invariance property in graph problems and the results are given in Figure 5.
D.4 Proof of Propasition!
Proposition 2. Assume the input format is as described in Equation (1) and that the attention mechanism is limited to attending to constant number of tokens. There exists at least one instance
26

---

8 An undiracted graph with odge list: [[4, 1], [1, 21, I2, 31, [3, 01, 14, o, [2, 01, [4, 31, 12, $]. [5, 6]. [6, 71. [5, 8J, What is diameter of this graph? Only provide concrele number.
0
3
An undirected graph with edge list: [10. 2), [2, 3). [3. 4). [0. 43, 12, 4j. (o, 3j. 12, 5). [5. 6). 7}. 8), the diameter of this graph? Only provide conerete number.
An undirected graph with edge list: [10. 4]. [4. sj. [S. 3J. [3. 11, [o. 11, [5. 11. [0, 2]. (2, 6].
8[]-
8]].
8). 8j. (2. SjJ. What is the diameter of this graph? Only provide a concrete number.
Predicted diameter distribution
Predicted diameter distribution
Predicted diameter distribution
GPT-4-turbo
3
NA
Mistral-7B
Figure 5: Illustrative Examples of LLMs Failure to Solve Graph Computational Problems under Permutation (i.e., node re-odering). Experiments were conducted for 30 times.
of one-step DP update such that no log-precision constant-width constant-deph transformer can simulate.
Proof. We present a proof by contradiction. Assume that token in a Transformer with a constant depth, constant width, and log-precision can attend to only a constant number of nodes. Under this assumption, the total information accessible to the token in such Transformer architecture amounts to Ollog n) bits. However, for graph with [V] nodes, the number of possible outcomes from executing one-step DP is (eelV),, necessitating @(V) ] bits for representation. By the pigeonhole principle, this scenario inevitably leads to at least two distinct DP outcomes being represented by the same output sequence generated by the model, thereby constituting contradiction.
D.5 Proof of Theorem
Theorem 4. (Spurious correlations of auto-regressive loss) Assume (1) the loss employed is a next- ooken-prediction loss utilizing cross-entropy, applied to the sub-sequence U1 02 ... during training: (2) the output logits are determined by target node and the current node 1/-1- Let Ne u. be the number of times the training dataset such that is the target node, V;-1 is the current node and is the next node. The optimal logits for predicting the next node from current node U;-1
towards target node is given by 0; 0:[u]] =E. "..N N2.
Ne.0
i No No > 0. If Ne O,
é [u] can be any non-negative number subject to E. 0; [u] 1.
Proof. We denote D the training dataset, I.j the sequence length of the i-th sequence in the dataset, Vijj as the one hot emhedding of the j-th token in the i-th training sequence, and ūig.u as the w-th logit the j-th token in the i-th sequence. The cross-entropy loss is given by
Vigau log Di.j.M
Lumnn m log Di.j.M
(a)
Σ Σ 1,
Ne log ū.jj.
(E[ID]] j=4
EE( jm4
N N. Σ,, Ne,
Σ
NNen Nenyy
log Rijj.
where (a) uses the assumption that the output logits are determined by target node and the current node U;-1- In (b), we assume that Σn, Ne, O. The cross-entropy is minimized when
If En, Ne,, n.a O, then the corresponding logits will not affect the loss Úijj. E. Ne
No
function and ū.j take any number.
27

---

User Request
User Request
2
Task Graph
Task Assessment
Strategy: Croedy Adugiive Beam
the color red cars to blue in "example.jpg jpg" label the objects, and classity
Alter color red cars blue in "cxample jpg" label the objects, and classify the
Stept Edit the based
LLM
+
Image Ediing
Image
Step2 Detect objects image
LLM
Object Deteation
Imange Segmentation
Casstiiclion
LLM
1 LLM
Step Perforn tolen classilication on
LLM
Chasiflcution
Summariration
Traniation
Decomposed Steps
Invocation Parh
Image Ediiing
Step lidi the image based on the given sexr
All Searched Paths ("Imago Editing" "Ghgect
Path Selection
Image Editing
Object Detection
Step Detect objects the iillage
I"lange Eaiting"
Detection" ; "Token Classiiction")
LLM
Detection
Tokest
Step
classification
3
Tokes Clasilliution
Direct
(b) GraphSearch
Figure 6: Illustration of LLM'' Direct Inference and GraphSearch Method.
E
Supplementary Materials for Training-free Methods
E.1
Implementation of Baselines
In this subsection, we present the implementation details of training- feienng-ffre baselines, including LLM's direct inference, GraphSearch, and ours SGC. Method illustrations are shown in Figure
LLM's Direct Inference: The prompt template for LLM's direct inference is given in Table 4. During experiments, uniformly apply 1-shot in context learning for LLM's direct inference of task invocation path. For open-sourced LLMs, the temperature parameter is set to 0.2.
The prompt template for GraphSearch is given in Table 5. This algorithm conducts an iterative search on the task graph to identify an optimal task invocation path that can best satisfy a given request. In each iteration, the neighbors of the last selected task considered candidates. These candidates are evaluated by LLM for their suitability for the current step (Task Assessment). The search process follows depth-first approach. After the task assessment in the final step, of potential invocation paths is generated. Subsequently, LLM is prompted to select the most appropriate path from these options (Puth Selection). The GraphSearch algorithm is implemented in three distinct variants, each employing a unique task selection strategy:
GraphSearch:
GreedySearch consistently selects the task node with the highest score at each step. Although fast and simple, this approach can lead cascading errors, resulting degraded performance.
AdaptiveSearch selects tasks with scores above a fixed threshold, adjusting the breadth of the search space in an adaptive mode. During experiments, we empirically set the score threshold
BeamSearch retains the top-k tasks based the LLM's assessment scores within candidates. Beam search can expand the search space but slightly reduces the efficiency. We uniformly set the beam width 2.
Ours SGC: Regarding the choices of LM backbones, for integrating GPT-3.5-turbe and GPT-4-turbo with SGC, the Roberta-355M [40] serves as the text encoder. For all other datasets and LLMs, the e5-335M [62] configuration is employed.
E.2 Results All LLMS
Table 8 supplements Table with other LLMs. The proposed methods perform consistently better.
28

---

Table 8: Comparison of Training-free Approaches: Overall Performance (Node-F1 and Link-F1 in %) and Token Consumption in x 10"
TaskBench Multimedia I-F]
RestBench TMDB
LLM
Method
HuggingFace
Daily Life I-F]
n-F1
I-F1
Tok
R-F1
n-F1"
TTkk
R-F1
[-F/
#Tok
1.96
Baichuan2 13B
AcaptiveSearch
GrardyySearch
39.30
30.58
10.41
4.89
10.81
6.42
33.24
18.74
9.22
4.45
11.17
5.69
15.60
34.39
12.73
1.61
16.71
5.91
22.5
30.33
10.00
2:98
3.62
8.71
BeamSearch
24.69
SGC
56.75
62.31
36.69
Direct
50.46
21.27
2.50
53.57
23.19
2.64
73.70
45.80
3.82
44.66
14.01
2.02
Vieuna 13B
Seapt
GreedySearch
$2.94
25.73
6.23
46.99
23.11
5.55
42.98
13.53
7.18
41
45.
13.69
7.02
3.42
BeamSearch
56.64
26.93
24.11
$4.09
26.19
25.42
54.55
23.60
24.86
46.91
15.41
7.79
SGC
59.62
31.98
2.31
61.78
37.66
2.43
83.33
63.77
3.82
48.79
15.99
1.89
3.82
1.91
Cade
7B
AdaptiveScurch
Gruooly-eurchh
BeamScarch
60.34
60.12
58.71
33.
31 16
31.36
17.95
6.84
64.12
62.32
62.83
38,99
36.81
21,448
5.35
5,50
83.25
82.51
83.42
64.15
63.48
24.48
7,83
7,088
65. 65.37
64.60
10.64
40.50
42.60
5,00
5.78
3.12
67.04
87.73
Direct
60.60
30.23
2.49
69.83
39.85
2.64
84.26
53.63
3.77
62. 63.23
22.02
1.96
Mistral 7B
AdaptiveSearch
GreedySearch
67.30
65.91
38.
38.90
6.52
7.68
71.59
58.92
44.84
34.72
6.26
75.18
86.39
63.65
493.47
10.92
8,22
54.04
60.044
21.35
23.18
9.99
4.38
HeamSearch
67.13
25.66
73.55
47.12
31.10
39.16
26.79
11:26
SGC
67.43
42.08
2.32
74.07
49,90
2,43
87.13
66.49
3.54
64.72
25.67
1.89
Direet
57.55
28.88
2,45
68.57
11.79
2.59
91.20
76.07
3,88
68. 91.91
43.74
2.02
Cade 13B
Sduptiveeerchh
SrachySearch
60.85
31.66
11.10
68.14
41.71
6.77
91.34
76.09
5.54
7.18
63.74
37.17
8.16
BeamScarch
62.65
34.31
20.14
69.55
13.35
19.51
91.74
76.60
19.19
68.08
12.92
8.88
SGC
65.51
39.44
2.31
73.32
53,28
2.43
92.96
79.57
3.64
71.40
47.55
1.90
Dircet
73.85
45.73
2.14
82.85
2.26
96.09
3,36
81. $1.70
57.55 52
1.67
3,5-turbo
GPT-
AdaptiveSeurch
GreedySSeach
Beam/Sarch
72.18
67.75
47.55
43.88
5.29
7,47
81.86
81:11
63.00
62.71
4.92
5.71
93.77
93.79
81.41
81.26
8.53
7.36
76.
77.57
53. 65
50.11
3.06
5.89
96.38
86.19
3.16
Direct
77.60
52.18
2.19
88.29
69.38
2.28
97.36
84..5
3.37
82.56
56.67
1.75
GPT: 4-turoo
SeaptiveSearch
GreedySearch
74.75
50.44
5.78
86.81
69 80
97.36
85.78
7.37
9.04
75. 35.34
49.95
3.73
ReumSearch
77.56
$2.54
8:98
16
70.39
6.90
97.35
85.78
8.99
80
51.00 .00
5.18
SGC
77.79
52.20
2,03
88.54
69.83
2.10
97.35
85.76
3.16
82.27
56.37
1.62
Table 9: Results of Supplementary Metrie: Accuracy (%) for Training-free Methods on Bench.nch. Accuracy if predicted tasks match the ground-truth task set, and otherwise.
1IM
Method
HoggingFace
Multimedia
DailyLife
LLM
Method
HuggingFace
Multimodia
Daily Life
Direct
8.72
11.20
24.43
Direct
15.00
15.19
47.69
Vicuna
13B
GraedySaachh
AdaptiveSearch
BeansSearch
12.58
9.34
Cudel
AdaptiveSeunch
Gradly
BeanSearch
16.20
17.90
21.10
45.07
SGC
16.02
20.12
42.17
SGC
21.20
29.32
55.33
Direct
16.36
25.05
44.53
Direct
14.29
24.10
66,40
Mistral 7B
AdaptiveSearch
GreedySearch
21,88
20.45
36.90
16.02
29.22
49.32
CodeL 13B
AdaptiveSearch
GreedySearch
17.30
19.11
24.10
24.90
67.00
66,80
BeunsSaarc
29.36
BeamStarch
67.20
SGC
22.54
Dircet
Direct
35-turbo
GPT-
AdaptiveScurde
GreeyySeuch
BeamSSarch
32.03
29.35
26.00
52.47
51.61
74.59
80.87
73.17
GPT- 4-turbo
AdaptiveSeurch
Gredyy Search
BearSrurch
33.26
33.68
33.47
61.57
61.17
86.57
86.77
SGC
32.44
51.61
83.13
SGC
34,09
60.97
86.77
E.3 Accuracy Results of Training-free Methods
Due space limitations, we present only the Node-F1 and Link-F1 scores for training-free methods in the main text. Here, we provide the Accuracy results in Table 9. These results show that integrating SGC significantly enhances accuracy across different LLMs on all datasets, making previously unsolvable planning scenarios manageable and successful.
E.4 Computational Cost Analysis
In this subsection, we present a comprehensive efficiency study on inference time of training-free methods and results are shown in Table 10.
29

---

Table 10: Computational Cost Analysis of Training-free Methods. Due to space constraints the table, some LLMs are abbreviated such as "GPT-3.55" for "GPT-3.5-turies
Inference Times Comparison on HuggingFace (Seconds)
Method
Baichuan
Vicuna
CodeLlamm--78
Mistral Came 13B
GPT-3.5
GPT-4
Direct
6.0
3.6
10.9
4.5
9.7
2.7
26.1
SeachyySearch
30.7
45.7
23.1
109.8
29.1
7.4
S5.6
AdaptiveScarch
50.2
79.4
27.2
28.2
52.4
9.4
87.0
BeamScarch
102.0
55.0
60.8
92.3
14.9
270.2
SGC
3.7
10.7
9.5
3.0
24.4
Inference Times Comparison on Multimedia (Seconds)
Direct
3.3
13.2
14.6
2.9
25.1
SeachyS
52.3
54.3
37.0
109.7
9.9
8.8
52.2
AdaptiveSearch
98.1
142.5
25.7
41.6
25.6
9.6
84.2
BeamScarch
122.3
69.8
103.0
92.0
84.4
15.0
70.9
SGC
9.5
3.4
12.9
4.5
14.1
3.1
23.5
Inference Times Comparison on Daily Life (Scconds)
Direct
10.0
6.5
19.4
5.6
18.6
3.4
31.0
GreedySearch
62.7
49.8
29.3
198.3
37.6
13.2
124.3
AdaptiveSearch
133.3
97.6
30.5
69.1
45.5
16.5
209.0
BeamSearch
196.9
54.1
106.9
195.9
64.9
89.4
161.7
SGC
6.5
18.6
17.9
3.6
29.5
Open-sourced LLMs were deployed local API services using the FastChat framework on single A100-80G GPU. This configuration enables faster and parallel inference. Under this setup. LLM's direct inference requires 3-15 seconds per request. GPT-3.5-turbe and GPT-4-turbo are accessed via API, with the latter generally requiring more time. GraphSearch requires several minutes to complete a request due to its exhaustive search on task graph, impacting the efficiency. In contrast, SGC achieves comparable efficiency to LLM's 's direct inference, as it requires only a single LLM query and both LM and SGC's forward propagation processes are extremely efficient (typically completing within seconds). Note that some discrepancies in reported times, such Mistral-7B's s GreedySearch taking longer than other modes, may be attributed to variations in the deployment across different A100 services.
30

---

the positive User Request
Training (Optional)
Poritive Task
red
Imagoto-Test
curs to blue "example.jps" label the objects, and classify the labels.
Extrett text from image fiee "imagt.ipe" Stop Description
LM
GNN
LM
Text-io- Emuge
Negatiive
LLM S
3
4
Step EAt mhe Image bowed on given lest
GNN
Image Editing
Decomposed Steps
Task Graph
Step 3 Fdir the image based on the given text
Step Detect objects the
Object Detoction
LM
Srop 2 Detect objects in the insge
Srap 3 Periinn token
Stop Perform token olassifcation on the
Token Classiliatiio
clasefication on deteeted labele
Figure 7: Illustration of GNN-enhanced Task Planning. First, LLMs interpret request into several manageable steps. Then, we leverage GNNs for task retrieval, sequentially matching each step description suitable task, finally generating the invocation path.
Supplementary Materials for Training-based Methods
F1 Implementation of Training- GNNs
LM and GNN Configuration: For training- GNNs, we uniformly use the e5-335M model [62] as the LM backbone. For the graph encoder, our setup includes single layer with hidden dimension of 1024. During the model training, we set the batch size to 512 and run for 20 epochs with learning rate of le 3. We use the Adam optimizer [25] and implement early stopping mechanism with a patience of 5 epochs to prevent over-fitting. All experiments are conducted on single NVIDIA A100-80G GPU.
From each dataset in TaskBench, we randomly select 3, 000 samples to create the trainset. The original data includes specific task steps and corresponding task invo- cation paths. Therefore, we first employ a topological sort to align each task step accurately with corresponding task, forming "<step, ground-truth task>" pairs. Then, for each pair, we randomly sample two negative tasks to constitute the "<step, positive task, negative task>" triplets for model training. These negative samples selected based on how textually similar they one, creating a robust differentiation challenge for the model.
Training Data Preparation:
Choices of Different Configurations: Our training- based model offers two configuration options: training only the GNN while keeping the LM frozen, or co-training both the LM and GNN. II- lustrations of these configurations are provided in Figure 8. The first configuration is designed to explore the GNN's capability in task retrieval. The latter leverages the LM's dataset-specific semantic embeddings to enhance performance. For the co-training setup, we use learning rate of 2e 5 and a training duration 10 epochs.
F.2 Implementation of TAPE and GraphToken
We adapt TAPE [16] and GraphToken [38] as saining-requicee basclines for task planning. Here, we detail the adaptation processes for each method.
TAPE:
To adapt TAPE for task planning, we reformulate the planning task as node classification problem, aiming to classify a user request into the appropriate task labels within the task graph. Firstly, LLMs interpret user requests by generating high-quality explanatory text, i.e., chain-of- thought reasoning, to understand each request. Then, fine-tuned LM encodes these chain-of chain-of-thought texts into latent embeddings. The fine-tuning process is based on pairs of textual descriptions and their corresponding ground-truth tasks. Finally, GNNs select the suitable tasks by leveraging both the generated text embeddings and the task embeddings. For fair performance comparison, we fine-tune the LM e5-335M and configure the GNN 2-layer GraphSAGE with hidden dimension of
31

---

Frozen
4 trainable
forward
backward propagation
Model Structure (Main Experiments)
Poshiiz Task
GNN
Imuge Texi
Extract text from the image file "image irs"
LM
BPR Loss
LM
Text-to- Ion-to--mmgee
Step Descriution
Negutiie Task
LM+GNN Co-trained Structure (Supplementary)
Plotther Took
GNN
Image-to-Tooe
LM
BPR
LM
image filo "image-jpe"
Step Description
Text-to-Image
Nogatbee
Figure 8: LM+GNN Configuration. We offer two configurations: only training the GNN while keeping the LM frozen (Table 1 1),, or co-training both the LM and GNN (Table 12).
1024. The training data for both the LM and GNNs are consistent, utilizing the same split of the training dataset.
For adapting GraphToken, we first encode the task graph G(V, X) by computing each node's representation by feeding its descriptive text into the pre-trained LM, e5-335M. Then, GNN transforms the initial node embedding matrix into H. The GNN configured as 2-layer GraphSAGE, with a hidden dimension of 1024. A mean pooling operation is further applied to the node embeddings to obtain the graph's overall representation as hG = Mean-Pooling( ()). Finally, both hg and the text embeddings of input instruction and user request are concatenated and fed into the LLM to generate the output planning result. During this process, the backbone LLMS are frozen, and only the GNN's parameters are tuned. For each dataset, we train over epochs using the same 3, 000 training samples consisting of <user request, ground ground-truth planning> pairs. The batch size is set to 16, with maximum input length of 512 and maximum output length of 300 for HuggingFace and Multimedia datasets, and 600 for DailyLife dataset. The learning rate is configured to le- 5.
GraphToken:
F33 Implementation of Fine-tuning LLMs
To explore the effectiveness of our proposed framework on fine-tuned LLMs, we employ Supervised Fine-Tuning (SFT) the CodeLlama-7B and Vicuna-13B models. We use the same set of 3, 000 samples from GNN training as the LLMs' fine-tuning data. In fine-tuning the LLM with LoRA [19]. we set the lora_r parameter (dimension for LoRA update matrices) to 8 and the lora_ alpha (scaling factor) to 16. The dropout ratio is set to 0.1, the batch size to 2, and we conduct training over 2 epochs with a learning rate of 1e 5. For HuggingFace dataset, the maximum input length is set to 800, while the maximum output length is 400. For Multimedia and Daily Life datasets, which contain larger number of tasks and require longer textual inputs, set the maximum input and output length to 1000 and 500, respectively. We utilize 2 NVIDIA A A100-80G GPUs for fine-tuning the LLMs..
E.4 Full Results of Training-baser GNNs
In Table 11, we present comprehensive results for all training- based GNNs, including GCN [26], GAT [57], GraphSAGE [15], GIN [67], and Graph Transformer [47]. To highlight the improvements brought by GNNs, we also include results from the strongest bascline, BeamSearch.
From the results, it is obvious that all GNN encoders significantly enhance the task planning abilities. For instance, when applied to Vicuna- 13B on HuggingFace dataset, the introduction of GCN results in a performance improvement of 17. 73,, GAT contributes to 17.48% increase, GraphSAGE leads to a 22.59% boost, and GraphTransformer improves predictions by 18.0%. This conclusion can be generalized across various LLMs and datasets, demonstrating the robust capabilities of GNNs.
32

---

Table 11: Performance of training- based GNNs. We also presents the results of BeamScaerch. the strongest variant from GraphSearch method to provide a comprehensive comparison. All GNNs consistently enhance task planning performance across diverse L.MMs, showing the effectiveness.
HuggingFace Tools
Multimedia Tools
Daily Life APIs n-F1*
LLM
Method
n-FI1
I-F1 f
n-F1
I-FI f
I-FI
Direct
45.85
19.00
47.57
4.08
33.45
9,52
BeamSearch
41.06
9.59
32.24
9.09
36.18
13.18
GCN
57.67
31.47
55.51
30.16
62.11
37.05
Baichuan-13B
GAT
57.74
31.87
54.95
29.24
62.11
37.05
GraphSAGE
59.32
34.36
56.15
31.60
65.18
40.49
GIN
57.38
31.17
55.08
30.04
62.11
37.05
GraphTransformer
59.15
34.36
56.06
31.12
64.52
40.14
Direct
50.46
21.27
53.57
23.19
73.70
45.80
BeamSearch
56.64
26.93
54.09
26.19
54.55
23.60
GCN
59.46
33.14
62.48
38.89
83.05
62.95
Vicuna-13B
GAT
59.28
33.39
62.96
39.24
83.05
62.95
GraphSAGE
61.86
35.68
63.71
39.88
86.07
67.63
GIN
59.14
32.33
62.61
38.82
83.05
62.95
GraphTramen GraphTransformer
59.57
33.47
63.32
39.38
85.41
66.28
Direct
58.06
29.39
59.44
30.83
84.12
62.89
BeamScarch
60.34
31.36
64.12
38.99
83.25
63.48
GCN
65.07
40.50
67.46
45.84
87.23
69.27
CodeLlama-7B
GAT
65.20
40.93
67.41
46.46
87.23
69.27
GraphSAGE
66.67
43.03
67.97
46.31
88.53
72.02
GIN
65.52
40.98
66.89
45.41
87.23
69.27
GraphTransformer
65.83
42.58
68.90
47.20
88.36
71.72
Direct
60.60
30.23
69.83
39.85
84.26
53.63
BeamSearch
67.13
36.73
73.55
47.12
85.87
61.53
GCN
66.54
40.74
73.34
50.76
86.39
65.49
Mistral-7B
GAT
66.77
40.74
73.36
50.20
86.39
65.49
GraphSAGE
68.12
43.09
75.51
52.94
87.51
66.57
GIN
66.69
40.79
72.89
50.44
86.39
65.49
GraphTrrnsformer
68.26
43.08
73.80
51.45
88.25
67.84
Direct
57.55
28.88
68.57
41.79
91.20
76.07
BeamSearch
62.65
34.31
69.53
43.35
91.74
76.60
GCN
66.22
41.05
72.99
52.18
91.83
77.88
CodeLlama-13B
GAT
66.29
41.28
74.08
53.56
91.83
77.88
GraphSAGE
67.30
42.41
74.93
54.52
93.84
80.38
GIN
66.40
40.89
73.62
53.15
91.83
77.88
GraphTransformer
66.70
42.07
74.72
54.10
93.81
80.44
Direct
73.85
45.73
82.85
62.07
96.09
83.65
BeamScarch
75.51
49.62
83.57
64.50
95.66
82.72
GCN
76.93
51.43
84.92
65.05
96.38
86.15
GPT--35-turbo
GAT
75.63
49.36
84.77
65.48
96.38
86.15
GraphSAGE
77.90
52.68
85.29
65.80
96.43
86.26
GIN
76.86
51.00
84.14
64,30
96.38
86.15
GraphTransformer
77.61
52.30
84.21
64.32
96.38
86.19
Direct
77.60
52.18
88.29
69.38
97.36
84.58
BeamSearch
77.56
52.54
88.16
70.39
97.35
85.78
GCN
77.01
50.49
88,56
69.60
97.10
85.22
GPT-4-turbo
GAT
76.41
49.66
88.43
69.52
97.10
85.22
GraphSAGE
78.76
52.53
88.63
69.65
97.34
85.67
GIN
77.74
51.02
88.05
69.13
97.36
84.58
GraphTTransformer
78.47
52.17
88.07
68.71
97.32
85.57
33

---

Table 12: Performance of Training-hased GNNs under the LM+GNN Co-trained Mode. Simul-
taneous training of L.M and GNN yields significant performance improvements.
HuggingFace Tools
Multimedia Tools
Daily Life APIs
LLM
Method
n-FIt
I-F1 f
n-F1
I-FI f
n-F1 f
I-FI
Direct
45.85
19.00
47.57
4.08
33.45
9.52
SGC
60.97
36.12
56.02
31.36
64.84
40.00
GCN
60.68
36.31
57.82
32.87
64.73
38.92
Baichuan-133
GAT
60.39
35.37
57.24
32.19
64.46
40.14
GraphSAGE
59.76
35.59
57.97
33.29
63.21
38.10
GIN
60.31
35.82
56.62
31.53
63.55
38.19
GraphTransformer
60.76
36.82
56.82
31,40
64.88
40.23
Direct
50.46
21.27
53.57
23.19
73.70
45.80
SGC
64.40
38.97
65.12
41.63
84.74
65.90
GCN
62,06
35.49
65.02
40.63
85.22
66.93
Vicuna-13B
GAT
63.06
36.97
64.58
40.30
85.63
67.11
GraphSAGE
62.82
37.04
65.89
42.18
84.23
65.44
GIN
62.09
35.33
64.44
40.67
85.31
66.83
GraphTransfone Transforrrr
62.11
36.01
64.57
40.17
85.42
66.55
Direct
58.06
29.39
59.44
30.83
84.12
62.89
SGC
67.47
43,58
69.61
48.24
87.98
70.63
GCN
67.03
43.24
69.33
47.60
87.88
70.40
CodeLlama-7B
GAT
67.12
42.96
68.62
46.17
88.59
71.64
GraphSAGE
67.19
42.94
70.00
48.28
87.81
70.20
GIN
66.62
42.34
69.00
47.72
88.45
71.53
GraphTransformer
67.12
43.08
69.27
47.96
88.43
71.59
Direct
60.60
30.23
69.83
39.85
84.26
53.63
SGC
69.04
44.22
76.09
54.91
87.58
66.70
GCN
67.72
43.02
76.79
54.90
87.87
67.13
Mistral-7B
GAT
67.54
43.56
76.26
53.94
87.86
67.30
GraphSAGE
67.61
43.14
76.96
55.46
87.61
66.75
GIN
68.95
43.97
76.47
54.95
87.75
67.07
GruphTransfomne
67.94
43.52
77.06
55.39
87.76
67.00
Direct
57.55
28.88
68.57
41.79
91.20
76.07
SGC
70.14
45.20
75.65
55.45
93.45
79.89
GCN
69.39
45.18
76.03
55.22
93.38
79.74
CodeLlama-13B
GAT
69.68
45.57
75.24
54.99
94.06
80.96
GraphSAGE
68.92
44.85
76.28
55.41
93.30
79.51
GIN
69.01
44.76
74.72
53.91
94.24
81.23
GraphTransforme
69.52
45.68
75.46
55.14
93.98
81.06
Direct
73.85
45.73
82.85
62.07
96.09
83.65
SGC
77.87
52.86
85.95
66.95
96.39
86.16
GCN
77.72
52.58
85.84
66.92
96.33
86.06
GPT-3.5-turbo
GAT
77.49
52.30
85.81
66.97
96.38
86.15
GraphSAGE
77.87
53.04
85.51
66.56
96.34
86.09
GIN
77.73
52.36
85.63
66.69
96.38
86.19
GraphTransformer
77.78
52.79
86.09
67.26
96.33
86.06
Direct
77.60
52.18
88.29
69.38
97.36
84.58
SGC
78.44
52.84
89.09
70.52
97.38
85.85
GCN
78.33
$2.75
89.00
70.24
97.34
85.67
GPT-4-turbo
GAT
78.37
52.43
88.99
70.48
97.32
85,56
GraphSAGE
78.49
52.62
88.80
70.25
97.42
85,80
GIN
78.45
53.07
88.74
69.84
97.42
85.80
GraphTTransformrr
78.30
52.27
88.90
70.24
97.42
85.80
34

---

F,5 Performance of LM+GNN Co-trained Mode
During our main experiments, the LM backbone remains frozen while only the GNN is trained to automatically learn the alignment between implicit step descriptions and suitable tasks, facilitating task retrieval. In this subsection, we conduct a supplementary study where the parameters of pre-trained LM are also tuned along with GNN during model training. The model configuration is illustrated in Figure 8, and the results are presented in Table 12.
The results demonstrate that, compared to the GNN-only tunable mode, co-training LM+GNN can lead to further performance improvements. This enhancement occurs because the language model acquires task-specific semantics, which makes the representations more discriminative and boosts the GNN's effectiveness task retrieval. Additionally, it is noted that under the co-training setup, the differences between various GNN encoders are relatively minor, with performance variations across GNNs for specific LLM on any dataset remaining within 2%.
F.6 Computational Cost Analysis
In this subsection, we provide the computational costs of training-based methods: training time for GNN or LM+GNN co-trained, and resources needed for fine-tuning LLMs. Results are shown in Table 13.
Table 13: Computational Cost Analysis Training- basedd Methods. We present total training times for both GNN and LM+GNN co-trained modes, and resources needed for fine-tuning LLMs.
Training GNNs
Time (Seconds) Multimedia
Mode
Configuration
Parameters
HuggingFace
Daily Life
GCN
1,049,600
136.5
136.1
237.7
GAT
1,051,648
136.9
151.8
237.8
GNN-only
GrE
2,098, 176
134.2
149.8
233.8
GIN
2,099,200
134.2
134.9
233.6
GraphTransformee
4,198,400
135.0
150.2
233.7
LM+SGC
145.191.889
743.1
323.3
384.7
LM-GCN
191,491
482.8
567.8
384.2
LM+GNN Co-trained
LM+GAT
336.193.536
741.3
812.3
384.4
LM+GraphSAGE
337.240.064
741.2
406.8
381.7
LM+GIN
337,241,083
735.6
361.8
382.9
AM-GrrphTTrassfomm
339,340,288
741.0
362.7
405.8
Fine-tuning LLMS
Device Time (Hours) Multimedia
LLM
# Param (# Trainable Param)
HuggingFace
Daily Life
Codel Jama-7B
7742,740,992 194,304) 13.022.417.920 (6.553.600)
2x 7.0
x 110 13.8
2x A 100 9.5
Vicuna- 13B
1xA100 17.8
2xA1000 10.3
Ax00 19.0
Efficiency of Training GNNs: During experiments, each dataset shares the same GNN configuration: 1 single layer with hidden dimension of 1024. Therefore, for each GNN, its number of parameters remains consistent across datasets. The parameter scales for GNN variants range from 1M to 4M, and the total training time for each dataset requires only 2-4 minutes, comparable to the time taken by GraphSearch to fulfill a single request. For LM+GNN co-trained mode, where e5-335M [62] serves the LM backbone, training times increase to approximately 6-12 minutes. In summary, both modes demonstrate high efficiency, with total training times spanning minutes, showcasing their ability rapidly adapt
task planning scenarios.
Efficiency Fine-tuning LLMs: Fine-tuning LLM with 3, 000 training samples over 2 epochs requires huge time, typically 10-20 hours or two A100-800 80G GPU devices.
35

---

G
Experiments on Task Parameter Prediction
To assess the quality task planning, we primarily focus on the predicted tasks and their dependencies, leaving the parameters for invoking these tasks undiscussed. As LLMs' direct inference for solely predicting tasks has proven unsatisfactory (Figure 2), relying on LLMs alone to directly predict these parameters is unreliable. In this section, we will first demonstrate that it is quite straightforward for LLMs to fill in the parameters given a planned task sequence, which is a simple extension of our framework. Furthermore, we will empirically show that with more accurately planned tasks, i.e., those retrieved by GNNs, LLMs can intelligently fill in the parameters.
G.1 Prompting LLMs to Fill in Parameters
Recall that our framework enables more accurate invoked task sequences, e.g. fei...... b for a specific user request. To finalize the invocation sequence, just adding an additional LLM query can complete the invocation parameters for each task. Specifically, by providing the original user request, planned tasks, and detailed descriptions including each task's input and output requirements, L.LMs can be intelligently prompted to fill in the invocation parameters for each planned task, resulting in well-structured invocation sequence ready for execution. Prompts are provided Table
Process:
Example: Taking the request shown in Figure I as an example, which is: "Please generate an image where a girl is reading book, and her pose the same as the boy 'example.jps jpp'. Then, please describe the new image with your voice." Suppose GNN's planned tasks include { Pose Detection. Pose-ta Image, emage-to-Tess
text-to-Speece }. LLMs can intelligently fill in the invoca- tion arguments as follows: [ ("task": : Pose Detection, "arguments": ['example.jpg' ), f"task": Pose-to- Image, "arguments": [output pose from Pose Detection] }, ("task": Image-to-Toe Text. "arguments": [output image from Pose-to- tasage) 1, "ttask": Bext-to-Speen "arguments": [output text from
G.2 Empirical Results of LLMs Predicted Parameters
We conduct this supplementary experiment on the HuggingFace dataset from TaskBench [45]. Specifically, we compare the directly predicted invocation parameters from LLMs (denoted as Direct) with the parameters filled automatically by LLMs using our GNN-retrieved tasks (querying prompt as shown Table 6). For GNNs, we consider both training-free ffee SGC and trauning-required GraphSAGE. Notably, with SGC, since the query for completing parameters also training- free, the entire pipeline can be deployed without any extensive model training or labeled data. We adopt evaluation metrics from TaskBench, including Parameter-Typp F1-Score (Param F-F and Parameter- Value F1-Score (Param v-FI). These metrics measure the accuracy of the predicted parameter types and concrete values, respectively. For example, when filling in the invocation for Pose Detection, the ground-truth parameter type is Image, and the ground-truth value is eexampl.. jpg'.
Experimental Setup:
Table 14: Performance (in %) of Task Parameters Prediction on the HuggingFace dataset
LLM
Method
[-/1
v-Flt
LLM
Method
1-F1 1
v-/1
Direct
38.77
18.56
Direct
44.62
33.24
Mistral-7B
SGC
18.13,19.6
39.64,2108
CodeLlama-I3B
SGC
57.74.1321
43.21 1997
GraphSAGE
59.07.20.30
41.40.2228
GraphSAGE
59.49.1487
45.54,
Direct
62.42
48.27
Direct
70.73
55.54
GPT-3.5-turbo
SGC
68. 13.13.577
54,34.6.7
GPT-4-turbo
SGC
72.91
58.02 58.02,2.4
GruphSAGE
71.19
56.83.8.5
GraphSAGE
73.09
58.20
Observation:
From the results shown in Table 14, we can conclude that: (1) LLMs' direct inference
of invocation arguments unsatisfactory. Even for the strongest LLM, GPT-4-turbo, the Parameter- Value Fl score is only 55%, which is far from expectations. (2) With accurate planning provided by GNNs, LLMs can leverage their inherent reasoning abilities analyze the context and correctly fill in the parameters. Across four LLMs, improvements of 3% to 23% can be observed, highlighting the advantages of GNN-enhanced planning. (3) Our method is well-suited for training- -free scenarios, as the tasks retrieved by the training-free SGC already enable LLMs to infer the parameters effectively. with only a minor performance gap compared to the trainingrrqquire GraphSAGE.
36

---

H
Case Studies
We show two cases in Figure 9 where the results of LLM's direct inference. BeamSearch, and GraphSAGE are compared. Due to space constraints and issues such as LLM's output content decoding errors or invalid paths, we present only the first four valid paths searched by BeamSearch on the task graph. From the cases, we can conclude that BeamSearch relies on LLM's inherent reasoning abilities. Although LLM can explore the ground-truth invocation path on the task graph, their final solutions are usually not the optimal as either containing the hallucination or wrongly invoked tasks due to limited instruction following and reasoning abilities. On the contrary, GNN can effectively align decomposed steps with suitable tasks, accurately achieving the ground-truth result and enhancing task planning.
Effectiveness of GNNs:
We also present the failure cases where GNN performance deteriorates compared to direct inference to provide a comprehensive discussion of our method. Our conclusion is that the method is sensitive to the quality of decomposed task steps, as an ambiguous step may mislead GNN to wrongly select the task, and such errors can cascade due the sequential selection of tasks the task graph. As the case shown in Figure 10, step 2 is ambiguously described as "Segment the image and identify the tabular data", which actually incorporates two distinct steps. This ambiguity causes GNN to choose the unsuitable Tabular Classi iffiiiiiiinnn instead of the correct Image Segmentation. Since tasks are selected sequentially on the task graph, where the next task is neighbor of the current selection, such error can prevent the exploration of the next appropriate task, as it may not be a neighbor of the current, incorrect selection. We also present the BeamSearch explored paths and its final solution, where it hits the ground-truth result.
Failure Cases of GNNs:
Diagnosing GraphSearch with GPT-44turbo: In our experiments, GraphSearch brings marginal or even decreased performance for GPT-4-turbo across most experimental datasets, contradicting current research [33, 32] which suggests that exhaustive search strategies can enhance the performance of more powerful LLMs. To provide a detailed analysis, we show three types of cases in Figure 11: Successful cases, Failure cases, as well as Maintaining cases:
Successful Cases:
As shown in the figure, despite inaccuracies in task decomposition (GPT-4 predicts an extra step compared to the three-step ground truth), its inherent reasoning abilities and the knowledge explored along the task graph can fix these mistakes, hitting the ground-truth.
Failure Cases: In the failure case, although GPT-4 identifies the ground-truth solution during searching process, the final decision includes an incorrect task. This occurs because the final solution selection demands complex reasoning abilities of LLM, as the context contains long textual information from different aspects: the full task graph, user request, all searched paths, and related instructions. The demanding context and reasoning challenge exceed GPT-4's capabilities, leading to errors.
These occur when GraphSearch merely replicates the result of LLM's direct inference, indicating added benefit from exploring the task graph. In these instances, despite navigating the graph, the LLM fails to self-correct inaccuracies due to inherent reasoning limitations.
Maintaining Cases:
We emphasize that the results of GraphSearch with GPT-4-turbo, tend to "maintaining" cases. Under such conditions, even a few failures can degrade overall performance, explaining why GraphSearch does not consistently enhance performance for GPT-4-turbo.
37

---

User Request
Convert the text "I love nature" into speech mudio, classify the audio. Finally, generate an image according to the audio classification result.
BeamSearchasnner
LLM
Direct
Scarched Paths
Final Solution
GraphSAGE
Test-to-Speech
Specete
Text-to-Sperch
Step f Conven the text "I love asture"
(eee-tt-SSpechh
Mistraie
Agtomattc Recognition
Automatic Speech Reoegnition
Audio Classiication
Automatic Speech Recognition
Step 2 Classify the generosed speech audio
Audio Classification
Step 3 insage besed classifcation result
Imsage Generstion
Text image
Feiling
Test Image
Editing
Imagee Generation
Text-to-lmage
text-to-Speech
Speech
Text-to-Speech
Step Generaae speech andio the ingurt lest
Text-to-Spnecch
Vieuma-133 13B
Audio C Classification
Speech Recagntiie
Audio Clussifiation
Classification
Stop Classily
Audio Classification
Step 3 Ginnennte an image based the classification
Audie-In-
Text-so Image
Transtation
Image
Trunsttioon
Text-to-Image
Text-to-lmage
have an English text "During summer, John loves to visit Eiffel Tower in Paris, France. He usually spends time taking pictures and eating ice cream at the nearby café.", would like key entities translated text, generate example image based those entities.
User Request
Spanish. Then, please identify
BeamSearch
LLM
Dircet
Searched Paths
Final Solution
GraphSAGE (Ours)
Translation
Translation
Translation
Step f Translate the from
Translation
Code Madeellama-133 13B
Named Fasiry
Recognition
Classiliationn
Summarization
Token Clessilication
Stop 2 Idcutify key entinies tranelated
SZZ
Classificarion
lext
Step Generate ecample imsgge
Text
Text Generation
Text Generation
Text
Text-to-llmag
Generation
Laiting
Lditting
ideniilied emitties
Translation
Trunslation
Translation
Step TTransate English Spanish
Translation
Mistral-77 7B
Named Entity
Token
Text Generntion
Named Recognition
Ilcatify entities
Token Classification
Recogrition
Stap Gieuratte an example image based the identified antition
Text-to-Image
Text Emert
Generatinn
Teststo-lmug
Image
Text-to-Image
Text-to- Imni-t
Figure 9: Case Study of GNN's Effectiveness. Nodes colored in pink and red denote wrongly predicted task or hallucinated task, respectively. Due space limitations, we only show the first four valid searched paths of BeamSearch for illustration. Even though LLM can explore ground-truth paths during searching, they lack certain instruction instruetion-oolloiing and reasoning abilities to consistently choose the optimal path. On the contrary, GNN can correctly align decomposed steps with suitable tasks, hitting the ground-trun result.
38

---

I have this image "example ipg", and the deseription is: change the color of the table in the image to bluc. After that, segment the image to identify the tabular data. Finally, classify the tabular data.
User Request
Direct Inference
GraphSearch
GraphSAGE (Ours)
Solution
Image Editing
Image Editing
Audio Classfication
Step Change the color of the table in the
Image Editing
ingut image
OZL
Tabular Classification
Image
Segmeniation
Segmeniation
Translation
Stop Segment the and ideatify rabular
Tabular: Classification
Tabular Classification
Tabular Classittation
Image Editing
Image Editing
Tabular Classification
Step Classidy the cabulaz data
Token Classitication
Figure 10: Failure cases of GNN. Our framework relies heavily on the quality of decomposed task steps. Ambiguous steps (step 2 which actually incorporates two steps) may mislead GNN to select the wrong task.
User Request
Direct
BeamSearch.idh-2
Searched Paths
Final Solution
have image file named
Image Classification
Image Classification
Image Classification
example.jpg jpg,
Success Case
know what the image is about.
Then, I want ask question "What color the main object in the image?", and finally, want check the similarity between the answer to the question and this sentence: "The main object in the image is blue."
IImage-to-Tex
Text Generation
Visual Question Answering
Question Answering
Visual Queation Answering
Visual Quesium Answering
Document Questien Answering
Queation Answering
Scutience Similarity
Santenee Similarity
Sentence Similarity
Sentence Similarity
Sentence Samilarity
Tabular Classification
Tabular Classification
Image-to-Tex)
Image-to- Text
Failure Case
have table image "example jpg" which is in French. need to classify the table, translate the output text to English and then compare its similarity this reference text. "This is important reference text."
Translation
Translation
Translation
Sentence Similanit
Sentence Similarity
Sentence Similurity
Similarity
Classification
Most Case (Maintain)
I would like to input an example image of streel view scene (example.jpg that contains multiple objects. Please divide the image into segmentss identify the objects, and generate images showcasing these detected objects separately.
Sepmentation
Image Segmeniattion
Imaage Editing
Image Segmentation
Objject Detection
Object
Object Detection
Image Segmeniation
Object Detection
Image-to- Image
Text-lo- Image
Image Editing
Text-to- Image
Objoct Delection
Image- to-Image
Image-to- Image
Figure 11: Diagnosing GraphSearch for GPT-4. provide three types of cases: Success Cases where GPT-4 can leverage inherent reasoning abilities to select the optimal invocation path, which may even fix wrongly decomposed task steps. Failure Cases where GPT-4 miss in the extremely long context, containing the whole task graph, all searched paths, and instructions, selecting unsatisfactory path. Maintain Cases where the searched result is the same as direct inference result, and those wrongly predicted tasks can still not be refined even under exhaustive search.
39

---

I Broader Impacts
In this paper, we did use any non-public data, unauthorized software, API in our paper, there are no privacy or other related ethical concerns. Similar to other models designed for autonomous agents, our model also has the unfortunate potential be used for malicious attacks. We pledge to restrict the usage of our model exclusively to the realm of research to prevent such misuse.
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims made in abstract and introduction truthfully reflect our contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
41

---

Justification:
Please see Appendix D.2 & D.5 where we provide detailed theoretical analysis.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We detailed all the experimental setups and implementation details in Section 5.1 and Appendix E. & F.I.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
42

---

Answer: [Yes]
Justification: Please refer to uploaded Supplementary Materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.cm cc/
mublic/guides Seriidde//odeeummissiisss.. swwssssssoooooooo oniooiopyyy ooiicylyyy))oo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //wpps.ccppuul////// ctcccc/pp.. wwtpccccpppccc.eec.cc.......cllt httpc///guiieesooeuuuuiiiiii /Ct////ooeeussiseeeeeeeeeee onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have specified all the data splits, hyperparameter settings, and model configurations both Experimental Setups in Section 5.1 and Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We follow existing studies to set up experiments, which does not provide the eгror bar. We can add the error bar if needed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
43

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Table 13 in the Appendix where we list the experimental devices and costed time.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / http///eurrpp.eeeee htcp/puuiic//thcccccceeeeeeoeeee
Answer: [Yes]
Justification:
We carefully follow the guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: specify them in Appendix Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "xl3KxkBWUK", "reviewer": "Reviewer_s7yo", "summary": "The paper formulates task planning as a graph decision-making problem. Through theoretical analysis, the paper shows the biases of attention and auto-regressive loss impede LLMs’ ability to effectively navigate decision-making on graphs. To mitigate this, the paper proposes to integrate GNNs with LLMs. Experiments demonstrate it can enhance overall performance.", "questions": "N/A", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a solid theoretical analysis of LLMs understanding graph-structured inputs, which is inspiring for future works.\n2. The proposed method is effective for task planning.\n3. The paper is well-written and easy to follow.", "weaknesses": "1. Combining LLM with GNN for graph-related tasks has been studied in many previous works and is not very novel.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for your insightful comments and recognition of this work, especially for acknowledging our theoretical contributions and superior performance.\n\n---\n\n\n> Combining LLM with GNN for graph-related tasks has been studied in many previous works and is not very novel.\n\nThank you for helping us to clarify this point. \n\nUnlike previous LLM+GNN works that often concentrate on text-attributed graphs or knowledge graphs, our research ventures into a new application, i.e., task planning for language agents. This area is gaining increasing attention with the development of LLMs [30,14,43]. Existing studies in this domain have centered around optimizing prompt designs for pre-trained LLMs. This paper initiates the exploration of graph learning-based methodologies within this area. Motivated by theoretical analysis, we propose a tailored approach to combine GNNs and LLMs for task planning, which demonstrates significant performance improvements over existing baselines. **We have also added experiments to show that the proposed combination outperforms existing LLM+GNN solutions [Ref A, B] in Table 2 of the PDF in the global rebuttal**.\n\n---\n\n[Ref A] He, Xiaoxin, et al. \"Harnessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning.\" ICLR 2024.\n\n[Ref B] Perozzi, Bryan, et al. \"Let Your Graph Do the Talking: Encoding Structured Data for LLMs.\" arXiv:2402.05862.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xEUpcdBChF", "reviewer": "Reviewer_ZJrg", "summary": "The paper proposes a GNN+transformers method to address some theoretical and practical issues in graph planning such as hallucinations. The task consists of matching a prompt that expresses a number of sub-tasks to a larger graph of tasks (the task pool) an agent (e.g., an LLM) can solve and invoke the right procedure to solve it (in the spirit of HuggingGPT).", "questions": "See each point in weaknesses, especially the third, fourth and fifth paragraphs.", "limitations": "See previous points.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The general problem is well formulated and the motivation behind GNNs to improve transformers on graph planning easy to follow. Section 3.1 (but not Figure 2) do a good job at describing the hallucination issue and the potential mitigations introduced by GNNs (my understanding is because they have grounded access to the true task graph).\nResults suggest that GNNs improve performance on task planning, both in training and training-free regime.", "weaknesses": "Figure 2 is problematic. It is never referenced in the paper and there is no reference to the dataset used and how the task is specified (I assume is the same setting as HuggingGPT, but just because it appears in the same section).\n\nI don’t follow the argument right after Eq. 3. Such representation may not be the standard representation of a graph, but it’s sufficient to fully reconstruct vertices and relationships (and is, in some cases, optimal, as pointed out by some works that you cite in the second paragraph of the introduction).\n\nWhile I understand Proposition 1 and its demonstration by contradiction in the Appendix, one can always choose a larger Transformer that could attend all the instances in the DP problem. Furthermore, you write that the information accessible by the Transformer is O(logn), with n left undefined (it is the number of tokens?), and compared to |V|, the number of nodes in the graph. It would help to use the same control variable for a comparison. \n\nI am not convinced by Theorem 1 and the following example 1. Despite a model never sees a path to d from a in the training set, that is not a proof (nor can be) that an LLM cannot interpolate (what some researcher in literature refers with the spurious term “emergent abilities”) from abc to bcd from other similar examples. As you correctly mention after Example 1, humans can concatenate abc and bcd. The ability to “correlate” can be learnt at training time by seeing different examples.\n\nIt is not totally clear to me, after reading the paper twice, how the representation of the GNN is combined with the LLM. That should be stated clearly and maybe integrated with Figure 1, which is not very illustrative. I’d like to see a formula that precisely describes the input of the problem (I guess a graph), how it is manipulated by the GNN and then fed to the LLM. I found an informal description of this step at lines 220-222, but I recommend to move that up in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for your insightful comments and recognition of this work, especially for the motivation to adopt GNNs in this new application. \n\n---\n\n> Weakness 1: Figure 2 is never referenced\n\nWe apologize for the confusion regarding Figure 2. The experimental settings are the same as HuggingGPT [31], using the HuggingFace dataset [30], and tasks are APIs on HuggingFace. We will provide a clearer caption and reference it in the revised manuscript.\n\n> Weakness 2: Representation of graph in Eq. 3\n\nThank you for helping us clarify Eq. 3. The edge list input format is a standard practice in works involving LLMs for graphs (e.g., [10, 41]). In existing studies, task graphs are often presented in Eq. 3, where the edge list is described by natural language and the initial states are the task descriptions of each task node, detailed in Appendix A.9 of [30]. Therefore, we adopt it as the basic graph representation for LLMs. \n\n> Weakness 3: One may choose larger Transformers and definition of O(logn)\n\nWe thank the reviewer for the meticulous review. In task planning, the use of pre-trained LLMs is common, but these models often have a fixed size, while the input graph size can vary. In studying the expressiveness of Transformers, it is typically assumed that the Transformer's embedding size remains constant relative to the problem size, as referenced in [Ref B]. Regarding the variable $n$, we define it as the number of tokens, with $n=\\Theta(\\text{poly}(|V|))$. Each parameter in the Transformer is designed to store information up to O(logn) bits to reflect practical machine precision (e.g., float16 or float32). We will include this explanation in the revised manuscript for better clarity. We welcome any different perspectives and are open to discussing them further.\n\n> Weakness 4: Theorem 2 and Example 1\n\nThe difficulty in path concatenation arises from the nature of the next-token-prediction loss itself--learning concatenation results in a higher training loss: When predicting the next token with the current node $i$ and target node $j$, the distribution of the next token that minimizes training loss should follow the corresponding distribution in the training dataset, i.e., $\\Pr[\\text{output} = k \\mid \\text{current node} = i \\text{ and target node} = j] = \\frac{N_{j,i,k}}{N_{j,i}}$. Path concatenation will alter the distribution from ${\\frac{N_{j,i,k}}{N_{j,i}} \\text{ for all } k}$, incurring a higher training loss.\n\n**Example:** Assume that the task is path-finding and training dataset contains the following three paths \"a b a b\", \"b d b c d\", and \"a e a d e\", where the first token is the source, the second token is the target, and the remaining tokens are a path from source to target. Now, suppose the input sequence is \"a e a\", if the model outputs d with probability 1, the cross-entropy loss is 0 (as only \"a e a d e\" in training data). However, if the model has the ability for path concatenation, the next token b will have a non-zero probability (as we have the path \"a b c d e\" through concatenation), and the cross-entropy loss will be larger than 0. \n\nInterestingly, after the submission, we find that this toy example has some practical implications in composition reasoning: if LLMs know the reasoning chain from $a\\rightarrow b \\rightarrow c$ and the chain $b\\rightarrow c \\rightarrow d$, they cannot perform reasoning $a\\rightarrow b \\rightarrow c \\rightarrow d$ through path concatenation. This holds for existing LLMs including GPT-4 [Ref A].\n\n> Weakness 5: how GNN is combined with LLMs. \n\n**Two-stage Framework (Figure 2 in the PDF of global response or Figure 6 of original paper)**  First, LLM interprets user request into several concrete steps as {$ s_1, \\ldots, s_n$} where $s_i$ is the $i$-th decomposed step. For the example request \"Please generate an image where a girl is reading a book, and her pose matches the boy in 'example.jpg', then describe the new image with your voice.\", the decomposition by GPT-4 is {\"1. Analyze the pose of the boy\", ... \"4. Convert the generated text into audio\"}. Then, we leverage GNN for task retrieval, sequentially matching each step description $s_i$ to a suitable task $v_i \\in V$ (e.g., matching \"1. Analyze the pose of the boy\" to \"Pose Detection\"), thus generating the invocation path. \n\nThen we provide the detailed GNN encoding process:\n\n* **Task Graph $G=(V,E,X)$** Each node $v \\in V$ represents an available task with a text $t_v$ describing its function (e.g., \"Translation. Translation is the task of converting text from one language to another.\").  Each edge $(u,v) \\in E$ indicates a dependency between tasks (e.g., the output format of task $u$ matches the input format of task $v$). We use an LM (i.e., e5-355M) to generate initial node features as $x_v = \\text{LM}(t_v)$. \n* **GNN Encoding** GNN incorporates dependencies between tasks and refines task embeddings as $h_v = \\text{GNN}(x_v, G)$ for node $v$. We then leverage updated embeddings for task retrieval: each step can be represented as $x_{i}^{\\text{step}} = \\text{LM}(s_i)$, we compute the dot product between $x_{i}^{\\text{step}}$ and task embeddings {$h_v$} for task selection. \n\nFinally, we explain GNN training. Each data sample in datasets contains the user request, a sequence of decomposed steps  {$s_1, \\ldots, s_n$} for the request, and ground-truth task invocation path {$v_1, \\ldots, v_n$}. We collect each $(s_i, v_i)$ pair and use a Bayesian Personalized Ranking loss for GNN training to realize its retrieval ability. \n\nThank you for pointing out the confusion, and we will improve the technical presentation accordingly.\n\n---\n[Ref A] Boshi Wang, et al. \"Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization.\" arXiv:2405.15071.\n\n[Ref B] William Merrill, and Ashish Sabharwal. \"The parallelism tradeoff: Limitations of log-precision transformers.\" TACL 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9BP6hi4oBK", "reviewer": "Reviewer_xcxm", "summary": "The paper proposes to use GNNs alongside LLMs for decision making problems represented in natural language and task graph inputs. Experimental results show that using GNNs provide improvements over just using LLMs.", "questions": "1. What is meant by \"fulfils the users' requests\"? Is this a classification problem, or a constraint satisfaction problem?\n2. What is the explicit graph encoding (nodes, edges, features) of the problem for use with the GNNs?\n3. Why are RestBench results only shown the no training results (Table 1) and not Table 2?", "limitations": "The authors addresses some limitations.\n- The work requires graphs to be part of the input problem.\n- Experiments repeats are not performed and error bars are not reported. Many score have marginal difference (e.g. <0.1 F1 score difference), yet this is not considered when highlighting the best performing model in the tables.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The results highlight that the approach makes sense and work, with improvements across benchmarks.\n\nThe paper provides some theory albeit simple and straightforward: graphs encoded as input strings into transformers are limited in expressiveness.", "weaknesses": "The paper has some clarity problems, as both the problem statement and the methodology of the paper is not clear without several rereads.\n\n1. The proposed definition of planning is vague and not well defined. The authors define task planning as a path finding problem on a task that fulfils user requests, where 'user requests' is not defined.\n\n2. It is not clear anywhere how GNNs are used to improve the performance the task planning problem described in the paper. More specifically, the input to the models in Sec. 4 are unclear, i.e. what is the type of request and $v_i$ in (request, {s_1, \\ldots, s_n}, {v_1, \\ldots, v_n}) in line 231. Furthermore, it is not mentioned what the graph encoding of the inputs of the problem are. What are the nodes, edge and features of the input problem for use with the GNN? It appears later on that the datasets already give you the graphs. Make this clear if this is true and describe the graph encodings in one place.\n\n3. \"The task planning considered here is more flexible and cannot be directly translated into formal languages\" is not explained. Both PDDL planning and the task planning problem the authors both have limitations as they require structured model inputs (PDDL language and graphs, respectively). Furthermore, the second half of the claim \"cannot be directly translated into formal languages\" is given no justification and explanation and appears as a handwavy argument to not consider these fields.\n\n4. GNN and graph representation learning have been employed in task planning and decision making for several years so it is wrong to claim that the paper \"presents an initial exploration into graph-learning-based approaches for task planning as pointed out in Section A.3. Related work concerning GNNs for PDDL planning is also missing, see e.g.\n- Sam Toyer, Sylvie Thiébaux, Felipe W. Trevizan, Lexing Xie: ASNets: Deep Learning for Generalised Planning. J. Artif. Intell. Res. 68: 1-68 (2020)\n- William Shen, Felipe W. Trevizan, Sylvie Thiébaux: Learning Domain-Independent Planning Heuristics with Hypergraph Networks. ICAPS 2020: 574-584\n- Simon Ståhlberg, Blai Bonet, Hector Geffner: Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits. ICAPS 2022\n- Jiayuan Mao, Tomás Lozano-Pérez, Joshua B. Tenenbaum, Leslie Pack Kaelbling: What Planning Problems Can A Relational Neural Network Solve? NeurIPS 2023\n- Dillon Ze Chen, Sylvie Thiébaux, Felipe W. Trevizan: Learning Domain-Independent Heuristics for Grounded and Lifted Planning. AAAI 2024\n\nOther comments and suggestions:\n- GNN definition not referenced, (1) is restrictive due to concatenation of edge features in aggregation function, but there are many GNNs that deal with edge features in other ways. \n- (1) is an MPNN\n- Define \"\\oplus is an operator\" more rigorously. A mathematical operator on integers, floats, booleans? What is the XOR operating on, the bit representation of a number, or a cast of a number to a boolean? \n- Figure 2: typos in legend. hallucination ratio not defined nor referenced anywhere in the text\n- Theorem 1: assumptions should not be listed in the appendix, and instead should be given before the statement of the theorem\n- F1-scores do not measure accuracy", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the insightful and constructive feedback.\n\n--- \n\n> Weakness 1, 3, 4 and Question 1: Definition of task planning and user request; Task planning and PDDL; Related work concerning GNNs for PDDL\n\nThis paper investigates task planning for language agents, a new and increasingly important application area with the development of LLMs [30, 14, 43].\n\n**Definition of Task Planning for Language Agents:** Task planning involves a task graph, a directed graph where nodes represent tasks and edges indicate dependencies between tasks. Each node contains text detailing the task's name and usage in natural language. **The inputs are this task graph and a user request expressed in natural language**. The request is often ambiguous and personal, making it difficult to define mathematically. The output is a sequence of tasks and their order of invocation (a path on the graph) to fulfill the user's request. \n \n**Example:** Figure 1 in the PDF illustrates task planning for HuggingGPT [31]. Task nodes correspond to APIs from the HuggingFace website, such as \"Translation\", accompanied by text descriptions like \"Translation is the task of converting text from one language to another.\" The **user request** is \"Please generate an image where a girl is reading a book, and her pose matches the boy in 'example.jpg', then describe the new image with your voice.\" The output is a sequence of four APIs (nodes): {\"Pose Detection\", \"Pose-to-Image\", \"Image-to-Text\", \"Text-to-Speech\"}, outlining the execution order. By invoking these APIs on HuggingFace, user request can be fulfilled.\n\nSince the output is a sequence of tasks (a path on the task graph), task planning for language agents is similar to a constraint satisfaction problem (CSP). However, it cannot be solved as a CSP because **both the task graph features and user requests are expressed in natural language**. \n\nUnlike classic planning with fixed goals (e.g., arranging tiles in numerical order in the n-puzzle), task planning for language agents involves **diverse and open-ended goals** due to varied and personal user requirements. For example, on HuggingFace, user intentions span video, text, and image domains. Formulating such specific and context-rich requests into PDDL is quite difficult, as shown by the example request.\n\nTo our knowledge, this is the first paper to explore the GNNs in task planning for language agents. We consider the references suggested by the reviewers to be important and constructive. Accordingly, we will discuss these references and narrow our title and statements to language agents in revised manuscript.\n\n> Weakness 2 and Question 2: Details of Framework\n\nDue to rebuttal space limitations, please refer to Weakness 5 of Reviewer ZJrg for the answer.\n\n> The theory is straightforward\n\nThank you for helping us refine the theoretical contributions. Section 3.2 explains that LLMs task planning issues arise from language pretraining and auto-regressive loss biases, rather than the input format.\n\nIn task planning for language agents, the existing studies focus on prompt engineering for pretrained LLMs, and we seek to investigate fundamental limits. We initially thought that the expressiveness was hindered by the input format. However, we discovered that the input format does not impede expressiveness, even when the hidden dimension is small (Theorem 1). Pursuing this line of inquiry, we found that sparse attention, an inductive bias inherent in language pretraining [48], restricts expressiveness (Proposition 1), and that the auto-regressive loss introduces spurious correlations (Theorem 2). These negative results inspire us to apply GNNs to complement LLMs.\n\n> Question 3: No RestBench results in Table 2\n\nAs mentioned in Line 289-290, RestBench has only 100 data samples, which limits effective model training.\n\n> (1) is an MPNN and define \"\\oplus is an operator\" more rigorously\n\nWe use the GNN definition from [49, 50], which is a general formulation of message-passing-based GNN (e.g., GCNs or GATs). As Aggregate$^{(k)}$ can be any functions operating on the set, it can represent commonly used operations on edges, such as multiplication. \n\nWe agree with the reviewer that it is a message-passing-based GNN and we will change its name in the revised manuscript. The input type of $\\oplus$ depends on the type of Answer[k − 1][j] and c[i][j] and can be any operator. \n\n> Definition of hallucination ratio\n\nAs mentioned in Line 122-124, it is defined as the percentage of non-existent nodes or links outputted by LLMs. Since LLMs' output domain is open-ended, their output may contain nodes or edges not present in the graph. Specifically, for a prediction {$v_1, \\ldots,  v_n$}, the node hallucination ratio is computed as $\\frac{ \\sum_{i=1}^n \\mathbb{I}(v_i \\notin V)}{n}$ where $\\mathbb{I}(\\cdot) \\in ${0, 1} is an indicator function. The same method applies to the link hallucination ratio.  \n\n> Assumptions should be put in main text\n\nDue to space limitations, we initially included the assumptions in the appendix. We totally agree with the reviewer that these assumptions would be more appropriately placed in the main text. We will revise the manuscript accordingly.\n\n> Missing accuracy\n\nThank you for your suggestion. **We have supplemented our results with accuracy metric in Table 1 of the PDF file in global rebuttal.** The results show that integrating GNNs significantly improves accuracy. \n\n> The work requires graphs to be part of the input problem\n\nThank you for pointing out the limitation. In task planning for language agents, the dependencies of tasks naturally form a graph, which we believe is straightforward to obtain.\n\n> Error bar\n\nWe followed previous works HuggingGPT [31] and TaskBench [30] to give the experimental results. The original papers did not provide performance variance as some experiments are extremely time-consuming and the variation is small. We will include error bars in the revised manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oBUjNEDFJ1", "reviewer": "Reviewer_wd1Z", "summary": "This work proposes to investigate the integration of LLMs and GNNs for task planning. Specifically, LLMs are employed for the request decomposition stage while GNNs are employed for the task retrieval stage. Experiments demonstrate gains on various datasets across various LLMs.", "questions": "please see above", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "+ the intersection of LLMs and graphs is interesting\n+ task planning is an important problem", "weaknesses": "- It would be nice to present a figure/clear description of how LLMs and GNNs are integrated for task planning, somewhere in Section 4. For now it seems that Sec 4.2&4.3 focus on details of existing GNN proposals, which is not the technical contribution of this work, so it might make more sense to better highlight the unique way of composing them.\n\n- There is some literature on combining LMs and GNNs for various purposes, most related ones include [1-3]. I'm not sure if the related work discussion is currently adequate and perhaps it would be helpful to start from [1-3]. In addition, maybe some of these could be valid baselines, especially for works like [2] and [3].\n\n- LLMs are used in stage 1: decomposition while GNNs are used in stage 2: task retrieval, right? One might say that the decomposition step is a more \"planning\" process than just retrieving task descriptions with GNNs, so it might make sense if the proposal could incorporate GNNs in stage 1. This decoupled/independent application of LLMs and GNNs each in one separate step seems less exciting, compared to the deeper combinations of LLMs and GNNs like [1-3]. Perhaps if the authors could empirically show that keeping them separate is better than these existing proposals?\n\n- It would be nice to show qualitative analysis for the improved stage 2, highlighting at least one killer example in the main paper where LLMs failed task retrieval but GNNs helped. Totally understand the space limit so merely a suggestion.\n\n- There is a mismatch between Sec 3.1 and 3.2. While 3.1 is empirically looking at LLM graph reasoning specific to the planning task, Sec 3.2 is looking at more general interpretations of LLM graph reasoning in natural language. As the title suggests, the main focus of this work is specifically task planning, so I'm not sure if 3.2 is integral/significant to the main argument and could be a standalone work.\n\n- Minor point, not sure if Figure 2 is presenting the strongest models both for open and proprietary LLMs. I see that GPT-4 is employed in Section 5.1, why not here?\n\n- Minor point, but the title could be a bit vague. \"Graph learning\" is a broad term, could mean the GNN-centric line of graph representation learning and could also be referring to the more recent LLM&graphs research direction. Maybe better highlight that this work presents a way to combine LLMs and GNNs, that they execute different stage of the task planning pipeline.\n\n[1] Yasunaga, Michihiro, et al. \"Deep bidirectional language-knowledge graph pretraining.\" Advances in Neural Information Processing Systems 35 (2022): 37309-37323.\n\n[2] He, Xiaoxin, et al. \"Harnessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning.\" The Twelfth International Conference on Learning Representations. 2023.\n\n[3] Perozzi, Bryan, et al. \"Let Your Graph Do the Talking: Encoding Structured Data for LLMs.\" arXiv preprint arXiv:2402.05862 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for your insightful and constructive feedback.\n\n--- \n\n> Weakness 1: Methodology figure\n\nThank you for your suggestion. The methodology figure is provided in Figure 6 of original paper and better illustrated in **Figure 2 of the PDF in the global response**. We will relocate it to the main text for better clarity.\n\n> Weakness 2: Comparison to related works [Ref A-C]\n\nThank you for pointing out these works. We will provide a detailed discussion in the revised manuscript. Our approach differs in both application and methodology: DRAGON [A] pre-trains a language-knowledge model for QA tasks, TAPE [B] focuses on node classification on text-attributed graphs, and GraphToken [C] addresses basic graph reasoning tasks. Unlike these papers, task planning involves a complex and ambiguous user request, which encompasses multiple tasks and thus does not belong to any applications in [A-C]. Here is a detailed comparison:\n| Paper          | Application        | Graph Type                 | Methodology             |\n| -------------- | ------------------- | -------------------------- | -------------------------------------- |\n| DRAGON [A]     | Question Answering  | Knowledge Graph            | LM                                     |\n| TAPE [B]       | Node Classification | Text-attributed Graph (TAG)      | LLM → LM → GNN |\n| GraphToken [C] | Graph Reasoning     | Graph w/o. Text            | GNN → LLM                  |\n| Ours           | Task Planning for Language Agents      | Task Graph (a kind of TAG) | LLM → LM + GNN             |\n\nThen, we considered using these as baselines. First, when language agents are deployed to a new environment, there is no training data available and training-free algorithms are needed (Table 1), making the above approaches inapplicable. Second, in the training-based scenario (Table 2), [B] and [C] can be adapted to our setting as baselines. Specifically, we adapted TAPE for task planning by mapping user requests to task labels using its original LLM-LM-GNN architecture. For GraphToken, we treated the user request as the input question, the expected plan as the answer, and the GNN encoded the task graph into latent embeddings.\n\n**Results in Table 2 in the PDF file of the global rebuttal show our method consistently outperforms them**. TAPE is unsuitable for task planning as its classification approach simplifies task planning, overlooking task dependencies. While GraphToken indeed demonstrates superior performance over direct LLM inference, we have noted instances of minor hallucination. This observation suggests that GraphToken's understanding of the task graph is not yet perfect. In addition, GraphToken is limited to open-source LLMs.\n\n> Weakness 3: Rationale for the two-stage algorithm\n\nThank you for providing valuable insights. The rationale is justified by three main reasons: 1) Training-free deployment is needed in new environments for language agents, whereas methods in [Ref A-C] require extensive training. 2) Flexibility to use proprietary LLMs, like GPT-3.5, while GraphToken [C] is limited to open-source LLMs. 3) Simplifying the methodology while integrating the strengths of both LLMs and GNNs. **To illustrate this advantage, we compare our method with [B, C] in the PDF and demonstrate superior performance.**\n\nWithin the framework, both the LLM and GNN contribute to the planning. The LLM interprets ambiguous user requests into concrete steps, while the GNN selects suitable tasks aligned with those steps. In the second stage—task retrieval, which involves graph planning and reasoning—LLMs face challenges due to hallucinations and limited graph understanding abilities (see Sections 3.1 and 3.2). Our framework leverages the strengths of both LLMs and GNNs in task planning, ensuring more accurate planning results.\n\n> Weakness 4: Qualitative analysis for the improved stage 2\n\nWe will move **Figure 9 on Page 24** to the main paper, where GNNs successfully correct paths that LLMs fail to generate. \n\n> Weakness 5: Mismatch between Section 3.1 and 3.2.\n\nWe thank the reviewers for allowing us to clarify Section 3.2's role in task planning for language agents like HuggingGPT. Current research in this area mainly uses pre-trained LLMs and focuses on prompt design (e.g., [20,23,31,42]), but exploring their fundamental limits is essential. Section 3.2, while focused on general graph planning, is also relevant to task planning, as evidenced by our theorems. In existing studies, task graphs are often presented in Eq. 3, where the edge list is describe by natural language and the initial states are the task descriptions of each task node, detailed in Appendix A.9 of [30]. Theorem 1 shows a positive result that confirms Transformer models' expressiveness for such tasks. However, sparse attention, a inductive bias of language [48], limits expressiveness (Proposition 1) and auto-regressive loss could introduce spurious correlations (Theorem 2). These negative results inspire us to jointly leverage GNNs and LLMs for task planning to combine their strengths. \n\n> Weakness 6: Missing GPT-4 in Figure 2\n\nWe omitted GPT-4 and CodeLlama-7B in Figure 2 due to limited space. The Task-F1 score of GPT-4-turbo is 77.60% with hallucination ratios of 0.12% for nodes and 6.73% for edges. \n\n> Weakness 7: Vagueness of \"graph learning\"\n\nThank you for bringing our attention to the vagueness of the title. We categorize our work into the more recent LLM&Graphs research direction as we integrate GNNs to boost task planning for language agents. We will change the title in the revised manuscript.\n\n---\n\n[Ref A] Yasunaga, Michihiro, et al. \"Deep bidirectional language-knowledge graph pretraining.\" NeurIPS 2022.\n\n[Ref B] He, Xiaoxin, et al. \"Harnessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning.\" ICLR 2024.\n\n[Ref C] Perozzi, Bryan, et al. \"Let Your Graph Do the Talking: Encoding Structured Data for LLMs.\" arXiv:2402.05862.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global Rebuttal

We sincerely thank all the reviewers for your constructive feedback and recognition of this work, especially for acknowledging **the theoretical contributions** (Reviewer s7yo), **the motivations to adopt GNNs** (Reviewer s7yo and ZJrg), and **the superior performance** (Reviewer s7yo, ZJrg, and xcxm). 

This paper focuses on a new application, i.e., task planning for language agents. This area is becoming increasingly popular and important with the development of LLMs [30, 14, 43]. Given its practical significance, there are many existing empirical works in this area while their focus is prompt design for pre-trained LLMs (e.g., [20,23,31,34,42]). We would like to re-emphasize the novelty and technical contributions of this work:

- To our knowledge, this is the **first attempt to theoretically understand the fundamental limits of LLMs in this application** (or more broadly, in LLMs for graph problems). We provide proofs that Transformers are expressive enough for planning on task graphs (Theorem 1), yet the attention mechanism's inductive bias could limit this expressiveness (Proposition 1), and auto-regressive loss might introduce spurious correlations (Theorem 2).
- Inspired by both theoretical and empirical findings, we propose to explore the use of GNNs in this application, **an orthogonal direction to existing studies**. Specifically, we propose an LLM+GNN solution that is flexible, supports **both training-free (zero-shot) and training-based algorithms**, and is compatible with **both open-sourced and closed-sourced LLMs**. 
- Extensive experiments demonstrate the proposed solution outperforms existing methods on TaskBench and RestBench in both **performance and efficiency**. Furthermore, the proposed solution complements to existing prompt engineering and fine-tuning techniques, with performance further enhanced by improved prompts or a fine-tuned model.
- As an early exploration of applying GNNs to language agents, our research emphasizes that LLMs alone may not be sufficient, and traditional methods like GNNs have a role to play. We hope this work will inspire future research in language agents.


In line with the reviewers' constructive feedback, we have made the following additions and clarifications in our rebuttal:
- We adapted TAPE [Ref A] and GraphToken [Ref B] for task planning and included them as new baselines, with results provided in Table 2 of the PDF. (Response to Weakness 2 of Reviewer wd1Z)
- We clarified the definition of task planning for language agents and how it differs from traditional planning tasks. (Response to Weakness 1, 3, 4 of Reviewer xcxm)
- We provided more details on our proposed framework. To enhance readability and facilitate understanding, illustrations of task planning for language agents and our framework are included in Figure 1 and Figure 2 of the PDF file. (Response to Weakness 5 of Reviewer ZJrg)
- We provided results of an extra metric, Accuracy, for both baselines and our method in Table 1 of the PDF, demonstrating significant improvements across different datasets and LLMs. (Response to Reviewer xcxm)

Please don't hesitate to let us know of any additional comments on the manuscript or the changes.

---

[Ref A] He, Xiaoxin, et al. "Harnessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning." ICLR 2024.

[Ref B] Perozzi, Bryan, et al. "Let Your Graph Do the Talking: Encoding Structured Data for LLMs." arXiv:2402.05862.

Meta-review: The paper explores the combination of LLMs and GNNs for task planning. It presents theoretical insights into LLM limitations on graph-structured data and demonstrates empirical gains across various datasets. While reviewers appreciate the novelty and potential of the approach, they raise concerns about the clarity of presentation, theoretical arguments, and comparisons to existing literature. The authors have addressed some of these concerns in their responses.
I lean towards recommending acceptance for this paper. The idea is interesting and the results are promising, but there's room for improvement in clarity and positioning within the existing literature. The authors should use the feedback to strengthen the paper for the final version.
Decision: Accept (poster)