Thompson Sampling via Fine-Tuning of LLMs
Authors: Nicolas Menet
Aleksandar Terzic
Michael Hersche
Andreas Krause
Abbas Rahimi
Venue: ICLR 2026 Poster (2026)
Keywords: Bayesian optimization
Thompson Sampling
discrete domain
variational Bayesian optimistic sampling
cumulative regret
theory
large language model
fine-tuning
probability of maximality
probability of optimality
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We scale Bayesian optimization to massive discrete spaces using large language models, guided by a novel regret bound we derive for a variational form of Thompson sampling.

Abstract: Bayesian optimization in large unstructured discrete spaces is often hindered by the computational cost of maximizing acquisition functions due to the absence of gradients. We propose a scalable alternative based on Thompson sampling that eliminates the need for acquisition function maximization by directly parameterizing the probability that a candidate yields the maximum reward. Our approach, *Thompson Sampling via Fine-Tuning* (ToSFiT) leverages the prior knowledge embedded in prompt-conditioned large language models, and incrementally adapts them toward the posterior. Theoretically, we derive a novel regret bound for a variational formulation of Thompson Sampling that matches the strong guarantees of its standard counterpart. Our analysis reveals the critical role of careful adaptation to the posterior probability of maximality—a principle that underpins our ToSFiT algorithm. Empirically, we validate our method on three diverse tasks: FAQ response refinement, thermally stable protein search, and quantum circuit design. Within a collection of methods covering in-context Bayesian optimization, reinforcement learning, and evolutionary search, ToSFiT exhibits both state-of-the-art sample efficiency and computational efficiency.

