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

The authors present GAVEL, a framework for verifying and repairing long-horizon LLM task planning using an explicit graph world model. The graph represents object relations, action preconditions, effects, and probabilistic beliefs over unobserved locations. This allows the system to predict action consequences before execution, detect violations, perform automatic repairs, and reserve LLM replanning solely for complex semantic errors. Evaluated on BEHAVIOR-1K using Qwen3-8B, GAVEL substantially improves task success rates and reduces travel distance.

With Qwen3-8B, GAVEL improves single-task success from 41.2% to 91.8%.

It improves multi-task success from 19.9% to 92.6%.

Distributional belief reasoning reduces travel distance by approximately 5.4% compared with a static variant.