PaperlayerView exact revision on arXiv

Source-linked AI summary

One Prompt is not Enough: Automated Construction of a Mixture-of-Expert Prompts

Ruochen Wang, Sohyun An, Minhao Cheng, Tianyi Zhou, Sung Ju Hwang, Cho-Jui Hsieh

arXiv:2407.00256v1cs.AIcs.CLcs.LGstat.ML

TL;DR

A single demo-free instruction may not cover the full problem space of a task. MoP assigns specialized experts to regions using semantically grouped demos and complementary instructions, achieving an 81% average win rate against prior methods across major benchmarks.

  • Problem

    Existing automatic prompting methods search for one demo-free instruction, which may not serve all task instances or cover the full problem space.

    Source: §1 · p. 2

  • Method

    MoP partitions tasks into regions, groups semantically similar demos into experts, and jointly searches for an instruction complementary to each demo group.

    Source: §1 · p. 2

  • Results

    81% average win rate across several major benchmarks against six representative recent methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    MoP’s specialized prompts expand problem-space coverage compared with optimizing a single prompt.

    Source: §1 · p. 2, §7 · p. 9

    The empirical-risk formulation assumes that the demos encapsulate all external information about the task.

    Source: §3 · p. 3

Abstract

from arXiv · show

Large Language Models (LLMs) exhibit strong generalization capabilities to novel tasks when prompted with language instructions and in-context demos. Since this ability sensitively depends on the quality of prompts, various methods have been explored to automate the instruction design. While these methods demonstrated promising results, they also restricted the searched prompt to one instruction. Such simplification significantly limits their capacity, as a single demo-free instruction might not be able to cover the entire complex problem space of the targeted task. To alleviate this issue, we adopt the Mixture-of-Expert paradigm and divide the problem space into a set of sub-regions; Each sub-region is governed by a specialized expert, equipped with both an instruction and a set of demos. A two-phase process is developed to construct the specialized expert for each region: (1) demo assignment: Inspired by the theoretical connection between in-context learning and kernel regression, we group demos into experts based on their semantic similarity; (2) instruction assignment: A region-based joint search of an instruction per expert complements the demos assigned to it, yielding a synergistic effect. The resulting method, codenamed Mixture-of-Prompts (MoP), achieves an average win rate of 81% against prior arts across several major benchmarks.

1. Introduction

Automatic prompt methods often search for one demo-free instruction, which may not cover a task’s full problem space. MoP assigns specialized prompts to regions and reports an 81% average win rate across major benchmarks.

1. Introduction

  • A single demo-free instruction may not serve all task instances or cover the whole problem space, limiting problem-solving potential.Source: §1 · p. 2
  • MoP partitions the problem space into homogeneous regions, each governed by a specialized prompt selected for new queries.Source: §1 · p. 2
  • Each expert pairs demos with an instruction: semantic similarity groups demos, then region-based joint search finds a complementary instruction.Source: §1 · p. 2
  • 81% average win rate across several major benchmarks; MoP surpasses six representative recent methods, with an empirical study spanning 50 tasks.Source: §1 · p. 2

2. Related work

Related work traces prompt optimization from in-context demonstrations and discrete search to LLM-generated prompts. MoP applies the Mixture-of-Experts paradigm to prompt optimization.

Prompt optimization for language generation

  • Prompt optimization evolved from in-context demonstration design to discrete prompt search and then to LLMs optimizing prompts in a human-like manner.Source: §2 · p. 2

Mixture of Experts Paradigm

  • The Mixture-of-Experts paradigm developed from traditional machine learning models into deep networks used across vision, speech, and language tasks.Source: §2 · pp. 2–3
  • MoP extends the architectural Mixture-of-Experts paradigm to prompt optimization by defining each expert as a specialized prompt.Source: §2 · p. 3

3. Preliminaries

The preliminaries define prompts as instructions plus demonstrations and describe automatic prompt optimization and APE. They also identify the single-instruction search space as a limitation of APE.

Terminology

  • A prompt is the full text before a question, divided into task instructions and input-output demonstrations.Source: §3 · p. 3

Prompt Optimization

  • Prompt optimization searches for a demo-free instruction that minimizes empirical risk or maximizes a task-specific score, then uses it with new inputs.Source: §3 · p. 3

APE - Automatic Prompt Engineering

  • APE asks an LLM to generate candidate instructions from sampled training demonstrations and selects one using a held-out validation set.Source: §3 · p. 3

