# Automatic Engineering of Long Prompts

Cho-Jui Hsieh, Si Si, Felix X. Yu, Inderjit S. Dhillon
Google Inc.
{cjhsieh, sisidaisy, felixyu<EMAIL_ADDRESS>
###### Abstract

Large language models (LLMs) have demonstrated remarkable capabilities in
solving complex open-domain tasks, guided by comprehensive instructions and
demonstrations provided in the form of prompts. However, these prompts can be
lengthy, often comprising hundreds of lines and thousands of tokens, and their
design often requires considerable human effort. Recent research has explored
automatic prompt engineering for short prompts, typically consisting of one or
a few sentences. However, the automatic design of long prompts remains a
challenging problem due to its immense search space. In this paper, we
investigate the performance of greedy algorithms and genetic algorithms for
automatic long prompt engineering. We demonstrate that a simple greedy
approach with beam search outperforms other methods in terms of search
efficiency. Moreover, we introduce two novel techniques that utilize search
history to enhance the effectiveness of LLM-based mutation in our search
algorithm. Our results show that the proposed automatic long prompt
engineering algorithm achieves an average of 9.2% accuracy gain on eight tasks
in Big Bench Hard, highlighting the significance of automating prompt designs
to fully harness the capabilities of LLMs.

##  1 Introduction

Large language models (LLMs) have exhibited remarkable capabilities when
trained on large datasets, demonstrating the ability to comprehend complex and
lengthy instructions for diverse tasks without the need for fine-tuning Wei et
al. (2022a); Brown et al. (2020); Chowdhery et al. (2022); Ouyang et al.
(2022). Several prompt design principles have emerged in recent years,
suggesting that incorporating more complex instructions, demonstrations, and
chain-of-thought reasoning into prompts can boost the performance on
challenging tasks Brown et al. (2020); Wei et al. (2022b), including those
involving mathematical problem-solving Cobbe et al. (2021) and reasoning
Suzgun et al. (2022); Srivastava et al. (2022). However, effective prompts for
tackling complex tasks often contain thousands of tokens, posing challenges in
designing and optimizing them. Figure 1 demonstrates a long prompt for a task
in Big Bench Hard Suzgun et al. (2022), which contains an instruction and
several demos, each with human-written chain-of-thoughts.

Figure 1: Left panel: the average accuracy improvements of the proposed method
over 3 runs with 50 iterations on the training set. We report the accuracy on
the whole set (including training and test sets). More detailed results can be
found in Table 2. Right panel: An example of a long prompt in BBH
(Disambiguation task) which consists of an instruction, several demo examples
and chain-of-thought reasoning. We show that by rewriting a few selected
sentences in this long prompt with our proposed method, we can improve the
accuracy by more than 10%.

Numerous studies have demonstrated the sensitivity of LLMs to prompts,
revealing that minor modifications, such as adding or removing a few tokens or
rephrasing the prompt, can significantly impact LLM performance Liu et al.
(2023); Zhu et al. (2023); Jiang et al. (2020). Therefore, prompt design has
become a labor-intensive endeavor. Further complicating the matter is the
rapid evolution of LLMs, rendering prompts crafted for a specific LLM
ineffective when applied to a newer version of LLM. This highlights the need
for automatic prompt engineering techniques.

While automatic prompt engineering has been studied recently, existing
research Deng et al. (2022); Xu et al. (2022); Guo et al. (2023); Fernando et
al. (2023) focuses on optimizing short instructions with one or a few
sentences. These methods either evolve prompts by searching for word
replacements or utilize LLMs to rewrite the entire prompt Xu et al. (2022);
Fernando et al. (2023); Guo et al. (2023); Yang et al. (2023). It is
challenging to apply them for evolving a long prompt like Figure 1. For long
prompts, word replacement-based search faces an immense search space, while
rewriting the entire prompt using a single LLM query is extremely difficult.
Although it is possible to apply these methods to individual sentences within
a prompt, we have observed that tuning a single sentence may not sufficiently
improve the performance of long prompts (see Section 4). Therefore, how to
automatically find better long pompts and what’s the potential performance
gain by tuning long prompts remain unanswered in the literature.

The main operation in our automatic prompt engineering technique is to replace
a sentence by a semantically equivalent sentence, which can be done by queries
to LLMs. By comparing the pros and cons of greedy algorithm and genetic
algorithm, two representative algorithms for discrete optimization, we show
that a simple greedy algorithm with beam search is more effective. Further,
for long prompt engineering it is important to identify which sentence to
change, and to what direction. We thus propose two novel techniques that
utilize search history to enhance the effectiveness of LLM-based mutation in
our algorithm.

Our contributions can be summarized below:

  * •

To the best of our knowledge, this paper presents the first formal discussion
of automatic long prompt engineering, demonstrating substantial performance
gains on multiple tasks.

  * •

We propose a greedy algorithm with beam search that can rapidly optimize
prompts. Furthermore, a novel guided mutation method is introduced to enhance
convergence.

  * •

We conducted experiments on the Big Bench Hard (BBH) benchmark Suzgun et al.
(2022); Srivastava et al. (2022), where prompts comprise thousands of tokens,
including instructions and chain-of-thought reasoning. Our results demonstrate
that the proposed automatic long prompt engineering method significantly
enhances performance. Notably, we achieved an average of 9.2% absolute
accuracy improvements on 8 tasks selected from BBH, as shown in Figure 1, with
only 50 evaluations on the training set.

##  2 Related Work

The remarkable ability of large language models (LLMs) to perform complex
tasks without fine-tuning through prompting has significantly broadened their
applicability. As a result, designing effective prompts to fully exploit the
capabilities of LLMs has become an important topic. Many principal ways for
prompt design have been studied recently Reynolds and McDonell (2021); Brown
et al. (2020); Wei et al. (2022b); Wang et al. (2022a, 2023a). For instance, a
well-designed prompt may include a system prompt (e.g., "you are an AI
programming assistant"), an instruction prompt outlining the task, multiple
contextual examples, and a chain-of-thoughts reasoning section that explains
the step-by-step thought process behind the examples. By incorporating these
elements, effective prompts often have tens of sentences and thousands of
tokens.

An orthogonal line of previous work has explored soft-prompt tuning, a
technique that optimizes prompts within a continuous embedding space using
standard continuous optimization algorithms Lester et al. (2021); Zhang et al.
(2021); Wang et al. (2022b). While capable of achieving satisfactory
performance, soft-prompts lack interpretability and cannot be applied via LLM
APIs. Additionally, these parameter-efficient fine-tuning methods demand large
training sets, making them unsuitable for applications with limited data, such
as those with only tens or hundreds of samples.

Given the limited availability of training data (<1000 samples), our focus
lies in exploring strategies for optimizing hard prompts, which are
semantically equivalent to the original prompts but yield superior
performance. In the context of automated prompt engineering, the literature
considers two primary settings. The first setting, which aligns with our work,
assumes the existence of an initial human-crafted prompt and aims to refine or
improve it to achieve enhanced performance. Several discrete search algorithms
have been proposed for this setting: Xu et al. (2022) employs a genetic
algorithm for prompt tuning, utilizing back translation, cloze tasks, and
sentence continuation to mutate the initial instruction. More recently,
Fernando et al. (2023); Guo et al. (2023) proposed leveraging LLMs for
mutation and crossover operations in evolutionary searches, while Yang et al.
(2023) demonstrated the optimization capabilities of LLMs in generating
improved prompt variations based on previous fitness scores. However, these
prompt evolution techniques are designed for short sentences or paragraphs
within a long prompt. For example, many of them try to evolve only the
instruction part or the sentence “Let’s think step by step” in the prompt. Our
work aims to provide complete freedom to evolve the entire long prompt,
opening up more avenues for improvement but also introducing challenges in
determining how and where to change the original prompt.

Another setting focuses on automatic prompt generation without a pre-existing
prompt. Honovich et al. (2022) demonstrated the ability of LLMs to generate
brief task descriptions when provided with input-output pairs. Building upon
this technique and incorporating random search, Zhou et al. (2022) proposed an
automatic prompt engineering (APE) algorithm capable of generating prompts
from given pairs. Pryzant et al. (2023) explored the utilization of input-
output pair feedback to refine instructions, while Chen et al. (2023)
developed a continuous relaxation approach employing Bayesian optimization for
search within a continuous space.

##  3 Proposed Method

In this paper, we address the challenge of automatic long prompt engineering
for language models. Given a language model $\mathcal{L}$ and an initial
prompt $p_{\text{init}}$ designed by human for a particular task, our goal is
to refine the prompt to achieve superior performance. To enhance the prompt,
we are provided with a limited training set (e.g., 100 input-output pairs)
$\\{(x_{i},y_{i})\\}_{i=1}^{n}$ for performance evaluation. Specifically, for
each sample we conduct prediction by $\mathcal{L}([p,x_{i}])$ and assess its
agreement with the corresponding ground truth label $y_{i}$. We define
$\text{score}(p)$ as the performance metric of prompt $p$ on the training set.
We consider the scenario where the number of available samples $n$ is limited,
which is a common situation where individuals lack sufficient data for model
fine-tuning but can still utilize the data to design an improved hard prompt.
We will evaluate generalization performance on a hold-out test set that is not
used in prompt search.

In this section, we will first introduce the search space of our algorithm and
an exploration of how to use LLM to navigate this space (Section 3.1). We then
delve into the proposed greedy algorithm with beam search, highlighting its
advantages over both vanilla greedy algorithms and genetic algorithms in
Section 3.2. Finally, Section 3.3 shows how to leverage search history to
guide the proposed framework to improve its performance.

###  3.1 Search space

Our goal is to generate a new prompt that is semantically similar to the
original prompt while achieving enhanced performance. Further, we avoid
introducing non-interpretable tokens, such as adversarial triggers Zou et al.
(2023). These restrictions offer two advantages: 1) the prompts discovered by
our algorithm are interpretable, facilitating the verification that the prompt
still performs the intended task, and 2) since we are only provided with a
limited set (e.g., 100) of training samples, constraining the search space can
mitigate the issue of overfitting.

To conduct prompt search within this space, we decompose the long prompt into
$m$ individual sentences:

$p=[s_{(1)},s_{(2)},\dots,s_{(m)}].$

