PaperlayerView exact revision on arXiv

Source-linked AI summary

Which Self-Improvements Should We Trust? Reliable Self-Improvement When Agents Reuse Their Benchmarks

Xiaojing Sun, Yuhan Zeng, Zihua She, Xiao Wang

arXiv:2609.33180v2stat.MLcs.AIcs.LGstat.ME

TL;DR

Reusing a fixed evaluation set can make adaptive self-improvement candidates overfit its feedback, while standard multiple-comparison methods assume candidates are independent of that set. REUSE limits feedback to promotion decisions and allocates error across possible histories; experiments report fewer false promotions while maintaining population performance near the best baselines.

  • Problem

    Repeated benchmark reuse makes later candidates depend on earlier evaluation outcomes, a form of adaptive dependence not controlled by methods that assume candidates are chosen independently of the evaluation set.

    Source: §1 · p. 2

  • Method

    REUSE returns only promotion decisions to the search process and allocates a global error budget across possible decision histories and candidate comparisons.

    Source: §1 · pp. 2–3

  • Results

    False promotions fell from up to 20.7% to 0%, while final true population performance stayed within 0.04 percentage points of the best baselines.

    Source: §1 · p. 3

  • Takeaways & Limitations

    REUSE provides a simultaneous guarantee that every promoted modification is a true population improvement without restricting the proposer or agent architecture.

    Source: §5 · p. 9

    The guarantee assumes an evaluation set independent of the proposer’s randomness, development data, and initial system, with influence on the search only through promotion decisions.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

As recursive self-improvement (RSI) rapidly advances, reliable evaluation becomes critical for guiding adaptive search. RSI typically relies on finite evaluation resources, such as fixed benchmarks, to determine which modifications are retained and what is proposed next. However, when these finite resources are repeatedly reused, new candidates are proposed based on feedback from the same evaluation set, so the search trajectory can adaptively overfit and empirical improvement may not reflect genuine population improvement on the underlying task distribution. Some existing methods account for multiple comparisons but assume that candidates are chosen independently of the evaluation set, and therefore do not control this adaptive dependence. To address this, we propose REUSE (Risk-controlled Evaluation Under Sequential Evolution), a certified evaluation and promotion framework that allows a fixed evaluation set to support repeated adaptive decisions while providing statistical guarantees. For a user-specified error level $\alpha$, with probability at least $1-\alpha$, every promoted modification is a genuine population improvement on the underlying task distribution. REUSE achieves this by strictly limiting the evaluation feedback returned to the search process and accounting for possible promotion histories within the error budget. We develop detailed statistical theory for RSI evaluation in this setting, including simultaneous error control, valid lower bounds on cumulative improvement, and a characterization of the fundamental limits of adaptive evaluation reuse. In live self-improvement experiments, REUSE commits substantially fewer false promotions than evaluation frameworks from current RSI systems and error-controlled baselines, reducing the proportion of false promotions from up to 20.7% to 0%, while achieving final true population performance comparable to the best baselines.

1 INTRODUCTION

Reusing fixed benchmarks in adaptive self-improvement can make measured gains reflect adaptation to those benchmarks rather than genuine population improvement. REUSE limits evaluation feedback and accounts for possible decision histories to provide guarantees while retaining progress.

1 INTRODUCTION

  • False promotions can arise from within-round selection, repeated testing, and adaptive dependence when later candidates respond to earlier evaluation outcomes.Standard multiple-comparison corrections address the first two sources but assume candidates are independent of the evaluation data, leaving adaptive dependence unaddressed.Source: §1 · pp. 1–2
  • REUSE returns only promotion decisions to the search process and accounts for possible decision histories in its global error budget.For user-specified α, it guarantees with probability at least 1 − α that every promoted modification is a genuine population improvement.Source: §1 · pp. 2–3
  • False promotions fell from up to 20.7% to 0%, while final true population performance stayed within 0.04 percentage points of the best baselines.The experiments compare REUSE with current RSI evaluation frameworks and error-controlled baselines.Source: §1 · p. 3

2 METHODOLOGY AND THEORETICAL GUARANTEES

