# How to run tree search over an agent's environment with sandbox forks

Make each sandbox a search node: fork it per candidate action, score the children, pause the best and stop the rest.

**On Runtime a node that waits in the frontier is paused, so it holds its
files, memory and processes and pays no compute**, and forking a paused
sandbox leaves it paused. Each fork call makes 1 to 10 children. A child that
waits on the model costs $0.03125 an hour at 2 vCPU and 4 GiB, and paused
state is billed at $0.08 per decimal GB per 30-day month, at rates published
on 25 September 2026 ([pricing](/docs/pricing)).

## Search over states, not just over text

Tree of Thoughts, from Yao and others in 2023, lets a language model consider
several reasoning paths, evaluate its own choices, and look ahead or backtrack.
Its authors report that GPT-4 with chain-of-thought prompting solved 4% of
Game of 24 tasks and Tree of Thoughts 74% (arXiv 2305.10601, read
25 September 2026).

For an agent that acts on a computer, the state is not only text. It is a
repository with half an edit applied, a database after a migration, a server
that is up or down. Searching over those states means being able to copy a
machine at any step and try something else from exactly there. That is what a
fork is: a new sandbox with the source's files, memory and running processes.

## How the pieces map

| Search concept  | In Runtime                                                    |
| --------------- | ------------------------------------------------------------- |
| Node            | A sandbox                                                     |
| Expand a node   | `node.fork({ count: k })`, one child per candidate action     |
| Apply an action | `child.exec(...)` or an agent step with sandbox tools         |
| Value of a node | A score your code computes inside the child: tests, a checker |
| Frontier        | The best children, paused: memory kept, no compute billed     |
| Prune           | `child.stop()`                                                |
| Backtrack later | `node.snapshot({ retentionDays })`, then create from it       |

## Beam search, the core loop

Beam search keeps the best `B` nodes at each depth and expands each into `K`
children. `propose` is your model call; `score.py` is your value function.

```ts check
import { Sandbox } from "withruntime";

type Node = { sbx: Sandbox; score: number; path: string[] };
const B = 3; // beam width
const K = 3; // children per node
const DEPTH = 4;

// Your model: k candidate shell actions for this node, given what happened so far.
async function propose(node: Node, k: number): Promise<string[]> {
  return Array.from(
    { length: k },
    (_, i) => `echo step-${node.path.length}-${i} >> /workspace/log`,
  );
}

async function expand(node: Node): Promise<Node[]> {
  const actions = await propose(node, K);
  if (actions.length === 0) return [];
  const children = await node.sbx.fork({ count: actions.length });
  return Promise.all(
    children.map(async (child, i) => {
      await child.exec(actions[i]!, { cwd: "/workspace", timeoutMs: 120_000 });
      const value = await child.exec(["python3", "/workspace/score.py"], { timeoutMs: 60_000 });
      return {
        sbx: child,
        score: Number(value.stdout.trim()) || 0,
        path: [...node.path, actions[i]!],
      };
    }),
  );
}

const root = await Sandbox.create({ timeoutSeconds: 3600 });
await root.files.write("/workspace/score.py", "print(0)\n"); // replace with your value function
let frontier: Node[] = [{ sbx: root, score: 0, path: [] }];

for (let depth = 0; depth < DEPTH; depth++) {
  const children = (await Promise.all(frontier.map(expand))).flat();
  await Promise.all(frontier.map((n) => n.sbx.stop())); // parents are no longer needed
  children.sort((a, b) => b.score - a.score);
  frontier = children.slice(0, B);
  await Promise.all(children.slice(B).map((n) => n.sbx.stop())); // prune
  await Promise.all(frontier.map((n) => n.sbx.pause())); // wait without compute
}

const best = frontier[0]!;
console.log(best.score, best.path);
await Promise.all(frontier.map((n) => n.sbx.stop()));
```

