PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs

Krista Opsahl-Ong, Michael J Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, Omar Khattab

arXiv:2406.11695v2cs.CLcs.AIcs.LG

TL;DR

Prompt optimization for multi-stage LM programs must improve prompts jointly without module-level labels, gradients, or internal model access. The paper factorizes optimization over instructions and demonstrations, uses task-grounded proposal and credit-assignment strategies, and develops MIPRO. MIPRO is most effective in five of seven benchmark settings, with reported gains of up to 13% accuracy.

  • Problem

    Prompt optimizers generally do not directly support multi-stage LM programs when module-level labels or evaluation metrics are unavailable.

  • Method

    The paper optimizes free-form instructions and few-shot demonstrations across modules using grounded proposal strategies, surrogate or history-based credit assignment, and MIPRO.

  • Results

    MIPRO is the most effective approach in five of seven settings and outperforms baseline optimizers by as much as 13% accuracy improvement.

  • Takeaways & Limitations

    Optimizing demonstrations is generally powerful, while instructions are especially important for complex conditional rules; jointly optimizing both usually performs best.

  • Takeaways & Limitations

    The optimizers have restricted ability to infer rules for complex tasks without a handwritten seed prompt, and the study fixes the proposer and task LMs.

Abstract

from arXiv · show

Language Model Programs, i.e. sophisticated pipelines of modular language model (LM) calls, are increasingly advancing NLP tasks, but they require crafting prompts that are jointly effective for all modules. We study prompt optimization for LM programs, i.e. how to update these prompts to maximize a downstream metric without access to module-level labels or gradients. To make this tractable, we factorize our problem into optimizing the free-form instructions and few-shot demonstrations of every module and introduce several strategies to craft task-grounded instructions and navigate credit assignment across modules. Our strategies include (i) program- and data-aware techniques for proposing effective instructions, (ii) a stochastic mini-batch evaluation function for learning a surrogate model of our objective, and (iii) a meta-optimization procedure in which we refine how LMs construct proposals over time. Using these insights we develop MIPRO, a novel algorithm for optimizing LM programs. MIPRO outperforms baseline optimizers on five of seven diverse multi-stage LM programs using a best-in-class open-source model (Llama-3-8B), by as high as 13% accuracy. We have released our new optimizers and benchmark in DSPy at http://dspy.ai

1 Introduction

LM programs advance NLP by composing modular calls, but their prompts are difficult to optimize jointly across multiple stages without intermediate labels or gradients. The paper formulates this challenge and introduces MIPRO, which jointly optimizes instructions and demonstrations.

  • Multi-stage LM programs combine prompting techniques into pipelines to solve complex NLP tasks.
  • Existing prompt optimizers largely search over strings and do not directly handle multi-stage programs lacking module-level labels or metrics.
  • The proposed setting assumes access only to the LM program, an optimization metric, and training inputs, with final outputs available when required by the metric.
  • Prompt optimization faces proposal and credit-assignment challenges as the number of modules and jointly tuned variables grows.
  • Optimizing demonstrations is often essential, instructions matter more for conditional rules, and jointly optimizing both generally performs best.
  • MIPRO outperforms baseline optimizers on five of seven benchmark tasks, with up to 13% accuracy improvement.

2 Problem Statement

The paper formalizes LM-program prompt optimization as selecting string assignments for prompt variables to maximize program-level performance. This problem is difficult because supervision is task-level, model internals are inaccessible, and evaluation resources are limited.

  • Algorithm 1 iteratively initializes an optimizer, proposes variable assignments, evaluates the updated program on data, updates its state, and extracts the best assignment.
  • An LM program contains m modules, each with a prompt template whose variables can include instructions, demonstrations, and target inputs.
  • The optimization goal is to assign strings to all prompt variables so the resulting program maximizes metric µ on training data.
  • The problem is intractable because prompts range over arbitrary strings, supervision is available only for the complete task, and gradients or embeddings are unavailable.
  • The work focuses on optimizing free-form instructions and K demonstration variables while holding other program variables constant.
  • The general optimizer framework is parameterized by an optimizer and an unoptimized program, with internal state guiding proposals and updates.

3 Designing LM Program Optimizers

The optimizer design addresses two bottlenecks: generating task-suitable candidate prompts and assigning credit across configurations of module-level changes. It combines proposer-LM strategies with greedy, surrogate, and history-based credit assignment.

  • Efficient optimization requires minimizing program evaluations and proposal sampling while addressing prompt proposal and credit assignment.
  • A proposer LM can bootstrap demonstrations, summarize dataset and program information, and support task-aware candidate prompt generation.
  • Grounding: Grounding gives the proposal LM context about dataset patterns, program control flow, and successful demonstrations to craft better instructions.
  • Learning To Propose: Proposal strategies expose hyperparameters such as generation temperature and whether to use data or program summaries, whose value may depend on the task and model.
  • Credit Assignment: Credit assignment is approached with greedy, surrogate, and history-based methods for estimating the contribution of module-level choices.
  • Greedy: Greedy assignment limits error misattribution but is inefficient and can miss changes whose benefits appear only after other stages improve.

4 Optimizers

The section presents optimizers for multi-stage LM programs that search over demonstrations and instructions while addressing prompt proposal and cross-module credit assignment. MIPRO combines grounded instruction proposals with Bayesian optimization over instruction–demonstration configurations.

  • 4.1 Bootstrap Random Search: Bootstrap Random Search first keeps high-scoring execution traces as demonstrations, then randomly searches their combinations and returns the best-performing set.Traces are retained when the program metric reaches a specified quality threshold.
  • 4.2 Module-Level OPRO: Module-Level OPRO uses histories of module instructions and program scores to propose new instructions, evaluates the joint program, and repeats for I iterations.The same program score is recorded in each module’s instruction history as a proxy for instruction quality.
  • 4.3 MIPRO: MIPRO bootstraps demonstrations, proposes grounded instructions, and applies Bayesian optimization to select the best combination of instruction and demonstration candidates.Its surrogate model explicitly learns the sensitivity of task-level scores to module-level parameters, separating credit assignment from proposal.
  • 4.3 MIPRO: MIPRO’s joint optimization generally performs best, while instruction optimization is more important for conditional-rule tasks and demonstration optimization is often essential for large gains.The restricted variants optimize instructions only or demonstrations only for cost, context-window, or task-specific reasons.
  • 4.5 Other OPRO variants: MIPRO++ meta-optimizes hyperparameters governing grounded instruction proposals, including summaries, proposer temperature, prompt-engineering tips, and selected demonstrations.Its Bayesian surrogate targets proposal hyperparameters rather than the LM program parameters themselves.
  • 4.5 Other OPRO variants: Program-Level OPRO relies on long full-trajectory histories and LM-assigned cross-stage credit, but the experiments use Module-Level OPRO because the more complex variant added no apparent performance gains.The authors identify strong assumptions and possible information loss as histories grow.

5 Experimental Setup

The benchmark evaluates LM program optimizers across seven diverse tasks, including multi-stage retrieval, question answering, classification, and entailment. Experiments compare instruction-only, few-shot-only, and joint optimization under fixed training, development, and test splits.

  • 5 Experimental Setup: The benchmark contains seven programs, using 500 training examples, 500 development examples, and a 2k-example test set when available.The test set uses the full available set when it contains fewer than 2k examples.
  • 5.1 Benchmark: Four programs are multi-stage and two are single-stage, with HotPotQA using repeated query generation followed by final answer generation.HotPotQA fullwiki requires retrieving two relevant Wikipedia articles for factoid questions.
  • 5.1 Benchmark: HotPotQA Conditional varies the accepted answer format by answer type to test whether instruction optimization handles subtle conditional rules.The task changes formatting requirements for people, dates, places, and other answer categories.
  • 5.1 Benchmark: The benchmark includes Iris and Heart Disease classification, testing prompt misspecification, Chain-of-Thought behavior, and multi-opinion clinical judgment.Iris uses six real-valued features, while Heart Disease uses 13 categorical and continuous features.
  • 5.1 Benchmark: ScoNe tests entailment reasoning over logical puzzles with nested negation, while HoVer tests three-hop retrieval over unchecked claims.HoVer alternates query generation, Wikipedia retrieval, and using retrieved results to inform subsequent steps.
  • 5.2 Experimental Setup: Experiments compare instruction-only, few-shot-only, and joint instruction–few-shot optimization across budgets of 20–50 trials and five runs per method-task pair.The main task model is Llama-3-8B, while GPT-3.5 commonly proposes instructions and teacher models bootstrap demonstrations.

