AI Paper Atlas

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

ICML 2026 · Multi-agent systems and games › LLM agents · approach: LLM multi-agent decision making

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 changedWhereMeasuredEffect
add trajectory-based credit assignment on top of outcome feedback (ablation)TRUCE · MultiAgentBench ResearchTask Score: 79.3 -> 83.0Improved
add unit-based prompt refinement instead of global prompt modification (ablation)TRUCE · MultiAgentBench ResearchCoordination Score: 86.4 -> 88.5Improved
add credit assignment to prompt optimization (ablation)TRUCE · MultiAgentBench ResearchMilestones/1M tokens: 18.28 -> 20.40Improved
keep top-attributed sub-trajectories in credit assignment (vs removing them) (ablation)TRUCE · MultiAgentBench ResearchCoordination Score: 80.83 -> 88.50 (CS); random removal 84.99Improved
use TRUCE instead of DsPy (MIPROv2) scalar-feedback optimizationgpt-4o-mini MAS · MultiAgentBench averageTask Score: 60.67 -> 69.00Improved
use TRUCE instead of TextGrad global rewritesgpt-4o-mini MAS · MultiAgentBench averageCoordination Score: 80.21 -> 88.27Improved
apply existing prompt optimizers (Reflexion, DsPy, TextGrad) to expert-designed CodeSimCodeSim · Programming average (gpt-4o-mini)Pass@1: 80.23 -> 77.98 (TextGrad)No clear effect
use TRUCE on CodeSim programming benchmarksCodeSim · Programming average (gpt-4o-mini)Pass@1: 80.23 -> 80.80Improved
apply TRUCE instead of Reflexion/TextGrad on Qwen3 MASQwen3 MAS · MultiAgentBench averageCoordination Score: 84.75 -> 85.96Mixed
use TRUCE instead of MAPRO or HiveMindgpt-4o-mini MAS · MultiAgentBench CodingCoordination Score: 63.46 -> 85.54Improved

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.

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

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy