PaperlayerView exact revision on arXiv

Source-linked AI summary

Small but Mighty: Test Suites as Improvement Signals for Self-Evolving Agents

Yutong Cheng, Wei Cheng, Wenchao Yu, Dawei Zhou, Haifeng Chen

arXiv:2610.15964v1cs.AIcs.SE

TL;DR

Self-evolving agents need to decide whether harness rewrites preserve accepted behavior, but repository tests catch only a minority of behavior-changing edits. TESEARCH searches for small, strong suites with quality–diversity evolution and an online kernel that models imprecise size requests. Across 129 modules and three backbones, its suites lead the compared methods, and as an agent signal they reject more behavior-changing rewrites than repository tests.

  • Problem

    Repository tests reject only 25.3% of behavior-changing rewrites, while rollout-based evaluation spends an agent episode per candidate on a noisy end-to-end score.

    Source: §1 · p. 1

  • Method

    TESEARCH uses quality–diversity search over suite-size niches and learns an online landing kernel to model the LLM’s imprecise control of size.

    Source: §1 · pp. 1–2

  • Results

    Across 129 modules and three backbones, TESEARCH produces the strongest suites of compared methods; as an agent signal, it rejects 59.9% of behavior-changing revisions versus 25.3% for repository tests.

    Source: §6 · p. 5, §5.3 · p. 5

  • Takeaways & Limitations

    The signal takes 3.5 s per decision and calls no model, so it can be run on every proposed rewrite.

    Source: §5.3 · p. 5

Abstract

from arXiv · show

A self-evolving agent rewrites its own harness and must decide which rewrites to keep, so its improvement signal is the check a rewrite has to pass. Verifying a rewrite by agent rollout is expensive and subjective, while executable checks such as the repository's own tests are too sparse to catch behavior-changing rewrites, rejecting only a quarter of them. We instead take test feedback as the executable signal, and search for test suites that are both small and strong with a quality-diversity evolutionary algorithm, so that the signal is dense and informative. TeSearch treats suite size as a behavior descriptor, so that quality is pursued at every size and a small, strong suite is reachable, and learns a transition kernel during the search that denoises the LLM as an actuator on that descriptor. Across 129 real-world modules and three backbones, TeSearch delivers the highest-quality suites of any method compared, LLM-driven evolutionary search included, and the smallest of any LLM-based one. Used as the improvement signal of a self-evolving agent, it rejects 59.9% of behavior-changing rewrites against 25.3% for the repository's tests, at a 4.0% false-alarm rate and 3.5 s per decision. The code and data are available at https://github.com/ccsnow127/TeSearch.

1 Introduction

Self-evolving agents rewrite their harness, so the check used to keep or reject each rewrite becomes their improvement signal. TESEARCH searches for small, strong test suites to make that signal more effective and efficient.

1 Introduction

  • Repository tests reject only 25.3% of behavior-changing rewrites, while rollout-based evaluation costs an agent episode and gives a noisy end-to-end score.A generated suite must be effective at catching behavioral changes and efficient to run and interpret on every proposed rewrite.Source: §1 · p. 1
  • Size defines where suites compete in the quality–diversity search, keeping small suites viable instead of letting larger suites eliminate them.Quality determines which suites win within each size niche.Source: §1 · p. 1
  • Because an LLM follows a requested test count imprecisely, the target niche and the suite’s eventual niche can differ.TESEARCH learns an online landing kernel and allocates calls across niches using size-annealing UCB.Source: §1 · p. 2
  • TESEARCH’s suites are strongest across 129 modules and three backbones, and as an agent signal reject more than twice as many behavior-changing rewrites as repository tests.The search uses a quality–diversity formulation and an online landing kernel to account for the LLM’s imprecise control of suite size.Source: §1 · p. 2

2 Related work

Related work spans several ways to improve agents and search for tests, but generally takes the test signal as given or does not control suite size during generation. TESEARCH instead optimizes the test signal and models requested size as an uncertain action.

2 Related work

  • Self-improvement ranges from weight-space updates [56] to context-space edits, including agents that rewrite their own code [17] [34] [65].Keep-or-discard signals include model judgment [6] [63] and external tests [7] [9], compilers [20] [29], or environments [36].Source: §2 · p. 2
  • Repository and ad hoc tests are used as agent signals, but prior work takes them as given rather than optimizing their strength and cost.TESEARCH optimizes the test signal for loops that run it on every rewrite.Source: §2 · p. 2
  • QD search preserves quality across behavior-descriptor regions [15], whereas test-generation and reduction methods do not control suite size during generation [35].Unlike classical QD, TESEARCH must request a size from the LLM before observing the resulting suite size.Source: §2 · p. 2

3 Size-optimized test generation

The objective is to deliver the smallest suite among those with maximal hypervolume, where suite quality reflects both coverage and mutation score. TESEARCH uses size as a quality–diversity descriptor and searches through niches despite imprecise LLM control of suite size.

