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
fudan  university
microsoft  research
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 11:11:00

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.

Main paper: 
 introduction: 
 LLM-based agents have recently emerged as a rapidly growing field of research and are considered a 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 instructions in natural language into concrete and solvable sub-tasks, and then fulfilling the user's request by executing each sub-task [43, 46, 45] . For instance, in the case of HuggingGPT [46] , task planning involves invoking expert AI models from the HuggingFace website to solve complex AI 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, 4, 63] . This paper proposes to explore an orthogonal direction, i.e., graph-learning-based 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 considerable 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 a discussion on the inherent limitations of LLMs 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.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 is 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 to graph structures, potentially reducing expressiveness. Contrary to this hypothesis, it is proved that by taking edge lists as the input, a constant-width 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] . 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] to 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:1. Task Planning Formulation: This study presents a formulation of task planning as a graph 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 as a new application in the graph learning domain. 
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 an additional GNN for sub-task retrieval, available in both training-free and training-based variants. The experiments on diverse LLMs and planning datasets demonstrate that the proposed method outperforms existing solutions with much less computation time. Furthermore, the performance is further enhanced by improved prompts or a fine-tuned model.In this section, we introduce task planning in language agents and the current LLM-based solutions.We start with the definition of task planning with a concrete example of HuggingGPT [46] . In task planning, there is a pool of pre-defined tasks. Task planning inputs include this task pool and a user request. The user request is expressed in natural language, which is ambiguous and could encompass 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.The current solution of task planning is purely based on LLMs and involves two stages [45, 46] . The first stage involves request decomposition, where a user's ambiguous request is broken down into concrete steps via LLMs. For instance, the request illustrated in Figure 1 is decomposed into the following steps: (1) analyze the pose of the boy; (2) take that pose and generate a 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-Text; (4) Text-to-Speech. Figure 6 illustrates this procedure.3 Graph Formulation and Insights 
graph formulation of task planning: 
 In this subsection, we formulate the task planning as a decision-making problem on the task graph. The task graph is a special kind of text-attributed graphs and we define it as G = (V, E, T ). Each node v ∈ V represents a pre-defined task in the task pool, associated with a text t v ∈ T describing its function (e.g., "Translation. Translation is the task of converting text from one language to another."). Each edge (u, v) ∈ E indicates a dependency between tasks (e.g., the output format of task u matches the input format of task v). Task planning is to select a path or connected sub-graph on the task graph.Viewed from this angle, task planning bears resemblance to 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 a fixed goal for a given domain, which is often explicitly expressed by mathematical formulas [55, 36] .With the task graph at hand, we diagnose LLMs in task planning in Figure 2 . 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 F1 score to assess the accuracy of the tasks identified by LLMs against the ground-truth tasks. Additionally, we report two task-graph-related metrics: 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 a 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 UltraTool dataset [20] , which consists of 260 sub-tasks. Figure 2b illustrates that the hallucination ratio increases with a larger task graph size.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 a sequence and are trained using an 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 decisionmaking problems that can be resolved using dynamic programming (DP) as described in (2) . The input comprises the edge list and initial states:u 1 v 1 c[u 1 ][v 1 ] u 1 v 2 c[u 1 ][v 2 ] . . . edge list u 1 Answer[0][u 1 ] . . . u n Answer[0][u n ] initial states (1)The intended output format isu 1 Answer[k][u 1 ] . . . u n Answer[k][u n ].In existing studies, task graphs are often presented in (1) , 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 [45] .As discussed in the previous subsection, task planning is a decision-making problem on the task graph. The decision-making problems on graphs are often solved by DP [3] and its general formulation is given byEQUATIONwhere 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, □ j∈T (i) 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-making problems on the text-attributed graphs (e.g., task planning), one may conceptualize them as 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, it enables Transformers to simulate DP efficiently, in terms of expressiveness, as demonstrated by the following theorem. The proof is presented in Appendix D.2. However, certain aspects of the proof's constructions are challenging to be realized in Transformers that have been pretrained on natural language. First, the embedding process must be carefully filtered to 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 a 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(|V |). In practice, the attention trained from natural language is 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 a constant number of tokens.There exists at least one instance of one-step DP update such that no log-precision constant-width 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-prediction loss. For a tractable theoretical study, we conceptualize this issue as a path-planning problem, since the output of task planning is essentially a path. We consider the training dataset comprises input sequences of the form s t s v 1 v 2 (2) the output logits are determined by target node t and the current node v i-1 . Let N t,vi-1,u be the number of times in the training dataset such that t is the target node, v i-1 is the current node and v i = u is the next node. The optimal logits for predicting the next node u from current node v i-1 towards target node t is given by vi[u] = Nt,v i-1 ,u u Nt,v i-1 ,u if u N t,vi-1,u > 0. If u N t,vi-1,u = 0, vi [u] can be any non-negative number subject to u vi [u] = 1.In our setup, s t is the instruction and the third token is a duplicate of the first token. It is reasonable to exclude these tokens in the loss calculation, which is the first assumption. The second assumption assumes that the output only depends on the current node and target node, which is a minimal requirement for path-related problems. For DP problems, the frequency-based prediction contradicts to the value-based ground-truth. We then give an example that auto-regressive loss even cannot find a valid path.Example 1. Consider a training dataset consisting of a sufficient number of valid paths. Suppose the dataset contains two paths a b c and b c d and there are no other paths such that t = d and the current node v i = a for all i. Then we have N d,a,u ≡ 0 for all u 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 a human, finding a path from a to d simply involves concatenating the paths a b c and b c d. However, auto-regressive loss fails under such circumstances. In task planning datasets, we indeed observe that the performance of fine-tuned LLMs is inferior to that of GNNs trained on the same dataset, as shown in Figure 3b . 
