PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ruiyang Wang, Hao-Lun Hsu, Swarajh Mehta, Jiwoo Kim, Zhihao Dou, Miroslav Pajic

arXiv:2609.19315v1cs.ROcs.AI

TL;DR

Long-horizon LLM plans may be inconsistent with action constraints, while uncertain object locations complicate multi-task ordering. GAVEL uses a graph world model to verify and repair plans, and to reorder tasks from location beliefs; reported results show benefits across task success and execution efficiency.

  • Problem

    LLM plans can violate action constraints, while collapsing location beliefs to their most likely outcome and fixing task order leaves information about uncertain objects unused.

    Source: §I · p. 1

  • Method

    GAVEL rolls LLM plans through an explicit graph world model, repairs failures implied by action semantics, and uses full object-location distributions to re-optimize task order online.

    Source: §I · p. 2, §VI · p. 8

  • Results

    GAVEL improves task success across single-task and multi-task settings, while full-distribution online reordering reduces traveled distance by approximately 5.4%.

    Source: §VI · p. 8

  • Takeaways & Limitations

    World-model reasoning complements LLM scaling: Qwen3-4B with GAVEL outperforms stronger hosted planners used alone, and both hosted models reach near-perfect success with GAVEL.

    Source: §VI · p. 8

Abstract

from arXiv · show

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.

I. INTRODUCTION

GAVEL uses an explicit graph world model to verify LLM plans, repair failures implied by modeled action semantics, and reason over uncertain object locations when ordering tasks. It targets executable long-horizon planning while reserving LLM replanning for failures requiring semantic reasoning.

I. INTRODUCTION

  • Standalone LLM plans may omit prerequisites, violate embodiment constraints, or fail to reach the intended state, motivating explicit pre-execution verification.The introduction notes that LLM failure rates grow with planning horizon, particularly for compact models.Source: §I · p. 1
  • Graph-derived repairs can avoid unnecessary LLM calls when a violated action precondition directly determines the correction.A failed grasp caused by insufficient proximity can be corrected from the graph’s modeled state transition.Source: §I · p. 1
  • Full object-location distributions support online task reordering because searching for one object updates beliefs about others and can change which subtask is cheapest next.The contribution describes converting these beliefs into expected search cost and re-optimizing the remaining task order.Source: §I · pp. 1–2
  • GAVEL rolls LLM-generated actions through a graph world model, verifies preconditions, goals, and safety, and repairs model-derivable failures while reserving semantic failures for the LLM.The graph also maintains distributions over unseen object locations and updates task order as observations arrive.Source: §I · pp. 1–2
  • BEHAVIOR-1K evaluation across single long-horizon tasks and partially observed multi-task instructions reports substantial gains in task success and execution efficiency.The introduction says the results span local and hosted LLMs and show world-model reasoning complements increased LLM capability.Source: §I · p. 2

B. Scene-Graph Grounding and Verification

GAVEL treats the scene graph as a world model that represents action transitions and uncertainty, rather than only as a pre-execution verifier. Its planning problem couples checking whether LLM plans are executable with minimizing expected execution distance as observations update uncertain object locations.

B. Scene-Graph Grounding and Verification

C. Graph Planning under Partial Observability

  • GAVEL retains distributions over unseen object locations and uses them to estimate execution costs and re-optimize task order online, building on semantic room-location beliefs.This contrasts with approaches that collapse beliefs to a most-likely location and fix task order at initialization.Source: C. Graph Planning under Partial… · p. 2

A. Problem Statement

  • The typed scene graph represents rooms, task-relevant objects, their relations, and unary states, while grounded actions have graph-valued preconditions and effects for predicting transitions.The plan is applicable when each action satisfies its preconditions along the induced trace.Source: A. Problem Statement · p. 2
  • The formulation assumes task goal-object sets are disjoint, so task order affects execution cost rather than goal feasibility, although subplans can interact through auxiliary objects or state changes.The problem couples plan executability checks with execution-cost changes as uncertain object locations are revealed.Source: A. Problem Statement · p. 3

B. Belief-Aware Task Ordering

GAVEL orders remaining tasks by estimated expected travel cost under the current belief about object locations. It executes the first task, incorporates observations, and recomputes the order.

B. Belief-Aware Task Ordering

  • For unlocalized objects, expected search cost uses the belief over reachable candidate rooms and accounts for travel distance and room-search effort.Room-search effort is approximated using traversable area and sensor coverage width.Source: B. Belief-Aware Task Ordering · p. 3
  • GAVEL approximates an ordering’s expected execution cost from the expected cost of doing its first task and the expected cost of each subsequent task transition.It chooses the minimum-cost ordering under the current belief.Source: B. Belief-Aware Task Ordering · p. 3
  • After executing only the first task of the minimum-cost ordering, GAVEL updates beliefs from observations and recomputes the remaining order; experiments enumerate permutations exactly for N ≤ 5.Constructing the task-cost estimates requires O(N^2) belief-conditioned rollouts.Source: B. Belief-Aware Task Ordering · p. 3

