With the rise of large language models, agentic systems can write code, invoke tools, revise prompts, and propose changes to their own components. This autonomy raises a core safety question for self‑improvement: can an automated gate such as a reward model or reviewer reliably decide whether a proposed update should be accepted?
The difficulty is structural. The gate must be a terminating, computable procedure, while the property we care about—whether an update truly improves a semantic score—may depend on unbounded program behavior and thus be non‑computable. We model agents as programs and define improvement via a semantic score that need not be computable. We study two evaluation abstractions: a certifier that approves or rejects an update, and a search procedure that, given a proposal generator, attempts to output an improving candidate when one exists.
We show that in the fully general setting no terminating procedure can simultaneously guarantee reliability (never accepting a non‑improvement) and non‑conservatism (never missing an available improvement): self‑referential constructions can force any such gate or searcher to fail. Randomized gates with bounded error face the same limit. We then identify a standard decidable regime used in practice—bounded evaluation and a finite proposal budget—under which exhaustive simulation yields a terminating search procedure with the desired guarantees.
We also demonstrate the limit of this recovery: a chain of accepted updates can raise the bounded score each round while the true score falls. Our results delineate a boundary where correctness guarantees collapse in unbounded, universal settings and where they can be recovered by design in bounded settings. Review