Searching for Optimal Solutions with LLMs via Bayesian Optimization
Authors: Dhruv Agarwal
Manoj Ghuhan Arivazhagan
Rajarshi Das
Sandesh Swamy
Sopan Khosla
Rashmi Gangadharaiah
Venue: ICLR 2025 Poster (2025)
Keywords: search
optimization
LLMs
test-time steering
bayesian optimization
reasoning
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We present Bayesian-OPRO (BOPRO), a method for generating optimal solutions with LLMs via Bayesian optimization that explores and exploits the search space based on evolving uncertainty estimates of the solution space as search progresses.

Abstract: Scaling test-time compute to search for optimal solutions is an important step towards building generally-capable language models that can reason. Recent work, however, shows that tasks of varying complexity require distinct search strategies to solve optimally, thus making it challenging to design a one-size-fits-all approach. Prior solutions either attempt to predict task difficulty to select the optimal search strategy, often infeasible in practice, or use a static, pre-defined strategy, e.g., repeated parallel sampling or greedy sequential search, which is sub-optimal. In this work, we argue for an alternative view using the probabilistic framework of Bayesian optimization (BO), where the search strategy is adapted dynamically based on the evolving uncertainty estimates of solutions as search progresses. To this end, we introduce Bayesian-OPRO (BOPRO)––a generalization of a recent method for in-context optimization, which iteratively samples from new proposal distributions by modifying the prompt to the LLM with a subset of its previous generations selected to explore or exploit different parts of the search space. We evaluate our method on word search, molecule optimization, and a joint hypothesis+program search task using a 1-D version of the challenging Abstraction and Reasoning Corpus (1D-ARC). Our results show that BOPRO outperforms all baselines in word search (≥10 points) and molecule optimization (higher quality and 17% fewer invalid molecules), but trails a best-k prompting strategy in program search. Our analysis reveals that despite the ability to balance exploration and exploitation using BOPRO, failure is likely due to the inability of code representation models in distinguishing sequences with low edit-distances.

Published as a conference paper at ICLR 2025
SEARCHING FOR OPTIMAL SOLUTIONS WITH LLMS VIA BAYESIAN OPTIMIZATION
Dhruv Agarwal 1 Manoj Ghuhan Arivazhagan 2:1, RRjarshi Das Sandesh Swamy?, Sopan Khosla Rashmi Gangadharaiah? 'University of Massachusetts Amherst, "AWS AI Labs, MMeta Al dagarwale es. umass edu, fmghuhan, sanswamy, rgangad) amazon. com, frajarshi, sopan) @meta. com
sopan)emeta.
ABSTRACT
Scaling test-time compute to search for optimal solutions is an important step to- wards building generally-capable language models that can reason. Recent work, however, shows that tasks of varying complexity require distinct search strate- gies solve optimally, thus making it challenging to design a one-size-fits-all approach. Prior solutions either attempt to predict task difficulty to select the optimal search strategy, often infeasible in practice, or strategy. e.g., repeated parallel sampling or greedy sequential search, which is sub-optimal. In this work, we argue for an alternative view using the probabilistic framework of Bayesian optimization (BO), where the search strategy is adapted dynamically based on the evolving uncertainty estimates of solutions as search progresses. To this end, we introduce Bayesian-OPRO (BOPRO) generaliza- tion of a recent method for in-context optimization, which iteratively samples from new proposal distributions by modifying the prompt to the LLM with subset of its previous generations selected to explore or exploit different parts of the search space. We evaluate our method on word search, molecule optimization, and joint hypothesis+progran search task using a 1-D version of the challenging Abstrac- tion and Reasoning Corpus (ID-ARC). Our results show that BOPRÓ outperforms all baselines in word search (210 points) and molecule optimization (higher qual- ity and 17% fewer invalid molecules), but trails best-k prompting strategy program search. Our analysis reveals that despite the ability to balance explo- ration and exploitation using BOPRO, failure is likely due to the inability of code representation models in distinguishing sequences with low edit-distances.
static, pre-defined
INTRODUCTION
Decision- under uncertainty is a hallmark of intelligent behavior (Kochenderfer 2015 Peter-
son 2017), with uncertainty arising from incomplete task information (e.g., unknown constraints and preferences) (Bazerman) 2012). limited inaccessible data due challenging or costly collection processes (e.g., efficacy of a drug design, feedback from human users) (Benary et al., (2023), or vast solution spaces that are difficult model comprehensively (e.g., scientific hypotheses) (Schneider) 2018 Majumder et al., 2024 2025). Such settings, thus, require searching for optimal solutions iteratively estimating the quality of plausible solutions conditioned on limited available evidence and prior beliefs to propose a candidate that is either similar to previous observation known to be high-performing or provide new information for future decision-making, commonly referred to as the opploration-exploitatioo tradeoff (Cohen et al. 2007). Specifically, we are interested in answer- ing whether a search method with large language models (LLMs) can be designed to handle this trade-off automatically!"
Recent work (Krishnamurthy et al. 2024) suggests that models are good at exploiting known so- lutions (finding local optima) but struggle to sufficiently explore the search space (finding global optima), thus, curtailing their application in real-world search tasks. Recent attempts to address this
Work done during an internship at Amazon. "Corresponingg authors. Work done at Amazon. Our code is available at: htttp:///ittubp com ama./n sci ence//OPRO- CC.R-022

---

Published as a conference paper at ICLR 2025
Optimal Solution
Z
Optimize Acquisition Pn
Retrieve &NNN Observations
arg max g
Dissimilor Observations
Gaussion Process (GP)
Latent BD Proposal
Similar Otnervations
Update Posterior
Construct Search Prompt
Description
Sample and Score Solutions
0252, 0.81, 0.79
f())
"Synthesize molecule with high QED and low scores bind PTPNT"
"cucexelelccgg4eccceerrr
LLM
<b-)
2t
3t
Figure 1: Overview of Bayesian-OPRO. In every iteration f. BOPRO starts by optimizing an ac- quisition function a to propose latent vector z Z, the embedding space of solution sequences. z represents a point in the search space considered promising to observe by the surrogate model. To sample one previous observations most similar to the BO proposal in the latent space, using them as in-context examples. The sampled solutions 24 are then scored using the black-box function f()) and mapped to Z using embedding function c(-), which are then together used to update the surrogate posterior.
solutions from 2/-. BOPRO constructs search prompt for LLM by retrieving
issue often involve constructing static meta- heut-shcsssstics to encourage exploratory behavior, such as with evolutionary algorithms (Lehman et al. 2023 Meyerson al. 2023 Poreees al., 2024). repeated sampling (Brown et 2024| Yang et al. 2024), or tuning parallel-to-sequente sampling ratios based on task difficulty (Snell al. 20024). Despite moderate success, these solu- tions are either too expensive, not performant enough, or require fixing a search strategy through offline evaluations. In this work, we explore an alternative direction and ask:
Can enable LLM-based search automatically adapt its strategy search progresses?
We answer in the affirmative and propose the use of Bayesian optimization (BO) (ushhner 1964 Frazier 2018). framework that builds surrogate an objective function using probabilistic model initialized with set of priors and initial samples, then generates a posterior predictive dis- tribution over candidate solutions by iteratively integrating new evidence. While there has been preliminary work in trying to combine LLMs with BO, prior works have either viewed the task as a selection problem from an existing pool candidates (Kristiadi et al. 2024 Opsahl-Ong et al.) 2024) relied on heuristics over samples from the LLM itself to build unprincipled uncertainty estimates (Liu et al., 2024).
We, therefore, propose Bayesian-OPee that leverages the evolving uncertainty in estimates of the solution space to generate promising solu- tions in each round of search to find the global optima. In each iteration, BOPRO uses latent-space BO to propose a latent target for the LLM, which used to sample solutions via a prompting strategy that builds upon recent in-context optimization method called OPRO (Yang et al. 2024). Specifically, we prompt the LLM with previously generated solutions that are most similar to the BO proposal vector order to bias its generation towards the BO-proposed region in the search space. We empirically validate our approach on three challenging language- based search tasks- word search, molecule optimization, and hypothesis+program search and find that BOPRO out- performs the baselines all tasks except program search. Notably on Semantle, while baselines plateau, likely getting stuck in local optima, BOPRO shows steady gains, pointing to its ability to adaptively explore and exploit the scarch space. We analyze the search behaviors of each method and demonstrate that BOPRO indeed shows the capacity to balance exploration and exploitation, which important for complex reasoning tasks. Despite this ability, find evidence to suggest that fail- ure on program search likely occurs due to an unavailability of fine- mraigid code representations that can distinguish between sequences with low edit-distances.
(BOPRO) novel method for integrating BO with LLMs
In summary, our contributions are: (1) we propose BOPRO ($)). a novel method for integrating BO with LLMMs that adapts the problem difficulty and evolving uncertainties search progresses. (2)
2

---

