Research map / Graph learning / GNN architectures
Can Graph Learning Improve Planning in LLM-based Agents?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes integrating GNNs (training-free SGC and trained GraphSAGE) with LLMs to retrieve sub-tasks on task graphs for LLM task planning, motivated by theoretical limits of Transformers on edge-list graph input.
Problem
LLM-based task planning in language agents requires selecting paths/subgraphs on a task graph, but LLMs hallucinate nodes/edges and degrade as task graphs grow; flattened edge-list input and auto-regressive loss limit their graph reasoning.
Approach
Keep the LLM for request decomposition, then use a GNN over text-attributed task graph embeddings (e5-335M node features) to greedily select each sub-task along graph neighbors; parameter-free SGC works zero-shot, and GraphSAGE trained with BPR loss improves further.
Key results
- Training-free SGC with GPT-4-turbo reaches 77.79 n-F1 on TaskBench HuggingFace vs 77.60 direct, and uses ~2K tokens vs ~9K for BeamSearch; SGC matches or beats BeamSearch across LLMs at 5-10x fewer tokens.
- Training-based GraphSAGE raises GPT-3.5-turbo HuggingFace n-F1 from 73.85 to 77.90 and Acc from 28.95 to 35.11.
- On UltraTool (260 nodes), GraphSAGE gives GPT-4-turbo a 9.05% accuracy improvement, with gains increasing with task graph size.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use training-free SGC retrieval instead of direct inference | GPT-3.5-turbo · HuggingFace | n-F1: 73.85 -> 76.37 | Helped |
| Use training-free SGC retrieval instead of direct inference | GPT-3.5-turbo · HuggingFace | l-F1: 45.73 -> 50.04 | Helped |
| Use training-free SGC retrieval instead of direct inference | GPT-3.5-turbo · Multimedia | n-F1: 82.85 -> 83.65 | Helped |
| Use training-free SGC retrieval instead of direct inference | GPT-3.5-turbo · Multimedia | l-F1: 62.07 -> 63.65 | Helped |
| Use training-free SGC retrieval instead of direct inference | GPT-3.5-turbo · Daily Life | n-F1: 96.09 -> 96.38 | Helped |
| Use training-free SGC retrieval instead of direct inference | GPT-3.5-turbo · Daily Life | l-F1: 83.65 -> 86.19 | Helped |
| Use training-free SGC retrieval instead of direct inference | GPT-3.5-turbo · TMDB | n-F1: 81.70 -> 82.63 | Helped |
| Use training-free SGC retrieval instead of direct inference | GPT-3.5-turbo · TMDB | l-F1: 57.52 -> 59.15 | Helped |
| Train GraphSAGE for task retrieval instead of direct inference | GPT-3.5-turbo · HuggingFace | n-F1: 73.85 -> 77.90 | Helped |
| Train GraphSAGE for task retrieval instead of direct inference | GPT-3.5-turbo · Multimedia | n-F1: 82.85 -> 85.29 | Helped |
| Train GraphSAGE for task retrieval instead of direct inference | GPT-3.5-turbo · Daily Life | n-F1: 96.09 -> 96.43 | Helped |
| Co-train e5-335M with GraphSAGE rather than training GraphSAGE alone (ablation) | GPT-3.5-turbo · HuggingFace | n-F1: 77.90 -> 77.87 | No clear effect |
Surprising findings
- GPT-4-turbo gains only marginally from the GNN on TaskBench, possibly due to pretraining exposure to these platforms or the weak e5-335M encoder.
- Fine-tuned LLM planning is inferior to GNNs trained on the same data, which the authors attribute to auto-regressive loss spurious correlations.
Limitations
- The proposed GNN method is simple; more sophisticated graph decision-making algorithms are not explored.
- Task graph construction currently requires manual effort.
- Gains with GPT-4-turbo are marginal, and the e5-335M encoder may be too weak for GPT-4 outputs.
Experimental setup
Datasets: TaskBench HuggingFace TaskBench Multimedia TaskBench Daily Life RestBench TMDB UltraTool
Benchmarks: TaskBench HuggingFace TaskBench Multimedia TaskBench Daily Life RestBench TMDB UltraTool
Metrics: Node F1 Link F1 Accuracy token consumption
Baselines: Direct inference GreedySearch AdaptiveSearch BeamSearch TAPE GraphToken GraphSearch
Builds on: HuggingGPT SGC BPR TAPE GraphToken
Closest papers by meaning
- GPTSwarm: Language Agents as Optimizable Graphs (ICML 2024 · similarity 0.89)
- $\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
- Graph-enhanced Large Language Models in Asynchronous Plan Reasoning (ICML 2024 · similarity 0.89)
- Graph-of-Agents: A Graph-based Framework for Multi-Agent LLM Collaboration (ICLR 2026 · similarity 0.88)
- Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models (ICML 2024 · similarity 0.88)
- GraphRouter: A Graph-based Router for LLM Selections (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.