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

On Runtime, a node that waits in the frontier is paused. It keeps its files, memory and processes, and it pays no compute. Forking a paused sandbox leaves it paused. Each fork call makes 1 to 100 children. A child that waits on the model costs $0.03125 an hour at 2 vCPU and 4 GiB. Paused state is billed at $0.08 per decimal GB per 30-day month. These are the rates published on 26 October 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 solved 74% (arXiv 2305.10601, read 26 October 2026).

For an agent that acts on a computer, the state is more than text. It is a repository with half an edit applied, a database after a migration, or a server that is up or down. Searching over those states means you can copy a machine at any step and try something else from exactly that point. 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. It expands each of them 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 on its own when a request reaches it. 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. Start a sandbox from the snapshot when the search returns to that node:

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. A block that two of your snapshots share counts once. Nodes that differ by a few files therefore cost little more than one node (pricing).

Choosing a value function

The search is only as good as its scores. These scores 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, or rows a query returns correctly.
• A model's judgment, as a last resort. Ideally, the model judges the node's observable state, not the agent's own account of it.

Run the scorer inside the child, where the state is. Keep the scorer in a place the agent's actions do not touch, or copy 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. Its action plus scoring uses 30 CPU-seconds:

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. Every account gets 100 free hours of a 1 GB machine in its first 30 days, with no card required.

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 26 October 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 26 October 2026.