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

AI summary

Overview

Research area: AI agents / automated software engineering — specifically self-evolving LLM agents and automated unit-test generation.

Technical level: Advanced. The paper combines quality–diversity (QD) evolutionary search, multi-armed bandit allocation, and mutation testing; the experimental protocol assumes familiarity with coverage and mutation-score metrics.

Scope (one sentence): The paper proposes TeSearch, a quality–diversity evolutionary search that generates small but highly effective Python test suites and uses them as the executable "keep-or-discard" signal for agents that rewrite their own code.

What This Paper Is About

A self-evolving agent improves itself by rewriting its own harness (the code that prompts the model, parses actions, executes them, and records trajectories), and every rewrite must be checked before it is kept. Checking by running full agent rollouts is expensive and noisy, while a repository's own tests are too weak — the authors measure them rejecting only 25.3% of rewrites that actually change behavior. The goal is to generate test suites that are simultaneously strong (catch behavioral changes) and small (cheap enough to run on every proposed rewrite), and to show that such suites make a better improvement signal than either rollouts or existing tests.

Key Contributions

1. A formalization of size-optimized unit test generation. The terminal objective is defined as delivering the smallest suite of maximal hypervolume, where hypervolume is coverage times mutation score. Rather than scalarizing quality against size, size is used as a behavior descriptor in a quality–diversity search, so quality is optimized inside each size niche and the small end of the range is never eliminated by larger suites.

2. A learned "landing kernel" for LLM actuation error. Because the search can only ask an LLM for a test count and the LLM follows that instruction imprecisely, the method models the realized size as log-normal around the requested size, with an online-estimated bias term that is compensated before each generation and a fixed spread used to spread credit across neighboring niches.

3. Size-annealing UCB allocation. A bandit over size niches whose reward is the increment in the multi-objective QD score, where the kernel's landing distribution weights expected exploitation and a size penalty sits inside the expectation (so the size a suite lands at is penalized, not the size aimed for). The penalty stays at zero until a hypervolume threshold is reached, so quality is secured before smaller suites are favored.

4. An empirical demonstration as an agent improvement signal. Across 129 real-world modules and three backbones the suites are the strongest of any method compared, and as the gate of a self-evolving agent they reject 59.9% of behavior-changing rewrites versus 25.3% for the repository's tests, at a 4.0% false-alarm rate and 3.5 s per decision.

Main Findings

• Best quality, smallest among LLM-based methods. On the 129 TestGenEval modules under an identical budget of N = 50 LLM calls per module, TeSearch reaches the highest hypervolume on every backbone: 0.916 on GPT-5.4, 0.976 on Claude Opus 4.8, and 0.908 on Gemini 3.1 Pro. The authors report this as 7.0–8.5 points above the strongest baseline. Delivered suite sizes are 38.6, 29.1, and 36.3 tests respectively — the smallest of any LLM-based method compared.

• Size as a coordinate, not an objective. Pynguin delivers fewer tests (20.4) but only hv = 0.090, and it runs on the 40 modules it supports, matched at 6000 s wall clock. The authors argue this shows small size alone is not the goal.

• Ablations separate the mechanisms. Removing the size penalty (λ = 0) costs little quality (−0.02 to −0.06 hv) but grows suites 1.5–2.9×. Removing the kernel inflates size most where the actuator overshoots most (+11.7 and +27.0 tests on Claude Opus 4.8 and Gemini 3.1 Pro). Removing UCB or the nearest-parent rule costs both quality and size on all three backbones.

• Population-based baselines isolate the formulation. OpenEvolve also keeps an archive but does not index it by size, so it has nothing small to return and delivers 51.5 tests on GPT-5.4. GEPA puts −s in the objective, admitting near-empty suites as non-dominated and leaving a front wide in size but shallow in quality.

• The actuator model holds empirically. Over 6063 TeSearch generations on GPT-5.4, the count bias δ ranges from −0.037 to +0.107 across modules and changes sign, so no fixed correction works; the log-size residuals have mean 0.013 and standard deviation 0.100.

• Allocation stays spread, not collapsed. Grouped into eight normalized size bands, no band falls below a 0.067 share of calls in any window.

• Large gains as an agent gate. On mini-swe-agent's harness, pooled over eight modules and 470 annotated revisions (217 divergent, 253 equivalent; annotator agreement κ = 0.74), TeSearch rejects 59.9% of divergent revisions versus 25.3% for repository tests, and wins on every individual module. It rejects 10 of the 253 equivalent revisions (4.0% false-alarm rate) where the repository tests reject none. A decision takes 3.5 s versus 5.9 s and calls no model.