3 Size-optimized test generation

  • The terminal objective is to deliver the smallest suite with maximal hypervolume, with hypervolume defined as coverage multiplied by mutation score.A suite’s coverage is the fraction of executable lines run; its mutation score is the fraction of a fixed mutant sample killed.Source: §3 · p. 2
  • Each size niche keeps a Pareto front over coverage and mutation score, using size as the behavior descriptor rather than a scalarized objective.This lets quality be optimized independently within size niches, rather than allowing larger suites to dominate a global competition.Source: §3 · p. 2
  • Suites are grouped into geometric size niches over module-specific boundaries, with the outermost bins open-ended.The lower bound is the module’s count of public functions and methods; geometric bins reflect increasing variation in generated size as requested size grows.Source: §3 · p. 2
  • Each iteration selects a target niche, chooses nearby front suites as parents, prompts the LLM with module feedback and target size, then files the suite where it lands.The landing size error updates the transition kernel.Source: §3 · pp. 2–3, Figure 1 · p. 3

4 TESEARCH

TeSearch models test-size requests as noisy actuation and learns where generated suites land. Its size-annealing UCB allocates search effort across niches, favoring smaller landed suites only after quality is secured.

The landing kernel

  • The landing kernel models suite size in log space, with systematic count bias and residual spread shaping the probability of landing outside the requested niche.The bias is estimated online and compensated before generation; the spread is held at its holdout median.Source: §4 · p. 3

Size-annealing UCB

  • Each call’s QD-score increment is credited to the niche where its suite actually lands, and the online LMS delta rule updates count bias from the log-size residual.The acquisition weights expected rewards by the landing distribution and includes an exploration term.Source: §4 · p. 3
  • The size penalty applies to expected landed size and stays zero until the best hypervolume reaches threshold H, so search secures quality before favoring smaller suites.This ordering follows the terminal objective of delivering the smallest suite of maximal hypervolume.Source: §4 · p. 3

5 Experiments

Across 129 modules and three backbones, TeSearch produced the strongest suites overall and the smallest among LLM-based methods. In the self-revision experiment, it rejected more behavior-changing edits than repository tests, with a low false-alarm rate and short decision time.

5.1 Setup

  • Across 129 TestGenEval modules, methods received 50 calls per module on three backbones, with Pynguin wall-clock matched and search, LLM, coding-agent, and ablation baselines.Ablations removed the kernel, UCB, nearest-parent selection, or size penalty.Source: §5.1 · p. 4

5.2 Test-suite quality

  • 7.0–8.5 points above the strongest baseline, TeSearch achieved the highest hypervolume on every backbone and delivered the smallest suites among LLM-based methods.Pynguin delivered fewer tests but had hv = 0.090; size was ranked separately from quality.Source: §5.2 · p. 4
  • Removing λ reduced hypervolume by 0.02–0.06 but grew suites 1.5–2.9×; removing the kernel added 11.7 and 27.0 tests on Claude Opus 4.8 and Gemini 3.1 Pro.Removing UCB or nearest parents also cost quality and size on all three backbones.Source: §5.2 · p. 4

5.3 Improvement signal for a self-evolving agent

  • 59.9% of divergent revisions were rejected by TeSearch versus 25.3% by repository tests, with 4.0% false alarms and 3.5 s per decision versus 5.9 s.The test-suite decision calls no model, while rollout acceptance spends an agent episode.Source: Table 2 · p. 5, §5.3 · p. 5

5.2 Test-suite quality

  • Over 6063 GPT-5.4 generations, online log-size residuals averaged 0.013 with standard deviation 0.100, and only the quality-gated ramp finished both highest in quality and smallest in size.The count bias ranged from −0.037 to +0.107 across modules and changed sign.Source: §5.2 · p. 5

5.3 Improvement signal for a self-evolving agent

  • Eight mini-swe-agent harness modules were revised by GPT-5.4 with preserving or behavior-changing intents; two annotators labeled 470 revisions as divergent or equivalent.The revisions were paired by goal and shape of edit; annotator agreement was κ = 0.74.Source: §5.3 · p. 5

6 Conclusion

The paper addresses how self-evolving agents can check whether harness edits preserve behavior. It proposes size-aware quality-diversity search for test suites and reports stronger suites and better rewrite detection than existing checks.

6 Conclusion

  • Self-evolving agents can rewrite their harness but lack a way to tell whether an edit leaves existing behavior intact.The paper frames that uncertainty as the improvement-signal problem.Source: §6 · p. 5
  • TeSearch uses suite size as a behavior descriptor in quality-diversity search and learns a transition kernel to model the LLM’s noisy size control.This keeps quality in play across suite sizes and makes small, strong suites reachable.Source: §6 · p. 5
  • Across 129 modules and three backbones, TeSearch delivered the strongest suites overall and the smallest among LLM-based methods, while rejecting 59.9% of behavior-changing rewrites versus 25.3% for repository tests.It made each decision in 3.5 s with no model call.Source: §6 · p. 5

