PaperlayerView exact revision on arXiv

Source-linked AI summary

SEE: Strategic Exploration and Exploitation for Cohesive In-Context Prompt Optimization

Wendi Cui, Zhuohang Li, Hao Sun, Damien Lopez, Kamalika Das, Bradley Malin, Sricharan Kumar, Jiaxin Zhang

arXiv:2402.11347v2cs.CL

TL;DR

Prompt optimization is difficult because natural-language prompts occupy a discrete, high-dimensional space, and existing approaches often optimize instructions and examples separately. SEE jointly optimizes these components through a metaheuristic exploration–exploitation framework; it reports strong benchmark performance while reducing computational costs.

  • Problem

    Automatic prompt optimization must search a discrete, high-dimensional space, while separate optimization of instructions and examples can overlook their interaction.

    Source: §1 · p. 2

  • Method

    SEE uses metaheuristic optimization to jointly refine prompt instructions and examples, alternating exploration and exploitation while adaptively selecting LLM operators.

    Source: §1 · p. 2

  • Results

    13.94 task accuracy improvement and 58.67% computational-cost reduction over SOTA methods are reported for SEE on harder BBH tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    SEE dynamically generates zero-shot and few-shot prompts, adapting prompt form to task requirements.

    Source: §5 · p. 9

    SEE still requires around 12 iterations and 4,000 API calls, which may be insufficient for large-scale online applications.

    Source: §6 · p. 10

Abstract

from arXiv · show

Designing optimal prompts for Large Language Models (LLMs) is a complicated and resource-intensive task, often requiring substantial human expertise and effort. Existing approaches typically separate the optimization of prompt instructions and in-context learning examples, leading to incohesive prompts that are defined and represented by suboptimal task performance. To overcome these challenges, we propose a novel Cohesive In-Context Prompt Optimization framework that refines both prompt instructions and examples. However, formulating such an optimization in the discrete and high-dimensional space of natural language poses significant challenges in both convergence and computational efficiency. To address these issues, we introduce SEE, a scalable and efficient prompt optimization framework that adopts metaheuristic optimization principles and strategically balances exploration and exploitation to enhance optimization performance and achieve efficient convergence. SEE features a quad-phased design that alternates between global traversal (exploration) and local optimization (exploitation) and adaptively chooses LLM operators during the optimization process. We have conducted a comprehensive evaluation across 35 benchmark tasks, and SEE significantly outperforms state-of-the-art baseline methods by a large margin, achieving an average performance gain of 13.94 while reducing computational costs by 58.67.

1 Introduction

Automatic prompt optimization must navigate a difficult joint space, while existing approaches often separate instructions and examples. SEE jointly optimizes prompt components and balances exploration with exploitation to improve performance and reduce computational costs.

1 Introduction

  • Automatic prompt optimization matters because manual prompt design requires substantial human effort and expertise.Prompt engineering can improve LLM performance, and automatic optimization is presented as a way to reduce that effort.Source: §1 · p. 1
  • Existing approaches optimize instructions or examples separately, overlooking their interplay and potentially producing suboptimal performance.SEE instead treats the instruction and examples as a cohesive prompt, without restricting prompts to zero-shot or few-shot styles.Source: §1 · pp. 1–2
  • 13.94 task accuracy improvement and 58.67% computational-cost reduction over SOTA methods are reported for SEE on harder BBH tasks.The evaluation compares SEE with nine SOTA methods across 35 benchmark tasks.Source: §1 · p. 2
  • SEE applies metaheuristic optimization to jointly refine prompt instructions and examples, supporting both zero-shot and few-shot prompts.The paper describes this as the first framework with that capability.Source: §1 · p. 2
  • SEE alternates exploration and exploitation across four phases and adaptively selects among five LLM operators during optimization.It also uses performance-based vectors with Hamming distance for task-aware similarity and adaptive phase-stop criteria.Source: §1 · p. 2

2 Preliminaries

Prompt optimization searches for a natural-language prompt that maximizes task performance, but its discrete, high-dimensional search space makes optimization difficult. The section also outlines the iterative components of metaheuristic methods.

Problem Formulation

  • The objective is to find a natural-language prompt that maximizes an LLM's performance on task input/output pairs.A prompt comprises an instruction and in-context examples, and performance is measured by a metric such as accuracy.Source: §2 · pp. 2–3
  • The prompt search space is discrete, intractable, and arbitrarily high-dimensional, making the optimization problem extremely difficult.The objective function evaluates prompt performance on the task data using the LLM.Source: §2 · p. 3