motivations: 
 In the last section, we find that a considerable portion of planning failures can be ascribed to the LLMs' inefficacy in 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 a 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 a 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-based methods.As we discussed in Section 2.2, the current solution to task planning involves two stages. The first stage requires the ability to 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 to a decomposed step. Thus, we can integrate GNNs in this stage. The illustration of our framework is shown in Figure 7 in Appendix.For each decomposed step outputted by the first stage, we use a 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, e5-335M [62] , to embed the i-th decomposed step. The resulting embedding is denoted as x step i . Second, for the task graph, we first use the same pre-trained language model e5-335M to convert each node's description into embeddings, denoted as the node feature h 0 v , where the superscript indicates the layer and the subscript represents the node. Then we adopt a K-layer SGC [65] to compute the final node embeddings, resulting inh v = h (K) v . Given a sequence of previously selected task nodes {v 1 , • • • , v i-1 }, the next node v i is chosen according to v i = argmax v∈N (vi-1) ⟨h v , x step i ⟩, where h v is the final node embedding, and N (v i-1 ) denotes the neighbors of node v i-1 in the task graph. Particularly, v 1 can be selected from the whole graph.As e5-335M is pre-trained and SGC is parameter-free, the proposed method requires no additional training and can be effectively applied in a zero-shot manner.The inference process in training-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.Data Preparation: We assume that each entry in the task planning dataset comprises a user request, a sequence of decomposed steps, and the corresponding ground-truth tasks, denoted as (request, {s 1 , . . . , s n }, {v 1 , . . . , v n }). 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 to 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 {(s i , v i )} n i=1 , where s i is a step described in natural language, and v i is its corresponding invoked task.Training Loss: The problem in the dataset can be viewed as a binary ranking problem, where the labeled node is 1 and the other nodes are 0. Therefore, we adopt the Bayesian Personalized Ranking (BPR) loss [41] designed for recommendation with binary rankings. The loss function is given by ℓ = (x step ,v,v ′ ) -log σ(⟨h v , x step ⟩ -⟨h v ′ , x step ⟩), where x step represents the embedding of the step's textual description generated by e5-335M, v is the ground-truth task, and v ′ is a negative task.We select negative tasks that are textually similar to the positive task, and for computational efficiency, we limit our selection to 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 
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 AI models on 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 in Figure 4 in Appendix. Other benchmarks, such as ToolBench [39] and ToolAlpaca [54] , are less suitable for our experiments due to (1) the absence of a well-defined task graph detailing tasks and their dependencies, and (2) a scarcity of samples involving multi-task planning, with a focus on single-task retrieval.Evaluation: For the datasets from TaskBench, 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.e., Node F1-Score (n-F1) and Link F1-Score (l-F1), which measure the accuracy of invoked tasks and invoked dependencies, respectively. Besides, the Accuracy (Acc) can measure the success rate from task level. We also measure the token consumption (# tok) as the efficiency metric.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 CodeLlama-13B(or 7B)-Instruct-hf [42] , Mistral-7B-Instruct-v0.2 [23] , Vicuna-13B-v1.5 [72] , and Baichuan2-13B-Chat [69] .To comprehensively investigate the effectiveness of different graph learning methods for task planning, we consider a wide range of graph neural networks, including SGC [65] , GCN [26] , GAT [57] , GraphSAGE [15] , GIN [67] , and Graph Transformers [47] .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 a 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 a training-free SGC for task retrieval based on decomposed task steps. The details of baselines are given in Section E.1 and illustrated in Figure 6 . Table 1 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-type methods rely on beam search to 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 1 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 ChatGPTplugins, and it 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. A detailed diagnostic analysis of cases involving GPT-4 is provided in Figure 11 in Appendix. -F1 ↑ l-F1 ↑ # Tok ↓ n-F1 ↑ l-F1 ↑ # Tok ↓ n-F1 ↑ l-F1 ↑ # Tok ↓ n-F1 ↑ l-F1 ↑ #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 GraphSAGE in the main text, relegating a 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, a 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) GraphToken [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.Observations: From Table 2 , we observe a significant improvement in performance when employing a training-based GraphSAGE approach over the training-free method. However, the co-training of GNNs with e5-335M does not yield a marked improvement, suggesting that message passing is the crucial element for enhancing performance. Further analysis across a 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 planning 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 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, as given in Appendix G (e.g. 9% improvement to GPT-3.5-turbo and 3% improvement to GPT-4-turbo).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 [16] is designed for node classification task and cannot predict links, so we report Link-F1 as "NA". GraphToken [38] requires finetuning LLMs, which is not compatible with close-sourced LLMs. The performance of other GNNs and LLMs are given in Table 11 and Table 12 in the Appendix. [20] .EQUATIONIntegrating GNNs can lead to more significant improvements in LLMs on larger task graphs. training duration extends to only 15 minutes when GNNs are jointly trained with e5-335M model. This efficiency stands in stark contrast to the 10-20 hours required for tuning open-sourced LLMs.0-shot 1-shot LLM Method n-F1 ↑ l-F1 ↑ Acc ↑ # Tok ↓ n-F1 ↑ l-F1 ↑ Acc ↑ #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 training-required GraphSAGE) against strong baselines like BeamSearch in Table 3 . Among the metrics, accuracy (Acc) is calculated based on whether the predicted tasks match the ground-truth tasks, measuring the success rate at each case level. In such conditions, integrating a GNN significantly enhances performance and mitigates planning failures, e.g., GPT-4-turbo undergoes a 9.05% accuracy improvement with the introduction of GraphSAGE. 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.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.e., 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 to 2, and results under this setting are denoted as "2-shot Prompt"; (2) Plan like a Graph (PlaG) [30] We adopt the prompt in [30] to encourage LLM to think and plan in a 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-13B and Mistral-7B on HuggingFace, it is clear that applying GraphSAGE 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 dataset-specific task planning capabilities, we conduct further experiments. For each dataset, we use LoRA [19] to fine-tune two LLMs of different parameter scales, including CodeLlama-7B and Vicuna-13B, based on the same training data as GNNs. Details of fine-tuning process are provided in Appendix F.3. The finetuned model is named as "FT-CodeLlama" and "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 of task planning. 
conclusions: 
 This paper presents an initial exploration into graph-learning-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.Limitations: Despite the encouraging performance, there are limitations that highlight significant opportunities for enhancement. Firstly, our proposed method, while effective, is straightforward; more sophisticated graph-learning-based decision-making algorithms could potentially offer further improvements. Secondly, the construction of the task graph currently requires manual effort. Investigating automated graph generation techniques for diverse applications is another promising direction for future work. 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-and-conquer 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. Multi-plan selection strategies, exemplified by the tree-of-thought [71] and graph-of-thought [4] , leverage search-based methods to generate plans. Subsequently, LLMs evaluate these plans to select the most effective one. The "GraphSearch" methods used in our baselines fall into this category. External planner approaches [31] use LLMs to 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 in this application. Reflection-based 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: We specify them in Appendix I.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Apart from task planning in language agents, there is also a domain in traditional AI called task planning [1, 6, 18, 55, 44, 51, 35, 10] . Task planning in traditional AI is defined as (S, A, T , C, G, s 0 ), where S is the states, A is the action space, T :S × S × A → [0, 1], a cost function C : S × A → [0, ∞), a set of goal states G ⊆ S, and an initial state s 0 . An agent following a policy π : A × S → [0, 1] will start in state s 0 , then repeatedly choose an action a ∼ π(a|s) and execute it to reach a new state s ′ ∼ T (s ′ |s, a), incurring a cost C(s, a) along its way. An optimal policy π * (a|s) is one that reaches the goal state with probability 1 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] .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 LLMs.Planning is a 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 UltraTool dataset used in this paper belongs to the tool agents. The Math agent, AlphaGeometry, employs LLMs to generate auxiliary constructions in geometry [56] .Considering lemmas as nodes and their interdependencies as edges, the endeavor to prove a 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 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.With the breakthroughs in LLMs, there has been a surge of interest in applying LLMs to graphrelated 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 a 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-path tasks, even with the use of complex prompts. GraphInstruct [34] attempts to fine-tune LLMs on graph-theory-related tasks, resulting in improved performance, though it remains far from satisfactory. Despite these empirical efforts, there is a 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.Considering these negative results, a new line of research has emerged that utilizes the output of GNNs as tokens for LLMs, as seen in GraphGPT [53] , GraphLLM [9] , GraphToken [38] , and G-Retriever [17] . These approaches have demonstrated significant improvements in performance on GNN-related tasks. However, they have not yet been applied to task planning due to 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 to task planning. This paper proposes to use task planning as a new benchmark for this line of research.Reasoning is closely related to task planning 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-Ford 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 0 to P. This analysis is further applied to linear and sparse Transformers in [70] .Our proof of Theorem 1 builds upon the proof of Theorem 4.7 in [12] . However, while [12] addresses DP problems without graph structures, Theorem 1 specifically focuses on DP problems with graph edge list inputs. Moreover, unlike [12] , which decomposes and solves the DP problem sequentially, Theorem 1 proposes a method to simulate DP on edge lists in parallel. In addition, we analyze the negative results rising from the inductive bias of attention mechanism and auto-regressive loss. These theoretical contributions are novel and promise to be valuable for general reasoning and planning tasks.GNNs are popular approaches for solving decision-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 in a manner that satisfies the constraints [24] . In this paper, we adopt this method to sequentially select task nodes. Furthermore, reinforcement learning can be used to enhance the performance of 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 a single iteration. Additionally, GNNs are utilized as the method for variable selection in exhaustive searches for exact solutions to combinatorial optimization problems [13] . This paper conceptualizes task planning as a graph-based decision-making problem. Both greedy and beam search algorithms have been adopted in task planning [33, 32] . Given this connection, a promising future direction involves repurposing GNNs for decision-making approaches in taskplanning applications. 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 groundtruth 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.The TMDB dataset from RestBench, focuses on movie-related searching and recommending functions.To align RestBench with our experiments, we have implemented the following processing steps:Reformatting original APIs by assigning unique task names and descriptions: APIs in RestBench were represented by request paths, such as "GET /movie/top_rated", referring to the API that retrieves top-rated movies on TMDB. To enhance semantic differentiation among APIs, we first prompt GPT-4 to assign a 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 a 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, we focus only on those APIs that appeared in at least one user request, resulting in a refined set of 46 APIs.Constructing a Task Graph: Each API is regarded as a unique task node, and we depict their relationships from two aspects: (1) categorical association, and (2) resource dependencies. For instance, APIs that provide movie-related functionalities, such as retrieving movie details or recommending films, are grouped under the movie category. Conversely, APIs focused on person-related functions, like searching for actors, are 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 a path structure, we treated each invoked API as a node and the sequence of invocations as directed links from one API to the next. For example, a 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/movie", "GET /movie/{movie_id}/credits"]. We transform this solution into a task invocation path as "{ "task_nodes": ["Search Movie", "Get Movie Credit"], "task_links": [{"source": "Search Movie", "target": "Get Movie Credit"}]} ".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 HuggingFace TMDB I just finished watching Titanic and I want some other movie recommendations.Step 1 Call Search Movie to find the movie ID of TitanicStep 2 Call Movie Recommend to obtain a list of recommended movies based on Titanic's IDStep graphs are relatively small, containing no more than 50 tasks, which falls within the capabilities of LLMs. Therefore, we aim to evacuate planning performance as well as GNN's effectiveness in a more challenging scenario, i.e., one that requires specific knowledge beyond the LLM's training and involves larger task graphs that possibly exceed its memory and reasoning capabilities.Constructing a Task Graph: 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 to 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 distinct 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.Reformatting Raw Data Examples: We allocated 500 samples for testing and 3, 000 samples for GNN training. Although the original UltraTool provided decomposed steps, we found them too coarse-grained, making it difficult to align step descriptions with suitable tasks. Therefore, we employed a similar strategy by prompting GPT-4 to infer decomposed task steps that align with each invoked task. As a result, each data sample consists of the user request, corresponding steps, and ground-truth invoked tasks, ensuring high quality for GNN training. of initial states, etc.), embedding for edge list tokens e pos2 (0 for initial state tokens, 1 for the first three elements of the edge list, 2 for the second three elements of the edge list, etc.). There are also constant-dimensional placeholders to put the states of DP. Block 2 -Edge Feature Operations: 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 if e type1 == 2; (2) Copy the second placeholder from the edge feature token to the node token by using SUM in Lemma 1 and setting S k = {j|(e pos2 k -e pos2 j ) 2 < δ}. Now the state for every node token u i of the i-th edge is [e type1 , e type2 , e token , e pos1 , e pos2 ,Answer[0][u i ], c[u i ][v i ]].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 i of the i-th edge is [e type1 , e type2 , e token , e pos1 , e pos2 ,Answer[0][u i ], c[u i ][v i ], g(Answer[0][u i ], c[u i ][v i ])];(2) Use MLPs to clean up the first and second placeholder. Now the state for every node token u i is [e type1 , e type2 , e token , e pos1 , e pos2 , g(Answer[0][u i ], c[u i ][v i ])]Block 4 -Message Passing: The goal of the fourth block is to compute □ 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 is achieved by using MEAN or MAX or SUM for the first placeholder and setting S k = {j|(e token k -e token j ) 2 + (e type2 k -e type2 j ) 2 < δ}. Now the state for every node token u i is [e type1 , e type2 , e token , e pos1 , e pos2 , □ vj ∈T (ui) g(Answer[0][u i ], c[u i ][v j ])];(2) Use MLPs to compute f . Now the state for every node token is [e type1 , e type2 , e token , e pos1 , e pos2 , f(□ vj ∈T (i) g(Answer[0][u i ], c[u i ][v j ]))].After four blocks, the final state for every node token u i is given by [e type1 , e type2 , e token , e pos1 , e pos2 , Answer [1] [u i ]].Answer[k][u i ] can be obtained by repeating the above four blocks k times. Lemma 1. [12] Let n ∈ N be an integer and x 1 , • • • , x n be a sequence of vectors wherex i = ( xi , r i , 1) ∈ [-M, M ] d+2 where M is a large constant. Let K, Q, V ∈ R d ′ ×(d+2)be any matrices with ∥V ∥ ∞ ≤ 1 and let 0 < ρ, δ < M be any real numbers. Denote q i = Qx i , k j = Kx i , v j = V x j . Define a matching set S = {j||q T i k j | ≤ ρ}. Define two following operations• COPY: The output is a sequence of vectors u 1 , • • • , u n with u i = v pos(i), where pos(i) = arg max j∈Si r j .• MEAN, MAX, SUM: The output is a sequence of vectors u 1 , • • • , u n , where u i = □ j∈Si v j and □ is min or max or sum or mean.Specifically, for any sequence of vectors x 1 , x 2 , • • • , x n ,We test whether LLMs respect the permutation invariance property in graph problems and the results are given in Figure 5 .Proposition 2. Assume the input format is as described in Equation (1) and that the attention mechanism is limited to attending to a constant number of tokens. There exists at least one instance An undirected graph with edge list: [[0, 1], [1, 2] , [2, 3] , [3, 4] , [0, 4], [2, 4] , [0, 3], [2, 5] , [5, 6] , [6, 7] , [7, 8] , [5, 8] , [5, 7] , [6, 8] ]. What is the diameter of this graph? Only provide a concrete number.GPT-4-turbo An undirected graph with edge list: [ [4, 1] , [1, 2] , [2, 3] , [3, 0] , [4, 0] , [2, 0], [4, 3] , [2, 5] , [5, 6] , [6, 7] , [7, 8] , [5, 8] , [5, 7] , [6, 8] ]. What is the diameter of this graph? Only provide a concrete number. 4] , [4, 5] , [5, 3] , [3, 1] , [0, 1], [5, 1] , [0, 3], [5, 2] , [2, 6] , [6, 7] , [7, 8] , [2, 8] , [2, 7] , [6, 8] ]. What is the diameter of this graph? Only provide a concrete number. (2) the output logits are determined by target node t and the current node v i-1 . Let N t,vi-1,u be the number of times in the training dataset such that t is the target node, v i-1 is the current node and v i = u is the next node. The optimal logits for predicting the next node u from current node v i-1 towards target node t is given by vi[u] = Nt,v i-1 ,u u Nt,v i-1 ,u if u N t,vi-1,u > 0. If u N t,vi-1,u = 0, vi [u] can be any non-negative number subject to u vi [u] = 1.Proof. We denote D as the training dataset, L i as the sequence length of the i-th sequence in the dataset, v i,j as the one hot embedding of the j-th token in the i-th training sequence, and vi,j,u as the u-th logit at the j-th token in the i-th sequence. The cross-entropy loss is given by- i∈[|D|] Li j=4 v i,j,u log vi,j,u = - i∈[|D|] Li j=4 I u=vi,j log vi,j,u (a) = - t,vj-1 u N t,vj-1,u log vi,j,u (b) = - t,vj-1,u u N t,vj-1,u N t,vj-1,u u N t,vj-1,u log vi,j,u ,where (a) uses the assumption that the output logits are determined by target node t and the current node v i-1 . In (b), we assume that u N t,vi-1,u ̸ = 0. The cross-entropy is minimized when vi,j,u = Nt,v j-1 ,u u Nt,v j-1 ,u . If u N t,vi-1,u = 0, then the corresponding logits will not affect the loss function and vi,j,u can take any number. In this subsection, we present the implementation details of training-free baselines, including LLM's direct inference, GraphSearch, and ours SGC. Method illustrations are shown in Figure 6 .The prompt template for LLM's direct inference is given in Table 4 . During experiments, we 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 are considered as candidates. These candidates are evaluated by LLM for their suitability for the current step (Task Assessment). The search process follows a depth-first approach. After the task assessment in the final step, a set of potential invocation paths is generated. Subsequently, LLM is prompted to select the most appropriate path from these options (Path Selection). The GraphSearch algorithm is implemented in three distinct variants, each employing a unique task selection strategy:• GreedySearch consistently selects the task node with the highest score at each step. Although fast and simple, this approach can lead to cascading errors, resulting in 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 to 3.• BeamSearch retains the top-k tasks based on 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 to 2.Ours SGC: Regarding the choices of LM backbones, for integrating GPT-3.5-turbo 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.Table 8 supplements Table 1 with other LLMs. The proposed methods perform consistently better. EQUATIONDue to 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.In this subsection, we present a comprehensive efficiency study on inference time of training-free methods and results are shown in Table 10 . Open-sourced LLMs were deployed as local API services using the FastChat framework4 on a 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-turbo 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 the task graph, impacting the efficiency. In contrast, SGC achieves comparable efficiency to LLM'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 as Mistral-7B's GreedySearch taking longer than other modes, may be attributed to variations in the deployment across different A100 services.Step LM and GNN Configuration: For training-based GNNs, we uniformly use the e5-335M model [62] as the LM backbone. For the graph encoder, our setup includes a single layer with a hidden dimension of 1024. During the model training, we set the batch size to 512 and run for 20 epochs with a learning rate of 1e -3. We use the Adam optimizer [25] and implement an early stopping mechanism with a patience of 5 epochs to prevent over-fitting. All experiments are conducted on a single NVIDIA A100-80G GPU.Training Data Preparation: 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 invocation 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 are selected based on how textually similar they are to the positive one, creating a robust differentiation challenge for the model.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. Illustrations 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 a learning rate of 2e -5 and a training duration of 10 epochs.We adapt TAPE [16] and GraphToken [38] as training-required baselines 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 a 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-ofthought reasoning, to understand each request. Then, a fine-tuned LM encodes these 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 a fair performance comparison, we fine-tune the LM as e5-335M and configure the GNN as a 2-layer GraphSAGE with a hidden dimension of 11 ), 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.GraphToken: For adapting GraphToken, we first encode the task graph G(V, E, X) by computing each node's representation x v by feeding its descriptive text into the pre-trained LM, e5-335M. Then, a GNN transforms the initial node embedding matrix into H. The GNN is configured as a 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 h G = Mean-Pooling(H). Finally, both h G 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 4 epochs using the same 3, 000 training samples consisting of <user request, ground-truth planning> pairs. The batch size is set to 16, with a maximum input length of 512 and a maximum output length of 300 for HuggingFace and Multimedia datasets, and 600 for DailyLife dataset. The learning rate is configured to 1e -5.To explore the effectiveness of our proposed framework on fine-tuned LLMs, we employ Supervised Fine-Tuning (SFT) on 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 a larger number of tasks and require longer textual inputs, we set the maximum input and output length to 1000 and 500, respectively. We utilize 2 NVIDIA A100-80G GPUs for fine-tuning the LLMs.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 baseline, 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.83%, GAT contributes to a 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. 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 a 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 in 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 a specific LLM on any dataset remaining within 2%.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 . Effectiveness of GNNs: 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.Failure Cases 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 to the sequential selection of tasks on 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 Classification instead of the correct Image Segmentation. Since tasks are selected sequentially on the task graph, where the next task is a neighbor of the current selection, such an 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.Diagnosing GraphSearch with GPT-4-turbo: 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. • Maintaining Cases: These occur when GraphSearch merely replicates the result of LLM's direct inference, indicating no 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.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.Convert the text "I love nature" into speech audio, classify the audio. Finally, generate an image according to the audio classification result.Text-to-Speech Automatic Speech Recognition Image Generation In this paper, we did not use any non-public data, unauthorized software, or 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 to be used for malicious attacks. We pledge to restrict the usage of our model exclusively to the realm of research to prevent such misuse.• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).https://github.com/lm-sys/FastChat 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. Combining LLM with GNN for graph-related tasks has been studied in many previous works and is not very novel.
