Summary of "The Self-Improvement Problem"

Summary (Overview)

• Core finding: In fully general (unbounded) settings, no terminating computable procedure can simultaneously guarantee both reliability (never accepting a non-improvement) and non-conservatism (never missing an available improvement) for verification-gated self-improvement systems.
• Structural impossibility: The obstruction is not statistical but structural—self-referential constructions allow proposals to exploit the evaluator (the "evaluator hacking" phenomenon), formalizing folklore concerns from AI safety into explicit theorems.
• Recovery via boundedness: Under standard practical restrictions (bounded evaluation and finite proposal budgets), exhaustive simulation yields a terminating searcher with the desired guarantees relative to the bounded proxy score.
• Additional results: Randomization with bounded error does not help (Proposition 1), and repeated accepted updates can raise the bounded score while the true score falls (Proposition 2, "proxy drift").
• Formal verification: A Lean 4 formalization of Theorems 1–3 accompanies the paper.

Introduction and Theoretical Foundation

Background and Motivation

Modern agentic pipelines follow a common pattern: an agent proposes self-updates (code patches, prompt rewrites, new checkpoints, tool policies), and an automated gate (reward model, regression test suite, automated reviewer) decides whether to apply them. The paper formalizes a fundamental mismatch:

"The gate must be a terminating, computable procedure, while the property we ultimately care about, namely whether an update is a genuine semantic improvement, depends on potentially unbounded program behavior."

Theoretical Framework

The paper models agents as programs and uses classical computability theory tools:

• Program encoding: Each agent is identified with a program index $p \in \mathbb{N}$ (a Gödel number), with behavior given by the partial function $\varphi_p$.
• Semantic score functional: $J: \mathbb{N} \to \mathcal{S}$ represents the intended notion of performance, where $\mathcal{S}$ is a score set (e.g., $\{0,1\}$ or $\mathbb{R}$). Crucially, $J$ may be uncomputable.

Two evaluation abstractions are studied:

1. Certifier: $V: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ that approves/rejects a candidate update
2. Searcher: $S: \mathbb{N} \times \mathbb{N} \to (\mathbb{N} \cup \{\bot\})$ that attempts to output some improving candidate given access to a proposal enumerator

Key Definitions

Definition 1 (Strict improvement): Given $J: \mathbb{N} \to \mathcal{S}$ with strict order $>$, $q$ is a strict improvement over $p$ if $J(q) > J(p)$.

Definition 2 (Soundness and completeness of a certifier): A total computable $V: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ is:

• Sound: $V(p,q) = 1 \Rightarrow J(q) > J(p)$ (no false approvals / no reward hacking)
• Complete: $J(q) > J(p) \Rightarrow V(p,q) = 1$ (no blocking genuine progress)

Kleene's Recursion Theorem

The fundamental tool enabling self-referential constructions:

$$φ_e = φ_{f(e)} \quad \text{(Fixed-Point Theorem)}$$

For any total computable function $f: \mathbb{N} \to \mathbb{N}$, there exists an index $e$ such that the programs compute the same partial function. This guarantees the existence of programs whose behavior depends on their own description.

Methodology

Agent and Proposal Modeling

• Agents are executable artifacts (checkpoints + code, Python packages, container images) encoded as natural numbers
• Proposal enumerators: Total computable functions $E: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ where $E(p,i)$ denotes the $i$-th proposed modification for base agent $p$
• Gates: Either certifiers $V$ or searchers $S$, both required to be total computable (always halt)

Proof Strategy

The paper uses diagonalization via Kleene's Recursion Theorem to construct adversarial candidates whose behavior flips based on the gate's decision. The key construction: a candidate $q$ that is "good if rejected and bad if accepted."

Empirical Validation / Results

Theorem 1: No Sound-and-Complete Improvement Certifier

Define the semantic score:

$$J(p) = \begin{cases} 1 & \text{if } \varphi_p(0) \text{ halts and outputs } 1 \\ 0 & \text{otherwise} \end{cases}$$

There is no total computable function $V: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ that is both sound and complete.

Proof sketch: Construct a self-referential program $q$ such that:

$$\varphi_q(0) = \begin{cases} 0 & \text{if } V(p,q) = 1 \\ 1 & \text{if } V(p,q) = 0 \end{cases}$$

• Case A ($V(p,q) = 1$): $q$ outputs 0, so $J(q) = J(p) = 0$ — violates soundness
• Case B ($V(p,q) = 0$): $q$ outputs 1, so $J(q) > J(p)$ — violates completeness

Theorem 2: No Sound and Weakly Complete Proposal-Respecting Total Searcher

Even replacing certification with the weaker task of search does not help. A proposal-respecting searcher $S$ must return $q = E_e(p,i)$ for some $i$ when it finds an improvement. The proof constructs an enumerator $E$ whose distinguished candidate $q$ is designed adversarially to $S(p,e)$:

• If $S(p,e) = q$: the candidate outputs 0, violating soundness
• If $S(p,e) \neq q$: the candidate outputs 1 and is a genuine improvement, but the searcher must either return $\bot$ (violating weak completeness) or return a non-improving candidate (violating soundness)

Proposition 1: No Randomized Certifier with Bounded Error

A probabilistic gate that errs with probability at most $1/3$ can be derandomized: simulate all coin paths (finite by König's lemma), compute exact acceptance probability $\alpha(p,q)$, and threshold at $1/2$. This yields a deterministic sound-and-complete certifier, contradicting Theorem 1.

Theorem 3: Decidability under Bounded Evaluation and Finite Proposals

Define the bounded-horizon score:

$$J_T(p) = \begin{cases} 1 & \text{if } \varphi_p(0) \text{ halts within } T \text{ steps and outputs } 1 \\ 0 & \text{otherwise} \end{cases}$$

With an evaluation bound $T$, proposal budget $B$, and generation bound $T_E$, exhaustive simulation yields a total computable searcher $S_{T,B,T_E}$ that is:

• Sound: returns only proposals $q = E_e(p,i)$ with $i < B$ and $J_T(q) > J_T(p)$
• Weakly complete within budget: if an improving proposal exists within the budget, the searcher finds it

Proposition 2: Accepted Updates Can Lower the True Score

For $n = 2k$ tasks, construct programs $p_0, p_1, \ldots, p_k$ where each step:

1. Raises the bounded score: $J_T^{(n)}(p_{i+1}) > J_T^{(n)}(p_i)$
2. Lowers the true score: $J^{(n)}(p_{i+1}) < J^{(n)}(p_i)$

The bounded score rises from 0 to $k$ while the true score falls from $2k$ to $k$. The mechanism: each update trades slow correct behavior for fast correct behavior on fewer tasks, hiding the loss beyond the time budget.

Theoretical and Practical Implications

Why Bounded Evaluation Blocks the Diagonal

In Theorems 1–2, the adversarial candidate runs the gate as a subroutine. In the bounded regime of Theorem 3, the searcher's running time exceeds $T$ (it simulates $B$ candidates for up to $T$ steps each), so a candidate that runs the searcher inside itself cannot halt within $T$ steps—its bounded score is 0, and the self-referential flip fails.

Generalization of the Semantic Objective

The diagonal construction in Theorem 1 requires only:

1. Extensionality: $J(p)$ depends only on $\varphi_p$, not program text
2. Attainable comparability: there exist partial computable functions $\psi_{lo}, \psi_{hi}$ with $J(\psi_{lo}) < J(\psi_{hi})$

This extends the impossibility to expected rewards, benchmark success rates, and any scalar summary of trajectories.

Design Principles for Improvement Loops

The results motivate a clear design principle:

"Make the limits explicit. Timeouts, finite candidate budgets, restricted update languages, sandboxing, and occasional external or human grounding are not optional conveniences. They are the conditions under which correctness guarantees become attainable."

Proof-Carrying Updates (Gödel Machines)

A one-sided alternative: gates that accept only proposals with certificates checked by a fixed sound proof system. Such gates are sound by construction but cannot be complete—the set of provable improvements is computably enumerable while the set of true improvements is not (a $\Pi_1$ fact).

Interactive and Environment-Coupled Scores

For negative results, $J$ may be any extensional functional. For positive results (Theorem 3), interactive evaluation requires explicit assumptions: finitely many actions/observations, computable transition probabilities, computable rational rewards, and a cap on agent compute per step.

Conclusion

Main Takeaways

1. Structural impossibility in the unbounded regime: No terminating procedure can be both sound and complete (or weakly complete) for verification-gated self-improvement when proposals may be self-referential.
2. Randomness and hiddenness do not help: These defenses change who can construct the diagonal candidate, not whether it exists.
3. Boundedness restores guarantees: With explicit timeouts and finite budgets, exhaustive evaluation yields reliable guarantees relative to the bounded proxy.
4. Proxy drift persists: Even in the decidable regime, accepted updates can systematically lower the true score while raising the bounded score.

Future Directions

• Characterize how fast proxy drift can grow when the proposer adapts to the evaluation schedule
• Identify which additional constraints control drift while retaining useful progress
• Map which restrictions restore which guarantees (randomized, hidden, stateful gates; restricted update languages; compute asymmetries)
• Extend the framework to multi-agent pipelines and interactive environments

The paper's contribution is the formalization itself: a minimal model of verification-gated self-improvement that separates impossibility in the unbounded setting from recovery in the bounded setting, turning the folklore claim that "evaluator hacking is unavoidable once the proposer can model the gate" into a theorem with explicit assumptions.