PaperlayerView exact revision on arXiv

Source-linked AI summary

Safe Harness Self-Evolution: A Theoretical Analysis of Feasibility and Limits

Qianshu Cai, Yonggang Zhang, Jun Nie, Maohao Ran, Huajiang Zheng, Jun Song, Xinmei Tian, Yike Guo, Wei Xue

arXiv:2609.08175v1cs.AI

TL;DR

Persistent harness self-evolution raises how an agent can safely improve while its underlying language model remains frozen and modifications affect future tasks. The paper develops a theoretical framework for generation, finite-data certification, selection, adoption, and post-update behavior, showing that generation and certification create distinct bottlenecks and that certified improvement need not imply further progress. Its guarantees rely on a fixed reward function and user-task distribution, with stronger subgroup and initial-agent retention guarantees requiring additional conditions.

  • Problem

    Persistent modifications can repair previously failed tasks while degrading performance on other user tasks, so safe qualification must control both failure-task improvement and retained-task change.

  • Method

    The paper connects reachability, candidate-pool selection, finite-data certification, safe adoption, evaluation limits, and successor-agent improvement under a fixed user-task distribution.

  • Results

    Generation and certification impose distinct constraints: more candidates need not improve successful-update guarantees when qualification remains unresolved, and current safe improvement does not guarantee further successor improvement.

  • Takeaways & Limitations

    The theory provides a basis for diagnosing stagnation and distinguishing bottlenecks attributable to the current state, generation, evaluation, certification, or later updates.

  • Takeaways & Limitations

    Guarantees assume persistent harness modifications with a frozen language model, fixed reward function, specified task distribution, and average retained-task tolerance; stronger subgroup or initial-agent guarantees require further conditions.

Abstract

from arXiv · show

Harness self-evolution is the process by which an agent modifies its prompts, tools, code, or orchestration in response to task feedback while keeping the underlying language model frozen, with changes persisting across subsequent tasks. We provide a systematic theoretical analysis of the feasibility and limits of safe harness self-evolution, connecting modification generation, finite-data certification and selection, safe adoption, and behavior after an update. Under a fixed user-task distribution, we establish conditions guaranteeing overall expected-reward improvement while controlling changes on retained tasks, characterize the probability of generating qualified modifications, and derive finite-data bounds for safe selection and adoption. Our analysis shows that generation and certification impose distinct constraints: current task performance does not determine the probability of generating qualified modifications, and generating more candidates need not improve the guarantee of a successful update when evaluation is limiting. Stagnation may therefore arise even when improvement opportunities remain. We further show that worst-case evaluation cost for recognizing genuine improvements diverges as expected reward approaches its upper bound. Across successive updates, certified improvement guarantees accumulate over a finite run, but a successful update does not by itself guarantee that further improvement remains possible. These results provide a basis for diagnosing bottlenecks and designing safer self-evolution mechanisms.

1 Introduction

The paper frames harness self-evolution as persistent modification of an agent’s harness around a frozen language model and develops a theory of when such modifications can be generated, certified, safely adopted, and followed by further improvement.

  • Scope and motivation: Harness self-evolution modifies prompts, code, tools, and orchestration around a frozen language model, with changes persisting across subsequent tasks.The analysis covers a loop in which modifications respond to task feedback and affect later agent behavior.
  • Scope and motivation: The analysis connects modification generation, finite-data certification, safe adoption, and successor-agent improvement across four central questions.These questions concern qualified modifications, adoption, limits to safe improvement, and further improvement after an update.
  • Safe improvement: Expected-reward improvement must combine repair of failure tasks with acceptable changes on retained tasks under the user-task distribution.The target is defined through the contribution of failure-task improvement and tolerated retained-task changes.
  • Safe improvement: Reachability and finite-data selection bounds show that generation opportunities, certification, and adoption impose distinct constraints on successful safe updates.If the current state cannot supply the required failure-task contribution, no generation process or evaluation budget can meet the target.
  • Diagnosis and continued evolution: Finite-sample confidence bounds separate generation uncertainty from uncertainty about whether evaluated modifications satisfy the target.Generating more candidates need not resolve qualification uncertainty, so stagnation can persist despite available improvement opportunities.
  • Diagnosis and continued evolution: Certified expected-reward improvements accumulate across a finite run, but a successful first update does not guarantee that a successor can improve again.The analysis constructs cases where the first update is qualified and certified while no later improvement is available.

2 Problem Setting

The problem setting models an incumbent agent with a frozen language model and an evolvable harness that generates, evaluates, certifies, and either adopts or rejects persistent modifications over user tasks.

  • Agent and task model: At step k, the incumbent agent is A_k = (M, C_k), where M is frozen and C_k contains the evolvable prompts, code, tools, and orchestration.The agent maps user tasks to outputs according to its current harness.
  • Generation and evaluation: A finite generation procedure produces candidate outputs in M_⊥, including failed runs, and valid modifications induce candidate agents eA_i = A_k ⊕ c_i.Only valid modifications proceed to behavioral evaluation.
  • Agent and task model: The user-task space T_user has distribution D_user, and expected reward averages task-level output rewards under that distribution.The reward function maps tasks and outputs to values in [0, 1], while V(A, t) is the expected reward on a task.
  • Generation and evaluation: The certifier uses finite evaluation results to determine whether modifications have sufficient evidence for safe adoption.A selector may choose a certified modification; otherwise the incumbent remains unchanged for the next step.
  • Analysis questions: The framework studies how often qualified modifications can be generated, when finite evaluation can certify them, how far safe improvement can proceed, and whether successors can improve further.These questions organize the analysis across generation, certification, adoption, limits, and subsequent self-evolution.

3 Qualified Modifications and Reachability

The paper defines qualified modifications by requiring failure-task improvement alongside bounded retained-task change, then analyzes when such modifications can be generated and selected safely. It shows that reachability depends on the target, agent state, and generation process, while candidate-pool size only bounds what selection can achieve.

  • Qualified modifications: Qualified modifications must improve incumbent failure tasks while keeping retained-task changes within a specified tolerance.The target T=(λ, δ) sets the minimum failure-task improvement and maximum tolerated retained-task change.
  • Qualified modifications: Improving failure-task performance alone can reduce overall reward when retained-task degradation is larger in magnitude.The decomposition therefore requires retained-task changes to remain small in either direction.
  • Qualified modifications: A qualified modification guarantees expected-reward gain of at least λ − (1 − Z_k)δ under the stated assumptions.Choosing λ_k(γ, δ)=γ+(1−Z_k)δ yields a required overall improvement γ.
  • Reachability and selection: The candidate-pool success probability is bounded by the probability that at least one sampled candidate is qualified.An oracle reaches this bound, so evaluation and selection cannot create a qualified modification absent from the fixed pool.
  • Reachability and selection: If either necessary inequality for positive reachability fails, no generation process, selector, candidate-pool size, or evaluation budget can produce a qualified modification.Satisfying the inequalities is only necessary, not sufficient, because the generation distribution may still assign zero probability to qualified modifications.
  • Reachability and selection: A benchmark score or frozen LLM alone cannot determine qualified-modification probability; the target and generation process must also be specified.The paper constructs configurations with identical frozen models and user-task behavior but different generation probabilities.

4 Finite-Data Certification and Safe Agent Updates

