Abstract
Planning is fundamental to LLM agents that solve complex, multi-step tasks, yet how to represent plans in a structured form that supports controllable execution remains an open challenge. Existing approaches often express plans as unstructured natural language or linear Chain-of-Thought (CoT), making it difficult to explicitly capture dependency structures among subtasks. They also lack outcome-conditioned transitions such as success/failure branches, limiting structured failure recovery during execution. We propose a Graph-based Adaptive Agentic Planner centered on a unified graph representation, GraphPlan, that jointly encodes prerequisite constraints and outcome-conditioned transitions, providing a structured substrate for failure localization and recovery. From a topological perspective, we show that CoT and unstructured planning are degenerate forms of GraphPlan under different constraints. Moreover, GraphPlan adaptively expands or collapses according to task complexity, enabling on-demand structuring. On SWE-bench Lite, a long-horizon interactive benchmark for repository-level repair, our method achieves a 51% resolution rate, substantially outperforming CoT (38%) and ReAct without planning (28.3%).