CRAFT: Cost-aware Refinement And Front-aware Tuning of Prompts

A new prompt optimization method called CRAFT treats large language model validation calls as a scarce resource, allocating them to candidates near the optimistic Pareto front of accuracy and prompt-token cost rather than collapsing objectives into a single weighted sum before search begins [1]. The approach, detailed in a paper submitted to arXiv on 3 June 2026, addresses a known problem in prompt engineering: prompts tuned for accuracy often grow long, raising inference cost on every model call [1]. The best accuracy-cost trade-off depends on the task and the budget, so prompt optimization becomes a search over the Pareto front of accuracy and prompt-token cost rather than a hunt for one prompt [1]. The usual shortcut, collapsing the objectives into a weighted sum, fixes the trade-off weight before search and often recovers only a narrow region of the front, a failure the authors call scalarization collapse [1]. CRAFT, which stands for Cost-aware Refinement And Front-aware Tuning, operates in rounds. Each round, complementary accuracy-oriented and cost-oriented generators propose edits, a Pareto-gap acquisition function spends the per-round validation budget, and NSGA-II retention keeps a spread-out population [1]. The algorithmic challenge is not merely choosing among evaluated trade-offs, but deciding what to evaluate: each candidate's accuracy requires target-LLM validation calls, so the optimizer must spend a per-round validation budget before the candidate's true front position is known [3]. Across six classification and reasoning benchmarks, CRAFT's retained fronts reached both high-accuracy and low-cost regions, while accuracy-only, cost-only, and weighted-sum baselines each concentrated in narrower regions [1]. The accuracy-cost trade-off becomes a post-search choice, not a pre-search weight [1]. The framework separates candidate generation from validation allocation, using complementary accuracy-oriented and cost-oriented generators, Pareto-gap acquisition, and NSGA-II retention as one budgeted loop [4]. The paper formalizes cost-aware prompt optimization as budgeted Pareto-front search over accuracy and prompt-token cost, where target-LLM validation calls govern which candidate trade-offs can be observed [5]. CRAFT maintains a small population of prompts and, round by round, reshapes it into an approximation of the accuracy-cost Pareto front [5]. Code for the method has been made available on GitHub [3].