Use Your INSTINCT: INSTruction optimization usIng Neural bandits Coupled with Transformers

Neural Network based bandits are shown to be an efficient mechanism but it is unclear whether a different surrogate function would not offer larger improvements. Similarly, more discussion about acquisition functions would be important. Overall, Authors choose one BO strategy, different than InstructZero and it is unclear whether it is better than any other, modern BO strategy, perhaps BORE TPE or evolutionary algorithms such as REA.

What is the main motivation behind using NN bandits for this problem instead of other BO methods?

The reason why we have used neural networks as the surrogate function and adopted the neural bandits-based BO strategy is because they (1) have been shown to be effective in optimizing sophisticated high-dimensional objective functions (Dai et al., 2022), and (2) allow us to leverage the strong expressive power of pre-trained transformers for instruction optimization.

Firstly, the neural bandits-based BO replaces the GP surrogate function with a neural network, which has been repeatedly shown to be effective in modeling complicated and high-dimensional objective functions. Secondly, the use of neural bandits allows us to stack an MLP on top of the hidden representation from a pre-trained transformer to perform the task of score prediction, which is used during instruction optimization. This paradigm for prediction tasks (hidden representation from pre-trained transformer + MLP) has been repeatedly proven successful (Radford et al., 2018; 2019), and our proposed INSTINCT algorithm allows us to adopt this successful paradigm for prediction tasks for instruction optimization. These are the unique and significant advantages offered by the neural network surrogate function and the neural bandits-based BO strategy we have adopted, compared with other modern BO strategies. We have also revised the paper to discuss these advantages of our method over the other BO strategies you have referenced (revised Appendix B.3).

Regarding the acquisition function, we have adopted the natural choice of the NeuralUCB acquisition function in our INSTINCT algorithm. It is indeed interesting to explore in future works whether other acquisition functions for neural bandits such as Neural Thompson sampling (NeuralTS) (Zhang et al., 2021) can bring further performance improvements as you have suggested.

↓↓↓ Continue below ↓↓↓

"The empirical evaluation is limited to optimizing instructions for a single black-box LLM (ChatGPT) and a single white-box LLM (Vicuna). Testing on more LLMs would strengthen the results."

As you suggested, we have added experiments using multiple combinations of different white-box and black-box LLMs (using the instruction induction tasks in our main paper) and presented the results in Response Table 1 below. The results show that our INSTINCT algorithm remains effective under different combinations of white-box and black-box LLMs. Specifically, we have considered 2 white-box LLMs: Vicuna and WizardLM [1], and 3 black-box LLMs: GPT3.5, GPT4, and PaLM2 [2]. We have fixed the number of soft tokens to 3 and used the validation set to perform a grid search over the intrinsic dimension within {10, 50, 100} (see the first paragraph of Sec. 4 for more detail).

Response Table 1: Test accuracy on instruction induction tasks using different combinations of black-box and white-box LLMs.

In addition to showing that our INSTINCT algorithm performs consistently well across different combinations, the results in Response Table 1 also provide some additional interesting insights. Firstly, GPT4+Vicuna achieves the best performance followed by GPT4+WizardLM, which is reasonable because GPT4 is the state-of-the-art LLM. Secondly, using WizardLM as the white-box LLM in general leads to better performances than using Vicuna (i.e., GPT3.5+WizardLM is better than GPT3.5+Vicuna, and PaLM2+WizardLM is better than PaLM2+Vicuna), even though WizardLM and Vicuna have the same number of parameters (i.e., 13B). This can also be justified because it is corroborated by some LLM leaderboards [3, 4], in which WizardLM ranks higher than Vicuna. Thirdly, using GPT3.5 as the black-box LLM generally leads to better performances than using PaLM2 (which can be seen by comparing GPT3.5+Vicuna with PaLM2+Vicuna, and comparing GPT3.5+WizardLM with PaLM2+WizardLM), which is consistent with the LLM leaderboard in [5].

Thank you again for your detailed and insightful feedback. We hope our clarifications and additional results could improve your evaluation of our work.

[1] Xu, C., Sun, Q., Zheng, K., Geng, X., Zhao, P., Feng, J., ... & Jiang, D. (2023). Wizardlm: Empowering large language models to follow complex instructions. arXiv preprint arXiv:2304.12244.

[2] Anil, R., Dai, A. M., Firat, O., Johnson, M., Lepikhin, D., Passos, A., ... & Wu, Y. (2023). PaLM 2 technical report. arXiv preprint arXiv:2305.10403.

[3] Li, X., Zhang, T., Dubois, Y., Taori, R., Gulrajani, I., Guestrin, C., Liang, P. & Hashimoto, T. B. (2023). AlpacaEval: An Automatic Evaluator of Instruction-following Models [Computer software]. GitHub. https://github.com/tatsu-lab/alpaca_eval

[4] HuggingFaceH4 / open_llm_leaderboard. (2023). Spaces. Retrieved November 16, 2023, from https://huggingface.co/spaces/HuggingFaceH4/open_llm_leaderboard

[5] Chatbot Arena Leaderboard. (2023). Retrieved November 16, 2023, from https://lmsys.org/blog/2023-05-25-leaderboard/

"The authors explore the BO approach for prompt tuning but neglect the recent line of work of evolutionary methods ... for example PROMPTBREEDER ... how this strategy fares against others. I understand the paper I have references only came out recently"

Thank you for the suggestion and for pointing out the concurrent related work of PROMPTBREEDER. We have added reference to PROMPTBREEDER (Fernando et al., 2023) as a concurrent work, since as you have also mentioned, the paper only came out recently (only released on arixv on Sep 28). The code for PROMPTBREEDER has not been released yet and we have found it infeasible to implement the algorithm within the short rebuttal period. Therefore, we have instead added comparisons with another evolutionary algorithm-based concurrent work: EvoPrompt (Guo et al., 2023), which was released on arXiv only on Sep 15. The results (Response Table 7 below) show that our INSTINCT significantly outperforms the concurrent work of EvoPrompt, even though EvoPrompt requires more queries to ChatGPT (more details below).

Response Table 7: Additional comparison with EvoPrompt.

Response Table 7 shows that our INSTINCT consistently outperforms all baselines, including the concurrent work of EvoPrompt. In addition, note that EvoPrompt uses more queries to ChatGPT than our INSTINCT. This is because, in every iteration, Evoprompt needs to query ChatGPT to generate a new instruction and query ChatGPT again to obtain its score, whereas our INSTINCT only needs the latter query to ChatGPT (to obtain the score). Despite getting less feedback from the black-box LLM (i.e., ChatGPT), our INSTINCT still performs better than EvoPrompt. This is because our INSTINCT is based on neural bandits which is a global optimization algorithm that is able to utilize the historical data to efficiently balance exploration vs. exploitation. In contrast, EvoPrompt uses the evolutionary algorithm which is a local optimization algorithm that cannot utilize historical data to efficiently explore the global search space of instructions. Moreover, some other concurrent works on black-box methods for instruction optimization are based on similar core ideas as EvoPrompt, i.e., they also use a powerful LLM (e.g., ChatGPT) to propose new candidate instructions via rephrasing and use evolutionary algorithms for instruction optimization. Therefore, our performance advantage over the representative method of EvoPrompt is also likely to hold for the other black-box methods.

On the other hand, our INSTINCT is in fact not mutually exclusive with these methods that use LLM to generate instructions, in the sense that these methods can be incorporated into our INSTINCT algorithm to further improve our performance. Specifically, as a proof-of-concept experiment, in the last paragraph of Sec. 5 in our paper, we had proposed a method to further improve our INSTINCT via ChatGPT rephrasing (similar to the rephrasing approaches used in APE and EvoPrompt), and Figure 5 shows that this rephrasing method has further improved the performance of our INSTINCT.

↓↓↓ Continue below ↓↓↓

