Full text not available for this paper

Trustworthy Recursive Self-Improvement with Statistical Guarantees

Summary (Overview)

  • TRUST framework introduced: The paper proposes Trustworthy Recursive Updates with Statistical Testing (TRUST), a novel acceptance gate for recursive self-improvement (RSI) that controls the rate of accepting harmful updates while preserving beneficial improvements.

  • False Evolution Rate (FER) control: TRUST formulates sequential acceptance decisions as an online multiple hypothesis testing problem, defining FER as the expected proportion of accepted updates causing unacceptable performance loss, and proves it is bounded by a prespecified budget qq.

  • Statistical guarantees: Under interpretable assumptions, the authors prove FER control (Theorem 2), power consistency showing the true evolution rate (TER) converges to 1 (Theorem 3), and a lower bound on final performance gain (Theorem 4).

  • Empirical validation: Across HotpotQA, DROP, and APPS benchmarks with DeepSeek-V4-Flash and Qwen-3.8-Flash models, TRUST reduces the average ratio of accepted inferior updates from Greedy's 45.59% to 2.78%, while achieving the highest final gain of 24.84 pp.

  • Key innovation: TRUST combines four components—noninferiority testing, overlap correction, e-value testing, and error budget allocation with LLM guidance—to balance statistical reliability and performance gain in RSI.

Introduction and Theoretical Foundation

Background and Motivation

Recursive self-improvement (RSI) enables AI agents to enhance their capabilities without retraining underlying language models by modifying their own prompts, memory, tools, and workflows. A self-improvement loop consists of three components:

  • A solver that executes tasks
  • A proposer that generates candidate updates
  • A gate that decides whether to accept candidates

The critical challenge: a greedy gate that accepts updates based solely on higher validation scores can mistake observed gains for genuine progress, leading to performance degeneration. Conversely, overly conservative statistical gates may reject beneficial updates and hinder improvement.

Theoretical Foundation

The paper builds on several statistical foundations:

Score definition: For a solver θ\theta, the population score is defined as:

J(θ)=EX∼D,Ω[u(X,Sθ(X,Ω))]J(\theta) = \mathbb{E}_{X \sim \mathcal{D}, \Omega}\left[u\left(X, S_\theta(X, \Omega)\right)\right]

where u(x,s)∈[0,1]u(x, s) \in [0,1] is the score of output ss on task xx.

False Evolution Rate (FER): For tolerance ε∈[0,1)\varepsilon \in [0,1), with Δt=J(Θ~t)−J(Θt−1)\Delta_t = J(\tilde{\Theta}_t) - J(\Theta_{t-1}):

FERε(T)=E[∑t≤T1{Δt≤−ε}AtRT∨1]\text{FER}_\varepsilon(T) = \mathbb{E}\left[\frac{\sum_{t \leq T} \mathbb{1}\{\Delta_t \leq -\varepsilon\} A_t}{R_T \vee 1}\right]

where RT=∑t≤TAtR_T = \sum_{t \leq T} A_t is the number of accepted updates.

Hypothesis testing formulation: In each round tt, TRUST tests:

H0t:Δt≤−ε,H1t:Δt>−εH_0^t: \Delta_t \leq -\varepsilon, \quad H_1^t: \Delta_t > -\varepsilon

Key theoretical foundations include:

  • False discovery rate (FDR) control (Benjamini & Hochberg, 1995)
  • e-value testing with betting interpretation (Shafer, 2021)
  • e-BH and e-LOND procedures allowing arbitrary dependence (Wang & Ramdas, 2022)
  • Noninferiority testing (Blackwelder, 1982) to allow a possible loss tolerance
  • Overlap correction for bias from reusing validation samples (Dwork et al., 2015)

Methodology

Problem Setup

The self-improvement process starts with initial incumbent Θ0\Theta_0 and recursively generates/evaluates candidates over TT rounds. A fixed validation pool VN=(Z1,…,ZN)∼DNV_N = (Z_1, \ldots, Z_N) \sim \mathcal{D}^N of size NN is used, with n≤Nn \leq N tasks drawn uniformly without replacement each round.

TRUST Algorithm Components

1. Testing Level Allocation with Context:

The testing level αt\alpha_t is allocated using an e-LORD rule within the e-GAI framework:

αt=min⁡{αmax⁡,ρtBt(Rt−1+1)}\alpha_t = \min\{\alpha_{\max}, \rho_t B_t (R_{t-1} + 1)\}

where BtB_t is the remaining FER budget, ρt\rho_t is the spending fraction, and Rt−1R_{t-1} is the number of prior acceptances. The budget charge is:

ct=αtRt−1+1,Bt+1=Bt−ctc_t = \frac{\alpha_t}{R_{t-1} + 1}, \quad B_{t+1} = B_t - c_t

An LLM analyzes historical context CtC_t to produce a multiplier wt=Ψ(Ct)w_t = \Psi(C_t), adjusting the spending fraction:

ρt=clip(wtT−t+1,ρmin⁡,ρmax⁡)\rho_t = \text{clip}\left(\frac{w_t}{T-t+1}, \rho_{\min}, \rho_{\max}\right)

