Can Graph Learning Improve Planning in LLM-based Agents?

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.

Strengths

+ the intersection of LLMs and graphs is interesting + task planning is an important problem

Weaknesses

- It would be nice to present a figure/clear description of how LLMs and GNNs are integrated for task planning, somewhere in Section 4. For now it seems that Sec 4.2&4.3 focus on details of existing GNN proposals, which is not the technical contribution of this work, so it might make more sense to better highlight the unique way of composing them. - 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

please see above

Rating

5

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

yes

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.

Strengths

The results highlight that the approach makes sense and work, with improvements across benchmarks. The paper provides some theory albeit simple and straightforward: graphs encoded as input strings into transformers are limited in expressiveness.

Weaknesses

The paper has some clarity problems, as both the problem statement and the methodology of the paper is not clear without several rereads. 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

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?

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

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.

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

Strengths

The general problem is well formulated and the motivation behind GNNs to improve transformers on graph planning easy to follow. Section 3.1 (but not Figure 2) do a good job at describing the hallucination issue and the potential mitigations introduced by GNNs (my understanding is because they have grounded access to the true task graph). Results suggest that GNNs improve performance on task planning, both in training and training-free regime.

Weaknesses

Figure 2 is problematic. It is never referenced in the paper and there is no reference to the dataset used and how the task is specified (I assume is the same setting as HuggingGPT, but just because it appears in the same section). 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

See each point in weaknesses, especially the third, fourth and fifth paragraphs.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

See previous points.

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.

Strengths

1. The paper provides a solid theoretical analysis of LLMs understanding graph-structured inputs, which is inspiring for future works. 2. The proposed method is effective for task planning. 3. The paper is well-written and easy to follow.

Weaknesses

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

Questions

N/A

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes