MASPOB: 用 GNN 代理 + LinUCB + 坐标上升做多智能体提示优化¶

会议: ICML 2026
arXiv: 2603.02630
代码: https://github.com/HZ1008/MASPOB
领域: 多 Agent / 提示优化 / 贝叶斯优化
关键词: MAS, prompt optimization, GAT, LinUCB, 坐标上升, 黑盒优化

一句话总结¶

MASPOB 把多智能体系统的 prompt 优化看作预算紧缩的黑盒优化，用 GAT 代理模型捕获 workflow topology 下的 prompt 耦合、用 LinUCB 在嵌入空间算 epistemic uncertainty、用坐标上升把联合搜索拆成序贯单体问题，复杂度从 \(\mathcal{O}(\prod |\mathcal{P}_i|)\) 降到 \(\mathcal{O}(\sum |\mathcal{P}_i|)\)；在 6 个基准（QA/Code/Math）上平均 80.58 超越 MIPRO 78.87、AFlow 78.52、IO 68.56。

研究背景与动机¶

领域现状：LLM 多智能体系统（MAS）让多个专业 agent 协同完成复杂任务。MAS 性能不仅取决于 LLM 本身，也取决于 workflow topology 和 agent prompts。AFlow、GPTSwarm 等探索自动化 topology，但很多 workflow 经过专家验证和安全审查不能改，所以优化 prompt 是唯一可行的提升手段。

现有痛点：MAS 上的 prompt 优化是三重挑战的组合黑盒问题——(1) 评估昂贵：一次评测要跑完整 end-to-end MAS 含多次 LLM 调用；(2) topology-induced coupling：上游 agent 的 prompt 变了，下游 agent 的 input 分布也变，objective 不可分解；(3) combinatorial explosion：N 个 agent 的联合 prompt 空间是 Cartesian product。

核心矛盾：现有 prompt optimizer 要么 single-agent（OPRO/PromptBreeder/Instinct）独立优化忽略 topology，要么 multi-stage 但用 implicit dependency 建模（MIPRO 用 TPE）几乎 topology-agnostic。在 budget=50 评测、prompt 空间指数增长的现实下，sample-inefficient 且 miss 高质量 coordinated combinations。

本文目标：同时解决三重挑战——sample-efficient 探索、topology-aware 建模、scalable combinatorial 搜索。

切入角度：把 prompt 优化 reframe 为 contextual bandit：UCB 提供 explore/exploit 平衡；GNN 作 surrogate 捕获 inter-agent dependency；coordinate ascent 把组合优化拆成序贯单体，复杂度从 \(O(\prod |\mathcal{P}_i|)\) 降到 \(O(\sum |\mathcal{P}_i|)\)。

核心 idea：三件套。GAT 消息传递得 topology-aware \(\mu(c)\)；information matrix \(\mathbf{M}\) 算 uncertainty \(\sigma(c) = \sqrt{\Phi(c)^\top \mathbf{M}^{-1} \Phi(c)}\)；UCB \(= \mu(c) + \alpha \sigma(c)\) 引导搜索；坐标上升每轮逐个优化单 agent prompt。

方法详解¶

整体框架¶

MAS workflow 建模为 DAG \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\)，\(N\) 个 agents，每个 agent \(a_i\) 绑定 prompt \(p_i \in \mathcal{P}_i\)。\(T = 50\) 评估预算找 \(c^* = \arg\max_c s(c)\)。三阶段：(1) Warmup \(T_0\) 轮随机 sample + GAT 初始训练；(2) Coordinate ascent + UCB 主循环 \(T - T_0\) 轮，每轮在当前 \(c^*\) 上逐 agent 选最高 UCB 的 prompt，评测新的 \(c\)；(3) 更新 GAT、information matrix、incumbent。Text encoder 用 Qwen3-Embedding-8B，LLM backbone GPT-4o-mini。

关键设计¶

GAT 代理模型捕获 topology-induced coupling:
- 功能：把"prompt 改了 → downstream agent input 分布变了 → 任务性能变了"显式建模进 prediction。
- 核心思路：每个 agent 是 node，node feature \(\Phi(p_i)\)，edges = workflow dependency + self-loop。Multi-head GAT 消息传递 \(\mathbf{h}_i^{(l+1)} = \|_{k=1}^K \sigma(\sum_{j \in \mathcal{N}(i) \cup \{i\}} \alpha_{ij}^{(k)} \mathbf{W}^{(l,k)} \mathbf{h}_j^{(l)})\)，attention \(\alpha_{ij}^{(k)}\) 由 leaky-ReLU + softmax 算。最后 mean pool + MLP 得 \(\mu(c)\)。
- 设计动机：OPRO/PromptBreeder 把 MAS 当黑盒；MIPRO 隐式建模 dependency 但 weak。GAT 显式编码 workflow topology，attention 还能学到"哪个 edge 重要"。
LinUCB + information matrix 量化 epistemic uncertainty:
- 功能：在 budget=50 下平衡 exploit（GAT 预测分高）和 explore（未见过的组合）。
- 核心思路：维护 \(\mathbf{M} \in \mathbb{R}^{Nd \times Nd}\)，初始化 \(\lambda \mathbf{I}\)，每次评估后 \(\mathbf{M} \leftarrow \mathbf{M} + \Phi(c) \Phi(c)^\top\)。Combined embedding \(\Phi(c) = [\Phi(p_1); \dots; \Phi(p_N)] \in \mathbb{R}^{Nd}\)；uncertainty \(\sigma(c) = \sqrt{\Phi(c)^\top \mathbf{M}^{-1} \Phi(c)}\)；UCB \(= \mu(c) + \alpha \sigma(c)\)。
- 设计动机：LLM 评估贵，必须 sample-efficient。Information matrix 是 LinUCB 经典工具，套到 prompt embedding 提供自然 novelty 信号，比 ε-greedy 智能。
坐标上升 + UCB 把指数搜索降为线性:
- 功能：把"对所有 \(\prod |\mathcal{P}_i|\) 组合算 UCB"变成"逐 agent 算 \(|\mathcal{P}_i|\) 个 UCB"。
- 核心思路：从当前最佳 \(c^*\) 出发，依次更新 \(p_i^* \leftarrow \arg\max_{p \in \mathcal{P}_i} \mathrm{UCB}(p_1^*, \dots, p_{i-1}^*, p, p_{i+1}^*, \dots, p_N^*)\)。每轮 UCB 评估只 forward GAT 不跑 MAS，几乎零成本；评估只在每轮结束跑一次完整 MAS。
- 设计动机：UCB+GNN forward 便宜、MAS evaluation 贵——把"贵的"和"便宜的"分清楚是巧妙算力分配。