We would like to thank the reviewer for taking the time to review our paper and providing such a detailed and insightful review. We particularly appreciate the reviewer for acknowledging that we tackle an important and clear problem, that our paper is well-written and easy to follow, and that our experimental results are convincing and show consistent improvements.

"I would love to see how: increasing the dimensionality D of the soft prompt affects the accuracy of the downstream accuracy of the black-box LLM with the best prompt chosen based on D. This should be repeated for both normal GP based BO and the NN-bandits based BO to see how the curves change."

As suggested, we have added experiments to study the impact of the dimensionality of the soft prompt on both InstructZero (GP-based BO) and our INSTINCT (neural bandits-based BO). The results (Response Table 1) show that GP-based BO (InstructZero) suffers from monotonic performance degradation when the soft prompt dimensionality increases. In contrast, neural bandits-based BO (our INSTINCT) maintains comparable performances across different soft prompt dimensionalities.

Response Table 1: The fraction of tasks that one approach achieves the best performance among 30 instruction induction tasks under different soft prompt dimensionalities. Higher is better.

We additionally present the test accuracy on some specific tasks in Response Tables 2, 3, 4, 5, and 6 below. The results show that the performance of InstructZero declines significantly when the soft prompt dimensionality is 51200, whereas the performance of our INSTINCT remains consistent.

Response Table 2: Test accuracy on informal_to_formal under different soft prompt dimensionalities.

Response Table 3: Test accuracy on taxonomy_animal under different soft prompt dimensionalities.

Response Table 4: Test accuracy on word_sorting under different soft prompt dimensionalities.

Response Table 5: Test accuracy on word_unscrambling under different soft prompt dimensionalities.

Response Table 6: Test accuracy on negation under different soft prompt dimensionalities.

Thank you for the insightful suggestion. We have added these results to the revised version of our paper.

↓↓↓ Continue below ↓↓↓

Dear Reviewer fbJ6,

Thank you again for your time in reviewing our paper and for asking many valuable questions.

Please let us know if our replies have addressed your concerns. We would be happy to address any further questions you might have within the discussion period.

Best wishes,

Authors

Thank you very much for your appreciation of the depth of our rebuttal. We are happy to know that most of your concerns are addressed in our previous rebuttal. We would like to resolve the remaining one on comparison with other modern BO approaches as follows:

My main question of "Authors choose a BO strategy different than InstructZero and it is unclear whether (the one they chose) is better than any other, modern BO strategies" is not yet answered

We conduct additional experiments using other modern BO strategies: BORE and TuRBO [1] to modify the BO strategy used in InstructZero and show that our INSTINCT algorithm performs significantly better than BORE and TuRBO. Specifically, we further compare BORE and TuRBO which are two of the state-of-the-art modern BO strategies. Note that TPE is compared in BORE's paper and BORE outperforms TPE by a large margin and thus we will not compare TPE here.

Response Table 1: Test accuracy of the best instruction from different algorithms.

From Response Table 1, we can see that our INSTINCT algorithm performs the best and is significantly better than other BO strategies, i.e., InstructZero, InstructZero (BORE), InstructZero (TuRBO). Specifically, InstructZero (BORE) performs better than the original InstructZero, this is because BORE enjoys an improved expressiveness by casting the computation of EI as a binary classification problem and further uses an MLP as the classifier, and hence BORE is a better BO strategy in instruction optimization. Since the BORE paper already shows that BORE performs significantly better than TPE, we believe that our INSTINCT will also perform significantly better than TPE. InstructZero (TuRBO) performs slightly worse than InstructZero, this is because the InstructZero adopts the instruction-coupled kernel that uses the instruction scores to improve the kernel function which cannot be easily adopted by TuRBO.

Thank you for the insightful suggestion. We have added these results to Appendix J of the revised version of our paper. We hope our clarifications and additional results could improve your evaluation of our work.

[1] Eriksson, D., Pearce, M., Gardner, J., Turner, R. D., & Poloczek, M. (2019). Scalable global optimization via local Bayesian optimization. Advances in neural information processing systems, 32.

