Planning subtasks as a graph cuts an agent's steps and latency

Autonomous agents run on tool calls. But almost every popular agent framework issues those calls in strict sequence: the agent thinks, calls one tool per step, waits for the result, then decides what to do next. That is convenient for keeping the agent under control and understanding what it is doing, but it hits a ceiling on tasks that contain independent subtasks which could be solved at the same time. Time goes into waiting that nothing depends on, cost climbs, and the context fills up with extra steps.

The researchers propose a simple way to give the model a more flexible tool-use strategy: train it to plan with an explicit graph of subtasks and their dependencies, then run that plan in layers — sequentially where the dependencies demand it, in parallel everywhere else. All the logic stays inside a single LLM: no heavy coordination between several agents, no hand-written prompts for each situation.

What GAP actually is

The idea is simple. The agent applies GAP (Graph-Based Agent Planning): it breaks the question into atomic subtasks — find a particular hotel online, check a fact — and builds a directed acyclic graph of the dependencies between them.

The planning graph is split into levels by topological sort. All subtasks on one level are independent, so they run in parallel as separate search queries, tool calls and subagents. The results from each level are then merged, and at the end the agent writes a short final answer for the user.

The result: fewer steps, fewer tokens, lower demands on the context window. The agent does not just solve the task — it also spells out its view of the plan for the user, in a dedicated markup that describes the solution graph.

How these agents are trained

The training pipeline has two stages. The first is SFT on synthetic trajectories with graph planning. The authors collected about 7,000 of them — favoring the harder cases, keeping a balance between trajectories with and without parallelism, and capping trajectory length — on top of Qwen2.5-3B-Instruct.

The second stage is reinforcement learning on real tasks. Why does that matter? SFT teaches a model to copy trajectories well, but it does not optimize the agent for acting efficiently. Under RL the agent generates plans for its own questions and is rewarded for a correct final answer. On those tasks it learns to use parallelism more widely where parallelism helps, and to shorten both the trajectory and the context it carries where that is safe. It amounts to optimizing trajectories with an eye on dependencies: do not call an extra tool if the call does not move the reward.

What the tests showed

The agent was tested on seven datasets, from NQ and TriviaQA to the harder HotpotQA, 2Wiki and Musique. What matters is not only whether it answers, but in how many steps, with what latency and with how many tokens.

On the hard benchmarks GAP clearly beats strong ReAct-based baselines. The average accuracy gain is around 1%, at a better cost. On HotpotQA the agent takes 1.78 steps on average against 2.27 for the best baseline, which brings average answer time down from 248 to 168 seconds. On 2Wiki the average step count falls from 3.05 to 2.03, and answer time from 262 to 206 seconds. Answers also stop bloating: 25% shorter on HotpotQA, 20% shorter on 2Wiki — fewer tokens, lower cost.

On tasks that come down to retrieving a single fact, GAP matches the best search agents or falls slightly behind them. That is expected: there is nothing to parallelize, but a short plan does not inflate the trajectory either. Across all the datasets, GAP lands on the best trade-off between answer quality and cost.

Why this matters

The key contribution is making the dependencies between steps explicit. It looks like a simple abstraction, but it is an important one, and it rests on the model understanding the shape of the task — which parts of a request are independent and which are linked. That design scales well to parallel calls to tools and agents, and it still keeps a single LLM as the orchestrator making the decisions, with no explicit multi-agent system.

The downside: those dependencies have to be extracted correctly. Get them wrong and you get empty or redundant calls — or the opposite, parallelism fired off too early, where firing early is dangerous. The authors teach this explicitly on working trajectories and through RL, but the sensitivity to the knowledge baked into those trajectories and to the tool list remains. The gains are also clearer on tasks with an obvious tree structure; on simple questions they are more modest.

Takeaways

Handling subgoals makes agents better at hard tasks. But existing search approaches for LLM-based agents implement subgoal handling through tool calls, and that only ever executes several subgoals one after another.

In this work the researchers showed that modeling the dependencies between subgoals explicitly, as a graph, makes it possible to process those subgoals in parallel — cutting the number of steps and the overhead, and improving agent performance.

In the experiments GAP substantially outperforms existing agents, thanks to more efficient planning and its use of parallelism. It is a step toward a next generation of autonomous agents: ones that do not merely react to their environment but build and optimize their own strategy of thinking, as a computable reasoning graph.

💾 Code