Searching for Optimal Solutions with LLMs via Bayesian Optimization

The innovation is questionable. Bayesian optimization has proven its utility and been extensively explored due to its strong performance and wide applicability. If this paper simply applies LLMs to the BO framework in the context of two specific tasks, the novelty is doubtful. There are already numerous search algorithms combining LLMs with BO. The experiments are insufficient. The experiments only compare BOPRO with three basic search strategies: greedy, repeated sampling, and random. These methods are too simple to demonstrate the superiority of BOPRO. The author should include current state-of-the-art methods, such as those mentioned in [1-4], and conduct more comprehensive experiments with different background.

Thank you for pointing out these issues. First, we have added the following additional experiments to address your concerns:

• A new multi-objective task of molecule optimization to synthesize molecules with high QED and low Vina scores for 58 protein binding sites (please see Section 7.2).
• A comparison with InstructZero (mentioned in [3]) on Semantle, which shows that InstructZero is only able to achieve 8% optimization accuracy, as compared to 66.67% achieved by the lowest-performing BOPRO variant (please see Table 1).

Additionally, we clarify that:

• Our primary baseline, earlier labeled “Greedy”, is in fact OPRO, which is referenced in [2]. We have updated the label on this baseline throughout the paper for clarity.
• Our experiments with LMX and BLMX on 1D-ARC (please see Appendix A.5.2) are representative of the evolutionary algorithm strategy described in [1].
• Finally we argue that the setting in [4] is artificial/easier than our setting as it performs BO over a fixed set of pre-generated candidates whereas in our setting, we generate new candidates, balancing exploration-exploitation based on the evolving uncertainty estimates of the solution space.

Below, we also provide a summary of our new results:
On Semantle (Section 7.1), we show that all BOPRO variants outperform OPRO by ≥10 points, whereas OPRO shows initial rapid gains but plateaus, getting stuck in a local optima. On the new task of molecule optimization (Section 7.2), we show that BOPRO produces better quality molecules that optimize both objectives (unlike OPRO) and 17% more valid proposals than OPRO, which tends to produce increasingly longer sequences causing the black-box function to fail. OPRO, thus, only finishes optimization for 12 of the 58 protein targets we evaluate on, whereas all BOPRO variants complete 100% of the tasks in the same wall-clock time.

The claimed generality is not well demonstrated. The abstract states that a key issue in this field is the lack of "a one-size-fits-all approach" (line 14), and the introduction provides several examples that highlight the importance of a general search strategy. I initially believed that generality would be a major highlight of the proposed algorithm. However, it is disappointing to see that the experiments were conducted on only "two representative language search tasks" (line 110), which clearly does not showcase BOPRO as a general method. As shown in Appendix A.6, the prompts are specifically tailored to the given tasks and are not generalizable.

We clarify that the lack of generality we highlight in current systems is in the search strategy they employ, more specifically - their inability to dynamically determine when to explore and when to exploit, which requires systems to pre-define a strategy using heuristics. In contrast, we have shown that BOPRO, through Bayesian optimization, can dynamically update its behavior during search based on its evolving beliefs about the solution space as more evidence is collected.

In terms of generality with respect to tasks, our experiments show that BOPRO is a strong method as long as the solution can be represented as a sequence of tokens and there is access to a good solution embedding function. To show this, we have added additional experiments (Section 7.2) on a new task of molecule optimization, and find that BOPRO outperforms the baselines. Thank you for pointing this out!

Indeed, the instruction prompts that we use for different tasks are different and simply specify the task description to the LLM. Our contribution is not in the specific instruction prompts used, but in the search framework that combines latent-space BO with LLM-based decoding, which remains constant across tasks.

The results are essentially negative (i.e., BOPRO is beaten by the greedy baseline and/or repeated sampling), which must be considered a weakness.

Please see our new results for Semantle (Section 7.1), where we show that all BOPRO variants outperform OPRO by ≥10 points, whereas OPRO shows initial rapid gains but plateaus, getting stuck in a local optima. We have also added a new task of molecule optimization (Section 7.2), where we show that BOPRO produces better quality molecules that optimize both objectives (unlike OPRO) and 17% more valid proposals than OPRO, which tends to produce increasingly longer sequences causing the black-box function to fail. OPRO, thus, only finishes optimization for 12 of the 58 protein targets we evaluate on, whereas all BOPRO variants complete 100% of the tasks. Our new experimental setting runs BOPRO without dimensionality reduction and, in Semantle, for double the number of iterations as before. Our method does still trail OPRO on program search (Section 7.3), and we present a detailed analysis of this failure case in Section 8. First (Section 8.1), we show that BOPRO indeed is able to balance exploration and exploitation through both quantitative and qualitative analyses. Then (Section 8.2), we show that the issue lies in off-the-shelf code representations being unable to distinguish between sequences with low edit-distances. This is an important limitation in current code embedding models, which would be useful to address in future work.

There seem to be a number of heuristics that were used. For example normalizing scores between 0.1 and 0.8, and the use PCA for dimensionality reduction (over other methods). It is stated that these improved performance. Was the performance improvement large? Is it expected that this will hold for other search tasks, or will these heuristics need to be adjusted in general?

