Task Facet Learning: A Structured Approach to Prompt Optimization

## Abstract

Abstract Given a task in the form of a basic description and its training examples, prompt optimization is the problem of synthesizing the given information into a text prompt for a large language model (LLM). Humans solve this problem by also considering the different facets that define a task (e.g., counter-examples, explanations, analogies) and including them in the prompt. However, it is unclear whether existing algorithmic approaches, based on iteratively editing a given prompt or automatically selecting a few in-context examples, can cover the multiple facets required to solve a complex task. In this work, we view prompt optimization as that of learning multiple facets of a task from a set of training examples. We identify and exploit structure in the prompt optimization problem — first, we find that prompts can be broken down into loosely coupled semantic sections that have a relatively independent effect on the prompt’s performance; second, we cluster the input space and use clustered batches so that the optimization procedure can learn the different facets of a task across batches. The resulting algorithm, UniPrompt , consists of a generative model to generate initial candidates for each prompt section; and a feedback mechanism that aggregates suggested edits from multiple mini-batches into a conceptual description for the section. Empirical evaluation on multiple datasets and a real-world task shows that prompts generated using UniPrompt obtain higher accuracy than human-tuned prompts and those from state-of-the-art methods. In particular, our algorithm can generate long, complex prompts that existing methods are unable to generate. Code for UniPrompt will be available at https://aka.ms/uniprompt .

## 1 Introduction

Given a task, choosing an input prompt is a key part of optimizing Large Language Model’s (LLM) performance [, ]. Minor changes in prompt can lead to performance gains or losses, necessitating prompt engineering [] for effective model utilization. Typically, manually-developed prompts combine task description with a few in-context examples, along with modifiers like chain-of-thought []. For greater accuracy, human prompt engineers spend considerable time to identify errors with a current prompt, consider the different facets of a task (e.g., counter-examples, explanations, analogies) that may fix those errors, and include them in the prompt. For instance, for a hate speech classification task, in addition to the definition, it may be helpful to specify the facets that lead to hate speech: the context of conversation, identifying intent, and differentiating hate speech from opinions or closely-related concepts such as vulgarity and profanity.

To avoid the cumbersome process of manually creating prompts, recent work aims to automate the process of generating natural language prompts that are also interpretable. Since language tokens are discrete, this leads to a challenging discrete optimization problem with a combinatorial space of possible outputs. Techniques for prompt optimization can be divided in two categories: non-directional, e.g., random search [, ] and genetic algorithms [, ], where the sampling of new input is “random” and does not explicitly aim to reduce error on a train set; and directional, where the sampling of new input depends on some error measure on a representative train sample.
Recently, more complex methods are proposed in the second category including reinforcement learning [, ] and updating prompts using auxiliary LLMs to reduce incorrect predictions over a train sample [, ].
While all these techniques focus on editing, adding, or deleting parts of a given prompt, they are developed with the goal of obtaining a concise description of the task. None of them focus on ensuring that multiple facets of a task are added to the prompt.

In this paper, we study how to optimize prompts to cover diverse, multiple facets of a task and improve overall accuracy. To develop a suitable algorithm, we analyze properties of the prompt optimization problem. First, we check how sensitive LLMs are to small changes in the input prompt, since directional optimization algorithms may not be as useful if LLMs are highly sensitive. Using a notion of probabilistic Lipschitz continuity, we find that LLMs become less sensitive with size. Across prompt edits with the same semantic meaning, Llama-13B accuracy fluctuates up to 63% of the minimum accuracy whereas the relative accuracy change in GPT-3.5 and GPT-4 models is 6% and 4% respectively. As a result, probabilistic Lipschitz constant for GPT-3.5 and GPT-4 is significantly smaller than that for Llama-13B, indicating that directional optimization methods may be best suited for larger models. Second, we study how LLM accuracy changes as more information is added to the prompt. Ideally, we would want a diminishing marginal returns (sub-modularity) property so that greedy addition of different facets can lead to a reasonable approximation of the true optimum. We find that diminishing returns property largely holds when adding different facets as new sections to the prompt, but it does not hold when directly adding in-context examples.

Our analysis provides two insights: 1) directional optimization may be feasible for models like GPT-3.5 having a low probabilistic Lipschitz constant; 2) including facets as additional text sections may lead to a well-behaved optimization problem. Based on these, we propose an algorithm, UniPrompt, that can generate the full prompt from scratch, given a one line description for a task. Specifically, we identify a prompt structure that provides different task facets as sections in the prompt and initializes them with text generated from a language model. To develop a high-accuracy prompt, we use an auxiliary LLM to obtain feedback about example predictions with the current prompt and decide to make edits at a section level (add, edit or delete) in each iteration. Our key insight is that feedback on a single example or a randomly selected batch of examples does not yield generalizable facet descriptions. Instead, we propose generating edits at a minibatch level and aggregating the edits at the batch level to yield a single edit that conveys a broad concept relevant to the task. To further increase the chances of facet learning, we cluster the input examples beforehand and use clustered mini-batches (see Figure 1).

We evaluate UniPrompt on zero-shot (no in-context examples) and few-shot settings on four different tasks. In the zero-shot setting, UniPrompt consistently achieves higher accuracy than existing prompt optimization methods. On Ethos, a hate speech dataset, UniPrompt obtains 94% accuracy whereas the next best method obtains 82%. In the few-shot setting, we compare UniPrompt to MedPrompt [], a state-of-the-art prompt composition method. We find that UniPrompt, requiring only one LLM call at inference time, obtains the same accuracy as MedPrompt that requires five calls. If we allow multiple calls to UniPrompt, we obtain over 4% accuracy gains. We also evaluate UniPrompt on a real-world semantic matching task in a web search engine. Compared to the best manual prompt, the prompt generated from UniPrompt leads to over 5% increase in accuracy on the negative class and nearly 2% accuracy increase overall.

