PaperlayerView exact revision on arXiv

Source-linked AI summary

EvoUndo: Recoverability-Constrained Self-Evolution for LLM Agent Harnesses

Tanmay Sah, Dolly Sah, Harshul Jain, Tanya Sah

arXiv:2608.28363v1cs.AI

TL;DR

LLM agents can improve their capabilities through self-modification, but persistent changes may not be safely reversible across different states. EvoUndo makes recoverability an explicit, counterfactually verified constraint and finds that exact state grounding and richer recovery languages resolve distinct recovery bottlenecks.

  • Problem

    Forward capability improvement does not ensure safe reversal because recovery may depend on information and state different from the mutation’s creation context.

  • Method

    EvoUndo represents, synthesizes, diagnoses, and independently verifies recovery for self-modifications across counterfactual states using typed observational equivalence.

  • Results

    Exact state-address grounding recovered 38/48 (79.2%) failures when L0 sufficed, while L1 enabled recovery on 142/143 (99.3%) failures in S1.

  • Takeaways & Limitations

    Reliable self-evolution requires co-designing verification, state grounding, witness semantics, and recovery-language expressivity.

  • Takeaways & Limitations

    The L0/L1 calculi are specialized to modeled harness state types, lack formal completeness guarantees, and have untested transfer to richer stacks.

Abstract

from arXiv · show

LLM agents increasingly modify their own prompts, tools, middleware, resources, and execution harnesses at runtime. Such self-evolution can improve capability, but a successful mutation may leave persistent effects that cannot be safely reversed in states different from the one in which it was created. We introduce EvoUndo, a framework for representing, synthesizing, diagnosing, and independently verifying recoverability of model-generated self-modifications across counterfactual states. Across 600 unseen one-shot self-evolution tasks, we identify 197 capability-improving mutations that fail recoverability verification. Under the original recovery representation, conventional repair strategies recover 0/197 of these natural failures. Deterministic oracle analysis recovers 48/197 under the original recovery language L0, while the extended recovery calculus increases empirical oracle recovery to 191/197. A protocol-locked 2x2 grounding-by-expressivity intervention then separates two bottlenecks: exact state-address grounding increases successful recovery from 0/48 to 38/48 (79.2%) when the original language is sufficient, while extending the recovery language enables recovery on 142/143 (99.3%) failures in the oracle-defined S1 stratum. On the primary gpt-oss-120b backbone, adding exact-address diagnostics to the richer language reduces recovery to 133/143 (93.0%); a Qwen3.8-27B replication preserves the grounding and expressivity effects but not this negative interaction, indicating that the latter is model-dependent. These results indicate that reliable agent self-evolution requires co-designing verification, state grounding, witness semantics, and recovery-language expressivity rather than relying on iterative prompting alone.

1 Introduction

EvoUndo frames self-evolution as capability improvement constrained by recoverability across counterfactual harness states. Its results show that exact state grounding and recovery-language expressivity address distinct failure modes, with diagnostic interactions depending on the model backbone.

  • Motivation: Recoverability requires restoring observationally equivalent pre-mutation states across counterfactual states, not merely improving the forward task objective.Mutations may overwrite configurations, reorder middleware, shadow tools, or leak background resources, making nominal-state recovery insufficient.
  • Results: 114/120 (95.0%) deliberately corrupted but recoverable mutations are repaired by verifier-guided typed diagnosis at budget four, versus 4/120 (3.3%) under independent regeneration.This result supports diagnosis as an actionable repair mechanism rather than merely an evaluation step.
  • Framework: EvoUndo couples witness capture, counterfactual verification, typed diagnosis, and closed-loop recovery synthesis for recoverability-constrained self-evolution.Candidates are admitted only when recovered states satisfy typed observational equivalence with their corresponding pre-states.
  • Results: 38/48 (79.2%) S0 failures are recovered by exact-address grounding, while L1 recovers 142/143 (99.3%) S1 failures.The protocol-locked 2 × 2 intervention separates grounding from expressivity bottlenecks.
  • Results: Exact-address feedback degrades L1 recovery on gpt-oss-120b, but the negative interaction does not reproduce on Qwen3.8-27B.The interaction between diagnostic granularity and recovery-language capacity is therefore backbone-dependent.