"I would like to see how the algorithm can optimize the instruction for black-box models from other families"

As we have discussed in our response above, we have added experiments using different combinations of white-box and black-box LLMs (Response Table 1 above), which include combinations where the white-box LLM is not distilled from the black-box LLM: The combinations of PaLM2+Vicuna and PaLM2+WizardLM. The results in Response Table 1 show that for these combinations, our INSTINCT algorithm is still able to find effective instructions with high scores. For example, the average ranking of PaLM2+WizardLM is better than GPT3.5+Vicuna and only slightly worse than GPT3.5+WizardLM. Therefore, these new experimental results suggest that our INSTINCT algorithm can generalize well across a wide range of combinations of white-box and black-box LLMs, not necessarily "from the same family".

"How many demos do you use for white-box LLM?"

For the instruction induction tasks and the text summarization task (Section 4.1), we have used 5 demos for the white-box LLM to generate the instructions, as shown in Figure 6 in our paper (page 14). For the chain-of-thought instruction optimization (Section 4.2), we have used 3 demos to generate new instructions as shown in Figure 9 in our paper (page 17).

Thank you again for your constructive feedback. We hope our additional results and clarifications could improve your opinion of our paper.

"Lack of the experiment on different combinations of white-box + black-box model"

As you suggested, we have added experiments using multiple combinations of different white-box and black-box LLMs (using the instruction induction tasks in our main paper) and presented the results in Response Table 1 below. The results show that our INSTINCT algorithm remains effective under different combinations of white-box and black-box LLMs. Specifically, we have considered 2 white-box LLMs: Vicuna and WizardLM [1], and 3 black-box LLMs: GPT3.5, GPT4, and PaLM2 [2]. We have fixed the number of soft tokens to 3 and used the validation set to perform a grid search over the intrinsic dimension within {10, 50, 100} (see the first paragraph of Sec. 4 for more detail).

Response Table 1: Test accuracy on instruction induction tasks using different combinations of black-box and white-box LLMs.

In addition to showing that our INSTINCT algorithm performs consistently well across different combinations, the results in Response Table 1 also provide some additional interesting insights. Firstly, GPT4+Vicuna achieves the best performance followed by GPT4+WizardLM, which is reasonable because GPT4 is the state-of-the-art LLM. Secondly, using WizardLM as the white-box LLM in general leads to better performances than using Vicuna (i.e., GPT3.5+WizardLM is better than GPT3.5+Vicuna, and PaLM2+WizardLM is better than PaLM2+Vicuna), even though WizardLM and Vicuna have the same number of parameters (i.e., 13B). This can also be justified because it is corroborated by some LLM leaderboards [3, 4], in which WizardLM ranks higher than Vicuna. Thirdly, using GPT3.5 as the black-box LLM generally leads to better performances than using PaLM2 (which can be seen by comparing GPT3.5+Vicuna with PaLM2+Vicuna, and comparing GPT3.5+WizardLM with PaLM2+WizardLM), which is consistent with the LLM leaderboard in [5].

[1] Xu, C., Sun, Q., Zheng, K., Geng, X., Zhao, P., Feng, J., ... & Jiang, D. (2023). Wizardlm: Empowering large language models to follow complex instructions. arXiv preprint arXiv:2304.12244.

[2] Anil, R., Dai, A. M., Firat, O., Johnson, M., Lepikhin, D., Passos, A., ... & Wu, Y. (2023). PaLM 2 technical report. arXiv preprint arXiv:2305.10403.

[3] Li, X., Zhang, T., Dubois, Y., Taori, R., Gulrajani, I., Guestrin, C., Liang, P. & Hashimoto, T. B. (2023). AlpacaEval: An Automatic Evaluator of Instruction-following Models [Computer software]. GitHub. https://github.com/tatsu-lab/alpaca_eval

[4] HuggingFaceH4 / open_llm_leaderboard. (2023). Spaces. Retrieved November 16, 2023, from https://huggingface.co/spaces/HuggingFaceH4/open_llm_leaderboard

