Summary (Overview)

• Core Problem: The paper addresses a critical statistical flaw in recursive self-improvement (RSI) systems that reuse a fixed evaluation benchmark across many rounds of adaptive search. When candidates are proposed based on feedback from the same evaluation set, the search trajectory can adaptively overfit, making empirical improvements misleading and leading to false promotions that do not generalize to the underlying population distribution.

• Key Contribution: The authors 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 rigorous statistical guarantees. For a user-specified error level α, with probability at least 1−α, every promoted modification is a genuine population improvement.

• Three Sources of False Promotions Addressed: REUSE jointly controls (1) within-round selection bias (selecting the best of K candidates), (2) repeated testing across rounds, and (3) adaptive dependence (later candidates adapt to earlier evaluation outcomes). Prior methods fail to account for adaptive dependence, violating the assumption that candidates are independent of the evaluation set.

• Key Mechanism: REUSE returns only binary promotion decisions to the search process (not scores or task-level outcomes) and allocates a global error budget across all possible decision histories, turning benchmark reuse into a controlled multiple-comparison problem.

• Experimental Results: In live self-improvement experiments on a binary classification task (Covertype dataset), REUSE commits zero false promotions (down from up to 20.7% for baseline methods) while achieving final population performance comparable to the best baselines (within 0.04 percentage points).

---

Introduction and Theoretical Foundation

Background and Motivation

Recursive self-improvement (RSI) has advanced rapidly—agents now rewrite their own tools, evolve production algorithms, and automate workflows like model alignment. However, these systems typically evaluate candidate modifications by repeatedly querying a finite set of fixed benchmarks. This creates a fundamental statistical challenge:

"When RSI systems rely on a finite set of benchmarks to guide adaptive search, the search trajectory becomes increasingly tuned to the evaluation signal, and empirical improvement may reflect adaptation to these benchmark tasks rather than genuine improvement."

The Three Sources of False Promotions

1. Within-round selection: Selecting the best of several candidates within a round favors candidates whose advantage on the evaluation set is overstated by chance.

2. Repeated testing: Testing across many rounds increases the probability that at least one test makes an error.

3. Adaptive dependence: Later candidates are adapted to earlier evaluation outcomes. When candidates are generated based on earlier outcomes on the evaluation set and then tested on the same set, the candidates become functions of the evaluation set itself, violating standard statistical test assumptions.

Statistical Setting

The formal framework defines:

• Population performance: $V(A) = \mathbb{E}_{W \sim Q}[s(A, W)]$ where $Q$ is the underlying population distribution and $s(A,W) \in [0,1]$ is the score of system $A$ on evaluation draw $W$.
• Population improvement: $\Delta(B, A) = V(B) - V(A)$
• Paired differences: $Z_i(B, A) = s(B, W_i) - s(A, W_i)$, which are i.i.d. with mean $\Delta(B, A)$.

Two key assumptions enable the framework:

Assumption 1 (Independent evaluation set): The evaluation set $S$ is independent of the tuple $(R, D, A_0)$—the proposer's randomness, development data, and initial system.

Assumption 2 (Decision-only feedback): For every round $t$ and candidate $k$, there exists a map $f_{t,k}$ such that $B_{t,k} = f_{t,k}(\xi, y_{1:t-1})$ where $y_{1:t-1}$ is the decision history and $\xi = (R, D, A_0)$. The evaluation set influences the search only through promotion decisions.

---

Methodology

REUSE Framework

The core idea: test each candidate against the current incumbent using paired evaluation on the fixed set $S$, allocating a single error budget across all possible candidate comparisons that could arise during the adaptive search.

Paired Sign Test

For pass/fail benchmarks ($s(A,W) \in \{0,1\}$), let:

• $n_+$ = number of tasks where candidate succeeds and incumbent fails
• $n_-$ = number of tasks where incumbent succeeds and candidate fails
• $M = n_+ + n_-$

The test is:

$$H_0: \Delta(B, A) \leq 0 \quad \text{versus} \quad H_1: \Delta(B, A) > 0$$

Under $H_0$, conditional on a disagreeing task, the probability the candidate wins is at most 1/2. The exact one-sided paired sign-test p-value is:

$$\pi(n_+, M) = P\left(\text{Bin}(M, \tfrac{1}{2}) \geq n_+\right), \quad \pi(0,0) = 1$$

Error Budget Allocation

The global error budget $\alpha \in (0, 1)$ is allocated across all comparisons that can arise under all possible decision histories. With $p$ promotions before round $t$, there are $\binom{t-1}{p}K^p$ possible decision histories. Each candidate comparison at round $t$ after $p$ promotions receives error budget:

$$\delta_{t,p} = \frac{\alpha \, w_t v_p}{\binom{t-1}{p}K^{p+1}}$$

where $\{w_t\}_{t\geq1}$ and $\{v_p\}_{p\geq0}$ are nonnegative weights satisfying $\sum_t w_t \leq 1$ and $\sum_p v_p \leq 1$. The paper uses $w_t = 1/[t(t+1)]$ and $v_p = 1/[(p+1)(p+2)]$.

This allocation addresses all three sources simultaneously:

• Weights over rounds $t$ control repeated testing
• Factor $K$ in denominator accounts for within-round selection
• $\binom{t-1}{p}K^p$ term handles adaptive dependence by covering all possible histories

Algorithm

Algorithm 1: REUSE at round t
1: p ← p_{t−1} and δ ← δ_{t,p}
2: for k = 1, ..., K do
3:   Compute (n_{+,k}, n_{−,k}) for B_{t,k} against A_{t−1}
4:   pass_k ← [π(n_{+,k}, n_{+,k} + n_{−,k}) ≤ ρδ]
5: end for
6: if at least one candidate passes then
7:   k* ← arg max_{k:pass_k} Z̄_k
8:   Compute lower confidence bound ℓ for Δ(B_{t,k*}, A_{t−1}) at error level (1−ρ)δ
9:   y_t ← k*
10:  C_t ← C_{t−1} + max{ℓ, 0}
11: else
12:  y_t ← 0, C_t ← C_{t−1}
13: end if

The budget $\delta_{t,p}$ is split: fraction $\rho\delta_{t,p}$ for the sign test, and $(1-\rho)\delta_{t,p}$ for constructing a lower confidence bound on population improvement.

Main Theoretical Result

Theorem 1 (Simultaneous validity and cumulative progress): For pass/fail evaluation with $s(A,W) \in \{0,1\}$ and $\gamma = 0$, under Assumptions 1 and 2, with probability at least $1-\alpha$:

1. $\Delta(A_t, A_{t-1}) > 0$ for every $t$ with $y_t \neq 0$ (every promotion is a true improvement)
2. $V(A_t) - V(A_0) \geq C_t$ for every $t \geq 1$ (cumulative certificate is valid)

The proof uses a union bound over all rounds, all possible histories, and all candidate comparisons, showing:

$$\sum_{t\geq1}\sum_{p=0}^{t-1}\binom{t-1}{p}K^p \cdot K\delta_{t,p} = \alpha \sum_{t\geq1} w_t \sum_{p=0}^{t-1} v_p \leq \alpha$$

Minimum Detectable Improvement

Proposition 1: For a fixed decision history node with disagreement probability $d \in (0,1]$, the minimum detectable population improvement is:

$$\Delta_{\min}(n, t, p, K, d) = \sqrt{\frac{2d \, L_{t,p}}{n}}$$

where $L_{t,p} = \ln(2/\delta_{t,p})$.

This shows that the detection threshold grows with $t$ and $p$ (as error budgets shrink to maintain the global guarantee), reflecting the need for stronger evidence as the search proceeds.

---

Empirical Validation / Results

Experimental Setup

• Task: Binary classification on the Covertype dataset (cover type 2 vs. the rest)
• Data split: Training set (50,000), development set (20,000), evaluation pool (60,000), held-out set (50,000)
• Evaluation set sizes: $n \in \{2{,}000, 10{,}000\}$, reused throughout the search
• Search: 200 rounds, up to $K=8$ candidates per round proposed by Qwen2.5-7B-Instruct
• Baselines: Empirical best-of-K, SICA-style, DGM-style, Elite, Niche-elite, PACE-style, Bonferroni-style
• Error level: $\alpha = 0.05$, $\gamma = 0$, $\rho = 1/2$

