Jaewon Chu

allonsy07@korea.ac.kr

Jinwoo Seo

sjwoo0612@kaist.ac.kr

Jaewon Cho

cho35750@kaist.ac.kr

Jeehye Na

jeehyena@kaist.ac.kr

Yunyang Xiong

Meta AI

hyunwoojkim@kaist.ac.kr

Youngdae Kim

UNIST

yunyang@meta.com

Hyunwoo J. Kim

youngdae.kim@unist.ac.kr

Abstract

Large language model (LLM)-based multi-agent systems (MAS) achieve strong performance by employing specialized multiple agents, yet their performance depends on the prompt design of each agent. For MAS prompt optimization, textual gradient methods that guide prompt updates using natural-language feedback have emerged as a leading paradigm. In this paper, we identify limitations in two stages of existing textual gradient approaches: gradient extraction and gradient aggregation. In gradient extraction, previous works select a target prompt without verifying whether modifying it resolves the failure, and derive gradients without agent-level supervision over the corresponding agent’s intermediate output. In gradient aggregation, individual gradients are randomly grouped and concatenated, often mixing unrelated failure modes and producing prompts that fail to generalize. To address these limitations, we propose AgentGrad, a prompt optimization framework for multi-agent systems based on sequential intervention and semantic textual gradient abstraction. For each failure, sequential intervention modifies the behavior of one agent at a time to identify the target agent whose modification resolves the failure. The modified output of the target agent then serves as agent-level supervision for extracting a fine-grained gradient. Semantic textual gradient abstraction clusters semantically similar gradients to prevent mixing unrelated failure modes, and abstracts each cluster into a generalized gradient that captures the shared corrective pattern. Experimental results show that AgentGrad achieves state-of-the-art performance across five MAS benchmarks and reduces wall-clock optimization time by $2.5\times$ on average compared to the next-fastest baseline.

1 Introduction

Recent advances in large language models (LLMs) have enabled the development of multi-agent systems (MAS), where multiple LLM-powered agents interact to solve complex tasks [1, 2, 3, 4]. A key advantage of MAS is that they decompose difficult problems into subtasks, allowing different agents to contribute complementary capabilities [1, 2, 3]. Such systems have shown strong performance across a wide range of challenging settings, including multi-step reasoning, planning, and information synthesis [1, 3, 4, 5, 6]. The behavior of each agent is governed by its input prompt, making prompt design critical to system performance [7, 8]. Motivated by this, recent works have explored automatic prompt optimization for MAS showing that refining agent prompts can substantially improve system performance [7, 8, 9, 10, 11, 12, 13]. Among these, textual gradient methods, which employ natural-language feedback to iteratively refine prompts, have emerged as a leading paradigm. [9, 10, 11, 14, 15].

In this paper, we identify systematic limitations in two stages of existing textual gradient approaches for MAS: textual gradient extraction and textual gradient aggregation. For gradient extraction, previous works exhibit two issues. First, the target prompt is selected without verifying whether modifying an individual prompt can resolve the failure. Existing methods either update all agent prompts simultaneously at substantial cost, or apply round-robin selection without testing which agent can repair the failure. Second, the gradient is derived without direct agent-level supervision over individual agents’ intermediate outputs. While agent-level supervision provides a direct update signal, it is unavailable in most MAS settings. In gradient aggregation, individual textual gradients are randomly grouped and directly concatenated. It often mixes unrelated failure modes and produces prompt that fails to generalize.

To address these challenges, we propose AgentGrad, a prompt optimization framework based on sequential intervention and semantic textual gradient abstraction. Sequential intervention addresses both limitations in the gradient extraction stage [16, 17, 18]. Specifically, AgentGrad applies sequential interventions (e.g., hint injection) to individual agents, identifying the target agent whose correction resolves the failure [16, 17, 18, 19, 20]. The intervention-adjusted output then serves as an agent-level pseudo-label to yield a fine-grained textual gradient.  [9, 11, 21, 22, 23]. Semantic textual gradient abstraction improves the gradient aggregation stage. It groups sample-level gradients that share a corrective pattern into semantic minibatches, and abstracts each minibatch into a single generalized textual gradient that captures the shared pattern [9, 10, 11, 14, 15, 24].

We evaluate AgentGrad on five MAS benchmarks spanning diverse task types: multi-hop QA (HotpotQA) [25], claim verification (HoVer) [26], instruction following (IFBench) [27], privacy-conscious delegation (PUPA) [28], and math reasoning (MATH) [29], using both open-source (Qwen3-8B) [30] and proprietary (GPT-5-mini) [31] backbones. Across all benchmarks, AgentGrad consistently outperforms strong recent prompt optimization baselines, including TextGrad [9] and GEPA [10], while substantially reducing wall-clock optimization time.

• We propose AgentGrad, a prompt optimization framework for MAS that addresses limitations in two stages of existing textual gradient approaches: gradient extraction and gradient aggregation.

• We introduce sequential intervention, a mechanism that resolves two limitations in gradient extraction stage: it identifies the target agent whose correction resolves the failure, and produces an agent-level pseudo-label that supplies fine-grained supervision for gradient extraction.

• We introduce semantic textual gradient abstraction, which groups sample-level gradients into semantic minibatches sharing a corrective pattern and abstracts each cluster into a single textual gradient with improved generalizability.

• Across five MAS benchmarks, AgentGrad achieves state-of-the-art performance and reduces wall-clock optimization time by $2.5\times$ on average over the next-fastest baseline.

2 Related Works

Automatic Prompt Optimization for LLM-Driven Agents