The paper develops finite-data procedures for certifying qualified modifications, selecting them safely, and abstaining when required evidence is unavailable. Its guarantees separate candidate generation from evaluation precision and bound unsafe acceptance while allowing retained-task effects to be controlled.

  • Certification and selection: Finite-data certification uses simultaneous coverage to ensure that every certified modification is qualified for the fixed target.The construction relies on pre-pool interval-width bounds and evaluation data separated from generation.
  • Certification and selection: Finite interval widths shrink the subset of qualified modifications guaranteed to be certified, while the qualified set itself remains unchanged.The inner certified subset requires target margins determined by upper bounds on total interval widths.
  • Certification and selection: O(log(N/βstat)/neff) interval widths mean that increasing candidate-pool size N can reduce certification probability at fixed effective evaluation sample size.More candidates can increase pool coverage, but simultaneous evaluation coverage becomes harder as N grows, so the lower bound need not increase with N.
  • Certification and selection: Mean reachability does not generally determine the probability that a shared-context candidate pool contains a qualified modification.A concavity bound using mean reachability is valid but can overestimate the context-averaged pool probability.
  • Safe updates: The finite-horizon protocol abstains when valid modifications or required evaluation samples are unavailable, retaining the incumbent instead.Evaluation uses separate failure-task and retained-task samples, paired rollouts, and simultaneous error radii for loss, retained-task change, and failure rate.
  • Safe updates: Theorem 4 bounds the probability of accepting a modification whose gain falls below the certified lower bound by βstep,k, but does not ensure improvement at every step.Two-Gate accepts only when the required inputs and observable checks hold; otherwise rejection or abstention leaves the incumbent unchanged.
  • Safe updates: Two-Gate uses the full declared retained-task tolerance, whereas Measured-margin uses the candidate’s estimated decrease and error radius.At matched tolerance and radii, retained-task increases are not counted as losses, and smaller estimated decreases reduce the deduction in the gain lower bound.

5 How Far Can Safe Self-Evolution Proceed?

Safe self-evolution can become infeasible when the threshold required to guarantee improvement conflicts with bounds imposed by incumbent performance, retained-task tolerance, and finite evaluation. More accurate evaluation helps, but cannot remove restrictions arising from the declared tolerance, and increasing only the failure-task sample size is insufficient.

  • Acceptance constraints: Acceptance requires τ to satisfy both the improvement-guarantee condition and the upper bound τ ≤ bLk.The admissible region combines the lower threshold needed for certification with an upper threshold determined by incumbent performance and evaluation quantities.
  • Acceptance constraints: The admissible region is nonempty if and only if δmax > 0, with acceptable δ values restricted to 0 < δ < δmax.When δmax > 0, the admissible threshold values form an interval constrained by both safety and incumbent-performance bounds.
  • Acceptance constraints: A declared δ ≥ δmax cannot be accommodated by adjusting τ or generating more modifications when the state and evaluation quantities are fixed.The resulting necessary condition appears as a lower bound on the observed failure rate.
  • Evaluation limits: More accurate evaluation relaxes the restriction by reducing εΣ, but the term (1 − Zk)δ remains even with exact evaluation.This residual term arises because the improvement guarantee uses the full declared tolerance to bound retained-task loss.
  • Evaluation limits: Increasing nF alone does not remove the evaluation limitation; other evaluation error bounds must also be reduced.Figure 2 separates the restriction remaining with exact evaluation from the additional restriction caused by finite data.
  • Further improvement: On a hard two-task family, maintaining stated error control and certification probability requires worst-case expected rollout cost that diverges as uk ↓ 0.The sufficient sample-size construction and rollout lower bound use different sample counts and are not matching minimax rates.
  • Further improvement: A low acceptance rate alone cannot distinguish absent qualified modifications, rare generation, and evaluation uncertainty that blocks certification.The paper treats these as separate diagnostic possibilities requiring different responses.

6 Diagnosing Self-Evolution