questions: questions: N/A
limitations: limitations: Yes
paper_summary: paper_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).
strength_weakness: strength_weakness: 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).

I 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).

While 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. 

I 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.

It 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.
questions: questions: See each point in weaknesses, especially the third, fourth and fifth paragraphs.
limitations: limitations: See previous points.
paper_summary: paper_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.
strength_weakness: strength_weakness: The paper has some clarity problems, as both the problem statement and the methodology of the paper is not clear without several rereads.

1. 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.

2. 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.

3. "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.

4. 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.
- Sam Toyer, Sylvie Thiébaux, Felipe W. Trevizan, Lexing Xie: ASNets: Deep Learning for Generalised Planning. J. Artif. Intell. Res. 68: 1-68 (2020)
- William Shen, Felipe W. Trevizan, Sylvie Thiébaux: Learning Domain-Independent Planning Heuristics with Hypergraph Networks. ICAPS 2020: 574-584
- Simon Ståhlberg, Blai Bonet, Hector Geffner: Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits. ICAPS 2022
- Jiayuan Mao, Tomás Lozano-Pérez, Joshua B. Tenenbaum, Leslie Pack Kaelbling: What Planning Problems Can A Relational Neural Network Solve? NeurIPS 2023
- Dillon Ze Chen, Sylvie Thiébaux, Felipe W. Trevizan: Learning Domain-Independent Heuristics for Grounded and Lifted Planning. AAAI 2024