Limitations of APE

  • APE searches only a single demo-free instruction space, which may not cover the complexity of NLP tasks.Source: §3 · p. 3

4. MoP: Mixture-of-Prompts

MoP partitions the problem space into regions, each handled by an expert with demos and an instruction. It assigns demos by semantic similarity, then jointly searches for region-specific instructions that complement them.

4.1. Framework Overview

  • Each expert prompt combines demos carrying local information with an instruction providing general task guidance, and the two are jointly optimized for that expert’s region.The framework seeks to optimize the performance of the entire mixture over data assigned to experts during inference.Source: §4.1 · pp. 3–4

4.2. Demo Assignment

  • Demo assignment clusters training examples into experts based on semantic similarity, motivated by the connection between in-context learning and kernel regression.The method uses K-means in an embedding space; that space need not be the API model’s, provided it reflects high-level semantic similarity.Source: §4.2 · pp. 4–5
  • The clustering objective minimizes between-cluster kernel values while keeping clusters balanced, and is equivalent to K-means in the embedding space.The practical implementation uses K-means-auto and scaled inertia to select the number of experts without biasing toward more clusters.Source: §4.2 · pp. 4–5
  • At inference, each query is routed to its closest expert in the embedding space, which uses its instruction and demos to make the prediction.The assigned expert is determined using the clustering centroids.Source: §4.2 · p. 5

4.3. Instruction Assignment

  • Region-Based Joint Search (RBJS) selects an instruction for each expert after demo assignment, aiming to maximize the performance of the mixture.Candidate instructions are generated using demos assigned to other experts so they can potentially capture information missed by the current expert’s demos.Source: §4.3 · p. 5
  • APE is used to generate candidate instructions, although the method allows other instruction-generation algorithms.The paper chooses APE for simplicity.Source: §4.3 · p. 5
  • RBJS evaluates candidate instructions on routed local validation data because an expert’s performance on its region may not align with performance on the full data distribution.The method routes validation inputs to experts before jointly searching for the instruction-and-demos pair.Source: §4.3 · p. 5

5. Experiments

Experiments compare MoP with prior methods across three prompt-optimization benchmarks and analyze demo clustering and instruction assignment. MoP has an average 81% pairwise win rate across the benchmarks.

5.1. Experimental Setup

  • The evaluation covers three benchmarks spanning coding, math, common-sense reasoning, knowledge retrieval, and other tasks, reporting mean and standard deviation across three runs.The experiments use GPT-3.5-Turbo-Instruct and follow the original APE settings with stated exceptions.Source: §5.1 · pp. 5–6
  • The experiments compare MoP with APE, APE+Demos, APE+K-centroids, InstructZero, IZ+Demos, and IZ+K-centroids.The listed baselines include single-instruction methods and variants that add demonstrations.Source: §5.1 · p. 6

5.2. Analysis

  • The analysis uses Auto categorization with a maximum of four experts and visualizes training, routed-validation, and routed-test demos as distinct shapes.The analysis figure also presents expert-specific task-solving ability and instruction-performance comparisons.Source: §5.2 · p. 6, Figure 2 · p. 6
  • 83% of test inputs have Hit Ratios between 0 and 1 when experts use clustered demos alone, indicating sensitivity to the assigned expert.The authors interpret this as evidence that experts develop distinct specialties and blind spots from their assigned demos.Source: §5.2 · pp. 6–7
  • Candidate-instruction rankings vary across experts, while rankings from random full-validation subsets misalign with those from routed local validation data.The analysis motivates distinct instructions and region-based evaluation during joint search.Source: §5.2 · p. 7

5.3. Main Results

  • MoP outperforms APE + Demos and IZ + Demos by a substantial margin in the showcased results against six prior methods.The main-results section shows 19 tasks and places all results in Appendix J.Source: §5.3 · p. 7
  • 81% average win rate across three benchmarks; MoP’s pairwise win rate dominates all six prior methods.The benchmarks are Instruction-Induction, Super Natural Instructions, and BIG-Bench-Hard.Source: §5.3 · p. 7

6. Ablation Study

The ablations test MoP’s robustness, demo-count sensitivity, clustering, embedding, prompt assignment, and routing choices. Across three benchmarks, MoP outperforms the APE+Demos and IZ+Demos averages, and its win rate averages 81%.