2 Problem Formulation

EvoUndo models self-evolution as capability-improving mutations to persistent agent-harness state that require witnessed, contract-based recovery. Recoverability is counterfactual and relational, requiring thresholded observational restoration across states, while experiments fix the forward mutation and repair only recovery components.

  • 2.1 Self-Evolving Agent Harnesses: A harness H = (S, Π) comprises persistent state S and execution policy Π, with mutation m capability-improving when ΔJ(m; S) > 0.Persistent state includes prompts, routing, tools, middleware, listeners, files, and managed resources.
  • 2.1 Self-Evolving Agent Harnesses: Permanent admission requires verified recovery semantics because persistent modifications can become obsolete or conflict with future goals.
  • 2.2 Witnessed Recovery and Running Example: Because mutations may overwrite predecessor information, recovery captures pre-state with witness w and applies program u to the mutated state and witness.Recovery computes ŝ = u(m(s), w(s)).
  • 2.2 Witnessed Recovery and Running Example: The timeout example restores a prior scalar using its witness, whereas middleware insertion requires recovery information beyond a simple scalar inverse.Setting timeout from 30 to 60 requires recording and restoring the prior value 30.
  • 2.3 Typed Observational Equivalence: Recovery uses typed observational equivalence under effect contract Ce rather than demanding byte-level equality across the entire environment.Representations canonicalize dictionary keys and volatile identifiers, while file contents are checked with SHA-256 hashes.
  • 2.4 Counterfactual Recoverability: Counterfactual recoverability evaluates whether recovery succeeds across states drawn from Q using language L, with required probability threshold τR, making it relational and parameterized by the mutation, representations, contract, and Q.
  • 2.5 Recoverability-Constrained Objective: The objective combines forward improvement with Pr_s∼Q[u(m(s), w(s)) ≃Ce s] ≥ τR and E(m, s) ⊆ Ce; experiments fix m = m0 and optimize only (w, u, Ce).Joint optimization of the forward mutation was not evaluated.

3 EvoUndo

EvoUndo represents self-modifications with immutable forward mutations and revisable witness, recovery, and effect-contract components. It verifies round-trip recovery across counterfactual states, diagnoses residuals, synthesizes bounded repairs in a formal language, and admits candidates only under conservative hidden-state confidence criteria.

  • Representation and repair: Each candidate is a 4-tuple of forward mutation, witness program, recovery program, and declared effect contract, with only the latter three revisable during repair.The forward mutation is locked at Turn 0 and executed verbatim; the contract must conform to the runtime’s typed effect constraints.
  • Verification: EvoUndo verifies each counterfactual state by executing the recovery round trip and checking whether the reconstructed state is equivalent under the declared effect contract.Development states provide diagnostics, while the fresh-holdout study uses a fully feedback-isolated hidden set for final admission.
  • Diagnostics: Failed development round trips produce residual diagnostics ranging from affected-subsystem and defect classifications to exact canonical state addresses and ordering traces.The coarse D0 diagnosis omits exact residual locations; D1 supplies verifier-observed addresses and traces.
  • Synthesis language: Recovery synthesis is bounded over witness capture, recovery, and contract revisions, while the immutable mutation remains fixed and proposals that pass development states are tested on hidden states.Witnesses record typed pre-state values before mutation; recovery operations may reference only those captures. L0 covers configuration, prompt, tool-registry, and routing state, whereas L1 adds middleware, listeners, files, sockets, and ordered cross-surface composition.
  • Admission control: Admission requires a 95% Wilson lower confidence bound of at least 0.85 over hidden counterfactuals, with fail-closed handling for syntax errors and other unsoundness risks.Repair budgets are B ∈ {1, 2, 3, 4} with early stopping, and the hidden-set criterion is LCB0.95(k, n) ≥ τR = 0.85.

4 Experimental Setup

