acceptodds
Under review as a conference paper at ICLR 2027

Towards a Theoretical Foundation for Tool-Augmented LLM Skill Libraries: The Price of Composition, Propagation, and Safety Under Evolution

Abstract

Skill libraries, natural-language procedures that condition a frozen large language model (LLM), carry tools, and read and write persistent artifacts, are now a de facto standard for building agents. Their reliability, however, still rests on folklore: we cannot yet say how much return an agent loses by composing skills, or how long a safety guarantee survives as the library is edited. We construct a single end-to-end object that answers both: a certificate for a composed agent that bounds the return it loses to composition, measured against the best its frozen model could achieve on a fixed plan, with every term one the designer can drive down or measure and which stays valid over an explicit editing horizon. Two modeling choices make the bound well-posed. First, gaps are measured against the realizable optimum, the best conditioning of the fixed model on the given plan, quarantining base-model capability and plan structure as invariants. Second, a two-layer model separates a within-invocation decision process from a cross-invocation calculus on artifacts. We then assemble the certificate term by term: an exact decomposition names where return is lost; a propagation theorem bounds how per-skill errors compound along the plan, letting each skill rupture (fail discontinuously) with bounded probability rather than assuming Lipschitz behavior, and yielding a convergent/linear/exponential depth trichotomy with matching lower bounds, a checkpoint rule, and black-box-measurable constants; size and learnability bounds control the errors at their source; a two-regime safety result supplies the horizon; and a capability-flow margin demotes tool-combination danger to higher order in the rupture rate. Five algorithms make the certificate constructive. Empirically, a black-box harness recovers the propagation constants on a 332-skill, six-database SKILL.md suite; across five models and six domains the resulting deploy/reject verdict discriminates on both axes; and on real end-to-end LLM pipelines over a nine-model sweep the measured loss stays within the certificate in every case.

Primary area:
learning theory
Keywords:
LLM agents, Skill libraries, Compositional error propagation, Agent certificate, Agent safety

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_63h9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper develops a theoretical framework for composing natural-language skill libraries around a frozen, tool-using LLM. It measures performance against a model-realizable, plan-relative optimum, separates within-invocation decisions from cross-invocation artifact propagation, and proposes a decomposition of performance loss into retrieval, selection, interference, tool, and helper-input terms. Its central propagation result combines a sensitivity-weighted sum over DAG paths with an additive rupture-probability budget, yielding contractive, linear, and amplifying regimes. Additional results concern library size, authoring sample complexity, safety under library edits, and dangerous capability combinations. These components are assembled into an agent certificate, with checkpointing and other proposed algorithms intended to improve it.

Critical strengths
  • The framework distinguishes several sources of failure that require different interventions. Defining a frozen-model, plan-relative target avoids attributing every failure to skill authoring, while the two-layer model distinguishes tool execution from the effects of intermediate artifacts. This is consequential because it gives a potentially useful vocabulary for diagnosing which failures a library edit or checkpoint could actually address (Sections 3-5).
  • The propagation model explicitly accommodates discontinuous failures and heterogeneous dependencies. Per-edge sensitivities and a separate rupture budget are more suitable for schema failures, refusals, and artifact corruption than an exclusively smooth model. Conditional on valid constants, Theorem 1 provides a transparent way to reason about branching pipelines and checkpoint placement. This is the most promising technical contribution.
