acceptodds
Under review as a conference paper at ICLR 2027

Inspect or Roll Back? Asymmetric Diagnostics for Checkpointed Recovery

Abstract

When a stateful workflow fails, recent checkpoints may already contain the mistake. A controller can inspect an earlier prefix or discard it and repeat the remaining work. We study how the two kinds of inspection error should affect this choice: falsely trusting a bad prefix risks an incorrect commit, whereas falsely rejecting a good prefix wastes computation. An ordered recovery model separates these consequences and supports inexpensive asymmetric diagnostics. A three-cost representation accounts exactly for mistaken execution paths within a restricted policy class; we extend it to failure penalties and persistent hidden error modes. Experiments compare calibrated unit-test services, shallow lookahead, an edge-cutting baseline, and broader-history policies. In an executed multi-file code-edit workflow, asymmetric tests reduce the one-step controller's checking and replay work by 18%; two-step lookahead matches full compilation, and repairing the test oracle saves substantially more. Risk-matched comparisons and measured planning costs identify full compilation as a conditional refinement for costly, reused workflows. The main practical lesson is to improve and calibrate the diagnostic before using deeper recovery planning.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
checkpoint recovery, sequential diagnosis, asymmetric testing, decision making, stateful agents

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_jz2xOpenReview ↗
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
AuthorsOpenReview ↗

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.

Compared withMedianMeanMaxShare above 1%Share above 5%
One-step1.844.6333.5161.6%29.6%
Depth 20.220.938.4830.3%2.0%
Depth 3 (n ≤ 16)0.000.144.105.2%0%

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.

AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_Kn5dOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This manuscript studies checkpoint recovery with imperfect diagnostics. It distinguishes the consequences of falsely accepting a faulty state from those of unnecessarily rejecting a valid state and introduces a three-cost representation for optimization within a restricted class of ordered policies. It also examines calibration, correlated errors, and planning overhead through controlled experiments and a code-editing task.

Critical strengths
  1. The three-cost representation enables exact optimization within the specified ordered policy class, supported by statewise safety guarantees and an additive approximation bound.

  2. The evaluation compares diagnostic design and planning depth with attention to risk and overhead, showing that improving diagnostic quality can be more beneficial than deeper planning.

Critical weaknesses
  1. The empirical evidence remains narrow. The synthetic experiments follow a specified channel model, while the code experiment uses an authored numerical pipeline with a controlled mutation family. These experiments validate the proposed mechanism but provide limited evidence that the practical benefits extend to more varied workflows and diagnostic errors. The authors acknowledge this limitation; additional task and fault diversity would nevertheless strengthen the main empirical contribution.

  2. The effect of the binary diagnostic interface is not quantified. As noted in Appendix A.3, fixed-batch tests produce failure counts that can contain information beyond the binary report. Both the compiler and the broader-history reference discard this information. A shallow baseline using the full count would help assess the practical cost of this restriction.

  3. The technical contribution is relatively limited. While the three-cost representation provides a useful structural result, it relies on established sequential-testing and dynamic-programming techniques and is restricted to a specific class of ordered policies. Its significance is further weakened by the limited additional improvements of full compilation over simpler planning strategies.

Questions for authors
  1. Can the diagnostic-design gains be demonstrated on additional workflows and fault types, particularly in cases where improving the underlying checker is difficult?

  2. How does a shallow policy using the full failure count compare with the binary-report policies in the code experiment?

  3. In the code experiment, how much of the approximately 18% savings remain after matching the actual model risk of symmetric and asymmetric policies?

  4. Could the related-work discussion clarify the relationship to recent diagnostic and rollback methods such as GA-Rollback [1]? A direct comparison would require compatible execution and information assumptions.

[1] Generator-Assistant Stepwise Rollback Framework for Large Language Model Agent. EMNLP, 2025.

2 comments
AuthorsOpenReview ↗

Response to Reviewer Kn5d (1/2)

Response to Reviewer Kn5d (1/2): risk matching (Q3) and failure counts (Q2, W2)

Thank you for the precise summary, and for recognizing the exactness and statewise safety of the three-cost representation.

