Agentic AI · L-Decomp
Task decomposition by hand, in the order of the lecture: boundaries and checks, the plan as an object, and scheduling and recovery.
The programming exercises are in the lab notebook lecture-Decomp-lab.ipynb.
These exercises compute what a check at a step boundary is worth. They use the success probability $p$ of a step, and the detection rate $d$ and the false-positive rate $\phi$ of a check, as the lecture defines them under Step Reliability with Verification.
A task needs n = 10 dependent steps; each step succeeds independently with p = 0.9.
The lecture's first formula for a step with a check assumed that the check fires only on a faulty step. Real critics also flag correct work. Keep the same setup — a step succeeds on its own with probability $p$, the check is run once on the first attempt, and a flagged step is redone once as a fresh draw with the same $p$ — but add the false-positive rate $\phi$: the probability that the check flags a step that was actually correct. As before, $d$ is the detection rate: the probability that it flags a step that was actually faulty.
The formula. Which formula of the lecture gives $p'$ for a check with the false-positive rate $\phi$? Show that it reduces to the lecture's formula for a check without false positives when $\phi = 0$.
When is the loop worth running? State the condition on $d$ and $\phi$. Then take $p = 0.9$, $n = 10$ and compute $p'$ and $p'^{\,n}$ for three checks:
| Check | $d$ | $\phi$ | |---|---|---| | a unit test on the artifact | 0.9 | 0.01 | | an LLM asked "does this reasoning look right?" | 0.2 | 0.25 | | no check at all | 0 | 0 |
Compare all three against the unchecked $p^{\,n}$.
The worst check. For a fixed $p$, which $(d, \phi)$ minimises $p'$? Give $p'$ and $p'^{\,10}$ in closed form and for $p = 0.9$. How does a reflection loop end up in that corner?
Estimating $\phi$. Estimate the false-positive rate $\phi$, and roughly the detection rate $d$, of each check, and justify each estimate from what the check reads: (a) unit tests of a generated function, written independently of it, for example by a developer; (b) unit tests written by the same model from the same specification as the function; (c) a JSON-Schema validator on a generated object; (d) a model asked whether the reasoning text of the step looks right; (e) a model that reads the artifact together with the report of a test run; (f) a human reviewer. Relate the estimates to the lecture's artifact vs. narration rule.
Formal or semantic. A generated function passes its unit tests. Which property of the function has been verified, and which has not? What does the answer imply for $d$?
These exercises place planning architectures in the design space of the lecture and compute what a check per step and a plan written before execution are worth. The seven design dimensions are the ones the lecture lists under Design Dimensions of a Planning Architecture.
For each task, decide whether a plan written before the first action (decomposition-first) or a decision on the next step at every turn (interleaved, as in ReAct) fits better. Justify the choice with a property of the task, and name the mechanism that the chosen mode needs to compensate for its cost.
A team describes its coding agent:
"The model writes the plan as a JSON list; each item has an id, a tool and a depends_on list.
A scheduler starts every item whose dependencies have finished, several at once. The output of each
item is checked by the unit tests of that item, and a rejected item is retried at most twice, with the
test report in its prompt. If an item still fails, a second model call rewrites the items that have
not yet run. No programmer writes the graph of steps."
Take the plan of Reliability: Monolithic vs. Decomposed with $d = 1$, but with one check after the whole graph instead of one after every step; a run detected as faulty derives all $n$ steps again.
These exercises compute with the plan as a DAG: its matrix, its topological orders, the check of a given order and its reachability relation.
🔁 Prior knowledge (your Algorithms course): Grundlagen der Graphen · Graphensuche (BFS/DFS). We reuse adjacency matrices and adjacency lists, degrees, traversal, matrix powers, and running-time analysis here.
A plan has the tasks A–F with the dependencies $$A\to B,\quad A\to C,\quad B\to D,\quad C\to D,\quad C\to E,\quad D\to F,\quad E\to F.$$
A C E B D F, (ii) A B D C E F, (iii) A B C E D F.Dependencies: $P\to Q,\ Q\to R,\ R\to S,\ S\to Q$. Run Kahn's algorithm by hand (repeatedly remove an in-degree-0 node). What happens, and what does the result say about the plan?
Run the scheduler of the lecture by hand on the DAG of exercise Plan → DAG → Order. The scheduler repeats the four steps of The Scheduler Loop (ready set, dispatch, wait, block); the procedure $\textbf{Schedule}$ below Notation for the Scheduler writes them out. Two workers are available, and ready tasks are dispatched in alphabetical order. Task A takes 1 time unit, B takes 3, every attempt of C takes 1, and D, E and F take 1 each. C runs inside $\textbf{Checked-Step}_C$ with the retry cap $\kappa = 2$.
Peer-reviewed papers
Preprints & other non-peer-reviewed papers