Understanding prompt engineering may not require rethinking generalization
Authors: Victor Akinwande
Yiding Jiang
Dylan Sam
J Zico Kolter
Venue: ICLR 2024 poster (2024)
Keywords: generalization
prompt engineering
PAC-Bayes
foundation models
Primary area: general machine learning (i.e., none of the above)
TL;DR: We show that prompt engineering generalizes well via a PAC-Bayes analysis.

Abstract: Zero-shot learning in prompted vision-language models, the practice of crafting prompts to build classifiers without an explicit training process, has achieved impressive performance in many settings. This success presents a seemingly surprising observation: these methods suffer relatively little from overfitting, i.e., when a prompt is manually engineered to achieve low error on a given training set (thus rendering the method no longer actually zero-shot), the approach still performs well on held-out test data. In this paper, we show that we can explain such performance well via recourse to classical PAC-Bayes bounds.  Specifically, we show that the discrete nature of prompts, combined with a PAC-Bayes prior given by a language model, results in generalization bounds that are remarkably tight by the standards of the literature: for instance, the generalization bound of an ImageNet classifier is often within a few percentage points of the true test error. We demonstrate empirically that this holds for existing handcrafted prompts and prompts generated through simple greedy search. Furthermore, the resulting bound is well-suited for model selection: the models with the best bound typically also have the best test performance. This work thus provides a possible justification for the widespread practice of "prompt engineering," even if it seems that such methods could potentially overfit the training data.

