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

Thank you for your insightful feedback and constructive points. We sincerely appreciate the care you put into this review.

The improver's signal for improvement is a real value, which is the aggregation of utilities of solutions to different problems… Different tasks have utilities with different values and scales.

Great point. We updated the paper so that all utilities are normalized to be on a $[0,1]$ scale (more generally one could use $[0,M]$). This is an issue faced by any performance benchmark that measures performance across diverse tasks.

Aggregating utilities ... may be an insufficient signal for improvement (just one number in each iteration and previous improver code).

Indeed, this is a fundamental challenge in all multi-task learning (i.e., task weighting). However, with some weak assumptions, and constraining the range of possible utilities between 0 and 1 (rather than all real numbers), we have updated the appendix with a discussion showing some theoretical bounds on the expected generalization if the tasks are independent samples from the task distribution.

Tasks may not be representative, and their selection is unclear.

We discuss our reasoning for selecting the tasks in their respective sections of “Experiments and Results.” We will clarify in the revision that we select less-well-known tasks for evaluation because for better-known tasks like efficient SAT solving, modern language models like GPT-4 have almost certainly trained on many implementations (for example, if you search for “SAT solver” on GitHub over 3000 SAT repositories are returned, but only 6 are returned for “parity with noise”) and hence are more likely to be overfit to them. It’s true that we don’t cover the full space of all challenging algorithmic problems, and additional tasks could improve the representativeness of our evaluation - we are happy to evaluate more transfer tasks if there are any particular ones you’d be interested in seeing.

It's unclear how the data and instances are selected. 3 and 4 together: how many tasks, data instances, and their types are required?

This is a great point and an important part of the experimental design. We’ve incorporated this into the paper in supplementary experiment details. In short, 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).

Figure 4a is missing iterations beyond T=4.

Due to the number of GPT-4 calls necessary per iteration (roughly three thousand calls per iteration per run), we only performed 4 iterations on the aggregated runs. We’ll highlight the significant cost of running this algorithm in limitations, and have added a discussion of budgets in the section where we introduce STOP, as well as a more formal discussion in the appendix. However, in the context of the framing of STOP as a pre-optimization technique, ultimately, we note that this may ultimately save compute.

It's unclear how much of the "improvement" is due to [improving] each selected task rather than generic recursive self-improvement… How does going wider (range of tasks and data) effect going deeper (iterations of recursive self improvement)?

Thank you for this critical question: if we view this from the perspective of trying to find the best possible solution for a particular downstream task, many of our decisions are likely inefficient. For many tasks, if we simply repurposed all of the language model and utility calls used in self-improvement, and instead generated more attempts at that particular problem, then the resulting solution would perform at least as well as one generated by a self-improved improver. Given this, we've extended the problem statement and added a discussion of STOP as a “pre-optimization” technique, and some corresponding generalization bounds in Appendix A.2. We also note that, quantitatively, our transfer results empirically suggest some generalization. Lastly, we’ve evaluated two additional baselines to contextualize the results, namely a chain-of-thought baseline, similar to the current seed improver but with only one attempted improvement, 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 CoT 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%.

How sensitive are the results to changes in the prompts?

Good point! Although we do touch on some specific considerations in the paragraphs labeled “Designing the seed improver” and “Describing the utility.” However, a systematic evaluation of prompt sensitivity is left to future work, and we have added a note about this in the limitations.

Will the link to the repo become available?

Yes, we will release the code publicly!

Thank you for your very detailed comments and suggestions. We feel that your feedback has been incredibly helpful in strengthening the rigor and clarity of our work. We've tried to address all of your comments and questions in the revised text, but please let us know if any of our responses are unclear or if you have any additional questions or concerns.

It is unclear what the connection between the input program (initial_solution) and the output program (best_solution) is. Is the seed program more helpful than compared to prompting the LLM for a program that maximizes some utility (possibly with example programs that demonstrate the task, similar to the few-shot setting for LLMs)? I understand that the goal here is to design a method that can recursively improve itself, but the significance of the results seem questionable to me if it is possible to attain the same results with a conceptually simple prompt.

Excellent points, and we strongly agree that this is a really important point to make clear! First, we’ve revised the problem statement a bit to emphasize the improver formulation and further highlight its equivalence to the maximization formulation in the Appendix subsection “Analysis of equivalent maximization formulation,” where we also discuss how one can think of maximization recursively. However, note that in practice, an initial solution provided to the improver may be unlikely for even a good maximizer to generate, allowing for what is essentially a “warm-start.” As a result, we do not see a maximizer as necessarily a simpler solution – with that being said however, we believe that better understanding the optimization dynamics of maximizers and understanding how these dynamics differ from those of improvers would be valuable future research.