Metaheuristic Optimization Framework

  • Metaheuristic optimization iteratively initializes candidates, generates variations, and selects or prunes candidates using an objective function.Examples cited include genetic algorithms, particle swarm optimization, and differential evolution.Source: §2 · p. 3
  • A metaheuristic process continues until a termination criterion, such as convergence or a computational limit, is met.The methods are described as applied in engineering design, scheduling, and machine learning.Source: §2 · p. 3

3 Proposed Method: Strategic Exploration and Exploitation (SEE)

SEE jointly optimizes prompt instructions and examples through a four-phase metaheuristic that alternates exploration and exploitation. It selects operators for each phase and uses development-set performance to guide candidate selection and stopping.

3.1 Intuition

  • SEE divides optimization into four phases and uses operators suited to each phase to pursue faster convergence and improved performance.The framework aims to deliver cohesive combinations of instructions and examples across tasks.Source: §3.1 · p. 3

3.2 Generation Operators

  • Five operators support generation and variation: Lamarckian, EDA, Crossover, Feedback, and Semantic, with global operators supporting exploration and local operators supporting exploitation.In operator tests, Lamarckian introduced diverse samples; Feedback converged faster but required two API/inference calls; EDA and Crossover had higher improvement probability.Source: §3.2 · p. 4

3.3 SEE Framework

  • SEE evaluates candidates on Ddev and uses performance scores for greedy selection and pruning across its optimization phases.The framework distinguishes Dtrain for initial Lamarckian initialization, Ddev for candidate scoring, and Dtest for final evaluation.Source: §3.3 · p. 4, §3.3.2 · p. 5

3.3.1 Phase 0: Global Initialization

  • Phase 0 creates a diverse initial pool either by reverse-engineering prompts from task input-output pairs or by diversifying expert-composed prompts.The two initializations are SEE-io-pair and SEE-example, respectively.Source: §3.3.1 · p. 5

3.3.2 Phase 1: Local Feedback Operation

  • Phase 1 applies the Feedback Operator to refine each candidate toward a local minimum using an Examiner's guidance and an Improver's revisions.The Examiner generates improvement guidance from candidate mistakes, which the Improver applies.Source: §3.3.2 · p. 5

3.3.3 Phase 2: Global Fusion Operation

  • Phase 2 uses EDA or Crossover to fuse multiple candidates, encouraging exploration and helping the search escape local optima.Candidates are compared using Hamming distance on performance-based vectors to promote diversity.Source: §3.3.3 · p. 5

3.3.4 Phase 3: Local Semantic Operation

  • Phase 3 uses the Semantic Operator for local exploitation, then selects the best candidate for testing on Dtest.The phase targets the final convergence stretch with a more cost-effective operator.Source: §3.3.4 · p. 5

3.4 SEE Novel Design Schemes

  • SEE compares candidates by Hamming distance over vectors of development-set outcomes and uses performance gain plus operator-specific tolerance to decide when phases stop.Global operators may run for a predefined duration without immediate gains, while fast-converging local operators can transition sooner.Source: §3.4 · pp. 5–6

4 Experiments

The experiments evaluate SEE on 35 benchmark tasks spanning three domains, using GPT-3.5-turbo for SEE results unless otherwise specified.

Experimental Setup

  • SEE is evaluated against 9 baselines across the benchmark suite.The reported SEE results use GPT-3.5-turbo unless otherwise specified.Source: §4 · p. 6
  • The experiment setup identifies Appendix E as the source for additional details.Dataset and task details are provided in Appendix E.1.Source: §4 · p. 6

35 Tasks and Datasets

  • The evaluation covers 35 benchmark tasks drawn from three domains: BBH, NLP detection, and instruction induction.The suite includes 8 BBH tasks, 3 NLP detection tasks, and 24 instruction induction tasks.Source: §4 · p. 6

9 Baselines

SEE outperforms strong baselines across BBH, detection, and instruction-induction tasks, while its phased strategy improves optimization performance and reduces computational cost. Analyses also examine model applicability, prompt cohesion, phase design, and prompt-search behavior.

9 Baselines

  • The nine baselines include search- and evolution-based prompt optimizers, while MoP and EASE can optimize instructions and examples simultaneously.The compared methods include APE, APO, OPRO, PromptBreeder, EvoPrompt, MoP, EASE, ZOPO, and AELP.Source: §9 · pp. 6–7

