[2603.02630] MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks

Computer Science > Machine Learning arXiv:2603.02630 (cs) [Submitted on 3 Mar 2026] Title:MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks Authors:Zhi Hong, Qian Zhang, Jiahang Sun, Zhiwei Shang, Mingze Kong, Xiangyi Wang, Yao Shu, Zhongxiang Dai View a PDF of the paper titled MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks, by Zhi Hong and 7 other authors View PDF HTML (experimental) Abstract:Large Language Models (LLMs) have achieved great success in many real-world applications, especially the one serving as the cognitive backbone of Multi-Agent Systems (MAS) to orchestrate complex workflows in practice. Since many deployment scenarios preclude MAS workflow modifications and its performance is highly sensitive to the input prompts, prompt optimization emerges as a more natural approach to improve its performance. However, real-world prompt optimization for MAS is impeded by three key challenges: (1) the need of sample efficiency due to prohibitive evaluation costs, (2) topology-induced coupling among prompts, and (3) the combinatorial explosion of the search space. To address these challenges, we introduce MASPOB (Multi-Agent System Prompt Optimization via Bandits), a novel sample-efficient framework based on bandits. By leveraging Upper Confidence Bound (UCB) to quantify uncertainty, the bandit framework balances exploration and exploitation, maximizing gains within a strictly limite...