Critical weaknesses
  • The supplementary proofs do not establish the stated compositional safety guarantee. Theorem 4 still reasons that each ruptured skill adds at most c capabilities, although c is defined as a per-action budget. One skill can add different capabilities across several actions, so the required number of distinct ruptured skills need not be ceil(k/c). In supplementary Theorem 9, p_bar = max_{i != j} P[R_i | R_j] is a pairwise quantity, but the chain-rule proof needs bounds conditional on all preceding ruptures. A concrete counterexample uses independent fair bits X and Y, with R1 = {X = 1}, R2 = {Y = 1}, and R3 = {X = Y}. Every pairwise conditional is 1/2, yet P[R1 ∩ R2 ∩ R3] = 1/4 > (1/2)^3. Proposition 16 adds a Markov restriction, but does not repair the unrestricted Theorem 9. These are failures in the assumptions-to-guarantee connection, consequential to the final safety certificate (supplement pp. 5 and 13).
  • The expanded experiments support rupture modeling more strongly than conservative certification. I credit the Lipschitz-only comparison, 28/30 perturbation-seed agreement, bootstrap analysis, and three public-library evaluations; these checks are present and relevant. The unresolved issue is whether measured constants upper-bound downstream return loss on new executions. Proposition 5 assumes a uniform proxy-to-return Lipschitz bound, while the live calibration uses fitted sensitivities and caps per-stage ratios at 3 (Appendix G.2); flooring them at 1 does not generally make this downward cap conservative. Lemma 2's proof also needs the gap terms to bound the supremum over downstream continuations uniformly. Appendix G.3 reports robust checkpointed cell verdicts in only 13/30 bootstrap intervals, and 11/15 displayed live bounds saturate at 1. Moreover, J_realizable - J(P) ≤ 1 - accuracy is an upper surrogate for the left-hand side, not evidence that the proposed certificate upper-bounds it. Public-library tests broaden the LLM-conditioning channel, with third-party tools unexecuted. Thus, the additions establish useful mechanisms and broader sources, but do not yet show that non-vacuous performance certificates and checkpoint decisions are reliably conservative.
  • Writing quality: frequent defensive statements and excessive emphasis on methodological boundaries. The paper repeatedly reassures the reader that its formulation is non-vacuous, no loss term is omitted, and the results go beyond restating an identity. Examples include “so the split is not vacuous” (Section 3), “not dropped” (Remark 1), and “rather than restating an identity” (Figure 2). Similar assurances that every term is controllable or measurable recur in the abstract and Sections 2, 8, and 11. The cumulative effect is an overly defensive, preemptive-rebuttal style: repeated reassurance draws attention to unresolved qualifications and can create the impression of protesting too much. This weakens the clarity and economy of the exposition. This is the consequence of the author's excessive reliance on GPT writing, and the author should optimize these writing sections to make their paper statements more persuasive, thereby improving the quality of their writing.
Questions for authors
  • Is the capability budget c enforced over an entire skill invocation? How should Theorem 4 change if it is per action? For supplementary Theorem 9, is the intended bound over all rupture histories rather than only pairwise conditionals, or is a verified Markov assumption required? Please reconcile the stated guarantee with the counterexample above.
  • What establishes a uniform proxy-to-return constant in Proposition 5 and the downstream-continuation bound required by Lemma 2? How are fitted slopes, rupture probabilities, and the LCAP = 3 ratio cap converted into conservative held-out bounds with a stated confidence level?
  • Among non-vacuous held-out pipeline bounds, what coverage and useful deploy/reject decisions are obtained when verifier recall and false positives are measured? At comparable verifier cost, how does certificate-guided checkpoint placement compare with uniform placement? The supplied Lipschitz-only comparison already addresses the need for a rupture term.
1 comment
AuthorsOpenReview ↗

Response to comment from reviewer 63h9

Respected reviewer 63h9,

Thank you for such a technically detailed review, each issue you raised was useful for us and the counterexample in particular was very helpful.

(1) About Theorem 4 and the capability budget. You are right, the proof uses "each ruptured skill adds ≤c\leq c capabilities", while cc was defined per action. Revised definition would be cc is the maximum number of undeclared capabilities exercisable by one ruptured invocation, enforced by a per-invocation sandbox. With only a per-action budget cac_a and at most AA actions per invocation, the theorem holds verbatim with c:=min⁡(∣C∣,A⋅ca)c := \min(|C|, A\cdot c_a). The order ⌈k/c⌉\lceil k/c\rceil is then in this effective cc.

(2) About Theorem 9. Your counterexample is correct, pairwise conditionals do not support the chain rule. The fix is to state Theorem 9 with the history conditional (we also mentioned this in general comment as well, kindly check it once)

