分支探索要 observation-equivalent restore：Columbia Eugene Wu 等 StateFork，Waypoint +26% / 探索最高 70% 更快

View PDF HTML (experimental)

Abstract: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.

Submission history

From: Jiakai Xu [view email]
[v1] Tue, 29 Sep 2026 23:11:44 UTC (263 KB)