Thank you for this question. Our new experimental setting addresses both of these concerns. First, we removed dimensionality reduction altogether, thus, reducing one additional choice a practitioner needs to make. This has also resulted in a significant boost for BOPRO, e.g., showing 10 percentage point gains over OPRO on Semantle. Our earlier setting of using PCA was informed by prior work and some initial results, which, in hindsight, we should have expanded to come to a final decision. Second, our new setting also removes scores from the prompt, which we found provide modest gains for all the methods (BOPRO and baselines), presumably because of the LLM’s inability to accurately interpret numbers associated with the solutions, indicating that the ordering of the examples is more important than their actual scores. We have, therefore, removed both considerations, simplifying the design of the method.

I wonder if the authors could explain the importance/significance of separating the solved from the unsolved cases in the various figures.

Our new revision keeps only one example of the search trajectory comparison between BOPRO and OPRO, which shows how the ability to balance exploration and exploitation in BOPRO allows it to solve the task (Fig. 5(c)) whereas OPRO gets stuck in a local optima and fails to solve the task (Fig. 5(d)). We also note that this behavior can be quantitatively observed in our Semantle experiments (Fig. 2(a)), where OPRO shows rapid initial gains and then plateaus, whereas BOPRO shows steady gains and achieves the best performance. The additional comparisons we showed in our previous revision, simply showed additional examples of the same behavior as well as a contrasting case where a task was successfully solved by OPRO’s greedy strategy.

Figure 2: It would be easier to read the plots if they indicated somehow which lines were the three BOPRO variants (e.g., with different line styles and/or legend labels) and which were the baselines.

Thank you for pointing this out! We have updated all our figures to clearly prefix all BOPRO methods with “BOPRO-”. Please let us know if this clears the confusion.

I think the related work would be nice to see earlier in the paper, particularly the part about other ways that Bayesian Optimization and LLMs have been combined.

This is a great suggestion. We have made the change in the new revision!

Some minor issues not affecting my recommendation: Line 120 and elsewhere: "For e.g.," this reads as too informal. Use "For example,". Figure 3 caption: There is maybe a word missing? "... random sampling with low due to ..." Section 7.2 Heading and elsewhere: "v/s" -> "vs."

Thank you! We have addressed these typos in the new revision.

The experimental tasks in this works look easy and insufficient, which could not be enough for examine the performance.

To address your concern, we have added a new experimental setting of molecule optimization (Section 7.2) where the goal is to synthesize molecules with both high QED (druglikeness) scores and high binding affinity (low Vina scores). Our results show that BOPRO produces better quality molecules that optimize both objectives (unlike OPRO) and 17% more valid proposals than OPRO. OPRO further tends to produce increasingly longer sequences causing the black-box function to fail, resulting in finishing optimization for only 12 of the 58 protein targets we evaluate, whereas all BOPRO variants complete 100% of the tasks.

Additionally, we note that our synthetic task of Semantle, albeit conceptually simple, represents a challenging test bed (also hosted as a popular online word game by the New York Times). The low scores with repeated sampling using LLMs as well as the fact that none of the compared methods perfectly solve the task underscores that this problem is non-trivial to solve.

Lastly, our experimental setting for hypothesis+program search using 1D-ARC, as well as its original task ARC, is widely recognized as being challenging, which is evidenced by the low scores achieved by prior work (e.g., GPT-4 direct prompting achieves only 41.5% on the full 1D-ARC dataset [1]). Furthermore, we construct from the full dataset a hard subset of tasks that cannot be trivially solved by repeated temperature-based sampling in 100 iterations, resulting in our final test bed.

[1] LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations (Xu et al., 2024)

The performance of this method is not good in the main experiment, as shown in Figure 2. Although the authors argue that this method could have stronger exploring capability and adaptability to different tasks, this kind of advantage isn't verified by the final performance which we should pay more attention to.

Please see our new results for Semantle (Section 7.1), where we show that all BOPRO variants outperform OPRO by ≥10 points, whereas OPRO shows initial rapid gains but plateaus, getting stuck in a local optima. We have also added a new task of molecule optimization (Section 7.2), where we show that BOPRO produces better quality molecules that optimize both objectives (unlike OPRO) and 17% more valid proposals than OPRO, which tends to produce increasingly longer sequences causing the black-box function to fail. OPRO, thus, only finishes optimization for 12 of the 58 protein targets we evaluate on, whereas all BOPRO variants complete 100% of the tasks. Our new experimental setting runs BOPRO without dimensionality reduction and, in Semantle, for double the number of iterations as before. Our method does still trail OPRO on program search (Section 7.3), and we present a detailed analysis of this failure case in Section 8. First (Section 8.1), we show that BOPRO indeed is able to balance exploration and exploitation through both quantitative and qualitative analyses. Then (Section 8.2), we show that the issue lies in off-the-shelf code representations being unable to distinguish between sequences with low edit-distances. This is an important limitation in current code embedding models, which would be useful to address in future work.

