🤖 AI

Semantic Cooperative Games for Contribution Attribution in LLM-Based Multi-Agent Systems

This paper introduces Semantic Cooperative Games (SCG) and its efficient single-trajectory algorithm SLIC, which utilize a semantic generation hypergraph and the Semantic Shapley Value to provide fast, counterfactual-free, and interpretable contribution attribution for LLM-based multi-agent systems, significantly reducing computational costs while maintaining accuracy.

Original authors: Pengyi Jiang, Xiaoguang Zhu, Quanyan Zhu

Published 2026-07-22

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Pengyi Jiang, Xiaoguang Zhu, Quanyan Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to solve a giant, complex puzzle together. They pass notes back and forth, each person adding a piece, correcting a mistake, or suggesting a new angle. In the world of artificial intelligence, these "friends" are Large Language Models (LLMs) working in a team, known as a multi-agent system. They don't just chat; they follow a strict workflow to build things like medical diagnoses, legal summaries, or code. But here's the tricky part: when the final puzzle is solved (or fails), how do we know who actually deserves the credit? Was it the person who found the first clue, the one who connected the dots, or the one who double-checked the edges?

For a long time, scientists tried to figure this out using a method called "counterfactual valuation." Think of it like a detective who, after a crime, asks, "What if we erased this person from the story?" They would delete an agent, re-run the whole conversation from scratch, and see if the result changed. If the answer changed, that agent was important. But this is like trying to fix a broken clock by taking it apart, rebuilding it ten different ways, and hoping the time is right. It takes forever, costs a lot of energy, and because AI can be a bit unpredictable (like a dice roll), the results often wobble. It's a messy, expensive way to find the truth.

This is where a new paper steps in with a clever, faster idea. Instead of re-rolling the dice or rebuilding the clock, the authors propose looking at the single, real conversation that already happened and tracing the "breadcrumbs" of meaning. They call their method Semantic Cooperative Games (SCG) and their algorithm SLIC.

Here is how it works, using a playful analogy: Imagine the team's conversation is a giant, tangled web of string. Each knot in the string is a piece of information (a "semantic node"), and the string connecting them shows how one idea led to another. Some strings are held by Agent A, others by Agent B. The paper suggests we don't need to cut the string and re-tie it to see who matters. Instead, we can look at the finished web and ask: "Which knots are absolutely necessary to hold up the final picture?"

The authors realized that in many cases, if Agent A writes a sentence and Agent B just repeats it, Agent B didn't actually add anything new. In the old "re-run" method, you might accidentally give Agent B credit just because you deleted Agent A and the system panicked. But the new SLIC algorithm uses a logic trick called "Boolean absorption." It's like realizing that if you have a key and a spare key, and the door opens with just the first key, the second key is redundant. SLIC spots these redundancies instantly by looking at the flow of ideas, not by guessing what might have happened.

The paper proves that under normal, straightforward conditions, this new method gives the exact same answer as the old, slow, re-running method. But the real magic is in the speed and stability. In a test using a medical benchmark (a dataset for checking health-related AI), the new method slashed the computing cost by 93.3%. That's a massive drop! It means we can figure out who did the heavy lifting in a team of AI agents without needing to run the simulation a hundred times.

Furthermore, in more complex, messy scenarios where the agents have different roles, the new method doesn't just give a score; it tells a story. It can spot when an agent is holding up the system structurally (like a pillar in a building) even if they didn't write much text, or when an agent's failure would cause a collapse. It aligns very well with what happens when you actually mess with the agents (like giving them "hallucinations" or fake info), with alignment scores reaching as high as 1.000 in some tests.

So, what's the takeaway? We don't need to break the machine to see how it works. By tracing the path of ideas in a single, real conversation, we can fairly and quickly decide who contributed what. It's a shift from "guessing by breaking" to "understanding by tracing," making it much easier to build better, more reliable teams of AI agents in the future.

Technical Summary: Semantic Cooperative Games for Contribution Attribution in LLM-Based Multi-Agent Systems

Problem Statement

The paper addresses the Contribution Attribution Problem (CAP) in Large Language Model (LLM)-based multi-agent systems. In these systems, final outputs emerge from complex sequences of agent actions, message exchanges, and ordered workflow dependencies. Existing attribution methods predominantly rely on counterfactual valuation, where contributions are estimated by removing agents, masking messages, or comparing scores across altered subsets of the system.

The authors identify two critical limitations in current counterfactual approaches within language-mediated workflows:

Workflow Dependence: Contribution is not solely a function of an agent's presence but depends on the specific execution order, routing rules, and downstream dependencies. A set-based counterfactual (e.g., removing a subset of agents) fails to capture the partial-order dependency structure inherent in LLM workflows.
Cost and Instability: Rerunning workflows to generate counterfactuals introduces high computational costs (repeated model calls) and high variance due to the stochastic nature of LLM decoding, prompting sensitivity, and orchestration details.

The paper argues that attribution should be treated not merely as a value-comparison problem but as a workflow-structural problem, where contributions are derived from the realized trajectory of semantic transformations rather than hypothetical reruns.

Methodology: Semantic Cooperative Games (SCG) and SLIC

