# Recursive task solver

`RecursiveTaskSolver` in `com.tnsai.coordination.roma` splits a task that is too big for one call into sub-tasks, solves them, and combines the answers. Sub-tasks that are still too big are split again, so the work forms a tree. A verifier checks each answer before it is used.

## How a task is solved

`solve(task)` starts at depth 0. At each depth:

1. If the depth has reached `maxDepth`, or the `Atomizer` says the task is atomic, the task is solved directly.
2. Otherwise the `TaskDecomposer` splits it into sub-tasks. An empty list means the task is solved directly after all.
3. Each sub-task is solved at the next depth, one after another. If any sub-task fails, the whole branch fails at once.
4. The solver agent combines the sub-results. Its prompt lists the original task and each sub-task with its result.
5. The `Verifier` checks the combined answer once. If it rejects the answer, the branch fails.

Solving directly means the solver agent gets the task text through `chat`, and the verifier checks the answer. A rejected answer is tried again, up to `maxRetries` attempts in total. The retry sends the same task text; the verifier's feedback is recorded in the trace but not passed to the solver. When every attempt is rejected, the task fails.

## Building a solver

| Builder method | Default | Meaning |
|---|---|---|
| `solver(agent)` | required | Answers atomic tasks and combines sub-results |
| `decomposer(decomposer)` | required | Splits a task into sub-tasks |
| `atomizer(atomizer)` | `Atomizer.depthBased(3)` | Decides whether to solve a task directly |
| `verifier(verifier)` | `Verifier.alwaysAccept()` | Accepts or rejects an answer |
| `maxDepth(n)` | 5 | Depth at which every task is solved directly |
| `maxRetries(n)` | 2 | Attempts per atomic task, including the first |

With the defaults, the depth-based atomizer stops splitting at depth 3, before `maxDepth` is reached.

<!-- java-contract: src/main/java/com/example/tnsai/docs/RecursiveSolverExample.java -->
```java
package com.example.tnsai.docs;

import com.tnsai.agents.Agent;
import com.tnsai.coordination.roma.Atomizer;
import com.tnsai.coordination.roma.RecursiveTaskSolver;
import com.tnsai.coordination.roma.RecursiveTaskSolver.SolveResult;
import com.tnsai.coordination.roma.RecursiveTaskSolver.SolveTrace;
import com.tnsai.coordination.roma.TaskDecomposer;
import com.tnsai.coordination.roma.Verifier;

/** Compilation contract for multi-agent/recursive-solver.md. */
public final class RecursiveSolverExample {

    private RecursiveSolverExample() {
    }

    static SolveResult solve(Agent solver, Agent planner, Agent reviewer) {
        RecursiveTaskSolver roma = RecursiveTaskSolver.builder()
            .solver(solver)
            .decomposer(TaskDecomposer.llmBased(planner))
            .atomizer(Atomizer.depthBased(2))        // depth 0 and 1 split, depth 2 is solved directly
            .verifier(Verifier.llmBased(reviewer))
            .maxDepth(4)
            .maxRetries(3)                           // attempts per atomic task
            .build();

        SolveResult result = roma.solve("Write a migration guide for moving from REST to gRPC");

        for (SolveTrace trace : result.traces()) {
            System.out.println("  ".repeat(trace.depth()) + trace.type() + " " + trace.detail());
        }
        if (!result.success()) {
            System.out.println("No accepted answer after " + result.durationMs() + " ms");
        }
        return result;
    }

    static Verifier lengthCheck() {
        return (task, result, attempt) -> result.length() > 200
            ? Verifier.Result.accept("Long enough")
            : Verifier.Result.reject("Too short on attempt " + attempt);
    }
}
```

## Components

All three components are functional interfaces, so a lambda works in place of the built-ins.

| Interface | Method | Built-ins |
|---|---|---|
| `Atomizer` | `isAtomic(task, depth)` | `depthBased(maxDepth)`: atomic once `depth >= maxDepth`. `llmBased(agent)`: asks whether the task is atomic; an answer starting with "yes" means atomic. |
| `TaskDecomposer` | `decompose(task, depth)` | `llmBased(agent)`: asks for 2–5 independent sub-tasks and keeps the lines that start with `- ` or `* ` |
| `Verifier` | `verify(task, result, attemptNumber)` | `llmBased(agent)`: asks for ACCEPT or REJECT and accepts an answer that starts with "ACCEPT". `alwaysAccept()`. |

A verifier returns `Verifier.Result.accept(feedback)` or `Verifier.Result.reject(feedback)`. For the combined answer of a decomposed task, `attemptNumber` is always 1.

The LLM-based components parse plain text. If the decomposer's agent does not answer with a bulleted list, no sub-tasks are found and the task is solved directly.

## Result and traces

`SolveResult` has `success`, `output`, `traces` and `durationMs`. When the task fails, `success` is false and `output` is null; there is no partial answer.

Each `SolveTrace` has a `type`, the `task`, a `detail`, the `depth` and an `attempt` number:

| `type` | `detail` | `attempt` |
|---|---|---|
| `DECOMPOSED` | The number of sub-tasks and their text | 0 |
| `SOLVED` | The answer | The attempt number |
| `AGGREGATED` | The combined answer | 0 |
| `VERIFIED` | `ACCEPTED: …` or `REJECTED: …` with the verifier's feedback | 0 |

Answers and sub-task text in `detail` are cut to 80 characters; verifier feedback is kept whole. The rejection of an atomic task's last attempt is not traced.

## Related

- [Handoffs, streams and choreography](handoffs.md)
- [Judge](judge.md)
- [Debate and peer review](debate.md)
- [Workflows](workflows.md)