Published as a conference paper at ICLR 2025
We conduct thorough empirical evaluation ($6) three search tasks, validating the efficacy of
BOPRO in finding optimized solutions compared to several strong baselines ($7). (3) We highlight program synthesis as failure case for BOPRO and present detailed analyses that (a) clearly demon-
strate a strong exploration capability in BOPRO (18.1) and (b) reveal that the lack of fine-grained representations is likely the root cause of optimization failure (88.2).
SEARCH TASKS
We first describe three language-barn based search tasks that we experiment with in this work in order to provide grounding for subsequent sections.
2.1 SEMANTLE: WORD SEARCH
Semantle is a synthetic word-search task, where the goal is to find a held-out English word (e.g., "polyeshylene") ") with a limited number of guesses (budget) given only scalar feedback scores that describe the similarity of a guessed word to the held-out word. In particular, we use representations from the SimCSE (Gao et al., 202I) embedding model as the black-box scoring function. Each held-out word is also paired with an imitial warm-start set of words and scores (e.g.. "hope" (score: 0.29), "golfing" (score: 0.35), "serum" " (score: 0,51)), which together define problem instance.
2.2 DOCKSTRING: MOLECULE OPTIMIZATION
Dockstring (Garcóa-Ortegón al. 2022) provides benchmark of challenging molecule optimiza- tion tasks that are closely related to real problems in drug discovery. In this work, we focus on the multi-objective task of synthesizing drug molecule (using SMILES strings (Weininger 1988)
that jointly optimizes for both druglikeness, as measured by QED scores (Bickerton et al. 2012) and binding (or docking) affinity target protein site, measured by Vina scores (Trott & Olson, 2010). Following Yuksekgonul et al.] (2024), we synthesize new molecules for each protein target starting from basic chemical Tragments-benzent (clcccocl), pentane (CCCCC), and acetamide (CC (=0) N).
2.3 ID-ARC: HYPOTHIESIS+ SEARCH
The Abstraction and Reasoning Corpus (Chollet 2019) is a set of analogy puzzles in which solver must infer the common abstract rule underlying a small set 3-5 "train" grid transformations. and apply that rule to new "test" grid. In this work, we use 1-dimensional version of the dataset, 1D-ARC, introduced by Xu et al. (2024) We take an inductive hypothesis+program search view Wang al. 2024), wherein search performed over the space of natural-language algorithms tollowed by generating its implementation as python program. The goal for each problem instance is, therefore, find algorithm and its python implementation that can solve all the train examples, followed by single evaluation of the best found program on a test example to receive a score.
3 BACKGROUND: BAYESIAN OPTIMIZATION
Bayesian optimization (BO) is a framework for derivative-free, global optimization to find
arg max fz))
zEA
where f: RRd + Rº the black-box function to optimize, (often defined by box constraints) constrain search, d is the number of input dimensions to tune, is typically the number of scalar objectives used to evaluate f (we set o = throughout this work), and we allowed limited budget T of evaluations that can be made using the black-box function
a feasible set within the input space
2 IIsspired by the online word game the same name: https::://// / ee. com/
We use the ID version to remove the need for identifying non-sequential object cohesion in 2D grids, noted being challenging for both moderate-sized models and uni-modal text models (Xu et al. 2024.
3

---

Published as a conference paper at ICLR 2025
to get an observation of the objective at some point in the input space. The goal for BO is then to iteratively select a point for evaluation that is most likely to be x² based on the available evidence.
In typical BO implementation, we first initialize Bayesian statistical model, called surrogate, to model f with either user-defined priors about the objective function or with uninformed priors. Typical choices for the surrogate model include Gaussian processes (GPs) (Rasmussen & Williams, 2006) and Bayesian neural networks (BNNs) (Springenberg et al.) (016), which encode distributions over plausible realizations of the true black-box function. Once initialized, set of warm-start experiments are then conducted by taking random samples from the input space and observing their black-box values. These samples are used to compute the initial posterior predictive distribution f(z) f which, in the case of a GP, is normal distribution with mean (z(z) and variance (x) at each input x at time-step f. The final component is an acquisition function a Rd IR, which is function that balances exploration and exploitation by assigning a scalar value to each point in the input space denoting the utility of sampling that point based on the posterior predictive
at given time-step. At each step t, the next point is then sampled
Tt == arg (x, ( f(1==11)), zEA
which can be optimized using standard gradient-based methods. We then evaluate the black-box function at this new point to get f(xx) and update the posterior predictive. This loop is repeated until either the search budget exhausted or a solution with sufficient quality found, following which the best solution found thus far is returned.
RELATED WORK
Test-time compute with LLMs. Snell et al. (2024) provide a framework for categorizing different methods for scaling test-time compute into refining the proposal distribution and using verifiers to guide decoding, e.g. during beam search. BBrwnn et al. (024) present an analysis of the ability of repeated sampling to scale test-time compute and derive scaling laws for the same. Several other test-time search and optimization methods ( (Yang et al. 2024 Lehman et al. 2023) Meyerson
al. 2023] Coomera-Paredee et al. 2024, Wang et al. 2024) approach the problem assuming the availability of a known verifier, similar to our setting.
Bayesian optimization and LLMs. Some methods use the LLM itself to simulate each step of BO via repeated prompting to compute uncertainties over candidate solutions (Liu et al., 2024 Ramos et al. 2023). Other methods have used BO with LLMs to perform efficient selection
discrete solution set (Kristiadi et al., 2024] Opsahl-Ong et al. 2024). Chen et al. (2024) propose an approach to learn soft-prompts with BO starting with set of random vectors and show promising results on instruction induction. Finally, our work is also related to carlier works performing LSBO with autoencoders instead of LLMs (Gómez-Bombarell) al. 2018).
5 BAYESIAN-OPRO (BOPRO)
We now introduce BOPRO (Fig. method for LLM- search that can automatically adapt its strategy based on the evolving uncertainties about the search space using latent-space BO over textual embeddings of plausible solutions for given task. In each iteration with BOPRO, a surro- gate model builds a probabilistic estimate of task performance for unobserved regions of the search space using previous observations and proposes vector representing promising region to sample solutions from next. The proposal vector is used to build search prompt that is input to an LLM to sample new solution sequences. The generated solutions are then scored using the black-box func- tion for the task and added to the pool of observations to improve surrogate estimates in subsequent iterations. This process repeated until either the optimal solution is found or the search budget is exhausted, following which the best solution found thus far is returned
'Our focus is to evaluate search methods and, thus, we tasks with external verifiers to avoid confounding with noisy feedback. However, our method can easily be used with learned verifiers such reward models.
4

---

Published as a conference paper at ICLR 2025
We next describe each component of BOPRO categorized broadly into: (1) generating the latent- space proposal using BO, and (2) decoding the solution text from the latent proposal via prompting.
5.1 LATENT-SPACE BO
5.1.1 WARM-STARTING
To generate the initial warm-start set {<> ))= we prompt an LLM generate W unique solutions using a manually written task description (see Appendix [.6.1] We then compute the latent-space embedding for each generated solution using a representation function Φ(.). e.g., text embedding model, to get
6(x) IR. We then derive the initial posterior predictive
distribution conditioned on {(=0 [( (1 ;= Note that the goal at this stage is only to provide wide coverage of the solution space, and not maximize
5.1.2 GENERATING REPRESENTATIONS
Representation prompt. To generate useful representations for solution candidates, convert the raw text of a solution into desendennnentt prompt before passing it through 6(-). Eg.. in program search, the algorithm and code y may simply be represented "Algorithm: 25 Code: y" (see Appendix A.6.2).
Representation function. BOPRO relies on the availability of embedding function Φ(-) that capable of generating good representations
plausible solutions for the task. For example, in program search, embeddings must be able to distinguish between distinct algorithmic constructs. Additionally, since is widely reported that GPs struggle with large imput dimensions (Snoek et al,,
2012 Wang al. 2.13). we, optionally, include dimensionality reduction function (0()) to get (((())
E Rd where d' << d. Several choices exist for vb, including PCA, low-rank projection
Li et al., 2018 Aghajanyan et al. [021), and random projection (Wang et al. 2013). When no
dimensionality reduction is used, 1/ is simply set as the identity function
5.1.3 GENERATING LATENT-SPACE PROPOSALS
Surrogate model. BOPRO uses a probabilistic surrogate model estimate the uncertainty in the search space and efficiently update its beliefs about the goodness of different regions new solutions are observed. Throughout this work, we use a Gaussian process (GP) surrogate model with a Matérn kernel (Genton 200T) and priors manually-tuned by visually assessing the fit of the posterior distribution on a known set of solution-score pairs for each task on a randomly sampled problem instance (see Fig. 7b.
Acquisition function. As described in } given a posterior predictive distribution over the fea- sible search space, BO uses an acquisition function to estimate the value of observing each point. We optimize this acquisition function using multi-start projected gradient ascent to get a new pro- posal vector that represents a promising region of the search space to sample solutions from. We experiment with three common choices: log expected improvement (LogEl) (Ament et al. 2023). upper-confidence bound (UCB) (Auer 2002). and Thompson sampling (TS) Thompson (933).
Please see Appendix A.4.2 for additional details on our BO setup.
5.2 LATENT-TO-TERS TEXT DECODING
With a latent BO proposal that represents promising region of the search space, we now require mechanism to sample textual sequences from the proposed region.
We found that using no dimensionality reduction results in the best performance and is, hence, our default setting for all experiments. Please Appendix A.5.6 for ablation result.
5

---

Published as a conference paper at ICLR 2025
5.2.1 GENERATING SOLUTIONS VIA SEARCH PROMPTS
Given BO proposal vector z/G, we first compute the cosine similarity sxi,= between z/ and each pre- viously observed solution vector (including the warm-start set) Z = {216 " ji=l:w U(z (= We then use the resultant solution-score pairs to construct search prompt by selecting and order- ing the top-k solutions according each $z/ in order to provide
inductive bias for generating solution 24 such that Zz (b(((x))) has higher similarity to z than previous solution vectors z E Z (see Appendix p.. In practice, we sample a batch of candidates for each z/. which we found improved performance for all methods we evaluated
Our method is a Bayesian generalization of a recent in-context optimizaton method, OPRO Yang et al., 2024), which instead constructs a search prompt by selecting the top-k observed solutions according to the black-box function itself, thereby using greedy strategy. As an example, consider Semantle problem with the hidden word being "wordsmith" " and the following previous guesses: "word" (score: 0.7), "sentence" (score: 0.65). "lock" " (score: 0.5), and "metal" (score: 0.49). Using OPRO, we would greedily select "word" and "sentence" to include in the prompt, whereas BOPRO could sample "lock" and "metal" based on the evolving uncertainties in the BO process, thus possibly generating "locksmith", ", which can further generate "wordsmith", ". Different from OPRO, we also find that removing numerical scores from the prompt results in modest improvement across methods, therefore we use this as the default setting.
Generalizing OPRO.
Alternative decoding strategies. Note that our generalization of OPRO can similarly be ex- tended to other in-context optimization methods, e.g., LMX (Meyerson et al. 2023) and FunSearch Coomera-Paredes et al., 2024). which are LLM-based evolutionary algorithms. To demonstrate this generalization, we also show experimental results with one such extension (Bayesian-LMXX, but find that it consistently underperforms BOPRO.
Handling sampling errors. There are two types of errors that can occur when repeatedly generat- ing solutions from an LLM. First, a generated solution may have already been sampled in a previous iteration, and second, generated solution might be invalid with respect to the black-box function, e.g., a generated python program may have syntax errors. To address both problems, we follow prior works and leverage retry ("self-refine") loops. Please see Appendix A.4 for additional details.
EXPERIMENTS
To validate the search performance of BOPRO, comprehensive set of experiments three challenging language-base based search tasks as introduced in 2 -emaantt (word search), Dockstring (molecule optimization), and 1D-ARC (hypothesis+progran search).
6.1 BASELINES
We evaluate three variants of BOPRO characterized by the acquisition function used: BOPRO- logEl, BOPRO-UCB, and BOPRO-TS. Our main baseline is OPRO (Greedy) (Yang al. 2024). which replaces the Bayesian prompting in our method with greedy best-k strategy. We also com- pare with a repeated sampling (RS) baseline"] which relies on the stochasticity from ancestral sam- pling to generate new solutions from a fixed initial prompt. Lastly, we include random baseline that samples & previously observed solution-score pairs in each iteration include in the prompt.
approach that replaces the hard-prompting in BOPRO with soft-prompt that is iteratively optimized using BO. Additionally, described in $5) it is straightforward to generalize Bayesian view to other in- context optimization methods, including evolutionary algorithms, and we present an experiment with one such method, LMX (Meyerson al. 2023).
Additional baselines (77.4).
We also evaluate InstructZero (Chen al. 2024
While every iteration in BOPRO may not yield ze that is close to z/. we show in experiments that the generations are sufficient to guide search towards optimized solutions over time.
Note that in Semantle, the initial warm-start is part of the task description, fixed prompt RS. For ID-ARC, manually write common task deseription used all methods.
make it available as

---

Published as a conference paper at ICLR 2025
2PO Drenty
OPTI (Cready)
Rando
Winds Guesbed
Valocutes Propused
Selutioee Gererated
(a) Semantle
(b) Dockstring
(c) ID-ARC
Figure 2: Best-so-far search performance (using Mistral-Large). (a) On Semantle, all BOPRO
variants outperform greedy OPRO in finding the hidden word by > 10 percentage points. (b) In molecule optimization, BOPRO shows slightly better performance than OPRO on average. Impor- tantly, OPRO is only able to finish optimization for 12 of 58 protein targets in the same wall-clock time as BOPRO due to consistently proposing invalid sequences (causing high latency in black-box evaluation). (c) In program search, BOPRO trails OPRO due to code embeddings that unable to distinguish between sequences with low edit-distances (see $8.2). Takeaway: BOPRO generates higher-quality solutions than all baselines on the tasks of word search and molecule optimization, but shows a failure scenario with hypothesis+program search.
6.2 MODELS
Our main results use Mistral-Large-22 (Jiang et al. 2023) the representative LLM generate solutions for each search method. We also present experiments with additional model families such as I.LaMA331. -88--nsttruc (Dubey et al. 2024), Gemma-2-22 2-bb-It (Team et al. 2024), and GPT-4o Achiam et al. 2023). For the embedding model, the tasks of Semantle and ID-ARC. we
embedding model, since is pre- trained on both general-puryy purposs English data well as code, both of which relevant to the tasks in question. For molecule optimization (Dockstring). we use the Molformer (Ross et al. 2022) embedding model, which jointly pre-trained natural-language text and SMILES strings.
GTE-Qwen-2- 1..-22--1.bbmmmmm Instruct (Li al. 2023), an instruction-us
Please see Appendix A.4 for additional details of our experimental setting.
MAIN RESULTS
7.1 SEMANTLE: WORD SEARCH
In Fig. [ a), show the main results Semantle by describing the percentage of problems where the hidden word was found over 50 problem instances (using 10 hidden words and warm-start sets) with maximum budget in each
1000 guesses and averaged over 3 repeat runs.
Results. First, we observe that both repeated sampling and the random baseline fail to find the hidden word in most runs, thus validating that Semantle is a challenging test bed for search that requires substantial shift the sampling distribution as more evidence is gathered. Next, we find that all BOPRO variants outperform the baselines by 10 percentage points. Notably, while OPRO shows rapid initial gains, it is followed by a long plateau, likely indicating that gets stuck in local optima. On the other hand, BOPRO shows steady gains, pointing to its capability adaptively explore and exploit the search space.
7.2 DOCKSTRING: MOLECULE OPTIMIZATION
Fig. b) shows our results for molecule optimization to synthesize optimized drug molecules for 58 clinically relevant protein targets from the Dockstring (García- Ortegón et al.) (002)) benchmark. In order to perform multi-objective optimization over both druglikeness (QED) and binding affinity
(Vina scores), we follow the common practice in BBO and maximize instead a single scalarized
metric that takes weighted combination of the scores (see Appendix A.4.1) For each protein

---

Published as a conference paper at ICLR 2025
target, start optimization with warm-start set of benzene (c (clecccel), pentane (CCCCC), and acetamide (CC (=O) N), and generate a maximum of 200 new molecule SMILES strings.
Results. Our results show that BOPRO marginally outperforms greedy OPRO on av- erage. More notably, find that OPRO is unable to even finish optimization for all 58 targets (completing only 12) over 2-day pe-
Target: PTPN1
B3P50
B3PMO ucs
BOPA0-T5
CPRO (Conedy)
mosting Afteery cahe scona
riod, which is the same wall-clock time allo- cated to BOPRO. Analyzing the generations, we find that the greedy approach in OPRO con- sistently proposes SMILES strings that are 40% longer than those proposed by BOPRO. This increases cvaluation time with the black-box function and, in fact, results in 17% more in- valid molecules being proposed than with BO- PRO. In Fig. 3] also visualize the distri- bution druglikeness and affinity scores of molecules generated by each method for one protein target, tyrosine-protein phosphatase receptor type (PTPN1). We see that OPRO is unable to jointly optimize both objectives but all BOPRO variants show an ability explore the complex manifold and propose molecules that have high druglikeness and better binding affinity (lower Vina score).
0.0
5.2
0.4
0.5
0.8
3.0
Drugitennss (D6.0)
Figure 3: SMILES distributions for PTPN1
7.3 ID-ARC: HYPOTIIESIS+PROGRMM SEARCH
Constructing ID-ARC-Hard. Following Wang et al. 2024), we run preliminary evaluation on their filtered subset of 108 problem instances. However, our results show that with only simple repeated sampling (RS) for 100 iterations using Mistral-Large it is possible to achieve test set accuracy of $1.48%, 8 points higher than the method Wang et al. (2024) that uses GPT-4. We, therefore, construct ID-ARC-Hard
challenging subset suitable for evaluating search performance by first running RS for 100 generations for each of the 901 problems in the original dataset, followed by sampling 130 instances from the unsolved subset of 175 problems.
Results. Our results are shown in Fig. ( and Fig. 4 Unlike previously, find that all BOPRO variants now trail the greedy OPRO baseline, with BOPRO even un- derperforming repeated sampling, noted as being strong method for code generation in prior work (Brown et al. 2024). We analyze this failure scenario and present hypothesis for the root cause in $
Test Accurayy
7.4 ADDITIONAL EXPERIMENTS
ONO Utread
Figure 4: ID-ARC test accuracy
Below, we present experiments with additional baselines that represent two distinct LLM-based iterative optimization methodologies.
InstructZero is a method that replaces hard- prompts, in BOPRO, with soft-prompts that are also optimized using BO to steer LLM generations to- wards higher utility. We evaluate this method on all 8.00%
InstructZero.
Method
Score
InstructZero
4.00%
InstructZero (w/ sampling)
RS
14.00%
50 problem instances in Semantle using Llama-3.1-8h
BOPRO-LogEI
66.67%
Instruct and compare it with BOPRO in Table [ We use both the original formulation of InstructZero well as a version that uses ancestral sampling instead of greedy decoding. Our results show that InstructZero is unable to outperform even repeated sampling, indicating the lack of any meaningful optimization.
BOPRO-UCB
76.67%
BOPRO-TS
73.33%
Table 1: InstructZero Semantle
8

---

Published as a conference paper at ICLR 2025
so Only BOPRO OPRD
Th4N ACCLPAO
Deeiiy
OPRO (Grazdy)
0.4
Generazed
(a) Solved tasks Vs. warm-start scores
(b) Performance with low warm-start scores
Iargst puttod thcrsserr serdery
(c) BOPRO (solved)
(d) OPRO (unsolved)
Figure 5: Exploration--xploitaiiii trade-off with BOPRO. (a) We show the distribution of tasks exclusively solved by each method versus the average warm-start scores for those tasks. OPRO able to solve tasks with high-scores showing an exploitation strategy, random sampling solves tasks with low scores due strategy), and BO shows a bimodal distribution solving both low- and high-scoring tasks, indicating adaptability task difficulty. (b) On tasks with low warm-start scores, BOPRO and other baselines outperform greedy. (c, d) Search trajectories for problem instance of ID-ARC; OPRO gets stuck local optima, while BOPRO-TS able explore different regions and find the correct solution.
dependence prior generations (thus, using exploration-only
LMX. Next, we evaluate the LMX evolutionary algorithm and also present its Bayesian general- ization, BLMX, described in $5 Our results 1D-ARC show that both LMX and BLMXX viable alternatives to OPRO and BOPRO, respectively, but often trail in performance. Please see Appendix A.5.2 for more details.
Generalization to other LLMs. Finally, we also validate our method with other LLMs (of varied sizes) by running additional experiments on Semantle with GPT-4o and Gemma-2-2b-Ic Our results shown in Appendix [A.5. and demonstrate similar trends to our main results.
WHY BOPRO UNDERPERFORMING ON PROGRAM SEARCH?
To determine the root cause of failure of BOPRO program search, next present detailed analysis of our 1D-ARC results.
8.1 IS BOPRO UNABLE TO BALANCE EXPLORATIOX-EXPLOTTAIII
To answer this question, we design an experiment starting search with different amounts of informa- tion available in the warm-start set. Arguably, tasks with low warm-start scores are more challenging and require more exploration, whereas tasks with high warm-start scores can more easily solved by greedily exploiting the best observed solution. In Figure a). we plot the probability density of problem instances solved by each method as a function of the average scores observed in the warm- start set. We find that OPRO performs better tasks with higher warm-start scores, suggesting an exploitation strategy. With BOPRO, on the other hand, we observe bimodal distribution that covers both low- and high-scores, indicating the ability balance exploration and exploitation.

---

Published as a conference paper at ICLR 2025
*Id_ _d_pcopy____ 1c 21"
21
"1d_ _dd_copy_mpe mc_ 3"
*1d recolor cmp 11
*1d mwve, wtt_movve__pppmmm _p__e__________
*Id_ wco__cocy_ceee _c__3"" 37
0.6
0.6
0.75
0.6
0.6
Difference in black-boo back--bx<<e score
0.4
0.50
0.4
0.4
0.4
0.2
0.25
0.2
0.2
0.0
0.0
0.5
1.0
0.5
0.5
0.5
0.5
"1d move dp. 8"
"1d pcopy. 1c 7
*1d pcopy mc. 30
'1d pcopy 1c 30
"1d mirror 27
0.75
0.75
0.6
0.50
0.4
0.50
0.4
0.2
0.25
0.2
0.2
0.0
distance
Figure 6: Diagnostic for representation quality. The scatter plot shows the distance between candidate solutions of 10 problems ID-ARC in the representation space and the corresponding difference in terms of their black-box scores. Useful representations for BO should result in no points in the top-left quadrant of these plots.
We verify these observations by plotting performance subset of ID-ARC-Hard tasks that have low warm-start scores (below the first quartile). As shown in Fig. Bb, OPRO suffers a sharp drop in performance whereas BOPRO, RS, and even random show improvements, with BOPRO-TS and RS showing the best performance. We also provide visual evidence in Fig. Bjc.d) for demonstrating the ability of BOPRO in balancing intooratioo-xpllitttttii the latent search space (see Appendix A.5.3 for more details). Takeaway: BOPRO does show the ability to balance exploration-exploitaaie and is, thus, not the cause of failure in program search.
by plotting the search trajectories in
8.2 ARE ORT-TIEESSHELL CODE EMBEDDINGS ILL-SUITED FOR PROGRAM SEARCH?
Since BOPRO relies on good representations of the solution space in order to perform meaningful optimization, likely cause of failure poor representation quality from off-the-shelf code em- bedders. which may not provide fine-grained signal for optimizing code sequences. To verify this hypothesis for 1D-ARC and the GTE-Qwen embeddings, we present diagnostic scatter plot (Ko- rovina et al. 2020) in Fig. 6 as their corresponding differences in black-box score Ideally, when I.2 distance low, the score difference should also be low in order to provide useful signal to the nonparametric GP surrogate. From our plot, however, we clearly see that this is not the case, i.c., solutions deemed similar in the embedding space vary dramatically in terms of task scores. This is intuitive as well col-idonsider two python code sequences that only differ in one inequality operator. Off-the-shelf embeddings do not capture this nuanced difference, but such change is likely to have an impact on program output. Takeaway: low edit-distances between candidate solutions and the unavailability of fine-grained code embedding models are a likely cause of failure for BOPRO in program search, indicating an important direction for future work? 9
that shows pairwise 1.2 distances between solution candidates as well
9 CONCLUSION
We propose a novel methodology, Bayesian-OPRO (BOPRO), for LLM-based search using Bayesian optimization, which uses the evolving uncertainty in estimates of the search space to pro- pose promising new solutions in each iteration to find the global optima. Our experiments on word search and molecule optimization show that BOPRO outperforms strong baselines. Notably, BO- PRO outperforms OPRO by 2 10 percentage points on Semantle and produces 17% fewer invalid molecules on Dockstring. On the challenging hypothesis-program search task of ID-ARC, how- ever, BOPRO trails OPRO. We investigate this failure and find that despite BOPRO showing the ability to balance exploration and exploitation, the problem lies in the inadequacy of off-the thelf code embedding models in providing distinct representations for sequences with low-edit distances.
*See Fig. 11 for the same plot on Semantlc.
"See Appendix A.1 for an additional discussion on limitations and future work.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, llge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv: 087744 2023.
Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoye. Intrinsic dimensionality explains the ef- fectiveness of language model fine-tuning. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.). Proceedings of the 59th Anmual Meeting of the Association for Computational Lin- guistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), Pp. 7319-732 7328, Online, August 2021. Association for Computational Linguis- tics. doi: 10. (0.18653/v1/2011 htt.://2222..lloog.556666 URL https: / /acl anthelogyy org/2011.
ac ong...g.....................oo.. 568
Sebastian Ament, Samuel Daulton, David Eriksson, Maximilian Balandat, and Eytan Bakshy. Un- expected improvements to expected improvement for bayesian optimization. Advances in Neural Information Processing Systems, 36:20577-206122 2023.
Peter Auer. Using confidence bounds for exploitation-exploatiin trade-offs. Journal of Machine Learning Research, 3(Nov):3977422, 2002.
Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy. Botorch: framework for efficient monte-carlo bayesian optimization. Advances in neural information processing systems, 33:21524-2155 2020.
MH Bazerman. Judgment in Managerial Decision Making. Free Press, 2012.
Manuela Benary, Xing David Wang, Max Schmidt, Dominik Soll, Georg Hilfenhaus, Mani Nassir, Christian Sigler, Maren Knödler, Ulrich Keller, Dieter Beule, et al. Leveraging large language models for decision support in personalized oncology. JAMA Network Open, 6(11):e233368- e2343689, 2023.
G Richard Bickerton, Gaia V Paolini, Jérémy Besnard, Sorel Muresan, and Andrew L Hopkins. Quantifying the chemical beauty of drugs. Nature chemistry, 4(2):90 2012.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprini arXiv:2407.2 2024.
Lichang Chen, Jiuhai Chen, Tom Goldstein, Heng Huang, and Tianyi Zhou. Instructzero: Effi- cient instruction optimization for black-box large language models. In Forty-first International Conference on Machine Learning, 2024. URL
TADPNrIss3]
François Chollet. On the measure of intelligence. arXiv preprint
Jonathan D Cohen, Samuel McClure, and Angela Yu. Should stay or should go? how the human brain manages the trade-off between exploitation and exploration. Philosophical Trans- actions of the Royal Society Biological Sciences, 362(1481):933-944 2007.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv preprint arXhv:240..21783, 2024.
Peter Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv: 2018.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. arXiv preprint arXiv:2104.0882 2021.
Miguel García-Ortegon Gregor NC Simm, Austin J Tripp, José Miguel Hernández- Lobato, Andreas Bender, and Sergio Bacallado. Dockstring: easy molecular docking yields better benchmarks for ligand design. Journal of chemical information and modeling, 62(15):346--3502 2022.

---

Published as a conference paper at ICLR 2025
Jacob R Gardner, Geoff Pleiss, David Bindel, Kilian Q Weinberger, and Andrew Gordon Wilson. Gpytorch: Blackbox matrix-matri gaussian process inference with gpu acceleration. In Advances in Neural Information Processing Systems, 2018.
Mare G Genton. Classes of kernels for machine learning: statistics perspective. Journal of machine learning research, 2(Dec):299-312 2001.
Rafael Gómezz-Bmbarelll, Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobatg Benjamín Sänchez-LLnggllng Dennis Sheberla, Jorge aguilera-Iparragene Timothy Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven contin- uous representation of molecules. ACS central science, 4(2):268-277) 2018.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
Mykel Kochenderfer. Decision making under uncertainty; theory and application. MIT press, 2015.
Ksenia Korovina, Sailun Xu, Kirthevasan Kandasamy, Willie Neiswanger, Barnabas Poczos, Jeff Schneider, and Eric Xing. Chembo: Bayesian optimization of small organic molecules with syn- thesizable recommendations. In International Conference on Artificial Intelligence and Statisties, pp. 3393-3403, PMLR, 2020.
Akshay Krishnamurthy, Keegan Harris, Dylan Foster, Cyril Zhang, and Aleksandrs Slivkins. Can large language models explore in-context? arXiv preprint arXiv:2403. 153711 2024.
Agustinus Kristiadi, Felix Strieth-Kalthofff, Marta Skreta, Pascal Poupart, Alán Aspuru-Guzik, and Geoff' Pleiss. sober look 11ms for material discovery: Are they actually good for bayesian optimization over molecules? arXiv preprint arXiv:2402.05011 2024.
Harold J Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. 1964.
Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O Stanley. Evolution through large models. In Handbook of Evolutionary Machine Learning, pp. 331-366. Springer, 2023.
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference Learning Representations, 2018. URL
net/ forum?id=ryup WCW
Zehan Li, Xin Zhang, Yanzhao Zhang, Dingkum Long, Pengjun Xie, and Meishan Zhang. Towards general text emheddings with multi-stage contrastive learning. arXiv preprint arXiv:2388.03281, 2023.
Tennison Liu, Nicolás Astorga, Nabeel Seedat, and Mihaela van der Schaar. Large language models to enhance bayesian optimization. arXiv preprint arXiv:2402.03921, 2024.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uni Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self- feedback...k. Advances in Neural Information Processing Systems, 36, 2024.
Bodhisattwa Prasad Majumder, Harshit Surana, Dhruv Agarwal, Sanchaita Hazra, Ashish Sabhar- wal, and Peter Clark. Position: data-driven discovery with large generative models. In Forty-first International Conference on Machine Learning, 2024.
Bodhisattwa Prasad Majumder, Harshit Surana, Dhruv Agarwal, Bhavana Dalvi Mishra, Abhijeets- ingh Meena, Aryan Prakhar, Tirth Vora, Tushar Khot, Ashish Sabharwal, and Peter Clark. Dis- coverybench: Towards data-driven discovery with large language models. In The Thirteenth International Conference Learning Representations, 2025.
12

---

Published as a conference paper at ICLR 2025
Elliot Meyerson, Mark Nelson, Herbie Bradley, Adam Gaier, Arash Moradi, Amy K Hoover, and Joel Lehman. Language model crossover: Variation through few-shot prompting. arXiv preprint 1rXf1:2302.12170, 2023.
Krista Opsahl-Ong. Michael Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. Optimizing instructions and demonstrations for multi-stage language model programs, arXiv preprint arXiv:2406. 1695, 2024.
Martin Peterson. An introduction to decision theory. Cambridge University Press, 2017.
Mayk Caldas Ramos, Shane S Michtavy, Mare D Porosoff, and Andrew D White. Bayesian opti- mization of catalysts with in-context learning, arXiv preprint arXiv:2304.05341, 2023.
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning.
The MIT Press, 2006.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2019. URL httL:/t::/// hatpp:///arxii /rrx
abs/ 0055/198.... 10084]
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468-475 2024.
Jerret Ross, Brian Belgodere, Vijil Chenthamarakshan, Inkit Padhi, Youssef Mrouch, and Payel Das. Large-scale chemical language representations capture molecular structure and properties. Nature Machine Intelligence, 4(12): (126):225-1220 2022. doi: 10. N0.1038//42256-022 020---0022-000 00580-77
Gisbert Schneider. Automating drug discovery. Nature reviews drug discovery, 17(2):97-113, 2018.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint crXiv:2408.03311, 2024.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Jost Tobias Springenberg. Aaron Klein, Stefan Falkner, and Frank Hutter. Bayesian optimiza- tion with robust bayesian neural networks. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neurul Information Processing Systems, volume 29, Cur- Associates, Inc., 2016. URLLttpp://proceednno wtwp:eewdddiins......seee.meeeee cctpppprcccpppppppppppepp files/
Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhu- patiraju. Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, et al. Gemma 2: Improving open language models at a practical size. arXiv e-prints, pp. arXiv-2408, 2024.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294) 1933.
Oleg Trott and Arthur J Olson. Autodock vina: improving the speed and accuracy of docking with new scoring function, efficient optimization, and multithreading. Journal of computational chemistry, (1(2):555-611 2010.
Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah Goodman. Hy- pothesis search: Inductive reasoning with language models. In The Twelfih International Confer- ence on Learning Representations, 2024. URL https: http:////perviiieeeeeeeee URLaattss///peeeeiiiee
net / forum?id
G7Ut IG0mim
Ziyu Wang, Masrour Zoghi, David Matheson, Frank Hutter, and Nando de Freitas. Bayesian opti- mization in a billion dimensions via random embeddings. In International Joint Conference on Artificial Intelligence (IJCAI). Technical Report arXiv: /301. 1942., 2013.
13

---

Published as a conference paper at ICLR 2025
David Weininger. Smiles, chemical language and information system. 1. introduction method- ology and encoding rules. Journal of chemical information and computer sciences, 28(1):31 1988.
T Wolf. Huggingface's transformers: State-of-the-arr natural language processing. arXiv preprint arXiv:1910.03771, 2019.
Yudong Xu, Wenhao Li, Pashootan Vaezipoor, Scott Sanner, and Elias Boutros Khalil. LLMs and the abstraction and reasoning corpus: representations. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL net foruforrmiioo Forrmmidd-Eamsoyysii
Successes, failures, and the importance of object-based
Chengrun Yang. Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoe Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024. URL httpppts//p.e..eeeeeeeeeeee
net/ ForumfG--BBbbbACOOEE
Mert Yuksekgonul, Federico Bianchi, Joseph Boen, Sheng Liu, Zhi Huang, Carlos Guestrin, and James Zou. Textgrad: Automatic" differentiation" via text. arXiv preprint 27Xiv:200.00499. 2024.
A APPENDIX
A.1 LIMITATIONS AND FUTURE WORK
There remain several questions that lie beyond the scope of our immediate investigation but would be useful to consider in future work. For instance, how can we accurately bound the space of valid solutions the latent embedding space in order for acquisition optimization to always give us valid latent proposal as well as not artificially constrain it to a limited region. Currently, we define the bounds for acquisition optimization as 1.5x the convex hull defined by the observed warm- start set. However, this may either be too large too small, depending on the problem. Another unanswered question is whether BO is negatively affected by the existence of multiple global optima, such in ID-ARC. Lastly, it is evident that using prompting- latent proposals back to discrete textual tokens does not offer precise control. Future work should investigate methods that improve the accuracy of converting latent proposals to text.
decoding method translate
A.2 ADDITIONAL. METHOD DETAILS
A.2.1 HANDLING SAMPLING ERRORS
Repetitions. Since our method repeatedly samples LLM to generate new solutions, generation of duplicate samples is common. We, therefore, use a limited number of re-sampling calls to the I.M try and generate new solutions in each round of search. If all calls result in repeated so- lutions, we accept the generation but use the BO proposal as the representation of the generated sequence along with the observed black-box value update the surrogate in the next iteration 1T0
Invalid generations. In tasks such as code generation, some proposed generations may be invalid, e.g., generated program may have syntax errors. In such cases, we use limited number of self- refine (Madaan et al. 2024) calls that attempt to fix the generated solution using the same LLM. If errors persist, we assign the solution a score of 1, assuming a [0, 1] range for valid scores.
A.2.2 EXTENDED BO DESCRIPTIONS
Acquisition functions. We evaluate BOPRO with three types of acquisition functions that each uses the posterior distribution differently to estimate the value of sampling the next point.
Log expected improvement (LogEl) computes the expected gain in performance for each point with respect to the best known solution so far.
1eWe found this technique reduced repetitions in experiments. This is likely due to noisy updates allow- ing the acquisition optimization to escape local optima.
14

---

Published as a conference paper at ICLR 2025
Upper-confidence bound (UCB) computes the value the sum of the value of a point and the standard deviation (uncertainty) at the point weighted by an exploration factor.
Thompson sampling (TS) randomly samples a function from the posterior distribution and uses the estimates from it as the acquisition values.
Acquisition optimization bounds. To optimize the acquisition function and generate a new BO proposal, we use multi-start projected gradient-ascent, which requires the specification of bounds to constrain the proposals. We use a heuristic of setting each dimension of the input embedding space to 1.5x the range observed in priori collection of unlabeled candidate solutions. When such collection is unavailable, we make use of the warm-start set instead.
Tuning priors We sample set of known solution-score pairs, order them in ascending order of their black-box scores, and plot the mean and standard deviation of the posterior distribution for each round of BO see if the posterior progressively fits the ground-truth function shown in Fig. 7
25
1.0
0.8
objective
0.2
Posterior
Warmstart
0.0
Posterior Trend
10.0
12.5
15.0
17.5
20.0
Rank
Figure 7: Prior tuning example on ID-ARC.
A.3 ADDITIONAL TASK/DATASET DETAILS
A.3.1 ARC AND 1D-ARC EXAMPLES
In Fig. 8 show examples of the type of grid transformations that required in the ARC and ID-ARC datasets.
Taining Inpur
Taining Input
Trining Inout
Rest Input
Triniin Cutput
Mirror
(a) ARC
(b) ID-ARC
Figure 8: ARC (Chollet 2019 and ID-ARC (Xu et al. 2024) example tasks.
15

---

Published as a conference paper at ICLR 2025
A.4 EXPERIMENTAL SETTINGS
A.4.1 TASK-SPECIFIC SETTINGS
Semantle. The black-box function we use is the cosine similarity of vector representations gener- ated using the SimCSE (Gao al. 2021) sentence embedding model, where the score for a candidate word x for a hidden word y is computed by comparing sequences "What is (x}?? and "What is a {y}??" The number of warm-start candidates is 20, number of solution generations 1000, BO optimization batch size is (i.e., in each iteration only sample one proposal vector by optimiz- ing the acquisition function), BO decoding batch size is 10. The total BO iterations are, therefore, 100. We also repeat retries with a maximum count of 3. During decoding, examples. The representation model we use is GTE- 10we2-11.5b-nmse
10 in-context
Dockstring. To perform multi-objective optimization over both druglikeness (QED scores) and binding affinity (Vina scores), scalarize the objective into a single metric. First, normalize vina scores by using their typical range of -3 to -12. We then take its negative and compute a weighted combination of this negative normalized Vina (NNV) score and QED scores 0.2 x QED +.8++0.8 0.8 x NNV. Given a new SMILES string generated by the LLM, we follow the mechanism in Yuksekgonul al. (2024) compute QED and Vina scores. Number of warm-start candidates is 3, number of solution generations is 200, BO optimization batch size is 1, BO decoding batch size is 10, number of in-context examples is 10, number of repeat retries is 3, and the representation model is Molformer.
ID-ARC. Since the dataset imposes only a 0-1 accuracy as the objective, we introduce a Hamming-distance based metric to provide process-level supervision for different search meth- ods. Specifically, we calculate the objective as the proportion of cells in the predicted grid that match the ground tround-truth grid. If there is shape mismatch, we assign score of -1. See Appendix [A.3.] for an example task. Number of warm-start candidates is 100, number of solution generations is 200, BO optimization batch size is 1, BO decoding batch size 10, number of in-context exam- ples is 3, number of unique retries is O, the number of self-refine trials for code fixes is 1, and the representation model GTE--wee-22-1 -.----eee-------nstrreee 1b-iintttttt
A.4.2 BO SETUP
We use BoTorch (Balandat et al. 2020) and GPyTorch (Gardner et al. 2018) for all BO-related code in our experiments. We use output standardization and no input normalization, but our embeddings generated using Sentence-Trame Transformers and manually tune the lengthscale and outputscale priors for a Matérn 5/2 kernel (Genton) 200T) by visualizing whether the posterior mean and standard deviation conform the true black-box function in successive BO iterations over a random sample of known set of solution-score pairs for single instance of a task (see Figure 7}. Specifically, we use a gamma prior with concentration=4 and rate=2 for the lengthscale (setting ard num dims=1) and outputscale, and normal prior with mean=0.4 and std=0.01 for the mean function. We also add noise variance of 0.001.
already normalized. We use GP as the surrogate model
A.4.3 LLM AND EMBEDDINGS SETUP
We use Huggingface transformers (Wolf 2019) library and AWS Bedrock APIs to access the LLMs used this work. For embeddings, we use the sentence-transformmrss (Reimers Gurevych] 2019) library along with models hosted on Huggingface. The decoding parameters used for sampling solutions from the LLM are temperature=1.0, top-p=0.9, max.new.tokens=512
A.5 ADDITIONAL EXPERIMENTS AND RESULTS
A.5.1 PERFORMANCE WITH ADDITIONAL LLMS ON SEMANTLE
In Fig. g we show experiments on Semantle using two additional LLMs on opposite ends of the scale spectrum ppecrrmm-Gemma-22 2eemma-2-2b-1 and GTP-4o.
16

---

Published as a conference paper at ICLR 2025
0.8
(Groedy))
0.8
49 0.6
86 Found
0.6
0.0
0.0
6:0
1000
200
400
6:00
850
2020
Words Guessed
Words Guessed
(a) Gemma-2-2b-1
(b) GPT-4o
Figure 9: Performance 50 Semantle problem instances. (a) Using Gemma-2, trend as with Mistral-Large of BOPRO outperforming OPRO, albeit with smaller gap. (b) Using GPT-4o, BOPRO only marginally outperforms OPRO. but demonstrates similar tendency of OPRO in showing rapid initial gains followed by a plateau versus the behavior of BOPRO, which shows steady gains. Note that we able evaluate on two methods due to budget constraints.
the same
A.5.2 PERFORMANCE WITH LMX AND BLMX ON ID-ARC
The BOPRO methodology similarly be extended to other in-context optimization methods by replacing the objective scores in constructing prompts with latent-space similarity scores to the BO proposal vector. For instance, below is description for Bayesian-L.MX (BLMX).
Bayesian-LMX. LMX ("language model cross-over") is an evolutionary algorithm that iteratively builds a new generation of child solutions by prompting the LLM with randomly sampled parent solutions from the previous generation, followed by round of tournament sampling to refine the set of parents sample from in the next iteration based on their objective scores. Similar to BOPRO, BLMX can be constructed by modifying the tournament selection to instead leverage the cosine similarity scores with respect to the BO proposal instead black-box function scores.
0.5
LogEI
BLMX-TS
BLMX-UCB
Test Accuracy
0.4
LMX (Greedy)
0.3
Random (LMX)
0.1
0.0
BUMK-ICS
LMI (Greed))
Randem (UMX)
30
2000
32.3
375
200
Salutions Generated
(a) ID-ARC-Hard: Train
(b) ID-ARC-Hard: Test
Figure 10: LMX Performance on 1D-ARC. Performance on ID-ARC-HarU using LMX-decoding (instead of OPRO) averaged over 130 problem instances on a single run. Overall, the trends remains the same as with OPRO-decoding, but all methods show drop in performance.
Results on ID-ARC-Hard. To implement the BLMX strategy, we first double the number of top- k candidates compared to those used with BOPRO, followed by randomly selecting of them to
17