6.1. Robustness of MoP on Out-of-Distribution Data

  • On adversarial OOD data, all methods lose performance, but MoP consistently outperforms the baselines; its region segmentation routes each query to the closest expert region.Source: §6.1 · p. 7, Table 1 · p. 7

6.2. Different Number of Demos

  • MoP outperforms the baselines across the tested demo counts, with reported gains over APE+Demos and IZ+Demos varying by task and demo count.Figure 5 measures task performance against N, the total number of training demos; reported gains are 16.89%, 22.89%, and 2.78% over APE+Demos and 21.67%, 19.88%, and 3.33% over IZ+Demos.Source: §6.2 · p. 7, Figure 5 · p. 8

6.3. Different Clustering Algorithm

  • 52.73% average performance for MoP exceeds 41.39% for APE+Demos and 39.87% for IZ+Demos; MoP’s average win rate against six baselines is 81%.Source: Figure 3 · p. 8, Figure 4 · p. 8
  • K-Means-Auto achieves the best results, while both K-Means variants outperform random clustering.K-Means-Auto automatically selects the number of experts because more experts do not necessarily improve results.Source: §6.3 · pp. 7–8

6.4. Different Embedding Model

  • Ada-002 performs best among the tested encoders, while GPT2-Large also works reasonably well, indicating MoP does not depend on one embedding model.Source: §6.4 · p. 9

6.5. Different Prompt Assignment Algorithms

  • Region-Based Joint Search achieves the best results among the prompt-assignment variants tested.The comparisons test independent search, same-cluster prompt generation, and ranking prompts across all validation data.Source: §6.5 · p. 9

6.6. Different Routing Algorithms

  • Embedding-based routing to the closest expert significantly outperforms random assignment.Source: §6.6 · p. 9

7. Conclusion

MoP replaces a single optimized instruction with expert prompts for specialized problem-space regions. The paper reports improved performance over comparable methods across diverse NLP tasks.

7. Conclusion

  • MoP adapts the Mixture-of-Experts framework by optimizing prompts for specialized regions rather than searching for one instruction, expanding problem-space coverage through divide and conquer.Source: §7 · p. 9
  • Similarity-based demo assignment and region-based joint instruction search equip MoP to improve performance over comparable methods across diverse NLP tasks.Source: §7 · p. 9
  • The paper directs readers to Appendix M for its limitations discussion.Source: §7 · p. 9

Impact Statement

The impact statement acknowledges possible misuse of the framework. The accompanying appendix material covers results, baselines, implementation, examples, algorithms, theory, and search costs.

Impact Statement

  • The authors acknowledge possible misuse of MoP to generate misleading information or promote unethical practices, and call for responsible application.Source: Impact Statement · p. 9

Appendix

  • The appendices include full main-experiment results, additional baselines, implementation details, examples, and a limitations discussion.Source: Appendix · p. 12

A. Comparison with additional baselines

  • On BIG-Bench-Hard, MoP has an 80% win rate against OPRO and a 70% win rate over APE + Nearest Neighbor.The OPRO comparison reruns OPRO with GPT-3.5-Turbo; the nearest-neighbor comparison uses text-embedding-ada-002 for distance.Source: A. Comparison with additional baselines · p. 13

B. Algorithms for MoP

  • The MoP algorithm clusters training demos, forms region-based validation subsets through routing, and selects instructions using validation scores.Source: B. Algorithms for MoP · p. 13

C. Theoretical connection between MoP and MoE

D. Search cost comparison

  • MoP uses one prompt at inference; its search cost with 10 experts is about three times APE’s, but can be reduced through parallelization.Demo assignment requires no LLM queries; prompt assignment scales linearly with experts and is fully parallelizable.Source: D. Search cost comparison · p. 14

E. Qualitative analysis of the discovered experts

MoP experts specialize in different query categories or movie sets, while similar expert specializations provide no benefit for tasks that need no specialized training data. The experiments use the same template across methods.

E. Qualitative analysis of the discovered experts

  • Auto-categorization experts specialize in one or two categories, while Movie recommendation experts focus on distinct sets of movies.One Auto-categorization expert handles celebrity queries; examples of Movie recommendation specializations include classic adventures and films with complex stories.Source: E. Qualitative analysis of the… · p. 14
  • For Larger Animals, MoP performs similarly to APE-Random, with negligible differences between expert specializations because selecting the largest animal needs no specialized training data.Source: E. Qualitative analysis of the… · pp. 14–15