pˉ=max⁡σmax⁡BPr⁡[Rσ | ⋂σ′∈BRσ′],\bar{p} = \max_{\sigma}\max_B \Pr\left[R_\sigma \,\middle|\, \bigcap_{\sigma'\in B}R_{\sigma'}\right],

which is the definition in main-text Theorem 4 and the one its proof uses. Theorem 4 in the main paper is therefore unaffected, only the appendix restatement was wrong. In your example Pr⁡[R3∣R1,R2]=1\Pr[R_3\mid R_1,R_2]=1, so pˉ=1\bar{p}=1 and the bound is 1≥1/41\geq 1/4. A pairwise quantity suffices only under an explicit 1-Markov rupture dependence (Prop. 16), which we now state as an assumption to be checked, not a default.

(3) About Lemma 2 (uniformity over continuations). We have revised the proof, by the triangle inequality for dAd_A along the idealization ladder,

εj≤∑rungssup⁡κ∈Kj∣Jκ(a(r))−Jκ(a(r+1))∣.\varepsilon_j \leq \sum_{\text{rungs}}\sup_{\kappa\in K_j}\left|J_\kappa(a^{(r)})-J_\kappa(a^{(r+1)})\right|.

We define gjg_j with these sup rungs, they coincide with the Lemma 1 rungs when KjK_j is a single continuation. Because Σℓ\Sigma_\ell is finite, KjK_j is finite, and the authoring bound holds uniformly over KjK_j at an additive log⁡∣Kj∣\log|K_j| cost.

(4) About Proposition 5 and conservativeness of the live constants. We agree on both counts.

(i) The uniform proxy-to-return constant is an assumption we cannot measure. The live certificates are certificates for drift in the proxy metric, and we now state this.

(ii) The LCAP=3 cap and the use of a pooled median sensitivity were not conservative. Recomputing the original Llama benign pipeline per stage moves its certificate from 0.26 to 0.54, which flips it to REJECT. The new protocol removes both: per-stage envelopes are fitted along the actual trajectory with no cap, and the rupture probability carries a one-sided Clopper–Pearson bound.

(5) About the held out coverage with measured verifier recall/false positives. The checkpoint is now a real node applied to both branches: a gpt-oss-120b verifier that, on NO, calls a repair step. Because repair also runs on the clean branch, its false positives enter the measured loss rather than being assumed away. Measured: the verifier fires on 3.7% (clean branch) / 4.5% (perturbed branch) of calls for gpt-oss-20b and on 0.0% / 1.2% for Qwen, with median contraction 1.0 (245 invocations each, calibration split). Held-out results (general-response table): all four cells hold, path-wise coverage is 0.81–0.96 against guaranteed levels of 0.48–0.84, and held-out violation rates are below PrupP^{\mathrm{rup}} in every cell. The one non-trivial certificate (0.73) is sound but about 3.4$\times$ loose.

(6) One more thing we would like to address is about the certificate guided vs uniform placement at equal cost.

  • Offline, on 300 random DAGs at equal budget, greedy reaches 1.00 / 1.00 / ≥0.99\geq 0.99 of the optimal reduction for m=1/2/3m = 1/2/3; uniform reaches 0.56 / 0.69 / 0.73, and its certificate is 1.7–2.5$\times$ larger.
  • On the live 10 stage pipelines the comparison is degenerate, and we say so: the real checkpoint's measured median contraction is 1.0, so greedy, uniform and optimal placements all give the same bound (0.63 for Qwen). Placement can only matter once a checkpoint contracts. The live data contain no such checkpoint, so the placement evidence remains the offline study.

Also we agree on the writing part. The revision will remove "so the split is not vacuous", "not dropped", "rather than restating an identity", and the repeated "every term controllable or measurable", replaces them with direct statements, and collects the proved-vs-assumed boundary into one paragraph in Section 3.

Regards, Authors of #13289

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

The paper studies how errors and safety risks accumulate when an LLM agent combines multiple skills. It proposes theoretical bounds and evaluates them using synthetic and live-agent experiments.

Critical strengths
  • It studies an important problem: one skill’s mistake can affect later steps.
  • It offers useful ways to think about reducing errors, such as adding checks between steps.