[5] Chatbot Arena Leaderboard. (2023). Retrieved November 16, 2023, from https://lmsys.org/blog/2023-05-25-leaderboard/

↓↓↓ Continue below ↓↓↓

We would like to thank the reviewer for taking the time to review our paper and providing such a detailed and constructive review. We particularly appreciate the reviewer for acknowledging that our experiments are extensive and comprehensive and that our proposed method is efficacious in enhancing instruction optimization for black-box LLMs.

"Lack of the novelty: ... It seems that the idea is just a combination of InstructZero and NeuralUCB."

We would like to clarify that our idea is far more than just a combination of InstructZero and NeuralUCB.

Firstly, the strong expressive power of pre-trained transformers is a key reason behind the success of LLMs. However, how do we leverage the strong expressive power of pre-trained transformers for instruction optimization? This significant research question remained unanswered till our work, which not only proposed a theoretically grounded solution to achieve this but also empirically verified the resulting significant performance improvement through extensive experiments. Specifically, the use of neural bandits allows us to stack an MLP on top of the hidden representation from a pre-trained transformer to perform the task of score prediction, which is used during instruction optimization. This paradigm for prediction tasks (pre-trained transformer + MLP) has been repeatedly proven successful (Radford et al., 2018; 2019), and our proposed INSTINCT algorithm allows us to adopt this successful paradigm for prediction tasks for instruction optimization, which, to the best of our knowledge, was not possible before our work.

Secondly, from the perspective of the field of neural bandits, our proposed INSTINCT algorithm has also made important contributions to this field. Specifically, to the best of our knowledge, we are the first work (1) to couple neural bandits with the hidden representation from pre-trained transformers, and (2) to apply neural bandits to problems with such high-dimensional input spaces (the input dimensions in our experiments are in the range of 5120-51200).

Lastly, note that naively (1) coupling neural bandits with the hidden representation from pre-trained transformers and (2) applying neural bandits to such high-dimensional problems will lead to excessively high computational costs. In our work, we have overcome this technical challenge and hence made our algorithm computationally feasible through our proposed method of pre-computation, which is another novel and important contribution of our work (Sec. 3.2, the paragraph "Pre-Computation to Save Costs").

↓↓↓ Continue below ↓↓↓

Dear Reviewer 16Xs,

Thank you again for your time in reviewing our paper and for asking many valuable questions.

Please let us know if our replies have addressed your concerns. We would be happy to address any further questions you might have within the discussion period.

Best wishes,

Authors

Dear Reviewer 16Xs,

Today is the last day of rebuttal, and we are eager to know whether our responses have addressed your concerns. To summarize:

1. We compare all the combinations of white-box and black-box LLMs you have proposed and also other combinations of different LLM families to show that our INSTINCT remains effective.
2. We explain how our INSTINCT is far more than just a combination of InstructZero and NeuralUCB.

We are happy to address any further questions you might have before the rebuttal ends.

Best wishes,

Authors

"It would also be interesting to see this summary via performance profiles curves [1, 2], as they are computed over a decently large set of tasks"

Thank you very much for the suggestion and for providing the references. We have followed your suggestion to plot the performance profile curves of different algorithms (including the newly added baseline of EvoPrompt discussed in our response above): See https://postimg.cc/McjLP25P (or the same figure at https://pasteboard.co/fvgFXjDuvZ1t.png as backup). The figure shows that the performance profile curves indeed make it much easier to distinguish the performances of the baselines of APE and InstructZero, and more importantly, the performance profile curves also make it easier to visualize the performance superiority of our INSTINCT algorithm. For ease of reference, we summarize the performance profile curves in Response Table 4 below for your convenience:

Response Table 4: $\rho(\tau)$ under different $\tau$ for all methods. Higher is better.

