operad-task-decomposition

license	Apache-2.0
name	operad-task-decomposition
description	Use operads to formally model hierarchical task decomposition for multi-agent systems. Covers typed composition, wiring diagrams, and the relationship to DAG-of-agents architectures. Grounded in Spivak's operad work (2013-2020) and Fong & Spivak 'An Invitation to Applied Category Theory' (2019, Chapter 6). Use when decomposing complex tasks for multi-agent execution, designing DAG topologies, validating decomposition type-safety, or building compositional agent workflows. NOT for general category theory education, individual skill creation, or runtime DAG execution.
category	Research & Academic
tags	["category-theory","operads","task-decomposition","multi-agent","wiring-diagrams","spivak","composition","applied-math"]

Operad Task Decomposition

An operad formalizes "a complex thing decomposes into simpler things, and the decomposition itself composes." Each operation has typed inputs and a typed output. Composition is hierarchical: you can plug the output of one operation into the input of another, provided the types match. The composition laws (associativity and identity) guarantee that decomposition is well-defined regardless of the order you assemble the pieces.

This is the mathematical structure underlying DAG-of-agents architectures, WinDAGs, and any system where tasks decompose into subtasks with explicit interface contracts.

When to Use

• Decomposing a complex task into subtasks for multi-agent execution
• Designing DAG topologies where nodes have typed inputs and outputs
• Validating that a task decomposition is well-typed (no interface mismatches)
• Building compositional agent workflows where subworkflows can be reused
• Reasoning about parallel vs. sequential execution (monoidal product vs. composition)
• Connecting task structure to olog-defined domain types
• Understanding why certain decompositions fail at integration boundaries

NOT for: General category theory education (use textbooks). Creating individual agent skills (use skill-architect). Runtime DAG execution and scheduling (use dag-orchestrator). Evaluating output quality (use dag-quality).

---

Core Mental Models

1. What Is an Operad?

An operad O consists of:

• A set of types (also called colors, or sorts)
• For each tuple of input types (t_1, ..., t_n) and output type t, a set of operations O(t_1, ..., t_n; t)
• A composition rule: if you have an operation f: (t_1, ..., t_n) --> t and operations g_i: (...) --> t_i for each input, you can compose them to get a single operation that takes all the g_i inputs and produces output t
• An identity operation id_t: (t) --> t for each type
• Associativity: composing in stages gives the same result regardless of grouping
• Equivariance (for symmetric operads): you can permute inputs

In plain English: An operad is a collection of "ways to combine things" where:

• Each combiner has typed input slots and a typed output
• You can nest combiners (plug one combiner's output into another's input slot)
• The order of nesting doesn't matter (associativity)
• There's a trivial combiner that does nothing (identity)

2. Task Decomposition as Operad Application

The key insight: A task decomposition IS an element of an operad.

Consider a task T that decomposes into subtasks S_1, S_2, S_3. This decomposition is an operation:

    decompose_T : (S_1_output, S_2_output, S_3_output) --> T_output

The operation says: "Given the results of subtasks S_1, S_2, and S_3, here is how to combine them into the result of task T."

Each subtask S_i may itself decompose further:

    decompose_S1 : (S_1a_output, S_1b_output) --> S_1_output

Composition in the operad gives you the full decomposition:

    decompose_T . (decompose_S1, id_S2, id_S3) :
        (S_1a_output, S_1b_output, S_2_output, S_3_output) --> T_output

Associativity guarantees: It doesn't matter whether you first decompose T into (S_1, S_2, S_3) and then decompose S_1 into (S_1a, S_1b), or whether you directly decompose T into (S_1a, S_1b, S_2, S_3). The result is the same.

Why this matters for multi-agent systems: Associativity means subtask delegation is safe. An agent can delegate a subtask to another agent, who further delegates, and the overall composition is correct as long as types match at every boundary.

3. Colored Operads for Typed Task Decomposition

A colored operad (also called a multicategory) is an operad where the types (colors) carry semantic meaning. In task decomposition:

• Types represent the kinds of artifacts that flow between agents
• An operation with input types (CodeReview, TestResults) and output type MergeDecision means: "given a code review and test results, produce a merge decision"
• Type mismatches are caught at design time, not runtime

Type examples for an agent workflow:

Types:
  ProblemDescription     -- natural language task specification
  DomainAnalysis         -- structured analysis of the problem domain
  DAGTopology            -- a validated directed acyclic graph of subtasks
  AgentOutput            -- raw output from a single agent execution
  QualityReport          -- evaluation of an agent's output
  SynthesizedResult      -- combined output from multiple agents
  FinalDeliverable       -- the completed, reviewed work product

Typed operations:

analyze : (ProblemDescription) --> DomainAnalysis
decompose : (DomainAnalysis) --> DAGTopology
execute_node : (ProblemDescription, DAGTopology) --> AgentOutput
evaluate : (AgentOutput, ProblemDescription) --> QualityReport
synthesize : (AgentOutput, AgentOutput, ...) --> SynthesizedResult
finalize : (SynthesizedResult, QualityReport) --> FinalDeliverable

Type-checking a decomposition: Before executing a DAG, verify that every edge's source type matches the target node's expected input type. This is a static check -- no agent needs to run. If types don't match, the decomposition is invalid and must be revised.

4. The Operad of Wiring Diagrams

Spivak's operad of wiring diagrams (2013) provides a visual and formal language for system composition:

• A box represents a system with typed input ports and typed output ports
• A wiring diagram connects output ports of inner boxes to input ports of other inner boxes (or to the outer box's output ports)
• The outer box's input ports feed into inner boxes
• Composition: you can replace any inner box with a wiring diagram of smaller boxes

    ┌──────────────────────────────────────┐
    │            Outer Box                 │
    │   ┌──────┐         ┌──────┐         │
    │   │ Box A │──out──>│ Box B │──out──>─┤──> final output
    │   └──────┘         └──────┘         │
    │       ^                              │
    ├──>────┘                              │
    │  input                               │
    └──────────────────────────────────────┘

This IS the WinDAGs architecture:

• Each box = an agent node in the DAG
• Each port = a typed input or output
• Wiring = edges in the DAG with type annotations
• Composition = replacing a node with a sub-DAG (hierarchical decomposition)

The operad structure guarantees: Any valid wiring diagram can be composed with any other valid wiring diagram (at matching ports), and the result is again a valid wiring diagram. This is the formal basis for "DAGs of DAGs" -- hierarchical agent orchestration.

5. The Monoidal Product for Parallelism

In an operad, the monoidal product (tensor product) models parallel execution:

    f : (A, B) --> C     -- sequential: f needs both A and B to produce C
    g : (D) --> E         -- independent operation

    f tensor g : (A, B, D) --> (C, E)  -- f and g run in parallel

For DAG scheduling:

• Operations that share NO input dependencies can be tensored (run in parallel)
• Operations with data dependencies must be composed (run sequentially)
• The wave-based execution model in DAG orchestrators is exactly the monoidal product applied per-wave: all nodes in a wave run in parallel (tensor), and waves execute sequentially (composition)

Practical implication: The operad structure tells you the MAXIMUM parallelism possible in a decomposition. If your DAG scheduler achieves less parallelism, it's leaving performance on the table. If it attempts more, it will produce type errors (using outputs before they're available).

6. Connection to Ologs

Types in an operad can reference objects in an olog. If you have an olog defining your domain (types = "a customer", "an order", "a product"), then the operad's colors can be the objects of that olog.

An operation in the operad like:

    process_order : (Customer, OrderDetails, InventoryStatus) --> FulfillmentPlan

has its input and output types grounded in the olog's type system. This means:

• The olog defines WHAT things exist in the domain
• The operad defines HOW tasks involving those things decompose
• Functors between ologs (problem equivalence) lift to natural transformations between operads (solution transfer)

---

Decision Framework: Constructing an Operad from a Task Description

Step 1: Identify the Types (Colors)

List every distinct kind of artifact that flows between agents or between stages of the task.

Test: Two artifacts have the same type if and only if they can be used interchangeably as input to any downstream operation. If artifact A can substitute for artifact B in every context, they have the same type. If there exists ANY operation that accepts A but not B, they have different types.

Common mistake: Too few types. Using "string" or "text" for everything defeats the purpose. Types should carry semantic meaning: "CodeReview" is different from "TestResults" even if both are strings.

Step 2: Identify the Operations

For each task or subtask, specify:

• What types of inputs does it require?
• What type of output does it produce?
• Is the operation deterministic or nondeterministic?

Format: operation_name : (InputType1, InputType2, ...) --> OutputType

Test for completeness: Can you chain the operations to get from the initial input types to the final output type? If there's a gap (no operation produces a type that a downstream operation needs), you're missing an operation.

Step 3: Define the Composition Rules