Automatic prompt optimization (APO) improves LLM-driven agents by refining instructions, demonstrations, and other textual inputs [7, 8, 32]. Early APO mainly targeted single-prompt settings through black-box search, edit-based instruction search, or LLM-generated feedback [12, 13, 33, 34, 35]. ProTeGi [11] introduced textual gradients by treating natural-language critiques of failed examples as gradient-like directions for prompt revision. Recent work extends APO from isolated prompts to compound agent systems [7, 8, 9, 10]. MIPRO [8] jointly searches instructions and demonstrations for multi-stage LM programs with Bayesian optimization [36, 37, 38]. TextGrad [9] extends textual gradients to compound LLM systems by propagating natural-language feedback across multiple LLM components, analogous to backpropagation. GEPA [10] combines trajectory-level reflection with evolutionary prompt search. These methods provide strong APO signals, typically through task-level feedback or trajectory-level reflection [8, 9, 10]. However, intermediate agent behaviors and interactions could provide finer-grained signals for multi-agent prompt optimization, yet this direction remains underexplored.

Failure Attribution in Multi-Agent Systems

Failure attribution in multi-agent systems is challenging since system-level errors can emerge from interactions among multiple agents [16, 19, 20]. This creates a credit-assignment problem: a failed final output gives limited evidence about which agent or step is associated with the failure [16, 39]. Recent benchmarks and diagnostic methods formalize this problem by localizing failures within multi-agent trajectories [16, 17, 18, 19, 20, 40]. Intervention-driven debugging systems further study these failures by editing, replaying, or perturbing agent executions to test how alternative behaviors affect the outcome [17, 41, 42]. Together, these works establish intervention as a practical tool for failure localization, attribution validation, and multi-agent debugging [41, 42]. AgentGrad extends this line of work from failure analysis to prompt optimization. It treats the corrected behavior revealed by intervention as agent-level supervision, turning attribution evidence into a localized target for updating the corresponding agent prompt.

Self-Generated Supervision

Self-generated supervision studies how LLMs can produce rationales, feedback, or reflections as optimization signals [43, 44, 45]. STaR bootstraps rationales to improve reasoning [43]. Reflexion and Self-Refine use model-generated feedback to refine later attempts, revised outputs, or future task behavior [44, 45]. These methods establish LLM-generated supervision as an effective optimization source without dense human annotations. Prior work primarily uses such supervision to improve reasoning trajectories, iterative outputs, or training objectives [22, 43, 44, 45], rather than to derive localized prompt updates for individual agents. AgentGrad redirects this supervision toward prompt-level optimization in multi-agent systems, translating agent-level behavioral correction into supervision for revising agent prompts.

3 Preliminaries

Prompt Optimization for MAS

Let $\Pi$ denote an MAS composed of $N$ LLM-based agents $({\pi }^1,\dots ,{\pi }^N)$. Given an input $x$, $\Pi$ generates output $\hat{y}=\Pi (x,𝒫)$, where $𝒫=(p^1,\dots ,p^N)$ denotes the collection of agent prompts. Given a reward function $r:\widehat{𝒴}\times 𝒴\to \left[0,1\right]$, prompt optimization finds ${𝒫}^{\ast }$ that maximizes the expected reward by exploring candidate prompts and validating improvement using a training set ${𝒟}_{\text{train}}$ and a validation set ${𝒟}_{\text{val}}$, respectively. Since rollouts—running $\Pi$ on an input followed by evaluation under reward function $r$—are computationally expensive, prompt optimization is typically formulated as finding the best solution within a budget of $B$ rollouts allowed [8, 10]:

${𝒫}^{\ast }=\arg \underset{𝒫}{\max }{𝔼}_{(x,y)\sim {𝒟}_{\text{val}}}r(\Pi (x,𝒫),y),\text{s.t. }\#\text{rollouts}\le B.$

(1)

The optimized ${𝒫}^{\ast }$ is then evaluated on a held-out test set ${𝒟}_{\text{test}}$. For the $i$-th input $x_i$, the system produces a sequence of intermediate inputs and outputs, where ${\hat{y}}_i^n={\pi }^n(x_i^n,p^n)$, $x_i^1=x_i$, ${\hat{y}}_i^N={\hat{y}}_i$, and $x_i^n$ for $n\ge 2$ is constructed from preceding agents’ outputs.

Textual Gradient

The textual gradient [11] is a natural-language analog of the numerical gradient used in gradient-based optimization. Following the formulation in TextGrad [9], the textual gradient with respect to a prompt $p$ is defined as

$\frac{\partial ℒ}{\partial p}={\text{LLM}}_{\nabla }(p,\hat{y},ℒ),$

(2)

where $ℒ$ is an objective, which may be either a non-differentiable function or a natural-language description of the failure, $\hat{y}$ is the prompt-conditioned output, and ${\text{LLM}}_{\nabla }$ is an LLM-based gradient extractor that produces a natural-language critique describing how $p$ should be modified to improve $ℒ$. A separate prompt optimizer LLM then aggregates sample-level textual gradients to produce an updated prompt. This extraction–aggregation procedure underlies a family of textual gradient methods [9, 14, 15]. Some recent works refer to this signal under different names — GEPA, for instance, calls it natural-language feedback [10] — but these methods share the same abstraction: a natural language description of how a prompt should be updated. We adopt textual gradient throughout this work to denote this signal.

4 Method

In this section, we present AgentGrad, a prompt optimization framework for multi-agent systems based on sequential intervention and semantic textual gradient abstraction. For the gradient extraction stage, we introduce sequential intervention, a mechanism that resolves the two limitations of this stage. Sequential intervention identifies the agent whose correction resolves a system-level failure (Section 4.1). The intervention-induced output then serves as an agent-level pseudo-label that supplies fine-grained supervision for textual gradient extraction (Section 4.2). For the gradient aggregation stage, we introduce semantic textual gradient abstraction (Section 4.3), which groups sample-level gradients into semantic minibatches sharing a corrective pattern and abstracts each cluster into a single textual gradient with improved generalizability. We provide the pseudocode of AgentGrad in algorithm 1.

媒体内容 · 前往原文查看