Q3: how much of the 18% remains at matched risk. At matched marginal risk, the probability of an incorrect commit under the prior, the saving is 15.3%. You are right that the 17.98% compares one-step policies at the same cap rather than at equal risk. Computed exactly from the test-input frequencies (Appendix E), the asymmetric policy spends about twice the risk: its marginal risk is 4.11·10⁻⁴ against 1.97·10⁻⁴, and its largest statewise risk is 3.78·10⁻³ against 2.00·10⁻³. We therefore re-planned one-step lookahead at 20 caps from 0.03 to 10⁻⁴, and a linear program chose mixture weights over these policies and restart that minimize the exact expected cost under each risk constraint. We executed the resulting mixtures on the same 800 paired setups (Section 7; Appendix G.1, Table 5).

Asymmetric one-step, matched onTestsWrong commits (of 800)Saving against symmetric (1504.36)
Same cap (as in the paper)1233.911270.45 [248.07, 292.83], 18.0%
Marginal risk1274.430229.93 [207.25, 252.61], 15.3%
Largest statewise risk1256.970247.39 [223.56, 271.22], 16.4%
Every state at or below the symmetric policy's risk1454.94049.42 [37.41, 61.43], 3.3%

The last row over-matches, because the qualifying policy's marginal risk is 3.87·10⁻⁶, about 50 times below the symmetric policy's. Loosening the symmetric policy to the asymmetric policy's risk instead leaves 15.7%. Because 800 trials cannot resolve risks near 10⁻⁴, we match risks computed in the model, which is exact for this family of test inputs. In the grid, at the three marginal-risk targets of Figure 3, symmetric one-step lookahead costs 48.24, 47.13 and 45.59 in exact expectation, against 44.67, 43.59 and 42.68 for asymmetric one-step. The asymmetric menu (the symmetric test plus asymmetric ones) therefore accounts for 77–81% of the cost gap between symmetric one-step lookahead and full compilation at matched risk, compared with 74% at the same cap. The abstract and Sections 1, 6 and 7 now report the matched-risk figures.

Q2 and W2: using the full failure count. Counts help modestly. In the code study, routing on counts saves 1.8% and curtailed batches save 4.3%, against 15–18% for the asymmetric menu (Appendix G.3). In the grid, binary reports lose nothing, because a test's final score is a sufficient statistic (Proposition 5).

  • A curtailed batch stops as soon as its accept or reject outcome is certain, so its reports and error rates are unchanged. Curtailment lowers asymmetric one-step from 1233.91 to 1181.30 tests, a saving of 52.61 [44.60, 60.61], and symmetric one-step from 1504.36 to 1444.25. With both curtailed, the asymmetric policy still saves 262.95 [242.25, 283.65] tests, or 18.2%, and Appendix G.3 recommends curtailment.
  • A count-routed one-step policy uses each count's binomial likelihood to choose the next boundary and test, or to stop. Because its intervals and final rollback still follow the calibrated reports, Theorem 1 still caps statewise risk at 1%. It saves 22.12 [15.02, 29.22] tests over the binary-report policy with one wrong commit, and in 100,000 simulated recoveries it uses 1228.13 tests against 1248.81 (standard error of the difference 0.36). With the symmetric menu, counts changed no decision in the 800 executed setups.
  • A controller that also used counts to update its interval would fall outside Theorem 1. We did not evaluate one, so these results measure only two uses of counts.

One correction: the broader-history reference was run only on the grid (Section 6.1 and Appendix D.3), and we fixed the sentence in Appendix A.3 that suggested otherwise.

AuthorsOpenReview ↗

Response to Reviewer Kn5d (2/2)

Response to Reviewer Kn5d (2/2): breadth of evidence (W1, Q1), technical contribution (W3) and GA-Rollback (Q4)

W1 and Q1: more workflows and fault types. We agree that the evidence was narrow, and the gains carry over only in part: asymmetric sampled tests save nothing on the real library (general response, point 3), and we could not add an agent workflow (Limitations, Section 8). In the real library (Appendix G.10), detection depends on the fault, and 144 faults fail exactly one of their module's tests. With failure rates estimated per stage from 6–40 faults, the policies exceed the cap δ on held-out faults in some of the 132 settings in 10 of 11 random splits, and in up to 48 of them in one split. Certifying the per-test cap of 0.0033 from labeled faults alone needs at least 898 faults per stage. In the code study, across the 10 re-calibrated input banks where every boundary has a safe test, one meeting the menu's targets (Appendix G.5), the asymmetric saving in exact expected cost is 0–20.0% at the same cap and 0–18.8% at matched marginal risk. It is zero only where detection is easy and correct code never fails, and in the other 5 banks both policies restart. Across replay prices from 0.25 to 16 times the paper's (Appendix G.4), the saving peaks at intermediate ratios of replay to check price.

