Partial Rollback vs Full Replay: Cost Model for Poisoned Agent State

Your agent swarm has been running for hours. A tool call returns malformed data, an LLM hallucination writes garbage to the state store, or a dependency updates and breaks assumptions. The swarm's state is now poisoned. You need to recover. Two options: partial rollback (undo a few steps) or full replay (re-run from a known-good checkpoint). Each has different costs. This article gives you a model to decide which is cheaper.

The Problem: Poisoned State

Agent state is everything the swarm remembers: conversation history, tool outputs, intermediate results, vector embeddings, and the control-plane database. Poisoning happens when any of that becomes inconsistent with reality. The swarm might still run, but its decisions are based on bad data. Left unchecked, it compounds errors.

Recovery means returning the swarm to a state where its future decisions are trustworthy. The two main strategies:

• Partial rollback: Undo specific actions that introduced the poison, then continue from the current state with corrections applied.
• Full replay: Restore a checkpoint from before the poisoning and re-run all subsequent steps.

Both have costs. The right choice depends on the cost model.

Cost Components

Define the following:

• N: number of steps (tool calls, LLM invocations, state mutations) between the last known-good checkpoint and the point where poisoning is detected.
• C_step: average cost of one step, including LLM inference, tool execution, and state writes. In dollars or compute units.
• R_rollback: cost of applying a rollback per step. This includes the cost of identifying which steps to undo, computing inverse operations, and verifying consistency.
• R_replay: cost of re-running one step from a checkpoint. Usually close to C_step, but may be higher if you need to re-fetch external data or re-embed.
• P_rollback: probability that a partial rollback leaves residual poison (i.e., the rollback is incomplete).
• P_replay: probability that a full replay also fails (e.g., the poison is in the checkpoint itself).
• F: cost of failure if recovery doesn't fully work. This includes running the swarm in a degraded state, manual intervention, or a second recovery attempt.

Total expected cost for each strategy:

[ E_{rollback} = N \cdot R_{rollback} + P_{rollback} \cdot F ] [ E_{replay} = N \cdot R_{replay} + P_{replay} \cdot F ]

Choose the strategy with lower expected cost. But the real insight is when R_rollback is much cheaper than R_replay per step, and P_rollback is low, partial rollback wins. When R_rollback is high or P_rollback is high, full replay is safer.

When Partial Rollback Wins

Partial rollback shines when the poisoning is localized and the state is structured enough to undo specific operations. For example, if a single tool call returned a bad value that was stored in a Postgres table, you can simply delete that row and re-run the dependent steps. The cost per step is low: a SQL DELETE and a few recomputations.

Consider a swarm that uses a vector store for embeddings. If one document is embedded with a faulty model version, you only need to re-embed that document, not replay the entire ingestion pipeline. The rollback is to remove the bad embedding and replace it.

Another case: a failed tool call that partially wrote to a database. You can issue compensating transactions to undo the partial write. This is analogous to saga patterns in microservices.

In these cases, R_rollback is a fraction of C_step because you're not re-running LLM calls. You're just fixing data.

When Full Replay Wins

Full replay becomes attractive when the state is deeply intertwined. If the poisoning affects the conversation history or the agent's internal reasoning, undoing specific steps is nearly impossible. You'd have to reconstruct what the agent was thinking at each point, which is essentially replaying anyway.

Also, if the checkpoint is recent and N is small, the cost of replay is low. For example, if you checkpoint every 10 steps, and poison is detected at step 12, replaying 2 steps is trivial.

Full replay also wins when the cost of verification after a partial rollback is high. You might not be able to prove that the rollback removed all traces of poison. In safety-critical swarms, the cost of residual poison (F) is high, so you default to replay.

A Concrete Example

Let's put numbers. Suppose your swarm runs 100 steps between checkpoints. Each step costs $0.10 (LLM + compute). R_rollback per step is $0.02 (just DB operations). R_replay per step is $0.12 (re-running LLM calls, plus some overhead). F (failure cost) is $100 (manual cleanup, downtime).

Assume P_rollback = 0.1 and P_replay = 0.01 (checkpoint is reliable).

Expected costs:

[ E_{rollback} = 100 \cdot 0.02 + 0.1 \cdot 100 = 2 + 10 = 12 ] [ E_{replay} = 100 \cdot 0.12 + 0.01 \cdot 100 = 12 + 1 = 13 ]

Partial rollback is slightly cheaper. But if P_rollback rises to 0.2, E_rollback = 2 + 20 = 22, and replay wins.

The model is sensitive to P_rollback. You need good estimates of that probability. In practice, you can derive it from historical data: how often did a rollback fail to fully recover?

Implementation Notes

To make partial rollback feasible, you need to design your state for undoability. That means:

• Event sourcing: Store every state change as an event. To roll back, you can replay events up to a certain point, or apply inverse events.
• Compensating actions: For each mutation, define an inverse. For example, if you insert a row, the inverse is delete that row.
• Dependency tracking: Know which steps depend on which state. If you roll back a step, you know which subsequent steps need to be recomputed.

Tools like Postgres with logical decoding or event logs in Kafka can help. For vector stores, maintain versioned embeddings.

For full replay, you need reliable checkpoints. Store them in a separate location, ideally immutable. Use a system like ZFS snapshots or a database dump. Checkpoint frequently enough that N stays small.

Case Study: Replacing SaaS with On-Prem

In one of our deployments, we ran a swarm that integrated with a third-party SaaS API. The API returned a malformed JSON that the agent parsed incorrectly, poisoning the state. The swarm had been running for 3 hours, with checkpoints every 15 minutes. That's 12 checkpoints, so N was up to 15 minutes of steps.

We tried partial rollback: we identified the specific tool call that failed and re-ran it with corrected parsing. But the poison had already propagated to a few downstream steps that used the bad data. We had to manually trace dependencies. It took 20 minutes of engineering time, whereas a full replay from the last checkpoint would have taken 5 minutes of compute.

The lesson: even if the per-step rollback cost is lower, the engineering time to identify the rollback scope can dominate. In that case, full replay was actually cheaper.

The Model in Practice

To decide quickly, you can use a heuristic:

• If N is small (< 10), always replay.
• If N is large and the poison is known to be localized, attempt partial rollback.
• If the poison is in the conversation history or reasoning trace, replay.
• If you have no confidence in P_rollback, assume it's high and replay.

But you can do better: instrument your swarm to log steps and dependencies. Then you can compute the cost model on the fly when a poisoning event is detected. Use a simple script that estimates C_step, R_rollback, R_replay from logs, and P_rollback from historical success rates.

Conclusion

Recovering from poisoned agent state is a cost trade-off. Partial rollback can save money when the poison is localized and the state is undoable. Full replay is simpler and more reliable when the state is deeply coupled or checkpoints are frequent.

Build your swarm with both options in mind: design for undoability, but always have a recent checkpoint. Then, when the poison hits, you can compute the expected cost and choose the cheaper path.

Remember: the cost of failure (F) is often the biggest factor. If you can't tolerate residual poison, replay. If you can, roll back.

Now go make your swarm resilient.