REUSE evaluates adaptive candidates on a reused, independent evaluation set while restricting the search process to decision-only feedback. It allocates error across possible comparisons and histories to guarantee valid promotions and cumulative improvement, while characterizing the threshold needed for reliable detection.

2.1 SETTING AND OBJECTIVE

  • The evaluation set must be independent of the proposer’s randomness, development data, and initial system, and may affect candidates only through earlier promotion decisions.The proposer is otherwise unrestricted, and the framework assumes measurability of candidate scoring.Source: §2.1 · p. 4

2.2 REUSE

  • REUSE tests candidates against the incumbent using paired evaluation and returns only the promotion decision; it can also certify cumulative progress with a running lower-bound certificate.The certificate is kept for auditing and is not returned to the proposer.Source: §2.2 · pp. 4–5
  • For a fixed history, REUSE uses a paired sign test to assess whether a candidate improves on the incumbent, with finite-sample validity established for the test.When multiple candidates pass, it promotes the one with the largest empirical improvement.Source: §2.2 · pp. 4–5
  • The error allocation covers repeated rounds, within-round candidate selection, and adaptive dependence by distributing the global budget across rounds, candidates, and possible histories.The history factor accounts for the possible decision histories that determine candidates and incumbents.Source: §2.2 · p. 5
  • With probability at least 1 − α, every promoted candidate has positive population improvement, and the cumulative certificate is a valid lower bound on improvement from the initial system.These guarantees apply to pass/fail evaluation under the stated assumptions and REUSE’s error allocation.Source: §2.2 · p. 5
  • Reliable detection requires larger true improvements as the evaluation set shrinks or the allocated error level tightens; the threshold also grows with the search history.For the stated threshold-rule class, comparable first-order growth in the promotion threshold is necessary to prevent eventual false promotion.Source: §2.2 · p. 6

3 EXPERIMENTS

The experiments test whether REUSE can limit false promotions under repeated benchmark reuse without sacrificing population improvement. On Covertype, REUSE makes no false promotions while matching the strongest methods' final population improvement.

3.1 EXPERIMENTAL SETUP

  • The study used Covertype classification, 200 rounds, and 30 seeds at each reused evaluation-set size of 2,000 or 10,000.Candidates were generated by Qwen2.5-7B-Instruct, with up to eight modifications per round.Source: §3.1 · p. 6
  • The comparison included benchmark-driven search methods and statistical-control baselines, with population improvement measured on held-out H.False promotions counted updates with non-positive held-out population improvement; the optimism gap compared improvement on reused S with improvement on H.Source: §3.1 · pp. 6–7, Table 1 · p. 7

3.2 RESULTS

  • 7.02 pp at n = 2,000 and 7.19 pp at n = 10,000: REUSE's final population improvement came with no false promotions.Its optimism gap stayed within one standard error of zero at both evaluation-set sizes.Source: Table 1 · p. 7, §3.2 · p. 8
  • REUSE's promotions were all strictly positive, while competing methods showed false promotions and Bonferroni-style made very few promotions.Figure 3 plots each promotion's population improvement; red triangles mark false promotions.Source: §3.2 · p. 8, Figure 3 · p. 8

4 RELATED WORK

Prior work addresses statistical control in self-improvement and adaptive holdout reuse, but the paper identifies a gap when candidates adapt to earlier outcomes on the same evaluation data. REUSE addresses this by restricting feedback and allocating error across possible decision histories.

Recursive self-improvement and statistical control

  • Existing self-improvement controls use global error budgets, sequential testing, or sealed audits, but often assume test-independent candidates or fail to account for information revealed by promotion decisions.REUSE combines decision-only feedback with error allocation over all possible decision histories.Source: §4 · p. 9

Adaptive data analysis and holdout reuse

  • Adaptive data-analysis methods bound information leakage or bias, while REUSE turns decision-history accounting into exact finite-sample tests for each promotion.The discussion covers differential privacy, description length, leaderboard mechanisms, and information-theoretic bounds.Source: §4 · p. 9

Multiple testing and sequential inference

  • Classical, weighted, sequential, and selective-inference procedures generally assume fixed hypotheses, fresh data, or characterizable selection, unlike arbitrary proposers adapting to the same data.REUSE allocates an error budget over possible decision histories to ensure finite-sample test validity.Source: §4 · p. 9