The paper separates generation, certification, and selection as distinct bottlenecks in self-evolution, then shows that accepted improvements do not ensure future improvement opportunities.

  • Acceptance Rates: Generation, certification, and selection impose distinct constraints on whether a self-evolution update succeeds.A pool can contain qualified modifications yet produce no qualified selection because candidates are uncertified or not selected.
  • Acceptance Rates: High certification probability implies non-small reachability, but low certification probability is compatible with either rare qualified generation or insufficient evidence.Inner-set guarantees can become uninformative when full-range rectangle requirements make the inner set empty.
  • Acceptance Rates: On a fixed pool, qualified modifications without qualified certified members indicate certification loss; available qualified certified members that are not selected indicate selection loss.Changing the certifier or selector does not change reachability or the gate-independent pool probability.
  • Estimating Reachability: Uniform reachability bounds separate uncertainty from finite generation samples from uncertainty about whether evaluated modifications satisfy the target.More candidates reduce the empirical-process term but need not resolve uncertainty caused by imprecise evaluation near target boundaries.
  • Finite-Run Guarantees: Accepted-step improvement guarantees accumulate over a finite run, but they do not guarantee that further-improving modifications will be generated.The finite-run guarantee requires per-step conditions and controlled total risk, without requiring independence between steps.
  • Finite-Run Guarantees: Under unrestricted updates, one step can improve expected reward with probability one while all subsequent steps provide no additional improvement.The construction uses the same successor modification in two instances whose later composition maps differ.
  • Self-Evolution over Multiple Steps: Across four WorkBuddy–DSH sequences, the fraction of new modifications meeting T0 fell from .906 initially to .625 and then .438 after successive update opportunities.The selected updates improved observed mean reward on one task set, but this did not establish that later modifications would meet the target.

7 Relation to prior work

The paper situates its analysis among work on harness self-evolution, theoretical self-improvement, generation-versus-selection, and safe policy improvement.

  • Harness self-evolution: Prior harness self-evolution work spans source-code rewriting, prompt evolution, reusable skills, workflow search, and sequences of agent variants.Related systems also use descendant performance or regression screening to guide search and adoption.
  • Theoretical analyses of self-improvement: The paper complements theoretical self-improvement analyses covering improver utility, policy-reachable hypothesis classes, validation, capacity control, and statistical adoption rules.These lines of work provide oracle, learnability, risk-improvement, and error-allocation perspectives.
  • Generation, selection, and iterative improvement: Generation-versus-selection studies distinguish success within a sampled pool from returning one candidate, paralleling this paper’s reachability and selection analysis.The candidate-pool bound shares the i.i.d. any-hit structure underlying pass@k, but concerns persistent harness modifications.
  • Safe policy improvement: Safe policy-improvement methods constrain policy changes or preserve baseline behavior when data coverage is insufficient.This paper instead compares incumbent and candidate agents under a common user-task distribution with separate improvement and retention requirements.

8 Limitations and Future Work

The analysis is scoped to frozen-LLM harness changes under specified reward and task-distribution assumptions, while future work targets broader validation and mechanisms preserving later improvement.

  • Limitations: The guarantees assume a frozen LLM, fixed reward function, and specified user-task distribution, with retention measured by average absolute change relative to the incumbent.Tail-level and cumulative-change extensions provide additional protection, but stronger subgroup guarantees remain outside the stated scope.
  • Limitations: Reachability confidence bounds separate generation sampling error from qualification uncertainty, which can remain large near target boundaries despite larger generation samples.The studies provide evidence for the examined settings, while broader comparisons across updates remain to be established.
  • Future Work: Future work should identify generation and update mechanisms that preserve subsequent opportunities to improve while maintaining current safe improvement.The unrestricted-update result motivates structural analysis of later-step reachability and adaptive search.
  • Future Work: Improving safe adoption requires sharper boundary-mass conditions, more efficient certification, and characterization of certification power at fixed evaluation budgets.These directions connect to worst-case evaluation-cost limits and stronger retention or changing-distribution requirements.
  • Future Work: Longer update sequences, more contexts, repeated independent rollouts, and controlled comparisons could clarify which mechanisms improve adoption and preserve further improvement.The framework also supports comparing certifiers, generation procedures, update rules, and transfer from reused suites to fresh tasks.

9 Conclusion