1: MAS $\Pi$, prompts $𝒫$, train/val sets ${𝒟}_{\text{train}},{𝒟}_{\text{val}}$, reward $r$, max reward $r_{\max }$, budget $B$, Hint $\mathscr{H}$

2: $r_{𝒫}(x,y):=r(\Pi (x,𝒫),y)$

3: $R_{𝒟}\left(𝒫\right):={𝔼}_{(x,y)\sim 𝒟}\left[r_{𝒫}(x,y)\right]$

4: $\text{Fail}(𝒫,𝒮):=\{(x,y)\in 𝒮:r_{𝒫}(x,y)<r_{\max }\}$

5: ${\text{Fail}}^{(n,\mathscr{H})}$ and $r_{𝒫}^{(n,\mathscr{H})}$ denote Fail and $r_{𝒫}$ after intervening on ${\pi }^n$ with hint $\mathscr{H}$

6: while rollout budget is not exhausted do

7: $ℱ\leftarrow \text{Fail}(𝒫,{𝒟}_{\text{train}})$

8: ${\Omega }^n\leftarrow \varnothing ,{ℱ}^{N+1}\leftarrow ℱ\forall n\in \{1,\dots ,N\}$

9: for$n=N,\dots ,1$do

10: ${ℱ}^n\leftarrow {\text{Fail}}^{(n,\mathscr{H})}(𝒫,{ℱ}^{n+1})$

11: ${𝒯}^n\leftarrow {ℱ}^{n+1}\setminus {ℱ}^n$

12: for each $(x_i,y_i)\in {𝒯}^n$do

13:       Obtain $(x_i^n,{\hat{y}}_i^n,{\tilde{y}}_i^n)$

14: ${\delta }_i^n\leftarrow {\text{LLM}}_{\nabla }(p^n,x_i^n,{\hat{y}}_i^n,{\tilde{y}}_i^n)$

15: ${\Omega }^n\leftarrow {\Omega }^n\cup \left\{{\delta }_i^n\right\}$

16: endfor

17: endfor

18: for each $n$do

19: ${\left\{{\overline{\delta }}_j^n\right\}}_{j=1}^{M_n}\leftarrow {\text{LLM}}_{\text{Aggregator}}\left({\Omega }^n\right)$$⊳$ with semantic minibatch ${𝒟}_j^n$ for each ${\overline{\delta }}_j^n$

20: endfor

21: for each $n,j$ in decreasing order of $\left|{𝒟}_j^n\right|$do

22: $p_{\text{new}}^n\leftarrow {\text{LLM}}_{\text{PromptOptimizer}}(p^n,{\overline{\delta }}_j^n)$

23: ${𝒫}_{\text{new}}\leftarrow 𝒫$ with $p^n$ replaced by $p_{\text{new}}^n$

24: if$R_{{𝒟}_j^n}\left({𝒫}_{\text{new}}\right)>R_{{𝒟}_j^n}\left(𝒫\right)$then

25: if$R_{{𝒟}_{\text{val}}}\left({𝒫}_{\text{new}}\right)>R_{{𝒟}_{\text{val}}}\left(𝒫\right)$then

26: $𝒫\leftarrow {𝒫}_{\text{new}}$

27: end if

28: end if

29: endfor

30: endwhile

31: return$𝒫$

4.1 Target Prompt Identification via Sequential Intervention

Our goal is to select the target prompt to update. We define the target prompt as the one whose correction alone is sufficient to resolve the failure. To this end, we identify the target prompt via sequential intervention, which modifies one agent at a time to verify whether its correction resolves the failure. An intervention modifies an agent’s behavior by injecting a hint into its prompt, guiding it toward a corrected intermediate output that leads the system to generate the correct output. Figure 2 illustrates the overall procedure of the sequential intervention.

Sequential Intervention.

Given the current prompt set $𝒫$ of $N$ agents, let $ℱ=\{(x_i,y_i)\mid r(\Pi (x_i,𝒫),y_i)<r_{\max }\}$ denote the set of failures from the training set ${𝒟}_{\text{train}}$, where $r$ is a reward function and $r_{\max }$ is the maximum reward value. For each failure $(x_i,y_i)\in ℱ$, we apply interventions one agent at a time in reverse execution order to identify the agent whose correction resolves it. Since we observed that failures tend to concentrate in later agents, this reverse order reduces the expected number of interventions. Starting with ${ℱ}^{N+1}=ℱ$, at step $n$ we inject hint $\mathscr{H}$ into agent ${\pi }^n$ by appending it to the agent’s current prompt. The appended hint guides the agent toward a corrected output; we denote the intervened MAS as ${\Pi }^{(n,\mathscr{H})}(x_i,𝒫)$. We define ${𝒯}^n$ as the subset of ${ℱ}^{n+1}$ resolved by intervening on ${\pi }^n$; for this subset, ${\pi }^n$ is identified as the target agent:

${𝒯}^n=\left\{(x_i,y_i)\in {ℱ}^{n+1}\right|r({\Pi }^{(n,\mathscr{H})}(x_i,𝒫),y_i)=r_{\max }\},$

(3)

where ${ℱ}^{n+1}$ denotes the failures still unresolved when the procedure reaches step $n+1$. The resolved failures ${𝒯}^n$ are then removed from the unresolved set (${ℱ}^n={ℱ}^{n+1}\setminus {𝒯}^n$), and the procedure proceeds to step $n$. Failures unresolved after step $n=1$ are treated as hard cases that cannot be resolved even with hint guidance, and are therefore excluded from the current training round. They are not permanently discarded: since $ℱ$ is reconstructed from ${𝒟}_{\text{train}}$ at the start of every round, these cases are revisited under the updated prompt set.

Hint Construction.