Figure: Figure 1: Existing prompt optimization methods (left) versus UniPrompt (right) on the SciQ [] dataset: [Left] State-of-the-art prompt optimization methods such as ProTeGi [] sample from the questions wrongly answered by the current prompt, and use an expert LLM (such as GPT-4) to obtain feedback on the mistakes made; This approach tends to overfit to specific examples, as can been seen from the proposed prompts $p^{\prime}$; leading to limited generalization. [Right] In contrast, UniPrompt identifies key task facets that generalize across examples by: (1) clustering examples into groups with similar task facets, and (2) employing a two-tier feedback-based update strategy. The resulting prompt updates extract generalizable concepts from the specific examples seen.
Refer to caption: x3.png

## 2 Characterizing the Prompt Optimization Problem

Assume access to black-box solver LLM $f:\mathcal{X}\rightarrow\mathbb{R}$ that takes as input a prompt $\mathbf{x}\in\mathcal{X}$ and outputs the average accuracy on a validation set $D_{v}$. Since the set of prompts is combinatorially large, we assume that all prompts can be embedded in a fixed $p$-dimensional space such that distance between two prompts in the vector space correspond to their semantic similarity. Thus, each prompt $\mathbf{x}$ can be expressed as a vector in $\mathbb{R}^{p}$. The prompt optimization problem can be written as $\arg\max_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x};D_{v})$.

We do not have access to the gradients, hence it is a zeroth-order optimization problem. For optimization, we consider the class of sequential algorithms that decide the next prompt based on all previous $\langle$prompt, output accuracy$\rangle$ pairs and a fixed task-specific training set that provides (labelled) input-output pairs for the task.

### 2.1 Is directional optimization feasible?

Previous work has shown that LLMs can be brittle to their input: changing the prompt slightly can create a significant difference in performance []. To understand whether optimization algorithms may work, it is important to understand how the surface of $f$ looks. If $f$ is brittle everywhere to small changes, then random search over prompts (such as in []) may be a competitive method; it is unclear whether optimization can help. On the other hand, if the change in $f$ given small changes to the input prompt is bounded, then optimization algorithms can hope to perform significantly better than random search.

More formally, we ask whether the prompt optimization problem is well-conditioned.
Typically, conditioning can be determined by the Hessian. However, since $f$ is assumed to be black-box, we approximate it by measuring sensitivity, or more specifically, Lipschitz continuity near the optimal solution.
Based on prior work on defining continuity of neural networks [], we use a probabilistic notion.

###### Definition 1

Probabilistic Lipschitz Continuity []. Given a probability distribution over inputs $\mathcal{X}$, $r\geq 0$, a function $f:\mathcal{X}\rightarrow\mathbb{R}$ is $(L,\epsilon)$-probabilistically Lipschitz with constant $L\geq 0$, if

$$ $\Pr_{\mathbf{x},\mathbf{x}^{\prime}\sim\mathcal{X}}[\operatorname{d}(f(\mathbf {x}),f(\mathbf{x}^{\prime}))\leq L.\operatorname{d}(\mathbf{x},\mathbf{x}^{ \prime})\ |\ \operatorname{d}(\mathbf{x},\mathbf{x}^{\prime})\leq r]\geq 1-\epsilon$ (1) $$

where $d$ is a distance measure such as $\ell_{1}$ or $\ell_{2}$ norm.

Note the focus on small changes in input through the parameter $r$. Intuitively, the Lipschitz property bounds the maximum change in $f$ given a small change in input prompt. Typically, the lower bound of error for any sequential optimization algorithm over $f$ is directly proportional to the Lipschitz constant $L$ []. Therefore, for faster convergence, it is desirable to have a low $L$, especially near the optimal solution.
Empirically, we estimate $L$ by sampling task-relevant prompts so that they are close to the optimal solution. Then we make small changes to the prompt such that the semantic meaning stays the same and measure the change in $f$. We show the change in $f$ per change in input for GPT-4, GPT-3.5, and Llama2-13B models in Figure 2(a) for the Ethos dataset commonly used in prompt optimization [, , , , ].
Assuming $\epsilon=0.05$, probabilistic Lipschitz constant $L$ for GPT-3.5 and GPT-4 is $<1$, whereas it is over three times more for Llama2-13B. Thus, as the size of the model increases, the probabilistic Lipschitz constant decreases, indicating that larger models like GPT-3.5 and GPT-4 are more robust to small changes and thus amenable to optimization algorithms. For Llama, the absolute change in accuracy ranges between 0.33 to 0.54, indicating a 63% change in accuracy even across prompts with the same semantic meaning. In contrast, the relative change in accuracy for GPT-3.5 and GPT-4 is 6% and 4% respectively. (See Appendix A.1 for experimental details)

Figure: Figure 2: On the Ethos dataset, (a) estimating (probabilistic) Lipschitz constant of models (Definition 1); (b) diminishing marginal utility (submodularity) of GPT-3.5 on two types of prompting strategies.
Refer to caption: extracted/5668825/Styles/L1.png

###### Definition 1

### 2.2 Can higher-order abstractions of task examples help prompt optimization?

Consider in-context learning [], where the prompt $\mathbf{x}$ is composed of a simple task description and a set of labeled examples from the task. The optimal prompt should consider all the aspects of the task which can only be discovered by exhaustively looking at the examples. But, in practice, we are constrained by (a) availability of a limited number of training examples, (b) prompt size. It is beneficial for in-context learning to consider the marginal utility of examples [, ]. For instance, it would help to add examples where the model fails rather than ones where the model already succeeds (see Table 4 in Appendix). This suggests that one could use a greedy algorithm for iteratively optimizing the prompt by finding failing examples and adding to the prompt. But would such a procedure converge to a good solution?

We can view $f(\mathbf{x})$ as a set function over the examples (that compose $\mathbf{x}$). A natural property to examine is submodularity (where greedy optimization provably converges to a good solution under some conditions []), i.e., the property of diminishing marginal utility of examples. The marginal utility of adding an example $e$ to the few-shot prompt corresponding to a set of examples $A$ is $\Delta_{A}=f(A\cup\{e\})-f(A)$. Let $B\subset A$ denote a subset of $A$. We define $f_{\text{fewshot}}$ to be the validation accuracy of GPT-3.5 using few-shot prompts on the Ethos dataset (see Section 4). In Figure 2 (b), we show the distribution of diminishing marginal utilities for $f_{\text{fewshot}}$ (light blue), i.e., we sample multiple $A,B$ sets of examples from the dataset and compute $\Delta_{B}-\Delta_{A}$, which is expected to be non-negative for submodular functions. As we see, the marginal utility differences are nearly uniformly random in $[-0.01,0.01]$, indicating that there is no submodularity structure to $f_{\text{fewshot}}$.

