Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization

Wenwu Li, Yuran Song, Mingze Zhao, Bo Jin, Wenhao Li · 2026

Read Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization by Wenwu Li, Yuran Song, Mingze Zhao, Bo Jin, Wenhao Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30227.txt.

Introduction

Wenwu Li and four co-authors unify temporal and structural credit assignment for multi-agent language-model prompt optimization. Optimization is hard because graphs are discrete and global signals sparse, so black-box optimizers cannot blame specific parts for failures. Their method splits the objective two ways: temporal credit via gates flagging key rounds, and structural credit via role policies isolating agent roles. A verbalized block descent algorithm alternates role prompts and protocols, using proxy gradients to target weak links, cutting query counts while improving results.

Catalog record

CREATORWenwu Li, Yuran Song, Mingze Zhao, Bo Jin, Wenhao Li
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44550
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30227

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization Wenwu Li, Yuran Song, Mingze Zhao, Bo Jin, Wenhao Li Abstract While Multi-Agent Systems (MAS) empower Large Language Models to tackle complex reasoning tasks through collaborative interaction, optimizing their dynamics remains a formidable challenge due to the discrete, non-differentiable nature of the computation graph and the sparsity of global supervisory signals. Existing black-box optimizers struggle to attribute trajectory-level failure to specific local components, resulting in inefficient, high-variance exploration. We argue that tractable MAS optimization needs structural inductive biases to disentangle error signals. We propose temporal and structural credit assignment , which decomposes the objective along two axes: (i) temporal credit , using state-space bottlenecks to identify critical rounds, and (ii) structural credit , using stationary role policies to isolate agent contributions. Leveraging these decomposed signals, we introduce a discrete, verbalized block coordinate descent algorithm for iterative refinement. Rather than indiscriminate global updates, it alternates between optimizing role prompts and aggregation protocols, using LLM-generated “proxy gradients” to target only the identified weak links. Across diverse reasoning benchmarks, our approach substantially reduces query complexity while improving performance, providing a principled and interpretable path toward self-improving MAS. 1 Introduction Large Language Models (LLMs) have evolved from static text generators into dynamic reasoning engines, achieving remarkable success in mathematical reasoning, code generation, and complex planning [ 2 , 26 ] . To transcend the limitations of single-model inference, recent research has shifted toward MAS, where specialized agents collaborate via iterative critique-and-revision cycles [ 35 , 31 ] . By distributing tasks across diverse roles (e.g., proposer, debater, synthesizer), MAS frameworks can theoretically solve problems that are intractable for a single monolithic model [ 14 ] . Figure 1: Overview of the credit-guided prompt optimization pipeline. Top: a multi-agent, multi-round reasoning loop (planner/solver/critic) produces per-round messages that are aggregated into a shared system state S_{r} ; an aggregation module feeds back to the next round. From the completed trajectory, we compute temporal credit across rounds (identifying critical rounds) and structural/spatial credit across agents (identifying effective or limiting roles). These credits then drive inference-time prompt updates, selectively refining the lowest-credit rounds/roles while keeping strong components fixed. Bottom: an example travel-itinerary task illustrates per-round agent outputs, the evolving shared state ( S_{1},S_{2},\ldots ), temporal credit weights, and a before/after prompt update that specializes guidance to the weak round/role. However, optimizing the interaction dynamics of MAS presents a formidable challenge. From an optimization perspective, an LLM-based MAS operates as a discrete, non-differentiable computation graph. Unlike neural network training where backpropagation precisely attributes error to specific weights, MAS optimization suffers from the Credit Assignment Problem (CAP) in its most severe form: the supervisory signal is typically sparse (a single scalar score at the terminal state) and global (applying to the entire trajectory) [ 24 , 7 ] . Existing approaches often treat the entire system as a black box [ 5 , 6 , 8 ] , applying derivative-free optimization or heuristic aggregation [ 19 , 1 ] . While effective for simple chains, these methods struggle in complex multi-round collaborations because they ignore the internal causal structure of the reasoning process. Optimizing a system with N agents over R rounds essentially involves searching in a space of \mathcal{O}(N\times R) coupled prompts. Without structural priors, this faces catastrophic variance and inefficient exploration [ 34 ] . In this work, we argue that making MAS optimization tractable requires imposing structural constraints on the computation graph to disentangle the error signal. We propose two principled relaxations that transform the chaotic interaction graph into a structured optimization landscape. First, state-space bottleneck via aggregation. In a fully connected MAS, information flows diffusely, making it impossible to pinpoint when reasoning collapsed. We introduce an explicit Aggregation Module at each round to summarize agent outputs into a unified state S_{t} . This effectively models the interaction as a Markov Decision Process (MDP), where the aggregator creates a “state bottleneck” [ 22 , 18 ] . This architectural choice is not merely functional; it is a prerequisite for Temporal Credit Assignment , allowing us to evaluate the quality of consensus at discrete time steps independent of individual agent noise. Second, stationary policy via parameter sharing [ 9 , 29 ] . Optimizing unique prompts for every agent at every round creates an explosion of parameters. We impose a Stationary Policy Constraint , where each role (e.g., the Debater) shares the same system prompt across all interaction rounds. This reduces the search space from trajectory-specific instructions to robust role definitions. Crucially, this constraint enables reliable Structural Credit Assignment : by observing an agent’s performance across multiple rounds, we can distinguish systematic role incompetence from transient stochastic errors. Building on these structural insights, we propose a unified framework for Temporal and Structural Credit Assignment , as shown in Figure 1 . We formalize the MAS optimization problem as a bi-level objective depending on two orthogonal variable blocks: (i) Role Prompts (defining agent behaviors) and (ii) Aggregation Prompts (defining state transition protocols). Instead of optimizing these jointly—which is prone to instability—we derive a novel Block Coordinate Descent (BCD) algorithm adapted for discrete prompt optimization [ 25 , 3 ] . Our method alternates between refining role-specific instructions (fixing the aggregation logic) and refining the aggregation protocol (fixing the role behaviors). To drive this descent, we utilize LLM-based critics to compute “proxy gradients”—decomposed credit scores that guide targeted textual updates only to the bottleneck components. Our contributions are summarized as follows: 1) We reformulate MAS prompt optimization by introducing state-space bottlenecks and stationary policy constraints. These inductive biases bridge the gap between sparse terminal rewards and dense, actionable feedback. 2) We propose a theoretically grounded optimization algorithm that alternates between structural (role) and temporal (aggregator) updates. This mimics Block Coordinate Descent in the discrete prompt space, ensuring stability and convergence compared to joint optimization baselines. 3) Numerical experiments demonstrate that our approach achieves higher task accuracy while reduces query complexity. By focusing updates on specific "weak link" roles or "phase transition" rounds, we avoid the inefficiency of indiscriminate global updates. 2 Related Works Prompt Optimization. Several methods have been developed for optimizing prompts, ranging from learning parameter-efficient soft prompts to automatically searching for optimal discrete prompts using reinforcement learning, meta-optimization, and evolutionary algorithms. Prompt-Tuning [ 13 ] freezes the parameters of a pre-trained language model and learns task-specific soft prompts via end-to-end backpropagation. RLPrompt [ 5 ] optimizes discrete textual prompts through reinforcement learning with a policy network. OPRO [ 28 ] frames prompt optimization as an iterative black-box optimization problem. EvoPrompt [ 8 ] integrates evolutionary algorithms with large language models by employing the LLM to implement linguistically coherent crossover and mutation operations. PromptBreeder [ 6 ] implements a self-referential self-improvement mechanism for prompts using a genetic algorithm that co-evolves task-prompts and mutation-prompts. LLM-based MAS. Current research on LLM-based multi-agent systems spans four key dimensions: system representation, optimization mechanisms, dynamic adaptation, and reasoning efficiency. GPTSwarm [ 32 ] exemplifies offline structural learning via static post-training optimization with strong theoretical grounding in policy-gradient methods. DyLAN [ 17 ] represents unsupervised online selection, offering principled agent evaluation without labeled data and drawing theoretical connections to Shapley-value attribution. EvoMAC [ 15

Read the complete text