5 DISCUSSION

The discussion presents REUSE as a way to control false promotions during long searches that reuse an evaluation set, while noting that the experiments cover only machine-learning classification. The appendices provide a paired lower confidence bound for bounded scores and establish validity of the exact paired sign test.

5 DISCUSSION

  • REUSE controls false promotions under benchmark reuse without restricting the proposer or agent architecture, but experiments demonstrate it only on machine-learning classification.The paper identifies larger agentic settings, richer feedback, refreshed evaluation sets, and control of secondary metrics as future directions.Source: §5 · p. 9

A.1 A PAIRED LOWER CONFIDENCE BOUND FOR BOUNDED SCORES

  • The paired lower confidence bound applies to bounded paired differences, supporting non-binary scores and serving as one component of the pass/fail certificate.The bound uses a data-dependent variance proxy that upper-bounds the variance.Source: §A.1 · p. 14

A.2 VALIDITY OF THE EXACT PAIRED SIGN TEST

  • The exact paired sign test controls rejection probability when the paired differences are i.i.d. in {-1, 0, +1} with nonpositive mean.The validity inequality also holds conditionally on every value of M.Source: §A.2 · p. 15

A.3 A LOWER CONFIDENCE BOUND FOR PASS/FAIL EVALUATION

This section develops a lower confidence bound for pass/fail evaluation by combining exact bounds on discordance and conditional success rates. It also explains how REUSE incorporates the bound into its running cumulative estimate.

A.3 A LOWER CONFIDENCE BOUND FOR PASS/FAIL EVALUATION

  • For pass/fail evaluation of i.i.d. outcomes Z1, …, Zn ∈ {−1, 0, +1} with mean μ, the lower confidence bound combines an exact bound with the bounded-score lower confidence bound from Lemma A1.Source: §A.3 · p. 16
  • Conditional on the number of non-tied outcomes, the positive-outcome count is binomial; a separate binomial bound covers the non-tie probability.The two coverage arguments are applied separately to the conditional success rate and the non-tie count.Source: §A.3 · pp. 15–16
  • For γ = 0, REUSE adds max{ℓ⋆, 0} to the running bound, keeping it nondecreasing while preserving its lower-bound interpretation.For bounded scores, promotion instead requires ℓ > γ ≥ 0 and contributes ℓ.Source: §A.3 · p. 16

A.4 PROOF OF THE MAIN GUARANTEE

This appendix establishes the main guarantee through auxiliary results for probe selection and calibration, simultaneous validity of adaptive comparisons and cumulative-progress bounds, and analyses of direct progress bounds and test power. It also characterizes limits of threshold-based promotion, including a bounded-score lower-bound construction in which repeated testing lets population-neutral candidates defeat sufficiently low thresholds.

A.4 PROOF OF THE MAIN GUARANTEE

  • With probability at least 1 − α, every comparison across all possible decision histories is valid simultaneously, so promoted candidates are genuine improvements and cumulative progress has a valid lower bound.The proof conditions on the search randomness, development data, and starting system, then integrates the bound to obtain the unconditional guarantee.Source: §A.4 · p. 18

A.5 A DIRECT LOWER BOUND AGAINST THE STARTING SYSTEM

  • With probability at least 1 − αc, the direct bound Dt lower-bounds V(At) − V(A0) for every round t.Under development-set screening, the history-count factor Kp is removed; the joint statement combines this proposition with Theorem 1’s events.Source: §A.5 · p. 19
  • When several promotions accumulate, the direct bound can be substantially tighter than the running bound, but neither dominates in every configuration.The direct bound pays one confidence margin for the comparison with A0, while the running bound adds a margin for each promoted step; the direct bound need only be recomputed after a promotion.Source: §A.5 · pp. 19–20