For each pair of operations where one's output type matches another's input type, verify that composition is well-defined:

• Does plugging operation A's output into operation B's input produce a meaningful result?
• Is the composition associative? (If A feeds B feeds C, does it matter whether you compute A-then-B first, or B-then-C first?)

For deterministic operations: Associativity is automatic. For nondeterministic operations (LLM calls): Associativity is approximate. Document the degree of variability.

Step 4: Identify Parallelism

Group operations by their data dependencies:

• Operations with NO shared inputs can be tensored (parallel)
• Operations where one's output feeds another's input must be composed (sequential)

This gives you the DAG topology:

Wave 1: {operations with only initial inputs}      -- all in parallel
Wave 2: {operations depending on Wave 1 outputs}   -- all in parallel
Wave 3: {operations depending on Wave 2 outputs}   -- all in parallel
...
Final:  {operation producing the final deliverable}

Step 5: Validate the Operad

1. Type consistency: Every edge in the DAG has a source type that matches the target input type
2. Completeness: There exists a path (sequence of compositions) from initial inputs to final output
3. No cycles: The composition graph is acyclic (this is what makes it an operad application, not a general category)
4. Identity check: For every type t, the identity operation id_t exists and acts as expected (passing through without modification)
5. Associativity check: For any three composable operations, both groupings produce the same result

---

Practical Implementation: Operads in TypeScript/JSON

Represent an operad for a task decomposition as a JSON schema:

interface OperadType {
  name: string;
  description: string;
  schema?: object;  // JSON Schema for the type's instances
}

interface OperadOperation {
  name: string;
  inputs: { name: string; type: string }[];  // references OperadType.name
  output: { type: string };                   // references OperadType.name
  agent?: string;                             // which agent/skill executes this
  parallelizable_with?: string[];             // operations that can run in parallel
}

interface TaskOperad {
  types: OperadType[];
  operations: OperadOperation[];
  composition_order: string[][];  // waves: each inner array runs in parallel
}

Example:

{
  "types": [
    { "name": "ProblemDescription", "description": "Natural language task spec" },
    { "name": "DomainAnalysis", "description": "Structured domain breakdown" },
    { "name": "CodePatch", "description": "A diff that modifies source code" },
    { "name": "TestResults", "description": "Pass/fail with coverage report" },
    { "name": "FinalDeliverable", "description": "Reviewed, tested code change" }
  ],
  "operations" 
    
       
            
          
       
    
    
       
       
             
             
      
          
       
    
    
       
            
          
       
    
    
       
       
             
             
      
          
       
    
  
   
    
    
    
    
  

Type-checking algorithm:

For each operation op in topological order:
  For each input (name, type) of op:
    Find the upstream operation that produces this type
    Verify it exists and appears in an earlier wave
    Verify the type names match exactly

If any check fails: INVALID decomposition. Report the type mismatch.

---

Relationship to WinDAGs

The WinDAGs architecture is an instantiation of the operad of wiring diagrams:

Operad Concept	WinDAGs Equivalent
Type (color)	Node output schema
Operation	Agent node with skill assignment
Composition	Edge connecting nodes
Identity	Pass-through node
Monoidal product	Wave (parallel execution group)
Wiring diagram	The DAG itself
Nested wiring diagram	Sub-DAG (hierarchical decomposition)
Associativity	"Decompose T into sub-DAGs, or directly into leaves -- same result"

The WinDAGs Decomposer agent is performing operad construction: Given a problem description, it produces a wiring diagram (DAG topology) where each box (node) has typed inputs and outputs, and the wiring (edges) respects type compatibility.

The WinDAGs Mutator is performing operad substitution: When a node fails and the DAG needs restructuring, the mutator replaces an operation with a different operation of the same type signature, or decomposes it into sub-operations. The operad structure guarantees the replacement is type-safe.

---

Anti-Patterns

The Untyped DAG

Novice: Builds a DAG where every edge carries "text" or "any". Nodes accept whatever the previous node produced. Type errors surface only at runtime when an agent receives input it can't process. Expert: Every edge in a DAG should have a named, documented type. Type-checking is free (it's a static analysis) and catches integration errors before any agent runs. If you can't name the type, you don't understand the interface. Define a schema for each type. Timeline: This is the default in most LLM-based agent frameworks. The cure is adding even minimal type annotations. Start with named string types; graduate to JSON schemas.

The Megaoperation

