SafeSieve: From Heuristics to Experience in Progressive Pruning for LLM-based Multi-Agent Communication

1. Problem Statement

Large Language Model (LLM) based Multi-Agent Systems (MAS) demonstrate strong collaborative capabilities but suffer from two critical issues:

• Redundant Communication: Dense, round-robin conversations between agents generate excessive token overhead, increasing inference costs and diluting attention on key information.
• Inefficient Optimization Strategies: Existing methods fall into two categories with distinct limitations:
  • Pre-design (Static): Methods like GPTSwarm and G-Designer construct static topologies before execution. They lack adaptability to runtime dynamics.
  • Post-pruning (Dynamic): Methods like AgentPrune and AgentDropout dynamically remove edges but often rely on greedy Top-k pruning. This approach risks removing critical communication paths, leading to local sub-optimality and reduced system robustness against malicious agents (prompt injection).

There is currently no unified framework that bridges heuristic initialization with experience-driven dynamic adaptation while preserving structural coherence among agents.

2. Methodology: SafeSieve

SafeSieve is a progressive, adaptive pruning algorithm designed to optimize MAS communication topologies. It operates via a dual-mechanism that transitions from heuristic initialization to experience-driven refinement, utilizing 0-extension clustering for structural preservation.

A. Dual-Mechanism Edge Scoring

SafeSieve employs a dynamic edge scoring matrix $E \in \mathbb{R}^{n \times n}$ that evolves over time ($t$):

1. Semantic Heuristic Initialization (Start):
   • Combines embedding-based similarity with expert LLM-assessed functional compatibility ($S_{compat}$).
   • Formula: $S_{compat} = \gamma \cdot \text{Similarity} + (1-\gamma) \cdot Q(S_{expert})$.
   • This provides a "plan" phase based on agent roles and capabilities.
2. Progressive Historical Feedback (Execution):
   • Tracks the Historical Complementarity ($C_{hist}$) of edges based on their contribution to successful task completions over time.
   • Integrated Scoring: The final edge score $E_{ij}(t)$ smoothly transitions from the initial semantic score to the accumulated historical score using a temporal weighting function:
     $$E_{ij}(t) = \left(1 - \frac{t}{T}\right) \cdot \alpha_0 \cdot S_{compat} + \left[\beta_0 + (\beta_{max} - \beta_0) \cdot \frac{t}{T}\right] \cdot C_{hist}(t)$$
   • This mimics the human "plan-then-adjust" paradigm.

B. 0-Extension Clustering for Pruning

Unlike greedy Top-k methods that remove edges individually, SafeSieve uses 0-extension clustering (a graph partitioning problem) to prune edges globally:

• Terminal Selection: Selects a subset of agents as cluster centers (terminals) to maximize connectivity transfer.
• Cluster Assignment: Solves an optimization problem to assign agents to terminals, minimizing the "distance" (inverse of edge score) of edges crossing cluster boundaries.
• Structured Pruning:
  • Edges crossing cluster boundaries that fall below a dynamic threshold $\theta(t)$ are pruned.
  • This preserves structurally coherent agent groups (communities) while eliminating ineffective links, avoiding the fragmentation caused by greedy pruning.
• Regularization: After pruning, edge scores are normalized to adapt to the new graph topology.

3. Key Contributions

1. Unified Framework: SafeSieve is the first post-pruning framework that integrates LLM-based semantic evaluation, cumulative historical feedback, and 0-extension clustering. It bridges the gap between early-stage heuristics and feedback-driven refinement.
2. Efficiency with Robustness: It achieves significant token reduction while maintaining or improving accuracy. Uniquely, it exhibits inherent adversarial resilience, detecting and mitigating malicious agents (prompt injection) with minimal accuracy degradation.
3. Heterogeneous Deployment: The framework supports cross-model collaboration (e.g., large LLMs guiding smaller ones). It leverages model diversity to reduce deployment costs by dynamically allocating tasks based on model capability and cost.

4. Experimental Results

Experiments were conducted on six benchmarks (MMLU, GSM8K, SVAMP, HumanEval, AQuA, MATH-500) using models like DeepSeek-V3 (671B) and GPT-4o-mini.

• Performance & Efficiency:

  • Accuracy: SafeSieve achieved an average accuracy of 94.01% on DeepSeek-V3, outperforming all baselines (e.g., +1.23% over AgentPrune, +2.86% over GPTSwarm).
  • Token Reduction: Reduced token usage by 12.4% – 27.8% compared to full-connected graphs and other pruning methods.
  • Ablation: Removing historical feedback dropped accuracy by 1.23%; replacing 0-extension with Top-k pruning dropped accuracy by 1.88%, validating the necessity of both components.

• Robustness (Adversarial Attacks):

  • Under prompt injection attacks (injecting low-quality/malicious agents), SafeSieve showed the highest resilience.
  • Average Accuracy Drop: Only 1.23% (compared to 4.59% for AgentPrune and 2.21% for AgentDropout).
  • The 0-extension clustering prevents "information islands," maintaining network connectivity even when malicious nodes are present.

• Heterogeneous Collaboration:

  • In mixed-model settings (e.g., DeepSeek-V3 + LLaMA-8B + Qwen2.5), SafeSieve reduced total deployment costs by 13.3% while maintaining performance.
  • It effectively utilized the "barrel principle," where large models handle complex reasoning and small models handle structured tasks, optimizing cost-efficiency ratios.

5. Significance

SafeSieve represents a paradigm shift in Multi-Agent System optimization:

• From Static to Adaptive: It moves beyond static topology design to a dynamic, learning-based pruning strategy that evolves with the task.
• From Greedy to Structural: By utilizing 0-extension clustering, it avoids the pitfalls of greedy edge removal, ensuring that the remaining communication graph remains structurally sound and functionally coherent.
• Practical Deployment: It offers a GPU-free (in terms of training requirements for the pruning logic) and scalable solution that significantly lowers the economic barrier for deploying complex LLM agent teams in real-world scenarios.

The code is open-sourced at: https://github.com/csgen/SafeSieve.