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

AI summary

Overview

Research area: Multi-agent systems built from large language models (LLMs), specifically credit assignment and post-training (RLHF/DPO-style) for cooperative agent teams.

Technical level: Advanced. The paper is purely theoretical, drawing on cooperative game theory (Shapley values), process reward models, and preference-based optimization. Familiarity with reinforcement learning from human feedback and multi-agent RL concepts helps considerably.

Scope: A conceptual framework that converts a single system-level evaluation score for a multi-LLM team into signed, credit-conserving, message-level training signals, with separate routes for successful and failed episodes.

What This Paper Is About

When a team of LLM agents (for example, a Planner, a Database agent, and an Analyst) jointly solves a task, existing evaluators only say how well the whole team did—not which agent or which specific message helped or hurt. Single-model post-training methods like RLHF, DPO, and GRPO assume one trajectory and one model, while classical multi-agent RL credit assignment assumes low-dimensional, repeated actions and dense numeric rewards, neither of which holds when actions are free-form text or code. The paper proposes a unified theoretical pathway from a global system score to local, per-message supervision, covering both success (who gets the reward) and failure (who gets the blame) cases.

Key Contributions

1. A system-to-agent-to-message attribution pipeline. A framework that turns a bounded system evaluation R_sys ∈ [0,1] into signed, credit-conserving message-level signals, bridging global outcomes and local supervision.

2. Complementary success and failure mechanisms. Shapley-based credit allocation with PRM-style refinement for successful episodes; first-error localization with repair-aware preference pairs for failed episodes.

3. Formal guarantees. Proofs that the resulting signals are bounded, credit-conserving (Σ_i φ_i = R_sys and Σ_{i,t} r_{i,t} = R_sys), anti-competitive, and repair-aware.

4. Compatibility with modern post-training. The signals are designed to plug directly into reinforcement learning (PPO/GRPO-style, per-message rewards) or preference-based objectives (DPO-style contrastive pairs), with sampling-based approximations to keep costs tractable.

Main Findings

• Shapley values provide fair, cooperative agent-level credit. Treating each agent as a "player" in a cooperative game, the Shapley value measures marginal contribution averaged over all coalitions. It satisfies symmetry, dummy (zero impact → zero credit), and efficiency (credits sum to the total). Critically, an agent's Shapley value can be negative, explicitly penalizing agents whose participation lowers system quality.

• Duplication and sabotage do not pay. Copying another agent's work yields near-zero marginal credit, and sabotaging others shrinks the total pool available to divide—so neither strategy increases an agent's share. This is the paper's anti-competition property.

• Message-level refinement conserves credit exactly. A judge labels each message as aligned (+1), counter-aligned (−1), or neutral (0) relative to the agent's own contribution direction. Weights ω_{i,t} = 1/k_i + λ(s_{i,t} − s̄_i) sum to one by construction, so r_{i,t} = ω_{i,t} · φ_i distributes exactly the agent's credit across its messages. Redundant messages earn only the baseline share; genuinely informative ones earn strictly more.

• Sign flips for harmful agents. If an agent is net harmful (φ_i < 0), aligned messages are penalized most (they reinforce the harm) while counter-aligned messages receive credit for diluting it.

• Failure requires a different route. When R_sys = 0, Shapley redistribution is uninformative because credits must sum to zero. Instead, the framework binary-searches over trajectory prefixes with a prefix judge to find the first harmful message t*, then asks a failure-alignment judge whether later messages repair or reinforce the failure, producing contrastive pairs (H_{t*−1}, y+, y−).

• Repair attempts are protected. Unlike OmegaPRM-style monotone schemes that label everything after an error as invalid, this framework judges later messages in context, so agents that attempt corrections are rewarded rather than punished.

• Boundedness holds. Each weight satisfies |ω_{i,t}| ≤ 1/k_i + 2λ, so message rewards are bounded, and optional clipping to [−1, 1] enforces a fixed range without changing relative proportions.