To address these challenges, the authors propose Semantic Cooperative Games (SCG), a framework that models a realized language flow as a semantic generation hypergraph, and SLIC (Semantic Logic Inversion for Contribution), a single-trajectory algorithm for computing contributions.

1. Semantic Generation Hypergraph

The core of SCG is the transformation of a realized workflow trace into a hypergraph $G = (S, L, N; \alpha, \omega, O, I)$ :

Semantic Nodes ( $S$ ): Extracted by recursively tracing back from value-bearing output nodes (defined by a rubric) to their predecessors in the language flow. Nodes are categorized as native, derived, or persistent.
Hyperedges ( $L$ ): Directed links representing semantic transformations where a set of input nodes produces an output node.
Ownership Map ( $\alpha$ ): Maps each hyperedge to the specific agent that generated it.
Output Nodes ( $O$ ) and Weights ( $\omega$ ): The specific semantic nodes evaluated by a rubric, assigned weights reflecting their task value.

2. Semantic Shapley Value (SSV)

Instead of querying a value function via reruns, SCG induces an agent-level semantic value function directly from the hypergraph structure.

Support Logic: For each output node, the system identifies minimal link-level supports (sets of links sufficient to produce the node).
Boolean Absorption: These supports are lifted to the agent level and simplified using Boolean absorption (e.g., $(A \land B) \lor A \equiv A$ ) to remove logically redundant paths.
Multilinear Expansion: The simplified Boolean support functions are expanded into unique multilinear (Möbius) coefficients.
Allocation: The Semantic Shapley Value (SSV) is computed by allocating these coefficients among the agents involved in each support term, adhering to Shapley axioms (efficiency, symmetry, dummy, additivity).

3. The SLIC Algorithm

SLIC computes SSV in a single pass without counterfactual reruns:

Trace Backward: Recursively trace predecessors from rubric output nodes to construct the semantic generation hypergraph.
Extract Supports: Identify minimal link-level supports for each output node.
Map and Absorb: Map links to agents, apply Boolean absorption to derive minimal agent support families, and eliminate redundancy.
Compute SSV: Expand support functions into multilinear coefficients and aggregate weighted contributions.

Theoretical Guarantee

The authors prove that under standard conditions (set-based value reachability, full observability, and no masking or order dependence), the Semantic Shapley Value reduces exactly to the classical Shapley value. This establishes SSV as a principled extension of cooperative game theory to semantic structures.

Key Contributions

SCG Framework: A novel semantic cooperative-game framework that represents realized language flows as semantic generation hypergraphs, inducing agent-level value functions from workflow-dependent semantic supports.
Semantic Shapley Value (SSV): A definition of contribution allocation over semantic support structures that extends the classical Shapley value from unordered coalitions to semantic hypergraphs.
SLIC Algorithm: A single-trajectory algorithm that computes SSV without counterfactual reruns, utilizing Boolean absorption and multilinear allocation to handle redundancy and joint support.
Theoretical Equivalence: A proof demonstrating that SSV coincides with the classical Shapley value under standard coalition-game conditions.

Experimental Results

Experiment 1: Consistency with Classical Shapley (Medical Benchmark)

Using the HealthBench domain, the authors constructed a controlled medical multi-agent workflow where agents solved independent subproblems (satisfying the reduction assumptions).

Comparison: SLIC was compared against Monte Carlo Shapley (Ground Truth), Leave-One-Out (LOO), and a Holistic LLM Judge.
Performance: SLIC achieved a Kendall $\tau_b$ of 0.814 and an L1 error of 6.61, significantly outperforming LOO (0.575, 15.08) and the Holistic Judge (0.479, 12.90).
Efficiency: SLIC reduced computation cost by 93.3% compared to the Monte Carlo baseline while maintaining high consistency, requiring only a single trajectory execution.

Experiment 2: Diagnosing Complex Multi-Role Workflows

In settings without ground-truth decomposition (meeting summarization, numerical reasoning, rule application, medical safety), the authors evaluated SSV against perturbation-induced score drops.

Alignment: SSV profiles showed strong alignment (mean Spearman $\rho = 0.868$ ) with score-drop profiles induced by medium and strong hallucination interventions.
Insight: SSV successfully identified agents whose removal or corruption caused significant system degradation. It also exposed cases where semantic contribution and structural privilege diverge (e.g., an agent with limited semantic work but high structural control) and where removal baselines fail due to redundancy.

Significance and Claims

The paper claims that SLIC provides a fast, counterfactual-free, and interpretable attribution method for complex LLM-based multi-agent systems. By shifting the focus from "what happens if we remove an agent" to "what semantic support did an agent provide in the realized trajectory," the method:

Eliminates the need for expensive and unstable reruns.
Explicitly captures intermediate semantic states and transformations.
Handles redundancy and joint support through Boolean logic and absorption.
Offers a principled foundation for downstream tasks such as failure diagnosis, workflow comparison, agent pruning, and robustness analysis.

The authors emphasize that this approach treats language flow as the observable layer of information flow, making contribution attribution a structural analysis problem rather than a black-box value estimation problem.