Cost-Aware Adaptive Prompt Selection for Large Language Models Using UCB and Thompson Sampling

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.

Authors

Institutions

Publication Details

Journal
Applied and Computational Engineering
Published
2026-11-17
DOI
https://doi.org/10.54254/2755-2721/2026.39115
Primary Topic
Advanced Bandit Algorithms Research
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Cost-Aware Adaptive Prompt Selection for Large Language Models Using UCB and Thompson Sampling

Junbo Zhang
1 links
Applied and Computational Engineering
Advanced Bandit Algorithms Research
article

Cost-Aware Adaptive Prompt Selection for Large Language Models Using UCB and Thompson Sampling

Junbo Zhang
article en

Abstract

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.

Applied and Computational EngineeringVol. 282(1)
Capital University of Economics and Business (CN)
Advanced Bandit Algorithms Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon