This paper presents a Bayesian Optimization (BO) approach for prompt optimization in large language models (LLMs). Prompt optimization aims to select the optimal sequence of n-grams to enhance the performance of LLMs on downstream tasks. The problem is formulated as a combinatorial optimization task, where the search space consists of all possible prompts of a given length. However, exhaustive search is impractical due to the vast size of the search space, so a continuous relaxation of the combinatorial space is used to enable efficient sampling via BO. The proposed method applies BO to search for the optimal prompt in the space of n-grams, using a continuous relaxation of the discrete decision variables. This approach allows for efficient exploration and exploitation of the prompt space, leveraging the sample efficiency and modular structure of BO. The method is validated on six benchmark datasets, including MNLI, QQP, SST-2, MRPC, QNLI, and RTE. The results show that the proposed approach outperforms other black-box prompt optimization methods in terms of performance and efficiency. The approach is particularly effective for tasks where the LLM is available as a Model as a Service (MaaS), as it does not require access to the model's internal parameters. The method also reduces the wall-clock time required for prompt optimization, making it more practical for real-world applications. The paper also discusses the challenges of prompt optimization, including the combinatorial nature of the search space and the need for efficient search strategies. It highlights the importance of using Bayesian Optimization for black-box optimization, as it provides a sample-efficient and modular approach to the problem. The results demonstrate that the proposed method is effective in improving the performance of LLMs on various natural language understanding tasks, while maintaining a balance between accuracy, search space size, and computational cost. The approach is also aligned with the interests of final users, as it allows for the development of simple services without requiring access to the LLM's gradient information.This paper presents a Bayesian Optimization (BO) approach for prompt optimization in large language models (LLMs). Prompt optimization aims to select the optimal sequence of n-grams to enhance the performance of LLMs on downstream tasks. The problem is formulated as a combinatorial optimization task, where the search space consists of all possible prompts of a given length. However, exhaustive search is impractical due to the vast size of the search space, so a continuous relaxation of the combinatorial space is used to enable efficient sampling via BO. The proposed method applies BO to search for the optimal prompt in the space of n-grams, using a continuous relaxation of the discrete decision variables. This approach allows for efficient exploration and exploitation of the prompt space, leveraging the sample efficiency and modular structure of BO. The method is validated on six benchmark datasets, including MNLI, QQP, SST-2, MRPC, QNLI, and RTE. The results show that the proposed approach outperforms other black-box prompt optimization methods in terms of performance and efficiency. The approach is particularly effective for tasks where the LLM is available as a Model as a Service (MaaS), as it does not require access to the model's internal parameters. The method also reduces the wall-clock time required for prompt optimization, making it more practical for real-world applications. The paper also discusses the challenges of prompt optimization, including the combinatorial nature of the search space and the need for efficient search strategies. It highlights the importance of using Bayesian Optimization for black-box optimization, as it provides a sample-efficient and modular approach to the problem. The results demonstrate that the proposed method is effective in improving the performance of LLMs on various natural language understanding tasks, while maintaining a balance between accuracy, search space size, and computational cost. The approach is also aligned with the interests of final users, as it allows for the development of simple services without requiring access to the LLM's gradient information.