A. System Overview

GAVEL combines LLM-generated task plans with graph-world-model verification and repair, while beliefs are updated and task order is reconsidered online. Task understanding extracts relevant objects, relations, and goals to initialize the graph and represent task completion.

A. System Overview

  • The pipeline decomposes an instruction into tasks, extracts goals, assigns RSN location beliefs to uncertain objects, and has an LLM generate plans for graph verification and repair before execution.After observations, it updates beliefs and reorders remaining tasks.Source: A. System Overview · p. 3, Figure 2 · p. 4

B. Task Understanding

  • For each task, lightweight Qwen3-1.7B adapters extract relevant objects and explicit relations for the belief graph, and parse a partial-graph goal state.Spatial predicates and semantic states can represent goal conditions; the adapters are trained on 8,000 synthetic instruction–target pairs with a disjoint 500-instruction validation set.Source: B. Task Understanding · p. 4

C. Belief Initialization

GAVEL initializes room-location beliefs for uncertain objects, obtains one action sequence per decomposed task from an LLM, and uses a graph world model to represent action consequences and constraints.

C. Belief Initialization

  • A Relational Semantic Network predicts room-type scores for uncertain objects, which GAVEL distributes uniformly among reachable instances of each type and normalizes over reachable rooms.The RSN uses a frozen text encoder and an MLP trained on scene object placements, with Platt scaling for calibration.Source: C. Belief Initialization · p. 4

D. LLM Action Planning

  • Given the instruction, believed graph, predicted location beliefs, task goals, and action definitions, a single LLM query produces a grounded action sequence for each decomposed task.The graph validates and repairs each sequence; unresolved violations are returned to the LLM for another attempt, up to a call budget.Source: D. LLM Action Planning · p. 4

E. Graph World Model

  • The graph world model represents grounded actions with preconditions and effects, checking proximity, affordance, gripper state, and container accessibility before modeling state changes and restoration constraints.Effects include grasping, placement, and appliance-induced states; opened containers and safety-critical appliances must be restored to their required state.Source: E. Graph World Model · p. 5

F. Plan Validation and Repair

GAVEL rolls candidate plans forward on the graph, checks applicability, goal completion, and safety, then applies model-derived edits when possible and sends unresolved failures to the LLM.

F. Plan Validation and Repair

  • GAVEL applies each action only when its preconditions hold, stops rollout at the first violation, and checks the resulting graph against the goal and trace-level safety constraints.The validator returns a structured verdict covering applicability failures, unmet goals, and safety violations.Source: F. Plan Validation and Repair · p. 5
  • REPAIR recursively applies corrections implied by the action model, such as navigating before a failed grasp or opening a closed container, and returns unresolved violations to the LLM.A visited-plan set prevents cyclic repair; restoration actions address safety violations.Source: F. Plan Validation and Repair · p. 5
  • When edits do not monotonically improve a plan, GAVEL retains the best previous candidate; its ranking accounts for applicability, goal completion, safety, and execution cost.The LLM-call budget limits generations, while graph-derived repair can make multiple edits between queries.Source: F. Plan Validation and Repair · p. 5

G. Belief-Aware Multi-Task Execution

GAVEL orders remaining tasks by expected cost under the current belief, checks that combined plans remain valid, and updates the order as observations arrive.

G. Belief-Aware Multi-Task Execution

  • At each task boundary, GAVEL evaluates every remaining-task ordering by expected cost, then validates concatenated plans and selects the cheapest ordering that passes.If the cheapest ordering causes cross-task interference, it considers the next one.Source: G. Belief-Aware Multi-Task Execution · pp. 5–6
  • GAVEL executes only the first task in the selected ordering, then uses new observations to update object-location beliefs and reoptimize the remaining order.Observed objects become localized, while searched rooms where an object was not found are removed from its belief support.Source: G. Belief-Aware Multi-Task Execution · p. 6

V. EXPERIMENTAL EVALUATION

The evaluation uses a scalable 2-D BEHAVIOR-1K executor, checks its single-task outcomes against OmniGibson, and benchmarks 100 single-task and 500 multi-task instructions.

A. Simulation Setup

  • All 100 single-task instructions had success outcomes matching the 2-D executor in OmniGibson, while the executor reduced plan execution time from roughly 17 minutes to about one second.The executor retains original floor plans, object properties, task predicates, and navigation geometry; its speed enabled 5,500 evaluations.Source: A. Simulation Setup · p. 6
  • Success, travel distance, and planning time are averaged over five random seeds and reported as mean ± std.Planning time includes decomposition, LLM calls, repair, and ordering.Source: A. Simulation Setup · p. 6

