Planning and task decomposition

What Is Task Decomposition?

WHY do we need it?

1. Complexity management: A single LM call has a fixed context window and limited effective reasoning depth per forward pass—while chain-of-thought prompting lets a model reason over many steps, an agent that must call external tools (search, code, APIs) cannot fit all those interactions into one pass. Decomposition spreads the work across multiple grounded steps.
2. Failure isolation: If subtask 3 fails, you don't restart from scratch—just retry that branch.
3. Paralelization: Independent subtasks can run concurrently (e.g., fetch from 3 APIs simultaneously).
4. Interpretability: The plan is human-readable; you see why the agent took each step.

HOW does it work? The agent uses one of three strategies:

• Hierarchical planning: Top-down recursion (goal → subgoals → primitive actions).
• Forward chaining: Start from current state, apply actions until goal is reached.
• Backward chaining: Start from goal, work backward to find required preconditions.

Derivation: Why Decomposition Reduces Search Space

Problem: Given a goal $G$ and $n$ possible actions at each step, naive search over depth $d$ has complexity $O(n^d)$.

Insight: If we decompose $G$ into $k$ independent subgoals $\{G_1, G_2, \ldots, G_k\}$, each requiring depth $d/k$, the complexity becomes:

Derivation:

1. Without decomposition: Explore all $n^d$ paths to depth $d$.
2. With decomposition:
   • Solve $G_1$ in $n^{d/k}$ paths.
   • Solve $G_2$ independently in $n^{d/k}$ paths.
   • Total: $k \cdot n^{d/k}$ paths.
3. Why is this better? For $n=10, d=6, k=3$:
   • Naive: $10^6 = 1{,}000{,}000$ paths.
   • Decomposed: $3 \cdot 10^2 = 300$ paths.

The exponential becomes linear in $k$ when subgoals are independent.

Planning Strategies in Detail

1. Hierarchical Task Network (HTN) Planning

HTN planning decomposes tasks using a hierarchy of methods: each complex task has multiple refinement rules.

Algorithm:

function HTN-Plan(task, state):
    if task is primitive:
        return [action(task)]
    else:
        for each method m that decomposes task:
            subtasks = m.decompose(task, state)
            subplans = [HTN-Plan(st, state) for st in subtasks]
            if all subplans succeed:
                return concatenate(subplans)
        return FAIL

Example: Goal: "Prepare coffee"

• Method 1: [Boil water, Grind beans, Brew]
• Method 2 (if no grinder): [Boil water, Use instant coffee]

The agent checks state.has_grinder and picks a method.

Why this step? Checking state ensures the plan is feasible given current resources.

Decomposition (forward chaining):

1. Search for earthquake data API → finds USGS API.
2. Fetch data for 2023 → HTTP GET request.
3. Parse JSON → extract magnitude field.
4. Plot histogram → call matplotlib.
5. Return image to user.

Each step's output feeds the next. If step 2 fails (API down), retry or switch to CSV fallback.

2. ReAct: Reasoning + Acting

ReAct interleaves thought (reasoning about what to do) and action (tool use).

Pattern:

Thought: I need to find the current population of Tokyo.
Action: search("Greater Tokyo Area population 2026")
Observation: ~37 million (Greater Tokyo Area, world's largest metro)
Thought: Now compare to the New York metro area.
Action: search("New York metropolitan area population 2026")
Observation: ~19.5 million
Thought: Tokyo is larger by ~17.5 million.
Answer: The Greater Tokyo Area (~37M) is roughly 90% larger than the New York metro area (~19.5M).

Why "Thought"? It makes the next action grounded in the current subgoal, not random tool spam. Note on units: always specify which boundary you mean—city proper (Tokyo ~14M) vs. metro area (Greater Tokyo ~37M)—or the comparison is meaningless.

Plan (backward chaining):

1. Need: Grammy winner in year $Y$.
2. To get $Y$: release year of 1989.
3. Action 1: search("1989 Taylor Swift release year") → 2014.
4. Action 2: search("Grammy Album of the Year 2015") → Morning Phase by Beck (awarded in 2015 for 2014 albums).
5. Answer: Beck.

Why this order? We can't ask for the Grammy winner until we know the year.

3. LM-Modulo Framework

Combines LLM's creativity with external verifiers (solvers, simulators).

Loop:

1. LM proposes a plan $P$.
2. Verifier checks $P$ (e.g., run code, check constraints).
3. If valid, execute $P$. Else, LM refines based on error feedback.

Example: Planning robot actions in a kitchen.

• LLM: "Pick up mug, pour coffee, place mug on table."
• Verifier (physics sim): "Collision! Mug is inside table."
• LLM (revision): "Pick up mug, move to position above table, lower mug, release."

Why this step? The verifier catches infeasible plans before real execution (safety-critical for robots).

Common Mistakes

Example:

• Bad: "Add 2+2" → [Parse input, Identify operation, Execute addition, Format output]
• Good: Just call calculate(2+2).

Example:

• Goal: "Summarize paper X and compare to paper Y."
• Subtasks:
  • $S_1$: Fetch paper X.
  • $S_2$: Fetch paper Y.
  • $S_3$: Summarize X (depends on $S_1$).
  • $S_4$: Summarize Y (depends on $S_2$).
  • $S_5$: Compare summaries (depends on $S_3, S_4$).
• Correct order: Run $S_1 \parallel S_2$, then $S_3 \parallel S_4$, then $S_5$.

Example:

• Plan: [Search Wikipedia, Extract info, Cite source]
• Failure: Wikipedia returns "Page not found."
• Replan: [Search Google Scholar, Download PDF, Extract info, Cite source]

Active Recall Flashcards

#flashcards/ai-ml

What is task decomposition in AI agents? :: Breaking a complex goal into a DAG of simpler, executable subtasks with clear dependencies.

1. Break it down: "I'll build the base first, then the walls, then the towers, then the roof."
2. Order matters: You can't put the roof on before the walls exist! So you do them in sequence.
3. Check as you go: After building the base, you check—does it look right? Is it strong enough? If not, fix it before moving on.
4. If something breaks: Say a tower falls over. You don't throw away the whole castle! You just rebuild that tower.

That's exactly what AI agents do with big tasks. They split them into steps, do them in order, check their work, and fix mistakes. Without a plan, the AI would just guess randomly and probably fail. With a plan, it's like having LEGO instructions—it knows exactly what to do next.

Connections

• 6.2.01-Tool-augmented-LMs: Task decomposition determines when and which tools to call.
• 6.2.03-Multi-agent-systems: Each agent can have its own planner; coordination requires planning at the team level.
• 5.3.02-Chain-of-thought-prompting: CoT is single-call multi-step reasoning; agent planning adds external actions interleaved with reasoning.
• 6.2.05-Memory-in-agents: Long-term memory stores past plans and outcomes to improve future decomposition.
• 8.1.03-Reasoning-under-uncertainty: Plans must account for uncertain outcomes (use probability over actions).
• Classical AI: HTN planning from STRIPS (1971), means-ends analysis from Newell & Simon (1961).

Key Takeaway: Planning transforms an intractable search problem into a structured, verifiable process. The agent's intelligence lies not just in acting, but in deciding what to do next and recognizing when to revise.

Concept Map

Hinglish (regional understanding)