We then allow each sentence to be rephrased while preserving its semantic
meaning. Since LLMs excel at sentence rephrasing, particularly when provided
with prompts like "Generate a variation of the following instruction while
keeping the semantic meaning," we employ an LLM-Mutator equipped with such a
prompt to identify alternative formulations for each sentence. The prompt we
used for vanilla LLM mutator can be found in Figure 2. An improved version of
LLM-Mutator will be introduced later in Section 3.3.

Figure 2: The vanilla LLM-Mutator used in our search.

###  3.2 Search algorithm

A straightforward approach to conducting the search using the LLM-Mutator is
the following greedy algorithm. At each iteration, we randomly select a
sentence, denoted by $s_{(i)}$, and utilize the LLM-Mutator to generate an
alternative sentence $s_{(i)}^{\prime}$. We then replace $s_{(i)}$ by
$s_{(i)}^{\prime}$ in the old prompt $p$ if the new resulting prompt improves
the performance. However, we observed that this vanilla greedy approach can be
easily trapped in local optima. In our problem, the training set is so limited
that sometimes a detrimental modification is not reflected in the training
score. As a result, unfavorable edit are sometimes accepted due to
insufficient evaluation, which hurts the prompt’s future improvement.

To address this issue, we propose conducting a beam search by maintaining a
pool of $k$ top-performing prompts, denoted as
$p^{*}_{1},p^{*}_{2},\dots,p^{*}_{k}$. At each iteration, we randomly select
one of these $k$ prompts and refine the chosen prompt. We then evaluate this
new candidate and maintain the top-$k$ prompt pool. This approach ensures that
even with the introduction of detrimental edits, recovery from such errors is
still possible as we retain not only the top prompt. Our experiments reveal
that this approach leads to significantly improved training and test
performance compared to the pure greedy algorithm, as demonstrated in Figure
3.

|
---|---
|
Figure 3: Comparison between beam-search greedy, greedy, and genetic
algorithm. This is the average results over three runs. Beam-search greedy
outperforms both greedy algorithm and genetic algorithm.

It is worth noting that our method is closely related to the Genetic Algorithm
(GA). GA is a widely recognized method for discrete optimization involving
black-box functions. Assuming $P=\\{p_{1},\dots,p_{k}\\}$ represents the
solutions in the current pool, GA applies mutation and crossover operations to
this pool to generate a set of newly proposed candidates
$P^{\prime}=\\{p^{\prime}_{1},\dots,p^{\prime}_{k}\\}$. The fitness scores
(performance of the solutions) of these newly proposed candidates are then
evaluated. Subsequently, only the top $k$ solutions in $P\cup P^{\prime}$ are
retained before proceeding to the next iteration.

While GA possesses a high exploration capability, its convergence rate is
considerably slower during the initial stages. Given the vastness of our
search space and the reasonably good quality of the human-written initial
prompt, a majority of mutations and crossovers performed in the first few
iterations yield poorly performing candidates. Evaluating each of these
candidates is computationally expensive, even though it can enhance solution
diversity.

Our algorithm is effectively a “greedy” version of GA. We maintain a candidate
set of size $k$ and update the candidate pool immediately upon generating each
new candidate, rather than waiting for the evaluation of the entire generation
of offspring before updating the pool. As a result, our solution pool remains
more up-to-date, leading to faster convergence compared to GA. Figure 3
further verifies this observation, demonstrating the slower initial growth of
GA’s learning curve.

###  3.3 History-guided search

Randomly rephrasing a sentence in a prompt is akin to conducting a random
mutation within the space of semantically equivalent sentences, potentially
requires a significant amount of trials to obtain a good solution. In this
subsection, we demonstrate how the search history can be employed to guide the
mutation in a more purposeful direction.

#### Guided mutation for a single sentence.

At iteration $T$, we can denote the search history as
$\\{(s_{t}^{\text{before}},s_{t}^{\text{after}},r_{t})\\}_{t=1}^{T-1}$, where
$s_{t}^{\text{before}}$ is the sentence before mutation,
$s_{t}^{\text{after}}$ is the sentence after mutation, and the reward $r_{t}$
indicates the change in the score ($r_{t}$ is positive if the mutation
enhances the performance, and negative if it deteriorates performance). Assume
$s_{T}$ is the current sentence that is selected for mutation, we can then use
the history to guide the mutation towards more positive reward. For example,
if we know rephrasing the sentence “So, it is true that Lesley is a great-
grandfather of Leroy” to “Therefore Leslie is Leroy’s great-grandfather.” can
improve the performance, then for another sentence “So, it is true that
everyone who is an ancestor of Dana is a stepbrother of Brian” we may want to
rewrite it as “Therefore everyone that is an ancestor of Dana is Brian’s
stepbrother.”

It has been shown that LLMs are able to learn from in-context examples Zhang
et al. (2021). Therefore, we propose to let the LLM-Mutator in-context learn
from the history. This can be done by listing history in the prompt: if
$r_{t}>0$, we include an in-context example $s_{t}^{\text{before}}\Rightarrow
s_{t}^{\text{after}}$, and if $r_{t}<0$ we include
$s_{t}^{\text{after}}\Rightarrow s_{t}^{\text{before}}$. The prompt for LLM-
Evolver is shown in Figure 4.

Figure 4: The guided LLM-mutator used in our search.

Since the history can be long and it has been shown that putting too many in-
context learning examples can be harmful for the performance, we only retrieve
a small set of relevant history entries when rephrasing a sentence.
Specifically, when evolving $s_{T}$, we compute the similarity between $s_{T}$
and each $s_{t}^{\text{before}}$, which is calculated by
$\phi(s_{T})^{T}\phi(s_{t}^{\text{before}})$ and $\phi$ is a sentence encoder
(we use a T5 Raffel et al. (2020) sentence encoder in our experiments). We
then only select entries that pass a certain threshold to include as in-
context examples.

#### Guided sampling for sentence selection.

A challenge in automatic long prompt engineering lies in identifying which
sentences in the prompt should be modified to improve performance. Our
experiments demonstrate that altering only a few sentences in a long prompt
can significantly enhance its effectiveness, but the changes need to be at
right places. It is thus beneficial to bias the sampling distribution towards
selecting more impactful sentences for modification.

We model sentence selection as a contextual bandit problem Langford and Zhang
(2007); Li et al. (2010). In contextual bandit problem, at each iteration a
learner is faced with $m$ arms associante with feature vectors
$x_{1},\dots,x_{m}$, and the learner is trying to pull an arm at each round to
optimize the overall reward. In our case, $m$ arms correspond to the $m$
sentences $s_{(1)},\dots,s_{(m)}$ in a prompt, and features can be obtained by
$\phi(s_{(i)})$ where $\phi$ is a text encoder. Utilizing feature information
is crucial because if modifying a particular sentence can lead to performance
improvement, it is likely that modifying similar sentences will also yield
positive results.

We then adopt the Lin-UCB algorithm Li et al. (2010), a widely recognized
algorithm for contextual bandit problems, to guide sentence selection. Given
the history
$\\{(s_{t}^{\text{before}},s_{t}^{\text{after}},r_{t})\\}_{t=1}^{T-1}$, we
compute a linear estimator of the underlying reward model

$w_{T}^{*}=(H^{T}H+\lambda I)^{-1}H^{T}r,$ (1)

where $H$ is a $(T-1)$-by-$d$ matrix with each row being
$\phi(s_{t}^{\text{before}})$, and $r=[r_{1},\dots,r_{T-1}]^{T}$. This is
simply a solution of a ridge regression with feature matrix $H$ and reward
$r$. The following UCB rule is then used to select the sentence for mutation:

$\arg\max_{i}\phi(s_{(i)})^{T}w_{T}^{*}+\alpha\sqrt{\phi(s_{(i)})^{T}A^{-1}\phi(s_{(i)})},$
(2)

where $A=H^{T}H+\lambda I$. Since this Lin-UCB estimation may not be accurate,
we let the algorithm has probability $P$ to choose a arm by purely random and
$1-P$ to choose the sentence based on Eq. (2).

##  4 Experimental Results

In this section, we present empirical evidence demonstrating that the proposed
long prompt tuning method can significantly enhance performance on the Big-
Bench Hard (BBH) benchmark Suzgun et al. (2022); Srivastava et al. (2022). We
then conduct ablation studies to analyze the proposed algorithm’s
effectiveness and show qualitative results on how the proposed algorithm
refines human-written prompts.

###  4.1 Experimental Settings

We consider the prompt developed in Suzgun et al. (2022) for the BBH tasks,
where prompts consist of two parts: Task Description and Demos. The Task
Description provides instructions describing the task, while each demo
includes the question, a chain-of-thoughts demonstration illustrating the
problem-solving process step-by-step, and the final answer. During prompt
tuning, the format (e.g., “Question. ”, “Answer. ”) are retained, while the
tuning algorithm is allowed to modify any other parts including the
instruction part and the chain-of-thoughts part. Table 1 summarizes the
statistics of the datasets used in this study. The full prompts for each data
can be downloaded from https://github.com/suzgunmirac/BIG-Bench-Hard.

Each task consists of 250 samples, randomly divided into 50% for training and
50% for testing. Only training samples are utilized for prompt tuning. All
tasks are multi-class classification problems, and we report accuracy on
training data, test data, and the combined dataset when comparing different
tuning methods.

For the main experiments, we evaluated the performance on the text-bison model
and utilized the instruction-tuned PaLM 2-L model as the LLM mutator. Both
models belong to the PaLM 2-model family Anil et al. (2023). Following the
previous prompt tuning works, we set temperature as $0$. However, to enhance
the diversity of sentence mutation, we set the temperature of the LLM-Mutator
to $0.5$.

Dataset | Number of Words | Number of
---|---|---
Mutable Sentences
Causal Judgement | 678 | 20
Salient Translation | 745 | 34
Disambiguation | 671 | 37
Formal Fallacies | 741 | 32
Hyperbaton | 539 | 19
Dyck Language | 679 | 22
Color Reasoning | 435 | 17
Logical Five | 461 | 25

Table 1: Initial prompt statistics for each dataset. When calculating the
“number of mutable sentences,” we only consider sentences that can be modified
during the search phase.

