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).

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

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.

TypeScriptimport { Sandbox } from "withruntime";type Node = { sbx: Sandbox; score: number; path: string[] };const B = 3; // beam widthconst K = 3; // children per nodeconst 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 functionlet 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()));

Pythonfrom withruntime import SandboxB, K, DEPTH = 3, 3, 4  # beam width, children per node, depthdef 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 outroot = Sandbox.create(timeout_seconds=3600)root.files.write("/workspace/score.py", "print(0)\n")  # replace with your value functionfrontier = [{"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 computebest = 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:

TypeScriptimport { 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).

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

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:

TextCPU:    3,600 × 30 s / 3,600 × $0.025             = $0.75Memory: 3,600 × 120 s / 3,600 × 4 GiB × $0.0075   = $3.60Total:                                              $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). 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, 2023, read 25 September 2026.

Related: parallel agent exploration, what a sandbox snapshot is, pause and resume a sandbox, RL environments, what a sandbox fork is.

Facts on this page were checked on 25 September 2026.