Cost-Aware Preference-Based Bayesian Optimization for Structured Prompt Configuration of Large Language Models

Prompt configuration strongly affects the accuracy, reliability, and cost of large language models (LLMs), but jointly tuning instructions, output contracts, demonstrations, reasoning cues, and decoding settings creates a large mixed discrete black-box optimization problem. We propose MNL-PCO, a cost-aware, preference-based Bayesian optimization framework that uses a ridge-regularized multinomial-logit (MNL) discrete-choice surrogate over structured prompt components. The surrogate is learned from pairwise preferences induced by observed configuration scores and provides directly interpretable component utilities without requiring learned prompt embeddings or kernel design. Evaluations are performed at three validation-subset fidelities (15%, 40%, and 100%); expected improvement is weighted by a fidelity-information factor, normalized by a pre-evaluation token-cost proxy, and combined with periodic full-fidelity promotion. We evaluate MNL-PCO in two stages. A controlled study covers four simulation regimes, 30 paired seeds per regime, a 23,328-configuration space, and 11 methods/ablations. MNL-PCO obtains the highest mean selected-prompt accuracy among the principal methods in all four regimes (0.907-0.960), significantly outperforming Hyperband and random-search baselines after Holm correction. On 100 unseen simulated configurations, its mean held-out Spearman correlation is 0.807 versus 0.667 for direct-score ridge. We then evaluate two local open-weight models-Llama 3.2 1B and Qwen2.5 1.5B-on IMDb, SST-2, and AG News with five paired seeds per setting and actual token/runtime accounting. MNL-PCO has the best mean test accuracy in four of six model-task settings and the best average accuracy rank (1.83), but it does not dominate IMDb, and the direct-score ridge surrogate ranks unseen live configurations better. These results support MNL-PCO as a competitive, interpretable structured-search method while also identifying the limits of an additive MNL utility model on real LLM behavior.