Source-linked AI summary
StateFork: Branchable Infrastructure for Agent Exploration
Jiakai Xu, Tianle Zhou, Georgios Liargkovas, Danielle Gillai, Ruizhe Fu, Patrick Shen, Eugene Wu, Kostis Kaffes
TL;DR
Terminal-agent exploration requires restoring the execution-session state that determines future observations, and doing so efficiently. StateFork separates logical exploration from physical state materialization, while Waypoint checkpoints terminal execution sessions. On Terminal-Bench, StateFork with Waypoint achieved higher task completion and faster exploration than the evaluated alternatives.
Problem
Terminal-agent branching must restore environment state that determines future observations, while keeping branch creation, restoration, and discard efficient.
Source: §1 · p. 1Method
StateFork separates logical exploration from physical state materialization, and Waypoint checkpoints terminal execution sessions using filesystem layering, process checkpointing, and a persistent terminal-compatible command session.
Source: §1 · p. 2Results
StateFork with Waypoint achieved 26% higher task completion rate than other evaluated platforms and completed exploration 70% faster than replaying commands from the initial state.
Source: §1 · p. 2Takeaways & Limitations
StateFork and Waypoint provide infrastructure for exploratory agents to represent exploration as a logical tree while restoring terminal execution sessions for observation-equivalent, physically efficient branching.
Source: §7 · p. 13Tasks relying on external services, remote APIs, or network peers outside the session may require additional coordination because StateFork does not provide a general distributed snapshot mechanism.
Source: §6 · p. 12
Abstract
from arXiv · showhide
AI agents improve task success by exploring multiple trajectories, but for computer-use agents each trajectory modifies external environment state. Branching from an intermediate point is correct only when restoration is observation-equivalent - future actions produce the same observations - and practical only when creating, restoring, and discarding branch states is physically efficient. We study this problem for terminal-using agents, where tasks modify files, shell context, running processes, and local services. We introduce StateFork, a logical control plane that separates exploration policies from physical state materialization, exposing sessions, commands, snapshots, restores, and cleanup over multiple execution substrates. We also build Waypoint, a checkpoint/restore substrate for terminal execution sessions that combines filesystem layering, process checkpointing, and a persistent terminal-compatible command session. Together, StateFork and Waypoint improve terminal-agent exploration by combining sample-efficient search with efficient restoration of the right execution state. On Terminal-Bench, branch-based exploration through StateFork and Waypoint improves task completion over pass@20 at the same visited-node budget, and using Waypoint achieves 26% higher task accuracy than other execution substrates while completing exploration up to 70% faster. These results show that observation-equivalent, physically efficient execution sessions are a key systems abstraction for exploratory AI agents.
1 Introduction
Terminal-agent exploration requires restoring the environment state that determines future observations, while keeping branch creation, restoration, and cleanup physically efficient. StateFork separates logical exploration from substrate-specific state materialization, and Waypoint checkpoints terminal execution sessions; together, they improve task completion and exploration speed on Terminal-Bench.
1 Introduction
- Terminal-agent branching must restore state that affects future observations, while keeping branch creation, restoration, and discard efficient.Terminal tasks can modify files, shell context, processes, memory, and local services, so command transcripts alone do not capture the relevant state.Source: §1 · pp. 1–2
- StateFork separates the logical exploration tree from physical state materialization and maps branch operations to substrate-specific restore mechanisms.Its layers include the agent or search policy, a logical control plane, and execution substrates such as replay, filesystem snapshots, and container or VM snapshots.Source: §1 · p. 2, Figure 1 · p. 2
- Waypoint checkpoints terminal execution sessions using filesystem layering, process checkpointing, and a persistent terminal-compatible command session.It preserves the session state that determines future terminal observations rather than the entire host machine or a portable deployment artifact.Source: §1 · p. 2
- StateFork with Waypoint achieves 26% higher task completion rate than other evaluated platforms while completing exploration 70% faster than replaying commands from the initial state.Source: §1 · p. 2
2 Fundamentals of Agent Exploration
Logical exploration allocates LLM calls across reusable trajectory prefixes, while terminal-agent branching also requires restoring execution sessions with observation equivalence and physical efficiency. Existing restoration substrates miss this combination, motivating StateFork and Waypoint.
2.1 Logical Agent Exploration
- Tree-based exploration reuses sampled prefixes and their observations to allocate later calls adaptively, unlike independent pass@k rollouts from the root.Logical exploration selects which unfinished prefixes to expand and which continuation to pursue.Source: §2.1 · p. 3
- At equal visited-node budgets, MCTS achieves higher Terminal-Bench task completion than pass@20 by reusing intermediate nodes instead of restarting from the root.Each search node corresponds to an LLM call, and Figure 2 plots task success against visited search nodes.Source: §2.1 · p. 3, Figure 2 · p. 3
2.2 Physical Requirements for Agent Exploration
- Terminal-agent branching requires observation-equivalent restoration of execution-session state, including files, shell context, processes, memory, and relevant local services.Restored states need not be bit-for-bit identical, but omitted state must not affect future observations or leak across sibling branches.Source: §2.2 · p. 4
2.3 Existing Execution Substrates Are Insufficient
- Restoration must also be physically efficient, but replay, undo, and existing checkpoints each miss part of the execution-session boundary or impose practical costs.Replay cost grows with prefix length and is fragile under nondeterminism; undo may lack faithful inverses, and file-, process-, runtime-, or VM/container-level mechanisms have scope gaps or costs.Source: §2.2 · p. 4, §2.3 · pp. 4–5
- StateFork separates logical exploration from physical materialization, while Waypoint combines filesystem layering, process checkpointing, and a persistent terminal-compatible command session.StateFork exposes branch, restore, and cleanup operations across backends; Waypoint targets observation-equivalent restoration of terminal execution sessions.Source: §2.3 · p. 5
3 StateFork: Logical Control Plane for Agent Exploration
StateFork separates an agent’s logical exploration tree from the substrate-specific mechanisms that materialize and restore its branch points. Its materialization policy balances checkpoint cost against replay cost while preserving a common interface across backends.
3 StateFork: Logical Control Plane for Agent Exploration
- StateFork separates logical branch points from physical materialization, allowing exploration policies to operate independently of how execution state is restored.Logical nodes may be virtual, storing commands to replay from a physical ancestor, or physical, backed by a substrate checkpoint.Source: §3 · pp. 5–6, §3.1 · p. 6, §3.2 · p. 6
3.1 Session Manager
- The session manager exposes commands, snapshots, restores, and cleanup while tracking the branch tree and shared metadata across substrates.Search policies can use the same interface with replay, filesystem snapshots, container or VM checkpoints, hybrid checkpoints, or Waypoint.Source: §3 · p. 6, §3.1 · p. 6
3.2 Materialization Policy
- Virtual checkpoints reduce creation and storage costs but require restoring a physical ancestor and replaying the command suffix.The Smart Decider materializes when estimated physical-checkpoint cost is no greater than accumulated replay cost; otherwise it keeps the node virtual.Source: §3.2 · pp. 6–7
- The Smart Decider uses resident memory as its sole predictor for Waypoint’s physical-checkpoint cost, with backend-specific estimates also supported.Its simple policy does not predict the future search tree or branch importance, leaving richer optimization policies for future work.Source: §3.2 · pp. 6–7
3.3 Backend Managers
- Backend managers translate logical operations into substrate-specific checkpoint, restore, execution, measurement, and cleanup operations.Logical tree management, command logging, and observability remain above the backend-specific layer.Source: §3.3 · p. 7
4 Waypoint: A Checkpoint/Restore Substrate for Terminal Agents
Waypoint checkpoints terminal-agent execution sessions by coordinating filesystem layers, process state, and a persistent shell. Its design targets local, controlled exploration, combining observation-relevant state restoration with efficient branch creation and restore.
4 Waypoint: A Checkpoint/Restore Substrate for Terminal Agents
- Waypoint composes existing Linux mechanisms at the execution-session boundary to restore the filesystem, process state, terminal state, and relevant local services.The session is full-state with respect to future terminal observations, not the entire host machine.Source: §4 · pp. 7–8
4.1 Session-Scoped Containment
- Waypoint presents a container-like root and confines ordinary task writes to a session layer, but it is not a VM security boundary.It targets controlled agent exploration and benchmark execution, not malicious tenants or privileged escape attempts.Source: §4.1 · p. 8
4.2 In-Place Filesystem Checkpointing
- Filesystem checkpoints seal the current OverlayFS upper directory and restore ancestry as read-only layers with a fresh writable layer.Recording a reference rather than copying file data avoids checkpoint creation proportional to filesystem size; overlay reconstruction requires coordinating with process checkpointing.Source: §4.2 · pp. 8–9
4.3 Stateful Shell Sessions
- A long-lived PTY-backed shell preserves shell-local state across commands while providing a programmatic command-step interface.Full-screen terminal applications, arbitrary signal delivery, live editing, and complex interactive job control are outside that interface.Source: §4.3 · p. 9
4.4 Process and Memory Checkpointing
- Waypoint coordinates OverlayFS layers with CRIU images so checkpoints preserve both durable file changes and shell and application process state.It quiesces the session, dumps the shell process tree, rebuilds the filesystem view, then restores the process tree into that view.Source: §4.4 · p. 9
4.5 Composing Primitives
- Waypoint remounts runtime filesystems after overlay reconstruction and allocates PTYs through the host devpts instance.Because the root filesystem view must be replaced, it stops the process tree rather than using CRIU’s leave-running checkpoint style.Source: §4.5 · pp. 9–10
5 Evaluation
The evaluation tests snapshot and restore costs as memory and filesystem state grow, then compares terminal-agent exploration across substrates and materialization policies. Waypoint and StateFork provide strong accuracy–efficiency trade-offs, while Smart Decider reduces the physical cost of exploration.
5.1 Microbenchmark
- Figure 4's microbenchmarks compare snapshot and restore latency across increasing memory and filesystem sizes using controlled workloads and multiple substrates.The measurements use repeated snapshots or restores and report median elapsed time.Source: §5.1 · p. 10, Figure 4 · p. 11
- Waypoint restores with lower latency than evaluated container and VM baselines across the memory range, although it is slower than bare CRIU because it restores more than process memory.It reconstructs the OverlayFS view, attaches a writable layer, remounts runtime filesystems, and resumes the process tree; its snapshot latency closely follows CRIU's process-dump cost.Source: §5.1 · p. 10
- Waypoint has the lowest latency at every evaluated filesystem size, with snapshot latency 3.6× lower and restore latency 2.1× lower than the best competing substrate.It seals the OverlayFS upper directory and rebuilds the mount stack, making the dominant work metadata remounting rather than moving file contents.Source: §5.1 · pp. 10–11, Figure 4 · p. 11
5.2 Macrobenchmark
- Waypoint reaches the best accuracy–time trade-off on Terminal-Bench; Prefix Replay reaches the same accuracy more slowly, while Docker commit and Podman-Hybrid have lower accuracy.Waypoint restores execution-session state without replaying long prefixes or paying deployment-oriented container overheads; Docker commit restores incomplete state, and Podman-Hybrid has higher overhead and failures around sockets and local services.Source: §5.2 · p. 11, Figure 5 · p. 12
- Waypoint achieves higher accuracy with fewer explored nodes than Docker commit and Podman-Hybrid, while Prefix Replay has similar node efficiency but substantially higher wall-clock cost.Figure 5 reports completion rate against wall-clock exploration time, explored nodes, and storage used.Source: §5.2 · p. 11, Figure 5 · p. 12
- Smart Decider lowers completion time by 23% on average and checkpoint storage by 58% versus eager StateFork + Waypoint materialization.Its largest gains occur when eager materialization creates checkpoints that are never restored or represent actions that are cheap to execute.Source: §5.2 · p. 12, Figure 6 · p. 12
6 Discussion and Limitations
Waypoint provides branch isolation, not a VM security boundary, and StateFork does not provide general distributed snapshots. GUI support is a possible extension, but full desktop or hardware-accelerated exploration would require broader checkpointing.
6 Discussion and Limitations
- Waypoint's session-scoped containment targets controlled agent exploration, not mutually distrustful tenants; arbitrary untrusted code should be paired with stronger sandboxing.A sufficiently privileged malicious process may exploit kernel interfaces or misconfigured mounts.Source: §6 · p. 12
- StateFork restores local state but does not provide a general distributed snapshot for external services, remote APIs, or network peers outside the session root.Observation equivalence depends on whether all task-relevant state lies inside the checkpoint boundary; auxiliary services or task-specific reset hooks may help some workloads.Source: §6 · p. 12
- Waypoint currently targets terminal agents; headless software-rendered GUI support is a natural extension, while full desktop or hardware-accelerated GUI exploration needs broader checkpointing.That broader boundary would include display and GUI processes, screenshot service, and mouse/keyboard input proxy.Source: §6 · p. 12
7 Conclusion
The conclusion argues that terminal-agent exploration benefits from reusing intermediate search nodes while restoring the execution-session state that determines future observations. StateFork separates search from physical materialization, and Waypoint efficiently captures terminal-session, filesystem, process, and memory state.
7 Conclusion
- StateFork separates agent search from physical state materialization, while Waypoint captures terminal-session, filesystem, process, and memory state for checkpoint and restore.The paper concludes that branch-based exploration improves sample efficiency and that execution-session checkpointing and selective materialization reduce its physical cost.Source: §7 · p. 13
A.1 Search Algorithms
The appendix describes pass@20 as iterative retries and MCTS as structured branching over command continuations. Both are evaluated with substantial stochastic sampling, but each configuration is run once.
A.1 Search Algorithms
- Pass@20 allows up to 20 independent trials, recording success if any trial reaches the target state.Each trial allows 30 exploratory rounds and a total of two iterations.Source: §A.1 · p. 14
- MCTS simulates alternative command continuations at each environment step, then uses an LLM-based decision module to select a move to commit.The evaluation fixes branching factor w = 3 and search depth d = 2 at each step.Source: §A.1 · p. 14
- Each configuration is evaluated in a single run, with accuracy averaged over all 77 Terminal-Bench tasks.Each condition aggregates hundreds of stochastic LLM calls, including 20 independent rollouts per task under pass@20 and a matched visited-node budget under MCTS.Source: §A.1 · p. 14