Critical weaknesses
  • The paper measures errors in experiments, but it is unclear why those measurements justify guarantees about future runs.
  • Its method for choosing where to add checks relies on a claim that appears false in some cases: two checks together may help even when neither helps alone.
Questions for authors
  1. How do the guarantees account for uncertainty in the measurements?
  2. Under what conditions does the method for choosing checks work?
  3. What exactly do the experiments count as an error?
1 comment
AuthorsOpenReview ↗

Response to comment from reviewer 86JG

Respected reviewer 86JG,

(1) How the guarantees account for measurement uncertainty? Table 8 plugged point estimates into the bound. The certificate is built from calibrated, held-out statistics. Per-stage envelopes are fitted on one split of inputs. The probability that any stage leaves its envelope or ruptures gets a one-sided Clopper Pearson upper bound from a second, disjoint split. The guarantee is: with probability ≥1−α\geq 1-\alpha over the calibration data, E[out]≤E[B(δ0)]+Prup\mathbb{E}[\mathrm{out}] \leq \mathbb{E}[B(\delta_0)] + P^{\mathrm{rup}} for a new run drawn from the same input distribution. It follows from Theorem 1 because, on the stable event, the chain recurrence holds deterministically. Prop. 8 gives the price (Θ(η−2log⁡δ−1)\Theta(\eta^{-2}\log\delta^{-1}) runs). Applied retroactively to Table 8 with its original pooled constants, the 95% bound keeps Llama's benign DEPLOY (C=0.44C=0.44) but not its verifier flip (0.600.60); with per stage constants the benign DEPLOY is lost as well (0.540.54). We now say so, and the held out experiment replaces Table 8 as the empirical evidence. Held-out results for the new protocol (general-response table): in all four held out cells the certificate holds and pathwise coverage exceeds its 1−Prup1-P^{\mathrm{rup}} guarantee. The confidence adjusted bound is conservative: for Qwen at 4 stages it gives 0.730.73 against a held out loss of 0.210.21 [0.14,0.29][0.14, 0.29], and it rejects at θ=0.5\theta = 0.5. We state this as the sample cost of a valid bound at n≈25–30n \approx 25\text{--}30.

(2). When the checkpoint-selection method works? Your example is right for the certificate as stated, because the saturation min⁡(1,⋅)\min(1,\cdot) creates complementarities. On a chain with L=1.5L=1.5 and d=8d=8, either checkpoint alone leaves C=1C=1 but both give C=0.63C=0.63. The fix: greedy placement now optimizes the uncapped surrogate B+PrupB+P^{\mathrm{rup}}. The guarantee holds when each checkpoint acts on every path through it by a position-independent factor (contraction LvL_v, catch rate qvq_v). Each path term is then 1−∏(1−av)1-\prod(1-a_v), a probabilistic-coverage function, so the objective is monotone submodular and greedy is within (1−1/e)(1-1/e) of optimal. Because min⁡(1,⋅)\min(1,\cdot) is monotone, this minimizes an upper bound on the certificate. On chains, an exact O(dm)O(dm) dynamic program needs no submodularity at all. Checks: 0/5,088 diminishing-returns violations for the surrogate on random DAGs (vs 420/5,088 for the capped form). At equal budget, greedy attains 1.00 / 1.00 / ≥0.99\geq 0.99 of the brute-force optimum for m=1/2/3m = 1/2/3, versus 0.56 / 0.69 / 0.73 for uniform spacing. On the live 10-stage pipelines the comparison is degenerate, and we say so: the real checkpoint's measured median contraction is 1.0, so greedy, uniform and optimal placements all give the same bound (0.63 for Qwen). Placement can only matter once a checkpoint contracts. The live data contain no such checkpoint, so the placement evidence remains the offline study.

(3) What counts as an error?

  • Deviation: the distance between the final output of the run on the clean input and the run on the perturbed input. The distance is lexical cosine distance in [0,1][0,1], our proxy artifact metric d^\hat{d} (Prop. 5).

  • Categorical rupture: an output shorter than 8 characters or matching a refusal pattern (end-to-end); additionally, in the per-skill grid, a robust outlier (>5>5 MAD above the fitted slope) or drift >0.5>0.5; on the tool channel, the tool raising an exception.

  • Stage-level rupture (new protocol): any stage whose (input deviation, output deviation) pair falls outside its calibrated envelope.

