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
cs.RO, cs.AI
2026-09-17
GAVEL verifies and repairs LLM robot plans with a graph world model. On BEHAVIOR-1K with Qwen3-8B, single-task success rises from 41.2% to 91.8%, multi-task from 19.9% to 92.6%.
LLM robot planners drop preconditions, reach into closed cabinets, and leave dishwashers running. Compact models fare worse as the horizon grows. On 100 BEHAVIOR-1K long-horizon tasks, Qwen3-4B succeeds 21.8% of the time and Qwen3-8B 41.2% if the plan is executed as generated.
SayPlan-style loops send every failed action back to the LLM. That costs 3.4 calls per task for Qwen3-4B and still only reaches 55.4%. Graph-edit planners such as EPoG are fast for rearrangement, but they cannot invent "run the dishwasher" from a difference between two scene graphs.
Partial observability makes this worse. Room layout is known; object rooms are not. Collapsing each belief to its mode and freezing task order throws information away: on 832 held-out queries the true room is ranked first only 47% of the time.
GAVEL treats the scene graph as a world model that can simulate action outcomes. Nodes are rooms, objects, and the robot. Edges encode relations such as near, inside, and holding. Unary flags track open, cooked, washed, and similar states. Nine primitives (NavigateTo, Grasp, PlaceOnTop, Open, ToggleOn, and the rest) each carry preconditions and effects covering proximity, affordance, gripper state, and container access.
The LLM proposes one grounded action sequence per subtask. The graph rolls the plan forward and stops at the first violated precondition. Failures whose fix is already implied by the action model are edited in place: missing proximity inserts NavigateTo, a closed container inserts Open, safety restoration closes cabinets and switches appliances off. Only remaining semantic failures go back to the LLM, up to T=5. Non-monotonic edits keep the best candidate seen so far.
Task understanding uses two LoRA adapters on Qwen3-1.7B, shared across all planners: one extracts objects and relations stated in the instruction, one extracts the goal graph. They train on 8,000 synthetic pairs. Unlocalized objects get a room-type prior from a Relational Semantic Network following SEEK (frozen bge-small-en-v1.5 plus a 256-128-64 MLP), then the type score is spread uniformly over room instances and Platt-calibrated. Held-out AUC is 0.904.
For multi-task instructions GAVEL keeps the full location distribution, builds expected search and transition costs, and enumerates permutations (N≤5). It executes only the first task of the cheapest valid ordering, updates beliefs from observations, and re-solves. Ordering takes 17 ms per instruction.
Evaluation uses a 2-D executor that preserves BEHAVIOR-1K floor plans, predicates, and navigation geometry. Success on all 100 single-task instructions matched OmniGibson. The executor cuts runtime from about 17 minutes to about one second, which is how 5,500 evaluations happen.
Single-task, 100 instructions, mean 12.2 primitives:
| Model | Method | Success | Mean LLM calls | Planning time |
| Qwen3-4B | llm-only | 21.8% | 1.0 | 9.2 s |
| Qwen3-4B | SayPlan-style feedback | 55.4% | 3.4 | 27.6 s |
| Qwen3-4B | graph repair only | 67.7% | 1.0 | 9.2 s |
| Qwen3-4B | GAVEL | 88.8% | 1.7 | 15.0 s |
| Qwen3-8B | llm-only | 41.2% | 1.0 | 13.3 s |
| Qwen3-8B | SayPlan-style feedback | 76.4% | 2.7 | 24.6 s |
| Qwen3-8B | graph repair only | 76.2% | 1.0 | 13.5 s |
| Qwen3-8B | GAVEL | 91.8% | 1.5 | 15.5 s |
Graph repair alone lifts Qwen3-4B past feedback-only replanning by 12.3 points at 1 call instead of 3.4. On Qwen3-8B, repair matches SayPlan; adding semantic re-queries reaches 91.8%.
On 500 multi-task instructions with Qwen3-8B: llm-only 19.9%, SayPlan-style 75.6%, EPoG-style 60.2% (every failure is an appliance-induced semantic state among 199 such instructions), GAVEL 92.6%. On the matched success set, travel drops from 83.01 m to 78.01 m versus SayPlan. Keeping the distribution and reordering online cuts distance from 82.45 m (MAP, fixed order) to 78.01 m, about 5.4%. Oracle with true locations is 56.17 m. Of GAVEL's 38 residual failures, 21 are object extraction, 5 unexecutable plans, 9 unmet goals.
Scaling the planner does not replace the world model. On a 100-instruction subset, Claude Sonnet 5 alone reaches 38.6% and GPT-5.6 Sol 24.6%; Qwen3-4B plus GAVEL reaches 75.2%. Combined with GAVEL, the hosted models hit 99.2% and 99.4% with almost no extra planning time.
The split is usable: the LLM owns procedures such as "washing means running the dishwasher"; the graph owns executability. A small local model with a world model beats a frontier model used as a standalone planner. For hosted models the graph adds almost no latency (GPT-5.6 Sol stays at 16.5 s), so the extra time on compact models is extra LLM retries, not verification.
Residual error has moved into instruction grounding. Anyone still iterating on embodied planners should put a hard action model around the LLM before buying a larger one.
The graph is symbolic. It does not check geometric reachability or collisions. The authors say the same verify-and-repair loop would need motion-level constraints to transfer to physical execution.
The semantic prior is mostly room type, so it cannot learn that this particular kitchen keeps mugs in a specific cabinet. Multi-task instructions are constructed with disjoint goal objects, so order affects cost, not feasibility. Real chores share utensils. Enumeration only works because N≤5. The large-scale 5,500-run numbers are from the 2-D executor; OmniGibson agreement covers the 100 single-task set only. The pairwise cost model has R² 0.93 (four-task) and 0.89 (five-task), so the ordering objective is itself an approximation.