The hint $\mathscr{H}$ is designed to provide the necessary guidance to direct an agent toward correct behavior. We construct $\mathscr{H}$ from the ground-truth $y_i$ or from constraints that the final output must satisfy, together with auxiliary context such as descriptions of the dataset, the MAS, and each agent role—components commonly used in prior prompt optimization methods [7]. We emphasize that $\mathscr{H}$ is used only at training time; the optimized prompts are deployed without any hint injection at inference time.

4.2 Textual Gradient Extraction via Agent-Level Supervision

In this section, we describe textual gradient extraction using the target agent’s intervention-induced output as an agent-level pseudo-label. For each target agent ${\pi }^n$ and each failure sample $(x_i,y_i)\in {𝒯}^n$ attributed to it (Section 4.1), we have two outputs under the same input $x_i^n$: the original output ${\hat{y}}_i^n$ produced during the failed execution, and the corrected output ${\tilde{y}}_i^n$ obtained by injecting hint $\mathscr{H}$ during sequential intervention:

${\hat{y}}_i^n={\pi }^n(x_i^n,p^n),{\tilde{y}}_i^n={\pi }^n(x_i^n,p^n,\mathscr{H}).$

(4)

Since both ${\hat{y}}_i^n$ and ${\tilde{y}}_i^n$ are generated under the same input context $x_i^n$, their difference isolates the behavioral change induced by the intervention. We therefore interpret ${\tilde{y}}_i^n$ as an agent-level pseudo-label specifying how ${\pi }^n$ should behave under $x_i^n$. To extract a textual gradient, AgentGrad uses this pseudo-label as input to a gradient extractor LLM:

${\delta }_i^n={\mathrm{LLM}}_{\nabla }(p^n,x_i^n,{\hat{y}}_i^n,{\tilde{y}}_i^n),$

(5)

which captures how $p^n$ should be modified to produce ${\tilde{y}}_i^n$ instead of ${\hat{y}}_i^n$. We call ${\delta }_i^n$ a sample-level textual gradient, since it is derived from a single failure sample $(x_i,y_i)$ and describes the correction required for that instance alone. Unlike standard textual gradient methods — which require an explicit $ℒ$ derived from comparing the system-level output against the ground-truth — our gradient requires no explicit loss; the contrast between ${\hat{y}}_i^n$ and ${\tilde{y}}_i^n$ implicitly provides agent-level supervision. This agent-level supervision yields fine-grained update signals for the target agent.

4.3 Semantic Textual Gradient Abstraction

In this section, we introduce semantic textual gradient abstraction, which clusters semantically similar sample-level gradients into semantic minibatches and abstracts each minibatch into a single generalized textual gradient. Standard textual gradient methods aggregate sample-level gradients from random minibatches. Such minibatches often mix gradients from unrelated failure modes leaving the prompt optimizer without a coherent update direction. In contrast, semantic minibatches contain failures that share a common corrective pattern, providing a coherent update direction.

For each agent ${\pi }^n$, let ${\Omega }^n={\left\{{\delta }_i^n\right\}}_{(x_i,y_i)\in {𝒯}^n}$ denote the set of sample-level textual gradients extracted in Section 4.2 over all failures attributed to ${\pi }^n$. We employ an aggregator LLM that clusters ${\Omega }^n$ into semantic minibatches and abstracts each minibatch into a generalized textual gradient:

${\left\{{\overline{\delta }}_j^n\right\}}_{j=1}^{M_n}={\mathrm{LLM}}_{\text{Aggregator}}\left({\Omega }^n\right),$

(6)

where ${\overline{\delta }}_j^n$ denotes the $j$-th generalized gradient for agent ${\pi }^n$ and $M_n$ is the number of resulting clusters, which is determined by the aggregator LLM. We use a separate index $j$ to distinguish generalized gradients from sample-level gradients indexed by $i$. The aggregator LLM performs two coupled steps within a single call: clustering ${\Omega }^n$ into semantically coherent groups, and abstracting each group into a generalized gradient that captures its shared corrective pattern.

Clustering into Semantic Minibatches.

The aggregator LLM groups semantically similar sample-level gradients in ${\Omega }^n$. Each group induces a semantic minibatch ${𝒟}_j^n$: the training failures from which the sample-level gradients in that group were extracted. The size of each cluster determines the abstraction level: larger clusters yield more general patterns shared across many failures, while smaller clusters yield finer-grained corrections. To guide this abstraction level, we provide the aggregator with a soft lower bound on cluster size, which follows a cyclic schedule across optimization iterations (e.g., $5\to 3\to 1\to 5\to \dots$). This schedule encourages the aggregator to alternate between coarse, broadly-shared patterns and finer, more specific corrections over the course of training. The lower bound on cluster size is recommended rather than strictly enforced, allowing the aggregator to form smaller clusters when the gradients are too dissimilar to group.

Abstracting into Generalized Gradients.

For each cluster, the aggregator LLM produces a generalized textual gradient ${\overline{\delta }}_j^n$ that captures the shared corrective pattern of its semantic minibatch. This gives the prompt optimizer a single, coherent direction to follow rather than a mixture of diverse sample-level signals. The resulting generalized gradients $\left\{{\overline{\delta }}_j^n\right\}$ and their semantic minibatches $\left\{{𝒟}_j^n\right\}$ serve as the primary signal for prompt updates.

4.4 Prompt Update and Validation

Given the generalized gradients $\left\{{\overline{\delta }}_j^n\right\}$ from Section 4.3, we update agent prompts in decreasing order of semantic minibatch size, applying broader, high-influence updates before finer ones. A prompt optimizer LLM generates a candidate prompt $p_{\text{new}}^n$ using the generalized gradient ${\overline{\delta }}_j^n$ and the current prompt $p^n$:

$p_{\text{new}}^n={\mathrm{LLM}}_{\text{PromptOptimizer}}(p^n,{\overline{\delta }}_j^n).$

(7)

