Skip to content

AgentGrad: Intervention-guided Prompt Optimization for Multi Agent Systems

Conference: NeurIPS 2026
arXiv: 2609.08572
Area: Others
Keywords: Large Language Model Multi-Agent Systems, Prompt Optimization, Textual Gradient, Sequential Intervention, Semantic Gradient Abstraction

TL;DR

To tackle credit assignment failures and gradient mixing conflicts in multi-agent prompt optimization, AgentGrad introduces reverse sequential intervention to identify responsible agents and produce pseudo-label supervision, combined with semantic clustering and gradient abstraction to generate coherent, generalizable updates.

Background & Motivation

Multi-agent systems (MAS) driven by large language models (LLMs) solve complex tasks by decomposing difficult challenges into specialized subtasks assigned to cooperative agents. This paradigm has achieved remarkable success across multi-step reasoning, planning, and tool use. Nevertheless, the cooperative ceiling of any MAS remains strictly governed by the prompt design of each constituent agent. To overcome manual prompt engineering, automatic prompt optimization (APO)—and specifically textual gradient methods that leverage natural language feedback and critiques to iteratively update prompts—has emerged as a prominent direction.

Despite their empirical promise, existing textual gradient methods face systematic bottlenecks in two critical stages within multi-agent environments: gradient extraction and gradient aggregation. In gradient extraction, conventional approaches suffer from two core limitations: first, target prompts are selected without verifying whether an individual agent's revision actually fixes the system failure, leading to either expensive simultaneous multi-prompt tuning or arbitrary round-robin choices; second, gradients are computed without direct agent-level intermediate supervision, relying on distant task-level end outputs that obscure internal failure dynamics. In gradient aggregation, standard methods randomly partition and concatenate sample gradients, inadvertently blending disparate, contradictory error modes and yielding prompts that fail to generalize.

Resolving these interaction bottlenecks requires translating macro system-level failures into verified causal attributions and structured abstract representations. Core idea: use reverse sequential intervention to identify responsible agents capable of resolving system failures while generating agent-level pseudo-labels, followed by semantic clustering and multi-scale abstraction of textual gradients to achieve accurate and efficient multi-agent prompt optimization.

Method

Overall Architecture

The optimization pipeline of AgentGrad iteratively refines the prompt collection \(\mathcal{P} = (p^1, \dots, p^N)\) across multiple agents. In each training iteration, the system executes the current prompts on the training set to collect failed instances \(\mathcal{F}\). It then applies prompt-level interventions in reverse execution order to isolate the single target agent whose behavioral correction independently fixes the failure. Using the contrast between original and intervened intermediate outputs, the system extracts sample-level textual gradients. An aggregator LLM clusters these gradients into semantic minibatches and synthesizes generalized gradients, which are validated hierarchically on their semantic minibatches and the validation set.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["MAS Execution & Failure Collection<br/>Collect unresolved failed set F"] --> B["Target Agent Identification<br/>Reverse sequential intervention"]
    B --> C["Agent-Level Supervision & Extraction<br/>Extract sample gradients from output contrast"]
    C --> D["Semantic Gradient Abstraction<br/>Cluster minibatches & synthesize generalized gradients"]
    D --> E["Hierarchical Validation & Update<br/>Minibatch screening then validation check"]
    E -->|Budget remaining| A
    E -->|Budget exhausted| F["Optimized Prompt Collection P*"]

Key Designs

1. Target Agent Identification: Reverse Sequential Intervention

To overcome severe credit assignment ambiguity in multi-agent workflows without incurring the computational explosion of simultaneous agent tuning, this design isolates exactly which agent's correction resolves the failure. Recognizing that failures frequently accumulate or manifest in downstream agents, AgentGrad applies hint interventions \(\mathcal{H}\) sequentially in reverse execution order (from \(n = N\) down to \(1\)). The hint \(\mathcal{H}\)—formulated from ground-truth labels \(y_i\), environmental constraints, and role descriptions—is injected into agent \(\pi^n\) strictly during training. If the intervened system successfully resolves the task (\(r(\Pi^{(n, \mathcal{H})}(x_i; \mathcal{P}), y_i) = r_{\max}\)), the instance is attributed to agent \(\pi^n\) and appended to resolved set \(\mathcal{T}^n\). Resolved instances are immediately removed from the unresolved pool \(\mathcal{F}^n\), terminating earlier upstream rollouts and cutting computational cost. Failures unresolved after step \(n=1\) are treated as unrecoverable hard cases for the current round and set aside until future iterations.

