Hierarchical Task Decomposition

When Tasks Get Big

The Hierarchy

Example Decomposition

Goal: Refactor authentication module to use OAuth.

  Sub-goal 1: Set up OAuth dependencies
    Task: Add dependency to requirements.txt
    Task: Configure OAuth client

  Sub-goal 2: Replace existing auth flow
    Task: Replace login endpoint
    Task: Replace session middleware
    Task: Update tests

  Sub-goal 3: Migration and rollout
    Task: Write migration script
    Task: Update documentation

LLM-Driven Decomposition

DECOMPOSE_PROMPT = '''
Decompose this goal into 3-6 sub-goals. For each sub-goal, list 2-5 concrete tasks.
Return JSON: {sub_goals: [{name, tasks: [str]}]}

Goal: {goal}
'''

Recursive Decomposition

When to Stop Decomposing

Tree Structures

@dataclass
class TaskNode:
    description: str
    status: Literal['pending', 'running', 'done', 'failed']
    children: list['TaskNode']
    result: str | None = None

Execute Depth-First

def execute(node):
    if node.children:
        for child in node.children:
            execute(child)
    else:
        node.status = 'running'
        try:
            node.result = run_leaf(node)
            node.status = 'done'
        except Exception as e:
            node.status = 'failed'

Aggregating Results

def aggregate(parent):
    summaries = [c.result for c in parent.children if c.status == 'done']
    parent.result = llm.invoke(f'Summarise these sub-task results: {summaries}').content

Surface the Tree to Users

[x] Add OAuth dependency
[x] Configure OAuth client
[~] Replace login endpoint   <-- in progress
[ ] Replace session middleware
[ ] Update tests

Allow Tree Editing

Re-Plan on Failure

if failed_count(node) > 2:
    parent = node.parent
    parent.children = llm_replan(parent, failure_context=node.last_error)

Cost of Decomposition

When to Stop Splitting

Recap