Paper deep dive

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

Xiaojing Sun, Yuhan Zeng, Zihua She, Xiao Wang

Year: 2026Venue: arXiv preprintArea: stat.MLType: PreprintEmbeddings: 131

Intelligence

Status: not_run | Model: - | Prompt: - | Confidence: 0%

Entities (0)

No extracted entities yet.

Relation Signals (0)

No relation signals yet.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

127,369 characters extracted from source content.

Expand or collapse full text

Which Self-Improvements Should We Trust? Reliable Self-Improvement When Agents Reuse Their Benchmarks Xiaojing Sun Affiliation: Purdue University Yuhan Zeng Affiliation: Purdue University Zihua She Affiliation: Purdue University Xiao Wang Affiliation: Purdue University Abstract 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. Specifically, for a user-specified error level α, with probability at least 1−α1-α, 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 a 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 promotions that are false from up to 20.7% to 0%, while achieving final true population performance comparable to the best baselines. 1 Introduction Recent progress in recursive self-improvement (RSI) has significantly advanced the capabilities of self-improving AI systems. For instance, agents now rewrite their own tools (Zhang et al., 2026; Robeyns et al., 2025), evolve production-ready algorithms (Novikov et al., 2025), and automate complex workflows like model alignment and post-training (Chen et al., 2026b; Rank et al., 2026). As agents become more capable at proposing and executing changes (Zelikman et al., 2024; Hu et al., 2025; Lu et al., 2024; Wang et al., 2026b), evaluation becomes increasingly critical (Manheim and Garrabrant, 2018; Skalse et al., 2022; Gao et al., 2023; Guo et al., 2026). The evaluation feedback dictates which candidate modifications are retained, expanded, or used to generate future proposals. Ideally, this feedback would favor only changes that improve performance on the underlying task distribution (Hastie et al., 2009; Recht et al., 2019). In practice, current RSI systems employ diverse search strategies but typically obtain this feedback by repeatedly querying a finite set of fixed benchmarks (Wang et al., 2026c). 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 (Shawn, 2026), and empirical improvement may reflect adaptation to these benchmark tasks rather than genuine improvement (Wang et al., 2026c; Chen et al., 2026b). False promotions in this setting arise from three main sources. • Within-round selection. Selecting the best of several candidates within a round favors candidates whose advantage on the evaluation set is overstated by chance (Cawley and Talbot, 2010; Efron, 2011; Xu et al., 2026). • Repeated testing. Testing across many rounds increases the probability that at least one test makes an error (Dunn, 1961; Holm, 1979). • Adaptive dependence. Later candidates are adapted to earlier evaluation outcomes (Dwork et al., 2015b; Hardt and Ullman, 2014; Blum and Hardt, 2015). The first two would arise even if every round used fresh evaluation data, and standard multiple comparison corrections handle them by accounting for the number of tests (Dunn, 1961; Holm, 1979; Bretz et al., 2009; Tian and Ramdas, 2021). The third source arises from benchmark reuse. When later candidates are generated based on earlier outcomes on the evaluation set and then tested on that same set, the candidates themselves become functions of the evaluation set. This adaptive dependence violates the assumption of standard statistical tests that candidates are chosen independently of the evaluation set (Kriegeskorte et al., 2009; Berk et al., 2013; Dwork et al., 2015a). Consequently, a candidate may be promoted because it overfits the specific evaluation set, rather than because it genuinely improves on the underlying task distribution. Recent work attempts to bring statistical error control into self-improvement loops and iterative evaluation (Shawn, 2026; Wu et al., 2025; Sengupta, 2026; Guo et al., 2026; Bertran et al., 2026). However, none of these methods account for all three sources of false promotion simultaneously. In particular, their statistical guarantees rely on each candidate being independent of the data on which it is evaluated, and restricting feedback alone does not account for the information revealed by the promotion decisions themselves. Because they do not address the adaptive dependence created by reusing the same evaluation set, they cannot guarantee that every promoted modification is a genuine population improvement. Figure 1: Overview of Reuse. (a) At round t, the proposer generates K candidate modifications using development data and earlier promotion decisions. (b) Reuse compares each candidate with the current system At−1A_t-1 on a fixed evaluation set S of n tasks that is reused in every round. (c) Only the promotion decision yty_t is returned to the proposer. With probability at least 1−α1-α, every promotion is a true improvement in population performance, V⁡(At)>V⁡(At−1)V(A_t)>V(A_t-1), simultaneously over the entire run, and the cumulative improvement V⁡(At)−V⁡(A0)V(A_t)-V(A_0) is certified to be at least CtC_t. In this paper, we propose Reuse (Risk-controlled Evaluation Under Sequential Evolution), a certified evaluation and promotion framework for adaptive self-improvement that controls all three sources jointly. Reuse allows a fixed evaluation set to be reused throughout an adaptive search while preserving valid evidence of population improvement. In each round, candidate modifications are evaluated against the current system, but the search process receives only the promotion decision rather than evaluation scores or task-level outcomes (Figure 1). Later candidates may still adapt to earlier decisions, but they can depend on the evaluation set only through this decision history. For each possible history, the candidates are determined without reference to the evaluation set, so the corresponding comparison is a valid test. Reuse therefore turns the dependence on the evaluation set into a multiple comparison problem over all possible decision histories, and controls it together with the first two sources within a global error budget. As a result, for a user-specified level α, with probability at least 1−α1-α, every promoted modification over the entire self-improvement process is a genuine population improvement on the underlying task distribution. Our main contributions are: • We propose Reuse, a certified evaluation and promotion framework for adaptive self-improvement that jointly addresses the statistical challenges of within-round selection, repeated testing, and adaptive dependence under finite evaluation resources. For a user-specified error level α, with probability at least 1−α1-α, every promoted modification is a genuine population improvement on the underlying task distribution. • We develop statistical theory for evaluation under benchmark reuse, including simultaneous error control over the entire process, valid lower bounds on cumulative improvement, the minimum detectable improvement, and the fundamental limits of adaptive evaluation reuse. • We evaluate Reuse in live self-improvement experiments against evaluation frameworks from current RSI systems and error-controlled baselines. Reuse commits substantially fewer false promotions than competing methods, reducing the proportion of promotions that are false from up to 20.7% to 0%, while achieving final true population performance within 0.04 percentage points of the best baselines, demonstrating that its rigorous statistical guarantees do not compromise overall progress. 2 Methodology and Theoretical Guarantees In this section, we formalize the adaptive self-improvement setting, present Reuse, and establish its statistical guarantees. More comprehensive theoretical results and complete proofs are given in Appendix A. 2.1 Setting and objective A system A∈A denotes the complete agent or AI system evaluated at a given round. A modification may change its prompt, code, tools, training procedure, or model parameters. Let Q denote the underlying population distribution on which system performance is measured. For an evaluation draw W∼QW Q, the score of system A is s⁡(A,W)∈[0,1]s(A,W)∈[0,1]. Any randomness used in the evaluation is included in W. The population performance of A is V⁡(A)=W∼Q[s⁡(A,W)],Δ⁡(B,A)=V⁡(B)−V⁡(A),V(A)=E_W Q[s(A,W)], (B,A)=V(B)-V(A), where Δ⁡(B,A) (B,A) is the population improvement of candidate B over system A. The self-improvement process starts from A0A_0. At round t, the current system is At−1A_t-1 and the proposer generates K candidates Bt,1,…,Bt,K.B_t,1,…,B_t,K. The promotion decision is yt∈0,1,…,Ky_t∈\0,1,…,K\. If yt=k>0y_t=k>0, candidate Bt,kB_t,k becomes the new system. If yt=0y_t=0, all candidates are rejected and the incumbent is retained. We write pt=∑s=1tys≠0p_t= _s=1^t1\y_s≠ 0\ for the number of promotions through round t. Promotion decisions are based on a fixed evaluation set S=(W1,…,Wn),Wi∼i.i.d.Q,S=(W_1,…,W_n), W_i i.i.d. Q, drawn before the process begins and repeatedly reused across rounds. For any pair of systems (B,A)(B,A), define the paired differences Zi(B,A)=s⁡(B,Wi)−s⁡(A,Wi),Z_i(B,A)=s(B,W_i)-s(A,W_i), which are i.i.d. with mean Δ⁡(B,A) (B,A). The proposer receives information from S only through previous promotion decisions. It may otherwise adapt using its own randomness R, development data D, and those decisions. We formalize this setting with two assumptions. Assumption 1 (Independent evaluation set). The evaluation set S is independent of the tuple (R,D,A0)(R,D,A_0) consisting of the proposer’s randomness, the development data, and the initial system. Assumption 2 (Decision-only feedback). Write ξ=(R,D,A0)ξ=(R,D,A_0). For every round t≥1t≥ 1 and candidate index k≤Kk≤ K, there is a map ft,kf_t,k such that Bt,k=ft,k(ξ,y1:t−1)B_t,k=f_t,k(ξ,y_1:t-1). Moreover, the map (ξ,w)↦s⁡(A0,w)(ξ,w) s(A_0,w) and, for every t≥1t≥ 1, k≤Kk≤ K, and fixed history h∈0,1,…,Kt−1h∈\0,1,…,K\^t-1, the map (ξ,w)↦s⁡(ft,k(ξ,h),w)(ξ,w) s(f_t,k(ξ,h),w) are jointly measurable. Assumption 1 requires that the evaluation set S be drawn independently of everything that shapes the search from the start, which is exactly what a benchmark is meant to be, a fresh sample from the target task distribution that plays no role in development. Assumption 2 requires that S influence the search only through the promotion decisions, while the proposer is otherwise unrestricted and can freely use any language model or development pipeline. Together, the two assumptions ensure that candidate generation depends on S only through the decision history. Once ξ is fixed, every possible decision history determines the incumbent and the next candidates without reference to S, and by Assumption 1 S remains an i.i.d. sample from Q. Every comparison determined in this way is therefore a valid test, and each comparison actually made during the search is one of them. This turns the adaptive dependence created by benchmark reuse into a multiple comparison problem over all possible decision histories, which the allocation in Section 2.2 explicitly controls. The measurability condition is technical and holds for essentially any practical proposer, for example whenever systems are prompts, programs, or configurations. For a practical improvement threshold γ≥0γ≥ 0, a promotion is false if Δ⁡(At,At−1)≤γ. (A_t,A_t-1)≤γ. Our goal is to control all promotions simultaneously: ℙ⁡(Δ⁡(At,At−1)>γ for every t with yt≠0)≥1−α.P\! ( (A_t,A_t-1)>γ for every t with y_t≠ 0 )≥ 1-α. (1) 2.2 Reuse To achieve the guarantee in (1), Reuse tests each candidate against the current system using paired evaluation and allocates a single error budget across all candidate comparisons that may arise during the adaptive search. At each round, the proposer generates candidates using development data and previous promotion decisions, and receives only the evaluation framework’s promotion decision. Figure 1 illustrates this process. We first consider pass/fail benchmarks with γ=0γ=0, where s⁡(A,W)∈0,1s(A,W)∈\0,1\. The same framework extends naturally to bounded scores s⁡(A,W)∈[0,1]s(A,W)∈[0,1], where the detailed construction is given in Section A.1. For a fixed candidate B and incumbent A, let n+n_+ be the number of evaluation tasks on which B succeeds and A fails, let n−n_- be the number on which A succeeds and B fails, and let M=n++n−M=n_++n_- be the number of tasks on which the two systems have different outcomes. We test whether the candidate genuinely improves on the incumbent: H0:Δ⁡(B,A)≤0versusH1:Δ⁡(B,A)>0.H_0: (B,A)≤ 0 H_1: (B,A)>0. (2) Under H0H_0, conditional on a task where the two systems disagree, the probability that B wins is at most 1/21/2. Conditional on M, this gives the exact one-sided paired sign-test p-value π⁡(n+,M)=ℙ⁡(Bin⁡(M,12)≥n+),π⁡(0,0)=1.π(n_+,M)=P\! (Bin(M, 12)≥ n_+ ), π(0,0)=1. (3) A small value of π⁡(n+,M)π(n_+,M) provides evidence in favor of Δ⁡(B,A)>0 (B,A)>0, and its finite-sample validity is established in Lemma A2. A single hypothesis test controls the error for one fixed candidate–incumbent comparison. In the self-improvement loop, however, many comparisons are made on the same evaluation set, and later candidates depend on earlier promotion decisions. To control false promotions over the entire run, Reuse allocates the global error budget α∈(0,1)α∈(0,1) across all comparisons that can arise under all possible decision histories. Suppose p promotions have occurred before round t. The p promotion rounds can be chosen in (t−1p) t-1p ways, and each promotion can select one of K candidates. Hence there are (t−1p)Kp t-1p\,K^p possible decision histories with p previous promotions. Under Assumption 2, once (R,D,A0)(R,D,A_0) are fixed, each such history determines the incumbent and the K candidates at round t. Let (wt)t≥1(w_t)_t≥ 1 and (vp)p≥0(v_p)_p≥ 0 be nonnegative weights satisfying ∑t≥1wt≤1 _t≥ 1w_t≤ 1 and ∑p≥0vp≤1. _p≥ 0v_p≤ 1. These weights distribute the overall error budget across the round index and the number of previous promotions. At round t after p promotions, each candidate comparison is assigned the error budget δt,p=αwtvp(t−1p)Kp+1. _t,p= α w_tv_p t-1pK^p+1. (4) This explicit allocation addresses all three sources of false promotion mentioned in Section 1 simultaneously. The weights over rounds t control repeated testing, the additional factor K in the denominator accounts for within-round selection, and the (t−1p)Kp t-1pK^p term handles adaptive dependence by covering all possible histories. Throughout the paper we use wt=1/[t⁡(t+1)]w_t=1/[t(t+1)] and vp=1/[(p+1)(p+2)].v_p=1/[(p+1)(p+2)]. To also quantify cumulative improvement, we divide δt,p _t,p into two parts. For a fixed ρ∈(0,1)ρ∈(0,1), a fraction ρδt,pρ _t,p is used for the sign test, and the remaining (1−ρ)δt,p(1-ρ) _t,p is used to construct a lower confidence bound ℓ on the candidate’s population improvemetn (Lemma A3). When a candidate is promoted, Reuse adds max⁡ℓ,0 \ ,0\ to a running certificate CtC_t, initialized at C0=0C_0=0. The certificate is kept for auditing and is not returned to the proposer during the search. For candidate k at round t, define its empirical improvement over the incumbent as Z¯k=1n∑i=1nZi(Bt,k,At−1). Z_k= 1n _i=1^nZ_i(B_t,k,A_t-1). If multiple candidates pass the promotion test, Reuse promotes the one with the largest Z¯k Z_k. The complete procedure is given in Algorithm 1. Algorithm 1 Reuse at round t 1: p←pt−1p← p_t-1 and δ←δt,pδ← _t,p 2: for k=1,…,Kk=1,…,K do 3: Compute (n+,k,n−,k)(n_+,k,n_-,k) and Z¯k Z_k for Bt,kB_t,k against At−1A_t-1 4: passk←[π(n+,k,n+,k+n−,k)≤ρδ]pass_k← [π(n_+,k,n_+,k+n_-,k)≤ρδ ] 5: end for 6: if at least one candidate passes then 7: k⋆←argmaxk:passkZ¯k ← _k:pass_k Z_k 8: Compute a lower confidence bound ℓ for Δ⁡(Bt,k⋆,At−1) (B_t,k ,A_t-1) at error level (1−ρ)δ(1-ρ)δ 9: yt←k⋆y_t← k 10: Ct←Ct−1+max⁡ℓ,0C_t← C_t-1+ \ ,0\ 11: else 12: yt←0y_t← 0, Ct←Ct−1C_t← C_t-1 13: end if Conditional on (R,D,A0)(R,D,A_0), each fixed-history comparison has probability at most δt,p _t,p of either an erroneous promotion decision or an invalid lower confidence bound. A union bound over all rounds, all possible histories, and all candidate comparisons gives ∑t≥1∑p=0t−1(t−1p)Kp⋅Kδt,p=α∑t≥1wt∑p=0t−1vp≤α. _t≥ 1 _p=0^t-1 t-1pK^p· K _t,p=α _t≥ 1w_t _p=0^t-1v_p≤α. This gives the following main result. Theorem 1 (Simultaneous validity and cumulative progress). Consider pass/fail evaluation, with s⁡(A,W)∈0,1s(A,W)∈\0,1\ and γ=0γ=0. Suppose Assumptions 1 and 2 hold, and Reuse is run as in Algorithm 1 with the allocation (4). Then, for every adaptive proposer satisfying these assumptions, with probability at least 1−α1-α, Δ⁡(At,At−1)>0 (A_t,A_t-1)>0 for every t with yt≠0y_t≠ 0. On the same event, the running certificate satisfies V⁡(At)−V⁡(A0)≥CtV(A_t)-V(A_0)≥ C_t for every t≥1t≥ 1. The cumulative bound follows by summing the valid stepwise contributions max⁡ℓ,0 \ ,0\ over promotions, since the corresponding population improvement telescope to V⁡(At)−V⁡(A0)V(A_t)-V(A_0). Development data may also be used to select a single candidate before S is queried. If only that candidate is tested on S, Theorem 1 applies with K=1K=1 in (4), since there is no within-round candidate selection on the evaluation set. We now establish how large a true improvement must be for reliable detection. We let ℒt,p=ln⁡(2/δt,p)L_t,p= (2/ _t,p) and let d=ℙ⁡(Zi(B,A)≠0)d=P\! (Z_i(B,A)≠ 0 ) denote the probability that the candidate and incumbent have different outcomes on a random task. The following result gives the corresponding minimum detectable population improvement. Proposition 1 (Minimum detectable improvement). Consider pass/fail evaluation with γ=0γ=0 and ρ=1/2ρ=1/2 at a fixed decision history node. Suppose the candidate and incumbent pairs are fixed independently of S and each has disagreement probability d∈(0,1]d∈(0,1]. Define Δmin(n,t,p,K,d)=2dℒt,pn. _ (n,t,p,K,d)= 2d\,L_t,pn. Under the regularity conditions in Section A.6, for any fixed η∈(0,1)η∈(0,1), a candidate with Δ⁡(B,A)≥(1+η)Δmin (B,A)≥(1+η) _ passes the promotion test with probability tending to one, whereas if all K candidates satisfy Δ⁡(Bt,k,At−1)≤(1−η)Δmin (B_t,k,A_t-1)≤(1-η) _ , the probability of any promotion tends to zero. The quantity Δmin _ represents the smallest population improvement that we can reliably detect. The formula shows that a larger evaluation set n in the denominator decreases this detection threshold. At the same time the term ℒt,pL_t,p in the numerator depends on the per-round error level δt,p _t,p. To maintain our global guarantee we must allocate smaller error budgets δt,p _t,p as the round count t and promotion count p increase. This decrease in δt,p _t,p causes ℒt,pL_t,p to grow which makes larger true improvements necessary for reliable detection at later stages. This behavior directly reflects our statistical intuition. By demanding stronger evidence as the search proceeds we prevent random noise from accumulating into false promotions over a long trajectory. This dependence on the adaptive history is not solely an artifact of our particular allocation. In Section A.7 we show that for a class of threshold rules a comparable first order growth in the promotion threshold is necessary to prevent an adaptive proposer from eventually inducing a false promotion. 3 Experiments In this section, we evaluate Reuse against existing methods in live self-improvement loops, where an LLM-based proposer generates modifications and a finite evaluation set is repeatedly reused. Our experiments address two key questions: First, how often do current RSI promotion schemes accept false improvements? Second, can Reuse prevent these false promotions without sacrificing true population improvement? 3.1 Experimental setup We consider the agent tasked with machine learning classification. Specifically, we use the Covertype dataset (Blackard, 1998)11 1 https://archive.ics.uci.edu/dataset/31/covertype for the binary classification of cover type 2 against the remaining six classes. A fixed random split yields a training set DtrD_tr of 50,000 examples for fitting candidates, a development set DdevD_dev of 20,000 examples for proposer feedback, and an evaluation pool ℰE of 60,000 examples, from which each run draws an evaluation set S of size n∈2,000,10,000n∈\2,000,10,000\ that is reused throughout the search. Together, DtrD_tr and DdevD_dev form D of Section 2.1. Since the underlying task distribution is unknown, we measure population improvement on a disjoint held-out set H of 50,000 examples. Each run lasts T=200T=200 rounds. At every round, Qwen2.5-7B-Instruct (Yang et al., 2024) proposes up to K=8K=8 modifications of a scikit-learn pipeline (Pedregosa et al., 2011) based on the prompt templates detailed in Section B.2. Each modification changes at most two components among the model family, feature subset, pre-processing, and hyperparameters. All methods start from the same gradient-boosting configuration, share the proposer, candidate space, and training data, and see the same evaluation set within a seed. We run 30 seeds at each evaluation-set size, and Appendix B gives the full protocol. We compare Reuse with several evaluation frameworks that reflect how current RSI systems use their benchmarks. Empirical best-of-K edits the incumbent and promotes the candidate with the largest positive gain on S (Chen et al., 2026b). SICA-style follows the archive-based search of SICA (Robeyns et al., 2025), DGM-style follows the parent selection of DGM (Zhang et al., 2026), and Elite and Niche-elite use population-based search inspired by AlphaEvolve (Novikov et al., 2025). We also evaluate baselines that add statistical control to the same loop. PACE-style applies a one-sided McNemar test (Dietterich, 1998) to each candidate at level α=0.05α=0.05, a fixed-sample analogue of the per-decision error control in PACE (Shawn, 2026). Bonferroni-style applies the same test at level 0.05/(TK)0.05/(TK), splitting the error budget evenly over all potential comparisons of a run, as in the union-bound allocation of SGM (Wu et al., 2025). To measure true improvement, we estimate the population improvement of each promoted modification by its paired improvement on the held-out set H, which no method ever accesses, and call a promotion false when this improvement is at most zero. For each method we report the final population improvement of the deployed system over the starting system A0A_0, the mean number of promotions per run, and the total number of false promotions across runs. We also report the optimism gap of the final system, defined as its improvement over A0A_0 measured on S minus its population improvement, which measures how much the reused evaluation set overstates the final improvement. 3.2 Results Table 1: Live self-improvement on Covertype over 30 seeds at each evaluation-set size, with all methods run on the same seeds. Pop. Impr. is the final population improvement of the deployed system over starting system A0A_0 in percentage points (p), estimated on the held-out set H and reported as mean ± standard error. Prom. is the mean number of promotions per run, and False is the number of promotions with non-positive population improvement, summed over the 30 runs. Opt. Gap is the final improvement measured on S minus the population improvement measured on H, which measures how much the reused evaluation set overstates the final improvement. Select., Repeat., and Adapt. indicate whether a rule controls errors from within-round selection, repeated testing, and adaptive dependence, the three sources of false promotion discussed in Section 1. n=2,000n=2,000 n=10,000n=10,000 Method Select. Repeat. Adapt. Pop. Impr. ↑ Prom. False ↓ Opt. Gap ↓ Pop. Impr. ↑ Prom. False ↓ Opt. Gap ↓ Empirical best-of-K ✗ ✗ ✗ 7.04±\,±\,0.08 13.0 75 0.43±\,±\,0.11 7.19±\,±\,0.06 14.2 71 0.15±\,±\,0.06 SICA-style ✗ ✗ ✗ 6.36±\,±\,0.18 12.3 72 0.34±\,±\,0.10 6.56±\,±\,0.16 12.5 62 0.14±\,±\,0.05 DGM-style ✗ ✗ ✗ 3.89±\,±\,0.17 6.4 34 0.06±\,±\,0.11 4.03±\,±\,0.18 7.2 18 0.01±\,±\,0.05 Elite ✗ ✗ ✗ 6.72±\,±\,0.14 14.3 89 0.47±\,±\,0.12 6.85±\,±\,0.12 13.7 59 0.16±\,±\,0.05 Niche-elite ✗ ✗ ✗ 6.46±\,±\,0.15 12.3 71 0.40±\,±\,0.13 6.37±\,±\,0.15 12.4 44 0.13±\,±\,0.05 PACE-style ✗ ✗ ✗ 6.45±\,±\,0.19 6.4 4 0.31±\,±\,0.10 7.23±\,±\,0.02 8.1 3 0.10±\,±\,0.05 Bonferroni-style ✓ ✓ ✗ 2.35±\,±\,0.37 1.3 0 0.21±\,±\,0.08 6.90±\,±\,0.12 6.5 0 0.10±\,±\,0.05 Reuse (ours) ✓ ✓ ✓ 7.02±\,±\,0.26 3.2 0 0.05±\,±\,0.12 7.19±\,±\,0.13 5.9 0 0.06±\,±\,0.07 Figure 2: Population improvement of the deployed system over starting system A0A_0 across rounds, estimated on H and averaged over 30 seeds, in percentage points (p). The left panel uses n=2,000n=2,000 and the right panel uses n=10,000n=10,000. Figure 3: Population improvement of every promoted modification over the system it replaces, estimated on H and pooled over 30 seeds, in percentage points (p). Each point is one promotion, and red triangles mark false promotions, whose population improvement is at most zero. Within each panel, the left column uses n=2,000n=2,000 and the right column uses n=10,000n=10,000. Table 1 reports the final population improvement over A0A_0 for each method alongside the number of promotions, the count of false promotions, and the optimism gap (Opt. Gap) of the final system. The results highlight how existing evaluation methods fail and how Reuse guarantees reliability without sacrificing true performance. For instance, at n=2,000n=2,000, Empirical best-of-K makes 75 false promotions, that is, nearly 20 percent of its accepted updates yield non-positive population improvement. Even when the evaluation set expands to n=10,000n=10,000, this framework still commits 71 false promotions. Although Empirical best-of-K achieves high final population improvement, its gains only match those of Reuse. Other benchmark-driven frameworks like SICA-style also commit numerous false promotions while yielding substantially lower population improvements. The Opt. Gap column further clarifies these behaviors. Methods like Empirical best-of-K and PACE-style show large gaps because they adaptively overfit to the evaluation set. DGM-style exhibits a small gap but achieves very low population improvement, which reflects an inability to optimize rather than successful generalization. Statistical baselines also struggle to balance safety and progress. Bonferroni-style avoids false promotions but proves heavily conservative. It makes only 1.3 promotions per run at n=2,000n=2,000 and restricts its final population improvement to a mere 2.35 p, well below the 7.02 p achieved by Reuse. PACE-style improves performance but lacks formal guarantees and still commits false promotions at both evaluation set sizes. Reuse effectively solves this trade-off. It makes no false promotion while matching the strongest methods, achieving a population improvement of 7.02 p at n=2,000n=2,000 and 7.19 p at n=10,000n=10,000. Furthermore, its optimism gap stays within one standard error of zero at both sizes alongside high final true performance, proving that it eliminates adaptive overfitting without falling into the underfitting trap seen in DGM-style. The trajectories across rounds in Figure 2 show that Reuse consistently stays near the top of the performance curves and establishes dominance when the sample size increases to n=10,000n=10,000. Figure 3 reveals the step-wise dynamics of individual promotions. Most competing methods display a dense cluster of points below zero, visibly marked by red triangles that represent false promotions. Bonferroni-style has no red triangles but produces very few points, confirming its overly conservative nature. In contrast, the entire cluster of points for Reuse sits noticeably higher, and every promotion is strictly positive. 4 Related Work Recursive self-improvement and statistical control. The idea of a system that improves itself with guarantees dates back to the Gödel machine (Schmidhuber, 2007). Language models have turned this into practical search loops that rewrite prompts, agent scaffolds, algorithms, and entire pipelines (Zelikman et al., 2024; Fernando et al., 2024; Robeyns et al., 2025; Zhang et al., 2026; Novikov et al., 2025; Chen et al., 2026b; Chen et al., 2026a). However, evaluating these systems by repeatedly querying fixed benchmarks often leads to false promotions and degraded deployment performance (Wang et al., 2026c; Shawn, 2026; Guo et al., 2026; Wang et al., 2026a). To address this, recent works gate self-modification with statistical tests, utilizing global error budgets (Wu et al., 2025; Sengupta, 2026), sequential testing (Shawn, 2026), or sealed audits (Guo et al., 2026; Mittal and Gupta, 2026). Yet, these approaches typically treat candidates as independent of the test data or restrict feedback without accounting for the information revealed by the promotion decisions themselves. Reuse overcomes this by combining decision-only feedback with an explicit error allocation over all possible decision histories, thereby controlling adaptive dependence on a reused evaluation set over the entire run. Adaptive data analysis and holdout reuse. The risk of reusing a holdout set adaptively is a central topic in adaptive data analysis. Mechanisms based on differential privacy and description length allow a holdout set to answer adaptively chosen queries (Dwork et al., 2015b; Dwork et al., 2015a), and the Ladder mechanism maintains a leaderboard by releasing scores only upon significant improvement (Blum and Hardt, 2015). Information-theoretic arguments bound the bias of adaptive analysis (Russo and Zou, 2016; Xu and Raginsky, 2017; Bassily et al., 2016), though empirical benchmark reuse often shows less overfitting than worst-case theory predicts (Recht et al., 2019; Roelofs et al., 2019; Bertran et al., 2026). Reuse explicitly counts decision histories, turning the information bound into exact finite-sample tests for each promotion. Multiple testing and sequential inference. Controlling the family-wise error over many hypotheses encompasses classical (Holm, 1979), weighted (Bretz et al., 2009), and sequential anytime-valid procedures (Lan and DeMets, 1983; Javanmard and Montanari, 2018; Howard et al., 2021; Ramdas et al., 2023; Waudby-Smith and Ramdas, 2024). Similarly, selective inference adjusts tests for data-driven selection biases (Berk et al., 2013; Fithian et al., 2014; Efron, 2011; Jamieson and Jain, 2018). However, these frameworks generally assume that hypotheses are fixed in advance, arrive with fresh data, or are selected by characterizable distributions. In a self-improvement loop, hypotheses are instead generated by an arbitrary proposer adapting to earlier outcomes on the same data. Reuse bridges this gap by allocating an error budget over all possible decision histories, ensuring each test is valid in finite samples (Clopper and Pearson, 1934; Maurer and Pontil, 2009). 5 Discussion Self-improving systems increasingly decide what to keep by querying the same evaluation set over long trajectories. We showed that this reuse creates a source of error that multiple comparison corrections do not address, because later candidates depend on earlier outcomes on the evaluation set. Reuse controls this by returning only promotion decisions and allocating an error budget over all decision histories, which yields a simultaneous guarantee that every promoted modification is a true population improvement. In live self-improvement experiments, Reuse made much fewer false promotion than other frameworks without sacrificing true population performance. Reuse achieves this reliability while placing no restrictions on the underlying proposer or agent architecture. While our experiments demonstrate the framework on a machine learning classification task, extending it to larger agentic settings like coding and model post-training is a natural next step. The decision-only feedback currently provides strict statistical guarantees, but future work could accommodate richer signals including rounded scores, privatized summaries, or periodically refreshed evaluation sets by explicitly accounting for their information transcripts. Furthermore, expanding the framework to simultaneously control for secondary metrics like safety and cost offers a promising path toward generating the auditable and provable records of capability gains increasingly required by frontier AI safety frameworks (OpenAI, 2025). Reproducibility statement Proofs of all theoretical results are given in Appendix Appendix A and the full experimental protocol and prompts in Appendix Appendix B. The supplementary material contains anonymized code for all experiments of Section 3. AI use statement Large language models (Claude, Anthropic; ChatGPT, OpenAI) were used solely to assist with the writing and presentation of this paper. Based on the authors’ draft, this assistance included refining wording for clarity and concision, improving paragraph organization, and adjusting the manuscript’s formatting. The authors developed the research ideas and theoretical arguments, designed the experiments, and analyzed and interpreted the results. The authors reviewed each edit suggested by the models and verified that it did not alter any technical claim or reported numerical value. The authors take full responsibility for the final text, technical claims, and reported results. Ethics statement Our experiments use the publicly available Covertype dataset (Blackard, 1998), which contains only cartographic variables and no personal or sensitive information. The task is a standard classification problem and involves no human subjects. We are not aware of ethical concerns arising from the data or the task, and we adhere to the ICLR Code of Ethics. References Bassily et al. (2016) R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman Algorithmic stability for adaptive data analysis. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), Cited by: §4. Berk et al. (2013) R. Berk, L. Brown, A. Buja, K. Zhang, and L. Zhao Valid post-selection inference. The Annals of Statistics 41 (2), p. 802–837. Cited by: §1, §4. Bertran et al. (2026) M. A. Bertran, A. Roth, and Z. S. Wu What fits (into few tokens) doesn’t overfit: compression and generalization in ML research agents. Note: arXiv preprint arXiv:2606.11045 Cited by: §1, §4. Blackard (1998) J. A. Blackard Covertype. Note: UCI Machine Learning Repository Cited by: §3.1, Ethics statement. Blum and Hardt (2015) A. Blum and M. Hardt The ladder: a reliable leaderboard for machine learning competitions. In Proceedings of the 32nd International Conference on Machine Learning (ICML), p. 1006–1014. Cited by: 3rd item, §4. Bretz et al. (2009) F. Bretz, W. Maurer, W. Brannath, and M. Posch A graphical approach to sequentially rejective multiple test procedures. Statistics in Medicine 28 (4), p. 586–604. Cited by: §1, §4. Cawley and Talbot (2010) G. C. Cawley and N. L. C. Talbot On over-fitting in model selection and subsequent selection bias in performance evaluation. Journal of Machine Learning Research 11, p. 2079–2107. Cited by: 1st item. Chen et al. (2026a) M. Chen, L. Wang, and B. Qu Recursive self-improvement in AI: from bounded self-refinement to autonomous research loops. Note: arXiv preprint arXiv:2607.07663 Cited by: §4. Chen et al. (2026b) Y. Chen, J. Wen, and J. H. Kirchner Automated researchers can mitigate well-characterized alignment failures. Note: Anthropic Alignment Science Cited by: §1, §1, §3.1, §4. Clopper and Pearson (1934) C. J. Clopper and E. S. Pearson The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika 26 (4), p. 404–413. Cited by: §A.3, §4. Dietterich (1998) T. G. Dietterich Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation 10 (7), p. 1895–1923. Cited by: §B.3, §3.1. Dunn (1961) O. J. Dunn Multiple comparisons among means. Journal of the American Statistical Association 56 (293), p. 52–64. Cited by: 2nd item, §1. Dwork et al. (2015a) C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth Generalization in adaptive data analysis and holdout reuse. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §4. Dwork et al. (2015b) C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth The reusable holdout: preserving validity in adaptive data analysis. Science 349 (6248), p. 636–638. Cited by: 3rd item, §4. Efron (2011) B. Efron Tweedie’s formula and selection bias. Journal of the American Statistical Association 106 (496), p. 1602–1614. Cited by: 1st item, §4. Fernando et al. (2024) C. Fernando, D. Banarse, H. Michalewski, S. Osindero, and T. Rocktäschel Promptbreeder: self-referential self-improvement via prompt evolution. In Proceedings of the 41st International Conference on Machine Learning (ICML), Cited by: §4. Fithian et al. (2014) W. Fithian, D. Sun, and J. Taylor Optimal inference after model selection. Note: arXiv preprint arXiv:1410.2597 Cited by: §4. Gao et al. (2023) L. Gao, J. Schulman, and J. Hilton Scaling laws for reward model overoptimization. In Proceedings of the 40th International Conference on Machine Learning (ICML), Cited by: §1. Guo et al. (2026) D. Guo, C. Cao, F. Yuan, Y. Wang, Y. Wang, and D. Wang Self-authored verification is unreliable in heuristic self-improving agents. Note: arXiv preprint arXiv:2607.24300 Cited by: §1, §1, §4. Hardt and Ullman (2014) M. Hardt and J. Ullman Preventing false discovery in interactive data analysis is hard. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), p. 454–463. Cited by: 3rd item. Hastie et al. (2009) T. Hastie, R. Tibshirani, and J. Friedman The elements of statistical learning: data mining, inference, and prediction. 2nd edition. Cited by: §1. Hoeffding (1963) W. Hoeffding Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58 (301), p. 13–30. Cited by: §A.1, §A.1, §A.6, §A.6. Holm (1979) S. Holm A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics 6 (2), p. 65–70. Cited by: 2nd item, §1, §4. Howard et al. (2021) S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics 49 (2), p. 1055–1080. Cited by: §4. Hu et al. (2025) S. Hu, C. Lu, and J. Clune Automated design of agentic systems. In International Conference on Learning Representations (ICLR), Cited by: §1. Jamieson and Jain (2018) K. G. Jamieson and L. Jain A bandit approach to sequential experimental design with false discovery control. In Advances in Neural Information Processing Systems (NeurIPS), p. 3660–3670. Cited by: §4. Javanmard and Montanari (2018) A. Javanmard and A. Montanari Online rules for control of false discovery rate and false discovery exceedance. The Annals of Statistics 46 (2), p. 526–554. Cited by: §4. Kriegeskorte et al. (2009) N. Kriegeskorte, W. K. Simmons, P. S. F. Bellgowan, and C. I. Baker Circular analysis in systems neuroscience: the dangers of double dipping. Nature Neuroscience 12 (5), p. 535–540. Cited by: §1. Kwon et al. (2023) W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. E. Gonzalez, H. Zhang, and I. Stoica Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Principles (SOSP), p. 611–626. Cited by: §B.2. Lan and DeMets (1983) K. K. G. Lan and D. L. DeMets Discrete sequential boundaries for clinical trials. Biometrika 70 (3), p. 659–663. Cited by: §4. Lu et al. (2024) C. Lu, C. Lu, R. T. Lange, J. Foerster, J. Clune, and D. Ha The AI scientist: towards fully automated open-ended scientific discovery. Note: arXiv preprint arXiv:2408.06292 Cited by: §1. Manheim and Garrabrant (2018) D. Manheim and S. Garrabrant Categorizing variants of Goodhart’s law. Note: arXiv preprint arXiv:1803.04585 Cited by: §1. Maurer and Pontil (2009) A. Maurer and M. Pontil Empirical bernstein bounds and sample variance penalization. In Proceedings of the 22nd Annual Conference on Learning Theory (COLT), Cited by: §4. Mittal and Gupta (2026) A. Mittal and D. Gupta Signed compression progress on a sealed audit is goodhart-resistant. Note: arXiv preprint arXiv:2606.11417 Cited by: §4. Novikov et al. (2025) A. Novikov, N. Vũ, M. Eisenberger, E. Dupont, P. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. R. Ruiz, A. Mehrabian, et al. AlphaEvolve: a coding agent for scientific and algorithmic discovery. Note: arXiv preprint arXiv:2506.13131 Cited by: §B.3, §1, §3.1, §4. OpenAI (2025) OpenAI Our updated preparedness framework. Note: OpenAI Cited by: §5. Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and É. Duchesnay Scikit-learn: machine learning in Python. Journal of Machine Learning Research 12 (85), p. 2825–2830. Cited by: §3.1. Ramdas et al. (2023) A. Ramdas, P. Grünwald, V. Vovk, and G. Shafer Game-theoretic statistics and safe anytime-valid inference. Statistical Science 38 (4), p. 576–601. Cited by: §4. Rank et al. (2026) B. Rank, H. Bhatnagar, A. Prabhu, S. Eisenberg, K. Nguyen, M. Bethge, and M. Andriushchenko PostTrainBench: can LLM agents automate LLM post-training?. In International Conference on Machine Learning (ICML), Cited by: §1. Recht et al. (2019) B. Recht, R. Roelofs, L. Schmidt, and V. Shankar Do ImageNet classifiers generalize to ImageNet?. In Proceedings of the 36th International Conference on Machine Learning (ICML), p. 5389–5400. Cited by: §1, §4. Robeyns et al. (2025) M. Robeyns, M. Szummer, and L. Aitchison A self-improving coding agent. In ICLR Workshop on Scaling Self-Improving Foundation Models without Human Supervision, Cited by: §B.3, §1, §3.1, §4. Roelofs et al. (2019) R. Roelofs, V. Shankar, B. Recht, S. Fridovich-Keil, M. Hardt, J. Miller, and L. Schmidt A meta-analysis of overfitting in machine learning. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §4. Russo and Zou (2016) D. Russo and J. Zou Controlling bias in adaptive data analysis using information theory. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS), p. 1232–1240. Cited by: §4. Schmidhuber (2007) J. Schmidhuber Gödel machines: fully self-referential optimal universal self-improvers. In Artificial General Intelligence, p. 199–226. Cited by: §4. Sengupta (2026) B. Sengupta Self-evolving agents with anytime-valid certificates. Note: arXiv preprint arXiv:2607.00871 Cited by: §1, §4. Shawn (2026) Z. Shawn PACE: anytime-valid acceptance tests for self-evolving agents. Note: arXiv preprint arXiv:2606.08106 Cited by: §1, §1, §3.1, §4. Skalse et al. (2022) J. Skalse, N. H. R. Howe, D. Krasheninnikov, and D. Krueger Defining and characterizing reward hacking. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1. Tian and Ramdas (2021) J. Tian and A. Ramdas Online control of the familywise error rate. Statistical Methods in Medical Research 30 (4), p. 976–993. Cited by: §1. Wang et al. (2026a) C. L. Wang, K. Dorchen, and P. Jin On the statistical limits of self-improving agents. Transactions on Machine Learning Research. Cited by: §4. Wang et al. (2026b) W. Wang, P. Piękos, L. Nanbo, F. Laakom, Y. Chen, M. Ostaszewski, M. Zhuge, and J. Schmidhuber Huxley-Gödel Machine: human-level coding agent development by an approximation of the optimal self-improving machine. In International Conference on Learning Representations (ICLR), Cited by: §1. Wang et al. (2026c) Y. Wang, H. Zhu, Z. Hu, Y. Yuan, Z. Chen, S. Senthil, H. Hajishirzi, Y. Tsvetkov, P. Dasigi, and T. Xiao Rethinking the evaluation of harness evolution for agents. In COLM Workshop on Lifelong Agents: Learning, Aligning, and Evolving, Cited by: §1, §1, §4. Waudby-Smith and Ramdas (2024) I. Waudby-Smith and A. Ramdas Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology 86 (1), p. 1–27. Cited by: §4. Wu et al. (2025) X. Wu, S. Yin, Y. Kang, X. Zhang, Q. Xu, Z. Chen, and W. Zhang SGM: a statistical Godel machine for risk-controlled recursive self-modification. Note: arXiv preprint arXiv:2510.10232 Cited by: §1, §3.1, §4. Xu and Raginsky (2017) A. Xu and M. Raginsky Information-theoretic analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §4. Xu et al. (2026) Y. Xu, J. Zhang, H. Sun, Z. Zhou, T. Cao, and V. Aggarwal Towards reliable LLM evaluation: correcting the winner’s curse in adaptive benchmarking. Note: arXiv preprint arXiv:2605.05973 Cited by: 1st item. Yang et al. (2024) A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, et al. Qwen2.5 technical report. Note: arXiv preprint arXiv:2412.15115 Cited by: §B.2, §3.1. Zelikman et al. (2024) E. Zelikman, E. Lorch, L. Mackey, and A. T. Kalai Self-taught optimizer (STOP): recursively self-improving code generation. In Conference on Language Modeling (COLM), Cited by: §1, §4. Zhang et al. (2026) J. Zhang, S. Hu, C. Lu, R. Lange, and J. Clune Darwin Gödel Machine: open-ended evolution of self-improving agents. In International Conference on Learning Representations (ICLR), Cited by: §B.3, §1, §3.1, §4. Appendix A Proofs and Additional Theory A.1 A paired lower confidence bound for bounded scores We first give a lower confidence bound for the mean of bounded paired differences. This result is used for non-binary scores and as one component of the certificate for pass/fail evaluation. Let z1,…,zn∈[−1,1]z_1,…,z_n∈[-1,1]. Write z¯=1n∑i=1nzi,z2¯=1n∑i=1nzi2. z= 1n _i=1^nz_i, z^2= 1n _i=1^nz_i^2. Here kl(a∥b)=aln(a/b)+(1−a)ln((1−a)/(1−b))kl(a\,\|\,b)=a (a/b)+(1-a) ((1-a)/(1-b)) is the Bernoulli relative entropy, with the usual continuous extensions at the endpoints. All logarithms are natural. For L>0L>0, define s^+(z;L)=maxq∈[z2¯,1]:nkl(z2¯∥q)≤L, s^+(z;L)= \q∈[ z^2,1]:n\,kl( z^2\,\|\,q)≤ L \, (5) and ε⁡(v,L)=2L3n+(2L3n)2+2vLn. (v,L)= 2L3n+ ( 2L3n )^2+ 2vLn. (6) We use the lower bound lcb⁡(z,L)=z¯−ε⁡(s^+(z,L),L).lcb(z;L)= z- ( s^+(z;L),L). (7) The quantity s^+(z,L) s^+(z;L) is an upper confidence bound for Z2EZ^2, which in turn upper bounds Var⁡(Z)Var(Z). The second term in (7) is a Bernstein deviation evaluated at this data-dependent variance proxy. Lemma A1 (Paired lower confidence bound). Let Z1,…,ZnZ_1,…,Z_n be i.i.d. random variables in [−1,1][-1,1] with mean μ. For δ∈(0,1)δ∈(0,1) and L=ln⁡(2/δ)L= (2/δ), ℙ(μ<lcb(Z1:n;L))≤δ.P\! (μ<lcb(Z_1:n;L) )≤δ. Proof. Let m=Z12,σ2=Var⁡(Z1)≤m.m=EZ_1^2, σ^2=Var(Z_1)≤ m. Since Zi2∈[0,1]Z_i^2∈[0,1] are i.i.d. with mean m, applying the Chernoff–Hoeffding bound to 1−Zi21-Z_i^2 (Hoeffding, 1963) gives ℙ(Z2¯≤a)≤exp−nkl(a∥m),0≤a<m.P\! ( Z^2≤ a )≤ \-nkl(a\,\|\,m)\, 0≤ a<m. For a=0a=0 and m<1m<1, the same bound follows from ℙ⁡(Zi2=0)≤1−mP(Z_i^2=0)≤ 1-m and independence. If m=1m=1, then Zi2=1Z_i^2=1 almost surely, so the probability is zero for every a<1a<1, consistent with the convention exp⁡(−∞)=0 (-∞)=0. By the definition of s^+ s^+, ℙ⁡(s^+<m)≤e−L=δ/2.P( s^+<m)≤ e^-L=δ/2. Next, the centered variables satisfy Zi−μ≤2Z_i-μ≤ 2. Bernstein’s inequality (Hoeffding, 1963), with range parameter b=2b=2, gives, for every ϵ>0ε>0, ℙ⁡(Z¯−μ≥ϵ)≤exp⁡−nϵ22σ2+43ϵ.P( Z-μ≥ε)≤ \! \- nε^22σ^2+ 43ε \. If σ2=0σ^2=0, the left-hand side is zero and the inequality remains valid. The positive solution of nϵ2=L⁡(2σ2+43ϵ)nε^2=L (2σ^2+ 43ε ) is ε⁡(σ2,L) (σ^2,L). Hence ℙ⁡(Z¯−μ≥ε⁡(σ2,L))≤e−L=δ/2.P\! ( Z-μ≥ (σ^2,L) )≤ e^-L=δ/2. The function ε⁡(v,L) (v,L) is increasing in v. On the event s^+≥m\ s^+≥ m\, ε⁡(s^+,L)≥ε⁡(m,L)≥ε⁡(σ2,L). ( s^+,L)≥ (m,L)≥ (σ^2,L). Therefore μ<lcb(Z1:n;L)⊆s^+<m∪Z¯−μ>ε(σ2,L). \μ<lcb(Z_1:n;L) \ \ s^+<m\∪ \ Z-μ> (σ^2,L) \. The two probabilities sum to at most δ. ∎ A.2 Validity of the exact paired sign test For pass/fail evaluation, Zi∈−1,0,+1.Z_i∈\-1,0,+1\. Let q+=ℙ⁡(Zi=+1),q−=ℙ⁡(Zi=−1),d=q++q−.q_+=P(Z_i=+1), q_-=P(Z_i=-1), d=q_++q_-. The population gain is μ=Zi=q+−q−.μ=EZ_i=q_+-q_-. Recall that n+n_+ and n−n_- denote the number of candidate wins and losses and M=n++n−.M=n_++n_-. The paired sign-test p-value is π⁡(n+,M)=ℙ⁡(Bin⁡(M,12)≥n+),π⁡(0,0)=1.π(n_+,M)=P\! (Bin(M, 12)≥ n_+ ), π(0,0)=1. Lemma A2 (Validity of the exact paired test). Let Z1,…,ZnZ_1,…,Z_n be i.i.d. in −1,0,+1\-1,0,+1\ with mean μ≤0μ≤ 0. For any δ′∈(0,1)δ ∈(0,1), ℙ⁡(π⁡(n+,M)≤δ′)≤δ′.P\! (π(n_+,M)≤δ )≤δ . The same inequality holds conditionally on every value of M. Proof. If d=0d=0, then M=0M=0 almost surely and π⁡(0,0)=1π(0,0)=1. The test never rejects. Assume d>0d>0 and define q=q+d=ℙ⁡(Zi=+1∣Zi≠0).q= q_+d=P(Z_i=+1 Z_i≠ 0). By independence, (n+,n−,n−M)(n_+,n_-,n-M) has the multinomial distribution with cell probabilities (q+,q−,1−d)(q_+,q_-,1-d). For 0≤k≤m≤n0≤ k≤ m≤ n, its probability mass factors as ℙ⁡(M=m,n+=k) (M=m,n_+=k) =(nm)(mk)q+kq−m−k(1−d)n−m = nm mkq_+^kq_-^m-k(1-d)^n-m =ℙ⁡(M=m)(mk)qk(1−q)m−k. =P(M=m) mkq^k(1-q)^m-k. Thus, for every m with ℙ⁡(M=m)>0P(M=m)>0, n+|M=m∼Bin⁡(m,q)n_+ M=m (m,q). The null hypothesis μ≤0μ≤ 0 is equivalent to q≤1/2q≤ 1/2. Fix such an m. Under the null, Bin⁡(m,q)Bin(m,q) is stochastically dominated by Bin⁡(m,1/2)Bin(m,1/2), so the rejection probability of the upper-tail sign test is maximized over q≤1/2q≤ 1/2 at q=1/2q=1/2. Indeed, if there is a rejection threshold, let k0k_0 be the smallest integer in 0,…,m\0,…,m\ with π⁡(k0,m)≤δ′π(k_0,m)≤δ . Monotonicity of π⁡(k,m)π(k,m) in k then gives ℙ⁡(π⁡(n+,M)≤δ′∣M=m) \! (π(n_+,M)≤δ M=m ) =ℙ⁡(n+≥k0∣M=m) =P\! (n_+≥ k_0 M=m ) ≤ℙ⁡(Bin⁡(m,12)≥k0)=π⁡(k0,m)≤δ′. \! (Bin(m, 12)≥ k_0 )=π(k_0,m)≤δ . If there is no rejection threshold, the rejection probability is zero. For m=0m=0 it is also zero. Averaging over M proves the unconditional claim. ∎ A.3 A lower confidence bound for pass/fail evaluation For d>0d>0, define q=q+d.q= q_+d. Then μ=q+−q−=(2q−1)d,Zi2=d.μ=q_+-q_-=(2q-1)d, _i^2=d. (8) For k successes in m Bernoulli trials, let θ¯(k,m,a) θ(k;m,a) denote the one-sided Clopper–Pearson lower confidence limit at error level a∈(0,1)a∈(0,1) (Clopper and Pearson, 1934). For 1≤k≤m1≤ k≤ m, it is the a-quantile of Beta⁡(k,m−k+1)Beta(k,m-k+1), and we set θ¯(0,m,a)=0 θ(0;m,a)=0. Given an error level δc∈(0,1) _c∈(0,1), define qlo=θ¯(n+,M,δc/4),dlo=θ¯(M,n,δc/4),q_lo= θ(n_+;M, _c/4), d_lo= θ(M;n, _c/4), and ℓsgn=(2qlo−1)dlo,qlo>1/2,−∞,qlo≤1/2. ^sgn= cases(2q_lo-1)d_lo,&q_lo>1/2,\\[5.69054pt] -∞,&q_lo≤ 1/2. cases (9) We combine this exact bound with the bounded-score lower confidence bound from Lemma A1: ℓ⋆(Z1:n;δc)=maxlcb(Z1:n;ln4δc),ℓsgn. (Z_1:n; _c)= \lcb (Z_1:n; 4 _c ), ^sgn \. (10) Lemma A3 (Lower confidence bound for pass/fail evaluation). For i.i.d. Z1,…,Zn∈−1,0,+1Z_1,…,Z_n∈\-1,0,+1\ with mean μ, ℙ⁡(μ<ℓsgn)≤δc2,P(μ< ^sgn)≤ _c2, and ℙ(μ<ℓ⋆(Z1:n;δc))≤δc.P\! (μ< (Z_1:n; _c) )≤ _c. Proof. If d=0d=0, then M=n+=0M=n_+=0 almost surely, so qlo=0q_lo=0 and ℓsgn=−∞ ^sgn=-∞. The first claim is immediate, and the second follows from Lemma A1. Assume henceforth that d>0d>0. By the conditional-count calculation in the proof of Lemma A2, the conditional law of n+n_+ given M=mM=m is Bin⁡(m,q)Bin(m,q) whenever ℙ⁡(M=m)>0P(M=m)>0. Applying the one-sided Clopper–Pearson coverage property conditionally and then averaging over M gives ℙ⁡(q<qlo)≤δc/4.P(q<q_lo)≤ _c/4. Separately, the indicators Zi≠01\Z_i≠ 0\ are i.i.d. Bernoulli variables with success probability d, so M∼Bin⁡(n,d)M (n,d). Applying the same coverage property directly to this count gives ℙ⁡(d<dlo)≤δc/4.P(d<d_lo)≤ _c/4. Therefore, with probability at least 1−δc/21- _c/2, q≥qlo,d≥dlo.q≥ q_lo, d≥ d_lo. On this event, when qlo>1/2q_lo>1/2, μ=(2q−1)d≥(2qlo−1)dlo=ℓsgn.μ=(2q-1)d≥(2q_lo-1)d_lo= ^sgn. When qlo≤1/2q_lo≤ 1/2, the bound equals −∞-∞ and the inequality holds automatically. Hence ℙ⁡(μ<ℓsgn)≤δc/2.P(μ< ^sgn)≤ _c/2. By Lemma A1, ℙ(μ<lcb(Z1:n;ln4δc))≤δc/2.P (μ<lcb (Z_1:n; 4 _c ) )≤ _c/2. A union bound over the two lower confidence bounds gives ℙ(μ<ℓ⋆(Z1:n;δc))≤δc.P\! (μ< (Z_1:n; _c) )≤ _c. ∎ Remark A1 (Running cumulative bound). The sign test may establish that μ>0μ>0 even when the numerical lower confidence bound ℓ⋆ is non-positive. For the pass/fail test with γ=0γ=0, Reuse therefore adds max⁡ℓ⋆,0 \ ,0\ to the running bound CtC_t. On the event of Theorem 1, both Δ⁡(At,At−1)>0 (A_t,A_t-1)>0 and Δ⁡(At,At−1)≥ℓ⋆ (A_t,A_t-1)≥ hold. Hence Δ⁡(At,At−1)≥max⁡ℓ⋆,0. (A_t,A_t-1)≥ \ ,0\. This keeps CtC_t nondecreasing while preserving its lower-bound interpretation. For the bounded-score extension, promotion requires ℓ>γ≥0 >γ≥ 0, and the contribution is ℓ itself. A.4 Proof of the main guarantee We prove Theorem 1 for general allocation weights (wt)(w_t) and (vp)(v_p) satisfying ∑t≥1wt≤1,∑p≥0vp≤1. _t≥ 1w_t≤ 1, _p≥ 0v_p≤ 1. For pass/fail evaluation with γ=0γ=0, let ρ∈(0,1)ρ∈(0,1) denote the fraction of δt,p _t,p used for the promotion test; the remaining fraction is used for the lower confidence bound. The proof applies to every such ρ. If δt,p=0 _t,p=0, all candidates are rejected and the running bound is unchanged. Such comparisons can be omitted from the argument below. Proof of Theorem 1. Condition on the search procedure’s randomness R, development data D, and starting system A0A_0. By Assumption 1, S remains i.i.d. from Q. All probabilities in this proof are conditional on (R,D,A0)(R,D,A_0). For round t, let y=y1:t−1y=y_1:t-1 denote a possible decision history. By Assumption 2, every such history determines an incumbent a⁡(y)a(y) and candidates b1(y),…,bK(y)b_1(y),…,b_K(y) that do not otherwise depend on S. Here y is a fixed hypothetical history: we do not condition on the event that the evaluation set produces that history. Let t−1,pY_t-1,p be the set of decision histories of length t−1t-1 containing exactly p promotions. Then |t−1,p|=(t−1p)Kp.|Y_t-1,p|= t-1pK^p. (11) The factor (t−1p) t-1p selects the promotion rounds and the factor KpK^p selects the promoted candidate at each such round. Fix t, p, y∈t−1,py _t-1,p, and candidate k. Write μy,k=Δ⁡(bk(y),a⁡(y)). _y,k= (b_k(y),a(y)). In what follows, Z1:nZ_1:n, n+n_+, and M refer to this fixed pair (bk(y),a(y))(b_k(y),a(y)). For pass/fail evaluation with γ=0γ=0, define the decision failure event Et,y,kdec=μy,k≤0∩π(n+,M)≤ρδt,p,E^dec_t,y,k=\ _y,k≤ 0\∩ \π(n_+,M)≤ρ _t,p \, and the confidence-bound failure event Et,y,kcert=μy,k<ℓ⋆(Z1:n;(1−ρ)δt,p).E^cert_t,y,k= \ _y,k< (Z_1:n;(1-ρ) _t,p ) \. By Lemma A2, ℙ⁡(Et,y,kdec)≤ρδt,p,P(E^dec_t,y,k)≤ρ _t,p, and by Lemma A3, ℙ⁡(Et,y,kcert)≤(1−ρ)δt,p.P(E^cert_t,y,k)≤(1-ρ) _t,p. Set Et,y,k=Et,y,kdec∪Et,y,kcertE_t,y,k=E^dec_t,y,k∪ E^cert_t,y,k. Then ℙ⁡(Et,y,k)≤δt,p.P(E_t,y,k)≤ _t,p. For the bounded-score extension, define instead Et,y,k=μy,k<lcb(Z1:n;ℒt,p).E_t,y,k= \ _y,k<lcb(Z_1:n;L_t,p) \. By Lemma A1, ℙ⁡(Et,y,k)≤δt,p.P(E_t,y,k)≤ _t,p. Now sum over every round, promotion count, decision history, and candidate. Using (4) and (11), ℙ⁡(⋃t,p,y,kEt,y,k) ( _t,p,y,kE_t,y,k ) ≤∑t≥1∑p=0t−1(t−1p)Kp⋅K⋅δt,p ≤ _t≥ 1 _p=0^t-1 t-1pK^p· K· _t,p (12) =α∑t≥1wt∑p=0t−1vp =α _t≥ 1w_t _p=0^t-1v_p (13) ≤α. ≤α. (14) Therefore, with probability at least 1−α1-α, every candidate comparison that can arise under every possible decision history is valid simultaneously. Consider the realized sequence. If yt=k≠0y_t=k≠ 0, the promoted candidate passed the promotion test. On the event above, with γ=0γ=0 for the sign-test route and any γ≥0γ≥ 0 for the bounded-score route, Δ⁡(At,At−1)>γ, (A_t,A_t-1)>γ, which proves the first claim. The same event also gives Δ⁡(At,At−1)≥max⁡ℓt,γ (A_t,A_t-1)≥ \ _t,γ\ at every promoted round, where ℓt _t denotes the lower bound used for the promoted comparison. Summing over promoted rounds gives V⁡(At)−V⁡(A0) V(A_t)-V(A_0) =∑s≤t:ys≠0Δ(As,As−1) = _s≤ t:y_s≠ 0 (A_s,A_s-1) (15) ≥∑s≤t:ys≠0maxℓs,γ ≥ _s≤ t:y_s≠ 0 \ _s,γ\ (16) =Ct. =C_t. (17) This proves the cumulative lower bound for each fixed ξ=(R,D,A0)ξ=(R,D,A_0). By the joint measurability in Assumption 2, the failure events used above, for each fixed hypothetical history, are measurable as functions of (ξ,S)(ξ,S). Their union over rounds and histories is a countable union of measurable sets. Since S and ξ are independent by Assumption 1, integrating the section-wise probability bound with respect to the law of ξ gives the unconditional statement. ∎ A.5 A direct lower bound against the starting system The running bound CtC_t adds one lower confidence bound for each promoted modification. We can also compare the current system AtA_t directly with the starting system A0A_0. This produces a second lower bound on total progress from the same stored evaluations. Let αc∈(0,1) _c∈(0,1) be a separate error level. For a decision history of length t containing p promotions, define δt,pc=αcwtvp(tp)Kp,ℒt,pc=ln⁡2δt,pc.δ^c_t,p= _cw_tv_p tpK^p, ^c_t,p= 2δ^c_t,p. (18) When pt≥1p_t≥ 1, define Dt=ℓ⋆(Z1:n(At,A0);δt,ptc),D_t= (Z_1:n(A_t,A_0);δ^c_t,p_t ), (19) for pass/fail outcomes. For general bounded scores, use Dt=lcb(Z1:n(At,A0);ℒt,ptc)D_t=lcb(Z_1:n(A_t,A_0);L^c_t,p_t) from Lemma A1 instead. If pt≥1p_t≥ 1 and δt,ptc=0δ^c_t,p_t=0, set Dt=−∞D_t=-∞. When pt=0p_t=0, set Dt=0,D_t=0, since At=A0A_t=A_0 exactly. Proposition A1 (Direct lower bound on total progress). Under Assumptions 1 and 2, with probability at least 1−αc1- _c, V⁡(At)−V⁡(A0)≥Dtfor all t≥1.V(A_t)-V(A_0)≥ D_t all t≥ 1. Under development-set screening, the same result holds with the factor KpK^p removed from (18). In the pass/fail setting with γ=0γ=0, under the conditions of Theorem 1, we additionally have V⁡(At)−V⁡(A0)≥max⁡Ct,DtV(A_t)-V(A_0)≥ \C_t,D_t\ for all t with probability at least 1−α−αc1-α- _c. Proof. Condition on (R,D,A0)(R,D,A_0) as in the proof of Theorem 1. Probabilities below are conditional on this tuple. A complete decision history y=y1:ty=y_1:t determines the current system at(y)a_t(y). If the history contains exactly p promotions, then there are (tp)Kp tpK^p such histories. For each history with p≥1p≥ 1, define Ft,y=Δ(at(y),A0)<ℓ⋆(Z1:n(at(y),A0);δt,pc).F_t,y= \ (a_t(y),A_0)< (Z_1:n(a_t(y),A_0);δ^c_t,p ) \. For each fixed hypothetical history y, the pair (at(y),A0)(a_t(y),A_0) is fixed given (R,D,A0)(R,D,A_0) and does not otherwise depend on S. We do not condition on observing y. Thus ℙ⁡(Ft,y)≤δt,pc.P(F_t,y)≤δ^c_t,p. For bounded scores, replace ℓ⋆ by the bound from Lemma A1; the same error bound holds. When p=0p=0, no promotion has occurred and at(y)=A0a_t(y)=A_0, so the desired inequality holds deterministically; set Ft,y=∅F_t,y= for these histories. The failure event is also empty when the error allotment is zero. A union bound gives ℙ⁡(⋃t,p,yFt,y) ( _t,p,yF_t,y ) ≤∑t≥1∑p=0t(tp)Kpδt,pc ≤ _t≥ 1 _p=0^t tpK^pδ^c_t,p (20) =αc∑t≥1wt∑p=0tvp = _c _t≥ 1w_t _p=0^tv_p (21) ≤αc. ≤ _c. (22) The result follows for the realized decision history. Integrating over (R,D,A0)(R,D,A_0) gives the unconditional statement. Under development screening, a history is determined only by its promotion rounds, giving (tp) tp possible histories and removing KpK^p. The joint statement follows from a union bound over the events of Theorem 1 and this proposition. ∎ Corollary A1 (Carry-forward between promotions). Suppose pt≥1p_t≥ 1 and let s⁡(t)=max⁡s≤t:ys≠0s(t)= \s≤ t:y_s≠ 0\ be the most recent promotion round. On the event of Proposition A1, V⁡(At)−V⁡(A0)≥Ds⁡(t).V(A_t)-V(A_0)≥ D_s(t). Hence the direct lower bound only needs to be recomputed when a promotion occurs. Proof. No promotion occurs between rounds s⁡(t)s(t) and t, so At=As⁡(t).A_t=A_s(t). Apply Proposition A1 at round s⁡(t)s(t). ∎ Comparison with the running bound. The two bounds summarize cumulative progress differently. The running quantity CtC_t adds one confidence bound for each promoted step. The direct quantity DtD_t bounds the single comparison between AtA_t and A0A_0. When several promotions accumulate, DtD_t can be substantially tighter because it pays one confidence margin rather than one margin for every promotion. Neither bound dominates in every configuration, so both can be reported under their respective error levels. A.6 Power and the minimum detectable improvement We next characterize the amount of population gain required to pass the promotion test for fixed comparisons. The pairs below are fixed independently of S. Equivalently, one may fix (R,D,A0)(R,D,A_0) and a hypothetical decision history as in the proof of Theorem 1. These power statements are not conditional on reaching that history in an adaptive run. Proposition A2 (Power of the promotion tests). Consider a fixed candidate–incumbent pair tested at round t after p promotions, with i.i.d. paired differences Z1,…,ZnZ_1,…,Z_n, population gain Δ , paired second moment m=Z2,m=EZ^2, and variance σ2σ^2. Let L=ℒt,p,β∈(0,1).L=L_t,p, β∈(0,1). (a) For the Bernstein–KL test, define Lβ=ln⁡2β,L_β= 2β, mβ=m+2mLβn+2Lβ3n,m_β=m+ 2mL_βn+ 2L_β3n, and u=mβ+2mβLn+2Ln.u=m_β+ 2m_βLn+ 2Ln. If Δ>γ+ε⁡(u,L)+ε⁡(σ2,Lβ), >γ+ (u,L)+ (σ^2,L_β), then this candidate passes the bounded-score promotion test with probability at least 1−β1-β. For pass/fail tasks with fixed d=ℙ⁡(Zi≠0)>0d=P(Z_i≠ 0)>0, the right-hand side of the sufficient condition above is γ+2dLn(1+o(1))γ+ 2dLn(1+o(1)) when n→∞n→∞, L→∞L→∞, L=o⁡(n)L=o(n), and Lβ=o⁡(L)L_β=o(L). (b) For the exact paired sign test with γ=0γ=0 and ρ=1/2ρ=1/2, define c⁡(M,L)=min⁡a∈0,1,…,M:ℙ⁡(Bin⁡(M,12)≥a)≤e−L,c(M,L)= \a∈\0,1,…,M\:P\! (Bin(M, 12)≥ a )≤ e^-L \, with c⁡(M,L)=∞c(M,L)=∞ when the set is empty. A candidate passes if and only if n+≥c⁡(M,L).n_+≥ c(M,L). For M≥1M≥ 1 and n+≥M/2n_+≥ M/2, Mkl(n+M∥12)≥L⟹pass⟹Mkl(n+M∥12)≥L−12ln⁡(2M).Mkl ( n_+M\, \|\, 12 )≥ L Mkl ( n_+M\, \|\, 12 )≥ L- 12 (2M). (23) In particular, for M≥1M≥ 1, n+−n−≥2LMn_+-n_-≥ 2LM is sufficient for promotion. Proof. For part (a), apply Bernstein’s inequality (Hoeffding, 1963) to Yi=Zi2∈[0,1]Y_i=Z_i^2∈[0,1]. Here Yi−m≤1Y_i-m≤ 1, so the range parameter is b=1b=1, and Var⁡(Yi)≤Zi4≤Zi2=m.Var(Y_i) _i^4 _i^2=m. Inverting the resulting tail bound, and using u+v≤u+v u+v≤ u+ v for u,v≥0u,v≥ 0, gives Z2¯≤m+2mLβn+2Lβ3n=mβ Z^2≤ m+ 2mL_βn+ 2L_β3n=m_β with probability at least 1−β/21-β/2. Applying the same Bernstein inequality to −Zi-Z_i, now with b=2b=2 and variance σ2σ^2, gives Z¯≥Δ−ε⁡(σ2,Lβ) Z≥ - (σ^2,L_β) with probability at least 1−β/21-β/2. The inequality kl(a∥q)≥(q−a)22q,q≥a,kl(a\,\|\,q)≥ (q-a)^22q, q≥ a, together with the definition of s^+ s^+ implies s^+≤Z2¯+2Z2¯Ln+2Ln≤u. s^+≤ Z^2+ 2 Z^2Ln+ 2Ln≤ u. On the intersection of the two high-probability events, ℓ≥Δ−ε⁡(σ2,Lβ)−ε⁡(u,L)>γ. ≥ - (σ^2,L_β)- (u,L)>γ. Hence the candidate passes. The asymptotic expression follows from ε⁡(u,L)=2mLn(1+o⁡(1)). (u,L)= 2mLn(1+o(1)). For part (b), the test level is ρδt,p=δt,p2=e−L.ρ _t,p= _t,p2=e^-L. Monotonicity of the binomial upper tail gives the characterization through c⁡(M,L)c(M,L). When M=0M=0, c⁡(M,L)=∞c(M,L)=∞ and the test cannot pass; the following calculations assume M≥1M≥ 1. For n+≥M/2n_+≥ M/2, the Chernoff–Hoeffding bound (Hoeffding, 1963) gives ℙ⁡(Bin⁡(M,12)≥n+)≤exp⁡−Mkl(n+M∥12).P\! (Bin(M, 12)≥ n_+ )≤ \! \-Mkl\! ( n_+M\, \|\, 12 ) \. The boundary n+=M/2n_+=M/2 follows from the trivial probability bound by one, and n+=Mn_+=M gives equality. This proves the first implication in (23). The binomial point-mass bound (29) gives, for every integer 0≤a≤M0≤ a≤ M, ℙ⁡(Bin⁡(M,12)=a)≥exp−Mkl(a/M∥ 1/2)2M.P\! (Bin(M, 12)=a )≥ \-Mkl(a/M\,\|\,1/2)\ 2M. If the candidate passes, then exp−Mkl(n+/M∥ 1/2)2M≤ℙ⁡(Bin⁡(M,12)=n+)≤π⁡(n+,M)≤e−L. \-Mkl(n_+/M\,\|\,1/2)\ 2M \! (Bin(M, 12)=n_+ )≤π(n_+,M)≤ e^-L. Taking logarithms yields Mkl(n+/M∥ 1/2)≥L−12ln(2M)Mkl(n_+/M\,\|\,1/2)≥ L- 12 (2M), which is the second implication in (23). Finally, write n+=M+x2,x=n+−n−.n_+= M+x2, x=n_+-n_-. For u=x/(2M)u=x/(2M) with |u|<1/2|u|<1/2, 2u2≤kl⁡(12+u∥12)≤2u21−4u2.2u^2 ( 12+u\, \|\, 12 )≤ 2u^21-4u^2. (24) The lower inequality extends to u=±1/2u=± 1/2 by continuity and gives Mkl(n+M∥12)≥x22M.Mkl ( n_+M\, \|\, 12 )≥ x^22M. Thus x≥2LMx≥ 2LM is sufficient for promotion. ∎ Asymptotic conditions for Proposition 1. Let n→∞n→∞, keep K and d∈(0,1]d∈(0,1] fixed, and set L=ℒt,pL=L_t,p with ln⁡n=o⁡(L) n=o(L) and L=o⁡(n)L=o(n). The round and promotion count may vary with n. All candidate–incumbent pairs are fixed independently of S; in the K-candidate statement, each pair has the same probability d of different outcomes. Candidates need not be independent of one another. Proof of Proposition 1. Let x=∑i=1nZi=n+−n−,M=∑i=1nZi2.x= _i=1^nZ_i=n_+-n_-, M= _i=1^nZ_i^2. For pass/fail outcomes, x=nΔ,Var⁡(x)≤nd,Ex=n , (x)≤ nd, and M=nd,Var⁡(M)≤nd.EM=nd, (M)≤ nd. Hence x=nΔ+OP(nd),x=n +O_P( nd), and M=nd(1+OP((nd)−1/2)).M=nd (1+O_P((nd)^-1/2) ). Let τ=2Lnd.τ= 2Lnd. Then Δmin=2dLn=τn. _ = 2dLn= τn. Since L→∞L→∞, τnd=2L→∞. τ nd= 2L→∞. Therefore the stochastic fluctuations in x and M are oP(τ)o_P(τ). If Δ≥(1+η)Δmin, ≥(1+η) _ , then x≥(1+η)τ−oP(τ),x≥(1+η)τ-o_P(τ), while 2LM=τ⁡(1+oP(1)). 2LM=τ(1+o_P(1)). Thus the sufficient condition in Proposition A2(b) holds with probability tending to one. If Δ≤(1−η)Δmin, ≤(1-η) _ , then x≤(1−η)τ+oP(τ).x≤(1-η)τ+o_P(τ). On x≤0\x≤ 0\ the test cannot pass. On x>0\x>0\, the preceding upper bound on x, together with M/(nd)→P1M/(nd) _P1 and L=o⁡(n)L=o(n), gives x/M=oP(1)x/M=o_P(1) on this event. Using (24), Mkl(n+M∥12)=x22M(1+oP(1)).Mkl ( n_+M\, \|\, 12 )= x^22M(1+o_P(1)). A pass would require x2≥2M(L−12ln⁡(2M))(1+oP(1))=τ2(1+oP(1)),x^2≥ 2M (L- 12 (2M) )(1+o_P(1))=τ^2(1+o_P(1)), where ln⁡(2M)L→0 (2M)L→ 0 by ln⁡n=o⁡(L) n=o(L). This contradicts x2≤(1−η+oP(1))2τ2x^2≤ (1-η+o_P(1) )^2τ^2 with probability tending to one. For fixed K, a union bound over the fixed candidate–incumbent pairs completes the second claim. ∎ A.7 Lower bound for threshold-based promotion rules We now show that the dependence on promotion history identified in the main text also appears as a lower bound for a natural class of promotion rules. The construction uses a bounded-score model satisfying Assumptions 1 and 2 exactly. A.7.1 Model and threshold gates Model M. A task is an infinite sign sequence W=(g1,g2,…)∈−1,+1ℕ,W=(g_1,g_2,…)∈\-1,+1\^N, whose coordinates are independent Rademacher variables. A system is a pair A=(ϑ,β),A=( ,β), where ϑ∈[−1/4,1/4],β∈ℝℕ,∥β∥1≤1/4, ∈[-1/4,1/4], β ^N, \|β\|_1≤ 1/4, and β has finite support. Define s⁡(A,W)=12+ϑ+∑jβjgj.s(A,W)= 12+ + _j _jg_j. (25) The score lies in [0,1][0,1] and V⁡(A)=12+ϑ.V(A)= 12+ . Hence Δ⁡(B,A)=ϑB−ϑA. (B,A)= _B- _A. Changing only β leaves population value unchanged. All constructions below start from A0=(0,0)A_0=(0,0). We write eje_j for the j-th coordinate vector. Let S=(W1,…,Wn)S=(W_1,…,W_n) be the evaluation set. Write gijg_ij for coordinate j of task i, and define Xj=n−1/2∑i=1ngij.X_j=n^-1/2 _i=1^ng_ij. The variables XjX_j are independent standardized Rademacher sums. For any systems A and B, Zi(B,A)=(ϑB−ϑA)+∑j(βB−βA)jgij.Z_i(B,A)=( _B- _A)+ _j( _B- _A)_jg_ij. (26) Coordinates shared by A and B cancel. There is no additional evaluation randomness, so repeated evaluation is deterministic. Definition A1 (Threshold gate). Fix b∈[0,1]b∈[0,1]. For z∈ℝnz ^n, define z¯=1n∑izi,z2¯=1n∑izi2, z= 1n _iz_i, z^2= 1n _iz_i^2, and Tb(z)=nz¯z2¯−bz¯2.T_b(z)= n\, z z^2-b z^2. (27) We set Tb(0)=0T_b(0)=0. When the denominator vanishes and z¯≠0 z≠ 0, set Tb(z)=+∞T_b(z)=+∞ for z¯>0 z>0 and Tb(z)=−∞T_b(z)=-∞ for z¯<0 z<0. A threshold gate is specified by b and deterministic thresholds λt,p≥0. _t,p≥ 0. At round t after p previous promotions, it computes Tk=Tb(Z1:n(Bt,k,At−1)).T_k=T_b (Z_1:n(B_t,k,A_t-1) ). It rejects all candidates when maxk⁡Tk≤2λt,p, _kT_k≤ 2 _t,p, and otherwise promotes a candidate attaining the maximum. The case b=0b=0 standardizes by the empirical second moment. The case b=1b=1 uses the empirical variance with divisor n. All proposers below satisfy Assumptions 1 and 2. They are deterministic and use only previous promotion decisions. We set γ=0γ=0. Let t=a false promotion occurs by round t. F_t=\a false promotion occurs by round t\. Theorem A1 (First-order lower bound). For the threshold-gate class in Definition A1, under the conditions of Corollaries A2 and A3 and the corresponding asymptotic regimes in Remark A3, a proposer that observes only previous promotion decisions can cause a false promotion with probability tending to one if the threshold parameters are uniformly below the first-order scale ln⁡(tK) (tK) before the first promotion, or Pln⁡(Kt/P)P (Kt/P) over the relevant rounds after P promotions, by a fixed multiplicative factor. In the latter regime, the conditions include t=⌊ςP⌋+1t= P +1, ς≥5 ≥ 5, P→∞P→∞, Kς→∞K →∞, ln⁡(Kς)=o⁡(n) (K )=o( n), and Pln⁡(eKς)=o⁡(n)P (eK )=o(n), as well as λs,p<n/34 _s,p<n/34 for every 1≤s≤t−11≤ s≤ t-1 and 0≤p≤min⁡P−1,s−10≤ p≤ \P-1,s-1\, as required by Corollary A3. The two regimes are established separately in Corollaries A2 and A3; the remaining subsections give the corresponding constructions and proofs. A.7.2 Auxiliary lemmas Binomial coefficient and point-mass bounds. For integers n≥2n≥ 2 and 1≤m≤n−11≤ m≤ n-1, (nm)≥expnln2−nkl(m/n∥ 1/2)8m(n−m)/n. nm≥ \n 2-nkl(m/n\,\|\,1/2)\ 8m(n-m)/n. (28) Consequently, for integers M≥1M≥ 1 and 0≤a≤M0≤ a≤ M, ℙ⁡(Bin⁡(M,12)=a)≥exp−Mkl(a/M∥ 1/2)2M.P\! (Bin(M, 12)=a )≥ \-Mkl(a/M\,\|\,1/2)\ 2M. (29) Proof. For integers j≥1j≥ 1, define Aj=j!ejjj+1/2,rj=Aj+1Aj=e(j+1)j+1/2.A_j= j!e^jj^j+1/2, r_j= A_j+1A_j=e ( jj+1 )^j+1/2. The function g⁡(x)=(x+1/2)ln⁡(1+1/x)g(x)=(x+1/2) (1+1/x) satisfies, for x>0x>0, g′(x)=ln⁡(1+1/x)−12(1x+1x+1)<0.g (x)= (1+1/x)- 12 ( 1x+ 1x+1 )<0. Indeed, strict convexity of t↦1/t 1/t gives ∫x+1t−1t<12(x−1+(x+1)−1) _x^x+1t^-1\,dt< 12(x^-1+(x+1)^-1). Thus ln⁡rj=1−g⁡(j) r_j=1-g(j) is increasing in j. For positive integers m,lm,l, set F⁡(m,l)=Am+l/(AmAl)F(m,l)=A_m+l/(A_mA_l). Then F⁡(m+1,l)F⁡(m,l)=rm+lrm≥1, F(m+1,l)F(m,l)= r_m+lr_m≥ 1, and the analogous inequality holds in the second coordinate. Hence F⁡(m,l)≥F⁡(1,1)=A2A12=18.F(m,l)≥ F(1,1)= A_2A_1^2= 1 8. Writing n=m+ln=m+l and expanding the factorials therefore gives (nm)=F⁡(m,l)nmlnnmml≥exp⁡nH(m/n)8ml/n, nm=F(m,l) nml n^nm^ml^l≥ \nH(m/n)\ 8ml/n, where H⁡(x)=−xln⁡x−(1−x)ln⁡(1−x)H(x)=-x x-(1-x) (1-x). Since H(x)=ln2−kl(x∥ 1/2)H(x)= 2-kl(x\,\|\,1/2), this proves (28). For 1≤a≤M−11≤ a≤ M-1, divide (28) by 2M2^M and use a⁡(M−a)≤M2/4a(M-a)≤ M^2/4 to obtain (29). For a=0a=0 or a=Ma=M, both the point mass and exp−Mkl(a/M∥ 1/2) \-Mkl(a/M\,\|\,1/2)\ equal 2−M2^-M, and 2M≥1 2M≥ 1, so the bound still holds. ∎ Lemma A4 (Rademacher tail). Let SnS_n be a sum of n independent Rademacher variables. For n≥64n≥ 64 and 1≤x≤n8,1≤ x≤ n8, ℙ⁡(Sn>xn)≥cRxexp⁡(−x22−(x2+5)29n),P(S_n>x n)≥ c_Rx (- x^22- (x^2+5)^29n ), where cR=e−5/222.c_R= e^-5/22 2. Proof. Let B=Sn+n2∼Bin⁡(n,12).B= S_n+n2 (n, 12). Set m0=⌊n+xn2⌋+1,w=⌊n2x⌋,m1=m0+w.m_0= n+x n2 +1, w= n2x , m_1=m_0+w. Then Sn>xn=B≥m0.\S_n>x n\=\B≥ m_0\. For m≥n/2m≥ n/2, the binomial probability mass is nonincreasing in m, so ℙ⁡(B≥m0)≥(w+1)ℙ(B=m1)≥n2xℙ(B=m1).P(B≥ m_0)≥(w+1)P(B=m_1)≥ n2xP(B=m_1). Applying (28) with m=m1m=m_1, which satisfies 1≤m1≤n−11≤ m_1≤ n-1, and using m1(n−m1)≤n2/4m_1(n-m_1)≤ n^2/4, we obtain ℙ⁡(B=m1)≥e−nkl(m1/n∥ 1/2)2n.P(B=m_1)≥ e^-nkl(m_1/n\,\|\,1/2) 2n. Writing m1/n=(1+v)/2m_1/n=(1+v)/2 and u=nvu= n\,v, the assumptions imply x<u≤x+2n+1x<u≤ x+ 2 n+ 1x and u2≤x2+5.u^2≤ x^2+5. The expansion of the Bernoulli relative entropy gives nkl(1+v2∥12)≤x2+52+(x2+5)29n.nkl ( 1+v2\, \|\, 12 )≤ x^2+52+ (x^2+5)^29n. Combining the inequalities gives the result. ∎ Lemma A5 (Uniform second moment of selected probes). Let n,M,Pn,M,P be positive integers with P≤MP≤ M, and let (gij)i≤n,j≤M(g_ij)_i≤ n,j≤ M be independent Rademacher variables. For J⊆[M]J [M] with |J|=P|J|=P, define QJ=1nP∑i=1n(∑j∈Jgij)2.Q_J= 1nP _i=1^n ( _j∈ Jg_ij )^2. For every ε>0 >0, ℙ⁡(max|J|=P⁡QJ≥1+ε)≤(MP)exp⁡−n2[ε−ln⁡(1+ε)],P ( _|J|=PQ_J≥ 1+ )≤ MP \- n2 [ - (1+ ) ] \, and therefore ℙ⁡(max|J|=P⁡QJ≥1+ε)≤(eMP)Pexp⁡−nε24(1+ε).P ( _|J|=PQ_J≥ 1+ )≤ ( eMP )^P \- n ^24(1+ ) \. Proof. Fix J and set Yi=P−1/2∑j∈Jgij.Y_i=P^-1/2 _j∈ Jg_ij. Then eμYi=cosh⁡(μ/P)P≤eμ2/2.Ee^μ Y_i= (μ/ P)^P≤ e^μ^2/2. If ξ∼N⁡(0,1)ξ N(0,1) is independent, then for 0≤s<1/20≤ s<1/2, esYi2=e2sξYi≤esξ2=(1−2s)−1/2.Ee^sY_i^2=Ee 2sξ Y_i ^sξ^2=(1-2s)^-1/2. Markov’s inequality with s=ε2(1+ε)s= 2(1+ ) gives ℙ⁡(∑iYi2≥n⁡(1+ε))≤exp⁡−n2[ε−ln⁡(1+ε)].P ( _iY_i^2≥ n(1+ ) )≤ \- n2 [ - (1+ ) ] \. Apply a union bound over the (MP) MP possible sets J and use (MP)≤(eM/P)P MP≤(eM/P)^P and ε−ln⁡(1+ε)≥ε22(1+ε). - (1+ )≥ ^22(1+ ). ∎ Lemma A6 (Calibration of a probe round). Let n≥3n≥ 3, b∈[0,1]b∈[0,1], and τ>0τ>0. For r∈[0,1/4]r∈[0,1/4] and x∈[−1,1]x∈[-1,1], define hr(x)=n(r+x)Dr(x),Dr(x)=1+r2+2rx−b(r+x)2.h_r(x)= n(r+x) D_r(x), D_r(x)=1+r^2+2rx-b(r+x)^2. Then the following properties hold. 1. If g∈−1,1ng∈\-1,1\^n has empirical mean x, then Tb(τ⁡(r+g))=hr(x).T_b (τ(r1+g) )=h_r(x). 2. For fixed r, hr(x)h_r(x) is strictly increasing in x. For x∈(−1,1)x∈(-1,1), it is continuous and strictly increasing in r. 3. For x∈[0,1]x∈[0,1], h1/4(x)≥n17.h_1/4(x)≥ n 17. 4. Let Λn=−1,−1+2/n,…,1. _n=\-1,-1+2/n,…,1\. For u∈Λn∩(0,1)u∈ _n∩(0,1) and u−=u−2/nu^-=u-2/n, every threshold h0(u)≤θ<h1/4(u)h_0(u)≤θ<h_1/4(u) admits an r∈(0,1/4]r∈(0,1/4] such that hr(x)>θ⟺x≥uh_r(x)>θ x≥ u for every x∈Λnx∈ _n. Proof. For z=τ⁡(r+g)z=τ(r1+g), z¯=τ⁡(r+x),z2¯=τ2(1+r2+2rx), z=τ(r+x), z^2=τ^2(1+r^2+2rx), which proves the first claim. Direct differentiation gives ∂xhr(x)=n(1+rx)Dr(x)−3/2>0 _xh_r(x)= n(1+rx)D_r(x)^-3/2>0 and ∂rhr(x)=n(1−x2)Dr(x)−3/2>0 _rh_r(x)= n(1-x^2)D_r(x)^-3/2>0 for |x|<1|x|<1. This proves the monotonicity statements. The third claim follows from h1/4(x)≥h1/4(0)=n41+(1−b)/16≥n17.h_1/4(x)≥ h_1/4(0)= n4 1+(1-b)/16≥ n 17. For the final claim, let f⁡(r)=hr(u),φ⁡(r)=hr(u−).f(r)=h_r(u), (r)=h_r(u^-). Both functions are continuous and strictly increasing and satisfy φ⁡(r)<f⁡(r). (r)<f(r). The intermediate value argument therefore produces an r for which φ⁡(r)<θ<f⁡(r). (r)<θ<f(r). Monotonicity in x gives the desired cutoff. ∎ A.7.3 The cost of repeated candidate testing Theorem A2 (Neutral candidates defeat thresholds below ln⁡(tK) (tK)). In model M, let (b,λ)(b,λ) be a threshold gate. Let n≥64n≥ 64, K,t≥1K,t≥ 1, and define N=tK,Λt=maxs≤t⁡λs,0,x=max⁡1,2Λt.N=tK, _t= _s≤ t _s,0, x= \1, 2 _t\. Assume x≤n/8x≤ n/8. Consider the non-adaptive proposer that submits Bs,k=(0,14e(s−1)K+k).B_s,k= (0, 14e_(s-1)K+k ). Every candidate has zero population gain. If q=ℙ⁡(Sn>xn),q=P(S_n>x n), then ℙ(tc)≤(1−q)N≤exp−cRNxe−x2/2−(x2+5)2/(9n).P( F_t^c)≤(1-q)^N≤ \- c_RNxe^-x^2/2-(x^2+5)^2/(9n) \. Proof. Until a promotion occurs, the incumbent remains A0A_0. Candidate (s,k)(s,k) depends on a fresh probe coordinate j=(s−1)K+kj=(s-1)K+k. By Lemma A6, Tk≥XjT_k≥ X_j whenever Xj≥0X_j≥ 0. Since 2λs,0≤2Λt≤x, 2 _s,0≤ 2 _t≤ x, any probe with Xj>xX_j>x forces a promotion. All such promotions are false because every candidate is population neutral. The N=tKN=tK probe coordinates are independent. Hence ℙ⁡(tc)≤(1−q)N≤e−Nq.P( F_t^c)≤(1-q)^N≤ e^-Nq. Apply Lemma A4. ∎ Corollary A2. In the setting of Theorem A2, suppose Λt≤(1−η)ln⁡N _t≤(1-η) N for a fixed η∈(0,1]η∈(0,1], with N≥2N≥ 2 and ln⁡N≤n/128 N≤ n/128. Then ℙ(t)≥1−exp−cRe−1/2Nη1+2ln⁡Ne−(2lnN+6)2/(9n).P( F_t)≥ 1- \-c_Re^-1/2 N^η 1+2 Ne^-(2 N+6)^2/(9n) \. In particular, ℙ⁡(t)→1P( F_t)→ 1 whenever tK→∞,ln⁡(tK)n→0.tK→∞, (tK)n→ 0. Proof. Apply Theorem A2 with x≤max⁡1,2ln⁡N.x≤ \1, 2 N\. The stated bound follows by substituting the tail estimate from Lemma A4. Under the asymptotic conditions, the exponent diverges. ∎ Remark A2. The result depends on the thresholds used throughout the tested rounds. More generally, if a set of rounds ℛ⊆[t]R [t] satisfies λs,0≤(1−η)ln⁡(|ℛ|K)for s∈ℛ, _s,0≤(1-η) (|R|K) s , the proposer can submit neutral probes only in those rounds. The same argument then applies with N=|ℛ|K.N=|R|K. A.7.4 The cost of promotion history Fix a∈(0,n/8].a∈(0, n/8]. Let ℓ=min⁡v∈nΛn:v≥a,u=ℓ/n, = \v∈ n\, _n:v≥ a\, u= / n, and define q=ℙ⁡(Sn≥an),π=1−(1−q)K.q=P(S_n≥ a n), π=1-(1-q)^K. For a target number P of promotions and η′>0η >0, set t0=⌈(1+η′)Pπ⌉,M=Kt0.t_0= (1+η )Pπ , M=Kt_0. We construct a proposer that uses previous promotion decisions to identify probe directions favored by the evaluation set. In a shifted-probe round, a successful probe is attached to a genuine positive shift. A neutral-probe promotion is already false. If no false promotion has occurred, after P genuine promotions the proposer combines the selected neutral probes into one final candidate whose population gain is zero. Let τ=18P.τ= 18P. The proposer keeps the selected probe indices in a set J, initially empty, and uses fresh indices js,k=(s−1)K+kj_s,k=(s-1)K+k. At round s, let p=|J|p=|J| and θs,p=2λs,p. _s,p= 2 _s,p. Adaptive proposer BP_B. The proposer acts as follows. 1. If a false promotion has already occurred or the final candidate has already been submitted, submit copies of the incumbent. 2. If p=Pp=P, submit K copies of Bfin=As−1+(0,τ∑j∈Jej).B^fin=A_s-1+ (0,τ _j∈ Je_j ). 3. If θs,p<h0(u), _s,p<h_0(u), submit neutral probes Bs,k=As−1+(0,τejs,k).B_s,k=A_s-1+(0,τ e_j_s,k). 4. If h0(u)≤θs,p<h1/4(u),h_0(u)≤ _s,p<h_1/4(u), choose rsr_s using Lemma A6 and submit Bs,k=As−1+(rsτ,τejs,k).B_s,k=A_s-1+(r_sτ,τ e_j_s,k). 5. Otherwise submit copies of the incumbent. If a candidate is promoted in a probe round, its probe index is added to J. The proposer can identify a false promotion from its own construction: neutral probes and the final candidate have zero population gain. Thus the construction depends only on previous promotion decisions and satisfies Assumption 2. Every submitted system remains in M: before the final round, ‖β‖1≤Pτ=1/8\|β\|_1≤ Pτ=1/8 and 0≤ϑ≤Pτ/4=1/320≤ ≤ Pτ/4=1/32, while the final candidate has ‖β‖1≤2Pτ=1/4\|β\|_1≤ 2Pτ=1/4. Theorem A3 (Adaptive proposer defeats slowly growing thresholds). In model M, let (b,λ)(b,λ) be a threshold gate. With the parameters defined above, fix ε>0 >0 and assume (B1) λs,p<n34 _s,p< n34 for all s≤t0s≤ t_0 and p≤min⁡P−1,s−1p≤ \P-1,s-1\; (B2) λs,P≤a2P2(1+ε) _s,P≤ a^2P2(1+ ) for all P+1≤s≤t0+1P+1≤ s≤ t_0+1. Then the proposer BP_B satisfies ℙ⁡(t0+1c)≤exp⁡−η′2P2(1+η′)+(MP)exp−n2(ε−ln⁡(1+ε)).P( F_t_0+1^c)≤ \- η 2P2(1+η ) \+ MP \- n2 ( - (1+ ) ) \. Proof. First suppose n∈1,2n∈\1,2\. Since 0<a≤n/80<a≤ n/8, the smallest positive value of a standardized Rademacher sum is n n, so ℓ=n = n and u=1u=1. Moreover, h0(1)=h1/4(1)=n1−b,h_0(1)=h_1/4(1)= n 1-b, where the value is interpreted as +∞+∞ when b=1b=1, consistently with the convention for TbT_b. For every s≤t0s≤ t_0, condition (B1) gives θs,0=2λs,0<n/17<h0(1). _s,0= 2 _s,0< n/17<h_0(1). Thus, until the first false promotion, the proposer submits only neutral probes and the promotion count remains zero. A fresh probe satisfies Xj≥aX_j≥ a if and only if all its n Rademacher coordinates equal +1+1. On this event its statistic is n/1−b n/ 1-b (or +∞+∞ when b=1b=1), which exceeds the threshold. Hence, if at least one of the K probes in a round has this property, a false promotion occurs. Here q=2−nq=2^-n and π=1−(1−q)Kπ=1-(1-q)^K. Independence of the fresh probe blocks and the definition of t0t_0 therefore yield ℙ⁡(t0+1c)≤(1−π)t0≤exp⁡(−πt0)≤exp⁡(−(1+η′)P)≤exp⁡−η′2P2(1+η′).P( F_t_0+1^c)≤(1-π)^t_0≤ (-π t_0)≤ (-(1+η )P )≤ \- η 2P2(1+η ) \. The last inequality follows from η′2≤2(1+η′)2η 2≤ 2(1+η )^2. Since the second term in the stated bound is nonnegative, this proves the theorem for n∈1,2n∈\1,2\. Henceforth assume n≥3n≥ 3. Let sG_s contain all probe coordinates introduced through round s and all gate randomness up to that round. Fresh probe coordinates in round s+1s+1 are independent of sG_s. For a probe or neutral round, let X(s)=maxk⁡Xjs,k.X^(s)= _kX_j_s,k. Then ℙ⁡(X(s)≥a)=π.P(X^(s)≥ a)=π. If θs,p<h0(u) _s,p<h_0(u), a probe with X(s)≥aX^(s)≥ a crosses the threshold even though its population gain is zero. Hence the round produces a false promotion with conditional probability at least π. If h0(u)≤θs,p<h1/4(u),h_0(u)≤ _s,p<h_1/4(u), Lemma A6 chooses rsr_s so that promotion occurs exactly when X(s)≥a.X^(s)≥ a. The promoted candidate then has population gain rsτ>0,r_sτ>0, so this promotion is genuine. Condition (B1) guarantees that, until a false promotion or the P-th selected probe, every round is one of these two types. Define Is=X(s)≥aI_s=1\X^(s)≥ a\ using the fresh coordinates for all s≤t0s≤ t_0; these indicators are independent Bernoulli variables with success probability π. On the event that no false promotion occurs and fewer than P probes are selected by t0t_0, each success Is=1I_s=1 must have produced a genuine selected probe. Consequently, Chernoff’s inequality gives ℙ⁡(t0c∩fewer than P selected probes by t0)≤ℙ⁡(∑s=1t0Is<P)≤exp⁡−η′2P2(1+η′).P\! ( F_t_0^c∩\fewer than P selected probes by t_0\ ) \! ( _s=1^t_0I_s<P )≤ \- η 2P2(1+η ) \. Suppose instead that P genuine probe promotions have occurred. The final candidate has paired differences z=τ∑j∈Jg⋅jz=τ _j∈ Jg_· j and population gain zero. On the event max|J|=P⁡QJ<1+ε, _|J|=PQ_J<1+ , we have z¯≥τn−1/2Pa z≥τ n^-1/2Pa and z2¯=τ2PQJ. z^2=τ^2PQ_J. Therefore Tb(z)>PaP⁡(1+ε)=aP1+ε.T_b(z)> Pa P(1+ )=a P1+ . Condition (B2) makes this larger than the promotion threshold, so the final neutral candidate is promoted. The only two ways to avoid a false promotion are therefore failure to collect P probes by t0t_0 or failure of the uniform second-moment event. Apply Lemma A5. ∎ Corollary A3 (First-order promotion-history rate). Let η∈(0,1]η∈(0,1], K,P≥1K,P≥ 1, and ς≥5 ≥ 5 with Kς≥e8K ≥ e^8. Define t=⌊ςP⌋+1t= P +1 and ΛK(ς)=ln⁡(Kς)−12ln⁡(2ln⁡(Kς))−6. _K( )= (K )- 12 (2 (K ) )-6. Assume the sample size satisfies 2ΛK(ς)≤n8,(2ΛK(ς)+5)29n≤12, 2 _K( )≤ n8, (2 _K( )+5)^29n≤ 12, and that λs,p<n/34 _s,p<n/34 for all s≤t−1s≤ t-1 and p≤min⁡P−1,s−1p≤ \P-1,s-1\. If λs,P≤(1−η)ΛK(ς)P _s,P≤(1-η) _K( )P for all P+1≤s≤tP+1≤ s≤ t, then a decision-only proposer satisfies ℙ(t)≥1−e−P/4−expPln(eKς)−nη28.P( F_t)≥ 1-e^-P/4- \P (eK )- nη^28 \. Proof. Apply Theorem A3 with a=2ΛK(ς),η′=1,ε=η.a= 2 _K( ), η =1, =η. The two sample-size conditions allow us to apply Lemma A4 and bound its correction term by 1/21/2. Since ΛK(ς)≤ln⁡(Kς) _K( )≤ (K ), this gives q≥cRaexp⁡−ΛK(ς)−1/2≥e322Kς≥6Kς.q≥ c_Ra \- _K( )-1/2\≥ e^32 2\,K ≥ 6K . Hence π=1−(1−q)K≥1−e−6/ς≥3.49ς,π=1-(1-q)^K≥ 1-e^-6/ ≥ 3.49 , which implies t0=⌈2Pπ⌉≤2ςP3.49+1≤ςP.t_0= 2Pπ ≤ 2 P3.49+1≤ P. The conditions of Theorem A3 follow. Finally use (MP)≤(eKς)P MP≤(eK )^P and nη24(1+η)≥nη28. nη^24(1+η)≥ nη^28. ∎ Corollary A4 (Linear growth in the promotion count is insufficient). Fix c>0c>0 and an integer p0≥0p_0≥ 0. Suppose λt,p≤cp _t,p≤ cp for all p≥p0p≥ p_0, and assume supt,p<p0λt,p=o⁡(n). _t,p<p_0 _t,p=o(n). The latter condition is omitted when p0=0p_0=0. Along any sequence satisfying n→∞,P→∞,Pln⁡(eK)=o⁡(n),ln⁡K=o⁡(n),n→∞, P→∞, P (eK)=o(n), K=o( n), there exists a decision-only proposer that causes a false promotion within O⁡(P)O(P) rounds with probability tending to one. Proof. Choose ς large enough that ς≥e8,Λ1(ς)≥2c ≥ e^8, _1( )≥ 2c and apply Corollary A3 with η=1/2η=1/2. For sufficiently large P, cP≤12ΛK(ς)P.cP≤ 12 _K( )P. The pre-promotion thresholds are o⁡(n)o(n) because P=o⁡(n)P=o(n), and the two sample-size conditions in Corollary A3 hold because ln⁡K=o⁡(n) K=o( n). Also Pln⁡(eKς)=o⁡(n)P (eK )=o(n), so both error terms in that corollary converge to zero. ∎ Remark A3 (Comparison with Reuse). For P+1≤t≤ςP+1,P+1≤ t≤ P+1, the allocation used by Reuse satisfies ℒt,P≤Pln⁡(eKς)+O⁡(ln⁡(KςP)+ln⁡1α).L_t,P≤ P (eK )+O ( (K P)+ 1α ). Thus the history-dependent contribution per promotion is at most ln⁡(eKς) (eK ). The lower bound in Corollary A3 has scale ΛK(ς)=ln⁡(Kς)−O⁡(ln⁡ln⁡(Kς)+1) _K( )= (K )-O\! ( (K )+1 ) per promotion. These history-dependent rates agree to first order as Kς→∞K →∞. This comparison concerns the history term, not the additional time- and error-level terms in ℒt,PL_t,P. For example, along sequences with P→∞P→∞, Kς→∞K →∞, ln⁡(Kς)=o⁡(n) (K )=o( n), and Pln⁡(eKς)=o⁡(n)P (eK )=o(n), the two remainder terms in Corollary A3 tend to zero for every fixed η∈(0,1]η∈(0,1]. Under its threshold conditions, the false-promotion probability therefore tends to one. Together with Corollary A2, this gives the two regimes summarized in Theorem A1. The thresholds in these lower bounds are controlled over the stated ranges of rounds; the results do not assert that every individual threshold must exceed the stated rate. The lower bound applies to the threshold-gate class in Definition A1. Reuse’s exact test is not literally a member of this class, but its standardized critical value has the same first-order scale in the regime of Proposition 1. The attack uses non-binary bounded scores; the comparison does not by itself establish a lower bound for every pass/fail promotion rule. It identifies the first-order history-dependent requirement within the stated threshold-gate class. Appendix B Experimental Details This appendix describes the protocol of the live experiments, the proposer and its prompts, the compared methods, and additional results. B.1 Protocol Covertype contains 581,012 examples with 54 features, and we label cover type 2 as positive. A single random permutation partitions the data into the disjoint blocks DtrD_tr, DdevD_dev, ℰE, and H of Section 3.1, and the remaining examples are unused. For each seed, S is a random sample of n examples from ℰE, and the 2,0002,000-example set is contained in the 10,00010,000-example set of the same seed. All methods use the same evaluation set within a seed. Table 2 summarizes the protocol. Every configuration is fitted once on DtrD_tr with fitting seed 0, and its predictions are cached so that a repeated configuration reuses the same fitted model. The experiments use NVIDIA A100 GPUs with 40 GB of memory, Python 3.11.16, scikit-learn 1.9.1, and vLLM 0.29.0. Table 2: Protocol shared by all methods in the live experiments. Quantity Setting Data Training set DtrD_tr 50,000 examples Development set DdevD_dev 20,000 examples Evaluation pool ℰE 60,000 examples Held-out set H 50,000 examples Evaluation-set size n 2,0002,000 or 10,00010,000 Seeds 30 at each evaluation-set size, seeds 3 to 32 Search Rounds T 200 Candidates per round K 8 Changed fields per candidate at most 2 Model families histogram gradient boosting, logistic regression Preprocessing no, standard, or robust scaling, optional selection of 10, 20, or 30 features Feature subsets all, topographic, hillshade, soil, topographic and soil Starting system A0A_0 gradient boosting, all features, depth 3, 100 iterations, learning rate 0.1 Promotion target classification accuracy Proposer Model Qwen2.5-7B-Instruct served by vLLM Sampling temperature 0.8, top-p 0.95, top-k 20, repetition penalty 1.05 Requests per round at most 3, each asking for 8 configurations Reuse Error levels α=0.05α=0.05, αc=0.05 _c=0.05, γ=0γ=0, ρ=1/2ρ=1/2 Allocation weights wt=1/[t⁡(t+1)]w_t=1/[t(t+1)] and vp=1/[(p+1)(p+2)]v_p=1/[(p+1)(p+2)] Draft threshold zdev≥1.645z_dev≥ 1.645 B.2 Proposer and prompt templates At every round, Qwen2.5-7B-Instruct (Yang et al., 2024), served through vLLM (Kwon et al., 2023), receives one system message and one user message. The system message describes the task, the configuration schema, and the allowed values, and it ends with a feedback paragraph that differs between Reuse and the compared methods. The user message contains the parent configuration, its accuracy on DdevD_dev, its error rates on 14 slices of DdevD_dev, and the previous ten rounds of search history. Each request asks for eight complete JSON configurations. Invalid proposals, proposals equal to the parent, and proposals that change more than two fields read by the parent’s or the proposal’s model family are discarded, and up to three requests are made per round. Reuse also discards configurations already evaluated in the run. Unfilled slots are replaced by copies of the parent, which cannot be promoted. Table 3 lists the information available to the proposer, and the templates follow. Table 3: Information in the prompt of the proposer. Only Reuse withholds evaluation accuracies on S, so its proposer learns about S solely through promotion decisions. SICA-style additionally sees up to ten archive members with the highest evaluation accuracy. Information in the prompt Compared methods Reuse Parent configuration ✓ ✓ Accuracy and slice error rates on DdevD_dev ✓ ✓ Accuracies of past proposals on DdevD_dev ✓ ✓ Evaluation accuracies on S ✓ ✗ Promotion decisions ✓ ✓ Development-draft updates and submissions ✗ ✓ Accuracies on H ✗ ✗ System message. The following part is shared by all methods. You are an expert machine-learning engineer improving a scikit-learn pipeline. The task is binary classification on forest cover-type data: 54 columns (10 topographic and hillshade measurements, 4 wilderness-area indicators, 40 soil-type indicators) and 50,000 training rows. Every configuration you propose is fitted from scratch on those same rows and judged by its accuracy. A configuration is a JSON object with exactly these eleven keys: - "model_family": "hist_gbm" (histogram gradient boosting) or "logreg" (logistic regression) - "learning_rate": number in [0.02, 0.3], hist_gbm only - "max_depth": integer in [2, 6], hist_gbm only - "max_iter": integer in [50, 300], boosting iterations, hist_gbm only - "min_samples_leaf": integer in [5, 100], hist_gbm only - "l2_regularization": number in [0, 1], hist_gbm only - "C": number in [0.001, 100], inverse regularization strength, logreg only - "scaling": "none", "standard" or "robust" - "feature_selection": "none", "kbest_10", "kbest_20" or "kbest_30" (ANOVA F-test over the columns kept) - "feature_subset": "all", "topo", "soil", "hillshade" or "topo_soil" -- fixed column presets: topo is elevation, aspect, slope and the three distance columns; hillshade is the three hillshade columns; soil is the 40 soil-type indicators; topo_soil is both; all is every column, including the four wilderness-area indicators - "seed": 0 Rules: - Every object must carry all eleven keys. A key you leave out is not "unchanged": it falls back to the default and silently undoes earlier work. Copy the current configuration and edit only the fields you mean to change. - A value outside its range, an unknown key or malformed JSON discards that candidate. - Keys that do not apply to the model family you chose are kept and ignored by the fit. - A proposal that changes more than two fields is discarded unseen, so keep every candidate within two changes of the current configuration. - Each proposal's accuracy on the development set is reported back to you in the next round, with its difference from the current configuration's. Build on the changes that raised it and abandon the ones that lowered it. Answer with one short line of reasoning and then a JSON array of configurations in a ```json code block. If the current configuration were the starting one, a reply proposing a slower learning rate and a scaled, screened variant would look like this: ```json [ "model_family": "hist_gbm", "learning_rate": 0.05, "max_depth": 3, "max_iter": 100, "min_samples_leaf": 20, "l2_regularization": 0.0, "C": 1.0, "scaling": "none", "feature_selection": "none", "feature_subset": "all", "seed": 0, "model_family": "hist_gbm", "learning_rate": 0.1, "max_depth": 3, "max_iter": 100, "min_samples_leaf": 20, "l2_regularization": 0.0, "C": 1.0, "scaling": "standard", "feature_selection": "kbest_20", "feature_subset": "all", "seed": 0 ] ``` B.3 Compared methods All compared methods share the proposer, the candidate space, and DtrD_tr with Reuse, and they differ in parent selection and promotion rule. Every run keeps an archive of distinct fitted configurations. The incumbent is the deployed configuration, and the parent is the configuration the proposer edits in the next round. Table 4 summarizes the methods, and the reported system of every method is the incumbent after round T. Table 4: Compared methods in the live experiments. Select., Repeat., and Adapt. indicate whether a rule controls errors from within-round selection, repeated testing, and adaptive dependence, as in Table 1. Method Feedback from S Promotion rule Select. Repeat. Adapt. Empirical best-of-K scores largest positive gain on S ✗ ✗ ✗ SICA-style scores largest positive gain on S ✗ ✗ ✗ DGM-style scores largest positive gain on S ✗ ✗ ✗ Elite scores largest positive gain on S ✗ ✗ ✗ Niche-elite scores largest positive gain on S ✗ ✗ ✗ PACE-style scores McNemar test at level 0.050.05 ✗ ✗ ✗ Bonferroni-style scores McNemar test at level 0.05/(TK)0.05/(TK) ✓ ✓ ✗ Reuse (ours) decisions only exact paired test with (4) ✓ ✓ ✓ Empirical best-of-K edits the incumbent and promotes the candidate with the largest strictly positive gain on S. SICA-style follows the archive-based search of SICA (Robeyns et al., 2025). It also edits the incumbent, and its prompt additionally lists up to ten archive members with the highest evaluation accuracy. DGM-style follows the parent selection of DGM (Zhang et al., 2026). Archive member i is chosen as parent with probability proportional to σ⁡(40(ai−a0−0.08))1+ei, σ\! (40(a_i-a_0-0.08) )1+e_i, where aia_i is its evaluation accuracy, a0a_0 is that of A0A_0, eie_i is the number of rounds in which it has been parent, and σ is the logistic function. Elite draws its parent uniformly from the four archive members with the highest evaluation accuracy, and Niche-elite groups configurations by model family and feature subset, draws one group uniformly, and uses its best member. These two methods follow the population-based search of AlphaEvolve (Novikov et al., 2025). The five methods above share the promotion rule of Empirical best-of-K. PACE-style and Bonferroni-style edit the incumbent and test all K candidates against it with the one-sided McNemar test (Dietterich, 1998), zMC=n+−n−n++n−,pMC=1−Φ⁡(zMC),z_MC= n_+-n_- n_++n_-, p_MC=1- (z_MC), with n+n_+ and n−n_- as in Section 2.2, Φ the standard normal distribution function, and pMC=1p_MC=1 when n++n−=0n_++n_-=0. PACE-style tests every candidate at level 0.050.05, and Bonferroni-style at level 0.05/(TK)=0.05/16000.05/(TK)=0.05/1600. If several candidates pass, the one with the largest gain on S is promoted. B.4 Additional results Table 5 complements Table 1 with seed-matched differences in final population improvement and the smallest population improvement among the promotions of each method. Table 5: Additional summaries of the live experiments over 30 seeds at each evaluation-set size, in percentage points. Diff. is the seed-matched difference in final population improvement between a method and Reuse, reported as mean ± standard error, so a positive value means the method ends higher. Worst is the smallest population improvement among all promotions of a method, pooled over runs. Diff. vs Reuse Worst ↑ Method n=2,000n=2,000 n=10,000n=10,000 n=2,000n=2,000 n=10,000n=10,000 Empirical best-of-K +0.02+0.02±\,±\,0.25 +0.00+0.00±\,±\,0.15 −0.89-0.89 −0.61-0.61 SICA-style −0.66-0.66±\,±\,0.29 −0.63-0.63±\,±\,0.19 −0.63-0.63 −0.42-0.42 DGM-style −3.13-3.13±\,±\,0.31 −3.16-3.16±\,±\,0.23 −1.44-1.44 −0.21-0.21 Elite −0.30-0.30±\,±\,0.28 −0.34-0.34±\,±\,0.18 −1.12-1.12 −0.44-0.44 Niche-elite −0.56-0.56±\,±\,0.34 −0.82-0.82±\,±\,0.19 −1.13-1.13 −0.41-0.41 PACE-style −0.57-0.57±\,±\,0.34 +0.04+0.04±\,±\,0.14 −0.34-0.34 −0.18-0.18 Bonferroni-style −4.67-4.67±\,±\,0.50 −0.29-0.29±\,±\,0.17 0.860.86 0.410.41 Reuse (ours) – – 1.201.20 0.340.34 B.4.1 Robustness and Ablations The theoretical guarantee of Theorem 1 holds for any allocation weights wtw_t and vpv_p and split ρ fixed before querying S. We tested the sensitivity of Reuse to these choices by running 11 different allocations on 10 fresh seeds at n=2,000n=2,000 (Table 6). Reuse successfully controlled the error across all configurations and made exactly zero false promotions out of 317 total promotions. The final population improvement remained stable and within the natural variation of the proposer. The running certificate CTC_T also responded naturally to the split ρ. The core guarantee of Reuse is highly robust to changes in the search heuristics. To demonstrate this reliability we evaluated an alternative variant that queries S at every step. In this setup the proposer edits the incumbent directly and the candidate with the highest development accuracy is tested on S at level ρδt,pρ _t,p with K=1K=1. The proposer receives only the promotion decision. Even with this more conservative search structure the variant completely avoided false promotions across 30 seeds at both evaluation set sizes (Table 7). It made 30 strictly positive promotions at n=2,000n=2,000 and 100 at n=10,000n=10,000. These results confirm that the error control mechanism fundamentally prevents false promotions and maintains rigorous validity regardless of the specific search mechanics or allocation parameters used. We further isolated the role of the exact test on S by ablating it. We ran Reuse at n=10,000n=10,000 on 10 new seeds using a smaller development set of 500 examples and a lowered pre-screening threshold of zdev>0z_dev>0 to deliberately allow poor candidates to reach the evaluation set. We compared this setup with a baseline that promotes every submitted candidate without testing it on S. The proposer of the untested version is told that each submitted candidate was tested and accepted so the two versions differ only in the application of the test. Figure 4 illustrates every evaluated candidate under these conditions. Reuse rejected all 9 candidates with population improvement at most zero and made no false promotion among its 47 accepted updates. Without the test the process committed 6 false promotions across 5 of the 10 runs with population improvements dropping down to −0.56-0.56 p. The two tested variants achieved very similar final population improvements, with no statistically significant difference between them. This confirms the test on S is strictly necessary and effective at filtering out the false improvements that pass the initial development screen. Table 6: Sensitivity of Reuse to its allocation (4) at n=2,000n=2,000 over 10 new seeds. We change one of ρ or wtw_t or vpv_p at a time from the default. The variable t indexes the rounds where S is queried and the harmonic weight uses c≈0.590747c≈ 0.590747. The columns for S tests, Prom., Pop. Impr. and CTC_T are means ± standard error over seeds. The False / all column sums false and all promotions over the 10 runs. Diff. is the seed-matched difference from the default run. Changed counts the runs in which the default allocation would have made at least one querying or promotion decision differently. CTC_T re-prices the promotions of the same-seed default run at the certificate level (1−ρ)δt,p(1-ρ) _t,p. All improvements are in percentage points. S tests Prom. False / Pop. Impr. Diff. Changed CTC_T at default’s Setting per run per run all (p) (p) runs promotions (p) Default 4.30±\,±\,0.37 2.90±\,±\,0.28 0/29 6.38±\,±\,0.23 N/A N/A 0.74±\,±\,0.11 Split ρ ρ=0.1ρ=0.1 4.00±\,±\,0.30 3.00±\,±\,0.15 0/30 7.23±\,±\,0.36 +0.85+0.85±\,±\,0.40 9/10 0.89±\,±\,0.11 ρ=0.25ρ=0.25 3.90±\,±\,0.18 2.60±\,±\,0.16 0/26 6.52±\,±\,0.27 +0.14+0.14±\,±\,0.37 4/10 0.84±\,±\,0.11 ρ=0.75ρ=0.75 4.80±\,±\,0.33 3.00±\,±\,0.26 0/30 6.52±\,±\,0.35 +0.14+0.14±\,±\,0.29 1/10 0.59±\,±\,0.10 ρ=0.9ρ=0.9 4.70±\,±\,0.33 3.00±\,±\,0.21 0/30 6.52±\,±\,0.26 +0.14+0.14±\,±\,0.32 5/10 0.44±\,±\,0.09 Submission weight wtw_t harmonic 4.60±\,±\,0.34 3.10±\,±\,0.23 0/31 6.94±\,±\,0.21 +0.56+0.56±\,±\,0.21 2/10 0.63±\,±\,0.10 flat 3.00±\,±\,0.26 2.30±\,±\,0.15 0/23 6.51±\,±\,0.33 +0.12+0.12±\,±\,0.43 10/10 0.31±\,±\,0.06 geometric 4.30±\,±\,0.21 3.10±\,±\,0.23 0/31 6.64±\,±\,0.21 +0.26+0.26±\,±\,0.35 1/10 0.80±\,±\,0.12 Promotion weight vpv_p front-loaded 4.90±\,±\,0.50 2.90±\,±\,0.18 0/29 7.11±\,±\,0.37 +0.73+0.73±\,±\,0.47 8/10 0.65±\,±\,0.10 flat 4.00±\,±\,0.26 2.80±\,±\,0.20 0/28 6.85±\,±\,0.33 +0.47+0.47±\,±\,0.39 7/10 0.49±\,±\,0.09 geometric 4.00±\,±\,0.30 3.00±\,±\,0.26 0/30 6.83±\,±\,0.42 +0.45+0.45±\,±\,0.42 0/10 0.79±\,±\,0.11 Table 7: False promotions of the alternative Reuse variant and of the seven compared methods over the 30 seeds at each evaluation set size. Prom. and False are identical to the metrics in Table 1. Runs is the number of runs out of 30 with at least one false promotion. n=2,000n=2,000 n=10,000n=10,000 Method Prom. False ↓ Runs ↓ Prom. False ↓ Runs ↓ Empirical best-of-K 13.0 75 30/30 14.2 71 28/30 SICA-style 12.3 72 30/30 12.5 62 26/30 DGM-style 6.4 34 22/30 7.2 18 15/30 Elite 14.3 89 27/30 13.7 59 25/30 Niche-elite 12.3 71 28/30 12.4 44 24/30 PACE-style 6.4 4 4/30 8.1 3 3/30 Bonferroni-style 1.3 0 0/30 6.5 0 0/30 Alternative variant 1.0 0 0/30 3.3 0 0/30 Figure 4: Performance of Reuse with and without its test on S at n=10,000n=10,000 over 10 seeds using a 500 example development set and pre-screening threshold zdev>0z_dev>0. Each point is a submitted candidate placed at its gain on S and its population improvement over the incumbent estimated on H. The shaded band marks population improvement at most zero and the dashed line is equality. The left panel shows Reuse whose test on S promotes the filled points and rejects the open circles. The right panel shows the same rule without the test which promotes every submitted candidate. Red triangles are false promotions. B.4.2 Per-seed results Tables 8 and 9 list every run: for each method and seed, the final population improvement and the numbers of false and of all promotions. Table 8: Per-seed results at n=2,000n=2,000 for the 30 seeds of Table 1. For each of the eight methods, a cell gives the final population improvement of the deployed system over A0A_0 in percentage points, estimated on the held-out set H, followed in parentheses by the run’s false promotions and all promotions; nonzero false counts are in red. Mean averages the final population improvement over the 30 seeds and Total sums the promotion counts. Mean and the false counts in Total equal the corresponding columns of Table 1, and the total promotions divided by 30 give its Prom. column. Empirical SICA- DGM- Niche- PACE- Bonferroni- Reuse Seed best-of-K style style Elite elite style style (ours) 3 7.14 (1/9) 5.76 (3/11) 4.65 (1/8) 7.14 (3/13) 7.17 (3/20) 7.22 (0/9) 0.00 (0/0) 7.24 (0/3) 4 7.25 (2/12) 7.24 (3/14) 5.26 (0/5) 7.25 (0/9) 7.24 (2/9) 5.75 (0/5) 3.21 (0/2) 5.73 (0/3) 5 7.06 (3/14) 7.41 (3/16) 2.77 (2/7) 4.65 (4/15) 6.81 (1/14) 3.79 (0/5) 0.00 (0/0) 7.26 (0/4) 6 6.70 (3/16) 5.55 (2/11) 2.33 (2/4) 6.70 (5/19) 6.70 (6/19) 6.72 (1/8) 4.11 (0/2) 6.70 (0/4) 7 7.14 (3/15) 5.92 (2/14) 3.21 (1/9) 5.92 (5/18) 6.50 (3/13) 4.65 (0/4) 0.86 (0/1) 10.00 (0/5) 8 7.24 (4/14) 7.24 (3/13) 2.82 (1/5) 7.24 (8/20) 7.24 (2/10) 7.24 (0/6) 3.93 (0/2) 7.24 (0/3) 9 7.02 (2/11) 7.24 (1/9) 4.03 (2/10) 7.02 (2/15) 4.65 (2/11) 7.24 (0/9) 0.00 (0/0) 7.24 (0/4) 10 7.10 (6/19) 5.40 (9/19) 4.43 (0/6) 5.75 (4/13) 7.27 (4/14) 7.17 (0/8) 5.76 (0/3) 5.06 (0/2) 11 5.45 (2/13) 5.75 (2/10) 1.86 (0/4) 7.37 (3/12) 7.34 (0/10) 6.52 (0/6) 1.51 (0/1) 5.76 (0/3) 12 7.37 (3/16) 6.64 (2/14) 4.30 (2/6) 7.37 (3/15) 5.24 (5/14) 7.37 (0/7) 0.00 (0/0) 10.80 (0/3) 13 7.37 (1/9) 5.32 (3/10) 4.65 (0/6) 6.84 (1/11) 6.15 (0/10) 7.24 (0/7) 4.65 (0/3) 5.92 (0/3) 14 7.34 (1/8) 7.34 (1/13) 4.92 (0/4) 6.64 (2/14) 5.77 (2/11) 7.34 (0/8) 4.11 (0/3) 7.41 (0/4) 15 7.22 (3/16) 6.18 (3/11) 3.89 (1/10) 6.70 (1/10) 5.67 (2/8) 6.55 (1/7) 4.65 (0/2) 4.80 (0/2) 16 7.34 (2/14) 7.34 (2/12) 2.73 (2/8) 7.02 (2/16) 7.34 (1/14) 7.14 (0/5) 2.73 (0/2) 6.40 (0/3) 17 6.80 (2/10) 7.37 (1/14) 2.84 (1/7) 7.37 (1/13) 7.37 (1/11) 7.37 (0/7) 0.00 (0/0) 6.31 (0/2) 18 7.14 (2/14) 4.65 (3/13) 4.11 (2/6) 5.52 (4/15) 5.71 (2/12) 7.24 (0/8) 1.20 (0/1) 6.84 (0/4) 19 6.77 (7/16) 6.84 (2/13) 4.06 (1/6) 5.29 (6/16) 7.24 (2/12) 5.14 (1/6) 0.00 (0/0) 5.72 (0/2) 20 5.87 (2/14) 6.84 (1/10) 4.23 (0/4) 5.29 (2/10) 7.25 (2/15) 7.14 (0/7) 2.19 (0/1) 6.45 (0/3) 21 7.37 (2/12) 5.75 (3/13) 5.23 (1/8) 7.27 (0/12) 5.80 (5/15) 7.14 (0/7) 4.11 (0/2) 5.80 (0/3) 22 7.24 (1/10) 7.27 (1/12) 2.77 (0/3) 6.18 (3/14) 5.26 (1/9) 6.49 (1/7) 4.11 (0/2) 5.76 (0/3) 23 7.37 (1/9) 7.37 (1/11) 4.56 (1/5) 7.37 (0/12) 5.68 (3/11) 5.72 (0/5) 4.65 (0/2) 9.67 (0/4) 24 7.24 (5/19) 5.82 (2/10) 4.43 (0/6) 7.10 (3/16) 5.76 (2/8) 4.65 (0/3) 5.65 (0/3) 7.10 (0/3) 25 7.34 (1/15) 5.65 (1/11) 3.35 (2/5) 7.27 (3/16) 7.34 (4/14) 6.64 (0/6) 2.73 (0/1) 6.84 (0/3) 26 6.80 (5/15) 5.52 (3/9) 4.65 (2/9) 7.12 (2/12) 7.05 (4/16) 6.08 (0/5) 3.21 (0/2) 6.45 (0/3) 27 6.70 (3/12) 7.14 (2/12) 4.30 (1/6) 6.70 (5/17) 7.14 (3/14) 7.24 (0/6) 2.95 (0/1) 7.02 (0/3) 28 6.95 (1/11) 3.49 (4/11) 3.51 (1/8) 7.14 (2/11) 6.95 (2/14) 7.12 (0/8) 0.00 (0/0) 7.18 (0/4) 29 7.14 (4/12) 6.70 (3/15) 2.92 (1/4) 6.81 (3/13) 6.45 (2/8) 7.24 (0/6) 4.07 (0/2) 10.00 (0/5) 30 7.34 (1/10) 7.05 (1/14) 4.65 (4/8) 7.06 (5/21) 5.00 (1/10) 6.50 (0/7) 0.00 (0/0) 7.34 (0/3) 31 7.24 (1/13) 7.05 (3/12) 4.11 (2/8) 7.24 (3/15) 7.05 (3/16) 5.68 (0/7) 0.00 (0/0) 7.10 (0/3) 32 7.25 (1/12) 5.94 (2/13) 5.14 (1/8) 7.14 (4/16) 5.71 (1/8) 4.11 (0/4) 0.00 (0/0) 7.41 (0/3) Mean 7.04 6.36 3.89 6.72 6.46 6.45 2.35 7.02 Total (75/390) (72/370) (34/193) (89/429) (71/370) (4/193) (0/38) (0/97) Table 9: Per-seed results at n=10,000n=10,000 for the 30 seeds of Table 1. For each of the eight methods, a cell gives the final population improvement of the deployed system over A0A_0 in percentage points, estimated on the held-out set H, followed in parentheses by the run’s false promotions and all promotions; nonzero false counts are in red. Mean averages the final population improvement over the 30 seeds and Total sums the promotion counts. Mean and the false counts in Total equal the corresponding columns of Table 1, and the total promotions divided by 30 give its Prom. column. Empirical SICA- DGM- Niche- PACE- Bonferroni- Reuse Seed best-of-K style style Elite elite style style (ours) 3 7.17 (1/17) 4.65 (0/5) 2.92 (1/7) 7.41 (4/20) 7.24 (2/10) 7.24 (0/9) 7.10 (0/7) 6.70 (0/5) 4 7.37 (1/13) 7.44 (2/14) 5.27 (1/8) 7.27 (3/16) 5.61 (0/7) 7.37 (0/7) 7.24 (0/7) 7.25 (0/8) 5 6.64 (2/14) 7.37 (2/13) 2.19 (0/5) 6.45 (2/8) 5.80 (0/9) 7.24 (0/9) 7.10 (0/7) 7.37 (0/6) 6 7.41 (2/15) 7.34 (2/13) 5.46 (0/7) 7.24 (1/9) 6.57 (2/20) 7.27 (0/10) 4.65 (0/4) 7.34 (0/7) 7 7.41 (3/17) 5.92 (1/13) 4.65 (1/8) 6.62 (4/21) 5.18 (0/13) 7.24 (0/9) 7.05 (0/7) 7.24 (0/6) 8 7.34 (3/13) 7.34 (2/13) 2.55 (0/4) 7.34 (1/15) 5.46 (1/12) 7.22 (0/8) 6.45 (0/6) 6.62 (0/6) 9 5.75 (2/11) 7.24 (5/15) 4.65 (1/8) 7.27 (1/13) 7.37 (2/15) 7.17 (0/9) 7.24 (0/7) 7.24 (0/6) 10 7.26 (0/10) 7.14 (3/15) 4.71 (0/11) 7.24 (2/21) 6.02 (0/12) 7.24 (0/8) 6.45 (0/7) 7.34 (0/6) 11 7.41 (2/16) 4.46 (3/9) 2.73 (1/9) 5.76 (0/9) 7.34 (3/18) 7.05 (1/9) 6.52 (0/6) 6.45 (0/6) 12 7.34 (3/14) 7.37 (1/17) 3.27 (0/5) 6.52 (2/12) 6.24 (2/11) 7.10 (0/8) 7.24 (0/7) 7.10 (0/5) 13 7.34 (2/13) 6.41 (1/10) 4.65 (0/6) 7.34 (2/15) 4.60 (1/8) 7.34 (0/8) 7.24 (0/7) 7.34 (0/6) 14 7.12 (2/12) 7.14 (4/15) 4.19 (2/9) 5.52 (3/11) 7.37 (4/14) 7.24 (1/8) 7.24 (0/7) 7.24 (0/5) 15 7.37 (1/13) 6.60 (3/15) 4.52 (1/9) 7.37 (1/14) 5.65 (2/11) 7.41 (0/11) 5.65 (0/6) 6.70 (0/5) 16 7.24 (1/8) 7.34 (1/16) 5.24 (0/7) 7.10 (3/16) 5.72 (0/7) 7.24 (0/6) 7.24 (0/5) 7.05 (0/6) 17 7.12 (2/11) 6.28 (0/10) 2.54 (1/6) 7.41 (1/17) 7.37 (1/12) 7.05 (0/7) 5.65 (0/5) 7.26 (0/7) 18 7.24 (1/10) 5.00 (3/11) 4.79 (0/6) 7.24 (0/14) 5.94 (1/9) 7.10 (0/7) 7.37 (0/7) 7.10 (0/6) 19 7.24 (4/18) 7.24 (4/18) 3.25 (1/8) 7.27 (0/9) 7.24 (2/16) 7.24 (0/10) 7.37 (0/7) 7.05 (0/6) 20 7.37 (4/18) 7.34 (2/16) 5.27 (1/10) 7.37 (2/16) 5.92 (2/13) 7.24 (0/7) 7.24 (0/7) 6.48 (0/6) 21 7.24 (3/16) 7.24 (2/15) 2.92 (0/5) 6.01 (3/13) 7.24 (1/15) 7.14 (0/8) 7.05 (0/7) 10.00 (0/6) 22 7.24 (3/13) 5.92 (2/12) 4.65 (0/7) 5.72 (1/12) 5.76 (1/10) 7.34 (0/8) 7.34 (0/7) 6.40 (0/6) 23 7.12 (6/19) 6.02 (0/6) 4.24 (3/10) 5.87 (2/13) 6.84 (3/18) 7.34 (0/8) 7.24 (0/6) 6.84 (0/6) 24 7.41 (5/18) 5.75 (3/13) 2.73 (0/5) 7.24 (3/14) 5.92 (1/14) 7.24 (0/7) 7.02 (0/7) 7.10 (0/6) 25 7.24 (1/17) 5.72 (1/10) 4.52 (0/10) 7.34 (0/8) 5.94 (1/13) 7.02 (0/8) 7.24 (0/7) 9.08 (0/6) 26 7.34 (3/16) 7.24 (4/16) 4.70 (1/8) 7.24 (3/17) 7.24 (3/13) 7.41 (1/9) 6.60 (0/6) 6.84 (0/4) 27 7.10 (2/10) 6.40 (1/7) 4.43 (0/7) 7.14 (3/12) 7.24 (2/10) 7.24 (0/6) 7.37 (0/6) 7.26 (0/6) 28 7.25 (2/12) 6.70 (2/12) 4.65 (1/9) 5.58 (2/11) 7.25 (0/10) 7.24 (0/7) 7.24 (0/7) 6.45 (0/6) 29 7.14 (6/21) 7.24 (2/9) 3.21 (0/3) 7.24 (2/11) 6.24 (2/14) 7.34 (0/8) 7.37 (0/6) 7.37 (0/6) 30 7.28 (3/15) 5.76 (3/11) 4.52 (0/5) 7.37 (0/13) 7.28 (1/12) 7.10 (0/8) 5.82 (0/5) 7.22 (0/5) 31 7.12 (1/15) 5.94 (0/11) 2.77 (1/5) 7.37 (5/19) 5.18 (3/13) 7.26 (0/8) 7.37 (0/7) 7.17 (0/7) 32 7.25 (0/11) 7.37 (3/16) 4.65 (1/10) 5.71 (3/11) 6.40 (1/14) 7.14 (0/8) 7.24 (0/7) 7.14 (0/5) Mean 7.19 6.56 4.03 6.85 6.37 7.23 6.90 7.19 Total (71/426) (62/376) (18/217) (59/410) (44/373) (3/243) (0/194) (0/177) B.4.3 Trajectories Figure 5 separates the trajectories of Figure 2 by method and adds standard errors across seeds. Figure 5: Mean population improvement of the deployed system over A0A_0 by round, estimated on H and averaged over 30 seeds, with one panel per method; dashed lines use n=2,000n=2,000 and solid lines use n=10,000n=10,000. Shaded bands show ±1± 1 standard error across the 30 seeds. B.4.4 Promotions and final performance Figure 6 plots the final population improvement of every run against its number of promotions. Reuse reaches a final population improvement comparable to that of Empirical best-of-K (Table 5) with far fewer promotions, a median of 3 against 13 per run at n=2,000n=2,000 and 6 against 14 at n=10,000n=10,000. No run of the seven compared methods improves on A0A_0 by more than 7.44 p, whereas four runs of Reuse at n=2,000n=2,000 and two at n=10,000n=10,000 improve on it by 9.08 to 10.80 p. Figure 6: Final population improvement over A0A_0 against the number of promotions in the run, estimated on H, one point per run with small horizontal jitter, for the 30 runs of each method at each evaluation-set size. Light gray points are the other benchmark-driven frameworks (SICA-style, DGM-style, Elite and Niche-elite), and outlined markers place Empirical best-of-K, PACE-style, Bonferroni-style and Reuse at their median number of promotions and median final population improvement. The arrow joins the medians of Empirical best-of-K and Reuse. B.4.5 Certificates Reuse records the running certificate CTC_T of Section 2.2 and the direct certificate DTD_T of Section A.5. Both are lower confidence bounds computed from the reused evaluation set alone, so they are reported separately from the population-gain estimates on H. Table 10 compares them with the realized population improvement, and none of the 274 per-promotion lower bounds ℓ that enter CTC_T exceeds the population improvement of its promotion. The direct certificate is larger than the running certificate in all 60 runs, because it pays one confidence margin for the whole trajectory rather than one per promotion. Table 10: Certificates of cumulative improvement for Reuse, over the 30 runs at each evaluation-set size. The final population improvement over A0A_0 is the mean over runs, estimated on H as in Table 1. CTC_T and DTD_T are reported as the mean over runs with the range across runs in brackets. Valid gives, for CTC_T and for DTD_T, the number of runs (of 30) in which the certificate is at most the realized final population improvement. The final population improvement, CTC_T and DTD_T are in percentage points. n Final population improvement Promotions per run Running certificate CTC_T Direct certificate DTD_T Valid CTC_T / DTD_T 2,0002,000 7.02 3.2 0.92 [0.13, 1.76] 3.10 [1.16, 5.49] 30 / 30 10,00010,000 7.19 5.9 2.67 [2.06, 3.88] 5.33 [4.34, 6.92] 30 / 30

Instant research discovery