Adaptive Graph Pruning for Multi-Agent Communication

1 Introduction

• Existing approaches use human-designed static layouts or optimize edges within a fixed agent pool, limiting per-task flexibility.Hand-designed layouts may work in one domain and fail in another, while manual tuning can be costly.Source: §1 · p. 1
• AGP jointly optimizes agent quantity through hard pruning and communication topology through soft pruning.The framework aims to tailor both the agent set and its connections to each task.Source: §1 · p. 2
• AGP uses two stages: it first trains soft-pruning networks for task-specific topologies, then jointly optimizes hard and soft pruning within a maximum complete graph.The second stage uses task–topology data pairs to configure agent counts and communication topologies per task.Source: §1 · p. 2
• Across six benchmarks, AGP reports state-of-the-art performance with an average improvement of 2.58% ∼9.84%.The paper also reports fewer training steps and lower token consumption, including a decrease of more than 90% after ten training steps.Source: §1 · p. 2
• The paper presents AGP as a task-adaptive framework that offers high training efficiency and inference-token economy.Its contributions also include dynamically constructing optimized communication topologies for individual tasks.Source: §1 · p. 2

2 Related Works

• Earlier multi-agent communication designs include non-interactive systems, chains, stars, trees, and general graphs.The section also describes fixed-node methods such as GPTSwarm and G-Designer, which optimize edge weights without adapting node count.Source: §2 · p. 2
• Agent-system automation includes prompt optimization, agent profiling, and inter-agent communication, alongside search-based system-design methods.The passage notes that exploring large configuration spaces can incur substantial computational overhead.Source: §2 · p. 2
• Prior graph approaches use predefined or globally optimized structures and may overlook task difficulty and heterogeneous agent usefulness.AGP is described as deriving per-task subgraphs and training a dual-pruning GNN to adapt connectivity and agent subset.Source: §2 · p. 2

3 Method

• AGP first mines high-utility subgraphs from a heterogeneous LLM-agent pool and keeps their edge labels and node masks as Stage II supervision.The method frames communication as graph-topology learning and produces a protocol for new queries.Source: §3 · p. 2

3.1 Preliminaries

• A maximum-size directed graph represents the agent pool, with edges indicating which agents may send messages to others.Each agent includes a language backbone, role or persona, dialogue history, and optional tools.Source: §3.1 · p. 3

3.2 Stage I: Collecting Optimized Graphs

• Stage I samples agent subsets, fine-tunes and scores each graph on its task, then retains the top two performers per task as supervision.The resulting edge labels and node masks are lifted into the maximum-node reference frame.Source: §3.2 · p. 3

3.3 Stage II: Training Soft-pruning & Hard-pruning

• Stage II uses a soft-pruning branch to weight information flow between retained agents and a hard-pruning branch to choose which agents remain.Both branches share a latent representation so edge and node decisions remain mutually consistent.Source: §3.3 · p. 4

3.3.1 Network Architecture

• The network encodes agent profiles and the task, applies a graph-convolutional backbone, and uses separate heads to predict edge weights and node masks.At inference, predicted node masks are thresholded at 0.5 to retain agents.Source: §3.3.1 · p. 4

3.3.2 Training Details

• AGP couples edge and node losses because edge supervision alone leaves all nodes active, while node-only sparsification produces a clique.The node loss includes a sparsity penalty and a coherence term that penalizes outgoing weights from ground-truth absent nodes.Source: §3.3.2 · p. 4

3.4 Dataset Composition

• The supervision corpus contains 460 labeled task graphs: 200 for general reasoning, 100 for mathematical reasoning, and 160 for code generation.Each example pairs a task description with a lifted edge-weight matrix and a mask identifying participating agents.Source: §3.4 · pp. 4–5

4.1 Experiment Setup

• AGP is evaluated on six public benchmarks across three task families, against single-agent prompting techniques and eight multi-agent systems.The benchmarks cover general knowledge, mathematical reasoning, and code generation.Source: §4 · p. 5, §4.1 · p. 5

