SOPL : A Sequential Optimal Learning Approach to Automated Prompt Engineering in Large Language Models (2025)

Abstract: Designing effective prompts is essential to guiding large language models (LLMs) toward desired responses. Automated prompt engineering aims to reduce reliance on manual efforts by streamlining the design, refinement, and optimization of natural language prompts. This paper proposes an optimal learning framework for automated prompt engineering for black-box models, designed to sequentially identify effective prompt features under limited evaluation budgets. We introduce a feature-based method to express prompt templates, which significantly broadens the search space. Bayesian regression is employed to utilize correlations among similar prompts, accelerating the learning process. To efficiently explore the large space of prompt features, we adopt the forward-looking Knowledge-Gradient (KG) policy for sequential optimal learning efficiently by solving mixed-integer second-order cone optimization problems, making it scalable and capable of accommodating prompts characterized only through constraints. Our method significantly outperforms a set of benchmark strategies assessed on instruction induction tasks within limited iterations of prompt evaluations, showing the potential of optimal learning for efficient prompt learning.

## introduction recent efforts in automated prompt engineering have primarily focused on iterative evaluation and refinement to converge to ideal prompts @xcite @xcite @xcite . these methods often assume the availability of numerous iterations. however, in many real-world scenarios, opportunities to evaluate prompts are limited, as each prompt evaluation can be costly or time-consuming. for example, a company may use llms to generate blog posts promoting a new product. the narrative of each post may vary depending on the target audi-ence such as lawyers, computer engineers, or educators, and the choice of underlying advertisements included. the llm prompt should be carefully designed to incorporate these key aspects. the post is then evaluated based on user click-through rates. each evaluation is expensive as it requires users to visit the website and interact with the content. in such cases, the number of prompts that can be tested is very limited. moreover, many existing approaches search over a set of precrafted candidate prompts for ideal prompts @xcite @xcite . these methods require identifying and enumerating a set of prompts, which restricts the scalability as the candidate set expands. they also fail to utilize the correlation among similar prompts to expedite learning. to unlock the potential of llms in diverse scenarios, it is crucial to develop an automated prompting framework for black-box llms 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. a recent survey @xcite summarizes existing methods for organizing and selecting demonstrative examples, and @xcite propose a method for ordering in-context samples based on label distributions. 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 rep-resentation enables the inclusion and exploration of a vast and diverse set of prompts, which does 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. it supports the integration of prior knowledge and user opinions and enables the capture of 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 evaluation metric. we formalize the iterative process of automated prompt engineering for black-box llms under a limited number of prompt evaluations as a sequential decision-making problem. given limited opportunities for prompt evaluation, this problem falls into the category of finite-horizon discrete-time markov decision processes; see @xcite ). 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 (powell, 2022) 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 @xcite or knowledge-gradient (kg) policy in @xcite . 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, outperforming common static data acquisition strategies and dynamic test-and-learn policies. 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 @xcite based on enumeration of all feasible alternatives, recent computational methods @xcite @xcite build on optimal quantization of the response probability followed by mixed-integer conic optimization reformulations to leverage efficient optimization solu-tion 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 approach requires users to predefine a set of features and corresponding choices to construct the prompt search space. however, these manual efforts can be substantially reduced by leveraging llms to generate a set of choices for each feature. given the capability of the kg policy, our method can efficiently explore the resulting feature spaces. we assess the performance of sequential prompt learning with adaptive prompt selection policies on a variety of instances of instruction induction tasks @xcite , designed for llms to deduce implicit tasks or instructions. we use the accuracy of responses from gpt-3.5 on the validation data as the primary performance metric. we evaluate the performance of the kg policy in comparison with the adaptive myopic policy, the increasingly popular thompson sampling policy, and other automated prompt engineering methods such as evoprompt @xcite using an evolutionary algorithm to refine prompts and triple @xcite using a multi-armed bandit approach to select prompts. our results show that the kg policy consistently identifies high-quality prompts within 30 or fewer evaluations, outperforming benchmark methods. furthermore, kg is particularly effective for challenging tasks with high uncertainty and sensitivity to prompt variations, demonstrating its potential for scalable, cost-efficient automated prompt engineering. our code is available foot_0 and data details are provided in the appendix. our contributions can be summarized as follows. the paper is organized as follows. section 2 reviews the related literature. section 3 formalizes the generic iterative process for automated prompt learning. section 4 discusses the forward-looking kg policy for prompt selection. illustrative examples and computational results are provided in section 5. we conclude the paper in section 6. their method requires increasing evaluations as the candidate set grows, whereas our kg policy scales efficiently with larger spaces of prompts. edit-based methods several approaches refine prompts by iteratively editing base prompts. grips @xcite applies local text edits, while @xcite and @xcite use evolutionary algorithms with mutations and crossover operations performed by an llm. @xcite propose an iterative prompt refinement scheme specially crafted for relevance ranking in information retrieval. these methods rely on local search by modifying existing prompts. our method, however, performs forward-looking exploration using bayesian optimal learning. prompt learning methods recent studies @xcite apply bayesian optimization to explore the embedding space of prompts, requiring white-box access to llms, while we directly search in the space of discrete prompts and eliminate the need for white-box llms. rlprompt @xcite formulates prompt construction as a reinforcement learning problem, which requires extensive evaluations during training. in contrast, our framework learns efficiently under limited evaluation budgets. recent surveys provide comprehensive taxonomies of existing methods for automated prompt optimization @xcite . our work complements the literature by introducing a sequential optimal learning framework that leverages the value of information for efficient prompt engineering. ## sequential optimal prompt learning 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. we illustrate our method with examples from the instruction induction dataset @xcite , however, the framework is general and applicable to a wide variety of tasks. as an example task, the objective is to identify the most effective instruction for guiding an llm to infer the common theme among a given list of items. prompt effectiveness is measured by the accuracy on a labeled dataset, which contains input paired with their ground truth common themes. for example, given the input "lawyers, basketball, walled yards," the corresponding label "involves courts" captures their common concept. a simple instruction such as "find the common theme among the input words" may serve as an initial guess. however, exhaustively guessing and testing all possible variations quickly becomes intractable without a systematic way to represent prompts and leverage information from prior attempts. ## kg prompt selection policy 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 @xcite @xcite . 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. for kg, we assume that x is binary. hence, at iteration n, the following kg quantity is maximized: the decision of the kg policy selects the prompt representation that maximizes the kg quantity in (9) foot_1 : according to proposition 5 in @xcite , for any @xmath0, the kg quantity corresponding to model (1) is given by the expectation in (11) is with respect to the onedimensional random variable t 2an . here, f t 2an is the cumulative distribution function of t 2an . therefore, the selected prompt representation based on the kg policy at state s n is computed by solving the following mixed-integer optimization problem: ## computational experiments we demonstrate the performance of the proposed sopl framework on the instruction induction tasks @xcite with gpt 3.5 and allow @xmath1. the dataset consists of 24 tasks, covering various aspects of text comprehension. for each task, we partition the dataset into a demonstration set for creating prompts, a validation set for evaluating intermediate prompts, and a held-out test set for evaluating the final prompt. we focus on the 13 challenging tasks with validation scores below 80% and large variance using the default meta prompt template in @xcite . ## conclusion and future work this paper introduces sopl, a sequential optimal prompt learning framework for efficient automated prompt engineering when exhaustive evaluation is costly or impossible. we develop a feature-based approach to model an expansive prompt space. the kg policy with correlated beliefs facilitates efficient and scalable prompt learning. our method achieves superior performance on instruction induction tasks within 30 prompt evaluations, showing the potential of optimal learning methods for efficient prompt learning. future work may explore continuous prompt representations by embedding vectors using the sopl framework.