One-sentence Summary

Researchers from South China University of Technology and Tsinghua University propose Atomic Task Graph (ATG), a unified planning-execution framework that explicitly models subtask dependencies as a directed acyclic graph to enable recursive decomposition, parallel execution, and localized error repair, thereby outperforming strong baselines in success rate and execution efficiency across three interactive benchmarks using only 7B–8B backbone models.

Key Contributions

• The Atomic Task Graph (ATG) is a unified control framework that models LLM agent task solving as a directed graph of atomic tool-use units with explicit input-output dependencies across planning and execution.
• Interface-preserving recursive graph compilation progressively decomposes tasks while recording graph evolution and localizing node context, reducing hallucinated actions and supporting error tracing.
• Dependency-aware graph execution with minimal necessary subgraph repair enables parallel execution of independent branches, failure localization, and localized repair without global replanning. Experiments on ALFWorld, WebShop, and ScienceWorld with 7B–8B backbone models demonstrate consistent improvements in success rate and execution efficiency.

Introduction

The authors leverage LLM-powered autonomous agents for complex multi-step tasks, but note that existing prompting-based frameworks organize problem solving as linear sequences, coupling errors and enabling broad failure propagation without explicit dependency structures. Prior work struggles to localize failures, relies on inefficient replanning, and suffers from hallucinated actions due to growing textual context. To address these, the authors propose Atomic Task Graph (ATG), a unified control framework that represents agent task solving as a directed acyclic graph of atomic tool-use units, employing interface-preserving recursive graph compilation to expose dependencies and localize context, and dependency-aware execution with minimal necessary subgraph repair for parallel execution and targeted failure recovery.

Method

The authors propose the Atomic Task Graph (ATG), a unified control framework that integrates graph structure throughout planning and execution to solve complex multi-step tasks. As illustrated in the framework diagram, ATG formulates agent task solving as a Directed Acyclic Graph (DAG), explicitly exposing subtask dependencies, enabling parallel execution, and localizing failures for precise repair.

The ATG pipeline consists of three key stages: Interface-Preserving Recursive Graph Compilation, Dependency-Aware Execution, and Minimal Necessary Subgraph Repair.

First, Interface-Preserving Recursive Graph Compilation transforms a coarse user task into an executable atomic task graph. Starting from an initial coarse-grained task graph, the system recursively refines non-atomic nodes until every node represents a single atomic tool-use unit. At each refinement step, the Large Language Model only accesses historical context directly relevant to the current node, progressively narrowing the context window. A crucial design principle is interface preservation. If a parent node $v$v has an external input interface $i_v$iv​ and output interface $o_v$ov​, the compiled subgraph $G_v$Gv​ must collectively consume the same external inputs and produce an output compatible with $o_v$ov​. This ensures that replacing $v$v with $G_v$Gv​ does not alter how the rest of the graph interacts with that computation. The recursion terminates when all nodes are atomic, and the intermediate graphs are recorded to form a refinement history. This history serves as an interpretable trace and a foundation for localized self-correction.

Second, Dependency-Aware Execution operates over the compiled graph. Before real-world execution, a thought experiment acts as a pre-execution filter to simulate the intended process internally. This step exposes latent structural or operational failures, such as incorrect tool selection or interface mismatches, moving the recovery burden from expensive execution to cheaper simulation. Nodes are then executed according to the topological order induced by graph dependencies. A node becomes executable only when all predecessor nodes have finished and required inputs are resolved, allowing the system to exploit structural parallelism for independent branches. During execution, the system records the input, output, execution status, and error messages for each node, providing precise evidence for downstream recovery.

Third, Minimal Necessary Subgraph Repair addresses failures locally rather than globally. When a failure occurs during the thought experiment or real execution, the system localizes it to a failed atomic node $v_f$vf​ or a set of failed nodes $F$F. These nodes are traced back through the refinement history to identify their lowest common historical ancestor $a_f$af​, which marks the original planning scope where the failure was introduced. The system then constructs a minimal repair subgraph covering the failed node, its relevant upstream context, and affected downstream nodes. The remainder of the ATG is frozen to preserve validated states and avoid redundant recomputation. The system repairs only this subgraph by replacing incorrect tools, inserting missing nodes, or adjusting local dependencies, and reintegrates it into the main graph while preserving its external input-output interface.

Experiment

ATG is evaluated on three long-horizon agent benchmarks (ALFWorld, WebShop, ScienceWorld) using open-source backbones (Mistral-7B, Gemma-7B, Llama-3-8B) and compared against implicit, explicit, and multi-agent control baselines. It consistently achieves the best performance across all settings, with gains attributed to its graph-based executable substrate that enables dependency tracking, parallel execution, pre-execution validation, and localized failure recovery, rather than merely introducing planning structures. Analysis further shows that ATG reduces execution steps and hallucinatory actions, catches planning failures early via thought experiments, and scales robustly across different backbone models, demonstrating that effective control frameworks can narrow the gap between smaller and larger models.

ATG consistently outperforms all baselines on ALFWorld, WebShop, and ScienceWorld, with especially large gains on Mistral-7B. It adds over 48 points over ReAct on ALFWorld and WebShop and surpasses the strongest explicit-control baseline PoG by more than 32 points on both. Ablations confirm that the pre-execution thought experiment and minimal subgraph repair are both crucial, with subgraph repair having a larger impact on long-horizon tasks. On Mistral-7B, ATG improves over ReAct by 49.16 points on ALFWorld and 48.12 points on WebShop. ATG surpasses PoG, the best explicit-control baseline, by 32.01 points on ALFWorld and 38.57 points on WebShop with Mistral-7B. Removing the pre-execution thought experiment reduces performance by up to 4.87 points on ALFWorld, while removing minimal subgraph repair causes a larger drop of up to 7.72 points.

Across ALFWorld, WebShop, and ScienceWorld, ATG achieves the lowest average steps, with parallel branches counted as a single step. It reduces steps substantially compared to both prompt-based baselines like ReAct and explicit-control methods like PoG, demonstrating the efficiency of dependency-aware parallel execution. ATG requires fewer average steps than all baselines, reducing steps by up to 42% relative to ReAct and up to 25% relative to the strongest baseline PoG. Parallel branch execution in ATG compresses effective depth: the method counts concurrent actions as one step, leading to consistently lower step counts across all three environments.

Prompt-based agents suffer from high hallucinatory action rates, with ReAct and Reflexion exceeding 38% of trajectories containing invalid actions. Structured planning methods like ToT and PoG partially mitigate this but still produce hallucinated actions in over a quarter of cases. ATG dramatically reduces the rate to 12.14%, achieving a 71.7% relative reduction over ReAct and 57.5% over PoG, demonstrating that its dependency-aware execution and pre-execution validation effectively prevent invalid actions. Prompt-based baselines (ReAct, Reflexion) exhibit hallucinatory action rates above 38%. Explicit-control methods (ToT, PoG) lower the rate but still exceed 28%. ATG achieves a 12.14% rate, less than half that of the next best method PoG.

Across ALFWorld, WebShop, and ScienceWorld, ATG is evaluated against prompt-based and explicit-control baselines, demonstrating substantial success-rate gains, especially with smaller models like Mistral-7B. Ablations confirm that both the pre-execution thought experiment and minimal subgraph repair are essential, with subgraph repair having a larger impact on long-horizon tasks. ATG also achieves the lowest step counts by executing independent actions in parallel and dramatically reduces hallucinatory action rates through dependency-aware validation.