Task | Original | Genetic Algorithm | Evolve “Step-by-step” | Greedy | Our Method
---|---|---|---|---|---
Prompt | Train | Test | Train | Test | Train | Test | Train | Test
Causal Judgment | 58.9 | 63.1$\pm$1.3 | 59.2$\pm$0.5 | 63.1$\pm$0.5 | 58.2$\pm$0.5 | 63.0$\pm$1.0 | 59.6$\pm$2.9 | 67.7$\pm$1.5 | 63.7$\pm$1.3
Salient Translation | 54.4 | 58.7$\pm$2.0 | 56.5$\pm$4.3 | 57.1$\pm$0.4 | 55.7$\pm$0.4 | 59.5$\pm$1.5 | 53.6$\pm$3.3 | 60.0$\pm$3.5 | 58.7$\pm$2.6
Disambiguation | 58.0 | 64.8$\pm$1.6 | 61.0$\pm$0.7 | 64.6$\pm$1.5 | 61.8$\pm$1.0 | 66.7$\pm$0.6 | 63.4$\pm$2.7 | 70.1$\pm$1.9 | 68.0$\pm$2.1
Formal Fallacies | 60.0 | 63.5$\pm$1.1 | 64.5$\pm$0.7 | 60.6$\pm$1.0 | 62.4$\pm$1.7 | 68.5$\pm$2.6 | 68.8$\pm$3.0 | 70.4$\pm$3.9 | 73.1$\pm$3.6
Hyperbaton | 74.4 | 82.8$\pm$1.3 | 76.3$\pm$2.5 | 84.9$\pm$0.0 | 79.6$\pm$0.3 | 83.5$\pm$3.3 | 79.3$\pm$5.3 | 88.4$\pm$2.6 | 85.5$\pm$1.1
Dyck Language | 16.0 | 20.2$\pm$1.7 | 16.4$\pm$0.4 | 18.25$\pm$0.0 | 20.4$\pm$0.1 | 19.0$\pm$0.4 | 17.3$\pm$0.6 | 22.8$\pm$0.7 | 20.9$\pm$0.4
Color Reasoning | 82.0 | 85.1$\pm$0.4 | 78.9$\pm$1.7 | 86.2$\pm$0.7 | 81.5$\pm$1.3 | 85.1$\pm$0.7 | 81.1$\pm$0.4 | 85.4$\pm$0.4 | 83.5$\pm$0.4
Logical Five | 38.8 | 49.3$\pm$2.7 | 48.2$\pm$1.6 | 54.5$\pm$1.0 | 50.3$\pm$0.4 | 53.9$\pm$3.9 | 51.3$\pm$1.2 | 59.8$\pm$2.2 | 54.7$\pm$0.9
Average | 55.3 | 60.94 | 57.6 | 61.2 | 58.7 | 62.4 | 59.3 | 65.6 | 63.5

Table 2: Main results on BBH benchmark. The search budget is limited to 50
evaluations over the training set for each method. We ran each experiment 3
times and report the mean and standard deviation.

###  4.2 Main results

We compare the proposed algorithm with the following baselines:

  * •

Original Prompt: Performance of the original human-designed prompt developed
in Suzgun et al. (2022), which also serves as the initialization for other
tuning methods.

  * •

Genetic Algorithm: An implementation of the genetic algorithm for long prompt
tuning. To facilitate a more comparable comparison with our method, we set the
pool size to $4$. At each step, $8$ new candidates are generated by randomly
mutating and performing crossover on the top candidates within the pool.

  * •

Evolve “step-by-step”: Several recent prompt tuning studies have explored the
concept of evolving a prompt using a single sentence, such as the ’Let’s think
step by step’ sentence employed in chain-of-thought prompts Kojima et al.
(2022). We adopted one of the state-of-the-art methods for single sentence
optimization Yang et al. (2023) to optimize all of the ’Let’s think step by
step’ sentences within the chain-of-thought prompt.

  * •

Greedy: A simple greedy approach mentioned in Section 3.2, where we only store
the top performing candidate in the pool and generating new candidate on top
of it.

For our method, we use the same hyper-parameters for all the experiments. We
set the pool size (beam size) to $4$ for all experiments. When applying guided
mutation in Section 3.3, we use a T5 encoder to encode both the current entry
and the history and normalize the embeddings to have a unit $\ell_{2}$ norm.
We retrieve only the top $4$ history entries and require the $\ell_{2}$
distance between the encoded history and the current sentence to be below
$0.5$. When applying the sentence selection algorithm described in Section
3.3, we set $\alpha=0.05$ in Eq. (2) and set $P=0.5$. Note that those hyper-
parameters are not well tuned.

For this experiment, we limited the computational budget to 50 evaluations on
the training set and reported the training, test, and combined accuracy
achieved by each method. All the experiments are run three times and we report
the mean and standard deviation. The results are summarized in Table 2. Our
proposed algorithm outperformed the other methods, demonstrating significant
improvements in accuracy across all tasks. We also compute the improvements of
accuracy on the whole dataset (including both training and testing) and report
the accuracy gain in Figure 1.

Across all 8 tasks, our algorithm achieves an average of 8.2% gain in test
accuracy and 9.2% gain in the accuracy of full evaluation set (train + test).
Among these tasks, we achieve the largest performance gain (18.45%) on the
logical deduction task, and the smallest gain (2.45%) on reasoning about
colored objects (Color Reasoning). One potential reason of small performance
gain on color reasoning is that the original prompt already achieves very high
accuracy, so there is not much room for improvements.

Comparing the baselines, it becomes evident that evolving a single sentence
(Evolve ’step-by-step’) fails to achieve substantial improvements in long
prompt tuning. This is mainly due to the fact that long prompt tuning
typically involves over 20 sentences with detailed instructions and
explanations, and thus naively modifying “Let’s think step by step” is
unlikely to lead to significant enhancements. Furthermore, the Genetic
Algorithm and Greedy Algorithm each exhibit their own limitations, as
discussed in Section 3.2, which are reflected in their inferior performance
compared to our method.

Despite being able to significantly boost the performance, we also observe
some degree of overfitting in our search procedure. Although the proposed beam
search method can partially mitigate overfitting (see Section 3.2), we still
observe higher training accuracy than testing in most cases. However, as the
performance gain is substantial, the prompts found by the algorithm are still
significantly better than the original one, even on the test set.

###  4.3 Ablation Study

We conduct an ablation study on the two techniques introduced in Section 3.3:
the history-guided mutation and the contextual bandit algorithm for sentence
selection. The results are presented in Table 3. We can observe that both
components are contributing to the final performance of the model.

Task | Disambiguation | Formal Fallacies | Hyperbaton | Logical Five
---|---|---|---|---
Train | Test | Train | Test | Train | Test | Train | Test
Our method (no history-guided mutation) | 67.4 | 66.9 | 61.1 | 66.1 | 83.6 | 78.1 | 55.6 | 53.2
Our method (no sentence selection) | 68.2 | 63.1 | 71.2 | 72.8 | 81.4 | 80.3 | 54.2 | 50.4
Our method | 70.1 | 68.0 | 70.4 | 73.1 | 88.4 | 85.5 | 59.8 | 54.7

Table 3: Ablation Study on the two components introduced in Section 3.3.

Original prompt: 38.8% accuracy New prompt found at iteration 48: 56% accuracy
(train 57.9% / test 54.0%) A: Let’s think step by step. A: Let’s think things
through one step at a time. (2) Eli finished below Amy: "(above) ? Amy ? Eli ?
(below)". (2) Amy was above Eli: "(above) ? Amy ? Eli ? (below)". Eli finished
last. Eli came in last place. Q: The following paragraphs each describe a set
of three objects arranged in a fixed order. The statements are logically
consistent within each paragraph. On a shelf, there are three books: a white
book, a green book, and an orange book. The green book is to the right of the
white book. The orange book is the rightmost. Q: Each paragraph below
describes three objects arranged in a fixed order, and the statements are
logically consistent in each paragraph. There are three books on a shelf: a
white, green, and orange book. The green book is to the right of the white
book, and the orange book is in the far right position. A: Let’s think step by
step. A: Let’s think through things one step at a time. The white book is the
leftmost. The white book is at the far left. A: Let’s think step by step. A:
Let’s think one step at a time.

Table 4: An example that our method improves the performance on Logical
Deduction Five Objects from 38.8% to 56%.

Original promp: 60% accuracy New prompt found at iteration 91: 76% accuracy
(train 92.1%, test 83.1%) Distinguish deductively valid arguments from formal
fallacies. Identify deductively valid arguments from formal fallacies. So, it
is true that Lesley is a great-grandfather of Leroy. So it’s true that Lesley
is Leroy’s great-grandfather. Whoever is not a great-grandfather of Clyde is a
stepbrother of Brian: If X = NOT (great-grandfather(Clyde)), then X =
stepbrother(Brian). * If someone is a stepbrother of Brian then they are not a
great-grandfather of Clyde. Furthermore, by (1), we have if X = NOT (great-
grandfather(Clyde)), then X = stepbrother(Brian). Additionally, according to
(1) we have that if X = NOT (great-grandfather(Clyde)), then X =
stepbrother(Brian). By the transitive relation rule in first-order logic, we
then have: if X = ancestor(Dana), then X = stepbrother(Brian). Using the
transitive relation rule in first-order logic, we have: if X = ancestor(Dana),
then X = stepbrother(Brian). Let’s see whether the Hypothesis can be deduced
from the arguments (1) and (2) by logical reasoning? Let’s see whether the
Hypothesis is a logical consequence of the arguments (1) and (2)? So, from (1)
and (2), we cannot necessarily deduce the Hypothesis. So, given (1) and (2),
we are not always entitled to infer the Hypothesis.

Table 5: An example demonstrating how our method changes the original prompt.
By conducting these changes the combined accuracy on Formal Fallacies can be
improved from 60% to 76%. Interestingly, there’s one line

###  4.4 Qualitative results

One important benefit of automatic hard prompt engineering is that the
resulting prompts remain interpretable by humans, allowing users to easily
verify the modifications. We provide some successful examples found by our
search in Table 4 and Table 5. In each table, we show only the different parts
of the initial prompt from BBH and the changes made by our method.