Where the checker is hard to improve, the asymmetric menu still helps. The grid's raw checker has fixed noise and can only be queried more, yet the menu lowers one-step cost there by 6.4–7.5% at matched marginal risk in model expectation (our arithmetic from Section 6). In the code study, we also kept the exact-match checker and doubled or quadrupled the rows on which correct code fails. Wherever a safe test exists, the asymmetric saving is then 11.96–19.98% at the same cap and 9.17–18.79% at matched risk, and elsewhere both policies restart. This is still one mutation family. We have not evaluated a language-model judge as the checker; its repeated judgments of one state would be correlated, a case that Proposition 2 bounds.

W3: limited technical contribution. We agree that the tools are classical; the revised Sections 1 and 8 credit them and state our claims more modestly. First, Theorem 1 shows that only the first false-clean report uses up the safety budget, so if replay adds no errors, tests can trade a higher false-bad rate for lower cost without a separate cap. The new Proposition 12 (Appendix G.9) shows why this trade is cheap: below a cap of 1/4, a test that reports bad after one net bad answer never needs more net clean answers than the symmetric test, and under mild conditions it uses fewer raw queries on both kinds of prefix. Second, after a mistaken report, the true state lies outside every interval still considered. Section 4 shows that two costs, one for each side of the interval, cover these cases, so dynamic programming with dominance pruning is exact over the class (Theorem 3), also with failure penalties and persistent modes (Corollary 4). Third, the experiments separate the two levers. At the same cap, the menu lowers grid cost from 44.80 to 41.88, and full compilation lowers it further to 40.86; in the code study, the menu saves 270.45 tests and full compilation 1.81 more. At 16 times the code study's replay price, both levers are small: the menu saves 2.17% at the same cap and full compilation 2.31% over one-step lookahead (Appendix G.4).

The ordered restriction is real, but it is also what keeps false-bad errors safe. Under the 1% cap, the broader-history reference of Section 6.1, which may end at any checkpoint, gains 0.64% on average with the same menu and 1.67% with a wider menu (7.16% in the best cell). Once each state's risk is matched, it gains 0.05–0.06% (Appendix D.3). These gains only lower-bound the loss from our restrictions, which can be arbitrarily large in the worst case (Appendix D.5).

Q4: GA-Rollback. Section 8 now discusses GA-Rollback and BacktrackAgent. In GA-Rollback (Li et al., EMNLP 2025), an assistant model flags an erroneous step, the environment is reset, and the generator regenerates from that step; the paper reports end-task success. Its critic names a step, whereas our tests ask whether the first fault lies at or before a given boundary. It neither measures nor caps the critic's false-alarm and miss rates, nor separates unsafe commits from wasted replay. Such a critic could serve as a diagnostic in our sense if it were asked about a prefix and calibrated in both directions on labeled trajectories, with two caveats: asking again about an unchanged prefix gives no new evidence, and regeneration after a false alarm can introduce new errors (Appendix G.7). BacktrackAgent (Wu et al., EMNLP 2025) reports its detector's precision and recall after the fact but does not price the two error types separately or cap misses. As you note, a direct comparison would need matching assumptions, so we discuss these methods without benchmarking them.

Reviewer_JXfpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

In a multi-step workflow, restarting from scratch after an error wastes valid work, while selective recovery can hide real bugs. The paper observes that false-clean and false-bad results have asymmetric costs. It therefore uses asymmetric sequential testing to reduce costs while controlling the risk of unsafe recovery. It also formulates recovery planning as a three-cost dynamic programming problem that accounts for checker errors. The evaluation demonstrates cost savings, although most of the gains come from the checker-side innovation.

Critical strengths
  • Insightful distinction between false-clean and false-bad results.
  • Rigorous formulation of the planning problem.
Critical weaknesses
  • The recovery model assumes trusted sources, and the cost assignments are not well justified.
  • The main planning algorithm offers very limited gains over simpler methods.