A.6 POWER AND THE MINIMUM DETECTABLE IMPROVEMENT

  • For fixed comparisons, the Bernstein–KL test has sufficient conditions for passing with probability at least 1 − β, including a pass/fail specialization based on the discordance rate d.The stated power analysis applies to comparisons fixed independently of the evaluation set, not conditionally on an adaptive run reaching them.Source: §A.6 · p. 20
  • For the exact paired sign test with γ = 0 and ρ = 1/2, the appendix characterizes promotion and gives a sufficient condition in terms of M and L.The sufficient condition is stated for M ≥ 1; when M = 0, the test cannot pass.Source: §A.6 · pp. 20–22

A.7 LOWER BOUND FOR THRESHOLD-BASED PROMOTION RULES

  • The lower-bound construction uses a bounded-score model that satisfies Assumptions 1 and 2, showing that promotion-history dependence also limits a natural class of promotion rules.Source: §A.7 · p. 23

A.7.1 MODEL AND THRESHOLD GATES

  • Threshold-gate proposers can cause a false promotion with probability tending to one when thresholds fall below the stated first-order scales before the first promotion or after P promotions.The post-promotion regime requires the theorem’s stated asymptotic conditions, including t = ⌊ςP⌋ + 1, ς ≥ 5, and P → ∞.Source: §A.7.1 · p. 24

A.7.2 AUXILIARY LEMMAS

  • Auxiliary lemmas establish monotonicity properties of binomial point-mass ratios used in the lower-bound analysis.Source: §A.7.2 · pp. 24–25
  • Lemma A5 establishes a uniform second-moment result for selected probes drawn from independent Rademacher variables.The supplied passage gives the lemma’s setup but not the bound itself.Source: §A.7.2 · p. 26
  • Lemma A6 establishes that the calibration function increases strictly with x and, for interior x, continuously and strictly with r.It also gives a cutoff result on the grid Λn.Source: §A.7.2 · pp. 26–27

A.7.3 THE COST OF REPEATED CANDIDATE TESTING

  • Theorem A2 shows that neutral candidates can defeat thresholds below ln(tK), producing false promotions despite zero population gain.When a probe exceeds the stated cutoff, it forces a promotion; every such promotion is false because each candidate is population neutral.Source: §A.7.3 · pp. 27–28

A.7.4 THE COST OF PROMOTION HISTORY

This section characterizes the cost of promotion history for threshold-gate evaluation. It gives a decision-only proposer that can induce false promotion under stated threshold conditions and compares the history-dependent rate with REUSE’s.

A.7.4 THE COST OF PROMOTION HISTORY

  • The proposer uses previous promotion decisions to identify favored probe directions, then combines selected neutral probes into a zero-gain final candidate.Neutral-probe promotions are already false, while the final candidate has zero population gain.Source: §A.7.4 · pp. 28–29
  • A decision-only proposer can cause a false promotion within O(P) rounds with probability tending to one under the stated conditions.The lower bound applies to the threshold-gate class, not to every pass/fail promotion rule; REUSE’s exact test is not literally in that class.Source: §A.7.4 · p. 32
  • The history-dependent rates for REUSE and the lower bound agree to first order as Kς grows, when comparing the history term alone.The comparison excludes additional time- and error-level terms.Source: §A.7.4 · p. 32
  • The lower-bound threshold conditions apply over stated ranges of rounds; they do not require every individual threshold to exceed the stated rate.The result is scoped to the threshold-gate class and its stated assumptions.Source: §A.7.4 · p. 32

B EXPERIMENTAL DETAILS

The appendix outlines the live-experiment protocol and proposer prompts. The shared setup uses a fixed data partition and gives the proposer different feedback depending on the method.

B EXPERIMENTAL DETAILS

B.1 PROTOCOL

  • Each Covertype seed draws an evaluation set S from E, with the 2,000-example set nested within that seed’s 10,000-example set.Source: §B.1 · p. 33

B.2 PROPOSER AND PROMPT TEMPLATES

  • The proposer receives the parent configuration, development-set accuracy and slice error rates, and the previous ten rounds of search history.Source: §B.2 · p. 33
  • Only REUSE withholds evaluation accuracies on S, so its proposer learns about S solely through promotion decisions.Source: Table 3 · p. 34

B.3 COMPARED METHODS

The live experiments compare methods that share the proposer, candidate space, and training data but differ in parent selection and promotion rules.

