PaperlayerView exact revision on arXiv

Source-linked AI summary

GBC: Gradient-Based Connections for Optimizing Multi-Agent Systems

Xiaocheng Yang, Abdulrahman Alrabah, Dilek Hakkani-Tür, Gokhan Tur

arXiv:2606.28187v1cs.MA

TL;DR

Multi-agent systems lack fine-grained credit assignment for errors across agents and interaction steps. GBC models workflows as computational graphs and uses token-level gradient attribution to optimize prompts, improving performance across MultiWOZ and τ-bench and sometimes matching or surpassing strong single-agent baselines.

  • Problem

    Existing multi-agent optimization methods rely on global feedback and lack fine-grained attribution of errors to tokens, reasoning steps, or interacting components.

  • Method

    GBC models multi-agent workflows as computational graphs and uses token-level gradient signals to attribute intermediate outputs, while AgentChord applies attribution-guided prompt refinement.

  • Results

    GBC consistently improves multi-agent performance across MultiWOZ and τ-bench metrics, in many cases matching or surpassing strong single-agent baselines.

  • Takeaways & Limitations

    Higher attribution quality is associated with greater optimization effectiveness, while GBC provides a mechanism for diagnosing and improving multi-agent coordination.

  • Takeaways & Limitations

    Gradient-based attribution requires multiple LLM forward and backward passes, making GBC expensive compared with black-box methods and limiting scalability.

Abstract

from arXiv · show

Multi-agent systems (MAS) built on large language models (LLMs) provide a promising framework for solving complex tasks through role specialization and structured interaction. However, their performance is often limited by miscoordination and, more fundamentally, the lack of fine-grained credit assignment across agents. Existing approaches typically rely on coarse-grained feedback, making it difficult to identify which agents or interaction steps are responsible for errors. We propose Gradient-Based Connections (GBC), an approach for fine-grained attribution and optimization of multi-agent systems. GBC models a MAS as a computational graph and introduces gradient-based connection weights to quantify the influence of each agent's output on downstream agents at the token level. By constructing an attribution graph and propagating task-specific loss signals backward, our method enables precise identification of error sources and targeted prompt optimization. We further develop AgentChord, an efficient implementation that leverages prefix-based gradient computation. Experiments on MultiWOZ and τ-bench show that GBC improves multi-agent performance and outperforms strong single-agent and multi-agent baselines, and higher attribution quality is associated with greater optimization effectiveness. Code is available at: https://github.com/yxc-cyber/AgentChord.

1 Introduction

Multi-agent systems show promise for complex tasks but often suffer from miscoordination and coarse-grained credit assignment that obscures which agents or interaction steps cause errors. GBC addresses these limitations with token-level attribution and targeted prompt optimization, while AgentChord provides a scalable implementation evaluated on MultiWOZ and τ-bench.

  • Multi-agent systems often fail to consistently outperform strong single-agent baselines because of miscoordination, inefficient communication, and weak verification.
  • Existing optimization methods rely on coarse-grained task signals, making it difficult to identify which agents or interaction steps caused errors.
  • GBC models multi-agent systems as directed computational graphs and quantifies each agent’s influence on subsequent agents through token-level gradient-based connections.
  • GBC propagates task-specific verbal loss signals backward through an attribution graph to identify error sources and target agent-prompt optimization.
  • AgentChord integrates GBC with a language-model optimizer, using prefix-based gradient computation to reduce backpropagation memory overhead and scaling evaluation across MultiWOZ and τ-bench.

2 Related Work

