# CAPO: Cost-Aware Prompt Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 76 references that are in the map.
- First posted on arXiv 22 Apr 2025.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity](https://mlsanity.com/paper/2104.08786/) (2021)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [How Can We Know What Language Models Know?](https://mlsanity.com/paper/1911.12543/) (2019)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [A Prompt Pattern Catalog to Enhance Prompt Engineering with ChatGPT](https://mlsanity.com/paper/2302.11382/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [Learning How to Ask: Querying LMs with Mixtures of Soft Prompts](https://mlsanity.com/paper/2104.06599/) (2021)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [The Prompt Report: A Systematic Survey of Prompt Engineering Techniques](https://mlsanity.com/paper/2406.06608/) (2024)
- [ParamILS: An Automatic Algorithm Configuration Framework](https://mlsanity.com/paper/1401.3492/) (2014)
- [An Information-theoretic Approach to Prompt Engineering Without Ground Truth Labels](https://mlsanity.com/paper/2203.11364/) (2022)
- [InstructZero: Efficient Instruction Optimization for Black-Box Large Language Models](https://mlsanity.com/paper/2306.03082/) (2023)
- [Toward Human Readable Prompt Tuning: Kubrick's The Shining is a good movie, and a good prompt too?](https://mlsanity.com/paper/2212.10539/) (2022)
- [TELeR: A General Taxonomy of LLM Prompts for Benchmarking Complex Tasks](https://mlsanity.com/paper/2305.11430/) (2023)
- [When Choosing Plausible Alternatives, Clever Hans can be Clever](https://mlsanity.com/paper/1911.00225/) (2019)

## Built on by (most cited first, 7 of 7)

- [From Static Templates to Dynamic Runtime Graphs: A Survey of Workflow Optimization for LLM Agents](https://mlsanity.com/paper/2603.22386/) (2026)
- [TextReg: Mitigating Prompt Distributional Overfitting via Regularized Text-Space Optimization](https://mlsanity.com/paper/2605.21318/) (2026)
- [Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits](https://mlsanity.com/paper/2605.14553/) (2026)
- [CANTANTE: Optimizing Agentic Systems via Contrastive Credit Attribution](https://mlsanity.com/paper/2605.13295/) (2026)
- [How to Ask the AI: A User Perspective Survey for Large Language Model Prompting](https://mlsanity.com/paper/2608.07494/) (2026)
- [CROP: Token-Efficient Reasoning in Large Language Models via Regularized Prompt Optimization](https://mlsanity.com/paper/2604.14214/) (2026)
- [How Should a Prompt Optimizer Spend a Tight Budget? BudgetAPO with Noise-Adaptive Evaluation](https://mlsanity.com/paper/2610.05671/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have revolutionized natural language processing by solving a wide range of tasks simply guided by a prompt. Yet their performance is highly sensitive to prompt formulation. While automatic prompt optimization addresses this challenge by finding optimal prompts, current methods require a substantial number of LLM calls and input tokens, making prompt optimization expensive. We introduce CAPO (Cost-Aware Prompt Optimization), an algorithm that enhances prompt optimization efficiency by integrating AutoML techniques. CAPO is an evolutionary approach with LLMs as operators, incorporating racing to save evaluations and multi-objective optimization to balance performance with prompt length. It jointly optimizes instructions and few-shot examples while leveraging task descriptions for improved robustness. Our extensive experiments across diverse datasets and LLMs demonstrate that CAPO outperforms state-of-the-art discrete prompt optimization methods in 11/15 cases with improvements up to 21%p in accuracy. Our algorithm achieves better performances already with smaller budgets, saves evaluations through racing, and decreases average prompt length via a length penalty, making it both cost-efficient and cost-aware. Even without few-shot examples, CAPO outperforms its competitors and generally remains robust to initial prompts. CAPO represents an important step toward making prompt optimization more powerful and accessible by improving cost-efficiency.