The first example demonstrated in Table 4 is for the logic deduction task on
five objects. The initial prompt achieves 38.8% accuracy while the revised
prompt found at iteration 48 improves the performance to 57.9% train accuracy
and 54.0% test accuracy. We observed that most of the changes involve minor
revisions to the original sentence without altering its meaning. These
seemingly insignificant modifications can lead to substantial improvements in
LLM accuracy, showcasing the important of automatic long prompt engineering.

The second prompt in Table 5 is for the Formal Fallacies task, designed to
identify whether a given logic statement is valid. The initial prompt achieves
60% accuracy while the revised prompt found at iteration 91 improves the train
accuracy to 92.1% and test accuracy to 83.1%. Similar to the previous case,
most of the changes involve minor revisions. In this case, we also want to
highlight a potential limitation of the proposed method that could be
addressed in future work. In the sentence marked as *, the revised sentence is
not semantically equivalent to the original one. The original and revised
sentences represent different logical statements (original sentence: not A
$\rightarrow$ B; new sentence: B $\rightarrow$ not A). However, the LLM
appears incapable of detecting this subtle distinction, leading to an
erroneous rephrasing. Although this change leads to improve training accuracy,
it actually hurts test accuracy. Therefore, incorrect mutations can lead to
overfitting, and developing strategies to mitigate these errors during the
search process would be an interesting area of future research.

##  5 Conclusions, Limitations, and Future Work

We study the problem of automatic prompt engineering for long prompts, often
comprising thousands of tokens. We investigate the performance of the standard
greedy algorithm and genetic algorithm, and develop a novel search algorithm
that yields superior performance. With only 50 evaluations on the training
set, our method achieves an average absolute accuracy improvement of 9.2%
across 8 tasks from Big Bench Hard. This demonstrates the significant
potential benefits of automatic long prompt tuning and underscores the
importance of this emerging area.

As the first paper focusing on automatic engineering of the entire long
prompts, we identify several limitations of the current methods which can lead
to interesting future research:

  * •

The current algorithm relies on using another LLM to rephrase a sentence. As
illustrated in Section 4.4, this LLM-mutator may introduce errors during
sentence rewriting, particularly for intricate sentences (e.g., CoT in
complicated logical deduction tasks). Therefore, improving the “correctness”
of LLM-Mutator is an interesting future area of research, which has not been
fully addressed in our work as well as other recent studies Fernando et al.
(2023); Guo et al. (2023).

  * •

Similar to any other training or tuning algorithms, automatic prompt
engineering can suffer from overfitting to the training data, as discussed in
Section 4. This overfitting can be potentially alleviated by applying
additional regularization techniques, such as imposing sparsity constraints by
reducing the number of modified sentences. However, further research is
required to identify the most effective regularization strategies for
automatic prompt engineering.

  * •

In the current implementation, we break down the long prompt into individual
sentences and modify one sentence at a time. However, it might be beneficial
to manipulate multiple sentences simultaneously during mutation or consolidate
multiple sentences into a single one. An automated mechanism for carrying out
this process would be an interesting direction for enhancing our method.

  * •

Although our algorithm is able to find a good solution with less than 100
evaluations on the training set, the cost is still not negligible especially
when tuning prompts using APIs with cost or rate limits. Employing early
stopping techniques, where the evaluation of poorly performing candidates are
terminated early, could potentially reduce the number of queries.

  * •

Although automatic prompt engineering can achieve significant gain, the search
space of hard prompt has limited representation power which hinders further
performance improvements. It has been shown that soft prompt tuning has
limited representation power Wang et al. (2023b), and our search space is a
small subset of soft prompts. Therefore, when provided with sufficient data,
computational resources, and white-box access to the LLM, (parameter-
efficient) fine-tuning may still achieve superior performance.

## Acknowledgements

We thank Ruochen Wang, Vineet Gupta, Kedar Dhamdhere, Daliang Li for valuable
discussions and feedback.

## References

  * Anil et al. (2023) Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. 2023.  Palm 2 technical report.  _arXiv preprint arXiv:2305.10403_.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Chen et al. (2023) Lichang Chen, Jiuhai Chen, Tom Goldstein, Heng Huang, and Tianyi Zhou. 2023.  Instructzero: Efficient instruction optimization for black-box large language models.  _arXiv preprint arXiv:2306.03082_.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. 2021.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_.
  * Deng et al. (2022) Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing, and Zhiting Hu. 2022.  Rlprompt: Optimizing discrete text prompts with reinforcement learning.  _arXiv preprint arXiv:2205.12548_.
  * Fernando et al. (2023) Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel. 2023.  Promptbreeder: Self-referential self-improvement via prompt evolution.  _arXiv preprint arXiv:2309.16797_.
  * Guo et al. (2023) Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. 2023.  Connecting large language models with evolutionary algorithms yields powerful prompt optimizers.  _arXiv preprint arXiv:2309.08532_.
  * Honovich et al. (2022) Or Honovich, Uri Shaham, Samuel R Bowman, and Omer Levy. 2022.  Instruction induction: From few examples to natural language task descriptions.  _arXiv preprint arXiv:2205.10782_.
  * Jiang et al. (2020) Zhengbao Jiang, Frank F Xu, Jun Araki, and Graham Neubig. 2020.  How can we know what language models know?  _Transactions of the Association for Computational Linguistics_ , 8:423–438.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213.
  * Langford and Zhang (2007) John Langford and Tong Zhang. 2007.  The epoch-greedy algorithm for contextual multi-armed bandits.  _Advances in neural information processing systems_ , 20(1):96–1.
  * Lester et al. (2021) Brian Lester, Rami Al-Rfou, and Noah Constant. 2021.  The power of scale for parameter-efficient prompt tuning.  _arXiv preprint arXiv:2104.08691_.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670.
  * Liu et al. (2023) Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2023.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  _ACM Computing Surveys_ , 55(9):1–35.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022\.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744.
  * Pryzant et al. (2023) Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. 2023\.  Automatic prompt optimization with" gradient descent" and beam search.  _arXiv preprint arXiv:2305.03495_.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ , 21(1):5485–5551.
  * Reynolds and McDonell (2021) Laria Reynolds and Kyle McDonell. 2021.  Prompt programming for large language models: Beyond the few-shot paradigm.  In _Extended Abstracts of the 2021 CHI Conference on Human Factors in Computing Systems_ , pages 1–7.
  * Srivastava et al. (2022) Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2022.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _arXiv preprint arXiv:2206.04615_.
  * Suzgun et al. (2022) Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, et al. 2022\.  Challenging big-bench tasks and whether chain-of-thought can solve them.  _arXiv preprint arXiv:2210.09261_.
  * Wang et al. (2023a) Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. 2023a.  Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models.  _arXiv preprint arXiv:2305.04091_.
  * Wang et al. (2022a) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022a.  Self-consistency improves chain of thought reasoning in language models.  _arXiv preprint arXiv:2203.11171_.
  * Wang et al. (2023b) Yihan Wang, Jatin Chauhan, Wei Wang, and Cho-Jui Hsieh. 2023b.  Universality and limitations of prompt tuning.  _arXiv preprint arXiv:2305.18787_.
  * Wang et al. (2022b) Yihan Wang, Si Si, Daliang Li, Michal Lukasik, Felix Yu, Cho-Jui Hsieh, Inderjit S Dhillon, and Sanjiv Kumar. 2022b.  Preserving in-context learning ability in large language model fine-tuning.  _arXiv preprint arXiv:2211.00635_.
  * Wei et al. (2022a) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. 2022a.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_.
  * Wei et al. (2022b) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022b.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837.
  * Xu et al. (2022) Hanwei Xu, Yujun Chen, Yulun Du, Nan Shao, Yanggang Wang, Haiyu Li, and Zhilin Yang. 2022.  Gps: Genetic prompt search for efficient few-shot learning.  _arXiv preprint arXiv:2210.17041_.
  * Yang et al. (2023) Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. 2023.  Large language models as optimizers.  _arXiv preprint arXiv:2309.03409_.
  * Zhang et al. (2021) Ningyu Zhang, Luoqiu Li, Xiang Chen, Shumin Deng, Zhen Bi, Chuanqi Tan, Fei Huang, and Huajun Chen. 2021.  Differentiable prompt makes pre-trained language models better few-shot learners.  _arXiv preprint arXiv:2108.13161_.
  * Zhou et al. (2022) Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. 2022.  Large language models are human-level prompt engineers.  _arXiv preprint arXiv:2211.01910_.
  * Zhu et al. (2023) Kaijie Zhu, Jindong Wang, Jiaheng Zhou, Zichen Wang, Hao Chen, Yidong Wang, Linyi Yang, Wei Ye, Neil Zhenqiang Gong, Yue Zhang, et al. 2023.  Promptbench: Towards evaluating the robustness of large language models on adversarial prompts.  _arXiv preprint arXiv:2306.04528_.
  * Zou et al. (2023) Andy Zou, Zifan Wang, J Zico Kolter, and Matt Fredrikson. 2023.  Universal and transferable adversarial attacks on aligned language models.  _arXiv preprint arXiv:2307.15043_.


# Bootstrapping Complete The Look at Pinterest

Eileen Li, Eric Kim, Andrew Zhai, Josh Beal, Kunlong Gu  Visual Search,
Pinterest<EMAIL_ADDRESS>
(2020)

###### Abstract.

Putting together an ideal outfit is a process that involves creativity and
style intuition. This makes it a particularly difficult task to automate.
Existing styling products generally involve human specialists and a highly
curated set of fashion items. In this paper, we will describe how we
bootstrapped the Complete The Look (CTL) system at Pinterest. This is a
technology that aims to learn the subjective task of “style compatibility” in
order to recommend complementary items that complete an outfit. In particular,
we want to show recommendations from other categories that are compatible with
an item of interest. For example, what are some heels that go well with this
cocktail dress? We will introduce our outfit dataset of over 1 million outfits
and 4 million objects, a subset of which we will make available to the
research community, and describe the pipeline used to obtain and refresh this
dataset. Furthermore, we will describe how we evaluate this subjective task
and compare model performance across multiple training methods. Lastly, we
will share our lessons going from experimentation to working prototype, and
how to mitigate failure modes in the production environment. Our work
represents one of the first examples of an industrial-scale solution for
compatibility-based fashion recommendation.

style modeling; embedding; visual search; recommender systems

††journalyear: 2020††copyright: rightsretained††conference: Proceedings of the
26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; August
23–27, 2020; Virtual Event, CA, USA††booktitle: Proceedings of the 26th ACM
SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’20), August
23–27, 2020, Virtual Event, CA, USA††doi: 10.1145/3394486.3403382††isbn:
978-1-4503-7998-4/20/08††ccs: Information systems Recommender systems††ccs:
Computing methodologies Computer vision††ccs: Computing methodologies Visual
content-based indexing and retrieval††ccs: Computing methodologies Image
representations††ccs: Computing methodologies Machine learning††ccs: Computing
methodologies Neural networks Figure 1. Complete The Look gives users outfit
ideas and helps them find complementary products in related categories. The
screen-captures above show outfit, jewelry, and shoes recommendations for the
red striped blouse.

##  1\. Introduction

Since the number of online shoppers has grown exponentially in the past
decade, platforms such as Amazon, Instagram, Taobao and Pinterest have all
worked to create products that add value to the shopping experience.

In this crowded arena, Pinterest uniquely focuses on discovery and
inspiration. Over 350M users visit the Pinterest website every month to
discover new ideas in the realm of fashion, beauty, food and drinks, travel,
home decor, and more. On Pinterest, they discover and save “pins”, images with
rich metadata attached, such as title, description, and url. Pinterest’s
ultimate goal is to turn inspiration into real-life actions and improvements.
In recent years, visual search products such as Shop The Look (Gu, 2019)
helped to close this loop by enabling users to make purchases directly from
pins they have saved. Shop The Look uses the Unified Embedding model (Zhai et
al., 2019) trained on millions of pieces of Pinterest content to find products
that are visually similar to the objects detected in the image.

As a follow-on to Shop The Look, we have been working on a novel shopping
experience called Complete The Look (CTL) (see Figure 1). Whereas Shop The
Look has the goal of visual exact match and retrieval, Complete The Look aims
to find products that are visual complements. CTL helps users find ideas about
how to style a particular product and gives them the option to continue their
shopping experience in related categories. We hope to answer queries such as,
“What are some hats that I might buy to wear with this jacket?”.

Completing an outfit is not a new problem, but existing solutions require
fashion products that have been highly curated and matched by human stylists.
There are also systems that use past engagement to build complementary
recommendations (i.e., “You liked this item? Maybe you’ll like this other item
too.”). In contrast, we describe a solution for when such explicit user
engagement does not exist. Specifically, we offer our approach to
bootstrapping the Complete-the-Look system and how we made it work with our
diverse corpus of tens of millions of products. To do so requires answering
some challenging questions, such as:

  * •

How do we generate an outfit dataset that is high-quality and relevant to the
shopping content on Pinterest?

  * •

How do we evaluate this subjective task of “style compatibility”?

  * •

How do we handle mislabeled or missing product metadata?

  * •

How do we design a system that is performant, scalable, and easy to maintain?

In particular, our contributions are:

  1. (1)

We describe an automatic way of generating an outfit dataset from the
Pinterest platform of over 1M unique outfits and 4M fashion items, leveraging
existing technologies in object detection, image style classification and
attribute classification. To the best of our knowledge, this is the largest
known dataset of fashion outfits, and we will release 100K outfits from our
training set with our entire test set of 25K outfits.

  2. (2)

We combine this dataset with a Convolutional Neural Net (CNN) to learn useful
style embeddings. We present quantitative experimental results comparing
performance across multiple training methodologies, including loss functions
(contrastive, triplet, classification), data preprocessing, network
architecture, and dataset collection.

  3. (3)

We deploy and evaluate this model in an end-to-end recommendation system that
performs retrieval from a diverse corpus of Pinterest shopping products,
overcoming challenges in serving infrastructure, domain adaption, and metadata
mislabeling.

##  2\. Related Works

###  2.1. Visual Similarity

Fine-grained visual similarity and retrieval is a well-studied problem. The
earlier approaches for modeling visual similarity relied mostly on hand-
crafted features and attributes (Kovashka et al., 2012) (Wang and Zhang,
2011). More recent approaches using CNNs have been able to achieve state-of-
the-art results (Bell and Bala, 2015) (Liu et al., 2016) (M. Hadi Kiapour,
2015) (Huang et al., 2015). The challenge falls on curating a high-quality
matching dataset (i.e., scene with bounding box and object pairs). The model
trained on this dataset, usually by way of metric learning, learns to
transform an image to its embedding representation. During retrieval, a query
embedding is compared with many candidate embeddings to find the most similar
results. This technology powers much of Pinterest’s visual search (Jing et
al., 2015), and is the backbone to the system on which CTL is built.

###  2.2. Style Modeling

Earlier approaches in style modeling relied on crowdsourcing hand-labeled
datasets (M. Hadi Kiapour, 2014). This involved having explicit buckets for
each style (e.g., “Bohemian” vs. “Classy”), which is limiting due to its
subjective nature. Since then, there have been efforts in scaling the
annotations for fashion datasets (Simo-Serra and Ishikawa, 2016) (Matzen et
al., 2017) in order to enable much more fine-grained attribute classification.
(Hsiao and Grauman, 2017b) uses the topic modeling approach to discover latent
“styles”, but still requires a hand-crafted set of attributes. More recently,
researchers have used outfits from the popular site Polyvore to train models
such as SiameseCNN (He et al., 2016a), sequence models (e.g., LSTM (Han et
al., 2017)), and graph-inspired networks (Cui et al., 2019) for learning style
(Lee et al., 2017) (Hsiao and Grauman, 2017a) (Vasileva et al., 2018) (He et
al., 2016b). In contrast to our system, most of these approaches are not
optimized for retrieval but are instead trained for fashion compatibility
classification.

###  2.3. Recommender Systems

Recommendation systems for fashion have grown in importance as as increasing
percentage of shopping moves online. The earlier systems used traditional
machine learning methods (e.g., SVM, logistic regression) trained on a hand-
annotated dataset and retrieved recommendations from a limited corpus (Liu et
al., 2012) (McAuley et al., 2015). More recently, Pinterest published a paper
that focused on scene-to-product recommendation (Kang et al., 2018)—e.g.,
given a beach scene, recommend products that are complementary. Here we
present a modified approach that handles product-to-product recommendation.
Many recommendation systems, such as Alibaba’s iFashion (Chen et al., 2019),
use past user engagement to train complementary models (Li et al., 2016) (He
et al., 2016a). We attempt the challenging task of bootstrapping such a system
without explicit user data.

##  3\. System overview

Figure 2. Serving system overview for Complete The Look

We define Complete The Look (CTL) as the problem of matching a single product
to multiple complementary products. While a user is viewing an apparel product
on Pinterest, we aim to offer them complementary products to help them
“complete” their look. The serving system is real-time, generating
recommendations in a fraction of a second through four stages: _query
understanding_ , _candidate generation_ , _full scoring_ , and _blending_ as
shown in Figure 2.

Query understanding takes the apparel product a user is currently viewing and
enriches the query with additional features. For CTL, the core features are
inferred from the CTL model, discussed more in Section 5.1, which predicts the
product category of the query along with the style embedding. The product
category prediction is then expanded into the outfit apparel categories that
are complementary. As an example, for the “Shirts & Tops” query category,
complementary categories to “complete” the look may be “Shoes”, “Sunglasses”,
and “Jewelry & Watches”.

Candidate generation leverages the complementary categories from _query
understanding_ to restrict our apparel corpus of millions of products to the
items that match the given categories. Each category has its own list of
candidates. Note that the corpus categories are also generated from offline
batch inference of the CTL model and the inverted indices per corpus
categories are built offline.

Full scoring takes each complementary category’s candidate lists and runs
approximate nearest neighbor (ANN) search of the query’s style embedding
against the complementary item’s style embeddings to rank the results within a
category. These ANN indices are built offline for each inverted index and
contain the CTL model predicted style embeddings for the candidates.

Blending merges each complementary category’s full-scored candidate lists and
selects the final ordering to present to users.

##  4\. Dataset

Fashion datasets such as Fashion136K (Jagadeesh et al., 2014) and StreetStyle
(Matzen et al., 2017) generally included “in-the-wild” street photos of people
wearing clothes. More recently, composition outfit datasets from Polyvore
website have been used for learning fashion tasks, such as FashionVC (20,726
outfits) (Song et al., 2017), Maryland Polyvore (33,375 outfits) (Han et al.,
2017), and Polyvore Outfits (68,306 outfits) (Vasileva et al., 2018). Polyvore
was a popular website where people created and shared collages of outfits.
Each outfit image consisted of multiple fashion items that came together to
form a cohesive style. Unfortunately, the site was shut down in 2018.

Pinterest is a visual discovery engine with billions of pieces of diverse
content saved by people around the world. In order to build a product that
works well in this varied ecosystem, we need a reliable way to gather a large-
scale outfit dataset for training that can be refreshed periodically. By using
an Image Style classifier and object detector, we have implemented an
extraction flow to decompose outfit images into their set of fashion objects.
We chose to filter for images in collage-like sets similar to those that were
popular on Polyvore. These “polyvore”-style images include objects that better
match the domain of our product corpus, which typically consists of images
with a clean background.

At a high level, the dataset extraction flow is comprised of the following
steps:

  1. (1)

We trained an Image Style classifier to identify “polyvore”-style images on
Pinterest. These images are not necessarily from polyvore.com, but simply
follow the same visual style of an outfit collage (Figure 3).

  2. (2)

We ran our object detection model to gather bounding boxes and category labels
for items on these “polyvore”-style images.

  3. (3)

We cleaned up this dataset using a number of post-processing criteria for
higher quality images. See Tables 2 and 3 for the dataset distributions broken
down by category and number of items per outfit, respectively.

Figure 3. Pinterest images are funneled through steps 1) fashion and
“polyvore”-style classification; 2) object detection and labeling; and 3)
heuristics post-processing, resulting in high quality, high volume outfit
dataset.

###  4.1. Image Style classifier