Prior work optimizes prompts and multi-agent systems using black-box search, textual feedback, evolutionary search, or structured coordination, but typically relies on coarse-grained signals. These approaches lack fine-grained attribution across tokens, reasoning steps, agents, and interactions, motivating GBC’s token-level credit assignment framework.

  • Prompt optimization: Automatic prompt optimization uses LLMs as generators and evaluators in iterative black-box search guided by coarse-grained performance signals.Early methods formulate prompt design as natural-language candidate generation and evaluation.
  • Prompt optimization: Gradient-inspired methods use textual feedback or computation-graph propagation to refine prompts and optimize LLM-based systems.Pro-TeGi follows textual gradients, while TextGrad propagates feedback across components and prompt variables.
  • Prompt optimization: Evolutionary methods such as GAAPO and GEPA explore diverse prompt candidates through genetic mutation and selection.These approaches complement gradient-inspired optimization with population-based search.
  • Limitations and motivation: Existing approaches optimize single-agent prompts or multi-agent coordination with global feedback, lacking fine-grained attribution of errors to tokens, steps, agents, or interactions.This limitation contributes to weak credit assignment amid misalignment, inefficient coordination, and difficult error-source identification; GBC addresses it with token-level attribution across agents.
  • Multi-agent systems: LLM-based multi-agent systems coordinate complex workflows through role specialization, task decomposition, communication, and structured computational-graph or dependency-graph architectures.Frameworks including AutoGen and ChatDev support role-based collaboration, while graph-based designs organize information flow and task execution.

3 Method

GBC models a multi-agent system as a directed acyclic agent graph, builds a gradient-based attribution graph, and propagates task-specific loss signals backward to identify contributions. An optimizer then uses attribution trajectories and optimization history to update agent prompts.

  • Framework: GBC decomposes optimization into an agent graph, gradient-based connections, a task-specific loss, and an optimizer.The forward graph produces a final output through sequential agent interactions.
  • Agent graph: Each agent is a prompt–model pair in a directed acyclic graph, with edges representing information flow between predecessor outputs and successor inputs.Agents execute in topological order, and the last agent produces the final output.
  • Attribution graph: Gradient-based connections assign predecessor-output weights and retain the top-m predecessors to form an attribution graph.The method considers mean/max variants of L1 norms and gradient–input products, using m = 1 by default.
  • Loss and backward attribution: A task-specific verbal loss encodes correctness and quality signals, including fine-grained feedback such as ground-truth comparisons or explanations.The loss is attached to the attribution graph to guide optimization.
  • Loss and backward attribution: The loss is backpropagated through the attribution graph to produce trajectories, which a language-model optimizer uses with current prompts and optimization history to update agent prompts.Trajectories trace contributions from inputs or intermediate outputs to the loss.

4 AgentChord

AgentChord is a practical framework for multiagent prompt optimization using Gradient-Based Connections. It improves scalability through prefix-based gradient computation that avoids storing gradients for prompt tokens.

  • AgentChord is a practical framework for multiagent prompt optimization using Gradient-Based Connections.
  • Prefix-based gradient computation reduces memory overhead by treating prompt tokens as a fixed prefix and computing gradients only for input tokens.Attribution is computed only with respect to the input, so gradients are required only for input tokens.
  • The implementation first processes the prompt without gradients to obtain the KV cache, then processes the input with gradients enabled.This avoids storing gradients for prompt tokens.

5 Experiment

GBC is evaluated on MultiWOZ task-oriented dialogue and τ-bench interactive tool use using manager–worker multi-agent systems. Optimization improves performance across both benchmarks, while attribution and error analyses identify domain-specific coordination and grounding as key factors.

  • Experimental Setup: GBC is evaluated on MultiWOZ 2.4 using 100 dialogues sampled from five domains and on τ-bench’s retail domain.MultiWOZ measures dialogue and slot-level performance, while τ-bench evaluates multi-step tool use.
  • MultiWOZ Results: On MultiWOZ, GBC improves most metrics, with an optimized variant reaching 99.0 Inform, 95.0 Success, 53.0 JGA, and 91.3 Slot F1.The optimized systems substantially outperform the Qwen-3-32B single-agent baseline on these metrics.
  • Error Analysis: MultiWOZ errors are dominated by cross-domain errors, information omission, and over-prediction, indicating coordination and dialogue-state tracking failures.Cross-domain errors particularly implicate imperfect manager–worker routing across multiple domains.
  • Update and Attribution Analysis: Domain-specific workers are updated more frequently than manager or responder agents, matching the observed MultiWOZ error patterns.Attribution quality is highest for mean and max L1 norm, which also produce the best MultiWOZ metrics.
  • τ-bench Results: On τ-bench, max of L1 norm raises Qwen-3-32B overall reward from 13.0 to 24.3, surpassing the strong single-agent baseline of 22.6.Mean of product with input also reaches 24.3 overall reward, driven by action reward increasing from 13.9 to 27.0.
  • τ-bench Error Analysis: In τ-bench, grounding failures dominate because successful completion requires resolving the correct user, order, and task state across multiple turns.Tool misuse also contributes to failures, showing that action selection remains important.

