💻 computer science

When Can Agents Safely Checkpoint, Fork, Restore, and Merge? Exact Checking for Execution Edits

This paper presents an exact algorithm that determines the safety of agent execution edits (such as checkpointing, forking, restoring, and merging) by computing all valid continuations that preserve required results and avoid policy violations, with formal verification provided via Lean mechanization and empirical validation.

Original authors: Yusheng Zheng, Xiaoyu Song, Yanpeng Hu, Lebin Cheng, Yuxi Huang, Wei Zhang

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yusheng Zheng, Xiaoyu Song, Yanpeng Hu, Lebin Cheng, Yuxi Huang, Wei Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern digital landscape, software agents act as autonomous assistants, capable of performing complex tasks by calling upon external tools. They can check flight schedules, process payments, or approve purchases, moving step-by-step through a workflow. However, these agents are not infallible; they can make mistakes, encounter unexpected roadblocks, or simply need to change direction mid-task. To handle this, developers have built systems that allow an agent to pause its work, save its current state, and later resume from that point, or even split its path to explore multiple options simultaneously. These capabilities—saving a snapshot of progress, branching into new paths, or merging different outcomes back together—are known as execution edits. They are essential for flexibility, allowing a task to recover from errors or explore alternatives without starting over from the beginning. Yet, this flexibility introduces a profound risk. If an agent is allowed to rewind or branch freely, it might accidentally repeat a critical action, such as authorizing a payment twice, or discard a result that the task still desperately needs. The challenge lies in ensuring that when an agent asks to change its path, the system can verify that the new path remains safe and compliant with all rules, without relying on the agent's own potentially flawed description of what it intends to do.

Researchers have developed a rigorous method to solve this problem, creating a system that can definitively determine whether a requested change to an agent's workflow is safe. The core of their work is an exact checker, a mathematical engine that examines the entire history of an agent's actions, not just its current state. When an agent requests to save a checkpoint, fork into a new branch, restore a previous state, or merge two paths, this checker does not simply ask the agent what it plans to do next. Instead, it looks at the immutable record of what has already happened: which tools were called, which permissions were granted, and which results are still required to finish the job. The system then calculates every possible way the task could continue from that point forward. It systematically eliminates any path that would violate a policy, such as authorizing a payment twice, or any path that would leave a necessary result unfinished. If at least one safe path remains, the system allows the edit to proceed and provides the agent with the specific rules it must follow to stay on that safe path. If no safe path exists, the system rejects the request and provides a clear proof of why it is impossible to continue safely, preventing the agent from ever entering a dangerous state.

The researchers demonstrated that this approach is far more reliable than previous methods, which often relied on the agent's own description of its workflow or failed to account for the complex interactions between different branches of a task. In their study, they showed that simply knowing the list of past actions is not enough; the system must also understand the specific relationships between those actions, such as which calls refer to the same underlying permission. They proved that if any part of this detailed history is missing, the system cannot guarantee safety. For instance, if the system knows a payment was authorized but does not know which specific transaction it belongs to, it cannot prevent a restored branch from accidentally authorizing the same payment again. By maintaining a complete and precise record of every call, every permission, and every required outcome, the new checker can distinguish between safe and unsafe edits with absolute certainty.

To validate their findings, the team built a working version of this checker and tested it against a wide variety of scenarios, including complex tasks with up to 128 different possible outcomes. The system proved capable of making these safety decisions in a fraction of a second, ranging from 0.11 milliseconds for simple cases to about 53 milliseconds for the most complex ones. In cases where an edit was unsafe, the system quickly identified the conflict and rejected it, often in less than six milliseconds. The researchers also used formal mathematical proofs, verified by a computer program, to demonstrate that their method works correctly for all six types of workflow edits they studied. These proofs confirmed that the system preserves the safety of the task even when the agent makes multiple changes, restarts after a crash, or when different parts of the system are running at the same time. The result is a robust framework where an agent can explore, recover, and adapt its workflow with the confidence that it will never accidentally break the rules or lose a critical result.

This work fundamentally changes how we think about managing autonomous agents. It moves the responsibility for safety from the agent, which might be confused or malicious, to a trusted runtime system that acts as a guardian. This guardian does not guess or hope for the best; it calculates the exact boundaries of what is possible. It ensures that every time an agent pauses to save its progress or splits its attention to try different approaches, the system has already verified that the future remains open and safe. The researchers found that this level of precision is not just a theoretical ideal but a practical reality, capable of handling the messy, non-linear nature of real-world tasks. By deriving the rules for safety directly from the history of what has already happened, rather than from the agent's current intentions, the system creates a reliable foundation for the next generation of autonomous software. The ability to fork, restore, and merge workflows without fear of disaster means that these agents can be more ambitious, tackling tasks that require exploration and recovery, secure in the knowledge that a precise, unyielding logic is watching over them.

Technical Summary: Exact Checking for Execution Edits in Agent Runtimes

Problem Statement

Agent runtimes supporting tool-using agents often require dynamic manipulation of execution flows, including Checkpointing (saving state), Forking (branching into alternatives), Restoring (reverting to a saved state), and Merging (combining branches). These operations, termed execution edits, allow for exploration, recovery, and reuse without restarting a task.