The analysis identifies distinct limits across generation, certification, adoption, and post-update improvement in harness self-evolution. It also formalizes the agent, task, reward, and evolvable-state framework used to state these results.

  • Conclusion: A target beyond the current state’s capabilities cannot be reached by increasing generation or evaluation budgets.Certification limits may still allow safe improvement when a modification’s retained-task loss is accounted for.
  • Conclusion: Uniform reachability bounds separate finite generation-sample uncertainty from unresolved qualification under finite evaluation.This distinction supports diagnosis of stagnation and shows why generating more modifications may not resolve certification uncertainty.
  • Conclusion: Across a finite update run, certified improvement guarantees accumulate under per-step conditions and run-level risk allocation.A successful safe update does not guarantee that the successor agent can improve further.
  • System scope: The theory keeps the language model frozen while allowing evolution of prompts, tools, orchestration, and source-code artifacts that persist after acceptance.Generation runs record valid modifications or failure, and validity is checked before behavioral evaluation.
  • Formal setting: Expected-reward comparisons use a fixed user-task distribution and fixed reward function, with ground-truth utility treated separately.The framework models agents as measurable Markov kernels over user-facing and self-modification tasks.
  • Scope boundary: Self-task distributions and expected rewards provide architectural notation only and are not consumed by the main results.The principal cross-agent quantity is expected reward under the user-task distribution.

C.1 Reward and task structure

The formal setting compares agents under a common user-task distribution and bounded reward, while modeling dependent task streams, evaluation separation, and finite candidate generation. Its assumptions determine when the statistical guarantees are informative.

  • Reward and task structure: The same user-task distribution is used for every agent produced by self-evolution.This assumption supports cross-agent comparisons through a common Duser.
  • Reward assumptions: The reward is bounded in [0, 1], and uniform reward fidelity requires |∆rtar(t, o)| ≤ ϵtar for every task–outcome pair.The analysis does not estimate ϵtar from observed task data.
  • Dependence assumptions: Task streams may be stationary β-mixing rather than independent, while failure detection is local to each task and outcome.The i.i.d. case is recovered when β ≡ 0.
  • Evaluation protocol: Generation material must be separated from evaluation material, including a fixed evaluation suite disjoint from the failure batch.Reusing generation material for evaluation violates the stated separation requirements.
  • Generation model: Each candidate pool contains N complete generation runs, including failures, and selection may choose a valid modification or retain the incumbent without conditional redrawing.The candidate-pool model permits general modification distributions without monotonicity, small-step, or factorization assumptions.
  • Limits: Positive reachability for a fixed target requires Juser(Ak) ≤ 1−λ, but this state-local condition does not determine reachability after changing the target, context, or update rule.The theory also requires domain-specific conditions for numerical bounds to be informative.

D.5 Evaluation cost for certification

Certification cost depends on the precision and variance of evaluation measurements. Paired Bernstein evaluation can reduce fixed-budget requirements, but the analyzed fixed-m gate may reject small budgets and does not derive adaptive stopping complexity.

  • Fixed-budget cost: m ≈ 2.8 × 10^3 rollouts are needed by the Hoeffding radius at Ẑk = 0.3 and LV = 13.8.This is a gate-side fixed-budget calculation from the displayed radius.
  • Paired evaluation: m = 833 satisfies the same requirement with paired Bernstein when σ̂δ = 0.1, reducing the calculated cost by about 3.3×.The comparison uses matched per-task risk β(1).
  • Small-budget boundary: At m = 50, the paired-radius additive term is approximately 1.38, so that radius cannot certify a positive paired difference.The fixed-m Hoeffding bound also fails for a separate reason, with 2εV ≈ 0.743.
  • Scope limitation: The analyzed fixed-m gate does not cover the admissible region at m = 50, while sequential stopping mechanisms are mentioned without derived stopping complexity or admissible-region results.An always-valid confidence sequence could replace the fixed radius while preserving coverage, but its sample complexity is not derived.

E Reward fidelity and ground-truth utility

