MO-CAPO: Multi-Objective Cost-Aware Prompt Optimization 5 DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Computing methodologies Supervised learning by classification CCS: Computing methodologies Genetic algorithms CCS: Mathematics of computing Evolutionary algorithms CCS: Computing methodologies Heuristic function construction CCS: Computing methodologies Natural language generation

Jan Büssing, Moritz Schlager, Timo Heiß, Tom Zehle, Matthias Feurer · 2026

Read MO-CAPO: Multi-Objective Cost-Aware Prompt Optimization 5 DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Computing methodologies Supervised learning by classification CCS: Computing methodologies Genetic algorithms CCS: Mathematics of computing Evolutionary algorithms CCS: Computing methodologies Heuristic function construction CCS: Computing methodologies Natural language generation by Jan Büssing, Moritz Schlager, Timo Heiß, Tom Zehle, Matthias Feurer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18869.txt.

Introduction

Jan Büssing and four colleagues optimize prompts for performance and inference cost together, instead of chasing accuracy alone. Existing multi-objective methods lean on generic NSGA-II search and ignore efficiency. Their MO-CAPO algorithm adds budget allocation and a cost measure covering the full compute profile of inference. Across four tasks and three models it finds varied Pareto fronts of prompts trading accuracy against cost. It beats the NSGA-II baseline in eight of twelve noisy comparisons at far lower budgets.

Catalog record

CREATORJan Büssing, Moritz Schlager, Timo Heiß, Tom Zehle, Matthias Feurer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122655
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18869

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