4.2 Quantitative Results

• AGP achieved the strongest overall accuracy (91.04%), surpassing G-Designer by +1.48 and the strongest single-agent baseline, SC, by +5.62, and ranked first on five of six task groups.Per-task gains ranged from +2.58 on MultiArith to +9.84.Source: §4.2 · p. 5
• AGP is the only fully adaptive system among the 12 baselines and improves or matches the best baseline across the reported domains.The reported gains include MMLU +9.84, GSM8K +7.56, SVAMP +4.04, and AQuA +9.78; HumanEval is +3.54 over single-agent.Source: §4.2 · p. 6
• AGP uses 2.5 × 10^5 prompt tokens on MMLU, 90% less than GPTSwarm, while raising accuracy from 82.8% to 87.65%.The comparison reports similar accuracy gains with lower token use on GSM8K, SVAMP, and HumanEval; AGP also costs less than G-Designer on every benchmark.Source: §4.2 · p. 6, Figure 5 · p. 6
• On MMLU, AGP rises from 80% to 88% in 10 updates, and the reported curves show baseline-beating performance in fewer than ten optimization steps.Figure 4 plots accuracy or Pass1 against training steps for AGP, G-Designer, and GPTSwarm; evaluations begin after the fifth step.Source: §4.2 · p. 6, Figure 4 · p. 6

4.3 Case Study

• The case studies show AGP reproducing an intuitive two-agent chain, pruning redundant coding agents, and retaining non-obvious roles for a social-economic question.The three cases illustrate layouts that are fully intuitive, partially intuitive, and counter-intuitive.Source: §4.3 · p. 7

4.4 Ablation Study

• With both pruning branches enabled, AGP reports state-of-the-art results on MMLU, GSM8K, and HumanEval; removing soft-pruning produces the steepest declines.Removing soft-pruning costs 4.16, 4.88, and 4.99 points on those benchmarks, respectively; removing hard-pruning increases prompt length by 22–30%.Source: §4.4 · p. 7, Table 2 · p. 7

5 Limitations

• The main paper uses a fixed gpt-4o-mini backend, with gpt-3.5-turbo reported in Appendix A.3 [22].Transfer across other LLM families or model scales remains open.Source: §5 · p. 7
• Richer quantitative analyses of efficiency are still needed beyond the node, edge, and weight analyses in Appendices A.4–A.5 [22].Source: §5 · p. 7
• All reported results are text-only; multimodal, temporally extended, and embodied-agent settings remain unexplored.The passage names vision–language, tool use, and robotics simulations with sensor/action streams as examples.Source: §5 · p. 7

6 Conclusion

• 91.04% best average score, up to 90% fewer prompt tokens, and baseline performance surpassed in fewer than ten optimization steps across six benchmarks.AGP produces a cost/accuracy-balanced topology in one forward pass after training.Source: §6 · p. 7
• AGP jointly soft-prunes edges and hard-prunes nodes to produce input-adaptive, variable-size communication graphs.Source: §6 · p. 7
• After training, AGP removes exhaustive graph search and manual workflow design, serving as a plug-and-play module for heterogeneous agent pools.Source: §6 · p. 7

A Appendix

• Appendix A.3 reports gpt-3.5-turbo results on MMLU and GSM8K to examine generalization to another LLM architecture.Source: A Appendix · p. 8
• Appendices A.4–A.5 analyze changes in pruned nodes and edges and the influence of β in the loss formula.Source: A Appendix · p. 8
• The appendix also covers motivation, notation, three case-study types, dataset statistics, and agent profiles with prompts.Source: A Appendix · p. 8

A.1 Motivation