The experimental results are limited to GPT-4 and GPT-3.5-turbo, which are both closed source and AFAIK can change over time. This means that the results will likely not be reproducible. I'd suggest running some additional experiments with open source models that offer the possibility of reproducing the results.

Thanks for pointing this out! The OpenAI API in fact offers timestamped models to facilitate reproducibility. We have added the following sentence to the first paragraph of the experiments section (Sec. 5): "Timestamped versions of the two models we utilize, gpt-4-0314 and gpt-3.5-turbo-0301, are available within the OpenAI API, to facilitate reproducibility." We have also added a sentence to our limitations section addressing this limitation. Regarding open-source models, given that best open-source models have coding performance at or below the level of GPT-3.5 on most benchmarks [1], it is unlikely that any of today's open source models will give improvements using STOP. We strongly suspect using these open-source models such as Mistral [2] would not result in improvement – however, if you believe that it would strengthen the results of this paper, we would be happy to run it.

The experiments are restricted to simple problem settings (albeit hard optimization problems) like LPN, 3SAT, or Maxcut… I would suggest to tone down the writing, especially in the introduction, as it currently to suggest a level of generality that is not support by experiments.

Thank you again for this excellent suggestion. We agree and have made several changes throughout the introduction to emphasize the more constrained scope of the approach in the paper. Here are some of the changes we’ve made to the introduction:

1. Added "within a defined scope" to the 2nd paragraph
2. "demonstrate improvement" => "indicate potential improvements … within the specific contexts of our experiments."
3. "The broader concept of RSI dates back at least half a century, formalized by [Good, 1996] and later by [Schmidhuber, 2003], but our work represents a more modest and specific application of these ideas."
4. Contribution (b) "demonstrating that this system…" => "(b) providing a case study where a system”
5. "Further explorations in \cref{sec:circumvent} measure the rate at which the model attempts to disable a sandbox flag, providing early but intriguing findings in this area."

Thanks for the clarifications. The responses have addressed most of my concerns. Given the extensive analysis and that the topic is both interesting and relevant, I revise my initial negative stance to a weak accept. The main concern that remains is that the proposed algorithm is only shown to work with GPT-4 for which we do not know how it was trained. Thus, the results presented here might not generally apply to other LLMs (even ones with similar scale or capability), and for example require specific pre-training data or training techniques.

Thank you for your suggestions and encouraging comments!

missing comparison with two types of baselines, the one is human designed prompt structure such as Chain-of-Though, and Program of Thoughts. which one is better, the prompt structure found in their meta-learning paradigm or these human crafted ones?

Great suggestions! First, we’d like to note that our current seed improver can be thought of as leveraging chain-of-thought prompting, since our prompt requests that the model first proposes an idea for an improvement before implementing the change to the code. However, we think that a purer chain-of-thoughts baseline, which simply attempts to improve the code once without calling the utility function, is a useful addition, so we’ve run this to help contextualize the results. In addition, as another reference, we’ve added a simple greedy iterative prompting baseline (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% if we include errors), while the greedy iterative improver scores 64.2%±0.9%. These baselines help provide a scale by which we can understand the magnitude of the improvements.

My question is given a downstream task, if STOP can find better meta-heuristics than the common ones? … is there any creativity in the meta-heuristics found by the language model? such as the combination of genetic algorithm and beam search? It should be of great interest to the community if the language model can find the new or more task-specific meta-heuristics, which brings better performance than human crafting.

We’ll preface this response 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 felt that some of the strategies proposed by the model indeed appeared creative and 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. At the same time, it is not the first time that simulated annealing has been used to optimize a difficult NLP task (e.g., [1]). 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. However, we believe that this is an extremely important discussion to have in the paper which is currently missing. We have added Appendix K (“On the Novelty of Improvements”) to incorporate this discussion.

[1] “Unsupervised Paraphrasing by Simulated Annealing” Liu et al., 2019

Thank you for your encouraging feedback and useful questions!

The base LLM has a huge importance on STOP's performance (Section 5.3)

