A Formulation of Recursive Self-Improvement and Its Possible Efficiency

Wenyi WangarXiv 2018 · OpenReview

TL;DR

This paper tackles the long-standing AI dream of Recursive Self-Improvement (RSI) by providing a formal mathematical framework for a class of RSI systems. The authors demonstrate the existence of computable and efficient RSI systems within this framework, showing empirically that they can achieve logarithmic runtime complexity with respect to the search space size, suggesting practical efficiency is achievable.

What Problem Does This Paper Address?

The concept of Artificial General Intelligence (AGI) often includes the idea of systems that can recursively improve themselves, leading to a potential "intelligence explosion." While this idea has been around since the dawn of computing, it has largely remained in the realm of philosophy and speculation, lacking concrete mathematical formulations and empirical evidence. Existing work often focuses on architectures or methodologies rather than a formal definition and proof of concept. This paper aims to bridge that gap by providing a formal definition for a specific type of RSI system and demonstrating its computability and efficiency.

Methods

The authors define an RSI system as a sequence of programs where each program generates the next, with an increasing ability to create "better" future programs. They formalize this by considering a finite set of programs ($P$) and a score function ($S$) over $P$, where a lower score indicates a better program. An RSI system iteratively generates a new program ($p'$) from the current program ($p$) and replaces $p$ with $p'$ if $p'$ is better according to $S$.

A key contribution is the development of a consistent score function. They propose using the expected number of steps to reach an "optimal" program as the score. This score function is constructed iteratively, ensuring that programs are added in nondecreasing order of their scores. The paper also models the program generation process as a homogeneous Markov chain, where each program defines a fixed probabilistic distribution over $P$.

Datasets

Not discussed in the paper. The paper focuses on theoretical formulation and simulation with synthetically generated program distributions.

Key Insights and Ideas

  • Formalizing the Dream: The paper moves the concept of RSI from philosophy to a formal mathematical domain, providing a concrete definition and a basis for theoretical analysis.
  • Score Function as Expected Steps: Defining the "goodness" of a program by the expected number of steps to reach an optimal program is an elegant way to create a consistent and computable score function.
  • Logarithmic Runtime Potential: The empirical results showing logarithmic runtime complexity with respect to the search space size are a significant finding, suggesting that efficient RSI might be practically achievable.
  • Markovian Simplification: While a simplification, the assumption of a homogeneous Markov chain for program generation still allows for the demonstration of efficient RSI, hinting that more complex dependencies might not be strictly necessary for efficiency.

Key Results

The paper demonstrates the existence of computable and efficient RSI systems within their defined framework. Through simulations, they show that their proposed RSI procedure achieves logarithmic runtime complexity with respect to the size of the search space. Specifically, Figure 2a shows a linear relationship between the number of programs ($l$) and the expected number of steps to reach the optimal program, and Figure 2b shows a linear relationship between the number of programs ($n$) and the rank of the uniform sampling program. Figure 3 further illustrates that the ranks of the current program improve exponentially in a statistical sense during the simulation, with all processes converging to the global optimal program.

Limitations and Future Work

The authors acknowledge that their current formulation is for a restricted class of RSI systems that satisfy the Markov assumption. They suggest several avenues for future work:

  • Embedding Histories: Expanding the model to incorporate past program generation history when creating new programs.
  • Program-as-Argument: Modeling programs that take another program as an argument and return a suggested improvement.
  • Oracle Score Function: Designing score functions that do not require enumerating all other programs for evaluation, which is crucial for practical applicability. They propose evaluating programs based on their performance on evaluable tasks or studying the reasoning behind a program's future behavior.
  • Biased, Noisy, or Inconsistent Score Functions: Investigating the behavior of RSI procedures when the score function deviates from the ideal properties analyzed in the paper.

Summary updated

Abstract

Recursive self-improving (RSI) systems have been dreamed of since the early days of computer science and artificial intelligence. However, many existing studies on RSI systems remain philosophical, and lacks clear formulation and results. In this paper, we provide a formal definition for one class of RSI systems, and then demonstrate the existence of computable and efficient RSI systems on a restricted version. We use simulation to empirically show that we achieve logarithmic runtime complexity with respect to the size of the search space, and these results suggest it is possible to achieve an efficient recursive self-improvement.
BibTeX
@misc{wang2018formulation,
  author = {Wenyi Wang},
  title = {{A Formulation of Recursive Self-Improvement and Its Possible Efficiency}},
  year = {2018},
  eprint = {1805.06610},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.06610},
}

Loading related content...

Figure