A recurring theme [, ] in the prompts that humans engineer is to organize task information in “sections” (introduction, context, etc.), treating prompt like a structured document. When humans engineer a prompt, they do it systematically by editing specific sections of the prompt. We hypothesize that there are a small number of facets that collectively define a task, which can be discovered by inspecting a representative set of examples from the data distribution. Consider the task of tagging hate speech. Identifying intent to harm, recognizing general aggression versus targeted hate, and differentiating hate from other objectionable content are some facets of the task. We ask whether there is submodularity structure in adding different facets (text sections) to a prompt, compared to adding in-context examples.
The answer to this question depends on multiple factors: (1) what are the contents of the sections and how are they generated?; (2) how does $f(\mathbf{x})$ behave w.r.t. the sections that make up the prompt $\mathbf{x}$?

Figure 2 (b) shows the distribution of marginal utility differences for $f_{\text{facets}}$ (dark blue), i.e., we sample multiple $A,B$ sets of facets (i.e., short sections) that are generated using a Llama2-13B model, and compute $\Delta_{B}-\Delta_{A}$ (defined as above, but the added element $e$ is now a section) using GPT-3.5 as the solver LLM (See Appendix A.2 for experimental details). We see that the diminishing marginal returns property largely holds for $f_{\text{facets}}$, unlike in the case of $f_{\text{fewshot}}$. This suggests that greedy strategies for prompt optimization problem over sections could work — but this crucially relies on how we generate the sections themselves.

The prompt optimization problem can now be posed as one of inferring the facets of a task from a set of training examples. In the following section, we propose a method that iteratively learns the facets of the task as sections of the prompt.

## 3 UniPrompt: Generating a Prompt that Captures Multiple Facets of a Task

Manual prompt engineering consists broadly of two steps: 1) generating an initial prompt; and 2) identifying errors and editing the prompt. The initial prompt for a task is constructed based on domain knowledge. Typically, the initial prompt contains implicit or explicit sections (e.g., introduction, task description, intended application, edge-cases, challenges, etc.) wherein each section corresponds to a relevant task facet. Given the initial prompt and a solver LLM, a human prompt engineer would look at the incorrect predictions, form hypotheses on which section of the prompt needs to be edited or whether a new section needs to be added, and then propose edits that may fix the errors. Then, the prompt engineer may pick the edit with the highest validation accuracy. These steps are repeated in a loop, until the validation accuracy saturates. A good engineer may also backtrack from an optimization trace and start from some previous prompt, in case the current optimization trajectory yields unsatisfactory results.

We present UniPrompt, a prompt optimization algorithm that aims to mimic the above process. Specifically, the algorithm extracts key concepts or facets relevant to a task and updates prompt sections using them, with the overall goal of increasing validation accuracy. Our analysis from Section 2 indicates that such a directional optimization procedure based on iteratively adding task facets can converge to a good solution, especially for solver LLMs such as GPT-3.5 and GPT-4.

We assume that the algorithm receives as input a one-line task description and a set of labelled $\langle$input, output$\rangle$ demonstrations. The algorithm proceeds in two stages:

1) Task Facets Initialization using background knowledge. In the first stage, the algorithm leverages a language model to generate a prompt with multiple facets, i.e., sections focusing on specific task aspects based on the task description. It greedily selects content for each facet from a pool of candidates generated using the language model.

2) Task Facets Refinement using examples. In the second stage, the algorithm refines the prompt using a set of training examples and an auxiliary LLM. Given a candidate prompt, it collects examples with prediction errors by the solver LLM, extracts key concepts or facets required to fix those errors, and makes appropriate edits. An edit may create a new section, modify an existing section, or delete an existing section. Additionally, we maintain a beam of best performing prompts to backtrack and restart from a previous prompt if the current optimization path is unsatisfactory.

Similar to UniPrompt, previous methods [, ] propose using an auxiliary LLM to provide feedback on incorrect predictions and propose edits to a given prompt. In our initial experiments, however, we find that collecting feedback over individual examples or randomly sampled batches leads to memorization of individual examples (see Figure 1) rather than recognition of facets that are important to the task. To avoid overfitting to the train examples and to extract generalizable concepts, we make two contributions. First, we follow a two-tier setup of synthesizing feedback for a batch of training examples. We break up a batch into mini-batches, collect feedback on each of the mini-batches and then use a separate prompt to aggregate the different feedback texts into a generalizable concept. Second, to increase chances that a mini-batch corresponds to a coherent facet, we cluster the training data beforehand and ensure that each mini-batch consists of examples from the same cluster. We provide details of the algorithm below (see Algorithm 1).

Notation: We denote the training set with $D_{t}$ where each example is a question-answer pair of the form $\{q_{i},a_{i}\}$. The validation set is denoted as $D_{v}$. We have $N$ training examples and $K$ validation examples. Input to the algorithm is the solver LLM $f_{LLM}$, train set $D_{t}$, validation set $D_{v}$, initial prompt for the task $p_{0}$, one-line task description $T$. In addition, we assume access to an “expert” auxiliary LLM such as GPT-4.

Figure: Algorithm 1 UniPrompt

### 3.1 Task facet initialization using background knowledge

While existing methods for prompt optimization [, ] iteratively edit a human-written prompt, our goal is to generate the entire prompt from scratch (specifically, based only on a one line description of the task). Therefore, one option is to initialize the prompt using only the task description. We call this Task Description Initialization and initialize the prompt with a single section titled Introduction containing the input task description.

