Agent checkpoint systems decide what state is recovery-relevant, how to snapshot it, and whether rollback is admissible. None decides which of the safe boundaries they expose are worth materializing. We formulate this as counterfactual checkpoint advantage, the reduction in future recovery cost obtained by checkpointing a candidate rather than skipping it, and measure it by driving a CP branch and a SKIP branch to the same logical failure and recovering both under matched model, tool, verifier, and stopping conditions. On a frozen pilot of 12 SWE-bench Verified tasks and 106 real recovery branches, checkpointing saves 49.4 s per task, and that figure resolves into two regimes two orders of magnitude apart. The first checkpoint returns 100.0 s on 156.5 s of protected work, a conversion of 0.64; a second one step later returns-1.1 s on 41.8 s, a conversion of -0.03. Recovery is a re-derivation rather than a replay, so preserved work is a poor guide to saved work, and the classical elapsed-work rule misprices the second checkpoint by its full nominal cost. We identify where placement can pay, and set the bar a placement policy must clear.
Figures & tables
Contrast
Tasks
CP (s)
SKIP (s)
Marginal value (s)
Conversion
First checkpoint vs. none
10
100.8
200.8
100.0 [72.4, 131.1]
0.64
One additional, one step later
10
100.6
99.5
−1.1 [ −9.5 , 8.4 ]
−0.03
Pooled over both strata
10
100.7
150.2
49.4 [34.1, 65.5]
Table 1: Marginal value of a checkpoint, by what the Skip world falls back to. Each row is a within-cell paired contrast over the 10 tasks whose recovery reached the endpoint verified by the task’s hidden tests. Brackets are 10,000-replicate task-bootstrap 95% intervals; advantage is net of measured creation cost, and conversion is advantage over the nominal work protected.
Proxy
First checkpoint ( n=10 )
Additional ( n=10 )
Drop largest
Tool calls
+0.85 ( p=0.003 )
+0.34
+0.81
Files modified
+0.71 ( p=0.025 )
−0.53
+0.72
Bytes changed
+0.70 ( p=0.030 )
−0.29
+0.83
Agent importance
−0.58 ( p=0.082 )
+0.06
−0.49
Table 2: Spearman correlation between a cheap online proxy and measured advantage, within stratum over verified-endpoint cells; pooling the strata would manufacture a correlation from the split alone. p -values are permutation tests over 20,000 relabelings; the last column drops the largest cell.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 1: Counterfactual labeling. From the previous checkpoint c− and candidate st we run two matched worlds, CP , which materializes st , and SKIP , which does not, to the same future failure, then recover both and measure J(CP) and J(SKIP) . Their difference is the label ACP(st) .
Group
Examples
Execution cost
elapsed seconds; tokens since last checkpoint; tool calls; retries; errors; expensive-tool count
distance from last checkpoint; time since last progress; branch depth; recent error trend
Appendix
Table 3: Proposed online feature families for advantage prediction. Not evaluated in this paper.
Figure 2: Marginal value of a checkpoint by what the Skip world falls back to, over the 10 verified-endpoint tasks, with task-bootstrap 95% intervals. The dashed rule is measured creation cost. These are the first two rows of Table 1 .
Step
Trajectories
Mean (s)
Share
Cumulative
1
12
172.1
73.9%
73.9%
2
12
45.5
19.5%
93.4%
3
12
13.9
6.0%
99.4%
4
3
5.4
0.6%
100%
Appendix
Table 4: Distribution of nominal (pre-failure) work over logical steps, across all 12 frozen trajectories. A checkpoint at candidate step k protects exactly step k ’s work: the Skip world restores at k−1 and re-executes step k before continuing to the same failure. The workload is close to a single expensive step followed by verification.
Restore point
Branches
Cost (s)
Tokens re-executed
Pristine (start over)
24
226.5
640,651
After step 1
45
108.6
162,656
After step 2
29
103.3
154,439
After step 3
8
95.6
118,976
Appendix
Table 5: Mean recovery cost by how much progress the restore point preserved, over all 106 branches. Descriptive only: these are not within-task paired contrasts, and the deepest bucket is drawn from the three four-step tasks alone. The paired contrasts in Table 1 are the controlled version of the same comparison.
Single-checkpoint policy
Verified (s)
All (s)
Checkpoint at first safe boundary
105.9
112.1
Checkpoint at second safe boundary
155.9
175.6
Appendix
Table 6: Retrospective single-checkpoint placement on the 9 three-step tasks (7 of which reached the verified endpoint), under a uniform prior over the two measured failure points. Lower is better. An oracle that picks the better boundary per task coincides with the first-boundary row on 9/9 tasks, so it is not shown separately.
Figure 3: Retrospective one-checkpoint budget, per task, on the 9 three-step tasks. Placing the single checkpoint at the first safe boundary is cheaper on every task. Because the second-boundary policy holds no checkpoint at the step-2 failure, this margin restates the first-checkpoint contrast rather than measuring placement.
Figure 4: Per-task, per-stratum checkpoint advantage ( J(SKIP)−J(CP) ), by repository and stratum. Hollow markers are the two tasks whose nominal trajectory never reached the endpoint verified by the hidden tests; they are excluded from the primary estimate and shown here for completeness. The legend’s “Early” and “Late” are the first-checkpoint and additional-checkpoint contrasts of Table 1 . Additional-checkpoint points sit near zero in every repository (Django mean −7.5 s, scikit-learn +4.2 s, SymPy +5.4 s), and 5 of the 12 are individually positive.
Task
Repository
Verified
Pairs
CP (s)
SKIP (s)
Adv. (s)
django-15731
django/django
yes
5
107.5
115.9
8.3
django-15814
django/django
yes
4
92.1
181.8
89.7
django-16136
django/django
yes
5
88.0
118.1
30.1
django-16315
django/django
yes
4
132.5
214.8
82.3
sklearn-25747
scikit-learn
no
4
148.4
212.1
63.7
sklearn-25931
scikit-learn
yes
4
102.6
146.0
43.5
Appendix
Table 7: Per-task means over the task’s two frozen cells. Advantage is the mean of J(SKIP)−J(CP) across those cells; positive favors checkpointing. “Verified” indicates whether both recovery branches reached the endpoint verified by the hidden tests (identical to the nominal outcome on this workload). “Pairs” counts repeated CP/SKIP measurements and sums to 53 across the table.
Repository
Tasks
CP (s)
SKIP (s)
Advantage (s)
Verified
django/django
4
105.0
157.6
52.6
4/4
scikit-learn/scikit-learn
4
116.8
165.4
48.5
3/4
sympy/sympy
4
94.3
177.1
82.7
3/4
Appendix
Table 8: Per-repository means over all frozen cells, including the two tasks that neither branch solved (4 tasks each). Restricted to verified-endpoint tasks the advantages are 52.6 s, 43.5 s, and 51.2 s respectively; the SymPy figure below is inflated by the unsolved sympy-23950 . Shown directly rather than bootstrapped: three repositories cannot support a repository-level resampling interval.
Figure 5: RippleCP intuition. A large physical state change may have low checkpoint value when it is cheap to reproduce (left), whereas a small semantic decision can have high value when many subsequent actions depend on it (right). RippleCP estimates whether checkpointing the current state avoids enough future recovery cost to justify materializing it.
Coding agents increasingly operate in executable environments where a failed attempt produces actionable feedback rather than merely an incorrect answer. Existing cost-aware systems typically treat such failures as cascade decisions: try a cheap model first, then escalate hard cases to a stronger and more expensive model. In coding, however, execution feedback can also make further cheap-model recovery worthwhile, raising a budgeted deployment question: when should an agent spend more cheap compute, and when should it escalate? We formulate this post-failure decision as recovery routing over heterogeneous actions and train a supervised router from execution rollouts. To make the same router usable under changing budgets, we add a Conformal Risk Control (CRC) layer that selects a deployment-time cost penalty without retraining and provides marginal expected-cost control under exchangeability. Across held-out failures from five coding benchmarks, cheap recovery and escalation exhibit complementary success patterns. The calibrated frontier improves over fixed actions, prompt-only routers, and a binary cascade baseline; in the main GPT-5.4-nano/GPT-5.4 setting, one CRC-calibrated frontier point exceeds always-escalate solve rate while using 35% of its mean recovery cost. Code is available at https://github.com/Qijia-He/agent-budget-control.
Qijia He, Jiayi Cheng, Chenqian Le +8
University of Washington · New York University · ByteDance +1
Autonomous agents act through sandboxed containers and microVMs whose state spans filesystems, processes, and runtime artifacts. Checkpoint and restore (C/R) of this state is needed for fault tolerance, spot execution, RL rollout branching, and safe rollback-yet existing approaches fall into two extremes: application-level recovery preserves chat history but misses OS-side effects, while full per-turn checkpointing is correct but too expensive under dense co-location. The root cause is an agent-OS semantic gap: agent frameworks see tool calls but not their OS effects; the OS sees state changes but lacks turn-level context to judge recovery relevance. This gap hides massive sparsity: over 75% of agent turns produce no recovery-relevant state, so most checkpoints are unnecessary. Crab (Checkpoint-and-Restore for Agent SandBoxes) is a transparent host-side runtime that bridges this gap without modifying agents or C/R backends. An eBPF-based inspector classifies each turn's OS-visible effects to decide checkpoint granularity; a coordinator aligns checkpoints with turn boundaries and overlaps C/R with LLM wait time; and a host-scoped engine schedules checkpoint traffic across co-located sandboxes. On shell-intensive and code-repair workloads, Crab raises recovery correctness from 8% (chat-only) to 100%, cuts checkpoint traffic by up to 87%, and stays within 1.9% of fault-free execution time.
Tool-using AI agents are increasingly deployed across enterprise software systems, yet widely used benchmarks primarily evaluate nominal task completion, conflating baseline planning competence with operational fault recovery. We introduce UndoBench, a benchmark spanning 36 base workflows and 36 fault scenarios across 8 enterprise domains, decoupling task competence from recovery capability via counterfactual paired trials under identical seeds alongside wire-level effect-history and environment-state oracles. On 12 held-out TEST workflows across two open-weight models, two frameworks, and three recovery paradigms (5,760 executions / 2,880 paired trials) in the frozen lost-acknowledgment study, nominal competence reached 83.54% while conditional recovery success rate (CRSR) fell to 46.72%, with naive retry producing duplicate external effects in 53.33% of trials. Extensions to commercial API models reproduced this competence-recovery separation. Evaluations across complementary execution boundaries show that recovery is phase-dependent: before mutation, methods perform similarly without duplicate effects among capable trials; during partial mutation, naive retry, per-call idempotency, and zero-privilege journaling collapse on the evaluated composite workflows; after commit but before acknowledgment, verification and server-side idempotency substantially improve safety. These findings demonstrate that evaluating nominal completion alone masks critical, phase-dependent recovery vulnerabilities in autonomous agents.