GraphThink: Graph-Enhanced LLM Thinking for Long-Horizon Embodied Task Planning

• URL: http://arxiv.org/abs/2608.07905v1
• Date: Sat, 08 Aug 2026 04:05:05 GMT
• Title: GraphThink: Graph-Enhanced LLM Thinking for Long-Horizon Embodied Task Planning
• Abstract summary: Embodied agents using LLM-based planners often struggle with physical hallucinations, poor generalization to long-horizon tasks, and lack of environmental awareness.<n>We propose GraphThink, a novel framework that integrates a task graph to provide structured knowledge for robust planning and a scene graph to maintain environmental memory for event-driven replanning.
• Score: 25.193747277080394
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Embodied agents using LLM-based planners often struggle with physical hallucinations, poor generalization to long-horizon tasks, and lack of environmental awareness. We propose GraphThink, a novel framework that integrates a task graph to provide structured knowledge for robust planning and a scene graph to maintain environmental memory for event-driven replanning. Specifically, the task graph guides LLM thinking through contextual prompting and iterative refinement, effectively mitigating planning hallucinations. Furthermore, within the GRPO framework, the task graph offers delicate reward design to train the LLM planner, enhancing long-horizon planning capabilities and improving generalization. Finally, an event-driven replanning module, powered by the scene graph, enables closed-loop environment awareness and error correction. GraphThink achieves state-of-the-art performance on the ALFRED benchmark. In particular, our high-level planner surpasses leading API-based LLMs on both the validation set and held-out long-horizon tasks, underscoring its robust zero-shot and few-shot capabilities. Additional evaluations further demonstrate strong out-of-distribution generalization to novel tasks and environments.

Related papers

• PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Models [52.48858778580074]
  Planning is a fundamental capability for large language models (LLMs)<n>PlanningBench is a framework for generating scalable, diverse, verifiable planning data for both evaluation and training.
  arXiv  Detail & Related papers  (2026-05-20T08:10:15Z)
• Embodied Task Planning via Graph-Informed Action Generation with Large Lanaguage Model [6.302973995986435]
  GiG is a novel planning framework that structures embodied agents' memory using a Graph-in-Graph architecture.<n>By clustering these graph embeddings, the framework enables retrieval of structure-aware priors.<n>We evaluate our framework on three embodied planning benchmarks-Robotouille Synchronous, Robotouille Asynchronous, and ALFWorld.
  arXiv  Detail & Related papers  (2026-01-29T15:18:58Z)
• Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks [36.63527489464188]
  Plan-and-Act is a framework that incorporates explicit planning into large language models (LLMs)<n>Plan-and-Act consists of a Planner model which generates structured, high-level plans to achieve user goals, and an Executor model that translates these plans into environment-specific actions.<n>We present a state-of-the-art 57.58% success rate on the WebArena-Lite benchmark as well as a text-only state-of-the-art 81.36% success rate on WebVoyager.
  arXiv  Detail & Related papers  (2025-03-12T17:40:52Z)
• Plan-over-Graph: Towards Parallelable LLM Agent Schedule [53.834646147919436]
  Large Language Models (LLMs) have demonstrated exceptional abilities in reasoning for task planning.<n>This paper introduces a novel paradigm, plan-over-graph, in which the model first decomposes a real-life textual task into executable subtasks and constructs an abstract task graph.<n>The model then understands this task graph as input and generates a plan for parallel execution.
  arXiv  Detail & Related papers  (2025-02-20T13:47:51Z)
• Vote-Tree-Planner: Optimizing Execution Order in LLM-based Task Planning Pipeline via Voting [4.500734889060007]
  This paper addresses the synergy between large language models (LLMs) and task planning systems.<n>We propose Vote-Tree-Planner to minimize redundancy while enhancing planning effectiveness.
  arXiv  Detail & Related papers  (2025-02-13T20:08:06Z)
• VeriGraph: Scene Graphs for Execution Verifiable Robot Planning [33.8868315479384]
  We propose VeriGraph, a framework that integrates vision-language models (VLMs) for robotic planning while verifying action feasibility. VeriGraph employs scene graphs as an intermediate representation, capturing key objects and spatial relationships to improve plan verification and refinement. Our approach significantly enhances task completion rates across diverse manipulation scenarios, outperforming baseline methods by 58% for language-based tasks and 30% for image-based tasks.
  arXiv  Detail & Related papers  (2024-11-15T18:59:51Z)
• Dynamic Planning for LLM-based Graphical User Interface Automation [48.31532014795368]
  We propose a novel approach called Dynamic Planning of Thoughts (D-PoT) for LLM-based GUI agents.<n>D-PoT involves the dynamic adjustment of planning based on the environmental feedback and execution history.<n> Experimental results reveal that the proposed D-PoT significantly surpassed the strong GPT-4V baseline by +12.7%.
  arXiv  Detail & Related papers  (2024-10-01T07:49:24Z)
• AgentGen: Enhancing Planning Abilities for Large Language Model based Agent via Environment and Task Generation [81.32722475387364]
  Large Language Model-based agents have garnered significant attention and are becoming increasingly popular.<n>Planning ability is a crucial component of an LLM-based agent, which generally entails achieving a desired goal from an initial state.<n>Recent studies have demonstrated that utilizing expert-level trajectory for instruction-tuning LLMs effectively enhances their planning capabilities.
  arXiv  Detail & Related papers  (2024-08-01T17:59:46Z)
• Learning to Plan for Retrieval-Augmented Large Language Models from Knowledge Graphs [59.76268575344119]
  We introduce a novel framework for enhancing large language models' (LLMs) planning capabilities by using planning data derived from knowledge graphs (KGs) LLMs fine-tuned with KG data have improved planning capabilities, better equipping them to handle complex QA tasks that involve retrieval.
  arXiv  Detail & Related papers  (2024-06-20T13:07:38Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is 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.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• DELTA: Decomposed Efficient Long-Term Robot Task Planning using Large Language Models [5.385540718118656]
  Large Language Models (LLMs) have sparked a revolution across many research fields.<n>Despite their vast collection of knowledge, large language models may generate infeasible plans due to hallucinations or missing domain information.<n>We introduce DELTA, a novel LLM-informed task planning approach.
  arXiv  Detail & Related papers  (2024-04-04T07:59:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.