In the second kind of initialization, we finetune a language model to generate a prompt with multiple diverse sections such as Introduction, Tricks, and Corner Cases; similar to the initial prompt that a human prompt engineer may produce. Here we use the world knowledge embedded in language models that are trained on extensive text data. The language model is finetuned to output the entire section contents given the task description and the section title. Specifically, we train a Llama2-13B model using a synthetic dataset generated using GPT-4. Across a wide range of tasks, we first use
use GPT-4 to identify the important sections given the task, section descriptions and a few examples (See Appendix A.6 for the prompt). We then fine-tune a language model $\phi$, that is Llama2-13B, in a supervised setting on a synthetically created dataset of the form $\langle T,P_{i},S_{i},{\bf S^{\prime}}_{\text{gold}}\rangle$ where $T$ denotes the task description, $P_{i}$ is the prompt generated using the fine-tuned model sequentially before section $S_{i}$ (i.e., it would have optimized sections $\{S_{1},S_{2},...S_{i-1}\}$), and ${\bf S^{\prime}}_{\text{gold}}$ is the gold section contents. $\phi$ is finetuned on the objective: $\min_{\phi}[-\log(p_{\phi}({\bf S^{\prime}}_{\text{gold}}|T,P_{i},D_{t},S_{i}))]$. We then sample 10 candidates for each section using the fine-tuned model and evaluate each section added incrementally against $D_{v}$ and select the best performing candidate for each section. More details on data collection and training of SLM are given in the Appendix A.4.
Examples of one line task description and the Llama-initialized prompt for different tasks are in Appendix A.3.

### 3.2 Task facet refinement using examples

Extracting task-relevant concepts from a set of examples to refine a prompt is a complex problem comprising multiple steps. Given a set of incorrect predictions, one needs to analyze what went wrong in each prediction, form hypotheses, aggregate the hypotheses to identify specific concepts that are relevant for the task, and then for each concept, one needs to attribute which facet/section of the current prompt needs to be edited to incorporate the concept. These operations are highly model-specific and are difficult to execute reliably. Therefore, for this stage, we exclusively rely on an “expert” auxiliary LLM such as GPT-4.

The whole process is executed through a series of prompts to the expert LLM. First, we prompt the expert LLM to diagnose mistakes (feedback) in each example given the answer and chain-of-thought reasoning produced by the solver LLM. Subsequently, we use this feedback to generate precise edits for the prompt that may fix the error. These individual edits are then aggregated over a mini-batch and fed back into the same LLM, which then identifies a few major edits to be applied to the current prompt. To aid in identifying major edits that correspond to generalizable facets, we propose to cluster the examples as a preprocessing step and create clustered batches, such that each cluster shares some common facet of the task.

#### 3.2.1 Preprocessing step: Clustering examples to facilitate facet identification

We explore two approaches for clustering: topic based clustering, and feedback based clustering.

Topic-Based Clustering. Given a set of examples, we identify $l$ topics that would span the entire train set. This type of clustering is motivated by the observation that solver LLM may make similar mistakes on examples from the same topic. Hence, for such examples, a common edit to the prompt could improve predictions for all the examples. To obtain the clusters, the expert LLM is prompted (for prompt see Appendix A.7) to provide a broad sub-topic $t_{i}$ for each question. Then the resultant list of sub-topics $\{t_{1},t_{2},\dots,t_{N}\}$ is again clustered into $k$ topics $\{t^{\prime}_{1},t^{\prime}_{2},\dots,t^{\prime}_{l}\}$ by prompting the expert LLM. Based on this clustering, each example ${q_{i},a_{i}}$ is assigned a cluster $t^{\prime}_{j}$ corresponding to $t_{i}$.

Feedback-Based Clustering. Another way to find examples that share similar task facets is the feedback they receive based on the initial prompt’s predictions. For instance, for a physics-based task, if two examples from different topics obtain the same feedback from the expert LLM to edit the “Rules” section of the prompt and include the statement, “Draw all forces on each body before writing the equations", then we argue that such examples can be clustered. This type of clustering makes the broad edit identification step easier. To obtain the clusters, we first evaluate all training examples against the initial prompt $p_{0}$ and store the feedback $f_{i}$ from the expert LLM, corresponding to each incorrectly answered example ${q_{i},a_{i}}$ (all the correctly answered questions form one cluster). We then prompt the expert LLM to cluster these feedbacks $\{f_{1},f_{2},\dots,f_{N}\}$ into $l$ clusters $\{f^{\prime}_{1},f^{\prime}_{2},\dots,f^{\prime}_{l}\}$ (see Appendix A.8). For each cluster $f^{\prime}_{j}$, we create a batch of examples ${q_{i},a_{i}}$ corresponding to each $f_{i}$ in $f^{\prime}_{j}$.

#### 3.2.2 Generating prompt edits that generalize to multiple examples

Two-tier Feedback. To encourage generalizable feedback from the expert LLM that applies to more than one example, we obtain feedback at two levels: mini-batch and batch. Given a batch (created using clustering discussed above), we break it up into mini-batches.
For each mini-batch $m$, we consider the questions for which the solver LM answered incorrectly with the current prompt. For these questions, we construct a prompt consisting of the questions, the chain-of-thought produced by the solver LLM, their incorrect predicted answers and the ground-truth answers. We ask the expert to provide one feedback for the mini batch (prompt is provided in Appendix A.9). In the prompt, we specify the following types of edits that the expert LLM can suggest: add a section or subsection, delete a section or subsection, and edit a section or subsection.

Given the different feedback texts for mini-batches within a batch $b$, the next step is use another call to the expert LLM to summarize the given set of edits and provide a single summarized section update. This combination ensures some degree of smoothness at every update which helps stabilize training. To make sure that the expert is able to generate generalizable edits, we additionally provide a random set of incorrect examples that are not in the current batch and ask it to suggest an edit based on the existing edits that can correct the errors. As before, the class of edits allowed is the same.

History for effective exploration: To ensure comprehensive and non-repetitive exploration of prompts, we also provide the batch-level history of edits in the mini-batch-level prompt. Specifically, we provide the expert with the history of edits $H[b]$ [, ] for the batch $b$ and the corresponding accuracy difference that each edit caused over the previous edit for the given batch. History is presented in the format $\{e_{i},acc_{i}-acc_{i-1}\}$ where $e_{i}$ is the edit proposed at the $i^{th}$ update and $acc_{i}$ is the accuracy of the $i^{th}$ updated prompt (See Appendix A.9 for the full prompt).

#### 3.2.3 Editing the prompt

Once the final set is edits is received for a batch, we use the expert LLM to apply edits to the current prompt (see Appendix A.10 for the prompt). An edit is accepted only if it increases the validation accuracy compared to the current prompt. We call this approach “Greedy”. Alternatively, we maintain a beam of $l$ best performing prompts based on validation accuracy, apply the edit to all the $l$ prompts, and update the beam to retain the top $l$ performing prompts. We call this method “Beam”. To avoid overfitting on the train examples (or keep adding unnecessary information to the prompt), we employ early stopping in the optimization process (More details given in Section 4).

### 3.3 Efficiency considerations: Computational Complexity

The computational complexity of UniPrompt is dominated by the training phase, and in particular, by the queries made to the solver and the expert LLMs; at inference time, we need a single query to the solver LLM using the learnt prompt and the given test example. This is particularly well-suited for settings such as recommendation systems, where inference time efficiency is critical. In contrast, methods such as MedPrompt [] require multiple calls at test time for a single test example. Let us now consider the compute complexity in terms of the number of expert or solver LLM calls made per epoch, stage-wise.

Clustering: First, we evaluate all the training examples using the current prompt. Second, for every wrongly predicted example, we obtain feedback from the expert LLM. Third, for the given set of feedbacks, we use a single call to cluster it into $l$ clusters. Each of the above steps incurs $O(N)$ queries, so the total query complexity of the clustering stage is $O(N)$. Finally, for each example, i.e., (question, answer) pair, we simply map it to the $l$ clusters (no LLM calls). This is a one-time cost.

Mini-batch feedback and Batch-level aggregation: At a given epoch, we evaluate every question in the mini-batch using the current prompt and the solver LLM ($N$ queries overall). Next, we obtain one feedback over all the wrong questions in the mini-batch $m$ ($N/|m|$ queries). We use one call to aggregate these feedbacks. For prompt selection, we evaluate $2k$ prompts on the batch $b$, where $k$ is the beam size ($O(2k|b|)$ queries per batch). Hence overall query complexity is $N+N/|m|+2kN+1$ or $O(kN)$. In practice, $k$ is a small number (2 in our experiments).

Assuming LLM throughput of 0.5 queries per second, a training + validation set of 300 examples, $l=10$ clusters, beam size $k=2$ and 20 epochs, it takes under 7 hours to train.

## 4 Experiments

Datasets
We perform evaluation on four standard datasets
: (1) Ethos [], (2) ARC [], (3) MedQA [], and (4) GSM8K []. Ethos, ARC, and MedQA contain multiple choice questions, and GSM8K contains questions with integer answers.

Implementation details
We set the initial prompt $p_{0}$ for each task as the one line task description and use 200 data points $(q_{i},a_{i})$ as the train set. We use GPT-3.5-Turbo as the solver model, that is used in a chain-of-thought setting. For Feedback and Combine, we use GPT-4 as the expert.
We maintain a beam size of 2. Mini-batch sizes (and batch sizes) are constrained by the context length of GPT-4. We find that mini-batch sizes 3 to 5 and batch sizes 5 to 7 work the best for our datasets. The temperature of the LLMs for our method is set to 0 for reproducibility of results.
We employ early stopping at batch-level in UniPrompt. We find that a $patience$ value of 5 works best for the given tasks.

Baselines
We compare UniPrompt with the following techniques: (1) Task Description: prompt is the one line task description that we use to initialize UniPrompt; (2) Chain-Of-Thought (or CoT) prompting []; (3) Expert Prompt: the prompt optimized by humans taken from prior works []; (4) OPRO [], that uses LLMs for discrete optimization over text prompts; (5) ProTeGi [] that proposes textual gradients and selects edits to prompts using bandit techniques; (6) Evoke [] that uses two instances of LLM, one that scores the current prompt, and the other that edits the prompt; (7) EvoPrompt [] that uses genetic algorithms to search through the space of prompts; and (8) MedPrompt [] that effectively combines multiple prompting strategies such as kNN-based few-shot selection, CoT reasoning, and ensembling.

Metrics
For each dataset, we perform 5-fold validation (we split the train set into 5 folds) and report the final test accuracy as the average accuracy of the 5 runs on the test sets.

### 4.1 How does UniPrompt compare to existing methods in zero-shot setting

In the zero-shot setting, we do not include labeled examples in the prompt for any of the compared methods. We report results for four versions of our method in Table 1; they differ in the initial prompt—task description, expert prompt, or the prompt generated by the fine-tuned Llama model (discussed in Section 3.1)—and the combining strategy (from Section 3.2.3)—beam search vs greedy.

UniPrompt variants significantly outperform the baselines including CoT and the state-of-the-art prompt optimization techniques like ProTeGi that crucially leverage LLMs for performing iterative prompt edits. We achieve maximum gains on the Ethos dataset with a $18.2\%$ increase in accuracy over the expert prompt. Further, we see accuracy increases of $4.0\%$ on MedQA, $3.5\%$ on GSM8k, and $7.6\%$ on ARC-Challange datasets.

An example of evolution of prompts using our algorithm is given in Appendix4. It starts with a simple description of task and adds important details like differentiating between hate speech and rudeness. In contrast, ProTeGi [] yields a rather terse prompt on the same dataset: “Does the following text contain language that targets a group of people based on their religion, gender, or other personal characteristics?”. This prompt does not provide various facets of the task, the way our method infers or an expert would typically write.

**Table 1: Test accuracies for the compared methods with GPT-3.5-Turbo as the solver model in the zero-shot setting (best in bold; second best underlined). The last four rows correspond to our proposed method.**
| Method | Ethos | ARC | MedQA | GSM8K |
| --- | --- | --- | --- | --- |
| Task Description | 76.8 | 79.7 | 52.7 | 59.4 |
| Expert Prompt | 74.1 | 78.4 | 53.1 | 78.9 |
| Llama Prompt (Section 3.1) | 74.0 | 89.7 | 52.6 | 79.5 |
| CoT | 72.0 | 79.4 | 50.3 | 76.3 |
| OPRO | 65.4 | 79.1 | 53.3 | 77.1 |
| ProTeGi | 76.0 | 78.8 | 52.9 | 77.3 |
| Evoke | 63.5 | 89.0 | 52.8 | 81.0 |
| EvoPrompt | 81.6 | 89.9 | 50.3 | 81.4 |
| UniPrompt (Init = Expert Prompt) + Beam | 84.0 | 86.0 | 52.3 | 82.4 |
| UniPrompt (Init = Task Description) + Beam | 92.3 | 86.0 | 57.1 | 82.4 |
| UniPrompt (Init = Llama Prompt) + Beam | 92.0 | 90.5 | 55.5 | 81.5 |
| UniPrompt (Init = Task Description) + Greedy | 93.7 | 90.5 | 55.5 | 82.3 |