---

Published as a conference paper at ICLR 2025
"computer"
polyethylene
"meatloal"
0.6
0.4
0.4
0.2
0.2
1.0
0.0
0.0
0.0
0.5
1.0
"airbase"
"killett
"machetes'
'mob'
"filament*
0.3
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.5
1.0
0.0
0.5
1.0
0.5
1.0
0.5
1.0
Figure 11: Diagnostic for representation quality on Semantle. The scatter plot shows the distance between candidate solutions of 10 hidden words in Semantle in the representation space and their corresponding difference in terms of their black-box scores. Useful representations for BO should result no points the top-left quadrant of the plots.
include. We, additionally, do not provide scores the prompt and instruct the model to combine the included solutions to generate new ones. Figure 10 shows our results.
A.5.3 VISUALIZING SEARCH TRAJECTORIES FOR 1D-ARC
We aim to visualize the exploration-exploottiio ability in BOPRO by plotting the search trajectory using t-SNE contour plots of the latent space of embedding vectors. To do this, aggregate all so- lutions generated across runs from each of our evaluated methods to construct map of the effective search space for each task. In Fig. ()c,d), we show search trajectories with BOPRO-TS and OPRO on single problem instance, which demonstrates that BOPRO is indeed able to conduct effective exploration of the search space.
A.5.4 DIAGNOSTIC REPRESENTATION PLOT: SEMANTLE
To contrast the diagnostic plot shown for ID-ARC in Fig. 6 show the same plot for Semantle in Fig. II a task where BOPRO does perform well. We clearly see that our desideratum from such a diagnostic plot of having low score differences when 1.2 distances are low well satisfied.
A.5.5 ABLATION: EFFECT OF NUMBER OF WARM-START EXAMPLES: SEMANTLE
In this section, we perform ablation evaluate the effect of the number of warm-start examples used to initialize
surrogate model. To this, we perform an experiment on Semantle using 5 target words and warm-start sets, resulting in 25 problem instances. We evaluate performance using W = {2, 5, 10, 20, 40) warm-start examples. Our results are shown in Fig. I2 We find that performance initially increases with increase in the number of warm-start examples from W till W = 20. At W = 40, we find that performance lowers. This result follows from the fact that while starting with beliefs about the search space, there is trade-off between using the available budget to perform an initial sampling vs. applying that budget targeted search.
warm-start examples initializes the surrogate model with more accurate
A.5.6 ABLATION: EFFECT OF DIMENSIONALITY REDUCTION ON SEMANTLE
In Fig. 13 we show the effect search performance of using PCA dimensionality reduction, ducing the original Qwen embeddings to 10 dimensions. We run an oracle experiment, where we replace the LLM latent-to-tex decoding step with a selection procedure from fixed set of 4000 words based on neighot retrieval to the proposed BO vector. We do this to remove any emrrr from LLM sampling in our analysis. The results clearly show that using PCA-based dimen-
18