Regards, Authors of #13289

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

The paper develops an end-to-end theoretical certificate for tool-augmented LLM skill libraries. It defines a realizable optimum for a frozen LLM, decomposes composition loss into retrieval, selection, interference, and tool terms, derives propagation results for heterogeneous plan DAGs with rupture failures, and further studies library size and learnability, safety under library evolution, and checkpointing. The authors validate the framework on controlled constructions, a 332-skill six-domain suite, public skill libraries, and live model/domain pipelines. The problem is important and the technical package is ambitious, but I remain uncertain whether the main theoretical results constitute a sufficiently distinct advance over existing analyses, and whether the formalization and deployment-oriented calibration are fully closed. I therefore lean toward weak rejection, with low confidence.

Critical strengths
  1. The paper tackles a timely and under-formalized reliability question for skill-based agents. In particular, the attempt to connect a realizable-gap target with heterogeneous path propagation, discontinuous rupture failures, checkpointing, and an explicit evolution horizon provides a potentially useful vocabulary for reasoning about composition-induced loss and safety.
  2. The submission provides an unusually substantial supporting package, including deferred proofs, algorithmic descriptions, deterministic checks, public skill-library measurements, and additional failure and uncertainty analyses. The authors also disclose certificate saturation, limited valid-trial counts, safe-side false negatives, and differences between assumed verifier behavior and live measurements, which makes the empirical limitations easier to inspect.
Critical weaknesses
  1. The paper’s central theoretical advance is difficult to isolate, and its formal scope is not yet fully closed. The propagation result combines heterogeneous plan-DAG sensitivities, multiple depth regimes, rupture terms, lower bounds, and recoverable constants, but the manuscript does not clarify which ingredient is genuinely new relative to the closest prior analyses. Moreover, ΠΩ\Pi_\Omega and Jτ∘J_\tau^\circ are defined through single-skill policies in Definition 1/Appendix B.0 but later used as the optimum for a multi-invocation plan; a plan-level definition or justification is needed.
  2. The live evidence does not yet establish deployment-prediction value. In the 15-cell table, 11 cells saturate at C=1C=1 and each verdict uses at least 8 valid trials; in the 30-cell grid, 2230\frac{22}{30} cells are deployable after one checkpoint, but only 1330\frac{13}{30} have cell-level bootstrap intervals robustly on one side of d⋆=5d^\star=5. Measured loss below the certificate supports bound validity, but not threshold calibration; the deployment claim therefore needs held-out calibration, bound-violation accounting, and justification for C≤0.5C \le 0.5 and d⋆≥5d^\star \ge 5.
Questions for authors
  1. Which single theorem or mechanism should readers regard as the paper's indispensable theoretical advance, and how does it differ from the closest error-compounding, DAG-propagation, compositionality, and safety results under matched assumptions?
  2. Please define the plan-level realizable optimum (for example, ΠΩ(P)\Pi_\Omega(P)) and explain whether this changes Theorem 1, Proposition 2, the safety results, or any reported certificate values.
1 comment
AuthorsOpenReview ↗

Response to comment from reviewer vXyD

Respected reviewer vXyD,

(1) Its the pair Theorem 1 + Theorem 5 . Its a propagation bound for heterogeneous plan DAGs whose nodes are locally sensitive and rupture with bounded probability, together with matching lower bounds showing both terms. (Also Reviewer 63h9 singles out the same result as the most promising!). Under matched assumptions it recovers each closest prior result as a special case.