The training curves in Figure 3 show that our method initially performs edits on the prompt that simultaneously increase the train as well as the validation accuracy. After about 10 or 15 iterations (each batch update is an iteration), validation accuracy decreases while train accuracy continues increasing, indicating overfitting; which we overcome by using early stopping.

### 4.2 How does UniPrompt perform compared to SOTA in the few-shot setting?

We now compare the performance of UniPrompt, in the few-shot setting with GPT-4 as the solver model, to the SOTA prompting technique MedPrompt [] that employs three key components: (1) few-shot prompting, where they dynamically select five relevant examples using k-nearest neighbors (kNN) clustering in the embedding space; (2) Chain-of-Thought (CoT) reasoning on the selected examples; and (3) self-consistency and ensembling with option shuffling. From Table 2, we observe that UniPrompt (first col), which requires only one call at inference time, performs almost as well as MedPrompt (last col), which requires five calls, on the MedQA, PubMedQA, and MedMCQA datasets. As we incrementally add components such as kNN few-shot, CoT, and Ensemble to our prompt, we see a significant increase in accuracy of $4.35\%$ on average across all datasets.

### 4.3 Results on a Real-world Task: Search Query Intent

We consider the task of inferring if two search queries share identical intent or not. This is an important task arising in search and recommendation pipelines, and is tackled today using LLMs. It is challenging to tell if two queries share the same intent, as it requires domain knowledge (e.g., brands and product categories), depends on geographical biases (e.g., “cricket” and “cricket game” are likely to mean the same in UK, but unlikely in the US), and even on cultural connotation. So, examples are crucial for understanding the task and engineering a prompt that generalizes well.

We sample real user queries from a proprietary application, rewrite them using ML models, and ask expert judges to label the query-pairs as identical or otherwise based on prescribed guidelines. We use a set of 200 examples as training data, and an additional 50 examples as validation set, to learn a prompt using UniPrompt, starting from the one-line description: Tell if query A and query B have same intent or not. The dataset is heavily biased towards positive samples, so the metric of success is improvement in accuracy, over the best manually-engineered prompt, on the positive and negative classes individually. For testing, we use a separate labelled set of 2527 examples from two geographies — one where the training data was sampled from, and the other unseen.

The prompt obtained using UniPrompt improves over the best manual prompt by 5.77% on the negative (rare) class, by 0.23% on the positive class, and by 1.86% overall on the test set. The learnt prompt captures the following facets of the task: (1) recognizing variations in names and abbreviations, and how they do not necessarily change the context; (2) recognizing the specificity of brands, and how even minor variations do change the context; and (3) recognizing the specificity of terms in queries, and how lack of specific terms can indicate departure of intent.

### 4.4 Do diverse task facets organized as sections really help?

We now revisit our hypothesis and motivation in Section 2.2. We want to empirically validate if all the diverse task facets that UniPrompt learns indeed contribute to the performance gains that we observe in Table 1. We consider two ablations:

1) We successively remove each facet (i.e., sections) in the learnt prompt for the task and report the performances of the prompts with fewer facets. In Figure 3, for the Ethos dataset, we see that almost every additional facet contributes to non-trivial gains in accuracy.

2) Could we have captured the information differently and retained the performance? We do a simple experiment – we summarize all the facets (i.e., learnt prompt) and evaluate the resulting prompt. In Figure 3 (right) (green line), we see that the summarized prompt has a significant accuracy drop.

### 4.5 Ablations: Impact of Clustering, Inclusion of History, and Greedy Update

Here we study effect of our design choices, namely clustering (Section 3.2), inclusion of history of past prompts (Section 3.2), and the greedy update rule (Section 3.2.3). The results are shown in Table 3. We see that clustering as well as edit history components are critical for performance of UniPrompt in all the datasets. We see a major drop of $14.8\%$ in accuracy in the Ethos dataset when clustering is removed, and a $4.3\%$ drop when history component is removed. In all the datasets except GSM8K, we find clustering is more important than history. This can attributed to variability of question types being less in GSM8K than in others: all questions are grade-8 arithmetic questions in GSM8K.

We also find that the greedy update rule proves to be superior or competitive compared to beam search in relatively easier datasets — where even less exploration produces good results, greedy proves to be a more effective update rule. On the other hand, in more complex datasets like MedQA, greedy appears to be a bad strategy. We also see that clustering examples based on feedback (“Fb Clustering”) is a better strategy than clustering based on topics, except for the Ethos dataset.

## 5 Related Work

Here, we highlight relevant work that are not addressed in the manuscript so far.
Deng et al. [] present a discrete prompt optimization method, RLPrompt, using reinforcement learning, where a policy network learns to generate effective prompts through reward-based training, with an emphasis on enhancing training efficiency through effective reward stabilization techniques.
A drawback of such automatic prompt optimization approaches [, , , ] is that the prompts generated tend to be short, often comprising only one or two sentences, which may not fully encapsulate the complexity of the task at hand.

Prior research [, ] has highlighted the significance of specific sections within prompts. For instance, a well-designed prompt typically incorporates elements such as a system prompt and a chain-of-thought section. However, existing methods do not specifically target the optimization of individual sections and their respective contents within the prompts. Hsieh et al. [] investigate the use of greedy and genetic algorithms to edit lengthy prompts. Their method focuses on paraphrasing one line at a time starting from an existing prompt, compared to our goal of learning facets of a task from scratch, thereby compromising generalization accuracy. Another orthogonal line of work that ha been explored recently for prompt optimization is the algorithmic selection of in-context examples [, , , , ].

## 6 Limitations and Future Work

