This paper investigates cost-aware adaptive prompt selection for large language models by modeling four prompt strategies as arms in a multi-armed bandit. Standard UCB and Thompson Sampling are compared with contextual extensions, LinUCB and Linear Thompson Sampling (LinTS), on GSM8K. The study evaluates accuracy, cumulative reward, cumulative regret, average token usage, tokens per correct answer, and budget satisfaction. On the held-out evaluation set, the Global Best prompt achieved 96.8% accuracy with a cumulative regret of 3.00, while the Oracle upper bound reached 97.4%. LinUCB achieved 95.47% accuracy with an average of 200.18 tokens per question, reducing token use by approximately 9.9% relative to the Global Best prompt (222.14 tokens). Under the medium normalized token budget B = 0.2893, cost-constrained LinUCB maintained 95.47%-95.49% accuracy and 93% budget satisfaction, compared with 30%-35% for LinTS. In addition, 92% of evaluation questions produced identical binary rewards across all four prompts, indicating limited prompt-specific heterogeneity. The results suggest that contextual prompt selection may provide greater value for resource control than for accuracy improvement in homogeneous, high-accuracy reasoning settings.
Research Article
Open Access