# Bayesian Optimization for Instruction Generation
## 3 Bayesian Optimization for Instruction Selection (BOInG)
Accounting also for \(\tau\), the final search space is \(\Omega^{\tau}\in\mathbb{R}^{q\times\tau}\); on the contrary, we want to identify a conveniently low-dimensional search space (\(\mathcal{P}\in\mathbb{R}^{d\times\tau}\)) to perform BO. As suggested in the recent literature, we use a random projection matrix (\(\mathbf{A}\in\mathbb{R}^{d\times q}\)), with entries sampled from a normal or uniform distribution to project any soft prompt (\(\mathbf{p}\)) from our conveniently low-dimensional search space (\(\mathcal{P}\)) into an associated point in the high-dimensional search space (\(\Omega^{\tau}\)). Thus, each \(d\)-dimensional token (\(\mathbf{p}_{[i]}\)) of the prompt (\(\mathbf{p}\)) is projected into an embedding (\(\mathbf{Ap}_{[i]}\)). Random projection is a quite common procedure known to be distance-preserving. However, the projection of the soft prompt is still not a hard prompt, which is, instead, needed as an input of the instruction generator (\(\mathcal{M}_{g}\)). It is important to remark that the embeddings of the tokens used to train \(\mathcal{M}_{g}\) all lie within the high-dimensional space (\(\Omega\)) and are denoted as set \(\mathcal{E}=\{\mathbf{e}_{i}\}_{i=1}^{|\mathbf{W}|}\), where \(\mathbf{e}_{i}=encode\big{(}W_{[i]}\big{)}\) and \(W_{[i]}=decode(\mathbf{e}_{i})\). Thus, the most naive strategy is to recast every projection (\(\mathbf{Ap}_{[i]}\)) into the closest \(\mathbf{e}_{j}\in\mathcal{E}\), then retrieve the associated token (\(W_{[j]}\)). This allows for the retrieval of a hard prompt (\(\mathbf{w}\in W^{\tau}\)) given the random projection of a given soft prompt (\(\mathbf{p}\in\mathcal{P}\)) the computation of the associated loss. Although this is a possible procedure, we later find that it can be largely ineffective. At a generic iteration (\(n\)) of BO, the trials (\(\mathbf{p}^{(1)},\dots,\mathbf{p}^{(n)}\)) and the associated losses (\(\mathcal{L}^{(1)},\dots,\mathcal{L}^{(n)}\)) are used to train a GP approximating a back-box and expensive loss function with respect to soft prompts (\(\mathbf{p}\)) in the low-dimensional space (\(\mathcal{P}\)). Selection of the  
Figure 5: Flow chart of a prompt optimization loop, starting with a hard prompt and small example set. The process involves instruction generation via closed-source LLMs (\(\mathcal{M}_{g}\)), prompt loss calculation using the \(\mathcal{M}_{g}\)’s generated output with as input for the generated instruction and training set, and Bayesian optimization. This cyclical workflow illustrates the generation of instructions in the BOTnG algorithm. next prompt to try (\(\mathbf{p}^{(n+1)}\)) is performed by optimizing an acquisition function balancing between exploration and exploitation. However, due to random projection induced by \(\mathbf{A}\), we are not sure that the projected point (\(\mathbf{Ap}\)) is \"consistent\" with the (embeddings of the) tokens known to \(\mathcal{M}_{g}\). In simpler terms, in a very high-dimensional space (\(\Omega\)), the projected point (\(\mathbf{Ap}_{[i]}\)) could be far away from the embedding of any token known to \(\mathcal{M}_{g}\), leading the LLM to generate incomprehensible and strange instructions that are difficult for \(\mathcal{M}_{s}\) to successively interpret. Indeed, we introduce a penalty function (\(\pi(\mathbf{p})\)) so that UCB is optimized while keeping all the projections (\(\mathbf{Ap}_{[i]}\)) associated with the soft prompt (\(\mathbf{p}\in\mathcal{P}\)) as close as possible to the embeddings of the tokens known to \(\mathcal{M}_{g}\). Our penalty function is defined as follows:  
\[\pi(\mathbf{p})=\frac{1}{\tau}\underset{i=1}{\overset{\tau}{\underset{i=1}{ \tau}}}\underset{e\in\mathcal{E}}{\min}\left\|\mathbf{Ap}_{[i]}-\mathbf{e}\right\| \tag{8}\]  
In more simple terms, \(\pi(\mathbf{p})\) is the average distance between each projection (\(\mathbf{Ap}_{[1]},\dots,\mathbf{Ap}_{[\tau]}\)) from the closest embedded tokens known to \(\mathcal{M}_{g}\).