6 Results & Discussion

The results identify when demonstrations, instructions, grounding, and joint optimization help across tasks, while showing that optimizer performance depends on task and budget.

  • Lesson 1: Optimizing bootstrapped demonstrations is key to achieving the best performance, generally outperforming instruction-only optimization except on HotPotQA Conditional.A Wilcoxon signed-rank test found Bootstrap Random Search beat the best instruction-only optimizer in all but one case.
  • Lesson 2: Jointly optimizing instructions and few-shot examples with MIPRO generally yields the best overall performance, with exceptions on HotPotQA, Heart Disease, and Iris without a typo.The comparison uses statistical tests against the second-highest averaging optimizer for each task.
  • Lesson 3: Instruction optimization is most important for conditional rules that are not obvious to the LM and cannot be expressed through a few examples.On HotPotQA Conditional, even 0-shot instruction optimization outperformed demonstration-only optimization; on Iris-Typo, it corrected seed-prompt mistakes.
  • Lesson 4: Grounding helps instruction proposal overall, but the best proposal strategy varies by task.Grounding was essential for HotPotQA and HoVer, while it hurt ScoNe; 0-Shot MIPRO++ recovered ScoNe performance by learning a task-specific strategy.
  • Lesson 4: The choice of bootstrapped demonstrations and the tip received the highest cross-task learned importance scores, while other proposal components varied in importance by task.The dataset summary was highly important for ScoNe but among the least important parameters for HotPotQA and HoVer.
  • Lesson 5: Optimizer comparisons are mixed, and different optimization budgets may produce more differentiated results.0-shot MIPRO++ outperformed 0-shot MIPRO for ScoNe and HotPotQA but was about equivalent for HoVer; the study leaves budget-dependent behavior for future work.

7 Related Work

Prior work optimizes prompts through several search and learning strategies, but existing approaches have limited applicability to multi-stage LM programs. Related systems differ in the assumptions and program structures they support.

  • Prompt optimization: Prompt optimization has used gradient-guided search, brute-force reranking, evolutionary algorithms, other LMs, and reinforcement learning.Prior reinforcement-learning work includes word-level edits affecting only a few words.
  • LM program optimization: DSPy expresses LM programs and optimizes prompts and weights, but the cited work explores only optimizers based on bootstrapping strong demonstrations.Sordoni et al. study joint optimization for stacked LLM calls using variational inference across two simple layers.
  • LM program optimization: Sordoni et al.'s approach relies on access to log probabilities for explicitly passed tokens to LMs.

8 Conclusion

The paper formalizes prompt optimization for LM programs, addresses proposal and credit-assignment challenges, and evaluates optimizer algorithms on a diverse benchmark. Its findings favor demonstrations broadly, instructions for complex conditional specifications, and joint MIPRO optimization in most settings.

  • Conclusion: The paper identifies two challenges: proposing a small set of high-quality prompts and assigning credit during optimization.
  • Conclusion: It addresses these challenges with three proposal-generation strategies and three credit-assignment strategies, evaluated on a benchmark of diverse tasks.
  • Conclusion: Optimizing few-shot demonstrations is powerful, while instruction optimization can be essential for complex task specifications with multiple conditional rules.
  • Conclusion: Jointly optimizing instructions and demonstrations with MIPRO is the most effective approach in five out of seven settings.

Limitations

The study's conclusions are bounded by fixed optimization and model settings and by limited ability to infer complex task rules without handwritten seed prompts.

  • Scope boundaries: The study does not examine how optimizer dynamics differ under extremely low or high budgets.Different budgets could reveal trade-offs between learning proposal improvements and efficiently optimizing existing proposals.
  • Scope boundaries: The experiments use a fixed proposer LM and task LM, leaving consistency across different models for future research.
  • Scope boundaries: The introduced optimizers have restricted ability to infer complex task rules without a handwritten seed prompt.Grounding may provide dataset details or examples but may be insufficient to extrapolate a comprehensive set of rules.

A Detailed Task Descriptions

