We sincerely thank the reviewer for your insightful and constructive feedback.

---

Weakness 1: Methodology figure

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

Weakness 2: Comparison to related works [Ref A-C]

Thank 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:

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

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.

Weakness 3: Rationale for the two-stage algorithm

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

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

Weakness 4: Qualitative analysis for the improved stage 2

We will move Figure 9 on Page 24 to the main paper, where GNNs successfully correct paths that LLMs fail to generate.

Weakness 5: Mismatch between Section 3.1 and 3.2.

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

Weakness 6: Missing GPT-4 in Figure 2

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

Weakness 7: Vagueness of "graph learning"

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

---

[Ref A] Yasunaga, Michihiro, et al. "Deep bidirectional language-knowledge graph pretraining." NeurIPS 2022.

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

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

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

We sincerely thank the reviewer for the insightful and constructive feedback.

---

Weakness 1, 3, 4 and Question 1: Definition of task planning and user request; Task planning and PDDL; Related work concerning GNNs for PDDL

This paper investigates task planning for language agents, a new and increasingly important application area with the development of LLMs [30, 14, 43].

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.

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.

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

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

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

Weakness 2 and Question 2: Details of Framework

Due to rebuttal space limitations, please refer to Weakness 5 of Reviewer ZJrg for the answer.

The theory is straightforward

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

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

Question 3: No RestBench results in Table 2

As mentioned in Line 289-290, RestBench has only 100 data samples, which limits effective model training.

(1) is an MPNN and define "\oplus is an operator" more rigorously

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

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

Definition of hallucination ratio

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

Assumptions should be put in main text

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

Missing accuracy

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

The work requires graphs to be part of the input problem

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

Error bar

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

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 sincerely thank the reviewer for your insightful comments and recognition of this work, especially for the motivation to adopt GNNs in this new application.

---

Weakness 1: Figure 2 is never referenced

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

Weakness 2: Representation of graph in Eq. 3

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

Weakness 3: One may choose larger Transformers and definition of O(logn)

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

Weakness 4: Theorem 2 and Example 1

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

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.

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

Weakness 5: how GNN is combined with LLMs.

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.

Then we provide the detailed GNN encoding process:

• 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)$.
• 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.

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

Thank you for pointing out the confusion, and we will improve the technical presentation accordingly.

---

[Ref A] Boshi Wang, et al. "Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization." arXiv:2405.15071.

[Ref B] William Merrill, and Ashish Sabharwal. "The parallelism tradeoff: Limitations of log-precision transformers." TACL 2023.

We sincerely thank the reviewer for your insightful comments and recognition of this work, especially for acknowledging our theoretical contributions and superior performance.

---

Combining LLM with GNN for graph-related tasks has been studied in many previous works and is not very novel.

Thank you for helping us to clarify this point.

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

---

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