Technical Summary: MAXSHAPLEY

Problem Statement

Generative search engines, which utilize Large Language Models (LLMs) to retrieve documents and synthesize direct answers, are disrupting the traditional incentive structures for content providers. Unlike traditional search, which directs users to source websites, generative search often answers queries within the interface, reducing traffic and revenue for original content creators. Furthermore, existing methods for attributing generated answers to specific sources are often unreliable, easily manipulated, or opaque.

The core challenge addressed is defining a fair, incentive-compatible mechanism to attribute credit to information sources based on their contribution to a generated answer. This attribution must satisfy standard fairness axioms (Efficiency, Symmetry, Null Player, Additivity) while remaining computationally feasible for latency-sensitive search pipelines. Existing solutions based on the Shapley value, the gold standard for fair allocation, are computationally intractable in this context because they typically require exponential enumeration of source subsets or repeated ablation trials, leading to prohibitive token costs and latency.

Methodology: MAXSHAPLEY

The authors propose MAXSHAPLEY, a novel algorithm that computes fair credit attribution by modeling the interaction between retrieved sources and the generated answer as a cooperative game. The method operates in a black-box setting, requiring only the query, the retrieved sources, and the final generated answer as input, without needing access to the search LLM's internal logits or probabilities.

The methodology consists of three primary stages:

1. Keypoint Decomposition: An attribution LLM ($\Psi_A$) decomposes the generated answer $a$ into a set of $n$ key points $P = \{p_1, \dots, p_n\}$ with associated weights $w_j$.
2. Support Scoring: The attribution LLM evaluates how well each source $s_i$ supports each key point $p_j$, producing a support score $v_{i,j}$. This step requires $n \times m$ evaluations (or fewer via batching), where $m$ is the number of sources.
3. Max-Sum Utility & Exact Shapley Computation:
   • The authors define a novel utility function $U_{MAXSHAPLEY}$ based on a sum-max structure. For a subset of sources $I$, the utility is the weighted sum of the maximum support score for each key point provided by any source in that subset:
     $$U_{MAXSHAPLEY}(I) = \sum_{j=1}^{n} w_j \cdot \max_{i \in I} v_{i,j}$$
   • This utility function models the cooperative nature of sources (providing complementary information) and the competitive nature of overlapping information (only the best source for a specific point contributes to the utility).
   • Crucially, this structure allows for exact Shapley value computation in polynomial time. The problem decomposes into $n$ independent "max-games." For each key point, the Shapley values are computed by sorting the support scores and performing a linear scan, an $O(m \log m)$ operation. This avoids the exponential $O(2^m)$ cost of brute-force Shapley or the sampling variance of Monte Carlo approximations.

Key Contributions

1. Algorithmic Innovation: The paper introduces MAXSHAPLEY, a Shapley-based attribution algorithm specifically designed for generative search. It provides an exact, efficient $O(m \log m)$ algorithm for the max-function Shapley subproblem, derived from a general class of coverage games.
2. Black-Box Efficiency: Unlike prior context attribution methods (e.g., ContextCite, KernelSHAP) that rely on repeated context ablation or log-likelihood access, MAXSHAPLEY requires only black-box access to an attribution LLM and avoids repeated generation trials.
3. Empirical Validation: The authors demonstrate that MAXSHAPLEY achieves attribution quality comparable to exact Shapley computation (FullShapley) and strong alignment with human annotations, while consuming a fraction of the computational resources.
4. Open Resources: The authors release open-source code, manually re-annotated subsets of HotPotQA, MuSiQUE, and MS-MARCO, and an educational demo.

Experimental Results

The authors evaluated MAXSHAPLEY on three multi-hop QA datasets: HotPotQA, MuSiQUE, and MS-MARCO.

• Efficiency vs. Quality Trade-off: MAXSHAPLEY achieves a Jaccard index of 0.88 on MuSiQUE (comparable to FullShapley) while using only 5.4% of the tokens required by FullShapley. Compared to KernelSHAP, the strongest Shapley approximation baseline, MAXSHAPLEY achieves similar alignment with human annotations at less than 7% of the token cost.
• Correlation with Ground Truth: MAXSHAPLEY shows strong ordinal correlation (Kendall's $\tau_b$) with FullShapley on HotPotQA and MuSiQUE. On MS-MARCO, it achieves moderate correlation, though all Shapley methods showed degradation on this dataset, likely due to the noisier nature of the source content.
• Stability: By using localized semantic judgments (scoring source-keypoint pairs) rather than repeated whole-answer ablations, MAXSHAPLEY mitigates the scoring instability often observed in LLM-as-a-judge evaluations, where semantically equivalent answers receive different scores based on wording or source ordering.
• Scalability: Token consumption for MAXSHAPLEY scales linearly with the number of sources, whereas KernelSHAP exhibits super-linear scaling.

Significance and Claims

The paper claims that MAXSHAPLEY offers a practical pathway toward incentive-compatible generative search. By providing a fair, computationally efficient, and black-box method for attributing credit, it addresses the "extinction-level event" facing content providers in the era of AI-generated answers.

The authors position their work as a necessary evolution in the ecosystem, moving beyond sponsored search auctions (which benefit advertisers, not organic providers) to a model where content providers are compensated based on their actual contribution to the utility of the generated answer. The method satisfies the axiomatic requirements of fairness (Shapley values) while overcoming the computational barriers that have previously made such attribution infeasible in real-time search settings. The authors remain modest, noting that while the method is robust, it operates under a black-box assumption and that future work could explore white-box attribution or utility functions that explicitly reward corroborating evidence from multiple independent sources.