We presented a method inspired by the human prompt engineering process to generate complex prompts from scratch that include different facets of a task. Our algorithm provides significant improvements over baseline prompt generation methods on multiple standard datasets. However, in our evaluation, we considered only classification tasks and only GPT-4 as the expert LLM. Generalizing to generative tasks, as well as investigating the impact of the expert LLM choice are some future directions.

## Appendix A Appendix

**Table 2: Comparison of UniPrompt (“Ours”) with MedPrompt, with GPT-4 as the solver model.**
|  | Ours | Ours + KNN | Ours + KNN + COT | Ours + KNN+COT+Ensemble | MedPrompt |
| --- | --- | --- | --- | --- | --- |
| MedQA | 80.9 | 81.0 | 83.9 | 87.0 | 80.6 |
| PubMedQA | 70.3 | 72.2 | 74.7 | 75.6 | 71.2 |
| MedMCQA | 79.2 | 81.4 | 82.6 | 84.5 | 79.1 |
| MMLU MG | 78.0 | 94.0 | 96.0 | 99.0 | 98.0 |

Figure: Figure 3: Training curves for MedQA (left) and ARC (middle) datasets when UniPrompt is initialized with (published) state-of-the-art prompts; (right) ablation of facets on Ethos (Section 4.4).
Refer to caption: extracted/5668825/latex/3_1.png

**Table 3: Ablation of design choices in UniPrompt with GPT-3.5-Turbo as the solver model.**
|  | Ethos | ARC | MedQA | GSM8K |
| --- | --- | --- | --- | --- |
| UniPrompt $-$ History | 88.0 | 84.6 | 55.3 | 80.8 |
| UniPrompt $-$ Clustering | 77.5 | 82.0 | 54.1 | 81.5 |
| UniPrompt | 92.3 | 86.0 | 57.1 | 82.4 |
| UniPrompt $+$ Greedy | 93.7 | 90.5 | 55.5 | 82.3 |
| UniPrompt $+$ Fb Clustering | 87.2 | 91.2 | 58.3 | 82.5 |

### A.1 Details on estimation of Lipschitz constant L 𝐿 L italic_L

TO calculate the Lipschitz constant for a given LLM and task, we take a human written promp and generate it’s paraphrases using GPT-4. We prompt GPT-4 with the following text: “You are given a sentence, you have to generate 30 paraphrases of the sentence, make sure that the cor content of each paraphrase is same, you can use add, subtract or change words". These paraphrases are then evaluated on the validation set $D_{v}$. For a measure of distance between two prompts, we take the cosine similarity between the embeddings of two prompts. We use text-ada-002 for generating the text embeddings for prompts.

### A.2 Details on marginal utility difference calculation for prompts

For a given LLM and task, to study the marginal utility of different facets for a prompt, we first sample a few facets (generated using the fine-tuned model) that individually perform better than the chain-of-thought prompt as a baseline. Given these set of facets, we sample three facets $f_{1},f_{2},f_{3}$ and generate four prompts: $A:f_{1},B:f_{2},A+\Delta:f_{1}+f_{3},B+\Delta:f_{2}+f_{3}$. We define $\Delta_{A}$ as the accuracy difference between prompt $A$ and prompt $A+\Delta:f_{A}+f_{A+\Delta}$. Similarly, $\Delta_{B}=f_{B}+f_{B+\Delta}$

### A.3 Prompt Initialization

One line task descriptions:

- 1.
Ethos: In this task, you have to determine whether a given text is hate speech or not.
- 2.
ARC: You have to solve the following science question.
- 3.
GSM8K: In this task, you are given a math question. You have to solve the question.
- 4.
MedQA: In this task, you are given a medical question. You have to solve the question.

An example of sectioned initialization prompt generated using finetuned Llama Model

### A.4 SLM Training Details

To induce the ability of structured prompt generation in a smaller language model, we curate a section-wise dataset of around 12,000 task-prompt pairs. The tasks for training dataset creation were taken from tasksource library [] that contains around five hundred classification tasks. We extract the task description from tasksource-instruct, which contains tasksource dataset recasted with instructions. For instance, the task description for BIG-bench Entailed Polarity task is, "Given a fact, answer the following question with a yes or a no".
The dataset provides diverse tasks and their short description, but not the human-generated prompts for each task. To approximate human-generated prompts, we use GPT-4 as a teacher model.

By prompting GPT-4 with the task description and section description, we ask it to generate the contents of the section. To ensure that the generated section-wise prompts are concise and relevant, we prompt GPT-4 to not generate more than five lines of content for each section. We use LLAMA2-13B model, which we finetune using LoRA adapters as the auxiliary LM that generates sections.

### A.5 Prompt to Llama2-13B for fine-tuning

#### A.5.1 Examples of training dataset

### A.6 Prompt for identifying important facets

### A.7 Clustering Type 1

### A.8 Clustering Type 2

### A.9 Feedback Prompts

Feedback over mini-batch

========================================
Feedback over batch

### A.10 Editing Prompt

### A.11 Example of prompt evolution using our method

See example in Figure 4.

Figure: Figure 4: Evolution of prompts through iterations of UniPrompt on the Ethos dataset. Starting from a simple one-line prompt having an accuracy of $82\%$, UniPrompt adds background knowledge, corner cases, and additional sub-sections yielding a prompt with accuracy $88\%$. After further iterations, our algorithm converges to a detailed, human-like longform prompt that achieves accuracy of $92\%$.
Refer to caption: x4.png

### A.12 Comparision of our method with existing methods

See Figure 5.

Figure: Figure 5: Comparison of human-written Prompt and prompt produced by UniPrompt on MedQA dataset.

Figure: Figure 6: Comparison of prompt produced by the state-of-the-art ORPO [] and by UniPrompt on the GSM8K dataset.

### A.13 Effect of length on performance of prompt

Here we answer the question: How much does only length contribute to UniPrompt’s success?. To answer this, we replace the prompt with in-context examples of the same context length and compare the accuracies in Table 4. We also compare the case where we include only the examples that the solver LLM gives incorrect prediction on, denoted as “Wrong ICL” row in the table. We see that there is a slight increase in accuracy when wrong examples are included in the prompt over randomly including examples. But, overall, UniPrompt performs much better than including in-context examples. This shows that length is not the only factor contributing to UniPrompt’s success.