Questions for authors
  1. The paper acknowledges the need for lifetime risk allocation but does not evaluate it in realistic long-running workflows. How does the risk of unsafe recovery accumulate over long trajectories? For example, for a coding agent with potentially thousands of steps and multiple recovery attempts, how reliable is the final outcome? Are real-world systems willing to accept this risk of incorrect results?

  2. Most of the gains appear to come from the asymmetric checker; the full compiler improves over asymmetric one-step planning by only 0.15% (1232.10 vs. 1233.91 unit-test executions). Given this, is the paper’s substantial effort to optimize the planner using dynamic programming justified?

  3. Why is replay cost modeled primarily as 256 regression-test executions per regenerated module, rather than the actual cost of regenerating and re-executing the workflow? In practice, how would regeneration from a trusted source work for coding tasks? LLMs are not guaranteed to produce correct results. Would accounting for this uncertainty change the paper’s trade-offs?

  4. The paper relies heavily on abstract terminology and formulas without providing enough examples to explain the core ideas. This makes it difficult to follow, particularly the problem formulation and evaluation.

  5. The evaluation setting is oversimplified. The paper needs to demonstrate gains in real workflows, such as agentic coding, rather than relying on small, manually constructed modules with injected faults.

2 comments
AuthorsOpenReview ↗

Response to Reviewer JXfp (1/2)

Response to Reviewer JXfp (1/2): presentation (Q4) and costs (Q3, W1)

Thank you for the detailed questions, and for finding the false-clean and false-bad distinction insightful.

Q4: abstract terminology and too few examples. We agree. Point 1 of the general response lists the presentation changes. The revision is built around one running example, the code study's seven-stage pipeline with a sign error in the fee stage. The fee stage is stage 4, so checkpoints 0–3 are safe (Figure 1). A bad report at boundary 3, a test of the prefix through stage 3, is a false-bad. The controller then considers only checkpoints 0–2, which are all safe, so the error costs extra replay but cannot cause a wrong commit. A clean report at boundary 5 is a false-clean, after which every checkpoint still considered is unsafe. Theorem 1 states this in general.

Section 3 now shows numerically why asymmetric tests are cheaper. A (−l, +u) test repeats a noisy raw check and keeps a score, adding 1 for each bad answer and subtracting 1 for each clean one; it reports clean when the score reaches −l and bad when it reaches +u. With the grid's noisier raw checker, which errs with probability η = 0.25, and a per-test cap of 0.002 on the false-clean rate:

Test (−l, +u)False-cleanFalse-badRaw queries, bad prefixRaw queries, clean prefix
Symmetric (−6, +6)0.00140.001411.9711.97
Asymmetric (−6, +1)0.00090.3331.997.34

The asymmetric test meets the same cap and is cheaper on both kinds of prefix, at the price of rejecting a clean prefix a third of the time. The new Proposition 12 (Appendix G.9) proves this pattern under conditions that hold at both grid noise levels. Tables 1 and 2 count checking and replay together, so the savings are net of the extra replay. At the same cap, the grid cost falls from 44.80 to 41.88, and the code study's from 1504.36 to 1233.91 unit tests. At matched marginal risk, the probability of an incorrect commit under the prior, the code-study saving is 15.3%, and it is 3.3% if every state's risk must stay at or below the symmetric policy's.

Figure 1 also shows the three costs that the planner of Section 4 tracks. Cost A covers a fault inside the interval of states still considered. After the false-clean report at boundary 5, the fault lies earlier than all of these states (cost B), and after the false-bad report at boundary 3, it lies later than all of them (cost C). A planner that ignores B and C, our "nominal" ablation, uses 1294.04 unit tests, against 1233.91 for one-step lookahead that accounts for report errors (Table 2).

Q3 and W1: why replay is priced as 256 tests. In our setup, 256 tests is the actual cost of replaying one module. Replay restores the module's source file and cached assumptions and then runs its 128 tolerance-based unit tests twice, so a full restart costs 1792 tests. The two passes are a fixed price of our setup, not a requirement of the method. Checking is counted in the same unit, because a check of the prefix through stage a runs r unit tests on each module it includes. In the grid, costs are normalized so that a raw query costs 1 and restart 101. The default failure penalty λ = 0 means minimizing resources under the 1% cap, not that failures are free, and Section 6 varies λ up to 10⁵. Table 2 now splits the cost: symmetric one-step spends 395.88 tests on checking and 1108.48 on replay, and asymmetric one-step 348.47 and 885.44. In a language-model workflow, the replay cost would be the measured cost of regenerating the discarded steps. To cover a range of such costs, we re-planned every policy with the replay price scaled (Appendix G.4). The asymmetric saving over symmetric one-step, in exact expected cost, is:

