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

arXiv 2026 29.6 method, system

TLDR

GAVEL uses an explicit graph world model to verify and repair LLM-generated long-horizon robot plans, improving BEHAVIOR-1K success rates significantly.

Reasoning

The paper presents a clear method for graph-based world modeling in LLM planning, with strong empirical results on BEHAVIOR-1K. However, the abstract lacks comparison to other world model paradigms and does not detail limitations or ablations.

Read-first score

Read-first score 29.6, weighted from topical fit, citation, graph, method, reproducibility, and recency signals. Original total remains 37.

Recency 5%

100

Uses a gentle age decay so recent papers surface without erasing older foundations. 2026

Topical relevance 25%

52.9

Uses existing LLM keyword relevance scores normalized to 0-100. world model,world simulator,generative world model,interactive world model,video world model,world dynamics prediction,model-based reinforcement learning world model

Methodology quality 15%

Screens visible abstract and analysis fields for experiment, dataset, baseline, metric, and limitation evidence. markers=none

Reproducibility 15%

Screens links and visible text for paper, code, dataset, artifact, and repository signals. pdf=True; code=False; dataset=False; markers=none

Graph prestige 15%

5.7

PageRank-style prestige over the local citation graph built from available OpenAlex references. local_pagerank=0.0016

Citation impact 15%

Uses OpenAlex-shaped citation metadata as a bibliometric attention signal, separate from paper quality. cited_by_count=0

Citation velocity 10%

Citation velocity estimates citations per publication-year to reduce old-paper bias. velocity=0.00

Field roles

Frontier

Rank sensitivity

Stability: volatile; rank range: 232.

Keyword Scores

world model

world dynamics prediction

world simulator

interactive world model

model-based reinforcement learning world model

generative world model

video world model

Deep Analysis

Innovations

Introduces GAVEL, a framework that uses an explicit graph world model to verify and repair LLM-generated long-horizon robot plans.
Uses the graph world model to predict action consequences, detect pre-condition/effect violations, and repair errors derivable directly from the world model, while reserving LLM replanning for errors requiring semantic reasoning.
Maintains probabilistic beliefs over unobserved object locations and uses them to reorder remaining subtasks in multi-task instructions to minimize expected search cost.

Methodology

GAVEL combines LLM planning with an explicit graph world model encoding object relations, action pre-conditions and effects, and probabilistic beliefs about unobserved object locations. It predicts the consequences of LLM-generated actions before execution to detect violations and repair model-derivable errors, invoking LLM replanning only for semantic errors. For multi-task instructions, it reasons over location distributions to reorder subtasks and reduce expected search cost.

Key Results

On BEHAVIOR-1K across 100 single long-horizon tasks and 500 multi-task instructions, GAVEL with Qwen3-8B improves single-task success from 41.2% to 91.8% and multi-task success from 19.9% to 92.6%; distributional belief reasoning reduces travel distance by approximately 5.4% compared with a static variant.

Resources

Paper