Published as a conference paper at ICLR 2024
UNDERSTANDING PROMPT ENGINEERING MAY NOT REQUIRE RETHINKING GENERALIZATION
Victor Akinwande', Yiding Jiang', Dylan Sam 1 & J. Zico 1.2 Carnegie Mellon University, "Bosch Center for AI
ABSTRACT
Zero-shot learning prompted vision-language models, the practice of crafting prompts to build classifiers without an explicit training process, has achieved impressive performance in many settings. This success presents seemingly surprising observation: these methods suffer relatively little from overfitting, i.e., when prompt is manually engineered to achieve low error given training set (thus rendering the method no longer actually zero-shot), the approach still performs well on held-out test data. In this paper, we show that we can explain palss such performance well via recourse to classical PAC-Bayes bounds. Specifically, we show that the discrete nature of prompts, combined with a PAC-Bayes prior given by a language model, results in generalization bounds that are remarkably tight by the standards of the literature: for instance, the generalization bound of an ImageNet classifier is often within a few percentage points of the true test error. We demonstrate empirically that this holds for existing handcrafted prompts and prompts generated through simple greedy search. Furthermore, the resulting bound is well-suited for model selection: the models with the best bound typically also have the best test performance. This work thus provides a possible justification for the widespread practice of "prompt engineering," " even if it seems that such methods could potentially overfit the training data.
INTRODUCTION
Generalization bounds provide statistical guarantees on the average-case performance of learning algorithm's 's output. However, in the case of deep learning models, there is still debate about how useful such bounds can be: Zhang et al. (2021) highlighted that classical approaches for deriving generalization bounds are insufficient for explaining the generalization ability of deep learning, spurring flurry of new approaches for deriving tighter generalization bounds for deep neural networks (Bartlett et al., 2017: Dziugaite & Roy. 2017: Neyshabur et al., 2017b). In the recent literature on generalization bounds for deep learning, large focus has been on developing data- dependent bounds, or bounds that consider both the data distribution and the hypothesis space. Some of the best data-dependent bounds arise from the PAC-Bayes framework (McAllester, 1999) and are derived by bounding the KL divergence between prior over the hypothesis space and the posterior yielded by the learning algorithm. However, although PAC-Bayes bounds led to the first non-vacuous generalization bounds for deep learning (Dziugaite & Roy, 2017), they are still too loose to be practically useful (Jiang et al., 2019) in most realistic settings. In fact, as Lotfi et al. (2022) have recently argued, many BACe bounds with data-dependent priors, while non- vacuous, can be best described as validation bounds- - i.e., the use of data-dependent priors effectively leverages held-out data in manner similar to cross-validation, which undermines their ability to explain generalization.
Notwithstanding the lack of clear theoretical basis, modern machine learning models are moving towards increasingly large pretrained models (Kaplan et al., 2020; Dosovitskiy et al., 2020). One prevailing paradigm is to use pretrained foundation models such CLIP (Radford et al., 2021) or ALIGN (Jia et al., 2021) 1) as feature extractors and provide weak supervision for a downstream target task via prompts, which are text descriptions of the desired tasks that are often significantly easier to obtain compared to full model weights or even a generic linear classifier over the last layer. The versatility and performance of prompting pretrained models have led to the rise of prompt engineering. an emergent paradigm in machine learning where practitioners carefully design the task specification in text or even learn the prompts in a data-driven fashion (Lester et al., 2021). ). For example, to obtain two-class image classifier, would write two sentences that describe the classes (e.g., "Thi is

---

Published as a conference paper at ICLR 2024
Table 1: Comparison with existing state-of-the-art generalization bounds for test error on different datasets. We report both data-independent and data-dependent bounds (* indicates data-dependent prior and indicates that the bounds not available). Note that different works use different architectures and analytic tools so direct comparison can be more nuanced. Nonetheless, our bounds on prompt engineering are significantly tighter than the existing PAC-Bayes bounds in the literature, often within few percent of the actual test error.
PAC-Bayes (prompt)
Dataset
Zhou et al. (2019)
Dziugaite et al. (2021)
Lotfi et al. (2022)
CIFAR-10
0. 0.230*
0.582 0.166*
0.063
CIFAR-100
0.946
0.444*
0.266
ImageNet
0.965
0.930 0.409*
0.319
dog" and "This is a cat"), and the two sentences are turned into text embeddings which can be used classify image embeddings. Despite its empirical success, little is understood of how and why prompting these pretrained models work and, in particular, why the method seems to suffer little from overfitting: manually tuning or even greedily optimizing prompts given training set often performs nearly as well on the corresponding test set.
In this paper, we demonstrate that rather simple analysis tools capture this behavior surprisingly well (under some assumptions). In particular, we show that classical PAC-Bayes bounds (McAllester, 1999), when applied to the discrete hypothesis class defined by prompts (and specifically with a prior given by a large language model), are often remarkably tight, even for large domains: for example, we achieve a generalization bound of 32% error for a full ImageNet classifier, which is within 6% of the actual test error. This represents a vast improvement over existing bounds for deep learning, where achieving any non-vacuous bound on domains like ImageNet typically requires a great deal of effort; see, for instance, Table 1 for a comparison with other approaches. Perhaps more interestingly. our bounds do not depend on the training data as the prior approaches do but instead depend on the pretraining data of pretrained model (e.g., CLIP) through the image encoder.
To summarize, we find that, unlike conventional deep learning models, prompting pretrained models does not suffer from vacuous generalization bounds, and one can readily derive a strong theoretical guarantee for using prompts via well-studied techniques. Overall, these findings suggest that, despite a large amount of automatic or manual tuning, prompt engineering is principled approach for using these pretrained models that do not suffer the same lack of theoretical grounding as conventional deep learning models. On the other hand, it does introduce its own set of considerations, which we will discuss in the experiments section and conclusion.
RELATED WORKS
Prompt Engineering. With the advent of large pretrained models, prompting developed as a different yet effective method to harness the abilities of these large models with limited labeled data (Brown et al., 2020; Le Scao & Rush, 2021; Liu et al., 2023). The flexibility of prompting has enabled a wide range of new capabilities unavailable to previous machine learning models, leading to a significant effort document successful prompting methods (Bach al., 2022) in both classification and text-to-image generation. One downside of prompting is that the performance varies greatly depending how the prompt is phrased. To address this issue, several methods have been proposed to learn "optimal" prompts given labeled data, which empirically performs well and is parameter efficient (Lester et al., 2021: Li & Liang, 2021: Gao et al., 2021: Zhou et al., 2022a;b). A limitation of data-driven methods is their tendency to learn "soft" prompts or embedding vectors that do not correspond to specific tokens. Moreover, from learning theoretic perspective, the continuous nature of soft prompts, combined with transformations by non-linear models, results in a complex hypothesis space, making it less amenable to theoretical analysis. In contrast, another line of work uses gradient- based methods to learn prompts that consist of discrete tokens that can be mapped to natural language (Wen et al., 2023). This work studies the theoretical guarantees of the latter
Depa-depnnd priors primarily refer to the setting where a portion of training data is used to obtain prior that is closer to the final posterior. We note that in our setting, the training of pretrained models uses data from different distributions and does not use any training data from the task of interest.
2

---

Published as a conference paper at ICLR 2024
approach, that is, why these discrete prompting methods seem to work without any overfitting, and our analysis extends to the methods proposed in Wen et al. (2023).
Prompt engineering has been extended to computer vision through CLIP (Contrastive Language- Image Pretraining) (Radford et al., 2021). CLIP combines an image and language encoder trained jointly to minimize a contrastive loss, enabling it to perform classification tasks based on natural language instructions. Examples include object recognition, image caption generation (Tewel et al., 1), and zero-shot image classification using textual descriptions even for unseen labels.
Generalization bounds. Generalization bounds are upper bounds on the test error of a model. Deriving such bounds for deep learning has been difficult, and most are usually vacuous (Zhang et al., 2021; Jiang et al., 2019; Dziugaite et al., 2020). Many well-studied tools in statistical learning theory are fundamentally limited when it comes to the analysis of deep neural networks (Nagarajan & Kolter, 2019b). The core component of a generalization bound complexity measure, a quantity that relates to some aspect of generalization. A complexity measure may depend on the properties of the trained model, optimizer, and possibly training data, as long it does not have access validation set. The most classic bounds, such as VC-dimension (Vapnik, 1971), are often related to some form of parameter counting which is often too pessimistic for deep neural networks. bose- bounds usually rely on the margin and some norms of the model weights (Langford & Caruana, 2001; Bartlett et al., 2017; Neyshabur et al.. 2015: 2017b), 7b), but these bounds have been ineffective at studying generalization of deep learning (Nagarajan & Kolter, 2019a). Another main class is the PAC-Bayes bounds (McAllester, 1999) which have been much more successful in deep learning due to the flcxibility of prior (Neyshabur et al., 2017a; Dziugaite & Roy, 2017; Zhou et al., 2019; Lotfi et al., 2022), although these bounds are still much looser than the actual generalization error. Our approach also belongs to the PAC-Bayes family, but apply the PAC-Bayes bounds to the distribution of discrete tokens (with a language model as the prior) rather than to a distribution over the parameters of a neural network. This allows us to derive significantly tighter bounds compared to applying the PAC-Bayes bounds with less informative priors.
PRELIMINARIES
Notations. Let X' E Rd be set of imputs and y = [K] be label set, and there exists probability
distribution D on (X'x ()) which is unknown. Let our data ( Yi)...).... (Xn, Y,) be drawn i.idd from D, and consider predictor f: X + y' and a fixed set of predictors indexed by the parameter set O. We use So to denote the classifier indexed by We consider the 0-1 loss given by f(y'.y) = 1yy= of y'}. The generalization error (risk) of a predictor is defined as R(0) = E(x,r)-p(((oo(X)
and the empirical risk r(0) 1 En= ((f Y,) satisfies [s(r())] = R(0) for sample S =
[(X1, ()). (Xn, Y.) An estimator is a function 0 U (X x 3)"" +
Vision-language models. CLIP consists of two encoders enCing and entCrtt Given an image X E X, the image encoder enCing X - Rd maps an image X to d-dimension real-valued embedding. Let ' be the space of texts and T E T single piece of text, the image encoder enc T+R2 12d maps T to d-dimension real-valued embedding. Given a batch of images { and their corresponding texts {T.) 1 the training objective maximizes the cosine similarity of the embeddings of the matching image and text pair and minimize the cosine similarity of image and text pairs that do not correspond to each other. The primary task we consider in this work is image classification via pretrained vision-language models. The goal is to find a class prompt, 0h T, for each class that achieves good accuracy. For K-class classification problem with 0 (0) 0 ...., 0²) E θ 7K (enCux (8h), enCing (x))
the zero-shot classifier is fo (X) = arg [a
Generalization bounds. Deriving generalization bounds is closely related to assigning hypothe- ses prior probabilities of being good (Shalev-Shward & Ben-David, 2014). One of the simplest approaches uses uniform convergence over the entire discrete hypothesis space (where | denotes the number of functions in the class) to derive the well-known generalization bound,
Theorem 3.1 (Shalev-Shwartz & Ben-David (2014)). For every 8 > 0, with probability 1 - 5 over the training set of size n, for any hypothesis 0 Q the following holds R(0)- S r(0) + log (e) +log(h)
2n
3

---

Published as a conference paper at ICLR 2024
This result does not consider the implicit bias of the learning algorithm (Neyshabur et al., 2014), the training data S, or the data-genera distribution D. In contrast, the PAC-Bayes framework offers flexible approach for leveraging this information by defining hierarchy over hypotheses in the hypothesis class θ that takes the form of prior distribution P over θ That is, we assign probability P(O) 2 0 for each 0 E θ and refer to P(0) as the prior score of 8. The learning process defines a posterior probability over θ, which we denote by Q. In the context of supervised learning, we can think of Q as defining the following prediction rule: given an instance X, we randomly pick hypothesis 0 according to Q and predict fe(X). Remarkably, it was shown that the expected generalization gap can be upper bounded by the KL-divergence between P and Q:
Theorem 3.2 (McAllester (1999)). For every 5 O, prior P over θ with probability 1 over the training set of size n. for any posterior Q over θ the following holds
[R()) - (0020/((00]
/
DR P) + log( +2
(1)
2n 1
4 METHODOLOGY
Designing a prompt is analogous to finding a set of weights in typical machine learning models, where the hypothesis space is the space of texts/tokens. The goal is to find class prompts that maximize training accuracy without finetuning the model's parameters. This process, which is often referred to as prompt engineering, can be formulated as discrete optimization over the space of tokens, V.
4.1 PROMPT SEARCH
To study the generalization capabilities of discrete prompts, we consider a simple greedy search algorithm that mimics an overeager prompt engineer who exhaustively tries adjusting prompts with every possible word, although the analysis extends to other techniques that produce discrete prompts. To find class prompts of length L, we will search for K L tokens over the space, VK- Naively, this search is exponential in the length of the prompt so to circumvent this problem, the prompts are generated successively; that is, we increment the prompts by selecting the token that maximizes search criterion, J. on the training dataset from set of candidate tokens, V C V. With slight abuse of notation, we will use (0) denote a candidate set that can be conditioned on the current 0.
The search criterion is the objective being optimized (e.g., the empirical loss), and candidate tokens permissible tokens that can be used to extend the current class prompts. At every step of the search, we keep the class prompts fixed except for all but one class. The prompt for each class
a sequence of tokens of E V. - (0), 0g .., ,0²) .0)) where < T., and we use 6-* to denote the class prompts for all classes that are not the 1 class. The next token for g is obtained via:
o = arg max Ju, 2 )))
(2)
vED(A)
The pseudocode for this sequential search is outlined in detail in Algorithm 1.
Empirical risk minimization. Using + to denote concatenation, we consider a simple form of search, greedy search, where
gyneedy (0) = Teeedy (v. - 8b + u. gh+1 (b+1.....))
(3)
where r is the empirical risk in terms of the 0-1 loss (see Section 3). In other words, we always search over all possible tokens (line 6) to maximize the training accuracy. This greedy search is an empirical risk minimization (Vapnik, 1991, ERM) learner since its only objective is to minimize the training error. There are several drawbacks to this simple algorithm, the chief of which is that we need to search over V exhaustively at each step, which can be expensive since it consists of all the tokens of the vasion-language model (e.g., CLIP has about 50000 tokens). Instead, we could search over only a a language model (LM) to induce distribution over
subset of V. To reduce this search space, the next tokens conditioned on 8 and only evaluate the tokens with high probabilities:
Pnext (0 105))= = PLM (0% 0 (0), 0g. . ... 0/))
(4)
4

---

Published as a conference paper at ICLR 2024
Given that CLIP is trained with natural language supervision, autoregressive LMs that are also trained on natural language can likely predict suitable next tokens. We then take the top N candidates and only evaluate the accuracy of these candidates. Conveniently, this can be seen as constraining the complexity of the prompt as the language model provides a structured prior. We observe that this pruning incurs minimal performance loss, suggesting that LMs indeed are good prior in searching for class prompts image classification tasks. Furthermore, we may use predefined strings further constrain the hypothesis space by starting with an initial prompt such as "This s is an image of [...]' I", instead of an empty string. These initial prompts can provide additional structure to the generated prompts by constraining the output distribution, similar to the role of inductive bias. We refer to this method as Greedy.
Structural risk minimization via PAC-Bayes. This procedure can be further augmented to opti- mize the PAC-Bayes bound via structural risk minimization (Vapnik & Chervonenkis, 1974, SRM) similar the approach of Dziugaite & Roy (2017), namely, we will take the hypothesis complexity (e.g.. KL-divergence) into account as we search for the next token for each prompt. We use the KL-divergence directly in the objective optimization without sacrificing the quality of the solution. Once again, we do this optimization in a sequential manner via Algorithm 1:
(f) = - E V max Puesa (1' (5))) Puexi (v 0 S = JL((U, 0 o x*)
(5)
of
gh- , ① gh+1 .....) )) + 3 log Prea( (
(6)
where A controls the size of the search space (adjusted according to computational constraints) and is a hyperparameter that controls the strength of the regularization. This set of permissible tokens could also be pruned and fixed beforehand by discarding tokens with low marginal probability. We refer this version of search as regui arized greedy.
4.2 GENERALIZATION GUARANTEES FOR PROMPTS
Since the space of all prompts is discrete and the total number of possible prompts is |o] = |V|.K for single hypothesis Ó, we have the following uniform convergence bound for prompts that depends on prompt length, the number of classes, and the number of tokens in the vocabulary by assigning uniform probability to each hypothesis (from Theorem 3.1):
LK log |V| + log(!)
R(O)= < r(0) +
2n
However, not all prompts are equally likely to be good. To obtain a tighter generalization guarantee on the learned Ó, we will leverage a classical PAC-Bayes bound to derive an upper bound on the generalization error of the learned prompts.
In conventional application of PAC- to deep learning. P and Q are often chosen to be isotropic Gaussian on the parameters (Langford & Caruana, 2001) so the KI-divergence between the prior and posterior can be easily computed. We instead use a language model as the prior over K independent prompts, P(0)- = P (- Further, we treat the prompts 0 found through search or through prompt engineering as point mass posterior, Q(6) 1 0). In this case, the KL-divergence is conveniently equal to the negative log-likelihood of á under the LM because the posterior is zero everywhere except for at 0:
DKL (Q1
Q log P(Ø) = log P(O)
Q(0)
ΣΣ 1=1 i=1
K T.
log PLM
(0)
0%
(8)
dE@
This bound has an intuitive interpretation, which is that the generalizing prompts are the ones that achieve good training performance and are likely under the language model. Having point- mass posterior over discrete space also means that we can derandomize the PAC-Bayes bound for free (Viallard et al., 2021). Combining these observations, we have the following deterministic upper bound on the generalization error (from Theorem 3.2):
K 1 E
log PLM 0
(s)) + log( (o) +
R(O) < (()) +1
(9)
2n
5

---

Published as a conference paper at ICLR 2024
Table 2: Performance and generalization bounds for prompts produced by Greedy and for hand- crafted prompts on different datasets with different CLIP architectures. UC represents the uniform convergence bound. Handcrafted prompts are taken from CLIP and Wise-FT (Wortsman et al., 2022).
Dataset
Model
Method
Train Err
Test Err
UC
PAC- MAC-Bayes
CIFAR-10
B-16
Greedy
0.050
0.060
0.154
0.086
L-14
Greedy
0.023
0.028
0.128
0.063
L-14
handcrafted
0.040
0.040
0.145
0.078
CIFAR-100
B-16
Greedy
0.208
0.255
0.537
0.317
L-14
Greedy
0.142
0.180
0.471
0.266
L-14
handcrafted
0.221
0.221
0.549
0.339
fMoW
B-16
Greedy
0.598
0.621
0.807
0.667
L-14
Greedy
0.514
0.547
0.723
0.596
L-14
handcrafted
0.725
0.402
0.934
0.804
OfficeHome
B-16
Greedy
0.104
0.150
0.635
0.281
L-14
Greedy
0.070
0.115
0.601
0.260
L-14
handcrafted
0.926
0.928
1.457
1.119
ImageNett
L-14
handcrafted
0.243
0.256
0.448
0.319
CIFAR-10 [Greedy]
CIFAR-100 [Greedy]
OfficeHome [Greedy]
0.08
converg ence
0.300
Uniform convergence PAC-Bayes
Uniffrm convergence
PAC-Bayes
PAC Bayes
Test ereer
0.06
enoe
0.275
enor
0:500
0.20
0.225
0.15
0.200
Bound
Bound
Figure Test eтrоr vs generalization bound on CIFAR-10, CIFAR-100, and OfficeHome. We compare the uniform convergence bound and PAC-Bayes bound, when evaluated on prompts produced by Greedy. The dashed line represents y = s.
We note that these techniques are not novel from a theoretical perspective and there are more sophisticated PAC-Bayes variants that may yield tighter results. Nonetheless, in the next section, will observe that this simple bound is surprisingly tight even for complex datasets such as ImageNet.
Data leakage and contamination. One strong assumption of these bounds, which we make explicitly and which could indeed be violated in practice, is that the image encoder is trained without access to the training set used for prompt engineering. If it is trained on this data, even from the training set, then the functional complexity of the hypothesis class depends not just on the prompt, but also implicitly on the complexity of the image encoder. We emphasize that this fact does not change the nature of the bounds above, but it does change whether or not any given bound in the experiments can be formally considered valid bound, or could be violated.
In practice, this is difficult to verify for the c.g. CLIP encoder, since the data it was trained on is not publicly disclosed. Nonetheless, the CLIP paper includes sensitivity analysis that shows relatively small effect of including any of the evaluation datasets they consider (Radford et al., 2021). ). Thus, while we fully acknowledge that data contamination may apply to the experiments below, we believe this to be similar to many current evaluations of foundation models, where it is difficult to assess the extent to which any performance truly zero-shot.
EXPERIMENTS
In this section, we evaluate the generalization of discrete prompts generated by Greedy on CIFAR- 10, CIFAR-100, ImageNet as well as domain generalization datasets fMoW (Christie et al., 2018) and OfficeHome (Venkateswara et al., 2017), which is much less studied in the context of numerical

---

Published as a conference paper at ICLR 2024
CIFAR-10 [Hand-crffted]
CIFAR-100 [Hand-crafted]
OfficeHome (Hand-crafted
PAC Bac-Bayos
0.36
PAC-Bayes
PAC-Bayos
0.09
0.34
5 0.95
0.08
0.32
0.07
0.30
2
0.06
0.28
1 0.93
0.05
0.04
0.24
0.93
0.22
0.92
0.07 0.09
10.0.11.000111111111011111001111 Bound
0.12
0.13
0.320.340.360.0
440.4600.45
1.09
1.12
1.13
Bound
Bound
Figure 2: Test error vs PAC-Bayes generalization bound on CIFAR-10, CIFAR-100, and OfficeHome on handerafted prompts. The dashed line represents y 22
CIFAR-10 [Greedy]
CIFAR-100 [Greedy]
OfficeHome [Greedy]
PAC Bayes
0.30
PAC Bayes Train 0-1 error
PAC-Bayes arror
Train 0-1 error
0.06
0- erro
0.28
Test crrar
Teat 000.1
0:25
0.20
0.04
0.23
0.15
0.20
0.02
0.05
0.10
0.15
0.20
0.20
0.40 0.60
0.20
0.40
0.60
0.80
Figure 3: Train error (orange) and generalization bound (blue) test error (y-axis) CIFAR-10. CIFAR-100, and OfficeHome of prompts produced by Greedy. The dashed line represents y = x. Notice that towards the region of low training loss (left), many prompts actually have higher test loss (negative correlation). On the other hand, the low bounds correlate with low test errors well.
generalization bounds. We also evaluate existing rell-performing handcrafted prompts taken from CLIP and Wise-FT (Wortsman et al., 2022). Given these prompts, we compute generalization bounds via PAC-Bayes are computed using LLaMA-7B (Touvron et al., 2023) as the prior. Within Greedy, we search using the CLIP vocabulary of 49 408 tokens and measure the generalization bounds for 100 realizations of Greedy with each corresponding to a fixed prompt length E {l...., 10} and split portion of the dataset 8 E (0.1..... 1.03. More details on the experimental procedure are in Appendix C.
and via uniform convergence (UC). The PAC-Bayes bounds
Baselines We compare our generalization bounds against existing generalization bounds on CIFAR- 10, CIFAR-100, and ImageNet. In particular, we compare against the works of Lotfi et al. (2022) and Zhou et al. (2019), which represent the latest progress in PAC-Bayes bounds for deep learning.
As shown in Table 1, discrete prompts achieve much tighter bounds than the state- of-the-art art across all 3 datasets. We remark that our approach also data-independent, while still achieving a tighter bound than the data-dependen approach in the work of Lotfi et al. (2022). An added benefit of this result is that we make little modification to the existing learning paradigm indeed prior bounds often need to make strict as- sumptions about the neural network such as Gaussian posterior or the weights lying in low dimensional manifold (Lotfi al., 2022) which may hurt the performance.
CIFAR-10
CIFAR-10
ERM
6.25
0.15
crrorr
8.15
0.10
8.10
0.05
0.05
0.10
0.15
0.20
0.25
0.30
Board
standard cextation
Figure 4: Test error vs the PAC-Bayes bound on CIFAR- 10 when using SRM (i.e., directly penalizing the PAC- Bayes bound) (left). We also report the train and test performance when the CLIP vocabulary is pruned (i.c., removing tokens that have logit values that are & stan- dard deviations away from the max token) using the lan- guage model (right). This yiclds prompts with tighter bounds at the cost of slightly higher error.
We observe that even simple UC bounds over discrete prompts generated by Greedy lead to tight, non-vacuous bounds across a variety of datasets, and PAC-Bayes bounds with an LLM prior further improve these bounds (Figure 1). These also apply to handcrafted prompts (Figure 2) from the existing literature (Radford et al., 2021; Wortsman et al., 2022) (other datasets' result in Appendix B).
7

---

Published as a conference paper at ICLR 2024
Structural risk minimization with the PAC-Bayes bound PAC-Bayes is related to SRM (Vapnik Chervonenkis, 1974), where one tries to optimize both the goodness of fit and complexity of the model. When we compare test error against train error or the generalization bound (Figure 3), we observe that the generalization bound can serve as useful criterion for model selection. We consider using SRM, where our complexity term is exactly the KL divergence term in Equation 8. Regulare r zed Greedy now jointly maximizes train accuracy and minimizes this KI. divergence term when adding new tokens to each class prompt. We observe that this naturally leads to tighter bounds for prompts yielded by Greedy accuracy. Interestingly, using LLaMA-7B as the prior does not significantly improve the linguistic coherence of prompts obtained through regularized search, which leaves room for more sophisticated search techniques to address this future work.
CIFAR-10 (Figure 4) while maintaining comparable
Pruning the hypothesis space In addition to regularizing the search objective with the KL term directly, another method to improve our generalization bounds is to prune the vocabulary using a large language model. We experiment with conditioning the language model on the class names and then selecting tokens from the language model's 's vocabulary with the highest probability under the language model. In Figure 4, we report the performance and generalization of Greedy when the tokens considered in search are restricted to within l standard deviattios (see Appendix B.1 for details) away from the maximum logit token. While the vocabulary size of LLaMA-7b is 32 000 tokens, the number of tokens within 3, 2, standard deviations from the maximum token are 6894, 1361, 185 respectively. We observe this implicitly prunes the hypotheses to contain those with smaller generalization сттоr at a small cost to the train and test error. Restricting the vocabulary also encodes prior knowledge about the data or domain. For example, further results using a vocabulary of English words in Appendix B.1 (instead of CLIP's vocabulary of tokens) show that we can learn slightly more interpretable prompts.
Effects of prompt length Another key quantity of prompt engineering is the prompt length which di- rectly controls the size of the hypothesis space. We analyze how the length of class prompts impacts the performance of Greedy (Figure 5). We note that at certain length, the train accuracy plateaus, which means that relatively small prompt length suffices for good classification performance.
CIFAR-10
OFAR-100
Officettome
0.00
Tan0leen
Tain
0.72
Test
5.05
2.225
0.65
8.04
5.200
0.63
5.00
0.33
3.350
promst length
Figure 5: The train and test accuracy with different prompt lengths for greedy search. Although the generalization gap increases with prompt length, there little overfitting even at the longest lengths.
Fitting random labels Motivated by our new observations about prompt enginecring, we hy- pothesize that the learned prompts are less prone overfitting the noise in the data. Zhang al. (2021) showed that conventional deep neural networks can fit both random labels, arguing that these models have much higher capacity than what traditional statistical learning theory can deal with. To demonstrate that prompt engineering is robust to label noise, we experiment with running Greedy
Train D-1 error
Train D-1 emor
0.032
Train 0-1 emor
0.8
Test 0-1 crror
0.06
Test 0-1
0.030
Test 0-1
0.6
0.02
0.026
0.2
0.024
0.2
0.4
0.6
0.8
1.0
0.02
0.04
0.06
0.08
0.02
0.04
0.06
0.08
ratio flipped labels
data sample proportion
vorab sample proportion
Figure 6: We show the generalization of discrete prompts produced by Greedy on randomly labeled data from CIFAR-10 (left). We also report the performance when search is done with 1% 9% of the labeled data (middle), and when search is done with 1% 9% of the CLIP vocabulary (right). We fix the prompt length to be 5.
8

---

Published as a conference paper at ICLR 2024
Table Performance and generalization bounds for prompts produced by Greedy and for linear probe (on top of CLIP features) on different datasets with 20 samples per class. UC represents the uniform convergence bound. We omit UC for linear probing because this is a multi-class problem.
Dataset
Model
Method
Train Ert
Test Err
UC- 20
PAC- (CC--Bays-222 20
CIFAR-10
L-14
Greedy
0.020
0.138
1.675
0.634
L-14
Linear Probe
0.000
0.038
2.591
CIFAR-100
L-14
Greedy
0.156
0.367
1.801
0.637
L-14
Linear Probe
0.000
0.198
3.715
on training data with a certain proportion of randomly flipped labels. We observe that both training and test accuracy drop monotonically in tandem as we flip these training labels (Figure 6), which suggests that the prompts cannot overfit the random labels. For baseline comparison, we also compare the performance of linear probe random labels. We observe that this achieves roughly random performance (13 (13.60% accuracy) with 100% flipped labels. This supports that Greedy is not too simple of search approach to fit the random labels other more complex methods also cannot.
Learning with small data When the number of data points small (e.g., n = 20), the use of PAC-Bayes is especially attractive since we can use all the data points to estimate the posterior and bound its risk. Furthermore, prompt engineering frequently used with limited labeled data; thus, further progress in understanding its gencralization properties must provide bounds in this regime. In Figure 6, we report the train and test accuracy of Greedy as we vary the amount of training data (between 1%-10% of the full data) we use in computing the search objective. We observe less than 2% increase in error with 2% of the training set of CIFAR-10. This highlights that Greedy can be remarkably data efficient. We then compute both the uniform convergence and PAC-Bayes bounds with 20 samples per class (Table 3). The results underscore the importance of an informative prior in the form of the LLM. The bounds obtained with the LLM prior are, albeit loose but still non-vacuous. To the best of our knowledge, this is not possible with prior approaches unless it is data detta-deeedeet. One could ask since we assume the representation from CLIP can we simply use an SVM-like bound on the learned features (McNamara & Balcan, 2017)? As a case in point, we present standard linear probe (on top of CLIP's features), which achieves slightly better accuracy but a vacuous generalization bound. The implementation details are described in Appendix C. The discrete nature of prompts and the fact that the corresponding hypothesis space of CLIP is so small crucial to the success of our approach. We believe that exploring avenues to obtain tighter PAC-Bayes bounds in the small data regime is an opportumity for future work and the use of data-dependent priors may be fruitful in this regard.
learned from the training data,
6 CONCLUSION AND LIMITATIONS
In this paper, we study the generalization properties of engineered prompts on image recognition tasks. We observe the surprising fact: prompt engineering does not seem to overfit, and also performs well on the test distribution. We provide principled approach to analyze this generalization behavior by framing discrete prompts as a relatively small hypothesis class, onto which we can naturally apply classical PAC-Bayes bounds using an LLM prior. This results in the tightest bounds yet observed across multiple complex datasets, including CIFAR-10, CIFAR-100, 100, and ImageNet. As a whole, this simple greedy searches over potential class prompts as
supports the use of prompt--ngineering high-performing and well-generalizing classifier.
Despite the ability to produce highly non-vacuous bounds, the bounds rely on the fact that pretrained vision-language models readily contain some hypothesis class that will perform well on the training set (for whatever the desired task is). This, in turn, naturally relies on the generalization performance of the underlying model itself, which our analysis evidently does not, and cannot, address (as they are only aware the language model, which does not observe the data).
Nonetheless, what our bounds do address is the fact that when given these performant models, manual prompt engineering (even when "overfitting" generalization behavior. Given the prevalence of prompt engineering in modern MI., we believe that this work provides important perspective on this widespread practice.
training set) often exhibits surprisingly strong

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We thank Nina Balcan for valuable discussions during this project. Victor Akinwande, and Dylan Sam were supported by funding from Bosch Center for AI. Dylan Sam was also supported by National Science Foundation Graduate Research Fellowship under Grant No. DGE2140739 and the ARCS Foundation. Yiding Jiang is supported by the Google PhD Fellowship.
REFERENCES
Stephen Bach, Victor Sanh, Zheng Xin Yong, Albert Webson, Colin Raffel, Nihal V Nayak, Abheesht Sharma, Taewoon Kim, M Saiful Bari, Thibault Févry, et al. Promptsource: An integrated development environment and repository for natural language prompts. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pp. 93-104, 2022. 2
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normalizzdd margin bounds for neural networks. ArXiv, abs/ (oss/7706,,898, 2017. 3,
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal,
Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020. 2
Gordon Christie, Neil Fendley, James Wilson, and Ryan Mukherjee. Functional map of the world. In
CVPR, 2018. 6
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwarz. Multiclass learnability and the erm principle. Mach. Learn. Res., 16(1):2377-2 2404, 2015. 17
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprins arXiv:2010. 19999, 2020. 1
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 1008, 2017. 3,
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M Roy. In search of robust measures of generalization.
Advances in Neural Information Processing Systems, 33:11723-11733 2020. 3
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. the role of data in pac-bayes bounds. In International Conference on Artificial Intelligence and Statistics, pp. 604-612. PMLR, 2021. 2
Tianyu Gao, Adam Fisch, and Danqi Chen. Making pre-trained language models better few-shot learners. In Joint Conference of the 59th Annual Meeting of the Association for Computational Linguisties and the 11th International Joint Conference on Natural Language Processing, ACL- IJCNLP 2021, pp. 3816-3834 Association for Computational Linguistics (ACL), 2021. 2
Chao Jia, Yinfei Yang. Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc Le, Yun-Hsuan Sung, Zhen Li, and Tom Duerig. Scaling up visual and vision- language representation learning with noisy text supervision. In International Conference on Machine Learning, pp. 4916. PMLR, 2021. 1
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv: 2019. 1, 17
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXhv:2001.0836/ 2020.
John Langford and Rich Caruana. (not) bounding the true error. In NIPS, 2001. 3.5
10

---

Published as a conference paper at ICLR 2024
Teven Le Scao and Alexander M Rush. How many data points is prompt worth? In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2627-2636, 2021. 2
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt
tuning. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 3045-3059, 2021. 1,2
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the Ith International Joint Conference on Natural Language Processing (Volume I: Long Papers), pp. 4582-4597, 2021. 2
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9):1-35, 2023.
Sanae Lotfi, Mare Finzi, Sanyam Kapoor, Andres Potapczynski, Micah Goldblum, and Andrew G Wilson. Pac-bayes compression bounds so tight that they can explain generalization. Advances in Neural Information Processing Systems, 35:3 1459-3113,,,, 2022. 2.
David A McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth anmual conference on Computational learning theory, pp. 164-170, 1999. 3.4
Daniel McNamara and Maria-Florina Balcan. Risk bounds for transferring representations with and without fine-tuning, In International Conference on Machine Learning, pp. 2373-2381. PMLR, 2017. 9
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprint arXiv:1901.01672, 2019a. 3
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019b. 3
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint 141.6661 2014. 4
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. ArXiv, abs/1503.00033, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring gen- cralization in deep learning. Advances in neural information processing systems, 30, 2017a.
Behnam Neyshabur, Srinadh Bhojanapalli, David A. McAllester, and Nathan Srebro. A pac-bayesian approach to 2017b. 3,
margin bounds for neural networks. ArXiv, abs//100 0996444
Alec Radford, Jong Wook Kim, Chris Hallacy. Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748 8763. PMLR, 2021. 6,
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Yoad Tewel, Yoav Shalev, Idan Schwartz, and Lior Wolf. Zero-shot image-to-text generation for visual-semantic arithmetic. arXiv preprini arXiv:2111. 1...24471.4447, 2021. 3
Hugo Touvron, Thibaut Lavril, Gautier Izacard. Xavier Martinet, Marie-Anne Lachaux, Timothéc Lacroix. Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. arXiv preprint 13X,,, 2023. 7
Vladimir Vapnik. Principles of risk minimization for learning theory. Advances in neural information processing systems, 4, 1991. 4
11

---

Published as a conference paper at ICLR 2024
Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974. 5,
Vladimir Naumovich Vapnik. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities. 1971. 3
Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5018-5027, 2017. 6
Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. A general framework for the disintegration of pac-bayesian bounds. arXiv preprint arXiv:2102.08649, 2021. 5
Yuxin Wen, Neel Jain, John Kirchenbauer, Micah Goldblum, Jonas Geiping, and Tom Goldstein.
Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery. arXiv preprint arXiv:2302.03666 2023. 2,3
Mitchell Wortsman, Gabriel Ilharco, Jong Wook Kim, Mike Li, Simon Kornblith, Rebecca Roelofs, Raphael Gontijo Lopes, Hannaneh Hajishirzi, Ali Farhadi, Hongseok Namkoong, et al. Robust fine-tuning of zero-shot models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7959-7971, 2022. 6,
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021. 3,
Kaiyang Zhou, Jingkang Yang, Chen Change Loy, and Ziwei Liu. Learning to prompt for vision- language models. International Journal of Computer Vision, 130(9):2337 -348,, 2022a.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan Adams, and Peter Orbanz. Non-vacuous generalization bounds at the imagenet scale: A pac-bayesian compression approach. In 7th International Conference Learning Representations, ICLR 20/9, 2019. 2, 3,
Yongchao Zhou, Andrei loan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. arXiv preprint arXiv:2211.01910, 2022b.
12

---

Published as a conference paper at ICLR 2024
A PESUDOCODE
Algorithm Sequential Prompt Search
1: < [initial prcipppt_ppppp]t
2: for [ t - do
3: class _las__order= f- randomly sampled order of class indices
4: for k in wwwsslllssssaee _arrsrrrrrrr_eee do
5: criteria -00
6:
for v in V(() do
This step is vectorized in practice. b Evaluate the score of v. Keep the prompt with best performance. & Update the current best score. > Update 0 with the better token.
7:
score t [w, 0% 0 k
8: score criteria then criteria &- score 0f 01 +
9:
11:
Return 0
B ADDITIONAL RESULTS
Other datasets We report the results of discrete prompts both generated by Greedy and hand- crafted on FMoW Figure 7.
fMoW [Greedy]
fMoW [Greedy]
fMoW (Hand-crafted)
0.70
PAC-Bayes
0.84
PAC-Bayes
Test 0.1 error
Train 0-1 emrrr
0.82
0.65
Test 0-1 enor
0.80
Unitorm convergence
0.65
PAC Bayes
0.78
0.60
0.76
0.74
0.55
0.55
0.72
0.6
0.7
0.8
0.9
0.80 0.82
0.84
0.86 0.88 0.90 0.92 Bound
Bound
0.50
0.60
0.70
Figure 7: Test error vs generalization bounds on fMoW. We report the uniform convergence bound and PAC-Bayes bound when evaluated on prompts produced by Greedy (left). We plot its train vs. test error (middle). We also report the performance of handcrafted prompts and their corresponding PAC-Bayes bound (right). The dashed line is T.
Creating the pruned vocabulary To create the pruned vocabulary, we take the class name each class (e.g., "dog"") and feed each one into the LLM and compute the logits over the next token. We then compute the standard deviation, a, over each class's logits and take the tokens that are ko from the maximum logit. Then, we use the union of the top tokens of all classes as the pruned vocabulary.
Vocabulary subsampling In addition to the result on CIFAR-10 in Figure 6, we report the per- formance of discrete prompts generated by greedy on CIFAR-100, when a random subset of the CLIP vocabulary is used in Figure 8. We observe less than 2% increase in error with 1% of the vocabulary. This provides further evidence of the robustness of Greedy to the vocabulary size. Random sampling, while easy implement, prunes hypotheses that may have desirable properties. As such, we report the performance of greedy on CIFAR-100 when the vocabulary pruned using the language model, and observe that Greedy can recover prompts with better generalization (See Figure 9).
Fitting random labels In addition to the result on CIFAR-10 in Figure 6, we report results on fitting to randomly labeled data for CIFAR-100, FMoW, and OfficeHome in Figure 10, and observe consistently that Greedy does not fit random labels. This provides evidence that contrasts the current literature the ability of neural networks to easily fit random labels.
Fitting with small data In Figure 11 we report results on fitting to small sample sizes on both CIFAR-10 and CIFAR-100. We consider random subsets between 1% 10% of the data and between
13

---

Published as a conference paper at ICLR 2024
C1AM-110
CIR48-100
0.032
0.19
0.030
0.18
0.026
0.17
0.026
0.16
0.024
0.15
0.02
0.04
0.06
0.08
0.02
0.04
0.06 0.08
vocab sample praportion
vocDD sampl: proportion
Figure 8: We show the generalization of Greedy when search is done with 1% 9% of the tokens sampled randomly from the CLIP vocabulary on CIFAR-10 (left), and CIFAR-100 (right). We fix the prompt length to be 5.
CIFAR-10
CIFAR-100
Train 0-1 error
Train D-1 error
0.35
0.15
Test error
0.30
0.10
0.25
standard deviation
standard deviation
Figure 9: We show the generalization of Greedy when search is done with subsets of the tokens sampled from the language model as described in the text on CIFAR-100eff), and CIFAR-100(righ) We fix the prompt length to be 5.
CIFAR-10 10
CIFAR-100
1.0
Jain 0'9
The
0.8
0.6
0.6
0.2
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
FMoW
OfficeHome
1.0
0.9
0.8
0.6
0.7
0.4
0.2
0.6
ratio of flipped labels
ratio of flipped labels
Figure 10: We show the generalization of Greedy with randomly labeled data on CIFAR-10, CIFAR- 100, FmoW, and OfficeHome. We fix the prompt length to be 5.
0.1% - 1%. We observe that the discrete prompts that Greedy can learn, even with small sample sizes, observe good generalization that degrades the sizes of the training set decrease.
Learning with a diff'rrnt vocabulary The Greedy algorithm is agnostic to the set of tokens used in the search procedure. In practice, one may use a vocabulary that encodes prior knowledge about the data or domain. Additionally, certain properties like interpretability may desired. We report results on searching with the language model's 's vocabulary (See Figure 12). We do not observe significant degradation performance. We also report results penalizing the search criteria using the bound (i.e. SRM) with different 3 values (See Figure 13). We observe that Greedy is able to recover prompts with better generalization as the penalty increases small cost to accuracy. We run Greedy on a vocabulary of English words obtained from the english-words* package. We show the prompts learned on CIFAR-10 in Figure 15.
Phttps://gi thub. com cowb.com/mwi..it
ens /eng1 ish-words-py
14

---

Published as a conference paper at ICLR 2024
CIAAR-30
CITAR-300
CIAR-10
CIAA--120
0.96
630
0.8
6.00
020a sample plpportion
03to sample praportion
0003 sample proporton
024a Samplec proparsinn
Figure 11: We show the generalization of Greedy when search done with 1% sampled randomly CIFAR-10 (left), and CIFAR-100 (second-left). We also show the generalization of Greedy when search done with 0.1% 0.9% of the data sampled randomly on CIFAR-10 (second-right), and CIFAR-100 (right). We fix the prompt length to be 5.
9% of the data
CIFA
CIFAR 120
3.2
0.1
0.10
125
prompt leigth
promptienge lemple
Figure 12: We show the generalization of Greedy with the Llama-7b vocabulary on CIFAR-10 (left) and CIFAR-100 (right).
03A8-110 8-1.
OFAR-10 8m1.29
0.08
0.08
0.06
0.06
0.04
0.04
prompt length
prompt length CIFR-100
CIRAR.10 3-167
0.08
0.06
0.04
prompt longth
promot length
Figure 13: We show the generalization Greedy with the LLaMA-7b vocabulary on CIFAR-10 with different values of penalty / with the SRM objective.
B. PROMPTING THE LANGUAGE MODEL BEFORE SEARCH
Prompt prefixes We prefix Greedy with:
1. a photo of
2. a blurry photo of
3. a black and white photo of a
4. a low contrast photo of a
5. a high contrast photo of a
6. a bad photo of a
7. a good photo of a
8. photo of small
15

---

Published as a conference paper at ICLR 2024
9. photo of big
10. photo of the
show the performance on CIFAR-I0 in Figure converges to prompt with roughly the same test-error regardless of the prefix.
We observe that Greedy consistently
CIFAR-10 (Prefix Greedy]
CIFAR-10 [Prefix Greedy]
Test 0-1 error
Bayes
0-1 errrr
0.06
PAC-
Train D-1 emoor
Train 0-1 erro
0.06
0.04
0.02
0.02
0.04
0.06
0.08
0.10
0.12
0.02
0.04
0.06
0.08
0.10
0.08
Rest 0-1 error
0.06
0.04
0.04
0.02
0.02
0.02
0.06
0,08
0.10
0.02
0.04
0.06
0.08
0.10
0.12
Test 0-1 errer
0.10
0.04
Text 0-2
0.05
0.02
0.02
0.06
0.10
0.14
0.08
Test 0-1 ertor
0.06
0.04
Test
0.02
0.02
0.08
Test 0-1 ereor
0.06
0.06
0.04
Text
0.04
0.02
0.02
0.04
0.08
0.12
0.06
0.08
Figure 14: When Greedy is prefixed with set of tokens, it consistently converges to prompts with with roughly the same test-error regardless the prefix.
[airplane, automobile, bird, cat, dog, frog,
truck]
aviarist nonsonant confirmment establishment hemiteraticn
nonmotoring known vaticinal allot nth
ornithophile slinsy renishly redivive nuchness
wheencat compearant stintedness osiery thisness
stagnature unchawed lophobranch primariness prinariness
dogrib babeoisn pneunococcic kaoliang bogusness
froggery phthalid auhuhu rippit hideousness
horsenanger fooyoung inordinary spreadingness forthbring
seafaring runness tralatition babeship knocking
truckLing phtherto senanto logy waywarden
Figure We show the learned prompts using full-word vocabulary of English words CIFAR-10. This achieves 3.3% test error with the L-14 base model.
16

---

Published as a conference paper at ICLR 2024
C EXPERIMENTAL DETAILS
Hyperparameters algorithm in Table 4.
We report the hyperparameters used CLIP, LLaMA-7b, and the Greedy
Table 4: Hyperparameters used in CLIP, LLaMA-7b and Greedy.
Value CLIP Vocabulary size
Hyperparameter
Batch size
100
49,408
LLaMA-7B Vocabulary size
32,000
Temperature
1.0
Bound
0.01
SRM |
1.0
Linear Probe Baseline A linear probe baseline trained with batch size of 64 and learning rate 0.01 for epochs. We compute the generalization bound using McAllester's bound with prior distribution over linear model weights of ((w!0) o² I) and a posterior of (ww, o²I), where I is an identity matrix of dimension (768 x the number of classes), w is our learned weights, and (())) is our random initialization. We then optimize over a grid of 20000 values for a E [0.1..... 1]. This mirrors the procedure from the work of Jiang et al. (2019). We also note that computing standard UC bound is challenging as we cannot specify a meaningful prior over an infinite space. Other approaches are challenging due to difficulties in computing multiclass analogues of the VC dimension such as the Natarajan dimension (Daniely et al., 2015).
17


Reviews:
[{"review_id": "8WwAwC4qVi", "reviewer": "Reviewer_DH9x", "summary": "The paper constructs (PAC-Bayes) generalization bounds using priors constructed from joint vision-language models. The found bounds are tighter than common bounds used for image classification with neural networks from scratch, which are usually tight unless data-dependent.", "questions": "I am mostly confused about the claims made in title, abstract, and introduction and otherwise found the paper interesting. The two things that bother me are the question of \"data-dependence\" and \"understanding prompt engineering\".\n1. data-dependent PAC-Bayes bounds would learn a prior on parameters based on a small pretraining dataset. This is extremely similar to the approach of pretraining a vision-language model. Would you disagree with this or see this differently?\n2. I did not have the feeling to improve my understanding of prompt engineering from the paper but rather has brought forward many interesting other aspects, especially that we can construct significantly tighter bounds for image classification for prompt-based classification than training from scratch.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- interesting and alternative perspective on prompting and construction of PAC-Bayesian bounds for modern deep learning methods\n- theoretical development well-written and easy to follow\n- find that prompt engineering for image classification provides relatively strong generalization guarantees and almost no overfitting in practice", "weaknesses": "- introduction/abstract somewhat oversell the paper and contradict later factual statements made in the paper (see issues of presentation below)\n- linear probe significantly better than using the greedy prompt search as shown in Tab. 3, which calls the performance of the greedy method into question and makes it unclear whether one should even use prompt engineering in such cases then despite the tighter bounds \n\n#### Issues of presentation\n- introduction & abstract dwell on the issue of classical deep learning PAC Bayes bounds, which are usually vacuous, unless conditioned on data. However, pretraining on a massive data set is rather similar to conditioning on data so I find this a bit inconsistent. I suppose it would be good to define data-dependent clearly if it applies to standard bounds but not the proposed one. Especially considering the likely case of data leakage into clip embeddings, claiming that the proposed method is not data-dependent seems inappropriate.\n- title claims \"understanding\" but the paper did not really provide a new understanding of prompt engineering, I would argue, and the authors seem to agree with this as can be seen in the 2nd paragraph of the conclusion. The 3rd paragraph of the conclusion is much more clear and honest given the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fBPL3lEhp3", "reviewer": "Reviewer_bDCR", "summary": "This paper proposes a new method to compute the generalization bound: by utilizing a language model to construct the prior and posterior distribution in the PAC-Bayes bound, the authors get a better generalization bound for prompt engineering for Vision-language models.", "questions": "Please see the weakness section, which criteria should be considered to test that a new generalization bound is significantly better? Also, is it possible to use similar ideas to analyze the (hard) prompt tuning in natural language processing? Besides, using the pre-trained LLaMA can improve the PAC-Bayes bound, is it some form of transferring the ''generalization problem'' of the prompt engineering to the generalization problem of the pre-trained language model?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is an important problem: understanding LLMs and other big models is an important problem. Computing or adding more insight into the generalization of these models is also important. The methodology seems interesting to me. The presentation is good.", "weaknesses": "It seems that the numbers between the UC and the PAC-Bayes, and I feel like there is not too much difference (most of them are within a factor of 2 or 3). I don't think the new generalization bound result is significantly different (although the method seems interesting to me), since scaling up the data by 4 to 9 times can reach nearly the same generalization error. Maybe more results with more scales helps.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "v7qw4vmTeQ", "reviewer": "Reviewer_q9H1", "summary": "This paper uses PAC-Bayesian theory to obtain generalization bounds for prompted classifiers, particularly prompted vision-language models like CLIP. By treating the space of (natural language) prompts as a parameter space, and using a generative pretrained language model as a prior over that space, with a posterior as the delta distribution on the prompt selected by some search procedure, very tight generalization bounds can be obtained for the prompted classifier. These bounds are tighter than other PAC-Bayes bounds in the literature, which were obtained for different model families.", "questions": "- Does prompting the language model differently induce a better prior? For example, if I prompt GPT-4 with \"I'm trying to prompt a vision-language model like CLIP to classify between cats and dogs. Can you suggest a good prompt?\" it replies: \"This image contains a {cat/dog}.\" So intuitively it seems like using the likelihood of possible CLIP prompts under this LM prompt would give a much better prior than off-the-shelf LLaMA, and it might also help with fluency. In general, it would've been interesting to see more ablation on the prompt used for the prior.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Combining PAC-Bayes bounds with the idea of treating prompts as tunable parameters is an interesting and original idea that seems promising for obtaining tight bounds, since the set of linguistically coherent task-specific prompts is a limited \"parameter space\", we know from existing empirical results that this set contains examples with low training error, and pretrained language models provide us with a natural choice of prior over this space.\n\n- The bounds obtained by the proposed approach are tighter than the bounds obtained by uniform convergence over the space of possible prompts and tighter than other PAC-Bayes bounds in the deep learning literature, including data-dependent ones (though those papers all consider different hypothesis classes).\n\n- Interesting results on non-vacuous generalization bounds for prompts in the very-low-data setting (20 samples per class). Since prompts are a hypothesis space with a strong prior, this model family seems like a very promising candidate for obtaining strong generalization bounds even in the few-shot-learning regime, which has been largely out of reach. These results push us towards such bounds.", "weaknesses": "- The proposed bounds are only evaluated on image classification tasks, but prompting and prompt engineering are equally if not more common in NLP for text classification and other tasks.\n\n- The abstract claims that \"the bound is remarkably suitable for model selection: the models with the best bound typically have the best test performance.\" Based on Figure 3, it seems like the bound is no more useful than just looking at the training error. But it's hard to tell because the points in the plot are not paired. Are there examples where using the PAC-Bayes bound leads to a different and better model selection choice than just using the training error? \n\n- _extends to the methods proposed in Wen et al. (2023)._ That paper has a much more sophisticated search method than the greedy search here. How do we know the resulting prompts are competitive with other search methods? It's less interesting if we're getting generalization bounds for a suboptimal classifier.\n\n- >both training and test accuracy drop monotonically in tandem as we flip these training labels (Figure 6), which suggests that the prompts cannot overfit the random labels.\n\n    - Either that, or the greedy search procedure just can't find a good enough prompt. As far as I can tell, we can't decide based on the evidence in the paper.\n\n- As far as I can tell, the analysis doesn't actually suggest a useful practical algorithm. Based on Figures 3 and 4, if I want to find the best prompt, it seems like my best bet is still to just pick the one that minimizes the training error (using whatever search method I come up with) and not bother with SRM.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bUJlWYhSzD", "reviewer": "Reviewer_miVF", "summary": "This paper provides a PAC-Bayes analysis of prompt engineering and a simple prompt search routine. The paper starts by proposing a simple greedy prompt search strategy that incrementally adds tokens that maximise the reward sequentially with a regularisation in terms of the probability of the next token as predicted by a language model. The authors then remark provide a PAC-Bayes bound for prompts by formulating the prompt search space as a hypothesis, the LM predicted token probabilities as priors and the posterior as a point mass. The authors show that the resulting bounds are surprisingly tight, and explain the observation that prompt engineering does not seem to overfit massively even though it is optimized on the training set only.", "questions": "Please address the concerns above.\n\n--- **Post-rebuttal** ---\n\nI thank the authors for responding to my review, and I remain positive about this work and its value to the community. I will stick to my original rating recommending acceptance (the reason I cannot give a higher rating is that this work, as mentioned in the original review, does have strong assumptions as also acknowledged by the authors).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper provides much-needed theoretical support for the increasingly popular paradigm of prompt engineering, which, as the authors described, is largely empirical up to this point. The use of PAC-Bayes theory in this context is intuitive and insightful and, to my knowledge, novel, and I'd even be a bit surprised that no one has tried this so far.\n\n- The derivation of bound, which is the paper's main contribution, is easy to follow and seems sound. The resulting bound is a massive improvement over the literature (although I am not extremely familiar with the literature in this area -- I defer a more thorough assessment to another, more experienced reviewer), and the experimental validation also provides empirical evidence supporting the authors' argument.", "weaknesses": "I'd like to state that I reviewed and participated in the discussion of a previous version of this manuscript at an earlier conference. The critical weakness is that, as the authors acknowledged in the latest manuscript, the validity of almost all derivations hinges on the assumption that there is no data contamination and that the encoder was not trained on the data that it is asked to infer (i.e., the setting is truly zero-shot). As the authors acknowledged, this is something that cannot be fully proved and disproved, partially due to the fact that what was included in the training data is not fully transparent and publicly known.\n\nHowever, as important as this weakness is, I think the dilemma is at least not only attributable to this work, and given the relative dearth of theoretical works on this area, I still think there is value in this paper to the community. I'd encourage the authors to emphasize more clearly and explicitly the limitations of their work and analysis throughout the paper. A possible remedy is to pre-train and fine-tune a comparable open-source model from scratch where one can fully control what data the model is trained on to investigate the derived bounds; I acknowledge this may require an enormous amount of compute and some qualitative discussions would suffice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)