**Table 4: Analysis of the effect of length and contents on the performance of UniPrompt**
|  | Ethos | ARC | GSM8K |
| --- | --- | --- | --- |
| UniPrompt | 93.7 | 90.5 | 82.4 |
| ICL Prompt | 63.0 | 86.7 | 76.3 |
| Wrong ICL | 70.4 | 87.1 | 78.2 |
| Summarized Prompt | 84.3 | 85.5 | 66.0 |

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: The impact of mini-batch size. 

The impact of aggregation.
soundness: 3
strengths: The strategy for creating mini-batches to generate edits and then aggregating them at the batch level to yield the final edit in a feedback mechanism is interesting. 

Experimental results achieves SOTA.
summary: This paper proposes a prompt optimization method $U_{NI}P_{ROMPT}$ to generate complex prompts for covering multiple facets of a task and improving overall accuracy. Its effectiveness is demonstrated through relevant experiments.
weaknesses: 1.The paper contains some detailed issues, e.g., $U_{ni}P_{rompt}$ mentioned in  line 100-101; an extra space before "So" mentioned in line 197-198. 

2. The experiments should be re-organized and polished carefully before submission, especially in Section 4.1,  4.2 and 4.5. 

3. Some qualitative experiments are supported be added to validate the differences in report accuracies under various mini-batch sizes.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: See weaknesses.
soundness: 3
strengths: - UNIPROMPT clusters examples to capture task-specific facets effectively, with a two-tier feedback mechanism ensuring that prompt modifications are generalizable and not overly specific to individual examples.
- The authors provides strong empirical results, with UNIPROMPT outperforming state-of-the-art methods on multiple datasets, notably achieving significant improvements on hate speech classification.
- By focusing on automatic prompt generation without relying heavily on human-engineered prompts, this approach may reduce the manual overhead of prompt tuning.
- Extensive ablations validate the contribution of each component (clustering, feedback structure) to performance.
summary: The paper introduces UNIPROMPT, a method that uses task facet learning to enhance prompt optimization by breaking down prompts into distinct semantic sections, targeting diverse facets such as counter-examples and explanations.
weaknesses: - All experiments are conducted on powerful proprietary LLMs, I wonder whether the proposed method remains effective for opensource LLMs such as LLaMA or Qwen.
- It seems that the proposed method underperforms DSPy on MedQA, while surpassing it on other benchmarks, what might be the reason?
- How to determine the number of clusters when constructing the minibatches? How does this affect the method's effectiveness?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: N/A
soundness: 3
strengths: (1) The paper introduces a new method for prompt optimization and consider multiple facets of a task and leveraging the structure in the prompt.
(2) The proposed clustering approach and two-tier feedback mechanism provide a systematic way to generate prompt edits that capture generalizable concepts.
(3) The experimental results on several datasets shows that UNIPROMPT outperforms human-tuned prompts and SOTA methods.
summary: This paper introduced a method for prompt optimization called UNIPROMPT. The prompt optimizaiton is deemed as the task of learning multiple facets of a task. UNIPROMPT exploit the structure in the prompt optimization and use a clustering approach to group examples with similar task facets. Experimental results on multiple datasets demonstrate that prompts generated using UNIPROMPT achieve higher accuracy than human-tuned prompts and state-of-the-art methods.
weaknesses: (1) I am skeptical about the current importance of prompt optimization. Prompt optimization is more of a need in an era when large models are not powerful (for example last year). Nowadays, the instruction model follows human instructions very well, and many of them are 0-shot, see llama-3.1 model card. I would like to hear the author's opinion on this.

(2) For the results in table 1, it is recommended to add an average column to make the presentation clearer.

(3) I found that on the ARC task, compared with the llama prompt, the optimized prompt led to a decrease in performance. Is there any explanation?

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. If I understand correctly, the wrongfully predicted training samples are clustered only once at onset, how does the algorithm handle the wrong samples after the optimization starts? Does it use them to generate feedback?

2. Did you try using other model families? How does the performance look like when the expert model is not as powerful as GPTs? 

3. The clustering is conducted through LLM, but this could be an issue when the number of examples increases. Did you try other clustering approach? which might make it feasible to dynamically cluster the examples along the iterations.
soundness: 3
strengths: 1. The paper is well-structured and the story is well-told. It starts with essential observations that motivate the improvements so that the approach bears heuristic justification. 

2. Experiments are comprehensive, including several baselines, and benchmarks of different types. Experiment results also provide strong support to the thesis of the paper.
summary: This paper presents an improvement to current prompt optimization approach. It does so by clustering the input space and enabling the optimization algorithm to learn multiple facets of a task from a set of batched clusters. The paper discusses the empirical observation that inspires the improvement and conducts experiments to demonstrate its efficacy. Results suggest that the framework achieve better results than existent approach.
weaknesses: My concern on the improvement is its generalization ability. The experiments cover hate speech detection, math, QA but there are many other task types not covered in this dataset. For example, OPRO and [Li et al 2024](https://arxiv.org/abs/2409.15199) ran experiments on BBH which contains a much more diverse task portfolio than presented in the paper. Since the proposed improvement centers around clustering the training examples, whether the samples can be cluster into meaningful subspace has a direct impact on optimization performance. But we don't see sufficient evidence to demonstrate the approach works on a divers task portfolio. 

Besides, the prompt optimization is very sensitive to the initial prompt and iterations (also discussed in Sec 2.1), but the reported metrics don't take the performance variation into consideration. I have concern on the robustness of the results.

Meta-review: This paper proposed a new prompt optimization algorithm, UniPrompt, which exploits the structure in the prompt optimization, uses clustering to capture different facet of the task feedback and feedback mechanism to capture generalizable facets. The experiment shows the effectiveness of the proposed method comparing with other prompt optimization algorithms. Reviewers all appreciate the contribution of the work; however, the concerns still persists on the ablation studies such as different base LLMs, prompt initialization, and clustering. Addressing these concerns through additional ablation studies would strengthen the paper and provide a more comprehensive understanding of UniPrompt's capabilities and limitations.

Decision: Reject