Research map / Multi-agent systems and games / LLM agents
From Interaction Trajectories to Prompt Rules: Credit Assignment for Multi-Agent Prompt Optimization
Bin Wu, Haoran Xu, Xiang Zhuang, Zonghao Chen, Zhu Li, Emine Yilmaz, Qiang Zhang
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a credit-assignment approach that maps multi-agent interaction trajectories to prompt-level rule updates for optimizing fixed-structure LLM multi-agent systems.
Problem
Optimizing natural-language prompts in LLM multi-agent systems with fixed roles and interaction structures is hard because behaviors emerge over long, noisy trajectories, making it unclear which prompt components cause success or failure.
Approach
Attributes outcomes to specific prompt components via analysis of interaction trajectories and converts that credit into prompt rule edits, rather than optimizing prompts end-to-end without credit assignment. (Details beyond the abstract not verified.)
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add trajectory-based credit assignment on top of outcome feedback (ablation) | TRUCE · MultiAgentBench Research | Task Score: 79.3 -> 83.0 | Improved |
| add unit-based prompt refinement instead of global prompt modification (ablation) | TRUCE · MultiAgentBench Research | Coordination Score: 86.4 -> 88.5 | Improved |
| add credit assignment to prompt optimization (ablation) | TRUCE · MultiAgentBench Research | Milestones/1M tokens: 18.28 -> 20.40 | Improved |
| keep top-attributed sub-trajectories in credit assignment (vs removing them) (ablation) | TRUCE · MultiAgentBench Research | Coordination Score: 80.83 -> 88.50 (CS); random removal 84.99 | Improved |
| use TRUCE instead of DsPy (MIPROv2) scalar-feedback optimization | gpt-4o-mini MAS · MultiAgentBench average | Task Score: 60.67 -> 69.00 | Improved |
| use TRUCE instead of TextGrad global rewrites | gpt-4o-mini MAS · MultiAgentBench average | Coordination Score: 80.21 -> 88.27 | Improved |
| apply existing prompt optimizers (Reflexion, DsPy, TextGrad) to expert-designed CodeSim | CodeSim · Programming average (gpt-4o-mini) | Pass@1: 80.23 -> 77.98 (TextGrad) | No clear effect |
| use TRUCE on CodeSim programming benchmarks | CodeSim · Programming average (gpt-4o-mini) | Pass@1: 80.23 -> 80.80 | Improved |
| apply TRUCE instead of Reflexion/TextGrad on Qwen3 MAS | Qwen3 MAS · MultiAgentBench average | Coordination Score: 84.75 -> 85.96 | Mixed |
| use TRUCE instead of MAPRO or HiveMind | gpt-4o-mini MAS · MultiAgentBench Coding | Coordination Score: 63.46 -> 85.54 | Improved |
Earlier methods this paper compares with
Named baselines from earlier accepted papers in this paper's results tables: better than 1 of 1 on most shared results.
- Reflexion — Reflexion: language agents with verbal reinforcement learning (NeurIPS 2023) · better on 3 of 3 shared results
Matched by method name in results tables read by AI. Authors' own tables tend to favour the newer method, and a comparison can be missed when a method is renamed.
Closest papers by meaning
- AgentGrad: Intervention-guided Prompt Optimization for Multi Agent Systems (NeurIPS 2026 · similarity 0.90)
- Multi-Agent Design: Optimizing Agents with Better Prompts and Topologies (ICLR 2026 · similarity 0.89)
- MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks (ICML 2026 · similarity 0.88)
- MARS: Multi-Agent Adaptive Reasoning with Socratic Guidance for Automated Prompt Optimization (AAAI 2026 · similarity 0.88)
- AMA-Bench: Evaluating Long-Horizon Memory for Agentic Applications (ICML 2026 · similarity 0.88)
- Reinforcing LLM Agents via Policy Optimization with Action Decomposition (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