• Adding agents can hurt accuracy and token cost: on GSM8K, HumanEval, and MMLU, accuracy peaks only for a narrow team size.Source: §A.1 · p. 8
• The paper asks whether topology learning can select agent subsets and edge weights from task feedback, and whether counter-intuitive agent combinations can outperform intuitive ones.Source: §A.1 · p. 8
• AGP unifies hard- and soft-pruning in one end-to-end framework; its case studies show learned graphs can reproduce, refine, or overturn human intuition.Source: §A.1 · p. 8

• The search space comprises a max-complete graph K_Nmax with anchored agents V and its sub-graph family G.Source: §A.2 · p. 8
• Edge weights W and node mask m represent AGP’s soft-pruning and hard-pruning degrees of freedom, yielding task-adaptive topology G_com.Source: §A.2 · p. 8
• The optimization notation includes utility U, cost C, trade-off coefficient λ_c, Stage I supervision pairs (A_gt, y), and node:edge loss terms.Source: §A.2 · p. 8

• 76.61% accuracy is reported under MMLU with gpt-3.5-turbo.Source: §A.3 · p. 8
• 87.27% accuracy is reported under GSM8K with gpt-3.5-turbo.Source: §A.3 · p. 8
• The authors state that these results provide evidence for AGP’s generalizability to other LLM architectures.Source: §A.3 · p. 8
• 81.94% average accuracy with gpt-3.5-turbo is 0.29% higher than the single-agent with gpt-4.Source: Table A1 · p. 8, §A.3 · p. 8

• With a nine-agent max-complete graph, the large-agent case has fitted A = 46.834, µ = 8.027, and σ = 1.310, and is described as slightly left-skewed.Source: §A.4 · p. 8
• For mathematical reasoning and code generation, the small-agent case has fitted A = 64.868, µ = 3.594, and σ = −0.607, and is described as nearly standard.Source: §A.4 · p. 8
• The authors interpret these fitted patterns as further evidence that AGP can provide more economical and task-adaptive solutions.Source: §A.4 · p. 8

A.5 Discussion on weights

• When β = 0.75, the converged loss is 0.582; at β = 1 it is 0.723, and at β = 1.333 the loss oscillates without converging.Under batch size 10, 20 steps, and learning rate 1e-3, the authors report faster convergence for more edge weights.Source: §A.5 · p. 9

A.6 Further Case Study

• Across representative tasks, AGP matches human designs when sufficient, prunes redundant agents on easy tasks, and sometimes retains seemingly irrelevant roles.In the partially-intuitive case, it achieves the best score with fewer messages than any full four-agent baseline; counter-intuitive roles may add orthogonal knowledge or critique that boosts accuracy.Source: §A.6 · p. 9, Figure A1 · p. 9

A.7.1 Training-set Statistics

• 54% of tasks are fully-intuitive and 43% partially-intuitive, while the remaining 3% are counter-intuitive, according to the Stage I graph distribution.The authors note that almost half of tasks are not optimally handled by a pre-defined intuitive team; the counter-intuitive cases retain seemingly unrelated agents.Source: §A.7.1 · pp. 9–10

A.7.2 Benchmark Statistics

• Table A4 presents benchmark descriptions and statistics, but the supplied passage does not state their values.Source: Table A4 · p. 10, §A.7.2 · p. 10

A.8 Agent Profile Details

• Table A5 lists the fifteen roles anchoring the max-complete graph K15, with expertise tags and responsibility summaries.Source: Table A5 · p. 10, §A.8.1 · p. 11

A.8.1 Heterogeneous Agent Pool

• The agent pool spans humanities, social science, STEM, software engineering, and general reasoning or critique.Source: §A.8.2 · p. 11

A.8.2 Coverage Statistics •

• Seven of fifteen agents focus on code and algorithms, four on factual or legal knowledge, two on mathematical deduction, and two on meta-reasoning.The complete graph considers 105 directed edges before pruning yields task-specific sub-graphs.Source: §A.8.2 · p. 11

Input Format:

• Each agent receives the current task, its profile, and the dialogue history, then contributes reasoning and an answer to the shared history.The described output fields include id, role, and agent output.Source: Input Format · p. 13