6 Conclusion

The paper introduces GBC for token-level, cross-agent attribution and optimization by modeling multi-agent workflows as computational graphs. It also presents AgentChord, which makes attribution-guided prompt refinement feasible for large language models and improves multi-agent performance on MultiWOZ and τ-bench.

  • 6 Conclusion: GBC models multi-agent workflows as computational graphs and uses token-level gradient signals to identify how intermediate outputs influence downstream decisions.This addresses the lack of effective credit assignment across agents.
  • 6 Conclusion: AgentChord combines attribution-guided feedback with iterative prompt refinement through prefix-based gradient computation.The strategy makes gradient-based attribution feasible for large-scale language models.
  • 6 Conclusion: GBC consistently improves multi-agent performance across multiple metrics on MultiWOZ and τ-bench, in many cases matching or surpassing strThe supplied passage truncates the comparison target after “surpassing str.”
  • 6 Conclusion: The work emphasizes token-level, cross-agent credit assignment as important for advancing interpretable and optimizable multi-agent architectures.The authors present GBC as a general and extensible approach for future research.

Limitations

GBC remains limited by computational cost, dependence on verbal loss design, first-order influence approximations, and uncertain generalization beyond evaluated settings. Some error types also persist after optimization, while future work targets efficiency, loss design, reinforcement learning, and adaptive topologies.

  • Computational cost: Gradient-based attribution requires multiple LLM forward and backward passes, limiting scalability to larger systems or longer interaction horizons.Prefix-based optimization reduces memory overhead but remains more expensive than purely black-box methods.
  • Verbal loss design: GBC’s effectiveness depends on task-specific verbal loss functions accurately capturing fine-grained errors; poor signals can produce noisy attribution and weaker optimization.The loss is expressed in natural language, making its quality and design central to attribution reliability.
  • Influence approximation: Token-level attribution uses a first-order influence approximation that may miss complex nonlinear interactions in long, multi-turn, or highly entangled workflows.Gradient-based signals do not fully capture all interactions between agents.
  • Generalization: Experiments cover MultiWOZ, τ-bench, and selected architectures such as manager–worker systems, leaving generalization to other domains and large-scale autonomous systems unvalidated.Open-ended reasoning and code generation are examples of settings requiring further validation.
  • Persistent errors: Cross-domain errors, information omission, and retrieval failures persist after optimization, potentially reflecting intrinsic task difficulty or current LLM limitations.These residual errors may not be attributable solely to the optimization method.
  • Future directions: Future work may investigate efficient gradient approximations, improved verbal loss design, reinforcement-learning integration, and dynamic or adaptive multi-agent topologies.These directions address the approach’s efficiency, attribution, and system-design limitations.

A Experiment Setting Detail · B Verbal Loss Prompts