G. Template used in our experiments

H. Tasks

The appendix describes the tasks and scoring metrics across Instruction Induction, Super Natural Instructions, and BIG-Bench-Hard, then outlines APE and the evaluation scope for these benchmarks.

H. Tasks

  • The three benchmarks span coding, mathematics, commonsense reasoning, and knowledge retrieval, with task summaries and example demos supplied in the task descriptions.Source: H. Tasks · pp. 16–17, Table 6 · p. 17

I. Score Functions

  • Instruction Induction uses execution accuracy, Super Natural Instructions uses ROUGE-L, and BIG-Bench-Hard uses execution accuracy.Instruction Induction execution accuracy is 1 for an exact match and 0 otherwise, with a modified proportion-correct variant for some tasks.Source: §I · p. 17

J.2. Results on Super Natural Instructions

  • Super Natural Instructions experiments focus on code and mathematics, including 20 tasks where APE’s ROUGE-L score was below 50%.Source: §J.2 · p. 19

J.3. Results on BIG-Bench-Hard benchmark

  • The BIG-Bench-Hard experiments use tasks considered challenging among the BIG-Bench Instruction Induction tasks proposed by Zhou et al. (2022).Source: §J.3 · p. 19

K.1. APE

  • The appendix identifies APE, or Automatic Prompt Engineering, as closely relevant to the paper’s work.Source: §K.1 · p. 19

K.1.1. THE BACKGROUND BEHIND AUTOMATIC PROMPT OPTIMIZATION

  • Automatic prompt optimization uses LLMs to design prompts from task demo datasets, addressing the laborious trial and error involved in crafting prompts.Source: §K.1.1 · pp. 19–20

J.1. Results on Instruction Induction

  • Instruction Induction results report execution-accuracy gains over the Section 5.1 baseline, excluding Ascii and Cs algorithms because their datasets are unavailable.Source: §J.1 · p. 17, Table 9 · p. 20

K.1.2. DETAILED EXPLANATION OF THE APE ALGORITHM

APE generates candidate instructions from sampled demonstrations, scores them on validation data, and uses the best single demo-free instruction at test time. The appendix also describes InstructZero’s soft-prompt optimization loop.

K.1.2. DETAILED EXPLANATION OF THE APE ALGORITHM

  • APE samples training demos to generate candidate instructions, evaluates them on validation data, and selects the highest-scoring single demo-free instruction for testing.The paper states that MoP and other methods use the same training, validation, and test datasets.Source: §K.1.2 · pp. 20–21
  • APE’s listed Super Natural Instructions scores include 97.18 ± 0.35 for Conala list intersection and 46.11 ± 18.29 for Mathdataset classification.The table reports APE performance on code- and mathematics-related tasks, with means and standard deviations from three experiments.Source: Table 10 · p. 21, §K.1.2 · p. 21

K.2. InstructZero

  • InstructZero optimizes a soft prompt through Bayesian optimization, converting it to an instruction with an open-source LLM before querying a black-box LLM.Source: §K.2 · p. 21
  • The appendix’s Super Natural Instructions and BIG-Bench-Hard tables report MoP’s ROUGE-L and execution-accuracy gains, respectively, over the Section 5.1 baseline.Both captions note that gaps below 1% can be considered ties; the demo counts are Ntrain/10 for Super Natural Instructions and Ntrain/5 for BIG-Bench-Hard.Source: Table 11 · p. 22, Table 12 · p. 22

L. Implementation Details

The implementation allocates a total of 20 candidate instructions to each method and matches demo counts for combined baselines. The limitations include potentially sub-optimal cluster trimming and weaknesses in instruction generation and demo-assignment theory.

L. Implementation Details

  • APE and InstructZero each search 20 candidate instructions, while MoP’s experts share a total of 20; combined baselines use MoP’s demo count.The α hyperparameter in Equation (10) is 0.02 across experiments.Source: L. Implementation Details · p. 22

M. Limitations

  • K-means-Auto clusters may be unbalanced, and randomly discarding excess demos can ignore their relative importance and be sub-optimal.The authors also note that APE can fail to generate sensible instructions and that the kernel-regression account does not explain demo-order sensitivity.Source: M. Limitations · p. 23
Loading 2407.00256v1…