Atomic Task Graph: A Unified Framework for Agentic Planning and Execution¶

🕒 Published (v1): 2026-07-02 09:34 UTC · Source: Arxiv · link

Why this paper was selected

Novel unified planning framework (Atomic Task Graph) directly applicable to agent harness scaffolding

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Atomic Task Graph (ATG) reformulates LLM agent task-solving as an explicit directed acyclic graph (DAG) of atomic tool-use units, exposing inter-subtask dependencies across both planning and execution. This enables parallel branch execution, pre-execution failure detection via a "thought experiment," and minimal-subgraph repair that freezes validated nodes rather than replanning globally. Using only 7B–8B open-source backbones, ATG consistently outperforms all baselines—including GPT-4 + ReAct on two benchmarks.

Problem¶

Existing prompt-based agent control frameworks organize task-solving as linear textual trajectories. Even methods that introduce trees or graphs use them only for candidate exploration; the executed plan remains sequential. This causes: (1) implicit, unstructured input-output dependencies that prevent verified intermediate results from being reused; (2) error propagation across coupled steps with no clean failure boundary; (3) accumulating textual context that induces hallucinated actions; and (4) costly global replanning on any failure.

Method¶

ATG represents the full task as a DAG \(G = (V, E)\) where each node \(v_j = (i_j, f_j, o_j)\) is an atomic tool-call triple (input, tool, output) and each edge \(e_{jk}\) indicates that \(o_j\) feeds into \(i_k\).

Planning — Interface-Preserving Recursive Graph Compilation: Starting from a coarse level-0 node, the LLM recursively expands non-atomic nodes into subgraphs. Each expansion must preserve the parent node's external input-output interface so the surrounding graph is not perturbed. Recursion terminates when every node maps to a single tool call. The sequence of intermediate graphs (refinement history) is retained for later error tracing.

Execution — Dependency-Aware Scheduling: Nodes are executed in topological order; any nodes with all predecessors resolved are eligible for parallel execution. Before real execution, a thought experiment simulates the plan internally, checking tool appropriateness, dependency validity, interface consistency, and missing steps. Detected issues are logged with type and location.

Recovery — Minimal Necessary Subgraph Repair: On failure (pre-execution or runtime), the system identifies failed node(s) \(F\) and traces them through the refinement history to find their lowest common historical ancestor \(a_f\). It constructs the minimal subgraph covering \(F\), upstream context, and affected downstream nodes, freezes everything else, replans only that subgraph while preserving its external interface, and reintegrates.

Key Contributions¶

ATG framework: unified DAG-based control spanning planning, execution, and recovery for LLM agents, requiring no fine-tuning or parameter updates.
Interface-preserving recursive graph compilation: progressive coarse-to-fine decomposition that records refinement history and localizes node context, reducing hallucinated actions.
Dependency-aware execution with thought experiment: parallel scheduling over explicit graph structure plus cheap pre-execution simulation to catch structural failures before costly environment interaction.
Minimal necessary subgraph repair: failure localization via refinement-history ancestry, repairing only the affected region while freezing validated states.

Results¶

Task success (ALFWorld / WebShop / ScienceWorld):
Llama-3-8B + ATG: 63.65 / 68.36 / 56.79 vs. best baseline PoG: 21.17 / 31.66 / 35.72
Mistral-7B + ATG: 55.73 / 62.75 / 49.81 vs. PoG: 23.72 / 24.18 / 28.63
Gemma-7B + ATG: 58.71 / 64.93 / 52.03 vs. PoG: 32.85 / 12.56 / 13.85
Llama-3-8B ATG surpasses GPT-4 + ReAct (41.24 / 64.34 / 66.16) on ALFWorld and WebShop.
Execution steps (ALFWorld): ATG 18.36 vs. ReAct 31.42; 25.3% fewer steps than PoG on ALFWorld.
Hallucinatory action rate (ALFWorld): ATG 12.14% vs. ReAct 42.86%, PoG 28.57% — 71.7% relative reduction over ReAct.
Ablations: removing the thought experiment drops ~4–5 points; removing subgraph repair drops ~6–8 points across backbones and benchmarks.

Limitations¶

Evaluated only on three text-based interactive benchmarks (ALFWorld, WebShop, ScienceWorld); generalization to vision-based or open-web environments is unverified.
The recursive compilation process adds planning overhead; latency costs of graph construction vs. linear ReAct are not quantified.
The thought experiment relies on the same backbone LLM for simulation, so systematic blind spots in the model will also affect pre-execution detection.
All backbone models tested are 7B–8B; it is unclear whether ATG's structural benefits persist or shrink when the backbone is already very capable (e.g., 70B+ models).
Hallucinatory action analysis is reported only for ALFWorld where the environment provides explicit invalid-action feedback; coverage for other benchmarks is not shown.

Relevance to Agentic AI / LLM Agents¶

ATG directly addresses the core reliability bottleneck in long-horizon LLM agents: the inability to reuse verified partial results and localize failures without global replanning. By making subtask dependencies a first-class, executable data structure rather than an implicit textual artifact, it connects to the broader trajectory of structured agent control (ReAct → ToT/PoG → ATG) and extends it into the execution and recovery phases. The result that 8B-parameter models with ATG beat GPT-4 + ReAct on two benchmarks is a strong evidence point that control framework design is a competitive lever alongside scale. The minimal-subgraph repair mechanism is particularly relevant to anyone working on agentic fault tolerance, since it operationalizes a compositional invariant (interface preservation) that could generalize to multi-agent pipelines and tool-augmented code agents.