A The size-niched grid

The size-niched grid partitions suite sizes on a logarithmic scale to reflect multiplicative variation. It is anchored to unhinted seed suites and bounded using module size and a size limit.

A The size-niched grid

  • The grid is centered on the geometric mean size of unhinted seed suites, which measures the backbone's default output size.The grid is built after the seed phase because suite-size noise is multiplicative.Source: A The size-niched grid · p. 9
  • Suite-size niches are geometric, with equal width on the log scale and adjacent centers separated by a factor of 1.22.With a modeled landing spread of σ = 0.10, an aimed draw lands in its target niche with 68% probability under the model.Source: A The size-niched grid · p. 9
  • The grid spans from the module's number of public functions and methods to four niches above the anchor, limiting unbounded suite growth.The lower bound also guards against suites that pack several checks into one test method; suites outside the grid are filed in overflow niches rather than dropped.Source: A The size-niched grid · pp. 9–10
  • After measuring seed suites, TESEARCH derives the grid boundaries, re-files the archive, and replays seed landings before allocating calls among niches.Overflow niches are not targeted, but calls that land there are still charged to the niche they aimed at.Source: A The size-niched grid · p. 10
  • The search returns the smallest-written suite among those with maximal hypervolume.Each measured suite is filed in the niche matching its written size, and its reward is the clipped increment in MOQD.Source: A The size-niched grid · p. 10

B The search loop

Algorithm 1 states the complete method.

B The search loop

C Parent selection and context assembly

TESEARCH selects globally available Pareto-front parents near the target size, orders them to guide improvement, and prompts the LLM with execution feedback and a size-specific task.

D Prompt construction

C Parent selection and context assembly

  • For each target, TESEARCH selects the nearest Pareto-front suite on each side in log size from the global archive, so even an empty target niche can be bred.If one side has no suite, parents come from the other side alone; the call must then compress or expand toward the target while raising hypervolume.Source: C Parent selection and context assembly · pp. 10–11
  • Parents and target are ordered by hypervolume first and smaller size second, with the target last; Table 3's comparison note reports both measured changes.Table 4 specifies the asymmetric target: compressing to the target requires no lower hypervolume, while expanding requires strictly higher hypervolume.Source: Table 3 · p. 11, C Parent selection and context assembly · p. 11, Table 4 · p. 12

D Prompt construction

  • For compression, the LLM is asked to reduce the strongest shown suite while preserving or improving its hypervolume; for extension, added tests must raise hypervolume.The prompts direct the model to retain strong exact-value assertions, repair useful failing tests, and avoid redundant padding.Source: D Prompt construction · pp. 12–13

E Revision intents and examples

The revision-intent experiment pairs behavior-changing edits with behavior-preserving intents of the same goal and edit shape, and provides examples of both outcomes.

E Revision intents and examples

  • The experiment revises eight mini-swe-agent harness modules using intents drawn from common self-improvement goals, including latency, tokens, robustness, and structure.Each module receives 64 revisions; behavior-changing intents are paired with preserving intents of the same goal and edit shape.Source: E Revision intents and examples · p. 13
  • Table 5 distinguishes the requested intent from the revision's actual behavior; only human-verified revisions that realize the intent enter the results.Intent pairs share a goal and edit shape, with the changing intent expressing the preserving intent's failure mode; counts pool revisions across eight modules.Source: Table 5 · p. 14
  • Table 6 gives examples of equivalent and divergent revisions, including their intent and content, for six of the eight harness modules.Source: Table 6 · p. 15

F Additional related work

Vertical agents evolve by streaming, managing, and retrieving domain knowledge. This paper focuses on test suites as executable signals for deciding which software revisions to keep.

F Additional related work

  • Vertical-agent knowledge evolves through streaming, management, and retrieval, with examples including threat-report knowledge graphs [10], agent-native CTI scaffolds [13], and retrieval over heterogeneous CTI sources [14].Other examples include user-adaptive parsing of hybrid system logs [59], natural-language translation into first-order logic [46], repository-specific coding playbooks, and recursively refined behavioral specifications [11].Source: F Additional related work · p. 16
  • Knowledge graphs, corpora, and parsers are typically judged once by extraction or answer accuracy, while specifications and documentation are judged by tests taken as given.The passage frames a domain-grounded signal for deciding which knowledge revisions to keep as important to vertical-agent evolution.Source: F Additional related work · p. 16
  • The paper searches for a software test suite that is strong enough to catch behavior-changing revisions yet small enough to run on every revision, including harness changes.The passage notes that the scope includes documentation and specifications as well as an agent’s own harness (§5.3).Source: F Additional related work · p. 16

Related papers

Loading 2610.15964v1…