Source

arxiv:2510.25320 — Graph-based Agent Planning with Parallel Tool Use (October 2025)

Summary

GAP builds an explicit dependency graph at planning time to determine which tool calls are independent and can execute concurrently. It substantially outperforms ReAct baselines on multi-hop QA through intelligent parallelization, reducing end-to-end latency while improving accuracy.

Relevance to Zeph

HIGH. Zeph already has TaskGraph DAG + DagScheduler (#1235). GAP's contribution is the planning step: LlmPlanner currently builds the DAG from natural language. GAP shows that explicitly tagging inter-task dependencies (and teaching the planner with correctness-based RL rewards) yields much better parallelization decisions. The existing DagScheduler interface can directly consume a better-planned DAG.

Proposed Implementation Sketch

Phase 1 (LOW/MEDIUM complexity): Add structured dependency annotation to LlmPlanner output — require the planner to output explicit parallel/sequential markers for each task alongside the existing DAG edges. No schema change needed (TaskGraph already has dependency edges).

Phase 2 (HIGH complexity, future): RL fine-tuning of the planner on dependency graph traces with correctness rewards. Deferred — requires replay buffer and reward signal from task outcomes.

Issue Overlap

None of the current open research issues. New improvement opportunity for orchestration subsystem (DagScheduler, LlmPlanner in zeph-orchestration).

Priority

P4 (backlog). Phase 1 is the actionable part without RL infrastructure.