However, existing systems lack a rigorous method to determine the safety of these edits. An unsafe edit can lead to policy violations, such as:

Double Authorization: Authorizing a one-time tool action (e.g., a purchase approval) twice because a restored branch repeats a previous step.
Discarding Required Results: Removing a branch that contains a necessary outcome for the task.
Conflicting Actions: Merging branches that result in incompatible sequences (e.g., paying two suppliers when only one is allowed).

The core challenge is that the Agent is untrusted and may request an edit that omits earlier actions or required results. The trusted runtime cannot rely on the Agent's description of the execution. Instead, it must derive safety conditions strictly from the immutable execution record, which contains the workflow structure, authorization logs, and call progress. Existing approaches either rely on the Agent to supply safety constraints or fail to derive the complete safety condition from the recorded execution history.

Methodology

The paper proposes an exact checker that determines whether a requested execution edit is safe by deriving the necessary preservation constraints directly from the execution record.

1. Execution Record and Model:
The system models the execution state as a well-formed record containing:

Workflow Structure: A directed acyclic graph (DAG) of branches, choices, and parallel/sequential compositions.
Authorization Log: An append-only log of authorized tool actions.
Call Identity: A mapping of workflow calls to specific tool actions, distinguishing between new authorizations and reused authorizations (crucial for Fork/Restore operations where calls may refer to the same underlying action).
Policy: A regular language defining valid sequences of authorization labels.

2. The Safety Condition:
A safe edit must satisfy four conditions:

Preservation of Required Results: Every result required before the edit must remain required, be satisfied by the current record, or be explicitly removed by the policy authority.
Policy Compliance: Every allowed partial execution must obey the policy, accounting for existing authorizations.
Completable: Every allowed partial execution must extend to a complete, policy-compliant execution.
Universal Completeness: For every result compatible with a partial execution, a safe completion must exist.

3. The Exact Checking Algorithm:
The checker operates by:

Deriving the Edited Workflow: Constructing the target workflow from the execution record and the requested edit rule.
Classifying Authorizations: Determining for every workflow call whether it creates a new authorization or reuses an existing one based on the action history.
Computing the Largest Safe Execution Set:
- The algorithm generates all possible complete executions for the target workflow.
- It iteratively prunes executions that violate the safety condition (specifically, those that, after a partial execution, leave a still-required result without a safe completion).
- This process uses a greatest fixed-point computation ( $\nu \mathcal{B}.\Phi(\mathcal{B})$ ) to find the largest set of executions where every compatible result remains completable.
Output:
- Accepted: If the fixed point is non-empty, the system returns the largest safe execution set.
- Rejected: If the fixed point is empty, the system returns a checkable proof listing the order of removals and reasons why no safe implementation exists.

4. Atomic Enforcement:
To ensure safety during runtime, the system employs an atomic rule update:

Before applying an edit, the runtime re-checks the execution record to ensure no concurrent tool calls have modified the state since the check.
If the state is unchanged, the runtime atomically switches the active rule version, activates the new automaton (derived from the safe execution set), and updates authorization tokens.
This ensures that overlapping calls are checked entirely under either the old or new rules, preventing race conditions.

Key Contributions

Safety Model: The paper defines safety for Checkpoint, Fork, Restore, and Merge based on the execution record rather than Agent input. It proves that exact checkers must distinguish cases based on four specific record components: workflow structure, call-action identity, authorization history, and active rule versions.
Exact Checking and Atomic Enforcement: The authors construct an executable checker that returns all safe ways to proceed or a proof of impossibility. The checker handles the six forms of Fork, Restore, and Merge exactly. The runtime protocol ensures atomic rule updates and preserves safety across restarts and repeated edits.
Mechanization and Validation: The core logic is mechanized in Lean, proving the soundness of the finite checker and runtime invariants. The system is validated with 19 paper-specific tests and 62 regression tests, covering execution sizes from 2 to 128 results.

Results

Correctness: The formal results establish that the checker accepts an edit if and only if a safe runtime implementation exists. The runtime behavior is proven to be weakly bisimilar to an ideal atomic machine.
Necessity of Record Information: The paper proves that omitting any of the four key record components (workflow, identity, authorizations, rules) makes the checker non-exact; different records indistinguishable by a partial view can require opposite verdicts.
Performance: In experiments, the checker processes accepted instances (2–128 results) in 0.11–53.47 ms and rejected instances in 0.11–5.51 ms.

Significance and Claims

The paper claims to provide the first exact decision procedure for execution edits in untrusted agent runtimes. Unlike prior work that relies on supplied models or synthesis, this approach derives the complete safety condition from the recorded execution.

The authors emphasize that their approach prevents the runtime from being tricked by an Agent's description of the execution. By strictly enforcing that edits preserve past authorizations and required results, the system guarantees that tool actions are not duplicated and required outcomes are not discarded. The work bridges the gap between dynamic workflow editing and formal security guarantees, ensuring that complex operations like branching and merging do not violate policy constraints or compromise task integrity. The formal guarantees hold across arbitrary sequences of edits, tool calls, and system restarts.