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
Published September 16, 2026 · on the feed September 21, 2026 · ▲ 4 · arXiv 2609.19315
The 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.
The Brief
2:19A short podcast summary of the paper. Written and voiced by AI.
Transcript
GAVEL. Graph World Models for Verified and Efficient Long-Horizon LLM Task Planning. By Ruiyang Wang and five others. Published on the sixteenth of September. No code repository is linked to it.
Large language models give a flexible interface for long-horizon robot planning, but the plans they generate often fail in three ways. They do not respect the constraints of the robot's embodiment, they do not recover from planning errors, and they do not reason well when the environment is only partly observable. A plan can read sensibly as text and still ask the robot to do something its body cannot do, or to fetch an object from a place nobody has looked.
GAVEL verifies and repairs these plans around an explicit graph world model. The graph holds three kinds of knowledge. It represents the relevant relations between objects. It represents the preconditions and effects of actions, what must be true before an action and what becomes true after. And it represents probabilistic beliefs about where objects that have not been observed are likely to be. Rather than trusting the language model's plan, GAVEL holds it up against this model.
With that model, GAVEL predicts the consequences of an action the language model proposes before it is executed, and detects violations. Where the correction follows directly from the world model, GAVEL repairs the action itself. Replanning by the language model is reserved solely for errors that need semantic reasoning. That division of labor means the language model is called back only when the graph cannot settle the matter itself. For instructions containing several tasks, GAVEL reasons over distributions of possible object locations to reorder the remaining subtasks, minimizing the expected cost of searching.
The evaluation uses BEHAVIOR-1K, with one hundred single long-horizon tasks and five hundred multi-task instructions. With Qwen3-8B, single-task success goes from forty-one point two percent to ninety-one point eight percent. Multi-task success goes from nineteen point nine percent to ninety-two point six percent. Reasoning over belief distributions also cuts travel distance by about five point four percent compared with a static variant.
The language model still proposes the plan. The graph checks it, fixes whatever follows from its own structure, and hands back only what needs semantic judgment. According to the authors, that harness makes long-horizon embodied planning more reliable and more efficient, for compact models and frontier hosted ones alike.
Paper Quest · 7 chapters · about 40 min
Play this paper
Learn it by doing: make the calls the authors made, guess the result before you see it, and defend it in a viva graded on your own words. Chapter 1 is right here.
Chapter 1 🧩 · The problem
A plan that reads well can still leave a robot at a closed door. Start there.
You ask a robot, through a language model, to wash the plate and put the apple away. The model writes a long, sensible-looking list of actions.
The road ahead
- 1 · The problem ~6 min A language model can write a robot plan that reads well as text but breaks the physical rules of the house.
- 2 · What came before ~3 min
- 3 · The key idea ~9 min Hold the language model's plan up against an explicit graph of the house, simulate it there, fix what the graph can fix, and ask the model only about the rest.
- 4 · Choose your own research ~3 min
- 5 · Build the method ~8 min The language model writes a plan, the graph rolls it forward, catches violations before execution, and repairs those its action model implies.
- 6 · The experiment ~6 min You’ll guess: With Qwen3-8B, plain language-model planning succeeded on 19.9% of multi-task instructions. What success rate did GAVEL reach with the same model?
- 7 · The viva ~5 min Three questions from the examiners, answered in your own words. Win it for the paper’s trophy.
Free, with Google or an email address. Your stars and progress are kept.