The experiments use a fixed four-GPU compute setup with GPT-4 for prompt refinement, while verbal-loss prompts tailor feedback to MultiWOZ and τ-bench evaluation signals. MultiWOZ prompts compare predicted and ground-truth dialogue information, whereas τ-bench prompts compare actions and required response content.

  • A Experiment Setting Detail: Experiments run on one node with four NVIDIA A40 GPUs, 208 GB memory, and 16 CPU cores for both optimization and inference.FP8 quantization is enabled when supported, and GPT-4 performs prompt refinement throughout optimization.
  • B.1 Verbal Loss Prompts for MultiWOZ: MultiWOZ uses Joint Goal Accuracy and Inform & Success verbal losses, with JGA computed at the turn level.The prompts are designed for distinct dialogue-state and task-success evaluations.
  • B.1.1 JGA Loss: The JGA prompt compares predicted dialogue states with ground-truth intentions and identifies false-positive and false-negative predictions.Prediction fields are replaced by JSON dialogue-state strings, while error fields encode slot-value or slot-name discrepancies.
  • B.1.1 JGA Loss: The JGA template represents dialogue states with JSON slot-value pairs, such as train departure, leave time, day, and destination.The supplied example includes Cambridge, 11:00, Wednesday, and Stansted values.
  • B.1.2 Inform & Success Loss: The Inform & Success prompt compares system-generated queries and information with their corresponding ground-truth queries and information.These fields are substituted with JSON strings representing the generated and reference content.
  • B.2 Verbal Loss Prompt for τ-bench: The τ-bench reward prompt evaluates ground-truth and predicted actions, action agreement, required response strings, predicted responses, and response agreement.Generated and reference tool-call trajectories populate the action fields, while binary rewards encode action_match and output_match.
  • B.2 Verbal Loss Prompt for τ-bench: τ-bench response fields substitute required text strings and system utterances, alongside corresponding binary action and output rewards.The template uses ground-truth tool-call trajectories and generated trajectories for action comparison.
  • B.2 Verbal Loss Prompt for τ-bench: The τ-bench template illustrates structured tool-call arguments, including an order identifier, item identifiers, replacement item identifiers, and payment method information.These values appear within an example exchange_delivered_order action.

C Language Model as Optimizer · C.1 Pseudocode of Language Model as Optimizer · C.2 Prompt of Language Model as Optimizer

The language-model optimizer iteratively updates multi-agent prompts using performance, attribution trajectories, tools, and optimization history. Its templates instruct the optimizer to identify agents needing improvement and return constrained prompt revisions with warning-based guidance.

  • C.1 Pseudocode of Language Model as Optimizer: The optimizer requires initial agent prompts, agent tools, and a prompt template before optimization begins.
  • C.1 Pseudocode of Language Model as Optimizer: At each iteration, the system runs the MAS on training samples and collects current prompts, performance, and attribution trajectories.
  • C.1 Pseudocode of Language Model as Optimizer: The optimizer appends prompt-performance pairs to history, queries an LLM for prompt updates, and returns the updated prompts after T iterations.
  • C.2 Prompt of Language Model as Optimizer: The instruction prompt presents the MAS structure, agent prompts, tools, inference trajectories, final-output comparisons, and optimization history to the optimizer.
  • C.2 Prompt of Language Model as Optimizer: The optimizer must identify agents needing improvement and propose revised prompts without changing agent order or suggesting unavailable tools.
  • C.2 Prompt of Language Model as Optimizer: Warnings may be added as markdown bullets, with each warning linked to a trajectory failure case, while DONT_CHANGE content and tags remain unchanged.
  • C.2 Prompt of Language Model as Optimizer: The input format includes agent structures, available tools, optimization history with performance, and trajectories represented as sequential outputs ending in a loss comparison.
  • C.2 Prompt of Language Model as Optimizer: The output format is a JSON object containing reasoning and an agent_prompts mapping with revised prompts containing a Warning section.

D Time Cost

Table 3 shows that optimization runtime is primarily determined by the benchmark and underlying model, while connection-weight choices add little computational burden.

  • MultiWOZ: 16.3–16.7 hours on MultiWOZ for Llama-3.3-70B-It versus 8.0–9.5 hours for Qwen-3-32B.These runtimes cover completing 10 optimization steps under different connection-weight settings.
  • τ-bench: 10.3–16.3 hours on τ-bench for Llama-3.3-70B-It versus consistently around 5–6 hours for Qwen-3-32B.Llama-3.3-70B-It varies more noticeably with connection weight, whereas Qwen-3-32B remains stable.
  • Overall: Connection-weight choices do not introduce a substantial additional computational burden.Across both benchmarks, overall runtime is primarily determined by the benchmark and underlying model.
Loading 2606.28187v1…