# Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs

arXiv: https://arxiv.org/abs/2406.11695 · HTML: https://mlsanity.com/paper/2406.11695/

## Key facts

- Cited by 291 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 52 references that are in the map.
- First posted on arXiv 17 Jun 2024.

## Builds on (most cited first, 26 of 26)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Making Pre-trained Language Models Better Few-shot Learners](https://mlsanity.com/paper/2012.15723/) (2020)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [DIN-SQL: Decomposed In-Context Learning of Text-to-SQL with Self-Correction](https://mlsanity.com/paper/2304.11015/) (2023)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery](https://mlsanity.com/paper/2302.03668/) (2023)
- [Demonstrate-Search-Predict: Composing retrieval and language models for knowledge-intensive NLP](https://mlsanity.com/paper/2212.14024/) (2022)
- [AI Chains: Transparent and Controllable Human-AI Interaction by Chaining Large Language Model Prompts](https://mlsanity.com/paper/2110.01691/) (2021)
- [HoVer: A Dataset for Many-Hop Fact Extraction And Claim Verification](https://mlsanity.com/paper/2011.03088/) (2020)
- [EvoPrompt: Connecting LLMs with Evolutionary Algorithms Yields Powerful Prompt Optimizers](https://mlsanity.com/paper/2309.08532/) (2023)
- [Autonomous Evaluation and Refinement of Digital Agents](https://mlsanity.com/paper/2404.06474/) (2024)
- [Language Model Cascades](https://mlsanity.com/paper/2207.10342/) (2022)
- [Code Generation with AlphaCodium: From Prompt Engineering to Flow Engineering](https://mlsanity.com/paper/2401.08500/) (2024)
- [Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval](https://mlsanity.com/paper/2101.00436/) (2021)
- [Joint Prompt Optimization of Stacked LLMs using Variational Inference](https://mlsanity.com/paper/2306.12509/) (2023)
- [ScoNe: Benchmarking Negation Reasoning in Language Models With Fine-Tuning and In-Context Learning](https://mlsanity.com/paper/2305.19426/) (2023)

## Built on by (most cited first, 30 of 291)

- [Agentic Context Engineering: Evolving Contexts for Self-Improving Language Models](https://mlsanity.com/paper/2510.04618/) (2025)
- [Agentic Harness Engineering: Observability-Driven Automatic Evolution of Coding-Agent Harnesses](https://mlsanity.com/paper/2604.25850/) (2026)
- [Multi-Agent Design: Optimizing Agents with Better Prompts and Topologies](https://mlsanity.com/paper/2502.02533/) (2025)
- [PAPILLON: Privacy Preservation from Internet-based and Local Language Model Ensembles](https://mlsanity.com/paper/2410.17127/) (2024)
- [Meta Context Engineering via Agentic Skill Evolution](https://mlsanity.com/paper/2601.21557/) (2026)
- [HarnessX: A Composable, Adaptive, and Evolvable Agent Harness Foundry](https://mlsanity.com/paper/2606.14249/) (2026)
- [EvoAgentX: An Automated Framework for Evolving Agentic Workflows](https://mlsanity.com/paper/2507.03616/) (2025)
- [Feedback Descent: Open-Ended Text Optimization via Pairwise Comparison](https://mlsanity.com/paper/2511.07919/) (2025)
- [Continual Harness: Online Adaptation for Self-Improving Foundation Agents](https://mlsanity.com/paper/2605.09998/) (2026)
- [Fine-Tuning and Prompt Optimization: Two Great Steps that Work Better Together](https://mlsanity.com/paper/2407.10930/) (2024)
- [LLM Agents Should Employ Security Principles](https://mlsanity.com/paper/2505.24019/) (2025)
- [SynthesizeMe! Inducing Persona-Guided Prompts for Personalized Reward Models in LLMs](https://mlsanity.com/paper/2506.05598/) (2025)
- [Optimas: Optimizing Compound AI Systems with Globally Aligned Local Rewards](https://mlsanity.com/paper/2507.03041/) (2025)
- [How to Train Your Advisor: Steering Black-Box LLMs with Advisor Models](https://mlsanity.com/paper/2510.02453/) (2025)
- [StructuredRAG: JSON Response Formatting with Large Language Models](https://mlsanity.com/paper/2408.11061/) (2024)
- [Searching for Privacy Risks in LLM Agents via Simulation](https://mlsanity.com/paper/2508.10880/) (2025)
- [From Few to Many: Self-Improving Many-Shot Reasoners Through Iterative Optimization and Generation](https://mlsanity.com/paper/2502.00330/) (2025)
- [Improved Representation Steering for Language Models](https://mlsanity.com/paper/2505.20809/) (2025)
- [SEW: Self-Evolving Agentic Workflows for Automated Code Generation](https://mlsanity.com/paper/2505.18646/) (2025)
- [Self-Generated In-Context Examples Improve LLM Agents for Sequential Decision-Making Tasks](https://mlsanity.com/paper/2505.00234/) (2025)
- [Co-Harness: Co-Evolving Harnesses and Model Weights for LLM Agents](https://mlsanity.com/paper/2607.22688/) (2026)
- [Grounding by Trying: LLMs with Reinforcement Learning-Enhanced Retrieval](https://mlsanity.com/paper/2410.23214/) (2024)
- [MAPRO: Recasting Multi-Agent Prompt Optimization as Maximum a Posteriori Inference](https://mlsanity.com/paper/2510.07475/) (2025)
- [Model Context Protocol (MCP) Tool Descriptions Are Smelly! Towards Improving AI Agent Efficiency with Augmented MCP Tool Descriptions](https://mlsanity.com/paper/2602.14878/) (2026)
- [Iteration of Thought: Leveraging Inner Dialogue for Autonomous Large Language Model Reasoning](https://mlsanity.com/paper/2409.12618/) (2024)
- [Adaptive Self-improvement LLM Agentic System for ML Library Development](https://mlsanity.com/paper/2502.02534/) (2025)
- [MemoHarness: Agent Harnesses That Learn from Experience](https://mlsanity.com/paper/2607.14159/) (2026)
- [Harness-R1: Learning to Edit Executable Runtime Harnesses from Agent Failure Trajectories](https://mlsanity.com/paper/2608.02276/) (2026)
- [CORRECT: COndensed eRror RECognition via knowledge Transfer in multi-agent systems](https://mlsanity.com/paper/2509.24088/) (2025)
- [AutoSaddler: Automatic Harness Optimization with Durable Updates from Agent Execution Traces](https://mlsanity.com/paper/2608.23041/) (2026)

## Abstract (arXiv)

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