• Largest gaps on parsing and rendering modules. The authors attribute this to mutation-optimized suites pinning details a mutant perturbs — a separator, a default, which exception surfaces — which repository tests, checking only that a module performs its function, miss.

Methodology in Plain English

The method generates a test suite for one Python module at a time, under a fixed budget of 50 LLM calls.

First, a small seed phase asks the model to write suites with no size instruction, and measures them. Those measurements set an "anchor" size (the geometric mean of the seed sizes) and, together with the module's number of public functions and methods, define a grid of size niches spaced geometrically, so consecutive niches differ by a constant ratio.

Then the search loop repeats: pick a target niche; take as parents the best suites nearest the target size on each side of it; show the model the module annotated with uncovered lines and surviving mutants, the two ordered parents (weakest first, strongest nearest the end of the prompt), and the requested test count; then measure the resulting suite and file it in whichever niche it actually lands in, not the one requested. Each niche keeps a Pareto front over (coverage, mutation score) rather than a single best suite.

Two mechanisms handle the fact that the LLM does not obey counts precisely. A kernel learns online how the model's realized size deviates from the requested one and corrects the request so it lands on the intended niche. A bandit decides which niche to aim at next, weighing expected reward (spread over niches by the kernel) against an exploration bonus, with a penalty for landing at large sizes that only switches on once a hypervolume threshold has been met — quality first, then shrinkage.

For the agent experiment, eight harness modules of mini-swe-agent are each revised 64 times by GPT-5.4 under paired intents, where each behavior-changing intent is the failure mode of a behavior-preserving one with the same goal and shape of edit. Human annotators label each revision divergent or equivalent, and a gate rejects a revision whenever the suite fails on it while passing on the unmodified module.

Why This Matters

The paper reframes a neglected knob: self-improving agents are usually judged by what they change, but the check that decides whether a change survives determines what the agent can learn. Treating test-suite construction as an optimization problem — with size as a first-class search coordinate and cost measured in seconds per decision — gives self-evolving loops a signal that is both stricter and cheaper than the status quo, and it names a concrete failure mode of "just use the repo's tests": those tests were written before the agent existed and anticipate none of its edits.

Real-world applications:

• Coding agents and IDE assistants (the paper cites Cursor, Codex and Claude Code as systems that lean on tests across whole repositories) could generate a compact gate suite per module before accepting a self-edit.
• CI and regression testing for legacy repositories, where the same machinery produces small, high-mutation-score suites rather than whatever size a generator happens to emit.
• Agent self-improvement pipelines that rewrite prompts, parsers, or scaffolding and need a cheap per-rewrite accept/reject decision instead of spending an episode on each candidate.
• Test-suite maintenance, since the size-indexed archive yields suites at many sizes, offering a principled alternative to post-hoc test-suite reduction.

Industry relevance: the decision cost (3.5 s, no model call) is small enough to sit inside a rewrite loop, and the method needs only a containerized module plus mutants, both of which most Python repositories can produce with existing tooling.

Future Directions

• Beyond Python and beyond TestGenEval. The evaluation covers 129 Python modules from one benchmark; whether the landing kernel and niche grid transfer to other languages, where test scaffolding and mutation tooling differ, is untested here.
• Reducing the 4.0% false-alarm rate. TeSearch rejects 10 of 253 behavior-preserving revisions where repository tests reject none; how much this costs a self-evolving loop in stalled evolution is not measured.
• Descriptor choice. Size is the only descriptor. Coverage gaps, module role, or runtime could be added as further behavior descriptors, but the paper does not test multi-descriptor archives.
• Comparison against rollout-based acceptance on the same budget. The paper argues rollout is expensive and subjective and cites a 3.5 s versus 5.9 s wall-clock gap against repository tests, but does not report a head-to-head acceptance-quality comparison with rollout gating.

Target Audience

Researchers and engineers working on self-improving LLM agents, automated test generation, or search-based software engineering. It is most useful to readers already comfortable with coverage and mutation testing and with evolutionary or bandit-based optimization; practitioners building agent harnesses will find the improvement-signal framing and the cost numbers directly actionable, while newcomers will need background in quality–diversity search to follow the method section.

Authors’ abstract

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.