Technical Summary: Gradient-Based Connections (GBC) for Optimizing Multi-Agent Systems

1. Problem Statement

Multi-agent systems (MAS) built on Large Language Models (LLMs) offer a promising framework for solving complex tasks through role specialization and structured interaction. However, their performance is frequently hindered by miscoordination and, more fundamentally, a lack of fine-grained credit assignment.

Existing optimization approaches typically rely on coarse-grained feedback signals (e.g., overall task success or global rewards). This makes it difficult to identify which specific agents, interaction steps, or token-level outputs are responsible for errors. Consequently, both manual debugging and automatic optimization are limited in effectiveness. While recent work has introduced gradient-inspired methods for single-agent prompt optimization, these do not explicitly address the attribution challenges inherent in multi-agent settings where errors propagate through complex interaction graphs.

2. Methodology: Gradient-Based Connections (GBC)

The authors propose Gradient-Based Connections (GBC), a framework that models a multi-agent system as a directed computational graph to enable token-level attribution and optimization. The framework consists of four core components:

2.1 Agent Graph Modeling

The system is modeled as a directed acyclic graph $G = (V, E)$, where each node $v$ represents an agent defined by a prompt-model pair $(P_v, M_v)$. Edges represent information flow, where the input to an agent is the concatenation of its prompt and the outputs of its predecessor agents. Agents are executed in topological order.

2.2 Gradient-Based Connections

To quantify the influence of each agent's output on downstream agents, GBC introduces connection weights computed via gradient-based signals. For an output $O_v$ and a predecessor output $O_u$, the connection weight $W_{O_v}(O_u)$ is calculated using one of four variants:

1. Mean of L1 Norm: Aggregates token-level salience scores via gradients.
2. Max of L1 Norm: Emphasizes the most influential tokens to reduce noise.
3. Mean of Product with Input: Captures first-order contributions via gradient-input interactions.
4. Max of Product with Input: Combines gradient-input interactions with an emphasis on influential tokens.

Based on these weights, an attribution graph is constructed by retaining the top-$m$ predecessors for each node, effectively pruning irrelevant connections.

2.3 Verbal Loss and Backward Propagation

A task-specific verbal loss is attached to the final output. This loss encodes correctness and quality signals (e.g., comparisons with ground truth or explanations) in natural language. The framework then propagates this loss backward through the attribution graph to extract attribution trajectories. These trajectories trace the contribution of specific inputs or intermediate outputs to the final loss, identifying the components most responsible for errors.

2.4 Optimizer and AgentChord

The authors introduce AgentChord, a practical implementation that integrates GBC with a language-model-based optimizer. The optimizer uses the current prompts, attribution trajectories, and optimization history to iteratively refine agent prompts.

Scalability Optimization: To address the memory overhead of backpropagation through LLMs, AgentChord employs a prefix-based gradient computation strategy. Since attribution is computed only with respect to the input tokens (while prompts are treated as a fixed prefix), gradients are calculated only for the input portion. This reduces memory complexity from $O(n \cdot d \cdot L)$ to $O((n-k) \cdot d \cdot L)$, where $k$ is the prompt length.

3. Key Contributions

The paper claims the following contributions:

• Gradient-Based Connections (GBC): A novel method for token-level attribution across agents using gradient-based signals, addressing the lack of fine-grained credit assignment in MAS.
• AgentChord: A scalable framework for optimizing multi-agent systems using attribution-guided updates, featuring efficient prefix-based gradient computation.
• Empirical Validation: Demonstration of the approach's effectiveness on multiple benchmarks (MultiWOZ and $\tau$-bench), showing improvements over both single-agent and unoptimized multi-agent baselines.

4. Experimental Results

The authors evaluated GBC on two benchmarks: MultiWOZ (task-oriented dialogue) and $\tau$-bench (interactive tool-use).

4.1 MultiWOZ Results

• Performance Gains: Before optimization, multi-agent systems did not consistently outperform strong single-agent baselines (e.g., Qwen-3-32B multi-agent had lower Joint Goal Accuracy (JGA) than the single agent). After optimization with GBC, performance improved significantly.
• Specific Metrics: Using the "Mean of L1 Norm" connection weight, the Qwen-3-32B multi-agent system improved JGA from 28.9 to 54.4 and Slot F1 from 79.3 to 91.4, surpassing the single-agent baseline across Inform, Success, JGA, and Slot F1 metrics.
• Attribution Quality: Analysis revealed a strong correlation between attribution accuracy and optimization effectiveness. Connection weights based on L1 norms (Mean/Max) yielded the highest attribution accuracy and the best task performance.
• Error Analysis: Optimization primarily reduced cross-domain errors, information omission, and over-prediction, indicating improved coordination and state tracking.

4.2 $\tau$-bench Results

• Performance Gains: Optimization consistently improved multi-agent performance. The "Max of L1 Norm" variant improved the overall reward for Qwen-3-32B from 13.0 to 24.3, surpassing the strong single-agent baseline of 22.6.
• Error Analysis: The dominant errors were retrieval/identification failures and tool misuse. GBC helped mitigate these by improving the grounding of user intent and tool selection across turns.

5. Significance and Claims

The paper positions GBC as a principled mechanism for diagnosing and improving multi-agent coordination. Its significance lies in:

• Shifting from Coarse to Fine-Grained: Moving beyond global reward signals to token-level attribution allows for precise identification of error sources within complex agent workflows.
• Enabling Optimization: By modeling MAS as computational graphs and propagating verbal loss signals, the method makes it possible to automatically optimize agent prompts in a targeted manner.
• Scalability: The prefix-based gradient computation makes gradient-based attribution feasible for large language models, overcoming previous memory constraints.
• Correlation of Attribution and Performance: The empirical finding that higher attribution quality leads to greater optimization effectiveness suggests that accurate error localization is a critical prerequisite for improving multi-agent systems.

6. Limitations

The authors acknowledge several limitations:

• Computational Cost: Despite memory optimizations, the requirement for multiple forward and backward passes remains expensive compared to black-box methods.
• Dependence on Verbal Loss: The effectiveness of the method relies heavily on the design and quality of the task-specific verbal loss function.
• First-Order Approximation: The gradient-based approach approximates influence linearly and may not fully capture complex non-linear interactions in highly entangled workflows.
• Generalization: Results are currently validated on specific benchmarks (MultiWOZ, $\tau$-bench) and architectures (manager-worker); generalization to other domains (e.g., code generation, open-ended reasoning) requires further validation.
• Persistent Errors: Some error types (e.g., cross-domain errors, retrieval failures) persist even after optimization, suggesting intrinsic task difficulties or LLM limitations beyond attribution.