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/

Authors

Institutions

Publication Details

Journal
Intelligent Data Analysis
Published
2026-11-12
DOI
https://doi.org/10.1177/1088467x261505175
Primary Topic
Advanced Bandit Algorithms Research
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

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

Yongquan Wan, Jiaxin Nan, Cairong Yan, Zijian Wang
Intelligent Data Analysis
Advanced Bandit Algorithms Research
article

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

Yongquan Wan, Jiaxin Nan, Cairong Yan, Zijian Wang
article en

Abstract

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/

Intelligent Data Analysis
Donghua University (CN), Shanghai Zhongqiao Vocational and Technical University (CN)
National Natural Science Foundation of China
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