Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generation

Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-23 03:25:11

Abstract: Several recent advances in AI systems solve problems by providing a "scaffolding" program that structures multiple calls to language models to generate better outputs. A scaffolding program is written in a programming language such as Python. In this work, we use a language-model-infused scaffolding program to improve itself. We start with a seed "improver" that improves an input program according to a given utility function by querying a language model several times and returning the best solution. We then run this seed improver to improve itself. Across a small set of downstream tasks, the resulting improved improver generates programs with significantly better performance than its seed improver. A variety of self-improvement strategies are proposed by the language model, including beam search, genetic algorithms, and simulated annealing. Since the language models themselves are not altered, this is not full recursive self-improvement. Nonetheless, it demonstrates that a modern language model, GPT-4 in our experiments, is capable of writing code that can call itself to improve itself. We consider concerns around the development of self-improving technologies and evaluate the frequency with which the generated code bypasses a sandbox.

Main paper: 
 introduction: 
 A language model (LM) can be queried to optimize virtually any objective describable in natural language. However, a program that makes multiple, structured calls to an LM can often produce outputs with higher objective values (Yao et al., 2022; 2023; Zelikman et al., 2023; Chen et al., 2022) . We refer to these as "scaffolding" programs, typically written (by humans) in a programming language such as Python. Our key observation is that, for any distribution over optimization problems and any fixed LM, designing a scaffolding program is itself an optimization problem. In this work, we introduce the Self-Taught Optimizer (STOP), a method in which code that applies an LM to improve arbitrary solutions is applied recursively to improve itself within a defined scope. Our approach begins with an initial seed 'improver' scaffolding program that uses the LM to improve a solution to some downstream task. As the system iterates, the model refines this improver program. We use a small set of downstream algorithmic tasks to quantify the performance of our self-optimizing framework. Our results indicate potential improvements when the model applies its self-improvement strategies over increasing iterations within the contexts of our experiments. Thus, STOP shows how LMs can act as their own meta-optimizers. We additionally investigate the kinds of self-improvement strategies that the model proposes (see Figure 1 ), the transferability of the proposed strategies across downstream tasks, and explore the model's susceptibility to unsafe self-improvement strategies. Seed Prompt for Self-Improvement 1 from helpers import extract_code 2 3 def improve_algorithm(initial_solution, utility, language_model): 4 """Improves a solution according to a utility function.""" 5 expertise = "You are an expert computer science researcher and programmer, especially skilled at → optimizing algorithms." 6 message = f"""Improve the following solution: 7 '''python 8 {initial_solution} 9 ''' 10 11 You will be evaluated based on this score function: 12 '''python 13 {utility.str} 14 ''' 15 16 You must return an improved solution. Be as creative as you can under the constraints. 17 Your primary improvement must be novel and non-trivial. First, propose an idea, then implement it. Figure 2 : Our seed improver. Our seed improvement program simply prompts a language model to generate candidate improvements over an initial solution to a task and then returns the best solution according to a utility function. STOP (Algorithm 1) uses this improver to recursively improve itself.We refer to this problem as recursively self-improving code generation, which is inspired by but not completely a Recursively Self-Improving (RSI) system because the underlying language model remains unchanged. The broader concept of RSI dates back at least half a century, formalized by Good (1966) and later by Schmidhuber (2003) , but our work represents a more modest and specific application of these ideas. However, that work focused on the development of more generally capable systems and assumed that the model was permitted to refine every aspect of its code. Our work is a small step in that direction, focusing only on the ability of the model to recursively improve the scaffold that calls it. This paper first formulates the RSI-code-generation problem in a mathematically well-defined fashion. We then define and evaluate STOP, which demonstrates the potential utility of RSI-code-generation. Improvements are shown across a variety of downstream tasks. Figure 1 illustrates a number of the functional and interesting scaffolds proposed by STOP when using a version of the GPT-4 language model (OpenAI, 2023b) trained on data up to 2021, well in advance of the introduction of most scaffolding systems. Further explorations in Section 6.2 measure the rate at which the model attempts to disable a sandbox flag, providing early but intriguing findings in this area. Lastly, Section 8 discusses concerns related to the responsible advancement of such technologies.Contributions. The main contributions in this work are (a) formulating an approach to metaoptimization where a scaffolding system recursively improves itself, (b) providing a case study where a system, using a modern language model (GPT-4) can successfully recursively improve itself, and (c) investigating the self-improvement techniques proposed and implemented by the model, including the ways in which the model circumvents safety measures such as a sandbox. 
related work: 
 Language Model Scaffolding. Many prompting strategies and scaffolds have been developed to enable more systematic reasoning in language models (Wei et al., 2022b; Yao et al., 2022; 2023; Zelikman et al., 2023; Chen et al., 2022; Zhou et al., 2022a; Khattab et al., 2022; Jiang et al., 2022; Sel et al., 2023; Besta et al., 2023; Poesia et al., 2023) . For example, scratchpads and chain-of-thought rely on communicating to the model that it should work through a problem step-by-step (Nye et al., 2021; Wei et al., 2022b) . Tree-of-Thoughts algorithmically scaffolds the model to consider branching paths of reasoning steps (Yao et al., 2023) . Graph of thoughts extends this, allowing other graph operations (where nodes are reasoning steps), such as aggregation (Besta et al., 2023) . Other work has focused on letting models reason with access to an interpreter such as Program of Thoughts prompting (Chen et al., 2022) , Program-aided Language Models (Gao et al., 2023) , Reflexion (Shinn et al., 2023) , or ReAct (Yao et al., 2022) , while yet others formalized this scaffolding structure such as Demonstrate-Search-Predict (DSP) (Khattab et al., 2022) , Language Model Cascades (Dohan et al., 2022) , or Cognitive Architectures (Sumers et al., 2023) . Each work can be understood as the result of researchers asking, "Given an imperfect language model, how can we provide structure to help it solve problems?" We instead ask if the language model can design that structure for itself and use its proposed structure to recursively improve that structure. Surprisingly, we even find that GPT-4 naturally proposes several of these techniques despite not having them in its training data.Algorithm 1: Self-Taught Optimizer (STOP) Input: Seed improver I 0 , language model L, recursion depth T , collection of downstream tasks D Output: An improved improver I T for t = 1 to T do Language Models as Prompt Engineers. Work has also explored the ability of language models to optimize prompts, such as the Automatic Prompt Engineer (APE) (Zhou et al., 2022b) or, recently, OPRO (Yang et al., 2023) and Promptbreeder (Fernando et al., 2023) . Note that, for these, the goal has consistently been to scaffold the language model to produce a prompt but not to scaffold it to produce a better scaffolding (beyond prompting-only scaffolds like zero-shot chain of thought), nor to produce a recursively applicable scaffolding. In other words, these prior works can be understood as proposing particular new scaffolds for prompt engineering but not for proposing new scaffolds. But, we share the inspiration of using the model to improve its reasoning without fine-tuning. Language Model Self-Improvement. Prior work, such as STaR (Zelikman et al., 2022) , demonstrated that language models can learn to solve harder problems by learning from their reasoning chains by filtering based on incorrect answers (as well as Huang et al. 2022 , which explored the specific case where a majority vote is used as the filter and Uesato et al. 2022, which emphasized the value of checking the accuracy of the reasoning itself). Inspired by self-play in games, Haluptzok et al. (2023) designed a self-improvement framework for code generation where a language model generates novel problems for fine-tuning itself. Related work has explored teaching language models to debug or optimize code (Chen et al., 2023b; Shypula et al., 2023) . However, our approach is orthogonal to these, as we do not leverage fine-tuning and instead focus on a model's ability to improve code that allows it to solve problems. Other related works are Voyager (Wang et al., 2023) , showing that a language model can optimize the programs available to an embodied agent to improve exploration in the video game Minecraft, and its contemporaneous work Language Models as Tool Makers (Cai et al., 2023) .I t ← I t-1 (û, I t-1 , L) //Recursive Self-Improvement (RSI). RSI was suggested by Minsky (1966) and Good (1966) , as cited by Yampolskiy (2015) . Schmidhuber (2003) first provided a rigorous formalization, wherein a problem solver would leverage itself to solve iteratively harder problems by making provable improvements to itself. Some of these principles are also highlighted in Schmidhuber (1987) . Unlike this work, we do not attempt to prove that scaffold improvements made by the model are optimal. As mentioned, RSI code generation differs from full RSI because only the scaffolding is improved. Additionally, many previous analyses involved selecting programs at random (i.e., "monkeys at typewriters") or enumeration with no dependence on the goal to be improved (Levin, 1973) . In contrast, using language models, we can describe the underlying goal in a prompt (which itself may be improved). Intuitively, providing this goal may make program search more effective. Some work has also suggested constraining the types of improvements (Nivel et al., 2013; Steunebrink et al., 2016) so as to encourage improvements that mitigate dangerous behavior. Regarding implementations, while efforts have been made for Gödel machines (Hall, 2007; Steunebrink & Schmidhuber, 2012) , our work is first to leverage language models for recursively self-improving code generation. 
problem statement: 
 In this section, we formulate the goal of selecting an improver via recursively self-improving code generation. This is viewed as a computationally expensive "pre-optimization" step with benefits that can be reaped in numerous downstream applications. First, we present definitions. Formally, let Σ * denote the set of finite text strings, and suppose we have a randomized black-box language model L : Σ * → Σ * which can be used to generate code, given a query. A utility u = (u func , u str ) is a pair where u func : Σ * → R is a black-box, possibly randomized function that assigns bounded real values to solution strings; and u str ∈ Σ * is a description which may simply be the source code of the function. With a slight abuse of notation we write u(x) ≡ u func (x) for solution x. A task τ = (u, s) is specified by utility u and a solution s ∈ Σ * . In our applications, solutions s are strings representing the source code of a program, but more generally any utility defined on strings can be used. Figure 3 : A pipeline for self-improvement. STOP (Algorithm 1) uses a seed improver program to iteratively optimize its own code using language model calls and a meta-utility function that evaluates how well an improver optimizes code for downstream tasks.An improver I is a program that improves a task solution using a language model L:s ′ = I(u, s, L) ideally with high utility u(s ′ ) ≫ u(s). Suppose there is a distribution D over downstream tasks τ ∼ D. Thus, the goal is to find an improver program I with high expected utility when used on a task, ū(I) ≜ E (u,s)∼D u(I(u, s, L)) .For training, we assume that we are given a collection of n downstream tasks D ∼ D n drawn independently from distribution D. We correspondingly define the meta-utility û of an improver I as the average utility over downstream training tasks, û(I) ≜ 1 |D| (u,s)∈D u(I(u, s, L)). The above equations define ūfunc and ûfunc . For their description string, we use a common "grey-box" description ūstr = ûstr which is a description (e.g., source code) indicating that the utility is the expectation over a set of downstream tasks, but the individual downstream tasks themselves are not included in the description. This enables one to optimize over û as an approximation to the actual objective ū. In addition, our theoretical analysis in Appendix A provides simple conditions under which optimizing û also nearly optimizes ū, and formalizes resource bounds on runtime and language models. Finally, Appendix A also gives an equivalent formulation of recursively self-improving code generation in terms of recursive maximization. However, in the maximization framework, no initial solution must be given. In this paper, STOP adopts the improver formulation because we have found the initial solution valuable for warm-starting the self-improvement process, but we suggest that the recursive maximization framework is more amenable to theoretical analysis. 
self-taught optimizer (stop): 
 Figure 3 provides a visual schematic of the self-improvement pipeline envisaged in Section 3, while Algorithm 1 provides pseudocode for this Self-Taught Optimizer (STOP). The key observation is that the selection of I is an optimization problem itself, to which we can recursively apply improvement. STOP begins with an initial seed improver I 0 . We define the t-th improver as the output of t successive rounds of self-improvement with meta-utility û: I t ≜ I t-1 (û, I t-1 , L). This is iterated for some prespecified number of iterations T , depending on available resources.Intuition. By using û, STOP selects improver based on a downstream utility improvement. This approach is motivated by the intuitions that 1) improvers that are good at improving downstream solutions may be more likely to be good scaffolding programs and thus to be good at self-improvement, and 2) selecting for single-round improvements may lead to better multi-round improvements. In practice, we allow the utilities and language model to impose budget constraints and initial solutions to be generated by humans or a model. Moreover, the cost is essentially O((budget u + budget L ) * budget û), where budget terms correspond to the number of times an improver can use that function.Designing the seed improver. Our chosen seed improver (Figure 2 ) simply prompts the LM to generate candidate improvements of an initial solution and then returns the best solution according to the utility function. We chose this particularly simple form to provide nontrivial improvement for a generic downstream task while 1) encouraging the LM to be as "creative" as possible, 2) minimizing initial prompt complexity, since self-improvement introduces additional complexity due to nested references to code strings inside of prompts, and 3) minimizing the prompt token count and therefore the costs of querying a LM. We also considered other variants of this seed prompt but heuristically found that this version maximized the novelty of improver improvements proposed by GPT-4. Iteration 0 records the performance of the seed improver I 0 . Given access to a strong language model like GPT-4 (left), STOP monotonically improves mean downstream performance. In contrast, with the weaker GPT-3.5 language model (right), mean performance degrades. Details are in Section 5.1.Describing the utility. To effectively convey the details of the utility function to the LM, we provide the utility to the improver in two forms, as a callable function and as a utility description string containing the essential elements of the utility source code (see Appendices E and F for examples). This choice was made for the following reasons. The description allows us to clearly convey budgetary constraints (e.g., on runtime or function calls) imposed by the utility to the LM. We first attempted to describe budgetary instructions in the seed improver prompt, but, as we discuss in Section 6.2, this led to the removal of such instructions and attempts at reward-hacking in later iterations. The downside of our approach is that it separates the constraints from the code to be optimized by the LM, which may decrease the likelihood that it will be used by the LM (Liu et al., 2023) . Finally, we observe empirically that replacing the source code with a purely English description of the utility leads to a reduced frequency of non-trivial improvement. 
experiments and results: 
 We explore 1) the benefits of self-improvement over a static seed improver for a fixed target task, 2) how well an improver trained on one task generalizes to new tasks, and 3) how model size may affect performance. Timestamped versions of the two models we utilize, gpt-4-0314 and gpt-3.5-turbo-0613, are available within the OpenAI API, to aid with reproducibility.We begin by evaluating STOP on a fixed downstream task with GPT-4. We select the task of learning parity with noise (LPN) (Blum et al., 2000) as a less-well-known, quickly-testable, and difficult algorithmic task. Note that better-known tasks have solutions more widely available online. In LPN, bitstrings are labeled with parity computed over an unknown subset of bits; given a training set of bitstrings with noisy labels, one must predict new bitstrings' true labels. Noiseless LPN is easily solved via Gaussian elimination, but noisy LPN is conjectured to be computationally intractable for large input dimensions (Blum et al., 2000) -we use a tractable 10-bit input dimension. To define a downstream utility u, we sample M = 20 independent instances of the LPN task with a short timeout and a small amount of noise and return a solution's average accuracy on those instances. For the initial solution s, we use a simple random sampling approach described in Appendix J. Finally, since the LM and hence improver are stochastic, we choose D to be 5 identical copies of (u, s) in Algorithm 1. To evaluate the generalization of each improved improver to new problem instances of the same task, we report test meta-utility on an independent set of M test = 50 LPN instances not seen during improvement.Figure 4 (left) reports mean test û (±1 standard error) across 5 independent STOP runs, showing improved downstream performance from 1-3 self-improvement rounds. Note, however, that, per run, improvement need not be monotonic, as 1) a better improver on downstream tasks need not be better at optimizing itself and 2) there is inherent stochasticity in the evaluation from nondeterministic LM calls. But, as the LM does not see the downstream task when prompted from the self-improving scaffold-each prompt contains only a template with placeholders for the task and solution-the LM cannot directly optimize the improver for the downstream task. We also evaluate two additional baselines for reference: a chain-of-thought baseline i.e., the seed improver with one attempted improvement and no utility calls (Wei et al., 2022b) ) and a greedy iterative improver (i.e., make the maximum permissible calls, select the best improvement, repeat as the budget allows). Across ten runs, the chain-of-thought baseline has a meta-utility of 57.7%±3.0% when it doesn't error (49.6%±3.5% with errors), while the greedy iterative improver scores 64.2%±0.9%. Our next set of experiments explores whether an improved improver is transferable across downstream tasks. Note that transferability is plausible as, in the self-improvement phase, the self-improver is not shown the downstream utility or downstream solution, only the metautility and its own improver code. Specifically, we select a better-performing improver from Section 5.1 generated by T = 4 STOP iterations and evaluate it on five new downstream tasks. Remarkably, we find the improved improver, detailed in Appendix H, outperforms the seed improver on each new downstream task without further optimization, as shown in Table 1 . As with LPN, we selected three tasks that are easy to evaluate, not very well known, and still fairly difficult: String Grid Distance, a string manipulation problem featured in a recent programming competition (https://codeforces.com/problemset/ problem/1852/D); a version of the quadratic assignment problem where each facility has a preference over each location that must also be considered when minimizing costs (Koopmans & Beckmann, 1957) ; and, parity without noise, as another form of generalization. We also include two well-known tasks: identifying solutions to random 3-SAT formulae and solving instances of the maxcut problem, both with short time constraints. The corresponding utilities and initial solutions are in Appendix G.We next explore the ability of a smaller language model, GPT-3.5-turbo, to improve its scaffolding.Following the protocol of Section 5.1 with 25 independent runs instead of 5, we find that GPT-3.5 is sometimes able to propose and implement better scaffolds, but only 12% of GPT-3.5 runs yielded at least a 3% improvement. In addition, GPT-3.5 exhibits a few unique failure cases that we did not observe with GPT-4. First, we found it was more likely to propose an improvement strategy that did not harm a downstream task's initial solution but did harm the improver code (e.g., randomly replacing strings in lines with some low probability per line, which had less impact on shorter solutions). Second, if the proposed improvements mostly harmed performance, suboptimal scaffoldings that unintentionally returned the original solution could be selected, resulting in no continued improvement as seen in Figure 4 right. Generally, the "ideas" behind the improvement proposals were reasonable and creative (e.g., genetic algorithms or local search), but implementations were often overly simplistic or incorrect. We observe that, initially, the seed improver with GPT-3.5 has a higher meta-utility than the one with GPT-4 (65% vs 61%). We attribute this primarily to a slightly higher prevalence of more complex solutions by GPT-4 that time out, such as training a neural network written with numpy for a thousand epochs. Moreover, the apparent difference in these models' improvement abilities may be partially explained by prior work on emergent abilities of LMs (Wei et al., 2022a) . 
inspecting the improvements: 
 Next, we qualitatively investigate the self-improvement strategies proposed by STOP, highlighting both the encouraging and novel approaches as well as some undesirable patterns. We notably find that a small fraction of generations attempt to perform reward hacking or sandbox circumvention.We begin by discussing a number of proposed self-improvement strategies, with examples detailed in Appendix B and visualized in Figure 1 . While each strategy was implemented by STOP, not all were ultimately selected by the improvement code, and some used an earlier iteration of the seed improver than that shown in Figure 2 (see Appendix Figure A.19) . Nonetheless, a variety of self-improvement strategies were selected as improved improvers, including the example given in Figure 5 . Beam search. The most common meta-heuristic we observed used by the model was beam search: the model would keep a list of all of its improvement attempts based on utility and expand the best k in the list. This has some similarity to the Tree-of-Thoughts approach (Yao et al., 2023) which was invented years after the training cutoff for the GPT-4 version we used (Sept. 2021).Genetic and evolutionary algorithms. One of the most common approaches proposed by the model was to use a genetic algorithm. Many of these attempts were infeasible in some essential way; for example, many attempts would include mutations that perturbed random characters or lines or performed crossover based on combining strings, which is extremely unlikely to work. However, aSelf-Improved Improver Figure 5 : Example of a self-improved improver after T = 10 iterations. This algorithm maintains a population of top solutions and uses an epsilon-greedy strategy to balance exploiting known good solutions and exploring new ones. Each exploration step corresponds to a higher-temperature sample, and epsilon is adjusted dynamically based on the relative rates of utility improvement from exploration and exploration. Temperature is also managed dynamically to adapt an exploration-exploitation tradeoff. Finally, an improvement stopping criterion and reset mechanism are used for efficiency.portion of attempts were reasonable, relying on the language model to generate mutations and perform crossover. We highlight that although multiple works have proposed to use genetic or evolutionary algorithms to improve prompts or to perform neural architecture search (Chen et al., 2023a; Guo et al., 2023) , to our knowledge, all of these works were after the training cutoff for GPT-4. We include a few examples of proposed genetic algorithm implementations in Appendix B.Decomposing and improving parts. A less common but notable approach we observed was where the model attempts to improve the performance one function at a time. For example, as in Appendix Figure A .12, the model separated the solution into function blocks with regular expressions and attempted improvements to each block one by one. This can be understood as analogous to Zelikman et al. (2023) : the probability that one of n solutions solves all of a problem's independent, modular parts correctly drops precipitously with the number of parts, but the probability that at least one attempt solves any given part does not depend on the number of parts. Therefore, trying combinations of attempts at parts can substantially increase success. In a related approach, the model randomized the prompt to optimize varying solution aspects at a time, for example, alternating between searching for a better data structure or a way to reduce memory usage or leveraging parallelism.Table 2: Unsandboxing. Percent of unsandboxed improvement attempts out of 10,000 (with 95% Wilson (1927) confidence intervals). Both language models attempted to run code on a small (< 1%) but non-zero fraction of initial improvements.Language Model Unsandboxing rate Unsandboxing rate with warning GPT-4 0.42% (0.31 to 0.57%) 0.46% (0.35 to 0.61%) GPT-3.5 0.12% (0.07 to 0.21%) 0.17% (0.11 to 0.27%) Simulated annealing. Despite being one of the best-known metaheuristics, to our knowledge, simulated annealing has not previously been applied as a scaffolding. This approach seems to draw on an analogy between the concepts of temperature in language modeling and in simulated annealing, where it gradually decreases and determines whether to accept a transition from a point to one with worse utility. Notably, it can find global optima despite many local optima (Goffe et al., 1994; Liu et al., 2020) .Varying temperature to explore. One alternative is to treat temperature as an exploration parameter: the closer the model is to depleting its budget, the more conservative it is with its exploration. This bears some resemblance to simulated annealing but is focused on optimizing the sampling temperature rather than controlling the acceptance criteria for the change in utility of an improved solution.Multi-armed prompt bandit and upper-confidence-bound (UCB) based search. Another method that views the optimization objective as an exploration task is reframing as a bandit problem: since the utility function can be stochastic, this approach emphasizes optimally selecting the best solution out of a set of sampled improvements.We also explore whether the language model proposes self-improvement strategies to circumvent the provided constraints (limiting the number of queries to the downstream utility, the number of language model calls, and the number of samples per language model call). We observed a few interesting patterns. First, when not strictly enforcing budget constraints, initially most generated programs would follow them, but because those that ignored the constraints performed better, these would be identified by the improver as better. Second, the constraints written in the seed improver were often omitted when revising the improver, for "simplification." Finally, although the language model is passed as an object to the algorithm to enforce the constraints, in at least one proposed solution the language model attempted to create a new language model object with larger constraints.To further explore potential risks, we implemented a functionality-limiting "sandbox" as part of the utility evaluation (see Appendix I), adding a run function with a use_sandbox=True parameter.To test the language model's frequency of sandbox adherence, we used the language model to generate 10,000 independent improvements of the seed improver. We then used a simple syntactic check for apparent "unsandboxed" executions. Specifically, we consider an improver to be unsandboxed if it contains either of the strings "use_sandbox=False" or "exec(". Since this was a computationally simple syntactic procedure, we also ran it on the OpenAI's GPT-3.5-turbo language model. Interestingly, unsandboxing was more than twice as common for GPT-4 than GPT-3.5-turbo.We also considered a second variant of the seed which included a warning, as illustrated in Figure 6 . Unsandboxing occurred at a higher average rate despite the warning, though the difference was not statistically significant for either model (via a two-proportion z-test with significance level 0.05).Results are reported in Table 2 . A manual inspection of the model's plans in the generations did not explicitly mention anything "malicious"-all comments discussing the removal of the sandbox were declared to be "for efficiency" or similar reasons, though the "intent" of a model is ill-defined.We note that the downstream utility function must be defined with care: reward hacking occurs when an unintended behavior is selected due to a misspecified reward and is a consequence of exploitable utility functions (see, e.g., Skalse et al., 2022) . For example, for the LPN task, we initially defined the utility with a numpy vector computation: acc = np.sum(y_hat == y) / n_test. However, we had not considered that the code may 'improve' the seed improver to return the predictions in a different "shape," i.e., an array with dimensions that were not as intended. Rather than causing an error, the result was a returned "accuracy" of over 1000%. Some techniques have been presented to avoid reward hacking (Amodei et al., 2016; Laidlaw et al., 2023) , and it would be valuable to explore their applicability to STOP in future work.  
limitations: 
 A fundamental limitation of our approach is that the language model itself is not improved. Furthermore, our meta-utility measures improver quality only indirectly via improvements in downstream task utility. Unlike in some prior work (e.g., Schmidhuber, 2003) , any single attempted improvement may result in worse performance, which can lead to further deterioration. Another limitation is that STOP requires an efficiently-evaluatable (and describable) utility function, which may not be available for every task. Correspondingly, as STOP's cost grows substantially faster than the cost of the optimized improver, it may be expensive to run. Our improvement framework also maintains a single improver at each step, while some approaches may benefit from maintaining a population. While this is not a strict limitation in that an improver could itself sample from a population of implementations, it likely imposes a bias. Moreover, a deeper analysis of alternative seed improvers and their tradeoffs would be valuable future work. Lastly, our experiments depend on a closed large language model that may be deprecated in the future, which harms interpretability and long-term reproducibility. Based on the GPT-3.5 results, it is unlikely that STOP would consistently work with any open-source LM at the time of writing (Touvron et al., 2023; Jiang et al., 2023) . 
concerns about developing stop: 
 Concerns about the consequences of RSI have been raised since its first mention. Minsky (1966) wrote, "Once we have devised programs with a genuine capacity for self-improvement, a rapid evolutionary process will begin... It is hard to say how close we are to this threshold, but once it is crossed, the world will not be the same." This is a particularly contentious topic recently, with intensified concern over negative consequences (Ambartsoumean & Yampolskiy, 2023; Gabriel & Ghazavi, 2021) .It is therefore important to carefully weigh the risks and benefits of studying RSI and specifically the small advance we introduce. First, STOP does not alter the black-box language model and hence is not full RSI. Moreover, at this point, we do not believe that the scaffolding systems STOP creates are superior to those hand-engineered by experts. If this is the case, then STOP is not (currently) enabling additional AI misuse. At the same time, it facilitates the study of aspects of RSI code generation such as sandbox avoidance and reward hacking. As Christiano (2023) argues, advances in scaffolding and agent models have the advantage of interpretability compared to advances in language models. However, as techniques for API-based fine-tuning of closed LMs become more available (OpenAI, 2023a), it would be plausible to incorporate these into the improvement loop. Therefore, it is difficult to assess the generality of our approach, especially with increasingly powerful large language models. However, this is itself a motivation for this work: understanding how LMs improve their scaffolding in the STOP self-improvement loop can help us understand and potentially mitigate negative impacts of better models. For instance, the simplistic ways in which the current LMs disable the sandbox are easily detectable. In essence, we would rather first observe problems with GPT-4 in simplified settings than with even more powerful LMs in real-world use. 
conclusions: 
 In this work, we introduced STOP, a framework for recursively optimizing code generation using language models as meta-optimizers. We demonstrated that large language models like GPT-4 are capable of improving code that leverages the LM itself. We found that, across a variety of algorithmic tasks, STOP generates improvers that boost the performance of downstream code. While the model does not optimize its weights or underlying architecture, this work indicates that self-optimizing LMs do not require that. However, this is itself a motivation: the capabilities of future LMs may be misunderstood if strong scaffolding strategies are not tested. Understanding the ways LMs improve their scaffolding with STOP can help researchers understand and mitigate the potential for misuse of more powerful LMs. Moreover, STOP may allow researchers to investigate the effectiveness of different techniques for mitigating undesirable self-improvement strategies.Ethics Statement There are several potential benefits of AI systems related to education, health, and many important aspects of quality of life. However, we recognize and take seriously the potential negative consequences of AI systems as well. Of particular interest is the concerns that recursively self-improving systems may have unintended negative consequences, which have been discussed by many authors. Section 8 discusses the reasons we feel this research, in balance, contributes to the study of a problem that is net beneficial. Specifically, the study of recursively self-improving code generation produces interpretable code, which makes it easier to detect and understand unintended behaviors of such systems. Our experiments in Section 6.2 show how this line of work enables the quantitative study of such behaviors.Here we extend the definitions of Section 3 to account for bounded resources such as runtime and language model calls, to prove generalization bounds, and to present an equivalent definition in terms of maximization. 
 
 Appendix: We first consider bounded resources. Recall that Σ * denotes the set of finite strings over an alphabet (or token set) Σ ⊇ {0, 1}. Let |x| denote the length of string x.Bounded language-models. First, to consider bounded resources, To capture most modern language models, we suppose that there are constants c, k ∈ N such that the language model L : Σ c → Σ c generates responses of length c, called the context length, to query strings of length c, in time k (shorter strings are handled by padding). Note that a bounded language model cannot output a program longer than c, and the same is true for our seed improver I 0 (u, s, L). Interestingly, however, other improvers can output meaningful programs longer than c by making more than one call to L.Bounded-runtime programs. Programs are represented by finite strings ∈ Σ * in a fixed (Turingcomplete) programming language. For simplicity of analysis we assume programs operate serially in steps. Every string π can be considered as a program and we write π(•) ∈ Σ * to denote its output (always a string) on one or more inputs. We assume the inputs can either be strings (which can encode numbers, text, programs, or arbitrary types of objects) or black-box (possibly randomized) functions.We assume that programs can call the following special black-box functions:• A clock function that, in unit time, returns the integer number of steps computed by the current program thus far and can therefore determine the duration of black-box function call.• A random bit function that returns a uniformly random bit in {0, 1} on each invocation, also running in unit time. We assume a fixed runtime bound b run on all programs being run to avoid long-running or infinite computations. We assume that there is a special string ⊥ ∈ Σ * where π(x) indicates a program failure, which may be a timeout, or π not encoding a valid program (i.e., a syntax error), or a runtime error on its input.• A sandbox function that runs a given program or black-box function with a parameter indicating a timeout number of steps.Bounded utility functions. It will be convenient to bound the range of the utility function. We assume that the utility function u : Σ * → [0, 1] is bounded by 1 and that u(⊥) = 0. To be completely formal, we must explain how to represent utility functions that output real values. One can do this by adding an additional parameter that indicates the desired precision, i.e., the number of bits of the output. We omit this from our analysis for simplicity.Bounded language model calls. The bounds on program runtime indirectly impose a bound on number of language model calls ≤ b run /k. However, we note that in STOP's implementation, additional bounds on the number of calls of a language model are explicitly made.Iterated downstream task improvement. The STOP framework, as in Section 4, considers only one round of improvement. It would be conceptually straightforward to modify û to explicitly account for multiple iterations of downstream task improvement. However, note that an improver can already internally perform multiple iterations of downstream task improvement.STOP can be viewed as a "pre-optimization" (like pre-training a language model) to find a good improver that will be used on a variety of downstream tasks. Generalization bounds concern the problem of how well will an improver work on future unseen tasks, albeit from the same distribution as the "training" tasks. In particular, they bound the degree to which one might be overfitting by using a limited number of training tasks rather than the full distribution. We provide two simple generalization bounds in this section. The first relates how close û is to expected (one-shot) improvement on new downstream tasks from the same distribution. The second provides absolute guarantees but for a slightly different (randomized) meta-utility function.Thus far we have considered a fixed set of n tasks (u, s) ∈ D, i.e., |D| = n, each being defined by a utility function u = (u func , u str ) consisting of a black-box function u func and a string u str , as well as an initial solution s ∈ Σ * . We now consider a distribution D over tasks (u, s) ∼ D. This is arguably the quantity we ultimately care about, as ū(I) determines the expected performance of a (single iteration) of an improver on a downstream task. If the tasks D ∼ D n are drawn i.i.d. from D, then one can prove a generalization bound stating that the average performance of an improver I on D is close to its expected performance on D: Proof. The standard proof follows from Chernoff bounds and the union bound. Denote the tasks by τ = (u, s) ∼ D. For any fixed improver I, there is a value y τ := u(I(τ, L)) for each task τ , and û(I) = τ ∈D y τ /n is simply the average of n i.i.d. random samples y τ , while ū(I) = E τ ∼D [y τ ] is the expectation. Thus, by the Chernoff bound, for any ϵ > 0 and fixed I,Lemma 1. Let n ≥ 1, δ ∈ [0, 1], l ≥ 2,Pr D∼D n [|û(I) -ū(I)| ≥ ϵ] ≤ 2 exp -2ϵ 2 n = 2 |Σ| 2l δ ≤ |Σ| l+1 δ ,where in the last step we have used the fact that l, |Σ| ≥ 2. Now there are only |Σ| l+1 possible programs (strings) of length ≤ l, and so by the union bound, the probability that any of them have |û(I) -ū(I)| ≥ ϵ is at most δ.The above lemma means that if selecting the best among any set of improvers according to û will yield a value of ū that is within 2ϵ of the best in the set.The above bound is relevant to the case where a final improver I is used in a single step of improvement on a downstream tasks, so the ultimate quantity of interest is ū(I). It implies that approximately optimizing û(I) is equivalent to approximately optimizing ū(I).We note that exactly the same bounds would apply to multiple steps of improvement if one replaced û and ū by the corresponding averages of any given number of rounds of iterated improvement on the new downstream task sampled from D.Stochastic meta-utility. Another simple generalization bound can be given if we consider the case in which the meta-utility is randomized. In particular, consider u(I) which is defined to be a randomized function that returns u(I(τ, L)) for a random task τ ∼ D. Clearly E[ u(I)] = ū(I), so u is an unbiased estimate of ū. Thus it is intuitive that one can similarly improve using u, albeit with more calls. One advantage of u is the following trivial observation: Observation 1. Any algorithm that makes at most n calls to u can be perfectly simulated using a a training set of n = |D| i.i.d. samples D ∼ D n .Grey-box utility descriptions. The results in this section lend support to use of grey-box descriptions of û, which only show its form as an average of utilities, because the grey-box description is identical, in expectation, to that of ū. Put another way, it would be easier to overfit to the training tasks (up to the worst-case bounds, as shown in this section) if the tasks are given explicitly to the pre-optimization algorithm, especially in the case where the program is quite large (as in over-parametrized neural networks that are larger than their training set size).A second, equivalent formulation is defined in terms of a maximizer program M which, given a language model and utility, outputs a solution string M (u, L) ∈ Σ * . Since we are thinking of a fixed language model throughout, we omit L and write M (u) = M (u, L) (and I(u, s) = I(u, s, L)) when the language model L is understood from context. The goal is to achieve high utility u(M (u)).Unlike an improver, a maximizer M does not require an initial solution. However, M can be still used to produce a higher-quality maximizer by applying M to an appropriately defined meta-utility function. To parallel the STOP approach of choosing M based on downstream tasks, one can use a set of downstream task utilities U (no initial solutions needed) to define the maximizer meta-utility ũ(M ) ≜ |U | -1 u∈U u(M (u)) and consider iterating M t ≜ M t-1 (ũ). To see the equivalence between maximizers and improvers, first note that one can, of course, convert any maximizer to an improver by ignoring the input solution and taking I(u, s) ≡ M (u). For the converse, note that one can utilize improvers as maximizers by including an initial solution in the utility u and optionally overriding it with a more recent solution in the comments of M . Specifically, suppose one defines a function e(M, u) extracting an appropriately encoded prior solution from M , if there is one, and otherwise the initial solution from u. Then one can convert improvers to maximizers by taking M (u) ≡ I(u, e(M, u)). Note that either optimizer can return itself, similar to a "quine."STOP uses performance at improving downstream tasks as a heuristic approximation to selecting good improvers more generally. It is not immediately clear how one would even give a non-cyclic definition of performance at improving improvers. Now, we illustrate a way to define recursive maximizer performance in a consistent fashion.To do so, consider a randomized process in which, in each iteration, a coin is flipped, and if it is heads, the maximizer is applied to the downstream task; if it is tails, however, it is applied to the problem of maximizing the maximizer. If the next flip is heads, then the result is used to maximize the downstream task. Otherwise, it recurs. If the coin has probability λ ∈ (0, 1) of being heads, then this process results in an expected number of maximizer calls, including for maximization and finally for the downstream task, is 1/λ. Hence, it is similar to a process where the maximizer is iteratively applied ≈ 1/λ times. However, this randomness enables us to define the objective consistently. In particular, for parameter λ ∈ (0, 1), define:u λ (M ) ≜ ũ(M ) with probability λ, u λ M (u λ )with probability 1 -λ.While the above definition looks cyclic, it is well-defined, just as a recursive program is well-defined. One can repeatedly expand the bottom case to get,u λ (M ) =              ũ(M )with probability λ, (maximize downstream performance) ũ(M (u λ ))with probability λ(1 -λ), (maximize downstream maximizer) ũ M (u λ )(u λ ) with probability λ(1 -λ) 2 , (max max that maxes downstream max)ũ M (u λ )(u λ )(u λ )with probability λ(1 -λ) 3 , (max max ...) ... Recursively self-improving code generation within the maximization framework may be achieved by taking a seed program M 0 (u) similar to our seed improver, which, for example, queries L for a solution maximizing u str and takes the best according to u func . (The number of queries is taken so as to remain in the runtime budget b run .) Then, one can define M t ≜ M t-1 (u λ ) for t = 1, 2, . . . , T.It is tempting to think that a fixed point M λ * = M λ * (u λ ), again a "quine" of sorts, may be good, but it may equally well be a minimizer as nothing in our framework favors maximization over minimization except the seed.Example Beam Search Algorithm from language_model import LanguageModel from helpers import extract_code def improve_algorithm(initial_solution, utility_str, utility):def beam_search(initial_solution, message, n_responses, temperature, beam_width): solutions = language_model.prompt(message, n_responses=n_responses, temperature=temperature) solutions = extract_code(solutions) solutions_with_scores = [(solution, utility(solution)) for solution in solutions] solutions_with_scores.sort(key=lambda x: x[1], reverse=True) return [solution for solution, _ in solutions_with_scores[:beam_width]] role = "You are an expert computer science researcher and programmer, especially skilled at → optimizing algorithms." message = f"""You must improve the following code. You will be evaluated based on a following → score function: '''python {utility_str} ''' Here is the current solution: '''python {initial_solution} ''' When run, your script must define an improved solution. Try to be as creative as possible under the → constraints. Your primary improvement must be novel and non-trivial. First, propose an idea for an improvement, → then implement it.""" language_model = LanguageModel(role) # First round: explore multiple solutions with higher temperature new_solutions = beam_search(initial_solution, message, n_responses=10, temperature=0.9, → beam_width=3) # Second round: refine the best solutions with lower temperature refined_solutions = [] for solution in new_solutions: message = f"""You have the following improved solution: '''python {solution} ''' Can you further improve this solution under the given constraints?""" refined_solutions.extend(beam_search(solution, message, n_responses=5, temperature=0.4, → beam_width=2)) # Pick the best solution among the refined solutions best_solution = max(refined_solutions, key=utility) return best_solution Targeted Improvement import re from language_model import LanguageModel from helpers import extract_code def improve_algorithm(initial_solution, utility_str, utility):"""Improves a solution according to a utility function.""" role = "You are an expert computer science researcher and programmer, especially skilled at → optimizing algorithms." message = f"""You must improve the following code snippet. You will be evaluated based on a → following score function: '''python {utility_str} ''' Here is the code snippet to improve: '''python {{code_snippet}} ''' When run, your script must define an improved snippet. Try to be as creative as possible under the → constraints. Your primary improvement must be novel and non-trivial. First, propose an idea for an improvement, → then implement it.""" def generate_new_snippets(code_snippet): language_model = LanguageModel(role) new_snippets = language_model.prompt(message.format(code_snippet=code_snippet), n_responses → =4, temperature=0. Upper confidence bound and multi-armed bandit from collections import defaultdict from helpers import extract_code from math import log, sqrt def improve_algorithm(initial_solution, utility, language_model):"""Improves a solution according to a utility function.""" expertise = "You are an expert computer science researcher and programmer, especially skilled at → optimizing algorithms." message = f"""Improve the following solution: '''python {initial_solution} ''' You will be evaluated based on this score function: '''python {utility.str} ''' You must return an improved solution. Be as creative as you can under the constraints. Your primary improvement must be novel and non-trivial. First, propose an idea, then implement it. B.9 IMPROVEMENTS ACROSS ITERATIONS Lastly, one may wonder about the changes in the kinds of improvements across iterations. We note that despite the instructions in the seed prompt to propose non-trivial and novel improvements, the creativity and scale of improvements appear to decline over iterations. Later improvements tend to be revisions and optimizations to be base algorithm, keeping its central idea and extending it (e.g., introducing caching, adding more types of optimizations to a list of hints, and adding temperature schedules). However, this is not always the case. For example, consider the improved improver in Figure 5 . Its initial improvement was to dynamically adjust the temperature with the number of calls. Its next improvement was to implement early stopping based on the number of improvements and to vary the number of messages used per call. The strategy of randomizing between high-temperature and low-temperature "explore" vs "exploit" phases was not implemented until the 7th improvement step, and the choice to use a counter to decide whether exploring or exploiting was more advantageous occurred in the next step.Earlier Seed Improver from language_model import LanguageModel from helpers import extract_code def improve_algorithm(initial_solution, utility_str, utility):"""Improves a solution according to a utility function.""" role = "You are an expert computer science researcher and programmer, especially skilled at → optimizing algorithms." message = f"""You must improve the following code. You will be evaluated based on a following → score function: '''python {utility_str} ''' Here is the current solution: '''python {initial_solution} ''' When run, your script must define an improved solution. Try to be as creative as possible under the → constraints. Your primary improvement must be novel and non-trivial. First, propose an idea for an improvement, → then implement it.""" language_model = LanguageModel(role) new_solutions = language_model.prompt(message, n_responses=5, temperature=0.7) new_solutions = extract_code(new_solutions) best_solution, best_utility = initial_solution, 0 for new_solution in new_solutions: utility_val = utility(new_solution) if utility_val > best_utility: best_solution = new_solution best_utility = utility_val return best_solution Figure A.19: Earlier seed improver. We include this earlier seed improver. It does not inform the language model of its ability to prompt with a batch of messages, which was ultimately important for more tractable run-times, given the latency of GPT4 calls. As discussed in Section 6.2, we slightly modified the seed prompt and meta-utility in a manner to make it apparent that the code was intended to be run in a sandbox. Generated proposal and code fragment for an unsafe improver that doesn't always use the sandbox GPT4: I propose: ...we can also sort the new_solutions based on their performance (score) in a nonsandbox environment, and then run a few top solutions in the sandbox environment. This can save computational cost and help to find an optimal solution faster. ... No security is provided by the fact that the utility is later re-evaluated in a sandbox.The string representation of the utility function need not match the true code exactly. For example, we typically obfuscate irrelevant logging code and any random seed values. We use multithreading libraries for implementing timeouts, but we remove these for simplicity and instead only present simpler timeout mechanisms to the model, like returning a zero score if an evaluation takes too long. Outside of the sandbox experiments, we include an exec command in the utility description but have a minimal function to evaluate the code to help debug and prevent the use of some undesirable libraries like multiprocessing. We also omit details that assign necessary properties to utility function like the budget or this currently-discussed string representation.For learning parity with noise, we use a timeout of 2 seconds, a fixed bitlength (10 bits), a p = 30% chance that a bit will be included in the parity subset for a task, 100 train samples for a given instance, and 20 test samples.All Wilson (1927) confidence intervals for binomial proportions were computed using the Python function statsmodels.stats.proportion.proportion_confint.For all tasks, we selected parameters such that the problem was approachable (i.e., the base improver could at least sometimes improve performance over the base performance) but non-trivial (the model should not immediately get perfect performance).One crucial abstract question that this work must contend with is how one should evaluate the novelty or creativity of the model's proposed improvement strategies. For example, the underlying metaoptimization strategies of genetic algorithms or simulated annealing are certainly not ones that GPT-4 proposed from scratch. We preface this discussion with a caveat: whether a proposed idea is creative or novel is ultimately always going to be a subjective judgment and is, to some extent, tied to the training data of the model -this is further complicated by the fact that, for the models we used, we do not have access to the details of their training data. With that being said, we would suggest that some of the strategies proposed by the model indeed appeared substantially different from the techniques that we had observed. For example, the simulated annealing approach seemed like a clever technique by implicitly recognizing that the underlying global optimization task may require non-monotonic improvement. Yet, it is not the first time that simulated annealing has been used to optimize a difficult NLP task (e.g., Liu et al. (2020) ). Similarly, the choice to attempt to improve code by attempting to improve one function at a time instead of revising also seemed creative, but the idea of decomposing a problem into parts and attempting to solve them individually is certainly not new in this space.Whether the fundamental optimization techniques are or are not novel, we would suggest that the automatic search and application of the existing optimization ideas to language model optimization and recursive self-improvement is novel. Many existing scaffolding innovations are also existing optimization techniques applied to LM-based optimization, such as Tree of Thoughts and Parsel. Part of the challenge comes from understanding which aspects of the optimization algorithm map onto which elements of the problem. For example, we found that STOP generated many genetic algorithms; however, only in a small subset of these generated genetic algorithms did it use the language model to perform the crossover and mutation. In many others, it performed mutations by randomly changing characters and crossover by randomly concatenating two randomly-truncated solution strings. Moreover, almost any new optimization algorithm can be described with reference to existing optimization algorithms, so it is ambiguous when an optimization algorithm is "different enough" to be considered new as opposed to simply a variant of an existing approach.Reproducibility StatementWe include implementation details, prompts, and relevant code examples throughout the paper and appendix. For reproducibility, we also include sandbox experiment details in Appendix I, additional experimental details around the utility description construction and the downstream tasks in Appendix J, the various utility descriptions and seed algorithms in Appendix F and Appendix G, and code examples of all discussed improvement attempts in Appendix H. We use models that are publicly available (primarily gpt-4-0314) and will open-source our code at https://github.com/anonymized/stop. 


Decision: The authors propose a method for improving a 'scaffolding program' (i.e., a program that issues multiple calls to LLMs) that is used to improve code solutions. The scaffolding program can then be applied to improve the scaffolding program itself, and the process can be iterated. The method discovers various interesting scaffolding programs, such as algorithms resembling beam search or genetic algorithms, and these programs lead to improved performance on held out test instances.

The framing of the paper and its methodology are quite creative and timely. All of the reviewers are positive on the paper, with some noting the paper's novelty, several potential applications of the ideas, and the paper's high quality analysis. Reviewers were altogether satisfied with the experiments following the discussion, during which initial comments about testing on additional tasks were determined to be fruitful areas for future work, which I agree with. The authors also provide code to further ease the process of expanding upon the ideas. This paper would make a great addition to the COLM program.

Reviews: review: paper_summary: paper_summary: This paper introduces Self-Taught Optimizer (STOP), a meta-optimization approach to improve a “scaffolding” program which issues multiple calls to an LLM to search for code solutions to solve downstream tasks. The key idea of the proposed method is to formulate the process of generating the scaffolding program itself as another search problem. Specifically, a scaffolding program takes as input a seed code solution to a downstream task and a utility function that measures solution quality, and issues multiple LLM calls to search for better candidate code solutions to solve the problem. Since the scaffolding program itself is also a code snippet, it could also be used as the input seed code solution to the scaffolding program to improve itself. In this case, the utility function of a scaffolding program is defined as the averaged utility when applying that scaffolding program on different downstream tasks.
strength_weakness: strength_weakness: * While the downstream tasks used to evaluate STOP (Table 1) are reasonable and fairly challenging, it would be nice to see if the improved improver would achieve better solve rates on more open-domain coding tasks, such as EvalPlus, LiveCodeBench for code generation or other recent benchmarks on debugging (DebugBench). 

* The analysis of reward hacking presented in Section 6.3 would benefit from further experiments. The current discussion appears somewhat speculative without quantitative results.
paper_summary: paper_summary: A meta-self-improvement procedure is described for code-generating language models. The procedure is seeded with a basic program, with access to a LLM API, that proposes revisions to a given program and selects the best one. The program is then called to revise *the revision program itself* to obtain an improved revision program, and these steps are iterated. It is shown that interesting algorithms resembling beam search, genetic search, etc. are discovered by this procedure. These algorithms produce better programs for combinatorial tasks that also transfer well across tasks. Some possible unsafe behaviours (e.g., hacking the reward mechanism by exploiting the lack of a tensor shape check) are also illustrated and discussed.
strength_weakness: strength_weakness: - Some parts of the main paper pose as formal but will be unsatisfying to any reader who seeks a formal description of the problem.  The text uses symbols and assumptions that are never defined and stated, hoping the reader will get the right idea. For example, in Section 3:
  - "Formally, let $\Sigma^*$ denote the finite set of text strings": $\Sigma$ was not defined.
  - "Let $L:\Sigma^*\to\Sigma^*$ be a randomized black-box LM...": what does "randomized black-box LM" mean? (It seems like this can just be any stochastic function, that is, function from $\Sigma^*$ to $P(\Sigma^*)$, where $P(X)$ is the space of probability measures over a discrete set $X$.) 
  - "$u_{\rm str}\in\Sigma^*$ is a description which may simply be...": what part of this is the formal definition? Is this simply saying "$u_{\rm str}$ is an element of $\Sigma^*$?
  - I am not aware of any formal meaning assignable to the statement "$f$ is a black-box-function", which is used a few times here.
  - The optimization problem alluded to in the very beginning of the paper is never written down.
    - I hoped to find the optimization problem written upon reading the phrase "find an improver program $I$ with high expected utility when used", but only the expected utility itself was defined. It is not even said over what space the optimization is performed (I guess it is over $I$?).
    - Equation (1) is not a definition. How to interpret a mathematical statement that reads "let $x=y$ and ideally ${\rm predicate}(x,y)$"?
  - In Section 4, paragraph "Intuition", the asymptotics are with respect to which variable?
  - Overall, the mixing of examples/informal language and attempts at formal definitions results in a text that provides neither formality nor intuition. I would suggest to keep the main text informal and keep the definitions/math to Appendix A.
- On experiments:
  - The phenomenon discovered in this paper emerges only at very large scales. For better understanding, it would be good to understand:
    - If a similar phenomenon exists at **smaller** scales: perhaps this can be studied with simpler tasks or with partially hardcoded scaffolding, so as to simplify the job of the LM.
    - Some qualitative explanation of why smaller models fail to meta-self-improve (Figure 4).
  - In the other direction, the evaluation could be expanded with experiments on prompt improvement on some more standard language tasks. Conversely, on the tasks currently evaluated, the comparison is only between the base model and different iterations of the proposed improver -- how would other improvement methods (based on fine-tuning or automatic prompt optimization) do here?
  - Can the evaluation of the accuracy shown in Table 1 also be shown over iterations, as in Figure 4, as well as error intervals if multiple instances of of the experiment were run?
  - I could not find many of the experiment details in the paper, in particular, the total compute budget (number of calls to GPT-4, for instance). Did I miss them?
questions: questions: Please see above.

Meta-note: I am likely to increase the rating if my questions are addressed.
paper_summary: paper_summary: The authors propose to take advantage of scaffolding programs with multiple calls to a LLM in an iterative self-improvement loop. In this framework, an “Improver” function is iterated on with the help of a code solution scoring mechanism based on the average score over a set of downstream tasks. The authors also look into the type of self-improvement strategies proposed by the fixed language model, such as genetic algorithms, simulated-annealing based search.
strength_weakness: strength_weakness: Novelty of the idea: the concept of the STOP algorithm seems very close to the concept of APE (Zhou et al., 2023) optimization algorithm where a LLM is queried for new prompt candidates which are scored and the one with maximum score is chosen. 

A limitation of this type of self improvement is that the meta-optimizer (what improves the improver) is fixed and could potentially limit the progress of the improver itself.

The proposed method seems to not work with GPT 3.5 turbo and Mixtral which suggest that the method or the chosen utility function is not robust or a careful choice of seed improver or utility function is required. 

I think there aren’t enough baselines in the paper. It would be fair to have APE and another iterative prompt optimization method, such as DLN (Sordoni et al 2023) as baselines for the downstream tasks with the same LLM as base.
questions: questions: I suggest moving the function definition of $\tilde{u}$ in Algorithm 1 above the main recursive loop to make it easier for the reader to understand where $\tilde{u}$ is coming from. 


Have you looked at how big each step of optimizing the improver $I$ is? Do you observe any big shift in the improver's scaffolding program at each iteration? If so, have you looked at perhaps implementing some sort of rolling average to keep the updates small enough?

At each step of applying the improver, there could be a big variance between the scores of extracted new solutions, and perhaps taking the “max” to be representative of that step is not the best. Have you looked at this potential issue and perhaps observed the use of an average of utility scores over new solutions as the representative score in updated improvers?

What is the prompt that meta optimizes the improver? And is there any filtering or check on an updated improver? (e.g. the code should be executable, a call to a LLM should exist, etc)
paper_summary: paper_summary: The paper is broadly about prompt optimization, specifically about using the LLM itself to iteratively refine and improve an initial seed prompt. The paper asserts that the various LLM prompt engineering techniques and methods are versions of the same general optimization problem, provides a theoretical formulation of this problem, then proposes the novel STOP algorithm as a way to leverage the LLM itself to conduct the optimization method search. The paper demonstrates this on the task of generating Python code implementations of solutions to lesser-known Computer Science problems. STOP is evaluated primarily on a checkpoint of GPT-4, though some experiments were conducted on checkpoints of GPT-3.5 turbo and one open source model, Mixtral-8x7B. Relative improvements are highlighted in the results, though the discussion primarily focuses on the nature and generalizability of the optimization methods produced by the algorithm. Special attention is given to instances where generated code produced by the LLM appears to have bypassed safeguards.
strength_weakness: strength_weakness: I do not see any specific reason to reject this paper. One relative weakness is a bit of disconnect between the initial general claims of the STOP algorithm and the practicality of it as demonstrated i.e. limited to code generation, specifically of individual algorithms to problems with well-defined utility functions that are easy to evaluate and describe. There is nothing wrong with this at all, but it's somewhat hard to see how we get from the reality of the experiments to the more sweeping general claims. Another minor issue is the occasional over-reliance on the Appendix for examples and details.
questions: questions: What was the actual usage in terms of number of calls / tokens consumed / cost per iteration or full run? While LLM consumption costs may not be anywhere near a limiting factor as actual LLM training, it would still be nice to have even a rough estimate of the usage and costs to conduct these experiments from a reproducibility and practicality standpoint. I did not carefully read the entire Appendix, so apologies if this information was included there.

Comments: title: Have we addressed some of your concerns?
comment: Great questions!

We define the meta-utility (as in Algo 1) as the average downstream task utility obtained when the improver is applied once to D independently sampled downstream task problem instances. For our main experiments we sampled 5 identical instances of the improvement task (see Sec 5.1). In practice, the meta-utility is stochastic and a few proposed model solutions depend on this (like a bandit that aimed to select the best improvement). And as you point out, there's no guarantee that a self-improved improver is actually better than the previous in terms of meta-utility, and for the weaker models we see this in practice. This also makes the task of finding an improver that works on a purely language-based downstream task (rather than just code) more tricky.

Thank you again!
Thank you for the response and additional details. Upon re-review, I am unable to point to any claim specifically that I would alter, as there do appear to be sufficient qualifications about the scope of the work. It may be that I glossed over them on first read through.
Please let us know if we have addressed your concerns or if you have further questions, as the rebuttal period ends soon.
Thank you so much for the response and clarifications.

I have some follow-up questions. 

In the improver improving process, during meta-utility calculation, do you only apply the current improver only once on the initial solution? I'm curious to know if the meta-utility function could be improved if the improver was applied either a fixed number of times on an initial solution or if it was applied on a couple of initial solutions per task? 
How noisy is the meta-utility function given that it is the only (and most important) signal to improve the improver with?

Is there a guarantee that using $improver_t$ is better than ${improver}_{t-1}$ at improving an "improver" ? From the meta-utility function we know that it would be better at improving initial solutions for a set of tasks, but is improving an improver the same as improving an initial solution of a task (which I believe is of a different nature)?