Setting (matched assumptions)Prior resultTheorem 1 specialisedWhat Thm 1/5 adds
homogeneous chain, Lipschitz LL, no discontinuitiesmodel-based RL rollout error ∝Ld−1L−1\propto \frac{L^d-1}{L-1} (Janner et al. 2019; Asadi et al. 2018)pj=0p_j=0 gives B=εLd−1L−1B=\varepsilon\frac{L^d-1}{L-1}heterogeneous per-edge LijL_{ij} on a DAG; lower bound attained with equality (Thm 5(i))
per-step error ε\varepsilon, neutral dynamicsimitation-learning compounding, linear in horizon (Ross & Bagnell 2010; Ross et al. 2011)L=1L=1 gives B=dεB=d\varepsilonthe contractive regime (depth-independent ε1−L\frac{\varepsilon}{1-L}) and the exact threshold λ=E[log⁡L]<0\lambda=\mathbb{E}[\log L]<0 (Prop. 7), not max⁡L<1\max L<1
independent per-step failure pp, no amplificationaccuracy decays as (1−p)d(1-p)^d (Dziri et al. 2023, informal propositions)ε=0\varepsilon=0 gives Prup=∑pjP^{\mathrm{rup}}=\sum p_jproof under arbitrary dependence (union bound) and Θ(dp)\Theta(dp) lower bound (Thm 5(ii)); combined with amplification in one bound
reasoning-chain snowballinformation-theoretic single chain (Gan et al. 2025)—DAG structure, checkpoints with measured contraction (Cor. 2), black-box constants

The contribution is the model, neither smooth only nor failure only bounds describe LLM pipelines, and a single bound with both terms is order optimal in both regimes simultaneously. We will state this plainly in Section 1.

(2) Definition 1 was single skill. We have revised the definition and would be for a plan P=({qi},D)P=(\{q_i\},D) with nn nodes, a conditioning assignment σ=(σ1,…,σn)∈Σℓn\sigma=(\sigma_1,\ldots,\sigma_n)\in\Sigma_\ell^n runs node ii under policy πσi\pi_{\sigma_i}. Let J(P;σ)J(P;\sigma) be the resulting return and J∘(P):=max⁡σJ(P;σ)J^\circ(P):=\max_\sigma J(P;\sigma). The maximum is attained because Σℓ\Sigma_\ell is finite (∣Πℓ∣≤∣V∣ℓ+1|\Pi_\ell|\leq |V|^{\ell+1}). Δplan:=J∘−J∘(P)\Delta_{\mathrm{plan}}:=J^\circ-J^\circ(P) is the plan-structure gap.

The ideal artifact ajideala_j^{\mathrm{ideal}} is node jj's output under the maximizer σ∗\sigma^* on ideal inputs. KjK_j is the set of downstream continuations obtained by varying σ\sigma on jj's descendants.

Definition 1 is the case n=1n=1. Effect on the results: (i) Theorem 1 is unchanged: it is a statement about node deviations relative to a trajectory. (ii) Proposition 2 holds with J∘:=J∘(P)J^\circ := J^\circ(P), which is what the main text already meant by "plan-relative" (Sec. 3). (iii) The safety results (Thms 3–4) do not involve J∘J^\circ. (iv) No reported certificate value changes, since no experiment computes J∘J^\circ directly.

Calibration of θ\theta=0.5 and d∗≥5d^* \geq 5 : These are operator inputs, a risk tolerance and an operating depth, analogous to choosing αα. The certificate's primary output is the useful depth d∗d^*, so any θ\theta can be read off. Sensitivity over the 30 cell grid:

θdeployable after one checkpoint (d*≥5)bare
0.37/301/30
0.413/301/30
0.522/301/30
0.625/301/30

The model ranking by median d∗d^* is identical for θ\theta ∈ {0.3, 0.5, 0.6}: Llama-3.1-8B > Llama-4-Maverick ≈ Llama-3.3-70B > Qwen3-Next-80B > gpt-oss-20B. The verdict's qualitative content is therefore not an artifact of θ\theta.

Held out calibration and bound violation accounting : This is the new split-calibrated experiment (kindly refer to the general response comment). The certificate is fitted on FIT/RUP and evaluated once on held-out TEST inputs. We report held-out coverage and the held-out rate of envelope violations against the calibrated PrupP^{rup}. In all four held-out cells the certificate holds, path-wise coverage exceeds its guarantee (e.g. 0.96 vs ≥ 0.84 for Qwen, 4 stages), and the held-out violation rate is below PrupP^{rup} (0.08–0.38 vs 0.16–0.52). The table is in the general response, including the caveat that the one non-trivial certificate (0.73) is about 3.4× looser than the held-out loss (0.21). Concerning the original grid, we agree the per-cell verdicts are noisy (13/30 cells are robust under bootstrap); the per-model pooled verdicts are robust for 4 of 5 models.