4.1 Main Results

  • SEE improves average BBH performance over AELP by +15.31, EvoPromopt by +13.29, and OPRO by +13.21.The evaluation covers eight BBH tasks.Source: §4.1 · p. 7
  • On detection tasks, SEE gains +1 on Ethos, +4 on Sarcasm, and +18 on Liar relative to APO.The largest reported gain is on the more complex Liar task.Source: §4.1 · p. 7
  • SEE outperforms APE and MoP on 87.5% of instruction-induction tasks, PromptBreeder on 91.7%, EvoPrompt, OPRO, and ZOPO on 100%, and EASE on 66.7%.The comparison spans 24 instruction-induction tasks.Source: §4.1 · p. 7

4.2 Analysis

  • Across tested models, GPT-4 performs best on all tasks, followed by Llama3-70B; randomly adding few-shot examples improves OPRO on 1/4 tasks and EvoPrompt on 2/4.SEE uses the same hyperparameter configuration across 35 tasks and reports competitive results on seven additional models.Source: §4.2 · p. 7, Table 3 · p. 7, Table 4 · p. 7

Phase Optimization vs Random Optimization

  • SEE beats random optimization in average score across four BBH tasks and has a better top score on two; removing Phase 1 causes the greatest observed degradation.Phase 0 is retained because it generates the initial candidate population.Source: Phase Optimization vs Random… · pp. 7–8, Table 5 · p. 8, Figure 4 · p. 8
  • Performance-vector Hamming distance beats embedding cosine similarity in average and maximum scores, while average prompt length can rise, fall, or oscillate during optimization.Reported task-specific gains include +5.2 on Disambiguation and +4.6 on Hyperbaton.Source: Phase Optimization vs Random… · p. 8, Table 6 · p. 8, Figure 5 · p. 9
  • SEE reduces computational cost by several orders of magnitude versus other strategies; PromptBreeder uses approximately 2.5 orders of magnitude more API calls, and SEE remains most efficient by token consumption on formal fallacies.Prompt lengths vary as operators add or remove examples; SEE generates few-shot prompts for 20/24 instruction-induction tasks and 4/8 BBH tasks.Source: Phase Optimization vs Random… · pp. 8–9, Figure 6 · p. 9

5 Conclusion

The conclusion presents SEE as a metaheuristic framework for jointly optimizing prompt instructions and examples. It emphasizes the exploration–exploitation schedule and adaptive operators, alongside performance and cost outcomes and flexible generation of zero-shot and few-shot prompts.

5 Conclusion

  • SEE applies metaheuristic optimization principles to jointly optimize prompt instructions and examples.The framework is described as cohesive in-context prompt optimization.Source: §5 · p. 9
  • Its exploration–exploitation schedule and adaptive operator application accompany reported state-of-the-art performance and reduced computational cost across benchmark tasks.The conclusion characterizes the benchmarks as diverse.Source: §5 · p. 9
  • SEE dynamically generates both few-shot and zero-shot prompts, adapting to task requirements.Source: §5 · p. 9

6 Limitations

SEE’s operator set combines distinct ways to generate prompt candidates, while the related-work discussion contrasts these methods with existing prompt-optimization approaches. The authors identify remaining limits in API cost and single-objective scope.

6 Limitations

  • SEE still requires around 12 iterations and 4,000 API calls, which may be insufficient for large-scale online applications.The authors also identify multi-objective optimization, such as jointly improving accuracy, interpretability, efficiency, or safety, as future work.Source: §6 · p. 10

A Related Work

  • Prior prompt-optimization methods include continuous soft-prompt tuning and discrete-token approaches, with concerns about interpretability, black-box access, scalability, reliability, and efficiency.More recent LLM-based methods often focus on optimizing instructions; SEE instead combines exploration and exploitation with adaptive operator selection.Source: A Related Work · p. 13

B Operator Definition

  • SEE uses seven operators across five classes to provide diverse candidate-generation strategies.The paper compares these operators with those used by other methods in Table 7.Source: B Operator Definition · p. 14, Table 7 · p. 15

B.1 Lamarckian Operator

  • SEE’s Lamarckian operator reverse-engineers an instruction from task input-output pairs, allowing candidate prompts to be generated without prior task knowledge.It follows principles used in APE and PromptBreeder.Source: §B.1 · p. 14

B.2 Feedback Operator

  • The Feedback operator examines a prompt’s failures, turns them into advice, and applies that advice to generate a revised prompt.The method describes this as a fast-converging local search component combined with other operators.Source: §B.2 · p. 14

