# Bayesian Optimization for Instruction Generation
## 3 Bayesian Optimization for Instruction Selection (BOInG)
Finally, \(\mathbf{p}^{(n+1)}\) is obtained as follows:  
\[\mathbf{p}^{(n+1)},\mathbf{w}^{(n+1)}\in\underset{\mathbf{p}\in\mathcal{P}}{ \operatorname{argmax}}\mu(\mathbf{p})+\beta\sigma(\mathbf{p})-C\pi(\mathbf{p}) \tag{9}\]  
where \(C\) is a regularization hyperparameter and \(\beta\) manages the exploration-exploitation trade-off. Indeed, the usual UCB is penalized by the quantity expressed as \(C\pi(\mathbf{p})\). It is important to remark that solving the penalized UCB requires computation of \(\pi(\mathbf{p})\); thus, we obtain \(\mathbf{p}^{(n+1)}\), along with the associated indices \((j^{*}_{i}=\underset{j=1,\dots,|W|}{\operatorname{argmin}}\left\|\mathbf{Ap} _{[i]}-\mathbf{e}_{j}\right\|)\) for each \(i=1,\dots,\tau\), from which we directly obtain the associated hard prompt (\(\mathbf{w}^{(n+1)}\)) such that \(\mathbf{w}^{(n+1)}_{i}=decode\Big{(}\mathbf{e}_{j^{*}_{i}}\Big{)}=W_{[j^{*}_{ i}]}\). This is crucial: we are searching in the conveniently low-dimensional search space (\(\mathcal{P}\)) but close to known embeddings, which is completely different form optimizing UCB \"freely\", then recasting \(\mathbf{p}^{(n+1)}\) to the closest embeddings a posteriori. In the second case, UCB could lead to a \(\mathbf{p}^{(n+1)}\) so far away from all the known tokens (due to the high dimensionality of \(\Omega^{\tau}\)) that recasting could be completely incoherent. Finally, knowing the embeddings of the tokens known to \(\mathcal{M}_{g}\) is the best option for the proposed approach; however, this requires \(\mathcal{M}_{g}\) to be a white-box model. To mitigate this request and give the chance to, instead, use powerful black-box LLMs, we decided to only adopt the embeddings of another white-box LLM-specifically, GPT2 in our case-under the assumption that the distances between embeddings should be coherent across different LLMs. GPT-3.5 Turbo is used in BOnG as an LLM. For each task, we use the following parameter settings: 5 and 20 samples from the training and validation sets, respectively. The number of tokens in every soft prompt is 5. The elements of the random projection matrix are sampled from a uniform distribution in \([-1,1]\). The value of \(d\) is set to 10, and 25 soft prompts are explored for each iteration. Finally, \(\beta=1\) and \(C=1\). We utilized an evolutionary search algorithm, namely \"_SampleReducingMCAcquisitionFunction_\", to find the top 25 soft prompts. All training and testing were performed on a 4-core machine equipped with an NVIDIA T4 GPU, which accelerated the matrix calculations necessary for determining the penalty (obtaining the embedding distances). The BOnG algorithm is summarized in the following (Algorithm 2). ```
Input: Examples \((\overline{\mathbf{X}},\overline{\mathbf{Y}})\), validation set \((\mathbf{X},\mathbf{Y})\), instruction generator LLM \(\mathcal{M}_{g}\), solver LLM \(\mathcal{M}_{s}\), maximal steps \(T\), the dimensionality \(d\) of the search space, number of tokens \(\tau\), vocabulary \(W\), embeddings set \(\mathcal{E}\ =\ \{\boldsymbol{e}_{i}\}_{i=1}^{|W|}\), random projection matrix \(\mathbf{A}\ \in\ \mathbb{R}^{d\times\ q}\).