GAVEL: Graph World Models for Verified and Efficient Long-Horizon LLM Task Planning
Submitted to ICRA 2027
LLM-generated robot plans often skip prerequisite steps or break embodiment constraints. GAVEL gives the LLM an explicit graph world model: it rolls each plan forward before execution, directly repairs failures whose fix follows from the action model, and sends only failures that need semantic reasoning back to the LLM. For multi-task instructions, it keeps beliefs over where unseen objects are and reorders the remaining tasks as the robot observes more.
- 41.2% → 91.8% success on 100 long-horizon BEHAVIOR-1K tasks (Qwen3-8B)
- 19.9% → 92.6% success on 500 multi-task instructions under partial observability
- A 4B local model with GAVEL (75.2%) outperforms frontier hosted LLMs used alone (at most 38.6%)