```python check
from withruntime import Sandbox

B, K, DEPTH = 3, 3, 4  # beam width, children per node, depth


def propose(node, k):
    """Your model: k candidate shell actions for this node."""
    return [f"echo step-{len(node['path'])}-{i} >> /workspace/log" for i in range(k)]


def expand(node):
    actions = propose(node, K)
    if not actions:
        return []
    children = node["sbx"].fork(count=len(actions))
    out = []
    for child, action in zip(children, actions):
        child.exec(action, cwd="/workspace", timeout_ms=120_000)
        value = child.exec(["python3", "/workspace/score.py"], timeout_ms=60_000)
        try:
            score = float(value.stdout.strip())
        except ValueError:
            score = 0.0
        out.append({"sbx": child, "score": score, "path": node["path"] + [action]})
    return out


root = Sandbox.create(timeout_seconds=3600)
root.files.write("/workspace/score.py", "print(0)\n")  # replace with your value function
frontier = [{"sbx": root, "score": 0.0, "path": []}]

for depth in range(DEPTH):
    children = [child for node in frontier for child in expand(node)]
    for node in frontier:
        node["sbx"].stop()  # parents are no longer needed
    children.sort(key=lambda n: n["score"], reverse=True)
    frontier, pruned = children[:B], children[B:]
    for node in pruned:
        node["sbx"].stop()
    for node in frontier:
        node["sbx"].pause()  # wait without compute

best = frontier[0]
print(best["score"], best["path"])
for node in frontier:
    node["sbx"].stop()
```

A paused node wakes by itself when a request reaches it, usually in about half
a second, and a fork of a paused sandbox stays paused while its children run.
So the next round's `expand` needs no explicit wake.

## Keeping nodes to come back to

Beam search forgets pruned nodes. Monte Carlo tree search and best-first
search come back to them. For those, keep a snapshot of a node before stopping
it, and start a sandbox from the snapshot when the search returns there:

```ts check
import { Runtime, Sandbox } from "withruntime";

const runtime = new Runtime();
const node = await Sandbox.connect("a-node-worth-keeping");
const saved = await node.snapshot({ name: "node-2-1", retentionDays: 1 });
await node.stop();
// ... later, when the search backtracks here:
await using revisit = await runtime.sandboxes.create({ snapshot: saved.id });
await runtime.snapshots.delete(saved.id); // once no branch needs it
```

A snapshot is billed on the bytes it alone stores, and a block two of your
snapshots share counts once, so nodes that differ by a few files cost little
more than one ([pricing](/docs/pricing#snapshots-images-and-volumes)).

## Choosing a value function

The search is only as good as its scores. Ones that work on a real machine:

- **Tests passed**, as a fraction, for a coding task.
- **A verifier's verdict**, such as a type checker, a proof checker or a
  schema validator.
- **A measured quantity**: runtime of a benchmark, size of a bundle, rows a
  query returns correctly.
- **A model's judgement**, as a last resort, ideally of the node's observable
  state rather than of the agent's own account of it.

Run the scorer inside the child, where the state is. Keep it in a place the
agent's actions do not touch, or rewrite it into each child before scoring.

## What tree search needs

| Need                                    | How Runtime covers it                                                      |
| --------------------------------------- | -------------------------------------------------------------------------- |
| Copying a state mid-task                | Forks copy files, memory and processes; about a second for a fresh sandbox |
| Many children at once                   | 1 to 10 per fork call; 100 sandboxes at once on a paid account to start    |
| A frontier that waits cheaply           | Pause stops compute billing; paused state kept 1 to 365 days               |
| Branches that cannot corrupt each other | Every node is a separate microVM with its own kernel and disk              |
| Returning to a pruned node              | Snapshots kept 1 to 365 days, copied off their server when taken           |
| Clean-up after a crash                  | Leases end on their own; label every node and list them by label           |

## What it costs

Take 100 searches a month with beam width 3, three children per node and depth
4: 36 children a search, 3,600 in all. Each child runs for 2 minutes on 2 vCPUs
and 4 GiB, and its action plus scoring use 30 CPU-seconds:

```
CPU:    3,600 × 30 s / 3,600 × $0.025             = $0.75
Memory: 3,600 × 120 s / 3,600 × 4 GiB × $0.0075   = $3.60
Total:                                              $4.35
```

That is about 4 cents a search, at $0.025 per vCPU-hour of measured CPU and
$0.0075 per GiB-hour while running ([pricing](/docs/pricing)). Paused
frontier nodes add paused storage for the minutes they wait. The fork
snapshots that make the children are free. A new account's 50 free hours need
no card.

## Sources

- Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan
  Cao and Karthik Narasimhan, [Tree of Thoughts: Deliberate Problem Solving with
  Large Language Models](https://arxiv.org/abs/2305.10601), 2023, read
  25 September 2026.

Related: [parallel agent exploration](/use-cases/parallel-agent-exploration),
[what a sandbox snapshot is](/glossary/sandbox-snapshot),
[pause and resume a sandbox](/how-to/pause-and-resume-a-sandbox),
[RL environments](/use-cases/rl-environments),
[what a sandbox fork is](/glossary/sandbox-fork).

Facts on this page were checked on 25 September 2026.