MO-CAPO: Multi-Objective Cost-Aware Prompt Optimization 5 DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Computing methodologies Supervised learning by classification CCS: Computing methodologies Genetic algorithms CCS: Mathematics of computing Evolutionary algorithms CCS: Computing methodologies Heuristic function construction CCS: Computing methodologies Natural language generation Jan Büssing, Moritz Schlager, Timo Heiß, Tom Zehle, Matthias Feurer Abstract . Large language models (LLMs) achieve strong performance across a wide range of tasks but are highly sensitive to prompt design, motivating the need for automatic prompt optimization. Existing methods predominantly focus on performance alone, ignoring competing objectives such as inference cost or latency. At the same time, existing work on multi-objective prompt optimization relies on off-the-shelf NSGA-II, ignoring optimization efficiency. As a remedy, we introduce MO-CAPO , a novel multi-objective prompt optimization algorithm that jointly optimizes performance and inference cost while leveraging budget allocation for cost-efficient optimization. We further propose a deployment-oriented cost objective that captures the full computational profile of LLM inference. We evaluate our approach across four tasks and three LLMs and compare it to an NSGA-II-based multi-objective method and state-of-the-art single-objective prompt optimizers. Results show that MO-CAPO consistently identifies strong, robust, and diverse Pareto front approximations while maintaining cost-efficiency. It outperforms the NSGA-II baseline on 8 out of 12 cases in terms of the noisy R2 metric and achieves competitive performances often already at a considerably lower budget. The discovered solution sets span diverse performance-cost trade-offs that are omitted by single-objective optimizers, yet the top-performance candidates remain competitive with single-objective solutions. Additionally, we conduct the first evaluation of multi-objective machine learning experiments that considers generalization and robustness through noisy R2 and approximation gap, enabling a more realistic assessment of solution quality. MO-CAPO enables practitioners to select from an efficiently discovered set of multiple prompts offering different trade-offs between performance and cost. 1. Introduction Nowadays, large language models (LLMs) yield impressive results on a wide variety of tasks ( Radford et al. 2019 ; Ouyang et al. 2022 ; Touvron et al. 2023 ) . They can be adapted to solve new tasks simply through a prompt as input, consisting of a textual instruction and optionally few-shot examples ( Brown et al. 2020 ; Liu et al. 2023 ) . However, the performance of an LLM on a given task is highly sensitive to the quality and formulation of this prompt, as well as the selection and order of few-shot examples ( Zhao et al. 2021 ; Lu et al. 2022 ; Zhou et al. 2023 ) . Optimizing prompts can therefore substantially improve performance ( Zehle et al. 2025b ) . Because manual prompt engineering is tedious and unreliable ( Jiang et al. 2020 ; Liu et al. 2023 ) , the field of automatic prompt optimization has emerged ( Cui et al. 2025 ; Li et al. 2025 ) . Most existing prompt optimization algorithms focus solely on optimizing performance. In practice, however, there are often several competing objectives for which we want to optimize prompts, such as cost or latency, in addition to performance ( Murthy et al. 2025 ) . At the same time, the optimization process itself can be costly, as evaluating prompts requires numerous LLM calls ( Agarwal et al. 2024 ) . CAPO ( Zehle et al. 2025b ) recognizes both challenges, but primarily addresses the cost-efficiency of the optimization process through a racing mechanism, and considers the cost of a prompt only by penalizing its length. This penalty is controlled by an a priori -chosen weight, and choosing an appropriate weight is a non-trivial task for users. Existing multi-objective prompt optimizers mostly rely on off-the-shelf NSGA-II to discover trade-offs between multiple objectives, such as performance and prompt length, and are not cost-efficient in their optimization procedures ( Yang and Li 2023 ; Câmara et al. 2025 ; do Val Lopes and Machado 2025 ) . In addition, costs are not only produced by prompt length. With the rise of thinking models that leverage internal reasoning ( Guo et al. 2025 ; Jaech et al. 2024 ) and prompting techniques such as chain-of-thought ( Wei et al. 2022 ) , output tokens have become a considerable driver of cost and latency. Figure 1 . Prompts for Mistral-3.2-24B on Subj: CAPO is limited to a single solution, whereas MO-CAPO discovers a Pareto front. The x-axis denotes the average cost in US dollars per 1M calls with a prompt, the y-axis its test set accuracy. From an optimization perspective, prompt optimization can naturally be viewed as an expensive black-box optimization problem ( Zhou et al. 2023 ; Cheng et al. 2024 ) . The objective function (LLM performance under a given prompt) can only be evaluated through costly LLM calls, while its internal structure remains unknown. This setting closely resembles established black-box optimization problems such as automatic algorithm configuration ( Hutter et al. 2009 , AAC;) and hyperparameter optimization (HPO) in machine learning ( Feurer and Hutter 2019 ) , where function evaluations are likewise expensive. Moreover, these problems are frequently multi-objective, e.g., trading off runtime vs. solution quality in AAC ( Blot et al. 2016 ) , or performance vs. interpretability in HPO ( Karl et al. 2023 ) . These fields have developed dedicated budget allocation strategies specifically for multi-objective optimization ( Blot et al. 2016 ; Rook et al. 2025 ) . In this work, we propose a new multi-objective prompt optimization method that builds on the evolutionary strategy of CAPO ( Zehle et al. 2025b ) , extends it to explicitly handle multiple objectives, and integrates an intensification mechanism for budget allocation inspired by the multi-objective AAC method MO-SMAC ( Rook et al. 2025 ) . Our main contributions are as follows: (1) We introduce MO-CAPO , an a posteriori multi-objective prompt optimization algorithm that enables the discovery of full Pareto front approximations of prompts that balance performance and inference cost (see Fig. 1 ) while keeping optimization itself cost-efficient. (2) We propose a new objective function that accounts for the full computational profile of LLM inference by weighting input and output tokens, providing a realistic measure of deployment costs for modern LLMs. (3) We are the first study to conduct a large multi-objective generalization evaluation by studying optimistic and pessimistic HV, approximation gap ( Feurer et al. 2023 ) , and the noisy R2 metric ( Branke 2025 ) . (4) We compare our method against SOTA single-objective prompt optimizers and an NSGA-II-based baseline across multiple LLMs and tasks, demonstrating superiority in multi-objective metrics, efficiency, solution set diversity, and competitive top performances. We verify the effect of the algorithmic components and new cost objective in dedicated ablation studies. 1 1 1 Code and experimental results are provided as supplementary material. 2. Notation and Problem Statement Let p=(i,\boldsymbol{e}) be a prompt consisting of an instruction i from the instruction space \mathcal{I} and an ordered tuple of k few-shot examples \boldsymbol{e}=(e_{1},\dots,e_{k}) from the example space \mathcal{E}^{k} . The complete search space \mathcal{P}=\mathcal{I}\times\bigcup_{k=0}^{k_{\max}}\mathcal{E}^{k} includes prompts from zero to k_{\max} shots. In automatic prompt optimization, this search space (or subspace when only instructions are tuned) is systematically explored using automatic optimization

Read the complete text