EP130: [GAP] Graph-based planning for faster AI agents

"GAP: Graph-based Agent Planning with Parallel Tool Use and Reinforcement Learning":The Problem: Current autonomous agents powered by large language models (LLMs) typically use sequential reasoning frameworks, such as the ReAct paradigm, executing one tool or action at a time. This step-by-step approach fails to take advantage of parallel processing for independent sub-tasks, leading to inefficient tool use, longer response times, and higher computational costs during complex, multi-step reasoning.The Solution: The authors introduce Graph-based Agent Planning (GAP), a novel framework that trains LLMs to explicitly map out task dependencies using a directed acyclic graph (DAG). When faced with a complex query, the GAP agent decomposes the task into a dependency-aware graph to autonomously determine which tools can be executed simultaneously in parallel and which must be run sequentially.Methodology: The researchers trained their model (based on Qwen2.5-3B) using a two-stage process:Supervised Fine-Tuning (SFT): The model was initially trained on a curated dataset of 7,000 high-quality, graph-based planning traces synthesized from Multi-Hop Question Answering (MHQA) benchmarks.Reinforcement Learning (RL): The model was then optimized end-to-end using reinforcement learning, rewarding the model for correct answers and training it to strategically balance parallel tool execution with context window constraints.Key Results:Higher Accuracy: GAP outperformed state-of-the-art multi-hop reasoning baselines, achieving a 0.9% average performance improvement across four multi-hop datasets.Dramatically Improved Efficiency: By parallelizing independent queries, GAP reduced the number of LLM interaction turns by up to 33.4% and decreased response token length by up to 24.9%.Lower Costs: These efficiency gains translate directly into faster execution times and lower inference costs, making the deployment of autonomous agents much more practical.