Replay price×0.25×1×4×16
Same cap5.10%17.33%14.81%2.17%
Matched marginal risk0.00%14.43%13.39%4.21%

The executed savings at ×1 are 18.0% and 15.3%. When replay is cheap, little inspection pays, and when it is very expensive, the extra replay caused by false-bad reports is costly. We have not measured this ratio for language-model workflows. In a coding task, regeneration is trusted when it re-executes deterministic tool or build steps from the restored state, or when it rewrites files from a reference source. Our code study does the latter: restoration rewrites each discarded module from its correct source and reruns its tests (Section 7). Re-prompting a language model is not a trusted source, and part 2/2 answers, under W1, how this uncertainty changes the trade-offs.

AuthorsOpenReview ↗

Response to Reviewer JXfp (2/2)

Response to Reviewer JXfp (2/2): trusted regeneration (W1), the planner (W2, Q2), lifetime risk (Q1) and realism (Q5)

W1: trusted regeneration. Part 1/2 explains the cost assignments under Q3. We agree that trusted regeneration is the strongest assumption, and the new Proposition 11 (Appendix G.7) shows that it matters. Restoring a checkpoint can be made reliable with snapshots, but regenerating the discarded steps with a language model cannot, since it may err again. Detected regeneration failures only raise replay cost, and silent failures at a constant rate add at most that rate to each state's risk. Silent failures that grow with the number of regenerated stages change the trade-off, because a false-bad report then leads to a deeper and riskier rollback. Suppose the silent-failure probability ρ_k after restoring checkpoint k is independent of the tests given the state and does not increase with k. Then a state's risk is at most ρ_0 plus (1 − ρ_0) times its diagnostic risk, so a total cap δ needs ρ_0 ≤ δ. In the code study with a silent-failure probability of 10⁻³ per stage, the asymmetric policy's largest risk over states is 1.07%, slightly above a 1% total cap. Re-planned with a failure penalty, it falls to 0.98% at almost unchanged cost (1249.48 tests), still above the symmetric policy's 0.90%. At 10⁻², no policy, restart included, can meet a 1% cap. Section 3 now says that false-bad errors need no separate cap only under trusted regeneration, which Section 2 lists as an assumption.

W2 and Q2: is the planner justified? The effort is justified only for an exact reference; we do not propose the compiler as a default method. Your number is correct, and the paper reaches the same conclusion: full compilation uses 1232.10 unit tests against 1233.91 for one-step lookahead, and the paired interval [−4.59, 8.21] includes zero (Section 7). The paper recommends improving the checker first, then trying shallow lookahead, and compiling only when the savings repay the overhead. Redesigning the test saves 18% at the same cap (15.3% at matched marginal risk), and repairing the checker lowers the cost to 723.05 tests, or 802.03 at a tighter 10⁻³ cap. We keep the compiler for two reasons. First, it makes "little remains for deeper ordered planning" a measured statement: in the grid, where it groups costs into buckets, the compiled policy is within 0.24 cost units on average (0.47 at most) of a lower bound on the best policy in the class, while it saves 0.95 units over one-step lookahead (Section 6.2). Second, it underlies the extensions to failure penalties and persistent hidden modes (Section 6 and Corollary 4).

Q1: risk over long trajectories. Within one recovery, risk does not grow with the number of checkpoints if tests are fresh and regeneration is trusted: only false-clean reports count, and each of the at most D tests is capped at δ/D (Theorem 1). Across recoveries risk adds up, and Section 3 now allocates it. What grows with trajectory length is the number of recoveries, the calibration effort and, if regeneration can fail silently, regeneration risk. Our bounds do not cover faults that never trigger a recovery. If recovery i uses fresh tests and cap δ_i, the probability that any recovery keeps a faulty prefix is at most the sum of the δ_i. Choosing δ_i = 6Δ/(π²i²) keeps this sum at a lifetime budget Δ, and a shared calibration adds its failure probability ξ once. Tightening is cheap because the false-clean rate falls geometrically in l. At η = 0.25, tightening δ_i from 10⁻² to 10⁻⁵ (1% lifetime risk over 1,000 recoveries) raises l from 6 to 12 and the mean raw queries on a clean prefix from 7.34 to 15.33, while a faulty prefix still needs about 2. This assumes known noise; if no calibrated test certifies the smaller cap, the policy falls back to restart (Corollary 6). Blind spots shared by all checks (Proposition 2) do not shrink with δ_i. With thousands of checkpoints, full compilation does not scale (planning for 128 checkpoints with at most five tests takes over 90 s), so one-step or depth-2 lookahead is the practical choice. Whether a risk is acceptable depends on the application, and our framework makes it explicit through δ and λ. Resuming without inspection leaves it unquantified: retrying the last action committed an incorrect result in 384 of 800 tasks (Table 2).

