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

arXiv: https://arxiv.org/abs/2608.07905 · HTML: https://mlsanity.com/paper/2608.07905/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Spatial and embodied reasoning, one of 17 directions in LLM reasoning.
- Builds on 45 of its 50 references that are in the map.
- First posted on arXiv 8 Aug 2026.

## Placed in

- LLM reasoning / [Spatial and embodied reasoning](https://mlsanity.com/lr/spatial-and-embodied-reasoning/)

## Builds on (most cited first, 30 of 45)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [AI2-THOR: An Interactive 3D Environment for Visual AI](https://mlsanity.com/paper/1712.05474/) (2017)
- [ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks](https://mlsanity.com/paper/1912.01734/) (2019)
- [CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing](https://mlsanity.com/paper/2305.11738/) (2023)
- [ProgPrompt: Generating Situated Robot Task Plans using Large Language Models](https://mlsanity.com/paper/2209.11302/) (2022)
- [LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language Models](https://mlsanity.com/paper/2212.04088/) (2022)
- [VirtualHome: Simulating Household Activities via Programs](https://mlsanity.com/paper/1806.07011/) (2018)
- [ConceptGraphs: Open-Vocabulary 3D Scene Graphs for Perception and Planning](https://mlsanity.com/paper/2309.16650/) (2023)
- [ToolRL: Reward is All Tool Learning Needs](https://mlsanity.com/paper/2504.13958/) (2025)
- [SayPlan: Grounding Large Language Models using 3D Scene Graphs for Scalable Robot Task Planning](https://mlsanity.com/paper/2307.06135/) (2023)
- [Logic-RL: Unleashing LLM Reasoning with Rule-Based Reinforcement Learning](https://mlsanity.com/paper/2502.14768/) (2025)
- [You Only Look at Screens: Multimodal Chain-of-Action Agents](https://mlsanity.com/paper/2309.11436/) (2023)
- [VLABench: A Large-Scale Benchmark for Language-Conditioned Robotics Manipulation with Long-Horizon Reasoning Tasks](https://mlsanity.com/paper/2412.18194/) (2024)
- [Episodic Transformer for Vision-and-Language Navigation](https://mlsanity.com/paper/2105.06453/) (2021)
- [Embodied Agent Interface: Benchmarking LLMs for Embodied Decision Making](https://mlsanity.com/paper/2410.07166/) (2024)
- [FILM: Following Instructions in Language with Modular Methods](https://mlsanity.com/paper/2110.07342/) (2021)
- [A Persistent Spatial Semantic Representation for High-level Natural Language Instruction Execution](https://mlsanity.com/paper/2107.05612/) (2021)
- [LoTa-Bench: Benchmarking Language-oriented Task Planners for Embodied Agents](https://mlsanity.com/paper/2402.08178/) (2024)
- [SPOC: Imitating Shortest Paths in Simulation Enables Effective Navigation and Manipulation in the Real World](https://mlsanity.com/paper/2312.02976/) (2023)
- [Prompter: Utilizing Large Language Model Prompting for a Data Efficient Embodied Instruction Following](https://mlsanity.com/paper/2211.03267/) (2022)
- [Context-Aware Planning and Environment-Aware Memory for Instruction Following Embodied Agents](https://mlsanity.com/paper/2308.07241/) (2023)
- [Search3D: Hierarchical Open-Vocabulary 3D Segmentation](https://mlsanity.com/paper/2409.18431/) (2024)
- [Factorizing Perception and Policy for Interactive Instruction Following](https://mlsanity.com/paper/2012.03208/) (2020)
- [EPO: Hierarchical LLM Agents with Environment Preference Optimization](https://mlsanity.com/paper/2408.16090/) (2024)
- [Look Wide and Interpret Twice: Improving Performance on Interactive Instruction-following Tasks](https://mlsanity.com/paper/2106.00596/) (2021)
- [AMOR: A Recipe for Building Adaptable Modular Knowledge Agents Through Process Feedback](https://mlsanity.com/paper/2402.01469/) (2024)

## Abstract (arXiv)

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.