B. Benchmarks

  • The benchmarks comprise 100 long-horizon tasks across 10 scenes and 500 multi-task instructions, each containing 2–5 tasks.Single-task reference plans average 12.2 primitives; multi-task instructions average 18.8 primitives across 4.66 rooms.Source: B. Benchmarks · p. 6

C. Compared Methods

Across single- and multi-task planning, GAVEL combines LLM semantic planning with graph-derived verification and repair, while belief-aware reordering reduces travel distance.

C. Compared Methods

  • The compared baselines isolate LLM-only planning, validation feedback, graph-edit planning, and oracle cost, while GAVEL variants distinguish repair, belief representation, and online reordering.gavel-basic uses one LLM proposal and graph repair; gavel-map fixes objects to their most likely room, whereas gavel-static retains distributions but fixes task order.Source: C. Compared Methods · p. 6

D. Belief and Cost-Model Quality

  • The RSN cost-model quality is R2 = 0.93 for four-task and R2 = 0.89 for five-task instructions; the most likely room ranks first for the true room in only 47% of 832 held-out queries.The RSN reports AUC 0.904 and Brier score 0.057; the pairwise cost model motivates O(N^2) construction rather than rolling out every permutation.Source: D. Belief and Cost-Model Quality · p. 6

E. Experiment 1: Single Long-Horizon Task Reliability

  • 91.8% of single-task plans succeed with Qwen3-8B and GAVEL, versus 41.2% for LLM-only planning; GAVEL averages 1.5 LLM calls per task.With Qwen3-4B, GAVEL reaches 88.8%, compared with 21.8% for LLM-only planning.Source: E. Experiment 1: Single Long-Horizon… · pp. 6–7

F. Experiment 2: Long-Horizon Multi-Task Execution

  • 92.6% of multi-task instructions are completed by GAVEL, compared with 75.6% for the SayPlan-style baseline; on matched successful sets, travel falls from 83.01 m to 78.01 m.GAVEL also reduces planning time by roughly 12 s per instruction.Source: F. Experiment 2: Long-Horizon… · p. 7, Table II · p. 7
  • The EPoG-style baseline succeeds on 60.2% of multi-task instructions but fails on appliance-induced semantic goals, which graph-state differences alone cannot specify.Examples include cooked, washed, or dried states that require running an appliance.Source: F. Experiment 2: Long-Horizon… · p. 7
  • Of GAVEL’s 38 residual multi-task failures, 21 stem from object extraction, 5 from unexecutable plans, and 9 from unmet goals.These residual failures lie mostly upstream of planning.Source: F. Experiment 2: Long-Horizon… · p. 7
  • Distributional beliefs and online reordering reduce mean travel distance by 4.45 m, or approximately 5.4%, compared with gavel-map.gavel-static reaches 79.69 m and online reordering reaches 78.01 m; ordering optimization takes 17 ms per instruction.Source: F. Experiment 2: Long-Horizon… · p. 7

G. Experiment 3: Does Model Scaling Replace GAVEL?

On the 100-instruction subset, GAVEL improves success for compact and hosted models, while scaling alone leaves long-horizon failures. The conclusion also reports lower travel distance from distributional beliefs and online reoptimization, alongside a symbolic-manipulation scope boundary.

G. Experiment 3: Does Model Scaling Replace GAVEL?

  • On the 100-instruction subset, Qwen3-4B with GAVEL reaches 75.2%, versus 2.4% for Qwen3-4B alone and 24.6% and 38.6% for hosted models alone.Qwen3-8B with GAVEL reaches 89.2%, and both hosted models reach near-perfect success with GAVEL.Source: G. Experiment 3: Does Model Scaling… · p. 7
  • Planning time remains 16.5 s for GPT-5.6 Sol and changes from 18.0 to 18.2 s for Claude Sonnet 5 with GAVEL.For compact models, additional cost comes from further LLM planning attempts rather than graph verification and repair.Source: G. Experiment 3: Does Model Scaling… · p. 7

VI. CONCLUSION

  • GAVEL rolls LLM-generated plans forward on a graph, repairs failures implied by modeled action semantics, and reserves LLM queries for failures needing semantic reasoning.Under partial observability, it estimates execution costs from distributional beliefs and reoptimizes task order as observations arrive.Source: §VI · p. 8
  • On BEHAVIOR-1K, graph-derived repair raises Qwen3-4B single-task success to 67.7%, and LLM re-queries for semantic failures raise it to 88.8%.Qwen3-4B with GAVEL also outperforms stronger hosted planners used alone.Source: §VI · p. 8
  • Retaining full object-location distributions and reoptimizing online reduces traveled distance by approximately 5.4%.Source: §VI · p. 8
  • The evaluation uses symbolic manipulation, so the graph captures logical action consequences but not geometric feasibility.The authors identify motion-level reachability and collision constraints as extensions for physical execution.Source: §VI · p. 8
Loading 2609.19315v1…