Image Style is a signal consisting of a family of multi-class and multi-label
visual classifiers. Each classifier uses the Unified Embedding (Zhai et al.,
2019) as input and outputs a score between 0 and 1 for every style class.
These classifiers are trained on human-curated image datasets with low label
noise. There are five labels of interest for the CTL model: Polyvore, Product
Shot, Stock Photo, Full Outfit, and Cropped Outfit (see Figure 4). These
labels are used to distinguish common types of shopping content in the fashion
domain. By filtering on the Polyvore score at a high-precision threshold of
0.9, around 35M images in the fashion domain are obtained.

Figure 4. Examples of Image Style categories for CTL model, from left to
right: (1) Polyvore, (2) Product Shot, (3) Stock Photo, (4) Full Outfit, and
(5) Cropped Outfit.

####  4.1.1. Domain difference

We use the “polyvore”-style to collect training data because objects detected
from these images resemble products on solid backgrounds (i.e., Product Shot).
As expected, quality decreases dramatically for out-of-domain products (i.e.,
Stock Photo, Full Outfit, Cropped Outfit). To ensure quality, we restrict CTL
queries and results using the Image Style classifier to filter for Product
Shots only (see Figure 5).

Figure 5. (Left) Product Shot pins that match the image domain of our training
set. We restrict CTL to only these images. (Right) Cropped Outfit pins that we
filter out for CTL.

###  4.2. Object Detection

To decompose each “polyvore”-style image into its individual articles of
clothing, e.g., “Shirts & Tops” and “Pants” (Figure 3), we utilize an object
detection model that is trained on fashion categories. Specifically, we use a
Faster-RCNN (Ren et al., 2015) with a ResNeXt101 (Xie et al., 2016) backbone
and Feature Pyramid Networks (Lin et al., 2016), trained using the Detectron
(Girshick et al., 2018) framework.

Our detection training set consists of 251,000 training images with 727,000
bounding boxes in the home decor and fashion domains. We set aside a
validation set consisting of 10,000 images with 30,000 bounding boxes.

At inference time, we use a whitelist of 21 fashion categories (Table 2) to
restrict the bounding boxes to the CTL categories. Of the 35M ”polyvore”-style
images, about 10M of them have at least one CTL object detected.

mAP | Precision | Recall
---|---|---
77.2 | 76.0 | 82.4
Table 1. Detection evaluation metrics on our in-house test set of 10k fashion
images. “mAP” is mean average precision. Precision and recall are obtained by
choosing the operating point that maximizes the F1 score.

To assess the quality of the detection model, we collected an in-house test
set of 10k images in the fashion category (see Table 1). We found that the
performance of the object detection model was satisfactory for the CTL dataset
generation pipeline.

Label | #Items(full) | #Items(100K) | #Items(test)
---|---|---|---
Shoes | 856,775 | 94,059 | 22,728
Handbags | 810,501 | 88,955 | 20,729
Shirts & Tops | 519,625 | 57,250 | 14,451
Pants | 468,845 | 51,706 | 11,666
Coats & Jackets | 397,353 | 43,552 | 9,698
Dresses | 254,806 | 28,066 | 6,903
Jewelry | 222,743 | 24,409 | 7,813
Hats | 168,394 | 18,581 | 4,343
Skirts | 138,343 | 15,152 | 3,630
Sunglasses | 86,802 | 9,343 | 2,174
Shorts | 84,743 | 9,265 | 2,166
Scarves & Shawls | 52,233 | 5,751 | 1,218
Watches | 51,613 | 5,605 | 1,313
Table 2. Number of items in full, released, and test datasets from top 13 out of 21 total categories. #Items | #Outfits(full) | #Outfits(100K) | #Outfits(test)
---|---|---|---
3 | 223,240 | 24,545 | 5,383
4 | 421,815 | 46,545 | 9,288
5 | 251,835 | 27,643 | 6,616
6 | 72,916 | 7,927 | 2,786
7 | 10,767 | 1,127 | 722
8 | 938 | 102 | 165
Table 3. Number of clothing articles in an outfit; in full, 100K and test
datasets.

###  4.3. Dataset Cleanup

Figure 6. We clean up the dataset using a number of heuristics to ensure clean
bounding boxes with a cohesive set of fashion items.

We want outfits that have good style cohesion and high diversity in category
and color. For example, training on a corpus consisting mostly of outfits with
white tops and blue jeans may lead to a model that heavily biases towards
recommending jeans for every query. We also want crops with clean backgrounds
so that they can better match the conditions of our product images. To help
curate a higher quality dataset, we applied a series of post-processing steps:

  * •

Discard overlapping bounding boxes by applying non-maximum suppression 111We
use an IOU threshold of 0.1.

  * •

Discard bounding boxes that are too small, specifically less than 5% of total
image area.

  * •

Enforce that each image has between 3 and 8 clothing items. We found that
outfits outside of this range tend to be noisy and lack cohesion, e.g.,
consisting of several different outfits in the same image.

  * •

Enforce at least 3 different types of clothing articles per outfit. This
further guarantees that the image contains a complete outfit.

  * •

Discard outfits where all items are of the same color. Many outfit images are
monochromatic, resulting in models biased for matching color instead of style.
Spot-checking results seem to show improvements with this filter, though the
problem still exists (see qualitative feedback in Section 6.5).

We tried curating by user engagement (e.g., clicks and repins) and image age
(i.e., number of days on Pinterest) to get popular, trending outfits, but we
did not find a noticeable difference in the generated outfits.

The final dataset has 1,006,519 outfits and 4,246,430 fashion objects. To the
best of our knowledge, this is the largest known dataset of fashion outfits.
We keep 24,960 outfits (109,471 items) as a holdout set and train on the
remaining 981,559 outfits (4,136,959 items). The female:male ratio is about
10:1. 100K outfits from the training set and the entire test set are made
publicly available 222https://github.com/eileenforwhat/complete-the-look-
dataset.

##  5\. Methodology

Figure 7. The CTL model has three components: visual featurizer, category
predictor, and style . We compare three different ways to train: A)
classification “proxy” loss, B) contrastive loss, and C) triplet loss.

###  5.1. Model Architecture

The CTL model is comprised of three modules: the _visual featurizer_ ,
_category classifier_ , and _style extractor_. We try to leverage as much
existing Pinterest technology as possible, lowering the risk and maintenance
cost of the system.

The visual featurizer uses the same SE-ResNext101 backbone (Hu et al., 2017)
as Pinterest’s Unified Embedding (Zhai et al., 2019). Unified Embedding is a
multi-task learning model that has been trained for three visual discovery
tasks: Flashlight (Ng, [n.d.]), Lens (Zhai, [n.d.]), and Shop The Look (Gu,
2019). The Unified Embedding is the primary image-based embedding used by many
systems at Pinterest.

“Layer4” of the featurizer backbone is fed into two separate networks: one for
category classification, and another for style learning.

The category classifier predicts the top category label for each input image,
from a total of 21 fashion CTL categories. These predictions are important
because we need to determine the query category (e.g., “Dresses”) and also
filter CTL results for particular candidate categories (e.g., “Shoes” and
“Coats & Jackets”). At serving time, products are stored in our retrieval
index keyed by the category prediction from this classifier, so we can
efficiently retrieve and filter results on any set of product categories.

The ground truth labels for this classifier come from the detection model (see
Table 1 for detection evaluation metrics). The category classifier is
implemented as two fully connected (FC) layers, achieving accuracy of 98.15%
across all categories on the test set.

The style extractor is a neural network with two FC-layers that outputs a
128-dimensional style embedding. We use batch normalization and a dropout rate
of 0.5. We experimented with three different training methods: a
classification network with “proxy” loss, contrastive loss (siamese) (He et
al., 2016a) and triplet loss (Hoffer and Ailon, 2014). Our production CTL
system uses the best performing model with triplet loss. See section 6 for
experiment results.

The motivation for the classification network is its similarity to the Unified
Embedding model (Zhai et al., 2019), if for example, we decide to add CTL as
an additional task to our Unified Embedding training. In the classification
model, each outfit has a unique instance label. At training time, we feed into
the model the image of a fashion item. From the output layer of the style
extractor, we calculate the softmax cross entropy loss for predicting into a
subset of “proxy” instances. We sample the number of proxies to be 2048 which
is consistent with Unified Embedding training.

Figure 8. We take this figure directly from the Unified Embedding paper (Zhai
et al., 2019). It depicts how we get a subset of “proxy” instances for
calculating classification loss.

To sample pairs for training a siamese network, we follow the sampling
methodology in (He et al., 2016a). Similarly, we guarantee that each of our
positive pairs comes from different categories (“heterogeneous dyads”) while
negatives are randomly sampled regardless of category. This is done to
dissuade learning visual similarity in place of style compatibility. We then
optimize using contrastive loss:

$\mathcal{L}_{contrast}(i,j):=y_{ij}D^{2}_{ij}+(1-y_{ij})[\alpha-
D_{ij}]^{2}_{+}$

where $D_{ij}$ denotes the distance between samples $i$ and $j$, and $y_{ij}$
is $1$ if samples $i$ and $j$ have the same label and $0$ otherwise.

We also train a triplets network by sampling _(anchor_image, pos_image,
neg_image)_. This is similar to the scene-based CTL paper (Kang et al., 2018),
where they trained a triplet network using _(anchor_scene, pos_product,
neg_product)_. In our case, however, every item in the triplet is a crop of a
product. We optimize using the loss function:

$\mathcal{L}_{triplet}(a,p,n):=[D^{2}_{ap}-D^{2}_{an}+\alpha]_{+}$

where $a$, $p$, $n$ denote the query, positive, and negative samples
respectively; $D^{2}_{ap}$ denotes the distance between the anchor and
positive samples, $D^{2}_{an}$ denotes the distance between the anchor and
negative samples; and $\alpha$ is the margin term.

###  5.2. Training and deployment details

We train our models using the PyTorch framework (Paszke et al., 2019) with 8
GPUs and the model takes about 10 hours to converge. We use Apex (ape, [n.d.])
mixed precision to increase training efficiency. We use the Adam optimizer
with learning rate of 0.048. For deployment, we deploy the PyTorch model to
C++ directly by serializing to TorchScript.

##  6\. Evaluation

###  6.1. Methods