The paper evaluates certification with a fixed reward function while separately defining ground-truth utility. Uniform reward fidelity transfers expected-reward guarantees to ground-truth utility with a quantified loss.

  • Reward fidelity: The certification rule and finite-sample evaluations use the fixed reward r, while ground-truth utility r∗ is treated separately.Under uniform reward fidelity, the expected-reward guarantee transfers to the corresponding ground-truth guarantee.
  • Assumption scope: Uniform reward fidelity applies pointwise to every task–outcome pair and remains valid across adaptive generation, selection, and updating.The present analysis treats ϵtar as a condition rather than estimating it from task data.
  • Transfer guarantee: 2ϵtar is subtracted when transferring a finite-sample expected-reward improvement lower bound to ground-truth utility.No additional probabilistic event is required for this transfer.

F.1 Decomposition and retained-task changes

The paper decomposes safe harness evolution into reward improvement and retained-task change, distinguishing reward-level behavior from outcome-distribution changes. It then connects reachability, candidate selection, certification, and evaluation limits.

  • Retained-task changes: Outcome-distribution divergence is strictly more sensitive than DR because reward-preserving outcome remappings can leave DR unchanged.The paper exhibits a single-task two-outcome setting with DR = 0 and divergent outcome distributions.
  • Decomposition: Expected user reward decomposes into improvement on the user-task distribution plus an error term controlled by retained-task changes.The paper gives the bound Juser(eA) − Juser(Ak) = LAk(eA) + EAk(eA) ≥ LAk(eA) − (1 − Zk)δ.
  • Reachability: The incumbent’s global reward shortfall upper-bounds improvement for every candidate, independently of sampling and certification.For candidates satisfying retained-task constraints, the feasible improvement scale is also bounded by the incumbent shortfall.
  • Reachability and selection: Candidate-pool selection can be analyzed through reachability, but target probabilities depend on the generation distribution and can differ across targets under the same distribution.A fixed distribution can assign probability p to one qualified set and zero to another, showing that current state information does not determine all target reachabilities.
  • Certification and selection: Finite-data certification provides simultaneous bounds, yet increasing the candidate count need not improve the certified success guarantee because evaluation widths grow with log N.The certified lower bound is therefore not necessarily monotone in N; an optimal candidate count requires a specified budget, allocation, and dependence model.

F.4 Task-stream evaluation and updates

Task-stream evaluation supplies finite-sample guarantees for estimating candidate behavior and certifying updates. The resulting conditions expose measurement thresholds, near-optimal evaluation costs, and the distinction between accumulated current improvement and guaranteed future progress.

  • Task-stream evaluation: Returned evaluation tasks are conditionally i.i.d. under the task-stream reference experiment, supporting concentration-based certification analyses.The analysis separately accounts for mixing-aware coupling when transferring the reference guarantees to actual task streams.
  • Task-stream evaluation: Finite-rollout absolute-value estimates of retained-task changes are conservative in expectation relative to their oracle values.For each task, E[|δ̂(t)|] ≥ |δ(t)|, and the aggregate estimate inherits the corresponding conservative comparison under the stated task-arrival assumptions.
  • Safe adoption: Certified acceptance controls the joint event that an accepted update improves expected reward by less than the specified margin.The measured-margin rule and Two-Gate rule differ in whether they control absolute retained-task changes or decreases and how those quantities are estimated.
  • Constraints on further improvement: The admissible region is nonempty only when the incumbent has sufficient reward shortfall and measurement margins exceed finite-sample errors.Necessary conditions include Θk > εΣ + εL and, for the retained-task branch, Zkāk > εΣ.
  • Constraints on further improvement: Recognizing genuine improvements becomes arbitrarily expensive as the incumbent reward shortfall uk approaches zero.For the stated certifiers, the worst-case expected rollout count satisfies E−[Neval] ≥ Zk/(10uk) under the specified regime.
  • Reachability diagnosis: Reachability confidence bounds distinguish uncertainty from finite generation samples from uncertainty about whether evaluated modifications satisfy the target.A low certification probability is compatible with either low reachability or low certification power, while the bounds apply uniformly across targets under the stated experiment.
  • Successive updates: Across accepted updates, certified improvement accumulates on the fixed reference distribution, but one successful update does not ensure later improvement remains reachable.Unrestricted composition maps can preserve current improvement while producing no further improvement opportunities.