Each candidate prompt is first evaluated on the semantic minibatch ${𝒟}_j^n$; if performance improves, it is then evaluated on the held-out validation set ${𝒟}_{\text{val}}$. If both stages pass, we accept the update by replacing $p^n$ in $𝒫$ with $p_{\text{new}}^n$; otherwise, we discard it and proceed to the next gradient.

5 Experiment

5.1 Experimental Setup

We evaluate AgentGrad against three state-of-the-art prompt optimization algorithms—MIPROv2 [8], TextGrad [9], and GEPA [10]—and a no-optimization baseline across five MAS benchmarks: HotpotQA, HoVer, IFBench, PUPA, and MATH [25, 26, 27, 28, 29]. For HotpotQA, HoVer, PUPA, and IFBench, we adopt the multi-agent systems, data splits, and reward functions from [10]; for MATH, we adopt from [6]. We evaluate two LLM backbones, GPT-5-mini and Qwen3-8B [30], where the same backbone serves as both the task LLM and all optimizer components across all optimization algorithms.

5.2 Main Results

媒体内容 · 前往原文查看

GPT-5-mini	HotpotQA	HoVer	PUPA	IFBench	MATH	Improvement
Baseline (No PO)	46.33 $\pm$ 0.69	58.11 $\pm$ 1.01	84.74 $\pm$ 0.33	73.07 $\pm$ 0.60	76.48 $\pm$ 0.91	-
MIPROv2	59.00 $\pm$ 1.66	62.89 $\pm$ 1.34	88.33 $\pm$ 2.13	73.70 $\pm$ 0.86	83.13 $\pm$ 1.72	+5.66
TextGrad	67.89 $\pm$ 1.31	63.22 $\pm$ 1.47	89.72 $\pm$ 2.43	73.07 $\pm$ 0.60	76.48 $\pm$ 0.91	+6.33
GEPA	68.33 $\pm$ 1.55	63.11 $\pm$ 1.90	91.87 $\pm$ 1.55	75.23 $\pm$ 0.32	86.37 $\pm$ 0.50	+9.24
AgentGrad (Ours)	73.89 $\pm$ 1.09	64.78 $\pm$ 1.44	95.17 $\pm$ 0.49	76.08 $\pm$ 0.45	87.62 $\pm$ 0.09	+11.76

媒体内容 · 前往原文查看

Qwen3-8B	HotpotQA	HoVer	PUPA	IFBench	MATH	Improvement
Baseline (No PO)	41.33 $\pm$ 0.84	36.67 $\pm$ 1.02	80.87 $\pm$ 0.06	40.82 $\pm$ 1.99	83.24 $\pm$ 0.38	-
MIPROv2	58.33 $\pm$ 2.37	45.44 $\pm$ 0.68	85.76 $\pm$ 2.86	40.08 $\pm$ 2.21	84.68 $\pm$ 0.92	+6.27
TextGrad	50.86 $\pm$ 5.36	51.44 $\pm$ 0.78	84.50 $\pm$ 2.31	42.52 $\pm$ 0.45	83.90 $\pm$ 0.67	+6.06
GEPA	57.33 $\pm$ 2.54	50.11 $\pm$ 1.60	91.03 $\pm$ 1.71	37.53 $\pm$ 1.62	85.05 $\pm$ 0.48	+7.62
AgentGrad (Ours)	60.45 $\pm$ 1.68	52.11 $\pm$ 1.66	91.51 $\pm$ 0.72	41.42 $\pm$ 0.99	85.81 $\pm$ 0.25	+9.67

AgentGrad achieves state-of-the-art performance across five MAS benchmarks on both backbone settings. With GPT-5-mini in Table 1, AgentGrad outperforms all baselines on every benchmark, achieving an average improvement of $+11.76$ points over the no-optimization baseline, with the largest margins on HotpotQA ($73.89$ vs. $68.33$ for GEPA) and PUPA ($95.17$ vs. $91.87$). In Table 2, AgentGrad with Qwen3-8B achieves the largest average improvement of $+9.67$ points over the no-optimization baseline, surpassing all baselines. The consistent gains across both proprietary and open-source models, spanning multi-hop QA, claim verification, instruction following, privacy-conscious delegation, and math reasoning, demonstrate that sequential intervention and semantic textual gradient abstraction generalize across diverse task types and agent configurations.

5.3 Analysis

Ablation Studies.

媒体内容 · 前往原文查看

TI	AS	STGA	HotpotQA	PUPA
			67.89 $\pm$ 0.80	85.74 $\pm$ 1.65
✓			69.33 $\pm$ 0.38	89.58 $\pm$ 1.89
✓	✓		70.89 $\pm$ 0.62	92.23 $\pm$ 0.68
✓		✓	71.89 $\pm$ 0.29	93.13 $\pm$ 0.53
✓	✓	✓	73.89 $\pm$ 1.09	95.17 $\pm$ 0.49

媒体内容 · 前往原文查看

Table 3 presents an ablation study on HotpotQA and PUPA with GPT-5-mini, progressively adding each component of AgentGrad to a vanilla baseline. All three components contribute positively. Target identification (TI) using sequential-intervention alone yields $+1.44$ and $+3.84$ points on HotpotQA and PUPA, showing that identifying the responsible agent already produces more effective gradients. Adding agent-level supervision (AS) on top of TI yields a further $+1.56$ and $+2.65$ points, while semantic textual gradient abstraction (STGA) on top of TI contributes $+2.56$ and $+3.55$ points. The full model (AgentGrad) achieves the best performance on both benchmarks, confirming that TI, AS, and STGA address complementary aspects of the prompt optimization process.

Optimization Trajectory.

Figure 3 shows validation performance as a function of the number of rollouts on HotpotQA (GPT-5-mini). AgentGrad consistently dominates all baselines at every rollout count on both benchmarks. On HotpotQA, AgentGrad achieves approximately $70\%$ by $\mathrm{1,000}$ rollouts, while GEPA requires over $\mathrm{6,000}$ rollouts to approach a comparable level, and MIPROv2 and TextGrad plateau below this threshold. AgentGrad’s confidence bands are also notably narrow, reflecting more stable optimization across seeds, and the performance gap is maintained rather than narrowing with additional rollouts.