A promotion is called false if its population improvement (measured on the held-out set) is at most zero.

Main Results

Table 1: Live self-improvement on Covertype over 30 seeds

Key findings:

• Empirical best-of-K commits 75 false promotions at $n=2{,}000$ (~20% of accepted updates) and 71 at $n=10{,}000$, due to adaptive overfitting.
• Bonferroni-style avoids false promotions but is overly conservative—at $n=2{,}000$ it makes only 1.3 promotions per run with final improvement of just 2.35 pp (vs. 7.02 pp for REUSE).
• REUSE achieves zero false promotions at both evaluation set sizes while matching the top-performing baselines on final population improvement, and its optimism gap stays within one standard error of zero.

Additional Results

• Per-promotion analysis (Figure 3): REUSE's promotions are all strictly positive, while baselines show dense clusters of false promotions below zero.
• Robustness: REUSE maintains zero false promotions across 11 different allocation configurations (317 total promotions, 0 false), demonstrating robustness to hyperparameter choices.
• Ablation: Without the test on S, the process commits 6 false promotions across 5 of 10 runs with population improvements dropping to −0.56 pp; with the test, all 9 candidates with non-positive population improvement are correctly rejected.
• Certificates: The running certificate $C_T$ and direct certificate $D_T$ are valid in all 60 runs (never exceeding realized population improvement).

---

Theoretical and Practical Implications

Theoretical Contributions

1. Simultaneous error control: REUSE is the first framework to jointly control within-round selection, repeated testing, and adaptive dependence in RSI evaluation loops.

2. Fundamental limits characterization: The paper establishes lower bounds showing that adaptive dependence creates an unavoidable statistical cost—threshold-based rules require thresholds growing with $\ln(tK)$ before the first promotion and $\ln(Kt/P)$ after $P$ promotions to prevent adaptive proposers from inducing false promotions. This "first-order lower bound" matches REUSE's error allocation rate.

3. Valid cumulative certificates: REUSE provides both a running certificate (summing per-promotion bounds) and a direct certificate (comparing to the starting system), both with formal validity guarantees.

Practical Implications

• Safe deployment of self-improving agents: REUSE provides a practical mechanism for deploying RSI systems with certified guarantees that every accepted modification is a true improvement, which is crucial for frontier AI safety frameworks.

• No restrictions on proposer architecture: REUSE places no constraints on the underlying proposer or agent architecture—it works with arbitrary LLM-based proposers.

• Trade-off resolution: The experiments demonstrate that rigorous statistical guarantees need not compromise progress—REUSE matches the best baselines on true performance while eliminating false promotions.

Limitations and Future Directions

• The current decision-only feedback provides strict guarantees but may be overly restrictive; future work could accommodate richer signals (rounded scores, privatized summaries, periodically refreshed evaluation sets) by accounting for their information transcripts.
• The framework currently focuses on a single metric (performance); extending to secondary metrics like safety and cost control is a promising direction.
• The lower bound results apply to a specific class of threshold-gate rules, and the experiments focus on a machine learning classification task; extending to larger agentic settings (coding, model post-training) is a natural next step.

---

Conclusion

The paper addresses a critical reliability gap in recursive self-improvement systems that reuse fixed evaluation benchmarks. The central insight is that adaptive dependence—where later candidates depend on earlier outcomes on the same evaluation set—is a distinct statistical failure mode that standard multiple-comparison corrections do not address.

REUSE provides a principled solution by:

1. Restricting feedback to binary promotion decisions, ensuring candidates depend on the evaluation set only through the decision history
2. Allocating error budgets across all possible decision histories, turning adaptive dependence into a tractable multiple-comparison problem

The framework delivers formal guarantees: with probability at least $1-\alpha$, every promoted modification is a genuine population improvement, and valid lower bounds on cumulative improvement are maintained. Empirical results on the Covertype classification task confirm the framework's practical value—eliminating false promotions (from up to 20.7% down to 0%) while preserving true population performance comparable to the best baselines.

As self-improving AI systems become more capable and widely deployed, REUSE offers a template for building evaluation frameworks that are both powerful and trustworthy, providing the auditable and provable records of capability gains increasingly required by frontier AI safety standards.