MaxShapley: Towards Incentive-compatible Generative Search with Fair Context Attribution

2025/12/05 by Mingxun Zhou, Patel, Sara, Giulia Fanti +2
Computer Science · #Artificial Intelligence (cs.AI) #Expert finding and Q&A systems #FOS: Computer and information sciences #Information Retrieval and Search Behavior #Machine Learning (cs.LG) #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2512.05958

openalex publication_date 2025/12/05 · openalex created_date 2025/12/09 · openalex updated_date 2026/07/28

Abstract

Generative search engines based on large language models (LLMs) are replacing traditional search, fundamentally changing how information providers are compensated. To sustain this ecosystem, we need fair mechanisms to attribute and compensate content providers based on their contributions to generated answers. We introduce MaxShapley, an efficient algorithm for fair credit attribution in generative search pipelines that retrieve external sources before generation. MaxShapley is a special case of the celebrated Shapley value; it leverages a de-composable max-sum utility function to compute attributions with polynomial-time computation in the number of documents, as opposed to the exponential cost of Shapley values. We evaluate MaxShapley on three multi-hop QA datasets (HotPotQA, MuSiQUE, MS MARCO); MaxShapley achieves comparable attribution quality to exact Shapley computation, while consuming a fraction of its tokens--for instance, it gives up to a 9x reduction in resource consumption over prior state-of-the-art methods at the same attribution accuracy. We release open-source code and re-calibrated datasets. An educational demo is available at https://fair-search.com.

Citations

• How to Correctly Report LLM-as-a-Judge Evaluations
• Generative Engine Optimization: How to Dominate AI Search
• GRADE: Generating multi-hop QA and fine-gRAined Difficulty matrix for RAG Evaluation
• Source Attribution in Retrieval-Augmented Generation
• The Attribution Crisis in LLM Search Results
• TokenShapley: Token Level Context Attribution with Shapley Value
• TracLLM: A Generic Framework for Attributing Long Context LLMs
• LAQuer: Localized Attribution Queries in Content-grounded Generation
• Attributing Response to Context: A Jensen-Shannon Divergence Driven Mechanistic Study of Context Attribution in Retrieval-Augmented Generation
• Learning to Attribute with Attention
• Real-time Ad retrieval via LLM-generative Commercial Intention for Sponsored Search Advertising
• SelfCite: Self-Supervised Alignment for Context Attribution in Large Language Models
• Data-Driven Mechanism Design: Jointly Eliciting Preferences and Information
• Attention with Dependency Parsing Augmentation for Fine-Grained Attribution
• A Survey on LLM-as-a-Judge
• AttriBoT: A Bag of Tricks for Efficiently Approximating Leave-One-Out Context Attribution
• ContextCite: Attributing Model Generation to Context
• The Llama 3 Herd of Models
• Adversarial Search Engine Optimization for Large Language Models
• Data Shapley in One Training Run
• Ad Auctions for LLMs via Retrieval Augmented Generation
• LLM Whisperer: An Inconspicuous Attack to Bias LLM Responses
• An Economic Solution to Copyright Challenges of Generative AI
• LLM Evaluators Recognize and Favor Their Own Generations
• Auctions with LLM Summaries
• Ads in Conversations
• The Butterfly Effect of Altering Prompts: How Small Changes and Jailbreaks Affect Large Language Model Performance
• Online Advertisements with LLMs: Opportunities and Challenges
• Lost in the Middle: How Language Models Use Long Contexts
• G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment
• TRAK: Attributing Model Behavior at Scale
• ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction
• MuSiQue: Multihop Questions via Single-hop Question Composition
• Sampling Permutations for Shapley Value Estimation
• Overview of the TREC 2020 deep learning track
• Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
• ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
• Overview of the TREC 2019 deep learning track
• REALM: Retrieval-Augmented Language Model Pre-Training
• Estimating Training Data Influence by Tracing Gradient Descent
• A Turvey-Shapley Value Method for Distribution Network Cost Allocation
• Data Shapley: Equitable Valuation of Data for Machine Learning
• HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering
• A Unified Approach to Interpreting Model Predictions
• Understanding Black-box Predictions via Influence Functions
• MS MARCO: A Human Generated MAchine Reading COmprehension Dataset
• "Why Should I Trust You?": Explaining the Predictions of Any Classifier
• A NEW MEASURE OF RANK CORRELATION

Related

• GEO: Generative Engine Optimization
• Source Attribution in Retrieval-Augmented Generation
• Learning to Rank for Multiple Retrieval-Augmented Models through Iterative Utility Maximization
• HAGRID: A Human-LLM Collaborative Dataset for Generative Information-Seeking with Attribution
• AttributionBench: How Hard is Automatic Attribution Evaluation?