Q5: realistic workflows. We agree, but we could not add agentic coding (Limitations, Section 8). We instead added a real-library study (general response, point 3; Section 7 and Appendix G.10). Its costs are exact expectations over the recorded test outcomes, with an assumed replay price of 32–2048 test runs per module plus one pass over its tests, and no recovery is executed. The gains are mixed: asymmetric sampled tests do not pay on this deterministic suite, while the planner with unlimited checks matches or slightly beats the best fixed procedure chosen in hindsight.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: what changed in the revised PDF

General response: what changed in the revised PDF

We thank the reviewers for their careful reviews. In the revised PDF, new analyses are in Appendix G, and the main text still ends on page 10. All section, table and appendix numbers in our replies refer to it.

1. Presentation (JXfp Q4; presentation scores of all three reviews). We rewrote the formulation around one running example and define key terms at first use.

  • Section 1 defines a service, a test procedure that returns one clean or bad report, and the compiler, our exact planner. It also explains asymmetric services, which accept more false-bad reports to save queries, and marginal risk, the probability of an incorrect commit under the prior.
  • Section 2 defines the symbols of the objective next to Eq. (3), states the assumptions, and introduces the running example, a sign error in stage 4 of the code study's seven-stage pipeline.
  • Figure 1, redrawn on this example, shows why a false-bad report only costs extra replay while a false-clean report makes every remaining restore unsafe. It also marks the three costs that the planner of Section 4 tracks, and Section 3 adds a numeric example of a cheaper asymmetric test.
  • We removed the main double meanings of symbols. Table 4 (Appendix A) lists the notation, and the new Table 3 summarizes the main experimental setups.
  • Tables 1–3 and Figures 1–3 have self-contained captions, and Section 6 explains step by step how we compare policies at equal risk.

2. The exact planner adds little over shallow lookahead (jz2x W1 and Q1, Kn5d W3, JXfp W2 and Q2). We agree, and the paper reports this as a main finding. We use the compiler as an exact reference for the ordered class and recommend shallow lookahead by default. In a search over 297 synthetic instances fixed in advance (Appendix G.6), planning with the compiler, which we call full compilation, is up to 33.5% cheaper than one-step lookahead when the first few checkpoints save most of the replay cost. Its median advantage over depth-2 lookahead, however, is 0.22%, and it exceeds 5% in only 6 instances. In both main studies, accounting for report errors at all matters more than planning deeper: the "nominal" planner, which treats every report as correct, costs about 5% more than one-step lookahead (43.89 against 41.88 in Table 1, and 1294.04 against 1233.91 tests in Table 2).

3. Real workloads (jz2x W2, Kn5d W1 and Q1, JXfp Q5). We added a study on the Python library boltons 25.0.0 (Section 7 and Appendix G.10). Its eight modules serve as stages and its 326 tests as checks, and the faults are 407 seeded mutants, small automatic code changes that each fail at least one test of their module. Costs are exact expectations over the recorded test outcomes, with an assumed replay price.

  • Detection varies widely: a fault fails 0.7–100% of its module's tests.
  • Calibration decides safety. Sampled checks, which run a random draw of the prefix's tests, were calibrated with one miss rate pooled over all faults, and the risk of an incorrect commit reached 0.99 for some fault location on held-out faults, against a cap of 0.01. Bounds valid for every fault keep this risk within the cap, but sampled checks built on them cost more than running all of the prefix's tests, so asymmetric sampled tests bring no saving on this deterministic suite.
  • When each check runs all of the prefix's tests and the number of checks is unlimited, the planner matches or slightly beats the best of five fixed procedures chosen in hindsight for each setting (median saving 0.1–6.7%). The best single procedure, used in every setting, costs 63% more than the planner in one of them.

We could not add an agent workload (Limitations, Section 8).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.