PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified Long-Horizon Code Agent Evolution via Validation-Gated Skill Optimization

Yifan Wang, Hao Cheng, Xiaomin Li, Yuexing Hao, Hemanth Neelgund Ramesh, Dongwon Jung, Hao Tang, Keru Wang, Chenliang Zhou, Qianhui Wu, Wenlin Yao, Ananth Grama, Andrzej Banburski-Fahey, Baolin Peng, Jaron Lanier, Jianfeng Gao

arXiv:2609.32990v1cs.AI

TL;DR

Long-horizon self-evolution asks whether agents with frozen model weights can keep improving through persistent textual memory, a question little tested in repository-level software engineering. VALVE proposes validation-gated skill-bank updates and provides theoretical guarantees. Across approximately 1,000 software-engineering tasks per repository, it reports average final and peak gains of 14.9 and 16.5 points, with lower drawdown and a more compact bank than ungated evolution.

  • Problem

    Prior self-evolution methods were mostly evaluated in bounded settings, leaving unclear whether repeated textual updates help when persistent memory must support hundreds of subsequent decisions.

    Source: §1 · p. 2

  • Method

    VALVE extracts skill proposals from task trajectories, validates proposals on held-out tasks before retaining them, and retrieves validated skills for future tasks.

    Source: §1 · p. 2

  • Results

    Across approximately 1,000 software-engineering tasks per repository, VALVE reports average final and peak gains of 14.9 and 16.5 points, versus 0.9 and 7.0 points without a gate, while cutting average drawdown by 4.0× and using an 11× more compact skill bank.

    Source: §6 · p. 9

  • Takeaways & Limitations

    Validation-gated updates provide a practical mechanism for reliable long-horizon agent evolution, with VALVE outperforming ungated evolution on final and peak gains while reducing drawdown and bank size.

    Source: §6 · p. 9

    The guarantees assume disjoint, i.i.d. adaptation, validation, and evaluation samples, with the evaluation set never used for extraction or validation.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

Long horizon agent self-evolution without model weight updates is essential for enabling deployed agents to accumulate reusable skills and improve over time. Prior self-evolution work has focused primarily on short-horizon tasks, while repository-level software engineering remains unexplored despite being an ideal testbed for long-horizon adaptation. In this setting, agents are required to solve streams of sequential tasks, navigate complex dependencies with evolving repositories and persistently store and reuse experience. Text-based skill optimization offers an efficient, non-parametric approach for such adaptation. However, existing methods often suffer from unstable updates, performance drawdown, and agent collapse over extended deployments. In this paper, we formalize the concept of in-context self-evolution and introduce VALVE, a validated-gated framework for long-horizon skill optimization. We establish finite convergence, provide theoretical guarantees for future-task gain and drawdown, and derive the validation and evaluation holdout sizes required for a prescribed tolerance, with leading-order scaling Empirically, our pipeline, VALVE achieves stable self-improvement over evolution horizon spanning more than 1,000 SWE tasks, with average final and peak gains of $14.9$ and $16.5$ points across three frontier models (GPT-5.5, Claude-4.6 and MiniMax-M2.7). The validation gate reduces average drawdown by 75% and produces an 11x more compact skill bank than ungated evolution. We further present extensive ablations identifying the design choices most critical to long-horizon skill evolution.

1 Introduction

The paper asks whether text-based agent self-evolution remains useful over long task streams, where repeated updates can destabilize persistent memory. It introduces validation-gated skill optimization and reports theoretical guarantees and sustained gains over roughly 1,000 tasks per repository.

Motivation

  • The paper formalizes the gap between bounded optimization studies and whether repeated textual updates help across hundreds of future decisions using persistent memory.Repository-level software engineering involves sequential tasks, complex codebases and dependencies, and carrying experience forward across diverse issues.Source: §1 · p. 2

VALVE

  • VALVE proposes skills from completed task trajectories, accepts them only after held-out validation shows improvement, and retrieves validated skills for future tasks.Its deployment horizon includes all task arrivals, but only validation-approved skills enter persistent memory.Source: §1 · p. 2

