Technical Summary: Evaluation-Aligned Training Signals for Multi-LLM Agents

Problem Statement

Large Language Model (LLM) Multi-Agent Systems (MAS) are increasingly used for complex tasks, yet they face significant training challenges. Unlike classical Reinforcement Learning (RL) agents operating in low-dimensional, repetitive action spaces, LLM agents act in high-dimensional spaces with diverse, often unique responses. This flexibility introduces fragility: errors can cascade, repair loops inflate costs, and coordination failures reduce reliability.

Current training methods are ill-suited for this setting. Single-agent post-training techniques (e.g., RLHF, DPO) map evaluation signals directly to a single trajectory, failing to distribute credit across multiple agents. Conversely, traditional Multi-Agent Reinforcement Learning (MARL) credit assignment methods rely on assumptions of dense numeric rewards and discrete state-action pairs that do not hold in language-based MAS. Consequently, there is a lack of principled methods to transform system-level evaluations (success/failure scores) into localized, auditable, and fair training signals for individual agents and their specific messages.

Methodology

The paper proposes a theoretical framework that unifies cooperative game-theoretic attribution with Process Reward Modeling (PRM) to bridge the gap between global system evaluation and local agent supervision. The framework operates via two complementary routes depending on the episode outcome:

1. Success-Case Attribution (System $\to$ Agent $\to$ Message)

When a system episode succeeds ($R_{sys} > 0$), the framework decomposes the global reward into fine-grained signals:

• System to Agent (Shapley Values): The global reward $R_{sys}$ is distributed among agents using Shapley values. This calculates each agent's marginal contribution to the system's performance across all possible coalitions.
  • Mechanism: Counterfactual coalitions are simulated by replaying the trajectory with specific agents replaced by a baseline policy (e.g., no-op or frozen reference).
  • Properties: This ensures fairness (symmetry, dummy, efficiency) and allows for negative credits if an agent's presence lowers the system score. The sum of agent rewards equals the system reward ($\sum r_i = R_{sys}$), preventing credit inflation.
• Agent to Message (PRM Refinement): The agent-level credit is further refined into per-message signals to address redundancy and inefficiency.
  • Mechanism: A domain-tuned judge assigns signed labels ($s_{i,t} \in \{-1, 0, +1\}$) to each message based on whether it aligns with or counteracts the agent's overall marginal contribution direction.
  • Signal Generation: Message rewards are calculated as a signed share of the agent's Shapley credit. Aligned messages receive a bonus, while counter-aligned or redundant messages are penalized. Crucially, the sum of message rewards for an agent equals the agent's total Shapley credit, ensuring credit conservation.

2. Failure-Case Attribution (First-Error Localization)

When a system episode fails ($R_{sys} = 0$), Shapley redistribution offers little guidance as credits must sum to zero. Instead, the framework employs:

• First-Error Localization: A binary search identifies the earliest message ($m_{i^*, t^*}$) that causes the trajectory to fail.
• Repair-Aware Preferences: Unlike monotone failure models that invalidate all subsequent steps, this approach distinguishes between the error and subsequent repair attempts.
  • Judges: A prefix judge detects the failure point, while a failure-alignment judge evaluates post-error messages to determine if they attempt to correct the trajectory.
  • Training Signal: Contrastive pairs are constructed ($H_{t^*-1}, y^+, y^-$), where $y^-$ is the harmful error and $y^+$ is a preferred alternative. These pairs feed into preference-based objectives (e.g., DPO, GRPO).

Key Contributions

1. Theoretical Framework: A unified approach transforming system-level evaluations into signed, credit-conserving message-level signals for LLM MAS.
2. Complementary Attribution Mechanisms:
   • Success: Shapley-based credit allocation refined by PRM-style signed message labels to promote cooperation and discourage redundancy.
   • Failure: First-error localization combined with repair-aware preferences to penalize errors while rewarding corrective attempts.
3. Theoretical Guarantees: The authors prove that the resulting signals are:
   • Bounded: Rewards are constrained within finite intervals.
   • Cooperative: Shapley values reward unique contributions and penalize sabotage or free-riding.
   • Credit-Conserving: The sum of local signals exactly equals the global system outcome, ensuring no artificial inflation of rewards.
4. Compatibility: The signals are designed to be directly compatible with modern reinforcement learning (e.g., PPO, GRPO) and preference-based (e.g., DPO) post-training pipelines.

Results and Claims

The paper is primarily conceptual. It does not present empirical benchmarks or experimental validation. Instead, the "results" are theoretical proofs demonstrating that the proposed signals satisfy necessary properties for stable and fair multi-agent training.

• Claimed Significance: The framework provides a scalable, auditable pathway from global evaluation to local supervision. It addresses the specific limitations of existing methods by handling high-dimensional language actions, sparse evaluations, and the need for repair-aware learning in multi-agent contexts.
• Modesty: The authors explicitly state that empirical validation is left for future work. They acknowledge that while the framework is theoretically sound, practical implementation requires handling computational costs (e.g., Shapley approximation via permutation sampling) and the reliability of judges.

Conclusion

This work establishes the conceptual foundation for cooperative, credit-conserving post-training of LLM multi-agent systems. By integrating Shapley values for fair attribution in success cases and first-error localization for repair-aware learning in failure cases, the paper offers a principled solution to the "who gets the reward and who gets the blame" problem in complex multi-agent workflows.