G.21 Sample-complexity lower bound for certification near the reward upper bound (§5.2)

Certification near the reward upper bound requires distinguishing nearly indistinguishable improving and non-improving candidates. The resulting worst-case rollout cost grows as the incumbent’s reward shortfall vanishes, independently of adaptive sampling or stopping rules.

  • Hard-family construction: Theorem 11 constructs two instances differing only in candidate rewards on failure tasks, with candidate improvements of +u/2 and −u/2.Both instances share Z_k = Z and incumbent shortfall u, making certification require distinguishing closely related cases.
  • Lower bound: E−[N] ≥ Z/(10u) candidate rollouts are required to certify the improving modification with probability at least 1/2 at level β.The lower bound applies under any task-selection policy and data-dependent stopping rule, with expectation under the non-improving instance.
  • Upper-bound consequence: As Juser(Ak) approaches 1, no fixed worst-case rollout budget can retain certification probability at least 1/2 across these hard pairs.Thus a uniform fixed-power certification budget cannot cover the range B_k < Juser < 1.
  • Proof mechanism: The hard-pair argument uses indistinguishable observables except candidate rewards on the failure task, linking information accumulation directly to informative rollout count.KL and total-variation bounds show that only candidate rollouts on the differing task contribute information.
  • Rate comparison: The lower bound has order Ω(Z/u), while the current gate’s Hoeffding-based schedules use quadratic base resolution in several sample coordinates.Empirical-Bernstein control resolves the informative reward gap with approximately O~(u^-1) observations, but the rates are not established as matching minimax rates.
  • Pipeline implication: The certification-cost constraint composes with candidate-pool selection: pool-restricted selection cannot exceed the probability that the pool contains a target-satisfying modification.Both generation/selection and certification constraints apply above B_k.

H When the task distribution responds to an Agent update

When task distributions respond to agent updates, comparative improvement on the pre-update distribution no longer directly equals realized post-update improvement. The analysis separates these quantities and adds a response-drift term to single-step guarantees.

  • Definitions: Comparative improvement evaluates two agents on one distribution, whereas realized improvement evaluates the updated agent after the task distribution responds.Absolute expected reward is a separate quantity evaluated under an agent-associated distribution.
  • Multi-step behavior: Theorem 12 decomposes realized reward increments into same-measure agent comparison and task-distribution movement, with endogenous response included in the drift term.Subtracting the response movement again would count the same movement twice.
  • Single-step guarantees: A single-step realized-improvement guarantee subtracts the response modulus ϱ from the comparative lower bound.The gate condition correspondingly becomes τ > (1 − Ẑ_k + ε_Z)(δ + ε_D) + ε_L + ϱ when a valid response bound is supplied.
  • Scope boundary: Assumption 5 alone provides no informative pre-update bound on ϱ, so post-update reward-response estimates are needed for the realized reading.The incumbent distribution is observed, while a candidate’s associated distribution is counterfactual before adoption.
  • Estimation: The response quantity W is controlled by the stated sampling and resolution analysis, but this does not control the full total variation ϱ.Estimating the post-update response therefore requires distinguishing the bounded observable from the full distributional shift.
  • Interpretation: A small average retained-task change need not imply that few tasks change, because every retained task can change when expected advantage is uniformly δ > 0.The positive resolution ε makes this possibility explicit.
  • Interpretation: Modifications preserving the same task-space behavior kernel have zero advantage and cannot satisfy a positive target threshold.When the agent-user channel is restricted to observed behavior on T_user, such modifications also have zero response modulus.
  • Multi-step behavior: Under Assumption 5, response occurs only when an update is accepted, so response accumulates over accepted updates rather than every attempted step.If the incumbent is retained, ϱ_k = 0.

I.1.1 Conditional sample-complexity relations and numerical example

