A Sequential Optimal Learning Approach
to Automated Prompt Engineering in Large Language Models

Large Language Models (LLMs) demonstrate exceptional capabilities in following instructions, making them a powerful tool to various downstream tasks [31, 20, 2, 30]. A well-designed prompt steers an LLM to generate desired responses, enabling effective adaptation to downstream applications without incurring the high cost of fine-tuning the model weights. Nevertheless, creating effective prompts can be challenging due to the sensitivity of LLM outputs to prompt variations [32, 21, 38]. In addition, manually identifying ideal prompts is often time-consuming and lacks systematic guidance. Automated approaches to designing, optimizing, and refining LLM prompts mitigate this challenge by minimizing the need for manual intervention.

Recent efforts in automated prompt engineering primarily have focused on iterative evaluation and refinement in order to converge to ideal prompts [12, 39, 28, 27, 35]. The methods by these studies often assume the availability of numerous iterations. However, in many real-world scenarios, opportunities to evaluate prompts are limited, as each prompt evaluation is costly or time-consuming. For example, in medical research, each prompt evaluation could involve extensive time and resources from medical professionals, making it impractical to test a large number of variations before selecting the final one.

Moreover, many existing approaches search over a set of precrafted candidate prompts for ideal prompts [33, 39, 22] These methods require identifying and enumerating a set of prompts, which restricts the scalability as the candidate set expands. Furthermore, it fails to utilize the correlation among similar prompt to expedite the learning.

To fully unlock the potential of LLMs across diverse scenarios, it is crucial to develop an automated prompting framework that is capable of capturing dependencies among prompts and efficiently identifying high-performing prompts within few evaluations. This paper presents a principled forward-looking iterative process for automated prompt engineering through the optimal design of a sequence of prompts.

We propose an interpretable feature-based approach to prompt representation. Various categorical or numerical features can be considered to characterize detailed aspects of a prompt, such as the selection and ordering of demonstrative examples. Previous works identify factors within a prompt that influence the LLM outputs but often treat these aspects in isolation. We allow for capturing various interactions among prompt attributes and can accommodate potential constraints on the features. This feature-based prompt representation enables the inclusion and exploration of a vast and diverse set of prompts, which, unlike previous approaches, do not require manual prompt provision. In addition, in contrast to prompt descriptions based on embedding vectors, our representation is inherently interpretable.

We adopt a Bayesian approach to refine beliefs about the influence of prompt features on the LLM response. This approach supports the integration of prior knowledge and user opinions as well as enabling to capture feature correlations. To operationalize this, we define a probabilistic model to link prompt features to a response quality of interest. In this paper, we demonstrate our approach using LLM response accuracy as the primary quality metric.

Next, we formalize the iterative process of automated prompt engineering in the presence of limitations on the number of prompt evaluations as a sequential decision-making problem. Given the limited opportunities for prompt evaluation, this problem falls into the category of finite-horizon discrete-time Markov decision processes; see [29]. An optimal learning policy sequentially selects a feasible prompt representation for evaluation, aiming to maximize the expected outcome of the final prompt. Due to the potentially large prompt feature space, the curse of dimensionality [25] hinders the exact computation of the optimal prompt selection. We adopt an approximate policy for the optimal learning problems, known as the expected improvement policy in [4, 5] or Knowledge-Gradient (KG) policy in [9, 26]. This is a forward-looking policy that maximizes the expected improvement in the value of information in each learning phase. The KG policy often excels in practical scenarios with limited evaluation budgets, frequently outperforming common static data acquisition strategies and dynamic test-and-learn policies. For the consistency of the KG policy, see [10] for correlated features and [14] for constrained search space.

The large space of prompt candidates, defined by constrained features, makes it impractical to enumerate all feasible alternatives for determining KG decisions. To address this challenge, we leverage recent advancements in scalable optimal learning and KG computation. In contrast to earlier results to compute KG decisions [9] based on enumeration of all feasible alternatives, recent computational methods [24, 14, 6] build on optimal quantization of the response probability followed by mixed-integer conic optimization reformulations to leverage efficient optimization solution methods. For optimal learning problems with larger feature spaces, an iterative process involving solving mixed-integer linear optimization problems is employed to achieve even greater computational efficiency and scalability.

Our framework allows for different prompt representations and selection policies, hence encompassing various existing methods for automated prompt engineering. For example, when a small, finite set of precrafted prompt templates is provided and a point-wise utility model is used, our setting simplifies to the setup in [22, 39, 33].