Wall-clock Time Comparison.

媒体内容 · 前往原文查看

Method	HotpotQA	HoVer	PUPA	IFBench	MATH	Avg. $\downarrow$
MIPROv2	501	1226	304	581	431	608
TextGrad	899	1553	325	332	126	647
GEPA	346	390	319	269	360	337
AgentGrad (Ours)	109	244	151	90	88	136
AgentGrad vs. next-best	$3.2\times$	$1.6\times$	$2.0\times$	$3.0\times$	$1.4\times$	$2.5\times$

Table 4 reports wall-clock optimization time on five benchmarks with GPT-5-mini. AgentGrad is the fastest method across all five benchmarks without exception, completing optimization in $136$ minutes on average — $2.5\times$ faster than GEPA, the next-fastest baseline, and $4.7\times$ faster than TextGrad. The speedup is most pronounced on HotpotQA ($3.2\times$ over GEPA) and IFBench ($3.0\times$), where AgentGrad finishes in under two hours while GEPA requires nearly six. Even on MATH, where TextGrad is unusually fast at $126$ minutes, AgentGrad completes in just $88$ minutes. Notably, AgentGrad achieves these speedups while simultaneously attaining the best task performance (Table 1), demonstrating that the two objectives — optimization quality and efficiency — are not in tension but are jointly improved by agent-level gradient signals.

Why AgentGrad Optimizes Faster and Generalizes Better.

Figure 4(a–b) compares minibatch and validation improvement ratios against GEPA and TextGrad, averaged over HotpotQA and PUPA. AgentGrad achieves a minibatch improvement ratio of $0.72$ versus $0.44$ for TextGrad and $0.28$ for GEPA. Since validation is triggered only when a candidate improves the minibatch, this higher ratio directly translates into more rollout usages per unit time, explaining AgentGrad’s wall-clock speedup. This efficiency does not come at the cost of quality: AgentGrad also achieves the highest validation improvement ratio ($0.27$ vs. $0.21$ and $0.14$), indicating that its accepted updates generalize more reliably. Figure 4(c–d) isolates each component’s contribution. TI and AS primarily raise the minibatch ratio (from $0.51$ to $0.87$), improving per-sample gradient signal quality, while STGA trades a modest minibatch ratio reduction for a gain in validation ratio, improving generalizability — yielding a clear division of roles among the three components.

媒体内容 · 前往原文查看

Source	HotpotQA	HoVer	PUPA	IFBench	MATH
Target	2WikiMultiHopQA	EX-FEVER	PUPA-TNB	IFEval	OlympiadBench
Baseline (No PO)	24.33 $\pm$ 0.00	30.00 $\pm$ 0.00	88.40 $\pm$ 0.27	91.22 $\pm$ 0.11	59.33 $\pm$ 0.00
MIPROv2	31.11 $\pm$ 4.81	32.89 $\pm$ 0.25	90.56 $\pm$ 2.20	91.70 $\pm$ 0.82	63.56 $\pm$ 2.92
TextGrad	36.22 $\pm$ 5.43	32.67 $\pm$ 1.49	89.60 $\pm$ 1.20	91.22 $\pm$ 0.11	59.33 $\pm$ 0.00
GEPA	44.89 $\pm$ 4.96	31.44 $\pm$ 0.82	91.51 $\pm$ 3.11	93.15 $\pm$ 0.47	66.00 $\pm$ 1.43
AgentGrad (Ours)	51.22 $\pm$ 1.63	33.11 $\pm$ 0.31	94.38 $\pm$ 0.83	95.00 $\pm$ 0.72	68.33 $\pm$ 1.21

Transferability of Optimized Prompts.

Table 5 evaluates whether optimized prompts remain effective on an unseen benchmark from the same domain [46, 47, 28, 48, 49], without any further optimization. AgentGrad achieves the best transfer performance on all five target benchmarks compared to strong prompt optimization algorithms. The margin over the next-best method is largest on 2WikiMultiHopQA (51.22 vs. 44.89 for GEPA) and PUPA-TNB (94.38 vs. 91.51). Together with the in-domain results (Tables 1,  2) and the optimization time comparison (Table 4), this shows that AgentGrad’s gains are not confined to the benchmark it was optimized on: the same prompts remain the strongest on unseen benchmarks within the domain.

Qualitative Results.

Figure 5 illustrates how AgentGrad abstracts sample-level gradients into an abstracted gradient. The target agent is asked to rewrite a private user query while replacing sensitive tokens with clear placeholders. However, the original outputs in red still reveal identifiers such as PTV News, Warsaw, Poland, and Mishaali Kapoor. Through intervention, AgentGrad obtains improved outputs, where sensitive tokens are correctly replaced with placeholders in green. By comparing the failed output with the intervention-adjusted output, AgentGrad extracts sample-level gradients that specify how the target agent prompt should be updated. Rather than using these gradients independently, AgentGrad clusters gradients with similar corrective signals and abstracts each cluster into a coherent update direction. In this example, the first three samples share the signal that names and locations identifying a person, organization, or place should be treated as sensitive. Their sample-level gradients are therefore abstracted into a generalized gradient and used to update the agent prompt in a more reliable and generalizable direction.

6 Conclusion