The authors mentioned in the Section 6 that " However, we find that our baseline of repeated sampling (RS) using a weaker Mistral-Large-2407 model is able to trivially surpass that score with an accuracy of 81.48%". I don't really get this statement, could the author please provide more detailed information of this? Using weaker model with less generations surpass the stronger model with more genrations go against my instincts.

Wang et al. [1], which is the work that we cite in Section 7.3, report achieving a test set accuracy of 73.1% on their provided subset. However, they do not compare to a simple repeated-sampling baseline as we have done. We conducted that experiment and found that even with a weaker model (Mistral-Large, not GPT-4), repeated sampling outperforms the technique used in Wang et al., which (a) suggests that their method may not be performing significant amounts of search, and (b) suggests that their chosen subset of questions may be an insufficient test bed for search. This is what motivated us to create a new hard subset of 1D-ARC composed of problems that were not solved in even 100 repeated samples with Mistral-Large. Note also that prior works have also found repeated sampling to be a strong method for code generation [2], therefore, the experimental setting in [1] should have included this important evaluation for completeness.

[1] Hypothesis search: Inductive reasoning with language models. (Wang et al., 2023)
[2] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling (Brown et al., 2024)

I am wondering if the choice of other dimensionality reduction technique can help improve the performance of BOPRO?
BOPRO might not be ready for practical use yet as it still consistently trails behind the greedy baseline.

Your intuition is precisely correct! Our analysis revealed that dimensionality reduction of embeddings was indeed a key reason for not seeing the expected results from BOPRO. Our new experiments, particularly on Semantle (Section 7.1), show that using the unreduced embeddings with BOPRO results in a significant improvement in performance, with BOPRO now outperforming all the baselines, including OPRO by ≥10 percentage points, whereas OPRO shows initial rapid gains but plateaus, getting stuck in a local optima (see Fig. 2(a)). This result is also interesting in the fact that we show that it is indeed possible to use Gaussian processes with very high dimensionality, contrary to a popularly-held belief from prior work and in the community. We have also added a new task of molecule optimization (Section 7.2), where we show that BOPRO produces better quality molecules that optimize both objectives (unlike OPRO) and 17% more valid proposals than OPRO, which tends to produce increasingly longer sequences causing the black-box function to fail. OPRO, thus, only finishes optimization for 12 of the 58 protein targets we evaluate on, whereas all BOPRO variants complete 100% of the tasks. Our method does still trail OPRO on program search (Section 7.3), and we present a detailed analysis of this failure case in Section 8, where we find that it is not because of an inability of BOPRO to balance exploration and exploitation (Section 8.1), but rather in the inability of off-the-shelf code embeddings in distinguishing between candidate code solutions with very low edit-distances (Section 8.2).

How does the number of warm-start prompts W influence the final performance of the model? Is there a specific range of W that balances exploration and exploitation effectively?

Thank you for your thoughtful question! While a larger W allows for the initialization of the surrogate model with more accurate beliefs about the search space, the trade-off when generating warm-start examples (instead of selecting from a known set) is in the allocation of test-time compute in this initial sampling v/s using the budget to perform search. The answer to the optimal number of examples is, thus, closely tied to the task and the ability of a warmstart generator (e.g., repeated sampling with an LLM) to produce diverse samples. To show this, we have conducted an experiment on Semantle for 25 problem instances for 5 warmstart settings: W={2, 5, 10, 20 (original setting), 40}. Our results are shown in Appendix A.5.5, where we find that performance initially increases with increase in the number of warm-start examples until W=20, after which it dips a little. This is in-line with our described intuition above.

In row 248, how do the authors sample a batch of candidates for each z’t+1? Could alternative sampling methods impact the diversity and quality of solutions generated?

Our procedure to sample candidate solutions given a BO proposal forms the second component of BOPRO, which we describe in Section 5.2 Latent-to-Text Decoding. In particular, given the BO proposal z’, we first select the most similar previously observed solutions using the cosine similarity between the embeddings of previous solutions and the BO proposal. We then order the selected observations in ascending order of similarity to construct the prompt (“search prompt”) that is input to an LLM. We then use temperature-based sampling to generate a batch of solutions with this search prompt. We believe that alternative sampling methods, such as greedy decoding or beam search, would be less suited to our method, given that our goal is not to sample one high-likelihood sequence, but to sample a batch of sequences from a target region in the search space, where temperature-based sampling can produce similar but distinct results.

BOPRO is not able to balance exploration and exploitation and might not be ready for practical use of the reasoning in the LLMs.

In Section 8.1, we show evidence that BOPRO indeed is able to balance exploration and exploitation. Specifically, in Fig. 5(a,b), we show that even when starting with low warm-start scores, BOPRO is able to balance exploration and exploitation and achieve higher optimization accuracy than OPRO, which takes a greedy approach. Further, in Fig. 5(c,d), we show visually the search trajectories followed by BOPRO and OPRO. While OPRO gets stuck in a local optima and fails to solve the problem, BOPRO shows the ability to explore the search space and zero-in on the right solution.