B.3 COMPARED METHODS

  • All compared methods share the proposer, candidate space, and Dtr, while differing in parent selection and promotion rule.Source: §B.3 · p. 34
  • Empirical best-of-K promotes the candidate with the largest strictly positive evaluation-set gain; the five archive-search methods share this promotion rule.Source: §B.3 · pp. 34–35
  • DGM-style selects archive members as parents with probability proportional to a score involving evaluation accuracy, parent counts, and a logistic function.Source: §B.3 · p. 35
  • PACE-style tests every candidate at level 0.05, while Bonferroni-style uses 0.05/(TK) = 0.05/1600; if several pass, the largest-gain candidate is promoted.Source: §B.3 · p. 35

B.4 ADDITIONAL RESULTS

Additional tables report seed-matched final-improvement differences and promotion-level worst cases, alongside sensitivity summaries for REUSE’s allocation choices.

B.4 ADDITIONAL RESULTS

  • Table 5 reports seed-matched differences in final population improvement and the smallest population improvement among each method’s promotions.Source: §B.4 · p. 35
  • Table 6 varies one of the split ρ or allocation weights wt or vp at a time from the default across 10 new seeds at n = 2,000.Source: Table 6 · p. 36
  • Table 6 reports means and standard errors for S tests, promotions, population improvement, and CT, plus false/all promotions and seed-matched differences.Source: Table 6 · p. 36

B.4.1 ROBUSTNESS AND ABLATIONS

Robustness experiments test REUSE under alternative allocation choices and search mechanics, and an ablation isolates the test on S. Across these settings, the reported results show no false promotions for the tested REUSE variants.

B.4.1 ROBUSTNESS AND ABLATIONS

  • 0 false promotions occurred among 317 promotions across 11 allocation configurations, while final population improvement remained stable and within natural proposer variation.Source: §B.4.1 · p. 36
  • The alternative REUSE variant made no false promotions across 30 seeds at either evaluation-set size, with 30 positive promotions at n = 2,000 and 100 at n = 10,000.Source: §B.4.1 · p. 36, Table 7 · p. 37
  • REUSE rejected all 9 tested candidates with population improvement at most zero and made no false promotion among 47 accepted updates.Source: §B.4.1 · p. 36, Figure 4 · p. 37
  • Without the test on S, the process made 6 false promotions across 5 of 10 runs, with population improvement falling to −0.56 pp.Source: §B.4.1 · p. 36, Figure 4 · p. 37

B.4.2 PER-SEED RESULTS

The per-seed tables report final population improvement alongside false and total promotions, while the appendix also examines trajectories, promotion counts, final performance, and cumulative-improvement certificates.

B.4.2 PER-SEED RESULTS

  • At n = 2,000 and n = 10,000, the per-seed tables report each method’s held-out population improvement alongside its false and total promotions.They also provide the mean improvement and total promotion counts across seeds.Source: §B.4.2 · p. 37, Table 8 · p. 38, Table 9 · p. 39

B.4.3 TRAJECTORIES

  • Figure 5 shows mean population improvement over A0 by round, with separate panels by method and standard-error bands across 30 seeds.Dashed lines use n = 2,000 and solid lines use n = 10,000.Source: Figure 5 · p. 40, §B.4.3 · p. 40

B.4.5 CERTIFICATES

  • The direct certificate exceeds the running certificate in all 60 runs, and none of the 274 per-promotion lower bounds entering the running certificate exceeds its promotion’s population improvement.The direct certificate uses one confidence margin for the whole trajectory, whereas the running certificate pays one per promotion.Source: §B.4.5 · p. 40, Table 10 · p. 41

B.4.4 PROMOTIONS AND FINAL PERFORMANCE

  • REUSE reaches final population improvement comparable to Empirical best-of-K with fewer median promotions: 3 versus 13 at n = 2,000 and 6 versus 14 at n = 10,000.No run of the seven compared methods improves on A0 by more than 7.44 pp, while four REUSE runs at n = 2,000 and two at n = 10,000 improve by 9.08 to 10.80 pp.Source: §B.4.4 · p. 40, Figure 6 · p. 41

Related papers

Loading 2609.33180v2…