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

2026-05-28 · Wenwu Li, Yuran Song, Mingze Zhao, Bo Jin, Wenhao Li arxiv

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.

📄 PDF Abstract BibTeX arXiv:2605.30227

Code (0)

등록된 구현이 없습니다.

A Survey of Temporal Credit Assignment in Deep Reinforcement Learning

2023-12-02 · Eduardo Pignatelli, Johan Ferret, Matthieu Geist, Thomas Mesnard 외

The Credit Assignment Problem (CAP) refers to the longstanding challenge of Reinforcement Learning (RL) agents to associate actions with their long-term consequences. Solving the CAP is a crucial step towards the success…

Decision Making Deep Reinforcement Learning reinforcement-learning Reinforcement Learning+2

Retrospective In-Context Learning for Temporal Credit Assignment with Large Language Models

2026-02-19 · Wen-Tse Chen, Jiayu Chen, Fahim Tajwar, Hao Zhu 외 arxiv

Learning from self-sampled data and sparse environmental feedback remains a fundamental challenge in training self-evolving agents. Temporal credit assignment mitigates this issue by transforming sparse feedback into den…

An Information-Theoretic Perspective on Credit Assignment in Reinforcement Learning

2021-03-10 · Dilip Arumugam, Peter Henderson, Pierre-Luc Bacon

How do we formalize the challenge of credit assignment in reinforcement learning? Common intuition would draw attention to reward sparsity as a key contributor to difficult credit assignment and traditional heuristics wo…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

MICA: Multi-granularity Intertemporal Credit Assignment for Long-Horizon Emotional Support Dialogue

2026-03-06 · Naifan Zhang, Ruihan Sun, Jinwei Su, Hengjie Yang 외 arxiv

Reinforcement learning (RL) for large language models (LLMs) has shown strong performance in single-turn tasks, but extending it to multi-turn interaction remains challenging due to sparse rewards and poor per-turn credi…

Reinforcement Learning

Selective Credit Assignment

2022-02-20 · Veronica Chelu, Diana Borsa, Doina Precup, Hado van Hasselt

Efficient credit assignment is essential for reinforcement learning algorithms in both prediction and control settings. We describe a unified view on temporal-difference algorithms for selective credit assignment. These …

Prediction reinforcement-learning Reinforcement Learning (RL)