PITON: Anchored Dependency Repair for Multi-Tool Planning

Tool-planning models expand a natural-language request into an ordered sequence of structured tool calls. Correct plans often require tools the request never mentions. Prior work supplies this knowledge with a dependency graph built from gold plans, joining any two tools called one immediately after the other. Treating every such adjacent pair as the same dependency conflates two situations: (1) within-goal dependency: two adjacent tools may serve one requested goal from the query, one tool being an unnamed prerequisite of the other; (2) cross-goal adjacency: two adjacent tools simply serve two different goals, requested back to back. The graph alone therefore cannot tell whether an observed adjacency represents a dependency needed by the current query or merely connects two consecutive goals. This distinction matters because frozen planners fail disproportionately on the former: on UltraTool, they recall 64.6% of cross-goal adjacencies but only 23.7% of within-goal dependencies, where the unnamed prerequisite is often missing. Motivated by this gap, we propose PITON, a model-agnostic repair framework for dependency-aware plan refinement. PITON anchors on a planner's draft, using the tools already selected as clues to missing prerequisites. It alternates an insertion reranker that recovers missing dependencies from the anchors' one-hop graph neighbourhood with a symmetric deletion reranker, until the plan stabilises. PITON is especially natural for masked diffusion models. They progressively commit confident tools and refine the remaining plan. We evaluate ten diffusion, autoregressive and closed-source planners on UltraTool, ShortcutsBench and MCP-Atlas, and show PITON raises edge F1 in all eighteen settings. The gain over the unrepaired draft reaches +26.0, +10.1 and +24.3 points on the three benchmarks. PITON requires only lightweight rerankers while keeping the base planner frozen, introducing minimal additional training overhead. Code is available at https://anonymous.4open.science/r/anchor-anon-6006.