We explain here how we have plotted the performance profile curves following the references you have provided. To draw the performance profile curve for a method, for each task $i$, we check whether the performance of this method in task $i$ is within $\tau$ distance to the best performance (among different methods) in task $i$, and hence define an indicator function $\mathbb{I}()$. Next, we average this indicator function across all $n_p$ tasks, which yields a value $\rho(\tau)$ (see equation below). Finally, the performance profile curve for this method is obtained by varying the value of $\tau$ and calculating the corresponding $\rho(\tau)$.

$\rho(\tau) = \frac{\sum_{i=1}^{n_p}\mathbb{I}\bigl((\text{Best performance in task } i - \text{Performance of this method in task } i) \le \tau \bigl)}{n_p}.$

We have added the performance profile curves as Figure 16 in our revised paper, and will add the figure to the main paper in our future revision. Thank you again for the insightful and helpful suggestion.

Thank you again for your encouraging and insightful feedback. We hope our clarifications and additional results could help improve your evaluation of our work.

"Only compared to two baselines: APE and InstructZero. I do see that this is addressed in Section 6 -- but can any of the black-box methods be adapted to your setting in some simple way?"

To further demonstrate our superior performance over other black-box methods, we have added another comparison with a concurrent work (released on arXiv only on Sep 15, 2023): EvoPrompt (Guo et al., 2023) which is based on evolutionary algorithms. The results (Response Table 3 below) show that our INSTINCT significantly outperforms the concurrent work of EvoPrompt, even though EvoPrompt requires more queries to ChatGPT (more details below).

Response Table 3: Test accuracy of the best instructions from different algorithms.

Response Table 3 shows that our INSTINCT consistently outperforms all baselines, including the concurrent work of EvoPrompt. In addition, note that EvoPrompt uses more queries to ChatGPT than our INSTINCT. This is because, in every iteration, Evoprompt needs to query ChatGPT to generate a new instruction and query ChatGPT again to obtain its score, whereas our INSTINCT only needs the latter query to ChatGPT (to obtain the score). Despite getting less feedback from the black-box LLM (i.e., ChatGPT), our INSTINCT still performs better than EvoPrompt. This is because our INSTINCT is based on neural bandits which is a global optimization algorithm that is able to utilize the historical data to efficiently balance exploration vs. exploitation. In contrast, EvoPrompt uses the evolutionary algorithm which is a local optimization algorithm that cannot utilize historical data to efficiently explore the global search space of instructions. Moreover, some other concurrent works on black-box methods for instruction optimization are based on similar core ideas as EvoPrompt, i.e., they also use a powerful LLM (e.g., ChatGPT) to propose new candidate instructions via rephrasing and use evolutionary algorithms for instruction optimization. Therefore, our performance advantage over the representative method of EvoPrompt is also likely to hold for the other black-box methods.

On the other hand, our INSTINCT is in fact not mutually exclusive with these methods that use LLM to generate instructions, in the sense that these methods can be incorporated into our INSTINCT algorithm to further improve our performance. Specifically, as a proof-of-concept experiment, in the last paragraph of Sec. 5 in our paper, we had proposed a method to further improve our INSTINCT via ChatGPT rephrasing (similar to the rephrasing approaches used in APE and EvoPrompt), and Figure 5 shows that this rephrasing method has further improved the performance of our INSTINCT.

↓↓↓ Continue below ↓↓↓

We would like to thank the reviewer for taking the time to review our paper, and for appreciating that our work has solid contributions, solves a clear problem, and provides thorough evaluations.

"It is interesting that the method can be sped up via pre-computation. Can the authors demonstrate this speedup"

As suggested, we have conducted additional experiments to compare the running time of our INSTINCT algorithm with and without the pre-computation of the representations. The results (Response Table 1 below) show that the pre-computation dramatically reduces the running time of our INSTINCT algorithm.

Response Table 1: The running time (± standard error) of our INSTINCT algorithm with and without pre-computation. The results are averaged on 20 instruction induction tasks in Table 1 of our paper.