---

Published as a conference paper at ICLR 2025
1.0
BOPRO-LogEI-10
BOPRO-LogEI-2
LogE--0
0.8
BOPRO-LogEI-40
BOPRO-LogEI-5
% Found
0.6
0.2
0.0
200
400
600
800
1000
Words Guessed
Figure 12: Effect of the number of warm-start examples on Semantle.
sionality reduction hampers search performance in BOPRO by large amount (nearly 40 percentage points).
1.0
0.8
% Found
0.6
0.4
BOPRO-LogEI
0.0
RogEO (PCA)
100
200
300
400
Words Guessed
Figure 13: Effect of PCA using selection-based BOPRO run over 4000 words on Semantle.
A.6
LLM PROMPTS
A.6.1
WARM-START GENERATION
Semantle
Your task is to guess hidden test word from the English dictionary. Start by guessing (n_cands) diverse words to maximi ze your chance of guessing the hidden word. creative.
19

---

Published as a conference paper at ICLR 2025
Do not guess any the following words: flist of words repeated by the LIM in the previous iteration).
Dockstring
Your task is to find the optimal drug molecule that has both a high druglikeness (QED) as well as streng binding affinity (vina) to the target protein. while both properties are important, binding affinity is twice important the druglikeness. Here is the target protein: target_proteinj.
Do not propese any of the follewing molecules: (list of molecules repeated by the LIM in the previcus iteration).
ID-ARC
Given the following {len (ttask_demss) } examples of input-output grids of integers from 0-9, your task to determine the transformation logic common to all examples and provide a python function that converts each input grid into its correspending cutput grid. Here are the examples:
INPUT #1:
111,1, 11..,.......
OUTPUT #1: 111,,,1,1........
Each number in grid may be treated as a unique color and a may be treated as an empty or black cell. Cont sequences of numbors row- wise, column-wise, or diagonally may represent objects forming patterns. The transformation involves figuring from the input to the output. For e.g., object patterns may contain shapes like rectangles, triangles, or crosses which can then be mirrored, rotated, translated, deformed, combined, repeated, etc.
how these object patterns change
Your functiens should have the follewing signature: "'yython
def transform (input:: nd.rray) >> ndarrayy Your code here
...
The following packages are already imported so do not repeat them: 'nunpy as np" and 'itertools'
start by guessing exactly (n_cands) diverse solutions that could solve the task. Make sure to not repeat any previous docstring or code. Be creative in the logic of your prepesals!
Do not repeat any of the fol following guesses:
REFEAT #1:
<docstringsThis function... .torciion..ddooctiiiin.... 'python
def transform (input: nd.adarray) -> nd.ndaryyy:
REPEAT #2:
(Note: directly start your response using the specified output format)
20

