Research map / Multi-agent systems and games / LLM agents

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

ICML 2026 · Multi-agent systems and games › LLM agents · approach: LLM multi-agent decision making · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MASPOB, a budgeted bandit-based prompt optimizer for fixed-topology multi-agent systems that combines a GAT surrogate, LinUCB uncertainty, and coordinate ascent, reporting gains over AFlow and MIPRO on six benchmarks with GPT-4o-mini.

Problem

Prompt optimization for LLM-based multi-agent systems with fixed workflow topology is hard because end-to-end evaluations are expensive, prompts are coupled through the topology, and the joint prompt space is combinatorial.

Approach

Model prompt combinations with a topology-aware GAT surrogate, use a LinUCB bonus in the learned embedding space for exploration, and maximize the UCB acquisition via coordinate ascent over single-agent prompt choices, reducing search cost from exponential to linear in the number of agents.

Key results

• MASPOB reaches 80.58% average across six benchmarks, versus 78.87 for MIPRO and 78.52 for AFlow with GPT-4o-mini under a 50-evaluation budget.
• Replacing the GNN with an MLP drops the average from 80.58 to 78.27 (-2.31 points).
• Coordinate ascent cuts runtime by 99.8% on HotpotQA (15.9 s vs 8801 s) at a cost of 0.29 points versus global search.

Surprising findings

• Using the MIPRO prompt domain instead of MASPOB's own domain gave a higher average (70.13 vs 69.67) on DROP and MATH, showing the optimizer's gains depend partly on the candidate set.
• The MLP-surrogate variant performs slightly worse than AFlow on average, indicating the GNN surrogate is responsible for most of the gain.

Limitations

• Assumes a static DAG for inter-agent information flow and does not model cross-agent cycles or dynamic conditional routing.
• Performance depends on the quality and diversity of the candidate prompt domain, which is generated by LLM paraphrasing.
• Evaluated mainly with GPT-4o-mini and a fixed 50-evaluation budget on small validation splits.

Experimental setup

Datasets: HotpotQA DROP HumanEval MBPP GSM8K MATH

Benchmarks: HotpotQA DROP HumanEval MBPP GSM8K MATH

Metrics: F1 Pass@1 solve rate accuracy

Baselines: IO CoT ReAct PromptBreeder Instinct AFlow MIPRO MAPRO

Builds on: LinUCB Graph Attention Network AFlow MIPRO NeuralUCB

Closest papers by meaning

• MASPO: Joint Prompt Optimization for LLM-based Multi-Agent Systems (ICML 2026 · similarity 0.91)
• AgentGrad: Intervention-guided Prompt Optimization for Multi Agent Systems (NeurIPS 2026 · similarity 0.90)
• Multi-Agent Design: Optimizing Agents with Better Prompts and Topologies (ICLR 2026 · similarity 0.89)
• GPTSwarm: Language Agents as Optimizable Graphs (ICML 2024 · similarity 0.88)
• MARS: Multi-Agent Adaptive Reasoning with Socratic Guidance for Automated Prompt Optimization (AAAI 2026 · similarity 0.88)
• Can Graph Learning Improve Planning in LLM-based Agents? (NeurIPS 2024 · similarity 0.87)