In Response Table 1 above, "Without pre-computation" is the baseline whose only difference with our INSTINCT algorithm is that this baseline uses forward passes to compute every hidden representation in each iteration, and "INSTINCT (with pre-computation)" is our algorithm. The first column in Response Table 1 (165 iterations, same as the experiments in our paper) shows that pre-computation drastically reduces the running time of our INSTINCT algorithm from 78 mins to 29 mins. In addition, Response Table 1 also shows that in tasks that require more iterations, the pre-computation brings even more significant speed-ups. This is because as the number of iterations increases, the cost of pre-computation is further amortized across more iterations, which makes the computational savings offered by pre-computation more pronounced.

We agree with the reviewer that the added empirical evaluation of the computational costs (Response Table 1) can further strengthen the contribution of our method of pre-computation. Thank you for pointing this out, and we will add the results and discussions here to the revised paper.

"Can the authors provide an empirical comparison between the computation costs involved with running INSTINCT compared to its baselines? Ideally for the sake of a fair evaluation, this should also include pre-computation."

As suggested, we have performed additional experiments to empirically compare the running time of InstructZero and our INSTINCT. The results (Response Table 2 below) show that our INSTINCT has comparable computational costs with InstructZero.

Response Table 2: The running time (± standard error) of InstructZero and our INSTINCT. The results are averaged over the 20 instruction induction tasks in Table 1 of our paper.

Response Table 2 shows that the running time of the two algorithms are on the same scale. Our INSTINCT is slightly slower than InstructZero due to the use of the neural network and the pre-computation of the transformer representations. However, with this slight increase in the computational cost, our INSTINCT has achieved significantly better performances than InstructZero as demonstrated in Tables 1, 2, 3, and 4 of our paper. Moreover, as we have shown in our response above (Response Table 1), the method of pre-computation is crucial for our INSTINCT to achieve a comparable computational cost with InstructZero, and the benefit of the pre-computation becomes more significant as a larger query budget is adopted. This further demonstrates the importance of the contribution of our method of pre-computation, and we will also add the results and discussions here to the paper after revision.

↓↓↓ Continue below ↓↓↓

Dear Reviewer zDza,

Thank you again for your time in reviewing our paper and for asking many valuable questions.

Please let us know if our replies have addressed your concerns. We would be happy to address any further questions you might have within the discussion period.

Best wishes,

Authors

Thanks for the thorough response and the additional analyses! These additional results are convincing to me and address all of the comments that I had, so I am happy to raise my score to an 8.

"If paraphrasing indeed improves instructions, is the optimization process still necessary?" and "a more straightforward approach would be to initially generate a rudimentary base instruction ... and then refine it through repeated paraphrasing."

We would like to thank the reviewer for pointing out the insights on utilizing paraphrasing and proposing a straightforward approach with repeated rephrasing. Interestingly, your proposed approach coincides with the main idea of the baseline of APE (explained in Sec. 6). We have extensively compared our INSTINCT with APE and shown that our INSTINCT consistently outperforms APE. Specifically, the baseline APE performs instruction optimization using the core idea of iterative paraphrasing. APE starts with LLM-generated initial candidate instructions and generates multiple candidates using ChatGPT paraphrasing. After that, APE evaluates the performances of all candidates and keeps the best one while discarding the others. This process is repeated for multiple iterations to find the best instruction. Figure 1, Table 1 and Table 4 in our paper show that our INSTINCT performs significantly better than APE which is based on paraphrasing. We will revise our paper to clearly describe APE in the first paragraph of the Experiments section (Sec. 4).

The reason why our INSTINCT is better than the paraphrasing-based approach is that our INSTINCT is a global optimization algorithm while the paraphrasing-based approach is a local optimization algorithm. Specifically, our INSTINCT uses neural bandits which utilizes the historical queries to proactively control the exploration-exploitation trade-off and hence can find the global optimum efficiently (i.e., using a small number of queries). In contrast, the paraphrasing-based approach is a local search algorithm that is not able to effectively balance the exploration-exploitation trade-off, as a result, it is unable to efficiently traverse the global search space of instructions and hence cannot find the global optimum efficiently. Therefore, the optimization process is still necessary for achieving the best performance.

