Large Language Model (LLM) agents have shown promise in multi-step planning tasks, butexisting approaches like LATS (Language Agent Tree Search) and ReAct rely heavily on LLMinference during planning, leading to high computational costs and stochastic behavior. Wepresent GATS (Graph-Augmented Tree Search), a planning framework that combines systematic UCB1-based tree search with a layered world model to eliminate LLM calls during inferencewhile achieving superior planning performance. Our three-layer world model integrates: (L1)exact symbolic action matching, (L2) statistics learned from execution logs, and (L3) LLMbased prediction for unknown actions. On synthetic planning tasks with branching paths anddead-ends, GATS achieves 100% success rate compared to 92% for LATS and 64% for ReAct.On a comprehensive stress test spanning 12 challenging scenariosincluding coding workows,web navigation, and long-horizon tasksGATS maintains 100% success while LATS dropsto 88.9% and ReAct to 23.9%. GATS requires zero LLM calls per task during planning(vs. 37 per task for LATS) and produces deterministic plans with zero variance across runs.Our results demonstrate that systematic search with learned world models can substantiallyoutperform LLM-guided exploration for agent planning.