Long-horizon skill optimization for repo-level software engineering

  • Across approximately 1,000 task arrivals per repository, VALVE achieves the best average final and peak gains across three frontier models and four repositories.Its pipeline combines mixed-outcome contrastive extraction, atomic validation of joint proposals with paired executable rollouts, and selective retrieval of rich-text principles and skills.Source: §1 · p. 2

Theory

  • The framework establishes finite convergence, guarantees for future-task gain and long-horizon drawdown, and holdout-size bounds for target tolerances.A disjoint evaluation set certifies final gain and drawdown, while the validation-panel size controls certified population loss of accepted updates.Source: §1 · p. 2

Evidence for selective retention

  • Validation reduces average drawdown from 6.1 to 1.5 points and produces an 11× smaller memory bank.Component ablations and item-level analysis examine how extraction, bank structure, and skill representation affect retained improvement.Source: §1 · p. 3

2 Related Work

Related work studies external textual state for agent improvement, as well as self-improvement in software engineering. VALVE focuses on validation and skill-bank evolution over long task streams while keeping the LLM and solver harness fixed.

Context, experience, and skill optimization

  • Prompt, context, experience, and skill methods optimize or accumulate external textual state, with SkillOpt and SkillOpt-Lite closest to VALVE’s held-out validation of skill updates.Prior methods include prompt optimization, richer context artifacts, trajectory-derived feedback and workflows, and skills constructed from trajectory evidence.Source: §2 · p. 3

Self-evolving code agents

  • Software-engineering agents have learned experience banks, adapted scaffolds, optimized agent implementations, or updated model parameters, whereas VALVE isolates skill-bank evolution with the LLM and solver harness fixed.This focus supports study of validation, regression, and convergence over long streams of project-level software-engineering tasks.Source: §2 · p. 3

3 VALVE: Validation-Gated Evolution for Agents

VALVE frames long-horizon agent evolution as text-space optimization of a persistent skill bank, with extraction and validation changing the bank while retrieval remains fixed. Its theory addresses convergence, population performance, adaptive validation, and holdout sizing.

3.1 Problem setup and VALVE framework

  • With model weights and solver harness fixed, population performance is expected solve probability under a task-specific retrieval of the persistent textual bank.The fixed retriever maps each task and bank into compact context because the full bank may consume context or misguide solving.Source: §3.1 · p. 3

3. VALVE: Validation-Gated Evolution for Agents

  • VALVE separates evolution into Extract, Validate, and Retrieve, and studies optimization of Extract and Validate while keeping retrieval fixed.The minimal interface allows different extraction, validation, memory, and retrieval mechanisms to instantiate the framework.Source: §3.1 · pp. 3–4

3.1 Problem setup and VALVE framework

  • VALVE extracts up to three principles and three skills from mixed outcomes among three attempts, then commits a proposed bank update only when paired held-out rollouts meet a positive validation margin.The retriever independently ranks principles and skills for each task, while the gate evaluates the complete state transition.Source: §3.1 · p. 4

3.2 Stable evolution and certified performance

  • Positive-margin acceptance makes the fixed-panel score non-decreasing and bounds accepted moves; a disjoint evaluation set certifies final population gain and peak-to-final drawdown.The drawdown budget depends on the number of distinct banks, which is bounded by accepted changes rather than the total task horizon.Source: §3.2 · pp. 4–5

3.3 Validation reliability and holdout sizing

  • A uniform population-loss bound remains valid when the same validation panel is reused adaptively, and inverting deviation radii yields holdout sizes for target tolerances.The sizing procedure treats validation and evaluation sets separately; the validation size controls loss for accepted updates, while the evaluation size controls drawdown slack.Source: §3.3 · p. 5

4 Experiments

Across four repositories and three backbones, the experiments compare VALVE with ungated evolution, SkillOpt, and base models. VALVE improves average final performance and retains more of its peak gain with less drawdown.