Thank you again for your time and your careful feedback. We hope our clarifications and additional results could improve your opinion of our work.

"An interesting baseline for the author to consider might be utilizing these Sobol sequences to create instructions and selecting the best one."

As clarified in our response above, we select 40 initial queries using the Sobol sequence to generate 40 instructions, and then evaluate these 40 instructions using ChatGPT to obtain their scores. To see how much our INSTINCT algorithm outperforms the initial Sobol sequence, we show in Response Table 1 below (in terms of test accuracy) that our INSTINCT algorithm significantly improves over the best instruction among these 40 initial instructions selected using the initial Sobel sequence. Note that validation accuracy (not test accuracy reported in the table) is the metric used during instruction optimization, which explains why in a few tasks, the best instruction among the 40 initial instructions has a higher test accuracy than our INSTINCT algorithm.

Response Table 1: Test accuracy of the best instruction generated by 40 random points from the Sobol sequence and the instruction generated by INSTINCT.

It is natural for one to ask: How does our INSTINCT compare to a pure random exploration baseline which spends all its 165 query budget using a Sobol sequence? We have conducted further experiments to demonstrate below in Response Table 2 that our INSTINCT consistently outperforms this pure exploration baseline. This is because our INSTINCT effectively balances exploration vs. exploitation during the optimization process.

Response Table 2: Test accuracy of the best instruction generated by 165 iterations of random selection from the Sobol sequence (same as the total evaluation budget) and the instruction generated by INSTINCT.

↓↓↓ Continue below ↓↓↓

We would like to thank the reviewer for taking the time to review our paper, for appreciating our contributions and acknowledging the novelty of our approach, and particularly for highlighting the strengths of our paper in terms of clarity of writing.

"It appears that the MLP on top of the pre-trained model remains unchanged, with its parameters being pre-determined using 1000 pairs of vectors and score."

We would like to clarify that in our algorithm, the MLP on top of the pre-trained model is changed (re-trained) after every iteration and we do not pre-determine the parameters of the MLP using 1000 vector-score pairs. We explain in more detail below.

As illustrated in Figure 2 of our paper, in each iteration, we select the soft prompt $z_t$ by maximizing the acquisition function (step 2), use $z_t$ to generate the instruction $\rho_t$ (step 3), and evaluate the score of this instruction $\rho_t$ to produce a score $h_t$ (step 4 and 5). After that, we add the hidden representation $z'_t$ of the soft prompt $z_t$ and the score $h_t$ into the training dataset of the MLP to form a new dataset, and use this new dataset to retrain the MLP. Therefore, our MLP is changed (re-trained) after every iteration.

As for pre-training the MLP using the initial dataset, we, in fact, use 40 (instead of 1000) pairs of vectors and scores as the initial dataset (selected using a Sobol sequence) to pre-train the MLP, and subsequently use our algorithm to select further queries (as described above). More specifically, we construct the initial dataset by selecting 40 initial queries (soft prompts) using a Sobol sequence and evaluating these 40 soft prompts using ChatGPT to obtain their scores, after which we use these 40 vector-score pairs to pre-train the MLP. Given that our overall query budget is only 165, we subsequently use our algorithm to sequentially select the remaining 165-40=125 queries, during which we re-train the MLP after every iteration (as described above).

↓↓↓ Continue below ↓↓↓

Dear Reviewer TRUy,

Thank you again for your time in reviewing our paper and for asking many valuable questions.

Please let us know if our replies have addressed your concerns. We would be happy to address any further questions you might have within the discussion period.

Best wishes,

Authors

Dear Reviewer TRUy,

Today is the last day of rebuttal, and we are eager to know whether our responses have addressed your concerns. To summarize:

1. We conduct additional experiments to show our INSTINCT improves significantly over random Sobol sequences.
2. We compare with the paraphrasing-based algorithm (our INSTINCT is much better) and explain why our optimization process is still necessary.

We are happy to address any further questions you might have before the rebuttal ends.

Best wishes,

Authors