# Bayesian Optimization for Instruction Generation
## 3 Bayesian Optimization for Instruction Selection (BOInG)  
In this section, we detail our proposed approach, BOInG. First, we introduce some useful notations:  
\(\mathcal{M}_{g}\): The LLM working as instruction generator. It receives a hard prompt and a small set of examples \(\left((\overline{\mathbf{X}},\overline{\mathbf{Y}})\sim\mathcal{D}\right)\) as input and produces a text representing an instruction. \(\mathcal{M}_{s}\): The LLM working as solver for a certain task. It receives an instruction and a large set of input examples, that I, \(\mathbf{X}\) from \(\left(\mathbf{X},\mathbf{Y}\right)\sim\mathcal{D}\), as input and provides its own predictions (\(\mathbf{\hat{Y}}\approx\mathbf{Y}\)). \(\mathbf{w}\in W^{\tau}\): A hard prompt consisting of \(\tau\) tokens given as input to \(\mathcal{M}_{g}\), with \(W\), a vocabulary, preferably the one which \(\mathcal{M}_{g}\) has been trained on. \(\mathcal{E}=\{\mathbf{e}_{i}\}_{i=1}^{|W|}\): The set of the token embeddings such that \(\mathbf{e}_{i}=encode\Big{(}W_{[i]}\Big{)}\) and \(W_{[i]}=decode(\mathbf{e}_{i})\), where \(W_{[i]}\) represents the \(i\)-th token in the vocabulary (\(W\)). \(\mathbf{p}\in\mathcal{P}\subset\mathbb{R}^{d}\): A soft prompt in a convenient low-dimensional search space. We consider the same workflow as in InstructZero [14] and Instruct [15], that is, \(\mathcal{M}_{g}\) works as an instruction generator; then, \(\mathcal{M}_{s}\) works as a solver for a certain task by using the instruction generated by \(\mathcal{M}_{g}\). The workflow starts by injecting a hard prompt (\(\mathbf{w}\in W^{\tau}\)) into \(\mathcal{M}_{g}\), along with a small set of examples \(\left((\overline{\mathbf{X}},\overline{\mathbf{Y}})\sim\mathcal{D}\right)\). The generated instruction, denoted by \(\mathcal{M}_{g}\big{(}\mathbf{w}\oplus(\overline{\mathbf{X}},\overline{ \mathbf{Y}})\big{)}\), is given as input to \(\mathcal{M}_{s}\), along with a large set of input examples (\(\mathbf{X}\)) whose associated output (\(\mathbf{Y}\)) must be predicted. The symbol \(\bigoplus\) denotes the concatenation operator. The final aim is to efficiently search for  
\[\mathbf{w}^{*}\in\underset{\mathbf{w}\in W^{\tau}}{\operatorname{argmax}} \mathcal{L}\big{(}\mathbf{w};\mathcal{M}_{g},\mathcal{M}_{s},(\overline{ \mathbf{X}},\overline{\mathbf{Y}}),(\mathbf{X},\mathbf{Y})\big{)} \tag{6}\]with the loss function defined as follows:  
\[\mathcal{L}\big{(}\mathbf{w};\mathcal{M}_{g},\mathcal{M}_{s},(\mathbf{\overline{X }},\mathbf{\overline{Y}}),(\mathbf{X},\mathbf{Y})\big{)}=\frac{1}{N}{\sum_{i=1 }^{N}1_{y_{i}}}=\mathcal{M}_{s}\Big{(}\mathcal{M}_{g}\Big{(}\mathbf{w}\bigoplus (\mathbf{\overline{X}},\mathbf{\overline{Y}})\Big{)}\bigoplus\mathbf{x_{i}} \Big{)} \tag{7}\]  
where \(1_{a=b}\) denotes the _indicator function_ (equal to \(1\) if and only if \(a=b\) and \(0\) otherwise) and \(\mathcal{M}_{s}(\mathcal{M}_{g}\big{(}\mathbf{w}\bigoplus(\mathbf{\overline{X }},\mathbf{\overline{Y}})\big{)}\bigoplus\mathbf{x_{i}})\) is the output provided by the second LLM (\(\mathcal{M}_{s}\)), given the input (\(\mathbf{x}_{i}\)) and the generated instruction (\(\mathcal{M}_{g}\big{(}\mathbf{w}\bigoplus(\mathbf{\overline{X}},\mathbf{ \overline{Y}})\big{)}\)). The entire optimization process is summarized in Figure 5.  
Solving problem (6) is difficult due to the combinatorial nature of the search space, that is, \(W^{\tau}\). As already addressed in the recent literature, our idea is to, instead, use a soft prompt (\(\mathbf{p}\in\mathcal{P}\subset\mathbb{R}^{d\times\tau}\)), where \(\tau\) is the number of tokens and \(d\) is the dimensionality of the latent representation of each token. The most natural and suitable choice for the latent representation of the tokens should be \(\mathcal{M}_{g}\)'s embedding space (\(\Omega\in\mathbb{R}^{q}\)), which, unfortunately, is usually high-dimensional, i.e., \(q\gg d\).