4.1 Experimental setup

  • The setup uses disjoint 100-task evaluation sets, a fixed 50-task validation panel, and evolution streams of approximately 1,000 tasks per repository.The comparison includes three backbones and uses three rollouts per task; SkillOpt and VALVE both use 50 validation tasks per repository.Source: §4.1 · p. 6
  • Validated evolution takes 122.1 hours per run on average, compared with 50.6 hours without the gate and 96.1 hours for SkillOpt.Source: §4.1 · p. 7

4.2 Main results

  • 14.9 points is VALVE’s average final resolved-rate gain across twelve model-repository runs, improving the average from 63.9% to 78.9%.VALVE outperforms its unevolved base model and its no-validation counterpart in every run, and beats SkillOpt in final model average for all three backbones.Source: Table 1 · p. 6, §4.2 · p. 7
  • 16.5 points is VALVE’s overall peak gain; it retains 14.9 points, with 1.5 points of average drawdown.SkillOpt peaks at 10.8 and retains 7.1 points, while VALVE without validation peaks at 7.0 and retains 0.9 points, with 6.1 points of drawdown.Source: Table 2 · p. 6, §4.2 · p. 7
  • For Claude-4.6, the no-validation average run peaks at +5.6 points but ends at −6.5, while VALVE reaches +21.1 and retains +19.6.Three of four no-validation Claude-4.6 runs and the MiniMax-M2.7 pydicom run finish below baseline.Source: §4.2 · p. 7
  • On Claude-4.6 with pygments, VALVE peaks at 97.0% and ends at 92.3% after approximately 1,000 stream tasks; without validation, it falls from 91.7% to 80.0%.Across twelve runs, average drawdown is 1.5 points with validation versus 6.1 without it.Source: §4.2 · p. 7

5 Ablation and Insights for Skill Optimization

The ablations identify skill organization and extraction granularity as the largest measured design effects, while validation size and selective retention shape final performance and bank growth. On pygments, every evaluated retained item improves resolved rate over the no-memory baseline.

5 Ablation and Insights for Skill Optimization

  • The section examines component choices, validation size, and how validation shapes skill-bank growth and utility.Figure 3 presents component-level ablations on pydicom with GPT-5.5, and Table 3 reports final bank sizes as skills / principles.Source: §5 · p. 7, Figure 3 · p. 7, Table 3 · p. 8

5.1 Component ablations

  • 11.7 points are lost when generation batch size rises from 1 to 4, and 11.0 points when the skill bank is replaced by a single document.These are the largest drops among the six one-component variants; removing principle memory costs 9.0 points, and sentence-format skills cost 10.0 points.Source: §5.1 · p. 8

5.2 Effect of validation size

  • Final resolved rate on pygments rises from 80.0% with no validation to 85.0%, 92.0%, and 92.3% at validation sizes 10, 30, and 50.Most final-rate improvement occurs between 10 and 30 tasks; peak performance is nonmonotone, moving from 91.7% to 87.3%, then 93.7% and 97.0%.Source: §5.2 · p. 8

5.3 Validated skill-bank dynamics and utility

  • On pygments, the validated bank reaches 26 items after seven accepted updates by step 323, while the ungated bank accumulates 453 items by about step 400 and finishes at 80.0% versus 92.3%.The validated bank then remains fixed; the authors interpret the contrast as favoring selective retention over continual accumulation.Source: §5.3 · p. 8
  • Every item in the 26-item validated pygments bank improves resolved rate over the no-memory baseline, with gains ranging from 0.33 to 10.33 points.Items are grouped as Environment, Repair Strategy, or Code Semantics.Source: §5.3 · p. 9
  • Learned skills encode executable procedures, whereas principles capture transferable diagnostic lessons, such as restoring intended statement order instead of masking an error with an arbitrary default.Examples range from a Pygments-specific yieldtuple invariant to a general multi-edit regression workflow.Source: §5.3 · p. 9

6 Conclusion

The conclusion presents validation-gated skill-bank evolution as a way to improve code agents over long task streams, with theoretical certificates for gain and drawdown. The appendices describe the online context-policy dynamics and the deviation-radius arguments supporting those certificates.

