Synthesizing Rollback Systems for Safer Agents
We built an undo button for Amazon S3: a verified layer that can roll back agent mistakes. We plan to extend the same approach to handle more of the world’s infrastructure and support more safety properties.
Published:
Article: Jack Feser, Nikhil Pimpalkhare, Zenna Tavares
AI agents operate a growing share of the world’s infrastructure, but they can and do make costly mistakes. This year, agents have deleted the production databases of a car rental software company and an online course platform, backups included, and almost every file on a user’s computer. As agents start to control our power grid, supply chains, financial systems, and ultimately all our critical infrastructure, mistakes become catastrophic risks.
We need guardrails for safer agents: mechanisms to constrain them from making unwanted, unsafe actions. At Basis, we aim to make agents provably safe, with guardrails that can be trusted because they come with formal guarantees. Earlier this year we introduced Pact, a formal language that lets agents coordinate through protocols that protect privacy and integrity. Today, we report new results from a collaboration with Amazon Web Services’ Automated Reasoning Group.
We have built a research prototype of a formally verified undo button for Amazon S3: a way to roll back unwanted actions and recover the conditions before things went wrong. When developers delegate tasks on stateful APIs such as AWS to coding agents, and those agents make mistakes, our system allows the user to roll back. Our approach is general, and can extend to support guardrails beyond undo, and infrastructure beyond Amazon S3.
Our undo button works by mediating agent interactions with an API using a compensator. A compensator sits between the agent and the API. Before it passes on a call that changes state, it records how to undo that call, and it refuses any call it cannot undo. To roll back, it runs the recorded undo steps in reverse order.
Compensators give coding agents transactional semantics: either an agent’s entire workload goes through or none of it does. If an agent tries to take an action that cannot be rolled back or otherwise produces an action sequence that crashes, our system automatically rolls back the state. If the user is dissatisfied with what the agent has done, they can undo its effects with the push of a button.
In this post, we describe how we developed a compensator for Amazon’s S3 API, which has more than one hundred complex interacting operations. We plan to extend this work to the rest of AWS and then to every API for which a compensator would be useful. Prior work has explored agent-native filesystems with undo and applying database recovery ideas to agents. Our focus is synthesizing compensators for opaque, stateful APIs, with an approach that has the potential to generalize to other APIs.
We structure the remainder of this post around the key insights enabling our work.
- These APIs are too large to build compensators for by hand. We instead synthesize compensators using an agentic loop.
- Synthesizing compensators from just API documentation produces systems that are sometimes useful but generally buggy. We found that we can significantly improve the soundness of our synthesized systems by verifying them with respect to lightweight “gray box” specifications of the write footprints of API operations. This suggests that API providers can expose relatively inexpensive partial specifications that enable third parties to synthesize more reliable software.
- Naively forcing LLMs to verify the compensators they synthesize leads to overly conservative compensators which refuse most API operations. We fix this by adding a form of positive feedback to the standard counterexample-based synthesis loop.
Synthesizing Compensators
A toy API that manipulates a counter. As you send operations from the agent, the compensator handles the interaction with the API and maintains a compensation trace. At any point, click Rollback and the compensator uses the trace to return the counter to its original value. The set operation makes the compensator snapshot the current state before changing it.
Counter starts at 0. Choose an operation.A compensator rolls back operations either by (1) associating operations with corresponding inverse operations or (2) snapshotting the state before the modification and later restoring it as with the set operation. The first approach requires a deep understanding of the relationships between API operations. The second option introduces new failure modes (e.g. the snapshot can be too large and crash the compensator) and requires understanding how to reach an arbitrary given snapshotted state.
We use LLMs to generate compensators for APIs. One-shot generation results in compensators that have bugs, meaning that they fail the precise specification we are testing against. Any action sequence whose effects we cannot roll back (treating a midway abort and rollback as a successful rollback) is a valid counterexample. The compensator should either have rejected one of the actions as uncompensable or it should have successfully rolled all of the actions back.
To reduce the number of bugs in the compensator, we synthesize compensators in a feedback loop: (1) given a compensator, an LLM in a fresh context generates a failing test case, and (2) given a failing test and a compensator, an LLM repairs the compensator so that it passes the test.
This loop is a version of a classic approach to inductive program synthesis called Counterexample Guided Inductive Synthesis (CEGIS), and it is both sound and complete (in the limit) when using a sound and complete decision procedure for code and counterexample generation. LLMs, of course, are neither sound nor complete, so our loop offers no formal guarantee of correctness or progress.
We found that finding and repairing counterexamples improves the quality of the generated code, but we are left with a question: how can we be confident that we found all the counterexamples? Unfortunately, we cannot be confident that our process generates correct code, because even though they are good bug finders, LLMs are not complete bug finders. Anyone who has used an LLM for code review has experienced this effect: different LLMs find different subsets of valid bugs. Just searching for failing tests is not enough to build confidence, because we can never know if we have missed one. Instead, we need to verify our code.
Synthesizing Robust Compensators
Verifying any property of a compensator means that we need to state some properties of the API operations.
We started by writing down which parts of the API state each operation changes.
We call these properties write sets.
For the S3 API, a write set is a set of buckets, objects, and attributes that an operation writes to.
For example, CreateBucket(b) has the write set {Bucket(b)}.
Properties like these are much simpler than complete functional descriptions of the behavior of an API operation, so we think that they’re plausible for API engineers to write and maintain as machine-readable documentation, as long as they’re useful.
Using these properties, we can prove some theorems about our compensators:
- When no rollback is performed, the compensator performs no additional writes.
- When a rollback is performed, the rollback actions write to exactly the same locations as the forward actions.
While these properties fall well short of functional correctness, they give us some additional assurance that the code we generate isn’t doing anything too unsafe. The first property tells us that the compensator only touches our API state during a rollback; if no rollback happens, then the state is only changed by the forward actions. The second property tells us that no state changed by a forward action is left unchanged by the rollback.
We synthesize our compensators in Dafny, which automatically proves that our code satisfies the properties above by reducing the proof to an SMT query. This style of verification is simpler and more automated than the interactive theorem proving approach used by Lean or Rocq, particularly when proving simpler program properties. The LLM does not need to interact with the prover beyond generating code and receiving feedback on its correctness.
Introducing verification into our synthesis process gives us much more confidence that we are generating reasonable code, but it has an unfortunate side effect in our use case. We allow compensators to optionally refuse to perform a given operation. This is a necessary escape hatch because some operations (for example, sending an email) cannot be compensated!
When we began verifying properties of synthesized compensators, the LLM would produce compensators which refused to perform any operation that modifies state. This solution is technically sound (if no actions run, then the initial state is equal to the final state and the compensator is correct!), but is obviously undesirable because the agent can’t do anything.
We found that the LLM was unlikely to reach for this solution when generating unverified code, but when we began verifying its output, this became common behavior. To deal with this problem, we need to do more than generate compensators that are merely correct.
Synthesizing Robust and Featureful Compensators
Standard counterexample-driven synthesis loops only provide negative feedback to the proposer, picking at weak points in its proposed candidate. Our verification infrastructure provides even stronger negative signals, scolding the proposer with obtuse error messages whenever its candidate does not pass its check. In the presence of such negativity, it is unsurprising that the proposer becomes overly conservative and refuses any operations that modify state.
We recover coverage for these operations by introducing a form of positive feedback which we call an opportunity. An opportunity consists of a test and a single-use compensator such that:
- the current candidate compensator refuses to complete the test
- the single-use compensator successfully executes the test and rolls the state back
Intuitively, an opportunity is positive feedback that it should also be able to cover the opportunity’s test case, as evidenced by the opportunity’s single-use compensator. Note that because the single-use compensator need only work for one test case, the logic that it implements can be completely custom. One of our key assumptions is the proposer can extract a generalizable improvement to the candidate from any custom single-use compensator covering a blocked test case.
We found that incorporating opportunities in our synthesis loop resulted in compensators that were both robust and frequently useful.
We evaluated four synthesis variants on 31 held-out S3 tasks. A pass means the workload completed and rollback restored the initial state; a safe abort means the compensator refused an operation and restored the initial state without completing the workload. Errors and state mismatches are separate failure outcomes.
Final-checkpoint outcomes for Astra (report, Table 1). Runs use round 59, except Dafny with counterexamples alone, which terminates after one checkpoint. No final-checkpoint state mismatches occurred.
With verification and opportunities, completed-and-restored tasks increased from 1 to 13 out of 31. Across all 60 evaluated checkpoints, that variant had no observed errors or state mismatches in 1,860 task evaluations. Unverified counterexample-only synthesis had 43 errors and one mismatch over the same number of evaluations; unverified synthesis with opportunities had one error and four mismatches. These are repeated evaluations of the same tasks, not independent safety trials.
Coverage across models (report, Table 2). Each run uses its latest evaluated checkpoint, capped at round 59—not a matched synthesis budget. Python with counterexamples has 2, 0, and 1 combined errors or mismatches for Luna, Sol, and Astra; all other non-passing tasks safely abort.
Across models of different strengths, we found that the story of using LLMs to synthesize compensators was largely the same. Current models can produce useful compensators but remain buggy after many rounds of counterexample-driven feedback. Verification alone produces overly conservative compensators; opportunities recover useful behavior while retaining the verified write-set properties. These properties do not prove that rollback restores the correct values, and zero observed failures on this benchmark is not a guarantee of functional correctness. The experiments also assume sequential execution with no concurrent writers and no failures during rollback.
Conclusion and Future Work
We think this project demonstrates the feasibility of the idea, but there’s a lot of work left to do. We’d like to support more of the AWS API, ideally by making the system more general rather than by doing custom per-API work. There’s substantial work to do on making our harness scale better (currently it runs a single agent at a time). The guarantees provided by verification can be expanded and strengthened. There’s more work to build on from the databases community: we should support failures during rollback and in restricted cases support concurrent writers.
Overall, we think this work is an interesting demonstration of the value of combining agentic AI and formal methods. If you found this post interesting, check out the other posts on our blog! We have several published projects in the AI/formal methods space, with more to come.
References
- Database deletion incident. The Guardian (2026).
- Production database destroyed by
terraform destroy. Alexey Grigorev (2026). - OpenAI admits GPT-5.6 occasionally deletes files. The Register (2026).
- Zhong et al. Don’t Let AI Agents YOLO Your Files: Information and Control in Agent-Native Filesystems. SOSP (2026).
- Wan Lim and Will Zhang. Stealing 50 Years of Database Ideas for AI Agents (2026).
- Solar-Lezama et al. Combinatorial sketching for finite programs. ASPLOS (2006).