We assess the performance of sequential prompt learning with adaptive prompt selection policies on a dataset of instruction induction tasks [15]. This benchmark dataset contains 24 instances of instruction induction, designed for LLMs to deduce implicit tasks or instructions from language prompts including answers or contextual information. For the instruction induction tasks, we first propose a feature-based prompt template and use the accuracy of responses collected from GPT-3.5 on the validation data as the primary performance metric. For the prompt selection, we evaluate the KG policy, the adaptive myopic policy, the increasingly popular Thompson sampling policy, and a number of other automated prompt engineering methods such as EvoPrompt [12] using an evolutionary algorithm to refine prompts and TRIPLE [33] using a multi-armed bandit approach to select prompts.

Our analyses show the effectiveness of our approach particularly with the KG prompt selection policy, which is capable to converge to high-quality prompts within 30 or fewer prompt evaluations. These prompts significantly outperform those generated by the benchmarks on the test data using the same number of LLM interactions. Further analysis reveals that the KG policy is particularly favorable for challenging tasks with high uncertainty in LLM responses and significant sensitivity to prompts, achieving a substantial margin over baseline policies. Our findings highlight the advantages of using the KG policy in prompt engineering to selectively evaluate prompts, expanding the potential for deploying automated prompt engineering in applications with large prompt evaluation costs.

Our contributions can be summarized as follows.

• •

  We introduce a sequential optimal learning framework for automated prompt engineering to guide through the process of designing a sequence of prompts that effectively elicit accurate responses from an LLM. The approach is particularly effective for applications where prompt evaluation is resource-intensive.

• •

  We propose a feature-based approach to represent language prompts, which greatly expands the prompt search space. A link function maps the features to LLM response accuracy through Bayesian model parameters to leverage correlations among prompts with shared characteristics. Our method enables simultaneous optimization of multiple features to generate improved prompts.

• •

  We leverage the KG policy within our sequential prompt learning to efficiently identify high-performing prompts in large prompt spaces. The KG policy outperforms various benchmark policies, especially for challenging tasks with high uncertainty in LLM response.

The remainder of the paper is organized as follows: Section 2 reviews the related literature. Section 3 discusses the generic iterative process for automated prompt learning, formalizing the problem as a sequential decision making problem. Section 4 discusses the forward-looking KG policy for the prompt selection in iterative automated prompting. Illustrative examples and computational results are provided in Sections 5 and 6. Finally, conclusions and potential extensions are discussed in Section 7.

We introduce a sequential optimal prompt learning framework, called SOPL, for automated prompt engineering that is compatible with black-box LLMs and generates human-readable prompts, while addressing the challenge of limited number of iterations for prompt evaluation. Our framework, depicted in Figure 1, follows the iterative process outlined in Algorithm 1. The components of the framework are explained in the subsequent subsections.

We consider a forward-looking optimal learning policy designed to maximize the expected improvement in an approximated value of information during each iteration. This approach, known as the Knowledge-Gradient (KG) policy, offers an approximate solution to the MDP for prompt selection. For additional discussion and analysis, refer to [13, 5, 11, 26]. The value of information is measured by the expected single-period improvement, i.e., the difference between the values of the knowledge states $S_{n+1}$ and $S_{n}$ if the prompt representation $x_{n+1}=x$ is selected. Hence, at iteration $n$, the following KG quantity is maximized:

where $V_{N}(S)$ is the value of the optimal policy at iteration $N$ for any knowledge state $S$, i.e., $V_{N}(S)=\max_{\pi\in\Pi}V_{N}^{\pi}(S)=\max_{x\in\mathcal{X}}\mathbb{E}[\eta_{x}|S]$, where $\eta_{x}$ is as in equation (1). Recall that $S_{n+1}$ is the transition from state $S_{n}$ induced by the updating procedure in equations (4)-(7). The quantity $\nu_{x}^{n}$ is the marginal value of one more prompt representation $x$ being queried. Its value is always nonnegative.

The decision of the KG policy selects the prompt representation that maximizes the KG quantity in equation (11):

For discussion on the related concepts of asymptotic optimality and statistical consistency of the KG policy, the reader is referred to [11, 10] when $\mathcal{X}$ is specified in the enumerative form, and see [14] when $\mathcal{X}$ is represented in a constraint-based form.

For any $x\in\mathcal{X}$, the KG quanitity corresponding to model (1) is given by:

where $T_{2a_{n}}$ follows a student’s t distribution with $2a_{n}$ degrees of freedom, and

The expectation in equation (13) is with respect to the one-dimensional random variable $T_{2a_{n}}$.