The experiments evaluate recoverability across 600 unseen self-evolution tasks and a frozen bank of 197 natural failures, using controlled oracle audits and a protocol-locked 2 × 2 factorial design. The setup separates recovery-language expressivity from exact state-address grounding across development and hidden states.

  • Benchmark: The natural benchmark contains 600 tasks across six architectural families, while Multi-Surface tasks combine mutations affecting at least two persistent state targets.The families are Configuration, Tools, Middleware, Listeners, Resources, and Multi-Surface; prompt and routing state are also modeled.
  • Evaluation protocol: Candidates are evaluated on 10 development and 40 hidden states, including IID and OOD perturbations, using gpt-oss-120b at temperature 0.2 with medium reasoning effort.The model runs at native MXFP4 precision on eight NVIDIA H200 GPUs; outcomes use Rescue@B, paired risk differences with 95% bootstrap CIs, and corrected McNemar tests.
  • Evaluation cohort: Of 600 sampled mutations, 197 are capability-positive but fail recovery verification, forming the frozen primary evaluation cohort alongside 120 controlled defect-injected mutations.The remaining natural candidates include 281 admissible and 122 capability-inadequate mutations; sampling used one candidate per task without rerolls.
  • Oracle audit: Oracle recoverability is 48/197 under L0 and 191/197 under L1, partitioning failures by whether the implemented language can construct a recovery program.Six tasks unrecovered by the L1 oracle are excluded from stratum contrasts, and the oracle is retrospective and privileged rather than available to deployed synthesizers.
  • Factorial design: The primary factorial study crosses diagnostic granularity {D0, D1} with recovery language {L0, L1}, testing grounding under L0, expressivity on S1, and grounding atop L1.The three protocol-locked contrasts are C1 D1L0 vs. D0L0 on S0, C2 D0L1 vs. D0L0 on S1, and C3 D1L1 vs. D0L1 on S1.

5 Controlled and Natural Recovery Results

Across controlled defects, closed-loop verifier feedback enables high recovery, but this success collapses on natural self-evolution failures under the base representation. In the full 600-task accounting, the richer D0L1 recovery setting rescues most recovery-defective mutations and substantially raises admissible benchmark yield.

  • Controlled recovery: On the controlled benchmark, prescriptive hints recover 117/120 (97.5%) defects, while typed diagnosis recovers 114/120 (95.0%) and independent regeneration recovers 4/120 (3.3%).Generic feedback recovers 104/120 (86.7%), and raw verifier traces recover 101/120 (84.2%) at budget B = 4.
  • Natural recovery: On 197 natural failures under L0, every verifier-guided repair mode recovers 0/197 (0.0%), while independent regeneration recovers 6/197 (3.0%).180/197 natural failures involve structural state transformations outside the predefined controlled defect taxonomy.
  • End-to-end accounting: 180/197 (91.37%) recovery-defective mutations are rescued under D0L1, producing 461/478 (96.44%) admissible capability-positive mutations and 461/600 (76.83%) total benchmark yield.This is a +30.00 pp absolute increase over the initially admissible 281/600 (46.83%).

6 Grounding–Expressivity Factorial Results

The factorial experiment shows that exact state-address grounding resolves failures under restrictive recovery language, while richer recovery primitives resolve failures requiring greater expressivity. Exact-address feedback harms performance on the primary backbone with the richer language, but this interaction is model-dependent in replication.

  • Factorial results: On S0, exact addresses raise recovery from 0/48 under D0L0 to 38/48 (79.2%) under D1L0, while on S1, L1 raises recovery from 0/143 to 142/143 (99.3%).These results isolate grounding and expressivity as distinct bottlenecks: exact addresses locate affected state surfaces, whereas richer primitives enable valid recovery programs.
  • Factorial results: On S1, adding exact-address feedback to L1 reduces recovery from 142/143 (99.3%) under D0L1 to 133/143 (93.0%) under D1L1.Trace review attributes the discordant cases to over-decomposition, sequence inversions, and over-capture collisions under D1L1.
  • Synthesis efficiency: Synthesis efficiency reaches 79.2% for D1L0 and 94.2% for D0L1, but falls to 87.4% for D1L1 from 0.0% for D0L0.The efficiency denominator includes only tasks that the deterministic oracle establishes are expressible in the assigned recovery language.
  • Factorial results: The full-cohort interaction on gpt-oss-120b is I = −25.89 pp, indicating that exact grounding is beneficial with restrictive language but not additive with richer primitives.The interaction supports treating diagnostic granularity as a model–representation design choice.
  • Cross-model replication: In the Qwen3.8-27B replication, grounding and expressivity effects persist, while exact-address diagnosis under L1 changes recovery by +6.25 pp rather than significantly decreasing it.The recurring bottlenecks transfer across backbones, but the negative grounding–expressivity interaction appears model-dependent.

