- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper targets the problem of finding a safe recovery point for stateful agentic workflows that failed. The goal is to find the lowest cost point to restart from resulting in fewer tests and faster replay while keeping the risk of restoring a bad checkpoint below a threshold. The problem is hard because checkpoints may already contain mistakes and testing is noisy, which runs the risk of restoring a clean checkpoint that is too far back in the past or a corrupted one that passes the tests. The authors build a compiler that plans testing across the checkpoints, accounting for the fact that answers may be wrong, and then tracking the cost of each outcome. This approach builds on the key idea that tests should be asymmetric: restoring from an unsafe checkpoint is worse than restoring from an older checkpoint results, which only causes wasted work without affecting safety. The authors implement their approach and show it on a synthetic grid and a python pipeline.
Critical strengths
(S1) The paper makes an interesting and useful observation that practitioners and researchers often gloss over.
(S2) The cost representation and asymmetry make a lot of sense.
(S3) The paper offers a practical path: calibrate checking, try lookahead, and use full compilation when the benefits outweigh the overheads.
Critical weaknesses
(W1) Unless I misunderstood something, the sophisticated machinery (the compiler) barely helps with low single-digit gain in the best case whereas the improving the tests or leveraging asymmetry yield much larger gains. For this part of the contribution to be validated, it would need to show meaningful gains in at least one scenario.
(W2) The paper is (at least partially) motivated with LLM agents, yet there are no agents in the evaluation, which feels a little odd. Furthermore, the evaluation is mostly synthetic and intentionally constructed to illustrate the proposed solution. There is nothing fundamentally wrong with the experiments and, as noted by the authors, the problem exists whether the workloads are generated or real, but it would help support the case made in the introduction to include more real-world stateful workflows or even agents.
(W3) The novelty seems narrowed than the paper claims given the breadth of related work on this problem. I am not an expert in statistics or DevOps / continuous integration, but this problem has been studied by Google and other cloud providers and probabilistic bisection is known technique. In HPC, there is quite a bit of work on silent errors and how they related to checkpointing that the authors could study to refine the related work and novelty claims.
(Minor) A few assumptions about the design seem non-trivial to obtain in practice. For example, how do you precisely know the failure rate of each test? Or how realistic is it to assume that a single fault hits the workflow and that everything before that is clean?
(Minor) I am not sure ICLR is the best fit for this work as it does not have a learning contribution and the evaluated system has no agents.
Questions for authors
(Q1) Can you show a scenario where the compiler approach achieves meaningful gains?
(Q2) Please explain how to determine the failure rate of tests?
(Q3) How do you deal with workflows containing multiple faults?
Please also see critical weaknesses above.
4 comments
Response to Reviewer jz2x (2/2)
Response to Reviewer jz2x (2/2): realism (W2), related work (W3), failure rates (Q2), multiple faults (Q3) and fit
W2: no agents, and a constructed evaluation. We agree; the Limitations paragraph of Section 8 now states this, and we added a real-library study (general response, point 3). The main studies are controlled because measuring both error directions needs trusted labels for every prefix, and we agree that the code study was built so that both occur. When we vary the code study's bank of test inputs (Appendix G.5), the asymmetric saving is 0–20.0% at the same cap and 0–18.8% at matched marginal risk; where detection is too weak, both policies restart. Agents would be harder in two ways: labeled faulty prefixes must represent the agent's own faults, and replay by a language model can add new errors (Appendix G.7). Section 1 now qualifies our claim that the problem is independent of how actions were generated.
W3: novelty and related work. Section 8 now covers this work, and our novelty claim is narrower. Google's flake-aware culprit finder (Henderson et al., ICST 2023) runs Bayesian noisy bisection over suspect commits and treats passing runs as reliable. In our terms, it allows only false-bad errors (α = 0), and then every recovery in our class is safe if replay adds no errors (Theorem 1). Ziftci and Reardon (ICSE-SEIP 2017) and Najafi et al. (ESEC/FSE 2019) also find culprits, and Gandalf (Li et al., NSDI 2020) decides whether to stop a rollout, while we choose which existing, possibly corrupted state to restore. We now cite probabilistic bisection (Horstein 1963; Jedynak et al. 2012; Waeber et al. 2013) and the "half-lie" search of Rivest et al. (JCSS 1980), and we do not claim asymmetric noisy search as new. In high-performance computing, Aupy et al. (PRDC 2013) and Benoit et al. (2017) assume correct checkpoint verification, while Cavelan et al. (ICPP 2015) and Bautista-Gomez et al. (JPDC 2016) place imperfect verifications periodically. In our reading, their false alarms cause re-execution in every error-free period, whereas ours cost extra replay once per recovery. We also corrected our phrase "separate systems concerns", which understated the overlap. What remains new is the restore decision under a risk cap for every fault location: we need a safe checkpoint with little extra replay, not the culprit (Theorem 7). Theorem 1 shows that only false-clean errors use up that cap, and Theorem 3 gives exact planning in the ordered class when tests err in both directions. In our code study, bisection and a newest-to-oldest scan with the calibrated symmetric test even cost more than restart (3003.78 and 3867.30 unit tests against 1792; Appendix G.2).
Q2: how to determine failure rates. We estimate them on prefixes with known labels, and only the false-clean rate needs a guaranteed bound (Section 3 and Appendix A.4). We run the raw check many times on prefixes known to be faulty, count how often it wrongly passes, and take exact binomial (Clopper–Pearson) upper bounds that hold jointly for all tests. If these bounds hold, every selected policy keeps the cap for every fault location. They fail with a probability ξ that we choose, which adds at most ξ to the risk (Corollary 6). If replay adds no errors, false-bad rates affect only cost, so estimates suffice; if replay can fail silently, deeper rollbacks carry risk of their own (Appendix G.7). The code study's calibration, which Table 2 excludes, uses 336,000 unit tests plus 112,000 held-out ones. At 558.09 tests saved per recovery relative to restart, it is repaid after about 600 recoveries, or about 800 with the held-out checks (our arithmetic from Table 2). The guarantee carries over only if the calibration faults represent the deployed faults, and a blind spot shared by all checks needs a separate bound (Proposition 2). In the real library, certifying the cap needs either a bound valid for every fault or about 900 labeled faults per stage.
Q3: multiple faults. The model does not assume a single fault. It tracks J, the first fault that persists in the saved state; a safe rollback goes back before J, so it also discards any later fault (Section 2). Two points need care (Appendix G.8). First, faults can mask each other, so safety needs false-clean bounds that hold for every possible combination of faults, or rates weighted by deployment frequencies; given such bounds, Theorem 1 holds. Second, exact cost accounting then needs a known finite model of fault combinations (Corollary 4), and otherwise the planner's cost is an approximation. In the code study, a second fault can only make detection easier, because each module is tested on its own sampled input.
ICLR fit. We agree that the contribution is decision-theoretic, with no new training method. It concerns sequential decisions under partial observability with diagnostics calibrated from labeled data, which we think fits well within ICLR's scope.
Thank you for the thorough and candid response. The narrower novelty claim and the answers on failure rates and multiple faults address those concerns. However, my main concern remains: by your own account, the compiler pays off mainly on synthetic early-cliff instances whose prevalence is unknown. I would also recommend including agents in the evaluation. I will keep my score for now.
Response to Reviewer jz2x (follow-up)
Thank you for the careful follow-up and for confirming that the novelty, failure-rate and multiple-fault concerns are resolved.
Compiler gains. We agree that full compilation pays off mainly on early-cliff instances, and we have not measured how common they are. However, our main claim does not depend on the compiler. The claim is that diagnostic design matters more than planning depth. In the code study, asymmetric tests save 18% at the same cap, while full compilation saves only 1.81 of 1233.91 unit tests (Section 7 and Table 2).
We keep the compiler mainly as a measuring tool, because it is exact for our policy class (Theorem 3). Using it, we find that depth-two lookahead recovers most of the gap to the best policy in that class. Full compilation beats depth-two lookahead by more than 5% in only 6 of 297 instances (Appendix G.6, and Proposition 13 in Appendix G.9). Our advice is therefore to improve the checker first, use shallow lookahead next, and compile only when the savings repay the overhead. This advice holds however common early-cliff workflows turn out to be.
Agents. We agree that an agent evaluation would strengthen the paper. We could not add one within the discussion period, and the Limitations paragraph in Section 8 says so. The real-library study (Section 7 and Appendix G.10) is the step toward real workloads that we were able to take, and it shows that on real faults, calibration decides safety. We see an agent evaluation as the most important next step.
Response to Reviewer jz2x (1/2)
Response to Reviewer jz2x (1/2): the compiler's gains (W1, Q1)
Thank you for the careful review, and for finding the observation useful and the cost representation sensible.
W1: the compiler barely helps. You are right that full compilation adds little in our experiments, and the paper reports this as a main finding. With the same asymmetric tests, full compilation lowers the grid cost from 41.88 for one-step lookahead to 40.86 (Table 1). Of the cost reduction from symmetric one-step lookahead to full compilation, asymmetric tests account for 74% at the same 1% risk cap (Table 1) and, in exact model costs, for 77–81% at matched marginal risk (Sections 5 and 6). At a matched marginal risk of 10⁻³, full compilation is 1.59% cheaper than one-step lookahead. In the code study, it saves 1.81 of 1233.91 unit tests, and the paired interval [−4.59, 8.21] includes zero. On a 64-state grid instance, its extra planning time pays off after about 47,000 reuses (Section 6.2).
We keep the compiler because it is exact for our policy class (Theorem 3), and its lower bound turns "shallow lookahead is nearly enough" into a measured statement. In the grid, where it groups costs into buckets, the compiled policy is within 0.24 cost units of that bound on average (0.47 at most), while it saves 0.95 units over one-step lookahead in exact model costs (Section 6.2). The compiler's extension to correlated test errors plays the same role: in 18 small settings, planning as if test errors were independent loses at most 0.04 units (Appendix A.5). Accounting for report errors matters more than depth, and one-step lookahead already does it: on the 64-state instance, full compilation saves 9.39 units over the "nominal" planner, which ignores report errors, and one-step lookahead recovers 8.94 of them (Appendix F.1 and our arithmetic).
Q1: a scenario with meaningful gains. Yes, in synthetic instances and mainly against one-step lookahead, which full compilation can beat by up to 33.51%. No executed workload in the paper shows a comparable gain, and against depth-2 lookahead the gain is at most 8.48%, so looking ahead pays mainly from one step to two.
In a minimal example, a fault at stage 1, a fault at stage 2, and no fault have prior probabilities 0.1, 0.1 and 0.8. Replay costs 100 from checkpoint 0 and nothing from checkpoints 1 and 2. At most two tests are allowed; each costs 1, never calls a faulty prefix clean (α = 0), and calls a clean prefix faulty with probability β = 1/3. One-step lookahead tests checkpoint 1 and stops, and it costs 41 because a false-bad report there forces a restart. The best two-test policy tests checkpoint 2 first and checkpoint 1 only after a bad report. It costs 23.69, which is 42% less, and depth-2 lookahead finds it. The new Proposition 13 (Appendix G.9) generalizes this: even with three states, two tests and α = 0, one-step lookahead can cost arbitrarily many times as much as the best policy in our class.
To see how often this happens, we computed exact model costs for 297 distinct instances fixed in advance (Appendix G.6, Table 8). They vary the number of checkpoints (8 or 16, plus 27 instances with 32), the test budget D (3 or 5), the replay profile (uniform, clustered, or "early-cliff", where the first few checkpoints save most of the replay cost), and three levels each of clean prior, noise and failure penalty. Here the compiler groups the costs that follow a wrong report into buckets of width 2, so it is approximate, and depth-2 or depth-3 lookahead is occasionally cheaper, by at most 0.22%. The table gives full compilation's percentage saving over each controller.
One-step lookahead is myopic on the early-cliff profile, where full compilation is 9.46% cheaper on average. Depth-2 lookahead recovers most of this, leaving an average gap of 1.55%, and full compilation beats depth 2 by more than 5% in only 6 instances, all early-cliff with D = 5. Matching risk for the ten largest gaps barely changes them. We added the early-cliff profile because the minimal example suggested it, and we have not measured how common such workflows are.