Thank you for raising this great point! On one hand, this is not particularly surprising given the consistent advantage that GPT-4 has over other models in prior work [1] and is in line with prior results about emergent properties from scaling [2]. With that said, the fact that these results currently require a large closed language model is indeed a limitation worth highlighting - we have added this to the limitations section. We have also extended Section 5.3 with a more detailed figure.

[1] “GPT-4 Technical Report” OpenAI 2023
[2] “Emergent Abilities of Large Language Models” Wei et al. 2022

Do the authors have thoughts how their proposed solutions can be used in meta-learning applications where the utility function may not be describle in natural language?

This is also a great question. Although we primarily use utility functions described in code and qualitatively find that these are preferable to those in pure natural language, recent work [3] indicates that for certain classes of problems, having users describe their preferences is less effective than having the model simply query the user. Some utilities can also be described by example. Exploring the effectiveness of a method like STOP on this class of problems is a valuable direction for future research.

[3] “Eliciting Human Preferences with Language Models” Li et al 2023

Thank you for the very helpful and constructive comments!

My main concern about this work is missing some of the important results for us to understand how well the proposed method works… Quantitatively, the differences between the results with GPT-4 and GPT-3.5… Are there any baseline methods (even heuristics) that you can compare the proposed method to?

Thank you for the suggestions! We have now added a new chart to help visualize the quantitative performance differences between GPT-4 and GPT-3.5 in Figure 4. We’ve also evaluated two additional baselines to help contextualize the results, namely a chain-of-thought baseline which is similar to the current seed improver but with only one attempted improvement, 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% if we include errors), while the greedy iterative improver scores 64.2%±0.9%. We’ve added this detail to the paper.

The writing of the paper could be improved… (e.g., all those "one can/may ...")

Thank you for this recommendation. We agree completely, and in the updated pdf have removed the references to alternative but ultimately unused design choices or, where appropriate, replaced them with their corresponding implications. For example, when we discuss the maximizer formulation, we now point to its useful theoretical implications in the appendix.

I am not entirely convinced about the "novelty" of the improver program generated by GPT-4… the ideas behind those improver programs (e.g., beam search, genetic algorithm, etc) are not new at all.

While the fundamental optimization techniques may or may not be novel, 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. However, we believe that this is an extremely important discussion to have in the paper which is currently missing. We have added Appendix K (“On the Novelty of Improvements”) to incorporate this discussion.

A couple of more related works for (self-)improving code generation with LLMs could have been mentioned

Thank you! We have discussed these references in the revision.

Is the Maximizer formulation used in the final proposed pipeline? If so, is the notation consistent with the M used in section 5.1?

Great point, thank you! In our revision, we have added a new more-theoretical section to the Appendix that uses the maximizer formulation. We have clarified in the revision (Appendix subsection “Analysis of equivalent maximization formulation,” paragraph 2) the equivalence of the maximizer formulation with the improver formulation, and show how it is useful for our extended theoretical analysis throughout the Appendix section “Theoretical Analysis.”

Can you comment on how difficult is it for the model to generalize to the improver solutions, given that it must have seen things like beam search, genetic algorithms, etc during training?

In practice, while the underlying algorithms are often things that the model has seen, many scaffolds that use well-known meta-optimization algorithms for language model solution optimization have been broadly adopted as non-trivial generalizations (for example, the now-widely-referenced “tree of thoughts” paper). We also add a theoretical discussion to elaborate on when we expect this to approach the true optimal meta-utility.

As the discussion period wraps up, we wanted to take this chance to highlight the main points raised and how we addressed them:

1. Baselines and curves. We responded to comments about additional hand-crafted baselines by introducing more baselines and ablations (443q, X5AY, VZPP, UnQ9), including a chain-of-thought-inspired baseline. We also added a new evaluation of GPT-3.5 performance across iterations.
2. Creativity of GPT-4. We addressed questions about the creativity of GPT-4's improvements (443q, X5AY, VZPP) with examples and a discussion of novelty in a new Appendix K (“On the Novelty of Improvements”).
3. Generalization and theory. To questions about the generalization properties of STOP and the value of the alternative maximizer formulation (443q, UnQ9), we added Appendix A ("Theoretical Analysis").
4. Additional limitations. We extended our limitations section, e.g., the dependence on the base model and the high cost of GPT-4 (yFD6, VZPP, UnQ9). Lastly, we revised the writing to clarify the constrained experimental scope (VZPP).

We again thank the reviewers for their comments and suggestions and hope we addressed them in our responses and revisions. If there are any remaining questions (or if they've all been resolved), please let us know – we are more than happy to clarify.