7 Fresh-Holdout Validation and Robustness

Fresh-holdout validation shows that frozen L1 generalizes across 300 unseen tasks, while stricter verification trades end-to-end yield for reduced false positives. Robustness sweeps preserve the qualitative behavior of counterfactual verification, with measurable inference and repair overhead.

  • Fresh-Holdout Validation: 16.8% → 0.0% development-to-hidden false positives, while strict verification reduced Rescue@4100 from 49.7% to 35.0% (∆ = −14.67 pp, p = 5.76 ×).These results came from 300 fresh unseen tasks using frozen L1 and a 100-state hidden evaluation suite; increasing development counterfactuals from Q2 to Q20 eliminated false positives under fixed B = 4.
  • Sensitivity and Robustness Analysis: Across sweeps of synthesis budgets, admission thresholds, development configurations, and hidden sample sizes, counterfactual verification retained stable qualitative behavior.The evaluated ranges were B ∈ {1, 2, 3, 4}, τR ∈ {0.75, 0.80, 0.85, 0.90, 0.95}, five development configurations, and nhid ∈ {10, 20, 30, 50, 100}.
  • Inference and Verification Overhead: 2.39–3.09 model calls and approximately 3.37k–4.30k generated tokens per fresh-holdout task, with higher verification strictness increasing cost.On the 197-task factorial cohort, closed-loop repair averaged 1.78 calls/task in D0L1, 1.95 in D1L1, and 2.40 in D1L0; mean latencies were 5.25–5.85 seconds on H200 GPUs.

8 Discussion and Limitations

EvoUndo’s effectiveness depends on adequate state grounding and recovery primitives, while diagnostic specificity can interact non-monotonically with language expressivity. Its guarantees and scope are limited by comparisons with snapshot recovery, empirical rather than deductive verification, specialized calculi, and untested transfer to richer harness stacks.

  • Discussion: 0/197 failures were recovered by iterative repair without adequate state addresses or recovery primitives, showing that prompting or reasoning effort alone is insufficient.On the primary model, diagnostic feedback also interacted non-monotonically with recovery-language expressivity, so maximal diagnostic specificity is not universally preferable.
  • Snapshot and transactional recovery: Effect-scoped snapshots recovered 300/300 (100.0%) selective-recovery tasks versus 243/300 (81.0%) for EvoUndo, but under same-surface concurrency both fell to 159/300 (53.0%) and 131/300 (43.7%), respectively.Full snapshots recovered 0/300 in both regimes because they clobbered subsequent state.
  • Proof-based verification and runtime enforcement: EvoUndo provides empirical typed round-trip evidence over heterogeneous modeled harness states, unlike Astrogator’s deductive verification within a specified automation calculus.The empirical approach covers recovery properties without claiming proof-level completeness.
  • Limitations and Data Governance: The L0/L1 calculi are specialized to modeled harness state types, lack formal completeness guarantees, and have untested transfer to richer stacks.Other limitations include keeping m immutable during repair, not evaluating joint optimization or transactional redesign of m, and limited coverage from typed equivalence and effect tracking.

9 Conclusion … D.3 Effect-Contract Coverage Audit

