MAPS: Multi-armed bandit-guided adaptive prompt strategy selection for large language models

Prompt strategy selection plays a critical role in maximizing the effectiveness of Large Language Models (LLMs), yet existing prompt engineering methods typically rely on fixed strategies or heuristic rules, limiting their adaptability across diverse mathematical reasoning tasks. Although recent approaches introduce diverse prompting strategies, they lack a principled mechanism for dynamically selecting the most suitable strategy according to task characteristics and historical feedback. To address this challenge, we propose MAPS, a Multi-Armed bandit-guided Adaptive Prompt Strategy selection framework for LLMs. MAPS formulates prompt strategy selection as a sequential decision-making problem and employs Thompson Sampling to dynamically choose among candidate strategies based on observed LLM feedback. By leveraging the exploration-exploitation trade-off, MAPS continuously discovers potentially effective strategies while exploiting strategies with strong empirical performance. Furthermore, we formulate prompt strategy optimization through cumulative regret minimization and establish a sublinear regret bound, providing theoretical guarantees for efficient long-term learning in black-box LLM environments. Extensive experiments on four arithmetic reasoning benchmarks, including AddSub, GSM, MultiArith, and SingleEq, across multiple LLM backbones demonstrate that MAPS consistently outperforms individual prompt strategies, achieving an average accuracy improvement of 2.5%–6.8%. Moreover, MAPS reduces performance variance by 6.3%, indicating improved robustness and cross-model generalization on mathematical reasoning tasks. The source code is available at: https://anonymous.4open.science/r/MAPS-code-334D/