Task Decomposition and Dependency Graphs

Multi-agent systems fail in patterns, and the patterns have been counted. MAST — the Multi-Agent System Failure Taxonomy — was built out of 1,642 annotated execution traces across 7 multi-agent frameworks. It names 14 failure modes in 3 categories. The taxonomy itself was fixed first on 150 traces, with inter-annotator agreement of kappa = 0.88. It was a NeurIPS 2025 spotlight.

The failure modes that belong to decomposition are not exotic corners of the distribution. Step repetition (FM-1.3) appears in 15.7% of the annotated material. Unaware of termination conditions (FM-1.5) is 12.4%. Disobey task specification (FM-1.1) is 11.8%. Task derailment (FM-2.3) is 7.40%. Fail to ask for clarification (FM-2.2) is 6.80%.

FM-2.2 is the one that describes a set of parallel branches launched over a prerequisite nobody resolved. The taxonomy defines it as “Inability to request additional information when faced with unclear or incomplete data, potentially resulting in incorrect actions.” Read that next to step repetition at 15.7%. The pair is the measured shape of branches that each guessed the missing input and then each redid the same work.

The repair the authors measured sits upstream of all of it. Improving agent role specification alone raised ChatDev's task success rate by 9.4% — same prompt, same GPT-4o backbone. The model did not get better. The contract did.

Signal 1 is the one with an experiment behind it. A model asked to check its own answer, with nothing outside itself to say whether the answer is right, tends to get worse. That is intrinsic self-correction, and a paper at ICLR 2024 measured it. GPT-3.5 fell from 75.9 to 75.1 and then 74.7 on GSM8K over two rounds. On CommonSenseQA it fell from 75.8 to 38.1. On HotpotQA, from 26.0 to 25.0. GPT-4 fell from 95.5 to 91.5 to 89.0 on GSM8K, and from 49.0 to 43.0 on HotpotQA.

Now give the same GPT-3.5 loop an oracle label to tell it when to stop. It rises from 75.9 to 84.3 on GSM8K. The loop is identical. The difference is entirely the external judge.

The authors state the mechanism in one sentence: “The fundamental issue is that LLMs cannot properly judge the correctness of their reasoning.” A subgoal that reports its own completion is that loop with the oracle removed. And 75.8 down to 38.1 on CommonSenseQA is what removing it can cost.

Signals 2 through 4 have no single published number attached to them here. They are earned the slow way: run the case repeatedly, then run a case built to break it.

Task decomposition turns a broad contract into subgoals that produce named artifacts or state changes. A useful decomposition exposes dependencies, shared inputs, parallel branches, and the evidence required to mark each subgoal complete.

More subtasks do not automatically improve reasoning, and LLMCompiler priced the difference in 2024. Hold the model fixed at LLaMA-2 70B. The same system reaches 2.82x on the embarrassingly parallel Movie Recommendation task. On ParallelQA it reaches only 2.27x — the authors' own 113-example benchmark, where the second tool's argument depends on the result of the first tool's output. What changed between the two runs is not the number of subtasks. It is the dependency structure. The closed-source column reads 3.74x on Movie Recommendation and 2.15x on ParallelQA, but those two runs use different backbones, gpt-3.5-turbo and gpt-4-turbo. They are not a like-for-like pair.

The residual overhead is coordination that cannot be parallelised at all. In the Movie Recommendation experiment the Planner and the final answering process cost 1.88 s and 1.62 s on average. Together that is already more than half of LLMCompiler's overall latency. And the branches do not finish together. The slowest parallel search averaged 1.13 s, nearly 2x the 0.61 s average latency of all tasks. The authors name it: “Another source of overhead is the straggler effect among the parallel tasks when they need to join together.”

Decomposing around artifacts rather than activities is not a preference invented for agents. It is a mandatory defense standard. The U.S. Department of Defense issued MIL-STD-881F on 13 May 2022, superseding MIL-STD-881E of 6 October 2020, and it is still active. It defines a work breakdown structure as “A product-oriented family tree composed of hardware, software, services, data, and facilities.”

The standard then rules out the decomposition most teams reach for first. “A WBS is a product structure—not an organizational structure or a capabilities structure”, it insists. It directs that the structure address “the products required, not the functions or costs associated with those products”. Splitting by who does the work, or by which capability is being exercised, is the thing the standard exists to forbid. And it is not advice: the standard “addresses mandatory procedures for all programs subject to DoD Instruction 5000.02”.

Read the map with that rule in force. A root contract carries the overall outcome, constraints, authority, and completion evidence. It becomes subgoals, each a bounded result with its own acceptance test. A dependency is an input or state that must exist before another subgoal begins. Every subgoal ends in an artifact — a typed output that can be reviewed, merged, or reused. That artifact is the product in the family tree. The join condition holds the rules for reconciling branches and resolving conflicts. Artifacts and the join condition need separate owners and separate tests.

Draw the dependency graph for a request your team currently handles as one long instruction. Use a published format rather than an ad-hoc box diagram. HuggingGPT, from 2023, makes task planning an explicit graph stage. The controller emits each subtask with a “dep” field of prerequisite task ids. A <resource> symbol injects a predecessor's output into a successor's arguments. That is the whole notation you need. Every subtask says what must exist before it, and where its inputs come from. The paper defines the hardest of its three request classes plainly: “Graph Task indicates that user requests can be decomposed into directed acyclic graphs.”

Expect the drawing to be hard, because it is hard for the planners too. The GPT-4-annotated evaluation set holds 1,450 single, 1,917 sequential and 130 graph requests, plus 46 human-annotated complex requests. GPT-3.5 scored 52.62 accuracy on single tasks. On sequential tasks it scored 51.92 F1 with 0.54 normalised edit distance. On graph tasks it managed a GPT-4 Score of 50.48, against 19.17 for Vicuna-7b and 13.14 for Alpaca-7b. Planning quality falls as the structure hardens, and 50.48 on graph tasks is the strongest planner in that study.

Work in this order. Name the final artifact: specify what the user or downstream system will receive. Identify irreversible unknowns: resolve identity, scope, authority, and data availability early. That is the step whose absence MAST counts as fail to ask for clarification (FM-2.2), at 6.80%. Create testable subgoals: give each branch inputs, outputs, and an acceptance condition. Mark parallel work: separate the branches that do not share mutable state. Define the join: specify conflict handling, provenance, and final contract validation. Mark every shared input as you go. Then leave behind a record showing that each subgoal could be judged by something other than its own report on itself.

Decompose around artifacts and state transitions, in the sense MIL-STD-881F fixed for hardware programmes: “A WBS is a product structure—not an organizational structure or a capabilities structure”. That choice makes subgoals observable, resumable, and easier to assign to humans, tools, or agents. Each one leaves a product behind that somebody else can pick up.

Whoever writes the decomposition owns the risk that it keeps every subtask and loses the dependency — the 81.54-against-54.70 risk. What that person owes the reviewer is a set of subgoals that can each be judged without taking the subgoal's own word for it. A self-graded subgoal is the intrinsic loop that took GPT-3.5 from 75.9 down to 74.7. The oracle-labelled version of the same loop reached 84.3.