Evaluating style compatibility is challenging because of its subjective
nature. We compare our model performance using multiple methods to get a
comprehensive assessment. We have a test set of 25K outfits (109,847 items),
which we use to measure retrieval recall and Fill-in-the-Blank (FITB)
accuracy. We also perform end-to-end evaluation on Pinterest’s real product
corpus, leveraging our in-house fashion specialists for labeling. Lastly, CTL
is launched internally, allowing us to conduct user studies and gain valuable
insights about how real users think when they use the product.

####  6.1.1. Recall@{1, 5, 10}

We measure the retrieval recall on a sub-sampled corpus. Since CTL is
ultimately used in a retrieval setting, measuring Recall@K (R@K) most closely
mirrors the production task.

In order to calculate exact recall, we limit the number of items per outfit in
the test set to be exactly five, removing outfits that do not meet this
criteria. For each item of an outfit, we calculate the R@{1, 5, 10} by
retrieving the top matches using k-nearest neighbors, with euclidean distance
between style embeddings as the distance measure. The retrieval corpus
includes the other items from the same outfit (positives) and randomly sampled
items (negatives). We calculate R@K according to two ways of generating the
corpus: 1) sampled across all categories, and 2) restricted to one category at
a time (and taking the mean). In both cases, the total size of the retrieval
corpus is N=200. Thus, R@K is computed by the following:

$R@K=\dfrac{{(\\#\;positives\;in\;top\;K)}}{min[(total\;num\;items\;in\;outfit)-1,K]}$

Since metrics gathered from both methods of sampling are highly correlated, we
only report on the latter in this paper for simplicity. In Figure 9, we
visualize some results from the retrieval task.

Figure 9. Example of the retrieval evaluation. For each item in an outfit, we
calculate R@{1,5,10}. The result is considered correct if it belongs to the
same outfit as the query.

####  6.1.2. Fill-in-the-Blank (FITB)

For the FITB task, we remove one item from each outfit. The model then has to
pick from the positive item and three randomly sampled items that belong to
the same category. Unlike the retrieval task, FITB uses multiple products as
queries rather than just a single product. Current SOTA methods for this task
(e.g., (Han et al., 2017), (Vasileva et al., 2018)) are not suited for our
large-scale one product to multi-complementary product retrieval.

A downside of both R@K and FITB evaluation tasks is that they only consider
clothing articles from the same “polyvore”-style image to be positive examples
for a given query clothing article. In fact, it’s likely that clothing
articles from other “polyvore”-style images in the test corpus could be
compatible with the query; for instance, blue jeans tend to be compatible with
many other items. We address this shortcoming by using human evaluation (see
Section 6.1.3).

####  6.1.3. Human Judgment

Human judgment is extremely valuable because it directly evaluates how our
models perform compared with a human stylist. The labeling template we
developed is shown in Figure 10. Since this is a highly specialized task, we
decided to only use in-house fashion specialists who follow a comprehensive
set of labeling guidelines. These labeling guidelines describe each failure
mode (e.g. mismatch color, print, season) with examples and attempt to reduce
any subjectivity. We have picked the best performing variant for each of
{Siamese, Triplets, and Classification} (refer to Section 5.1) for comparison.

The questions for this task were generated by sampling 120 products from
Pinterest and running the CTL system end-to-end (see Figure 2). We compute
precision by evaluating whether each $(query,candidate)$ pair is a compatible
match. In addition, we also asked for qualitative feedback such as common
failures and most jarring mistakes. Both quantitative and qualitative feedback
can be found in Section 6.5.

Figure 10. Human evaluation task: for each model, we retrieve CTL results for
a sampled set of products, and ask whether each $(query,candidate)$ pair is
compatible.

###  6.2. Comparing style extractor training methods

We explored several approaches to training the CTL style extractor for the
fashion visual complements task (refer to 5.1). We report metrics on
R@{1,5,10} and FITB accuracy using our test set.

Scene-based CTL. This is the same dataset and model as (Kang et al., 2018),
and we include this evaluation as a baseline (See Table 4). This model was
trained for the task of retrieving complementary products given a scene image
(e.g., the beach). The training uses (anchor_scene, positive_product,
negative_product) with triplet loss, and a separate network for scene and
product images. For this evaluation, we only use the product network since
there are no scenes in our dataset. We see that style embeddings trained in
this manner do not generalize well to the new task of product-to-products
recommendation.

Classification with “proxy” loss. We found that training for the
classification task as described in Section 5.1 showed promising qualitative
results, but performed worse than metric learning methods (See Table 4).

Siamese. We train with contrastive loss. We try the sampling strategy
described in (He et al., 2016a) of 16:1 negative-to-positive ratio, but we
find that a simple 1:1 strategy performs better (See Table 4).

Triplets. We generate triplets $(anchor,positive,negative)$ from our outfits
by taking any two items from the same outfit as anchor and positive. We
compare performance when sampling negatives randomly or from the same category
as positives. We found that triplets training while restricting by category
out-performs all other methods (See Table 4).

Method | R@1 | R@5 | R@10 | FITB
---|---|---|---|---
CTL(scene-based) | 3.9 | 16.5 | 29.6 | 40.1
Classification | 15.8 | 41.6 | 58.8 | 71.9
Siamese(16:1) | 15.2 | 40.7 | 57.6 | 71.9
Siamese(1:1) | 16.0 | 46.0 | 64.3 | 74.3
Triplets(random) | 18.5 | 49.4 | 67.5 | 77.6
Triplets(cat) | 20.3 | 51.4 | 68.8 | 78.5
Table 4. Recall@1,5,10 and FITB metrics for different CTL training methods.

###  6.3. Comparing visual featurizers

In this section we compare the effects of using Unified Embedding, which has
the advantage of additional training on Pinterest data, versus ImageNet for
weight initialization of the visual featurizer. These experiments were
conducted using triplet loss with category-restricted sampling, which is our
best performing model (see Table 4).

We find that pretraining on Pinterest data yields substantial gains relative
to using default ImageNet weights, with an R@1 gain from 17.6% to 20.3% (see
Table 5). This suggests that there is a substantial domain shift from ImageNet
images to Pinterest images.

Method | R@1 | R@5 | R@10 | FITB
---|---|---|---|---
ImageNet | 17.6 | 47.2 | 64.0 | 75.5
Unified | 20.3 | 51.4 | 68.8 | 78.5
Table 5. A comparison of ImageNet vs. Unified Embedding weight initialization
for the visual featurizer.

###  6.4. Comparing training set sizes

In this section we compare how decreasing training set size affects
performance (see Table 6). This helps us answer the question, “How much
training data is enough?”. We use triplet loss with category-restricted
sampling, which is our best performing model in Table 4. Performance on the
test set continues to increase as we add training examples, although 10K to
100K outfits sees a significant improvement (R@1 12.1% -¿ 16.4%) while 100K to
1M outfits sees a lesser gain (R@1 16.4% -¿ 20.3%).

#Outfits | #Objects | R@1 | R@5 | R@10 | FITB
---|---|---|---|---|---
10K | 46K | 12.1 | 37.0 | 54.1 | 66.0
100K | 453K | 16.4 | 44.3 | 62.6 | 74.8
200K | 835K | 16.8 | 46.3 | 64.5 | 75.1
500K | 2.1M | 19.1 | 49.2 | 66.6 | 77.1
1M (full) | 4.13M (full) | 20.3 | 51.4 | 68.8 | 78.5
Table 6. An ablation of model performance versus training dataset size. The
100K dataset is released.

###  6.5. Human evaluation and qualitative feedback

We asked our in-house fashion specialists to evaluate the end-to-end CTL
quality through the eyes of a stylist (refer to Section 6.1.3). The results
are shown in Table 7 and Figure 11. The quantitative results are consistent
with our other evaluations, and shows that the triplet loss with category-
restricted sampling is the best performing model.

Method | Overall Precision
---|---
Siamese (1:1) | 47.7
Classification | 50.6
Triplets (cat) | 55.0
Table 7. Human evaluation results comparing best performing variants from
Table 4. Figure 11. Example of correct vs. incorrect evaluation results for a
given query, by the standards of a human stylist.

We also asked our in-house specialists for qualitative feedback, and it was
clear from their feedback that—when compared with a human stylist—CTL relies
more on color and pattern matching. This can result in recommendations that
either lack diversity or the “human touch” if matches are always the same
color or pattern, or are extremely off if the color or pattern does not match
entirely. This suggests additional investigation into ensuring that there is
sufficient clothing diversity in the training set, as Section 4.3 describes.

Figure 12. Complete The Look retrieval results from Pinterest product corpus.
The first column is the query image and the four images to the right are
recommendations from different categories.

###  6.6. User studies

As of early 2020, we have a prototype of CTL that is released internally.
Qualitative results can be found in Figure 12. Although we expect more
improvements before general launch, this prototype enabled us to conduct user
studies to get early feedback.

We invited 5 Pinterest users to come in for hour-long sessions during which we
guided them through using the CTL product feature. Users had high expectations
for CTL results, and they wanted to see matches that resembled curation from a
human stylist. Overall, the user studies demonstrated that users do see the
value of the CTL product, which confirms our continued investment in building
it out.

##  7\. Conclusion and future work

We shared our approach and results from bootstrapping to productionizing the
Complete The Look (CTL) system.

We implemented an automated data pipeline that generates a labeled image
dataset for the fashion outfit recommendation task. For our model, we ran
comprehensive sets of experiments comparing multiple methods, relying on
offline metrics such as R@K that best mirror our product use case. Serving the
model in production proved challenging as the problem scaled to tens of
millions of unique products. To keep recommendation quality high, we trained
and utilized image classifiers that help us trigger CTL only on images that
match the training set’s domain.

In the future, we hope to add more training data from different image styles
(e.g., cropped outfit, full outfit, stock photo) to make the model more robust
to domain variations. We also hope to incorporate price as an input, since it
is a poor user experience to match a $8,000 ring with a $20 dress.
Furthermore, we hope to add user personalization, so that we can tailor
recommendations to a particular user’s style.

##  8\. Acknowledgments

The authors would like to thank the rest of the visual search team, especially
Chuck Rosenberg for his leadership, Kofi Boakye for his thoughtful editing,
and Angela Guo for her feedback and guidance. We would also like to thank
Mariellen Barros and Marta Scotto for labeling efforts; Joyce Zha, Claire Li,
and Suzy Kim for frontend support; Cherrylyn Cawit and Shilpa Banerjee for
conducting user studies.

## References

  * (1)
  * ape ([n.d.]) [n.d.].  apex.amp - Apex 0.1.0 documentation.  https://nvidia.github.io/apex/amp.html.  (Accessed on 06/12/2020).
  * Bell and Bala (2015) Sean Bell and Kavita Bala. 2015.  Learning Visual Similarity for Product Design with Convolutional Neural Networks.  _ACM Trans. Graph._ 34, 4, Article 98 (July 2015), 10 pages.  https://doi.org/10.1145/2766959
  * Chen et al. (2019) Wen Chen, Pipei Huang, Jiaming Xu, Xin Guo, Cheng Guo, Fei Sun, Chao Li, Andreas Pfadler, Huan Zhao, and Binqiang Zhao. 2019.  POG: Personalized Outfit Generation for Fashion Recommendation at Alibaba iFashion.  (05 2019).
  * Cui et al. (2019) Zeyu Cui, Zekun Li, Shu Wu, Xiaoyu Zhang, and Liang Wang. 2019.  Dressing as a Whole: Outfit Compatibility Learning Based on Node-wise Graph Neural Networks.  (02 2019).  https://doi.org/10.1145/3308558.3313444
  * Girshick et al. (2018) Ross Girshick, Ilija Radosavovic, Georgia Gkioxari, Piotr Dollár, and Kaiming He. 2018\.  Detectron.  https://github.com/facebookresearch/detectron.
  * Gu (2019) Kunlong Gu. 2019\.  Automating Shop the Look on Pinterest - Pinterest Engineering Blog - Medium.  https://medium.com/pinterest-engineering/automating-shop-the-look-on-pinterest-a17aeff0eae2.  (Accessed on 02/02/2020).
  * Han et al. (2017) Xintong Han, Zuxuan Wu, Yu-Gang Jiang, and Larry S. Davis. 2017\.  Learning Fashion Compatibility with Bidirectional LSTMs. In _Proceedings of the 25th ACM International Conference on Multimedia_ (Mountain View, California, USA) _(MM ’17)_. Association for Computing Machinery, New York, NY, USA, 1078–1086.  https://doi.org/10.1145/3123266.3123394
  * He et al. (2016a) Ruining He, Charles Packer, and Julian McAuley. 2016a.  Learning Compatibility Across Categories for Heterogeneous Item Recommendation. 937–942.  https://doi.org/10.1109/ICDM.2016.0116
  * He et al. (2016b) Ruining He, Charles Packer, and Julian McAuley. 2016b.  Learning Compatibility Across Categories for Heterogeneous Item Recommendation. 937–942.  https://doi.org/10.1109/ICDM.2016.0116
  * Hoffer and Ailon (2014) Elad Hoffer and Nir Ailon. 2014.  Deep Metric Learning Using Triplet Network.  https://doi.org/10.1007/978-3-319-24261-3_7
  * Hsiao and Grauman (2017a) Wei-Lin Hsiao and Kristen Grauman. 2017a.  Creating Capsule Wardrobes from Fashion Images.  _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2017), 7161–7170.
  * Hsiao and Grauman (2017b) Wei-Lin Hsiao and Kristen Grauman. 2017b.  Learning the Latent ”Look”: Unsupervised Discovery of a Style-Coherent Embedding from Fashion Images.  (07 2017).
  * Hu et al. (2017) Jie Hu, Li Shen, and Gang Sun. 2017.  Squeeze-and-Excitation Networks.  _CoRR_ abs/1709.01507 (2017).  arXiv:1709.01507 http://arxiv.org/abs/1709.01507
  * Huang et al. (2015) Junshi Huang, Rogerio Feris, Qiang Chen, and Shuicheng Yan. 2015\.  Cross-Domain Image Retrieval with a Dual Attribute-Aware Ranking Network.  (05 2015).  https://doi.org/10.1109/ICCV.2015.127
  * Jagadeesh et al. (2014) Vignesh Jagadeesh, Robinson Piramuthu, Anurag Bhardwaj, Wei di, and Neel Sundaresan. 2014\.  Large Scale Visual Recommendations From Street Fashion Images.  _Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (01 2014).  https://doi.org/10.1145/2623330.2623332
  * Jing et al. (2015) Yushi Jing, David C. Liu, Dmitry Kislyuk, Andrew Zhai, Jiajing Xu, Jeff Donahue, and Sarah Tavel. 2015.  Visual Search at Pinterest.  _CoRR_ abs/1505.07647 (2015).  arXiv:1505.07647 http://arxiv.org/abs/1505.07647
  * Kang et al. (2018) W. C. Kang, E. Kim, J. Leskovec, C. Rosenberg, and J. McAuley. 2018.  Complete the Look: Scene-based Complementary Product Recommendation.  _arXiv:1812.01748_ (2018).  arXiv:arXiv:1812.01748
  * Kovashka et al. (2012) Adriana Kovashka, Devi Parikh, and Kristen Grauman. 2012\.  WhittleSearch: Image Search with Relative Attribute Feedback.  _Proceedings / CVPR, IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ 115, 2973–2980.  https://doi.org/10.1109/CVPR.2012.6248026
  * Lee et al. (2017) Hanbit Lee, Jinseok Seol, and Sang-goo Lee. 2017.  Style2Vec: Representation Learning for Fashion Items from Style Sets.  (08 2017).
  * Li et al. (2016) Yuncheng Li, Liangliang Cao, Jiang Zhu, and Jiebo Luo. 2016\.  Mining Fashion Outfit Composition Using An End-to-End Deep Learning Approach on Set Data.  _IEEE Transactions on Multimedia_ PP (08 2016).  https://doi.org/10.1109/TMM.2017.2690144
  * Lin et al. (2016) Tsung-Yi Lin, Piotr Dollár, Ross B. Girshick, Kaiming He, Bharath Hariharan, and Serge J. Belongie. 2016.  Feature Pyramid Networks for Object Detection.  _CoRR_ abs/1612.03144 (2016).  arXiv:1612.03144 http://arxiv.org/abs/1612.03144
  * Liu et al. (2012) Si Liu, Tam Nguyen, Jiashi Feng, Meng Wang, and Shuicheng Yan. 2012.  Hi, magic closet, tell me what to wear! 1333–1334.  https://doi.org/10.1145/2393347.2396470
  * Liu et al. (2016) Ziwei Liu, Ping Luo, Shi Qiu, Xiaogang Wang, and Xiaoou Tang. 2016.  DeepFashion: Powering Robust Clothes Recognition and Retrieval with Rich Annotations. 1096–1104.  https://doi.org/10.1109/CVPR.2016.124
  * M. Hadi Kiapour (2014) Alexander C. Berg Tamara L. Berg M. Hadi Kiapour, Kota Yamaguchi. 2014.  Hipster Wars: Discovering Elements of Fashion Styles. In _European Conference on Computer Vision_.
  * M. Hadi Kiapour (2015) Svetlana Lazebnik Alexander C. Berg Tamara L. Berg M. Hadi Kiapour, Xufeng Han. 2015.  Where to Buy It:Matching Street Clothing Photos in Online Shops. In _International Conference on Computer Vision_.
  * Matzen et al. (2017) Kevin Matzen, Kavita Bala, and Noah Snavely. 2017\.  StreetStyle: Exploring world-wide clothing styles from millions of photos.  _arXiv preprint arXiv:1706.01869_ (2017).
  * McAuley et al. (2015) Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Hengel. 2015.  Image-Based Recommendations on Styles and Substitutes.  (06 2015).  https://doi.org/10.1145/2766462.2767755
  * Ng ([n.d.]) Vincent Ng. [n.d.].  Flashlight for Pinterest - Visual Discovery on Steroids.  http://www.mcngmarketing.com/flashlight-pinterest-visual-discovery-steroids/.  (Accessed on 02/05/2020).
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  PyTorch: An imperative style, high-performance deep learning library. In _Advances in Neural Information Processing Systems_. 8024–8035.
  * Ren et al. (2015) Shaoqing Ren, Kaiming He, Ross B. Girshick, and Jian Sun. 2015\.  Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks.  _CoRR_ abs/1506.01497 (2015).  arXiv:1506.01497 http://arxiv.org/abs/1506.01497
  * Simo-Serra and Ishikawa (2016) Edgar Simo-Serra and Hiroshi Ishikawa. 2016.  Fashion Style in 128 Floats: Joint Ranking and Classification Using Weak Data for Feature Extraction. 298–307.  https://doi.org/10.1109/CVPR.2016.39
  * Song et al. (2017) Xuemeng Song, Fuli Feng, Jinhuan Liu, Zekun Li, Liqiang Nie, and Jun Ma. 2017\.  NeuroStylist: Neural Compatibility Modeling for Clothing Matching. 753–761.  https://doi.org/10.1145/3123266.3123314
  * Vasileva et al. (2018) Mariya Vasileva, Bryan Plummer, Krishna Dusad, Shreya Rajpal, Ranjitha Kumar, and David Forsyth. 2018\.  Learning Type-Aware Embeddings for Fashion Compatibility.  (03 2018).
  * Wang and Zhang (2011) Xianwang Wang and Tong Zhang. 2011.  Clothes search in consumer photos via color matching and attribute learning. 1353–1356.  https://doi.org/10.1145/2072298.2072013
  * Xie et al. (2016) Saining Xie, Ross B. Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. 2016.  Aggregated Residual Transformations for Deep Neural Networks.  _CoRR_ abs/1611.05431 (2016).  arXiv:1611.05431 http://arxiv.org/abs/1611.05431
  * Zhai ([n.d.]) Andrew Zhai. [n.d.].  Building Pinterest Lens: a real world visual discovery system.  https://medium.com/pinterest-engineering/building-pinterest-lens-a-real-world-visual-discovery-system-59812d8cbfbc.  (Accessed on 02/05/2020).
  * Zhai et al. (2019) Andrew Zhai, Hao-Yu Wu, Eric Tzeng, Dong Huk Park, and Charles Rosenberg. 2019.  Learning a Unified Embedding for Visual Search at Pinterest. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Anchorage, AK, USA) _(KDD ’19)_. Association for Computing Machinery, New York, NY, USA, 2412–2420.  https://doi.org/10.1145/3292500.3330739