2. Agent-Level Supervision & Extraction: Contrastive Behavioral Pseudo-Labels

Standard textual gradient techniques derive critiques from the gap between system-level final outputs and ground-truth answers, an approach that leads to severe diffusion and misattribution across multi-agent communication hops. AgentGrad treats the intervened intermediate output \(\tilde{y}_i^n = \pi^n(x_i^n; p^n, \mathcal{H})\) as a localized, high-quality pseudo-label specifying how agent \(\pi^n\) should act given identical input context \(x_i^n\). Comparing the un-intervened failure output \(\hat{y}_i^n = \pi^n(x_i^n; p^n)\) with \(\tilde{y}_i^n\) under identical input conditions cleanly isolates the behavioral correction. A gradient extractor LLM then computes a fine-grained sample-level textual gradient: $\(\delta_i^n = \mathrm{LLM}_{\nabla}(p^n, x_i^n, \hat{y}_i^n, \tilde{y}_i^n)\)$ This formulation removes the need for crafting hand-engineered non-differentiable loss functions, deriving direct agent-level supervision solely from behavioral contrast.

3. Semantic Textual Gradient Abstraction: Coherent Clustering and Multi-Scale Synthesis

Conventional gradient aggregation randomly groups gradients and concatenates critiques, frequently merging orthogonal failure modes (such as output formatting errors and logical calculation flaws) and causing prompt optimizers to generate bloated or self-conflicting instructions. AgentGrad introduces an aggregator LLM to cluster the sample gradient set \(\Omega^n = \{\delta_i^n\}\) into semantically coherent groups, creating semantic minibatches \(\mathcal{D}_j^n\). Each minibatch is abstracted into a single, unified generalized gradient \(\bar{\delta}_j^n\). To balance coarse broad-pattern guidance and fine-grained corrective precision, the aggregator follows a cyclic schedule lower bound on cluster sizes (e.g., \(5 \to 3 \to 1 \to 5 \dots\)), guiding the optimization trajectory smoothly between broad repairs and delicate corner-case refinements.

4. Hierarchical Validation & Prompt Updating: Coarse-to-Fine Gated Admission

With generalized gradients \(\{\bar{\delta}_j^n\}\) organized by decreasing cluster size \(|\mathcal{D}_j^n|\), the prompt optimizer prioritizes pervasive errors affecting the largest subsets of failures. For each candidate prompt \(p_{\text{new}}^n = \mathrm{LLM}_{\text{PromptOptimizer}}(p^n, \bar{\delta}_j^n)\), the framework enforces a two-stage evaluation barrier: the candidate is first evaluated on the inducing semantic minibatch \(\mathcal{D}_j^n\). Only if empirical reward improves is it granted evaluation on the held-out validation set \(\mathcal{D}_{\text{val}}\). Passing both stages admits the prompt update (\(p^n \leftarrow p_{\text{new}}^n\)), whereas failure at either hurdle triggers immediate rejection. This gated screening avoids expensive full validation rollouts for unpromising candidates, dramatically accelerating optimization throughput.

A Worked Example

In a privacy-conscious delegation task (PUPA), an agent must redact private queries by replacing sensitive tokens with generic placeholders. Under the baseline prompt, three failed examples occur: Example 1 leaks an organization name ("PTV News"), Example 2 leaks a geographic location ("Warsaw, Poland"), and Example 3 leaks a fictional identifier name ("Mishaali Kapoor"). 1. Intervention & Pseudo-Labeling: Under reverse intervention, the redaction agent receives a hint \(\mathcal{H}\) identifying sensitive entities and outputs properly sanitized text containing [ORG], [LOCATION], and [PERSON] tokens. System evaluation returns full reward, confirming the target agent. 2. Sample Gradient Extraction: The gradient extractor compares failed and corrected outputs to produce sample gradients: "Prompt must treat news agency acronyms as sensitive organizations," "Prompt must identify city and country names as sensitive entities," and "Prompt must flag personal names regardless of context." 3. Semantic Clustering & Abstraction: The aggregator identifies that all three samples share the common corrective policy of redacting identifying named entities (personal, geographic, institutional). It clusters them into a single semantic minibatch and generates the generalized gradient: "Establish a unified redaction rule: any token naming a person, organization, or location must be replaced with corresponding generic placeholders." Unrelated format critiques are excluded. 4. Validation: The prompt updated with this generalized gradient achieves 100% improvement on the semantic minibatch and subsequent gain on the validation set, successfully updating the agent prompt.

