TL;DR
RobustSGPO introduces explicit search-space control to semantic-gradient-based prompt optimization for multi-agent systems. By systematically planning edit scopes, enforcing structural constraints via a typed compiler, and maintaining a diverse archive of candidate solutions, it significantly improves task completion rates and optimization efficiency under a fixed token budget.
What Problem Does This Paper Address?
Building on prior work (AgentX), which automates multi-agent workflows using semantic gradients (SGPO) to diagnose and fix execution failures, the authors tackle a major limitation: unconstrained LLM-based optimization often fails to explore the search space effectively.
When given free rein to optimize a multi-agent system, LLMs tend to fall back on familiar, local prompt rewrites rather than addressing complex cross-agent handoffs or structural changes. Conversely, restricting edits to a single agent prevents the system from fixing multi-agent coordination issues. The paper addresses how to systematically select, execute, and retain valid structural and prompt edits within a multi-agent harness under a fixed token budget.
Methods
RobustSGPO introduces three core mechanisms to control the search space:
- Explicit Edit Selection: Instead of letting the LLM freely generate changes, a controller pre-specifies the edit scope (which agents to modify), the operation type (e.g., field alignment), and the exact targets before content generation.
- Patch Construction & Verification (Typed Compiler): A predefined code layer handles structural additions/removals and normalizes names. This ensures that the generated edits strictly comply with the requested plan and pass structural validity checks before execution.
- Category-Based Retention (Archive): Inspired by quality-diversity algorithms (like MAP-Elites), RobustSGPO maintains an archive of the best-performing snapshots categorized by their edit scope and operation. The search process alternates between mutating the current best solution (incumbent) and these archived alternatives, preventing the optimization from getting stuck in local minima.
Datasets
The method is evaluated on the AgentX brainstorming workflow, which coordinates question, idea, and validation agents. The evaluation uses 120 tasks split into two distinct families:
- Local instruction failures
- Cross-agent handoff/structural failures
The tasks are split into a 30/15/15 optimization/validation/test configuration per family (60/30/30 tasks total).
Key Insights and Ideas
- More freedom isn't always better: Simply opening up the entire search space doesn't lead to better results because LLMs naturally concentrate on simple text rewrites. Explicitly scheduling permissions (starting narrow and expanding, e.g., $1 \to 2 \to 3$ agents) yields much better final quality than keeping the space wide open from the start.
- Structural enforcement beats free-form generation: Letting a typed compiler handle the boilerplate of adding/removing agents or routing changes drastically improves structural validity (77.8% validity vs. 48.9% for unconstrained generation).
- The Adaptation-Retention Tradeoff: When shifting to new tasks, keeping an elite archive of diverse edit categories preserves performance on the original tasks (reducing degradation), whereas random reservoir sampling explores aggressively and reaches a higher peak on the new destination tasks at the cost of forgetting the old ones.
Key Results
- Higher Quality: RobustSGPO achieved a final test score of 4.30 (on a 0–5 scale), outperforming the baseline SGPO (3.82) by 0.48 points.
- Token Efficiency: Under a strict 20-million-token budget, RobustSGPO outperformed baseline SGPO by 0.37 points (4.14 vs 3.77), proving that structured search saves compute.
- Task Completion: RobustSGPO boosted the task completion rate on held-out tasks from 60.0% to 80.0%, showing substantial gains in handling both local and cross-agent failures.
Limitations and Future Work
- Archive Overhead: Maintaining and rescoring the category archive introduces a measurable token cost. When evaluated at equal token costs rather than equal rounds, RobustSGPO's margin over a simpler structured search narrows from 0.10 to 0.04 points.
- Scope of Evaluation: The experiments are limited to a single brainstorming workflow within the AgentX framework and do not benchmark against other prompt optimization frameworks on generalized public datasets.
Summary updated