---

Published as a conference paper at ICLR 2025
A.6.2 SOLUTION REPRESENTATION
To compute embeddings for the generated solutions, first map the raw solution text to template to provide additional context for sentence-embedding models when needed:
Semantle: "(x}"
ID-ARC: "Algorithm:(x)
Dockstring: "Protein target: (target) Molecule Candidate: {x)"
A.6.3
SOLUTION GENERATION
Semantle
Your task is to guess hidden test word from the English dictionary. Use the below series your previcus guesses (in increasing) order of their similarity to the hidden word in terms of their *meaning*) to make new guess, Your new guess should not have been made before and should score higher than your previous guesses. Analyze your previcus guesses to decide what word could reach target
of (target_score:.Af]
If you guess an invalid word (i.e., not in the dictionary or a repeat guess), you will get no score, sc stick to proper, single-word English words, and do not repeat your previcus guesses!
Now, guess exactly n=$s new wo)d that could give you target score (target_scoree.Af)
(Note: give only the word in the previded JSON format)
Dockstring
Your task to find the optimal drug molecule that has both high druglikeness (QED) as well as a strong binding affinity (vina) to the target protein. While both properties are important, binding affinity is twice important the druglikeness. Here is the target protein: target_protein)
below series your previcus guesses increasing order of their scalarized scores (between and 1) to make a new guess to maximize the score. Your new guess should not have been made before. Analyze your previcus guesses to decide what molecule to guess next. If you propose invalid melecule make repeat guess, you will get no score, so stick to valid SMILES strings, and do net repeat your previous guesses!
guess exactly n= molecule that could be the optimal word. creative!
Now, guess exactly n-šs new (o) that could give you target score of score: 4E1.
(Note: give only a list of SMILES strings in the provided JSON format, e. g. \
[1 [I"response"; ["SMILES1", "SMILES2", ...])))
ID-ARC
Given the following (len (task (task_demcs) } examples of input grids of integers from 0-9, your task to determine the transformation logic common to all examples and provide a python function that converts each input grid into its correspending cutput grid. Here are the examples:
INPUT #1:
21

---

'numpy Published as a conference paper at ICLR 2025
111,2,1,1..... OUTFUT 41:
Each number in grid may treated unique color and may treated as an empty or black cell. Continuous sequences numbers row- wise, column-wise, or diagonally may represent objects forming patterns. The transformation involves figuring out how these object patterns change from the input to the output. For e.g., object patterns may contain shapes like rectangles, triangles, or crosses which can then be mi mirrored, rotated, translated, deformed, combined, repeated, etc.
Your functions should have the fellewing signature: "'python
def transform (input: np. ndarray)))) -> np. nd.rraaray: Your code here
The following packages are already imported do not repeat them: as np* and 'itertools'
Here are your top previous guesses and scores (in ascending order of accuracy compared to the target solution)
GUESS (score: ...):
<docstring> </docstring>
GUESS (score: </dbcstring> <docstring>
GUESS (score: ...): <docstring> </docstring>
Analyze your previous guesses to make exactly {n) new guess(es) 1ikely to give you target score of (target_score:.dd 4f). creative your logic
Do not repeat of the following guesses:
REFEAT 41:
<docstringsThis function... wrt.iion.../dccstriiiie </docstring> "'python
def transform (input: adarrayyyy) -> ndarray::
REPEAT #2:
(Note: directly start your response using the speci fied output format)
22


Reviews:
[{"review_id": "EUfjqNvKxr", "reviewer": "Reviewer_mJwg", "summary": "In this paper, the authors are interested in answering whether the LLMs can search for optimal solutions and reason in the planning problems. They extend the prior works which either attempt to predict the task difficulty to select the optimal solution or greedy sequential search, both of which are not always optimal. More specifically, the authors propose Bayesian-OPRO, that integrates Bayesian optimization with LLMs, which iteratively samples from new proposal distributions by prompting the LLM with a subset of its previous generations selected to explore different parts of the search space. They evaluated their method on two language-based search tasks.", "questions": "Questions:\n1.\tHow 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?\n\n2.\tIn 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? \n\n3.\tI am wondering if the choice of other dimensionality reduction technique can  help improve the performance of BOPRO?\n\n4.\tDo authors have any insights on what specific strategies can be introduced to improve BOPRO’s ability to balance exploration and exploitation?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n1.\tThe paper is clear and well-written, with all the relevant works cited. \n\n2.\tThe authors provide a thorough analysis of BOPRO’s exploration and exploitation capabilities and acknowledge that the proposed method fails to exploit.\n\n3.\tI like that this paper discusses the limitations and future work openly. These insights can help future researchers to build and improve upon the current methodology.", "weaknesses": "Weaknesses:\n\n1.\tThe proposed methodology is dependent on the access to an external verifier.\n\n2.\tBOPRO is not able to balance exploration and exploitation and might not be ready for practical use of the reasoning in the LLMs.\n\n3.\tBOPRO might not be ready for practical use yet as it still consistently trails behind the greedy baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "71OhpNrCqG", "reviewer": "Reviewer_AwB4", "summary": "This work proposed a method leveraging LLM to perform optimization, named Bayesian-OPRO (BOPRO). This work can be seen as a generalization version of recent work OPRO. Their method is to intergrate bayesian optimization into LLM-based search, to be more specific, they use BO to determine the search direction for LLM by constructing a surrogate function on the latent space for value assignment. The experiment is performed in two tasks, however, the performance of this method underperforms OPRO in both tasks, although the authors have provided some in-depth analysis in terms of exploration capability and adaptbility.", "questions": "1. The author mentioned in the introduction section that \"Despite moderate success, these solutions are either too expensive, not performant enough, or impractical in offering a general solution for search.\". How does this method resolve these issues? There seems no clear explanation of this aspect in the paper.\n2. 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.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method is novel, although there have been works focusing on combining LLM and BO to perform optimization tasks, the specific method of this work is different from other works. They perform BO process in latent space and design a reasonable encoding-decoding method. \n2. The presentation is good, statements and visual presentation in the paper is clear. \n3. Apart from main experiments, more in-depth analysis about adaptability and exploration are provided.", "weaknesses": "1. The experimental tasks in this works look easy and insufficient, which could not be enough for examine the performance.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ERIleZWZvs", "reviewer": "Reviewer_dfPF", "summary": "This paper introduces BOPRO, a novel search method designed to improve the identification of optimal solutions by combining Bayesian Optimization with an LLM-based search strategy. BOPRO operates through an iterative search process, in which Bayesian Optimization is applied over a latent-space embedding derived from the LLM-generated prompts. \n\nAn empirical evaluation of BOPRO is performed on two benchmark tasks for language-based search, wherein it is found that BOPRO is outperformed by a greedy baseline approach. \n\nFurther investigation of the search behaviour of BOPRO is performed, revealing that it has strong exploration capabilities and can adapt to problem difficulty, but that it fails to effectively exploit promising regions of the search space.", "questions": "I wonder if the authors could explain the importance/significance of separating the solved from the unsolved cases in the various figures. \n\nThere 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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is well-written and relatively easy to follow. The proposed method has many details and \"moving parts\" but these are clearly outlined and their significance explained. The same goes for the experimental setup and results. \n\nThe paper is open and forthright about the limitations of BOPRO. \n\nThe paper includes nice big figures that are intuitive and easy to understand. \n\nDespite the essentially negative results, the paper does a good job of clearly outlining the experimental investigation of BOPRO. \n\nGiven the popularity of LLMs and the effectiveness of Bayesian Optimization, I think the investigation described in this paper can be seen as a valuable contribution and could be a helpful starting point for future research.", "weaknesses": "The results are essentially negative (i.e., BOPRO is beaten by the greedy baseline and/or repeated sampling), which must be considered a weakness. \n\nFigure 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. \n\nI 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. \n\nSome minor issues not affecting my recommendation: \n\n- Line 120 and elsewhere:  \"For e.g.,\" this reads as too informal. Use \"For example,\".\n\n- Figure 3 caption: There is maybe a word missing? \"... random sampling with low due to ...\"\n\n- Section 7.2 Heading and elsewhere: \"v/s\" -> \"vs.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u7NCmhfV7c", "reviewer": "Reviewer_pYWd", "summary": "This paper introduces BOPRO, a novel Bayesian optimization-based search methodology for LLM-driven tasks, showing its exploratory capabilities and adaptability to task difficulty. Despite BOPRO’s strengths, it underperforms compared to a greedy baseline. The paper also identifies its limitations and suggests directions for future improvement.", "questions": "1. Why doesn't the author provide an overall framework diagram of the BOPRO or use the \"Algorithm\" environment in LaTeX to fully describe the BOPRO process? The current description is quite unclear, making it difficult for readers to form a comprehensive understanding of the relationship between BO and LLM.\n2. Why are Qwen-1.5 and T5-base used as the base models? Specifically, (a) why are different models used for the two tasks? (b) why are other models (such as Llama) not evaluated, or why hasn't an ablation study been conducted on the base models? (c) If BOPRO is based on prompts, why not consider using the GPT-4 series as the base model (especially since the original paper on the 1D-ARC dataset also evaluated performance on GPT-4)?\n3. As mentioned under \"weaknesses\", if the goal is to show the generality, comprehensive experiments on multiple search tasks are needed. The following problems could serve as useful references: combinatorial optimization (e.g., traveling salesman problem, knapsack problem), path planning and navigation, game problems (e.g., in reinforcement learning environments, Go, or chess), and program synthesis. While it may be challenging for the author to cover all types of tasks, covering too few problem scenarios is insufficient to demonstrate the generality of BOPRO. Why hasn't the author attempted more tasks?\n4. The comparison methods are not strong enough; simple greedy strategies represent very basic approaches. In the introduction, the author lists a series of highly relevant methods and highlights their shortcomings. Why doesn't the author conduct comparative experiments to demonstrate these shortcomings (as mentioned in lines 51-52, \"too expensive, not performant enough, or impractical in offering a general solution for search\")?\n5. Regarding exploration and exploitation, the author mentions that \"we are interested in answering whether search with large language models (LLMs) can handle this trade-off\"(line 43). Although the trajectory demonstrates a good balance, is this really the capability of the LLM? Most BO-based frameworks specifically balance exploration and exploitation, typically related to the choice of acquisition function. The BO acquisition functions used in the experiments all include sufficient exploration components, so is this balance due to them? This question is not well addressed and may require ablation studies to clarify. \n6. The author mentioned that \"BOPRO trails a strong greedy baseline in aggregate\"(line 26-27). Is this due to the prompt design? Can better performance be achieved by modifying the prompt?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Combining the search capabilities of BO and the language capabilities of LLM is a research direction worth exploring.\n- Plotting the search path (e.g., Fig.1 and Fig.5) is a great way to illustrate the trade-off between exploration and exploitation.\n- The experiment conducted a detailed analysis of BOPRO underperforming.", "weaknesses": "- 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.\n- 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.\n- 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.\n- The reproducibility is questionable. I intended to test the performance of the algorithm, but I could not find any code or materials to support reproducibility. For example, the author claims that BO is described in Appendix A.2, but the expressions for the acquisition functions and related parameters are not provided. Similarly, in the LLM section, there is no explanation for why the Sematle task uses the T5-base model while the 1D-ARC task uses the Qwen1.5 model. ICLR has clear expectations regarding reproducibility (https://iclr.cc/Conferences/2025/AuthorGuide), and the author is encouraged to include such information at the end of the paper. Perhaps a reproducibility statement is not necessary, but at least it should ensure that key parameters are covered in the paper. \n- Expression. The entire manuscript should be carefully proofread; otherwise, it is not ready for publication. For instance, \"warm-start\" and \"warmstart\" are used interchangeably (lines 685 and 689). \n\n[1] Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O Stanley. Evolution through large models. In Handbook of Evolutionary Machine Learning, pp. 331–366. Springer, 2023.\n\n[2] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024.\n\n[3] Lichang Chen, Jiuhai Chen, Tom Goldstein, Heng Huang, and Tianyi Zhou. Instructzero: Efficient instruction optimization for black-box large language models. In Forty-first International Conference on Machine Learning, 2024.\n\n[4] Krista Opsahl-Ong, Michael J Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. Optimizing instructions and demonstrations for multi-stage language model programs. arXiv preprint arXiv:2406.11695, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)