Loss & Training

Optimization operates under a fixed total rollout budget \(B\). The expected reward across dataset \(\mathcal{D}\) is formalized as \(R_{\mathcal{D}}(\mathcal{P}) = \mathbb{E}_{(x, y) \sim \mathcal{D}} [r(\Pi(x; \mathcal{P}), y)]\). The outer loop maintains the failure pool \(\mathcal{F}\), while the inner loop conducts sequential intervention and gradient extraction. By enforcing the dual improvement condition: $\(R_{\mathcal{D}_j^n}(\mathcal{P}_{\text{new}}) > R_{\mathcal{D}_j^n}(\mathcal{P}) \quad \text{and} \quad R_{\mathcal{D}_{\text{val}}}(\mathcal{P}_{\text{new}}) > R_{\mathcal{D}_{\text{val}}}(\mathcal{P})\)$ AgentGrad guarantees monotonic non-decreasing validation trajectory, preventing catastrophic forgetting and over-fitting to narrow failure instances.

Key Experimental Results

Main Results

Evaluations across five diverse MAS benchmarks—HotpotQA (multi-hop QA), HoVer (fact verification), PUPA (privacy delegation), IFBench (instruction following), and MATH (mathematical reasoning)—using both proprietary GPT-5-mini and open-source Qwen3-8B backbones across 3 random seeds.

Benchmark Metric Baseline (No PO) MIPROv2 TextGrad GEPA AgentGrad (Ours)
GPT-5-mini Backbone
HotpotQA Accuracy (%) 46.33 ± 0.69 59.00 ± 1.66 67.89 ± 1.31 68.33 ± 1.55 73.89 ± 1.09
HoVer Accuracy (%) 58.11 ± 1.01 62.89 ± 1.34 63.22 ± 1.47 63.11 ± 1.90 64.78 ± 1.44
PUPA Accuracy (%) 84.74 ± 0.33 88.33 ± 2.13 89.72 ± 2.43 91.87 ± 1.55 95.17 ± 0.49
IFBench Accuracy (%) 73.07 ± 0.60 73.70 ± 0.86 73.07 ± 0.60 75.23 ± 0.32 76.08 ± 0.45
MATH Accuracy (%) 76.48 ± 0.91 83.13 ± 1.72 76.48 ± 0.91 86.37 ± 0.50 87.62 ± 0.09
Avg. Gain (GPT-5-mini) Absolute points - +5.66 +6.33 +9.24 +11.76
Qwen3-8B Backbone
HotpotQA Accuracy (%) 41.33 ± 0.84 58.33 ± 2.37 50.86 ± 5.36 57.33 ± 2.54 60.45 ± 1.68
HoVer Accuracy (%) 36.67 ± 1.02 45.44 ± 0.68 51.44 ± 0.78 50.11 ± 1.60 52.11 ± 1.66
PUPA Accuracy (%) 80.87 ± 0.06 85.76 ± 2.86 84.50 ± 2.31 91.03 ± 1.71 91.51 ± 0.72
IFBench Accuracy (%) 40.82 ± 1.99 40.08 ± 2.21 42.52 ± 0.45 37.53 ± 1.62 41.42 ± 0.99
MATH Accuracy (%) 83.24 ± 0.38 84.68 ± 0.92 83.90 ± 0.67 85.05 ± 0.48 85.81 ± 0.25
Avg. Gain (Qwen3-8B) Absolute points - +6.27 +6.06 +7.62 +9.67

Ablation Study

Ablation on HotpotQA and PUPA using GPT-5-mini, progressively incorporating target identification (TI), agent-level intermediate supervision (AS), and semantic textual gradient abstraction (STGA):

Configuration (TI / AS / STGA) HotpotQA Accuracy (%) PUPA Accuracy (%) Mechanistic Role
Vanilla Baseline 67.89 ± 0.80 85.74 ± 1.65 Standard unguided textual gradient descent
+ TI (Target Identification only) 69.33 ± 0.38 89.58 ± 1.89 Pinpoints responsible agent, isolating credit attribution
+ TI + AS (Intermediate Supervision) 70.89 ± 0.62 92.23 ± 0.68 Contrastive output generates targeted localized pseudo-labels
+ TI + STGA (Gradient Abstraction) 71.89 ± 0.29 93.13 ± 0.53 Prevents noisy gradient conflict, forming coherent update direction
AgentGrad (TI + AS + STGA) 73.89 ± 1.09 95.17 ± 0.49 Joint synergy yielding optimal convergence and performance

Key Findings

  • Drastic Optimization Wall-Clock Speedup: AgentGrad finishes optimization in an average of 136 minutes across five benchmarks, achieving a 2.5× speedup over the next-fastest baseline GEPA (337 minutes) and a 4.7× speedup over TextGrad (647 minutes). On HotpotQA, AgentGrad reaches 70% accuracy within 1,000 rollouts, while GEPA requires over 6,000 rollouts.
  • Superior Cost Efficiency: In API monetary expenditure, AgentGrad costs $27.14 on average, reducing cost by 21.8% relative to GEPA ($34.73) and saving over 70% compared to TextGrad ($96.82).
  • High Minibatch and Validation Hit Ratios: AgentGrad achieves a minibatch improvement ratio of 0.72 (compared to 0.44 for TextGrad and 0.28 for GEPA) and a validation improvement ratio of 0.27 (vs. 0.21 and 0.14), proving that abstract gradients consistently translate to robust out-of-sample improvements.
  • Out-of-Distribution Transferability: Prompts optimized on source benchmarks achieve state-of-the-art zero-shot transfer on unseen benchmarks in the same domain (e.g., HotpotQA to 2WikiMultiHopQA: 51.22% vs. GEPA 44.89%), confirming that generalized gradients encapsulate principled strategies rather than dataset-specific memorization.

Highlights & Insights

  • Causal Intervention for Multi-Agent Credit Assignment: Transforming counterfactual intervention into an automated localization tool cleanly solves the attribution bottleneck in multi-agent prompt optimization.
  • Self-Generated Contrastive Supervision: Leveraging the behavioral shift between unguided and hint-guided executions provides high-signal agent-level pseudo-labels without human annotation overhead.
  • Semantic Minibatch Abstraction Over Random Mixing: Analogous to resolving gradient interference in multi-task learning, semantic clustering distills coherent prompt updates that prevent instruction bloat and mutual cancellation.

Limitations & Future Work

  • Reliance on Verifiable Ground-Truth Hints: Sequential intervention relies on hint \(\mathcal{H}\) constructed from ground-truth outputs or explicit constraints, making application to open-ended creative dialogue or subjective tasks non-trivial.
  • Single-Agent Causal Assumption: The current formulation assumes that fixing a single agent is sufficient to resolve each failure. Highly coupled multi-agent cascades where simultaneous coordinated adjustments are required may be treated as unrecoverable hard cases.
  • Future Directions: Extending intervention strategies to multi-agent joint perturbations and applying gradient abstraction to dynamic agent topology discovery.
  • vs TextGrad: TextGrad backpropagates natural language critiques across chained LLM calls, but lacks causal verification of agent responsibility and intermediate agent pseudo-labels, often leading to diluted updates. AgentGrad isolates responsible agents via counterfactual intervention.
  • vs GEPA: GEPA relies on full-trajectory reflection and evolutionary mutation, but random batching mixes disparate error modes, causing sluggish convergence (taking 2.5× more wall-clock time). AgentGrad's semantic abstraction and gated validation dramatically streamline rollout usage.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Reverse causal intervention and semantic gradient abstraction provide a fundamentally principled framework for MAS prompt optimization.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Tested on 5 diverse MAS benchmarks across proprietary and open models, featuring comprehensive ablation, wall-clock time, cost analysis, and out-of-domain transfer evaluations.
  • Writing Quality: ⭐⭐⭐⭐⭐ Rigorously formalized, clear mathematical notation, intuitive figures, and well-structured empirical analysis.
  • Value: ⭐⭐⭐⭐⭐ Offers a high-utility, cost-effective paradigm for optimizing compound AI systems in production.