6 Conclusion

  • Across four repositories and three backbones, VALVE reports average final and peak gains of 14.9 and 16.5 points, versus 0.9 and 7.0 without a gate, with 4.0× lower average drawdown and an 11× smaller bank.The conclusion also states that positive-margin acceptance converges after finitely many bank changes and that a disjoint evaluation set certifies final gain and long-horizon drawdown.Source: §6 · p. 9

A Proofs and Certification Details

  • The proof appendix assigns convergence, localized refinement, held-out certificates, the reused-panel bound, and holdout-size inversion to separate proof sections.Appendix A.2 establishes the deviation radius and range constants used throughout.Source: A Proofs and Certification Details · p. 13

A.1 Online dynamics of the context policy

  • The online policy selects context from strictly past experience, generates a trajectory, observes its outcome, and appends the interaction record.Because experience is endogenous, the context policy and experience distribution are coupled through the rollout process; successful evolution must improve future contexts without using future interactions.Source: §A.1 · p. 13

A.2 The deviation radius

  • The one-sided Bennett radius bounds the deviation used in the paper’s certificates under an i.i.d. sampling assumption, a variance bound, and a one-sided range bound.The appendix explains that inverting the deviation exponent yields the radius expression and identifies when a smaller effective range than 2 is admissible.Source: §A.2 · pp. 13–14

A.3 Proof of fixed-panel convergence

With a fixed validation panel and score carry-forward, accepted updates make the recorded score non-decreasing, yielding finite convergence. Under baseline-concentrated headroom, the number of accepted moves can be bounded by the observed unstable-task fraction plus a residual allowance.

A.3 Proof of fixed-panel convergence

  • Accepted moves increase the carried-forward panel score by at least ρ, while rejected moves leave it unchanged, so the score is non-decreasing and the final score is its maximum.Because the score lies in [0, 1], telescoping bounds the number of accepted moves and thus the number of distinct banks visited; the argument permits arbitrary panel reuse and history-dependent proposals.Source: §A.3 · pp. 14–15

A.4 Baseline-concentrated headroom

  • With only r baseline rollouts, the observed unstable-task fraction can underestimate population mass because low but nonzero solve probabilities may yield only failures.For r = 3, each empirically unstable task contributes 1/3 to vmass, but this does not make bh an unbiased estimate of population mass h.Source: §A.4 · p. 15
  • Under Assumption 2, the accepted-move count is bounded using the baseline-unstable panel fraction and a residual allowance for unrealizable headroom.The proof obtains Kρ ≤ bh + εloc; zero residual is an idealized case, not an assumption imposed on experiments.Source: §A.4 · p. 15
  • The baseline-rollout plug-in estimator is corrected by multiplying by r/(r − 1), giving an unbiased estimate of Ex[p(1 − p)] after averaging over tasks.This variance estimate is distinct from estimating the population mass h of baseline-unstable tasks.Source: §A.4 · p. 15

A.5 Proof of the certified gain and drawdown

A disjoint evaluation set certifies final population gain and peak-to-final drawdown for a run whose reported banks are fixed before that set is observed. The same paired evaluation principle also certifies the population-level performance difference between gated and ungated final banks.

A.5 Proof of the certified gain and drawdown

  • The final-gain certificate applies to a fixed initial/final bank pair evaluated on a disjoint holdout, yielding a high-probability lower bound on population gain.The pair is determined before the evaluation set is drawn, so the proof conditions on run randomness and requires no union bound for this comparison.Source: §A.5 · pp. 15–16
  • The peak-to-final drawdown certificate covers each distinct bank checkpoint and uses a union bound over at most A banks.Checkpoints with the same bank have identical drawdown; Theorem 1 bounds A by K + 1 accepted changes plus the initial bank.Source: §A.5 · p. 16

A.6 Certified separation between gated and ungated evolution

  • A paired holdout comparison certifies the final population-performance difference between gated and ungated runs on the same repository.The per-task contrast uses the same evaluation tasks for both runs, and the repository-average corollary extends the certificate across repositories with disjoint evaluation sets.Source: §A.6 · pp. 16–17

A.7 Proof of the reused-panel population-loss guarantee