B.3 ESTIMATION OF DISTRIBUTION Operator

  • EDA generates candidates from a selected, diverse subset of high-performing prompts; EDA+Index additionally uses prompt ordering.The subset is randomized before being given to the LLM; EDA+Index orders it by performance while informing the LLM that candidates are ranked in descending order.Source: §B.3 · pp. 14–15

B.4 Crossover Operator

  • Crossover combines features from two parent prompts, while CR+D pairs the best candidate with its most distinct counterpart.The distance between prompts is measured using a similarity score.Source: §B.4 · p. 15

B.5 Semantic Operator

  • The Semantic operator generates a new candidate that shares the source prompt’s semantic meaning.It is applied to every candidate in the current pool.Source: §B.5 · p. 15

C.1 Few-Shot Additional / Removal Analysis

This analysis examines how operators add or remove few-shot examples, a capability the paper identifies as important for traversing the in-context prompt space.

C.1 Few-Shot Additional / Removal Analysis

  • Few-shot addition and removal are examined as operator capabilities relevant to traversing the in-context prompt space.The section provides examples of operators adding or removing few-shot examples.Source: §C.1 · p. 15
  • One displayed example gives the input “92 24” and output “68” before an instruction is introduced.The preceding text frames the example as an input-output pair for a friend given an instruction and examples.Source: §C.1 · p. 16
  • The examples include Lamarckian and Feedback operations that add few-shot examples.Table 8 covers Lamarckian addition, and Table 9 covers feedback-based addition.Source: Table 8 · p. 16, Table 9 · p. 17
  • The examples also include Feedback and Semantic operations that remove few-shot examples.Table 10 describes feedback-based removal; Table 11 is labeled as Semantic Operator removal.Source: Table 10 · p. 18, Table 11 · p. 19

C.2 Operator Feature Analysis

The operator analysis compares improvement likelihood and convergence speed across four operators, then relates those patterns to how long each operator should be allowed to run. It also describes SEE’s unrestricted operator prompts.

C.2 Operator Feature Analysis

  • The preliminary experiment averages operator performance across four randomly seeded initial pools and applies each operator five times per round over five rounds.The tasks are Causal Judgement, Salient Translation Error Detection, Disambiguation QA, and Hyperbaton; each operator is run 100 times.Source: §C.2 · p. 20
  • Crossover and EDA produce improvements in more steps than Semantic, while Feedback produces the fewest improvements.Figure 7 reports the number of improvement occurrences by operator.Source: Figure 7 · p. 20, §C.2 · p. 20
  • The authors set operator tolerance to 4 for EDA and Crossover but 1 for Feedback and Semantic, interpreting the latter pair as reaching a local minimum quickly.They recommend more patience with EDA and Crossover because later applications may still improve performance.Source: §C.2 · p. 21
  • EDA and Crossover show similar improvement counts across steps; their first four steps have nearly equal improvement ratios, although the first step brings the most improvement.The analysis evaluates improvement counts and average percentage gain across five consecutive applications.Source: §C.2 · p. 20, Figure 8 · p. 21, Figure 9 · p. 21
  • Feedback and Semantic show significantly more improvement in the first step than later steps; for Feedback, step 1 accounts for over 34% of improvement counts.Figure 8 concerns improvement counts by step, while Figure 9 compares improvement ratios.Source: Figure 8 · p. 21, Figure 9 · p. 21, §C.2 · p. 21

D Operator Prompts

  • SEE’s operator prompts avoid restrictions that other frameworks place on feedback, crossover, or semantic operations.The prompt descriptions include whole-prompt feedback and application, EDA+Index ordering, and semantic changes that may extend to intentions.Source: D Operator Prompts · p. 22, Table 13 · p. 22, Table 14 · p. 23

E Details of Experiments

The experiments use GPT-3.5-turbo operator agents and evaluate selected prompts on test data. The paper reports averaged results across repeated runs for BBH and APO tasks.

E Details of Experiments

  • GPT-3.5-turbo agents implement the operators, and accuracy is computed only for successful API responses because security guardrails block some calls.The study compares GPT-3.5 and GPT-4 on four BBH tasks and all other tasks.Source: E Details of Experiments · p. 25
  • Prompts are selected by development-set score, and their scores are reported on the test set.For BBH and APO, the authors conduct three end-to-end runs and report average performance and standard deviation.Source: E Details of Experiments · p. 25

