Skip to content

GAVEL: Graph World Models for Verified and Efficient Long-Horizon LLM Task Planning

Sep 2026 · arXiv.org · Vol abs/2609.19315 · 0 citations · 29 references
Computer Science

TL;DR

Improvements show that an explicit graph world model harness can substantially improve the reliability and efficiency of long-horizon embodied planning across compact and frontier hosted LLM capabilities.

Abstract

Large language models (LLMs) provide a flexible interface for long-horizon robot planning, but generated plans often fail to respect embodiment constraints, recover from planning errors, or reason effectively under partial observability. We present GAVEL, a framework for verifying and repairing long-horizon LLM planning built around an explicit graph world model. The graph represents relevant object-relations, action pre-conditions and effects, and probabilistic beliefs over unobserved object locations. This model can predict the consequences of LLM-generated actions before execution, detect violations, and repair those whose corrections follow directly from the world model. This method also reserves LLM replanning solely for errors requiring semantic reasoning. For multi-task instructions, GAVEL reasons over distributions of possible object locations to reorder remaining subtasks and minimize expected search cost. We evaluate GAVEL on BEHAVIOR-1K across 100 single long-horizon tasks and 500 multi-task instructions. With Qwen3-8B, GAVEL improves single-task success from 41.2% to 91.8% and multi-task success from 19.9% to 92.6%. Distributional belief reasoning also reduces travel distance by approximately 5.4% compared with a static variant. These improvements show that an explicit graph world model harness can substantially improve the reliability and efficiency of long-horizon embodied planning across compact and frontier hosted LLM capabilities.

View source

Similar papers

Preprint Sep 2026

Safe Task Planning with Long-Term Graph Memory for Embodied Agents

A novel safe task-planning framework, SafeMem, which constructs and maintains a long-term semantic graph memory of the open and dynamic environment, and substantially improves safe success rates compared to state-of-the-art VLM-driven task planners.

Si-Yuan Li, Tai-Yan Lang, Ao Yan et al. · 1 citation
#artificial intelligence Preprint Sep 2026

X-Planner: Event-Structured Task Planning for Embodied Intelligence

Task planning bridges high-level instructions and executable behavior in long-horizon manipulation, yet modern Vision-Language-Action (VLA) systems often leave this intermediate structure implicit. Existing chain-of-thought (CoT) planners also tend to rely on coarse task-level annotations or serialize long reasoning tr...

Howard Lu, Shalfun Li, Porter Pan et al. · 0 citations

SAGE: Symbolic Action-Gating and Editing for LLM Task Planners

SAGE (Symbolic Action-Gating and Editing), a single-LLM planner built from two lightweight mechanisms: a domain-agnostic symbolic gate that blocks precondition-violating actions with typed reasons as a runtime safety monitor, and a local edit that regenerates only the failed sub-goal's suffix, keeping completed and unt...

T. Bui, Jongsul Moon, Youngouk Kim et al. · 0 citations
#robotics Preprint Aug 2026

Evidence-Gated Task and Motion Planning with Vision-Language Models

Evidence Acquisition and Feasibility Gating (EAFG) is proposed, a framework that acquires visual evidence through VLM-generated exploratory subgoals and TAMP-based execution and applies a feasibility gate to decide whether to proceed with task planning, acquire further evidence, or halt.

Tsunehiko Tanaka, Matthew Stephenson, Alistair Macvicar et al. · 0 citations
#artificial intelligence Preprint Sep 2026

SGG-ReflAct: Sub-Goal Guided ReflAct with Structured Planning for Reliable Long-Horizon Reasoning

SGG-ReflAct (Sub-Goal Guided Re flAct), a reasoning backbone that integrates sub-goals generated through a single path LLM planner into the reflection process, and BeamSGG-ReflAct, which replaces the single-path planner with a beam search based LLM planner for structured plan exploration.

Jaeho Jung, Sung-Hoon Jung · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.