Published as a conference paper at ICLR 2026
THOMPSON SAMPLING VIA
OF LLMs
Nicolas Menet Aleksandar Terzic Michael Hersche', Andreas Krause", Abbas Rahimi'
1 IBM Research -urrich, "Department of Computer Science, ETH Zürich
ABSTRACT
Bayesian optimization large unstructured discrete spaces often hindered by the computational cost of maximizing acquisition functions due to the absence gradients. We propose a scalable alternative based on Thompson sampling that eliminates the need for acquisition function maximization by directly pa- rameterizing the probability that a candidate yields the maximum reward. Our approach, Thompson Sampling via Fine-Tuning (ToSFiT), leverages the prior knowledge embedded in prompt-conditioned large language models, and incre- mentally adapts them toward the posterior. Theoretically, we derive novel re- gret bound for a variational formulation of Thompson Sampling that matches the strong guarantees of its standard counterpart. Our analysis reveals the critical role of careful adaptation to the posterior probability of maximality-a princi- ple that underpins our TOSFIT algorithm. Empirically, we validate our method on three diverse tasks: FAQ response refinement, thermally stable protein search, and quantum circuit design. Within collection methods covering in-context Bayesian optimization, reinforcement learning, and evolutionary search, ToSFIT exhibits both state-of-the-ar sample efficiency and computational efficiency.
INTRODUCTION
Humans rely on beliefs, shaped by internal world models, to make decisions. Since our knowledge of the world is often incomplete, these beliefs must account for uncertainty through probabilistic reasoning. To stay effective, beliefs must be updated as new information arises. Bayesian inference provides principled method for this updating process, using Bayes' theorem adjust beliefs by combining prior knowledge with new evidence. This foundational idea extends naturally to compu- tational settings, where algorithms must make decisions under uncertainty.
Bayesian optimization (Kushner 1964 1964 Garnett 2023) is one such algorithmic framework that lever- ages Bayesian inference for large-scale experimental design and automated discovery, particularly in settings where experimental evaluations are costly or time-consuming. As strategy for optimiz- ing expensive black- box reward functions, it maintains posterior distribution over the unknown rewards -yaacclly modeled as a Gaussian process over a domain X X-and uses this model to guide the search for promising configurations. New candidates are selected by maximizing an acquisition function that balances two objectives: exploring uncertain regions to gather new information, and exploiting areas that are already known to perform well (Kushner) 1964
Auer 2002).
Among existing acquisition strategies, Thompson sam- pling [Thompson] 1933; Russo et 2018)) stands out due
prompt
LLM
candidates
reward function
to its state-of-the-ee art convergence guarantees (Russo &
Van Roy] 2014 2016 Chowdhury Gopalan 2017) and
tuning
rewards
its strong empirical performance (Chapelle & 1011) despite being one of the earliest strategies for Bayesian optimization. Thompson sampling draws function from the reward posterior, which effectively serves as an ac- quisition function, and selects the point that maximizes it. The resulting evaluation points are distributed accord-
Figure 1: TOSFIT treats candidate gen- eration as Thompson sampling and fine- tunes the LLM to the posterior PoM.
ing the probability of maximality (PoM) of rewards (Menet et 2025
Code httpps//ggitiii com/ httt://.ccommm/////o/tooptt http///mpsoonssaaaaaaaaa ing- fine- ton-tuninggnn waannnnninggoooo-

---

Published as a conference paper at ICLR 2026
Observations
Posterior Mean
Confidence Interval
Sample from Posterior
Thompson Sample
Continuous Domain
(b) Unstructured Discrete Domain
Whereas in continuous domains gradient ascent can be used to maximize the acquisition function, in unstructured discrete domains maximization would require iterating over all points. To scale to combinatorially large discrete domains, we propose to circumvent intractable acquisition function maximization by directly sampling from the parameterized probability of maximality.
Figure 2:
While acquisition function maximization has been made tractable high-dimensional Euclidean sruces-throught projection to lower dimensions (Wang et al.) 2016 Kirschner et al. 2019) lo- cal optimization (Eriksson et al. 2019 remains fundamental challenge large unstructured discrete domains, where the absence of gradients precludes efficient search. Yet, such spaces are of high scientific and economic relevance. Notable examples include the space of amino acid sequences (Jumper et al. [202] Liu et al. 2023) and the space of valid code for quantum circuits Javadi-Abhar cct al. 2024; Vishwakarma et al., 2024). Note that with 20 amino acids and a maximum sequence length of 100, the search space already exceeds the number of atoms in the observable universe.
In this work, we scale Bayesian optimization to large unstructured discrete spaces by instantiating Thompson Sampling fine-tuming of large language models (ToSFIT, Figure T). Our approach builds on Variational Bayesian Optimistic Sampling (VBOS), established by O D'nnnghue & Latti- more (2021), but introduces key distinction: instead of optimizing toward the posterior probability of maximality starting from a uniform policy, we initialize with a prompt-conditions pre-trained LLM, and gradually adapt it toward the posterior. By treating generated proposals as Thompson samples, ToSFIT avoids intractable acquisition function maximization. Our contributions are:
1. We improve the cumulative regret bound of exact VBOS from Ø(VT[X) to Ō(yTTT) accounting for reward correlation across the search space through the maximal informa- tion gain y² and generalize the bound to cover approximate (e.g., gradient-based VBOS.
2. Our novel regret bound motivates policy initialization according to pre-training & context as well as deliberate fine-tuning to the posterior PoM, resulting in the ToSFIT algorithm.
3. We validate our method on FAQ response refinement, protein optimization, and quantum circuit design. Within collection of methods covering Bayesian optimization, reinforce- ment learning, as well as evolutionary search, ToSFiT exhibits state-of-the performance.
2 PRELIMINARIES
Consider unknown reward vector R over discrete domain X. In Bayesian optimization, want to find the x E X that maximizes Rg. Typically, we model our prior belief as Gaussian, i.e., R N(,, K) with mean and covariance K. Thompson sampling suggests conducting Bayesian optimization by repeatedly conditioning the Gaussian reward vector R on a noisy observation Y, := R2 (O o point x X sampled from the posterior probability of maximality
PoM(z]data)) PRR,- R* data] with R max; R..
In practice, sampling from the probability of maximality is typically implemented by drawing realization from the reward posterior and then selecting the point that maximizes this sample- effectively treating the realization as an acquisition function (Russo et al. 2018 see Figure How- ever, in large unstructured discrete domains, such maximization becomes intractable. To address this, we propose to directly parameterize the probability of maximality using generative LLM. This approach, illustrated in Figure]) [ avoids explicit maximization and, following the framework of O' D'Donoghue Lattimore (202I) ensures consistency with the underlying reward model and thus vanishing regret (see Theorem
2

---

Published as a conference paper at ICLR 2026
2.1 BATCHED BAYESIAN OPTIMIZATION
Traditionally, Bayesian optimization is performed sequentially: one candidate is selected, evalu- ated, and used to update the Gaussian reward model before the next candidate is chosen. However, in many real-world applications succiioonsssshhhhheee as drug discovery (Houghten (2000) or automated program synthesis (Romera- Pareeess et al. (122))-simultaneuus candidate evaluation can significantly re- duce wall-clock time, motivating the development of batched Bayesian optimization (Ginsbourger cct al. 2010 Azimi et al., 2012; Desautels et al. 2014 Wang et al. 2018). Classical Bayesian optimization methods typically propose single, deterministic candidate, and therefore require ad- ditional mechanisms to promote diversity across the batch and avoid redundant evaluations. In con- trast, Thompson sampling naturally generates diverse candidates by independently sampling from the posterior (Hernández-Loord Lobato et al., 2017), achieving equal asymptotic regret as in the sequen- tial setting (Kandasamy al. 2018:] Nava al. 2022). This property makes Thompson sampling particularly well-suited for batched optimization, a key feature of TOSFIT.
2.2 REGRET BOUNDS FOR BAYESIAN OPTIMIZATION
Bayesian optimization algorithms such Thompson sampling and Upper Confidence Bound (UCB, Srinivas et al. 2010) are typically framed as balancing exploration with exploitation (Kushner 1964
Auer 2002 such that, assuming the black-box reward function R X - R is drawn from Gaussian process, in expectation cumulative regret grows sublinearly:
E Ra E oTT).
Here, x² denotes the action played by the Bayesian optimization algorithm conditioned on a history of observations Ht. Note that sublinear cumulative regret is equivalent to vanishing average regret, i.e. asymptotically optimal performance.
Beyond the Bayesian setting, regret guarantees can also be established for the model-agnostic setting that assumes the reward r to lie in reproducing kernel Hilbert space H. induced by a kernel K X X X + R+ In this case, Gaussian reward model is still used for inference, but amplitude (i.e., prior uncertainty) must be chosen large enough to accommodate the complexity of r, as measured by the norm ||r|| K. Notable examples of such model-agnostic algorithms include GP-UCB (Srinivas et al. 2010) and GP-TS (Chowdhury & Gopalan 2017), variant of Thompson sampling.
In practice. however, hyperparameters such the amplitude are often to observations via marginal likelihood maximization (MLM), which can underestimate the true complexity of the reward func- tion (Berkenkamp et al. 2019). To avoid overconfident posterior estimates and premature conver- gence, is common adopt a multiplicative exploration bonus the MLM-fitted prior amplitude. This ensures sufficient uncertainty for effective exploration- a strategy we incorporate into TOSFIT to account for the fixed-reward setting used in experiments.
2.3 VARIATIONAL BAYESIAN OPTIMISTIC SAMPLING
As shown in O'Donoguue & Lattimore (202I) and Tarbouriech et al. (2024) Gaussian PoM is effectively approximated by the VBOS policy म. the distribution that maximizes the functional
((T) = Ex [u + / -2 In TT)) oz], where ग is distribution over X and a. == Va (1)
adaptive UCB exploration bonus
Here, the reward surrogate F.. == Mv + 2 (T.) ) Og represents a nigh-probabilicn upper bound on R, OO'Donoghue & Lattimore 202T). VBOS reveals an intimate connection (Tarbburreeh et al.)
2024 Menet et al. 2025) between PoM and upper confidence bounds augmented with entropy reg-
ularization (Ziebart 2010 Haarnoja et al. 2018). Moreover, max, V+T)) V(PoM) > E[R*] (see
Corollary i Appendix which is the key property that allows bounding the expected cumulative
"The expressivity of a reproducing kernel Hilbert space can vary widely with the choice of its kemel. For instance, the linear kernel induces the reproducing kernel Hilbert space of (all) linear functions, whereas the radial basis function kernel corresponds to smooth subset of the square-integrable functions L22 that can uniformly approximate any continuous function on a compact set.
3

---

Published as a conference paper at ICLR 2026
regret by Ö (T for any optimistic policy with V(T)) E[R"]. In addition to its variational form, Menet et al. (2025) pointed out a near-closed form with almost-linear runtime in [X], given by
2g = v( He-r") for v(c) == exp(- + c) with '² such that Σx Te = 1.
(2)
In combinatorially large domains X, even the near-closed form of Equation 2 becomes too ex- pensive, despite its almost-linear runtime in | Instead, approximate policy
मे
arg A (Xi-1 ((p) based on gradient ascent of Equation (I) must suffice. Our theoretical results in Section
reveal rertoaal the challenges of Bayesian optimization with gradient-based policy updates. As a remedy to accelerate convergence, we cast Thompson sampling as fine-tuning of LLMs.
3 THOMPSON SAMPLING VIA FINE-TUNING
We introduce Thompson Sampling via Fine- Tuning (ToSFIT), a scalable variant of Thompson sam- pling that leverages strong priors from generative pre-training and task-dependent in-context con- ditioning. ToSFIT does not maximize an acquisition function, but rather parameterizes the PoM with pre-trained prompt-conditioned large language model (see Figure By considering model generations as samples from the PoM, we avoid expensive acquisition function maximization. To stay consistent with the posterior PoM and achieve sublinear cumulative regret, we initialize the pol- icy according to the pre-training and then cautiously adapt the model parameters using the VBOS objective. This algorithmic design is guided by the theoretical analysis in Section 4
Algorithm TOSFIT with Gaussian Process Reward Model
Hyperparameters m E N denotes a burn-in period to find prior parameters of the GP and allow the closed-form so- lution # of the VBOS objective to ap- proach the generative policy T² from pre-training (more on that in Section 4 c E N is the number of steps of gradient ascent per step of Bayesian optimization and trades off sample efficiency with Fine-tune Th toward VBOS with learning rate 1) computational efficiency. generation batch size: a large batch size improves GPU utilization and leads to more stable gradients. denotes the batch size of Bayesian opti- mization. 17 is the global learning rate.
Require: pre-trained policy n², GP feature map & Sample .1....,, I' ~ T and observe y1,,-.. 3m
Conduct GP marginal likelihood maximization while budget not exhausted do n K - closed-form Gaussian posterior for j = -....., do
Generate T1... FB R
Estimate d' 20
Vu- K= (TT) using 21,...,
E N the
end for Observe U1,..., Ub associated with æ1, .........)) Conduct GP marginal likelihood maximization end while
{l...., .I....,,), .B}
return (Targ max, ue: max; y1)
3.1 SCALING GAUSSIAN PROCESSES
The Moore-Aronszajj theorem states that any kernel K can be expressed as an inner product in reproducing kernel Hilbert space IHI,, i.e., K K(x, 2) (Φ(x), d(z)) for feature map o X H. Thus we assume, without loss of generality, a linear kernel in HI, enabling scalable Gaussian process inference. Flexibility is retained through the choice of feature map which can be obtained from fixed embedding models (Ranković & Schwaller 2023 Wei et al. 2022), learned adaptively during optimization (Ranković Schwaller 2025), or designed for the task hand (Greenhill al., 2020).
Furthermore, detailed in Appendix D we leverage formulation of linear Gaussian processes that enables conditioning on observations, computing the reward posterior, and performing marginal likelihood maximization-all in closed form. As result, both the computational and memory complexity scale in (dim(H))),. independently of the number of observations, and has negligible overhead (see Table 2 in Section of the Appendix).
3.2 GRADIENTS OF VARIATIONAL BAYESIAN OPTIMISTIC SAMPLING
We derive explicit gradients of the VBOS objective, offering new insights into its optimization landscape. All proofs are in Appendix E Note that the score trick (Williams 1992) cannot be applied blindly, since the reward surrogate iz Mz + (-2n((m)) a. depends the policy ?².
4

---

Published as a conference paper at ICLR 2026
Proposition 1. Consider the VBOS objective V(T") Ezaro lige + v 2m VBOS objective V is concave (strictly of > 0 42) and its gradients are
oz). The
db ((TT) = Exarrd (14 - 2 (TT ) Jx
a0 In m..
11 for
ç E R is arbitrary baseline and -v -v' (u) V22ln(u) 1/ 2 2m - 0.
Interpretation as Energy-Base Model For a given reward uncertainty or and (parametrized) probability of maximality xı there is, according to Equation (2) and up to E R, exactly one consistent expected reward given by 1e := K + v (m²) - Gradient ascent on V thus pushes up the probability of sample generation if and only if fr underestimates the true pa- In this light, VBOS can be considered an energy-based model (LeCun et al. 2006).
3.3 STABILIZING GRADIENTS OF VBOS
To ensure vanishing regret according Theorem D of Section 4 we must fine-tune the prompt- conditioned pre-trained policy T² toward the posterior PoM using gradient ascent on the VBOS objective. Define the pscudo reward P == -- ( that occurs in Proposition Then
de VTT") E Ex) In क.. with 2; n.
Here, 70 - & is referred to as the advantage function. In practice, this estimator can suffer from high variance, depending on the choice of baselines & E E. To address this, we adopt the Reinforce Leave-One-Out (RLO0) baseline (Kool et al., 2019), where each & is set to the average of the other surrogates in the batch: &; B-I ii P This technique has been demonstrated to outperform more complex alternatives like Proximal Policy Optimization (Schulman et al. (017)) in fine-tuning large language models (Ahmadian et al.) 2024). To further stabilize learning, we normalize the advantage function by its empirical standard deviation, derived from the empirical second moments:
advantage std 1/ E, ( {n which amounts to variance-adaptive learning rate. As shown in Proposition 3 of Appendix C standardized RLOO is mathematically equivalent to the advantage function used in Group Relative Policy Optimization (Shao et al. 2024).
4 THEORY
Given that one cannot exactly maximize VBOS in practice without incurring prohibitive computa- tional cost, how close is any policy the maximizer? Geometrically, the divergence of a policy from the exact VBOS policy स is measured by the suboptimality gap in the VBOS objective:
Proposition 2. Let a R |X| divergence (p f(p) - f(g) (Vf(g).p q)- Then the Bregman divergence of any π 1 from the maximizer के arg maxpe V(p) given by Do( 7) V(+)) (TT).
For the convex f(p) -. P&O /
2 2n Pa. define the Bregman
Even the exact VBOS policy से only conducts approximate Thompson sampling. Nevertheless, O' D'Donoghue & Lattimore (202) prove upper bound the cumulative regret incurred when sampling a bandit according to exact VBOS, i.e., for x' ~ The bound reads E, /²" - RR+]] S [ In [X| T"). Note that the structure of the kernel is not taken into account, i.c.. the worst-case bandit with independent arms is assumed. In Theorem we demonstrate a significantly tighter regret bound for VBOS, matching the strong regret bounds of Thompson sampling (Russo & Van Roy| 2014) and GP-UCB (Srinivas et al. 2010), regardless of the kernel.
Theorem 1. Let R ~ N(n, K) with Kr I 1 Vx E X and additive observation noise N (0 If R observed at T² for a policy &¹ depending on history H², then
EITT, R' Roo] S VCo, HTTT + De
C-. + ²) is constant, H == HI is the expected average entropy of the
policy and hence upper bounded by In [X|, n² == max I[YLT; ; R) is the maximum information gain for observation locations L", and # is the unconstrained maximizer of VBOS given H².
Thee theorem also holds for heteroscedastic additive Gaussian noise replacing on with maxzex (n(x).
5

---

Published as a conference paper at ICLR 2026
For exact VBOS, have improved the cumulative regret bound from T(X) to o Whereas the former is vacuous in combinatorially large discrete domains X, the latter is not. E.g., with linear kernel in d dimensions, have >" Od yielding regret bound that scales gracefully with the problem size (Srinivas et al. 2010).
For inexact VBOS, we provide the first regret bound. It depends on Bregman divergence between the exact solver #f of VBOS, and the sampling policy x¹. As Proposition Propositionnestablisseee Destablishes this Bregman divergence directly captures what extent nO maximizes the variational objective V.
4.1 INSIGHTS: POLICY INITIALIZATION VIA PRE- TRA-NIAIN CONTEXT
The approximation error (x #*) risks dominating the regret bound, since gradient-based optimization of the VBOS objective V yields a policy n² that lags behind the exact VBOS policy मt. To mitigate this source of cumulative regret, T' must be initial- ized and maintained within high- probability neighborhood of #', es- pecially for large when म' tends to concentrate near the pre-trained pol- icy. To support this, TOSFIT initial- izes n' via pre-training and prompt- conditioning, and adapts cautiously toward the posterior PoM #' using small learning rates. These insights are illustrated in Figure for for a three-armed bandit and experimentally verified Section [5.6] Note that Theorem [ holds even the pre-training prior nº is biased toward suboptimal regions. In that case, more compute effort in the form of gradient steps are required to ensure a vanishing Do (*),
Policy Simplex
Policy Simplex
Inexact
Careless
VBOS
TOSFIT
Uniform Policy
Exact VBOS
Careful TOSFIT Pre-trained Policy
Figure 3: Left: Inexact gradient- based VBOS struggles to find the best arm in very high-dimensional probability sim- plices. Right: ToSFrT starts in the right region of the sim- plex. Still, careful adaptation towards VBOS is paramount to retain the prior knowledge necessary to find the best arm.
5 EXPERIMENTS
We empirically evaluate TOSFIT across three diverse domains for language models between 0.6B and 8B parameters. We report the mean and standard error of the best-seen reward using 25 random seeds, defined as the maximum reward observed up to step i... max45n Tat. This metric cap- tures the best solution found so far and is often used in black-box optimization benchmarks. Details in Appendix B Within collection of methods covering Bayesian optimization, reinforcement learning, and evolutionary search, FoSFIT exhibits tional efficiency. ToSFIT can naturally be applied in batched settings, and sample efficiency can be further improved by adjusting the computational effort per round of Bayesian optimization.
sample efficiency and computa-
5.1 SETTINGS
FAQ Refinement is a natural language task that tests the algorithm's 's ability to optimize text based on semantic alignment. We ask a Owen3-1.7B/Qwwnn--e model (Yang et al., (2025) write (FAQ) response. The reward is modeled as the alignment to an unknown ground-truth, judged by the Swen3--mbedddigg.. we adopt a linear kernel over the first 256 entries of the embeddings of The search space consists of all token sequences, which is exponentially large in the response length.
model (Zhang et al. 2025). As a deep kernel,
-0.diinng........... 6.6
Protein Search explores the challenge of designing thermally stable proteins- a task with significant implications for drug development and industrial biotechnology. The goal is to identify amino acid sequences that exhibit high thermal stability, a property that enhances protein robustness and shelf life. Note that with 20 standard amino acids in the human body and sequence lengths of 100 and above, the search space exceeds the number of atoms in the observable universe. We sample amino acid sequences from ProtGPT2 (Ferruz et al.] 2022) (0.738B parameters) and score them according to their negative thermal instability index (Guruprasad et al. 1990). Two baselines, FIBO and EVOLUTIONARY SEARCH (LLLM), require instruction-tuned models. There, we Qwen3-

---

Published as a conference paper at ICLR 2026
0.6B/Qwen3-88 8B model. To predict the thermal stability and assess epistemic uncertainty, adopt GP with linear kernel over the mean token embeddings from ProtGPT2 projected to the unit sphere.
Quantum Circuit Design the task of designing quantum circuits that prepare low-energy quan- tum states in unknown environments. The challenge lies in navigating vast, discrete space of valid quantum programs, where entanglement and gate structure critically influence performance. To gen- erate Qiskit circuits Tavadi-Abhar et al. 2024), model (Hui et al., 2024) prompted to fill-in-hhe-mide middle (Bavarian et al. 2022) after initializing six disentangled qubits in the state. The baselines FIBO and EVOLUTIONARY SEARCH (LLM) require instruction-tune 7B-Instruct. As reward, consider the negative energy of the prepared state under unknown Hamiltonian with strong interaction terms, requiring entanglement for optimal performance. The feature map for the linear Gaussian process over rewards consists of a code validity bit well as all two-qubit Pauli observables, which can be efficiently simulated using quantum computers.
Qwen2.5 1oen2..--oderr (ooder-1..BBB Set.B//wee...-oooleeee
models, for which we use Qwen2.5 1-555-CCer----e 1.55- Inssrruct/Qwen25--Cooeee
5.2 BASELINES
We compare against seven baselines, For fair comparison, the reward model (if present) is always Gaussian process over the same (deep) embeddings. As in [i et (2022). UNGUIDED GEN- ERATION samples directly from the pre-trained LLM without feedback, serving as a -daapivee baseline. As in Kristiadi al.] (2024) and Ranković Schwaller (2025). POST-GENER ATION TS performs Thompson sampling over fixed subset of candidates (of size 1000), here generated by the LLM prior to optimization. ACTOR CRITIC (Barto et al. 1983) maximizes Egare [Ux] rather than V. and SOFT ACTOR CRITIC (Haarnoja et al. 2018) additionally adds entropy regularization, i.e.,
Unguided Generation
Evolutionary Search (LLM)
Actor Critic
FIBO
Post- Gett-Gerration TS
Evolutionary Search (Character)
Soft Actor Critic
ToSFIT
80
Best-Seen See-SSennie Reward
60
0.82
40
0.80
20
0.76
-0
500
1000
500
1000
500 # Evaluations
1000
# Evaluations
# Evaluations
(a) FAQ Response Refinement using Qwen3-1.7B
(b) Protein Search
(c) Quantum Circuit Design
using PrxGPP22-0.78 or Qwen3-0.6B
using Qwen2.5-Code S-CCodar-.5B(Innnsee
0.98
80
Best-Seen Reward
60
0.96
40
FIBO (best 10)
20
0.84
-20
0.82
1000
1000
# Evaluations
# Evaluations
# Evaluations
(d) FAQ Response Refinement
(e) Protein Search
(f) Quantum Circuit Design
using Qwen3-8n
using ProIGPT2.0 0.7B or Qwen3-8B
using Qwen2 S.Cder 7BC Instrnet)
Figure 4: Across three tasks and within collection of methods covering Bayesian optimization, inforcement learning, as well as evolutionary search, ToSFIT exhibits state-of-the-a performance. In (b) and (e) EVOLUTIONARY SEARCH (LLM) and FIBO Qwen for instruction following.

---

Published as a conference paper at ICLR 2026
maximizes Ez-ro like a In m EVOLUTIONARY SEARCH (CHARACTER) (Holland 1975) treats solutions as sequences of text characters and applies biology inspired crossover and mutation opera- tors. EVOLUTIONARY SEARCH (LLM) (Romera Paredes et al. 2024) prompts language model to conduct crossover and mutation of solutions. Finally, FIBO (Sutter et al. 2025) performs Thompson
sampling fully in-context of LLM by attending list of evaluated candidate solutions.
5.3 TOSFIT OBTAINS STATE-OF-THE-ARY SAMPLE EFFICIENCY
Consider Figure In all three tasks Lasks-FAQ Response Refine- ment, Protein Search, and Quantum Circuit Design-ToSFri obtains state-of-the-at sample efficiency. Indeed, the best-seen reward of UNGUIDED GENERATION quickly saturates a sub- optimal level. Classical Bayesian optimization over fixed subset of generated candidates PROST-GENERATION TS) iden- tifies good solution more efficiently. but remains confined the initial sample pool. EVOLUTIONARY SEARCH as well as ACTOR CRITICS conduct undirected exploration without opti- mism in the face of uncertainty, i.e., an exploration bias guided by the reward potential of unexplored regions. As confirmed in Figure 5 the optimism of ToSFIT results in a more stable exploration-exploitttonn tradeoff than that of ACTOR CRITICS. FIBO is closest to ToSFIT in spirit, but relies on in-context learning instead of parameter updates. As can be seen from the result, this leads to significantly lower performance than TOSFIT. As FIBO keeps the generated candidate solutions as generation context, it quickly runs out of memory and compute scales quadratically with the number of rounds, forcing us to compare against a top- 10 truncated version of FIBO in Figure 4d
Actor Critic
Goneration Entropy
200
ToSFIT
150
100
50
0
500
1000
# Evaluations
Figure 5: TOSFIT balances explo- ration with exploitation leading to stable policy diversity. Shown Quantum Circuit Design, for other settings, see Section A.2
Table 1: Among all LLM-based methods considered for optimization, only TOSFIT explores using optimism, conditions model generation for improved efficiency, and does not require the LLM to execute complex procedures via instruction following which sets requirements on the model size.
Exploits
Explores using Entropy
Explores
Conditions
Instruction Following
Promising
using Optimism
Model Generation
Regions
Agnostic
UNGUIDED GENERATION
no
yes
POST-GENERATION TS
yes
yes yes no
yes yes
EVOLUTIONARY SEARCH
yes
ACTOR CRITIC
yes
no no yes yes
SoFT ACTOR CRITIC
yes
yes
no yes
yes
FIBO
yes
yes
yes
yes
no
TOSFIT
yes
yes
yes
yes
yes
Scaling to Larger Models Contrast the top row of experiments in Figure 4 with the bottom row (in Protein Search ProtGPT-2 used twice for TOSFIT as well as all baselines without instruction following due the absence of larger variants thereof). While increasing the model size is highly beneficial to FAQ Response Refinement, a natural language task, the tasks of Protein Search and Quantum Circuit Design profit far less. This matches the observations by Rooera--areees et al. (224) for code discovery. Indeed, novel discovery often requires leaving the training data manifold, l... the generative policy does have be tightly concentrated on the most promising solutions.
5.4 ToSFIT REMAINS EFFECTIVE BATCHED BAYESIAN OPTIMIZATION
So far, we have focused on sequential Bayesian optimization, setting 6 1 in Algorithm How- ever, when observations are delayed or time- consuminn batched Bayesian optimization becomes preferable. Figure 6 considers setting where up to 16 proteins can be synthesized and tested in parallel. While batching reduces sample efficiency- efficiencyrrquiiing requiring more evaluations to reach given reward-it improves iteration efficiency, achieving target performance in fewer rounds.
8

---

Published as a conference paper at ICLR 2026
100
80
Best- Best-Seen Reward
ToSFiT
Best- Seen Reward
TOSFIT
ToSFIT
TOSFIT 4
ToSFiT
60
TOSFIT 16
50
40
50
100
150
200
250
0
200
400
600
800
1000
# Evaluation Batches
# Evaluations
Figure 6: Protein Search with batched TOSFIT. The number to the right indicates the batch size b. Larger batches improve the iteration efficiency (left) with slightly lower sample efficiency (right).
5.5 TOSFIT TRADES OFF COMPUTATIONAL EFFICIENCY WITH SAMPLE EFFICIENCY
Consider Figure 7a
which explores the com- putational efficiency of
Best Seen Reward
100
Best Seen Reward
80
75-
TOSFIT. We do not plot the ACTOR CRITICS and POST-GENERATION TS, as their computational cost matches, respectively, ToSFIT and UNGUIDED GENERATION with strictly worse reward. For 10'000 rounds FIBO runs of memory in its standard implementation, thus once again implement FIBO attending only the top-10 candidate solutions and their scores. This also decreases its compute costs drastically at the cost of limiting its sample efficiency. Note that the strong sample efficiency of TOSFIT compensates for the additional compute cost introduced by model fine-tuning, resulting in state-of-the-art computational efficiency. Next, consider Figure 7b By investing additional compute through multiple steps of gradient ascent per round, the sample efficiency of ToSFIT can be further improved if needed.
Unguided Gen.
50-
RIBO (hes
60
TOSHIT c=1
25-
Evolut Scarch
ToSFiT c=2
T:SRT
ToSFiT c=4
0-
40
TOSHIT c=8
25
2500
5000
7500
500
1000
Seconds NVIDIA A100
Evaluations
(a) Latency on fully batched (B
(b) The sample efficiency TOSFIT
= 16) Protein Search. FIBO and EVOLUTIONARY SEARCH (LLM)
on Protein Search is improved by in-
creasing the number of steps of gradi-
each tested with Qwen3-0.6B (fast) and Qwen3-8B (slow).
ascent per round (denoted by
Figure 7: TOSFIT has state-of-the-art computational efficiency (a) and can trade off computational efficiency with sample efficiency (b).
5.6 TOSFIT BENEFITS FROM STRONG PRIORS AND REQUIRES CAREFUL PINE-TUNTE
Lastly, we validate our theoretical insights. Theorem highlights the importance of initializing the sampling policy with strong prior knowledge. Figure g provides empirical support: masking the number of qubits in the prompt (TOSFIT weak context) leads to a significantly worse reward than using the full prior context (TOSFIT). Note that uniform initialization fails produce valid code. The theorem further suggests cautious adaptation to avoid drifting too far from the initialization. shown in Figure 9 large learning rate may initially improve performance by closely following VBOS, but eventually leads to forgetting the prior and stagnating as optimization becomes harder.
RELATED WORK
As a remedy for the intractable maximization of acquisition functions over combinatorially large discrete domains, Bal et al. (2025) assume a factorization into the cartesian product of much smaller domains. They then identity local maxima as configurations where changing any of the factors individually decreases the acquisition function, and query the black-box function with the highest scoring game equilibrium. In contrast to TOSFIT, the domain must be structured to admit a factor- ization into cartesian products, and their optimization strategy does not leverage priors from L.Mss.

---

Published as a conference paper at ICLR 2026
0.85
Best-Seen Reward
Best- SSenn Reward
4
Unguided Generation
Unguided Generation
0.80
T6STT IE-6
3-
ToSFIT
ToSFIT 1E-7
T6STIT weak context
TOSFIT 1E-8
0.75
2
200
400
600
800
1000
200
400
600
800
1000
# Evaluations
# Evaluations
Figure 8: TOSFIT benefits markedly from strong initial policy. On Quantum Circuit De- sign, using the most informative initial policy yields much better performance.
Figure 9: Careful adaptation to VBOS is essen- tial to retain prior knowledge, here demonstrated for FAQ Refinement. The learning rate (1) is in- dicated to the right.
In similar vein, Swersky et al. (2000) propose maximization of acquisition functions over discrete spaces through local mutations candidate solution. To conduct directed mutations, they learn policy. In contrast to TOSFIT, their policy must be repeatedly applied to maximize the acquisition function, which quickly becomes expensive by itself, and shares similar limitations |Bal et al. 2225), such as the need for structured domains and lack of integration with pre-traines models.
There is extensive prior work on relaxing Bayesian optimization over discrete space to continuous space using variational autoencoders (Kusner et al. 2017: Lu et al., 2018 Griffiths & Hernández- Lobato 2020) Notin et al.] 202T] Lee al.) 2025). Acquisition function maximization
then tractably performed via gradient ascent in the continuous latent space. However, these methods require a task-specific pre-training phase for the autoencoder, whereas TOSFIT can be applied zero-
shot through prompt-conditionie thus benefiting from large-scale industrial LLM pretraining.
Finally, Rankovie & Schwaller 2025) learn deep kernel features for Bayesian optimization with Gaussian processes. By treating the neural feature map hyperparameter, they gradient ascent to maximize the marginal likelihood of observations during Bayesian optimization in a fully online fashion. Experimentally, they find much better optimization trajectories compared to fixed feature maps. That said, they do not address the intractability of acquisition function maximization. Their method is complementary to TOSFIT and could be integrated to learn task-specific embeddings.
7 CONCLUSION
We demonstrate that Thompson sampling can be efficiently scaled to large unstructured discrete domains by parameterizing the probability of maximality with generative policy. Our theoreti- cal analysis reveals that VBOS already leverages the kernel structure of Gaussian processes and achieves the strong regret bound of standard Thompson sampling and GP-UCB. Extending these results to approximate V VOOS highlights the importance of initializing the sampling policy accord- ing to strong priors from pre-training and adapting it cautiously to maintain prior knowledge. These insights are supported by empirical results across three diverse tasks. Within a collection of meth- ods covering Bayesian optimization, reinforcement learning, as well as evolutionary search, and to statistical significance, ToSFIT exhibits simultaneously state-of-the-a sample efficiency and computational efficiency. Together, our findings demonstrate the potential of combining foundation models with principled Bayesian optimization to tackle complex, discrete search problems.
7.1 LIMITATIONS AND FUTURE WORK
To ensure controlled comparisons, we evaluate TOSFIT under fixed feature maps-either derived from pre-trained embeddings or manually designed. A promising direction for future work is to learn deep, task-adaptive embeddings jointly with the Gaussian process, as Ranković & Schwaller 2025), replace the GP with more expressive reward models such Bayesian neural networks or ensembles (Lakshminarayanall et al. 2017). Moreover, to reduce the computational and memory could restrict updates to the last few layers of the gener- such as in-context
overhead introduced by tine-tuning ator. Finally, alternative strategies for optimizing the VBOS objective conditioning-nan may offer a lightweight alternative weight adaptation.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This work does not involve human subjects, personally identifiable information, or sensitive data. All experiments were conducted using publicly available models. The proposed method, ToSFIT, is intended for research in optimization over discrete domains and is evaluated in controlled settings. We emphasize that ToSFIT is intended for deployment in high-stakes decision-making without appropriate human oversight and Lomain-specinn validation. As ToSFIT avoids the costly max- imization of acquisition functions, environmental impact was a central consideration. No known conflicts of interest are associated with this work.
REPRODUCIBILITY STATEMENT
Apart from the complete experimental code base provided publicly at /attps://githin com/ TBM/thompson- sampl -ai--sssmlliiii--aaa foig-via-fine-tiue www.ineettnnnn-eeeeeeeee toee-tuiingoff11mme
pseudocode for TOSFTT is given in Algorithm [ The baselines are also implemented in the code in self-contained man- ner. The experimental environments for the three tasks considered also provided in the code. Moreover, the provided README.md gives step-by-step tutorial to reproduce all results in the paper. The hardware and software for running the experiments is described in detail in Section the Appendix. Furthermore, Section (o.tionnB.3]dee detaill the hyperparameter sweep conducted during devel- opment this paper. In the evaluation, statistical significance is indicated via mean and standard under 25 seeds, complete set of assumptions. Both detailed proofs as well as proof sketches for the main results are provided in Section of the Appendix. We distinguish between novel claims and prior statements by citing the appropriate works.
O,.... . 24. All theoretical statements
self-contained and include the
ACKNOWLEDGMENT
This work is supported by the Swiss National Science Foundation (SNSF), grant 10002666.
REFERENCES
Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadaee, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back basies: Revisiting REINFORCE-style optimization for learning from human feedback in LLMs. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, volume 1, 2024. URL https:/ arxivv abs/2402..0 14740
Peter Auer. Using confidence bounds for exploitation-exploraiion trade-offs. Journal of Ma- chine Learning Research, 3, 2002. URL htttt:://ww.ww.... hwtp://w...orgpppppe///oo.o.o.o.
Javad Azimi, Ali Jalali, and Xiaoli Fern. Hybrid batch Bayesian optimization, 2012. URL https:
//arxiv. org/ abs/ /12.a.12222.50 5597
Melis Ilayda Bal, Pier Giuseppe Sessa, Mojmir Mutny, and Andreas Krause. Optimistic games for combinatorial Bayesian optimization with application to protein design. In International Confer- ence on Learning Representations, 2025.
pattps://arxtie http:///..rr/abbb//0../.
Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, pp. 834 846, 1983.
httttps://leeexplorrtt
leee. htt.://ww......e.eeeeec///oeoe/e
Mohammad Bavarian, Heewoo Jun, Nikolas Tezak, John Schulman, Christine McLeavey, Jerry Tworek, and Mark Chen. Efficient training of language models to fill in the middle, 2022. URI.
https::/arxiv wwt./oo/////oooooooooooooo.. 2207 14255
Felix Berkenkamp, Angela P Schoellig, and Andreas Krause. No-regret Bayesian optimization with unknown hyperparameters. Journal of Machine Learning Research, 20, 2019. URL https:
11

---

Published as a conference paper at ICLR 2026
Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Neural In- formation Processing Systems, 2011. URL wttppp:ppppppppeeeeeeeeeee nips. hwtp::ssssssssccscepeeeeeessesee cc/ppprr files/
Sayak Ray Chowdhury and Aditya Gopalan. On kemnliizdd multi-armed bandits. In International Conference on Machine Learning. Proceedings of Machine Learning Research, 2017. URL
https::/aaxiy>: org/ 1704. 00445
Peter JA Cock, Tiago Antao, Jeffrey T Chang, Brad A Chapman, Cymon J Cox, Andrew Dalke, Iddo Friedberg, Thomas Hamelryck, Frank Kauff, Bartek Wilczynski, et al. Biopython: freely available python tools for computational molecular biology and bioinformatics. Bioinformatics,
25, 2009, URL wtt.thttts:/speeeeeeeee ncbi...... r.lm.
Thomas Desautels, Andreas Krause, and Joel W Burdick. Parallelizing exploration-exploitation tradeoff's in Gaussian process bandit optimization. Journal of Machine Learning Research, 15(1): 3873-3923, 2014. /ttttttss///ssstttt http:/iwwww..r.a.oa/aaoo/a// /20.. 6402
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D) Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In Neural Information Processing Systems, volume 32, 2019. URL
arxiv. http://twww.o..g.....//oooo wwwp//g/////ooooooo/////////.abe abs / 1910.01739
Noelia Ferruz, Steffen Schmidt, and Birte Höcker. ProtGPT2 is a deep unsupervised language model for protein design. Nature communications,, 13(1):4348, 2022, URL BRLLhttps:/// nawur....w.........ee.aammmm....
com/ http//aaaccee///111--002222 32007-7
Roman Garnett. Bayesian Optimization. Cambridge University Press, 2023. URL https://
David Ginsbourger, Rodolphe Le Riche, and Laurent Carraro. Kriging is well-suited to parallclize optimization. In Computational intelligence in expensive optimization problems, pp. 131-162. Springer, 2010. URL http:::ttt///tttt es ubc. 2010 CI (tr.aooourrrrbaallllllrli...oaao
Robert M Gray. Entropy and Information Theory. Springer Science & Business Media, 2011. URL
www.sstaarrr...o. otttps://ee.ttaaford..ee wtw.:/aaooe.euuegrggaaaeae//a//e
Stewart Greenhill, Santu Rana, Sunil Gupta, Pratibha Vellanki, and Svetha Venkatesh. Bayesian optimization for adaptive experimental design: A review. IEEE access, 8:13937-13948, 2020.
URL htt.::pss///eeeexplrreee feee. htrg//dccumeet/855740
Syan-Rhys Griffiths and José Miguel Hernández- Bernandez-Lbbto. Constrained Bayesian optimization for automatic chemical design using variational autoencoders. Chemicul science, 11, 2020. URL
https://arxiie /tttps://arxiv.orr//aass///// wwt./bs////oooooooooo
179.. 05501
Kunchur Guruprasad, BV Bhasker Reddy, and Madhusudan W Pandit. Correlation between stability of a protein and its dipeptide composition: a novel approach for predicting in vivo stability of protein from its primary sequence. Protein Engineering, Design and Selection, 4, 1990. URL
htttps://pubncr .nb.b nlm. nih. gttpp//519//////////
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- on Machine Learning, 2018. URL httph: /ttp/aiiviv/.. wwtp://gggaabbsssoooo
abwaabssssss 010111111111100111111111111 01290
José Miguel Hernández-Lobato, James Requeima, Edward O. Kyzer-Knapp, and Alán Aspuru- Guzik. Parallel and distributed Thompson sampling for large-scale accelerated exploration of chemical space. In International Conference Machine Learning, pp. 1470-1479. Proceedings of Machine Learning Research, 2017. URL http:hhtss://aattt http:://axivvv.o www.xii.oog/bb......o 018.
John Henry Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, 1975.
Richard A Houghten. Parallel array and mixture- synthetic combinatorial chemistry: Tools for the next millennium. Anmual Review of Pharmacology and Toxicology, 40, 2000. URL https: 7/pubmed ncbi .nlm. .in wttplo//ooo/101100
12

---

Published as a conference paper at ICLR 2026
Binyuan Hui, Jian Yang, Zeyu Cui, Jiaxi Yang, Dayiheng Liu, Lei Zhang, Tianyu Liu, Jiajun Zhang, Bowen Yu, Keming Lu, Kai Dang, Yang Fan, Yichang Zhang, An Yang, Rui Men, Fei Huang, Bo Zheng, Yibo Miao, Shanghaoran Quan, Yunlong Feng, Xingzhang Ren, Xu- ancheng Ren, Jingren Zhou, and Junyang Lin. Qwen2.5-Coder technical report, 2024. URL
htttps://axxiv www. htw.g///bb//2233 12186 1
Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quantum computing with Qiskit, 2024. URL https:tt////mm http://xxxvv.rr./.. abs/
2405. 08810
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvumakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate protein structure prediction with AlphaFold. nature, 596, 2021. URI.tttss: /wtp///ww..........////
com/ com/articles// 34 wet.eeeeeeee/111102222222222 021-1999-22-
Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabás Póczos. Parallelised Bayesian optimisation via Thompson sampling. In International conference on artificial intel- ligence and statistics, pp. 133-142. Proceedings Machine Learning Research, 2018. URL
mlr press Kaaa4//kaaaaaa11aa2 html
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. URL
6980
Johannes Kirschner, Mojmir Mutny, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. Adap- tive and safe Bayesian optimization in high dimensions via one-dimensional subspaces. In In- ternational Conference on Machine Learning, pp. 3429-3438. Proceedings of Machine Learning Research, 2019. URL https://axxx org/ abs/ 190119911... 03229
Wouter Kool, Herke van Hoof, and Max Welling. Buy REINFORCE samples, get a baseline for free! In International Conference on Learning Representations 2019 Deep Reinforcement net/
Learning meets Structured Prediction Workshop, 2019. URL
[
Agustinus Kristiadi, Felix Frieth-Kalthhoff, Marta Skreta, Pascal Poupart, Alán Aspuru-Guzik, and Geoff Pleiss. A sober look at LLMs for material discovery: Are they actually good for Bayesian optimization over molecules? In International Conference on Machine Learning, 2024. URL
hhttps://arxt org/ awarrg//////// 2402. 05015
Harold J Kushner. A new method of locating the maximum point of an ar- bitrary multipeak
curve in the presence of noise. Journal of Basic En- URL abstract/86/1/97/
gineering. 86,
1964.
asme Swm.::.rgg/.tuuueeennennnerrrrrr hta.ap/cee.eaiiiaaat..ooea/////r
392213/ New Met Locating the Maximum Pointoo--nn
redi redireeceerrmmfffullcc
Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoen-
coder. In International Conference Machine Learning, 2017. /tLpsttt:////....oo
abs/17033 01925
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predic-
tive uncertainty estimation using deep ensembles. Advances in Neural Information Processing Systems, 30, 2017. URL
/ abs /ates/11222 612. 01474
Yann LeCun, Sumit Chopra, Raia Hadsell, Ranzato, Fujie Huang, et al. torial energy-based learning. Predicting structured data, 1(0), 2006. wttp//sgggeeeee../
A tu-
URL
Seunghun Lee, Jinyoung Park, Jaewon Chu, Minseo Yoon, and Hyunwoo J Kim. Latent Bayesian optimization via autoregressive normalizing flows. In International Conference on Learning Rep- 14889
resentations, 2025.
13

---

Published as a conference paper at ICLR 2026
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et Competition--evel code generation with AlphaCode. Science, 378(6624) 2022. URL https::/axxiv..ot abs/
2203. 0701.07814 07814
Gary Liu, Denise B Catacutan, Khushi Rathod, Kyle Swanson, Wengong Jin, Jody C Mohammed, Anush Chiappino- Saad A Syed, Meghan Fragis, Kenneth Rachwalski. et al. Deep learning- guided discovery of an antibiotic targeting Acinetobacter baumannii. Nature Chemical Biology, 19, 2023. URL https: www. nature............. com 0tt.://a...cleess1111-000------0 022-41559---200333-3
Xiaoyu Lu, Javier Gonzalez, Zhenwen Dai, and Neil D Lawrence. Structured variationally auto- encoded optimization. In International Conference Machine Learning, 2018. URL https:
//proceedings. mlr. wwwpsp/ws/sweeeeeeeee
html]
Nicolas Menet, Jonas Hübotter, Parnian Kassraie, and Andreas Krause. LITE: Efficiently estimating Gaussian probability of maximality. In International Conference on Artificial Intelligence and Statistics, volume 258, pp. 4906-5004. Proceedings of Machine Learning Research, 2025. URL
attps://arxias wttpvv.vvvv.../.vv. org/ abs / 13535
Elvis Nava, Mojmir Mutny, and Andreas Krause.
Diversified sampling for batched Bayesian op- timization with determinantal point processes. In International Conference Artificial Intelli- gence and Statistics, pp. 7031-7054. Proceedings of Machine Learning Research, 2022. URL.
bttps://arxiss org.
11665
Pascal Notin, José Miguel Hernández-Lobato and Yarin Gal. Improving black-box optimization in VAE latent space using decoder uncertainty. In Advances in Neural Information Processing Systems, 2021. URL
abs 2117.00000
Brendan O' DDnooguue and Tor Lattimore. Variational Bayesian optimistic sampling. In Neural Information Processing Systems, 2021. http::://ax....or/////a/.//
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Yang. Zach Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style. nigh-performance deep learning library, 2019. htth::::: //twxii..v.vv//////////.. org /1t...99..... 01703
Bojana Ranković and Philippe Schwaller. BoChemian: Large language model embeddings for Bayesian optimization of chemical reactions. In Neural Information Processing Systems 2023 Workshop on Adaptive Experimental Design and Active Learning in the Real World, 2023. URL net.
https://openreet
Bojana Ranković and Philippe Schwaller. GOLLuM: Gaussian process optimized reerrrnnnn
LLM finetuning through Bayesian optimization, 2025. URL htl.httpss////exi..oor wwtpwwwwwwwww.o.r///oo/o
2504.06265
Carl Edward Rasmussen and Christopher KI Williams. Gaussian Processes for Machine Learning. Springer, 2006.
ppf
Bernardino Comera-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 mod- els. Nature, 625(7995):468-47)) 2024. URL https:/ www. nature com/ conmarricles////// 841586-0033-6622--
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39, 2014. URL
2609
Daniel Russo and Benjamin Van Roy. An information-theorrtie analysis of Thompson sampling. Journal of Machine Learning Research, 17, 2016. URL httttttttp/t/ttte/ wwtp:/iwwwrggbbbbbpba
5341
14

---

Published as a conference paper at ICLR 2026
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on Thompson sampling. Foundations and Trends@ in Machine Learning, 11, 2018. URL https:
wwtxxi..rg/abbs//111 02038
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017. URL
Zhihong Shao, Peiyi Wang. Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. DeepSeckMath: Pushing the limits of mathe- matical reasoning in open language models, 2024.
wttp:/ioorrg/aa....o. abrgg//bs2442
03300
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning, 2010. URL htttptt//axxx/>>> www. 0ttp///b.///11.... 3995
Gustavo Sutter, Mohammed Abdulrahman, Hao Wang, Sriram Ganapathi Subramanian, Mare St- Aubin, Sharon O' Sullivan,, Lawrence Wan, Luis -aandovz-Sandvva,, Pascal Poupart, and Agusti- nus Kristiadi. Simplifying Bayesian optimization via in-context direct optimum sampling, 2025.
URL htttt:tt///xxiii/ org/ httrg//bb//550.22252 23913
Kevin Swersky, Yulia Rubanova, David Dohan, and Kevin Murphy, Amortized Bayesian optimiza- tion over discrete spaces. In Conference on Uncertainty in Artificial Intelligence. Proceedings of Machine Learning Research, 2020. URL https:/pproeeed.ngg mlr press/v124/
swersky20a. html
Jean Tarbouriech, Tor Lattimore, and Brendan O'Donoghue. Probabilistic inference in reinforce-
ment learning done right. In Neural Information Processing Systems, 2024. URL https:
7/arxiv. org. aba/abaaaa /2112211...0 13294
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-299 1933. URL hattps://wwn
jstor. aetto..org/stable/233222
Sanjay Vishwakarma, Francis Harkins, Siddharth Golecha, Vishal Sharathchandra Bajpe, Nicolas Dupuis, Luca Buratti, David Kremer, Ismael Faro, Ruchir Puri, and Juan Cruz-Benito. Qiskit Hu- manEval: An evaluation benchmark for quantum code generative models. In IEEE International Conference on Quantum Computing and Engineering, volume 1, pp. 1169-1176. IEEE, 2024.
URL htt.hhtsss//axxi...rrrrees abrr://bs/2446..222 14712
Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched large-scale Bayesian optimization in high-dimensional spaces. In International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, 2018 URL https:
erg/absi 1706. 01445
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Feitas. Bayesian op- timization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55, 2016. htt.hhtts:///rrtt org. abs 331..1942
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In International conference on machine learning. Proceedings of Machine Learning Research, 2022. URL http///axvvv... org/ wtwpgg//aaa./../a//ee/e///// 2203. 06176
Ronald J Williams.
Simple statistical gradient-followingg algoritth for connectionist reifforcmmmtttt learning. Machine learning, 8, 1992. URL http://://iinnksii.i..e.e 10. 1000000000999990000
coom/article.
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge. Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang. Jing Zhou, Jingren Zhou, Junyang Lin. Kai Dang. Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui
15

---

Published as a conference paper at ICLR 2026
Men, Ruize Gao, Shixuan Liu, Shuang Luo. Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang. Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yugiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. Qwen3 technical report, 2025. URL www.::ttps/..c..... /tte:///xxiii org/ abs /2005. 09388
Yanzhao Zhang, Mingxin Li, Dingkun Long, Xin Zhang, Huan Lin, Baosong Yang, Pengjun Xie, An Yang. Dayiheng Liu, Junyang Lin, Fei Huang, and Jingren Zhou. Qwen3 Embedding: Advancing text embedding and reranking through foundation models, 2025. URL https:
//arxiv.org// 2tlpaab///25551111
Brian Ziebart. Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy. Careeie Mellon University, 2010. URL https: / /wwww CS cmu, edu/
#22iebart/oubb1occiiono///eeeee whwpsa//ttttsssssbbbbbrree bziebbrrt........ pdf
16

---

Published as a conference paper at ICLR 2026
APPENDIX
A ADDITIONAL EXPERIMENTAL RESULTS
A.I COMPUTATIONAL COST OF TOSFIT
Bayesian optimization is designed to trade the number of evaluations of an expensive reward func- tion against the computationally demanding computation of the reward posterior. In this spirit, we emphasize sample efficiency the main consideration. Nevertheless, as measured in wall-clock time Table model fine-tuning only incurs a minor latency overhead (here 19%). As a result, despite more cost per round ToSFIT reaches higher reward scores at a fixed computational budget, i.e, it is computationally more efficient than all baselines (see Figure 7a).
Wall-clock time per step of fully-batched TOSFIT (b B 16) A100 GPU for Table 2:
Protein Search. The majority of the runtime is spent on candidate generation.
Autoregressive Generation 1.08 = 0.05
Model Fine-Tuning
GP Update 0.33 + 0.06 ms
TOSFIT 1.29 + 0.05
0.21 + 0.01
Note that in the fully-batched setting considered here all generations are both used to estimate VBOS gradients and provide observational feedback to the reward model. The 19% overhead observed Table / stems from the additional non-auto-regressive backward pass during model fine-tuning. This computational overhead results in fewer generated candidates at fixed budget.
A.2 GENERATION DIVERSITY
A common failure point of reward-based fine-tuning is diversity collapse of the policy, As can be ob- served in Figure 10, ACTOR CRITIC (Barto et al. 1983) is strongly at risk. In contrast, SOFT ACTOR CRITIC (Haamoja et al.) 2018) retains diversity by directly regularizing the loss with an additional entropy term. Similarly, the objective of ToSFIT contains the additional term V-2 n da. which can be understood as entropy regularization targeted toward underexplored regions where large. As shown in Figure [0 this results in highly robust diversity trajectories. Moreover, con- trast to constant entropy regularization, such an uncertainty exploration-exploitatii tradeoff increases diversity in case of large uncertainty, and decreases diversity given sufficient observations.
200
300
200
Actor Critic
Generation Entropy
150
Soft Actor Critic
400
150
ToSFTT
100
100
50
50
500
1000
500
1000
500
1000
Evaluations
# Evaluations
Evaluations
(a) FAQ Response Refinement
(b) Protein Search
(c) Quantum Circuit Design
Figure 10: ToSFIT directs exploration by incorporating uncertainty- aware entropy regularization
via Ex-re / 2 л.. oz]- It avoids the diversity collapse of ACTOR CRITIC and is more stable than SOFT ACTOR CRITIC (see Subfigure 10c). Moreover, by steering generation diversity with the reward uncertainty a., TISFIT enables both phases of exploration and phases of exploitation. Note that the behavior of each method yields distinct observation histories on top of loss discrepancies.
17

---

Published as a conference paper at ICLR 2026
A.3 LOSS AND RISK OF OVERFITTING
The loss function in TOSFIT is set to the negative VBOS objective, i.e., lower bound on max,ex Rg. contrast to training on fixed dataset, the loss function evolves during optimization as more data is observed. Thus, the optimization dynamics typically do not lead to a monotonous increase the objective, see Figure [T] Such non- non-stationarity leads incorrect gradient statistics for optimizers like Adam (Kingma & Ba 2013). Thus, adopt vanilla stochastic gradient descent. Moreover, in contrast to fixed dataset, there is no risk of overfitting the policy: the optimal policy the one that maximizes the VBOS objective, as proven in Theorem [ Indeed, both entropy regularization and uncertainty in the reward function are directly integrated into the loss. Overfitting of the reward surrogate μı or may still occur, but can mitigated by adopting ensembles or Gaussian processes.
100
Actor Critic
VBOS Objective
80
Soft Actor Critic
ToSFIT
60
40
20
500
1000
# Evaluations
Figure 11: Evolution of the VBOS ob- jective during Quantum Circuit Design using Qwen2.5-Codde--1.5.
B EXPERIMENTAL DETAILS
To ensure reproducibility, we provide the setup for each of the experiments in Section 5 All experiments conducted on compute nodes with AMD EPYC 7763 64-Core CPU, 2TB RAM, and an NVIDIA A100-SXM4 GPU (80GB), running on Red Hat Enterprise Linux 9.4 with CUDA 12.4. Our Pytorch-based code (Paszke et al., 2019) is provided at hhttss:/ com/ htt.t//p/ttooooo--eoeerooo sampling- fine- caneee-uunn tun www.innoo--ninn Ims] including experimental configuration files and environment file specifying the necessary packages and their versions.
B. BASELINES
For UNGUIDED GENERATION, we simply generate and evaluate candidates according to the hyperparameters detailed in Section
For POST-GENERATION TS, we first generate fixed candidate pool using the large lan- guage model with the same hyperparameters, where the pool size is set to the number of steps of Bayesian optimization. Then, we conduct standard Thompson sampling on the candidate subset using a Gaussian process surrogate model derived from the (deep) task-dependent embeddings.
For TOSFIT, we generate and evaluate candidates according to the same hyperparameters, but additionally follow Algorithm to perform weight updates for consistency between the policy and the surrogate reward model, the same Gaussian process in
TS.
The ACTOR CRITIC baseline follows TOSFIT, but maximizes E [pz] rather than V.
SOFT ACTOR CRITIC additionally adds entropy regularization to ACTOR CRITIC, i.e., maximizes a In T.). The hyperparameter is swept for each experimental setting.
E [4g
For the EVOLUTIONARY SEARCH baselines, we generate new candidates by selecting two parents in each round independently via tournament selection with tournament size 3 and applying a crossover and mutation operation. We only let the 10 fittest members of the population survive. The initial population has one entry that acts as an example for the desired format. For the three tasks considered, the initial entry is set to
FAQ: How do reset my password?
Q: How do I reset my password?
A: To reset your password, follow these steps:
Log in to your account (if you have access to the platform or service you' using).
18

---

Published as a conference paper at ICLR 2026
Locate the 'Forgot Password' 'Reset Password' link, usually found in the login form or menu. Enter your email address username associated with your account. Follow the instructions sent to your email (or the confi rmation screen).
Complete the password reset process by entering a new password and confirming it.
Submit the form to finalize the reset. you're unable to locate the "Forgot Password" option,
contact the support team for assistance.
qe. (0,
EVOLUTIONARY SEARCH (CHARACTER) applies crossover by cutting each parent in half at a uniformly chosen location and stitching the pieces together. Mutation is performed through random substitution (at rate 0.05 per position) of the characters of the candidate solution with a letter from the vocabulary
for Protein Search and one of the 95 printable ASCII characters for FAQ Response Refinement and Quantum Circuit Design. After substitution, random insertion & deletion of characters (at rate 0.01) performed.
EVOLUTIONARY SEARCH (LLM) performs crossover and mutation in context through instruction following of the subsequent system prompt
You are conducting evolutionary search in context. You are provided two candidate solutions. Propose new distinct solution by combining the candidate solutions and mutating the result. Your novel candidate solution must be enclosed by <candidate> </candidate>, Never repeat previous solutions. Your search space is over FAQ responses to the question "How do reset my password?". /no_think
[...] Your search space is over amino acid sequences, with each amino acid represented
single-letter code. /no_think
[...] Your search space is over 6-qubit Qiskit quantum circuits, already prepared with 'qc = (uantumCircuit())
Finally, FIBO implements Thompson sampling fully in context by attending list of evalu- ated candidate solutions, initially set to the same examples provided to EVOLUTIONARY SEARCH (LLM). The algorithm implements Thompson sampling by adopting the following system prompt:
You are conductinn ing Bayesian in context. You are provided list of candidate solutions and the rewards achieved by these solutions. Propose a new distinct
zation (Thompson sampling) fully
solution that maximizes the reward. Your novel candidate solution must be enclosed by <candidate> </candidate>, Never repeat previous solutions. Your search space is over FAQ responses to the question "How do I reset my password?". /no_think
[...] Your search space is over amino acid sequences, with each amino acid represented as a single-letter code. code./no_thin!
[...] Your search space is over 6-qubit Qiskit quantum circuits, already prepared with lqc QuantumCircuit
19

---

Published as a conference paper at ICLR 2026
B.2 EXPERIMENTAL DETAILS SHARED ACROSS EXPERIMENTS
ToSFIT requires minimal task-specific hyperparameter tuning. Across all experiments with Gaus- sian process reward model, a burn-in period of m = 16 steps is adopted and an exploration bonus of 4.0 is applied to the prior amplitude inferred via MI.M. The toise-to-ampliude ratio dar is al- ways set to 0.01, reflecting the absence of noise in the measurements, but ensuring stable inversion of the observation covariance matrix. Unless stated otherwise, the number of steps of gradient as- cent per step of Bayesian optimization, c, is fixed at 1 to maximize computational efficiency. To ensure stable estimation of VBOS gradients, the generation batch size B is always set to 16 with temperature set to 1.0. We conduct unbatched Bayesian optimization (b = 1) unless otherwise spec- ified. Learning rates are the only hyperparameters tuned per task: 1.0 x 10-7 for FAQ refinement, 1.0 x 10-5 for Protein Search, and 5.0 x 10-6 for Quantum Circuit Design. The baseline SOFT ACTOR CRITIC requires an additional entropy regularization coefficient as hyperparameter and is swept across {0.01, 0.1, 1.0, 10.0} for each experiment. We report on the best configuration.
Implementation Details of TOSFIT To reduce the memory overhead of TOSFIT compared to UNGUIDED GENERATION (and in light of Section A.3). we do not adopt parameter-wise optimiza- tion statistics (Kingma Ba 2015). Instead, we use vanilla stochastic gradient descent with fixed learning rate and without momentum. We do not store the gradients, but instead apply them di- rectly during the backward pass. Also, while we perform fully-batched auto-regressive generation, the forward & backward passes to compute 2 In (T;) are performed in unbatched fashion with checkpointing. This crucially brings down memory consumption with little impact on runtime. All experiments were run single NVIDIA A100 GPU with 80 Gigabytes of VRAM.
B.3 CHOICE OF HYPERPARAMETERS
As mentioned above, TOSFIT requires minimal task-specific hyperparameter tuning. Indeed, only the learning rate is tuned for each task, based on one-dimensional grid search with search loca- tions (5.0 x 10-5, 1.0 x 10-5 5.0 x 10-6, 1.0 x 10-6, 6.00 x 10-7, 2.0 x 10-7, 1.0 x 10-7,5.0 x 10-*3. Burn-in periods of E (4, 8, 16) were tried out with 16 being sufficiently large to en- sure stable marginal likelihood maximization, yet small enough to not significantly impact sam- ple efficiency due to delayed optimization. The exploration bonus was sweeped across the set (1.0, 4.0, 8.0, 16.0) on a toy task. A bonus of 4.0 provided the best trade-off between ex- ploration and exploitation, and generalized strong performance on the reported experiments. The number of steps of gradient ascent per step of Bayesian optimization, c, was kept to in order to minimize the computational overhead compared UNGUIDED GENERATION. For the generation batch size B, the values {4, 8, 16, 32, 64) were tried out. 16 was the smallest size where GPU uti- lization became acceptably large during auto-regressive generation. However, empirically B did not significantly impact the simple regret trajectories during Bayesian optimization, suggesting that could possibly be lowered for alternative models and/or hardware. The baseline SOFT ACTOR CRITIC requires an additional entropy regularization coefficient as hyperparameter and is swept across {0.01, 0.1, 1.0, 10.0) for each experimental setup.
B.4 FAQ REANEMENT
For TOSFIT, the ACTOR CRITICS, UNGUIDED GENERATION, and POST-GENERATION TS, we use the Bwen3-1.7B/Qwen33.
model with the system prompt You are helpful assistant. followed by the prompt Write an FAQ response to the question "How do I reset my password?". /no think. We adopt learning rate of 1.0--7/2.0E-7. As kernel features, we extract the first 256 entries of the Swen3-Embedding-00 -0.66 model (Zhang et al., 2025) with input set to the concatenation of prompt and response. We normalize the result to the unit sphere and add an additional constant entry to act as a bias. The reward is modeled as the alignment to the unknown ground-truth response To reset your password, go to the login page and click the "Forgot Password" link. Enter your registered email address, and we'll 'll send you instructions to create new password. Make sure to check your spam folder if you don't see the email within a few minutes., computed through the cosine similarity between the full
embeddings of the candidate and the ground-truth.
20

---

Published as a conference paper at ICLR 2026
B.5 PROTEIN SEARCH
For TOSFIT, the ACTOR CRITICS, UNGUIDED GENERATION, and POST-GENERATION TS, we use the ProtGPT2 model (Ferruz al. 2022 with initial token </endoftexi>> and learning rate of 1.0F-5. As kernel features, we normalize each 1280 dimensional token embedding of the generated sequence the unit sphere, average across the sequence length, normalize the result to the unit sphere, and add an additional constant 1 entry to act bias. The reward is set to the negative thermal instability index (Guruprasad et al. 1990) implemented in the BioPython library (Cock) al. 2009).
B.6 QUANTUM CIRCUIT DESIGN
For TOSFIT, the ACTOR CRITICS, UNGUIDED GENERATION, and POST-GENERATION TS, use the Qwen2.5-Coder- Sew.---Cooor--11//Qvee L.5B/Qwen.55CCmm C.dderr model (Hui et al. (004) prompted with fill-in- the-middle (Bavarian al. 2022) to generate Qiskit circuit et al. (0224):
<ifim prefixl>
def ()rcuit(): qc = QuantumCirauie (6)
< <lfim_suffixi>
return qc
qe = circuit ()
state = Statevector. from promminnstruutiio (qc)
fim miim_iiddlel>).
We adopt learning rate of 5.0E-6/L.0E-5. As kernel features, take all 210 two-qubit Pauli observables, which are efficiently simulated by quantum computers, and concatenate an additional code invalidity bit. If the code invalidity bit is set I, all other features set zero. Finally, we add a constant entry to act as a bias. The reward is set to the negative energy of the prepared state according to unknown Hamiltonian. The Hamiltonian is constructed through the following weighted linear combination of Pauli terms:
(ZIIIIII, -1.0)
(IZIIIII, 1.0)
(IIXIIII, -1.0)
(IIIYIII, -1.0)
(IIIIZZI, -1.0)
(IIIIXXI, -1.0)
(IZZIIII, -1.0)
(IIIIIIX, -0.5)
IIIZIIIX, -0.5).
Note that the Hamiltonian heavily features pnpepositiioninduciin X and Y operators and pair-wiet wise interaction terms, necessitating entanglement to reach the lowest energy state.
C STANDARDIZED RLOO Is GRPO
ToSFIT crucially relies on the score trick (Williams) 1992) for unbiased gradient estimation of the i.i.d.
VBOS objective (see Proposition I.. The generalized score trick states that for I; n
de Epwn [r(z, 0)] = E [(((z, E) d do (x)] ~ B (f(r,, 0) + E:) de
In x (x:),
where (xx00) 1r 0)/ In ( r(r, 0). Note that for unbiased estimation the free base- line ε IR can be chosen differently for each {I....,) as long as does not depend on Iz. One effective baseline that greatly reduces the variance is to set & = E f(z,, Kool et al. 2019), resulting in the 'Reinforce Leave One Out" (RLOO) advantage function B-I Ejz; f(z,, 0). As we show in Proposition 3, standardization of RLOO recovers the advantage function introduced by /Shoo al. (2024) for Group Relative Policy Optimization.
21

---

Published as a conference paper at ICLR 2026
Proposition 3. Consider the 'Reinforce Leave One Out' (Kool et al. 2019) advantage functitnn given by f; B-i f & for Li.d. samples f with j E {1..... B). Then the expected advantage is zero and unbiased estimator of the variance is F (n म- Lizh fi)². Moreover, standardizing RLOO results precisely in the udvantage function employed by Shuo et al. (2024) for 'Group Relutive Policy Optimization' (GRPO):
f B-1 E E3tt
P:
B E, f
1
B
En B Eiph f1)2
En
(fr. B E1
B
standurdized
GRPO
D CONSTANT-TIME GP INFERENCE
To ensure efficient runtime in scale settings and to integrate with deep neural features ó X Fd we consider Gaussian processes (GPs) with linear kernels over F (Rasmussen Williams, 2006). As we explain in the following, our implementation requires constant ((d)) memory and compute for conditioning on an observation, inferring posterior mean variance a point, and conducting marginal likelihood maximization. In contrast to straightforward implementation, does not increase with the number of past observations.
D.1 SETTING
Let R GP(v, A²%) with linear kernel kz. = ((z) for ó RR. Here, À E R., and E denote parameters of the prior. We assume that observations Ya of come with i.i.d. additive Gaussian noise, i.e., Yu ~ R2 + Xe for ε ~ (O0, (ooiee) independent across observations. Then, given batch of observations (Io, (0), the posterior GP takes the closed form
Pi = + 122'
22 (Kzo + to I. v);
(3)
8x,=/22 kz,z k (Ee0 Ior ks.
(4)
where Gnar Tnoise / denotes the noise to amplitude ratio and Exo X the observation covariance matrix.
D.2 CLOSED-FORM MLM
In our setup, the only free parameters are the global scale À E R4 and the global offset v E R. We avoid optimizing &aar E 2 due to (1) dual use for numerical stability the inverse of and analytical intractability of general marginal likelihood maximization. As prove in Proposition 4 in this setting the marginal data likelihood can be maximized efficiently in closed form.
Proposition 4. Let Y NE) Then for E R the (marginal) likelihood p(Y y) is maximized if
y 1 FETI and ptt
(9 10--or')7
D.3 BYPASSING THE COVARIANCE MATRIX
The conditioning on observations in Equations 3) and (4) well the closed-form marginal likelihood maximization outlined in Proposition both rely on computing, storing, and inverting the unscaled prior data covariance matrix Σ. Since Σ grows in trivial application of the closed formulas would prevent constant-time GP inference. However, for linear kernels, a computationally much more efficient form be exploited instead. Define $ = (0(I1) ... o(2.)) E dd
22

---

Published as a conference paper at ICLR 2026
Then, per the Sherman-Morrison. Morrison-Woodbrry Woodbury formula
x = (D" 1b + o (n)rte)
(1g - x= (D02 T + o aa
o
4- = ($4" + 0 onar la)
Φ. and
(5)
=.
La --- xp" -I- ppp
0 nar V
Note that the expression to the left of Equation 5 underlies the conditioning of the mean in Equa- tion and that the left-hand expression Equation (6) is used to condition the kernel Equa- tion Therefore, given Vr-l E I and Pyo, +1 E IRd computing Mar and lizzz according to Equations 3 and (4) can be performed in (dd) steps for any prior parameter-pair (v, A). Further- more, having additionally access to Voyo. 1 1 v21 E R allows performing closed-fron -fom marginal likelihood maximization according to Proposition 4 also in ((d²) steps. So, to avoid scaling in the number of past observations s, we only need to keep track v oyo. $1, yOyo. 1 1 and yō 11 during Bayesian optimization, i.e., while we add columns to & and new entries to yo and 1. For most of these terms, this is trivial. Only V requires again relying on -ormman-Moorioo---- -oooodrrr...rrr... i.e,
T =(DT" + o I+ )(z))(x)²)² new
=V (')(1) [+0(z) dce) T
Keeping track of these quantities requires (dd)) memory with each additional observation demand- ing (dd²) compute, validating our complexity claims.
E
PROOFS
Before diving into the individual proofs of the theorems and propositions introduced in the paper, take the opportunity to present proof sketches for the main results.
E.1 PROOF SKETCHES
Proposition We show concavity by deriving the Hessian of the VBOS objective, which is diagonal matrix with non-positive entries. To derive the unbiased estimator of the gradients, we apply the generalized score trick for reward functions that depend on the model parameters A.
Proposition After verifying convexity of f. we simply expand the definition of the Bregman divergence and use that V (ā) the VBOS objective on the probability simplex and known to lie in the relative interior.
cll for Lagrange multiplier c, since म is known to maximize
Theorem 1
We first use linearity of expectation and the law of total expectation individ- ually consider the expected instantaneous regret [| Rg [7']] at each time step. Next, we leverage the technical result from Corollary 2 established by prior work, to upper bound E|R" [76'] with V(** In contrast to previous analysis by TTrbbouricc et al. (0024). we in- corporate practical limitations of gradient-based objective maximization by replacing V( with Dr (rt #²) +')+ Vx*". Since xf follows n² in practice, and not म it is essential to have V(r))) instead of ((#") as an upper bound. Now, following previous analysis, we simplify ((='(((') - R22+ [7''
to Elog' / 222 In [?"] and apply the Cauchy-Schware Schwarz inequality to arrive at the product of
term that scales in VT and E E[ Whereas Tarbouriech et al. (2024) bound the latter based on the phoeon-hole principle, we instead bound it by the maximal information gain >T_ technique introduced by (Srinivas al. (2010) to analyze multi-arma bandits with correlated rewards.
23

---

Published as a conference paper at ICLR 2026
E.2 FORMAL PROOFS
Proposition 1. Consider the VBOS objective ((T²)- := Ex lua + 221n(11155) oz). The VBOS objective V is concave (strictly o 0 Vx) and its gradients are
V( Be-xo 114 -
- 26---116 (m
d mi db
-12 for E=
& E R is an arbitrary baseline and -v (u) = (221n(u) 1/
1/11111///uu// 12nn 2221n( as u -
Proof of Proposition D To show concavity, follow the proof of Proposition 4 in Menet et al. 2025 by noting that v' > 0 and considering the (diagonal) Hessian of V, where
Or, V(r) Pz o (o((222(LL/r))
(21m(1/ = us 22 (rz), and
0² Ör Dr
<0 ==
V(r) -0 2== (rx))
= x x
Note the use of the inverse function rule d concavity is even ensured. So, we only need show the formula for gradients. score trick, which states that
Lu'
(a) = 1/ t ((b))bboo)(a))
ba) In case OR 0 Va, strict
forgradientss We make use the
v))ly=x(()) f(. v)) y=x*(() d 4 E (f T (x)) Be-xo (e v) + y dr
d (w)
d9
Plugging in and using that E E [s nor 2) results in the desired expression:
(g T for any constant & E R (that neither depends on
da
ab ((TT) =E =B
(mz + 1 1n ox
Ox)
dla x de
2l((
d
E B
(1z v-l (T 0x)
d0
E B (1z - -
v (m
d In
d0
Proposition 2. Let a E | For the convex f(p) := := -xx PrO2 2 Pu. define the Bregman
divergence Do(p, q) f(v) - f(4) - (VI(4),p 4)- Then the Bregman divergence of any π
AIXI-1 from the maximizer क arg max V(p) given by Dz #) V( V(T)
Proof of Proposition We follow parts of the proof of Lemma 5 by Tarbouriech et al. (2024). First, recall from Equation the closed-form expression for मे u( or where is cumulative distribution function with e (u) = 1/V-2huu /-2 unu. Next, notice that due to being aØ_ v
(p=))) 0. and strictly convex (positive definite Hessian), i.e., the Bregman divergence is well-defined. Next, recall that V(p) = E. Putt + JxP= /-2 pav and thus (p)) (M, p) fp)). Since मे maximizes V and is in the relative interior of the simplex (the objective is concave and at the border its derivatives blow up), the
de cumulative distribution function one has dp. 22
As such, (p) is continuously-differemnn
conditions give c1 = (V( = ff( for some e E R. i.e., Vf(=) = μ cll and thus V(T)) = (VS(a), m) - ((() + e. Plugging into V=#) V(T) then gives precisely the definition of D #).
Theorem 1. Let R N(u, K) with Ke, 1 E X and additive observation noise N(0, of R observed at x' T² for policy n' depending history H., then
EI - Ryd S VC,, HTTT + Da
4/Inn1 + ;,, is constant, H = (T is the expected average entropy of the policy and hence upper bounded by In |X|, 1- == max T(Yr;; R) is the maximum information gain for T observation locations 1.. and #t is the unconstrained maximizer of VBOS given H'.
*The theorem also holds for heteroscedastic additive Gaussian noise by replacing on with maxzex (n(x).
24

---

Published as a conference paper at ICLR 2026
Proof of Theorem 7 First, note that if R is multivariate Gaussian, then for 74 the history of ob- servations at step t, R' = R(H,' is also a multivariate Gaussian Vt. Next, we leverage Corollary to upper bound the regret
E R²
Rxi E, BiE[ Rz [7'']
$ E, E[V(#*)((*) Eytnarl [1211
E, E[V(TT (+t) + Do (T', #²) Bew [ [7']]
E, E 0r / 2n n' (x*))( + D (x', **)].
Note the application of Proposition 2 which allows us to bound the cumulative regret even the policy n' differs from the one suggested by VBOS, i.e., #t. Next, we use the Cauchy-Schwee inequality as well as Lemma uncover the dependency on maximum information gain, a measure of the complexity of the kernel. We get
Σ, E -2n
SV Ee E E Eed In( (2))
E E0 [?(")
E.
s E, H Com
Lemma (Donsker-Varadhan Varadhan variational representation). Fix two probability distributions Σ [0, and q - [0, 1] over the measurable space (S,, Σ) such that p is absolutely continuous with respect to (p & q). Then
DKL|plla] [uup[E,|X]] In En eexp X]},
X
where the supremum is laken over all measurable X - R such that [x[X] and Eglexp X] are well-defined.
Proof. The provided proof is a generalization of Theorem 3.2 by Gray (2011) from discrete spaces to arbitrary probability spaces. Since p < q, there exists a Radon-Nykodym derivative dy
2y (w)), i.e.,
holds p(A) .A dg (w)dq(w) for function dg (w) uniquely defined up set of q-measure zero. Now, let : > IR be any random variable such that E,,, [X] and (exp X] are well-defined. Then
dp (w:) - Ep [In
exp X
DRL(Plla]- [E) - (exp X1)) =Ep
dg
B.g /exp X
dp
(w) Eg [exp_
-In
dq
exp(X)
dp
-EE [In
d) DKupplAA 2 0,
where we defined the probability measure X(A) SA exp(X(())) (x))) / lexp X]dg(w), substituted [exp X] (xp(X)
dA
a and simplified the derivatives.
Lemma 2 (Conditioned KL-divergence). Consider the probability space (2, E, PP) and an event E of non-zero probubility, i.e. P[B] > 0. Then
DrL [P[ [8] P| P[B).
Proof. The proof follows Menet al. 2025
According the definition of conditional expectation
it holds
P[An n 8
/
LEE P(
PLA [3]
dIP(w)
YA
P[
where we recognize absolute continuity IP[ |B] < P and identify the Radon-Nykodym derivative
dPl
B
(w)
1ee8 Plugging the derivative into the definition of Bullback-Leible divergence
P(B]
25

---

Published as a conference paper at ICLR 2026
results in the desired term:
dPP
[3]]
DKL Pl.
[8]
P]
=
In
dP[
[3]
dP
0
dP
[8]
dIP
[B]
dP
dP
1 B
11 WEB
In(
dP
P(
P[]]
In PP
Definition 1.
The (Cramér) rate function A of a random variable X S2 I. is defined as the convex conjugate of the cumulant generaling function A, i.e.
(²)a) 03 A(3) where A(3) == In Ejee(XX-EI
850
Lemma 3 (Upper bound conditional expectation). Let X Ω + R be random variable on (S2, P) such that the (restricted) cumulant generating function
Rt + [0, o0) +
In E [Be ([X])) exists. Assume further that P O such that PP [BB is well-defined. Then with A the Cramer rate function of X (see Definition T it holds that
X 8 < E[X] + (- 1n ((8))
Proof. The provided proof is an adaptation of Lemma 11 by Tarbouriech al. (2024). We apply Lemma I with p( = | and q(E) = P[E). and restrict the supremum over just the random
variables {X(X [X))AER; This gives
1 ž sup {ΛE[x - E[X] B] In Elexp((AA - EX)I
XER
sup(A [3] B[X]) A(A) AE
[E[ E[X])
Furthermore, since À R+ it follows that A is strictly increasing and thus admits strictly increas- ing inverse, i.e.,
(DxL Il P)) > [[ - [[
As final step, Lemma which states that D [P IP] In IPB).
Corollary (Upper bound on Gaussian conditional expectation). Let X N o²) and P[B] 0. Then
B BB 1 + =
Proof. Since X (N, o²), it has cumulant generating function A(B) = B2 and (Cramér) rate function A s² (207) with inverse (A) 22. Plugging into Lemma results in the desired expression.
Corollary 2. Let R Nu, K) with a. / Knn Define R max, R2 and p" P(RR. R*). Then
E[R*] v(p")
max V(p). PEAIXI-1
Proof. The proof is direct consequence of Corollary
E = Σ. p ER = R*] < EnPia + -aa--2llm -2
26

---

Published as a conference paper at ICLR 2026
RI be multivariate Gaussian with øR, V/ X that is consec- utively evaluated at locations L == (x²)²= with observations Y8 = Rg + cz. The independent noise is distributed as ex (0, for) , on Vx E X. Then the maximum information gain 7² upper bounds the aggregated predictive variances at the locations, i.e.
Lemma 4. R:
max 1(Y R2) 2 In(l+o
o Rt-1.
=1/Can
Proof. The proof generalizes that of SSiinias al. (2010) from homoscedastic heteroscedastic noise. First, note that the expression on the right hand side is well-defined, because OR'=1 only
depends the observation locations I.T,, but on the observed value. Next, note that YL R is multivariate normal with independent components of variance of (x+), (s=)),..,,"))) (x (,), thus
I(2;; R) = =r - H [R]
=( 1/ Σ In(2Teo
Furthermore, may decompose
H[rr] H[{[.=]]]]]]] +| [{r=
[[[]m + (n(e (x")
o ( )),
using that YgT LY is Gaussian with variance a (x²" + oz
Recursively expanding then results
in
T(Y Rt = = In(1 + o ( Rg))
Finally, by assumption g E [0, 1). allowing lower bound each summand
o he S 1/ In(1 + (2))) in(1+02(at))
=Coote
Indeed, the inequality is tight for oe E [0, 1] and holds in-between due to concavity of
of my In(1 2 (29)) Rag In(1 + oz
Proposition 3. Consider the 'Reinforce Leave One Out' (Kool et al. 2019) advantage function given
by fi B-T Ejtt f for i...d. samples ij with j E (1, (1,.... ; B3. Then the expected advantage is
and an unbiased estimator of the variance 1 B Σn (fr, B-j Eith f.) Moreover. standardizing
RLOO results precisely in the advantage function employed by Shao et al. (0024) for 'Group Relative Policy Optimization' (GRPO):
f:
Ejti
A: 1 E3 F3
En J Eith 12)
B En (fr. 1o2 A2
standurdized RLDO
GRPO
Proof of Proposition 3 With linearity of the expectation and f
3.i.d. ~
p(f), the expected advantage
0 Vi. From the same two properties, an unbiased estimator of the variance of the advantage also follows:
Elf, 3ー Ej - -
E En (fr B Eign. - =E((f) -ー Eith f1) 02
=Var(f. F-Σ Ejd; fy].
27

---

Published as a conference paper at ICLR 2026
Finally, simple algebra results in equivalence between variancee-regularrized RLOO and GRPO:
f. 1 B-1 Ej P3
(Bf, (Bt--E,))/(BB1)
V B (Pn B-I Exph f1)2
B En ((BP) - Ei, 1))² B (A: - -,,
V 1 2 En (fn - Ei
E
En B A))
Proposition 4. Let Y N(v, X) and (I,...,1)T R'. Then for y E IR, the (marginal)
likelihood p(Y = v) is maximized if
1 and Xope PET
1) oot
Proof of Proposition f For y al, we get papt = a and Xopt = 0, i... Y = al and P|Y = y] 1, which is clearly optimal. So, w.l.o.g. assume y * 1. Since p(y) is a smooth function of E R, E R,, and because for any y oe 1 it holds that ply) + 0 as v + too or À + {0, oo), it suffices to consider the first-order conditions find the maximizers. With Lemma providing the gradients, the closed-form solutions follow swiftly. For v we have
2lmp(y) = 2 w1)² =
Likewise, for À we get
dA - 21mp(y)
= - -/ (1
- - (1- (v--1)/1
= = (y- (y- =0
Lemma 5. Let N Exp with á = (Φ) (#1.... pm) and 1/- (1/1,..., Un). Then
-2mm((y) = in | + (y-Hu)) ( + const.
Moreover, its gradients with respect to Φ; are
22 - m2) Eit do.
us
(8)
and its gradients with respect to R); are
Tr((2:) - - (v (w) )) daps E.).
(9)
Proof of Lemma S Equation follows immediately by taking the logarithm of the multivariate
normal probability density function, given by
p(y)
((21)TEal exp(- - -mo) (Y - 22)
Equation 8 follows from Equation since
d
2 Inp((v) = Tr(E d (y u²)(y) )T)
dø;
dØ:
=-2T((Eid (y - (1)) dØ: wT)
-22 : d
do p4:
28

---

Published as a conference paper at ICLR 2026
where we have used symmetry of Eg. in the last step. Likewise, Equation 9 tion (7) through the following chain of equalities:
results from Equa-
d
d 21n((y) (2 2v) Tr(
diti 2n pb) mb)
díb
deps
-Tr(2') Ex - -2x
x-1 (2r 1b - 1²)
dijs
dv'
Ev. Σng (y - (o) (y ub) TE/ dEe
-Tr(Ex))
dips
dips
=Ir((_# - Σn (y ( (E (v 1b))²) d di
Ex);
dM where we have used that de |M] |M] Tr(M d M) and that M M
M for M
du
de
-alued function of as well as symmetry of x.g.
F
USE OF LARGE LANGUAGE MODELS
Large language models used aid and polish writing, in particular by giving feedback on the clarity of this paper, and to a minor extent for retrieval and discovery (i.e., finding related work). No large language model generated content was directly included without further adjustments.
29


Reviews:
[{"review_id": "MVKuVsgMDJ", "reviewer": "Reviewer_UTrs", "summary": "This paper proposes a variational Bayesian optimization surrogate (VBOS) objective that provides a tighter bound for Thompson sampling–based optimization. The method enables gradient-based fine-tuning of generative models under non-differentiable and expensive reward functions.", "questions": "Following the weakness\n- For the given tasks, if apply RL methods such as PPO/GRPO, what would be the results? How your methods be better than RL? (or how your methods are correlated with RL?)\n- What is the diversity measure during the fine-tuning? Do you have mode-collapse problem?\n- How to select the convergence point, if I have enough computation resources?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper presents an interesting and theoretically grounded idea. The VBOS formulation provides a principled way to incorporate uncertainty into generative model fine-tuning for non-differentiable rewards. The theoretical analysis is sound and detailed.", "weaknesses": "- GP: The paper relies on the assumption that the underlying reward follows a Gaussian process prior. Will this be held for discrete or highly non-smooth reward functions?\n- Baselines: while the paper focuses on Bayesian optimization–based baselines, it omits comparisons with standard reinforcement learning (RL) methods such as PPO/GRPO, which can also handle non-differentiable rewards to fine-tune LLMs. (Are there any reasons that PPO/GRPO is not able to be used here?) Empirically, I can see VBOS adds an uncertainty term $\\sigma_x$; however, such comparisons would be crucial to demonstrate that the exploration term can contribute beyond simple reward-based fine-tuning.\n- Diversity measure: Reward-based fine-tuning sometimes leads to diversity collapse to a narrow high-reward set. Since the proposed VBOS objective explicitly includes an uncertainty term that should encourage exploration, it would be valuable to report how diversity changes during optimization.\n- Performance convergence: In Figure 4, ToSEiF appears to achieve higher rewards given the same computational cost. However, it is unclear when the fine-tuning process converges. If I have enough resources, when to stop the fine-tuning? Could the authors provide more complete curves, extending beyond the current range, potentially into regions where ToSEiF’s performance even declines (perhaps in the appendix)? This would help readers better understand the convergence behavior and overall stability of the optimization process.", "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": "unWRDHN2OG", "reviewer": "Reviewer_c3Vs", "summary": "This paper tackles the prohibitive cost of Bayesian optimization (BO) in large, unstructured discrete spaces. The authors’ key move is to eliminate expensive acquisition-function maximization over huge domains by directly sampling the next candidate from a parameterized distribution that approximates the posterior probability of maximality (PoM). They instantiate Thompson Sampling as fine-tuning a large language model (tagged TOSFIT) using a prompt-conditioned, pre-trained LLM that is carefully adapted toward PoM. The work builds on Variational Bayesian Optimistic Sampling (VBOS; O’Donoghue & Lattimore, 2021), but particularly strengthens it; they reformulate the analysis to yield a structure-aware regret bound (in terms of information gain) and extend it to approximate VBOS, which directly motivates TOSFIT’s emphasis on pre-trained policy initialization and cautious, PoM-aligned adaptation.", "questions": "1. Regarding the choice of $c = 1$ for the fine tuning update, can the authors provide more detail on the compute versus performance trade off?\n2. What guided the selection of baselines? Are there other established methods for combinatorial or discrete BO that were considered but not included? A brief rationale for the baseline set would be helpful.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is well motivated by both the challenges of BO in large discrete settings and the limitations of existing approaches. The authors demonstrate a solid command of the literature.\n\n2. The algorithm is well argued and clearly presented. Although the work builds on VBOS, the authors provide clear theoretical reformulations and insight driven analysis that justify the development of TOSFIT.\n\n3. The experiments show clear performance gains over the chosen baselines.\n\n4. The mathematical assumptions, propositions, and theorems are clearly stated and organized in the main paper and the supplementary material.\n\n5. The scalability of the proposed methodology is well expounded, with clear guidelines for practice and future research directions.", "weaknesses": "1. The paper could give a clearer background on the core concept and regret formulations behind VBOS before introducing the intimate connection to UCB. While the adaptive UCB exploration bonus is central to the gradient formulation, the explicit bridge from VBOS to regret bounds could be surfaced earlier. VBOS exact regret bound via the optimistic set appears in Proposition 2, but new readers may struggle without an earlier signpost.\n\n2. Fine tuning uses one VBOS gradient ascent step per round $c = 1$. This keeps cost low, but it raises natural questions about the compute versus quality trade off if more steps are used in complex settings.\n\nMinor comment: The choice of a linear GP is well reasoned, but performance depends on the feature embedding. Using a fixed embedding in the experiments limits generalizability. The authors acknowledge this as future work and outline how to address it, which helps mitigate the concern.", "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": "i8VgrOF7oK", "reviewer": "Reviewer_YiCY", "summary": "This paper introduces TOSFIT, a scalable approach to Bayesian Optimization (BO) over large unstructured discrete domains. Instead of maximizing acquisition functions directly, the method parameterizes the probability of maximality (PoM) using a prompt-conditioned large language model (LLM). TOSFIT adapts the pre-trained policy toward the posterior PoM through online fine-tuning guided by a Variational Bayesian Optimistic Sampling (VBOS) objective. The paper derives new theoretical regret bounds that match those of standard Thompson Sampling (TS) and GP-UCB, extends the analysis to approximate VBOS, and demonstrates empirical gains in frequently-asked-questions (FAQ) response refinement, protein search, and quantum circuit design tasks.", "questions": "Please see Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper proposes a new bridge between BO and LLM, replacing acquisition maximization with posterior-aligned fine-tuning. The regret analysis is solid. In addition, TOSFIT consistently outperforms unguided LLM generation and static candidate-based TS.", "weaknesses": "1. While theoretically rigorous, some derivations (e.g., the gradient of VBOS and its concavity proof) are dense and may be inaccessible to a broader ICLR audience. A high-level intuition section would improve readability.\n2. The comparison is limited to two relatively weak baselines (unguided LLM and post-generation TS). More direct comparisons to in-context optimization or gradient-based RL fine-tuning (e.g., RLHF or FIBO) would strengthen empirical claims.\n3. It remains unclear whether performance improvements stem primarily from the fine-tuning process or from better use of GP-based uncertainty.\n4. Although the paper claims negligible overhead, it would be helpful to report absolute runtime and fine-tuning cost relative to BO iterations.", "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": "5hatffnKMv", "reviewer": "Reviewer_9Xyb", "summary": "This paper addresses Bayesian optimization in large unstructured discrete spaces by proposing ToSFiT (Thompson Sampling via Fine-Tuning), which parameterizes the probability of maximality (PoM) directly using large language models instead of performing expensive acquisition function maximization. The authors establish a novel regret bound for variational Thompson sampling that scales with the maximal information gain rather than the domain size, and demonstrate their approach on three diverse tasks: FAQ refinement, protein design, and quantum circuit optimization.", "questions": "- Why limit POST-GENERATION TS to 1000 candidates? What happens with 10k or 100k candidates with the same computational budget as ToSFiT?\n- All experiments use small models (1.5-1.7B parameters). How does this scale to larger models?\n- How does the method scale to longer sequence generation tasks?\n- When does TOSFIT fail? When the LLM prior is misaligned, is it possible that TOSFIT will perform worse than random search?\n- Have you considered using the LLM to propose multiple diverse candidates per forward pass (e.g., via beam search or sampling), which might improve the gradient estimator?\n- Could you use the GP uncertainty to modulate the learning rate or number of fine-tuning steps adaptively?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Addresses a genuine problem: acquisition function maximization in large discrete spaces is prohibitively expensive\n- The combination of pre-trained LLMs with principled Bayesian optimization is timely and well-motivated\n- The improved regret bound is a solid theoretical contribution that advances understanding of VBOS\n- Demonstrates the approach on three genuinely different domains (language, proteins, quantum circuits)", "weaknesses": "-  The performance of TOSFIT is fundamentally tied to the quality of the fixed feature map (i.e., the embeddings from a pre-trained model). If the pre-trained embeddings do not capture the features relevant to the reward function, the GP model may struggle, limiting the overall performance regardless of the policy optimization.\n- Missing comparisons to other recent LLM-based optimization methods (e.g., FIBO is discussed but not compared experimentally), VAE-based methods, or even simpler approaches like evolutionary strategies\n- Missing comparisons to other discrete optimization approaches (e.g., evolutionary methods, MCMC-based optimization)\n- Limited discussion of when you would vs. wouldn't use this method. When is the 19% overhead worth it vs. just generating more candidates?", "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)