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

arXiv: https://arxiv.org/abs/2605.30227 · HTML: https://mlsanity.com/paper/2605.30227/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 23 of its 31 references that are in the map.
- First posted on arXiv 28 May 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 23 of 23)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Aligning AI With Shared Human Values](https://mlsanity.com/paper/2008.02275/) (2020)
- [Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problems](https://mlsanity.com/paper/1705.04146/) (2017)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [MedMCQA : A Large-scale Multi-Subject Multi-Choice Dataset for Medical domain Question Answering](https://mlsanity.com/paper/2203.14371/) (2022)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs](https://mlsanity.com/paper/2406.11695/) (2024)
- [EvoPrompt: Connecting LLMs with Evolutionary Algorithms Yields Powerful Prompt Optimizers](https://mlsanity.com/paper/2309.08532/) (2023)
- [Improving Multi-Agent Debate with Sparse Communication Topology](https://mlsanity.com/paper/2406.11776/) (2024)
- [Batch Calibration: Rethinking Calibration for In-Context Learning and Prompt Engineering](https://mlsanity.com/paper/2309.17249/) (2023)
- [MAS-GPT: Training LLMs to Build LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2503.03686/) (2025)
- [Beyond Majority Voting: LLM Aggregation by Leveraging Higher-Order Information](https://mlsanity.com/paper/2510.01499/) (2025)
- [Leveraging Large Language Models for Effective and Explainable Multi-Agent Credit Assignment](https://mlsanity.com/paper/2502.16863/) (2025)
- [MAPRO: Recasting Multi-Agent Prompt Optimization as Maximum a Posteriori Inference](https://mlsanity.com/paper/2510.07475/) (2025)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [Collaborative Multi-Agent Test-Time Reinforcement Learning for Reasoning](https://mlsanity.com/paper/2601.09667/) (2026)

## Built on by (most cited first, 3 of 3)

- [MAS-PromptBench: When Does Prompt Optimization Improve Multi-Agent LLM Systems?](https://mlsanity.com/paper/2606.23664/) (2026)
- [AttriMem: Attribution-Guided Process Feedback for Agent Memory Construction](https://mlsanity.com/paper/2607.21106/) (2026)
- [GraphOPD: Graph-Augmented On-Policy Distillation for LLM Agents](https://mlsanity.com/paper/2610.08959/) (2026)

## Abstract (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.