The conditional relations separate sampling-error effects from constraints imposed by declared tolerances and reward bounds. As sampling radii vanish, tolerance-driven boundaries remain, while reachability and candidate-pool success retain distinct scope limits.

  • Numerical example: The required failure quota grows quadratically in inverse distance to the zero-failure-radius boundary, while (m, n_R) determine the boundary itself.Finite-horizon arrival is governed separately by a binomial return relation.
  • Conditional relations: Measurement radii decrease at rate Θ(n^-1/2), while the reward upper bound retains one declared tolerance term and one sample-dependent term.The table distinguishes the estimator branch from the gap-to-reward-upper-bound branch.
  • Conditional relations: Additional samples reduce ε_Σ but cannot remove the declared term (1 − Z_k)δ from the positive-tolerance feasibility boundary.The zero-radius upper bound remains Juser(A_k) < 1 − (1 − Z_k)δ − ε_Σ.
  • Across updates: Certified improvement reduces remaining expected-reward shortfall, but neither Z_k ā_k nor Z_k is claimed to decrease monotonically.The declared tolerance component survives when sampling radii vanish, unlike the finite-sample lower bound set by those radii.
  • Across updates: Enforcing the same tolerance at each step need not preserve that tolerance relative to the initial retained-task distribution because retained-task weights are reweighted by the current incumbent.Theorem 7 accumulates certified gains on the stationary user-task distribution, while the retained-task reference can change across updates.
  • Reachability scope: Positive reachability requires Juser(A_k) ≤ 1 − λ, with an additional Corollary 5 condition of 1 − γ − (1 − Z_k)δ.The declaration rule yielding 1 − (1 − Z_k)δ belongs to a different gate and is not a competing primary bound for fixed-(λ, δ) reachability.
  • Reachability scope: The selector success bound is conditional on a candidate pool and is not a prediction of capability after multiple agent updates.A multi-step theory must specify how modification distributions, reachability, and targets change after each update.

I.3.2 Evaluation cost of reachability estimation

Reachability estimation is limited by distinct sampling, evaluation, and ambiguity terms: larger generation samples reduce sampling error, but cannot remove evaluation-boundary uncertainty or shared incumbent error. The resulting costs can remain substantial, while empirical studies show that point estimates may suggest qualified modifications even when simultaneous certification rarely succeeds.

  • Scope: The cost analysis does not estimate amortized savings because they depend on the unknown probability that confidence rectangles cross the target boundary.Appendix D.5 provides only a gate-side worst-case comparison and makes no claim about amortized savings.
  • Budget decomposition: A shared-incumbent term remains even as generation-sample size increases, while per-task bias remains at fixed evaluation budget.Both budgets must be adequate because increasing m cannot remove the |Rev|-controlled additive term, and increasing suite size cannot remove fixed-m per-task bias.
  • Reference cost: Approximately 6.6 × 10^8 rollouts are required at the stated fixed-suite reference design, with a possible reduction under assumption (M3) that is not estimated.The design evaluates 500 modifications on 500 failure tasks and 5000 retained tasks, with per-task reward standard deviation bounded by σV ≤ .15.
  • Budget decomposition: Increasing the generation sample shrinks the sampling radius, but more precise evaluation is needed to resolve confidence-rectangle boundary ambiguity.The final interval width contains both a sampling-radius term and a confidence-bound gap; reducing only the former does not ensure the desired resolution.
  • Empirical diagnosis: At the stated budgets, independent-audit point estimates classify many modifications as target-satisfying, but simultaneous certification rarely succeeds on the held-out DS-1000 suite.The diagnostic covers four studied contexts; one solver draw per agent–task pair supports point summaries, while simultaneous target-grid bounds remain mostly vacuous.
  • Empirical diagnosis: For the realized WorkBuddy–DSH bank, all four modifications meet the target under audit point estimates, yet every confidence interval crosses λ and the separate gate certifies none.The system therefore retains the incumbent, with bQpt = 0 for this bank.
Loading 2609.08175v1…