• Computational cost is controllable. Exact Shapley is exponential (O(2^n) coalitions), but Monte Carlo permutation sampling reduces this to roughly O(M·n) per episode. First-error localization costs O(log T · C_eval). The authors recommend Shapley attribution for post-training calibration rather than early-stage training.

Methodology in Plain English

The researchers did not run experiments. They constructed a mathematical framework and proved properties about it.

The setup: a team of role-specialized LLM agents produces an interleaved trajectory of messages ending in a final answer. An evaluator assigns one bounded score to the whole run.

For successful runs, the framework asks a counterfactual question for every subset of agents: how well would the team have done without this subset, where absent agents fall back to a fixed baseline policy (a no-op or frozen reference model)? This defines the coalition value function. Shapley values across these coalitions give each agent its fair share of the score. Then a domain-tuned judge (an LLM-as-judge, a compact process reward model, or rule-based checks like SQL validators or unit tests) labels each message relative to that agent's average alignment, and credit is redistributed proportionally—no credit created or destroyed.

For failed runs, the framework treats the trajectory as a sequence and binary-searches for the earliest prefix that flips a judge's verdict from "still viable" to "failed." That message is the critical error. A second judge then evaluates the suffix to distinguish repair attempts from compounding errors. The harmful message and a preferred alternative form a contrastive pair, which standard preference-optimization algorithms can consume directly.

Why This Matters

Impact on research: The paper addresses a genuine gap—single-agent post-training has no mechanism for distributing credit across multiple models and multiple messages, and multi-agent RL methods assume action spaces that do not resemble natural language. By grounding supervision in cooperative game theory and proving conservation and boundedness, it gives the community a principled starting point for training multi-LLM teams. Its guarantees (no credit inflation, no free-riding, no credit hoarding) are properties that existing pipelines simply do not possess.

Real-world applications:

• Enterprise data analysis pipelines where planner/query/analyst agents collaborate on SQL-driven reporting and failures need to be traced to a specific step.
• Software engineering agents (code writers, testers, reviewers) where a failed build must be attributed to a specific agent action, and later repair attempts should be rewarded rather than discarded.
• Scientific workflows using specialist models, such as pairing a domain-specific chemistry model with a code translation agent, where fair credit across heterogeneous capabilities matters.
• Customer-facing multi-agent assistants where runtime cost is driven by redundant or repair-loop messages, and efficiency penalties reduce wasted API calls.

Industry relevance: Organizations deploying multi-agent LLM systems currently tune them by hand or with coarse outcome rewards. A framework that converts a single evaluation into per-message training signals—and that is compatible with existing RLHF and DPO infrastructure, including the ability to replace full Shapley computation with lightweight learned surrogates—offers a practical path to automating that tuning while keeping the supervision auditable.

Future Directions

1. Empirical validation. The authors explicitly defer experiments to follow-up work, planning to test on LLM multi-agent benchmarks against existing baselines. This is the most obvious next step.

2. Heterogeneous and specialist teams. When agents are different foundation models rather than differently prompted instances of one model, the choice of baseline policy for absent agents becomes critical to fair Shapley credit. The paper defers this to an appendix and flags it as unresolved.

3. Surrogate models for scalability. Training compact predictors to approximate Shapley credit ratios or response-level judges, with periodic recalibration to handle distribution shift, is proposed but not demonstrated.

4. Judge reliability and cost. The framework depends on local judges, and while the authors argue that role-specific local judgments are easier than global correctness assessments, the question of systematic judge error and evaluator expense remains open.

Target Audience

This paper is most valuable to researchers working on multi-agent LLM systems, reinforcement learning from human feedback, and post-training methodology—particularly those interested in credit assignment, cooperative game theory applied to machine learning, or process reward models. Practitioners building production multi-agent pipelines will find the framing useful for thinking about attribution and efficiency penalties, though they should note the absence of empirical results. Readers without a background in cooperative game theory or RL post-training will need to work through the Shapley formulation and the RLHF/DPO references to follow the argument.

Authors’ 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.