The first term in the KG quantity in equation (13) can be approximated by

where $t_{1},...,t_{J}\in\mathbb{R}$ is the sequence of points that minimizes the quadratic quantization error of the Voronoi quantizer for $T_{2a_{n}}$, $t_{0}=-\infty$, and $t_{J+1}=\infty$. The weights are defined as $w_{j}=F_{T_{2a_{n}}}\left(\frac{t_{j}+t_{j+1}}{2}\right)-F_{T_{2a_{n}}}\left(\frac{t_{j-1}+t_{j}}{2}\right)$ for $j=1,\cdots,J$. Here, $F_{T_{2a_{n}}}$ is the cumulative distribution function of $T_{2a_{n}}$. Therefore, the selected prompt representation based on the KG policy at state $S_{n}$ is computed by solving the following mixed-integer optimization problem:

Here, $m$ is the dimensionality of the prompt representation features, and $P_{n}:=\frac{a_{n}}{b_{n}}(\frac{A^{\top}A}{h^{\top}h}+\Sigma_{n}+\Sigma_{\Theta})$, where $A$ and $h$ form the equality constraints of the feasible set $\mathcal{X}=\{x|Ax=h,Bx\leq g\}$. In this problem, $\mathcal{X}^{+}$, consisting of elements $(x,\tau)\in\mathbb{R}^{m}$, represents the homogenized version of the set $\mathcal{X}$. In the last constraint, $M$ denotes a large constant. For further details and a computationally efficient iterative algorithm only involving solving mixed-integer programming problems to solve this problem, see Propositions 6 and 7 in [24].

We demonstrate the performance of the proposed SOPL framework on the instruction induction tasks [15]. The dataset consists of 24 individual tasks, covering various aspects of text comprehension. Each data point comprises a pair of input and output. For example, for the task larger_animal, one data point consists of an input “cougar, flea” and an output “cougar”. The objective is to find an instruction such that when the LLM is queried with the instruction and an input, its response matches the correct output. A possible instruction for this task can be “choose the larger animal”. Similar to [39], we generate possible instructions by prompting an LLM using a meta prompt, which consists of demonstrative examples of input-output pairs and asks for a possible instruction. For each task, we partition the dataset into three sets: a demonstration dataset, a validation dataset, and a held-out test dataset.

We focus on the 13 challenging tasks where the validation score are below 80% with relatively large variance using the default meta prompt template in [15]. Table 2 presents the average test performance across 13 tasks for SOPL and the benchmark approaches. For each task, we illustrate the mean and standard deviation of the test score across 20 replications in Figure 5. The results indicate that SOPL-KG outperforms the benchmarks. It exhibits the highest average test score of 0.6281 among all methods, with a 6.47% improvement in average test score and a 17.92% average improvement per task relative to EvoPrompt. For each task, we rank the five methods from the highest to the lowest test score, and calculate the average ranking across 13 tasks. The SOPL-KG achieves the highest average ranking of 1.85, and the SOPL-TS has the second best ranking of 2.69, outperforming both EvoPrompt and TRIPLE. We compute the standard deviation of the test scores across 20 replications for each task, and report the average across 13 tasks in Table 2. The SOPL-KG exhibits the lowest standard deviation, demonstrating its robustness to variations in random seeds.

The findings highlight the effectiveness of our proposed framework with feature-based prompt representations and the KG prompt selection policy in comparison to other benchmarks. Although the space of all feature combinations is prohibitively large for exhaustive exploration, the SOPL-KG is capable of discovering high-quality prompts within given prompt evaluations.

This paper introduces SOPL, a sequential optimal prompt learning framework for automated prompt engineering focused on efficient prompt learning in practical scenarios where exhaustive evaluation is costly or impossible. Specifically, we develop a feature-based approach to model prompts, enabling a constraint-based and expansive prompt search space. The forward-looking KG policy with correlated beliefs facilitates efficient and scalable prompt learning. We demonstrate that our proposed method achieves superior performance on instruction induction tasks with only 30 or fewer opportunities of prompt evaluation. We find that the KG policy yields substantial performance gains compared to baseline policies, especially for challenging tasks with high uncertainty. Moreover, our framework allows for future investigation of continuous representations of prompts by embedding vectors. Our work shows a promising direction of leveraging optimal learning methods for efficient prompt learning, paving the way for future research on scalable prompt engineering.

This research was supported in part through the computational resources and staff contributions provided for the Quest high performance computing facility at Northwestern University which is jointly supported by the Office of the Provost, the Office for Research, and Northwestern University Information Technology.