The reused-panel guarantee controls population loss on accepted moves by enumerating possible bank-and-move pairs conditional on run randomness. The sizing rule inverts a concentration radius, and the numerical instantiation reports the resulting certificates and holdout requirements.

A.7 Proof of the reused-panel population-loss guarantee

  • The proof compresses possible run histories into a finite family of bank-and-move pairs for each acceptance count, allowing panel reuse and adaptive proposals.The family is defined without reference to the panel; conditional on other run randomness, its pairs are fixed before panel outcomes are observed.Source: §A.7 · p. 17
  • With probability at least 1 − δ, each accepted move’s population gain is at least its panel gain minus the deviation radius, and therefore at least ρ minus that radius.The guarantee is conditional on run randomness and then holds unconditionally; the acceptance rule supplies the panel-gain threshold.Source: §A.7 · pp. 17–18
  • The reused-panel proof allows dependent candidate pairs and adaptive verdict-driven proposals, but requires the gate horizon Tgate to be fixed in advance.Panel reuse induces dependence across possible pairs, handled by a union bound.Source: §A.7 · p. 18

A.8 Proof of the sizing rule

  • The sizing rule requires N ≥ (u⋆)^−2, with leading-order holdout size 2s²L/γ² as tolerance γ becomes small.Reported sizes invert the exact radius rather than its relaxation and are therefore no larger.Source: §A.8 · p. 18

A.9 Numerical instantiation

  • Figure 7 plots the holdout size required for a prescribed tolerance on logarithmic vertical axes, with reference lines for 100 evaluation tasks and 50 validation tasks.The figure presents the Corollary 1 sizing relationship and marks the panel sizes used in the runs.Source: Figure 7 · p. 19
  • At the stated numerical settings, the certificates give DD ≤ 7.5, gain ≥ +12.4, and gated-versus-ungated separation ≥ +5.0 points.The corresponding measured values are 0.92, 17.2, and 8.0 points; a 10-point drawdown tolerance requires 51 evaluation tasks, while the per-update tolerance requires 136 panel tasks.Source: §A.9 · pp. 18–19

B.1 Data construction and reference configuration

The reference protocol partitions repository tasks before adaptation and evolves a persistent memory through task-conditioned extraction, retrieval, and paired validation. Evaluation tracks final and peak performance, while the documented ablations alter method components that are sometimes coupled.

B.1 Data construction and reference configuration

  • The common reference protocol is applied across repositories, with repository selection spanning four codebases chosen for task volume and distinct forms of repository knowledge.The repositories are DeepDiff, Pygments, pydicom, and SQLFluff; each provides more than 1,000 nonempty tasks.Source: §B.1 · p. 19, Table 5 · p. 20

B.2 Rollout collection and evolution trigger

  • Each task receives three independent attempts under one frozen retrieved context, and only mixed-outcome tasks trigger contrastive extraction.All tasks are still solved and scored; a 100-step evolution budget can require observing approximately 1,000 raw tasks.Source: §B.2 · p. 20

B.3 Extract: contrastive reflection

  • Extract contrasts successful and failed trajectories from the same task to propose principles and skills, with principles expressing general reasoning strategies and skills expressing actionable procedures.The persistent bank keeps principles and skills as separate append-only memory types; malformed outputs yield an empty proposal.Source: §B.3 · pp. 20–21, §B.4 · p. 21

B.4 Persistent skill state

  • The persistent memory stores item content and provenance, merges normalized duplicates, and suppresses candidates with token-set Jaccard similarity of at least 0.45.The reference configuration does not periodically summarize or consolidate accepted items, keeping updates individually traceable.Source: §B.4 · pp. 21–22

B.5 Retrieve: task-conditioned skill composition

  • Retrieve independently ranks principles and skills using lexical overlap, semantic similarity, and an importance prior, then selects the ten highest-scoring items of each type.Selected rich bodies are injected without re-summarization, and retrieved guidance is not to override contradictory repository evidence.Source: §B.5 · p. 22