EvoUndo argues that safe, auditable self-evolution requires jointly designing verification, state grounding, witness semantics, and recovery-language expressivity. It operationalizes this principle through typed harness states, canonical addresses, counterfactual verification, observational equivalence, and dynamically checked effect contracts.

  • 9 Conclusion: EvoUndo shows that safe self-evolution requires co-designing verification, state grounding, witness semantics, and recovery-language expressivity.When recovery representations are aligned, language models can synthesize state-dependent recovery programs for auditable self-evolving agents.
  • Reproducibility Statement; Ethics Statement; AI Use Statement: The released implementation includes code, task definitions, counterfactual generators, protocol locks, and evaluation traces, while experiments used isolated sandboxes and require additional authorization and audit controls for live deployment.Generative AI tools assisted coding and draft editing.
  • A Extended Related Work: EvoUndo complements prior self-improvement, reversible-runtime, reversible-programming, and runtime-enforcement work by separating capability validation from recoverability verification.SEVerA provides stronger deductive guarantees, while EvoUndo uses empirical counterfactual verification; the approaches address complementary properties.
  • B EvoUndo Implementation Details; B.1 Harness State Representation; B.2 Candidate Representation; D.2 Typed Observational Equivalence: The harness is modeled as typed persistent state with canonical addresses and type-specific observational equivalence spanning configuration, prompts, routing, tools, middleware, listeners, files, and resources.Candidate mutations freeze the forward change while allowing witness capture, recovery, and effect-contract repair.
  • B.3 Canonical State Addresses: Canonical verifier diagnostics expose semantic locations such as tools["tool id"], config["key"], middleware["middleware id"], files["path"], and resources["resource id"].Addresses are canonicalized across residual extraction and rendering, and derive only from verifier-visible development executions.
  • C Recovery Languages; C.1 Base Recovery Language L0; C.2 Extended Recovery Language L1: L1 extends L0 with indexed sequence, listener, file-prestate, resource-descriptor, and ordered multi-surface recovery operations.The runtime rejects unsupported L1 primitives in L0 conditions, treating them as invalid model outputs rather than evidence of formal language completeness.
  • D Counterfactual Verification and Audit Baselines; D.1 Round-Trip Evaluation and Counterfactual Generation Taxonomy; D.2 Typed Observational Equivalence: Recovery is tested on counterfactual states using type-specific semantic equivalence rather than byte-level equality over the entire harness.The effect contract selects relevant targets; middleware requires membership and ordering, tools require binding and implementation state, listeners require registration restoration, and files require prior-state restoration.
  • D.3 Effect-Contract Coverage Audit: Dynamic effect tracking rejects any mutation whose observed effects are omitted from its declared contract.The audit constructs incomplete contracts for 300 mutations spanning all six harness families, using E(m, s) = SnapshotDiff(s, m(s)) ∪ ExecutionTraceEffects(m, s) and requiring E(m, s) ⊆ Ce.

D.4 Snapshot-Restore Baselines

Across 300 multi-step mutation tasks, EvoUndo was compared with full-state and effect-scoped snapshot restoration under disjoint-surface and same-surface regimes. Full snapshots failed under selective recovery, while effect-scoped snapshots were strongest when exact restorable pre-state was available; EvoUndo targeted cases requiring synthesized inverse semantics.

  • Runtime overhead: 1165.0/1165.0 B, 177.8/145.0 B, and 393.6/350.5 B were the mean/median storage values for Full Snapshot, Effect-Scoped Snapshot, and EvoUndo, respectively.Storage counts UTF-8 encoded JSON bytes for full harness state, touched pre-state values, or EvoUndo's witness store plus recovery AST.
  • Runtime overhead: 0.084/0.083 ms, 0.039/0.037 ms, and 0.050/0.047 ms were the corresponding mean/median capture, rollback, and verification latencies.Latency was measured with wall-clock time.perf counter() across capture, rollback, and verification.
  • Recovery outcomes: 0/300 full-snapshot recoveries succeeded because restoring the full state clobbered all subsequent state changes.The comparison covered 300 tasks across different-surface selective recovery and same-surface concurrent recovery regimes.
  • Recovery outcomes: Effect-scoped snapshots were strongest when the exact affected pre-state was known, serializable, and directly restorable, but both selective approaches degraded for mutations within the same structured surface.EvoUndo addresses cases where inverse semantics are missing, state-dependent, structured, or must be synthesized.

E Controlled Recoverability Benchmark … I Fresh-Holdout Counterfactual Sensitivity