实验关键数据¶

主实验：6 个基准（GPT-4o-mini，3 次平均）¶

方法	HotpotQA	DROP	HumanEval	MBPP	GSM8K	MATH	平均
IO	60.36	53.09	89.31	69.11	87.80	51.71	68.56
CoT	67.62	58.27	89.57	69.89	88.34	52.47	71.03
ReAct	65.61	67.25	87.79	66.08	88.91	52.61	71.38
PromptBreeder	68.76	71.85	88.80	70.38	91.97	52.13	73.98
Instinct	69.92	71.90	90.08	70.23	92.64	52.40	74.53
AFlow	73.42	79.48	91.09	79.96	93.36	53.83	78.52
MIPRO	74.37	79.13	91.35	80.65	92.80	54.90	78.87
MASPOB	75.43	82.28	94.15	80.65	93.90	57.05	80.58

MASPOB 在 6 个任务里 5 个 SOTA，平均 80.58 vs MIPRO 78.87（+1.71）vs IO 68.56（+12.02）。

复杂 topology 实验¶

在 AFlow 自动生成的更大 topology（HotpotQA 8 agents, DROP 7, HumanEval 7）上 MASPOB 仍是最高，且优势随 agent 数量放大——验证 GAT 显式 topology 建模的针对性价值。

关键发现¶

平均 +12% 相对 IO：prompt 优化整体能拉 +12 分；MASPOB 再 +1.7 分 vs MIPRO。
MATH 任务上最大改善：数学推理需要多步逻辑链，topology coupling 最强；MASPOB MATH +2.15 vs MIPRO。
HumanEval 94.15：代码生成天花板被推到 94.15，对工业最关心场景特别有效。
同 budget 下胜出：所有方法用同样 50 评估预算，MASPOB 的 sample-efficiency 是真实优势。

亮点与洞察¶

三个挑战 → 三个机制的清晰对应：sample 贵 → UCB；topology coupling → GAT；combinatorial → coordinate ascent。每个 component 解一个具体痛点。
GNN as surrogate for prompt opt：第一次把 workflow topology 当作 inductive bias 注入 surrogate，是方法学创新。
LinUCB 在 prompt embedding 空间：把 contextual bandit 工具搬到 LLM prompt 优化，无需手调 ε。
Coordinate ascent + cheap UCB forward：把"贵评估"和"便宜代理 forward"分开是巧妙算力分配。
6 个 benchmark 跨 3 领域：QA + Code + Math 都覆盖，不挑任务。
可适配其他 multi-agent systems：思路可推广到其他 combinatorial design space 上做 sample-efficient 优化的场景。

局限与展望¶

依赖 workflow 已固定：假设 topology 已设计好，只优化 prompt——但这恰好是问题设定前提。
GAT 训练数据少：50 评估总样本对 GNN 偏少，可能 overfit；warmup \(T_0\) 选取需调。
Prompt embedding 质量依赖 Qwen3-Embedding：固定 encoding 可能限制 GAT 表达能力。
没跟 DSPy / TextGrad 对比：缺 RL-style 和 gradient-based baseline。
只用 GPT-4o-mini：更强 LLM 下的 marginal gain 未知。
没 long-horizon stability：500+ 评估预算是否还保持优势未知。
理论 regret 分析缺失：LinUCB 在组合空间下的 regret bound 未给。

评分¶

新颖性: ⭐⭐⭐⭐⭐ GNN surrogate + LinUCB + coordinate ascent 三件套组合应用到 MAS prompt opt 是方法学创新。
实验充分度: ⭐⭐⭐⭐ 6 基准跨 3 领域 + 7 baseline + 复杂 topology 实验扎实；缺 RL-style 和大模型 backbone。
写作质量: ⭐⭐⭐⭐⭐ 问题动机清晰（三重挑战）、方法对应（三件套）、伪代码可复现。
价值: ⭐⭐⭐⭐⭐ 直接服务 MAS 部署痛点（workflow 固定 + prompt 优化），开源代码降门槛，对生产环境 LLM agent 系统有实战价值。