Who Gets the Reward & Who Gets the Blame? Evaluation-Aligned Training Signals for Multi-LLM Agents

Chih-Hsuan, Yang, Tanwi Mallick, Le Chen, Krishnan Raghavan, Amal Gueroudji, Ian T. Foster, Rajeev Thakur

TL;DR

This paper introduces a novel theoretical framework to solve the credit assignment problem in multi-LLM agent systems. By combining cooperative game theory (Shapley values) for successful outcomes and first-error localization for failures, it translates global system evaluations into precise, message-level training signals. This provides a principled, auditable pathway to post-train multi-agent systems using standard reinforcement learning and preference optimization methods.

What Problem Does This Paper Address?

Multi-Agent Systems (MAS) powered by LLMs excel at complex tasks by breaking them down across specialized roles (e.g., planners, database coders, and analysts). However, training these systems to improve over time is notoriously difficult because we usually only get a single, global evaluation at the very end (e.g., did the team successfully solve the data analysis problem?).

Standard alignment techniques like RLHF or DPO are designed for single models, where the evaluation maps directly to a single model's trajectory. Meanwhile, traditional Multi-Agent Reinforcement Learning (MARL) methods rely on simple, repetitive action spaces and dense numeric rewards, which fail in the high-dimensional, unique text spaces of LLMs. Consequently, there hasn't been a principled way to figure out who deserves the credit when a multi-agent system succeeds, or who takes the blame when it fails.

Methods

The authors propose a dual-route framework that treats successful and failed episodes differently:

  1. Success Route (System $\rightarrow$ Agent $\rightarrow$ Message): When a system trajectory succeeds, the framework uses Shapley values from cooperative game theory to fairly distribute the global reward to individual agents based on their marginal contribution. To compute this, they simulate counterfactual coalitions by replaying traces and replacing "absent" agents with baseline policies. This agent-level credit is then distributed down to specific messages using a signed Process Reward Model (PRM). A judge labels messages as aligned (+1), counter-aligned (-1), or neutral (0) relative to the agent's direction, creating a credit-conserving weighting scheme where the sum of message rewards exactly equals the global system reward.
  2. Failure Route (First-Error Localization): When the system fails, dividing a zero reward is uninformative. Instead, the framework uses a binary search ($O(\log T)$ complexity) over the trajectory prefixes to pinpoint the first critical error that derailed the system. It then constructs contrastive preference pairs (the error vs. a corrected alternative) suitable for Direct Preference Optimization (DPO), while ensuring that any subsequent agents attempting to repair the error are not unfairly penalized.

Datasets

Not discussed in the paper. The contribution of this paper is entirely conceptual and theoretical; no datasets were used, and empirical validation is left for future work.

Key Insights and Ideas

  • Unified Success and Failure Regimes: Instead of trying to force a single mathematical formulation onto both outcomes, the framework elegantly splits into a reward-decomposition route for successes and an error-localization preference route for failures.
  • Credit Conservation: The message-level rewards are mathematically guaranteed to be "budgeted" by the actual system outcome. They sum up exactly to the agent's credit, which in turn sums to the global score, preventing reward inflation or free-riding.
  • Inverting the Signs for Harmful Agents: A fascinating property of the signed PRM formulation is that if an agent is determined to be net-harmful ($\phi_i < 0$), its actions that align with its trajectory are penalized the most, while actions that counteract its own harmful path are rewarded for trying to dilute the harm.
  • Anti-Competition and Anti-Hoarding: Because Shapley values reward unique marginal contributions, agents are disincentivized from duplicating another agent's work or sabotaging teammates, naturally fostering true cooperation.

Key Results

As a purely theoretical paper, there are no quantitative experimental results or benchmark scores. Instead, the authors provide rigorous theoretical guarantees:

  • Efficiency & Credit Conservation: Proving that $\sum_{i,t} r_{i,t} = R_{sys}$, meaning all supervision signals are perfectly budgeted by the realized system outcome.
  • Boundedness: Demonstrating that message-level rewards remain within stable, predictable intervals, preventing training instability.
  • Computational Complexity: Showing that while exact Shapley values scale exponentially ($O(2^n)$), practical Monte Carlo permutation sampling reduces the cost to polynomial time ($O(Mn)$), making it scalable for real-world engineering.

Limitations and Future Work

  • Lack of Empirical Validation: The framework has not yet been tested on real-world LLM multi-agent benchmarks, which the authors note as their immediate next step.
  • Baseline Dependency in Heterogeneous Teams: For teams made of completely different models (e.g., a specialized chemistry model vs. a general LLM), defining a fair "baseline policy" to simulate an agent's absence is highly sensitive and requires careful engineering to avoid distorting credit assignment.
  • Reliability of Judges: The framework relies heavily on intermediate judges (LLM-as-a-judge or compact PRMs) to label message alignment and locate errors, meaning noisy or biased judges could degrade training quality.

Summary updated

Abstract

Large Language Models (LLMs) in multi-agent systems (MAS) have shown promise for complex tasks, yet current training methods lack principled ways to connect system-level evaluation with agent- and message-level learning. We propose a theoretical framework that unifies cooperative game-theoretic attribution with process reward modeling to transform system evaluation to agent credit to response-level signals. Unlike prior approaches that rely only on attribution (Shapley) or step-level labels (PRM), our method produces local, signed, and credit-conserving signals. In success cases, Shapley-based credit assignment fairly allocates outcomes across agents and is refined into per-message rewards that promote cooperation while discouraging redundancy or sabotage; in failure cases, first-error localization yields repair-aware preferences that penalize harmful steps while rewarding corrective attempts. The resulting signals are bounded, cooperative, and directly compatible with reinforcement- or preference-based post-training, providing a unified and auditable pathway from global evaluation to local supervision in LLM multi-agent training. Our contribution is conceptual: we present a theoretical foundation and training signals, leaving empirical validation for future work.
BibTeX
@misc{chihhsuan2025who,
  author = {Chih-Hsuan and Yang and Tanwi Mallick and Le Chen and Krishnan Raghavan and Amal Gueroudji and Ian T. Foster and Rajeev Thakur},
  title = {{Who Gets the Reward \& Who Gets the Blame? Evaluation-Aligned Training Signals for Multi-LLM Agents}},
  year = {2025},
  eprint = {2511.10687},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.10687},
}
Figure