Across controlled and natural-failure benchmarks, richer diagnostics and recovery expressivity substantially improve empirical recoverability, while deterministic oracle audits separate synthesis failures from language limitations. Factorial, cross-model, and fresh-holdout evaluations test grounding, expressivity, counterfactual stability, and protocol sensitivity under fixed experimental conditions.

  • E Controlled Recoverability Benchmark: 117/120 (97.5%) capability-positive controlled defects were recovered with prescriptive guidance at B = 4, versus 4/120 (3.3%) under strict regeneration.Typed diagnosis recovered 114/120 (95.0%), generic feedback 104/120 (86.7%), and raw verifier traces 101/120 (84.2%).
  • F Natural Failure Bank: 197/600 natural candidates were capability-positive but recovery-defective, and Generic, Raw, Typed, and Prescriptive repair recovered 0/197 under the original representation.Strict regeneration recovered 6/197 at B = 4; the defective candidates were frozen for subsequent analyses.
  • G.1 Deterministic Constructive Principles; G.2 Oracle Inputs and Construction Algorithm; G.4 Admission Criterion for Oracle Solvability: The deterministic constructive oracle builds witness captures and inverse operations in LIFO order, then admits candidates only after compilation, positive capability change, perfect development recovery, hidden-state confidence, and typed equivalence checks.Its results are empirical recoverability under the implemented oracle, not a formal proof of language-theoretic completeness.
  • G.6 Oracle Stratum Resampling Stability Sweep: Across 10 independently resampled counterfactual suites, oracle strata remained unchanged at |S0| = 48, |S1| = 143, with 6 unrecovered cases and Jaccard = 1.The audit used the same generative state distribution while changing counterfactual seeds 1000 through 10000.
  • H.4 Discordant Trace Analysis (D1L1 vs. D0L1); H.5 Cross-Model Replication with Qwen3.8-27B (Step 24B): Qwen3.8-27B replicated grounding and expressivity effects under constrained decoding, but not gpt-oss-120b’s negative D1-on-L1 interaction; detailed D1 diagnostics also produced a 10.2% truncation rate.The replication used a frozen 96-task subset, while discordant gpt-oss-120b tasks were analyzed through authenticated trace metrics in Table 6.
  • I Fresh-Holdout Counterfactual Sensitivity: The fresh-holdout study evaluates frozen L1 recovery on 300 unseen tasks under common diagnostics, budget, and a 100-state hidden set, with tables covering false positives, sample-size, threshold, cost, and family sensitivity.The holdout uses 50 tasks from each of six architectural families and zero overlap with the original 600-task cohort; τR = 0.85 remains the protocol-locked primary threshold.

J Statistical Analysis … K.2 Execution Integrity and Protocol Locking

The confirmatory contrasts show strong positive effects for C1 and C2, but a significant negative effect for C3, with these directions robust to leave-one-family-out analysis. The study uses exact paired testing, fail-closed execution, and cryptographically hashed artifacts to protect protocol integrity.

  • J Statistical Analysis: The contrasts used paired two-sided exact McNemar tests with joint Holm–Bonferroni correction and 100,000 paired bootstrap resamples for risk-difference intervals.
  • J Statistical Analysis: C1 showed Δ= +79.17 pp, 95% CI [+66.67, +89.58], p_raw = 7.28×10−12, and p_Holm = 1.46×10−11.
  • J Statistical Analysis: C2 showed Δ= +99.30 pp, 95% CI [+97.90, +100.00], p_raw = 3.59 × 10−43, and p_Holm = 1.08 × 10−42.
  • J Statistical Analysis: C3 showed Δ= −6.29 pp, 95% CI [−11.19, −2.10], with p_raw = p_Holm = 0.01171875.
  • K.1 Family-Level Leave-One-Out Sensitivity: Leave-one-family-out estimates remained strongly positive for C1 and C2, while C3 stayed negative across every partition.The exploratory full-cohort factorial interaction was also negative: I = −25.89 pp, 95% CI [−34.01, −18.27].
  • K.2 Execution Integrity and Protocol Locking: Execution was fail-closed: service failures aborted runs, malformed outputs consumed attempts, and out-of-language recovery primitives were rejected before execution.
  • K.2 Execution Integrity and Protocol Locking: Result artifacts, manifests, protocol configurations, success vectors, and analysis scripts were cryptographically hashed to distinguish authenticated results from superseded runs.
Loading 2608.28363v1…