Other comments and suggestions:
- 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. 
- (1) is an MPNN
- 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? 
- Figure 2: typos in legend. hallucination ratio not defined nor referenced anywhere in the text
- Theorem 1: assumptions should not be listed in the appendix, and instead should be given before the statement of the theorem
- F1-scores do not measure accuracy
questions: questions: 1. What is meant by "fulfils the users' requests"? Is this a classification problem, or a constraint satisfaction problem?
2. What is the explicit graph encoding (nodes, edges, features) of the problem for use with the GNNs?
3. Why are RestBench results only shown the no training results (Table 1) and not Table 2?
limitations: limitations: The authors addresses some limitations.
- The work requires graphs to be part of the input problem.
- 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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].

- 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?

- 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.

- 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.

- 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?

- 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.

[1] Yasunaga, Michihiro, et al. "Deep bidirectional language-knowledge graph pretraining." Advances in Neural Information Processing Systems 35 (2022): 37309-37323.

[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.

[3] Perozzi, Bryan, et al. "Let Your Graph Do the Talking: Encoding Structured Data for LLMs." arXiv preprint arXiv:2402.05862 (2024).
questions: questions: please see above
limitations: limitations: yes

Comments: comment: We would like to express our sincere gratitude for the time and effort you dedicated to reviewing our manuscript. Your insightful feedback has strengthened the experiments of this paper. We truly appreciate your contributions to the improvement of our work.
Thanks for the reply. I will keep my positive score.
Dear Reviewer,

Thank you for your thorough review and insightful suggestions. Your comments have been invaluable in refining our paper.
We appreciate your positive reception of our rebuttal and are glad that our response has addressed your concerns. We are committed to carefully revising the manuscript according to your feedback.

Thank you again for your constructive review.

Warm regards,

The Authors
We thank the authors for their response and answers in response to the weaknesses and questions I pointed out in the review, namely

(1) clarity of the problem statement and technical details in the methodology, and

(2) ambiguity of the definition of "task planning", namely whether the problem is concerned with natural language or symbolic problem statements.

The authors sufficiently address these weaknesses in their rebuttal, alongside the other minor comments, and I trust that authors are able to address them in the final version of the paper.
Dear Reviewer,

We greatly appreciate your insightful suggestions and comments, which have significantly contributed to the refinement of our paper. We are also thankful for your acknowledgment of our rebuttal efforts.

Regarding the first question, we thank you for bringing this important reference to our attention and will discuss it in the revised manuscript. The issues investigated in [1]—Multiplication, Einstein’s Puzzle, and Maximum Weighted Independent Set on a sequence of integers—are not traditionally defined as graph problems because they do not involve graphs as inputs. Instead, they conceptualize the computations as computation graphs, similar to the computation graph taken by Pytorch. 

In response to the second question, our application takes a task graph and a user request in natural language as inputs, and produces a path on the task graph as the output. The ability to accurately interpret the task graph input is therefore crucial. Our experiments reveal that LLMs often hallucinate about non-existent nodes and edges, or the generation of disconnected paths. This suggests that (1) LLMs struggle to understand task graph inputs and (2) enhancing LLMs' graph comprehension could improve their application in task planning. Consequently, we explore the reasons behind LLMs' difficulties with task graph comprehension in Section 3.2.

Regarding the over-claiming concerns raised by Reviewer xcxm, there is a field known as task planning in both traditional AI and language agents. While they share the same name, they are distinct areas. We did not realize that there is an area called task planning in traditional AI until it was highlighted by the reviewer. The references cited by Reviewer xcxm pertain to task planning in traditional AI, whereas our paper addresses task planning in language agents. Following the rebuttal to Reviewer xcxm, we will revise our title and statements to avoid confusion. 

If you have a different perspective, please feel free to share it with us, and we would be happy to address it during the discussion period.

Warm regards,

The Authors
I would like to thank the authors for their detailed response.

- In the global comment, the authors claim that *this is the first attempt to theoretically understand the fundamental limits of LLMs in this application (or more broadly, in LLMs for graph problems)*. I wonder if [1] might weaken this claim.

- Again "improving LLMs for planning" and "studying the fundamental limits of transformers/LLMs in graphs" are two separate research question. I'm not sure the value of having part #2 in this part #1-centric work and how it benefits planning.

Other than that, reviewer xcxm do raise many valid points, especially how this work might be over-claiming on several fronts regarding existing literature and I share these concerns. I'm upping my score to 5 at the moment, but not sure if I'm comfortable championing without reviewer xcxm's response.

[1] Dziri, Nouha, et al. "Faith and fate: Limits of transformers on compositionality." NeurIPS 2023