The benchmark spans single-stage classification and reasoning tasks alongside multi-hop retrieval and question answering programs. HotPotQA Conditional adds answer-type formatting rules to test instruction optimization under conditional requirements.

  • HotPotQA requires three stages: generating a search query, reading retrieved passages for a second query, and answering from all retrieved passages.
  • HotPotQA Conditional: HotPotQA Conditional applies lowercase formatting for people, no punctuation for places, a “Peace!” suffix for dates, and all caps for other categories.Answer types are annotated as person, place, or date, and evaluation combines exact match with regex parsing.
  • Iris: Iris classifies flowers into three species from sepal and petal measurements, testing whether optimizers can teach simple rules not provided to the LM.
  • Heart Disease: Heart Disease predicts a binary outcome from 13 patient features, using three clinical opinions followed by a final judgment.
  • ScoNe evaluates binary entailment reasoning with negation, while HoVer fact-checks claims through many-hop Wikipedia search and evidence retrieval.The HoVer program alternates searches, summaries, and query generation across multiple hops.

B.1 Data Splits

Experiments separate training, development, and test data, use task-dependent optimization budgets, and run primarily with Llama 3 8B and proposer models from the GPT family. Instruction candidates are generated from dataset and program context with varied proposal tips.

  • Data Splits: Training data trains optimizers, development data supports internal method iteration, and test data is reserved for final evaluation and reporting.HotPotQA Conditional has fewer examples because labels were hand-created; Iris and Heart Disease have no development split.
  • Hyperparameters: Candidate counts are chosen heuristically, generally using N < T/v, where T is the trial budget and v is the number of optimized variables.
  • Language Models: Most experiments use Llama 3 8B, while proposer models use GPT-3.5 or GPT-4 with temperature 0.7 and top_p=1.0.Llama inference is parallelized across eight A100 GPUs in many experiments; a single suitable GPU or cloud provider could replicate all results.
  • Instruction Proposal: The instruction proposal program receives dataset and program descriptions plus a tip, then outputs a proposed instruction.Tips encourage diversity through creativity, concision, description, high-stakes framing, or task-relevant personas.

C.3 Dataset Summary Generation Process

Dataset and program summaries provide grounded context for instruction proposals, while bootstrapped demonstrations and Bayesian surrogate modeling support optimization across LM-program variables. The summaries are generated iteratively from training-set observations and program code.

  • Dataset Summaries: Dataset summaries are built by asking a proposer LM for batchwise observations, stopping after five “COMPLETE” outputs, then condensing observations into two or three sentences.Observation prompts may consider topics, content, syntax, conciseness, and the dataset’s likely task.
  • Program Summaries: Program summaries are generated from DSPy code to describe the intended task and apparent control flow.
  • Hyperparameter Importance: Learned importances vary by task: dataset summaries, tips, demonstrations, and proposal temperature can each matter for proposal quality.The cited analyses identify dataset summaries, tips, and task demonstrations for ScoNe; demonstrations for HotPotQA; and demonstrations, tips, and temperature for HoVeR.
  • Surrogate Modeling: A Bayesian surrogate estimates which latent prompt variables are most impactful, enabling MIPRO to abstract credit assignment away from the LLM.

G Optimization Results

Optimization results and prompt progressions are reported across six benchmark tasks, with figures tracking training performance over trials. The analysis finds that proposers can overfit instructions to meta-prompt demonstrations, although such instructions may still appear in strong programs.

  • Optimization Results: Training performance over optimization trials is plotted for ScoNe, HotPotQA, HoVeR, HotPotQA Conditional, Iris, and Heart Disease.
  • Prompt Progressions: Prompt progressions are documented for 0-Shot MIPRO across ScoNe, HotPotQA, HoVeR, HotPotQA Conditional, Iris, and Heart Disease.
  • Failure Mode: Current proposers tend to overfit instructions to the few-shot examples in the meta-prompt.
  • Failure Mode: Some overfit instructions occur in the best-performing programs, possibly because they provide implicit few-shot guidance or because stronger credit assignment could remove them.The paper leaves this phenomenon for future investigation.
  • Figures: The reported optimization figures cover ScoNe, HotPotQA, HoVeR, HotPotQA Conditional, Iris-Typo, and Heart Disease.
Loading 2406.11695v2…