E.1 Benchmark tasks

The appendix specifies the benchmark tasks, comparison baselines, and SEE implementation settings used in the experiments.

E.1 Benchmark tasks

  • The evaluation covers instruction-induction, hate-speech, fake-news, sarcasm, and BBH tasks, with task-specific training, development, and test samples.Instruction Induction uses up to 50 training and development examples; Ethos, Liar, and Sarcasm each use 50/50/150, while BBH uses 125 training/development and up to 125 test examples.Source: §E.1 · p. 25

E.2 Baselines

  • SEE is compared with prompt-optimization baselines spanning search, feedback, evolutionary, and joint instruction-example optimization approaches.The baselines include APE, ZOPO, APO, OPRO, PromptBreeder, EvoPrompt, AELP, MoP, and EASE.Source: §E.2 · p. 25

E.3 SEE Setting

  • SEE uses larger initial pools, operator-specific tolerances, fixed model temperatures, best-candidate stopping checks, and greedy pool selection.The initial pool size is 15 and later pools are 5; operator tolerances imply at least eight applications in phase 2. Operator and evaluation temperatures are 0.5 and 0, respectively.Source: §E.3 · p. 26

F.1 BBH Task Average & Standard Deviation

The appendix reports BBH task performance averaged across three runs, alongside standard deviations.

F.1 BBH Task Average & Standard Deviation

  • Each method was run three times, with average performance and standard deviation reported for BBH tasks.Table 19 is captioned as reporting BBH task averages and standard deviations.Source: §F.1 · p. 27, Table 19 · p. 27

F.2 3 Detect Task for APO

This section presents SEE-generated prompts across text transformations, language generation, classification, extraction, and arithmetic, illustrating their task rules, constraints, and examples. It also reports SEE’s performance against prompt-optimization baselines and describes the human-readable prompts and mix of zero-shot and few-shot formats.

F.3 24 Instruction Induction Tasks

  • SEE outperformed APE zero shot on 23 / 24 tasks, APE few shot on 21 / 24, Prompt Breeder on 22 / 24, MoP on 21 / 24, EvoPrompt, OPRO, and ZOPO on 14 / 14 each, and EASE on 10 / 15.The comparison uses best prompts on 24 instruction-induction tasks; EASE results use instruction, and ZOPO uses the better performance of its two versions.Source: §F.3 · p. 27, Table 21 · p. 28

F.4 Generated Prompt Comparison

  • In the Rhymes comparison, SEE’s prompt was easy to understand with few-shot examples, while APE and ZOPO prompts did not fit the task and Prompt Breeder’s relation to rhyme was unclear.The task was to write a word that rhymes with the input word.Source: §F.4 · p. 28

G.4 Synthetic Few-shot Examples.

  • 97.8% of 92 synthetic few-shot examples were accurate; 24.09% aligned with training samples, and prompt performance remained 94% despite the two inaccurate labels.The manual evaluation covered examples generated on 24 instruction-deduction tasks.Source: §G.4 · p. 34

H Generated Prompts

  • SEE’s best prompts included both few-shot and zero-shot formats, and their few-shot examples were largely generated by the LLM rather than copied from instructions or training sets.The prompts were generated by gpt-3.5.Source: H Generated Prompts · p. 35
  • Generated prompts cover negation, passive-voice rewriting, and pluralization, with instructions for changing verbs, sentence focus, or word endings.The pluralization prompt addresses consonant-y, f/fe, already-plural, and irregular forms.Source: H Generated Prompts · pp. 44, 46
  • Other prompts request rhyming words and everyday synonyms, with guidance to check rhyme quality, spelling, and meaning.The rhyme instructions warn against partial rhymes or mismatched stress; the synonym prompt cautions against words with different connotations.Source: H Generated Prompts · pp. 47, 51
  • Extraction prompts identify a word’s second letter or the first word beginning with a specified letter, returning an empty list when no match exists.The first-match prompt specifies case-insensitive matching and lowercase output.Source: H Generated Prompts · pp. 47, 50
  • Prompts ask models to rate sentence similarity from 1 to 5 with an explanation, or classify sentiment as negative, neutral, or positive.The sentiment prompt emphasizes context and figurative language.Source: H Generated Prompts · pp. 48–49
  • A programming prompt asks for two input numbers to be added and the sum returned as a one-element list containing a string.It instructs converting inputs to integers before addition and converting the result back to a string.Source: H Generated Prompts · p. 50
Loading 2402.11347v2…