Technical Summary: MO-CAPO: Multi-Objective Cost-Aware Prompt Optimization

1. Problem Statement

Large Language Models (LLMs) demonstrate strong performance across diverse tasks but remain highly sensitive to prompt design, necessitating automatic prompt optimization. While existing methods focus primarily on maximizing performance, they often ignore competing objectives such as inference cost and latency. Furthermore, the optimization process itself is expensive, requiring numerous LLM calls.

Current approaches face two main limitations:

1. Single-Objective Focus: Most optimizers (e.g., CAPO, GEPA) optimize for performance alone or use scalarization with a fixed, pre-chosen trade-off weight to penalize prompt length. This approach fails to capture the full spectrum of performance-cost trade-offs and requires users to manually tune weights, which is non-trivial.
2. Inefficient Multi-Objective Methods: Existing multi-objective prompt optimizers typically rely on off-the-shelf algorithms like NSGA-II. These methods often lack cost-efficiency in their optimization procedures, evaluating candidates on full datasets without mechanisms to discard unpromising solutions early. Additionally, they often use prompt length as a proxy for cost, ignoring the distinct computational profiles of input versus output tokens in modern LLMs (where output generation is significantly more expensive).

The core problem is to develop a prompt optimization algorithm that jointly optimizes performance and inference cost, discovers a diverse set of Pareto-optimal solutions (the Pareto front), and does so efficiently under a limited evaluation budget.

2. Methodology: MO-CAPO

The authors propose MO-CAPO (Multi-Objective Cost-Aware Prompt Optimization), an algorithm that extends the evolutionary strategy of CAPO to handle multiple objectives explicitly while integrating budget allocation mechanisms.

2.1 Cost Objective

MO-CAPO introduces a deployment-oriented cost objective that accounts for the full computational profile of LLM inference. Unlike previous methods that penalize only prompt length, MO-CAPO defines cost as a weighted sum of input and output tokens:
$$c_\Phi(p, x) = w_{in} \cdot tok_{in}(p; x) + w_{out} \cdot tok_{out}(p; x)$$
Where $w_{in}$ and $w_{out}$ are model-specific weights derived from API pricing or latency metrics. This formulation reflects the reality that output tokens are typically more expensive due to sequential autoregressive decoding.

2.2 Algorithmic Framework

MO-CAPO operates as a genetic algorithm with a population of prompts consisting of instructions and few-shot examples. It integrates concepts from NSGA-II and the multi-objective automatic algorithm configuration method MO-SMAC.

• Incumbent Set & Population: The algorithm maintains a population ($P_\mu$) and a dedicated incumbent set ($P_{inc}$) representing the current Pareto front approximation.
• Parent Selection: Unlike CAPO's random selection, MO-CAPO uses a binary tournament selection adapted for heterogeneous evaluation levels. It favors incumbents (solutions on the Pareto front) and uses crowding distance (CD) to maintain diversity. For non-incumbents with different evaluation levels, it applies a weaker dominance criterion to ensure fair comparison.
• Intensification (Budget Allocation): This is the core efficiency mechanism. Instead of evaluating every candidate on the full development set, challengers are evaluated progressively on data blocks.
  • A challenger is compared against the closest incumbent in objective space.
  • If the challenger is dominated by the incumbent on the subset of data evaluated so far, its evaluation is terminated early ("rejected"), saving budget.
  • If it survives, it is evaluated on more blocks until it either dominates an incumbent or completes evaluation on all shared blocks.
  • Surviving challengers are added to the population and potentially the incumbent set.
• Environmental Selection: To maintain population size, dominated candidates are removed. If candidates have heterogeneous evaluation levels, those with fewer evaluations are discarded first to prevent bias.

3. Key Contributions

The paper outlines four primary contributions:

1. MO-CAPO Algorithm: A novel multi-objective prompt optimization algorithm that discovers full Pareto front approximations balancing performance and inference cost while maintaining cost-efficiency through an intensification mechanism.
2. Realistic Cost Objective: A new objective function that weights input and output tokens separately, providing a realistic measure of deployment costs for modern LLMs, moving beyond simple prompt-length proxies.
3. Rigorous Evaluation Protocol: The first large-scale evaluation of multi-objective prompt optimization that considers generalization and robustness using:
   • Noisy R2 (nR2): Measures selection robustness by simulating user preference selection on the development set and evaluating on the test set.
   • Approximation Gap: Quantifies the difference between optimistic (non-dominated on test set) and pessimistic (non-dominated on development set) Pareto fronts.
   • Empirical Attainment Surfaces (EAS): Visualizes performance stability across multiple runs.
4. Comprehensive Benchmarking: A comparison against state-of-the-art single-objective optimizers (CAPO, GEPA, EvoPromptGA) and an NSGA-II-based baseline across three LLMs and four tasks, demonstrating superiority in multi-objective metrics and efficiency.

4. Experimental Results

The authors evaluated MO-CAPO on three LLMs (GPT-OSS-120B, Qwen3-30B, Mistral-3.2-24B) and four tasks (AG News, GSM8K, Subj, MBPP) with a token budget of 7.5 million.

• Multi-Objective Performance: MO-CAPO outperformed the NSGA-II-based baseline in 8 out of 12 model-dataset combinations regarding the noisy R2 metric. It consistently identified strong, robust, and diverse Pareto front approximations.
• Efficiency: MO-CAPO demonstrated significantly higher efficiency. It found competitive solution sets at much lower budgets (often requiring less than 1/3 of the budget to reach 80% of final performance) compared to NSGA-II-PO. The intensification mechanism allowed MO-CAPO to evaluate up to 5.7 times more candidates than the baseline.
• Diversity of Solutions: The discovered solution sets spanned diverse performance-cost trade-offs, including low-cost solutions omitted by single-objective optimizers and high-performance solutions. The prompts varied in instruction detail, number of few-shot examples, and input/output token ratios.
• Competitiveness with Single-Objective Methods: Despite optimizing for cost, the top-performance candidates found by MO-CAPO remained competitive with state-of-the-art single-objective optimizers. In terms of accuracy rankings, MO-CAPO was statistically indistinguishable from CAPO and GEPA in many settings and significantly outperformed EvoPrompt and initial instructions.
• Ablation Studies:
  • Intensification: Removing this mechanism (reverting to NSGA-II-PO) resulted in slower convergence and higher token consumption.
  • Cost Weights: The input token weight ($w_{in}$) was found to be the dominant driver for controlling prompt cost. Removing it led to a dramatic increase in input token usage and degraded optimization quality (nR2).

5. Significance and Claims

The paper claims that MO-CAPO enables practitioners to select from an efficiently discovered set of multiple prompts offering different trade-offs between performance and cost, rather than being forced into a single solution or a manually tuned scalarization.

Key claims regarding significance include:

• Efficiency: The integration of multi-objective budget allocation (intensification) into evolutionary prompt optimization allows for the discovery of robust Pareto fronts under tight computational budgets.
• Realism: By explicitly modeling input and output token costs, the method provides a more accurate representation of real-world deployment costs than length-based proxies.
• Robustness: The use of approximation gaps and noisy R2 metrics provides a more realistic assessment of solution quality, accounting for generalization errors and stochastic variability often masked by standard metrics like Hypervolume.
• Practical Utility: The method offers a diverse set of viable low-cost alternatives that are ignored by performance-only methods, addressing the practical reality that marginal accuracy gains often do not justify substantial increases in inference costs.

The authors position this work as the first thorough evaluation of multi-objective optimization for machine learning that extends preliminary methodologies to prompt optimization, emphasizing the need for robust, generalization-aware metrics in this domain.