B.6 Validate: paired acceptance on executable outcomes

  • Validate compares current and candidate banks on the same fixed 50-task panel with three executable rollouts per task, accepting a joint proposal only when it clears ρ = 0.02.The panel is reused, so the threshold is an empirical margin rather than a confidence level; each condition aggregates 150 binary outcomes.Source: §B.6 · pp. 22–23

B.7 Evaluation protocol and reported statistic

  • The evaluation protocol uses a disjoint 100-task panel with three rollouts per task and reports final-checkpoint avg@3 before the trajectory peak.The peak uses the panel for checkpoint selection and is not an untouched final-test estimate; gains are relative to the shared step-0 evaluation.Source: §B.7 · p. 23

B.8 Ablation implementations and prompts; C.1 Prior work behind each ablated component

  • Ablation comparisons represent operational method variants rather than perfectly isolated component effects, because some interventions jointly change representation, control flow, or feedback.The ablation definitions are mapped to prior methods, but the documented couplings constrain causal interpretation of the differences.Source: §B.8 · pp. 23–24, Table 6 · p. 23, §C.1 · p. 24

C.2 Growth and composition of the skill bank

Validation keeps the learned bank compact as it grows, while runtime analysis reports main-run and per-step ablation costs.

C.2 Growth and composition of the skill bank

  • At step 323, the validated pygments bank has 26 items and stays fixed; the ungated bank reaches 453 items by approximately step 400.The validated bank contains 12 skills and 14 principles; despite its much larger bank, the ungated run ends at 80.0% resolved rate versus 92.3% for the validated run.Source: §C.2 · p. 24
  • 11× more compact banks result with validation: all main runs retain 204 skills and 192 principles, versus 2,422 skills and 2,024 principles without it.Table 3 extends the comparison across the main runs.Source: §C.2 · p. 24, Table 7 · p. 25

D Time and efficiency analysis

  • Runtime logs normalize component-ablation costs per evolution step because the ablations use different evolution horizons.Main model–repository runs are reported by total wall-clock time.Source: D Time and efficiency analysis · p. 25

D.1 Main experiment runtime

The runtime analysis compares total wall-clock time across main experiments and per-step time across component ablations.

D.1 Main experiment runtime

  • 122.1 hours for validated evolution, 50.6 hours for ungated evolution, and 96.1 hours for SkillOpt, averaged across twelve main runs.Table 8 excludes held-out test evaluation; MiniMax-M2.7 runtimes also reflect local inference throughput.Source: §D.1 · p. 25, Table 8 · p. 25

D.2 Ablation runtime

  • 2.41 hours per step makes the sentence-format variant the slowest reported component ablation, while evolving on all tasks is fastest at 1.14 hours per step.Table 9 reports only per-step time, omitting total runtime and evolved-step counts.Source: §D.2 · p. 26, Table 9 · p. 26

E Case study of useful generated skills

The case study examines learned skills and principles from a Claude-4.6 pygments run, showing how they encode different levels of coding knowledge and how individual items perform on a holdout.

E Case study of useful generated skills

  • On a 100-task holdout, each final-bank item is evaluated alone against the no-memory baseline, with gain measured as resolved-rate change.Each task uses three rollouts; equal step values mark items created by the same accepted update.Source: E Case study of useful generated skills · p. 26, Table 10 · p. 26
  • Skills generally encode specific executable repair procedures, while principles abstract diagnostic lessons from particular failures.The examples span a repository-specific lexer invariant and the broader lesson to restore intended data-flow order rather than mask a symptom with a default value.Source: E Case study of useful generated skills · p. 27
  • +2.00 pp is the reported gain for the code-semantics skill audit_yield_tuple_index_group_consistency.It captures the invariant that a lexer callback should take token position and value from the same regex capture group.Source: E Case study of useful generated skills · pp. 27–28
  • +10.33 pp is the reported gain for the repair-strategy skill revert_to_known_good_as_fix_strategy.The item is listed at evolved step 262.Source: E Case study of useful generated skills · pp. 27, 29
  • +3.33 pp is the reported gain for the code-semantics principle about use before assignment signaling reordered code.The principle appears at evolved step 323.Source: E Case study of useful generated skills · p. 29

Related papers

Loading 2609.32990v1…