Novice: A single operation takes 15 inputs and produces a complex output. The operation is a monolith that can't be decomposed further. Expert: If an operation has more than 4-5 inputs, it almost certainly decomposes into sub-operations. Apply the operad composition recursively: find intermediate types that split the megaoperation into stages. Each stage should have 2-3 inputs. This mirrors the "small functions" principle in software engineering, but with formal type-theoretic backing. Timeline: Common when the decomposer agent is given too little guidance about granularity. Fix by setting a max-inputs constraint on the decomposer.

The Phantom Type

Novice: Defines types that no operation produces or consumes. The type exists in the schema but has no role in the decomposition. Expert: Every type must appear as the output of at least one operation AND the input of at least one operation (except for initial input types and the final output type). Phantom types indicate either missing operations or over-specified type systems. Remove them or add the operations that connect them. Timeline: Happens when copying type lists from ologs without checking which types participate in the task workflow.

The Cycle Pretending to Be Composition

Novice: Creates a "decomposition" where operation A's output feeds B, and B's output feeds back to A. "It's iterative refinement!" Expert: Operads are acyclic by construction. Iteration is NOT composition -- it's a fixed-point computation. Model iteration as a SEPARATE operation: iterate(f, convergence_criterion) that internally applies f repeatedly until convergence. The iterate operation itself has typed inputs and outputs and participates in the operad normally. The cycle lives INSIDE the iterate box, not in the operad's wiring. Timeline: Very common in agent systems that do "revise until good." The fix is always to encapsulate the loop.

---

Shibboleths

"Operads are just DAGs" -- No. A DAG is a graph. An operad is an algebraic structure with composition laws. The key difference: an operad tells you not just the topology but also the TYPE CONSTRAINTS at every connection point, and it guarantees that composition is associative. A DAG can have arbitrary, unchecked connections.

"Why not just use function types?" -- Operad operations are multi-input, single-output. Function types (in the lambda calculus sense) are single-input, single-output (you curry multi-input functions). The operad formalism avoids currying, which means the parallelism structure is explicit: if an operation takes (A, B, C), you know A, B, and C can be computed in parallel. With curried functions f: A -> B -> C -> D, the parallelism is hidden.

"Associativity doesn't matter in practice" -- It matters enormously for hierarchical delegation. If agent X decomposes a task and delegates subtask S to agent Y, who further decomposes S and delegates sub-subtask S' to agent Z, associativity guarantees that the overall result is the same as if X had directly decomposed to the leaf level. Without associativity, delegation introduces path-dependent bugs.

"How is this different from a type system?" -- An operad IS a type system, but one specifically designed for hierarchical composition. A general type system (like TypeScript's) lets you compose functions but doesn't distinguish between sequential and parallel composition. The operad's monoidal product makes parallelism a first-class citizen.

---

Reference Files

When deeper detail is needed:

• Fong, B. & Spivak, D.I. (2019). An Invitation to Applied Category Theory: Seven Sketches in Compositionality. Cambridge University Press. Chapter 6 covers operads and wiring diagrams. The canonical accessible introduction.
• Spivak, D.I. (2013). "The operad of wiring diagrams: formalizing a graphical language for databases, recursion, and plug-and-play circuits." arXiv:1305.0297. -- The formal foundation for wiring diagram operads.
• Vagner, D., Spivak, D.I., & Lerman, E. (2015). "Algebras of open dynamical systems on the operad of wiring diagrams." Theory and Applications of Categories, 30(51). -- Extends wiring diagrams to dynamical systems; relevant for agents with internal state.
• Spivak, D.I. (2014). Category Theory for the Sciences. MIT Press. -- Broader context; Chapters 4-7 for ologs and functors that ground operad types.
• Catlab.jl documentation. algebraicjulia.org -- Implements operads computationally; useful for validation and enumeration.

---

Quality Gates

You have a valid task operad when:

• Every type has a name, description, and (ideally) a JSON schema
• Every operation has explicitly typed inputs and a typed output
• No type mismatches exist at any composition boundary
• There exists a composition path from initial input types to the final output type
• The composition graph is acyclic
• Maximum parallelism is identified (operations in the same wave share no dependencies)
• Every type is produced by at least one operation and consumed by at least one operation (except initial/final types)
• No operation has more than 5 inputs (decompose further if so)
• Iterative/looping behaviors are encapsulated inside operations, not expressed as cycles in the operad
• The operad corresponds to a valid WinDAGs DAG topology (if applicable)