We propose AgentGrad, a prompt optimization framework for multi-agent systems that addresses systematic limitations in two stages of existing textual gradient approaches: gradient extraction and gradient aggregation. AgentGrad introduces sequential intervention, which identifies the agent responsible for each failure and produces an agent-level pseudo-label as fine-grained supervision for gradient extraction. Next, AgentGrad introduces semantic textual gradient abstraction, which clusters sample-level gradients into semantic minibatches sharing a corrective pattern and abstracts each cluster into a single generalized gradient with improved generalizability. Across five MAS benchmarks spanning multi-hop QA, claim verification, instruction following, privacy-conscious delegation, and math reasoning, AgentGrad achieves state-of-the-art performance with both GPT-5-mini and Qwen3-8B, outperforming MIPROv2, TextGrad, and GEPA while reducing wall-clock optimization time by 2.5× on average over the next-fastest baseline. It shows that sequential intervention-based target prompt identification, agent-level supervision, and textual gradient abstraction are effective for prompt optimization.

References

• [1] Q. Wu, G. Bansal, J. Zhang, Y. Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, et al. (2024) Autogen: enabling next-gen llm applications via multi-agent conversations. In COLM, Cited by: §1.
• [2] G. Li, H. Hammoud, H. Itani, D. Khizbullin, and B. Ghanem (2023) Camel: communicative agents for" mind" exploration of large language model society. In NeurIPS, Cited by: §1.
• [3] S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, J. Wang, C. Zhang, Z. Wang, S. K. S. Yau, Z. Lin, et al. (2023) MetaGPT: meta programming for a multi-agent collaborative framework. In ICLR, Cited by: §1.
• [4] C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, et al. (2024) Chatdev: communicative agents for software development. In ACL, Cited by: §1.
• [5] M. A. Islam, M. E. Ali, and M. R. Parvez (2024) Mapcoder: multi-agent code generation for competitive problem solving. In ACL, Cited by: §1.
• [6] B. Lei, Y. Zhang, S. Zuo, A. Payani, and C. Ding (2024) Macm: utilizing a multi-agent system for condition mining in solving complex mathematical problems. In NeurIPS, Cited by: §1, §5.1.
• [7] O. Khattab, A. Singhvi, P. Maheshwari, Z. Zhang, K. Santhanam, S. Vardhamanan, S. Haq, A. Sharma, T. T. Joshi, H. Moazam, et al. (2024) Dspy: compiling declarative language model calls into self-improving pipelines. In ICLR, Cited by: §1, §2, §4.1.
• [8] K. Opsahl-Ong, M. J. Ryan, J. Purtell, D. Broman, C. Potts, M. Zaharia, and O. Khattab (2024) Optimizing instructions and demonstrations for multi-stage language model programs. In EMNLP, Cited by: §1, §2, §3, §5.1.
• [9] M. Yuksekgonul, F. Bianchi, J. Boen, S. Liu, Z. Huang, C. Guestrin, and J. Zou (2024) Textgrad: automatic" differentiation" via text. arXiv preprint arXiv:2406.07496. Cited by: §1, §1, §1, §2, §3, §3, §5.1.
• [10] L. A. Agrawal, S. Tan, D. Soylu, N. Ziems, R. Khare, K. Opsahl-Ong, A. Singhvi, H. Shandilya, M. J. Ryan, M. Jiang, et al. (2026) Gepa: reflective prompt evolution can outperform reinforcement learning. In ICLR, Cited by: §1, §1, §1, §2, §3, §3, §5.1.
• [11] R. Pryzant, D. Iter, J. Li, Y. Lee, C. Zhu, and M. Zeng (2023) Automatic prompt optimization with “gradient descent” and beam search. In EMNLP, Cited by: §1, §1, §2, §3.
• [12] C. Yang, X. Wang, Y. Lu, H. Liu, Q. V. Le, D. Zhou, and X. Chen (2023) Large language models as optimizers. In ICLR, Cited by: §1, §2.
• [13] Y. Zhou, A. I. Muresanu, Z. Han, K. Paster, S. Pitis, H. Chan, and J. Ba (2022) Large language models are human-level prompt engineers. In ICLR, Cited by: §1, §2.
• [14] P. Sharma and A. Z. Henley (2026) Modular prompt optimization: optimizing structured prompts with section-local textual gradients. arXiv preprint arXiv:2601.04055. Cited by: §1, §1, §3.
• [15] A. Cui, P. Nandyalam, A. Rufail, E. Cheung, A. Lei, K. Zhu, and S. O’Brien (2024) Introducing mapo: momentum-aided gradient descent prompt optimization. arXiv preprint arXiv:2410.19499. Cited by: §1, §1, §3.
• [16] S. Zhang, M. Yin, J. Zhang, J. Liu, Z. Han, J. Zhang, B. Li, C. Wang, H. Wang, Y. Chen, et al. (2025) Which agent causes task failures and when? on automated failure attribution of llm multi-agent systems. In ICML, Cited by: §1, §2.
• [17] G. Zhang, J. Wang, J. Chen, W. Zhou, K. Wang, and S. Yan (2026) AgenTracer: who is inducing failure in the llm agentic systems?. In ICLR, Cited by: §1, §2.
• [18] Y. Wang, W. Wu, J. Wang, and Q. Wang (2026) From flat logs to causal graphs: hierarchical failure attribution for llm-based multi-agent systems. arXiv preprint arXiv:2602.23701. Cited by: §1, §2.
• [19] Y. In, M. Tanjim, J. Subramanian, S. Kim, U. Bhattacharya, W. Kim, S. Park, S. Sarkhel, and C. Park (2026) Rethinking failure attribution in multi-agent systems: a multi-perspective benchmark and evaluation. arXiv preprint arXiv:2603.25001. Cited by: §1, §2.
• [20] M. Chen, J. Wang, F. Mu, Y. Wang, Z. Liu, H. Feng, and Q. Wang (2026) Seeing the whole elephant: a benchmark for failure attribution in llm-based multi-agent systems. In ACL, Cited by: §1, §2.
• [21] M. Li, K. Aggarwal, Y. Xie, A. Ahmad, and S. Lau (2024) Learning from contrastive prompts: automated optimization and adaptation. arXiv preprint arXiv:2409.15199. Cited by: §1.
• [22] F. Jiao, G. Guo, X. Zhang, N. F. Chen, S. Joty, and F. Wei (2025) Preference optimization for reasoning with pseudo feedback. In ICLR, Cited by: §1, §2.
• [23] X. Lin, Z. Dai, A. Verma, S. Ng, P. Jaillet, and B. K. H. Low (2024) Prompt optimization with human feedback. arXiv preprint arXiv:2405.17346. Cited by: §1.
• [24] Z. Ding, J. Hong, Z. Shi, J. T. Wang, Z. Lin, L. Yin, M. Liu, Z. Wang, and Y. Chen (2025) Scaling textual gradients via sampling-based momentum. In ICML Workshop, Cited by: §1.
• [25] Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. Cohen, R. Salakhutdinov, and C. D. Manning (2018) HotpotQA: a dataset for diverse, explainable multi-hop question answering. In EMNLP, Cited by: §1, §5.1.
• [26] Y. Jiang, S. Bordia, Z. Zhong, C. Dognin, M. Singh, and M. Bansal (2020) HoVer: a dataset for many-hop fact extraction and claim verification. In EMNLP Findings, Cited by: §1, §5.1.
• [27] V. Pyatkin, S. Malik, V. Graf, H. Ivison, S. Huang, P. Dasigi, N. Lambert, and H. Hajishirzi (2025) Generalizing verifiable instruction following. In NeurIPS Datasets and Benchmarks Track, Cited by: §1, §5.1.
• [28] L. Siyan, V. C. Raghuram, O. Khattab, J. Hirschberg, and Z. Yu (2025) Papillon: privacy preservation from internet-based and local language model ensembles. In NAACL, Cited by: §1, §5.1, §5.3.
• [29] D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt (2021) Measuring mathematical problem solving with the MATH dataset. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, External Links: Link Cited by: §1, §5.1.
• [30] A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. (2025) Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §1, §5.1.
• [31] OpenAI (2026) GPT-5 mini Model. Note: https://developers.openai.com/api/docs/models/gpt-5-miniAccessed: 2026-05-07 Cited by: §1.
• [32] K. Ramnath, K. Zhou, S. Guan, S. S. Mishra, X. Qi, Z. Shen, S. Wang, S. Woo, S. Jeoung, Y. Wang, et al. (2025) A systematic survey of automatic prompt optimization techniques. In EMNLP, Cited by: §2.
• [33] J. Chu, S. Lee, and H. J. Kim (2026) PRESTO: preimage-informed instruction optimization for prompting black-box llms. NeurIPS. Cited by: §2.
• [34] A. Prasad, P. Hase, X. Zhou, and M. Bansal (2023) Grips: gradient-free, edit-based instruction search for prompting large language models. In EACL, Cited by: §2.
• [35] Q. Guo, R. Wang, J. Guo, B. Li, K. Song, X. Tan, G. Liu, J. Bian, and Y. Yang (2024) Evoprompt: connecting llms with evolutionary algorithms yields powerful prompt optimizers. In ICLR, Cited by: §2.
• [36] P. I. Frazier (2018) A tutorial on bayesian optimization. arXiv preprint arXiv:1807.02811. Cited by: §2.
• [37] J. Chu, J. Park, S. Lee, and H. J. Kim (2024) Inversion-based latent bayesian optimization. NeurIPS. Cited by: §2.
• [38] S. Lee, J. Chu, S. Kim, J. Ko, and H. J. Kim (2023) Advancing bayesian optimization via learning correlated latent space. NeurIPS. Cited by: §2.
• [39] K. Nagpal, D. Dong, J. Bouvier, and N. Mehr (2025) Leveraging large language models for effective and explainable multi-agent credit assignment. In AAMAS, Cited by: §2.
• [40] Y. Yu, M. Li, S. Xu, J. Fu, X. Hou, F. Lai, and B. Wang (2025) CORRECT: condensed error recognition via knowledge transfer in multi-agent systems. arXiv preprint arXiv:2509.24088. Cited by: §2.
• [41] W. Epperson, G. Bansal, V. C. Dibia, A. Fourney, J. Gerrits, E. Zhu, and S. Amershi (2025) Interactive debugging and steering of multi-agent ai systems. In CHI, Cited by: §2.
• [42] M. Ma, J. Zhang, F. Yang, Y. Kang, Q. Lin, S. Rajmohan, and D. Zhang (2026) DoVer: intervention-driven auto debugging for llm multi-agent systems. In ICLR, Cited by: §2.
• [43] E. Zelikman, Y. Wu, J. Mu, and N. Goodman (2022) Star: bootstrapping reasoning with reasoning. In NeurIPS, Cited by: §2.
• [44] N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao (2023) Reflexion: language agents with verbal reinforcement learning. In NeurIPS, Cited by: §2.
• [45] A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, et al. (2023) Self-refine: iterative refinement with self-feedback. In NeurIPS, Cited by: §2.
• [46] X. Ho, A. D. Nguyen, S. Sugawara, and A. Aizawa (2020) Constructing a multi-hop qa dataset for comprehensive evaluation of reasoning steps. In COLING, Cited by: §5.3.
• [47] H. Ma, W. Xu, Y. Wei, L. Chen, L. Wang, Q. Liu, and S. Wu (2024) EX-fever: a dataset for multi-hop explainable fact verification. In ACL Findings, Cited by: §5.3.
• [48] J. Zhou, T. Lu, S. Mishra, S. Brahma, S. Basu, Y. Luan, D. Zhou, and L. Hou (2023) Instruction-following evaluation for large language models. arXiv preprint arXiv:2311.07911. Cited by: §5.3.
• [49] C. He, R. Luo, Y. Bai, S. Hu, Z. Thai, J. Shen, J. Hu, X. Han, Y. Huang, Y. Zhang, et al. (2024) Olympiadbench: a challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems. In ACL, Cited by: §5.3.