2. E-Value Construction with Overlap Correction:

The score difference Dt,i∈[−1,1]D_{t,i} \in [-1,1] is rescaled to Yt,i=(1+Dt,i)/2∈[0,1]Y_{t,i} = (1 + D_{t,i})/2 \in [0,1]. The null boundary becomes pε=(1−ε)/2p_\varepsilon = (1-\varepsilon)/2. The overlap-corrected boundary is:

ut,i(β)=pε+ζt,iβu^{(\beta)}_{t,i} = p_\varepsilon + \zeta_{t,i}\beta

where ζt,i\zeta_{t,i} is the exposure probability (probability that the current sample was previously used) and β\beta is the correction strength.

The sequential e-value evidence is:

Mt,m(β)=∏i=1m[1+ηt,i(Yt,i−ut,i(β)ut,i(β))]M^{(\beta)}_{t,m} = \prod_{i=1}^{m}\left[1 + \eta_{t,i}\left(\frac{Y_{t,i} - u^{(\beta)}_{t,i}}{u^{(\beta)}_{t,i}}\right)\right]

with betting fractions ηt,i∈[0,1)\eta_{t,i} \in [0,1) chosen adaptively.

3. Acceptance Rule: Accept the candidate at the first m≤nm \leq n where Mt,m(β)≥1/αtM^{(\beta)}_{t,m} \geq 1/\alpha_t.

Theoretical Assumptions

Assumption 1 (Overlap correction validity): For any tt and ii:

E[Yt,i∣Ht,i−1,Qt,i=1]≤pε+β, if H0t is true\mathbb{E}[Y_{t,i} | H_{t,i-1}, Q_{t,i} = 1] \leq p_\varepsilon + \beta, \text{ if } H_0^t \text{ is true}

Assumption 2 (Power consistency conditions):

  • (a) P(UT=0)≤rN,n→0P(U_T = 0) \leq r_{N,n} \to 0 (proposer generates improvements with high probability)
  • (b) n/N→0n/N \to 0 (overlap becomes negligible)
  • (c) 0<η−≤ηt,i≤η+<2ε/(1+ε)0 < \eta_- \leq \eta_{t,i} \leq \eta_+ < 2\varepsilon/(1+\varepsilon) (bounded betting fractions)

Empirical Validation / Results

Experimental Setup

  • Benchmarks: HotpotQA, DROP, APPS
  • Models: DeepSeek-V4-Flash, Qwen-3.8-Flash
  • Validation: 200 examples; Test: 300 held-out examples
  • Editable harness: 20 operators across 4 components (reasoning, routing, memory, workflow)
  • Baselines: Greedy, PACE (e-process test), SGM-B (Bernstein), SGM-H (Hoeffding)
  • TRUST parameters: q=0.30q = 0.30, ε=0.10\varepsilon = 0.10, β=0.01\beta = 0.01

Main Results

Table 1: Main Comparison (DeepSeek-V4-Flash)

DatasetGateGain (pp) ↑FER₀ (%) ↓TER (%) ↑MDD (pp) ↓
HotpotQAGreedy7.87 ± 0.5564.67 ± 3.2840.03 ± 5.064.96 ± 0.93
PACE10.15 ± 0.750.0012.63 ± 3.650.00
SGM-B0.000.000.000.00
SGM-H0.000.000.000.00
TRUST11.58 ± 1.3010.00 ± 10.0018.11 ± 8.390.02 ± 0.02
DROPGreedy36.24 ± 2.1935.28 ± 1.6860.12 ± 7.775.38 ± 1.58
PACE29.70 ± 0.590.006.68 ± 1.670.00
SGM-B0.000.000.000.00
SGM-H0.000.000.000.00
TRUST31.47 ± 1.420.0011.93 ± 1.290.00
APPSGreedy33.89 ± 2.7141.08 ± 4.3150.83 ± 2.898.48 ± 2.23
PACE28.68 ± 2.660.005.19 ± 1.000.00
SGM-B0.000.000.000.00
SGM-H0.000.000.000.00
TRUST34.55 ± 1.040.0011.64 ± 3.530.00

Key findings:

  • TRUST achieves the highest final gain in 4 of 6 settings
  • TRUST maintains FER₀ below 30% in all settings; Greedy exceeds 30% everywhere
  • Maximum drawdown for TRUST is only 0.27 pp vs. 8.48 pp for Greedy
  • SGM-B never accepts updates; SGM-H accepts only 3 updates across all runs (overly conservative)
  • TRUST achieves higher scores and TER than PACE in all six settings

Ablation Studies

Parameter sensitivity (HotpotQA/DeepSeek-V4-Flash):

  • FER budget qq: Larger qq → more aggressive (higher TER and FER₀); gain peaks at q=0.3q = 0.3
  • Noninferiority margin ε\varepsilon: ε=0\varepsilon = 0 produces no accepted updates; ε=0.15\varepsilon = 0.15 yields early gains but 5.33 pp MDD
  • Overlap correction β\beta: FER₀ drops from 23.33% (β=0\beta=0) to 0% (β=0.03\beta=0.03); gain peaks at β=0.01\beta = 0.01 (11.58 pp)

LLM guidance ablation: TRUST with LLM achieves 44.91 ± 1.36% vs. 43.78 ± 1.18% without, demonstrating the benefit of contextual allocation.

Theoretical Results

Theorem 1 (Conditional e-value validity): Under Assumption 1, the statistic Mt,m(β)M^{(\beta)}_{t,m} satisfies:

E[Mt,m(β)∣Ftpre]≤1, if H0t is true\mathbb{E}[M^{(\beta)}_{t,m} | F_t^{\text{pre}}] \leq 1, \text{ if } H_0^t \text{ is true}

This also holds at any stopping time τt≤n\tau_t \leq n, justifying the early-stopping acceptance rule.

Theorem 2 (FER control):

FERε(T)≤q\text{FER}_\varepsilon(T) \leq q

Theorem 3 (TER consistency): Under Assumption 2, there exists κ>0\kappa > 0 such that:

TER(T)≥1−rN,n−Te−κn\text{TER}(T) \geq 1 - r_{N,n} - T e^{-\kappa n}

Hence TER(T)→1\text{TER}(T) \to 1 as N,n→∞N, n \to \infty. This reveals the theoretical role of noninferiority: when ε=0\varepsilon = 0, no positive betting fraction satisfies Assumption 2(c), so positive ε\varepsilon is needed for TER convergence.

Theorem 4 (Gain lower bound):

G(T)≥(1−e−κn)PT−∑t=1TE[Atmin⁡{(−Δt)+,ε}+αt(−Δt−ε)+]\mathcal{G}(T) \geq (1 - e^{-\kappa n})\mathcal{P}_T - \sum_{t=1}^{T}\mathbb{E}\left[A_t \min\{(-\Delta_t)^+, \varepsilon\} + \alpha_t(-\Delta_t - \varepsilon)^+\right]

where PT=∑t=1TE[(Δt)+]\mathcal{P}_T = \sum_{t=1}^{T}\mathbb{E}[(\Delta_t)^+] is the expected total positive effect of proposed candidates.

Theoretical and Practical Implications

Theoretical Implications

  1. Bridge between hypothesis testing and RSI: The paper connects statistical testing criteria (FER control) to concrete performance metrics (final gain, TER), providing a rigorous foundation for analyzing acceptance gates in self-improving agents.

  2. Role of noninferiority: The analysis reveals that a positive tolerance margin ε\varepsilon is theoretically necessary for power consistency—without it, no betting strategy can satisfy the assumptions for TER convergence.

  3. LLM guidance with guarantees: The FER guarantee does not depend on the LLM correctly identifying beneficial candidates. The LLM only influences budget allocation, not the statistical validity, ensuring safety even with imperfect contextual judgment.

  4. Adaptive stopping: FER control extends to any stopping time with respect to the self-improvement history, allowing the process to be stopped based on observed performance without losing guarantees.

Practical Implications

  1. Safe autonomous improvement: TRUST enables agents to improve autonomously while bounding the risk of accepting harmful updates, addressing a critical safety concern for deployed AI systems.

  2. Interpretable parameters: The three key parameters (qq, ε\varepsilon, β\beta) provide intuitive control over gate behavior:

    • qq: overall risk budget for false evolution
    • ε\varepsilon: acceptable loss tolerance
    • β\beta: correction for validation data reuse
  3. Resource efficiency: Unlike conservative FWER-controlling methods (SGM-B, SGM-H) that effectively never accept updates, TRUST maintains statistical safety while achieving meaningful improvements, making it practical for real-world RSI.

  4. Case study insights: The paper demonstrates concrete failure modes of greedy gates—e.g., an update that improves validation performance by memorizing a repeated question but degrades test performance by altering evidence selection on new questions.

Conclusion

TRUST applies online multiple hypothesis testing to control the False Evolution Rate across rounds in self-improving agents, with LLM guidance and interpretable parameters for adjusting gate behavior. The framework:

  1. Balances reliability and improvement: Achieves high final gains (24.84 pp average) while maintaining FER₀ at 2.78% (vs. 45.59% for Greedy) and near-zero drawdowns.

  2. Provides rigorous guarantees: FER control, TER consistency, and gain lower bounds under explicit, interpretable assumptions.

  3. Outperforms existing statistical gates: Achieves higher final scores than PACE, SGM-B, and SGM-H while maintaining safety.

Limitations and Future Directions

  • Parameter tuning: The paper does not address how to identify the exact overlap correction strength β\beta from data or optimally tune other parameters.
  • Conservative guarantees: The noninferiority margin provides interpretable tolerance, but theoretical guarantees can be conservative and only partially explain practical behavior.
  • LLM allocator errors: The LLM can occasionally make mistakes when judging candidate updates, potentially leading to poor multiplier choices.
  • Optimization: Optimizing the gate to maximize gain while keeping safety metrics within target ranges is a promising direction for future work.

The framework extends existing statistical methods and provides a flexible statistical foundation for making recursive self-improvement more trustworthy and effective.

Related papers