For presentation : In the revision, the main theorem will be stated first in Section 5, with the dependency figure as the roadmap. The notation table is cross-referenced at each first use and defensive asides are removed.

Regards, Authors of #13289

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response for our work

We thank the reviewers for close, technical reading. Several points identified were genuine weakness. We have corrected all of them, and the corrections below will be incorporated into the revised paper. The below general comment is to make sure that our work is well understood along with revisions. Corrections to theory : (1) In theorem 4 : The proof needs a budget per ruptured invocation rather than per action. We now define c as the max number of undeclared capabilities in a single rupture invocation can exercise. If only a per action budget cac_a is enforced and an invocation takes at most A actions, the theorem holds with c:=min(∣c∣,A−ca)c := min(|c|, A-c_a).

(2) In theorem 9 : The appendix statement used a pairwise pˉ\bar{p}, which doesn't support chain rule. We now use history conditioned pˉ=max⁡σmax⁡BPr⁡[Rσ | ⋂σ′∈BRσ′]\bar{p} = \max_{\sigma} \max_{B} \Pr\left[R_{\sigma} \ \middle|\ \bigcap_{\sigma' \in B} R_{\sigma'}\right], which is the definition already used by Theorem 4 and its proof. On the counter example this pˉ=1(Pr⁡[R3∣R1,R2]=1)\bar{p} = 1 \left(\Pr[R_3 \mid R_1, R_2] = 1\right), so the bound holds. Proposition 16 is now presented as the special case under a 1 Markov rupture dependence, with that assumption stated.

(3) In Lemma 2 : ϵj\epsilon_j is a supremum over downstream continuations, so the 'rungs' must bound it uniformly. We now apply the triangular inequality of dAd_A along the idealisation ladder : εj≤∑rungssup⁡κ∈Kj∣ΔJκ∣\varepsilon_j \leq \sum_{\text{rungs}} \sup_{\kappa \in K_j} \left|\Delta J_\kappa\right| and define gjg_j with these sup-rings. As ∑l\sum_{l} is finite, the per term bounds hold uniformly over KjK_j, at an additive log(∣Kj∣)log(|K_j|) cost in the sample complexity.

(4) For checkpoint placement : The submodularity claim is false for the capped certificate min⁡(1,B)+Prup\min(1,B)+P^{\mathrm{rup}}. With the cap, two checkpoints can help when neither helps alone. For example, on a chain with L=1.5L=1.5 and d=8d=8, a checkpoint after stage 33 alone or after stage 66 alone leaves C=1C=1, while selecting both gives C=0.63C=0.63.

Algorithms 2 and 6 now optimize the uncapped surrogate B+PrupB+P^{\mathrm{rup}}. Each path term has the form 1−∏v(1−av)1-\prod_v(1-a_v),which is a probabilistic-coverage function. Hence, the surrogate is monotone submodular, and the (1−1/e)(1-1/e) approximation guarantee holds. Since min⁡(1,⋅)\min(1,\cdot) is monotone, minimizing this surrogate also minimizes an upper bound on CC.

On chains, the O(dm)O(dm) dynamic program is exact for either objective. Numerically, we observe 00 diminishing-returns violations in 5,0885{,}088 random checks for the surrogate, compared with 420420 violations for the capped form.

AuthorsOpenReview ↗

Continuation of the General response

Source inputs are split into disjoint FIT / RUP / TEST sets. On FIT, per-stage envelopes out≤εj+Lj⋅in\mathrm{out}\leq \varepsilon_j+L_j\cdot\mathrm{in} are fitted along the actual pipeline trajectory, per stage, with no cap and no pooling. On RUP, the probability that any node leaves its envelope or ruptures gets a Clopper–Pearson upper bound (Bonferroni-corrected over the envelope choices). The certificate is evaluated once on TEST. Theorem 1 then gives: with probability ≥1−α\geq 1-\alpha over calibration, E[out]≤E[B(δ0)]+Prup\mathbb{E}[\mathrm{out}]\leq \mathbb{E}[B(\delta_0)]+P^{\mathrm{rup}} on new runs from the same input distribution. The checkpoint is a real node (verifier plus a repair call) applied to both branches, so its false positives are paid for and its contraction is measured rather than assumed. Results (θ=0.5\theta=0.5, α=0.05\alpha=0.05; certificate fixed on FIT/RUP, then evaluated once on TEST):

PipelineCCConclusionHeld-out loss, mean [95% CI]Path-wise coverage (guaranteed ≥\geq)Held-out ScS^c vs PrupP^{\mathrm{rup}}
Qwen3.8-27B, 4 stages0.73REJECT0.21 [0.14, 0.29], n=25n=250.96 (≥0.84\geq 0.84)0.08 vs 0.16
Qwen3.8-27B, 10 stages1.00REJECT0.35 [0.24, 0.48], n=22n=220.82 (≥0.58\geq 0.58)0.23 vs 0.42
gpt-oss-20b, 4 stages1.00REJECT0.52 [0.36, 0.67], n=23n=230.96 (≥0.48\geq 0.48)0.09 vs 0.52
gpt-oss-20b, 10 stages1.00REJECT0.61 [0.49, 0.73], n=21n=210.81 (≥0.49\geq 0.49)0.38 vs 0.51

What this shows and what it does not. (i) Soundness: no cell violates the certificate, pathwise coverage exceeds its guaranteed level everywhere, and the held out violation rate stays below the calibrated PrupP^{\mathrm{rup}} everywhere. (ii) Tightness: the only non-trivial cell (Qwen, 4 stages) is sound but about 3.4$\times$ loose, so at θ=0.5\theta=0.5 it rejects a pipeline whose held out drift is 0.21. This is a conservative false negative. With 24–30 calibration runs, the Clopper Pearson term alone is 0.16–0.55, which is the sample cost Prop. 8 predicts. We present this as a soundness check, not as evidence of tightness. (iii) The ordering is consistent where the certificate can show one: at 4 stages it ranks Qwen below gpt-oss (0.73 vs 1.00), as the held out loss does (0.21 vs 0.52). At 10 stages both certificates saturate at 1.00, so they do not separate the models. (iv) The real checkpoint fires on 0–4.5% of calls and has median measured contraction 1.0 (calibration split). It does not contract this proxy metric, and we report that. Counting the 400 as a full rupture (loss 1) moves the gpt-oss 10 stage mean to 0.63 and its coverage to ≥0.77\geq 0.77, and changes no conclusion.

Corrections to empirical claims. (a) The new protocol runs on currently served models: gpt-oss-20b (also in the paper), Qwen3.8-27B, and gpt-oss-120b as verifier/repair. (b) The original end to end checkpoint reset a flagged artifact to the clean branch's output. That is an idealized recovery, so the reported 4.2$\times$ loss reduction was optimistic; the new experiment uses a real repair step. (c) Under a 95% upper bound on the rupture rate (0/15 observed ruptures gives up to 0.18), the original Table 8 changes: Llama's benign DEPLOY survives (C=0.44C=0.44), but the Llama verifier flip (0.60) and Mistral-Small's DEPLOY (0.64) do not. We report this and no longer present the flip as a headline. With per-stage rather than pooled constants (reply to 63h9), Llama's benign certificate rises to 0.54 even before the confidence adjustment, so that DEPLOY does not survive either; the original Table 8 verdicts are superseded by the held-out experiment above. (d) "Bounds hold in all 27 cells": 21 of those cells have C=1C=1 and hold trivially, and 3 cells of the four extra models rest on ≤1\leq 1 valid trial. We now report only informative cells (C<1C<1) with ≥8\geq 8 valid trials.

About Writing. The revision will remove the defensive phrasing (examples in that reply) and move the statement of what is proved vs. assumed into a single paragraph.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.