EvoPlanner: Decoupling Evidence Obligations from Evolving Task Graphs for Reliable Tool Use

Reliable tool use depends on maintaining a coherent account of what the original request still requires as an agent revises its plan. Structured planners organize dependent actions, and verification-guided methods assess intermediate outputs, yet task-level status alone cannot express which parts of a request remain supported after a task is split or replaced. An incomplete task may already have obtained useful evidence; retaining its output does not by itself preserve an explicit link to the requirements that evidence satisfies. We present EvoPlanner, which separates fixed queries-derived evidence obligations from an evolving Task DAG. Accepted observations are linked to these obligations through persistent Witnesses, and unmet obligations guide bounded revisions to unresolved tasks. This design preserves the recorded support across task replacement while allowing the acquisition strategy to change. In StableToolBench, EvoPlanner achieves macro-average SoPR scores of six-subsets of $50.4\%$ and $62.2\%$ with Qwen-Long and DeepSeek V4 Flash, exceeding our corresponding VeriMap reproductions by $10.8$ and $17.0$ percentage points. Together with the component ablations, these results support integrating evidence verification with dynamic plan revision, enabling agents to adapt their execution while retaining acquired support and improving task completion.