Technical Summary: CRAFT (Cost-aware Refinement And Front-aware Tuning of Prompts)

1. Problem Formulation

The paper addresses the multi-objective optimization problem inherent in tuning natural-language prompts for Large Language Models (LLMs). While longer, structured prompts often yield higher task accuracy, they incur higher inference costs (token counts) on every model call. Conversely, aggressive compression reduces cost but risks degrading performance.

The authors argue that optimizing for a single objective (accuracy or cost) or collapsing them into a fixed weighted sum (scalarization) is suboptimal. Such approaches often fail to recover the full Pareto front—the set of prompts where no other prompt is both more accurate and shorter. The paper identifies a specific failure mode called scalarization collapse, where fixed-weight search strategies recover only a narrow region of the trade-off surface, missing high-accuracy/low-cost or low-accuracy/high-cost extremes depending on the chosen weight. Furthermore, the discrete nature of prompt space and the non-convex relationship between prompt text, accuracy, and cost make fixed scalar rewards insufficient.

The core challenge is that evaluating a candidate prompt's true accuracy requires expensive target-LLM validation calls. Since the optimizer operates under a fixed budget of these calls per round, it must decide which candidates to evaluate without knowing their true position on the Pareto front.

2. Methodology: The CRAFT Framework

CRAFT (Cost-aware Refinement And Front-aware Tuning) is a Pareto-front prompt optimizer that treats target-LLM validation calls as a scarce resource. It operates in iterative rounds, maintaining a population of prompts and reshaping it to approximate the accuracy-cost Pareto front.

2.1. Core Loop Components

Each round consists of three distinct steps:

1. Candidate Generation (Refiner and Condenser):

   • CRAFT employs two complementary generators with opposing biases to propose edits to the current population.
   • Refiner (Accuracy-oriented): Uses a structure-aware optimizer (defaulting to SCULPT) to parse prompts into hierarchical trees and apply edits (reordering, elaborating, clarifying) to maximize task accuracy.
   • Condenser (Cost-oriented): Uses a structure-aware compressor (named DISTILL) to edit the parsed prompt tree by deleting redundant nodes or merging sections, targeting lower token counts while preserving task-critical instructions.
   • This dual-generation strategy ensures the candidate pool explores both ends of the trade-off spectrum.

2. Pareto-Gap Acquisition (Validation Allocation):

   • Instead of scoring all candidates or using a scalar score, CRAFT allocates the per-round validation budget to candidates that are likely to improve the current front approximation.
   • It calculates an Upper Confidence Bound (UCB) score ($p^+ = \mu + \beta\sigma$) for each candidate based on partial validation history, balancing exploration (high uncertainty) and exploitation (high mean score).
   • These optimistic scores are paired with normalized costs to form an optimistic candidate front ($F^+_t$).
   • The Pareto gap ($g_i$) is computed as the Manhattan distance from a candidate to the nearest point on this optimistic front. Candidates with smaller gaps (those closest to or on the front) are prioritized for full validation. This ensures the budget is spent on candidates that can extend the known front.

3. NSGA-II Retention (Population Selection):

   • After validation, the selector retains a population of size $k$ for the next round.
   • It uses Non-dominated Sorting Genetic Algorithm II (NSGA-II) logic to partition candidates into non-dominated fronts ($F_1, F_2, \dots$).
   • To ensure diversity, if the boundary front must be partially selected to fill the population, a maximin spread rule is applied. This iteratively selects candidates that maximize the minimum Euclidean distance to already selected candidates in the normalized accuracy-cost space, ensuring the retained population covers the trade-off surface evenly rather than clustering in one region.

3. Key Contributions

1. Formalization: The paper formalizes cost-aware prompt optimization as a budgeted Pareto-front search over accuracy and prompt-token cost, explicitly modeling the constraint that target-LLM validation calls govern which trade-offs can be observed.
2. CRAFT Framework: It proposes a front-aware optimization loop that decouples candidate generation from validation allocation. Key innovations include:
   • Complementary accuracy-oriented and cost-oriented generators.
   • Pareto-gap acquisition to optimistically allocate the validation budget.
   • NSGA-II retention to maintain a diverse, spread-out population.
3. Empirical Evidence: The authors demonstrate that standard baselines (accuracy-only, cost-only, and weighted-sum scalarization) suffer from scalarization collapse, concentrating in narrow regions of the front. In contrast, CRAFT successfully retains feasible prompts across both high-accuracy and low-cost regions.

4. Experimental Results

The authors evaluated CRAFT on six English classification and reasoning benchmarks: BeaverTails, GoEmotions, and four BIG-Bench Hard tasks (DisambiguationQA, Causal Judgement, Formal Fallacies, Salient Translation).

• Performance: CRAFT achieved the highest composite rank across all metrics (front quality, score, and cost). While it did not win every individual metric (e.g., cost-oriented baselines sometimes achieved lower token counts), it was the only method to consistently cover both ends of the Pareto front.
• Baselines:
  • Single-axis baselines (SCULPT for accuracy, DISTILL/LLMLingua for cost) excelled in their specific domain but failed on the other.
  • Weighted-sum baselines (WPRO) collapsed to narrow regions determined by their fixed weights, failing to capture the full trade-off surface.
• Ablations: Removing either the refiner or the condenser degraded performance, confirming that both modules are necessary to provide the diversity required for front extension.
• Cross-LLM Transfer: CRAFT's gains were robust across different optimizer LLMs (GPT-5.5, GPT-5.4, DeepSeek, Kimi), indicating the framework is not tied to a specific optimizer model.
• Efficiency: The method reached performance plateaus around 8 optimization rounds, suggesting efficient use of the validation budget.

5. Significance and Claims

The paper claims that the accuracy-cost trade-off in prompt engineering should be treated as a post-search choice rather than a pre-search weight. By directly optimizing the Pareto front, CRAFT allows practitioners to select the optimal prompt for a specific deployment budget after the search is complete, rather than being forced to guess the correct weighting beforehand.

The authors position CRAFT as a solution to the "scalarization collapse" problem, offering a more reliable approach for scenarios where the optimal balance between accuracy and cost is unknown or varies across different deployment contexts.

6. Limitations

The paper acknowledges several limitations:

• Scope: Evaluation is restricted to English classification and short-answer reasoning. Generalization to open-ended generation (summarization, code, dialogue) or multilingual settings is untested.
• Model Families: Experiments primarily used OpenAI models (GPT-5 family) as targets. Evaluation on non-OpenAI targets (e.g., Claude, Gemini, Llama, Qwen) remains future work.
• Initial Prompts: The method assumes a minimally task-relevant initial prompt; behavior under weak or adversarial initial prompts is unexplored.
• Generators: The study used a specific set of generators (SCULPT, DISTILL, OPRO, EvoPrompt). While the framework is modular, the performance of alternative generator types (e.g., history-aware compressors) was not fully investigated.